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

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

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space $\mathcal{O} ({\mathit{ef}}(k, W){\mathit{poly}}(n) )$ , where ef(k,W) is some super-polynomial function and poly(n) is some polynomial in the size of the input n. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness.     

Structure and behavior preservation by Petri-net-based refinements in system design

A refinement is a transformation for replacing a simple entity of a system with its functional and operational details. In general, the refined system may become incorrect even if the original system is correct because some of its original properties may have been lost or some unneeded properties may have been created. For systems specified in pure ordinary Petri nets, this paper proposes the conditions imposed on several types of refinement under which the following 19 properties will be preserved: state machine, marked graph, free choice net, asymmetric choice net, conservativeness, structural boundedness, consistence, repetitiveness, rank, cluster, rank-cluster-property, coverability by minimal state-machines, siphon, trap, cyclomatic complexity, longest path, boundedness, liveness and reversibility. Such results have significance in three aspects: (1) It releases the designer's burden for having to provide different methods for individual properties. (2) In the literature, refinements have been shown preserving several equivalence relations and behavioral properties. Our results show that they also preserve many structural properties. (3) It greatly enlarges the scope of applicability of refinements because they can now be applied on systems that satisfy more properties than just liveness and boundedness.     

非交互式Petri网可覆盖性验证的高效实现

近年来,基于Petri网可覆盖性的验证技术已经成功地应用于并发程序的验证与分析中.然而,由于Petri网的可覆盖性问题复杂度太高,这类技术在应用时有较大的局限性,对于输入规模较大的问题常常会出现超时的情况.而Petri网的一个子系统——非交互式Petri网,其可覆盖性和可达性复杂性均是NP完备的,同时表达力又可以作为某类并发程序的验证模型.设计并实现了可以高效验证非交互式Petri网可覆盖性的工具CFPCV.采用基于约束的方法,从模型中提取约束,并使用Z3 SMT求解器对约束进行求解,同时,通过子网可标记方法对候选解进行验证,从而保证每组解都是正确解.通过实验分析了该工具的成功率、迭代次数以及运行效率,发现该算法不仅验证成功率高,而且性能非常优异.     

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.     

Diagnosability of Petri nets with observation graphs

This paper addresses the problem of diagnosability for dynamic discrete event systems modeled with bounded or unbounded Petri nets that are deadlock-free and monitored with sensor configurations with marking and event measurements. The proposed method gives necessary and sufficient conditions for diagnosability. It is based on the transformation of the coverability graph into an observation graph that encodes all observation sequences of measured markings and events with respect to the sensor configuration. This graph also encodes all sequences of transitions that may fire from any reachable marking of the Petri net. Diagnosability is determined by analyzing the paths and circuits in the observation graph. The method is illustrated with several examples of bounded or unbounded Petri nets.     

基于Petri网超媒体模型的分析与比较

超媒体建模研究是当前一个重要研究方向。基于Petri网理论的模型是对有向图模型的改进,与其他模型比较,能够更好地刻画超媒体系统。原因如下:Petri网是一个二部有向图,适合于说明超媒体的链接机制;Petri网是一种天然的具有并行执行语义的自动机,模型可以自然地表达超媒体系统中的动态执行语义;Petri网能够说明各种顺序、并发和同步活动,满足描述多媒体表现的需要;利用Petri网的图形特性和严格的数学基础,人们可以检查和分析超媒体中的潜在问题。该文着重对四个典型的基于Petri网的超媒体模型:MHPN、HCPN、MORENA和HTSPN模型进行分析和比较。     

Observability of place/transition nets

We discuss the problem of estimating the marking of a place/transition (P/T) net based on event observation. We assume that the net structure is known while the initial marking is totally or partially unknown. We give algorithms to compute a marking estimate that is a lower bound of the actual marking. The special structure of Petri nets allows us to use a simple linear algebraic formalism for estimate and error computation. The error between actual marking and estimate is a monotonically nonincreasing function of the observed word length, and words that lead to error are said to be complete. We define several observability properties related to the existence of complete words, and show how they can be proved. To prove some of them, we also introduce a useful tool, the observer coverability graph, i.e., the usual coverability graph of a P/T net augmented with a vector that keeps track of the estimation error on each place of the net. Finally, we show how the estimate generated by the observer may be used to design a state feedback controller for forbidden marking specifications.     

Modeling and Analyzing of Workflow Authorization Management

The administration of authorizations in an organization is a complex task. To ensure that tasks constituting the business processes are performed by authorized users, a proper authorization mechanism is required. Alturi and Huang have proposed a workflow authorization model and presented a color-timed Petri net based representation of their model. In this paper, we extend their model by using the colored Petri net formalism to model authorization management, security constraints like separation of duties, and role hierarchy in an elegant way to establish an integrated authorization management model. One of the great advantages of using Petri net formalism for system modeling is its strong mathematical foundation and the availability of a rich set of analysis techniques. Therefore, we will show in this paper the use of linear algebraic technique to analyze the reachable authorization states, and coverability graph to calculate the valid execution chains against the colored Petri net based workflow authorization management model.     

Model-Checking with Coverability Graphs

We show that several formulas of a temporal logic can be verified using the coverability graph of the underlying system. Of course, the procedure is not capable of verifying all formulae, since already the reachability problem for (unbounded) Petri nets is computationally hard. Thus, the procedure returns true, false, or unknown for a query. The formulae that can be verified cover most of the well known standard properties which have been listed in the context of coverability graph analysis so far.     

Parallel computation of continuous Petri nets based on hypergraph partitioning

Continuous Petri net can be used for performance analysis or static analysis. The analysis is based on solving the associated ordinary differential equations. This paper presents a method to parallel compute these differential equations. We first map the Petri net to a hypergraph, and then partition the hypergraph to minimize interprocessor communication while maintaining a good load balance; Based on the partition result, we divide the differential equations into several blocks; Finally, we design a parallel computing algorithm to compute these equations. Software hMETIS is used to partition the hypergraph, and software SUNDIALS is used to support the parallel computing of differential equations. Gas station problem and dining philosopher problem have been used to demonstrate the feasibility, accuracy, and scalability of our method.     

Sizing of an industrial plant under tight time constraints using two complementary approaches: (max,+) algebra and computer simulation

In this article (max,+) spectral theory results are applied in order to solve the problem of sizing in a real-time constrained plant. The process to control is a discrete event dynamic system without conflict. Therefore, it can be modeled by a timed event graph, a class of Petri net, whose behavior can be described with linear equations in the (max,+) algebra. First the sizing of the process without constraint is solved. Then we propose to design a simulation model of the plant to validate the sizing of the process.     

Commodification of accelerations for the Karp and Miller Construction

Karp and Miller’s algorithm is based on an exploration of the reachability tree of a Petri net where, the sequences of transitions with positive incidence are accelerated. The tree nodes of Karp and Miller are labeled with ω-markings representing (potentially infinite) coverability sets. This set of ω-markings allows us to decide several properties of the Petri net, such as whether a marking is coverable or whether the reachability set is finite. The edges of the Karp and Miller tree are labeled by transitions but the associated semantic is unclear which yields to a complex proof of the algorithm correctness. In this work we introduce three concepts: abstraction, acceleration and exploration sequence. In particular, we generalize the definition of transitions to ω-transitions in order to represent accelerations by such transitions. The notion of abstraction makes it possible to greatly simplify the proof of the correctness. On the other hand, for an additional cost in memory, which we theoretically evaluated, we propose an “accelerated” variant of the Karp and Miller algorithm with an expected gain in execution time. Based on a similar idea we have accelerated (and made complete) the minimal coverability graph construction, implemented it in a tool and performed numerous promising benchmarks issued from realistic case studies and from a random generator of Petri nets.

     

Automating the Conversion of Colored Petri Nets with Qualitative Tokens Into Colored Petri Nets with Quantitative Tokens

The authors describe an algorithm for conversion of colored Petri nets with qualitative tokens into a colored Petri net with quantitative tokens preserving boundedness, mutual exclusion, and liveness properties. This conversion allows the invariance method to be applied to colored Petri nets, which uses the Truncated Set of Solutions finding algorithm for Petri net state equations expressed through systems of linear homogenous Diophantine equations. To show the algorithm’s efficiency, it is applied to the colored Petri net that models the operation of a grid system. Equivalence of net models is tested by constructing and analyzing equal finite-state machine.     

Scheduling and control of real-time systems based on a token player approach

Petri nets are a powerful formalism for the specification and verification of concurrent systems, such as sequential systems and manufacturing systems. To deal with real-time systems whose time issues become essential, different extensions of Petri nets with time have been proposed in the literature. In this paper, a new scheduling and control technique for real-time systems modeled by ordinary P-time Petri nets is proposed. Its goal is to provide a scheduling for a particular firing sequence, without any violation of timing constraints ensuring that no deadline is missed. It is based on the firing instant notion and it consists in determining an inequality system generated for a possible evolution (in terms of a feasible firing sequence for the untimed underlying Petri net) of the model. This system can be used to check reachability problems as well as evaluating the performances of the model considered and determining the associated control for a definite functioning mode and it introduces partial order on the execution of particular events.     

并发操作系统中基于有色Petri网的死锁检测与避免

1.引言系统的并发性与资源的共享性是并发操作系统的主要特征,其目的是最大限度地提高计算机资源的利用率。死锁是并发操作系统必须解决的一个重要问题。人们试图用不同的方法来解决死锁问题。如Dijkstra提出的有名的死锁避免的“银行家算法”,Coffman等人给出的死锁检测算法。 Petri网模型作为模拟与分析并发、异步、分布式系统的一种有效工具,已被用于解决操作系统中的许多问题。如进程通讯中的生产者/消费者问题、哲学家用餐问题,资源竞     

基于Petri网的一种时序分析方法

Ｐｅｔｒｉ网由于有强大的建模能力和成熟的理论支持,被广泛应用于各种系统的建模．本文通过把Ｐｅｔｒｉ网转换成转移系统,利用转移系统和Ｋｒｉｐｋｅ结构给出时序逻辑语义的解释,从而建立了一种在Ｐｅｔｒｉ网上进行时序分析的方法．这种方法是根据不动点理论,用模型检查验证公式正确性．通过对Ａｄａ程序会合性质进行模型检查,验证了这种方法的有效性．     

SAT-Solving the Coverability Problem for Petri Nets

Net unfoldings have attracted great attention as a powerful technique for combating state space explosion in model checking, and have been applied to verification of finite state systems including 1-safe (finite) Petri nets and synchronous products of finite transition systems. Given that net unfoldings represent the state space in a distributed, implicit manner the verification algorithm is necessarily a two step process: generation of the unfolding and reasoning about it. In his seminal work McMillan (K.L. McMillan, Symbolic Model Checking. Kluwer Academic Publishers, 1993) showed that deadlock detection on unfoldings of 1-safe Petri nets is NP-complete. Since the deadlock problem on Petri nets is PSPACE-hard it is generally accepted that the two step process will yield savings (in time and space) provided the unfoldings are small.In this paper we show how unfoldings can be extended to the context of infinite-state systems. More precisely, we show how unfoldings can be constructed to represent sets of backward reachable states of unbounded Petri nets in a symbolic fashion. Furthermore, based on unfoldings, we show how to solve the coverability problem for unbounded Petri nets using a SAT-solver. Our experiments show that the use of unfoldings, in spite of the two-step process for solving coverability, has better time and space characteristics compared to a traditional reachability based implementation that considers all interleavings for solving the coverability problem.     

基于Petri网的CSP并发系统验证技术研究

通信顺序进程(CSP)和Petri网是两种重要的并发系统建模工具。CSP语言具有高度抽象性,可有效刻画并发进程之间的各种相互作用,但在物理结构的描述与验证分析方面显得不足。Petri 网是一种形式化、图形化的并发系统建模和分析工具,侧重于系统的物理结构描述和性质分析。结合两者优点,首先利用CSP描述待验证的并发系统,然后将其转化为Petri网来分析系统的动态行为特性,最后利用性质分析工具TINA对系统性质进行分析和验证。实验结果表明,传统的CSP进程性质验证工具不能验证CSP进程的安全性,但其转化为Petri网后可有效地分析出导致安全性不能满足的危险因素,从而扩大了CSP描述的并发系统可验证性质的范围。     

Petri网的TT型子网精细化操作性质分析及其应用

针对企业用加工厂或车间加工某种产品等这一类业务处理问题，提出了用Petri网精细化操作解决问题的方案。定义了一种TT-型子网，用这种子网分别对Petri网系统中的某些变迁进行细化，得到更细致、更精确的Petri网系统。研究了Petri网精细化操作的动态性质保持问题，给出这种精细化操作保持活性、有界性、可回复性和公平性的充要条件；本文的结果可为Petri网系统静态和动态性质的考察提供有效途径，为Petri网复杂大系统的分析提供重要手段，并特别适合于一类业务系统的描述和处理，具有一定的实用价值。