Deploy KLEE to Europe — Cristian Cadar 🇷🇴 (Imperial College London 🇬🇧), the LLVM Symbolic Execution Engine That Found 84 Bugs in GNU Coreutils, on EU Infrastructure in 2026

Coverage-guided fuzzing (AFL++) and static analysis (Infer, Frama-C) each cover a region of the bug-finding landscape. Between them sits a third technique — symbolic execution — that explores program paths exhaustively by treating inputs as symbolic unknowns and delegating path feasibility to an SMT solver. The canonical open-source implementation is KLEE, built on top of LLVM at Stanford and published at OSDI 2008. Its opening result — 84 previously unknown bugs in the GNU Coreutils, tools that had been maintained for decades — remains one of the most striking demonstrations of automated testing in the research literature.

Cristian Cadar 🇷🇴 completed his PhD at Stanford University under Dawson Engler and is now a Professor in the Department of Computing at Imperial College London 🇬🇧. Together with Daniel Dunbar and Dawson Engler, he published "KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs" at the USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2008. The paper won the OSDI Distinguished Paper Award. Cadar has since led KLEE's development from Imperial College, making it one of the few major LLVM-based verification tools with a primary European academic home.

Imperial College London 🇬🇧 is consistently ranked among the world's top five universities for Computer Science. The Department of Computing has produced foundational work in programming language theory, formal verification, and systems security. Cadar's Reliable and Secure Systems Lab at Imperial is the upstream hub for KLEE development, with doctoral students and postdocs across the EU contributing via the GitHub repository.

Symbolic Execution: The Core Principle

Where AFL++ mutates concrete inputs guided by coverage feedback, KLEE treats program inputs as symbolic variables — unknowns that can take any value — and executes the program symbolically, tracking constraints over those unknowns.

The execution state in KLEE is a pair (σ, π):

• σ — the symbolic state: a mapping from program variables to symbolic expressions (e.g., x → α₁ + 3 where α₁ is a symbolic input byte)
• π — the path condition: a conjunction of constraints over symbolic variables accumulated along the current execution path (e.g., α₁ > 0 ∧ α₁ < 128)

When the program reaches a conditional branch if (e), KLEE forks the execution into two states:

• State A: (σ, π ∧ e) — the branch taken
• State B: (σ, π ∧ ¬e) — the branch not taken

Before forking, KLEE queries the STP (Simple Theorem Prover) or Z3 constraint solver to check whether each branch is satisfiable. If π ∧ e is unsatisfiable, the taken branch is infeasible on any input — that state is pruned. If π ∧ ¬e is unsatisfiable, the not-taken branch is pruned. Only feasible states survive.

At the end of a feasible path, KLEE queries the solver to generate a concrete test input — a specific assignment of values to the symbolic input variables that satisfies all constraints accumulated on that path. This test input is guaranteed to exercise that exact path through the program.

# Compile to LLVM bitcode with debug info, no optimisation
clang -emit-llvm -c -g -O0 -fsanitize=address prog.c -o prog.bc

# Run KLEE — explores all paths, generates test cases
klee --libc=uclibc --posix-runtime prog.bc --sym-arg 8

# Generated tests in klee-out-0/
ls klee-out-0/*.ktest | head -5
# replay each test
klee-replay ./prog klee-out-0/test000001.ktest

What KLEE Found in GNU Coreutils

The landmark result in the OSDI 2008 paper was running KLEE on all 89 programs in GNU Coreutils — ls, cat, mkdir, chmod, cp, sort, uniq, and 82 others — using their POSIX command-line argument interfaces as the symbolic input space.

KLEE found 84 bugs across these programs. The bugs included:

• Buffer overflows — paste computing an incorrect buffer size when given many files
• Integer overflows — seq with extremely large step values
• Null pointer dereferences — tr when given malformed character class specifications
• Logic errors — dd ignoring certain combinations of flags

The striking detail: many of these bugs were ten years or older, present across multiple versions of Coreutils. Manual code review and random testing had not found them. KLEE's systematic path enumeration found them automatically in hours.

KLEE also achieved 90%+ branch coverage on most of the Coreutils programs — a level that manual test suites typically do not reach. The generated test suite has since been adopted into the Coreutils regression test suite.

Beyond Coreutils, the KLEE ecosystem has analysed:

• Busybox — 56 bugs found in utility programs
• GNU bash — 17 bugs including memory corruption
• OpenSSH — path exploration of the authentication state machine
• Debian package testing — klee is part of the Debian automated testing infrastructure

Architecture: KLEE's Internals

Compact State Representation

KLEE may maintain thousands of concurrent execution states simultaneously — one per unexplored path prefix. Naively, each state would need its own copy of the entire process heap. KLEE uses copy-on-write (COW) sharing: states that share a common path prefix share their heap representation. Only when a state writes to a memory object does KLEE create a private copy. This reduces memory usage by orders of magnitude for programs with many shared prefixes.

Constraint Independence Optimisation

The path condition π may contain hundreds of constraints over dozens of symbolic variables. When checking sat(π ∧ c) for a new constraint c, only the constraints mentioning variables that appear in c are relevant — the rest are independent and cannot affect satisfiability. KLEE partitions the constraint set into independent subsets and queries the solver only on the relevant partition, dramatically reducing solver invocation cost.

Query Caching and Counterexample Reuse

Equivalent queries arise repeatedly as KLEE explores different paths that share the same constraint structure. KLEE maintains an expression-level cache (not string-based) that identifies semantically equivalent queries. When a new query matches a cached result, the answer is returned instantly without invoking the SMT solver.

Search Heuristics

Exploring all paths depth-first leads to getting stuck in loops. KLEE uses two interleaved search strategies:

• Random Path Selection: maintains a binary tree of execution states, selects states by random walk from root — biased toward shorter paths
• Coverage-New Heuristic: prioritises states that are closest to executing previously uncovered LLVM instructions — biased toward exploring new code

Interleaving these two heuristics balances between exploring new paths quickly and covering new code.

POSIX Modelling

Real programs call the operating system — open(), read(), write(), malloc(), getenv(). KLEE cannot symbolically execute system calls (the kernel is not in scope). Instead, KLEE includes a POSIX runtime library (--posix-runtime) that provides symbolic models of standard library functions:

• klee_make_symbolic(&buf, size, "buf") — marks a memory region symbolic
• --sym-arg N — makes command-line arguments symbolic strings of length ≤ N
• --sym-files N M — models N symbolic files of size ≤ M bytes each
• --sym-stdin M — models stdin as a symbolic stream of length ≤ M bytes

The POSIX model allows KLEE to reason about file-processing programs (Coreutils), network servers (with manual harness), and parsers.

Deploying KLEE on sota.io

Dockerfile

FROM klee/klee:3.0 AS klee-base
# klee/klee includes: KLEE binary, clang, LLVM, STP, uclibc, POSIX runtime

FROM klee-base AS analyzer
WORKDIR /workspace
COPY . .

# Compile to LLVM bitcode
RUN clang -emit-llvm -c -g -O0 \
    -I/usr/local/include \
    src/parser.c -o parser.bc

# Run KLEE with resource limits
CMD ["klee", \
     "--max-time=3600s", \
     "--max-memory=4096", \
     "--output-dir=/results", \
     "--libc=uclibc", \
     "--posix-runtime", \
     "parser.bc", \
     "--sym-arg", "64", \
     "--sym-files", "2", "256"]

sota.io Configuration

# sota.toml
[build]
dockerfile = "Dockerfile"

[resources]
memory = "4096Mi"
cpu = 2

[volumes]
results = "/results"

sota deploy
# Constraint solver runs on EU infrastructure
# Generated tests and crash witnesses in /results
# source code, symbolic traces, and test inputs never leave EU perimeter

CI/CD Integration

# .github/workflows/klee.yml
name: KLEE Symbolic Execution
on: [push, pull_request]

jobs:
  symbolic-test:
    runs-on: ubuntu-latest
    container: klee/klee:3.0
    steps:
      - uses: actions/checkout@v4
      - name: Compile to LLVM bitcode
        run: |
          clang -emit-llvm -c -g -O0 \
            -fsanitize=address,undefined \
            src/parser.c -o parser.bc
      - name: Run KLEE
        run: |
          klee --max-time=300s \
               --libc=uclibc \
               --posix-runtime \
               parser.bc \
               --sym-arg 32 \
               2>&1 | tee klee.log
      - name: Check for errors
        run: |
          # Fail if KLEE found assertion violations or memory errors
          ! grep -q "ASSERTION FAIL\|memory error" klee.log
      - name: Upload test cases
        uses: actions/upload-artifact@v4
        with:
          name: klee-tests
          path: klee-out-*/

KLEE + AddressSanitizer

The most effective deployment combines KLEE with LLVM AddressSanitizer: KLEE explores paths symbolically, ASan detects memory errors that would not crash immediately.

# Compile with ASAN instrumentation
clang -emit-llvm -c -g -O0 \
  -fsanitize=address \
  -fno-omit-frame-pointer \
  target.c -o target.bc

# KLEE will report ASan violations as errors
klee --libc=uclibc --posix-runtime \
     --max-time=1800s \
     target.bc --sym-arg 64
# klee-out-0/test*.ktest = reproducible test cases
# klee-out-0/*.err     = error witnesses with path conditions

KLEE vs AFL++: Complementary Approaches

KLEE and AFL++ are not competitors — they are complementary tools that cover different regions of the bug-finding landscape.

In practice, teams run both: KLEE generates a high-quality seed corpus (concrete test cases from symbolic execution) that is then fed into AFL++ as seeds, combining exhaustive path coverage with the throughput of coverage-guided fuzzing.

EU Provenance and Regulatory Fit

Cristian Cadar at Imperial College London

Cristian Cadar 🇷🇴 obtained his BSc from Politehnica University of Bucharest 🇷🇴 — Romania is a European Union member state. He completed his PhD at Stanford and joined Imperial College London 🇬🇧 as a Lecturer in 2013, where he is now a full Professor. His Reliable and Secure Systems Lab at Imperial drives KLEE's development. Doctoral and postdoctoral researchers from EU member states regularly contribute to KLEE upstream.

Imperial College London, while technically a UK institution post-Brexit, maintains deep EU research ties: Horizon Europe associate membership, ERC grants, and EPSRC-funded collaborations with EU partner universities. The KLEE codebase is developed and maintained primarily from London and collaborating European institutions.

CRA 2027 — Cyber Resilience Act

The CRA requires manufacturers of products with digital elements to systematically identify and document vulnerabilities. KLEE's output directly satisfies this requirement:

• Error witnesses (.err files with path conditions) are machine-readable evidence of specific vulnerability instances
• Test case generation provides reproducible triggers for identified bugs — directly usable in vulnerability reports and CVE documentation
• Path coverage statistics demonstrate systematic testing as mandated by CRA Art. 13

NIS2 — Network and Information Security Directive

NIS2 Art. 21(2)(d) requires "appropriate technical measures to manage the risks posed to the security of network and information systems." For C/C++ systems software, KLEE detects:

• CWE-131 (Incorrect Calculation of Buffer Size) — exactly the class of bug found in paste
• CWE-190 (Integer Overflow or Wraparound) — found in seq and dd
• CWE-476 (NULL Pointer Dereference) — found in tr
• CWE-416 (Use After Free) — detectable via symbolic execution + ASan

EU AI Act — Article 9

EU AI Act Art. 9 requires documented risk management for high-risk AI systems. AI systems implemented in C/C++ (inference engines, ONNX/TFLite runtimes, GPU kernels) benefit directly from KLEE analysis: symbolic execution of the parser and loader paths exhaustively explores the input space that external model files represent, finding parser bugs that could be triggered by adversarially crafted models.

GDPR — Article 25

KLEE analysis keeps all source code, symbolic traces, path conditions, and generated test cases on EU infrastructure. The cryptographic detail: path conditions encode implicit information about program behaviour — sensitive source code structure is encoded in the constraints. Running KLEE on sota.io ensures this information never leaves the EU perimeter, satisfying GDPR Art. 25 data minimisation and privacy by design requirements for software development pipelines handling personal data.

Deploy KLEE on sota.io

sota.io is an EU-native Platform-as-a-Service hosted on German infrastructure — no Cloud Act, GDPR-compliant by default, managed PostgreSQL included.

# Install sota CLI
npm install -g @sota-io/cli

# Login and create project
sota login
sota projects create klee-analysis

# Deploy
sota deploy --project klee-analysis

# Stream logs
sota logs --project klee-analysis --follow

Free tier includes sufficient compute for KLEE analysis of moderate-sized programs. KLEE's symbolic execution is CPU-bound rather than I/O-bound — sota.io's managed container environment provides predictable CPU allocation without cold-start penalties.

Start free →

Blog #185 in the EU Formal Methods Series

This post is part of sota.io's series on EU-originated formal methods, verification, and security tools deployable on European infrastructure. KLEE (Cadar 🇷🇴, Imperial College London 🇬🇧) joins:

• Infer — O'Hearn 🇬🇧 (QMUL → Meta, ACM Turing Award 2023), bi-abduction-based static analysis
• AFL++ — Fioraldi 🇮🇹 (EURECOM → CISPA 🇩🇪) + Maier 🇩🇪, coverage-guided greybox fuzzing
• Frama-C — Baudin 🇫🇷 (CEA LIST 🇫🇷), C code analysis via abstract interpretation + deductive verification
• CompCert — Leroy 🇫🇷 (INRIA → Collège de France), formally verified C compiler in Coq/Rocq

All deployable on sota.io. All EU-provenance. All GDPR-compliant by infrastructure.