2026-04-05·10 min read·sota.io team

Deploy UltimateAutomizer to Europe — Matthias Heizmann 🇩🇪 (University of Freiburg), the Automata-Based Software Verifier that Wins SV-COMP, on EU Infrastructure in 2026

At the annual SV-COMP competition held at ETAPS/TACAS, two German university tools reliably occupy the top positions in the ReachSafety category — the flagship category that tests whether a C program can reach a designated error location. One is CPAchecker from LMU Munich. The other is UltimateAutomizer from the University of Freiburg.

Where CPAchecker expresses its algorithms through the CPA framework, UltimateAutomizer takes a fundamentally different approach: it reduces software verification to automata theory. Programs are represented as automata. Safety properties are represented as automata. Verification becomes a question of automata complementation and language emptiness. Refinement is driven by Craig interpolation over SMT formulas — extracting loop invariants and path conditions from infeasible counterexamples. The result is a verifier that handles subtle control-flow structures — nested loops, recursive functions, complex inter-procedural interactions — with unusual depth.

UltimateAutomizer is not a standalone tool. It is the verification-oriented plugin within the Ultimate program analysis framework, developed at the Chair of Programming Languages and Software Engineering at the University of Freiburg.

Matthias Heizmann and Andreas Podelski at Freiburg

Andreas Podelski 🇩🇪 is a Full Professor at the University of Freiburg, head of the Software Engineering group, and one of Europe's leading researchers in formal verification and program analysis. He has worked on model checking, abstract interpretation, and transition invariants since the early 1990s. His group at Freiburg produced a series of influential results on termination analysis (the transition invariant method, published with Thomas Henzinger 🇦🇹 at EPFL) and on the automata-theoretic approach to software verification that became the algorithmic core of UltimateAutomizer.

Matthias Heizmann 🇩🇪 is a senior researcher and the primary developer of UltimateAutomizer at Freiburg. His PhD thesis, Automata, Trace Abstraction, and Software Verification, developed the theoretical foundations of the trace abstraction approach and its connection to Craig interpolation. Heizmann has been the main contributor to UltimateAutomizer's SV-COMP entries and has published at CAV, TACAS, and POPL.

The foundational TACAS 2013 tool paper is: Ultimate Automizer and the Search for Perfect Interpolants — by Matthias Heizmann, Jürgen Christ, Daniel Dietsch, Evren Ermis, Jochen Hoenicke, Markus Lindenmann, Alexander Nutz, Christian Schilling, and Andreas Podelski. The paper introduces the trace abstraction framework and demonstrates that choice of interpolation procedure is the dominant factor in UltimateAutomizer's performance.

The University of Freiburg 🇩🇪 was founded in 1457 — one of the oldest universities in the German-speaking world. Located in Baden-Württemberg, it is a founding member of the League of European Research Universities (LERU), the same consortium that includes Cambridge 🇬🇧, Oxford 🇬🇧, ETH Zurich 🇨🇭, KU Leuven 🇧🇪, Leiden 🇳🇱, and UCL 🇬🇧. Podelski's research is funded by the German Research Foundation (DFG) and EU Horizon Europe programmes.

Trace Abstraction: Programs as Languages of Error Traces

The conceptual core of UltimateAutomizer is the trace abstraction framework. The key insight is that a software verification problem — "does this program have any execution that reaches an error location?" — can be reformulated as a language containment problem over finite and infinite sequences of program statements.

A trace is a finite sequence of program statements: an assignment, a branch condition, a loop guard, a function call. The set of all possible execution traces of a program — the set of all paths through the control-flow graph, considering all possible input values — forms a (potentially infinite) language over the alphabet of program operations.

Safety verification asks: does the language of error-reaching traces have any element that is also a feasible execution — a trace that corresponds to a consistent assignment of values to program variables?

UltimateAutomizer's approach:

Represent the program's set of error-reaching traces as a Büchi automaton (for liveness) or a regular language automaton (for reachability)
Abstract this language using an interpolant automaton — an overapproximation that preserves feasibility properties
Check whether the abstracted language is empty
If not: extract a candidate trace, check its feasibility via SMT
If infeasible (spurious counterexample): compute Craig interpolants from the proof of infeasibility, construct a new interpolant automaton, and exclude the infeasible trace and all traces it overapproximates
Repeat until the language is empty (all error traces excluded — program is safe) or a feasible counterexample is found

The key operation in step 5 — constructing an interpolant automaton from a sequence of Craig interpolants — is what gives the algorithm its automata-theoretic character. The sequence of interpolants φ0, φ1, ..., φn (where φ0 = true, φn = false, and each φᵢ → wp(φᵢ₊1, stmtᵢ)) defines an automaton state for each program location and a transition that is enabled exactly when the current formula holds. This automaton recognizes all traces that "look like" the infeasible trace at the level of the interpolant predicates.

The elegance of the approach: interpolants define automata automatically. No manual predicate selection. No manual invariant annotation. The invariants emerge from the SMT-proof of trace infeasibility.

Büchi Automata for LTL Properties

For liveness properties — does this program eventually terminate? does this loop always make progress? — UltimateAutomizer uses Büchi automata, the standard model for recognizing ω-regular languages (languages of infinite words, i.e., infinite execution traces).

A Büchi automaton is a finite automaton over infinite sequences where acceptance requires visiting a designated set of states infinitely often. An LTL (Linear Temporal Logic) formula can be converted into a Büchi automaton (Vardi-Wolper, 1986) — this is the standard construction used in hardware model checking tools like SPIN and NuSMV.

For software verification, liveness checking becomes: does the program have any lasso-shaped execution — a finite prefix followed by an infinite loop — that visits an accepting state infinitely often? UltimateAutomizer's UltimateBuchiAutomizer plugin handles this case, checking termination via Büchi automata emptiness in the product of the program automaton and the property Büchi automaton.

Craig Interpolation via SMTInterpol

The interpolation engine underneath UltimateAutomizer is SMTInterpol — developed by Jochen Hoenicke 🇩🇪, a co-author of the TACAS 2013 UltimateAutomizer paper, at the University of Freiburg. This is a uniquely EU collaboration: the verifier and its SMT backend were built at the same institution by overlapping research groups.

SMTInterpol computes sequence interpolants — a sequence of formulas φ0, φ1, ..., φn that over-approximate the strongest postcondition along a program path — directly from SMT proofs over the theory of linear arithmetic and uninterpreted functions. The interpolation procedure for the quantifier-free theory of linear real arithmetic (LRA) over an infeasible path produces the tightest possible invariants: interpolants that are exact consequences of the path formula.

# SMTInterpol is also distributed as a standalone JAR
# for sequence interpolant computation in verification pipelines
java -jar smtinterpol.jar program-path.smt2

# UltimateAutomizer uses SMTInterpol internally
# but the tool accepts standard C programs directly:
java -jar UltimateAutomizer.jar \
  --spec PropertyReachability.prp \
  --file program.c \
  --architecture 64bit

The Ultimate Framework

UltimateAutomizer is one plugin in the broader Ultimate program analysis framework, which provides shared infrastructure for multiple analysis tools developed at Freiburg:

UltimateAutomizer — safety verification via trace abstraction and CEGAR
UltimateBuchiAutomizer — termination + liveness verification via Büchi automata
UltimateKojak — large-block encoding for inter-procedural verification (inspired by IMPACT/LLVM)
UltimateGemCutter — concurrent program verification (thread safety + data race analysis)
UltimatePea2IcfgTranslator — Phase Event Automata (PEA) to interprocedural control-flow graph translation — a bridge between requirements engineering (AUTOSAR/EAST-ADL PEA notation) and formal verification

The Ultimate framework is built on the Eclipse rich client platform and provides a shared ICFG (interprocedural control-flow graph) intermediate representation, a shared parse infrastructure for C (via CDT/CIF), and a plugin architecture where multiple analyses can be combined in a pipeline.

SV-COMP Performance

At SV-COMP 2024 (TACAS 2024, Luxembourg 🇱🇺), UltimateAutomizer placed in the top tier across multiple categories:

Category	UltimateAutomizer Performance
ReachSafety	Top tier, multiple gold medals in subcategories
MemSafety	Consistently top-3
Termination	Category-leading (UltimateBuchiAutomizer)
SoftwareSystemsVerification	Competitive on real Linux kernel benchmarks

The SV-COMP scoring system penalizes false results more than it rewards correct ones — a tool that gives a wrong SAFE verdict for an unsafe program loses more points than it gained. UltimateAutomizer's trace-abstraction approach is particularly strong in the soundness dimension: the automata-theoretic exclusion of infeasible traces is a proof, not a heuristic. When UltimateAutomizer reports SAFE, it has generated a machine-checkable certificate.

SV-COMP EU Dominance

The SV-COMP ReachSafety leaderboard is an index of EU academic strength in formal verification:

Tool	Institution	Country
CPAchecker	LMU Munich	🇩🇪 Germany
UltimateAutomizer	University of Freiburg	🇩🇪 Germany
nuXmv	FBK Trento	🇮🇹 Italy
Gazer-Theta	BME Budapest	🇭🇺 Hungary
VeriAbs	Siemens AG	🇩🇪 Germany
ESBMC	Manchester	🇬🇧 UK
CBMC	Oxford	🇬🇧 UK

The two consistent top performers — CPAchecker and UltimateAutomizer — are both from German universities. Both rely on EU-developed SMT solvers (SMTInterpol Freiburg + MathSAT5 FBK Trento + Princess Uppsala). Both are funded by DFG and EU Horizon Europe. The SV-COMP is, in practice, a showcase of German CS university research quality.

How to Run UltimateAutomizer

UltimateAutomizer is distributed as a pre-built JAR. For standard safety verification of a C program:

# Download UltimateAutomizer (latest release from GitHub)
wget https://github.com/ultimate-pa/ultimate/releases/download/v0.2.4/UltimateAutomizer-linux.zip
unzip UltimateAutomizer-linux.zip
cd UltimateAutomizer

# Verify reachability property (SV-COMP format)
java -jar plugins/org.eclipse.equinox.launcher_*.jar \
  -data workspace/ \
  --spec config/PropertyReachability.prp \
  --file program.c \
  --architecture 64bit

# Verify memory safety
java -jar plugins/org.eclipse.equinox.launcher_*.jar \
  -data workspace/ \
  --spec config/PropertyMemSafety.prp \
  --file program.c \
  --architecture 64bit

# Check termination (UltimateBuchiAutomizer)
java -jar plugins/org.eclipse.equinox.launcher_*.jar \
  -data workspace/ \
  --spec config/PropertyTermination.prp \
  --file program.c \
  --architecture 64bit

The property file is an SV-COMP-standard .prp file:

# PropertyReachability.prp: check that __VERIFIER_error() is unreachable
CHECK( init(main()), LTL(G ! call(__VERIFIER_error())) )

This is a temporal logic specification: "globally, the program does not call __VERIFIER_error()". UltimateAutomizer converts this LTL formula to a Büchi automaton, constructs the product with the program automaton, and checks language emptiness.

Docker Deployment for CI/CD

A production Dockerfile for a UltimateAutomizer verification service:

FROM debian:bookworm-slim

# Java 17 is required
RUN apt-get update && apt-get install -y \
    wget \
    unzip \
    gcc \
    cpp \
    openjdk-17-jre-headless \
    && apt-get clean

# Download UltimateAutomizer
ARG UA_VERSION=0.2.4
RUN wget -q https://github.com/ultimate-pa/ultimate/releases/download/v${UA_VERSION}/UltimateAutomizer-linux.zip \
    && unzip -q UltimateAutomizer-linux.zip -d /opt/ultimate \
    && rm UltimateAutomizer-linux.zip

WORKDIR /opt/ultimate/UltimateAutomizer

# Copy sources and property specs
COPY src/ /workspace/src/
COPY specs/ /workspace/specs/

CMD ["bash", "-c", \
     "for src in /workspace/src/*.c; do \
        echo \"=== Verifying $(basename $src) ===\"; \
        java -jar plugins/org.eclipse.equinox.launcher_*.jar \
          -data /tmp/workspace-$(basename $src .c) \
          --spec /workspace/specs/PropertyReachability.prp \
          --file \"$src\" \
          --architecture 64bit 2>&1; \
      done"]

For GitHub Actions integration:

# .github/workflows/ultimateautomizer.yml
name: UltimateAutomizer Formal Verification

on: [push, pull_request]

jobs:
  verify:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      
      - name: Set up Java 17
        uses: actions/setup-java@v4
        with:
          java-version: '17'
          distribution: 'temurin'
      
      - name: Download UltimateAutomizer
        run: |
          wget -q https://github.com/ultimate-pa/ultimate/releases/download/v0.2.4/UltimateAutomizer-linux.zip
          unzip -q UltimateAutomizer-linux.zip -d /opt/ultimate
      
      - name: Verify safety properties
        run: |
          cd /opt/ultimate/UltimateAutomizer
          for src in $GITHUB_WORKSPACE/src/*.c; do
            echo "=== Verifying $(basename $src) ==="
            java -jar plugins/org.eclipse.equinox.launcher_*.jar \
              -data /tmp/ws-$(basename $src .c) \
              --spec config/PropertyReachability.prp \
              --file "$src" \
              --architecture 64bit
          done
      
      - name: Check termination
        run: |
          cd /opt/ultimate/UltimateAutomizer
          for src in $GITHUB_WORKSPACE/src/loops/*.c; do
            java -jar plugins/org.eclipse.equinox.launcher_*.jar \
              -data /tmp/ws-term-$(basename $src .c) \
              --spec config/PropertyTermination.prp \
              --file "$src" \
              --architecture 64bit
          done

Industrial Relevance: EU Safety-Critical Systems

Automotive: ISO 26262 ASIL D

UltimateAutomizer is applicable to AUTOSAR C code verification under ISO 26262 at ASIL D level. The SV-COMP benchmarks include C programs drawn from Linux device drivers and embedded control systems — the same code patterns that appear in AUTOSAR basic software (BSW) implementations.

For automotive teams at Bosch 🇩🇪, Continental 🇩🇪, ZF Friedrichshafen 🇩🇪, and Infineon 🇩🇪, UltimateAutomizer's trace abstraction approach provides:

Absence of runtime errors (null pointer dereference, buffer overflow, integer overflow) with machine-generated proof certificates
Termination proofs for safety-relevant control loops (adaptive cruise control state machines, ABS pressure modulation loops)
Reachability proofs showing safety mechanisms (watchdog resets, limp-home modes) are reachable under fault conditions

The inter-procedural analysis is critical for AUTOSAR: function calls across runnable boundaries, shared BSW module APIs, OS task interactions. UltimateKojak's large-block encoding handles these inter-procedural patterns without state-space explosion.

PEA-to-ICFG for Requirements Traceability

The UltimatePea2IcfgTranslator plugin provides a direct bridge between Phase Event Automata (PEA) — the formal semantics notation used in AUTOSAR/EAST-ADL requirements engineering — and the ICFG verification infrastructure.

This means: your ISO 26262 requirements (written in PEA notation in your requirements management tool) can be automatically translated into verification tasks that UltimateAutomizer checks against the C implementation. Requirements traceability + formal verification in a single toolchain — no manual encoding, no interpretation step.

IEC 61508 SIL 3/4

For German Tier-1 industrial control manufacturers — Beckhoff Automation 🇩🇪, Sick AG 🇩🇪, WAGO 🇩🇪, Pilz 🇩🇪 — IEC 61508 SIL 3/4 certification requires formal verification evidence for safety-critical C code in PLCs and safety I/O modules.

UltimateAutomizer's verification results, combined with witness exports compatible with the SV-COMP witness format, provide:

Machine-readable SAFE certificates for absence of specific error patterns
Counterexamples (in SV-COMP witness format) for any safety violations found
A documented, reproducible verification pipeline (JAR version + configuration file + property spec)

The documented reproducibility satisfies IEC 61508 Part 3's requirement for "software tool confidence level" (T1 through T3) assessment.

EN 50128 SIL 4: Railway Signalling

Siemens Mobility 🇩🇪, Thales Rail 🇫🇷, Alstom 🇫🇷, and Hitachi Rail Europe 🇬🇧🇮🇹 develop EN 50128 SIL 4 software for European Train Control System (ETCS) onboard units and trackside systems. C and C++ remain the implementation languages for safety-critical ETCS components.

UltimateAutomizer's termination analysis (via UltimateBuchiAutomizer) is particularly relevant for EN 50128: railway safety requirements mandate deterministic response time — control loops must terminate and respond within bounded time. Liveness proofs via Büchi automata emptiness checks provide formal evidence that these bounds hold for all possible train state combinations.

EU Regulatory Context

EU Cyber Resilience Act (CRA) 2027

The CRA's requirement for absence of known exploitable vulnerabilities can be partially addressed via formal verification. UltimateAutomizer's SAFE certificates for:

Buffer overflow absence (MemSafety property)
Null pointer dereference absence (MemSafety)
Integer overflow absence (Overflow property)
Unreachability of attack-relevant error states (ReachSafety)

These are machine-generated, reproducible proofs — stronger evidence than testing or static analysis warnings, and directly archivable in a CRA technical documentation package.

EU AI Act Article 9: Risk Management Systems

For high-risk AI systems with embedded C inference engines — automotive ADAS Annex III §3, medical device classification Annex III §5, industrial robot control Annex III §6 — UltimateAutomizer verification of the C runtime provides:

Reachability proofs that the inference API cannot reach undefined behavior for all valid input ranges
Termination proofs that the inference loop terminates for all inputs (no infinite loops that could stall safety-critical systems)
Memory safety proofs that weight array accesses cannot overflow for valid model sizes

The SV-COMP correctness witness format is compatible with EU conformity assessment body (CAB) technical review — a structured XML certificate is easier to audit than a test suite.

UltimateAutomizer's reachability analysis with custom property automata can verify data flow properties — checking that personal data cannot reach an output buffer or logging sink without passing through an authorization check. This provides formal evidence for GDPR Art. 25 (privacy by design) and Art. 32 (technical security measures) compliance.

The Freiburg Formal Verification Ecosystem

The University of Freiburg has produced a cluster of related formal verification tools beyond UltimateAutomizer:

SMTInterpol (Jochen Hoenicke 🇩🇪, now also at ETH Zurich 🇨🇭) — the Craig interpolation engine underlying UltimateAutomizer and several other EU verifiers
Büchi Store — a library of Büchi automata constructions used in UltimateBuchiAutomizer
TreeAutomizer (Daniel Dietsch 🇩🇪) — Horn-clause-based verification using tree automata, extending the automata-theoretic approach to CHC solving

Hoenicke's SMTInterpol is used not only in UltimateAutomizer but also as a backend option in CPAchecker (LMU Munich) and is referenced in the Viper/Chalice pipeline (ETH Zurich). This cross-institutional sharing of SMT infrastructure is a characteristic of EU formal verification research: tools are designed for interoperability, not isolation.

Deploying UltimateAutomizer on sota.io

UltimateAutomizer runs on any Linux server with Java 17+. For a continuous verification service that stores results in PostgreSQL:

FROM debian:bookworm-slim

RUN apt-get update && apt-get install -y \
    wget unzip gcc cpp \
    openjdk-17-jre-headless \
    postgresql-client \
    && apt-get clean

# Install UltimateAutomizer
RUN wget -q https://github.com/ultimate-pa/ultimate/releases/download/v0.2.4/UltimateAutomizer-linux.zip \
    && unzip -q UltimateAutomizer-linux.zip -d /opt/ultimate \
    && rm UltimateAutomizer-linux.zip

WORKDIR /opt/ultimate/UltimateAutomizer

COPY verify.sh /usr/local/bin/verify
COPY specs/ /workspace/specs/
RUN chmod +x /usr/local/bin/verify

CMD ["verify"]

#!/bin/bash
# verify.sh — run UltimateAutomizer + store results in sota.io PostgreSQL

for src in /workspace/src/*.c; do
  name=$(basename "$src" .c)
  
  result=$(java -jar plugins/org.eclipse.equinox.launcher_*.jar \
    -data "/tmp/ws-${name}" \
    --spec /workspace/specs/PropertyReachability.prp \
    --file "$src" \
    --architecture 64bit 2>&1)
  
  verdict=$(echo "$result" | grep -oP 'RESULT: (SAFE|UNSAFE|UNKNOWN)' | head -1)
  
  # Store in EU PostgreSQL on sota.io
  psql "$DATABASE_URL" -c "
    INSERT INTO verification_results (program, tool, verdict, timestamp, raw_output)
    VALUES ('${name}', 'UltimateAutomizer-0.2.4', '${verdict}', NOW(), \$\$${result}\$\$)
    ON CONFLICT (program, tool) DO UPDATE SET
      verdict = EXCLUDED.verdict,
      timestamp = EXCLUDED.timestamp,
      raw_output = EXCLUDED.raw_output;"
  
  echo "=== ${name}: ${verdict} ==="
done

# Deploy to sota.io
docker build -t ultimateautomizer-service .
docker push registry.sota.io/your-project/ultimateautomizer-service

curl -X POST https://api.sota.io/v1/projects/YOUR_PROJECT_ID/deploy \
  -H "Authorization: Bearer $SOTA_API_KEY" \
  -H "Content-Type: application/json" \
  -d '{"image": "registry.sota.io/your-project/ultimateautomizer-service"}'

Verification evidence — SAFE certificates, counterexamples, interpolant sequences — stored in EU PostgreSQL on German infrastructure, under EU jurisdiction, fully compliant with GDPR and CRA from day one.

UltimateAutomizer is open source (LGPL 3.0). The Ultimate framework is published at github.com/ultimate-pa/ultimate. sota.io has a free tier — deploy your first UltimateAutomizer verification service in minutes and generate formal evidence that satisfies EU regulatory requirements for safety-critical C code.