Phân tích và thiết kế an ninh mạng theo lý thuyết trò chơi - Nghiên cứu của Kien Chi Nguyen

c 2011 Kien Chi Nguyen GAME THEORETIC ANALYSIS AND DESIGN FOR NETWORK SECURITY BY KIEN CHI NGUYEN DISSERTATION Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical and Computer Engineering in the Graduate College of the University of Illinois at Urbana-Champaign, 2011 Urbana, Illinois Doctoral Committee: Professor Tamer Başar, Chair Assistant Professor Tansu Alpcan, Berlin Technical University, Germany Professor Pierre Moulin Professor William H. Srikant ABSTRACT Together with the massive and rapid evolution of computer networks, there has been a surge of research interest and activity surrounding network security recently. A secure network has to provide users with confidentiality, authentication, data integrity and nonrepudiation, and availability and access control, among other features. With the evolution of current attacks and the emergence of new attacks, in addition to traditional countermeasures, networked systems have to adopt more quantitative approaches to guarantee these features.

In response to this need, we study in this thesis several quantitative approaches based on decision theory and game theory for network security. We first examine decentralized detection problems with a finite number of sensors making conditionally correlated measurements regarding several hypotheses. Each sensor sends to a fusion center an integer from a finite alphabet, and the fusion center makes a decision on the actual hypothesis based on the messages it receives from the sensors. We show that when the observations are conditionally dependent, the Bayesian probability of error can no longer be expressed as a function of the marginal probabilities.

We then characterize this probability of error based on the set of joint probabilities of the sensor messages. We show that there exist optimal solutions under both Bayesian and Neyman-Pearson formulations, in the general case as well as in the special case where the sensors are restricted to threshold rules based on likelihood ratios. We provide an enumeration method to search for the optimal thresholds, which works for both the case where sensor observations are given as probability density functions and the case where they are given as probability mass functions. This search algorithm is applied to a dataset extracted from TCP dump data to detect attacks from regular connections.

We also study two-player classical and stochastic fictitious play processes which can be ii viewed as sequences of nonzero-sum matrix games between an Attacker and a Defender. Players do not have access to each other’s payoff matrix. Each has to observe the other’s actions up to the present and plays the action generated based on the best response to these observations. However, when the game is played over a communication network, there are several practical issues that need to be taken into account: First, the players may make random decision errors from time to time.

Second, the players’ observations of each other’s previous actions may be incorrect. The players will try to compensate for these errors based on the information they have. We examine the convergence property of the game in such scenarios, and establish convergence to the equilibrium point under some mild assumptions when both players are restricted to two actions. We also propose and establish the local stability property of a modified version of stochastic fictitious play where the frequency update is time-invariant.

We then apply a fictitious play algorithm in the push-back defense against DDoS attacks and observe the convergence to a Nash equilibrium of the static game. We finally formulate the security problem on a network with multiple nodes as a two- player stochastic game between the Attacker and the Defender. We propose a linear model to quantify the interdependency among constituent nodes in terms of security assets and vulnerability. This model is general enough to address the differences in security asset valuation between the Attacker and the Defender, as well as the costs of attacking and defending.

We solve the game using an iterative algorithm when the game is zero-sum and using a nonlinear program in the general case when the game is nonzero-sum. The solutions provide the players with the optimal stationary strategies at each state of the network and the overall payoffs of the game. Numerical examples are presented to illustrate our model. Our analyses and designs in this thesis thus cover multiple components of the decision making and resource allocation processes in a network intrusion detection and prevention system.

They are meant to complement current research in network security with some quantitative approaches, in order to detect, prevent, and counter attacks more effectively. iii To my parents iv ACKNOWLEDGMENTS First, I would like to express my sincere thanks to my research adviser at the University of Illinois at Urbana-Champaign (UIUC), Professor Tamer Başar, for his guidance, advice, and support during my Ph. studies and research. It has been a great pleasure for me to work with and learn from him.

I would also like to thank Professor Tansu Alpcan (Deutsche Telekom Laboratories and the Technical University of Berlin, Germany) for his guidance, advice, and support during my Ph. research and my internships at Deutsche Telekom Laboratories. I am grateful to Professor Pierre Moulin, Professor William Sanders, and Professor Rayadurgam Srikant for serving on my Ph. committee, and for their valuable comments during my preliminary examination and final defense.

I also thank Professor Todd Coleman, Professor Minh Do, Professor Bruce Hajek, Professor P. Kumar, Professor David Nicol, and Professor Dilip Sarwate for their support with my coursework, research, and teaching assistantships at the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory (CSL) at UIUC. I would like to gratefully acknowledge the financial support from the Vietnam Education Foundation, Deutsche Telekom Laboratories, and the Boeing Company for my M. I also appreciate the support from CSL staff, especially that from Becky Lonberger, during my appointments in CSL.

