Verified Software: Theories, Tools, Experiments

Frontmatter

Cyber War, Formal Verification and Certified Infrastructure

Abstract

Cyber war is recognized to be real. Like all wars this is bad for many people, but not for manufacturers of weapons. An attacker in cyber war can be defined as an unauthorized user process without access to physical side channels; with physical access we would be back to ordinary warfare and espionage. IT infrastructure which - by separation theorems - can be guaranteed to be immune against such attackers is therefore a defensive weapon in cyber war. The verification community is the only potential manufacturer of such infrastructure and thus has a chance to access resources vastly superior to those for ordinary research and development.

In order to develop such infrastructure, one would have to

1

develop a pervasive mathematical theory of IT infrastructure

 

2

formally verify it

 

3

convince industry and politicians, that the specifications of this theory are meaningful and

 

4

convince certification agencies, that all verification tools involved are sound

 

Problem (3) could be solved by providing standardized machine readable specifications of the usual components of IT infrastructure. Note that agreeing on standards is usually a non trivial sociological process. (1), (2) and (4) are ’ordinary’ technical problems. In the main part of this talk we will review the state of the art for these problems and estimate the resources to resolve the remaining open subproblems. The resulting costs are large compared to normal research budgets and very small compared to the cost of war.

Wolfgang Paul

A Certified Multi-prover Verification Condition Generator

Abstract

Deduction-based software verification tools have reached a maturity allowing them to be used in industrial context where a very high level of assurance is required. This raises the question of the level of confidence we can grant to the tools themselves. We present a certified implementation of a verification condition generator. An originality is its genericity with respect to the logical context, which allows us to produce proof obligations for a large class of theorem provers.

Paolo Herms, Claude Marché, Benjamin Monate

Integrated Semantics of Intermediate-Language C and Macro-Assembler for Pervasive Formal Verification of Operating Systems and Hypervisors from VerisoftXT

Abstract

Pervasive formal verification of operating systems and hypervisors is, due to their safety-critical aspects, a highly relevant area of research. Many implementations consist of both assembler and C functions. Formal verification of their correctness must consider the correct interaction of code written in these languages, which is, in practice, ensured by using matching application binary interfaces (ABIs). Also, these programs must be able to interact with hardware. We present an integrated operational small-step semantics model of intermediate-language C and Macro-Assembler code execution for pervasive operating systems and hypervisor verification. Our semantics is based on a compiler calling convention that defines callee- and caller-save registers. We sketch a theory connecting this semantic layer with an ISA-model executing the compiled code for use in a pervasive verification context. This forms a basis for soundness proofs of tools used in the VerisoftXT project and is a crucial step towards arguing formal correctness of execution of the verified code on a gate-level hardware model.

Sabine Schmaltz, Andrey Shadrin

The Location Linking Concept: A Basis for Verification of Code Using Pointers

Abstract

While the use of pointers can be minimized by language mechanisms for data abstraction, alias avoidance and control, and disciplined software development techniques, ultimately, any verifying compiler effort must be able to verify code that makes use of them. Additionally, in order to scale, the verification machinery of such a compiler must use specifications to reason about components. This paper follows a natural question that arises from combining these ideas: can the general machinery of specification-based component verification also be used to verify code that uses instances of types that are more traditionally built-in, such as arrays and pointers? This paper answers the question in the affirmative by presenting a Location_Linking_Template, a concept that captures pointer behavior, and uses it to verify the code of a simple data abstraction realized using pointers. In this deployment, pointers have a specification like any other component. We also note that the concept can be extended and realized so that different systems can plug in alternative implementations to give programmers the flexibility to choose, e.g., manual memory management or automatic garbage collection depending on their performance concerns.

Gregory Kulczycki, Hampton Smith, Heather Harton, Murali Sitaraman, William F. Ogden, Joseph E. Hollingsworth

Verifying Implementations of Security Protocols by Refinement

Abstract

We propose a technique for verifying high-level security properties of cryptographic protocol implementations based on stepwise refinement. Our refinement strategy supports reasoning about abstract protocol descriptions in the symbolic model of cryptography and gradually concretizing them towards executable code. We have implemented the technique within a general-purpose program verifier VCC and applied it to an extract from a draft reference implementation of Trusted Platform Module, written in C.

Nadia Polikarpova, Michał Moskal

Deciding Functional Lists with Sublist Sets

Abstract

