基于回溯树分解的互斥约束工作流可满足性计数

翟治年; 王巍橡; 卢亚辉; 吴茗蔚; 郑志军; 余法红

doi:10.11959/j.issn.1000-0801.2016260

您当前的位置：

首页 >

文章列表页 >

基于回溯树分解的互斥约束工作流可满足性计数

研究与开发 | 更新时间：2024-06-05

- 基于回溯树分解的互斥约束工作流可满足性计数
- Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition
- 电信科学 2016年32卷第10期页码：101-109
- 作者机构：
  
  1. 浙江科技学院信息与电子工程学院，浙江杭州310023
  2. 深圳大学计算机与软件学院，广东深圳518060
  2. 嘉兴学院数理与信息工程学院，浙江嘉兴314001
- 作者简介：
  
  [ "翟治年（1977-），男，博士，浙江科技学院信息与电子工程学院讲师，主要从事访问控制、服务组合与工作流调度方面的研究工作。" ]
  [ "王巍橡（1995-），男，浙江科技学院信息与电子工程学院本科在读。" ]
  [ "卢亚辉（1976-），男，博士，深圳大学计算机与软件学院副教授，主要从事工作流理论与过程挖掘研究工作。" ]
  [ "吴茗蔚（1977-），女，博士，浙江科技学院信息与电子工程学院副教授，主要从事无线通信技术研究工作。" ]
  [ "郑志军（1967-），男，博士，浙江科技学院信息与电子工程学院副教授，主要从事智能优化与并行计算研究工作。" ]
  [ "余法红（1977-），男，博士，嘉兴学院数理与信息工程学院讲师，主要从事智能计算、复杂网络与隐私保护研究工作。" ]
- 基金信息：
  
  浙江省教育厅科研基金资助项目;Foundation Items: Zhejiang Provincial Education Department Research Foundation of China(Y201533771);浙江省自然科学基金资助项目;Zhejiang Provincial Natural Science Foundation of China(LY16F020027);国家自然科学基金资助项目;The National Natural Science Foundation of China(61302112)
- DOI：10.11959/j.issn.1000-0801.2016260
  中图分类号： TP309
- 网络出版日期：2016-10，
  
  纸质出版日期：2016-10-20
- 稿件说明：
移动端阅览
翟治年, 王巍橡, 卢亚辉, 等. 基于回溯树分解的互斥约束工作流可满足性计数[J]. 电信科学, 2016,32(10):101-109.

Zhinian ZHAI, Weixiang WANG, Yahui LU, et al. Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition[J]. Telecommunications science, 2016, 32(10): 101-109.
翟治年, 王巍橡, 卢亚辉, 等. 基于回溯树分解的互斥约束工作流可满足性计数[J]. 电信科学, 2016,32(10):101-109. DOI： 10.11959/j.issn.1000-0801.2016260.

Zhinian ZHAI, Weixiang WANG, Yahui LU, et al. Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition[J]. Telecommunications science, 2016, 32(10): 101-109. DOI： 10.11959/j.issn.1000-0801.2016260.

摘要

工作流可满足性（WS）研究一定访问控制策略下的资源分配问题，其计数问题有利于判断工作流对资源异常情况的顽健性。本文研究互斥约束下的WS计数问题，通过多项式计数归约为约束可满足性计数问题，将经典的回溯树分解方法用于#WS（≠）求解。实验表明，改进后的算法降低了执行时间，相对于现有#WS（≠）算法，提出的算法对低密度约束下的工作流具有一定的综合性能优势。

Abstract

Workflow satisfiability（WS）concerns the issue of resource allocation under some access control policies. Counting all its solutions is advantaged to verify the robustness of a workflow to resource exceptions. The counting problem of WS with only exclusion constraints was addressed. The classic backtracking tree-decomposition method was employed to solve #WS（≠）via a polynomial-time counting reduction to a counting constraint satisfiability problem. Experiments show that

the proposed optimized algorithm declined in running time

and has well synthetical performance for workflows with low-density constraints compared to the existing #WS（≠）algorithms.

关键词

Keywords

references

WANG Q , LI N . Satisfiability and resiliency in workflow authorization systems [J ] . ACM Transactions on Information and System Security , 2010 , 13 ( 4 ): 747 - 759 .

翟治年，王刚，郑志军，等 . 基于可满足性计数的（≠,=）约束工作流顽健性验证 [J ] . 电子学报， 2015 , 43 ( 11 ): 2298 - 2234 .

