摘要 入侵检测是网络安全的最后一道防线，模式匹配算法是基于特征匹配的入侵检测系统中的核心算法，模式匹配的效率决定这类入侵检测系统的性能。本文对入侵检测系统中的模式匹配算法进行了综述，包括经典的单模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法。对各种算法的性能进行了分析。最后提出了改进模式匹配算法效率的研究方向。
关键词: 网络安全；入侵检测；模式匹配；多模式匹配
1 引言
随着Internet应用的普及，网络安全问题也日益突出。入侵是指试图破坏资源的完整性、可用性和保密性的活动的集合。作为防火墙之后网络安全的最后一道防线，入侵检测系统（IDS）是指检测上述行为的活动，识别出未经授权或越权访问系统资源的行为的软硬件系统。由于入侵检测系统可以在一定程度上主动预防和检测出来自系统内、外部的入侵，并作出适当响应，动态改变网络的安全性，因此入侵检测的研究正成为网络安全研究的热点。
根据采用的分析技术入侵检测分为误用检测和异常检测 [1]。误用检测根据已知的攻击方法，预先定义入侵模式，通过判断这些模式是否出现来完成检测任务。异常检测是指根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均属误用检测。误用检测中使用的检测技术主要有：模式匹配、专家系统、状态转移等，而其中因为模式匹配原理简单、可扩展性好而最为常用，例如著名开放源码的入侵检测系统Snort就是基于模式匹配的。
由此可见，模式匹配算法的性能直接影响入侵检测系统的检测效率。在高速网络环境，如果模式匹配算法来不及处理大量的实时网络数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中就可能包含入侵信息。本文以下部分介绍几种著名的模式匹配算法，包括单模式匹配算法和多模式匹配算法，为设计入侵检测系统选择模式匹配算法提供指导。
2 单模式匹配算法
模式匹配是指在给定长度为n的文本串T=T[1]T[2]…T[n]中查找长度为m的模式串P=P[1]P[2]…P[m]的第一次出现的过程。这里T[i]（1≤i≤n），P[j]（1≤j≤m）∈∑（字符集），若在T中能找到P的出现，则称匹配成功，否则称匹配失败。
一次只能在文本串中对一个模式串进行匹配的算法，称为单模式匹配算法，可同时对多个模式串进行匹配的算法称多模式匹配算法。
平凡的模式匹配算法（BF算法）中，一趟匹配失败后，T只后移一个字符，所以算法简单，但效率低。高效的模式匹配算法都是设法增大不匹配时T的后移量，本节下面介绍3种经典的快速单模式匹配算法，第3节介绍著名的多模式匹配算法—AC算法。
2.1 KMP算法
D.Knuth、J.Morris和V.Pratt提出一种快速模式匹配算法，称为KMP算法[2]。
KMP算法的基本思想是：若某趟匹配过程中T[i]和P[j]不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，文本串T不动，即指针i不回溯，让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串S无关，因此K可以事先确定。若定义函数next(j)=K，则next函数的定义应为：
next(j)=Max{k| P[1..K-1]=P[j-k+1.. j-1] }
KMP算法的时间复杂度是O(m+n)，空间复杂度是O(m)，对BF算法进行了很大的改进。
2.2 BM算法
KMP算法虽然在不匹配时能使模式串右移若干位，但右移的距离不可能超过一趟匹配操作所进行的比较次数j，存在这一问题的根本原因是KMP算法的匹配操作是从左向右进行的。在KMP算法的启发下，R.Boyer和J.Moore提出了一种新的快速字符串匹配算法，即BM算法[3]。
BM算法的基本思想是从右向左进行比较。开始时仍是P的最左边与T的最左边对齐，但首先进行Pm与Tm的比较。当某趟比较中出现不匹配时，BM算法采用两条启发性规则计算模式串右移的距离，即坏字符规则和好后缀规则。
1) 坏字符规则（Bad Character）
P中的某个字符与T中的某个字符不相同时使用坏字符规则右移模式串P，P右移的距离可以通过delta1函数计算出来。delta1函数的定义如下：
2) 好后缀规则(Good Suffix)
坏字符规则没有考虑已经取得的部分匹配的情况，而KMP算法却考虑了。该规则将KMP算法和BM算法的思想结合起来，在不丢失真解的前提下确定一个新的移动距离delta2，该函数与样本P有关。具体分以下两种情况，如图1所示。
·P中间的某一子串P[j-s+1..m-s]与已比较部分P[j+1..m]相同，可让P右移s位。
·P已比较部分P[j+1..m]的后缀P[s+1..m]与P的前缀P[1..m-s]相同，可让P右移s位。
满足上面情况的s的最小值为最佳右移距离。delta2的定义如下：
delta2（j）=min{s|(P[j+1..m]=P[j-s+1..m-s])&&(P[j]≠P[j-s])(j>s),P[s+1..m]=P[1..m-s](j≤s)}
在匹配过程中，取delta1和delta2中的大者。BM算法的最坏时间复杂度为O(m•n)，但实际比较次数只有文本串长度的20%～30%。
2.3 RK算法
RK算法[4]是Turing奖获得者R.M.Karp和M.O.Rabin在1981年提出来的，该算法采用了与KMP算法和BM算法完全不同的方法。该算法利用Hash方法和素数理论，首先定义一个Hash函数，然后将模式串P和文本串T中长度为m的子串利用Hash函数转换成数值。显然只需比较那些与模式串具有相同Hash函数值的子串，从而提高了效率。当然因为Hash冲突的存在，还要进一步进行字符串比较，但只要选择适当的素数Hash冲突的概率就会很小。
设c=|∑|，Hash函数为h(r)=r mod q，这里q是在区间[1..n2m]中随机选取的适当大的素数，asc(c)为任意字符c的Ascii码。将模式串P映射成整数x（0≤x≤q-1）的方法为：
p=h(asc(P[1])cm-1+ asc(P[2])cm-2+…+asc(P[m-1])c1+asc(P[m]))
同理，将文本串T中长度为m的子串ti=T[i..i+m-1] 映射成整数ti的方法为：
ti=h(asc(T[i])cm-1+ asc(T[i+1])cm-2+…+asc(T[i+m-2])c1+asc(T[i+m-1]))
为了快速计算T中每个长度为m的子串的Hash函数值，可以推导出递推公式：
ti+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(ti-asc(T[i])cm-1) +asc(T[i+m])) mod q
其中i=1..n-m，根据这一递推公式可很容易地计算出T中每个长度为m的子串的Hash函数值。
如果不考虑字符匹配所需时间，RK算法的时间复杂度是O(n+m)，若考虑字符匹配所需时间，则RK算法的时间应是O(m•n)。但实际应用中，可设法取q适当大，使得在计算机中求余仍可执行而Hash冲突又几乎不可能发生，从而使得KR算法的实际运行时间只需O(m+n)。
3 多模式匹配的AC算法
3.1 入侵检测中多模式匹配的必要性
在网络入侵检测系统中，一个网络数据包的内容可能匹配或部分匹配很多条规则，因此在匹配每条规则时都会重新运行匹配算法，导致效率降低。如snort的web-coldfusion.rules规则就包含16条规则，而这16条规则中都包含/cfdocs/。但如果当前包中没有/cfdocs/，则与这16条规则的匹配完全不必进行，但根据前面单模式匹配的思想这16次匹配又都必须进行。随着攻击手段的增加，规则集中的规则必然成倍增加，如snort 1.6.3的规则为854条，而snort 1.8.3的规则为1270条。因此，单纯提高单模式匹配算法的效率，很难满足未来入侵检测系统的要求。多模式匹配算法只需对文本串扫描一次就可以找出模式串集合中与其匹配的全部模式串，从而大大提高匹配效率。下面介绍最经典的多模式匹配算法—AC算法。
3.2 AC算法
AC算法[5]是基于FSA（有穷状态自动机）的，在进行匹配之前先对模式串集合Sp进行预处理，形成树型FSA，然后只需对文本串T扫描一次就可以找出与其匹配的所有模式串。
预处理生成3个函数：goto（转移）函数，failure（失效）函数和output（输出）函数。
设U={0，1，2…}为状态集合，转移函数g:(U,Sp)→U为一映射，其建立过程为：逐个取出Sp中模式串的每个字符，从状态0出发，由当前状态和新取出的字符决定下一状态。如果有从当前状态出发并标注该字符的矢线，则将矢线所指的状态赋为当前状态，否则，添加一个标号比已有状态标号大1的新状态，并用一条矢线从当前状态指向新加入的状态，并将新加入的状态赋为当前状态。Sp中的所有模式串处理完后，再画一条从0状态到0状态的自返线，标注的字符为不能从0开始的字符集。例如，Sp={he,she,his,hers}的goto函数如图2所示。
图2 {he,she,his,hers}的goto函数图
失效函数f用来指明当某个模式与文本匹配不成功时，应处理的下一状态。f的构造方法为：所有第一层状态的失效函数为0，如f(1)=f(3)=0；对于非第一层状态s，若其父状态为r（即存在字符a,使g(r,a)=s），则f(s)=g(f(s*),a)，其中状态s*为追溯s的祖先状态得到的第一个使g(f(s*),a)存在的状态。如f(4)=g(f(3),h)=g(0,h)=1，f(5)=g(f(4),e)=g(1,e)=2。
输出函数output的作用是在匹配过程中输出已经匹配的模式串。output的构造分两步，第一步是在构造转移函数g时，每处理完一个模式串，则将该模式串加入到当前状态s的输出函数中，如output(2)={he},output(5)={she}。第二步是构造失效函数f时，若f(s)=s’,则output(s)=output(s)∪output(s’),如output(5)=output(5)∪output(2)={she,he}。
AC算法的匹配过程如下：从状态0出发，每取出文本串中的一个字符，利用g和f函数进入下一状态。当某个状态的output函数不为空时输出其值，表示在文本串中找到该模式串。
AC算法模式匹配的时间复杂度是O(n)，而且与模式集中模式串的个数和每个模式串的长度无关。无论模式串P是否出现在T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O(n)。包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式串的长度总和。
对多模式串的匹配而言，虽然AC算法比BM算法高效得多。但AC算法必须逐一地查看文本串的每个字符，而BM算法能够利用跳转表跃过文本串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。Commentz-Walter首先结合了BM算法和AC算法的特征，提出了一种解决多模式匹配问题的算法。实践表明Commentz-Walter算法要比AC算法快很多。Baeza-Yates也给出了一种组合BMP算法和AC算法的多模式匹配算法。AC-BM算法根据一种前缀关键字树来计算劣势移动表和优势跳转表，从而可以跳跃式地并行搜索模式集合。
4 结束语
随着网络应用的发展和网络带宽的不断增加，必须加快网络入侵检测系统的处理性能，否则，网络入侵检测系统只能形同虚设，由于大量的网络数据来不及处理而使入侵漏报。而目前实用的网络入侵检测系统多是基于特征匹配的系统，这类系统中的关键运算是模式匹配运算，因此提高模式匹配的效率是提高这类系统检测能力的关键所在。本文对已有的模式匹配算法进行了综述，主要包括3中重要的单模式匹配算法和AC多模式匹配算法。将快速单模式匹配算法与多模式匹配算法相结合是今后改进模式匹配算法努力的方向。
参考文献
[1] Hochberg J,Jackson K, Stallings C,et al.NADIR:An Automated System for Detecting Network Intrusion and Misuse.Computers and Security, 1993,12(3):235-248
[2] Knuth DE , Morris JH , Pratt VR. Fast Pattern Matching in Strings[J ] , SIAM Journal on Computer , 1977 , 6 (2) :323-350.
[3] Boyer RS , Moore JS. A Fast String Searching Algorithm[J ] . Communications of the ACM ,1977 ,20(10) :762-772.
[4] Crochemorc M,Rytter W.Text Algorithms.Oxford University Press.1994
[5] Aho AV,Corasick MJ.Efficient String Matching:An Aid to Bibliographic Search. Communications of the ACM ,1975 ,18(6) :333-340.
|
