基于預(yù)定義類的緊湊型正則表達(dá)式匹配算法

麥濤濤，潘曉中，王亞奇，蘇 陽

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

(*通信作者電子郵箱wj_maitao@126.com)

基于預(yù)定義類的緊湊型正則表達(dá)式匹配算法

麥濤濤1，2*，潘曉中1，2，王亞奇1，2，蘇 陽1，2

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

(*通信作者電子郵箱wj_maitao@126.com)

針對目前硬件正則表達(dá)式匹配算法在存儲空間以及吞吐量等方面面臨的挑戰(zhàn)，結(jié)合擴(kuò)展有限自動機(jī)(XFA)正則表達(dá)式匹配算法，提出了一種預(yù)定義類的壓縮自動機(jī)匹配算法(Pre-Class CFA)。通過預(yù)定義類，算法既可以實(shí)現(xiàn)正則表達(dá)式中類字符匹配，又能夠通過優(yōu)先級的設(shè)定匹配特殊字符集，并在XFA消除確定性有限狀態(tài)機(jī)(DFA)狀態(tài)爆炸問題的基礎(chǔ)上進(jìn)一步壓縮了遷移邊數(shù)目；同時(shí)算法根據(jù)現(xiàn)場可編程門陣列(FPGA)和遷移邊的特征，設(shè)計(jì)了一種基于并聯(lián)只讀存儲器(ROM)結(jié)構(gòu)的遷移邊存取方法，可以實(shí)現(xiàn)同一狀態(tài)多條遷移邊的并行讀取和匹配。在中低性能FPGA平臺ALTERA DE2- 70上對算法進(jìn)行測試，實(shí)驗(yàn)中系統(tǒng)吞吐量為1.3 Gb/s，可實(shí)現(xiàn)千兆網(wǎng)絡(luò)下的入侵檢測和垃圾過濾。

正則表達(dá)式匹配；擴(kuò)展有限自動機(jī)；現(xiàn)場可編程門陣列

0 引言

隨著海量信息處理和大數(shù)據(jù)處理等技術(shù)的發(fā)展，網(wǎng)絡(luò)應(yīng)用對海量信息下匹配引擎的性能提出了更高的要求[1]。深度包過濾(Deep Packet Inspection, DPI)技術(shù)作為網(wǎng)絡(luò)過濾系統(tǒng)的核心，采用特征匹配算法將數(shù)據(jù)包中的數(shù)據(jù)與預(yù)定義的惡意數(shù)據(jù)特征碼進(jìn)行匹配，從而濾除惡意數(shù)據(jù)包。由木桶原理可知，網(wǎng)絡(luò)安全應(yīng)用中，模式匹配在最差情況下的性能決定了系統(tǒng)在線工作性能。為此，提高模式匹配在最差情況下的性能是入侵檢測系統(tǒng)的關(guān)鍵問題[2]。

模式匹配廣泛應(yīng)用于信息檢索、模式識別、入侵檢測、內(nèi)容過濾、病毒代碼檢測、基因匹配等眾多領(lǐng)域[3]。模式匹配根據(jù)模式串的描述方式可分為字符串匹配和正則表達(dá)式匹配。隨著網(wǎng)絡(luò)的不斷發(fā)展，惡意數(shù)據(jù)特征碼長度、數(shù)目和種類增長迅速，正則表達(dá)式描述方式以其較強(qiáng)的表達(dá)能力逐步應(yīng)用成為主流網(wǎng)絡(luò)安全系統(tǒng)，例如Snort[4]、Clam AV[5]等數(shù)據(jù)庫的主要描述形式。表1給出了不同版本的Snort規(guī)則數(shù)目以及Pcre規(guī)則所占比例[4]。正則表達(dá)式匹配算法是本文研究的主要內(nèi)容。

表1 Snort規(guī)則集統(tǒng)計(jì)分析結(jié)果

正則表達(dá)式匹配通常采用確定性有限狀態(tài)機(jī)(Deterministic Finite Automaton, DFA)。DFA處理每個(gè)字符僅需要訪問一個(gè)狀態(tài)，避免了回溯問題，匹配速度快，但是DFA編譯速度慢、空間消耗大等問題，限制了其在基于硬件的正則表達(dá)式匹配系統(tǒng)中的發(fā)展和應(yīng)用。

