微信服务号

微信订阅号

2025年4月5日 7:21 星期六
首页 > 过刊浏览>2023年第34卷第8期 >3674-3685. DOI:10.13328/j.cnki.jos.006615
PDF HTML阅读 XML下载 导出引用 引用提醒
基于非交互式Petri网的异步程序验证模型和方法
作者:
作者简介:

吴志文(1998-),男,硕士生,主要研究领域为形式化验证,程序分析与验证;李国强(1979-),男,博士,副教授,CCF高级会员,主要研究领域为形式化方法,程序语言理论

通讯作者:

李国强,E-mail:li.g@sjtu.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61872232,61732013)


Model and Method for Verifying Asynchronous Program Based on Communication-free Petri Net
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [20]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    异步程序使用异步非阻塞调用方式来实现程序的并发, 被广泛应用于并行与分布式系统中. 验证异步程序复杂性很高, 无论是安全性还是活性均达到EXPSPACE难. 提出一个异步程序的程序模型系统, 并在其上定义两个异步程序上的问题: $ \epsilon $等价性问题和$ \epsilon $可达性问题. 通过将3-CNF-SAT规约到这两个问题, 再将其规约至非交互式Petri网的可达性证明两个问题是NP完备的. 案例表明, 这两个问题可以解决异步程序上一系列的程序验证问题.

    Abstract:

    Asynchronous programs utilize asynchronous non-blocking calls to achieve program concurrency, and they are widely applied in parallel and distributed systems. However, it is very complex to verify asynchronous programs, and the difficulty can be ranked as EXPSPACE in terms of both safety and liveness. This study proposes a program model of asynchronous programs and defines two problems of asynchronous programs, namely, ∈-equivalence and ∈-reachability. In addition, the two problems can be proved to be NP-complete by reducing the 3-CNF-SAT to the problems and making them further reduced to the reachability of the communication-free Petri net. The case shows that the two problems can solve the verification problems of asynchronous programs.

    参考文献
    [1] Ramalingam G. Context-sensitive synchronization-sensitive analysis is undecidable. ACM Transactions on Programming Languages and Systems, 2000, 22(2): 416–430. [doi: 10.1145/349214.349241]
    [2] Leroux J, Praveen M, Sutre G. Hyper-ackermannian bounds for pushdown vector addition systems. In: Proc. of the Joint Meeting of the 23rd EACSL Annual Conf. on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symp. on Logic in Computer Science (LICS). Vienna: ACM, 2014. 1–10.
    [3] Leroux J, Sutre G, Totzke P. On the coverability problem for pushdown vector addition systems in one dimension. In: Proc. of the 42nd Int’l Colloquium on Automata, Languages, and Programming. Kyoto: Springer, 2015. 324–336.
    [4] D’Osualdo E, Kochems J, Ong CHL. Automatic verification of Erlang-style concurrency. In: Proc. of the 20th Int’l Static Analysis Symp. Seattle: Springer, 2013. 454–476.
    [5] Sen K, Viswanathan M. Model checking multithreaded programs with asynchronous atomic methods. In: Proc. of the 18th Int’l Conf. on Computer Aided Verification. Seattle: Springer, 2006. 300–314.
    [6] Petri CA. Kommunikation mit automaten [Ph.D. Thesis]. Bonn: University of Bonn, 1962.
    [7] Ganty P, Majumdar R. Algorithmic verification of asynchronous programs. ACM Transactions on Programming Languages and Systems, 2012, 34(1): 6. [doi: 10.1145/2160910.2160915]
    [8] Atig MF, Bouajjani A, Kumar KN, Saivasan P. Verification of asynchronous programs with nested locks. In: Proc. of the 37th IARCS Annual Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum Fuer Informatik, 2018. 11.
    [9] Emmi M, Ganty P, Majumdar R, Rosa-Velardo F. Analysis of asynchronous programs with event-based synchronization. In: Proc. of the 24th European Symp. on Programming Languages and Systems. London: Springer, 2015. 535–559.
    [10] Lakos C. The consistent use of names and polymorphism in the definition of object Petri nets. In: Proc. of the 17th Int’l Conf. on Application and Theory of Petri Nets. Osaka: Springer, 1996. 380–399.
    [11] Valk R. Petri nets as token objects. In: Proc. of the 19th Int’l Conf. on Application and Theory of Petri Nets. Lisbon: Springer, 1998. 1–24.
    [12] Christensen S, Hansen ND. Coloured Petri nets extended with channels for synchronous communication. In: Proc. of the 15th Int’l Conf. on Application and Theory of Petri Nets. Zaragoza: Springer, 1994. 159–178.
    [13] Czerwiński W, Fröschle S, Lasota S. Partially-commutative context-free processes. In: Proc. of the 20th Int’l Conf. on Concurrency Theory. Bologna: Springer, 2009. 259–273.
    [14] 杨启哲, 李国强. 基于通信Petri网的异步通信程序验证模型. 软件学报, 2017, 28(4): 804-818. http://www.jos.org.cn/1000-9825/5191.htm
    Yang QZ, Li GQ. Model on asynchronous communication program verification based on communicating Petri nets. Ruan Jian Xue Bao/Journal of Software, 2017, 28(4): 804-818 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5191.htm
    [15] Esparza J. Petri nets, commutative context-free grammars, and basic parallel processes. Fundamenta Informaticae, 1997, 31(1): 13–25. [doi: 10.3233/FI-1997-3112]
    [16] Huynh DT. Commutative grammars: The complexity of uniform word problems. Information and Control, 1983, 57(1): 21–39. [doi: 10.1016/S0019-9958(83)80022-9]
    [17] Esparza J, Ganty P, Kiefer S, Luttenberger M. Parikh's theorem: A simple and direct automaton construction. Information Processing Letters, 2011, 111(12): 614–619. [doi: 10.1016/j.ipl.2011.03.019]
    [18] 丁如江, 李国强. 非交互式Petri网可覆盖性验证的高效实现. 软件学报, 2019, 30(7): 1939–1952. http://www.jos.org.cn/1000-9825/5750.htm
    Ding RJ, Li GQ. Efficient implementation of coverability verification on communication-free Petri net. Ruan Jian Xue Bao/Journal of Software, 2019, 30(7): 1939–1952 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5750.htm
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

吴志文,李国强.基于非交互式Petri网的异步程序验证模型和方法.软件学报,2023,34(8):3674-3685

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-09-03
  • 最后修改日期:2021-10-14
  • 在线发布日期: 2022-03-24
  • 出版日期: 2023-08-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19789601位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号