Search

Since the advent of the computer and computer programming there have been many attempts to improve the quality of the software systems developed. At various stages in this evolution of development techniques, processes, and methodologies, a review of the current trend in software development is conducted. One such current trend is in the realm of safety-critical system development. Safety-critical systems are characterized by the resulting potential of harm to or loss of life if such systems should fail during operation. A strategy applied in developing such systems is the use of formal specification techniques. Formal specification techniques are the application of rigorous techniques to assess the correctness of system design. The use of formal specification techniques in safety-critical system development has been in place for a number of decades and there have been multiple reviews and comparisons of the successful and failed application of formal specification techniques. This report reviews examples of the application of formal specification techniques in a number of application domains, with a focus on the types of error detection and correction associated with the particular technique. The benefit of this work is towards the assessment of the suitable of a specific formal specification technique with a particular problem domain.

The subject of this demo is a tool, under development, for training undergraduate students in system design. The tool supports the requirement elicitation and system specification phases of system design. The tool permits specifications in natural languages, such that stakeholders not familiar with computer programming and formal specifications may participate in the development and validation of the requirements and the specifications. A GUI may be produced from verbal specifications enabling think aloud evaluations of the designed system. The tool is intended for undergraduate students who do not have the time required for learning the use of feature rich industrial software tools. Our tool has few features making it easy to learn and easy to use, which should enable the students to invest most of their resources in the essence of their exercises.

Formal specifications of software systems are extremely useful because they can be rigorously analyzed, verified, and validated, giving high confidence that the specification captures the desired behavior. To transfer this confidence to the actual source code implementation, a formal link is needed between the specification and the implementation. Generating the implementation directly from the specification provides one such link. A program transformation system such as Paige's APTS can be useful in developing a source code generator. This paper describes a case study in which APTS was used to produce code generators that construct C source code from a requirements specification in the SCR (Software Cost Reduction) tabular notation. In the study, two different code generation strategies were explored. The first strategy uses rewrite rules to transform the parse tree of an SCR specification into a parse tree for the corresponding C code. The second strategy associates a relation with each node of the specification parse tree. Each member of this relation acts as an attribute, holding the C code corresponding to the tree at the associated nodes the root of the tree has the entire C program as its member of the relation. This paper describes the two code generators supported by APTS, how each was used to synthesize code for two example SCR requirements specifications, and what was learned about APTS from these implementations.

Testing is the primary method to validate that a software implementation meets its specification. In this paper, we demonstrate an approach to validating an executable semantics using property- and model-based random testing in QuickCheck to automate and unify the testing of the semantics and its implementation. Our approach shows the use of executable semantics to bridge the gap between formal mathematical specification and implementation, as well as emphasising the suitability of functional programming languages -- in this case Erlang -- for writing executable semantics. The approach is illustrated through a concrete example, in which the implementation of a proposed extension to the Erlang programming language -- scalable groups -- is tested. This new component comes with a small-step operational semantics written in mathematical notation, and was initially tested using unit testing. Through our work, we were able to find new bugs in both the implementation and the specification.

We define a predicate-transformer semantics for an object oriented language that includes specification constructs from refinement calculi. The language includes recursive classes, visibility control, dynamic binding, and recursive methods. Using the semantics, we formulate notions of refinement. Such results are a first step toward a refinement calculus.

The majority of formal methods for distributed systems have their origins in the 1980’s and were targeted at the early generations of distributed systems. However, modern distributed systems have new features not found in the early systems, e.g. they areobject-oriented, havemobile components, aretime sensitive and are constructed according to advanced system development architectures, e.g.viewpoints models. A major topic of current research is thus, how to enhance the existing formal techniques in order to support these new features. This paper gives a tutorial level review of this research area. We particularly focus on the process algebra LOTOS and consider how the technique can be reconciled with these new features.

The lack of a method for developing programs from Z specifications is a widely recognized difficulty. In response to this problem, different approaches to the integration of Z with a refinement calculus have been proposed. These programming techniques are promising, but as far as we know, have not been formalized. Since they are based on refinement calculi formalized in terms of weakest preconditions, the definition of a weakest precondition semantics for Z is a significant contribution to the solution of this problem. In this paper, we actually construct a weakest precondition semantics from a relational semantics proposed by the Z standards panel. The construction provides reassurance as to the adequacy of the resulting semantics definition and additionally establishes an isomorphism between weakest preconditions and relations. Compositional formulations for the weakest precondition of some schema calculus expressions are provided.

