Автор: Иннокентий Сенновский

Как найти баги, о которых вы и не догадывались, или что такое фаззинг

Все уже привыкли, что программу надо покрывать тестами, чтобы потом не было стыдно. Но вот проблема: разработчик может защититься только от багов, которые он способен предугадать. Да и тестировщик вряд ли сможет перебрать все варианты входных данных, которые приводят к ошибке.

Чтобы справиться с этой проблемой, придумали фаззеры — инструменты тестирования, которые сами пытаются найти баги в программе. В этой статье я рассмотрю, какие они вообще бывают (для C/C++, потому что баги в таких программах особенно болезненны), но сделаю упор на Greybox-фаззеры (почему, расскажу в статье).

Речь пойдет не об инструментах пентестеров, вроде Dirbuster или Burp Suite, которые проверяют программы на типичные проблемы и затрагивают лишь поверхность, а о фаззерах вроде AFL и LibFuzzer, которые тестируют программу, руководствуясь ее внутренним строением и механизмами.

Что такое фаззер

Давайте начнем с того, что такое собственно фаззинг.

Допустим, у нас есть программа, которую мы хотим протестировать. Будем называть ее на заморский манер — PUT (Program Under Test).

В академической среде фаззинг — это когда мы исполняем PUT с использованием входных данных, которые расширяют входное пространство PUT. Если по-простому, то пытаемся найти данные, которые выявят новую функциональность в программе.

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

Фаззер, как следует из названия, это инструмент для проведения фаззинга. Его общий алгоритм можно высокоуровнево представить так:

def FuzzTesting (Corpus, Tlimit):
    BugsFound = set()
    Corpus = Preprocess(Corpus)
    while (Telapsed < Tlimit) and Continue(Corpus):
        configuration = Schedule(Corpus,Telapsed, Tlimit)
        testcases = InputGen(configuration)
        Bugs_new, execinfos = InputEval(configuration, testcases, BugOracle)
        Corpus = ConfUpdate(Corpus, Configuration, execinfos)
        BugsFound.add(Bugs_new)
    return (Corpus,BugsFound)

Сразу поясню две сущности, которые могли показаться непонятными:

• Corpus (seed pool, корпус) — набор используемых фаззером входных данных, или тест-кейсов. Обычно фазз-тестирование запускают не на пустом корпусе. Если тестируют какую-то функцию, то сначала собирают образцы данных, которые подаются в нее при нормальной работе. Допустим, тестируя парсер изображений, подготавливают набор самых разных файлов, которые он должен обрабатывать. Это позволяет быстрее добраться до интересной функциональности и не тратить время на прохождение скучных проверок, таких как сигнатуры файлов.
• Bug Oracle (оракул багов) — программа или модуль, которые детектируют нарушение политики безопасности, например опасные обращения к памяти или запись файла не туда. К оракулам багов я еще вернусь дальше в статье.

Таким образом, фаззер:

1. Обрабатывает начальные тест-кейсы, создавая корпус.
2. Входит в цикл фаззинга, который продолжается, пока не закончится время или не сработает некое условие.
3. Внутри цикла генерирует конфигурацию, а из нее — новые тест-кейсы.
4. Обрабатывает эти тест-кейсы, получает баги и информацию об исполнении.
5. На основе информации об исполнении расширяет корпус и добавляет баги.
6. После окончания фаззинга выдает корпус и найденные баги.
   
   

   Виды фаззинга

Основных видов фаззинга — три:

1. Blackbox.
2. Whitebox.
3. Greybox.

В каждой статье должна быть хоть одна кринжовая картинка. Вот она:

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

Whitebox — самый тяжелый вариант (инструменты — KLEE и подобные). У него есть три самых явных подвида:

1. Symbolic Execution (символическое, оно же символьное, исполнение). При нем вместо преобразования кода программы в исполняемый код компилятор выплевывает набор формул, который описывает всю работу программы. Далее специальный решатель (обычно это SMT-решатель вроде z3) преобразует SMT в SAT и пытается найти определенные пространства решений. Формулы модифицируются таким образом, чтобы пройти каждую ветвь исполнения изначальной программы.

   
   

   Если вы хотите поиграться с таким фаззером, воспользуйтесь старым и проверенным KLEE или более новым и, на мой взгляд, простым SymCC. Последний очень советую, если надо протестировать маленькую программу для парсинга файлов.

   
   

   У всех машин для символического исполнения есть одна проблема: в общем случае решение SAT, к которому в итоге приводятся программы, является NP-полной задачей. SMT-решатели находят решения за счет крайне эффективного упрощения теорем на каждом этапе, но чем больше программа и чем глубже в нее надо проникнуть, тем менее вероятно, что решатель справится за приемлемое время.

   
   

