Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis
Article No.: 21, Pages 1 - 22
Abstract
User authorization queries in the context of role-based access control have attracted considerable interest in the past 15 years. Such queries are used to determine whether it is possible to allocate a set of roles to a user that enables the user to complete a task, in the sense that all the permissions required to complete the task are assigned to the roles in that set. Answering such a query, in general, must take into account a number of factors, including, but not limited to, the roles to which the user is assigned and constraints on the sets of roles that can be activated. Answering such a query is known to be NP-hard. The presence of multiple parameters and the need to find efficient and exact solutions to the problem suggest that a multi-variate approach will enable us to better understand the complexity of the user authorization query problem (UAQ).
In this article, we establish a number of complexity results for UAQ. Specifically, we show the problem remains hard even when quite restrictive conditions are imposed on the structure of the problem. Our fixed-parameter tractable (FPT) results show that we have to use either a parameter with potentially quite large values or quite a restricted version of UAQ. Moreover, our second FPT algorithm is complex and requires sophisticated, state-of-the-art techniques. In short, our results show that it is unlikely that all variants of UAQ that arise in practice can be solved reasonably quickly in general.
References
[1]
Alessandro Armando, Giorgia Gazzarata, and Fatih Turkmen. 2020. Benchmarking UAQ solvers. In Proceedings of the 25th ACM Symposium on Access Control Models and Technologies (SACMAT’20). ACM, 145–152.
[2]
Alessandro Armando, Silvio Ranise, Fatih Turkmen, and Bruno Crispo. 2012. Efficient run-time solving of RBAC user authorization queries: Pushing the envelope. In Proceedings of the 2nd ACM Conference on Data and Application Security and Privacy (CODASPY’12). ACM, 241–248.
[3]
Clara Bertolissi, Daniel Ricardo dos Santos, and Silvio Ranise. 2018. Solving multi-objective workflow satisfiability problems with optimization modulo theories techniques. In Proceedings of the 23rd ACM on Symposium on Access Control Models and Technologies (SACMAT’18), Elisa Bertino, Dan Lin, and Jorge Lobo (Eds.). ACM, 117–128.
[4]
Liang Chen and Jason Crampton. 2009. Set covering problems in role-based access control. In Proceedings of the 14th European Symposium on Research in Computer Security (ESORICS’09) (Lecture Notes in Computer Science), Michael Backes and Peng Ning (Eds.), Vol. 5789. Springer, 689–704.
[5]
David Cohen, Jason Crampton, Andrei Gagarin, Gregory Gutin, and Mark Jones. 2014. Iterative plan construction for the workflow satisfiability problem. J. Artif. Intell. Res. 51 (2014), 555–577.
[6]
David A. Cohen, Jason Crampton, Andrei Gagarin, Gregory Gutin, and Mark Jones. 2016. Algorithms for the workflow satisfiability problem engineered for counting constraints. J. Comb. Optim. 32, 1 (2016), 3–24.
[7]
Jason Crampton, Andrei Gagarin, Gregory Gutin, Mark Jones, and Magnus Wahlström. 2016. On the workflow satisfiability problem with class-independent constraints for hierarchical organizations. ACM Trans. Priv. Secur. 19, 3 (2016), 8:1–8:29.
[8]
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.
[9]
R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer.
[10]
R. G. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.
[11]
Siqing Du and James B. D. Joshi. 2006. Supporting authorization query and inter-domain role mapping in presence of hybrid role hierarchy. In Proceedings of the 11th ACM Symposium on Access Control Models and Technologies (SACMAT’06), David F. Ferraiolo and Indrakshi Ray (Eds.). ACM, 228–236.
[12]
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63, 4 (2016), 29:1–29:60.
[13]
Gregory Gutin and Daniel Karapetyan. 2020. Constraint branching in workflow satisfiability problem. In Proceedings of the 25th ACM on Symposium on Access Control Models and Technologies (SACMAT’20). 93–103.
[14]
Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman. 2019. Parameterized complexity of conflict-free set cover. In Proceedings of the 14th International Computer Science Symposium in Russia (CSR’19). 191–202.
[15]
Daniel Karapetyan, Andrew J. Parkes, Gregory Z. Gutin, and Andrei Gagarin. 2019. Pattern-based approach to the workflow satisfiability problem with user-independent constraints. J. Artif. Intel. Res. 66 (2019), 85–122.
[16]
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. 2018. Deterministic truncation of linear matroids. ACM Trans. Algor. 14, 2 (2018), 14:1–14:20.
[17]
Jianfeng Lu, Jianmin Han, Wei Chen, and JinWei Hu. 2012. Safety and availability checking for user authorization queries in RBAC. Int. J. Comput. Intell. Syst. 5, 5 (2012), 860–867.
[18]
Jianfeng Lu, James B. D. Joshi, Lei Jin, and Yiding Liu. 2015. Towards complexity analysis of User Authorization Query problem in RBAC. Comput. Secur. 48 (2015), 116–130.
[19]
Jonathan D. Moffett. 1998. Control principles and role hierarchies. In Proceedings of the 3rd ACM Workshop on Role-based Access Control. Association for Computing Machinery, New York, NY, 63–69.
[20]
Jonathan D. Moffett and Emil C. Lupu. 1999. The uses of role hierarchies in access control. In Proceedings of the 4th ACM Workshop on Role-based Access Control. Association for Computing Machinery, New York, NY, 153–160.
[21]
Nima Mousavi. 2014. Algorithmic Problems in Access Control. Ph.D. Dissertation. University of Waterloo.
[22]
Nima Mousavi and Mahesh V. Tripunitara. 2012. Mitigating the intractability of the user authorization query problem in role-based access control (RBAC). In Proceedings of the 6th International Conference on Network and System Security (NSS’12). (Lecture Notes in Computer Science), Li Xu, Elisa Bertino, and Yi Mu (Eds.), Vol. 7645. Springer, 516–529.
[23]
Qihua Wang and Ninghui Li. 2010. Satisfiability and resiliency in workflow authorization systems. ACM Trans. Info. Syst. Secur. 13, 4 (2010), 40.
[24]
Guneshi T. Wickramaarachchi, Wahbeh H. Qardaji, and Ninghui Li. 2009. An efficient framework for user authorization queries in RBAC systems. In Proceedings of the 14th ACM Symposium on Access Control Models and Technologies, (SACMAT’09), Barbara Carminati and James Joshi (Eds.). ACM, 23–32.
[25]
Yue Zhang and James B. D. Joshi. 2008. UAQ: A framework for user authorization query processing in RBAC extended with hybrid hierarchy and constraints. In Proceedings of the 13th ACM Symposium on Access Control Models and Technologies (SACMAT’08), Indrakshi Ray and Ninghui Li (Eds.). ACM, 83–92.
Index Terms
- Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis
Recommendations
Towards complexity analysis of User Authorization Query problem in RBAC
The User Authorization Query (UAQ) problem for RBAC is to determine whether there exists an optimum set of roles to be activated to provide a particular set of permissions requested by a user. It is a key issue related to efficiently handling users' ...
On the parameterized complexity of multiple-interval graph problems
Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more ...
Parameterized complexity dichotomy for Steiner Multicut
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2021
286 pages
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 August 2021
Accepted: 01 February 2021
Revised: 01 January 2021
Received: 01 July 2020
Published in TOPS Volume 24, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- Leverhulme Trust
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 77Total Downloads
- Downloads (Last 12 months)10
- Downloads (Last 6 weeks)2
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format