Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 8th International Symposium on NASA Formal Methods, NFM 2016, held in Minneapolis, MN, USA, in June 2016.
The 19 full and 10 short papers presented in this volume were carefully reviewed and selected from 70 submissions. The papers were organized in topical sections named: requirements and architectures; testing and run-time enforcement; theorem proving and proofs; application of formal methods; code generation and synthesis; model checking and verification; and correctness and certification.

Inhaltsverzeichnis

Frontmatter

Requirements and Architectures

Frontmatter

Temporal Logic Framework for Performance Analysis of Architectures of Systems

Abstract
This paper presents a formal mathematical framework for performance analysis (in terms of success of given tasks) of complex systems, ATLAS. This method interestingly combines temporal aspects (for the description of the complex system) and probabilities (to represent performance). The system’s task to be evaluated is described using a temporal language, the ATLAS language: the architecture of the task is decomposed into elementary functionalities and temporal operators specify their arrangement. Starting with the success probabilities of the elementary functionalities, it is then possible to compute the overall success probability of the task using mathematical formulae which are proven in this paper. The method is illustrated with a deorbitation task for a retired satellite called ENVISAT.
Ariane Piel, Jean Bourrely, Stéphanie Lala, Sylvain Bertrand, Romain Kervarc

On Implementing Real-Time Specification Patterns Using Observers

Abstract
English language requirements are often used to specify the behavior of complex cyber-physical systems. The process of transforming these requirements to a formal specification language is often challenging, especially if the specification language does not contain constructs analogous to those used in the original requirements. For example, requirements often contain real-time constraints, but many specification languages for model checkers have discrete time semantics. Work in specification patterns helps to bridge these gaps, allowing straightforward expression of common requirements patterns in formal languages. In this work we demonstrate how we support real-time specification patterns in the Assume Guarantee Reasoning Environment (AGREE) using observers. We demonstrate that there are subtle challenges, not mentioned in previous literature, to express real-time patterns accurately using observers. We then demonstrate that these patterns are sufficient to model real-time requirements for a real-world avionics system.
John D. Backes, Michael W. Whalen, Andrew Gacek, John Komp

Open Access

Contract-Based Verification of Complex Time-Dependent Behaviors in Avionic Systems

Abstract
Avionic systems involve complex time-dependent behaviors across interacting components. This paper presents a contract-based approach for formally verifying these behaviors in a compositional manner. A unique feature of our contract-based tool is the support of architectural specification for multi-rate platforms. An abstraction technique has also been developed for properties related to variable time bounds. Preliminary results on applying this approach to the verification of an aircraft cabin pressure control system are promising.
Devesh Bhatt, Arunabh Chattopadhyay, Wenchao Li, David Oglesby, Sam Owre, Natarajan Shankar

ARSENAL: Automatic Requirements Specification Extraction from Natural Language

Abstract
Requirements are informal and semi-formal descriptions of the expected behavior of a complex system from the viewpoints of its stakeholders (customers, users, operators, designers, and engineers). However, for the purpose of design, testing, and verification for critical systems, we can transform requirements into formal models that can be analyzed automatically. ARSENAL is a framework and methodology for systematically transforming natural language (NL) requirements into analyzable formal models and logic specifications. These models can be analyzed for consistency and implementability. The ARSENAL methodology is specialized to individual domains, but the approach is general enough to be adapted to new domains.
Shalini Ghosh, Daniel Elenius, Wenchao Li, Patrick Lincoln, Natarajan Shankar, Wilfried Steiner

Testing and Run-Time Enforcement

Frontmatter

Assisted Coverage Closure

Abstract
Malfunction of safety-critical systems may cause damage to people and the environment. Software within those systems is rigorously designed and verified according to domain specific guidance, such as ISO26262 for automotive safety. This paper describes academic and industrial co-operation in tool development to support one of the most stringent of the requirements — achieving full code coverage in requirements-driven testing. We present a verification workflow supported by a tool that integrates the coverage measurement tool RapiCover with the test-vector generator FShell. The tool assists closing the coverage gap by providing the engineer with test vectors that help in debugging coverage-related code quality issues and creating new test cases, as well as justifying the presence of unreachable parts of the code in order to finally achieve full effective coverage according to the required criteria. We illustrate the tool’s practical utility on automotive industry benchmarks. It generates 8\(\times \) more MC/DC coverage than random search.
Adam Nellis, Pascal Kesseli, Philippa Ryan Conmy, Daniel Kroening, Peter Schrammel, Michael Tautschnig

