Provably Correct Systems


PROCOS II - 7071

Work Area: Theories for Concurrency and Real Time: Specification and Verification

Keywords programming methodology, safety-critical systems, specification languages, programming languages


Start Date: 24 July 92 / Duration: 36 months / Status: running

[ participants / contact ]


Abstract PROCOS II aims to improve dependability, reduce timescales and cut development costs of construction for embedded systems, particularly in real-time and safety-critical applications. It uses and develops the results of basic research into fundamental properties of interactive systems. It aims to provide a scientific basis for future standards of practice in the development of embedded systems, ensuring correctness of all stages in the development, from elicitation and analysis of requirements through design and implementation of programs down to compilation and execution on verified hardware.


Aims

Our overall objectives are to advance the state of the art of systematic design of complex heterogeneous systems, including both software and hardware; in particular, to reduce the risk of error in the specification, design and implementation of embedded safety-critical systems.

To approach this goal, we plan to develop a theory, system and methodology to cover all of the following: (1) Requirements capture and analysis; (2) system specification and design; (3) programming language processing and compilation; (4) a hardware machine, including multiprogramming kernel; (5) an implementation in hardware down to gate level. Support for (4) and (5) have also been provided from national sources.

Approach and Methods

(2), (3) and (4) above were included in ProCoS i. Each level is served by a theory and calculus designed to be at the most appropriate level of abstraction. It seems feasible to embed these separate formalisms in a single abstract mathematical theory, which ensures their mutual consistency, and defines a clear sense in which implementations conform to designs, designs to specifications, and specifications to requirements. This reduces the risk of error due to misunderstanding as a project moves from one phase to the next.

In ProCoS i concepts and proof techniques have been developed by concentrating collaboratively on a rather simple language and simple case studies. At the same time, we have developed theories that promise to deal successfully with a much more ambitious language, encompassing concurrency, communication, timing constraints, recursion, procedures and parameters.

Occam and the transputer have been chosen as the underlying programming language and machine architecture and subsets (or related and compatible supersets) of these are selected for study.

Progress and Results

For the requirements phase, advances are being made in the application and extension of Duration Calculus by considering probabilistic aspects and the problems associated with hybrid systems. We are working towards filling the gap between the requirements and the specification level by adding real-time features to the specification language and also the programming language.

A real-time design calculus is being developed for the transformation of a specification into a program, using a wide spectrum language which encompasses both levels.

The programming language is being designed to express assertions on the timed behaviour of programs. It features delay timing as present in occam and allows the programmer to specify upper bounds for the time spent for the execution of internal actions. A full prototype compiler will be rigorously developed and partially proved correct.

The compilation of occam programs directly into synchronous hardware is being investigated, using Field Programmable Gate Array technology. The proof of correctness depends on using a realistic model of the underlying hardware. We have adopted an approach in which programs are compiled into a normal form that is a very restricted subset of the high level language, but is close to the actual hardware in form.

Overall, a universal model , based on a Z calculus, is being developed to link the various levels in a mathematically coherent manner. A gas burner and other case studies are being used to ensure the consistency and compatibility of the various levels.

Verification support is being used as required. In particular, Lambda, the Larch-based LP proof system, and the OBJ3 and 2OBJ systems are being used in various areas of the project.

Potential

The partners use a selection of these features in somewhat more significant case studies, which are carried through all the stages listed above. ProCoS ii will also seek a simplification of the technology to make it truly useful for engineers, and conduct further theoretical work to spearhead future advances.

Latest Publications

Information Dissemination Activies

A ProCoS tutorial was presented at the Formal Methods Europe Symposium in Denmark, April 1993, and a joint conference with the existing Formal Techniques in Real Time and Fault Tolerant Systems series is planned for September 1994 in Germany.

An associated ProCoS Working Group of interested industrial and academic organisations is planned to aid dissemination of results.

Further information about PROCOS-II is available from the PROCOS-II home page <URL:http://www.comlab.ox.ac.uk/archive/procos/procos2.html>.


Coordinator

Oxford University - UK
Computing Laboratory
11 Keble Road
UK - OXFORD OX1 3QD

Partners

Universität Oldenburg - D
Universität Kiel - D
Technical University of Denmark - DK

CONTACT POINT

Prof. C.A.R. Hoare
tel +44/865 273840
fax +44/865 273839
e-mail: procos@comlab.ox.ac.uk


LTR synopses home page LTR work area index LTR acronym index LTR number index LTR Projects index
All synopses home page all acronyms index all numbers index

PROCOS II - 7071, August 1994


please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook