Ссылки на остальные статьи данного цикла:

От автора

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

Статья потенциально может содержать ошибки и неточности, автор открыт к диалогу (и самообразованию), если Вам есть что подсказать, исправить и скорректировать - пишите!

На протяжении всей статьи будут приведены ссылки на исходный код, который относится к последней (на момент написания статьи) стабильной версии AFL++ 4.30 . Всё, что описано в статье, основывается именно на этой версии, но с высокой вероятностью будет актуально как для более старых, так и для более новых версий, так как затрагивает основные механизмы работы этого фаззера.

Введние

AFL (American Fuzzy Lop) и его современная версия AFL++ —это инструмент для фаззинга, использующий метод, основанный на анализе покрытия кода (coverage-guided fuzzing). Этот подход позволяет отслеживать, какие участки программы активируются при подаче определенных входных данных. Таким образом собирается обратная связь и на основе этой информации AFL++ формирует набор тестовых данных, который постепенно расширяется за счет мутаций, чтобы охватить больше участков программы.

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

Давайте рассмотрим работу AFL++ на конкретном пример кода:

int main(){
	input = get_in(); функция-заглушка, для получение ввода из файл / stdin или каким-то другим способом.
	if(condition_A){
		...code_A...
	}else if(condition_B){
		...code_B ..
	}else{
		...code_C...
	}
	return 0;
}

Предположим, у нас есть определенный набор данных, подав который с помощью функции get_in(), мы выполним участок кода code_C.

Выполнение уникальной трассы кода будем называть edge (или ребро).
Набор данных, коотрый приводит к открытию нового edge будем называть seed (сид).
Совокупность seed'ов будем называть corpus (корпус).
Seed, который приводит к аварийному завершению исследуемой программы, будем называть crash (краш / падение).
Seed, который приводит к зависанию исследуемой программы, будем называть hangs (зависание).
Совокупность сидов, крашей и зависаний (выходные данные фаззинга), будем называть артефактами фаззинга.

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

Архитектура afl-fuzz

Типичная команда запуска фаззера выглядит примерно так:

afl-fuzz -i in -o out -- ./bin [@@]

Немного подробнее про опции:

-i - путь до директории с начальным (входным) корпусом данным (Важно! наборы данных в этой папке не должны приводить к падению или зависанию программы);
-o - путь, куда будут сохраняться выходные данные фаззера (артефакты)
-- такими символами разграничиваются опции утилиты afl-fuzz и опции исследуемой программы;
bin - путь до исследуемой программы
[@@] - специальная опция afl-fuzz. При отсутствии символов @@ фаззер будет подавать данные на программу из потока. Если запустить afl-fuzz, выставив символы @@, то на вход исследуемой программы сиды будут подаваться как файлы.

Итак, немного глубже рассмотрим то, как происходит запуск и работа утилиты afl-fuzz:

Когда запускается afl-fuzz, выполняется серия функций инициализации. После этого afl-fuzz создает дочерний процесс с помощью fork. Дочерний же процесс выполняет запуск исследуемой программы (цели) с помощью функции exec. Однако, фаззинг тестирование не начинается в дочернем процессе. Вместо этого дочерний процесс останавливается прямо перед вызовом функции main и становится forkserve'ом.

Этот forkserver создаёт новый дочерний процесс (дочерний процесс дочернего процесса - внук), и уже в этом процессе (внуке) запускается фаззинг тестирование.
Такой подход связан с тем, что fork работает гораздо быстрее, чем exec, поэтому резонно запускать фаззинг именно в процессе - внуке, а не в главном или дочернем процессе, ведь такой подход позволяет повысить скорость фаззинг тестирования, что очень важно.

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

Чтобы afl-fuzz мог взаимодействовать с бинарным файлом исследуемой программы (будем его так же называть целевым файлом), создаются два канала (pipe): управляющий канал (control pipe) и канал статуса (status pipe).

