Теория языков программирования
Property-based Testing
QuickCheck нашёл баг в bzip2 компрессоре, который существовал 10 лет. Тест: compress(decompress(x)) == x. Запустился, нашёл counterexample, shrinking свёл к 20 байтам. Один тест, одно свойство - и давний баг найден.
- **Google OSS-Fuzz**: 700+ open source проектов фазятся 24/7. 10 000+ уязвимостей найдено в OpenSSL, libpng, Chromium, FFmpeg
- **Rust ecosystem**: cargo-fuzz используется для rustc, serde, nom parser. rustc сам фазит компилятор - нашёл паники в borrow checker
- **Erlang QuickCheck (Quviq)**: коммерческая версия. Нашла баги в Dets (Erlang persistent storage), RabbitMQ, Riak - production distributed systems
QuickCheck
QuickCheck (Haskell, 1999) - фреймворк для property-based testing. Вместо конкретных примеров описываются свойства (properties), которые должны выполняться для ВСЕХ входных данных. QuickCheck генерирует сотни случайных тест-кейсов автоматически.
В чём принципиальное отличие property-based testing от example-based?
Shrinking
Shrinking - минимизация counterexample. Если QuickCheck нашёл ошибку на входе [42, -7, 1000, 0, -3], shrinking пытается найти минимальный пример: возможно ошибка воспроизводится на [-7, 0]. Это делает отладку на порядки проще.
Hedgehog (Haskell) использует integrated shrinking - генераторы автоматически включают shrinking без отдельной реализации. Это устраняет целый класс проблем с custom generators в QuickCheck.
Почему shrinking критически важен для практического использования property-based testing?
Генераторы
Генератор (Gen a) описывает как случайно создать значение типа a для тестирования. Хорошие генераторы охватывают граничные случаи (0, -1, max_int), невалидные входы, специальные значения. Генераторы комбинируются в монадическом стиле.
Почему хорошие генераторы явно включают граничные случаи (0, maxInt, пустой список)?
Fuzzing
Fuzzing - автоматическая генерация входных данных для поиска crashes, ошибок памяти, зависаний. Coverage-guided fuzzing (AFL, libFuzzer) использует feedback от execution coverage для направленного поиска. Google OSS-Fuzz нашёл 10000+ уязвимостей.
Разница fuzzing и property-based testing: fuzzing ищет crashes/UB/memory errors - не нужно формулировать свойства. Property-based testing проверяет бизнес-логику. Google Chromium, Firefox, OpenSSL постоянно фазятся - OSS-Fuzz 24/7 на 700+ проектах.
Property-based testing требует много времени на формулировку свойств - проще написать unit тесты
Часто достаточно простых универсальных свойств: encode/decode roundtrip, idempotency, commutativity, monotonicity
encode(decode(x)) == x - одна строка которая проверяет всю сериализацию/десериализацию. Эквивалент сотен ручных тестов. Время окупается при поиске edge cases
Что такое coverage-guided fuzzing и почему он эффективнее случайного fuzzing?
Итоги
- **QuickCheck**: описываем свойства (invariants), генератор создаёт 100+ случайных тест-кейсов автоматически
- **Shrinking**: найденный counterexample минимизируется до минимального воспроизводящего примера - ключ к читаемым ошибкам
- **Генераторы**: монадические, комбинируемые. Явно включайте граничные случаи (0, maxInt, empty) - там живут баги
- **Fuzzing**: находит crashes/memory errors без spec. Coverage-guided (AFL/libFuzzer) эффективнее случайного. Google OSS-Fuzz: 10K+ уязвимостей
Связанные темы
Property testing - часть широкого спектра верификации:
- Model checking — Model checking даёт исчерпывающую гарантию, property testing - вероятностную через sampling
- Theorem provers — Proof assistants дают математические доказательства свойств
Вопросы для размышления
- QuickCheck генерирует случайные тесты, но случайность может никогда не найти определённый баг. Как Hypothesis (Python) решает это через targeted property-based testing?
- Fuzzing находит crashes, property-based testing находит логические ошибки. Можно ли объединить? Как выглядело бы coverage-guided property-based testing?
- Encode/decode roundtrip - простое и мощное свойство. Какие ещё универсальные свойства работают для большинства структур данных и алгоритмов?