0 引言

　　正則表達(dá)式使用標(biāo)準(zhǔn)的語法規(guī)則來描述模式，與精確字符串相比，正則表達(dá)式可以描述復(fù)雜的字符序列，并降低空間復(fù)雜度。強(qiáng)大的表達(dá)能力使正則表達(dá)式在網(wǎng)絡(luò)安全領(lǐng)域廣泛應(yīng)用，成為描述規(guī)則的主要工具[1]，目前主流的入侵檢測/防御系統(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á)式匹配算法，算法使用輔助變量和簡單的操作指令消除了由*、[ ]和{ }等重復(fù)匹配造成的DFA空間爆炸問題，降低了狀態(tài)空間的存儲(chǔ)需求。

　　為提高檢測引擎的吞吐量，同時(shí)擺脫系統(tǒng)對(duì)引擎的約束以及引擎對(duì)系統(tǒng)的性能影響，使用專用器件實(shí)現(xiàn)入侵檢測的包過濾過程成為目前的發(fā)展趨勢。FPGA由于高速并行可在線編程等優(yōu)點(diǎn)成為硬件檢測引擎的實(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ù)檢測方案，算法使用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ù)約束檢測方案。該方案與之前提出的基于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ù)檢測匹配

　　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ù)器的溢出，我們設(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ù)檢測匹配模塊，模塊與基于并聯(lián)RAM的匹配模塊相結(jié)合，通過約束重復(fù)參數(shù)儲(chǔ)存器可以實(shí)現(xiàn)約束重復(fù)高效檢測匹配。計(jì)數(shù)模塊在實(shí)現(xiàn)約束重復(fù)檢測匹配的同時(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ò)安全檢測的高性能正則表達(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在深度包檢測中的應(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.