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 - when is a set of roles good? Recently, the role mining problem (RMP) has been defined as the problem of discovering an optimal set of roles from existing user permissions. Several different objectives for optimality have been proposed. However, one problem with these definitions is that often organizations already have a deployed set of roles and wish to optimize this set. Even if an optimal set of roles is discovered, if this is widely different, it is impossible to simply throw out the deployed roles and start using the new ones as this may disrupt organizational processes and separation of duty constraints that are defined on roles. Essentially, what is missing is taking role migration cost into account when defining optimality, which would allow us to come up with the best suited set of roles.
In this paper, we define a fundamentally different Role Mining Problem that takes the problem of deployed roles into account. We define the Minimal Perturbation RMP as the problem of discovering an optimal set of roles from existing user permissions that are similar to the currently deployed roles. In order to do this, we discuss the concept of similarity of roles and propose suitable definitions. Solutions also need to be parameterized to set relative weight of similarity and minimality to find the optimal set. We propose a heuristic solution based on the previously developed FastMiner algorithm that meets these requirements. We demonstrate the effectiveness of the algorithm through our experimental results.