一種實現(xiàn)網(wǎng)絡(luò)入侵檢測的高效算法及其實現(xiàn)架構(gòu)

余 偉，田新志，陳 丹

(1.西安思源學(xué)院 基礎(chǔ)部，西安 710038;2.西安思源學(xué)院 電子信息工程學(xué)院，西安 710038；3.西安空間無線電技術(shù)研究所，西安 710100)

0 引言

隨著互聯(lián)網(wǎng)發(fā)展成為一個巨大的全球開放網(wǎng)絡(luò)，對互聯(lián)網(wǎng)的攻擊從未停止過，從黑客攻擊、邪惡的探測攻擊到網(wǎng)絡(luò)詐騙，這些攻擊甚至無需資金投入就能實現(xiàn)，而且可以在世界上任何地方發(fā)起；最常用的網(wǎng)絡(luò)保護(hù)系統(tǒng)是防火墻和網(wǎng)絡(luò)入侵檢測系統(tǒng)(NIDS,network intrusion detection system)[1-2]。它們安裝在網(wǎng)絡(luò)的邊界，以檢查和監(jiān)控流入和流出的網(wǎng)絡(luò)流量。防火墻只執(zhí)行網(wǎng)絡(luò)的第3層或第4層過濾，基于數(shù)據(jù)包頭部來處理數(shù)據(jù)包。而NIDS不僅提供第3層或第4層過濾，還提供了第7層過濾。NIDS搜索數(shù)據(jù)包頭部和有效載荷以識別攻擊模式(或簽名)。因此，NIDS可以檢測和阻止網(wǎng)絡(luò)上傳播的有害內(nèi)容，識別出攻擊的模式，然后采取行動終止連接或向系統(tǒng)管理員發(fā)出警報。

隨著互聯(lián)網(wǎng)的迅速發(fā)展和攻擊數(shù)量的劇增，NIDS的設(shè)計也已成為一個巨大的挑戰(zhàn)。現(xiàn)有的基于軟件的解決方案無法實現(xiàn)內(nèi)存高效利用和大的吞吐量，因此，必須采用硬件輔助。基于硬件的NIDS高速字符串匹配方案主要分為3大類：基于三態(tài)內(nèi)容尋址存儲器(TCAM,ternary content addressable memory)、基于動態(tài)/靜態(tài)隨機存取存儲器(DRAM/SRAM,dynamic/static random access memory)，以及基于SRAM邏輯的方案。盡管基于TCAM的引擎可以在一個時鐘周期內(nèi)檢索結(jié)果，但它們功耗太高，并且其吞吐量受到TCAM相對較低的速度限制；基于SRAM和SRAM邏輯的解決方案需要多個周期來執(zhí)行一次搜索。因此，通常采用流水線技術(shù)來提高吞吐量。同時，基于SRAM的方法受到內(nèi)存限制，導(dǎo)致低效的內(nèi)存利用，從而限制了所支持的字典大小。此外，由于I/O管腳數(shù)量的制約，在這些架構(gòu)中很難采用外部SRAM。由于這兩個限制，即使最先進(jìn)的基于SRAM的解決方案都不能很好地擴展以支持更大的字典。這種可擴展性一直是硬件中實現(xiàn)NIDS的主要問題。

一般來說，基于硬件的字符串匹配架構(gòu)可以分為3類：TCAM、流水線非確定有限自動機(NFA, non-deterministic finite automaton)和流水線確定有限自動機(DFA,deterministic finite automaton)。

在文獻(xiàn)[3]提出的基于TCAM的架構(gòu)中，利用未使用的TCAM記錄來提高搜索性能，選擇性地生成TCAM表項來合并重疊的匹配條件，從而大大減少訪問TCAM表項的數(shù)量。但整個字典都存儲在TCAM中，它對任何輸入都有確定的查找時間。這種架構(gòu)的優(yōu)點是內(nèi)存效率高(接近1字節(jié)/字符)和更新機制簡單，但實現(xiàn)的吞吐量低；在文獻(xiàn)[4-6]提出的流水線NFA字符串匹配架構(gòu)中，把所有給定的字符串模式組合起來構(gòu)建一個NFA，把NFA實現(xiàn)為一個流水線網(wǎng)絡(luò)，并行地匹配多個字符串模式。這些設(shè)計盡管能夠?qū)崿F(xiàn)8～10 Gbps的吞吐量，但主要缺點是缺乏靈活性和所支持的字典相對較小；文獻(xiàn)[7]提出的字段合并(FM,field merge)NFA架構(gòu)，將每個輸入字符劃分為k個位字段，并構(gòu)造一個樹結(jié)構(gòu)的NFA。然后，把字典“垂直地”劃分為正交的位字段，每個位字段用于構(gòu)造一個樹形結(jié)構(gòu)的NFA，稱為部分狀態(tài)機(PSM,partial state machine)。此外，在PSM的構(gòu)造過程中，維護(hù)一個逐級輔助表(ATB,auxiliary table)，以將每個完全匹配狀態(tài)唯一地映射到同一級別上的一組部分匹配狀態(tài)。這種設(shè)計的優(yōu)勢在于，通過采用相對較小的ATB，可以簡化流水線遍歷和PSM的輸出合并。字段合并NFA完全基于內(nèi)存，通過更新內(nèi)存內(nèi)容可以很容易地執(zhí)行動態(tài)字典更新，但其內(nèi)存效率依賴于字典，不同字典之間的差異很大；文獻(xiàn)[8-9]提出的位分割(BS, bit split)DFA架構(gòu)基于[10]的算法。它將N個模式的字典樹轉(zhuǎn)換為有O(N)個狀態(tài)的DFA，對于每個字符需要O(1)計算，無論字典大小。然而，狀態(tài)轉(zhuǎn)換表中的有效(非零)狀態(tài)通常非常稀少，這就導(dǎo)致了大量的內(nèi)存浪費，使得內(nèi)存帶寬和延遲成為這種架構(gòu)的瓶頸；為了提高內(nèi)存效率，文獻(xiàn)[11]提出了位分割算法，該算法將一個完整的DFA分割成幾個分裂狀態(tài)機。分裂狀態(tài)機中的每個狀態(tài)都維護(hù)一個部分匹配向量，以將狀態(tài)映射到一組可能的匹配。盡管這種設(shè)計提高了內(nèi)存效率，但對于具有數(shù)千個狀態(tài)的大型字典來說，從DFA構(gòu)建分裂狀態(tài)機的成本非常高。盡管可以優(yōu)化位分割方法的性能，但這樣的優(yōu)化需要為每個組規(guī)劃資源，并使動態(tài)字典更新更加困難；可變步幅(VS, variable-stride)多模式匹配架構(gòu)[12]也是一種基于DFA的方法，其主要思想是可以一步掃描可變數(shù)量的字符。盡管這是一個ASIC實現(xiàn)，但它實現(xiàn)了較高的內(nèi)存效率，并且可以移植到FPGA平臺。但這種設(shè)計的吞吐量較低，因為它高度依賴于字典。

上述研究的主要問題是低內(nèi)存效率、低吞吐量和相對較小的支持字典。此外，這些設(shè)計或多或少依賴于字母表的大小，隨著字母表大小的增加，內(nèi)存效率會降低；另一方面，基于TCAM的方案雖然具有較高的內(nèi)存效率和可擴展性，但吞吐量低和功耗高。隨著模式數(shù)據(jù)庫的增長，這些問題會變得更加嚴(yán)重。

為此，本文提出了一種預(yù)處理算法和一種可擴展、高吞吐量、內(nèi)存高效的大規(guī)模字符串匹配架構(gòu)。由于采用了線性流水線架構(gòu)，所以具有靈活的擴展性，還能保證固定的延遲。

1 背景知識以及問題定義和記號

1.1 字符串模式匹配

字符串模式匹配(也稱為精確字符串匹配或字符串匹配)是NIDS最重要的功能之一，它提供了內(nèi)容搜索功能。字符串匹配算法是將給定字典(或數(shù)據(jù)庫)中的所有字符串模式與流經(jīng)設(shè)備的流量進(jìn)行比較。

1.2 問題定義

字符串模式匹配問題可以表述為：給定一個長度為K的輸入字符串、一個由全部ASCII字符構(gòu)成的字母表∑(|∑|=256)和一個由N個字符串模式{S0,S1,…,SN-1}(其字符屬于字母表∑)構(gòu)成的字典，找到并返回給定輸入字符串中每個模式的所有出現(xiàn)(如果存在的話)。

