Fast and memory-efficient regular expression matching for deep packet inspection

ABSTRACT

Packet content scanning at high speed has become extremely important due to its applications in network security, network monitoring, HTTP load balancing, etc. In content scanning, the packet payload is compared against a set of patterns specified as regular expressions. In this paper, we first show that memory requirements using traditional methods are prohibitively high for many patterns used in packet scanning applications. We then propose regular expression rewrite techniques that can effectively reduce memory usage. Further, we develop a grouping scheme that can strategically compile a set of regular expressions into several engines, resulting in remarkable improvement of regular expression matching speed without much increase in memory usage. We implement a new DFA-based packet scanner using the above techniques. Our experimental results using real-world traffic and patterns show that our implementation achieves a factor of 12 to 42 performance improvement over a commonly used DFA-based scanner. Compared to the state-of-art NFA-based implementation, our DFA-based packet scanner achieves 50 to 700 times speedup.

REFERENCES

• 1: J. Levandoski, E. Sommer, and M. Strait, "Application Layer Packet Classifier for Linux." http://l7-filter.sourceforge.net/.
• 2: "SNORT Network Intrusion Detection System." http://www.snort.org.
• 3: "Bro Intrusion Detection System." http://bro-ids.org/Overview.html.
• 4: L. Tan and T. Sherwood, "A High Throughput String Matching Architecture for Intrusion Detection and Prevention," Proc. LISA, 2005.
• 5: Young H. Cho , William H. Mangione-Smith, Deep Packet Filter with Dedicated Logic and Read Only Memories, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.125-134, April 20-23, 2004
• 6: Zachary K. Baker , Viktor K. Prasanna, Time and area efficient pattern matching on FPGAs, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968312]
• 7: Zachary K. Baker , Viktor K. Prasanna, A Methodology for Synthesis of Efficient Intrusion Detection Systems on FPGAs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.135-144, April 20-23, 2004
• 8: M. Aldwairi, T. Conte, and P. Franzon, "Configurable string matching hardware for speedup up intrusion detection," Proc. WASSA, 2004.
• 9: S. Dharmapurikar, M. Attig, and J. Lockwood, "Deep packet inspection using parallel bloom filters," IEEE Micro, 2004.
• 10: Fang Yu , Randy H. Katz , T. V. Lakshman, Gigabit Rate Packet Pattern-Matching Using TCAM, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.174-183, October 05-08, 2004
• 11: Young H. Cho , William H. Mangione-Smith, A pattern matching coprocessor for network security, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065641]
• 12: Todd J. Green , Ashish Gupta , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML streams with deterministic automata and stream indexes, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042051]
• 13: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 14: 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
• 15: 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]
• 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: 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]
• 18: 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
• 19: Christopher R. Clark , David E. Schimmel, Scalable Pattern Matching for High Speed Networks, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.249-257, April 20-23, 2004
• 20: 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
• 21: "Standard for Information Technology, Portable Operating System Interface (POSIX)," Portable Applications Standards Committee of IEEE Computer Society and the Open Group.
• 22: C. L. A. Clarke and G. V. Cormack, "On the use of regular expressions for searching text," Technical Report CS-95-07, Department of Computer Science, University of Waterloo, 1995.
• 23: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 24: "MIT DARPA Intrusion Detection Data Sets." http://www.ll.mit.edu/IST/ideval/data/2000/2000_data_index.html.
• 25: V. Paxson et al., "Flex: A fast scanner generator." http://www.gnu.org/software/flex/.
• 26: Perl compatible Regular Expression, http://www.pcre.org/
• 27: F. Yu, Z. Chen, Y. Diao, T. V. Lakshman and R. H. Katz,, "Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection," UC Berkeley technical report, May 2006.
• 28: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Design, Security

Keywords:
DFA, deep packet, inspection, intrusion detection, regular expressions