Memory-Based Architecture for Multicharacter Aho-Corasick String Matching

The Aho-Corasick (AC) string matching algorithm is commonly used in signature-based intrusion detection and antivirus systems. In this paper, we present a hardware implementation of the AC algorithm that can process multiple characters per cycle. State transitions are implemented using table lookup. Hence, updates to the pattern set do not require hardware reconfiguration. A fundamental issue of multicharacter AC string matching is the transition rules explosion problem. We apply the transition rule reduction strategy such that the number of transition rules can be reduced to less than two rules per state in the finite automaton. The memory cost is further optimized by implementing the rule table as near-minimal perfect hash table. We implement the proposed method on a virtex-7 FPGA for a pattern set with 2200 Snort signatures. The normalized memory cost of our design is 13.75 bytes per character of the pattern set when four characters are processed per cycle, and the FPGA can operate at 216 MHz.