吳君欽，王 凱

(江西理工大學 信息工程學院，江西 贛州 341000)

在網絡安全監(jiān)控中，深度報文檢測技術是一種主要的手段，它通過字符串匹配算法把網絡中捕獲到的數(shù)據流與特定的字符串進行匹配。這里所說的特定字符串是指在分析數(shù)據報文協(xié)議的基礎上提取的特征字符，通過這種方式可以識別并阻斷某些數(shù)據流，實現(xiàn)有效的網絡安全防范。

在深度報文檢測技術上，經典的字符串匹配算法有單模式匹配的KMP和BM算法,改進的多模式匹配的AC算法、CM算法、WANG方法和 Wu-Manber算法，然而這些算法都采用字符串匹配為基礎。隨著網絡的不斷發(fā)展，應用軟件特征字符識別的復雜度越來越大，采用字符串匹配已難以匹配識別，因此這些算法的局限性也凸顯出來?；谡齽t表達式的多模式匹配具備了優(yōu)越的表達匹配能力和靈活性，相比傳統(tǒng)的字符串匹配更加精確高效。

基于正則表達式的多模式匹配是把正則表達式轉變?yōu)樽詣訖C，自動機分為兩種：非確定有限自動機(NFA)和確定有限自動機(DFA)。NFA的優(yōu)點是占用內存和系統(tǒng)資源少，但是需要對每個字符進行遍歷，處理狀態(tài)集里的所有狀態(tài)，很耗費時間。如 good(day|night|evening)：若要搜 goodday，NFA需要把goodday、goodnight、goodevening全部遍歷一次才能完成搜索。相比之下，DFA搜索一個字符只需要訪問一個狀態(tài),但是若把所有的正則表達式都轉變?yōu)镈FA將會占用非常大的系統(tǒng)內存資源，目前的硬件條件還無法滿足這一點。

結合NFA和DFA各自的優(yōu)缺點，本文提出了一種猜測-分組-檢驗的匹配算法。使用DFA在猜測的基礎上添加分組，能夠更有效減少系統(tǒng)內存占用率；然后再結合NFA檢測確保算法具備高匹配度。

1 正則表達式相關算法

深度報文包檢測技術是基于系統(tǒng)規(guī)則庫對在網絡中捕獲的數(shù)據包中的每一個字節(jié)進行掃描和識別，標準的字符串匹配算法有：Aho-Corasiek[1]、ComentZ-Walter[2]和Wu-Manber[3]算法。如今隨著網絡協(xié)議復雜度日益增加，傳統(tǒng)的字符串匹配算法難以精確地識別出復雜多變的協(xié)議類型[4]。

SOMMER R和 PAXSON V[5]認為，用正則表達式描述網絡中數(shù)據協(xié)議行為比用字符串表達更為高效、靈活。KUMAR S[6]等通過將DFA的某些狀態(tài)用單條缺省邊來代替，提出一種稱為延遲輸入DFA，實驗結果表明,相比于傳統(tǒng)的DFA存儲空間可減少95%以上。但是引入缺省邊導致處理一個字符需要多次訪問內存，參考文獻[7]對參考文獻[6]進行改進,提出一種目錄尋址的D2FACD2FA，用包含部分狀態(tài)信息的目錄標簽來代替狀態(tài)的ID，而這些信息一般是保存在狀態(tài)表的條目中，使得一次轉移只消耗一個字符。

YU F等人提出了將正則表達式進行分組的思想[8]。其方法是：計算正則表達式兩兩之間是否引起狀態(tài)增長，在進行分組時，選擇一條與其他表達式具有最小相關度的正則表達式開始，然后按照相同的原則向這個組里不斷添加，直到這個組形成的DFA內存超過預先設定的閾值，再開始創(chuàng)建另一個新組。重復這個過程，直到所有的表達式都被分配出去為止。

[9]提出了一種混合自動機的方法，其基本思想是：將整個規(guī)則集編譯成一個NFA結構之后，并不對它進行完全的確定化，而是在確定化之前判斷狀態(tài)之間跳轉的原因。進行部分確定化的結果就是形成了一個混合的自動機結構，它的前面一部分是DFA的狀態(tài)，而在每個邊界狀態(tài)之后都帶有一個NFA，這個NFA以邊界狀態(tài)作為初始狀態(tài)。

張樹壯等人提出了一種基于猜測-驗證的匹配方法[10]：首先使用DFA對正則表達式中的部分子特征進行搜索，完成特征存在性的猜測。當猜測到有可能匹配某個特征后，再使用NFA進行驗證。這種方法既充分利用了DFA的高效性，減少了對相對較慢的驗證過程,又借助NFA避免了內存消耗過于巨大。

本文在深入研究和分析以上算法的基礎上，針對DPI規(guī)則庫這樣十分龐大的規(guī)則系統(tǒng)，借鑒一些經典正則表達式匹配算法，提出一種猜測-分組-檢驗算法。該算法把分組作為核心步驟，利用正則表達式之間的相關性組合后進行分組，能夠十分有效地降低系統(tǒng)內存資源的使用率。結合NFA驗證，該算法能夠對輸入進行有效的匹配和識別。

2 算法描述

正則表達式匹配算法分為三個步驟：猜測、分組和檢驗?？傮w來說，在安全監(jiān)控中所使用的規(guī)則一般都可以分為若干個特征子塊 Sub-feature，如圖1所示，每個子特征之間通過正則表達式運算符連接在一起。獲取到這些特征子塊之后，可以簡單地把它們合并轉換為一個DFA。然而這樣一個DPI的規(guī)則庫，將會占用十分龐大的系統(tǒng)內存資源。所以在獲得特征子塊后，需要采用相似性度分析對這些子塊進行分組，把相似程度高的子塊聚合在一起，并通過子集構造法轉換為一個DFA,再通過正則運算符把各個組的DFA連接在一起。分組后的DFA占用系統(tǒng)內存資源小，可以有效減少空間使用率，進而提高資源的有效利用率。若某個輸入與猜測選擇出的特征子塊匹配，則把輸入進行NFA驗證，驗證方法是基于DPI庫中的每條規(guī)則轉變?yōu)镹FA得到的。

圖1 特征子塊示意圖

2.1 猜測

在面向網絡數(shù)據流匹配的基礎上，安全監(jiān)控中使用的規(guī)則可以明顯地分為若干個部分(Sub-feature)。首先從系統(tǒng)規(guī)則庫保留的某條規(guī)則中還原出Sub-feature，然后以Sub-feature的出現(xiàn)為依據猜測輸入是否與某些規(guī)則匹配。在本文中，根據規(guī)則庫每條規(guī)則中某段字符串出現(xiàn)的概率來選取Sub-feature進行輸入猜測。

2.2 分組

若正則表達式兩兩之間具有相似性 (這里的相似性定義為：當正則表達式單獨轉換為DFA所需要的狀態(tài)數(shù)大于正則表達式聯(lián)合在一起轉換為DFA所需要的狀態(tài)數(shù)，那么稱正則表達式具備相似性)，則它們聯(lián)合在一起轉變?yōu)镈FA所需要的狀態(tài)數(shù)小于其單獨轉換所需要的狀態(tài)數(shù)總和，這將大大減少占用的系統(tǒng)內存資源。若兩個正則表達式具有相似性，例如abde、abdz兩個正則表達式，將它們單獨轉換為 DFA，如圖2、圖3所示，聯(lián)合起來轉換為DFA，如圖4所示。結果表明，聯(lián)合轉換需要7個狀態(tài)，而單獨轉換共需要10個狀態(tài)，聯(lián)合轉換比單獨轉換減少了3個狀態(tài)。

圖2 abde轉換狀態(tài)圖

圖3 abdz轉換狀態(tài)圖

圖4 abde和abdz聯(lián)合轉換狀態(tài)圖

其中S1和S2分別為代表兩個需做比較的正則表達式，ED(S1,S2)是指 S1和 S2之間編輯距離，max(|S1|,|S2|)是選擇兩個正則表達式中字符多的一個。若兩個正則表達式完全一樣，則計算結果為1；若兩個正則表達式完全不同，則計算結果為0。式(1)的字符串相似度算法復雜度小、精確度大，采用其進行相似度計算能夠有效減少內

相似性計算中采用字符串相似性計算法,如式(1)所示：存消耗并且確保極高的匹配率。

采用上述的相似性計算法將每個Sub-feature進行相似度分析并分組。首先，在所有未分組的Sub-feature中選取一個與其他Sub-feature具有相似性的Sub-feature加入一個新組并記為group0；其次，在所有未處理的Sub-feature中，選取一個與 group0中所有 Sub-feature具有相似性的Sub-feature加入group0中；然后，重復以上步驟，把相似度低的或者未處理的正則表達式另行分組為 group1、group2、group3 等。

Sub-feature分組后， 對每個組 group0、group1、group2及group3等分別進行DFA轉換，分組轉換后的DFA要比沒有分組直接轉換DFA所需要的狀態(tài)數(shù)少,有效地降低了系統(tǒng)資源使用率。

2.3 檢驗

經過上述的猜測和分組過程可以將大部分不滿足條件的輸入過濾掉,只剩少數(shù)數(shù)據可以與某條規(guī)則中的網絡數(shù)據流所有特征子塊相匹配從而需要進行完整驗證過程。因此可以使用速度相對較慢、但內存需求較低的NFA來完成。NFA是通過從特征子塊中提取的各條完整規(guī)則，經過Thompson構造法轉換得到的。該檢驗方法通過占用系統(tǒng)內存資源不大的NFA來實現(xiàn)，保證了匹配結果的精確性。