針對DFA存儲空間需求大的問題，近幾年，研究者提出了多種DFA的改進(jìn)算法。Smith等[6]提出一種采用輔助變量代替額外狀態(tài)的DFA改進(jìn)算法——擴(kuò)展有限自動機(jī)(Extended Finite Automaton, XFA)匹配算法，其通過簡單的指令操作來檢測是否匹配成功，能消除DFA狀態(tài)空間爆炸問題，與DFA相比，XFA的狀態(tài)空間數(shù)減少了4個(gè)數(shù)量級，匹配時(shí)間與DFA接近。黃昆等[7]在XFA算法的基礎(chǔ)上利用優(yōu)先級壓縮和位圖存儲的方法提出了壓縮有限自動機(jī)(Compact Finite Automaton, CFA)算法，在遷移邊壓縮方面取得了不錯的效果；但是算法規(guī)則匹配使用二次查找，當(dāng)網(wǎng)絡(luò)中出現(xiàn)分布式拒絕服務(wù)(Distributed Denial of Service, DDoS)攻擊時(shí)容易出現(xiàn)丟包、漏包的情況。張大方等[8]提出的智能有限自動機(jī)(Smart Finite Automaton， SFA)算法有效解決了XFA算法冗余遷移邊的問題，通過增加輔助判斷指令避免了狀態(tài)機(jī)重復(fù)匹配的情況。IBM蘇黎世實(shí)驗(yàn)室提出了一種基于緊湊型DFA和XFA的正則表達(dá)式匹配引擎，該引擎適用于少量規(guī)則的匹配操作，當(dāng)規(guī)則數(shù)為600時(shí)，吞吐率可達(dá)到45 Gb/s，隨著規(guī)則數(shù)目的增多，引擎的吞吐率呈指數(shù)下降[9]。以上基于XFA的改進(jìn)算法對包含克林閉合組“.*”“[]”以及“{}”等元字符的正則表達(dá)式優(yōu)化效果明顯，但是針對d / [0- 9](匹配數(shù)字)、[a-z](匹配小寫字母)、[bB](不區(qū)分大小寫)等類字符匹配，XFA并不能對遷移邊進(jìn)行有效壓縮。本文結(jié)合XFA提出了一種基于預(yù)定義類的緊湊型自動機(jī)(Pre-Class CFA)匹配算法。

1 擴(kuò)展有限自動機(jī)概述

DFA狀態(tài)爆炸的根本原因是當(dāng)多個(gè)DFA組合成一個(gè)DFA時(shí)，單個(gè)DFA的歧義路徑和非歧義路徑相互組合，導(dǎo)致組合DFA產(chǎn)生大量的額外狀態(tài)，使消耗的空間量呈指數(shù)級增長[8]。DFA的定義如下：D={Q,Σ,δ,q0,F}。其中:Q為狀態(tài)集，Σ為字母表，δ為遷移函數(shù)，q0為初始狀態(tài)，F(xiàn)為接受狀態(tài)集。例如正則表達(dá)式集{.*ab.*cd, .*ef.*gh}，其聯(lián)合DFA結(jié)構(gòu)圖如圖1(a)所示，圖中省略了其他狀態(tài)到初始狀態(tài)的失敗轉(zhuǎn)移。從圖1可以看出，由于單個(gè)DFA中存在通配符“.*”，使得當(dāng)兩個(gè)DFA的狀態(tài)進(jìn)行交叉組合時(shí)，狀態(tài)機(jī)中狀態(tài)數(shù)目呈指數(shù)級增長，造成組合DFA空間爆炸[10]。

為消除組合DFA狀態(tài)空間爆炸的問題，Smith等[6]提出了XFA解決方案，使用輔助變量代替額外狀態(tài)來記錄部分匹配的結(jié)果。XFA匹配時(shí)，當(dāng)讀入一個(gè)字符，XFA檢查當(dāng)前狀態(tài)對應(yīng)遷移邊遷移的下一狀態(tài)，在執(zhí)行下一狀態(tài)指令時(shí)檢測輔助變量，從而判斷是否匹配成功[8]。XFA定義如下：X={Q,V,Σ,δ,U,(q0,v0),F}。其中：V表示輔助變量集，U表示每個(gè)狀態(tài)的更新函數(shù)，v0表示輔助變量的初始值，其余參數(shù)與DFA相同。圖1(b)給出了使用XFA匹配{.*ab.*cd, .*ef.*gh}的狀態(tài)圖，在組合XFA狀態(tài)PV上添加bit1和bit2的賦值操作指令，在狀態(tài)SV、PY上分別增加bit1和bit2的判斷指令，在整個(gè)組合XFA中共需要7個(gè)狀態(tài)和2個(gè)輔助變量，相比DFA中的15個(gè)狀態(tài)減小了50%。輔助變量的引入使XFA解決了DFA狀態(tài)空間爆炸問題。

圖1 {.*ab.*cd, .*ef.*gh}狀態(tài)圖

2 基于預(yù)定義類的緊湊型自動機(jī)

