张斌，商铮

1.解放军信息工程大学，郑州 450004

2.解放军军事经济学院，武汉 430000

基于属性约束的权限委托机制及冲突检测方法

张斌1，商铮2

1.解放军信息工程大学，郑州 450004

2.解放军军事经济学院，武汉 430000

针对现有的委托方法中委托约束局限于用户角色的问题，提出了一种基于属性约束的权限委托机制ARPDM，使用先决条件、受托条件和撤销条件等对委托者和受托者的能力进行约束，能够增加权限委托的约束能力，从多个方面对委托者和受托者的委托行为进行控制。分析了委托过程中可能发生的委托约束冲突、冗余委托冲突和环状委托冲突等，设计了一种基于委托树的冲突检测算法，将冲突问题映射为树中结点的关系问题，能够通过一次遍历检测多种冲突，避免了传统方法需要多次检测的问题，具有较高的效率。

属性；委托；冲突；一致性

1 引言

权限委托是指在访问控制系统中，权限所有者将自己权限的全部或一部分委托给另外一个实体，由后者代其完成相应的工作。采用委托机制能使集中式的管理工作分布化，权限管理更加灵活方便。

在权限委托机制中，若委托者的决定权过大，系统中权限的传播将难以控制，需要对委托过程中的参与者进行约束，进而保证委托过程的安全性。为了解决这个问题，现有的权限委托方法主要采用以下两种方式：（1）划分权限，在PBDM模型[1]中定义可委托角色集合，限制允许委托的权限；（2）控制受托范围，例如基于映射机制的细粒度RBAC委托授权模型[2]中定义先决角色，检查受托者的资格，并限制委托的深度。这些方法在一定程度上解决了委托约束问题，但依然存在不足。首先，现有的委托方法大多针对RBAC模型，约束条件一般都是用户所具有的角色，而角色只是用户的一个属性，需要使用更多的属性表达约束条件；其次，由于委托是用户的自主行为，不同用户之间的委托可能会产生冲突，需要消除委托冲突，保证委托的可控性[3-6]。文献[7]提出一种基于参数的委托方法，能够检测出委托约束冲突和冗余委托冲突，但是需要在每次委托中加入衰减参数，且冲突的检测需要遍历所有存在的委托链。文献[8]提出一种基于图的委托冲突检测方法，能够检测出委托约束冲突和环状委托冲突，但是检测环状委托需要以每个用户结点为起点，重复进行检测。文献[9]所提出的委托方法支持多属性约束，但是只定义了受托者获得权限所需要的条件，不能控制权限委托的范围。

针对现有权限委托机制中权限传播难以控制、冲突检测效率较低的问题，本文提出了一种基于属性约束的权限委托机制（A ttribute Restricted Perm ission Delegation M echanism，ARPDM），定义了先决条件、受托条件和撤销条件等委托约束条件，采用多种属性对委托参与者的权力进行约束，有效解决了委托过程可控问题；针对委托过程中可能出现的三类冲突，提出了一种基于委托树的冲突检测方法，能够更加有效地检测多种冲突，满足一致性需求。

2 基于属性约束的权限委托机制

ARPDM机制如图1所示。ARPDM机制中，权限的拥有者（委托者）将自己权限的全部或一部分委托给其他用户（受托者），使后者能够利用前者的权限执行相关的活动。为了保证委托过程的可控性，委托者和受托者都需要满足一定的约束条件。

图1 基于属性约束的权限委托机制

2.1 ARPDM中主要元素及关系

ARPDM中的主要元素为DOR，DEE，P，DC，ATT(DOR)，ATT(DEE)，RDC，D，它们分别表示委托者集，受托者集，权限集，委托条件集，委托者属性集，受托者属性集，再委托条件集和委托深度集。

委托条件包括三种：（1）先决条件（Prerequisite Condition），规定委托行为的发起者需要满足的条件，是对委托者是否具备委托能力的约束；（2）受托条件（Delegatee Condition），规定受托者要获得权限需要满足的条件，是对受托者能否获得委托权限的约束；（3）撤销条件（Revoke Condition），规定撤销委托权限需要满足的条件。它们的集合分别表示为PRC、DEC和REC且DC=PRC∪DEC∪REC。再委托条件用于描述受托者获得权限后，继续委托需要满足的条件，由权限的委托者在委托权限时定义。

ARPDM中主要的元素关系有：

（1）属性分配关系

DORAA⊆DOR×ATT(DOR)为委托者-属性指派关系。

DEEAA⊆DEE×ATT(DEE)为受托者-属性指派关系。

（2）用户与权限的映射关系

DOR_P(dor)返回委托者dor所具备的权限集。

DOR_DelP(dor)返回委托者dor可以委托的权限集。

DOR_DelEdP(dor)返回委托者dor已经实施委托的权限集。

DEE_P(dee)返回受托者dee所具备的权限集。

DEE_DelP(dee)返回受托者dee通过委托获得的权限集。

DelP(dor，dee)返回受托者dee从委托者dor处获得的委托权限集。

（3）属性与委托条件的关系

FulfilPRC(att(dor)，prc)∈{true，false}表示委托者dor的属性与先决条件prc的关系，该值为true时，表示委托者的属性满足先决条件。

FulfilDEC(att(dee)，dec)∈{true，false}表示受托者dee的属性与受托条件dec的关系，该值为true时，表示委托者的属性满足受托条件。

FulfilREC(att(dor)，att(dee)，rec)∈{true，false}表示委托者dor的属性、受托者dee的属性与撤销条件rec的关系，该值为true时，表示委托者和受托者的属性满足撤销条件。

（4）权限委托关系

DR⊆DOR×DEE×P×D×DEC×REC为权限委托关系，(dor，dee，p，d，dec，rec)∈dr表示委托者dor将权限p委托给受托者dee，委托深度为d，受托条件为dec，撤销条件为rec。

2.2 委托实施过程

ARPDM权限委托实施过程分为请求阶段、判定阶段和执行阶段三个阶段，它们的主要作用如下：

（1）请求阶段

在请求阶段，委托者必须向系统提供的信息有：委托权限、委托深度、撤销条件、再委托限制、受托者和受托条件等。可以表示为：

式中request.p、request.d、request.rec、request.rdc、request.dor、request.dec分别表示委托请求中的权限、委托深度、撤销条件、再委托限制、受托者和受托条件。当Check(request)=true表示委托者的请求合法，能够被系统响应。

（2）判定阶段

在判定阶段，系统根据委托请求者提供的信息，判断请求的合法性，判断的依据主要包括以下几个方面：

①是否满足先决条件

先决条件由权限的授予者定义，利用FulfilPRC函数判断委托者的属性能否满足权限委托的先决条件。当FulfilPRC(att(dor)，p.prc)=true时，表明在当前环境下委托请求者dor的属性满足权限p的先决条件p.prc，可以进行委托。

②是否违背系统安全约束

在受托者获得委托权限前，需要判断其是否因为获得委托权限而违背系统的安全约束，如职责分离等。如果违背了安全约束，那么委托将无法执行。定义用于检查受托者是否因为获得委托权限而违背安全约束的函数：

obey(P)=true表示某用户的权限集P违背了系统的安全约束，当Con(request)=true时，表明受托者dee在获得权限后不能满足安全约束，这种情况下，系统不允许委托者进行委托。

③是否满足委托深度限制

委托深度表示受托者能够继续委托的次数，用以控制权限传播的范围。权限每次委托后，其深度限制减1，即p.d=pre_p.d-1，其中pre_p表示委托前委托者拥有的权限。当p.d=0时，权限无法委托给其他用户。定义用于检查委托权限是否满足委托限制的函数：

Depth(request)=true表示请求委托的权限满足委托深度限制，能够继续委托。

（3）执行阶段

在执行阶段，在满足受托条件request.dec的情况下，受托者request.dee获得权限request.p，并且委托的深度限制d减1。如果request.dee继续委托，必须保证当前委托深度大于0，且request.dee和环境属性满足再委托限制request.rdc；当受托者属性和委托者属性满足撤销条件，即Fulfil(att(dor)，att(dee)，rec)=true时，权限委托结束，撤销受托者获得的权限。

3 权限委托冲突检测

在访问控制系统中，权限委托是一种用户的自主行为，出于灵活性的考虑，权限委托采用分布式的管理方式，每个具备权限的用户都有可能成为权限的委托者。不同的用户按照各自的权限管理需求进行委托很有可能带来委托冲突，造成权限委托的不一致。虽然ARPDM中定义了先决条件、受托条件、撤销条件等约束，但是无法避免委托冲突的发生。本节对权限委托可能引起的冲突进行定义，分析委托冲突产生的原因，提出对冲突进行检测的方法。

3.1 委托冲突定义

用户在进行权限委托时，可能出现如下几类委托冲突的情况，分别称为委托约束冲突、冗余委托冲突和环状委托冲突。

（1）委托约束冲突

委托约束冲突是指两个委托者将相同的权限委托给同一用户，并且委托约束条件不相同的情况。如图2所示，委托约束冲突可分为三类，委托深度冲突、受托条件冲突和撤销条件冲突，它们分别表示如下：

图2 委托约束冲突

图3 冗余委托冲突

（2）冗余委托冲突

在定义冗余委托冲突前，首先定义委托链。

委托链：关于权限p的委托链是一个由参与委托的用户组成的序列＜u0，u1，…，un＞。在委托链中，每个用户都与其后序用户存在委托关系，即∀ui∈{u|uin ＜u0，u1，…，un＞}(0≤i＜n,i∈Z)，∃d,dec，rec使(ui，ui+1，p，d，dec，rec)∈dr。

冗余委托冲突可分为两种，一类是与原始权限相关的冗余，如图3左部，某用户u1已经由授权管理员授予了某权限p1，而其他用户又将权限p1委托给u1，即(u2，u1，p1，d1，dec1，rec1)∈dr，(M，u1，p1)∈A（表示管理员M为u1分配权限p1）；另一类是与委托权限相关的冗余，如图3右部，某用户u3将权限p2委托给u4和u5，u4将权限委托给其他人后，又将权限委托给u5，即(u3，u5，p2，d4，dec4，rec4)∈dr，并且存在一个关于权限p2的委托链＜u3，u4，…，u5＞。

（3）环状委托冲突

环状委托冲突是指某用户将权限委托后，经过若干次委托，又成为权限的受托者，如图4所示。用户u1将权限p1委托给其他用户，其他用户又将权限委托给了u1。环状委托使得权限的委托者成为权限的受托者，可能造成委托的无限循环，无法确定最终的受托者。对于权限p，如果存在委托链＜ui，uj，…，ui＞(0＜i，j≤n，i，j∈Z)，则称存在环状委托。

图4 环状委托冲突

3.2 委托冲突检测

根据ARPDM的特点，提出一种基于带参数委托树的委托冲突检测方法，将系统中的委托冲突状态映射为对应的委托树结构，从而将委托冲突问题映射为树中结点的关系问题，并提出一种高效的冲突检测算法。

委托树：关于用户u的委托结构是一个树Tree(u)= (v，F)，其中v是树的根结点，F是m≥1棵树的森林，F=(T1，T2，…，Tm)，其中Tk(1≤k≤m)称为根结点v的第k棵子树。在委托树中，每个节点都对应一个用户，父结点与子结点的连线代表用户与用户之间的权限分派关系，如图5所示。

图5 委托树示例

假定委托机制中委托权限最初都由系统管理员授予，如果将管理员看做委托树的根结点，将它的子结点看做是得到授权的用户，将深度大于1的结点看做是得到委托权限的用户，形成的树形结构可以映射为系统的委托状态。在该树中，只要用户委托成功，就在其对应的结点下建立孩子结点；当需要进行委托撤销时，就删除委托者对应的子结点。

在委托树中，每个结点都对应一个用户和一个权限集，即任取树中结点vi，存在ui和Pi使得ui=user(vi)，Pi=pers(vi)，分别映射为结点vi所对应的用户和权限集。委托树生成过程如下：

（1）生成委托树的根结点v，其对应的用户为授权管理员，其对应的权限集为所有已经分配出去的权限。

（2）若授权管理员为用户ui分配了权限集Pi，则新建根结点的子结点vi，且ui=user(vi)，Pi=pers(vi)。管理员为几个用户分配权限，则根结点就有几个孩子结点。

（3）对于委托树中的每一个非根结点vx，其对应的用户uy为其他用户uj委托了权限集Pj，则新建结点vx的子结点vj，且uj=user(vj)，Pj=pers(vj)。

（4）重复步骤（3），直到所有权限委托完毕。

在委托树中，树中结点主要有两种关系：父子关系和祖先子孙关系。父子关系代表直接的委托关系，如果两个结点满足关系vi=parent(vj)，则称结点vi是结点vj的父结点。满足父子关系的结点，其对应的用户具有委托关系，即∃p,d,dec,rec，使得(user(vi),user(vj),p,d,dec,rec)∈dr，由于结点vj所代表用户的全部权限都是由结点vi委托的，因此两个结点权限集满足关系pers(vj)⊂pers(vi)。祖先子孙关系代表间接的委托关系，若两个结点满足关系vi=ancestor(vj)，则称vi是vj的祖先结点，它们之间必然存在一条委托链＜user(vi)，…，user(vj)＞，并且pers(vj)⊂pers(vi)。

通过对委托树的分析，将委托冲突的检测问题映射为树中结点的关系问题，并给出如下定理：

定理1委托机制中不出现委托约束冲突的条件是委托树上的相同用户的结点，其对应权限集的交集为空，或它们的父结点相同，或相同权限的委托深度、受托条件和撤销条件相同。

通过反证法证明，假设委托树上存在相同用户的结点，这两个结点权限集的交集不为空、它们的父结点不同且相同权限的委托深度、受托条件或撤销条件是不同的，证明存在委托约束冲突。

结论：存在委托约束冲突。

证明：由于(user(v3)，user(v1)，px，d1，dec1，rec1)∈dr且(user(v4)，user(v2)，px，d2，dec2，rec2)∈dr，并且user(v1)=user(v2)，user(v3)≠user(v4)，当d1≠d2时，不同用户为相同用户委托相同的权限，且深度不同，存在深度冲突；

当dec1≠dec2时，不同用户为相同用户委托相同的权限，且受托条件不同，存在受托条件冲突；

当rec1≠rec2时，不同用户为相同用户委托相同的权限，且撤销条件不同，存在撤销条件冲突。得证。

定理2委托机制中不出现冗余委托冲突的条件是委托树上的相同用户的结点，其对应权限集的交集为空或它们父结点不是祖先子孙关系。

用反证法证明，假设委托树上存在相同用户的结点，这两个结点权限集的交集不为空且它们的父结点是祖先子孙关系，那么一定存在冗余委托冲突。

条件：v1，v2∈Nodes(T)，user(v1)=user(v2)，pers(v1)∩pers(v2)≠φ，v3=parent(v1)，v4=parent(v2)，v3=ancestor(v4)

结论：存在冗余委托冲突

证明：由pers(v1)∩pers(v2)≠φ可知∃p，使p∈pers(v1)∩pers(v2)。

如果v3是根结点，则∃d1，dec1，rec1，使(M，user(v1)，p)∈A且(user(v4)，user(v2)，d1，dec1，rec1)∈dr，又因为user(v1)=user(v2)，满足第一类冗余委托的条件，存在冗余委托。

如果v3不是根结点，则∃d2，dec2，rec2，d3，dec3，rec3使 (user(v3)，user(v1)，p，d1，dec1，rec1)∈dr并且(user(v4)，user(v2)，p，d2，dec2，rec2)∈dr，由于v3=ancestor(v4)，v4=parent(v2)可知，v3=ancestor(v2)，因此存在关于权限p的委托链＜user(v3)，…，user(v4)，user(v2)＞，因为v1和v2所指示的用户相同，即user(v1)=user(v2)，因此存在关于权限p的委托链＜user(v3)，…，user(v4)，user(v1)＞。

又因 (user(v3)，user(v1)，p，d1，dec1，rec1)∈dr成立，满足第二类冗余委托的条件，存在冗余委托。得证。

定理3委托机制中不出现环状委托冲突的条件是委托树上所有结点所代表的用户都与其祖先结点代表的用户不相同。

通过反证法证明，假设委托树上存在相同的用户，且它们之间存在祖先子孙关系，则存在环状委托冲突。

条件：v1，v2∈Nodes(T)，user(v1)=user(v2)，v1=ancestor(v2)

结论：存在环状委托冲突

证明：∀p∈pers(v2)，由于v1是v2的祖先结点，所以p∈pers(v1)成立，且存在关于权限p的委托链＜user(v1),…，user(vx)，user(v2)＞，因为v1和v2所指示的用户相同，即user(v1)=user(v2)，得到关于权限p的委托链＜user(v1),…，user(vx)，user(v1)＞，因此环状委托冲突存在。得证。

