Algorithms to accelerate multiple regular expressions matching for deep packet inspection

ABSTRACT

There 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 simple string matching algorithms to match packets against a large, but finite set of strings. owever, there is growing interest in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power and flexibility. Deterministic finite automata (DFA) representations are typically used to implement regular expressions. However, DFA representations of regular expression sets arising in network applications require large amounts of memory, limiting their practical application.In this paper, we introduce a new representation for regular expressions, called the Delayed Input DFA (D²FA), which substantially reduces space equirements as compared to a DFA. A D²FA is constructed by transforming a DFA via incrementally replacing several transitions of the automaton with a single default transition. Our approach dramatically reduces the number of distinct transitions between states. For a collection of regular expressions drawn from current commercial and academic systems, a D2FA representation reduces transitions by more than 95%. Given the substantially reduced space equirements, we describe an efficient architecture that can perform deep packet inspection at multi-gigabit rates. Our architecture uses multiple on-chip memories in such a way that each remains uniformly occupied and accessed over a short duration, thus effectively distributing the load and enabling high throughput. Our architecture can provide ostffective packet content scanning at OC-192 rates with memory requirements that are consistent with current ASIC technology.

REFERENCES

• 1: 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]
• 2: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 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: Bro: A System for Detecting Network Intruders in Real-Time. http://www.icir.org/vern/bro-info.html
• 5: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 6: Spyros Antonatos , Kostas G. Anagnostakis , Evangelos P. Markatos, Generating realistic workloads for network intrusion detection systems, Proceedings of the 4th international workshop on Software and performance, January 14-16, 2004, Redwood Shores, California
• 7: 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]
• 8: Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
• 9: S. Wu, U. Manber," A fast algorithm for multi-pattern searching," Tech. R. TR-94-17, Dept. of Comp. Science, Univ of Arizona, 1994.
• 10: Fang Yu, et al., "Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection", UCB tech. report, EECS-2005-8.
• 11: N. Tuck, T. Sherwood, B. Calder, and G. Varghese, "Deterministic memory-efficient string matching algorithms for intrusion detection," IEEE Infocom 2004, pp. 333--340.
• 12: Lin Tan , Timothy Sherwood, A High Throughput String Matching Architecture for Intrusion Detection and Prevention, Proceedings of the 32nd annual international symposium on Computer Architecture, p.112-122, June 04-08, 2005
• 13: 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
• 14: S. Yusuf and W. Luk, "Bitwise Optimised CAM for Network Intrusion Detection Systems," IEEE FPL 2005.
• 15: 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]
• 16: C. R. Clark and D. E. Schimmel, "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," In Proceedings of 13th International Conference on Field Program.
• 17: 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
• 18: Robert W. Floyd , Jeffrey D. Ullman, The Compilation of Regular Expressions into Integrated Circuits, Journal of the ACM (JACM), v.29 n.3, p.603-622, July 1982 [doi>10.1145/322326.322327]
• 19: Scott Tyler Shafer, Mark Jones, "Network edge courts apps," http://infoworld.com/article/02/05/27/020527newebdev_1.html
• 20: TippingPoint X505, www.tippingpoint.com/products_ips.html
• 21: Cisco IOS IPS Deployment Guide, www.cisco.com
• 22: Tarari RegEx, www. tarari.com/PDF/RegEx_FACT_SHEET.pdf
• 23: Cu-11 standard cell/gate array ASIC, IBM. www.ibm.com
• 24: Virtex-4 FPGA, Xilinx. www.xilinx.com
• 25: N.J. Larsson, "Structures of string matching and data compression," PhD thesis, Dept. of Computer Science, Lund University, 1999 .
• 26: S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood, "Deep Packet Inspection using Parallel Bloom Filters," IEEE Hot Interconnects 12, August 2003. IEEE Computer Society Press.
• 27: Z. K. Baker, V. K. Prasanna, "Automatic Synthesis of Efficient Intrusion Detection Systems on FPGAs," in Field Prog. Logic and Applications, Aug. 2004, pp. 311--321.
• 28: 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
• 29: Maya Gokhale , Dave Dubois , Andy Dubois , Mike Boorman , Steve Poole , Vic Hogsett, Granidt: Towards Gigabit Rate Network Intrusion Detection Technology, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.404-413, September 02-04, 2002
• 30: J. Levandoski, E. Sommer, and M. Strait, "Application Layer Packet Classifier for Linux". http://l7-filter.sourceforge.net/.
• 31: "MIT DARPA Intrusion Detection Data Sets," http://www.ll.mit.edu/IST/ideval/data/2000/2000_data_index.html.
• 32: Vern Paxson et al., "Flex: A fast scanner generator,"http://www.gnu.org/software/flex/
• 33: SafeXcel Content Inspection Engine, hardware regex acceleration IP.
• 34: Network Services Processor, OCTEON CN31XX, CN30XX Family.
• 35: R. Prim, "Shortest connection networks and some generalizations,"Bell System Technical Journal, 36:1389--1401, 1957.
• 36: J. B. Kruskal, "On the shortest spanning subtree of a graph and the traveling salesman problem," Proc. of the American Mathematical Society, 7:48--50, 1956.
• 37: F. M. Liang. A lower bound for on-line bin packing. In Information Processing letters, pages 76--79, 1980.
• 38: Will Eatherton, John Williams, "An encoded version of reg-ex database from cisco systems provided for research purposes".
• 39: Garey, M. R., and Johnson, D. S., "Bounded Component Spanning Forest", pp 208, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

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, regular expressions