曹波 馮偉東 孟浩華 劉祺

（1.國網湖北省電力公司信息通信公司武漢430077）（2.湖北電力科學研究院武漢430077）

一種解決防火墻規(guī)則沖突的混合型算法的研究?

曹波1馮偉東1孟浩華1劉祺2

（1.國網湖北省電力公司信息通信公司武漢430077）（2.湖北電力科學研究院武漢430077）

防火墻沖突檢測算法是一種經典的解決防火墻過濾規(guī)則間沖突的優(yōu)化算法，可有效地提高防火墻規(guī)則集的運行效率，減少規(guī)則間沖突的發(fā)生，從而節(jié)約大量的計算資源，保障網絡通信的正常進行，但隨著數據規(guī)模和用戶數量的飛速增長，防火墻規(guī)則集也在日益擴大，原有的沖突檢測算法已無法滿足當前的網絡通信需求，必須加以改進。論文提出了將默認規(guī)則與沖突檢測算法相結合，在檢測之前先執(zhí)行預優(yōu)化的改進策略，同時將默認規(guī)則進行解析處理，隨后將其與原有規(guī)則集相合并，大大提高了防火墻的匹配效率，縮短了防火墻的處理時延。

防火墻；動態(tài)調整；沖突檢測；平均匹配次數；默認規(guī)則

Class NumberTP301

1 引言

防火墻技術自投入使用以來就一直隨著網絡的快速發(fā)展而不斷的更新改進，作為用戶主機或局域網與外部網絡之間的隔離帶，防火墻對數據過濾性能的好壞直接關系到內網與外網之間有效數據的傳輸效率，若設置不當將會成為網絡通信的瓶頸。如何在網絡數據規(guī)模日益龐大，數據種類日益增多的環(huán)境下，保持乃至改進防火墻的性能，一直是網絡安全領域的研究熱點。目前的研究工作需要解決的問題主要分為兩類，一是隨著網絡傳輸數據的不斷增多，數據類型日益復雜，網絡攻擊手段多樣化，防火墻規(guī)則集也隨之逐漸積累增長，規(guī)則間的沖突現象日益惡化，嚴重影響了防火墻的性能［1］；另一類則集中在防火墻處理時延方面，即如何進一步壓縮防火墻的規(guī)則匹配時延，減少因防火墻的存在而帶來的對正常數據傳輸的遲滯現象［2］。本文提出將目前采用的規(guī)則沖突檢測算法作為防火墻優(yōu)化的第一步驟，同時將默認規(guī)則進行解析分離，取出部分有效的規(guī)則添加到規(guī)則集中參與次序調整，形成了一種新的優(yōu)化算法，通過實驗證明，該方法有效地降低了規(guī)則匹配時間，并減少了防火墻規(guī)則沖突概率。

2 規(guī)則集動態(tài)調整機制

防火墻規(guī)則集是實現數據過濾的關鍵要素，而隨著網絡數據狀況的變化，其規(guī)則的前后順序也需要相應的靈活調整，將高匹配概率的規(guī)則置于集合前列，從而有效地減少匹配成功花費的時延，這意味著使用頻率越高的規(guī)則，則越容易被拿來首先與數據流匹配，因此量化并衡量某條規(guī)則的使用頻率成為了該機制的核心內容。

在對規(guī)則使用頻率進行統計分析時，目前主要采取的方式有兩種，第一種為全局式，即將防火墻投入使用以來處理的全部數據流量作為分析對象，以任一規(guī)則在這個龐大的數據集中匹配的次數作為衡量該規(guī)則優(yōu)劣的依據；第二種為局部式，可根據指定的某段時期（或者靠近監(jiān)測統計點的一段時間）內的數據流量進行統計分析。從這兩種方式可以看出，前者的統計性較好，但以往大量累積的陳舊記錄可能會對當前的統計結果形成干擾；而后者則可能陷入局部峰值。因此，有專家提出了一種基于可變時間的優(yōu)化算法，將網絡在不同時間段的流量大小作為影響因子參與到優(yōu)化過程中，設置系數M=防火墻最大處理流量/當前流量，而采樣時間Tn=M×Tn-1，即根據某時間段內數據流量大小來決定該納入統計的該時間段的長短［3］。

3 沖突檢測預優(yōu)化分析

3.1 防火墻規(guī)則結構

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

