Hacker News

Right Code, Wrong Comment: The Pointer Chase Inside Zlib

Comments

Right Code, Wrong Comment: The Pointer Chase Inside zlib

At zlib/trees.c:945, inside the inner loop of compress_block, sits a single assertion:

/* Check for no overlay of pending_buf on needed symbols */
#ifdef LIT_MEM
Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow");
#else
Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow");
#endif

In every release build of zlib (#ifndef ZLIB_DEBUG), Assert preprocesses to whitespace. Neither compress_block, nor send_bits, nor put_byte checks whether s->pending has room before writing to s->pending_buf.

When we set out to build machine-checked Lean 4 safety proofs for both zlib and zlib-ng (zlib ร— Lean; repository cla7aye15I4nd/oss-proof), most of both codebases came down to familiar systems invariants: ring-buffer wraparound in inflate_fast, hash-chain bounds over uninitialized slots in longest_match, and state-machine discipline across streaming calls.

Line 945 of zlib's trees.c was different. Right above the buffer allocation in deflate.c, zlib's authors wrote a 38-line mathematical proof that this stripped assertion can never fire - and that proof is wrong. Yet when we put down the theorem prover and tried to construct an exploit input that actually crashes compress_block, every single attempt hit an invisible wall.

This post walks through the whole investigation from the ground up:

  • What deflate actually does: why zlib needs two passes per block, and why two cursors end up racing through the same pending_buf array.
  • Why deflate.c's proof fails (and why an exploit still won't fit): why an average bit-length bound cannot prevent a mid-block collision - and why a collision would trigger an out-of-bounds .rodata read, not just corrupt output.
  • How the C code connects to our Lean 4 proof: step by step, how pointer mutations and bi_buf bit-shifts reduce to pure Huffman-tree inequalities - culminating in an algebraic cancellation that closes memLevel 1..2 without brute-force search.
  • Proof geometry vs. physical reality: the exact byte-and-bit closest approaches we synthesized on unmodified deflate(), why slot-by-slot proofs hit a mathematical ceiling near 980 while physical C stops at 720, and how one could close that gap.

1. How deflate Actually Works (and Why Two Pointers Share One Buffer)

If you have never read zlib's source code, variable names like pending_buf, sym_buf, bi_valid, and _dist_code look opaque. The underlying idea, however, is straightforward once you trace a concrete string like "abcde_abcde_!" through one DEFLATE block.

Pass 1: Why deflate Cannot Emit Bits Immediately

Suppose deflate is scanning "abcde_abcde_!". Its LZ77 matcher (deflate_fast or deflate_slow) spots that the second "abcde" repeats the bytes 6 positions earlier, turning the 13-byte string into 9 symbols: 'a', 'b', 'c', 'd', 'e', '_', Match(dist = 6, len = 5), '_', '!'

Why doesn't deflate immediately write the Huffman bitcodes for 'a', 'b', 'c' to the output stream as soon as it sees them? Because it does not know the Huffman tree yet! Optimal Huffman coding assigns short bitstrings (down to 1 bit) to frequent symbols and long bitstrings (up to 15 bits) to rare ones. Until deflate has scanned the entire block and counted how many times each byte and match length occurs, it cannot build the block's custom Huffman trees.

So deflate processes every block in two passes:

  • Pass 1 - Record & Tally (_tr_tally, trees.c:1095-1119): As the matcher scans input, it parks each symbol in an intermediate array sym_buf using a fixed 3-byte (24-bit) encoding - two bytes for dist (0 for a literal, 1..32506 for a match) and one byte for lc (the literal byte, or len - 3) - while incrementing frequency counters Freq[].
  • Pass 2 - Build Trees & Emit Bits (_tr_flush_block, trees.c:997-1089): Once sym_buf fills up, deflate builds Huffman trees from Freq[], reads back the recorded 3-byte symbols from sym_buf one by one, and packs their variable-length bitcodes into the output byte queue pending_buf.

Buckets and Extra Bits: How a 3-Byte Symbol Can Become 48 Bits (or 1 Bit)