從圖1(b)可以看到緊湊型自動機(jī)可以有效地解決由克林閉合組“.*”所帶來的狀態(tài)爆炸問題，同時(shí)利用輔助變量也可以避免由“[]”“{}”等多次重復(fù)匹配元字符所帶來的狀態(tài)爆炸，但是對于規(guī)則集中常見的不區(qū)分大小寫、特殊字符類匹配等元字符匹配所造成的空間復(fù)雜度的增加，XFA算法未給出有效的解決方案。本文結(jié)合XFA使用的指令方法，提出了可以匹配字符類的Pre-ClassCFA正則表達(dá)式匹配算法。

2.1 基于預(yù)定義類的遷移邊壓縮方法

Pre-ClassCFA支持多種形式的狀態(tài)遷移，不僅包括XFA中的精確匹配，還支持不區(qū)分大小寫、類匹配和缺省轉(zhuǎn)移等特殊遷移。

類匹配[11]可以實(shí)現(xiàn)字符類，例如數(shù)字([0- 9]或d)、字母([a-z]以及[A-Z])、字類字符([A-Za-z0- 9]或w)以及對應(yīng)的否定形式等全部或者部分字符的匹配。通過定義類可以實(shí)現(xiàn)多條相同初始狀態(tài)和目的狀態(tài)遷移邊的歸一化，減少遷移邊的數(shù)目，降低算法的空間和時(shí)間復(fù)雜度。在算法設(shè)計(jì)中將不區(qū)分大小寫也歸到類匹配進(jìn)行處理。

例如規(guī)則“a[bB][^c][0- 8]*9[a-z]”，其DFA狀態(tài)轉(zhuǎn)移圖如圖2所示，規(guī)則中出現(xiàn)了不區(qū)分大小寫匹配[bB]、數(shù)字類匹配[0- 8]和小寫字母匹配[a-z]，若按照傳統(tǒng)自動機(jī)匹配則以上三個(gè)狀態(tài)轉(zhuǎn)移需要消耗37個(gè)存儲空間。通過分析ASCII碼的特點(diǎn)，不區(qū)分大小寫、數(shù)字、字母等類字符可以通過特殊的匹配規(guī)則使用一條轉(zhuǎn)移規(guī)則進(jìn)行處理。例如不區(qū)分大小寫[bB]，由于在ASCII碼中大小寫字母ASCII碼值相差32，用二進(jìn)制表示為8′b00100000，則設(shè)置匹配規(guī)則為Char⊕8′b01×00010。

但是對于上述規(guī)則中出現(xiàn)的“0- 8”，與數(shù)字匹配“d”相比缺少字符“9”，若使用精確匹配則需要9個(gè)轉(zhuǎn)移狀態(tài)。為解決類似于 “[0- 8]”的狀態(tài)轉(zhuǎn)移問題，采用優(yōu)先級的方法，如表2所示，取類匹配“d”代替“[0- 8]”，同時(shí)添加精確匹配字符“9”使其匹配優(yōu)先級高于“d”的優(yōu)先級，以避免重新定義字符類，降低自動機(jī)構(gòu)造的計(jì)算復(fù)雜度，減少遷移邊數(shù)目。若規(guī)則中出現(xiàn)“[0- 7]”匹配時(shí)，使用上述優(yōu)先級的匹配方法則需要三條遷移邊；但是根據(jù)“0- 7”ASCII碼的特點(diǎn)，可以直接將“[0- 7]”定義為一個(gè)類，則匹配僅需要一條遷移邊。

圖2 “a[bB][^c][0- 8]*9[a-z]”DFA狀態(tài)圖

表2 “a[bB][^c][0- 8]*9[a-z]”狀態(tài)轉(zhuǎn)移表

Tab.2Statetransitiontableof“a[bB][^c][0- 8]*9[a-z]”

RuleCurrentstateInputNextstatePriorityR0??S00R1?aS10R2S1[bB]S20R3S2?S40R4S2aS30R5S2cS00R6S3dS40R7S39S51R8S3[bB]S20R9S4dS40R10S49S50R11S5[a?z]S60

下面給出了基于預(yù)定義類遷移邊壓縮方法偽代碼，S為XFA狀態(tài)集，δ為轉(zhuǎn)移函數(shù)，Tc為遷移邊集合，其中初始的Tc為XFA的遷移邊集合，最終輸出的是壓縮后的遷移邊集合。算法通過遍歷每一個(gè)狀態(tài)來判斷該狀態(tài)的遷移邊中是否存在可以壓縮的遷移邊，若存在，則判斷可壓縮遷移邊的類型，對于未定義的壓縮類型，稱之為新類型。由于過多的類匹配類型將增加規(guī)則類型標(biāo)識符的位寬，從而增加消耗的存儲器資源，因此最終需要對定義的類類型進(jìn)行篩選，選擇最優(yōu)的類定義。

