{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:39:10Z","timestamp":1756384750823,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,10,22]],"date-time":"2016-10-22T00:00:00Z","timestamp":1477094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/K005162\/1"],"award-info":[{"award-number":["EP\/K005162\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Royal Society Wolfson Research Merit Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2016,12,12]]},"abstract":"<jats:p>\n            A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The\n            <jats:italic>workflow satisfiability problem<\/jats:italic>\n            (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP.\n          <\/jats:p>\n          <jats:p>In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.<\/jats:p>","DOI":"10.1145\/2988239","type":"journal-article","created":{"date-parts":[[2016,10,25]],"date-time":"2016-10-25T12:37:00Z","timestamp":1477399020000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations"],"prefix":"10.1145","volume":"19","author":[{"given":"Jason","family":"Crampton","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}]},{"given":"Andrei","family":"Gagarin","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}]},{"given":"Mark","family":"Jones","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}]}],"member":"320","published-online":{"date-parts":[[2016,10,22]]},"reference":[{"volume-title":"ANSI INCITS 359-2004 for Role Based Access Control","author":"American National Standards Institute. 2004.","key":"e_1_2_1_1_1","unstructured":"American National Standards Institute. 2004. ANSI INCITS 359-2004 for Role Based Access Control . American National Standards Institute . American National Standards Institute. 2004. ANSI INCITS 359-2004 for Role Based Access Control. American National Standards Institute."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Thomas Bartz-Beielstein Marco Chiarandini Lus Paquete and Mike Preuss (Eds.). 2010. Experimental Methods for the Analysis of Optimization Algorithms. Springer.   Thomas Bartz-Beielstein Marco Chiarandini Lus Paquete and Mike Preuss (Eds.). 2010. Experimental Methods for the Analysis of Optimization Algorithms. Springer.","DOI":"10.1007\/978-3-642-02538-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-140500"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/300830.300837"},{"volume-title":"IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214","author":"D. F.","key":"e_1_2_1_5_1","unstructured":"D. F. C. Brewer and Michael J. Nash. 1989. The Chinese wall security policy . In IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214 . D. F. C. Brewer and Michael J. Nash. 1989. The Chinese wall security policy. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750423.2750438"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9877-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1063979.1063986"},{"key":"e_1_2_1_9_1","volume-title":"10th International Symposium on Parameterized and Exact Computation (IPEC\u201915)","volume":"43","author":"Crampton Jason","year":"2015","unstructured":"Jason Crampton , Andrei Gagarin , Gregory Gutin , and Mark Jones . 2015 . On the workflow satisfiability problem with class-independent constraints . In 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915) (Leibniz International Proceedings in Informatics (LIPIcs)), Thore Husfeldt and Iyad Kanj (Eds.) , Vol. 43 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 66--77. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.IPEC.2015.66 10.4230\/LIPIcs.IPEC.2015.66 Jason Crampton, Andrei Gagarin, Gregory Gutin, and Mark Jones. 2015. On the workflow satisfiability problem with class-independent constraints. In 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915) (Leibniz International Proceedings in Informatics (LIPIcs)), Thore Husfeldt and Iyad Kanj (Eds.), Vol. 43. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 66--77. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.IPEC.2015.66"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462410.2462419"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487222.2487226"},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_12_1","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer Verlag . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer Verlag."},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Gagarin Andrei","year":"2015","unstructured":"Andrei Gagarin , Jason Crampton , Gregory Gutin , Mark Jones , and Magnus Wahlstr\u00f6m . 2015 . The pattern-backtracking FPT algorithm and experimental data set for the WSP with class-independent constraints. (2015). Figshare. http:\/\/dx.doi.org\/10.6084\/m9.figshare.1603424 . Retrieved November 16, 2015. 10.6084\/m9.figshare.1603424 Andrei Gagarin, Jason Crampton, Gregory Gutin, Mark Jones, and Magnus Wahlstr\u00f6m. 2015. The pattern-backtracking FPT algorithm and experimental data set for the WSP with class-independent constraints. (2015). Figshare. http:\/\/dx.doi.org\/10.6084\/m9.figshare.1603424. Retrieved November 16, 2015."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.11.008"},{"volume-title":"Frontiers in Algorithmics 2015 (Lecture Notes in Computer Science).","author":"Karapetyan Daniel","key":"e_1_2_1_15_1","unstructured":"Daniel Karapetyan , Andrei Gagarin , and Gregory Gutin . 2015. Pattern backtracking algorithm for the workflow satisfiability problem . In Frontiers in Algorithmics 2015 (Lecture Notes in Computer Science). Vol. 9130 . Springer , 138--149. Daniel Karapetyan, Andrei Gagarin, and Gregory Gutin. 2015. Pattern backtracking algorithm for the workflow satisfiability problem. In Frontiers in Algorithmics 2015 (Lecture Notes in Computer Science). Vol. 9130. Springer, 138--149."},{"key":"e_1_2_1_16_1","volume-title":"Kreher","author":"Kocay William","year":"2004","unstructured":"William Kocay and Donald L . Kreher . 2004 . Graphs, Algorithms , and Optimization. Chapman 8 Hall\/CRC Press . William Kocay and Donald L. Kreher. 2004. Graphs, Algorithms, and Optimization. Chapman 8 Hall\/CRC Press."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/373256.373257"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880022.1880034"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2013.31"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2988239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2988239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:40:07Z","timestamp":1750218007000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2988239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,22]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,12,12]]}},"alternative-id":["10.1145\/2988239"],"URL":"https:\/\/doi.org\/10.1145\/2988239","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"type":"print","value":"2471-2566"},{"type":"electronic","value":"2471-2574"}],"subject":[],"published":{"date-parts":[[2016,10,22]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}