Немного про современные технологии greybox фаззинга02.08.2021 13:32

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

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

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

Чтобы справиться с этой проблемой, придумали фаззеры — инструменты тестирования, которые сами пытаются найти баги в программе. В этой статье я рассмотрю, какие они вообще бывают (для 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 
#include 
#include 
#include 
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:

   {
   "": [[""]],
   "": [[""]],
   "": [["", "", ""]],
   "": [["