基于距离比较的AC自动机并行匹配算法  

Distance Comparison Based Parallel Pattern Matching

作　　者：姜海洋[1,2,3] 李雪菲 杨晔 JIANG Haiyang;LI Xuefei;YANG Ye(Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China;Jiangsu Future Networks Innovation Institute,Nanjing 211111,China)

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院大学,北京100049 [3]江苏省未来网络创新研究院,南京211111

出　　处：《电子与信息学报》2022年第2期581-590,共10页Journal of Electronics & Information Technology

基　　金：国家重点研发计划(2019YFB1804500);光合基金B类(20210702)。

摘　　要：随着网络带宽的快速增长,作为网络安全设备核心模块的多模式匹配(MPM)算法面临严峻的性能挑战。该文提出一种高效的数据包分割和并行匹配算法—距离比较并行匹配算法(DCPM)。和已有方法相比,并行的DCPM线程间不存在同步开销,引入的冗余检测开销达到理论最小。基于Aho-Corasick(AC)算法,在8核处理器平台上将DCPM算法与已有的数据包分割方法进行了性能比较。实验结果表明,和已有方法相比,DCPM算法的适应性更好,性能受网络流量中模式串占比、模式串长度及自动机状态数等因素的影响更小;在处理真实数据集时,DCPM算法的加速比提升1.3~3.5倍。Multi-Pattern Matching(MPM)works as a core algorithm of packet processing procedure.In order to improve the performance,an efficient packet segmentation and parallel pattern matching algorithm–DCPM(Distance Comparison Parallel Matching)is proposed based on the Aho-Corasick(AC)algorithm.Comparing with existing solutions,DCPM eliminates the threads’synchronization overhead and decreases the redundant detection overhead.The DCPM algorithm is evaluated on an eight-core processor server platform.The experimental results show that the performance is largely improved(1.3~3.5 times when processing real-world traffic with 8 threads,compared with existing solutions).Meanwhile,the performance of DCPM is less affected by the proportion of pattern strings in the traffic,the length of pattern strings,as well as the number of states in automata.

关 键 词：模式匹配 多线程 多核 深度包检测 AHO-CORASICK算法 

分 类 号：TN915.08[电子电信—通信与信息系统] TP393.08[电子电信—信息与通信工程]