一種高效的邏輯復用深度包過濾技術

摘要：

為提高檢測系統的準確性，系統在數據流過濾過程中除了檢查包頭，還要針對載荷內容進行匹配檢測，但運算量非常大，因此匹配模塊的運行速度決定了入侵檢測系統的性能。為此，提出了一種基于FPGA深度包過濾技術的入侵檢測模型，以及一項既能減小系統規模，又能提高過濾速率的邏輯復用優化技術。

關鍵詞：深度包過濾； 并行流水線結構； 模式匹配

中圖分類號：TP309．2文獻標志碼：A

文章編號：1001-3695(2007)11-0124-03

隨著網絡時代的快速發展，針對網絡應用層的攻擊日益增多。要防止計算機遭受網絡攻擊，僅僅依靠檢查網絡數據包的包頭是遠遠不夠的。作為入侵檢測系統，不僅要檢查包頭，還要針對數據包的有效載荷部分進行檢查，因此系統中使用一些主要檢測載荷內容的深度包過濾器是非常必要的。

包頭域的位置是通過標準協議來定義的，因此系統能較容易地實現針對包頭的高效檢測，相反有效載荷內容卻不受任何標準定義的限制，對其搜索和分析勢必會更復雜，工程開銷更大。這就需要一種主要針對載荷內容匹配的新技術，既能減小比較匹配系統規模，又能提高系統運行效率，在這種工程需求下邏輯復用技術應運而生。

1）深度包過濾技術概述

簡單地講，深度包過濾就是在傳統的只針對網絡數據包頭的檢測已遠遠不能適應網絡安全需求的情況下，系統除了檢測包頭，還要將數據包中有效載荷部分與系統過濾器規則庫中的每一個匹配模式進行比較，以發現各種潛在的攻擊，從而使計算機具備更多網絡保護。

深度包過濾器的核心處理單元如圖1所示。

字符串序列輸入移位比較過濾器處理單元，與三個8 bit寄存器進行移位比較匹配。寄存器中的匹配模式字符串是“ACE”，而此時輸入對應的子串是“AAC”，三個字符中只有“A”匹配，通過“與”邏輯，最終1 bit仲裁寄存器輸出值為“0”，表示比較器沒有發現匹配；接著輸入字符串“ACE”進行下一輪比較，則三個字符均匹配，仲裁寄存器輸出值由“0”變為“1”，結果輸出至其他處理單元。圖示系統是單字符串行比較，而且檢測系統中的字符串匹配吞吐量會隨著模式字符的增加而減少，因此運行速度比較慢。這就需要一種高效的并行處理方案來提高檢測系統的整體性能。

2）相關研究工作

近年來，為滿足高速網絡過濾的需求，針對FPGA（現場可編程門陣列）出現了一些快速模式匹配算法。R.Sidhu等人[1]把針對常用模式的非確定性有限自動機（NFA）設置在FPGA中，以取得快速模式匹配。而華盛頓大學把常用式轉換成確定性有限自動機（DFA），這表明在實際中大部分DFA能夠優化高速集成的硬件[2]。

這些設計都主張使用硬件并行結構所帶來的高性能，而沒有考慮到模式的規模大小。上述方案均是按照Snort模式中小的子集來設計的。如果把當前所有的Snort模式用以上方案來編譯，最后產生的硬件將由于規模太龐大而很難在普通單片FPGA上實現。

為了提高檢測系統的過濾速度及準確度，同時又能從最大程度上節約FPGA的使用成本，提高其使用率，降低工程造價，因而研究采用了下文所述的深度包過濾系統結構以及邏輯復用優化技術。

1深度包過濾系統結構

本文提出的深度包過濾系統由扇出樹、深度過濾和邏輯仲裁三部分組成，如圖2所示。網絡數據包進入過濾系統，經扇出樹產生相同包頭和載荷內容，再分別并行經過不同比較匹配單元同時處理，各路匹配結果被送至邏輯仲裁單元，最后從仲裁單元產生輸出對該數據包的下一步處理方法。使用了數據包頭與載荷內容的同時并行比較，而且又針對不同的模式進行匹配（每個內容過濾器中的模式是不同的），所以系統檢測的準確率及速率得到了有效提高。

1．1扇出樹部分

扇出樹將網上傳輸的一個個數據包完整備份成多個相同的包，同時發送給多個并行比較單元，為下一步比較匹配提供數據。輸出樹部分是整個過濾系統的基礎。輸出延遲是影響該環節的主要因素，因此又提出了寄存器樹的概念，即從樹的第一級開始使用小的輸出，而后隨級數的提高而增加輸出，一直增加到最后一級的優化樹結構，從而有效降低了因延遲產生的數據包傳輸中的瓶頸效應。

1．2深度過濾部分

從扇出樹發送來的數據包分為兩部分進行比較，即數據包頭和數據包載荷內容。數據包頭格式較固定，包頭匹配也較容易實現。本文重點討論數據包載荷內容部分的匹配。過濾單元的匹配速度是影響整個檢測系統吞吐量最主要的因素。這里采用并行流水線比較結構，字符串并行輸入匹配模塊，并與系統定義的多種模式同時進行比較匹配，從而進一步提高了匹配效率，克服了因串行比較所產生的速度慢的問題。每一路中數據包頭的比較結果與載荷內容的匹配結果同時被送至下一個處理單元——邏輯仲裁部分。

1．3邏輯仲裁部分

從并行比較單元送來的模式匹配結果被送至邏輯仲裁部分。該部分根據多路并行比較結果產生仲裁結論，即決定系統對數據包的下一步正確操作，如記錄、刪除等，從而實現對特征數據包及可疑數據包的安全處理，防止受到網絡攻擊，維護計算機的正常運行。

2邏輯復用的深度包過濾技術

本文設計的系統由若干檢測單元組成。這些單元能夠同時將輸入數據與系統中定義的所有模式進行比較。通過對設計的系統結構使用優化技術，如利用消除相同邏輯的方法，就可以從根本上減少邏輯域的大小，從而把大量模式設置在一塊FPGA上，在很大程度上降低了匹配模塊的規模，降低了消耗，使系統在處理海量數據方面具有更好的適應性。

2．1一般并行比較匹配方法

圖2所示的系統是串行單字符比較，速度比較慢。為了提高該比較匹配單元的工作效率，提出了擴展總線寬度以及增加相同檢測模塊的方法來實現高速處理數據流。如圖3所示，32 bit總線寬度的檢測模塊取代了串行單字符檢測，被用來并行檢查每個輸入字符隊列（每個周期同時比較四個字符）。

圖3中定義的第一個周期中，并行字符序列“FACE”與系統第二個字符串模式“ACE”匹配，匹配結果在寄存器中暫時保存。此時寄存器中產生控制信號使其下一級（上、下級劃分以圖中虛線為界）“GH”比較單元在下一周期比較結果有效。接著第二周期“GHBA”輸入，恰好與系統第二個字符串模式的下一級“GH”匹配，其結果有效，則鎖存器輸出有效高電平（輸出值為“1”）。輸入采用的是并行結構，輸入字符序列對于每個字符串模式的上、下兩級均同時比較，只是在上一級匹配的情況下下一級的比較結果才有效，而第二周期中輸入的第四個字符“A”與系統第四個字符串模式“A”同時也匹配，使得第四個寄存器保存了匹配結果，并產生控制信號，使第四個字符串模式下一級“CEGH”比較單元在第三周期比較的結果有效。后面各周期輸入比較依此類推。

2．2邏輯復用技術

從工程實踐中可以得出，深度包過濾器面臨的挑戰性問題是巨大的邏輯資源需求問題。據統計至2004年初，Snort模式設置約有2 080種。要實現整個模式設置估計將需要超過23萬個邏輯門，將用到12塊FPGA，系統規模較大，同時產品性價比太低，主要是工程造價太高，所以僅僅使用一般匹配方法是很不適合的。

上文提供的方法，雖能較容易地設計出其架構，但同時也使用了大量空閑子結構，浪費了系統資源。下面提出一種提高邏輯域利用率的設計方案，即通過改進邏輯來減少相同的匹配模式，即邏輯復用技術。 

在從字符總線上過濾字符串的過程中，所有的4字符子串匹配模塊均并行連接在同一總線上，同時會有很多比較器檢查同一子串，而實際上部分比較器的使用率很低，從某種程度上浪費了系統資源。需要一種方法去除這些多余的部件，同時也能提高系統的處理速度。

舉例說明，如圖4所示，針對“CACAC”模式和“ACAC”模式的匹配模塊中有四組相同的比較器。通過比較相同的子串，如針對子串“ACAC”“CAC”“AC”和“C”的多余比較器能夠省去。比如，若第一個周期中輸入了字符串“CACA”，則同時滿足了模式“CACAC”（后稱第一個模式）和模式“ACAC”（后稱第二個模式）中的上一級子串“CACA”和“ACA”，使得下一個周期中其各自相匹配字符串模式的下一級子串比較結果有效。那么下一個周期中輸入的字符串第一個字符如果是“C”，第二個模式第二個字符串的下一級“C”就可以直接利用第一個模式第一個字符串下一級“C”的匹配結果，而沒有必要再進行重復比較，使用簡單的“與”邏輯門即可實現復用。同理，第二個模式第三個字符串的下一級“AC”可以直接利用第一個模式第二個字符串下一級“AC”的匹配結果。后面的“CAC”“ACAC”同理也可以實現邏輯復用，去除多余的比較器，可以使整個系統總的邏輯域大大減少。優化結果如圖5所示。

