Jean-Raymond Abrial (6 November 1938 – 26 May 2025), one of the founding figures of modern formal methods in computer science, passed away at the age of 86. His contributions laid the groundwork for mathematically rigorous software development, and his influence spans generations of researchers, engineers, and educators worldwide.

The development of formal methods (FM) in China dates back to the early 1950s, when several logicians shifted their research focus from mathematics to theoretical computer science and began advocating the application of mathematical logic to enhance the rigor of computing systems. A significant expansion of FM in China emerged in the 1980s, pioneered by a new generation of talented computer scientists who had visited, studied, and/or worked in Western countries, such as the United Kingdom and the United States, closely tied to China’s reform and opening-up policy. A notable milestone was the establishment of the United Nations University International Institute for Software Technology (UNU/IIST) in Macau in the early 1990s, which played a crucial role in advancing FM research and collaboration in China. In recent years, the return of an increasing number of talented young scholars has further strengthened China’s FM community, elevating its influence and contribution within the global FM landscape.

Low-rank latent factorization of tensors is a powerful method for analyzing high-dimensional and incomplete (HDI) data derived from cyber-physical systems, particularly when computational resources are limited. However, traditional tensor factorization models are inherently linear and struggle to capture the complex nonlinear spatiotemporal dependencies embedded in the data. This paper introduces a novel latent factorization model, namelyAuto-encodingNeuralTuckerFactorization (ANTucF) for accurate spatiotemporal representation learning on the HDI tensor. It constructs a low-rank Tucker factorization-based neural network to capture a potential latent manifold in space and time, built upon three core ideas: a) applying density-oriented modeling principles with neural networks to facilitate latent feature learning via positional and temporal encoding of mode indices; b) constructing a Tucker interaction tensor to represent all possible spatiotemporal interactions among distinct spatial and temporal modes; and c) enhancing the uniqueness of the core tensor in Tucker factorization by incorporating nonlinear spatiotemporal representation learning via auto-encoding latent interaction learning. The ANTucF model outperforms several state-of-the-art LFT models in estimating missing observations on real-world datasets. Additionally, visualizations demonstrate its ability to capture finer spatiotemporal dynamics by nonlinearly exploiting an optimal Tucker core tensor using a data-driven approach.

Model execution allows us to prototype and analyse software engineering models by stepping through their possible behaviours, using techniques like animation and simulation. On the other hand, deductive verification allows us to construct formal proofs demonstrating satisfaction of certain critical properties in support of high-assurance software engineering. To ensure coherent results between execution and proof, we need unifying semantics and automation. In this article, we mechanise Interaction Trees (ITrees) in Isabelle/HOL to produce an execution and verification framework. ITrees are coinductive structures that allow us to encode infinite labelled transition systems, yet they are inherently executable. We use ITrees to create verification tools for stateful imperative programs, concurrent programs with message passing in the form of the CSP and Circus languages, and abstract system models in the style of the Z and B methods. We demonstrate how ITrees can account for diverse semantic presentations, such as structural operational semantics, a relational program model, and CSP's failures-divergences trace model. Finally, we demonstrate how ITrees can be executed using the Isabelle code generator to support the animation of models.

RoboChart is a core notation in the RoboStar framework. It is a timed and probabilistic domain-specific and state machine-based language for robotics. RoboChart supports shared variables and communication across entities in its component model. It has formal denotational semantics given in CSP. The semantic technique of Interaction Trees (ITrees) represents behaviours of reactive and concurrent programs interacting with their environments. Recent mechanisation of ITrees, ITree-based CSP semantics and a Z mathematical toolkit in Isabelle/HOL bring new applications of verification and animation for state-rich process languages, such as RoboChart. In this paper, we use ITrees to give RoboChart novel operational semantics, implement it in Isabelle, and use Isabelle's code generator to generate verified and executable animations. We illustrate our approach using an autonomous chemical detector and patrol robot models, exhibiting nondeterminism and using shared variables. With animation, we show two concrete scenarios for the chemical detector when the robot encounters different environmental inputs and three for the patrol robot when its calibrated position is in other corridor sections. We also verify that the animated scenarios are trace refinements of the CSP denotational semantics of the RoboChart models using FDR, a refinement model checker for CSP. This ensures that our approach to resolve nondeterminism using CSP operators with priority is sound and correct.

