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

1 控制網(wǎng)絡(luò)的應(yīng)用特點與分析
    分布控制系統(tǒng)中的控制器的網(wǎng)絡(luò)環(huán)境與一般互聯(lián)網(wǎng)有所不同：
    (1)控制網(wǎng)絡(luò)管理相對較嚴(yán)，但是一旦發(fā)生攻擊，瞬間會造成停機等事故。一個強度僅6 000 pps(Packet Per Second)的攻擊會在幾百毫秒之內(nèi)就使某些控制器復(fù)位。
    (2)在控制應(yīng)用中降低設(shè)備功耗對系統(tǒng)可靠性極其重要,工作溫度越高，壽命越短，約每增高10℃，壽命降低一半，低功耗和易于自然散熱是設(shè)計考慮的重要因素。
    (3)控制系統(tǒng)對可靠性設(shè)計有嚴(yán)格的要求。國際上的IEC 61508標(biāo)準(zhǔn)提出了安全完整性等級的概念，最高為4級，對于相對安全的第3級，要求系統(tǒng)每小時出現(xiàn)故障的可能性在10-7(h-1)以下,平均故障間隔時間在1 142年以上。對軟件設(shè)計也提出了相應(yīng)的規(guī)定[1]，如不能動態(tài)申請內(nèi)存（非動態(tài)變量）、迭代的有限使用等，尤其對程序的確定性執(zhí)行時間提出了嚴(yán)格的要求。其中控制系統(tǒng)至少要達到3級標(biāo)準(zhǔn)，安全保護系統(tǒng)要達到4級，這些都使一些原有防火墻應(yīng)用的方法受到了限制。
    在傳統(tǒng)的防火墻規(guī)則匹配方法中,基于硬件的CAM（Content-Addressable Memory）[2]和TCAM（Ternary Content Addressable Memory）方法[3]實現(xiàn)了線速處理，是防火墻規(guī)則處理中性能最好的。但該方法需要增加硬件模塊，使成本增高，熱功耗增加，TCAM的每比特的能量消耗，是SRAM的150倍[3]。基于哈希表的BSOL(Binary Search On Leaves)是一個優(yōu)秀的算法[4]，其算法復(fù)雜度為O(log(∑wi)),其中w表示防火墻規(guī)則空間的域長，wi表示第i維的域長,BSOL的處理效率在理論上與規(guī)則數(shù)無關(guān)。還有在BSOL算法基礎(chǔ)之上,提出一種改進的高維報文分類算法MCBF(Multi Cuttings and Bloom Filters)[5],運用ASIC的并行處理，減少對哈希表的訪問次數(shù)，但這些都需要與Bloom Filter相配才能獲得很好的效果[6],而對于Bloom Filter，如用軟件實現(xiàn)，計算量大；而在工業(yè)控制中，增加硬件模塊，就增加功耗，同時哈希表的應(yīng)用也使計算負荷不穩(wěn)定。
    本文利用控制器本身的計算能力構(gòu)建防火墻過濾功能,遵循IEC 61508安全完整性等級SIL3等標(biāo)準(zhǔn)，提出了面向集合的三叉樹算法,在對包過濾有確定性處理時間的前提上,獲得log3級的查找時間復(fù)雜度，穩(wěn)定了控制器在循環(huán)周期內(nèi)的處理負荷，對所占空間有準(zhǔn)確的上限，避免了使用動態(tài)內(nèi)存。
