一种改进的KMP入侵检测的模式匹配算法

赵森严，黄 伟，李阳铭

一种改进的KMP入侵检测的模式匹配算法

*赵森严1，黄 伟1，李阳铭2

（1.安徽工程大学计算机与信息学院，安徽，芜湖 241000; 2.中科院合肥智能机械研究所，安徽，合肥 230031）

提出了一种基于KMP的模式匹配算法，给出了具体的实现方法。在不丢失匹配项的前提下，增大next函数的值，使得模式串向右尽可能得滑动更远的一段距离，忽略不必要的比较。通过实验证明，该方法与传统的方法相比能有效地加快匹配的速度，提高入侵检测的效率。

KMP算法；模式匹配；next函数；入侵检测

随着互联网的飞速发展和广泛的应用，网络安全问题日益突出。网络入侵检测系统已经成为提高网络安全性的重要技术，是网络安全领域中研究的一个热点。在很多的商业入侵检测产品中，都采用了模式匹配算法。模式匹配就是将收集到的信息与已知的网络入侵和系统误用模式数据库进行比较，从而发现违背安全策略的行为，它具有分析速度快、误报率小等优点。据统计，花费在模式匹配上的时间占整个入侵检测系统总处理时间的30%左右[1]。因此，模式匹配成为影响网络入侵检测系统性能的主要因素，而模式匹配的实质就是字符串匹配。本文在分析传统的KMP检测算法的基础上提出一种改进的匹配算法，该算法增大了next函数的值，使得模式串向右尽可能得滑动更远的一段距离，忽略不必要的比较，提高了模式匹配的速度。

1 KMP算法

KMP算法是模式匹配的一种改进算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。每当一趟匹配过程中出现字符比较不等式，不需要回溯指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离，继续进行比较[2]。

此算法首先对模式串预处理，然后将主串与模式串中对应的各个字符进行比较，如果发现不匹配，即Ti≠Pj，1≤i≤n，1≤j≤m时，则下一次比较应和Pnext[j]对齐比较。

在KMP算法中模式串的next函数，其定义如下[2]：

由此定义，通过递推的方法可以得出next函数值，例如：模式串为”abaabcac”，其结果如表一所示：

表1 模式串abaabcac的next[j]值

例如：主串acabaabaabcacaabc，模式abaabcac，以下是利用模式next函数进行匹配的过程：

图1利用模式的next函数进行匹配过程

通过图1可以看出，滑动存在冗余，如第一次滑动过程中，当T2≠P2时，模式向右滑动1个距离，使得P1与T2对齐，它们明显是不匹配的，后面的匹配过程中也出现了这种情况。

2 改进策略

由于在匹配过程中出现许多不必要的比较，所以，本文提出一种字符串匹配新的方法：

