一種基于FPGA的報文內(nèi)容過濾算法

1、一種基于FPGA的報文內(nèi)容過濾算法         摘  要  報文內(nèi)容過濾技術是防火墻、入侵檢測系統(tǒng)和情報信息綜合系統(tǒng)的重要技術之一。本文提出的算法充分發(fā)揮了硬件并行運算和流水線的優(yōu)勢，采用并行移位的匹配模塊結構展寬了處理帶寬，使用Bloom Filter技術加速自動狀態(tài)機轉換，同時設計了高效的Hash硬件電路，提高了算法性能。實驗證明該算法可以穩(wěn)定的過濾2.5Gbps的IP報文數(shù)據(jù)。    關鍵字  報文內(nèi)容過濾；FPGA；Bloom Filter；自

2、動狀態(tài)機   所謂報文內(nèi)容過濾，顧名思義是對IP包數(shù)據(jù)段的載荷進行過濾，過濾規(guī)則是字符串形式的數(shù)據(jù)內(nèi)容。以IDS系統(tǒng)為例，管理員根據(jù)所掌握的入侵情況事先為系統(tǒng)設定入侵規(guī)則，這些規(guī)則的一個重要組成部分就是IP數(shù)據(jù)載荷的某些內(nèi)容，具體表現(xiàn)為字符串。當系統(tǒng)接收到一個IP包后，IDS的內(nèi)容過濾部分就會用自身的系統(tǒng)算法將規(guī)則庫中的字符串逐一和包的內(nèi)容匹配，一旦匹配了某個字符串，則證明匹配了相應的規(guī)則。   隨著網(wǎng)絡信息復雜化以及安全需求多樣化，對報文內(nèi)容過濾的需求也更加迫切。首先從安全角度來看，防火墻和入侵監(jiān)測系統(tǒng)急需高效率的報文內(nèi)容過濾算法。由于當今的入侵行為和

3、攻擊方式更具有復雜性，主要表現(xiàn)在數(shù)據(jù)載荷的內(nèi)容中出現(xiàn)特征字符串，例如蠕蟲病毒“Nimda”、“Code Red”、“Slammer”都包含特殊的字符串；從網(wǎng)絡應用來看，應用于深度報文分類的路由設備、流量控制等同樣需要獲得并且對IP數(shù)據(jù)內(nèi)容分類，例如一些多媒體數(shù)據(jù)、P2P數(shù)據(jù)都含有特定的字符串信息作為本身的標識；另外從信息獲取的角度來看，技偵領域和數(shù)據(jù)挖掘如何從海量數(shù)據(jù)中發(fā)掘有用信息和情報資源，同樣需要內(nèi)容過濾。1  內(nèi)容過濾的代表算法1.1  AC算法   AC算法即由Aho和Corasick提出的多模式匹配算法（即一次搜索查找可以判定多個字符串匹配問題

4、）。簡單地說，AC 算法使用了有限自動機的結構來接收并存儲規(guī)則庫中所有的字符串。自動機是結構化的，這樣每個前綴都可用唯一的狀態(tài)來標識，甚至是那些多個模式的前綴，這樣復雜的前綴就可以簡單的轉化為狀態(tài)機中的一個狀態(tài)。當文本T中下一個字符不是模式中預期的下個字符中的一個時，會有一條失敗鏈指向那個狀態(tài)，代表最長的模式前綴，同時也是當前狀態(tài)的相應后綴。在實踐中，我們設定三個函數(shù)：狀態(tài)轉移函數(shù)goto（）、成功匹配輸出函數(shù)output（）、匹配失敗跳轉函數(shù)failure（）。1.2  王的多模式匹配算法   王永成教授等人設計了更多關注了多模式匹配過程中字串之間的相互關系，對

5、AC算法進行了改進0。算法在自動狀態(tài)機思想的基礎上，應用了BM算法0的跳轉思想，即利用了匹配過程中匹配失敗的信息，跳過盡可能多的字符。實現(xiàn)了快速的多模式匹配算法。在匹配的過程中，同樣使用goto（）函數(shù)轉移當前狀態(tài)，在找到匹配結果之后output（）函數(shù)輸出成功信息。而在匹配失敗的時候，使用skip函數(shù)大幅度劃文本T，減少goto（）函數(shù)的調用次數(shù)，從而提高過濾效率。1.3  Bloom Filter算法   Bloom Filter法最初多用于數(shù)據(jù)庫存儲和查詢結構，近年來也應用于IP包內(nèi)容過濾等領域。Bloom Filter算法的原理是找到k個hash函數(shù)，其值

