Deviations: what a call must satisfy
This page is for someone who calls zlib and asks: is my call covered by a safety theorem? The checklist below answers by function family, in C terms. The tables after it give the Lean premise behind each line, the goals that state it, and the reason for it.
A call that satisfies the lines for its function is covered. A call outside them is not covered: it is neither proved safe nor claimed to be unsafe.
The page lists every premise of a safety goal that is narrower than zlib.h, or that a reader
could miss. A premise that only repeats zlib.h is in the Lean statement of the goal;
coverage names the goal of each function. Conditions on the model that a caller
cannot act on are in model limits. What is trusted and not proved is in the
trusted base.
Checklist for a caller
Each line ends with the Lean predicate that states it; a line that no predicate states says so.
NULL is allowed wherever a line says so, and only there.
Every call
- The library is the default x86_64 Linux build: LP64, static, compiled from zlib 1.4 (upstream
commit
99623ef7) with the seven patches. zallocandzfreeof everyz_streamareZ_NULL, so zlib uses its default allocator (DefaultOrNull). A custom allocator is not covered. A failingmallocis covered.- No single object in memory has 2^63 bytes or more (
ByteObjectsFit). This is the LP64 limitPTRDIFF_MAXon one object; it does not limit total memory or the length of a stream. - The lines hold for the whole history. A call on a stream or a file is covered when every earlier
call on it, from its init or open on, also satisfied its lines, whatever those calls returned
(
StreamReachable,GzHistory,BackSafeReachable).
inflateInit, inflateInit2, deflateInit, deflateInit2 (the zlib.h macros and the
functions behind them)
strmisNULLor points to az_streamwhosezallocandzfreeareZ_NULL(InitArguments).- Nothing else is asked. The other fields of the
z_stream,stateincluded, may hold any value.version, which the macros pass for you, isNULLor a readable string, andstream_sizeis any value: on a mismatch the call returns an error code and leaves no allocation behind. Everylevel,windowBits,memLevelandstrategyis covered.
This answers the most common call:
z_stream s;
s.zalloc = Z_NULL;
s.zfree = Z_NULL;
s.opaque = Z_NULL;
int rc = inflateInit(&s); /* covered by Goal.inflateInit__safety */
The call is covered, and the struct does not have to be zeroed first. When it returns Z_OK,
the theorem also says that the stream is reachable, so every later call on s is covered by the
goals below. Note 1 says what the model does with the fields
the code leaves unset.
When the call fails, every later call on s is refused with an error value, and so is covered,
in two cases: the call returned Z_VERSION_ERROR, or you had set s.state = Z_NULL before the
call. Otherwise it depends on the failure: note 2 says what each
failure leaves in the record.
inflate, deflate, deflateParams
next_inisNULLor points toavail_inreadable bytes.next_outisNULLor points toavail_outwritable bytes (StreamBuffers).- The input range and the output range do not overlap, and neither lies in memory that zlib
allocated for the stream (
StreamBuffers). - Between two calls you change only
next_in,avail_in,next_outandavail_outof thez_stream, and memory that zlib did not allocate for the stream (Rebuffer). - If a
gz_headeris attached, the lines under "gzip header" hold (ActiveHeader).
inflateSync
next_inisNULLwithavail_in == 0, or points toavail_inreadable bytes outside the stream's own memory (StreamArguments).
Dictionaries: inflateSetDictionary, deflateSetDictionary, inflateGetDictionary,
deflateGetDictionary
- The dictionary pointer is
NULL, or a buffer outside the stream's own memory: readable fordictLengthbytes for the twoSetcalls, writable for the bytes returned for the twoGetcalls (CallerRange).zlib.hsays that 32768 bytes are always enough for aGetcall. - For the two
Getcalls,dictLengthisNULLor points to auIntvariable of your own that overlaps neither the dictionary buffer, thez_streamnor the stream's own memory. No Lean predicate states this line: the translation returns the length as a value (row "Result cells").
gzip header, reading: inflateGetHeader, then inflate
- At
inflateGetHeader:headis notNULL. Itsextra,nameandcommentare eachNULLor writable forextra_max,name_maxandcomm_maxbytes. The record and these buffers are outside the stream's own memory (HeaderMemory). - The record stays attached to the stream until a successful
inflateResetorinflateReset2, aninflateSyncthat finds a sync point (it resets the stream), aninflateGetHeadercall that replaces it, orinflateEnd. While it is attached, the record and its buffers stay valid in the same way at everyinflatecall, also after the header is complete (HeaderMemoryinActiveHeader). - While
inflateis still reading the header, theextrabuffer does not overlap the unread input, and in modeEXTRAthe record'sextra_lenis not below the length the stream still has to read (InflateHeaderProgress). This is a condition on the record at eachinflatecall, whoever wrote the field.inflateon a stream writesextra_lenin the record attached to it. - A copy made by
inflateCopyis attached to the same record. These lines hold at everyinflatecall on the copy too, until the copy is detached in one of the same ways. Two streams attached to one header record are outside the goals: the goals describe one stream.
gzip header, writing: deflateSetHeader, deflatePrime, then deflate, deflateParams,
deflateBound, deflateBound_z
deflateSetHeaderanddeflatePrimeare called before the firstdeflatecall after init or reset, aszlib.hsays (DeflateNotStarted).- At
deflateSetHeader:headisNULL, or a record outside the stream's own memory. ItsextraisNULLor readable forextra_lenbytes outside the stream's own memory. Itsnameandcommentare eachNULLor a NUL-terminated string (HeaderMemory). - The record stays attached to the stream until
deflateReset, adeflateSetHeadercall that replaces it, ordeflateEnd. - From
deflateSetHeaderuntildeflatehas written the header out, at everydeflate,deflateParams,deflateBoundanddeflateBound_zcall: - the record and its buffers are still valid as in the line for
deflateSetHeader(HeaderMemoryinActiveHeader); - the input range and the output range of the
z_stream, the extra field, the name and the comment do not overlap one another, and the three header buffers are outside the stream's own memory (DeflateHeaderApart); - when a
deflatecall has returned in the middle of the extra field, the name or the comment, you do not shorten that field or set it toNULL(DeflateHeaderProgress). - After the header is written out,
deflateanddeflateParamsask nothing of the record. zlib does not report that moment. deflateBoundanddeflateBound_zread an attached record whenever they are called, also after the header is written out. At every such call the record and its buffers are valid as in the line fordeflateSetHeader(DeflateHeaderLive).- A copy made by
deflateCopyis attached to the same record. These lines hold for the calls on the copy too.
inflateCopy, deflateCopy
sourceis a stream as in the next item, anddestpoints to az_streamthat is notsource(source ≠ dest).- The copy points to the same
gz_headerrecord assource. The lines under "gzip header" then hold for the calls on both streams.
The other stream calls (inflateEnd, deflateEnd, inflateReset, inflateReset2,
inflatePrime, inflateMark, deflateReset, deflateTune, deflatePending, deflateUsed)
- No premise on the arguments. The stream is one that an init or a copy returned
Z_OKfor and that was used as this checklist says. - You do not call
deflateResetKeepdirectly on a deflate stream.zlib.hlists it among the undocumented functions, and a history that contains a direct call is outside the deflate goals.deflateReset, which calls it and then clears the hash tables, is covered (StreamOperation). deflatePendinganddeflateUsed: each result pointer (pending,bits) isNULLor points to a variable of your own that overlaps neither thez_streamnor the stream's own memory. No Lean predicate states this line: the translation returns the results as values (row "Result cells").
A NULL or inconsistent stream
- These are refused: a stream pointer that is
NULL; az_streamwhosestateisZ_NULL, as afterEnd; and a struct copy of az_streamthat is still live. The refusal is a clause of the safety goal of every documented stream function except the four init functions. - A refused call returns an error value and leaves memory as it was, except that
inflateCopyanddeflateCopyfrom a refused source setdest->statetoZ_NULL. Note 2 gives the values and the exact statements. - Not covered: a
z_streamwith a set allocator whosestateholds a stale or garbage pointer. This includes a struct copy used after the original was ended.
compress, compress2, compress_z, compress2_z
sourceis readable forsourceLenbytes,destis writable for*destLenbytes, and the two do not overlap (CompressArguments). ANULLsourcewithsourceLen == 0and aNULLdestwith*destLen == 0are allowed.- The calls that the C refuses with
Z_STREAM_ERRORare covered whatever the other arguments are: aNULLsourcewith a nonzerosourceLen, aNULLdestwith a nonzero*destLen, and aNULLdestLenfor the_zforms (compressRejected). compressandcompress2take a non-NULLdestLen(CompressorSafety).destLenpoints to a variable of your own that does not overlapsourceordest. No Lean predicate states this line: the translation takes*destLenas a value (row "Whole-buffer compression").
uncompress, uncompress2, uncompress_z, uncompress2_z
sourceisNULLor readable for the source length, anddestisNULLor writable for*destLenbytes.destLen, andsourceLenof the2forms, are eachNULLor point to eight readable and writable bytes (LengthCell).source,destand the length variables do not overlap one another (UtilitySeparation).uncompressanduncompress2take non-NULLlength pointers.
Checksums and queries
adler32,adler32_z:bufisNULLonly withlen == 0; otherwise it is readable forlenbytes (AdlerBufferBytes).crc32,crc32_z:bufisNULL, or readable forlenbytes.crc32_combine_op:opis a value thatcrc32_combine_genorcrc32_combine_gen64returned, aszlib.hsays.- The combine functions,
compressBound,compressBound_z,zlibVersionandzlibCompileFlagshave no premise.
Callback decoder: inflateBackInit, inflateBack, inflateBackEnd
- At
inflateBackInit:zallocandzfreeareZ_NULL;windowBitsis 8 to 15;windowis notNULL, is writable for2^windowBitsbytes, and is a byte array or part of one, not a byte field inside a structure (BackInitArguments,BackSafeReachable.init). Thestatefield of thez_streammay hold any value. - At each
inflateBackcall,strm->next_inisNULL, or points toavail_inreadable bytes that do not overlap the window and that are a byte array or part of one (BackFirstChunk). - Your
inandoutfunctions return, write only memory of your own, and do not write the window, thez_streamor zlib's state. Each chunk thatinhands out is readable, is a byte array or part of one, does not overlap the window, and stays readable until the nextincall (CallbackProtocol,BackPlatform). - One
inflateBackcall is offered fewer than 2^48 input bytes in all, the first chunk included (inputBound). - Between two
inflateBackcalls you do not write the window, and you change only the four buffer fields of thez_stream(BackSafeReachable.caller). Whenwindowpoints to the first byte of an array, this holds for the whole array, also past2^windowBitsbytes: between two calls you write no byte of it.
gzip files: the gz* functions
pathandmodeareNULLor NUL-terminated strings (GzOpenSafe,GzDopenSafe).- A buffer passed to
gzread,gzfreadorgzgetsis writable, and a buffer passed togzwriteorgzfwriteis readable, for the length the call names. Theerrnumpointer ofgzerrorisNULLor points to anintof your own (GzRange). - These buffers, the
intofgzerror, the argument ofgzputs, and the format and every pointer argument ofgzprintfandgzvprintfare memory of your own, not memory that zlib allocated for the file. In particular, never pass the string thatgzerrorreturned back into a call on the same file (GzRange,GzArguments). - The argument of
gzputsis a NUL-terminated string, notNULL(CString). - A
gzprintforgzvprintfcall is a call ofvsnprintfthat C defines for its format and arguments, and its format has no%n. The library does not check this, and no premise states it. The model does not read the conversions of the format, so it does not detect a format that does not match its arguments: for such a call the theorem holds of the model and says nothing about the C. On a file open for writing and not in error, the format is a NUL-terminated string and every pointer argument points into memory that is not freed (GzArguments). - Between calls you do not write memory that zlib allocated for the file (
GzCallerFrame). - You do not use a file after the call that closed it:
gzclose, orgzclose_rorgzclose_won a file of that mode. The file is freed, as in C. - Termination of
gzread,gzfread,gzgetc,gzgetc_,gzgetsandgzungetcis proved when the file descriptor can deliver fewer than 2^61 more bytes (ReadsFinite). Without that, the proof still shows that these calls cause no undefined behaviour. - A
NULLfile is refused by every function, with nothing changed (Goal.gz_refusal). Thegzgetc()macro onNULLis undefined behaviour in C and is not covered.
Build and platform
The columns of every table below: the premise and the Lean predicate that states it; what it asks; the goals that state it; and the reason for it, with what is not covered.
| Premise | What it asks | Goals | Reason, and what is not covered |
|---|---|---|---|
| Initial configuration | Default x86_64 Linux, LP64, static build and default allocator: zalloc and zfree are each NULL or the default function (DefaultOrNull, DefAlloc) |
Every goal | The proofs are about this build and this allocator. Not covered: a custom allocator, and any other build configuration (progress). Failure of the default allocator is covered: the goals hold for every allocation outcome. |
Platform byte-object scope (ByteObjectsFit) |
Each byte object has fewer than 2^63 bytes, including caller, static and embedded storage |
See the list below | The LP64 limit PTRDIFF_MAX on the size of one object (platform). It limits neither total memory nor the length of a stream. |
Where the goals state ByteObjectsFit:
- on the heap of every stream call (
StreamCallDomain, and clause 2 ofStreamSequenceSafety); - for inflate streams, also on every earlier heap of the history, before each call and after each
caller edit (
StreamReachable.step,.rebuffer); a deflate history carries it only at the call a goal states; - in the
compress*anduncompress*goals (CompressorSafety,UncompressCountedSafe,UncompressSingleSafe); - on the heap of every gz open and after every caller edit of a gz history (
GzHistory,GzOpenSafe,GzDopenSafe), which covers the caller's path and mode strings; - for the callback decoder, on the heap of each
inflateBackcall and after each call-back step (BackSafeReachable.step,BackPlatform).
The init, checksum and refusal goals do not state it. The End goals do not state it for the
heap of the call; an inflate history carries it as the second item says. A concrete heap satisfies it
(inflate_default_witness_platform).
The conditions that goals put on the model's heap (Fresh, Uniq, LibraryGlobals,
CrcGlobals), the loop fuel, the CRC address model and the rule for pointer plus zero and
NULL - NULL are not duties of a caller. They are in model limits.
Stream calls: inflate and deflate
The safety goal of a stream function holds on every reachable stream (StreamReachable) whose
arguments satisfy StreamArguments.
| Premise | What it asks | Goals | Reason, and what is not covered |
|---|---|---|---|
Stream initialisation (InitArguments) |
strm is NULL, or a readable record whose zalloc and zfree are each NULL or the default function (DefaultOrNull). version is NULL or readable for its first byte. The heap is well formed (model limits). The other fields of the record, state included, the first byte of version and stream_size are arbitrary. Goal.inflateBackInit__safety asks one thing more, which zlib.h asks as well: a non-NULL window with windowBits 8 to 15 is writable for 2^windowBits bytes. |
Goal.inflateInit2__safety, Goal.inflateInit__safety, Goal.deflateInit2__safety, Goal.deflateInit__safety, Goal.inflateBackInit__safety |
Only DefaultOrNull is narrower than zlib.h. A wrong version, a wrong stream_size and a NULL stream are covered: the call returns an error code and leaves no block behind (InitResultSafe). See note 1. |
First call of a history (StreamReachable.inflateInit, .deflateInit) |
A history starts at an init call that returned Z_OK, on a readable record with DefaultOrNull, a version whose first byte is '1', and stream_size = 112. |
Both sequence goals, and every one-function stream goal through StreamReachable |
Apart from DefaultOrNull, these are the conditions under which the C returns Z_OK. There is no clause on state. |
Stream buffers (StreamBuffers) |
The input range (next_in, avail_in) and the output range (next_out, avail_out) are separate, and neither lies in storage the stream owns. Each range is NULL or readable, and the output range is writable. |
Goal.inflate_safety, Goal.deflate_safety, Goal.deflateParams_safety, and these calls in both sequence goals (StreamArguments). The functional Goal.inflate and Goal.deflate assume it too. |
zlib.h describes these calls for buffers the caller keeps apart. Not covered: input that overlaps output, and a buffer inside the stream's own state. |
Caller edits between calls (Rebuffer) |
Between two calls of a history the caller changes only next_in, avail_in, next_out and avail_out of the stream record, and memory the stream does not own. |
Both sequence goals; every one-function stream goal through StreamReachable |
zlib.h's rule: the application updates the buffer fields, and all other fields "must not be updated by the application". Not covered: a history in which the caller writes another field of the record, or a block the stream owns. |
Other stream arguments (StreamArguments) |
inflateSync: the input range is NULL with avail_in = 0, or readable and outside the stream's storage. deflatePrime: no deflate call has started the stream (DeflateNotStarted); deflateSetHeader has the same ordering rule (row "Header arguments"). The header and dictionary calls have their own rows. The other stream calls have no argument premise. |
The function's safety goal, and the same call in a sequence goal | The ordering rule is zlib.h's ("before the first deflate() call"). deflatePrime after a deflate call is undefined behaviour of the real C (reproduced with the real C under a sanitizer). |
Dictionary buffers (CallerRange) |
The dictionary argument is NULL, or a readable range (writable for the two Get calls) with no byte in a block the stream owns. For inflateGetDictionary the range has whave bytes; for deflateGetDictionary, min(w_size, strstart + lookahead) bytes. |
Goal.inflateGetDictionary_safety, Goal.deflateGetDictionary_safety, Goal.inflateSetDictionary_safety, Goal.deflateSetDictionary_safety, and these calls in the sequence goals |
A caller's dictionary has no reason to lie in the stream's storage. Not covered: a dictionary buffer inside the stream's window or other storage. |
Result cells (dictLength, pending, bits) |
No premise, and none can be stated. The translation passes these scalar out-parameters as values, not as memory. inflateGetDictionary takes the value of *dictLength, or none for NULL (Option UInt32). deflateGetDictionary, deflatePending and deflateUsed take only the fact whether each pointer is NULL (Bool). Each function returns the value the C stores as a further result. |
Goal.inflateGetDictionary_safety, Goal.deflateGetDictionary_safety, Goal.deflatePending_safety, Goal.deflateUsed_safety, and these calls in the sequence goals |
The goals say nothing about the memory of the result cell, through which the C stores with a plain assignment (*dictLength = ...). Covered: a call whose result cell is an ordinary variable of the caller, apart from the dictionary buffer, the stream record and the storage the stream owns. Not covered: any other call. |
Header arguments (HeaderMemory, DeflateNotStarted, DeflateHeaderLive) |
inflateGetHeader: the header record is not NULL, is not owned by the stream, and its extra, name and comment buffers are NULL or writable for extra_max, name_max and comm_max bytes. deflateSetHeader: the header is NULL or a record the stream does not own, whose non-NULL extra is readable for extra_len bytes and has no byte in a block the stream owns, and whose non-NULL name and comment are NUL-terminated strings shorter than 2^64 bytes; and no deflate call has started the stream. name and comment have no ownership clause at this call; the row "Deflate gzip header regions" has it. deflateBound, deflateBound_z: ActiveHeader (the four rows below) and a set gzip header that is live at any time, not only while it is written. |
Goal.inflateGetHeader_safety, Goal.deflateSetHeader_safety, Goal.deflateBound_safety, Goal.deflateBound_z_safety, and these calls in the sequence goals |
inflateGetHeader stores through the pointer (head->done = 0), so a NULL header is not covered. The ordering rule of deflateSetHeader is zlib.h's; a NULL header set while the header is being written is dereferenced by the real C (reproduced with the real C under a sanitizer). |
Attached gzip header stays live (HeaderMemory in ActiveHeader) |
At every inflate call, in every mode, also after the header is complete (done set): the record given to inflateGetHeader is still a live record that the stream does not own, and its non-NULL extra, name and comment are still writable for extra_max, name_max and comm_max bytes, outside the stream's storage. For a deflate stream, at every deflate, deflateParams, deflateBound and deflateBound_z call while the status is GZIP_STATE .. HCRC_STATE (DeflateHeaderWriting): the record given to deflateSetHeader is live and not owned by the stream, its non-NULL extra is readable for extra_len bytes outside the stream's storage, and its non-NULL name and comment are NUL-terminated strings. GZIP_STATE is the status of a gzip stream from init or reset on, before any deflate call, so the period starts at deflateSetHeader. After the header is written the caller may release it, except for deflateBound and deflateBound_z (row above). A stream made by inflateCopy or deflateCopy has the header pointer of its source, so the row holds for the calls on the copy too. |
Goal.inflate_safety, Goal.deflate_safety, Goal.deflateParams_safety, Goal.deflateBound_safety, Goal.deflateBound_z_safety, and these calls in both sequence goals |
The library keeps the caller's pointer and uses it in later calls. For inflate the premise asks more than the C uses: inflate.c reads and writes state->head only in the header modes (HEAD .. HCRC). Not covered: an inflate call after the caller freed the record or its buffers, also after done. For deflate the premise asks for extra_len readable bytes; the C reads extra_len mod 2^16. |
Inflate gzip extra field (InflateHeaderProgress) |
While inflate reads a gzip header (HEAD .. HCRC) into an attached gz_header, its extra buffer (extra_max bytes) is separate from the unread input; in EXTRA, the record's extra_len is not below state->length. |
Goal.inflate_safety and every inflate call of Goal.inflate_sequence_safety; also the functional Goal.inflate and Goal.inflate_sequence |
Each excluded case is undefined behaviour of the real C in the zmemcpy of EXTRA (reproduced with the real C under a sanitizer): an overlapping copy, or a write past extra_max after extra_len is lowered inside the extra field. The premise is a condition on the record at each call, whoever wrote extra_len: the caller, or inflate on another stream attached to the same record, since inflate writes extra_len in its attached record. Not covered: two streams attached to one header record, as after inflateCopy. zlib.h is silent on all of this. |
Deflate gzip header regions (DeflateHeaderApart) |
While the status is GZIP_STATE .. HCRC_STATE and a gz_header is attached, at every deflate, deflateParams, deflateBound and deflateBound_z call: the input range, the output range, the extra field (extra_len mod 2^16 bytes), the name and the comment (each through its NUL) are pairwise separate byte ranges, which may share a block; the extra field, name and comment lie outside the storage the stream owns. The input and output ranges are the ones the z_stream fields name at that call, also for deflateBound and deflateBound_z, which do not use them. |
Goal.deflate_safety, Goal.deflateParams_safety, Goal.deflateBound_safety, Goal.deflateBound_z_safety and every such call of Goal.deflate_sequence_safety; also the functional Goal.deflate and Goal.deflate_sequence |
These regions have no reason to overlap. Not covered: one string used as both name and comment (the same address, for example two merged string literals), because the two ranges, each through its NUL, coincide. A name in the output range or in pending_buf is undefined behaviour of the real C: a flush or a header byte overwrites its NUL, and the name loop reads past the buffer (reproduced with the real C under a sanitizer). zlib.h is silent on these layouts. |
Deflate gzip header progress (DeflateHeaderProgress) |
At each call of the row above, when an earlier deflate call returned in the middle of a field of the attached gz_header, the caller has kept what was already written: a field still covers the part written (gzindex), and in EXTRA_STATE, NAME_STATE or COMMENT_STATE that field is not set to NULL part-way (gzindex = 0 when it is NULL). |
The same goals as the row above | The excluded edits are undefined behaviour of the real C (reproduced with the real C under a sanitizer): a shortened field is read past its end; a field set to NULL part-way is skipped without resetting gzindex, and the next string is read from gzindex on, past its end. zlib.h asks for the header before the first deflate call and is silent on changes while it is written. |
Refused streams (RefusedInflate, RefusedDeflate) |
A refused stream is NULL, or a readable record whose state is NULL, whose zalloc or zfree is NULL, or whose state is a live state record the check refuses (a wrong back pointer, mode or status). |
The refusal clause of the safety goal of each documented stream function except the four init functions, and of Goal.inflateCopy_safety and Goal.deflateCopy_safety; Goal.inflate_refusal, Goal.deflate_refusal |
Contains a record after End, the destination of a failed copy, a struct copy of a live record, and a record after a failed init as note 2 says. The same note lists the three kinds of record that are not covered. |
| Copy destination | In the clause for a copy from a reachable source: the destination is a readable stream record that is not the source record (source ≠ dest), and the source has the default allocator (DefAlloc). The refusal clauses ask only for a readable destination record, or for nothing when dest is NULL; they have no source ≠ dest premise. |
Goal.inflateCopy_safety, Goal.deflateCopy_safety, and the functional Goal.inflateCopy, Goal.deflateCopy |
With dest == source and a reachable source, the C zmemcpy(dest, source, sizeof(z_stream)) copies an object onto itself, which is undefined behaviour. With a refused source the C returns before the copy, so dest == source is covered there. Not covered, because the model cannot express it: a destination that partly overlaps the source record, a buffer or a state record (model limits, address and layout model). |
Direct deflateResetKeep |
A deflate call history (StreamOperation .deflate) has no direct deflateResetKeep call; deflateReset and deflateInit2_ stay. |
Goal.deflate_sequence_safety and the one-function deflate goals through StreamReachable |
zlib.h declares deflateResetKeep under "undocumented functions (not part of the zlib API)". Not covered: a history that contains a direct call. |
Note 1: init and unset fields
In C, the fields that the caller of inflateInit leaves unset hold indeterminate values. The
model has no such value. An unset integer field has an arbitrary value, and an unset pointer
field has some value the model can express: NULL or a reference to a model object. The four
init goals and Goal.inflateBackInit__safety hold for every such value, because InitArguments
constrains only zalloc and zfree. The init functions of the C assign strm->state and do not
read it. That the model has no "uninitialised pointer" value is a limit of the model
(trusted base, item 2).
The three non-vacuity goals of init (Goal.inflate_initialisation_domain,
Goal.deflate_initialisation_domain, Goal.inflate_back_initialisation_domain) are stated for a
record whose state is NULL before the call (InitDomain). They say that init returns Z_OK
on every such heap when no allocation fails. They are not premises of a safety goal.
Note 2: refused streams
Where the refusal is stated. The safety goal of every documented inflate and deflate stream
function except the four init functions has two clauses: the refusal of a refused stream
(RefusedInflate or RefusedDeflate), and the call on a reachable stream. Goal.inflateCopy_safety
and Goal.deflateCopy_safety have a clause for a refused source, beside their clauses for a
NULL argument. Goal.inflate_refusal and Goal.deflate_refusal state again, in one goal each,
the refusals of inflate, inflateEnd, inflateReset, inflateReset2, inflateGetDictionary,
inflateSetDictionary and inflateCopy, and of deflate, deflateSetDictionary,
deflateParams, deflateGetDictionary and deflateCopy.
What a refused call returns. Z_STREAM_ERROR, with two exceptions that follow the C.
inflateMark returns -65536. deflateBound and deflateBound_z return the bound they give
for a NULL stream with the same sourceLen, which is not an error value.
What a refused call changes. For every function except inflate, inflateSync and the two
copies, the heap after the call is the heap before it. A copy from a refused source stores NULL
in the state field of the destination record, as the C does (dest->state = Z_NULL), and
changes nothing else; the clause asks that the destination is a readable record and the source
pointer is not NULL. For inflate and inflateSync, on a heap that is Fresh, the goal
states that the call writes no block that was live, that every live block is as it was, and that
no block is created or freed. This is not heap equality: each of the two translations allocates
and frees a local four-byte array, so the model's block counters may grow.
A record after a failed init. It is refused when its state is NULL, or when its zalloc
or zfree is NULL. The table says what each failure leaves in the record.
| Failure | state after the call |
zalloc, zfree after the call |
|---|---|---|
Z_VERSION_ERROR; Z_STREAM_ERROR of inflateBackInit_ for a NULL window or a bad windowBits |
As before the call | As before the call. When they were NULL, as the checklist asks, the record is refused whatever state holds |
Z_MEM_ERROR when the state record cannot be allocated |
As before the call | Set to the default functions |
Z_STREAM_ERROR of deflateInit2_ for a bad parameter |
As before the call | Set to the default functions |
Z_STREAM_ERROR of inflateInit2_ for a bad windowBits |
NULL |
Set to the default functions |
Z_MEM_ERROR of deflateInit2_ when one of its four buffers cannot be allocated |
NULL |
Set to the default functions |
In rows 1 to 3 state holds what the caller left there. With zalloc and zfree set, the
record is refused if that value is NULL; if it is a stale or garbage pointer, the record is
one of the three kinds below.
Not covered. Three kinds of record are outside the refusal domain when zalloc and zfree
are set. In C the state check reads through the pointer in each of them, which is undefined
behaviour.
- A state field that holds a garbage address, as in a never-initialised automatic
z_stream. The model cannot express it: the field isNULL, an inflate state number or a deflate state number, and a pointer in fresh memory isNULL(model limits, row "Uninitialised pointers become NULL"). - A dangling state: the field names a state that is not live, as in a struct copy used after the original was ended. The predicate excludes it.
- A wrongly typed state: a deflate state passed to an inflate function, or the reverse. The predicate excludes it.
A model-only case. A state made by inflateBackInit_ has its strm and mode fields
unwritten. In C the state check of an inflate function reads an indeterminate pointer; the model
reads NULL, so the record is refused (RefusedInflate). For such a stream the refusal goals
are statements about the model only (model limits,
row "Uninitialised pointers become NULL"). zlib.h ends such a stream with inflateBackEnd.
Whole-buffer utilities and checksums
| Premise | What it asks | Goals | Reason, and what is not covered |
|---|---|---|---|
Whole-buffer compression (CompressArguments) |
The source and the destination do not overlap: Separate source n dest c. The source is readable and the destination writable for its capacity, unless the call is one the C refuses (compressRejected). compress and compress2 take a non-NULL length cell; a NULL cell is admitted only for the _z forms. |
Goal.compress_safety, Goal.compress2_safety and their _z forms |
Source and destination have no reason to overlap. The length cell *destLen is a scalar value in the translation (Option UInt64), not memory, so the goals say nothing about its memory. Not covered: overlapping source and destination, and a length cell that is not a writable variable apart from both. |
Counted decompression (UtilitySeparation, UncompressCountedSafe, UncompressSingleSafe) |
Source, destination, the destination-length cell and the source-length cell are pairwise separate. uncompress and uncompress_z need the source/destination and length-cell/data separations. A length cell is eight readable and writable bytes (LengthCell); uncompress and uncompress2 take non-NULL cells. |
Goal.uncompress_safe, Goal.uncompress2_safe and their _z forms |
These regions have no reason to overlap. Here the cells *destLen and *sourceLen are memory in the translation, so the separation is a stated premise. Not covered: a length cell that aliases a data buffer or the other cell. |
Adler initialization queries (AdlerBufferBytes) |
buf is NULL only with zero length; a non-NULL readable buffer has its full length domain. |
Goal.adler32_safety, Goal.adler32_z_safety, and the functional Goal.adler32, Goal.adler32_z |
Narrower than zlib.h of zlib 1.4, which allows a NULL buf without a condition on len. With NULL and len = 1 the C reads buf[0], before its test for NULL. Not covered: a NULL buf with a nonzero len. The CRC goals keep BufferBytes, which admits NULL with any length. |
| CRC combination operator | The operator is one that crc32_combine_gen or crc32_combine_gen64 returned. |
Goal.crc32_combine_op_safety |
zlib.h's domain for crc32_combine_op. Not covered: an arbitrary op value. |
Callback decoder
Goal.inflate_back_sequence_safety holds on the histories of BackSafeReachable. So do the
history clauses of Goal.inflateBack_safety and Goal.inflateBackEnd_safety, which repeat
clauses of the sequence goal: every row below that names the sequence goal holds for those two
goals as well. Goal.inflateBackInit__safety has none of these premises; its premises are in
the row "Stream initialisation".
| Premise | What it asks | Goals | Reason, and what is not covered |
|---|---|---|---|
Callback decoder init (BackInitArguments in BackSafeReachable.init) |
The stream record is readable; zalloc and zfree are each NULL or the default function; version points to a readable byte '1'; stream_size = 112; the call returned Z_OK. The record's other fields, state included, may hold any value. |
Goal.inflate_back_sequence_safety |
Apart from the default allocator, these are the conditions under which the C returns Z_OK. An init call that fails starts no history; its safety is Goal.inflateBackInit__safety. |
Callbacks (CallbackProtocol) |
The caller supplies a protocol for its in and out functions; the list below gives its clauses. |
Goal.inflate_back_sequence_safety |
The callbacks are caller code, so what they do is a premise. Descriptor objects may share the window allocation outside the slice. |
Caller edits between calls (BackSafeReachable.caller) |
Between two calls a caller edit is a Rebuffer (row "Caller edits between calls") that keeps the window slice and the read-only flag of every block that stays live. |
Goal.inflate_back_sequence_safety |
The window is the decoder's history. Narrower than zlib.h, which does not forbid a write to the window between two calls. That the C does not read earlier window bytes (inflateBack sets state->whave = 0 at the start of each call) is not yet confirmed. When the window pointer is at offset 0 of its block, the stream owns that block in the model (InflateOwned), and Rebuffer then keeps the whole block between calls, not only the slice. No C code can change a read-only flag, so that clause excludes no caller. |
| Callback input total | protocol.inputBound < 2^48: one inflateBack call is offered fewer than 2^48 input bytes in all. The total counts the first chunk (next_in, avail_in at the call) and every chunk the in calls hand out. |
Goal.inflate_back_sequence_safety |
The runtime bounds every loop by 2^64 iterations (model limits), and each round of the decoding loop reads at least one bit, so a call offered more input could exhaust the fuel where C would continue. zlib.h has no such limit. Above the bound nothing is concluded for that call: not that it returns, not the absence of undefined behaviour, not its frame. |
| Callback decoder window | 8 ≤ windowBits ≤ 15 and a non-NULL window writable for 2^windowBits bytes, as zlib.h asks, and also: the window is a slice of a heap byte block. |
Goal.inflate_back_sequence_safety, through BackSafeReachable.init |
The model's only other writable byte view is the depth array inside a deflate state, which is library storage that a caller cannot name. Not covered: a window there. |
| Callback decoder input chunks | Every input chunk lies in a heap byte block: the caller's first chunk (BackFirstChunk) and each chunk in hands out (BackPlatform). |
Goal.inflate_back_sequence_safety |
inflate_fast runs on the chunk, and its proof is for heap byte blocks (model limits, "Fast decoder helpers"). Not covered: a chunk in other storage of the model, such as a field of a structure or static data; the C handles a chunk in any readable storage. |
The clauses of CallbackProtocol:
- Each of
inandoutreturns without a fault and changes only the caller's own blocks, which exclude the state and the stream record. - The blocks that hold callback input, the first chunk included, are among the caller's own
blocks, also for callbacks that only read them. For these blocks the conclusion's guarantee is
the invariant clause, not the frame clause (
CallbackFrame). When the input shares the window's block, that block is one of the caller's own; the frame then does not limit the library's writes in it to the window slice, and the invariant describes the bytes outside the slice. - The clauses about a call of
inoroutare required only on a heap in which the stream is a valid callback decoder over this window (CallbackEntry). The library hands only such heaps to the callbacks. Without this restriction no protocol could exist (callbacks). - Each keeps the bytes of the window slice.
inhands out a readable chunk that is separate from the window, the state and the stream record.outkeeps the current input chunk readable.- The total input has a finite bound (
inputBound). - Each callback leaves the heap well formed (
Fresh,Uniq), and every block it creates is one of the caller's own (ExternalFrame). - The protocol carries an invariant over the heap and the log of bytes supplied and delivered.
Each callback keeps it. The invariant may depend only on the caller's own blocks and on the
allocator fields of the heap, and not on the bytes of the window slice
(
CallbackProtocol.local_).
Two more premises about the same call are premises of the third clause of the goal, not clauses
of CallbackProtocol: the first chunk (next_in, avail_in) is readable and separate from the
window, and the invariant holds on the heap on which inflateBack is called.
Goal.inflateBack_call_domain shows that these premises and a protocol hold together on a
concrete call.
Gzip file interface
Goal.gz_sequence_safety holds on every history of one handle (GzHistory), for every
file-system world. The safety goal of each gz function (Goal.<function>_safety) restricts one
clause of it to that function, with the same premises: a row below that names
Goal.gz_sequence_safety holds for the goals of the functions it is about. The goals are about
the patched source (patches 0002 to 0005). The gz world is trusted
semantics beside the heap: the external-I/O model describes it, and the
trusted base says what is assumed of it.
| Premise | What it asks | Goals | Reason, and what is not covered |
|---|---|---|---|
Gz open arguments (GzOpenSafe, GzDopenSafe, GzHistory.open) |
path and mode are each NULL or a NUL-terminated string shorter than 2^64 bytes; the heap is well formed and its byte objects fit; the world is a well-formed file system (FileSystem). |
Goal.gz_sequence_safety |
The C reads each string up to its NUL. Covered: every descriptor, every mode text and every world, including every failure. Not covered: a path or mode that is not NUL-terminated inside its object. |
Gz caller buffers (GzRange in GzArguments) |
The caller buffers of gzread, gzfread, gzwrite, gzfwrite, gzputs, gzgets and gzerror are readable (writable for the reading calls and for gzerror's errnum) and lie apart from the blocks the handle owns (GzOwned). The argument of gzputs is a NUL-terminated string (CString), through its NUL: readable bytes without a NUL, and NULL, are outside. |
Goal.gz_sequence_safety |
The library frees and rewrites its own blocks during a call (below). Not covered: a buffer inside the handle's blocks. |
Gz printf strings (GzArguments) |
The format of gzprintf and gzvprintf and every pointer argument lie apart from the blocks the handle owns (GzOwned). |
Goal.gz_sequence_safety |
The same reason as the row above. |
Gz printf call (caller's obligation; GzArguments) |
The call of vsnprintf is defined in C for the format and the arguments, and the format has no %n: no premise states this, the caller ensures it, as for every printf call (trusted base). GzArguments asks, when the file is open for writing and not in error, that the format is a NUL-terminated string and that every pointer argument points into a block that is not freed. It asks this also when gz_init, gz_zero or gz_vacate then fails, where the C returns before it calls vsnprintf. |
Goal.gz_sequence_safety |
vsnprintf is an external call modelled by its contract, so every valid format whose arguments are integers or strings is covered. The model's argument type (VaArg) has no floating-point or void * case: floating conversions and %p are not covered. The model does not read the conversions of the format, so a call that C does not define is no fault in the model, and the goal says nothing about the C for it. Not covered: %n, which writes caller memory that the frame of the conclusion does not describe; a format that does not match its arguments; and a call that returns before vsnprintf with a format that is not a string. |
Gz caller and world steps (GzCallerFrame, GzWorldStep) |
Between two calls the caller may change any block the handle does not own, and may free its own buffers; the heap stays well formed and its byte objects fit. The world may change to any well-formed file system: another party may close or reuse the handle's descriptor. | Goal.gz_sequence_safety |
The handle's blocks belong to the library. Not covered: a history in which the caller writes a block the handle owns. The world step admits more than a real system does. |
Gz reading termination (ReadsFinite) |
For gzread, gzfread, gzgetc, gzgetc_, gzgets and gzungetc: the handle's descriptor has a finite read budget below 2^61 bytes (fs.readBudget fd = some b with b < 2^61), the total the descriptor can still deliver. The premise also says that the descriptor number is not negative (HasBudget). |
The termination half of Goal.gz_sequence_safety, for these six calls only |
On an endless source two loops of the C do not end (below). The premise excludes no fault: the no-fault half and the post-condition hold for every world, with no budget. gzdirect, the write side and gzseek do not need it. |
| Gz OS facts | A nonempty write never returns 0; close releases the descriptor also when it fails. |
Goal.gz_sequence_safety, through the world model |
Assumptions about the system, trusted and not checked. Both are Linux behaviour. lseek is not restricted: a successful call may return any 64-bit value. The first bounds the write loops of gz_comp. not yet confirmed: by a reading of the C, a write that returned 0 forever would make gz_comp loop forever. The model has no world with such a write, so no theorem states this. |
The model of strerror is a limit of the model, not a duty of a caller: see
model limits, row "External error
strings".
Why the handle's own strings are excluded
The string that gzerror returns is state->msg. The library frees it in gz_error whenever
it clears or replaces the error, which many entries do before they read their arguments. So
passing the string back into a call on the same handle can be a use after free in the C. On a
writer whose last write stalled, gzprintf(f, "%s", gzerror(f, &e)) frees the message and then
reads it in vsnprintf: AddressSanitizer reports a heap use after free. zlib.h only warns that
later gzerror calls may invalidate the string. The premise excludes the handle's own blocks for
every call that takes caller memory, whether or not that call frees the message.
Why a read budget
Two loops of the C do not end on an endless source: a source that delivers forever data that
decodes to nothing (empty gzip members) keeps gz_fetch looping, and gz_skip with a huge
pending skip reads forever. No finite loop fuel covers this. With a read budget every loop is
bounded.
The figure 2^61 is the model's limit, not zlib's. A loop of the model has 2^64 iterations of
fuel. The reading loops are bounded by measures built from the input left, the read budget and
the bytes still to deliver (fetchRank; the measures of gz_read and gz_skip). A fetch fills
its buffer unless it fails, ends the input, reaches GZ_OFF_MAX or lowers fetchRank, so a
budget below 2^61 keeps those measures, and the iterations, below 2^64. Some bound is needed:
2^70 bytes of empty gzip members, 20 bytes each, need more rounds than the loop fuel.
The budget is keyed by descriptor number: a number reused after close inherits the remaining
budget. gzdopen refuses a negative descriptor, so no handle comes from one.