Компиляторы
Тестирование компиляторов
Компилятор это один из самых сложных программных продуктов: тысячи оптимизаций, десятки архитектур, миллионы строк кода. Баг в компиляторе - это молчаливая ошибка: программа компилируется без warnings, запускается, но даёт неверный результат. Поэтому CSmith автоматически генерирует C программы и сравнивает GCC с Clang - и нашёл 325+ таких молчаливых bugs. Тестирование компиляторов - отдельная инженерная дисциплина.
- **OSS-Fuzz + LLVM**: >9000 bugs найдено за 7 лет непрерывного fuzzing; каждый crash автоматически открывает issue в LLVM bugzilla с минимизированным reproducer
- **CSmith в production**: баги найденные CSmith в GCC и Clang влияли на production код - miscompilation в OpenSSL, Chrome V8, Firefox SpiderMonkey были обнаружены именно через differential testing
- **rust cargo-mutants**: применяется в крупных Rust open source проектах (tokio, serde) для оценки coverage; типично 15-25% мутантов выживают что указывает на пропущенные edge cases
Fuzzing компиляторов
Fuzzing компилятора - генерация случайных программ и проверка что компилятор не падает. Coverage-guided fuzzer (libFuzzer, AFL++) мутирует входные данные для покрытия новых путей кода. Compiler fuzzing специфика: invalid input должен давать ошибку, valid input должен компилироваться без crash.
OSS-Fuzz (Google, 2016) непрерывно фаззит LLVM, GCC, OpenSSL, Python, Go и 700+ других проектов. По данным 2023 года: найдено 9000+ bugs в LLVM за 7 лет. AFL++ нашёл первый bug в TypeScript компиляторе в 2020. Rust fuzzing инструменты: cargo-fuzz, honggfuzz-rs, arbitrary crate для генерации структурированного input.
Что проверяет compiler fuzzer в первую очередь?
Differential Testing
Differential testing: компилировать одну программу несколькими компиляторами или с разными уровнями оптимизации, сравнивать результат выполнения. Расхождение = баг в одном из компиляторов. Особенно эффективно с generation-based fuzzer'ами которые генерируют валидные программы без UB.
CSmith (University of Utah, Zhendong Su) нашёл 325+ bugs в GCC, Clang, MSVC, ICC через differential testing. EMI (Equivalence Modulo Inputs) метод нашёл 1000+ bugs добавляя dead code. Le et al. в 2014 нашли компиляторные bugs с miscompilation которые могли влиять на production code используя CSmith + differential testing в Chrome, Firefox, OpenSSL.
Почему программы для differential testing должны быть без Undefined Behavior (UB)?
Mutation Testing
Mutation testing - оценка качества тест-сюита путём внесения мелких изменений (мутаций) в исходный код компилятора. Если мутация не детектируется тестами - тест-сюит неполный. Применительно к компилятору: мутировать оптимизационные passes и проверить что тесты падают. Stryker (JS), PIT (Java), mutmut (Python).
LLVM использует FileCheck для regression tests: каждый IR трансформирующий pass имеет `.ll` тест который проверяет конкретный output. Mutation testing выявляет что некоторые FileCheck паттерны слишком слабые (проверяют только факт наличия инструкции, не её корректность). Rust cargo-mutants анализирует проекты и типично находит 10-30% неубитых мутантов.
Что значит 'выживший мутант' в mutation testing?
CReduce: минимизация bug repro
После нахождения bug нужно минимизировать reproducer: файл из 10000 строк сократить до 5. CReduce (автоматическая программная редукция) применяет трансформации к исходнику (удалить функцию, упростить выражение, удалить параметр) и проверяет что bug воспроизводится. Повторяет до fixpoint.
CReduce разработан в University of Utah. Типичное время работы: 1-60 минут для файла 10000 строк. LLVM разработчики используют CReduce для каждого ICE bug report - сырой reproducer из продакшна невозможно анализировать. clang-reduce-crash.py - wrapper скрипт в LLVM который автоматизирует CReduce для crashes Clang.
Тестирование компилятора требует написания тысяч ручных тест-кейсов
Наиболее эффективные методы - автоматические: fuzzing находит crashes без ручных тестов, differential testing находит miscompilations, mutation testing оценивает полноту тест-сюита
CSmith нашёл 325+ bugs без написания ни одного ручного теста. OSS-Fuzz находит 1000+ bugs в год в LLVM автоматически. Ручные тесты важны для regression и conformance, но масштаб поиска bugs обеспечивают автоматические методы
Почему минимизация reproducer критична для эффективного bug reporting?
Итоги
- Coverage-guided fuzzing (libFuzzer, AFL++): мутирует входы для максимального покрытия; OSS-Fuzz нашёл 9000+ LLVM bugs за 7 лет
- Differential testing (CSmith): компиляция одной программы разными компиляторами; расхождение в output = miscompilation bug. Программы без UB - обязательное условие
- CReduce минимизирует reproducer с 10000 строк до 15: automation трансформаций с interestingness test как оракулом
Связанные темы
Тестирование компиляторов применяет общие принципы ко специфике компиляторов:
- Написание компилятора — Тест-сюит неотъемлемая часть разработки компилятора; FileCheck тесты для каждого pass обязательны
- LLVM Passes — Каждый LLVM pass имеет FileCheck тесты; mutation testing оценивает их полноту
- Собеседование по компиляторам — Знание методологий тестирования компиляторов - признак senior-уровня
Вопросы для размышления
- Differential testing требует программы без UB. Как CSmith гарантирует генерацию C программ без Undefined Behavior, учитывая что UB в C весьма богатое подмножество?
- CReduce минимизирует reproducer применяя трансформации. Как CReduce знает что трансформация сохранила семантику программы достаточно чтобы bug воспроизводился?
- Mutation testing нашёл что 25% мутантов в cargo проектах выживают. Что это говорит о качестве тестов в типичном Rust проекте и как это исправить без написания 1000 тестов вручную?