A Survey on Workflow Satisfiability, Resiliency, and Related Problems
---
paper_title: Secure workflow deployment in multi-organizational environments

paper_content:

A centrifugal separator has a centrifuge rotor and a casing, the casing forming an outer space for the rotor. The rotor is rotatable around a rotary axis and within the casing. The rotor includes a rotor wall, which defines an outer periphery of the rotor and encloses an inner space, an inlet, which extends through the rotor wall and permits feeding of a product to the inner space, and a number of outlets, which extend through the rotor wall and are arranged to permit intermittent discharge of a separated product from the inner space to the outer space. The outlets are distributed around the periphery of the rotor. The number of outlets is uneven, and a valve member extends around the rotor wall to define a space between the wall and the valve member at the level of the outlets.
---
paper_title: Model checking of security-sensitive business processes

paper_content:

Security-sensitive business processes are business processes that must comply with security requirements (e.g. authorization constraints). In previous works it has been shown that model checking can be profitably used for the automatic analysis of security-sensitive business processes. But building a formal model that simultaneously accounts for both the workflow and the access control policy is a time consuming and error-prone activity. In this paper we present a new approach to model checking security-sensitive business processes that allows for the separate specification of the workflow and of the associated security policy while retaining the ability to carry out a fully automatic analysis of the process. To illustrate the effectiveness of the approach we describe its application to a version of the Loan Origination Process featuring an RBAC access control policy extended with delegation.
---
paper_title: A systematic review on security in Process-Aware Information Systems - Constitution, challenges, and future directions

paper_content:

Display Omitted HighlightsSecurity in PAIS constitutes an interdisciplinary research area.Security is a multifaceted subject that covers technical and human aspects in PAIS.12 security controls are identified for Process-Aware Information Systems (PAIS).Security controls have centered on preventive countermeasures so far.Reaction, detection, and human orientation constitute promising research directions. ContextSecurity in Process-Aware Information Systems (PAIS) has gained increased attention in current research and practice. However, a common understanding and agreement on security is still missing. In addition, the proliferation of literature makes it cumbersome to overlook and determine state of the art and further to identify research challenges and gaps. In summary, a comprehensive and systematic overview of state of the art in research and practice in the area of security in PAIS is missing. ObjectiveThis paper investigates research on security in PAIS and aims at establishing a common understanding of terminology in this context. Further it investigates which security controls are currently applied in PAIS. MethodA systematic literature review is conducted in order to classify and define security and security controls in PAIS. From initially 424 papers, we selected in total 275 publications that related to security and PAIS between 1993 and 2012. Furthermore, we analyzed and categorized the papers using a systematic mapping approach which resulted into 5 categories and 12 security controls. ResultsIn literature, security in PAIS often centers on specific (security) aspects such as security policies, security requirements, authorization and access control mechanisms, or inter-organizational scenarios. In addition, we identified 12 security controls in the area of security concepts, authorization and access control, applications, verification, and failure handling in PAIS. Based on the results, open research challenges and gaps are identified and discussed with respect to possible solutions. ConclusionThis survey provides a comprehensive review of current security practice in PAIS and shows that security in PAIS is a challenging interdisciplinary research field that assembles research methods and principles from security and PAIS. We show that state of the art provides a rich set of methods such as access control models but still several open research challenges remain.
---
paper_title: Workflow data patterns: Identification, representation and tool support

paper_content:

Workflow systems seek to provide an implementation vehicle for complex, recurring business processes. Notwithstanding this common objective, there are a variety of distinct features offered by commercial workflow management systems. These differences result in significant variations in the ability of distinct tools to represent and implement the plethora of requirements that may arise in contemporary business processes. Many of these requirements recur quite frequently during the requirements analysis activity for workflow systems and abstractions of these requirements serve as a useful means of identifying the key components of workflow languages. In this paper, we describe a series of workflow data patterns that aim to capture the various ways in which data is represented and utilised in workflows. By delineating these patterns in a form that is independent of specific workflow technologies and modelling languages, we are able to provide a comprehensive treatment of the workflow data perspective and we subsequently use these patterns as the basis for a detailed comparison of a number of commercially available workflow management systems, workflow standards and web-service composition languages.
---
paper_title: Workflow Resource Patterns: Identification, Representation and Tool Support

paper_content:

In the main, the attention of workflow researchers and workflow developers has focussed on the process perspective, i.e., control-flow. As a result, issues associated with the resource perspective, i.e., the people and machines actually doing the work, have been largely neglected. Although the process perspective is of most significance, appropriate consideration of the resource perspective is essential for successful implementation of workflow technology. Previous work has identified recurring, generic constructs in the control-flow and data perspectives, and presented them in the form of control-flow and data patterns. The next logical step is to describe workflow resource patterns that capture the various ways in which resources are represented and utilised in workflows. These patterns include a number of distinct groupings such as push patterns (“the system pushes work to a worker”) and pull patterns (“the worker pulls work from the system”) to describe the many ways in which work can be distributed. By delineating these patterns in a form that is independent of specific workflow technologies and modelling languages, we are able to provide a comprehensive treatment of the resource perspective and we subsequently use these patterns as the basis for a detailed comparison of a number of commercially available workflow management systems.
---
paper_title: When four-eyes become too much: a survey on the interplay of authorization constraints and workflow resilience

paper_content:

We survey the state of the art on workflow satisfiability and its practical consequences in terms of runtime obstructions and resilience. The satisfiability problem is related to authorization constraints put on the workflows: irrespective of the particular access control model, authorization constraints such as "separation of duties", delegation of rights and the sudden unavailability of subjects assigned to a particular task (e.g. in case of illness) may lead to situations in which workflow instances cannot be run, i.e. they are not satisfiable. In consequence, these obstructed workflows do not generate the expected value to the company. This constitutes a serious threat for the provision of reliable process-aware information systems and a challenge for reliable enterprise engineering. The contribution of this paper is to systematically classifiy the existing approaches to detect and handle workflow unsatisfiability.
---
paper_title: A systematic review on security in Process-Aware Information Systems - Constitution, challenges, and future directions

paper_content:

Display Omitted HighlightsSecurity in PAIS constitutes an interdisciplinary research area.Security is a multifaceted subject that covers technical and human aspects in PAIS.12 security controls are identified for Process-Aware Information Systems (PAIS).Security controls have centered on preventive countermeasures so far.Reaction, detection, and human orientation constitute promising research directions. ContextSecurity in Process-Aware Information Systems (PAIS) has gained increased attention in current research and practice. However, a common understanding and agreement on security is still missing. In addition, the proliferation of literature makes it cumbersome to overlook and determine state of the art and further to identify research challenges and gaps. In summary, a comprehensive and systematic overview of state of the art in research and practice in the area of security in PAIS is missing. ObjectiveThis paper investigates research on security in PAIS and aims at establishing a common understanding of terminology in this context. Further it investigates which security controls are currently applied in PAIS. MethodA systematic literature review is conducted in order to classify and define security and security controls in PAIS. From initially 424 papers, we selected in total 275 publications that related to security and PAIS between 1993 and 2012. Furthermore, we analyzed and categorized the papers using a systematic mapping approach which resulted into 5 categories and 12 security controls. ResultsIn literature, security in PAIS often centers on specific (security) aspects such as security policies, security requirements, authorization and access control mechanisms, or inter-organizational scenarios. In addition, we identified 12 security controls in the area of security concepts, authorization and access control, applications, verification, and failure handling in PAIS. Based on the results, open research challenges and gaps are identified and discussed with respect to possible solutions. ConclusionThis survey provides a comprehensive review of current security practice in PAIS and shows that security in PAIS is a challenging interdisciplinary research field that assembles research methods and principles from security and PAIS. We show that state of the art provides a rich set of methods such as access control models but still several open research challenges remain.
---
paper_title: When four-eyes become too much: a survey on the interplay of authorization constraints and workflow resilience

paper_content:

We survey the state of the art on workflow satisfiability and its practical consequences in terms of runtime obstructions and resilience. The satisfiability problem is related to authorization constraints put on the workflows: irrespective of the particular access control model, authorization constraints such as "separation of duties", delegation of rights and the sudden unavailability of subjects assigned to a particular task (e.g. in case of illness) may lead to situations in which workflow instances cannot be run, i.e. they are not satisfiable. In consequence, these obstructed workflows do not generate the expected value to the company. This constitutes a serious threat for the provision of reliable process-aware information systems and a challenge for reliable enterprise engineering. The contribution of this paper is to systematically classifiy the existing approaches to detect and handle workflow unsatisfiability.
---
paper_title: Automated Synthesis of Run-time Monitors to Enforce Authorization Policies in Business Processes

paper_content:

Run-time monitors are crucial to the development of security-aware workflow management systems, which need to mediate access to their resources by enforcing authorization policies and constraints, such as Separation of Duty. In this paper, we introduce a precise technique to synthesize run-time monitors capable of ensuring the successful termination of workflows while enforcing authorization policies and constraints. An extensive experimental evaluation shows the scalability of our technique on the important class of hierarchically specified security-sensitive workflows with several hundreds of tasks.
---
paper_title: Satisfiability and Resiliency in Workflow Authorization Systems

paper_content:

We propose the role-and-relation-based access control (R2BAC) model for workflow authorization systems. In R2BAC, in addition to a user’s role memberships, the user’s relationships with other users help determine whether the user is allowed to perform a certain step in a workflow. For example, a constraint may require that two steps must not be performed by users who have conflicts of interests. We study computational complexity of the workflow satisfiability problem, which asks whether a set of users can complete a workflow. In particular, we apply tools from parameterized complexity theory to better understand the complexities of this problem. Furthermore, we reduce the workflow satisfiability problem to SAT and apply SAT solvers to address the problem. Experiments show that our algorithm can solve instances of reasonable size efficiently. Finally, it is sometimes not enough to ensure that a workflow can be completed in normal situations. We study the resiliency problem in workflow authorization systems, which asks whether a workflow can be completed even if a number of users may be absent. We formally define three levels of resiliency in workflow systems and study computational problems related to these notions of resiliency.
---
paper_title: A reference monitor for workflow systems with constrained task execution

paper_content:

We describe a model, independent of any underlying access control paradigm, for specifying authorization constraints such as separation of duty and cardinality constraints in workflow systems. We present a number of results enabling us to simplify the set of authorization constraints. These results form the theoretical foundation for an algorithm that can be used to determine whether a given constrained workflow can be satisfied: that is, does there exist an assignment of authorized users to workflow tasks that satisfies the authorization constraints? We show that this algorithm can be incorporated into a workflow reference monitor that guarantees that every workflow instance can complete. We derive the computational complexity of our algorithm and compare its performance to comparable work in the literature.
---
paper_title: The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency

paper_content:

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a \emph{decision} problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). ::: In this paper, we introduce the \textsc{Bi-Objective Workflow Satisfiability Problem} (\BOWSP), which enables us to solve \emph{optimization} problems related to workflows and security policies. In particular, we are able to compute a "least bad" plan when some components of the security policy may be violated. In general, \BOWSP is intractable from both the classical and parameterized complexity point of view. We prove there exists an fixed-parameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP if we restrict our attention to user-independent constraints. ::: We also present a second algorithm to compute a Pareto front which uses mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most of the instances. ::: Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of \BOWSP.
---
paper_title: Constraint expressions and workflow satisfiability

paper_content:

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.
---
paper_title: Satisfiability and Feasibility in a Relationship-Based Workflow Authorization Model

paper_content:

A workflow authorization model is defined in the framework of Relationship-Based Access Control (ReBAC), in which the protection state is a social network. Armed with this model, we study a new decision problem called workflow feasibility. The goal is to ensure that the space of protection states contains at least one member in which the workflow specification can be executed to completion. We identify a sufficient condition under which feasibility can be decided by a refutation procedure that is both sound and complete. A formal specification language, based on a monotonic fragment of the Propositional Dynamic Logic (PDL), is proposed for specifying protection state spaces. The adoption of this language renders workflow feasibility NP-complete in the general case but polynomial-time decidable for an important family of workflows.
---
paper_title: Minimizing Organizational User Requirement while Meeting Security Constraints

paper_content:

Large systems are complex and typically need automatic configuration to be managed effectively. In any organization, numerous tasks have to be carried out by employees. However, due to security needs, it is not feasible to directly assign any existing task to the first available employee. In order to meet many additional security requirements, constraints such as separation of duty, cardinality and binding have to be taken into consideration. Meeting these requirements imposes extra burden on organizations, which, however, is unavoidable in order to ensure security. While a trivial way of ensuring security is to assign each user to a single task, business organizations would typically like to minimize their costs and keep staffing requirements to a minimum. To meet these contradictory goals, we define the problem of Cardinality Constrained-Mutually Exclusive Task Minimum User Problem (CMUP), which aims to find the minimum users that can carry out a set of tasks while satisfying the given security constraints. We show that the CMUP problem is equivalent to a constrained version of the weak chromatic number problem in hypergraphs, which is NP-hard. We, therefore, propose a greedy solution. Our experimental evaluation shows that the proposed algorithm is both efficient and effective.
---
paper_title: Satisfiability and Resiliency in Workflow Authorization Systems

paper_content:

We propose the role-and-relation-based access control (R2BAC) model for workflow authorization systems. In R2BAC, in addition to a user’s role memberships, the user’s relationships with other users help determine whether the user is allowed to perform a certain step in a workflow. For example, a constraint may require that two steps must not be performed by users who have conflicts of interests. We study computational complexity of the workflow satisfiability problem, which asks whether a set of users can complete a workflow. In particular, we apply tools from parameterized complexity theory to better understand the complexities of this problem. Furthermore, we reduce the workflow satisfiability problem to SAT and apply SAT solvers to address the problem. Experiments show that our algorithm can solve instances of reasonable size efficiently. Finally, it is sometimes not enough to ensure that a workflow can be completed in normal situations. We study the resiliency problem in workflow authorization systems, which asks whether a workflow can be completed even if a number of users may be absent. We formally define three levels of resiliency in workflow systems and study computational problems related to these notions of resiliency.
---
paper_title: Satisfiability and Resiliency in Workflow Authorization Systems

paper_content:

We propose the role-and-relation-based access control (R2BAC) model for workflow authorization systems. In R2BAC, in addition to a user’s role memberships, the user’s relationships with other users help determine whether the user is allowed to perform a certain step in a workflow. For example, a constraint may require that two steps must not be performed by users who have conflicts of interests. We study computational complexity of the workflow satisfiability problem, which asks whether a set of users can complete a workflow. In particular, we apply tools from parameterized complexity theory to better understand the complexities of this problem. Furthermore, we reduce the workflow satisfiability problem to SAT and apply SAT solvers to address the problem. Experiments show that our algorithm can solve instances of reasonable size efficiently. Finally, it is sometimes not enough to ensure that a workflow can be completed in normal situations. We study the resiliency problem in workflow authorization systems, which asks whether a workflow can be completed even if a number of users may be absent. We formally define three levels of resiliency in workflow systems and study computational problems related to these notions of resiliency.
---
paper_title: Resiliency Policies in Access Control Revisited

paper_content:

Resiliency is a relatively new topic in the context of access control. Informally, it refers to the extent to which a multi-user computer system, subject to an authorization policy, is able to continue functioning if a number of authorized users are unavailable. Several interesting problems connected to resiliency were introduced by Li, Wang and Tripunitara [13], many of which were found to be intractable. In this paper, we show that these resiliency problems have unexpected connections with the workflow satisfiability problem (WSP). In particular, we show that an instance of the resiliency checking problem (RCP) may be reduced to an instance of WSP. We then demonstrate that recent advances in our understanding of WSP enable us to develop fixed-parameter tractable algorithms for RCP. Moreover, these algorithms are likely to be useful in practice, given recent experimental work demonstrating the advantages of bespoke algorithms to solve WSP. We also generalize RCP in several different ways, showing in each case how to adapt the reduction to WSP. Li et al also showed that the coexistence of resiliency policies and static separation-of-duty policies gives rise to further interesting questions. We show how our reduction of RCP to WSP may be extended to solve these problems as well and establish that they are also fixed-parameter tractable.
---
paper_title: Cerberus: Automated Synthesis of Enforcement Mechanisms for Security-Sensitive Business Processes

paper_content:

Cerberus is a tool to automatically synthesize run-time enforcement mechanisms for security-sensitive Business Processes BPs. The tool is capable of guaranteeing that the execution constraints $$EC $$ on the tasks together with the authorization policy $$AP $$ and the authorization constraints $$AC $$ are satisfied while ensuring that the process can successfully terminate. Cerberus can be easily integrated in many workflow management systems, it is transparent to process designers, and does not require any knowledge beyond usual BP modeling. The tool works in two phases. At design-time, the enforcement mechanism M, parametric in the authorization policy $$AP $$, is generated from $$EC $$ and $$AC $$; M can thus be used with any instance of the same BP provided that $$EC $$ and $$AC $$ are left unchanged. At run-time, a specific authorization policy is added to M, thereby obtaining an enforcement mechanism $$M^*$$ dedicated to a particular instance of the security-sensitive business process. To validate our approach, we discuss the implementation and usage of Cerberus in the SAP HANA Operational Intelligence platform.
---
paper_title: The specification and enforcement of authorization constraints in workflow management systems

paper_content:

In recent years, workflow management systems (WFMSs) have gained popularity in both research and commercial sectors. WFMSs are used to coordinate and streamline business processes. Very large WFMSs are often used in organizations with users in the range of several thousands and process instances in the range of tens and thousands. To simplify the complexity of security administration, it is common practice in many businesses to allocate a role for each activity in the process and then assign one or more users to each role—granting an authorization to roles rather than to users. Typically, security policies are expressed as constraints (or rules) on users and roles; separation of duties is a well-known constraint. Unfortunately, current role-based access control models are not adequate to model such constraints. To address this issue we (1) present a language to express both static and dynamic authorization constraints as clauses in a logic program; (2) provide formal notions of constraint consistency; and (3) propose algorithms to check the consistency of constraints and assign users and roles to tasks that constitute the workflow in such a way that no constraints are violated.
---
paper_title: Guidelines for snowballing in systematic literature studies and a replication in software engineering

paper_content:

Background: Systematic literature studies have become common in software engineering, and hence it is important to understand how to conduct them efficiently and reliably. Objective: This paper presents guidelines for conducting literature reviews using a snowballing approach, and they are illustrated and evaluated by replicating a published systematic literature review. Method: The guidelines are based on the experience from conducting several systematic literature reviews and experimenting with different approaches. Results: The guidelines for using snowballing as a way to search for relevant literature was successfully applied to a systematic literature review. Conclusions: It is concluded that using snowballing, as a first search strategy, may very well be a good alternative to the use of database searches.
---
paper_title: Avoiding Policy-based Deadlocks in Business Processes

paper_content:

In the field of business process management, deadlocks describe a situation where a workflow execution is blocked and cannot be completed. We speak of policy-based deadlocks if such a situation is caused by unsatisfiable resource requirements due to security constraints specified as part of the business process. In this paper we propose a method to avoid policy-based deadlocks by analyzing a workflow's security constraints, determine the minimal required number of users, and provide an optimal user-activity assignment for a deadlock-free workflow execution. We will finally validate our proposed approach by applying it to a real-world scenario.
---
paper_title: On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations

paper_content:

A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP. In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.
---
paper_title: Petri nets: Properties, analysis and applications

paper_content:

Starts with a brief review of the history and the application areas considered in the literature. The author then proceeds with introductory modeling examples, behavioral and structural properties, three methods of analysis, subclasses of Petri nets and their analysis. In particular, one section is devoted to marked graphs, the concurrent system model most amenable to analysis. Introductory discussions on stochastic nets with their application to performance modeling, and on high-level nets with their application to logic programming, are provided. Also included are recent results on reachability criteria. Suggestions are provided for further reading on many subject areas of Petri nets. >
---
paper_title: Task-based entailment constraints for basic workflow patterns

paper_content:

Access Control decisions are based on the authorisation policies defined for a system as well as observed context and behaviour when evaluating these constraints at runtime. Workflow management systems have been recognised as a primary source for defining authorisation policies at workflow designtime, as well as generating context at runtime. This paper analyses recent work in the workflow community regarding established control-flow patterns. We claim that there is an intrinsic relationship between these patterns and a set of task-based entailment constraints - such as Separation of Duty - that have been recently identified by the access control community. These constraints are based on a pre-determined partial order on sequence and parallel execution patterns. When, however, such an order does not exist, because of more complex control-flow patterns, ambiguous constraint evaluation situations will arise at workflow runtime. Accordingly, this paper reviews basic workflow patterns and identifies relationships between these and task-based entailment constraints. In addition, an analysis of possible runtime ambiguities that may arise from these relationships is presented. Our approach is based on recently developed techniques for visual constraint representation at a workflow design-time.
---
paper_title: On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations

paper_content:

A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP. In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.
---
paper_title: Communicating sequential processes

paper_content:

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of Dijkstra's guarded command, these concepts are surprisingly versatile. Their use is illustrated by sample solutions of a variety of familiar programming exercises.
---
paper_title: The specification and enforcement of authorization constraints in workflow management systems

paper_content:

In recent years, workflow management systems (WFMSs) have gained popularity in both research and commercial sectors. WFMSs are used to coordinate and streamline business processes. Very large WFMSs are often used in organizations with users in the range of several thousands and process instances in the range of tens and thousands. To simplify the complexity of security administration, it is common practice in many businesses to allocate a role for each activity in the process and then assign one or more users to each role—granting an authorization to roles rather than to users. Typically, security policies are expressed as constraints (or rules) on users and roles; separation of duties is a well-known constraint. Unfortunately, current role-based access control models are not adequate to model such constraints. To address this issue we (1) present a language to express both static and dynamic authorization constraints as clauses in a logic program; (2) provide formal notions of constraint consistency; and (3) propose algorithms to check the consistency of constraints and assign users and roles to tasks that constitute the workflow in such a way that no constraints are violated.
---
paper_title: Petri nets, algebras, morphisms, and compositionality

