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

Deploy 2LS to Europe — Daniel Kroening 🇩🇪 (University of Oxford), the Two-Level Lattice Solver for Automated Invariant Synthesis, on EU Infrastructure in 2026

Among the persistent challenges in software verification, one stands out as particularly demanding: the automatic synthesis of loop invariants. For most verifiers, loop invariants must be supplied manually — the engineer writes the annotation, the tool checks it. For programs with complex arithmetic over arrays, pointers, and control-flow interactions, finding those invariants by hand is often as hard as the original verification problem.

2LS — the Two-Level Lattice Solver — was designed specifically to address this. Developed by Saurabh Joshi and Daniel Kroening at the University of Oxford and presented at CAV 2014 in Vienna, 2LS combines abstract interpretation over template domains with bounded model checking in a two-level lattice structure: the outer level over-approximates reachable program states (providing safety), while the inner level under-approximates infeasible traces (providing refutation). The combination synthesizes loop invariants automatically — no manual annotation required for the core safety argument.

2LS is the lesser-known sibling of CBMC, also from Kroening's group at Oxford. Where CBMC encodes programs as propositional formulas and uses SAT/SMT to find concrete counterexamples, 2LS works at the abstraction level — inferring invariants rather than finding bugs. The two tools are complementary: CBMC for bounded bug-finding, 2LS for invariant synthesis and unbounded safety.

Daniel Kroening and Saurabh Joshi at Oxford

Daniel Kroening 🇩🇪 is a Full Professor of Computer Science at the University of Oxford 🇬🇧 and one of the most productive software verification researchers in Europe. Born and educated in Germany, Kroening has spent his career building tools that bridge the gap between theoretical verification methods and industrial C/C++ codebases. His 2004 tool CBMC (C Bounded Model Checker, with Edmund Clarke at CMU) became the most widely deployed academic formal verification tool for C — used in production at Amazon AWS, Toyota, NASA JPL, and Airbus.

After CBMC, Kroening's group at Oxford's Department of Computer Science continued developing complementary verification tools: 2LS for invariant synthesis, ESBMC (with the University of Manchester 🇬🇧), and tools for hardware-software co-verification. The Oxford Computer Science department, founded in the 1950s as part of the UK's earliest computing research programmes, has been a central node in the EU formal verification network since the 1970s.

Saurabh Joshi 🇮🇳 was a DPhil (PhD) student at Oxford under Kroening when 2LS was developed. The CAV 2014 paper — 2LS: A Verification Tool Based on 2-Variable Logic — presented at Computer-Aided Verification 2014 in Vienna, Austria 🇦🇹, introduced the two-level lattice framework and its application to loop invariant synthesis for C programs.

The Oxford formal methods group at the time included Kroening, Peter Schrammel 🇩🇪 (Diffblue, now at University of Sussex 🇬🇧), and Michael Tautschnig 🇩🇪 (Amazon Web Services) — a German-dominated team at a British institution, characteristic of the cross-European nature of UK academic computer science before Brexit.

The Two-Level Lattice Framework

The name "2LS" stands for Two-Level Lattice Solver. The mathematical structure is elegant: rather than working in a single abstract domain, 2LS operates in a product domain where two complementary lattices interact.

Level 1: Template Polyhedra (Over-Approximation)

The outer lattice in 2LS is the template polyhedra domain — a parametric abstract domain originally introduced by Sankaranarayanan, Sipma, and Manna (Stanford, 2005) and refined in 2LS for automatic template selection. A template polyhedron is a set of linear constraints of the form:

c1x1 + c2x2 + ... + cnxn ≤ d

where the template directions (c1, ..., cn) are fixed in advance and only the bounds d are inferred. This generalises standard abstract domains:

