The role mining problem: A formal perspective
The role mining problem: A formal perspective
复制标题
DOI：
10.1145/1805974.1805983
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Jaideep Vaidya;V. Atluri;Qi Guo
中科院分区：
文献类型：
--
作者：
Jaideep Vaidya;V. Atluri;Qi Guo
设计一套完整、正确的角色集是实现基于角色的访问控制的最重要和最具挑战性的任务之一。与此相关的一个关键问题是善良/有趣的概念什么时候一个角色是好的/有趣的？在本文中，我们将角色挖掘问题（RMP）定义为从现有用户权限中发现最佳角色集的问题。本文的主要贡献是形式化地定义了RMP，并分析了其理论界限。除了上述基本RMP之外，我们还介绍了两种不同的RMP变体，称为Δ-近似RMP和最小噪声RMP，它们具有实用意义。我们把已知的“集合基问题”归结为RMP，证明了RMP是一个NP完全问题。本文的一个重要贡献也是显示的关系的RMP已经确定的几个问题，在数据挖掘和数据分析文献。通过证明RMP在本质上可以简化为这些已知的问题，我们可以直接借用现有的实现解决方案，并指导这一方向的进一步研究。我们还基于之前提出的FastMiner算法开发了一个启发式解决方案，该算法非常准确且高效。
Devising a complete and correct set of roles has been recognized as one of the most important and challenging tasks in implementing role-based access control. A key problem related to this is the notion of goodness/interestingness—when is a role good/interesting? In this article, we define the Role Mining Problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions. The main contribution of this article is to formally define RMP and analyze its theoretical bounds. In addition to the above basic RMP, we introduce two different variations of the RMP, called the Δ-Approx RMP and the minimal-noise RMP that have pragmatic implications. We reduce the known “Set Basis Problem” to RMP to show that RMP is an NP-complete problem. An important contribution of this article is also to show the relation of the RMP to several problems already identified in the data mining and data analysis literature. By showing that the RMP is in essence reducible to these known problems, we can directly borrow the existing implementation solutions and guide further research in this direction. We also develop a heuristic solution based on the previously proposed FastMiner algorithm, which is very accurate and efficient.