2. Concolic Execution (конколическое исполнение). Это попытка немного упростить символическое исполнение за счет обогащения решателя данными от реального исполнения программы. Выполнили программу на известном тест-кейсе → сохранили данные → запустили решать попадание на другую ветвь с полученной информацией.

   
   

3. Data Taint Tracking (термин на русском я не встречал). Это самый легкий с точки зрения вычислений метод, который относят к Whitebox-фаззингу. При исполнении программы все байты, которые зависят от определенных байтов входных данных, помечаются (taint). За счет этого фаззер отслеживает, что влияет на выбор пути исполнения, данные на какой позиции нужно менять.

   
   

Blackbox туповат, Whitebox неэффективен для сложных программ и ест много ресурсов, поэтому придумали нечто среднее.

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

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

Покрытие программы используется как лакмусовая бумажка, чтобы определить, надо ли добавлять тест-кейс в корпус или он бесполезен. Если исполнение PUT достигает новой части программы (например, изменяет условие в каком-то if), то фаззер детектирует это событие и добавляет тест-кейс в корпус. Таким образом покрытие программы расширяется и вероятность обнаружения какой-то проблемы увеличивается.

Дальше в статье я сосредоточусь именно на Greybox как на самом эффективном виде фазз-тестирования.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(int argc, char* argv[]) {
    int coeffs[]={10, 2 , -3, 5, 6, 7, -11, 4, 0};
    int results[]={49, 70, -39};
    printf("What's the solution to the following system of  equations?\n");
    for (int i=0; i<3; i++){
        printf("%d*x0 ",coeffs[i*3]);
        for (int j=1; j<3; j++){
            int curCoeff=coeffs[i*3+j];
            if ( curCoeff < 0){
                printf("- %d*x%d ",abs(curCoeff),j);
            } else if (curCoeff > 0){
                printf("+ %d*x%d ",curCoeff,j);
            }
        }
        printf("= %d;\n",results[i]);
    }
    int solution[3];
    ssize_t result;
    printf("Reading %lu bytes for x1, x2, x3:\n",sizeof(int)*3);
    for (int i = 0; i<3; i++)
    {
        if(read(STDIN_FILENO,&solution[i],sizeof(int))!=sizeof(int)){
            printf ("Error reading\n");
            return -1;
        }
    }
    int success=1;
    for (int i = 0; i < 3; i++){
        int accumulator=0;
        for (int j =0; j < 3; j++) {
            accumulator+=coeffs[i*3+j]*solution[j];
        }
        if (accumulator!=results[i]){
            success=0;
            break;
        }
    }
    if (success)
        printf("Hooray!!!\n");
    else
        printf("Goodbye, DumDum\n");
    return 0;
}

docker run --name=symcc_container -v $(pwd):/build_dir -it --rm symcc

symcc symcc_example.c -o symcc_example

clang symcc_example.c -o symmcc_example_nosym

mkdir output/{1,2,3,4};
echo -n "TESTTESTTEST" > first_input;

Внутренности Greybox-фаззеров

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

(Я остановлюсь на этих четырех аспектах для краткости — конечно, ими дело не ограничивается.)

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

Как уже сказано выше, Greybox-фаззеры используют покрытие, чтобы понять, какие тест-кейсы полезны.

Покрытие фаззер может понимать по-разному. Вот несколько типов, которые встречаются в доступных решениях:

1. Покрытие базовых блоков (Basic Block Coverage). Это самый примитивный способ измерения покрытия программы, потому что он игнорирует все связи между блоками.
2. Покрытие ветвей (Edge Coverage). В этом случае в качестве единицы покрытия рассматривается направленное ребро между базовыми блоками. Оно было введено фаззером AFL и быстро подтвердило свою эффективность: оказалось, что с его помощью можно быстрее обнаруживать интересные тест-кейсы.
3. Покрытие N-грам (N-gram coverage). При этом типе покрытия фаззер следит за последовательностью из нескольких блоков.
4. Контекстное покрытие. Здесь фаззер следит не просто за покрытыми базовыми блоками или ветвями, но и за тем, откуда была вызвана функция, в которой оказались пройдены данные блок или ветвь.

Во всех случаях при обнаружении нового покрытия фаззер добавляет тест-кейс в корпус.

