1 BM算法研究
1977年Boyer和Moore提出了一种全新的算法,即BM算法。它的特点在于匹配过程中,模式从左向右移动,但字符比较却从右向左进行。其基本算法思想是:(1)匹配从右至左进行。(2)若匹配失败发生在Pi≠Ti且Ti不出现在模式P中,则将模式右移直到Pi位于匹配失败位置T的右边第一位(即Ti 1位),若Ti在P中有若干地方出现,则选择j=max{k|Pk=Ti}即通过Skip函数计算文本字符Ti失配时模式向右移动的距离,也称坏字符启发。(3)若模式后面k位与文本T中一致的部分有一部分在P中其他地方出现,则可以将P向右移动,直接使这部分对齐,且要求这一部分尽可能大,Shift函数通过对已经匹配部分的考查决定模式向右移动的距离,也称好后缀启发。
实例分析:
第1次匹配:
Example
here is a simple example
第2次匹配(坏字符启发):
Example
here is a simple example
第3次匹配(坏字符启发):
Example
here is a simple example
第4次匹配(好后缀启发):
Example
here is a simple example
第5次匹配(坏字符启发):
Example
here is a simple example
BM算法预处理时间复杂度为O(m s),空间复杂度为O(s),s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(mn)。最坏情况下要进行3n次比较,最好情况下的时间复杂度为O(n/m)。
2 改进BM匹配算法研究
2.1 改进的意义
综合分析会发现虽然BM算法考虑较全面,但它使用了两个数组,预处理时间开销较大,于是在BM算法基础上我们对其进行了简化,使得算法更简单、高效,提出了一种改进的BM算法。通过实验表明改进的模式匹配算法能减少比较次数,有效地提高了匹配效率。
2.2 改进的原理
在BM算法匹配过程中,常出现模式的一部分后缀与文本匹配,而模式的前缀却不匹配,在这种情况下,就进行了一些不必要的比较。因此在BMGJ算法中,我们在对模式串与文本字符串进行匹配时采用从模式两端向中间位置交替的匹配顺序,模式匹配先从模式最右端Pm开始进行。若Pm匹配不成功,则通过Skip函数计算出模式向右移动的距离,这与BM算法中坏字符启发思想相同;若Pm匹配成功,则比较模式P1与文本中相应的字符。若P1匹配不成功,则考查文本中与模式中Pm下一个字符对齐的字符,若该字符不出现在模式中,则模式可以向右移动m 1个位置,若该字符出现在模式中,则计算其Skip函数,然后将模式向右移动相应的长度;若P1匹配成功,则按上述方法依次对Pm-1,P2,Pm-2,P3,…进行匹配,依此类推,直到匹配过程完成。实例分析:
经过多次匹配实验,结果显示改进后的BM算法进行模式匹配时字符比较次数、匹配时间均少于原BM算法,匹配效率有所提高。
3 结语
随着网络规模的不断扩大和入侵手段的不断更新,对入侵检测也提出了更高的要求。目前,BM算法还是入侵检测系统中主要使用的模式匹配方法,而它本身存在的一些问题使其还是有改进的余地,本文对其进行了改进,并且通过实验结果分析得出改进以后在匹配效率的提高。以后我们还可以在检测引擎中结合其他智能化的检测方法,如协议分析、神经网络、遗传算法等,这将是我们下一步研究的重点。
参考文献
`1`?谷晓钢,江荣安,赵铭伟.Snort的高效规则匹配算法`J`.计算机工程,2006,(18).
`2`?唐正军.入侵检测技术导论(第一版)`M`.北京:机械工业出版社,2004.
`3`?边肇祺,阎平凡,杨存荣.模式识别(第一版)`M`.北京:清华大学出版社,1988.
`4`?郭军,笹尾勤.入侵检测中模式匹配算法的FPGA实现`J`.科技创新导报,2007,(14).
以上是关于论入侵检测系统的研究与改进已公布的相关信息,请自考生们认真查看,如果你想获取最新的江苏自考新闻或者江苏自考问题答疑,可以扫描江苏自考网公众号二维码,我们会最第一时间内为你解答。
➤自考有疑惑或想进学习群,请联系江苏自考网客服