Когда количество строчек кода в вашем софте исчисляется миллионами, поиск багов осложняется многократно. К счастью, сегодня есть возможность автоматизировать тестирование с помощью фаззеров. Как они работают, почему их стоит применять и на что они способны — об этом вы узнаете в этой статье.
Еще по теме: Как проверить свой роутер на уязвимость
Традиционная практика тестирования предполагает, что на вход программы подаются самые разные данные — корректные, почти корректные и граничные случаи. Это позволяет убедиться, что в целом код работает правильно и серьезных ошибок в логике работы нет. Однако при этом качество проверки целиком зависит от качества тестов и их количества.
Поэтому всегда есть вероятность того, что какой-то важный случай был упущен, не вошел в фиксированный набор тестов и наш код все-таки содержит ошибку, которую достаточно продвинутый хакер сможет эксплуатировать. Так что даже положительный результат не следует рассматривать как повод прекратить тестирование. Но ведь и слепо перебирать все возможные значения — тоже не вариант, никаких ресурсов не хватит.
Фаззинг берет лучшее от двух существующих подходов. Мы не ограничиваем себя конечным количеством тестовых случаев и постоянно генерируем случайные входные данные для нашего кода, но при этом каждая новая последовательность использует данные из предыдущих попыток для максимизации результата.
Сразу возникает резонный вопрос — могут ли случайные данные что-то протестировать в действительности? Предположим, мы хотим проверить компилятор С/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, и о нем я расскажу подробнее.
Упрощенно работу фаззера в форме псевдокода можно представить так:
|
1 2 3 4 5 6 7 |
Build the program with source coverage instrumentation; Collect the initial corpus of inputs (optional, but recommended); while (true) { Choose a random input from corpus and mutate it; Run the target program on the input, collect code coverage; If the input gives new coverage, add mutation back to corpus; } |
Сначала программа компилируется с инструментацией по покрытию кода. Это позволяет нам при прогоне программы понять, какие строчки кода были исполнены по факту. Дальше собирается репрезентативный корпус данных. На самом деле это опциональный шаг, можно начать с пустого набора данных. Дальше фаззер выбирает один из вариантов, мутирует его и подает на вход программы. Если при этом было получено новое кодовое покрытие, успех фиксируется и данные добавляются в набор.
Попытаемся теперь оценить, насколько эффективен этот алгоритм и почему он вообще работает. В качестве примера возьмем такой код:
|
1 2 3 4 5 6 7 8 |
if (input[0] == `1`) { if (input[1] == `3`) { if (input[2] == `3` && input[3] == `7`) { // Potential out-of-bounds write input[input[4]] = input[5]; } } } |
Чтобы попасть на строчку кода с потенциальной ошибкой, нам нужно правильно угадать четыре байта входного потока. Если использовать простой перебор «брутфорс», это потребует от нас около 232 попыток. Крайне расточительно! Попробуем взглянуть, как с такой задачей справится фаззер.
Если входной корпус пуст и не содержит никаких данных, результат первых попыток окажется полностью случайным. Это будет продолжаться ровно до того момента, пока фаззер не угадает первый байт. На это потребуется порядка 28 итераций. При этом фаззер зафиксирует новое покрытие, и правильный вход будет наконец добавлен в корпус.
Еще по теме: Лучшие сайты для поиска уязвимостей
Следующие попытки используют полученный результат в качестве отправной точки и последовательно улучшают наше покрытие. Легко подсчитать, что с таким подходом потребуется проверить порядка 210 вариантов, чтобы обнаружить ошибку. По сути, мы уменьшили число вариантов более чем в миллион раз и свели экспоненциальную проблему к полиномиальной, что очень неплохо.
Если пример выше вас не впечатлил и кажется слишком простым, рекомендую почитать заметку в блоге создателя AFL Михала Залевского — Pulling JPEGs out of thin air. В качестве демонстрации возможностей фаззеров Залевский синтезировал корректный файл формата JPEG (со всеми полями и заголовками) практически из ничего. И да, судя по результатам, его фаззер явно неравнодушен к абстрактному искусству.
При этом на каждом этапе изменения данных в корпусе вовсе не обязаны быть сложными. Мы можем просто переставлять, добавлять, удалять или инвертировать отдельные биты или байты в одном входе. Допустимо скрещивать различные входы, получая новые данные для следующих итераций. Или добавлять данные из какого-либо словаря. Можно использовать «магические цифры», которые должны генерировать ошибки в граничных случаях. Например, 28, 231, 232 + 1 и так далее.
Впрочем, это только тривиальные способы. Справится ли фаззер с такими условиями в коде?
|
1 2 3 4 5 6 |
if (*(uint64_t*)input == 0xDEADBEEFCAFEBABE) { … } if (crc32(input + 4, size - 4) == *(uint32_t*)input) { … } |
Описанный выше процесс последовательной мутации тут уже не сработает — для увеличения покрытия и продвижения по коду условие нужно угадать сразу и целиком. Поэтому мы разработали несколько подходов, которые перехватывают такие сравнения при инструментации (-fsanitize-coverage=trace-cmp). Это позволяет в момент исполнения получить доступ к операндам и добавить их в корпус. Также поддерживаются сравнения в функциях strcmp и memcmp.
И это открывает для нас новые возможности. Если взять «правильный» операнд и вставить в определенное место в нашей входной последовательности, то ветвление в коде можно будет проскочить за одну попытку.
Другой способ основан на расстоянии Хэмминга. Мы считаем число различных битов в операндах, и, если в ходе мутации нам удалось как-то сократить это расстояние, вход запоминается для дальнейшего использования. Таким образом мы последовательно приближаемся к необходимому значению.
Пример фаззинга
Чтобы написать фаззер на основе libFuzzer, надо сделать ровно две вещи. Во-первых, реализовать свою функцию Fuzz Target, которая будет передавать данные в тестируемую программу. Во-вторых, программу нужно скомпилировать с инструментацией и скомпоновать с библиотекой libFuzzer. Наибольшие трудности в C++ обычно вызывает именно последний этап, но мы разберем оба.
|
1 2 3 4 5 6 7 8 9 |
/* example for boost::regex library */ int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { try { std::string str((char*)Data, Size); boost::regex e(str); } catch (const std::exception&) {} return 0; } |
Исключения здесь пришлось перехватить, так как библиотека regex оповещает о некорректных выражениях именно с помощью исключений. Как видите, код очень простой и не требует каких-то особых знаний о фаззерах. Данные Data генерирует непосредственно библиотека libFuzzer, и их нужно лишь направить в правильную функцию.
Второй шаг — это собрать все в один исполняемый файл. Собирать будем с санитайзерами и инструментацией кода.
|
1 |
$ ./b2 cxxflags="-fsanitize-coverage=trace-pc-guard -fsanitize=address" toolset=clang install |
Первый флажок компилятора добавляет инструментацию для покрытия кода в исполняемый файл, второй отвечает за работу ASan — санитайзера адресов.
|
1 |
$ clang++ fuzzer.cc -fsanitize-coverage=trace=pc-guard -fsanitize=address libFuzzer.a |
На этом этапе мы собираем сам фаззер (с теми же флажками компилятора) и компонуем его с библиотекой libFuzzer. Именно в ней происходит основной цикл фаззинга, и лишь изредка управление передается нашей функции.
Работа фаззера была плодотворной, и уже через полчаса он нашел в коде несколько ошибок, причем некоторые были достаточно серьезными, в том числе с переполнением стека. За подробностями вы можете обратиться на сайт проекта. Стоит отметить, что все ошибки были оперативно устранены авторами библиотеки. Но, я думаю, всегда можно попытаться нафаззить что-то еще.
Фаззинг — процесс все-таки случайный, и заранее никогда нельзя угадать, сколько времени потребуется, чтобы обнаружить новую ошибку. Если вы хотите сначала потренироваться на готовом примере, рекомендуем начать с практической части из нашей предыдущей статьи по этой теме.
Поиск логических ошибок
Одна из наиболее интересных особенностей фаззеров — их возможность обнаруживать логические ошибки в программах. Когда ничего особо криминального как будто не происходит, но при этом программа все равно ведет себя некорректно и выдает неправильный результат. Зачастую с помощью фаззеров можно находить много таких ошибок.
До этого момента мы в основном обсуждали явные падения, связанные со стабильностью и безопасностью работы. Но с помощью фаззинга можно находить ошибки и в логике работы программы. На первый взгляд кажется, что это малореально, ведь кто-то должен заранее сообщить фаззеру правильный результат для каждого входа из корпуса.
К счастью, если проявить немного смекалки, способы все равно есть. Например, результаты можно проверять на достоверность, хотя бы приблизительно. Другими словами, выход программы должен выглядеть разумно (а не в стиле «полтора землекопа»).
Скажем, если работает декодер несжимающего формата изображений и для файла в 100 байт на выходе получается 100 Мбайт, то тут явно где-то ошибка. Или если известно, что в правильном выходе должна содержаться какая-то определенная строчка или заголовок, а они отсутствуют — это тоже повод задуматься.
Если наш процесс обратим, то результаты можно попробовать прогнать через взаимнообратную функцию и сравнить. Это может быть случай шифровки и дешифровки сообщений, архивации и разархивации файлов и прочее. Выход должен быть при этом равен исходному вводу.
Порой мы все-таки знаем правильный результат и нам есть с чем сравнивать. Например, если вы хотите фаззить какую-нибудь специфичную реализацию сортировки, которая знает о данных что-то дополнительно и использует это для более эффективной работы, — результат всегда можно сравнить со стандартными функциями и убедиться, что данные на выходе отсортированы в правильном порядке.
Еще один прием основан на сравнении двух реализаций. При этом нужно заранее проверить обе программы: они должны выдавать один и тот же результат на одинаковых данных. Или хотя бы синхронно генерировать схожие ошибки в случае некорректного входа. Конечно, писать новую библиотеку только для фазз-тестов мало кому хочется, но всегда можно попробовать найти альтернативы в свободном доступе.
И разумеется, сторонняя реализация необязательно должна быть на том же языке. Либо это может быть простой и неоптимизированный код против сложного. В любом случае варианты всегда найдутся, стоит только дать волю воображению!
Как фаззят в Google
Почему вообще фаззинг используют в Google? Разработка сегодня стала быстрее, и кода очень много. Корректность кода очень важна, стабильность все еще важна, а безопасность, разумеется, на первом месте. В такой ситуации нужно двигаться быстро, но при этом держать под контролем стоимость разработки. Просто нанять больше разработчиков уже не получается, на рынке труда нет столько квалифицированных кадров.
Традиционное тестирование в такой ситуации уже не работает и не справляется с ростом кодовой базы. Уход в автоматическое тестирование с помощью фаззинга на этом фоне выглядит логичным решением. Для Google призывает разработчиков писать фазз-тесты. Они подхватываются системой фаззинга и добавляются в остальной набор тестов.
Также на серверах Google развернут OSS-Fuzz. Это система непрерывного фаззинга проектов с открытыми исходниками. Сегодня на него подписано уже более 200 проектов. Если у вас есть востребованная и достаточно популярная библиотека, то вы сможешь поучаствовать. С вас — фаззер и инструкции по сборке последней версии, с Google — хостинг на кластере и гарантированный поток обнаруженных ошибок.
В 2017 году результаты работы этого проекта выглядели следующим образом: более двух тысяч найденных ошибок в шестидесяти проектах с открытым кодом. На сегодняшний день число подписанных на сервис проектов увеличилось более чем в три раза, а количество ошибок перевалило за десять тысяч. Около 35% этих ошибок — неопределенные ситуации, найденные с помощью санитайзера ubsan, примерно 15% — ошибки при работе с памятью и переполнение буферов, и более 10% — это другие ошибки самого разного рода.
Также в Google есть родственная система ClusterFuzz для браузера Chromium. Сегодня она поддерживает более 350 фаззеров, основная часть из них на libFuzzer и AFL, но есть и совершенно кастомные вещи. Система автоматически добавляет информацию о найденных ошибках и тестирует присланные решения.
Кроме того, в Google стараются популяризовать фаззинг за пределами Google — они проводят фаззатоны (по аналогии с хакатонами), недели фаззинга и выступают с докладами на профильных конференциях.
Как-то я задался вопросом: а сколько всего ошибок в Google обнаружили с помощью фаззинга? В 2017 году эта цифра была порядка пятнадцати тысяч, во всех проектах. То ли код у Google слишком плохой, то ли фаззеры слишком хорошие — я так пока еще и не определился.
Выводы
Фаззинг — это ни в коем случае не панацея. Он не заменяет другие методики тестирования, но и его заменить нельзя. Самое главное — это рабочая техника, которая хорошо дополняет арсенал поиска уязвимостей. Фаззеры в первую очередь стоит применять там, где возникают вопросы безопасности, на границе доверия и там, где есть пользовательский ввод. И пусть наши программы станут лучше.
