入侵检测模式匹配算法的研究与改进

1 / 9入侵检测模式匹配算法的研究与改进摘 要:网络安全已经成为国家和官方安全的重要组成部分,入侵检测也就变的至关重要。现今大多数入侵检测系统还是采用的基于规则的模式匹配策略,模式匹配算法的好坏直接影响到入侵检测系统的准确性和实时性。提出了一种改进的 BM 算法,并从改进的意义、原理和实验分析说明了改进算法在匹配效率上的提高。 关键词:模式匹配;入侵检测;算法 1 BM 算法研究 1977 年 Boyer 和 Moore 提出了一种全新的算法,即BM 算法。它的特点在于匹配过程中,模式从左向右移动,但字符比较却从右向左进行。其基本算法思想是:(1)匹配从右至左进行。(2)若匹配失败发生在 PiTi 且 Ti 不出现在模式 P 中,则将模式右移直到 Pi 位于匹配失败位置 T 的右2 / 9边第一位(即 Ti+1 位),若 Ti 在 P 中有若干地方出现,则选择 j=maxk|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 / 9第 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)。 4 / 92 改进 BM 匹配算法研究 改进的意义 综合分析会发现虽然 BM 算法考虑较全面,但它使用了两个数组,预处理时间开销较大,于是在 BM 算法基础上我们对其进行了简化,使得算法更简单、高效,提出了一种改进的 BM 算法。通过实验表明改进的模式匹配算法能减少比较次数,有效地提高了匹配效率。 改进的原理 在 BM 算法匹配过程中,常出现模式的一部分后缀与文本匹配,而模式的前缀却不匹配,在这种情况下,就进行了一些不必要的比较。因此在 BMGJ 算法中,我们在对模式串与文本字符串进行匹配时采用从模式两端向中间位置交替的匹配顺序,模式匹配先从模式最右端 Pm 开始进行。若 Pm5 / 9匹配不成功,则通过 Skip 函数计算出模式向右移动的距离,这与 BM 算法中坏字符启发思想相同;若 Pm 匹配成功,则比较模式 P1 与文本中相应的字符。若 P1 匹配不成功,则考查文本中与模式中 Pm 下一个字符对齐的字符,若该字符不出现在模式中,则模式可以向右移动 m + 1 个位置,若该字符出现在模式中,则计算其 Skip 函数,然后将模式向右移动相应的长度;若 P1 匹配成功,则按上述方法依次对 Pm-1,P2,Pm-2,P3,进行匹配,依此类推,直到匹配过程完成。实例分析: 第 1 次匹配: Example here is a simple example 第 2 次匹配: Example here is a simple example 6 / 9第 3 次匹配(传统 BM 算法匹配中,此遍比较需要从右端比较 5 次才可以找到一个坏字符,但对于改进后的算法,只比较两次就可以找到一个坏字符): Example here is a simple example 第 4 次匹配: Example here is a simple example 第 5 次匹配: Example here is a simple example 在上例中,我们可以看出用传统的 BM 算法匹配共进7 / 9行了 4 次移动 15 次比较,用改进的 BM 算法匹配共进行了 4次移动 12 次比较,匹配次数减少。 改进后的 BM 算法的预处理时间复杂度为 O(m+s),空间复杂度为 O(s),搜索阶段时间复杂度为 O(mn)。该算法在比较右端字符失配时采用 BM 坏字符启发的思想,在比较了左端字符失配时采用对文本中与模式最右端对齐的下一个字符进行考查的方法,使得大多数情况下具有比 BM 算法更大的右移长度,从而有更好的平均性能。 改进的实验分析 我们所做的实验软件环境主要是:采用的操作系统是MicroSoft Windows XP Professional(Service Pack2),使用 JBuilderXX 编译工具,所用 JDK 为。 为了对各算法的性能进行比较次数和比较用时的测试,我们随机地选取了一段纯英文自然语 T 文本和模式串 P,在同一台计算机上用不同算法进行 3 万、5 万、10 万次循环匹配,分别统计各算法循环匹配所进行的字符比较次数和总消耗的时间。 文本串:T=One day one pig went to a bar and the bar tender asked what can I get for you today 8 / 9and the pig said five beers. He drank up all the beer and then he asked were the bathroom was the bar tender said straight down the hall to the left. Then three more pigs came in and the bar tender asked what can I get you today. 模式串:P= I get you today. 测试结果下表 1 所示:经过多次匹配实验,结果显示改进后的 BM 算法进行模式匹配时字符比较次数、匹配时间均少于原 BM 算法,匹配效率有所提高。 3 结语 随着网络规模的不断扩大和入侵手段的不断更新,对9 / 9入侵检测也提出了更高的要求。目