多模式匹配及其改進(jìn)算法在協(xié)議識(shí)別中的應(yīng)用

朱姣姣，葉 猛

(1.光纖通信技術(shù)和網(wǎng)絡(luò)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074;2.武漢郵電科學(xué)研究院通信與信息系統(tǒng)，湖北 武漢 430074;3.武漢虹旭信息技術(shù)有限責(zé)任公司安全產(chǎn)品部，湖北 武漢 430074)

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)信息安全［1］與對(duì)抗已經(jīng)成為網(wǎng)絡(luò)信息時(shí)代的一個(gè)至關(guān)重要的問(wèn)題。為了能夠準(zhǔn)確地對(duì)網(wǎng)絡(luò)上的內(nèi)容進(jìn)行監(jiān)控，就需要搞清楚網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)包協(xié)議類(lèi)型，但在目前，TCP/IP協(xié)議體系下的網(wǎng)絡(luò)中，若要弄清楚數(shù)據(jù)包的協(xié)議類(lèi)型，就必須要能夠準(zhǔn)確地識(shí)別數(shù)據(jù)包的應(yīng)用層協(xié)議類(lèi)型。而傳統(tǒng)的采用端口的協(xié)議識(shí)別［2］對(duì)于采用動(dòng)態(tài)端口進(jìn)行通信卻力所不能及，由于模式匹配算法檢測(cè)原理簡(jiǎn)單易實(shí)現(xiàn)、實(shí)時(shí)性好、準(zhǔn)確率高而備受廣大軟件愛(ài)好者喜愛(ài)，且技術(shù)上已經(jīng)相對(duì)成熟，在協(xié)議識(shí)別領(lǐng)域得到了廣泛應(yīng)用，基于以上分析，本文重點(diǎn)討論多模式匹配算法，以及其改進(jìn)算法在協(xié)議識(shí)別中的應(yīng)用，并分析模式匹配算法的今后研究方向。

1 模式匹配算法

單模式匹配算法是指在文本串中一次只對(duì)一個(gè)模式進(jìn)行匹配;多模式匹配算法則可同時(shí)對(duì)多個(gè)模式進(jìn)行匹配，在很大程度上提高了匹配效率，且多模式匹配算法同樣也適用于單模式的情況。

1.1 單模式匹配算法

常用的單模式匹配算法有BF算法、KMP算法、BM算法［3］，下面簡(jiǎn)要分析這幾種算法。

BF算法是最早最簡(jiǎn)單的單模匹配算法，其特點(diǎn)是直觀、簡(jiǎn)單，但涉及多次回溯，算法效率極低。

無(wú)需回溯指示文本串的指針是KMP算法的最大優(yōu)勢(shì)，其充分利用部分已匹配字符，將模式串盡可能向右滑動(dòng)一段距離。但KMP算法存在著重復(fù)比較的缺陷。

BM算法基本思想是先對(duì)模式串進(jìn)行預(yù)處理，當(dāng)存在不匹配時(shí)，通過(guò)采用壞字符規(guī)則和好后綴規(guī)則，來(lái)計(jì)算模式串的偏移值，取兩者中的較大值，實(shí)現(xiàn)跳躍式的遍歷匹配。BM算法在單模式匹配中效率很高，但BM算法使用了兩個(gè)數(shù)組，預(yù)處理開(kāi)銷(xiāo)大，計(jì)算兩個(gè)偏移量的過(guò)程也很復(fù)雜。

針對(duì)單模式匹配算法，假如要匹配多個(gè)模式，則有幾個(gè)模式，那么就需要進(jìn)行幾趟遍歷，在效率上是很低的。而多模式匹配算法一次遍歷則可匹配出多個(gè)模式，因此，根據(jù)多模式匹配算法所占有的優(yōu)勢(shì)，將其應(yīng)用于協(xié)議識(shí)別中。

1.2 AC多模式匹配算法

AC算法［4］是基于應(yīng)用層報(bào)文內(nèi)容實(shí)時(shí)分析的核心算法。這種簡(jiǎn)單有效的算法用來(lái)在一串文本中確定給定的一組關(guān)鍵字在文本中發(fā)生的頻度，它具有匹配速度快、占用CPU少、適合海量數(shù)據(jù)的網(wǎng)絡(luò)環(huán)境等優(yōu)點(diǎn)。

