Abstract
A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirements, such as separationofduty, impose constraints on which subsets of users may perform certain subsets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies all such authorizations and constraints. An algorithm for solving WSP is important, both as a static analysis tool for workflow specifications, and for the construction of runtime reference monitors for workflow management systems. Given the computational difficulty of WSP, it is important, particularly for the second application, that such algorithms are as efficient as possible.
We introduce classindependent constraints, enabling us to model scenarios where the set of users is partitioned into groups, and the identities of the user groups are irrelevant to the satisfaction of the constraint. We prove that solving WSP is fixedparameter tractable (FPT) for this class of constraints and develop an FPT algorithm that is useful in practice. We compare the performance of the FPT algorithm with that of SAT4J (a pseudoBoolean SAT solver) in computational experiments, which show that our algorithm significantly outperforms SAT4J for many instances of WSP. Userindependent constraints, a large class of constraints including many practical ones, are a special case of classindependent constraints for which WSP was proved to be FPT (Cohen et al., J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixedparameter tractability of WSP.
BibTeX  Entry
@InProceedings{crampton_et_al:LIPIcs:2015:5572,
author = {Jason Crampton and Andrei Gagarin and Gregory Gutin and Mark Jones},
title = {{On the Workflow Satisfiability Problem with Classindependent Constraints}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {6677},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5572},
URN = {urn:nbn:de:0030drops55727},
doi = {10.4230/LIPIcs.IPEC.2015.66},
annote = {Keywords: Workflow Satisfiability Problem; Constraint Satisfaction Problem; fixedparameter tractability; userindependent constraints}
}
Keywords: 

Workflow Satisfiability Problem; Constraint Satisfaction Problem; fixedparameter tractability; userindependent constraints 
Seminar: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015) 
Issue Date: 

2015 
Date of publication: 

09.11.2015 