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