{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:27Z","timestamp":1750220187385,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,9]],"date-time":"2022-07-09T00:00:00Z","timestamp":1657324800000},"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":[[2022,11,30]]},"abstract":"<jats:p>Recent work has shown that many problems of satisfiability and resiliency in workflows may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and \u201cNo\u201d otherwise. However, in many practical settings it would be more useful to obtain a \u201cleast bad\u201d policy than just a \u201cNo,\u201d where \u201cleast bad\u201d is characterized by some numerical value indicating the extent to which the policy violates the base authorization relation and constraints. Accordingly, we introduce the Valued APEP, which returns an authorization policy of minimum weight, where the (non-negative) weight is determined by the constraints violated by the returned solution.<\/jats:p><jats:p>We then establish a number of results concerning the parameterized complexity of Valued APEP. We prove that the problem is fixed-parameter tractable (FPT) if the set of constraints satisfies two restrictions, but is intractable if only one of these restrictions holds. (Most constraints known to be of practical use satisfy both restrictions.) Our analysis is based on the novel concept of a user profile.<\/jats:p><jats:p\/><jats:p>We also introduce a new type of resiliency problem in the context of workflow satisfiability, show how it can be addressed using Valued APEP, and use this to build a set of benchmark instances for Valued APEP. We describe two different formulations of this problem using mixed integer programming and report the results of computational experiments which solve the problem using these formulations as input to a general-purpose solver. Our results show that the formulation which employs the user profile concept, has FPT-like running time and usually significantly outperforms our naive formulation of the problem.<\/jats:p>","DOI":"10.1145\/3528101","type":"journal-article","created":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T12:49:56Z","timestamp":1650545396000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Valued Authorization Policy Existence Problem: Theory and Experiments"],"prefix":"10.1145","volume":"25","author":[{"given":"Jason","family":"Crampton","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduard","family":"Eiben","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2377-0417","authenticated-orcid":false,"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Karapetyan","sequence":"additional","affiliation":[{"name":"University of Nottingham, Nottingham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2295136.2295154"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2018.2883416"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/300830.300837"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2714576.2714633"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3205977.3205982"},{"key":"e_1_3_2_7_2","series-title":"Proceedings of the International Workshop on Security and Trust Management","first-page":"140","volume":"7170","author":"Chen Liang","year":"2011","unstructured":"Liang Chen and Jason Crampton. 2011. Risk-aware role-based access control. In Proceedings of the International Workshop on Security and Trust Management(Lecture Notes in Computer Science, Vol. 7170). Springer, 140\u2013156."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4435"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.003"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450569.3463571"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2914642.2914650"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487222.2487226"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2752952.2752961"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-16849"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_2_16_2","first-page":"156","volume-title":"Proceedings of the 26th ACM Symposium on Access Control Models and Technologies","author":"Dimmock Nathan","year":"2004","unstructured":"Nathan Dimmock, Andr\u00e1s Belokosztolszki, David M. Eyers, Jean Bacon, and Ken Moody. 2004. Using trust and risk in role-based access control policies. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies. ACM, 156\u2013162."},{"issue":"3","key":"e_1_3_2_17_2","first-page":"255","article-title":"Automatically finding execution scenarios to deploy security-sensitive workflows","volume":"54","author":"Santos Daniel Ricardo dos","year":"2017","unstructured":"Daniel Ricardo dos Santos, Silvio Ranise, Luca Compagna, and Serena Elisa Ponta. 2017. Automatically finding execution scenarios to deploy security-sensitive workflows. J. Comput. Secur. 54, 3 (2017), 255\u2013282.","journal-title":"J. Comput. Secur."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292006.3300038"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766282"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04650-0"},{"key":"e_1_3_2_22_2","article-title":"Solving the workflow satisfiability problem using general purpose solvers","author":"Karapetyan Daniel","year":"2021","unstructured":"Daniel Karapetyan and Gregory Gutin. 2021. Solving the workflow satisfiability problem using general purpose solvers. arXiv:2105.03273 (2021).","journal-title":"a"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11339"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030404"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1513601.1513602"},{"key":"e_1_3_2_26_2","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41\u201372.","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11203-9_20"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629502"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-658-07365-7","volume-title":"Break-Glass\u2014Handling Exceptional Situations in Access Control","author":"Petritsch Helmut","year":"2014","unstructured":"Helmut Petritsch. 2014. Break-Glass\u2014Handling Exceptional Situations in Access Control. Springer."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1880022.1880034"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-181244"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3528101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:25Z","timestamp":1750186945000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,9]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11,30]]}},"alternative-id":["10.1145\/3528101"],"URL":"https:\/\/doi.org\/10.1145\/3528101","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"type":"print","value":"2471-2566"},{"type":"electronic","value":"2471-2574"}],"subject":[],"published":{"date-parts":[[2022,7,9]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}