Game theoretic analysis and design for network security

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 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