结合形式化的面向对象设计方法与支撑系统

为了有效地结合形式化和非形式化设计方法各自的优点,克服其不足之处,以尽可能保证软件设计的质量与可靠性,文章提出了一种将形式化方法与非形式化的面向对象设计方法ＨＯＯＤ（ｈｉｅｒａｒｃｈｉｃａｌｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄｄｅｓｉｇｎ）相结合的途径,并介绍了其机器支撑环境的设计与实现．该途径在对层次式面向对象设计方法ＨＯＯＤ进行必要扩充的基础上,有机地集成了Ｚ语言等形式规约技术．支持这一途径的支撑环境提供了一套方便灵活的图形构筑工具、语法制导的形式语言与文本编辑工具,以及自动检查机制等．     

Specifying transaction-based information systems with regularexpressions

The work is about the formal specification of transaction-based, interactive information systems. A transaction is a task that the user can execute independently, and the system can be defined as a partially ordered set of transactions. The general framework is the transformational paradigm, based on the classical Waterfall development model (W.W. Royce, 1970). The stages are systems analysis, software specification, design, and implementation. The systems analysis and software specification stages are covered. An informal, transaction-oriented method for systems analysis is proposed. The resulting system specification involves two parts: a high-level specification of each transaction and a formal specification of the system's control flow, i.e., the order of execution of the transactions. The system's control flow is expressed in a formal language describing concurrent regular expressions built on transaction names. At the software specification stage, some operational requirements, such as connect/disconnect transactions and the application of the all-or-nothing principle, are added to the system specification. Then a serial product automaton (SPA) is used to transform the concurrent expression into a single regular expression. This result is proven to be consistent with the system specification     

一个面向网络并行环境的需求规约语言

提出了一个面向网络并行环境的需求规约语言ＯＯＲＳＬ。ＯＯＲＳＬ支持面向对象的分析方法,可以定义并行成分一进程,可以使用前后断言来表达用户的功能需求,允许将非经和半形式化的需求定义嵌入形式化的需求定义中。因此,ＯＯＲＳＬ语言是一个半形式化的语言,它为网络并行环境下的软件自动化和软件形式化开发提供了支持介绍了ＯＯＲＳＬ的设计思想和主要语法成分。给出了一个实例。     

形式化语言RT-Z的合成及其应用

Z是一种确定相关数据特征的非常成功的形式化语言，却在构造动态行为方面的模型缺乏相应的功能；而Timed CSP是一种确定动态行为的功能强大的语言，但它没提供适当的结构来构造相关数据特征。文中通过形式化语言Z和过程代数Timed CSP合成一种新的形式化方法RT-Z，使得RT-Z在软件系统开发过程的需求定义和设计阶段能书写软件系统一致、简单的规格说明。     

Towards the formal specification of an OPS5 production system architecture

The article presents a formal specification for many important aspects of the OPS5 production systems framework. the article illustrates how an abstract formal specification of a production system can be created and the benefits this provides to those involved in the development of knowledge-based systems. the formal specification is preceded by an informal specification of a production system upon which the formal model is based and the development is illustrated through the use of concrete examples. the notation used is that of “Z” (J. M. Spivey, The Z Notation, Prentice-Hall, Englewood Cliffs, NJ, 1990), a language based upon typed set theory. This language has been used to success in the specification of critical conventional software systems (I. Hayes, Technical Monograph PRG-46, Oxford University Computing Laboratory, Oxford, England, 1985) and which is formal enough to allow for the creation of rigorous specifications, yet is of a form that makes these specifications “readable.” the aim of the article is to show that formal techniques can be applied to areas of knowledge-based system development, thus promoting correctness, reliability, and understanding. © 1994 John Wiley & Sons, Inc.     

基于设计决定的逐步求精方法及环境

逐步描述、变换及证明的软件开发过程包含两个转换,一是从非形式的用户需求到形式描述,一是从形式描述到算法实现。开发过程中的关键是如何做出设计决定。为了更好地维护、重用软件以及程序证明,不仅仅要对软件的形式描述及实现做文档记录,也要记下开发过程中所做的每一步决定。我 们用两个例子来说明如上这种逐步求精的方法以及设计决定在其中所起的作用,并且我们实现了一个包括SPEC、OOMM、PROT、VERI几个子系统组成的环境来支持上述过程。     

Performance modelling of a network processor using POOSL

The increasing complexity of innovative real-time hardware/software systems forced industry to consider system-level design methods. Before actually implementing a system with hardware and software components, system-level design methods enable analysing the performance of different design alternatives that realise the required functionality. In order to develop performance models early in the design process, the parallel object-oriented specification language (POOSL) can be used. POOSL is an expressive modelling language for analysing complex real-time distributed hardware/software systems. Being equipped with a formal semantics, POOSL ensures unambiguous execution of models and proper application of performance analysis techniques. This paper discusses the use of POOSL for analysing the performance of a network processor. A network processor consists of components that perform their behaviour in a synchronously concurrent way, whereas POOSL is based on an asynchronous modelling paradigm. In this paper, we illustrate that constructing abstract models of synchronous systems for the purpose of performance analysis may benefit from an asynchronous modelling approach.     

GUIDE: Games with UML for interactive design exploration

In this paper we present our design tool GUIDE, which allows the user to explore a design in UML interactively by playing a game. The game incorporates both the design model and a specification of what it means for the design to be correct. The central idea of this approach is that the designer can increment the game during a play and gradually add more detail to it. Specification and design are refined by repeated plays of the game. The designer stops playing when design and specification are detailed enough for his purpose and match each other. The interactive game approach helps to cope with incompleteness and informal definition of UML models, which make strictly formal verification techniques difficult. The designer may resolve these problems when they arise during a play or let the GUIDE tool determine how the play should proceed. We discuss the potential impact of GUIDE and tools like it on software development.     

Development of an atomic‐broadcast protocol using LOTOS

In this article we report on the development of a group‐communication service using the formal specification language LOTOS, and present our experience in using publicly available tools for this purpose. The service implements atomic broadcast through a Two‐Phase‐Commit protocol, providing at‐least‐once delivery semantics and with no restriction on message delivery order. First we wrote an informal specification describing the desired properties from the service, the interfaces with the underlying network layer and the upper user layer, and the protocol to be used by the service. Then we developed the formal specification of the protocol in LOTOS. After validating the formal specification and thus having a certain confidence in its adequacy with respect to the informal specification, we derived test cases from the formal specification and implemented the service using the Concert/C distributed programming language. While testing the implementation, we found that most errors were related to unspecified features or bugs in the execution environment. From this experience, we draw our conclusions on the usefulness of software development based on formal techniques. Copyright © 1999 John Wiley & Sons, Ltd.     

Decomposition in Real-Time Safety-Critical Systems

Existing formal techniques for the development of software for use in safety-critical systems do not adequately address non-functional system requirements such as those involving timing. In this paper we describe a formal development method in which specifications may be decomposed into unexceptional programs whilst preserving the functional and timing requirements of the specification. We illustrate the method with a speed monitoring example.     

Provably correct derivation of algorithms using FermaT

The transformational programming method of algorithm derivation starts with a formal specification of the result to be achieved, plus some informal ideas as to what techniques will be used in the implementation. The formal specification is then transformed into an implementation, by means of correctness-preserving refinement and transformation steps, guided by the informal ideas. The transformation process will typically include the following stages: (1) Formal specification (2) Elaboration of the specification, (3) Divide and conquer to handle the general case (4) Recursion introduction, (5) Recursion removal, if an iterative solution is desired, (6) Optimisation, if required. At any stage in the process, sub-specifications can be extracted and transformed separately. The main difference between this approach and the invariant based programming approach (and similar stepwise refinement methods) is that loops can be introduced and manipulated while maintaining program correctness and with no need to derive loop invariants. Another difference is that at every stage in the process we are working with a correct program: there is never any need for a separate “verification” step. These factors help to ensure that the method is capable of scaling up to the development of large and complex software systems. The method is applied to the derivation of a complex linked list algorithm and produces code which is over twice as fast as the code written by Donald Knuth to solve the same problem.     

Detection of metamorphic and virtualization-based malware using algebraic specification

We present an overview of the latest developments in the detection of metamorphic and virtualization-based malware using an algebraic specification of the Intel 64 assembly programming language. After giving an overview of related work, we describe the development of a specification of a subset of the Intel 64 instruction set in Maude, an advanced formal algebraic specification tool. We develop the technique of metamorphic malware detection based on equivalence-in-context so that it is applicable to imperative programming languages in general, and we give two detailed examples of how this might be used in a practical setting to detect metamorphic malware. We discuss the application of these techniques within anti-virus software, and give a proof-of-concept system for defeating detection counter-measures used by virtualization-based malware, which is based on our Maude specification of Intel 64. Finally, we compare formal and informal approaches to malware detection, and give some directions for future research.     

Formal Specifications of User Requirements

There is a wide gap between informal requirements and a formal object-oriented specification. To help bridge this gap, we propose that a formal and executable user-centred model should be constructed initially. The user-centred model, which specifies the behaviour that the environment expects from the system, is expressed in terms of agent views and gives very early feedback to the requirements' capture process. Once the user-centred model has been validated with respect to the environment, it can be used as a step in the construction and validation of the formal object-oriented specification.     

On integrating confidentiality and functionality in a formal method

This paper proposes a formal method, based on Circus, for developing software systems that respect a joint specification of functionality and confidentiality attributes. We extend the semantics of Circus to capture the information that users can infer about a system’s behaviour, enabling confidentiality and functionality attributes of a system to be specified together. We represent inconsistencies between functionality and confidentiality properties as miracles, rendering insecure functionality infeasible. We present techniques for verifying that a system design’s functionality and confidentiality attributes are mutually consistent, and for ensuring that consistency is maintained by refinement steps.