A graph-theoretic network security game
Date
2005ISSN
0302-9743Source
1st International Workshop on Internet and Network Economics, WINE 2005Volume
3828 LNCSPages
969-978Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Consider a network vulnerable to viral infection. The system security software can guarantee safety only to a limited part of the network. 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. Each attacker player chooses a node of the graph (or a set of them, via a probability distribution) to infect. The protector player chooses independently, in a basic case of the problem, a simple path or an edge of the graph (or a set of them, via a probability distribution) and cleans this part of the network from attackers. Each attacker wishes to maximize the probability of escaping its cleaning by the protector. In contrast, the protector aims at maximizing the expected number of cleaned attackers. We call the two games obtained from the two basic cases considered, as the Path and the Edge model, respectively. We are interested in the associated Nash equilibria on them, where no network entity can unilaterally improve its local objective. We obtain the following results: - The problem of existence of a pure Nash equilibrium is script N sign P-complete for the Path model. This opposed to that, no instance of the Edge model possesses a pure Nash equilibrium, proved in [4]. - We compute, in polynomial time, mixed Nash equilibria on corresponding graph instances. These graph families include, regular graphs, graphs that can be decomposed, in polynomially time, into vertex disjoint r-regular subgraphs, graphs with perfect matchings and trees. - We utilize the notion of social cost [3] for measuring system performance on such scenario here is defined to be the utility of the protector. We prove that the corresponding Price of Anarchy in any mixed Nash equilibria of the game is upper and lower bounded by a linear function of the number of vertices of the graph. © Springer-Verlag Berlin Heidelberg 2005.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
On supporting security and privacy-preserving interaction through adaptive usable security
Belk, Marios; Fidas, Christos A.; Germanakos, Panagiotis; Samaras, George S. (2014)The purpose of this paper is to propose a preliminary framework for supporting usable security on the World Wide Web through adaptivity in user interface designs. In particular we elaborate the concept of "Adaptive Usable ...
-
Master Thesis
Security in e-Health: Information classification mapping into security technologies
Stavrou, Eliana (Πανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών / University of Cyprus, Faculty of Pure and Applied Sciences, 2006-06)This research work addresses security-related issues in the electronic and mobile healthcare environments and proposes an appropriate security framework. The proposed framework will identify the necessary security technologies ...
-
Conference Object
Secure Event Logging Using a Blockchain of Heterogeneous Computing Resources
Koumidis, K.; Kolios, P.; Ellinas, Georgios; Panayiotou, Christos G. (2019)Secure logging is essential for the integrity and accountability of cyber-physical systems (CPS). To prevent modification of log files the integrity of data must be ensured. In this work, we propose a solution for secure ...