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

• 学术论文 • 上一篇    下一篇

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

翟治年1, 卢亚辉2, 余法红3, 周武杰1, 向坚1, 吴茗蔚1   

  1. 1. 浙江科技学院信息与电子工程学院, 浙江杭州 310023;
    2. 深圳大学计算机学院, 广东深圳 518060;
    3. 嘉兴学院数理与信息学院, 浙江嘉兴 314001
  • 收稿日期:2015-04-20 修回日期:2015-07-08 出版日期:2017-03-25 发布日期: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-nian1, LU Ya-hui2, YU Fa-hong3, ZHOU Wu-jie1, XIANG Jian1, WU Ming-wei1   

  1. 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

摘要:

工作流可满足性(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

中图分类号: