基于概念格分层的角色最小化优化算法

王静宇 吴晓晖

(内蒙古科技大学信息工程学院 内蒙古 包头 014010)

0 引 言

自底向上的角色工程(Role Engineering)[1]，也被称为角色挖掘(Role Mining)，它是通过数据挖掘的方法对访问控制系统现存数据中的用户-权限之间关系的进行分析，然后自底向上挖掘出可以安全管理系统的角色。这种方法可以半自动化或自动化地实现角色的提取和优化。目前大数据及复杂的信息系统中提取和优化角色是一个热点研究问题[2]。

在属性角色挖掘算法上，传统的数据挖掘技术存在一些不足之处，它在挖掘过程中常常会挖掘出大量冗余的属性角色信息，造成了属性角色和权限管理复杂性的增加。而属性角色挖掘算法的目标就是找出一组最小角色集合能够安全有效地实现系统中用户权限的分配、删除和更新等管理，因此如何高效地找到满足最小权限原则的最小属性角色集合成为角色挖掘的一个重要研究内容。目前角色挖掘方面的算法和研究成果已有很多[3-8]，都是NP完全的。20世纪80年代，德国的Wille教授提出形式概念分析[9](Formal Concept Analysis,FCA),它的核心数据结构就是概念格。概念格作为一种工具，由于其具有的一些特点在角色挖掘方面有很大的优势[10]，这方面已有一些重要研究[11-15]。文献[16]在基于概念格的RBAC模型基础上，给出了概念格模型上最小角色集、角色约简、角色替代的定义及相关定理的证明。为了降低时间复杂度，还提出了一种贪婪算法寻找最小角色集。

本文利用概念格的RBAC模型，引入概念格分层的性质，将概念格分层的性质与角色约简等定理相结合，提出一种逐层查找最小角色集的优化算法，避免贪婪算法带来的重复性计算，进一步提高查找最小角色集算法的时间性能，降低算法的时间复杂度。通过仿真实验验证了算法的有效性。

1 基本概念及性质

1.1 概念格

三元组K=(U,M,I)称为一个形式背景(简称背景)，其中U表示对象的集合，M表示属性的集合，I是U与M两个集合的笛卡尔积U×M上的二元关系。(u,m)∈I(或写作uIm)表示对象u具有属性m。通常形式背景用一个矩形的表来表示，它的行表示对象，列表示属性。若u行m列的交叉处用数字1，则表示对象u拥有属性m；若u行m列的交叉处用数字0，则表示对象u不拥有属性m。

设K=(U,M,I)为一个背景，若A⊆U,B⊆M,令：

f(A)={m∈M|∀u∈A,(u,m)∈I}

g(B)={u∈U|∀m∈B,(u,m)∈I}

如果A、B满足f(A)=B,g(B)=A，则称二元组(A,B)是形式概念(简称概念)。A是概念(A,B)的外延，B是概念(A,B)的内涵。用L(U,M,I)或L(K)表示背景K=(U,M,I)上的所有概念的集合。

设K=(U,M,I)是一个形式背景，∀A,A1,A2∈U,∀B,B1,B2∈M,则有以下性质：

性质1A1⊆A2⟹f(A1)⊇f(A2)，B1⊆B2⟹g(B1)⊇g(B2)；

性质2A⊆g(f(A))，B⊆f(g(B))；

性质3f(A)=f(g(f(A)))，g(B)=g(f(g(B)))；

性质4f(A1)∩f(A2)=f(A1∪A2)，g(B1)∩g(B2)=g(B1∪B2);

性质5(g(f(A)),f(A))和(g(B),f(g(B)))都为概念。

设(A1,B1)和(A2,B2)是形式背景K=(U,M,I)的两个概念，若A1⊆A2(等价于B2⊆B1),则称(A1,B1)是(A2,B2)的特化概念，或(A2,B2)是(A1,B1)的泛化概念。用“≤”符号表示概念之间的这种特化-泛化关系为，即(A1,B1)≤(A2,B2)。在形式背景K=(U,M,I)上的所有概念连同特化-泛化关系构成一个完备格，称为概念格，记为L(U,M,I)或L(K)。在L(K)中，如果A1⊂A2，且不存在概念(A3,B3)，使得A1⊂A3⊂A2((A1,B1)≤(A3,B3)≤(A2,B2)),则称(A1,B1)是(A2,B2)的直接子概念，(A2,B2)是(A1,B1)的直接父概念，并记作(A1,B1)<(A2,B2),将直接父概念和直接子概念用线段连接起来就构成了概念格的Hasse图。

对于一个对象u∈U,通常用f(u)代替f({u})来表示对象u的对象内涵{m∈M|ulm}，g(m)代替g({m})来表示属性m的属性外延{u∈U|ulm}。故(g(f(u)),f(u))一定是概念，称为u的对象概念。同样，(g(m),f(g(m)))也一定是概念，称为m的属性概念。

1.2 基于概念格的RBAC

访问控制矩阵的三个基本要素为主体(用户)、客体(资源)和操作。列表示主体，行表示客体，矩阵中的列行交叉处表示主体对客体之间的操作。基于角色的访问控制中，用户表示主体，权限表示操作与客体(对象)的二元组，并且引入角色的概念，有以下相关定义：

1) 用户集合U(USERS)、角色集合R(ROLES)、权限集合P(PRMS)；

2) 用户权限分配关系：UPA，将此关系分为用户与角色的关系UA和角色与权限的关系PA来表示；

3) 用户角色分配关系：UA⊆U×R,表示多对多的用户和角色的对应关系；

4) 角色权限分配关系：PA⊆R×P,表示多对多的角色和权限的对应关系；

5)pers(r)={p∈P|(r,P)∈PA}表示角色r所拥有的权限集；

6)PERS(R)={p∈P|r∈R,(r,P)∈PA}表示角色集R所拥有的权限集。

根据这种对应关系，一个形式背景K=(U,M,IA)就对应于一个访问控制矩阵，其中U表示用户集合，P表示权限集合，IA⊆U×P。对于u∈U,p∈P,(u,p)∈IA表示用户u拥有权限p。因此可以用表1的矩形表来表示RBAC模型下的形式背景。形式背景生成的概念格L(K)如图1所示。

表1 形式背景示例

图1 表1所示形式背景的概念格Hasse图

2 最小角色集

2.1 概 念

定义1角色挖掘问题 给定一个m×n的访问控制矩阵A(表示用户-权限的关系)，将A分解为大小分别为m×k和k×n的两个矩阵UA(表示用户-角色的关系)和PA(表示角色-权限的关系)，使得k在所有可能的矩阵分解中最小。

在概念格上，由于可以挖出所有可能的角色，并且概念和角色是一一对应的，角色挖掘问题中在访问控制矩阵A上求解最小角色集的问题就可以等价于在概念格生成的角色概念集合中求解最小角色概念集的问题。

定义2最小属性角色概念集 设形式背景K=(U,M,I)，Sm是形式背景生成的概念格L(K)当中的一个概念集合。如果Sm满足以下两个条件，则称Sm为访问控制背景K上的最小属性角色概念集。

条件1对于访问控制背景K中每个用户所拥有的权限，都可以用概念集合Sm中的若干个概念的内涵的并集来表示。

条件2概念集合Sm中的概念个数是最小的。

文献[16]给出了相关定理及证明：

定理1概念格上所有对象概念的集合必然满足定义2最小角色概念集定义中的条件1。

定理2角色集替代具有传递性。

定理3设CS⊆L(K),C∈L(K),CS是C的所有父概念构成的集合，若C不是属性概念，则C可以用CS来替代。

定理4概念格上由属性概念诱导的角色集不存在其他替代。

定理5既是属性概念，也是对象概念的概念必然包含在最小角色概念集中。

2.2 概念格分层

对于K=(U,M,I)的形式背景，其生成的概念格为L(K)，a是L(K)中的一个概念节点，节点a的父节点集合为Sf，则节点a的层号值为：

从L(K)的顶点开始遍历整个概念格节点，则L(K)中的每个节点的层号是唯一的。

入度Indegree：该节点的父节点数目。

出度Outdegree：该节点的子节点数目。

对于概念格L(K)中的节点，可以用层号、入度以及出度来标记它，记作(Layer，Indegree，Outdegree)。

