Constrained Role Mining

Role Based Access Control (RBAC) is a very popular access control model, for long time investigated and widely deployed in the se- curity architecture of different enterprises. To implement RBAC, roles have to be firstly identified within the considered organization. Usually the process of (automatically) defining the roles in a bottom up way, starting from the permissions assigned to each user, is called role min- ing. In literature, role mining have been formally analyzed and several techniques have been proposed in order to return a set of valid roles. Recently, the problem of defining different kind of constraints on the number and the size of the roles included in the resulting role set has been addressed. In this paper we provide a formal definition of the role mining problem under the cardinality constraint, i.e. restricting the max- imum number of permissions that can be included in a role. We discuss formally the computational complexity of the problem and propose a novel heuristic, returning a role set satisfying the cardinality constraint. Furthermore we present experimental results obtained after the applica- tion of the proposed heuristic on both real and synthetic datasets, and compare its performance with respect to previous proposals in literature.