Specification matching is a way to compare two software components. In the context of software reuse and library retrieval it can help determine whether one component can be substituted for another or bow one can be modified to fit the requirements of the other. In the context of object-oriented programming, it can help determine when one type is a behavioral subtype of another. In the context of system interoperability, it can help determine whether the interfaces of two components mismatch. We use formal specifications to describe the behavior of software components, and hence, to determine whether two components match. We give precise definitions of not just exact match, but more relevantly, various flavors of relaxed match. These definitions capture the notions of generalization, specialization, substitutability, subtyping, and interoperability of software components. We write our formal specifications of components in terms of pre-and post-condition predicates. Thus, we rely on theorem proving to determine match and mismatch. We give examples from our implementation of specification matching using the Larch Prover.

A commonly made criticism of formal methods is that they increase costs. Selective use of formal methods to define critical requirements can, however, lead to a significant decrease in lifecycle costs. In particular the economic and technical benefits of outsourcing the development of software can be fully realized and the cost of outsourcing slightly reduced by use of a formal specification. In this paper we describe a development in which a formal specification prepared by the customer formed part of the contract with the supplier. We conclude that this use of a formal specification can reduce risks and costs for all concerned and can help foster fruitful and co-operative relations in situations which are often fraught with confrontation.

Non-determinacy is important in the formal specification and formal derivation of programs, but non-determinacy within expressions is theoretically problematical. The refinement calculus side-steps the problem by admitting non-determinacy only at the level of statements, leading to a style of programming that favours statements and procedures over expressions and functions. But expressions are easier to manipulate than statements, and the poverty of the expression notation has made the formal derivation of imperative programs tedious. Here we introduce non-deterministic expressions into the refinement calculus by constructing a weakest precondition semantics for imperative specifications and programs that holds good even when expressions may be non-deterministic.

A view is a partial specification of a program, consisting of a state space and a set of operations. A full specification is obtained by composing several views, linking them through their states (by asserting invariants across views) and through their operations (by defining external operations as combinations of operations from different views). By encouraging multiple representations of the program's state, view structuring lends clarity and terseness to the specification of operations. And by separating different aspects of functionality, it brings modularity at the grossest level of organization, so that specifications can accommodate change more gracefully. View structuring in Z is demonstrated with a few small examples. Both the features of Z that lend themselves to view structuring and those that are a hindrance are discussed.

The field of distributed systems is now entering a stage of maturity with work focusing on standards for Open Distributed Processing (ODP). However, it is still important that standardization remains responsive to new technological demands such as the emergence of distributed multimedia computing. This paper focuses on the likely impact of multimedia computing on formal description within ODP. In particular, a framework is proposed for the formal specification and verification of quality of service and more general real-time concerns in distributed multimedia systems. This framework exhibits a separation of concerns between the specification of behaviour and requirements and also between the specification of abstract behaviour and real-time concerns. The usefulness of this framework is demonstrated by the development of an approach based on LOTOS together with a real-time temporal logic, QTL.

This paper describes the rationale for integrating a structured systems analysis method (SSADM, version 4) and a formal notation (Z). It introduces the SAZ Method and shows how this can be used to add rigour to the specification of the system state and processing in SSADM. The paper concludes by summarizing the results of using SAZ on a number of case studies.

Proving program correctness has a significant side-benefit of leading the step-wise systematic development of programs. Correctness is proved formally using predicate logic, which requires certain mathematical maturity from the programmer. This work proposes a diagrammatic reasoning tool for representing the predicates, with a minimal blend of symbolic notation, thus providing an easy-to-use tool to achieve the same benefit. We also build a software tool that could be used for drawing the diagrammatic predicates in the course of the construction of the program.

A QuickCheck property is a logical statement of aspects of the behaviour of a system. We report on how similar test cases in a test suite written in Erlang can be identified and then refactored into properties, giving a generalisation of the specification implicit in the test suite. Properties give more concise, easier to maintain test suites and better test coverage. A preliminary evaluation of the techniques in industry demonstrates feasibility as well as potential benefits.A QuickCheck property is a logical statement of aspects of the behaviour of a system. We report on how similar test cases in a test suite written in Erlang can be identified and then refactored into properties, giving a generalisation of the specification implicit in the test suite. Properties give more concise, easier to maintain test suites and better test coverage. A preliminary evaluation of the techniques in industry demonstrates feasibility as well as potential benefits