paper_content:

Abstract It is shown how a category of Petri nets can be viewed as a subcategory of two sorted algebras over multisets. This casts Petri nets in a familiar framework and provides a useful idea of morphism on nets different from the conventional definition—the morphisms here respect the behaviour of nets. The categorical constructions which result provide a useful way to synthesise nets and reason about nets in terms of their components; for example, various forms of parallel composition of Petri nets arise naturally from the product in the category. This abstract setting makes plain a useful functor from the category of Petri nets to a category of spaces of invariants and provides insight into the generalisations of the basic definition of Petri nets—for instance, the coloured and higher level nets of Kurt Jensen arise through a simple modification of the sorts of the algebras underlying nets. Further, it provides a smooth formal relation with other models of concurrency such as Milner's calculus of communicating systems (CCS) and Hoare's communicating sequential processes (CSP), though this is only indicated in this paper.
---
paper_title: Beyond separation of duty: An algebra for specifying high-level security policies

paper_content:

The process of introducing security controls into a sensitive task, which we call secure task design in this article, consists of two steps: high-level security policy design and low-level enforcement scheme design. A high-level security policy states an overall requirement for a sensitive task. One example of a high-level security policy is a separation of duty policy, which requires a task to be performed by a team of at least k users. Unlike low-level enforcement schemes such as security constraints in workflows, a separation of duty policy states a high-level requirement about the task without referring to individual steps in the task. While extremely important and widely used, separation of duty policies state only requirements on the number of users involved in the task and do not capture the requirements on these users' attributes. In this article, we introduce a novel algebra that enables the formal specification of high-level policies that combine requirements on users' attributes with requirements on the number of users motivated by separation of duty considerations. We give the syntax and semantics of the algebra and study algebraic properties of its operators. After that, we study potential mechanisms to enforce high-level policies specified in the algebra and a number of computational problems related to policy analysis and enforcement.
---
paper_title: Task-based entailment constraints for basic workflow patterns

paper_content:

Access Control decisions are based on the authorisation policies defined for a system as well as observed context and behaviour when evaluating these constraints at runtime. Workflow management systems have been recognised as a primary source for defining authorisation policies at workflow designtime, as well as generating context at runtime. This paper analyses recent work in the workflow community regarding established control-flow patterns. We claim that there is an intrinsic relationship between these patterns and a set of task-based entailment constraints - such as Separation of Duty - that have been recently identified by the access control community. These constraints are based on a pre-determined partial order on sequence and parallel execution patterns. When, however, such an order does not exist, because of more complex control-flow patterns, ambiguous constraint evaluation situations will arise at workflow runtime. Accordingly, this paper reviews basic workflow patterns and identifies relationships between these and task-based entailment constraints. In addition, an analysis of possible runtime ambiguities that may arise from these relationships is presented. Our approach is based on recently developed techniques for visual constraint representation at a workflow design-time.
---
paper_title: On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations

paper_content:

A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP. In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.
---
paper_title: The specification and enforcement of authorization constraints in workflow management systems

paper_content:

In recent years, workflow management systems (WFMSs) have gained popularity in both research and commercial sectors. WFMSs are used to coordinate and streamline business processes. Very large WFMSs are often used in organizations with users in the range of several thousands and process instances in the range of tens and thousands. To simplify the complexity of security administration, it is common practice in many businesses to allocate a role for each activity in the process and then assign one or more users to each role—granting an authorization to roles rather than to users. Typically, security policies are expressed as constraints (or rules) on users and roles; separation of duties is a well-known constraint. Unfortunately, current role-based access control models are not adequate to model such constraints. To address this issue we (1) present a language to express both static and dynamic authorization constraints as clauses in a logic program; (2) provide formal notions of constraint consistency; and (3) propose algorithms to check the consistency of constraints and assign users and roles to tasks that constitute the workflow in such a way that no constraints are violated.
---
paper_title: Algorithms for the workflow satisfiability problem engineered for counting constraints

paper_content:

The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification that satisfies the constraints in the specification. The problem is NP-hard in general, but several subclasses of the problem are known to be fixed-parameter tractable (FPT) when parameterized by the number of steps in the specification. In this paper, we consider the WSP with user-independent counting constraints, a large class of constraints for which the WSP is known to be FPT. We describe an efficient implementation of an FPT algorithm for solving this subclass of the WSP and an experimental evaluation of this algorithm. The algorithm iteratively generates all equivalence classes of possible partial solutions until, whenever possible, it finds a complete solution to the problem. We also provide a reduction from a WSP instance to a pseudo-Boolean SAT instance. We apply this reduction to the instances used in our experiments and solve the resulting PB SAT problems using SAT4J, a PB SAT solver. We compare the performance of our algorithm with that of SAT4J and discuss which of the two approaches would be more effective in practice.
---
paper_title: Iterative Plan Construction for the Workflow Satisfiability Problem

paper_content:

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan - an assignment of tasks to authorized users - such that all constraints are satisfied. It is natural to see the WSP as a subclass of the Constraint Satisfaction Problem (CSP) in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive is that the number of tasks is usually very small compared to the number of users, so it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. ::: ::: This novel approach to the WSP, using techniques from CSP, has enabled us to design a generic algorithm which is FPT for several families of workflow constraints considered in the literature. Furthermore, we prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. Lastly, we identify a new FPT constraint language, user-independent constraints, that includes many of the constraints of interest in business processing systems. We demonstrate that our generic algorithm has provably optimal running time O*(2k log k), for this language, where k is the number of tasks.
---
paper_title: Role-Based Access Control Models

paper_content:

Security administration of large systems is complex, but it can be simplified by a role-based access control approach. This article explains why RBAC is receiving renewed attention as a method of security administration and review, describes a framework of four reference models developed to better understand RBAC and categorizes different implementations, and discusses the use of RBAC to manage itself.
---
paper_title: Constraint expressions and workflow satisfiability

paper_content:

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.
---
paper_title: Assisting the Deployment of Security-Sensitive Workflows by Finding Execution Scenarios

paper_content:

To support the re-use of business process models, an emerging trend in Business Process Management, it is crucial to assist customers during deployment. We study how to do this for an important class of business processes, called security-sensitive workflows, in which execution constraints on the tasks are complemented with authorization constraints (e.g., Separation of Duty) and authorization policies (constraining which users can execute which tasks). We identify the capability of solving Scenario Finding Problems (SFPs), i.e. finding concrete execution scenarios, as crucial in supporting the re-use of security-sensitive workflows. Solutions of SFPs provide evidence that the business process model can be successfully executed under the policy adopted by the customer. We present a technique for solving two SFPs and validate it on real-world business process models taken from an on-line library.
---
paper_title: When four-eyes become too much: a survey on the interplay of authorization constraints and workflow resilience

paper_content:

We survey the state of the art on workflow satisfiability and its practical consequences in terms of runtime obstructions and resilience. The satisfiability problem is related to authorization constraints put on the workflows: irrespective of the particular access control model, authorization constraints such as "separation of duties", delegation of rights and the sudden unavailability of subjects assigned to a particular task (e.g. in case of illness) may lead to situations in which workflow instances cannot be run, i.e. they are not satisfiable. In consequence, these obstructed workflows do not generate the expected value to the company. This constitutes a serious threat for the provision of reliable process-aware information systems and a challenge for reliable enterprise engineering. The contribution of this paper is to systematically classifiy the existing approaches to detect and handle workflow unsatisfiability.
---
paper_title: Satisfiability and Resiliency in Workflow Authorization Systems

paper_content:

We propose the role-and-relation-based access control (R2BAC) model for workflow authorization systems. In R2BAC, in addition to a user’s role memberships, the user’s relationships with other users help determine whether the user is allowed to perform a certain step in a workflow. For example, a constraint may require that two steps must not be performed by users who have conflicts of interests. We study computational complexity of the workflow satisfiability problem, which asks whether a set of users can complete a workflow. In particular, we apply tools from parameterized complexity theory to better understand the complexities of this problem. Furthermore, we reduce the workflow satisfiability problem to SAT and apply SAT solvers to address the problem. Experiments show that our algorithm can solve instances of reasonable size efficiently. Finally, it is sometimes not enough to ensure that a workflow can be completed in normal situations. We study the resiliency problem in workflow authorization systems, which asks whether a workflow can be completed even if a number of users may be absent. We formally define three levels of resiliency in workflow systems and study computational problems related to these notions of resiliency.
---
paper_title: A reference monitor for workflow systems with constrained task execution

paper_content:

We describe a model, independent of any underlying access control paradigm, for specifying authorization constraints such as separation of duty and cardinality constraints in workflow systems. We present a number of results enabling us to simplify the set of authorization constraints. These results form the theoretical foundation for an algorithm that can be used to determine whether a given constrained workflow can be satisfied: that is, does there exist an assignment of authorized users to workflow tasks that satisfies the authorization constraints? We show that this algorithm can be incorporated into a workflow reference monitor that guarantees that every workflow instance can complete. We derive the computational complexity of our algorithm and compare its performance to comparable work in the literature.
---
paper_title: Fundamentals of Parameterized Complexity

paper_content:

This comprehensive and self-contained textbook presents an accessible overview of the state of the art of multivariate algorithmics and complexity. Increasingly, multivariate algorithmics is having significant practical impact in many application domains, with even more developments on the horizon. The text describes how the multivariate framework allows an extended dialog with a problem, enabling the reader who masters the complexity issues under discussion to use the positive and negative toolkits in their own research. Features: describes many of the standard algorithmic techniques available for establishing parametric tractability; reviews the classical hardness classes; explores the various limitations and relaxations of the methods; showcases the powerful new lower bound techniques; examines various different algorithmic solutions to the same problems, highlighting the insights to be gained from each approach; demonstrates how complexity methods and ideas have evolved over the past 25 years.
---
paper_title: The specification and enforcement of authorization constraints in workflow management systems

paper_content:

In recent years, workflow management systems (WFMSs) have gained popularity in both research and commercial sectors. WFMSs are used to coordinate and streamline business processes. Very large WFMSs are often used in organizations with users in the range of several thousands and process instances in the range of tens and thousands. To simplify the complexity of security administration, it is common practice in many businesses to allocate a role for each activity in the process and then assign one or more users to each role—granting an authorization to roles rather than to users. Typically, security policies are expressed as constraints (or rules) on users and roles; separation of duties is a well-known constraint. Unfortunately, current role-based access control models are not adequate to model such constraints. To address this issue we (1) present a language to express both static and dynamic authorization constraints as clauses in a logic program; (2) provide formal notions of constraint consistency; and (3) propose algorithms to check the consistency of constraints and assign users and roles to tasks that constitute the workflow in such a way that no constraints are violated.
---
paper_title: Satisfiability and Resiliency in Workflow Systems

paper_content:

We propose the role-and-relation-based access control (R2BAC) model for workflow systems. In R2BAC, in addition to a user's role memberships, the user's relationships with other users help determine whether the user is allowed to perform a certain step in a workflow. For example, a constraint may require that two steps must not be performed by users who have a conflict of interest. We also study the workflow satisfiability problem, which asks whether a set of users can complete a workflow. We show that the problem is NP-complete for R2BAC, and is NP-complete for any workflow model that supports certain simple types of constraints (e.g., constraints that state certain two steps must be performed by two different users). After that, we apply tools from parameterized complexity theory to better understand the complexities of this problem. We show that the problem is fixed-parameter tractable when the only relations used are = and ≠, and is fixed-parameter intractable when user-defined binary relations can be used. Finally, we study the resiliency problem in workflow systems, which asks whether a workflow can be completed even if a number of users may be absent. We formally define three levels of resiliency in workflow systems, namely, static resiliency, decremental resiliency and dynamic resiliency, and study computational problems related to these notions of resiliency.
---
paper_title: The consistency of task-based authorization constraints in workflow

paper_content:

Workflow management systems (WFMSs) have attracted a lot of interest both in academia and the business community. A workflow consists of a collection of tasks that are organized to facilitate some business process specification. To simplify the complexity of security administration, it is common to use role-based access control (RBAC) to grant authorization to roles and users. Typically, security policies are expressed as constraints on users, roles, tasks and the workflow itself. A workflow system can become very complex and involve several organizations or different units of an organization, thus the number of security policies may be very large and their interactions very complex. It is clearly important to know whether the existence of such constraints will prevent certain instances of the workflow from completing. Unfortunately, no existing constraint models have considered this problem satisfactorily. In this paper, we define a model for constrained workflow systems that includes local and global cardinality constraints, separation of duty constraints and binding of duty constraints. We define the notion of a workflow specification and of a constrained workflow authorization schema. Our main result is to establish necessary and sufficient conditions for the set of constraints that ensure a sound constrained workflow authorization schema, that is, for any user or any role who are authorized to a task, there is at least one complete workflow instance when this user or this role executes this task.
---
paper_title: Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis

paper_content:

The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equals constraints. Since the number of steps $k$ is relatively small in practice, Wang and Li (2010) introduced a parametrisation of WSP by $k$. Wang and Li (2010) showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) and Cohen et al. (2014) designed FPT algorithms of running time $O^*(2^{k})$ and $O^*(2^{k\log_2 k})$ for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time $O^*(2^{ck})$ and $O^*(2^{ck\log_2 k})$ for the two restrictions of WSP, respectively, with any $c<1$, unless the Strong Exponential Time Hypothesis fails.
---
paper_title: Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints

paper_content:

The workflow satisfiability problem (WSP) is a planning problem. Certain sub-classes of this problem have been shown to be fixed-parameter tractable. In this paper we develop an implementation of an algorithm for WSP that has been shown, in our previous paper, to be fixed-parameter for user-independent constraints. In a set of computational experiments, we compare our algorithm to an encoding of the WSP into a pseudo-Boolean SAT problem solved by the well-known solver SAT4J. Our algorithm solves all instances of WSP generated in our experiments, unlike SAT4J, and it solves many instances faster than SAT4J. For lightly constrained instances, SAT4J usually outperforms our algorithm.
---
paper_title: On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations

paper_content:

A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP. In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.
---
paper_title: On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem

paper_content:

A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of 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 runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.
---
paper_title: On the Workflow Satisfiability Problem with Class-Independent Constraints

paper_content:

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.
---
paper_title: Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints

paper_content:

The workflow satisfiability problem is concerned with determining whether it is possible to find an allocation of authorized users to the steps in a workflow in such a way that all constraints are satisfied. The problem is NP-hard in general, but is known to be fixed-parameter tractable for certain classes of constraints. The known results on fixed-parameter tractability rely on the symmetry (in some sense) of the constraints. In this paper, we provide the first results that establish fixed-parameter tractability of the satisfiability problem when the constraints are asymmetric. In particular, we introduce the notion of seniority constraints, in which the execution of steps is determined, in part, by the relative seniority of the users that perform them. Our results require new techniques, which make use of tree decompositions of the graph of the binary relation defining the constraint. Finally, we establish a lower bound for the hardness of the workflow satisfiability problem.
---
paper_title: On the Satisfiability of Workflows with Release Points

paper_content:

There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specification means that it is impossible to allocate authorized users to each step in the workflow. Recent developments have seen the workflow satisfiability problem (WSP) studied in the context of workflow specifications in which the set of steps may vary from one instance of the workflow to another. This, in turn, means that some constraints may only apply to certain workflow instances. Inevitably, WSP becomes more complex for such workflow specifications. In this paper, we present the first fixed parameter algorithms to solve WSP for workflow specifications of this type. Moreover, we significantly extend the range of constraints that can be used in workflow specifications of this type.
---
paper_title: Constraint expressions and workflow satisfiability

paper_content:

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.
---
paper_title: Algorithms for the workflow satisfiability problem engineered for counting constraints

paper_content:

The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification that satisfies the constraints in the specification. The problem is NP-hard in general, but several subclasses of the problem are known to be fixed-parameter tractable (FPT) when parameterized by the number of steps in the specification. In this paper, we consider the WSP with user-independent counting constraints, a large class of constraints for which the WSP is known to be FPT. We describe an efficient implementation of an FPT algorithm for solving this subclass of the WSP and an experimental evaluation of this algorithm. The algorithm iteratively generates all equivalence classes of possible partial solutions until, whenever possible, it finds a complete solution to the problem. We also provide a reduction from a WSP instance to a pseudo-Boolean SAT instance. We apply this reduction to the instances used in our experiments and solve the resulting PB SAT problems using SAT4J, a PB SAT solver. We compare the performance of our algorithm with that of SAT4J and discuss which of the two approaches would be more effective in practice.
---
paper_title: On the parameterized complexity of the workflow satisfiability problem

paper_content:

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of those steps. A workflow specification is said to be satisfiable if there exists an assignment of 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. Finding such an assignment is a hard problem in general, but work by Wang and Li in 2010 using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this paper, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints.
---
paper_title: Iterative Plan Construction for the Workflow Satisfiability Problem

paper_content:

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan - an assignment of tasks to authorized users - such that all constraints are satisfied. It is natural to see the WSP as a subclass of the Constraint Satisfaction Problem (CSP) in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive is that the number of tasks is usually very small compared to the number of users, so it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. ::: ::: This novel approach to the WSP, using techniques from CSP, has enabled us to design a generic algorithm which is FPT for several families of workflow constraints considered in the literature. Furthermore, we prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. Lastly, we identify a new FPT constraint language, user-independent constraints, that includes many of the constraints of interest in business processing systems. We demonstrate that our generic algorithm has provably optimal running time O*(2k log k), for this language, where k is the number of tasks.
---
paper_title: Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

paper_content:

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan -- an assignment of tasks to authorized users -- such that all constraints are satisfied. ::: The WSP is, in fact, the conservative Constraint Satisfaction Problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, NP-complete. It was observed by Wang and Li (2010) that the number k of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of WSP regarding parameter k. ::: We take a more detailed look at the kernelization complexity of WSP(\Gamma) when \Gamma\ denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in \Gamma\ are regular: (1) We are able to reduce the number n of users to n' <= k. This entails a kernelization to size poly(k) for finite \Gamma, and, under mild technical conditions, to size poly(k+m) for infinite \Gamma, where m denotes the number of constraints. (2) Already WSP(R) for some R \in \Gamma\ allows no polynomial kernelization in k+m unless the polynomial hierarchy collapses.
---
paper_title: Automated Synthesis of Run-time Monitors to Enforce Authorization Policies in Business Processes

paper_content:

Run-time monitors are crucial to the development of security-aware workflow management systems, which need to mediate access to their resources by enforcing authorization policies and constraints, such as Separation of Duty. In this paper, we introduce a precise technique to synthesize run-time monitors capable of ensuring the successful termination of workflows while enforcing authorization policies and constraints. An extensive experimental evaluation shows the scalability of our technique on the important class of hierarchically specified security-sensitive workflows with several hundreds of tasks.
---
paper_title: Verification of Composed Array-Based Systems with Applications to Security-Aware Workflows

paper_content:

We introduce a class of symbolic transition systems capable of representing collections of security-aware workflows and we study the verification of reachability properties of such systems. More precisely, we define composed array-based systems as an extension of array-based systems in which array variables are indexed over more than one type. For an application relevant sub-class of these systems we show how to mechanize a symbolic backward reachability procedure by modularly re-using the techniques developed for array-based systems. Finally, and most importantly, we find sufficient conditions for the termination of the procedure and we apply this result to derive the decidability of the reachability problems of two important classes of security-aware workflow systems.
---
paper_title: A SMT-based methodology for monitoring of security-aware workflows

paper_content:

Run-time monitors are crucial to the development of security-aware workflow management systems, which are at the heart of modern e-services and need to mediate access to their resources by imposing authorisation constraints (e.g., separation of duty). In this paper, we propose a new methodology to build run-time monitors capable of ensuring the successful termination of workflows subject to authorisation constraints. The methodology is based on state-of-the-art satisfiability modulo theories techniques.
---
paper_title: On the Modeling and Verification of Security-Aware and Process-Aware Information Systems

paper_content:

Many business processes are modeled as workflows, which often need to comply with business rules, legal requirements, and authorization policies. Workflow satisfiability is the problem of determining whether there exists a workflow instance that realizes the workflow specification while simultaneously complying with such constraints. Although this problem has been studied by the computer security community in the past, existing solutions are tailored for particular workflow models, so their applicability to other models or richer forms of analysis is questionable. We here investigate whether the satisfiability of formulas in an NP-complete fragment of linear-time temporal logic can serve as a more expressive and versatile tool for deciding the satisfiability of workflows. We also show that this fragment can solve this problem for a standard model from the literature.
---
paper_title: Cerberus: Automated Synthesis of Enforcement Mechanisms for Security-Sensitive Business Processes

paper_content:

Cerberus is a tool to automatically synthesize run-time enforcement mechanisms for security-sensitive Business Processes BPs. The tool is capable of guaranteeing that the execution constraints $$EC $$ on the tasks together with the authorization policy $$AP $$ and the authorization constraints $$AC $$ are satisfied while ensuring that the process can successfully terminate. Cerberus can be easily integrated in many workflow management systems, it is transparent to process designers, and does not require any knowledge beyond usual BP modeling. The tool works in two phases. At design-time, the enforcement mechanism M, parametric in the authorization policy $$AP $$, is generated from $$EC $$ and $$AC $$; M can thus be used with any instance of the same BP provided that $$EC $$ and $$AC $$ are left unchanged. At run-time, a specific authorization policy is added to M, thereby obtaining an enforcement mechanism $$M^*$$ dedicated to a particular instance of the security-sensitive business process. To validate our approach, we discuss the implementation and usage of Cerberus in the SAP HANA Operational Intelligence platform.
---
paper_title: Verifying BPEL Workflows Under Authorisation Constraints

