Constraint Expressions and Workflow Satisfiability
This addresses the need for static analysis tools and run-time reference monitors in workflow management systems, but appears incremental as it builds on existing constraint expression concepts.
The paper tackles the problem of determining whether a workflow specification with security and business constraints can be assigned authorized users to satisfy all constraints, and develops new methods based on constraint expressions to create algorithms and analyze complexity for related problems.
A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements and business rules may impose constraints on which users are permitted to perform those steps. A workflow specification is said to be satisfiable if there exists an assignment of authorized 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 run-time reference monitors for workflow management systems. We develop new methods for determining workflow satisfiability based on the concept of constraint expressions, which were introduced recently by Khan and Fong. These methods are surprising versatile, enabling us to develop algorithms for, and determine the complexity of, a number of different problems related to workflow satisfiability.