一種改進的單模式匹配算法

張玉新，李成海，白瑞陽

（空軍工程大學 防空反導學院，西安 710051）

一種改進的單模式匹配算法

張玉新，李成海，白瑞陽

（空軍工程大學 防空反導學院，西安 710051）

0 引言

網絡已成為人們生活、學習、生產等諸多領域不可缺少的一部分，但是由于諸多的因素造成了網絡安全問題的頻發(fā)，在網絡高速化的時代，如何從大量數據中提取特定的信息，顯得十分重要。模式匹配就是給定字符串T和S，其中字符串T稱為正文，字符串S稱為模式，要求在正文T中找到模式S是否出現。

模式匹配可以分為單模式匹配和多模式匹配，其中單模匹配有著名的BF算法、BM算法、BMH算法、KMP算法，文獻[1]提出的快速單模式匹配算法(FSBM)充分利用已匹配的后綴和字符串后一位字符的信息,已達到在每一次跳躍中跳躍盡量大的距離，文獻[2]利用模式字符串中存在重復字符串來獲得最大的移動距離。多模匹配有AC算法，AC-BM算法，文獻[3,4]也提出了相關的一些改進。其中Snort2.9中應用的就是單模匹配和多模匹配算法。本文重點以單模式匹配為研究內容，并結合傳統的一些匹配算法如BM算法、BMH算法、Sunday(QS)算法，給出一種改進后的單模式匹配算法。

1 單模式匹配

單模式匹配算法是指在文本串T=t1t2t3…tn中一次只對一個模式P=p1p2p3…pn進行匹配。

1.1 BF算法

模式匹配最簡單的做法是用模式串P的字符依次與文本串T作對比，這就是BF算法的思想，是最早最簡單的單模匹配算法，其特點是直觀簡單，圖1為BF算法匹配過程。

圖1 BF算法匹配過程

如果p1=t1,p2=t2,p3=t3,p4=t4,…,pm=tm，則表明匹配成功，如果中間有一位匹配不成功，則右移一位從頭再次開始匹配，直到匹配成或移到文本串最右端結束匹配過程。從匹配過程可以看出指向文本串的指針在一次匹配失敗的情況下，執(zhí)行下次匹配的時候指針需要返回再次重頭開始，涉及多次回溯，最糟糕的情況下，每一次比較到最后才出現匹配成功，則一次比較需要m次，匹配完成最多需要n-m+1趟，通常n≥m，所以時間復雜度為Q(n*m)，算法效率極低。

1.2 BM及BMH算法

BM算法的基本思想是：模式串P以左對齊的方式，從右往左依次和文本串進行匹配，發(fā)生匹配失敗時使用壞字符和好后綴中的最大值實現最大右移步長。壞字符原則，即一次匹配過程中出現匹配失敗ti1Pj，當ti能夠在模式串P中找到，將出現在P中最右端的ti右移與文本串中的ti對齊進行下一次匹配，當ti不能夠在模式串P中找到，將模式串P右移的距離為已連續(xù)匹配的字符數。好后綴原則，當模式串P的后綴中有子串與文本串T已匹配，模式串P可以右移的距離為子串的長度，當模式串P的后綴中有子串與文本串T已匹配且模式串前綴中有子串與以匹配后綴子串相同，將前綴子串與后綴子串右移對齊，實現一次右移。BM算法的匹配過程如圖2所示。

圖2 BM算法的匹配過程

第1次匹配時p7=t7,p8=t8且模式串中p4p5=p7p8，采用后后綴原則，第2次匹配和第4次匹配均采用壞字符原則，第3次匹配p6p7p8=t11t12t13采用好后綴原則實現左移。

在模式匹配中，壞字符產生的概率占94.03%，遠大于好后綴啟發(fā)規(guī)則，BMH算法就是在匹配時只考慮壞字符啟法規(guī)則，在大部分情況下，BMH算法的性能要優(yōu)越于BM算法。BMH算法的思想是首先匹配模式串末尾所對應文本串的字符，若果匹配成功則再匹配其余的m-1位字符。只要文本串T中的任何字符造成匹配失敗，都將由文本中和模式串最后一個位置對應的字符來啟發(fā)模式向右的移動。BMH算法的最大右移距離為m。BMH算法匹配過程如圖3所示。

圖3 BMH算法匹配過程

1.3 QS算法

Sunday提出的QS算法，任然只采用了壞字符規(guī)則，與BMH不同的是QS算法在匹配過程中考慮與模式串T對齊的最后一個字符的下一個字符，最大跳躍距離為m+1。

當發(fā)生不匹配時，QS算法用下一個字符來計算右移量，即使用T[i+l]，當該字符不出現在模式串中時，可以直接跳過T[i+1]，右移距離比BMH大，但當T[i+l]在模式串中出現時，而T[i]不在模式串中出現時，這時右移距離BMH要大于QS算法，QS效率就不如BMH了。

2 改進的一種算法

2.1 算法思想

受BMH和QS的啟發(fā)，結合二者的優(yōu)點提出一種改進的匹配算法。該算法的基本思想是：采用模式串P與文本串T左對齊，匹配時從右向左匹配。定義i（i=1，2，…，n）為指向文本串T的指針，j（j=1，2，…，m）為指向模式串的指針。改進的算法也采用QS算法中與模式串T對齊后的下一個字符T[i+m]位，依據T[i+m]位生成壞字符表，同時利用連續(xù)的兩組字符T[i+m-1]T[i+m]和T[i+m]T[i+m+1]生成右移距離表。

2.2 匹配過程

