Pattern-Based Plan Construction for the Workflow Satisfiability Problem.
David A. Cohen, Jason Crampton, Gregory Gutin, Mark Jones · arXiv (Cornell University) · 2013
The workflow satisfiability problem (WSP) is a novel form of constraint satisfaction problem that arises in the context of workflow design and the enforcement of security constraints defined over such workflows. In WSP, we are given a set $S$ of tasks, a set $U$ of users, a set of constraints with variables from $S$, and, for each task $s$, a list of users authorized to perform $s$. We are to decide whether there is an assignment $\pi$ (called a plan) of tasks to authorized users such that all constraints are satisfied. We design a generic algorithm for WSP using a new approach, in which plans are grouped into equivalence classes, each class being associated with a \emph{pattern}. We demonstrate that the generic algorithm is a fixed-parameter algorithm for user-independent constraints, a family or constraints that includes many of the constraints of interest in business processing systems. The algorithm for user-independent constraints is of running time $O^*(2^{k\log k})$, where $k=|S|$, and we show that there is no algorithm of running time $O^*(2^{o(k\log k)})$ unless the Exponential Time Hypothesis fails.