TY - GEN

T1 - Fast exact and heuristic methods for role minimization problems

AU - Ene, Alina

AU - Rao, Prasad

AU - Horne, William

AU - Schreiber, Robert

AU - Milosavljevic, Nikola

AU - Tarjan, Robert E.

PY - 2008

Y1 - 2008

N2 - We describe several new bottom-up approaches to problems in role engineering for Role-Based Access Control (RBAC). The salient problems are all NP-complete, even to approximate, yet we find that in instances that arise in practice these problems can be solved in minutes. We first consider role minimization, the process of finding a smallest collection of roles that can be used to implement a pre-existing user-to-permission relation. We introduce fast graph reductions that allow recovery of the solution from the solution to a problem on a smaller input graph. For our test cases, these reductions either solve the problem, or reduce the problem enough that we find the optimum solution with a (worst-case) exponential method. We introduce lower bounds that are sharp for seven of nine test cases and are within 3.4% on the other two. We introduce and test a new polynomial-time approximation that on average yields 2% more roles than the optimum. We next consider the related problem of minimizing the number of connections between roles and users or permissions, and we develop effective heuristic methods for this problem as well. Finally, we propose methods for several related problems.

AB - We describe several new bottom-up approaches to problems in role engineering for Role-Based Access Control (RBAC). The salient problems are all NP-complete, even to approximate, yet we find that in instances that arise in practice these problems can be solved in minutes. We first consider role minimization, the process of finding a smallest collection of roles that can be used to implement a pre-existing user-to-permission relation. We introduce fast graph reductions that allow recovery of the solution from the solution to a problem on a smaller input graph. For our test cases, these reductions either solve the problem, or reduce the problem enough that we find the optimum solution with a (worst-case) exponential method. We introduce lower bounds that are sharp for seven of nine test cases and are within 3.4% on the other two. We introduce and test a new polynomial-time approximation that on average yields 2% more roles than the optimum. We next consider the related problem of minimizing the number of connections between roles and users or permissions, and we develop effective heuristic methods for this problem as well. Finally, we propose methods for several related problems.

KW - Role mining

KW - Role-based access control

UR - http://www.scopus.com/inward/record.url?scp=57349100404&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57349100404&partnerID=8YFLogxK

U2 - 10.1145/1377836.1377838

DO - 10.1145/1377836.1377838

M3 - Conference contribution

AN - SCOPUS:57349100404

SN - 9781605581293

T3 - Proceedings of ACM Symposium on Access Control Models and Technologies, SACMAT

SP - 1

EP - 10

BT - SACMAT'08 - Proceedings of the 13th ACM Symposium on Access Control Models and Technologies

T2 - 13th ACM Symposium on Access Control Models and Technologies, SACMAT'08

Y2 - 11 June 2008 through 13 June 2008

ER -