{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T22:05:06Z","timestamp":1767650706381,"version":"3.38.0"},"reference-count":29,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2016,12,23]],"date-time":"2016-12-23T00:00:00Z","timestamp":1482451200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2017,3,16]]},"abstract":"<jats:p> A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean that a workflow is unsatisfiable, in the sense that it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a\u00a0 decision problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). <\/jats:p><jats:p> In this paper, we introduce the Bi-Objective Workflow Satisfiability Problem (BO-WSP), which enables us to solve optimization problems related to workflows and security policies. In particular, we are able to compute a \u201cleast bad\u201d plan when some components of the security policy may be violated. In general, BO-WSP is intractable from both the classical and parameterized complexity point of view (where the parameter is the number of steps). We prove that computing a Pareto front for BO-WSP is fixed-parameter tractable (FPT) if we restrict our attention to user-independent constraints. This result has important practical consequences, since most constraints of practical interest in the literature are user-independent. <\/jats:p><jats:p> Our proof is constructive and defines an algorithm, the implementation of which we describe and evaluate. We also present a second algorithm to compute a Pareto front which solves multiples instances of a related problem using mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most instances. <\/jats:p><jats:p> Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of BO-WSP. <\/jats:p>","DOI":"10.3233\/jcs-16849","type":"journal-article","created":{"date-parts":[[2016,12,24]],"date-time":"2016-12-24T01:41:08Z","timestamp":1482543668000},"page":"83-115","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":20,"title":["The bi-objective workflow satisfiability problem and workflow resiliency"],"prefix":"10.1177","volume":"25","author":[{"given":"Jason","family":"Crampton","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, UK"}]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, UK"}]},{"given":"Daniel","family":"Karapetyan","sequence":"additional","affiliation":[{"name":"University of Essex, UK"},{"name":"University of Nottingham, UK"}]},{"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, UK"}]}],"member":"179","published-online":{"date-parts":[[2016,12,23]]},"reference":[{"key":"ref001","unstructured":"American National Standards Institute, ANSI INCITS 359\u20132004 for Role Based Access Control, 2004."},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1145\/2295136.2295154"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.1989.36295"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1145\/1542207.1542239"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29963-6_11"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2007.21"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08016-1_5"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4435"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"J.Crampton, R.Crowston, G.Gutin, M.Jones and M.S.Ramanujan, Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints, in: FAW-AAIM, M.R.Fellows, X.Tan and B.Zhu, eds, Lecture Notes in Computer Science, Vol. 7924, Springer, 2013, pp. 198\u2013209.","DOI":"10.1007\/978-3-642-38756-2_21"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1145\/2462410.2462419"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1145\/2752952.2752961"},{"key":"ref012","unstructured":"J.Crampton, G.Gutin and D.Karapetyan, Source codes of the pattern branch and bound algorithm for the valued workflow satisfiability problem, Retrieved 5 April 2015. doi:10.6084\/m9.figshare.136747010.6084\/m9.figshare.1367470."},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1145\/2487222.2487226"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809088"},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1145\/990036.990062"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/31.3.283"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.11.008"},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"D.Karapetyan, A.Gagarin and G.Gutin, Pattern backtracking algorithm for the workflow satisfiability problem, in: Frontiers in Algorithmics, FAW 2015, Lecture Notes in Computer Science, Vol. 9130, Springer, 2015, pp. 138\u2013149.","DOI":"10.1007\/978-3-319-19647-3_13"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"J.C.Mace, C.Morisset and A.P.A.van Moorsel, Quantitative workflow resiliency, in: Computer Security \u2013 ESORICS 2014 \u2013 19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7\u201311, 2014. Proceedings, Part i, M.Kutylowski and J.Vaidya, eds, Lecture Notes in Computer Science, Vol. 8712, Springer, 2014, pp. 344\u2013361.","DOI":"10.1007\/978-3-319-11203-9_20"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5563-6"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1145\/1755688.1755719"},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1145\/2811269"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1145\/1133058.1133079"},{"key":"ref028","doi-asserted-by":"publisher","DOI":"10.1145\/1880022.1880034"},{"key":"ref029","unstructured":"E.W.Weisstein, Markov\u2019s inequality, From MathWorld\u2013A Wolfram Web Resource. Available at: http:\/\/mathworld.wolfram.com\/MarkovsInequality.html."}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-16849","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-16849","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-16849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T10:34:42Z","timestamp":1741689282000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-16849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,23]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,16]]}},"alternative-id":["10.3233\/JCS-16849"],"URL":"https:\/\/doi.org\/10.3233\/jcs-16849","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"type":"print","value":"0926-227X"},{"type":"electronic","value":"1875-8924"}],"subject":[],"published":{"date-parts":[[2016,12,23]]}}}