支持模式串动态更新的多模式匹配Karp-Rabin算法  

Dynamical adaptive Karp-Rabin multi-pattern matching algorithm

作　　者：王歧[1,2,3] 卢毓海[1,3] 刘洋[1,3] 刘燕兵[1,3] 谭建龙[1,3] 孙波[4] WANG Qi;LU Yuhai;LIU Yang;LIU Yanbing;TAN Jianlong;SUN Bo(Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;University of Chinese Academy of Sciences, Beijing 100049, China;National Engineering Laboratory for Information Security Technologies, Beijing 100093, China;National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100029, China)

机构地区：[1]中国科学院信息工程研究所,北京100093 [2]中国科学院大学,北京100049 [3]信息内容安全技术国家工程实验室,北京100093 [4]国家计算机网络应急技术处理协调中心,北京100029

出　　处：《计算机工程与应用》2017年第4期39-44,69,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61272427);中国科学院战略性科技先导专项(No.XDA06031000);新疆自治区科技专项(No.201230123)

摘　　要：多模式匹配算法是网络监测和内容过滤系统的核心算法,但是现有的多模式匹配算法无法实现高并发下动态更新模式串的功能。通过改进Karp-Rabin算法,实现了多模式字符串匹配技术,实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin算法的基础上进一步改进,使其在高并发情况下能够支持模式串动态增删功能。实验表明该算法在单个线程不断更新的条件下,随着扫描线程个数的增加,搜索速度能够保持线性增长。Multi-pattern matching algorithm plays an important role in network monitoring and filtering system, but the existing multi-pattern matching algorithms can not achieve the function of updating patterns dynamically with high concurrencies.Firstly, the paper has realized multi-pattern matching technology by improving Karp-Rabin algorithm. Experiments show that the improved algorithm exhibits good performance. Then on the basis of the improvement, functionality of updating patterns dynamically is improved. Experiments show that if there is a single thread updating continuously, search speed keeps linear growth with the increase of scanning thread.

关 键 词：多模式匹配 Karp-Rabin算法 动态更新 入侵检测系统 多线程 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]