Chapter 02
Formats and grammars
How formats are built, how a grammar and constraints describe them, and how to read a control file byte by byte.
A format is an agreement between whoever writes the bytes and whoever reads them. It says which parts exist, in what order, and how to find their boundaries. Before testing a parser, it helps to be able to read its input yourself.
Four common shapes
Chunks
PNG, WAV, and MP4 are sequences of self-describing blocks. Each block starts with a length and a type, so a reader can skip blocks it does not understand. PNG adds a CRC checksum to every chunk. MP4 boxes can contain other boxes, so the structure is a tree.
Offsets and directories
ZIP stores a central directory at the end of the file that points back to each entry. PDF keeps a cross-reference table with the byte offset of every object. A reader jumps around the file instead of reading it front to back, which means the same bytes can be reached in more than one way.
Trees of text
SVG is XML: elements, attributes, and nesting. The parser builds a tree before anything else looks at it.
Lines and tokens
HTTP/1.1, ASCII PLY, and ASCII PNM are text. HTTP has a start line and header lines ending in CRLF. PNM is a list of whitespace-separated numbers. PLY has a header that declares how many records follow. Text formats look simple, but they still carry counts and lengths that the parser has to check.
Grammars and constraints
A grammar describes the shape of valid inputs. Here is a rough grammar for a PNG file:
<png> ::= <sig> <ihdr> <chunk>* <iend> <sig> ::= 89 50 4E 47 0D 0A 1A 0A <chunk> ::= <length:4> <type:4> <data> <crc:4>
The grammar captures the order of the parts, but not the relationships between them. Two rules are missing: the length field must match the size of the data, and the CRC must match the checksum of the type and data. These are constraints. Most real formats need both: a grammar for the structure, and constraints for lengths, counts, checksums, and offsets.
This matters for testing. If you change random bytes in a PNG, you will almost always break a CRC, and a strict decoder will reject the file at the first chunk. The interesting code behind that check is never reached. Generators that know the grammar and the constraints, such as Fandango, can produce inputs that pass these checks and still vary the parts that matter.
Read the controls
Each format in Parsarium has small valid control files. Pick one below, look at the highlighted bytes, and answer the question. The answer shows what a real parser reported for that file.
Key ideas
- Formats come in a few shapes: chunks, offsets and directories, trees of text, and lines of tokens.
- A grammar describes the order and nesting of parts. Constraints describe how parts relate: lengths, counts, checksums, offsets.
- Random mutations usually break a constraint, so a strict parser rejects the input before reaching interesting code.
- Generators that know both the grammar and the constraints can produce inputs that pass these checks and still vary what matters.
Check yourself
Answer all five to see your score
In a PNG chunk, which bytes does the CRC cover?
- The length, the type, and the data
- The type and the data
- Only the data
The PNG specification computes the CRC over the chunk type and the chunk data. The length field is not included.
Why do random byte flips rarely reach deep code in a PNG decoder?
- Most flips break a CRC, and a strict decoder rejects the chunk.
- PNG decoders ignore changed bytes.
- PNG files are too small to mutate.
A single flipped byte in a chunk invalidates its checksum. The decoder stops at the first check, and the code after it never runs.
Which of these can a grammar alone not express?
- The order of the parts
- That a length field equals the size of the data that follows
- Which parts can repeat
Order, nesting, and repetition are what grammars do well. Relationships between values, such as lengths and checksums, need constraints.
Which format is usually read starting from its end?
- WAV
- ZIP
- ASCII PNM
A ZIP reader looks for the end-of-central-directory record at the end of the file, then follows it to the central directory and the entries.
An ASCII PNM file starts with P3 2 1 255. What do 2 and 1 mean?
- Width and height
- Channels and bit depth
- Major and minor version
P3 selects ASCII RGB, then come the width and height, then the maximum sample value, then the samples.
Exercises
Exercise 2.1Warm-up
Answer all ten questions in the byte inspector above, one per format. For each one, find the highlighted bytes in the hexdump and say what part of the format they belong to.
Hint
The ASCII column on the right of the dump often makes the structure easier to see, especially for text formats and chunk types.
Solution
The answers are revealed in the inspector. The point of the exercise is the second step: being able to say, for each format, where its structure starts and what tells the reader how much to read next.
Exercise 2.2Practice
Change the width in the PNG control from 2 to 3. Make two versions: one that keeps the old CRC, and one with the CRC fixed. Then run both through Pillow.
python3 - <<'EOF'
import os, struct, zlib
data = bytearray(open(os.path.join(os.environ["PARSARIUM"], "controls/png/red-green.png"), "rb").read())
data[16:20] = struct.pack(">I", 3) # IHDR width: 2 -> 3
open("wide-old-crc.png", "wb").write(data)
data[29:33] = struct.pack(">I", zlib.crc32(data[12:29])) # CRC over type + data
open("wide-new-crc.png", "wb").write(data)
EOF
$ parsarium run png python pillow wide-old-crc.png --results runs/wide-old $ parsarium run png python pillow wide-new-crc.png --results runs/wide-new
Compare stdout_tail and stderr_tail in the two receipts. Which check stopped the first file? How far did the second one get?
Hint
IHDR starts at offset 8: four bytes of length, four of type (offsets 12 to 15), thirteen of data (16 to 28), and four of CRC (29 to 32). The width is the first four data bytes.
Solution
The first file fails the IHDR checksum, so a strict decoder stops there. The second file passes that check and reaches the image data, where it finds fewer pixels than the header promises. What happens next is the decoder's choice: report an error, fill the missing pixels, or return a partial image. The receipt shows which one Pillow makes. Keep wide-new-crc.png; chapter 6 sends it to every PNG parser.
Exercise 2.3Challenge
Write a grammar and the constraints for ASCII PNM in P3 form, precise enough that a generator could produce valid files from it. Then list three ways to break a constraint while keeping the grammar valid.
Hint
Start from the control: P3, width, height, maximum value, then the samples. Think about how many samples there must be and what range each one can take.
Solution
<pnm> ::= "P3" <ws> <width> <ws> <height> <ws> <maxval> (<ws> <sample>)+ <ws>? <width> ::= <digits> <height> ::= <digits> <maxval> ::= <digits> <sample> ::= <digits>
Constraints: the number of samples equals 3 × width × height; every sample is at most maxval; maxval is between 1 and 65535. Grammar-valid but constraint-breaking inputs: one sample too few or too many; a sample larger than maxval; a width and height whose product overflows a 32-bit integer. Each of these tests a check the parser should make.