Фаззинг глазами программиста. Как в Google автоматизируют поиск багов

Когда количество строчек кода в твоих программах исчисляется миллионами, поиск ошибок осложняется тысячекратно. К счастью, сегодня есть возможность автоматизировать тестирование с помощью фаззеров. Как они работают, почему их стоит применять и на что они способны — об этом ты узнаешь в сегодняшней статье.

Традиционная практика тестирования предполагает, что на вход программы подаются самые разные данные — корректные, почти корректные и граничные случаи. Это позволяет убедиться, что в целом код работает правильно и серьезных ошибок в логике работы нет. Однако при этом качество проверки целиком зависит от качества тестов и их количества.

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

Фаззинг берет лучшее от двух существующих подходов. Мы не ограничиваем себя конечным количеством тестовых случаев и постоянно генерируем случайные входные данные для нашего кода, но при этом каждая новая последовательность использует информацию из предыдущих попыток для максимизации результата.

Сразу возникает резонный вопрос — могут ли случайные данные что-то протестировать в действительности? Предположим, мы хотим проверить компилятор С/C++ и посылаем на вход сгенерированные последовательности символов. Совершенно очевидно, что мы получим много ошибок от компилятора на стадии лексикографического анализа и парсера выражений, но при этом едва затронем оптимизацию и генерацию кода. Выглядит не очень-то эффективно, согласись. К счастью, это напрасное опасение.

Где можно применять фаззинг

Фаззинг можно успешно использовать везде, где на входе требуются сложные данные. Тривиальные случаи решаются простым перебором, но если у тебя есть хотя бы десять байт входных данных, то 280 уже создают проблему при тестировании, и обычные тесты тут вряд ли справятся.

Именно поэтому самые распространенные случаи применения фаззинга приходятся на различные парсеры (XML, JSON), мультимедиакодеки (аудио, видео, графика), сетевые протоколы (HTTP, SMTP), криптографию (SSL/TLS), браузеры (Firefox, Chrome) и компрессию файлов (ZIP, TAR). Также целями фаззинга могут быть компиляторы (C/C++, Go), интерпретаторы (Python, JS), библиотеки для обработки регулярных выражений (regexp), базы данных (SQL) и комплекты офисных приложений (LibreOffice).

Чрезвычайно важен сегодня и фаззинг операционных систем, различных гипервизоров и виртуальных машин. Так что мы в Google даже запустили специальный фаззер syzkaller, который непрерывно тестирует несколько сборок ядра Linux, FreeBSD, NetBSD, а также Android и ChromeOS.

Резюмируем: фаззинг абсолютно необходим для тех программ, которые работают на границе доверия и используют входные данные из ненадежных источников.

Санитайзеры

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

Однако работой с памятью их возможности не ограничиваются. Они также позволяют обнаруживать состояние гонки для потоков, ситуации взаимной блокировки, обращения по нулевому указателю, деление на ноль (куда же без него), переполнения для типов данных и некорректные битовые сдвиги — одним словом, солидную часть ошибок, которые вызывают неопределенное поведение в программах.

Санитайзеры очень помогают во время отладки. Для их использования достаточно скомпилировать исходники с включенной инструментацией, которая добавит специальные команды в исполняемый файл. По ним можно будет следить за ходом выполнения программы и состоянием памяти. При обнаружении ошибок будет сгенерирован отладочный вывод и программа завершит работу.

Сегодня работу с санитайзерами поддерживают компиляторы GCC и Clang. Настоятельно рекомендую обратить на них внимание. Мало просто сгенерировать фаззером некорректные входные данные, которые обрушат программу. Ошибку следует устранить, а для этого надо собрать максимум информации. Именно в этом и помогают санитайзеры. Их совместное использование повышает эффективность тестирования. Так что в некотором смысле фаззеры и санитайзеры созданы друг для друга. ?

Типы фаззеров

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

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

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

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

На основе мутаций

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

При этом никаких дополнительных усилий от разработчика тут не требуется (разве что написание специальных алгоритмов мутаций), но и качество входных данных у таких фаззеров обычно среднее.

Построение грамматики по данным

Также есть способ сочетать оба описанных выше подхода. Специалисты по обработке данных и машинному обучению могут попытаться построить грамматику на основе уже имеющейся информации. Однако оценить результат на выходе таких фаззеров зачастую непросто.

На основе покрытия кода

Подобные фаззеры устроены по принципу генетического алгоритма и стремятся максимизировать покрытие тестового кода. С практической точки зрения это один из самых эффективных на сегодня типов фаззеров. На этой основе работает libFuzzer, и о нем я расскажу подробнее.

Упрощенно работу фаззера в форме псевдокода можно представить так:

Источник: xakep.ru