AC算法的基本思想是在處理階段分別建立3個(gè)函數(shù)，即轉(zhuǎn)向函數(shù)(goto)、失效函數(shù)(fail)以及輸出函數(shù)(output)，由此形成一個(gè)樹(shù)型有限自動(dòng)機(jī);在搜索查找階段，互相交叉使用以上3個(gè)函數(shù)，然后進(jìn)行掃描文本，可定位出關(guān)鍵字在文本中的所有出現(xiàn)位置。

算法描述:構(gòu)造P={P1，P2，…，Pk}對(duì)應(yīng)的 k樹(shù)。首先，從唯一的根節(jié)點(diǎn)開(kāi)始;然后，通過(guò)添加一條從根節(jié)點(diǎn)出發(fā)的路徑的方式，依次插入每一個(gè)模式Pi。新的節(jié)點(diǎn)和邊被插入到K樹(shù)中，以致產(chǎn)生了一條能拼寫(xiě)出關(guān)鍵字Pi的路徑。在路徑的終點(diǎn)存儲(chǔ)Pi的標(biāo)識(shí)i，關(guān)鍵字Pi會(huì)被添加到輸出函數(shù)中。

1.2.1 生成樹(shù)型有限自動(dòng)機(jī)

例如，模式集{at，ater，eat，a＆e}的樹(shù)型有限自動(dòng)機(jī)，轉(zhuǎn)向函數(shù)goto如圖1所示。

圖1 轉(zhuǎn)向函數(shù)goto示意圖

失效函數(shù)fail和輸出函數(shù)output如表1所示。

表1 失效函數(shù)fail和輸出函數(shù)output

1.2.2 生成確定有限自動(dòng)機(jī)

由以上3個(gè)函數(shù)生成的狀態(tài)樹(shù)為不確定有限狀態(tài)機(jī)(NFA)，當(dāng)發(fā)現(xiàn)匹配失敗后，需要通過(guò)fail函數(shù)來(lái)完成狀態(tài)跳轉(zhuǎn)，使用確定有限狀態(tài)機(jī)(DFA)，通過(guò)合并fail函數(shù)和goto函數(shù)，生成新DFA。利用這個(gè)確定的有窮自動(dòng)機(jī)可以減少狀態(tài)轉(zhuǎn)移的次數(shù)，使得效率得到一定的提高。例如在狀態(tài)1下輸入字符e:NFA中，首先跳轉(zhuǎn)至狀態(tài)0，再在0狀態(tài)下輸入字符e，跳轉(zhuǎn)至狀態(tài)5，需查詢(xún)2次狀態(tài)表;DFA中，直接跳轉(zhuǎn)至狀態(tài)5，僅需查詢(xún)1次狀態(tài)表即可。

2 AC多模式匹配算法的改進(jìn)

由于AC算法不能實(shí)現(xiàn)跳躍式搜索，研究者據(jù)此提出了多種基于AC的改進(jìn)算法。Commentz－Walter提出一種結(jié)合AC和BM的算法(簡(jiǎn)稱(chēng)CW算法［5］)，該算法將BM算法跳躍思想應(yīng)用于多模式匹配中，匹配效率較高。Jang－Jong Fan和Keh－Yih SuCrochemore結(jié)合RF算法給出的 Dawg－Match 算法性能更優(yōu)(簡(jiǎn)稱(chēng) Dawg 算法［6］)，王永成通過(guò)反向構(gòu)建goto函數(shù)來(lái)實(shí)現(xiàn)模式匹配，該算法從右到左進(jìn)行模式串比較，采取連續(xù)跳躍的思想，在匹配過(guò)程中盡可能跳過(guò)多的字符(簡(jiǎn)稱(chēng)Wang算法［7］)。