There is one more piece of the format we need before everything clicks: how matches are Huffman-coded. A match distance dist can be anywhere from 1 to 32,768. If DEFLATE built a Huffman tree with 32,768 leaves, transmitting the tree description at the start of every block would cost kilobytes - far larger than small files!

Instead, RFC 1951 ยง3.2.5 splits every length and distance into a coarse bucket (which is Huffman-coded) plus raw binary "extra bits" (which pinpoint the exact offset inside that bucket):

  • Literals & Lengths share one 286-symbol tree (dyn_ltree): codes 0..255 are literal bytes; 256 is END_BLOCK; 257..285 are 29 length buckets, carrying 0 to 5 extra bits (for example, bucket 284 covers lengths 227..257 using 1 Huffman code + 5 extra bits; bucket 285 is length 258 alone with 0 extra bits).
  • Distances use a 30-symbol tree (dyn_dtree): codes 0..29 are 30 distance buckets, carrying 0 to 13 extra bits (bucket 29 covers distances 16,385..32,768 using 1 Huffman code + 13 extra bits).

To map dist - 1 (0..32,767) to its bucket 0..29 in O(1) time, zlib uses a 512-byte lookup table _dist_code[512] (deflate.h:320-321).

Because DEFLATE caps Huffman code lengths at 15 bits, one 3-byte symbol in sym_buf can turn into:

  • As little as 1 bit (a very frequent literal byte), or
  • As much as 15 + 5 + 15 + 13 = 48 bits (a rare match landing in a 5-extra-bit length bucket and a 13-extra-bit distance bucket) - twice the 24 bits it occupied in sym_buf!

Three Competing Block Formats - and the Shared Buffer Overlay

When Pass 1 finishes recording up to n โ‰ค B - 1 symbols - where B = lit_bufsize = 2^(memLevel+6) ranges from 128 (memLevel = 1) to 32,768 (memLevel = 9, default 16,384 at memLevel = 8) - _tr_flush_block evaluates three legal DEFLATE encodings for the block and picks whichever produces the fewest bytes:

  • Stored (00): Abandon compression and copy the raw uncompressed input bytes straight out of the sliding window (stored_len + 4 bytes).
  • Fixed Huffman (01): Use RFC 1951's hardcoded Huffman tables (literals take 8 or 9 bits, lengths 7 or 8 bits, distances 5 bits). No tree header is needed - just a 3-bit tag - and every symbol costs at most 8 + 5 + 5 + 13 = 31 bits.
  • Dynamic Huffman (10): Build custom trees dyn_ltree and dyn_dtree from Freq[]. Because the decoder does not know these custom trees yet, send_all_trees must serialize the tree code-lengths at the very start of the block (compressed with a tiny 19-symbol run-length Huffman tree called bl_tree) before compress_block encodes symbol 0.

Now look at memory layout. Pass 2 only begins when pending_buf (the output queue) has been completely flushed to the caller (pending = 0), leaving at most bi_valid bits:

lit_bufsize = 1 << (memLevel + 6);
pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, LIT_BUFS); /* 4 * B bytes */
s->pending_buf_size = (ulg)s->lit_bufsize * 4;
...
s->sym_buf = s->pending_buf + s->lit_bufsize; /* starts 1/4 of the way in */
s->sym_end = (s->lit_bufsize - 1) * 3; /* max n = B - 1 triples */

Step through all four stages of a block below to watch how Pass 1 and Pass 2 share pending_buf[0 .. 4B):

Once compress_block starts Pass 2b, two cursors race left-to-right across the same array:

  • The Runner (B + 3k): starts at byte B (8B bits). On step k, reading symbol k frees 3 bytes, advancing the boundary of unread symbols by +24 bits.
  • The Chaser (pending + bi_valid): starts near byte 0 (with at most 7 leftover bits), leaps forward by the 3-bit tag + dynamic tree header before symbol 0 is read, and then advances by 1 to 48 bits per symbol.

