基于加权结构复杂度的角色挖掘评价
2016-12-22孙伟鲁骏
孙伟++鲁骏
摘 要：现有自底向上的角色工程方法构建过程较繁杂，工程造价高昂。探讨几种角色挖掘算法的基本思想及其优缺点。以这些角色挖掘算法为评价对象，以加权结构复杂度为评价标准，在真实数据集上对构建的RBAC系统状态进行测试与评价。实验结果验证了几种算法的优越性。
关键词关键词：角色工程；角色挖掘；评价标准；加权结构复杂度
DOIDOI：10.11907/rjdk.161824
中图分类号：TP301
文献标识码：A 文章编号文章编号：16727800（2016）011002503
0 引言
基于角色的访问控制（RBAC）通过角色实现了用户与权限的逻辑分离，是当前主流的访问控制机制之一[1]。作为构建与维护RBAC系统的角色工程技术要求设计合适的角色集，并为其指派权限集与用户集，以精确反映系统功能和安全需求。Kuhlmann等[2]利用数据挖掘技术从
原始系统配置中提取角色，用于构建RBAC系统。此方法又称角色挖掘，因其具有自动、快速的特点而备受关注[3]。为充分体现RBAC系统管理方便、操作简单的特点，首先需要定义一个完整、正确的角色集。然而，现有利用矩阵分解法、子集枚举法、图优化法、概率模型法、最小干扰法等构建RBAC系统代价高昂。本文以现有7种不同的角色挖掘方法为研究对象，结合加权结构复杂度，对其构建的系统进行多方位评价。
1 相关研究
现有角色挖掘方法按输出结果可分为两类：第一类仅输出挖掘角色集，不考虑角色层次关系，这类算法包括Complete Miner（CM）[4]、Fast Miner（FM）[4]；第二类输出构建的系统状态，允许存在角色层次，这类算法包括ORCA[5]、Graph Optimization（GO）[6]、HP Role Minimization（HPRM）[7]、HP Edge Minimization（HPEM）[7]、Hierarchical Miner（HM）[8]。7种角色挖掘算法基本思想如下：
1.1 Complete Miner（CM）
将分配给用户的不同权限集视为初始角色，对任意两个不同的初始角色作交集运算，产生新角色，将其添进初始角色集，并在此角色集中作交运算以寻找新角色。重复上述过程直至不再产生新角色。该算法运用集合论的枚举法，穷举权限集合的所有可能，时间复杂度为O（2|InitRoles|），其中|InitRoles|为初始角色的个数。
1.2 Fast Miner（FM）
按照分配给用户的不同权限集形成初始角色集，并将得到的角色集作交集运算以产生新的角色集。FM和CM 的不同之处在于 FM 新产生的角色不再参与交集运算，时间复杂度降为O（|InitRoles|2）。其中|InitRoles|为初始角色的个数。
1.3 ORCA
基于数据挖掘的聚类算法思想，首先设定每个权限对应一个角色，也就是一个簇，其次选择两个簇进行合并。重复上述过程直至剩下一个簇或者簇的数目满足用户要求。ORCA 最终得到的凝聚层次树可以在某一层进行分割，得到的状态即为ORCA 的一个角色状态。
1.4 Graph Optimization（GO）
将分配给每个用户的权限集作为初始角色，给出优化目标函数，按目标函数对初始角色集进行优化。GO算法分为以下4种情况：①两个角色的权限集相同，删除一个角色并将该角色的用户集添加到另外一个角色的用户集中；②两个角色的权限集相交，形成一新角色，其权限集是两个相交角色的共有权限组合，其用户集是两个角色的用户之和，并在原角色和新角色之间添加一条角色层次线；③两个角色中其中一角色的权限集包含另一个角色的权限集，在包含到被包含角色之间添加一条角色层次线；④两个角色的权限集之间没有任何关系，不进行任何操作。
1.5 HP Role Minimization（HPRM）
首先选择一用户，查看其它用户是否包含当前用户的所有权限，并将得到的用户集合和当前用户的权限集合并成一角色；其次，从用户-权限分配关系中删除相应用户的当前权限集；最后，进行下一次迭代，直至用户-权限分配关系被挖掘角色集完全覆盖。
1.6 HP Edge Minimization（HPEM）
首先利用HPRM算法挖掘候选角色集，然后执行类似GO算法目标函数对候选角色集进行优化，直至候选角色集不能被进一步优化。
1.7 Hierarchical Miner（HM）
首先，利用形式概念得出初始形式概念格；其次，处理继承中的包含关系以简化概念格形式；再次，在存在复合角色的情况下，若删除复合角色后的目标函数值比删除前的目标函数值小，则需要删除复合角色；最后，重复删除复合角色直至目标函数值不再减少。
以上几种算法的优缺点比较如表1所示。
2 基于加权结构复杂度的角色挖掘评价
在角色工程领域将RBAC系统的构建成本记为加权结构复杂度。定义给出加权结构复杂度，并以此为标准，对角色挖掘构建的RBAC系统状态进行评价。
2.1 加权结构复杂度
定义1：原始系统配置ρ。转换RBAC前的原始配置ρ
是一个三元组
定义2：构造系统状态γ。转换RBAC后的系统状态γ是一个四元组
定义3：加权结构复杂度（Weighted Structural Complexity，WSC）[8]。给定系统状态γ及四元组W=
wsc（γ，W）= wr×|R|+wu×|UA|+wp×|PA|+wh×|RH|
WSC考虑了系统配置的所有关系，并为不同关系设置了不同的权重。
2.2 评价方法
角色挖掘评价描述如下：
步骤1：执行上述几种算法，输出相应的系统状态γ。
步骤2：以加权结构复杂度为评价标准，设置不同的W，并计算wsc（γ，W）。
步骤3：对构建系统效果进行评价。
3 实验与结果分析
实验选用文献[9]的数据集进行测试与评价，实验前相关数据如表2所示。
3.1 实验设置及测试环境
分别设置W=<1，0，0，0>、W=<0，1，1，1>。上述几种不同算法进行测试，评价系统状态的加权结构复杂度。
相关测试环境：奔腾双核E5400CPU 2.70GHz，2GB内存，160GB硬盘，Window XP操作系统；在Java中实现算法，并使用角色挖掘器Rminer。
3.2 结果分析
表3、表4分别给出了不同W下系统状态的评价值。可以看出，后三种算法（HPRM，HPEM，HM）构建系统效果明显优于其它算法。
4 结语
本文以现有7种不同的角色挖掘研究方法为评价对象，结合预置的加权结构复杂度，在真实数据集上对构建系统进行综合评价。实验结果表明，HPRM、HPEM、HM三种算法构建系统效果明显优于其它算法，对于角色工程实践具有一定理论参考价值。
参考文献：
[1] 孙伟，李艳灵，周文勇.细粒度基于传递功能的约束委托模型[J].信阳师范学院学报：自然科学版，2013，26（3）：442445.
[2] KUHLMANN M，SHOHAT D，SCHIMPF G.Role miningrevealing business roles for security administration using data mining technology[C].Proceedings of the 8th ACM Symposium on Access Control Models and Technologies.Como：ACM Press，2003：179186.
[3] 孙伟，鲁骏，李艳灵.一种面向用户的约束角色挖掘优化[J].信阳师范学院学报：自然科学版，2014，27（4）：589592，618.
[4] VAIDYA J，ATLURI V，WARNER J.RoleMiner：mining roles using subset enumeration[C].Proc. of the 13th ACM Conference on Computer and Communications Security.Alexandria：ACM press，2006：144153.
[5] SCHLEGELMILCH J，STEFFENS U.Role mining with ORCA[C].Proceedings of the 10th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2005：168176.
[6] ZHANG DANA，RAMAMOHANARAO K，EBRINGERT.Role engineering using graph optimisation[C].Proc. of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis：ACM Press，2007：139144.
[7] ENE A，HORNE W，MILOSAVLJEVIC N，et al.Fast exact and heuristic methods for role minimization problems[C].Proc. of the 13th ACM Symposium on Access Control Models and Technologies.Estes Park：ACM Press，2008：110.
[8] MOLLOY I，CHEN H，LI T C，et al.Mining roles with semantic meanings[C].Proceedings of the 13th ACM Symposium on Access Control Models and Technologies.Estes Park：ACM Press，2008：2130.
[9] MOLLOY I，LI NINGHUI，LI TIANCHENG，et al.Evaluating role mining algorithms[C].Proceedings of the 14th ACM Symposium on Access Control Models and Technologies.Stresa：ACM Press，2009：95104.
（责任编辑：陈福时）
