Dynamical adaptive Karp-Rabin multi-pattern matching algorithm

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

Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (4): 39-44.DOI: 10.3778/j.issn.1002-8331.1608-0004

Previous Articles Next Articles

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

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

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

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

Abstract

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

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

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

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

[1]	SUN Yunhao, LI Fengyu, LI Guanyu, HAN Bing, XING Weikang. Multi-pattern Matching Method for RDF Graph [J]. Computer Engineering and Applications, 2020, 56(13): 84-92.
[2]	HUANG Simeng1, CHENG Lianglun2, WANG Tao2. Multi-Pattern Complex Event Detection Method Based on Double-Array Trie-Tree [J]. Computer Engineering and Applications, 2019, 55(4): 91-95.
[3]	CHEN Jianping, KANG Yiyi, HU Lingyao, LU You, WU Hongjie, FU Qiming. Building Energy Efficiency Method Based on Multi-Thread Parallel Reinforcement Learning [J]. Computer Engineering and Applications, 2019, 55(15): 219-227.
[4]	LIU Haiyan, ZHANG Yu, BI Jianquan, XING Meng. Review of technology based on distributed and collaborative network intrusion detection [J]. Computer Engineering and Applications, 2018, 54(8): 1-6.
[5]	WANG Rong, WANG Jianxin, CHEN Xiang, SHENG Yu. Digital image experiment platform for heterogeneous resource integration [J]. Computer Engineering and Applications, 2018, 54(15): 185-191.
[6]	SUN Jian, LIU Yuan, ZHAO Xinjie. Detection of application layer DDoS attacks based on clustering [J]. Computer Engineering and Applications, 2016, 52(21): 116-120.
[7]	ZHAO Xu, WANG Wei. Multithreading model for multimedia packets in NIDS based on genetic algorithm [J]. Computer Engineering and Applications, 2016, 52(14): 115-118.
[8]	CHEN Ming1, WEN Ying1, TAN Tao2. Intrusion detection system based on MDP and game theory in WSN [J]. Computer Engineering and Applications, 2015, 51(9): 117-121.
[9]	ZHAO Xu, WANG Wei. Optimization research of DSAMDP method with dynamic programming theory [J]. Computer Engineering and Applications, 2014, 50(22): 83-87.
[10]	ZHANG Wei1, DONG Qunfeng2. Design and implementation of cloud security comprehensive analysis system [J]. Computer Engineering and Applications, 2014, 50(19): 89-94.
[11]	LI Chaoyan1, PEI Lintao2. Difference of multi-thread parallel Floyd algorithm with macro parameter and global variable [J]. Computer Engineering and Applications, 2014, 50(16): 45-47.
[12]	WENG Guang’an. Simulation dataset based study on byte frequency intrusion detection [J]. Computer Engineering and Applications, 2014, 50(12): 96-99.
[13]	LI Zhiwen, ZHANG Wei. String matching technology for large-scale short pattern set [J]. Computer Engineering and Applications, 2014, 50(1): 105-110.
[14]	LIU Rui1, YU Bo1, CUI Yaodong2. Several heuristic strategies to improve computational efficiency for One-Dimensional Cutting Stock Problem [J]. Computer Engineering and Applications, 2013, 49(9): 247-250.
[15]	LEI Xiangyu, ZHOU Ping. Research of support vector machine classifiers for intrusion detection [J]. Computer Engineering and Applications, 2013, 49(11): 88-91.

Dynamical adaptive Karp-Rabin multi-pattern matching algorithm

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics