模式匹配算法在入侵检测中的应用

冉占军　姚全珠　王晓峰　邹又姣

摘 要：仅依靠传统的被动防御技术已经不能满足如今的网络安全需要，基于模式匹配的入侵检测系统正成为研究和应用的热点，模式匹配效率的高低决定了这类入侵检测系统的性能。全面综述了应用于入侵检测系统的经典的模式匹配算法，包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC－BM算法，并对各种算法的执行效率进行了总结。通过分析算法的思想，提出了未来此类算法的研究方向。

关键词：入侵检测；KMP算法；BM算法；RK算法；AC算法；AC－BM算法

中图分类号：TP301文献标识码：B

文章编号：1004 373X(2009)02 063 05

Application of Pattern Matching Algorithm in Intrusion Detection Technique

RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1

(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)

Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.

Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC－BM algorithm

0 引 言

随着网络技术的发展，各种基于网络的应用层出不穷。面对日益突出的网络安全问题，仅靠传统的被动防御已经不能满足要求，能够主动检测并预防的入侵检测系统应运而生。

根据采用的分析方法，入侵检测分为误用检测和异常检测。误用检测是指：根据己知的攻击方法，预先定义入侵特征，通过判断这此特征是否出现来完成检测任务。异常检测是指：根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有: 模式匹配、专家系统、状态转移等，其中模式匹配原理简单，可扩展性好，而且最为常用。据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。

由此可见，模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高，入侵检测系统需要处理的数据量越来越大，如果模式匹配算法来不及处理这些实时的大量的数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中很可能就包含有入侵信息，从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法，包括单模式匹配算法和多模式匹配算法，通过对它们进行剖析和实际测试，提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。

1 单模式匹配算法

1.1 相关定义

模式匹配：是指在给定长度为n的目标串T=T1T2…T璶中查找长度为m的模式串P=P1P2…P璵的首次出现或多次出现的过程。这里T璱(1≤i≤n)，

P璲(1≤j≤m)∈∑(字符集)，若P在T中出现1次或多次，则称匹配成功，否则称匹配失败。

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

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

最简单的模式匹配算法是Brute－Force算法(BF算法)。在BF算法的目标串和模式串的字符比较中，只要有1个字符不相等，而不管前面已有多少个字符相等，就需要把目标串T回退，下次比较时目标串T只后移1个字符。虽然算法简单，但效率低下，不适合用于入侵检测系统中，不做重点介绍。

高效的模式匹配算法都是设法增大不匹配时目标串T或模式串P之间的偏移量，以减少总的比较次数。下面介绍3种经典的快速单模式匹配算法。

1.2 KMP算法

1970年，S.A.Cook从理论上证明了一维模式匹配问题可以在O(m+n)时间内解决［1］。D.E.Knuth，V.R.Pratt和T.H.Morris 在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法［1］，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1个字符比较不等便需要回溯的缺点，使算法的效率得到了大幅度提高，时间复杂度达到最理想的O(m+n)，空间复杂度是O(m)。

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

定义next［j］函数为：

next［j］=max{k|1＜k＜j且 P1P2…P璳=

P璲-kP璲-k+2…P璲-1} ，集合非空

0，其他情况

-1(标记)，j=0时

1.3 BM算法

相对于BF算法，KMP算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位，但由上述next函数可知：右滑的最大距离不会超过1趟匹配操作所进了的比较次数j，原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发，R.S.Boyer和J.S.Moore提出一种新的快速字符串匹配算法－BM算法［1－3］。

BM算法基本思想是：开始时将目标串T与模式串P左对齐，自右至左逐个字符进行比较(即首先比较P璵与T璵)；当某趟比较时T璱与模式串的对应字符不匹配，则把模式串右滑d(x)一段距离，执行由P璵与T璱+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离：

(1) 好后缀移动。其又分为2种情况：

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

图1 右滑距离s,(s＜j)

② P已比较部分P［j+l…m］的后缀P［s+l…m］与P的前缀P［l…m-s］相同，P右移s位。如图2所示。

图2 右滑距离s,(s≥j)

取满足上述两种情况的s的最小值作为移动距离。因此可以定义一个距离函数dist1(j)：

dist1(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中的某个字符不相同时使用坏字符移动。右滑距离函数dist2(x)定义如下：

dist2(x)=

m,(x not in P)或

(x=P璵且x≠P璲(1≤j≤m-1))

m-j,j=max{ j | P璲=x,1≤j≤m-1},

其他情况

匹配时取移动距离为：dist=max{dist1(j),dist2}。文献［4］证明算法需要的预处理时间为O(m+σ)，最坏运行时间为O，即扫描部分运行时间为O。在大字母表(相对于模式长度)情况下，BM算法非常快，实际比较次数只有目标串长度的20%~30%。

1.4 RK算法

Karp和Rabin在1981年提出来的RK算法［5］利用了Hash方法和素数理论。

RK算法的思想是：首先定义一个Hash函数，用该函数计算出模式串P的Hash函数值，再计算出目标串T中所有长度为m的子串的Hash函数值，然后用相应的Hash函数值进行比较。当出现Hash冲突时，再进行相应字符串的比较，当构造Hash函数的素数选择得合理，Hash冲突出现的概率就可以做到很小。

Hash函数的构造及相应Hash值的计算如下：

设c∈∑，构造Hash函数：

h(asc(c))=asc(c) mod q

式中：q∈［1…n2m］且为素数；asc(c)为任意字符c的ASCII码。

映射模式串P为Hash函数值x(0≤x≤q-1)的方法为：

令：

X=h(asc(P［1］)cm-1+asc(P［2］)cm-2+…

+asc(P［m-1］)c1+asc(P［m］))

同理，映射目标串T中长度为m的子串t璱=T［i…i+m-1］为Hash函数值t璱的方法是：

令：

t璱=h(asc(T［i］)cm-1+asc(T［i+1］)cm-2+…+asc(T［i+m-2］)c1+asc(T［i+m-1］))

用i+1替换i，并带入Hash函数，从而得递推公式：

t璱+1=h(asc(T［i+1］)cm-1+asc(T［i+2］)cm-2+

…+asc(T［i+m-1］)c1+asc(T［i+m］))

=(c(t璱-asc(T［i］)cm-1) +asc(T［i+m］)) mod q

式中，i=1，2，…，n-m。

根据上述公式可把目标串T中每个长度为m的子串的Hash函数值计算出来。

如果Hash冲突不发生，即不再需要额外的字符匹配，RK算法的时间复杂度是O(m+n)；若考虑字符匹配，则RK算法的时间复杂度是O(mn)。在实际应用中，可设法取适当大的素数q，使得mod q仍可执行并且Hash冲突又几乎不发生，从而使得KR算法的实际运行时间只需O(m+n)。

RK算法采用了与KMP和BF算法不同的思路，尽量减少字符之间的比较次数，从而达到提高效率的目的。

1.5 单模式匹配算法改进情况简介

研究人员对单模式匹配算法提出了不少变形和改进算法。

在文献［6］中黄占友等人提出的KMP算法的改进对特殊的字符串能够提高效率；文献［1］ 中庞善臣等人对BM算法的改进有效地减少了最坏情况下的比较次数，同时方便在二位匹配和不精确匹配中推广；文献［7］中贺龙涛等人通过将好后缀与坏字符两种情况合并进行处理对BM进行改进。采用该思想的同类改进算法还有很多，如：发表于2006年12月32卷23期《计算机工程》上渠瑜等人的对《对BM模式匹配算法的一个改进》，限于篇幅，不一一列举。在文献［8］中张国平等人对BM算法的改进是通过定义一个距离函数来求出每次匹配失败时的最大可能移动距离；文献［9］ 蔡晓妍等人对BM算法的改进则是结合了BM算法和TunedBM算法的优点，采用TunedBM的坏字符和BM的好后缀对模式进行预处理，然后根据当前尝试中匹配失败字符的位置信息，决定查找好后缀跳跃表还是坏字符跳跃表以期获得更大的跳跃距离。文献［3］张立航等人对RK算法的改进是通过引入2次Hash运算进行的。通过两次Hash运算使出现Hash冲突的情况大为减少。

2 多模式匹配算法

2.1 入侵检测中采用多模式匹配的必要性

与单模式匹配算法相比，多模式匹配算法的优势在于一趟遍历可以对多个模式进行匹配，从而大大提高了匹配效率。对于单模式匹配算法，如果要匹配多个模式，那么有几个模式就需要几趟遍历。当然多模式匹配算法也适用于单模式的情况。在入侵检测系统中，一条入侵特征可能匹配或部分匹配很多条规则，如果采用单模式匹配，在匹配每条规则时都需要重新运行匹配算法，效率很低。然而，日益增多的网络攻击使得入侵检测的规则数目仍在不断增长，例如，Snort1.8.3的规则为1 270条，snort2.0的规则为2 300多条，到Snort 2.6.1则增加到3 600多条规则，因此，单纯提高单模式匹配算法的效率，很难使入侵检测系统满足越来越大的网络数据吞吐量和日益增加的攻击。

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

下面介绍其中2种经典的多模式匹配算法。

2.2 AC算法

AC算法［10］1975年产生于贝尔实验室，最早用于图书馆的书目查询程序中。该算法基于有限状态自动机(FSA),在进行匹配之前先对模式串集合SP进行预处理，形成模式树(树形FSA)，然后只需对目标串T扫描一次就可以找出所有与其匹配的模式串P。模式树K的构成如下：

K的每一条边e上都用1个字符作为标签；

与同一节点相连的边的标签均不同；

每1个模式p∈SP都存在1个节点v，使得L(v)=p，其中L(v)表示从根节点到v所经过的所有边上的标签的拼接；

每一个叶子节点v，都存在一个模式p∈SP使得以L(v′)=p。

例如：对于模式集SP={he,she,his,hers}模式树如图3所示，其中圆圈表示节点，双圈是根节点，边上的字符就是该边的标签，填充点圈的标签就是各个模式。

图3 模式树

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

由模式树扩展所得的AC自动机M是1个6元组：

M=(Q,Σ,g,f,q0,F )

其中：

(1) Q是有限状态集(模式树上的节点)；

(2) Σ是有穷的输入字符表(数据包中可能出现的所有字符)；

(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.3 AC－BM算法

对多模式串的匹配而言，虽然AC算法比BM算法高效得多，但AC算法必须逐一查看目标串的每个字符，即必须按顺序输入，不能实现跳跃，而BM算法则能够利用“右滑”跳过目标串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。许多人据此给出了各种改进的算法。Commentz－Walter最先将BM算法和AC算法结合在一起给出了Commentz－Walter算法；Baeza－Yates结合BMP算法和AC算法也给出了多模式匹配改进算法。

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

该算法的思想是：首先把要查找的多个模式构成一个关键字树，把相同的前缀作为树的根节点。模式树从目标串的右端向左移动，一旦模式树确定在适当的位置，字符比较从左向右开始进行。模式树移动时同时使用坏字符移动和好前缀移动。坏字符移动的策略为:如果出现不匹配的情况，移动模式树，使得树中其他模式的能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上，如果在当前的深度上，目标字符没有出现在任何模式中，则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为：将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置，或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在模式树的移动过程中，必须确保模式树的偏移量不能大于树中最短的模式长度。

2.4 AC，AC－BM算法改进情况简介

文献［10］中卢汪节等人针对AC算法在构造状态机时空间冗余较大的情况，对状态机各结点进行压缩存储，使空间性能和时间性能都有提高；文献［11］中万国根等人对AC－BM算法的改进借鉴了BMH算法的思想，取消了原算法的好前缀跳转，优化了坏字符跳转，并修改了skip的计算方法，对大字符集的情况在平均情况下具有更优的性能；文献［12］对AC－BM的改进则是通过预处理思想实现的，在进行AC-BM匹配之前首先扫描首和(或)尾字符，确定其位置，再到相应位置进行匹配，相当于把目标串按模式串首、尾字符分成数段，每段进行比较，段间不含首字符的就直接跳过，不用比较，从而提高效率。

3 算法的实际执行效率

上述这些算法究竟哪种算法具有最好的执行效率呢?能不能仅通过时间复杂度来进行衡量呢？时间复杂度仅是一个度量的范围，表示受几个参数的影响，并不代表一个具体的值，还需要在具体的环境中进行测试。

文献［13］测试了包括上述算法在内的多种单模式和多模式匹配算法的性能。测试平台为：硬件：CPU Intel Xeon 3.46 GHz X 2，内存2 GB DDR，硬盘200 GB SCSI；软件：Windows 2003 Server,Intel IXA SDK4.1。单模式匹配测试的规则集，使用随机生成的8，16，32，48，128位具有代表意义的规则，可以对应端口、IP地址，MAC地址、IPv6地址等，对多模式匹配测试采用Snort系统2.4.3规则集。

单模式匹配算法主要测试模式长度与匹配时间、占用空间及预处理时间的变化关系。测试结果表明：各算法的测试指标在规则长度增长的情况下均呈递增趋势，但BM算法的增长速度最为缓慢，在不太在意存储空间的情况下，BM可以作为优先考虑的算法，同时对IPV6地址也更为合适。

多模式匹配算法的测试项目为规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系。测试结果表明AC－BM算法在上述3项测试中取得了很好的性能平衡。这也是新

版的Snort系统中选用AC－BM算法的重要原因。

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

常用的模式匹配算法所采用的思想主要有基于字符比较、基于自动机、基于hash查找、基于位逻辑运算和基于Tries树型机构搜索。鉴于目前网络的实际状况，多模式匹配算法更加适合于基于模式匹配的入侵检测系统。这里认为应该从下面3个方面着手：一是继续研究和改进精确的模式匹配，将快速的单模式匹配算法和多模式匹配算法相结合，充分借鉴同类算法的先进思想，如：引入Hash函数、引入自动机、对字符串分块等来不断提高多模式匹配算法的性能；二是尝试采用模糊匹配的策略，国外对此已经开始进行相应的研究；三是对网络数据包和入侵特征进行研究，总结出这两类字符串特点，有针对性地对这两类字符串的匹配问题进行研究。

5 结 语

网络带宽的不断增加、日益严重的网络安全状况要求必须尽快提高网络入侵检测系统的性能。虽然入侵检测系统可以采用很多技术，并且这些技术也在不断的研究和发展中，但是目前主流的实用的入侵检测技术仍然是基于模式匹配的。因此如何提高模式匹配的效率成为研究入侵检测系统的一个关键所在。在此对已有的经典模式匹配算法进行了系统综述，并对入侵检测系统中模式匹配算法的未来研究方向给出了观点。

参考文献

［1］庞善臣,王淑栋,蒋昌俊.BM串匹配的一个改进算法［J］.计算机应用,2004,12(12):11－13.

［2］Boyer R S,Moore J S.A Fast String Searching Algorithm ［J］.Communications of ACM,1977,20(10):762－772.

［3］张立航,潘正运,刘海峰.基于改进的KR算法在网闸中的实现［J］.微计算机信息(管控一体化),2008(24):137－138.

［4］Johnson T,Newman－Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks ［J］.Journal of Parallel and Distributed Computing,1996,32(1):74－89.

［5］Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort ［EB/OL］.http://www.silicondefense.com/sotfware/acbm/speed－of－snort－03－16－2001.padf,2003.

［6］黄占友,刘悦.对KMP串匹配算法的改进［A］.第四次全国便携计算机学术交流会论文集［C］.北京:科学出版社,1997.

［7］贺龙涛,方滨兴,胡铭曾.对BM串匹配算法的一个改进［J］.计算机应用,2003,23(3):6－8.

［8］张国平,徐汶东.字符串模式匹配算法的改进［J］.计算机工程与设计,2007,28(20):4 881－4 884.

［9］蔡晓妍,戴冠中,杨黎斌.一种快速的单模式匹配算法［J］.计算机应用研究,2008,25(1):45－46,81.

［10］卢汪节,鞠时光.入侵检测系统中一种改进的AC算法［J］.计算机工程与应用,2006(15):146－148.

［11］万国根,秦志光.改进的AC－BM字符串匹配算法［J］.电子科技大学学报,2006,35(4):531－533.

［12］周四伟,蔡勇.AC－BM算法的改进及其在入侵检测中的应用［J］.微计算机应用,2007,28(1):27－31.

［13］王琢,赵永哲,姜占华.网络处理模式匹配算法研究［J］.计算机应用研究,2007,24(12):310－312.

作者简介

冉占军 男，1977年出生，陕西西安人，讲师，硕士研究生。主要研究方向为算法、网络安全。

姚全珠 男，1960年出生，博士，教授。主要研究方向为算法、数据库、网络安全。

王晓峰 女，1966年出生，博士，副教授。主要研究方向为信息安全。

邹又姣 女，1975年出生，硕士，讲师。主要研究方向为信息安全。