趙森嚴，黃 偉，李陽銘

一種改進的KMP入侵檢測的模式匹配算法

*趙森嚴1，黃 偉1，李陽銘2

（1.安徽工程大學計算機與信息學院，安徽，蕪湖 241000; 2.中科院合肥智能機械研究所，安徽，合肥 230031）

提出了一種基于KMP的模式匹配算法，給出了具體的實現(xiàn)方法。在不丟失匹配項的前提下，增大next函數(shù)的值，使得模式串向右盡可能得滑動更遠的一段距離，忽略不必要的比較。通過實驗證明，該方法與傳統(tǒng)的方法相比能有效地加快匹配的速度，提高入侵檢測的效率。

KMP算法；模式匹配；next函數(shù)；入侵檢測

隨著互聯(lián)網(wǎng)的飛速發(fā)展和廣泛的應用，網(wǎng)絡安全問題日益突出。網(wǎng)絡入侵檢測系統(tǒng)已經成為提高網(wǎng)絡安全性的重要技術，是網(wǎng)絡安全領域中研究的一個熱點。在很多的商業(yè)入侵檢測產品中，都采用了模式匹配算法。模式匹配就是將收集到的信息與已知的網(wǎng)絡入侵和系統(tǒng)誤用模式數(shù)據(jù)庫進行比較，從而發(fā)現(xiàn)違背安全策略的行為，它具有分析速度快、誤報率小等優(yōu)點。據(jù)統(tǒng)計，花費在模式匹配上的時間占整個入侵檢測系統(tǒng)總處理時間的30%左右[1]。因此，模式匹配成為影響網(wǎng)絡入侵檢測系統(tǒng)性能的主要因素，而模式匹配的實質就是字符串匹配。本文在分析傳統(tǒng)的KMP檢測算法的基礎上提出一種改進的匹配算法，該算法增大了next函數(shù)的值，使得模式串向右盡可能得滑動更遠的一段距離，忽略不必要的比較，提高了模式匹配的速度。

1 KMP算法

KMP算法是模式匹配的一種改進算法。此算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作。每當一趟匹配過程中出現(xiàn)字符比較不等式，不需要回溯指針，而是利用已經得到的“部分匹配”結果將模式串向右“滑動”盡可能遠的一段距離，繼續(xù)進行比較[2]。

此算法首先對模式串預處理，然后將主串與模式串中對應的各個字符進行比較，如果發(fā)現(xiàn)不匹配，即Ti≠Pj，1≤i≤n，1≤j≤m時，則下一次比較應和Pnext[j]對齊比較。

在KMP算法中模式串的next函數(shù)，其定義如下[2]：

由此定義，通過遞推的方法可以得出next函數(shù)值，例如：模式串為”abaabcac”，其結果如表一所示：

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

例如：主串acabaabaabcacaabc，模式abaabcac，以下是利用模式next函數(shù)進行匹配的過程：

圖1利用模式的next函數(shù)進行匹配過程

通過圖1可以看出，滑動存在冗余，如第一次滑動過程中，當T2≠P2時，模式向右滑動1個距離，使得P1與T2對齊，它們明顯是不匹配的，后面的匹配過程中也出現(xiàn)了這種情況。

2 改進策略

由于在匹配過程中出現(xiàn)許多不必要的比較，所以，本文提出一種字符串匹配新的方法：

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

首先創(chuàng)建一個Inext數(shù)組，Inext數(shù)組中記錄當主串與模式不匹配時，模式應該向右滑動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函數(shù)值，例如：模式串為”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函數(shù)進行匹配的過程：

圖3 利用模式的Inext函數(shù)進行匹配過程

3 測試實驗及結果

本文隨機選取了3000字左右的文本T, 模式串為該文本中長度不同的字符序列P{ P1, P2, P3, P4, P5, P6 ,P7}7個字符串，長度分別為11，27，43，71，93，112，136 進行實驗，分別測試 KMP和改進的算法在查詢過程中的匹配次數(shù)，實驗結果如圖4所示：

圖4 模式串數(shù)目不同時的算法性能分析

從圖4中可以看出，在同一個模式串 P的比較過程中，改進后的算法比較次數(shù)遠遠少于KMP，因此，改進后的算法在字符串匹配算法總體性能是優(yōu)越的。

本文采用讀取數(shù)據(jù)包的方法進行測試統(tǒng)計，即在數(shù)據(jù)包過濾中使用KMP算法以及改進的后的算法。圖5所示的就是在不同數(shù)據(jù)包大小的情況下，兩種種算法所需要時間的比較。

圖5 每個數(shù)據(jù)包花費的檢測時間

如圖5所示，改進的KMP算法在匹配時間上明顯縮短，并且隨著數(shù)據(jù)包的增大，其優(yōu)勢更加明顯，可以明顯提高包過濾效率。

4 結論

本文在KMP算法的基礎上提出一種新的模式匹配算法，擴大向右滑動的距離，減少多余的比較，進而提高匹配的效率。隨著網(wǎng)絡應用范圍的擴大以及帶寬增大的情況下，本文提出的方法能夠提高網(wǎng)絡入侵檢測系統(tǒng)的處理性能。

[1] 韓忠秋,劉曉潔,李濤,等.一種入侵檢測系統(tǒng)的模式匹配算法[J].計算機應用研究,2009, 26(8):51-54.

[2] 嚴蔚敏,吳偉民.數(shù)據(jù)結構[M].北京:清華大學出版社,1997.

[3] 張瑩,徐劍,常桂然,賈杰.Ad hoc網(wǎng)絡中雙向快速字符串匹配算法[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] 董明明,鞏青歌,張琦.入侵檢測系統(tǒng)中模式匹配算法的改進[J].計算機應用與軟件,2011, 28(5):43-48.

[6] 范洪博,姚念民.一種高速精確單模式串匹配算法[J].計算機研究與發(fā)展，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-），男，安徽馬鞍山人，助教，碩士，主要從事計算機網(wǎng)絡與信息安全研究(E-mail: zsy19831104@163.com);

黃 偉(1981-），男，浙江余姚人，講師，碩士，主要從事計算機網(wǎng)絡研究(E-mail:yfworld@163.com);

李陽銘(1981-），男，遼寧阜新人，助理研究員，博士，主要從事模式識別研究(E-mail:ayun@lim.ac.cn).