Covering sharing trees: a compact data structure for parameterized verification

The control state reachability problem is decidable for well-structured infinite-state systems like (Lossy) Petri Nets, Vector Addition Systems, and broadcast protocols. An abstract algorithm that solves the problem is the backward reachability algorithm of [1, 21 ]. The algorithm computes the closure of the predecessor operator with respect to a given upward-closed set of target states. When applied to this class of verification problems, symbolic model checkers based on constraints like [7, 26 ] suffer from the state explosion problem.In order to tackle this problem, in [13] we introduced a new data structure, called covering sharing trees, to represent in a compact way collections of infinite sets of system configurations. In this paper, we will study the theoretical complexity of the operations over covering sharing trees needed in symbolic model checking. We will also discuss several optimizations that can be used when dealing with Petri Nets. Among them, in [14] we introduced a new heuristic rule based on structural properties of Petri Nets that can be used to efficiently prune the search during symbolic backward exploration. The combination of these techniques allowed us to turn the abstract algorithm of [1, 21 ] into a practical method. We have evaluated the method on several finite-state and infinite-state examples taken from the literature [2, 18 , 20 , 30 ]. In this paper, we will compare the results we obtained in our experiments with those obtained using other finite and infinite-state verification tools.     

Oris: a tool for modeling, verification and evaluation of real-time systems

Oris is a tool for qualitative verification and quantitative evaluation of reactive timed systems, which supports modeling and analysis of various classes of timed extensions of Petri Nets. As most characterizing features, Oris implements symbolic state space analysis of preemptive Time Petri Nets, which enable schedulability analysis of real-time systems running under priority preemptive scheduling; and stochastic Time Petri Nets, which enable an integrated approach to qualitative verification and quantitative evaluation. In this paper, we present the current version of the tool and we illustrate its application to two different case studies in the areas of qualitative verification and quantitative evaluation, respectively.     

An Assertional Language for the Verification of Systems Parametric in Several Dimensions: (Preliminary Results)

We propose a rich assertional language to be used for symbolic verification of systems with several parametric dimensions. Our approach combines notions coming from different fields. We use Colored Petri Nets [16] to describe nets of processes carrying structured data. We combine concepts coming from constraint programming [23] and multiset rewriting [19] to finitely and concisely represent transitions and infinite collection of states of Colored Petri Nets. Finally, we incorporate these concepts in the verification technique based on backward reachability and upward-closed sets of [1,12]. We obtain a procedure that can be used as an automatic support for attacking parameterized verification problems. We apply these ideas to verify safety properties of a parameterized mutual exclusion algorithm. A number of open questions arise from our preliminary experiments, finding an adequate counterpart of our framework in the world of automated deduction being among the more interesting ones.     

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

展开技术借助分支进程可在一定程度上缓解Petri网性质分析中的状态爆炸问题.但展开网中仍然包含了系统的所有状态信息.某些应用问题仅需对系统特定状态的可覆盖性进行判定,以此为目标,有望缩减网系统展开的规模.为此,针对安全Petri网的可覆盖性判定问题提出了一种目标导向的反向展开算法,结合启发式技术缩减展开的规模,以此提高...     

基于Petri网的网上股票交易系统模拟与验证

给出了基于时序Petri网下的网上证券交易系统,其模型过于复杂。由于Petri网本身很强的模拟能力,本文用P/T_系统,模拟了证券交易所的网上证券交易系统,进而用S-不变等方法对其进行了验证。     

延迟时间Petri网的验证分析

延迟时间Petri网（Delay Time Petri Nets，DTPN）是一类重要的时间扩展Petri网系统，解决了其他时间扩展Petri网（如时间Petri网）在保存时间约束时所面临的困难。可调度验证的目的是验证工作流模型时间约束的合理性，对流程实例的时间可达性进行仿真。提出一种基于DTPN的时间约束工作流验证分析方法。给出了DTPN的相关定义，并结合工作流控制结构描述了变迁可触发的时间条件；提出了DTPN触发点的概念以及基于此的验证分析算法；简要分析了DTPN的特性。DTPN的研究丰富完善了现有时间Petri网体系，具有积极的意义。     

Computer aided verification of Lamport's fast mutual exclusionalgorithm using colored Petri nets and occurrence graphs with symmetries

In this paper, we present a computer tool for verification of distributed systems. As an example, we establish the correctness of Lamport's Fast Mutual Exclusion Algorithm. The tool implements the method of occurrence graphs with symmetries (OS-graphs) for Colored Petri Nets (CP-nets). The basic idea in the approach is to exploit the symmetries inherent in many distributed systems to construct a condensed state space. We demonstrate a significant increase in the number of states which can be analyzed. The paper is to a large extent self-contained and does not assume any prior knowledge of CP-nets (or any other kinds of Petri Nets) or OS-graphs. CP-nets and OS-graphs are not our invention. Our contribution is the development of the tool and verification of the example, demonstrating how the method of occurrence graphs with symmetries can be put into practice     

时间约束工作流的可调度性分析

提出一种时间约束工作流的可调度性分析方法。针对时间约束Petri网（Timing Constraint Petri Nets,TCPN）为普通Petri网无法建模多参与资源的不足,给出了扩展的时间约束Petri网（w-TCPN）的定义;结合w-TCPN的拓扑结构,从模型和实例两个层次,给出了w-TCPN变迁可调度的判定定理;提出了时间约束的调整策略。w-TCPN的研究使得时间约束工作流的建模和可调度性分析更加合理。     

Improving state class constructions for CTL* model checking of time Petri nets

The state space explosion is still one of the most challenging problems in formal verification using enumerative techniques. The challenge is even greater for real time systems whose state spaces are generally infinite due to time density. To use enumerative techniques with these systems, their state spaces need to be contracted into finite structures that preserve properties of interest. We propose in this paper an efficient approach to construct a contraction of the time Petri net model state space, which preserves its CTL* properties.     

Feature Nets: behavioural modelling of software product lines

Software product lines (SPLs) are diverse systems that are developed using a dual engineering process: (a) family engineering defines the commonality and variability among all members of the SPL, and (b) application engineering derives specific products based on the common foundation combined with a variable selection of features. The number of derivable products in an SPL can thus be exponential in the number of features. This inherent complexity poses two main challenges when it comes to modelling: firstly, the formalism used for modelling SPLs needs to be modular and scalable. Secondly, it should ensure that all products behave correctly by providing the ability to analyse and verify complex models efficiently. In this paper, we propose to integrate an established modelling formalism (Petri nets) with the domain of software product line engineering. To this end, we extend Petri nets to Feature Nets. While Petri nets provide a framework for formally modelling and verifying single software systems, Feature Nets offer the same sort of benefits for software product lines. We show how SPLs can be modelled in an incremental, modular fashion using Feature Nets, provide a Feature Nets variant that supports modelling dynamic SPLs, and propose an analysis method for SPL modelled as Feature Nets. By facilitating the construction of a single model that includes the various behaviours exhibited by the products in an SPL, we make a significant step towards efficient and practical quality assurance methods for software product lines.     

Implementing Coloured Petri Nets Using a Functional Programming Language

Coloured Petri Nets (CPNs) are a graphically oriented modelling language for concurrent systems based on Petri Nets and the functional programming language Standard ML. Petri Nets provide the primitives for modelling concurrency and synchronisation. Standard ML provides the primitives for modelling data manipulation and for creating compact and parameterisable CPN models.Functional programming and Standard ML have played a major role in the development of CPNs and the CPN computer tools supporting modelling, simulation, verification, and performance analysis of concurrent systems. At the modelling language level, Standard ML has extended Petri Nets with the practical expressiveness required for modelling systems of the size and complexity found in typical industrial projects. At the implementation level, Standard ML has been used to implement the formal semantics of CPNs that provide the theoretical foundation of the CPN computer tools.This paper provides an overview of how functional programming and Standard ML are applied in the CPN modelling language and the supporting computer tools. We give a detailed presentation of the key algorithms and techniques used for implementing the formal semantics of CPNs, and we survey a number of case studies where CPNs have been used for the design and analysis of systems. We also demonstrate how the use of a Standard ML programming environment has allowed Petri Nets to be used for the implementation of systems.     

Reduction of constraints for controller synthesis based on safe Petri Nets

In this paper, we present an efficient method based on safe Petri Nets to construct a controller. A set of linear constraints allows forbidding the reachability of specific states. The number of these so-called forbidden states, and consequently the number of constraints, are large and lead to a large number of control places. A systematic method to reduce the size and the number of constraints for safe Petri Nets is offered. By using a method based on Petri Net invariants, maximal permissive controllers are determined.     

一种随机着色Petri网及模型的性能分析

针对随机Petri网（SPN）在系统性能分析时,其状态空间随着系统规模增大而指数性增长,造成求解稳定状态概率的复杂性的不足,提出了一种随机着色Petri网（SCPN）。分析了它的有界性和可达性,证明了它同构于一个一维连续时间的马尔可夫链;同时,也分析了随机着色Petri网用于建模和系统性能定量分析的方法。     

