所謂報(bào)文內(nèi)容過(guò)濾，顧名思義是對(duì)IP包數(shù)據(jù)段的載荷進(jìn)行過(guò)濾，過(guò)濾規(guī)則是字符串形式的數(shù)據(jù)內(nèi)容。以IDS系統(tǒng)為例，管理員根據(jù)所掌握的入侵情況事先為系統(tǒng)設(shè)定入侵規(guī)則，這些規(guī)則的一個(gè)重要組成部分就是IP數(shù)據(jù)載荷的某些內(nèi)容，具體表現(xiàn)為字符串。當(dāng)系統(tǒng)接收到一個(gè)IP包后，IDS的內(nèi)容過(guò)濾部分就會(huì)用自身的系統(tǒng)算法將規(guī)則庫(kù)中的字符串逐一和包的內(nèi)容匹配，一旦匹配了某個(gè)字符串，則證明匹配了相應(yīng)的規(guī)則。

隨著網(wǎng)絡(luò)信息復(fù)雜化以及安全需求多樣化，對(duì)報(bào)文內(nèi)容過(guò)濾的需求也更加迫切。首先從安全角度來(lái)看，防火墻和入侵監(jiān)測(cè)系統(tǒng)急需高效率的報(bào)文內(nèi)容過(guò)濾算法。由于當(dāng)今的入侵行為和攻擊方式更具有復(fù)雜性，主要表現(xiàn)在數(shù)據(jù)載荷的內(nèi)容中出現(xiàn)特征字符串，例如蠕蟲(chóng)病毒“Nimda”、“Code Red”、“Slammer”都包含特殊的字符串；從網(wǎng)絡(luò)應(yīng)用來(lái)看，應(yīng)用于深度報(bào)文分類的路由設(shè)備、流量控制等同樣需要獲得并且對(duì)IP數(shù)據(jù)內(nèi)容分類，例如一些多媒體數(shù)據(jù)、P2P數(shù)據(jù)都含有特定的字符串信息作為本身的標(biāo)識(shí)；另外從信息獲取的角度來(lái)看，技偵領(lǐng)域和數(shù)據(jù)挖掘如何從海量數(shù)據(jù)中發(fā)掘有用信息和情報(bào)資源，同樣需要內(nèi)容過(guò)濾。

1、內(nèi)容過(guò)濾的代表算法

1.1 AC算法

AC算法即由Aho和Corasick提出的多模式匹配算法（即一次搜索查找可以判定多個(gè)字符串匹配問(wèn)題）。簡(jiǎn)單地說(shuō)，AC 算法使用了有限自動(dòng)機(jī)的結(jié)構(gòu)來(lái)接收并存儲(chǔ)規(guī)則庫(kù)中所有的字符串。自動(dòng)機(jī)是結(jié)構(gòu)化的，這樣每個(gè)前綴都可用唯一的狀態(tài)來(lái)標(biāo)識(shí)，甚至是那些多個(gè)模式的前綴，這樣復(fù)雜的前綴就可以簡(jiǎn)單的轉(zhuǎn)化為狀態(tài)機(jī)中的一個(gè)狀態(tài)。當(dāng)文本T中下一個(gè)字符不是模式中預(yù)期的下個(gè)字符中的一個(gè)時(shí)，會(huì)有一條失敗鏈指向那個(gè)狀態(tài)，代表最長(zhǎng)的模式前綴，同時(shí)也是當(dāng)前狀態(tài)的相應(yīng)后綴。在實(shí)踐中，我們?cè)O(shè)定三個(gè)函數(shù)：狀態(tài)轉(zhuǎn)移函數(shù)goto（）、成功匹配輸出函數(shù)output（）、匹配失敗跳轉(zhuǎn)函數(shù)failure（）。

1.2 王的多模式匹配算法