Pre-ClassCFA(S,δ,Σ)Tran_SetTc=?;num=0;array[128];For(eachstateSiinS)doFor(eachstateSiinS)doFor(charfrom 8′h00 to 8′h7f) If(Tran tk=Sj→δ(Si,char)) array[char]=1;

num++;

Endfor

If(num=2)If(array中兩個(gè)存儲為1的空間地址相差32)type=不區(qū)分大小；

If(num=10)type=數(shù)字匹配；

Tc=Tc∪t數(shù)字;

Tc=Tc∩t0～9;

?

If(num=9)If(array中地址為8′h30-8′h38為1)Tc=Tc∪t0-8; Tc=Tc∩t0～9; Tc=Tc∪t9; t9.priority=1;

Endfor

array[]=0;

Endfor

2.2 基于并聯(lián)存儲塊的遷移邊存儲與查找

為提高算法的資源利用率，在構(gòu)造Pre-ClassCFA時(shí)使用多條規(guī)則構(gòu)成一個(gè)自動機(jī)，則在進(jìn)行匹配時(shí)需要查找對應(yīng)狀態(tài)的所有遷移邊。狀態(tài)轉(zhuǎn)移邊的查找方法可以分為兩類：

1)使用狀態(tài)值和輸入值通過哈希函數(shù)產(chǎn)生指針進(jìn)行查找；

2)使用內(nèi)容地址存儲器(ContentAddressableMemory,CAM)進(jìn)行查找。

指針方法查找速度快，但是哈希碰撞問題會嚴(yán)重影響查找精度，尤其當(dāng)規(guī)則數(shù)目比較大時(shí)，哈希碰撞問題更加突出。內(nèi)容地址存儲器可以對CAM中的數(shù)據(jù)進(jìn)行快速并行查找，但是CAM作為外部存儲器，與片內(nèi)存儲器相比執(zhí)行頻率和延遲都存在一定的差距。本文利用文獻(xiàn)[12]提出的可變內(nèi)容尋址存儲器(modifiedContentAddressableMemory,mCAM)的設(shè)計(jì)思想，構(gòu)造設(shè)計(jì)了適合Pre-ClassCFA算法的遷移邊查找方案——并聯(lián)存儲塊(InterleavedMemoryBanks,IMB)遷移邊查找方法。

2.2.1 遷移邊分類與規(guī)則定義

對狀態(tài)機(jī)的存儲首先要對遷移邊進(jìn)行處理，根據(jù)遷移邊的特點(diǎn)，將遷移邊分為兩類，如圖3所示。一類是精確轉(zhuǎn)移(Exacttransition)，其存儲內(nèi)容包括規(guī)則類型(Type)、下一狀態(tài)(Nextstate)和輸入字符(Inputchar)。規(guī)則類型指遷移邊的類型，根據(jù)遷移邊定義類型的多少對其進(jìn)行編碼。另一類是缺省轉(zhuǎn)移(Defaulttransition)，即狀態(tài)機(jī)中的失敗轉(zhuǎn)移，缺省轉(zhuǎn)移規(guī)則包含當(dāng)前狀態(tài)的遷移邊數(shù)目(Transitionnumber)、失敗遷移狀態(tài)(Nextstate)和匹配規(guī)則號(MatchID)。Tra.num存儲該狀態(tài)中精確轉(zhuǎn)移的數(shù)目，標(biāo)識匹配起始位置到結(jié)束位置的偏移量，MatchID表示該狀態(tài)匹配的規(guī)則號。

2.2.2 基于IMB的遷移邊查找方法

為實(shí)現(xiàn)規(guī)則的高速匹配，需要在一個(gè)時(shí)鐘內(nèi)對某狀態(tài)的所有遷移邊進(jìn)行分析。當(dāng)前的現(xiàn)場可編程門陣列(Field-ProgrammableGateArray,FPGA)產(chǎn)品內(nèi)部嵌有數(shù)百個(gè)片內(nèi)存儲塊，使用這些存儲塊可以構(gòu)造一個(gè)并聯(lián)存儲塊，不僅能提高查找效率，也能夠充分利用FPGA的存儲帶寬。

如果存儲塊數(shù)目n大于或者等于自動機(jī)中所有狀態(tài)的最大遷移邊數(shù)目Nmax，則所有的遷移邊可以在一個(gè)時(shí)鐘內(nèi)實(shí)現(xiàn)并行處理；若n

