Thursday, October 18, 2012

Study Group: Game Theory in Internet Security

This study group was chaired by Theo Tryfonas and Theo Spyridopoulos and focused on applications of Game Theory in Internet Security. The discussion was based on the work presented in the following two publications:
  1. Sankardas Roy, Charles Ellis, Sajjan Shiva, Dipankar Dasgupta, Vivek Shandilya, Qishi Wu, "A survey of game theory as applied to network security," Hawaii International Conference on System Sciences (HICSS), 2010 [ doi ]
  2. Qishi Wu, Sajjan Shiva, Sankardas Roy, Charles Ellis, Vivek Datla, "On modeling and simulation of game theory-based defense mechanisms against DoS and DDoS attacks," Spring Simulation Multiconference (SpringSim '10), 2010 [ doi ]
In the first paper, introduced by Theo Tryfonas, the authors present a survey and taxonomy of existing game-theoretic approaches designed to enhance network security. Current research into network security only considers non-cooperative games. Since they are one-shot, static non-cooperative games are by definition of imperfect information (at least one player is not aware of at least one other player's previous moves). Conversely, dynamic games can be of either perfect or imperfect information. Both game categories can be either complete (every player knows all other players' strategies and payoffs) or incomplete. After briefly discussing the characteristics of each game type, they classify many existing game-theoretic network security approaches into one of the investigated game categories.

During the second part of the discussion, we took a dive into the details of how game-theory can be employed to protect a network against DoS and DDoS attacks and more specifically on attacks aiming to deplete the network's bandwidth. The interaction between the malicious user and the network administrator is modeled as a non-zero-sum game between two players.

In this work, the authors investigate two scenarios:
  • The attacker controls a single node (DoS)
  • The attacker controls multiple nodes (DDoS)
The only countermeasure available to the defending player is a firewall. There is a pipe of limited bandwidth B connecting the firewall with the service under attack. If T is the rate of the traffic crossing the pipe, the attack is considered successful if T > B, resulting in some legitimate traffic getting dropped.

In both situations, the attacker tries to choose the optimal number of attacking nodes (in the DDoS scenario) and to optimise each node's traffic transmission rate. The defender aims to configure the firewall in a way that will block as much malicious traffic as possible, while dropping as little legitimate traffic as possible.

The authors first investigate a static, one-shot game, whereby the two players decide on their strategy before the game starts and they are not allowed to change it afterwards. Subsequently, the authors discuss a dynamic game, whereby players are allowed to adjust their strategies as the game progresses.

The scenarios adopt the following metrics:

Legitimate User Traffic: When not under attack (na: no attack), the network has traffic from n legitimate users with total rate Tna where Xi is the traffic sending rate of user i.
Tna = X1 + X2 + ... + Xn
If all Xi follow a Normal Distribution, then Tna will also follow a Normal Distribution. Additionally, the model makes the assumption that under normal operation, Tna < B with high probability.

The attacking player controls the number of attacking nodes (m) and each node's traffic sending rate rA (common for all nodes). The DoS scenario is a simplified version of the DDoS scenario, where m=1.
When the network is under attack, the traffic rate crossing the pipe is T:
T = X1 + X2 + ... + Xn + m * rA
The firewall drops packets of a flow with a probability which is dependent on the flow's rate. This probability is modeled by a sigmoid function. As a result, the firewall drops both malicious as well as legitimate packets. The defender controls the value of parameter M, which represents the flow rate which will be dropped with probability 0.5.

The attacker's aim is to increase va and vn while maintaining a low incurred cost vc.
  • va: ratio of bandwidth consumed by the attacker to bandwidth consumed by legitimate traffic
  • vn: lost users to total number of users ratio
  • vc: attacker's cost, proportional to the number of nodes used for the attack
After applying weights to each of those factors, the total payoff for the attacker is:
Va = wba * vb + wna * vn - wca * vc
The payoff for the defender is:
Vb = - wbb * vb - wnb * vn + wcb * vc
As an example, the authors perform an analysis of the zero-sum version of this game, whereby the attacker's and defender's weights are the same:
Va = -Vd
wba = wbb = wb, wna = wnb = wn, wca = wcb = wc
The authors conclude analytically that the static game has a Nash equilibrium. Further investigation via simulations focuses on vb, the first component of player payoff. Results demonstrate that, in order to bypass the firewall, the attacker can increase m while reducing rA. They also demonstrate that there exists an optimal strategy for both players.

The dynamic game is a sequence of time steps, with both the attacker and defender having a payoff at each step. Each player gets an opportunity to change strategy at each time step. The total payoff for each player is the sum of those individual payoffs. Other than pointing out its differences with the static game, this paper does not investigate the dynamic game any further.

No comments:

Post a Comment