**Ceci est une ancienne révision du document !**

# Free software tools for formal verification of computer programs

by David Mentré <dmentre @ linux-france.org>

*Version 1.18 - 2011-04-26*

We are now living in the XXIst century. We should no longer make software as in the sixties or seventies, with a few tests. We are now able to make software without **any** bugs (well, without most of them, see below). This is possible using specialised tools called *formal tools*. Such tools are able to match a computer program against a specification, i.e. a formal description of the expected behaviour of the program. If the specification is correct and the formal verification can be done, then the program is guaranteed to be bug free. Of course, this is the ideal case and we are far from guaranteed bug free programs in the real world. But, as developer of free software, we should try to be as close as possible of this goal. As a first step, I list here free software tools that can help verification of computer programs.

Note: David A. Wheeler as made a lengthy paper on High Assurance (for Security or Safety) and [[free_-_libre|Free-Libre / Open Source Software (FLOSS)… with Lots on Formal Methods]]. You should read it if you are interested in the subject!

## Proof assistants

Proof assistants are computer programs that aids a human to prove things (so they are sometimes called /theorem provers/). Generally, they understand several formal logics with there rules and are able to apply those rules, automatically or guided by the human verifier. Such tools are at the core of the verification process.

### Coq

Coq is a proof assistant environment.

- License: GNU LGPL 2.1

- Web site: http://coq.inria.fr/

- Debian packages: coq coq-doc proofgeneral-coq

### ACL2

ACL2 is an environment where programs are described using an applicative subset of Common Lisp. Each function of the program entered in the environment is formally proven (termination, …).

- License: GNU GPL

- Debian packages: acl2 acl2-books acl2-books-certs

acl2-books-source acl2-doc acl2-emacs acl2-infix acl2-infix-source

acl2-source

### Milawa

Milawa is a “self-verifying” theorem prover for an ACL2-like logic.

We begin with a simple proof checker, call it A, which is short enough to verify by the “social process” of mathematics.

We then develop a series of increasingly powerful proof checkers, call them B, C, D, and so on. We show that each of these is sound: they accept only the same formulas as A. We use A to verify B, and B to verify C, and so on. Then, since we trust A, and A says B is sound, we can trust B, and so on for C, D, and the rest.

Our final proof checker is really a theorem prover; it can carry out a goal-directed proof search using assumptions, calculation, rewrite rules, and so on. We use this theorem prover to discover the proofs of soundness for B, C, and so on, and to emit these proofs in a format that A can check. Hence, “self verifying.”

- License : GNU GPL 2+

### Phox

PhoXis a proof assistant based on High Order logic and it is eXtensible. One of the principle of this proof assistant is to be as user friendly as possible and so to need a minimal learning time. The current version is still expirimental but starts to be really usable. It is a good idea to try it and make comments to improve the final version.

- License: ??

- Web site:

http://www.lama.univ-savoie.fr/sitelama/Membres/pages_web/RAFFALLI/phox.html

### HOL Light

HOL Light is a computer program to help users prove interesting mathematical theorems completely formally in higher order logic. It sets a very exacting standard of correctness, but provides a number of automated tools and pre-proved mathematical theorems (e.g. about arithmetic, basic set theory and real analysis) to save the user work. It is also fully programmable, so users can extend it with new theorems and inference rules without compromising its soundness.

- License: BSD like

### HOL Zero

HOL Zero is a new, basic theorem prover for the HOL logic, designed with trustworthiness as its top priority. It is primarily intended for two roles:

- highly-trustworthy system for checking and/or consolidating proofs created on other theorem provers;

- pedagogical example of a simple theorem prover and its implementation.

Note that some proof porting mechanism is required for the role of checking/consolidating proofs. One such mechanism is under development at Proof Technologies.

Unlike other HOL systems, HOL Zero is NOT primarily targetted at developing proofs, although it is suitable for simple natural deduction proofs. It concentrates on doing basic functionality well, and has relatively sophisticated term parsing, pretty printing and error reporting. Its source code is very carefully written and commented, and aims to be as simple and readable as possible. An extensive glossary of HOL-related terminology is provided as part of the user documentation.

- License: BSD like

### haRVey

haRVey is a SMT (Satisfiability Modulo Theories) prover. There are presently two branches of haRVey: haRVey-SAT and haRVey-FOL.

- haRVey-FOL integrates a First-Order Logic theorem prover (hence its name), i.e. the E-prover. It uses the superposition calculus as implemented by the E-prover, to determine the satisfiability of Boolean combinations of atoms with functions interpreted in a first-order theory with equality.

- haRVey-SAT is based on congruence closure, the Nelson-Oppen framework, and rudimentary instantiation techniques to decide the satisfiability of a set of atoms written with uninterpreted symbols, linear arithmetics, some lambda-expressions, and some quantifiers. The Boolean engine is a SAT solver (zChaff or MiniSAT), hence its name.

- License:

- haRVey-FOL: GNU LGPL 2.1

- haRVey-FOL relies on E-prover (http://eprover.org/): GNU GPL

- haRVey-SAT: BSD like

- haRVey-SAT relies on MiniSat(http://minisat.se/): BSD like

- Web site: http://harvey.loria.fr/haRVey.php

### Brillant

Set of free software tools aiming at implementing the B method, for both software and hardware.

- License: GNU LGPL

- Web site: https://gna.org/projects/brillant

### HOL

HOL 4 is the latest version of the HOL automated proof system for higher order logic: a programming environment in which theorems can be proved and proof tools implemented. Built-in decision procedures and theorem provers can automatically establish many simple theorems. An oracle mechanism gives access to external programs such as SAT and BDD engines. HOL 4 is particularly suitable as a platform for implementing combinations of deduction, execution and property checking.

- License: BSD like

- Web site: http://hol.sourceforge.net/

### Zenon

Zenon is an automatic theorem that handles first-order logic with equality. Its most important feature is that it outputs the proofs of the theorems, in Coq-checkable form.

- License: BSD like

- Web site: http://focal.inria.fr/zenon/

### Maude

Maude is a high-performance reflective language and system supporting both equational and rewriting logic specification and programming for a wide range of applications. Maude has been influenced in important ways by the OBJ3 language, which can be regarded as an equational logic sublanguage. Besides supporting equational specification and programming, Maude also supports rewriting logic computation.

Rewriting logic is a logic of concurrent change that can naturally deal with state and with concurrent computations. It has good properties as a general semantic framework for giving executable semantics to a wide range of languages and models of concurrency. In particular, it supports very well concurrent object-oriented computation. The same reasons making rewriting logic a good semantic framework make it also a good logical framework, that is, a metalogic in which many other logics can be naturally represented and executed.

- License: GNU GPL

- Web site: http://maude.cs.uiuc.edu/

### PVS

PVS is a verification system: that is, a specification language integrated with support tools and a theorem prover. It is intended to capture the state-of-the-art in mechanized formal methods and to be sufficiently rugged that it can be used for significant applications. PVS is a research prototype: it evolves and improves as we develop or apply new capabilities, and as the stress of real use exposes new requirements.

- License: GNU GPL

- Web site: http://pvs.csl.sri.com/

### Sparkle

Sparkle is a proof tool specially constructed for Clean (a state-of-the-art pure and lazy functional programming language). The tool knows the Clean 2.0 syntax and semantics. It comes with a rich set of proof tactics and a powerful hint mechanism to aid the user in proving properties of Clean programs.

- License: GNU LGPL (same as Clean language)

- Web site: http://clean.cs.ru.nl/

### Isabelle

Isabelle is a generic proof assistant. It allows mathematical formulas to be expressed in a formal language and provides tools for proving those formulas in a logical calculus. The main application is the formalization of mathematical proofs and in particular formal verification, which includes proving the correctness of computer hardware or software and proving properties of computer languages and protocols.

Compared with similar tools, Isabelle's distinguishing feature is its flexibility. Most proof assistants are built around a single formal calculus, typically higher-order logic. Isabelle has the capacity to accept a variety of formal calculi. The distributed version supports higher-order logic but also axiomatic set theory and several other formalisms. See logics for more details.

- License: BSD like

- Web site: http://isabelle.in.tum.de/

### [[proof_power|ProofPower]]

ProofPoweris a suite of tools supporting specification and proof in Higher Order Logic (HOL) and in the Z notation. The suite comprises the following packages:

- PPDev * The ProofPowerdeveloper kit, mainly comprising SLRP, a parser generator for Standard ML.

- PPTex * The ProofPowerinterface to TeXand LaTeX.

- PPXpp - The X Windows/Motif front-end for ProofPower.

- PPHol - The HOL specification and proof development system.

- PPZed - The Z specification and proof development system.

- PPDaz - The Compliance Tool for specifying and verifying Ada programs.

All the ProofPowerpackages except PPDaz are free, open-source, software made available under the terms of the GNU General Public License.

ProofPowerhas been under ongoing development since 1989. It was originally designed and implemented by International Computers Ltd. to support proofs of specification-to-model correspondence for high-assurance secure systems. It has since played an important role in approaches to specifying and verifying safety-critical systems in work by the Defence and Evaluation Research Agency, now QinetiQ, and others. Since 1997, on-going developments to the product have been undertaken by Lemma 1 Ltd. In Spring 2000, International Computers Ltd. transferred its rights in ProofPowerto Lemma 1 Ltd who now maintain this web site and support and distribute the software.

- License: GPL (except PPDaz)

## Model checkers

Model checkers are tool that verify all possible states of a formal model, i.e. a formal description of a system. Compared to proof assistant, they can be less powerful but easier to use.

### [[nu_smv|NuSMV]]

NuSMVis a reimplementation and extension of SMV, the first model checker based on BDDs. NuSMVhas been designed to be an open architecture for model checking, which can be reliably used for the verification of industrial designs, as a core for custom verification tools, as a testbed for formal verification techniques, and applied to other research areas.

- License: GNU LGPL 2.1

- Web site: http://nusmv.irst.itc.it/

### Murphi

Murphi also has a formal verifier based on explicit state enumeration. The verifier performs depth- or breadth-first search in the state graph defined by a Murphi description, storing all the states it encounters in a large hash table. When a state is generated that is already in the hash table, the search algorithm does not expand its successor states (they were expanded whenever the state was originally inserted in the table).

- License: BSD like

### Mec 5

Mec 5 is a model-checker for finite AltaRicamodels, using a very expressive specification language (systems of fixpoint equations over finite relations with first-order quantifiers and equality testing).

- License: Public domain

- Web site: http://altarica.labri.fr/Tools/Mec5/

### Maria

Maria is a reachability analyzer for concurrent systems that uses Algebraic System Nets (a high-level variant of Petri nets) as its modelling formalism.

- License: GNU LGPL

- Web site: http://www.tcs.hut.fi/Software/maria/

## SAT Solvers

### CVC3

CVC3 is an automatic theorem prover for Satisfiability Modulo Theories (SMT) problems. It can be used to prove the validity (or, dually, the satisfiability) of first-order formulas in a large number of built-in logical theories and their combination.

CVC3 is the last offspring of a series of popular SMT provers, which originated at Stanford University with the SVC system. In particular, it builds on the code base of CVC Lite, its most recent predecessor. Its high level design follows that of the Sammy prover.

CVC3 works with a version of first-order logic with polymorphic types and has a wide variety of features including:

- several built-in base theories: rational and integer linear arithmetic, arrays, tuples, records, inductive data types, bit vectors, and equality over uninterpreted function symbols;

- support for quantifiers;

- an interactive text-based interface;

- a rich C and C++ API for embedding in other systems;

- proof and model generation abilities;

- predicate subtyping;

- essentially no limit on its use for research or commercial purposes (see license).

- License: BSD like

- Web site: http://www.cs.nyu.edu/acsys/cvc3/

### SAL

The heart of SAL is a language, developed in collaboration with Stanford and Berkeley, for specifying concurrent systems in a compositional way. It is supported by a tool suite that includes state of the art symbolic (BDD-based) and bounded (SAT-based) model checkers, an experimental “Witness” model checker, and a unique “infinite” bounded model checker based on SMT solving. Auxiliary tools include a simulator, deadlock checker and an automated test generator.

- License: GNU GPL

- Web site: http://sal.csl.sri.com/

### Alt Ergo

Alt-Ergo is an automatic theorem prover dedicated to program verification. Alt-Ergo is based on CC(X) a congruence closure algorithm parameterized by an equational theory X. Currently, CC(X) can be instantiated by the empty equational theory and by the linear arithmetics. Alt-Ergo contains also a home made SAT-solver and an instantiation mechanism.

- License: GNU GPL

- Web site: http://alt-ergo.lri.fr/

## Tools to help verification of real programs

I have put under this category software that can be applied to real world programs (in language like C for example) to prove properties on them.

### Boogie

Boogie is a program verification system that produces verification conditions for programs written in an intermediate language (also named Boogie). The intermediate language is easy to target from source languages such as Spec#, C#, or even C.

- License: Microsoft Public License (Ms-PL)

- Web site: http://boogie.codeplex.com/

### Saturn

The goal of the Saturn project is to statically and automatically verify properties of large (meaning multi-million line) software systems. The focus of much of our work is simultaneously achieving scalability, precision, and a straightforward way of expressing analyses that is easy to reason about. We plan to use these techniques to verify properties of a full operating system.

- License: BSD like

- Web site: http://saturn.stanford.edu/

### [[frama_-c|Frama-C]]

Frama-C is a suite of tools dedicated to the analysis of the source code of software written in C.

If you have a C program and need to

- validate it formally

- look for potential runtime errors

- audit or review it

- reverse engineer it to understand its structure

- generate formal documentation

One or more of the following Frama-C tools may be of assistance to you:

- A parser, a type checker and source level linker for C code optionally annotated with ACSL formulas.

- A set of builtin static analysis plugins:

- A runtime error detection plug-in based on abstract interpretation techniques

- A dependencies computation plug-in

- An interactive value analysis plug-in

- A Use/Defs computation plug-in

- A slicing plug-in

- A weakest precondition calculus plug-in based on Floyd-Hoare logic

- License: GNU LGPL v2

- Web site: http://frama-c.cea.fr/

### Why

Why is a verification conditions generator (VCG) back-end for other verification tools. It understands ML, C and Java languages (with the help of other programs).

- License: GNU GPL

- Web site: http://why.lri.fr/

### CIL

CIL is a framework to analyse and manipulate C programs.

- License: BSD like

- Web site: http://manju.cs.berkeley.edu/cil/

### Splint

Splint is a tool for statically checking C programs for security vulnerabilities and coding mistakes. With minimal effort, Splint can be used as a better lint. If additional effort is invested adding annotations to programs, Splint can perform stronger checking than can be done by any standard lint.

- License: GNU GPL

- Web site: http://www.splint.org/

- Debian packages: splint splint-doc

### Cqual

Cqual is a type-based analysis tool that provides a lightweight, practical mechanism for specifying and checking properties of C programs. Cqual extends the type system of C with extra user-defined type qualifiers. The programmer adds type qualifier annotations to their program in a few key places, and Cqual performs qualifier inference to check whether the annotations are correct. The analysis results are presented with a user interface that lets the programmer browse the inferred qualifiers and their flow paths.

- License: GNU GPL

- Web site: http://www.cs.umd.edu/~jfoster/cqual/

### CCured

CCured is a source-to-source translator for C. It analyzes the C program to determine the smallest number of run-time checks that must be inserted in the program to prevent all memory safety violations. The resulting program is memory safe, meaning that it will stop rather than overrun a buffer or scribble over memory that it shouldn't touch. Many programs can be made memory-safe this way while losing only 10$-160% run-time performance (the performance cost is smaller for cleaner programs, and can be improved further by holding CCured's hand on the parts of the program that it does not understand by itself). Using CCured we have found bugs that Purify misses with an order of magnitude smaller run-time cost.

- License: BSD like

- Web site: http://manju.cs.berkeley.edu/ccured/

### CHIC

CHIC is a modular verifier for behavioral compatibility checking of software and hardware components. The goal of CHIC is to be able to check that the interfaces for software or hardware components provide guarantees that satisfy the assumptions they make about each other. CHIC supports a variety of interface property specification formalisms.

- License: BSD like

### Smatch!!!

Smatch is C source checker but mainly focused checking the Linux kernel code. It is based on the papers about the Stanford Checker.

Basically, Smatch uses a modified gcc to generate .c.sm files. The .c.sm files are piped through individual Smatch scripts that print out error messages.

For example, someone might want to write a Smatch script that looked for code that called copy_to_user() while the kernel was locked. If the script saw a place that called lock_kernel() then it would record the state as locked. If the script saw a place that called unlock_kernel() it would set the state to unlocked. If the state was locked and the script saw a place that called copy_to_user() the script would print out an error message.

- License: GNU GPL

- Web site: http://smatch.sourceforge.net/

### Sparse

Sparse, the semantic parser, provides a compiler frontend capable of parsing most of ANSI C as well as many GCC extensions, and a collection of sample compiler backends, including a static analyzer also called “sparse”. Sparse provides a set of annotations designed to convey semantic information about types, such as what address space pointers point to, or what locks a function acquires or releases.

- License: OSL v1.1 (“Open Software License”)

### Stance

Features:

- Error-finding tool based on static analysis.

- Target language is C (ANSI C99), but extensible to C#/C++/Java.

- Full ANSI C99 support, including most GNU C extensions.

- Modular structure, easy extensibility, fast development.

- Easy to use interface and error path inspection.

- Makefile support and batch execution.

Errors detected:

- Memory allocation errors (null pointers, memory leaks, dangling pointers)

- Bad locking discipline (double locks/unlocks, locks not released etc.)

- Interrupt handling (cli/sti-style).

- And all the errors which can be described by state automata.

- License: GNU GPLv2

- Web site: http://stanse.fi.muni.cz/

### Focal

Focal (formerly known as FoC) is a language for software-proof codesign. In Focal, code, specifications, and proofs are developped together in the same source files, using a novel object-oriented module system. The compiler analyses the dependencies in order to ensure the consistency of the source, then translates the code to Objective Caml, and the proofs to Coq.

- License: BSD like

### [[fo_ca_lize|FoCaLize]]

The FoCaLizedevelopment effort started in 2006: it was clearly a continuation of the Focand Focal efforts. The new system was rewritten from scratch. A new language and syntax was designed and carefully implemented, with in mind ease of use, expressivity, and programmer friendyness. The addition of powerful data structure definitions together with the corresponding pattern matching facility, lead to new expressing power.

The Zenon automatic theorem prover was also integrated in the compiler and natively interfaced within the FoCaLizelanguage. New developments for recursive functions support is on the way (in particular for termination proofs).

A formal specification can be built by declaring names of functions and values and introducing properties. Then, design and implementation can incrementally be done by adding definitions of functions and proving that the implementation meets the specification or design requirements. Thus, developing in FoCaLizeis a kind of refinement process from formal model to design and code, completely done within FoCaLize. Taking the global development in consideration within the same environment brings some conciseness, helps documentation and reviewing. Thus a FoCaLizedevelopment is organised as a hierarchy that may have several roots. The upper levels of the hierarchy are built along the specification stage while the lower ones correspond to implementation and each node of the hierarchy corresponds to a progress toward a complete implementation.

The FoCaLizesystem provides means for the developers to formally express their specifications and to go step by step (in an incremental approach) to design and implementation while proving that such an implementation meets its specification or design requirements. The FoCaLizelanguage offers high level mechanisms such as inheritance, late binding, redefinition, parametrization, etc. Confidence in proofs submitted by developers or automatically done relies on formal proof verification. FoCaLizealso provides some automation of documentation production and management.

- License: BSD like

- Web site: http://focalize.inria.fr

## Tools to make formal models

### Alloy

The Alloy Analyzer is a tool developed by the Software Design Group for analyzing models written in Alloy, a simple structural modeling language based on first-order logic. The tool can generate instances of invariants, simulate the execution of operations (even those defined implicitly), and check user-specified properties of a model. Alloy and its analyzer have been used primarily to explore abstract software designs. Its use in analyzing code for conformance to a specification and as an automatic test case generator are being investigated in ongoing research projects.

- License: GNU GPL

- Web site: http://alloy.mit.edu/

### mCRL2

mCRL2 is a formal specification language with an associated toolset. The toolset can be used for modelling, validation and verification of concurrent systems and protocols.

The toolset supports a collection of tools for linearisation, simulation, state-space exploration and generation and tools to optimise and analyse specifications. Moreover, state spaces can be manipulated, visualised and analysed.

- License: BSD like

- Web site: http://www.mcrl2.org

### TLA+ Proof System

The TLA+ Proof System (TLAPS) is a platform for computerized verification of TLA+ proofs using formal reasoning systems such as automated theorem provers, proof-assistants, SMT/SAT solvers, and decision procedures. TLA+ is a specification language designed for concurrent, distributed, reactive and real-time systems, but it can also be used to formalize any discrete algorithm. The TLA+ proof language is declarative, hierarchical, and scalable to large system specifications. It provides a consistent abstraction over the various backend verifiers. The current release of TLAPS handles just enough temporal reasoning to check safety properties; an extension to the full TLA+ language is under active development.

- License: BSD

## Conclusion

It remains to test all those programs. A hard task that is not yet done.