Overwriting [B .. B + 3k) is completely harmless - those symbols have already been read! Disaster strikes only if the Chaser ever catches B + 3k and overwrites a symbol that compress_block hasn't read yet.

2. Why Overwriting sym_buf Breaks Memory Safety - and Why deflate.c's Proof Is Wrong

Not Just Corrupt Output: The _dist_code[512] Cliff

Before trying to break or prove this invariant, ask a triage question: if s->pending did overtake B + 3k and overwrite unread symbols, wouldn't deflate merely emit a corrupt compressed stream? Look twenty lines above the Assert in trees.c:913-939:

dist = s->sym_buf[sx++] & 0xff;
dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8;
...
lc = s->sym_buf[sx++];
if (dist == 0) {
    send_code(s, lc, ltree); /* send a literal byte */
} else {
    code = _length_code[lc];
    send_code(s, code + LITERALS + 1, ltree);
    ...
    dist--; /* dist is now the match distance - 1 */
    code = d_code(dist);
    Assert(code < D_CODES, "bad d_code");
    ...
}

When _tr_tally records a legitimate match, dist - 1 stays safely inside 0..32767, and d_code(dist) stays safely inside 0..29 via _dist_code[0..511]. If compressed bits overwrite an unread symbol in sym_buf, the two bytes of dist become an arbitrary uint16_t up to 65535. Any value in 32769..65535 (0x8001..0xffff) enters the else branch and drives 256 + ((dist - 1) >> 7) to indices 512..767 - an out-of-bounds read up to 256 bytes past _dist_code in .rodata!

If that adjacent .rodata byte exceeds 60, send_code(s, code, dtree) and extra_dbits[code] read out of bounds again on dyn_dtree[61] and extra_dbits[30].

Drag the 16-bit dist slider below past 32,768 to see the exact cascade:

So even if your goal is pure memory safety - proving deflate free of undefined behavior - you cannot dodge proving that the Chaser never catches the Runner.

The Fallacy in deflate.c:465-502

zlib's authors knew this overlay needed a justification, so they wrote a 38-line mathematical proof in deflate.c:465-502. First, they analyze Fixed blocks:

The longest possible fixed-codes length/distance pair is then 31 bits total. [...] As each symbol is consumed, the pointer to the next sym_buf value to read moves forward three bytes. From that symbol, up to 31 bits are written to pending_buf. The closest the written pending_buf bits gets to the next sym_buf symbol to read is just before the last code is written.

For Fixed blocks, the logic is sound: every single symbol frees 24 bits and writes at most 31 bits, so the Chaser gains at most +7 bits per step. Even at memLevel = 1 (B = 128, n = 127), 127 ร— 7 = 889 bits of net catch-up cannot close a 1,024-bit head start. (Minor detail: the comment concludes on line 490 that 139 bits remain because it forgets bi_valid bits and the 3-bit tag, but the margin still holds.)

Then they turn to Dynamic blocks, and the proof breaks:

For Dynamic blocks, the same logic applies, except that the maximum code length is 15 bits for literal/length codes and 15 bits for distance codes. [...] The average length so far is at most 24 bits per symbol, so the Chaser cannot catch the Runner on average.

The flaw is averaging over the whole block. Safety is a prefix property: the Chaser must stay behind B + 3k at every intermediate k, not just at k = n. A block whose total average is โ‰ค 24 bits/symbol can still front-load ten 48-bit matches (gaining 10 ร— 24 = 240 bits) before a long tail of 1-bit literals pulls the average back down. The comment's global average says nothing about that mid-block surge.

Worse, the header H itself - send_all_trees emitting bl_tree + literal/length code-lengths + distance code-lengths - can be thousands of bits before symbol 0 is even read. The comment never bounds H.

Tracking Bits, Not Bytes: S, bi_buf, and put_short

To prove safety, we must model bit-accurate output. C holds pending bits in bi_buf (s->bi_valid tracks how many bits are held) and flushes two bytes (put_short) to pending_buf[pending++] strictly when bi_valid + len > 16. Tracking pending and bi_valid separately through dozens of send_bits calls is painful because pending jumps in 2-byte steps.

