文獻標識碼： 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 引言
正則表達式使用標準的語法規則來描述模式，與精確字符串相比，正則表達式可以描述復雜的字符序列，并降低空間復雜度。強大的表達能力使正則表達式在網絡安全領域廣泛應用，成為描述規則的主要工具[1]，目前主流的入侵檢測/防御系統(NIDS/NIPS)，例如Snort[2]、ClamAV[3]等已經將基于正則表達式的規則集成到其過濾系統中，且所占比重逐漸增大。
有限狀態機（FA）和正則表達式所描述的語言都是正則語言，因此有限狀態機是實現正則表達式匹配的主要方法。有限狀態機通常分為兩種：確定性有限狀態機(DFA)和非確定性有限狀態機(NFA)，通過對兩種狀態機深入而細致的研究和分析，Washington University的Kumar和Becchi等人提出了D2FA[4]、混合自動機(Hy brid-FA)[5]以及XFA[6]等方法來實現大規模正則表達式的實用化[7]。
XFA算法是比較高效的正則表達式匹配算法，算法使用輔助變量和簡單的操作指令消除了由*、[ ]和{ }等重復匹配造成的DFA空間爆炸問題，降低了狀態空間的存儲需求。
為提高檢測引擎的吞吐量，同時擺脫系統對引擎的約束以及引擎對系統的性能影響，使用專用器件實現入侵檢測的包過濾過程成為目前的發展趨勢。FPGA由于高速并行可在線編程等優點成為硬件檢測引擎的實驗開發和應用平臺。
硬件實現XFA算法，若使用輔助變量和指令解決約束重復計數問題，則需要對存在約束重復的規則單獨進行處理，消耗大量的硬件資源。本文針對這個情況設計專用計數器結構解決約束重復問題。
1 約束重復問題
1.1 問題的提出
傳統處理約束重復問題的方法是將約束重復的內容展開，描述為精確匹配串的形式，在Snort規則集中存在約束重復數百上千次的規則，若使用展開的方法進行匹配將消耗大量的硬件資源，匹配效率低下。此外為現在4種類型的約束匹配，必須設計多種類型的匹配電路，例如要實現“abc{3,5}”的匹配，傳統的方法將表達式展開為“abc{3}”，“abc{4}”和“abc{5}”，而后使用OR門連結三者對應的電路。因此在正則表達式匹配中設計高效的計數器實現約束匹配是非常必要的。
表1給出了4種約束重復Exactly，At Least，At Most和Between的規則表述及相關實例，其中Sub-RE表示約束重復的對象。
M.Faezipour and M.Nourani在文獻[8]提出了一種針對NFA匹配算法的約束重復檢測方案，算法使用Sub-Regex單元實現輸入數據，使用Counter Reset單元實現約束重復匹配。Le Hoang Long等對文獻[8]的方案進行改進，方案壓縮了復位單元，同時給出了NFA編譯方案，使通過編譯過程直接避免了字符重疊所造成的失配情況[9]。
1.2 解決方案
為解決約束重復問題，同時達到最佳的匹配效率和資源利用率，提出了一種基于FPGA的重復約束檢測方案。該方案與之前提出的基于IMB狀態遷移方案相結合，約束重復模塊僅需要考慮單字符計數功能。匹配整體架構如圖1(a)所示，匹配模塊通過并聯RAM查找匹配結果，將匹配結果轉換為Inc、Rst_inc等控制信號輸入到計數模塊中，同時根據匹配結果查詢約束重復參數N、M和g值，并輸入到計數模塊中。計數模塊根據控制信號進行計數操作，將得到的計數值與N、M進行比較，然后將比較輸出通過一系列與或操作得到最終的匹配信號。
2 基于FPGA的約束重復檢測匹配
2.1 匹配模塊
將規則集編譯為XFA后，需要將XFA的狀態值和遷移邊進行存儲，我們提出了一種高效的遷移邊存取方案，如圖2。方案利用FPGA內部豐富的存儲器資源，構造一個并聯存儲塊，使用存儲器并行查找的方法快速讀取可能遷移邊信息，通過匹配確定下一狀態地址。
遷移邊根據目的狀態的不同分為兩種，一種為精確轉移，一種為缺省轉移。為實現約束重復匹配，遷移邊的定義如圖3所示，精確轉移遷移邊規則最高位為約束重復標志位CR，當CR位為1則表示在對應匹配字符處存在約束重復；而后存儲的是規則類型（Type），下一狀態（Next state）和匹配字符（Matching char）。缺省轉移遷移邊由高位到低位分別存儲轉移邊數目（Transition number）、下一狀態（Next state）、匹配規則號（MatchID）/約束重復參數地址（CR_addr），當CR位為1時，MatchID/CR_addr中存儲的是CR_addr。轉移規則各個部分的空間大小由規則集對應的XFA大小決定。
約束重復參數存儲在內部存儲器中，每一個地址存儲的數據包括標識信號g，數據存儲格式標識符Flag，數據Data，如圖4所示。標識符Flag用于區別數據的存儲格式，當Flag=0時，表示約束重復中N=M類，即Exactly、At Most類。另外，為方便計算，我們將At Least 類也歸為N=M類，此時Data域中存儲的數據為M/N值。當Flag=1時表示約束重復中M>N類，即Between類，此時Data域分為data1、data2兩部分，分別儲存M值和N值。存儲器大小的設置由存儲規則決定，例如Snort規則集，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 計數模塊
計數模塊由計數器、比較器、數據選擇器以及與門或門組成。計數器根據輸入的Inc、Rst_inc控制信號進行計數操作，Inc信號為約束重復標識，當匹配模塊匹配的字符為約束重復Sub-RE的最后一個字符時，其輸出信號Inc為高電平，當Inc為高電平時，每個時鐘計數器計數值q進行一次加1操作；Rst_inc為局部復位信號，當匹配模塊約束重復匹配成功或者失敗時產生一次局部復位信號，計數值q的復位值為1。比較器將計數值q與數據信號M和N進行比較，當n≤q≤m時比較器輸出為1。數據選擇器根據控制信號g來控制在At Least約束重復情況下計數器的使能。
根據約束類型的不同，計數器參數取值如表2示所示。
之前的計數器對At Least約束類處理是將“(Sub-RE){n,}”分解為“(Sub-RE){n}(Sub-RE)*”。“(Sub-RE){n}”使用計數器exactly模式進行匹配，而“(Sub-RE)*”則通過匹配模式的狀態遷移來實現，兩者結合需要在匹配模塊與計數器模塊之間增加額外的控制信號，增大系統的資源開銷。
經過分析，當計數器計數值q介于n和m之間時，除At Least情況，其它情況輸入信號O均為高電平，此時g=0；而當q≥m時，At Least輸出O為高電平，此時g=1。由此我們可以通過在輸入時加入標識信號g來解決At Least類的計數問題。得到O的輸出取值為：
2.2.1 約束重復重疊情況分析與處理
重疊的定義為：輸入字符部分字符在同一RE的不同位置發生匹配。約束重復重疊情況通常出現在Exactly類和Between類中。例如子正則表達式為“a{3}cd”，匹配字符為“aaaaacd”，當匹配到第四個“a”時，匹配失敗，此時計數器置位，重新匹配則字符串為“aacd”，輸出結果為不匹配，出現漏檢的情況。
根據約束重復重疊情況出現位置的不同，我們分3種情況進行處理。當出現在開始位置時，上述例子的漏檢情況將會發生，此時僅需要將Exactly類和Between類改為At Least類即可；當出現在中間位置，例如子正則表達式為“9a{3}cd”，匹配字符為“9aaaacd”，兩者顯然不匹配，計數器在匹配三個“a”后置位將不會影響匹配結果；當出現在末尾時，此時Exactly類和Between類匹配效果與At Least類相同，不會造成漏檢的情況。
2.2.2 計數器溢出處理
At Least約束重復當出現惡意攻擊使重復匹配數超過計數器計數值q最大值時造成計數器的溢出，此時計數器的輸出將發生錯誤。為避免計數器的溢出，我們設置計數值q的位寬qn≥?骔logMmax」，其中Mmax為約束重復M的最大值，在匹配時，當計數值q≥m時取q=m。此時O的輸出取值為：
圖1(b)所示是根據式(2)生成的約束重復結構圖。
3 實驗及性能分析
實驗從Snort2.9.7.3中選擇約束重復規則進行計數模塊實驗仿真，輔助存儲器中存儲的參數向量寬度為18 bit，其中a=7 bit，b=16 bit，標志位Flag和g各占1 bit。仿真在Quartus軟件使用ALTERA DE2-70系列開發平臺，通過綜合得到計數器模塊使用硬件資源為：23個LE，11個reg，模塊工作最大時鐘頻率為373.83 MHz，而匹配模塊最大時鐘頻率為281.9 MHz，完全可以滿足匹配系統的計數操作。如圖5所示是計數器對M=N類約束重復（圖5(a)）和M>N類約束重復（圖5(b)）使用ModelSim軟件進行功能仿真得到的仿真波形圖。
在Snort2.9.7.3[2] 13 529條包含正則表示式的規則中，8 036條規則包含約束重復匹配，占規則數的59.4%。表3給出了使用Snort規則集Oracle、Web-misc、Web-cgi進行實驗分析的結果，從表中可以看出，使用計數器對約束重復問題進行處理，與傳統的展開匹配方式相比，大大降低了存儲器的消耗量，規則中約束重復所占比例越高，優化效果越明顯。
4 結束語
本文我們針對XFA設計了一種高效的基于FPGA的約束重復檢測匹配模塊，模塊與基于并聯RAM的匹配模塊相結合，通過約束重復參數儲存器可以實現約束重復高效檢測匹配。計數模塊在實現約束重復檢測匹配的同時避免了因At Least類在起始位置可能引起的失配情況。計數器模塊的實現僅需要少量的基本邏輯單元LE和寄存器，工作頻率可達到373.83 MHz，將Snort中部分規則集進行編譯分析，該方案可以壓縮50%以上的正則表達式規則存儲空間，部分規則集的壓縮比例可達99%。
參考文獻
[1] 張樹壯，羅浩，方濱興，等.一種面向網絡安全檢測的高性能正則表達式匹配算法[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] 魏德志，洪聯系，林麗娜，等.一種改進的XFA在深度包檢測中的應用[J].Computer Engineering and Applications，2012，48(34).
[7] 張樹壯，羅浩，方濱興.面向網絡安全的正則表達式匹配技術[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.