Memory-Based Architecture for Multicharacter Aho–Corasick String Matching
| Autor: | Derek Pao, Xing Wang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Finite-state machine
Computer science Byte 020206 networking & telecommunications 02 engineering and technology String searching algorithm 020202 computer hardware & architecture Set (abstract data type) Hardware and Architecture Aho–Corasick string matching algorithm Memory architecture 0202 electrical engineering electronic engineering information engineering Algorithm design Electrical and Electronic Engineering Algorithm Perfect hash function Software |
| Zdroj: | IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 26:143-154 |
| ISSN: | 1557-9999 1063-8210 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|