Dr. William Horne,
Secure Systems Lab, HP Labs, Princeton, NJ

Monday, September 29, 2:00PM
Babbio 221, Stevens Institute of Technology

Abstract:
We describe several new bottom-up approaches to problems in roleengineering 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 (a role is viewed as a collection of permissions) that can be used to implement a pre-existing user-to-permission relation. We introduce fast graph reductions that allow recovery of the optimum solution from the solution to a problem on a smaller input graph. These reductions either completely solve the problems on which we have tried them, or reduce the problem enough that we then find the the optimum solution with an exponential (in the worst case) method. We introduce lower bounds that are sharp for seven of nine test cases and are within 3% on the other two. We introduce and test a new approximation method that on average yields 2% more roles than the optimum, but is faster than our reduction method. 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 a way to use a solution to the role minimization problem in order to implement a system in which users are assigned to groups of users (possibly overlapping, so a user may be part of several groups), which are granted roles, which confer permissions.

This paper appeared at SACMAT'08.

Biograph
Dr. Horne is a Research Manager in the Secure Systems Lab of HP Labs. He currently manages several research projects involving systems and network security and risk analytics. His research interests include systems security, cryptography, privacy, and tamper-resistant software. Prior to joining HP in 2002, he held research positions at InterTrust's STAR Lab and NEC Research Institute.