深度包檢測技術(shù)中多模式匹配算法研究

艾鑫　田志宏　張宏莉

摘要：網(wǎng)絡(luò)數(shù)據(jù)流量的急速增長給深度包檢測技術(shù)帶來了新的挑戰(zhàn)，作為深度包檢測技術(shù)的重要基礎(chǔ)，字符串匹配算法針對大模式集合的優(yōu)化結(jié)果直接決定了深度包檢測技術(shù)的性能優(yōu)劣。對廣泛應(yīng)用的多模式串匹配AC算法進(jìn)行了改進(jìn)，通過引入平衡二叉樹結(jié)構(gòu)消除AC自動機中的無用狀態(tài)節(jié)點，在保證算法速度的前提下解決其在大規(guī)模模式集合匹配過程中內(nèi)存占用過大的問題，經(jīng)過實驗驗證，在模式集規(guī)模達(dá)100 000時，改進(jìn)的AVLAC算法內(nèi)存占用為傳統(tǒng)AC算法的5%左右。

關(guān)鍵詞：深度包檢測； 字符串匹配； AC算法； AVLAC算法

0引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展以及計算機硬件水平的不斷提高，網(wǎng)絡(luò)數(shù)據(jù)流量呈現(xiàn)出爆炸式的增長，數(shù)據(jù)特點從曾經(jīng)的靜態(tài)、少量和小范圍轉(zhuǎn)變?yōu)閷崟r、高速和大規(guī)模[1]。作為網(wǎng)絡(luò)安全的重要分支，信息內(nèi)容安全一直是學(xué)術(shù)界的熱點和重點，而對于深度包檢測技術(shù)，因其作為一種已獲廣泛應(yīng)用的內(nèi)容安全監(jiān)管和過濾的技術(shù)手段，深入研究其在大數(shù)據(jù)流量環(huán)境下的優(yōu)化方法具有重要意義。

深度包檢測技術(shù)，即DPI技術(shù)是一種基于應(yīng)用層的流量檢測和控制技術(shù)，當(dāng)IP數(shù)據(jù)包、TCP或UDP數(shù)據(jù)流通過基于DPI技術(shù)的管理系統(tǒng)時，該系統(tǒng)通過深入讀取IP包載荷的內(nèi)容而對OSI七層協(xié)議中的應(yīng)用層信息進(jìn)行重組，由此得到整個應(yīng)用程序的內(nèi)容，再按照系統(tǒng)定義的管理策略對流量進(jìn)行操作[2]。深度包檢測的技術(shù)從功能上可以劃分為協(xié)議還原、模式匹配和數(shù)據(jù)包操作3個層次，其中，模式匹配階段根據(jù)預(yù)先定義的特征模式集合對協(xié)議還原層提交上來的數(shù)據(jù)進(jìn)行匹配并將匹配結(jié)果遞交上層進(jìn)行相應(yīng)操作，一個性能良好的串匹配算法會大大提高系統(tǒng)效率。本文主要研究多模式串匹配算法在大規(guī)模模式集合情形下的優(yōu)化。

1研究現(xiàn)狀

根據(jù)匹配方式的不同，Navarro[3]等人將多模式匹配算法大致分為3類：基于前綴搜索的匹配算法，基于后綴搜索的匹配算法以及基于子串搜索的匹配算法，下面對各類典型的算法進(jìn)行介紹。

（1）基于前綴搜索的AC自動機算法[4]

AC算法是經(jīng)典的自動機算法，于1975年產(chǎn)生于貝爾實驗室，其特點是基于前綴搜索，并且是目前應(yīng)用最為廣泛的多模式匹配算法之一。該算法應(yīng)用有限自動機巧妙地將字符比較轉(zhuǎn)化為狀態(tài)轉(zhuǎn)移。其基本思想分為兩步。在預(yù)處理階段，AC自動機算法建立了三個函數(shù)，[JP2]也就是狀態(tài)跳轉(zhuǎn)goto函數(shù)、失效fail函數(shù)和輸出output函數(shù)，并由此構(gòu)造了一個樹型有限自動機。在搜索查找階段，則通過上述三個函數(shù)的交叉使用掃描文本，定位得到關(guān)鍵字在文本中的所有出現(xiàn)位置。[JP]

AC算法的關(guān)鍵是構(gòu)造樹型有限自動機，樹型有限自動機包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字代表。算法進(jìn)行匹配的時候，狀態(tài)機讀入文本串中的字符，然后通過產(chǎn)生狀態(tài)轉(zhuǎn)移或者偶爾發(fā)送輸出的方式來處理文本。其行為則可通過預(yù)處理階段建立的三個函數(shù)進(jìn)行標(biāo)明和指示。

（2）基于后綴搜索的Wu-Manber跳躍掃描算法[5]

Wu-Manber算法是基于后綴的跳躍掃描算法，又簡稱為WM算法，算法通過壞字符跳轉(zhuǎn)機制，采用字符塊技術(shù)，增大了待匹配文本和模式不匹配的可能性，從而增加了直接跳躍的機會。使用散列表選擇模式集合中的一個子集與當(dāng)前文本進(jìn)行完全匹配，并使用前綴表進(jìn)一步過濾不匹配的模式，使算法獲得了較高的運行效率。

WM算法和AC算法一樣，在匹配之前也需要對給定的模式集合進(jìn)行預(yù)處理，首先需要知道模式集合中最短的字符串長度，然后根據(jù)這一信息建立后綴哈希hash表、跳轉(zhuǎn)shift表以及前綴prefix表，這三個表將在匹配過程中提供算法所需要的各種信息：hash表確定掃描窗口內(nèi)后綴的跳轉(zhuǎn)距離，通過shift表指向所有具有相同后綴哈希值的模式鏈表以及具有相同后綴哈希值的模式前綴鏈表，prefix表則存儲了模式的前綴哈希值。

WM算法進(jìn)行模式匹配時，通過hash表、shift表與prefix表，并連同已知的字符串最短長度m建立滑動窗口，在滑動窗口內(nèi)，從后往前尋找最長好后綴，并在遇到壞字符時根據(jù)相應(yīng)規(guī)則進(jìn)行跳躍。試用一例說明，如果在hash表中沒有找到后綴字符塊B相應(yīng)的hash值，那么算法將會直接跳轉(zhuǎn)m-B+1個字符。WM算法通過巧妙的跳躍規(guī)則能夠縮短大部分情況下的模式匹配時間，但在特殊情況下，諸如m較小時算法效率不高。

（3）基于子串搜索的SBOM算法[6]

SBOM算法使用了Factor Oracle的數(shù)據(jù)結(jié)構(gòu)進(jìn)行掃描，根據(jù)這種數(shù)據(jù)結(jié)構(gòu)建立的自動機可以識別模式集合P的超集，利用Factor Oracle自動機，從后向前地掃描長度為lmin的文本窗口。如此就會出現(xiàn)兩種情況：[JP2]如果無法識別文本字符x，則可以將窗口直接移動到字符x的后面。如果無法識別當(dāng)前窗口內(nèi)的所有字符，就回到窗口起始位置，再將整個字符串和P的一個子集進(jìn)行比較驗證，判別是否發(fā)生了匹配。