6、域都是1，2，m同時設定一個模式矢量M，其長度為m。對于規(guī)則庫P中的每個模式，計算 hash1（p）、hashk（p） ，每次計算所得的 hashx（p）根據(jù)其數(shù)值對應到模式矢量的相應位置。這樣，一個模式經(jīng)過k個hash函數(shù)計算所得k個值，進而對應到模式矢量的k個位置，形成一個模式矢量。在查找的過程中，在文本中取出同p相同長度的字符串，經(jīng)過k個hash函數(shù)計算后生成其相應的模式矢量，用這個模式矢量和庫中的各個模式矢量比較，可以確定是否匹配。1.4  Dharmapurikar的算法   Dharmapurikar 等人修改了基本的AC算法，并引入了Bloom fi

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

8、0; 對于字符串匹配而言，一個匹配單元是1-byte，這樣一個匹配模塊一次的輸入為1byte。如果可以將輸入帶寬從1-byte拓展到G-byte的話那么過濾速率顯然也相應的提高了G倍。圖1  一個G=4的內(nèi)容過濾器   圖1以一個G=4的實例說明了并行內(nèi)容過濾器的算法結構。過濾器由四個完全相同的過濾模塊并行組成，其中每個模塊一次接收一定長度（B）的字串，進行過濾計算，下個周期接收下一組B長的字串。而對于整個過濾器而言，每個周期流入Gbyte的數(shù)據(jù)，流出Gbyte的數(shù)據(jù)。以過濾模塊1為例，當前窗口接收串為“abcde”，下一個周期窗口內(nèi)的串為“efghi”。雖然對于

9、每個模塊而言，每次會改變G=4個字節(jié)，但是因為存在了并行的4個模塊，且每個模塊的判斷窗口都間隔1byte，這樣就不會漏掉數(shù)據(jù)流中的任何一個位置。如果規(guī)則集中含有字符串“cdefg”的話，那么顯然模塊3對當前窗口過濾之后會給出一個匹配結果，而其他三個模塊都不會有匹配結果產(chǎn)生。這樣的并行結構通過使用處理位置上相互比鄰的G個匹配模塊，解決了自動狀態(tài)機模型中對于輸入字串1byte的限制，展寬了過濾帶寬，進而提高了過濾速率。2.2  匹配模塊的內(nèi)部結構   圖1中的一個匹配模塊是一個獨立的內(nèi)容過濾單元，也是一個獨立的狀態(tài)機轉換單元。其內(nèi)部根據(jù)輸入的G-byte的字串計算狀態(tài)

10、轉移以及匹配的命中結果。下面介紹一個匹配模塊的原理結構。   圖2所示的是一個4byte寬的狀態(tài)機模型，狀態(tài)的每次轉移都需要4byte的數(shù)據(jù)（4）。例如，判斷S6=“elephant”，在當前狀態(tài)q0的情況下，輸入串為“elep”時，狀態(tài)轉移q0q4，接著輸入“hant”，狀態(tài)轉移到q7，此時有匹配的結果輸出。而普通的狀態(tài)機，需要8次的狀態(tài)轉移。   在過濾的過程中更多的規(guī)則串并不是B的倍數(shù)，例如“phone”，在第一次狀態(tài)轉移中由于“phon”的存在由q0轉移到q3，此后至需要判斷下個輸入中     &

11、#160;   是不是后綴“e*”就可以判斷是否命中了s5，同樣還有“technically”中的后綴“l(fā)ly”等。對長度為1到B-1之間的后綴，采用并行的B-1個后綴判斷子模塊。同時注意到對于長度恰好是B的整數(shù)倍的規(guī)則串，可以理解成有一個長度為0的后綴，這樣便于同上述并行的B-1個后綴判斷子模塊一同組成B個并行的運算結構。圖3給出了一個B=4的情況下的一個匹配模塊的結構，其中4個Bloom Filter分別處理后綴長度為0、1、2、3的情況。然后通過查表得到狀態(tài)轉移關系以及結果輸出情況。圖2  一個4byte寬（B=4）的狀態(tài)機圖3  B=4情況下的一

12、個匹配模塊2.3  使用Bloom Filter   如前文所述，由于狀態(tài)轉移表占用很大的存儲空間，需要使用off-chip的RAM來保存。而通常情況下外部存儲器的讀取帶寬很小，不能支持一個模塊的B個查表要求。其實在真實情況中只有很少的情況下才會有狀態(tài)的轉換，這時使用Bloom Filter來濾掉大量的不會產(chǎn)生狀態(tài)變化的輸入。一個狀態(tài)轉移關系可以表示成：   當前狀態(tài)，輸入字串 =下個狀態(tài)，輸出信息   所以可以對2元組當前狀態(tài)，輸入字串進行hash運算，用結果搜索狀態(tài)轉移hash表，找到2元組下個狀態(tài)，輸出信息。Bloom

