A Systematic Approach to the Petri Net Based Specification of Concurrent Systems

We describe an approach to the specification of concurrent systems which enables a Petri net model of a system to be built up in a systematic way starting from a trace-based CSP specification. This method enables the separate specification of the behavior of each component (process) and their interactions in terms of the feasible sequences of events in which they can be involved. A set of rules is then applied to transform the trace-based specifications into a complete Petri net that is analyzed and/or executed to validate system behavior. The domain transformation procedure is fully automatable. The specification of a safety-critical railway control system is used as a case study.     

形式化方法概貌

形式化方法是基于严格数学基础,对计算机硬件和软件系统进行描述、开发和验证的技术.其数学基础建立在形式语言、语义和推理证明三位一体的形式逻辑系统之上.形式化方法已经以不同程度和不同方式愈来愈多地应用在计算系统生命周期的各个阶段.介绍了形式化方法的发展历程和基本方法体系;以形式规约和形式验证为主线,综述了形式化方法的理论、方法、工具和应用的现状,展示了形式化方法与软件学科其他领域的交叉和融合;分析了形式化方法的启示,并展望了其面临的发展机遇和未来趋势.形式化方法的发展和研究现状表明：其应用已经取得了长足的进步,在提高计算系统的可靠性和安全性方面发挥了重要作用.在当今软件日益成为社会基础设施的时代,形式化方法将与人工智能、网络空间安全、量子计算、生物计算等领域和方向交叉融合,得到更加广阔的应用.研究和建立这种交叉融合的理论和方法不仅重要,而且具有挑战性.     

一种基于线性逻辑的构件组装方法研究

构件组装是基于构件的软件开发中的一个重要环节.本文利用线性逻辑描述了具有语义信息的构件结构,描述了独立于具体的计算环境、具有普遍适用性的三种构件组装关系,利用定理证明的方法,根据现存构件的描述和构件组装关系自动生成构件组装的方案,并从被适应的构件描述中推导出复合构件的描述,以提高对构件适应过程的描述和分析能力,为构件组装形式化分析、组装正确性的检验提供了保证,并列出了一些值得进一步研究的问题.     

构件适应和组装的形式化语义描述

构件适应技术是基于构件的软件工程中一个很难解决的问题,分析了三种构件适应结构的应用条件,采用了形式化语义的方法描述和推导了与构件以及构件适应相关的问题,根据构件描述与应用需求描述动态地选择不同的适应层次来适应构件,从被适应的构件描述中推导出复合构件的描述,为构件适应的形式化分析、组装正确性检验提供了保证,并列出了一些值得进一步研究的问题。     

A Formal Approach to Agent Design: An Overview of Constraint-Based Agents

Formal models for agent design are important for both practical and theoretical reasons. The Constraint-Based Agent (CBA) design approach includes two formal models: Constraint Nets and Timed -automata. A constraint net models the agents and the environment symmetrically as, possibly hybrid, dynamical systems; a timed -automaton specifies the desired real-time dynamic behaviors of the situated agents. Given a constraint-based specification of the desired behavior, a constraint-based agent can be synthesized as a constraint solver. Using formal modeling and specification, it is also possible to verify complex agents as obeying real-time temporal constraint specifications. This overview paper presents a summary of the development and application of the CBA framework.     

基于串空间的安全协议形式化验证模型及算法

网络安全在信息时代非常重要,而网络安全的关键问题之一是安全协议。首先介绍了当前安全协议形式化验证的前沿方向－－串空间理论,随后阐述了基于该理论设计的自动验证模型－－T模型,给出了该模型的算法及描述,并通过验证改进前后的Needham-Schroeder协议来说明T模型的优势。     

一种获得应用软件规格说明的新途径

在4GL开发环境下,应用系统的开发都是以界面的设计为导向的。该文介绍了一种在4GL环境下获得应用软件规格说明的新途径,即通过确定界面模型来确定应用软件的规格说明,并详细介绍了确定界面模型的方法———OVID(ObjectViewInteractionDesign,对象视图交互设计)。     

Verifying Temporal Properties of Reactive Systems: A STeP Tutorial

We review a number of formal verification techniques supported by STeP, the Stanford Temporal Prover, describing how the tool can be used to verify properties of several versions of the Bakery Mutual exclusion algorithm for mutual exclusion. We verify the classic two-process algorithm and simple variants, as well as an atomic parameterized version. The methods used include deductive verification rules, verification diagrams, automatic invariant generation, and finite-state model checking and abstraction.     

An approach to systems verification

The term systems verification refers to the specification and verification of the components of a computing system, including compilers, assemblers, operating systems and hardware. We outline our approach to systems verification, and summarize the application of this approach to several systems components. These components consist of a code generator for a simple high-level language, an assembler and linking loader, a simple operating system kernel, and a microprocessor design.     

Introduction to formal methods of software design

The potential benefits of using formal methods in the design of software are discussed. Concepts are illustrated by several small examples, with the objective of helping to bridge the gap between theory and practice. The paper introduces and explains some of the terminology, symbols and notation for the discrete mathematics used in the formal methods literature, intended to assist the reader in further study.     

Prospec: Support for Elicitation and Formal Specification of Software Properties

Although formal verification techniques have been demonstrated to improve program dependability, software practitioners have not widely adopted them. One reason often cited is the difficulty in writing formal specifications. This paper introduces Prospec, a tool to assist practitioners in formally specifying software properties. Prospec uses property patterns and scopes. Previous efforts at providing tool support for property specification have not provided convenient abstractions for specifying properties that include multiple events or conditions. A taxonomy of composite propositions is introduced to address this issue by defining relations among propositions and providing graphical abstractions that can assist in specification and validation of properties. This paper shows how composite propositions can enhance the specification pattern system by helping practitioners consider subtleties of behavior in sequences and concurrency through directed questions and visual abstractions. The paper introduces an elicitation and specification process to define patterns, scopes, and composite propositions.     

Formal hardware verification methods: A survey

Growing advances in VLSI technology have led to an increased level of complexity in current hardware systems. Late detection of design errors typically results in higher costs due to the associated time delay as well as loss of production. Thus it is important that hardware designs be free of errors. Formal verification has become an increasingly important technique towards establishing the correctness of hardware designs. In this article we survey the research that has been done in this area, with an emphasis on more recent trends. We present a classification framework for the various methods, based on the forms of the specification, the implementation, and the proff method. This framework enables us to better highlight the relationships and interactions between seemingly different approaches.     

Traditional, iterative, and component-based development: A social analysis of software development paradigms

Information systems have always been developed through social processes, wherein actors playing a variety of specialized roles interact to produce new business applications of information technology. As systems development practices continue to evolve, an ongoing assessment of their social implications is required. This paper develops a framework for understanding the potential social implications of an emerging, component-based development paradigm. Like two alternative paradigms for systems development, the traditional life-cycle and the iterative-incremental paradigms, the new component-based paradigm requires that certain generic roles be performed to build a desired application. For each paradigm, we identify the actors who play different roles, specify the nature of their interdependence, and indicate the requirements for managing conflicts constructively. The framework may guide research into the social dynamics of system development and serve as a tentative guide to the management of information systems development.     

动态存储管理安全验证的Coq实现

随着软件规模和复杂度的日益提升,软件安全的问题变得越来越严峻,同时有越来越多的研究工作集中在高可信软件的开发上 .由于类型系统表达能力的不足,现有的研究不触及底层软件的验证 .由于Hoare逻辑更好的表达能力,采用Hoare逻辑风格的推理,在汇编语言级别,使用Coq形式化与定理证明工具可以实现一个经过安全验证的动态存储管理函数库,这是程序验证技术一次有意义的实践 .实践表明,程序验证技术可以应用到高可信软件的开发上 .     

Using Program Transformations to Provide Safety Properties for Real-Time Systems

The process of showing that a program satisfies some particular properties with respect to its specification is called program verification. Axiomatic semantics is a verification method that makes assertions describing properties about the states of a program. There exists a transformation from the assertions of a program's verification proof to executable assertions. The latter may be embedded in the program to make it fault tolerant. An axiomatic proof system for concurrent programs is applied to generate executable assertions in a real time distributed environment. A train set example is used as modelproblem.     

Compact Data Structures and State-Space Reduction for Model-Checking Real-Time Systems

During the past few years, a number of verification tools have been developed for real-time systems in the framework of timed automata. One of the major problems in applying these tools to industrial-sized systems is the huge memory-usage for the exploration of the state-space of a network (or product) of timed automata, as the model-checkers must keep information about not only the control structure of the automata but also the clock values specified by clock constraints. In this paper, we present a compact data structure for representing clock constraints. The data structure is based on an O(n ³) algorithm which, given a constraint system over real-valued variables consisting of bounds on differences, constructs an equivalent system with a minimal number of constraints. In addition, we have developed an on-the-fly reduction technique to minimize the space-usage. Based on static analysis of the control structure of a network of timed automata, we are able to compute a set of symbolic states that cover all the dynamic loops of the network in an on-the-fly searching algorithm, and thus ensure termination in reachability analysis. The two techniques and their combination have been implemented in the tool UPPAAL. Our experimental results demonstrate that the techniques result in truly significant space-reductions: for six examples from the literature, the space saving is between 75% and 94%, and in (nearly) all examples time-performance is improved. Noteworthy is also the observation that the two techniques are completely orthogonal.