Bi-objective Optimization in Role Mining

Role mining is a technique 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. In this paper, 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. Extending 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̄. 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, (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.