The role hierarchy mining problem: Discovery of optimal role hierarchies

Role hierarchies are fundamental to the role based access control (RBAC) model. The notion of role hierarchy is a well understood concept that allows senior roles to inherit the permissions of the corresponding junior roles. Role hierarchies further ease the burden of security administration, as there is no need to explicitly specify and maintain a large number of permissions. Given a set of roles or user permissions, one may construct a number of alternative hierarchies. However, there does not exist the notion of an optimal role hierarchy. Optimality helps in maximizing the benefit of employing the role hierarchy. In this paper, we propose such a formal metric. Our optimality notion is based on the smallest graph representation of the role hierarchy (minimal in the number of edges) having the same transitive closure as any alternate representation. We show why this makes sense as well as ways to achieve this. The main contributions of this paper are to formalize the notion of optimality for role hierarchy construction, along with proposing heuristic solutions to achieve this objective, thus making role hierarchies feasible and practical.