A Multiple String Matching Algorithm Based on Memory Optimization

Multiple string matching algorithms play a fundamental role in many network security systems, such as intrusion detection and prevention systems, anti-virus systems, anti-spam systems, firewall, etc. It has been observed that the memory space usage and cache locality of automata are critical factors affecting multiple string matching algorithms searching speed. As the pattern set size grows larger and larger, classical multiple string matching algorithms suffer from great performance degradation because of the massive storage usage of string matching automata. The authors propose optimization strategies for the classical string matching algorithm SBOM to reduce its automata size and improve its cache locality, which results in a great promotion in searching speed. More specifically, the Factor Oracle of SBOM algorithm is first replaced with a suffix tree structure, and then the rarely accessed automata nodes are removed through the pruning method to reduce suffix tree to nearly linear space complexity, and finally the pruned suffix tree is represented with double-array trie structure to compress its memory space. Compared with SBOM, this algorithm can greatly reduce memory usage and improve searching speed. Experiments on random data sets show that the proposed algorithm uses memory less than 5% of SBOM and achieves 100% performance improvement over SBOM algorithm. The proposed algorithm is especially suitable for high-speed online pattern matching.