摘 要:网络安全已经成为国家和官方安全的重要组成部分,入侵检测也就变的至关重要。现今大多数入侵检测系统还是采用的基于规则的模式匹配策略,模式匹配算法的好坏直接影响到入侵检测系统的准确性和实时性。提出了一种改进的bm算法,并从改进的意义、原理和实验分析说明了改进算法在匹配效率上的提高。
关键词:模式匹配;入侵检测;算法

1 bm算法研究

1977年boyer和moore提出了一种全新的算法,即bm算法。它的特点在于匹配过程中,模式从左向右移动,但字符比较却从右向左进行。其基本算法思想是:(1)匹配从右至左进行。(2)若匹配失败发生在p_i≠t_i且t_i不出现在模式p中,则将模式右移直到p_i位于匹配失败位置t的右边第一位(即t_i+1位),若t_i在p中有若干地方出现,则选择j=max{k|p_k=t_i}即通过skip函数计算文本字符t_i失配时模式向右移动的距离,也称坏字符启发。(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)。LocALhOSt最坏情况下要进行3n次比较,最好情况下的时间复杂度为o(n/m)。

2 改进bm匹配算法研究

2.1 改进的意义
综合分析会发现虽然bm算法考虑较全面,但它使用了两个数组,预处理时间开销较大,于是在bm算法基础上我们对其进行了简化,使得算法更简单、高效,提出了一种改进的bm算法。通过实验表明改进的模式匹配算法能减少比较次数,有效地提高了匹配效率。
2.2 改进的原理
在bm算法匹配过程中,常出现模式的一部分后缀与文本匹配,而模式的前缀却不匹配,在这种情况下,就进行了一些不必要的比较。因此在bmgj算法中,我们在对模式串与文本字符串进行匹配时采用从模式两端向中间位置交替的匹配顺序,模式匹配先从模式最右端p_m开始进行。若p_m匹配不成功,则通过skip函数计算出模式向右移动的距离,这与bm算法中坏字符启发思想相同;若p_m匹配成功,则比较模式p₁与文本中相应的字符。若p₁匹配不成功,则考查文本中与模式中p_m下一个字符对齐的字符,若该字符不出现在模式中,则模式可以向右移动m + 1个位置,若该字符出现在模式中,则计算其skip函数,然后将模式向右移动相应的长度;若p₁匹配成功,则按上述方法依次对p_m-1,p₂,p_m-2,p₃,…进行匹配,依此类推,直到匹配过程完成。实例分析:
第1次匹配:
example
here is a simple example
第2次匹配:
example
here is a simple example
第3次匹配(传统bm算法匹配中,此遍比较需要从右端比较5次才可以找到一个坏字符,但对于改进后的算法,只比较两次就可以找到一个坏字符):
example
here is a simple example
第4次匹配:
example
here is a simple example
第5次匹配:
example
here is a simple example
在上例中,我们可以看出用传统的bm算法匹配共进行了4次移动15次比较,用改进的bm算法匹配共进行了4次移动12次比较,匹配次数减少。
改进后的bm算法的预处理时间复杂度为o(m+s),空间复杂度为o(s),搜索阶段时间复杂度为o(mn)。该算法在比较右端字符失配时采用bm坏字符启发的思想,在比较了左端字符失配时采用对文本中与模式最右端对齐的下一个字符进行考查的方法,使得大多数情况下具有比bm算法更大的右移长度,从而有更好的平均性能。

2.3 改进的实验分析
我们所做的实验软件环境主要是:采用的操作系统是microsoft windows xp professional(service pack2),使用jbuilder2006编译工具,所用jdk为jdk1.6。
为了对各算法的性能进行比较次数和比较用时的测试,我们随机地选取了一段纯英文

[1] [2] 下一页