Property Testing, Fuzzing, and Oracles
Prerequisites: S3 testing; S4 parser or interpreter; lesson 2 or the networking frame decoder. Budget: 30-45 hours. Outcome: discover a defect with generated inputs, minimize it, and explain what your oracle can detect.
Diagnostic
State the input domain and expected outcome of one existing function. Explain why “the program did not crash” is a weak correctness oracle. If expected behavior cannot be described, write the contract before generating more tests.
Choose an oracle before a generator
A property specifies a relation that should hold across many valid inputs. A codec might satisfy decode(encode(x))=x over its supported values. A sorter must return ordered output and preserve the input multiset; ordering alone permits an implementation that always returns an empty list.
Differential testing compares implementations of the same contract. Disagreement identifies a question, not automatically which implementation is wrong. Metamorphic testing applies a transformation with a known relation: permuting the inputs to an order-insensitive sum should preserve the exact result under the declared arithmetic model. Floating-point arithmetic requires additional care because reassociation changes rounding.
Fuzzing explores inputs, often emphasizing unusual boundaries or feedback such as coverage. Coverage describes execution reached; it does not prove that results were checked correctly.
Worked example: a bad round-trip property
An encoder and decoder both incorrectly reverse character order. The round trip can still recover the original text, so the shared bug survives. Add a known-format example from an independent specification or compare against an independently implemented codec.
Similarly, a parser that accepts malformed records is not necessarily caught by generating only valid records. Use separate valid and invalid input strategies, with clear expected rejection behavior. Avoid classifying an unexpected exception as an ordinary rejection if it represents a real defect.
Guided assignment
Use the lesson 2 language or S5 frame decoder as your target. Start with a deterministic seed and bounded size. Generate valid trees or frames, then introduce boundary mutations: truncated header, excessive declared length, unknown token, deeply nested structure, or wrong type.
Keep at least three independent checks: a known-answer example, a structural property, and a differential or metamorphic relation. Inject a plausible defect such as losing bytes after the first complete frame or substituting a shadowed variable. Confirm that your test system detects it.
Minimize a failing input while preserving the same failure predicate. Save the original, minimized case, seed, environment, failure explanation, fix, and regression test. For a resource-exhaustion target, set explicit time and memory budgets and distinguish a test-harness timeout from a semantic rejection.
Acceptance: find the injected defect; reduce it to an explanatory case; demonstrate failure before and success after the fix; preserve at least one oracle that would catch a shared encoder/decoder mistake. A tool printing “millions of cases” does not satisfy the gate on its own.
Independent transfer
A parser's grammar is updated to permit a previously invalid token. Which tests should change? Check: update the specification and affected generation/rejection expectations; do not blindly delete every failing test or retain an obsolete rejection rule.
Read test generation, grammar-based input, and reduction topics in The Fuzzing Book. The local static-analysis and event-driven fuzzing papers become seminar candidates after you have a working oracle. Defend the untested properties and remaining limits under the rubric.