另外針對(duì)AC算法對(duì)內(nèi)存需求大的問(wèn)題，研究者們也提出了多種快速和高效存儲(chǔ)的優(yōu)化算法，Norton［8］等提出了 Banded－Row Forma(帶狀行格式)和Sparse－Row Format(稀疏行格式)的稀疏存儲(chǔ)格式。Tuck等采用位圖壓縮和路徑壓縮方法來(lái)減小自動(dòng)機(jī)內(nèi)存消耗，改善了儲(chǔ)存性能。但均可能不同程度地引起匹配性能的下降。

在存在短模式串的情況下，CW算法、Dawg算法以及Wang算法的匹配性能會(huì)急劇下降，平均每字符檢查的次數(shù)驟然增加，比不上AC算法的效率。

針對(duì)這一問(wèn)題，本文提出一種基于AC的多模式匹配改進(jìn)算法，其關(guān)鍵技術(shù)在于它不僅利用匹配過(guò)程中的“壞字符”信息，盡可能跳躍更多的字符，還利用模式匹配的信息，增加跳躍的步長(zhǎng)。本文的算法基于這樣一個(gè)前提，短模式串比長(zhǎng)模式串匹配概率更高，且以更高的概率優(yōu)先命中。

2.1 預(yù)處理階段

算法的預(yù)處理階段包括構(gòu)建模式串集合的AC狀態(tài)機(jī)，以及跳躍表shift。

AC狀態(tài)機(jī)是一個(gè)有限狀態(tài)自動(dòng)機(jī)(DFSA)，可描述為(Q，δ，f，s0，T)。其中Q表示狀態(tài)機(jī)中狀態(tài)的有限集合，δ表示狀態(tài)轉(zhuǎn)移函數(shù)，f表示失配狀態(tài)轉(zhuǎn)移函數(shù)，s0表示初始狀態(tài)，T表示匹配的狀態(tài)。在具體實(shí)現(xiàn)中，可以通過(guò)消除”壞字符”回溯取消f，使得δ對(duì)任何輸入的字符轉(zhuǎn)移到非空狀態(tài)(包括s0)。這樣AC狀態(tài)機(jī)簡(jiǎn)化為(Q，δ，s0，T)，圖 2 表示了一個(gè)模式集合 P={aabbaa，bbaabb，abb，aa}對(duì)應(yīng)的狀態(tài)機(jī)，狀態(tài)上方表示輸出的模式集合output。

構(gòu)建模式子集的shift表之前，首先按照模式串的長(zhǎng)度將所有的模式分為L(zhǎng)個(gè)相交的子集。給定P=p1，p2，…，pm，計(jì)算集合 SL={distinct|pi|，1≤i≤m}，有SL=L，則 SL 可進(jìn)一步記為 SL={l1，l2，…，lL}。令 SL={pi，|pi|=l，1≤i≤m}，顯然有 ?pi∈SL，≡l，且在預(yù)處理階段pi的狀態(tài)均是未匹配的。

圖2 模式集合P的AC自動(dòng)機(jī)

令集合 Setj={pi，|pi|≥lj，1≤i≤m}，1≤j≤L，這樣就得到了L個(gè)相交模式集合的子集，且Setj－Set1={|pi|=lj－1}，2≤j≤L。從QS算法的描述可知壞字符qsBc表定義為

式中:c∈Σ，p為任意模式串。而在多模式匹配算法情況下shift表可定義為

式中:c∈Σ，1≤j≤L。

設(shè) P={aabbaa，bbaabb，abb，aa}，將 P 劃分為{aabbaa，bbaabb}，{aabbaa，bbaabb，abb，aa}，{aabbaa，bbaabb，abb}3個(gè)子集，且最大跳躍值分別為3，4和7。

此外還需要將每一個(gè)存在output輸出的狀態(tài)做一個(gè)標(biāo)記j，決定模式串屬于哪一個(gè)Setj可以加快跳躍的判斷。形式描述為{j，max(|output|)=lj}，其中output為節(jié)點(diǎn)輸出的模式串集合，如果使用鏈表存儲(chǔ)的話，則output指向第一個(gè)模式串，output－＞next指向下一個(gè)模式串，直到next域指向NULL。具體實(shí)現(xiàn)可以規(guī)定|output|≥|output－＞next|≥…≥|ε|，則有 max(|output|)=|output|。

設(shè)置所有存在output輸出的節(jié)點(diǎn)所屬的集合下標(biāo)的算法采用了深度優(yōu)先的遍歷方式，其中δ為構(gòu)建狀態(tài)機(jī)后得到的狀態(tài)轉(zhuǎn)移函數(shù)。算法描述如下:

2.2 搜索階段

搜索算法結(jié)合了AC算法和QS算法的技術(shù)。在QS算法中，比較窗口內(nèi)比較次序可以是任意的，一旦發(fā)生了失配的情況，可根據(jù)左鄰比較窗口的第一個(gè)字符決定下一個(gè)比較窗口跳躍的距離。本算法采用了由左往右的方式比較模式串，并依次讀入字符實(shí)現(xiàn)AC狀態(tài)的轉(zhuǎn)移。

算法在比較的過(guò)程中，如果某個(gè)短模式的集合匹配成功，則使用在預(yù)處理中計(jì)算的新的shift表，可以預(yù)期字符跳躍距離將動(dòng)態(tài)增加，并能以更高的匹配速度處理余下的文本串。算法描述如下，其中T表示目標(biāo)文本串，size表示目標(biāo)文本串的長(zhǎng)度。

下面舉例說(shuō)明，如模式集合P={aabbaa，bbaabb，abb，aa}，目標(biāo)文本串T=aabbaxxxaabbaa。

第一個(gè)比較窗口初始大小為2，如圖3所示。

圖3 比較窗口

直到遇到字符x，此時(shí)已匹配了{(lán)abb，aa}，尚未匹配的模式集合為{aabbaa，bbaabb}，窗口滑動(dòng) shift［x，2］=8，且窗口動(dòng)態(tài)增加到6，如圖4所示。

圖4 比較窗口

比較一直到文本T結(jié)束，模式{aabbaa}被匹配。算法總共比較了12個(gè)字符。

3 實(shí)驗(yàn)分析

測(cè)試環(huán)境是編譯器gcc version 4.1.2，優(yōu)化開(kāi)關(guān)全部打開(kāi)，CPU Pentium III 800 MHz，內(nèi)存為256 Mbyte，操作系統(tǒng)為L(zhǎng)inux 2.6.40，測(cè)試文本T為30 Mbyte文本串。選取AC算法、去掉fail的AC算法、Wang算法、CW算法作為比較對(duì)象。

1)模式數(shù)量一定，模式長(zhǎng)度的變化對(duì)匹配速度的影響如圖5所示，圖5中給出的模式數(shù)量固定為100個(gè)，可預(yù)先在模式集合中設(shè)置一些短模式串。

圖5 不同模式長(zhǎng)度下算法的匹配速度

2)模式長(zhǎng)度一定，模式個(gè)數(shù)的變化對(duì)匹配速度的影響如圖6所示，圖6中給出的模式長(zhǎng)度固定為10 byte。

圖6 不同模式數(shù)量下算法的匹配速度

測(cè)試結(jié)果證明圖5在模式集合中存在長(zhǎng)度較短的模式情況時(shí)，本文的算法能夠顯著抵抗由此引起的性能衰減。圖6驗(yàn)證了本算法隨著模式個(gè)數(shù)的增加，匹配速度不會(huì)出現(xiàn)陡然惡化的情況。綜合實(shí)驗(yàn)的結(jié)果，可以得出在大多數(shù)情況下本文的算法相比其他算法有最好的匹配速度，匹配效果不受模式數(shù)目的限制，抗短模式影響比較好。

4 多模式匹配在協(xié)議識(shí)別中的應(yīng)用