区间速率连续Petri网可达稳态必要性分析

文章就区间速率连续Petri网可达稳态的必要性问题进行研究,在介绍区间速率连续Petri网及其使能、引发语义的基础上首先给出区间速率连续Petri网在指定标识下具有稳态的条件;其次通过提出区间速率连续Petri网一种标识向量等价类划分方法从而给出分析区间速率连续Petri网可达稳态必要性的有效方法;最后给出一个应用例子,考察区间速率连续Petri网的可达稳态问题。     

一类Petri网系统的活性

Petri网是一种用来研究具有异步、并发特征的离散事件系统的合适的工具，当用Petri网来模拟一个实际系统时，关心的问题之一就是要确定这个Petri网模型是否具有一些所期望的特生，如活性、有界性等，这些特性均是系统的重要动态行为，该文基于文献[1]给出了Petri网的一子类，即弱化非自控网（Weak Extended Non SelfControlling Nets,简称WENSeC网），该类网覆盖了扩展自由选择网和扩展非自控网，文中提出了并证明了WENSeC网系统活性的的充分必要条件满足死锁－陷阱性质，同时对WENSeC网的一子类，通过转化方法，证明了该类结构有界网的结构活判定算法可借用扩非自控网的有关结果也是多项式时间算法。     

基于加权FPN的聚驱综合调整系统决策分析

模糊Petri网(Fuzzy Petri Nets, FPN)是一种适合于描述异步并发事件的计算机系统模型,可以有效地对并行和并发系统进行形式化验证和决策分析.针对聚驱综合调整系统知识具有不确定性和模糊性的特点,给出了基于加权模糊产生式规则的加权FPN决策模型.在此模型的基础上,给出了决策推理过程的形式化推理算法.算法考虑了推理过程中的众多约束条件,将复杂的推理过程采用矩阵运算来实现,充分利用了FPN的并行处理能力,使决策推理过程更加简单和快速.并以压裂方式调整为例,说明了该模型具有直观、表达能力强和易于推理等优点,具有较强的实用价值.     

Petri网及其扩展研究

Petri网是一种应用非常广泛的建模工具。首先给出了基本Petri网的概念,在此基础上对多种Petri网进行了广泛的研究,包括时间因素Petri网、有色Petri网、面向对象Petri网、模糊Petri网及受控Petri网,并针对每种Petri网的特点和应用范围进行了讨论,提出了Petri网当前发展的方向和急需解决的热点问题。     

基于DTPN的时间Petri网的组件级化简规则

时间Petrl网(TPNs)是实时系统时间特性常用的描述和验证的Petri网模型.组件级化简方法是TPN模型常用的分析方法,在保持外部可观察时间特性的前提下,将组件TPN模型化简成一个很简单的TPN模型.然而它却失去了组件内部的性质,如冲突和并发等性质.文中引人延迟时间Petri网(DTPN),通过组件TPN模型向DTPN模型转化,使化简后模型既保持外部可观察时间特性,又保持组件内部的冲突和并发等性质.为了分析化简后的DTPN模型,文中还提出了一种新的DT-PN调度分析方法.最后通过对一个C2系统的组件TPN模型的分析实例,验证该方法的有效性.     

Reverse Unfolding of Petri Nets and its Application in Program Data Race Detection

The unfolding technique can partially alleviate the state explosion in Petri nets through branching processes. However, all states of a system are still contained in its unfolding net. To deal with some practical problems, only the coverability determination of a specific state is needed. In view of this, reducing the scale of the unfolding net is feasible. This study proposes a target-oriented reverse unfolding algorithm for the coverability determination of 1-safe Petri nets, which combines a heuristic technique to reduce the scale of unfolding nets, thereby improving the efficiency of coverability determination. Furthermore, the reverse unfolding is applied to the formal verification of concurrent programs, and their data race detection is converted into the coverability determination of a specific state in 1-safe Petri nets. The experiment compares the efficiency between forward nfolding and reverse unfolding in the coverability determination of a Petri net. The results show that when the Petri net has more forward branches than backward branches, reverse unfolding is more efficient than forward unfolding. Finally, the key factors influencing the efficiency of reverse unfolding are analyzed.     

一种新型Petri Net:双层变迁定时Petri Net

嵌入式系统的设计尤其是复杂嵌入式系统的设计，需要对系统的稳定性、可靠性等进行分析，进而对系统进行设计优化。这首先需要对系统建立适当的模型进行仿真分析，该文在深入分析现有Petri Net的基础上，构建了一种适合于嵌入式系统建模的新型Petri Net。