Coverage-Guided Fuzzing

Стандартный алгоритм любого современного фаззера, заслуживающего внимания. Набор тест-кейсов рассматривается как эволюционирующая популяция, пути исполнения SUT - как ландшафт приспособленности, а достижение нового покрытия - как критерий отбора. Тест-кейсы, задействующие новый код, остаются в корпусе и мутируют дальше; потомки, не добавляющие покрытия, отбрасываются.

Из руководства по тестированию от Trail of Bits:

fn fuzz(corpus) {
  let bug_set = [];
  while let Some(test_case) = schedule(corpus) {
    let offspring = mutate(test_case);
    let observations = execute(offspring);

    if (is_interesting(observations)) { corpus.append(offspring); }
    if (is_bug(observations))         { bug_set.append(offspring); }
  }
  return bug_set;
}

Четыре точки настройки, примерно в порядке возрастания их влияния на кампанию:

• mutate - побитовые инверсии, вставки и удаления байтов, склейка фрагментов из разных записей корпуса, подстановка токенов из словаря. Большинство фаззеров поставляются с фиксированным набором мутаторов; продвинутые движки позволяют собирать свои.
• is_interesting - почти всегда проверка "попал ли прогон на ребро графа, которого ещё нет в карте покрытия"; некоторые движки также отслеживают состояние операндов сравнения (value-profile в libFuzzer) или покрытие с учётом контекста вызова функций
• schedule - выбирает, какую запись корпуса мутировать следующей. Приоритезация "favored seeds" в AFL - канонический пример; в LibAFL планирование вынесено в trait
• execute - запускает SUT под инструментированием; здесь находится критический по вводу-выводу горячий путь движка

Почему покрытие работает как функция приспособленности

Покрытие - дешёвая аппроксимация условия "входные данные выполняют код, который предыдущий корпус не задействовал". Это почти то, что нужно: истинная цель - "найти входы, вскрывающие баги", но ошибки обычно скапливаются в редко выполняемом коде, а покрытие рёбер графа достаточно тесно коррелирует с достижимостью, чтобы эвристика приносила те внушительные списки найденных уязвимостей, которыми славится эта область. При этом фазинг на основе покрытия систематически упускает баги в полностью покрытом коде (например, тонкие ошибки, зависящие от значений данных на пути, которого корпус достигает, но не нагружает должным образом).

Какое инструментирование обеспечивает работу

Фаззеру необходимо знать, какие рёбра графа управления выполнились. Есть два пути:

• На этапе компиляции - -fsanitize=fuzzer (Clang) или компиляторы-обёртки AFL вставляют счётчик на каждое ребро. Быстро во время работы, но требует сборки SUT из исходников.
• Только по бинарному коду - режим QEMU, Intel PT, режим Frida. Работает медленнее (в 10-100 раз), зато не требует исходного кода. Применяется при фазинге закрытых компонентов или скомпилированных зависимостей.

Сочетание с другими техниками

• grammar-based-fuzzing - заменяет mutate на мутатор синтаксических деревьев с учётом грамматики; обратная связь по покрытию работает по-прежнему
• structure-aware-fuzzing - оборачивает входные данные в декодер: корпус состоит из байтов, а SUT получает типизированные значения
• differential-fuzzing - заменяет is_bug на условие "вывод реализации A != вывод реализации B"; покрытие всё так же определяет is_interesting
• zstd-lean-proof-automation - противоположный полюс того же компромисса: формальное доказательство гарантирует отсутствие ошибок там, где фазинг ищет их наличие, а автоматизация доказательств с помощью LLM изменила цену этого подхода

Движки

• libFuzzer - внутрипроцессный, самый быстрый, требует исходного кода. API LLVMFuzzerTestOneInput.
• AFL++ - межпроцессный, с более широким набором санитайзеров и вариантов отслеживания покрытия, прямой потомок оригинального AFL
• LibAFL - библиотека модульных компонентов для сборки собственного фаззера
• Honggfuzz - фаззер от Google с поддержкой PT/Intel BTS и persistent mode
• Специализированные движки - kAFL (фазинг ядра через Intel PT в KVM), Syzkaller (фазинг системных вызовов Linux), AFLNet (фазинг протоколов с сохранением состояния)