Bi-objective Optimization in Role Mining

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 \(\mathit {UPA} \subseteq U \times P\) , a role mining algorithm seeks to compute a set of roles R , a user–role authorization relation \(\mathit {UA} \subseteq U \times R\) , and a permission–role authorization relation \(\mathit {PA} \subseteq R \times 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 \(\mathit {UPA}\) and the relation defined by the composition of \(\mathit {UA}\) and \(\mathit {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 \le \bar{r}\) and \(k\le \bar{k}\) , where \(\bar{r}\) and \(\bar{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 \(\bar{r} +\bar{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.