Handling least privilege problem and role mining in RBAC

Hejiao Huang (), Feng Shang (), Jinling Liu () and Hongwei Du ()
Additional contact information
Hejiao Huang: Harbin Institute of Technology Shenzhen Graduate School
Feng Shang: Harbin Institute of Technology Shenzhen Graduate School
Jinling Liu: Harbin Institute of Technology Shenzhen Graduate School
Hongwei Du: Harbin Institute of Technology Shenzhen Graduate School

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 6, 63-86

Abstract: Abstract 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 $$GA_{Basic}$$ GA Basic algorithm for Basic-RMP and $$GA_{Edge}$$ GA Edge algorithm for Edge-RMP, are designed. Experiment results show that the average similarity rate between role sets produced by $$GA_{Basic}$$ GA Basic algorithm and the original ones used in generating the dataset is above 90 %. However, in the process of converting role mining into Set Cover Problem, the number of candidate role set is very large. In order to reduce the complexity of the $$GA_{Basic}$$ GA Basic algorithm, this paper presents a new polynomial-time algorithm with a performance nearly the same as that of $$GA_{Basic}$$ GA Basic algorithm.

Keywords: RBAC; Role mining; Greedy algorithm (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9633-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9633-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9633-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().