Управляющий канал находится по адресу FORKSRV_FD и используется для отправки сообщений управления в целевой бинарный файл. Этот канал доступен для чтения только целевому бинарному файлу и для записи только afl-fuzz.
Канал статуса находится по адресу FORKSRV_FD+1 и используется для передачи статусов обратно в afl-fuzz. Этот канал доступен для записи только целевому бинарному файлу и для чтения только afl-fuzz.

Управляющий канал используется для передачи управляющих сообщений в целевой бинарный файл. Канал статуса — для отправки ответных сообщений в afl-fuzz.

Теперь, когда у нас есть общее представление о том, как запускается afl-fuzz, давайте более подробно разберём почему AFL++ coverage-guided.

Инструментация и сбор покрытия кода

Для работы AFL++ бинарный файл должен быть инструментирован специальными инструкциями. Это необходимо для того, чтобы фаззер мог отслеживать открытие новых ребер с помощью мутированных данных при фаззинг тестировании. Это и называется покрытием кода. Такие инструментации могут быть как динмаческими, так и статическими. В рамках данной статьи будем обсуждать статический способ иснтрументирования кода с помощью компиляторов AFL++.
Факт открытия нового ребра сохраняется в специальный массив, который называется "картой покрытия" (подробнее о нём будет ниже).

В настоящее время AFL++ позволяет использовать различные системы инструментации кода для дальнейшего сбора покрытия, но наиболее распространнеными являются PCGUARD и LTO.
Для использования этих методов предусмотрены специальные обертки (wrappers) AFL++ над компилятором, которые реализованы в следующих бинарных файлах:

Инструментация PCGUARD активируется с помощью компилятора afl-clang-fast.
Инструментация LTO активируется с помощью компилятора afl-clang-lto.

Эти методы позволяют эффективно отслеживать выполнение программы и собирать подробные данные о покрытии кода.

В рамках данной статьи будем рассматривать только инструментации PCGUARD и LTO.

Об особенностях компиляции и выборе подходящего компилятор подробно рассказывается в документации на AFL++.
Если коротко, то изменения компилятора так же влияет и на скорость фаззинга.
Выбор способа инструментирования кода по скорости от лучшего к худшему:

LTO (afl-clang-lto) -> LLVM  (afl-clang-fast) -> GCC_plugin (afl-gcc-fast) -> GCC (afl-gcc)

Так же различные компиляторы отличаются не только скоростью фаззинга, но и требованием к версии clang и llvm.

Если чуть более обстоятельно, то советую почитать документацию

Одной из недооцененных проблем оригинального AFL были коллизии при заполнении карты покрытия. Эта проблема долгое время оставалась в тени, но приводила к потерям покрытия и снижению эффективности фаззинга.

В AFL++ эта проблема стала объектом пристального внимания. Частично ее удалось решить с выходом LLVM 9, где появилась функция LLVM: SplitEdge(). Благодаря этой функции стало возможным вставлять дополнительные блоки кода для инструментации на каждом ребре (edge) выполнения программы и инкрементировать соответствующий счетчик в карте покрытия. На основе этой возможности была создана собственная система инструментации под названием PCGUARD, основанная на механизмах LLVM. В результате компилятор afl-clang-fast, использующий эту систему, стал поддерживаться только с версии LLVM 9 и выше.

С выходом LLVM 12 появилась возможность реализовать подмену компоновщика (link-time optimizer, LTO), что позволило полностью устранить проблемы, связанные с коллизиями карты покрытия. Такой способ инструментации получил название LTO и поддерживается начиная с версии LLVM 12.

Теперь давайте рассмотрим инструментацию кода на практике.
Пусть у нас есть простейшая программа, которая принимает и обрабатывает данные из потока ввода:

#include 
#include 
#include 
#include 
#define SIZE 10

int main()
{
        char *str = readline("Enter your string \n");
        char * array = malloc(SIZE * sizeof(char));
        if(str == NULL)
                return 0;
        strcpy(array, str);
        printf("%s", array);
        free(str);
        free(array);
        return 0;
}

Скомпилируем её с инструментацией PCGUARD

afl-clang-fast main.c -lreadline -o bin_fast

И декомпилируем получившийся исполняемый файл в IDA PRO:

