Game Theoretic Modeling of Network Security Attacks
This paper deals with modeling of network's dynamic using game theory approach. The process of interaction among players (network users) trying to maximize their payoffs (e.g. throughput) could be analyzed using game based concepts (Nash equilibrium, Pareto efficiency, evolution stability etc) In this work we presented the model of TCP network's dynamic and proved existence and uniqueness of solution, formulated payoff matrix for a network game and found conditions of equilibrium existence depending of loss sensitivity parameter. We consider influence if denial of service attacks on the equilibrium characteristics and illustrate results by simulations. 1.0 INTRODUCTION It is almost impossible now to imagine our life without computer networks. Only for several decades, the Internet has rapidly transformed the ways in which individuals, societies and even governments communicate, exchange information and conduct their economic and social activities. And this process is far from the ending. As was envisioned recently by Google's executive chairman Eric Schmidt: "the internet will disappear as everything in our life gets connected. There will be so many devices, sensors, things that you are wearing, things that you are interacting with that you won't even sense it. It will be part of your presence all the time." It seems that future Internet has to be self organizing, self protecting, and self optimizing. This nextgeneration communication environment will include interaction of intelligent devices that are capable of autonomously take decisions within highly dynamic and rapidly changing digital world. However, the continuous (and successful till now) development of networks, which is accompanied by exponential growing of their complexity, heterogeneity and distributiveness and which appears natural at the present time, creates new challenging problems. As mentioned in [1] to address these problems with appropriate approach we need to develop a new set of models based on control theory, game theory, and network optimization. First, let us introduce a problem on a high level. Consider a interaction between selfish users in a network (network here is some common pool with limited resources) Each user can adopt a method of action (strategy) which have influence on whole network and other users. The examples of actions are: choose protocol, change rate or route of data flows. For every possible combination of adopted strategies (outcome) there is a reward or utility for each user, which indicates his/her preferences over outcomes. Selfishness (or rationality in game theory terminology) means that a user wants to maximize utility. For instance, when user wants to download big file he prefers to receive as much network resources as possible. However, if user wants to read news then small but stable connection is sufficient. This situation leads to obvious conflict when summary users' demand is bigger then network supply. If this happens network drops or delays users' data, so generally it is not good for users. From the other side, network underloading (when demand is smaller then network capacity) is also undesirable because leads to inefficiency of resource using. Delivering information about network state to end user is a challenging problem and crucial part of any feedback based protocol. As a rule user has knowledge about successful delivery of his data (in other words he knows that network is probably underloaded) and about overload event (if he doesn't receive successful STO MP MSG 133 3 1 ACK acknowledgement packet) with some delay. This type of information is called binary feedback. The natural rate control based on this information called AIMD (additive increase, multiplicative decrease) scheme. There are another possibilities, but it was proved that AIMD algorithm will oscillate near the point of effective (all bottle necks will be loaded) and fair (in some sense) allocation of network resources. AIMD was the core of first version of first successful protocol TCP, which still carries 70 percent of the Internet traffic. Nowadays, TCP isn't one protocol but big family (number keeps increasing) of algorithms with different implementations of the origin idea. Protocol development went through the competitive evolution between different protocols, abandonment of some of them and appearance of new ones. The possibility to deploy new versions of protocols gives user control to improve performance of his connection by choosing suitable algorithm. When many users are trying to achieve better performance it is difficult to predict consequences of such a competition. There is a problem how to ensure stable, fair and effective network behavior in the situation of dynamic and antagonistic interaction of selfish users. First natural approach to address this problem with optimization framework was developed in work by Kelly et al. [3] Later it was shown that congestion control, routing and scheduling in wired and wireless networks can be thought of as fair resource allocation. The protocols in this framework are nothing else as algorithms that allow a decentralized solution of the problem. This idea to consider network as an algorithm for solving maximization problem of total network utility (sum of users' utilities) proved to be very fruitful [2] The limitation in this approach is that protocol (in centralized or decentralized manner) dictates what strategy user should use. It is natural to assume that users try to improve performance of their connection by choosing suitable protocol. The problem here lies in interaction between different implementations of TCP which could be "unfriendly" This means that one implementation is more "aggressive" and another is more "peaceful" in competition for resources. The question of protocols interaction is quite complex. Building analytic model for predicting network behavior for different protocols is a challenging problem. There are many approaches of investigation of complex networks from different directions (static, dynamic, deterministic etc) There is, however, novel systematic approach towards network modeling the game theory. Game theory addresses problems in which multiple players with conflicting goals compete with each other. The evolutionary games concept is a part of game theory that focuses on studying interactions between populations rather than individual players. One of the earliest publications about the use of evolutionary games in networking is [4] that study through simulations some aspects of competition between TCP users. For this model it was shown that dynamic of this process described by difference equation has stable solution and users payoffs are forming a structure of evolutionary game known as Hawk Dove game. Also there were identified conditions under which equilibrium is evolutionary stable. There is another possible reason of inefficient, unstable or unpredictable network behavior security violation. Unfortunately, networks have many security issues: illegal data access, viruses, network attacks, etc. One of the most dangerous attacker's activities are Denial of Service (DoS) attacks. DoS attack aims to stop the service provided by a target. When the traffic of a DoS attack comes from multiple sources, it called a Distributed Denial of Service (DDoS) attack. By using multiple attack sources, the power of a DDoS attack is amplified and the problem of defense is made more complicated. Currently we have numerous DoS attack types. Each attack uses some special exploit of Internet protocols or software weaknesses. Recently novel type of attack was developed. This low rate attacks, using carefully calculate timing, imply significant inefficiencies that tremendously reduce system capacity or service quality. In the literature, this kind of network intrusion is called shrew attack or Reduction of Quality (RoQ) attack. This constant development of new attacks demands new solutions especially in attack detection area. Intrusion Detection Systems (IDSs) is a software which is used to monitor events occurring in a network. An IDS is also used to analyze these events in order to determine whether an attack has occurred. Once an attack is detected, a report is sent to the network administrator. Current IDSs are not very sophisticated and rely on ad hoc schemes and experimental algorithms. Due to these, IDSs need theoretical tools to handle Game Theoretic Modeling of Network Security Attacks 3 2 STO MP MSG 133 sophisticated, organized attacks. Game theoretic approaches have been proposed by many researchers to improve network security, for example to analyze high level "security investment game" but these models usually don't include network dynamics. Game theory provides mathematical base for analyzing and modeling security problems with many agents which could interact in complex, dynamic environment. The advantage of game theory approach is s possibility of analyzing many different scenarios before adopting a certain strategy. Using mathematical modeling we can simulate network topology, controlling algorithms and users' actions. This model could greatly improve network administration by predicting future security problems and likely behavior of users before we actually start to build our network. On the other hand network security measurements involve risk assessment. For example, one of the metrics is the probability of it being attacked. If we adopt game theory view on network dynamic then we can formulate conditions when interaction between rational users leads to an equilibrium state of the network. Network attack is a result of malicious actions of attacker. Attack changes equilibrium characteristics and could be therefore detected. In this work we describing integrated approach based on game theory models. First, we introduce formal model of TCP network dynamic. We mainly focus on AIMD behavior because it is the most important mechanism of T