TA的每日心情 | 怒
2019-11-20 15:22 |
|---|
签到天数: 2 天 [LV.1]初来乍到
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
工作流可满足性(≠，= )计数及其护完全性 ( r( a* k: E3 O" _
摘要:工作流可满足性(WS)是资源分配对访问控制(AC)策略提出的基本要求.相关工作主要围绕WS决策问题展开,通过找到一个具体的解来说明AC策略的正确性.然而为了进一步验证AC策略在资源异常情况下的合理性,统计所有解的数量将更有帮助.本文对互斥和绑定约束下的WS计数问题进行研究,通过构造从典范性#完全问题#3SAT到该问题的多项式计数归约,证明其属于#P完全问题,为其恰当地求解奠定了理论基础.
; a$ {. j2 V! S2 X3 v0 D; I关键词:工作流;访问控制;授权;约束;资源分配;可满足性6 J1 v: q& E# o) b9 I6 R
4 s0 R+ D2 a9 O# i" m1引言! p: i3 l5 g! U. G
工作流系统需要组织资源来执行一组指向特定目标的业务步骤.其关键环节是资源分配,它在工作流每次运行(称为案例)时,为每个步骤指派唯一的执行用户[1.2].为防止非法和不当访问,需通过一定的访问控制( Access Control ,AC)策略对资源分配进行制约.AC策略主要包括授权和约束.其中授权将每个步骤的候选执行资格分配给一组用户.而约束作用于利益相关的步骤,要求其执行用户之间满足某种关系.
. p4 n1 z; J; u' Z9 y! [4 d这就引出了一个有基础意义的问题:是否存在恰当的资源分配,使任何步骤均由其授权用户执行,且不违反彼此间的约束[3].此问题称为工作流可满足性( Workflow Satisfiability , WS).它关系到工作流的可行性,反映了AC策略规划是否正确.因为步骤的执行需要时间和经济成本,WS不能靠执行期发现问题随时调整的方式来保证,而须在AC规划阶段加以验证.
5 M8 C1 k; V. V自1999年文献[4]涉及相关问题以来,WS研究已经取得了一些成果[1,s~8].这些工作多以找到WS的一个解为目标(文献[4]枚举所有解),由此说明WS成立.然而,历史更久的合取范式(Conjunctive NormalForm, CNF)可满足性(Satisfiability , SAT)[9和约束可满足性(Constraint Satisfiability , CS)等经典问题,均包括决策(求一个具体的解)和计数(统计所有解的数量)两个* ?# n! `! p v6 q& u$ z t9 h
1 w. K' M- b* \: r2 h
7 Q! @8 z/ g# s$ ?" {8 u8 z$ c/ U/ E* ~8 t) X
|
|
/1 
发表于 2021-3-2 11:23
收藏
淘帖
支持！
反对！