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

    在深度報(bào)文檢測(cè)技術(shù)上，經(jīng)典的字符串匹配算法有單模式匹配的KMP和BM算法,改進(jìn)的多模式匹配的AC算法、CM算法、WANG方法和Wu-Manber算法，然而這些算法都采用字符串匹配為基礎(chǔ)。隨著網(wǎng)絡(luò)的不斷發(fā)展，應(yīng)用軟件特征字符識(shí)別的復(fù)雜度越來(lái)越大，采用字符串匹配已難以匹配識(shí)別，因此這些算法的局限性也凸顯出來(lái)?；?a class="innerlink" href="http://ihrv.cn/tags/正則表達(dá)式" title="正則表達(dá)式" target="_blank">正則表達(dá)式的多模式匹配具備了優(yōu)越的表達(dá)匹配能力和靈活性，相比傳統(tǒng)的字符串匹配更加精確高效。
    基于正則表達(dá)式的多模式匹配是把正則表達(dá)式轉(zhuǎn)變?yōu)樽詣?dòng)機(jī)，自動(dòng)機(jī)分為兩種：非確定有限自動(dòng)機(jī)(NFA)和確定有限自動(dòng)機(jī)(DFA)。NFA的優(yōu)點(diǎn)是占用內(nèi)存和系統(tǒng)資源少，但是需要對(duì)每個(gè)字符進(jìn)行遍歷，處理狀態(tài)集里的所有狀態(tài)，很耗費(fèi)時(shí)間。如good(day|night|evening):若要搜goodday，NFA需要把goodday、goodnight、goodevening全部遍歷一次才能完成搜索。相比之下，DFA搜索一個(gè)字符只需要訪問(wèn)一個(gè)狀態(tài),但是若把所有的正則表達(dá)式都轉(zhuǎn)變?yōu)镈FA將會(huì)占用非常大的系統(tǒng)內(nèi)存資源，目前的硬件條件還無(wú)法滿足這一點(diǎn)。
       結(jié)合NFA和DFA各自的優(yōu)缺點(diǎn)，本文提出了一種猜測(cè)-分組-檢驗(yàn)的匹配算法。使用DFA在猜測(cè)的基礎(chǔ)上添加分組，能夠更有效減少系統(tǒng)內(nèi)存占用率；然后再結(jié)合NFA檢測(cè)確保算法具備高匹配度。