為方便描述現(xiàn)定義：S表示規(guī)則中所有的正則表達式集合，r為集合中的正則表達式，rk為 Sub-feature，Gd表示基于相似度算法分組數(shù)：

該算法首先從正則表達式中搜索出Sub-feature作為猜測條件，根據相似性算法函數(shù)ES計算所有Subfeature的相似度,并選出相似度大于70%的 Sub-feature，儲存在分組函數(shù) groupi(i=0,1,2,…,d-1)中，共有 d個分組。在輸入前，通過函數(shù)make_DFA、make_NFA生成預處理的DFA和NFA。當有輸入時，算法進行匹配，若輸入能夠滿足猜測并與DFA匹配成功，則對輸入的完整規(guī)則進行NFA匹配。

3 實驗結果與分析

正則表達式匹配算法性能是否優(yōu)越的一個評價標準是系統(tǒng)內存占用率。本實驗將猜測-檢驗算法進行對比和分析。實驗采用的正則表達式來自Linux Lay er-7 filter(L7)以及snort規(guī)則集中常用的 Web-misc規(guī)則類；并用編譯工具在VC上生成NFA和DFA。

實驗配置：主機 CPU頻率 2.69 GHz；1.99 GB內存；Window XP操作系統(tǒng),網絡配置器是Realtek RTL8169/8110 Family Gigabit Ethernet NIC。

實驗步驟：(1)在 L7和snort規(guī)則集中提取出Subfeature；(2)采用式(1)中字符串相似性算法把相似性大于70%的Sub-feature分為一組，實驗中對L7和Web-misc類的Sub-feature進行分組；(3)將每組中的正則表達式分別通過編譯工具生成DFA，并最終合并為一個DFA；(4)對比猜測-檢驗算法。

實驗結果與分析：表1、表2分別給出了 L7和 snort中的Web-misc規(guī)則采用本文算法與猜測-檢驗算法所占內存需求對比。由實驗結果可以看出,基于L7規(guī)則庫，猜測-分組-檢驗算法所占用的內存比猜測-驗證算法減少了35%；而基于snort中Web-misc規(guī)則庫，猜測-分組-檢驗算法所占用的內存比猜測-驗證算法減少了5%，且猜測-分組-檢驗算法的DFA狀態(tài)數(shù)大幅度小于猜測-驗證算法。由此可知,本文所提正則表達式算法能更有效地減少系統(tǒng)內存資源的使用。本文在深入學習、研究正則表達式和探討了優(yōu)化

表1 L7規(guī)則上的內存需求對比

表2 snort中Web-misc規(guī)則上的內存需求對比

NFA與DFA的基礎上,借鑒一些經典的正則表達式匹配算法提出了一種新的面向網絡數(shù)據流正則表達式匹配算法：猜測-分組-檢驗算法。這種算法首先使用分組算法對正則表達式中的Sub-feature進行相似性分組，然后完成對輸出的特征子塊猜測，最后將通過猜測的輸出進行完整的NFA檢驗。算法通過對比猜測-驗證算法進行實驗分析，驗證了該算法具備系統(tǒng)內存資源占用率低和匹配能力強的優(yōu)點。

參考文獻

[1]AHO A V,CORASIEK M J.Effieient string matehing：an aid to bibliographic searerch[J].Communications of the ACM,1975,18(6)：333-340.

[2]WALTER B C.A string matching algorithm fast on the average[J].Processing of ICALP,1979,71(7)：118-132.

[3]WU S,MANBER U.A fast algorithm for multi-pattern searching[C].Department of Computer Science,1994.

[4]Qi Deyu,Qian Zhengping,Zheng Weipin.Fast dynamic pattern matching for deep packet inspection[C].Proceedings of 2008 IEEE International Conference on Networking,Sensing and Contriol,ICNSC,2008.

[5]SOMMER R,PAXSON V.Elthaneing byte-level network intrusion deteetion signatures with context[C].ACM conf,on Computer and Communication Security,2003.

[6]KUMAR S,DHARMAPURIKAR S,YU F.Algorithms to accel-erate multiple regular expressions matching for deep packet inspection[J].Computer Communication Review,2006,36(4)：339-350.

[7]KUMAR S,TUMER J,WILLIAMS J.Advanced algorithms for fast and scalable deep packet inspection[C].ACM,2006.

[8]YU F,CHEN Z F,DIAO Y L,et al.Fast and memoryefficient regular expression matching for deep packet inspection[C].In：Proc.of the IEEE/ACM Symp.on Architectures for Networking and Communications Systems.San Jose,2006.

[9]BECCHI M,CROWLEY P.A hybrid finite automaton for practical deep packet inspection[C].In：Processing of the ACM CoNEXT 2007,2007.

[10]張樹壯,羅浩,方濱興，等.一種面向網絡安全檢測的高性能正則表達式匹配算法[J].計算機學報,2010,33(10)：1976-1986.