| As one of the core technologies in network security systems, pattern matching algorithm greatly influences, and even determines the overall performance, so it aroused general concerns from both academic and industrial researchers. Now, the major challenge of pattern matching research comes from the quickly enlarging pattern set. Most classic algorithms can not work well under large-scale pattern set. Moreover, along with the increasing network bandwidth, pattern matching often becomes the bottleneck in network security systems. As a result, efficient pattern matching algorithm for large-scale pattern set is now urgently needed, and this research topic has significant academic value and application outlook.This paper proposes a novel high performance pattern matching algorithm for large-scale pattern set, named Multi-Phase Dynamic Hash (MDH). In this algorithm, multi-phase hash is introduced to cut down the memory requirement under large-scale pattern set, and dynamic-cut heuristics is designed to fully explore pattern set information and improve the overall matching performance. Experimental results demonstrate that MDH can speed up the matching procedure by about 100% to 300%, compared with other classic multiple pattern matching algorithms, such as AC, WM and SBOM, whereas, maintain comparatively low memory requirement.Then, this paper further presents a pattern-length adaptive algorithm and an intelligent verification optimization to break the inherent limitations of MDH algorithm and enhance the algorithm scalability. Beside this, this paper also designed several multi-core multi-threaded parallel algorithms on the basis of MDH, which can make full use of hardware advantage of generic multi-core CPU and the latest multi-core network application processors. Finally, we apply MDH algorithm to a popular opensource virus scanning system, Clam AntiVirus, and get large performance improvement, which again prove its performance and portability. |
PDF Full Text Request