Interval domain: templates xᵢ ≤ d and -xᵢ ≤ d (upper and lower bounds per variable)
Octagon domain: templates ±xᵢ ± xⱼ ≤ d (difference bounds between variable pairs — Miné 🇫🇷, ENS Paris, 2001)
Zone domain: templates xᵢ - xⱼ ≤ d (one-directional difference bounds)
General template polyhedra: arbitrary linear combinations, capturing octagonal and non-linear loop behaviors

The key insight: instead of computing the abstract transformer for each template direction independently, 2LS solves for the optimal bounds d — the tightest values that make the template a valid over-approximation of the reachable set. This turns invariant synthesis into a constraint optimisation problem over linear arithmetic.

Level 2: Bounded Model Checking (Under-Approximation)

The inner lattice provides the counterexample backbone. 2LS uses CBMC as its BMC engine: for a given loop unrolling bound k, CBMC encodes the program as a formula and either:

Finds a counterexample (a concrete execution violating the property) — refuting the current candidate invariant
Returns UNSAT — confirming that no violation exists within bound k

The UNSAT result feeds back to Level 1: the template bound inference is constrained to exclude the infeasible bounded traces found by CBMC. This produces tighter invariants than abstract interpretation alone.

k-Induction

The two levels interact via k-induction, the verification strategy that:

Base case: prove the property holds for all executions of length ≤ k (via BMC)
Inductive step: assume the property holds for k consecutive steps, prove it holds for step k+1 (via invariant strengthening)

In 2LS, the inductive step is discharged by the template polyhedra solver: find bounds that make the template invariant inductive — i.e., that a state satisfying the invariant after one loop iteration still satisfies the invariant. If the template invariant is inductive and the base case holds, the property holds for all loop iterations, not just the first k.

The power of 2LS: k-induction succeeds where BMC alone cannot — it proves properties for all loop executions, not just executions up to a fixed unrolling depth. And the template polyhedra solver makes invariant synthesis automatic — the user provides the property, not the invariant.

# 2LS basic usage: verify a C program with k-induction
./2ls --k-induction program.c

# Specify loop unrolling bound
./2ls --k-induction --unwind 10 program.c

# Template domain selection
./2ls --k-induction --intervals program.c    # interval domain
./2ls --k-induction --octagons program.c     # octagon domain
./2ls --k-induction --template program.c     # template polyhedra (default)

# Termination analysis
./2ls --termination program.c

# Memory safety
./2ls --memory-safety program.c

The 2-Variable Logic Connection

The "2-variable" in 2LS's original CAV 2014 presentation refers to the logic underlying the template instantiation: the constraint synthesis problem for template polyhedra reduces to satisfiability in two-variable logic over ordered structures (a fragment of first-order logic decidable in polynomial space). This provides a theoretical foundation for the termination and soundness of the template bound computation.

In practice, the SMT solver Z3 (Microsoft Research, widely used in EU verification tools) discharges the constraint synthesis queries. Z3's linear arithmetic solver handles the polyhedra bound computation efficiently for the variable counts typical in embedded C code.

SV-COMP and Verification Performance

2LS has participated in SV-COMP (Software Verification Competition, held at ETAPS/TACAS) in the ReachSafety and MemSafety categories. Its performance profile reflects its design: 2LS is particularly strong on programs with numeric-heavy loop bodies where template polyhedra can capture the exact invariant, and where k-induction closes the proof that BMC leaves open.

The SV-COMP context highlights where 2LS sits in the EU verification ecosystem:

Tool	Institution	Approach	Strength
CPAchecker	LMU Munich 🇩🇪	Predicate abstraction + CEGAR	Broad, SV-COMP champion
UltimateAutomizer	Freiburg 🇩🇪	Trace abstraction + Büchi	SV-COMP top tier
CBMC	Oxford 🇬🇧	Bounded model checking	Bug-finding, CI/CD
2LS	Oxford 🇬🇧	Template polyhedra + k-induction	Invariant synthesis
nuXmv	FBK Trento 🇮🇹	IC3/PDR + BDD	Hardware-style safety

