Fast exact and heuristic methods for role minimization problems

ABSTRACT

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.

REFERENCES

• 1: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 2: D. Cornaz and J. Fonlupt. Chromatic characterization of biclique covers. Discrete Mathematics, 306(5):495--507, 2006.
• 3: Edward J. Coyne, Role engineering, Proceedings of the first ACM Workshop on Role-based access control, p.4-es, November 30-December 02, 1995, Gaithersburg, Maryland, United States [doi>10.1145/270152.270159]
• 4: Alina Ene. Biclique Covers of Bipartite Graphs: The Minimum Biclique Cover and Edge Concentration Problems. 2007. Princeton University.
• 5: M.P. Gallagher, A. O'Connor, and B. Kropp. The economic impact of role-based access control. Technical Report Planning Report 02-1, National Institute of Standards and Technology, March 2002.
• 6: Floris Geerts, Bart Goethals, and Taneli Mielikäinen. Tiling databases. In Discovery Science, volume 3245 of Lecture Notes in Computer Science, pages 278--289. Springer-Verlag, 2004.
• 7: John E. Hopcroft and Richard M. Karp. An n^5<over>2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225--231, 1973.
• 8: Martin Kuhlmann , Dalia Shohat , Gerhard Schimpf, Role mining - revealing business roles for security administration using data mining technology, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775435]
• 9: V. S. Anil Kumar , H. Ramesh, Covering Rectilinear Polygons with Axis-Parallel Rectangles, SIAM Journal on Computing, v.32 n.6, p.1509-1541, 2003 [doi>10.1137/S0097539799358835]
• 10: Xuemin Lin, On the computational complexity of edge concentration, Discrete Applied Mathematics, v.101 n.1-3, p.197-205, April 15, 2000 [doi>10.1016/S0166-218X(99)00207-3]
• 11: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 12: A. Mehrotra and M.A. Trick. A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4):344--354, 1996.
• 13: H. Muller. Alternating cycle-free matchings. Order, 7(1):11--21, 1990.
• 14: J.B. Orlin. Contentment in graph theory: covering graphs with cliques. Indagationes Mathematicae, 39:406--424, 1977.
• 15: René Peeters, The maximum edge biclique problem is NP-complete, Discrete Applied Mathematics, v.131 n.3, p.651-654, 28 September 2003 [doi>10.1016/S0166-218X(03)00333-0]
• 16: R. Rymon. Method and apparatus for role grouping by shared resource utilization. U.S. Patent Application 20030172161, September 2003.
• 17: Jürgen Schlegelmilch , Ulrike Steffens, Role mining with ORCA, Proceedings of the tenth ACM symposium on Access control models and technologies, June 01-03, 2005, Stockholm, Sweden [doi>10.1145/1063979.1064008]
• 18: Daluss J. Siewert. Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of f0; 1g matrices. PhD thesis, The University of Colorado at Denver, 2000.
• 19: H.U. Simon. On approximate solutions for combinatorial optimization problems. SIAM J. Disc. Math., 3(2):294--310, 1990.
• 20: U.S. Department of Veteran's Affairs. Licensed Providers Permission Table. http://www.va.gov/rbac/docs/20050120PermissionTablesLicensedProviders.doc.
• 21: Jaideep Vaidya , Vijayalakshmi Atluri , Qi Guo, The role mining problem: finding a minimal descriptive set of roles, Proceedings of the 12th ACM symposium on Access control models and technologies, June 20-22, 2007, Sophia Antipolis, France [doi>10.1145/1266840.1266870]
• 22: Jaideep Vaidya , Vijayalakshmi Atluri , Janice Warner, RoleMiner: mining roles using subset enumeration, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180424]
• 23: Dana Zhang , Kotagiri Ramamohanarao , Tim Ebringer, Role engineering using graph optimisation, Proceedings of the 12th ACM symposium on Access control models and technologies, June 20-22, 2007, Sophia Antipolis, France [doi>10.1145/1266840.1266862]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Security

Keywords:
role mining, role-based access control