Designing information and communication systems that are robust and resilient to attacks has been and continues to be an important and challenging topic. One of the main difficulties resides in quantifying the vulnerability/robustness of a system in the presence of an intelligent attacker who might exploit the structure of the system to design harmful attacks. To capture the strategic nature of the interactions between a defender and an adversary, game theoretic models have been gaining a lot of interest in the study of the security of information and communication systems.
In this talk, I will introduce the notion of blocking games and discuss how it can be used to design a framework for analyzing robustness/vulnerability of information systems in adversarial environment. Blocking games model abstract situations where an agent (the defender) needs to choose a subset of a finite set of resources to perform a mission critical task. The resources can be the links/nodes of a network, a set of computer programs, or a set of servers in a data center. An attacker wants to disrupt the task by choosing some resource(s) to attack. We have studied such a scenario as a quasi-zero-sum, 2-player game and, using the theory of Blocking Pairs of Polyhedra, we have provided a closed-form characterization of its Nash equilibria.
I will particularly discuss network blocking games: an application of blocking games to the analysis of communication networks vulnerability/robustness in adversarial environment. In these models, the goal of the defender (network operator) is to maintain some connectivity by choosing a subset of links in the network. The attacker wants to disrupt the communication by attacking the links. The Nash equilibrium strategies are then used to predict the most likely attackers actions and the Nash equilibrium payoff serves as a quantification of the vulnerability/robustness of the network. Using illustrative examples, I will discuss network vulnerability metrics derived from these models and how these metrics can be used to design robust networks and/or strengthen the robustness of existing ones. I will also show how these metrics can be used to identify the most critical links in a network.
This is joint work with Prof. Jean C. Walrand, Prof. Venkat Anantharam (UC Berkeley), Dr. Vladimir Marbukh (NIST), and Aron Lazska (Budapest University of Technology and Economics).