Computer Science ›› 2017, Vol. 44 ›› Issue (9): 125-130.doi: 10.11896/j.issn.1002-137X.2017.09.025

Previous Articles     Next Articles

Research on Pattern Matching Algorithm in Intrusion Detection System

XU Zhou-bo, ZHANG Yong-chao, GU Tian-long and NING Li-hua   

  • Online:2018-11-13 Published:2018-11-13

Abstract: As an network intrusion detection system,Snort’s detection principle is based on pattern matching.In order to improve the efficiency of the matching algorithm,the BM algorithm in Snort was improved from two aspects.Firstly,in order to increase the moving distance when missing match,the two characters following the character which is aligned with the rightmost location of the pattern in the text and the two corresponding characters moved by length of the pattern are taken into consideration.And the most moving distance is 2m+2.Furthermore,the appearance frequency of the bigger moving distance when missing match is increased by using the probability characteristic of the combination of the rightmost and its next characters.Finally,experiments on these algorithms were conducted.The experimental results show that the proposed algorithm can effectively reduce the times of moving windows and comparing character.As a result,the matching efficiency is improved.

Key words: Intrusion detection,Snort,Pattern matching,Improved BM algorithm

[1] KURUNDKAR G D,NAIK N A,KHAMITKAR S D.Network intrusion detection using Snort[J].International Journal of Engineering Research and Applications,2012,2(2):1288-1296.
[2] OUYANG W L,TOMBARI F,MATTOCCIA S,et al.Perfor-mance evaluation of full search equivalent pattern matching algorithms[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(1):127-143.
[3] HORSPOOL N R.Practical fast searching in strings[J].Soft-ware Practice and Experience,1980,10(6):501-506.
[4] SUNDAY D M.A very fast substring search algorithm[J].Communications of the ACM,1990,33(8):132-142.
[5] MU Y M,LI M G,LIANG Q.The survey of the pattern mat-ching algorithm in intrusion detection system[J].ACTA Electronica Sinica,2006,34(S1):2488-2490.(in Chinese) 牟永敏,李美贵,梁琦.入侵检测系统中模式匹配算法的研究[J].电子学报,2006,34(S1):2488-2490.
[6] QIAO J X,ZHANG H.Improvement of BM algorithm in intrusion detection system[C]∥IEEE International Conference on Software Engineering and Service Science.Beijing,IEEE,2015:652-655.
[7] FAN H B,YAO N M.A fast and exact single pattern matching algorithm[J].Journal of Computer Research and Development,2009,46(8):1341-1348.(in Chinese) 范洪博,姚念民.一种高速精确单模式串匹配算法[J].计算机研究与发展,2009,46(8):1341-1348.
[8] SIMONE F,OˇUZHAN KLEKCI M.Fast and flexible packedstring matching[J].Journal of Discrete Algorithms,2014,28:61-72.
[9] YUN S.An efficient TCAM-based implementation of multi-pattern matching using covered state encoding[J].IEEE Transactions on Computers,2012,61(2):213-221.
[10] LIN C H,CHANG S C.Efficient pattern matching algorithm for memory architecture[J].IEEE Transactions on Very Large Scale Integration Systems,2011,19(1):33-41.
[11] ERDEM O.Tree-based string pattern matching on FPGAs[J].Computers and Electrical Engineering,2016,49:117-133.
[12] SUN W J,QIAN H.Improved BM algorithm and its application in network intrusion detection[J].Computer Science,2013,40(12):174-176.(in Chinese) 孙文静,钱华.改进BM算法及其在网络入侵检测中的应用[J].计算机科学,2013,40(12):174-176.
[13] MA Z F,YANG S Y,GUO G F.A fast improved pattern matching algorithm based on BM[J].Control and Decision,2013,28(12):1855-1859.(in Chinese) 马占飞,杨树英,郭广丰.一种快速的基于BM模式匹配的改进算法[J].控制与决策,2013,28(12):1855-1859.
[14] CHO S,NA J C,PARK K,et al.A fast algorithm for order-preserving pattern matching[J].Information Processing Letters,2015,115(2):397-402.
[15] NSIRA N B,LECROQ T,ELLOUMI M.A fast Boyer-Mooretype pattern matching algorithm for highly similar sequences[J].International Journal of Data Mining and Bioinformatics,2015,13(3):266-288.
[16] ZHANG H L,XU D L,LIANG M,et al.Massive string efficient matching method research[J].Acta Electronica Sinica,2014,42(6):1220-1224.(in Chinese) 张宏莉,徐东亮,梁敏,等.海量模式高效匹配方法研究[J].电子学报,2014,42(6):1220-1224.
[17] BOYER R S,MOORE J S.A fast string searching algorithm[J].Communications of the ACM,1977,20(10):762-772.
[18] LI X B,LIU B X,XU R S.Research of string matching techniques[J].Computer Engineering,2004,30(22):24-26.(in Chinese) 李雪宝,刘宝旭,许榕生.字符串匹配技术研究[J].计算机工程,2004,30(22):24-26.
[19] LIU G S,WANG Y C,XU H Q.A single pattern matching algorithm based on character frequency[J].Acta Electronica Sinica,2002,30(12A):2079-2082.(in Chinese) 刘功申,王永成,许欢庆.基于字频的单模式匹配算法[J].电子学报,2002,30(12A):2079-2082.
[20] AHMED M,MAHMOOD A N,HU J K.A survey of network anomaly detection techniques[J].Journal of Network and Computer Applications,2016,60:19-31.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!