1 正則表達(dá)式相關(guān)算法
       深度報(bào)文包檢測(cè)技術(shù)是基于系統(tǒng)規(guī)則庫(kù)對(duì)在網(wǎng)絡(luò)中捕獲的數(shù)據(jù)包中的每一個(gè)字節(jié)進(jìn)行掃描和識(shí)別，標(biāo)準(zhǔn)的字符串匹配算法有:Aho-Corasiek[1]、 ComentZ-Walter[2]和Wu-Manber[3]算法。如今隨著網(wǎng)絡(luò)協(xié)議復(fù)雜度日益增加，傳統(tǒng)的字符串匹配算法難以精確地識(shí)別出復(fù)雜多變的協(xié)議類型[4]。
       SOMMER R和PAXSON V[5]認(rèn)為，用正則表達(dá)式描述網(wǎng)絡(luò)中數(shù)據(jù)協(xié)議行為比用字符串表達(dá)更為高效、靈活。KUMAR S[6]等通過(guò)將DFA的某些狀態(tài)用單條缺省邊來(lái)代替，提出一種稱為延遲輸入DFA，實(shí)驗(yàn)結(jié)果表明,相比于傳統(tǒng)的DFA存儲(chǔ)空間可減少95%以上。但是引入缺省邊導(dǎo)致處理一個(gè)字符需要多次訪問(wèn)內(nèi)存，參考文獻(xiàn)[7]對(duì)參考文獻(xiàn)[6]進(jìn)行改進(jìn),提出一種目錄尋址的D2FA-CD2FA，用包含部分狀態(tài)信息的目錄標(biāo)簽來(lái)代替狀態(tài)的ID，而這些信息一般是保存在狀態(tài)表的條目中，使得一次轉(zhuǎn)移只消耗一個(gè)字符。
      YU F等人提出了將正則表達(dá)式進(jìn)行分組的思想[8]。其方法是：計(jì)算正則表達(dá)式兩兩之間是否引起狀態(tài)增長(zhǎng)，在進(jìn)行分組時(shí)，選擇一條與其他表達(dá)式具有最小相關(guān)度的正則表達(dá)式開(kāi)始，然后按照相同的原則向這個(gè)組里不斷添加，直到這個(gè)組形成的DFA內(nèi)存超過(guò)預(yù)先設(shè)定的閾值，再開(kāi)始創(chuàng)建另一個(gè)新組。重復(fù)這個(gè)過(guò)程，直到所有的表達(dá)式都被分配出去為止。
      參考文獻(xiàn)[9]提出了一種混合自動(dòng)機(jī)的方法，其基本思想是：將整個(gè)規(guī)則集編譯成一個(gè)NFA 結(jié)構(gòu)之后，并不對(duì)它進(jìn)行完全的確定化，而是在確定化之前判斷狀態(tài)之間跳轉(zhuǎn)的原因。進(jìn)行部分確定化的結(jié)果就是形成了一個(gè)混合的自動(dòng)機(jī)結(jié)構(gòu)，它的前面一部分是DFA的狀態(tài)，而在每個(gè)邊界狀態(tài)之后都帶有一個(gè)NFA，這個(gè)NFA以邊界狀態(tài)作為初始狀態(tài)。
       張樹(shù)壯等人提出了一種基于猜測(cè)-驗(yàn)證的匹配方法[10]：首先使用DFA對(duì)正則表達(dá)式中的部分子特征進(jìn)行搜索，完成特征存在性的猜測(cè)。當(dāng)猜測(cè)到有可能匹配某個(gè)特征后，再使用NFA進(jìn)行驗(yàn)證。這種方法既充分利用了DFA的高效性，減少了對(duì)相對(duì)較慢的驗(yàn)證過(guò)程,又借助NFA避免了內(nèi)存消耗過(guò)于巨大。
       本文在深入研究和分析以上算法的基礎(chǔ)上，針對(duì)DPI規(guī)則庫(kù)這樣十分龐大的規(guī)則系統(tǒng)，借鑒一些經(jīng)典正則表達(dá)式匹配算法，提出一種猜測(cè)-分組-檢驗(yàn)算法。該算法把分組作為核心步驟，利用正則表達(dá)式之間的相關(guān)性組合后進(jìn)行分組，能夠十分有效地降低系統(tǒng)內(nèi)存資源的使用率。結(jié)合NFA驗(yàn)證，該算法能夠?qū)斎脒M(jìn)行有效的匹配和識(shí)別。
2 算法描述
    正則表達(dá)式匹配算法分為三個(gè)步驟：猜測(cè)、分組和檢驗(yàn)?？傮w來(lái)說(shuō)，在安全監(jiān)控中所使用的規(guī)則一般都可以分為若干個(gè)特征子塊Sub-feature，如圖1所示，每個(gè)子特征之間通過(guò)正則表達(dá)式運(yùn)算符連接在一起。獲取到這些特征子塊之后，可以簡(jiǎn)單地把它們合并轉(zhuǎn)換為一個(gè)DFA。然而這樣一個(gè)DPI的規(guī)則庫(kù)，將會(huì)占用十分龐大的系統(tǒng)內(nèi)存資源。所以在獲得特征子塊后，需要采用相似性度分析對(duì)這些子塊進(jìn)行分組，把相似程度高的子塊聚合在一起，并通過(guò)子集構(gòu)造法轉(zhuǎn)換為一個(gè)DFA,再通過(guò)正則運(yùn)算符把各個(gè)組的DFA連接在一起。分組后的DFA占用系統(tǒng)內(nèi)存資源小，可以有效減少空間使用率，進(jìn)而提高資源的有效利用率。若某個(gè)輸入與猜測(cè)選擇出的特征子塊匹配，則把輸入進(jìn)行NFA驗(yàn)證，驗(yàn)證方法是基于DPI庫(kù)中的每條規(guī)則轉(zhuǎn)變?yōu)镹FA得到的。

    其中S1和S2分別為代表兩個(gè)需做比較的正則表達(dá)式， ED(S1,S2)是指S1和S2之間編輯距離，max(|S1|,|S2|)是選擇兩個(gè)正則表達(dá)式中字符多的一個(gè)。若兩個(gè)正則表達(dá)式完全一樣，則計(jì)算結(jié)果為1；若兩個(gè)正則表達(dá)式完全不同，則計(jì)算結(jié)果為0。式(1)的字符串相似度算法復(fù)雜度小、精確度大，采用其進(jìn)行相似度計(jì)算能夠有效減少內(nèi)存消耗并且確保極高的匹配率。
    采用上述的相似性計(jì)算法將每個(gè)Sub-feature進(jìn)行相似度分析并分組。首先，在所有未分組的Sub-feature中選取一個(gè)與其他Sub-feature具有相似性的Sub-feature加入一個(gè)新組并記為group0；其次，在所有未處理的Sub-feature中，選取一個(gè)與group0中所有Sub-feature具有相似性的Sub-feature加入group0中；然后，重復(fù)以上步驟，把相似度低的或者未處理的正則表達(dá)式另行分組為group1、group2、group3等。
　    Sub-feature分組后，對(duì)每個(gè)組group0、group1、group2及group3等分別進(jìn)行DFA轉(zhuǎn)換，分組轉(zhuǎn)換后的DFA要比沒(méi)有分組直接轉(zhuǎn)換DFA所需要的狀態(tài)數(shù)少,有效地降低了系統(tǒng)資源使用率。
2.3 檢驗(yàn)
       經(jīng)過(guò)上述的猜測(cè)和分組過(guò)程可以將大部分不滿足條件的輸入過(guò)濾掉,只剩少數(shù)數(shù)據(jù)可以與某條規(guī)則中的網(wǎng)絡(luò)數(shù)據(jù)流所有特征子塊相匹配從而需要進(jìn)行完整驗(yàn)證過(guò)程。因此可以使用速度相對(duì)較慢、但內(nèi)存需求較低的NFA來(lái)完成。NFA是通過(guò)從特征子塊中提取的各條完整規(guī)則，經(jīng)過(guò)Thompson構(gòu)造法轉(zhuǎn)換得到的。該檢驗(yàn)方法通過(guò)占用系統(tǒng)內(nèi)存資源不大的NFA來(lái)實(shí)現(xiàn)，保證了匹配結(jié)果的精確性。
    為方便描述現(xiàn)定義：S表示規(guī)則中所有的正則表達(dá)式集合，r為集合中的正則表達(dá)式，rk為Sub-feature，Gd表示基于相似度算法分組數(shù):
For(rk∈S)
    {
　　For (d=0;d<diff;d++)
            For(k=0;k<max;k++)
            {
                If(ES(rd,rk)>=0.7)
                Gd=group(rk,k);
　　        }
    }
DFA=make_DFA(Gd);
NFA=make_NFA(S);
If（Wait(P)==1）
{
For(i=0;i<sizeoff(P);i++)
A=dfa_match(DFA,pi);
If(A&isin;DFA.OK)
nfa_match(NFA,P)
}
    該算法首先從正則表達(dá)式中搜索出Sub-feature作為猜測(cè)條件，根據(jù)相似性算法函數(shù)ES計(jì)算所有Sub-feature的相似度,并選出相似度大于70%的Sub-feature，儲(chǔ)存在分組函數(shù)groupi(i=0,1,2,&hellip;,d-1)中，共有d個(gè)分組。在輸入前，通過(guò)函數(shù)make_DFA、make_NFA生成預(yù)處理的DFA和NFA。當(dāng)有輸入時(shí)，算法進(jìn)行匹配，若輸入能夠滿足猜測(cè)并與DFA匹配成功，則對(duì)輸入的完整規(guī)則進(jìn)行NFA匹配。