圖4 “a[bB][^c][0- 8]*9[a-z]”遷移邊存儲結(jié)構(gòu)

圖5給出了由存儲器構(gòu)成的匹配引擎結(jié)構(gòu)。引擎包括地址產(chǎn)生器、IMB、字符匹配器和狀態(tài)選擇器。遷移邊按照定義的規(guī)則存儲在IMB中，每個(gè)存儲塊都包含一個(gè)地址產(chǎn)生器，地址產(chǎn)生器根據(jù)當(dāng)前狀態(tài)值產(chǎn)生對應(yīng)塊匹配起始地址，讀取存儲的規(guī)則后，字符匹配器將與精確匹配中的字符進(jìn)行匹配，當(dāng)遇到類匹配時(shí)，根據(jù)類匹配的類型，選擇合適的匹配算法。匹配結(jié)束后的結(jié)果輸入到狀態(tài)選擇器中，狀態(tài)選擇器根據(jù)遷移邊的優(yōu)先級決定下一狀態(tài)值。

圖5 匹配引擎結(jié)構(gòu)

下面給出的是基于硬件設(shè)計(jì)的Pre-ClassCFA算法頂層模塊Verilog偽代碼。第1)行給出了頂層模塊端口信號，其中包括三個(gè)輸入信號：clk、rst、char和一個(gè)輸出信號：match_ID，clk和rst作為全局的時(shí)鐘和復(fù)位信號驅(qū)動整個(gè)模塊的運(yùn)作，char是輸入的檢測字符，match_ID為匹配得到的特征碼ID。第2)～5)行為頂層模塊調(diào)用的子模塊，Mult模塊是一個(gè)數(shù)據(jù)選擇器，在每個(gè)時(shí)鐘確定該時(shí)鐘的狀態(tài)指針，若復(fù)位則輸出初始狀態(tài)指針，否則輸出Comparator輸出的指針；Read模塊的作用是通過Mult模塊輸出的狀態(tài)指針讀取IMB中的遷移邊；Sort模塊的作用是將Read模塊讀取的遷移邊根據(jù)狀態(tài)指針信號將遷移邊進(jìn)行分類及優(yōu)先級排序；Comparator模塊是將遷移邊與輸入字符進(jìn)行匹配，匹配時(shí)根據(jù)遷移邊中規(guī)則類型標(biāo)識符，選擇對應(yīng)的匹配電路進(jìn)行匹配，這其中包括定義的類匹配。

1)

modulePre-ClassCFA(clk,rst,char,match_ID)

2)

Mult(clk,rst,index,index_next,addr,bank);

3)

Read(clk,rst,index,addr,bank,char,char1,data0,data1,data2,data3);

4)

Sort(clk,rst,bank,data0,data1,data2,data3,index,char1,char2,exact_data0,exact_data1,exact_data2,bank_num,d_next_state,ID);

5)

Comparator(clk,rst,bank_num,char,ID,exact_data0,exact_data1,exact_data2,d_next_state,next_state,match_ID);

6)

endmodule

2.3 輔助變量存儲器設(shè)計(jì)

輔助變量存儲器給每一個(gè)擁有克林閉合組的規(guī)則設(shè)置一個(gè)地址，存儲空間大小等于所有規(guī)則中克林閉合組的最大值Kmax。在進(jìn)行ID設(shè)置時(shí)，確定一個(gè)規(guī)則閾值Thr，將存在克林閉合組規(guī)則的ID值設(shè)置在閾值以下，使用ID值中大于閾值的高位存儲比較指令值；同時(shí)將MatchID的最高位設(shè)置為標(biāo)志位，用來區(qū)別規(guī)則中是否存在克林閉合組，當(dāng)最高位為“1”時(shí)表示存在，反之不存在。例如設(shè)規(guī)則數(shù)為100，存在克林閉合組的規(guī)則數(shù)為15，其中Kmax=4，則取MatchID為8bit，閾值Thr=16，設(shè)置輔助變量儲存器地址空間為4bit。若規(guī)則中僅含有一個(gè)，則在存儲器中存儲“1110”，存在兩個(gè)則存儲“1101”，存在三個(gè)則存儲“1100”，以此類推。當(dāng)輸入規(guī)則ID時(shí)，若計(jì)數(shù)器值為0，則計(jì)數(shù)器讀取規(guī)則對應(yīng)存儲器中的數(shù)值并加1，同時(shí)寄存ID；反之，則檢測輸入的ID與寄存器輸出的ID是否相同，相同則計(jì)數(shù)器直接加1，不同則計(jì)數(shù)器讀取新規(guī)則數(shù)據(jù)并加1。每次輸入都要更新寄存器中的ID值。計(jì)數(shù)器每計(jì)數(shù)結(jié)束需判斷計(jì)數(shù)值是否為“1111”，若是，則匹配成功，計(jì)數(shù)器置零，寄存器復(fù)位。