Synthesizing Runtime Enforcer of Safety Properties Under Burst Error

Abstract
We propose a game-based method for synthesizing a runtime enforcer for a reactive system to ensure that a set of safety-critical properties always holds even if errors occur in the system due to design defect or environmental disturbance. The runtime enforcer does not modify the internals of the system or provide a redundant implementation; instead, it monitors the input and output of the system and corrects any erroneous output signal that may cause a safety violation. Our main contribution is a new algorithm for synthesizing a runtime enforcer that can respond to violations instantaneously and guarantee the safety of the system under burst error. This is in contrast to existing methods that either require significant delay before the enforcer can respond to violations or do not handle burst error. We have implemented our method in a synthesis tool and evaluated it on a set of temporal logic specifications. Our experiments show that the enforcer synthesized by our method can robustly handle a wide range of properties under burst error.
Meng Wu, Haibo Zeng, Chao Wang

Compositional Runtime Enforcement

Abstract
Runtime enforcement is a methodology used to enforce that the output of a running system satisfies a desired property. Given a property, an enforcement monitor modifies an (untrusted) sequence of events into a sequence that complies to that property. In practice, we may have not one, but many properties to enforce. Moreover, new properties may arise as new capabilities are added to the system. It then becomes interesting to be able to build not a single, monolithic monitor that enforces all the properties, but rather several monitors, one for each property. The question is to what extent such monitors can be composed, and how. This is the topic of this paper. We study two monitor composition schemes, serial and parallel composition, and show that, while enforcement under these schemes is generally not compositional, it is for certain subclasses of regular properties.
Srinivas Pinisetty, Stavros Tripakis

Open Access

Improving an Industrial Test Generation Tool Using SMT Solver

Abstract
We present an SMT solving based test generation approach for MATLAB Simulink designs, implemented in the HiLiTE tool developed by Honeywell for verification of avionic systems. The test requirements for a Simulink model are represented by a set of behavioral equivalence classes for each block in the model, in terms of its input(s) and output. A unique feature of our approach is that the equivalence class definitions, as well as the upstream subgraph of a block under test, are translated as constraints into SMT expressions. An SMT solver is called at the back-end of HiLiTE to find a satisfiable solution that is further augmented into an end-to-end test case at the model level.
Hao Ren, Devesh Bhatt, Jan Hvozdovic

The comKorat Tool: Unified Combinatorial and Constraint-Based Generation of Structurally Complex Tests

Abstract
This tool paper presents comKorat, which unifies constraint-based generation of structurally complex tests with combinatorial testing. Constraint-based test generation is an effective approach for generating structurally complex inputs for systematic testing. While this approach can typically generate large numbers of tests, it has limited scalability – tests generated are usually only up to a small bound on input size. Combinatorial test generation, e.g., pair-wise testing, is a more scalable approach but is challenging to apply on commercial software systems that require complex input structures that cannot be formed by using arbitrary combinations. The comKorat tool integrates Korat and ACTS test generators to generate test suites for large scale commercial systems. This paper presents a case-study of applying comKorat on a software application developed at Yahoo!. The experimental results show that comKorat outperforms existing solution in execution time and finds a total of 23 previously unknown bugs in the application.
Hua Zhong, Lingming Zhang, Sarfraz Khurshid

Code Generation and Synthesis

Frontmatter

Automated Synthesis of Safe Autonomous Vehicle Control Under Perception Uncertainty

