Safety of uncompress*
uncompress, uncompress_z, uncompress2 and uncompress2_z are safe on every input that
meets the premises below, whatever the source bytes are: the call returns, has no undefined
behaviour, writes only the destination buffer and the length cells, and frees everything it
allocated. This page gives the statement, its premises and the shape of the proof.
Source: uncompr.c. Buffer utilities reads the C. Terms:
glossary.
What is proved
| Goal | Theorem |
|---|---|
Goal.uncompress2_z_safe |
uncompress2_z_safe |
Goal.uncompress2_safe |
uncompress2_safe |
Goal.uncompress_z_safe |
uncompress_z_safe |
Goal.uncompress_safe |
uncompress_safe |
All four are safety results, are required, and are done. Each theorem proves its goal exactly as stated, with no hypothesis added; the premises below are part of the goal statements.
The goals are instances of UncompressCountedSafe and UncompressSingleSafe. For every input
that meets the premises below:
- the call runs without undefined behaviour and returns. In Lean: running the translated
function on the heap gives
.okwith a return code and a new heap, not a fault; - an argument error returns
Z_STREAM_ERRORand changes nothing; - otherwise the call writes at most
capacitybytes into the output buffer, writes the length cells, and writes nothing else. The destination-length cell then holds the number of bytes written. The goal admits one exception:Z_MEM_ERRORwith nothing written and both cells holding the values they had. That is the return after a failedinflateInit, where the C does not store through the cells; - every allocation is freed on every return path;
- the code is
Z_OK,Z_BUF_ERROR,Z_DATA_ERRORorZ_MEM_ERROR, andZ_MEM_ERRORcomes only after an allocation failed.
Nothing is said about the bytes written. That is the functional goal Goal.uncompress*,
which is not required for the safety results.
What is assumed
| Premise | Meaning |
|---|---|
Fresh, Uniq, LibraryGlobals |
The caller heap is well formed and the static tables are the initial ones. |
ByteObjectsFit |
Every byte object has fewer than 2^63 bytes. |
Length cells (LengthCell) |
Each non-NULL length pointer names eight readable and writable bytes. They hold the length in little-endian order: the capacity in *destLen, the source length in *sourceLen. uncompress and uncompress2 take non-NULL cells; the _z forms admit NULL and refuse it. uncompress and uncompress_z pass the source length as a value and have no source-length cell. |
| Readable source, writable destination | A non-NULL source is readable for the source length. A non-NULL dest is writable for the capacity. |
Separation, uncompress2 and uncompress2_z (UtilitySeparation) |
Source, destination, the destination-length cell and the source-length cell are pairwise separate: six conditions. |
Separation, uncompress and uncompress_z |
Three Separate premises of UncompressSingleSafe: source and destination; the destination-length cell and the destination; the destination-length cell and the source. |
Two ranges are separate (Separate) when one of them is empty,
or one of the two pointers is NULL, or they lie in different blocks, or their byte ranges in
one block do not overlap.
The separation has a row in deviations, "Counted decompression".
Structure
flowchart TD
init["start_state: inflateInit2_ on the local stream"] --> loop
loop["loop_run_safe: do ... while (err == Z_OK)"] --> call
call["call_phase_safe: one inflate call (inflate_public)"] --> loop
loop --> epi["epilogue: store the counts, inflateEnd, free the stream and the dummy output block"]
epi --> z["uncompress2_z_with_safe"]
z --> w2["counted2_of_z: uncompress2"]
z --> w1["single_of_counted: uncompress_z, uncompress"]
The proof is written once, for any relation on the result (CountedWith, SingleWith). The
safety goals instantiate it with SafeRel: the output fits the capacity, the consumed input
fits the source, and the return code is one of the documented ones. SafeState and SafeFinal
are the loop state and the final state of that proof; they hold everything but the format
fact. The functional proof, which is not required for the safety results, extends them with
NoOver: no complete stream at the start of the source has been read to its end.
What the proof uses
inflate_public, the full contract of oneinflatecall (Goal.inflate), for each call.Goal.inflateis a functional contract. The safety proof uses its progress, frame and ownership clauses.reach_invariant, for the decoder of every reachable stream.
No format fact of inflate is used.
Termination
The measure is the unread source plus the unfilled room:
avail_in + len + avail_out + left, where len and left are the C locals: the source bytes
and the destination room not yet given to the stream. The refills move bytes between the stream fields and the
remaining lengths, so they keep it. Each call that returns Z_OK consumes input or writes
output. This is the progress clause of Goal.inflate,
rc = Z_OK → (used ≠ 0 ∨ out ≠ []) ∧ flush ≠ Z_FINISH; the proof uses its first part. So the
measure falls. At the start it is at most sourceLen + destLen, which is below 2^64, the loop
fuel.
The rule is cdoWhile_decreasing.