工作流可满足决策(≠)的完备独立树分解回溯法  

Backtracking Tree-Decomposition Method with Complete Independence for Workflow Satisfiability Decision(≠)

作　　者：翟治年[1] 卢亚辉[2] 余法红[3] 高慧敏[4] ZHAI Zhinian;LU Yahui;YU Fahong;GAO Huimin(School of Information and Electronic Engineering,Zhejiang University of Science and Technology,Hangzhou 310023,China;School of Computer and Software,Shenzhen University,Shenzhen,Guangdong 518060,China;College of Mathematics Physics and Information Engineering,Jiaxing University,Jiaxing,Zhejiang 314001,China;College of Mechanical and Electrical Engineering,Jiaxing University,Jiaxing,Zhejiang 314001,China)

机构地区：[1]浙江科技学院信息与电子工程学院,杭州310023 [2]深圳大学计算机与软件学院,广东深圳518060 [3]嘉兴学院数理与信息工程学院,浙江嘉兴314001 [4]嘉兴学院机电工程学院,浙江嘉兴314001

出　　处：《计算机科学与探索》2018年第12期2021-2032,共12页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.61572163;浙江省自然科学基金Nos.LY15F030021;LY16F020027;浙江省教育厅科研项目No.Y201737476;教育部人文社会科学研究项目No.17YJC630109;浙江省哲学社会科学规划项目No.15NDJC186YB~~

摘　　要：互斥约束工作流可满足决策是关系到安全业务可行性的重要问题,而其现有算法的理论和实测性能,或时间和空间代价严重失衡。根据其低约束密度特征,利用Jegou的树分解回溯方法来解决上述问题。因该方法仅根据约束不相关性得出子问题独立性,不能保证部分解之间的兼容性,从变量不相交和约束不相关两个角度建立了完备的子问题独立性及其部分解缓存原理,设计了相应的算法,并通过交错归纳的方法证明其正确性。分析表明,该算法时间复杂度为O*(|S|~3×d^(W+1)),一定条件下低于目前最优的O*(2^(|S|)(|X|+|U|~2))时间,其中S、d、W分别为步骤集、步骤授权列表的最大规模、树分解宽度。实验表明,该算法在低密度约束下,时间性能显著超过现有理论或实际性能最优的算法,且未付出很大空间代价。Exclusion constrained workflow satisfiability decision is an important problem that is concerned with the feasibility of secure business.Its representative algorithms so far are seriously out-of-balance between the theoretical and practical performance,or time and space cost.According to its low density of constraints,Jegou's backtracking tree decomposition method is used to address the above issue.However,its concept of sub-problem independence is deduced only from the property of constraint irrelevance and has no guarantee to the compatibility between partial solutions.A complete sub-problem independence with a caching principle for partial solutions is set up from the view of both variable non-intersection and constraint irrelevance.A corresponding algorithm is designed and its correctness is proven via a method of alternating induction.Its time complexity is O*(|S|^3×d^W+1)which is conditionally lower than the most optimal time O*(2^|S|(|X|+|U|^2))so far,where S,d,W are the set of steps,the maximum scale of authorization lists for steps and the tree-decomposition width.Experiments show that,under the condition of low constraint density,the algorithm has remarkable time efficiency than the algorithms with the best theoretical or practical performance,while no quite much space cost is paid.

关 键 词：工作流 访问控制 资源分配 约束满足 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]