Abstract
Autonomous vehicles have found wide-ranging adoption in aerospace, terrestrial as well as marine use. These systems often operate in uncertain environments and in the presence of noisy sensors, and use machine learning and statistical sensor fusion algorithms to form an internal model of the world that is inherently probabilistic. Autonomous vehicles need to operate using this uncertain world-model, and hence, their correctness cannot be deterministically specified. Even once probabilistic correctness is specified, proving that an autonomous vehicle will operate correctly is a challenging problem. In this paper, we address these challenges by proposing a correct-by-synthesis approach to autonomous vehicle control. We propose a probabilistic extension of temporal logic, named Chance Constrained Temporal Logic (C2TL), that can be used to specify correctness requirements in presence of uncertainty. We present a novel automated synthesis technique that compiles C2TL specification into mixed integer constraints, and uses second-order (quadratic) cone programming to synthesize optimal control of autonomous vehicles subject to the C2TL specification. We demonstrate the effectiveness of the proposed approach on a diverse set of illustrative examples.
Susmit Jha, Vasumathi Raman

Obfuscator Synthesis for Privacy and Utility

Abstract
We consider the problem of synthesizing an obfuscation policy that enforces privacy while preserving utility with formal guarantees. Specifically, we consider plants modeled as finite automata with pre-defined secret behaviors. A given plant generates event strings for some useful computation, but meanwhile wants to hide its secret behaviors from any outside observer. We formally capture the privacy and utility specifications using the automaton model of the plant. To enforce both specifications, we propose an obfuscation mechanism where an edit function “edits” the plant’s output in a reactive manner. We develop algorithmic procedures that synthesize a correct-by-construction edit function satisfying both privacy and utility specifications. To address the state explosion problem, we encode the synthesis algorithm symbolically using Binary Decision Diagrams. We present EdiSyn, an implementation of our algorithms, along with experimental results demonstrating its performance on illustrative examples. This is the first work, to our knowledge, to successfully synthesize controllers satisfying both privacy and utility requirements.
Yi-Chin Wu, Vasumathi Raman, Stéphane Lafortune, Sanjit A. Seshia

Code Generation Using a Formal Model of Reference Counting

Abstract
Reference counting is a popular technique for memory management. It tracks the number of active references to a data object during the execution of a program. Reference counting allows the memory used by a data object to be freed when there are no active references to it. We develop the metatheory of reference counting by presenting an abstract model for a functional language with arrays. The model is captured by an intermediate language and its operational semantics, defined both with and without reference counting. These two semantics are shown to correspond by means of a bisimulation. The reference counting implementation allows singly referenced data objects to be updated in place, i.e., without copying. The main motivation for our model of reference counting is in soundly translating programs from a high-level functional language, in our case, an executable fragment of the PVS specification language, to efficient code with a compact footprint in a small subset of a low-level imperative language like C.
Gaspard Férey, Natarajan Shankar

EventB2Java: A Code Generator for Event-B

Abstract
Event-B is a formal specification language and a methodology used to build software systems. Formal specifications are more useful when they can be executed. An executable formal specification provides insight on the behaviour of the system being modelled w.r.t an expected behaviour. This paper presents a tool that generates executable implementations of Event-B models. The tool is implemented as a plug-in of the Rodin platform, an Eclipse IDE that provides a set of tools to work with Event-B models. Our tool has extensively been used for generating code for Event-B models of Android applications, reactive systems, Smart Cards, searching algorithms, among others. The first author regularly uses EventB2Java in teaching to help master students of Software Engineering to get a better grasp of the behaviour of a model in Event-B and to detect inconsistencies in the model.
Néstor Cataño, Víctor Rivera

Applications of Formal Methods

Frontmatter

A Formally Verified Checker of the Safe Distance Traffic Rules for Autonomous Vehicles

Abstract
One barrier in introducing autonomous vehicle technology is the liability issue when these vehicles are involved in an accident. To overcome this, autonomous vehicle manufacturers should ensure that their vehicles always comply with traffic rules. This paper focusses on the safe distance traffic rule from the Vienna Convention on Road Traffic. Ensuring autonomous vehicles to comply with this safe distance rule is problematic because the Vienna Convention does not clearly define how large a safe distance is. We provide a formally proved prescriptive definition of how large this safe distance must be, and correct checkers for the compliance of this traffic rule. The prescriptive definition is obtained by: (1) identifying all possible relative positions of stopping (braking) distances; (2) selecting those positions from which a collision freedom can be deduced; and (3) reformulating these relative positions such that lower bounds of the safe distance can be obtained. These lower bounds are then the prescriptive definition of the safe distance, and we combine them into a checker which we prove to be sound and complete. Not only does our work serve as a specification for autonomous vehicle manufacturers, but it could also be used to determine who is liable in court cases and for online verification of autonomous vehicles’ trajectory planner.
Albert Rizaldi, Fabian Immler, Matthias Althoff

Probabilistic Formal Verification of the SATS Concept of Operation

Abstract
The objective of NASA’s Small Aircraft Transportation System (SATS) Concept of Operations (ConOps) is to facilitate High Volume Operation (HVO) of advanced small aircraft operating in non-towered non-radar airports. Given the safety-critical nature of SATS, its analysis accuracy is extremely important. However, the commonly used analysis techniques, like simulation and traditional model checking, do not ascertain a complete verification of SATS due to the wide range of possibilities involved in SATS or the inability to capture the randomized and unpredictable aspects of the SATS ConOps environment in their models. To overcome these limitations, we propose to formulate the SATS ConOps as a fully synchronous and probabilistic model, i.e., SATS-SMA, that supports simultaneously moving aircraft. The distinguishing features of our work include the preservation of safety of aircraft while improving throughput at the airport. Important insights related to take-off and landing operations during the Instrument Meteorological Conditions (IMC) are also presented.
Muhammad Usama Sardar, Nida Afaq, Khaza Anuarul Hoque, Taylor T. Johnson, Osman Hasan

Formal Translation of IEC 61131-3 Function Block Diagrams to PVS with Nuclear Application

Abstract
The trip computers for the two reactor shutdown systems of the Ontario Power Generation (OPG) Darlington Nuclear Power Generating Station (DNGS) are being refurbished due to hardware obsolescence. For one of the systems, the general purpose computer originally used is being replaced by a programmable logic controller (PLC). The trip computer application software has been rewritten using function block diagrams (FBDs), a commonly used PLC programming language defined in the IEC 61131-3 standard. The replacement project’s quality assurance program requires that formal verification be performed to compare the FBDs against a formal software requirements specification (SRS) written using tabular expressions (TEs). The PVS theorem proving tool is used in the formal verification. Custom tools developed for OPG are used to translate TEs and FBDs into PVS code. In this paper, we present a method to rigorously translate the graphical FBD language to a mathematical model in PVS using an abstract syntax to represent the FBD constructs. We use an example from the replacement project to demonstrate the use of the model to translate a FBD module into a PVS specification.
Josh Newell, Linna Pang, David Tremaine, Alan Wassyng, Mark Lawford

Formal Analysis of Extended Well-Clear Boundaries for Unmanned Aircraft

Abstract
This paper concerns the application of formal methods to the definition of a detect and avoid concept for unmanned aircraft systems (UAS). In particular, it illustrates how formal analysis was used to explain and correct unexpected behaviors of the logic that issues alerts when two aircraft are predicted not to be well clear from one another. As a result of this analysis, a recommendation was proposed to, and subsequently adopted by, the US standards organization that defines the minimum operational requirements for the UAS detect and avoid concept.
César Muñoz, Anthony Narkawicz

Formal Validation and Verification Framework for Model-Based and Adaptive Control Systems

Abstract
This paper presents the interim results of a three-year NASA project for the development of a comprehensive framework for the validation and verification (V&V) of model-based control systems and adaptive control systems (MBCSs/ACSs), with focus on Unmanned Aircraft Systems (UAS) applications. The framework applies a formal V&V methodology based on a combination of logic-dynamic model constructs and associated analysis processes, to support the generation of a documentable assurance case for a UAS control system, and to demonstrate its compliance with applicable aviation system certification standards .
Sergio Guarro, Umit Ozguner, Tunc Aldemir, Matt Knudson, Arda Kurt, Michael Yau, Mohammad Hejase, Steve Kwon

Techniques for Automated Verification

Frontmatter

Verifying Relative Safety, Accuracy, and Termination for Program Approximations

Abstract
Approximate computing is an emerging area for trading off the accuracy of an application for improved performance, lower energy costs, and tolerance to unreliable hardware. However, developers must ensure that the leveraged approximations do not introduce significant, intolerable divergence from the reference implementation, as specified by several established robustness criteria. In this work, we show the application of automated differential verification towards verifying relative safety, accuracy, and termination criteria for a class of program approximations. We use mutual summaries to express relative specifications for approximations, and SMT-based invariant inference to automate the verification of such specifications. We perform a detailed feasibility study showing promise of applying automated verification to the domain of approximate computing in a cost-effective manner.
Shaobo He, Shuvendu K. Lahiri, Zvonimir Rakamarić

Bandwidth and Wavefront Reduction for Static Variable Ordering in Symbolic Reachability Analysis

Abstract
We investigate the use of bandwidth and wavefront reduction algorithms to determine a static BDD variable ordering. The aim is to reduce the size of BDDs arising in symbolic reachability. Previous work showed that minimizing the (weighted) event span of the variable dependency graph yields small BDDs. The bandwidth and wavefront of symmetric matrices are well studied metrics, used in sparse matrix solvers, and many bandwidth and wavefront reduction algorithms are readily available in libraries like Boost and ViennaCL.
In this paper, we transform the dependency matrix to a symmetric matrix and apply various bandwidth and wavefront reduction algorithms, measuring their influence on the (weighted) event span. We show that Sloan’s algorithm, executed on the total graph of the dependency matrix, yields a variable order with minimal event span. We demonstrate this on a large benchmark of Petri nets, Dve, Promela, B, and mcrl2 models. As a result, good static variable orders can now be determined in milliseconds by using standard sparse matrix solvers.
Jeroen Meijer, Jaco van de Pol

Gray-Box Learning of Serial Compositions of Mealy Machines

Abstract
We study the following gray-box learning problem: Given the serial composition of two Mealy machines A and B, where A is known and B is unknown, the goal is to learn a model of B using only output and equivalence queries on the composed machine.
We introduce an algorithm that solves this problem, using at most |B| equivalence queries, independently of the size of A. We discuss its efficient implementation and evaluate the algorithm on existing benchmark sets as well as randomly-generated machines.
Andreas Abel, Jan Reineke

Theorem Proving and Proofs

Frontmatter

Specification and Proof of High-Level Functional Properties of Bit-Level Programs

Abstract
In a computer program, basic functionalities may be implemented using bit-wise operations. To formally specify the expected behavior of such a low-level program, it is desirable that the specification should be at a more abstract level. Formally proving that low-level code conforms to a higher-level specification is challenging, because of the gap between the different levels of abstraction. We address this challenge by designing a rich formal theory of fixed-sized bit vectors, which on the one hand allows a user to write abstract specifications close to the human—or mathematical—level of thinking, while on the other hand permits a close connection to decision procedures and tools for bit vectors, as they exist in the context of the Satisfiability Modulo Theory framework. This approach is implemented in the Why3 environment for deductive program verification, and also in its front-end environment SPARK for the development of safety-critical Ada programs. We report on several case studies used to validate our approach.
Clément Fumex, Claire Dross, Jens Gerlach, Claude Marché

Formal Verification of an Executable LTL Model Checker with Partial Order Reduction

Abstract
We present a formally verified and executable on-the-fly LTL model checker that uses ample set partial order reduction. The verification is done using the proof assistant Isabelle/HOL and covers everything from the abstract correctness proof down to the generated SML code. Building on Doron Peled’s paper “Combining Partial Order Reductions with On-the-Fly Model-Checking”, we formally prove abstract correctness of ample set partial order reduction. This theorem is independent of the actual reduction algorithm. We then verify a reduction algorithm for a simple but expressive fragment of Promela. We use static partial order reduction, which allows separating the partial order reduction and the model checking algorithms regarding both the correctness proof and the implementation. Thus, the Cava model checker that we verified in previous work can be used as a back end with only minimal changes. Finally, we generate executable SML code using a stepwise refinement approach. We test our model checker on some examples, observing the effectiveness of the partial order reduction algorithm.
Julian Brunner, Peter Lammich

A Modular Way to Reason About Iteration

