The generalized temporal role mining problem

Role mining, the process of deriving a set of roles from the available user-permission assignments, is considered to be an essential step in successful implementation of Role-Based Access Control (RBAC) systems. Traditional role mining techniques, however, are not equipped to handle temporal extensions of RBAC like the Temporal-RBAC (TRBAC) model. In this paper, we formally define the problem of finding a minimal set of roles from temporal user-permission assignments, such that in the resulting TRBAC system, users acquire either the same or a subset of the permissions originally assigned to them for the complete or partial durations of time as specified in the input. We show that the problem is NP-complete and propose a greedy algorithm for solving it. Our algorithm first derives a set of candidate roles from the temporal user-permission assignments and then selects the least possible number of roles from the candidate role set. The final output consists of a set of roles, a user-to-role assignment relation, a role-to-permission assignment relation and a role enabling base describing the time durations for which each role is enabled. Performance of the proposed approach has been evaluated on a number of synthetic as well as real-world datasets.