Sampling network traffic for anomaly detection

Packet sampling is commonly deployed in high-speed backbone routers to minimize resources used for network monitoring. Traditionally, sampled traffic data is used for network management tasks such as heavy hitters detections, and traffic matrix estimations, but recently it has also been used in numerous anomaly detection algorithms, as security analysis becomes increasingly critical for network providers. While the impact of sampling on traffic engineering metrics such as flow size and mean rate is well studied, its impact on anomaly detection remains an open question.;This dissertation presents a first comprehensive study on whether existing sampling techniques distort traffic features critical for effective anomaly detection. We sampled packet traces captured from a Tier-1 IP-backbone using four popular methods: random packet sampling, random flow sampling, smart sampling, and sample-and-hold. The sampled data is then used as input to detect two common classes of anomalies: volume anomalies and port scans. Since it is not feasible to enumerate an existing solutions, we study three representative algorithms: a wavelet-based volume anomaly detection and two portscan detection algorithms based on hypotheses testing. Our results show that all the four sampling methods introduce fundamental bias that degrades the performance of the three detection schemes, however the degradation curves are very different.;Therefore we present a new sampling design: Fast Filtered Sampling (FFS), which is comprised of an independent low-complexity filter, concatenated with any sampling scheme at choice. FFS ensures the integrity of small flows for anomaly detection, while still providing acceptable identification of heavy hitters. This is achieved through a filter design which suppresses packets from flows as a function of their size, 'boosting' small flows relative to medium and large flows. Through extensive evaluation on traffic traces, we show the efficacy of FFS for applications such as portscan detection and traffic estimation. There are quite a few avenues to improve such as hash collision and memory consumption. Hence we also propose several new specialized filtered sampling schemes utilizing various Bloom filter designs for various purposes including traffic accounting, capturing unique flow set, and estimating flow size distribution.