Another CDFA Based Multi-Pattern Matching Algorithm and Architecture for Packet Inspection
Tian Song, Dongsheng Wang · 2011
Multi-pattern matching algorithm and architecture is critical for packet inspection based network security applications, especially for high speed network or large pattern sets. This paper presents a method to optimize the potential memory usage of DFA based algorithms for multi-pattern expression matching by the combining DFA's paths, named isomorphic path combination (IMPC). To achieve IMPC, a novel multi-pattern matching algorithm, called ACS, is proposed, which is based on CDFA. Compared to the algorithms on DFA, our method can reduce 78.6% states for Snort pattern set, which results in one of the most memory efficient methods. The most important is that our method is a kind of optimization and can be embedded to other algorithms as the second step for better results. Finally the architecture based on ACS is proposed and the experimental results show that 47.6% to 84.0% memory space can be saved for different size of pattern sets as compared to the best known architectures. The method is another one based on CDFA. It means that CDFA may be a more proper model for multi-pattern matching than other FAs.