ZHAI Z N , WANG G , ZHENG Z J , et al . Verification of（≠,=） constrained workflow robustness based on satisfiability counting [J ] . Acta Electronica , 2015 , 43 ( 11 ): 2298 - 2234 .

AHMED T , TRIPATHI A R . Security policies in distributed CSCW and workflow systems [J ] . IEEE Transactions on Systems, Man,and Cybernetics Part A:Systems and Humans , 2010 , 40 ( 6 ): 1220 - 1231 .

BERTINO E , FERRARI E , ALTURI V . The specification and enforcement of authorization constraints in workflow management systems [J ] . ACM Transactions on Information System Security , 1999 , 2 ( 1 ): 65 - 104 .

CRAMPTON J , KHAMBHAMMETTU H . Delegation and satisfiability in workflow systems [C ] // 13th ACM Symposium on Access Control Models and Technologies , June 11 , 2008 , Colorado, USA , New York : ACM Press , 2008 : 31 - 40 .

BASIN D , BURRI S J , KARJOTH G . Obstruction-free authorization enforcement: aligning security and business objectives [C ] // The 24th ComputerSecurityFoundationsSymposium , June 27 , 2011 , Cernay, France . New Jersey : IEEE Press , 2011 : 99 - 113 .

CRAMPTON J , GUTIN G , YEO A . On the parameterized complexi and Kernelization of the workflow satisfiability problem [J ] . AC Transactions on Information and System Security , 2012 , 16 ( 1 ): 1518 - 1527 .

翟治年，卢亚辉，周武杰，等 . 工作流可满足性（≠）计数的固定参数线性算法 [J ] . 计算机学报， 2016 ( 39 ).

ZHAI Z N , LU Y H , ZHOU W J , et al . Fixed-parameter linear algorithm for counting workflow satisfiability （≠） [J ] . Chinese Journal of Computers , 2016 ( 39 ).

JEGOU P , TERRIOUX C . Hybrid backtracking bounded by tree-decomposition of constraint networks [J ] . Artificial Intelligence , 2003 , 146 ( 1 ): 43 - 75 .

ROBERTSON N , SEYMOUR P D , GRAPH MINORS . II. Algorithmic aspects of tree-width [J ] . Journal of Algorithms , 1986 , 7 ( 86 ): 309 - 322 .

DECHTER R , PEARL J . Tree clustering for constraint networks [J ] . Artificial Intelligence , 1989 , 38 ( 4 ): 353 - 366 .

BULATOV A A . The complexity of the counting constraint satisfaction problem [J ] . Physical Review D Particles ＆ Fields , 1993 , 49 ( 10 ): 5349 - 5363 .

谷文祥，朱磊，黄平，等 . 可满足问题中的模型计数 [J ] . 智能系统学报， 2012 , 7 ( 1 ): 33 - 39 .

GU W X , ZHU L , HUANG P , et al . The model counting of a satisfiability problem [J ] . CAAI Transactions on Intelligent Systems , 2012 , 7 ( 1 ): 33 - 39 .

ANGEL SMARK O , JONSSON P , LINUSSON S , et al . Determining the number of solutions to binary CSP instances [C ] // 8th International Conference on Principles and Practice of Constraint Programming , September 9 , 2002 , New York, USA . New Jersey : IEEE Press , 2002 : 181 - 186 .

ANGELSMARK O , JONSSON P . Improved algorithms for counting solutions in constraint satisfaction problems [J ] . Lecture Notes in Computer Science , 2003 ( 2833 ): 81 - 95 .

DAHLLÖF V , JONSSON P , WAHLSTRÖM M . Counting models for 2SAT and 3SAT formulae [J ] . Theoretical Computer Science , 2005 , 332 ( 1 - 3 ): 265 - 291 .

MARCIAL-ROMERO J R , LUNA G D I , HERNÁNDEZ J A , et al . A parametric polynomial deterministic algorithm for #2SAT [M ] . Advances in Artificial Intelligence and Soft Computing . New York : Springer International Publishing , 2015 .

FAVIER A , GIVRY S D , JÉGOU P . Exploiting problem structure for solution counting [C ] // International Conference on Principles and Practice of Constraint Programming , September 20 , 2009 , Lisbon, Portugal . New Jersey : IEEE Press , 2009 : 335 - 343 .

浏览量

507

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于OS-MBRL的网络切片资源动态分配方法研究

基于深度强化学习的毫米波大规模MIMO系统资源联合优化

面向多元可控负荷调控的云边协同负荷资源分配策略

工业物联网中基于任务紧急程度的资源分配算法

面向温控负荷聚合调控的云边端网络资源分配