工作流可满足性(≠,=)计数及其#P完全性

doi:10.3969/j.issn.0372-2112.2017.03.015

电子学报 ›› 2017, Vol. 45 ›› Issue (3): 605-611.DOI: 10.3969/j.issn.0372-2112.2017.03.015

工作流可满足性(≠,=)计数及其#P完全性

翟治年¹, 卢亚辉², 余法红³, 周武杰¹, 向坚¹, 吴茗蔚¹

1. 浙江科技学院信息与电子工程学院, 浙江杭州 310023;
2. 深圳大学计算机学院, 广东深圳 518060;
3. 嘉兴学院数理与信息学院, 浙江嘉兴 314001

收稿日期:2015-04-20 修回日期:2015-07-08 出版日期:2017-03-25
- 通讯作者:
- 余法红
- 作者简介:
- 翟治年 男,1977年5月生,河北张家口人.2000年、2003年和2012年分别在合肥工业大学土木建筑工程学院和华南理工大学计算机科学与工程学院取得工学学士、硕士和博士学位.曾在广东北电通信设备有限公司从事C++开发.现为浙江科技学院信息与电子工程学院讲师,主要从事访问控制、服务组合与工作流调度方面的研究.E-mail:zhaizhinian@gmail.com;卢亚辉 男,1976年5月生,陕西宝鸡人.1997年、2003年和2008年分别在南京大学、中科院遥感所和清华大学获理学学士、理学硕士和工学博士学位.现为深圳大学计算机与软件学院副教授,主要从事工作流、系统安全、Petri网、Pi演算等方面的研究.E-mail:luyahui@szu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61502429，No.61302112）; 浙江省自然科学基金 (No.LQ15F020010，No.LY16F020027）; 浙江省教育厅科研项目 (No.Y201533771）; 钱江人才计划 (No.QJD1402023）

Counting Workflow Satisfiability(≠,=) and Its #P Completeness

ZHAI Zhi-nian¹, LU Ya-hui², YU Fa-hong³, ZHOU Wu-jie¹, XIANG Jian¹, WU Ming-wei¹

1. School of Information and Electronic Engineering, Zhejiang University of Science and Technology, Hangzhou, Zhejiang 310023, China;
2. School of Computer, Shenzhen University, Shenzhen, Guangdong 518060, China;
3. College of Mathematics Physics and Information, Jiaxing University, Jiaxing, Zhejiang 314001, China

Received:2015-04-20 Revised:2015-07-08 Online:2017-03-25 Published:2017-03-25

摘要/Abstract

摘要：

工作流可满足性（WS）是资源分配对访问控制（AC）策略提出的基本要求.相关工作主要围绕WS决策问题展开，通过找到一个具体的解来说明AC策略的正确性.然而为了进一步验证AC策略在资源异常情况下的合理性，统计所有解的数量将更有帮助.本文对互斥和绑定约束下的WS计数问题进行研究，通过构造从典范性#P完全问题#3SAT到该问题的多项式计数归约，证明其属于#P完全问题，为其恰当地求解奠定了理论基础.

关键词: 工作流, 访问控制, 授权, 约束, 资源分配, 可满足性

Abstract:

Workflow satisfiability(WS)is an essential claim to access control(AC)policies from the view of resource allocation.So far,the related researches are concentrated on the decision problem of WS,which finds a single solution to show the correctness of an AC policy.However,to further verify its rationality under resource exception,and to count all the solutions will be more useful.In this paper,the counting problem of WS with exclusion and binding constraints is addressed.The problem is proved to be #P complete by constructing a polynomial time counting reduction from the well-known #P complete problem of #3SAT to it,and then gets a theoretical basis to be solved appropriately.

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

中图分类号:

TP309

翟治年, 卢亚辉, 余法红, 周武杰, 向坚, 吴茗蔚. 工作流可满足性(≠,=)计数及其#P完全性[J]. 电子学报, 2017, 45(3): 605-611.

ZHAI Zhi-nian, LU Ya-hui, YU Fa-hong, ZHOU Wu-jie, XIANG Jian, WU Ming-wei. Counting Workflow Satisfiability(≠,=) and Its #P Completeness[J]. Acta Electronica Sinica, 2017, 45(3): 605-611.

参考文献

[1] AALST W,HEE K.Workflow Management:Models,Methods and Systems[M].Massachusetts,USA:MIT Press, 2004.
[2] 翟治年,卢亚辉,奚建清,等.面向企业级流程的职责分离框架及其冗余分析[J].电子学报,2013,41(10):2087-2093. ZHAI Z,LU Y,XI J,et al.Enterprise-level business process oriented framework for separation of duties with its redundancy analysis[J].Acta Electronica Sinica,2013,41(10):2087-2093.(in Chinese)
[3] WANG Q,Li N.Satisfiability and resiliency in workflow authorization systems[J].ACM Transactions on Information and System Security,2010,13(4):1-35.
[4] BERTINO E,FERRARI E,ATLURI 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,GUTIN G,YEO A.On the parameterized complexity and kernelization of the workflow satisfiability problem[J].ACM Transactions on Information and System Security,2013,16(1):1-31.
[6] ATLURI V,BERTINO E,FERRARI E,et al.Supporting delegation in secure workflow management systems[A].17th Annual Conference on Data and Application of Security[C].Berlin,GER:Springer,2003.190-202.
[7] CRAMPTON J,KHAMBHAMMETTU H.Delegation and satisfiability in workflow systems[A].13th ACM Symposium on Access Control Models and Technologies[C].NY,USA:ACM,2008.31-40.
[8] BASIN D,BURRI S,KARJOTH G.Obstruction-free authorization enforcement:aligning security and business objectives[A].Computer Security Foundations Symposium[C].WA,USA:IEEE CS,2011.99-113.
[9] 赵相福,欧阳丹彤.使用SAT求解器产生所有极小冲突部件集[J].电子学报,2009,37(4):804-810. ZHAO X,OUYANG D.Deriving all minimal conflict sets using satisfiability algorithms[J].Acta Electronica Sinica,2009,37(4):804-810.(in Chinese)
[10] VALIANT L.The complexity of computing the permanent[J].Theoretical Computer Science,1979,8(2):189-201.
[11] VALIANT L.The complexity of enumeration and reliability problems[J].SIAM Journal on Computing,1979,8(3):410-421.
[12] 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.
[13] BULATOV A.The complexity of the counting constraint satisfaction problem[J].Journal of the ACM,2013,60(345):1-29.
[14] VADHAN S P.The Complexity of Counting[D].MA,USA:Harvard University,1995.

[1]	宋佰霖, 许华, 齐子森, 饶宁, 彭翔. 一种基于深度强化学习的协同通信干扰决策算法[J]. 电子学报, 2022, 50(6): 1301-1309.
[2]	赵夫群, 耿国华. 基于特征区域划分的文物碎片自动匹配算法[J]. 电子学报, 2022, 50(6): 1436-1443.
[3]	张宏伟, 张小虎, 曹勇. 贝叶斯序贯重要性积分滤波器[J]. 电子学报, 2022, 50(4): 823-831.
[4]	宋政育, 郝媛媛, 孙昕. 低轨卫星协作边缘计算任务迁移和资源分配算法[J]. 电子学报, 2022, 50(3): 567-573.
[5]	李世银, 鲁姗妹, 马帅, 张凡, 徐子涵, 王洪梅, 李宗艳, 熊海良. 有限字符输入DCO-OFDMA系统的资源分配算法研究[J]. 电子学报, 2022, 50(3): 574-584.
[6]	刘焕淋, 胡俊岭, 任杰, 胡会霞, 唐畅, 陈浩楠. 基于光路负载均衡和邻域匹配的串扰感知资源分配方法[J]. 电子学报, 2022, 50(11): 2746-2753.
[7]	赵雄文, 张钰, 秦鹏, 王晓晴, 耿绥燕, 宋俊元, 刘瑶, 李思峰. 空天地一体化无线光通信网络关键技术及其发展趋势[J]. 电子学报, 2022, 50(1): 1-17.
[8]	张建民, 黎铁军, 马柯帆, 肖立权. 一种加速FPGA布线的不可满足子式求解算法[J]. 电子学报, 2021, 49(6): 1210-1216.
[9]	罗智勇, 朱梓豪, 谢志强, 孙广路. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
[10]	崔玉亚, 张德干, 张婷, 杨鹏, 朱浩丽. 一种面向移动边缘计算的多用户细粒度任务卸载调度方法[J]. 电子学报, 2021, 49(11): 2202-2207.
[11]	刘冰洁, 毕晓君. 一种基于角度信息的约束高维多目标进化算法[J]. 电子学报, 2021, 49(11): 2208-2216.
[12]	陈思光, 陈佳民, 赵传信. 基于深度强化学习的云边协同计算迁移研究[J]. 电子学报, 2021, 49(1): 157-166.
[13]	吴立强, 韩益亮, 杨晓元, 张敏情, 杨凯. 基于理想格的鲁棒门限代理重加密方案[J]. 电子学报, 2020, 48(9): 1786-1794.
[14]	刘剑锋, 孙力帆, 普杰信, 何子述, 王燕玲. 基于刚性约束的双移动机器人协同定位[J]. 电子学报, 2020, 48(9): 1777-1785.
[15]	张广驰, 曾志超, 崔苗, 武庆庆, 林凡, 刘怡俊. 无线供电混合多址接入网络的最优能效资源分配研究[J]. 电子学报, 2020, 48(4): 697-705.

工作流可满足性(≠,=)计数及其#P完全性

Counting Workflow Satisfiability(≠,=) and Its #P Completeness

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics