Critical Systems: Formal Methods and Automated Verification

This paper summarizes our experiences from an exercise in deductive verification of functional properties of automotive embedded C-code in an industrial setting. We propose a formal requirements model that supports the way C-code requirements are currently written at Scania. We describe our work, for a safety-critical module of an embedded system, on formalizing its functional requirements and verifying its C-code implementation by means of VCC, an established tool for deductive verification. We describe the obstacles we encountered, and discuss the automation of the specification and annotation effort as a prerequisite for integrating this technology into the embedded software design process.

Abstract modeling of timing properties is often based on events. An event can be seen as a sequence of times. Timing constraints can then be expressed as constraints on events: an example is the TADL2 language that has been developed in the automotive domain.

Event-based constraints can express timing properties of implementations as well as timing requirements. An important step in timing verification is then to show that any events that comply with the properties of the implementation, i.e., that describe the timings of its possible behaviours, also satisfy the requirements.

Real-time software is often organised as a set of periodically repeating tasks, especially in domains with time-critical systems like automotive and avionics. This implementation naturally yields periodic events, where each event occurrence belongs to a periodically repeating time window. An interesting question is then: if some events are periodic in this fashion, will they then fulfil a timing constraint that describes a timing requirement? We show, for a number of TADL2 timing constraints, how to translate this implication into an equivalent Presburger formula. Since Presburger logic is decidable, this yields an automated method to decide whether the periodic implementation satisfies the timing requirements or not. Initial experiments with a Presburger solver indicate that the method is practical.

The query-checking problem for temporal logic may be formulated as follows. Given a Kripke structure M and a temporal-logic query of form \(\phi \left[ {\texttt {var}}\right] \), which may be thought of as a temporal formula with a missing propositional subformula \({\texttt {var}}\), find the most precise propositional formula f that, when substituted for \({\texttt {var}}\) in \(\phi \left[ {\texttt {var}}\right] \), ensures M satisfies the resulting temporal property. Query checking has been used for system comprehension, specification reconstruction, and other related applications in the formal analysis of systems.

In this paper we present an automaton-based methodology for query checking over linear temporal logic (LTL). While this problem is known to be hard in the general case, we show that by exploiting several key observations about the interplay between the input model M and the query \(\phi \left[ {\texttt {var}}\right] \), we can produce results for many problems of interest. In support of this claim, we report on preliminary experimental data for an implementation of our technique.

Functional failures in Safety Instrumented System (SIS) of offshore platforms may have catastrophic consequences for the production, facility, environment and health. This work presents a method for automatic conformance testing of safety specifications represented in a Cause and Effect Matrix (CEM) for Programmable Logic Controllers (PLC) in charge of SIS. Test cases are automatically designed from the CEM using a CEG-BOR strategy to enhance coverage of black box test. Petri Net models support the automated oracle creation and test result evaluation. An experimental tool has been developed to edit the CEM, to generate and execute test cases on a PLC simulator, to generate and execute the Petri Net oracles and to present the verdict. The method has been applied to test the SIS of an offshore oil platform.

Model-based testing is a prominent validation technique, integrating well with other formal approaches to verification, such as model checking. Automated test derivation and execution approaches often struggle with asynchrony in communication between the implementation under test (IUT) and tester, a phenomenon present in most networked systems. Earlier attacks on this problem came with different restrictions on the specification model side. This paper presents a new and effective approach to model-based testing under asynchrony. By waiving the need to guess the possible output state of the IUT, we reduce the computational effort of the test generation algorithm while preserving soundness and conceptual completeness of the testing procedures. In addition, no restrictions on the specification model need to be imposed. We define a suitable conformance relation and we report on empirical results obtained from an industrial case study from the domain of electric mobility.

High-security processes have to load confidential information into shared resources as part of their operation. This confidential information may be leaked (directly or indirectly) to low-security processes via the shared resource. This paper considers leakage from high-security to low-security processes from the perspective of scheduling. The workflow model is here extended to support preemption, security levels, and leakage. Formalization of leakage properties is then built upon this extended model, allowing formal reasoning about the security of schedulers. Several heuristics are presented in the form of compositional preprocessors and postprocessors as part of a more general scheduling approach. The effectiveness of such heuristics are evaluated experimentally, showing them to achieve significantly better schedulability than the state of the art. Modeling of leakage from cache attacks is presented as a case study.

