基于非交互式Petri网的异步程序验证模型和方法  

Model and Method for Verifying Asynchronous Program Based on Communication-free Petri Net

作　　者：吴志文 李国强[1] WU Zhi-Wen;LI Guo-Qiang(School of Software,Shanghai Jiao Tong University,Shanghai 200240,China)

机构地区：[1]上海交通大学软件学院,上海200240

出　　处：《软件学报》2023年第8期3674-3685,共12页Journal of Software

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

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

关 键 词：异步程序 非交互式Petri网 ϵ可达性 ϵ等价性 可达性 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]