  Workflows specify collections of tasks that must be executed under the
responsibility or supervision of human users. Workflow management systems and
workflow-driven applications need to enforce security policies in the form of
access control, specifying which users can execute which tasks, and
authorization constraints, such as Separation of Duty, further restricting the
execution of tasks at run-time. Enforcing these policies is crucial to avoid
frauds and malicious use, but it may lead to situations where a workflow
instance cannot be completed without the violation of the policy. The Workflow
Satisfiability Problem (WSP) asks whether there exists an assignment of users
to tasks in a workflow such that every task is executed and the policy is not
violated. The WSP is inherently hard, but solutions to this problem have a
practical application in reconciling business compliance and business
continuity. Solutions to related problems, such as workflow resiliency (i.e.,
whether a workflow instance is still satisfiable even in the absence of users),
are important to help in policy design. Several variations of the WSP and
similar problems have been defined in the literature and there are many
solution methods available. In this paper, we survey the work done on these
problems in the past 20 years.
