Robust Parsing

Binary File Formats in Practice

Chapter 9 · Robust Parsing

Every parser in this course so far has been fed files it wrote itself. Real files are not so polite. They get cut short by a failed download, damaged by a bad disk, written by buggy programs, or built on purpose to break the reader. A parser that is correct for good input and unpredictable for bad input is only half finished. This chapter collects the defences that Binary File Formats in Practice 8 began: a single checked gate for reading, limits on counts and sizes, protection from decompression bombs and pointer loops, and a small fuzzer that proves the parser fails cleanly.

What was run

Every snippet and solution in this chapter was executed, and the output shown in the comments is what Python printed. Everything is done in memory, so nothing is left behind. The snippets build on one another: run them in order in one session.

Every Number in the File Is a Claim

The core idea is simple: nothing read from a file is known to be true. A length, a count, an offset, a version, even a "this record is 12 bytes" are only statements the file makes about itself. Robust parsing means checking each statement against what you can actually see before acting on it. The failures fall into a few families:

Problem	Example	Defence
Truncation	The file ends in the middle of a field	Check bytes remaining before every read
Lying length	A record claims more bytes than the file has	Compare the length with the bytes that remain
Lying count	"4 billion items" in a 20-byte file	A fixed limit, and a check that the items could fit
Expansion	A tiny compressed stream that inflates to gigabytes	Cap the output size while decompressing
Loops and depth	An offset that points back at itself; records nested thousands deep	Visited set, hop limit, depth limit
Bad content	Invalid UTF-8, an unknown version	Validate and reject with a clear message
Leftovers	Extra bytes after the last record	Decide: reject, or skip on purpose

One Gate for Every Read

The easiest way to forget a check is to scatter reads through the code. Instead, put them behind one small class whose only job is to hand out bytes safely, and make it raise one error type for every kind of bad input. Callers then catch a single FormatError rather than a mixture of whatever Python happens to raise.

import struct, zlib

class FormatError(ValueError):
    """The input is not a valid file. Raised for every kind of bad input."""

class Reader:
    def __init__(self, buf):
        self.buf = bytes(buf)
        self.pos = 0

    def remaining(self):
        return len(self.buf) - self.pos

    def take(self, n):
        if n < 0 or n > self.remaining():
            raise FormatError(f"need {n} bytes at offset {self.pos}, {self.remaining()} left")
        chunk = self.buf[self.pos:self.pos + n]
        self.pos += n
        return chunk

    def unpack(self, fmt):
        st = struct.Struct(fmt)
        return st.unpack(self.take(st.size))

r = Reader(b"\x01\x02\x03")
print(r.unpack("<H"), r.remaining())               # (513,) 1
try:
    r.unpack("<I")
except FormatError as e:
    print(e)                                  # need 4 bytes at offset 2, 1 left
try:
    r.take(-1)
except FormatError as e:
    print(e)                                  # need -1 bytes at offset 2, 1 left
print(b"abc"[5:9], b"abc"[5:9] == b"")      # b'' True
try:
    b"abc"[5]
except IndexError as e:
    print("IndexError:", e)               # IndexError: index out of range
    

Three details earn their place here. The check is n > remaining before slicing, because Python slicing never complains: asking for bytes past the end quietly returns a shorter, even empty, result, and the parser carries on with garbage. A negative request is refused too, since buf[pos:pos + n] with a negative n would walk backwards. And the message carries the offset and the shortfall, which turns "invalid file" into something you can debug with a hex dump from Binary File Formats in Practice 1.

Indexing is the opposite trap: buf[5] past the end raises IndexError, which has nothing to do with your format and would escape a caller expecting FormatError. Routing everything through take avoids both.

Counts and Sizes Are Claims Too

A count field is the classic way to make a program allocate far more than the file justifies. Suppose a format starts with a 4-byte record count, and a hostile file says four billion. A parser that builds a list of that size, or loops that many times before noticing the data has run out, wastes huge amounts of memory or time. Two cheap checks stop it. First, a hard limit chosen by you. Second, a feasibility test: if each record needs at least a minimum number of bytes, the count cannot exceed remaining // minimum.

# u32 count, then count x (u16 id, u8 name length, name bytes)
MIN_RECORD = 3
MAX_RECORDS = 1000

