Programming Language Theory
Property-based Testing
QuickCheck found a bug in the bzip2 compressor that had been lurking for ten years. The test: compress(decompress(x)) == x. It ran, found a counterexample, and shrinking reduced it to 20 bytes. One test, one property, and a long-standing bug fell out.
- **Google OSS-Fuzz**: 700+ open source projects fuzzed 24/7. Over 10,000 vulnerabilities found in OpenSSL, libpng, Chromium, FFmpeg.
- **Rust ecosystem**: cargo-fuzz is used on rustc, serde, and the nom parser. rustc fuzzes itself, finding panics in the borrow checker.
- **Erlang QuickCheck (Quviq)**: the commercial version. Found bugs in Dets (Erlang persistent storage), RabbitMQ, and Riak. These are production distributed systems.
QuickCheck
QuickCheck (Haskell, 1999) is a framework for property-based testing. Instead of concrete examples, you describe properties that must hold for ALL inputs. QuickCheck then generates hundreds of random test cases automatically.
What is the core difference between property-based testing and example-based testing?
Shrinking
Shrinking minimizes a counterexample. If QuickCheck finds a failure on input [42, -7, 1000, 0, -3], shrinking tries to find a minimal failing example. Maybe the bug reproduces on [-7, 0]. This makes debugging orders of magnitude easier.
Hedgehog (Haskell) uses integrated shrinking: generators automatically include shrinking without a separate implementation. This eliminates a whole class of problems with custom generators in QuickCheck.
Why is shrinking critical to making property-based testing practical?
Generators
A generator (Gen a) describes how to randomly create a value of type a for testing. Good generators cover edge cases (0, -1, max_int), invalid inputs, and special values. Generators compose in a monadic style.
Why do good generators explicitly include edge cases (0, maxInt, empty list)?
Fuzzing
Fuzzing automatically generates inputs to find crashes, memory errors, and hangs. Coverage-guided fuzzing (AFL, libFuzzer) uses execution-coverage feedback to direct the search. Google OSS-Fuzz has found over 10,000 vulnerabilities.
Fuzzing versus property-based testing: fuzzing hunts crashes, undefined behavior, and memory errors without requiring you to formulate properties. Property-based testing checks business logic. Google Chromium, Firefox, and OpenSSL are continuously fuzzed. OSS-Fuzz runs 24/7 on 700+ projects.
Property-based testing takes a lot of effort to formulate properties. Easier to write unit tests
Often simple universal properties suffice: encode/decode roundtrip, idempotency, commutativity, monotonicity.
encode(decode(x)) == x is a one-liner that exercises the entire serialization layer. It is equivalent to hundreds of manual tests. The time invested pays off when edge cases surface.
What is coverage-guided fuzzing and why is it more effective than random fuzzing?
Summary
- **QuickCheck**: describe properties (invariants), the generator produces 100+ random test cases automatically.
- **Shrinking**: a found counterexample is minimized to a minimal reproducer. Key to readable failures.
- **Generators**: monadic and composable. Explicitly cover edge cases (0, maxInt, empty). That is where bugs live.
- **Fuzzing**: finds crashes and memory errors without a spec. Coverage-guided (AFL, libFuzzer) beats random. Google OSS-Fuzz: 10K+ vulnerabilities.
Related topics
Property testing sits inside a broader verification spectrum:
- Model checking — Model checking gives exhaustive guarantees. Property testing gives probabilistic ones via sampling.
- Theorem provers — Proof assistants give mathematical proofs of properties.
Вопросы для размышления
- QuickCheck generates random tests, but randomness might never hit a specific bug. How does Hypothesis (Python) tackle this with targeted property-based testing?
- Fuzzing finds crashes, property-based testing finds logic errors. Can we combine them? What would coverage-guided property-based testing look like?
- encode/decode roundtrip is a simple and powerful property. What other universal properties hold for most data structures and algorithms?