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 × Lean
doneEvery 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 × Lean
not doneTop-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 × Lean
not doneTop-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 doneStrict 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 × Lean
not doneStrict 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.
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.
Each stream, decoder or handle carries an explicit invariant over its owned heap blocks, buffer capacities, lookup tables and cursors.
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.
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.