麥濤濤，潘曉中，王亞奇

(武警工程大學(xué) 電子技術(shù)系網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室，陜西 西安710086)

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

麥濤濤，潘曉中，王亞奇

(武警工程大學(xué) 電子技術(shù)系網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室，陜西 西安710086)

針對(duì)目前正則表達(dá)式匹配中約束重復(fù)問(wèn)題所帶來(lái)的空間消耗爆炸以及失配等問(wèn)題，基于FPGA設(shè)計(jì)了一種硬件約束重復(fù)檢測(cè)匹配模塊，該模塊與基于并聯(lián)ROM的XFA匹配模塊相結(jié)合，可以快速實(shí)現(xiàn)約束重復(fù)的檢測(cè)和匹配。通過(guò)定義約束重復(fù)參數(shù)存儲(chǔ)器，計(jì)數(shù)模塊僅消耗少量的硬件資源即可實(shí)現(xiàn)約束重復(fù)的檢測(cè)匹配。實(shí)驗(yàn)中計(jì)數(shù)模塊可實(shí)現(xiàn)Gbps的吞吐量，同時(shí)使正則表示式規(guī)則存儲(chǔ)空間壓縮50%以上。

約束重復(fù)；FPGA；并聯(lián)ROM

0　引言

正則表達(dá)式使用標(biāo)準(zhǔn)的語(yǔ)法規(guī)則來(lái)描述模式，與精確字符串相比，正則表達(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ī)則集成到其過(guò)濾系統(tǒng)中，且所占比重逐漸增大。

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

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

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

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

1　約束重復(fù)問(wèn)題

1.1問(wèn)題的提出

傳統(tǒng)處理約束重復(fù)問(wèn)題的方法是將約束重復(fù)的內(nèi)容展開(kāi)，描述為精確匹配串的形式，在 Snort規(guī)則集中存在約束重復(fù)數(shù)百上千次的規(guī)則，若使用展開(kāi)的方法進(jìn)行匹配將消耗大量的硬件資源，匹配效率低下。此外為現(xiàn)在4種類型的約束匹配，必須設(shè)計(jì)多種類型的匹配電路，例如要實(shí)現(xiàn)“abc{3,5}”的匹配，傳統(tǒng)的方法將表達(dá)式展開(kāi)為“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ì)象。

表1　約束重復(fù)類型、定義及實(shí)例

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編譯方案，使通過(guò)編譯過(guò)程直接避免了字符重疊所造成的失配情況[9]。

1.2解決方案

為解決約束重復(fù)問(wèn)題，同時(shí)達(dá)到最佳的匹配效率和資源利用率，提出了一種基于FPGA的重復(fù)約束檢測(cè)方案。該方案與之前提出的基于IMB狀態(tài)遷移方案相結(jié)合，約束重復(fù)模塊僅需要考慮單字符計(jì)數(shù)功能。匹配整體架構(gòu)如圖1(a)所示，匹配模塊通過(guò)并聯(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)行比較，然后將比較輸出通過(guò)一系列與或操作得到最終的匹配信號(hào)。

圖1　檢測(cè)引擎結(jié)構(gòu)圖

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ǔ)器并行查找的方法快速讀取可能遷移邊信息，通過(guò)匹配確定下一狀態(tài)地址。

圖2　匹配模塊結(jié)構(gòu)圖

遷移邊根據(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大小決定。

圖3　遷移邊定義

約束重復(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的最大取值分別為=300、=100，取 a=7 bit，b=16 bit。二者比較取大值則取 b=16 bit，此時(shí)存儲(chǔ)器大小為18 bit。

圖4　約束重復(fù)參數(shù)存儲(chǔ)器定義

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來(lái)控制在 At Least約束重復(fù)情況下計(jì)數(shù)器的使能。

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

表2　計(jì)數(shù)器參數(shù)設(shè)置

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

經(jīng)過(guò)分析，當(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。由此我們可以通過(guò)在輸入時(shí)加入標(biāo)識(shí)信號(hào)g來(lái)解決At Least類的計(jì)數(shù)問(wèn)題。得到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)在開(kāi)始位置時(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ù)超過(guò)計(jì)數(shù)器計(jì)數(shù)值q最大值時(shí)造成計(jì)數(shù)器的溢出，此時(shí)計(jì)數(shù)器的輸出將發(fā)生錯(cuò)誤。為避免計(jì)數(shù)器的溢出，我們?cè)O(shè)置計(jì)數(shù)值 q的位寬，其中 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系列開(kāi)發(fā)平臺(tái)，通過(guò)綜合得到計(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)行功能仿真得到的仿真波形圖。

圖5　仿真波形圖

在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ù)問(wèn)題進(jìn)行處理，與傳統(tǒng)的展開(kāi)匹配方式相比，大大降低了存儲(chǔ)器的消耗量，規(guī)則中約束重復(fù)所占比例越高，優(yōu)化效果越明顯。

表3Snort規(guī)則集實(shí)驗(yàn)分析

4　結(jié)束語(yǔ)

本文我們針對(duì) XFA設(shè)計(jì)了一種高效的基于 FPGA的約束重復(fù)檢測(cè)匹配模塊，模塊與基于并聯(lián)RAM的匹配模塊相結(jié)合，通過(guò)約束重復(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%。

[1]張樹(shù)壯，羅浩，方濱興，等.一種面向網(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]張樹(shù)壯，羅浩，方濱興.面向網(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.

Constraint repetition inspection for XFA on FPGA

Mai Taotao，Pan Xiaozhong，Wang Yaqi
(Key Laboratory of Network and Information Security of the CAPF，Department of Electronic Technology，Engineering University of the CAPF，Xi′an 710086，China)

Aiming at the space explosion and mismatching problems posed by complex constraint repetitions in regular expression.This paper designs a FPGA-based hardware constraint repetition inspection block.Combining with the interleaved ROM block,this block can quickly achieve constraint repetition detection and matching.By defining constraint-repetition-parameter-memory,the counting block consumes only a small amount of hardware resources to achieve constrained duplicate detection matches.Experimental results for module that the counting block can reach Gbps throughput and the regular expression rule storage space compression by more than 50%.

constraint repetition；FPGA；interleaved ROM

TP391

A

10.16157/j.issn.0258-7998.2016.09.012

國(guó)家自然科學(xué)基金項(xiàng)目（61402531）；陜西省自然科學(xué)基金項(xiàng)目（2014JQ8307，2015JQ6231）

麥濤濤(1992-)，通信作者，男，碩士研究生，主要研究方向：嵌入式系統(tǒng)、網(wǎng)絡(luò)安全，E-mail：wj_maitao@126.com。

潘曉中(1964-)，男，碩士，教授，主要研究方向：信息研究與安全。

王亞奇(1986-)，男，博士，講師，主要研究方向：網(wǎng)絡(luò)安全。

中文引用格式：麥濤濤，潘曉中，王亞奇.基于 FPGA的XFA約束重復(fù)檢測(cè)匹配[J].電子技術(shù)應(yīng)用，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.