Building Software
Sections

Contents Section 2, Verification and Evals

Property-Based Testing and Test Quality

Checking invariants across thousands of generated inputs, and measuring whether your tests would actually catch a bug.

Section 2 of 9, subsection 3 of 6. Depth: do. An 8-minute read.

Mistakes to catch in review

  1. Code that passes every hand-written example and fails on an input nobody thought of, such as an empty string, a huge number or combining characters.

  2. High line coverage with weak assertions, so deliberately introduced bugs go unnoticed.

  3. A parser or decoder that crashes or hangs on malformed input.

Let the Computer Choose the Inputs

An agent needs to store a list of tags in a single text column. It writes an encoder, a decoder and four example tests. ["urgent", "billing"] encodes to "urgent,billing" and decodes back, and a single tag round-trips. The coverage report says 100%.

TypeScript
export const encodeTags = (tags: string[]) => tags.join(",");
export const decodeTags = (s: string) => s.split(",");
Two boxes on the left, [] 'no tags' and [""] 'one empty tag', each have an arrow labelled 'encode' into one purple box, "" 'stored'. An arrow labelled 'decode' leads from it to [""] 'decoded'. A note reads: two lists, one string.
An empty list and a list holding one empty tag are both stored as the empty string, so no decoder can tell them apart; split returns one empty tag for both.

This code is broken three ways, and none of the four tests can see it. A tag containing a comma comes back as two tags. An empty list encodes to "", and "".split(",") returns [""], a list with one empty tag. And a list holding one empty tag also encodes to "", so two different lists produce the same stored string.

Every example test was chosen by someone, and whoever chose the inputs brought their blind spots along. An agent that writes tests after reading its own code tends to pick inputs the code already handles. One remedy is to let the computer generate the inputs. A second tool, mutation testing, measures whether a suite would notice a bug at all.

A property is a rule that holds for every input

An example test says: for this input, expect this output. A property says: for every input, this relationship holds. For an encoder and decoder the obvious property is the round trip. Decode what you encoded and you get back exactly what you started with.

A property-based testing library turns that sentence into a test. It generates random inputs, a hundred by default in both fast-check for JavaScript and Hypothesis for Python, checks the property on each one, and reports any input that breaks it.

TypeScript
import { test, expect } from "vitest";
import fc from "fast-check";

test("decoding an encoding gives back the original tags", () => {
  fc.assert(
    fc.property(fc.array(fc.string()), (tags) => {
      expect(decodeTags(encodeTags(tags))).toEqual(tags);
    }),
  );
});

fc.array(fc.string()) is a generator: a recipe for random lists of random strings, including empty lists and empty strings. Run this against the comma version and it fails within a few runs, reporting the empty list.

Patch the decoder to return [] for "" and run again. Now it fails with [""], a list holding one empty tag. No decoder can fix that one, because [] and [""] both encode to "" and the information is gone before the decoder sees it.

Shrinking makes a failure readable

The first random input that breaks a property is usually messy, such as a list of six strings full of punctuation. Reading it tells you little, so when a property fails the library shrinks the input. It tries smaller versions, such as a shorter list, a shorter string or a smaller number, and keeps any version that still fails. It stops when no smaller version fails and reports that one, though the search is best-effort and the result is not guaranteed to be the smallest possible.

A flowchart. 'Random input: a hundred by default' leads to a diamond, 'Property holds?'. 'Yes: next' loops back to the random input; 'no' leads to 'Failing input: usually messy', then down to a diamond, 'Smaller one fails?'. 'Yes' leads to 'Keep it: try smaller again', which loops back to that diamond; 'no' leads down to a purple 'Report: e.g. []'. A note reads: one cause per report.
Random inputs run until one breaks the property. The library then keeps any smaller version that still fails, and reports the input once no smaller version does.

That is how you get [] and [""] instead of a wall of noise. Filter those two lists out of the generator and the next report is [","], a single tag that is just a comma. Each shrunk counterexample points at one cause.

The block below is a small property checker written from scratch, so you can watch all three reports happen. It draws random tag lists from a seeded generator, so every run draws the same lists. It stops at the first list that fails the round trip, then shrinks it by dropping one tag or one character at a time for as long as the smaller list still fails. Change the seed to another whole number from 1 to 2,147,483,646 and the first failing list changes, but the shrunk results stay the same. A seed outside that range can break the generator. Zero, for example, stays zero under multiplication, so every list it draws is empty.

TypeScriptRuns in your browser
const encodeTags = (tags: string[]) => tags.join(",");
const splitDecode = (s: string) => s.split(",");
const patchedDecode = (s: string) => (s === "" ? [] : s.split(","));
const show = (x: unknown) => JSON.stringify(x);

// A seeded random generator, so every run draws the same inputs.
// The seed must be a whole number from 1 to 2147483646.
let seed = 7;
const rand = (n: number) => (seed = (seed * 48271) % 2147483647) % n;
const randomTag = () => Array.from({ length: rand(4) }, () => "ab,"[rand(3)]).join("");
const randomTags = () => Array.from({ length: rand(5) }, randomTag);

// Smaller versions of an input: drop one tag, or drop one character from one tag.
function* smaller(tags: string[]) {
  for (let i = 0; i < tags.length; i++) yield tags.filter((_, j) => j !== i);
  for (let i = 0; i < tags.length; i++)
    for (let c = 0; c < tags[i].length; c++)
      yield tags.map((t, j) => (j === i ? t.slice(0, c) + t.slice(c + 1) : t));
}

function check(decode: (s: string) => string[], skip: string[][] = []) {
  const fails = (tags: string[]) =>
    !skip.some((x) => show(x) === show(tags)) && show(decode(encodeTags(tags))) !== show(tags);
  for (let run = 1; run <= 100; run++) {
    const tags = randomTags();
    if (!fails(tags)) continue;
    let small = tags;
    let shrinking = true;
    while (shrinking) {
      shrinking = false;
      for (const s of smaller(small)) {
        if (fails(s)) { small = s; shrinking = true; break; }
      }
    }
    return `run ${run} failed on ${show(tags)}, shrunk to ${show(small)}`;
  }
  return "100 runs passed";
}

console.log(check(splitDecode));
console.log(check(patchedDecode));
console.log(check(patchedDecode, [[], [""]]));

The fix is a format that cannot be confused, where each tag is prefixed with its length:

TypeScript
export const encodeTags = (tags: string[]) =>
  tags.map((t) => `${t.length}:${t}`).join("");
// ["ab", "", "c,d"] becomes "2:ab0:3:c,d"

The round-trip property now passes. The decoder reads a number, a colon, and then exactly that many characters, so commas and empty tags carry no special meaning.

Malformed input and fuzzing

The round trip only feeds the decoder strings the encoder produced. In production the decoder reads whatever is in the column, including rows written by an older version, edited by hand, or corrupted. So here is a second property: for any string at all, the decoder returns a list or throws a clean decode error. It never crashes with some other error, and it always finishes.

Here is the agent's first length-prefix decoder:

TypeScript
export function decodeTags(s: string): string[] {
  const tags: string[] = [];
  let i = 0;
  while (i < s.length) {
    const colon = s.indexOf(":", i);
    const len = Number(s.slice(i, colon));
    tags.push(s.slice(colon + 1, colon + 1 + len));
    i = colon + 1 + len;
  }
  return tags;
}

Feed it a single space. There is no colon, so colon is -1. s.slice(0, -1) is the empty string, Number("") is 0, and i becomes -1 + 1 + 0, which is 0 again. The loop never moves forward, and the program hangs.

A hang is harder to catch than a crash, because a test that never finishes never reports. Fuzzers handle this by running each input under a time limit. In a property test, the simpler move is to make the loop prove it makes progress, which turns any would-be hang into an error the tool can report and shrink. The corrected decoder validates before it trusts:

TypeScript
export class DecodeError extends Error {}

export function decodeTags(s: string): string[] {
  const tags: string[] = [];
  let i = 0;
  while (i < s.length) {
    const colon = s.indexOf(":", i);
    const prefix = s.slice(i, colon);
    if (colon === -1 || !/^\d+$/.test(prefix)) throw new DecodeError(`bad length prefix at ${i}`);
    const end = colon + 1 + Number(prefix);
    if (end > s.length) throw new DecodeError(`tag at ${i} runs past the end`);
    tags.push(s.slice(colon + 1, end));
    i = end; // end > i, so every pass moves forward
  }
  return tags;
}

test("any string decodes or throws DecodeError", () => {
  fc.assert(
    fc.property(fc.string({ unit: "binary" }), (s) => {
      try {
        decodeTags(s);
      } catch (e) {
        if (!(e instanceof DecodeError)) throw e;
      }
    }),
  );
});

The unit: "binary" option makes the generator draw from the whole range of code points, including strings no encoder would ever write. fast-check's default strings are ASCII only and would miss most malformed input.

A dedicated fuzzer takes the same idea further. Coverage-guided fuzzers such as libFuzzer, AFL and Go's built-in go test -fuzz watch which code paths each input reaches and mutate the inputs that reach new ones. They run for minutes or hours and are the standard tool for parsers that read untrusted data. A property test runs a hundred inputs in milliseconds on every commit, so the two work well together.

The generator decides what you can find

Suppose the agent writes the length prefix as [...t].length to "handle Unicode," which counts code points instead of JavaScript's UTF-16 code units. The decoder still slices by code units. A character outside the Basic Multilingual Plane, such as most emoji, is one code point and two code units. The prefix says 1, so the decoder takes half the character and then throws on the other half.

A prefix 1:, which counts 1 code point, sits beside a large box, one emoji \u{1F600}, 1 code point and 2 code units, holding a first half, code unit 1, and a second half, code unit 2. Numbered arrows run in order: 1, the decoder reads 1; 2, it takes the first half as the tag; 3, it moves to the next code unit; 4, it reads the second half as a length prefix and hits a purple DecodeError, no length prefix here. A note reads: counted one way, sliced another.
The prefix counts the emoji as 1 code point, but the decoder slices 1 code unit. It takes the first half as the tag, then finds the second half where it expects a length prefix and throws.

The round-trip property from the start of the lesson does not catch this. In fast-check 4, fc.string() produces ASCII characters by default, so it never generates an emoji. Give the round-trip test the generator the fuzz property above uses, fc.string({ unit: "binary" }), and it starts failing. That generator draws from the whole range of code points, and the counterexample shrinks to a single character such as U+10000, which is one code point and two code units.

Here are the two encoders side by side, each fed one ASCII list and one emoji, through the validating decoder from the previous section. The ASCII list cannot tell them apart.

TypeScriptRuns in your browser
class DecodeError extends Error {}
function decodeTags(s: string): string[] {
  const tags: string[] = [];
  let i = 0;
  while (i < s.length) {
    const colon = s.indexOf(":", i);
    const prefix = s.slice(i, colon);
    if (colon === -1 || !/^\d+$/.test(prefix)) throw new DecodeError(`bad length prefix at ${i}`);
    const end = colon + 1 + Number(prefix);
    if (end > s.length) throw new DecodeError(`tag at ${i} runs past the end`);
    tags.push(s.slice(colon + 1, end));
    i = end;
  }
  return tags;
}

const byCodePoints = (tags: string[]) => tags.map((t) => `${[...t].length}:${t}`).join("");
const byCodeUnits = (tags: string[]) => tags.map((t) => `${t.length}:${t}`).join("");

const emoji = "\u{1F600}";
console.log("code points:", [...emoji].length, " code units:", emoji.length);

for (const encode of [byCodePoints, byCodeUnits]) {
  for (const tags of [["a,b", ""], [emoji]]) {
    try {
      console.log(encode.name, JSON.stringify(tags), "->", JSON.stringify(decodeTags(encode(tags))));
    } catch (e) {
      console.log(encode.name, JSON.stringify(tags), "->", `DecodeError: ${(e as Error).message}`);
    }
  }
}

The code-point encoder writes 1: in front of the emoji. The decoder takes one code unit, the first half of the emoji, and then finds the second half where it expects the next length prefix.

A property only checks the inputs its generator can produce. When you read a property test, read the generator and ask what it can never produce: empty values, very large numbers, characters outside ASCII, or combining characters. The letter "é" can be one code point or an "e" followed by a combining accent, and the two look identical on screen. If the generator cannot produce the case, the test is silent about it.

Common property shapes

Finding a property is the hard part. A few shapes cover most code:

  • Round trip: decode(encode(x)) equals x. Fits serializers, parsers paired with printers, and compression.
  • Idempotence: applying the function twice gives the same result as applying it once. Fits normalizers, formatters and deduplication.
  • Output invariants: something is true of every output, whatever the input. A sorted list is in order and has the same length as the input; a sanitized string contains only allowed characters.
  • Conservation: a quantity survives the operation. A transfer between two accounts leaves the total unchanged.
  • Reference comparison: a fast implementation gives the same answers as a slow, obviously correct one.

Each shape states a requirement without naming a single expected output, which is why it can be checked on inputs that appear in no example test. When a property fails, the fault can be in the code or in the property. A wrong property is worth finding too, because it means the requirement was misunderstood.

Coverage says what ran

Go back to the agent's original suite. One of its tests looked like this:

TypeScript
test("round trips tags", () => {
  expect(decodeTags(encodeTags(["a", "b"]))).toBeTruthy();
});

It executes every line of both functions, so line coverage is 100%. Coverage measures exactly that: which lines, or with branch coverage which branches, ran during the tests. It says nothing about whether any assertion looked at the result. Low coverage proves some code is untested, and high coverage proves only that the code ran.

Mutation testing measures whether tests notice

Mutation testing asks the question coverage cannot: the tool makes one small change to your code, called a mutant, such as turning < into <=, + 1 into - 1, or a function's return value into an empty array. Then it runs the tests. If some test fails, the mutant is killed. If every test passes, the mutant survived, and you have found a change to the code that no test can see.

Against that test, the mutant that makes decodeTags return [] survives, because an empty array is truthy in JavaScript. The fix is a stronger assertion, toEqual(["a", "b"]), which kills it. Tools include Stryker for JavaScript and TypeScript, PIT for Java, mutmut for Python and cargo-mutants for Rust. Mutation testing runs the suite once per mutant, so teams usually run it on the files a change touched.

The block below runs four mutants of the validating decoder against the weak test and the strong one. Each mutant is written into the code behind a switch, and Stryker does much the same: it builds every mutant into one copy of the code and turns on one per test run.

TypeScriptRuns in your browser
class DecodeError extends Error {}
const encodeTags = (tags: string[]) => tags.map((t) => `${t.length}:${t}`).join("");

// The decoder with four mutants built in; `mutant` switches one on.
function decodeTags(s: string, mutant = "none"): string[] {
  if (mutant === "return []") return [];
  const tags: string[] = [];
  let i = 0;
  while (mutant === "< to <=" ? i <= s.length : mutant === "< to !==" ? i !== s.length : i < s.length) {
    const colon = s.indexOf(":", i);
    const prefix = s.slice(i, colon);
    if (colon === -1 || !/^\d+$/.test(prefix)) throw new DecodeError(`bad length prefix at ${i}`);
    const end = colon + (mutant === "+ 1 to - 1" ? -1 : 1) + Number(prefix);
    if (end > s.length) throw new DecodeError(`tag at ${i} runs past the end`);
    tags.push(s.slice(colon + 1, end));
    i = end;
  }
  return tags;
}

