Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Game Theoretical Approach to Communication Security

Assane Gueye

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2011-19
March 14, 2011

http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-19.pdf

The tremendous advances we have witnessed the last four decades in the area of Information Technologies and Communications (ICT) did not come without their share of problems: they have brought an increasingly number of security concern. The many of cyber incidents that occur in the recent history is a good illustration of these concerns. These attacks are being carried by attackers that are becoming more and more sophisticated. The greatest security threats today are not coming from those script-kiddies and fame-driven hackers who attack communication systems just to impress their peers. In this digital age, security systems have to be designed and implemented to defend against well organized and very sophisticated adversaries such as malicious insiders, cybercriminals, cyberterrorists, industrial spies, and in some cases, nation-state intelligence agents. Being able to defend against and survive these new types of attackers is ``vital’’, and it is quite widely accepted that to achieve that goal, traditional security solutions alone are insufficient and new techniques for modeling, analyzing, and implementing communication security solutions have to be explored. In this thesis, we propose a Game Theoretical approach to the security problem, and using illustrative examples, we 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, and suggest defense strategies for the defender. We consider an intruder game where a given node of the network is receiving information via another node (or relay) which might be compromised by an attacker. The attacker’s goal is to corrupt the information and deceive the receiver. Our intelligent virus game models the strategic attempt of a virus designer to infect a network protected by an Intrusion Detection System (IDS). Finally, in our matrix security game models, we solve a class of security problems where a defender needs to choose a set of resources to perform a mission critical task. An attacker is trying to disrupt the task by choosing one resource to attack. By modeling the interactions between defenders and attackers as games we predict the adversaries’ attacks, determine the set of assets that are most likely to be attacked, and suggest defense strategies for the defender. For example in the intruder and virus games, we have found that the most aggressive attackers are not the most dangerous ones. Also, by analysis the NE solutions, we have shown how to build security mechanisms that can deter a strategic attacker from attacking. In the security game models, we introduce the notion of ``critical subset of resources’’ and show how this notion can be used to define a security metric. For instance, considering a network topology design game, we found that the usual edge-connectivity metric (size of a minimum cut set) is not appropriate in an adversarial environment.

Advisor: Jean Walrand


BibTeX citation:

@phdthesis{Gueye:EECS-2011-19,
    Author = {Gueye, Assane},
    Title = {A Game Theoretical Approach to Communication Security},
    School = {EECS Department, University of California, Berkeley},
    Year = {2011},
    Month = {Mar},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-19.html},
    Number = {UCB/EECS-2011-19},
    Abstract = {The tremendous advances we have witnessed the last four decades in the area of Information Technologies and Communications (ICT) did not come without their share of problems: they have brought an increasingly number of security concern. The many of cyber incidents that occur in the recent history is a good illustration of these concerns.

These attacks are being carried by attackers that are becoming more and more sophisticated.  The greatest security threats today are not coming from those script-kiddies and fame-driven hackers who attack communication systems just to impress their peers. In this digital age, security systems have to be designed and implemented to defend against well organized and very sophisticated adversaries such as malicious insiders, cybercriminals, cyberterrorists, industrial spies, and in some cases, nation-state intelligence agents.

Being able to defend against and survive these new types of attackers is ``vital’’, and it is quite widely accepted that to achieve that goal, traditional security solutions alone are insufficient and new techniques for modeling, analyzing, and implementing communication security solutions have to be explored.

In this thesis, we propose a Game Theoretical approach to the security problem, and using illustrative examples, we 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, and suggest defense strategies for the defender.
 We consider an intruder game where a given node of the network is receiving information via another node (or relay) which might be compromised by an attacker. The attacker’s goal is to corrupt the information and deceive the receiver.  
Our intelligent virus game models the strategic attempt of a virus designer to infect a network protected by an Intrusion Detection System (IDS).

 Finally, in our matrix security game models, we solve a class of security problems where a defender needs to choose a set of resources to perform a mission critical task. An attacker is trying to disrupt the task by choosing one resource to attack.
By modeling the interactions between defenders and attackers as games we predict the adversaries’ attacks, determine the set of assets that are most likely to be attacked, and suggest defense strategies for the defender.
For example in the intruder and virus games, we have found that the most aggressive attackers are not the most dangerous ones. Also, by analysis the NE solutions, we have shown how to build security mechanisms that can deter a strategic attacker from attacking.

In the security game models, we introduce the notion of ``critical subset of resources’’ and show how this notion can be used to define a security metric. For instance, considering a network topology design game, we found that the usual edge-connectivity metric (size of a minimum cut set) is not appropriate in an adversarial environment.}
}

EndNote citation:

%0 Thesis
%A Gueye, Assane
%T A Game Theoretical Approach to Communication Security
%I EECS Department, University of California, Berkeley
%D 2011
%8 March 14
%@ UCB/EECS-2011-19
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-19.html
%F Gueye:EECS-2011-19