Optimal Boolean Matrix Decomposition: Application to Role Engineering

@inproceedings{lu08optimal,
author = {Haibing Lu and Jaideep Vaidya and Vijayalakshmi Atluri},
title = {Optimal Boolean Matrix Decomposition: Application to Role Engineering},
booktitle = {IEEE 24th International Conference on Data Engineering},
year = {2008},
month = {April},
address = {Cancun, Mexico},
}

This paper models boolean matrix decomposition through binary integer programming. The problem is mostly described in the context of role engineering and RMP, the Role Mining Problem. The same problems are described with the addition of edge-RMP. Edge-RMP sounds like the goal of my graph optimisation, a graphing approach that minimises number of roles as well as role assignments/edges. This paper re-describes RMP, min-noise RMP, δ-approximate RMP now with edge-RMP. The contribution of the paper is the transformation of the problems into a set of equalities and inequalities models for binary integer programming. Different constraints on the models are applied to the problem to represent different variations of RMP.

Once again, the access control matrix A is described as the composition of B ⊗ C. That is, B and C is the decomposition of A. The are translated into binary integer programming models and heuristics for solving the problems are described.

Basic RMP approach: use FastMiner to identify candidate roles and create role to permission matrix based on results. Prune permission sets of users to that each permission set is unique and create access control matrix. Use constraints (to ensure no addition/remove of user/permissions) to identify user to permission assignment matrix.

Similar/slightly modified approaches are discussed for the edge-RMP and δ-approximate RMP and min-noise RMP. The approaches rely on FastMiner for producing good candidate roles.

The main contribution of the paper is theoretical representation of problem and how greedy heuristics can be used in modelled binary integer problems when candidate roles are provided. Experimental results show good run times and accuracy for their generated test sets.