曹波 馮偉東 孟浩華 劉祺

（1.國(guó)網(wǎng)湖北省電力公司信息通信公司武漢430077）（2.湖北電力科學(xué)研究院武漢430077）

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

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

（1.國(guó)網(wǎng)湖北省電力公司信息通信公司武漢430077）（2.湖北電力科學(xué)研究院武漢430077）

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

防火墻；動(dòng)態(tài)調(diào)整；沖突檢測(cè)；平均匹配次數(shù)；默認(rèn)規(guī)則

Class NumberTP301

1 引言

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

2 規(guī)則集動(dòng)態(tài)調(diào)整機(jī)制

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

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

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

3.1 防火墻規(guī)則結(jié)構(gòu)

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

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

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

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

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

防火墻在收到某數(shù)據(jù)包后，即按照如上表中的規(guī)則順序?qū)?shù)據(jù)包進(jìn)行逐條對(duì)比，當(dāng)發(fā)現(xiàn)可以匹配時(shí)即判斷該數(shù)據(jù)包非法并予以攔截；每條規(guī)則都由7個(gè)字段組成，因此可以看成為一個(gè)7元素的集合，從而可用集合間的關(guān)系來衡量規(guī)則間的關(guān)系，這一轉(zhuǎn)變帶來了明顯的益處，即可以采用早已應(yīng)用成熟并且邏輯嚴(yán)謹(jǐn)?shù)募现械母鱾€(gè)關(guān)系概念，諸如包含、被包含、分離、相等、相交［5～6］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5）對(duì)于EXTCP表中的規(guī)則，合并過的標(biāo)記為1，否則為0，構(gòu)造標(biāo)記數(shù)組UNI_TCP［］；

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

7）嘗試對(duì)EXUNI_TCP［］標(biāo)記的規(guī)則進(jìn)行兩兩組，將有合并價(jià)值的規(guī)則保留，其余刪除，保證EXUNI_TCP［］數(shù)組中任意兩條規(guī)則均可合并；

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

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

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

6 仿真試驗(yàn)及分析

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

表3 初始規(guī)則集

經(jīng)沖突檢測(cè)系統(tǒng)檢測(cè)，發(fā)現(xiàn)存在沖突關(guān)系如表4。

表4 規(guī)則沖突檢測(cè)結(jié)果

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

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

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

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

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

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

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

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

7 結(jié)語

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

［1］彭國(guó)軍，王泰格，邵玉如，等.基于網(wǎng)絡(luò)流量特征的未知木馬檢測(cè)技術(shù)及其實(shí)現(xiàn)［J］.信息網(wǎng)絡(luò)安全，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ī)則沖突檢測(cè)和次序優(yōu)化的研究與實(shí)現(xiàn)［D］.上海：華東師范大學(xué)，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］馬維晏，李忠誠(chéng).基于流的網(wǎng)絡(luò)流量特征分析［J］.小型微型計(jì)算機(jī)系統(tǒng)，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ī)則集沖突檢測(cè)算法［J］.北京郵電大學(xué)學(xué)報(bào)，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］楊奕，楊樹堂，陳健寧.基于統(tǒng)計(jì)分析與規(guī)則沖突檢測(cè)的防火墻優(yōu)化［J］.計(jì)算機(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日

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