王永成教授等人設(shè)計(jì)了更多關(guān)注了多模式匹配過(guò)程中字串之間的相互關(guān)系，對(duì)AC算法進(jìn)行了改進(jìn)0。算法在自動(dòng)狀態(tài)機(jī)思想的基礎(chǔ)上，應(yīng)用了BM算法0的跳轉(zhuǎn)思想，即利用了匹配過(guò)程中匹配失敗的信息，跳過(guò)盡可能多的字符。實(shí)現(xiàn)了快速的多模式匹配算法。在匹配的過(guò)程中，同樣使用goto（）函數(shù)轉(zhuǎn)移當(dāng)前狀態(tài)，在找到匹配結(jié)果之后output（）函數(shù)輸出成功信息。而在匹配失敗的時(shí)候，使用skip函數(shù)大幅度劃文本T，減少goto（）函數(shù)的調(diào)用次數(shù)，從而提高過(guò)濾效率。

1.3 Bloom Filter算法

Bloom Filter法最初多用于數(shù)據(jù)庫(kù)存儲(chǔ)和查詢結(jié)構(gòu)，近年來(lái)也應(yīng)用于IP包內(nèi)容過(guò)濾等領(lǐng)域。Bloom Filter算法的原理是找到k個(gè)hash函數(shù)，其值域都是{1，2，…，m}同時(shí)設(shè)定一個(gè)模式矢量M，其長(zhǎng)度為m。對(duì)于規(guī)則庫(kù)P中的每個(gè)模式，計(jì)算 hash1（p）、……、hashk（p） ，每次計(jì)算所得的 hashx（p）根據(jù)其數(shù)值對(duì)應(yīng)到模式矢量的相應(yīng)位置。這樣，一個(gè)模式經(jīng)過(guò)k個(gè)hash函數(shù)計(jì)算所得k個(gè)值，進(jìn)而對(duì)應(yīng)到模式矢量的k個(gè)位置，形成一個(gè)模式矢量。在查找的過(guò)程中，在文本中取出同p相同長(zhǎng)度的字符串，經(jīng)過(guò)k個(gè)hash函數(shù)計(jì)算后生成其相應(yīng)的模式矢量，用這個(gè)模式矢量和庫(kù)中的各個(gè)模式矢量比較，可以確定是否匹配。

1.4 Dharmapurikar的算法

Dharmapurikar 等人修改了基本的AC算法，并引入了Bloom filter，設(shè)計(jì)了基于硬件的匹配方案。該算法拓展了AC狀態(tài)機(jī)的輸入帶寬，從1byte擴(kuò)展到Gbyte。相應(yīng)的狀態(tài)機(jī)內(nèi)部對(duì)一個(gè)狀態(tài)變化也要判斷一組Gbyte的數(shù)據(jù)。而對(duì)于文本T尾部不足Gbyte的部分，采用并行的G-1個(gè)過(guò)濾單元，專用于過(guò)濾剩余長(zhǎng)度為1、2、……、G-1的部分。而在狀態(tài)轉(zhuǎn)移的過(guò)程中，使用了Bloom Filter過(guò)濾掉了不可能產(chǎn)生狀態(tài)轉(zhuǎn)移的輸入，極大地提高了匹配效率。而對(duì)于數(shù)量很少的狀態(tài)轉(zhuǎn)移操作，通過(guò)查找off-chip的存儲(chǔ)單元中的hash表來(lái)確定狀態(tài)轉(zhuǎn)移和相應(yīng)的匹配結(jié)果。本文在此基礎(chǔ)上作進(jìn)一步研究。

2、內(nèi)容過(guò)濾算法描述

2.1 算法的并行結(jié)構(gòu)

對(duì)于字符串匹配而言，一個(gè)匹配單元是1-byte，這樣一個(gè)匹配模塊一次的輸入為1byte。如果可以將輸入帶寬從1-byte拓展到G-byte的話那么過(guò)濾速率顯然也相應(yīng)的提高了G倍。