13、 Filter的作用就是濾掉大量不會查找到結果的元組，只在當前當前狀態(tài)，輸入字串有可能在hash表中查到結果的時候才允許對應項查找狀態(tài)轉移表。這樣極大地減少了查表次數(shù)，提高了算法速率。2.4  Hash函數(shù)的硬件實現(xiàn)方法   對于Bloom Filter中使用的hash函數(shù)，要求易于硬件，占用盡可能少的時鐘周期。H3算法提供了一個很好的解決方案。設子串的第i個字節(jié)為bi1、bi2、bi8，則這個位置上的一個hash值為：hi=di1bi1di2bi2di8bi8   其中dij是一個預設的隨機矩陣的一個值。這樣，從1到i的hash值為：Hi=H

14、i-1hi   可見，位置i上的hash函數(shù)可以通過i-1位置上的hash函數(shù)簡單的算出。并且如果dij=di+1j的話，可見t時刻的hi和t+1時刻的hi-1是相同的，這樣所有Hi就可以通過并行的移位結構在一個時鐘周期內(nèi)完成，而不用等待Hi-1的計算結果。相應的結構如圖4所示，算法可以在一個時鐘周期內(nèi)算出所有Hi的值，非常便捷。圖4  硬件Hash函數(shù)的邏輯結構3  FPGA實現(xiàn)   本文的實驗系統(tǒng)使用的是Altera公司StratixII系列的EP2S60FPGA芯片。該芯片擁有2.5Mb的片內(nèi)RAM空間，可以支持最多兩個獨立of

15、f-chip的DDR或QDR單元。輸入信號是經(jīng)過前端處理的POS信號，解為整載的IP報文數(shù)據(jù)。規(guī)則隨機地取自IDS系統(tǒng)SNORT的2000條規(guī)則。   在實現(xiàn)的過程中使用8個并行的過濾模塊，也就是每次輸入8byte的數(shù)據(jù)。雖然更高的并行數(shù)量會提高系統(tǒng)的處理帶寬，但是也相應需要占用更多的RAM空間，這里考慮到SNORT的規(guī)則相對較短（多分布在5-15byte），采用8byte并行的算法。Bloom Filter由6個并行的hash函數(shù)構成，每個hash函數(shù)對應的hash表采用2kbit，這樣一共占用了2kbit*6*8*8=768kbit的片內(nèi)RAM資源，約占總量的30%。經(jīng)

16、過計算，這樣的Bloom Filter設計可以保證經(jīng)過過濾操作之后，只有6e-10的假匹配存在（即對應的hash值表明當前元組當前狀態(tài)，輸入字串可以產(chǎn)生正確的狀態(tài)轉移，然而在off-chip的RAM中找不到對應項）。這里需要提一下，由于8個并行模塊是同構的，其hash表也是相同的，如果使用時分的hash表查找方法或者Lucent memory core可以占用更少的RAM資源。   當實驗系統(tǒng)FPGA工作在77MHz的情況下的時候，可以正確無誤的過濾2.5Gpbs的IP報文數(shù)據(jù)。由于該算法使用的RAM和時鐘頻率都沒有達到額定值，同時，內(nèi)部Bloom Filter和狀態(tài)轉移表

17、的構成同樣有待進一步優(yōu)化，所以本文算法具有進一步升級的潛力。4  結論   本文針對目前網(wǎng)絡傳播速率急劇增加，數(shù)據(jù)處理規(guī)則規(guī)模龐大的特點，提出了基于FPGA的IP報文內(nèi)容過濾算法。本文在當前多種優(yōu)秀的內(nèi)容過濾技術的基礎上，充分利用了FPGA芯片高速并行處理和流水線操作的特點，提出使用并行的移位模塊來拓展過濾算法的處理帶寬，使得算法支持的IP報文速率得到了很大的提高。同時，為解決off-chip的RAM讀取帶寬受限的瓶頸，以及在狀態(tài)轉移過程中讀取下一個狀態(tài)需要占用額外的時鐘周期的問題，提出了用Bloom Filter過濾掉不會產(chǎn)生狀態(tài)轉移的輸入字串，進一步提高處理速

18、率。另外，設計了僅需要一個時鐘周期就可以完成hash計算的硬件電路，并且通過改進，可以在一個時鐘周期內(nèi)得到所有后綴長度的hash值，使得算法在FPGA中的流水性能增強。最后通過在實驗系統(tǒng)中的測試，在77MHz的時鐘下可以正確的過濾2.5Gbps的IP報文，并且有進一步升級的潛力。參考文獻1Coit C J，Staniford S，McAlerney JTowards faster pattern matching for intrusion detection or exceeding the speed of snortCIn：DARPA Information Survivability Conference and Exposition，2001王永成，沈州，許一震改進的多模式匹配算法計算機研究與發(fā)展，2002，39(1)：55-60B. BloomSpace/time trade-offs in hash coding with allowable errorsACM，13(7)：422426，May 1970S. Dharmapurikar，P. Krishnamurthy，T. S. Sproull，and J. W. Lockwoo