Alt-Ergo, an automatic solver for

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...

s, is mainly used in formal program verification. It operates on the principle of

satisfiability modulo theories In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involv ...

(SMT). Development was undertaken by researchers at the

Paris-Sud University Paris-Sud University (), also known as the University of Paris — XI (or as the Orsay Faculty of Sciences, University of Paris before 1971), was a French research university distributed among several campuses in the southern suburbs of Paris, ...

, Laboratoire de Recherche en Informatique, Inria Saclay Ile-de-France, and

CNRS The French National Centre for Scientific Research (, , CNRS) is the French state research organisation and is the largest fundamental science agency in Europe. In 2016, it employed 31,637 staff, including 11,137 tenured researchers, 13,415 eng ...

. Since 2013, project management and oversight has been conducted by OCamlPro company. It is released under the

free and open-source software Free and open-source software (FOSS) is software available under a license that grants users the right to use, modify, and distribute the software modified or not to everyone free of charge. FOSS is an inclusive umbrella term encompassing free ...

CeCILL-C license.

Technologies

Design choices

Alt-Ergo employs a specialized input language with prenex polymorphism, designed to reduce the number of axioms requiring quantification and to simplify the complexity of problems. While Alt-Ergo offers partial support for the

SMT-LIB In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involv ...

2 language, its efficiency with SMT files is comparatively limited.

Main components

The core architecture of Alt-Ergo comprises three main elements: a

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...

(DFS)-based

SAT solver In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem (SAT). On input a formula over Boolean data type, Boolean variables, such as "(''x'' or ''y'') and (''x'' or not ''y'' ...

, a quantifiers instantiation engine that uses e-matching, and an assembly of

decision procedure Decision may refer to: Law and politics *Judgment (law), as the outcome of a legal case * Landmark decision, the outcome of a case that sets a legal precedent * ''Per curiam'' decision, by a court with multiple judges Books * ''Decision'' (novel ...

s for a range of built-in theories. These components collectively enable Alt-Ergo's abilities in automatic formula solving.

Built-in theories

Alt-Ergo implements (semi-)decision procedures for the following theories: *

Empty theory In mathematical logic, an uninterpreted function or function symbol is one that has no other property than its name and '' n-ary'' form. Function symbols are used, together with constants and variables, to form terms. The theory of uninterpreted ...

* Linear integer arithmetic * Linear rational arithmetic * Non-linear arithmetic * Floating point arithmetic * Polymorphic arrays * Enumerated

data type In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these ...

s * AC symbols * Record

Industrial uses

Several verification platforms are built on Alt-Ergo:
Why3
a platform for deductive program verification, uses Alt-Ergo as main prover * CAVEAT, a C-verifier developed by CEA and used by Airbus; Alt-Ergo was included in the qualification DO-178C of one of its aircraft *

Frama-C Frama-C is a set of interoperable program analyzers for C programs. The name ''Frama-C'' stands for ''Framework for Modular Analysis of C programs''. Frama-C has been developed by the French Commissariat à l'Énergie Atomique et aux Énergi ...

, a framework to analyse C-code, uses Alt-Ergo in the Jessie and WP plugins (dedicated to ''deductive program verification'') * SPARK, uses Alt-Ergo (behind GNATprove) to automate the verification of some assertions in Spark 2014 * Atelier-B can use Alt-Ergo instead of its main prover (raising success from 84% to 98% o
ANR Bware project benchmarks
*

Rodin François Auguste René Rodin (; ; 12 November 184017 November 1917) was a French sculptor generally considered the founder of modern sculpture. He was schooled traditionally and took a craftsman-like approach to his work. Rodin possessed a u ...

, a B-method framework developed by Systerel, can use Alt-Ergo as a back-end
Cubicle
an open source model checker to verify safety properties of array-based transition systems
EasyCrypt
a toolset for reasoning about relational properties of probabilistic computations with adversarial code * BWARE * Cafein * FUI Hi-Lite * Decert * ADT Alt-Ergo * A3PAT

References

External links

*, OcamlPro
Alt-Ergo at LRI
OCaml software Formal methods tools Software testing tools Linux software {{Science-software-stub