基于聚类和重排序的XACML策略评估优化方法

郑 楷，田秀霞，卢官宇，张玉秀

(上海电力大学计算机科学与技术学院，上海 200090)

1 引言

访问控制是目前安全服务中的重要机制。在众多访问控制模型中，基于属性的访问控制模型[1](ABAC)适用于开放式环境，对于访问主客体统一使用属性来描述，实现授权的细粒度化。策略决策点(PDP)是ABAC中的重要组件，负责对于访问请求的评估。OASIS组织推出的可扩展的访问控制标记语言(eXtensible Access Control Markup Language，XACML)适用于ABAC模型，使用XML的方式描述访问请求、策略和响应。XACML标准[2]通过检查用户的访问请求是否匹配策略，进而给出决策结果。

分布式资源共享、webservice等场景都需要制定大量XACML策略对资源进行细粒度化访问控制，但是随着访问请求的增加和策略规则规模的扩大，策略评估性能成为影响授权系统性能的瓶颈。

SUN公司在OASIS组织指定XACML标准后，推出了策略访问控制评估原型系统SUNXACML[3]。在PDP模块，SUNPDP采用的暴力的方式在策略库中检索适用于访问请求的规则。在策略规模较小的场景下，暴力逐条检索的方式对于评估性能来说影响不是很大。然而当系统中策略规则达到成千上万条的时候，评估时延、系统开销不容忽视。目前关于提高PDP评估性能方面的工作主要围绕优化大规模策略集[4]-[9]以及提出新的评估模型[10]-[16]展开。王雅哲等[4]利用状态覆盖思想分析造成规则冗余的原因，并给出了不同规则合并算法下的冗余判定定理。戚湧等人[5]结合规则压缩消除规则间的冗余规则，并将文本属性映射为数字属性，使用HashMap存储映射关系。S. Marouf等人[6]提出了一个基于自适应重排序和聚类的PDP框架，先对规则按主体属性分类，进一步对于主体属性使用K-means算法对规则进行聚类；并且根据评估历史，基于规则的成功命中率对规则进行重排序。通过聚类可以减少访问请求比较的规则个数，然而K-means算法需要提前指定簇的数量，而簇的数量事先并不知晓。Zhang等人[7]对于策略使用ACO算法进行分类，称ACO的分类效果优于K-means。韩道军等[8]提出基于属性与或矩阵和类型分析的XACML策略查询方法，计算出每个规则属性的区分度，利用区分度和属性与或矩阵筛选掉与当前访问请求无关的规则。Deng等人[10]针对每个属性建立了属性位图存储含有该属性的规则，通过对属性位图的逻辑与运算，确定适用于访问请求的规则。Liu等人[11]提出的评估引擎XEngine将XACML策略的属性数值化为数字连续区间，将嵌套递归的策略结构标准化为扁平结构。数字区间的匹配效率高于字符串匹配，然而属性必须是连续区间，对于属性是不连续区间的情况，方案没有给出说明。Mourad等人[12]基于集合代数提出了新的XACML框架：SBA-XACML，该框架将XACML策略/请求转化为SBA-XACML策略/请求，评估模块对转化后的请求进行评估，性能上优于XEngine。Deng等人[16]提出了一种类似于数组的数据结构规则字典，使用规则字典快速确定规则的索引；另外，使用bitmap存储策略集中规则的effect，节约存储空间。然而规则属性值变更的话，需要更新规则字典的内容结构和文本结构。位图存储的只是规则的effect，然而规则还是存储在类似于四维数组的规则字典里；规则多的情况下，内存开销大。

以上提升PDP评估性能的方案存在一些局限性。通过解决策略间的冲突、检测并减少策略间的冗余，从而优化大规模复杂策略集的方案不够高效。另外，以上提出的新的评估模型并没有结合优化大规模策略集，评估性能有待提升。本文在研究XACML策略优化方法的同时，也基于提出的两种优化方法，设计了一个包含计算中心、规则匹配器的优化评估模型PDPCR(Policy Decision Point based on Clustering and Reordering)，达到减少匹配运算量、提高匹配速度的目的。

2 背景知识

XACML 3.0标准中规定了两种模型：数据流模型和语言模型。

XACML数据流模型主要由策略执行点(Policy Enforcement Point，PEP)、策略决策点(PolicyDecisionPoint，PDP)、策略管理点(Policy Administration Point，PAP)、策略信息点(Policy Information Point，PIP)、上下文处理器(Context Handler)组成。

PAP负责为PDP提供策略/策略集。PIP负责收集主体属性、资源属性、环境属性，提供给上下文处理器。PEP主要负责访问请求的转发、响应的接收。PDP主要负责对访问请求的评估。上下文处理器主要是起到PEP和PDP之间、PDP和PIP之间的中间人作用。

数据流模型简化执行过程如下：PEP接受来自访问请求者的访问请求，将其发送给上下文处理器；上下文处理器将访问请求构建为XACML格式，并将其发送给PDP；PDP负责接收来自上下文处理器的访问请求，结合策略/策略集对访问请求进行评估，并将响应上下文返回给上下文处理器；上下文处理器将响应上下文转化为PEP本地响应格式，并将其发送给PEP；PEP根据响应结果决定是否授予给对资源的访问权限。

XACML语言模型主要由策略集(Policy Set)、策略(Policy)、规则(Rule)三部分组成，以一种树状结构嵌套定义访问权限，如图1所示。

定义1(策略集，PolicySet)：策略集是XACML策略文件的根元素，用四元组表示PS=(id，T，P，PC)。其中，id是策略集的编号；T是策略集的目标元素，规定了可以适用于该策略集的主体属性、资源属性、操作属性；P是策略集中的所有策略的集合，P=(p1，p2，…，pn)；PC是策略合并算法，用来解决策略集中发生的策略冲突或缺失。

定义2(策略，Policy)：策略是策略集的子元素，用四元组表示P=(id，T，R，RC)。其中，id是策略的编号；T是策略的目标元素，规定了可以适用于该策略的主体属性、资源属性、操作属性；R是策略中的所有规则的集合R=(r1，r2，…，rn)；RC是规则合并算法，用来解决策略中发生的规则冲突或缺失。

定义3(规则，Rule)：规则是策略的子元素，用四元组表示R=(id，T，e，c)。其中，id是规则的编号；T是规则的目标元素，规定了可以适用于该规则的主体属性、资源属性、操作属性；e是规则的决策结果，e∈{Permit，Deny}；c是规则的condition元素，通常是一个布尔函数，进一步地限定访问请求。

定义4(访问请求，AccessRequest)：访问请求用四元组表示为

Req=(subject，resource，action，environment)

其中，subject是主体属性，resource是资源属性，action是操作属性，environment是环境属性。

3 评估模型

本节详细介绍PDPCR评估模型。先给出PDPCR模型的体系结构和功能部件组成；然后介绍PDPCR中使用的策略优化技术，即聚类和重排序。

3.1 评估模型框架

PDPCR评估模型框架由两部分组成，策略预处理和策略评估，如图2所示。策略预处理是将策略/策略集中的规则抽取出来，对于大规模的规则集合基于规则相似度进行聚类，基于规则优先度对簇内规则进行重排序。策略评估是指评估模型中的计算中心接收访问请求，计算出该访问请求最适用的规则簇；规则匹配器在小规模的指定规则簇中遵循“首次出现优先”的规则合并算法寻找该访问请求适用的规则，对访问请求进行评估，同时评估记录会被写入评估日志；最后评估模型给出评估响应。

图2 PDPCR评估模型框架

3.2 规则聚类

从原始XACML策略中抽取出规则，先计算规则间的相似度；然后基于DBSCAN算法对规则集进行聚类，形成规则簇；最后计算规则簇的簇心。

3.2.1 计算相似度

规则的组成元素为：subject，resource，action，condition。计算规则间的相似度，实则计算规则对应属性间的相似度[17]。

定义5(属性相似度，Attribute Similarity)：在实际中，属性类型主要分为三种：字符串类型、数值类型、数值区间类型。针对不同类型的属性，采用不同的方法计算属性相似度。

相同元素的属性间的相似度表示为AS(attr1，attr2)。

1) 字符串类型。若2个字符串值相等，则这2个字符串属性相似度为1，否则为0。

2) 数值类型。若2个数值相等，则这2个数值类型属性相似度为1，否则为0。

3) 数值区间类型。设数值区间1为A，数值区间2为B，则

(1)

定义6(规则相似度，RuleSimilarity)：设有规则r1、r2，两者相似度为

RS(r1，r2)=w1*AS(r1.subject，r2.subject)

+w2*AS(r1.resource，r2.resource)

+w3*AS(r1.action，r2.action)

+w4*AS(r1.condition，r2.condition)

(2)

这里w1，w2，w3，w4为不同元素间的相似度权重。在XACML中，访问请求中的属性是与规则中的subject、resource、action、condition元素顺序进行匹配的，当有一个元素属性不匹配时，则剩余的元素属性不再进行比较。所以根据XACML中的规则元素匹配特性，设置w1，w2，w3，w4为递减的。

3.2.2 基于DBSCAN的规则聚类算法

在评估访问请求的过程中，为了避免全量遍历策略库，提出了一种基于DBSCAN[18]的规则聚类算法。DBSCAN(Density Based Spatial Clustering of Applications with Noise)算法是一种著名的基于密度的聚类算法，该算法可以找出样本点的全部密集区域，并把这些密集区域当做聚类簇。DBSCAN算法可以发现任意形状的聚类簇，无需提前设定聚类簇的数量，适合于对较低维度数据进行聚类。下面是规则聚类算法的一些定义。

定义7 (规则间距离，RuleDistance)：设r1、r2为2条规则，则两者间的距离为：

RD(r1，r2)=1-RS(r1，r2)

(3)

其中RS(r1，r2)为规则r1和r2间的相似度。

定义8(规则r的Eps领域半径，Eps-neighborhood)：指规则r的Eps领域半径内的规则集合。符号表示为

NEps(r)={r′∈R|RS(r，r′)≤Eps}

(4)

其中R为所有规则的集合。

定义9(核心规则，CoreRule)：若规则r的邻域半径Eps内的规则个数大于等于邻域密度阈值MinPts，即，NEps(r)≥MinPts时，规则r是核心规则。

定义10(边界规则，BorderRule)：若规则r的邻域半径ε内的规则个数<邻域密度阈值MinPts，但是r在其它核心规则的领域半径内，那么规则r是边界规则。

定义11(噪声规则，NoiseRule)：既不是核心规则也不是边界规则的规则。

定义12(直接密度可达，directly density-reachable)：若规则r是从规则r’直接密度可达的，则满足以下两个条件

1)r∈NEps(r′)

2) |NEps(r′)|≥MinPts

即满足r’是核心规则并且r在r’的Eps领域半径内。

定义13(密度可达，density-reachable)：对于规则r1，r2，…，rn，如果ri+1是从ri直接密度可达的，则称rn从r1密度可达。

定义14(密度相连，density-connected)：存在规则r1，r2，r3，如果r1和r3都从r2密度可达，则称r1和r3密度相连。

定义15(规则簇，Rule Cluster)：设R是所有规则的集合，一个规则簇C是R的一个非空子集满足以下条件：

1)∀r，r’：如果r∈C，r’从r密度可达，则r’∈C

2)∀r，r’∈C：r和r’是密度连接的

根据以上定义，有如下定理。

定理1：设规则r为规则集合R中的一个核心规则，那么集合O={o|o∈Rando从r密度可达}是一个规则簇。

定理2：设R为规则簇，规则r为R中的任意一个核心规则，那么规则簇R可以表示为集合O={o|o从r密度可达}

规则聚类算法步骤如下：

1) 将所有规则标记为unvisited，标记所有规则的clusterId为0，计数器k初始化为1；

2) 随机选择一个未访问的规则r，标记r为已访问；如果不存在未访问的规则，算法结束；

3) 如果r是核心规则，则将设置r的clusterId为k，将r的邻域半径内的规则放入集合N；

4) 对于N的每个规则rule，标记其为已访问，并更新其clusterId为k；如果rule为核心规则，则将rule的邻域半径内的所有规则添加进N；重复执行步骤4)，直到N中的每个规则都已访问；

5) 计数器k自增1，进入步骤2)。

上述过程的伪代码描述如算法1所示。

规则聚类算法需要三个输入参数：单值规则集合R、邻域半径∈、邻域密度阈值MinPts。输出是含有k+1个规则簇的集合C。算法首先是利用基于密度的思想将规则集合进行聚类，标记好每个规则的clusterId；然后基于clutserId进行规则分类，相同clusterId的规则归为一类。噪声规则的cluserId为0。聚类算法的时间复杂度是O(|R|*找出某规则邻域半径内的规则所需的时间)，其中找出某规则邻域半径内的规则采用的是遍历比较的方式，所以聚类算法的时间复杂度是O(|R|2)。基于clutserId进行规则分组算法的时间复杂度是O(|R|)。所以算法1总的时间复杂度是O(|R|2)。

算法 1：规则聚类

输入：R：单值规则集合；∈：邻域半径； MinPts：邻域密度阈值

输出：S：含有 k+1 个规则簇的集合 {C0，C1，C2，…，Ck}

function clusterRules(R，∈，MinPts)

标记所有规则的 clusterId 为 0；

标记所有规则为 unvisited；

while存在 unvisited 的规则

随机选择一个 unvisited 的规则 r；

标记 r 为 visited；

k=1；

if r 为核心规则then

r.clutserId=k；

令 N 为 r 的∈邻域内的规则集合

for rule ∈N

if rule 是 unvisited then

标记 rule 为 visited；

endif

if rule 为核心规则then

for r’∈rule的∈邻域半径内的规则

N.append(r′)；

end for

end if

if rule.clutserId==0 then

rule.clutserId=k；

end if

end for

k++；

end if

end while

S=groupByClusterId(R)；

returnS

end function

3.2.3 计算簇心

簇心规则是能够代表规则簇的规则。通过计算访问请求与簇心的相似度，可以快速确定访问请求最有可能适用的规则簇。簇心规则也是由subject属性、resource属性、action属性、condition属性组成。其中每个属性是簇内所有规则中出现频率最高的属性。比如规则簇C1所有规则中subject属性出现频率最高的是学生，那么规则簇C1的簇心规则的subject属性为学生。

3.3 簇内规则重排序

为了提高访问请求与簇内规则的匹配速度，提出了基于规则优先度的簇内规则重排序优化技术。

定义16(规则优先度，RulePriority)规则r的优先度为

RP(r)=w1*f(r.action)+w2*f(r.resource)

(5)

其中，f(attribute)为系统中属性的使用频率，f(attribute)∈[0，1]。w1，w2分别为action属性、resource属性的权重，权重大小可以根据不同应用场景进行调整。因为访问控制策略主要功能是对资源(resource)上的操作(action)进行规定与约束，所以规则优先度由资源属性和操作属性来衡量。属性使用频率表由系统管理员来维护，具体的属性使用频率可以由评估日志分析得出。簇内规则重排序算法如算法2所示。

通过计算簇内规则的优先度，将优先度大的规则置于规则簇前端，优先度小的规则置于规则簇后端。比如在访问请求中含有大量查询属性的应用场景中，将含有查询属性的规则置于簇内前端。这样当访问请求在某规则簇中顺序搜索适用的规则时，只需遍历少量规则即可得到决策结果，提高了决策效率。

算法2：规则重排序

输入：R：规则簇；f：属性使用频率表

输出：R’：重排序后的规则簇

function reorderRules(R，f)

for r ∈R

r.RP=w1*f(r.action)+w2*f(r.resource)

p.insert(r) //p为优先队列

endfor

returnp

end function

4 实验与分析

本节实验的目的是验证本文提出的方法，并与SUNPDP、SBA-XACML比较评估性能，给出量化结果。实验分为三部分进行，第一部分分析SUNXACML的评估时间，第二部分分析不同优化方法对评估时间的影响，第三部分分析不同优化方法下与访问请求比较的平均规则个数。实验环境为：Intel 2.60GHz 8核CPU，8G内存，Windows 10操作系统，JavaRuntime Environment 1.8.0。

