麥濤濤,潘曉中,王亞奇,蘇 陽
(1.武警工程大學 電子技術(shù)系,西安 710086; 2.武警部隊網(wǎng)絡與信息安全保密重點實驗室,西安 710086)
(*通信作者電子郵箱wj_maitao@126.com)
基于預定義類的緊湊型正則表達式匹配算法
麥濤濤1,2*,潘曉中1,2,王亞奇1,2,蘇 陽1,2
(1.武警工程大學 電子技術(shù)系,西安 710086; 2.武警部隊網(wǎng)絡與信息安全保密重點實驗室,西安 710086)
(*通信作者電子郵箱wj_maitao@126.com)
針對目前硬件正則表達式匹配算法在存儲空間以及吞吐量等方面面臨的挑戰(zhàn),結(jié)合擴展有限自動機(XFA)正則表達式匹配算法,提出了一種預定義類的壓縮自動機匹配算法(Pre-Class CFA)。通過預定義類,算法既可以實現(xiàn)正則表達式中類字符匹配,又能夠通過優(yōu)先級的設(shè)定匹配特殊字符集,并在XFA消除確定性有限狀態(tài)機(DFA)狀態(tài)爆炸問題的基礎(chǔ)上進一步壓縮了遷移邊數(shù)目;同時算法根據(jù)現(xiàn)場可編程門陣列(FPGA)和遷移邊的特征,設(shè)計了一種基于并聯(lián)只讀存儲器(ROM)結(jié)構(gòu)的遷移邊存取方法,可以實現(xiàn)同一狀態(tài)多條遷移邊的并行讀取和匹配。在中低性能FPGA平臺ALTERA DE2- 70上對算法進行測試,實驗中系統(tǒng)吞吐量為1.3 Gb/s,可實現(xiàn)千兆網(wǎng)絡下的入侵檢測和垃圾過濾。
正則表達式匹配;擴展有限自動機;現(xiàn)場可編程門陣列
隨著海量信息處理和大數(shù)據(jù)處理等技術(shù)的發(fā)展,網(wǎng)絡應用對海量信息下匹配引擎的性能提出了更高的要求[1]。深度包過濾(Deep Packet Inspection, DPI)技術(shù)作為網(wǎng)絡過濾系統(tǒng)的核心,采用特征匹配算法將數(shù)據(jù)包中的數(shù)據(jù)與預定義的惡意數(shù)據(jù)特征碼進行匹配,從而濾除惡意數(shù)據(jù)包。由木桶原理可知,網(wǎng)絡安全應用中,模式匹配在最差情況下的性能決定了系統(tǒng)在線工作性能。為此,提高模式匹配在最差情況下的性能是入侵檢測系統(tǒng)的關(guān)鍵問題[2]。
模式匹配廣泛應用于信息檢索、模式識別、入侵檢測、內(nèi)容過濾、病毒代碼檢測、基因匹配等眾多領(lǐng)域[3]。模式匹配根據(jù)模式串的描述方式可分為字符串匹配和正則表達式匹配。隨著網(wǎng)絡的不斷發(fā)展,惡意數(shù)據(jù)特征碼長度、數(shù)目和種類增長迅速,正則表達式描述方式以其較強的表達能力逐步應用成為主流網(wǎng)絡安全系統(tǒng),例如Snort[4]、Clam AV[5]等數(shù)據(jù)庫的主要描述形式。表1給出了不同版本的Snort規(guī)則數(shù)目以及Pcre規(guī)則所占比例[4]。正則表達式匹配算法是本文研究的主要內(nèi)容。
表1 Snort規(guī)則集統(tǒng)計分析結(jié)果
正則表達式匹配通常采用確定性有限狀態(tài)機(Deterministic Finite Automaton, DFA)。DFA處理每個字符僅需要訪問一個狀態(tài),避免了回溯問題,匹配速度快,但是DFA編譯速度慢、空間消耗大等問題,限制了其在基于硬件的正則表達式匹配系統(tǒng)中的發(fā)展和應用。
針對DFA存儲空間需求大的問題,近幾年,研究者提出了多種DFA的改進算法。Smith等[6]提出一種采用輔助變量代替額外狀態(tài)的DFA改進算法——擴展有限自動機(Extended Finite Automaton, XFA)匹配算法,其通過簡單的指令操作來檢測是否匹配成功,能消除DFA狀態(tài)空間爆炸問題,與DFA相比,XFA的狀態(tài)空間數(shù)減少了4個數(shù)量級,匹配時間與DFA接近。黃昆等[7]在XFA算法的基礎(chǔ)上利用優(yōu)先級壓縮和位圖存儲的方法提出了壓縮有限自動機(Compact Finite Automaton, CFA)算法,在遷移邊壓縮方面取得了不錯的效果;但是算法規(guī)則匹配使用二次查找,當網(wǎng)絡中出現(xiàn)分布式拒絕服務(Distributed Denial of Service, DDoS)攻擊時容易出現(xiàn)丟包、漏包的情況。張大方等[8]提出的智能有限自動機(Smart Finite Automaton, SFA)算法有效解決了XFA算法冗余遷移邊的問題,通過增加輔助判斷指令避免了狀態(tài)機重復匹配的情況。IBM蘇黎世實驗室提出了一種基于緊湊型DFA和XFA的正則表達式匹配引擎,該引擎適用于少量規(guī)則的匹配操作,當規(guī)則數(shù)為600時,吞吐率可達到45 Gb/s,隨著規(guī)則數(shù)目的增多,引擎的吞吐率呈指數(shù)下降[9]。以上基于XFA的改進算法對包含克林閉合組“.*”“[]”以及“{}”等元字符的正則表達式優(yōu)化效果明顯,但是針對d / [0- 9](匹配數(shù)字)、[a-z](匹配小寫字母)、[bB](不區(qū)分大小寫)等類字符匹配,XFA并不能對遷移邊進行有效壓縮。本文結(jié)合XFA提出了一種基于預定義類的緊湊型自動機(Pre-Class CFA)匹配算法。
DFA狀態(tài)爆炸的根本原因是當多個DFA組合成一個DFA時,單個DFA的歧義路徑和非歧義路徑相互組合,導致組合DFA產(chǎn)生大量的額外狀態(tài),使消耗的空間量呈指數(shù)級增長[8]。DFA的定義如下:D={Q,Σ,δ,q0,F}。其中:Q為狀態(tài)集,Σ為字母表,δ為遷移函數(shù),q0為初始狀態(tài),F(xiàn)為接受狀態(tài)集。例如正則表達式集{.*ab.*cd, .*ef.*gh},其聯(lián)合DFA結(jié)構(gòu)圖如圖1(a)所示,圖中省略了其他狀態(tài)到初始狀態(tài)的失敗轉(zhuǎn)移。從圖1可以看出,由于單個DFA中存在通配符“.*”,使得當兩個DFA的狀態(tài)進行交叉組合時,狀態(tài)機中狀態(tài)數(shù)目呈指數(shù)級增長,造成組合DFA空間爆炸[10]。
為消除組合DFA狀態(tài)空間爆炸的問題,Smith等[6]提出了XFA解決方案,使用輔助變量代替額外狀態(tài)來記錄部分匹配的結(jié)果。XFA匹配時,當讀入一個字符,XFA檢查當前狀態(tài)對應遷移邊遷移的下一狀態(tài),在執(zhí)行下一狀態(tài)指令時檢測輔助變量,從而判斷是否匹配成功[8]。XFA定義如下:X={Q,V,Σ,δ,U,(q0,v0),F}。其中:V表示輔助變量集,U表示每個狀態(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的判斷指令,在整個組合XFA中共需要7個狀態(tài)和2個輔助變量,相比DFA中的15個狀態(tài)減小了50%。輔助變量的引入使XFA解決了DFA狀態(tài)空間爆炸問題。
圖1 {.*ab.*cd, .*ef.*gh}狀態(tài)圖
從圖1(b)可以看到緊湊型自動機可以有效地解決由克林閉合組“.*”所帶來的狀態(tài)爆炸問題,同時利用輔助變量也可以避免由“[]”“{}”等多次重復匹配元字符所帶來的狀態(tài)爆炸,但是對于規(guī)則集中常見的不區(qū)分大小寫、特殊字符類匹配等元字符匹配所造成的空間復雜度的增加,XFA算法未給出有效的解決方案。本文結(jié)合XFA使用的指令方法,提出了可以匹配字符類的Pre-ClassCFA正則表達式匹配算法。
2.1 基于預定義類的遷移邊壓縮方法
Pre-ClassCFA支持多種形式的狀態(tài)遷移,不僅包括XFA中的精確匹配,還支持不區(qū)分大小寫、類匹配和缺省轉(zhuǎn)移等特殊遷移。
類匹配[11]可以實現(xiàn)字符類,例如數(shù)字([0- 9]或d)、字母([a-z]以及[A-Z])、字類字符([A-Za-z0- 9]或w)以及對應的否定形式等全部或者部分字符的匹配。通過定義類可以實現(xiàn)多條相同初始狀態(tài)和目的狀態(tài)遷移邊的歸一化,減少遷移邊的數(shù)目,降低算法的空間和時間復雜度。在算法設(shè)計中將不區(qū)分大小寫也歸到類匹配進行處理。
例如規(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)自動機匹配則以上三個狀態(tài)轉(zhuǎn)移需要消耗37個存儲空間。通過分析ASCII碼的特點,不區(qū)分大小寫、數(shù)字、字母等類字符可以通過特殊的匹配規(guī)則使用一條轉(zhuǎn)移規(guī)則進行處理。例如不區(qū)分大小寫[bB],由于在ASCII碼中大小寫字母ASCII碼值相差32,用二進制表示為8′b00100000,則設(shè)置匹配規(guī)則為Char⊕8′b01×00010。
但是對于上述規(guī)則中出現(xiàn)的“0- 8”,與數(shù)字匹配“d”相比缺少字符“9”,若使用精確匹配則需要9個轉(zhuǎn)移狀態(tài)。為解決類似于 “[0- 8]”的狀態(tài)轉(zhuǎn)移問題,采用優(yōu)先級的方法,如表2所示,取類匹配“d”代替“[0- 8]”,同時添加精確匹配字符“9”使其匹配優(yōu)先級高于“d”的優(yōu)先級,以避免重新定義字符類,降低自動機構(gòu)造的計算復雜度,減少遷移邊數(shù)目。若規(guī)則中出現(xiàn)“[0- 7]”匹配時,使用上述優(yōu)先級的匹配方法則需要三條遷移邊;但是根據(jù)“0- 7”ASCII碼的特點,可以直接將“[0- 7]”定義為一個類,則匹配僅需要一條遷移邊。
圖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
下面給出了基于預定義類遷移邊壓縮方法偽代碼,S為XFA狀態(tài)集,δ為轉(zhuǎn)移函數(shù),Tc為遷移邊集合,其中初始的Tc為XFA的遷移邊集合,最終輸出的是壓縮后的遷移邊集合。算法通過遍歷每一個狀態(tài)來判斷該狀態(tài)的遷移邊中是否存在可以壓縮的遷移邊,若存在,則判斷可壓縮遷移邊的類型,對于未定義的壓縮類型,稱之為新類型。由于過多的類匹配類型將增加規(guī)則類型標識符的位寬,從而增加消耗的存儲器資源,因此最終需要對定義的類類型進行篩選,選擇最優(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中兩個存儲為1的空間地址相差32)type=不區(qū)分大?。?/p>
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時使用多條規(guī)則構(gòu)成一個自動機,則在進行匹配時需要查找對應狀態(tài)的所有遷移邊。狀態(tài)轉(zhuǎn)移邊的查找方法可以分為兩類:
1)使用狀態(tài)值和輸入值通過哈希函數(shù)產(chǎn)生指針進行查找;
2)使用內(nèi)容地址存儲器(ContentAddressableMemory,CAM)進行查找。
指針方法查找速度快,但是哈希碰撞問題會嚴重影響查找精度,尤其當規(guī)則數(shù)目比較大時,哈希碰撞問題更加突出。內(nèi)容地址存儲器可以對CAM中的數(shù)據(jù)進行快速并行查找,但是CAM作為外部存儲器,與片內(nèi)存儲器相比執(zhí)行頻率和延遲都存在一定的差距。本文利用文獻[12]提出的可變內(nèi)容尋址存儲器(modifiedContentAddressableMemory,mCAM)的設(shè)計思想,構(gòu)造設(shè)計了適合Pre-ClassCFA算法的遷移邊查找方案——并聯(lián)存儲塊(InterleavedMemoryBanks,IMB)遷移邊查找方法。
2.2.1 遷移邊分類與規(guī)則定義
對狀態(tài)機的存儲首先要對遷移邊進行處理,根據(jù)遷移邊的特點,將遷移邊分為兩類,如圖3所示。一類是精確轉(zhuǎn)移(Exacttransition),其存儲內(nèi)容包括規(guī)則類型(Type)、下一狀態(tài)(Nextstate)和輸入字符(Inputchar)。規(guī)則類型指遷移邊的類型,根據(jù)遷移邊定義類型的多少對其進行編碼。另一類是缺省轉(zhuǎn)移(Defaulttransition),即狀態(tài)機中的失敗轉(zhuǎn)移,缺省轉(zhuǎn)移規(guī)則包含當前狀態(tài)的遷移邊數(shù)目(Transitionnumber)、失敗遷移狀態(tài)(Nextstate)和匹配規(guī)則號(MatchID)。Tra.num存儲該狀態(tài)中精確轉(zhuǎn)移的數(shù)目,標識匹配起始位置到結(jié)束位置的偏移量,MatchID表示該狀態(tài)匹配的規(guī)則號。
2.2.2 基于IMB的遷移邊查找方法
為實現(xiàn)規(guī)則的高速匹配,需要在一個時鐘內(nèi)對某狀態(tài)的所有遷移邊進行分析。當前的現(xiàn)場可編程門陣列(Field-ProgrammableGateArray,FPGA)產(chǎn)品內(nèi)部嵌有數(shù)百個片內(nèi)存儲塊,使用這些存儲塊可以構(gòu)造一個并聯(lián)存儲塊,不僅能提高查找效率,也能夠充分利用FPGA的存儲帶寬。
如果存儲塊數(shù)目n大于或者等于自動機中所有狀態(tài)的最大遷移邊數(shù)目Nmax,則所有的遷移邊可以在一個時鐘內(nèi)實現(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中,每個存儲塊都包含一個地址產(chǎn)生器,地址產(chǎn)生器根據(jù)當前狀態(tài)值產(chǎn)生對應塊匹配起始地址,讀取存儲的規(guī)則后,字符匹配器將與精確匹配中的字符進行匹配,當遇到類匹配時,根據(jù)類匹配的類型,選擇合適的匹配算法。匹配結(jié)束后的結(jié)果輸入到狀態(tài)選擇器中,狀態(tài)選擇器根據(jù)遷移邊的優(yōu)先級決定下一狀態(tài)值。 圖5 匹配引擎結(jié)構(gòu) 下面給出的是基于硬件設(shè)計的Pre-ClassCFA算法頂層模塊Verilog偽代碼。第1)行給出了頂層模塊端口信號,其中包括三個輸入信號:clk、rst、char和一個輸出信號:match_ID,clk和rst作為全局的時鐘和復位信號驅(qū)動整個模塊的運作,char是輸入的檢測字符,match_ID為匹配得到的特征碼ID。第2)~5)行為頂層模塊調(diào)用的子模塊,Mult模塊是一個數(shù)據(jù)選擇器,在每個時鐘確定該時鐘的狀態(tài)指針,若復位則輸出初始狀態(tài)指針,否則輸出Comparator輸出的指針;Read模塊的作用是通過Mult模塊輸出的狀態(tài)指針讀取IMB中的遷移邊;Sort模塊的作用是將Read模塊讀取的遷移邊根據(jù)狀態(tài)指針信號將遷移邊進行分類及優(yōu)先級排序;Comparator模塊是將遷移邊與輸入字符進行匹配,匹配時根據(jù)遷移邊中規(guī)則類型標識符,選擇對應的匹配電路進行匹配,這其中包括定義的類匹配。 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è)計 輔助變量存儲器給每一個擁有克林閉合組的規(guī)則設(shè)置一個地址,存儲空間大小等于所有規(guī)則中克林閉合組的最大值Kmax。在進行ID設(shè)置時,確定一個規(guī)則閾值Thr,將存在克林閉合組規(guī)則的ID值設(shè)置在閾值以下,使用ID值中大于閾值的高位存儲比較指令值;同時將MatchID的最高位設(shè)置為標志位,用來區(qū)別規(guī)則中是否存在克林閉合組,當最高位為“1”時表示存在,反之不存在。例如設(shè)規(guī)則數(shù)為100,存在克林閉合組的規(guī)則數(shù)為15,其中Kmax=4,則取MatchID為8bit,閾值Thr=16,設(shè)置輔助變量儲存器地址空間為4bit。若規(guī)則中僅含有一個,則在存儲器中存儲“1110”,存在兩個則存儲“1101”,存在三個則存儲“1100”,以此類推。當輸入規(guī)則ID時,若計數(shù)器值為0,則計數(shù)器讀取規(guī)則對應存儲器中的數(shù)值并加1,同時寄存ID;反之,則檢測輸入的ID與寄存器輸出的ID是否相同,相同則計數(shù)器直接加1,不同則計數(shù)器讀取新規(guī)則數(shù)據(jù)并加1。每次輸入都要更新寄存器中的ID值。計數(shù)器每計數(shù)結(jié)束需判斷計數(shù)值是否為“1111”,若是,則匹配成功,計數(shù)器置零,寄存器復位。 3.1 算法性能分析 通過分析Pre-ClassCFA與XFA的定義PC={Q,V,Σ′,δ′,U,(q0,v0),F}和X={Q,V,Σ,δ,U,(q0,v0),F},當初始狀態(tài)相同時,輸入相同的字符二者具有相同的目的狀態(tài),可證明Pre-ClassCFA與XFA等價。 由于正則表達式的復雜性和多樣性,以下通過分析最壞情況遷移邊數(shù)目來比較Pre-ClassCFA與XFA的性能。設(shè)自動機中狀態(tài)總數(shù)為Ns,字母表Σ中有m個字母,則XFA遷移邊總數(shù)Xt=Ns×(m+1),Pre-ClassCFA遷移邊總數(shù)PCt=(Ns+c)-(c×Ratio),其中:c表示各個狀態(tài)非失敗轉(zhuǎn)移的遷移邊數(shù)目之和,Ratio表示各類類匹配在正則表達式遷移邊中所占的比例。二者相比,遷移邊減少數(shù)目為: 在自動機中,非失敗轉(zhuǎn)移的遷移邊數(shù)目之和c為: c=Ns*N;N≥1,N∈Z+ 則 RX/PC=(m+1)/[1+(1-Ratio)×N] 通過對Snort2.9.8.0中的正則表達式規(guī)則進行統(tǒng)計分析,發(fā)現(xiàn)其中33%的規(guī)則進行匹配時不區(qū)分大小寫,包含字母、數(shù)字以及否定形式等其他類匹配的正則表達式規(guī)則占規(guī)則總數(shù)約42%,根據(jù)文獻[14]統(tǒng)計分析,Snort規(guī)則的平均長度為207,則Ratio≈6.8%。在理想情況下,當m=256,N=3時,與XFA相比,Pre-ClassCFA在遷移邊數(shù)目上減少了67.6%。 3.2 實驗評估 實驗使用ALTERA低成本CycloneⅡ系列的開發(fā)平臺,平臺搭載EP2C70F896C6FPGA芯片,選擇Snort規(guī)則庫規(guī)則集進行仿真實驗分析,將規(guī)則文件編譯為Pre-ClassCFA,并將其遷移邊存儲在IMB中。根據(jù)文獻[14]給出的實驗結(jié)果,并聯(lián)只讀存儲器(Read-OnlyMemory,ROM)進行并行流水線操作時,由于多路選擇器在數(shù)據(jù)讀取時存在延遲,因而并非并聯(lián)塊數(shù)越多數(shù)據(jù)的處理效率越高。在使用流水線的方式設(shè)計Pre-ClassCFA時,使用的資源全部是寄存器和查找表等非邏輯資源。表3給出了使用不同數(shù)量并聯(lián)ROM進行流水線操作時Pre-ClassCFA使用的LTU(LookUpTable)、REG(REGister)數(shù)目以及自動機的最大工作頻率。從表中可以看出,自動機消耗的FPGA資源很小,消耗量小于器件資源總量的1%;對比表中流水線結(jié)構(gòu)和非流水線結(jié)構(gòu)自動機的最大頻率可以看出,通過在系統(tǒng)中增加流水線級數(shù)可以提高系統(tǒng)頻率,且采用2級流水線的4-ROM結(jié)構(gòu)自動機的工作頻率達到最大值,由于受實驗器件性能的約束,系統(tǒng)有最大工作頻率為162.06MHz,系統(tǒng)最大吞吐量可達到1.3Gb/s。 表3 不同數(shù)目并聯(lián)ROM的實驗相關(guān)參數(shù) 本文從Snort規(guī)則庫中選擇FTP、exploit、SMTP、Web-client和Web-misc五個規(guī)則集對算法進行分析評估,如表4所示給出了使用XFA、CFA和本文算法編碼上述規(guī)則集所需的遷移邊數(shù)目。 表4 Snort規(guī)則集參數(shù)統(tǒng)計 從表4中可以看出,本文算法與XFA算法相比遷移邊數(shù)目減少了70.21%~90.37%,與CFA算法相比遷移邊數(shù)目減少了15.41%~33.05%,其中正則表達式中類匹配出現(xiàn)頻率越高,遷移邊壓縮效果越明顯。同時本文提出的基于IMB的遷移邊查找方法針對FPGA存儲器結(jié)構(gòu)設(shè)計,充分利用了器件的片內(nèi)存儲器資源,與CFA算法片內(nèi)片外分步查找方法相比,查詢性能有較大的提升,性能提升程度與器件性能相關(guān),在本文使用的FPGA器件中,若使用同步靜態(tài)隨機存取存儲器(SynchronousStaticRandomAccessMemory,SSRAM)作為片外存儲器,則查詢性能提高了56.62%。 本文提出了一種基于XFA的改進正則表達式匹配算法——Pre-ClassCFA算法。算法通過預定義類,減少了正則表達式中字符類匹配時遷移邊條數(shù)。在Pre-ClassCFA數(shù)據(jù)存儲中,本文基于并聯(lián)ROM結(jié)構(gòu)設(shè)計了適合該算法遷移邊特征的IMB遷移邊存儲結(jié)構(gòu),通過對遷移邊進行編碼,將數(shù)據(jù)全部存儲在片內(nèi)存儲器中,大大提高了數(shù)據(jù)讀取速度,從而確保了算法的匹配效率。實驗結(jié)果表明,Pre-ClassCFA在大大壓縮遷移邊的同時可以在頻率上限為260MHz的中低性能FPGA系統(tǒng)中實現(xiàn)大規(guī)模正則表達式的高速匹配,系統(tǒng)吞吐量可達到1.3Gb/s,可滿足千兆網(wǎng)絡下的數(shù)據(jù)檢測。 雖然本文算法在遷移邊壓縮和匹配效率上取得了較好的效果,但是該算法通過軟件編程實現(xiàn)的規(guī)則預處理過程步驟多、處理過程復雜,尤其是對于極少數(shù)特殊的類匹配,由于目前規(guī)則處理程序不夠完善,仍需要進行人工處理,從而給系統(tǒng)規(guī)則的更新造成影響。作者下一步的研究方向是對規(guī)則預處理程序進行完善,提高算法的整體性能。 ) [1] 褚衍杰,李云照,魏強.一種改進的多模式匹配算法[J].西安電子科技大學學報(自然科學版), 2014, 41(6): 174-179.(CHUYJ,LIYZ,WEIQ.Improvedmulti-patternmatchingalgorithm[J].JournalofXidianUniversity(NaturalScience), 2014, 41(6): 174-179.) [2] 嵩天,李冬妮,汪東升,等.存儲有效的多模式匹配算法和體系結(jié)構(gòu)[J].軟件學報,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ù)包檢測的緊湊型正則表達式匹配算法[J].中國科學:信息科學,2010,40(2):356-370.(HUANGK,ZHANGDF,XIEGG,etal.Deeppacketinspectionorientedcompactregularexpressionmatchingalgorithm[J].ScienceChinaInformationSciences, 2010, 40(2): 356-370.) [8] 張大方,張潔坤,黃昆.一種基于智能有限自動機的正則表達式匹配算法[J].電子學報,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。 國家自然科學基金資助項目(61402531);陜西省自然科學基金資助項目(2014JQ8307,2015JQ6231)。 麥濤濤(1992—),男,河南洛陽人,碩士研究生,主要研究方向:網(wǎng)絡安全、嵌入式系統(tǒng); 潘曉中(1964—),男,陜西西安人,教授,碩士,主要研究方向:網(wǎng)絡安全、嵌入式系統(tǒng); 王亞奇(1982—),男,河南周口人,講師,博士,主要研究方向:網(wǎng)絡空間安全; 蘇陽(1986—),男,寧夏銀川人,助教,碩士,主要研究方向:嵌入式系統(tǒng)。 1001- 9081(2017)02- 0397- 05 10.11772/j.issn.1001- 9081.2017.02.0397 TP393 A3 算法性能分析與實驗評估
4 結(jié)語