改进型有色Petri网的安全协议分析

利用有色Petri网分析安全协议时存在空间爆炸问题,对此提出了构建入侵者成功攻击安全协议所需知识集RI与入侵者可以获得的知识集KI,并定义入侵成功函数的改进型有色Petri网。利用改进型有色Petri网对具体的Helsinki协议和TMN协议进行了分析。实验表明,该方法能大大简化带有入侵者的Petri网模型的构造过程,有效缓解了Petri网在分析安全协议时的空间爆炸问题。     

改进身份认证协议的形式化描述与验证

以前用着色Petri网验证协议,大多只验证了其正确性,采用着色Petri网对自行设计的基于PKI的动态身份认证系统的安全性进行了描述和验证;一般在使用传统1-可达性分析方法分析复杂身份认证协议时,会存在状态空间爆炸的问题,为了有效地解决该问题,提出了一种用1-可迭性分析方法和向回分析方法相结合的策略,对该身份认证协议进行了分析,从而验证了该身份认证协议是安全的.     

一种新的形式化模型对安全认证协议的分析*

针对形式化建模方法在进行网络协议分析时遇到建立模型过程复杂、状态空间庞大等问题,提出在Petri网的基础上,引入融合库所建立一种新的形式化模型。利用该方法对Otway-Rees协议建立模型,并从可达性和仿真两方面进行分析。实验结果表明,该方法适合应用在协议分析中,不仅使协议建立模型更加简便,而且在一定程度上缩小了其状态空间。     

一种基于Petri网的安全协议验证方法

安全协议是实现网络安全的关键,如何验证安全协议的安全性是一个非常重要的工作。论文提出一种基于着色Petri网的安全协议形式化描述与安全验证方法,此方法建立在逆向状态分析和着色petri网可达性矩阵的基础之上,并采用具体协议来验证该方法的有效性。     

着色Petri网在科技计划项目管理系统建模中的应用

在深入研究科技计划项目管理业务基础上,鉴于Petri网的特点,提出了利用着色Petri网建模科技计划项目管理系统的方法.分析了着色Petri网适合于系统建模的原因,以项目管理评审环节为例讨论了着色Petri网在建模中的应用,并建立了基于着色Petri网的系统模型.通过对该模型的分析仿真结果表明,该方法是可行和有效的.     

基于分层时延CPN的轧钢物流系统建模

用户需求的多样性和随机性会导致生产过程物流异常复杂.针对该问题,提出一种基于分层时延着色Petri网(CPN)的轧钢物流系统模型,采用自顶向下的建模方法,利用CPN对轧钢系统中功能相同的设备进行不同着色,从而降低Petri网的规模以及防止系统模型的空间爆炸问题.实验结果表明,该建模方法能真实反映复杂系统的特点,并为其优...     

着色Petri网对高性能集群的建模与性能评估

针对形式化建模方法导致的状态空间爆炸问题,提出了一种基于Petri网的高性能集群建模与性能评估方法.首先分析了高性能集群的系统架构,构建了模型的总体结构;然后针对集群系统建立了相应的任务产生子模型和调度子模型,并通过对Petri网进行着色,根据不同种类任务的执行特点设计了相应的任务处理模型.仿真结果表明,利用所建立的模型能够有效评估关键参数对集群性能的影响.     

联锁逻辑形式化模型检验的研究

利用自动机理论模型检验算法,检验车站联锁逻辑的有色Petri网模型是否满足预期的性能。通过采用带标签的广义Büchi自动机(LGBA)构建线性时态逻辑,有效地解决了模型检验中的状态空间爆炸问题。该方法的研究增强了有色Petri网的分析和验证能力,利用该方法对车站联锁逻辑的实际问题进行了性能验证。     

一种新的安全协议验证方法

提出了一种基于Petri网的安全协议形式化描述和安全性验证的方法．该方法的特点是利用逆向状态分析和Petri网的状态可达性分析，判定协议运行过程中可能出现的不安全状态以及这些状态是否可达．通过实例证明了这种方法的有效性．     

用于软件可靠性分析的分解方法

随机Petri网(SPN)是一种有力的系统建模和分析工具.但SPN在应用中经常碰到状态空间爆炸问题.分解压缩技术是解决随机网状态空间指数性增长的有效方法之一.介绍了一种获得SPN可靠性模型瞬时状态的分解方法.该方法在保证评价和预测可靠性精确度的基础上,不仅能有效地降低可靠性描述与分析的复杂度,还扩大了分解压缩技术的适用范围.     

基于Petri网的密码协议形式化建模

密码协议是安全共享网络资源的机制和规范,是构建网络安全环境的基石,其安全性对整个网络环境的安全起着至关重要的作用。提出了采用Colored Petri Nets(CPN,着色Petri网)分析密码协议的新方法。采用新方法对TMN协议的多次并发会话通信进行形式化建模,模型依据会话配置和会话顺序进行功能单元划分,采用on-the-fly方法生成攻击路径。采用状态空间搜索技术,发现了该协议的多次并发会话不安全状态,并获得了新的攻击模式。     

SimQPN—A tool and methodology for analyzing queueing Petri net models by means of simulation

