Page 38 - 《软件学报》2021年第6期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(6):1612−1630 [doi: 10.13328/j.cnki.jos.006240] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
Petri 网的反向展开及其在程序数据竞争检测的应用

1,2
郝宗寅 , 鲁法明 1
1
(山东科技大学 计算机科学与工程学院,山东 青岛 266590)
2 (厦门大学 信息学院,福建 厦门 361005)
通讯作者: 鲁法明, E-mail: fm_lu@163.com

摘 要: 展开技术借助分支进程可在一定程度上缓解Petri网性质分析中的状态爆炸问题.但展开网中仍然包含了
系统的所有状态信息.某些应用问题仅需对系统特定状态的可覆盖性进行判定,以此为目标,有望缩减网系统展开的
规模.为此,针对安全 Petri 网的可覆盖性判定问题提出了一种目标导向的反向展开算法,结合启发式技术缩减展开
的规模,以此提高目标标识可覆盖性判定的效率.进而,将反向展开算法应用于并发程序的形式化验证,将并发程序
的数据竞争检测问题转换为 Petri 网特定标识的可覆盖性判定问题.实验对比了正向展开与反向展开在 Petri 网可覆
盖性判定问题上的效率,结果表明:当 Petri 网展开的正向分支较多时,反向展开相比正向展开具有更高的可覆盖性
判定效率.最后,对影响反向展开效率的关键因素做了分析与总结.
关键词: Petri 网;可覆盖性判定;反向展开;启发式优化;数据竞争检测
中图法分类号: TP311

中文引用格式: 郝宗寅,鲁法明.Petri 网的反向展开及其在程序数据竞争检测的应用.软件学报,2021,32(6):1612−1630.
http://www. jos.org.cn/1000-9825/6240.htm
英文引用格式: Hao ZY, Lu FM. Reverse unfolding of Petri nets and its application in program data race detection. Ruan Jian
Xue Bao/Journal of Software, 2021,32(6):1612−1630 (in Chinese). http://www.jos.org.cn/1000-9825/6240.htm

Reverse Unfolding of Petri Nets and its Application in Program Data Race Detection
1,2
HAO Zong-Yin , LU Fa-Ming 1
1 (College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, China)
2 (School of Informatics, Xiamen University, Xiamen 361005, China)

Abstract: Unfolding technology can partially alleviate the state explosion problem in Petri net through branching processes. However,
an unfolding still contains all states of a system. Some practical problems only need to determine the coverability of a specific state,
which is expected to reduce the scale of unfolding net. This study proposes a target-oriented reverse unfolding algorithm for the
coverability problem of 1-safe Petri nets, which combines heuristic technology to reduce the scale of unfolding nets, thereby improving
the efficiency of coverability determination. Furthermore, the reverse unfolding technology is applied to the formal verification of

∗ 基金项目: 国家自然科学基金(61602279, 61472229); 国家重点研发计划(2016YFC0801406); 山东省泰山学者工程专项基金
(ts20190936); 山东省高等学校青创科技支持计划(2019KJN024); 山东省博士后创新专项基金(201603056); 鲁渝科技协作计划
(cstc2020jscx-lyjsAX0008); 国家海洋局海洋遥测工程技术研究中心开放基金(2018002); 山东科技大学领军人才与优秀科研创新团
队项目(2015TDJH102)
Foundation item: National Natural Science Foundation of China (61602279,61472229); National Key Research and Development
Plan (2016YFC0801406); Taishan Scholars Program of Shandong Province (ts20190936); Excellent Youth Innovation Team Foundation of
Shandong Higher School (2019KJN024); Postdoctoral Innovation Foundation of Shandong Province (201603056); Shandong-Chongqing
Science and Technology Cooperation Plan (cstc2020jscx-lyjsAX0008); Open Foundation of First Institute of Oceanography, MNR
(2018002); Shandong University of Science and Technology Research Fund (2015TDJH102)
本文由“形式化方法与应用”专题特约编辑田聪教授推荐.
收稿时间: 2020-08-31; 修改时间: 2020-10-26; 采用时间: 2020-12-19; jos 在线出版时间: 2021-02-07