Fast and Memory-efficient Multiple Pattern Matching Algorithm
Multiple string matching algorithm that can compare hundreds of string patterns simultaneously is a critical component of Intrusion Detection/Prevention System(IDS/IPS).But in Gbps high speed network,the speed of pattern matching is still the bottleneck.This paper proposed an algorithm that based on deterministic finite automata(DFA)which can process multiple characters in a matching cycle.It extracts the head of DFA and constructs it as a sub-DFA,called Head DFA(HDFA).The other part of the DFA is constructed as another sub-DFA called General DFA(GDFA).Tow sets of hardware are designed to carry out the two sub-DFAs respectively and work simultaneously.Matching result is chosen from results of the two sets of hardware according to current state and each matching result.It can not only improve the matching speed,but can also decrease the required memory size greatly by making use of the relationship between the two sub-DFAs.