基于职责分离的角色挖掘算法

王静宇 崔永娇

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

0 引 言

在访问控制系统中，基于角色的访问控制(Role-based Access Control, RBAC)具有安全、灵活和高效等优势，是目前应用研究最广泛的访问控制模型。访问控制是为用户分配一组权限，允许用户去访问系统中的某些资源，RBAC则是通过角色将权限组织在不同的集合中，并将角色分配给用户。由于角色的数量远远小于权限的数量，因此在企业中使用RBAC系统能够有效降低系统管理复杂度，提高管理效率。定义角色以及分配用户的过程称为角色工程[1]，主要有自上而下和自下而上两种方法。自下而上是专家通过分析和分解企业的业务流程来构造角色，但是当企业中用户和权限的数量变得非常大时，使用该方法构建RBAC系统则变得费时费力，不再适用。因此，根据已有的用户权限分配关系采用自动化或半自动化构造角色的自下而上的方法应运而生，这种方法又称为角色挖掘，现已成为角色工程领域研究的主要方向[2]。此外，为了更好地配置RBAC系统，还需满足各种具有约束的策略，例如：基数、先决条件和职责分离(Separation of Duty，SoD)。基数约束是指角色可拥有的用户或权限数有限，权限可分配的角色数以及用户可拥有的角色数有限。SoD是防止欺诈、保证计算机访问安全的重要约束，通常是指对于给定的k和n，至少有k个用户才用完成所给定的包含n个权限的任务。SoD是在权限方面约束用户集，但在RBAC中通常使用静态互斥角色(Statically Mutually Exclusive Roles，SMER)约束来实现。本文以权限分组为基础(简单角色挖掘算法)，结合静态互斥角色约束条件，提出一种满足静态职责分离的角色挖掘算法。

1 相关工作

职责分离(SoD)是防止欺诈行为、保证计算机访问安全的重要约束策略，也是RBAC系统所必须遵守的安全原则。对此，专家学者做了相关研究。熊厚仁等[3]针对RBAC系统中职责分离策略的冗余、冲突一致性解决问题，提出一种职责分离策略的一致性分析和判定的方法，但是该方法并未考虑到策略的实现和满足性等问题。孙伟等[4]利用枚举法，对互斥权限约束下的角色挖掘方法进行了优化改进，由于该方法使用角色职责分离验证安全约束的合理性，缺乏对于具体SoD策略的实施，且时间复杂度较大，因此在应用场景中不具有实际意义。Chen等[5]对于约束集的生成问题进行了相关研究，定义角色层次结构和一组SMER约束之间的兼容性概念，提出兼容性的必要和充分条件。Lu等[6]提出扩展布尔矩阵分解(EBMD)，是在Lu等[7]提出的矩阵分解(BMD)上进行扩展，允许负面授权角色中的否定权限或用户中的负面角色来实施SoD约束。Li等[8]将静态职责分离约束转化为静态互斥角色约束来实现，同时表明直接执行SoD策略是难以实现的，检查RBAC状态是否满足SoD策略则是有效的。同样的，Sarana等[9]针对SoD约束策略的角色挖掘问题，提出SoD-aware和后处理两种方法，SoD-aware是利用二分图从在角色挖掘过程中形成可执行的SMER，后处理的方法则是针对角色挖掘结果进行处理，判断是否满足约束。Roy等[10]基于图的最小着色数方法，提出一种在多个SMER约束下查找最小用户数的方法，得到满足约束的用户权限分配关系，但将SoD约束转化为可强制执行的SMER约束实际上是非常具有挑战性的。因此，本文的目标是以用户权限矩阵(UPA)和一组SoD约束作为输入，并找到与其一致的用户角色(UA)和角色权限(PA)矩阵以及一组t-t SMER约束，这些约束能够正确地强制执行给定的SoD约束，同时优化角色数量。

2 相关理论基础

