2026-06-25·9 min read·sota.io team

Deploy Alt-Ergo to Europe — Sylvain Conchon 🇫🇷 + Evelyne Contejean 🇫🇷 + OCamlPro 🇫🇷 (LRI Paris-Sud, 2006), the EU-Native SMT Solver Powering Frama-C, Why3, and GNATprove, on EU Infrastructure in 2026

Every formal proof about a C function at Airbus 🇫🇷, every SPARK Ada subprogram verified at AdaCore 🇫🇷 Paris, every WhyML module checked by Why3 — at the bottom of the deductive stack, there is a solver that must answer the question: is this first-order logical formula satisfiable, or is it a contradiction? That question is answered, for the majority of obligations in the EU formal verification ecosystem, by a single piece of software built in Paris: Alt-Ergo.

Alt-Ergo is an SMT solver — a Satisfiability Modulo Theories engine — developed by Sylvain Conchon 🇫🇷 and Evelyne Contejean 🇫🇷 at the LRI (Laboratoire de Recherche en Informatique, CNRS UMR 8623, Université Paris-Sud, Orsay) and first published in 2006. It is now developed and commercially maintained by OCamlPro 🇫🇷 (Paris), the French company that also maintains the OCaml compiler toolchain for the opam ecosystem.

Alt-Ergo is not a general-purpose SMT solver competing with Z3 or CVC5 across all problem domains. Its distinguishing characteristic is optimisation for program verification proof obligations — the shapes of logical formulas that arise from C and Ada programs annotated with function contracts. Frama-C WP generates ACSL-derived weakest preconditions; GNATprove generates SPARK Ada subprogram contracts; Why3 generates WhyML program obligations. In every case, the proof obligations share a structural signature: linear arithmetic over integers and rationals, function application with congruence, array reads and writes, and quantified invariants instantiated over finite domains. Alt-Ergo is tuned for precisely this signature.

The institutional pedigree is entirely French. LRI is a joint research unit of CNRS and Université Paris-Sud (now Université Paris-Saclay), funded by the French Ministry of Higher Education and Research. OCamlPro is a French company with no US parent. Alt-Ergo is 100% EU-origin — no US Cloud Act jurisdiction, no ITAR encumbrance for aerospace customers.

What Is SMT Solving?

Before examining Alt-Ergo's architecture, it is worth being precise about what SMT solving means — since the term appears throughout formal verification documentation without always being explained.

SAT solving answers the satisfiability question for propositional logic: given a Boolean formula over propositional variables, does there exist a truth assignment that makes the formula true? SAT solvers (using the CDCL algorithm — Conflict-Driven Clause Learning) can handle formulas with millions of variables and clauses in seconds.

SMT solving extends SAT to first-order logic with background theories: given a formula that may contain integer arithmetic expressions, function applications, array accesses, or bitvector operations — in addition to Boolean structure — does there exist a model over the theory's domain that satisfies the formula?

A proof obligation from Frama-C WP might look like:

∀ i : int. 0 ≤ i < n → a[i] ≥ 0 → sum(a, 0, i) ≥ 0 → sum(a, 0, i+1) ≥ 0

This mixes universal quantification, integer arithmetic (0 ≤ i < n), array indexing (a[i]), and an uninterpreted function (sum). A pure SAT solver cannot handle it. An SMT solver handles it by combining a SAT backbone with theory solvers that reason within each theory (integers, arrays, uninterpreted functions) and exchange lemmas to reach a global answer.

Alt-Ergo's Architecture: DPLL(T) + Shostak + E-Matching

Alt-Ergo's architecture follows the DPLL(T) paradigm — the standard framework for modern SMT solvers — with specific theory combination and quantifier instantiation strategies tuned for program verification.

The DPLL(T) Framework

DPLL(T) separates concerns between the propositional backbone and the theory solvers:

Input formula (first-order + theory terms)
              ↓ Abstraction
Propositional skeleton (Boolean variables stand for theory atoms)
              ↓ DPLL SAT backbone
Propositional assignment (candidate model)
              ↓ Theory check
Theory solvers: is this assignment T-consistent?
    ├── Linear Arithmetic solver (integers + rationals)
    ├── Uninterpreted Functions / Congruence Closure
    ├── Array solver
    ├── Bitvector solver (Alt-Ergo Pro)
    └── Algebraic Data Type solver
              ↓ T-inconsistent: add theory lemma to propositional problem
              ↓ T-consistent: SAT (satisfiable model found)
              ↓ No more assignments: UNSAT (formula is a contradiction = proof obligation discharged)

When the output is UNSAT, it means the negation of the proof obligation is unsatisfiable — the proof obligation is a tautology — and the verification condition is discharged: the code is proved correct with respect to that property.

Theory Combination: Shostak Theories

Alt-Ergo uses Shostak's combination method for theories that admit a canonizer and a solver: algorithms that can respectively reduce terms to a canonical form and solve equalities within the theory. Shostak combination is more efficient than the general Nelson-Oppen framework for theories that satisfy Shostak's conditions — and linear arithmetic over integers and rationals qualifies.

The congruence closure algorithm handles uninterpreted functions: if f(a) = b and a = c, then f(c) = b — without knowing anything about f. This covers the shape of most function contract postconditions, where the function's return value is characterised by a postcondition rather than an explicit definition.

Quantifier Instantiation: E-Matching

The most demanding part of program verification proof obligations are quantified formulas: ∀ i. P(i) or ∃ x. Q(x). Quantifiers cannot be handled directly by the theory solvers — they must be instantiated to ground formulas before the theory combination can proceed.

Alt-Ergo uses E-matching: a technique that finds terms in the current proof context that match the pattern in the quantifier trigger, then instantiates the quantifier body with those terms. For the loop invariant ∀ i. 0 ≤ i < k → a[i] ≥ 0, when the solver finds term a[j] in the context, it instantiates with i := j and adds 0 ≤ j < k → a[j] ≥ 0 as a ground lemma.

E-matching is a heuristic: it is complete for certain shapes of quantifiers (specifically, unit theories) but not in general. For obligations that E-matching cannot discharge, Why3 routes to Isabelle/HOL or Coq/Rocq for interactive proof construction.

Alt-Ergo's Input Languages

Alt-Ergo accepts two input formats, reflecting its dual role as a standalone solver and an embedded backend.

Native Alt-Ergo Format (.ae)

The native .ae format is higher-level than SMT-LIB 2, closer to the mathematical formulas generated by Why3's prover drivers:

(* Alt-Ergo native format: prove that summing non-negative values is non-negative *)

(* Type declarations *)
type 'a array

(* Function declarations *)
logic select : 'a array, int -> 'a
logic sum : int array, int, int -> int

(* Axioms *)
axiom sum_base : forall a : int array, i : int. sum(a, i, i) = 0
axiom sum_rec  : forall a : int array, i j : int.
  i < j -> sum(a, i, j) = select(a, i) + sum(a, i+1, j)

(* Goal: sum of non-negative values is non-negative *)
goal sum_nonneg :
  forall a : int array, n : int.
  n >= 0 ->
  (forall i : int. 0 <= i < n -> select(a, i) >= 0) ->
  sum(a, 0, n) >= 0

Running Alt-Ergo on this goal produces:

File "sum.ae", line 15, characters 0-157: Valid (0.04s)

Valid means the goal is a logical consequence of the axioms — the proof obligation is discharged in 40 milliseconds.

SMT-LIB 2 Format (.smt2)

Alt-Ergo also accepts SMT-LIB 2 — the standard interchange format for SMT solvers — making it interoperable with any verification tool that generates SMT-LIB 2 output:

; SMT-LIB 2 format: array bounds check
(set-logic AUFLIA)
(declare-fun a (Int) Int)
(declare-const n Int)

; Preconditions
(assert (>= n 0))
(assert (forall ((i Int)) (=> (and (>= i 0) (< i n)) (>= (a i) 0))))

; Negate the conclusion (proof by refutation)
(assert (not (>= (+ (a 0) (a 1)) 0)))
(assert (>= n 2))

; Ask: is the negation satisfiable?
(check-sat)
; Expected: unsat — the negation has no model — goal is proved

The EU Deductive Stack: Frama-C → Why3 → Alt-Ergo

Alt-Ergo's most important deployment context is as the default SMT backend in the three-layer EU deductive verification stack. Understanding this stack is essential for understanding why Alt-Ergo matters for aerospace, nuclear, and railway EU compliance.

Layer 1: Frama-C (CEA LIST + INRIA 🇫🇷)

Frama-C's WP plugin computes weakest preconditions of C functions annotated with ACSL contracts. For each requires/ensures pair, WP generates a verification condition: a first-order formula that, if valid, proves the function satisfies its contract. These verification conditions are passed to Why3.

Layer 2: Why3 (LRI / INRIA Saclay 🇫🇷)

Why3 receives the Frama-C verification conditions, encodes them in WhyML's type system, and dispatches them to provers via driver files — prover-specific translations. The Why3 driver for Alt-Ergo translates proof obligations to Alt-Ergo's native .ae format, calibrated for Alt-Ergo's specific quantifier triggers and theory combination.

Layer 3: Alt-Ergo (OCamlPro 🇫🇷)

Alt-Ergo receives the encoded proof obligations and runs DPLL(T) with Shostak theory combination and E-matching. For the vast majority of program verification obligations — those involving linear arithmetic and uninterpreted function equalities — Alt-Ergo returns Valid in milliseconds.

C source with ACSL contracts
         ↓ Frama-C WP plugin (CEA LIST 🇫🇷, Paris-Saclay)
Weakest Preconditions: ∀ inputs. {pre} code {post}
         ↓ Why3 encoding (LRI / INRIA Saclay 🇫🇷)
Proof obligations in Why3 format
         ↓ Alt-Ergo driver (OCamlPro 🇫🇷, Paris)
Alt-Ergo DPLL(T) + Shostak + E-matching
         ↓
Valid / Unknown / Timeout
         ↓ Unknown/Timeout: route to Z3, CVC5, Isabelle/HOL

The entire stack — from C source to proof certificate — runs on French public research infrastructure with no US toolchain dependency. For Airbus 🇫🇷 A350/A380 DO-178C Level A avionics software, this is not merely convenient: it is a compliance requirement. ITAR-controlled aerospace models cannot be sent to US cloud infrastructure for analysis. Alt-Ergo running on EU servers resolves this constraint at the tool level.

GNATprove / SPARK Ada (AdaCore 🇫🇷 Paris)

The same architecture applies to SPARK Ada. AdaCore's GNATprove tool uses Why3 as its intermediate verification language and Alt-Ergo as the default SMT solver:

SPARK Ada source (subprogram contracts)
         ↓ GNATprove flow analysis + proof generation (AdaCore 🇫🇷)
SPARK proof obligations
         ↓ Why3 encoding
         ↓ Alt-Ergo 🇫🇷 (primary) + Z3 + CVC5 (overflow)
Proved / Unproved

Every Airbus 🇫🇷 A350 DO-178C Level A Ada subprogram verified by GNATprove passes through Alt-Ergo. Every EUROCONTROL 🇧🇪 SESAR ATM Ada module verified for flight safety uses Alt-Ergo. The EU formal methods deductive stack is not a theoretical construction — it is production infrastructure for European aerospace.

Institutional Provenance

Sylvain Conchon 🇫🇷 is Professor at Université Paris-Saclay (formerly Université Paris-Sud), where he leads research in automated deduction, SMT solving, and type theory. His research group at LMF (Laboratoire Méthodes Formelles, successor to LRI) continues to develop Alt-Ergo's formal foundations.

Evelyne Contejean 🇫🇷 is Directrice de Recherche at CNRS, based at LMF / Université Paris-Saclay. Her research focuses on rewriting theory, constraint solving, and algebraic decision procedures — the theoretical core of Alt-Ergo's Shostak combination.

OCamlPro (Paris) was founded by alumni of INRIA Rocquencourt to provide commercial OCaml tooling and formal verification services. OCamlPro maintains Alt-Ergo under a dual licence: CeCILL-C (a French free software licence, legally equivalent to LGPL under French law, compatible with GPL) for the open-source version, and a commercial licence for Alt-Ergo Pro — an extended version with improved bitvector arithmetic, floating-point theories (IEEE 754), and performance optimisations for embedded systems verification.

The LMF (Laboratoire Méthodes Formelles) is a joint research unit: CNRS UMR 9653 + Université Paris-Saclay + ENS Paris-Saclay + CentraleSupélec. It is funded by the French Ministry of Higher Education and Research. No US jurisdiction applies to its research outputs.

EU Industrial Applications

Airbus 🇫🇷 — DO-178C DAL A Avionics

Airbus uses Frama-C WP with Alt-Ergo to formally verify C code in A350/A380 avionics systems at DO-178C Design Assurance Level A — the highest assurance level, requiring formal verification credit. Alt-Ergo discharges the majority of proof obligations; complex obligations fall through to Z3 or Isabelle. The EU-origin of Alt-Ergo satisfies ITAR data residency requirements for aerospace intellectual property.

EDF 🇫🇷 — IEC 61508 SIL4 Nuclear I&C

EDF (Électricité de France) uses Frama-C with Alt-Ergo for reactor protection function C code under IEC 61508 SIL4 — the highest safety integrity level for industrial systems. Alt-Ergo-discharged proof obligations provide formal evidence for the safety case documentation required by the French nuclear regulator (ASN).

Thales 🇫🇷 — EN 50128 SIL4 Railway

Thales uses Frama-C WP for railway interlocking C code under EN 50128 SIL4. Alt-Ergo processes the arithmetic-heavy proof obligations from station control and track circuit monitoring code. The EU origin satisfies French export control requirements for railway signalling system intellectual property.

AdaCore 🇫🇷 — SPARK Ada Ecosystem

AdaCore's entire SPARK Ada customer base — Airbus, EUROCONTROL, MBDA 🇫🇷🇬🇧🇩🇪, Siemens Mobility 🇩🇪, Rolls-Royce FADEC 🇬🇧 — uses Alt-Ergo as the primary prover via GNATprove. AdaCore publishes Alt-Ergo performance benchmarks against Z3 and CVC5 specifically for SPARK Ada proof obligations: Alt-Ergo consistently leads on pure arithmetic and linear arithmetic obligations, while Z3 leads on bit-vector and non-linear arithmetic.

Regulatory Compliance Angles

EU AI Act Art. 9 — Technical Documentation for High-Risk AI

EU AI Act Article 9 requires that high-risk AI systems (Annex III: autonomous driving, medical diagnosis, critical infrastructure, employment screening) maintain technical documentation proving system behaviour. Alt-Ergo-discharged proof obligations constitute machine-checked formal evidence — not test results, not design documents, but mathematical proofs. For AI inference C code or SPARK Ada components in Annex III systems, Alt-Ergo provides the verification evidence that Article 9 demands.

Alt-Ergo can verify ACSL frame conditions (assigns clauses in Frama-C, global variables annotations in SPARK) that prove functions access only the data they are specified to access. A function annotated assigns \nothing and proved by Alt-Ergo via Frama-C WP cannot write to memory it is not supposed to touch — a machine-checked enforcement of the data minimisation principle required by GDPR Art. 25.

IEC 61508 SIL4 / EN 50128 SIL4 — Formal Verification Credit

IEC 61508 and EN 50128 both recognise formal verification as a technique for achieving SIL3 and SIL4. The standard requires that the specification language has "formally defined syntax and semantics." ACSL (for Frama-C) and SPARK Ada contracts satisfy this requirement; Alt-Ergo-discharged proof obligations constitute the formal verification evidence.

NIS2 — Critical Infrastructure Security

NIS2 requires operators of critical infrastructure (energy, transport, water, health) to maintain state-of-the-art cybersecurity measures. For C and Ada control software in critical infrastructure OT systems, Alt-Ergo-verified proof obligations demonstrate that software components meet their formal specifications — a concrete, auditable cybersecurity measure.

Deploy Alt-Ergo on sota.io

Alt-Ergo runs on Linux (amd64/arm64) with minimal dependencies — it is a single OCaml binary. Installation via the opam OCaml package manager or via system packages:

# Ubuntu/Debian
sudo apt-get install alt-ergo

# OPAM (OCaml ecosystem) — latest version
opam install alt-ergo

# Verify installation
alt-ergo --version
# Alt-Ergo 2.5.x — OCamlPro (Paris, France)

sota.io deployment — Dockerfile for an Alt-Ergo verification service:

FROM sotaio/builder:ubuntu-24.04

# Install Alt-Ergo + Why3 (full EU deductive stack)
RUN apt-get update && apt-get install -y \
    alt-ergo \
    why3 \
    ocaml \
    frama-c \
    && rm -rf /var/lib/apt/lists/*

# Detect provers in Why3
RUN why3 config detect
# Output: Alt-Ergo x.x, Eprover x.x, ...

WORKDIR /verification

# Copy ACSL-annotated C source
COPY src/ ./src/

# Run Frama-C WP with Alt-Ergo via Why3
RUN frama-c -wp \
    -wp-prover alt-ergo,z3 \
    -wp-timeout 30 \
    -wp-report report.json \
    src/safety_critical.c

# Standalone Alt-Ergo on Why3-generated obligations
RUN why3 prove -P alt-ergo obligations/*.why

sota.io handles the underlying Linux infrastructure — OCaml runtime, memory limits for large proof obligation sets, process isolation between concurrent verification jobs — while you focus on writing and verifying code.

The free tier supports verification pipelines up to 512 MB memory: sufficient for Alt-Ergo on typical Frama-C WP output (a 500-function C module generates several thousand proof obligations, each requiring 1–50 ms in Alt-Ergo). Larger obligation sets — full aerospace module verification, 50,000+ obligations — scale on sota.io's standard tier.

The EU SMT Solver Landscape

Alt-Ergo occupies a specific position in the broader SMT solver landscape that is worth making explicit.

Z3 (Microsoft Research Redmond, US): dominant general-purpose SMT solver, used as fallback by Why3/Frama-C for non-linear arithmetic and complex bit-vector obligations. US origin — ITAR and Cloud Act considerations apply.

CVC5 (Stanford/NYU, US): strong on strings, sets, and quantified arithmetic. US origin.

MathSAT5 (FBK Trento 🇮🇹): EU-native, used by nuXmv for infinite-state model checking (different problem domain from deductive verification).

Alt-Ergo (OCamlPro 🇫🇷): EU-native, optimised for program verification proof obligations, default prover in the French formal verification toolchain.

The strategic implication: organisations subject to ITAR, GDPR, or EU AI Act requirements that prefer to keep their formal verification infrastructure on EU-sovereign computing can use Alt-Ergo as the primary prover and accept that a small percentage of obligations (non-linear arithmetic, complex bit-vectors) will require Z3. For the EU aerospace and nuclear sectors, this tradeoff is already validated in production.