Bi-objective Optimization in Role Mining

Crampton, Jason; Eiben, Eduard; Gutin, Gregory; Karapetyan, Daniel; Majumdar, Diptapriyo

Abstract

Role mining is a technique that is used to derive a role-based authorization policy from an existing policy. Given a set of users U, a set of permissions P, and a user–permission authorization relation UPA⊆U×P, a role mining algorithm seeks to compute a set of roles R, a user–role authorization relation UA⊆U×R, and a permission–role authorization relation PA⊆R×P, such that the composition of UA and PA is close (in some appropriate sense) to UPA. Role mining is therefore a core problem in the specification of role-based authorization policies. Role mining is known to be hard in general and exact solutions are often impossible to obtain, so there exists an extensive literature on variants of the role mining problem that seek to find approximate solutions and algorithms that use heuristics to find reasonable solutions efficiently.

In this article, we first introduce the Generalized Noise Role Mining problem (GNRM)—a generalization of the MinNoise Role Mining problem—which we believe has considerable practical relevance. In particular, GNRM can produce “security-aware” or “availability-aware” solutions. Extending the work of Fomin et al., we show that GNRM is fixed parameter tractable, with parameter r+k, where r is the number of roles in the solution and k is the number of discrepancies between UPA and the relation defined by the composition of UA and PA. We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both r and k subject to upper bounds r≤r¯ and k≤k¯, where r¯ and k¯ are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter r¯+k¯. From a practical perspective, a solution to BO-GNRM gives security managers the opportunity to identify a mined policy offering the best tradeoff between the number of policy discrepancies and the number of roles.

We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a) we obtained strong support that Gurobi’s performance is fixed-parameter tractable, and (b) our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies. We observed that, in many cases, our solver is capable of obtaining optimal solutions when the values of either k or r are small.

Citation

Crampton, J., Eiben, E., Gutin, G., Karapetyan, D., & Majumdar, D. (2024). Bi-objective Optimization in Role Mining. ACM Transactions on Privacy and Security, 28(1), Article 5. https://doi.org/10.1145/3697833

• Journal Article Type: Article
• Acceptance Date: Sep 13, 2024
• Online Publication Date: Oct 14, 2024
• Publication Date: Nov 9, 2024
• Deposit Date: Mar 12, 2025
• Publicly Available Date: Mar 19, 2025
• Journal: ACM Transactions on Privacy and Security
• Print ISSN: 2471-2566
• Electronic ISSN: 2471-2574
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 28
• Issue: 1
• Article Number: 5
• DOI: https://doi.org/10.1145/3697833
• Public URL: https://nottingham-repository.worktribe.com/output/40705724
• Publisher URL: https://dl.acm.org/doi/10.1145/3697833
• Additional Information: Received: 2024-03-20; Accepted: 2024-09-13; Published: 2024-10-14
• Other Repo URL: https://arxiv.org/abs/2403.16757