Game Theory for Networks. Third International ICST Conference, GameNets 2012, Vancouver, BC, Canada, May 24-26, 2012, Revised Selected Papers

Research Article

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

Download
469 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-35582-0_20,
        author={Assane Gueye and Vladimir Marbukh and Jean Walrand},
        title={Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach},
        proceedings={Game Theory for Networks. Third International ICST Conference, GameNets 2012, Vancouver, BC, Canada, May 24-26, 2012, Revised Selected Papers},
        proceedings_a={GAMENETS},
        year={2012},
        month={12},
        keywords={Vulnerability Metric Value of Communication Network Spanning Tree Betweenness Centrality Critical Links Nash Equilibrium},
        doi={10.1007/978-3-642-35582-0_20}
    }
    
  • Assane Gueye
    Vladimir Marbukh
    Jean Walrand
    Year: 2012
    Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach
    GAMENETS
    Springer
    DOI: 10.1007/978-3-642-35582-0_20
Assane Gueye1, Vladimir Marbukh1, Jean Walrand2
  • 1: National Institute of Standards and Technology
  • 2: University of California

Abstract

In this paper, we propose a quantification of the vulnerability of a communication network where 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 as a metric for vulnerability. In the process, we generalize the notion of centrality: a metric largely used in Graph Theory to measure the relative 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.