Safety,liveness and fairness in temporal logic

In this paper we present syntactic characterization of temporal formulas that express various properties of interest in the verification of concurrent programs. Such a characterization helps us in choosing the right techniques for proving correctness with respect to these properties. The properties that we consider include safety properties, liveness properties and fairness properties. We also present algorithms for checking if a given temporal formula expresses any of these properties.This work is partly supported by NSF grant CCR-9212183. A preliminary version of this paper appeared in the Fourth ACM Symposium on Principles of Distributed Computing.     

基于Petri网的软件演化过程

随着遗产软件系统的老化,软件演化已成为软件工程的一个新兴领域.对软件演化及过程的特征进行了描述,提出基于Petri网的软件演化过程;最后给出了软件演化过程的活性判断及优化算法.     

A symbolic model checking approach to verifying satellite onboard software

This paper discusses the use of symbolic model checking technology to verify the design of an embedded satellite software control system called the attitude and orbit control system (AOCS). This system is mission critical because it is responsible for maintaining the attitude of the satellite and for performing fault detection, isolation, and recovery decisions. An executable AOCS implementation by Space Systems Finland has been provided in Ada source code form, and we use the input language of the symbolic model checker NuSMV 2 to model the implementation at a detailed level. We describe the modeling techniques and abstractions used to alleviate the state space explosion due to the handling of timers and the large number of system components controlled by the AOCS. The required behavior has been specified as extended state machine diagrams and translated to temporal logic properties. Besides well-known LTL and CTL model checking algorithms, we adapt a previously unexplored form of the liveness-to-safety approach to the problem. The latter new technique turns out to successfully prove all desired properties of the system, outperforming both the LTL and CTL implementations of NuSMV 2.     

单触发Petri网的一个可达性判定方法

可达性判定问题是Petri网理论研究的一个重要课题.已有文献提出通过构造Petri网的可达树或可覆盖树来分析其可达性,但其中无界量ω的引入导致了无界Petri网运行过程中的信息丢失,使其可达性无法得到判定.众所周知,对于有界Petri网,通过构造其可迭性树或可达标识图来判定其可达性是容易的,但对于大量存在的无界Petri网,找到一个能判定其可达性的一般性算法却不太容易.本文给出一个Petri网子类--单触发Petri网,并给出它的一个可达性判定方法.     

一种形式化的软件可演化性特征描述方法

软件系统的活性和安全性是判断软件可演化性的重要依据之一。现有方法多使用经典逻辑对系统的活性和安全性进行刻画。环境及涉众的复杂性使得软件的可演化性分析可能出现矛盾的输入。经典逻辑的无矛盾律导致其不能对软件系统的演化特性进行有效建模。针对该问题,提出了一种形式化的软件可演化性特征描述方法,该方法允许矛盾性输入的存在,可用于对软件可演化性等存在矛盾特性的系统进行建模和分析。该方法使用多值时序逻辑刻画软件系统的演化需求,同时提出了一种抽象软件模型对软件系统进行建模,通过抽象软件模型的活性和安全性来对软件系统的可演化特征进行描述。     

Interpreting Message Flow Graphs

We give a semantics for Message Flow Graphs (MFGs), which play the role for interprocess communication that Program Dependence Graphs play for control flow in parallel processes. MFGs have been used to analyse parallel code, and are closely related to Message Sequence Charts and Time Sequence Diagrams in telecommunications systems. Our requirements are firstly, to determine unambiguously exactly what execution traces are specified by an MFG, and secondly, to use a finite-state interpretation. Our methods function for both asynchronous and synchronous communications. From a set of MFGs, we define a transition system of global states, and from that a Büchi automaton by considering safety and liveness properties of the system. In order easily to describe liveness properties, we interpret the traces of the transition system as a model of Manna-Pnueli temporal logic. Finally, we describe the expressive power of MFGs by mimicking an arbitrary Büchi automaton by means of a set of MFGs.     

基于注意力的热点块和显著像素卷积神经网络的人脸防伪方法

人脸防伪用于验证被测试者是否为真实活体,是计算机视觉领域的一个研究热点.攻击手段的多样性以及人脸识别主要在嵌入式、移动式等不具备高计算能力的设备上应用,使得快速有效的人脸防伪计算成为具有挑战性的任务.针对该问题,文中提出了一种基于注意力的热点块和显著像素卷积神经网络的方法.其中,热点块机制以对5个热点块的判别来取代对整...     

Defining liveness

A formal definition for liveness properties is proposed. It is argued that this definition captures the intuition that liveness properties stipulate that ‘something good’ eventually happens during execution. A topological characterization of safety and liveness is given. Every property is shown to be the intersection of a safety property and a liveness property.     

Identification and elimination of redundant control places in petri net based liveness enforcing supervisors of FMS

In the past two decades, a number of Petri-net-based approaches were proposed for deadlock prevention in flexible manufacturing systems (FMS). An FMS is modeled as a Petri net, and then the controller or the liveness enforcing supervisor (LES) is computed as a Petri net. A live Petri net (LPN) guarantees deadlock-free operations of the modeled FMS. An LES consists of a number of control places (CPs) and their related arcs. To-date most of the attention has been paid to make the underlying Petri net models live without questioning whether or not all of the computed CPs are necessary. It is often the case that the number of CPs determined by these approaches is not minimal. Reducing it in order to reduce the complexity of the controlled system is an important issue that was not tackled before. To address this problem, this paper proposes a redundancy test for an LES of an FMS. The proposed approach takes an LPN model, controlled by n CPs, as input and in the existence of any redundant CPs it produces redundant and necessary CPs. The proposed approach is applicable to any LPN consisting of a Petri net model (PNM), controlled by means of a set of CPs.