Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition

Zhinian ZHAI; Weixiang WANG; Yahui LU; Mingwei WU; Zhijun ZHENG; Fahong YU

doi:10.11959/j.issn.1000-0801.2016260

您当前的位置：

首页 >

文章列表页 >

Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition

research and development | 更新时间：2024-06-05

- Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition
- Telecommunications Science Vol. 32, Issue 10, Pages: 101-109(2016)
- 作者机构：
  
  1. 浙江科技学院信息与电子工程学院，浙江杭州310023
  2. 深圳大学计算机与软件学院，广东深圳518060
  2. 嘉兴学院数理与信息工程学院，浙江嘉兴314001
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2016260
  CLC： TP309
- Published Online：2016-10，
  
  Published：20 October 2016
- 稿件说明：
移动端阅览
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：

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 .

Views

507

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on dynamic allocation of network slicing resources based on OS-MBRL

Deep reinforcement learning-based resource joint optimization for millimeter-wave massive MIMO systems

Adaptive distributed cloud edge collaborative load control strategy for load management

Task urgency-based resource allocation algorithm in industrial Internet of things

Cloud edge end network resource allocation for thermostatically controlled load aggregation regulation

Related Author

YAN Jiahui

ZHONG Weixuan

DONG Ligang

JIANG Xian

WANG Guangchang

LU Lingrong

LIU Qingli

LI Xiaoyu

Related Institution

UT Starcom Telecom Co., Ltd.

Zhejiang Gongshang University

Key Laboratory of Communication and Network, Dalian University

School of Information Engineering, Dalian University

Beijing FibrLINK Communications Co., Ltd.

⁰