The Role Mining Problem: Finding a Minimal Descriptive Set of Roles

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, the authors 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.