基于默認規(guī)則及沖突檢測的防火墻規(guī)則優(yōu)化算法

高　飛，曹　波，莊　嚴

(國網湖北省電力公司信息通信公司，湖北　宜昌　443000)

?

基于默認規(guī)則及沖突檢測的防火墻規(guī)則優(yōu)化算法

高飛，曹波，莊嚴

(國網湖北省電力公司信息通信公司，湖北宜昌443000)

摘要：防火墻過濾規(guī)則集的日益增大以及規(guī)則間存在的相互沖突嚴重影響了網絡的性能。對防火墻匹配優(yōu)化算法進行研究和改進，在使用統(tǒng)計分析方法提高了規(guī)則調整動態(tài)性的基礎上，結合規(guī)則間的沖突檢測進行預優(yōu)化，同時提出將默認規(guī)則分離出一部分進行合并操作，將生成的新規(guī)則參與原規(guī)則集的次序調整。仿真結果證明該方法有效的降低了防火墻規(guī)則匹配時間，提高了防火墻性能。

關鍵詞：防火墻；規(guī)則匹配；沖突檢測；默認規(guī)則；無沖突區(qū)域

防火墻作為內部網和外部網之間的唯一出入口，在保護內部網絡不受外界侵犯的同時，其性能對網絡有效數(shù)據的傳輸產生很大影響，如何防止火墻成為網絡通信的瓶頸，一直是網絡安全領域的研究熱點，目前的問題主要集中在兩個方面，一是隨著網絡環(huán)境的日益復雜和防火墻規(guī)則集的日益增大，規(guī)則間的相互沖突情況也越來越嚴重，增加了防火墻管理的難度；二是如何更有效的對防火墻規(guī)則集進行優(yōu)化，壓縮防火墻規(guī)則匹配時間，降低其對網絡有效數(shù)據傳輸?shù)挠绊?。文獻[1]提出了一種防火墻規(guī)則沖突檢測算法，能夠實現(xiàn)規(guī)則的無沖突修改，但沒有考慮到規(guī)則本身次序調整的效率；文獻[2]提出了將一種防火墻規(guī)則沖突檢測的可視化方案，一定程度上提高了操作的便捷性；文獻[3]給出了一種通過防火墻規(guī)則集的完整性來篩除異常規(guī)則的方法，但算法的動態(tài)性能較差，尤其對于規(guī)則集非常龐大的防火墻，此算法并不適用；文獻[4]將統(tǒng)計分析方法運用到規(guī)則集的優(yōu)化上，一定程度上提高了防火墻的性能，但忽視了沖突檢測以及默認規(guī)則在優(yōu)化過程中起到的積極作用。

本文提出將規(guī)則沖突檢測運用到防火墻規(guī)則集的預優(yōu)化當中，并設計了一種無沖突合并算法，將默認規(guī)則分離出一部分，添加到規(guī)則集中參與次序調整，從而形成了一種新的防火墻優(yōu)化算法，有效的減少了防火墻規(guī)則集的規(guī)模，降低了規(guī)則匹配時間，提高了防火墻的性能。

1統(tǒng)計分析在規(guī)則優(yōu)化中的應用

防火墻規(guī)則集的動態(tài)調整是影響防火墻性能的關鍵環(huán)節(jié)，根據過濾規(guī)則的使用頻率，對規(guī)則進行動態(tài)排序，使得高匹配概率的規(guī)則位于規(guī)則集的最前列，以提高匹配的成功率，降低耗時，從而實現(xiàn)對防火墻的優(yōu)化。

在對規(guī)則使用頻率進行統(tǒng)計分析時，通常存在兩種方法，一是根據全部的數(shù)據流量進行統(tǒng)計，二是根據一段時期內的數(shù)據流量進行統(tǒng)計，該段時期既可以是臨近統(tǒng)計點的一個時間段，也可以是指定的某個歷史時期。第一種方式更多的側重于數(shù)據的全面性，力爭實現(xiàn)排序結果的全局最優(yōu)，將全部歷史數(shù)據當中匹配成功頻率最高的規(guī)則排在最前列，理所當然的其匹配時間將會減少，但該方法的缺點也是很明顯的，因其假設某條規(guī)則被匹配成功的概率在整個歷史時期不會發(fā)生變化，由于受到歷史數(shù)據龐大的基數(shù)影響，那些陳舊的規(guī)則依舊被排序在最前端，而新出現(xiàn)的規(guī)則雖然可能在短時間內匹配成功概率最高，但依舊被排序在靠后的位置，影響了防火墻對當前數(shù)據流量的靈敏度；第二種方法只考慮某段時期內的數(shù)據流量，較少的數(shù)據量可能會影響統(tǒng)計分析的結果，但可以較為靈敏的反應當前網絡數(shù)據狀況，因此得到了更多的應用。文獻[5]提出了一種基于可變時間的優(yōu)化算法，將網絡在不同時間段的流量大小作為影響因子參與到優(yōu)化過程中，設置系數(shù)M=防火墻最大處理流量/當前流量，而采樣時間Tn=M×Tn-1，這樣使得采樣時間的大小更加符合本時間段的數(shù)據流量大小，改進了防火墻對當前網絡狀況的敏感度。本文就是以該方法為研究對象，在其基礎上將沖突檢測與默認規(guī)則有機結合，形成新的優(yōu)化算法。

2規(guī)則沖突檢測實現(xiàn)對規(guī)則集的預優(yōu)化

2.1　防火墻規(guī)則間的關系

防火墻規(guī)則一般如表1所示的七個字段組成[6]。

表1　防火墻參數(shù)模型

發(fā)送方將自身的IP地址及掩碼封裝進源地址字段，將接收方的IP地址封裝進目的地址字段；源端口和目的端口同具體的服務進程相關聯(lián)，如表中的目的端口：53表示DNS服務；協(xié)議字段指的是交付上層哪個協(xié)議進行后續(xù)處理；動作字段表示防火墻對符合該規(guī)則的數(shù)據包的處理方法。對于Ti3～Ti6的取值范圍，可用一閉區(qū)間[S，E] 表示，如對于Ti3，可表示為[S(Ti3)，E(Ti3)]，由此，一條規(guī)則可歸納為下式

Ri=

(1)

表2給出了根據式(1)格式的防火墻規(guī)則集列表。

表2　防火墻規(guī)則集示例

防火墻根據上述規(guī)則對接收到的數(shù)據包進行匹配檢測，而每條規(guī)則所匹配的數(shù)據可視作一個集合，則規(guī)則之間的關系就可以轉化為集合間的關系表示，根據集合的概念和規(guī)則，任意兩個非空集合之間的關系都可劃分為包含、被包含、分離、相等、相交[7-8]。

設某規(guī)則Rx匹配的集合為Sx，位于Rx之前的任意規(guī)則BeforeRx匹配的集合為BeforeSx，則有In-Sx=Sx∩BeforeSx；Com-Sx=Sx-In-Sx；Com-BeforeSx=BeforeSx-In-Sx，其中In-Sx為Sx與BeforeSx的交集，Com-Sx為Sx相對于In-Sx的補集，Com-BeforeSx為BeforeSx相對于In-Sx的補集。

則上述五種關系可表述為[9]：

1) 包含：In-Sx≠0andCom-BeforeSx=0andCom-Sx≠0；

2) 被包含：In-Sx≠0andCom-BeforeSx≠0andCom-Sx=0；

3) 分離：In-Sx=0；

4) 相交：In-Sx≠0andCom-BeforeSx≠0andCom-Sx≠0；

5) 相等：Sx=BeforeSx。

2.2　防火墻規(guī)則沖突類型

由上述規(guī)則間的關系可以推導出以下四種不同的沖突情況[4]

1) 影子沖突：Sx?BeforeSx，即當前此規(guī)則完全被之前的某條規(guī)則所覆蓋；

2) 冗余沖突：Sx?BeforeSx，且動作相同，即當前規(guī)則包含了之前的某條規(guī)則，且處理方案一致，形成冗余；

3) 泛化沖突：Sx?BeforeSx，且動作相異，即當前規(guī)則包含了之前的某條規(guī)則，且處理方案不同，造成沖突；

