入侵防御检测系统模式匹配算法综述.doc

《入侵防御检测系统模式匹配算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、入侵防御检测系统模式匹配算法综述入侵检测中的异常检测是指根据川户的行为或资源的使川状况的正常程度来判断是否属于入侵，其误检率和漏检率高，因此目前大多数入侵检测系统产品均属误用检测。而在异常检测的诸多技术中，由于模式匹配原理简单、可扩展性好而最为常用。所以可以说，模式匹配算法的性能直接影响入侵检测系统的检测效率。其模式匹配算法可以分为两类：单模式匹配算法和多模式匹配算法。单模式匹配算法般包括BF算法、BM算法、KMP算法、RK算法，而多模式匹配算法常用的有AC算法、AC-BM算法、IACBM算法。

2、模式匹配是指在给定长度为n的文本串T=T[l]T[2]...T[n]中查找长度为m的模式串P=P[l]P[2]...P[m]的第一次出现的过程。这里T[i]（l

3、高：主串指针i在若干个字符序列比较相等后，若有一个字符不相等，仍需回溯至i(i=i-j+1),最好情况下时间复杂度o(m)(主串开头即匹配到)，最快情况下时间复杂度o(n*m)(主串结尾匹配)。算法较为简单，但效率很低。(2)BM算法BM算法的基本思想是从右向左进行比较。开始时仍是P的最左边与T的最左边对齐，但首先进行Pm与Tin的比较。当某比较中出现不匹配时，BM算法采用两条启发性规则计算模式串右移的距离，即坏字符规则和好后缀规则。1)坏字符规则(BadCharacter)P中的某个字符与T中

4、的某个字符不相同时使用坏字符规则右移模式串P，P右移的距离可以通过deltal函数计算出来。deltal函数的定义如下：Cm;xHP[j](lWjWm),即:x在P中未出现deltal(x)=

5、P[k]=x3lWk

6、。九P中间的某一子串P[j-s+l..m-s]与已比较部分P[j+l・・m]相同,可让P右移s位。九P已比较部分P[j+l・・m]的后缀P[s+l..m]与P的前缀P[l..m-s]相同，可让P右移s位。满足上面情况的s的最小值为最佳右移距离。delta2的定义如下:delta2(j)=min{s

7、(P[j+l..m]=P[j-s+l..m-s])&&(P[j]/P[j-s])(j>s)?P[s+l..m]=P[l..m-s](j

8、ta1和delta2中的大者。BM算法的最坏时间复杂度为O(m・n),但实际比较次数只有文本串长度的20%〜30%0(3)KMP算法KMP算法的基本思想是：若某趟匹配过程中T[i]和P[j]不匹配，而前j-1个字符已经匹配。此时只需右移模式串P,文本串T不动，即指针i不回溯，让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串S无关，因此K可以事先确定。若定义函数next(j)=K,则next函数的定义应为：next(j)=Max{k

9、P[l..K-l]=P[j-

10、k+l..j-1]}KMP算法的时间复杂度是O(m+n),空间复杂度是O(m),对BF算法进行了很大的改进。(4)RK该算法利用Hash方法和素数理论，首先定义一个Hash函数,然后将模式串P和文本串T中长度为m的子串利用Hash函数转换成数值。显然只需比较那些与模式串具有相同Hash函数值的子串，从而提高了效率。当然因为Hash冲突的存在，还要进一步进行字符串比较，但只要选择适当的素数Hash冲突的概率就会很小。设c=E

11、,Hash函数为h(r)=rmodq,这里q是在区间[l..n2m]中随

12、机选取的适当大的素数，asc(c)为任意字符c的Ascii码。将模式串P映射成整数x(0