王静宇 吴晓晖

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

0 引 言

自底向上的角色工程(Role Engineering)[1]，也被称为角色挖掘(Role Mining)，它是通过数据挖掘的方法对访问控制系统现存数据中的用户-权限之间关系的进行分析，然后自底向上挖掘出可以安全管理系统的角色。这种方法可以半自动化或自动化地实现角色的提取和优化。目前大数据及复杂的信息系统中提取和优化角色是一个热点研究问题[2]。

在属性角色挖掘算法上，传统的数据挖掘技术存在一些不足之处，它在挖掘过程中常常会挖掘出大量冗余的属性角色信息，造成了属性角色和权限管理复杂性的增加。而属性角色挖掘算法的目标就是找出一组最小角色集合能够安全有效地实现系统中用户权限的分配、删除和更新等管理，因此如何高效地找到满足最小权限原则的最小属性角色集合成为角色挖掘的一个重要研究内容。目前角色挖掘方面的算法和研究成果已有很多[3-8]，都是NP完全的。20世纪80年代，德国的Wille教授提出形式概念分析[9](Formal Concept Analysis,FCA),它的核心数据结构就是概念格。概念格作为一种工具，由于其具有的一些特点在角色挖掘方面有很大的优势[10]，这方面已有一些重要研究[11-15]。文献[16]在基于概念格的RBAC模型基础上，给出了概念格模型上最小角色集、角色约简、角色替代的定义及相关定理的证明。为了降低时间复杂度，还提出了一种贪婪算法寻找最小角色集。

本文利用概念格的RBAC模型，引入概念格分层的性质，将概念格分层的性质与角色约简等定理相结合，提出一种逐层查找最小角色集的优化算法，避免贪婪算法带来的重复性计算，进一步提高查找最小角色集算法的时间性能，降低算法的时间复杂度。……