劉仲會(huì)，許芳奎，許紅光

（1.天津電子信息職業(yè)技術(shù)學(xué)院，天津 300350；2.北京理工大學(xué)，北京 100081）

0 引言

VanDyke 軟件［1］公布的與安全相關(guān)的調(diào)查結(jié)果表明，盡管病毒是受調(diào)查者面臨的最大威脅，但66%的用戶(hù)選擇了系統(tǒng)滲入作為最大威脅；調(diào)查還顯示，采用普通防火墻來(lái)阻止可疑流量時(shí)并不總是有效；隨著黑客攻擊和網(wǎng)絡(luò)蠕蟲(chóng)開(kāi)始影響互聯(lián)網(wǎng)，網(wǎng)絡(luò)入侵防御系統(tǒng)（Network Intrusion Prevention Systems，NIPS）就被開(kāi)發(fā)用于識(shí)別和報(bào)告攻擊。

NIPS 系統(tǒng)通常由2 個(gè)主要組件構(gòu)成：一個(gè)模式匹配引擎和一個(gè)補(bǔ)充數(shù)據(jù)包分類(lèi)引擎。模式匹配引擎的輸入是一個(gè)數(shù)據(jù)包，其輸出是一組匹配模式，屬于已知攻擊簽名集合。字符串匹配算法是NIPS的主要構(gòu)建模塊。大多數(shù)算法要么太復(fù)雜而無(wú)法在硬件中實(shí)現(xiàn)，要么有較差的性能［2-8］；文獻(xiàn)［9］提出了一種改進(jìn)的多模式匹配HSBOM 算法。該算法在預(yù)處理過(guò)程中建立哈希表代替SBOM 算法的Factor Oracle 自動(dòng)機(jī)來(lái)存儲(chǔ)模式集中的所有子串信息，大幅度減少算法占用的存儲(chǔ)空間；文獻(xiàn)［10］針對(duì)經(jīng)典多模式匹配算法中的正則表達(dá)式確定有限自動(dòng)機(jī)（Deterministic Finite Automata，DFA）匹配的缺點(diǎn)，提出對(duì)規(guī)則進(jìn)行預(yù)處理，將相同類(lèi)似的規(guī)則分成同一組，減少生成DFA 的總個(gè)數(shù)和構(gòu)造DFA 的時(shí)間。結(jié)果表明，對(duì)系統(tǒng)規(guī)則的匹配速度以及減少內(nèi)存使用方面均有較大的提高；文獻(xiàn)［11］提出了一種基于流量分析算法的網(wǎng)絡(luò)入侵模式特征對(duì)比方法。實(shí)驗(yàn)結(jié)果表明，算法提升了網(wǎng)絡(luò)入侵檢測(cè)效率；文獻(xiàn)［12-13］提出了并行Bloom 濾波器算法，對(duì)每個(gè)可能的模式長(zhǎng)度，采用一個(gè)Bloom 濾波器，通過(guò)采用4 個(gè)并行引擎來(lái)得到一個(gè)合理的成本-空間之間的權(quán)衡；文獻(xiàn)［14］提出了一種基于移位的算法。算法采用基于內(nèi)存的哈希引擎網(wǎng)絡(luò)處理器和長(zhǎng)度為w 的前綴滑動(dòng)窗口，并采用一個(gè)大小為（28）w的移位表；三態(tài)內(nèi)容尋址存儲(chǔ)器（Ternary Content Addressable Memory，TCAM）［15］是一種先進(jìn)的存儲(chǔ)芯片，每個(gè)bit 位可以存儲(chǔ)3 個(gè)值：0、1 和“don’t care”，正是這個(gè)第3 種狀態(tài)特征，使其既能進(jìn)行精確匹配查找，又能進(jìn)行模糊匹配查找。在最新的模式匹配算法中，采用TCAM 的是文獻(xiàn)［16］提出的模式匹配算法。該算法在TCAM 中放置攻擊簽名集并置入一個(gè)簡(jiǎn)單的“窮舉法”模式匹配算法，從數(shù)據(jù)包連續(xù)構(gòu)建一個(gè)w 字節(jié)長(zhǎng)的關(guān)鍵字，同時(shí)TCAM 查找一個(gè)匹配。

