On Scalable Attack Detection in the Network
Ramana Rao Kompella, Student Member, IEEE, Sumeet Singh, and George Varghese, Member, IEEE
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 1

Abstract—
Current intrusion detection and prevention systemsseek to detect a wide class of network intrusions (e.g., DoS attacks,worms, port scans) at network vantage points. Unfortunately,
even today, many IDS systems we know of keep per-connectionor per-flow state to detect malicious TCP flows. Thus, it is hardlysurprising that these IDS systems have not scaled to multi-gigabit
speeds. By contrast, both router lookups and fair queuing havescaled to high speeds using aggregation via prefix lookups orDiffServ. Thus, in this paper, we initiate research into the question
as to whether one can detect attacks without keeping per-flowstate. We will show that such aggregation, while making fast implementationspossible, immediately causes two problems. First,
aggregation can cause behavioral aliasing where, for example,good behaviors can aggregate to look like bad behaviors. Second,aggregated schemes are susceptible to spoofing by which the
intruder sends attacks that have appropriate aggregate behavior.We examine a wide variety of DoS and scanning attacks andshow that several categories (bandwidth based, claim-and-hold,
port-scanning) can be scalably detected. In addition to existingapproaches for scalable attack detection, we propose a novel datastructure called partial completion filters (PCFs) that can detect
claim-and-hold attacks scalably in the network. We analyze PCFsboth analytically and using experiments on real network traces todemonstrate how we can tune PCFs to achieve extremely low falsepositive and false negative probabilities.