入侵检测系统中的模式匹配算法研究

第12卷第2期重庆科技学院学报（自然科学版）2010年4月收稿日期：2009-09-30作者简介：罗金玲(1965-)，女，湖南娄底市人，娄底职业技术学院电子信息工程系副教授，研究方向为网络安全。

入侵检测系统产生于传统安全策略无法满足日益苛刻的安全需求的情形下，它是一种主动保护自己免受攻击的网络安全技术，是继防火墙、数据加密等传统安全保护措施后的新一代安全保障技术。

模式匹配算法是基于特征匹配的入侵检测系统中的核心算法。

据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。

由此可见，模式匹配算法性能的优劣直接影响到入侵检测系统的效率。

在此介绍几种用于入侵检测的经典模式匹配算法，并在此基础上提出一种入进算法，最后给出入侵检测系统中模式匹配算法的选择策略。

1单模式匹配算法（1）模式匹配。

在给定长度为n 的目标串T 中查找长度为m 的模式P 首次或多次出现的过程，T=T i ，1≤i ≤n ,P=P j ；1≤j ≤m 。

若P 在T 中出现1次或多次，则称匹配成功，否则称匹配失败。

（2）单模式匹配算法。

在目标串中一次只能对1个模式串进行算法匹配。

（3）多模式匹配算法。

在目标串中可同时对多个模式串进行算法匹配。

高效的模式匹配算法都是设法增大不匹配时目标串T 或模式串P 之间的偏移量，以减少总比较次数。

下面介绍两种经典的快速单模式匹配算法。

1.1KMP 算法1970年，Cook 从理论上证明了一维模式匹配问题可以在O (m +2)时间内解决。

Knutht 等在BF 算法的基础上提出了一种快速模式匹配算法，称为KMP 算法［3,4］。

该算法克服了BF 算法的目标串指针在多个字符比较后相等时，只要有1个字符比较不等便需要回溯的缺点，使算法效率得到了大幅度提高，时间复杂度达到最理想的O (m+n )，空间复杂度是O(m )。

KMP 算法的基本思想是：若某趟匹配过程中T i和P j 不匹配，而前j -1个字符已经匹配，此时只需右移模式串P ，目标串T 不动，即指针i 不回溯，让P k 与T i 继续比较，移动后重新开始比较的位置k 仅与模式串P 有关，而与目标串T 无关，因此k 可以通过下面的next 函数事先确定。

定义next ［j ］函数为：next[j ]=max{k ｜1<k <j ，且P 1P 2…P k =P j-k P j-k +2…P j -1}集合非空0其他情况-1（标记）j =0≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤时1．2BM 算法相对于BF 算法，KMP 算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位。

但由上述next 函数可知，右滑的最大距离不会超过1趟匹配操作所进行的比较次数j ，原因在于KMP 算法的匹配操作是从左到右进行的。

受到KMP 算法的启发，Boyer 和Moore 提出一种新的快速字符串匹配算法一BM 算法［5,6］。

BM 算法基本思想是：开始时将目标串T 与模式串P 左对齐，自右至左逐个字符进行比较(即首先入侵检测系统中的模式匹配算法研究罗金玲刘罗仁（娄底职业技术学院，娄底417000）摘要：综述入侵检测系统中的模式匹配算法，包括经典的单模式匹配算法KMP 算法、BM 算法和多模式匹配AC算法。

在此基础上提出一种改进算法———两端分段匹配算法，并加以验证，最后指出改进模式匹配算法效率的研究方向。

关键词：入侵检测；模式匹配；KMP 算法；BM 算法；AC 算法；两端分段匹配算法中图分类号：TP301文献标识码：A文章编号：1673-1980（2010）02-0159-04比较P m 与T m )；当某趟比较时T i 与模式串的对应字符不匹配，则将模式串右滑距离d(x )，执行由P m 与T i +d(x )起始的自右至左的匹配检查。

BM 算法采用两条规则计算模式串右移的距离：好后缀移动和坏字符移动。

（1）好后缀移动，分两种情况。

第一种情况，当P 已比较部分P ［j +1…m ］与其中间的某一子串P ［j -s +1…m -s ］相同，P 右移s 位，如图1所示。

第二种情况，当P 已比较部分P ［j +1…m ］的后缀P ［s +1…m ］与P 的前缀P ［1…m-s ］相同，P 右移s 位，如图2所示。

