楊嘉佳，姜臘林，姜 磊，戴 瓊，譚建龍

(1.長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114;2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190;3.中國(guó)科學(xué)院信息工程研究所，北京 100093)

1 概述

網(wǎng)絡(luò)入侵檢測(cè)(Network Intrusion Detection，NID)系統(tǒng)在網(wǎng)絡(luò)安全領(lǐng)域扮演著越來(lái)越重要的作用。當(dāng)前的NID，比如Bro［1］、Snort［2］和L7-filter 主要利用特征來(lái)描述和檢測(cè)網(wǎng)絡(luò)入侵行為。傳統(tǒng)的特征都是基于精確串模式來(lái)描述，但是隨著智能攻擊，傳統(tǒng)的基于精確串的特征描述難以準(zhǔn)確地描述這些新型攻擊的復(fù)雜特征，導(dǎo)致基于精確串的入侵檢測(cè)準(zhǔn)確率降低。由于正則表達(dá)式具有豐富和靈活的表達(dá)能力，當(dāng)前的NID 已采用正則表達(dá)式替代精確串來(lái)描述攻擊特征。據(jù)統(tǒng)計(jì)，截至2013 年，Snort 已經(jīng)有超過(guò)1 500條正則表達(dá)式規(guī)則。針對(duì)ClusterFA 算法存在的問(wèn)題，本文對(duì)類(lèi)中心向量表CommonTable 行之間的冗余建立索引表，同時(shí)利用游程編碼(Ren-length Encoding，RLE)［3］對(duì)連續(xù)重復(fù)轉(zhuǎn)移狀態(tài)進(jìn)行編碼。

2 背景介紹

傳統(tǒng)的正則表達(dá)式匹配算法都是用確定型有限自動(dòng)機(jī)(Deterministic Finite Automaton，DFA)和非確定型有限自動(dòng)機(jī)(Nondeterministic Finite Automaton，NFA)來(lái)實(shí)現(xiàn)。NFA 的時(shí)間復(fù)雜度是O(n2)，空間復(fù)雜度是O(n)，而DFA 最壞情況下的時(shí)間復(fù)雜度為O(1)，空間復(fù)雜度為O(2n)，容易遭遇空間爆炸性問(wèn)題。NFA 的時(shí)間復(fù)雜度是其理論模型決定的，在不改變處理器體系結(jié)構(gòu)的情況下很難對(duì)其進(jìn)行改進(jìn)，因此，當(dāng)前的研究大多集中于對(duì)DFA 的內(nèi)存空間進(jìn)行縮減。

自1960 年以來(lái)，大量與DFA 相關(guān)的算法和理論已經(jīng)被提出［4-6］，包括D2FA、δFA［7］、CRD、混合結(jié)構(gòu)自動(dòng)機(jī)、基于歷史記錄的自動(dòng)機(jī)［8］以及XFA 等，這些方法都是以時(shí)間換空間，通過(guò)增加計(jì)算量來(lái)減少內(nèi)在空間的使用。

文獻(xiàn)［9］發(fā)現(xiàn)較為復(fù)雜的正則表達(dá)式會(huì)造成DFA狀態(tài)數(shù)呈指數(shù)級(jí)增長(zhǎng)。為了避免這種情況，提出改寫(xiě)規(guī)則的思想，顯著地減少了DFA 狀態(tài)數(shù)目。此外，還提出將正則表達(dá)式進(jìn)行分組的思想，將具有較大相關(guān)度的正則表達(dá)式分到不同的組里，盡可能減少表達(dá)式之間的交互作用，從而減少DFA 所需存儲(chǔ)空間。

