文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.09.012
中文引用格式： 麥濤濤，潘曉中，王亞奇. 基于FPGA的XFA約束重復檢測匹配[J].電子技術應用，2016，42(9)：47-50，54.
英文引用格式： Mai Taotao，Pan Xiaozhong，Wang Yaqi. Constraint repetition inspection for XFA on FPGA[J].Application of Electronic Technique，2016，42(9)：47-50，54.
0 引言
正則表達式使用標準的語法規(guī)則來描述模式，與精確字符串相比，正則表達式可以描述復雜的字符序列，并降低空間復雜度。強大的表達能力使正則表達式在網(wǎ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算法是比較高效的正則表達式匹配算法，算法使用輔助變量和簡單的操作指令消除了由*、[ ]和{ }等重復匹配造成的DFA空間爆炸問題，降低了狀態(tài)空間的存儲需求。
為提高檢測引擎的吞吐量，同時擺脫系統(tǒng)對引擎的約束以及引擎對系統(tǒng)的性能影響，使用專用器件實現(xiàn)入侵檢測的包過濾過程成為目前的發(fā)展趨勢。FPGA由于高速并行可在線編程等優(yōu)點成為硬件檢測引擎的實驗開發(fā)和應用平臺。
硬件實現(xiàn)XFA算法，若使用輔助變量和指令解決約束重復計數(shù)問題，則需要對存在約束重復的規(guī)則單獨進行處理，消耗大量的硬件資源。本文針對這個情況設計專用計數(shù)器結構解決約束重復問題。
1 約束重復問題
1.1 問題的提出
傳統(tǒng)處理約束重復問題的方法是將約束重復的內(nèi)容展開，描述為精確匹配串的形式，在Snort規(guī)則集中存在約束重復數(shù)百上千次的規(guī)則，若使用展開的方法進行匹配將消耗大量的硬件資源，匹配效率低下。此外為現(xiàn)在4種類型的約束匹配，必須設計多種類型的匹配電路，例如要實現(xiàn)“abc{3,5}”的匹配，傳統(tǒng)的方法將表達式展開為“abc{3}”，“abc{4}”和“abc{5}”，而后使用OR門連結三者對應的電路。因此在正則表達式匹配中設計高效的計數(shù)器實現(xiàn)約束匹配是非常必要的。
表1給出了4種約束重復Exactly，At Least，At Most和Between的規(guī)則表述及相關實例，其中Sub-RE表示約束重復的對象。
M.Faezipour and M.Nourani在文獻[8]提出了一種針對NFA匹配算法的約束重復檢測方案，算法使用Sub-Regex單元實現(xiàn)輸入數(shù)據(jù)，使用Counter Reset單元實現(xiàn)約束重復匹配。Le Hoang Long等對文獻[8]的方案進行改進，方案壓縮了復位單元，同時給出了NFA編譯方案，使通過編譯過程直接避免了字符重疊所造成的失配情況[9]。
1.2 解決方案
為解決約束重復問題，同時達到最佳的匹配效率和資源利用率，提出了一種基于FPGA的重復約束檢測方案。該方案與之前提出的基于IMB狀態(tài)遷移方案相結合，約束重復模塊僅需要考慮單字符計數(shù)功能。匹配整體架構如圖1(a)所示，匹配模塊通過并聯(lián)RAM查找匹配結果，將匹配結果轉換為Inc、Rst_inc等控制信號輸入到計數(shù)模塊中，同時根據(jù)匹配結果查詢約束重復參數(shù)N、M和g值，并輸入到計數(shù)模塊中。計數(shù)模塊根據(jù)控制信號進行計數(shù)操作，將得到的計數(shù)值與N、M進行比較，然后將比較輸出通過一系列與或操作得到最終的匹配信號。
2 基于FPGA的約束重復檢測匹配
2.1 匹配模塊
將規(guī)則集編譯為XFA后，需要將XFA的狀態(tài)值和遷移邊進行存儲，我們提出了一種高效的遷移邊存取方案，如圖2。方案利用FPGA內(nèi)部豐富的存儲器資源，構造一個并聯(lián)存儲塊，使用存儲器并行查找的方法快速讀取可能遷移邊信息，通過匹配確定下一狀態(tài)地址。
遷移邊根據(jù)目的狀態(tài)的不同分為兩種，一種為精確轉移，一種為缺省轉移。為實現(xiàn)約束重復匹配，遷移邊的定義如圖3所示，精確轉移遷移邊規(guī)則最高位為約束重復標志位CR，當CR位為1則表示在對應匹配字符處存在約束重復；而后存儲的是規(guī)則類型（Type），下一狀態(tài)（Next state）和匹配字符（Matching char）。缺省轉移遷移邊由高位到低位分別存儲轉移邊數(shù)目（Transition number）、下一狀態(tài)（Next state）、匹配規(guī)則號（MatchID）/約束重復參數(shù)地址（CR_addr），當CR位為1時，MatchID/CR_addr中存儲的是CR_addr。轉移規(guī)則各個部分的空間大小由規(guī)則集對應的XFA大小決定。
約束重復參數(shù)存儲在內(nèi)部存儲器中，每一個地址存儲的數(shù)據(jù)包括標識信號g，數(shù)據(jù)存儲格式標識符Flag，數(shù)據(jù)Data，如圖4所示。標識符Flag用于區(qū)別數(shù)據(jù)的存儲格式，當Flag=0時，表示約束重復中N=M類，即Exactly、At Most類。另外，為方便計算，我們將At Least 類也歸為N=M類，此時Data域中存儲的數(shù)據(jù)為M/N值。當Flag=1時表示約束重復中M>N類，即Between類，此時Data域分為data1、data2兩部分，分別儲存M值和N值。存儲器大小的設置由存儲規(guī)則決定，例如Snort規(guī)則集，N=M類約束重復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信號為約束重復標識，當匹配模塊匹配的字符為約束重復Sub-RE的最后一個字符時，其輸出信號Inc為高電平，當Inc為高電平時，每個時鐘計數(shù)器計數(shù)值q進行一次加1操作；Rst_inc為局部復位信號，當匹配模塊約束重復匹配成功或者失敗時產(chǎn)生一次局部復位信號，計數(shù)值q的復位值為1。比較器將計數(shù)值q與數(shù)據(jù)信號M和N進行比較，當n≤q≤m時比較器輸出為1。數(shù)據(jù)選擇器根據(jù)控制信號g來控制在At Least約束重復情況下計數(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)，兩者結合需要在匹配模塊與計數(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 約束重復重疊情況分析與處理
重疊的定義為：輸入字符部分字符在同一RE的不同位置發(fā)生匹配。約束重復重疊情況通常出現(xiàn)在Exactly類和Between類中。例如子正則表達式為“a{3}cd”，匹配字符為“aaaaacd”，當匹配到第四個“a”時，匹配失敗，此時計數(shù)器置位，重新匹配則字符串為“aacd”，輸出結果為不匹配，出現(xiàn)漏檢的情況。
根據(jù)約束重復重疊情況出現(xiàn)位置的不同，我們分3種情況進行處理。當出現(xiàn)在開始位置時，上述例子的漏檢情況將會發(fā)生，此時僅需要將Exactly類和Between類改為At Least類即可；當出現(xiàn)在中間位置，例如子正則表達式為“9a{3}cd”，匹配字符為“9aaaacd”，兩者顯然不匹配，計數(shù)器在匹配三個“a”后置位將不會影響匹配結果；當出現(xiàn)在末尾時，此時Exactly類和Between類匹配效果與At Least類相同，不會造成漏檢的情況。
2.2.2 計數(shù)器溢出處理
At Least約束重復當出現(xiàn)惡意攻擊使重復匹配數(shù)超過計數(shù)器計數(shù)值q最大值時造成計數(shù)器的溢出，此時計數(shù)器的輸出將發(fā)生錯誤。為避免計數(shù)器的溢出，我們設置計數(shù)值q的位寬qn≥?骔logMmax」，其中Mmax為約束重復M的最大值，在匹配時，當計數(shù)值q≥m時取q=m。此時O的輸出取值為：
圖1(b)所示是根據(jù)式(2)生成的約束重復結構圖。
3 實驗及性能分析
實驗從Snort2.9.7.3中選擇約束重復規(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類約束重復（圖5(a)）和M>N類約束重復（圖5(b)）使用ModelSim軟件進行功能仿真得到的仿真波形圖。
在Snort2.9.7.3[2] 13 529條包含正則表示式的規(guī)則中，8 036條規(guī)則包含約束重復匹配，占規(guī)則數(shù)的59.4%。表3給出了使用Snort規(guī)則集Oracle、Web-misc、Web-cgi進行實驗分析的結果，從表中可以看出，使用計數(shù)器對約束重復問題進行處理，與傳統(tǒng)的展開匹配方式相比，大大降低了存儲器的消耗量，規(guī)則中約束重復所占比例越高，優(yōu)化效果越明顯。
4 結束語
本文我們針對XFA設計了一種高效的基于FPGA的約束重復檢測匹配模塊，模塊與基于并聯(lián)RAM的匹配模塊相結合，通過約束重復參數(shù)儲存器可以實現(xiàn)約束重復高效檢測匹配。計數(shù)模塊在實現(xiàn)約束重復檢測匹配的同時避免了因At Least類在起始位置可能引起的失配情況。計數(shù)器模塊的實現(xiàn)僅需要少量的基本邏輯單元LE和寄存器，工作頻率可達到373.83 MHz，將Snort中部分規(guī)則集進行編譯分析，該方案可以壓縮50%以上的正則表達式規(guī)則存儲空間，部分規(guī)則集的壓縮比例可達99%。
參考文獻
[1] 張樹壯，羅浩，方濱興，等.一種面向網(wǎng)絡安全檢測的高性能正則表達式匹配算法[J].計算機學報，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在深度包檢測中的應用[J].Computer Engineering and Applications，2012，48(34).
[7] 張樹壯，羅浩，方濱興.面向網(wǎng)絡安全的正則表達式匹配技術[J].軟件學報，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.