通過(guò)對(duì)常見(jiàn)網(wǎng)絡(luò)協(xié)議的特征進(jìn)行分析或者查閱某應(yīng)用層協(xié)議公開(kāi)的RFC文檔，提取出協(xié)議的特征信息，作為鑒別應(yīng)用層協(xié)議網(wǎng)絡(luò)數(shù)據(jù)流的標(biāo)識(shí)。每種應(yīng)用的分組中都攜帶有特定的報(bào)文信息，一般是幾個(gè)字節(jié)長(zhǎng)的固定字段，例如，SMTP協(xié)議報(bào)文中含有RCPT TO，MAIL等特征信息，根據(jù)此特征進(jìn)行模式匹配，由此判斷出該報(bào)文是屬于哪種網(wǎng)絡(luò)協(xié)議的應(yīng)用。根據(jù)多模式匹配算法，對(duì)某種協(xié)議所具有的關(guān)鍵字建立一棵模式樹(shù)，一個(gè)規(guī)則表示一個(gè)協(xié)議，一個(gè)規(guī)則對(duì)應(yīng)一個(gè)模式集合，在文本串中通過(guò)模式匹配進(jìn)行協(xié)議識(shí)別，當(dāng)某個(gè)規(guī)則中的所有模式都被找到時(shí)，再繼續(xù)檢查報(bào)文是否滿足其他如IP限制、端口限制等條件，只有這些都滿足，才說(shuō)明這個(gè)報(bào)文完全匹配這個(gè)規(guī)則。

5 小結(jié)

隨著新的應(yīng)用協(xié)議不斷出現(xiàn)，需要不斷改進(jìn)模式匹配算法以提高其在協(xié)議識(shí)別中的準(zhǔn)確性和高效性。本文主要提出了一種基于AC的多模式匹配改進(jìn)算法，利用匹配過(guò)程中“壞字符”信息，盡可能跳躍更多的字符和模式匹配信息，動(dòng)態(tài)增加跳躍的步長(zhǎng)。這種算法能較好地抵抗短模式引起的性能衰減。本文的算法可以繼續(xù)分析空間的復(fù)雜性，以及壓縮狀態(tài)轉(zhuǎn)移表對(duì)性能的影響。

網(wǎng)絡(luò)帶寬的不斷增加給網(wǎng)絡(luò)安全技術(shù)帶來(lái)巨大的挑戰(zhàn)。協(xié)議識(shí)別作為網(wǎng)絡(luò)安全技術(shù)的一個(gè)重點(diǎn)，提出了更高的要求。雖然協(xié)議識(shí)別可以采用很多技術(shù)，但模式匹配算法仍然是目前的主流協(xié)議識(shí)別技術(shù)。因此如何繼續(xù)改進(jìn)模式匹配來(lái)提高匹配速度，成為今后研究協(xié)議識(shí)別技術(shù)的一個(gè)關(guān)鍵，這里可以從以下幾個(gè)方面著手:一是將各種模式匹配算法相結(jié)合;二是模式匹配算法與其他智能方法的結(jié)合;三是對(duì)模糊匹配的深入研究。

［1］楊明，孫洪峰.信息與因特網(wǎng)絡(luò)安全防范技術(shù)［J］.電視技術(shù)，2003，27(1):30－32.

［2］陳亮，龔儉，徐選.應(yīng)用層協(xié)議識(shí)別算法［J］.計(jì)算機(jī)科學(xué)，2007，34(7):73－75.

［3］冉占軍，姚全珠，王曉峰，等.模式匹配算法在入侵檢測(cè)中的應(yīng)用［J］.現(xiàn)代電子技術(shù)，2009(2):63－67.

［4］AHO A C，CORASICK M J.Efficient string matching:an aid to bibliographic search［J］.Communications of the ACM，1975，18(6):330－343.

［5］COMMENTZ－WALTER B.A string matching algorithm fast on the average［C］//Proc.6th ICALP.［S.l.］:IEEE Press，1979:118－132.

［6］FAN J J，SU K Y.An efficient algorithm for matching multiple patterns［J］.IEEE Transactions on Knowledge and Data Engineering，1993，5(2):339－351.

［7］王永成，沈州，許一震.改進(jìn)的多模式匹配算法［J］.計(jì)算機(jī)研究與發(fā)展，2002，39(1):55－60.

［8］NORTON M.Optimizing pattern matching for intrusion detection［EB/OL］.［2006－05－11］.http://docs.idsresearch.org./Optimizing Pattern-MatchingForIDS.pdf.