Motivated by the problem of deciding verification conditions for the verification of functional programs, we present new decision procedures for automated reasoning about functional lists. We first show how to decide in NP the satisfiability problem for logical constraints containing equality, constructor, selectors, as well as the transitive sublist relation. We then extend this class of constraints with operators to compute the set of all sublists, and the set of objects stored in a list. Finally, we support constraints on sizes of sets, which gives us the ability to compute list length as well as the number of distinct list elements. We show that the extended theory is reducible to the theory of sets with linear cardinality constraints, and therefore still in NP. This reduction enables us to combine our theory with other decidable theories that impose constraints on sets of objects, which further increases the potential of our decidability result in verification of functional and imperative software.

Thomas Wies, Marco Muñiz, Viktor Kuncak

Developing Verified Programs with Dafny

Abstract

Dafny [2] is a programming language and program verifier. The language is type-safe and sequential, and it includes common imperative features, dynamic object allocation, and inductive datatypes. It also includes specification constructs like pre- and postconditions, which let a programmer record the intended behavior of the program along with the executable code that is supposed to cause that behavior. Because the Dafny verifier runs continuously in the background, the consistency of a program and its specifications is always enforced.

Dafny has been used to verify a number of challenging algorithms, including Schorr-Waite graph marking, Floyd’s “tortoise and hare” cycle-detection algorithm, and snapshotable trees with iterators. Dafny is also being used in teaching and it was a popular choice in the VSTTE 2012 program verification competition. Its open-source implementation has also been used as a foundation for other verification tools.

In this tutorial, I will give a taste of how to use Dafny in program development. This will include an overview of Dafny, basics of writing specifications, how to debug verification attempts, how to formulate and prove lemmas, and some newer features for staged program development.

K. Rustan, M. Leino

Verifying Two Lines of C with Why3: An Exercise in Program Verification

Abstract

This article details the formal verification of a 2-line C program that computes the number of solutions to the n-queens problem. The formal proof of (an abstraction of) the C code is performed using the Why3 tool to generate the verification conditions and several provers (Alt-Ergo, CVC3, Coq) to discharge them. The main purpose of this article is to illustrate the use of Why3 in verifying an algorithmically complex program.

Jean-Christophe Filliâtre

Development and Evaluation of LAV: An SMT-Based Error Finding Platform

System Description

Abstract

We present design and evaluation of LAV, a new open-source tool for statically checking program assertions and errors. LAV integrates into the popular LLVM infrastructure for compilation and analysis. LAV uses symbolic execution to construct a first-order logic formula that models the behavior of each basic blocks. It models the relationships between basic blocks using propositional formulas. By combining these two kinds of formulas LAV generates polynomial-sized verification conditions for loop-free code. It uses underapproximating or overapproximating unrolling to handle loops. LAV can pass generated verification conditions to one of the several SMT solvers: Boolector, MathSAT, Yices, and Z3. Our experiments with small 200 benchmarks suggest that LAV is competitive with related tools, so it can be used as an effective alternative for certain verification tasks. The experience also shows that LAV provides significant help in analyzing student programs and providing feedback to students in everyday university practice.

Milena Vujošević-Janičić, Viktor Kuncak

A Lightweight Technique for Distributed and Incremental Program Verification

Abstract

Applying automated verification to industrial code bases creates a significant computational task even when the individual conditions to be checked are trivial. This affects the wall clock time taken to verify the program and has knock-on effects on how the tools are used and on project management. In this paper a simple and lightweight technique for adding incremental and distributed capabilities to a program verification system is given. Experiments with an implementation of the technique for the SPARK tool set show that it can yield an average 29 fold speed increase in incremental use and near optimal speedup in distributed use. Critically, this gives a qualitative change in how automated verification is used in a large commercial project.

Martin Brain, Florian Schanda

A Comparison of Intermediate Verification Languages: Boogie and Sireum/Pilar

Abstract

Use of contract-based specification languages is slowly increasing. This advancement has been due in part to the growing efficiency and usefulness of Intermediate Verification Languages (IVLs) which abstract the low level details of program verification and act as a backbone for higher level tools. This paper looks at two mature IVLs, Boogie and Sireum/Pilar, and provides a comparative study of their features in order to offer resources for tool developers and IVL designers. As validation for this comparison, we introduce two tools, ruby2boogie and ruby2pilar, to illustrate the translation from Ruby to Boogie and Pilar.

Loren Segal, Patrice Chalin

LLBMC: Bounded Model Checking of C and C++ Programs Using a Compiler IR

Abstract

Bounded model checking (BMC) of C and C++ programs is challenging due to the complex and intricate syntax and semantics of these programming languages. The BMC tool LLBMC presented in this paper thus uses the LLVM compiler framework in order to translate C and C++ programs into LLVM’s intermediate representation. The resulting code is then converted into a logical representation and simplified using rewrite rules. The simplified formula is finally passed to an SMT solver. In contrast to many other tools, LLBMC uses a flat, bit-precise memory model. It can thus precisely model, e.g., memory-based re-interpret casts as used in C and static/dynamic casts as used in C++. An empirical evaluation shows that LLBMC compares favorable to the related BMC tools CBMC and ESBMC.

