Game Theory Based Network Security

By Yi Luo , Ferenc Szidarovszky , Youssif Al-Nashif , Salim Hariri, 2010

Summary

Game theory is an appropriate methodology to model the interactions between attackers and network administrator and to determine the best countermeasure strategy against attacks. There are however some difficulties in directly applying classical game theory, since the attackers’ strategies are uncertain, their steps are not instantaneous, the rules of the games might change in time, and so on. Therefore any game theory based methodology has to take these difficulties into account. There are many types of intrusions. Multi-stage attacks are the most destructive and most difficult kinds for any defense system. They use intelligence to strategically compromise the targets in a planned sequence of actions, so the usual methodology designed to protect against single-stage attacks cannot be used.

This paper introduces a multi-stage intrusion defense system, where the interactions between the attacker and the administrator are modeled as a two-player non-cooperative non-zero-sum dynamic game with incomplete information. The two players conduct Fictitious Play along the game tree, which can help the administrator to find quickly the best strategies to defend against attacks launched by different types of attackers. The algorithm is an online procedure, which gives the most appropriate response of the administrator at any stage of the game. So it has to be repeated at all actual decision nodes of the administrator. Their algorithm is different than the usual methods based on decision trees, since at each step only a finite horizon is considered, instead of expected outcomes certain equivalents are used and the probabilities of the different arcs are continuously updated based on new information.

Multi-stage attacks are represented by special game trees. Figure 1 shows the first two interactions on a game tree. The attacker is the leader, the administrator is the follower. The root of the tree is the initial decision node of the attacker, and the possible initial moves of the attacker are represented by the arcs originating at the root. These actions might include attacking the server with different intensity levels, sending a virus to a group of customers, etc. At the end point of each arc the administrator has to respond, so they are its decision nodes. After the administrator’s response the attacker makes the next move, and so on. This tree continuous until the intruder gives up the attack or reaches its goals. This tree can become very large and the payoff values at the decision nodes are uncertain, therefore the classic method, known as backward induction, cannot be used in this case.

Figure 2 shows a network structure. It is assumed that the HTTP server, Database 2, the FTP1 server and the information in the CEO are the vulnerable components in the network system, and access to the information in the CEO is the attacker’s objective. It is also assumed that the CEO needs services provided by the HTTP server, Database 2 and the FTP1 server to do its jobs. The attacker can launch multi-stage attacks to obtain the information from the CEO in many different ways. Then the administrator can respond to it by selecting from a set of options, and so on, which leads to the game tree. Next they assume that in addition to the sensitive data in the CEO the data in the Accounting is another vulnerability of the system. The attacker has now two objectives: the information in CEO and the data in Accounting. The Accounting also needs services provided by Database 2 and the HTTP server, etc. The computer study assume that the attacker always selects the action leading to maximal impact, and the administrator always selects its best action at its decision nodes by using one of the three tested algorithms.

They applied three methods to find the best responses of the administrator: One is a greedy algorithm (GA) in which the administrator completely blocks the traffic of  corresponding services on routers, firewall, or disconnect the machines using managed switches, etc. regardless of what kind of attack occurs or what is the intensity levels of the attack. Another algorithm is also myopic, single-interaction optimization algorithm (SO) in which the administrator tries to minimize the loss from the most current attack at each interaction without considering future interactions with the attacker. The third algorithm is the one they developed. The results are shown Table 1. Two types of attacks were assumed. The risk seeking attacker worried about only the expectation of the impact (α = 0 ), while the risk neutral intruder selected a relatively high risk taking coefficient (α =1). The two scenarios refer to the cases of one or two objectives of the attacker. The last three columns indicate the three methods which were used for comparison. The numbers in the last three columns of the table show the total losses of the system with using different methods.

Results

Clearly their method resulted in the smallest overall losses in all cases, where the loss reduction was 41%, 51%, 52% and 58% in comparison to the Greedy Algorithm, and 23%, 30%, 29% and 36% in comparison to single-interaction optimization.

Critique

They assert that their  algorithm is different than the usual methods based on decision trees, since at each step only a finite horizon is considered, instead of expected outcomes certain equivalents are used and the probabilities of the different arcs are continuously updated based on new information.  The performance of their algorithm is much better than that of other algorithms based on the results of their numerical experiments. The loss reduction varies between 23% and 58%. However, the biggest issue about the article is their ambiguous process . They do not show their calculations and it makes harder to understand their approach.

Luo, Y., Szidarovszky, F., Al-Nashif, Y., & Hariri, S. (2010). Game theory based network security. Journal of Information Security, 1(01), 41

Source: http://www.scirp.org/journal/PaperInformation.aspx?paperID=2330