Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition

Abstract

Workflow satisfiability（WS）concerns the issue of resource allocation under some access control policies. Counting all its solutions is advantaged to verify the robustness of a workflow to resource exceptions. The counting problem of WS with only exclusion constraints was addressed. The classic backtracking tree-decomposition method was employed to solve #WS（≠）via a polynomial-time counting reduction to a counting constraint satisfiability problem. Experiments show that, the proposed optimized algorithm declined in running time, and has well synthetical performance for workflows with low-density constraints compared to the existing #WS（≠）algorithms.

Keywords

• workflow;authorization;constraint;resource allocation;satisfiability