google/aflamerican fuzzy lop — фаззер, ориентированный на безопасность
Изначально разработан Михалом Залевски (Michal Zalewski) [email protected].
Если у вас нет времени читать этот файл, см. QuickStartGuide.txt.
Фаззинг — одна из самых мощных и проверенных стратегий выявления проблем безопасности в реальном программном обеспечении; именно с его помощью была найдена подавляющая часть ошибок удалённого выполнения кода и повышения привилегий, обнаруженных на сегодняшний день в критически важном с точки зрения безопасности ПО.
К сожалению, фаззинг также относительно поверхностен: слепые случайные мутации крайне редко позволяют достичь определённых путей выполнения в тестируемом коде, оставляя некоторые уязвимости вне досягаемости этого метода.
Предпринималось множество попыток решить эту проблему. Один из ранних подходов, пионером которого стал Тэвис Орманди (Tavis Ormandy), — дистилляция корпуса. Метод опирается на сигналы покрытия, чтобы отобрать подмножество интересных начальных входных данных из огромного качественного корпуса файлов-кандидатов, а затем фаззить их традиционными средствами. Этот подход работает исключительно хорошо, но требует наличия такого корпуса под рукой. Кроме того, измерения блочного покрытия дают лишь очень упрощённое понимание состояния программы и менее полезны для направления усилий фаззинга в долгосрочной перспективе.
Другие, более сложные исследования сосредоточены на таких методах, как анализ потока управления программы («конколическое выполнение»), символьное выполнение или статический анализ. Все эти методы чрезвычайно перспективны в экспериментальных условиях, но на практике страдают от проблем с надёжностью и производительностью — и в настоящее время не предлагают жизнеспособной альтернативы «глупым» методам фаззинга.
American Fuzzy Lop — это фаззер переборного типа, сочетающийся с чрезвычайно простым, но исключительно надёжным инструментируемым генетическим алгоритмом. Он использует модифицированную форму покрытия рёбер графа потока управления, чтобы без труда улавливать тонкие локальные изменения в потоке управления программы.
Если несколько упростить, общий алгоритм можно свести к следующему:
загрузить предоставленные пользователем начальные тестовые примеры в очередь;
взять следующий входной файл из очереди;
попытаться сократить тестовый пример до минимального размера, не изменяющего измеряемое поведение программы;
многократно мутировать файл, используя сбалансированный и хорошо изученный набор традиционных стратегий фаззинга;
если любая из полученных мутаций привела к новому переходу состояния, зафиксированному инструментацией, добавить мутированный результат как новую запись в очередь;
перейти к шагу 2.
Обнаруженные тестовые примеры также периодически прореживаются, чтобы исключить те, что устарели из-за более новых находок с более высоким покрытием; кроме того, применяются и другие шаги минимизации усилий под управлением инструментации.
Побочным результатом процесса фаззинга является создание небольшого самодостаточного корпуса интересных тестовых примеров. Они чрезвычайно полезны для подготовки других режимов тестирования, требующих больших трудозатрат или ресурсов, — например, для стресс-тестирования браузеров, офисных приложений, графических пакетов или закрытых инструментов.
Фаззер тщательно протестирован и обеспечивает производительность «из коробки», значительно превосходящую слепой фаззинг или инструменты, основанные только на покрытии.
Когда доступен исходный код, инструментация может быть внедрена с помощью сопутствующего инструмента, который работает как замена gcc или clang в любом стандартном процессе сборки стороннего кода.
Инструментация оказывает довольно умеренное влияние на производительность; в сочетании с другими оптимизациями, реализованными в afl-fuzz, большинство программ можно фаззить так же быстро или даже быстрее, чем с помощью традиционных инструментов.
Правильный способ перекомпиляции целевой программы может различаться в зависимости от особенностей процесса сборки, но почти универсальный подход выглядит так:```shell $ CC=/path/to/afl/afl-gcc ./configure $ make clean all
Для программ на C++ также стоит задать `CXX=/path/to/afl/afl-g++`.
Обёртки clang (`afl-clang` и `afl-clang++`) используются аналогично;
пользователи clang также могут воспользоваться более производительным режимом инструментирования,
как описано в llvm_mode/README.llvm.
При тестировании библиотек нужно найти или написать простую программу, которая читает
данные из stdin или из файла и передаёт их тестируемой библиотеке. В таком
случае крайне важно слинковать этот исполняемый файл со статической версией
инструментированной библиотеки либо убедиться, что загружается корректный файл `.so`
во время выполнения (обычно задаётся через `LD_LIBRARY_PATH`). Самый простой вариант — статическая
сборка, обычно возможная с помощью:```shell
$ CC=/path/to/afl/afl-gcc ./configure --disable-shared
Установка AFL_HARDEN=1 при вызове 'make' приведёт к тому, что обёртка CC
автоматически включит параметры усиления защиты кода, облегчающие обнаружение
простых ошибок памяти. Libdislocator, вспомогательная библиотека, входящая в состав AFL (см.
libdislocator/README.dislocator), также может помочь выявить проблемы повреждения кучи.
PS. Пользователям ASAN рекомендуется просмотреть файл notes_for_asan.txt на предмет важных предостережений.
Когда исходный код НЕ доступен, фаззер предлагает экспериментальную поддержку для быстрой инструментации бинарных «чёрных ящиков» на лету. Это достигается с помощью версии QEMU, работающей в малоизвестном режиме "эмуляции пользовательского пространства".
QEMU — это отдельный от AFL проект, но вы можете без труда собрать функцию, выполнив:```shell $ cd qemu_mode $ ./build_qemu_support.sh
Дополнительные инструкции и предостережения см. в qemu_mode/README.qemu.
Этот режим примерно в 2-5 раз медленнее инструментирования на этапе компиляции,
хуже поддается параллелизации и может иметь некоторые другие особенности.
## 5) Выбор исходных тестовых примеров
Для корректной работы фаззеру требуется один или несколько исходных файлов, которые
содержат хороший пример входных данных, обычно ожидаемых целевым
приложением. Есть два основных правила:
- Делайте файлы небольшими. Идеально — менее 1 кБ, хотя это не строго обязательно.
Обсуждение того, почему размер важен, см. в [perf_tips.txt](https://github.com/google/afl/blob/HEAD/docs/perf_tips.txt).
- Используйте несколько тестовых примеров только в том случае, если они функционально отличаются
друг от друга. Нет смысла использовать пятьдесят разных отпускных фотографий
для фаззинга библиотеки для работы с изображениями.
Множество хороших примеров исходных файлов можно найти в подкаталоге testcases/
который поставляется вместе с этим инструментом.
PS. Если для проверки доступен большой корпус данных, возможно, вы захотите использовать
утилиту afl-cmin, чтобы определить подмножество функционально различных файлов, которые
задействуют разные пути выполнения кода в целевом бинарном файле.
## 6) Фаззинг бинарных файлов
Сам процесс фаззинга выполняется утилитой afl-fuzz. Эта программа
требует каталог только для чтения с исходными тестовыми примерами, отдельное место для
хранения результатов, а также путь к бинарному файлу для тестирования.
Для целевых бинарных файлов, принимающих входные данные напрямую из stdin, обычный синтаксис выглядит так:```shell
$ ./afl-fuzz -i testcase_dir -o findings_dir /path/to/program [...params...]
Для программ, которые принимают ввод из файла, используйте '@@', чтобы указать место в командной строке цели, куда должно быть подставлено имя входного файла. Фаззер подставит его за вас:```shell $ ./afl-fuzz -i testcase_dir -o findings_dir /path/to/program @@
Вы также можете использовать опцию -f, чтобы записывать мутированные данные в конкретный файл. Это полезно, если программа ожидает определённое расширение файла или что-то подобное.
Неинструментированные бинарники можно фаззить в режиме QEMU (добавьте -Q в командной строке) или в традиционном режиме «слепого» фаззера (укажите -n).
Вы можете использовать -t и -m, чтобы переопределить стандартные ограничения по времени ожидания и памяти для выполняемого процесса; редкие примеры целей, которым могут понадобиться такие настройки, включают компиляторы и видеодекодеры.
Советы по оптимизации производительности фаззинга обсуждаются в [perf_tips.txt](https://github.com/google/afl/blob/HEAD/docs/perf_tips.txt).
Обратите внимание, что afl-fuzz начинает с выполнения набора детерминированных шагов фаззинга, которые могут занять несколько дней, но обычно дают аккуратные тестовые примеры. Если вы хотите получить быстрые и «грязные» результаты сразу — как в zzuf и других традиционных фаззерах — добавьте опцию -d в командную строку.
## 7) Интерпретация вывода
Смотрите файл [status_screen.txt](https://github.com/google/afl/blob/HEAD/docs/status_screen.txt) для получения информации о том, как интерпретировать отображаемую статистику и следить за состоянием процесса. Обязательно обратитесь к этому файлу, особенно если какие-либо элементы интерфейса выделены красным.
Процесс фаззинга будет продолжаться, пока вы не нажмёте Ctrl-C. Как минимум, вы должны позволить фаззеру завершить один цикл очереди, что может занять от пары часов до недели или около того.
В выходном каталоге создаются и обновляются в реальном времени три подкаталога:
- queue/ - тестовые примеры для каждого отличительного пути выполнения, а также все исходные файлы, заданные пользователем. Это синтезированный корпус, упомянутый в разделе 2.
Перед использованием этого корпуса для любых других целей вы можете уменьшить его размер с помощью инструмента afl-cmin. Этот инструмент найдёт меньший поднабор файлов, обеспечивающий эквивалентное покрытие рёбер.
- crashes/ - уникальные тестовые примеры, которые заставляют тестируемую программу получать фатальный сигнал (например, SIGSEGV, SIGILL, SIGABRT). Записи сгруппированы по полученному сигналу.
- hangs/ - уникальные тестовые примеры, которые заставляют тестируемую программу выходить по тайм-ауту. Стандартное ограничение времени до того, как что-то классифицируется как зависание, — это большее из 1 секунды и значения параметра -t.
Это значение можно точно настроить, задав AFL_HANG_TMOUT, но это редко бывает необходимо.
Сбои и зависания считаются «уникальными», если связанные с ними пути выполнения содержат какие-либо переходы состояний, не наблюдавшиеся в ранее зафиксированных ошибках. Если один и тот же баг может быть достигнут несколькими способами, в начале процесса будет некоторое завышение счётчика, но оно должно быстро сойти на нет.
Имена файлов сбоев и зависаний связаны с родительскими, не вызывающими ошибок записями очереди. Это должно помочь при отладке.
Если вы не можете воспроизвести сбой, найденный afl-fuzz, наиболее вероятная причина в том, что вы не задаёте тот же предел памяти, что и инструмент. Попробуйте:```shell
$ LIMIT_MB=50
$ ( ulimit -Sv $[LIMIT_MB << 10]; /path/to/tested_binary ... )
Измените LIMIT_MB в соответствии с параметром -m, переданным в afl-fuzz. На OpenBSD, также измените -Sv на -Sd.
Любая существующая выходная директория также может использоваться для возобновления прерванных заданий; попробуйте:```shell $ ./afl-fuzz -i- -o existing_output_dir [...etc...]
Если у вас установлен gnuplot, вы также можете создавать наглядные графики для любого
активного задания фаззинга с помощью afl-plot. Пример того, как это выглядит,
см. на [http://lcamtuf.coredump.cx/afl/plot/](http://lcamtuf.coredump.cx/afl/plot/).
## 8) Параллельный фаззинг
Каждый экземпляр afl-fuzz занимает примерно одно ядро. Это означает, что на
многоядерных системах параллелизация необходима для полного использования аппаратных ресурсов.
Советы по фаззингу общего целевого приложения на нескольких ядрах или нескольких сетевых
машинах см. в [parallel_fuzzing.txt](https://github.com/google/afl/blob/HEAD/docs/parallel_fuzzing.txt).
Режим параллельного фаззинга также предлагает простой способ взаимодействия AFL с другими
фаззерами, движками символьного или конколического исполнения и т.д.; опять же, советы см. в
последнем разделе [parallel_fuzzing.txt](https://github.com/google/afl/blob/HEAD/docs/parallel_fuzzing.txt).
## 9) Словари фаззера
По умолчанию движок мутаций afl-fuzz оптимизирован для компактных форматов данных -
например, изображений, мультимедиа, сжатых данных, синтаксиса регулярных выражений или шелл-
скриптов. Он несколько менее подходит для языков с особенно многословным и
избыточным синтаксисом - в частности, HTML, SQL или JavaScript.
Чтобы избежать хлопот с созданием синтаксически ориентированных инструментов, afl-fuzz предоставляет способ
подпитывать процесс фаззинга необязательным словарём языковых ключевых слов,
магических заголовков или других специальных токенов, связанных с целевым типом данных,
-- и использовать его для восстановления базовой грамматики на лету:
[http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html](http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html)
Чтобы воспользоваться этой функцией, сначала нужно создать словарь в одном из двух
форматов, описанных в dictionaries/README.dictionaries; а затем указать фаззеру
на него через опцию -x в командной строке.
(В этом подкаталоге также уже предоставлено несколько распространённых словарей.)
Нет возможности задать более структурированные описания базового
синтаксиса, но фаззер, скорее всего, разберётся с некоторыми аспектами на основе
одной лишь обратной связи от инструментации. Это действительно работает на практике, например:
[http://lcamtuf.blogspot.com/2015/04/finding-bugs-in-sqlite-easy-way.html](http://lcamtuf.blogspot.com/2015/04/finding-bugs-in-sqlite-easy-way.html)
PS. Даже если явный словарь не задан, afl-fuzz попытается извлечь
существующие синтаксические токены из входного корпуса, внимательно наблюдая за
инструментацией во время детерминированных инверсий байтов. Это работает для некоторых типов
парсеров и грамматик, но не так хорошо, как режим -x.
Если словарь действительно трудно подобрать, есть и другой вариант: дать AFL поработать
некоторое время, а затем использовать библиотеку захвата токенов, которая поставляется как вспомогательная
утилита вместе с AFL. За подробностями обратитесь к libtokencap/README.tokencap.
## 10) Триаж аварийных сбоев
Группировка сбоев на основе покрытия обычно даёт небольшой набор данных, который
можно быстро разобрать вручную или с помощью очень простого скрипта для GDB или Valgrind.
Каждый сбой также можно проследить до его родительского тестового примера без сбоя в
очереди, что упрощает диагностику неисправностей.
Тем не менее важно признать, что некоторые сбои при фаззинге могут быть
сложны для быстрой оценки на предмет эксплуатируемости без большого объёма отладки и
анализа кода. Для содействия этой задаче afl-fuzz поддерживает поистине уникальный
режим «исследования сбоев», включаемый флагом -C.
В этом режиме фаззер принимает на вход один или несколько аварийных тестовых примеров
и использует свои стратегии фаззинга на основе обратной связи, чтобы очень быстро перечислить все
пути выполнения, которых можно достичь в программе, сохраняя её в
аварийном состоянии.
Мутации, не приводящие к сбою, отклоняются; также отклоняются любые изменения, которые
не влияют на путь выполнения.
Результатом является небольшой корпус файлов, которые можно очень быстро изучить, чтобы увидеть,
какой степенью контроля атакующий обладает над адресом сбоя, или
возможно ли обойти первоначальное чтение за пределами границ - и увидеть, что находится
ниже.
Ах да, ещё кое-что: для минимизации тестовых примеров попробуйте afl-tmin. Этот инструмент
можно использовать очень простым способом:```shell
$ ./afl-tmin -i test_case -o minimized_result -- /path/to/program [...]
Инструмент работает как с падающими, так и с непадающими тестовыми примерами. В режиме падений он охотно принимает как инструментированные, так и неинструментированные бинарники. В режиме без падений минимизатор полагается на стандартную инструментацию AFL, чтобы сделать файл проще, не изменяя путь выполнения.
Минимизатор принимает синтаксис -m, -t, -f и @@ в манере, совместимой с afl-fuzz.
Ещё одним недавним дополнением к AFL является инструмент afl-analyze. Он принимает входной файл, пытается последовательно инвертировать байты и наблюдает за поведением тестируемой программы. Затем он цветово кодирует входные данные в зависимости от того, какие разделы выглядят критическими, а какие нет; хотя это и не пуленепробиваемо, он часто может дать быстрое понимание сложных форматов файлов. Дополнительную информацию о его работе можно найти ближе к концу technical_details.txt.
Фаззинг — это замечательный и недооценённый метод для обнаружения непадающих ошибок проектирования и реализации тоже. Немало интересных ошибок было найдено путём модификации целевых программ, чтобы они вызывали abort(), когда, например:
Две библиотеки больших чисел выдают разные результаты при получении одного и того же сгенерированного фаззером входа,
Библиотека обработки изображений выдаёт разные результаты, когда её просят декодировать одно и то же входное изображение несколько раз подряд,
Библиотека сериализации / десериализации не выдаёт стабильных результатов при итеративной сериализации и десериализации данных, предоставленных фаззером,
Библиотека сжатия выдаёт выходные данные, не согласующиеся с входным файлом, когда её просят сжать, а затем распаковать конкретный блок данных.
Реализация таких или подобных проверок корректности обычно занимает очень мало времени;
если вы сопровождаете конкретный пакет, вы можете сделать этот код условным с помощью
#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION (флаг, также используемый
в libfuzzer) или #ifdef __AFL_COMPILER (этот только для AFL).
Имейте в виду, что, как и многие другие вычислительно интенсивные задачи, фаззинг может создавать нагрузку на ваше оборудование и на операционную систему. В частности:
Ваш процессор будет сильно нагреваться и потребует адекватного охлаждения. В большинстве случаев, если охлаждение недостаточно или перестаёт работать должным образом, частота процессора будет автоматически снижена. Тем не менее, особенно при фаззинге на менее подходящем оборудовании (ноутбуках, смартфонах и т.п.), не полностью исключено, что что-то может выйти из строя.
Целевые программы могут хаотично захватывать гигабайты памяти или заполнять дисковое пространство мусорными файлами. AFL пытается обеспечивать базовые ограничения памяти, но не может предотвратить каждый возможный сбой. Суть в том, что не следует заниматься фаззингом на системах, где перспектива потери данных не является приемлемым риском.
Фаззинг включает миллиарды операций чтения и записи в файловую систему. На современных системах это обычно активно кэшируется, что приводит к довольно скромному «физическому» вводу-выводу, но существует множество факторов, которые могут изменить это уравнение. Вы несёте ответственность за мониторинг потенциальных проблем; при очень интенсивном вводе-выводе срок службы многих HDD и SSD может сократиться.
Хороший способ контролировать дисковый ввод-вывод в Linux — команда 'iostat':```shell $ iostat -d 3 -x -k [...optional disk ID...]
## 13) Known limitations & areas for improvement
Here are some of the most important caveats for AFL:
- AFL detects faults by checking for the first spawned process dying due to
a signal (SIGSEGV, SIGABRT, etc). Programs that install custom handlers for
these signals may need to have the relevant code commented out. In the same
vein, faults in child processed spawned by the fuzzed target may evade
detection unless you manually add some code to catch that.
- As with any other brute-force tool, the fuzzer offers limited coverage if
encryption, checksums, cryptographic signatures, or compression are used to
wholly wrap the actual data format to be tested.
To work around this, you can comment out the relevant checks (see
experimental/libpng_no_checksum/ for inspiration); if this is not possible,
you can also write a postprocessor, as explained in
experimental/post_library/.
- There are some unfortunate trade-offs with ASAN and 64-bit binaries. This
isn't due to any specific fault of afl-fuzz; see [notes_for_asan.txt](https://github.com/google/afl/blob/HEAD/docs/notes_for_asan.txt)
for tips.
- There is no direct support for fuzzing network services, background
daemons, or interactive apps that require UI interaction to work. You may
need to make simple code changes to make them behave in a more traditional
way. Preeny may offer a relatively simple option, too - see:
https://github.com/zardus/preeny
Some useful tips for modifying network-based services can be also found at:
https://www.fastly.com/blog/how-to-fuzz-server-american-fuzzy-lop
- AFL doesn't output human-readable coverage data. If you want to monitor
coverage, use afl-cov from Michael Rash: https://github.com/mrash/afl-cov
- Occasionally, sentient machines rise against their creators. If this
happens to you, please consult http://lcamtuf.coredump.cx/prep/.
Beyond this, see INSTALL for platform-specific tips.
## 14) Special thanks
Many of the improvements to afl-fuzz wouldn't be possible without feedback,
bug reports, or patches from:```
Jann Horn Hanno Boeck
Felix Groebert Jakub Wilk
Richard W. M. Jones Alexander Cherepanov
Tom Ritter Hovik Manucharyan
Sebastian Roschke Eberhard Mattes
Padraig Brady Ben Laurie
@dronesec Luca Barbato
Tobias Ospelt Thomas Jarosch
Martin Carpenter Mudge Zatko
Joe Zbiciak Ryan Govostes
Michael Rash William Robinet
Jonathan Gray Filipe Cabecinhas
Nico Weber Jodie Cunningham
Andrew Griffiths Parker Thompson
Jonathan Neuschfer Tyler Nighswander
Ben Nagy Samir Aguiar
Aidan Thornton Aleksandar Nikolich
Sam Hakim Laszlo Szekeres
David A. Wheeler Turo Lamminen
Andreas Stieger Richard Godbee
Louis Dassy teor2345
Alex Moneger Dmitry Vyukov
Keegan McAllister Kostya Serebryany
Richo Healey Martijn Bogaard
rc0r Jonathan Foote
Christian Holler Dominique Pelle
Jacek Wielemborek Leo Barnes
Jeremy Barnes Jeff Trull
Guillaume Endignoux ilovezfs
Daniel Godas-Lopez Franjo Ivancic
Austin Seipp Daniel Komaromy
Daniel Binderman Jonathan Metzman
Vegard Nossum Jan Kneschke
Kurt Roeckx Marcel Bohme
Van-Thuan Pham Abhik Roychoudhury
Joshua J. Drake Toby Hutton
Rene Freingruber Sergey Davidoff
Sami Liedes Craig Young
Andrzej Jackowski Daniel Hodson
Спасибо!
Вопросы? Проблемы? Сообщения об ошибках? Пожалуйста, используйте GitHub.
Для проекта также существует список рассылки; чтобы присоединиться, отправьте письмо на [email protected]. Или, если вы предпочитаете сначала просмотреть архивы, попробуйте: https://groups.google.com/group/afl-users.