文獻(xiàn)［10］提出D2FA 表示方法，認(rèn)為如果2 個(gè)狀態(tài)對(duì)于相同的輸入字符具有相同的跳轉(zhuǎn)目標(biāo)，那么這2 個(gè)狀態(tài)是等價(jià)的。對(duì)于等價(jià)的狀態(tài)，用一條默認(rèn)轉(zhuǎn)移邊把2 個(gè)等價(jià)的狀態(tài)連接起來(lái)，通過(guò)引入默認(rèn)轉(zhuǎn)移來(lái)減少狀態(tài)轉(zhuǎn)移的數(shù)目，從而降低自動(dòng)機(jī)的存儲(chǔ)空間，實(shí)驗(yàn)結(jié)果表明D2FA 比DFA 減少存儲(chǔ)空間90%以上，但是引入默認(rèn)轉(zhuǎn)移邊導(dǎo)致一個(gè)字符可能需要多次訪存，會(huì)降低DFA 的匹配性能。為了解決這個(gè)問(wèn)題，文獻(xiàn)［11］對(duì)D2FA 進(jìn)行了改進(jìn)，提出了CD2FA。CD2FA 不僅具有類(lèi)似于D2FA 的壓縮效果，而且由于它使用了哈希函數(shù)，可以直接計(jì)算出對(duì)應(yīng)于每個(gè)字符的跳轉(zhuǎn)目標(biāo)，與原始DFA 一樣，每處理一個(gè)字符時(shí)只需訪問(wèn)1 個(gè)狀態(tài)，使得CD2FA 吞吐量與原始的DFA 相當(dāng)。

文獻(xiàn)［12］提出另一種消除狀態(tài)間由等價(jià)項(xiàng)而形成的冗余方法，稱(chēng)為δFA。通過(guò)觀察發(fā)現(xiàn)，在DFA中相鄰的狀態(tài)之間，通常會(huì)有大量的等價(jià)項(xiàng)，所以提出為DFA 增加一個(gè)臨時(shí)轉(zhuǎn)換表，而不必像D2FA 那樣使用缺省轉(zhuǎn)換。δFA 并不能完全避免冗余，而且它還必須增加額外的操作來(lái)更新臨時(shí)轉(zhuǎn)換表項(xiàng)，所以大量的更新操作可能會(huì)降低DFA 的匹配效率。

文獻(xiàn)［13］通過(guò)觀察DFA 的狀態(tài)轉(zhuǎn)移表，注意到每一個(gè)狀態(tài)都有大量相似的轉(zhuǎn)移狀態(tài)，只有少量(＜1%)不同的轉(zhuǎn)移狀態(tài)。通過(guò)分析D2FA，發(fā)現(xiàn)該算法是從相鄰的狀態(tài)來(lái)減少冗余，是一種局部的算法。因此從全局的視角出發(fā)，提出了一種新穎的可以大幅度縮減DFA 空間的算法，稱(chēng)為ClusterFA 算法，并首次采用簇聚類(lèi)技術(shù)來(lái)解決DFA 的壓縮問(wèn)題。實(shí)驗(yàn)證明，相對(duì)原始DFA 而言，能減少95%的空間消耗。但是該算法的壓縮效率與分組個(gè)數(shù)K 值密切相關(guān)，而確定K 值需要較大的時(shí)間復(fù)雜度。此外，觀察實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，算法類(lèi)中心向量表CommonTable 行與行之間存在冗余，以及每行的轉(zhuǎn)移狀態(tài)有較高的重復(fù)率，因此，該方法的壓縮率還可以進(jìn)一步提高。

3 ClusterFA 算法

ClusterFA 算法是在研究D2FA，δFA 時(shí)提出來(lái)的，是一種基于冗余消除達(dá)到內(nèi)存空間縮減目的的DFA 壓縮算法。

視DFA 狀態(tài)轉(zhuǎn)移表為一個(gè)N ×C 大小的矩陣，命名為DFAMatrix。其中，N 表示狀態(tài)的數(shù)目;C 是字母?jìng)€(gè)數(shù)，其值一般等于ASCII 字母表字符個(gè)數(shù)256。DFAMatrix［s，c］定義了當(dāng)輸入字符c 時(shí)，狀態(tài)從s 轉(zhuǎn)移到下一狀態(tài)。

ClusterFA 算法通過(guò)clusterStates()函數(shù)把類(lèi)似的狀態(tài)分成K 個(gè)分組，命名為Groups，同時(shí)建立索引表IndexTable 記錄DFA 狀態(tài)屬于哪一分組。然后從Groups 中的每一分組提取一個(gè)參考狀態(tài)，建立用于記錄K 個(gè)參考狀態(tài)的CommonTable 表和存儲(chǔ)特殊狀態(tài)的稀疏矩陣SparseMatrix 過(guò)程，如算法1［13］所示。

假設(shè)當(dāng)前狀態(tài)是s，輸入字符是c。在ClusterFA算法中執(zhí)行一次查找時(shí)，首先通過(guò)查找IndexTable，找到狀態(tài)所在分組的分組號(hào)(id)，再進(jìn)入Common-Table 表中找到分組id 對(duì)應(yīng)的中間狀態(tài)tcommon。

