Compact architecture for high-throughput regular expression matching on FPGA

ABSTRACT

In this paper we present a novel architecture for high-speed and high-capacity regular expression matching (REM) on FPGA. The proposed REM architecture, based on nondeterministic finite automaton (RE-NFA), efficiently constructs regular expression matching engines (REME) of arbitrary regular patterns and character classes in a uniform structure, utilizing both logic slices and block memory (BRAM) available on modern FPGA devices. The resulting circuits take advantage of synthesis and routing optimizations to achieve high operating speed and area efficiency. The uniform structure of our RE-NFA design can be stacked in a simple way to produce multi-character input circuits to scale up throughput further. An n-state m-character input REME takes only O (n X log₂ m) time to construct and occupies no more than O (n X m) logic units. The REMEs can be staged and pipelined in large numbers to achieve high parallelism without sacrificing clock frequency.

Using the proposed RE-NFA architecture, we are able to implement 3 copies of two-character input REMEs, each with 760 regular expressions, 18715 states and 371 character classes, onto a single Xilinx Virtex 4 LX-100-12 device. Each copy processes 2 characters per clock cycle at 300 MHz, resulting in a concurrent throughput of 14.4 Gbps for 760 REMEs. Compared with the automatic NFA-to-VHDL REME compilation [13], our approach achieves over 9x throughput efficiency (Gbps*state/LUT). Compared with state-of-the-art REMEs on FPGA, our approach also indicates up to 70% better throughput efficiency.

REFERENCES

• 1: Bro Intrusion Detection System. http://bro-ids.org/.
• 2: SNORT.ORG. http://www.snort.org/.
• 3: 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]
• 4: 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]
• 5: Joao Bispo, Ioannis Sourdis, Joao M. P. Cardoso, and Stamatis Vassiliadis, "Regular Expression Matching for Feconfigurable Packet Inspection", FPT '06: Proceedings of the IEEE International Conference on Field Programmable Technology, 2006., Dec. 2006, pp. 119--126.
• 6: 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
• 7: 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]
• 8: Christopher L. Hayes , Yan Luo, DPICO: a high speed deep packet inspection engine using compact finite automata, 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.1323579]
• 9: 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
• 10: 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]
• 11: 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
• 12: Cheng-Hung Lin , Chih-Tsun Huang , Chang-Ping Jiang , Shih-Chieh Chang, Optimization of regular expression pattern matching circuits on FPGA, Proceedings of the conference on Design, automation and test in Europe: Designers' forum, March 06-10, 2006, Munich, Germany
• 13: 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]
• 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: Randy Smith , Cristian Estan , Somesh Jha, Backtracking Algorithmic Complexity Attacks against a NIDS, Proceedings of the 22nd Annual Computer Security Applications Conference on Annual Computer Security Applications Conference, p.89-98, December 11-15, 2006 [doi>10.1109/ACSAC.2006.17]
• 16: Norio Yamagaki, Reetinder Sidhu, and Satoshi Kamiya, "High-Speed Regular Expression Matching Engine Using Multi-Character NFA", FPL '08: Proceedings of the International Conference on Field Programmable Logic and Applications, 2008., Aug. 2008, pp. 697--701.
• 17: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

Additional 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, Performance, Security

Keywords:
BRAM, FPGA, NFA, finite state machine, intrusion detection, regular expression