用于控制器保護的防火墻規則的三叉樹算法

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

（杭州和利時自動化有限公司,浙江 杭州310018）

在分布控制系統DCS中曾發生過網絡風暴襲擊控制器的事件。控制器是分布控制系統的核心，一旦遭遇故障，將會造成重大的生命財產損失。因此如何防止網絡的攻擊是一個必須考慮的因素。

1 控制網絡的應用特點與分析

分布控制系統中的控制器的網絡環境與一般互聯網有所不同：

(1)控制網絡管理相對較嚴，但是一旦發生攻擊，瞬間會造成停機等事故。一個強度僅6 000 pps(Packet Per Second)的攻擊會在幾百毫秒之內就使某些控制器復位。

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

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

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

本文利用控制器本身的計算能力構建防火墻過濾功能,遵循IEC 61508安全完整性等級SIL3等標準，提出了面向集合的三叉樹算法,在對包過濾有確定性處理時間的前提上,獲得log3級的查找時間復雜度，穩定了控制器在循環周期內的處理負荷，對所占空間有準確的上限，避免了使用動態內存。

2 面向集合運算的三叉樹

定義規則時，往往會用到一段連續的空間，如一個IP網段、一段端口號等，如果在這連續的空間有著統一的處理要求，就可把這一集合當做一個樹節點來處理。對于IP源地址、目的地址、端口號等構成的多維空間的規則匹配，可用逐步降維的方法轉化為面向集合的三叉樹搜索來解決這個問題。

對集合的分類查找采用三叉樹的方法，前提條件是要查找的集合已被處理成為在空間上連續的閉區間，代表這個集合樹結點的關鍵字不再是一個鍵值，而是由2個鍵分別表示這個集合的閉區間的上、下界端點值，稱為這個集合結點的右鍵和左鍵。例如,在IP源地址空間上有3個網 段 集 ：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個結點如圖1表示。

表1 一個防火墻規則表例子

使用三叉樹查找,獲得log3級的查找時間復雜度，且每步處理開銷小,但要根據安全規則構建成規則樹，需解決規則沖突問題。

IP源、IP目的、IP協議、傳輸層端口號等組成多維歐氏空間,一條防火墻規則在多維歐氏空間構成一個超多面體，用網絡包匹配規則的過程就是看它被包含在哪條規則構成的超多面體內。檢查防火墻規則是否沖突，就是檢查這些規則構成的超多面體之間有無相交、包含的問題。對規則表中要去除矛盾的規則，可簡化成對規則表中的任兩條規則進行分析。如果兩條規則發生沖突,對相交的空間進行分割,分割后的空間劃歸為優先級高的規則。

下面以一個有兩條規則的例子說明解決規則沖突的方法,如表1所示。假定規則序號越低優先級越高,經分析后逐維表示，如圖2所示。

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

在消除了規則沖突后,逐維生成規則樹的次序是：IP源地址→IP目的地址→協議號→目的端口號。

規則樹生成算法描述如下：

(1)選擇IP源地址空間做第1維,根據規則集R={r1,r2,…,rN}劃分在該維若干個區間x(i,1)，x(i,2),…x(i,N′)，其中區間x(i,j)的第一個下標i表示所在的維數序號，初始化時i=1，第二個下標表示在該維內相應的區間序號，區間x(i,j)是將要生成的面向集合的三叉樹的節點,N表示規則個數,N′表示規則集在該維形成的區間個數。

(2)依次取第 1維第j個區間x(i,j),(初始化時i=1，j=1），找出與區間x(i,j)相關的所有規則集R(i,j)(其中第一個下標i表示所在的維數序號，第二個下標表示在該維內相應的區間序號），直至第1維所有區間相關的所有規則集R(1，1），R(1，2），…R(1,N′)都生成。

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

(4)i=1。

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

(6)對第（i+1）維空間，根據第i維空間的x(i,j)節點相關的規則集R(i,j)，劃分在該第（i+1）維若干個區間x(i+1,1)，x(i+1,2),…x(i+1,N′′)， 如 此 重 復 直 至 完 成 在第i維所有的x(i,j)節點相關的規則集R(i,j)對第(i+1)維空間的劃分。

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

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

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

(10)樹已生成，根據在第i維空間的葉節點x(i,j)，找到相應的規則集R(i,j)，對葉節點x(i,j)設置行動屬性值，如此重復直至所有第i維空間的葉節點都設置行動屬性值，算法結束。

表2 網絡包處理性能比較

3 比較分析

三叉樹算法在單維空間，N條規則最多可劃分2N+1個區間，生成的節點數最大為2N-1個,尚若N足夠大,1可忽略,三叉樹查找規則的時間復雜度為O(「log32N),在IP源地址、目的地址，目的端口號三維空間的規則匹配,單維最壞情況的時間復雜度為∑log32N，N為規則數，在三維空間最壞情況的時間復雜度為log38N3。

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

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

在SUN的SPARC平臺上與順序查找算法在100 Mb/s網絡上的吞吐率相比較，檢查處理能力與規則數的關系，三叉樹算法，1條規則時，吞吐率為 99.4 Mb/s，順序查找算法吞吐率為 99.2 Mb/s，兩者相差不大，三叉樹算法，配置到 43 815條規則時，仍有 99.2 Mb/s的吞吐率，而順序查找算法在配置499條規則時吞吐率就降到了34.7 Mb/s，顯示了在處理規則數量多時的性能優勢。

三叉樹算法所占據的空間與規則數相關，在每一維最多劃分出2N-1個節點區間(N為規則數)，在 3維空間，經優化后的有向圖的節點數小于6N。

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

[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]袁志堅，陳穎文，繆嘉嘉,等.典型Bloom過濾器的研究及其數據流應用[J].計算機工程，2009,35（7）：5-7.

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