Independent Parallel Compact Finite Automatons for Accelerating Multi-String Matching

Date Added: Apr 2010
Format: PDF

Multi-string matching is a key technique for implementing network security applications like Network Intrusion Detection Systems (NIDS) and anti-virus scanners. Existing DFA-based research have claimed to achieve high-speed throughput at an expenses of extremely high memory cost, so fail to be used in the embedded systems like high-speed routers where very tight on-chip resources are available. This paper extends the classic longest prefix principle from single-character to multi-character string matching and proposes a multi-string matching acceleration scheme named Independent Parallel Compact Finite Automata (PC-FA). The scheme can be understood as consisting of k PC-FAs, each of which can process one character from the input stream, achieving a speedup up to k with reduced memory occupation.