3 算法性能分析與實(shí)驗(yàn)評估

3.1 算法性能分析

通過分析Pre-ClassCFA與XFA的定義PC={Q,V,Σ′,δ′,U,(q0,v0),F}和X={Q,V,Σ,δ,U,(q0,v0),F}，當(dāng)初始狀態(tài)相同時(shí)，輸入相同的字符二者具有相同的目的狀態(tài)，可證明Pre-ClassCFA與XFA等價(jià)。

由于正則表達(dá)式的復(fù)雜性和多樣性，以下通過分析最壞情況遷移邊數(shù)目來比較Pre-ClassCFA與XFA的性能。設(shè)自動機(jī)中狀態(tài)總數(shù)為Ns，字母表Σ中有m個(gè)字母，則XFA遷移邊總數(shù)Xt=Ns×(m+1),Pre-ClassCFA遷移邊總數(shù)PCt=(Ns+c)-(c×Ratio),其中：c表示各個(gè)狀態(tài)非失敗轉(zhuǎn)移的遷移邊數(shù)目之和，Ratio表示各類類匹配在正則表達(dá)式遷移邊中所占的比例。二者相比，遷移邊減少數(shù)目為：

在自動機(jī)中，非失敗轉(zhuǎn)移的遷移邊數(shù)目之和c為：

c=Ns*N；N≥1,N∈Z+

則

RX/PC=(m+1)/[1+(1-Ratio)×N]

通過對Snort2.9.8.0中的正則表達(dá)式規(guī)則進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)其中33%的規(guī)則進(jìn)行匹配時(shí)不區(qū)分大小寫，包含字母、數(shù)字以及否定形式等其他類匹配的正則表達(dá)式規(guī)則占規(guī)則總數(shù)約42%，根據(jù)文獻(xiàn)[14]統(tǒng)計(jì)分析，Snort規(guī)則的平均長度為207，則Ratio≈6.8%。在理想情況下，當(dāng)m=256，N=3時(shí)，與XFA相比，Pre-ClassCFA在遷移邊數(shù)目上減少了67.6%。

3.2 實(shí)驗(yàn)評估

實(shí)驗(yàn)使用ALTERA低成本CycloneⅡ系列的開發(fā)平臺，平臺搭載EP2C70F896C6FPGA芯片，選擇Snort規(guī)則庫規(guī)則集進(jìn)行仿真實(shí)驗(yàn)分析，將規(guī)則文件編譯為Pre-ClassCFA，并將其遷移邊存儲在IMB中。根據(jù)文獻(xiàn)[14]給出的實(shí)驗(yàn)結(jié)果，并聯(lián)只讀存儲器(Read-OnlyMemory,ROM)進(jìn)行并行流水線操作時(shí)，由于多路選擇器在數(shù)據(jù)讀取時(shí)存在延遲，因而并非并聯(lián)塊數(shù)越多數(shù)據(jù)的處理效率越高。在使用流水線的方式設(shè)計(jì)Pre-ClassCFA時(shí)，使用的資源全部是寄存器和查找表等非邏輯資源。表3給出了使用不同數(shù)量并聯(lián)ROM進(jìn)行流水線操作時(shí)Pre-ClassCFA使用的LTU(LookUpTable)、REG(REGister)數(shù)目以及自動機(jī)的最大工作頻率。從表中可以看出，自動機(jī)消耗的FPGA資源很小，消耗量小于器件資源總量的1%；對比表中流水線結(jié)構(gòu)和非流水線結(jié)構(gòu)自動機(jī)的最大頻率可以看出，通過在系統(tǒng)中增加流水線級數(shù)可以提高系統(tǒng)頻率，且采用2級流水線的4-ROM結(jié)構(gòu)自動機(jī)的工作頻率達(dá)到最大值，由于受實(shí)驗(yàn)器件性能的約束，系統(tǒng)有最大工作頻率為162.06MHz，系統(tǒng)最大吞吐量可達(dá)到1.3Gb/s。

表3 不同數(shù)目并聯(lián)ROM的實(shí)驗(yàn)相關(guān)參數(shù)

本文從Snort規(guī)則庫中選擇FTP、exploit、SMTP、Web-client和Web-misc五個(gè)規(guī)則集對算法進(jìn)行分析評估，如表4所示給出了使用XFA、CFA和本文算法編碼上述規(guī)則集所需的遷移邊數(shù)目。

