0 引言

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

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

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

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

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

1 約束重復(fù)問題

　　1.1 問題的提出

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

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

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

　　1.2 解決方案

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

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

　　2.1 匹配模塊

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

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

　　約束重復(fù)參數(shù)存儲在內(nèi)部存儲器中,，每一個地址存儲的數(shù)據(jù)包括標識信號g，數(shù)據(jù)存儲格式標識符Flag,，數(shù)據(jù)Data,，如圖4所示。標識符Flag用于區(qū)別數(shù)據(jù)的存儲格式,，當Flag=0時,，表示約束重復(fù)中N=M類，即Exactly,、At Most類,。另外，為方便計算,，我們將At Least 類也歸為N=M類,，此時Data域中存儲的數(shù)據(jù)為M/N值。當Flag=1時表示約束重復(fù)中M>N類,，即Between類,，此時Data域分為data1、data2兩部分,，分別儲存M值和N值,。存儲器大小的設(shè)置由存儲規(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,，此時存儲器大小為18 bit,。

　　2.2 計數(shù)模塊

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

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

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

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

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

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

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

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

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

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

3 實驗及性能分析

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

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

4 結(jié)束語

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

　　參考文獻

　　[1] 張樹壯，羅浩,，方濱興,，等.一種面向網(wǎng)絡(luò)安全檢測的高性能正則表達式匹配算法[J].計算機學(xué)報，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)系，林麗娜,，等.一種改進的XFA在深度包檢測中的應(yīng)用[J].Computer Engineering and Applications,，2012，48(34).

　　[7] 張樹壯,，羅浩,，方濱興.面向網(wǎng)絡(luò)安全的正則表達式匹配技術(shù)[J].軟件學(xué)報，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.