1.3 記號

圖1所示為表1示例字典對應(yīng)的前綴樹[13-14]表示。給定一個字典和相應(yīng)的前綴樹表示，定義以下術(shù)語和記號：

圖1 表1示例字典的前綴樹

表1 事例模式數(shù)據(jù)庫(字典)(最大模式長度為8)

1)字符串、模式或簽名：標(biāo)識任何惡意內(nèi)容的獨特特征；

2)*(星號)：包含一個空的任何字符串；

3){n}：重復(fù)前一項n次，其中n是一個正整數(shù)；

4)|S|：字符串S的長度(以位表示)，例如當(dāng)每個ASCII字符占用8位時|abcd|=32；

5)S1是S2的前綴當(dāng)且僅當(dāng)S2=S1(，如S1=ab，S2=abcd，S1說成是S2的前綴孩子，S2是S1的前綴父親。為簡單起見，分別用孩子和父來表示前綴孩子和前綴父親。在S1=S2時，S1是S2的前綴，反之亦然；

6)S1和S2是不同的當(dāng)且僅當(dāng)S1不是S2的前綴且S2不是S1的前綴，否則，認(rèn)為它們是重疊的。所有模式對都是不相交的一組模式稱為不相交模式集；

7)S1

8)字符串S的二進(jìn)制表示記為BS，將S的所有字符轉(zhuǎn)換成其相應(yīng)的ASCII值即可得到；

9)字符串S的范圍表示用L位(L>|S|)表示為RS=[RSL,RSH]，其中RSL=BS0{n}和RSH=BS1{n}，滿足n=L-|S|。在L=|S|時，RS=[BS,BS]；

10)任何節(jié)點(從前綴樹的根到該節(jié)點的路徑表示字典中的模式)都稱為模式節(jié)點。如果一個模式位于一個葉子節(jié)點上，則它就稱為葉子模式節(jié)點，否則，就稱為非葉子模式節(jié)點。

2 字符串匹配算法

2.1 前綴屬性

字符串匹配可以構(gòu)建為前綴匹配問題。考慮兩個字符串SA和SB，在L位數(shù)空間(Ω=[0{L},1{L}]中，L≥max(|SA|,|SB|)，令nA=L-|SA|，nB=L-|SB|和nAB=abs(|SB|-|SA|)=abs(nB-nA)。下面給出用作為本文研究基礎(chǔ)的屬性。

屬性1：給定兩個不同的字符串SA和SB，如果|SA|=|SB|，則SA和SB不重疊。

屬性2：給定兩個不同的字符串SA和SB，如果它們重疊，則其中一個必須是另一個的前綴。

屬性3：給定兩個不同的字符串SA和SB，如果SA是SB的前綴，則SA

2.2 葉子-追加算法

對于字符串匹配引擎來說，樹搜索算法是一個很好的選擇，因為查找延遲不依賴于模式的長度，而是取決于字典中模式的數(shù)量。然而，為了采用樹搜索算法，需要對給定的模式集進(jìn)行處理，以消除模式之間的重疊。

對此，本文提出一種葉子-追加算法來分離模式。算法以前綴樹作為輸入，輸出一組不相交的模式。所有孩子(或非葉子)模式都與它們的父親(或葉子)模式合并。令L為模式的最大長度，每個父模式都有一個長度為L位的匹配向量(MV, matching vector)附屬于它。匹配向量是一個二進(jìn)制字符串，指示父模式中包含多少個子-父模式以及它們是什么。位置i的值為1意味著有一個長度為i字節(jié)的子-父模式，從父模式的開頭開始。例如，如果父模式是andy，且它的匹配向量是0111，則包含3個子模式：an、and和andy，分別對應(yīng)于位置2、3和4上的1。一個模式可以是多個父模式的子模式(前綴)。圖2所示為兩個父模式andy和between的示例合并。前綴樹是從一組給定模式構(gòu)建的。樹的每個節(jié)點包括：1)一個葉子位；2)一個模式位；3)一個模式；4)一個匹配向量。葉子位和模式位分別確定節(jié)點是葉子節(jié)點還是模式節(jié)點。葉子-追加算法按順序遍歷前綴樹，并將非葉子模式推到它們的葉子模式，圖3所示為圖1的前綴樹在執(zhí)行葉子-追加算法后的結(jié)果。一旦前綴樹被附加葉子后，就收集葉子及其相關(guān)的匹配向量，以形成一個不相交的模式集。表2所示為表1示例字典在葉子-追加算法后的字典。

圖2 示例合并

圖3 葉子-追加樹

表2 表1示例字典在葉子-追加算法后的模式

2.3 二叉搜索樹字符串匹配算法

本節(jié)提出一種基于完全二叉搜索樹(BST, binary search tree)[15]的高效內(nèi)存數(shù)據(jù)結(jié)構(gòu)。二叉搜索樹算法是一種在排序列表中查找特定元素的技術(shù)。

給定字典經(jīng)過葉子-追加，并提取葉子模式及其匹配向量，葉子模式用于構(gòu)建BST，BST中的每個節(jié)點包含一個模式和一個匹配向量。構(gòu)建了相應(yīng)的BST之后，根據(jù)每個節(jié)點的比較結(jié)果，通過左遍歷或右遍歷來執(zhí)行字符串匹配。如果輸入字符串小于或等于該節(jié)點的值，則將其轉(zhuǎn)發(fā)到該節(jié)點的左子樹，否則轉(zhuǎn)發(fā)到右子樹。

為表2中的不相交模式集構(gòu)建的完整BST示例如圖4所示，示例中考慮的是最大長度為8個字符的模式。完整的BST映射如下：每一層的節(jié)點都存儲在一個連續(xù)的內(nèi)存塊中。令x表示節(jié)點A的索引值。A有2個孩子節(jié)點，索引值為2x(左孩子)和2x+1(右孩子)。在以2為基的數(shù)字系統(tǒng)中，2x={x,0}和2x+1={x,1}，其中{}表示串接。采用這個內(nèi)存映射，不需要將孩子指針存儲在每個節(jié)點上，這些指針是通過簡單地將當(dāng)前節(jié)點的地址與比較結(jié)果位串接起來顯式地實時計算的。

圖4 表2中不相交模式集的示例完整BST

輸入流用8個字符的窗口進(jìn)行處理，每次前進(jìn)1個字符。例如有一個8個字符的輸入字符串a(chǎn)nchorer到達(dá)，匹配狀態(tài)向量(MSV,matching status vector)被重置(MSV=00000000)。在樹的根(P12)，將輸入與節(jié)點的模式car進(jìn)行比較，得到不匹配和“l(fā)ess than”結(jié)果。輸入字符串向左遍歷。在節(jié)點P11，它與模式beat進(jìn)行比較，再次得到相同的結(jié)果。然后輸入字符串被轉(zhuǎn)發(fā)到左邊。在節(jié)點P3，輸入字符串匹配節(jié)點的模式andy，得到一個匹配和一個“l(fā)ess than”結(jié)果。當(dāng)輸入字符串與孩子模式an匹配時，MSV的第二位被設(shè)置為MSV=01000000。輸入字符串然后遍歷到左邊。在節(jié)點P5，輸入字符串匹配節(jié)點的模式anchor且MSV=01000010，這就是最后結(jié)果。

注意，一個輸入字符串的所有匹配模式必須是最長匹配模式的前綴。因此，葉子-追加步驟確保這些模式包含在最長模式的同一節(jié)點中。如果輸入字符串SI到達(dá)該節(jié)點，則應(yīng)該找到所有匹配模式，即輸入字符串SI到達(dá)了包含最長匹配模式的節(jié)點。

2.4 BST字符串匹配算法的內(nèi)存效率

本節(jié)分析采用提出的葉子-追加算法生成的不相交模式集(SDP,set of disjoint patterns)，分析中用到以下記號：

1)L：不相交模式的最大長度(以字節(jié)為單位)；

3)NDP：不相交模式的數(shù)目；

4)MDP：不相交模式集的大小(以字節(jié)為單位)；

5)MBST：采用BST數(shù)據(jù)結(jié)構(gòu)存儲SDP所需內(nèi)存的大小(以字節(jié)為單位)；

