賀煒，郭云飛，扈紅超

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

1 引言

近年來(lái)，作為網(wǎng)絡(luò)信息過(guò)濾、文字處理等應(yīng)用中的關(guān)鍵組成部分，正則表達(dá)式匹配技術(shù)得到了快速發(fā)展。正則表達(dá)式匹配技術(shù)作為實(shí)現(xiàn)大規(guī)模模式匹配的主要手段，廣泛應(yīng)用于二進(jìn)制序列分析、擴(kuò)展標(biāo)記語(yǔ)言處理及入侵檢測(cè)系統(tǒng)中[1,2]。目前正則表達(dá)式匹配主要通過(guò)不確定性有限自動(dòng)機(jī)（NFA,nondeterministic finite automata）以及確定性有限自動(dòng)機(jī)（DFA, deterministic finite automata）來(lái)實(shí)現(xiàn)。

假設(shè)需要對(duì)k（k＞1）條正則表達(dá)式完成匹配，其中，第i（i=1,2,…,k ）條正則表達(dá)式中包含ni個(gè)字符。將k條正則表達(dá)式通過(guò)McNaughton-Yamada構(gòu)造法轉(zhuǎn)化為NFA后，會(huì)產(chǎn)生個(gè)NFA狀態(tài)[3]，每輸入一個(gè)字符，都需要對(duì)這些狀態(tài)進(jìn)行并行檢測(cè)。上述特性導(dǎo)致基于NFA的正則表達(dá)式匹配在處理過(guò)程中的時(shí)間復(fù)雜度較高。雖然NFA能夠通過(guò)硬件結(jié)構(gòu)的加速來(lái)提高處理速率，但硬件加速方案通常缺少靈活性并且很難做到實(shí)時(shí)更新[4]。

針對(duì)NFA的缺點(diǎn)，另外一種解決方案是將NFA轉(zhuǎn)化為DFA。通過(guò)將NFA中各個(gè)狀態(tài)之間所有的有效轉(zhuǎn)移存儲(chǔ)在狀態(tài)轉(zhuǎn)移表（STT, state transition table）中，DFA可在硬件或軟件平臺(tái)中得到較好的實(shí)現(xiàn)。但是，基于DFA的正則表達(dá)式匹配也存在一些問(wèn)題[5]。

1) 狀態(tài)數(shù)爆炸：在最壞情況下，對(duì)于有n個(gè)狀態(tài)的NFA，其最小等價(jià)DFA的狀態(tài)數(shù)將達(dá)到O(2n)數(shù)量級(jí)。

2) 壓縮時(shí)間代價(jià)：盡管STT可以通過(guò)消除相似狀態(tài)冗余來(lái)壓縮，但是現(xiàn)有壓縮算法的時(shí)間復(fù)雜度至少為O(n2)。

NFA的空間特性較好，時(shí)間特性較差，而DFA相反，兩者都不能很好地滿(mǎn)足實(shí)際網(wǎng)絡(luò)應(yīng)用的需求。因此，快速高效是大規(guī)模正則表達(dá)式匹配的首要目標(biāo)。本文將NFA、DFA兩者優(yōu)勢(shì)相結(jié)合，提出了一種新的自動(dòng)機(jī)構(gòu)建算法Group2-DFA，在保持高速處理的前提下，緩解DFA狀態(tài)爆炸的影響。本文首先通過(guò)分析狀態(tài)爆炸現(xiàn)象，得出DFA狀態(tài)爆炸的原因；然后根據(jù)狀態(tài)間約束關(guān)系對(duì)NFA狀態(tài)集合進(jìn)行分組；第三步將每個(gè)NFA組轉(zhuǎn)化為DFA，得到若干single-DFA，將各個(gè)single-DFA按照一定的方法組合，得到Group-DFA。由于Group-DFA處理速率較低，對(duì)Group-DFA進(jìn)行二級(jí)分組，最終得到Group2-DFA。

2 相關(guān)工作

基于NFA的正則表達(dá)式匹配最初在集成電路中實(shí)現(xiàn)，隨后SIDHU和PRASANNA將其部署在現(xiàn)場(chǎng)可編程門(mén)陣列（FPGA）中[6]。為了進(jìn)一步提高系統(tǒng)的吞吐率以及資源利用率，F(xiàn)PGA實(shí)現(xiàn)中加入了許多優(yōu)化措施，例如流水線、前綴提取、多字符匹配、字符編碼等[7,8]。但是由于電路結(jié)構(gòu)本身的缺點(diǎn)，在FPGA平臺(tái)中，很難對(duì)基于NFA的正則表達(dá)式匹配進(jìn)行及時(shí)更新。

基于DFA的正則表達(dá)式匹配可通過(guò)處理器架構(gòu)來(lái)實(shí)現(xiàn)，相對(duì)于NFA，這種結(jié)構(gòu)更加簡(jiǎn)單并易于操作。然而，狀態(tài)爆炸問(wèn)題導(dǎo)致算法對(duì)于內(nèi)存的需求急劇增加，影響了內(nèi)存性能和實(shí)際中部署的可行性。

