On scalable attack detection in the network

ABSTRACT

Current intrusion detection and prevention systems seek 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-connection or per-flow state to detect malicious TCP flows. Thus, it is hardly surprising that these IDS systems have not scaled to multigigabit speeds. By contrast, both router lookups and fair queuing have scaled to high speeds using aggregation via prefix lookups or DiffServ. Thus, in this paper, we initiate research into the question as to whether one can detect attacks without keeping per-flow state. We will show that such aggregation, while making fast implementations possible, 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 and show that several categories (bandwidth based, claim-and-hold, port-scanning) can be scalably detected. In addition to existing approaches for scalable attack detection, we propose a novel data structure called partial completion filters (PCFs) that can detect claim-and-hold attacks scalably in the network. We analyze PCFs both analytically and using experiments on real network traces to demonstrate how we can tune PCFs to achieve extremely low false positive and false negative probabilities.

REFERENCES

• 1: [1] M. Roesch, Snort. [Online]. Available: http://www.snort.org
• 2: Paul Barford , Jeffery Kline , David Plonka , Amos Ron, A signal analysis of network traffic anomalies, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637210]
• 3: Balachander Krishnamurthy , Subhabrata Sen , Yin Zhang , Yan Chen, Sketch-based change detection: methods, evaluation, and applications, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948236]
• 4: [4] S. J. Staniford, "Containment of scanning worms in enterprise networks," J. Computer Security, 2004, to be published.
• 5: [5] ForeScout Technologies. [Online]. Available: http://www. forescout.com
• 6: [6] D. Moore, G. Voelker, and S. Savage, "Inferring Internet denial of service activity," in Proc. 10th USENIX Security Symp., Aug. 2001, pp. 9-22.
• 7: [7] Mazu Publishing. [Online]. Available: http://www.mazu.com
• 8: [8] Arbor Networks. [Online]. Available: http://www.arbornetworks.com
• 9: [9] H. Wang, D. Zhang, and K. Shin, "Detecting SYN flooding attacks," in Proc. IEEE INFOCOM, 2002, pp. 1530-1539.
• 10: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 11: Kirill Levchenko , Ramamohan Paturi , George Varghese, On the difficulty of scalably detecting network attacks, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030087]
• 12: [12] R. Keyes, "The Naptha DoS vulnerabilities," [Online]. Available: http://www.cert.org/advisories/CA-2000-21.html
• 13: Nicholas Weaver , Vern Paxson , Stuart Staniford , Robert Cunningham, A taxonomy of computer worms, Proceedings of the 2003 ACM workshop on Rapid malcode, October 27-27, 2003, Washington, DC, USA [doi>10.1145/948187.948190]
• 14: Stuart Staniford , Vern Paxson , Nicholas Weaver, How to Own the Internet in Your Spare Time, Proceedings of the 11th USENIX Security Symposium, p.149-167, August 05-09, 2002
• 15: [15] MyDoom. B Virus. [Online]. Available: http://www.us-cert.gov/cas/ techalerts/TA04-028A.html
• 16: [16] CERT Advisory CA-2001-19, "Code Red" Worm Exploiting Buffer Overflow In IIS Indexing Service DLL, [Online]. Available: http://www.cert.org/advisories/CA-2001-19.html
• 17: [17] CERT Advisory CA-2001-26 Nimda Worm, [Online]. Available: http:// www.cert.org/advisories/CA-2001-26.html
• 18: [18] CERT Advisory CA-1998-01 Smurf IP Denial-of-Service Attacks, [Online]. Available: http://www.cert.org/advisories/CA-1998-01.html
• 19: Vern Paxson, An analysis of using reflectors for distributed denial-of-service attacks, ACM SIGCOMM Computer Communication Review, v.31 n.3, July 2001 [doi>10.1145/505659.505664]
• 20: [20] T. M. Gill and M. Poletto, "MULTOPS: A data-structure for bandwidth attack detection," in Proc. 10th USENIX Security Symp., 2001, pp. 23-38.
• 21: [21] M. Datar and S. Muthuktishnan, "Estimating rarity and similarity over data stream windows," DIMACS, Tech. Rep. 2001-21, 2001.
• 22: [22] A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. J. Strauss, "Quicksand: Quick summary and analysis of network data," DIMACS, Tech. Rep. 2001-43, 2001.
• 23: 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
• 24: [24] C. Estan and G. Varghese, "Autofocus: A tool for automatic traffic analysis," in Proc. ACM SIGCOMM, 2003, pp. 137-148.
• 25: [25] Cisco NetFlow. [Online]. Available: http://www.cisco.com/en/US/ products/ps6601/products_ios_protocol_group_home.html
• 26: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 27: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]
• 28: [28] R. J. Larsen and M. L. Marx, An Introduction to Mathematical Statistics and Its Applications. Upper Saddle River, NJ: Prentice-Hall, 2001.
• 29: [29] NMap. [Online]. Available: http://www.insecure.org/nmap
• 30: [30] Cooperative Association for Internet Data Analysis (CAIDA). [On-line]. Available: http://www.caida.org
• 31: Alefiya Hussain , John Heidemann , Christos Papadopoulos, A framework for classifying denial of service attacks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863968]
• 32: [32] L. T. Heberlein, G. V. Dias, K. N. Levitt, B. Mukherjee, J. Wood, and D. Wolber, "A network security monitor," in Proc. IEEE Symp. Research in Security and Privacy, 1990, pp. 296-304.
• 33: [33] S. Robertson, E. V. Siegel, M. Miller, and S. J. Stolfo, "Surveillance detection in high bandwidth environments," in Proc. 2003 DARPA DISCEX III Conf., pp. 229-238.
• 34: [34] J. Jung, V. Paxson, A. Berger, and H. Balakrishnan, "Fast portscan detection using sequential hypothesis testing," in Proc. IEEE Symp. Security and Privacy, 2004, pp. 211-225.
• 35: [35] E. Shenk, "Another new thought on dealing with SYN flooding," 1996 [Online]. Available: http://www.wcug.wwu.edu/lists/netdev/199609/ msg00171.html
• 36: [36] Riverhead Networks. [Online]. Available: http://www.riverhead.com
• 37: [37] L. Carter and M. N. Wegman, "Universal classes of hash functions," J. Comput. Syst. Sci., vol. 18, no. 2, pp. 143-154, 1979.
• 38: [38] A. Yaar, A. Perrig, and D. Song, "SIFF: a stateless Internet flow filter to mitigate DDoS flooding attacks," in Proc. IEEE Symp. Security and Privacy, 2004, pp. 130-143.
• 39: Abraham Yaar , Adrian Perrig , Dawn Song, Pi: A Path Identification Mechanism to Defend against DDoS Attacks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.93, May 11-14, 2003
• 40: Haining Wang , Danlu Zhang , Kang G. Shin, SYN-dog: Sniffing SYN Flooding Sources, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.421, July 02-05, 2002
• 41: [41] D. J. Bernstein, "SYN Cookies," 1997 [Online]. Available: http://cr.yp.to/syncookies.html
• 42: Jonathan Lemon, Resisting SYN Flood DoS Attacks with a SYN Cache, Proceedings of the BSDCon 2002, p.89-97, February 11-14, 2002
• 43: Christoph L. Schuba , Ivan V. Krsul , Markus G. Kuhn , Eugene H. spafford , Aurobindo Sundaram , Diego Zamboni, Analysis of a Denial of Service Attack on TCP, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.208, May 04-07, 1997
• 44: [44] Netscreen Technologies. [Online]. Available: http://www. netscreen.com
• 45: Cheng Jin , Haining Wang , Kang G. Shin, Hop-count filtering: an effective defense against spoofed DDoS traffic, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948116]
• 46: [46] C. Leckie and R. Kotagiri, "A probabilistic approach to detecting network scans," in Proc. 8th IEEE Network Operations and Management Symp., 2002, pp. 359-372.
• 47: [47] S. Staniford, J. A. Hoagland, and J. M. McAlerney, "Practical automated detection of stealthy portscans," in Proc. 7th ACM Conf. Computer and Communications Security, 2000, pp. 1-7.
• 48: [48] J. Pescatore, M. Easley, and R. Stiennon, "Network security platforms will transform security markets," 2002 [Online]. Available: http://www.techrepublic.com/article.jhtml?id=r00220021223jdt01. htm&src=bc

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Security

Keywords:
data structures, denial of service, network attacks, routers, scanning, streaming algorithms, syn flooding