On the workflow satisfiability problem with class-independent constraints

DOI10.4230/LIPICS.IPEC.2015.66MaRDI QIDQ5363761zbMATH OpenOpenAlexFDO

Authors

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1504.03561

zbMATH Keywords

constraint satisfaction problemfixed-parameter tractabilityuser-independent constraintsworkflow satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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 separation-of-duty, impose constraints on which subsets of users may perform certain subsets of steps. The emph{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 run-time 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 class-independent 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 fixed-parameter 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 pseudo-Boolean SAT solver) in computational experiments, which show that our algorithm significantly outperforms SAT4J for many instances of WSP. User-independent constraints, a large class of constraints including many practical ones, are a special case of class-independent constraints for which WSP was proved to be FPT (Cohen {em et al.}, J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixed-parameter tractability of WSP.

Recommendations

• Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
• Algorithms for the workflow satisfiability problem engineered for counting constraints
• Engineering algorithms for workflow satisfiability problem with user-independent constraints
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Parameterized complexity of the workflow satisfiability problem

Cited in

(9)

• On the satisfiability of authorization requirements in business process
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Engineering algorithms for workflow satisfiability problem with user-independent constraints
• Algorithms for the workflow satisfiability problem engineered for counting constraints
• Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
• Parameterized complexity of the workflow satisfiability problem
• Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints

This page was built for publication: On the workflow satisfiability problem with class-independent constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363761)