取满足上述两种情况的s 最小值作为移动距离，因此可以定义一个距离函数D l (j )：D 1(j )=min{s ｜P [j +1…m ]=[j-s +l …m-s ]&&P [j ]≠P [j-s ]（s<j ）,P [s +l …m ]=P [l …m-s ]（2）坏字符移动。

P 中的某个字符与T 中的某个字符不相同时使用坏字符移动。

右滑距离函数D 2(x )定义如下：D 2(x )=m ，（x not in P ）或（x =P m 且x ≠P j (1≤j ≤m -1)）m-j ，j =max{j ｜P j =x ，1≤j ≤m -1}其他情≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤况匹配时取移动距离为：d =max{D l (j )，D 2}。

文献证明算法需要的预处理时间为O (m +σ)，最坏运行时间为O ［(n-m +1)m+σ］，即扫描部分运行时间为O ［(n -m )m ］。

在大字母表(相对于模式长度)情况下，BM 算法非常快，实际比较次数只有目标串长度的20％～30％。

2多模式匹配算法与单模式匹配算法相比，多模式匹配算法的优势在于一趟遍历可以对多个模式进行匹配，从而大大提高了匹配效率。

对于单模式匹配算法，如果要匹配多个模式，那么有几个模式就需要几趟遍历。

当然多模式匹配算法也适用于单模式的情况。

在入侵检测系统中，一条入侵特征可能匹配或部分匹配很多条规则。

如果采用单模式匹配，在匹配每条规则时都需要重新运行匹配算法，效率很低。

然而，日益增多的网络攻击使得入侵检测的规则数目仍在不断增长，因此，单纯提高单模式匹配算法的效率，很难使入侵检测系统满足越来越大的网络数据吞吐量和日益增加的攻击。

目前比较常见的多模式匹配算法有Aho-Corasick 算法、Aho-COrasick-Boyer-Moore 算法、Manber-Wu 算法和Set-Wise Boyel-Moore-Hospool 算法。

2．1AC 算法AC 算法于1975年产生于贝尔实验室，最初用于图书馆的书目查询程序。

该算法基于有限状态自动机(FSA)，在进行匹配之前先对模式串集合SP 进行预处理，形成模式树(树形FSA)，然后只需对目标串T 扫描一次就可以找出所有与其匹配的模式串P 。

模式树K 的构成如图3所示，其中圆圈表示节点，双圈是根节点，边上的字符就是该边的标签，填充点圈的标签就是各个模式。

在预处理阶段，模式树的各个节点作为状态，根节点作为初态，标签为模式的节点作为终态，利用转向函数g 和失效函数f 作为转移函数，将模式树扩展成一个树型有限自动机。

由模式树扩展所得的AC 自动机M 是一个六元组，M =(Q ,∑，g ，f ，q 0，F )：（1）Q 是有限状态集(模式树上的节点)。

（2）∑是有穷的输入字符表(数据包中可能出现的所有字符)。

串T1串P ，本次比较串P ，下次比较1j +1m j-s+1m-ssm s<j图1右滑距离s<j串T串P ，本次比较串P ，下次比较11j +1m1m-ssnm s ≥j图2右滑距离s ≥j图3模式树321h e r s is654789she（3）g是转移函数，g(s，a)表示从当前状态s开始，沿着边上标签为a的路径所达状态。

假如(u，v)边上的标签为a，那么g(u，a)=v；如果根节点上出来的边上的标签没有a，则g(0，a)=0，即如果没有匹配的字符出现，自动机停留在初态。

（4）f也是转移函数，表示不匹配时自动机的状态转移。

该函数定义为：f(s)，当w是L(s)最长真后缀并且w是某个模式的前缀，那么f(s)就是以w为标签的那个节点。

（5）q0∈Q是初态(根节点，标识符为0)。

（6）F是终态集(以模式为标签的节点集)。

于是，在目标串中查找模式的过程转化成在模式树中的查找过程。

查找一个串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走。

若自动机能够抵达终态v，则说明T中存在模式L (v)；否则不存在模式。

AC算法模式匹配的时间复杂度是O(n)，并且与模式集中模式串的个数和每个模式串的长度无关。

无论模式串P是否出现在目标串T中，T中的每个字符都必须输入状态机中。

因此无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O (n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式串的长度总和。

2．2AC-BM算法对多模式串匹配而言，AC算法比BM算法高效得多，但AC算法必须逐一查看目标串的每个字符，即必须按顺序输入，不能实现跳跃，而BM算法则能够利用“右滑”跳过目标串中的大段字符，从而提高搜索速度。

如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。

AC-BM算法是Jang Jong在1993年结合Ac算法的有限自动机和BM算法的连续跳跃思想提出来的新算法，利用劣势移动表和优势跳转表来实现跳跃式地并行搜索，算法的时间复杂度为O(mn)。

该算法的思想是：首先把要查找的多个模式构成一个关键字树，把相同的前缀作为树的根节点。

模式树从目标串的右端向左移动，一旦模式树确定在适当的位置，字符比较从左向右开始进行。

模式树移动时同时使用坏字符移动和好前缀移动。

坏字符移动的策略为：如果出现不匹配的情况，移动模式树，使得树中其他模式中能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上；如果在当前的深度上，目标字符没有出现在任何模式中，则模式树的偏移量为树中最短模式的长度。

好前缀移动的移动策略为：将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置，或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。

在模式树的移动过程中，必须确保模式树的偏移量不能大于树中最短的模式长度。

2.3两端分段匹配算法基于BM单模式算法和AC多模式算法本文提出一种快速两端分段模式匹配算法，算法描述如下：（1）将P与T左端对齐，进行BM匹配。

如果一次性匹配成功，则称为完全匹配，返回结果；如果P i≠T i时将P i提出作为L1，即L1={P1，···，P i}。

（2）将P i+1向下进行匹配，遇到不等时分段。

（3）由多次（1）、（2）步骤得L1，L2，···，L k。

（4）将T分为t1，t2，···，t m个子集，其中{t1，t2，···，t m}∈Σ。