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, all the IDS systems we know of keep per-connection or per-flow state. Thus it is hardly surprising that IDS systems (other than signature detection mechanisms) have not scaled to multi-gigabit speeds. By contrast, note that both router lookups and fair queuing have scaled to high speeds using <i>aggregation</i> 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 cause two problems. First, aggregation can cause <i>behavioral</i> 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 attacks and show that several categories (bandwidth based, claim-and-hold, host scanning) can be scalably detected. By contrast, it appears that stealthy port-scanning cannot be scalably detected without keeping per-flow state.

REFERENCES

• 1: Cert. advisory ca-1998-01 smurf ip denial-of-service attacks. http://www.cert.org/advisories/CA-1998-01.html.
• 2: Cert. advisory ca-2001-19 "code red" worm exploiting buffer overflow in iis indexing service dll. http://www.cert.org/advisories/CA-2001-19.html.
• 3: Cert advisory ca-2001-26 nimda worm. http://www.cert.org/advisories/CA-2001-26.html.
• 4: Mazu networks. http://www.mazu.com.
• 5: Mydoom.b virus. http://www.us-cert.gov/cas/alerts/SA04-028A.html.
• 6: Sco inc. http://www.sco.com.
• 7: Arbor Networks. http://www.arbornetworks.com.
• 8: 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]
• 9: Bernstein, D. J. SYN cookies. http://cr.yp.to/syncookies.html, 1997.
• 10: 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]
• 11: Check Point Software Technologies Ltd. Syndefender. http://www.checkpoint.com/products/firewall-1.
• 12: Datar, M., and Muthukrishnan, S. Estimating rarity and similarity over data stream windows. Technical report, 2001--21,, DIMACS, Nov. 2001.
• 13: 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
• 14: Cristian Estan , George Varghese , Mike Fisk, Bitmap algorithms for counting active flows on high speed links, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948225]
• 15: Forescout Technologies. http://www.forescout.com.
• 16: Fyodor. http://www.insecure.org/nmap.
• 17: Gilbert, A., Guha, S., Indyk, P., Muthukrishnan, S., and Strauss, M. Quicksand: Quick summary and analysis of network data. Technical report, 2001-43, DIMACS, Nov. 2001.
• 18: Gill, T. M., and Poletto, M. MULTOPS: a data-structure for bandwidth attack detection. In USENIX Security Symposium (2001).
• 19: Greene, B. R., and McPherson, D. Sink holes: A swiss army knife isp security tool. http://www.nanog.org/mtg-0306/pdf/sink.pdf.
• 20: Heberlein, L. T., Dias, G. V., Levitt, K. N., Mukherjee, B., J.Wood, and D.Wolber. A network security monitor. In Proc. IEEE Symposium on Research in Security and Privacy (1990), pp. 296--304.
• 21: 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]
• 22: 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]
• 23: Jung, J., Paxson, V., Berger, A., and Balakrishnan, H. Fast portscan detection using sequential hypothesis testing. In Proceedings of IEEE Symposium on Security and Privacy (2004).
• 24: Keyes, R. The Naptha DoS Vulnerabilities. http://razor.bindview.com/publish/advisories/adv_NAPTHA.html.
• 25: 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]
• 26: John E Freund , Ronald E Walpole, Mathematical statistics (4th ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 27: Leckie, C., and Kotagiri, R. A probabilistic approach to detecting network scans. In Proceedings of the Eight IEEE Network Operations and Management Symposium (Apr. 2002).
• 28: Jonathan Lemon, Resisting SYN Flood DoS Attacks with a SYN Cache, Proceedings of the BSDCon 2002, p.89-97, February 11-14, 2002
• 29: 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]
• 30: Martin Roesch. Snort. http://www.snort.org.
• 31: Moore, D., and Shannon, C. Sco offline from dos attack. http://www.sco.com.
• 32: Moore, D., Voelker, G., and Savage, S. Inferring internet denial of service activity. In USENIX Security Symposium (2001).
• 33: NetFlow, C. http://www.cisco.com/warp/public/732/Tech/netflow.
• 34: Netscreen 100 Firewall Appliance. http://www.netscreen.com.
• 35: Netscreen Technologies. http://www.netscreen.com.
• 36: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 37: 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 ]
• 38: 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]
• 39: Pescatore, J., Easley, M., and Stiennon, R. Network security platforms will transform security markets. http://www.techrepublic.com/article.jhtml?id=r00220021223jdt01.htm&src=bc, Dec. 2002.
• 40: Robertson, S., Siegel, E., Miller, M., and Stolfo, S. Surveillance detection in high bandwidth environments. In Proceedings of the 2003 DARPA DISCEX III Conference (Apr. 2003), pp. 229--238.
• 41: 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
• 42: Staniford, S., Hoagland, J. A., and McAlerney, J. M. Practical automated detection of stealthy portscans. In In Proceedings of the 7th ACM Conference on Computer and Communications Security (2000).
• 43: 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
• 44: Staniford, S. J. Containment of scanning worms in enterprise networks. In Journal of Computer Security (Nov. 2003).
• 45: Wang, H., Zhang, D., and Shin, K. Detecting syn flooding attacks. In IEEE INFOCOM (2002).
• 46: 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
• 47: 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]
• 48: 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
• 49: Yaar, A., Perrig, A., and Song, D. Si: A stateless internet flow lter to mitigate ddos ooding attacks. In Proceedings of the IEEE Symposium on Security and Privacy (2004).
• 50: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Design, Measurement, Performance, Security

Keywords:
denial of service, scalability, security