要消除相同比較器，實現邏輯復用，首先將每個目標字符串分成如圖4所示的一系列1~4字符不等的片段；接著從所有片段中抽出一組模式惟一的字符串片段，并且只有這部分字符串片段被輸入比較器，比較的結果與其模式相同的片段共用，從而有效消除了比較器之間相同的部分；最后，比較器的匹配結果輸出，被直接送至邏輯仲裁模塊處理，除去了中間或門、寄存器等邏輯部件，而在邏輯仲裁模塊實現相應功能，并同時產生總線控制信號(BCS)，如圖5所示。試驗證明該優化設計可以有效提高系統速度。

2．3邏輯復用的優勢

為了提高速度與可編程能力，一些入侵檢測系統簡單運用了FPGA過濾器，缺點是設計過于龐大。通過共用相同子邏輯比較結果，能有效地減少過濾器的引腳，從而解決不能把大量模式設置映射在單片FPGA上的問題。

實踐證明，這些設計方法使得能夠在一塊Xilinx Virtex－ⅡPro－XC2VP20 FPGA上設置2 080個攻擊過濾模式，對于64~1 500 Byte的數據包，具有針對網絡流量超過2．5 Gbps的過濾速率。邏輯復用技術在很大程度上降低了模塊規模消耗，并有效提高了系統過濾速率。

3結束語

入侵檢測系統是一個典型的數據處理系統。它通過對大量數據進行分析，來判斷被監控的系統是否受到了入侵攻擊。鑒于此，本文提出了一種基于FPGA的并行流水線式深度包過濾入侵檢測系統模型，在載荷深度匹配部分應用了邏輯復用技術，在很大程度上提高了系統過濾準確性及比較匹配速率，降低了匹配模塊的規模和成本，使系統在處理海量數據方面更具有適應性與高效性。但是，基于FPGA的過濾系統存在不容易寫入、修改的問題，今后可以考慮利用內容可編址存儲器（CAM）和Snort規則裝置，來實現快速可重新編程深度包過濾。

參考文獻：

[1]SIDHU R， PRASANNA V K. Fast regular expression matching using FPGAs[C]//Proc of the 9th Annual IEEE Symposium on Field－Programmable Custom Computing Machines.Rohnert Park， CA:[s.n.]，2001:227-238.

[2]MOSCOLA J， LOCKWOOD J， LOUI R P， et al. Implementation of a content－scanning module for an Internet firewall[C]//Proc of the 11th Annual IEEE Symposium on Field－Programmable Custom Computing Machines.Napa， California， Los Alamitos:[s.n.]，2003:31-38.

[3]NAVARRO G， YATESA R B. New and faster filters for multiple approximate string matching[J]. Random Structures and Algorithms， 2002，20(1):23-49.

[4]王永成.改進的多模式匹配算法[J].計算機研究與發展， 2002，39(1):55-60.

（上接第123頁）

易地辨認出來，已達到版權保護的目的。這些說明本文提出的算法是有效的。

參考文獻：

［1］WONG P H W， AU Q C.A capacity estimation technique for JPEG image watermarking[J]. IEEE Transactions on Circuits and Systems for Video Technology，2003，13(8):746-752.

［2］WONG P H W， AU Q C.A blind watermarking technique in JPEG compressed domain[J]. IEEE International Conference on Image Processing，2002 (3)：497-500.

［3］TAO B，DICKISON B.Adaptive watermarking in the DCT domain[C]//Proc of IEEE International Conference Acoustics，Speech，and Signal Processing.1997:2985-2988.

［4］伍宏濤，胡云，鈕心忻，等.抗JPEG壓縮和圖像合并的水印算法[J]. 電子與信息學報，2005，27(6):914-918.

［5］WONG P H W， OSCAR C，WONG J W C.Data hiding and watermarking in JPEG compresseddomain by DC coefficient modification[C]//Proc of SPIE.2000：237-244.

［6］劉化波，李秀艷，謝海燕，等.基于圖像壓縮標準JPEG和人類視覺系統的數字水印算法[J].大連海事大學學報，2005，31(1):99－101.

［7］李霞，姚璐.一種基于JPEG壓縮的信息隱藏方法[J]. 計算機工程與應用，2003，29：164－166.

［8］LIN Yin.Stack filter design：a structural approach[J]. IEEE Tran￣sactions on Signal Processing，1995，43（4）：831-840.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”