一种解决防火墙规则冲突的混合型算法的研究∗

曹波 冯伟东 孟浩华 刘祺

（1.国网湖北省电力公司信息通信公司武汉430077）（2.湖北电力科学研究院武汉430077）

一种解决防火墙规则冲突的混合型算法的研究∗

曹波1冯伟东1孟浩华1刘祺2

（1.国网湖北省电力公司信息通信公司武汉430077）（2.湖北电力科学研究院武汉430077）

防火墙冲突检测算法是一种经典的解决防火墙过滤规则间冲突的优化算法，可有效地提高防火墙规则集的运行效率，减少规则间冲突的发生，从而节约大量的计算资源，保障网络通信的正常进行，但随着数据规模和用户数量的飞速增长，防火墙规则集也在日益扩大，原有的冲突检测算法已无法满足当前的网络通信需求，必须加以改进。论文提出了将默认规则与冲突检测算法相结合，在检测之前先执行预优化的改进策略，同时将默认规则进行解析处理，随后将其与原有规则集相合并，大大提高了防火墙的匹配效率，缩短了防火墙的处理时延。

防火墙；动态调整；冲突检测；平均匹配次数；默认规则

Class NumberTP301

1 引言

防火墙技术自投入使用以来就一直随着网络的快速发展而不断的更新改进，作为用户主机或局域网与外部网络之间的隔离带，防火墙对数据过滤性能的好坏直接关系到内网与外网之间有效数据的传输效率，若设置不当将会成为网络通信的瓶颈。如何在网络数据规模日益庞大，数据种类日益增多的环境下，保持乃至改进防火墙的性能，一直是网络安全领域的研究热点。目前的研究工作需要解决的问题主要分为两类，一是随着网络传输数据的不断增多，数据类型日益复杂，网络攻击手段多样化，防火墙规则集也随之逐渐积累增长，规则间的冲突现象日益恶化，严重影响了防火墙的性能［1］；另一类则集中在防火墙处理时延方面，即如何进一步压缩防火墙的规则匹配时延，减少因防火墙的存在而带来的对正常数据传输的迟滞现象［2］。本文提出将目前采用的规则冲突检测算法作为防火墙优化的第一步骤，同时将默认规则进行解析分离，取出部分有效的规则添加到规则集中参与次序调整，形成了一种新的优化算法，通过实验证明，该方法有效地降低了规则匹配时间，并减少了防火墙规则冲突概率。

2 规则集动态调整机制

防火墙规则集是实现数据过滤的关键要素，而随着网络数据状况的变化，其规则的前后顺序也需要相应的灵活调整，将高匹配概率的规则置于集合前列，从而有效地减少匹配成功花费的时延，这意味着使用频率越高的规则，则越容易被拿来首先与数据流匹配，因此量化并衡量某条规则的使用频率成为了该机制的核心内容。

在对规则使用频率进行统计分析时，目前主要采取的方式有两种，第一种为全局式，即将防火墙投入使用以来处理的全部数据流量作为分析对象，以任一规则在这个庞大的数据集中匹配的次数作为衡量该规则优劣的依据；第二种为局部式，可根据指定的某段时期（或者靠近监测统计点的一段时间）内的数据流量进行统计分析。从这两种方式可以看出，前者的统计性较好，但以往大量累积的陈旧记录可能会对当前的统计结果形成干扰；而后者则可能陷入局部峰值。因此，有专家提出了一种基于可变时间的优化算法，将网络在不同时间段的流量大小作为影响因子参与到优化过程中，设置系数M=防火墙最大处理流量/当前流量，而采样时间Tn=M×Tn-1，即根据某时间段内数据流量大小来决定该纳入统计的该时间段的长短［3］。

3 冲突检测预优化分析

3.1 防火墙规则结构

防火墙规则一般如表1所示的七个字段组成［4］。

表1 防火墙参数模型

发送方将自身的IP地址和目的地IP地址分别封装进IP数据报首部源地址字段和目的地址字段，同时采用不同的源端口和目的端口来识别不同的应用进程；协议字段指向了上层使用的具体协议类型；动作字段指的是一旦某数据包被规则集中的某条规则匹配，则该数据包将如何处理，反之亦然。对于Ti3～Ti6的取值范围，可用[] S，E表示，如对于Ti3，可表示为[] S(Ti3)，E(Ti3)，将其他字段均按照此方法进行解析，则完整的规则字段可表述为