The schedulability analysis of real-time systems (even on a single processor) is a very difficult task, which becomes even more complex (or undecidable) when periods or deadlines become uncertain. In this work, we propose a unified formalism to model monoprocessor schedulability problems with several types of tasks (periodic, sporadic, or more complex), most types of schedulers (including \(\mathsf {EDF}\), \(\mathsf {FPS}\) and \(\mathsf {SJF}\)), with or without preemption, in the presence of uncertain timing constants. Although the general case is undecidable, we exhibit a large decidable subclass. We demonstrate the expressive power of our formalism on several examples, allowing also for robust schedulability.

This paper presents a method that allows mobile systems with uncertainty in motion and sensing to react to unknown environments while high-level specifications are satisfied. Although previous works have addressed the problem of synthesising controllers under uncertainty constraints and temporal logic specifications, reaction to dynamic environments has not been considered under this scenario. The method uses feedback-based information roadmaps (FIRMs) to break the curse of history associated with partially observable systems. A transition system is incrementally constructed based on the idea of FIRMs by adding nodes on the belief space. Then, a policy is found in the product Markov decision process created between the transition system and a Rabin automaton representing a linear temporal logic formula. The proposed solution allows the system to react to previously unknown elements in the environment. To achieve fast reaction time, a FIRM considering the probability of violating the specification in each transition is used to drive the system towards local targets or to avoid obstacles. The method is demonstrated with an illustrative example.

This paper addresses the problem of path planning for multiple robots under high-level specifications given as syntactically co-safe linear temporal logic formulae. Most of the existing solutions use the notion of abstraction to obtain a discrete transition system that simulates the dynamics of the robot. Nevertheless, these solutions have poor scalability with the dimension of the configuration space of the robots. For problems with a single robot, sampling-based methods have been presented as a solution to alleviate this limitation. The proposed solution extends the idea of sampling methods to the multiple robot case. The method samples the configuration space of the robots to incrementally constructs a transition system that models the motion of all the robots as a group. This transition system is then combined with a Büchi automaton, representing the specification, in a Cartesian product. The product is updated with each expansion of the transition system until a solution is found. We also present a new algorithm that improves the performance of the proposed method by guiding the expansion of the transition system. The method is demonstrated with examples considering different number of robots and specifications.

Swarms of mobile robots have recently attracted the focus of the Distributed Computing community. One of the fundamental problems in this context is that of gathering the robots: the robots must meet at a common location, not known beforehand. Despite its apparent simplicity, this problem proved quite hard to characterise fully, due to many model variants, leading to informal error-prone reasoning.

Over the past few years, a significant effort has resulted in the set up of a formal framework, relying on the Coq proof assistant, that was used to provide certified results related to the gathering problem. We survey the main abstractions that permit to reason about oblivious mobile robots that evolve in a bidimensional Euclidean space, the distributed executions they can perform, and the variants of the gathering problem they can solve, while certifying all obtained results. We also describe the remaining steps to obtain a certified full characterisation of the problem.

We develop a learning-based testing framework for register automaton models that can express the windowing behavior of TCP, thereby presenting the first significant application of register automata learning to realistic software for a class of automata with Boolean-arithmetic constraints over data values. We have applied our framework to TCP implementations belonging to different operating systems and have found a violation of the TCP specification in Linux and Windows. The violation has been confirmed by Linux developers.

The feature interaction problem has been recognized as a general problem of software engineering. The problem appears when a combination of features interacts generating a conflict, exhibiting a behaviour that is unexpected for the features considered in isolation, possibly resulting in some critical safety violation. Verification of absence of critical feature interactions has been the subject of several studies. In this paper, we focus on functional interactions and we address the problem of the 3-way feature interactions, i.e. interactions that occur only when three features are all included in the system, but not when only two of them are. In this setting, we define a widely applicable definition framework, within which we show that a 3 (or greater)-way interaction is always caused by a 2-way interaction, i.e. that pairwise sampling is complete, hence reducing to quadratic the complexity of automatic detection of incorrect interaction.

Dezyne is an industrial language with an associated set of tools, allowing users to model interface behaviours and implementations of reactive components and generate executable code from these. The tool and language succeed the successful ASD:Suite tool set, which, in addition to modelling reactive components, offers a set of verification capabilities allowing users to check the conformance of implementations to their interfaces. In this paper, we describe the Dezyne language and a model transformation to the mCRL2 language, providing users access to advanced model checking capabilities and refinement checks of the mCRL2 tool set.