本文所提出的方法需要在委托树中查找相同用户的结点，对树中结点进行遍历并进行对比，其时间复杂度为O(n2)，其中n表示委托树中结点的数量。文献[1]、[2]、[10]中所提出的委托方法通过受托者的角色和委托次数等对委托进行约束，在ARPDM中都可通过定制约束条件中的属性来实现（如将受托条件设为用户属性、把再委托条件定义为剩余委托次数必须大于0）。文献[7]的权限检查方法是基于委托链的，每次检测都需要遍历所有的委托链，与该方法相比，本文的方法能够检测出更多的冲突类型，并且以可视化的方式进行检测。文献[8]中基于图论的环状委托查找算法的时间复杂度为O(m3)，其中m表示委托图中结点的数量，与该方法相比，本文的方法在n＜m3时具有更好的时间性能，且能够通过一次检测判定三种不同的冲突。

4 结论

本文提出了一种支持多属性约束的权限委托机制ARPDM，采用多种约束条件对委托参与者进行约束，能够提高委托的可控性，防止随意委托的情况。为了避免不同用户按照各自的需求实施委托可能会造成委托冲突的问题，本文分析了三类委托冲突，提出了一种基于委托树的冲突检测方法，将委托冲突的问题映射为委托树中结点的关系问题，能够通过一次遍历检测多种冲突，提高冲突检测的效率。

[1]Zhang Xinw en，Oh S，Sandhu R.PBDM：a flexible delegation model in RBAC[C]//Proceedings of the SACMAT’03.Como，Italy：ACM Press，2003.

[2]蔡伟鸿，韦岗，肖水.基于映射机制的细粒度RBAC委托授权模型[J].电子学报，2010，38（8）.

[3]孙伟，邬长安，王瑞民.角色转授权模型中授权冲突问题的解决方案[J].计算机工程与应用，2008，44（36）：244-248.

[4]Ruan Chun，Varadharajan V.Resolving conflicts in authorization delegations[C]//The Australian Conference ACISP2002，July 3-5，2002.

[5]周丽丽，王凤英.协同环境下的委托授权模型架构及实现[J].山东理工大学学报：自然科学版，2010，24（5）：11-14.

[6]陈旭日，徐炜民，沈文枫，等.基于最小生成树的委托授权模型[J].计算机应用与软件，2007，24（11）：47-49.

[7]Ruan Chun，Varadharajan V.A weighted graph approach to authorization delegation and conflict resolutions[J]. LNCS 3108：ACISP，2004：402-413.

[8]洪帆，段素娟，黎成兵.基于图的委托授权模型[J].北京邮电大学学报，2005，28（6）：5-7.

[9]叶春晓，吴中福，符云清，等.基于属性的扩展委托模型[J].计算机研究与发展，2006，43（6）：1050-1057.

[10]翟征德.基于量化角色的可控委托模型[J].计算机学报，2006，29（8）：1401-1407.

ZHANG Bin1,SHANG Zheng2

1.PLA Information Engineering University,Zhengzhou 450004,China
2.PLA Military Economic Academy,Wuhan 430000,China

To solve the constraints of user role in permission delegation methods,the paper proposes an attribute restricted permission delegation mechanism to strengthen the delegation constraints,in which the capability of delegators and delegatees is constrained by prerequisite condition,delegatee condition and revoke condition.By analyzing conflicts existing in the process of delegation,such as delegation constraint conflicts,redundant delegation conflicts,circle delegation conflicts and so on,this paper designs a conflict detection algorithm based on delegation tree.In this algorithm,permission conflicts can be expressed the relationship of nodes in delegation tree,and multiple delegation conflicts can be detected efficiently through one traversing of delegation tree.

attribute;delegation;conflict;consistency

A

TP393

10.3778/j.issn.1002-8331.1209-0256

ZHANG Bin,SHANG Zheng.Attribute restricted permission delegation mechanism and delegation conflict detecting method.Computer Engineering and Applications,2014,50（16）：95-99.

国家重点基础研究发展规划（973）（No.2011CB311801）。

张斌（1969—），教授，硕士生导师，主研方向：网络与信息安全；商铮，男，硕士研究生。E-mail：zhangyym@xinhuanet.com

2012-09-23

2012-12-17

1002-8331（2014）16-0095-05

CNKI网络优先出版：2012-12-20,http://www.cnki.net/kcms/detail/11.2127.TP.20121220.1652.004.htm l