def parse_list(buf):
    r = Reader(buf)
    (count,) = r.unpack("<I")
    if count > MAX_RECORDS:
        raise FormatError(f"count {count} over limit {MAX_RECORDS}")
    if count * MIN_RECORD > r.remaining():
        raise FormatError(f"count {count} cannot fit in {r.remaining()} bytes")
    out = []
    for _ in range(count):
        ident, n = r.unpack("<HB")
        try:
            name = r.take(n).decode("utf-8")
        except UnicodeDecodeError as e:
            raise FormatError(f"bad UTF-8 at offset {r.pos - n}") from e
        out.append((ident, name))
    return out

good = struct.pack("<I", 2) + struct.pack("<HB", 7, 3) + b"Ada" + struct.pack("<HB", 8, 2) + b"Bo"
print(parse_list(good))                       # [(7, 'Ada'), (8, 'Bo')]
for label, bad in [
    ("huge count", struct.pack("<I", 4_000_000_000) + b"xx"),
    ("count too big for data", struct.pack("<I", 500) + good[4:]),
    ("cut name", good[:-1]),
    ("bad utf-8", struct.pack("<I", 1) + struct.pack("<HB", 1, 2) + b"\xff\xfe"),
]:
    try:
        parse_list(bad)
    except FormatError as e:
        print(label, "->", e)
# huge count -> count 4000000000 over limit 1000
# count too big for data -> count 500 cannot fit in 11 bytes
# cut name -> need 2 bytes at offset 13, 1 left
# bad utf-8 -> bad UTF-8 at offset 7
    

Notice that the same check appears in different clothes everywhere: a length against the bytes left, a count against the bytes left, a decode failure turned into the shared error type. The last one uses raise ... from e so the original exception is kept as the cause while callers still catch only FormatError.

Choosing Limits

A limit is a promise about the largest thing your program will accept. Pick them on purpose and write them down next to the format:

Total file size. If you read the whole file into memory, refuse files over a size you can afford before reading them (check os.path.getsize or read at most the limit plus one byte).
Item counts and string lengths. Far below what the length field could express. A 4-byte length can say four gigabytes; a name field rarely needs more than a few hundred bytes.
Nesting depth. A small number, such as the 8 used in Binary File Formats in Practice 8. Python's default recursion limit is 1000 frames (check), so a hostile file nested deeper than that would otherwise crash the parser with a RecursionError rather than a clean rejection.
Total work. Loops over records should have an upper bound that does not depend only on the file's own claims.
Decompressed size. See the next section.

Decompression Bombs

Compression makes a particularly nasty lie possible, because the input is tiny but the output is not. A run of zeros compresses extremely well: fifty million zero bytes squeeze into about 48 thousand, a ratio above a thousand to one. A parser that calls zlib.decompress(data) on untrusted input will happily build the full fifty million bytes (and a determined attacker can do far worse). The fix is to decompress with a cap using a decompressor object, which accepts a max_length and stops there:

bomb = zlib.compress(b"\x00" * 50_000_000, 9)
print(len(bomb))                              # 48610

def inflate(data, max_out):
    d = zlib.decompressobj()
    try:
        out = d.decompress(data, max_out + 1)
    except zlib.error as e:
        raise FormatError(f"corrupt stream: {e}") from e
    if len(out) > max_out:
        raise FormatError(f"output over {max_out} bytes")
    if not d.eof:
        raise FormatError("stream is cut short")
    return out

print(len(inflate(zlib.compress(b"hello" * 100), 1000)))   # 500
for label, data in [("bomb", bomb), ("cut", zlib.compress(b"hello" * 100)[:-4])]:
    try:
        inflate(data, 1_000_000)
    except FormatError as e:
        print(label, "->", e)
# bomb -> output over 1000000 bytes
# cut -> stream is cut short
    

Asking for max_out + 1 bytes is the trick: if more than max_out come back, the stream wanted to produce more than you allow, and you can refuse without ever having held the whole thing. The eof flag then separates a stream that genuinely ended from one that was cut off. The same care applies to the PNG chunk data from Binary File Formats in Practice 5, whose image data is compressed: a decoder that trusts the header's width and height to size its buffers inherits the same problem.

Offsets, Loops and Pointer Chains

Some formats do not store records one after another; they store offsets that say where the next thing lives. An offset is another claim, with a new way to fail: it can point outside the file, or back at something already visited, which makes a loop. A parser that follows "next" pointers until it sees an end marker will spin forever on a file whose chain has no end.

