基于Petri网的混合安全策略建模与验证

提出了一种基于有色Petri网的建模方法,在系统的Petri网模型中可以对中国墙策略进行分析和验证.给出了基于有色Petri网的混合安全策略的形式化定义;并通过一个系统实例阐述了如何利用该方法对系统的混合安全性进行分析和验证.无论是在系统的设计阶段还是实现阶段,该方法都能够有效地提升系统的混合安全性.     

基于受控计时扩展Petri网的分拣系统建模

分拣系统中 ,由于操作人员的参与 ,可能导致被分拣货物和装箱清单不一致。这主要是由于上包控制和货包信息的同步跟踪不可控所造成。为解决这个问题 ,该文提出受控计时扩展Petri网 ,在此基础上对自动分拣系统进行了建模 ,并分析了操作人员的控制作用。实际应用表明 ,受控计时扩展Petri网为具有人参与的物流系统提供了一种良好的建模方法。     

Formal and incremental construction of distributed algorithms: On the distributed reference counting algorithm

The development of distributed algorithms and, more generally, distributed systems, is a complex, delicate and challenging process. Refinement techniques of (system) models improve the process by using a proof assistant, and by applying a design methodology aimed at starting from the most abstract model and leading, in an incremental way, to the most concrete model, for producing a distributed solution. We show, using the distributed reference counting (DRC) problem as our study, how models can be produced in an elegant and progressive way, thanks to the refinement and how the final distributed algorithm is built starting from these models. The development is carried out within the framework of the event B method and models are validated with a proof assistant.     

基于Petri网化简技术的工作流模型正确性研究

为了更有效地对工作流模型进行分析验证，提出了一种基于Petri网化简技术的工作流模型正确性验证方法。在对各种工作流模型验证技术深入研究的基础上，通过对非自由选择网结构活性和有界性的分析，给出了针对Petri网中非自由选择部分的分析方法。在保持活性和有界性的前提下，给出了将活的且有界的非自由选择部分转化为自由选择部分的转化方法，从而将非自由选择的Petri网验证问题转化为自由选择Petri网的验证问题。通过一个例子说明了如何使用该文提出的方法来验证模型的正确性。     

Synthesis a Petri net based control model for a FMS cell

Petri nets have been recognised as a high level formal and graphical specification language for modelling, analysis, and control of concurrent asynchronous distributed systems. This paper presents a PN model, synthesised by an extended version of the knitting synthesis technique. This method, as an incremental design approach, establishes the conditions under which the fundamental behavioural properties of the synthesised systems are fulfilled and preserved. That is, the synthesised models are live, bounded, and reversible (cyclic). A Petri net with the aforementioned properties is called a well-behaved Petri net system which is guaranteed to operate in a deadlock-free, stable, and cyclic fashion. Well-behaved Petri net models, synthesised using the proposed method can be compiled into control codes and implemented as real-time controllers for flexible manufacturing systems. The significance of this paper is due to the application of an extended version of knitting synthesis technique to a real life example of a flexible manufacturing system.     

Modeling and formal verification of embedded systems based on a Petri net representation

In this paper we concentrate on aspects related to modeling and formal verification of embedded systems. First, we define a formal model of computation for embedded systems based on Petri nets that can capture important features of such systems and allows their representation at different levels of granularity. Our modeling formalism has a well-defined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process. Second, we propose an approach to the problem of formal verification of embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking tools. We propose two strategies for improving the verification efficiency, the first by applying correctness-preserving transformations and the second by exploring the degree of parallelism characteristic to the system. Some examples, including a realistic industrial case, demonstrate the efficiency of our approach on practical applications.     

一种基于线性逻辑的Petri网分析方法

1 引言 Petri网是一种用网状图形表示系统模型的方法,能够从组织结构、控制和管理的角度,精确描述系统中事件(变迁)之间的依赖(顺序)和不依赖(并发)关系。Petri网理论提供了强大的分析方法,如不变量分析、系统性能分析(如活性)等以证明系统的正确性。近年来Petri网也被用来表示知识推理,例如用于诊断和监控,这就需要发展一种关于Petri网行为的推理主题。有些学者把经典逻辑和Petri网相结合,用Petri网表示产生式规则系统,网的框架代表基于产生式规则     

基于Petri网的工作流合法性验证综述

对传统的工作流合理性验证方法进行了阐述,并分析了这些方法的优缺点,着重针对国内外学者用Pe-tri网对工作流合理性验证方法进行综述,分析其特点,并指出了工作流的合理性验证的发展方向。     

Verification of bounded Petri nets using integer programming

