Optimal Boolean Matrix Decomposition: Application to Role Engineering
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 297-306
Abstract
A decomposition of a binary matrix into two matrices gives a set of basis vectors and their appropriate combination to form the original matrix. Such decomposition solutions are useful in a number of application domains including text mining, role engineering as well as knowledge discovery. While a binary matrix can be decomposed in several ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions optimizing different criteria matching various semantics. In this paper, we first present a number of variants to the optimal Boolean matrix decomposition problem that have pragmatic implications. We then present a unified framework for modeling the optimal binary matrix decomposition and its variants using binary integer programming. Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for binary integer programming. Although the proposed solutions are applicable to any domain of interest, for providing more meaningful discussions and results, in this paper, we present the binary matrix decomposition problem in a role engineering context, whose goal is to discover an optimal and correct set of roles from existing permissions, referred to as the role mining problem (RMP). This problem has gained significant interest in recent years as role based access control has become a popular means of enforcing security in databases. We consider several variants of the above basic RMP, including the min-noise RMP, delta-approximate RMP and edge-RMP. Solutions to each of them aid security administrators in specific scenarios. We then model these variants as Boolean matrix decomposition and present efficient heuristics to solve them.Keywords
This publication has 12 references indexed in Scilit:
- The Discrete Basis ProblemIEEE Transactions on Knowledge and Data Engineering, 2008
- The role mining problem2007
- Role engineering using graph optimisation2007
- Tiling Databases2004
- Role mining - revealing business roles for security administration using data mining technology2003
- Observations on the role life-cycle in the context of enterprise security management2002
- Proposed NIST standard for role-based access controlACM Transactions on Information and System Security, 2001
- The role-based access control system of a European bank2001
- The specification and enforcement of authorization constraints in workflow management systemsACM Transactions on Information and System Security, 1999
- Role-based access control modelsComputer, 1996