每個不相交模式有一個長度為L位(或L/8字節(jié))的匹配向量。MDP和MBST分別根據(jù)式(1)和(2)計算，式(3)為BST字符串匹配算法的內(nèi)存效率：

(1)

MBST=NDP×(L+L/8)=9NDP/8×L

(2)

(3)

2.5 BST級聯(lián)

圖5 BST級聯(lián)原理的框圖

3 實現(xiàn)架構(gòu)

3.1 總體架構(gòu)

本文提出一種基于流水線的二叉搜索樹來實現(xiàn)可擴展、高吞吐量、內(nèi)存高效的字符串匹配架構(gòu)，實現(xiàn)原理框圖如圖6所示。如上所述，匹配步驟包括(1)模式匹配和(2)標(biāo)簽匹配，分別由模式匹配模塊(PMM,pattern matching module)和標(biāo)簽匹配模塊(LMM,label matching module)完成。輸入數(shù)據(jù)流一次輸入到PMML個字節(jié)，輸入窗口每個時鐘周期前進(jìn)1個字節(jié)。然后，PMM根據(jù)模式數(shù)據(jù)庫匹配輸入字符串，同時LMM匹配{前綴, 后綴, 匹配向量}組合，以驗證長模式并輸出匹配結(jié)果。臨界點是輸入窗口的大小L與LMM中的記錄數(shù)之間的關(guān)系。窗口大小L應(yīng)大于或等于LMM的匹配延遲。因此，L應(yīng)根據(jù)字典的大小來選取。

圖6 總體架構(gòu)原理框圖

3.2 PMM架構(gòu)

流水線用于每個時鐘周期生成一個查找操作，以提高吞吐量。流水線級的數(shù)量由搜索樹的高度決定。樹的每一層映射到一個流水線級，流水線級有自己的內(nèi)存(或表)。級聯(lián)BST用于提高內(nèi)存效率。因此，PMM架構(gòu)中使用了多個BST。

基本流水線和BST的單個級的框圖如圖7所示。為了利用架構(gòu)提供的雙端口特性，把該架構(gòu)配置為雙線性流水線。這種配置使得匹配速率加倍。在每一級，內(nèi)存有2組讀/寫端口，以便每個時鐘周期可以輸入2個字符串。內(nèi)存中每個記錄的內(nèi)容包括：(1)一個模式P，(2)一個匹配向量MV和(3)一個模式標(biāo)簽PL。在每個流水線級，有4個數(shù)據(jù)字段轉(zhuǎn)發(fā)自前一級：(1)輸入字符串SI，(2)匹配狀態(tài)向量MSV，(3)內(nèi)存訪問地址Addr和(4)匹配標(biāo)簽ML。轉(zhuǎn)發(fā)的內(nèi)存地址用于檢索模式及其存儲在本地內(nèi)存中的相關(guān)數(shù)據(jù)。將此信息與輸入字符串進(jìn)行比較，以確定匹配狀態(tài)。在匹配的情況下，匹配標(biāo)簽ML和匹配狀態(tài)向量MSV被更新。比較結(jié)果(如果輸入字符串大于節(jié)點的模式，則為1，否則為0)添加到當(dāng)前內(nèi)存地址并轉(zhuǎn)發(fā)到下一級。

圖7 模式匹配模塊及其基本流水線級的架構(gòu)

在流水線的每一級有一個比較器。它將輸入字符串與節(jié)點的模式進(jìn)行比較，并用節(jié)點的匹配向量來生成匹配狀態(tài)向量。輸入包括：(1)一個輸入字符串SI，(2)一個模式P，(3)一個匹配向量MV，(4)一個模式標(biāo)簽PL和(5)一個匹配標(biāo)簽。輸入字符串SI和模式P進(jìn)入到字節(jié)比較器，比較器執(zhí)行兩個輸入的字節(jié)比較。結(jié)果(M7-M0)輸入到匹配向量解碼器。解碼器的輸出與節(jié)點的匹配向量進(jìn)行與(AND)，然后結(jié)果與字符串比較器的輸出進(jìn)行與(AND)，比較器將模式標(biāo)簽和匹配標(biāo)簽進(jìn)行比較，以生成一個8位匹配向量(MSV)。

3.3 LMM架構(gòu)