Florian Merz, Stephan Falke, Carsten Sinz

The Marriage of Exploration and Deduction

Abstract

State space exploration based on abstraction and refinement has been the cornerstone of several successful software verification tools from the last decade. While these tools have made impressive progress in verifying control-dominant properties of code, most prominently in the domain of device drivers, their applications to more data-intensive properties have been limited. In particular, we focus on parameterized systems, which define infinite families of systems, one for each value of the parameter. Many real-life software systems, for example, memory management units or cache coherence protocols can be modeled as parameterized systems (parameterized, e.g., by the number of processes and memory locations), We want to perform uniform verification of parameterized systems, where we show a formula is an invariant of every member in the parameterized family.

Rupak Majumdar

Modeling and Validating the Train Fare Calculation and Adjustment System Using VDM++

Abstract

The Train Fare Calculation and Adjustment System (TFCAS), developed by the OMRON Corporation, is a large-scale and complex system that helps passengers buy tickets and adjust their train fare on the railways across Japan. In this paper we present the results and experiences gained in a collaborative research project between AIST and OMRON, in which VDM++ has been applied to formalize TFCAS’s specifications and validate its consistency as well as reliability properties. An executable VDM++ model can be used to raise the level of the quality of the informal system specification, the efficiency of existing system test-suites, and the quality of real implementation. The application of VDM++ enables us to detect 32 erroneous issues in the original informal specification document. Moreover, we also show how the development process can be improved in a front-loading manner using the formal method VDM++.

Nguyen Van Tang, Daisuke Souma, Goro Hatayama, Hitoshi Ohsaki

Formalized Verification of Snapshotable Trees: Separation and Sharing

Abstract

We use separation logic to specify and verify a Java program that implements snapshotable search trees, fully formalizing the specification and verification in the Coq proof assistant. We achieve local and modular reasoning about a tree and its snapshots and their iterators, although the implementation involves shared mutable heap data structures with no separation or ownership relation between the various data.

The paper also introduces a series of four increasingly sophisticated implementations and verifies the first one. The others are included as future work and as a set of challenge problems for full functional specification and verification, whether by separation logic or by other formalisms.

Hannes Mehnert, Filip Sieczkowski, Lars Birkedal, Peter Sestoft

Comparing Verification Condition Generation with Symbolic Execution: An Experience Report

Abstract

There are two dominant approaches for the construction of automatic program verifiers, Verification Condition Generation (VCG) and Symbolic Execution (SE). Both techniques have been used to develop powerful program verifiers. However, to the best of our knowledge, no systematic experiment has been conducted to compare them.

This paper reports on such an experiment. We have used the specification and programming language Chalice and compared the performance of its standard VCG verifier with a newer SE engine called Syxc, using the Chalice test suite as a benchmark. We have focused on comparing the efficiency of the two approaches, choosing suitable metrics for that purpose. Our metrics also suggest conclusions about the predictability of the performance. Our results show that verification via SE is roughly twice as fast as via VCG. It requires only a small fraction of the quantifier instantiations that are performed in the VCG-based verification.

Ioannis T. Kassios, Peter Müller, Malte Schwerhoff

Verification of TLB Virtualization Implemented in C

Abstract

Efficient TLB virtualization is a core component of modern hypervisors. Verifying such code is challenging; the code races with TLB virtualization code in other processors, with other guest threads, and with the hardware TLBs, and implements an abstract TLB that races with other abstract TLBs and guest threads. We give a general methodology for verifying virtual device implementations, and demonstrate the verification of TLB virtualization code (using shadow page tables) in the concurrent C verifier VCC. To our knowledge, this is the first verification of any kind against a realistic model of a modern hardware MMU.

Eyad Alkassar, Ernie Cohen, Mikhail Kovalev, Wolfgang J. Paul

Formalization and Analysis of Real-Time Requirements: A Feasibility Study at BOSCH

Abstract

In this paper, we evaluate a tool chain to algorithmically analyze real-time requirements. According to this tool chain, one formalizes the requirements in a natural-language pattern system. The requirements can then be automatically compiled into formulas in a real-time logic. The formulas can be checked automatically for properties whose violation indicates an error in the requirements specification (the properties considered are: consistency, rt-consistency, vacuity). We report on a feasibility study in the context of several automotive projects at Bosch. The results of the study indicate that the effort for the formalization of real-time requirements is acceptable; the analysis algorithms are computationally feasible; the benefit (the detection of specification errors resp. the formal guarantee of their absence) seems significant.

Amalinda Post, Jochen Hoenicke