2 面向集合運算的三叉樹
    定義規(guī)則時，往往會用到一段連續(xù)的空間，如一個IP網(wǎng)段、一段端口號等，如果在這連續(xù)的空間有著統(tǒng)一的處理要求，就可把這一集合當(dāng)做一個樹節(jié)點來處理。對于IP源地址、目的地址、端口號等構(gòu)成的多維空間的規(guī)則匹配，可用逐步降維的方法轉(zhuǎn)化為面向集合的三叉樹搜索來解決這個問題。
    對集合的分類查找采用三叉樹的方法，前提條件是要查找的集合已被處理成為在空間上連續(xù)的閉區(qū)間，代表這個集合樹結(jié)點的關(guān)鍵字不再是一個鍵值，而是由2個鍵分別表示這個集合的閉區(qū)間的上、下界端點值，稱為這個集合結(jié)點的右鍵和左鍵。例如,在IP源地址空間上有3個網(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個結(jié)點如圖1表示。

    使用三叉樹查找,獲得log3級的查找時間復(fù)雜度，且每步處理開銷小,但要根據(jù)安全規(guī)則構(gòu)建成規(guī)則樹，需解決規(guī)則沖突問題。
    IP源、IP目的、IP協(xié)議、傳輸層端口號等組成多維歐氏空間,一條防火墻規(guī)則在多維歐氏空間構(gòu)成一個超多面體，用網(wǎng)絡(luò)包匹配規(guī)則的過程就是看它被包含在哪條規(guī)則構(gòu)成的超多面體內(nèi)。檢查防火墻規(guī)則是否沖突，就是檢查這些規(guī)則構(gòu)成的超多面體之間有無相交、包含的問題。對規(guī)則表中要去除矛盾的規(guī)則，可簡化成對規(guī)則表中的任兩條規(guī)則進行分析。如果兩條規(guī)則發(fā)生沖突,對相交的空間進行分割,分割后的空間劃歸為優(yōu)先級高的規(guī)則。
    下面以一個有兩條規(guī)則的例子說明解決規(guī)則沖突的方法,如表1所示。假定規(guī)則序號越低優(yōu)先級越高,經(jīng)分析后逐維表示，如圖2所示。

    在多維空間上，兩條規(guī)則不相沖突的充要條件是至少存在某個維，它們的規(guī)則集合互不相交。規(guī)則序號1和規(guī)則序號2所形成的空間域有相交的情況，在IP源地址的[b, c]區(qū)間、IP目的地址的[f,g]區(qū)間、協(xié)議號6、目的端口號的[k, l]區(qū)間相交，無法確定其行動。根據(jù)優(yōu)先級保證規(guī)則1的區(qū)間，在這4個區(qū)間內(nèi)，調(diào)整任一個都可消除沖突，因此有多個調(diào)整方案，可在IP源地址空間上把[b, c]區(qū)間從規(guī)則2中劃出，使其IPsrc2的區(qū)間變?yōu)閇c+,d](在這里，c+=c+1，c點劃歸IPsrc1集合),兩條規(guī)則互不相交,調(diào)整后的規(guī)則2的IP源地址空間如圖2 IPsr2′所示。
