Design of high performance pattern matching engine through compact deterministic finite automata

ABSTRACT

Pattern matching relies on deterministic finite automata (DFA) to search for predefined patterns. While a bit-DFA method is recently proposed to exploit the parallelism in pattern matching, we identify its limitations and present two schemes, Label Translation Table (LTT) and CAM-based Lookup Table (CLT), to reduce the DFA memory size by 85%, and simplify the design by requiring only four processing elements of bit-DFA instead of thousands.

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: N. S. Artan and H. J. Chao. Multi-packet Signature Detection using Prefix Bloom Filters. In IEEE GLOBECOM, November 2005.
• 3: M. Becchi and S. Cadambi. Memory-Efficient Regular Expression Search Using State Merging. In IEEE INFOCOM, 2007.
• 4: H-J Jung, Z. K. Baker, and V. K. Prasanna. Performance of FPGA Implementation of Bit-split Architecture for Intrusion Detection Systems. In RAW at IEEE IPDPS, April 2006.
• 5: Jia Ni , Chuang Lin , Zhen Chen , Peter Ungsunan, A Fast Multi-pattern Matching Algorithm for Deep Packet Inspection on a Network Processor, Proceedings of the 2007 International Conference on Parallel Processing, p.16, September 10-14, 2007 [doi>10.1109/ICPP.2007.7]
• 6: Piti Piyachon , Yan Luo, Efficient memory utilization on network processors 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.1185358]
• 7: Piti Piyachon , Yan Luo, Compact state machines for high performance pattern matching, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278607]
• 8: Snort. http://www.snort.org/, 2003.
• 9: Ioannis Sourdis , João Bispo , João M. Cardoso , Stamatis Vassiliadis, Regular Expression Matching in Reconfigurable Hardware, Journal of Signal Processing Systems, v.51 n.1, p.99-121, April 2008 [doi>10.1007/s11265-007-0131-0]
• 10: 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
• 11: Lin Tan , Brett Brotherton , Timothy Sherwood, Bit-split string-matching engines for intrusion detection and prevention, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.1, p.3-34, March 2006 [doi>10.1145/1132462.1132464]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance, Security

Keywords:
content addressable memory, deterministic finite automata, pattern matching