Our Experience with the CodeContracts Static Checker

(Invited Tutorial)

Abstract

In this tutorial I will report our experience with CodeContracts [5], and in particular with its static checker (cccheck/clousot) [6].

CodeContracts are a language-agnostic solution to the specification problem. Preconditions, postconditions and object invariants are with opportune method calls acting as specification markers [4]. The CodeContracts API is part of the core .NET standard. The CodeContracts tools have been downloaded more than 50 000 times, and they are currently used in many projects by professional programmers.

Francesco Logozzo

Isabelle/Circus: A Process Specification and Verification Environment

Abstract

The Circus specification language combines elements for complex data and behavior specifications, using an integration of Z and CSP with a refinement calculus. Its semantics is based on Hoare and He’s unifying theories of programming (UTP).

We develop a machine-checked, formal semantics based on a “shallow embedding” of Circus in Isabelle/UTP (our semantic theory of UTP based on Isabelle/HOL). We derive proof rules from this semantics and implement tactic support that finally allows for proofs of refinement for Circus processes (involving both data and behavioral aspects).

This proof environment supports a syntax for the semantic definitions which is close to textbook presentations of Circus.

Abderrahmane Feliachi, Marie-Claude Gaudel, Burkhart Wolff

Termination Analysis of Imperative Programs Using Bitvector Arithmetic

Abstract

Currently, nearly all methods for proving termination of imperative programs apply an unsound and incomplete abstraction by treating bitvectors and bitvector arithmetic as (unbounded) integers and integer arithmetic, respectively. This abstraction ignores the wrap-around behavior caused by under- and overflows in bitvector arithmetic operations. This is particularly problematic in the termination analysis of low-level system code. This paper proposes a novel method for encoding the wrap-around behavior of bitvector arithmetic within integer arithmetic. Afterwards, existing methods for reasoning about the termination of integer arithmetic programs can be employed for reasoning about the termination of bitvector arithmetic programs. An empirical evaluation shows the practicality and effectiveness of the proposed method.

Stephan Falke, Deepak Kapur, Carsten Sinz

Specifying and Verifying the Correctness of Dynamic Software Updates

Abstract

Dynamic software updating (DSU) systems allow running programs to be patched on-the-fly to add features or fix bugs. While dynamic updates can be tricky to write, techniques for establishing their correctness have received little attention. In this paper, we present the first methodology for automatically verifying the correctness of dynamic updates. Programmers express the desired properties of an updated execution using client-oriented specifications (CO-specs), which can describe a wide range of client-visible behaviors. We verify CO-specs automatically by using off-the-shelf tools to analyze a merged program, which is a combination of the old and new versions of a program. We formalize the merging transformation and prove it correct. We have implemented a program merger for C, and applied it to updates for the Redis key-value store and several synthetic programs. Using Thor, a verification tool, we could verify many of the synthetic programs; using Otter, a symbolic executor, we could analyze every program, often in less than a minute. Both tools were able to detect faulty patches and incurred only a factor-of-four slowdown, on average, compared to single version programs.

Christopher M. Hayden, Stephen Magill, Michael Hicks, Nate Foster, Jeffrey S. Foster

Symbolic Execution Enhanced System Testing

Abstract

We describe a testing technique that uses information computed by symbolic execution of a program unit to guide the generation of inputs to the system containing the unit, in such a way that the unit’s, and hence the system’s, coverage is increased. The symbolic execution computes unit constraints at run-time, along program paths obtained by system simulations. We use machine learning techniques –treatment learning and function fitting– to approximate the system input constraints that will lead to the satisfaction of the unit constraints. Execution of system input predictions either uncovers new code regions in the unit under analysis or provides information that can be used to improve the approximation. We have implemented the technique and we have demonstrated its effectiveness on several examples, including one from the aerospace domain.

Misty Davies, Corina S. Păsăreanu, Vishwanath Raman

Infeasible Code Detection

Abstract

A piece of code in a computer program is infeasible if it cannot be part of any normally-terminating execution of the program. We develop an algorithm for the automatic detection of all infeasible code in a program. We first translate the task of determining all infeasible code into the problem of finding all statements that can be covered by a feasible path. We prove that in order to identify all coverable statements, it is sufficient to find all coverable statements within a certain minimal subset. For this, our algorithm repeatedly queries an oracle, asking for the infeasibility of specific sets of control-flow paths.

We present a sound implementation of the proposed algorithm on top of the Boogie program verifier utilizing a theorem prover to provide the oracle required by the algorithm. We show experimentally a drastic decrease in the number of theorem prover queries compared to existing approaches, resulting in an overall speedup of the entire computation.

Cristiano Bertolini, Martin Schäf, Pascal Schweitzer

Backmatter