Design and Implementation of A Multi-pattern String Matching Algorithm in Cloud Center Network Intrusion Detection System

doi:10.3969/j.issn.1671-1122.2018.01.008

Abstract

Abstract:

Cloud center network traffic and string pattern set scale is very large, bring great challenge to intrusion detection system. In order to solve the Wu-Manber multi-pattern string matching algorithm matching efficiency and low matching success rate, and reduce the effects of the shortest pattern string length to match algorithm. This paper proposes an improvement algorithm based on WM - IS_WM (Improved Sunday Wu - Manber) algorithm. This method improve the WM algorithm by using the idea of character jump and leakage matching that can make the match window move a greater distance since the current matching fails. It can reduces the number of useless matching, and raises the efficiency of pattern string matching. By using text data test and setting up the sensitive word filtering system, the results of the experiments show that the IS_WM algorithm has lower time complexity and higher matching efficiency than the other algorithms. The proposed IS_WM algorithm is helpful to improve the ability of detecting and filtering sensitive words of cloud center network intrusion detection system.

Key words: multi-pattern string matching, WM algorithm, IS_WM algorithm, characters jump matching

CLC Number:

TP309.1

Guofeng ZHAO, Fei YE, Yongan YAO, Yan ZHAO. Design and Implementation of A Multi-pattern String Matching Algorithm in Cloud Center Network Intrusion Detection System[J]. Netinfo Security, 2018, 18(1): 52-57.

Figures/Tables 6

References 19

[1]	DAGAR V, PRAKASH V, BHATIA T.Analysis of Pattern Matching Algorithms in Network Intrusion Detection Systems[C]//IEEE. International Conference on Advances in Computing, Communication, & Automation. September 30-October 1, 2016, Mahatama Jyotiba Phule Rohilkhand University, Bareilly, India. New York: IEEE, 2016:1-5.
[2]	李国, 蒿培培. 基于Android平台的入侵检测系统的研究与实现[J]. 信息网络安全, 2013(2):27-29.
[3]	DANG N L, LE D N, LE V T.A New Multiple-Pattern Matching Algorithm for the Network Intrusion Detection System[J]. IACSIT International Journal of Engineering and Technology, 2016, 8(2): 94-100.
[4]	林闯, 苏文博, 孟坤, 等. 云计算安全: 架构, 机制与模型评价[J]. 计算机学报, 2013, 36(9): 1765-1784.
[5]	张光斌, 谢维盛, 吴鸿伟. 基于CUDA的多模式匹配技术[J]. 信息网络安全, 2011(9): 126-128.
[6]	SINGH R, MOHAAR G S.Fast Document Indexing Using Aho-Corasick State Machine[C]// IEEE Computer Society. International Conference on Information Reuse and Integration, July 28-30,2016,Pittsburgh, PA, USA. New York: IEEE, 2016: 469-475.
[7]	MA W H, LIU Y M, Ye F, et al.An Improved Wu-Manber Multiple Patterns Matching Algorithm[J]. Applied Science and Technology, 2007, 34(10): 33-37.
[8]	ALDWAIRI M, Al-KHAMAISEh K.Exhaust: Optimizing Wu-Manber Pattern Matching for Intrusion Detection Using Bloom Filters[C]// IEEE. Web Applications and NETWORKING , March 21-23 ,2015,Sousse, Tunisia. New York: IEEE, 2015: 1-6.
[9]	XIANG Q Q, LV Z, QIAO P L.An Improvement Measure to AC-BM Pattern Matching Algorithm in Intrusion Defense System[J]. Applied Mechanics and Materials. Trans Tech Publications, 2013, 7(344): 234-237.
[10]	刘春晖. 基于跳跃式匹配的多模式匹配算法研究[D]. 合肥:合肥工业大学, 2015.
[11]	徐京, 张彦, 辛阳,等. 高速网络内容监控系统的关键技术分析[J]. 信息网络安全, 2012(10):29-35.
[12]	刘卫国, 胡勇刚. DHSWM: 一种改进的WM多模式匹配算法[J]. 中南大学学报: 自然科学版, 2011, 42(12): 3765-3771.
[13]	ZHANG L, PENG Y, LIANG J, et al.An Improved String Matching Algorithm for HTTP Data Reduction[C]//IEEE. Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2015 International Conference on,September 23-25,2015, Adelaide, SA, Australia. New York: IEEE, 2015: 345-348.
[14]	WU S, MANBER U. A Fast Algorithm for Multi-pattern Searching[EB/OL]. .
[15]	ZHANG W.An Improved Wu-Manber Multiple Patterns Matching Algorithm[C]// IEEE. Electronic Information and Communication Technology (ICEICT),August 20-22,2016, Harbin, China. New York: IEEE, 2016: 286-289.
[16]	CHEN J, CAI S, ZHU L, et al.An Improved String-searching Algorithm and Its Application in Component Security Testing[J]. Tsinghua Science and Technology, 2016, 21(3): 281-294.
[17]	巫喜红, 凌捷. 改进的Sunday 模式匹配算法的设计与实现[J]. 哈尔滨理工大学学报, 2013, 18(6): 52-57.
[18]	YANG Z, SHEN L, YANG Y.Poster: A YC_Sunday Algorithm Based on Improved Sunday Algorithm[C]// IEEE. European Alliance of Innovation.International Conference on Communications and Networking in China,August 14-16,2014, Maoming, China. New York: IEEE, 2014: 680-681.
[19]	杨波. 基于有限状态自动机的中文多模式匹配算法研究[D]. 合肥:合肥工业大学, 2013.