入侵检测系统中bm模式匹配算法研究

《入侵检测系统中bm模式匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2010年2月湖南芽一钾耘学院学报Feb．2010第10卷第1期JournalofHunanrstNormalUniversityV01．10．No．1入侵检测系统中BM模式匹配算法研究李俊英1，2，黄汉永(1．中南大学信息科学与工程学院，湖南长沙410008；2．湖南第一师范学院信息科学与工程系，湖南长沙410205)摘要：模式匹配算法是基于规则的入侵检测系统的核心。基于BM模式匹配算法研究，可对其进行改进。改进算法有效地加快了模式匹配的速度，提高了入侵检测的效率。关键词：模式匹配；入侵检测；BM算法；，中图分类号：TP393．08文献标识码

2、A文章编号：1674—831X(2010)01—0154-03随着网络的持续快速发展，信息安全和网络安全形势时模式P可以右移的偏移量。日趋严重和复杂化，入侵检测系统作为一种积极主动的安假设失配发生在T[i+jl=b和P【i]：a处，Badchar、Good—全防护系统，日益成为网络安全领域的研究热点。入侵检sufix函数计算移动过程如下：测系统的实现涉及协议分析、特征匹配、专家系统等多个方(1)Badchar函数计算移动过程。该移动分为2种情况：面，其中最广泛应用的是特征匹配，模式匹配则是入侵检测①将文本串字符T[i+j]与它在模式串中从右到左

3、首次出现中基于攻击特征的关键检测技术之一。Il因此，模式匹配算的位置对齐。如图1(a)所示。②在模式串中如果没有Ⅱi+j]，法的性能直接影响到整个人侵检测系统的效率。则将模式串的最左端字符g1]与i+j+l】对齐，如图1(b)所模式匹配问题可描述如下：对于给定的正文主串示嘲T-T。，⋯Tn，(长度为n)和模式串P=P一Pm(长度为m)，fn>>m)，要求在主串T中寻找等于模式串P的子串，如果存IIJ在这样的子串，则称匹配成功，函数值返回与P中第一个P[二工]==二二字符相等的字符在主串T中的序号；否则称为匹配失败，P口Ⅱ二二函数值返回为0。在各

4、种单模式匹配算法中，应用最广泛和最著名的是BM算法。(a)P[1⋯mJ中再次出现~Ii+Jl1．BM算法1977年，Boyer和Moore提出了一种新的字符串快速P[二正[二]匹配算法——BM算法。BM算法分为预处理和查找两个阶段。厂l———————不—包——含——b———————]l1．1预处理阶段(6j研1⋯州中没有再次出现+J1预处理阶段主要是计算Badchar(charch)和Goodsuffx图1Badchar计算移动过程(charch)l~个偏移函数的值。tnBadchar(charh)数表示如下：，m，x不在P中出现或只出现在尾部

5、(2)Goodsufix函数计算移动过程。该移动分为2种情况：①假设u是文本串与模式串比较过程中已经匹配了的Bad。h)：jfm-j，其中j=max(j：PIJl=x，1≤j≤m一1)，一个子串，如果U再次出现在模式串中，且U前面字符不是其余隋况a，则将模式串最右端再次出现的且前面字符不是a的片段Badchar函数用来计算模式中的某个后缀被匹配成功u与文本串T[i+j+l⋯m]对齐，如图2a所示；②如果u未再收稿日期：2009—03—28作者简介：李俊英(1980一)，女，湖南邵阳人，中南大学信息科学与工程学院研究生，湖南第一师范学院信息科学与

6、工程系讲师；黄汉永(1949一)，男，中南大学信息科学与工程学院副教授。154第l期李俊英，黄汉永：入侵检测系统中BM模式匹配算法研究2010年次出现在模式中，或再次出现但U前面字符是a，将片段T齐，从【7】和P【6】重新开始反向匹配，但是由于Ⅵ6】6]=⋯h’【j+j十¨·m】中最长的后缀v与模式串前缀v对齐，若不存在是成功的匹配，该字符在模式串P中仅出现过一次；所以P这样的，则模式串跳过u，如图2b所示。【5】不会等于P[61，而T[6]=P[6I，所以P[SI不会等于T[61，因此第2次匹配不会成功。bIu(2)再来看看第4次的匹配：由于

7、第3次匹配从ⅡlII开始，失败于T[81处，所以这次匹配从T[14]开始与模式串PP[二工[二]进行从右到左的比较，同样，由于第3次匹配成功的“h”在P口互二二工]中只出现过一次，因而这次比较也是没必要的。(a)u出现在模式串中且前面字符不是a3．2BM算法改进思路对原BM算法的改进主要是在匹配失败后，加大文本向后跳跃的幅度，笔者主要进行了以下两点改进：P[二日](1)通过匹配成功的子串中只在模式P中出现过一次P匾二二二]的字符Ⅵi]产生跳跃。(b)u在模式串中没有出现或出现且前面字符是a(2)通过文本中本次匹配最后一个字符的后两个字符在模式P

8、中的位置产生跳跃。图2Goodsuffix计算移动过程为此，定义一个函数Q()()，当字符XeP，并且仅出现1．2查找阶段过1次时，Q(x)返回值为1