Safety of compress*
compress, compress_z, compress2 and compress2_z are safe on every input that meets the
premises below: the call returns, has no undefined behaviour, writes only the destination
buffer, and frees everything it allocated. This page gives the statement, its premises and
the shape of the proof.
Source: compress.c. Buffer utilities reads the C. Terms:
glossary.
What is proved
| Goal | Theorem |
|---|---|
Goal.compress2_z_safety |
compress2_z_safety |
Goal.compress2_safety |
compress2_safety |
Goal.compress_z_safety |
compress_z_safety |
Goal.compress_safety |
compress_safety |
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.
Each goal is an instance of CompressorSafety. For every input that meets the premises below:
- the call runs without undefined behaviour and returns;
- a rejected argument returns
Z_STREAM_ERRORand changes nothing; - otherwise the call writes at most the capacity into the output buffer and nothing else;
- every allocation is freed on every path;
Z_MEM_ERRORcomes only after an allocation failed.
Nothing is said about the bytes written. That is the functional contract
CompressorContract, 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. |
CompressArguments |
The arguments are rejected by the C's own checks, or the source is readable, the destination is writable for its capacity, and the two do not overlap. |
| The length cell | compress and compress2 take a non-null destLen. The _z forms admit NULL and refuse it. In the translation the cell is a value passed in and a value returned, not memory. So a cell that overlaps the source or the destination cannot be expressed, and such a call is outside the theorems. |
The separation of source and destination, and the limit on the length cell, have a row in deviations, "Whole-buffer compression".
Structure
flowchart TD
args["argument checks: refusal before any object is made"] --> init
init["init_cases: deflateInit_ fails (free the stream) or succeeds"] --> loop
loop["loop_run: do ... while (err == Z_OK), one deflate call per iteration"] --> epi
epi["epilogue: output length, deflateEnd, free the stream"] --> z["compress2_z_safety_gen"]
z --> w["compress_z, compress2, compress"]
compress2_z drives a local z_stream through deflateInit_, a loop of deflate calls and
deflateEnd. Before each deflate call the loop refills avail_in and avail_out, which are
32-bit, from the 64-bit remaining lengths. This page calls that refill a rebuffer of the
stream.
CState is the state between iterations: the stream invariant, reachability, the counts of
consumed input and produced output, and the fact that the heap is the caller's heap with the
output so far written into the destination.
The proof is generic in the histories of the stream it drives (CompressReach).
compress2_z_safety_gen takes two facts about those histories:
- the full contract of one
deflatecall,Goal.deflate, restricted to them; DeflateLoopFacts, four facts about onedeflatecall thatGoal.deflatedoes not state:- a
Z_NO_FLUSHcall that is not refused, has input and room, and returnsZ_OKmakes progress; - new input after the first
Z_FINISHgivesZ_BUF_ERRORor writes at least one byte; - every call keeps the gzip header pointer;
- every call keeps the owned blocks.
compress2_z initialises its stream with memLevel 8. So the four theorems
instantiate the generic proof with DeflateReachMid: the histories that start with
deflateInit2_ at memLevel ≥ 3 and then only rebuffer the stream and call deflate. Along
them lit_bufsize ≥ 512, and both facts hold with no hypothesis (goalDeflate_mid,
loopFacts_mid). Histories with memLevel 1 or 2 need a further bound on the compressor's
shared pending and symbol buffer, described in trees. The
theorems here do not use it.
deflateInit_ and deflateEnd are used through their own theorems (deflateInit_proof,
deflateEnd_safe, deflate_end_public).
Termination
The measure is avail_in + sourceLen + avail_out + left. Here sourceLen and left are the C
locals: the source bytes and the destination room not yet given to the stream. The measure
starts below the loop fuel, 2^64. The refills keep it. A call that returns Z_OK is not
refused and has room; otherwise Goal.deflate gives Z_BUF_ERROR. With Z_NO_FLUSH the
call has input, because source remains after the refill, so DeflateLoopFacts gives progress. With Z_FINISH, the progress
clause of Goal.deflate gives progress, unless the stream is finished and has new input; in
that case DeflateLoopFacts gives Z_BUF_ERROR or a written byte. Progress lowers the
measure.
The bound functions
compressBound and compressBound_z read no memory. Their goals Goal.compressBound and
Goal.compressBound_z give the exact value of the bound formula, and these same goals are
their safety goals. The theorems are compressBound and compressBound_z.
Not covered: that every output of the translated compressor fits the bound. That is a
functional statement, which the safety results do not need; see
buffer utilities. For compress and compress_z, when every allocation succeeds,
Goal.compress_completes and Goal.compress_z_completes state it
(the round trip). For the other levels, the theorem compress_bound_adequate
states it, and
deflate_bound_adequate states the same for the bound of deflateBound, for the heap-free
API model only. No theorem says that the translated compress2 or
deflate follows that model.