Protomatching network traffic for high throughputnetwork intrusion detection

ABSTRACT

Before performing pattern matching, a typical misuse-NIDS performs protocol analysis: it parses network traffic according to the attack protocol and normalizes the traffic into the form used by its signatures. For example, consider a NIDS that attempts to identify an HTTP-based attack. The NIDS must extract the URL from the raw traffic, convert HEX encoded characters into their equivalent ASCII form if necessary, and only then perform matching on the normalized URL. Protocol analysis is time consuming, especially in a NIDS that analyzes and normalizes all traffic just to discover that the majority of the traffic does not match any of its signatures.We develop a technique called protomatching that combines protocol analysis, normalization, and pattern matching into a single phase. The goal of the protomatching signatures is to exclude non-attack traffic quickly before the NIDS performs any further time-consuming analysis. Protomatching is based on a novel signature with two properties. First, the signature ensures that the attack pattern appears in the context that enables successful attack. This saves the need for protocol analysis. Second, the signature matches both encoded and normalized forms of an attack and this saves the need for normalization.We empirically show that a Snort implementation that uses protomatching is up to 49% faster than an unmodified Snort.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: S. Antonatos, M. Polychronakis, P. Akritidis, K. G. Anagnostakis, and E. P. Markatos. Piranha: Fast and memory-efficient pattern matching for intrusion detection. In IFIP International Information Security Conference, Chiba, Japan, May 2005.
• 3: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 4: CheckPoint Software Technologies. InterSpec Internal Security. Available at www.checkpoint.com.
• 5: Cisco Systems. Cisco IPS 4200 Series Sensors. Available at www.cisco.com.
• 6: C. J. Coit, S. Staniford, and J. McAlemey. Towards faster string matching for intrusion detection or exceeding the speed of snort. In DARPA Information Survivability Conference and Exposition (DISCEX II'01), Anaheim, CA, June 2001.
• 7: Jedidiah R. Crandall , Zhendong Su , S. Felix Wu , Frederic T. Chong, On deriving unknown vulnerabilities from zero-day polymorphic and metamorphic worm exploits, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102152]
• 8: Holger Dreger , Anja Feldmann , Vern Paxson , Robin Sommer, Operational experiences with high-volume network intrusion detection, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030086]
• 9: eEye Digital Security. %u coding IDS bypass vulnerability, 2001. Available at www.eeye.com/html/Research/Advisories/AD20010705.html.
• 10: R. Fielding , J. Gettys , J. Mogul , H. Frystyk , L. Masinter , P. Leach , T. Berners-Lee, Hypertext Transfer Protocol -- HTTP/1.1, RFC Editor, 1999
• 11: Mike Fisk , George Varghese, Fast Content-Based Packet Handling for Intrusion Detection, University of California at San Diego, La Jolla, CA, 2001
• 12: M. Handley and V. Paxson. Network intrusion detection: Evasion, traffic normalization, and end-to-end protocol semantics. In USENIX Security Symposium, Washington, DC, Aug. 2001.
• 13: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 14: Internet Security Systems. RealSecure Network 10/100. Available at www.iss.net.
• 15: J. C. Junqua and G. van Noord, editors. Robustness in Language and Speech Technology. Springer, 2001.
• 16: Christopher Kruegel , Fredrik Valeur , Giovanni Vigna , Richard Kemmerer, Stateful Intrusion Detection for High-Speed Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.285, May 12-15, 2002
• 17: Christopher Krügel , Thomas Toth , Engin Kirda, Service specific anomaly detection for network intrusion detection, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508835]
• 18: Rong-Tai Liu , Nen-Fu Huang , Chia-Nan Kao , Chih-Hao Chen , Chi-Chieh Chou, A Fast Pattern-Match Engine for Network Processor-based Network Intrusion Detection System, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04) Volume 2, p.97, April 05-07, 2004
• 19: E. Markatos, S. Antonatos, M. Polychronakis, and K. Anagnostakis. Exclusion-based signature matching for intrusion detection. In IASTED International Conference on Communications and Computer Networks, Cambridge, MA, Nov. 2002.
• 20: R. Marti. THOR: A tool to test intrusion detection systems by variations of attacks. Master's thesis, Swiss Federal Institute of Technology, Mar. 2002.
• 21: M. Mohri, F. C. N. Pereira, and M. D. Riley. AT&T Finite-State Machine Library. Available at www.research.att.com/sw/tools/fsm.
• 22: D. Mutz, C. Krügel, W. Robertson, G. Vigna, and R. R. Kemmerer. Reverse engineering of network signatures. In The AusCERT Asia Pacific Information Technology Security Conference, Gold Coast, Australia, May 2005.
• 23: Darren Mutz , Giovanni Vigna , Richard Kemmerer, An Experience Developing an IDS Stimulator for the Black-Box Testing of Network Intrusion Detection Systems, Proceedings of the 19th Annual Computer Security Applications Conference, p.374, December 08-12, 2003
• 24: James Newsome , Brad Karp , Dawn Song, Polygraph: Automatically Generating Signatures for Polymorphic Worms, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.226-241, May 08-11, 2005 [doi>10.1109/SP.2005.15]
• 25: 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]
• 26: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 27: J. Postel , J. K. Reynolds, File Transfer Protocol, RFC Editor, 1985
• 28: J. Postel, Simple Mail Transfer Protocol, RFC Editor, 1982
• 29: T. H. Ptacek and T. N. Newsham. Insertion, evasion, and denial of service: Eluding network intrusion detection. Technical Report T2R-0Y6, Secure Networks, Inc., Calgary, AB, Canada, 1998.
• 30: Robert Grahm. SideStep: IDS evasion tool, Jan. 2000.
• 31: D. J. Roelker. HTTP IDS evasions revisited, Jan. 2003. Available at www.idsresearch.org.
• 32: M. Roesch. Snort: the Open Source Network Intrusion Detection System. Available at www.snort.org.
• 33: S. Rubin. Formal Models and Tools to Improve NIDS Accuracy. PhD thesis, University of Wisconsin-Madison, 2006.
• 34: Shai Rubin , Somesh Jha , Barton P. Miller, Language-Based Generation and Evaluation of NIDS Signatures, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.3-17, May 08-11, 2005 [doi>10.1109/SP.2005.10]
• 35: L. Schaelicke, T. Slabach, B. Moore, and C. Freeland. Characterizing the performance of network intrusion detection sensors. In International Symposium on Recent Advances in Intrusion Detection, Pittsburgh, PA, Sep. 2003.
• 36: Robin Sommer , Vern Paxson, Enhancing byte-level network intrusion detection signatures with context, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948145]
• 37: R. Sommer and V. Paxson. Exploiting independent state for network intrusion detection. In Annual Computer Security Applications Conference, Tucson, AZ, Dec. 2006.
• 38: SourceFire Inc. SourceFire IS3000 Series. Available at www.sourcefire.com.
• 39: L. Tan and T. Sherwood. A high throughput string matching architecture for intrusion detection and prevention.
• 40: Ray Teitelbaum, Minimal distance analysis of syntax errors in computer programs., 1976
• 41: The National Institute of Standards and Technology (NIST).National vulnerability database. Available at nvd.nist.gov.
• 42: The NSS Group. Intrusion prevention systems (IPS) group test (Edition 3), Aug. 2005.
• 43: The Tcpdump Group. TCPDUMP/LIBPCAP. Available at www.tcpdump.org.
• 44: TippingPoint, a Division of 3Com. UnityOne, Intrusion Prevention Systems. Available at www.tippingpoint.com.
• 45: G. Tripp. A finite-state-machine based string matching system for intrusion detection on high-speed networks. In European Institute for Anti-Virus Research (EICAR) Annual Conference, Malta, May 2005.
• 46: Giovanni Vigna , William Robertson , Davide Balzarotti, Testing network-based intrusion detection signatures using mutant exploits, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030088]
• 47: S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Technical Report TR94-17, Department of Computer Science at the University of Arizona, May 1994.
• 48: V. Yegneswaran, J. Giffin, P. Barford, and S. Jha. An architecture for generating semantic-aware signatures. In USENIX Security Symposium, Washington, DC, Aug. 2005.
• 49: S. Yu. Grail+: A symbolic computation environment for finite-state machines, regular expressions, and finite languages. Available at www.csd.uwo.ca/research/grail/grail.html.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Unauthorized access (e.g., hacking, phreaking)

General Terms:
Management, Security

Keywords:
intrusion detection, protocol analysis, signatures