def parse_chain(buf, max_hops=16):
    # each node: u8 value, u16 offset of the next node (0xFFFF = end)
    seen, pos, values = set(), 0, []
    while pos != 0xFFFF:
        if pos in seen:
            raise FormatError(f"loop: offset {pos} visited twice")
        if len(seen) >= max_hops:
            raise FormatError("chain too long")
        seen.add(pos)
        if pos + 3 > len(buf):
            raise FormatError(f"node at {pos} is outside the data")
        v, nxt = struct.unpack_from("<BH", buf, pos)
        values.append(v)
        pos = nxt
    return values

ok = bytes([10, 3, 0]) + bytes([20, 0xFF, 0xFF])
loop = bytes([10, 3, 0]) + bytes([20, 0, 0])
far = bytes([10, 99, 0])
print(parse_chain(ok))                        # [10, 20]
for label, b in [("loop", loop), ("far", far)]:
    try:
        parse_chain(b)
    except FormatError as e:
        print(label, "->", e)
# loop -> loop: offset 0 visited twice
# far -> node at 99 is outside the data
    

The visited set catches a true loop at once; the hop limit is a second line of defence that also bounds a long but finite chain. Both are cheap, and a loop-free format that "never" produces cycles still deserves them, because the reader cannot know the writer was honest.

Checksums Detect Accidents, Not Attackers

A CRC, like the one on each PNG chunk in Binary File Formats in Practice 5, is excellent at noticing accidental damage: a flipped bit, a truncated transfer. It does nothing against someone who changes the data and recomputes the checksum, because a CRC has no secret.

payload = b"hello world"
framed = payload + struct.pack("<I", zlib.crc32(payload))

def check(framed):
    body, (crc,) = framed[:-4], struct.unpack("<I", framed[-4:])
    if zlib.crc32(body) != crc:
        raise FormatError("checksum mismatch")
    return body

print(check(framed))                          # b'hello world'
flipped = bytes([framed[0] ^ 1]) + framed[1:]
try:
    check(flipped)
except FormatError as e:
    print(e)                                  # checksum mismatch
forged = flipped[:-4] + struct.pack("<I", zlib.crc32(flipped[:-4]))
print(check(forged))                          # b'iello world'
    

So a checksum is a good first filter for corruption, but it never replaces the structural checks above: a file with a valid CRC can still hold a lying length. Protection against deliberate tampering needs a keyed construction such as a message authentication code or a digital signature, which is outside this course.

Prove It: Break Your Own Files

Careful code is a belief; a test is evidence. The cheapest useful test for a parser is a small fuzzer: take a valid file, damage it in every simple way, and check that the parser either accepts the result or rejects it with FormatError. Anything else, whether struct.error, IndexError, RecursionError or a hang, is a bug. The simplest damage is to cut the file at every possible length and to overwrite each byte with a few extreme values:

def parse_tlv(buf, depth=0):
    if depth > 8:
        raise FormatError("nested too deeply")
    r = Reader(buf)
    out = []
    while r.remaining():
        t, n = r.unpack("<BH")
        v = r.take(n)
        out.append((t, parse_tlv(v, depth + 1) if t == 0x10 else v))
    return out

def tlv(t, v):
    return struct.pack("<BH", t, len(v)) + v

doc = tlv(0x10, tlv(1, b"Bo") + tlv(0x10, tlv(1, b"Ada") + tlv(2, b"\x24"))) + tlv(1, b"top")
print(len(doc), parse_tlv(doc))
# 27 [(16, [(1, b'Bo'), (16, [(1, b'Ada'), (2, b'$')])]), (1, b'top')]

def fuzz(parser, doc):
    results = {"ok": 0, "rejected": 0}
    crashes = []
    cases = [doc[:i] for i in range(len(doc))]
    for i in range(len(doc)):
        for val in (0x00, 0xFF, doc[i] ^ 0x80):
            cases.append(doc[:i] + bytes([val]) + doc[i + 1:])
    for case in cases:
        try:
            parser(case)
            results["ok"] += 1
        except FormatError:
            results["rejected"] += 1
        except Exception as e:
            crashes.append((type(e).__name__, case))
    return len(cases), results, crashes

n, res, crashes = fuzz(parse_tlv, doc)
print(n, res, len(crashes))                   # 108 {'ok': 55, 'rejected': 53} 0
    