首次匹配時由T[i+m]位生成壞字符表，如果T[i+m]不在模式串P中按照QS算法思想模式串將會右移m+1位；若T[i+m]在模式串P中能夠找到，計算連續(xù)的T[i+m-1]T[i+m]和T[i+m]T[i+m+1]兩個字符是否在模式串中有連續(xù)出現的，兩組連續(xù)的子串只要有一個出現就將模式串P中最右端中出現的子串右移與其中跳躍距離最大的對齊，即跳躍距離=max{( T[i+m-1]T[i+m]),( T[i+m]T[i+m+1])}，如果T[i+m-1]T[i+m]和T[i+m]T[i+m+1]直接跳過T[i+m-1]T[i+m]和T[i+m]T[i+m+1]，此時跳躍距離可達m+2。圖4是改進算法的匹配過程。

圖4 改進算法的匹配過程

在第一次匹配中可以看出T[9]=P[3]，且T[8]T[9]=P[2]P[3]，T[9]T[10]=T[3]T[4]，二者右移距離都為2，將模式串P右移2位；第二次匹配T[15]=P[8]，且T[14]T[15]=P[1]P[2]，T[15]T[16]在模式串P中沒有找到對應的子串，模式串P右移7位；依次在第4次完成整個匹配。

從上圖4可以看出，整個匹配過程主需要循環(huán)4次就可以完成，該算法同時獲得了較大的移動距離，提高了匹配效率，從圖2、圖3的對比中可以發(fā)現該算法在某些情況下比BM算法、BHM算法匹配速度更快。

3 實驗結果及結論

本實驗在windows XP，Pentium Dual-Core E5800，2GB RAM環(huán)境下對BM算法，BMH算法、QS算法和改進的算法分別編程測試，在一篇純英文文章153KB，149829個字符的情況下，以4、6、8、12長度的模式串進行測試得到如圖5匹配比較次數和圖6匹配經歷時間所示的結果。從圖中比較次數和運行時間可以看出改進后的算法具有一定的優(yōu)越性。

圖5 匹配比較次數

圖6 匹配經歷時間

4 結束語

改進后的匹配算法通過實驗證實提高了匹配效率，在網絡數據高速增長的時代，只有高效的算法才能勝任實時入侵檢測的需求，本文提出的改進算法為下一步在入侵檢測中的應用奠定了基礎。

[1]王天聰,侯整風,何玲.基于BM的模式匹配改進算法[J].合肥工業(yè)大學學報,2011,34(3):363-366.

[2]丁國強,趙國增,李傳鋒.改進BM算法策略的網絡入侵檢測系統設計[J].計算機測量與控制,2011,11(19):2661-2664.

[3]汪永進,顧乃杰,任開新.一種按字長匹配的Wu－Manber多模式匹配算法[J].小型微型計算機系統,2013,34(7):1650-1653.

[4]王培鳳,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].計算機應用研究,2011,28(4):1251-1253,1259.

[5]張宇,劉萍,劉燕兵,譚建龍,郭莉.對模式串匹配算法WuManber的復雜度攻擊[J].計算機研究與發(fā)展,2011,48(8):1381-1389.

[6]嵩天,李冬妮,汪東升,薛一波. 存儲有效的多模式匹配算法和體系結構[J]. 軟件學報,2013,24(7):1650-1665.

[7]王英,左祥麟,左萬利,王鑫. 基于本體的Deep Web查詢接口集成[J]. 計算機研究與發(fā)展,2012,49(11):2383-2394.

[8]梁棟,朱明,唐俊,范益政,顏普. 基于局部相對形狀上下文與Q-譜的點模式匹配算法[J].電子學報,2012,40(4):636-641.

[9]朱映映,吳錦鋒,明仲. 基于網絡事件和深度協議分析的入侵檢測研究[J].通信學報,2011,32(8):171-178.

[10]Tan GM, Liu P, Bu DB et al. Revisiting multiple pattern matching algorithms for multi-core architecture[J].Journal of computer science and technology,2011,26(5):866-874.

[11]Dong Liang,PuYan,MingZhu, Yizheng Fan, Kui Wang.Spectral matching algorithm based on nonsubsampled contourlet transform and scale-invariant feature transform[J]. Journal of Systems Engineering and Electronics,2012,23(3):453-459.

[12]李艷鵾,付維娜,劉帥,祝明. 并行系統中KMP串匹配算法的實現[J].制造業(yè)自動化,2011,33(1):189-191.

[13]梁威,葉猛. 海量數據過濾系統中匹配算法的研究[J].電視技術,2013,37(1):87-90.

[14]侯寶劍,謝飛,胡學鋼,劉應玲,王海平. 基于后綴樹的帶有通配符的模式匹配研究[J].計算機科學,2012,39(12):177-180,194.

[15]朱西講.一種改進的BM算法在網絡安全控制中應用[J].科技通報,2012,28(6):49-51.

Improved single pattern matching algorithm

ZHANG Yu-xin, LI Cheng-hai, BAI Rui-yang

模式匹配算法在病毒特征碼檢測、入侵檢測、生物信息等諸多領域有著廣泛的應用，如何提高匹配的效率是制約模式匹配算法的決定因素，本文通過分析傳統的模式匹配算法提出一種改進的單模式匹配算法，通過對比分析和驗證，該算法提高了匹配效率。

模式匹配；BM算法；BMH算法

張玉新（1990 -），男，甘肅民樂人，碩士研究生，研究方向為網絡信息安全。

TP393.08

A

1009-0134(2014)06(上)-0015-03

10.3969/j.issn.1009-0134.2014.06(上).04

2014-03-08

國家自然科學（61272486）