The queueing Petri net (QPN) paradigm provides a number of benefits over conventional modeling paradigms such as queueing networks and generalized stochastic Petri nets. Using queueing Petri nets (QPNs), one can integrate both hardware and software aspects of system behavior into the same model. This lends itself very well to modeling distributed component-based systems, such as modern e-business applications. However, currently available tools and techniques for QPN analysis suffer the state space explosion problem, imposing a limit on the size of the models that are tractable. In this paper, we present SimQPN—a simulation tool for QPNs that provides an alternative approach to analyze QPN models, circumventing the state space explosion problem. In doing this, we propose a methodology for analyzing QPN models by means of discrete event simulation. The methodology shows how to simulate QPN models and analyze the output data from simulation runs. We validate our approach by applying it to study several different QPN models, ranging from simple models to models of realistic systems. The performance of point and interval estimators implemented in SimQPN is subjected to a rigorous experimental analysis.     

一种兼顾协议正确性验证和性能评估的Petri网方法

基于Petri网的协议形式化分析方法由于其精炼、简洁和无二义性逐步成为分析协议的一条可靠和准确的途径,但是协议的形式化分析目前研究还不够深入,协议分析的两个重点内容正确性验证和性能评估所需要的模型不同,一种模型只能解决一方面的工作。为了有效地解决这一问题,文中提出了一种用原型Petri网作为协议验证模型的思路和方法,在不改变原型Petri网结构的基础上对变迁赋予发生时延,解决了协议的性能评估问题。本文还给出了协议验证内容与Petri网分析方法的对应关系,并对0-1停止等待协议进行了详细的分析,最后把0-1停止等待协议的原型Petri网模型转化为时延Petri网,对协议的性能进行了评估。     

Petri nets modeling and analysis using extended bag-theoreticrelational algebra

Petri nets are a powerful modeling tool for studying reactive, concurrent systems. Analysis of the nets can reveal important information concerning the behavior of a modeled system. While various means for the analysis of the nets has been developed, a major limitation in the analysis, is explosion of large states space in simulation. An efficient method to manage large states space would overcome such a limitation. This paper proposes a framework for the modeling and analysis of Petri nets using relational database technologies. Formalism of the framework is based on a bag-theoretic relational algebra extended from the conventional, Within the framework, Petri nets are formalized by bag relations, and analysis algorithms are developed based on such formal relations. Properties associated with the nets are formalized by queries described in terms of the bag-theoretic relational algebra. The framework has been realized in a commercial relational database system using a standard SQL.     

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.     

Hierarchical reachability graph of bounded Petri nets forconcurrent-software analysis

Petri nets have been proposed as a promising tool for modeling and analyzing concurrent-software systems such as Ada programs and communication protocol software. Among analysis techniques available for Petri nets, the most general approach is to generate all possible states (markings) of the system in a form of a so-called reachability graph. However, this conventional reachability graph approach is inefficient or intractable, even for a bounded Petri net, due to state explosion in many practical applications. To cope with this problem, this paper proposes a method for constructing a hierarchically organized state space called the hierarchical reachability graph (HRG). Using the HRG, we obtain necessary and sufficient conditions for reachability and deadlock, as well as algorithms to test whether a given state or marking is reachable from the initial state and whether there is a deadlock state (a state with no successor states)     

State space analysis of Petri nets with relation-algebraic methods

A large variety of systems can be modelled by Petri nets. Their formal semantics are based on linear algebra which in particular allows the calculation of a Petri net’s state space. Since state space explosion is still a serious problem, efficiently calculating, representing, and analysing the state space is mandatory. We propose a formal semantics of Petri nets based on executable relation-algebraic specifications. Thereupon, we suggest how to calculate the markings reachable from a given one simultaneously. We provide an efficient representation of reachability graphs and show in a correct-by-construction approach how to efficiently analyse their properties. Therewith we cover two aspects: modelling and model checking systems by means of one and the same logic-based approach. On a practical side, we explore the power and limits of relation-algebraic concepts for concurrent system analysis.     

着色Petri网应用研究

着色Petri网是在经典Petri网理论基础上增加了token类型和网的模块这两个功能,它现在已成为一种较完善的语言,可以用来对各种系统规范和协议等进行设计、规范描写、仿真和验证等。文章对着色Petri网的基本理论进行了简单介绍,并对一个简单的通信协议进行建模和分析,提出了今后着色Petri网发展的一个主要方向。     

自动化仓库输送调度问题的建模与控制研究

基于面向对象着色Petri网模型和时态逻辑方法,对自动化仓库输送系统运行过程的调度问题进行研究。建立了系统的面向对象着色Petri网模型,讨论了该过程的死锁分析问题,给出了系统行为的时态逻辑规范和死锁避免的最大允许反馈控制策略。     

Reduction rules for time Petri nets

The goal of net reduction is to increase the effectiveness of Petri-netbased real-time program analysis. Petri-net-based analysis, like all reachabilitybased methods, suffers from the state explosion problem. Petri net reduction is one key method for combating this problem. In this paper, we extend several rules for the reduction of ordinary Petri nets to work with time Petri nets. We introduce a notion of equivalence among time Petri nets, and prove that our reduction rules yield equivalent nets. This notion of equivalence guarantees that crucial timing and concurrency properties are preserved.