On the complexity of role updating feasibility problem in RBAC. (English) Zbl 1371.68120
Summary: In Role Based Access Control (RBAC) systems, it is necessary and important to update the role-permission assignments in order to reflect the evolutions of the system transactions. However, role updating is generally complex and challenging, especially for large-scale RBAC systems. This is because the resulting state is usually expected to meet various requirements and constraints. In this paper, we focus on a fundamental problem of role updating in RBAC, which determines whether there exists a valid role-permission assignment, i.e., whether it can satisfy all the requirements of the role updating and without violating any role-capacity or permission-capacity constraint. We formally define such a problem as the Role Updating Feasibility Problem (RUFP), and study the computational complexity of RUFP in different subcases. Our results show that although several subcases are solvable in linear time, this problem is NP-complete in the general case.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | ANSI, American National Standard for Information technology-role based access control, 2004 (2004), ANSI INCITS 359-2004 |
| [2] | Joshi, J. B.D.; Bertino, E.; Ghafoor, A.; Zhang, Y., Formal foundations for hybrid hierarchies in GTRBAC, ACM Trans. Inf. Syst. Secur., 10, 4, 1-39 (2008) |
| [3] | Le, X.; Doll, T.; Barbosu, M., An enhancement of the role-based access control model to facilitate information access management in context of team collaboration and workflow, J. Biomed. Inform., 45, 6, 1084-1107 (2012) |
| [4] | Zhang, Y.; Joshi, J. B.D., Uaq: a framework for user authorization query processing in RBAC extended with hybrid hierarchy and constraints, (Proc. 13th ACM Symposium on Access Control Models and Technologies. Proc. 13th ACM Symposium on Access Control Models and Technologies, New York, NY, USA (2008)), 83-92 |
| [5] | Guneshi, T.; Wahbeh, H. Q.; Li, Ninghui, An efficient framework for user authorization queries in RBAC systems, (Proc. 14th ACM Symposium on Access Control Models and Technologies. Proc. 14th ACM Symposium on Access Control Models and Technologies, Stresa, Italy (2009)), 23-32 |
| [6] | Armando, A.; Ranise, S.; Turkmen, F.; Crispo, B., Efficient run-time solving of RBAC user authorization queries: pushing the envelope, (Proc. ACM Conference on Data and Application Security and Privacy. Proc. ACM Conference on Data and Application Security and Privacy, San Antonio, Texas, USA (2012)), 241-248 |
| [7] | Hu, J.; Zhang, Y.; Li, R.; Lu, Z., Role updating for assignments, (Proc. 15th ACM Symposium on Access Control Models and Technologies. Proc. 15th ACM Symposium on Access Control Models and Technologies, Pittsburgh, Pennsylvania, USA (2010)), 89-98 |
| [8] | Hu, J.; Zhang, Y.; Li, R., Towards automatic update of access control policy, (Proc. The 24th USENIX Large Installation System Administration Conference. Proc. The 24th USENIX Large Installation System Administration Conference, San Jose, CA, USA (2010)), 59-74 |
| [9] | Bauer, L.; Garriss, S.; Reiter, M. K., Detecting and resolving policy misconfigurations in access-control systems, (Proc. 13th A CM Symposium on Access Control Models and Technologies. Proc. 13th A CM Symposium on Access Control Models and Technologies, Estes Park, Colorado, USA (2008)), 185-194 |
| [10] | Sohr, K.; Drouineaud, M.; Ahn, G.-J.; Gogolla, M., Analyzing and managing role-based access control policies, IEEE Trans. Knowl. Data Eng., 20, 7, 924-939 (2008) |
| [11] | Stoller, S. D.; Yang, P.; Ramakrishnan, C.; Gofman, M. I., Efficient policy analysis for administrative role based access control, (Proc. 14th ACM Conference on Computer and Communications Security. Proc. 14th ACM Conference on Computer and Communications Security, Alexandria, Virginia, USA (2007)), 445-455 |
| [12] | Li, N.; Tripunitara, M. V., Security analysis in role-based access control, ACM Trans. Inf. Syst. Secur., 9, 4, 391-420 (2006) |
| [13] | Sandhu, R.; Bhamidipati, V.; Munawer, Q., The ARBAC97 model for role-based administration of roles, ACM Trans. Inf. Syst. Secur., 2, 1, 105-135 (February 1999) |
| [14] | Sun, Y.; Wang, Q.; Li, N., On the complexity of authorization in RBAC under qualification and security constraints, IEEE Trans. Dependable Secure Comput., 8, 6, 883-897 (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