The choice of solution, which a systems architect is confronted with within the framework of a product structure definition, can very quickly prove to be a thorny problem owing to the possible combinatorial system. In this paper, we will offer an alternative resting on the utilization of constraint-based programming techniques for representing and managing such complexity. More precisely, we will dwell on the presentation of a constraint-based approach to the composition relation management of a product class in design. After setting forth all the potential of the constraint-based approach, we will formally explain, in more detail, the six types of relations that seem to be essential to building a class of products. The approach is based on a three-level architectural model. The first level concerns the product model as such, the second supplies a formal representation of this model, whereas the third consists of rendering an arithmetic constraint-based approach to the intermediate model. We will use the discrete constraint satisfaction problems for operating and solving the latter. Our overall approach, from product modeling to resolution, is intended to be a generic one and the case in point will be the design of a functional pivot link between a connecting rod and a piston. The architect can subsequently make his own choices and the tool will automate their propagation by means of the constraint network modeling the problem. A dimensioning architectural model is, thus, obtained in compliance with the original list of requirements.

Software automation has been viewed as a revolutionary way to improve the dependability and productivity of software. The paper takes the sorting algorithms as study cases, employs PAR method and generic techniques, and derives two abstract generic sorting algorithmic programs, from which a class of concrete sorting algorithmic programs can be generated automatically through operation replacement. And further specialized programs can be produced in multiple languages from a single copy of the instantiated algorithmic program automatically by means of the PAR platform.

The task of software production is to build software systems which are to fulfil certain requirements. For years the approach has been to build up by trial and error a program which, having satisfied carefully prepared test data, offers a plausible solution to the problem. But is it correct? Even for toy examples this is not obvious. In particular, it is often not even clear whether the original problem has been fully understood. The reason for this dilemma is that the transition from the informal problem statement to the final program is too big to be intellectually managable. To master these problems, we advocate a software development method where the whole process is split into smaller steps by introducing formal specifications for (parts of) the problem and then stepwisely deriving efficient programs by correctness-preserving transformations.

SPECIFIER, an interactive system which derives formal specifications of data types and programs from their informal descriptions, is described. The process of deriving formal specifications is viewed as a problem-solving process. The system uses common problem-solving techniques such as schemas, analogy, and difference-based reasoning to derive formal specifications. If an informal description is a commonly occurring operation for which the system has a schema, then the formal specification is derived by instantiating the schema. If there is a no such schema, SPECIFIER tries to find a previously solved problem which is analogous to the current problem. If the problem found is directly analogous to the current problem, it applies an analogy mapping to obtain a formal specification. On the other hand, if the analogy found is only approximate, it solves the directly analogous part of the problem by analogy and performs difference-based reasoning using the remaining (unmatched) parts to transform the formal specification obtained by analogy to a formal specification for the entire original problem. >

The numerous benefits of automatic application code generation are widely accepted within the software engineering community. A few of these benefits include raising the abstraction level of application programming, shorter product development time, lower maintenance costs, and increased code quality and consistency. Surprisingly, code generation concepts have not yet found wide acceptance and use in the field of programmable logic controller (PLC) software development. Software engineers at the NASA Kennedy Space Center (KSC) recognized the need for PLC code generation while developing their new ground checkout and launch processing system. They developed a process and a prototype software tool that automatically translates a high-level representation or specification of safety critical application software into ladder logic that executes on a PLC. This process and tool are expected to increase the reliability of the PLC code over that which is written manually, and may even lower life-cycle costs and shorten the development schedule of the new control system at KSC. This paper examines the problem domain and discusses the process and software tool that were prototyped by the KSC software engineers.

VERITAS/sup +/, a specification logic based on dependent types, is described. The overall aim is to demonstrate how the use of dependent types together with subtypes and datatypes allows the writing of specifications that are clear, concise, and generic. The development of theories of arithmetic, numerals, and iterative structures is described, and the proof of a theorem that greatly simplifies the formal verification of iterative arithmetic structures is outlined. The VERITAS/sup +/ logic is defined by modeling it as a partial algebra within a purely functional metalanguage. Aspects of the computational implementation of the logic and its associated toolset are briefly described. >

For a long time, one of the major research goals in the computer science research community has been to raise the level of abstraction power of specification languages/programming languages. Many specification languages and formalisms have been invented, but unfortunately very few of those are practically useful, due to limited computer support of these languages and/or inefficient implementations. Thus, one important goal is executable specification languages of high abstraction power and with high performance, good enough for practical usage and comparable in execution speed to hand implementations of applications in low-level languages such as C or C++. In this paper we briefly describe our work in creating efficient executable specification languages for two application domains. The first area is formal specification of programming language semantics, whereas the second is formal specification of complex systems for which we have developed an object-oriented mathematical modeling language called Modelica, including architectural support for components and connectors. Based on these efforts, we are currently working on a unified equation-based mathematical modeling language that can handle modeling of items as diverse as programming languages, computer algebra, event-driven systems, and continuous-time physical systems. The key unifying feature is the notion of equation. In this paper we describe the design and implementation of the unified language. A compiler implementation is already up and running, and used for substantial applications.

This paper investigates the rationale for integrating a structured systems analysis method (SSADM version 4) and a formal notation (Z). It describes the integrated specification, and discusses the advantages and disadvantages of formal specification and development for information systems.

This paper presents a formalisation of the steam boiler problem using Circus, a unified theory of the formal specification languages Z and CSP. The aim of Circus is to provide powerful support for the specification of the data-oriented and behavioural aspects of concurrent systems, and to provide a calculational development technique for languages similar to Occam, Java, and Handel-C.

Requirements-to-design-to-code (R2D2C) is an approach to the engineering of computer-based systems that embodies the idea of requirements-based programming in system development. It goes further, however, in that the approach offers not only an underlying formalism, but full formal development from requirements capture through to the automatic generation of provably-correct code. As such, the approach has direct application to the development of systems requiring autonomic properties. We describe a prototype tool to support the method, and illustrate its applicability to the development of LOGOS, a NASA autonomous ground control system, which exhibits autonomic behavior. Finally, we briefly discuss other areas where the approach and prototype tool are being considered for application.

No significant general-purpose method is currently available to mechanically transform system requirements into a provably equivalent model. The widespread use of such a method represents a necessary step toward high-dependability system engineering for numerous application domains. Current tools and methods that start with a formal model of a system and mechanically produce a provably equivalent implementation are valuable but not sufficient. The "gap" unfilled by such tools and methods is that the formal models cannot be proven to be equivalent to the requirements. We offer a method for mechanically transforming requirements into a provably equivalent formal model that can be used as the basis for code generation and other transformations. This method is unique in offering full mathematical tractability while using notations and techniques that are well known and well trusted. Finally, we describe further application areas we are investigating for use of the approach.

We describe a method for combining formal program development with a disciplined and documented way of introducing realistic compromises, for example necessitated by resource bounds. Idealistic specifications are identified with the limits of sequences of more “realistic” specifications, and such sequences can then be refined in their entirety. Compromises amount to focusing the attention on a particular element of the sequence instead of the sequence as a whole. This method addresses the problem that initial formal specifications can be abstract or complete but rarely both. Various potential application areas are sketched, some illustrated with examples. Key research issues are found in identifying metric spaces and properties that make them usable for refinement using approximations.

Global computing involves the interplay of a vast variety of languages, but practially useful foundations for language specification and prototyping at the semantic level are lacking. In this talk we present a systematic approach consisting of three techniques: 1. A generic calculus of explicit substitutions with names (called CINNI) that allows us give a first-order representation of syntax to uniformly deal with all binding aspects. 2. An executable representation of Felleisen-style operational semantics in terms of first-order rewrite rules. 3. A logical framework, namely rewriting logic, that allows us to express (1) and (2) and, in addition, language aspects such as concurrency and non-determinism. We illustrate the use of these techniques in two applications: 1. A formal specification and analysis of PLAN, a Packet Language for Active Networks, that has been developed in the Switchware project at UPenn. This work was conducted in the scope of the DARPA Active Network Program. 2. The development of CIAO, a Calculus of Imperative Active Objects, a core language for concurrent object-oriented programming. It is especially designed to allow a the representation of practically relevant sublanguages of common object-oriented languages such as Java, C#, and C++. This second application is subject of ongoing work.