工作流可满足性(≠，= )计数及其护完全性

mutougeda

工作流可满足性(≠，= )计数及其护完全性

摘要:工作流可满足性(WS)是资源分配对访问控制(AC)策略提出的基本要求.相关工作主要围绕WS决策问题展开,通过找到一个具体的解来说明AC策略的正确性.然而为了进一步验证AC策略在资源异常情况下的合理性,统计所有解的数量将更有帮助.本文对互斥和绑定约束下的WS计数问题进行研究,通过构造从典范性#完全问题#3SAT到该问题的多项式计数归约,证明其属于#P完全问题,为其恰当地求解奠定了理论基础.
- k5 Q4 W, W+ A, ~0 w关键词:工作流;访问控制;授权;约束;资源分配;可满足性

1引言
% C# x% L+ U% |5 O工作流系统需要组织资源来执行一组指向特定目标的业务步骤.其关键环节是资源分配,它在工作流每次运行(称为案例)时,为每个步骤指派唯一的执行用户[1.2].为防止非法和不当访问,需通过一定的访问控制( Access Control ,AC)策略对资源分配进行制约.AC策略主要包括授权和约束.其中授权将每个步骤的候选执行资格分配给一组用户.而约束作用于利益相关的步骤,要求其执行用户之间满足某种关系.
这就引出了一个有基础意义的问题:是否存在恰当的资源分配,使任何步骤均由其授权用户执行,且不违反彼此间的约束[3].此问题称为工作流可满足性( Workflow Satisfiability , WS).它关系到工作流的可行性,反映了AC策略规划是否正确.因为步骤的执行需要时间和经济成本,WS不能靠执行期发现问题随时调整的方式来保证,而须在AC规划阶段加以验证.
自1999年文献[4]涉及相关问题以来,WS研究已经取得了一些成果[1,s~8].这些工作多以找到WS的一个解为目标(文献[4]枚举所有解),由此说明WS成立.然而,历史更久的合取范式(Conjunctive NormalForm, CNF)可满足性(Satisfiability , SAT)[9和约束可满足性(Constraint Satisfiability , CS)等经典问题,均包括决策(求一个具体的解)和计数(统计所有解的数量)两个

游客，如果您要查看本帖隐藏内容请回复

" {0 q+ {* t( c9 }

NNNei256

工作流可满足性(≠，= )计数及其护完全性