本文針對(duì)NIPS 系統(tǒng)中的核心部件——模式匹配組件，提出了一種新的基于TCAM 的旋轉(zhuǎn)TCAM（Rotating TCAM，RTCAM）模式匹配算法。它不僅支持現(xiàn)有的TCAM 使用和一些可以用硬件實(shí)現(xiàn)的額外邏輯，而且能夠使NIPS 系統(tǒng)在線工作在幾千兆比特每秒的總速率來(lái)實(shí)現(xiàn)對(duì)惡意流量數(shù)據(jù)包的有效檢測(cè)，相比于現(xiàn)有的基于TCAM 的模式匹配算法，還能大大減少內(nèi)存訪問(wèn)和TCAM 查找訪問(wèn)。

1 預(yù)備知識(shí)

1.1 Snort 數(shù)據(jù)庫(kù)

Snort［3］是一個(gè)開(kāi)源NIPS，常用于工業(yè)領(lǐng)域，它是一個(gè)包含有數(shù)千個(gè)攻擊簽名的規(guī)則數(shù)據(jù)庫(kù)。在內(nèi)部，Snort 采用一種基于軟件的模式匹配算法，應(yīng)用一個(gè)關(guān)鍵字集，這個(gè)關(guān)鍵字集保存在一個(gè)類(lèi)似于關(guān)鍵字樹(shù)的Aho-Corassick 中。

1.2 符號(hào)和定義

定義1 一個(gè)模式P 定義為來(lái)自于一個(gè)字母表∑的一組字符串，它需要在輸入的文本內(nèi)被識(shí)別。一個(gè)子模式Ps定義為一個(gè)模式P 的一個(gè)子字符串。

定義2 一個(gè)搜索窗口定義為輸入文本的一部分，其中的一個(gè)子模式被搜索。

定義3 一個(gè)移位值定義為算法可以安全跳過(guò)而不會(huì)丟失任何模式匹配的字節(jié)數(shù)。從形式上來(lái)說(shuō)，如果0≤s≤n-m 且T［s+1，…，s+m］=P［1，…，m］，則長(zhǎng)度為m 的模式P 在長(zhǎng)度為n 的文本T 中發(fā)生移位s。

定義4 一個(gè)字符串匹配算法定義如下：定義文本為一個(gè)數(shù)組T［1，…，n］，定義模式為一個(gè)數(shù)組P［1，…，m］，并假設(shè)P 和T 的元素為從一個(gè)有限的字母表∑中抽取出來(lái)的字符。字符串匹配問(wèn)題就是尋找移位的問(wèn)題。在一個(gè)給定的文本中尋找多個(gè)模式的擴(kuò)展問(wèn)題稱(chēng)為“多模式匹配”，其目標(biāo)是輸出文本中所有模式出現(xiàn)的位置。本文構(gòu)建多模式字符串匹配問(wèn)題如下：T=t［1，...，n］和r 個(gè)模式的一個(gè)集合P，使得Pj∈P，其中1≤j≤r（模式可以有不同的長(zhǎng)度）。

2 旋轉(zhuǎn)TCAM 算法

2.1 旋轉(zhuǎn)TCAM 算法原理