定义1布尔矩阵(UPA)。用户-权限分配关系形式为定位布尔矩阵即二元0-1矩阵(Binary Matrix)，其中行表示用户，列表示权限。UPA矩阵中(ui，pi)值为1，表示用户ui拥有权限pi，若没有则表示为0。因此，角色挖掘就是将给定的用户-权限关系矩阵(UPA)，分解成用户-角色分配关系(UA)和角色-权限分配关系(PA)布尔矩阵。

定义2RBAC模型。假设USERS表示用户集合，数量为n；PERMS表示权限集合，数量为m；ROLES表示角色集合，数量为q；UA⊆USERS×RLOES为用户角色分配关系；PA⊆ROLES×PERMS为权限角色分配关系；UPA⊆USERS×PERMS为用户权限分配关系；RH⊆ROLES×ROLES为角色继承关系。

定义3k-n职责分离约束(k-n SoD)。k-n SoD约束定义为sod<{p1,p2,…，pn},K>,其中：1

定义4t-m 静态互斥角色(t-m SMER)。t-m SMER约束定义为smer<{r1,r2,…,rm}，t>，其中:1

定义5t-t 静态互斥角色(t-t SMER)。t-t SMER约束定义为smer<{r1,r2,…,rt}，t>，其中t≥2，1。SMER约束集合为C={C1∪C2…∪Ci}，Ci=<{r1,r2,…,rm}，t>代表一个SMER约束。

定义5静态职责分离约束下的角色挖掘(SoD-Role Mining Perms，SRMP)。给定一个用户权限分配关系UPA，一组SoD约束E，找到一组角色集R，用户角色分配关系UA，角色权限分配关系PA，SMER约束集合C，使得C强制执行E并且最小化角色数量|R|。

3 算法设计

3.1 基于职责分离的角色挖掘算法(SRMP)

本文提出的满足静态职责分离的角色挖掘算法(SRMP)，采用布尔矩阵UPA表示系统中的用户权限分配关系，以权限分组为基础，在角色挖掘过程中实施t-t SMER约束，强制执行SoD约束，得到满足约束的UA、PA，以及t-t SMER约束集C，同时最小化角色数量。其详细描述如算法1所示。

算法1满足静态职责分离的角色挖掘算法SRMP

输入：用户权限分配关系UPA，一组 SoD约束E。

输出：用户角色分配关系UA，角色权限分配关系PA，角色SoD约束关系SA，角色集R，t-t SMER约束集C。

BEGIN

1. 调用角色生成算法(mineRole)；

2. 判断约束满足问题；

3. 调用t-t SMER 约束生成算法(t-t SMER)；

END

3.2 角色生成算法(MineRole)

MineRole算法是在Blundo 等[11]提出的简单角色挖掘算法(Simple Role Mining Algorithm)基础上，采用在矩阵中权限分组的挖掘方式，生成角色集，同时在挖掘角色的过程中为角色赋予SoD约束信息，同样采用布尔矩阵表示角色与SoD约束关系SA。

本文中定义U[p]为用户u中的权限P、UC[p]定义为用户u中未被覆盖的权限p。U定义为角色中的用户、P定义为角色中的权限、Sei定义为包含一组SoD约束信息的角色集。

首先将用户权限关系转化成布尔矩阵UPA表示，根据用户中的权限数进行降序排序，然后选择用户中具有最少未被覆盖的权限的一行，作为新生成角色中的权限，加入到P中。判断新角色中的权限是否是ei中的权限，如果是则将ei约束信息赋予新生成的角色。根据所选择的权限P，查看其他用户中未被覆盖的权限是否包含P，若是则加入到U中。最后从用户权限UPA中删除已被选择的权限即将矩阵中被选择的(ui,pi)变为0。其详细算法描述如算法2所示。

算法2角色生成算法(MineRole)

输入：用户集合U，权限集合P，用户权限分配关系UPA，k-n SoD约束集E。

输出：用户角色分配关系UA，角色权限分配关系PA，角色与SoD约束关系SA，初始角色集initRoles。

BEGIN：

1.candidateRoles=∅,U=∅,P=∅,Sei=∅；

2. while there exists at least one useruwith uncovered perms

//至少存在一个未被覆盖权限的用户

3. do

4. selectuwith minimum number of uncovered perms；

//选择具有最少权限的一行

5. newRoleP=select row；

//新生成角色中的权限

6. candidateRoles=candidateRolesU{newRole}；

//新生成的角色加入候选角色集

7. if newRole having at least one permission inei

//新生成的角色中包含约束ei中的权限

8.Sei=SeiU{newRole}；

//为角色赋予SoD约束信息

9. end if

10. forv≠u

//查找其他包含P权限的用户

11. do

12. ifP⊂UC[p]

13. newRoleU=U{V}；

14. end if

15. end for

END

3.3 t-t SMER约束生成算法

t-t SMER约束生成算法是根据上文得到的用户角色分配关系UA、角色权限分配关系UA、角色与SoD约束关系SA，以及初始角色集initRoles，进行计算处理得到最终的角色权限分配关系UA、最终角色集finalRoles。

t-t SMER约束生成算法，根据算法1得到的角色与SoD约束关系SA，找到包含ei约束权限的角色集Sei，并计算角色的数|Sei|，若存在一个角色包含ei约束中的所有权限或角色数|Sei|小于用户数k，则该约束不可执行。然后根据定理1，得到t-t SMER约束中可以设置的最大约束值t，设置合理的约束值。同时计算UA中，用户分配的角色集中包含ei约束的角色数n，判断n和t的大小。若n})加入到t-t SMER约束集C；若n>t,则说明该用户角色分配关系不满足约束，选取前t个约束角色分配给用户，并从剩余角色中删除约束权限，生成不包含约束权限的新角色，重新分配给用户u和新角色集、UA、PA，得到最终角色集finalRoles、用户角色分配关系UA，以及角色权限分配关系PA。其详细算法描述如算法3所示。

算法3t-t SMER约束生成算法

输入：用户角色分配关系UA，角色权限分配关系PA，角色与SoD约束关系SA，k-n SoD约束E，初始角色集initRoles。

输出：t-t SMER约束集C，finalRoles，用户角色分配关系UA，角色无权限分配关系PA。

BEGIN:

1. caculate the number |Sei| formSA

//包含ei约束的角色数；

//得到最大的t值；

3. for eachrinSei

4. If any role inSeihas all the permission ineithen

//若Sei中存在一个角色包含所有ei中的约束权限

5. Declareeias not enforceable；

//声明ei约束不能强制执行

6. continue

7. end if

8. if

9. |Sei|

//角色的数量小于用户的数量

10. Declareeias not enforceable；

11. continue

12. end if

13. for each subset of rolesRof sizetfromSei

14. do

15. caculatenthe number of roles ofCiformUA；

//用户u中包含Ci约束的角色数

16. if

17.n

//如果用户中的角色满足约束

18.C=CU{}

//将该约束加入t-t SoD约束集

19. else

20. Select firstt-1 roles inuand generate new roles；

//选择前t个角色分配个用户u，并生成

//新角色，即从剩余角色中删除约束权限

21. Declareeias not enforceable；

//声明ei约束不能强制执行

22. updateUA；

//更新UA，为用户u重新分配不含约束的角色

23. end if

END

3.4 实例分析

用户集U={u1,u2,…,u7}，权限集P={p1,p2,…,p7}，一个由7个用户7个权限构造的用户权限关系矩阵如表1所示，设定k-n SoD约束集：

表1 用户权限关系矩阵表(UPA)

E={e1,e2}：

e1=<{p1,p3,p4},2>

e2=<{p1,p5,p6},2>

