2009年12月第10卷　第4期            长沙铁道学院学报(社会科学版)            Dec.2009Vol .10　No .4
　基于改进的BM 算法在
IDS 中的应用
3
姜华斌
(湖南商务职业技术学院，湖南长沙410205)
摘　要：分析了BM 算法的特征，提出了一种改进B M 字符匹配算法，使改进的BM 算法可以加快其检测速度，提高现有的入侵检测系统的检测能力。
关键词：改进;BM 算法;I D S
  串的模式匹配是一种重要的串运算，对于长度为n 的正文字符串T =T 1…T n 和长度为m 的模式串P =P 1…P m ，要出模式P 在正文T 中的首次出现，一旦模式P 在正文中到，则匹配成功，否则匹配失配。简单的模式匹配算法(B F 算法)思想是：首先将T 1与P 1进行比较，若不相同，则将T 2与P 1进行比较，直
到T 中的某个字符T i 与P 1相同，再将它们之后的字符进行比较，当T 的某一个字符T i 和P 的字符P t 不同时，则T 返回到本趟开始字符的下一个字符,P 返回到P 1，重复上述过程开始下一次比较。当P 中的字符全部比较完，则说明匹配成功，否则匹配失败。
随着网络的迅猛发展、网络安全问题的日益突出、黑客入侵活动的日益猖獗，越来越多的系统遭到了入侵的威胁，入侵检测技术(I D S )成为当今社会关注的焦点。入侵检测作为安全的最后一道屏障，可以在一定程度上预防和检测来自系统内、外部的入侵。由于入侵模式的多样性，入侵检测策略和模型也有多种。从入侵检测的策略来看，入侵检测模型主要有两种：误用检测和异常检测
[1]
。目前大多数入侵检测系统
(I DS)产品均采用误用检测的方法，在误用检测中所用到的检
测技术有：模式匹配，专家系统，状态转移法等，而其中模式匹配最为常用，其具有原理简单、扩展性好等优点，例如Snort 、
B ro 等著名I DS 均采用了模式匹配的技术。
字符串长度17模式串长度
匹配算法直接影响I D S 的实时性能。在网络数据包中搜索入侵特征时，需要一个更加高效的特征串匹配算法。字符串搜索算法中，最著名的是K M P 算法和BM 算法[2]。这两个算法在最坏情况下均具有线性搜索时间
[3]
。但是在实用上,
BM 算法则往往比K M P 算法快上3～5倍。大多数入侵检测
系统现在都使用BM 算法，但BM 算法也存在需改进的地方[4]。
一、Boyer -Moore 算法
Boye r -Moore 算法是一个非常著名的模式匹配算法，它
使用启发式的方法来减少需要比较的次数，绝大部分的入侵
检测模式匹配算法都是在它的基础之上发展而来的。
在讨论算法之前，先假定如下:
(1)入侵特征模式串，也就是我们要查的字符串表示为P;
(2)待检测的数据包，也就是我们将要从中查P 的数
据，表示为T;
(3)P 的长度为m;(4)T 的长度表示为n;
(5)P 的第一个字符和最后一个字符分别表示为P 1、P m ;(6)T 的第一个字符和最后一个字符分别表示为T 1、T n 。BM 算法的思想[5]是:
(1)模式与文本的匹配从右向左进行。将P 与T 从左端
对齐，即P 1与T 1对齐。匹配先从P 的最右端字符开始，判断
Pm 与T m 是否匹配，如果匹配成功，则向左移动，继续判断Pm -1与T m -1是否匹配，循环继续下去，直到P 中的字符全部
匹配成功或者是有不匹配的字符出现。
(2)坏字符移动。BM 算法对模式进行预处理，得到一些
启发式信息，并使用这些信息来计算P 向右移动的距离d
(x )，该移动函数是针对字符x 。
d (x )=
m  若x 不在P 中，或x =Pm 且x ≠P j (1≤j ≤m -1)m -j  其它情况，其中j =max (j :P j =x,1≤j ≤m )
(3)好后缀移动。该移动函数则是针对某个子串的，在对
模式的预处理过程中，算法发现P 中包含一个字符子串，它将在T 中寻这个字符子串的下一个出现位置。将P 移动到该位置，使字符子串与T 中相应的字符子串对齐。
(4)当模式与文本不匹配时，根据坏字符移动函数和好后
缀移动函数来计算偏移值，取两者中的较大值。
文本T =“W angrhe trchsearch ”，模式串P =“search ”，在文本中匹配模式串的过程为表1。
3收稿日期基金项目湖南省高等学校科学研究项目(6D 5)
作者简介姜华斌()，男，湖南岳阳人，副教授，硕士。
1
91:2009-10-19
:004:1971-
表1　B M的模式匹配过程
1234567891011121314151617次W a n g r h e t r c h s e a r c h 一s e a r c h
二s e a r c h
三s e a r c h
四s e a r c h
五s e a r c h
  第一次比较时,T5≠P5，但T5=P4,P4为P中编号最大的，所以d(x)=5-4,P往后移动1位;
