基于snort的入侵检测系统的研究(15)

图4-1 BM算法匹配过程

4.1.2 AC 算法

Aho-Corasick 算法[16]（简称 AC 算法）是同时搜索多个模式的经典匹配算法。AC 算法利用多个模式串构建一个有限状态模式匹配自动机。自动机是结构化的，每个前缀都可用唯一的状态来标志。当文本中的下一个字符不是模式中预期的下一个字符中的一个时，会出现一条失败链指向那个状态，代表最长的模式前缀，同时也是当前状态的相应后缀。

Snort 应用 AC 算法时，做了以下改进，使得该算法在运行时具有更好的性能。（1）同时支持确定型和不确定型有限状态自动机；（2）采用线性链表来初始化状态转移表；（3）执行过程中，自动机的状态转移表转换成全矩阵形式，有利于减少内存开销；（4）在每一个状态转移链表中增加一个布尔型变量，来指示状态中是否存在一个匹配的模式。

4.1.3 Sunday 算法

Sunday 算法[17]是 Daniel M Sunday 于 1990 年提出的一种比 BM 算法搜索速度更快的算法。该算法的核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行过下一步的匹配，从而提高了匹配的效率。

假设在发生不匹配时 T[i]≠P[j], 1≤j≤M。此时已经匹配的部分为u，并假设字符串u的长度为L。这个时候，我们很显然知道此时的T[L+i+1]肯定要参加下一轮的匹配。并且 P[M]至少要移动到这个位置（即模式串 P至少向右移

动一个字符的位置）。

下面分两种情况讨论（我们只讨论模式串从左向右移动，字符按 P[M]、P[M-1]、 、P[3]的次序从右向左比较的情况。相反的情况可用类似的方法讨论）：

①T[L+i+1]在模式串 P 中没有出现。这个时候模式串 P 移动到T[L+i+1]（包括 T[L+i+1]本身）之前的任何位置，都没有意义。因此，P[0]必须移动到 T[L+i+1]之后的字符的位置。

② T[L+i+1]在模式串 P 中出现。这里所说的 T[L+i+1]在模式串 P中能够出现是指 T[L+i+1]从模式串的右侧，即按 P[M-1]、P[M-2]、 、P[0]的次序查找。如果发现 T[L+i+1]和 P 中的某个字符相同，则记下这个位置，即为 k，1≤k≤M，且 P[k]= T[L+i+1]。此时，应该把模式串 P向右移动 M-k 个字符的位置，即移动到 P[k]和 T[L+i+1]对齐的位置。

按照这种字串移动算法，然后按照字符从右向左的次序匹配。如果完全匹配了，则匹配成功；否则，在进行下一轮的移动，直到正文 T 的最右端结束。该算法最坏情况下的时间复杂度为 O（N*M）。对于短模式串的匹配问题，该算法执行速度较快。Sunday 算法的匹配过程如图4-2所示：

图4-2 Sunday 算法匹配过程

Snort采用了Boyer—Moore字符串匹配算法进行模式匹配。

BM 算法在匹配效率上有一定的缺陷，目前许多算法已经能够在进行模式匹配时，使模式串获得更大的移动距离，提高了匹配效率。下面介绍的一种算法就是建立在对模式串信息分析和利用的基础上实现的。

4.2 匹配算法的优化

通过上述算法分析，根据将要建立的入侵检测系统的实际应用环境的具体情况，决定采用优化的Sunday算法作为入侵检测系统的模式匹配算法。Sunday改进算法的核心思想是：在原Sunday算法之中增加了预处理过程。把原来的模

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新高等教育基于snort的入侵检测系统的研究(15)全文阅读和word下载服务。