Model checking based on the causal partial order semantics of Petri nets is an approach widely applied to cope with the state space explosion problem. One of the ways to exploit such a semantics is to consider (finite prefixes of) net unfoldings—themselves a class of acyclic Petri nets—which contain enough information, albeit implicit, to reason about the reachable markings of the original Petri nets. In [19], a verification technique for net unfoldings was proposed, in which deadlock detection was reduced to a mixed integer linear programming problem. In this paper, we present a further development of this approach. The essence of the proposed modifications is to transfer the information about causality and conflicts between the events involved in an unfolding, into a relationship between the corresponding integer variables in the system of linear constraints. Moreover, we present some problem-specific optimisation rules, reducing the search space. To solve other verification problems, such as mutual exclusion or marking reachability and coverability, we adopt Contejean and Devie's algorithm for solving systems of linear constraints over the natural numbers domain and refine it, by taking advantage of the specific properties of systems of linear constraints to be solved. Another contribution of this paper is a method of re-formulating some problems specified in terms of Petri nets as problems defined for their unfoldings. Using this method, we obtain a memory efficient translation of a deadlock detection problem for a safe Petri net into an LP problem. We also propose an on-the-fly deadlock detection method. Experimental results demonstrate that the resulting algorithms can achieve significant speedups.

Distributed simulation of modular time Petri nets: An approach and a case study exploiting temporal uncertainty

This paper proposes an approach to modular modelling and simulation of complex time-critical systems. The modelling language is represented by Merlin and Farber’s Time Petri Nets (TPNs) augmented with inhibitor arcs and modular constructs borrowed from the Petri Net Markup Language (PNML) interchange format. Analysis techniques depend on Temporal Uncertainty Time Warp (TUTW), a time warp algorithm capable of exploiting temporal uncertainty in general optimistic simulations over a networked context. A key feature of the approach is the fact that TPN models naturally exhibit a certain degree of temporal uncertainty which the TUTW control engine can exploit to achieve good speedup without a loss in the accuracy of the simulation results. The developed TUTW/TPN kernel is demonstrated by modelling and simulation of a real-time system example.A preliminary version of this paper was presented at 38th SCS Annual Simulation Symposium, April 4–6, 2005, San Diego (CA), IEEE Computer Society, pp. 233–240. Franco Cicirelli achieved a PhD in computer science from the University of Calabria (Unical), DEIS—department of electronics informatics and systems science. As a postdoc, he is making research on agent and service paradigms for the development of distributed systems, parallel simulation, Petri nets, distributed measurement systems. He holds a membership with ACM. Angelo Furfaro, PhD, is a computer science assistant professor at Unical, DEIS, teaching object-oriented programming. His research interests are centred on: multi-agent systems, modeling and analysis of time-dependent systems, Petri nets, parallel simulation, verification of real-time systems, distributed measurement systems. He is a member of ACM. Libero Nigro is a full professor of computer science at Unical, DEIS, where he teaches object-oriented programming, software engineering and real-time systems courses. He directs the Software Engineering Laboratory (www.lis.deis.unical.it). His current research interests include: software engineering of time-dependent and distributed systems, real-time systems, Petri nets, modeling and parallel simulation of complex systems, distributed measurement systems. Prof. Nigro is a member of ACM and IEEE.     

基于Petri的分布式实时嵌入式软件合理性分析

合理的模型是保证分布式实时嵌入式(DRE)软件可靠性的关键.提出了分析DRE软件模型的合理性方法.该方法基于带抑制弧的时间Petri网(ITPN),采用自顶向下的策略对功能模块及其通信过程分别建模,并利用Petri网的合成运算形成整个应用的ITPN模型.在确保系统实时性的前提下,给出软件模型合理性的形式化定义及其判定定理.最后以实例说明该方法的可行性.     

Tutorial and Survey Articles: An introduction to Petri Nets

This paper describes the fundamental concepts and characteristics of Petri nets (PNs) that make them a significant tool for modeling and analyzing asynchronous systems with concurrent and parallel activities and follows the extensions that improved the implementation capabilities of the original PNs.

Their first and most relevant extension was time modeling, a vital aspect of system performances not considered in the original version. There are several possibilities for introducing time in PNs. Among them, a technique that associates time with places is presented in some detail. As PNs tend to become cumbersome and time consuming when large and complex systems are involved, a method for decomposing timed PNs of open queuing networks is reviewed here.

Though initially developed as an information/computer-based technique, PNs were immediately adopted in a variety of application areas, such as manufacturing, design, planning and control. Viewed through a more recently developed programming perspective, the ordinary PNs became “high level” PNs suitable for defining different data types and for applying hierarchical approaches.

It is expected that the robust theoretical basis of this tool coupled with its visual and flexibility features will continue to appeal to researchers and practitioners alike in a variety of domains and as a result will continue to evolve and expand.     

Integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems

This paper presents some results of integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems. The intention of this research is to use predicate transition nets as a specification method and to use first order temporal logic as a verification method so that their strengths — the easy comprehension of predicate transition nets and the reasoning power of first order temporal logic can be combined. In this paper, a theoretical relationship between the computation models of these two formalisms is presented; an algorithm for systematically translating a predicate transition net into a corresponding temporal logic system is outlined; and a special temporal refutation proof technique is proposed and illustrated in verifying various concurrent properties of the predicate transition net specification of the five dining philosophers problem.     

