基于SMFDD实现分布式防火墙异常规则检测及优化

吴 军，邓宝龙，邵定宏

（南京工业大学 电子与信息工程学院，江苏 南京211816）

0 引 言

防火墙规则间异常的检测方法一般将规则序列转化对等体或对已存在的对等体［1－4］进行改进，达到提高规则间异常检测效率的目的。Al－Shaer和H.Hamed 首次对分布式防火墙规则间存在的异常进行定义［5］，并提出了基于策略树PT （policy tree）的分布式防火墙规则异常检测算法。该算法时间复杂度为O（dN ），其中d是规则维数，N 表示规则数量。文献 ［5］提出了一种BDD （binary decision diagrams）变体二叉树BT （binary tree）模型，实现了分布式防火墙规则异常的检测。该算法的时间复杂度为O（lg N ＋N／w），其中N 为规则数量，w 为机器字长。BT 算法相对于PT 算法规则异常检测效率有一定的提高，但是在构建对等体时将规则序列号丢弃，导致无法精确分析具体规则间产生的异常，并且随着规则数量的增加检测效率降低。陈文慧提出一种防火墙决策树FDT （firewall decision tree）的变形 MFDT （marked firewall decision tree）模型［6］。MFDT 模型除满足FDT 的特性外，MFDT 中保留规则原始位置信息。MFDT 可以实现规则的插入、删除、更新操作，但是此模型仅局限于独立防火墙规则间的分析。Alex X.Liu等人提出了将防火墙规则转化为策略图FDD［7］，不仅可以保证与原始规则保持一致性、完整性、紧凑性基础上，消除独立防火墙规则间的异常。由于FDD 构建过程中将规则的序列号丢弃，以及构建过程中会增加决策路径数量［7］，这些都增加了基于FDD 模型分析分布式防火墙规则异常的困难。另外，文献 ［8］提出一种方法可以将独立防火墙中的异常规则自动修正，但对于自动修正分布式防火墙中的异常规则，实现优化异常规则的研究较少。

研究发现，存在的分布式防火墙异常规则检测算法通常将上游［9］（下游）防火墙转化为对等体，将下游［9］（上游）防火墙中规则逐一和对等体进行比较，判断规则间异常。由于在构建对等体时将规则序列号丢弃，导致无法精确具体分析规则间产生的异常，并且随着规则数量的增加检测效率降低，同时缺少分布式防火墙异常规则自动修正优化方法。针对上述问题，我们提出了一种基于FDD 的进化模型半同构标记防火墙决策图SMFDD，实现分布式防火墙具体规则间异常检测，提高异常规则检测效率，同时通过SMFDD 间逻辑操作达到优化分布式防火墙中异常规则的目的。实验结果表明，在布式防火墙规则转化为SMFDD后，对SMFDD 之间的比较操作可以快速检测规则间异常。尤其当防火墙规则数量较大时，效果更加显著。SMFDD 间的逻辑操作，实现了对存在异常的规则自动修正，达到优化异常规则的目的。

1 SMFDD模型分析

本节首先分析分布式防火墙规则间的异常，然后对FDD 进化过程进行分析。整个进化过程包括两部分：防火墙规则转化为对等体标记防火墙决策图MFDD （marked firewall decision diagram）、MFDD 半同构化处理形成SMFDD。最后通过SMFDD 比较操作检测规则异常，以及SMFDD 间逻辑操作，自动修正异常规则。

1.1 规则异常定义

防火墙规则由访问控制列表中的列表项组成，决定数据包执行的动作。每个规则由规则号、过滤域、动作域3部分组成。其中规则号决定数据包匹配的顺序。过滤域通常由源IP地址、目的IP、源port、目的port、协议类型五元组组成。动作域只考虑接受与拒绝数据包。防火墙中的规则表示为：＜order＞＜protocol＞＜src＿ip＞＜src＿port＞＜dst＿ip＞＜dst＿port＞＜action＞。规则异常是指规则之间1个域或多个域重叠或交叉，导致产生一种模糊分类问题［9］。 若规则 rx和 ry存在异常， 则 i：rx［Fi］ry［Fi］，且rx和ry的动作域 （action）不同。其中，∈｛，，＝｝，Fi ∈｛protocol，src＿ip，src＿port，dst＿ip，dst＿port｝。

分布式防火墙结构，如图1所示，对于靠近源地址的防火墙fu称为上游防火墙，靠近目的地址的防火墙fd称为下游防火墙。下面给出分布式防火墙规则异常的定义［9］：

定义1 上游防火墙fu允许的数据包被下游的防火墙fd丢弃，则出现非法流入异常。

定义2 上游防火墙fu拒绝的数据包被下游的防火墙fd接受，则出现屏蔽异常。

图1 分布式防火墙结构

1.2 SMFDD的构建及运算

在SMFDD的构建过程中，首先将防火墙规则转化为FDD的变体MFDD，要确保MFDD 的有序性。MFDD 在保持原始规则完整性、一致性、紧凑性的基础上，消除独立防火墙规则间异常，同时保持原始规则序列信息。其次，将MFDDs半同构化处理构造成除叶子节点之外，其他节点完全相同的SMFDDs。下面是关与MFDD模型相关定义。

定义3 防火墙规则的过滤域包括F1F2，…Fd，表示顺序关系，使得F1F2…Fd，当所有决策路径（v1e1…vkekvk＋1）都满足F（v1）F（v2）… F（vk），则称MFDD 满足有序性。

定义4 当MFDDs f 和f′中对应非叶子节点v 和v′，v和v′节点的边一一对应，且具有相同的标识，称v 和v′是半同构节点。

定义5 当MFDDs f 和f′中所有对应非叶子节点具有相同的出度值和入度值，且对应边的具有相同的标识，称f 和f′是半同构化体。

1.2.1 SMFDD 的构建过程

SMFDD 的构建过程如下：①防火墙规则转化为对等体MFDD。②MFDDs半同构化处理形成SMFDDs。

步骤1 MFDD 构建

将规则序列＜r1，...，rn＞转化为对等体MFDDf，f和规则序列的过滤决策是一致的。其中规则形式化表述为rk［F1］∧rk［F2］∧...∧rk［F3］→action。从第1条规则r1转化决策路径开始，依次将r2，...，rn添加到f 中，最终形成规则序列对等体MFDDf。假设已将规则集中r1，...，rk添加到f 中，f根节点v 有k 条边e1，...，ek，如果需要将规则rk＋1添加到f，则需要完成以下2个步骤。

首先，判断是否需要添加边到v，令rk＋1的F1值为S1，边的标示为I（e1），M（e）为规则序列号标记。如果S1－（I（e1）∪...∪I（ek）≠，则需要添加一条ek＋1，令I（ek＋1）＝S1－（I（e1）∪...∪I（ek）），M（ej）＝｛k＋1｝，同时ek＋1指向rk＋1［F2］∧rk＋1［F3］∧...∧rk＋1［Fd］→action 产生的子树。反之，则不需添加新的边。其次，比S1和I（ej），其中1≤j≤k，比较结果包括以下3种情况：①S1∩I（ej）＝。满足第1 步的条件，创建新边。②S1∩I（ej）＝I（ej）。规则域存在重叠部分，同一个数据包可能匹配rk＋1和M（ej）中规则，令M（ej）＝M（ej）∪｛k＋1｝，边ej指向rk＋1［F2］∧rk＋1［F3］∧...∧rk＋1［Fd］→action 产生的子树。③S1∩I（ej）≠∧S1∩I（ej）≠I（ej）。

将边ej拆分成边e′和e″，其中I（e′）＝I（ej）－S1，I（e″）＝I（ej）∩S1，M（e″）＝M（e′）＝M（ej），将e′和e″指向ej边所指向的子树，并删除边ej指向的子树。将表1和表2中的上游防火墙fu和下游防火墙fd中规则应用到上述构造过程对应生成图2和图3。为简单起见，本文设定协议类型值为只包括0 （TCP）或1 （UDP）。对于表3 是表示规则过滤域的简写与域值范围，表4是图例中IP地址及动作域的简写标识。

表1 防火墙fu 的规则集

表2 防火墙fd 的规则集

图2 fu 对等体

表3 规则过滤域的简写与域值范围

图3 fd 对等体

表4 简写标识

步骤2 MFDDs半同构化处理构建SMFDDs

MFDDs的半同构化等价于全部非叶子节点的半同构化。对于节点va有m 条边 ｛e1，e2…，em｝，vb有n条边｛e′1，e′2…，e′n｝，va和vb出边的I（e）为单一连续区间。假设边e1的I（e1）＝ ［a，b1］，边e′1的I（e′1）＝ ［a，b′1］。I（e1）和I（e′1）比较结果分以下两种情况：①当b1＝b′1，I（e1）＝I（e′1）。下一步比较边e2和e′2的I（e2）和I（e′2）值。②当b1≠b′1，假设b1＜b′1，将边e′1拆分成两条边e和e′，e和e′分别指向e′1的子树，I（e）＝ ［a，b1］，I（e′）＝［b1＋1，b′1］，边标记M（e）＝M（e′）＝M（e′1）。下一步比较I（e2）和I（e′）。这里边的标识左区间是相同的，将这个比较过程继续下去，直到节点最右侧的边。当最右侧边的值也相同时，完成节点的半同构化。重复上述过程，除叶子节点外，实现所有节点半同构化。将图2与图3经过半结构化处理后，结果如图4和图5所示。

1.2.2 SMFDD 间比较操作检测异常规则

通过比较半同构体f 和f′中对应决策路径中的叶子节点的值，判断规则间是否存在异常。设（1≤r≤m，1≤i≤n）表示叶子节点的值，其中m 和n分别表示叶子节点数和防火墙中规则的个数。通过比较f 和f′对应决策路中的值，判断规则间是否存在异常。比较的结果包括：①-r，r′，1≤r，r′≤m，。防火墙规则r和r′过滤决策相同，r和r′之间不存在异常关系。②-r，r′，1≤r，r′≤m，。防火墙规则r和r′过滤决策相同，r和r′之间存在异常关系。例如，通过比较图4和图5半同构体f 和f′中对应决策路径中的叶子节点的值，可以发现fu中规则r1和fd中规则r′3存在屏蔽异常。

图4 fu 生成的SMFDDf

图5 fd 生成的SMFDDf′

1.2.3 SMFDD 间逻辑操作优化异常规则

2 算法提出

本节采用类C 描述，给出了SMFDD 构造算法、规则异常检测算法及规则优化算法的伪代码。

2.1 SMFDD构造算法

上述算法，首先将上下防火墙规则转化为MFDDf′和f″后，在此基础上，将f′和f″中非叶子节点半同构化处理，完成f′和f″半同构体的构建。

2.2 规则异常检测算法

上述算法，在将上下游防火墙规则转化成SMFDD f′和SMFDDf″基础上，比较f′和f″对应的决策路径中叶子节点值。根据异常的定义，判断规则间的异常关系。

2.3 规则优化算法

上述算法，通过将f′和f″对应的决策路径中叶子节点值之间逻辑与操作，自动修正异常规则。

3 性能分析与评价

本文使用仿真实验来分析与评价算法的性能，首先搭建仿真实验环境，然后分析实验结果并评价算法的性能。

3.1 实验设计

在NS2中构建一个虚拟的分布式防火墙应用场景，选取其中两个防火墙，将不同数量规则写入防火墙中。文献［10］资料反映实际投入使用的防火墙规则数量最多约为3000条，在实验过程中，设定防火墙规则最多为3000条，符合实际应用条件。本文实验包括3部分：第1部分是对FDD 进化过程的性能分析；第2部分分析了在不同规则的情况下，MFDD 进化模型实现规则异常检测的效率，并将其与BT 算法和PT 算法进行比较；第3部分通过SMFDD间逻辑操作，分析了规则间异常优化算法的性能。

3.2 结果分析

实验的第1部分是对FDD 进化过程的性能分析。图7给出了FDD 进化过程的仿真结果，从中可以看出，随着防火墙中规则数量的增加，FDD 进化过程各部分所需时间都在增加。当规则集数量相同时，规则集转化为对等体MFDD 的时间占FDD 进化过程比例最大，半同构化过程其次，半同构体间比较时间相对最少。

图7 FDD 进化过程

实验的第2部分分析了基于SMFDD 的规则异常检测算法的执行效率，并将其与BT 算法和PT 算法进行比较。从仿真结果图8可以看出，当防火墙中规则数量较少时，BT算法速度最快，PT算法略低于BT算法，基于SMFDD 的规则异常检测算法执行速度低于两者。从图9中可以看出，当防火墙中规则数量较多时，基于SMFDD 的规则异常检测算法最优，PT算法和BT算法相近，但是执行速度远低于基于SMFDD的规则异常检测算法。出现这种结果的原因包括：①当防火墙中含有少量规则时，由规则集转化为对等体BT、PT或MFDD时，MFDD的构建过程需要较多的时间。即在规则异常检测过程中，MFDD的构建时间占有比例较大。②由于FDD进化模型产生的决策路径数量高于BT和PT模型，增加了规则异常检测时间。③当防火墙中规则数量增加后，由于基于SMFDD的规则异常检测算法只需要将半同构体间对应的决策路径进行一次比较，既可以判断规则间的异常。BT或PT算法根据规则间异常关系，规则多次与决策路径比较。综上所述，当防火墙中规则数量较多时，基于SMFDD的规则异常检测算法优于BT与PT算法。

图8 PT、BT 及SMFDD 算法分析

图9 PT、BT 及SMFDD 算法分析

实验第3部分分析了优化规则异常算法的性能。仿真结果如图10所示，从中可以看出，随着防火墙中规则数目的增加，该算法的执行时间也在增加。对于两个拥有3000条规则的防火墙，完成异常规则的修正需要大约16s，说明该算法具有较高执行的效率。

图10 SMFDD 逻辑与运算

4 结束语

本文提出的SMFDD 模型，在保持原始规则完整性、一致性、紧凑性，消除了独立防火墙规则间异常。将规则序列号添加到SMFDD 中，通过SMFDD 间的比较操作，可以快速确定异常规则。另外，通过SMFDD 之间逻辑操作，定位到引起规则异常重叠或交叉域，修正分布式防火墙规则间异常，优化防火墙规则。仿真结果表明，当防火墙含有一定量规则时，基于SMFDD 的异常规则检测算法可以显著提高分布式防火墙规则间异常检测效率，异常优化算法实现快速优化异常规则。

［1］Hu Hongxin，Gail－Joon Ahn，Kulkami K.Dectecting and resolving firewall policy anomalies ［J］.IEEE Transactions on Depend Computing，2012，9 （3）：318－331.

［2］Jeffrey A，Samak T.Model checking firewall policy configurations［C］／／Proceedings of the IEEE International Symposium on Polices for Distributed Systems and Network，2009：60－67.

［3］Acharya HB，Gouda MG.Firewall verification and redundancy checking are equivalent processing ［C］／／IEEE INFOCOM，2011：2123－2128.

［4］Liu AX，Gouda MG.Firewall policy queries ［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20（6）：766－777.

［5］ZHANG Li，CHEN Qinghua.The research on distributed firewall policy anomaly detection algorithm ［D］.Nanjing：Nanjing University of Science and Technology，2007 （in Chinese）.［张丽，陈清华.分布式防火墙策略异常检测算法的研究［D］.南京：南京理工大学，2007.］.

［6］CHEN Weihui，CHEN Huaping，WANG Weiping.The research on firewall system of policy configuration ［D］.Hefei：University of Science and Technology of China，2007 （in Chinese）.［陈文慧，陈华平，王卫平.防火墙系统策略配置研究［D］.合肥：中国科学技术大学，2007］.

［7］Gouda MG，Liu AX.Structured firewall design ［J］.Computer Networks，2007，51 （4）：1106－1120.

［8］Liu AX，Gouda MG.Complete redundancy removal for packet classifiers in TCAMs ［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21 （4）：424－437.

［9］WANG Weiping，CHEN Wenhui，ZHU Weiwei，et al.Analysis of distributed firewall policy configuration mistakes and their detection ［J］.Journal of the Graduate School of the Chinese Academy of Sciences，2007，24 （2）：257－265 （in Chinese）.［王卫平，陈文惠，朱卫未，等.分布式防火墙策略配里错误的分析与检测 ［J］.中国科学院研究生院学报，2007，24 （2）：257－265.］

［10］Chen F，Liu AX，Hwang J，et al.First step towards automatic correction of firewall policy faults ［J］.ACM Transactions on Autonomous and Adaptive Systems，2012，7 （2）：1－24.