為了解決DFA內(nèi)存需求高的問(wèn)題，目前常用的方法有2種：1）YU、PASETTO等[9,10]利用NFA的不確定性來(lái)壓縮STT，以此達(dá)到較高的吞吐率性能。但是這類(lèi)方法計(jì)算的復(fù)雜度較高，且大多依賴(lài)于特定的正則表達(dá)式集合特性。QI等[11]利用DFA狀態(tài)的相似性壓縮STT，提出FEACAN（front-end acceleration for content-aware network）算法，能夠達(dá)到80%的壓縮率。LIU等[12]提出的CSCA（cluster-based splitting compression algorithm）通過(guò)切分STT發(fā)現(xiàn)內(nèi)在的冗余，能夠達(dá)到95%的壓縮率。但是FEACAN和CSCA算法都會(huì)降低系統(tǒng)的吞吐率。2）將大規(guī)模正則表達(dá)式匹配問(wèn)題分解為若干小問(wèn)題分別解決。ANTONELLO等[13]使用判決檢驗(yàn)算法將m(m＞1)個(gè)正則表達(dá)式組合成g(m＞g＞0)個(gè)小組；WOODS等[14]將正則表達(dá)式切分為前綴和后綴2個(gè)組合，并且將所有的前綴構(gòu)造為一個(gè)復(fù)合DFA，當(dāng)?shù)竭_(dá)DFA邊界狀態(tài)時(shí)，觸發(fā)后綴匹配；YANG等[15]提出的SFA（semi-deterministic finite automata）算法采用NFA和DFA混合結(jié)構(gòu)，在空間利用和吞吐率方面均有較好的效果。

3 理論基礎(chǔ)

3.1 正則表達(dá)式匹配

定義1 對(duì)于正則表達(dá)式R，基于NFA的正則表達(dá)式匹配是在連續(xù)輸入字符流的條件下，構(gòu)造不確定性有限自動(dòng)機(jī)M=(Q,Σ,δ,q0,F)，其中，Q是有限的NFA狀態(tài)集合；Σ是有限的字母表；δ是不確定性狀態(tài)轉(zhuǎn)移函數(shù)，數(shù)量級(jí)為Q×Σ，大約為2Q；q0是狀態(tài)機(jī)的初始狀態(tài)，q0∈Q；F是狀態(tài)機(jī)結(jié)束狀態(tài)集合，F(xiàn)?Q。

定義2 對(duì)于正則表達(dá)式R，基于DFA的正則表達(dá)式匹配是根據(jù)標(biāo)準(zhǔn)構(gòu)造方法，將相應(yīng)的不確定性有限自動(dòng)機(jī)M轉(zhuǎn)化為確定性有限自動(dòng)機(jī)M'=(Q',Σ, δ',q0,F ')，其中，Q'是有限的NFA狀態(tài)集合，Q'?2Q；δ'是確定性狀態(tài)轉(zhuǎn)移函數(shù)，數(shù)量級(jí)為Q'×Σ；F'是狀態(tài)機(jī)結(jié)束狀態(tài)集合，F(xiàn)'?Q'；q0和Σ的定義與NFA中相同。

3.2 狀態(tài)爆炸分析

YU等[9]證明了對(duì)于實(shí)際的正則表達(dá)式，NFA到DFA的轉(zhuǎn)化會(huì)引起指數(shù)級(jí)別的狀態(tài)爆炸，其等價(jià)最小DFA有2n個(gè)狀態(tài)。為了更好地說(shuō)明Group2-DFA原理，簡(jiǎn)要分析發(fā)生狀態(tài)爆炸的原因。

對(duì)于正則表達(dá)式r1=/.*[a|b][c|d]{n -1}/.，構(gòu)建NFA，命名為A。A中有初始狀態(tài)q0、結(jié)束狀態(tài)qn及n-1個(gè)中間狀態(tài){q1,…,qn-1}，各個(gè)狀態(tài)間相互獨(dú)立，互不影響。接收任意的輸入，q0到達(dá)狀態(tài)q1；接收輸入a或b，q1到達(dá)狀態(tài)q2；接收輸入c或d，qi到達(dá)狀態(tài)qi+1，1＜i＜n。

構(gòu)造輸入字符流，第一個(gè)字符為任意字符，第二個(gè)字符為a或b，之后的字符為c或d，各個(gè)字符之間相互獨(dú)立不相關(guān)。當(dāng)正則表達(dá)式r1接收到這一字符流時(shí)，對(duì)應(yīng)的2n個(gè)狀態(tài)均可能出現(xiàn)。將A轉(zhuǎn)化為DFA后，至少會(huì)有2n個(gè)狀態(tài)，與原有n+1個(gè)狀態(tài)相比，呈指數(shù)級(jí)增長(zhǎng)。

以上論述的基礎(chǔ)是各個(gè)輸入字符間相互獨(dú)立，各個(gè)狀態(tài)間互不影響，而在實(shí)際應(yīng)用中，各個(gè)狀態(tài)間存在相互約束，利用這種約束關(guān)系，可減小狀態(tài)爆炸的規(guī)模。例如：狀態(tài)q1、q2相互獨(dú)立時(shí)，狀態(tài)間約束不確定，存在4種狀態(tài)組合(q1,q2)={(0,0),(0,1),(1,0),(1,1)}（標(biāo)記1表示狀態(tài)被激活）。若假設(shè)狀態(tài)q1被激活時(shí)，q2一定被激活，則狀態(tài)間約束關(guān)系確定，狀態(tài)組合變?yōu)?q1,q2)={(0,0),(1,1)}2種，轉(zhuǎn)化為DFA后，總狀態(tài)數(shù)由2n+1減少為2n。以此類(lèi)推，當(dāng)各個(gè)狀態(tài)間均有確定的約束關(guān)系時(shí)，可消除DFA狀態(tài)爆炸的現(xiàn)象。

3.3 狀態(tài)約束關(guān)系

根據(jù)狀態(tài)爆炸分析可得出，若能確定狀態(tài)間的約束關(guān)系，減少轉(zhuǎn)化過(guò)程中的不確定性，則可大幅地減少DFA中的狀態(tài)數(shù)。為描述狀態(tài)間約束關(guān)系，引入3種集合關(guān)系：相交、包含、分離，具體定義如下。

定義3 記(q0,s)=q，其中，s為輸入序列字符串；q0為初始狀態(tài)，q為q0接收輸入s后到達(dá)的目的狀態(tài)。狀態(tài)qx,qy∈Q，記Φx是滿(mǎn)足(q0,s)=qx的輸入序列s的集合，Φy是滿(mǎn)足(q0,s)=qy的輸入序列s的集合。

若Φx∩Φy=φ，則qx,qy互相分離，記為qx∩qy=φ。

若Φx∩Φy=Φx，則qx包含于qy，記為qx?qy。

若Φx∩Φy≠φ且Φx?Φy,Φy?Φx，則qx,qy相交。

當(dāng)qx,qy分離時(shí)，約束關(guān)系確定，qx,qy不會(huì)被同時(shí)激活，在轉(zhuǎn)化為DFA的過(guò)程中，不會(huì)引起狀態(tài)爆炸。

當(dāng)qx包含于qy時(shí)，qx被激活，qy一定被激活，不會(huì)引起狀態(tài)增加；當(dāng)qy被激活，qx不一定被激活，會(huì)引起一定的狀態(tài)數(shù)增長(zhǎng)。

當(dāng)qx,qy相交時(shí)，2種狀態(tài)相關(guān)性不強(qiáng)，可能同時(shí)被激活，也可能只激活一個(gè)，約束關(guān)系不確定，會(huì)引起狀態(tài)爆炸。

根據(jù)定義的3種約束關(guān)系，提出NFA狀態(tài)約束關(guān)系分析（NFA-SCA, NFA state constrain analysis）算法，可得到NFA狀態(tài)集中任意2個(gè)狀態(tài)之間的約束關(guān)系。圖1中1）～8）通過(guò)分析狀態(tài)轉(zhuǎn)移路徑，得到各個(gè)狀態(tài)對(duì)應(yīng)的輸入序列集合Φ；9）～15）比較各個(gè)狀態(tài)的輸入序列集合，決定相互間約束關(guān)系的種類(lèi)。NFA-SCA算法偽代碼描述如圖1所示。

圖1 NFA-SCA算法

4 基于狀態(tài)約束的Group2-DFA算法

4.1 NFA狀態(tài)集合分組

為了降低狀態(tài)數(shù)爆炸式增長(zhǎng)對(duì)正則表達(dá)式匹配的影響，在NFA-SCA算法得到的狀態(tài)間約束關(guān)系的基礎(chǔ)上，按照以下原則將狀態(tài)集合劃分為若干小組：

1) 同一組內(nèi)狀態(tài)兩兩不相交；

2) 相交的狀態(tài)放到不同的組內(nèi)；

3) 每個(gè)組內(nèi)包含盡可能多的相離和相互包含的狀態(tài)。

依照上述原則分組可保證同一組內(nèi)不會(huì)有相交狀態(tài)，確定了狀態(tài)間的約束關(guān)系，避免了大規(guī)模的狀態(tài)增長(zhǎng)。

劃分過(guò)程步驟如下。

1) 初始化：建立狀態(tài)集合V，包括所有NFA狀態(tài)，置0m=。

2) 若V不為空，建立空集合mV。按狀態(tài)序號(hào)，取V中一個(gè)狀態(tài)tq，作以下判斷：

①若mV為空，tq加入mV，并從V中刪除tq；

②若mV不為空，將tq與mV中所有狀態(tài)相比，若tq與這些狀態(tài)都不相交，則tq加入mV，并從V中刪除tq；否則，tq放回V中，嘗試V中下一個(gè)狀態(tài)，直到遍歷V中的所有狀態(tài)。記錄Vm及其大小，m=m+1。重復(fù)2）直到V為空。

狀態(tài)集合劃分（SSD, state set division）算法的偽代碼描述如圖2所示。

圖2 SSD算法

4.2 構(gòu)建一級(jí)分組DFA(Group-DFA)

SSD算法可得到k個(gè)狀態(tài)集合Vm,m=0,1,…,k ，每個(gè)Vm均有自身對(duì)應(yīng)的狀態(tài)集、字符表、轉(zhuǎn)移函數(shù)、初始狀態(tài)、結(jié)束狀態(tài)，即對(duì)應(yīng)于一個(gè)NFA，Mm=(Qm,Σ, δm,q0m,Fm)，其中，Qm是Vm中的狀態(tài)集合；Σ是有限的字母表；δm是Vm中的狀態(tài)轉(zhuǎn)移函數(shù)；q0m是NFA的初始狀態(tài)；Fm是NFA結(jié)束狀態(tài)集合；

對(duì)于每一個(gè)Mm，按照標(biāo)準(zhǔn)構(gòu)建算法轉(zhuǎn)化為相應(yīng)的等價(jià)DFA，即為Mm'，由于每個(gè)Mm中不包含相交的狀態(tài)，所有每個(gè)Mm'中狀態(tài)數(shù)增長(zhǎng)較少。這樣可得到k個(gè)獨(dú)立的DFA，稱(chēng)為k個(gè)single-DFA。

每個(gè)single-DFA中包括2種狀態(tài)轉(zhuǎn)移：內(nèi)部轉(zhuǎn)移和平行轉(zhuǎn)移。內(nèi)部轉(zhuǎn)移實(shí)現(xiàn)DFA內(nèi)部的狀態(tài)跳轉(zhuǎn)，每個(gè)平行轉(zhuǎn)移作為其他single-DFA的輸入，激活另一個(gè)single-DFA中的狀態(tài)；因此，single-DFA中的若干個(gè)狀態(tài)都有可能同時(shí)被內(nèi)部轉(zhuǎn)移和其他single-DFA的平行轉(zhuǎn)移同時(shí)激活，這種情況不滿(mǎn)足DFA同一時(shí)刻只有一個(gè)激活狀態(tài)的特性，為保證DFA的特性，添加多跳轉(zhuǎn)關(guān)系綜合判斷邏輯，保留一個(gè)激活狀態(tài)。

多跳轉(zhuǎn)關(guān)系綜合判斷（MTA，multi-transition analysis）：按照single-DFA編號(hào)的大小，即m值的大小定義優(yōu)先級(jí)：m值越小，single-DFA輸出的平行轉(zhuǎn)移的優(yōu)先級(jí)越高。當(dāng)一個(gè)single-DFA中的幾個(gè)狀態(tài)同時(shí)被激活時(shí)，選擇優(yōu)先級(jí)高的轉(zhuǎn)移所激活的狀態(tài)，其余狀態(tài)不被激活。

構(gòu)造Group-DFA時(shí)，每個(gè)single-DFA(i)最多有k個(gè)進(jìn)位輸出狀態(tài)，以kbit長(zhǎng)進(jìn)位輸出向量vector記錄該輸出狀態(tài)。k個(gè)single-DFA最多同時(shí)有k個(gè)進(jìn)位輸出向量：vector(1),…,vector (k)，記錄此k個(gè)向量值，共需要k×k大小的矩陣存儲(chǔ)。

對(duì)于k個(gè)向量值，分析每個(gè)single-DFA會(huì)接收哪些平行轉(zhuǎn)移，通過(guò)判斷這些進(jìn)位輸出的優(yōu)先級(jí)，即源DFA序號(hào)，確定保留哪一個(gè)平行轉(zhuǎn)移作為輸入。

MAT算法代碼描述如圖3所示。

圖3 MTA算法

k個(gè)single-DFA間采用多跳轉(zhuǎn)關(guān)系綜合判斷邏輯連接，都滿(mǎn)足DFA的特性，組成的新DFA結(jié)構(gòu)命名為Group-DFA。Group-DFA是NFA與DFA的混合結(jié)構(gòu)，其中，各個(gè)DFA單獨(dú)運(yùn)行，DFA之間為并行操作，由同一個(gè)初始狀態(tài)觸發(fā)，相當(dāng)于NFA中的各個(gè)狀態(tài)，呈現(xiàn)NFA特性。

在最好的情況下，原始NFA中，各個(gè)狀態(tài)都不相交，則構(gòu)造的Group-DFA是一個(gè)單獨(dú)的DFA；在最壞的情況下，各個(gè)狀態(tài)相互之間都相交，則構(gòu)造的Group-DFA仍然是原始的NFA。

4.3 構(gòu)建二級(jí)分組DFA(Group2-DFA)

Group-DFA算法在實(shí)現(xiàn)過(guò)程中沒(méi)有限制分組的數(shù)目。對(duì)于有N個(gè)狀態(tài)的NFA，假設(shè)存在k個(gè)相交狀態(tài)對(duì)，則會(huì)產(chǎn)生k個(gè)single-DFA。由于k個(gè)single-DFA之間呈NFA特性，k值過(guò)大將導(dǎo)致處理速率急劇降低。

為降低分組數(shù)量對(duì)處理速率的影響，設(shè)計(jì)二級(jí)分組結(jié)構(gòu)如下。

1) 將k個(gè)single-DFA看作一個(gè)NFA中的k個(gè)狀態(tài)。

2) 對(duì)該k個(gè)狀態(tài)執(zhí)行NFA-SCA算法，得到狀態(tài)間約束關(guān)系。

3) 根據(jù)2）中的結(jié)果，執(zhí)行SSD算法，對(duì)狀態(tài)集合進(jìn)行劃分，得到二級(jí)分組集合。不同之處在于劃分集合的數(shù)目限定為p個(gè)，若存在多于p個(gè)的相交狀態(tài)，將多余的狀態(tài)劃入已知的p個(gè)集合中，得到二級(jí)分組集合。

4) 對(duì)3）中得到的p個(gè)NFA狀態(tài)集合按照標(biāo)準(zhǔn)構(gòu)建算法轉(zhuǎn)化為p個(gè)DFA，稱(chēng)為Class2-DFA；并執(zhí)行MTA算法，將p個(gè)Class2-DFA通過(guò)多跳轉(zhuǎn)關(guān)系綜合判斷邏輯連接。

5) 在4）的結(jié)果中加入初始狀態(tài)，二級(jí)分組DFA——Group2-DFA構(gòu)建結(jié)束，Group2-DFA中包含p個(gè)Class2-DFA結(jié)構(gòu)， Class2-DFA中的每個(gè)狀態(tài)對(duì)應(yīng)一個(gè)single-DFA。

Group2-DFA中包含3種轉(zhuǎn)移關(guān)系：Class2-DFA的內(nèi)部轉(zhuǎn)移、Class2-DFA之間的平行轉(zhuǎn)移和single-DFA的內(nèi)部轉(zhuǎn)移。Group2-DFA中同樣存在多個(gè)DFA狀態(tài)被同時(shí)激活的問(wèn)題，按照single-DFA中的方式，根據(jù)編號(hào)大小來(lái)定義優(yōu)先級(jí)，然后使用多跳轉(zhuǎn)關(guān)系綜合判斷邏輯處理。

4.4 性能分析

有n個(gè)狀態(tài)的NFA，時(shí)間復(fù)雜度為O(1)，空間復(fù)雜度為O(n)；構(gòu)建Group-DFA后，有k個(gè)single-DFA，時(shí)間復(fù)雜度為O(k2)，空間復(fù)雜度為O(an)，其中，a為線性常數(shù)；構(gòu)建Group2-DFA后，等價(jià)NFA結(jié)構(gòu)有p個(gè)狀態(tài)，且有兩級(jí)的DFA邏輯結(jié)構(gòu)，所以時(shí)間復(fù)雜度為O(2p2)，在p個(gè)二級(jí)集合中，每個(gè)集合最壞情況下有個(gè)相交狀態(tài)，每一個(gè)狀態(tài)代表一個(gè)single-DFA，定義為二級(jí)分割參數(shù)；將p個(gè)二級(jí)集合轉(zhuǎn)化為p個(gè)DFA后，相比于Group-DFA，狀態(tài)數(shù)會(huì)增加(2xx)倍，空間復(fù)雜度為，隨著值的增加，Group2-DFA的空間復(fù)雜度增大，但時(shí)間復(fù)雜度減小，為了權(quán)衡時(shí)間和空間的代價(jià)，p值的選取需要根據(jù)實(shí)驗(yàn)結(jié)果和實(shí)際需求來(lái)確定。

5 實(shí)驗(yàn)仿真和性能驗(yàn)證

5.1 模型建立

針對(duì)Group-DFA中NFA、DFA混合的特點(diǎn)，設(shè)計(jì)處理模型如圖4所示。

圖4中，Group-DFA由若干個(gè)single-DFA單元以及多跳轉(zhuǎn)關(guān)系綜合判斷模塊（簡(jiǎn)稱(chēng)為綜合模塊）組成，single-DFA單元如虛線框內(nèi)所示，包括狀態(tài)查找表STT、狀態(tài)合并、輸入組合3個(gè)模塊：輸入組合以輸入字符和當(dāng)前狀態(tài)作為輸入，并將組合結(jié)果送入STT查詢(xún)；STT根據(jù)輸入數(shù)據(jù)得到相應(yīng)的轉(zhuǎn)移結(jié)果，若是內(nèi)部轉(zhuǎn)移，直接送入狀態(tài)合并模塊，若是進(jìn)位轉(zhuǎn)移，則送入綜合模塊；狀態(tài)合并模塊接收STT的內(nèi)部轉(zhuǎn)移以及綜合模塊得到的進(jìn)位轉(zhuǎn)移作為輸入，決定在single-DFA內(nèi)部選擇哪一個(gè)轉(zhuǎn)移狀態(tài)作為當(dāng)前狀態(tài)。

綜合模塊實(shí)現(xiàn)MTA算法中的功能，分析處理各個(gè)single-DFA得到的進(jìn)位轉(zhuǎn)移結(jié)果。

對(duì)于Group2-DFA，二級(jí)分組結(jié)構(gòu)包含p個(gè)DFA結(jié)構(gòu)，每個(gè)DFA中的狀態(tài)對(duì)應(yīng)一個(gè)single-DFA，處理模型如圖5所示。

5.2 性能仿真

性能分析采用的實(shí)驗(yàn)環(huán)境為：系統(tǒng)：Ubuntu 11.10；編譯環(huán)境：gcc4.2.4；內(nèi)存：2 GB；CPU：Intel雙核。

實(shí)驗(yàn)數(shù)據(jù)采用snort24、snort31、bro217、dotstar300等4個(gè)規(guī)則集[16,17]。本節(jié)從空間存儲(chǔ)消耗、系統(tǒng)吞吐率以及單字符平均內(nèi)存訪問(wèn)次數(shù)3方面對(duì)算法性能進(jìn)行分析，對(duì)比算法包括Group2-DFA算法、SFA算法、FEACAN算法以及CSCA算法。為了評(píng)價(jià)4種算法的性能，消除額外因素的影響，算法實(shí)現(xiàn)時(shí)，去掉了FEACAN算法中的硬件加速部分。

5.2.1 正則表達(dá)式規(guī)模與single-DFA數(shù)量關(guān)系

表1中給出了正則表達(dá)式規(guī)模與生成的single-DFA數(shù)量之間的關(guān)系，規(guī)模大小以正則表達(dá)式數(shù)量表示；采用NFA-SCA算法和SSD算法生成相應(yīng)的若干single-DFA。

圖4 Group-DFA處理模型

圖5 Group2-DFA處理模型

表1 正則表達(dá)式規(guī)模與single-DFA數(shù)量關(guān)系

從表1中可看出，隨著正則表達(dá)式規(guī)模的增大，NFA狀態(tài)數(shù)也增多，各個(gè)狀態(tài)之間的關(guān)系也更加復(fù)雜，出現(xiàn)了更多的相交情形，single-DFA的數(shù)量也隨之增多。

其中，Thp(x)為吞吐率函數(shù)，SN(x)為狀態(tài)數(shù)函數(shù)，分別表示二級(jí)分割參數(shù)為x時(shí)的系統(tǒng)吞吐率和狀態(tài)數(shù)。其中，x=1時(shí)，表示不進(jìn)行分割，Group2-DFA就是Group-DFA。由性能增益函數(shù)g(x)的定義可知，g(x)是以x=1時(shí)的吞吐率Thp(1)和狀態(tài)數(shù)SN(1)為標(biāo)準(zhǔn)，將Thp(x)和SN(x)歸一化后的比值，表示隨著x的變化，吞吐率和狀態(tài)數(shù)增長(zhǎng)的效果。

在snort24、bro217和dotstar300 3種規(guī)則集下，分別計(jì)算Group2-DFA的狀態(tài)數(shù)以及吞吐率如圖6所示。

圖6 性能增益隨分割參數(shù)的變化

從圖6中可看出，對(duì)于不同的規(guī)則集，x=4時(shí)，性能增益均達(dá)到最大值，說(shuō)明此時(shí)吞吐率增長(zhǎng)較大，狀態(tài)數(shù)增長(zhǎng)相對(duì)較小，整體性能達(dá)到最佳。

面對(duì)不同的實(shí)際應(yīng)用，對(duì)于空間性能要求較高時(shí)，可減小分割參數(shù)；對(duì)于吞吐率性能要求較高時(shí)，可增大分割參數(shù)，以達(dá)到合適的效果。

5.2.3 空間存儲(chǔ)性能與系統(tǒng)吞吐率

空間存儲(chǔ)占用與狀態(tài)數(shù)量呈正比，因此分析算法生成的狀態(tài)數(shù)可反映空間存儲(chǔ)的性能。實(shí)驗(yàn)中實(shí)現(xiàn)了基于SFA算法，F(xiàn)EACAN算法、CSCA算法以及Group2-DFA算法的正則表達(dá)式匹配，根據(jù)5.2.2節(jié)的實(shí)驗(yàn)結(jié)果，Group2-DFA算法的二級(jí)分割參數(shù)取x=4。正則表達(dá)式規(guī)則選用snort24、bro217和dotstar300的混合集合，規(guī)則數(shù)量從24開(kāi)始逐漸增加，最多選取300條正則表達(dá)式。

4種算法的狀態(tài)數(shù)對(duì)比情況如圖7所示。正則表達(dá)式規(guī)模較小時(shí)，4種算法得到的狀態(tài)數(shù)差別較?。浑S著正則表達(dá)式規(guī)模的增長(zhǎng)，Group2-DFA算法的狀態(tài)數(shù)增長(zhǎng)最慢，近似呈線性增長(zhǎng)，而SFA算法、FEACAN算法以及CSCA算法的狀態(tài)數(shù)增長(zhǎng)較快，可以看出，Group2-DFA算法在減少狀態(tài)數(shù)方面的優(yōu)勢(shì)較為明顯。

圖7 4種算法狀態(tài)數(shù)對(duì)比

表2給出了4種規(guī)則集合下，Group2-DFA相對(duì)于DFA的狀態(tài)減少率。

表2 正則表達(dá)式集合下Group2-DFA的狀態(tài)減少率

根據(jù)表2計(jì)算可得，對(duì)于4個(gè)不同的規(guī)則集合，Group2-DFA的狀態(tài)減少率分別為：79.1%、75.9%、54.4%以及大于96.6%。

正則表達(dá)式集合bro217中，處于相交關(guān)系的狀態(tài)較少，狀態(tài)爆炸不明顯，Group2-DFA算法對(duì)于狀態(tài)數(shù)的減少百分比較??；測(cè)試中，Group2-DFA算法對(duì)于snort集合、dotstar_300集合的性能較好，能達(dá)到75%以上。另外，由于dotstar_300生成的DFA數(shù)目大于1×105個(gè)，超出預(yù)設(shè)的內(nèi)存占用，沒(méi)有得到全部的DFA狀態(tài)數(shù)。

圖8給出了4種算法的吞吐率（Gbit/s）對(duì)比情況。從圖8中可以看出，隨著正則表達(dá)式規(guī)模的增加，Group2-DFA算法的吞吐率較為穩(wěn)定，這是由于Group2-DFA算法的吞吐率主要受到并行等價(jià)NFA數(shù)量的影響，與參數(shù)x的選取有關(guān)，與正則表達(dá)式規(guī)模無(wú)關(guān)。Group2-DFA算法的吞吐率與SFA算法較為接近，相差較小，但Group2-DFA算法的浮動(dòng)較小，比SFA算法穩(wěn)定。而FEACAN和CSCA的吞吐率受正則表達(dá)式規(guī)模的影響較大，雖然在正則表達(dá)式規(guī)模較小時(shí)，兩者的吞吐率高于Group2- DFA算法，但是隨著正則表達(dá)式規(guī)模的增加，吞吐率呈下降趨勢(shì)，當(dāng)正則表達(dá)式大于250條時(shí)，其吞吐率小于Group2-DFA算法。

圖8 4種算法的吞吐率對(duì)比

圖9給出了4種算法處理一個(gè)字符時(shí)的平均內(nèi)存訪問(wèn)次數(shù)?？梢钥闯?，在處理一個(gè)字符時(shí)，Group2-DFA算法需要訪問(wèn)多次內(nèi)存，時(shí)間復(fù)雜度有所增長(zhǎng)，高于其他3種算法。這是由于Group2-DFA算法中包括兩級(jí)分組結(jié)構(gòu)，每一級(jí)中都包括NFA和DFA 2種形態(tài)，而NFA和DFA的狀態(tài)轉(zhuǎn)移表需要單獨(dú)存儲(chǔ)，導(dǎo)致處理字符時(shí)，可能需要讀取多次內(nèi)存。雖然Group2-DFA算法的時(shí)間復(fù)雜度有所增長(zhǎng)，但由于采用二級(jí)分組結(jié)構(gòu)，充分利用了DFA的快速處理特性，所以Group2-DFA算法仍然可以達(dá)到較高的吞吐率。

圖9 單字符平均內(nèi)存訪問(wèn)次數(shù)

實(shí)驗(yàn)結(jié)果表明，Group2-DFA算法的狀態(tài)數(shù)小于SFA、FEACAN、CSCA算法；當(dāng)正則表達(dá)式規(guī)模增加時(shí)，Group2-DFA算法的吞吐率穩(wěn)定在較高水平；對(duì)于不同的規(guī)則集合，Group2-DFA算法的單字符平均內(nèi)存訪問(wèn)次數(shù)高于其他3種算法。綜上所述，根據(jù)性能增益合理選取分割參數(shù)后，Group2-DFA算法能夠達(dá)到較好的狀態(tài)減少率，并且保持較高的系統(tǒng)吞吐率，付出的代價(jià)是單字符平均內(nèi)存訪問(wèn)次數(shù)有一定的增加。

6 結(jié)束語(yǔ)

本文提出的Group2-DFA算法結(jié)合NFA的空間和DFA的時(shí)間特性，以一定的時(shí)間復(fù)雜度為代價(jià)，減小了DFA的空間復(fù)雜度。算法通過(guò)分析NFA轉(zhuǎn)化為DFA過(guò)程中產(chǎn)生狀態(tài)爆炸的原因，引入了一種狀態(tài)分類(lèi)方法，構(gòu)建二級(jí)分組模型，在保證系統(tǒng)吞吐率的前提下，有效地減輕了狀態(tài)爆炸的影響。在系統(tǒng)結(jié)構(gòu)上，Group2-DFA算法呈現(xiàn)NFA的并行處理特性，在內(nèi)部實(shí)現(xiàn)中，采用單獨(dú)的DFA處理；這種混合結(jié)構(gòu)使得Group2-DFA算法能夠通過(guò)多核技術(shù)實(shí)現(xiàn)并行加速，有效地提升了系統(tǒng)的吞吐率。

對(duì)于大規(guī)模的正則表達(dá)式集合，分組得到的single-DFA數(shù)量較多，會(huì)降低系統(tǒng)處理的性能，進(jìn)一步的研究可考慮對(duì)分組的方法進(jìn)行改進(jìn)，以提高處理速率。另外，由于采用單字符輸入的方法，處理速率受到一定的限制，為了達(dá)到更高的系統(tǒng)吞吐率，可引入多字符處理機(jī)制來(lái)滿(mǎn)足實(shí)際需求。

[1] JIANG L, TAN J, LIU Y. ClusterFA: a memory-efficient DFA structure for network intrusion detection[A]. Proceedings of the 7th ACM Symposium on Computer and Communications Security Information[C]. New York,USA, 2012. 65-66.

[2] BECCHI M, CROWLEY P. Efficient regular expression evaluation:theory to practice[A]. Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C].Colorado: ACM, 2008. 50-59.

[3] YANG Y H E, JIANG W, PRASANNA V K. Compact architecture for high-throughput regular expression matching on FPGA[A]. Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. San Jose, California,USA,2008.30-39.

[4] ZHENG K, ZHANG X, CAI Z, etal. Scalable NIDS via negative pattern matching and exclusive pattern matching[A]. Proceedings IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies[C].San Dieg, 2010. 1-9.

[5] 李奇越. 網(wǎng)絡(luò)內(nèi)容分析中基于硬件的字符串匹配算法的研究[D].合肥: 中國(guó)科技大學(xué), 2008.LI Q Y. String Matching Algorithm Research based on Hardware in Network, Content Analysis[D]. Hefei: University of Science and Technology of China, 2008.

[6] LIN C H, HUANG C T, JIANG C P,etal. Optimization of regular expression pattern matching circuits on FPGA[A]. Proceedings of Design, Automation and Test in Europe[C]. Germany, 2006. 1-6.

[7] LE H, PRASANNA V. A memory-efficient and modular approach for large-scale string pattern matching[J]. IEEE Transactions on Computers, 2013,62(5):844-857.

[8] BECCHI M, CROWLEY P. A hybrid finite automaton for practical deep packet inspection[A]. Proceedings of ACM CoNEXT Conference[C]. New York,USA, 2007.1-12.

[9] YU F, CHEN Z, DIAO Y, etal. Fast and memory-efficient regular expression matching for deep packet inspection[A]. ACM/IEEE Symposium on Architecture for Networking and Communications System[C]. San Jose, California,USA, 2006. 93-102.

[10] PASETTO D, PETRINI F, AGARWAL V. Tools for very fast regular expression matching[J]. Computer, 2010, 43(3):50-58.

[11] QI Y, WANG K, FONG J, etal. FEACAN: front-end acceleration for content-aware network processing[A]. Proceedings of 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies[C].Shanghai, China, 2011. 2114-2122.

[12] LIU T, YANG Y, LIU Y, etal. An efficient regular expressions compression algorithm from a new perspective[A]. Proceedings of 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies[C].Shanghai, China, 2011. 2129-2137.

[13] ANTONELLO R, FERNANDES S, SADOK D, etal. Deterministic finite automaton for scalable traffic identification: the power of compressing by range[A]. Network Operations and Management Symposium (NOMS)[C]. Piscataway:IEEE, 2012. 155-162.

[14] WOODS L, TEUBNER J, ALONSO G. Complex event detection at wire speed with FPGAs[J]. The VLDB Endowment, 2010, 3(1-2):660-669.

[15] YANG Y H E, PRASANNA V K. Space-time tradeoff in regular expression matching with semi-deterministic finite automata[A]. Proceedings of 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies[C]. Shanghai, China, 2011. 1853-1861.

[16] Sourcefire, SNORT[EB/OL].http://www.snort.org/snort-downloads, 2012.

[17] International computer science institute, bro intrusion detection system[EB/OL]. http://bro-ids.org/download/index.html, 2012.