Nonfunctional Requirements Validation Using Nash Equilibria
Andreas Gregoriades, Vicky G. Papadopoulou · Sciyo eBooks · 2010
Recent work by [KO04,ACY05] and [MPPS05b,MPPS05c], initiated the introduction of strategic games on graphs (and the study of their associated Nash equilibria) as a means of studying security problems in networks with selfish entities.By selfish we mean that each entity in the game aims to maximize its utility.In the security games studied in [KO04], a large number of players must make individual decisions related to security.The ultimate safety of each player may depend in a complex way on the actions of the entire population.[MPPS05b, MPPS05c] considers a security problem on a distributed network modeled as a multi-player non-cooperative game with attackers (e.g., viruses) and a defender (e.g., a security software) entities.More specifically, there are two classes of confronting randomized players on a graph: attackers, each choosing vertices and wishing to minimize the probability of being caught, and a single defender, who chooses edges and gains the expected number of attackers it kills.A subsequent work [MMPPS06] introduced the Price of Defense in order to evaluate the loss in the provided security guarantees due to the selfish nature of attacks and defenses.This notion can be also seen as a (negative) measurement of the network security.A collection of polynomial computable Nash equilibria with guarantee defense ratio (i.e.security level) is presented. Road MapThe paper is organised as follows.Firstly, we illustrate the principles of game theory, followed with a description of the approach.The important question that arises here is the following: '' Given the limited capabilities of the system security software, which part of the network should it choose to clean or protect from possible attack, so that the security level achieved is at least equal to the required level specified by the network designer?'' Game TheoryGame Theory is a branch of applied mathematics that attempts to analytically model the rational behavior of intelligent agents in strategic situations, in which an individual's success depends on the decisions of others.While initially developed to analyze competitions in which one individual does better at another's expense, it evolved into techniques for modeling a wide class of interactions, characterized by multiple criteria.Most of the existing and foreseen complex networks, such as the Internet, are operated and built by thousands of large and small entities (autonomous agents), which collaborate to process and deliver end-to-end flows originating from and terminating at any of them.Recently, Game Theory has been proven to be a powerful modeling tool to describe such selfish, rational and at the same time, decentralized interactions [C01, O94].In particular, Game Theory was successfully utilized for analyzing and most importantly evaluating the performance of existing networks in various aspects.Examples of such performance aspects include makespan, throughput, latency, resource utilization, users' satisfaction as well as security guarantees [R05, R02, ACY05, ADTW03, KP99, T04].At the same time, a significant branch of Game Theory, Mechanism Design [NR99] is used to design future networks given a number of functional requirements specifications.Game Theory has been used to understand selfish rational behaviour of complex networks, e.g. the Internet, of many "agents" (consisting the players of the game).In such domains, www.intechopen.