paper_content:

Business Process Execution Language (BPEL), or Web Services BPEL (WS-BPEL), is the standard for specifying workflow process definition using web services. Research on formal modelling and verification of BPEL has largely concentrated on control flow and data flow, while security related properties have received little attention. In this work, we present a formal framework that integrates Role Based Access Control (RBAC) into BPEL and allows us to express authorisation constraints using temporal logic. Using this framework, we show how model-checking can be applied to verify that a given BPEL process satisfies the security constraints.
---
paper_title: A methodology to build run-time monitors for security-aware workflows

paper_content:

Run-time monitors are crucial to the development of workflow management systems, which are at the heart of several modern E-services. In this paper, we propose a new methodology to build run-time monitors capable of ensuring the successful termination of workflows subject to authorization constraints. The methodology is based on state-of-the-art Satisfiability Modulo Theories techniques.
---
paper_title: Aegis: Automatic Enforcement of Security Policies in Workflow-driven Web Applications

paper_content:

Organizations often expose business processes and services as web applications. Improper enforcement of security policies in these applications leads to business logic vulnerabilities that are hard to find and may have dramatic security implications. Aegis is a tool to automatically synthesize run-time monitors to enforce control-flow and data-flow integrity, as well as authorization policies and constraints in web applications. The enforcement of these properties can mitigate attacks, e.g., authorization bypass and workflow violations, while allowing regulatory compliance in the form of, e.g., Separation of Duty. Aegis is capable of guaranteeing business continuity while enforcing the security policies. We evaluate Aegis on a set of real-world applications, assessing the enforcement of policies, mitigation of vulnerabilities, and performance overhead.
---
paper_title: Modular Synthesis of Enforcement Mechanisms for the Workflow Satisfiability Problem: Scalability and Reusability

paper_content:

Modularity is an important concept in the design and enactment of workflows. However, supporting the specification and enforcement of authorization in this setting is not straightforward. In this paper, we introduce a notion of component and a combination mechanism for security-sensitive workflows. These are business processes in which execution constraints on the tasks are complemented with authorization constraints (e.g., Separation of Duty) and authorization policies (specifying which users can execute which tasks). We show how authorization constraints can also be imposed across components and demonstrate the usefulness of our notion of component by showing (i) the scalability of a technique for the synthesis of run-time monitors for security-sensitive workflows; and (ii) the design of a plug-in for the reuse of workflows and related run-time monitors inside an editor for security-sensitive workflows.
---
paper_title: Verification of Business Process Entailment Constraints Using SPIN

paper_content:

The verification of access controls is essential for providing secure systems. Model checking is an automated technique used for verifying finite state machines. The properties to be verified are usually expressed as formula in temporal logic. In this paper we present an approach to verify access control security properties of a security annotated business process model. To this end we utilise a security enhanced BPMN notation to define access control properties. ::: ::: To enhance the usability the complex and technical details are hidden from the process modeller by using an automatic translation of the process model into a process meta language (Promela) based on Coloured Petri net (CPN) semantics. ::: ::: The model checker SPIN is used for the process model verification and a trace file is written to provide visual feedback to the modeller on the abstraction level of the verified process model. As a proof of concept the described translation methodology is implemented as a plug-in for the free web-based BPMN modelling tool Oryx.
---
paper_title: Security-Sensitive Tackling of Obstructed Workow Executions

paper_content:

Imposing access control onto workflows considerably reduces the set of users authorized to execute the workflow tasks. Further constraints (e.g. Separation of Duties) as well as unexpected unavailabilty of users may finally obstruct the successful workflow execution. To still complete the execution of an obstructed workflow, we envisage a hybrid ::: approach. If a log is provided, we partition its traces into “successful” and “obstructed” ones by analysing the given workflow and its authorizations. An obstruction should then be solved by finding its nearest match from the list of successful traces. If no log is provided, we flatten the workflow and its authorizations into a Petri net and encode the obstruction with a corresponding “obstruction marking”. The structural theory of Petri nets shall then be tweaked to provide a minimized Parikh vector, that may violate given firing rules, however reach a complete marking and by that, complete the workflow.
---
paper_title: Optimal workflow-aware authorizations

paper_content:

Balancing protection and empowerment is a central problem when specifying authorizations. The principle of least privilege, the classical approach to balancing these two conflicting objectives, says that users shall only be authorized to execute the tasks necessary to complete their job. However, when there are multiple authorization policies satisfying least privilege, which one should be chosen? In this paper, we model the tasks that users must execute as workflows, and the risk and cost associated with authorization policies and their administration. We then formulate the balancing of empowerment and protection as an optimization problem: finding a cost-minimizing authorization policy that allows a successful workflow execution. We show that finding an optimal solution for a role-based cost function is NP-complete. We support our results with a series of examples, which we also use to measure the performance of our prototype implementation.
---
paper_title: Secure workflow deployment in multi-organizational environments

paper_content:

A centrifugal separator has a centrifuge rotor and a casing, the casing forming an outer space for the rotor. The rotor is rotatable around a rotary axis and within the casing. The rotor includes a rotor wall, which defines an outer periphery of the rotor and encloses an inner space, an inlet, which extends through the rotor wall and permits feeding of a product to the inner space, and a number of outlets, which extend through the rotor wall and are arranged to permit intermittent discharge of a separated product from the inner space to the outer space. The outlets are distributed around the periphery of the rotor. The number of outlets is uneven, and a valve member extends around the rotor wall to define a space between the wall and the valve member at the level of the outlets.
---
paper_title: Organization based access control

paper_content:

None of the classical access control models such as DAC, MAC, RBAC, TBAC or TMAC is fully satisfactory to model security policies that are not restricted to static permissions but also include contextual rules related to permissions, prohibitions, obligations and recommendations. This is typically the case of security policies that apply to the health care domain. We suggest a new model that provides solutions to specify such contextual security policies. This model, called organization based access control, is presented using a formal language based on first-order logic.
---
paper_title: Dynamic enforcement of abstract separation of duty constraints

paper_content:

Separation of Duties (SoD) aims to prevent fraud and errors by distributing tasks and associated privileges among multiple users. Li and Wang proposed an algebra (SoDA) for specifying SoD requirements, which is both expressive in the requirements it formalizes and abstract in that it is not bound to any specific workflow model. In this paper, we both generalize SoDA and map it to enforcement mechanisms. First, we increase SoDA's expressiveness by extending its semantics to multisets. This better suits policy enforcement over workflows, where users may execute multiple tasks. Second, we further generalize SoDA to allow for changing role assignments. This lifts the strong restriction that authorizations do not change during workflow execution. Finally, we map SoDA terms to CSP processes, taking advantage of CSP's operational semantics to provide the critical link between abstract specifications of SoD requirements by SoDA terms and runtime-enforcement mechanisms.
---
paper_title: On the satisfiability of authorization requirements in business process

paper_content:

Satisfiability problem of authorization requirements in business process asks whether there exists an assignment of users to tasks that satisfies all the requirements, and methods were proposed to solve this problem. However, the proposed methods are inefficient in the sense that a step of the methods is searching all the possible assignments, which is time-consuming. This work proposes a method to solve the satisfiability problem of authorization requirements without browsing the assignments space. Our method uses improved separation of duty algebra (ISoDA) to describe a satisfiability problem of qualification requirements and quantification requirements (Separation of Duty and Binding of Duty requirements). Thereafter, ISoDA expressions are reduced into multi-mutual-exclusive expressions. The satisfiabilities of multi-mutual-exclusive expressions are determined by an efficient algorithm proposed in this study. The experiment shows that our method is faster than the state-of-the-art methods.
---
paper_title: ECA rules for controlling authorisation plan to satisfy dynamic constraints

paper_content:

The workflow satisfiability problem has been studied by researchers in the security community using various approaches. The goal is to ensure that the user/role is authorised to execute the current task and that this permission doesn't prevent the remaining tasks in the workflow instance to be achieved. A valid authorisation plan consists in affecting authorised roles and users to workflow tasks in such a way that all the authorisation constraints are satisfied. Previous works are interested in workflow satisfiability problem by considering intra-instance constraints, i.e. constraints which are applied to a single instance. However, inter-instance constraints which are specified over multiple workflow instances are also paramount to mitigate the security frauds. In this paper, we present how ECA (Event-Condition-Action) paradigm and agent technology can be exploited to control authorisation plan in order to meet dynamic constraints, namely intra-instance and inter-instance constraints. We present a specification of a set of ECA rules that aim to achieve this goal. A prototype implementation of our proposed approach is also provided in this paper.
---
paper_title: Inter-instance authorization constraints for secure workflow management

paper_content:

Work flows model and control the execution of business process in an organization. They are typically comprised of tasks or logical steps in the business process. To mitigate the ability of insiders to commit fraud, care should be taken that people authorized to perform critical tasks cannot collude. This is typically done through the specification of separation of duty (SOD)constraints. SOD constraints impose restrictions on which users or roles can be assigned to tasks and have been discussed widely in the research literature in the context of a single work flow instance. In this paper, we argue that SOD constraints that span multiple instances of a work flow also need to be considered to mitigate the security fraud. To this end, we extend the notion of SOD to include constraints that span multiple executing instances of a work flow and constraints that also take into consideration the history of completed work flow instances. We present a constraint specification language to specify the inter-instance constraints and propose methodologies to identify the cases in which certain SOD specifications would result in an anomaly. Specifically, we identify 3 types of anomalies, namely, inconsistency, depletion anomaly and overlapping anomaly The identification and rectification of anomalies are done at both the work flow specification time as well as at runtime,as appropriate,so that users can be assigned to tasks in a consistent manner.
---
paper_title: Satisfiability Analysis of Workflows with Control-Flow Patterns and Authorization Constraints

paper_content:

Workflow security has become increasingly important and challenging in today's open service world. While much research has been conducted on various security issues of workflow systems, the workflow satisfiability problem, which asks whether a set of users together can complete a workflow, is recently identified as an important research problem that needs more investigation. In this paper, we study the computational complexity of the problem along two directions: one is by considering either one path or all paths of a workflow, and the other is by considering the possible patterns in a workflow. We have shown that the general workflow satisfiability analysis problem is intractable. This result motivates us to consider restrictions on workflow control-flow patterns and access control policies, and to identify tractable cases of practical interest.
---
paper_title: Obstruction-Free Authorization Enforcement: Aligning Security with Business Objectives

paper_content:

Access control is fundamental in protecting information systems but it also poses an obstacle to achieving business objectives. We analyze this tradeoff and its avoidance in the context of systems modeled as workflows restricted by authorization constraints including those specifying Separation of Duty (SoD) and Binding of Duty (BoD).To begin with, we present a novel approach to scoping authorization constraints within workflows with loops and conditional execution. Afterwards, we consider enforcement's effects on business objectives. We identify the notion of obstruction, which generalizes deadlock within a system where access control is enforced, and we formulate the existence of an obstruction-free enforcement mechanism as a decision problem. We present lower and upper bounds for the complexity of this problem and also give an approximation algorithm that performs well when authorizations are equally distributed among users.
---
paper_title: Security Constraints in Temporal Role-Based Access-Controlled Workflows

paper_content:

Workflows and role-based access control models need to be suitably merged, in order to allow users to perform processes in a correct way, according to the given data access policies and the temporal constraints. Given a mapping between workflow models and simple temporal networks with uncertainty, we discuss a mapping between role temporalities and simple temporal networks, and how to connect the two resulting networks to make explicit who can do what, when. If the connected network is still executable, we show how to compute the set of authorized users for each task. Finally, we define security constraints (to prevent users from doing unauthorized actions) and security constraint propagation rules (to propagate security constraints at runtime). We also provide an algorithm to check whether a set of propagation rules is safe, and we extend an existing execution algorithm to take into account these new security aspects.
---
paper_title: Chromatic Graph Theory

paper_content:

Beginning with the origin of the four color problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. Introducing graph theory with a coloring theme, Chromatic Graph Theory explores connections between major topics in graph theory and graph colorings as well as emerging topics. This self-contained book first presents various fundamentals of graph theory that lie outside of graph colorings, including basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the text deals exclusively with graph colorings. It covers vertex colorings and bounds for the chromatic number, vertex colorings of graphs embedded on surfaces, and a variety of restricted vertex colorings. The authors also describe edge colorings, monochromatic and rainbow edge colorings, complete vertex colorings, several distinguishing vertex and edge colorings, and many distance-related vertex colorings. With historical, applied, and algorithmic discussions, this text offers a solid introduction to one of the most popular areas of graph theory.
---
paper_title: Flexible Scoping of Authorization Constraints on Business Processes with Loops and Parallelism

paper_content:

Real-life business process specifications include situations where work may be repeated due to exceptions such as the lack of resources or failed approvals. However, most authorization constraint models for business processes describe them as partially ordered sets of tasks. This abstraction simplifies the analysis of constraints greatly but prevents their use in real systems because control flows with loops are not supported. To overcome this limitation, we scope authorization constraints to task instances using the concept of release, which removes associations between users and their previously executed tasks. We define a model applying releases to cardinality and interval constraints, such as Separation of Duty (SoD). The latter is based on the notion of intervals defined by pairs of tasks and imposing conditions on the users executing them. We extend BPMN to visualize our constraints, bridging the gap between IT and business people as well as to auditors.
---
paper_title: Checking Satisfiability Aspects of Binding Constraints in a Business Process Context

paper_content:

Binding of Duty (BOD) constraints define that the same subject (or role) who performed a certain task t 1 must also perform a corresponding bound task t 2. In this paper, we describe algorithms for checking the satisfiability of binding constraints in a business process context. In particular, these algorithms check the configuration of a process-related RBAC model to find satisfiability conflicts. Furthermore, we discuss options to resolve satisfiability conflicts.
---
paper_title: Deploying Access and Flow Control in Distributed Workflows

paper_content:

Workflows are operational business processes. Workflow Management Systems (WFMS) are concerned with the control and coordination of these workflows. In recent years, there has been a trend to integrate WFMS in distributed inter-organizational systems. In this case malfunctioning of one WFMS can affect more than one organization, making the correct functioning of a WFMS a critical issue. Thus, an important function of WFMS is to enforce the security of these interorganizational workflows. Several works have been done to integrate the security aspects in the workflow specification. Unfortunately, these research works generally adopt a centralized management approach and are based on static access control models. Therefore, they do not deal with flow control, a very important requirement in WFMS. In this paper, we suggest a decentralized and dynamic approach to handle a security policy in workflows taking into account access and flow control. The last part of the paper deals with the workflow satisfiability problem. It studies the complexity of the problem which asks whether a set of users can complete a constrained workflow in some system configuration.
---
paper_title: Automated Synthesis of Run-time Monitors to Enforce Authorization Policies in Business Processes

paper_content:

Run-time monitors are crucial to the development of security-aware workflow management systems, which need to mediate access to their resources by enforcing authorization policies and constraints, such as Separation of Duty. In this paper, we introduce a precise technique to synthesize run-time monitors capable of ensuring the successful termination of workflows while enforcing authorization policies and constraints. An extensive experimental evaluation shows the scalability of our technique on the important class of hierarchically specified security-sensitive workflows with several hundreds of tasks.
---
paper_title: Satisfiability and Resiliency in Workflow Authorization Systems

paper_content:

We propose the role-and-relation-based access control (R2BAC) model for workflow authorization systems. In R2BAC, in addition to a user’s role memberships, the user’s relationships with other users help determine whether the user is allowed to perform a certain step in a workflow. For example, a constraint may require that two steps must not be performed by users who have conflicts of interests. We study computational complexity of the workflow satisfiability problem, which asks whether a set of users can complete a workflow. In particular, we apply tools from parameterized complexity theory to better understand the complexities of this problem. Furthermore, we reduce the workflow satisfiability problem to SAT and apply SAT solvers to address the problem. Experiments show that our algorithm can solve instances of reasonable size efficiently. Finally, it is sometimes not enough to ensure that a workflow can be completed in normal situations. We study the resiliency problem in workflow authorization systems, which asks whether a workflow can be completed even if a number of users may be absent. We formally define three levels of resiliency in workflow systems and study computational problems related to these notions of resiliency.
---
paper_title: Quantitative Workflow Resiliency

paper_content:

A workflow is resilient when the unavailability of some users does not force to choose between a violation of the security policy or an early termination of the workflow. Although checking for the resiliency of a workflow is a well-studied problem, solutions usually only provide a binary answer to the problem, leaving a workflow designer with little help when the workflow is not resilient. We propose in this paper to provide instead a measure of quantitative resiliency, indicating how much a workflow is likely to terminate for a given security policy and a given user availability model. We define this notion by encoding the resiliency problem as a decision problem, reducing the finding of an optimal user-task assignment to that of solving a Markov Decision Process. We illustrate the flexibility of our encoding by considering different measures of resiliency, and we empirically analyse them, showing the existence of a trade-off between multiple aspects such as success rate, expected termination step and computation time, thus providing a toolbox that could help a workflow designer to improve or fix a workflow.
---
paper_title: The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency

paper_content:

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a \emph{decision} problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). ::: In this paper, we introduce the \textsc{Bi-Objective Workflow Satisfiability Problem} (\BOWSP), which enables us to solve \emph{optimization} problems related to workflows and security policies. In particular, we are able to compute a "least bad" plan when some components of the security policy may be violated. In general, \BOWSP is intractable from both the classical and parameterized complexity point of view. We prove there exists an fixed-parameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP if we restrict our attention to user-independent constraints. ::: We also present a second algorithm to compute a Pareto front which uses mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most of the instances. ::: Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of \BOWSP.
---
paper_title: Resiliency Policies in Access Control Revisited

paper_content:

Resiliency is a relatively new topic in the context of access control. Informally, it refers to the extent to which a multi-user computer system, subject to an authorization policy, is able to continue functioning if a number of authorized users are unavailable. Several interesting problems connected to resiliency were introduced by Li, Wang and Tripunitara [13], many of which were found to be intractable. In this paper, we show that these resiliency problems have unexpected connections with the workflow satisfiability problem (WSP). In particular, we show that an instance of the resiliency checking problem (RCP) may be reduced to an instance of WSP. We then demonstrate that recent advances in our understanding of WSP enable us to develop fixed-parameter tractable algorithms for RCP. Moreover, these algorithms are likely to be useful in practice, given recent experimental work demonstrating the advantages of bespoke algorithms to solve WSP. We also generalize RCP in several different ways, showing in each case how to adapt the reduction to WSP. Li et al also showed that the coexistence of resiliency policies and static separation-of-duty policies gives rise to further interesting questions. We show how our reduction of RCP to WSP may be extended to solve these problems as well and establish that they are also fixed-parameter tractable.
---
paper_title: Modelling user availability in workflow resiliency analysis

paper_content:

Workflows capture complex operational processes and include security constraints limiting which users can perform which tasks. An improper security policy may prevent certain tasks being assigned and may force a policy violation. Deciding whether a valid user-task assignment exists for a given policy is known to be extremely complex, especially when considering user unavailability (known as the resiliency problem). Therefore tools are required that allow automatic evaluation of workflow resiliency. Modelling well defined workflows is fairly straightforward, however user availability can be modelled in multiple ways for the same workflow. Correct choice of model is a complex yet necessary concern as it has a major impact on the calculated resiliency. We describe a number of user availability models and their encoding in the model checker PRISM, used to evaluate resiliency. We also show how model choice can affect resiliency computation in terms of its value, memory and CPU time.
---
paper_title: Authorization and User Failure Resiliency for WS-BPEL Business Processes

paper_content:

We investigate the problem of WS-BPEL processes resiliency in RBAC-WS-BPEL, an authorization model for WS-BPEL that supports the specification of authorizations for the execution of WS-BPEL process activities by roles and users and authorization constraints, such as separation and binding of duty. The goal of resiliency is to guarantee that even if some users becomes unavailable during the execution of a WS-BPEL process, the remaining users can still complete the execution of the process. We extend RBAC-WS-BPEL with a new type of constraints called resiliency constraints and the notion of user failure resiliency for WS-BPEL processes and propose an algorithm to determine if a WS-BPEL process is user failure resilient.
---
paper_title: Resiliency Policies in Access Control

paper_content:

We introduce the notion of resiliency policies in the context of access control systems. Such policies require an access control system to be resilient to the absence of users. An example resiliency policy requires that upon removal of any s users, there should still exist d disjoint sets of users such that the users in each set together possess certain permissions of interest. Such a policy ensures that even when emergency situations cause some users to be absent, there still exist independent teams of users that have the permissions necessary for carrying out critical tasks. The Resiliency Checking Problem determines whether an access control state satisfies a given resiliency policy. We show that the general case of the problem and several subcases are intractable (NP-hard), and identify two subcases that are solvable in linear time. For the intractable cases, we also identify the complexity class in the polynomial hierarchy to which these problems belong. We discuss the design and evaluation of an algorithm that can efficiently solve instances of nontrivial sizes that belong to the intractable cases of the problem. Furthermore, we study the consistency problem between resiliency policies and static separation of duty policies. Finally, we combine the notions of resiliency and separation of duty to introduce the resilient separation of duty policy, which is useful in situations where both fault-tolerance and fraud-prevention are desired.
---
paper_title: WRAD: Tool Support for Workflow Resiliency Analysis and Design

paper_content:

Designing efficient workflows is complex especially when considering security constraints that restrict which users can perform which tasks. This is further exacerbated when considering users could become unavailable at runtime, which is known as the workflow resiliency problem. Ideally, designers undertake resiliency analysis at the design stage so that the likely impact of security constraints on a workflow can be assessed before its execution. In this paper, we describe a new tool called Workflow Resiliency Analysis and Design (WRAD) which automatically encodes a textual description of a workflow into the probabilistic model-checker PRISM, and carries out a resiliency evaluation. WRAD also computes optimal change sets for security constraints to assure a given resiliency threshold is reached.
---
paper_title: Assisting the Deployment of Security-Sensitive Workflows by Finding Execution Scenarios

paper_content:

To support the re-use of business process models, an emerging trend in Business Process Management, it is crucial to assist customers during deployment. We study how to do this for an important class of business processes, called security-sensitive workflows, in which execution constraints on the tasks are complemented with authorization constraints (e.g., Separation of Duty) and authorization policies (constraining which users can execute which tasks). We identify the capability of solving Scenario Finding Problems (SFPs), i.e. finding concrete execution scenarios, as crucial in supporting the re-use of security-sensitive workflows. Solutions of SFPs provide evidence that the business process model can be successfully executed under the policy adopted by the customer. We present a technique for solving two SFPs and validate it on real-world business process models taken from an on-line library.
---
paper_title: Security Policy Satisfiability and Failure Resilience in Workflows

paper_content:

Security policy satisfiability and high failure resilience (i.e. survivability) are desirable properties of every system. Security issues and failure resilience are usually treated in stand alone mode and not in synergy. In this paper, we bridge this gap for workflows. We propose techniques which ensure that user-task assignment is both secure and failure resilient and present frameworks that meet different criteria of security policy, security constraints, and failure resilience.
---
paper_title: Resiliency Variance in Workflows with Choice

paper_content:

Computing a user-task assignment for a workflow coming with probabilistic user availability provides a measure of completion rate or resiliency. To a workflow designer this indicates a risk of failure, especially useful for workflows which cannot be changed due to rigid security constraints. Furthermore, resiliency can help outline a mitigation strategy which states actions that can be performed to avoid workflow failures. A workflow with choice may have many different resiliency values, one for each of its execution paths. This makes understanding failure risk and mitigation requirements much more complex. We introduce resiliency variance, a new analysis metric for workflows which indicates volatility from the resiliency average. We suggest this metric can help determine the risk taken on by implementing a given workflow with choice. For instance, high average resiliency and low variance would suggest a low risk of workflow failure.
---
paper_title: Dynamic Workflow Adjustment with Security Constraints

paper_content:

Dynamic workflow adjustment studies how to minimally adjust existing user-task assignments, when a sudden change occurs, e.g. absence of users, so that all tasks are being attended and no constraint is violated.In particular, we study two key questions: i Will the workflow still be satisfiable given a change? ii If the answer is yes, how to find a satisfying assignment with the minimum perturbation to the old system? We consider various types of changes, including absence of a user, addition of a separation-of-duty constraint, addition of a binding-of-duty constraint, and revocation of a user-to-task authorization, study their theoretical properties and formulate them into the well-studied Boolean satisfiability problem, which enables a system engineer without much technical background to solve problems by using standard satisfiability solvers. A step further, towards more efficient solutions for our specific problems, we propose customized algorithms by adapting and tailoring the state-of-art algorithms inside standard solvers. Our work would have implications for business process management, staffing, and cost planning.
---
paper_title: Valued Workflow Satisfiability Problem

paper_content:

A workflow is a collection of steps that must be executed in some specific order to achieve an objective. A computerised workflow management system may enforce authorisation policies and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of policies and constraints may mean that a workflow is unsatisfiable, in the sense that it is impossible to find an authorised user for each step in the workflow and satisfy all constraints. In this paper, we consider the problem of finding the"least bad"assignment of users to workflow steps by assigning a weight to each policy and constraint violation. To this end, we introduce a framework for associating costs with the violation of workflow policies and constraints and define the \emph{valued workflow satisfiability problem} (Valued WSP), whose solution is an assignment of steps to users of minimum cost. We establish the computational complexity of Valued WSP with user-independent constraints and show that it is fixed-parameter tractable. We then describe an algorithm for solving Valued WSP with user-independent constraints and evaluate its performance, comparing it to that of an off-the-shelf mixed integer programming package.
---
paper_title: Enhancing Workflow Systems Resiliency by Using Delegation and Priority Concepts

paper_content:

Enforcing dynamic access control constraints in workflow management systems (WFMS) is a very important requirement with regard to security issues. However, respecting those constraints may prohibit the completion of a workflow instance in the case of the lack of authorized users. Such situation is known in the literature as a WSP (Workflow Satisfiability Problem). The ability of a WFMS to use different methods to bypass a WSP situation is often seen as a resiliency property. In this work, we propose a new approach that aims to enhance the resiliency of a WFMS while meeting -at run time- the main workflow dynamic access control requirements. In fact, by using both delegation and priority concepts it is possible to find a user which is as suitable as possible to perform the current task instance with lesser security risks.
---
paper_title: The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency

paper_content:

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a \emph{decision} problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). ::: In this paper, we introduce the \textsc{Bi-Objective Workflow Satisfiability Problem} (\BOWSP), which enables us to solve \emph{optimization} problems related to workflows and security policies. In particular, we are able to compute a "least bad" plan when some components of the security policy may be violated. In general, \BOWSP is intractable from both the classical and parameterized complexity point of view. We prove there exists an fixed-parameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP if we restrict our attention to user-independent constraints. ::: We also present a second algorithm to compute a Pareto front which uses mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most of the instances. ::: Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of \BOWSP.
---
paper_title: ALPS: An Action Language for Policy Specification and Automated Safety Analysis

paper_content:

Authorization conditions of access control policies are complex and varied as they might depend, e.g., on the current time, the position of the users, selected parts of the system state, and even on the history of the computations. Several models, languages, and enforcement mechanisms have been proposed for different scenarios. Unfortunately, this complicates the verification of safety, i.e. no permission is leaked to unauthorized users. To avoid these problems, we present an intermediate language called Action Language for Policy Specification. Two desiderata drive its definition: (i) it should support as many models and policies as possible and (ii) it should be easily integrated in existing verification systems so that robust techniques (e.g., model checking or satisfiability solving) can be exploited to safety. We argue (i) by using selected examples of access control models and policies taken from the literature. For (ii), we prove some theoretical properties of the language that pave the way to the definition of automatic translations to available verification techniques.
---
paper_title: On the Complexity of Authorization in RBAC under Qualification and Security Constraints

paper_content:

In practice, assigning access permissions to users must satisfy a variety of constraints motivated by business and security requirements. Here, we focus on Role-Based Access Control (RBAC) systems, in which access permissions are assigned to roles and roles are then assigned to users. User-role assignment is subject to role-based constraints, such as mutual exclusion constraints, prerequisite constraints, and role-cardinality constraints. Also, whether a user is qualified for a role depends on whether his/her qualification satisfies the role's requirements. In other words, a role can only be assigned to a certain set of qualified users. In this paper, we study fundamental problems related to access control constraints and user-role assignment, such as determining whether there are conflicts in a set of constraints, verifying whether a user-role assignment satisfies all constraints, and how to generate a valid user-role assignment for a system configuration. Computational complexity results and/or algorithms are given for the problems we consider.
---
paper_title: Relationship-based access control: protection model and policy language

paper_content:

Social Network Systems pioneer a paradigm of access control that is distinct from traditional approaches to access control. Gates coined the term Relationship-Based Access Control (ReBAC) to refer to this paradigm. ReBAC is characterized by the explicit tracking of interpersonal relationships between users, and the expression of access control policies in terms of these relationships. This work explores what it takes to widen the applicability of ReBAC to application domains other than social computing. To this end, we formulate an archetypical ReBAC model to capture the essence of the paradigm, that is, authorization decisions are based on the relationship between the resource owner and the resource accessor in a social network maintained by the protection system. A novelty of the model is that it captures the contextual nature of relationships. We devise a policy language, based on modal logic, for composing access control policies that support delegation of trust. We use a case study in the domain of Electronic Health Records to demonstrate the utility of our model and its policy language. This work provides initial evidence to the feasibility and utility of ReBAC as a general-purpose paradigm of access control.
---
paper_title: The Authorization Policy Existence Problem

paper_content:

Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorization policies) may mean that a user is unable to fulfill her/his organizational duties because access to resources is denied. In short, there is a tension between the need to protect resources (using policies and constraints) and the availability of resources. Recent work on workflow satisfiability and resiliency in access control asks whether this tension compromises the ability of an organization to achieve its objectives. In this paper, we develop a new method of specifying constraints which subsumes much related work and allows a wider range of constraints to be specified. The use of such constraints leads naturally to a range of questions related to "policy existence", where a positive answer means that an organization's objectives can be realized. We provide an overview of our results establishing that some policy existence questions, notably for those instances that are restricted to user-independent constraints, are fixed-parameter tractable.
---
paper_title: An Auto-Delegation Mechanism for Access Control Systems

paper_content:

Delegation is a widely used and widely studied mechanism in access control systems. Delegation enables an authorized entity to nominate another entity as its authorized proxy for the purposes of access control. Existing delegation mechanisms tend to rely on manual processes initiated by end-users. We believe that systems in which the set of available, authorized entities fluctuates considerably and unpredictably over time require delegation mechanisms that can respond automatically to the absence of appropriately authorized users. To address this, we propose an auto-delegation mechanism and explore the way in which such a mechanism can be used to provide (i) controlled overriding of policy-based authorization decisions (ii) a novel type of access control mechanism based on subject-object relationships.
---
paper_title: A Framework for Expressing and Enforcing Purpose-Based Privacy Policies

paper_content:

Purpose is a key concept in privacy policies. Although some models have been proposed for enforcing purpose-based privacy policies, little has been done in defining formal semantics for purpose, and therefore an effective enforcement mechanism for such policies has remained a challenge. We have developed a framework for expressing and enforcing such policies by giving a formal definition of purpose and proposing a modal-logic language for formally expressing purpose constraints. The semantics of this language are defined over an abstract model of workflows. Based on this formal framework, we discuss some properties of purpose, show how common forms of purpose constraints can be formalized, how purpose-based constraints can be connected to more general access control policies, and how they can be enforced in a workflow-based information system by extending common access control technologies.
---
paper_title: An actor-based, application-aware access control evaluation framework

paper_content:

To date, most work regarding the formal analysis of access control schemes has focused on quantifying and comparing the expressive power of a set of schemes. Although expressive power is important, it is a property that exists in an *absolute* sense, detached from the application context within which an access control scheme will ultimately be deployed. By contrast, we formalize the access control *suitability analysis problem*, which seeks to evaluate the degree to which a set of candidate access control schemes can meet the needs of an application-specific workload. This process involves both reductions to assess whether a scheme is *capable* of implementing a workload (qualitative analysis), as well as cost analysis using ordered measures to quantify the *overheads* of using each candidate scheme to service the workload (quantitative analysis). We formalize the two-facet suitability analysis problem, which formally describes this task. We then develop a mathematical framework for this type of analysis, and evaluate this framework both formally, by quantifying its efficiency and accuracy properties, and practically, by exploring an academic program committee workload.
---
paper_title: Assisting the Deployment of Security-Sensitive Workflows by Finding Execution Scenarios

paper_content:

To support the re-use of business process models, an emerging trend in Business Process Management, it is crucial to assist customers during deployment. We study how to do this for an important class of business processes, called security-sensitive workflows, in which execution constraints on the tasks are complemented with authorization constraints (e.g., Separation of Duty) and authorization policies (constraining which users can execute which tasks). We identify the capability of solving Scenario Finding Problems (SFPs), i.e. finding concrete execution scenarios, as crucial in supporting the re-use of security-sensitive workflows. Solutions of SFPs provide evidence that the business process model can be successfully executed under the policy adopted by the customer. We present a technique for solving two SFPs and validate it on real-world business process models taken from an on-line library.
---
paper_title: Satisfiability and Feasibility in a Relationship-Based Workflow Authorization Model

paper_content:

A workflow authorization model is defined in the framework of Relationship-Based Access Control (ReBAC), in which the protection state is a social network. Armed with this model, we study a new decision problem called workflow feasibility. The goal is to ensure that the space of protection states contains at least one member in which the workflow specification can be executed to completion. We identify a sufficient condition under which feasibility can be decided by a refutation procedure that is both sound and complete. A formal specification language, based on a monotonic fragment of the Propositional Dynamic Logic (PDL), is proposed for specifying protection state spaces. The adoption of this language renders workflow feasibility NP-complete in the general case but polynomial-time decidable for an important family of workflows.
---
paper_title: Avoiding Policy-based Deadlocks in Business Processes

paper_content:

In the field of business process management, deadlocks describe a situation where a workflow execution is blocked and cannot be completed. We speak of policy-based deadlocks if such a situation is caused by unsatisfiable resource requirements due to security constraints specified as part of the business process. In this paper we propose a method to avoid policy-based deadlocks by analyzing a workflow's security constraints, determine the minimal required number of users, and provide an optimal user-activity assignment for a deadlock-free workflow execution. We will finally validate our proposed approach by applying it to a real-world scenario.
---
paper_title: A Declarative Framework for Specifying and Enforcing Purpose-aware Policies

paper_content:

Purpose is crucial for privacy protection as it makes users confident that their personal data are processed as intended. Available proposals for the specification and enforcement of purpose-aware policies are unsatisfactory for their ambiguous semantics of purposes and/or lack of support to the run-time enforcement of policies. ::: ::: In this paper, we propose a declarative framework based on a first-order temporal logic that allows us to give a precise semantics to purpose-aware policies and to reuse algorithms for the design of a run-time monitor enforcing purpose-aware policies. We also show the complexity of the generation and use of the monitor which, to the best of our knowledge, is the first such a result in literature on purpose-aware policies.
---
paper_title: Minimizing Organizational User Requirement while Meeting Security Constraints

paper_content:

Large systems are complex and typically need automatic configuration to be managed effectively. In any organization, numerous tasks have to be carried out by employees. However, due to security needs, it is not feasible to directly assign any existing task to the first available employee. In order to meet many additional security requirements, constraints such as separation of duty, cardinality and binding have to be taken into consideration. Meeting these requirements imposes extra burden on organizations, which, however, is unavoidable in order to ensure security. While a trivial way of ensuring security is to assign each user to a single task, business organizations would typically like to minimize their costs and keep staffing requirements to a minimum. To meet these contradictory goals, we define the problem of Cardinality Constrained-Mutually Exclusive Task Minimum User Problem (CMUP), which aims to find the minimum users that can carry out a set of tasks while satisfying the given security constraints. We show that the CMUP problem is equivalent to a constrained version of the weak chromatic number problem in hypergraphs, which is NP-hard. We, therefore, propose a greedy solution. Our experimental evaluation shows that the proposed algorithm is both efficient and effective.
---
paper_title: On delegation and workflow execution models

paper_content:

Workflow systems have long been of interest to computer science researchers due to their practical relevance. Supporting delegation mechanisms in workflow systems is receiving increasing research interest. In this paper, we conduct a comprehensive study of user delegation operations in computerized workflow systems. In a workflow system, the semantics of a delegation operation are largely based on three factors: the underlying workflow execution model, task type and delegation type. We describe three different workflow execution models and examine the effect of various delegation operations in each workflow execution model. We then extend our workflow execution models to examine the effect of various delegation operations in different role-based workflow execution models.
---
paper_title: Delegation and satisfiability in workflow systems

paper_content:

Supporting delegation mechanisms in workflow systems is receiving increasing interest from the research community. An important requirement of a constrained workflow is to guarantee the satisfiability of the workflow, which requires that some set of authorized users can complete a workflow. Typically, any mechanism that is used to establish the satisfiability of a workflow is based on the workflow specification and the user authorization information. The effect of a successful user delegation request is to change the user authorization information, thereby affecting the satisfiability of the workflow. Existing work on delegation in workflows does not consider the satisfiability of the workflow. In this paper, we address the satisfiability problem of workflows, while supporting user delegation mechanisms, in the context of three different workflow execution models. We consider delegation of concrete tasks, abstract tasks and roles. We present algorithms for evaluating various delegation requests in each workflow execution model.
---
paper_title: Static Detection of Collusion Attacks in ARBAC-Based Workflow Systems

paper_content:

Authorization in workflow systems is usually built on top of role-based access control (RBAC), security policies on workflows are then expressed as constraints on the users performing a set of tasks and the roles assigned to them. Unfortunately, when role administration is distributed and potentially untrusted users contribute to the role assignment process, like in the case of Administrative RBAC (ARBAC), collusions may take place to circumvent the intended workflow security policies. In a collusion attack, a set of users of a workflow system collaborates by changing the user-to-role assignment, so as to sidestep the security policies and run up to completion a workflow they could not complete otherwise. In this paper, we study the problem of collusion attacks in a formal model of workflows based on stable event structures and we define a precise notion of security against collusion. We then propose a static analysis technique based on a reduction to a role reachability problem for ARBAC, which can be used to prove or disprove security for a large class of workflow systems. We also discuss how to aggressively optimise the obtained role reachability problem to ensure its tractability. Finally, we implement our analysis in a tool, WARBAC, and we experimentally show its effectiveness on a set of publicly available examples, including a realistic case study.
---
paper_title: Bypassing Workflow Satisfiability Problem Due to Access Control Constraints

paper_content:

Most workflow management systems (WFMS) support a role-based distribution of work in order to respect both functional and static access control constraints. They often have an authorization system that deals with such constraints. However, few of them consider dynamic access control constraints as dynamic separation of duties (DSoD) and least privileges (LP).Respecting those dynamic constraints could produce a problem of completing a workflow instance also known as WSP (Workflow Satisfiability Problem) especially in the case of unavailability of authorized users as a result of holiday or sickness, overloading, emergencies, etc.
---
paper_title: Role-Based Access Control Models

paper_content:

Security administration of large systems is complex, but it can be simplified by a role-based access control approach. This article explains why RBAC is receiving renewed attention as a method of security administration and review, describes a framework of four reference models developed to better understand RBAC and categorizes different implementations, and discusses the use of RBAC to manage itself.
---
paper_title: Policy Negotiation for Co-owned Resources in Relationship-Based Access Control

paper_content:

The collaborative nature of content development has given rise to the novel problem of multiple ownership in access control, such that a shared resource is administrated simultaneously by co-owners who may have conflicting privacy preferences and/or sharing needs. Prior work has focused on the design of unsupervised conflict resolution mechanisms. Driven by the need for human consent in organizational settings, this paper explores interactive policy negotiation, an approach complementary to that of prior work. Specifically, we propose an extension of Relationship-Based Access Control (ReBAC) to support multiple ownership, in which a policy negotiation protocol is in place for co-owners to come up with and give consent to an access control policy in a structured manner. During negotiation, the draft policy is assessed by formally defined availability criteria: to the second level of the polynomial hierarchy. We devised two algorithms for verifying policy satisfiability, both employing a modern SAT solver for solving subproblems. The performance is found to be adequate for mid-sized organizations.
---
paper_title: Aegis: Automatic Enforcement of Security Policies in Workflow-driven Web Applications

paper_content:

Organizations often expose business processes and services as web applications. Improper enforcement of security policies in these applications leads to business logic vulnerabilities that are hard to find and may have dramatic security implications. Aegis is a tool to automatically synthesize run-time monitors to enforce control-flow and data-flow integrity, as well as authorization policies and constraints in web applications. The enforcement of these properties can mitigate attacks, e.g., authorization bypass and workflow violations, while allowing regulatory compliance in the form of, e.g., Separation of Duty. Aegis is capable of guaranteeing business continuity while enforcing the security policies. We evaluate Aegis on a set of real-world applications, assessing the enforcement of policies, mitigation of vulnerabilities, and performance overhead.
---

Title: A Survey on Workflow Satisfiability, Resiliency, and Related Problems

Section 1: Introduction
Description 1: Write about what workflows are, their use in business processes, and the importance of authorization policies and constraints. Introduce the concept of the Workflow Satisfiability Problem (WSP) and related issues such as resiliency and feasibility. Highlight the motivation for the survey.

Section 2: Methodology
Description 2: Describe the methodology used for the survey, including defining research questions, performing literature search, selecting relevant papers, and classifying the literature in terms of problems and solutions.

Section 3: Workflows and Authorization
Description 3: Explain the relationship between workflow models and authorization, including control-flow, data-flow, and authorization perspectives. Discuss the specification of security-sensitive workflows and various types of authorization constraints.

Section 4: Workflow Satisfiability
Description 4: Provide an overview of research on the Workflow Satisfiability Problem (WSP), categorizing it into initial works, FPT algorithms, model checking, and other approaches. Compare relevant papers based on control-flow models, authorization constraints, ordered/unordered, and execution time.

Section 5: Workflow Resiliency
Description 5: Discuss research on workflow resiliency, differentiating between static, dynamic, and quantitative resiliency. Describe how resiliency is defined and researched in workflow systems.

Section 6: Related Problems
Description 6: Explore other problems related to workflow satisfiability such as workflow feasibility, WSP with delegation, Cardinality-Constrained Minimum User Problem, and purpose-based privacy policies. Include their significance and existing solutions.

Section 7: Conclusion
Description 7: Summarize the findings from the survey, providing insights on the active state of research in the area, the variations of WSP studied, and related problems. Answer the research questions posed in the introduction and outline future research challenges.