实验中的3个访问控制策略集来自实际系统：VMS[19](Virtual Meeting System)策略集、LMS[20](Library Management System)策略集、ASMS[21](AuctionSale Management System)策略集。对三个策略集加以修改和扩展，扩展后分别含有3072、6160、9000条规则。

访问请求的构造基于策略集规则中的属性。解析策略集，得到subject属性集合、resource属性集合、action属性集合、condition属性集合。对这四个集合进行笛卡尔乘积，便可得到访问请求。然而，为了模拟真实环境中的访问请求的分布，基于评估日志中的属性使用频率，控制访问请求中的属性的满足一定条件。比如LMS系统中，访问请求action属性中的借书和还书使用频率比较高，那么在批量构造出的LMS访问请求中，大部分访问请求的action属性是借书和还书。

首先测量SUNPDP在三个策略集下的评估时间，访问请求数分别为2000、4000、6000、8000、10000。图3实验结果表明SUN PDP对于同一策略集，随着访问请求数的增加，评估时间相应增加；对于不同策略集，访问请求数相同的情况下，含有规则数多的策略集评估时间更长。SUNPDP对于每个访问请求，在含有数千条规则的策略库中遍历匹配规则，时延开销大，到达了104ms的数量级。

图3 SunPDP评估时间

接着分别对三个策略集使用规则聚类、规则聚类+重排序的优化方法，对比评估时间的差异。使用规则聚类优化技术后，VMS中3072条规则生成了12个规则簇，平均每个簇256条规则；LMS中6160条规则生成了28个规则簇，平均每个簇220条规则；ASMS中9000条规则生成了45个规则簇，平均每个规则簇200条规则。

为了尽量减小误差，评估时间的测量进行3次，取平均值。在PDPCR评估模型中，策略预处理部分，即规则聚类和重排序的时间不包含在评估时间的测量中，评估时间包括计算中心中访问请求寻找最适用的规则簇的时间以及规则匹配器中访问请求寻找适用的规则的时间。对于SBA-XACML评估模型，评估时间的测量不包含将XACML策略/访问请求转化为SBA-XACML策略/访问请求的时间，仅包含对SBA-XACML访问请求评估的时间。VMS策略集、LMS策略集、ASMS策略集的实验效果如图4所示。实验结果表明使用了规则聚类优化技术之后，访问请求的评估时间明显降低，相对于SUNPDP提升了2.5个数量级；同时使用规则聚类和重排序两种优化技术后，访问请求的评估时间进一步降低，相对于SUNPDP提升了3个数量级。

图4 不同策略集评估时间对比

最后分析不同优化方法下访问请求平均比较的规则个数。访问规则聚类将原始规模较大的策略集分解为多个小规模的规则簇，目的在于减少访问请求与规则的比较次数。图5实验结果表明，原始数千条规则的策略集，在规则聚类之后，访问请求仅需与规则簇中的规则比较100多次，即可得到判决结果，相对于SUNPDP效率提升了约1倍。在簇内规则重排序之后，高优先级的规则置于簇前端，访问请求的比较次数进一步减少。

图5 规则比较次数对比

5 结束语

本文从XACML评估效率低下问题出发，从两个方面对XACML策略进行了优化处理，并基于两种优化方法设计了一个新的评估引擎。首先是运用规则聚类优化方法，将大规模的策略集分解聚类为多个规模较小的规则簇，缩减了策略规模，减少了匹配运算量，提升了匹配速度。通过使用规则聚类优化技术，相对于SUN PDP，平均规则比较次数减少了60%，访问请求评估时间减少了约2.5个数量级。同时，为了进一步提高簇内规则的匹配速度，提出了簇内规则重排序的优化方法，基于规则优先度调整簇内规则的顺序。通过使用规则重排序优化技术，访问请求评估时间能在规则聚类优化技术的基础上继续减少约0.4个数量级。实验结果表明，基于两种优化方法的评估引擎PDPCR的评估性能明显高于其它同类系统。

未来的工作中，进一步研究含有多值属性的规则间的相似度计算方法以及精化策略集，减少策略的冗余规则，优化PDP评估性能。