On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations
Open Access
- 22 October 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Privacy and Security
- Vol. 19 (3) , 1-29
Abstract
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.Keywords
Funding Information
- EPSRC (EP/K005162/1)
- Royal Society Wolfson Research Merit Award
This publication has 13 references indexed in Scilit:
- Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time HypothesisInformation Processing Letters, 2016
- Algorithms for the workflow satisfiability problem engineered for counting constraintsJournal of Combinatorial Optimization, 2015
- On the Parameterized Complexity and Kernelization of the Workflow Satisfiability ProblemACM Transactions on Information and System Security, 2013
- Satisfiability Analysis of Workflows with Control-Flow Patterns and Authorization ConstraintsIEEE Transactions on Services Computing, 2013
- Errors in graph embedding algorithmsJournal of Computer and System Sciences, 2011
- Satisfiability and Resiliency in Workflow Authorization SystemsACM Transactions on Information and System Security, 2010
- A reference monitor for workflow systems with constrained task execution2005
- The Chinese Wall security policy2003
- The role-based access control system of a European bank2001
- The specification and enforcement of authorization constraints in workflow management systemsACM Transactions on Information and System Security, 1999