基于RBAC的角色挖掘及授权查询方法的研究

孙伟　王淑礼

摘 要： 针对现有角色挖掘结果存在冗余，以及授权管理在安全性等方面存在的问题，将角色挖掘与授权查询分别转化为布尔矩阵分解问题及部分最大可满足性问题，给出一种基于RBAC的角色挖掘及授权查询方法。应用实例结果表明：该方法挖掘的角色集更为简洁，且具有可解释性；查询搜索的角色组合能够严格保证系统的安全性，且满足授权的有效性要求。

关键词： 角色挖掘； 授权查询； 布尔矩阵分解问题； 部分最大可满足性问题

中图分类号：TP309 文献标志码：A 文章编号：1006-8228（2016）11-11-03

Research on role mining and authorization query method based on RBAC

Sun Wei， Wang Shuli

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

Abstract： Aiming at the problems of redundancy in the existing role mining results， and security in authorization management， etc.， the role mining and authorization query are transformed into the problems of Boolean matrix decomposition and partial maximal satisfiability， and a role mining and authorization query method based on RBAC（Role-Based Access Control）is proposed. The application example shows that the set of optimal roles dug by proposed method is succinct and interpretable； the role's combination of the query and search can strictly guarantee the security of the system， and meet the requirements of the validity of the authorization.

Key words： role mining； authorization querying； Boolean matrix decomposition problem； partial maximal satisfiability problem

0 引言

伴随着计算机、互联网与通信技术的高速发展与大规模应用，信息系统的安全性成为越来越突出的问题。作为保证网络与信息系统安全的一个重要环节，访问控制机制备受人们关注。基于角色的访问控制（RBAC）已成为当前企业建立安全应用的首选机制。随着大量非RBAC案例向RBAC系统的大量迁移和成功实施，设计一个完整、正确的角色集，并构建好RBAC系统对于成功实现用户与权限的逻辑分离至关重要。作为构建RBAC系统的角色挖掘技术旨在寻找一组适合的角色来精确地反映系统的功能和安全需求[1]。同时，对于构建好的RBAC系统，作为管理与维护RBAC系统的用户授权查询问题旨在寻求在单个会话中激活能覆盖用户请求权限的角色组合，以达到提高系统安全性并保证信息完整性的目的[2]。因此，在传统访问控制中如何挖掘简洁、可用且具有可解释性的角色集，辅助构建RBAC系统并寻求覆盖尽可能多权限的合适角色组合，对于角色挖掘方法及授权查询问题的研究很具挑战性，是一项热点研究课题。

1 相关研究

自顶向下方法通过对业务流程和用户场景进行专家分析而得到满足系统功能需求的角色。尽管自顶向下方法定义的角色更加符合实际需求，该方法需要大量专家的参与，耗时费力。自底向上方法从底层的用户-权限分配关系出发，采用数据挖掘技术自动、快速地构建或辅助构建RBAC系统。此方法又称角色挖掘，现已成为角色工程技术的主要研究方向[3]。对于构建好的RBAC系统，授权管理通过角色实现用户与权限的逻辑分离，这已被证明是一种灵活、方便的访问控制技术。文献[4]针对授权管理中权限查询难以计算，提出基于衍生规则和可达矩阵的两种查询方法，但不满足最小权限分配要求，且未对角色授权作进一步研究。文献[5]通过静态互斥角色约束对权限查询进行有效约束，支持灵活的角色授权。文献[6]针对云计算环境中授权管理繁重，提出最小惟一角色集及其求解方法，缩短为用户授权角色的时间。然而两文献均不满足动态互斥角色约束要求。针对现有角色挖掘结果存在冗余、缺乏可解释性，以及RBAC授权管理在安全性、有效性等方面存在的问题，本文将布尔矩阵分解问题与部分最大可满足性问题的研究相结合，提出一种基于RBAC的角色挖掘及授权查询研究方法。

2 预备知识与问题描述

沿用标准化RBAC模型的用户集U、角色集R、权限集P、用户-角色关联UA、角色-权限关联PA，不考虑角色层次和互斥约束。

定义1 布尔矩阵分解问题（BMD）[7]。如果存在A=CX，其中A，C，X均为布尔矩阵，那么称CX是A的一个布尔分解，即A可布尔分解成C与X。

Basic RMP可以看作是BMD的一个实例，即：将原始UPA分解成UA与PA，以辅助构造RBAC相关配置，同时使q（UA的列数或PA的行数）取极小值。可表示如下：

?

定义2 部分最大可满足性问题（Partial MAX-

SAT）的布尔逻辑描述[8]。

⑴ 文字：用布尔变量x1，x2，…，xi，…表示实例中的若干个体元素。对于任意xi，称xi或xi（xi的逻辑非）为文字。

⑵ 子句：由n个文字通过析取运算符（）连接成形如“x1x2…xn”的实例，称为子句c。

⑶ 真值指派：用映射函数（t：{x1，x2，…，xi，…}→

{0，1}）为子句中每一文字赋以真（用1表示）或假（用0表示）。

⑷ 合取范式：由m个子句通过合取运算符（）连接成“c1c2…cm”形式，称为Partial MAX-SAT的合取范式，用cnf（c1，c2，…，cm）表示。cnf（c1，c2，…，cm）为1，当且仅当每个ci在同一真值指派下均为1。

⑸ 严格子句：称子句c1，c2，…，cm为Partial MAX-

SAT的严格子句，是可满足的，当且仅当存在真值指派，使得cnf（c1，c2，…，cm）为1。所有严格子句的集合用HC表示。

⑹ 松弛子句：Partial MAX-SAT中不满足严格子句要求的，称为松弛子句。所有松弛子句的集合用SC表示。

3 基于RBAC的角色挖掘及授权查询

3.1 角色挖掘方法

给出基于布尔矩阵分解的角色挖掘步骤如下。

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

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

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

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

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

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

3.2 授权查询方法

授权查询是指寻求在单个会话中激活能覆盖用户请求权限的角色组合，同时遵循动态互斥角色约束并满足最小权限分配要求。动态互斥角色约束表示为dmer<{r1，r2，…，rm}，t，s>，其中1。其中s∈S，表示单个会话；Plb、Pub分别表示请求权限下界、上界，且Plb?Pub?P；match∈{min（最小匹配），max（最大匹配），exact（精确匹配）}，表示匹配类型。以下给出基于部分最大可满足性问题的授权查询方法。

步骤1 使用转换规则将静态授权逻辑和动态互斥角色约束转化为严格子句。

步骤2 采用子句更新算法将满足不同匹配的请求权限转化为松弛子句。

步骤3 利用子句编码及递归算法寻求真值指派。

4 实例分析

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

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

{p1，p2，p3}}。结果如图2所示。

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

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

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

5 结束语

本文将角色挖掘问题转化为布尔矩阵分解问题，通过创建并优化候选角色集以满足基本角色挖掘的要求，并在构建的RBAC系统中将授权查询问题转化为部分最大可满足性问题，以寻求合适的角色组合。应用实例分析表明，与快速挖掘法相比，本文挖掘的角色结果更加简洁，且查询搜索的角色组合保证了系统的安全性，体现了授权的有效性。然而，本文方法未能体现RBAC机制的角色势约束要求，存在局限性。因此，如何限制指派给用户的角色数、进一步增强挖掘结果的可解释性是下一步需要研究的问题。

参考文献（References）：

[1] 孙伟，鲁骏，李艳灵.一种面向用户的约束角色挖掘优化[J].信

阳师范学院学报：自然科学版，2014.27（4）：589-592，618

[2] ZHANG YUE，JOSHI J B D.Uaq：a framework for user

authorization query processing in RBAC extended with hybrid hierarchy and constraints[C]//Proceedings of the 13th ACM Symposium on Access Control Models and Technologies.New York：ACM Press，2008：83-92

[3] 马晓普，李瑞轩，胡劲纬.访问控制中的角色工程[J].小型微型

计算机系统，2013.34（6）：1301-1306

[4] 王婷，陈性元，任志宇.授权管理中的权限衍生计算方法[J].计

算机应用，2011，31（5）：1291-1294.

[5] 王婷，陈性元，张斌，等.基于互斥角色约束的静态职责分离策

略[J].计算机应用，2011，31（7）：1884-1886，1890

[6] 杨柳，唐卓，李仁发，等.云计算环境中基于用户访问需求的角

色查找算法[J].通信学报，2011，32（7）：169-175

[7] 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

[8] FU ZHAOHUI，MALIK S.On solving the partial MAX-SAT

problem[C]//Proceedings of the 9th International Conference on the Theory and Application of Satisfiability Testing-SAT 2006. Seattle： IEEE Press，2006：252-265