表4 Snort規(guī)則集參數(shù)統(tǒng)計(jì)

從表4中可以看出,本文算法與XFA算法相比遷移邊數(shù)目減少了70.21%～90.37%，與CFA算法相比遷移邊數(shù)目減少了15.41%～33.05%，其中正則表達(dá)式中類匹配出現(xiàn)頻率越高，遷移邊壓縮效果越明顯。同時(shí)本文提出的基于IMB的遷移邊查找方法針對FPGA存儲器結(jié)構(gòu)設(shè)計(jì)，充分利用了器件的片內(nèi)存儲器資源，與CFA算法片內(nèi)片外分步查找方法相比，查詢性能有較大的提升，性能提升程度與器件性能相關(guān)，在本文使用的FPGA器件中，若使用同步靜態(tài)隨機(jī)存取存儲器(SynchronousStaticRandomAccessMemory,SSRAM)作為片外存儲器，則查詢性能提高了56.62%。

4 結(jié)語

本文提出了一種基于XFA的改進(jìn)正則表達(dá)式匹配算法——Pre-ClassCFA算法。算法通過預(yù)定義類，減少了正則表達(dá)式中字符類匹配時(shí)遷移邊條數(shù)。在Pre-ClassCFA數(shù)據(jù)存儲中，本文基于并聯(lián)ROM結(jié)構(gòu)設(shè)計(jì)了適合該算法遷移邊特征的IMB遷移邊存儲結(jié)構(gòu)，通過對遷移邊進(jìn)行編碼，將數(shù)據(jù)全部存儲在片內(nèi)存儲器中，大大提高了數(shù)據(jù)讀取速度，從而確保了算法的匹配效率。實(shí)驗(yàn)結(jié)果表明，Pre-ClassCFA在大大壓縮遷移邊的同時(shí)可以在頻率上限為260MHz的中低性能FPGA系統(tǒng)中實(shí)現(xiàn)大規(guī)模正則表達(dá)式的高速匹配，系統(tǒng)吞吐量可達(dá)到1.3Gb/s，可滿足千兆網(wǎng)絡(luò)下的數(shù)據(jù)檢測。

雖然本文算法在遷移邊壓縮和匹配效率上取得了較好的效果，但是該算法通過軟件編程實(shí)現(xiàn)的規(guī)則預(yù)處理過程步驟多、處理過程復(fù)雜，尤其是對于極少數(shù)特殊的類匹配，由于目前規(guī)則處理程序不夠完善，仍需要進(jìn)行人工處理，從而給系統(tǒng)規(guī)則的更新造成影響。作者下一步的研究方向是對規(guī)則預(yù)處理程序進(jìn)行完善，提高算法的整體性能。

)

