Step-FA: Step-Based Compact Finite Automaton for Accelerating Multi-String Matching

Multi-string matching is a key technique for network security applications like Network Intrusion Detection Systems (NIDS) and anti-virus scanners. %, where every packet is inspected against thousands of predefined signatures in real time. Existing DFA-based approaches always tradeoff between memory and throughput, no known approach has the best of both worlds. Hence, they fail to be used in the embedded systems like high speed routers where only limited on-chip resources are available. This post proposes a multi-step string matching acceleration scheme named step Finite Automata (Step-FA). Different from classical string matching approaches, we suppose to match an additional structural characteristic named as the distance of certain characters in Step-FA rather than the pure explicit characters themselves. As Step-FA does not follow each-byte-one-memory-access manner in the classical DFA, a high speedup can be achieved meanwhile the memory requirement decreased sharply. The Step-DFA gives the trade-off between accurate and approximate matching. For the purpose of guaranteeing he equivalence between the Step-FA and DFA, a verification module is introduced to fast check the already matched results. Experimental evaluations with ClamAV show that a 6 times of speedup can be practically achieved by a single Step-FA Matching System with a 70% reduced memory comparing to the up-to-date DFA-based approaches.