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