A distributed approach for fault detection and diagnosis based on Time Petri Nets

This paper proposes an algorithm for the model based design of a distributed protocol for fault detection and diagnosis for very large systems. The overall process is modeled as different Time Petri Net (TPN) models (each one modeling a local process) that interact with each other via guarded transitions that becomes enabled only when certain conditions (expressed as predicates over the marking of some places) are satisfied (the guard is true). In order to use this broad class of time DES models for fault detection and diagnosis we derive in this paper the timing analysis of the TPN models with guarded transitions. In this paper we also extend the modeling capability of the faults calling some transitions faulty when operations they represent take more or less time than a prescribed time interval corresponding to their normal execution. We consider here that different local agents receive local observation as well as messages from neighboring agents. Each agent estimates the state of the part of the overall process for which it has model and from which it observes events by reconciling observations with model based predictions. We design algorithms that use limited information exchange between agents and that can quickly decide “questions” about “whether and where a fault occurred?” and “whether or not some components of the local processes have operated correctly?”. The algorithms we derive allow each local agent to generate a preliminary diagnosis prior to any communication and we show that after communicating the agents we design recover the global diagnosis that a centralized agent would have derived. The algorithms are component oriented leading to efficiency in computation.     

基于Petri网理论的FC-AE-ASM建模与性能分析*

以确定与随机Petri网为工具,基于周期消息,对光纤通道在航空电子环境的FC-AE-ASM（fiber channel anonymous subscriber messaging）网络进行建模仿真,根据仿真计算出FC-AE-ASM网络负载和系统的延迟时间两个重要的性能指标,通过对两个指标的性能曲线进行分析,有助于进一步理解航电系统事件消息在FC-AE-ASM网络中的传输机制,为综合航电系统的设计和完善提供重要的理论依据。     

基于Petri网和逻辑电路的网络安全验证

利用Petri网的库所和变迁来描述网络的状态和行为,用逻辑代数的0和1形象表示库所的状态,将复杂的PN模型转换成简单的逻辑表达式,提出了Petri网与逻辑电路相结合的新型网络数据流验证方式。这种方法具有的形式化步骤与数学模型相支持,是一种新型快捷的网络安全验证方法。     

Petri net based process scheduling: A model of the control system of flexible manufacturing systems

In this paper, we propose a class of algorithms for the sub-optimal solution of a particular class of problems of process scheduling, particularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, each formed by a number of temporally related tasks (segments). Tasks are executable by alternate resource sets, different both in performance and costs. Processes and tasks are characterized by release times, due dates, and deadlines. Time constraints are also present in the availability of each resource in resource sets. It has been proven that such a problem does not admit an algorithm for an optimal solution in polynomial time. Our proposed algorithm finds a sub-optimal schedule according to a set of optimization criteria, based on task and process times (earliness, tardiness), and/or time independent costs of resources. Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling algorithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) theautomatic synthesis of Petri net models of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose kernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-optimal multi-criteria algorithms. Furthermore, the paper defines the interaction mechanisms between the coordination and scheduling subsystems. Our approach clearly distinguishes the mechanism of the net execution from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: theexecutor and thescheduler levels. One of the outstanding differences between these levels is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distributed component, whose behavior may heavily depend on the problem class. If the scheduler fails, the executor is, in any case, able to proceed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.     

基于逻辑Petri网的Web服务簇模型

在基于聚类的Web服务中,同一服务簇中的服务在参数名称、参数数量和顺序方面不尽一致,具有参数不确定性的特点,导致参数匹配仍需要很大的工作量。因此提出一种基于逻辑Petri网的Web服务簇模型,将服务的参数集合表示为基于服务簇参数集的逻辑向量,建立了服务簇到各个服务的映射关系,实现对服务参数的统一管理。基于语义相似度的参数匹配仅在服务簇层进行,在服务簇内可以用位置向量直接定位参数,通过逻辑比较判断是否匹配,使得参数匹配的规模和计算复杂度大大降低,提高了服务发现效率。     

审计缓冲区的形式化模型及其验证

审计系统作为安全信息系统的一个重要组成部分,对于监督系统的正常运行、保障安全策略的正确实施、构造计算机入侵检测系统等都具有十分重要的意义。审计缓冲区的管理是审计系统的核心部分,本文利用时序Petri网对审计缓冲区管理的实现方案进行建模,进而对系统的安全性和活性进行了分析和验证。该方法利用时序逻辑扩充了Petri网缺乏描述系统事件之间时序关系的局限性,同时发挥了Petri网对系统并发和物理结构的有效描述及分析的优势,达到了系统验证的目的。