[1] 褚衍杰，李云照，魏強(qiáng).一種改進(jìn)的多模式匹配算法[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 41(6): 174-179.(CHUYJ,LIYZ,WEIQ.Improvedmulti-patternmatchingalgorithm[J].JournalofXidianUniversity(NaturalScience), 2014, 41(6): 174-179.)

[2] 嵩天,李冬妮,汪東升,等.存儲有效的多模式匹配算法和體系結(jié)構(gòu)[J].軟件學(xué)報(bào),2013,24(7):1650-1665.(SONGT,LIDN,WANGDS,etal.Memoryefficientalgorithmandarchitectureformulti-patternmatching[J].JournalofSoftware, 2013, 24(7): 1650-1665.

[3]NAVARROG,RAFFINOTM.FlexiblePatternMatchinginStrings:PracticalOn-LineSearchAlgorithmsforTextsandBiologicalSequences[M].NewYork:CambridgeUniversityPress, 2002: 41-75.

[4]Snort[EB/OL].[2016- 07- 12].http://www.snort.org/.

[5]ClamAntiVirus[EB/OL].[2016- 07- 12].http://www.clamav.net/.

[6]SMITHR,ESTANC,JHAS.XFA:fastersignaturematchingwithextendedautomata[C]//SP’08:Proceedingsofthe2008IEEESymposiumonSecurityandPrivacy.Washington,DC:IEEEComputerSociety, 2008: 187-201.

[7] 黃昆,張大方,謝高崗,等.一種面向深度數(shù)據(jù)包檢測的緊湊型正則表達(dá)式匹配算法[J].中國科學(xué):信息科學(xué),2010,40(2):356-370.(HUANGK,ZHANGDF,XIEGG,etal.Deeppacketinspectionorientedcompactregularexpressionmatchingalgorithm[J].ScienceChinaInformationSciences, 2010, 40(2): 356-370.)

[8] 張大方,張潔坤,黃昆.一種基于智能有限自動機(jī)的正則表達(dá)式匹配算法[J].電子學(xué)報(bào),2012,40(8):1617-1623.(ZHANGDF,ZHANGJK,HUANGK.Aregularexpressionmatchingalgorithmwithsmartfiniteautomaton[J].ActaElectronicaSinica, 2012, 40(8): 1617-1623.)[9] VAN LUNTEREN J, HAGLEITNER C, HEIL T, et al.Designing a programmable wire-speed regular-expression matching accelerator [C]// MICRO-45: Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture.Washington, DC: IEEE Computer Society, 2012: 461-472.

[10] SMITH R, ESTAN C, JHA S, et al.Deflating the big bang: fast and scalable deep packet inspection with extended finite automata [C]// SIGCOMM ’08: Proceedings of the 2008 ACM SIGCOMM Computer Communication.New York: ACM, 2008: 207-218.

[11] VAN LUNTEREN J.High-performance pattern-matching for intrusion detection [C]// Proceedings of the IEEE INFOCOM 2006.Washington, DC: IEEE Computer Society, 2006: 1-13.

[12] HAYES C L, LUO Y.DPICO: a high speed deep packet inspection engine using compact finite automata [C]// ANCS ’07: Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems.New York: ACM, 2007: 195-203.

[13] Xilinx, Inc.Virtex 4 family overview [EB/OL].(2010- 08- 30) [2016- 02- 24].http://www.xilinx.com/support/documentation/data_sheets/ds112.pdf.

[14] VASILIADIS G, POLYCHRONAKIS M, IOANNIDIS S.MIDeA: a multi-parallel intrusion detection architecture [C]// CCS’11: Proceedings of the 18th ACM Conference on Computer and Communications Security.New York: ACM, 2011: 297-308.

This work is partially supported by the National Natural Science Foundation of China (61402531), the Natural Science Foundation of Shaanxi Province (2014JQ8307, 2015JQ6231).

MAI Taotao, born in 1992, M.S.candidate.His research interests include network safety, embedded system.

PAN Xiaozhong, born in 1964, M.S., professor.His research interests include network safety, embedded system.

WANG Yaqi, born in 1982, Ph.D., lecturer.His research interests include security of cyberspace.

SU Yang, born in1986, M.S., assistant.His research interests include embedded system.

Predefined-class based algorithm for compact regular expression matching

MAI Taotao1,2*, PAN Xiaozhong1,2, WANG Yaqi1,2, SU Yang1,2

(1.DepartmentofElectronicTechnology,EngineeringCollegeoftheChineseArmedPoliceForce,Xi’anShaanxi710086,China;2.KeyLaboratoryofNetworkandInformationSecurityoftheChineseArmedPoliceForce,Xi’anShaanxi710086,China)

For hardware regular expression matching algorithms are faced with the challenges in memory space and throughput, a Predefined-class Compact Finite Automaton (Pre-class CFA) matching algorithm based on Extended Finite Automaton (XFA) regular expression matching algorithm was proposed.By using the predefined classes, the algorithm not only can achieve class character matching in regular expression, but also can match the special character set by priority setting; besides, the migrating edges were reduced when eliminating the Deterministic Finite Automaton (DFA) state space exploration problem.At the same time, based on the characteristics of Field-Programmable Gate Array (FPGA) and migration edge, a migration edge access method based on parallel Read-Only Memory (ROM) was designed to realize the parallel reading and matching of the same state with mutiple migration edges.The algorithm was tested on ALTERA DE2- 70 FPGA platform, which is a low-performance platform.The throughput of the experimental system is 1.30 Gb/s, which can realize intrusion detection and garbage filtering under gigabit network.

regular expression matching; Extended Finite Automaton (XFA); Field-Programmable Gate Array (FPGA)

2016- 08- 15;

2016- 09- 12。

國家自然科學(xué)基金資助項(xiàng)目(61402531);陜西省自然科學(xué)基金資助項(xiàng)目(2014JQ8307,2015JQ6231)。

麥濤濤(1992—),男,河南洛陽人,碩士研究生,主要研究方向:網(wǎng)絡(luò)安全、嵌入式系統(tǒng); 潘曉中(1964—),男,陜西西安人,教授,碩士,主要研究方向:網(wǎng)絡(luò)安全、嵌入式系統(tǒng); 王亞奇(1982—),男,河南周口人,講師,博士,主要研究方向:網(wǎng)絡(luò)空間安全; 蘇陽(1986—),男,寧夏銀川人,助教,碩士,主要研究方向:嵌入式系統(tǒng)。

1001- 9081(2017)02- 0397- 05

10.11772/j.issn.1001- 9081.2017.02.0397

TP393

A