{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:49Z","timestamp":1750220569015,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"crossref","award":["RPG-2018- 161"],"award-info":[{"award-number":["RPG-2018- 161"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>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).<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3450768","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T20:00:54Z","timestamp":1629403254000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis"],"prefix":"10.1145","volume":"24","author":[{"given":"Jason","family":"Crampton","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory Z.","family":"Gutin","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381991.3395616"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2133601.2133631"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205977.3205982"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04444-1_42"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750423.2750438"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9877-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2988239"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_8_1","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"#cr-split#-e_1_2_1_9_1.1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer. DOI:https:\/\/doi.org\/10.1007\/978-1-4612-0515-9 10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"#cr-split#-e_1_2_1_9_1.2","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer. DOI:https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.  R. G. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"volume-title":"Proceedings of the 11th ACM Symposium on Access Control Models and Technologies (SACMAT\u201906)","author":"Du Siqing","key":"e_1_2_1_11_1","unstructured":"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\u201906) , David F. Ferraiolo and Indrakshi Ray (Eds.). ACM, 228\u2013236. 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\u201906), David F. Ferraiolo and Indrakshi Ray (Eds.). ACM, 228\u2013236."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381991.3395600"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19955-5_17"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11339"},{"key":"e_1_2_1_16_1","article-title":"Deterministic truncation of linear matroids","volume":"14","author":"Lokshtanov Daniel","year":"2018","unstructured":"Daniel Lokshtanov , Pranabendu Misra , Fahad Panolan , and Saket Saurabh . 2018 . Deterministic truncation of linear matroids . ACM Trans. Algor. 14 , 2 (2018), 14:1\u201314:20. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. 2018. Deterministic truncation of linear matroids. ACM Trans. Algor. 14, 2 (2018), 14:1\u201314:20.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/18756891.2012.733216"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2014.10.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/286884.286900"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 4th ACM Workshop on Role-based Access Control. Association for Computing Machinery","author":"Jonathan","year":"1917","unstructured":"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\u2013160. DOI:https:\/\/doi.org\/10.1145\/3 1917 1.319186 10.1145\/319171.319186 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\u2013160. DOI:https:\/\/doi.org\/10.1145\/319171.319186"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 6th International Conference on Network and System Security (NSS\u201912)","volume":"7645","author":"Mousavi Nima","unstructured":"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\u201912) . (Lecture Notes in Computer Science), Li Xu, Elisa Bertino, and Yi Mu (Eds.) , Vol. 7645 . Springer, 516\u2013529. 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\u201912). (Lecture Notes in Computer Science), Li Xu, Elisa Bertino, and Yi Mu (Eds.), Vol. 7645. Springer, 516\u2013529."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880022.1880034"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542207.1542213"},{"volume-title":"Proceedings of the 13th ACM Symposium on Access Control Models and Technologies (SACMAT\u201908)","author":"Zhang Yue","key":"e_1_2_1_25_1","unstructured":"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\u201908) , Indrakshi Ray and Ninghui Li (Eds.). ACM, 83\u201392. DOI:https:\/\/doi.org\/10.1145\/1377836.1377850 10.1145\/1377836.1377850 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\u201908), Indrakshi Ray and Ninghui Li (Eds.). ACM, 83\u201392. DOI:https:\/\/doi.org\/10.1145\/1377836.1377850"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450768","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:42Z","timestamp":1750195722000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3450768"],"URL":"https:\/\/doi.org\/10.1145\/3450768","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"type":"print","value":"2471-2566"},{"type":"electronic","value":"2471-2574"}],"subject":[],"published":{"date-parts":[[2021,8,19]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}