设主串T：”T1T2…Tn”，模式串P：” P1P2…Pn”，(0

首先创建一个Inext数组，Inext数组中记录当主串与模式不匹配时，模式应该向右滑动Inext[j]的距离。Inext[j](1≤j≤m)的值是这样确定的：具体步骤如下：

① Pj与”Pj+1…Pm”依次匹配(0next[j]，则Inext[j]=k-j，否则Inext[j]=next[j]；

②如果Pj与”Pj+1…Pm”没有匹配的项，则依次匹配” Pj-1…P1”，当Pj遇到第一个相同字符Pi(1≤i≤j-1)后，则Inext[j]= Inext[i]；

③如果Pj与” Pj-1…P1”没有匹配项，则Inext[j]=Max(Inext[1],…,Inext[j-1])。

Inext[j]定义如下：

由此定义，可以得出Inext函数值，例如：模式串为”abaabcac”，其结果如表二所示：

表2 模式串abaabcac的Inext[j]值

图2 算法流程图

改进后的匹配算法具体步骤如下：

步骤1：匹配主串与模式串，如果模式第j(1≤j<≤m)个字符失配，即Ti≠Pj(0

步骤2：匹配主串与模式串，没有失配，则匹配成功；如果主串未结束，子串向右滑动m，转步骤1，否则转步骤4；

步骤3：如果不同配，则模式向右滑动Inext[j]=Max(Inext[1], …,Inext[j-1])个距离，转步骤1；

步骤4：结束。

算法流程图如图3。

例如：主串acabaabaabcacaabc，模式abaabcac，以下是利用模式Inext函数进行匹配的过程：

图3 利用模式的Inext函数进行匹配过程

3 测试实验及结果

本文随机选取了3000字左右的文本T, 模式串为该文本中长度不同的字符序列P{ P1, P2, P3, P4, P5, P6 ,P7}7个字符串，长度分别为11，27，43，71，93，112，136 进行实验，分别测试 KMP和改进的算法在查询过程中的匹配次数，实验结果如图4所示：

图4 模式串数目不同时的算法性能分析

从图4中可以看出，在同一个模式串 P的比较过程中，改进后的算法比较次数远远少于KMP，因此，改进后的算法在字符串匹配算法总体性能是优越的。

本文采用读取数据包的方法进行测试统计，即在数据包过滤中使用KMP算法以及改进的后的算法。图5所示的就是在不同数据包大小的情况下，两种种算法所需要时间的比较。

图5 每个数据包花费的检测时间

如图5所示，改进的KMP算法在匹配时间上明显缩短，并且随着数据包的增大，其优势更加明显，可以明显提高包过滤效率。

4 结论

本文在KMP算法的基础上提出一种新的模式匹配算法，扩大向右滑动的距离，减少多余的比较，进而提高匹配的效率。随着网络应用范围的扩大以及带宽增大的情况下，本文提出的方法能够提高网络入侵检测系统的处理性能。

[1] 韩忠秋,刘晓洁,李涛,等.一种入侵检测系统的模式匹配算法[J].计算机应用研究,2009, 26(8):51-54.

[2] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.

[3] 张莹,徐剑,常桂然,贾杰.Ad hoc网络中双向快速字符串匹配算法[J].计算机科学, 2010, 37(1):35-39.

[4] Boyer R S, Moore J S. A fast string searching algorithm [J].Communications of ACM, 1977, 20(10): 762-777.

[5] 董明明,巩青歌,张琦.入侵检测系统中模式匹配算法的改进[J].计算机应用与软件,2011, 28(5):43-48.

[6] 范洪博,姚念民.一种高速精确单模式串匹配算法[J].计算机研究与发展，2009，46(8): 1341-1348.

AN IMPROVED PATTERN MATCHING ALGORITHM OF INTRUSION DETECTION BASED ON KMP

*ZHAO Sen-yan1，HUANG Wei1，LI Yang-ming2

(1. School of Computer and Information, AnHui Polytechnic University, WuHu, Anhui 241000, China;(2. Department of automation, University of Science and Technology, HeFei, AnHui 230000, China;(3. Institute of Intelligent Machines, Chinese Academy of Science, HeFei, Anhui 230031, China)

We proposed a pattern matching algorithm based on KMP and given the specific implementation method.In the premise of not lost a match, we enlarged the value of next function which move pattern string to the right a longer distance as far as possible and ignore unnecessary comparison.Experimental shows that this method compared with the traditional method can accelerate the speed of matching effectively and improve the efficiency of intrusion detection.

KMP algorithm;pattern matching; next function; intrusion detection

TP309

A

10.3969/j.issn.1674-8085.2013.01.012

1674-8085(2013)01-0055-03

2012-06-18；

2012-12-06

国家自然科学基金青年基金项目(61105090)

*赵森严(1983-），男，安徽马鞍山人，助教，硕士，主要从事计算机网络与信息安全研究(E-mail: zsy19831104@163.com);

黄 伟(1981-），男，浙江余姚人，讲师，硕士，主要从事计算机网络研究(E-mail:yfworld@163.com);

李阳铭(1981-），男，辽宁阜新人，助理研究员，博士，主要从事模式识别研究(E-mail:ayun@lim.ac.cn).