基于枚举法的角色挖掘及其约束性研究

孙伟++苏辉

摘要：针对现有角色挖掘结果存在冗余、缺乏约束性等问题，结合RBAC系统状态安全性等方面的研究，提出一种基于子集枚举的角色挖掘研究方法，给出了枚举角色挖掘的算法描述。该方法使用职责分离约束限制完成任务所需的最小用户数，利用互斥角色约束限制用户允许拥有的最大角色数，并给出了最小约束构造算法及其正确性证明，能够满足系统的安全性与约束性要求。

关键词：角色挖掘 子集枚举 安全性 约束性

中图分类号：TP309 文献标识码：A 文章编号：1007-9416（2016）12-0064-02

基于角色的访问控制（RBAC）是当前主流的访问控制机制之一。为了在传统非RBAC系统中实施RBAC策略，需要构造合适的角色集并辅助构建RBAC系统，称之为角色工程。通常存在自顶向下与自底向上两种角色工程方法[1-2]。自顶向下方法从工程用例的需求分析出发，根据执行任务所需的不同权限设计角色系统[3-4]。自上而下的方法得出的角色集虽然更加符合企业和组织的实际情况，但是该方法需要大量的专家对业务逻辑进行分析，而这种成本对中小型企业也许是无法承担的，一旦组织内的业务和职能有所变化就需要重新进行业务分析得到新的角色集以适应这种变化。相比于自顶向下实施起来非常困难、容易出错、成本代价高的缺点，自底向上方法从底层的用户-权限分配关系出发，利用数据挖掘技术提取满足已有访问模式的不同权限而形成角色系统，并称此方法为角色挖掘。与自顶向下的人工處理方式相比，角色挖掘能够自动、快速地构建或辅助构建RBAC系统，现已成为角色工程技术的主要研究方向[5]。

现有角色挖掘方法按输出结果可分为两类：第一类仅输出挖掘角色集，不考虑角色层次关系，这类算法包括Complete Miner（CM）、Fast Miner（FM）等；第二类输出构建的系统状态，允许存在角色层次，这类算法包括ORCA、Graph Optimization（GO）、HP Role Minimization（HPRM）、HP Edge Minimization（HPEM）、Hierarchical Miner（HM）。本文结合RBAC系统状态安全性等方面的研究，提出一种基于子集枚举的角色挖掘研究方法，以满足应用系统的约束性要求。

1 基于子集枚举的角色挖掘

文献[6]通过枚举底层的不同权限子集挖掘角色，并允许角色重叠，提出完全挖掘和快速挖掘两种算法。前者虽能从用户-权限分配关系中穷举所有待选角色集，但时间复杂度为指数级，挖掘效率低；后者改进挖掘过程，统计关联角色的用户数，虽未能穷举所有角色，但挖掘效率优于前者。

为了体现枚举挖掘的高效性与完整性，基于枚举法的角色挖掘基本思想：对于给定的访问控制矩阵（M（UPAoriginal）），根据哈希映射规则将M（UPAoriginal）转换为原始用户-权限关联（UPAoriginal）；将分配给用户的不同权限集作为整体视为角色，确立原始角色集（InitRoles），并计算关联不同角色的用户数；结合集合论的枚举法，通过二重循环将任意两原始角色做交集，产生新角色（NewRole），确定候选角色集（CandRoles），进而构建URAoriginal和PRAoriginal。以下给出枚举挖掘法的算法（EBRM Algorithm）描述。

EBRM Algorithm

输入：M（UPA）

输出：URA，Cand_Roles

1）根据哈希映射规则将M（UPA）转换为UPA

2）创建Init_Roles

Begin

初始化Init_Roles=（；

for（UPA中的任意用户u）

if（assigned_permissions（u）（Init_Roles） then

Init_Roles=Init_Roles（{assigned_permissions（u）}；

End

3）创建New_role，Cand_Roles，并指派URA

Begin

初始化New_role=null，Cand_Roles=（，URA=（；

for（Init_Roles的任意角色ri）

{Init_Roles= Init_Roles＼{ri}；

Cand_Roles=Cand_Roles（{ri}；

for（Init_Roles的任意角色rj）

{New_role= ri（rj；

if（（New_role（Cand_Roles）（（New_role！=rj）） then

{Cand_Roles=Cand_Roles（{New_role}（{rj}；

；

}

else if（New_role（Cand_Roles） then

；

else if（New_role==rj） then

；

}

}

End

2 系统状态的安全性

随着信息技术的不断发展和大规模应用，系统的安全性备受关注。RBAC系统的安全性受角色工程方法的影响，而角色结果又取决于互斥约束的设置，不同的挖掘结果可能破坏系统安全。角色职责分离（k-n RSSOC）和互斥角色约束（t-m SMER）[7]是保证状态（安全的两项基本策略，能够检测不符合要求的角色。借助职责分离研究如何设置互斥约束，可以保证系统的安全性。以下给出两命题。

命题1 当t=2时，c1=smer<{r1，r2，…，rn}，t>可准确实施e1=rssoc<{r1，r2，…，rn}，n>。

4 结语

本文提出的研究方法基于子集枚举思想，给出了一种EBRM算法，并通过职责分离与互斥角色挖掘满足约束要求的角色结果。然而，本文方法未能体现RBAC机制的权限分配势约束要求，存在局限性。因此，如何优化角色挖掘，以满足系统对权限所分配角色数的限制要求，进一步增强挖掘结果的可解释性及系统的安全性是下一步需要研究的问题。

参考文献

[1]Li R，Li H，Gu X，et al.Role Mining Based on Cardinality Constraints[J].Concurrency and Computation：Practice and Experience，2015，27（12）：3126-3144.

[2]Lu H，Hong Y，Yang Y，et al.Towards User-oriented RBAC Model[J].Journal of Computer Security，2015，23（1）：107-129.

[3]Lu H，Vaidya J，Atluri V.An Optimization Framework for Role Mining[J].Journal of Computer Security，2014，22（1）：1-31.

[4]Neumann G，Strembeck M.A Scenario-driven Role Engineering Process for Functional RBAC Roles[C]//Proceedings of the 7th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2002：33-42.

[5]馬晓普，李瑞轩，胡劲纬.访问控制中的角色工程[J].小型微型计算机系统，2013，34（6）：1301-1306.

[6]Vaidya J，Atluri V，Warner J.Role Miner：Mining Roles Using Subset Enumeration[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security.Alexandria：ACM press，2006：144-153.

[7]Li N，Tripunitara M V，Bizri Z.On Mutually Exclusive Roles and Separation of Duty[J].ACM Transaction on Information and System Security，2007，10（2）：42-51.