On the parameterized complexity of the workflow satisfiability problem
On the parameterized complexity of the workflow satisfiability problem
复制标题
工作流可满足性问题的参数化复杂度
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Anders Yeo
中科院分区：
文献类型：
--
作者：
J. Crampton;G. Gutin;Anders Yeo
工作流规范定义了一组步骤以及必须执行这些步骤的顺序。安全要求可能会对允许哪些用户组执行这些步骤的子集施加约束。一个工作流规范被称为是可满足的，如果存在一个分配的用户的工作流步骤，满足所有的约束。一个算法，用于确定是否存在这样的分配是很重要的，无论是作为一个静态分析工具的工作流规范，并为工作流管理系统的运行时参考监视器的建设。找到这样的分配通常是一个困难的问题，但Wang和Li在2010年使用参数化复杂性理论的工作表明，在合理的假设下，有效的算法存在于工作流规范中。本文改进了工作流可满足性问题的复杂性界。我们还概括和扩展的工作流规范中可能定义的约束类型，并证明了可满足性问题仍然是固定参数听话的约束。
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.
工作流可满足性问题的迭代计划构建
影响因子：
5
作者：
Cohen David
通讯作者：
Cohen David
DOI：
10.1145/2487222.2487226
发表时间：
2012-05
期刊：
ACM Trans. Inf. Syst. Secur.
影响因子：
--
作者：
J. Crampton;G. Gutin;Anders Yeo
通讯作者：
J. Crampton;G. Gutin;Anders Yeo