// A test passes if it returns true without throwing.
const passes = (test: () => boolean) => { try { return test(); } catch { return false; } };
const weak = (m: string) => passes(() => Boolean(decodeTags(encodeTags(["a", "b"]), m)));
const strong = (m: string) => passes(() => JSON.stringify(decodeTags(encodeTags(["a", "b"]), m)) === '["a","b"]');

for (const m of ["return []", "< to <=", "+ 1 to - 1", "< to !=="]) {
  const verdict = (t: (m: string) => boolean) => (t(m) ? "survived" : "killed");
  console.log(`${m.padEnd(11)} weak test: ${verdict(weak).padEnd(8)}  strong test: ${verdict(strong)}`);
}

The weak test misses the return [] mutant and the strong test kills it. The other two broken mutants make the decoder throw, so even the weak test catches them. The last one survives both tests because no input makes it behave differently from the original.

A flowchart. 'Mutant: one small change' leads to 'Run the tests', then to a diamond, 'Any test fails?'. 'Yes' leads to 'Killed'. 'No' leads to a purple 'Survived: no test sees it', then to a diamond, 'Input that differs?'. 'One exists' leads to 'Missing test: add it'; 'none can exist' leads to 'Equivalent: ignore it'. A note reads: try to tell them apart.
A mutant that makes any test fail is killed. A survivor is a missing test if some input makes it behave differently from the original, and an equivalent mutant to ignore if no such input can exist.

Read each surviving mutant and decide which kind it is. Most mark an assertion that is missing or too weak. Some are equivalent mutants, changes that cannot alter behavior. In for (let i = 0; i < tags.length; i++), changing < to != is one: i starts at 0 and rises by 1, so it reaches the array length exactly and never passes it. The decoder's while loop is another. Every pass sets i to end, and the decoder throws before end can pass s.length, so i !== s.length stops at the same moment i < s.length does.

To tell the two kinds apart, try to write an input on which the mutant and the original give different results. If one exists, it is a missing test, so add it. If none can exist, ignore the mutant.

Check your understanding

