基于默认规则及冲突检测的防火墙规则优化算法
2015-02-18高飞，曹波，庄严
高 飞，曹 波，庄 严
(国网湖北省电力公司信息通信公司，湖北 宜昌 443000)
基于默认规则及冲突检测的防火墙规则优化算法
高飞，曹波，庄严
(国网湖北省电力公司信息通信公司，湖北宜昌443000)
摘要：防火墙过滤规则集的日益增大以及规则间存在的相互冲突严重影响了网络的性能。对防火墙匹配优化算法进行研究和改进，在使用统计分析方法提高了规则调整动态性的基础上，结合规则间的冲突检测进行预优化，同时提出将默认规则分离出一部分进行合并操作，将生成的新规则参与原规则集的次序调整。仿真结果证明该方法有效的降低了防火墙规则匹配时间，提高了防火墙性能。
关键词：防火墙；规则匹配；冲突检测；默认规则；无冲突区域
防火墙作为内部网和外部网之间的唯一出入口，在保护内部网络不受外界侵犯的同时，其性能对网络有效数据的传输产生很大影响，如何防止火墙成为网络通信的瓶颈，一直是网络安全领域的研究热点，目前的问题主要集中在两个方面，一是随着网络环境的日益复杂和防火墙规则集的日益增大，规则间的相互冲突情况也越来越严重，增加了防火墙管理的难度；二是如何更有效的对防火墙规则集进行优化，压缩防火墙规则匹配时间，降低其对网络有效数据传输的影响。文献[1]提出了一种防火墙规则冲突检测算法，能够实现规则的无冲突修改，但没有考虑到规则本身次序调整的效率；文献[2]提出了将一种防火墙规则冲突检测的可视化方案，一定程度上提高了操作的便捷性；文献[3]给出了一种通过防火墙规则集的完整性来筛除异常规则的方法，但算法的动态性能较差，尤其对于规则集非常庞大的防火墙，此算法并不适用；文献[4]将统计分析方法运用到规则集的优化上，一定程度上提高了防火墙的性能，但忽视了冲突检测以及默认规则在优化过程中起到的积极作用。
本文提出将规则冲突检测运用到防火墙规则集的预优化当中，并设计了一种无冲突合并算法，将默认规则分离出一部分，添加到规则集中参与次序调整，从而形成了一种新的防火墙优化算法，有效的减少了防火墙规则集的规模，降低了规则匹配时间，提高了防火墙的性能。
1统计分析在规则优化中的应用
防火墙规则集的动态调整是影响防火墙性能的关键环节，根据过滤规则的使用频率，对规则进行动态排序，使得高匹配概率的规则位于规则集的最前列，以提高匹配的成功率，降低耗时，从而实现对防火墙的优化。
在对规则使用频率进行统计分析时，通常存在两种方法，一是根据全部的数据流量进行统计，二是根据一段时期内的数据流量进行统计，该段时期既可以是临近统计点的一个时间段，也可以是指定的某个历史时期。第一种方式更多的侧重于数据的全面性，力争实现排序结果的全局最优，将全部历史数据当中匹配成功频率最高的规则排在最前列，理所当然的其匹配时间将会减少，但该方法的缺点也是很明显的，因其假设某条规则被匹配成功的概率在整个历史时期不会发生变化，由于受到历史数据庞大的基数影响，那些陈旧的规则依旧被排序在最前端，而新出现的规则虽然可能在短时间内匹配成功概率最高，但依旧被排序在靠后的位置，影响了防火墙对当前数据流量的灵敏度；第二种方法只考虑某段时期内的数据流量，较少的数据量可能会影响统计分析的结果，但可以较为灵敏的反应当前网络数据状况，因此得到了更多的应用。文献[5]提出了一种基于可变时间的优化算法，将网络在不同时间段的流量大小作为影响因子参与到优化过程中，设置系数M=防火墙最大处理流量/当前流量，而采样时间Tn=M×Tn-1，这样使得采样时间的大小更加符合本时间段的数据流量大小，改进了防火墙对当前网络状况的敏感度。本文就是以该方法为研究对象，在其基础上将冲突检测与默认规则有机结合，形成新的优化算法。
2规则冲突检测实现对规则集的预优化
2.1 防火墙规则间的关系
防火墙规则一般如表1所示的七个字段组成[6]。
表1 防火墙参数模型
发送方将自身的IP地址及掩码封装进源地址字段，将接收方的IP地址封装进目的地址字段；源端口和目的端口同具体的服务进程相关联，如表中的目的端口：53表示DNS服务；协议字段指的是交付上层哪个协议进行后续处理；动作字段表示防火墙对符合该规则的数据包的处理方法。对于Ti3～Ti6的取值范围，可用一闭区间[S，E] 表示，如对于Ti3，可表示为[S(Ti3)，E(Ti3)]，由此，一条规则可归纳为下式
Ri=
(1)
表2给出了根据式(1)格式的防火墙规则集列表。
表2 防火墙规则集示例
防火墙根据上述规则对接收到的数据包进行匹配检测，而每条规则所匹配的数据可视作一个集合，则规则之间的关系就可以转化为集合间的关系表示，根据集合的概念和规则，任意两个非空集合之间的关系都可划分为包含、被包含、分离、相等、相交[7-8]。
设某规则Rx匹配的集合为Sx，位于Rx之前的任意规则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 防火墙规则冲突类型
由上述规则间的关系可以推导出以下四种不同的冲突情况[4]
1) 影子冲突：Sx⊂BeforeSx，即当前此规则完全被之前的某条规则所覆盖；
2) 冗余冲突：Sx⊃BeforeSx，且动作相同，即当前规则包含了之前的某条规则，且处理方案一致，形成冗余；
3) 泛化冲突：Sx⊃BeforeSx，且动作相异，即当前规则包含了之前的某条规则，且处理方案不同，造成冲突；
4) 关联冲突：Sx∩BeforeSx≠φ，且动作相异，即当前规则与之前的某条规则存在交集，且处理方案不同，造成冲突；
随着防火墙工作时间的延续，其规则集也日益积累不断扩充，导致规则间的冲突概率也随之增大，这给防火墙的正常运转造成了很大的影响和隐患，额外消耗资源及规则配置出错的情况将会日益加重，因此，规则冲突的检测对于防火墙的维护而言是非常必要的。
3基于默认规则的防火墙优化
3.1 添加默认规则的可行性
衡量防火墙性能好坏的一个重要标准是平均匹配次数[3]，其公式可表示为
(2)
i为规则序号，pi为该规则的匹配概率。显然，优化工作的目标就是尽可能降低W，提高运行效率。由式(2)可以看出，对W产生影响的因素有两点，一是规则数量n，二是规则所处的位置i及其匹配概率pi，且i值越大，对W的影响越大。
在规则集中，默认规则为最后一项，即i值最大，与默认规则相匹配的数据流需要遍历整个规则集才能被默认规则命中，并且由于默认规则不参与规则集的次序调整，可能会对防火墙的性能产生很大影响，形成瓶颈效应。如果在默认规则中发现某些规则具有较高的匹配命中次数，则可以考虑将其分离出来，添加至规则集中参与次序调整，可以有效的降低W值，但这种做法需要满足两个前提条件。
1) 添加的规则不可同原有规则相冲突，原因上文已述，这里不再赘述；
2) 添加新的规则无疑会增大规则数量n的值，从而增大W，因此必须考虑添加规则的匹配概率pi，其值过小时不得添加，可用以下公式来衡量
α=W-Wnew=(n+1-m)·p2-p1-p3-…-pk
(3)
式中：α为衡量因子，其值为W原值与新值的差；n为规则总数；m为添加规则的序号；p1为原默认规则匹配概率；p2为添加规则匹配概率；3…k为添加规则后原规则序号。很明显，只有当α>0时，添加默认规则才有意义。
3.2 无冲突的合并规则
在向原规则集添加新规则之前，先要提取防火墙日志中匹配默认规则的数据包，从中解析出规则集，再对该规则集进行整合压缩，从而减少待添加规则的数量以及达到设定的匹配概率，即规则的合并过程；同时还必须保证合并过后的新规则不能与原规则集相冲突，即判断规则是否可合并，待可合并的新规则数量达到了设定值后，再进行合并操作。
两条规则Ri、Rj之间无冲突的充分必要条件为Ri、Rj不相关。假设Rj与Ri具有相同的协议类型，即Ti2=Tj2，且完全从属于下列任一区域中：
(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无冲突，而以上各区域则称为无冲突域。
对于Ti2=Tj2且Ti7=Tj7的两条规则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=
定义4.1若Ri、Rj同规则R不相关，则合并后的Rk也同R不相关。
证：设Ri、Rj处于R的某一无冲突区域内，如(0.0.0.0，S(T3))，则有
max(E(Ti3)，E(Tj3))∈(0.0.0.0，S(T3)，
即新规则的T3域仍然处在R的无冲突区域(0.0.0.0，S(T3))内，其他域同理得证。
3.3 本文优化算法
本文的优化算法分为两个步骤：① 通过规则冲突检测实现预优化，并对统计分析算法提出约束条件；② 从默认规则中分离出符合条件的新规则集，添加至原规则集中，进一步提高防火墙规则的匹配效率。
预优化的目的是减少规则集中无效规则的数量，降低优化算法的计算量。预优化对象为规则集内存在的影子冲突和冗余冲突，算法如下：
1) 对于造成影子冲突的规则Ri，将其删除；
2) 对于造成冗余冲突的规则Ri，若Ri没有与其后的规则产生泛化冲突，则删除Ri。
根据统计分析优化算法的规则，对于高匹配概率的某条规则Ri，在重新排序中应将其位置提前，但若Ri同时会造成泛化/关联冲突，则单一的调换其位置可能会造成防火墙原始语意的改变，从而影响了过滤效果，因此，设定约束条件为：若Ri、Rj存在泛化/关联冲突，则不可将其位置互换；若Ri、Rj存在泛化/关联冲突，而Ri为高概率匹配规则需要调前，则Ri与Rj应同时调前，如图1所示。
在完成了预优化之后，下一步则可进行默认规则的分离、合并及添加过程。具体步骤如下：
1) 根据不同的Ti2将原规则表分解成TCP表、UDP表等，同时将防火墙日志中提取出的同默认规则匹配的规则集按照同样的方式分解，如AddTCP表、AddUDP表等(以下以TCP表为例)；
2) 进行规则合并的可行性判断，将AddTCP表中任意两条规则Ri、Rj组合，同TCP表中的每条规则进行对比，若均处于某条规则的无冲突域中，则Ri、Rj可合并，记为Ri↔Rj=1；否则不可合并，记为Ri↔Rj=0，以此关系数据构造关系数组Rel-TCP[i][j]；
3) 对于AddTCP表中的规则，合并过的标记为1，否则为0，以此构造标记数组Com-TCP[]；
4) 对于AddTCP表中的未被合并过的规则Ri，查询关系数组Rel-TCP[i][j]可得到所有能与Ri合并的规则，将规则号记录在数组AddCOM-TCP[]中；
5) 对AddCOM-TCP[]标记的规则进行两两组合分析，将不可合并的规则全部淘汰删除，保证AddCOM-TCP[]数组中任意两条规则均可合并；
6) 按上文提出的无冲突合并方法将进行合并，并在Com-TCP[]中将合并后的新规则标记为1；
7) 对于合并后的规则，若符合式(3)指明的前提条件，则添加至原规则集中，否则不予添加；
8) 返回步骤(4)继续检索AddTCP表，直至遍历完成。
4仿真试验及分析
本文设定的测试规则集涵盖了全部冲突类型，并且从网络数据流量的真实度考虑，为少数规则匹配了大量的数据包，以TCP表为例，初始规则集如表3所示。
表3 初始规则集
经冲突检测系统检测，发现存在冲突关系如下
表4 规则冲突检测结果
经过预优化处理后，得到规则集如下
表5 预处理后的规则集
同时从防火墙日志中得到的与默认规则匹配的数据表如下
表6 与默认规则匹配的数据表
根据上文提出的合并算法，对表5、表6进行对比分析及合并优化，产生的新的规则为
Rnew=
表7 重排序后的规则集
根据前文给出的规则间的关系和对规则冲突的定义可以看出，新的规则集中没有出现规则的冲突情况，验证了无冲突合并算法的有效性。在将新规则添加至4号位置之前，原规则集按照统计分析方法进行排序后，其平均匹配次数W1=4.66712，在加入新规则后，再次计算平均匹配次数为W2=3.75451。
从实验结果可以看出，在添加了合并规则之后，新的规则集的平均匹配次数有了明显的降低，由此可以证明该优化算法的有效性，虽然不能排除在某些特殊情况下，按照本文算法合并后的规则无法满足添加入规则集的条件，从而导致一定的资源浪费，但从网络数据流量的整体特点的角度来评价，该优化方法依旧具有较强的适用性。
5结束语
本文首先对防火墙规则集常用的统计分析优化算法进行研究，并结合数学集合的概念，总结出防火墙规则间存在的五类不同关系，以此为基础推导出四种类型的规则冲突，提出利用冲突检测实现防火墙规则集的预优化以及对统计分析优化算法形成约束条件；随后提出一种无冲突的合并规则，将默认规则中符合条件的规则分离出来并进行合并操作，形成新的有效规则，参与到统计分析优化算法的动态次序调整中。经实验证明，该优化算法有效的降低了防火墙规则的平均匹配次数，提高了防火墙性能。
参考文献：
[1]张昭理，洪帆，肖海军.一种防火墙规则冲突检测算法[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]庄冠夏.防火墙规则冲突检测和次序优化的研究与实现[D].上海：华东师范大学，2011.
[6]胡伟，段金蓉，范敏.基于统计分析的动态过滤规则优化的研究[J].信息安全，2008，24(2)：102-103.
[7]马维晏，李忠诚.基于流的网络流量特征分析[J].小型微型计算机系统，2009，9(10)：54-58.
[8]李鑫，季振洲，刘韦辰，等.防火墙过滤规则集冲突检测算法[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年创刊，季刊，每期定价5.00元，全年定价20.00元。《安徽理工大学学报(自然科学版)》为安徽理工大学主办的综合性学术刊物，主要刊载地质工程、环境工程、测绘工程、采矿工程、安全工程、信息管理与信息系统、土木工程、建筑学、机械工程、测控技术与仪器、自动化、电子信息工程、计算机科学与技术、矿物加工工程、化学工程与工艺、弹药工程与爆炸技术、制药工程、信息与计算科学、应用物理学、医学以及相关基础学科的学术论文和最新研究成果等。
本刊国内外公开发行，侧重体现本校特色，面向国内外组稿。本刊是《CAJ-CD规范》执行优秀期刊，美国《化学文摘》(CA)源期刊，美国《剑桥科学文摘》(CSA)源期刊，俄罗斯《文摘杂志》(VINITI)源期刊，《中国科技论文统计》源期刊，《中文科技期刊数据库》源期刊，《中国学术期刊综合评价数据库》源期刊，此外，我刊还是《中国期刊网》、《中国学术期刊(光盘版)》全文收录期刊和《万方数据——数字化期刊群》上网期刊。另外，我刊和全国各高校学报、科研院所出版的刊物均有学术交流，凡被本刊发表的研究成果及论文，能很快地传播并及时为国内外同行专家引用。
本刊参加全国非邮发报刊联合征订，请读者向天津市大寺泉集北里别墅17号(邮编300385)天津市河西区联合征订服务部直接汇款订阅，不必先索取订单，由本刊负责将刊物寄给订户。也可直接向本刊订阅，由邮局汇款到安徽省淮南市安徽理工大学学术出版中心。
邮政编码： 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-)，男，湖北武汉人，高级工程师，硕士，研究方向：企业信息安全管理与技术应用。
收稿日期：2015-05-27
中图分类号：TP393.08
文献标志码：A
文章编号：1672-1098(2015)04-0070-07
