计算机科学 ›› 2017, Vol. 44 ›› Issue (9): 125-130.doi: 10.11896/j.issn.1002-137X.2017.09.025
徐周波,张永超,古天龙,宁黎华
XU Zhou-bo, ZHANG Yong-chao, GU Tian-long and NING Li-hua
摘要： 入侵检测系统Snort检测的基本原理是模式匹配。为了提高模式匹配算法的效率,从两方面对Snort中的BM算法进行改进。首先,为了增大模式串移动的距离,改进算法利用了与模式串最右端对齐的下一个及第二个文本字符,以及这两个字符再向右偏移模式串长度所对应字符在模式串中的出现情况,最大移动距离达到了2m+2。其次,为了增大失配时大的移动距离出现的概率,利用了最右端字符与其下一个字符的组合概率特性。最后,对算法进行了性能测试。测试结果表明改进算法减少了窗口移动次数和字符比较次数,提高了匹配效率。
| [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 KLEKCI 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! |
|
||
首页