一個(gè)大小為M 的TCAM，可以構(gòu)建為有「M/w?行，w 是TCAM 的寬度。TCAM 是駐留在脫機(jī)過(guò)程的2個(gè)階段。在第1 階段，將規(guī)則簽名（模式）進(jìn)行劃分，以適合所選擇的w。比w 長(zhǎng)的模式占據(jù)1 行以上，第1 行的模式標(biāo)記為“模式前綴”，把標(biāo)記為前綴的那些短模式通過(guò)采用TCAM 的“don’t care”位填充為w 的大小。每個(gè)TCAM 行有一個(gè)對(duì)應(yīng)的移位值，這個(gè)移位值表示當(dāng)匹配發(fā)生時(shí)，可以在數(shù)據(jù)包中安全移位的字節(jié)數(shù)。在這個(gè)階段，全部TCAM 行的移位值為0；在下一個(gè)階段，通過(guò)將前綴向右移，丟棄最右端的字符并在左邊添加“don’t care”，為每個(gè)模式前綴創(chuàng)建一組移位子模式。這樣旋轉(zhuǎn)使移位值增加1，故稱(chēng)為旋轉(zhuǎn)TCAM（Rotating TCAM，RTCAM）。重復(fù)這樣的過(guò)程，直至全部模式的字節(jié)都是“don’t care”。由于TCAM 查找返回第1 個(gè)匹配的行，故TCAM 行是根據(jù)它們的移位值按升序排序的，最后的行對(duì)應(yīng)最大的移位值，且包含w 個(gè)“don’t care”字節(jié)，從而提供默認(rèn)的匹配行。

2.2 旋轉(zhuǎn)TCAM 算法的實(shí)現(xiàn)描述

本節(jié)給出RTCAM 算法的具體實(shí)現(xiàn)描述。算法運(yùn)行3 步或4 步：（i） 從位置position=pos（初始pos=0）的數(shù)據(jù)包構(gòu)造大小為w 的關(guān)鍵字；（ii）調(diào)用TCAM 查找并得到匹配的行；（iii）返回相應(yīng)的行移位（shift）值。一個(gè)大于0 的移位值表示沒(méi)有一個(gè)模式匹配給定的關(guān)鍵字，可以用position=position+shift重復(fù)步驟（i）。一個(gè)為0 的shift 值意味著一個(gè)前綴模式匹配了關(guān)鍵字，并調(diào)用步驟（iv）。這一步驟查詢(xún)內(nèi)部數(shù)據(jù)結(jié)構(gòu)來(lái)定位潛在的攻擊模式。如果匹配的模式小于關(guān)鍵字的大?。╳），則出現(xiàn)簡(jiǎn)單的情況，這時(shí)，將相關(guān)的模式添加到專(zhuān)用的“匹配模式列表”中，并用position=position+1 調(diào)用步驟（i）；如果模式是部分匹配（即它匹配一個(gè)較長(zhǎng)模式的前綴），則模式的剩余部分也應(yīng)當(dāng)被匹配，一種方法是采用內(nèi)存指令比較數(shù)據(jù)包和模式的其余部分，更快的方法是再次采用TCAM 來(lái)減少內(nèi)存訪問(wèn)延遲。步驟（iv）通過(guò)將它分割成幾個(gè)w 長(zhǎng)的子模式并用TCAM 迭代查找，多次使用TCAM 來(lái)匹配模式的剩余部分。這個(gè)操作是在特定規(guī)則（模式所屬的規(guī)則）的環(huán)境中執(zhí)行的。只有當(dāng)全部TCAM 匹配的行對(duì)應(yīng)于0 移位值時(shí)，該模式才可以被標(biāo)記為完全匹配，否則，用position+1 再次調(diào)用步驟（i）。算法實(shí)現(xiàn)過(guò)程的偽代碼如算法1 所示。

2.3 算法中的數(shù)據(jù)結(jié)構(gòu)

2.3.1 模式列表

在算法的步驟（iv）中訪問(wèn)模式列表數(shù)據(jù)結(jié)構(gòu)，用于比較一個(gè)模式的后綴與數(shù)據(jù)包內(nèi)容。一個(gè)模式列表記錄（entry）包含幾個(gè)字段，保存有需要實(shí)現(xiàn)各種Snort 關(guān)鍵字的信息：1）len：模式長(zhǎng)度；2）root：是一個(gè)布爾值，表明這種模式是否是一個(gè)規(guī)則的第一個(gè)模式；3）offset：表明模式應(yīng)當(dāng)從數(shù)據(jù)包的哪里搜索；4）distance：兩個(gè)連續(xù)匹配（即先前模式匹配和當(dāng)前模式匹配）之間允許的最小字節(jié)數(shù)；5）within：兩個(gè)連續(xù)模式匹配之間允許的最大字節(jié)數(shù)；6）depth：對(duì)于指定模式，算法應(yīng)當(dāng)搜索數(shù)據(jù)包多遠(yuǎn)；7）TCAM_Ptrs：TCAM 引用數(shù)組，用于算法的步驟（iv）。

