基于布尔矩阵分解的角色极小化挖掘方法

摘要：现有自底向上的角色工程方法挖掘结果存在冗余、缺乏可解释性。为优化角色结果，结合基本角色挖掘问题及布尔矩阵分解问题的研究，提出一种基于布尔矩阵分解的角色极小化挖掘方法。该方法使用快速挖掘法创建候选角色集，采用贪心算法进一步优化候选角色集。应用实例结果表明，该方法挖掘的极小角色集更加简洁，且具有可解释性。

关键词：角色工程；角色挖掘；基本角色挖掘问题；布尔矩阵分解

中图分类号：TP309 文献标识码：A 文章编号：1009-3044（2016）19-0215-03

Mining Minimal Role Set Based on Boolean Matrix Decomposition

SUN Wei， LU Jun

（School of Computer & Informatiion Technology， Xinyang Normal University， Xinyang 464000， China）

Abstract： Results of role mining lack interpretability and are very redundant in existing approaches to bottom-up role engineering.In order to discover optimal roles，this paper researches basic role mining problem and boolean matrix decomposition problem，a method of mining minimal role set is proposed.Candidate role set is generated by using fast miner，and the greedy algorithm is applied to optimize the roles.Results of the application example show that，the set of optimal roles is succinct and interpretable.

Key words： role engineering；role mining；basic role mining problem；boolean matrix decomposition

基于角色的访问控制（RBAC）系统具有操作简单、可扩展性强、管理代价低等优点[1]，RBAC是大规模企业等组织建立系统应用的首选机制。从企业组织的功能需求出发，构建能准确反映其功能特征的RBAC系统关键在于设计合适的角色集。为此，研究者们相继提出了角色工程技术以及自顶向下与自底向上两种基本方法[2，3]。自顶向下方法通过对业务流程和用户场景进行专家分析而得到满足系统功能需求的角色。尽管自顶向下方法定义的角色更加符合实际需求，该方法需要大量专家的参与，耗时费力。与自顶向下的人工处理方式相比，自底向上方法从底层的用户-权限分配关系出发，采用数据挖掘技术自动、快速地构建或辅助构建RBAC系统。此方法又称角色挖掘，现已成为角色工程技术的主要研究方向[4]。

1 相关研究

角色挖掘研究方法主要有以下几类：（1）将用户-权限分配关系的布尔矩阵转化为用户-角色指派与角色-权限指派两个布尔矩阵，以挖掘合适的角色集；（2）RBAC系统的角色实际上是不同权限组合成的角色集合。将分配给用户的初始权限集作为角色，并通过集合交操作可得到新角色；（3）角色看作图的顶点，顶点所包含的元素表示权限，角色间的层次关系看作图的边，基于图论思想进行角色挖掘；（4）将分配给不同用户的权限集进行聚类，基于数据挖掘的聚类思想挖掘角色。Vaidya等[5]对基本的角色挖掘问题进行了系统的阐述和定义，分析了问题的理论边界，给出了δ-近似和最小噪声两种方法，并指出该问题是NP-难问题。在此基础上，Vaidya等又提出了边角色挖掘问题及其求解方法，进一步减轻管理员在角色分配和权限定义方面的负担。Lu等[6]提出了一个角色数最小化问题的统一建模框架。Ene等[7]提出了把最小角色数的求解转化为最小biclique覆盖问题，以寻找最小角色集。Zhang等[8]使用矩阵分解法获取角色层次图，再利用图优化技术以寻找合适的角色集。角色挖掘目标是寻找满足用户-权限分配关系的最小角色集合。然而，在实际系统的构建与维护过程中，以上方法挖掘出的冗余角色将增加系统管理负担，并存在安全隐患。针对该问题，本文将角色挖掘问题转化为布尔矩阵分解问题，提出一种角色极小化挖掘方法，能够实现基本角色挖掘目标。

2 预备知识与问题描述

2.1 角色工程元素

定义1 角色工程元素。沿用标准化RBAC模型的用户集U、角色集R、权限集P、用户-角色关联UA、角色-权限关联PA，不考虑角色层次和互斥约束。ass_perms（r）、ass_roles（u）分别表示在RBAC系统中指派给角色r的权限集和指派给用户u的角色集；ass_perms（u）表示在非RBAC系统中直接指派给用户u的权限集。可形式化表示如下：

2.2 基本角色挖掘问题

定义2 基本角色挖掘问题（Basic RMP）[5]。对于给定非RBAC系统中的用户集U’，权限集P’以及用户-权限分配关系UPA’，寻找角色集R’，用户-角色指派关系UA’及角色-权限指派关系PA’，以辅助构建RBAC系统，满足指派给任意用户的角色集恰好覆盖该用户的所有权限，同时挖掘的角色数|R’|应尽可能少。可形式化表示为：

2.3 布尔矩阵表示法

定义3 布尔矩阵相乘[8]。给定n行k列布尔矩阵C、k行m列布尔矩阵X、n行m列布尔矩阵A，其中用“”表示布尔乘操作符，C与X相乘的结果为A，表示为CX=A。

若cil、xlj、aij分别表示C、X、A中的单元元素，则布尔矩阵相乘运算应满足：

一个布尔矩阵可以表示成两个布尔矩阵的乘积，乘积中前一个矩阵表示概念集，后一个矩阵表示如何将目标数据用概念集合并的形式表示。

（2） A=CXAT=（CX）T AT=X TC T，即将分解前后的矩阵同时转置，分解式仍成立。

2.4 Basic RMP的布尔矩阵表示

对于包含n个用户、m个权限、q个角色的RBAC系统，用户-角色指派关系可以表示成一个二维布尔矩阵，用UA简化表示，其中矩阵单元值UA[i][k]表示用户是否拥有角色；角色-权限指派关系也用矩阵PA简化表示，PA[k][j]表示角色是否拥有权限；而非RBAC系统的用户-权限直接指派关系也可以表示为矩阵UPA，UPA[i][j]表示用户是否拥有权限，形式化表示如下：

3 基于布尔矩阵分解的角色极小化挖掘

角色极小化挖掘方法的基本思想：首先，基于聚类思想并使用快速挖掘法（Fast Miner）创建候选角色集；其次，基于布尔矩阵分解思想，采用贪心算法将候选角色指派给不同用户，并不断优化候选角色集，以满足Basic RMP的挖掘要求。以下给出角色极小化挖掘方法的算法描述。

算法1 候选角色集的创建

步骤1 将拥有相同权限集的用户群聚成一类。分别选取同一聚类的一个用户，并暂时去除该聚类的其他冗余用户，以降低挖掘规模。

步骤2 基于Fast Miner，将分配给用户的不同权限集作为整体视为角色，确立初始角色集。

步骤3 采用集合论的枚举法，通过二重循环将任意两初始角色做交集，创建新角色，并构造候选角色集。

算法2 候选角色集的优化

步骤1 结合Fast Miner的挖掘结果，将挖掘问题转化为布尔矩阵分解形式：UPA=UAPA。

步骤2 对于UPA中任意值为0的单元，确定UA中相应位置值为0的单元。

步骤3 根据布尔矩阵乘运算法则，将步骤1得到的分解式进行转置操作，并等价表示成A=CX，其中A表示直接权限指派的列向量矩阵，C表示算法1中候选角色集的列向量矩阵，X表示待确定用户指派的列向量矩阵。

步骤4 根据进一步确定X中相应单元的值（当X的某一行全为0时，去除对应的候选角色）。反复执行该步骤，直至候选角色集达到极小化。

4 实例分析与比较

为了验证本文方法的有效性，选用构造的数据集实例进行分析，并与Fast Miner挖掘结果进行比较。图1给出了一个由6个用户、3个权限构成的原始数据集UPA。

首先，通过调用算法1能够压缩数据集空间，降低了挖掘规模，并得到候选角色集：{{p2}，{p1，p2}，{p2，p3}，{p1，p2，p3}}。结果如图2所示。

其次，调用算法2。通过步骤1、步骤2，可以得到初始分解形式，并根据UPA中值为0的单元，改进初始分解方案如下：

步骤3通过对上述分解式进行整体转置，得到形如A=CX的列向量矩阵等价分解形式：

根据步骤4的分析可知，X中x21=x32=x43=1，其余单元可取值0或1。然而，由于C4=C2C3，将x23，x33取值为1而将x43修改为0，既能保证挖掘的角色覆盖所有权限，又使挖掘的角色结果{r2，r3}达到极小化。因此，与挖掘出{r1，r2，r3，r4}的Fast Miner方法相比，本文方案更优化，挖掘结果更简洁。

5 结束语

本文提出的角色极小化挖掘方法将角色挖掘问题转化为布尔矩阵分解问题，通过创建并优化候选角色集，能够满足基本角色挖掘的要求。实例分析表明，与快速挖掘法相比，该方法挖掘的角色结果更加简洁，对于角色工程实践具有一定的理论参考价值。然而，本文方法未能体现RBAC机制的角色势约束要求，存在局限性。因此，如何限制指派给用户的角色数、进一步增强挖掘结果的可解释性是下一步需要研究的问题。

参考文献：

[1] 孙伟，李艳灵，周文勇.细粒度基于传递功能的约束委托模型[J].信阳师范学院学报：自然科学版，2013，26（3）：442-445.

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

[3] 孙伟，鲁骏，李艳灵.一种面向用户的约束角色挖掘优化[J].信阳师范学院学报：自然科学版，2014，27（4）：589-592，618.

[4] Molloy I，Li Ning-hui，Li Tian-cheng，et al.Evaluating role mining algorithms[C]//Proceedings of the 14th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2009：95-104.

[5] Vaidya J，Atluri V，Guo Qi.The role mining problem：finding a minimal description set of roles[C]//Proceedings of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis：ACM Press，2007：175-184.

[6] Lu Hai-bing，Vaidya J，Atluri V.Optimal boolean matrix decomposition：application to role engineering[C]//Proceedings of the 24th International Conference on Data Engineering.Cancun：IEEE press， 2008：297-306.

[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：1-10.

[8] Zhang Dana，Ramamohanarao K，Ebringer T.Role engineering using graph optimisation[C]//Proc. of the 12th ACM Symposium on Access Control Models and Technologies.Sophia Antipolis：ACM Press，2007：139-144.