Title: A graph-theoretic network security game

Authors: Marios Mavronicolas, Vicky G. Papadopoulou, Anna Philippou, Paul G. Spirakis

Addresses: Department of Computer Science, University of Cyprus, Nicosia CY-1678, Cyprus. ' Department of Computer Science, University of Cyprus, Nicosia CY-1678, Cyprus. ' Department of Computer Science, University of Cyprus, Nicosia CY-1678, Cyprus. ' Department of Computer Engineering and Informatics, University of Patras, Rion, Patras 26500, Greece; Research Academic Computer Technology Institute, Rion, Patras 26500, Greece

Abstract: Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. We model this practical network scenario as a non-cooperative multi-player game on a graph, with two kinds of players, a set of attackers and a protector player, representing the viruses and the system security software, respectively. We are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results: for certain families of graphs, mixed Nash equilibria can be computed in polynomially time. These families include, among others, regular graphs, graphs with perfect matchings and trees. The corresponding price of anarchy for any mixed Nash equilibria of the game is upper and lower bounded by a linear function of the number of vertices of the graph. (We define the price of anarchy to reflect the utility of the protector). Finally, we introduce a generalised version of the game. We show that the existence problem of pure Nash equilibria here is NP complete.

Keywords: graph theory; Nash equilibria; network security games; viral infections.

DOI: 10.1504/IJAACS.2008.021488

International Journal of Autonomous and Adaptive Communications Systems, 2008 Vol.1 No.4, pp.390 - 410

Published online: 28 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article