2.3.2 TCAM 規(guī)則表

該表將一個(gè)TCAM 行和模式列表之間關(guān)聯(lián)起來(lái)。每個(gè)表記錄包含移位值、一個(gè)包含（inclusion）模式列表和一個(gè)關(guān)聯(lián)（association）模式列表。當(dāng)一個(gè)TCAM 匹配發(fā)生時(shí)，將匹配的TCAM 行內(nèi)容與包含匹配行的模式集相關(guān)聯(lián)作為它們的前綴。包含模式列表用于識(shí)別小于w 的模式，它們是匹配模式（TCAM 行）的前綴。

2.3.3 匹配模式列表該列表保存當(dāng)前處理數(shù)據(jù)包的匹配模式，每個(gè)記錄包含匹配模式及其在數(shù)據(jù)包中相應(yīng)的結(jié)束位置。

2.3.4 規(guī)則列表規(guī)則列表在一個(gè)規(guī)則及其對(duì)應(yīng)模式之間進(jìn)行映射。

2.4 算法實(shí)例及NIPS 中的數(shù)據(jù)包流

用下頁(yè)圖1 所示的實(shí)例來(lái)闡明RTCAM 算法的具體操作過(guò)程。假設(shè)TCAM 的寬度為4，輸入的數(shù)據(jù)包是“wwabcdeftxyzabcdarp”，我們來(lái)尋找在表1 中出現(xiàn)的規(guī)則。

表1 Snort 規(guī)則示例

在階段0，匹配模式列表是空的。

首先搜索位置0 的數(shù)據(jù)包。第1 個(gè)關(guān)鍵字是wwab（數(shù)據(jù)包的前4 個(gè)字節(jié)），TCAM 查找返回??ab記錄，且移位值是2。數(shù)據(jù)內(nèi)包的關(guān)鍵字位置然后增加2。接下來(lái)的關(guān)鍵字是abcd，采用這個(gè)關(guān)鍵字的查找匹配第1 個(gè)TCAM 記錄，且相應(yīng)的移位值為0?，F(xiàn)在調(diào)用算法步驟（iv），并使用關(guān)聯(lián)指針來(lái)比較完整模式和數(shù)據(jù)包的內(nèi)容。第1 個(gè)關(guān)聯(lián)指針指向包含模式abcdef 的節(jié)點(diǎn)。該模式?jīng)]有offset 或depth，因此，沒(méi)有位置限制，模式的長(zhǎng)度為6，故算法取接下來(lái)的2 個(gè)字節(jié)并采用關(guān)鍵字cdef（加上來(lái)自于先前查找的最后2 個(gè)字節(jié)）執(zhí)行一個(gè)TCAM 查找。這個(gè)關(guān)鍵字也得到0 作為移位值，而且TCAM 記錄的指標(biāo)出現(xiàn)在TCAM_Ptrs 數(shù)組中。算法尋找到一個(gè)匹配，并將該模式添加到匹配模式列表中。算法還打開(kāi)規(guī)則記錄位圖中的模式位。關(guān)鍵字abcd 的關(guān)聯(lián)列表中的下一個(gè)指針指向包含abcdarp 模式（該模式不匹配數(shù)據(jù)包內(nèi)容，查找關(guān)鍵字darp 失?。┑墓?jié)點(diǎn)。