圖1 一個(gè)G=4的內(nèi)容過(guò)濾器

圖1以一個(gè)G=4的實(shí)例說(shuō)明了并行內(nèi)容過(guò)濾器的算法結(jié)構(gòu)。過(guò)濾器由四個(gè)完全相同的過(guò)濾模塊并行組成，其中每個(gè)模塊一次接收一定長(zhǎng)度（B）的字串，進(jìn)行過(guò)濾計(jì)算，下個(gè)周期接收下一組B長(zhǎng)的字串。而對(duì)于整個(gè)過(guò)濾器而言，每個(gè)周期流入Gbyte的數(shù)據(jù)，流出Gbyte的數(shù)據(jù)。以過(guò)濾模塊1為例，當(dāng)前窗口接收串為“abcde”，下一個(gè)周期窗口內(nèi)的串為“efghi”。雖然對(duì)于每個(gè)模塊而言，每次會(huì)改變G=4個(gè)字節(jié)，但是因?yàn)榇嬖诹瞬⑿械?個(gè)模塊，且每個(gè)模塊的判斷窗口都間隔1byte，這樣就不會(huì)漏掉數(shù)據(jù)流中的任何一個(gè)位置。如果規(guī)則集中含有字符串“cdefg”的話，那么顯然模塊3對(duì)當(dāng)前窗口過(guò)濾之后會(huì)給出一個(gè)匹配結(jié)果，而其他三個(gè)模塊都不會(huì)有匹配結(jié)果產(chǎn)生。這樣的并行結(jié)構(gòu)通過(guò)使用處理位置上相互比鄰的G個(gè)匹配模塊，解決了自動(dòng)狀態(tài)機(jī)模型中對(duì)于輸入字串1byte的限制，展寬了過(guò)濾帶寬，進(jìn)而提高了過(guò)濾速率。

2.2 匹配模塊的內(nèi)部結(jié)構(gòu)

圖1中的一個(gè)匹配模塊是一個(gè)獨(dú)立的內(nèi)容過(guò)濾單元，也是一個(gè)獨(dú)立的狀態(tài)機(jī)轉(zhuǎn)換單元。其內(nèi)部根據(jù)輸入的G-byte的字串計(jì)算狀態(tài)轉(zhuǎn)移以及匹配的命中結(jié)果。下面介紹一個(gè)匹配模塊的原理結(jié)構(gòu)。

圖2所示的是一個(gè)4byte寬的狀態(tài)機(jī)模型，狀態(tài)的每次轉(zhuǎn)移都需要4byte的數(shù)據(jù)（≤4）。例如，判斷S6=“elephant”，在當(dāng)前狀態(tài)q0的情況下，輸入串為“elep”時(shí)，狀態(tài)轉(zhuǎn)移q0—〉q4，接著輸入“hant”，狀態(tài)轉(zhuǎn)移到q7，此時(shí)有匹配的結(jié)果輸出。而普通的狀態(tài)機(jī)，需要8次的狀態(tài)轉(zhuǎn)移。

在過(guò)濾的過(guò)程中更多的規(guī)則串并不是B的倍數(shù)，例如“phone”，在第一次狀態(tài)轉(zhuǎn)移中由于“phon”的存在由q0轉(zhuǎn)移到q3，此后至需要判斷下個(gè)輸入中是不是后綴“e***”就可以判斷是否命中了s5，同樣還有“technically”中的后綴“l(fā)ly”等。對(duì)長(zhǎng)度為1到B-1之間的后綴，采用并行的B-1個(gè)后綴判斷子模塊。同時(shí)注意到對(duì)于長(zhǎng)度恰好是B的整數(shù)倍的規(guī)則串，可以理解成有一個(gè)長(zhǎng)度為0的后綴，這樣便于同上述并行的B-1個(gè)后綴判斷子模塊一同組成B個(gè)并行的運(yùn)算結(jié)構(gòu)。圖3給出了一個(gè)B=4的情況下的一個(gè)匹配模塊的結(jié)構(gòu)，其中4個(gè)Bloom Filter分別處理后綴長(zhǎng)度為0、1、2、3的情況。然后通過(guò)查表得到狀態(tài)轉(zhuǎn)移關(guān)系以及結(jié)果輸出情況。

圖2 一個(gè)4byte寬（B=4）的狀態(tài)機(jī)

圖3 B=4情況下的一個(gè)匹配模塊

2.3 使用Bloom Filter

如前文所述，由于狀態(tài)轉(zhuǎn)移表占用很大的存儲(chǔ)空間，需要使用off-chip的RAM來(lái)保存。而通常情況下外部存儲(chǔ)器的讀取帶寬很小，不能支持一個(gè)模塊的B個(gè)查表要求。其實(shí)在真實(shí)情況中只有很少的情況下才會(huì)有狀態(tài)的轉(zhuǎn)換，這時(shí)使用Bloom Filter來(lái)濾掉大量的不會(huì)產(chǎn)生狀態(tài)變化的輸入。一個(gè)狀態(tài)轉(zhuǎn)移關(guān)系可以表示成：

《當(dāng)前狀態(tài)，輸入字串》 ==〉《下個(gè)狀態(tài)，輸出信息》

所以可以對(duì)2元組《當(dāng)前狀態(tài)，輸入字串》進(jìn)行hash運(yùn)算，用結(jié)果搜索狀態(tài)轉(zhuǎn)移hash表，找到2元組《下個(gè)狀態(tài)，輸出信息》。Bloom Filter的作用就是濾掉大量不會(huì)查找到結(jié)果的元組，只在當(dāng)前《當(dāng)前狀態(tài)，輸入字串》有可能在hash表中查到結(jié)果的時(shí)候才允許對(duì)應(yīng)項(xiàng)查找狀態(tài)轉(zhuǎn)移表。這樣極大地減少了查表次數(shù)，提高了算法速率。

2.4 Hash函數(shù)的硬件實(shí)現(xiàn)方法

對(duì)于Bloom Filter中使用的hash函數(shù)，要求易于硬件，占用盡可能少的時(shí)鐘周期。H3算法提供了一個(gè)很好的解決方案。設(shè)子串的第i個(gè)字節(jié)為《bi1、bi2、……、bi8》，則這個(gè)位置上的一個(gè)hash值為：

hi=di1?bi1⊕di2?bi2⊕……⊕di8?bi8

其中dij是一個(gè)預(yù)設(shè)的隨機(jī)矩陣的一個(gè)值。這樣，從1到i的hash值為：

Hi=Hi-1⊕hi

可見(jiàn)，位置i上的hash函數(shù)可以通過(guò)i-1位置上的hash函數(shù)簡(jiǎn)單的算出。并且如果dij=di+1j的話，可見(jiàn)t時(shí)刻的hi和t+1時(shí)刻的hi-1是相同的，這樣所有Hi就可以通過(guò)并行的移位結(jié)構(gòu)在一個(gè)時(shí)鐘周期內(nèi)完成，而不用等待Hi-1的計(jì)算結(jié)果。相應(yīng)的結(jié)構(gòu)如圖4所示，算法可以在一個(gè)時(shí)鐘周期內(nèi)算出所有Hi的值，非常便捷。

圖4 硬件Hash函數(shù)的邏輯結(jié)構(gòu)

3、FPGA實(shí)現(xiàn)

本文的實(shí)驗(yàn)系統(tǒng)使用的是Altera公司StratixII系列的EP2S60FPGA芯片。該芯片擁有2.5Mb的片內(nèi)RAM空間，可以支持最多兩個(gè)獨(dú)立off-chip的DDR或QDR單元。輸入信號(hào)是經(jīng)過(guò)前端處理的POS信號(hào)，解為整載的IP報(bào)文數(shù)據(jù)。規(guī)則隨機(jī)地取自IDS系統(tǒng)SNORT的2000條規(guī)則。