По умолчанию в большинстве современных фаззеров используется покрытие ветвей.

Механизм исполнения PUT

Механизм исполнения влияет на быстродействие фаззера, то есть на количество тест-кейсов, которые фаззер успеет обработать за секунду.

В самом примитивном варианте фаззер заново запускает программу на каждый тест-кейс.

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

Чтобы не терять время, предусмотрели три более сложных механизма:

1. Fork mode. Процесс запускают один раз, после чего для каждого тест-кейса делают форк процесса. Это позволяет пропустить инициализацию при каждом тест-кейсе, и подготовка занимает намного меньше времени, чем при создании все новых и новых процессов.

   
   

   Fork — самый простой способ ускориться, если приложение принимает данные из STDIN. Этот механизм встроен в фаззер AFL++.

   
   

2. Fork mode ++ (название мое). Процесс запускается один раз, после чего делается форк и сохраняется содержимое всех страниц. Как только исполнение на тест-кейсе завершено, модуль проверяет, какие страницы надо восстановить, и заменяет только их.

   
   

   Этот механизм написали тоже для AFL++. Неудобство в том, что для его использования нужен специальный модуль ядра, который следит, какие страницы были изменены (флаг Dirty в структурах пэйджинга). Зато этот способ быстрее Fork: со слов разработчиков модуля, прирост скорости составляет от 20 до 360% в зависимости от PUT.

   
   

3. Persistent mode. Программа инициализируется, доходит до функции X, после чего эта функция исполняется в цикле с подменой аргументов.

   
   

   Это самый быстрый с точки зрения фаззинга способ, но у него есть свои минусы. Во-первых, обычно он требует множества модификаций PUT. Во-вторых, он может вызывать проблемы, так как отдельные исполнения перестают быть независимыми. В-третьих, он создает false positive: так как процесс не меняется, есть большой риск изменения состояния процесса и наведенных ошибок. Поэтому обычно цикл исполняется N-е количество раз, после чего либо создается новый форк процесса из оригинального состояния, либо процесс перезапускается.

   
   

   Persistent mode — основа работы фаззера libFuzzer, но его можно добавить и в AFL++ (в документации все объясняется).

   
   

Модель тест-кейсов

Эта модель отвечает за то, как фаззер мутирует и воспринимает наши тест-кейсы.

Основных вариантов два:

1. Фаззинг бинарных данных.
2. Фаззинг на основе предоставленной модели (Structure-Aware Fuzzing).

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

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

1. Алфавит.
2. Набор фиксированных токенов.
3. Зависимости между токенами.
4. Наличие кусков (chunk) данных определенной структуры.

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

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

Вот несколько форматов модели данных:

1. Форма, используемая в Peach Fuzzer. Останавливаться на ней мы не будем, потому что она не распространена.

   
   

2. Расширенная форма Бэкуса-Наура (РБНФ/EBNF), которую, например, использует грамматический мутатор AFL++. Она наиболее удобна для тестирования текстовых форматов и протоколов, таких как SMTP. К примеру, здесь представлена сохраненная в JSON грамматика для JSON:

   
   

   {
   "<start>": [["<json>"]],
   "<json>": [["<element>"]],
   "<element>": [["<ws>", "<value>", "<ws>"]],
   "<value>": [["<object>"], ["<array>"], ["<string>"], ["<number>"],
               ["true"], ["false"],
               ["null"]],
   "<object>": [["{", "<ws>", "}"], ["{", "<members>", "}"]],
   "<members>": [["<member>", "<symbol-2>"]],
   "<member>": [["<ws>", "<string>", "<ws>", ":", "<element>"]],
   "<array>": [["[", "<ws>", "]"], ["[", "<elements>", "]"]],
   "<elements>": [["<element>", "<symbol-1-1>"]],
   "<string>": [["\"", "<characters>", "\""]],
   "<characters>": [["<character-1>"]],
   "<character>": [["0"], ["1"], ["2"], ["3"], ["4"], ["5"], ["6"], ["7"],
                   ["8"], ["9"], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"],
                   ["g"], ["h"], ["i"], ["j"], ["k"], ["l"], ["m"], ["n"],
                   ["o"], ["p"], ["q"], ["r"], ["s"], ["t"], ["u"], ["v"],
                   ["w"], ["x"], ["y"], ["z"], ["A"], ["B"], ["C"], ["D"],
                   ["E"], ["F"], ["G"], ["H"], ["I"], ["J"], ["K"], ["L"],
                   ["M"], ["N"], ["O"], ["P"], ["Q"], ["R"], ["S"], ["T"],
                   ["U"], ["V"], ["W"], ["X"], ["Y"], ["Z"], ["!"], ["#"],
                   ["$"], ["%"], ["&"], ["\""], ["("], [")"], ["*"], ["+"],
                   [","], ["-"], ["."], ["/"], [":"], [";"], ["<"], ["="],
                   [">"], ["?"], ["@"], ["["], ["]"], ["^"], ["_"], ["`"],
                   ["{"], ["|"], ["}"], ["~"], [" "], ["<esc>"], ["'"]],
   "<esc>": [["\\","<escc>"]],
   "<escc>": [["\\"],["b"],["f"], ["n"], ["r"],["t"],["\""]],
   "<number>": [["<int>", "<frac>", "<exp>"]],
   "<int>": [["<digit>"], ["<onenine>", "<digits>"], ["-", "<digits>"],
             ["-", "<onenine>", "<digits>"]],
   "<digits>": [["<digit-1>"]],
   "<digit>": [["0"], ["<onenine>"]],
   "<onenine>": [["1"], ["2"], ["3"], ["4"], ["5"], ["6"], ["7"], ["8"],
                 ["9"]],
   "<frac>": [[], [".", "<digits>"]],
   "<exp>": [[], ["E", "<sign>", "<digits>"], ["e", "<sign>", "<digits>"]],
   "<sign>": [[], ["+"], ["-"]],
   "<ws>": [["<sp1>", "<ws>"], []],
   "<sp1>": [[" "],["\n"],["\t"],["\r"]],
   "<symbol>": [[",", "<members>"]],
   "<symbol-1>": [[",", "<elements>"]],
   "<symbol-2>": [[], ["<symbol>", "<symbol-2>"]],
   "<symbol-1-1>": [[], ["<symbol-1>", "<symbol-1-1>"]],
   "<character-1>": [[], ["<character>", "<character-1>"]],
   "<digit-1>": [["<digit>"], ["<digit>", "<digit-1>"]]
   }

   
   

   Проблема с РБНФ заключается в том, что это грамматика второго типа или бесконтекстная грамматика, из-за чего технически определять ей XML или HTML нельзя. И парсить их RegEx, кстати, тоже. Пространство генерируемых ею тест-кейсов заведомо меньше пространства, определяемого данными форматами, что ограничивает сложные граничные случаи, которые могут быть сгенерированы РБНФ. Например, в этой модели мы не можем задать правило «если в тест-кейсе четное число букв a, то последней должна быть обязательно b», не скатившись в перебор всех возможных вариантов.

   
   

3. Использование Protocol Buffers. Это удобный способ определить структуру файла или протокола: вы описываете их при помощи Protocol Buffers и пишете свой преобразователь из protobuf в бинарные данные.

   
   

   Существует специальная библиотека libprotobuf-mutator, которая позволяет использовать заготовленные мутаторы на внутренние типы и в целом сама мутирует protobuf-представление тест-кейса. С ее помощью можно с минимальным вложением сил получить достаточно умный мутатор (а если он и тупит, то документация подскажет, как легко добавить логику).

   
   

   Пример части определения для фаззинга парсера DNS-сообщений:

   
   

   syntax = "proto2";
   package dnsmessage;
   message Message{
   required Header header = 1;
   repeated Question question = 2;
   repeated ResourceRecord answer = 3;
   repeated ResourceRecord authority = 4;
   repeated ResourceRecord additional = 5;
   message Header{
       required int32 id = 1;
       required bool qr = 2;
       required Opcode opcode = 3;
       required bool aa = 4;
       required bool tc = 5;
       required bool rd = 6;
       required bool ra = 7;
       required bool ad = 8;
       required bool cd = 9;
       required RCode rcode = 10;
       required int32 qdcount = 11;
       required int32 ancount = 12;
       required int32 nscount = 13;
       required int32 arcount = 14;
   }
   ...
   }

   
   

Оракулы багов

Вот сравнительная таблица стандартных оракулов багов, которые есть в компиляторе Clang (его используют фаззеры под C/C++):

Чтобы было понятно, как оракулы работают, приведу пример с ASAN — он мне кажется наиболее полезным для обнаружения эксплуатабельных багов.

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

#include <stdio.h>

int main(){
    int size, pick;
    unsigned char* array;
    printf("Pick malloc size: ");
    scanf("%d",&size);
    array=calloc(size,1);
    printf("Read from element: ");
    scanf("%d",&pick);
    printf("Result: %x\n",array[pick]);
    free(array);
    return 0;
}