Abstract
In this paper we present an approach to specify programs performing iterations. The idea is to specify iteration in terms of the finite sequence of the elements enumerated so far, and only those. In particular, we are able to deal with non-deterministic and possibly infinite iteration. We show how to cope with the issue of an iteration no longer being consistent with mutable data.
We validate our proposal using the deductive verification tool Why3 and two iteration paradigms, namely cursors and higher-order iterators. For each paradigm, we verify several implementations of iterators and client code. This is done in a modular way, i.e., the client code only relies on the specification of the iteration.
Jean-Christophe Filliâtre, Mário Pereira

A Proof Infrastructure for Binary Programs

Abstract
Establishing properties of binary programs by proof is a desirable goal when the properties of interest are crucial, such as those that arise in safety- and security-critical applications. Practical development of proofs for binary programs requires a substantial infrastructure to disassemble the program, define the machine semantics, and actually undertake the required proofs. At the center of these infrastructure requirements is the need to document semantics in a formal language. In this paper we present a work-in-progress proof infrastructure for binary programs based on AdaCore and Altran’s integrated development and verification environment, SPARKPro. We illustrate the infrastructure with proof of a security property.
Ashlie B. Hocking, Benjamin D. Rodes, John C. Knight, Jack W. Davidson, Clark L. Coleman

Hierarchical Verification of Quantum Circuits

Abstract
In this paper, we introduce the idea of hierarchical verification for quantum circuits, where we use a powerful language, higher-order logic, to reason about quantum circuits formally. We propose a formal modeling and verification approach that captures quantum models built hierarchically from primitive optical quantum gates. The analysis and verification of composed circuits is done seamlessly based on dedicated mathematical foundations formalized in the HOL Light theorem prover. In order to demonstrate the effectiveness of the proposed infrastructure, we present the formal analysis of the controlled-phase gate and Shor’s factoring quantum circuits.
Sidi Mohamed Beillahi, Mohamed Yousri Mahmoud, Sofiène Tahar

Correctness and Certification

Frontmatter

Semantics for Locking Specifications

Abstract
Lock-based synchronization disciplines, like Java’s @GuardedBy, are widely used to prevent concurrency errors. However, their semantics is often expressed informally and is consequently ambiguous. This article highlights such ambiguities and overcomes them by formalizing two possible semantics of @GuardedBy, using a reference operational semantics for a core calculus of a concurrent Java-like language. It also identifies when such annotations are actual guarantees against data races. Our work aids in understanding the annotations and supports the development of sound tools that verify or infer them.
Michael D. Ernst, Damiano Macedonio, Massimo Merro, Fausto Spoto

From Design Contracts to Component Requirements Verification

Abstract
During the development and verification of complex airborne systems, a variety of languages and development environments are used for different levels of the system hierarchy. As a result, there may be manual steps to translate requirements between these different environments. This paper presents a tool-supported export technique that translates high-level requirements from the software architecture modeling environment into observers of requirements that can be used for verification in the software component environment. This allows efficient verification that the component designs comply with their high-level requirements. It also provides an automated tool chain supporting formal verification from system requirements down to low-level software requirements that is consistent with certification guidance for avionics systems. The effectiveness of the technique has been evaluated and demonstrated on a medical infusion pump and an aircraft wheel braking system.
Jing Liu, John D. Backes, Darren Cofer, Andrew Gacek

A Hybrid Architecture for Correct-by-Construction Hybrid Planning and Control

Abstract
This paper describes Hy-CIRCA, an architecture for verified, correct-by-construction planning and execution for hybrid systems, including nonlinear continuous dynamics. Hy-CIRCA addresses the high computational complexity of such systems by first planning at an abstract level, and then progressively refining the original plan. Hy-CIRCA integrates the dReal nonlinear SMT solver with enhanced versions of the SHOP2 HTN planner and the CIRCA Controller Synthesis Module (CSM). SHOP2 computes a high level nominal mission plan, the CIRCA CSM develops reactive controllers for the mission steps, accounting for disturbances, and dReal verifies that the plans are correct with respect to continuous dynamics. In this way, Hy-CIRCA decomposes reasoning about the plan and judiciously applies the different solvers to the problems they are best at.
Robert P. Goldman, Daniel Bryce, Michael J. S. Pelican, David J. Musliner, Kyungmin Bae

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise