一種高效的正則表達(dá)式dfa存儲方法

由于網(wǎng)絡(luò)安全的需要，深度包檢測變得越來越重要，多模式匹配是最重要的技術(shù)。現(xiàn)在，基于其靈活性和效率的表達(dá)能力，正統(tǒng)表達(dá)的df（definemata）具有更好的處理性能，而非正統(tǒng)表達(dá)的df（非正統(tǒng)表面活性劑）具有更高的處理性能，但占用的內(nèi)存區(qū)域是最大的問題。因此，本文主要討論df的存儲壓縮。1正則表達(dá)式存儲壓縮深度包檢測,即掃描數(shù)據(jù)包的包頭及有效載荷內(nèi)容,對網(wǎng)絡(luò)安全及網(wǎng)絡(luò)監(jiān)控至關(guān)重要.許多重要的網(wǎng)絡(luò)處理應(yīng)用都需要深度包檢測,比如入侵檢測系統(tǒng)、防御系統(tǒng)和防火墻等,且當(dāng)前大多數(shù)系統(tǒng)是軟件實現(xiàn)的.在深度包檢測中,多模式匹配是實現(xiàn)數(shù)據(jù)包掃描的核心技術(shù),即通過掃描一次文本,找出模式集合中的模式在文本中的所有出現(xiàn).傳統(tǒng)的多模式匹配,其模式是多個精確字符串(例如apple,banana)的集合.由于通配符、字符集合等正則特征,正則表達(dá)式具有很強的表達(dá)能力和靈活性,一個正則表達(dá)式本身就是一組字符串的集合.正則表達(dá)式正在替換精確的字符串成為可選取的模式匹配語言.當(dāng)前,幾個內(nèi)容檢測引擎已經(jīng)添加了對正則表達(dá)式的支持,比如Snort入侵檢測系統(tǒng)、Bro入侵檢測系統(tǒng)、Linux應(yīng)用協(xié)議分類器(L7-filter)等.基于正則表達(dá)式的多模式匹配,其原理是將正則表達(dá)式構(gòu)造成FSM(finitestatesmachine),再用FSM對文本進行掃描,從而實現(xiàn)模式在文本中的出現(xiàn).DFA因其處理性能比NFA好而成為了首選的自動機形式,但DFA需要很大的存儲空間,這是當(dāng)前最嚴(yán)重的限制因素.因此,本文主要針對DFA的存儲壓縮進行討論.DFA的存儲空間是由狀態(tài)點數(shù)目和每個狀態(tài)點的狀態(tài)轉(zhuǎn)移數(shù)目共同決定的,文中對這兩方面分別進行了探討.首先,對FSM的狀態(tài)點數(shù)目進行壓縮,提出了一種復(fù)合的FSM的構(gòu)造方法,通過對正則表達(dá)式轉(zhuǎn)化成DFA的狀態(tài)點數(shù)目復(fù)雜度的分析,將不同復(fù)雜度的正則表達(dá)式采用不同的方式構(gòu)建FSM,使得所有平方級和指數(shù)級復(fù)雜度的狀態(tài)點數(shù)目降低到了線性級.其次,對DFA的狀態(tài)轉(zhuǎn)移數(shù)目進行壓縮,給出了一種高效的壓縮算法,即WD2FA(weighteddelayedinputDFA)算法,該算法尤其對于復(fù)雜的正則表達(dá)式具有更好的壓縮效果,且相對于D2FA(dDelayedinputDFA)有更強的壓縮能力,使得D2FA是WD2FA在權(quán)值為0情況下的特例.本文第2節(jié)介紹FSM存儲壓縮的相關(guān)工作.第3節(jié)針對狀態(tài)點數(shù)目進行壓縮.第4節(jié)是狀態(tài)轉(zhuǎn)移數(shù)目的壓縮算法.第5節(jié)給出壓縮算法的整體結(jié)構(gòu).第6節(jié)是實驗性能結(jié)果.最后第7節(jié)對全文進行總結(jié).2背景和相關(guān)工作2.1nfa的空間和處理復(fù)雜度為了對存儲空間進行壓縮,首先考慮正則表達(dá)式是如何表示的.正則表達(dá)式都是用FSM來表示,它有兩種邏輯形式:DFA和NFA.對于任意的正則表達(dá)式,都對應(yīng)有一個具有最少狀態(tài)點數(shù)目的DFA.DFA用五元組(Q,Σ,q0,δ,A)表示,其中,Q為狀態(tài)點集合,Σ為字符表,q0為初始狀態(tài)點,A為終止?fàn)顟B(tài)點,δ為狀態(tài)轉(zhuǎn)移函數(shù).一個DFA有且只有一個初始狀態(tài)點作為匹配的起點,之后每掃描文本中的一個字符,則根據(jù)轉(zhuǎn)移函數(shù)δ確定下一個狀態(tài)點,當(dāng)遇到終止?fàn)顟B(tài)點(終止?fàn)顟B(tài)點可有多個)時,則產(chǎn)生一個模式輸出.NFA與DFA的區(qū)別在于,NFA的轉(zhuǎn)移函數(shù)δ確定了一個或者多個下一狀態(tài)點,而DFA的轉(zhuǎn)移函數(shù)δ確定唯一的下一狀態(tài)點.FSM所需要的存儲空間是由狀態(tài)點數(shù)目和每個狀態(tài)點的狀態(tài)轉(zhuǎn)移數(shù)目共同決定的.在網(wǎng)絡(luò)處理過程中,字符表是擴展的ASCII碼,這樣,每個狀態(tài)點有256個狀態(tài)轉(zhuǎn)移.包含數(shù)百條正則表達(dá)式的規(guī)則集,在構(gòu)建DFA時將有數(shù)萬個狀態(tài)點,以至于需要數(shù)百兆的存儲空間.隨著正則表達(dá)式數(shù)目的增加,空間需求將是不可容忍的.FSM的空間和處理復(fù)雜度見表1.當(dāng)輸入一個字符時,DFA能夠確定唯一的下一狀態(tài)點,因此處理復(fù)雜度為O(1).而NFA由于它的不確定性,處理一個字符時的最壞復(fù)雜度為O(n2).DFA雖然處理復(fù)雜度很好,但其實際上是用更多的狀態(tài)點記錄了NFA處理字符的不確定性分枝,以至于空間復(fù)雜度要比NFA大得多.從理論上講長度為n的正則表達(dá)式構(gòu)建的DFA需要狀態(tài)點數(shù)目為O(2n),構(gòu)建的NFA需要的狀態(tài)點數(shù)目為O(n).對于含有m條正則表達(dá)式的集合,有3種方法可以表示:將其表示成為m個獨立的FSM;將其合并成一個FSM;將其表示成k(k<m)個獨立的FSM,也即將m條規(guī)則分成k組,每組合并成一個獨立的FSM.對于DFA,多個DFA合并可以提高處理性能.若表示成k個獨立的FSM,則其處理一個字符的復(fù)雜度為O(k),但k值越小,DFA占用的空間越大.為了達(dá)到最佳性能,應(yīng)該對規(guī)則分組采取折衷選擇.對于NFA,合并不能提高處理性能.第2.2節(jié)和第2.3節(jié)介紹當(dāng)前對DFA的優(yōu)化算法和相關(guān)工作,包括處理性能(或者稱為吞吐量)的優(yōu)化和存儲空間的優(yōu)化,此外,還有硬件上的相關(guān)應(yīng)對方案.文獻較全面地介紹了深度包檢測問題和相關(guān)算法.2.2狀態(tài)轉(zhuǎn)移擴展原理吞吐量(throughout)是指FSM經(jīng)過一次狀態(tài)轉(zhuǎn)移能夠處理的字符個數(shù),用以衡量FSM的處理性能.DFA的處理能力為經(jīng)過一次狀態(tài)轉(zhuǎn)移處理一個字符.一種改進方法是,對DFA的狀態(tài)轉(zhuǎn)移表進行擴展,即對字符表進行笛卡爾乘積,生成新的狀態(tài)轉(zhuǎn)移表,使其在處理時每次能夠讀入多個字符.狀態(tài)轉(zhuǎn)移擴展的原理如下:δ(u,ab)=δ(δ(u,a),b).在這個式子中,u代表初始狀態(tài)點,a與b代表字符激勵.利用擴展的狀態(tài)轉(zhuǎn)移表,狀態(tài)點u經(jīng)過兩個字符ab的激勵可以直接產(chǎn)生輸出,輸出的下一狀態(tài)點等于狀態(tài)點u先經(jīng)過字符激勵a再經(jīng)過字符激勵b產(chǎn)生的下一狀態(tài)點.對轉(zhuǎn)移表的擴展,使得狀態(tài)轉(zhuǎn)移數(shù)目劇增,也即存儲空間變得很大,因此必須對其進行壓縮.2.3位圖壓縮技術(shù)正則表達(dá)式的rewrite技術(shù),其前提是采用最左最短匹配方式(leftshortestmatching)掃描數(shù)據(jù),在不影響匹配結(jié)果的情況下對部分正則表達(dá)式進行改寫,從而減少了DFA的狀態(tài)點數(shù)目.表壓縮算法是將字符表中的字符進行等價劃分和重新編碼(當(dāng)同一等價類中的字符,作為任意狀態(tài)點的激勵時,產(chǎn)生相同的下一狀態(tài)點),字符個數(shù)從256減少到了等價類的個數(shù),從而降低了狀態(tài)轉(zhuǎn)移的數(shù)目.D2FA存儲壓縮技術(shù)是針對狀態(tài)轉(zhuǎn)移的壓縮技術(shù).在DFA中,對于任意兩個狀態(tài)點u和v,某些相同的激勵可能產(chǎn)生相同的狀態(tài)點輸出,即δ(u,a)=δ(v,a).對于所有類似字符a產(chǎn)生的狀態(tài)轉(zhuǎn)移,只在狀態(tài)點u中加以保留而在狀態(tài)點v中去除所有的這些狀態(tài)轉(zhuǎn)移并為其添加一個稱為默認(rèn)狀態(tài)轉(zhuǎn)移(defaulttransitions)的狀態(tài)轉(zhuǎn)移到狀態(tài)點u.這樣,當(dāng)在狀態(tài)點v中匹配類似a的字符時,首先默認(rèn)轉(zhuǎn)移到u,再由u決定下一狀態(tài)點.位圖壓縮也是一種針對狀態(tài)轉(zhuǎn)移的壓縮算法,它用256個連續(xù)的bit位對應(yīng)于ASCII碼,標(biāo)識出字符激勵的類別.文獻中,從某個狀態(tài)點出發(fā),若存在某個字符為激勵,則將對應(yīng)的bit位標(biāo)識為1,否則,標(biāo)識為0.文獻中,從某個狀態(tài)點出發(fā),若某個字符激勵要經(jīng)由D2FA的默認(rèn)轉(zhuǎn)移,則將對應(yīng)的bit位標(biāo)識為1,否則,標(biāo)識為0.規(guī)則集的分組(grouping)技術(shù)將多個DFA合并成一個DFA,以提高處理性能.為了不增加額外的存儲空間,采用如下處理方法:對所有DFA進行劃分,劃分子塊的數(shù)量要達(dá)到最少,并且每一個劃分子塊合并成的DFA狀態(tài)點數(shù)目不超過對應(yīng)劃分子塊各DFA狀態(tài)點數(shù)目的總和.此外,采用硬件平臺,借助并行技術(shù)可以達(dá)到很好的性能.硬件結(jié)構(gòu)有兩種實現(xiàn)策略:其一,將DFA制成硬件邏輯:當(dāng)處理一個字符時是并行處理的,使得處理字符的復(fù)雜度為O(1).采用這種策略要考慮規(guī)則集的更新即硬件邏輯需要重新配置(reconfiguration),于是FPGA是一個很好的選擇.另外,當(dāng)規(guī)則集數(shù)目較大時,硬件資源消耗也大,必須進行存儲壓縮;其二,基于存儲器的硬件設(shè)計:將FSM存儲在存儲器中,這樣,可以根據(jù)存儲器的數(shù)目和類型進行靈活的設(shè)計.但為了將FSM存于片內(nèi)存儲器中,對空間的壓縮有更為嚴(yán)格的要求.3復(fù)合的fsm技術(shù)正則表達(dá)式的一些正則特征導(dǎo)致了對應(yīng)的DFA要占用巨大的存儲空間.文獻在分析了正則特征的基礎(chǔ)上提出了正則表達(dá)式的rewrite技術(shù),從而減少了一部分DFA的狀態(tài)點數(shù)目.本節(jié)對正則特征進行了更加詳細(xì)的分析,之后提出復(fù)合的FSM的解決方案,從而使所有平方級和指數(shù)級復(fù)雜度的狀態(tài)點數(shù)目降低到線性級.第3.1節(jié)對正則表達(dá)式生成DFA的狀態(tài)點數(shù)目的復(fù)雜度進行了分析.在此基礎(chǔ)上,第3.2節(jié)提出了復(fù)合的FSM的構(gòu)建方法.第3.3節(jié)~第3.5節(jié)給出了實現(xiàn)復(fù)合的FSM的相關(guān)技術(shù).3.1基于狀態(tài)點數(shù)目的狀態(tài)點數(shù)目增長構(gòu)建復(fù)雜度在這里是指正則表達(dá)式生成DFA的狀態(tài)點數(shù)目的復(fù)雜度.長度為n的正則表達(dá)式最壞情況下的構(gòu)建復(fù)雜度為O(2n).然而在實際情況中,構(gòu)建復(fù)雜度大多數(shù)呈線性級或者平方級.經(jīng)過對具體實驗數(shù)據(jù)的分析,表2給出了詳細(xì)的構(gòu)建復(fù)雜度,其中K代表正則表達(dá)式的長度.我們以∧AB.{0,j}CD為例,說明DFA的線性構(gòu)造過程.在構(gòu)建DFA時,j每增1,則需要增加一個并列結(jié)構(gòu)的分枝,引出一個C與非C的狀態(tài)點,這樣的狀態(tài)點數(shù)目為K+2j+1.需要平方復(fù)雜度構(gòu)造DFA的正則表達(dá)式有∧A+.{j}D,其狀態(tài)點數(shù)目提升的原因是DFA需要記錄A+與.{j}的重疊.在構(gòu)建DFA時,狀態(tài)點數(shù)目的多項式級增長是由字符集合和長度限制{j}的組合引起的,與K無關(guān).如果正則表達(dá)以.*開頭,并包含字符集合與長度限制的組合,構(gòu)建時狀態(tài)點數(shù)目的增長就呈現(xiàn)出了指數(shù)級的復(fù)雜度,當(dāng)掃描文本到達(dá)某個狀態(tài)點時,若出現(xiàn)不能繼續(xù)向前匹配的情況,就需要從當(dāng)前狀態(tài)點回退,而狀態(tài)點數(shù)目的指數(shù)級增長原因就在于要記錄大量的回退信息∧AB[∧

]*CD.{j}EF是一種較為特殊的形式,其雖然以定位符∧開始,但中間的[∧

]*充當(dāng)了.*的作用,使得整個正則表達(dá)式與.*CD.{j}EF一樣具有指數(shù)級的復(fù)雜度.3.2復(fù)合fsm的實現(xiàn)方法根據(jù)正則表達(dá)式構(gòu)建DFA狀態(tài)點數(shù)目的復(fù)雜度,將不同復(fù)雜度類型的正則表達(dá)式構(gòu)建成不同類型的FSM由這些不同類型的FSM組合成的FSM稱為復(fù)合的FSM(hybridFSM).高復(fù)雜度正則表達(dá)式中的幾個或者一個所占用的存儲空間就是無法容忍的.因此,復(fù)合的FSM的實現(xiàn)目標(biāo)為:從規(guī)則集中把所有構(gòu)建成DFA后對應(yīng)有平方級和指數(shù)級狀態(tài)點數(shù)目的正則表達(dá)式無一遺漏地挑選出來,并轉(zhuǎn)換成特殊的DFA,以將狀態(tài)點數(shù)目的復(fù)雜度降低到線性級.復(fù)合FSM的實現(xiàn)方法如圖1所示.先對正則表達(dá)式集合(規(guī)則集)按照構(gòu)建DFA的復(fù)雜度進行分類.然后線性級復(fù)雜度對應(yīng)的正則表達(dá)式轉(zhuǎn)化為普通的DFA;平方級復(fù)雜度對應(yīng)的正則表達(dá)式,具有∧A+.{j}形式的先用rewrite技術(shù)進行改寫,再轉(zhuǎn)化為普通的DFA,具有∧A+.{j}D形式的,轉(zhuǎn)化為帶計數(shù)器的DFA;指數(shù)級復(fù)雜度對應(yīng)的正則表達(dá)式,具有.*AB.{j}和∧AB[∧

]*CD.{j}形式的用rewrite技術(shù)轉(zhuǎn)化為普通的DFA,具有.*AB.{j}CD和∧AB[∧

]*CD.{j}EF形式的,轉(zhuǎn)化為LazyDFA.3.3我國最左最短匹配規(guī)則Rewrite技術(shù)的原理,是在不影響匹配結(jié)果的情況下(采用最左最短的匹配方式),對具有某些特征的正則表達(dá)式進行改寫,從而達(dá)到減少DFA狀態(tài)點數(shù)目的目的.Rewrite技術(shù)形成了兩條改寫規(guī)則:規(guī)則1.將具有∧A+.{j}特征的正則表達(dá)式改寫為∧A.{j},這樣,狀態(tài)點數(shù)目降低到了K+j.規(guī)則2.主要針對.*AB.{j}或者.*AB[A-Z]{j}形式的正則表達(dá)式,實際上就是遵從最左最短的方式進行匹配這樣生成的DFA狀態(tài)點數(shù)目為K+j.基于第3.1節(jié)對正則表達(dá)式復(fù)雜度的分析,這里增加一條rewrite規(guī)則,即:規(guī)則3.對∧AB[∧

]*CD.{j}形式的正則表達(dá)式,用最左最短匹配方式構(gòu)建DFA,這樣,狀態(tài)點數(shù)目為K+j.Rewrite技術(shù)可以將一部分平方級和指數(shù)級構(gòu)建復(fù)雜度的正則表達(dá)式改寫為具有線性級復(fù)雜度的正則表達(dá)式,但只能改寫以長度限制(即{j})為后綴的正則表達(dá)式,無法處理∧A+.{j}D,∧AB[∧

]*CD.{j}EF或者.*AB.{j}D形式的正則表達(dá)式.也即這3種形式的正則表達(dá)式一旦按照前邊的方法改寫,將無法得出正確的匹配輸出.針對rewrite技術(shù)的不足,本文采用如下應(yīng)對方法:對于∧A+.{j}D形式的正則表達(dá)式,提出了帶計算器的DFA;對于.*AB.{j}D和∧AB[∧

]*CD.{j}形式的正則表達(dá)式,采用LazyDFA.第3.4節(jié)和第3.5節(jié)描述了這些方法3.4帶計數(shù)df的f3.4.1狀態(tài)點數(shù)目與nfa所需要的狀態(tài)點數(shù)目關(guān)系以∧B+[∧

]{3}D為例,分析一下具有平方級構(gòu)造復(fù)雜度的正則表達(dá)式轉(zhuǎn)化成FSM的結(jié)構(gòu)特點.圖2(a)為∧B+[∧

]{3}D對應(yīng)的NFA,其狀態(tài)點數(shù)目為O(n).在最壞情況下,處理復(fù)雜度為O(n2).假設(shè)輸入串為BBBBD,匹配過程中形成的狀態(tài)集依次為{0},{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5},由于最后一個狀態(tài)集中含有終止?fàn)顟B(tài)5而使得匹配終止.將各個狀態(tài)集中的狀態(tài)點數(shù)目加起來,可以得到NFA處理時的轉(zhuǎn)移次數(shù).這樣,∧B+[∧

]{j}D對應(yīng)的NFA在最壞情況下的轉(zhuǎn)移次數(shù)為(j+1)(j+2)/2.圖2(b)為∧B+[∧

]{3}D對應(yīng)的DFA,由于字符B在B+與[∧

]{3}中重疊出現(xiàn),DFA必須記錄輸入字符B的每種可能路徑,這樣使其具有了平方級的狀態(tài)點數(shù)目.精確地講,描述B+[∧

]{j}的DFA所需要的狀態(tài)點數(shù)目為(j+1)(j+2)/2,如圖2(b)中的狀態(tài)點1~狀態(tài)點10.通過上述分析可知,DFA中記錄路徑需要的狀態(tài)點數(shù)目與NFA在最壞情況下需要的處理次數(shù)相等.這并非巧合,而是反映了用子集法構(gòu)造DFA的原理,同時也展現(xiàn)了平方級復(fù)雜度的DFA結(jié)構(gòu)是如何形成的.3.4.2dfa的構(gòu)建我們以∧B+[∧

]{3}D為例,解釋具有計數(shù)器的DFA的構(gòu)造方法.如圖3(a)所示:首先將正則表達(dá)式改寫為∧B[∧

]{3}D,并構(gòu)造相應(yīng)的DFA;之后引入一個計數(shù)器counter,用以記錄歷史路徑,即記錄從狀態(tài)點1開始到達(dá)狀態(tài)點4終止的連續(xù)的B的個數(shù).這樣,狀態(tài)點4的轉(zhuǎn)移是由當(dāng)前狀態(tài)點及計數(shù)器共同決定的.狀態(tài)點4的轉(zhuǎn)移信息如圖3(a)所示,計數(shù)器的取值為0~3,相應(yīng)的狀態(tài)4有4種狀態(tài)轉(zhuǎn)移信息.本文將∧B[∧

]{j}D中表示[∧

]{j}的第1個狀態(tài)點(圖3(a)中的狀態(tài)點1)和最后一個狀態(tài)點(圖3(a)中的狀態(tài)點4)分別稱為內(nèi)部起始狀態(tài)點(internalstartState)和內(nèi)部終止?fàn)顟B(tài)點(internalendState);將內(nèi)部起始和終止?fàn)顟B(tài)點以及它們之間的狀態(tài)點稱為內(nèi)部狀態(tài)點(internalstate).帶計數(shù)器的DFA構(gòu)建方法為:先將∧B+[∧

]{j}D改寫成∧B[∧

]{j}D再構(gòu)建成標(biāo)準(zhǔn)的DFA,同時記錄內(nèi)部狀態(tài)點的標(biāo)號.在掃描時要做一些與計數(shù)器相關(guān)的處理:計數(shù)器初始化為0,當(dāng)?shù)竭_(dá)內(nèi)部起始狀態(tài)點后,觸發(fā)計數(shù)器并記錄從內(nèi)部起始狀態(tài)點出發(fā)的連續(xù)B的個數(shù),每有一個連續(xù)的B,則計數(shù)器加1;到達(dá)內(nèi)部終止?fàn)顟B(tài)點后,要結(jié)合計數(shù)器的值共同決定下一轉(zhuǎn)移狀態(tài).∧B+[∧

]{j}D對應(yīng)的計數(shù)器具有0~j的取值范圍,因而內(nèi)部終止?fàn)顟B(tài)具有j+1種狀態(tài)轉(zhuǎn)移信息.通過圖3(a)可以發(fā)現(xiàn),實際上,狀態(tài)轉(zhuǎn)移只有3種,即counter的值劃分為3類:{0},{1~j-1}和{j}.帶計數(shù)器DFA的掃描處理算法如圖3(b)所示.用上述方法構(gòu)造具有計數(shù)器的DFA實現(xiàn)了對∧B+[∧

]{j}D形式的正則表達(dá)式的改寫,使?fàn)顟B(tài)點數(shù)目從平方級降低到了線性級.更為精確地,將表示[∧

]{j}這一部分的需要的狀態(tài)點數(shù)目從(j+1)(j+2)/2減少到了j+1.對于rewrite技術(shù)無法改寫的形如.*AB.{j}D和∧AB[∧

]*CD.{j}EF的正則表達(dá)式,其具有指數(shù)級的狀態(tài)點數(shù)目,這里將其構(gòu)建成lazyDFA.它介于NFA和DFA之間,在NFA掃描處理時計算并存儲實際需要的一些DFA狀態(tài)點,狀態(tài)數(shù)目的復(fù)雜度為O(n),從而將對應(yīng)的正則表達(dá)式的構(gòu)建復(fù)雜度從指數(shù)級降低到了線性級.4ddosf2a帶權(quán)下df為了對DFA狀態(tài)轉(zhuǎn)移的數(shù)目進行壓縮,我們給出了一種高效存儲的算法,即WD2FA(weighteddelayedinputDFA,帶權(quán)延遲DFA).WD2FA比D2FA具有更好的壓縮性能,且D2FA是WD2FA權(quán)值為0情況下的特例.4.1.1化dcfe對兩種DFA狀態(tài)而言,除了有可能存在大量的相同字符激勵指向相同的下一狀態(tài)之外(D2FA的構(gòu)造思路,如圖4(a)所示),如下情況也是經(jīng)常存在的:如圖4(b)所示,取兩個狀態(tài)點u和v,對于大量相同的字符激勵a,使得δ(v,a)=δ(u,a)+W,其中,W為一個整數(shù).類似于D2FA的構(gòu)造思路,只在狀態(tài)u中保留這些相同字符激勵的狀態(tài)轉(zhuǎn)移信息,v中去除這些字符激勵對應(yīng)的轉(zhuǎn)移信息并添加一個帶權(quán)值(W)的默認(rèn)狀態(tài)轉(zhuǎn)移到狀態(tài)u.圖4(b)中,加粗的箭頭代表默認(rèn)轉(zhuǎn)移.假設(shè)狀態(tài)點z的編號值比狀態(tài)點x大2,則權(quán)值W設(shè)置為2.當(dāng)在狀態(tài)點v匹配a這樣的字符時,先由默認(rèn)轉(zhuǎn)移轉(zhuǎn)換到狀態(tài)點u,則下一狀態(tài)的值為權(quán)值2加上u指向的下一狀態(tài)點x,即得到狀態(tài)點z.在圖4(b)中,只有當(dāng)狀態(tài)點x和z是同一個狀態(tài)點時(如圖4(a)所示),才能用D2FA算法進行壓縮.因此我們可以發(fā)現(xiàn),D2FA是WD2FA的所有默認(rèn)轉(zhuǎn)移權(quán)值都為0情況下的特例.4.1.2dfa的下一轉(zhuǎn)移狀態(tài)我們以正則表達(dá)式∧B+.{3}D為例進一步說明WD2FA的工作過程,其狀態(tài)轉(zhuǎn)移矩陣見表3.在表中,‘-’表示沒有下一轉(zhuǎn)移狀態(tài),在實際中應(yīng)該回到起始狀態(tài)點.為了更清楚地說明問題,其值取為-1.DFA的每個狀態(tài)點有256個狀態(tài)轉(zhuǎn)移,這樣,整個DFA有3072個狀態(tài)轉(zhuǎn)移.經(jīng)WD2FA壓縮后,一共只需記錄274個狀態(tài)轉(zhuǎn)移.4.1.3達(dá)到狀態(tài)點的信息,加默轉(zhuǎn)移權(quán)值的獲取在用WD2FA處理字符時,從某個狀態(tài)點出發(fā),先檢測輸入字符對應(yīng)的狀態(tài)轉(zhuǎn)移信息是否為默認(rèn)轉(zhuǎn)移:如果是非默認(rèn)轉(zhuǎn)移,則根據(jù)狀態(tài)轉(zhuǎn)移信息直接到達(dá)下一狀態(tài)點;否則,根據(jù)默認(rèn)轉(zhuǎn)移到的狀態(tài)點和默認(rèn)轉(zhuǎn)移權(quán)值共同決定下一狀態(tài)點,然后再重復(fù)上述操作.若經(jīng)由多次默認(rèn)轉(zhuǎn)移,則要對每次獲取的默認(rèn)轉(zhuǎn)移權(quán)值進行累加.例如取表3中的狀態(tài)點3,輸入字符為A,默認(rèn)轉(zhuǎn)移到1,權(quán)值為3;然后從狀態(tài)點1出發(fā),經(jīng)字符A默認(rèn)轉(zhuǎn)移到0,權(quán)值為3,累加為6;再從狀態(tài)點0出發(fā),到達(dá)下一狀態(tài)點為-1,沒有默認(rèn)轉(zhuǎn)移,加上權(quán)值6,則得到最終的狀態(tài)點為5.4.2狀態(tài)點u到狀態(tài)轉(zhuǎn)移在DFA定義的基礎(chǔ)上,第4.2節(jié)定義了一些與WD2FA相關(guān)的概念,以便于WD2FA的分析和算法設(shè)計.給定一個DFA={Σ,δ,Q,q0,A},Σ為字符表,δ為轉(zhuǎn)移函數(shù),Q為狀態(tài)點集合,q0為初始狀態(tài),A為接受狀態(tài).定義1(相似).對于任意u,v∈Q,u≠v,任取a,b∈Σ,如果存在常整數(shù)W,使得δ(u,a)=δ(v,a)+W,且δ(u,b)=δ(v,b)+W則稱激勵字符a與b在狀態(tài)點u和v中是相似的.假設(shè)字符表為{a,b,c,d,e,f},狀態(tài)轉(zhuǎn)移信息見表4.字符a,b,e是相似的,即任取字符x∈{a,b,e},有δ(u,x)=δ(v,x)+1.同理,字符c,d是相似的.特別地,根據(jù)定義,一個單獨的字符與其自身是相似的,例如字符f.定義2(相似劃分).對于任意u,v∈Q,u≠v,存在字符表Σ的子集Σ1,Σ2,…,Σn且UΣi=Σ,?i,j∈[1,n],i≠j有Σi∪Σj=?,使得?a∈Σi有δ(u,a)=δ(v,a)+Wi且?i,j∈[1,n],i≠j有Wi≠Wj,則稱Σ1,Σ2,…,Σn是Σ在狀態(tài)點u和v中的相似劃分.Σ={a,b,c,d,e,f}在狀態(tài)點u和v中的相似劃分為Σ1={a,b,e},Σ2={c,d},Σ3={f},且W1=1,W2=-2,W3=3.定義3(相似度).對于任意u,v∈Q,u≠v,設(shè)Σ的相似劃分為Σ1,Σ2,…,Σn,令稱其為狀態(tài)點u和v的相似度.例子中,狀態(tài)點u和v的相似度D=3,因為劃分子塊Σ1={a,b,e}具有最多的字符數(shù)目.劃分子集的個數(shù)可能只有1個或|Σ|個,相應(yīng)的D取值為|Σ|或1.這樣,D的取值范圍為[1,|Σ|].后文描述時用Duv或者Dvu來表示狀態(tài)點u和v的相似度,Duv與Dvu是相等的,它們表示同一個信息,即相似度D.定義4(默認(rèn)轉(zhuǎn)移和默認(rèn)轉(zhuǎn)移權(quán)值).對于任意u,v∈Q,u≠v,設(shè)Σ的相似劃分為Σ1,Σ2,…,Σn,狀態(tài)點u和v的相似度D對應(yīng)的劃分子塊為Σi,任取a∈Σi,有δ(u,a)=δ(v,a)+Wi.從狀態(tài)點u的狀態(tài)轉(zhuǎn)移中去除Σi中字符對應(yīng)的狀態(tài)轉(zhuǎn)移,同時給狀態(tài)點u添加一個從其出發(fā)到狀態(tài)點v的轉(zhuǎn)移,即Σi中字符對應(yīng)這個新添加的狀態(tài)轉(zhuǎn)移,稱這個新添加的狀態(tài)轉(zhuǎn)移是從狀態(tài)點u到狀態(tài)點v的默認(rèn)轉(zhuǎn)移(defaulttransitions).此外,稱Wi為狀態(tài)u到狀態(tài)v的默認(rèn)轉(zhuǎn)移權(quán)值,簡稱為狀態(tài)u到狀態(tài)v的權(quán)值,記作Wuv.延用上邊的例子,狀態(tài)點u和v的相似度D對應(yīng)的劃分子塊為{a,b,e},因此,在狀態(tài)u中去除字符a,b,e對應(yīng)的狀態(tài)轉(zhuǎn)移信息,然后添加一個到狀態(tài)v的默認(rèn)轉(zhuǎn)移,狀態(tài)u到狀態(tài)v的默認(rèn)轉(zhuǎn)移權(quán)值為Wuv=1.性質(zhì)1.對于任意u,v∈Q,u≠v,有Wuv=-Wvu.證明:從狀態(tài)u到狀態(tài)v,在劃分子塊Σi中,?a∈Σi,有δ(u,a)=δ(v,a)+Wi,即Wuv=Wi.改寫一下表達(dá)式有δ(v,a)=δ(u,a)+(-Wi),實際上就是狀態(tài)v到狀態(tài)u的表達(dá)式,即Wvu=-Wi.因此,Wuv=-Wvu.□4.3算法描述4.3.1狀態(tài)集中后的認(rèn)同轉(zhuǎn)移問題本節(jié)通過對3個問題的回答進行展開,并引出WD2FA的數(shù)據(jù)結(jié)構(gòu),最后給出WD2FA的實現(xiàn)目標(biāo).問題1.對于狀態(tài)集中的每個狀態(tài)點是不是都要建立默認(rèn)轉(zhuǎn)移關(guān)系?在這里,給某個狀態(tài)點建立默認(rèn)轉(zhuǎn)移關(guān)系是指,要么從這個狀態(tài)點出發(fā)有指向其他狀態(tài)點的默認(rèn)轉(zhuǎn)移,要么有默認(rèn)轉(zhuǎn)移到達(dá)這個狀態(tài)點,或者兩者兼具.正則表達(dá)式一般由幾個至幾十個有效字符組成,例如Snort系統(tǒng)中的NNTP規(guī)則∧SEARCH\s+[∧

]{1024},起主要作用的字符為{S,E,A,R,C,H,\s,

},只有8個.而字符表有256個字符,在構(gòu)建DFA時,從每個狀態(tài)點出發(fā)還要為不起主要作用的200多個字符建立轉(zhuǎn)移信息,而這些字符往往都指向同一個下一狀態(tài).換言之,任取狀態(tài)集中的兩個狀態(tài)點u和v,一般情況下,它們的相似度Duv大于200.為了爭取最大化的空間存儲壓縮,我們?yōu)闋顟B(tài)集中的每一個狀態(tài)點都建立默認(rèn)轉(zhuǎn)移關(guān)系,但有一定的限制條件,建立默認(rèn)轉(zhuǎn)移關(guān)系后的狀態(tài)機是有向圖,必須保證默認(rèn)轉(zhuǎn)移不能形成環(huán),否則處理字符時將陷入死循環(huán)因此,至少有一個狀態(tài)點只有指向它的默認(rèn)轉(zhuǎn)移而沒有從它出發(fā)指向其他狀態(tài)的默認(rèn)轉(zhuǎn)移.問題2.如果從某個狀態(tài)點出發(fā)有默認(rèn)轉(zhuǎn)移,那么允許它有幾個默認(rèn)轉(zhuǎn)移?結(jié)合WD2FA處理字符的原理,答案是只允許有一個到其他狀態(tài)點的默認(rèn)轉(zhuǎn)移,否則將產(chǎn)生多分枝現(xiàn)象.由上可以引出表示默認(rèn)轉(zhuǎn)移的數(shù)據(jù)結(jié)構(gòu),默認(rèn)轉(zhuǎn)移邊構(gòu)成了有向圖.問題1表明,在此有向圖中不存在環(huán);問題2表明,從某個狀態(tài)點出發(fā)最多只有一個有向邊.所以,此有向圖是樹或者森林.若一個狀態(tài)點沒有從它出發(fā)指向其他狀態(tài)點的默認(rèn)轉(zhuǎn)移,那么這個狀態(tài)點是根結(jié)點.若這樣的狀態(tài)點只有一個,則此有向圖是樹,否則是森林.問題3.處理一個字符時可能要經(jīng)由多次默認(rèn)轉(zhuǎn)移,那么默認(rèn)轉(zhuǎn)移的次數(shù)要不要限制?定義5(默認(rèn)轉(zhuǎn)移長度).在由默認(rèn)轉(zhuǎn)移構(gòu)成的樹中,樹的最大深度稱為默認(rèn)轉(zhuǎn)移長度,記作L.在用WD2FA處理字符時,處理一個字符的復(fù)雜度為O(L).如果對L的值不加以限制,它的值可能較大,這樣雖然壓縮強度大,但卻影響了處理性能.因此,處理一個字符時,默認(rèn)轉(zhuǎn)移長度L要加以限制.限制默認(rèn)轉(zhuǎn)移長度L,就是限制樹的深度.這里只構(gòu)建一棵樹,在原有的樹中不斷地添加狀態(tài)點u到樹中現(xiàn)有的狀態(tài)點v,使得任取樹中現(xiàn)有的狀態(tài)w,有Duv=max{Duw}.若存在多個滿足條件的v,則取現(xiàn)有樹中的深度最小的狀態(tài)點.如果添加的樹枝使樹深超過了L,那么重新尋找一個原樹中的結(jié)點,直至滿足默認(rèn)轉(zhuǎn)移的長度限制為止.通過對3個問題的分析,可以得出構(gòu)造WD2FA的要點.在構(gòu)建WD2FA時,為狀態(tài)集中的所有狀態(tài)點都建立默認(rèn)轉(zhuǎn)移關(guān)系,且由默認(rèn)轉(zhuǎn)移形成的有向圖是樹,并且要對默認(rèn)轉(zhuǎn)移長度(樹深)加以限制.圖5給出了一個默認(rèn)轉(zhuǎn)移樹的示例,其中加粗的實線邊代表默認(rèn)轉(zhuǎn)移,邊上的數(shù)字是默認(rèn)轉(zhuǎn)移的權(quán)值,虛線邊代表非默認(rèn)的狀態(tài)轉(zhuǎn)移,邊上的字母是字符激勵,從而形成了一棵以狀態(tài)點0為根結(jié)點、最大樹深(長度限制L)為2的樹2.4.3.2狀態(tài)轉(zhuǎn)換算法的建立如圖6所示,我們首先給出了表示兩個狀態(tài)點相似度的數(shù)據(jù)結(jié)構(gòu)以及求解兩個狀態(tài)點間相似度的算法.在數(shù)據(jù)結(jié)構(gòu)中,相似劃分塊(resembleBlock)是一個256個bit的位圖,當(dāng)字符對應(yīng)的狀態(tài)轉(zhuǎn)移是默認(rèn)轉(zhuǎn)移時則相應(yīng)的bit位置為1,否則,置為0.通過這種方法,在匹配處理中輸入一個字符激勵后,我們就能夠判別對應(yīng)的下一狀態(tài)轉(zhuǎn)移是否為默認(rèn)轉(zhuǎn)移.從算法中可以得出計算兩個狀態(tài)點間相似度的時間復(fù)雜度為O(|Σ|).為了表示整個狀態(tài)機的默認(rèn)轉(zhuǎn)移關(guān)系,要構(gòu)建一棵樹,樹枝是兩個結(jié)點間的默認(rèn)轉(zhuǎn)移.考慮這樣一個無向完全圖:頂點集合為狀態(tài)機的狀態(tài)點集合Q,任取兩個頂點u和v,u和v之間存在一條無向邊,邊的權(quán)值為頂點u和v的相似度Duv.在為所有狀態(tài)點構(gòu)建默認(rèn)轉(zhuǎn)移時,若不考慮長度限制,那么就是從這個無向完全圖中獲取一個最大權(quán)值生成樹.由于默認(rèn)轉(zhuǎn)移長度要加以限制,因此我們要構(gòu)建樹深不超過長度限制的最大權(quán)值生成樹.構(gòu)建生成樹時利用prim算法,并在其基礎(chǔ)之上限制樹的深度不超過長度限制的值,WD2FA的帶長度限制的默認(rèn)轉(zhuǎn)移生成樹算法如圖7所示.建立好生成樹之后,所有的狀態(tài)點都包含在了樹中,因此只需從樹根開始遍歷所有結(jié)點,并在非根結(jié)點中添加到其父結(jié)點的默認(rèn)轉(zhuǎn)移關(guān)系,則為整個FSM建立了默認(rèn)轉(zhuǎn)移關(guān)系.圖8給出了WD2FA掃描處理算法的偽代碼,處理單個字符的復(fù)雜度為O(L).其中,L為默認(rèn)轉(zhuǎn)移的長度限制5算法框架內(nèi)的fsm壓縮結(jié)合前邊的內(nèi)容,本節(jié)給出了一個高效存儲的深度包檢測算法的實現(xiàn)結(jié)構(gòu),如圖9所示.首先對FSM的狀態(tài)點數(shù)目進行壓縮,如圖中上方的虛線框內(nèi)所示.其次,在狀態(tài)點數(shù)目壓縮的基礎(chǔ)上,對FSM的狀態(tài)轉(zhuǎn)移數(shù)目進行壓縮,如圖中下方虛線框內(nèi)所示.采用圖中的算法框架,可以對FSM占用的存儲空間實現(xiàn)最大化的壓縮.通過狀態(tài)點數(shù)目的壓縮,將規(guī)則集進行分類,然后分別構(gòu)建不同的FSM,從而形成復(fù)合的FSM,使得所有平方級和指數(shù)級復(fù)雜度的數(shù)目降低到線性級.進一步對它們的狀態(tài)轉(zhuǎn)移數(shù)目進行壓縮,我們可以將復(fù)合的FSM內(nèi)的自動機看作兩類:一類是DFA,對應(yīng)圖中普通的DFA和帶計數(shù)器的DFA;另一類是NFA,對應(yīng)圖中的LazyDFA.對DFA采用構(gòu)建WD2FA的方式進行壓縮,通過實驗,其結(jié)果表明,可以將狀態(tài)轉(zhuǎn)移數(shù)目穩(wěn)定地壓縮為原來的5%左右.對NFA采用表壓縮技術(shù)進行壓縮,經(jīng)實驗統(tǒng)計,表壓縮可以將字符表中256個字符壓縮為20多個.這樣,表壓縮可以將轉(zhuǎn)移數(shù)目壓縮為原來的10%左右.對于這些算法的結(jié)合運用,在第6節(jié)中給出了詳細(xì)的實驗數(shù)據(jù)說明.6比較和分析實驗數(shù)據(jù)6.1基于rewche的fsm實驗使用了Snort系統(tǒng)2007年3月注冊版的規(guī)則集,從中提取了2087條正則表達(dá)式.表5給出了要構(gòu)建的不同的FSM對應(yīng)正則表達(dá)式的數(shù)目、平均長度、平均長度限制(正則表達(dá)式{}內(nèi)的數(shù)值)和構(gòu)建DFA占用的空間等信息.復(fù)合的FSM對表中的5個類別分而治之,改進后的空間性能見表6.壓縮前后,對DFA占用空間的統(tǒng)計都沒有使用狀態(tài)轉(zhuǎn)移的壓縮.這樣,復(fù)合的FSM占用的總空間大約為512M.關(guān)于處理性能,rewrite技術(shù)對其并無影響.對于帶計數(shù)器的DFA,當(dāng)觸發(fā)計數(shù)器時,與標(biāo)準(zhǔn)的DFA相比,所需要的處理僅僅是對計數(shù)器進行賦值操作以及最后一個內(nèi)部狀態(tài)點對計數(shù)器的判斷處理操作,將計數(shù)器的值存儲在寄存器中,這樣具有與標(biāo)準(zhǔn)的DFA相當(dāng)?shù)奶幚硇阅?對于LazyDFA,開始構(gòu)建和存儲時是NFA,然后在掃描處理時計算并存儲第1次用到的DFA狀態(tài)點,當(dāng)下次使用這些狀態(tài)點時,只需查表即可.LazyDFA實現(xiàn)時要考慮如何減小其查表時帶來的額外開銷,可以用二分查找或哈希查找代替線性查找.6.2第二,dfa的壓縮能力本節(jié)通過比較壓縮前后的狀態(tài)轉(zhuǎn)移數(shù)目來驗證WD2FA的壓縮性能.在Snort規(guī)則集中有一小部分指數(shù)級構(gòu)造復(fù)雜度的正則表達(dá)式無法直接構(gòu)造成DFA,相對而言,LinuxL7-filter規(guī)則集要簡單一些.因此,實驗選取了LinuxL7-filter的規(guī)則集,并整理出113條正則表達(dá)式.實驗結(jié)果見表7,壓縮比是指用壓縮掉的數(shù)目除以原來DFA的總數(shù)目.對于所有的113條規(guī)則,WD2FA的壓縮比是94.26%,