表1 防火墻參數模型

發(fā)送方將自身的IP地址和目的地IP地址分別封裝進IP數據報首部源地址字段和目的地址字段，同時采用不同的源端口和目的端口來識別不同的應用進程；協議字段指向了上層使用的具體協議類型；動作字段指的是一旦某數據包被規(guī)則集中的某條規(guī)則匹配，則該數據包將如何處理，反之亦然。對于Ti3～Ti6的取值范圍，可用[] S，E表示，如對于Ti3，可表示為[] S(Ti3)，E(Ti3)，將其他字段均按照此方法進行解析，則完整的規(guī)則字段可表述為

將防火墻規(guī)則集中的所有規(guī)則均按此方式進行解析，得到的結果如表2所示。

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

防火墻在收到某數據包后，即按照如上表中的規(guī)則順序對數據包進行逐條對比，當發(fā)現可以匹配時即判斷該數據包非法并予以攔截；每條規(guī)則都由7個字段組成，因此可以看成為一個7元素的集合，從而可用集合間的關系來衡量規(guī)則間的關系，這一轉變帶來了明顯的益處，即可以采用早已應用成熟并且邏輯嚴謹的集合中的各個關系概念，諸如包含、被包含、分離、相等、相交［5～6］。

3.2 規(guī)則間沖突類型

按照集合間的關系來解析規(guī)則間的沖突現象，可將其分為四種不同的沖突類型［7］：

1）影子沖突：Sx?BeforeSx，Sx為某規(guī)則字段集合；BeforeSx為該規(guī)則之前的任一規(guī)則的字段集合；該沖突指某規(guī)則成為了規(guī)則集中之前某一規(guī)則的子集，成為完全重復的無意義規(guī)則；

2）冗余沖突：Sx?BeforeSx，且動作相同，與影子沖突相反，指的是當前某規(guī)則完全包含之前某規(guī)則，導致前一規(guī)則成為冗余規(guī)則；

3）泛化沖突：Sx?BeforeSx，且動作相異，即當前規(guī)則集合與之前的某條規(guī)則完全一致，但處理方法卻相反，造成矛盾；

4）關聯沖突：Sx∩BeforeSx≠?，且動作相異，即當前規(guī)則集合與之前的某條規(guī)則有部分相同，但處理方法卻相反，造成矛盾；

以上四種沖突在防火墻的運轉過程中均有可能發(fā)生，且發(fā)生的概率隨著防火墻規(guī)則集的不斷積累而持續(xù)上升，因此，許多防火墻的使用者均反映防火墻使用時間越久，性能越差，這在一定程度上就是由于規(guī)則集內發(fā)生的沖突數量的增加而造成的，由此可以看出，在防火墻的維護工作中，對規(guī)則集沖突現象的篩查和解決，對于保持防火墻運轉性能而言是至關重要的。

4 默認規(guī)則的解析與處理

衡量防火墻運行質量的高低，關鍵在于篩查數據包的速度，即對一個非法的數據包，需要經過多長時間才能夠判別出來，這一標準從規(guī)則集匹配角度來解析，就得到了關鍵參數-平均匹配次數［8］：

式（2）中，i為序號，pi為該序號對應規(guī)則能夠被某數據包匹配成功的概率，W即為平均匹配概率，此值的大小同防火墻性能的高低成反比。觀察式（2）可以發(fā)現，W值的大小由兩個變量決定，一是規(guī)則集的規(guī)模，即規(guī)則數量n，二是以概率pi匹配成功的規(guī)則的序號，即該規(guī)則所處位置，顯然，i值越小，則防火墻性能表現越好。

在規(guī)則集中，默認規(guī)則為最后一項，顯然其序號最大，若默認規(guī)則成功匹配，則意味著規(guī)則集中的其他全部規(guī)則都曾參與匹配并失敗，這顯然對防火墻的平均性能表現產生了極大的負面影響，另一方面，即使默認規(guī)則被多次匹配成功，在動態(tài)調整算法中，也不會改變其位置，這就意味著防火墻將可能頻繁地以最低的匹配效率執(zhí)行數據篩查功能，反之，若能將默認規(guī)則中匹配概率較高的那部分分離出來，添加至規(guī)則集中參與次序調整，帶來的性能提升將會是非常明顯的，但需要解決以下兩個問題［9～10］：

1）新規(guī)則不能產生新的沖突，否則將會適得其反；

2）添加新的規(guī)則會導致規(guī)則集的增大，對W也會帶來影響，因此必須選擇有價值的默認規(guī)則進行分離與添加，而判別的依據就是匹配概率pi，具體可由下式計算：

式中m為添加規(guī)則的序號；p1為原默認規(guī)則匹配概率；p2為添加規(guī)則匹配概率；3，…，k為添加規(guī)則后原規(guī)則序號；只有當α＞0時，才有必要執(zhí)行默認規(guī)則的添加。

5 混合型優(yōu)化算法的設計

本文將沖突檢測和默認規(guī)則分離添加兩個環(huán)節(jié)有機的結合到一起，設計思路為：首先通過規(guī)則沖突檢測對防火墻規(guī)則集進行預優(yōu)化，并對統計分析算法提出約束條件，隨后從默認規(guī)則中分離出部分有價值的規(guī)則進行添加，具體步驟如下：

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

2）對于造成冗余沖突的規(guī)則Ri，若Ri沒有與其后的規(guī)則產生泛化沖突，則刪除Ri，完成預優(yōu)化環(huán)節(jié)；

3）根據各個規(guī)則集合中協議字段的不同，將規(guī)則表分解成TCP表、UDP表等，同時做好默認規(guī)則的準備工作，按同樣方式將其分解為EXTCP表、EXUDP表等，本文以TCP表作為示例進行介紹；

4）將EXTCP表中任意兩條規(guī)則Ri、Rj組合，若同規(guī)則集中的其余規(guī)則無沖突，則Ri、Rj可合并，記為Ri?Rj=1；否則不可合并，記為Ri?Rj= 0，以此關系數據構造關系數組CHG_TCP［i］［j］；

5）對于EXTCP表中的規(guī)則，合并過的標記為1，否則為0，構造標記數組UNI_TCP［］；

6）反之，對未被合并過的規(guī)則Ri，查詢關系數組CHG_TCP［i］［j］可得到所有能與Ri合并的規(guī)則，將其序號記錄進EXUNI_TCP［］中；

7）嘗試對EXUNI_TCP［］標記的規(guī)則進行兩兩組，將有合并價值的規(guī)則保留，其余刪除，保證EXUNI_TCP［］數組中任意兩條規(guī)則均可合并；

8）按上文提出的無沖突合并方法將進行合并，并在UNI_TCP［］中將合并后的新規(guī)則標記為1；

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

10）返回步驟6）繼續(xù)檢索EXTCP表，直至遍歷完成。

6 仿真試驗及分析

本文以TCP表為示例，選定規(guī)則樣本包括了所有沖突類型，并根據網絡實際狀況，針對某些規(guī)則進行頻繁的數據包匹配，初始規(guī)則集如表3所示。

表3 初始規(guī)則集

經沖突檢測系統檢測，發(fā)現存在沖突關系如表4。

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

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

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

從防火墻日志中得到的與默認規(guī)則匹配的數據表如表6。

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

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

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

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

優(yōu)化后的規(guī)則表中，任意兩條規(guī)則均不會出現沖突現象，由此證明了合并新規(guī)則的有效性。序號為4的新規(guī)則在添加進規(guī)則集之前，根據前文所述公式，計算得到了平均匹配次數W1=4.65527，添加此規(guī)則后，經過一段時間的實踐，計算得到的W2=3.86244，有效地提高了防火墻規(guī)則匹配成功的概率，縮小了防火墻處理時延。

7 結語

本文針對防火墻規(guī)則集的優(yōu)化策略進行研究，首先分析了規(guī)則集動態(tài)調節(jié)機制的效果，并對目前常用的沖突檢測算法進行分析，采用集合的概念對目前規(guī)則集中存在的沖突現象進行分類，提出利用沖突檢測實現防火墻規(guī)則集的預優(yōu)化；在此基礎上提出了將默認規(guī)則中有價值的一部分規(guī)則提取出來，形成新的有效規(guī)則，參與到原規(guī)則集中，進行動態(tài)調整。經過實踐證明，該算法有效地降低了防火墻規(guī)則的平均匹配次數，提高了防火墻性能，具有一定的推廣價值。

［1］彭國軍，王泰格，邵玉如，等.基于網絡流量特征的未知木馬檢測技術及其實現［J］.信息網絡安全，2012（10）：5-9. PENG Guojun，WSNG Getai，SHAO Yuru，et al.Unknown Trojan detection technology based on network traffic char?acteristics and its implementation［J］.Information network security，2012（10）：5-9.

［2］Ui-Hyong Kim，Jung-Min Kang，Jae-Sung Lee，Hy?ong-Shik Kim，Soon-Young Jung.Practical firewall poli?cy inspection using anomaly detection and its visualization［J］.Multimedia Tools and Applications，2014，2（71）：627-641.

［3］Fu Z，Wu F，Huang H，et al.IPSec/VPN security policy： correctness，conflict detection and resolution［C］//Pro?ceedings of Policy'2001 Workshop，2001：39-56.

［4］Myung Kun，Yoon Shigang，Chen Zhan Zhang.Reducing the Size of Rule Set in a Firewall［C］//IEEE International Conference on communications，2012：1274-1279.

［5］莊冠夏.防火墻規(guī)則沖突檢測和次序優(yōu)化的研究與實現［D］.上海：華東師范大學，2011：44-48. ZHUANG Guanxia.Research and implementation of fire?wall rule conflict detection and sequence optimization［D］.Shanghai：East China Normal University，2011：44-48.

［6］Golnabi K，Richard K M，Khan L，et al.Analysis of Fire?wall Policy Rules Using Data Mining Techniques［C］// Proc.of the 10thIEEE/IFIP Network Operations and Man?agement Symposium.［S.l.］：IEEE Press，2006：335-340.

［7］馬維晏，李忠誠.基于流的網絡流量特征分析［J］.小型微型計算機系統，2009，9（10）：54-58. MA Weiyan，LI Zhongcheng.Characteristic analysis of net?work traffic based on flow［J］.Small and micro computer system，2009，9（10）：54-58.

［8］李鑫，季振洲，劉韋辰，等.防火墻過濾規(guī)則集沖突檢測算法［J］.北京郵電大學學報，2011，29（4）：90-93. LI Xin，JI Zhengzhou，LIU Weichen，et al.Firewall filter?ing rule set conflict detection algorithm［J］.Journal of Bei?jing University of Posts and Telecommunications，2011，29（4）：90-93.

［9］D.Wang，R.Hao，D.Lee.Fault detection in rule-based software systems［J］.Information and Software Technolo?gy，2012，45（12）：865-871.

［10］楊奕，楊樹堂，陳健寧.基于統計分析與規(guī)則沖突檢測的防火墻優(yōu)化［J］.計算機工程，2008，34（15）：129-131. YANG Yi，YANG Shutang，CHEN Jianning.Firewall op?timization based on statistical analysis and rule conflict detection［J］.Computer Engineering，2008，34（15）：129-131.

A Hybrid Algorithm to Solve Firewall Rule Conflict

CAO Bo1FENG Weidong1MENG Haohua1LIU Qi2
（1.Information Communication Company State Grid Hubei Electric Power Company，Wuhan430077）（2.State Grid Hubei Electric Power Research Institute，Wuhan430077）

Firewall conflict detection algorithm is a classical algorithm for the rule set of firewall filtering，which could effec?tively improve the efficiency of the firewall rule set and reduce the conflict between the rules，so as to save a lot of computing re?sources and ensure the normal operation of the network communication.However，with the rapid growth of data size and the number of users，the original conflict detection algorithm has been unable to meet the current network communication needs because the fire?wall rule set is also increasing，so the improvement is essential.This paper proposes to combine the default rules and the collision detection algorithm，and improve the pre optimization before detection.At the same time，the default rule is analyzed and combined with the original rule set，which greatly improves the matching efficiency of the firewall and shortens the processing delay of the fire?wall.

firewall，dynamic tuning，conflict detection，average matching times，default rules

TP301

10.3969/j.issn.1672-9722.2017.07.010

2017年1月11日，

2017年2月17日

曹波，男，碩士，高級工程師，研究方向：信息通信系統管理與信息安全。馮偉東，男，碩士，高級工程師，研究方向：信息通信系統管理與信息安全。孟浩華，男，碩士，高級工程師，研究方向：信息通信系統管理與信息安全。劉祺，男，碩士，高級工程師，研究方向：信息通信系統管理與信息安全。