基于預定義類的緊湊型正則表達式匹配算法

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

(1.武警工程大學 電子技術系，西安 710086； 2.武警部隊網絡與信息安全保密重點實驗室，西安 710086)

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

基于預定義類的緊湊型正則表達式匹配算法

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

(1.武警工程大學 電子技術系，西安 710086； 2.武警部隊網絡與信息安全保密重點實驗室，西安 710086)

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

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

正則表達式匹配；擴展有限自動機；現場可編程門陣列

0 引言

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

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

表1 Snort規則集統計分析結果

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

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

1 擴展有限自動機概述

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

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

圖1 {.*ab.*cd, .*ef.*gh}狀態圖

2 基于預定義類的緊湊型自動機

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

2.1 基于預定義類的遷移邊壓縮方法

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

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

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

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

圖2 “a[bB][^c][0- 8]*9[a-z]”DFA狀態圖

表2 “a[bB][^c][0- 8]*9[a-z]”狀態轉移表

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

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

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

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=不區分大小；

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

Tc=Tc∪t數字;

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 基于并聯存儲塊的遷移邊存儲與查找

為提高算法的資源利用率，在構造Pre-ClassCFA時使用多條規則構成一個自動機，則在進行匹配時需要查找對應狀態的所有遷移邊。狀態轉移邊的查找方法可以分為兩類：

1)使用狀態值和輸入值通過哈希函數產生指針進行查找；

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

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

2.2.1 遷移邊分類與規則定義

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

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

為實現規則的高速匹配，需要在一個時鐘內對某狀態的所有遷移邊進行分析。當前的現場可編程門陣列(Field-ProgrammableGateArray,FPGA)產品內部嵌有數百個片內存儲塊，使用這些存儲塊可以構造一個并聯存儲塊，不僅能提高查找效率，也能夠充分利用FPGA的存儲帶寬。

如果存儲塊數目n大于或者等于自動機中所有狀態的最大遷移邊數目Nmax，則所有的遷移邊可以在一個時鐘內實現并行處理；若n

圖4 “a[bB][^c][0- 8]*9[a-z]”遷移邊存儲結構

圖5給出了由存儲器構成的匹配引擎結構。引擎包括地址產生器、IMB、字符匹配器和狀態選擇器。遷移邊按照定義的規則存儲在IMB中，每個存儲塊都包含一個地址產生器，地址產生器根據當前狀態值產生對應塊匹配起始地址，讀取存儲的規則后，字符匹配器將與精確匹配中的字符進行匹配，當遇到類匹配時，根據類匹配的類型，選擇合適的匹配算法。匹配結束后的結果輸入到狀態選擇器中，狀態選擇器根據遷移邊的優先級決定下一狀態值。

圖5 匹配引擎結構

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

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 輔助變量存儲器設計

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

3 算法性能分析與實驗評估

3.1 算法性能分析

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

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

在自動機中，非失敗轉移的遷移邊數目之和c為：

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

則

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

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

3.2 實驗評估

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

表3 不同數目并聯ROM的實驗相關參數

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

表4 Snort規則集參數統計

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

4 結語

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

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

)

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

[2] 嵩天,李冬妮,汪東升,等.存儲有效的多模式匹配算法和體系結構[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] 黃昆,張大方,謝高崗,等.一種面向深度數據包檢測的緊湊型正則表達式匹配算法[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—),男,河南洛陽人,碩士研究生,主要研究方向:網絡安全、嵌入式系統; 潘曉中(1964—),男,陜西西安人,教授,碩士,主要研究方向:網絡安全、嵌入式系統; 王亞奇(1982—),男,河南周口人,講師,博士,主要研究方向:網絡空間安全; 蘇陽(1986—),男,寧夏銀川人,助教,碩士,主要研究方向:嵌入式系統。

1001- 9081(2017)02- 0397- 05

10.11772/j.issn.1001- 9081.2017.02.0397

TP393

A