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

doi:10.11959/j.issn.1000-0801.2016260

Abstract

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.

Key words: workflow, authorization, constraint, resource allocation, satisfiability

Zhinian ZHAI,Weixiang WANG,Yahui LU,Mingwei WU,Zhijun ZHENG,Fahong YU. Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition[J]. Telecommunications Science, 2016, 32(10): 101-109.

Figures/Tables 2

References 18

[1]	WANG Q , LI N . Satisfiability and resiliency in workflow authorization systems[J]. ACM Transactions on Information and System Security, 2010,13(4): 747-759.
[2]	翟治年，王刚，郑志军，等. 基于可满足性计数的（≠,=）约束工作流顽健性验证[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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	翟治年，卢亚辉，周武杰，等. 工作流可满足性（≠）计数的固定参数线性算法[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).
[9]	JEGOU P , TERRIOUX C . Hybrid backtracking bounded by tree-decomposition of constraint networks[J]. Artificial Intelligence, 2003,146(1): 43-75.
[10]	ROBERTSON N , SEYMOUR P D , GRAPH MINORS . II. Algorithmic aspects of tree-width[J]. Journal of Algorithms, 1986,7(86): 309-322.
[11]	DECHTER R , PEARL J . Tree clustering for constraint networks[J]. Artificial Intelligence, 1989,38(4): 353-366.
[12]	BULATOV A A . The complexity of the counting constraint satisfaction problem[J]. Physical Review D Particles ＆ Fields, 1993,49(10): 5349-5363.
[13]	谷文祥，朱磊，黄平，等. 可满足问题中的模型计数[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.
[14]	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.
[15]	ANGELSMARK O , JONSSON P . Improved algorithms for counting solutions in constraint satisfaction problems[J]. Lecture Notes in Computer Science, 2003(2833): 81-95.
[16]	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.
[17]	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.
[18]	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.

Metrics

Recommended 0

No Suggested Reading articles found!

序号	实例配置	参考文献[2]		参考文献[8]		BTD			算法1
序号	实例配置	时间/s	空间/MB	时间/s	空间/MB	时间/s	空间/MB	时间/s	空间/MB	W+1
1	13_70_1-33_6	0.009 35	5 458	0.422	21	0.000 320	17	0.000 239	17	2.4
2	15_41_1-33_7	0.010 7	2 729	0.922	30	0.000 242	17	0.000 203	17	2.2
3	16_40_34-66_9	0.011 7	6 822	3.39	44	0.001 89	17	0.000 841	17	3.2
4	16_74_67-100_6	0.015 0	6 821	14.5	71	0.030 4	17	0.010 4	17	2.6
5	17_43_1-100_5	0.013 4	6 822	12.7	83	0.000 742	17	0.000 426	17	2
6	18_26_34-66_15	0.014 5	6 822	8.74	116	0.003 01	17	0.001 14	17	4.6
7	18_27_1-33_8	0.009 88	0	5.68	116	0.000 267	17	0.000 228	17	2.8
8	18_45_34-66_9	0.013 7	6 821	28.2	175	0.036 8	17	0.022 7	17	3.4
9	18_46_67-100_5	0.009 34	6 821	40.4	175	0.002 01	17	0.000 810	17	2
10	21_50_67-100_6	0.065 9	6 821	601	2011	0.006 59	17	0.002 22	17	2
11	21_73_1-100_8	1.07	6 822	822	2732	360+	14	360+	14	3.6
12	23_28_34-66_13	0.014 2	6 825	679	4777	0.128	18	0.214	18	6.2
13	27_39_34-66_8	0.278	6 824	∞	8 000+	0.143	18	0.241	18	4.4
14	27_50_1-33_7	0.012 3	6 824	∞	8 000+	0.008 26	17	0.002 74	17	5.4
15	28_43_1-100_7	6.08	6 824	∞	8 000+	2.50	19	4.82	19	4.4
16	29_38_67-100_7	∞	7 057+	∞	8 000+	360+	17	360+	17	3.6
17	30_29_1-100_15	1.79	7 339	∞	8 000+	1 098+	29	1 096+	29	12.4
18	30_35_34-66_13	∞	7 745+	∞	8 000+	1 444+	24	1 444+	24	9.8
19	30_73_67-100_8	∞	7 884+	∞	8 000+	1 133+	22	1 131+	22	5.4
20	30_74_1-33_7	0.002 47	7 388	∞	8 000+	0.017 0	17	0.006 52	17	3.2

算法1	ω	5	10	15	20	25	30	35
\|S\|=8,\|U\|=4	W+1	2	2	2.3	2	2.7	3.3	3.3
	\|X\|	1.3	2.7	5.7	4	7.3	10	10.3
	时间/s	0.000 338	0.000 211	0.000 314	0.000 249	0.000 601	0.000 738	0.001 43
\|S\|=12,\|U\|=5	W+1	2	2.3	2.7	3	4	6	5.7
	\|X\|	4.7	6.7	10.3	11.3	17.7	24.7	26.3
	时间/s	0.000 898	0.000 532	0.001 09	0.003 57	0.011 1	0.767	0.291
\|S\|=14,\|U\|=8	W+1	2	3.3	6	4.7	5	6.3	6.7
	\|X\|	3.3	13	15.3	21	19.3	30	32.3
	时间/s	0.000 937	0.034 6	14.4	175.0	32.4	1 009.5	19 772.0

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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 18

Related Articles 15

Metrics

Recommended 0

[1]	Yu KANG, Yaqiong LIU, Tongyu ZHAO, Guochu SHOU. A survey on AI algorithms applied in communication and computation in Internet of vehicles [J]. Telecommunications Science, 2023, 39(1): 1-19.
[2]	Han WANG, Lei DIAO, Mengling WANG, Xin RONG, Jiamin LI, Xiaohu YOU. A survey of key issues of URLLC in industrial internet of things [J]. Telecommunications Science, 2022, 38(Z1): 77-92.
[3]	Zhimin HE, Yuzhe LIN, Yujie CHENG, Shi YAN. Downlink wireless resource allocation method of V2X based on wireless sensing assistance [J]. Telecommunications Science, 2022, 38(9): 60-70.
[4]	Lushan ZOU, Xiaowen HUANG, Jingmin YANG, Yifeng ZHENG, Guanglin ZHANG, Wenjie ZHANG. Review on resources allocation and pricing methods in mobile edge computing [J]. Telecommunications Science, 2022, 38(3): 113-132.
[5]	Yun SHENG, Chen XU, Guangyuan ZHENG. Task offloading and resource allocation in NOMA-based ultra-dense MEC networks [J]. Telecommunications Science, 2022, 38(2): 35-46.
[6]	Cheng DING, Jinrong CHEN, Xiaodong CAO, Yi WANG. Quality of service based hierarchical resource allocation algorithm [J]. Telecommunications Science, 2022, 38(1): 102-111.
[7]	Yunhe YU, Jun SUN. Research on resource allocation algorithm of centralized and distributed Q-learning in machine communication [J]. Telecommunications Science, 2021, 37(11): 41-50.
[8]	Liuqing WU,Xiaorong ZHU. Joint optimization algorithm for task offloading resource allocation based on edge-end collaboration [J]. Telecommunications Science, 2020, 36(3): 42-52.
[9]	Kai LI,Wei LIU,Guiyang LUO,Jinglin LI. Customer-centered mobile network intelligent operation approach [J]. Telecommunications Science, 2020, 36(2): 101-108.
[10]	Xian ZHANG,Xueyan CAO,Binghong LIU,Yuan AI,Chenxi LIU. Smart fog radio access networks for 6G:architecture and key technologies [J]. Telecommunications Science, 2020, 36(1): 3-10.
[11]	Xiaoan BAO,Yundi CAO,Na ZHANG,Junyan QIAN,Jianwen CAO. Multi-objective cloud workflow scheduling algorithm based on grid variance [J]. Telecommunications Science, 2019, 35(2): 1-13.
[12]	Haiyu JIA,Jia CHEN,Mingxin WANG. Survey on network function virtualization in RAN [J]. Telecommunications Science, 2019, 35(1): 97-112.
[13]	Bing YI,Yongli CHEN,Ruixue ZHAO. Resource allocation scheme for D2D communication in mmWave 5G networks [J]. Telecommunications Science, 2019, 35(1): 138-146.
[14]	Xuehua LI,Chen SHEN,Yuanyuan YAO. Performance analysis of 60 GHz pulse multiuser communication system based on cross-layer strategy [J]. Telecommunications Science, 2018, 34(9): 70-77.
[15]	Weichun GE,Huanhuan LUO,Guiping ZHOU,Yingjie WANG,Xiangyu KONG,Luyao GUAN,Chuang SONG,Min ZHANG,Qing LI. Resource management scheme of power fiber to the home network slicing [J]. Telecommunications Science, 2018, 34(9): 153-159.