Instead, define the total emitted bit count:

Every send_bits(s, val, len) call - whether it flushes two bytes or not! - increases S by literally len. Because put_short flushes 16 bits only when S crosses a multiple of 16 (bi_valid stays in 1..16 after any write), pending is completely determined by S:

At block-flush entry, pending = 0 and bi_valid = v0 โ‰ค 7. After the 3-bit block tag, H bits of dynamic header, and the first k symbols s0, ..., s(k-1), we have S_k = v0 + 3 + H + sum(i=0..k-1) cost(s_i).

Meanwhile, at the end of the block (k = n), compress_block still has to emit the โ‰ค 15-bit END_BLOCK code and byte-align within 4B bytes (block_room). Unifying both prefix safety (S_k โ‰ค 8(B + 3k)) and end-of-block room into one condition (DynamicRoom in trees.c.universal-dynamic.lean) asks for:

Step C: Erasing sym_buf Order (sym_buf โ†’ Freq[])

Notice a crucial structural fact about trees.c: build_tree and build_bl_tree never read sym_buf! They read only the total frequency arrays dyn_ltree[c].Freq and dyn_dtree[d].Freq tallied during Pass 1. If an adversary permutes the n symbols inside sym_buf - moving every expensive match (> 24 bits) to the front and every cheap literal (< 24 bits) to the back - the trees H, E, and cost() stay identical, but the mid-block peak max_k (S_k - 24k) only grows.

So the worst case for prefix safety is sorted-descending order. Bounding that worst case depends only on Freq[], not on input order. Define the block excess:

In one stroke, the heap array sym_buf and the loop index k disappear! Proving compress_block safe for every input order reduces to proving one order-free budget inequality on the trees produced by build_tree:

Step D: Connecting C's Tree Functions to Three memLevel Regimes

Why can't H + E + 25 exceed 8B? Because in build_tree, deep codewords require exponentially large block weight. Trace build_tree (trees.c:627-716) on a tiny example. Suppose you want to push a leaf x (with Freq = 1) down to depth 4. At each step, pqremove pops the two lightest nodes from the min-heap and merges them:

  • Depth 4 โ†’ 3: x (weight 1) merges with a sibling of weight โ‰ฅ 1 โ†’ parent has weight โ‰ฅ 2.
  • Depth 3 โ†’ 2: to avoid merging earlier, the next sibling must weigh โ‰ฅ 1 โ†’ grandparent weighs โ‰ฅ 3.
  • Depth 2 โ†’ 1: the next sibling must weigh โ‰ฅ 2 (since two 1s were available when 1+1 merged!) โ†’ weight โ‰ฅ 5.
  • Depth 1 โ†’ 0: the root's other child must weigh โ‰ฅ 3 โ†’ total tree weight W โ‰ฅ 8 = F_6!

By induction on the min-heap pops in build_tree, our Lean proof establishes that in any unclamped Huffman tree of total weight W, every used leaf of frequency f โ‰ฅ 1 at depth l satisfies:

From here, as B = 2^(memLevel+6) shrinks from 32,768 down to 128, the proof connects to three distinct parts of trees.c:

Regime 1: memLevel 5..9 (B โ‰ฅ 2,048) - Bounding gen_bitlen Clamping

When B โ‰ฅ 2,048, a skewed block can have W > 1,597 and grow a Huffman tree deeper than DEFLATE's 15-bit format cap. In C, gen_bitlen (trees.c:583-593) clamps any depth > 15 down to 15. Clamping breaks the prefix-code Kraft equality (sum 2^(-l_i) > 1), so gen_bitlen runs a repair loop that demotes shallower leaves (bits -> bits + 1) until sum 2^(-l_i) = 1 again. Even accounting for worst-case demotions across all 286 literal/length buckets and 30 distance buckets (trees.c.heap.gbfibpush.lean)

Read on Hacker News ↗ ← Back to News

Comments

No comments yet. Start the discussion.