Of the 108 damaged files, 55 still parse (a changed value byte is still a valid value, and some cuts land exactly between records) and 53 are rejected cleanly. None crash. Now the same test on a sloppy parser that reads lengths without checking them:

def sloppy(buf):
    pos, out = 0, []
    while pos < len(buf):
        t = buf[pos]
        (n,) = struct.unpack_from("<H", buf, pos + 1)
        out.append((t, buf[pos + 3:pos + 3 + n]))
        pos += 3 + n
    return out

n, res, crashes = fuzz(sloppy, doc)
print(n, res, len(crashes), sorted({c[0] for c in crashes}))
# 108 {'ok': 104, 'rejected': 0} 4 ['error']
    

The sloppy parser has two failures, and the second is the worse. Four cases crash with struct.error (a header cut short). But it accepts 104 of 108, including many it should have refused: a record whose length overruns the data silently becomes a shorter record, so a damaged file produces plausible but wrong results with no warning. Silent acceptance of bad data is more dangerous than a crash, because nobody notices.

Where the stakes are higher

In Python the cost of these mistakes is usually an exception or wasted memory. In languages without bounds checking, such as C, a lying length can read or write beyond a buffer, and that is a well-known source of serious security flaws (check). The habits are the same in every language; only the consequences differ.

A Robust Parser Checklist

One gate. All reads go through a helper that checks bytes remaining. No raw indexing of untrusted lengths.
One error type. Convert struct.error, UnicodeDecodeError and zlib.error into FormatError so callers handle one thing.
Check before you allocate or loop. Counts and sizes against a limit and against what could fit.
Cap expansion. Decompress with an output limit, and compare the declared size with the real one.
Bound the structure. Depth limit, hop limit, visited set.
Validate content. Magic, version, text encoding, reserved fields that must be zero.
Decide about leftovers. Trailing bytes are either an error or an intentional extension point; never an accident.
Report the offset. Every error message says where in the file it happened.
Fuzz it. Truncate and mutate a good file, and require that only FormatError comes out.

Challenges

Exercise 1

Write a parser for a small inventory file: the magic bytes INV1, a 1-byte version (only 1 is accepted), a 2-byte little-endian item count, then that many items, each a 1-byte name length, the UTF-8 name (never empty), a 4-byte quantity and a 2-byte price. Build it on a checked reader. Enforce a file-size limit of 65,536 bytes, a limit of 100 items, a check that the count could fit in the bytes left, and a refusal of trailing bytes. Show a good file parsed, an empty list, and eleven bad inputs each rejected with its own clear message.

📄 View solution

Exercise 2

Write a safe loader for a blob made of a 4-byte little-endian declared size followed by a zlib stream. Refuse a declared size over 1,000,000 before decompressing, cap the decompressor's output, and check the real size equals the declared size. Show a good blob, a 50-million-byte bomb (with an honest size and with a lying one), a size that is too small, too large and absurd, and a cut stream, trailing bytes, corrupt data, non-zlib data and a blob too short for its size field. Every failure must be a FormatError.

📄 View solution

Exercise 3

Build a fuzz harness that cuts a seed file at every length and replaces each byte with 0x00, 0xFF and the byte with its top bit flipped (skipping replacements equal to the original), counting accepted, rejected and crashed cases and recording the first case for each crash type. Run it against a careful nested type-length-value parser and a sloppy one, and finish by feeding both a record nested 50 levels deep.

📄 View solution

Quick Reference

Principle: every length, count, offset and size in a file is a claim to verify
Slicing never fails: buf[a:b] past the end returns less; indexing raises IndexError; check first
Checked reader: take(n) refuses n < 0 or n > remaining and names the offset
One error type: wrap struct.error, UnicodeDecodeError, zlib.error with raise FormatError(...) from e
Counts: hard limit, plus count * min_size <= remaining
Bombs: zlib.decompressobj().decompress(data, max_out + 1), then check length and eof
Loops and depth: visited set, hop limit, recursion depth limit
CRC: catches accidents, not tampering
Fuzz: truncate at every length, mutate every byte; only FormatError is acceptable

Coming next

Binary File Formats in Practice 10 is the capstone: you design a tiny container format of your own, write the reader and writer, apply the defences from this chapter, and test it with round trips and a fuzzer.