工作流可满足性（≠）计数的固定参数线性算法

摘要

工作流可满足性（Workflow Satisfiability，WS）（≠）判定给定授权和互斥约束下的资源分配是否存在，是工作流访问控制中的基本问题。目前可以通过寻找一个具体的解来完成该判定，相应问题称为 WS（≠）决策，现有的最低时间复杂度为 O *（2｜S｜（｜C｜＋｜U｜2））（S ，C，U 分别为步骤集、约束集、用户集）。然而，仅 WS（≠）有解时，工作流授权规划未必合理，对资源异常可能缺乏鲁棒性。若能统计所有解的个数，不仅可判定 WS（≠）有解与否，还能为授权规划提供重要的参考，相应的问题称为 WS（≠）计数。该文提出 WS（≠）计数问题，并根据 Bjorclund 关于集合划分权重和的结果证明其时间复杂度为 O *（2｜S｜｜U｜），即其以｜S｜为固定参数，关于｜U｜线性时间可解，由此降低了当前的 WS（≠）判定时间复杂度。进而，该文提出了一种快速的动态规划递推式，并全面优化 Bjorclund 方法的空间利用方式，使该文算法的实际性能随之提高，而 O *时间复杂度不变。随机合成数据集上的实验表明，该文最终的计数算法相对前述决策算法，执行时间平均降低了93％，峰值空间平均降低了87％，而求解规模提高了44％。%Workflow Satisfiability (≠)is an elementary problem in workflow access control, determining whether or not there exists a resource allocation which satisfies given authorizations and exclusion constraints.In the existing research,a concrete solution is found to show the satisfiability,the problem of which is named as WS (≠)decision with the best-known time complexity O *(2|S| (|C|+|U|2 ))(S ,C,U denote the sets of steps,constraints and users respectively).However,in a merely satisfiable workflow,the authorization planning might be unreasonable,with low robustness to resource exception.If the number of all solutions is counted, not only the satisfiability can be determined,but also the authorization planning can be referred to it.In this paper,the counting problem of WS(≠)is proposed.Based on Bjorclund’s result of sum weighted partitions,its time complexity is proved to be O *(2|S||U|),that means the problem is solvable within the linear time of|U|with|S|as the fixed parameter.Thus our counting WS(≠) algorithm can determine WS(≠)in lower time complexity.Further,a fast dynamic programming recursion formula is proposed in this paper,and the space utilization of Bjorclund’s method is optimized roundly.As a result,the practical performance of our algorithm is improved with the same O * time complexity.Experiments on randomly created dataset show that:compared to the aforementioned decision algorithm,our final counting algorithm achieves averagely 93% decrease in executing time,87 % decrease in space usage,while the solvable input scale is increased by 44%.