4) 關聯(lián)沖突：Sx∩BeforeSx≠φ，且動作相異，即當前規(guī)則與之前的某條規(guī)則存在交集，且處理方案不同，造成沖突；

隨著防火墻工作時間的延續(xù)，其規(guī)則集也日益積累不斷擴充，導致規(guī)則間的沖突概率也隨之增大，這給防火墻的正常運轉造成了很大的影響和隱患，額外消耗資源及規(guī)則配置出錯的情況將會日益加重，因此，規(guī)則沖突的檢測對于防火墻的維護而言是非常必要的。

3基于默認規(guī)則的防火墻優(yōu)化

3.1　添加默認規(guī)則的可行性

衡量防火墻性能好壞的一個重要標準是平均匹配次數(shù)[3]，其公式可表示為

(2)

i為規(guī)則序號，pi為該規(guī)則的匹配概率。顯然，優(yōu)化工作的目標就是盡可能降低W，提高運行效率。由式(2)可以看出，對W產生影響的因素有兩點，一是規(guī)則數(shù)量n，二是規(guī)則所處的位置i及其匹配概率pi，且i值越大，對W的影響越大。

在規(guī)則集中，默認規(guī)則為最后一項，即i值最大，與默認規(guī)則相匹配的數(shù)據流需要遍歷整個規(guī)則集才能被默認規(guī)則命中，并且由于默認規(guī)則不參與規(guī)則集的次序調整，可能會對防火墻的性能產生很大影響，形成瓶頸效應。如果在默認規(guī)則中發(fā)現(xiàn)某些規(guī)則具有較高的匹配命中次數(shù)，則可以考慮將其分離出來，添加至規(guī)則集中參與次序調整，可以有效的降低W值，但這種做法需要滿足兩個前提條件。

1) 添加的規(guī)則不可同原有規(guī)則相沖突，原因上文已述，這里不再贅述；

2) 添加新的規(guī)則無疑會增大規(guī)則數(shù)量n的值，從而增大W，因此必須考慮添加規(guī)則的匹配概率pi，其值過小時不得添加，可用以下公式來衡量

α=W-Wnew=(n+1-m)·p2-p1-p3-…-pk

(3)

式中：α為衡量因子，其值為W原值與新值的差；n為規(guī)則總數(shù)；m為添加規(guī)則的序號；p1為原默認規(guī)則匹配概率；p2為添加規(guī)則匹配概率；3…k為添加規(guī)則后原規(guī)則序號。很明顯，只有當α>0時，添加默認規(guī)則才有意義。

3.2　無沖突的合并規(guī)則

在向原規(guī)則集添加新規(guī)則之前，先要提取防火墻日志中匹配默認規(guī)則的數(shù)據包，從中解析出規(guī)則集，再對該規(guī)則集進行整合壓縮，從而減少待添加規(guī)則的數(shù)量以及達到設定的匹配概率，即規(guī)則的合并過程；同時還必須保證合并過后的新規(guī)則不能與原規(guī)則集相沖突，即判斷規(guī)則是否可合并，待可合并的新規(guī)則數(shù)量達到了設定值后，再進行合并操作。

兩條規(guī)則Ri、Rj之間無沖突的充分必要條件為Ri、Rj不相關。假設Rj與Ri具有相同的協(xié)議類型，即Ti2=Tj2，且完全從屬于下列任一區(qū)域中：

(0.0.0.0，S(T3))or(E(T3)，

255.255.255.255)or(0，S(T4))or(E(T4)，

65535)or(0.0.0.0，S(T5))or(E(T5)，

255.255.255.255)or(E(T6)，65535)，則Rj與Ri不相關，即Rj與Ri無沖突，而以上各區(qū)域則稱為無沖突域。

對于Ti2=Tj2且Ti7=Tj7的兩條規(guī)則Ri、Rj其合并過程按以下操作進行：

S(T3)=min(S(Ti3)，S(Tj3))；

E(T3)=max(E(Ti3)，E(Tj3))；

S(T4)=min(S(Ti4)，S(Tj4))；

E(T4)=max(E(Ti4)，E(Tj4))；