LMM架構(gòu)幾乎與PMM架構(gòu)相同。不同之處在于(1)只有一個BST，(2)每個記錄沒有匹配向量和(3)不再需要匹配標(biāo)簽字段。匹配操作實際上更簡單，因為它不需要處理重疊問題。此外，每個節(jié)點中搜索鍵的大小實質(zhì)上更短，使得比較更快。在設(shè)計中，用一個完整的BST來搜索標(biāo)簽匹配表。LMM架構(gòu)及其基本的流水線級如圖8所示。

圖8 標(biāo)簽匹配模塊及其基本流水線級的架構(gòu)

令Nl表示LMM表中的記錄數(shù)目。LMM的延遲時間為「log2(Nl+1)?。如前所述，輸入窗口大小L必須大于或等于LMM的延遲，即L≥「log2(Nl+1)?。

3.4 字典更新

字典更新包括2個操作：1)模式刪除和2)新模式插入。第一種更新需要刪除現(xiàn)有的模式。每個模式可以包括(a)多個模式和(b)僅一個模式。在情形(a)，刪除可以通過重置已處理模式的匹配向量的位i來完成，其中i是待刪除模式的長度。例如，考慮有匹配向量0111的模式andy。要刪除模式 and，第3位設(shè)置為0，匹配向量變?yōu)?101。在情形(b)，有2種可能方法：惰性刪除和完全刪除。惰性方法可以采用在情形(a)中描述的相同更新機制來執(zhí)行。完全刪除時，如果樹的結(jié)構(gòu)發(fā)生變化，則必須重新構(gòu)建BST，并且必須重新加載每個流水線級的整個內(nèi)存內(nèi)容。

在第二種更新中，把新模式插入到現(xiàn)有的字典中。如果新模式有父模式，則只需要更新父匹配向量來包含新模式。如果新模式不是任何現(xiàn)有模式的孩子，則添加一個新節(jié)點。

3.5 模塊可擴展性

本文設(shè)計的架構(gòu)可以橫向擴展，也可以縱向擴展，或二者同時擴展。在橫向方向上，可以添加更多的流水線級來支持更大的字典。如果片上存儲器的數(shù)量不夠，則可以將流水線級擴展到外部SRAM；在縱向擴展中，可以多次復(fù)制架構(gòu)。這時，全部流水線有相同的內(nèi)存內(nèi)容，并且可以同時匹配更多的數(shù)據(jù)流。由于每個流水線中的匹配是獨立執(zhí)行的，所以輸入流可以在每個流水線中(流內(nèi))交叉地匹配不同字符；每個流水線還可以匹配獨立的輸入流(流間)，以增加總的吞吐量；除了這兩種情形外，還可以在兩個方向上擴展架構(gòu)，以支持更大的字典，同時獲得更高的吞吐量。

4 性能評價

4.1 實驗設(shè)置

采用Snort[16]和Rogets[17]用于實驗的安全字典。Snort是惡意互聯(lián)網(wǎng)活動的簽名列表，是一種普遍的開源和跨平臺NIDS，它采用簽名和包頭來檢測惡意Internet活動。作為一個開源系統(tǒng)，Snort規(guī)則由網(wǎng)絡(luò)安全社區(qū)提出，以制定廣泛接受和有效的規(guī)則集；Rogets是系統(tǒng)黑客通用密碼破解者單詞列表，該字典通常為系統(tǒng)黑客提供可行的密碼和詞表，相反，在網(wǎng)絡(luò)安全社區(qū)中用于防止服務(wù)器/系統(tǒng)密碼被黑。兩個實驗字典的統(tǒng)計數(shù)據(jù)如表3所示。

表3 Rogets和Snort字典的統(tǒng)計數(shù)據(jù)

4.2 內(nèi)存效率

本節(jié)對所提出的字符串匹配算法的內(nèi)存效率進(jìn)行評價。兩個實驗字典的不同段長度值的標(biāo)簽匹配表中的記錄數(shù)如表4所示。

表4 不同段長度值的標(biāo)簽匹配表中的記錄數(shù)

如前所述，段長度L需要大于或等于LMM的匹配延遲，所以在設(shè)計中用一個完整的BST來實現(xiàn)LMM。因此，標(biāo)簽匹配表中的記錄數(shù)不應(yīng)超過2L-1，故分析中采用3個L值(16,20,24)。對于每個L值，采用不同LS∈{4,8,12,16}值的級聯(lián)BST方法實現(xiàn)PMM。

表5所示為實驗得到的結(jié)果，其中PMM的內(nèi)存需求和LMM的內(nèi)存需求分別表示為MPMM和MLMM(以比特為單位)，對于L和LS的每個組合的總體設(shè)計的內(nèi)存效率表示為ME；可見，當(dāng)L=24和LS=4時，Rogets和Snort的內(nèi)存效率都達(dá)到了最佳，分別為0.56字節(jié)/字符和1.32字節(jié)/字符。最大的Rogets和Snort字典分別只需要100 kB和300 kB的片上內(nèi)存，而先進(jìn)的FPGA設(shè)備需要超過4 MB的片上內(nèi)存。因此，所提出的架構(gòu)足以滿足NIDS的實際實現(xiàn)。還可看到，Rogets字典有更好的內(nèi)存效率，因為Rogets的字母表較小為26，而Snort為256。

表5 不同段長度值的Rogets和Snort字典的內(nèi)存效率

4.3 吞吐量

采用帶Virtex-5 FX200T的Xilinx ISE 12.4為FPGA，在Verilog中實現(xiàn)所提出的模式匹配核。表6所示為對于不同模式段長度(以字節(jié)為單位)的實驗結(jié)果。可見，在所有情形下，邏輯資源的數(shù)量都很低(不到總資源的15%)。對于24字節(jié)的段長度，實現(xiàn)了197 MHz的頻率，實現(xiàn)了每個流水線1.6 Gbps的吞吐量，在雙流水線架構(gòu)下，吞吐量達(dá)到了3.2 Gbps。

表6 不同段長的實現(xiàn)結(jié)果

4.4 與目前先進(jìn)設(shè)計的性能比較

在內(nèi)存效率和吞吐量方面進(jìn)行比較。盡管內(nèi)存效率影響最大支持字典的大小，但吞吐量決定整個設(shè)計的處理速度。對于內(nèi)存效率而言，較小的值表示更好的設(shè)計，而對于吞吐量，較大的值表示更好的設(shè)計。表7所示為本文設(shè)計和目前先進(jìn)設(shè)計的比較結(jié)果。這些先進(jìn)設(shè)計方法包括字段合并(FM,field merge)[7]、位分割(BS,bit split)[8]和可變步幅(VS,variable stride)[12]。為了公平比較，對段大小為8字節(jié)的整個Rogets和Snort字典計算內(nèi)存效率，并采用相同的FPGA設(shè)備實現(xiàn)。

表7 本文設(shè)計、VS、BS和FM的性能比較

可以看到，對于同一字典，本文設(shè)計在內(nèi)存效率和每流吞吐量方面都優(yōu)于目前的先進(jìn)設(shè)計方法。與最先進(jìn)的設(shè)計FM[7]相比，本文設(shè)計實現(xiàn)了超過4倍的內(nèi)存效率提高，只需要FM的1/4(對于Rogets和Snort來說)內(nèi)存，同時獲得1.4倍的每流吞吐量。與BS設(shè)計相比，本文設(shè)計只需要BS的1/51(對于Rogets)和1/26(對于Snort)的內(nèi)存，同時實現(xiàn)1.8倍的每流吞吐量。此外，本文設(shè)計的內(nèi)存效率和吞吐量不依賴于符號集(或字母表)的大小，而對于其他設(shè)計，當(dāng)符號集增大時，它們的性能會顯著下降。

5 結(jié)束語

本文針對大規(guī)模字符串的模式匹配提出了一種葉子-追加算法和二叉搜索樹的字符串匹配算法，它可以在不增加模式數(shù)量的情況下拆分給定的模式集，還提出了實現(xiàn)該算法的總體架構(gòu)；實驗結(jié)果表明，與目前先進(jìn)的設(shè)計相比，本文設(shè)計獲得了更好的內(nèi)存效率和吞吐量；在未來的研究中，我們打算改進(jìn)本文的算法，以在每個時鐘周期匹配多個字符，也進(jìn)一步研究標(biāo)簽匹配模塊的替代架構(gòu)。