一种改进的Boyer-Moore算法在IDS中的应用

计算机科学 ›› 2013, Vol. 40 ›› Issue (Z11): 196-198.

一种改进的Boyer-Moore算法在IDS中的应用

王淅娜,喻建鹏

解放军后勤学院研究生2队北京100858;海军装备部北京100841

出版日期:2018-11-16 发布日期:2018-11-16

Improved Boyer-Moore Algorithm Applied in IDS

WANG Xi-na and YU Jian-peng

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 在IDS的检测引擎模块设计中,基于Pattern-Matching的误用检测算法是设计师们最常用到的一种核心技术实现途径,而IDS丢包率和误报率的高低以及检测引擎匹配速度的快慢都取决于模式匹配算法性能的好与坏。Boyer-Moore算法及其改进了的Boyer-Moore Horspool算法和Boyer-Moore HorspoolS算法是目前应用最广泛的单模式匹配算法。在分析了 BM 算法及各种改进算法的基础上提出了一种新的基于BM算法的改进算法。该算法利用了字符串末字符和末字符对应文本串的下一字符的唯一性,同时考虑了文本串的信息以加大匹配速率,从而更好地适应IDS对模式匹配算法高效性的要求。

关键词: 入侵检测,BM算法,模式匹配,Snort,KMP算法

Abstract: In module design for detection engine of IDS,the misuse of detection based on the Pattern Matching algorithm is the most commonly used by designers as a means of core technology,and the loss rate of data packet,the rate of false positives of IDS and Matching speed of detection engine depend on the performance of Pattern Matching algorithm．Boyer-Moore algorithm,its improved Boyer-Moore Horspool algorithm and Boyer Moore Horspool System algorithm are the the most used-widely Pattern Matching algorithm．Based on the analysis of the BM algorithm and improved algorithm,a new improved BM algorithm is proposed in the article．The algorithm takes advantage of the end character of the string and the uniqueness of next character of corresponding text strings in it,and consider the text string information to increase Matching speed,so that can accommodate to the requirement of high-efficiency of Pattern Matching algorithm for IDS.

Key words: Intrusion detection,BM algorithm Pattern-matching,Snort,KMP algorithm

王淅娜,喻建鹏. 一种改进的Boyer-Moore算法在IDS中的应用[J]. 计算机科学, 2013, 40(Z11): 196-198. https://doi.org/

WANG Xi-na and YU Jian-peng. Improved Boyer-Moore Algorithm Applied in IDS[J]. Computer Science, 2013, 40(Z11): 196-198. https://doi.org/

参考文献

[1] 冉占军,姚全珠.模式匹配算法在入侵检测中的应用[J].计算机应用技术,2011,1(12):63-65
[2] 王新志,等.一种面向软件行为可信性的入侵检测方法[J].中国科学技术大学学报,2011,1(7):626-635
[3] 李雪莹,刘宝旭,许榕生.字符串匹配技术研究[J].计算机工程,2011,0(22):24-26
[4] 杨文君,魏占国,王玉平．入侵检测系统中高效的模式匹配算法[J]．小型微型计算机系统,2010,0(11),2281-225
[5] Namjoshi K,Narlikar G．Robust and Fast Pattern Matching for Intrusion Detection [C]∥IEEE Conference Computer Communications.Piscataway,2010:14-19
[6] Kim H J,Hong H,Kim H-S,et al．A Memory-Efficient Parallel String Matching for Inrusion Detection System [J].IEEE Comunications Letters,2010,3(12):1004-1006
[7] 郇正军.基于snort的网络入侵检测系统研究[D].山东大学,2009:18-19
[8] 袁静波,郑吉森,丁顺利.一种BM模式匹配算法的改进[J].计算机工程与应,2009,5(17):105-107

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed