Skip to content
FORMAL VERIFICATION

oss-proof

Machine-checked Lean 4 proofs about statement-by-statement translations of open-source C libraries: every covered public function is free of undefined behaviour, memory errors and leaks, and terminates, under the premises each theorem states.

Libraries and status

Each result has one of two states: done (a Lean theorem whose statement is exactly the goal exists and passes every check) or not done.

zlib 1.4 (with 7 patches) · default x86_64 Linux LP64 static build, default allocator

Every documented public function of the default x86_64 Linux build of zlib 1.4 (with seven patches) is proved safe over every call sequence, together with the round trip of the default zlib stream.

Documented public functions
86 / 86
Required goals (done / total)
113 / 113
Confirmed upstream issues
8
7-Zip C SDK 26.00 (unpatched) · portable scalar x86_64 Linux LP64 build

Top-down Lean 4 safety invariants and strict ISO C17 runtime bootstrap for the 7-Zip pure-C SDK (.7z container DAG, BCJ2, PPMd7 arena allocator, LZMA/LZMA2); full C translation safety proofs are not done.

Documented public functions
—
Registered goals (proved / stated)
12 / 16
Confirmed upstream issues
0
libarchive 3.8 (unpatched) · default scalar x86_64 Linux LP64 build (RAR5 & 7-Zip readers)

Top-down Lean 4 safety invariants and strict ISO C17 runtime bootstrap for libarchive's RAR5 and 7-Zip format decoders; statement-by-statement C translation safety proofs are not done.

Documented public functions
—
Registered goals (proved / stated)
13 / 16
Confirmed upstream issues
0

zstd × Lean

not done
Zstandard 1.5.7 (unpatched) · portable scalar x86_64 Linux LP64 decoder build

Strict ISO C17 runtime bootstrap and verification scope for Meta Zstandard's standalone C decoder (libzstd); C translation and public decoder safety proofs are not done.

Documented public functions
—
Registered goals (proved / stated)
5 / 9
Confirmed upstream issues
0
Brotli 1.2 (unpatched) · portable scalar x86_64 Linux LP64 decoder build

Strict ISO C17 runtime bootstrap and verification scope for Google Brotli's C decoder (libbrotlidec); C translation and public decoder safety proofs are not done.

Documented public functions
—
Registered goals (proved / stated)
5 / 9
Confirmed upstream issues
0

How every proof is built

Every library in this collection follows the same translation discipline, strict ISO C17 memory and fault model, and proof structure.

01Translate statement by statement

Pinned C code is translated to Lean without reordering or simplifying. Every ISO C17 undefined behaviour—including null or dangling pointer + 0 and cross-object pointer subtraction—raises Fault.ub; unsigned arithmetic wraps and signed arithmetic is checked.

02Define representation invariants

Each stream, decoder or handle carries an explicit invariant over its owned heap blocks, buffer capacities, lookup tables and cursors.

03Prove each function without assumptions

No callee contract is assumed. Every helper has a theorem about its own translation; every public entry is proved to return without fault, write only its frame, and match its allocation ledger.

04Compose histories and witness premises

Induction over call sequences proves safety and leak-free teardown across arbitrary histories, paired with concrete non-vacuity witnesses.

flowchart LR
    S["Pinned C source and patches"] -->|"statement-by-statement"| T["Lean translation and fault model"]
    T --> I["Init theorem establishes invariant"]
    I --> V["Calls preserve invariant, frame, no leak"]
    V --> G["Lean kernel checks exact goal"]

What a done result rests on

Lean’s kernel checks every proof: each theorem’s type must be syntactically equal to its goal, using only the three standard axioms (propext, Classical.choice, Quot.sound), with no sorry, native_decide, bv_decide, unsafe, partial, opaque, extra axiom or extern binding.

Every proof rests on an explicit trusted base: the Lean kernel and checkers, the runtime model of memory and pointers, the hand translation from C, the pinned upstream source and patches, the target build and external-call model, and the goal statements themselves. Differential tests under AddressSanitizer and UndefinedBehaviorSanitizer compare the translation byte-for-byte against the real C as evidence of fidelity, not proof.

OSS-PROOF

Contents

READING NOWoss-proof