然后查找(s，c)是否在稀疏矩陣SparseMatrix中，如果存在，把tcommon當(dāng)作下一個(gè)狀態(tài)Snext，否則，把tcommon+SparseMatrix［s］［c］作為下一個(gè)狀態(tài)Snext，查找過(guò)程偽代碼描述如算法2［13］所示。

算法1

從N-狀態(tài)DFA 建立ClusterFA，其中，Groups［i］表示聚類(lèi)的第i 個(gè)分組

算法2

4 基于ClusterFA 算法的改進(jìn)

4.1 ClusterFA 算法分析

對(duì)于一個(gè)新的DFA，ClusterFA 算法很難決定將其分為多少分組較為合適。也就是說(shuō)，無(wú)法提前確定分組個(gè)數(shù)K 的理想值。更重要的是，K 值直接與壓縮效率有關(guān)。文獻(xiàn)［13］提出2 種方法來(lái)尋找理想K 值，第1 種方法是利用分層聚類(lèi)方法從N 中找到合適的K 值;第2 種方法是采用人工方法利用不同的K 值來(lái)測(cè)試聚類(lèi)算法，并找到理想K 值。第1 種方法的時(shí)間復(fù)雜度是O(N3)，其中，N 為狀態(tài)的數(shù)量，這種方法對(duì)于大規(guī)模DFA 來(lái)說(shuō)并不適用。一般地，采用第2 種方法來(lái)尋找合適的K 值，但是在實(shí)際應(yīng)用中用人工的方法從N 中找到理想K 值，工作量又太大，例如，對(duì)分組數(shù)K 與編譯時(shí)間的關(guān)系進(jìn)行實(shí)驗(yàn)(實(shí)驗(yàn)環(huán)境:處理器酷睿雙核T5750 2.00 GHz，內(nèi)存1 GB，Win7 操作系統(tǒng))，結(jié)果如表1 所示，隨著分組數(shù)K 的增加，編譯時(shí)間也不斷增長(zhǎng)。

表1 編譯時(shí)間與分組數(shù)關(guān)系 h

由于很難找到理想K 值，通過(guò)聚類(lèi)算法得到的CommonTable 表會(huì)出現(xiàn)很多有相同首尾的重復(fù)行，如圖1 所示，可以看出重復(fù)行占總行數(shù)9%～22%，而且CommonTable 表中重復(fù)行首尾相同部分占整行比例范圍為86.1%～96.1%，統(tǒng)計(jì)結(jié)果如表2 所示。因此，通過(guò)提取CommonTable 表中重復(fù)行的相同首尾部分建立索引表，減少CommonTable 表消耗的內(nèi)存空間。

圖1 各規(guī)則集重復(fù)行占總行數(shù)比例

表2 各規(guī)則集重復(fù)行首尾相同部分占整行比例 %

此外，通過(guò)ClusterFA 中的聚類(lèi)算法進(jìn)行聚類(lèi)后，CommonTable 表每行中會(huì)出現(xiàn)很多連續(xù)重復(fù)轉(zhuǎn)移狀態(tài)。假設(shè)連續(xù)重復(fù)的轉(zhuǎn)移狀態(tài)為一個(gè)片斷，根據(jù)統(tǒng)計(jì)，轉(zhuǎn)移狀態(tài)重復(fù)數(shù)為1 的片斷、轉(zhuǎn)移狀態(tài)重復(fù)數(shù)為2 的片斷與轉(zhuǎn)移狀態(tài)重復(fù)數(shù)為3 的片斷占整行的比例如圖2 所示。從圖中可以看出，長(zhǎng)度大于2的片斷占據(jù)了相當(dāng)比例，因此，設(shè)計(jì)一種策略對(duì)CommonTable 表進(jìn)行壓縮以進(jìn)一步節(jié)省內(nèi)存空間。

圖2 連續(xù)重復(fù)轉(zhuǎn)移狀態(tài)的各長(zhǎng)度片斷所占比例

4.2 Cluster 算法改進(jìn)方法

為了保證較好的壓縮效果，采用一種RLE 的變體［14］進(jìn)行編碼。對(duì)于連續(xù)重復(fù)的轉(zhuǎn)移狀態(tài)number，假設(shè)其重復(fù)次數(shù)為w(w≥2)，由于DFA 轉(zhuǎn)移狀態(tài)數(shù)值不為負(fù)數(shù)，可以用(-256 -w)來(lái)表示連續(xù)重復(fù)的w 個(gè)轉(zhuǎn)移狀態(tài);對(duì)于單個(gè)轉(zhuǎn)移狀態(tài)(w=1)，直接用該轉(zhuǎn)移狀態(tài)表示。例如對(duì)序列{1，1，1，2，4，3，4}編碼得，-259，1，2，4，3，4。

首先，利用ClusterFA 算法［13］將圖3 等價(jià)的原始DFA 表分解為CommonTable 表與SparseMatrix 表，分解過(guò)程示例如圖4 所示;然后，在ClusterFA 算法基礎(chǔ)上進(jìn)行擴(kuò)展，將CmmonTable 表分解成RLE_M 表與Rest_Table 表，并進(jìn)行RLE 壓縮后，得到RLE_Index表和RLE_Compress 表，過(guò)程示例如圖5 所示。

圖3 DFA 轉(zhuǎn)移狀態(tài)

圖4 原始DFA 的分解

圖5 分解壓縮

4.2.1 建表過(guò)程

建表過(guò)程分成4 個(gè)步驟:

(1)遍歷整個(gè)CommonTable 表，將有首尾相同部分com_pre，且首尾相同部分長(zhǎng)度L≥6 的行劃為一分組，記錄各行的行號(hào)id，剩下的不符合條件的行，不用分組，不記錄其行號(hào)id。假設(shè)符合條件的分組數(shù)量為X，如果X≥2，執(zhí)行步驟(2);否則，執(zhí)行步驟(4)。

(2)記錄每個(gè)分組的某一行中與com_pre 不同的部分non_com 的偏移位置，記為(start_pos，last_pos)。其中，start_pos 表示non_com 頭與行首的偏移量，last_pos 表示non_com 尾與行首的偏移量。對(duì)com_pre 進(jìn)行RLE 壓縮得pre，將(各行id，-2，start_pos，last_pos，pre，-1)放入索引表。-1 作為索引表RLE_Index 中分組與分組之間分隔標(biāo)志，-2 作為區(qū)分id 與start_pos 的界限標(biāo)志。對(duì)CommonTable 表建立REL_Index，結(jié)果如下:1 3，-2，5 6，-260 1 -258 3-1，由于RLE_Index 需要記錄有首尾相同部分的行id，non_com 的偏移位置start_pos，last_pos，以及用-2，-1 作為界限標(biāo)志，所以需要額外的空間開(kāi)銷(xiāo)，為了保證壓縮效果，在步驟(1)中只對(duì)有首尾相同部分且L≥6 的行在索引表REL_Index 中建立表項(xiàng)。接著執(zhí)行步驟(3)。

(3)假設(shè)CommonTable 提取首尾相同部分后，余下部分為Rest_Table 表，對(duì)Rest_Table 的每一行進(jìn)行RLE 編碼壓縮，最終的壓縮結(jié)果為一維數(shù)組RLE_Compress，Rest_Table 的每一行壓縮后占一維數(shù)組的一個(gè)片斷，用-1 表示一行的結(jié)束。

(4)執(zhí)行這一步，表明CommonTable 表沒(méi)有首尾相同部分的行，此時(shí)，只需對(duì)整個(gè)CommonTable 表進(jìn)行RLE 編碼，得到RLE_Compress 表。

建表過(guò)程偽碼如算法3 所示，第1 行has_common_Part()函數(shù)判斷CommonTable 表中是否有首尾相同部分且首尾相同部分長(zhǎng)度L ＞4 的行。如果有，則利用divide()函數(shù)將CommonTable 表分成X個(gè)分組Groups，第4 行proces_com_part ()函數(shù)將分組的首尾相同部分提取出來(lái)，第5 行RLE()函數(shù)對(duì)com_pre 進(jìn)行游程編碼，第6 行put()用于將(id，-2，start_pos，last_pos，pre，-1)片斷放入RLE_Index中，第8 行表示從CommonTable 中去掉所有com_pre后，剩余部分為Rest_Table。

算法3

4.2.2 查找過(guò)程

假設(shè)當(dāng)前狀態(tài)是s，輸入字符是c，為了查找到下一跳狀態(tài)，需要執(zhí)行以下步驟:

(1)通過(guò)查找IndexTable［12］，找到狀態(tài)所在分組的id，假設(shè)為y。

(2)通過(guò)搜索RLE_Index 表中‘各行id'字段，判斷y 是否在RLE_Index 表中;如果y 在RLE_Index表中，則得到其對(duì)應(yīng)的pre，start_pos，last_post，執(zhí)行步驟(3);若不在，則執(zhí)行步驟(4)。

(3)將pre 的前start_pos 位、RLE_Compress 中的第y 個(gè)片斷和pre 的后(256 -last_post-1)位連接起來(lái)并解碼得到向量pre_RLE_Compress，通過(guò)pre_RLE _ Compress ［c］→中 間 狀 態(tài) tcommon，執(zhí)行步驟(5)。

(4)將RLE_Compress 中第y 個(gè)片斷解碼得到向量RLE_Compress'，通過(guò)RLE_Compress'［c］→中間狀態(tài)tcommon，執(zhí)行步驟(5)。

(5)查找(s，c)是否在稀疏矩陣SparseMatrix中，如果不存在，把tcommon當(dāng)作下一個(gè)狀態(tài)Snext，否則把tcommon+SparseMatrix［s］［c］作為下一個(gè)狀態(tài)Snext。

查找過(guò)程偽碼描述如算法4 所示。其中，decoded(the y fragment of RLE_Compress)表示對(duì)RLE_Compress 中的第y 個(gè)片斷進(jìn)行解碼，BloomFilter.test(s，c)表示用Bloom 過(guò)濾器來(lái)判斷(s，c)是否在SparseMatrix 稀疏矩陣中。

算法4

5 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)環(huán)境:處理器酷睿雙核T5750 2.00 GHz，內(nèi)存1 GB，Win7 操作系統(tǒng)。利用開(kāi)源工具regex-tool生成原始DFA 狀態(tài)轉(zhuǎn)移表并利用Bro，Snort 和L7-filter 規(guī)則集進(jìn)行測(cè)試。由于空間爆炸問(wèn)題，很難將L7-filter 規(guī)則集直接生成DFA，因此把L7-filter 分成7 分組，然后利用開(kāi)源工具regex-tool 生成。同時(shí)，也把snort 規(guī)則分成3 分組。規(guī)則集的具體情況如表3所示［12］。

表3 規(guī)則集的具體情況

En_ClusterFA 壓縮率公式:

ClusterFA 壓縮率公式:

經(jīng)過(guò)對(duì)經(jīng)典的DFA 算法δFA，D2FA，以及ClusterFA 算法、En_ClusterFA 進(jìn)行測(cè)試，δFA，D2FA采用文獻(xiàn)［12］中原有數(shù)據(jù)，而對(duì)ClusterFA 算法、En_ClusterFA 分別利用式(1)、式(2)測(cè)試20 次，然后取平均值，得到的壓縮率如表4 所示。

以規(guī)則集為橫坐標(biāo)，壓縮率為縱坐標(biāo)，將表4 繪制成趨勢(shì)圖，如圖6 所示，同時(shí)將表4 中ClusterFA算法與En_ClusterFA 測(cè)試結(jié)果進(jìn)行繪圖，如圖7所示。

從圖6 可以看出，En_ClusterFA 的壓縮率是最好的，而且壓縮率曲線相比其他算法更穩(wěn)定。而從圖7 也可以看出，En _ ClusterFA 的壓縮率較ClusterFA 算法有較好改善，平均壓縮率從ClusterFA算法的95%提升到了99%。

表4 δFA，D2FA，ClusterFA，En_ClusterFA 算法壓縮率

圖6 各規(guī)則集的壓縮率趨勢(shì)

圖7 ClusterFA 算法與En_ClusterFA 壓縮率對(duì)比

但是，En_ClusterFA 算法過(guò)程中使用了RLE 編碼，這并不適合于用軟件來(lái)實(shí)現(xiàn)，因?yàn)榫幗獯a會(huì)消耗太多時(shí)間，從而導(dǎo)致該算法吞吐率較ClusterFA算法下降，如表5、圖8 所示為軟件實(shí)現(xiàn)該算法的吞吐率情況，后續(xù)工作將進(jìn)一步從減少編解碼所消耗的時(shí)間入手，利用FPGA 硬件的并行性特點(diǎn)，對(duì)RLE 編解碼過(guò)程進(jìn)行優(yōu)化，提高En_ClusterFA 的吞吐率。

表5 吞吐率比較 (MB·s -1)

