Detecting Network Intrusion via Sampling: A Game Theoretic Approach

In this paper, we consider the problem of detecting an intruding packet in a communication network. detection is accomplished by sampling a portion of the packet transiting selected network links ( or router interfaces). Since sampling entails incurring network costs for real-time packet sampling and packet examination hardware. We would like to dvelop a network packet sampling strategy to effectively detect network intrusions while not exceeding a given total sampling budget. We consider this problem in a game theoretic framework, where the in truder picks paths (oe the network ingress point if only shortest path routing is possible ) to minimize chances of detection and where the network operator chooses a sampling to maximize the chances of detection. We formulate the game theoretic problem, and develop sampling schemes that are optimal in this game theoretic setting.