Bitmap algorithms for counting active flows on high speed links

In this paper we present a family of algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high speed link. Such counting can be used to detect DoS attacks and port scans, and to solve measurement problems. The central difficulty is that count processing must be done within a packet arrival time (8 nsec at OC-768 speeds) and, hence, must require only a small number of memory references to limited, fast memory. A naive solution that maintains a hash table requires several Mbytes because the number of flows can be more than a million. By contrast, our new algorithms take very little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we used one of our new algorithms to replace the port scan detection component of the popular intrusion detection system Snort. Doing so reduced the memory usage on a ten minute trace from 50 Mbytes to 5.6 Mbytes while maintaining a 99.5% probability of alarming on a scan within 9 seconds of when the large-memory algorithm would alarm. By contrast, the best known prior algorithm (probabilistic counting) takes 4 times more memory on the port scan application and 8 times more memory on a measurement application. Our algorithms also lead to a reduction by a factor of seven in the total memory usage of a traffic analysis application from the CoralReef suite. Fundamentally, this is because our algorithms can be customized to take advantage of special features of applications such as a large number of instances that have very small counts or prior knowledge of the likely range of the count.Pre-2018 CSE ID: CS2003-073