現(xiàn)在，算法采用包含列表并檢查模式數(shù)2。由于對(duì)offset 值的約束是8，而當(dāng)前的位置是2，故算法不匹配這個(gè)模式。算法對(duì)數(shù)據(jù)包內(nèi)的搜索位置增加1，并構(gòu)建搜索關(guān)鍵字bcde。這個(gè)關(guān)鍵字匹配最后的TCAM 記錄，所以移位值為4，因而下一個(gè)關(guān)鍵字為ftxy。在兩個(gè)查找操作內(nèi)，關(guān)鍵字xyza 得到一個(gè)為0的移位值。

算法再次采用關(guān)聯(lián)指針，這時(shí)，關(guān)聯(lián)指針包含模式xyz。由于這不是root 模式，故算法檢查先前模式的匹配模式列表。先前模式出現(xiàn)在列表中，且它的結(jié)束位置是7。xyz 模式的內(nèi)部值為5，它的長(zhǎng)度為3，且當(dāng)前位置為9。算法確認(rèn)9+3≤7+5+1，因而匹配模式被插入到匹配模式列表中。算法還采用規(guī)則記錄位圖設(shè)置模式位。由于位圖中的全部位被設(shè)置，算法就可以“宣布”一個(gè)攻擊。最后，數(shù)據(jù)包中的搜索位置被移位1。

兩個(gè)查找得到一個(gè)具有移位值為0 的匹配關(guān)鍵字abcd。算法再一次采用關(guān)聯(lián)指針，第一個(gè)節(jié)點(diǎn)包含模式abcdef。由于關(guān)鍵字cdar 的查找得到一個(gè)大于0 的移位值，故得到該模式不匹配，并繼續(xù)下一個(gè)關(guān)聯(lián)指針（abcdarp）。depth 值為25，當(dāng)前位置為11，模式長(zhǎng)度為7。算法檢查11+7≤25。由于模式長(zhǎng)度為7（大于w），故算法取下一個(gè)字節(jié)并用關(guān)鍵字darp 調(diào)用TCAM。這個(gè)關(guān)鍵字得到0 作為移位值，且TCAM 記錄的指標(biāo)在TCAM_Ptrs 數(shù)組中，所以算法把該模式添加到模式匹配列表中，并采用規(guī)則設(shè)置對(duì)應(yīng)于該模式的位。由于這是規(guī)則中唯一的模式，所以算法觸發(fā)一個(gè)攻擊警報(bào)。

算法繼續(xù)掃描數(shù)據(jù)包作為進(jìn)一步的攻擊檢測(cè)，直至整個(gè)數(shù)據(jù)包被分析完。

圖1 算法示例

當(dāng)然，在執(zhí)行算法時(shí)，還要考慮最壞情況下的性能以及窗口大小。在前者中，對(duì)算法可以引入一個(gè)簡(jiǎn)單的預(yù)處理階段，將每個(gè)長(zhǎng)模式轉(zhuǎn)換成一組短模式（每個(gè)短模式的長(zhǎng)度等于或小于w），然后采用distance 和within 關(guān)鍵字把這些短模式關(guān)聯(lián)起來(lái)；在后者中，需要對(duì)RTCAM 內(nèi)存需求進(jìn)行計(jì)算?？傊x擇w 是一個(gè)在成本和性能之間的權(quán)衡。

3 算法實(shí)驗(yàn)結(jié)果

為了對(duì)算法的性能進(jìn)行評(píng)價(jià)，采用2 個(gè)模式集來(lái)進(jìn)行仿真測(cè)試。第1 個(gè)測(cè)試集是來(lái)自于ClamAV的病毒簽名集［17］，它僅包含簡(jiǎn)單的模式（比較長(zhǎng)），第2 個(gè)測(cè)試集來(lái)自于從Snort［18］工具的入侵檢測(cè)簽名構(gòu)成，這些大多數(shù)簽名由相關(guān)模式構(gòu)成；用幾個(gè)不同的TCAM 寬度來(lái)仿真基于本文提出的旋轉(zhuǎn)TCAM匹配算法，并將本文提出的旋轉(zhuǎn)TCAM 匹配算法與文獻(xiàn)［16］同樣基于TCAM 的匹配算法進(jìn)行比較。

3.1 ClamAV 模式集的仿真結(jié)果

ClamAV 的0.82 版有26 986 個(gè)簡(jiǎn)單模式，其平均模式長(zhǎng)度為124.1。當(dāng)在ClamAV 數(shù)據(jù)庫(kù)上運(yùn)行本文的NIPS 時(shí)，得到的性能結(jié)果如表2 所示。

表2 TCAM 寬度對(duì)平均移位值的影響（ClamAV 模式集）

可見(jiàn)，隨著TCAM 寬度的增大，TCAM 內(nèi)存大小需求和平均移位值會(huì)隨之增大。

3.2 Snort 模式集的仿真結(jié)果

Snort 模式包含許多短模式（≤4）。在大多數(shù)情況下，這些模式是關(guān)聯(lián)規(guī)則的一部分。因此，除了模式本身外，可通過(guò)加入更多信息到每個(gè)TCAM 行來(lái)消除TCAM 匹配。如創(chuàng)建一個(gè)哈希函數(shù)h，它的輸入是額外的數(shù)據(jù)D，輸出是關(guān)鍵字k，即h（D）=k。把k加入到TCAM 的每個(gè)記錄中；為主協(xié)議添加1 個(gè)字節(jié)的位圖和另一個(gè)表示與該模式相關(guān)聯(lián)的最低端口和最高端口范圍的值。采用這種擴(kuò)展，得到如表3 所示的對(duì)于每個(gè)不同TCAM 寬度的TCAM 內(nèi)存大小需求和移位平均值，對(duì)照表2 可見(jiàn)，在短模式的情況下，盡管這些模式是關(guān)聯(lián)規(guī)則的一部分，但明顯得到了更好的結(jié)果。

下面來(lái)比較本文提出的算法和文獻(xiàn)［16］提出的算法在TCAM 查找訪問(wèn)和內(nèi)存訪問(wèn)（SRAM 訪問(wèn)）兩方面的性能。圖2（a）所示為2 種算法在不同TCAM 寬度時(shí)的內(nèi)存訪問(wèn)數(shù)量與數(shù)據(jù)包長(zhǎng)度之間的關(guān)系曲線，圖2（b）所示為2 種算法在不同TCAM 寬度時(shí)所需要的TCAM 查找訪問(wèn)數(shù)量與與數(shù)據(jù)包長(zhǎng)度之間的關(guān)系曲線。從圖2 可見(jiàn)，盡管文獻(xiàn)［16］提出的算法在TCAM 調(diào)用時(shí)并不一定需要內(nèi)存調(diào)用，而本文提出的算法在每次TCAM 調(diào)用時(shí)需調(diào)用內(nèi)存來(lái)得到移位值，但本文的算法相比于文獻(xiàn)［16］的解決方案來(lái)說(shuō)，調(diào)用TCAM 的次數(shù)明顯減少，即使本文算法對(duì)于每次TCAM 調(diào)用都要調(diào)用內(nèi)存，但內(nèi)存調(diào)用的總數(shù)量也明顯少于文獻(xiàn)［16］的解決方案，所以本文的算法明顯優(yōu)于文獻(xiàn)［16］的算法。

圖2 2 種算法的內(nèi)存訪問(wèn)和TCAM 查找訪問(wèn)性能比較

4 結(jié)論

本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)完整的NIPS 系統(tǒng)中的模式匹配組件，它基于一種新的模式匹配算法——旋轉(zhuǎn)TCAM 算法，對(duì)于實(shí)際網(wǎng)絡(luò)流量，可以獲得較高的平均線速度，而且完全兼容Snort 的規(guī)則語(yǔ)法。

對(duì)于未來(lái)的研究，準(zhǔn)備采用FPGA 和基于哈希算法來(lái)實(shí)現(xiàn)模式匹配，并將它和基于RTCAM 解決方案的性能進(jìn)行比較。