3 實(shí)驗(yàn)結(jié)果與分析
     正則表達(dá)式匹配算法性能是否優(yōu)越的一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)是系統(tǒng)內(nèi)存占用率。本實(shí)驗(yàn)將猜測(cè)-檢驗(yàn)算法進(jìn)行對(duì)比和分析。實(shí)驗(yàn)采用的正則表達(dá)式來(lái)自Linux Lay er-7 filter(L7)以及snort規(guī)則集中常用的Web-misc規(guī)則類；并用編譯工具在VC上生成NFA和DFA。
     實(shí)驗(yàn)配置:主機(jī)CPU頻率2.69 GHz；1.99 GB內(nèi)存；Window XP操作系統(tǒng),網(wǎng)絡(luò)配置器是Realtek RTL8169/8110 Family Gigabit Ethernet NIC。
　  實(shí)驗(yàn)步驟： (1)在L7和snort規(guī)則集中提取出Sub-feature；(2)采用式(1)中字符串相似性算法把相似性大于70%的Sub-feature分為一組，實(shí)驗(yàn)中對(duì)L7和Web-misc類的Sub-feature進(jìn)行分組； (3)將每組中的正則表達(dá)式分別通過(guò)編譯工具生成DFA，并最終合并為一個(gè)DFA；(4)對(duì)比猜測(cè)-檢驗(yàn)算法。
     實(shí)驗(yàn)結(jié)果與分析：表1、表2分別給出了L7和snort中的Web-misc規(guī)則采用本文算法與猜測(cè)-檢驗(yàn)算法所占內(nèi)存需求對(duì)比。由實(shí)驗(yàn)結(jié)果可以看出,基于L7規(guī)則庫(kù)，猜測(cè)-分組-檢驗(yàn)算法所占用的內(nèi)存比猜測(cè)-驗(yàn)證算法減少了35%；而基于snort中Web-misc規(guī)則庫(kù)，猜測(cè)-分組-檢驗(yàn)算法所占用的內(nèi)存比猜測(cè)-驗(yàn)證算法減少了5%，且猜測(cè)-分組-檢驗(yàn)算法的DFA狀態(tài)數(shù)大幅度小于猜測(cè)-驗(yàn)證算法。由此可知,本文所提正則表達(dá)式算法能更有效地減少系統(tǒng)內(nèi)存資源的使用。

    本文在深入學(xué)習(xí)、研究正則表達(dá)式和探討了優(yōu)化NFA與DFA的基礎(chǔ)上,借鑒一些經(jīng)典的正則表達(dá)式匹配算法提出了一種新的面向網(wǎng)絡(luò)數(shù)據(jù)流正則表達(dá)式匹配算法：猜測(cè)-分組-檢驗(yàn)算法。這種算法首先使用分組算法對(duì)正則表達(dá)式中的Sub-feature進(jìn)行相似性分組，然后完成對(duì)輸出的特征子塊猜測(cè)，最后將通過(guò)猜測(cè)的輸出進(jìn)行完整的NFA檢驗(yàn)。算法通過(guò)對(duì)比猜測(cè)-驗(yàn)證算法進(jìn)行實(shí)驗(yàn)分析，驗(yàn)證了該算法具備系統(tǒng)內(nèi)存資源占用率低和匹配能力強(qiáng)的優(yōu)點(diǎn)。
參考文獻(xiàn)
[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 algorithmsfor 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] 張樹(shù)壯,羅浩,方濱興，等.一種面向網(wǎng)絡(luò)安全檢測(cè)的高性能正則表達(dá)式匹配算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(10):1976-1986.