Game theoretic modeling, analysis, and mitigation of security risks.

In the digital era we are living in today, cyber attacks are being carried by well organized and very sophisticated adversaries such as malicious insiders, cybercriminals, cyberterrorists, industrial spies, and in some cases, nation-state intelligence agents. Security experts must not only design and implement security solutions to defend against such sophisticated attackers, but they also need to find appropriate tools to measure and minimize the cost of security. To that end, many researchers have recently been considering the mathematical subject of Game Theory.

The application of game theoretic models to the security problem has many advantages. In addition to providing a principled way to understand security, Game Theory can capture the adversarial nature of the security problem. Also, instead of designing a defense against a specific attack, game theoretic models attempt to design a defense against a sophisticated attacker who plans in anticipation of a complex defense. As of such, both the defender and attacker's actions can be in principle computed and analyzed. With a game theoretic approach, equilibrium payoffs can serve as good metrics for the cost of security. Furthermore, Game Theory can model issues of trust, incentives, and externalities that arise in security systems.

In this talk, we consider three communication scenarios and show how, by modeling the interaction between an attacker and a defender as game, one can predict the adversary’s attack, determine the set of assets that are most likely to be attacked, suggest defense strategies for the defender, and gain some insights about the cost of security. In our first example, we study an intruder game where a given node of a network is receiving information via another node (relay) which might be compromised by an attacker. The attacker’s goal is to corrupt the information and deceive the receiver, while the receiver would like to minimize the cost of wrongly detecting a message. The second example is an intelligent virus game that models the strategic attempt of a virus designer to infect a network protected by an Intrusion Detection System (IDS). The IDS is trying to detect the presence of the virus as early as possible to minimize the infection cost. The analysis of the Nash equilibria of these games shows that in general, the most aggressive attackers are not always the most dangerous ones. We also show, for the intruder game, how, by introducing a challenge-response mechanism, one can reduce the the attacker's attack reward to zero.

In the third example, we study a network topology design game where a network designer is choosing a spanning tree on the graph of a network to connect all nodes. An attacker is trying to cut the tree by attacking one link of the graph. One of our findings in this scenario is that, the usual edge- connectivity metric for a graph is not the appropriate vulnerability measure in a network where strategic adversaries are present.

Computing Nash equilibria of a two-player game is known to be in general complex. We will show how, for a class of security games, one can compute a Nash equilibrium using algorithms that run in polynomial time

Speaker Bio: Assane Gueye has just joined NIST as a Guest Researcher at the Computing and Communication Theory Group (CCTG/ITL) working in collaboration with Dr. Vladimir Marbukh. He received his Ph.D. (March 2011) in EECS from UC Berkeley and his MSE in Communication Engineering from the Ecole Polytechnique Fédérale de Lausanne (EPFL)- Switzerland in 2004. Assane's recent work is on applying Game Theory notions to the Communication Security problem. His Ph.D. Dissertation “A Game Theoretic Approach to Communication Security” was supervised by Prof. Jean C. Walrand. In these approaches, the interaction between the attacker and the defender is modeled as a game and Nash equilibria are computed and analyzed. Assane has also worked on Bottleneck Identification in Complex Network and on Sensor Network deployment. His research interests also include Information and Communication Technologies for Development (ICT4D).

Presentation Slides: PPT

Note: Visitors from outside NIST must contact Robin Bickel; (301) 975-3668; at least 24 hours in advance.