入侵检测系统中一种模式匹配算法的研究与改进
开篇：润墨网以专业的文秘视角，为您筛选了一篇入侵检测系统中一种模式匹配算法的研究与改进范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:对基于入侵检测系统来说,模式匹配算法是基于特征匹配的入侵检测系统中的核心算法,也是当前入侵检测设备中普遍应用的算法。它的效率直接影响到入侵检测系统的准确性和实时性,文章通过对模式匹配算法的改进,提出了一种改进的算法,在匹配文本中重复字符串较多时,该算法可以加快入侵检测系统的检测速度,提高现有入侵检测系统的检测能力。
关键词:BM算法;入侵检测系统(IDS);模式匹配
中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)05-1101-03
Reasching and Improving of Pattern Matching Algorithm in Intrusion Detection System
ZHU Jun,YU Qiang
(School of Computer & Information, Hefei University of Technology, Hefei 230601, China)
Abstract: For the Intrusion Detection System(IDS), pattern matching algorithm is based on feature matching intrusion detection system in the core algorithm, but also the current intrusion detection equipment widely used algorithms. Its efficiency directly affects the accuracy of intrusion detection systems and real-time, the article through improved pattern matching algorithm is proposed an improved algorithm, repeated in the matching text strings more, the algorithm can speed up the intrusion detection system the detection rate, upgrade the existing intrusion detection system detection capability.
Key words: BM algorithm; intrusion detection system(IDS); pattern matching
由于计算机网络自身存在的局限性和信息系统的脆弱性,使得计算机网络系统上的硬件资源,通信资源,软件及信息资源等因为各种原因而遭到破坏、更改、泄露或功能失效,使得信息系统处于异常状态,甚至引起系统的崩溃瘫痪,造成巨大的经济损失。在这样的形式下,以保护网络中的信息免受各种攻击为目的的网络安全变得越来越重要,对安全方面的考虑提高到了越来越重要的地位上。
在设计现有防护系统的时候,只可能考虑到已知的安全威胁与有限范围的未知安全威胁。防护技术只能做到尽量阻止攻击企图的得逞或者延缓这个过程,而不能阻止各种攻击事件的发生,这时就需要引入入侵检测手段加以弥补。
入侵检测系统(IDS)就是按照一定的安全策略建立相应的安全辅助措施的保障系统。目前IDS软件的开发方式基本上就是按照这个思路进行的。对IDS的要求是:如果系统遭到攻击,IDS应尽可能的检测到,甚至是实时的检测到入侵攻击,然后采取适当的处理措施[1]。IDS一般不是采取预防的措施以防止入侵 事件的发生,入侵检测作为安全技术其作用在于:
1) 识别入侵者;
2) 识别入侵行为;
3) 检测和监视已成功的安全突破;
4) 为对抗入侵及时提供重要信息,阻止事件的发生和事态的扩大。
从这些角度看待安全问题,入侵检测非常必要,它将弥补传统安全保护措施的不足。从目前入侵检测技术的研究来看,一个重要的环节是对入侵行为特征进行匹配,即规则匹配。规则匹配的过程就是对从网络上捕获的每一条数据报文和预先定义的入侵规则树进行匹配的过程。如果发现存在某条规则匹配这个报文,就表示检测到一个攻击,然后按照规则指定的行为进行处理;如果搜索完所有的规则都没有找到匹配的规则,就表示报文是正常的报文。BM算法和KMP算法是入侵检测中应用范围最广的一种字符匹配算法,近年来在IDS中也得到应用,典型的IDS中的Snort就采用了BM算法[2]。但由于BM算法自身存在的缺陷,导致在高速网络环境下入侵检测的速度可能跟不上数据包到达速率,进而可能导致丢包现象。 本文提出了BM算法的改进算法,充分利用了Badchar函数在匹配过程中起到的移动指针的主导作用,去掉了GoodSuffix函数的烦琐计算,并对 Badchar函数进行了一定程度的修改,提高了匹配速度。
1 BM算法
该算法由Boyer和Moore提出,是实用中最为快速的算法,并且被大多数IDS所采用。有实验数据表明,BM的匹配速度大约是KMP的3-5倍。
BM基本思想[3-4]:BM算法的基本思想是先对模式P进行预处理,计算两个偏移函数:Badchar(针对某个字符)和GoodSuffix(针对某个子串),然后将文本和模式对齐,从右往左进行匹配,当文本字符与模式字符不匹配时,根据函数Badchar()和GoodSuffix()计算出的偏移值,取两者中的大者。将文本指针往右移,匹配成功则予以输出[3]。
若考虑Badchar()函数的约束,则当文本在字符c与模式不匹配时,下次应移动的距离为Badchar[c]-(m-j),其中j为c在本次匹配中的位置。这样就可以实现下次匹配时文本中的c与模式中的c位置对齐,从而加快匹配的速度。
2 改进的BM算法
使用BM算法进行匹配时,有时虽然发现了模式匹配,但在匹配过程中比较次数过多,最长可达一个模式的长度,有时第二次匹配时己匹配的结果在第三次匹配时仍然逐一比较。如果可以利用第二次匹配的匹配结果,对部分匹配文本进行记录,那么进行第三次匹配时就可以实现跳跃式的比较,这就是改进BM算法的设计思想。
新算法设置了记录与模式的一个后缀相匹配文本的因子。在本次匹配过程中,当比较到模式中已记录的上次匹配后缀时,则实现跳跃式比较,跳过此后缀,从而会减小这次匹配过程中的字符比较次数。与BM算法相比,这无疑会对加快字符搜索有所贡献。
改进BM算法描述
Begin
i:=0;u:=0;shift:=m;
while i≤ n-m do
j:=m;
while j>0 and if p[j]=t[i+j] do
if u0 and j=m-shift then
j:=j-u;
else
j:=j-1;
endif
endwhile
if j≤0 then
output (i+1);
shift:=goodsuffix(0);
u:=m-shift;
else
u:=m-j;i:=i+shift;//移动
endwhile
End
改进BM算法的实例:P:hdbhbhbh,T:hdbudhdbhbhbhububdbhubdh
第1次匹配
i=7不匹配移动1位
(goodsuffix[7]=badchar[a]-8+8)
第2次匹配
i=5不匹配则移动4位
(goodsuffix[5]=badchar[c]-8+6)
第3次匹配
完全匹配,则移动7位(goodsuffix[0]
(带下划线的字符表示上次已经被匹配了,因此本次匹配将跳过)
第4次匹配
i=5不匹配
(goodsuffix[5]=badchar[c]-8+6)
第5次匹配
不匹配则移动7位(goodsuffix[6],至串尾,比较结束。从上面的实例可以看出:文本字符数:24,模式字符:8,进行匹配次数:5字符比较:15,在第三次匹配时,由于在第二次己经匹配了bh,所以省略了2次字符比较。
3 改进BM算法与BM算法的性能比较
为了对标准BM算法和改进BM算法进行定量的性能分析,我们使用了WinDump3.6.2在一个局域网内部随机采集了500M的网络流量数据,使用了检测规则120条,分别对两种算法进行了测试。
1) 时间性能比较[4-5]。通过实验,得到图1。
从图1可见,改进BM算法比BM算法在时间性能上有一定的提高,改善幅度大约在10%-15%左右。由此可见,改进BM算法在处理具有重复后缀的模式匹配时执行速度较快。
2) 空间性能比较[6-7]
表1是BM算法和改进BM算法占用内存空间的比较。可以看出,改进BM算法和BM算法相比所需要的内存空间差别不大。
从测试比较结果可以看出,改进BM算法在执行时间上要比BM算法略快,而占用的内存空间与BM算法基本相等。
4 结论
本文通过对经典的模式算法的分析,提出了改进算法,并用实验加以验证,结果证明,改进BM算法在处理具有重复后缀的模式匹配时执行速度较快。比BM算法增加了一些额外计算,在空间占用几乎与BM算法相等。
参考文献:
[1] 胡建伟.网络安全与保密[M].西安:西安电子科技大学出版社,2003.
[2] 杨武.入侵检测系统中高效模式匹配算法的研究[J].计算机工程,2004(7).
[3] 司凤山.李东江.基于网络入侵检测系统的技术改进[J].枣庄学院学报,2006(2).
[4] 张雷.基于模式匹配的网络入侵检测系统研究[D].成都:西南交通大学信息科学与技术学院,2006.
[5] 巫喜红.凌捷.BM模式匹配算法剖析[J].计算机工程与设计,2007(1).
[6] 伊静.刘培玉.入侵检测中模式匹配算法的研究[J].计算机应用与软件,2005(1).
[7] 冯涛.余冬梅.边培泉.NetBill协议的形式化描述及分析[J].兰州理工大学学报,2004(4).