0 引言

　　正則表達(dá)式使用標(biāo)準(zhǔn)的語法規(guī)則來描述模式,，與精確字符串相比,，正則表達(dá)式可以描述復(fù)雜的字符序列，并降低空間復(fù)雜度,。強(qiáng)大的表達(dá)能力使正則表達(dá)式在網(wǎng)絡(luò)安全領(lǐng)域廣泛應(yīng)用,，成為描述規(guī)則的主要工具[1]，目前主流的入侵檢測(cè)/防御系統(tǒng)(NIDS/NIPS)，例如Snort[2],、ClamAV[3]等已經(jīng)將基于正則表達(dá)式的規(guī)則集成到其過濾系統(tǒng)中,，且所占比重逐漸增大。

　　有限狀態(tài)機(jī)（FA）和正則表達(dá)式所描述的語言都是正則語言,，因此有限狀態(tài)機(jī)是實(shí)現(xiàn)正則表達(dá)式匹配的主要方法,。有限狀態(tài)機(jī)通常分為兩種：確定性有限狀態(tài)機(jī)(DFA)和非確定性有限狀態(tài)機(jī)(NFA)，通過對(duì)兩種狀態(tài)機(jī)深入而細(xì)致的研究和分析,，Washington University的Kumar和Becchi等人提出了D2FA[4],、混合自動(dòng)機(jī)(Hy brid-FA)[5]以及XFA[6]等方法來實(shí)現(xiàn)大規(guī)模正則表達(dá)式的實(shí)用化[7]。

　　XFA算法是比較高效的正則表達(dá)式匹配算法,，算法使用輔助變量和簡(jiǎn)單的操作指令消除了由*,、[ ]和{ }等重復(fù)匹配造成的DFA空間爆炸問題，降低了狀態(tài)空間的存儲(chǔ)需求,。

　　為提高檢測(cè)引擎的吞吐量,，同時(shí)擺脫系統(tǒng)對(duì)引擎的約束以及引擎對(duì)系統(tǒng)的性能影響，使用專用器件實(shí)現(xiàn)入侵檢測(cè)的包過濾過程成為目前的發(fā)展趨勢(shì),。FPGA由于高速并行可在線編程等優(yōu)點(diǎn)成為硬件檢測(cè)引擎的實(shí)驗(yàn)開發(fā)和應(yīng)用平臺(tái),。

　　硬件實(shí)現(xiàn)XFA算法，若使用輔助變量和指令解決約束重復(fù)計(jì)數(shù)問題,，則需要對(duì)存在約束重復(fù)的規(guī)則單獨(dú)進(jìn)行處理,，消耗大量的硬件資源。本文針對(duì)這個(gè)情況設(shè)計(jì)專用計(jì)數(shù)器結(jié)構(gòu)解決約束重復(fù)問題,。

1 約束重復(fù)問題

　　1.1 問題的提出

　　傳統(tǒng)處理約束重復(fù)問題的方法是將約束重復(fù)的內(nèi)容展開,，描述為精確匹配串的形式，在Snort規(guī)則集中存在約束重復(fù)數(shù)百上千次的規(guī)則,，若使用展開的方法進(jìn)行匹配將消耗大量的硬件資源,，匹配效率低下。此外為現(xiàn)在4種類型的約束匹配,，必須設(shè)計(jì)多種類型的匹配電路,，例如要實(shí)現(xiàn)“abc{3,5}”的匹配，傳統(tǒng)的方法將表達(dá)式展開為“abc{3}”,，“abc{4}”和“abc{5}”,，而后使用OR門連結(jié)三者對(duì)應(yīng)的電路。因此在正則表達(dá)式匹配中設(shè)計(jì)高效的計(jì)數(shù)器實(shí)現(xiàn)約束匹配是非常必要的,。

　　表1給出了4種約束重復(fù)Exactly,，At Least，At Most和Between的規(guī)則表述及相關(guān)實(shí)例,，其中Sub-RE表示約束重復(fù)的對(duì)象。

　　M.Faezipour and M.Nourani在文獻(xiàn)[8]提出了一種針對(duì)NFA匹配算法的約束重復(fù)檢測(cè)方案,，算法使用Sub-Regex單元實(shí)現(xiàn)輸入數(shù)據(jù),，使用Counter Reset單元實(shí)現(xiàn)約束重復(fù)匹配,。Le Hoang Long等對(duì)文獻(xiàn)[8]的方案進(jìn)行改進(jìn)，方案壓縮了復(fù)位單元,，同時(shí)給出了NFA編譯方案,，使通過編譯過程直接避免了字符重疊所造成的失配情況[9]。

　　1.2 解決方案