7 questions on this lesson. Pick an answer to see whether it holds and why.

  1. 1An agent added this property for a name normalizer, and it passed 100 runs under fast-check 4. Which of these inputs can the property never have tried?
    TypeScript
    fc.assert(
      fc.property(fc.string(), (name) => {
        expect(normalizeName(normalizeName(name))).toEqual(normalizeName(name));
      }),
    );
    Show the answer

    Answer C. In fast-check 4, fc.string() draws ASCII characters only, so no accent of any kind can appear. The empty string is a tempting answer, but generators favor small values and produce it often. Spaces, digits and punctuation are ASCII too. To reach accents, use fc.string({ unit: "binary" }) or a generator built for that case.

  2. 2An agent stores a list of numbers as one string. A round-trip property over fc.array(fc.integer()) fails. What does the shrunk counterexample show?
    TypeScript
    const encode = (xs: number[]) => xs.join(" ");
    const decode = (s: string) => s.split(" ").map(Number);
    Show the answer

    Answer A. The empty list encodes to the empty string, "".split(" ") returns [""], and Number("") is 0, so [] comes back as [0]. The shrinker keeps trying smaller lists and the empty list is the smallest, so it lands there. [0] is tempting because 0 appears in the bug, but [0] itself round-trips: it encodes to "0" and decodes to [0].

  3. 3A pull request raises branch coverage of parseDate from 60% to 100% by adding one test. The test calls parseDate on twelve date formats and asserts only that no call throws. Which bug can still merge with every test green?
    Show the answer

    Answer D. Coverage records which branches ran, and the only thing this test looks at is whether a call threw. A wrong month is a returned value nobody compared with anything, so it passes. A throwing format is the tempting answer, but that is the one failure this test does check. Full branch coverage rules out a branch that never ran, and a syntax error would fail the run before any test passed.

  4. 4Mutation testing changes >= to > in this function, and both assertions still pass. What should you do?
    TypeScript
    export const isAdult = (age: number) => age >= 18;
    
    test("adults", () => {
      expect(isAdult(30)).toBe(true);
      expect(isAdult(5)).toBe(false);
    });
    Show the answer

    Answer B. The mutant and the original agree on 30 and 5 and disagree only at 18, where 18 > 18 is false. An input exists that tells them apart, so the mutant is a missing test, not an equivalent one. Age 100 gives true under both versions and kills nothing, and the comparison already runs for both inputs.

  5. 5An agent wrote this parser for newline-separated records. What does parseRecords("abc") do?
    TypeScript
    function parseRecords(s: string): string[] {
      const out: string[] = [];
      let i = 0;
      while (i < s.length) {
        const nl = s.indexOf("\n", i);
        out.push(s.slice(i, nl));
        i = nl + 1;
      }
      return out;
    }
    Show the answer

    Answer C. With no newline, indexOf returns -1, so i becomes -1 + 1, which is 0, and the loop starts over. It pushes "ab" forever until memory runs out. ["ab"] is tempting because slice(0, -1) really is "ab", but the loop never ends to return it. A property test over arbitrary strings with a progress check would report and shrink this.

  6. 6This property checks an agent's mySort. Which broken implementation passes it on every input?
    TypeScript
    fc.assert(
      fc.property(fc.array(fc.integer()), (xs) => {
        const out = mySort(xs);
        for (let i = 0; i + 1 < out.length; i++) {
          expect(out[i]).toBeLessThanOrEqual(out[i + 1]);
        }
      }),
    );
    Show the answer

    Answer B. An empty list has no neighbors to compare, so it is in order every time. The property also needs to say the output is a rearrangement of the input, with the same length and the same elements. The default sort() looks like it might slip through, but it compares numbers as strings, so [10, 9] stays [10, 9] and the generator finds a case like that quickly.

  7. 7A team already runs a property test with 100 random inputs on every commit for its image-header parser. What does adding a coverage-guided fuzzer that runs for hours each night give them?
    Show the answer

    Answer D. A coverage-guided fuzzer keeps the inputs that reached new code and mutates them further, so over hours it gets deep into a parser that random inputs rarely pass. It still proves nothing about inputs it never tried. Shrinking is tempting, but property-testing libraries shrink too, and the fast per-commit test stays useful beside the slow nightly run.

You understand it when you can

Drill

An agent wrote slug = s => s.toLowerCase().replace(/ /g, '-').replace(/[^a-z0-9-]/g, '') with eight passing example tests, including 'Hello World' becoming 'hello-world'. Write three properties: a slug contains only [a-z0-9-], never starts or ends with a hyphen, and slugging a slug changes nothing. Without running anything, find an input that breaks each property that can be broken, and explain why the others cannot be.

Topics

Properties and Invariants
Round-trip, idempotence, ordering and conservation properties that must hold for every input.
Generators and Shrinking
Producing varied inputs and reducing any failure to its smallest example, with libraries such as fast-check and Hypothesis as examples.
Fuzzing
Feeding random and malformed input to parsers and interfaces to find crashes and security bugs.
Mutation Testing
Introducing small bugs on purpose to measure whether the tests notice them.
Coverage and Its Limits
What line and branch coverage measure, and why a high number can hide a weak suite.

Further reading

Start here

Short reads

Watch

Books

  • Property-Based Testing with PropEr, Erlang, and Elixir: Find Bugs Before Your Users Do. Fred Hebert, 2019.

    The most thorough book-length treatment of how to think in properties, write custom generators, read shrunk counterexamples and do stateful testing. The ideas carry over directly to fast-check and Hypothesis.

  • The Fuzzing Book. Andreas Zeller, Rahul Gopinath and 3 others, 2024. Free to read online.

    A free, executable textbook that builds random, mutation-based, grammar-based and coverage-guided fuzzers from scratch, and explains what each one finds in malformed-input handling.

  • Introduction to Software Testing. Paul Ammann and Jeff Offutt, 2016, 2nd edition.

    Defines coverage criteria (statement, branch, logic, mutation) formally, making clear what each criterion guarantees and what a high coverage number leaves untested.

Primary sources