Probabilistic programming combines general computer programming, statistical inference, and formal semantics to help systems make decisions when facing uncertainty. Probabilistic programs are ubiquitous, including having a significant impact on machine intelligence. While many probabilistic algorithms have been used in practice in different domains, their automated verification based on formal semantics is still a relatively new research area. In the last two decades, it has attracted much interest. Many challenges, however, remain. The work presented in this paper, probabilistic unifying relations (ProbURel), takes a step towards our vision to tackle these challenges. Our work is based on Hehner's predicative probabilistic programming, but there are several obstacles to the broader adoption of his work. Our contributions here include (1) the formalisation of its syntax and semantics by introducing an Iverson bracket notation to separate relations from arithmetic; (2) the formalisation of relations using Unifying Theories of Programming (UTP) and probabilities outside the brackets using summation over the topological space of the real numbers; (3) the constructive semantics for probabilistic loops using Kleene's fixed-point theorem; (4) the enrichment of its semantics from distributions to subdistributions and superdistributions to deal with the constructive semantics; (5) the unique fixed-point theorem to simplify the reasoning about probabilistic loops; and (6) the mechanisation of our theory in Isabelle/UTP, an implementation of UTP in Isabelle/HOL, for automated reasoning using theorem proving. We demonstrate our work with six examples, including problems in robot localisation, classification in machine learning, and the termination of probabilistic loops. • A probabilistic semantics unification framework (ProbURel). • A new probabilistic programming language modelling Bayesian learning. • Iteration-based fix-point theorems and unique fix-point theorem for loops. • Mechanised theories in Isabelle/HOL and proved six examples.

Securing a safety-critical system is a challenging task, because safety requirements have to be considered alongside security controls. We report on our experience to develop a security architecture for railway signalling systems starting from the bare ...

Abstract Recently, formal methods have been used in large industrial organisations (including AWS, Facebook/Meta, and Microsoft) and have proved to be an effective part of a software engineering process finding important bugs. Perhaps because of that, practitioners are interested in using them more often. Nevertheless, formal methods are far less applied than expected, particularly for safety-critical systems where they are strongly recommended and have the most significant potential. We hypothesise that formal methods still seem not applicable enough or ready for their intended use in such areas. In critical software engineering, what do we mean when we speak of a formal method? And what does it mean for such a method to be applicable both from a scientific and practical viewpoint? Based on what the literature tells about the first question, with this manifesto, we identify key challenges and lay out a set of guiding principles that, when followed by a formal method, give rise to its mature applicability in a given scope. Rather than exercising criticism of past developments, this manifesto strives to foster increased use of formal methods in any appropriate context to the maximum benefit.

In today’s world, critical infrastructure is often controlled by computing systems. This introduces new risks for cyber attacks, which can compromise the security and disrupt the functionality of these systems. It is therefore necessary to build such systems with strong guarantees of resiliency against cyber attacks. One way to achieve this level of assurance is using formal verification, which provides proofs of system compliance with desired cyber security properties. The use of Formal Methods (FM) in aspects of cyber security and safety-critical systems are reviewed in this article. We split FM into the three main classes: theorem proving, model checking, and lightweight FM. To allow the different uses of FM to be compared, we define a common set of terms. We further develop categories based on the type of computing system FM are applied in. Solutions in each class and category are presented, discussed, compared, and summarised. We describe historical highlights and developments and present a state-of-the-art review in the area of FM in cyber security. This review is presented from the point of view of FM practitioners and researchers, commenting on the trends in each of the classes and categories. This is achieved by considering all types of FM, several types of security and safety-critical systems, and by structuring the taxonomy accordingly. The article hence provides a comprehensive overview of FM and techniques available to system designers of security-critical systems, simplifying the process of choosing the right tool for the task. The article concludes by summarising the discussion of the review, focusing on best practices, challenges, general future trends, and directions of research within this field.

Abstract RoboChart is a timed domain-specific language for robotics, distinctive in its support for automated verification by model checking and theorem proving. Since uncertainty is an essential part of robotic systems, we present here an extension to RoboChart to model uncertainty using probabilism. The extension enriches RoboChart state machines with probability through a new construct: probabilistic junctions as the source of transitions with a probability value. RoboChart has an accompanying tool, called RoboTool, for modelling and verification of functional and real-time behaviour. We present here also an automatic technique, implemented in RoboTool, to transform a RoboChart model into a PRISM model for verification. We have extended the property language of RoboTool so that probabilistic properties expressed in temporal logic can be written using controlled natural language.

Simulation and formal verification are important complementary techniques necessary in high assurance model-based systems development. In order to support coherent results, it is necessary to provide unifying semantics and automation for both activities. In this paper we apply Interaction Trees in Isabelle/HOL to produce a verification and simulation framework for state-rich process languages. We develop the core theory and verification techniques for Interaction Trees, use them to give a semantics to the CSP and Circus languages, and formally link our new semantics with the failures-divergences semantic model. We also show how the Isabelle code generator can be used to generate verified executable simulations for reactive and concurrent programs.

