??? 摘??要: 基于網(wǎng)絡(luò)處理器" title="網(wǎng)絡(luò)處理器">網(wǎng)絡(luò)處理器的特點(diǎn),,提出了一種新的多模" title="多模">多模匹配算法HBM算法,。在Intel網(wǎng)絡(luò)處理器IXP2400上,設(shè)計(jì)實(shí)現(xiàn)了高速反蠕蟲病毒引擎" title="反蠕蟲病毒引擎">反蠕蟲病毒引擎,。實(shí)驗(yàn)表明,,引擎達(dá)到了千兆以太網(wǎng)的性能要求,具有較好的實(shí)際應(yīng)用價(jià)值,。
??? 關(guān)鍵詞: 網(wǎng)絡(luò)處理器? 反蠕蟲病毒引擎? 多模匹配算法? HBM算法
?
??? 隨著Internet規(guī)模的擴(kuò)大,,網(wǎng)絡(luò)安全已經(jīng)成為當(dāng)前網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)中的一個(gè)重要問題。為此,,在當(dāng)前的網(wǎng)絡(luò)防火墻和入侵檢測(cè)系統(tǒng)(IDS)中,,除了需要進(jìn)行協(xié)議分析、流狀態(tài)檢測(cè)外,,還需要對(duì)網(wǎng)絡(luò)分組的載荷進(jìn)行特征匹配,,以此來確定網(wǎng)絡(luò)分組中是否含有蠕蟲病毒代碼。與網(wǎng)絡(luò)帶寬的飛速提高相比,,反蠕蟲系統(tǒng)的掃描引擎的發(fā)展還不成熟,,開發(fā)千兆以太網(wǎng)環(huán)境下的反蠕蟲系統(tǒng)還有難度。本文給出的對(duì)于網(wǎng)絡(luò)分組載荷進(jìn)行掃描檢測(cè)的多模匹配引擎,,正是一種適合高速環(huán)境下的反蠕蟲引擎系統(tǒng),。
1 相關(guān)工作
??? 反蠕蟲引擎平臺(tái)主要有兩種:一種是采用全硬件定制的方式;另一種是采用軟件實(shí)現(xiàn)的方式,。采用硬件方式往往能夠得到較高的掃描檢測(cè)速度,,但是不適合設(shè)計(jì)比較復(fù)雜的防火墻或IDS系統(tǒng);采用軟件方式的掃描引擎速度較慢,,但是可以用來設(shè)計(jì)實(shí)現(xiàn)功能復(fù)雜的系統(tǒng),。
??? 網(wǎng)絡(luò)處理器[1]是一種介于全硬件定制和通用處理器之間的新型處理器,相對(duì)于前兩種實(shí)現(xiàn)方式,,網(wǎng)絡(luò)處理器兼有他們的優(yōu)點(diǎn),。一方面,,它采用執(zhí)行程序的方式,相比于硬件實(shí)現(xiàn)方式,,可以完成較為復(fù)雜的處理功能,。同時(shí),,也可以方便地添加和擴(kuò)展功能模塊,,有效地移植和整合現(xiàn)有的程序功能。另一方面,,它的硬件體系結(jié)構(gòu)針對(duì)網(wǎng)絡(luò)應(yīng)用進(jìn)行了優(yōu)化,,大大提升了分組處理過程,可以得到較好的性能指標(biāo),,適合作為網(wǎng)絡(luò)應(yīng)用的開發(fā)平臺(tái)[1,5,9],。
??? 反蠕蟲引擎的核心算法是多模匹配算法(multi-pattern matching algorithm)[2,4],即對(duì)于輸入的字符串,,掃描其是否包含預(yù)先給定的若干特征字符串之一,,蠕蟲攜帶的特征字符串也稱為特征碼(signature)。
??? 多模匹配的主要算法之一是將BM算法[6]在多模匹配條件下進(jìn)行擴(kuò)展,。BM算法是一種啟發(fā)式算法,,主要利用了失效字符轉(zhuǎn)跳及好后綴轉(zhuǎn)跳思想,如圖1和圖2所示,。該算法思想是在每次匹配中,,從右往左反向逐個(gè)比較字符,當(dāng)發(fā)生匹配失敗時(shí),,根據(jù)此字符的信息以及之前比較過的字符串后綴(即字符串最右部分)信息,,最大程度地向后移動(dòng)比較指針,從而減少無(wú)用的比較次數(shù),。在圖1中,,輸入字符‘l’匹配失敗,從失效轉(zhuǎn)跳表Delta1中,,找到‘l’對(duì)應(yīng)項(xiàng)的值(該值為‘l’在“hello hi”中最右出現(xiàn)處到串末尾的距離),,并將輸入字符串向左移動(dòng)相應(yīng)距離。在圖2中,,輸入串的‘do’和特征字符串末尾的‘do’相匹配,,稱特征字符串的‘do’為好后綴。轉(zhuǎn)跳時(shí),,可以將輸入字符串的‘do’移動(dòng)到和特征串中的前一個(gè)‘do’相對(duì)齊位置,。
?
??? BM算法思路推廣到多模匹配中,由于匹配模式增加,,Delta1表的每一項(xiàng)必須是字符塊而不是單個(gè)字符(否則,,所有值均接近0,,無(wú)法給出好的轉(zhuǎn)跳信息),這樣就帶來Delta1表空間增大的問題,,同時(shí)原來的好后綴生成算法在多模匹配下也不正確,,需要重新設(shè)計(jì)。
??? 這類算法主要有WM算法[4],、Setwise BMH算法[7],、AC-BM算法[8]等。WM算法只對(duì)輸入字符串的后綴進(jìn)行一次比較,,并沒有很好地利用字符串的整體信息,,也沒有利用好后綴的可能轉(zhuǎn)跳。Setwise BMH算法和AC-BM算法的失效字符轉(zhuǎn)跳表(Delta1表)的組織空間往往很大,,無(wú)法放入高速緩存之中,,不適合在網(wǎng)絡(luò)處理器上實(shí)現(xiàn)。為此,,本文基于網(wǎng)絡(luò)處理器的特點(diǎn),,提出了一種新的多模匹配算法,即HBM算法,。
2 HBM算法描述
??? HBM算法同樣使用失效字符轉(zhuǎn)跳思想,,所不同的是,將失效字符轉(zhuǎn)跳表(Delta1表)進(jìn)行散列壓縮(允許碰撞),,從而可以大大減少Delta1表的空間占用,;同時(shí),在多模匹配情況下改進(jìn)好后綴轉(zhuǎn)跳方式,。與以上幾種算法相比,,HBM算法可以在空間要求大大降低的情況下,得到相近甚至更優(yōu)的時(shí)間性能,;同時(shí),,在網(wǎng)絡(luò)處理器系統(tǒng)中,可利用高速緩存單元,,得到更好的系統(tǒng)性能數(shù)據(jù),。其主要步驟如下:
??? (1)每次比較的基本單位是若干個(gè)字符(在實(shí)現(xiàn)中取4個(gè)字符)組成的字符塊。
??? (2)每次對(duì)一段輸入子字符串的匹配是從右向左依次進(jìn)行的,。例如,,子字符串“abcdef”需要先比較字符塊“cdef”,再比較“bcde”,,最后比較“abcd”,。判斷第i次字符塊比較是否成功的條件是:該字符塊在Delta1表中的值D1是否小于i(即D1??? (3)一旦某個(gè)字符塊比較失敗,,則當(dāng)前子字符串匹配失敗。根據(jù)啟發(fā)式移位表Delta1和Delta2向左移動(dòng)輸入字符串,,開始一輪新的子字符串匹配,。
??? (4)算法使用兩張啟發(fā)式移位表:Delta1和Delta2,第(3)步中輸入字符串的移動(dòng)距離,,取兩者中的較大值,。
??? (5)若某個(gè)子字符串的所有字符塊均比較成功,則還需要和蠕蟲特征碼進(jìn)行精確比較,,才能確定其為特征碼之一或是一次誤判(false-positive),。
??? 整個(gè)掃描過程并不復(fù)雜,算法的主要難點(diǎn)在于如何有效地構(gòu)造兩張啟發(fā)式移位表Delta1和Delta2,。下面對(duì)這兩張表的構(gòu)造做詳細(xì)介紹。
2.1 Delta1表構(gòu)造
??? Delta1表的構(gòu)造和原BM算法相比,,不同之處在于:
??? (1)比較的基本單位變?yōu)樽址麎K,。
??? (2)字符塊在Delta1表中的索引位置由散列函數(shù)值決定。
??? (3)如果兩個(gè)字符塊由于散列沖突而對(duì)應(yīng)Delta1表的同一項(xiàng),,則此項(xiàng)存放兩者中的較小“移位距離”,。
??? 例如,圖3中“efgh”和“abcd”的散列值相同,,它們就存放于Delta1表中的同一項(xiàng),,其值取較小的值0。
?
?
2.2 Delta2表構(gòu)造
??? Delta2表的構(gòu)造比較復(fù)雜,,下面將給出其構(gòu)造和使用方法,。
??? 在多模匹配情況下,不能像BM算法那樣直接找特征串首部是否有和后綴相同的字串,,而是要通過字符塊在Delta1表中的值D1,,來間接判斷首部是否有好后綴。例如,,在圖4中,,字串“xbcde”和后綴串“abcde”具有相同的特征(如圖所示,從右往左數(shù),,第i個(gè)字符塊的Delta1值D1
?
?
??? 記特征字符串?dāng)?shù)為n,長(zhǎng)度為L(zhǎng),,塊大小為b,;記特征碼為S0,S2……,,Sn-1,為了便于描述,,將任意字符串pattern=a0a1a2…aL-1,,擴(kuò)充記為pattern=…$$$$a0a1a2…aL-1,即ai=$,。其中$為假想字符,,可為任意字符,同時(shí)任何含有$的字符塊,,其Delta1值定為D1=0,。這里對(duì)所有特征字符串都作了這種擴(kuò)充。
??? 在給出Delta2表的構(gòu)造和使用之前,,先給出某個(gè)子字符串“相一致”,,以及函數(shù)rpr(rightmost plausible reoccurrence)的定義。
??? “相一致”指的是在特征字符串中,,某個(gè)子字符串和后綴子字符串,,它們的首字符塊有不同的特性,而其余對(duì)應(yīng)字符塊則有共同的特性,,如圖4所示,。由于出現(xiàn)好后綴轉(zhuǎn)跳時(shí),后綴子字符串的Delta1值特性固定,,因此定義特征字符串中的子字符串C=c0 c1…cn和后綴字符串“相一致”,,要求滿足條件(1):
???
式中,D1(ci ci+1…ci+b-1)為字符塊ci ci+1…ci+b-1在Delta1表中的移位值,。
??? 定義函數(shù)y=rpr(Si,t),,t∈[0,L-b-1],要求在特征字符串Si中,,從位置t往左(不包括t),,找到長(zhǎng)度為L(zhǎng)-t的最右的相一致的子字符串,記此子字符串為位置k開始的siksi(k+1)…si(k+L-t-1),,則rpr(Si,t)=k+1,。
??? Delta2表長(zhǎng)度固定為L(zhǎng)-b+1,記Delta2表的第t項(xiàng)的值為D2(t),,則其值可由(2)式求得,。
???
式中,0≤t≤L-b-1,,maxr{rpr(Si,t)}表示對(duì)于r=0,1,…n-1,,取這n個(gè)特征字符串Sr的rpr值中的最大值。
3 基于網(wǎng)絡(luò)處理器的優(yōu)化
??? 本文將HBM算法在Intel網(wǎng)絡(luò)處理器IXP 2400上實(shí)現(xiàn),并針對(duì)IXP 2400的體系結(jié)構(gòu)特點(diǎn)進(jìn)行了優(yōu)化,。主要由網(wǎng)絡(luò)處理器的XScale核心對(duì)蠕蟲特征碼進(jìn)行初始化處理,,組織兩張啟發(fā)式移位表;運(yùn)行時(shí)主要由微引擎執(zhí)行掃描工作,,完成網(wǎng)絡(luò)分組的接收,、分類、掃描和轉(zhuǎn)發(fā)功能,。系統(tǒng)整體功能模塊如圖5所示,。
?
??? 在IXP 2400上實(shí)現(xiàn)HBM多模匹配算法時(shí),綜合起來,,主要的優(yōu)化有:
??? (1)算法中的散列運(yùn)算用邏輯操作完成,,不需要復(fù)雜的乘除指令支持,適合網(wǎng)絡(luò)處理器的指令結(jié)構(gòu),。
??? (2)將特征字符串組織成散列鏈表的形式,,以減少精確匹配時(shí)的I/O" title="I/O">I/O操作次數(shù)。散列鏈表結(jié)構(gòu)如圖6所示,。
?
??? (3)將兩張?jiān)L問頻率較高的表Delta1和Delta2存放在I/O存取速度快的存儲(chǔ)單元,,將訪問頻率低的特征字符串集合存放在存取速度慢的單元,如表1所示,。
?
?
??? (4)對(duì)于輸入的分組載荷進(jìn)行預(yù)讀取功能,以減少I/O操作次數(shù),。即對(duì)于輸入的分組載荷,,每次從慢速DRAM中預(yù)讀取最大的64個(gè)二進(jìn)制字符,通過軟件計(jì)算指針位置,,從而有效地利用預(yù)讀取的分組載荷,,減少I/O訪問次數(shù)。
4 實(shí)驗(yàn)測(cè)試與性能分析
??? 在測(cè)試床中對(duì)系統(tǒng)的有效性進(jìn)行了測(cè)試,。該測(cè)試床包括以下設(shè)備:千兆以太網(wǎng)絡(luò)交換機(jī)(TP-LINK TL-SL2226P+,24+2G),、流量發(fā)生器IXIA 1600、ENP 2611實(shí)驗(yàn)板(含IXP2400網(wǎng)絡(luò)處理器),,以及攜帶蠕蟲病毒的PC機(jī),、多臺(tái)普通PC機(jī)和服務(wù)器。其配置環(huán)境示意圖如圖7所示,。反蠕蟲病毒引擎工作在監(jiān)聽模式下被動(dòng)接收分組,、檢測(cè)并發(fā)出報(bào)警。
?
??? 實(shí)驗(yàn)采用隨機(jī)產(chǎn)生的固定長(zhǎng)度特征碼字,,字長(zhǎng)為32字節(jié),,特征碼的數(shù)量為512個(gè)(注意:HBM算法也支持非固定長(zhǎng)度的特征碼字)。產(chǎn)生的以太網(wǎng)幀長(zhǎng)度分別為118、246,、…,、1 398以及最大可能的1 518字節(jié)。分組中攜帶特征碼字的比例(簡(jiǎn)稱為命中率)為0%,、20%,、…、100%,,特征碼字在分組載荷中的出現(xiàn)位置隨機(jī)決定,。實(shí)驗(yàn)輸入的分組數(shù)目為4 000。
??? Intel網(wǎng)絡(luò)處理器IXP 2400的XSCAL核的工作主頻為400MHz,,每個(gè)微引擎(ME)的工作主頻為400MHz,,SRAM和DRAM的總線主頻為100MHz。實(shí)驗(yàn)數(shù)據(jù)的吞吐率" title="吞吐率">吞吐率值均取于媒體總線(Media Bus)上,,其時(shí)鐘頻率為104MHz,。
??? 圖8和圖9反映了反蠕蟲引擎的吞吐率性能。圖8(a)是命中率為0%時(shí)的吞吐率隨以太幀長(zhǎng)度變化情況,,即沒有網(wǎng)絡(luò)分組包含蠕蟲特征碼的情況,,引擎性能最后穩(wěn)定在1 400Mbps~1 500Mbps之間。圖8(b)是命中率為100%時(shí)的情況,,即每個(gè)網(wǎng)絡(luò)分組都包含蠕蟲特征碼的極端情況,。此時(shí),一旦發(fā)現(xiàn)特征碼即結(jié)束操作,,剩余的載荷內(nèi)容不必繼續(xù)檢測(cè),,吞吐率隨著以太幀長(zhǎng)度的增加而增加。圖9為吞吐率隨命中率變化情況,,隨著命中率的增加,,每幀平均不需要檢測(cè)的載荷數(shù)目增多,吞吐率增大,。圖10為不包含蠕蟲特征碼的網(wǎng)絡(luò)分組通過反蠕蟲引擎的延時(shí)情況,,隨著幀長(zhǎng)度的增加,單幀處理的平均延時(shí)呈線性平穩(wěn)增長(zhǎng),。由以上性能數(shù)據(jù)可知:在IXP2400上采用HBM算法的反蠕蟲引擎,,已經(jīng)達(dá)到了千兆以太網(wǎng)的吞吐率要求;同時(shí),,算法的吞吐率性能穩(wěn)定,,在蠕蟲爆發(fā)時(shí)(即命中率大幅度提高),性能不會(huì)有大的下降,。
?
????
?
??? 網(wǎng)絡(luò)處理器由于具有靈活的可編程特性,,適用于高速的網(wǎng)絡(luò)分組處理,。本文采用Intel IXP2400網(wǎng)絡(luò)處理器,設(shè)計(jì)和實(shí)現(xiàn)了基于深度包檢測(cè)的反蠕蟲病毒引擎,。HBM算法是對(duì)經(jīng)典BM算法的一個(gè)推廣,,算法的重點(diǎn)是以字符塊為比較單位,重新設(shè)計(jì)Delta1表和Delta2表,。同時(shí)根據(jù)網(wǎng)絡(luò)處理器的存儲(chǔ)器架構(gòu)特點(diǎn),,以允許沖突的散列運(yùn)算壓縮Delta1表,合理存放相應(yīng)的數(shù)據(jù)結(jié)構(gòu),,減少了I/O開銷,。實(shí)驗(yàn)結(jié)果表明,HBM算法有效地提高了吞吐率,并且性能指標(biāo)穩(wěn)定,,達(dá)到了高速網(wǎng)絡(luò)環(huán)境下的性能要求,。
參考文獻(xiàn)
[1] CHEN Z, LIN C, NI J.AntiWorm NPU-based Parallel?Bloom filters in Giga-Ethernet?LAN[C]//IEEE International Conference on Communications:Network Security and Information Assurance Symposium, 2006.Istanbul:IEEE Press,2006:2118-2123.
[2] SONG H,LOCKWORD J.Multi-pattern signature matching for hardware network intrusion detection systems[C]//: Global Telecommunications Conference Nov,2005:GLOBECOM’05.St. Louis: IEEE Press, 2005:5.
[3]? ?KIENZLE D M, ELDER M C. Recent worms: a survey and trends[C]//Proceedings of the 2003 ACM workshop on ?Rapid Malcode, October, 2003. Washington: ACM Press,2003: 1-10.
[4] ?WU S, MANBER U. A fast algorithm for multi-pattern searching. Technical Report TR-94-17[R]. Department of Computer Science, University of Arizona, 1994.
[5] ?LIU R, HUANG N, KAO C. A fast pattern-match engine ?for network processor-based network intrusion detection system[C]//:Information Technology: Coding and Computing 2004: Proceedings of ITCC 2004 International Conference. Las Vegas: IEEE Press, 2004:97-101.
[6] ?BOYER R, MOORE J. A fast string searching algorithm[J]. Communications of the ACM, 1977,20(10):762-772.
[7] ?FISK M,VARGHESE G.An analysis of fast string matching applied to content-based forwarding and intrusion detection. Technical Report CS2001-0670[R]. University of California-San Diego, 2002.
[8] ?COIT C, STANIFORD S, MCALERNEY J. Towards faster pattern matching for intrusion detection, or exceeding the speed of snort[C]//. Proc. of the 2nd DARPA Information Survivability Conference and Exposition:DISCEX II. Piscataway: IEEE Press, 2001:367-373.
[9] ?XU B, ZHOU X, LI J. Recursive shift indexing: A fast multi-pattern string matching algorithm[C]//Proc. of the 4th International Conference on Applied Cryptography and Network Security:ACNS 2006. Singapore: Springer,2006.