Report on
Detecting Network Intrusions via Sampling: A Game Theoretic Approach
In this paper Kodialam and Lakshman explore Intrusion Detection through
probabilistically sampling links. They relate the sampling problem to a two person zero sum game and give the minmax result from Game Theory. They show how the
solution can be computed for the intrusion detection game and use that information to gain some insight in rerouting traffic flows.
Two heuristics are given to show the effects of rerouting traffic within the network and how it increases the probability of detecting an attack (by reducing the amount of traffic across the minimum cut of a graph).
Some of the strong points of the paper include being the first to relate Game
Theory to Intrusion Detection and coming up with two heuristics to reroute flows in order to increase the probability of "winning the game". Also notable is the evaluation of the performance of these algorithms to show how they stack up against the minmax flow algorithm.
Despite these strengths our group discussion helped us arrive at a few areas that this paper fell short. First, some of the assumptions made in the paper may not be considered realistic in a commercial network. For example, limiting a virus to a single packet versus a sequence of packets, or events (failed login attempts or port scans). Also, other solutions have been demonstrated that eliminate the need for sampling all together. These solutions monitor the entire traffic stream flowing in and out of a network. Some skepticism was also expressed in
determining if a Game Theoretic approach is appropriate for Intrusion Detection. Describing it as a Game Theoretic problem may have been forced. In terms of presenting the material in the paper, some of the examples were also a little unclear and potentially contained errors. Overall, we feel that this paper will end up somewhere in the middle of the group.
Todd Sproull