No abstract available.

No abstract available.

Abstract Machines, such as mobile robots and delivery drones, incorporate controllers responsible for a task while handling risk (e.g. anticipating and mitigating hazards; preventing and alleviating accidents). We refer to machines with this capability as risk-awaremachines. Risk awareness includes robustness and resilience and complicates monitoring (i.e., introspection, sensing, prediction), decision making, and control. From an engineering perspective, risk awareness adds a range of dependability requirements to system assurance . Such assurance mandates a correct-by-construction approach to controller design, based on mathematical theory.We introduce RiskStructures, an algebraic framework for risk modelling intended to support the design of safety controllers for risk-aware machines. Using the concept of a risk factor as a modelling primitive, this framework provides facilities to construct, examine, and assure these controllers.We prove desirable algebraic properties of these facilities, and demonstrate their applicability by using them to specify key aspects of safety controllers for risk-aware automated driving and collaborative robots.

Abstract We provide a new approach to synthesize controllers for nonlinear continuous dynamical systems with control against safety properties. The controllers are based on neural networks (NNs). To certify the safety property we utilize barrier functions, which are represented by NNs as well. We train the controller-NN and barrier-NN simultaneously, achieving a verification-in-the-loop synthesis. We provide a prototype tool nncontroller with a number of case studies. The experiment results confirm the feasibility and efficacy of our approach.

Advances in sensing, communications and data analytics have made it possible to construct virtual replicas of Cyber-Physical Systems (CPSs). Such replicas, known as digital twins, can in principle inform decision making during operation and evolution of the systems they model. This short paper introduces the ISoLA 2020/21 series of papers on the technology and practice of engineering digital twins for CPSs. The focus is on the relationship between model-based design, machine learning, digital twins and CPSs.

A digital twin for a Cyber-Physical System includes a simulation model that predicts how a physical system should behave. We show how to quantify and characterise violation events for a given safety property for the physical system. The analysis uses the digital twin to inform a runtime monitor that checks whether the noise and violations observed fall within expected statistical distributions. The results allow engineers to determine the best system configuration through what-if analysis. We illustrate our approach with a case study of an agricultural vehicle.

Many applications in emerging scenarios, such as autonomous vehicles, intelligent robots, and industrial automation, are safety-critical with strict timing requirements. However, the development of real-time systems is error prone and highly dependent on sophisticated domain expertise, making it a costly process. This article utilises the principles of model-driven engineering (MDE) and proposes two methodologies to automate the development of real-time Java applications. The first one automatically converts standard time-sharing Java applications to real-time Java applications, using a series of transformations. It is in line with the observed industrial trend, such as for the big data technology, of redeveloping existing software without the real-time notion to realise the real-time features. The second one allows users to automatically generate real-time Java application templates with a lightweight modelling language, which can be used to define the real-time properties—essentially a synthesis process. This article opens up a new research direction on development automation of real-time programming languages and inspires many research questions that can be jointly investigated by the embedded systems, programming languages as well as MDE communities.

Robots are becoming ubiquitous: from vacuum cleaners to driverless cars, there is a wide variety of applications, many with potential safety hazards. The work presented in this paper proposes a set of constructs suitable for both modelling robotic applications and supporting verification via model checking and theorem proving. Our goal is to support roboticists in writing models and applying modern verification techniques using a language familiar to them. To that end, we present RoboChart, a domain-specific modelling language based on UML, but with a restricted set of constructs to enable a simplified semantics and automated reasoning. We present the RoboChart metamodel, its well-formedness rules, and its process-algebraic semantics. We discuss verification based on these foundations using an implementation of RoboChart and its semantics as a set of Eclipse plug-ins called RoboTool.

Cyber-Physical Systems (CPSs) [ 1 ] connect the real world to software systems through a network of sensors and actuators in which physical and logical components interact in complex ways. There is a diverse range of application domains [ 2 ], including health [ 3 ], energy [ 4 ], transport [ 5 ], autonomous vehicles [ 6 ] and robotics [ 7 ]; and many of these include safety critical requirements [ 8 ]. Such systems are, by definition, characterised by both discrete and continuous components. The development and verification processes must, therefore, incorporate and integrate discrete and continuous models. The development of techniques and tools to handle the correct design of CPSs has drawn the attention of many researchers. Continuous modelling approaches are usually based on a formal mathematical expression of the problem using dense reals and differential equations to model the behaviour of the studied hybrid system. Then, models are simulated in order to check required properties. Discrete modelling approaches rely on formal methods, based on abstraction, model-checking and theorem proving. There is much ongoing research concerned with how best to combine these approaches in a more coherent and pragmatic fashion, in order to support more rigorous and automated hybrid-design verification. It is also possible to combine different discrete-event and continuous-time models using a technique called co-simulation. This has been supported by different tools and the underlying foundation for this has been analysed. Thus, the track will also look into these areas as well as the industrial usage of this kind of technology.

No abstract available.

Abstract FreeRTOS is an open-source real-time microkernel that has a wide community of users. We present the formal specification of the behaviour of the task part of FreeRTOS that deals with the creation, management, and scheduling of tasks using priority-based preemption. Our model is written in the Z notation, and we verify its consistency using the Z/Eves theorem prover. This includes a precise statement of the preconditions for all API commands. This task model forms the basis for three dimensions of further work: (a) the modelling of the rest of the behaviour of queues, time, mutex, and interrupts in FreeRTOS; (b) refinement of the models to code to produce a verified implementation; and (c) extension of the behaviour of FreeRTOS to multi-core architectures. We propose all three dimensions as benchmark challenge problems for Hoare’s Verified Software Initiative.

Abstract A model checker is an automatic tool that traverses a specific structure (normally a Kripke structure referred as the modelM) to check the satisfaction of some (temporal) logical propertyf. This is formally stated as M⊧f . For some formal notations, the modelMof a specificationS(written in a formal languageL) can be described as a labelled transition system (LTS). Specifically, it is not clear in general how usual tools such as SPIN, FDR, PAT, etc., create the LTS representation from a given process. Although one expects the coherence of the LTS generation with the semantics ofL, it is completely hidden inside the model checker itself. In this paper we show how to create a model checker forL, using a development approach based on its operational semantics. We use a systematic semantics embedding and the formal modeling using logic programming and analysis (FORMULA) framework to this end. We illustrate our strategy considering the formal language COMPASS modelling language (CML)—a new language that was based on CSP, VDM and the refinement calculus proposed for modelling and analysis of systems of systems. As FORMULA is based on satisfiability modulo theories solving, our model checker can handle communications and predicates involving data with infinite domains by building and manipulating a symbolic LTS. This goes beyond the capabilities of traditional CSP model checkers such as FDR and PAT. Moreover, we show how to reduce time and space complexities by simple semantic modifications in the embedding. This allows a more semantics-preserving tuning. Finally, we show a real implementation of our model checker in an integrated development platform for CML and its practical use on an industrial case study.

No abstract available.

Abstract Many tools can check if a test set provides control coverage; they are, however, of little or no help when coverage is not achieved and the test set needs to be completed. In this paper, we describe how a formal characterisation of a coverage criterion can be used to generate test data; we present a procedure based on traditional programming techniques like normalisation, and weakest precondition calculation. It is a basis for automation using an algebraic theorem prover. In the worst situation, if automation fails to produce a specific test, we are left with a specification of the compliant test sets. Many approaches to model-based testing rely on formal models of a system under test. Our work, on the other hand, is not concerned with the use of abstract models for testing, but with coverage based on the text of programs.

Multicore processors are ubiquitous. Their use in embedded systems is growing rapidly, and given the constraints on uniprocessor clock speeds, their importance in meeting the demands of increasingly processor-intensive embedded applications cannot be understated. To harness this potential, system designers need to have available to them embedded operating systems with built-in multicore support for widely available embedded hardware. This paper documents our experience of adapting FreeRTOS, a popular embedded real-time operating system, to support multiple processors. A working multicore version of FreeRTOS that is able to schedule tasks on multiple processors as well as provide full mutual-exclusion support for use in concurrent applications is presented. Mutual exclusion is achieved in an almost completely platform-agnostic manner, preserving one of FreeRTOS's most attractive features: portability. Copyright © 2013 John Wiley & Sons, Ltd.

Abstract Safety-Critical Java (SCJ) is a version of Java for real-time programming, restricted to facilitate certification of implementations of safety-critical systems. Its development is the result of an international effort involving experts from industry and academia. What we provide here is, as far as we know, the first formalisation of the SCJ model of memory regions. We use Hoare and He’s unifying theories of programming (UTP), enabling the integration of our theory with refinement models for object orientation and concurrency. In developing the SCJ theory, we also make a contribution to UTP by providing a general theory of invariants (an instance of which is used in the SCJ theory). The results presented here are a first essential ingredient to formalise the novel programming paradigm embedded in SCJ, and enable the justification and development of formal reasoning techniques based on refinement.

