SHOCK: A Worst-Case Ensured Sub-Linear Time Pattern Matching Algorithm for Inline Anti-Virus Scanning
Nen-Fu Huang, Wang‐Ting Tsai · 2010
To detect viruses, worms and, malware in the multi- gigabit environment, it is crucial for modern content-aware network security appliances to have a fast virus scanning scheme.Signature based multi- pattern matching algorithm is the core technology to enable fast virus scanning accurately and quickly. This paper proposes a multi-pattern matching algorithm with a simple shift/hash technique and a novel heuristic by inspecting overlaps between pairs of patterns to ensure both average and worst-case performance. Experimental results show that our algorithm performs 600 Mbps to 1.4 Gbps faster than the ClamAV AC and BM-based algorithms and achieves a maximum of 3.8 Gbps throughput in inline virus scanning while the memory consumption is nearly the same.