　在消除了規(guī)則沖突后,逐維生成規(guī)則樹的次序是：IP源地址→IP目的地址→協(xié)議號→目的端口號。
    規(guī)則樹生成算法描述如下：
    (1)選擇IP源地址空間做第1維,根據(jù)規(guī)則集R={r1,r2,…,rN}劃分在該維若干個區(qū)間x(i,1)，x(i,2),…x(i,N′)，其中區(qū)間x(i,j)的第一個下標(biāo)i表示所在的維數(shù)序號，初始化時i=1，第二個下標(biāo)表示在該維內(nèi)相應(yīng)的區(qū)間序號，區(qū)間x(i,j)是將要生成的面向集合的三叉樹的節(jié)點,N表示規(guī)則個數(shù),N′表示規(guī)則集在該維形成的區(qū)間個數(shù)。
    (2)依次取第1維第j個區(qū)間x(i,j),(初始化時i=1，j=1），找出與區(qū)間x(i,j)相關(guān)的所有規(guī)則集R(i,j)(其中第一個下標(biāo)i表示所在的維數(shù)序號，第二個下標(biāo)表示在該維內(nèi)相應(yīng)的區(qū)間序號），直至第1維所有區(qū)間相關(guān)的所有規(guī)則集R(1，1），R(1，2），…R(1,N′)都生成。
    (3)在第1維生成平衡的面向集合的三叉樹，其樹的根節(jié)點即是整個規(guī)則樹的根節(jié)點，所有在第1維空間由三叉樹的節(jié)點表示的區(qū)間x(1，j)(j=1,2,…,N′)的出口都是進入下一維空間生成子樹結(jié)構(gòu)的根節(jié)點。
    (4)i=1。
    (5)在第i維取x(i,j)節(jié)點相關(guān)的規(guī)則集R(i,j)，根據(jù)R(i,j)做向第(i+1)維空間的映射，如此重復(fù)直至完成在第i維所有的x(i,j)節(jié)點向第（i+1）維空間的映射；
    (6)對第（i+1）維空間，根據(jù)第i維空間的x(i,j)節(jié)點相關(guān)的規(guī)則集R(i,j)， 劃分在該第（i+1）維若干個區(qū)間x(i+1,1)，x(i+1,2),…x(i+1,N′′)，如此重復(fù)直至完成在第i維所有的x(i,j)節(jié)點相關(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é)點進入下一維的出口作為第(i+1）維生成子樹的根，在第(i+1）維空間生成平衡的面向集合的三叉樹，如此重復(fù)直至所有第(i+1）維在步驟(6)劃分的區(qū)間都生成平衡的面向集合的三叉樹。
    (9)進入下一維，i=i+1，如果i<4,則轉(zhuǎn)步驟(5)；否則轉(zhuǎn)步驟(10)。
    (10)樹已生成，根據(jù)在第i維空間的葉節(jié)點x(i,j)，找到相應(yīng)的規(guī)則集R(i,j)，對葉節(jié)點x(i,j)設(shè)置行動屬性值，如此重復(fù)直至所有第i維空間的葉節(jié)點都設(shè)置行動屬性值，算法結(jié)束。
3 比較分析
    三叉樹算法在單維空間，N條規(guī)則最多可劃分2N+1個區(qū)間，生成的節(jié)點數(shù)最大為2N-1個,尚若N足夠大,1可忽略,三叉樹查找規(guī)則的時間復(fù)雜度為O(「log32N), 在IP源地址、目的地址，目的端口號三維空間的規(guī)則匹配,單維最壞情況的時間復(fù)雜度為&sum;log32N，N為規(guī)則數(shù)，在三維空間最壞情況的時間復(fù)雜度為log38N3。
    在查找速度上,與硬件實現(xiàn)的內(nèi)容可尋址存儲器CAM (Content-Addressable Memory)芯片MCM69C232相比較[2,7],結(jié)果如表2所示。

    MCM69C232芯片的匹配時間為160 ns,在每秒有2 440連接處理時，匹配周期時間最小為200 ns，三叉樹方法為797 ns，在處理64和1 514 B長度的網(wǎng)絡(luò)包要比CAM分別增加6%和1.6%的時間開銷，有一定的性能差距。但隨著網(wǎng)絡(luò)連接數(shù)的增多，到每秒10 000個連接時，MCM69C232芯片的匹配周期時間到800 ns以上[7]，而三叉樹方法匹配周期時間不變，從成本和減少耗電等因素考慮，三叉樹方法更適于嵌入式實時控制應(yīng)用。
    在SUN的SPARC平臺上與順序查找算法在100 Mb/s網(wǎng)絡(luò)上的吞吐率相比較，檢查處理能力與規(guī)則數(shù)的關(guān)系，三叉樹算法，1條規(guī)則時，吞吐率為99.4 Mb/s，順序查找算法吞吐率為99.2 Mb/s，兩者相差不大，三叉樹算法，配置到43 815條規(guī)則時，仍有99.2 Mb/s的吞吐率，而順序查找算法在配置499條規(guī)則時吞吐率就降到了34.7 Mb/s，顯示了在處理規(guī)則數(shù)量多時的性能優(yōu)勢。
    三叉樹算法所占據(jù)的空間與規(guī)則數(shù)相關(guān)，在每一維最多劃分出2N-1個節(jié)點區(qū)間(N為規(guī)則數(shù))，在3維空間，經(jīng)優(yōu)化后的有向圖的節(jié)點數(shù)小于6N。
    總之，本文提出面向集合的三叉樹算法，匹配規(guī)則速度較快，占用內(nèi)存規(guī)模適度，運行期間不用動態(tài)申請內(nèi)存，易于可靠性分析與驗證，適于高可靠性要求的控制應(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] 袁志堅，陳穎文，繆嘉嘉,等.典型Bloom過濾器的研究及其數(shù)據(jù)流應(yīng)用[J].計算機工程，2009,35（7）：5-7.
[7] Motorola, Inc. MCM69C232 Advance Information 4K&times;64 CAM.REV 3[R].Denver: Motorola,Inc.,1998.