UC Berkeley

The increased reliance on the Internet has made information and communication systems more vulnerable to security attacks.

Many recent incidents demonstrate this vulnerability, such as the rapid propagation of sophisticated malwares, the fast growth of botnets, denial-of-service (DoS) attacks against business and government websites, and attacks against the power grid system.

Experts must design and implement security solutions 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.

Instead of designing a defense against a specific attack, Game Theory attempts to design a defense against a sophisticated attacker who plans in anticipation of a complex defense. By including this `second-guessing' element into the design process, Game Theory has the potential of crafting improved security mechanisms. In addition, Game Theory can model issues of trust, incentives, and externalities that arise in security systems.

This thesis illustrates the potential usefulness of Game Theory in security. By modeling the interactions between defenders and attackers as games in three types of common communication scenarios, we predict the adversaries' attacks, determine the set of assets that are most likely to be attacked, and suggest defense strategies for the defenders.

The first example is a communication scenario where some components might be compromised. Specifically, we consider Bob who is receiving information that might be corrupted by an attacker, Trudy. We model the interaction between Trudy and Bob as a zero-sum game where Trudy chooses whether and how to corrupt the data and Bob decides how much he should trust the received information. By analyzing the Nash equilibrium of the game, we have determined when Bob should trust the received information, and how Trudy should corrupt the data. We have also shown how a challenge-response option for Bob can

deter Trudy from corrupting the information.

The second example is a scenario where an intelligent virus is attempting to infect a network protected by an Intrusion Detection System (IDS). The IDS detects intrusions by analyzing the volume of traffic going inside the network. We model the interaction of the intelligent virus and the IDS as a zero-sum game where the IDS chooses the detection threshold, while the virus is trying to

choose its infection rate to maximize its ultimate spreading.

Using a Markov chain model, we compute the Nash equilibria of the game and analyze them. In general, a more aggressive virus is more damaging but is also faster to detect. Hence, in its best attack, the intelligent virus chooses an infection rate that balances between

an aggressive attack that can be easily detected and a slow attack that causes less damage. The best defense strategy against such a sophisticated virus is to quarantine the traffic and analyze it prior to letting it go inside the network (in addition to setting the optimal threshold).

The third example is a blocking security game. For this game, given a finite set of resources S, a defender needs to choose a feasible subset T of S

of resources to perform a mission critical task. The attacker, at the same time, tries to disrupt the task by choosing one resource e of S to attack. Each resource e of S has a cost &mu(e) of attack. The defender loses some value &lambda(T,e) whenever the task is disrupted

(i.e. the attacked resource &me belongs to his subset &T). This loss goes to the attacker. We analyze the game by using the combinatorial tools of blocking pairs of matrices (hence the name blocking security game).

We introduce the notion of critical subset of resources and use this notion to define a vulnerability metric for the task. We find that, in Nash equilibrium, the attacker always targets a critical set of resources and the defender chooses a feasible subset that minimally intersects that critical subset. We illustrate the model with two examples of communication scenarios that consider design of network topology in the presence of a strategic adversary.

The first example studies a scenario where a network manager is choosing a spanning tree of a graph while 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. The second example deals with a supply-demand network where a network manager is choosing a feasible flow to transport the maximum amount of goods from a set of sources to a set of destinations,

and an attacker is trying to minimize this by attacking an arc of the network. In this case, we find that critical subsets of links are cutsets that maximize the minimum fraction of goods carried per link of the cutset. In most cases, these correspond to minimum cutsets of the graph.

Although computing Nash equilibria of a two-player game is generally complex, we have shown how, for a class of blocking games, one can compute a critical set of resources (hence a Nash equilibrium) in polynomial time.