将防火墙规则集中的所有规则均按此方式进行解析，得到的结果如表2所示。

表2 防火墙规则集示例

防火墙在收到某数据包后，即按照如上表中的规则顺序对数据包进行逐条对比，当发现可以匹配时即判断该数据包非法并予以拦截；每条规则都由7个字段组成，因此可以看成为一个7元素的集合，从而可用集合间的关系来衡量规则间的关系，这一转变带来了明显的益处，即可以采用早已应用成熟并且逻辑严谨的集合中的各个关系概念，诸如包含、被包含、分离、相等、相交［5～6］。

3.2 规则间冲突类型

按照集合间的关系来解析规则间的冲突现象，可将其分为四种不同的冲突类型［7］：

1）影子冲突：Sx⊂BeforeSx，Sx为某规则字段集合；BeforeSx为该规则之前的任一规则的字段集合；该冲突指某规则成为了规则集中之前某一规则的子集，成为完全重复的无意义规则；

2）冗余冲突：Sx⊃BeforeSx，且动作相同，与影子冲突相反，指的是当前某规则完全包含之前某规则，导致前一规则成为冗余规则；

3）泛化冲突：Sx⊃BeforeSx，且动作相异，即当前规则集合与之前的某条规则完全一致，但处理方法却相反，造成矛盾；

4）关联冲突：Sx∩BeforeSx≠∅，且动作相异，即当前规则集合与之前的某条规则有部分相同，但处理方法却相反，造成矛盾；

以上四种冲突在防火墙的运转过程中均有可能发生，且发生的概率随着防火墙规则集的不断积累而持续上升，因此，许多防火墙的使用者均反映防火墙使用时间越久，性能越差，这在一定程度上就是由于规则集内发生的冲突数量的增加而造成的，由此可以看出，在防火墙的维护工作中，对规则集冲突现象的筛查和解决，对于保持防火墙运转性能而言是至关重要的。

4 默认规则的解析与处理

衡量防火墙运行质量的高低，关键在于筛查数据包的速度，即对一个非法的数据包，需要经过多长时间才能够判别出来，这一标准从规则集匹配角度来解析，就得到了关键参数-平均匹配次数［8］：

式（2）中，i为序号，pi为该序号对应规则能够被某数据包匹配成功的概率，W即为平均匹配概率，此值的大小同防火墙性能的高低成反比。观察式（2）可以发现，W值的大小由两个变量决定，一是规则集的规模，即规则数量n，二是以概率pi匹配成功的规则的序号，即该规则所处位置，显然，i值越小，则防火墙性能表现越好。

在规则集中，默认规则为最后一项，显然其序号最大，若默认规则成功匹配，则意味着规则集中的其他全部规则都曾参与匹配并失败，这显然对防火墙的平均性能表现产生了极大的负面影响，另一方面，即使默认规则被多次匹配成功，在动态调整算法中，也不会改变其位置，这就意味着防火墙将可能频繁地以最低的匹配效率执行数据筛查功能，反之，若能将默认规则中匹配概率较高的那部分分离出来，添加至规则集中参与次序调整，带来的性能提升将会是非常明显的，但需要解决以下两个问题［9～10］：

1）新规则不能产生新的冲突，否则将会适得其反；

2）添加新的规则会导致规则集的增大，对W也会带来影响，因此必须选择有价值的默认规则进行分离与添加，而判别的依据就是匹配概率pi，具体可由下式计算：

式中m为添加规则的序号；p1为原默认规则匹配概率；p2为添加规则匹配概率；3，…，k为添加规则后原规则序号；只有当α＞0时，才有必要执行默认规则的添加。

5 混合型优化算法的设计

本文将冲突检测和默认规则分离添加两个环节有机的结合到一起，设计思路为：首先通过规则冲突检测对防火墙规则集进行预优化，并对统计分析算法提出约束条件，随后从默认规则中分离出部分有价值的规则进行添加，具体步骤如下：

1）对于造成影子冲突的规则Ri，将其删除；

2）对于造成冗余冲突的规则Ri，若Ri没有与其后的规则产生泛化冲突，则删除Ri，完成预优化环节；

3）根据各个规则集合中协议字段的不同，将规则表分解成TCP表、UDP表等，同时做好默认规则的准备工作，按同样方式将其分解为EXTCP表、EXUDP表等，本文以TCP表作为示例进行介绍；

4）将EXTCP表中任意两条规则Ri、Rj组合，若同规则集中的其余规则无冲突，则Ri、Rj可合并，记为Ri↔Rj=1；否则不可合并，记为Ri↔Rj= 0，以此关系数据构造关系数组CHG_TCP［i］［j］；

5）对于EXTCP表中的规则，合并过的标记为1，否则为0，构造标记数组UNI_TCP［］；

6）反之，对未被合并过的规则Ri，查询关系数组CHG_TCP［i］［j］可得到所有能与Ri合并的规则，将其序号记录进EXUNI_TCP［］中；

7）尝试对EXUNI_TCP［］标记的规则进行两两组，将有合并价值的规则保留，其余删除，保证EXUNI_TCP［］数组中任意两条规则均可合并；

8）按上文提出的无冲突合并方法将进行合并，并在UNI_TCP［］中将合并后的新规则标记为1；

9）对于合并后的规则，若符合式（1）指明的前提条件，则添加至原规则集中，否则不予添加；

10）返回步骤6）继续检索EXTCP表，直至遍历完成。

6 仿真试验及分析

本文以TCP表为示例，选定规则样本包括了所有冲突类型，并根据网络实际状况，针对某些规则进行频繁的数据包匹配，初始规则集如表3所示。

表3 初始规则集

经冲突检测系统检测，发现存在冲突关系如表4。

表4 规则冲突检测结果

经过预优化处理后，得到规则集如表5。

表5 预处理后的规则集

从防火墙日志中得到的与默认规则匹配的数据表如表6。

表6 与默认规则匹配的数据表

根据上文提出的合并算法，对表5、表6进行对比分析及合并优化，产生的新的规则为

Rnew=TCP，192.122.210.88-122.125.32.54， 900-2400，181.22.7.224-181.66.22.44，30-64，Deny，同时也将被合并的几条规则的匹配次数累加，即为Rnew的匹配次数，将Rnew添加进原始规则集TCP表中，并按前文所述的排序算法及约束条件进行次序调整，排序后结果如表7所示。

表7 重排序后的规则集

优化后的规则表中，任意两条规则均不会出现冲突现象，由此证明了合并新规则的有效性。序号为4的新规则在添加进规则集之前，根据前文所述公式，计算得到了平均匹配次数W1=4.65527，添加此规则后，经过一段时间的实践，计算得到的W2=3.86244，有效地提高了防火墙规则匹配成功的概率，缩小了防火墙处理时延。

7 结语

本文针对防火墙规则集的优化策略进行研究，首先分析了规则集动态调节机制的效果，并对目前常用的冲突检测算法进行分析，采用集合的概念对目前规则集中存在的冲突现象进行分类，提出利用冲突检测实现防火墙规则集的预优化；在此基础上提出了将默认规则中有价值的一部分规则提取出来，形成新的有效规则，参与到原规则集中，进行动态调整。经过实践证明，该算法有效地降低了防火墙规则的平均匹配次数，提高了防火墙性能，具有一定的推广价值。

［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］庄冠夏.防火墙规则冲突检测和次序优化的研究与实现［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］李鑫，季振洲，刘韦辰，等.防火墙过滤规则集冲突检测算法［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］杨奕，杨树堂，陈健宁.基于统计分析与规则冲突检测的防火墙优化［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日

曹波，男，硕士，高级工程师，研究方向：信息通信系统管理与信息安全。冯伟东，男，硕士，高级工程师，研究方向：信息通信系统管理与信息安全。孟浩华，男，硕士，高级工程师，研究方向：信息通信系统管理与信息安全。刘祺，男，硕士，高级工程师，研究方向：信息通信系统管理与信息安全。