Michela Becchi
ABSTRACT
Deterministic finite automata (DFAs) are widely used to perform regular expression matching in linear time. Several techniques have been proposed to compress DFAs in order to reduce memory requirements. Unfortunately, many real-world IDS regular expressions include complex terms that result in an exponential increase in number of DFA states. Since all recent proposals use an initial DFA as a starting-point, they cannot be used as comprehensive regular expression representations in an IDS.
In this work we propose a hybrid automaton which addresses this issue by combining the benefits of deterministic and non-deterministic finite automata. We test our proposal on Snort rule-sets and we validate it on real traffic traces. Finally, we address and analyze the worst case behavior of our scheme and compare it to traditional ones.
- A. V. Aho and M. J. Corasick, "Efficient String Matching: An Aid to Bibliographic Search," Communications of the ACM, pp. 333--340, 1975. Google Scholar
Digital Library
- B. Commentz-Walter, "A string matching algorithm fast on the average," in ICALP, July 1979. Google ScholarDigital Library
- S. Wu, U. Manber, "A fast algorithm for multi-pattern searching," Tech. Report TR-94-17, Univ of Arizona, 1994.Google Scholar
- J. E. Hopcroft and J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation," Addison Wesley, 1979. Google ScholarDigital Library
- J. Hopcroft, "An nlogn algorithm for minimizing states in a finite automaton," in Theory of Machines and Computation, J. Kohavi, Ed. New York: Academic, 1971, pp. 189--196.Google Scholar
- M. Roesch, "Snort: Lightweight Intrusion Detection for Networks," in System Administration Conf., 1999 Google ScholarDigital Library
- Snort: http://www.Snort.org/Google Scholar
- Cisco Systems. Cisco ASA 5505 Adaptive Security Appliance. http://www.cisco.com.2007.Google Scholar
- Citrix Systems. Citrix Application Firewall. http://www.citrix.com. 2007.Google Scholar
- Bro: http://bro-ids.org/Google Scholar
- Vern Paxson et al., "Flex: A fast scanner generator," http://www.gnu.org/software/flex/Google Scholar
- R. Sommer and V. Paxson, "Enhancing byte-level network intrusion detection signatures with context.", in CCS 2003. Google ScholarDigital Library
- N. Tuck, T. Sherwood, B. Calder, and G. Varghese, "Deterministic memory-efficient string matching algorithms for intrusion detection," in Infocom 2004.Google Scholar
- L. Tan, and T. Sherwood, "A High Throughput String Matching Architecture for Intrusion Detection and Prevention," ISCA 2005. Google ScholarDigital Library
- F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz, "Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection", in ANCS 2006 Google ScholarDigital Library
- S. Kumar et alt., "Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection," in ACM SIGCOMM, Sept 2006. Google ScholarDigital Library
- S. Kumar, et alt, "Advanced Algorithms for Fast and Scalable Deep Packet Inspection", in ANCS 2006 Google ScholarDigital Library
- M. Becchi and S. Cadambi, "Memory-Efficient Regular Expression Search Using State Merging", in INFOCOM 2007Google Scholar
- M. Becchi and P. Crowley, "An Improved Algorithm to Accelerate Regular Expression Evaluation", in ANCS 2007 Google ScholarDigital Library
- M. Becchi and P. Crowley, "Addressing complex regular expressions through counting automata", Washington University Tech. Report, July 2007.Google Scholar
- R. W. Floyd, and J. D. Ullman, "The Compilation of Regular Expressions into Integrated Circuits", Journal of ACM, vol. 29, no. 3, pp 603--622, July 1982. Google ScholarDigital Library
- R. Sidhu and V. K. Prasanna, "Fast Regular Expression Matching using FPGAs", in FCCM 2001 Google ScholarDigital Library
- C. R. Clark and D. E. Schimmel, "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," in FLP 2003.Google Scholar
- J. Moscola et alt., "Implementation of a content-scanning module for an internet firewall," in FCCM, USA, April 2003. Google ScholarDigital Library
- Internet traffic traces: http://cctf.shmoo.com/Google Scholar
- Cu-11 standard cell/gate array ASIC, IBM. www.ibm.comGoogle Scholar
Index Terms
- A hybrid finite automaton for practical deep packet inspection
Recommendations
Algorithms to accelerate multiple regular expressions matching for deep packet inspection
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsThere is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement ...
Advanced algorithms for fast and scalable deep packet inspection
ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systemsModern deep packet inspection systems use regular expressions to define various patterns of interest in network data streams. Deterministic Finite Automata (DFA) are commonly used to parse regular expressions. DFAs are fast, but can require ...
DFA-based and SIMD NFA-based regular expression matching on cell BE for fast network traffic filtering
SIN '09: Proceedings of the 2nd international conference on Security of information and networksRegular expression matching is the heart of many data processing routines, such as string search, network traffic filtering, etc. The traditional way of regexp matching is building and execution of a deterministic finite automaton (DFA), that provides O(...
Comments