Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition - Zhinian ZHAI; Weixiang WANG; Yahui LU; Mingwei WU; Zhijun ZHENG; Fahong YU (Dianxin kexue)
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.