Abstract The increasing interest in the combination of different computational paradigms is well represented by Hoare and He in the Unifying Theories of Programming (UTP). In this paper, we present a mechanisation of part of that work in a theorem prover, ProofPower-Z; the theories of alphabetised relations, designs, reactive and CSP processes are in the scope of this paper. Furthermore, the mechanisation of Circus , a language that combines Z, CSP, specification statements and Dijkstra’s guarded command language, is also presented here. We also present an account of how this mechanisation is achieved, and more interestingly, of what issues were raised, and of our decisions. We aim at providing tool support not only for CSP and Circus , but also for further explorations of Hoare and He’s unification, and for the mechanisation of languages whose semantics is based on the UTP.

No abstract available.

The INESS (Integrated European Signalling System) Project, funded by the FP7 programme of the European Union, aims to provide a common, integrated, railway signalling system within Europe. INESS experts have been using the Executable UML (xUML) language to model an executable specification of the proposed system. Due to safety-critical aspects of these systems, one key idea is to formally analyse them. In this context, we have been working with other universities on different translation-based methods that enable the formal verification of xUML models. At the core of this approach is a verification framework based on model transformation technology, used to implement an automatic and transparent verification method for xUML. Since a translation-based approach is used, a key aspect to achieve transparency is the automatic generation of counter-examples for verified properties that have a false result during the analysis, in terms of the original xUML model. We describe in this paper how we achieve this using model transformation technology.

Timed Circus is a compact extension to Circus, that is, it inherits only the CSP part of Circus while introducing time. Although it looks much like timed CSP from the viewpoint of syntax, its semantics is very different from that of timed CSP because it uses a complete lattice in the implication ordering instead of the complete partial order of the standard failures-divergences model of CSP. The complete lattice gives rise to a number of strange processes which violate some axioms of CSP, especially when the miracle (the top element) and SKIP meet time. In this paper, compared with timed CSP, we will extensively explore such strange processes which turn out to be very useful in specifying a distinct property that "something must occur". Finally, we use a simple example to demonstrate how our model can contribute to modelling temporal behaviours with multiple time scales in complex systems.

The importance of verification for software products is being increasingly appreciated in industry, although still not as much as necessary to become a standard development approach for industrial-scale high-quality software.In 2005, a global initiative was started by eminent researchers in both industry and academia, with the aim of establishing and disseminating a culture of software verification from the first principles by means of theories, tools and experiments.This special issue contains a selection of contributions originally presented at the 2008 Workshop on Tools at VSTTE 2008, the conference on Verified Software: Theories, Tools and Experiments in Toronto.The VSTTE series of conferences and workshops focuses on the challenge of verifying software systems.Within VSTTE, the scope of the Tools workshop includes implementations and enabling techniques for program verifiers, which are important ingredients for the dissemination of principles and techniques among industrial practitioners.This special issue complements a sister special issue of the Journal on Software Tools For Technology Transfer (STTT) [STT10].The FAC papers address the foundational aspects of tool-based verification, whereas the STTT selection focuses on practical aspects.The general public perceives the quality of software products as a major issue.In fact, the cost of software construction is dominated by the process of debugging it and validating that the software meets the desired requirements.Due to the prohibitive cost of manual inspection, it is widely believed that computers themselves need to be part of the solution.To this end, Tony Hoare's Grand Challenge for computing research proposes the Verifying Compiler, that is, computer-implemented algorithms that validate the correctness of a given program [Hoa03].In the Manifesto of the Grand Challenge, presented at VSTTE 2005 [MW08, Coo07], the first in the series of VSTTE conferences and workshops, Tony Hoare and Jay Misra directly recognise and appraise the importance of tools as vehicles for the transmission of knowledge to practitioners.In the second paragraph of the introduction, they write: "This paper argues that the time is ripe to embark on an international Grand Challenge project to construct a program verifier that would use logical proof to give an automatic check of the correctness of programs submitted to it.Prototypes for the program verifier will be based on a sound and complete theory of programming; they will be supported by a range of program construction and analysis tools; and the entire toolset will be evaluated and evolve by experimental application to a large and widely representative sample of useful computer programs.The project will provide the scientific basis of a solution for many of the problems of programming error that afflict all builders and users of software today."The paper also suggested that the achievement of this vision should be accelerated by a major international research initiative, modelled on a Grand Challenge, with specific measurable goals.The suggested measure was one million lines of verified code, together with its specifications, designs, assertions, and other artifacts.

No abstract available.

We propose a timed model of Circus which is a compact extension of original Circus. Apart from introducing time, this model uses UTP-style semantics to describe each process as a reactive design. One of significant contributions of our timed model is to extensively explore the reactive design miracle, the top element of a complete lattice with respect to the implication ordering. The employment of the miracle brings a number of brand-new features such as deadline and urgent events, which provide a more powerful and flexible expressiveness in system specifications.

