Evaluating role mining algorithms

ABSTRACT

While many role mining algorithms have been proposed in recent years, there lacks a comprehensive study to compare these algorithms. These role mining algorithms have been evaluated when they were proposed, but the evaluations were using different datasets and evaluation criteria. In this paper, we introduce a comprehensive framework for evaluating role mining algorithms. We categorize role mining algorithms into two classes based on their outputs; Class 1 algorithms output a sequence of prioritized roles while Class 2 algorithms output complete RBAC states. We then develop techniques that enable us to compare these algorithms directly. We also introduce a new role mining algorithm and two new ways for algorithmically generating datasets for evaluation. Using synthetic as well as real datasets, we compared nine role mining algorithms. Our results illustrate the strengths and weaknesses of these algorithms.

REFERENCES

• 1: Alessandro Colantonio , Roberto Di Pietro , Alberto Ocello, A cost-driven approach to role engineering, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1364198]
• 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: Alina Ene , William Horne , Nikola Milosavljevic , Prasad Rao , Robert Schreiber , Robert E. Tarjan, Fast exact and heuristic methods for role minimization problems, Proceedings of the 13th ACM symposium on Access control models and technologies, June 11-13, 2008, Estes Park, CO, USA [doi>10.1145/1377836.1377838]
• 4: Mario Frank , David Basin , Joachim M. Buhmann, A class of probabilistic models for role engineering, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455809]
• 5: 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
• 6: Axel Kern , Andreas Schaad , Jonathan Moffett, An administration concept for the enterprise role-based access control model, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775414]
• 7: 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]
• 8: Haibing Lu , Jaideep Vaidya , Vijayalakshmi Atluri, Optimal Boolean Matrix Decomposition: Application to Role Engineering, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.297-306, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497438]
• 9: Ian Molloy , Hong Chen , Tiancheng Li , Qihua Wang , Ninghui Li , Elisa Bertino , Seraphin Calo , Jorge Lobo, Mining roles with semantic meanings, Proceedings of the 13th ACM symposium on Access control models and technologies, June 11-13, 2008, Estes Park, CO, USA [doi>10.1145/1377836.1377840]
• 10: I. Molloy, H. Chen, T. Li, Q. Wang, N. Li, E. Bertino, S. Calo, and J. Lobo. Mining roles with multiple objectives. In Review.
• 11: Gustaf Neumann , Mark Strembeck, A scenario-driven role engineering process for functional RBAC roles, Proceedings of the seventh ACM symposium on Access control models and technologies, June 03-04, 2002, Monterey, California, USA [doi>10.1145/507711.507717]
• 12: Haio Roeckle , Gerhard Schimpf , Rupert Weidinger, Process-oriented approach for role-finding to implement role-based security administration in a large industrial organization, Proceedings of the fifth ACM workshop on Role-based access control, p.103-110, July 26-28, 2000, Berlin, Germany [doi>10.1145/344287.344308]
• 13: J. H. Saltzer and M. D. Schroeder. The protection of information in computer systems. Proceedings of the IEEE, 63(9), 1975.
• 14: 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]
• 15: Dongwan Shin , Gail-Joon Ahn , Sangrae Cho , Seunghun Jin, On modeling system-centric information for role engineering, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775434]
• 16: S. D. Stoller, P. Yang, C. R. Ramakrishnan, and M. I. Gofman. Efficient policy analysis for administrative role based access control, Oct. 2007.
• 17: 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]
• 18: Jaideep Vaidya , Vijayalakshmi Atluri , Qi Guo , Nabil Adam, Migrating to optimal RBAC with minimal perturbation, Proceedings of the 13th ACM symposium on Access control models and technologies, June 11-13, 2008, Estes Park, CO, USA [doi>10.1145/1377836.1377839]
• 19: 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]
• 20: 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:
Experimentation, Management, Security

Keywords:
evaluation, rbac, role engineering, role mining