在實(shí)現(xiàn)的過(guò)程中使用8個(gè)并行的過(guò)濾模塊，也就是每次輸入8byte的數(shù)據(jù)。雖然更高的并行數(shù)量會(huì)提高系統(tǒng)的處理帶寬，但是也相應(yīng)需要占用更多的RAM空間，這里考慮到SNORT的規(guī)則相對(duì)較短（多分布在5-15byte），采用8byte并行的算法。Bloom Filter由6個(gè)并行的hash函數(shù)構(gòu)成，每個(gè)hash函數(shù)對(duì)應(yīng)的hash表采用2kbit，這樣一共占用了2kbit*6*8*8=768kbit的片內(nèi)RAM資源，約占總量的30%。經(jīng)過(guò)計(jì)算，這樣的Bloom Filter設(shè)計(jì)可以保證經(jīng)過(guò)過(guò)濾操作之后，只有6e-10的假匹配存在（即對(duì)應(yīng)的hash值表明當(dāng)前元組《當(dāng)前狀態(tài)，輸入字串》可以產(chǎn)生正確的狀態(tài)轉(zhuǎn)移，然而在off-chip的RAM中找不到對(duì)應(yīng)項(xiàng)）。這里需要提一下，由于8個(gè)并行模塊是同構(gòu)的，其hash表也是相同的，如果使用時(shí)分的hash表查找方法或者Lucent memory core可以占用更少的RAM資源。

當(dāng)實(shí)驗(yàn)系統(tǒng)FPGA工作在77MHz的情況下的時(shí)候，可以正確無(wú)誤的過(guò)濾2.5Gpbs的IP報(bào)文數(shù)據(jù)。由于該算法使用的RAM和時(shí)鐘頻率都沒(méi)有達(dá)到額定值，同時(shí)，內(nèi)部Bloom Filter和狀態(tài)轉(zhuǎn)移表的構(gòu)成同樣有待進(jìn)一步優(yōu)化，所以本文算法具有進(jìn)一步升級(jí)的潛力。

4、結(jié)論

本文針對(duì)目前網(wǎng)絡(luò)傳播速率急劇增加，數(shù)據(jù)處理規(guī)則規(guī)模龐大的特點(diǎn)，提出了基于FPGA的IP報(bào)文內(nèi)容過(guò)濾算法。本文在當(dāng)前多種優(yōu)秀的內(nèi)容過(guò)濾技術(shù)的基礎(chǔ)上，充分利用了FPGA芯片高速并行處理和流水線操作的特點(diǎn)，提出使用并行的移位模塊來(lái)拓展過(guò)濾算法的處理帶寬，使得算法支持的IP報(bào)文速率得到了很大的提高。同時(shí)，為解決off-chip的RAM讀取帶寬受限的瓶頸，以及在狀態(tài)轉(zhuǎn)移過(guò)程中讀取下一個(gè)狀態(tài)需要占用額外的時(shí)鐘周期的問(wèn)題，提出了用Bloom Filter過(guò)濾掉不會(huì)產(chǎn)生狀態(tài)轉(zhuǎn)移的輸入字串，進(jìn)一步提高處理速率。另外，設(shè)計(jì)了僅需要一個(gè)時(shí)鐘周期就可以完成hash計(jì)算的硬件電路，并且通過(guò)改進(jìn)，可以在一個(gè)時(shí)鐘周期內(nèi)得到所有后綴長(zhǎng)度的hash值，使得算法在FPGA中的流水性能增強(qiáng)。最后通過(guò)在實(shí)驗(yàn)系統(tǒng)中的測(cè)試，在77MHz的時(shí)鐘下可以正確的過(guò)濾2.5Gbps的IP報(bào)文，并且有進(jìn)一步升級(jí)的潛力。

責(zé)任編輯：gt