EnglishРусский Map
↑Supply Chain Security

Фаззинг на основе грамматик

Wiki conceptfuzzingsecuritytesting ↳ show in map Markdown
title
Фаззинг на основе грамматик
type
concept
summary
Генерация входных данных фаззинга по контекстно-свободной грамматике вместо случайных байтов, чтобы проходить ранний парсинг и проверять внутреннюю логику
parent
supply-chain-security
tags
fuzzing, security, testing
created
2026-05-12
updated
2026-05-12
lang
ru
translation_of
grammar-based-fuzzing
source_updated
2026-05-12
translated
2026-09-01
translator
lllm/antigravity/gemini-3.7-flash-medium

Фаззер с контролем покрытия, генерирующий случайные байты, потратит большую часть процессорного времени на то, как цель отбрасывает некорректные данные ещё на этапе лексера. Для любой цели с нетривиальным форматом ввода - JSON, protobuf, ASN.1, фрейм RPC, кодирование транзакций - по-настоящему интересный код начинается через несколько стадий после разбора байтов. Фаззинг на основе грамматик решает эту проблему: данные генерируются по контекстно-свободной грамматике и потому структурно валидны изначально, а мутации происходят внутри грамматики (перезапись правил, замена поддеревьев), а не на уровне байтов.

Грамматика обычно задаётся списком продукционных правил. Nautilus, AFL++ в режиме грамматик и CSmith используют различные варианты этой идеи. Небольшой пример для JSON из документации gosentry:

[
  ["Json", "\\{\"postOfficeBox\":{Number}\\}"],
  ["Number", "{Digit}"],
  ["Number", "{Digit}{Number}"],
  ["Digit", "0"], ["Digit", "1"], ...
]

Каждый входной элемент представляет собой валидный JSON нужной формы, что позволяет фаззеру мутировать само число, обёрнутое в синтаксические конструкции.

Где это окупается

  • Компиляторы, парсеры, движки запросов - всё, где интересные баги находятся глубже фронтенда
  • Дифференциальное тестирование нескольких реализаций одной спецификации (см. differential-fuzzing) - обеим реализациям нужны валидные входные данные, чтобы их результаты могли разойтись
  • Фаззинг на соответствие протоколу - байты должны соответствовать структуре протокола, иначе получатель просто разорвёт соединение

Где это не помогает

  • Баги в самих лексерах и парсерах - для фронтенда случайные байты подходят лучше
  • Цели, где входные данные принципиально не структурированы (пиксели изображений, необработанный звук)
  • Случаи, когда грамматика и есть тестируемая спецификация, а её написание отнимает половину всей работы

Комбинирование стратегий

В реальных кампаниях фаззинга генерацию на основе грамматик обычно сочетают с побайтовыми мутациями: грамматику используют для начального наполнения корпуса и шага "сгенерировать валидную базу", а побайтовые мутации - для поиска пограничных случаев в токенизаторе и парсере. Обратная связь по покрытию работает в обоих случаях, так как инструментация находится в самой цели, а не в генераторе входных данных.

Связь со structure-aware фаззингом

structure-aware-fuzzing - это внутриязыковой эквивалент: вместо грамматики фаззеру передают тип Go/Rust/C++ для входных данных, и он конструирует экземпляр напрямую. Фаззинг на основе грамматик лучше подходит, когда входные данные представляют собой байты в сети (сериализованный протокол, исходный код); structure-aware фаззинг - правильный выбор, когда на вход подаётся значение, принимаемое API (структура, типизированная запись). gosentry поддерживает оба подхода.

Linked from