DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2015.66

On the Workflow Satisfiability Problem with Class-independent Constraints

Authors: Jason Crampton, Andrei Gagarin, Gregory Gutin, and Mark Jones

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract

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 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 et al., J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixed-parameter tractability of WSP.

Cite as

Jason Crampton, Andrei Gagarin, Gregory Gutin, and Mark Jones. On the Workflow Satisfiability Problem with Class-independent Constraints. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 66-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{crampton_et_al:LIPIcs.IPEC.2015.66,
  author =	{Crampton, Jason and Gagarin, Andrei and Gutin, Gregory and Jones, Mark},
  title =	{{On the Workflow Satisfiability Problem with Class-independent Constraints}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{66--77},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.66},
  URN =		{urn:nbn:de:0030-drops-55727},
  doi =		{10.4230/LIPIcs.IPEC.2015.66},
  annote =	{Keywords: Workflow Satisfiability Problem; Constraint Satisfaction Problem; fixed-parameter tractability; user-independent constraints}
}

Document

DOI: 10.4230/DagRep.3.8.73

Verifiably Secure Process-Aware Information Systems (Dagstuhl Seminar 13341)

Authors: Rafael Accorsi, Jason Crampton, Michael Huth, and Stefanie Rinderle-Ma

Published in: Dagstuhl Reports, Volume 3, Issue 8 (2013)

Abstract

From August 18--23, 2013, the Dagstuhl Seminar "Verifiably Secure Process-aware Information Systems" was held in Schloss Dagstuhl -- Leibniz Center for Informatics. During this seminar, participants presented their current research and discussed open problems in the arising field of securing information systems driven by processes. The executive summary and abstracts of the talks given during the seminar are put together in this paper.

Cite as

Rafael Accorsi, Jason Crampton, Michael Huth, and Stefanie Rinderle-Ma. Verifiably Secure Process-Aware Information Systems (Dagstuhl Seminar 13341). In Dagstuhl Reports, Volume 3, Issue 8, pp. 73-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{accorsi_et_al:DagRep.3.8.73,
  author =	{Accorsi, Rafael and Crampton, Jason and Huth, Michael and Rinderle-Ma, Stefanie},
  title =	{{Verifiably Secure Process-Aware Information Systems (Dagstuhl Seminar 13341)}},
  pages =	{73--86},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{8},
  editor =	{Accorsi, Rafael and Crampton, Jason and Huth, Michael and Rinderle-Ma, Stefanie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.8.73},
  URN =		{urn:nbn:de:0030-drops-43435},
  doi =		{10.4230/DagRep.3.8.73},
  annote =	{Keywords: Business Processes, Information Security, Compliance, Risk-Aware Processes, Service Compositions}
}

Search Results

Documents authored by Crampton, Jason

On the Workflow Satisfiability Problem with Class-independent Constraints

Abstract

Cite as

Verifiably Secure Process-Aware Information Systems (Dagstuhl Seminar 13341)

Abstract

Cite as

Thanks for your feedback!

Could not send message