Partial character decoding for improved regular expression matching in FPGAs

Abstract

High-speed string pattern matching in hardware is required in many applications including network intrusion detection applications. Regular expressions are one method to implement such matching and are often built in FPGAs using non-deterministic finite automata (NFAs). To obtain high throughputs it is necessary to process many bytes in parallel. This paper extends the modular NFA construction method of Sidhu and Prasanna to handle the processing of many bytes in parallel. The paper also introduces the concept of partial character decoding in which character match units are shared but the number of signals needed to be routed around the FPGA is reduced over previous shared-decoder approaches. With these approaches, throughput over 5Gbps is achieved for the full default Snort rule-set (23401 literals) in a Xilinx Virtex-2 6000 FPGA. Throughputs over 40Gbps are achieved on smaller rule-sets. Suggestions to improve performance are also given.