Detecting Network Intrusions via Sampling: A Game Theoretic 
Approach

Murali Kodialam 
T.V.Lakshman

Bell Laboratories
IEEE INFOCOMM 2003

Synopsis:
  This paper deals with the problem of detecting an intruding 
packet in a communication network. The basic approach is to 
sample a portion of the packets transiting selected network 
links. Whats interesting about this paper is that it applies a 
game theoretic approach for detecting network intrusions. The 
basic premise is that the service provider and the intruder are 
two players in a zero sum game.
  In Game theory,2 Player Strategic Game is defined as a game in 
which :
a.Each player has a strategy
b.Each player has a payoff or utility
c.Both players have complete information
  A Zero Sum Game is a game in which total utility of all players 
is zero
  The authors setup game between the service provider and the 
intruder as follows: The service provider chooses a set of 
detection probabilities at the links. The intruder has a 
probability distribution over the set of paths between the attack 
node and the target node and he chooses the path from this set 
according to the probability distribution. The intruder tries to 
minimize the maximum probability of the packet being sampled. The 
service provider tries to maximise the minimum probability 
distribution that the intruder may choose. 
  A minimax solution for this zero-sum game exists in the Game 
Theoretic framework and the authors apply it to develop an 
optimal sampling strategy for the service provider.
  The paper also describes several variants of the basic approach 
such as:
i.Allowing service provider to route network flows in order to 
maximize the value of the game, this discussion explains two 
algorithms Flow Flushing Algorithm and the Cut Saturation 
Algorithm
ii.Allowing intruder to introduce malicious packet at one of a 
set of nodes N.
iii.Objective of intruder is to reach any one of a set of nodes N 
instead of a single target node.
iv.Allowing intruder to introduce packet at one of a set of 
nodes, but he can no longer choose a specific path ; here they 
discuss the case of routing along shortest paths.
   The papers describes experimental results to analyse and 
validate the approach. It also analyses the effect of capacity on 
the value of the game and shows that the service provider can 
improve the probability of detection by exploiting the spare 
capacity to reroute flows.
   Thus, the paper describes how sampling can be used to detect 
intrusions in a network. Also since sampling can be an expensive 
operation in realtime, the authors apply game theoretic approach 
to provide heuristics for efficient intrusion detection within 
limited sampling budgets.

Pros:
1. Bright new idea!! Application of game theory for a real 
security problem.
2. Well-written, the sequence of explanations brought forth the 
idea well, first the minmax solution and then heuristics to 
improve chances of detection.
3. Performance results validate the potential of their approach.
4. Variants consider various possible attacks and present 
different strategies specific to the attack.

Cons:
1.Their approach works on the assumption that finding a single 
malicious packet will detect an intrusion. But intrusions are 
rarely single packets, an attack often spans several packets.
2. Their model is susceptible to a denial-of-service attack.
3. The paper does not make it clear what can be defined as a 
'malicious packet'.
4. The paper makes strong assumptions over the service providers 
control over the network.
5. A proof of concept, ie some performance analysis in real 
environment would have helped appreciate the practicality of 
their approach more.
6. Comparison with similar approaches? Given that theirs is a 
fairly new idea, this isnt a big con but they should have 
discussed other probabilistic intrusion detection approaches.

Discussion Questions

1. How can sampling be done efficiently in realtime? This is an 
open problem from this paper and a solution would complement 
their approach.

2. Can you think of more heuristics to improve the chances of 
detecting the malicious packet?

3. Can the intruder still succeed? Basically how can their 
approach be broken?

4. Are probabilistic approaches good in real systems or are they 
good only from theoretic point of view? How practical can such an 
approach be?

5. Security is always a game between a service provider and an 
attacker. Most security systems consist of the blue team and the 
red team. In that sense it seems natural that the idea of a zero 
sum game can be extended to other security paradigms. Which other 
areas do u think this can be applied?

6. The paper shows how to detect intrusions. Can the similar 
approach help in preventing intrusions? 

7. After you detect an intrusion, what next? How to fix the 
damage it caused? What other complementary approaches can be used 
be with this one to form a comprehensive Network Intrusion 
Detection System?

Vote.
Strong Accept: 0
Accept: 8
Reject: 0 
Strong Reject: 0