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

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

0 引 言
随着网络技术的发展，各种基于网络的应用层出不穷。面对日益突出的网络安全问题，仅靠传统的被动防御已经不能满足要求，能够主动检测并预防的入侵检测系统应运而生。
根据采用的分析方法，入侵检测分为误用检测和异常检测。误用检测是指：根据己知的攻击方法，预先定义入侵特征，通过判断这此特征是否出现来完成检测任务。异常检测是指：根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数人侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有：模式匹配、专家系统、状态转移等，其中模式匹配原理简单，可扩展性好，而且最为常用。据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。由此可见，模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高，入侵检测系统需要处理的数据量越来越大，如果模式匹配算法来不及处理这些实时的大量的数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中很可能就包含有入侵信息，从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法，包括单模式匹配算法和多模式匹配算法，通过对它们进行剖析和实际测试，提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。

1 单模式匹配算法
1．1 相关定义
模式匹配：是指在给定长度为n的目标串T=T1T2…Tn中查找长度为m的模式串P=P1P2…Pm的首次出现或多次出现的过程。这里Ti(1≤i≤n)，Pj(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+2)时间内解决。D．E．Knuth，V．R．Pratt和T．H．Morris在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1个字符比较不等便需要回溯的缺点，使算法的效率得到了大幅度提高，时间复杂度达到最理想的O(m+n)，空间复杂度是O(m)。
KMP算法的基本思想是：若某趟匹配过程中Ti和Pj不匹配，而前j一1个字符已经匹配。此时只需右移模式串P，目标串T不动，即指针i不回溯，让Pk与Ti继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串T无关，因此k可以通过下面的next函数事先确定。
定义next[j]函数为：

1．3 BM算法
相对于BF算法，KMP算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位，但由上述next函数可知：右滑的最大距离不会超过1趟匹配操作所进了的比较次数j，原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发，R．S．Boyer和J．S．Moore提出一种新的快速字符串匹配算法一BM算法。
BM算法基本思想是：开始时将目标串T与模式串P左对齐，自右至左逐个字符进行比较(即首先比较Pm与Tm)；当某趟比较时Ti与模式串的对应字符不匹配，则把模式串右滑d(x)一段距离，执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离：
(1)好后缀移动。其又分为2种情况：
①P已比较部分P[j+1…m]与其中间的某一子串P[j一s+l…m―s]相同，P右移s位。如图1所示。

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

取满