The role mining problem: Finding a minimal descriptive set of roles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

216 Scopus citations

Abstract

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 paper, 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 paper 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 paper is also to show the relation of the role mining problem 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.

Original languageEnglish (US)
Title of host publicationSACMAT'07
Subtitle of host publicationProceedings of the 12th ACM Symposium on Access Control Models and Technologies
Pages175-184
Number of pages10
DOIs
StatePublished - 2007
EventSACMAT'07: 12th ACM Symposium on Access Control Models and Technologies - Sophia Antipolis, France
Duration: Jun 20 2007Jun 22 2007

Publication series

NameProceedings of ACM Symposium on Access Control Models and Technologies, SACMAT

Other

OtherSACMAT'07: 12th ACM Symposium on Access Control Models and Technologies
CountryFrance
CitySophia Antipolis
Period6/20/076/22/07

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • RBAC
  • Role engineering
  • Role mining

Fingerprint Dive into the research topics of 'The role mining problem: Finding a minimal descriptive set of roles'. Together they form a unique fingerprint.

Cite this