S(T5)=min(S(Ti5)，S(Tj5))；

E(T5)=max(E(Ti5)，E(Tj5))；

S(T6)=min(S(Ti6)，S(Tj6))；

E(T6)=max(E(Ti6)，E(Tj6))；

T2=Ti2=Tj2；T7=Ti7=Tj7

得到Rk=為合并后的新規(guī)則，可以明顯看出，Rk為Ri、Rj的父規(guī)則，其匹配的數(shù)據包也包含了Ri、Rj匹配的數(shù)據包。

定義4.1若Ri、Rj同規(guī)則R不相關，則合并后的Rk也同R不相關。

證：設Ri、Rj處于R的某一無沖突區(qū)域內，如(0.0.0.0，S(T3))，則有

max(E(Ti3)，E(Tj3))∈(0.0.0.0，S(T3)，

即新規(guī)則的T3域仍然處在R的無沖突區(qū)域(0.0.0.0，S(T3))內，其他域同理得證。

3.3　本文優(yōu)化算法

本文的優(yōu)化算法分為兩個步驟：① 通過規(guī)則沖突檢測實現(xiàn)預優(yōu)化，并對統(tǒng)計分析算法提出約束條件；② 從默認規(guī)則中分離出符合條件的新規(guī)則集，添加至原規(guī)則集中，進一步提高防火墻規(guī)則的匹配效率。

預優(yōu)化的目的是減少規(guī)則集中無效規(guī)則的數(shù)量，降低優(yōu)化算法的計算量。預優(yōu)化對象為規(guī)則集內存在的影子沖突和冗余沖突，算法如下：

1) 對于造成影子沖突的規(guī)則Ri，將其刪除；

2) 對于造成冗余沖突的規(guī)則Ri，若Ri沒有與其后的規(guī)則產生泛化沖突，則刪除Ri。

根據統(tǒng)計分析優(yōu)化算法的規(guī)則，對于高匹配概率的某條規(guī)則Ri，在重新排序中應將其位置提前，但若Ri同時會造成泛化/關聯(lián)沖突，則單一的調換其位置可能會造成防火墻原始語意的改變，從而影響了過濾效果，因此，設定約束條件為：若Ri、Rj存在泛化/關聯(lián)沖突，則不可將其位置互換；若Ri、Rj存在泛化/關聯(lián)沖突，而Ri為高概率匹配規(guī)則需要調前，則Ri與Rj應同時調前，如圖1所示。

在完成了預優(yōu)化之后，下一步則可進行默認規(guī)則的分離、合并及添加過程。具體步驟如下：

1) 根據不同的Ti2將原規(guī)則表分解成TCP表、UDP表等，同時將防火墻日志中提取出的同默認規(guī)則匹配的規(guī)則集按照同樣的方式分解，如AddTCP表、AddUDP表等(以下以TCP表為例)；

2) 進行規(guī)則合并的可行性判斷，將AddTCP表中任意兩條規(guī)則Ri、Rj組合，同TCP表中的每條規(guī)則進行對比，若均處于某條規(guī)則的無沖突域中，則Ri、Rj可合并，記為Ri?Rj=1；否則不可合并，記為Ri?Rj=0，以此關系數(shù)據構造關系數(shù)組Rel-TCP[i][j]；

3) 對于AddTCP表中的規(guī)則，合并過的標記為1，否則為0，以此構造標記數(shù)組Com-TCP[]；

4) 對于AddTCP表中的未被合并過的規(guī)則Ri，查詢關系數(shù)組Rel-TCP[i][j]可得到所有能與Ri合并的規(guī)則，將規(guī)則號記錄在數(shù)組AddCOM-TCP[]中；

5) 對AddCOM-TCP[]標記的規(guī)則進行兩兩組合分析，將不可合并的規(guī)則全部淘汰刪除，保證AddCOM-TCP[]數(shù)組中任意兩條規(guī)則均可合并；

6) 按上文提出的無沖突合并方法將進行合并，并在Com-TCP[]中將合并后的新規(guī)則標記為1；

7) 對于合并后的規(guī)則，若符合式(3)指明的前提條件，則添加至原規(guī)則集中，否則不予添加；

