On the difficulty of scalably detecting network attacks

ABSTRACT

Most network intrusion tools (e.g., Bro) use per-flow state to reassemble TCP connections and fragments in order to detect network attacks (e.g., SYN Flooding or Connection Hijacking) and preliminary reconnaissance (e.g., Port Scans). On the other hand, if network intrusion detection is to be implemented at high speeds at network vantage points, some form of aggregation is necessary. While many security analysts believe that such per-flow state is required for many of these problems, there is no clear proof that this is the case. In fact, a number of problems (such as detecting large traffic footprints or counting identifiers) have scalable solutions. In this paper, we initiate the study of identifying when and how a security attack detection problem can have a scalable solution. We use tools from Communication Complexity to prove that the common formulations of many well-known intrusion detection problems (detecting SYN Flooding, Port Scans, Connection Hijacking, and content matching across fragments) require per-flow state. Our theory exposes assumptions that need to be changed to provide scalable solutions to these problems; we conclude with some systems techniques to circumvent these lower bounds.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: CERT. http://www.cert.org/
• 3: CERT. "CERT Advisory CA-1996-21 TCP SYN Flooding and IP Spoofing Attacks." 1996.
• 4: CERT. "CERT Advisory CA-1997-28 IP Denial-of-Service Attacks." 1997.
• 5: Check Point Software Technologies, Ltd. http://www.checkpoint.com/
• 6: Cisco Systems. http://www.cisco.com/
• 7: F. Cohen. "A Mathematical Structure of Simple Defense Network Deceptions." Computers & Security 19 (2000), pp. 520--528.
• 8: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 9: 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]
• 10: ForeScout Technologies. http://www.forescout.com/
• 11: Fortinet, Inc.. http://www.fortinet.com/
• 12: Fyodor. "Remote OS detection via TCP/IP Stack FingerPrinting." http://www.insecure.org/nmap/nmap-fingerprinting-article.html
• 13: M. Handley, V. Paxson. "Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics." 10th USENIX Security Symposium, pp. 115--131.
• 14: 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]
• 15: Juniper Networks. http://www.juniper.net/
• 16: Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
• 17: Ramana Rao Kompella , Sumeet Singh , George Varghese, On scalable attack detection in the network, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028812]
• 18: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 19: Mazu Networks. http://www.mazunetworks.com/
• 20: D. Moore, G. Voelker, and S. Savage. "Inferring Internet Denial-of-Service Activity." 10th USENIX Security Symposium, pp. 9--22.
• 21: Norton Internet Security 2004. http://www.symantec.com/sabu/nis/nis_pe/
• 22: Network Associates, Inc. http://www.nai.com/
• 23: NetScreen Technologies, Inc. http://www.netscreen.com/
• 24: V. Paxson. "Bro: A System for Detecting Network Intruders in Real-Time." 7th USENIX Security Symposium, pp. 31--52.
• 25: J. Postel. "Transmission Control Protocol." RFC 793.
• 26: J. Postel. "Internet Control Message Protocol." RFC 792.
• 27: Silicon Defense. http://www.silicondefense.com/
• 28: Snort. http://www.snort.org/
• 29: TINY Software. http://www.tinysoftware.com/home/pg=tpf5_home
• 30: TippingPoint Technologies. http://www.tippingpoint.com/
• 31: H. Wang, D. Zhang, and K. Shin. "Detecting SYN Flooding Attacks." IEEE INFOCOM, 2002.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Security, Theory

Keywords:
communication complexity, network intrusion detection