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. A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search. Comm. of the ACM, 18(6), June 1975.]]
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. R. S. Boyer and J. S. Moore. A fast string searching algorithm. Comm. of the ACM, 20(10), Oct. 1977.]]
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. J. R. Crandall, Z. Su, S. F. Wu, and F. T. Chong. On deriving unknown vulnerabilities from zero-day polymorphic and metamorphic worm exploits. In ACM Conference on Computer and Communications Security, Alexandria, VA, Nov. 2005.]]
8. H. Dreger, A. Feldmann, V. Paxson, and R. Sommer. Operational experiences with high-volume network intrusion detection. In ACM Conference on Computer and Communications Security, Washington, DC, 2004.]]
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, and T. Berners-Lee. RFC 2616 - Hypertext Transfer Protocol. The Internet Engineering Task Force, June 1999.]]
11. M. Fisk and G. Varghese. Applying fast string matching to intrusion detection. Technical Report CS2001-0670, University of California San Diego, May 2001. Updated version available at http://woozle.org/mfisk/.]]
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. J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2 edition, 2001.]]
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. C. Kruegel, F. Valeur, G. Vigna, and R. A. Kemmerer. Stateful intrusion detection for high-speed networks. In IEEE Symposium on Security and Privacy, Oakland, CA, May 2002.]]
17. C. Krügel, T. Toth, and E. Kirda. Service specific anomaly detection for network intrusion detection. In ACM Symposium on Applied Computing, Madrid, Spain, March 2002.]]
18. R.-T. Liu, N.-F. Huang, C.-N. Kao, and C.-H. Chen. A fast pattern matching algorithm for network processor-based intrusion detection system. In IEEE International Conference on Performance, Computing, and Communications, Phoenix, AZ, Apr. 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. D. Mutz, G. Vigna, and R. A. Kemmerer. An experience developing an IDS stimulator for the black-box testing of network intrusion detection systems. In Annual Computer Security Applications Conference, Las Vegas, NV, Dec. 2003.]]
24. J. Newsome, B. Karp, and D. Song. Polygraph: Automatic signature generation for polymorphic worms. In IEEE Symposium on Security and Privacy, Oakland, CA, May 2005.]]
25. V. Paxson. Bro: a system for detecting network intruders in real-time. Computer Networks, 31(23/24), Dec. 1999.]]
26. N. Peter. Revised report on the algorithmic language ALGOL 60. Comm. of the ACM, 3(5), 1960.]]
27. J. Postel and J. Reynolds. RFC 959 - File Transfer Protocol. The Internet Engineering Task Force, 1985.]]
28. J. B. Postel. RFC 821 - Simple Mail Transfer Protocol. The Internet Engineering Task Force, 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. S. Rubin, S. Jha, and B. P. Miller. Language-based generation and evaluation of NIDS signatures. In IEEE Symposium on Security and Privacy, Oakland, CA, May 2005.]]
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. R. Sommer and V. Paxson. Enhancing byte-level network intrusion detection signatures with context. In ACM Conference on Computer and Communications Security, Washington, DC, Oct. 2003.]]
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. R. Teitelbaum. Minimal Distance Analysis of Syntax Errors in Computer Programs. PhD thesis, Computer Science Department, Carnegie-Mellon University, Sep. 1975.]]
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. G. Vigna, W. Robertson, and D. Balzarotti. Testing network-based intrusion detection signatures using mutant exploits. In ACM Conference on Computer and Communications Security, Washington, DC, Oct. 2004.]]
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

• Security and privacy

  • Cryptography

    • Cryptanalysis and other attacks

  • Intrusion/anomaly detection and malware mitigation

• Social and professional topics

  • Computing / technology policy

    • Computer crime