NIST logo

Publication Citation: Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach

NIST Authors in Bold

Author(s): Assane Gueye; Vladimir V. Marbukh;
Title: Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach
Published: February 13, 2012
Abstract: In this paper, we propose a quantification of the vulnerability of a communication network when links are subject to failures due to the actions of a strategic adversary. We model the adversarial nature of the problem as a 2-player game between a network manager who chooses a spanning tree of the network as communication infrastructure and an attacker who is trying to disrupt the communication by attacking a link. We use previously proposed models for the value of a network to derive payoffs of the players and propose the network‰s expected loss-in-value as a metric for vulnerability. In the process, we generalize the notion of betweenness centrality: a metric largely used in Graph Theory to measure the relative importance of a link within a network. Furthermore, by computing and analyzing the Nash equilibria of the game, we determine the actions of both the attacker and the defender. The analysis reveals the existence of subsets of links that are more critical than the others. We characterize these critical subsets of links and compare them for the different network value models. The comparison shows that critical subsets depend both on the value model and on the connectivity of the network. Knowing the critical parts of a network is crucial for network design and improvement. We describe an efficient algorithm that can be used to compute critical subsets of a graph.
Citation: IEEE Journal on Selected Areas in Communications
Keywords: Communication Network Security; Vulnerability Metric; Game Theory
Research Areas: Math, Assessment, Modeling
PDF version: PDF Document Click here to retrieve PDF version of paper (519KB)