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

doi:10.3778/j.issn.1002-8331.1608-0004

计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (4): 39-44.DOI: 10.3778/j.issn.1002-8331.1608-0004

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

王歧1，2，3，卢毓海1，3，刘洋1，3，刘燕兵1，3，谭建龙1，3，孙波4

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

出版日期:2017-02-15 发布日期:2017-05-11

Dynamical adaptive Karp-Rabin multi-pattern matching algorithm

WANG Qi1，2，3, LU Yuhai1，3, LIU Yang1，3, LIU Yanbing1，3, TAN Jianlong1，3, SUN Bo4

1.Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
2.University of Chinese Academy of Sciences, Beijing 100049, China
3.National Engineering Laboratory for Information Security Technologies, Beijing 100093, China
4.National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100029, China

Online:2017-02-15 Published:2017-05-11

摘要/Abstract

摘要： 多模式匹配算法是网络监测和内容过滤系统的核心算法，但是现有的多模式匹配算法无法实现高并发下动态更新模式串的功能。通过改进Karp-Rabin 算法，实现了多模式字符串匹配技术，实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin 算法的基础上进一步改进，使其在高并发情况下能够支持模式串动态增删功能。实验表明该算法在单个线程不断更新的条件下，随着扫描线程个数的增加，搜索速度能够保持线性增长。

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

Abstract: 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.

Key words: multi-pattern matching, Karp-Rabin, updating dynamically, intrusion detection system, multi-thread

王歧1，2，3，卢毓海1，3，刘洋1，3，刘燕兵1，3，谭建龙1，3，孙波4. 支持模式串动态更新的多模式匹配Karp-Rabin算法[J]. 计算机工程与应用, 2017, 53(4): 39-44.

WANG Qi1，2，3, LU Yuhai1，3, LIU Yang1，3, LIU Yanbing1，3, TAN Jianlong1，3, SUN Bo4. Dynamical adaptive Karp-Rabin multi-pattern matching algorithm[J]. Computer Engineering and Applications, 2017, 53(4): 39-44.

[1]	孙云浩，李逢雨，李冠宇，韩冰，邢维康. 面向RDF图的多模式匹配方法[J]. 计算机工程与应用, 2020, 56(13): 84-92.
[2]	黄思猛1，程良伦2，王涛2. 基于双数组trie树的多模式复杂事件检测方法[J]. 计算机工程与应用, 2019, 55(4): 91-95.
[3]	陈建平，康怡怡，胡龄爻，陆悠，吴宏杰，傅启明. 基于多线程并行强化学习的建筑节能方法[J]. 计算机工程与应用, 2019, 55(15): 219-227.
[4]	刘海燕，张钰，毕建权，邢萌. 基于分布式及协同式网络入侵检测技术综述[J]. 计算机工程与应用, 2018, 54(8): 1-6.
[5]	王荣，王建新，陈向，盛羽. 面向异构资源集成的数字图像实验平台[J]. 计算机工程与应用, 2018, 54(15): 185-191.
[6]	孙剑，刘渊，赵新杰. 基于聚类的应用层DDoS攻击检测方法研究[J]. 计算机工程与应用, 2016, 52(21): 116-120.
[7]	赵旭，王伟. 结合遗传算法的NIDS多媒体包多线程择危模型[J]. 计算机工程与应用, 2016, 52(14): 115-118.
[8]	陈明1，文颖1，谭涛2. WSN中基于MDP与博弈论的入侵检测系统[J]. 计算机工程与应用, 2015, 51(9): 117-121.
[9]	谭睿璞1，赵伟2. 一种快速的可变形物体的碰撞检测算法[J]. 计算机工程与应用, 2014, 50(9): 170-175.
[10]	冯仁君1，宋巍2，马晓星1. 基于WS-BPEL过程的Web服务依赖关系分析[J]. 计算机工程与应用, 2014, 50(2): 25-30.
[11]	张伟1，董群锋2. 云安全综合分析系统的设计与实现[J]. 计算机工程与应用, 2014, 50(19): 89-94.
[12]	李超燕1，裴林滔2. 基于宏与全局变量Floyd并行算法的性能对比[J]. 计算机工程与应用, 2014, 50(16): 45-47.
[13]	翁广安. 基于模拟数据集的字节频度入侵检测研究[J]. 计算机工程与应用, 2014, 50(12): 96-99.
[14]	李志文，张伟. 一种面向大规模短特征集的字符串匹配技术[J]. 计算机工程与应用, 2014, 50(1): 105-110.
[15]	刘睿1，于波1，崔耀东2. 一维下料问题中提高计算效率方法的研究[J]. 计算机工程与应用, 2013, 49(9): 247-250.

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

Dynamical adaptive Karp-Rabin multi-pattern matching algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics