Article ID: | iaor201526107 |
Volume: | 30 |
Issue: | 1 |
Start Page Number: | 63 |
End Page Number: | 86 |
Publication Date: | Jul 2015 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Du Hongwei, Huang Hejiao, Shang Feng, Liu Jinling |
Keywords: | security |
For a given role‐based access control (RBAC) configuration, user‐role assignment satisfying least privilege principle (specified as LPUAP) is one of the most important problems to be solved in information security. LPUAP has been proved to be NP‐hard. This paper gives several efficient greedy algorithms for handling this problem. Experiment results show that the output of our algorithms is almost optimal while the running time is greatly reduced. In another case where a RBAC configuration is to be set up, 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 (i.e., Basic‐RMP and Edge‐RMP) have also been proved to be NP‐hard. This paper converts Basic‐RMP to set cover problem and Edge‐RMP to weighted set cover problem, and two algorithms respectively named