用于控制器保護(hù)的防火墻規(guī)則的三叉樹算法

傅一帆,劉小樹,劉 躍,黃 玲

（杭州和利時(shí)自動(dòng)化有限公司,浙江 杭州310018）

在分布控制系統(tǒng)DCS中曾發(fā)生過網(wǎng)絡(luò)風(fēng)暴襲擊控制器的事件?？刂破魇欠植伎刂葡到y(tǒng)的核心，一旦遭遇故障，將會(huì)造成重大的生命財(cái)產(chǎn)損失。因此如何防止網(wǎng)絡(luò)的攻擊是一個(gè)必須考慮的因素。

1 控制網(wǎng)絡(luò)的應(yīng)用特點(diǎn)與分析

分布控制系統(tǒng)中的控制器的網(wǎng)絡(luò)環(huán)境與一般互聯(lián)網(wǎng)有所不同：

(1)控制網(wǎng)絡(luò)管理相對較嚴(yán)，但是一旦發(fā)生攻擊，瞬間會(huì)造成停機(jī)等事故。一個(gè)強(qiáng)度僅6 000 pps(Packet Per Second)的攻擊會(huì)在幾百毫秒之內(nèi)就使某些控制器復(fù)位。

(2)在控制應(yīng)用中降低設(shè)備功耗對系統(tǒng)可靠性極其重要,工作溫度越高，壽命越短，約每增高 10℃，壽命降低一半，低功耗和易于自然散熱是設(shè)計(jì)考慮的重要因素。

(3)控制系統(tǒng)對可靠性設(shè)計(jì)有嚴(yán)格的要求。國際上的IEC 61508標(biāo)準(zhǔn)提出了安全完整性等級(jí)的概念，最高為4級(jí)，對于相對安全的第3級(jí)，要求系統(tǒng)每小時(shí)出現(xiàn)故障的可能性在10-7(h-1)以下,平均故障間隔時(shí)間在1 142年以上。對軟件設(shè)計(jì)也提出了相應(yīng)的規(guī)定[1]，如不能動(dòng)態(tài)申請內(nèi)存（非動(dòng)態(tài)變量）、迭代的有限使用等，尤其對程序的確定性執(zhí)行時(shí)間提出了嚴(yán)格的要求。其中控制系統(tǒng)至少要達(dá)到3級(jí)標(biāo)準(zhǔn)，安全保護(hù)系統(tǒng)要達(dá)到4級(jí)，這些都使一些原有防火墻應(yīng)用的方法受到了限制。

在傳統(tǒng)的防火墻規(guī)則匹配方法中,基于硬件的CAM（Content-Addressable Memory）[2]和 TCAM（Ternary Content Addressable Memory）方法[3]實(shí)現(xiàn)了線速處理，是防火墻規(guī)則處理中性能最好的。但該方法需要增加硬件模塊，使成本增高，熱功耗增加，TCAM的每比特的能量消耗，是SRAM的150倍[3]?；诠１淼腂SOL(Binary Search On Leaves)是一個(gè)優(yōu)秀的算法[4]，其算法復(fù)雜度為 O(log(∑wi)),其中w表示防火墻規(guī)則空間的域長，wi表示第i維的域長,BSOL的處理效率在理論上與規(guī)則數(shù)無關(guān)。還有在BSOL算法基礎(chǔ)之上,提出一種改進(jìn)的高維報(bào)文分類算法 MCBF(Multi Cuttings and Bloom Filters)[5],運(yùn)用 ASIC的并行處理，減少對哈希表的訪問次數(shù)，但這些都需要與 Bloom Filter相配才能獲得很好的效果[6],而對于 Bloom Filter，如用軟件實(shí)現(xiàn)，計(jì)算量大；而在工業(yè)控制中，增加硬件模塊，就增加功耗，同時(shí)哈希表的應(yīng)用也使計(jì)算負(fù)荷不穩(wěn)定。

