Bitmap algorithms for counting active flows on high speed links

ABSTRACT

This paper presents a family of bitmap 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. Counting is especially hard when processing must be done within a packet arrival time (8 nsec at OC-768 speeds) and, hence, must require only a small number of accesses to limited, fast memory. A naive solution that maintains a hash table requires several Mbytes because the number of flows can be above a million. By contrast, our new probabilistic 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 replaced the port scan detection component of the popular intrusion detection system Snort with one of our new algorithms. This reduced memory usage on a ten minute trace from 50 Mbytes to 5.6 Mbytes while maintaining a 99.77% probability of alarming on a scan within 6 seconds of when the large-memory algorithm would. The best known prior algorithm (probabilistic counting) takes 4 times more memory on port scan detection and 8 times more on a measurement application. 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.

REFERENCES

• 1: Cisco offers wire-speed intrusion detection, December 2000. http://www.nwfusion.com/reviews/2000/1218rev2.html.
• 2: Nick Duffield , Carsten Lund , Mikkel Thorup, Properties and prediction of flow statistics from sampled packet streams, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637225]
• 3: Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 4: C. Estan, G. Varghese, and M. Fisk. Bitmap algorithms for counting active flows on high speed links. Technical Report 0738, CSE Department, UCSD, March 2003.
• 5: Wenjia Fang and Larry Peterson. Inter-as traffic patterns and their implications. In Proceedings of IEEE GLOBECOM, December 1999.
• 6: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 7: Fyodor. Remote OS detection via TCP/IP stack fingerprinting. Phrack, (54), December 1998.
• 8: Dina Katabi , Mark Handley , Charlie Rohrs, Congestion control for high bandwidth-delay product networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: Ken Keys, David Moore, R. Koga, E. Lagache, M. Tesch, and K. Claffy. The architecture of coralreef: an internet traffic monitoring software suite. PAM2001, Workshop on Passive and Active Measurements, RIPE, 2001.
• 10: Ratul Mahajan , Steven M. Bellovin , Sally Floyd , John Ioannidis , Vern Paxson , Scott Shenker, Controlling high bandwidth aggregates in the network, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.62-73, July 2002 [doi>10.1145/571697.571724]
• 11: David Moore. Personal conversation. also see caida analysis of code-red, 2001. http://www.caida.org/ analysis/ security/ code-red/.
• 12: Cisco netflow. http://www.cisco.com /warp /public /732 /Tech /netflow.
• 13: Riverstone Networks. Lfap: Lightweight flow accounting protocol. http://www.riverstonenet.com/ technology/accounting_for_profitability.shtml.
• 14: Dave Plonka, FlowScan: A Network Traffic Flow Reporting and Visualization Tool, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 15: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 16: Stuart Staniford , James A. Hoagland , Joseph M. McAlerney, Practical automated detection of stealthy portscans, Journal of Computer Security, v.10 n.1-2, p.105-136, 2002
• 17: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 18: Kyu-Young Whang , Brad T. Vander-Zanden , Howard M. Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems (TODS), v.15 n.2, p.208-229, June 1990 [doi>10.1145/78922.78925]
• 19: Ming-Young You and Cheng-Shang Chang. Resampling for wireless access. In Proceedings of IEEE PIMRC, June 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Algorithms, Measurement

Keywords:
counting flows, network traffic measurement