　　為解決約束重復(fù)問題,，同時(shí)達(dá)到最佳的匹配效率和資源利用率,，提出了一種基于FPGA的重復(fù)約束檢測(cè)方案。該方案與之前提出的基于IMB狀態(tài)遷移方案相結(jié)合,，約束重復(fù)模塊僅需要考慮單字符計(jì)數(shù)功能,。匹配整體架構(gòu)如圖1(a)所示，匹配模塊通過并聯(lián)RAM查找匹配結(jié)果,，將匹配結(jié)果轉(zhuǎn)換為Inc,、Rst_inc等控制信號(hào)輸入到計(jì)數(shù)模塊中，同時(shí)根據(jù)匹配結(jié)果查詢約束重復(fù)參數(shù)N,、M和g值,，并輸入到計(jì)數(shù)模塊中。計(jì)數(shù)模塊根據(jù)控制信號(hào)進(jìn)行計(jì)數(shù)操作,，將得到的計(jì)數(shù)值與N,、M進(jìn)行比較，然后將比較輸出通過一系列與或操作得到最終的匹配信號(hào),。

2 基于FPGA的約束重復(fù)檢測(cè)匹配

　　2.1 匹配模塊

　　將規(guī)則集編譯為XFA后,，需要將XFA的狀態(tài)值和遷移邊進(jìn)行存儲(chǔ)，我們提出了一種高效的遷移邊存取方案,，如圖2,。方案利用FPGA內(nèi)部豐富的存儲(chǔ)器資源，構(gòu)造一個(gè)并聯(lián)存儲(chǔ)塊,，使用存儲(chǔ)器并行查找的方法快速讀取可能遷移邊信息,，通過匹配確定下一狀態(tài)地址。

　　遷移邊根據(jù)目的狀態(tài)的不同分為兩種,，一種為精確轉(zhuǎn)移,，一種為缺省轉(zhuǎn)移。為實(shí)現(xiàn)約束重復(fù)匹配,，遷移邊的定義如圖3所示,，精確轉(zhuǎn)移遷移邊規(guī)則最高位為約束重復(fù)標(biāo)志位CR，當(dāng)CR位為1則表示在對(duì)應(yīng)匹配字符處存在約束重復(fù),；而后存儲(chǔ)的是規(guī)則類型（Type）,，下一狀態(tài)（Next state）和匹配字符（Matching char）。缺省轉(zhuǎn)移遷移邊由高位到低位分別存儲(chǔ)轉(zhuǎn)移邊數(shù)目（Transition number）、下一狀態(tài)（Next state）,、匹配規(guī)則號(hào)（MatchID）/約束重復(fù)參數(shù)地址（CR_addr）,，當(dāng)CR位為1時(shí)，MatchID/CR_addr中存儲(chǔ)的是CR_addr,。轉(zhuǎn)移規(guī)則各個(gè)部分的空間大小由規(guī)則集對(duì)應(yīng)的XFA大小決定,。

　　約束重復(fù)參數(shù)存儲(chǔ)在內(nèi)部存儲(chǔ)器中，每一個(gè)地址存儲(chǔ)的數(shù)據(jù)包括標(biāo)識(shí)信號(hào)g,，數(shù)據(jù)存儲(chǔ)格式標(biāo)識(shí)符Flag,，數(shù)據(jù)Data，如圖4所示,。標(biāo)識(shí)符Flag用于區(qū)別數(shù)據(jù)的存儲(chǔ)格式,，當(dāng)Flag=0時(shí)，表示約束重復(fù)中N=M類,，即Exactly,、At Most類。另外,，為方便計(jì)算,，我們將At Least 類也歸為N=M類，此時(shí)Data域中存儲(chǔ)的數(shù)據(jù)為M/N值,。當(dāng)Flag=1時(shí)表示約束重復(fù)中M>N類,，即Between類，此時(shí)Data域分為data1,、data2兩部分,，分別儲(chǔ)存M值和N值。存儲(chǔ)器大小的設(shè)置由存儲(chǔ)規(guī)則決定,，例如Snort規(guī)則集,，N=M類約束重復(fù)M/N的最大取值Mmax=Nmax=1 286，取b=11 bit,；M>N類M和N的最大取值分別為,，取a=7 bit，b=16 bit,。二者比較取大值則取b=16 bit,，此時(shí)存儲(chǔ)器大小為18 bit。

　　2.2 計(jì)數(shù)模塊

　　計(jì)數(shù)模塊由計(jì)數(shù)器,、比較器,、數(shù)據(jù)選擇器以及與門或門組成。計(jì)數(shù)器根據(jù)輸入的Inc,、Rst_inc控制信號(hào)進(jìn)行計(jì)數(shù)操作,，Inc信號(hào)為約束重復(fù)標(biāo)識(shí),，當(dāng)匹配模塊匹配的字符為約束重復(fù)Sub-RE的最后一個(gè)字符時(shí)，其輸出信號(hào)Inc為高電平,，當(dāng)Inc為高電平時(shí),，每個(gè)時(shí)鐘計(jì)數(shù)器計(jì)數(shù)值q進(jìn)行一次加1操作,；Rst_inc為局部復(fù)位信號(hào),，當(dāng)匹配模塊約束重復(fù)匹配成功或者失敗時(shí)產(chǎn)生一次局部復(fù)位信號(hào)，計(jì)數(shù)值q的復(fù)位值為1,。比較器將計(jì)數(shù)值q與數(shù)據(jù)信號(hào)M和N進(jìn)行比較,，當(dāng)n≤q≤m時(shí)比較器輸出為1。數(shù)據(jù)選擇器根據(jù)控制信號(hào)g來控制在At Least約束重復(fù)情況下計(jì)數(shù)器的使能,。

　　根據(jù)約束類型的不同,，計(jì)數(shù)器參數(shù)取值如表2示所示。

　　之前的計(jì)數(shù)器對(duì)At Least約束類處理是將“(Sub-RE){n,}”分解為“(Sub-RE){n}(Sub-RE)*”,?！?Sub-RE){n}”使用計(jì)數(shù)器exactly模式進(jìn)行匹配，而“(Sub-RE)*”則通過匹配模式的狀態(tài)遷移來實(shí)現(xiàn),，兩者結(jié)合需要在匹配模塊與計(jì)數(shù)器模塊之間增加額外的控制信號(hào),，增大系統(tǒng)的資源開銷。

　　經(jīng)過分析,，當(dāng)計(jì)數(shù)器計(jì)數(shù)值q介于n和m之間時(shí),，除At Least情況，其它情況輸入信號(hào)O均為高電平,，此時(shí)g=0,；而當(dāng)q≥m時(shí)，At Least輸出O為高電平,，此時(shí)g=1,。由此我們可以通過在輸入時(shí)加入標(biāo)識(shí)信號(hào)g來解決At Least類的計(jì)數(shù)問題。得到O的輸出取值為：

　　2.2.1 約束重復(fù)重疊情況分析與處理

　　重疊的定義為：輸入字符部分字符在同一RE的不同位置發(fā)生匹配,。約束重復(fù)重疊情況通常出現(xiàn)在Exactly類和Between類中,。例如子正則表達(dá)式為“a{3}cd”，匹配字符為“aaaaacd”,，當(dāng)匹配到第四個(gè)“a”時(shí),，匹配失敗，此時(shí)計(jì)數(shù)器置位,，重新匹配則字符串為“aacd”,，輸出結(jié)果為不匹配，出現(xiàn)漏檢的情況,。

　　根據(jù)約束重復(fù)重疊情況出現(xiàn)位置的不同,，我們分3種情況進(jìn)行處理,。當(dāng)出現(xiàn)在開始位置時(shí)，上述例子的漏檢情況將會(huì)發(fā)生,，此時(shí)僅需要將Exactly類和Between類改為At Least類即可,；當(dāng)出現(xiàn)在中間位置，例如子正則表達(dá)式為“9a{3}cd”,，匹配字符為“9aaaacd”,，兩者顯然不匹配，計(jì)數(shù)器在匹配三個(gè)“a”后置位將不會(huì)影響匹配結(jié)果,；當(dāng)出現(xiàn)在末尾時(shí),，此時(shí)Exactly類和Between類匹配效果與At Least類相同，不會(huì)造成漏檢的情況,。

　　2.2.2 計(jì)數(shù)器溢出處理

　　At Least約束重復(fù)當(dāng)出現(xiàn)惡意攻擊使重復(fù)匹配數(shù)超過計(jì)數(shù)器計(jì)數(shù)值q最大值時(shí)造成計(jì)數(shù)器的溢出,，此時(shí)計(jì)數(shù)器的輸出將發(fā)生錯(cuò)誤。為避免計(jì)數(shù)器的溢出,，我們?cè)O(shè)置計(jì)數(shù)值q的位寬qn≥?骔logMmax」,，其中Mmax為約束重復(fù)M的最大值，在匹配時(shí),，當(dāng)計(jì)數(shù)值q≥m時(shí)取q=m,。此時(shí)O的輸出取值為：

　　圖1(b)所示是根據(jù)式(2)生成的約束重復(fù)結(jié)構(gòu)圖。

3 實(shí)驗(yàn)及性能分析