圖8 ClusterFA 和En_ClusterFA 吞吐率比較

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

本文針對(duì)ClusterFA 算法的數(shù)據(jù)冗余問(wèn)題進(jìn)行研究，結(jié)合游程編碼的優(yōu)點(diǎn)，提出了改進(jìn)算法En_ClusterFA。將重復(fù)行相同首尾部分分離，然后對(duì)整個(gè)類(lèi)中心向量表游程編碼。實(shí)驗(yàn)結(jié)果表明，En_ClusterFA 能夠有效地減少ClusterFA 算法的數(shù)據(jù)冗余，減少存儲(chǔ)空間消耗。今后的研究重點(diǎn)是利用現(xiàn)場(chǎng)可編程門(mén)陣列［14-16］加速En_ClusterFA 算法的編碼與解碼，減少編碼與解碼所消耗的時(shí)間，提高吞吐率。

［1］Paxson V.A System for Detecting Network Intruders in Real-time［J］.Computer Networks，1999，31 (23):2435-2463.

［2］Roesch M.Snort-lightweight Intrusion Detection for Networks［C］//Proc.of the 13th USENIX Conference on System Administration.Seattle，USA:［s.n.］，1999:229-238.

［3］蒙繼華，孫寶生，李 婷.采用行程編碼進(jìn)行位圖壓縮的研究［J］.新疆大學(xué)學(xué)報(bào)，2003，20(4):121-123.

［4］Yates R B，Gonnet H.Fast Text Searching for Regular Expressions or Automation Searing on Tries［J］.Journal of the ACM，1996，43(6):915-936.

［5］Myers G.A Four Russians Algorithm for Regular Expression Pattern Matching［J］.Journal of the ACM，1992，39(2):432-448.

［6］Thompson K.Programming Techniques:Regular Expression Searching Algorithm［J］.Communications of the ACM，1968，11(6):419-422.

［7］Ficara D，Giordano S，Procissi G，et al.An Improved DFA for Fast Regular Expression Matching ［J］.ACM SIGCOMM Computer Communication Review，2008，38(5):29-40.

［8］Kumar S，Chandrasekaran B，Turner J，et al.Curing Regular Expressions Matching Algorithms from Insomnia，Amnesia，and Acalculia［C］//Proc.of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems.Washington D.C.，USA:［s.n.］，2007:144-164.

［9］Yu Fang，Chen Zhifeng，Diao Yanlei，et al.Fast and Memory-efficient Regular Expression Matching for Deep Packet Inspection［C］//Proc.of ACM/IEEE Symposium on Architecture for Networking and Communications Systems.New York，USA:［s.n.］，2006:93-102.

［10］Kumar S，Crowley P，Yu Fang，et al.Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection［C］//Proc.of Annual Conference of ACM Special Interest Group on Data Communication.Pisa，Italy:［s.n.］，2006:339-350.

［11］Kumar S，Turner J，Williams J.Advanced Algorithms for Fast and Scalable Deep Packet Inspection［C］//Proc.of ACM/IEEE Symposium on Architecture for Networking and Communications Systems.［S.l.］:IEEE Press，2006:81-92.

［12］Ficara D，Giordano S，Procissi G，et al.An Improved DFA for Fast Regular Expression Matching ［J］.ACM SIGCOMM Computer Communication Review，2008，38(5):29-40.

［13］Jiang Lei，Tan Jianlong，Liu Yuanbin.ClusterFA:A Memory-efficient DFA Structure for Network Intrusion Detection［C］//Proc.of the 7th ACM Symposium on Information，Computer and Communications Security.Seoul，South Korea:［s.n.］，2012:65-66.

［14］Lee J，Hwang S H，Park N，et al.A High Performance NIDS Using FPGA-based Regular Expression Matching［C］//Proc.of ACM Symposium on Applied Computing.New York，USA:［s.n.］，2007:1187-1191.

［15］Faezipour M，Nourani M.Constraint Repetition Inspection for Regular Expression on FPGA［C］//Proc.of the 16th IEEE Symposium on High Performance Interconnects.［S.l.］:IEEE Press，2008:111-118.

［16］Yang Y，Prasanna V K.Automatic Construction of Largescale Regular Expression Matching Engines on FPGA［C］//Proc.of the International Conference on Reconfigurable Computing and FPGAs.［S.l.］:IEEE Press，2008:73-78.