Внимательный читатель обратит внимание на появившиеся конструкции, которые сопровождает переменная _afl_area_ptr.
Помните выше мы ввели термин карта покрытия? Так вот - это _afl_area_ptr.

_afl_area_ptr - это массив, к которому осуществляется доступ каждый раз при достижении новой области. Обратите внимание, что есть доступ к __afl_area_ptr происходит во всех ветвлениях кода - в операторе if и в операторе else.

Давайте внимательнее разберем строки 12 и 20:

12 |  *((_BYTE *)_afl_area_ptr + dword_91A0) += __CFADD__(*((_BYTE *)_afl_area_ptr + dword_91A0), 1) + 1;
20 |  *((_BYTE *)_afl_area_ptr + dword_919C) += __CFADD__(*((_BYTE *)_afl_area_ptr + dword_919C), 1) + 1;

_afl_area_ptr по определению будем считать байтовым массивом, поэтому уберем приведение типов.
Метки dword_91A0 и dword_919C в IDA PRO явяются указателями на участок памяти и относятся к массиву нашей карты памяти, что видно далее:

Инструкции с паттерном *sancov* являются следствием инструментации компилятора - таким способом выделяется секция данных для карты покрытия по ребрам.

Наглядно видно, что метки dword_919C и dword_91A0 идут последовательно друг за другом и инициализируются нулем, а значит метка dword_919C является нулевым элементом массива карты покрытия, а dword_91A0 - первым.

Теперь преобразованные строки инструментации кода выглядят так:

12 |*_afl_area_ptr[1] += __CFADD__(*_afl_area_ptr, 1) + 1;
20 |*_afl_area_ptr[0] += __CFADD__(*_afl_area_ptr, 1) + 1;

__CFADD__ - макрос, который выполняет сложение (в нашем случае с единицей) с учетом переноса.

12 | _afl_area_ptr[1] =_afl_area_ptr[1] + 1 + (__afl_area_ptr[1] == 255 ? 1 : 0);
20 | _afl_area_ptr[0] =_afl_area_ptr[0] + 1 + (__afl_area_ptr[0] == 255 ? 1 : 0);

Исходник

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

Теперь обратим внимание на инструментацию LTO, на те же строки 12 и 20:

Инструментация LTO очень похожа на PCGUARD, за исключением того, что индекс _afl_area_ptr заполняется во время компиляции, а не во время выполнения. Это видно на тех же строках 12 и 20 - здесь уже нет подсчета адреса массива через адреса и метки, вместо этого используется адресация со смещением, где offset - смещение, было подсчитано уже во время компиляции и имеет конкретное значение.

Инструментация кода

Давайте попытаемся разобраться, как вообще происходит инструментация кода.
Если тезисно, то AFL++ использует механизмы сбора покрытия кода, предоставляемые LLVM

Подробнее об этом можно почитать в документации

Данный механизм позволяет вставлять специальные вызовы в пользовательские функции на уровне функций, базовых блоков и рёбер.
Для активации данного механизма необходимо добавить специальные флаги компиляции, благо AFL++ делает это самостоятельно, причем добавляет и ряд дополнительных опций: -fsanitize-coverage=trace-pc-guard,bb,no-prune,pc-table:

trace-pc-guard - инструментация сбора покрытия после каждого ребра;
bb - инструментация сбора покрытия после каждого базового блока;
no-prune - позволяет убрать отсечение некоторой информации при сборе покрытия;
pc-table - инструментация создает таблицу, которая содержит пары [PC (Адрес базового блока.), PCFlags (Флаги, описывающие свойства базового блока)]. Позволяет отслеживать пути выполнения, которые привели к определенному состоянию.

Согласно документации LLVM использование таких инструментаций приводит к добавлению специальных вызовов функций в определенные участки кода (в зависимости от выбранного типа инструментации). Также это накладывает на пользователя необходимость переодпределения реализаций данных функций, что реализовано в AFL++, например изменение инструментации создания PCs таблицы или изменение инструментации сбора покрытия после каждого ребра.

Конец

В следующей части подробно поговорим о инициализации и запуске forkservr'a

Разбираемся в устройстве AFL++. Часть 1