8) 返回步驟(4)繼續(xù)檢索AddTCP表，直至遍歷完成。

4仿真試驗及分析

本文設定的測試規(guī)則集涵蓋了全部沖突類型，并且從網絡數(shù)據流量的真實度考慮，為少數(shù)規(guī)則匹配了大量的數(shù)據包，以TCP表為例，初始規(guī)則集如表3所示。

表3　初始規(guī)則集

經沖突檢測系統(tǒng)檢測，發(fā)現(xiàn)存在沖突關系如下

表4　規(guī)則沖突檢測結果

經過預優(yōu)化處理后，得到規(guī)則集如下

表5　預處理后的規(guī)則集

同時從防火墻日志中得到的與默認規(guī)則匹配的數(shù)據表如下

表6　與默認規(guī)則匹配的數(shù)據表

根據上文提出的合并算法，對表5、表6進行對比分析及合并優(yōu)化，產生的新的規(guī)則為

Rnew=，同時也將被合并的幾條規(guī)則的匹配次數(shù)累加，即為Rnew的匹配次數(shù)，將Rnew添加進原始規(guī)則集TCP表中，并按前文所述的排序算法及約束條件進行次序調整，排序后結果如表7所示。

表7　重排序后的規(guī)則集

根據前文給出的規(guī)則間的關系和對規(guī)則沖突的定義可以看出，新的規(guī)則集中沒有出現(xiàn)規(guī)則的沖突情況，驗證了無沖突合并算法的有效性。在將新規(guī)則添加至4號位置之前，原規(guī)則集按照統(tǒng)計分析方法進行排序后，其平均匹配次數(shù)W1=4.66712，在加入新規(guī)則后，再次計算平均匹配次數(shù)為W2=3.75451。

從實驗結果可以看出，在添加了合并規(guī)則之后，新的規(guī)則集的平均匹配次數(shù)有了明顯的降低，由此可以證明該優(yōu)化算法的有效性，雖然不能排除在某些特殊情況下，按照本文算法合并后的規(guī)則無法滿足添加入規(guī)則集的條件，從而導致一定的資源浪費，但從網絡數(shù)據流量的整體特點的角度來評價，該優(yōu)化方法依舊具有較強的適用性。

5結束語

本文首先對防火墻規(guī)則集常用的統(tǒng)計分析優(yōu)化算法進行研究，并結合數(shù)學集合的概念，總結出防火墻規(guī)則間存在的五類不同關系，以此為基礎推導出四種類型的規(guī)則沖突，提出利用沖突檢測實現(xiàn)防火墻規(guī)則集的預優(yōu)化以及對統(tǒng)計分析優(yōu)化算法形成約束條件；隨后提出一種無沖突的合并規(guī)則，將默認規(guī)則中符合條件的規(guī)則分離出來并進行合并操作，形成新的有效規(guī)則，參與到統(tǒng)計分析優(yōu)化算法的動態(tài)次序調整中。經實驗證明，該優(yōu)化算法有效的降低了防火墻規(guī)則的平均匹配次數(shù)，提高了防火墻性能。

參考文獻：

[1]張昭理，洪帆，肖海軍.一種防火墻規(guī)則沖突檢測算法[J].計算機工程與應用， 2007，43(15)：111-117.

[2]UI-HYONG KIM， JUNG-MIN KANG， JAE-SUNG LEE，et al. Practical firewall policy inspection using anomaly detection and its visualization[J]. Multimedia Tools and Applications 2014，2(71)： 627-641.

[3]AHMED KHOUMSI，WADIE KROMBI.Mohammed Erradi A Formal Approach to Verify Completeness and Detect Anomalies in Firewall Security Policies[C]// Foundations and Practice of Security Lecture Notes in Computer Science， 2015(8 930)：221-236.

[4]MYUNG KUN，YOON SHIGANG，CHEN ZHAN ZHANG.Reducing the Size of Rule Set in a Firewall[C]//IEEE International Conference on Com-munications， 2012：

1 274-1 279.

[5]莊冠夏.防火墻規(guī)則沖突檢測和次序優(yōu)化的研究與實現(xiàn)[D].上海：華東師范大學，2011.

[6]胡偉，段金蓉，范敏.基于統(tǒng)計分析的動態(tài)過濾規(guī)則優(yōu)化的研究[J].信息安全，2008，24(2)：102-103.

[7]馬維晏，李忠誠.基于流的網絡流量特征分析[J].小型微型計算機系統(tǒng)，2009，9(10)：54-58.

[8]李鑫，季振洲，劉韋辰，等.防火墻過濾規(guī)則集沖突檢測算法[J].北京郵電大學學報， 2011，29(4)： 90-93.

[9]D WANG， R HAO， D LEE. Fault detection in rule-based software systems[J]. Information and Software Technology，2012，45(12)：865-871.

歡迎訂閱《安徽理工大學學報(自然科學版)》，歡迎投稿

《安徽理工大學學報(自然科學版)》1981年創(chuàng)刊，季刊，每期定價5.00元，全年定價20.00元。《安徽理工大學學報(自然科學版)》為安徽理工大學主辦的綜合性學術刊物，主要刊載地質工程、環(huán)境工程、測繪工程、采礦工程、安全工程、信息管理與信息系統(tǒng)、土木工程、建筑學、機械工程、測控技術與儀器、自動化、電子信息工程、計算機科學與技術、礦物加工工程、化學工程與工藝、彈藥工程與爆炸技術、制藥工程、信息與計算科學、應用物理學、醫(yī)學以及相關基礎學科的學術論文和最新研究成果等。

本刊國內外公開發(fā)行，側重體現(xiàn)本校特色，面向國內外組稿。本刊是《CAJ-CD規(guī)范》執(zhí)行優(yōu)秀期刊，美國《化學文摘》(CA)源期刊，美國《劍橋科學文摘》(CSA)源期刊，俄羅斯《文摘雜志》(VINITI)源期刊，《中國科技論文統(tǒng)計》源期刊，《中文科技期刊數(shù)據庫》源期刊，《中國學術期刊綜合評價數(shù)據庫》源期刊，此外，我刊還是《中國期刊網》、《中國學術期刊(光盤版)》全文收錄期刊和《萬方數(shù)據——數(shù)字化期刊群》上網期刊。另外，我刊和全國各高校學報、科研院所出版的刊物均有學術交流，凡被本刊發(fā)表的研究成果及論文，能很快地傳播并及時為國內外同行專家引用。

本刊參加全國非郵發(fā)報刊聯(lián)合征訂，請讀者向天津市大寺泉集北里別墅17號(郵編300385)天津市河西區(qū)聯(lián)合征訂服務部直接匯款訂閱，不必先索取訂單，由本刊負責將刊物寄給訂戶。也可直接向本刊訂閱，由郵局匯款到安徽省淮南市安徽理工大學學術出版中心。

郵政編碼： 232001

電話： 0554-6668044

E-mail: xbzrb@aust.edu.cn

Firewall Rules Optimization Algorithm Based on Default Rules and

Conflict Detection

GAO Fei, CAO Bo, ZHUANG Yan

(Information Communication Company, State Grid Hubei Electric Power Company, Yichang Hubei 443000, China)

Abstract:The increasing of firewall filtering rules set and the conflict between the rules seriously affect the performance of the network. The rules matching optimization algorithm of firewall was studied and improved. On the basis of improved dynamic adjustment of conflict rules by using statistical analysis method, detection of conflict among the rules was pre-optimized, and the merging operation of part of the rules separated from the default ones was proposed. the new rules will be generated to participate in the order of the original rule set.The order of the newly generated rules and the original rule set was adjusted. The simulation results showed that the method is effective to reduce the firewall rules matching time and improve performance of firewall.

Key words:firewall; rules matching; conflict detection; default rules; conflict free area

作者簡介：高飛(1971-)，男，湖北武漢人，高級工程師，碩士，研究方向：企業(yè)信息安全管理與技術應用。

收稿日期：2015-05-27

中圖分類號：TP393.08

文獻標志碼：A

文章編號：1672-1098(2015)04-0070-07