Abstract: Role Based Access Control (RBAC) is accepted as the de facto access control model for organizations of all sizes. However, engineering the right set of roles is crucial to enable the correct deployment of RBAC within an organization. Indeed, discovering an optimal and correct set of roles from existing permission assignments, referred to as the role mining problem (RMP), has gained significant attention in recent years. Role Mining is itself an instantiation of Boolean matrix decomposition – wherein a Boolean matrix is decomposed into two Boolean matrices giving a set of basis vectors and their appropriate combination. In fact, such decompositions are useful in a number of application domains beyond role engineering, including text mining as well as knowledge discovery. While a Boolean matrix can be decomposed in many ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions that are optimal with respect to different criteria that may match various semantics. In this paper, we first present a number of variants of the optimal Boolean matrix decomposition problem, including usage RMP, basic RMP, δ-approximate RMP, and edge RMP, that have pragmatic implications in the context of role mining. We then present a unified framework for modeling the optimal Boolean matrix decomposition and its variants using integer linear programming (ILP). Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for integer linear programming. We also develop efficient heuristics and solutions for each RMP variant, and validate them by a comprehensive experimental evaluation.
Keywords: Role based access control, role mining, Boolean matrix decomposition, integer linear programming
