Approximation Algorithms for Minimizing the Number of Roles and Administrative Assignments in RBAC

In role based access control (RBAC), minimizing the descriptive set of roles (specified as Basic-RMP) and minimizing the administrative assignments for roles (specified as Edge-RMP) can greatly decrease the management costs. Both role mining problems are proved to be NP-hard. In this work, we convert Basic-RMP to set cover problem and Edge-RMP to weighted set cover problem. Hence, many well-known methods for solving the Set Cover Problems can be applied to solve these role mining problems. According to the conversion process and the greedy idea for solving set cover problems, two algorithms respectively named GA_Basic algorithm for Basic-RMP and GA_Edge algorithm for Edge-RMP, are given in this paper. Experiment results show that the average similarity rate between role sets produced by GA_Basic algorithm and the original ones is above 90%. However, in the process of converting role mining into Set Cover Problem, the number of candidate role set was exponential. In order to reduce the complexity of the GA_Basic algorithm, this paper presents a new polynomial-time algorithm with a performance nearly the same as that of GA_Basic algorithm.