第二次比较时,T7≠P6，但T7=P2，所以P往后移动6-2 =4位;
同样，经过第三次、第四次比较，直到第五次比较才完全匹配。
事实上我们认为，在第一次比较时P5=‘c’，它在T串中的T10位置才出现，所以可以直接往后移10-5=5位，第二次比较可以不进行；同样，第三次比较T8≠P3,P3=‘a’，它在T串中的T14位置才出现，所以可以直接往后移14-8=6位。
二、改进BM算法的基本思想
Boye r-Moore算法在比较字符的次数和移位上比一般的算法少了许多，上例发生了5次移位，这样使得匹配速率提高了很多。BM算法是一个单模式字符串匹配算法，坏字符移动最大的距离不超过m；而好后缀移动，该移动函数则是针对某个子串的，算法发现P中包含一个字符子串，它将在T中寻这个字符子串，子串越长时间越多。而当Ti≠P j时采用在T 中P j比子串的速度要快得多，出来后面第一个Td= P j,max{d-i,d(Ti)}即为P往后移动的位数。在比较时会出现很多入侵特征模式串P中的字符是待检测的数据包所在的串T中没有的。因此，这种思想可减少一些无用的移位和比较。
表2为通过这种改进的BM算法后在文本中匹配模式串的过程。
表2　改进B M的模式匹配过程
1234567891011121314151617次W a n g r h e t r c h s e a r c h 一s e a r c h
二s e a r c h
三s e a r c h
  未改进的BM算法的预处理阶段的时间空间复杂性是O (m+n)，查阶段的时间复杂性是O(mn)，改进后的BM算法查阶段的时间复杂度为O(n)。
单纯的模式匹配检测方法的根本问题是，它把网络数据包看作是无序随意的字节流，对该网络数据包的内部结构完全不了解。但网络通信协议是一个高度格式化的、具有明确含义和取值的数据流。如果将协议分析和模式匹配方法结合起来，可以获得更好的效率、更精确的结果。协议分析的作用是辨别数据包的类型，以便使用相应的数据分析程序来检测数据包，同时，可有效地利用网络协议的层次性，快速地判断出攻击特征是否存在。由于协议字段中某些值是在预定范围之内，所以可以利用这些消息提早判断出是否有入侵行为。
因此，可以继续改进BM算法，设计一种模糊快速搜索[6]的匹配算法，假设将长度为m的模式P与长度为n的文本T 进行匹配，该算法的基本思想是：运用Ha s h方法和素数理论，定义一个Hash函数，首先将模式串数值化，然后将文本中每个长度为m的子串利用相同的Hash函数进行数值化。匹配过程不是直接比较模式串与文本子串本身，而是比较Hash函数值，显然只有那些与模式串具有相同Hash函数值的文本子串才有可能与该模式串匹配，这是必要条件。而没有必要考虑文本中所有长度为m的子串，因而大
大提高了串匹配算法的速度。
三、结论
在入侵检测系统中改进的BM算法可减少了移位次数，特别是在T串中模式串出现较少时，查时间短，匹配速度更快，能有效地预防攻击者针对B M算法的攻击。其次，改进BM算法减少了比较次数，在信息量大的情况下，效率更加明显。同时，利用运用Ha s h方法和素数理论设计一种模糊快速搜索匹配算法，进一步有针对入侵检测系统提高匹配的速度还有待于进一步研究。
参考文献:
[1]Hochberg J,Jack s on K,St allings C,et al.NAD I R:An Automated
Syste m for Detecting Net w ork I n trusi on and M isuse[J].Computers and Security,1993,12(3):235-248.
[2]殷人昆，陶永雷.数据结构[M].北京：清华大学出版社,1999.
[3]Boyer R S.A fas t string s earch i ng al go rithm[J].Com m unicati on s of
t he Ass oci ation for C omp uting Machinery,1997,20(10):762-772.
[4]Clark P,N iblet t T.The C N2induct i on algorit hm[J].M achine L earn
-i ng,1989,3(4):261-283.
[5]唐谦，张大方.入侵检测中模式匹配算法的性能分析[J].计算机
工程与应用,2005,(17):136-138.
[6]于泠，陈波.I DS中模式匹配算法及其并行化设计[J].计算机工
程,2004,30(4):46-48.
2 9 1

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。