The role mining problem: finding a minimal descriptive set of roles

ABSTRACT

Devising a complete and correct set of roles has been recognized as one of the most important and challenging tasks in implementing role based access control. A key problem related to this is the notion of goodness/interestingness -- when is a role good/interesting? In this paper, we define the role mining problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions. The main contribution of this paper is to formally define RMP, and analyze its theoretical bounds. In addition to the above basic RMP, we introduce two different variations of the RMP, called the δ-approx RMP and the Minimal Noise RMP that have pragmatic implications. We reduce the known "set basis problem" to RMP to show that RMP is an NP-complete problem. An important contribution of this paper is also to show the relation of the role mining problem to several problems already identified in the data mining and data analysis literature. By showing that the RMP is in essence reducible to these known problems, we can directly borrow the existing implementation solutions and guide further research in this direction.

REFERENCES

• 1: C. Damm, K. H. Kim, and F. Roush. On covering and rank problems for boolean matrices and their applications. In Computing and Combinatorics: 5th Annual International Conference, COCOON '99,volume 1627 of Lecture Notes in Computer Science, pages 123--133. Springer-Verlag, 1999.
• 2: 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]
• 3: David F. Ferraiolo , Ravi Sandhu , Serban Gavrila , D. Richard Kuhn , Ramaswamy Chandramouli, Proposed NIST standard for role-based access control, ACM Transactions on Information and System Security (TISSEC), v.4 n.3, p.224-274, August 2001 [doi>10.1145/501978.501980]
• 4: M. P. Gallagher, A. O'Connor, and B. Kropp. The economic impact of role-based access control. Planning report 02-1, National Institute of Standards and Technology, March 2002.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: F. Geerts, B. Goethals, and T. Mielikainen. Tiling databases. In Discovery Science, Lecture Notes in Computer Science, pages 278--289. Springer-Verlag, 2004.
• 7: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 8: Dorit S. Hochbaum, Approximating clique and biclique problems, Journal of Algorithms, v.29 n.1, p.174-200, Oct. 1998 [doi>10.1006/jagm.1998.0964]
• 9: Axel Kern , Martin Kuhlmann , Andreas Schaad , Jonathan Moffett, Observations on the role life-cycle in the context of enterprise security management, Proceedings of the seventh ACM symposium on Access control models and technologies, June 03-04, 2002, Monterey, California, USA [doi>10.1145/507711.507718]
• 10: 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]
• 11: G. Markowsky. Ordering d-classes and computing schein rank is hard. Semi-group Forum, 44:373--375, 1992.
• 12: T. Mielikäinen. Intersecting data to closed sets with constraints. In B. Goethals and M. J. Zaki, editors, FIMI, volume 90 of CEUR Workshop Proceedings. CEUR-WS.org, 2003.
• 13: P. Miettinen. The discrete basis problem, master's thesis. Master's thesis, University of Helsinki, 2006.
• 14: P. Miettinen, T. Mielikainen, A. Gionis, G. Das, and H. Mannila. The discrete basis problem. In Knowledge Discovery in Databases: PKDD 2006, Lecture Notes in Artificial Intelligence, pages 335--346, 2006.
• 15: N. Mishra, D. Ron, and R. Swaminathan. On finding large conjunctive clusters. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, volume 2777 of Lecture Notes in Computer Science, pages 448--462. Springer, 2003.
• 16: Feng Pan , Gao Cong , Anthony K. H. Tung , Jiong Yang , Mohammed J. Zaki, Carpenter: finding closed patterns in long biological datasets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956832]
• 17: 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]
• 18: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 19: Andreas Schaad , Jonathan Moffett , Jeremy Jacob, The role-based access control system of a European bank: a case study and discussion, Proceedings of the sixth ACM symposium on Access control models and technologies, p.3-9, May 2001, Chantilly, Virginia, United States [doi>10.1145/373256.373257]
• 20: 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]
• 21: 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]

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:
RBAC, role engineering, role mining