A software development process is effectively an abstract form of model transformation, starting from an end-user model of requirements, through to a system model for which code can be automatically generated. The success (or failure) of such a transformation depends substantially on obtaining a correct, well-formed initial model that captures user concerns. Model-based testing automates black box testing based on the model of the system under analysis. This paper proposes and evaluates a novel model-based testing technique that aims to reveal specification/requirement-related errors by generating test cases from a test model and exercising them on the design model. The case study outlined in the paper shows that a separate test model not only increases the level of objectivity of the requirements, but also supports the validation of the system under test through test case generation. The results obtained from the case study support the hypothesis that there may be discrepancies between the formal specification of the system modeled at developer end and the problem to be solved, and using solely formal verification methods may not be sufficient to reveal these. The approach presented in this paper aims at providing means to obtain greater confidence in the design model that is used as the basis for code generation.

We explore the interactions between program-variable state visibility and communication behaviour in state-rich CSP-like processes, using the Unifying Theories of Programming (UTP) framework. The key results of this work are: having variable state visible while a process is waiting to communicate, results in an operationally complex theory of behaviour; by contrast, considering state as unobservable during communication wait periods results in an elegant theory, with much cleaner operational intuitions. The language constructs most affected by this observability choice are those of external choice and parallel composition. We also discuss situations where this state hiding can prevent the adoption of interesting operators that seize control from waiting processes.

Abstract We describe: (1) the internal structures of FDR, the refinement model checker for Hoare’s Communicating Sequential Processes (CSP); and (2) an application-programming interface (API) that allows users to interact more closely with FDR and to have finer-grain control over its behaviour and data structures. This API makes it possible to create optimised CSP code to perform refinement checks that are more space or time efficient, enabling the analysis of more complex and data-intensive specifications. The API can be used either by those constructing CSP models or by tools that automatically generate CSP code. We present examples of using our tool, including handling advanced FDR features such as transparent functions, which compress state spaces before checking. We also show how to transform FDR’s graph format into a graph notation such as JGraph, enabling visualisation of labelled transition systems of CSP specifications.

Abstract Circus specifications define both data and behavioural aspects of systems using a combination of Z and CSP constructs. Previously, a denotational semantics has been given to Circus; however, a shallow embedding of Circus in Z, in which the mapping from Circus constructs to their semantic representation as a Z specification, with yet another language being used as a meta-language, was not useful for proving properties like the refinement laws that justify the distinguishing development technique associated with Circus. This work presents a final reference for the Circus denotational semantics based on Hoare and He’s Unifying Theories of Programming (UTP); as such, it allows the proof of meta-theorems about Circus including the refinement laws in which we are interested. Its correspondence with the CSP semantics is illustrated with some examples. We also discuss the library of lemmas and theorems used in the proofs of the refinement laws. Finally, we give an account of the mechanisation of the Circus semantics and of the mechanical proofs of the refinement laws.

No abstract available.

We present a research roadmap for the second pilot project in the Verified Software Grand Challenge on formally verified POSIX file stores. The work is inspired by the requirements for NASA's forthcoming Mars Rover missions. The roadmap describes an integrated and comprehensive body of work, including current work, as well as further opportunities for collaboration.

The International Grand Challenge in Verified Software is benchmarking current verification technology by conducting a series of experiments, and one such experiment is to build a verified POSIX-compliant flash filestore. An objective of this experiment is to combine different formal methods, and this raises issues about the different logics used. One significant area of difference is in the treatment of undefined expressions, and we show how this difference can be overcome using a unifying theory. This then allows us to use a theorem proverfor Z to verify theorems about a data type specified and refined in VDM.

Abstract We describe our experiences in mechanising the specification, refinement, and proof of the Mondex Electronic Purse using the Z/Eves theorem prover. We took a conservative approach and mechanised the original L a T E X sources without changing their technical content, except to correct errors. We found problems in the original specification and some missing invariants in the refinements. Based on these experiences, we present novel and detailed guidance on how to drive Z/Eves successfully. The work contributes to the Repository for the Verified Software Grand Challenge.

This issue of Formal Aspects is devoted to an experiment conducted as part of the world-wide Grand Challenge in Verified Software.The challenge is to achieve a significant body of verified programs that have precise external specifications, complete internal specifications, and machine-checked proofs of correctness with respect to a sound theory of programming.The first pilot project in the challenge was to mechanise the proof of correctness of the Mondex smart-card for electronic finance.Eight international research groups tackled the problem, and the following papers record the experiences of six of these groups.The pilot project remains open for other groups to contribute. The certification of the Mondex electronic purse to ITSEC Level E6Woodcock, Stepney, Cooper, Clark, and Jacob were all involved in the original work on Mondex; the first three were specifiers and the last two evaluators.They recall the work that led to the successful certification of the Mondex electronic purse, and the research that this inspired.The paper contains an introduction to the Mondex specification and refinement, and an overview of the proof. Mondex, an electronic purse: specification and refinement checks with the Alloy model-finding methodRamananandro started from the existing specification on Mondex in Z, and constructed a specification in the Alloy specification language, which is based on relational first-order logic with transitive closures.The experiment shows that, if the concerns about finiteness are dropped, then the Mondex specification can be expressed in first-order logic without transitive closures.Ramananandro checked the specification with the Alloy Analyser, a tool for finding models.The Analyser translates the specification into a boolean formula, which it then tries to satisfy.If an assignment of variables is found, then the program translates it back to get a counterexample.This can be accomplished only for bounded numbers of objects: their scope.The specification has been checked for a scope of at most eight objects of each kind.The analysis found several bugs in Mondex: (i) purses can hold unauthentic transaction details; (ii) a wrong case analysis in a proof; (iii) a mistake in a framing schema.

Abstract. Ten years ago the Mondex electronic purse was certified to ITSEC Level E6, the highest level of assurance for secure systems. This involved building formal models in the Z notation, linking them with refinement, and proving that they correctly implement the required security properties. The work has been revived recently as a pilot project for the international Grand Challenge in Verified Software. This paper records the history of the original project and gives an overview of the formal models and proofs used.

We present first steps in the construction of formal models of NAND flash memory, based on a recently emerged open standard for such devices. The model is at a level of abstraction that captures the internal architecture of such a device, as well as the commands that are used to operate it. The model is intended as a key step in a plan to develop a verified filestore system, by providing a description of the hardware devices that would be used in it implementation.

We present results from the second pilot project in the international Verification Grand Challenge: a formally verified specification of a POSIX-compliant file store using the Z/Eves theorem prover. The project's overall objective is to build a verified file store for space-flight missions. Our specification of the file store is based on Morgan & Sufrin's specification of the UNIX filing system; the proof and its mechanisation in Z/Eves are novel. We show how our work contributes towards building a verified software repository: a set of general theories and experiments reusable across different domains.

Parts of the CICS transaction processing system were modelled formally in the 1980s in a collaborative project between IBM Hursley Park and Oxford University Computing Laboratory. Z was used to capture a precise description of the behaviour of various modules as a means of communicating requirements and design intentions. These descriptions were not mechanically verified in any way: proof tools for Z were not considered mature, and no business case was made for effort in this area. We report a recent experiment on using the Z/Eves mechanical theorem prover to construct a machine-checked analysis of one of the CICS modules: the File Control API. This work was carried out as part of the international Grand Challenge in Verified Software, and our results are recorded in the Verified Software Repository. We give a brief description of the other modules, and propose them as challenge problems for the verification community.

No abstract available.

Summary form only given. The computer science research community is collaborating to develop verification technology that will demonstrably enhance the productivity and reliability with which software is designed, developed, integrated, and maintained

Abstract The verified software repository is dedicated to a long-term vision of a future in which all computer systems justify the trust that society increasingly places in them. This would be accompanied by a substantial reduction in the current high costs of programming error, incurred during the design, development, testing, installation, maintenance, evolution, and retirement of computer software. An important technical contribution to this vision will be a verifying compiler: a tool-set that automatically proves that a program will always meet its specification, insofar as this has been formalised, without even needing to run it. This has been a challenge for computing research for over 30 years, but the current state of the art now gives grounds for hope that it may be implemented in the foreseeable future. Achievement of the overall vision will depend also on continued progress of research into dependability and software evolution, as envisaged by the UKCRC Grand Challenge project in dependable systems evolution . The verified software repository is a first step towards the realisation of this long-term vision. It will maintain and develop an evolving collection of state-of-the-art tools, together with a representative portfolio of real programs and specifications on which to test, evaluate, and develop the tools. It will contribute initially to the inter-working of tools, and eventually to their integration. It will promote transfer of the relevant technology to industrial tools and into software engineering practice. It will build on the recognised achievements of practical formal development of safety-critical computer applications, and contribute to an international initiative in verified software, covering theory, tools, and experimental validation.

Abstract Hoare and He’s unifying theories of programming (UTP) is a model of alphabetised relations expressed as predicates; it supports development in several programming paradigms. The aim of Hoare and He’s work is the unification of languages and techniques, so that we can benefit from results in different contexts. In this paper, we investigate the integration of angelic nondeterminism in the UTP; we propose the unification of a model of binary multirelations, which is isomorphic to the monotonic predicate transformers model and can express angelic and demonic nondeterminism.

