一種高效的邏輯復(fù)用深度包過(guò)濾技術(shù)

摘要：

為提高檢測(cè)系統(tǒng)的準(zhǔn)確性，系統(tǒng)在數(shù)據(jù)流過(guò)濾過(guò)程中除了檢查包頭，還要針對(duì)載荷內(nèi)容進(jìn)行匹配檢測(cè)，但運(yùn)算量非常大，因此匹配模塊的運(yùn)行速度決定了入侵檢測(cè)系統(tǒng)的性能。為此，提出了一種基于FPGA深度包過(guò)濾技術(shù)的入侵檢測(cè)模型，以及一項(xiàng)既能減小系統(tǒng)規(guī)模，又能提高過(guò)濾速率的邏輯復(fù)用優(yōu)化技術(shù)。

關(guān)鍵詞：深度包過(guò)濾； 并行流水線結(jié)構(gòu)； 模式匹配

中圖分類(lèi)號(hào)：TP309．2文獻(xiàn)標(biāo)志碼：A

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

隨著網(wǎng)絡(luò)時(shí)代的快速發(fā)展，針對(duì)網(wǎng)絡(luò)應(yīng)用層的攻擊日益增多。要防止計(jì)算機(jī)遭受網(wǎng)絡(luò)攻擊，僅僅依靠檢查網(wǎng)絡(luò)數(shù)據(jù)包的包頭是遠(yuǎn)遠(yuǎn)不夠的。作為入侵檢測(cè)系統(tǒng)，不僅要檢查包頭，還要針對(duì)數(shù)據(jù)包的有效載荷部分進(jìn)行檢查，因此系統(tǒng)中使用一些主要檢測(cè)載荷內(nèi)容的深度包過(guò)濾器是非常必要的。

包頭域的位置是通過(guò)標(biāo)準(zhǔn)協(xié)議來(lái)定義的，因此系統(tǒng)能較容易地實(shí)現(xiàn)針對(duì)包頭的高效檢測(cè)，相反有效載荷內(nèi)容卻不受任何標(biāo)準(zhǔn)定義的限制，對(duì)其搜索和分析勢(shì)必會(huì)更復(fù)雜，工程開(kāi)銷(xiāo)更大。這就需要一種主要針對(duì)載荷內(nèi)容匹配的新技術(shù)，既能減小比較匹配系統(tǒng)規(guī)模，又能提高系統(tǒng)運(yùn)行效率，在這種工程需求下邏輯復(fù)用技術(shù)應(yīng)運(yùn)而生。

1）深度包過(guò)濾技術(shù)概述

簡(jiǎn)單地講，深度包過(guò)濾就是在傳統(tǒng)的只針對(duì)網(wǎng)絡(luò)數(shù)據(jù)包頭的檢測(cè)已遠(yuǎn)遠(yuǎn)不能適應(yīng)網(wǎng)絡(luò)安全需求的情況下，系統(tǒng)除了檢測(cè)包頭，還要將數(shù)據(jù)包中有效載荷部分與系統(tǒng)過(guò)濾器規(guī)則庫(kù)中的每一個(gè)匹配模式進(jìn)行比較，以發(fā)現(xiàn)各種潛在的攻擊，從而使計(jì)算機(jī)具備更多網(wǎng)絡(luò)保護(hù)。

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

字符串序列輸入移位比較過(guò)濾器處理單元，與三個(gè)8 bit寄存器進(jìn)行移位比較匹配。寄存器中的匹配模式字符串是“ACE”，而此時(shí)輸入對(duì)應(yīng)的子串是“AAC”，三個(gè)字符中只有“A”匹配，通過(guò)“與”邏輯，最終1 bit仲裁寄存器輸出值為“0”，表示比較器沒(méi)有發(fā)現(xiàn)匹配；接著輸入字符串“ACE”進(jìn)行下一輪比較，則三個(gè)字符均匹配，仲裁寄存器輸出值由“0”變?yōu)椤?”，結(jié)果輸出至其他處理單元。圖示系統(tǒng)是單字符串行比較，而且檢測(cè)系統(tǒng)中的字符串匹配吞吐量會(huì)隨著模式字符的增加而減少，因此運(yùn)行速度比較慢。這就需要一種高效的并行處理方案來(lái)提高檢測(cè)系統(tǒng)的整體性能。

2）相關(guān)研究工作

近年來(lái)，為滿足高速網(wǎng)絡(luò)過(guò)濾的需求，針對(duì)FPGA（現(xiàn)場(chǎng)可編程門(mén)陣列）出現(xiàn)了一些快速模式匹配算法。R.Sidhu等人[1]把針對(duì)常用模式的非確定性有限自動(dòng)機(jī)（NFA）設(shè)置在FPGA中，以取得快速模式匹配。而華盛頓大學(xué)把常用式轉(zhuǎn)換成確定性有限自動(dòng)機(jī)（DFA），這表明在實(shí)際中大部分DFA能夠優(yōu)化高速集成的硬件[2]。

這些設(shè)計(jì)都主張使用硬件并行結(jié)構(gòu)所帶來(lái)的高性能，而沒(méi)有考慮到模式的規(guī)模大小。上述方案均是按照Snort模式中小的子集來(lái)設(shè)計(jì)的。如果把當(dāng)前所有的Snort模式用以上方案來(lái)編譯，最后產(chǎn)生的硬件將由于規(guī)模太龐大而很難在普通單片F(xiàn)PGA上實(shí)現(xiàn)。

為了提高檢測(cè)系統(tǒng)的過(guò)濾速度及準(zhǔn)確度，同時(shí)又能從最大程度上節(jié)約FPGA的使用成本，提高其使用率，降低工程造價(jià)，因而研究采用了下文所述的深度包過(guò)濾系統(tǒng)結(jié)構(gòu)以及邏輯復(fù)用優(yōu)化技術(shù)。

1深度包過(guò)濾系統(tǒng)結(jié)構(gòu)

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

1．1扇出樹(shù)部分

扇出樹(shù)將網(wǎng)上傳輸?shù)囊粋€(gè)個(gè)數(shù)據(jù)包完整備份成多個(gè)相同的包，同時(shí)發(fā)送給多個(gè)并行比較單元，為下一步比較匹配提供數(shù)據(jù)。輸出樹(shù)部分是整個(gè)過(guò)濾系統(tǒng)的基礎(chǔ)。輸出延遲是影響該環(huán)節(jié)的主要因素，因此又提出了寄存器樹(shù)的概念，即從樹(shù)的第一級(jí)開(kāi)始使用小的輸出，而后隨級(jí)數(shù)的提高而增加輸出，一直增加到最后一級(jí)的優(yōu)化樹(shù)結(jié)構(gòu)，從而有效降低了因延遲產(chǎn)生的數(shù)據(jù)包傳輸中的瓶頸效應(yīng)。

1．2深度過(guò)濾部分

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

1．3邏輯仲裁部分

從并行比較單元送來(lái)的模式匹配結(jié)果被送至邏輯仲裁部分。該部分根據(jù)多路并行比較結(jié)果產(chǎn)生仲裁結(jié)論，即決定系統(tǒng)對(duì)數(shù)據(jù)包的下一步正確操作，如記錄、刪除等，從而實(shí)現(xiàn)對(duì)特征數(shù)據(jù)包及可疑數(shù)據(jù)包的安全處理，防止受到網(wǎng)絡(luò)攻擊，維護(hù)計(jì)算機(jī)的正常運(yùn)行。

2邏輯復(fù)用的深度包過(guò)濾技術(shù)

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

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

圖2所示的系統(tǒng)是串行單字符比較，速度比較慢。為了提高該比較匹配單元的工作效率，提出了擴(kuò)展總線寬度以及增加相同檢測(cè)模塊的方法來(lái)實(shí)現(xiàn)高速處理數(shù)據(jù)流。如圖3所示，32 bit總線寬度的檢測(cè)模塊取代了串行單字符檢測(cè)，被用來(lái)并行檢查每個(gè)輸入字符隊(duì)列（每個(gè)周期同時(shí)比較四個(gè)字符）。

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

2．2邏輯復(fù)用技術(shù)

從工程實(shí)踐中可以得出，深度包過(guò)濾器面臨的挑戰(zhàn)性問(wèn)題是巨大的邏輯資源需求問(wèn)題。據(jù)統(tǒng)計(jì)至2004年初，Snort模式設(shè)置約有2 080種。要實(shí)現(xiàn)整個(gè)模式設(shè)置估計(jì)將需要超過(guò)23萬(wàn)個(gè)邏輯門(mén)，將用到12塊FPGA，系統(tǒng)規(guī)模較大，同時(shí)產(chǎn)品性價(jià)比太低，主要是工程造價(jià)太高，所以僅僅使用一般匹配方法是很不適合的。

上文提供的方法，雖能較容易地設(shè)計(jì)出其架構(gòu)，但同時(shí)也使用了大量空閑子結(jié)構(gòu)，浪費(fèi)了系統(tǒng)資源。下面提出一種提高邏輯域利用率的設(shè)計(jì)方案，即通過(guò)改進(jìn)邏輯來(lái)減少相同的匹配模式，即邏輯復(fù)用技術(shù)。 

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

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

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

2．3邏輯復(fù)用的優(yōu)勢(shì)

為了提高速度與可編程能力，一些入侵檢測(cè)系統(tǒng)簡(jiǎn)單運(yùn)用了FPGA過(guò)濾器，缺點(diǎn)是設(shè)計(jì)過(guò)于龐大。通過(guò)共用相同子邏輯比較結(jié)果，能有效地減少過(guò)濾器的引腳，從而解決不能把大量模式設(shè)置映射在單片F(xiàn)PGA上的問(wèn)題。

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

3結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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ìn)的多模式匹配算法[J].計(jì)算機(jī)研究與發(fā)展， 2002，39(1):55-60.

（上接第123頁(yè)）

易地辨認(rèn)出來(lái)，已達(dá)到版權(quán)保護(hù)的目的。這些說(shuō)明本文提出的算法是有效的。

參考文獻(xiàn)：

［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]. 電子與信息學(xué)報(bào)，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］劉化波，李秀艷，謝海燕，等.基于圖像壓縮標(biāo)準(zhǔn)JPEG和人類(lèi)視覺(jué)系統(tǒng)的數(shù)字水印算法[J].大連海事大學(xué)學(xué)報(bào)，2005，31(1):99－101.

［7］李霞，姚璐.一種基于JPEG壓縮的信息隱藏方法[J]. 計(jì)算機(jī)工程與應(yīng)用，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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”