基于决策树的安全策略冲突检测

（中国船舶重工集团公司第七二二研究所 武汉 430205）

1 引言

网络安全的重要性引起了人们的关注，由于不断增加的网络攻击威胁，各类网络中的重要元素逐渐变为网络安全设备（如防火墙和IPSec网关）。在这些网络管理中，系统行为的规范一般是由策略定义［1］，由策略决定安全设备在不同情况下执行的动作。目前广泛应用的网络管理方法是结合策略的方法［2］，但目前策略配置主要由人工进行配置，由于人工配置的原因会出现配置的策略之间的冲突。一些安全漏洞可能会在安全设备执行策略时出现，导致系统的正常运行受到影响。随着网络规模的增大，策略的数目也在不断增加，使得策略冲突情况将更容易发生。因此，对策略进行冲突检测来减少这些情况是至关重要的。由于分布式系统具有种类繁多的安全设备和结构复杂的网络，难以实现人工方式对策略冲突进行检测。目前网络管理领域中关于策略的重要研究方向是找到一种方法可以准确快速检测策略冲突。

2 相关工作

近年来在安全策略的冲突检测方面，国内外做了许多研究，针对策略冲突检测提出了不同的方法，文献［3］提出了一种基于有限状态传感器策略的碰撞检测方法，该方法将事件转移函数和自适应子集添加到有限自动机（Finite State Transducer，FST）中以处理冲突。文献［4］提出了一种有向无环图模型（DAG），该模型通过将分布式系统中的元素抽象为DAG来检测策略冲突。文献［5］还使用图论来检测和解决从冲突。与以前的文献不同，文献［6］使用分类树的授权算法将父节点的规则与子节点上的相应规则进行比较，从而检测冲突。文献［7～8］中通过对策略语义的研究，实现了策略冲突检测。当现有策略与静态职责分离策略共存时，文献［9］所提出的冲突解决方法以满足互斥要求为目标。这些方法在性能上均存在不足，在基于角色、有限自动机、有向图等方法上，对于规则的顺序比较具有较强依赖性。而本文的决策树模型将对上诉问题进行解决，决策树可以大量减少顺序比较。

近年来国内外对决策树进行了大量研究，2010年，普渡大学博士B.Vamanan针对大规模规则集研究提出基于分子集的决策树算法EffiCuts［10］。2013年，北京大学W.Li博士在EffiCuts算法基础上提出改进算法HybridCuts算法［11］，通过减少子集数目提升算法查找性能。对于决策树切割技术单一问题，2014年中科院计算所G.Xie团队提出智能切割算法 SmartSplit［12］。2018 年，北京大学 W.Li博士再次对决策树算法进行改进，提出融合等长度和等密度切割的决策树算法 CutSplit［13］。2019 年，W.Li博士再次进行优化，提出支持高性能更新的TabTree算法［14］。现在已经有的大量关于决策树的研究的出现证明了决策树在现实中具有应用价值。

3 安全策略冲突基本概念

安全策略的匹配顺序是从上到下，因此安全策略中的冲突可能是由不同规则之间的依赖性引起的。因此，冲突检测的第一步是对不同规则之间的关系进行定义。

由于IPSec的自上而下的策略匹配，如果安全策略顺序配置不正确，则可能永远不会触发某些规则，从而导致策略错误。策略冲突从定义上可以被分为以下几类冲突。

1）策略屏蔽冲突

规则Rx屏蔽了规则Ry，当且仅当满足以下两个条件之一：

Rx[序号]＜ Ry[序号]，Rx=Ry，Rx[行为]≠ Ry[行为]

Rx[序号]＜Ry[序号]，Ry⊂ Rx，Rx[行为]≠ Ry[行为]

2）策略冗余冲突

对规则Rx来说，规则Ry是冗余的，当且仅当满足下面两个条件之一：

Rx[序号]＜ Ry[序号]，Rx=Ry，Rx[行为]=Ry[行为]

Rx[序号]＜ Ry[序号]，Ry⊂ Rx，Rx[行为]=Ry[行为]

反之，对规则Ry来说，规则Rx是冗余的，当且仅当：

Rx[序号]＜ Ry[序号]，Rx⊂ Ry，Rx[行为]=Ry[行为]

当存在以下情况时，内部策略也将发生冗余冲突：

Rx[序号]＜ Ry[序号]，Rx∩ Ry≠ φ，Rx[行为]=Ry[行为]

3）策略相关冲突

规则Rx和Ry之间出现策略相关冲突，当且仅当满足以下条件：

Rx[序号]＜Ry[序号]，Rx∩Ry≠φ，Rx[行为]≠Ry[行为]

4 访问列表冲突决策树模型

在数据分类领域中，决策树是一项重要技术，通过学习训练集构造决策树，然后根据决策树模型对目标数据类别进行预测［15］。在构造决策树时，首要的步骤是预处理策略集对应的五元组数据，具体是将复合维度分解和确定维度空间。五元组中的源、目的地址，源、目的端口均为连续维度，在进行划分时的维度范围是最小值至最大值，而协议则是非连续维度，协议中的值为一个个的协议元素，在进行划分时为元素集合的划分。对于协议这种非连续维度中的元素可能存在元素A包含元素B的情况，这种情况下对应维度就为复合维度，在预处理时需要将复合维度进行分解，将例如元素B的这类元素分解为其本身与其父元素的组合。例如表1中的策略的元素有SCTP、TCP、UDP和IP这些协议。这些协议元素中例如SCTP就可以视为复合元素，将这种复合元素分解为所有复合元素的父元素的集合，即IP/SCTP。以此类推，表1中的协议这类复合型维度可以被分解为表2所示。

表1 规则示例

表2 复合维度分解

在预处理时，对于源IP地址、目的IP地址这类连续维度，将对应维度在规则中的最大值和最小值找到。由于协议这类非连续维度的范围就是维度中所有可以取到的元素集合。因此，表1对应的维度范围如表3所示。

表3 确定维度空间

在对策略集进行预处理后，我们可以开始构建决策树。首先，我们可以根据确定的维度空间对策略集中的规则进行裁剪。首先确定决策树的两个参数：叶子节点中可以存放的最大规则数T和每个维度范围可划分为np个。当T小于当前节点内存放的规则数时，说明节点内存放规则数多于设定值，选择对应的维度范围进行均分，当节点内存放规则均不大于T时就认为该节点为叶子节点，当所有节点均划为叶子节点时，决策树的构造就完成了。

以表4中的规则为例，由于规则数目较少，假定T和np均为3，在构建决策树时，先以源IP地址进行划分，源IP地址的维度空间为202.168.80.0～202.168.80.255，根据np=3，将其均匀的切割为3个区间，若规则中源IP地址落在202.168.60.0～202.168.60.85的范围内时将其划分到第一个节点，规则中源IP地址落在 202.168.80.86～202.168.80.170的范围内时将其划分到第二个节点，规则中源IP地址落在202.168.80.171～202.168.80.255的范围内时将其划分到第三个节点，然后对划分后的节点与T进行大小判断，若节点内的规则数大于T则选择下一个维度即目的地址进行切割，直到叶子节点内的规则数均不大于T。

图1 构造决策树

图2是决策树构建算法流程，先对策略集进行预处理，若存在复合维度，先将复合型维度进行分解，统计连续维度范围，从源IP地址开始，将范围均分为np个范围，计算落在划分的各个节点范围中的策略数，判断T是否小于节点内策略数，若T小于节点内策略数，择下一个维度进行划分，直到所有叶子节点内策略数均不大于T，在找到对应叶子节点后，顺序查找比较存放在叶子节点内的策略，若叶子节点中存放的策略的五元组存在交集，则进一步判断存在的冲突类型。根据上述策略的冲突分类判断冲突类型，若为屏蔽冲突，根据希望执行动作决定将被屏蔽策略删除或将屏蔽策略删除，若为冗余冲突，可删除冗余的策略，若为相关冲突，则将两条策略交集部分根据希望执行动作进行分割，将交集部分划分到希望执行的动作对应策略下，将另一条策略中的交集部分删除。若新增策略与已有策略之间没有交集则将其添加至相应的叶子节点内。

图2 算法流程

基于决策树的策略冲突检测具体步骤如下。

1）将已有策略集构建为一个决策树模型，决策树构建完成后先检测当前情况内的叶子节点内是否存在策略冲突，若存在，根据冲突类型的不同选择不同解决方法，若不存在，则说明当前构建完成的决策树中不含冲突策略，在之后新增策略比对时，只存在新增策略与已有策略之间的冲突。

2）将新增策略A从源IP地址这个维度进行比对划分，根据新增策略A的源IP地址范围判断其落在哪个子节点分支上，若源IP地址同时落在两个或两个以上的源IP地址分支上，则将策略A根据源IP地址分支的范围划分为n个相应源IP地址范围的策略。

3）将新增策略A继续以下一个维度进行匹配，操作与步骤2）类似，直至将策略A与对应叶子节点匹配。

4）将新增策略A与相应的叶子节点内的策略进行顺序比对，判断策略A与已有策略之间是否存在交集，若无交集，则说明新增策略与已有策略之间不存在冲突，若存在交集，则判断新增策略与已有策略之间的冲突类型。

这种方法下仅需检测对应叶子节点内的规则就可以找到策略之间是否发生冲突，不需要对所有已有策略进行比对，分析是否产生冲突。

5 冲突检测算法性能分析

目前提出的对策略的冲突进行检测的方法一般是基于顺序匹配，本文提出的决策树方法对比顺序匹配极大减少了策略查找数目。本文的方法是先构造决策树，通过将策略在不同维度上进行切割，最终形成每个叶子节点内策略数均不大于T的决策树，在进行策略冲突检测时，先将策略在决策树中分维度进行匹配，在最后与之相匹配的叶子节点内的规则集中进行顺序查找匹配。对于n条规则，构造决策树进行冲突检测的方法的时间复杂度为O（mn），在决策树的叶子节点内进行策略的查找匹配的时间复杂度为O（Tm）。在文献［7］中的方法中需要对每两条策略之间进行特征因子处理，进行了大量的顺序查找比对，这种方法的时间复杂度为O（nm）。将两种方法的测试数据进行对比，当策略数目较少的时候，本文方法与文献［7］的方法相比并没有出现明显的优势，但随着策略数目的翻倍增加，本文方法的算法效率对比文献［7］的方法优势越发明显，对同样数目的策略，策略冲突检测时间出现明显减少。

图3 相同运行环境下本文算法与文献［7］方法运行时间对比

6 结语

本文结合了包分类中的匹配思想，先对策略进行预处理、构建决策树后，在叶子节点中查找规则冲突情况。本文提出的方法中若新增策略为确定值而非范围时，进行分维度查找匹配的过程与包分类的过程类似。因此对策略进行划分，在叶子节点内进行查找的方法对包分类也有参考意义。对比之前基于顺序查找的各种方法来说，本文提出的方法在查找上提高了性能。与文献［7］的方法比较，当规则数目较大时，时间效率有很大提升，有明显的优势。本文由于测试数据的IP地址范围有限，对于变化范围更大的IP地址范围需进一步研究调整决策树的。但本文针对五元组模型提出的策略冲突检测模型，对于其他策略模型是否具有适用性还需作进一步的研究。