Abstract We present a refinement strategy for Circus , which is the combination of Z, CSP, and the refinement calculus in the setting of Hoare and He’s unifying theories of programming. The strategy unifies the theories of refinement for processes and their constituent actions, and provides a coherent technique for the stepwise refinement of concurrent and distributed programs involving rich data structures. This kind of development is carried out using Circus ’s refinement calculus, and we describe some of its laws for the simultaneous refinement of state and control behaviour, including the splitting of a process into parallel subcomponents. We illustrate the strategy and the laws using a case study that shows the complete development of a small distributed program.

Abstract. Morgan's refinement calculus is a successful technique for developing software in a precise and consistent way. This technique, however, can be hard to use, as developments may be long and repetitive. Many authors have pointed out that a lot can be gained by identifying commonly used development strategies, documenting them as tactics, and using them as single transformation rules. Also, it is useful to have a notation for describing derivations, so that they can be analysed and modified. In this paper, we present ArcAngel, a language for defining such refinement tactics; we present the language, its semantics, and some of its algebraic laws. Apart from Angel, a general-purpose tactic language that we are extending, no other tactic language has a denotational semantics and proof theory of its own.

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.

Abstract. Formal methods are coming of age: mathematical techniques and tools are now regarded as an important part of the development process in a wide range of industrial and governmental organisations. A transfer of technology into the mainstream of systems development is slowly, but surely, taking place. FM'99, the First World Congress on Formal Methods in the Development of Computing Systems, was a result and a measure of this new-found maturity. It brought together an impressive array of industrial and applications-oriented papers that show how formal methods have been used to tackle real problems. The proceedings are published as Volumes 1708 and 1709 in Springer-Verlag's Lecture Notes in Computer Science. These proceedings are a record of the technical symposium of FM'99. Alongside the papers describing applications of formal methods, you will find technical reports, papers, and abstracts detailing new advances in formal techniques, from mathematical foundations to practical tools. After the World Congress, we decided that many papers deserved a wider audience, and we created an opportunity for their authors to revise and extend their work. The proceedings contain over one hundred papers, and we decided to publish twelve of them simultaneously in special issues of three journals: Formal Aspects of Computing, Formal Methods in System Design, and IEEE Transactions in Software Engineering. The papers selected are among the best submitted to FM'99, and were subjected to a rigorous second review process involving leading international academic and industrial researchers.

Formal methods are coming of age: mathematical techniques and tools are now regarded as an important part of the development process in a wide range of industrial and governmental process in a wide range of industrial and governmental organizations. A transfer of technology into the mainstream development is slowly but surely taking place. (Introduction).

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.

Abstract. The fact that Z is a specification language only, with no associated program development method, is a widely recognised problem. As an answer to that, we present ZRC, a refinement calculus based on Morgan's work that incorporates the Z notation and follows its style and conventions. This work builds upon existing refinement techniques for Z, but distinguishes itself mainly in that ZRC is completely formalised. In this paper, we explain how programs can be derived from Z specifications using ZRC. We present ZRC-L, the language of our calculus, and its conversion laws, which are concerned with the transformation of Z schemas into programs of this language. Moreover, we present the weakest precondition semantics of ZRC-L, which is the basis for the derivation of the laws of ZRC. More than a refinement calculus, ZRC is a theory of refinement for Z.

Abstract We present a very general language for expressing tactic programs. The paper describes some essential tactic combinators (tacticals), and gives them a formal semantics. Those definitions are used to produce a complete calculus for reasoning about tactics written in this language. The language is extended to cover structural combinators which enable the tactics to be precisely targeted upon particular sub-expressions.

The standard approach to the specification of a secure system is to present a (usually state-based) abstract security model separately from the specification of the system's functional requirements, and establishing a correspondence between the two specifications. This complex treatment has resulte d in development methods distinct from those usually advocated for general applications. We provide a novel and intellectually satisfying formulation of security properties in a process algebraic framework, and show that these are preserved under refinement. We relate the results to a more familiar state-based (Z) specification methodology. There are efficient algorithms for verifying our security properties using model checking.

Abstract Operations on action systems may be defined corresponding to CSP hiding and renaming. These are of particular use in describing the refinement between action systems in which the granularity of actions is altered. We derive a simplified expression for hiding sets of actions and present sufficient conditions for forwards simulation in which the concrete system uses hiding and renaming. Both of these reduce the complexity of proofs of refinement. We present a case study in specification and refinement using action systems which makes use of the operations and refinement rules previously defined.

We describe the rudiments of algorithm refinement: the business of taking a specification and producing code that correctly implements it. The paper starts with a general discussion of the concepts, and then turns to a particular calculus for algorithm refinement.