deflate.InflateStream `bits_left` unsafety

[squeek502]

With certain inputs, it's possible for the bits_left field of InflateStream to either cause:

thread 445840 panic: integer cast truncated bits
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:276:48: 0x22f215 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).peekBits (fuzz-deflate-debug)
                self.bits |= @as(u32, byte) << @intCast(u5, self.bits_left);
                                               ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:491:38: 0x2305e6 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).decode (fuzz-deflate-debug)
                _ = try self.peekBits(code_len);
                                     ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:368:47: 0x22db87 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).dynamic (fuzz-deflate-debug)
                const symbol = try self.decode(&lencode);
                                              ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:554:50: 0x20f8b3 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).step (fuzz-deflate-debug)
                            2 => try self.dynamic(),
                                                 ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:635:30: 0x20f109 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).read (fuzz-deflate-debug)
                try self.step();
                             ^

or

thread 445832 panic: integer overflow
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:289:28: 0x22f351 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).discardBits (fuzz-deflate-debug)
            self.bits_left -= bits;
                           ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:284:29: 0x22d749 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).readBits (fuzz-deflate-debug)
            self.discardBits(bits);
                            ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:461:60: 0x22ebb2 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).codes (fuzz-deflate-debug)
                            @intCast(u16, try self.readBits(DEXT[distance_symbol]));
                                                           ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:559:44: 0x20f973 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).step (fuzz-deflate-debug)
                        if (!try self.codes(self.hlen, self.hdist)) {
                                           ^
/home/ryan/Programming/zig/zig/build/lib/zig/std/compress/deflate.zig:635:30: 0x20f109 in std.compress.deflate.InflateStream(std.io.reader.Reader(*std.io.fixed_buffer_stream.FixedBufferStream([]u8),std.io.fixed_buffer_stream.ReadError,std.io.fixed_buffer_stream.FixedBufferStream([]u8).read)).read (fuzz-deflate-debug)
                try self.step();
                             ^

This was found by fuzzing std.compress.deflate.inflateStream().reader().readAllAlloc().

Here's some tests that trigger both crashes with minimized inputs:

const std = @import("std");

test "integer overflow" {
    const data = "\x950000";
    try testInflate(data);
}

test "intCast truncate" {
    const data = "\x950\x00\x0000000";
    try testInflate(data);
}

fn testInflate(data: []const u8) !void {
    const allocator = std.testing.allocator;

    const reader = std.io.fixedBufferStream(data).reader();
    var window: [0x8000]u8 = undefined;
    var inflate = std.compress.deflate.inflateStream(reader, &window);

    var inflated = inflate.reader().readAllAlloc(allocator, std.math.maxInt(usize)) catch {
        return;
    };
    defer allocator.free(inflated);
}

And here's a zip of a larger set of inputs that will trigger the crashes (potentially in different ways):

inflate-stream-crash-inputs.zip

[squeek502]

This might actually be caused by failing to reject inputs before these overflows/truncations happen.

I've set up a fuzzer that compares the inflated outputs between Zig's standard library and puff.c, and it's hitting inputs where the puff.c implementation returns an error but the Zig implementation does not. Running the overflow/truncation inputs from the OP through puff also gives a normal error code rather than hitting undefined behavior or returning an inflated output, so I'm thinking Zig's not returning errors when it should in certain cases and that's what's causing it to hit the checked illegal behavior here.

[mattbork]

The integer overflow is due to InflateStream.readBits, which does

const val = self.peekBits(bits);
self.discardBits(bits);
return val;

The problem is that errors from peekBits (like the underlying reader's EndOfStream) are held in val rather then being immediately returned. This means discardBits can be called even if peekBits has failed and the bit buffer has fewer than bits many bits in it, thus underflowing bits_left. Using try on the call to peekBits corrects this.

The truncated cast is a little more involved. The test that triggers it starts a block with dynamic Huffman codes but then marks all the symbols in the code length alphabet as unused (i.e., the length of each symbol is 0). When Huffman.construct realizes it's building an empty table, it returns early, leaving every field of the Huffman struct other than count uninitialized. In particular, min_code_len is still maxInt(u16). Thus, the first time InflateStream.decode is called with this table, it will try to peek 65535 bits, leading bits_left to eventually exceed the size of a u5. Then the @intCast(u5) used in shifting bits into the bit buffer will panic.

The fix is to have decode return the OutOfCodes error immediately when the Huffman table is empty. It's not enough to make constructing an empty Huffman table an error because in the (somewhat pathological) case of a dynamic block that immediately uses the end of data symbol, the Huffman table for distances is never used and can be empty without error. The puff.c implementation indeed accepts such a block without error.

With these fixes, all of the larger set of crashing inputs properly return errors, mostly EndOfStream with a few OutOfCodes errors. I'll put together a PR soon.

[squeek502]

@mattbork I've also been investigating and have come to similar conclusions. I'm not familiar with deflate, though, so I've been trying to learn as I go; my solutions are more of a 'this seems to work' rather than coming from a place of understanding.

My set of changes so far:

• Move self.prefix_lut = mem.zeroes(@TypeOf(self.prefix_lut)); to the top of Huffman.construct so that it always gets initialized, and then also set last_code/last_index/min_code_len to 0. Also make self.min_code_len get set to 0 instead of math.maxInt(u16) if all code lengths are 0.
• Use try self.peekBits in readBits as you said

Here's the diff:

diff --git a/lib/std/compress/deflate.zig b/lib/std/compress/deflate.zig
index b443c2971..ceb2becdc 100644
--- a/lib/std/compress/deflate.zig
+++ b/lib/std/compress/deflate.zig
@@ -46,13 +46,18 @@ const Huffman = struct {
     min_code_len: u16,
 
     fn construct(self: *Huffman, code_length: []const u16) !void {
+        // Set everything to valid defaults up-front, as it's possible to return early
+        self.prefix_lut = mem.zeroes(@TypeOf(self.prefix_lut));
+        self.last_code = 0;
+        self.last_index = 0;
+        self.min_code_len = 0;
+
         for (self.count) |*val| {
             val.* = 0;
         }
 
-        self.min_code_len = math.maxInt(u16);
         for (code_length) |len| {
-            if (len != 0 and len < self.min_code_len)
+            if (len != 0 and (self.min_code_len == 0 or len < self.min_code_len))
                 self.min_code_len = len;
             self.count[len] += 1;
         }
@@ -86,8 +91,6 @@ const Huffman = struct {
             }
         }
 
-        self.prefix_lut = mem.zeroes(@TypeOf(self.prefix_lut));
-
         for (code_length) |len, symbol| {
             if (len != 0) {
                 // Fill the symbol table.
@@ -280,7 +283,7 @@ pub fn InflateStream(comptime ReaderType: type) type {
             return self.bits & mask;
         }
         fn readBits(self: *Self, bits: usize) !u32 {
-            const val = self.peekBits(bits);
+            const val = try self.peekBits(bits);
             self.discardBits(bits);
             return val;
         }

[mattbork]

That works but the path through InflateStream.decode is perhaps not obvious in the case of an empty alphabet. And because of the readBits(PREFIX_LUT_BITS) in decode, an EndOfStream error may be returned when a OutOfCodes error would be more correct. For example, I think testInflate("\x95\x00\x00\x00") should return OutOfCodes because there are still 3 bits left when it tries to read the first literal code length but the code length alphabet is empty. I think an explicit check in decode may be better, like

@@ -487,6 +487,8 @@ pub fn InflateStream(comptime ReaderType: type) type {
             var code_len = h.min_code_len;
+            if (code_len == 0)
+                return error.OutOfCodes;
             while (true) {
                 _ = try self.peekBits(code_len);

Do you want to put together the PR or should I?

[squeek502]

Do you want to put together the PR or should I?

Go right ahead. I'll likely create another issue afterwards with some possible error correctness problems (where puff.c returns an error but Zig's implementation does not or vice versa).