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

1、入侵检测系统中模式匹配算法的研究摘要  入侵检测是网络安全的最后一道防线，模式匹配算法是基于特征匹配的入侵检测系统中的核心算法，模式匹配的效率决定这类入侵检测系统的性能。本文对入侵检测系统中的模式匹配算法进行了综述，包括经典的单模式匹配算法-KMP算法、BM算法、RK算法和多模式匹配AC算法。对各种算法的性能进行了分析。最后提出了改进模式匹配算法效率的研究方向。关键词: 网络安全；入侵检测；模式匹配；多模式匹配1 引言    随着Internet应用的普及，网络安全问题也日益突出。入侵是指试图破坏资源的完整性、可用性和保密性的活动的集合。作为防火墙之后网

2、络安全的最后一道防线，入侵检测系统（IDS）是指检测上述行为的活动，识别出未经授权或越权访问系统资源的行为的软硬件系统。由于入侵检测系统可以在一定程度上主动预防和检测出来自系统内、外部的入侵，并作出适当响应，动态改变网络的安全性，因此入侵检测的研究正成为网络安全研究的热点。    根据采用的分析技术入侵检测分为误用检测和异常检测 1。误用检测根据已知的攻击方法，预先定义入侵模式，通过判断这些模式是否出现来完成检测任务。异常检测是指根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均属误用检测。

3、误用检测中使用的检测技术主要有：模式匹配、专家系统、状态转移等，而其中因为模式匹配原理简单、可扩展性好而最为常用，例如著名开放源码的入侵检测系统Snort就是基于模式匹配的。    由此可见，模式匹配算法的性能直接影响入侵检测系统的检测效率。在高速网络环境，如果模式匹配算法来不及处理大量的实时网络数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中就可能包含入侵信息。本文以下部分介绍几种著名的模式匹配算法，包括单模式匹配算法和多模式匹配算法，为设计入侵检测系统选择模式匹配算法提供指导。2 单模式匹配算法    模式匹配是指在给定长度为

4、n的文本串T=T1T2Tn中查找长度为m的模式串P=P1P2Pm的第一次出现的过程。这里Ti（1in），Pj（1jm）（字符集），若在T中能找到P的出现，则称匹配成功，否则称匹配失败。    一次只能在文本串中对一个模式串进行匹配的算法，称为单模式匹配算法，可同时对多个模式串进行匹配的算法称多模式匹配算法。    平凡的模式匹配算法（BF算法）中，一趟匹配失败后，T只后移一个字符，所以算法简单，但效率低。高效的模式匹配算法都是设法增大不匹配时T的后移量，本节下面介绍3种经典的快速单模式匹配算法，第3节介绍著名的多模式匹配算法AC算法。

5、2.1 KMP算法2.2 BM算法     2) 好后缀规则(Good Suffix)    坏字符规则没有考虑已经取得的部分匹配的情况，而KMP算法却考虑了。该规则将KMP算法和BM算法的思想结合起来，在不丢失真解的前提下确定一个新的移动距离delta2，该函数与样本P有关。具体分以下两种情况，如图1所示。l ·P中间的某一子串Pj-s+1.m-s与已比较部分Pj+1.m相同，可让P右移s位。l ·P已比较部分Pj+1.m的后缀Ps+1.m与P的前缀P1.m-s相同，可让P

6、右移s位。满足上面情况的s的最小值为最佳右移距离。delta2的定义如下：delta2（j）=mins|(Pj+1.m=Pj-s+1.m-s)&&(PjPj-s)(j>s),Ps+1.m=P1.m-s(js)     在匹配过程中，取delta1和delta2中的大者。BM算法的最坏时间复杂度为O(mn)，但实际比较次数只有文本串长度的20%30%。2.3 RK算法3 多模式匹配的AC算法3.1 入侵检测中多模式匹配的必要性3.2 AC算法    AC算法5是基于FSA（有穷状态自动机）的，在进行匹配之

7、前先对模式串集合Sp进行预处理，形成树型FSA，然后只需对文本串T扫描一次就可以找出与其匹配的所有模式串。    预处理生成3个函数：goto（转移）函数，failure（失效）函数和output（输出）函数。    设U=0，1，2为状态集合，转移函数g:(U,Sp)U为一映射，其建立过程为：逐个取出Sp中模式串的每个字符，从状态0出发，由当前状态和新取出的字符决定下一状态。如果有从当前状态出发并标注该字符的矢线，则将矢线所指的状态赋为当前状态，否则，添加一个标号比已有状态标号大1的新状态，并用一条矢线从当前状态指向新加入的状态，并

8、将新加入的状态赋为当前状态。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

9、（即存在字符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)

10、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算法总时间复杂

11、度是O(M+n)，其中M为所有模式串的长度总和。     对多模式串的匹配而言，虽然AC算法比BM算法高效得多。但AC算法必须逐一地查看文本串的每个字符，而BM算法能够利用跳转表跃过文本串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。Commentz-Walter首先结合了BM算法和AC算法的特征，提出了一种解决多模式匹配问题的算法。实践表明Commentz-Walter算法要比AC算法快很多。Baeza-Yates也给出了一种组合BMP算法和AC算法的多模式匹配算法。AC-BM算法根据一种前

12、缀关键字树来计算劣势移动表和优势跳转表，从而可以跳跃式地并行搜索模式集合。4 结束语    随着网络应用的发展和网络带宽的不断增加，必须加快网络入侵检测系统的处理性能，否则，网络入侵检测系统只能形同虚设，由于大量的网络数据来不及处理而使入侵漏报。而目前实用的网络入侵检测系统多是基于特征匹配的系统，这类系统中的关键运算是模式匹配运算，因此提高模式匹配的效率是提高这类系统检测能力的关键所在。本文对已有的模式匹配算法进行了综述，主要包括3中重要的单模式匹配算法和AC多模式匹配算法。将快速单模式匹配算法与多模式匹配算法相结合是今后改进模式匹配算法努力的方向。参考文献1 H

13、ochberg J,Jackson K, Stallings C,et al.NADIR:An Automated System for Detecting Network Intrusion and Misuse.Computers and Security, 1993,12(3):235-2482 Knuth DE , Morris JH , Pratt VR. Fast Pattern Matching in StringsJ , SIAM Journal on Computer , 1977 , 6 (2) :323-350.3 Boyer RS , Moore JS. A Fast String Searching AlgorithmJ . Communications of the ACM ,1977 ,20(