如图1所示的概念格Hasse图，将它分层并用(Layer，Indegree，Outdegree)标记每个节点如下：

第0层：1#(0，0，2)。

第1层：2#(1，1，2)，3#(1，1，3)。

第2层：4#(2，1，1)，5#(2，2，2)，6#(2，1，2)，7#(2，1，2)。

第3层：8#(3，2，2)，9#(3，2，1)，10#(3，2，1)。

第4层：11#(4，2，1)，12#(4，1，1)。

第5层：13#(5，4，0)。

性质6位于同一层的节点之间不能相互转化。

性质7任一个第N+1层的节点，至少被一个第N层的节点所覆盖。

推论1由性质6可知，同层节点之间不存在替代和约简，故同层节点可以同时按层从底向上进行替代和约简。

推论2由定理3及性质7可知，只有当对象集合节点的父节点大于等于2时，该节点才能被其父节点所替代。

推论3由定理4可知，当遇到属性概念时就不能在被其他替代，可以找到属性概念所在的层作为角色替代的终止条件。

3 算法描述

本节主要描述在概念格中寻找最小概念角色集的算法。首先可以使用任意一种构造概念格的方法从形式背景下构造出概念格，然后再进行最小概念角色集查找算法。

根据第2节介绍，算法的主要思想是：首先先遍历整个概念格得到层号值，就可以得到每个格节点对应的(Layer，Indegree，Outdegree)标记向量； 然后从对象概念的集合开始，根据层号得到算法的起始位置和终止位置，从下到上逐层将集合中满足条件的角色概念用父概念集合替代；最终得到最小角色概念集。

3.1 概念格分层算法

概念格分层算法如算法1所示，目的是求得概念格各个节点的层号。该算法是根据经典的Bellman-Ford算法(求最短路径算法)改写的。首先将输入的概念格 Hasse图边权值赋予负值，找到顶点C0赋予零，从顶点开始利用Bellman-Ford算法的原理求出每个节点到顶点C0的最长路径的dist()，这个值是个负值，故取dist()的相反数得出每个节点的层号；然后得到每个节点的标记向量(Layer，Indegree，Outdegree)。

算法1概念格分层算法

Function StratificationLattice(L(K))

输入：概念格L(K)

输出：每个节点的层号Layer以及标记

向量(Layer，Indegree，Outdegree)

BEGIN

1. 查找没有前驱节点的节点C0为Hasse图的顶点；

2. Fori=0；i<总节点数n；i++；

3.dist(i)=∞

4. END Fori

5. dist(C0)=0；

6. Fori=1，i<总节点数n；i++；

7. For 每一条边e(u,v)；

8. Ifdist(u)+w(u,v)

9.dist(v)=dist(u)+w(u,v)；

10.Layer(v)=-dist(v)；

11. END IF

12. END Fore(u,v)

13. END Fori

14. 为每个节点得到标记向量(Layer，Indegree，Outdegree)

END

算法1第1～5行找到Hasse图顶点并初始化每个节点到顶点的最长路径dist()。第6～10行遍历所有边得到各节点的层号。第8行，若节点u和节点v存在vu关系，则w(u,v)=-1。算法1的时间复杂度为O(Ne)，其中N为Hasse图的总节点数，e为Hasse图的总边数。

3.2 查找算法

算法2查找算法描述

Function SearchRole(L(K))

输入：概念格L(K)；

输出：最小角色集MinRoleSet

BEGIN

1.ObjSet:={概念格L(K)中的所有对象概念}；

2.AttSet:={概念格L(K)中的所有属性概念}；

3.MinRoleSet:=ObiSet∩AttSet

4. 标记MinRoleSet中的概念为必选角色概念；

5.CandidateRoleSet:=ObjSet-MinRoleSet；

6. 得到AttSet集合中所有属性概念的最小层数Layer1；

7. 得到CandidateRoleSet集合所有对象概念的最大层数Layer2；

8. DO

9.RoleSet:=CandidateRoleSet；

10. FOR eachP∈CandidateRoleSet

11. FORLayerC=Layer2,LayerC<=Layer1,LayerC--；

12. IF(P不是属性概念)AND(IndegreeC>=2)THEN

13. 将P的所有父概念加入CandidateRoleSet,并删除P；

14.TempSet:=CandidateRoleSet；

15. IFTempSet<=RoleSetTHEN

16.RoleSet:=TempSet；

17. END IF；

18.CandidateRoleSet:=RoleSet；

19. END IF；

20. END FOR；

21. END FOR；

22. 将CandidateRoleSet中的所有概念移至MinRoleSet；

23. ReturnMinRoleSet；

END

查找算法如算法2所示，其中：第1～2行初始化ObjSet和AttSet分别保存对象概念和属性概念；第3～4行根据定理5计算出必选角色概念，并标记必选角色概念然后保存到MinRoleSet集合中；第5行是去除必选角色概念得到待选角色概念集合并保存到CandidateRoleSet集合中；第6～7行得到终止与起始的层数；第8～21行是对待选角色集合进行角色替代和约简，直至到达算法的终止层数并且找不到更小的角色概念集就结束算法；第22行将算法找到的最后的结果保存到MinRoleSet集合中即为最小角色概念集。本算法的时间复杂度为O(UP)，其中U表示用户数，P表示属性(权限)数。

4 实验及分析

本文实验环境平台：硬件是3.0 GHz的CPU和8 GB内存，操作系统是Windows 7。实验主要从时间复杂度和准确度两方面验证算法的有效性。仿真测试数据集是随机生成了两组形式背景数据集。为了验证本文优化算法的结果，与文献[16]的SearchMinRole方法进行对比。

第一组形式背景数据集，权限的数目不变，都为30，用户数目从100到500，每一次间隔20的增加进行测试算法的时间复杂度和准确度。此次实验的目的是观察用户数目增加时算法的时间复杂度和准确度(真实的最小角色概念集与算法所找到的最小角色概念集的比例)，并与SearchMinRole方法进行对比。图2显示了算法的时间复杂度，图3显示了算法的准确度。可以看出，随着用户数目的增加，两个算法的时间复杂度都呈指数级增长，准确度下降。主要原因是用户数目的增加，导致了概念格构造时会产生大量的概念集合，在进行搜索角色替代需要更多的时间。图2中，随着用户数目的增多，本文算法比SearchMinRole算法的时间复杂度有很大的优化，这是由于本文采用层次化的方法，按层进行角色替代，避免了SearchMinRole算法迭代带来的一些重复性计算。图3中，本文的算法与SearchMinRole算法的准确度大致相同。

图2 用户数目增大时算法的时间复杂度

图3 用户数目增大时算法的准确度

第二组形式背景数据集，用户的数目不变，都为200，权限数目以每一次间隔10增加，从10到150进行测试算法的时间复杂度和准确度。此次实验的目的是观察权限数目的变化对算法的时间复杂度和准确度的影响，并与SearchMinRole方法进行对比。图4显示了算法的时间复杂度，图5显示了算法的准确度。可以看出，随着权限数目的增加，两个算法在时间开销方面都呈指数级增长，准确度上升。由于权限数目的增加，导致了概念格构造时会产生大量的概念集合，在进行搜索角色替代需要更多的时间。但是权限的数目增多使得概念格的连通性增大，更容易找到最小角色概念集，准确度就会提高。图4中，随着权限数目的增多，本文算法比SearchMinRole算法的时间复杂度有很大的优化。图5中，本文的算法与SearchMinRole算法的准确度大致相同。

图4 权限数目增大时算法的时间复杂度

图5 权限数目增大时算法的准确度

由以上两组实验结果分析可知，本文算法是实用有效的，能够根据角色拥有的权限找到最小的角色概念集，降低复杂系统中访问控制策略的管理难度。相比SearchMinRole方法在时间复杂度方面有更高的效率。

5 结 语

本文研究了基于概念格分层的最小角色集算法问题。根据最小角色集、角色替代和角色约简的定义及定理，结合概念格分层的性质，提出了一种逐层进行角色替代去寻找最小角色集的算法，降低了复杂系统访问控制的管理难度，提高了系统安全性。最后通过实验证明了算法的有效性。

研究利用分层方法构造概念格的算法，与本文的查找算法相结合，进一步降低时间复杂度是一个值得研究的工作。另外，用户数目过大时，算法的准确性会下降，提高准确性是下一步的研究方向。