Тот день, когда я полюбил фаззинг

В 2007 году я написал пару инструментов ^[1] для моддинга космического симулятора Freelancer ^[2]. Ресурсы игры хранятся в формате “binary INI” или “BINI”. Вероятно, бинарный формат выбрали ради производительности: такие файлы быстрее загружать и читать, чем произвольный текст в формате INI.

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

Я не анализировал формат BINI, и я не первый, кто научился их редактировать. Но существующие инструменты мне не нравились, и у меня было своё видение, как они должны работать. Я предпочитаю интерфейс в стиле Unix, хотя сама игра работает под Windows.

В то время я как раз познакомился с инструментами yacc ^[3] (в действительности Bison ^[4]) и lex ^[5] (в действительности flex ^[6]), а также Autoconf, поэтому использовал именно их. Было интересно опробовать эти утилиты в деле, хотя я рабски подражал другим проектам с открытым исходным кодом, не понимая, почему всё сделано так, в не иначе. Из-за использования yacc/lex и создания конфигурационных скриптов потребовалась полноценная Unix-подобная система. Это всё видно в оригинальной версии программ ^[7].

Проект оказался вполне успешным: и я сам с успехом использовал эти инструменты, и они появились в разных коллекциях для моддинга Freelancer.

Рефакторинг

В середине 2018 года я вернулся к этому проекту. Вы когда-нибудь смотрели на свой старый код с мыслью: чем ты вообще думал? Мой формат INI оказался гораздо более жёстким и строгим, чем необходимо, запись бинарников происходила сомнительным образом, а сборка даже нормально не работала.

Благодаря десяти годам лишнего опыта я точно знал, что сейчас напишу эти инструменты гораздо лучше. И я сделал это за несколько дней, переписав их с нуля. В мастер-ветке на Github сейчас лежит этот новый код.

Мне нравится всё делать как можно проще ^[8], поэтому я избавился от autoconf в пользу более простого и портируемого Makefile ^[9]. Нет больше ни yacc, ни lex, а парсер написан вручную. Используется только соответствующий, портируемый C. Результат настолько прост, что я собираю проект одной короткой командой из Visual Studio ^[10], поэтому Makefile не так уж и нужен. Если заменить stdint.h на typedef, можно даже собрать и запустить binitools под DOS ^[11].

Новая версия быстрее, компактнее, чище и проще. Она гораздо более гибка в отношении ввода INI, поэтому её проще использовать. Но действительно ли она корректнее?

Фаззинг

Я много лет интересовался фаззингом ^[12], особенно afl ^[13] (american fuzzy lop). Но так и не освоил его, хотя и протестировал некоторые инструменты, которые регулярно использую. Но фаззинг не нашёл ничего примечательного, по крайней мере, прежде чем я сдался. Я тестировал свою библиотеку JSON и почему-то тоже ничего не нашёл. Ясное дело, что мой JSON-парсер не мог быть настолько надёжным, верно? Но фаззинг ничего не показал. (Как оказалось, моя библиотека JSON таки довольно надёжна, во многом благодаря усилиям сообщества!)

Но теперь у меня появился относительно новый INI-парсер. Хотя он может успешно анализировать и правильно собирать исходный набор файлов BINI в игре, его функциональность по-настоящему не тестировалась. Наверняка здесь фаззинг что-нибудь да найдёт. Кроме того, для запуска afl на этом коде не нужно писать ни строчки. Инструменты по умолчанию работают со стандартным вводом, что идеально.

Предполагая, что у вас установлены необходимые инструменты (make, gcc, afl), вот как легко запускается фаззинг binitools:

$ make CC=afl-gcc
$ mkdir in out
$ echo '[x]' > in/empty
$ afl-fuzz -i in -o out -- ./bini

Утилита bini принимает на входе INI и выдаёт BINI, так что её гораздо интереснее проверить, чем обратную процедуру unbini. Поскольку unbini анализирует относительно простые двоичные данные, то (вероятно) фаззеру нечего искать. Впрочем, я на всякий случай всё равно проверил.

В этом примере я поменял компилятор по умолчанию на оболочку GCC для afl (CC=afl-gcc). Здесь afl вызывает GCC в фоновом режиме, но при этом добавляет в двоичный файл собственный инструментарий. При фаззинге afl-fuzz использует этот инструментарий для мониторинга пути выполнения программы. Документация afl ^[14] объясняет технические детали.

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

Самый интересный и страшный результат — полный сбой программы. Когда я первый раз запустил фаззер для binitools, у bini обнаружилось много такие сбоев. В течение нескольких минут afl обнаружила ряд тонких и интересных ошибок в моей программе, что было невероятно полезно. Фаззер нашёл даже маловероятный баг устаревшего указателя ^[15], проверив разный порядок различных выделений памяти. Этот конкретный баг стал поворотным моментом, который заставил меня осознать ценность фаззинга.

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

Создание набора тестов

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

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

Во-вторых, многие из этих входных данных оказались длиннее, чем необходимо для вызова их уникального пути выполнения. Тут помог afl-tmin, минимизатор тестовых случаев, который сократил тестовый корпус.

Я разделил допустимые и недопустимые входные данные — и проверил их в репозитории. Взгляните на все эти дурацкие входы, придуманные фаззером ^[16], на основе единственного минимального входа:

• допустимые входные данные ^[17]
• недопустимые входные данные ^[18]

По сути, здесь парсер замораживается в одном состоянии, а набор тестов гарантирует, что конкретный билд ведёт себя очень специфическим образом. Это особенно полезно для гарантии, чтобы сборки, сделанные другими компиляторами на других платформах действительно ведут себя одинаково по отношению к своим выходным данным. Мой набор тестов даже выявил ошибку в библиотеке dietlibc, потому что binitools не прошёл тесты после связывания с ней. Если бы нужно было внести нетривиальные изменения в парсер, то по сути пришлось бы отказаться от текущего набора тестов и начать всё сначала, чтобы afl cгенерировал весь новый корпус для нового парсера.

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

Автор: m1rko

Источник ^[19]