Skip to content
FORMAL VERIFICATION

zlib × Lean

Machine-checked Lean 4 proofs about a statement-by-statement translation of zlib: every documented public function of the default x86_64 Linux build is safe, with no undefined behaviour, no memory error, no leak, and termination, under the premises each theorem states.

Results

The first three are the safety results; the fourth is a functional result. Each one is done or not done.

  1. 1done

    inflate is safe on every input: no undefined behaviour, no memory error, no leak, and it terminates, for every sequence of calls on a stream and every split of the buffers.

  2. 2done

    deflate is safe on every input, for every sequence of calls on a stream.

  3. 3done

    Every other documented public function is safe: compress* and uncompress*, the other stream functions, the checksums, the gzip file interface and the callback decoder inflateBack.

  4. 4done

    The round trip of the default zlib stream: uncompress(compress(x)) = x, and compressing with deflateInit at the default level and deflate calls with any flush value, finished by deflate(Z_FINISH) calls, and then decompressing with inflateInit gives back the input, for every split of the buffers.

Done: a Lean theorem whose statement is exactly the goal exists and passes every check of the project. Not done: there is no such theorem.

That the translation and the runtime model match the C is reviewed and tested, not proved: see the trusted base. The conditions a call must meet are in the deviations. What a done result rests on is in its own page.

The state of every function, and what is not planned →

Read zlib first

  1. A complete codec: LZ77 and Huffman

    A complete small codec: repeated passages, Huffman codes, how the rules are transmitted, and how decoding ends. It starts from ABABABAB and rebuilds the core of DEFLATE.

  2. Implementing and optimizing zlib

    How zlib actually implements and tunes deflate and inflate: window, hash chains, match search, table lookup and copying. The deepest article.

  3. Extending zlib: streams and integrity

    Streaming, dictionaries, wrappers, Adler-32, CRC-32 and the application interface: why complete buffers are not enough.

Reference

ZLIB × LEAN

Contents

READING NOWzlib × Lean