首先根据用户中的权限数降序排序，选择包含权限数最小的一行即用户u6，r1分配权限{p3,p4,p6}，e1、e2约束的权限分别包括{p3,p6}，用户{u4,u5,u6}包含r1中的权限。下一次选择用户u5，r2分配权限{p5}，e2约束的权限包含{p5},用户{u1,u2,u3,u4}包含r2中的权限。r3选择的用户为u2,权限{p1,p4}，e1、e2约束的权限包含p1,故为r3赋予e1、e2约束信息，用户{u2,u7}包含r3中的权限。R4选择u3，r4分配权限为{p2,p7}，该角色分配的用户为{u1,u3}。r5选择用户u4,分配权限为{p1,p3,p6}，e1、e2约束权限均包含p1，故为r5赋予约束信息e1、e2,分配的用户为{u4,u5}。得到用户角色分配关系UA、角色权限分配关系PA以及角色SoD约束信息SA矩阵，分别如表2、表3和表4所示。

表2 用户角色关系矩阵(UA)

表3 角色权限关系矩阵(PA)

表4 角色与SoD约束关系矩阵(SA)

根据上文中得到的角色SoD约束布尔矩阵表，计算t-t SMER约束中t可取的最大值，e1为3，e2为4，本文中均取t值为3，计算用户中包含约束的角色数，e1包含的角色为{r1,r3,r5}，转化为 t-t SMER约束为c1={,3}，根据UA判断用户中包含e1约束的角色均满足c1,因此e1是可执行的。e2包含的角色为{r1,r2,r3,r5}，转化为t-tSMER为c1={,3}，c2={,3}，c3={,3}，c4={,3}，同样根据UA判断用户中包含e2约束的角色均满足e2,因此e2是可执行的。得到最终的3-3 SMER约束集为C={C1∪C2∪C3∪C4}。

4 实验与结果分析

为了验证算法的准确性与有效性，采用现有的数据集对算法进行实验分析，并与文献[8]中提出的Naive approach方法进行比较。Naive approach方法是将给定的SoD约束转化为角色级别的静态职责分离(RSSoD)，根据RSSoD要求生成SMER约束。实验数据集如表5所示。

表5 实验数据集

本文的实验环境是：Inter(R)Core(TM)i3-3240 CPU 3.4 GHz,12 GB内存，340 GB，Window 10操作系统。在Eclipse开发环境下，利用Java语言实现算法。

本文选取2-2 SoD、2-3 SoD、3-5 SoD、3-7 SoD、5-10 SoD 5种不同类型的约束作为参数进行实验。对于给定的K和n值，从所有权限种随机选择n个权限。针对每一种SoD约束的数量，每次实验固定选取为20。但由于每次选取的权限是随机的，可能存在偏差，因此对于每个SoD实验重复20次，选取平均值作为结果。实验展示不同类型约束以及不同约束数量下，SRMP和naive approach算法在生成SMER数量、运行时间的对比关系。实验结果如图1和图2所示。

图1 t-t SoD和SMER数变化关系

图2 k-n SoD和运行时间变化关系

从图1的实验结果可以看出，随着k、n参数的增加，本文所提出的SRMP算法和Naive approach算法所生成SMER约束数也不断增多，虽然差别不大但从总体看SRMP算法生成的SMER数还是少于Naive approach算法的。从图2的实验结果可以看出，SRMP算法在运行时间上占据显著优势，尤其是当系统中数据量增多、k和n约束值增大时，与Naive approach算法相比，更能体现SRMP算法的运行效率。实验结果表明SRMP算法明显优于Naive approach算法。

5 结 语

本文提出的基于职责分离的角色挖掘算法，在角色挖掘过程中考虑SoD约束，生成 t-t SMER约束集强制执行SoD约束；使用布尔矩阵表示用户权限分配关系，利用权限分组挖掘角色，同时根据为角色赋予SoD约束信息；根据得到的用户角色、角色SoD约束关系，生成SMER约束集。实验结果表明，该算法能够有效实施给定的SoD约束生成t-t SMER约束集。未来将在本文算法中考虑其他约束，例如基数约束、最小特权等，进一步提高系统安全。