Efficient regular expression evaluation: theory to practice

ABSTRACT

Several algorithms and techniques have been proposed recently to accelerate regular expression matching and enable deep packet inspection at line rate. This work aims to provide a comprehensive practical evaluation of existing techniques, extending them and analyzing their compatibility. The study focuses on two hardware architectures: memory-based ASICs and FPGAs.

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: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 3: 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.
• 4: Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]
• 5: R. McNaughton and H. Yamada, "Regular Expressions and State Graphs for Automata," in IEEE Transactions on Electronic Computers, EC-9(1), pp. 39--47, 1960.
• 6: Sailesh Kumar , Sarang Dharmapurikar , Fang Yu , Patrick Crowley , Jonathan Turner, Algorithms to accelerate multiple regular expressions matching for deep packet inspection, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 7: Michela Becchi , Patrick Crowley, An improved algorithm to accelerate regular expression evaluation, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323573]
• 8: Benjamin C. Brodie , David E. Taylor , Ron K. Cytron, A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching, Proceedings of the 33rd annual international symposium on Computer Architecture, p.191-202, June 17-21, 2006
• 9: Sailesh Kumar , Jonathan Turner , John Williams, Advanced algorithms for fast and scalable deep packet inspection, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185359]
• 10: Fang Yu , Zhifeng Chen , Yanlei Diao , T. V. Lakshman , Randy H. Katz, Fast and memory-efficient regular expression matching for deep packet inspection, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185360]
• 11: Michela Becchi , Patrick Crowley, A hybrid finite automaton for practical deep packet inspection, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York [doi>10.1145/1364654.1364656]
• 12: Sailesh Kumar , Balakrishnan Chandrasekaran , Jonathan Turner , George Varghese, Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323574]
• 13: Randy Smith , Cristian Estan , Somesh Jha, XFA: Faster Signature Matching with Extended Automata, Proceedings of the 2008 IEEE Symposium on Security and Privacy (sp 2008), p.187-201, May 18-21, 2008 [doi>10.1109/SP.2008.14]
• 14: Reetinder Sidhu , Viktor K. Prasanna, Fast Regular Expression Matching Using FPGAs, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.227-238, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.22]
• 15: C. R. Clark and D. E. Schimmel, "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," in FPL 2003.
• 16: James Moscola , John Lockwood , Ronald P. Loui , Michael Pachos, Implementation of a Content-Scanning Module for an Internet Firewall, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.31, April 09-11, 2003
• 17: B. L. Hutchings , R. Franklin , D. Carver, Assisting Network Intrusion Detection with Reconfigurable Hardware, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.111, September 22-24, 2002
• 18: C. R. Clark et al., "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," in FLP 2003.
• 19: Ioannis Sourdis , Dionisios Pnevmatikatos, Pre-Decoded CAMs for Efficient and High-Speed NIDS Pattern Matching, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.258-267, April 20-23, 2004
• 20: Abhishek Mitra , Walid Najjar , Laxmi Bhuyan, Compiling PCRE to FPGA for accelerating SNORT IDS, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323571]
• 21: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 22: SNORT: http://www.snort.org
• 23: 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]
• 24: Xilinx: http://www.xilinx.com

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

General Terms:
Theory