Fast Exact and Heuristic Methods for Role Minimization Problems

@inproceedings{ene08fast,
author = {Alina Ene and William Horne and Mikola Milosavljevic and Prasad Rao and Robert Schreiber and Robert E. Tarjan},
title = {Fast Exact and Heuristic Methods for Role Minimization Problems},
booktitle = {SACMAT'08: Proceedings of the thirteenth ACM symposium on Access control models and technologies},
year = {2008},
month = {June},
address = {Estes Park, Colorado},
}

This paper addresses the RMP (Role Mining Problem) as a graphing problem. To minimise the number of roles while ensuring no user to permissions assignments are modified, user permission assignments are graphed and reduced. Role set solutions are then derived from the reduced graph. To address the issue of both minimising number of roles and number of edges, my graph optimisation approach was implemented, tested on their data sets and analysed. (Horrah).

The basic access control matrix is presented as an undirected bipartite graph G. Vertices are either in U (users) or P (permissions). It was noted that for a role, users and permissions assigned to the role induce a biclique in G. Since roles cover all permissions and users, the set of all roles R is a biclique cover of G. The role minimisation problem maps to finding the minimal biclique cover (MBC) of G, which is also NP-hard and known to be hard to approximate.

MBC is then reduced to minimum clique partition and chromatic number. Graph G' is created where edges in G are vertices in G'. An edge in G' is present iff endpoints of correspondence edges of G include a biclique in G. A clique in G' corresponds to a biclique in G. The clique cover number of G' corresponds to the biclique cover number of G. The biclique cover number of G is the chromatic number of G'.

Based on these proofs/reduction/mapping of problems, lower bound biclique cover algorithms are presented that can find best clique covers when each biclique is a star (equivalent to finding minimal number of roles). Rank adjacency is also used to estimate biclique cover number. When proposed iterative method for exact solutions for finding bicliques are too time consuming, greedy algorithms for finding bicliques are also proposed. Reducing the number of roles based on edge count is also used. Interesting results using the applied techniques on their data tests is then discussed. Assignment of users to groups before assignment to roles can also be done to reduce the size of the graph.

Algorithms were tested on 7 data sets, none of which seem to have RBAC implemented. Exact details of the datasets were not disclosed: number of users, number of permissions (probably for privacy reasons). Results of algorithm on the data are tabulated. One role that is found in their largest dataset is assigned to 2804 users and has 20 permissions. Four-fifths of the roles consist of a single user and all of their permissions. Heuristic approaches are quite fast and a combination of their approaches comes close to exact calculations. Bounds for heuristics are measured based on their test results.

They note that their results still have some what under defined meaning for roles semantically. What do the roles mean, why is the infrastructure good? Also in some of their data sets, the number of roles is the same as the number of users or permissions.