本文利用控制器本身的計(jì)算能力構(gòu)建防火墻過濾功能,遵循IEC 61508安全完整性等級(jí)SIL3等標(biāo)準(zhǔn)，提出了面向集合的三叉樹算法,在對包過濾有確定性處理時(shí)間的前提上,獲得log3級(jí)的查找時(shí)間復(fù)雜度，穩(wěn)定了控制器在循環(huán)周期內(nèi)的處理負(fù)荷，對所占空間有準(zhǔn)確的上限，避免了使用動(dòng)態(tài)內(nèi)存。

2 面向集合運(yùn)算的三叉樹

定義規(guī)則時(shí)，往往會(huì)用到一段連續(xù)的空間，如一個(gè)IP網(wǎng)段、一段端口號(hào)等，如果在這連續(xù)的空間有著統(tǒng)一的處理要求，就可把這一集合當(dāng)做一個(gè)樹節(jié)點(diǎn)來處理。對于IP源地址、目的地址、端口號(hào)等構(gòu)成的多維空間的規(guī)則匹配，可用逐步降維的方法轉(zhuǎn)化為面向集合的三叉樹搜索來解決這個(gè)問題。

對集合的分類查找采用三叉樹的方法，前提條件是要查找的集合已被處理成為在空間上連續(xù)的閉區(qū)間，代表這個(gè)集合樹結(jié)點(diǎn)的關(guān)鍵字不再是一個(gè)鍵值，而是由2個(gè)鍵分別表示這個(gè)集合的閉區(qū)間的上、下界端點(diǎn)值，稱為這個(gè)集合結(jié)點(diǎn)的右鍵和左鍵。例如,在IP源地址空間上有3個(gè)網(wǎng) 段 集 ：128.0.0.11-128.0.0.16，128.0.0.40-128.0.0.45和128.0.0.51-128.0.0.53,這3個(gè)結(jié)點(diǎn)如圖1表示。

表1 一個(gè)防火墻規(guī)則表例子

使用三叉樹查找,獲得log3級(jí)的查找時(shí)間復(fù)雜度，且每步處理開銷小,但要根據(jù)安全規(guī)則構(gòu)建成規(guī)則樹，需解決規(guī)則沖突問題。

IP源、IP目的、IP協(xié)議、傳輸層端口號(hào)等組成多維歐氏空間,一條防火墻規(guī)則在多維歐氏空間構(gòu)成一個(gè)超多面體，用網(wǎng)絡(luò)包匹配規(guī)則的過程就是看它被包含在哪條規(guī)則構(gòu)成的超多面體內(nèi)。檢查防火墻規(guī)則是否沖突，就是檢查這些規(guī)則構(gòu)成的超多面體之間有無相交、包含的問題。對規(guī)則表中要去除矛盾的規(guī)則，可簡化成對規(guī)則表中的任兩條規(guī)則進(jìn)行分析。如果兩條規(guī)則發(fā)生沖突,對相交的空間進(jìn)行分割,分割后的空間劃歸為優(yōu)先級(jí)高的規(guī)則。

下面以一個(gè)有兩條規(guī)則的例子說明解決規(guī)則沖突的方法,如表1所示。假定規(guī)則序號(hào)越低優(yōu)先級(jí)越高,經(jīng)分析后逐維表示，如圖2所示。

在多維空間上，兩條規(guī)則不相沖突的充要條件是至少存在某個(gè)維，它們的規(guī)則集合互不相交。規(guī)則序號(hào)1和規(guī)則序號(hào)2所形成的空間域有相交的情況，在IP源地址的[b,c]區(qū)間、IP目的地址的[f,g]區(qū)間、協(xié)議號(hào) 6、目的端口號(hào)的[k,l]區(qū)間相交，無法確定其行動(dòng)。根據(jù)優(yōu)先級(jí)保證規(guī)則1的區(qū)間，在這4個(gè)區(qū)間內(nèi)，調(diào)整任一個(gè)都可消除沖突，因此有多個(gè)調(diào)整方案，可在IP源地址空間上把[b,c]區(qū)間從規(guī)則 2中劃出，使其IPsrc2的區(qū)間變?yōu)閇c+,d](在這里，c+=c+1，c點(diǎn)劃歸 IPsrc1集合),兩條規(guī)則互不相交,調(diào)整后的規(guī)則2的IP源地址空間如圖2 IPsr2′所示。

在消除了規(guī)則沖突后,逐維生成規(guī)則樹的次序是：IP源地址→IP目的地址→協(xié)議號(hào)→目的端口號(hào)。

規(guī)則樹生成算法描述如下：

(1)選擇IP源地址空間做第1維,根據(jù)規(guī)則集R={r1,r2,…,rN}劃分在該維若干個(gè)區(qū)間x(i,1)，x(i,2),…x(i,N′)，其中區(qū)間x(i,j)的第一個(gè)下標(biāo)i表示所在的維數(shù)序號(hào)，初始化時(shí)i=1，第二個(gè)下標(biāo)表示在該維內(nèi)相應(yīng)的區(qū)間序號(hào)，區(qū)間x(i,j)是將要生成的面向集合的三叉樹的節(jié)點(diǎn),N表示規(guī)則個(gè)數(shù),N′表示規(guī)則集在該維形成的區(qū)間個(gè)數(shù)。

(2)依次取第 1維第j個(gè)區(qū)間x(i,j),(初始化時(shí)i=1，j=1），找出與區(qū)間x(i,j)相關(guān)的所有規(guī)則集R(i,j)(其中第一個(gè)下標(biāo)i表示所在的維數(shù)序號(hào)，第二個(gè)下標(biāo)表示在該維內(nèi)相應(yīng)的區(qū)間序號(hào)），直至第1維所有區(qū)間相關(guān)的所有規(guī)則集R(1，1），R(1，2），…R(1,N′)都生成。

(3)在第1維生成平衡的面向集合的三叉樹，其樹的根節(jié)點(diǎn)即是整個(gè)規(guī)則樹的根節(jié)點(diǎn)，所有在第1維空間由三叉樹的節(jié)點(diǎn)表示的區(qū)間x(1，j)(j=1,2,…,N′)的出口都是進(jìn)入下一維空間生成子樹結(jié)構(gòu)的根節(jié)點(diǎn)。

(4)i=1。

(5)在第i維取x(i,j)節(jié)點(diǎn)相關(guān)的規(guī)則集R(i,j)，根據(jù)R(i,j)做向第(i+1)維空間的映射，如此重復(fù)直至完成在第i維所有的x(i,j)節(jié)點(diǎn)向第（i+1）維空間的映射；

(6)對第（i+1）維空間，根據(jù)第i維空間的x(i,j)節(jié)點(diǎn)相關(guān)的規(guī)則集R(i,j)，劃分在該第（i+1）維若干個(gè)區(qū)間x(i+1,1)，x(i+1,2),…x(i+1,N′′)， 如 此 重 復(fù) 直 至 完 成 在第i維所有的x(i,j)節(jié)點(diǎn)相關(guān)的規(guī)則集R(i,j)對第(i+1)維空間的劃分。

(7)對第(i+1）維空間，依次就新劃分的區(qū)間(i+1,k)，k=1，2,…,N′′， 在第i維空間相關(guān)的規(guī)則集R(i,j)基礎(chǔ)上，找出映射到第(i+1）維空間的區(qū)間x(i+1,k)相關(guān)的所有規(guī)則，形成新規(guī)則集R(i+1，k)；k=1,2,…,如此重復(fù)直至第（i+1）維所有劃分的區(qū)間都形成了新規(guī)則集。

(8)在第i維空間，以x(i,j)節(jié)點(diǎn)進(jìn)入下一維的出口作為第(i+1）維生成子樹的根，在第(i+1）維空間生成平衡的面向集合的三叉樹，如此重復(fù)直至所有第(i+1）維在步驟(6)劃分的區(qū)間都生成平衡的面向集合的三叉樹。

(9)進(jìn)入下一維，i=i+1，如果i＜4,則轉(zhuǎn)步驟(5)；否則轉(zhuǎn)步驟(10)。

(10)樹已生成，根據(jù)在第i維空間的葉節(jié)點(diǎn)x(i,j)，找到相應(yīng)的規(guī)則集R(i,j)，對葉節(jié)點(diǎn)x(i,j)設(shè)置行動(dòng)屬性值，如此重復(fù)直至所有第i維空間的葉節(jié)點(diǎn)都設(shè)置行動(dòng)屬性值，算法結(jié)束。

表2 網(wǎng)絡(luò)包處理性能比較

3 比較分析

三叉樹算法在單維空間，N條規(guī)則最多可劃分2N+1個(gè)區(qū)間，生成的節(jié)點(diǎn)數(shù)最大為2N-1個(gè),尚若N足夠大,1可忽略,三叉樹查找規(guī)則的時(shí)間復(fù)雜度為O(「log32N),在IP源地址、目的地址，目的端口號(hào)三維空間的規(guī)則匹配,單維最壞情況的時(shí)間復(fù)雜度為∑log32N，N為規(guī)則數(shù)，在三維空間最壞情況的時(shí)間復(fù)雜度為log38N3。

在查找速度上,與硬件實(shí)現(xiàn)的內(nèi)容可尋址存儲(chǔ)器CAM(Content-Addressable Memory)芯片 MCM69C232相比較[2,7],結(jié)果如表2所示。

MCM69C232芯片的匹配時(shí)間為 160 ns,在每秒有2 440連接處理時(shí)，匹配周期時(shí)間最小為200 ns，三叉樹方法為797 ns，在處理64和1 514 B長度的網(wǎng)絡(luò)包要比CAM分別增加6%和1.6%的時(shí)間開銷，有一定的性能差距。但隨著網(wǎng)絡(luò)連接數(shù)的增多，到每秒10 000個(gè)連接時(shí)，MCM69C232芯片的匹配周期時(shí)間到800 ns以上[7]，而三叉樹方法匹配周期時(shí)間不變，從成本和減少耗電等因素考慮，三叉樹方法更適于嵌入式實(shí)時(shí)控制應(yīng)用。

在SUN的SPARC平臺(tái)上與順序查找算法在100 Mb/s網(wǎng)絡(luò)上的吞吐率相比較，檢查處理能力與規(guī)則數(shù)的關(guān)系，三叉樹算法，1條規(guī)則時(shí)，吞吐率為 99.4 Mb/s，順序查找算法吞吐率為 99.2 Mb/s，兩者相差不大，三叉樹算法，配置到 43 815條規(guī)則時(shí)，仍有 99.2 Mb/s的吞吐率，而順序查找算法在配置499條規(guī)則時(shí)吞吐率就降到了34.7 Mb/s，顯示了在處理規(guī)則數(shù)量多時(shí)的性能優(yōu)勢。

三叉樹算法所占據(jù)的空間與規(guī)則數(shù)相關(guān)，在每一維最多劃分出2N-1個(gè)節(jié)點(diǎn)區(qū)間(N為規(guī)則數(shù))，在 3維空間，經(jīng)優(yōu)化后的有向圖的節(jié)點(diǎn)數(shù)小于6N。

總之，本文提出面向集合的三叉樹算法，匹配規(guī)則速度較快，占用內(nèi)存規(guī)模適度，運(yùn)行期間不用動(dòng)態(tài)申請內(nèi)存，易于可靠性分析與驗(yàn)證，適于高可靠性要求的控制應(yīng)用。

[1]International Electrotechnical Commission.Functional safety of electrical/electronic/programmable electronic safety-related System-Part3:Software Requirements.IEC 61508-3[S].Switzerland:IEC Central Office,2010.

[2]Luo Huiqian,Liu Kai.A firewall system based on contentaddressable memory and ARM[J].Computer Security,2008(5):36-38.

[3]TAYLOR D E.Survey and taxonomy of packet classification Techniques[J].ACM Computing Surveys,2005,37(3):238-275.

[4]Lu Haibin,SAHNI S.O(logW)multidimensional packet classification[J].IEEE Transactions on Networking,2007,15(2):462-472.

[5]Li Lin.Research on key techniques of firewall rule set[D].Chengdu:University of Electronic Science and Technology of China,2009.

[6]袁志堅(jiān)，陳穎文，繆嘉嘉,等.典型Bloom過濾器的研究及其數(shù)據(jù)流應(yīng)用[J].計(jì)算機(jī)工程，2009,35（7）：5-7.

[7]Motorola,Inc.MCM69C232 Advance Information 4K×64 CAM.REV 3[R].Denver:Motorola,Inc.,1998.