基于XACML的策略冲突检测与消解方法*

王 聪，李瑞轩，辜希武，汤俊伟

华中科技大学 计算机科学与技术学院，武汉 430074

1 引言

在面向云计算服务的分布式应用环境中，XML（extensible markup language）对安全访问控制起着越来越重要的作用[1]，安全策略广泛使用可扩展的访问控制标记语言（extensible access control markup language，XACML）进行表示。XACML是一种基于XML的开放标准语言，它设计用于描述安全政策以及对网络服务、数字版权管理（digital rights management，DRM）和企业安全应用信息进行访问的权限。XACML在2003年2月由结构化信息标准促进组织（OASIS）批准，开发用于标准化XML的访问控制。XACML有时也称可扩展的访问控制语言（extensible access control language，XACL）。

XACML提供了一种基于属性的访问控制（attribute based access control，ABAC）方法[2]，其以实体属性为核心，访问决策基于主体、资源、操作、环境等实体属性，能够解决复杂信息系统中的细粒度访问控制和大规模用户动态扩展问题，为开放网络提供更为灵活和安全的访问控制技术[2]。

然而，由于XACML的高灵活性，安全策略定义的属性区间之间更有可能产生交集，导致安全策略之间冲突发生得更为频繁，安全策略的维护以及对于访问请求的决策更为困难。尽管XACML本身提供了几种合并算法来处理策略冲突，如允许优先（permit-overrides algorithm）、拒绝优先（deny-overrides algorithm）等，但是大量的冲突策略和冗余策略直接影响了策略决策的效率，预先检测和消解策略冲突以及冗余能极大地减少策略决策所需处理的策略数。因此，XACML安全策略的冲突检测与消解已经成为一个亟待解决的问题。

本文从策略的描述语言XACML出发，分析了目前基于XACML的策略冲突检测与冲突消解算法存在的不足。基于已有的策略冲突检测算法，提出了一系列改进措施，包括建立规则索引和使用属性值集合来统一描述XACML中灵活多变的目标条件定义。对于冲突检测的结果，本文提出了一种新的一次性策略冲突消解算法。该算法采用有向无环图（directed acyclic graph，DAG）的拓扑排序来计算规则合并优先级，将所有规则映射成N维空间中的一个区域，然后按照优先级由高到低的顺序依次获取冲突消解之后每条规则所决定的区域，一次性完成冲突消解。

本文组织结构如下：第1章对研究的问题和方法进行了概述；第2章介绍相关背景知识以及研究现状；第3章介绍了冲突消解算法以及相应的改进；第4章详细描述了冲突消解算法；第5章通过一系列实验分析了冲突检测以及冲突消解算法的性能以及影响算法性能的因素；第6章总结全文，并对未来的工作进行展望。

2 相关工作

XACML已经被产业界广泛采用，并成为工业界标准，目前已经有多种投入应用的策略评估模型。XACML策略包含3个主要组件：Target（目标）、Rule（规则）和Rule CombineAlgorithm（规则合并算法）。

（1）Target定义了一组对于实体属性的条件，这些条件描述了策略或规则能适用的请求集合。

（2）Rule主要由Target、Condition和Effect组成。Target和Condition共同定义了规则适用的请求集合，Condition的分析比较复杂，目前还没有考虑Condition的冲突检测研究，而Condition也不在本文的研究范围内。Effect定义了这些适用的请求是被允许（Permit）还是拒绝（Deny）。

（3）Rule Combine Algorithm描述了当多条规则对同一个请求同时适用，并且评估结果产生冲突时，如何解决这些冲突的方法，也作为冲突消解的依据。主要有允许优先、拒绝优先等。

XACML通过多种属性类型的细粒度刻化定义访问控制策略，但同时也容易导致比较复杂和隐蔽的策略规则冲突类型。XACML自身提供了规则的合并算法，用户在使用过程中大量冲突的产生和消解过程被屏蔽，用户只用关心最终的评估结果即可，降低了模型的使用难度。然而，这种机制也存在一定的问题。首先，XACML将冲突处理的过程屏蔽，使得管理人员不易发现系统的安全漏洞，不能从管理视图的角度分析冲突的位置和细节；另外，大量重叠的规则使得访问控制策略评估请求时需要评估的规则数增加，影响对请求评估的效率，发现并预先消解冲突利于提升策略评估引擎的性能。

安全策略冲突分析的研究主要包括冲突（和冗余）检测和冲突消解两部分。目前对于冲突检测方法的研究主要分为4类：（1）基于SAT技术；（2）基于描述逻辑；（3）基于策略描述语言；（4）基于本体推理。下面分别介绍4类冲突检测方法与其存在的问题。

目前有一类研究采用SAT-solver技术对策略分析问题进行讨论，然而这些研究都只能处理策略冲突检测的问题，并不能解决冲突消解[3]。Lupu等人[4]提出的模态冲突模型根据模态符号将策略冲突定义为正向授权/负向授权冲突、正向职责/负向职责冲突、正向职责/负向授权冲突3种类型，借助模态符号冲突分析对安全策略进行静态检测。Moffett等人[5]研究了策略之间的关系，并且实现了一个策略检验工具在一个新策略加入到策略库之前对策略进行检查。McDaniel等人[6]在多条策略之间自动调和问题上进行了理论研究，并且证明了该问题是一个NP完全问题。

Wang等人[7]对XACML策略中的规则冗余进行了相关研究，其运用描述逻辑对XACML形式化，然后采用一些已有逻辑分析工具研究了策略冗余的问题。文献[8]提出了一种基于描述逻辑的访问控制策略冲突检测方法，文献[9]引入可废止描述逻辑（defeasible description logics，DDL）来建模XACML中的策略，将得到的知识库作为输入，使用Pellet推理机对XACML策略进行冗余分析。上述研究都采用了基于形式逻辑的冲突检测方法，该类方法通过逻辑推理检测出语义冲突，但不易实现，在实际应用中需要开发相应的推理验证工具。

也有一些研究基于策略描述语言的特点进行冲突检测。文献[10]分析了XACML中基于主体属性和资源属性层次关系的策略冲突，给出了算法的思想，但是算法复杂度较高，并且只进行了冲突和冗余检测的研究，并没有提出冲突消解的方法。类似地，文献[11]研究了基于资源层次关系的策略冲突检测，该研究采用有向无环图表示资源之间层次关系，采用符号化模型检验的方法进行冲突检测。文献[12]将策略属性归一化为几种基本类型，并相应地提出了冲突检测的详细算法。该研究提出了一种消解一个策略冲突对的算法，但是只能一次消解一对冲突，并不能从全局上考虑，进行一次性消解。刘江等人[13]提出了一种基于策略属性分解的冲突检测方法，然而该算法的性能有待提升。文献[14]提出了一种基于多维整数空间的安全策略冲突检测与消解方法。该方法将每个条件字段映射到一个整数集合，然后运用整数集合运算来进行冲突检测与消解。然而并不是所有的条件字段都能一一映射到整数集合，该方法的适用范围有所限制。

文献[15]提出的基于对立属性推理和文献[16]提出的基于分离类推理的安全策略冲突检测方法都属于基于本体推理的冲突检测方法，构建领域本体是应用该类方法的前提，而本体构建是一个难点。

上述研究主要针对冲突检测提出了各种各样的解决方案，然而上述研究中大多数并未涉及冲突消解的问题，只有少量研究针对其冲突检测的方法提出了一些冲突消解的思路。文献[13]从算法层面上提出了较为完整的冲突消解方法，然而该方法只能一次消解一对冲突，并不能实现大量冲突自动的一次性消解。文献[14]基于多维整数空间的冲突消解与其冲突检测的方案一样，适用范围有所限制。除此之外，还有少量专门针对冲突消解问题的研究。文献[17]提出了一种访问控制策略非一致性冲突消解方法，该方法把策略非一致性冲突的消解问题规约为一个SAT问题，并采用一种基于策略优先级的方法消解冲突。文献[18]提出了一种面向软件定义网络的访问控制策略实时冲突检测与解决方法，主要针对OpenFlow协议的无状态性，提出一种基于FlowPath的实时动态策略冲突检测与解决方法。

总体来说，安全策略冲突分析一直都是策略分析关注的一个重点问题，基于XACML的安全策略模型的研究很丰富，然而大多数XACML策略冲突分析研究工作从理论层面上提出各自的解决方案，并未深入到算法的层面。另外，现有的绝大部分冲突分析的研究着重于策略冲突检测，对策略冲突消解的算法研究并不多，即使部分研究提到，也仅仅涉及到两条规则之间冲突的消解，并未从全局上考虑所有冲突的一次消解。

针对上述问题，本文从算法的角度，在对现有的策略冲突检测算法进行改进的同时，提出了一种全新的一次消解大量XACML策略冲突的算法。该算法并不依赖于现有各种冲突检测算法的结构，可消解任何符合条件的策略冲突，适用范围广，灵活性也比较强。

3 冲突与冗余检测

3.1 冲突检测问题描述及算法思路

3.1.1 冲突与冗余定义

定义1如果存在一个请求使得两条XACML规则做出的评估结果相反，则说这两条规则之间存在冲突。

定义2对于某一条XACML规则R，如果对于R适用的所有请求，存在一条规则R′，使得R做出的评估结果始终与R′相同，则称规则R冗余。

例如，对于下列5条规则：

R1:if((1≤x≤4)AND(2≤y≤5))→Permit

R2:if((1≤x≤4)AND(1≤y≤4))→Permit

R3:if((2≤x≤3)AND(5.5≤y≤7))→Deny

R4:if((3.5≤x≤6)AND(3≤y≤6))→Deny

R5:if((2≤x≤3)AND(3≤y≤4))→Permit

对于规则R2与R4，当请求内容为(x=3.5 ANDy=3.5)时，R2的评估结果为Permit，R4的评估结果为Deny，故规则R2与R4存在冲突。事实上当请求符合条件((3.5≤x≤6)AND(3≤y≤4))时，规则R2与R4都将做出相反的结果，将上述条件称为冲突对(R2,R4)的冲突区域。一个冲突规则对除了包含产生冲突的两条规则之外，还应包含如下信息：两条规则Target的交集（冲突区域）以及交集的类型，冲突的规则合并算法。

对于规则R5，其适用的所有请求都适用于规则R1，并且规则R1与之做出的评估结果都相同(Permit)，故规则R5为冗余规则，称规则R1为冗余规则R5的覆盖规则。上述覆盖规则R1和冗余规则R5构成一个冗余规则对(R1,R5)。

对于规则R1和R2，虽然存在请求同时适用于两条规则，但此时两条规则做出的评估结果是相同的，故规则R1和R2之间不存在冲突。规则R3与R1、R2的条件在属性x上存在重叠，但在属性y上没有，故R3与R1、R2都不可能同时适用于某一请求，不存在冲突。图1在二维空间中描述了上述例子中的冲突和冗余。

需要说明的是，XACML标准中一个Target可以有多个Subject构成一个Subjects，这些Subject之间是或的关系，只需要满足一个Subject定义的条件即满足Subjects标签的条件，Resource等类似。然而，对于这样的Target总能分解成若干个只包含一个Subject、Resource、Action和Environment标签的简单Target，因此下文只描述这种简单Target冲突的检测与消解。

Fig.1 Policy conflict and redundancy图1 策略冲突和冗余

定义3一条规则R的Target对某一个属性Α所定义的条件对应的属性值集合称为该Target或该规则在属性Α上的投影，记为RA。

例如上述例子中，{1 ≤x≤4}为规则R1和R2在属性x上的投影。

3.1.2 算法的目标与基本思想

首先，将规则的Target映射到一个N维空间，每一个维度表示Target中的一个属性，每一条规则根据Target的适用条件表示成为空间中的一个区域。每一个规则的空间区域会在各个坐标轴上形成投影，这个投影表示规则的Target在该属性上的条件，用该属性上的一个集合表示。这样Target在每一个属性维度上表示成一个集合，形成一个属性到属性值集合的映射。对于Target没涉及到的属性，即认为Target没有进行规定，相应属性值集合为全集。

然后，寻找空间中存在重叠的区域，并且判断空间重叠的类型：完全相等、包含或相交。如果重叠的两个规则Effect相反，则两条规则之间存在冲突；如果重叠的两个规则Effect相同，当重叠的类型为完全相等或包含时，被包含的区域为冗余规则。两个空间区域存在重叠的充分必要条件是两个空间区域在每个属性坐标轴上的投影都存在重叠。一个空间区域包含另一个空间区域的充分必要条件是前者在每个属性坐标轴上的投影都包含后者在该坐标轴上的投影。因此寻找空间中存在的重叠，即计算属性坐标轴中投影集合的交集以及投影相交的类型。两个Target在N维空间中的重叠区域，称为两个Target的交集。

根据以上思想，得到规则冲突与冗余检测算法，见算法1。用3.1.1小节中描述的冲突规则对和冗余规则对分别表示一对冲突和冗余。其中计算两个Target交集在算法2中详细描述。

算法1冲突检测算法

输入：Rule rule，要检测冲突的规则。

输出：Listconflicts，与规则rule冲突的冲突规则对列表；Listredundancies，涉及规则rule冗余规则对列表。

//到R-A索引中获得与R有冲突可能的规则列表

3.2 R-A规则索引

规则的Target中，属性被划分为4类：主体（Sub-ject）、资源（Resource）、操作（Action）和环境（Environment）。只有4类属性对应的条件同时被满足时，该条规则才适用。也就是说，冲突和冗余规则检测时，只有涉及对相同的资源做相同的操作的规则之间才可能存在冲突。假设一条规则针对文件file1是否允许被读取，另一条规则针对文件file2是否允许修改，那么这样的两条规则之间检测冲突是没有意义的。只有当两条规则涉及到相同的资源和相同的操作时，才对其检测冲突和冗余。

为此，本文设计了一个资源-操作二级规则索引（resource-action，R-A规则索引），索引中一级索引为资源属性，二级索引为操作属性，其结构如图2所示。只需要对位于同一条索引记录的规则，即涉及到相同资源属性和操作属性的规则检测冲突和冗余。

Fig.2 Two-level index structure of R-Arule图2 R-A规则二级索引结构

3.3 基于属性值集合的冲突检测算法

3.1节提到，判断两个Target映射的n维空间区域是否存在重叠，需要判断其在每一个属性坐标轴上的投影是否存在重叠。首先将属性的数据类型统一转化为Integer、Long、Double、String，XACML规范定义的所有数据类型都可以映射到上述4种基本类型。

属性坐标轴上的投影可以表示成为一个集合。根据该属性在Target中Match函数的不同，集合可以采用单值集合、区间和正则集3种形式统一表示。单值集合表示只包含一个值的集合，用于表示Equal函数；区间由一个上界和下界表示，用于表示Greater than和Less than之类的比较函数，上下界都既可能是开区间也可能是闭区间；正则集用一个有限自动机来表示，用于表示正则式匹配的函数。另外，字符串忽略大小写的相等函数也用正则集来表示。

为了表示和运算的简便，在用有限自动机表示正则集合时，做了一点优化。用字符区间代替原有的单个字符作为有限自动机中状态转换函数的条件，这样做大大减少了状态转换函数的数目，也极大减少了有限自动机的交集运算。例如：表示正则集[b-/uffff][/d/D]*，该正则式表示所有大于等于“b”的字符串，简化前后的有限自动机如图3所示，其中图3（a）为简化前的自动机，图3（b）为简化后的自动机。

Fig.3 Simplified representation of finite automata图3 有限自动机简化表示

这样，规则冲突与冗余检测算法的核心也就是对各属性值集合求交集。3种属性值集合之间求交集存在下列情形。

情形1单值集合与3种集合中的任意一种求交集。

这种情况下，只需要判断另外一个集合中是否包含该单值集合包含的值。若包含，则判断另外一个集合包含元素的个数，如果大于1则为包含关系，否则为相等关系。

情形2区间与区间求交集。

这种情况下，可以通过比较区间的端点与端点的开闭状态，直接判断出交集以及相交的类型。

情形3正则集与正则集求交集。

可以利用有限自动机求交集的算法，该算法已经有了丰富的研究，文献[12]中也有详细描述。

情形4正则集与区间求交集。

此处的区间必然是字符串区间。将字符串区间转化为有限自动机表示的正则集，并利用正则集之间的交集算法求得交集。将字符串区间转化为有限自动机的算法在相关文献[12]中已有表述，本文不做详细叙述。

对属性值集合求交集运算并得出相交类型之后，得出计算两个Target交集的算法，见算法2。

算法2Target交集算法

输入：Targett1,t2，要计算交集的两个Target。

输出：Target intersection，两个Target的交集，依然是Target形式；type，交集的类型，无交集，相等，t1包含t2，t1是t2子集或t1和t2部分相交。

//建立两个Target的属性集合映射

4 冲突消解

4.1 冲突消解问题描述与算法思路

由第3章的冲突检测算法可得到一系列的冲突规则对，每个冲突规则对的两条规则Target之间存在一定的重叠，冲突消解的任务就是根据重叠部分规则的合并规则（允许优先或拒绝优先等），选择一条覆盖的规则，并在被覆盖的规则中把重叠部分除去。例如，图4中R1和R2为两条规则，其存在的冲突如图4（a）所示，按照合并规则，在重叠部分R2将覆盖掉R1，那么冲突消解之后，将R1的重叠部分从原规则中除去，形成新的两条无冲突的规则，如图4（b）所示。

Fig.4 Conflict resolution图4 冲突消解

上面描述了在两个属性x、y上两条规则冲突的情况，对于多个属性以及多条规则冲突的情形类似。每一个属性都对应一个维度，假设总共有N个属性，那么每一条规则的Target都对应一个N维的超矩体空间，K条规则将空间划分成许多个小区域，每一个小区域都是一条或多条规则的重叠。多条规则同时适用于重叠区域的条件，当其中有规则的Effect不同时，即产生了冲突，规则的合并算法决定了重叠区域最终具有决定权的规则。于是，冲突消解的问题转化成为每一块重叠区域找到其最终具有决定权的规则。下面以4条规则、3个属性为例，描述冲突消解算法的总体思路，规则例子如表1所示。

根据3.1节的描述，冲突检测的结果包含了冲突规则对和冗余规则对；首先对存在的冗余进行处理，即删除冗余的规则；另外，每个冲突规则对还记录了冲突的类型，包括完全覆盖和仅存在交集等，对于一个规则被完全覆盖并且根据规则合并算法也不优先保留该规则的情况，也只需要删除被覆盖的规则即可。以上两种情况不多叙述，在进行冲突消解之前进行预处理，下面直接描述每对冲突规则之间存在交集但不完全覆盖的情况。

Table 1 Rule examples表1 规则示例

每块区域具有决定权规则的选择依据为事先设定好的规则合并算法，规则合并算法描述的是当两条规则同时适用于一个请求时，如何合并两条规则各自的评估结果，算法主要有允许优先、拒绝优先等。根据每一对冲突的规则合并算法，所有冲突规则对可以产生一个有向图，根据有向图的拓扑排序决定的规则优先级来选择。

每一个重叠区域在各个坐标轴上会投影成一个片段（Split），这些片段对每个坐标轴进行了划分。例如上述例子中x轴、y轴和z轴划分的片段如图5所示。

Fig.5 Attribute axis division图5 属性轴划分

为了简便，图5中没有区别每个区间的开闭情况，而具体实现的时候需要考虑。每个片段中间的规则表示所有投影到该片段的规则集合，这些规则成为该片段的投影规则。单个点也能形成一个片段，如z轴只有z=read和z=write两个片段。

这样，在每个坐标轴上选取一个片段就能对应一个三维空间的区域，而覆盖这个区域的规则由每个片段中投影到的规则集合求交集求得。例如图中x-y平面的左下角区域，x轴和y轴上片段投影规则集合求交集之后为(A,C)，若在选取z轴上的read片段，则覆盖该三维区域的规则依然有A和C，决定该区域的规则即为A、C之间优先级高者；而对于x-y平面的右上角区域，x轴和y轴上片段投影规则集合求交集之后为空集，表示无论z轴选取哪个片段，所确定的区域都没有任何规则覆盖到。

确定了每个坐标轴的划分之后，根据规则优先级由高到低依次确定该规则决定的区域，完成冲突消解的过程。采用了一种称作空间区域选择树的数据结构来确定每条规则决定的空间区域。

4.2节详细介绍冲突的有向图表示以及拓扑排序决定规则优先级，4.3节详细介绍属性轴划分的算法，4.4节详细介绍构建空间区域选择树的算法以及优化。

4.2 有向无环图与规则优先级

上一节中提到，任何一个冲突对的两条冲突规则之间根据规则合并算法存在覆盖与被覆盖的关系，即覆盖的优先级。把每一条规则作为一个结点，每一个冲突对的覆盖关系作为一条有向边，由覆盖的规则指向被覆盖的规则，这样就得到了一个全局的冲突有向图。

例如，图6（a）中表示了4条规则A、B、C、D之间的重叠关系。于是，图中表示了(A,B)、(A,D)、(C,D)、(B,C)4个冲突规则对。

假如，4对冲突的覆盖关系分别为A→B、B→C、C→D、A→D，那么可以得到一个有向图，如图6（b）所示。然而，注意到当4对冲突的覆盖关系分别为A→B、B→C、C→D、D→A时，得到有向图如图6（c）所示。图中由于存在有向环，无法确定重叠区域的覆盖优先级，从而这种情况无法进行一次性冲突消解，只能手动选择一对冲突消解，打破环路之后才能继续进行。

对于冲突的有向无环图，可根据其拓扑排序来确定规则的覆盖优先级，环路检测可以在拓扑排序过程中进行。需要说明的是，有些结点之间并不存在直接或间接有向路径连接，对于这样的结点，拓扑顺序的先后对于冲突消解的结果没有任何影响，原因如下：

Fig.6 Representation of conflicting directed graphs图6 冲突的有向图表示

（1）若两个结点代表规则的Effect相同，那么两者重叠部分无论哪条规则优先级更高，Effect都是一样的；

（2）若两个结点代表规则的Effect不同，那么两条规则必然不存在重叠区域，否则两条规则之间存在冲突，两个结点之间将有一条直接的有向边决定其拓扑顺序。

在实际情况中，冲突对应的DAG可能存在若干个互相不连通的弱联通子图，这些子图分别代表了各自独立的冲突规则序列，可以将这些独立的弱联通子图分离出来各自独立消解。而DAG弱联通分量的检测可以在冲突检测累积冲突对的过程中完成。

4.3 属性轴划分

在4.1节中，根据规则在各个坐标轴上投影的重叠对坐标轴进行了划分。例如，对于4.1节中的例子，x轴被划分出如图7所示的片段。

Fig.7 xattribute axis division图7 x属性轴划分

在第3章冲突检测中，把对属性的各种条件归纳成了3种集合：属性值区间、单值集合和正则集。对于单值集合可以看作上下界相等的属性值区间，而对于有限的正则集，可以用多个单值集合的并集来枚举表示，可以把属性值区间、单值集合、有限正则集统称为可划分的集合；而无限正则集称为不可划分的集合，因为如果对其划分将产生无限多个片段。对于冲突消解中的一个属性，如果所有规则在该属性上的条件对应的集合都是可划分的，则该属性即为可划分的，否则该属性不可划分。

对于可划分的属性，每个片段都可以用起始位置和终止位置来表示，而起始点和终止点除了要记录具体的值，还要记录是开区间还是闭区间。注意到当所有片段在坐标轴上有序排列之后，每个片段的结束位置与下一个片段的起始位置是成对出现的，它们位于坐标轴上同一点，如果某片段起始是闭区间，则其上一个片段的终止是开区间，反之亦然。因此，确定了所有片段的起始点和开闭状态后，所有的片段也就确定了。例如图7中，x轴的起始点列表为(2,close)、(3,close)、(4,open)、(5,open)、(6,open)、(7,open)，其中close表示闭区间，open表示开区间。确定的片段分别为(-∞,2)、[2,3)、[3,4]、(4,5]、(5,6]、(6,7)、[7,+∞)。

对属性轴划分的过程就是对所有起始点排序，每两个相邻起始点之间自然就形成了一个小段。起始点比较的规则如下：首先比较两个点值的大小，若不相等则返回比较结果；若相等则作为闭区间的起始点小于作为开区间的起始点。单个属性的属性轴划分算法见算法3。

算法3属性轴划分算法

输入：MapruleList，规则ID→Range(startPoint,endPoint)的映射。

输出：Map>splits，起始点→规则集合的映射,记录每个起始点对应区间的规则集合；Listpoints，起始点的升序排列列表。

//获得所有起始点

对于不可划分的属性，即条件中含有无限正则集的属性，无法用上述方法进行划分，本文的做法是并不显式地对该属性进行划分，只是在后面建立空间区域选择树时才局部进行划分，在4.4节中进行描述。

4.4 建立空间区域选择树消解冲突

对属性轴进行分段之后，根据规则优先级由高到低的顺序，对每条规则建立空间区域选择树。其目的是选择出每条规则在空间中决定的区域，即该规则覆盖的区域中，其优先级最高的部分。对于优先级最高的规则，其内容将会被完全保留，不需要对其构建空间区域选择树。

空间区域选择树是一个N+1层的有序树，根结点表示进行选择的规则R，树的每一层表示在一个属性上进行的一次选择，每一个非根结点表示R在该层对应属性上投影的一个分段，每一条从根结点到非根结点的路径代表了在各个属性轴上选择属性对应条件的过程，也是逐步细化空间区域的过程。当每一个属性上都选择了一个条件之后，该路径即确定了一个规则R覆盖的子区域，只需要判断R是否是该区域中优先级最高的规则即可。为此，每一个非根结点中还记录一个高优先级规则集合字段，该字段表示选择到该结点时对应的空间区域中，比R优先级更高的规则集合，若该字段为空集(∅)，则该区域由规则R决定。

4.1节描述的例子中，假设规则优先级由高到低为A→B→C→D，以x、y、z的顺序依次选择属性条件，规则C的空间区域选择树构造过程如图8（a）所示，图中加粗的路径即确定了两个由规则C决定的区域。由空间区域选择树的构建过程可知，决定一条路径是否被选中的因素是叶子结点的高优先级规则集合字段，因此对于每一层中该字段相同的兄弟结点可以合并成一个结点，上面的空间区域选择树经合并之后的选择树如图8（b）所示。另外，当一个非叶结点的高优先级规则集为空集时，其子孙结点该字段也必然为空，因此从该节点往下直到叶子，每个结点都只有一个孩子结点，每个结点的分段字段即为规则R在对应属性上的条件。

Fig.8 Spatial area selection tree图8 空间区域选择树

重复上面的过程，对每一条规则进行空间区域选择树的构造，即可选出所有消解之后的规则。注意，若某一条规则构造选择树之后，没有一条路径可以被选中，这表示该规则覆盖到的所有区域都被优先级更高的规则覆盖了，当构造优先级更低的规则的选择树时，可以在规则集合字段中忽略该条规则。

4.3节提到了条件中含有无限正则集的属性不显式的划分。假设存在这样的属性w，需要构造规则R的选择树，优先级比R高的规则集合为{P1,P2,…}，则对属性轴w中R投影的部分R_w做局部划分，划分方法如下：

（1）将R_w划分成R_w∩P1_w和R_w-P1_w得到两个集合，注意当交集结果为空集时，差集等于R_w，无需计算，下面每一步都同样。

（2）对步骤（1）中得到的两个集合与P2_w分别取交集和差集，得到最多4个集合。

（3）对每一个Pi做同样的划分，最后最多会得到2(n-1)个集合。当然这是最坏的情况，实际情况中会得到很多空集。

上述划分中得到的每一个集合都作为属性w这一层的一个结点，并且不用进行结点的合并。为了避免每次构造分类树时重复计算，可以把这些交集与差集缓存起来，其中交集的缓存在冲突检测时即可建立。

由空间区域选择树的构造方法上看，当属性数目更多，冲突涉及的规则更多时，属性选择的顺序对选择树的结点数会有一定影响。对于一个特定的规则R，属性选择的顺序最好综合考虑以下两个原则：（1）属性轴片段数少的属性优先；（2）R在属性轴的每个片段中，重叠规则数目较少者优先。为了简便起见，并没有为每条规则制定特定的属性选择顺序，而是根据属性轴划分情况，对每个属性轴计算权重，制定全局的属性选择顺序。对于一个属性x，Xi为x的一个片段，Ri为片段Xi中投影规则的数目，属性x的权重计算方式如下：

而对于不可划分的属性，权重为无穷大。权重的计算可以在属性轴划分的同时完成。根据权重由低到高的顺序选择属性。规则R的空间区域选择树构建算法见算法4。

算法4空间区域选择树构建算法

输入：AttrList，按权重升序排列的属性列表；RuleId，要构造的规则R的Id；PrevRuleSet，比规则R优先级高的规则ID集合。

5 模拟实验及性能分析

为了测试本文提出的策略冲突检测与消解算法的正确性、完备性以及算法性能等，本文根据XACML规范定义策略库作为数据集，利用Java语言实现了算法，在AMD A6-3420M四核处理器，内存DDR3 4 GB 1 333 MHz，运行Windows 7系统的PC机上进行实验。实验模拟了大规模策略集合冲突和冗余检测以及冲突消解的过程，并对实验结果进行了正确性分析和算法性能分析。

5.1 模拟实验

为了检验算法的正确性与完备性，本文模拟了一个对远程文件系统进行访问控制的安全策略集，将文件的操作权限设置为read、write、execute共3种。假定用IP地址来标识访问文件系统的用户，用一个整数类型的属性privilege来衡量用户的权限（0～4），值越大表示权限越高。所有的访问控制策略以XACML标准描述，访问控制策略全集Q如表2所示，规则合并算法采用允许优先（permit-overrides）。

Table 2 Full set of access control strategies表2 访问控制策略全集

表2中的规则r2表示允许IP地址符合192.168.*.*且权限privilege不小于2的用户读取文件file1；规则r7中的“¬”表示对集合取反；而r8表示拒绝任何权限和IP的用户执行文件file1，all-user和all-privilege在XACML策略文件中分别表现为对应的Subject中没有IP地址和权限属性的限制，即没有对应该属性的标签。

（1）冲突检测

在冲突检测实验中，检测结果如下：

① 冲突规则 7 对：(r1,r2)，(r1,r9)，(r1,r11)，(r10,r2)，(r10,r9)，(r10,r11)，(r5,r8)。

② 冗余规则4对：(r2,r11)，(r9,r11)，(r4,r3)，(r7,r6)（后面为冗余规则）。

检测时间为876 ms。

（2）冗余处理和冲突消解预处理

首先，对冲突检测结果进行冗余处理，删除冗余规则r3、r6、r11，还要删除r11对应的冲突规则对。

然后，在剩余冲突规则对中找出那些Target交集类型存在包含或相等关系的冲突对，删除存在直接覆盖关系的冲突规则。在实验中，Target存在包含关系的冲突对有(r10,r9)和(r5,r8)。实验中规则合并算法采用允许优先，因此冲突对中优先保留的规则分别为r10和r8。对于冲突对(r10,r9)，尽管r10的Target被完全包含在r9中，但在消解时优先保留r10的内容，因此其不能被直接删除，冲突消解时需要将r9中与r10重叠的部分去除。而对于冲突规则对(r5,r8)，完全被覆盖，并且其也不是优先保留的规则，因此可以被直接删除。

这样经过冗余处理和冲突消解预处理之后，剩余的4个冲突规则对为(r1,r2)，(r1,r9)，(r10,r9)，(r10,r2)。

（3）冲突消解

剩余的4对冲突中涉及4条规则，根据规则合并算法生成冲突的DAG，通过拓扑排序确定规则的优先级。上述冲突的DAG如图9所示。规则的优先级顺序从高到低依次为r1、r10、r2、r9。

确定规则优先级后，按照规则优先级从高到低的顺序依次构建空间区域选择树，构建时间如表3所示。可以看出，规则优先级越低，构造空间区域选择树的时间越长，这是由于规则优先级越低，在构建选择树的时候要考虑的高优先级规则越多，选择树的结点数也随之增长。而对于优先级最高的规则r1，保留原有规则即可，不需要构建选择树。

Fig.9 Conflicting DAG图9 冲突有向无环图

Table 3 Build-time of space area selection tree表3 空间区域选择树构建时间

注意到，在模拟实验的例子中，选择了IP地址和权限两个主体属性，其中IP地址使用了正则式，对应的正则集可以视为无限正则集，该属性是不可划分的。而对于权限属性采用整数类型表示，是可划分的属性。而资源属性（文件名），操作属性都是字符串枚举类型，同样是可以划分的。这些可划分属性的属性轴划分在构建空间区域选择树之前预先进行，而IP地址的划分在空间区域选择树构建过程中动态划分。

经过冲突消解之后，优先级最高的规则直接保留，剩余3条规则被消解。其中r10去除了与r1重叠的部分；r2去除与r1和r10相冲突的部分生成两条规则，分别用r2_1和r2_2表示；r9去除相冲突的部分之后被r2完全覆盖，消解之后没有产生任何规则。最终得到的规则如表4所示。包括冗余处理和冲突消解预处理在内，冲突消解总共花费的时间为626 ms。

5.2 冲突检测算法性能评估

Table 4 Conflict resolution results表4 冲突消解结果

实验1冲突检测性能与规则数目之间的关系。

冲突检测的性能与规则索引中规则的密集程度，即索引中每个索引项对应的规则数密切相关，为了更好地检验规则数目以及规则索引密集程度对冲突检测性能的影响，预先控制了每个索引项对应的规则数目C，在不同的密集程度下对不同规则数目检验冲突检测算法的性能，这样实际的规则总数R相当于索引项数目E与C值的乘积。图10展示了C值分别为10、20、30时，索引项E从10增加到50的冲突检测时间。

图10中在固定每个索引项对应规则数目的条件下，冲突检测时间随索引项数目（或规则数）线性增长是可以预见的。虽然两条规则之间的冲突检测与规则的具体结构以及涉及属性的数目相关，但在一个索引项中进行冲突检测时，大体上时间与索引项中包含规则数正相关，而固定C值之后，该时间几乎为定值，检测时间自然随索引项数目线性增长。

Fig.10 Experiment 1 of conflict detection performance图10 冲突检测性能实验1

实验2冲突检测性能与规则在索引中密集程度的关系。

固定规则的数目R，改变密集程度C值，检验冲突检测算法的性能。图11展示了R分别取600、1 200和1 800时，C由10增长到60，冲突检测时间与冲突规则对数目的变化趋势图。图11（b）中冲突规则对数目统计的是每一次检测到的冲突规则对与冗余规则对数目总和。很明显可以看出，冲突检测时间和冲突规则对数目在一定的规则总数下随规则在索引中的密集程度线性增长。

5.3 冲突消解算法性能评估

在5.2节冲突检测实验2的基础上，对检测到的冲突进行消解，并检验了冲突规则对数目与冲突消解时间之间的关系，如图12所示。从图12（a）可以看出，从整体上看，冲突消解时间随冲突规则对数目的增长呈线性增长的趋势，然而从局部上看，冲突消解时间与冲突规则对数目的关系则不甚明显。经过分析，认为规则冲突的密集程度对冲突消解时间会有比较大的影响，对于相同数目的冲突规则对，若涉及到的规则数不同，冲突消解的时间会有差别。一方面，涉及规则数越多，需要构造的空间选择树越多；另一方面，涉及的规则数越多，每个属性轴的分片数量越多，构造的空间选择树的结构就越复杂。

为了验证这一想法，用冲突数与规则数的比值λ衡量冲突的密集程度。在每一组规则数R相同的实验中，统计了λ与冲突消解时间的关系，如图12（b）所示。很明显，在一定的规则集规模下，冲突消解时间与冲突密集程度成正比关系。

Fig.11 Experiment 2 of conflict detection performance图11 冲突检测性能实验2

6 结束语

本文对基于XACML规范的ABAC策略的冲突检测与消解展开了深入研究，改进了传统的策略冲突检测算法，并提出了一种新的一次性消解冲突的算法。在模拟实验环境中实现了该算法，并对算法的性能与影响算法性能的因素进行了实验与分析。实验结果表明，策略冲突检测与冲突消解算法能有效地对策略冲突进行检测和消解，并且在有大量冲突的数据集上，能达到比较好的性能。

Fig.12 Conflict resolution performance图12 冲突消解性能

将XACML规范中的数据类型和函数类型统一成几种简单的形式，具有良好的扩展性，支持XACML中Target标签的所有形式的冲突与冗余的检测与消解。然而，目前算法并不支持XACML中Condition标签的冲突检测，这将是下一步主要的研究方向之一。另外，在算法的性能上，若能合理地利用缓存，并在冲突检测与冲突消解之间建立方便的数据共享机制，算法的性能还有提高的空间。

[1]Li Xiaodong,Zhu Hao,Yang Weidong.XML keywords search based on secure access control[J].Journal of Frontiers of Computer Science and Technology,2010,4(1):73-81.

[2]Wang Xiaoming,Fu Hong,Zhang Lichen.Research process attribute-based access control[J].Chinese Journal of Electronics,2010,38(7):1660-1667.

[3]Lin Dan,Rao P,Bertino E,et al.EXAM:a comprehensive environment for the analysis of access control policies[J].International Journal of Information Security,2010,9(4):253-273.

[4]Lupu E C,Sloman M.Conflicts in policy-based distributed systems management[J].IEEE Transactions on Software Engineering,1999,25(6):852-869.

[5]Moffett J D,Sloman M S.Policy conflict analysis in distributed system management[J].Journal of Organizational Computing and Electronic Commerce,1994,4(1):1-22.

[6]McDaniel P,Prakash A.Methods and limitations of security policy reconciliation[J].ACM Transactions on Information and System Security,2006,9(3):259-291.

[7]WangYazhe,Feng Dengguo.Aconflict and redundancy analysis method for XACML rules[J].Chinese Journal of Computers,2009,32(3):516-530.

[8]Huang Feng,Huang Zhiqiu,Liu Linyuan.A DL-based method for access control policy conflict detecting[C]//Proceedings of the 1st Asia-Pacific Symposium on Internetware,Beijing,Oct 17-18,2009.New York:ACM,2009:16.

[9]Kolovski V,Hendler J,Parsia B.Formalizing XACML using defeasible description logics,TR-233-11[R].University of Maryland,2006.

[10]Xia Xiaofeng.A conflict detection approach for XACML policies on hierarchical resources[C]//Proceedings of the 2012 International Conference on Green Computing and Communications,Conference on Internet of Things,and Conference on Cyber,Physical and Social Computing,Besancon,Nov 20-23,2012.Washington:IEEE Computer Society,2012:755-760.

[11]Huonder F.Conflict detection and resolution of XACML policies[D].Rapperswil University of Applied Sciences Rapperswil,2010.

[12]Agrawal D,Giles J,Lee K W,et al.Policy ratification[C]//Proceedings of the 6th International Workshop on Policies for Distributed Systems and Networks,Stockholm,Jun 6-8,2005.Washington:IEEE Computer Society,2005:223-232.

[13]Liu Jiang,Zhang Hongqi,Dai Xiangdong,et al.A static ABAC policy conflict resolution algorithm[C]//Proceedings of the 4th International Conference on Multimedia Information Networking and Security,Nanjing,Nov 2-4,2012.Piscataway:IEEE,2012:83-86.

[14]Wang Yongliang,Chen Xingyuan,Wu Bei,et al.Security policy conflict detection and resolution based on multidimensional integer space[J].Computer Engineering,2009,35(4):134-136.

[15]Calero J M A,Pérez J M M,BernabéJ B,et al.Detection of semantic conflict in ontology and rule-based information systems[J].Data&Knowledge Engineering,2010,69(11):1117-1137.

[16]Campbell G A.Ontologies for resolution policy definition and policy conflict detection,CSM-1722007[R].Stirling:University of Stirling,2007.

[17]Li Ruixuan,Lu Jianfeng,Li Tianyi,et al.An approach for resolving inconsistency conflicts in access control policies[J].Chinese Journal of Computers,2013,36(6):1210-1223.

[18]Wang Juan,Wang Jiang,Jiao Hongyang,et al.A method of OpenFlow-based real-time conflict detection and resolution for SDN access control policies[J].Chinese Journal of Computers,2015,38(4):872-883.

附中文参考文献:

[1]李晓东,朱皓,杨卫东.安全访问控制的XML关键字检索[J].计算机科学与探索,2010,4(1):73-81.

[2]王小明,付红,张立臣.基于属性的访问控制研究进展[J].电子学报,2010,38(7):1660-1667.

[7]王雅哲,冯登国.一种XACML规则冲突及冗余分析方法[J].计算机学报,2009,32(3):516-530.

[14]王永亮,陈性元,吴蓓,等.基于多维整数空间的安全策略冲突检测与消解[J].计算机工程,2009,35(4):134-136.

[17]李瑞轩,鲁剑锋,李添翼,等.一种访问控制策略非一致性冲突消解方法[J].计算机学报,2013,36(6):1210-1223.

[18]王鹃,王江,焦虹阳,等.一种基于OpenFlow的SDN访问控制策略实时冲突检测与解决方法[J].计算机学报,2015,38(4):872-883.