Abstract
Role Based Access Control (RBAC) is a very popular access control model, for a long time investigated and widely deployed in the security architecture of different enterprises. To implement RBAC, roles have to be firstly identified within the considered organization. Usually the process of (automatically) defining the roles in a bottom up way, starting from the permissions assigned to each user, is called role mining. In literature, the role mining problem has been formally analyzed and several techniques have been proposed in order to obtain a set of valid roles.
Recently, the problem of defining different kind of constraints on the number and the size of the roles included in the resulting role set has been addressed. In this paper we provide a formal definition of the role mining problem under the cardinality constraint, i.e. restricting the maximum number of permissions that can be included in a role. We discuss formally the computational complexity of the problem and propose a novel heuristic. Furthermore we present experimental results obtained after the application of the proposed heuristic on both real and synthetic datasets, and compare the resulting performance to previous proposals.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blundo, C., Cimato, S.: A simple role mining algorithm. In: Proceedings of the 2010 ACM Symposium on Applied Computing, SAC 2010, pp. 1958–1962. ACM, New York (2010), http://doi.acm.org/10.1145/1774088.1774503
Blundo, C., Cimato, S.: Constrained role mining. arXiv:1203.3744v1 [cs.CR] (2012)
Chen, L., Crampton, J.: Set covering problems in role-based access control. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 689–704. Springer, Heidelberg (2009)
Coyne, E.J.: Role engineering. In: ACM Workshop on Role-Based Access Control (1995)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics 162 (2004, 2005)
Ene, A., Horne, W., Milosavljevic, N., Rao, P., Schreiber, R., Tarjan, R.E.: Fast exact and heuristic methods for role minimization problems. In: Proc. of the 13th ACM Symposium on Access Control Models and Technologies, pp. 1–10. ACM (2008)
Ferraiolo, D.F., Sandhu, R.S., Gavrila, S.I., Kuhn, D.R., Chandramouli, R.: Proposed NIST standard for role-based access control. ACM Transaction on Information System Security 4(3), 224–274 (2001)
Frank, M., Basin, D.A., Buhmann, J.M.: A class of probabilistic models for role engineering. In: ACM Conference on Computer and Communications Security, pp. 299–310. ACM (2008)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP- Completeness. W.H. Freeman and Company (1979)
Hingankar, M., Sural, S.: Towards role mining with restricted user-role assignment. In: 2nd International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace Electronic Systems Technology (Wireless VITAE), pp. 1–5 (February 28, 2011- March 3, 2011)
John, J., Sural, S., Atluri, V., Vaidya, J.: Role mining under role-usage cardinality constraint. In: Proc. of the 12th IFIP Conference on Security, pp. 705–716 (2012)
Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
Kuhlmann, M., Shohat, D., Schimpf, G.: Role mining - revealing business roles for security administration using data mining technology. In: Proc. of the 8th ACM Symposium on Access Control Models and Technologies, pp. 179–186. ACM, New York (2003), http://doi.acm.org/10.1145/775412.775435
Kumar, R., Sural, S., Gupta, A.: Mining rbac roles under cardinality constraint. In: Jha, S., Mathuria, A. (eds.) ICISS 2010. LNCS, vol. 6503, pp. 171–185. Springer, Heidelberg (2010), http://portal.acm.org/citation.cfm?id=1940366.1940383
Li, N., Tripunitara, M.V., Bizri, Z.: On mutually exclusive roles and separation-of-duty. ACM Trans. Inf. Syst. Secur. 10 (May 2007), http://doi.acm.org/10.1145/1237500.1237501
Ma, X., Li, R., Lu, Z., Wang, W.: Mining constraints in role-based access control. Mathematical and Computer Modelling (2011), http://linkinghub.elsevier.com/retrieve/pii/S0895717711000719
Molloy, I., Chen, H., Li, T., Wang, Q., Li, N., Bertino, E., Calo, S., Lobo, J.: Mining roles with semantic meanings. In: Proc. of the 13th ACM Symposium on Access Control Models and Technologies, pp. 21–30. ACM (2008)
Molloy, I., Li, N., Li, T., Mao, Z., Wang, Q., Lobo, J.: Evaluating role mining algorithms. In: SACMAT 2009, pp. 95–104 (2009)
Roeckle, H., Schimpf, G., Weidinger, R.: Process-oriented approach for role-finding to implement role-based security administration in a large industrial organization. In: Proceedings of the Fifth ACM Workshop on Role-Based Access Control, RBAC 2000, pp. 103–110. ACM (2000), http://doi.acm.org/10.1145/344287.344308
Sandhu, R.S., Coyne, E.J., Feinstein, H.L., Youman, C.E.: Role-based access control models. Computer 29, 38–47 (1996)
Schreiber, R.: Datasets used for role mining experiments, http://www.hpl.hp.com/personal/Robert_Schreiber/
Scilab Consortium. Scilab: The Free Software for Numerical Computation (Ver 530 (for Mac OS X 1067)), http://www.scilab.org/
Stockmeyer, L.J.: The minimal set basis problem is NP-complete. Tech. Rep. RC 5431, IBM Research (May 1975)
Vaidya, J., Atluri, V., Guo, Q.: The role mining problem: finding a minimal descriptive set of roles. In: Proc. of the 12th ACM Symposium on Access Control Models and Technologies, pp. 175–184. ACM (2007)
Vaidya, J., Atluri, V., Guo, Q.: The role mining problem: A formal perspective. ACM Trans. Inf. Syst. Secur. 13(3) (2010)
Vaidya, J., Atluri, V., Warner, J.: Roleminer: mining roles using subset enumeration. In: CCS 2006, pp. 144–153. ACM (2006)
Zhang, D., Ramamohanarao, K., Ebringer, T.: Role engineering using graph optimisation. In: Proc. of the 12th ACM Symposium on Access Control Models and Technologies, pp. 139–144. ACM (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blundo, C., Cimato, S. (2013). Constrained Role Mining. In: Jøsang, A., Samarati, P., Petrocchi, M. (eds) Security and Trust Management. STM 2012. Lecture Notes in Computer Science, vol 7783. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38004-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-38004-4_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38003-7
Online ISBN: 978-3-642-38004-4
eBook Packages: Computer ScienceComputer Science (R0)