Если скомпилировать программу с ASAN, он покажет чтение элемента за границей:

Основные семейства Greybox-фаззеров для C/C++

Мне кажется, что стоит упомянуть три семейства (хотя вы можете со мной не согласиться). Вот они:

• AFL;
• LibFuzzer;
• Honggfuzz.

AFL — это фаззер, который дал толчок в массовому использованию Greybox-фазз-тестирования, когда Michal Zalewski (lcamtuf) выпустил его в 2013 году. Базовая идея фаззера была такой: собираем покрытие ветвей при каждом исполнении, цель — максимизировать покрытие.

Сейчас «ванильный» AFL уже не используется, но от него отпочковалось много проектов, например WinAFL и TinyAFL, которые позволяю проводить фаззинг приложений на Windows при помощи бинарной инструментации. Самый популярный и быстроразвивающийся проект я уже называл выше: это AFLPlusPlus (AFL++). Он вбирает в себя новые техники и постоянно расширяет возможности исследователей.

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

LibFuzzer распространяется вместе с Clang. Он эволюционирует не так быстро, как AFL++, но там тоже есть встроенные приятные фичи (например, алгоритм entropic, который выбирает наиболее эффективные тест-кейсы из корпуса).

Этот фаззер рассчитан только на использование в persistent mode. Однако на случай, если приложение отжирает слишком много памяти, у него есть и fork mode: он форкает процесс для небольшого числа итераций в persistent mode, после чего прибивает его.

Использовать libFuzzer очень легко.

Honggfuzz отличается методами сбора покрытия: фаззер позволяет использовать Intel Branch Trace Store или Intel Processor Trace. Также в нем есть есть стандартная возможность инструментировать приложение во время компиляции и поддержка фаззинга скомпилированных приложений при помощи qemu mode (хотя это есть и у AFL++).

Легко ли его использовать, сказать не могу: я обходился AFL++ и libFuzzer. Так как собственного опыта работы с honggfuzz у меня нет, дальше в статье я его не касаюсь.

А вот libFuzzer и AFL++ давайте рассмотрим подробнее.

LibFuzzer на практике

Давайте попробуем написать простой обвяз (harness) для фаззинга с libFuzzer.

Установите себе Clang, если он еще не поставлен (инструкция). Скопируйте следующий код в basic_example.c:

#include <stddef.h>
#include <stdint.h>

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    if (size > 0 && data[0] == 'H')
        if (size > 1 && data[1] == 'I')
            if (size > 3 && data[2] == '!')
            __builtin_trap();
    return 0;
}

В качестве входа, в который будут подаваться тест-кейсы, в libFuzzer используется следующая функция:

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)

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

В libFuzzer еще определена такая стандартная функция:

int LLVMFuzzerInitialize(int *argc, char ***argv)

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

Скомпилируем наш обвяз:

clang -fsanitize=fuzzer basic_example.c -o basic_example

Если бы мы хотели добавить ASAN и UBSAN, то нужно было бы компилировать так:

clang -fsanitize=fuzzer,address,undefined basic_example.c -o basic_example

Clang сам добавит все необходимое для persistent mode.

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

Фаззер тут же находит тест-кейс (его можно заметить на видео в конце снизу — «H!HH»), который вызывает прерывание. Тест-кейс сохранен под именем crash-<хеш от содержимого>. Его можно снова передать в исследуемое приложение, чтобы посмотреть стек вызовов:

А теперь AFL++

Если исходники уже подготовлены к использованию с libFuzzer, то переделать их под работу с AFL++ в persistent mode тривиально. Достаточно скачать afl_driver.cpp, который распространяется в составе LLVM, и скомпилировать под AFL++.

1. Качаем, собираем и устанавливаем AFL++.

   
   

2. Компилируем basic_example.c, afl_driver.cpp и линкуем:

   
   

   afl-clang-fast -c basic_example.c
   afl-clang-fast++ -c afl_driver.cpp
   afl-clang-fast++ basic_example.o afl_driver.o -o basic_afl_example

   
   

3. Создаем директории, кладем какой-нибудь файл в input и запускаем:

   
   

   mkdir input output; echo "" > input/0;
   afl-fuzz -i input -o output -- ./afl_basic_example

   
   
4. 
   

   Как видно, AFL++ тоже находит прерывание, но в базовой конфигурации делает это медленнее libFuzzer.

   
   

Крутизна AFL и мутации

Я упоминал, что именно AFL привел к взрыву исследований и разработки в области фаззинга. Но почему именно AFL?

Это был первый фаззер, который сочетал одновременно несколько особенностей:

1. Его было просто использовать. В случаях с вводом по stdin достаточно было заменить компиляторы GCC/Clang на afl-gcc или afl-clang. (Это не значит, что GCC надо заменять на afl-gcc, а Clang на afl-clang. Если хотите этим заняться, посмотрите документацию AFL++ и выберите компилятор, который встроит самую быструю инструментацию, доступную вам.)
2. Он использовал покрытие ветвей, которое оказалось эффективнее для фаззинга, чем покрытие блоков.
3. Он составлял расписание тест-кейсов (schedule) так, чтобы медленные тест-кейсы не отъедали слишком много времени. Расписание фаззера — это алгоритм решения, какие тест-кейсы из корпуса фаззер выбирает на каждом этапе и сколько времени он выделяет на тестирование их мутированных версий. AFL строит очередь из всех тест-кейсов в корпусе, причем при постановке в очередь приоритет отдает новым тест-кейсам. Также AFL настраивает количество запусков PUT с мутированными тест-кейсами, увеличивая или уменьшая его в зависимости от времени выполнения базового тест-кейса, который мутирует в данный момент. Иначе при обнаружении особенно медленного экземпляра ему бы выделялось больше всего времени.
4. Он содержал механизмы мутаций и извлечения информации из тест-кейсов, предоставленных в начальном корпусе, которые Michal Zalewski проверил на эффективность опытным путем.

О последней особенности — механизмах мутации — надо рассказать подробнее.

Мутации — это еще одна составляющая фаззинга, наравне с покрытием, механизмом исполнения PUT, моделью тест-кейсов и оракулами. Есть две основные фазы мутаций:

1. Детерминистическая.
2. Хаос (Havoc).

В конфигурации по умолчанию AFL начинает с детерминистической фазы. Для каждого тест-кейса в стартовом корпусе AFL последовательно применяет следующие мутации (после каждой мутации проверяет PUT с данным тест-кейсом):

1. Флип одного бита в тест-кейсе (0x00 → 0x80).
2. Флип последовательной пары битов (0x00 → 0xC0).
3. Флип последовательной четверки битов (0x00 → 0xF0).
4. Инвертирование байта (0x00 → 0xFF).
5. Инвертирование двух последовательных байтов (0x0000 → 0xFFFF).
6. Инвертирование четырёх последовательных байтов (0x00000000 → 0xFFFFFFFF).
7. Добавление и вычитание из байтов, вордов и двордов малых значений (и в little-endian, и в big-endian).
8. Замена байтов, вордов, двордов на особые значения (1, −1, 0, 127 и пр.).

Такие мутации с высокой вероятности изменят работу PUT, если там производится обработка бинарных данных.

При этом AFL анализирует поведение программы при осуществлении отдельных битфлипов. Например, AFL видит, что работа PUT при флипе 0-го бита меняется, с 0–31 она изменена, а когда флип производится на 32 бите, все возвращается к прежней работе. В этом случае AFL понимает, что, скорее всего, в этих четырех байтах находится MAGIC или другая константа, запоминает ее и добавляет в словарь, который потом использует на хаотической фазе. Это делает его крайне эффективным: если собран большой корпус файлов, которые должна обрабатывать PUT, то AFL с большой вероятностью сможет создать интересную комбинацию из частей известных тест-кейсов.

Когда AFL заканчивает детерминистическую фазу (или сразу, если пользователь ее пропускает), то переходит в хаотическую фазу. В этой фазе есть две стратегии:

• просто хаос;
• хаос со сплайсингом.

Первая стратегия — просто хаос — одновременно использует несколько мутаций на одном тест-кейсе (не обязательно все сразу):

1. Одиночные битфлипы.
2. Подстановка особых значений.
3. Добавление и вычитание малых значений.
4. Замена отдельных байтов случайными значениями.
5. Удаление блоков байтов.
6. Замена и вставка блоков байтов.
7. Замена блока блоком из одинаковых байтов.

Вторая стратегия — хаос со сплайсингом — делает так:

1. Берет пару тест-кейсов, которые отличаются как минимум в двух местах.
2. Разрывает каждый из них.
3. Склеивает разные части.
4. Применяет первую стратегию к результату.

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

Еще не конец

Фух, долгое и мучительное введение в то, как работает фаззер, закончилось.

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