And as always, I am indebted to my parents, my sister, my brother-in-law, and my nephews, Ben and Bean, for their love and encouragement. Finally, I would like to thank my collaborators, colleagues, and friends, who include, among others, Michael Bloem, Loc Bui, Praveen Bommannavar, Robin Chelliyil, Quang Do, Akshay Kashyap, Tanmay Khirwadkar, Hieu Le, Tung Le, Hoang Nguyen, Nghia Nguyen, Minh Pham, Thomas Riedl, Yu Ru, Nathan Shemonski, Hui Sun, Hamidou Tembine, Duan Tran, Anh Truong, Jayakrishnan Unnikrishnan, Loan Vo, and Xiaolan (Joy) Zhang. v TABLE OF CONTENTS CHAPTER 1 INTRODUCTION. 1 CHAPTER 2 DECENTRALIZED DETECTION WITH CONDITIONALLY DE- PENDENT OBSERVATIONS .2 Decentralized hypothesis testing with non-i.3 The existence of optimal solutions .4 A special case with bivariate normal distributions and simulation results .5 The majority vote versus the likelihood ratio test .6 An algorithm to compute the optimal thresholds .7 KDD Cup 1999 data and simulation results .8 Conclusion to the chapter.

42 CHAPTER 3 FICTITIOUS PLAY FOR NETWORK SECURITY .2 Static games and fictitious play .3 Classical fictitious play with decision and observation errors .4 Algorithms for stochastic fictitious play .5 Stochastic fictitious play with decision errors .6 Stochastic fictitious play with observation errors .7 Limiting Nash equilibrium of stochastic fictitious play .8 Stochastic fictitious play with time-invariant frequency update .9 Using fictitious play in the pushback mechanism against DDoS attacks .10 Conclusion to the chapter. 96 CHAPTER 4 STOCHASTIC GAMES FOR SECURITY IN NETWORKS WITH INTERDEPENDENT NODES .2 Linear influence network models for security assets and for vulnerabilities .3 The network security problem as a nonzero-sum stochastic game .4 The network security problem as a zero-sum stochastic game .5 Conclusion to the chapter. 128 vi CHAPTER 1 INTRODUCTION Together with the massive and rapid evolution of computer networks, there has been a surge of research interest and activity surrounding network security recently. Today’s attackers are much smarter and more computationally powerful than their predecessors, thanks to the rapid progress of electronic and computer engineering.

The ubiquitous Internet, empowered by state-of-the-art routers, high-bandwidth connections, and advanced access technologies, which provides users with never-before-seen data rates and flexibility, unfortunately, also fur- nishes attackers with the tools to carry out more distributed, more destructive, and stealthier assaults on networked targets. A secure network has to provide users with confidentiality, au- thentication, data integrity and nonrepudiation, and availability and access control, among other features [1, 2]. Nowadays, with the evolution of current attacks and the emergence of new attacks, in addition to traditional countermeasures, networked systems have to adopt more quantitative approaches to guarantee these features. In response to this need, we study in this thesis several quantitative approaches based on decision theory and game theory for network security.

On the one hand, when dealing with theories, we take into account specific conditions and ramifications that arise in the context of network security in order to come up with meaningful results. One the other hand, the analyses and the models are meant to be general enough to be applicable to a wide range of network security problems, whether they arise in wired or wireless networks. We do, however, attempt to apply the theoretical results to specific network security problems whenever possible. That way, we hope to be able to first verify the theoretical findings using real-world problems, and then observe the complications that may lessen the impact and use of these theories.

While network security, which spans all the layers of the Open Systems Interconnection 1 model, is a collection of many different subjects of study, from cryptography to security protocols, from hardware security to resource allocation, from dependability to privacy [3,4], we restrict ourselves to a class of network security problems that deal with decision making and resource allocation. The results thus will be better comprehended from a systemic point of view. We assume a very dynamic environment and sophisticated players who can allot their resources across multiple heterogeneous targets and adjust their strategies over time. We then impose practical constraints arising from limited communication bandwidths and the imperfection of the decision and observation processes.

We also take into account the correlation among the observations from different agents and the interdependency among all the nodes in a network. In this dissertation, we first look at the problem of detecting attacks in a networked sys- tem (Chapter 2). This is considered to be the task of the network intrusion detection (and prevention) system (IDS – IDPS). Although an IDS (IDPS) could be either host-based or network-based, in this work we generally use the term IDS (IDPS) to refer to a network intrusion detection system (network intrusion detection and prevention system).

Intrusion detection approaches are normally classified into two categories: anomaly detection and mis- use detection. In anomaly detection, the IDS characterizes the correct and/or acceptable behavior of the system to detect wrongful behavior. Misuse detection, in contrast, uses known patterns of penetration/attack to detect intrusion. These approaches, while working well with attacks whose attributes are remarkably different from regular traffic (for anomaly detection), or with attacks that follow fixed patterns in terms of protocols and traffic fea- tures (for misuse detection), fall short of dealing with attackers who can adjust their traffic parameters in more flexible manners.

We thus examine in this work the use of hypothesis testing for attack detection. In hypothesis testing-based approaches, one generally has to characterize both regular traffic and attacks in terms of parameter distributions. These ap- proaches can thus be considered to lie somewhere in between anomaly detection and misuse detection [4]. Three formulations that are most widely used in hypothesis testing are Bayesian, minimax, and Neyman-Pearson.

In Bayesian hypothesis testing, we are given prior distributions (of some parameters) of the hypotheses, and based on the observations of these parameters, 2 we pick a hypothesis that minimizes the average cost. An alternative formulation that is used when the prior distributions are unknown is the minimax approach, where we minimize the maximum of the conditional costs given each hypothesis. If a cost structure is not well defined or is not available, we can use the Neyman-Pearson formulation, where we minimize the miss probability given an upper bound on the false alarm probability.