{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T21:46:15Z","timestamp":1767649575376,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications and for the construction of runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.<\/jats:p>","DOI":"10.1145\/2487222.2487226","type":"journal-article","created":{"date-parts":[[2013,6,18]],"date-time":"2013-06-18T12:36:08Z","timestamp":1371558968000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem"],"prefix":"10.1145","volume":"16","author":[{"given":"Jason","family":"Crampton","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London"}]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London"}]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[{"name":"University of Johannesburg"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"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":"publisher","DOI":"10.1007\/978-3-642-03748-1_7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2011.14"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2295136.2295154"},{"volume-title":"Secure computer systems: Unified exposition and multics interpretation. Tech. rep. MTR-2997","author":"Bell D.","key":"e_1_2_1_5_1","unstructured":"Bell , D. and LaPadula , L. 1976. Secure computer systems: Unified exposition and multics interpretation. Tech. rep. MTR-2997 , Mitre Corporation , Bedford, MA . Bell, D. and LaPadula, L. 1976. Secure computer systems: Unified exposition and multics interpretation. Tech. rep. MTR-2997, Mitre Corporation, Bedford, MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/300830.300837"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/501978.501979"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201911)","volume":"9","author":"Bodlaender H. L.","unstructured":"Bodlaender , H. L. , Jansen , B. M. P. , and Kratsch , S . 2011a. Cross-composition: A new technique for kernelization lower bounds . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201911) . T. Schwentick and C. Durr Eds., LIPIcs Series , vol. 9 , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 165--176. Bodlaender, H. L., Jansen, B. M. P., and Kratsch, S. 2011a. Cross-composition: A new technique for kernelization lower bounds. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201911). T. Schwentick and C. Durr Eds., LIPIcs Series, vol. 9, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 165--176."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"volume-title":"Proceedings of the IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214","author":"Brewer D. F. C.","key":"e_1_2_1_12_1","unstructured":"Brewer , D. F. C. and Nash , M. J . 1989. The chinese wall security policy . In Proceedings of the IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214 . Brewer, D. F. C. and Nash, M. J. 1989. The chinese wall security policy. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1063979.1063986"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462410.2462419"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382287"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_16"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity . Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283482"},{"key":"e_1_2_1_20_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory . Springer."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSAC.2008.26"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1237500.1237501"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/319171.319186"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.485845"},{"volume-title":"Proceedings of the 10th Computer Security Foundations Workshop (CSFW\u201997)","author":"Simon R. T.","key":"e_1_2_1_28_1","unstructured":"Simon , R. T. and Zurko , M. E . 1997. Separation of duty in role-based environments . In Proceedings of the 10th Computer Security Foundations Workshop (CSFW\u201997) . IEEE Computer Society, 183--194. Simon, R. T. and Zurko, M. E. 1997. Separation of duty in role-based environments. In Proceedings of the 10th Computer Security Foundations Workshop (CSFW\u201997). IEEE Computer Society, 183--194."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.009"},{"volume-title":"Foundations of Constraint Satisfaction","author":"Tsang E. P. K.","key":"e_1_2_1_30_1","unstructured":"Tsang , E. P. K. 1993. Foundations of Constraint Satisfaction . Academic Press . Tsang, E. P. K. 1993. Foundations of Constraint Satisfaction. Academic Press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022883727209"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880022.1880034"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2487222.2487226","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2487222.2487226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:39Z","timestamp":1750236519000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2487222.2487226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2487222.2487226"],"URL":"https:\/\/doi.org\/10.1145\/2487222.2487226","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}