Property-Based и Mutation Testing

Апрель 2014: Heartbleed (CVE-2014-0160) показал, что OpenSSL два года жил с buffer overread в TLS heartbeat. Test coverage был высокий, code review был, баг пропустили. Параллельно нашли двое: Neel Mehta из Google (вручную, по review кода 21 марта) и финны из Codenomicon (2 апреля, новым правилом Safeguard внутри своего фаззера Defensics). Codenomicon нашёл за часы то, что юнит-тесты с code review не нашли за два года. Это разорвало миф 'мы пишем тесты, у нас всё хорошо'. Coverage 90% и mutation score 40% - норма, не исключение. Современные testing-практики строятся на признании: программисты не могут вообразить все входы, нужны автоматы, которые ищут баги.

• **Erlang OTP, QuickCheck (Quviq)**: нашёл race condition в dets через 100 строк свойств - проблема висела 5 лет, не находилась unit-тестами.
• **OSS-Fuzz (Google)**: 30 000+ багов в open-source за 8 лет, в том числе тысячи в OpenSSL, libreoffice, ffmpeg, sqlite.
• **Meta TestGen-LLM 2024**: автогенерация тестов через LLM улучшила mutation score на 40% на их codebase - первая система LLM-test-generation в production масштабе.

QuickCheck и property-based

Классический unit-test проверяет конкретный пример: reverse([1,2,3]) == [3,2,1]. Программист сам выбирает входы - и пропускает те случаи, о которых не подумал. QuickCheck (Haskell, 1999, Klaus и Hughes) перевернул подход: вместо одного примера задаётся свойство (property), которое должно выполняться для всех входов, а генератор подкидывает сотни случайных значений. Reverse-свойство: reverse(reverse(xs)) == xs. Свойство ассоциативности: (a + b) + c == a + (b + c). QuickCheck нашёл баги в Erlang OTP, в Riak, в Volvo (через PropEr). Главная сила - shrinking: при падении свойство автоматически уменьшается до минимального падающего входа. 1000 случайных тестов плюс shrinking часто покрывают то, что unit-тесты не нашли за годы.

Свойства бывают: round-trip (encode/decode), идемпотентность (sort(sort(x)) == sort(x)), инварианты (длина после filter <= исходной), oracle-сравнение (новая реализация vs reference), метаморфические (если f(x) = y, то f(transform(x)) = transform(y)). Hypothesis (Python), fast-check (JS), proptest (Rust), jqwik (Java), ScalaCheck - современные имплементации QuickCheck с продвинутым shrinking.

Shrinking - ключевая фишка. Без него падение на random входе длиной 1000 элементов даёт бесполезный stacktrace. Hypothesis автоматически уменьшит до 2-3 элементов, на которых баг ещё проявляется - и это можно дебажить.

Mutation testing

Покрытие кода (line coverage 90%) ничего не говорит о качестве тестов. Тест может выполнить строку, но не проверить её результат - покрытие будет, а баг останется незамеченным. Mutation testing спрашивает: если я внесу ошибку в код, заметят ли это мои тесты? Mutation engine берёт код, делает копию с одной маленькой мутацией (заменяет + на -, < на <=, true на false, удаляет вызов), запускает тесты. Если хоть один тест упал - мутант убит, тесты адекватны. Если все прошли - мутант выжил, тесты дырявые. Mutation score = killed / total mutants. Большие проекты типа Google живут на 80-85% mutation score, что даёт реальную гарантию качества.

Стандартные мутации (AOR - Arithmetic Operator Replacement, ROR - Relational Operator, COR - Conditional, LCR - Logical Connector, etc). Эквивалентные мутанты - мутации, не меняющие семантику (i++ vs ++i в некоторых контекстах) - проблема mutation testing: они не убиваются никакими тестами. Современные инструменты используют LLM для распознавания эквивалентных мутантов (Stryker, PIT). Стоимость mutation testing высока: для каждой мутации запускается весь тестовый набор - 1000 мутаций * 10 секунд = 3 часа.

Fuzzing

Fuzzing - property-based testing на стероидах: вместо генератора по схеме просто скармливаем функции random или genetic-mutated байты. AFL (American Fuzzy Lop, 2013) был breakthrough: instrumentation добавляет coverage-обратную связь к мутациям. Когда новый вход открывает новую ветку - он сохраняется в очереди и мутируется дальше. Так фуззер находит вглубь, не наугад. AFL за 12 лет нашёл тысячи багов в OpenSSL, sudo, file, bash. OSS-Fuzz от Google непрерывно фаззит 1000+ open-source проектов - нашёл 30 000+ багов за 8 лет. LibFuzzer и Honggfuzz - in-process варианты для библиотек.

Coverage-guided fuzzing работает так: instrumented binary при выполнении сообщает хеш набора пройденных edge'ов. Если хеш новый - вход интересен, добавляется в seed corpus. Мутация энергии: разные стратегии - bit flips, byte arithmetic, dictionary insertion, splicing. Sanitizers (ASan, UBSan, MSan) превращают bug в crash, который фуззер видит. Без sanitizer'ов память portion фаззера не обнаружила бы Heartbleed.

Fuzzing требует sanitizer'ов. Без ASan фаззер видит только assertion failures и SIGSEGV - пропустит use-after-free, off-by-one с маленьким out-of-bounds, integer overflow. ASan+UBSan превращают 90% memory bugs в crash. Performance overhead: 2-3x slowdown, но это окупается.

Генеративные подходы

Property-based, mutation, fuzzing - всё это автоматическая генерация тестов. Следующий шаг - generative AI: LLM генерируют осмысленные тесты по сигнатуре и docstring. CodeT5+, Codex, GPT-4 показывают line coverage 65-80% на autogenerated тестах для Python. Tools: Pynguin (search-based), TestPilot (Salesforce, GPT-3.5), Meta TestGen-LLM (40% мутационного улучшения на их codebase). Метаморфическое тестирование - старая идея, новое применение: если f(x) = y, какое соотношение между f(x) и f(transform(x))? Для нейросетей это решение тестирования: dropout не должен сильно менять предсказание, поворот изображения - сохранять класс.

Hybrid подходы: LLM генерирует базовый тест, property-based генератор подкидывает edge cases, mutation testing оценивает adequacy. Concolic testing (KLEE, DSE) - символьное исполнение совмещённое с конкретными запусками: SMT-solver вычисляет вход для каждой ветки. Differential testing - две реализации (старая и новая) или (С и Rust) сравниваются на одинаковых входах, расхождение = баг.

Различия подходов: property-based - программист пишет свойства, генератор делает входы; mutation - программист пишет тесты, мутатор делает баги; fuzzing - программист пишет parser, fuzzer делает входы; LLM-generated - программист пишет код, LLM делает и тесты. Они дополняют, а не заменяют друг друга.

Ключевые идеи

• **Property-based testing** проверяет инварианты для тысяч случайных входов, shrinking уменьшает падающий вход до минимального примера для отладки.
• **Mutation testing** оценивает качество тестов: внедряет баги в код и смотрит, ловят ли тесты их. Mutation score - честная метрика adequacy, в отличие от coverage.
• **Coverage-guided fuzzing** использует instrumentation для направленного поиска: сохраняет входы, открывающие новые ветки, и мутирует их. Sanitizers превращают memory bugs в crash'ы.
• **Generative и hybrid подходы** (LLM + property-based + mutation) - будущее тестирования: автоматизация на каждом уровне с проверкой adequacy.

Связанные темы

Property-based и mutation testing развивают идеи классических подходов:

• TDD и BDD — Property-based - расширение TDD: вместо одного примера задаётся семейство свойств. Red-Green-Refactor цикл работает идентично
• Безопасность — Fuzzing - основной инструмент security research. OWASP рекомендует fuzzing parsers, protocol implementations, deserialization endpoints

Вопросы для размышления

• Mutation testing стоит 10x больше computational ресурсов, чем обычный test run. В каких ситуациях этот overhead оправдан, а в каких - нет?
• Property-based test может скрыть баг, если генератор выбирает не те значения (например, всегда нечётные числа). Как валидировать сами генераторы?
• LLM генерирует тесты с coverage 80%, но они тестируют только happy path. Как комбинировать LLM-generated тесты с property-based и mutation для надёжности?

Связанные уроки

• se-12 — Традиционное тестирование - основа перед property-based
• se-14 — После продвинутых тестов - рефакторинг с уверенностью
• prob-04-bayes — Property-based testing генерирует входы из вероятностных распределений
• alg-19-divide-conquer — Mutation testing - divide and conquer для нахождения пробелов
• ml-04-data-preprocessing — Fuzzing и property testing аналогичны data augmentation в ML
• stat-05-hypothesis