Game theoretic analysis and design for network security :Doctor of Philosophy - Major: Electrical and Computer Engineering

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¸sar, Chair

Assistant Professor Tansu Alpcan, Berlin Technical University, Germany

Professor Pierre Moulin

Professor William H. Sanders

Professor R. 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