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

Published

February 13, 2012

Author(s)

Assane Gueye, Vladimir V. Marbukh

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

Pub Type

Journals

Download Paper

Local Download

Keywords

Communication Network Security, Vulnerability Metric, Game Theory

Citation

Gueye, A. and Marbukh, V. (2012), Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach, IEEE Journal on Selected Areas in Communications, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=910926 (Accessed March 14, 2025)