2LS occupies a complementary niche: where CBMC finds concrete bugs and CPAchecker/UltimateAutomizer prove safety via predicate/trace abstraction, 2LS synthesises the numeric invariants that make those proofs possible. For programs with polynomial-bounded loop variables — typical in signal processing, control theory, and automotive embedded code — 2LS's template approach often produces tighter invariants with less manual effort.

How to Run 2LS

2LS is built on the CPROVER infrastructure (also used by CBMC) and requires a similar setup:

# Clone and build from source
git clone https://github.com/diffblue/2ls.git
cd 2ls
git submodule update --init
cmake -S . -Bbuild -DCMAKE_BUILD_TYPE=Release
cmake --build build -- -j$(nproc)

# Basic safety verification with k-induction
./build/src/2ls/2ls --k-induction program.c

# Memory safety check
./build/src/2ls/2ls --memory-safety --k-induction program.c

# Termination
./build/src/2ls/2ls --termination program.c

# Template polyhedra with explicit domain
./build/src/2ls/2ls --k-induction --template-polyhedra program.c

# Nested loops: increase unrolling depth
./build/src/2ls/2ls --k-induction --unwind 20 nested_loop.c

A minimal C program demonstrating 2LS invariant synthesis:

/* loop_bounds.c — 2LS synthesizes the loop invariant 0 <= i <= n automatically */
#include <assert.h>

int main() {
  int n;
  __CPROVER_assume(n >= 0 && n <= 100);
  
  int i = 0;
  int sum = 0;
  
  while (i < n) {
    sum += i;
    i++;
  }
  
  /* 2LS synthesizes: 0 <= i <= n and sum == i*(i-1)/2 */
  assert(i == n);
  assert(sum >= 0);
  return 0;
}

# 2LS automatically finds the loop invariant and proves both assertions
./build/src/2ls/2ls --k-induction loop_bounds.c
# VERIFICATION SUCCESSFUL

Docker Deployment for CI/CD

A production Dockerfile for a 2LS verification service:

FROM debian:bookworm-slim AS builder

RUN apt-get update && apt-get install -y \
    git cmake ninja-build \
    g++ flex bison \
    libz-dev libgmp-dev \
    && apt-get clean

# Build 2LS from source
RUN git clone --depth=1 https://github.com/diffblue/2ls.git /opt/2ls-src \
    && cd /opt/2ls-src \
    && git submodule update --init --depth=1 \
    && cmake -S . -Bbuild -GNinja -DCMAKE_BUILD_TYPE=Release \
    && cmake --build build

FROM debian:bookworm-slim

RUN apt-get update && apt-get install -y libgmp10 && apt-get clean

COPY --from=builder /opt/2ls-src/build/src/2ls/2ls /usr/local/bin/2ls

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

CMD ["verify"]

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

for src in /workspace/src/*.c; do
  name=$(basename "$src" .c)
  
  result=$(2ls \
    --k-induction \
    --memory-safety \
    --unwind 20 \
    "$src" 2>&1)
  
  if echo "$result" | grep -q "VERIFICATION SUCCESSFUL"; then
    verdict="SAFE"
  elif echo "$result" | grep -q "VERIFICATION FAILED"; then
    verdict="UNSAFE"
  else
    verdict="UNKNOWN"
  fi
  
  # Store in EU PostgreSQL on sota.io
  psql "$DATABASE_URL" -c "
    INSERT INTO verification_results (program, tool, verdict, timestamp, raw_output)
    VALUES ('${name}', '2ls-k-induction', '${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 2ls-verification-service .
docker push registry.sota.io/your-project/2ls-verification-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/2ls-verification-service"}'

Verification results — synthesised invariants, SAFE certificates, counterexamples — stored in EU PostgreSQL on German infrastructure, under EU jurisdiction, fully GDPR-compliant.

Industrial Relevance: EU Safety-Critical Systems

Automotive: ISO 26262 ASIL D

2LS's template polyhedra domain is particularly well-suited for automotive control software: PID controllers, braking algorithms, powertrain state machines all have numeric loop bodies with bounded arithmetic. The interval and octagon domains capture these precisely.

For automotive teams at Bosch 🇩🇪, Continental 🇩🇪, Infineon 🇩🇪, and STMicroelectronics 🇮🇹 working under ISO 26262 ASIL D, 2LS provides:

Automatic invariant synthesis for control loops: no manual @invariant annotations in safety cases
Arithmetic overflow proofs: template polyhedra over bounded integer ranges prove absence of wrap-around in safety-critical counters and accumulators
Range analysis: tight bounds on sensor readings, actuator outputs, and accumulated error terms — directly useful as ISO 26262 Component Safety Requirements

The connection to CBMC is industrially significant: many teams that use CBMC for bug-finding in CI/CD can add 2LS for the invariant synthesis step, using the same CPROVER infrastructure and harness patterns. One toolchain, two complementary verification modes.

IEC 61508 SIL 3/4

For German process industry manufacturers — Endress+Hauser 🇩🇪, Pepperl+Fuchs 🇩🇪, Wago 🇩🇪 — IEC 61508 SIL 3/4 certification requires formal verification evidence for C safety functions in field devices and safety controllers.

2LS's k-induction approach satisfies IEC 61508 Part 3's "formal proof" technique (T3.7) when:

The template domain is sufficient to express the safety property (typically yes for bounded numeric code)
The loop unrolling bound is shown sufficient (via --unwinding-assertions — same flag as in CBMC)
The verification pipeline is documented and reproducible

The CPROVER infrastructure (shared with CBMC) provides mature tool qualification documentation via Diffblue's (Oxford spinout) toolchain certification support.

EN 50128 SIL 4: Railway Signalling

For ETCS onboard units and interlocking controllers developed by Siemens Mobility 🇩🇪 and Thales Rail 🇫🇷, 2LS's termination analysis complements CBMC's safety analysis. EN 50128 SIL 4 requires evidence that:

Safety functions are reachable (reachability — CBMC)
Safety functions terminate (termination — 2LS --termination)
Loop variables stay within safe bounds (invariant — 2LS --k-induction)

The three modes together provide a formal evidence package across the safety hierarchy: bounded reachability, unbounded termination, and numeric range proofs.

EU Regulatory Context

EU Cyber Resilience Act (CRA) 2027

The CRA requires manufacturers of products with digital elements to demonstrate "state of the art" security measures. For embedded C products, 2LS provides:

Absence of integer overflow (CWE-190): template polyhedra over bounded integer types prove wrap-around impossible
Absence of array out-of-bounds (CWE-125/787): index invariant synthesis proves array accesses remain within bounds
Absence of null pointer dereference (CWE-476): pointer analysis combined with range invariants

These certificates, produced by a reproducible pipeline (2LS version + property spec + harness), qualify as formal verification evidence in a CRA technical documentation package.

EU AI Act Article 9: Risk Management Systems

For high-risk AI systems with C inference engines — ADAS (Annex III §3), medical devices (Annex III §5), industrial control (Annex III §6) — 2LS provides:

Inference loop termination proofs: --termination mode proves the inference computation terminates for all valid inputs — no infinite loops in safety-critical AI decisions
Output range invariants: template polyhedra prove output activations stay within physically meaningful bounds (no unbounded growth in neural network layers)
Index safety for tensor operations: invariant synthesis over loop counters in matrix multiply operations

The synthesised invariants are human-readable (linear constraints), which simplifies the EU AI Act conformity assessment review: auditors can inspect the invariants without understanding the full verification algorithm.

2LS's data-flow analysis modes can verify that personal data processing loops remain within their specified scope: a template invariant processed_count ≤ dataset_size proves that a loop cannot silently extend beyond the consented data range — a direct GDPR Art. 25 "data minimisation by design" argument.

The Oxford-Diffblue Formal Verification Ecosystem

Daniel Kroening's Oxford group spawned the company Diffblue 🇬🇧 (Oxford spinout, founded 2016), which commercialises CPROVER-based technology for:

Diffblue Cover: automated Java unit test generation (used at Goldman Sachs, Deutsche Bank 🇩🇪, Morgan Stanley)
CBMC commercial support: enterprise tool qualification documentation
2LS commercial development: continued invariant synthesis research

The Oxford formal verification cluster built around Kroening's group:

CBMC (2004) — C Bounded Model Checker, CAV/TACAS, now at Amazon AWS
2LS (2014) — Two-Level Lattice Solver, CAV 2014 Vienna 🇦🇹
JBMC (2018) — Java Bytecode Model Checker (Peter Schrammel 🇩🇪, Oxford/Sussex)
ESBMC (University of Manchester 🇬🇧 fork) — extended for C++ and floating-point
Diffblue Cover (2016, Oxford spinout) — commercial Java test generation

This cluster represents one of the densest formal verification research outputs from a single institution in Europe. The common CPROVER infrastructure means advances in one tool directly benefit the others — a genuine research ecosystem, not isolated tools.

Deploying 2LS on sota.io

2LS runs on any Linux server with a standard C/C++ toolchain. For a continuous invariant-synthesis service that stores results in PostgreSQL:

FROM debian:bookworm-slim AS builder

RUN apt-get update && apt-get install -y \
    git cmake g++ flex bison libz-dev libgmp-dev ninja-build \
    && apt-get clean

RUN git clone --depth=1 https://github.com/diffblue/2ls.git /2ls \
    && cd /2ls \
    && git submodule update --init --depth=1 \
    && cmake -S . -Bbuild -GNinja -DCMAKE_BUILD_TYPE=Release \
    && cmake --build build

FROM debian:bookworm-slim

RUN apt-get update && apt-get install -y libgmp10 postgresql-client && apt-get clean
COPY --from=builder /2ls/build/src/2ls/2ls /usr/local/bin/2ls

COPY run_verification.sh /usr/local/bin/run_verification
RUN chmod +x /usr/local/bin/run_verification

CMD ["run_verification"]

#!/bin/bash
# run_verification.sh — 2LS invariant synthesis + sota.io PostgreSQL storage

for src in /workspace/src/*.c; do
  name=$(basename "$src" .c)
  
  # Run 2LS with template polyhedra + k-induction
  result=$(2ls \
    --k-induction \
    --template-polyhedra \
    --memory-safety \
    --unwind 20 \
    "$src" 2>&1)
  
  verdict=$(echo "$result" | grep -oP 'VERIFICATION (SUCCESSFUL|FAILED)' | head -1 | awk '{print $2}')
  
  # Extract synthesised invariants (2LS outputs them in the result)
  invariants=$(echo "$result" | grep -A5 'Invariant' | head -20)
  
  # Store in EU PostgreSQL on sota.io — no US jurisdiction
  psql "$DATABASE_URL" -c "
    INSERT INTO formal_verification (
      component, verifier, verdict, invariants, timestamp
    ) VALUES (
      '${name}', '2ls-template-polyhedra', '${verdict}',
      \$inv\$${invariants}\$inv\$, NOW()
    ) ON CONFLICT (component, verifier) DO UPDATE SET
      verdict = EXCLUDED.verdict,
      invariants = EXCLUDED.invariants,
      timestamp = EXCLUDED.timestamp;"
  
  echo "=== ${name}: ${verdict} ==="
done

Verification results and synthesised invariants stored in EU-jurisdiction PostgreSQL — directly useful for ISO 26262, IEC 61508, and CRA technical documentation packages.

2LS is open source (BSD licence). Source code at github.com/diffblue/2ls. sota.io has a free tier — deploy your first 2LS invariant-synthesis service in minutes and generate formal evidence that satisfies EU regulatory requirements for safety-critical C code.