　　實(shí)驗(yàn)從Snort2.9.7.3中選擇約束重復(fù)規(guī)則進(jìn)行計(jì)數(shù)模塊實(shí)驗(yàn)仿真,，輔助存儲(chǔ)器中存儲(chǔ)的參數(shù)向量寬度為18 bit,，其中a=7 bit，b=16 bit,，標(biāo)志位Flag和g各占1 bit,。仿真在Quartus軟件使用ALTERA DE2-70系列開發(fā)平臺(tái)，通過綜合得到計(jì)數(shù)器模塊使用硬件資源為：23個(gè)LE,，11個(gè)reg,，模塊工作最大時(shí)鐘頻率為373.83 MHz，而匹配模塊最大時(shí)鐘頻率為281.9 MHz,，完全可以滿足匹配系統(tǒng)的計(jì)數(shù)操作,。如圖5所示是計(jì)數(shù)器對(duì)M=N類約束重復(fù)（圖5(a)）和M>N類約束重復(fù)（圖5(b)）使用ModelSim軟件進(jìn)行功能仿真得到的仿真波形圖。

　　在Snort2.9.7.3[2] 13 529條包含正則表示式的規(guī)則中,，8 036條規(guī)則包含約束重復(fù)匹配,，占規(guī)則數(shù)的59.4%。表3給出了使用Snort規(guī)則集Oracle,、Web-misc,、Web-cgi進(jìn)行實(shí)驗(yàn)分析的結(jié)果，從表中可以看出,，使用計(jì)數(shù)器對(duì)約束重復(fù)問題進(jìn)行處理,，與傳統(tǒng)的展開匹配方式相比,，大大降低了存儲(chǔ)器的消耗量，規(guī)則中約束重復(fù)所占比例越高,，優(yōu)化效果越明顯,。

4 結(jié)束語

　　本文我們針對(duì)XFA設(shè)計(jì)了一種高效的基于FPGA的約束重復(fù)檢測(cè)匹配模塊，模塊與基于并聯(lián)RAM的匹配模塊相結(jié)合,，通過約束重復(fù)參數(shù)儲(chǔ)存器可以實(shí)現(xiàn)約束重復(fù)高效檢測(cè)匹配,。計(jì)數(shù)模塊在實(shí)現(xiàn)約束重復(fù)檢測(cè)匹配的同時(shí)避免了因At Least類在起始位置可能引起的失配情況。計(jì)數(shù)器模塊的實(shí)現(xiàn)僅需要少量的基本邏輯單元LE和寄存器,，工作頻率可達(dá)到373.83 MHz,，將Snort中部分規(guī)則集進(jìn)行編譯分析,，該方案可以壓縮50%以上的正則表達(dá)式規(guī)則存儲(chǔ)空間,，部分規(guī)則集的壓縮比例可達(dá)99%。

　　參考文獻(xiàn)

　　[1] 張樹壯,，羅浩,，方濱興，等.一種面向網(wǎng)絡(luò)安全檢測(cè)的高性能正則表達(dá)式匹配算法[J].計(jì)算機(jī)學(xué)報(bào),，2010,，33(10)：1976-1986.

　　[2] Snort 2.9.7.3.2016.http：//www.snort.org.

　　[3] DIEN N K，HIEU T T,，THINH T N.Memory-based multipattern signature scanning for clamAV antivirus[M].Future Data and Security Engineering.Springer International Publishing,，2014：58-70.

　　[4] KUMAR S，DHARMAPURIKAR S,，YU F,，et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection[C].Proceedings of the 2006 Conference on Applications，Technologies,，Architectures,，and Protocols for Computer Communications.New York：ACM Press，2006：339-350.　

　　[5] BECCHI M,，ROWL C E P.A hybrid finite automaton for 　practical deep packet inspection.Proceedings of the ACM CoNEXT.New York,，2007：1-12.

　　[6] 魏德志，洪聯(lián)系,，林麗娜,，等.一種改進(jìn)的XFA在深度包檢測(cè)中的應(yīng)用[J].Computer Engineering and Applications，2012,，48(34).

　　[7] 張樹壯,，羅浩，方濱興.面向網(wǎng)絡(luò)安全的正則表達(dá)式匹配技術(shù)[J].軟件學(xué)報(bào),，2011,，22(8)：1838-1853.

　　[8] AEZIPOUR M,，NOURANI M.Constraint repetition inspection for regular expression on FPGA[C].Proc.of the 2008 16th IEEE Symp.on High Performance Interconnects.Washington，2008.111-118.

　　[9] LONG H L,，HIEU T T,，TAI V T，et al.ECEB：enhanced constraint repetition block for regular expression matching on FPGA[J].ECTI Transactions on Electrical Engineering,，Electronics,，and Communications，2011,，9：65-74.