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

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

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

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

Максимизировать фаззинг: Link Time Optimization

Чтобы понять это улучшение, надо знать, как фаззер AFL считает покрытие ветвей. Принцип достаточно прост:

AFL создает большой массив AFL_MAP в памяти тестируемой программы (PUT — Program Under Test). Обычно он занимает 64 КБ или больше.
Каждому базовому блоку в программе присваивается уникальный идентификатор (BB_ID).
При прохождении базового блока его идентификатор сохраняется в переменную (PREVBB_ID).
При прохождении следующего блока высчитывается BRANCH_ID и инкрементируется счетчик в AFL_MAP:
```
BRANCH_ID = BB_ID ^ (PREVBB_ID >> 1);
AFL_MAP[BRANCH_ID] += 1;
```

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

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

Но действительно крутое изменение, внесенное в AFL++, называется Link Time Optimization или просто LTO.

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

Преимущества механизма LTO:

никаких коллизий идентификаторов ветвей (массив AFL_MAP выделяется под все BRANCH_ID);
скорость выполнения увеличивается до 20%;
можно автоматически составлять словарь (AutoDict).

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

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

Не застревать на бесполезных тест-кейсах: AFLFast

Знаете, что делает обычный AFL, когда встречает такой код?

int main(){
    unsigned char buffer[0x100]={0};
    read(STDIN_FILENO, buffer, 0x100);
    if (buffer[0]=='b')                 // ~ 6*256 + 6*256 + 6*256 + 6* 256
        if (buffer[1]=='a')             // ~ 6*256 + 6*256 + 6*256
            if (buffer[2]=='d')         // ~ 6*256 + 6*256  
                if (buffer[3]=='!')     // ~ 6*256      
                    if (buffer[4]=='!') 
                        if (buffer[5]=='!') 
                            abort();
    return 0;
}

При помощи фаззинга находит тест-кейс с первой буквой b и добавляет его в начало очереди.
С высокой вероятностью не находит ba сразу после перехода к b и после окончания кванта времени возвращается к оригинальному тест-кейсу.
Снова фаззит b. Допустим, теперь находит ba. Добавляет в начало очереди.
Не находит bad. Теперь снова фаззит оригинальный тест-кейс, потом b и только потом ba.
Ну вы поняли.

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

Marcel Böhme придумал решение этой проблемы, которое он назвал AFLFast. Он предложил рассматривать программу как цепь Маркова. Есть определенные вероятности перехода между соседними состояниями, а остальные вероятности — это уже композиция:

AFL использует понятие seed energy (энергия тест-кейса). Когда идет выбор тест-кейса для мутаций из очереди, seed energy определяет, сколько раз AFL будет его использовать. И в обычном AFL формула очень простая:

$p(i)=\alpha(i)$

где $\alpha(i)$ — константа, обратно пропорциональная времени выполнения PUT на этом тест-кейсе. Это сделано для защиты от пожирания энергии медленными тест-кейсами.

В AFLFast же используется следующая функция:

$p(i)=min((\frac{\alpha(i)}{\beta}\cdot\frac{2^{s(i)}}{f(i)}),M)$

$\alpha(i)$ та же;
$\beta$ — просто константа для настройки;
$inline$ — количество раз, которое этот тест-кейс уже был выбран;
$inline$ — сколько раз вообще за время фаззинга зарегистрировано покрытие, соответствующее этому тест-кейсу;
$inline$ — среднее количество выполнений на тест-кейс.

В чем смысл:

$inline$ уменьшает количество энергии для тест-кейсов, к которым постоянно будут возвращаться остальные (например, когда в начале файла есть MAGIC, и он постоянно перетирается во время мутаций).
$2^{s(i)}$ позволяет экспоненциально увеличивать энергию для новых тест-кейсов, таким образом приоритизируя фаззинг на их основе.
Минимизация по $inline$ не дает тест-кейсам уходить в отрыв. Как только они достигают среднего объема попыток по всему корпусу, они ограничиваются.

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

Мутировать тест-кейсы эффективно: MOpt

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

Вот таблица, которая на примере парсинга бинарных данных и парсинга текста (в данном случае — HTML) показывает, может ли быть полезной в одиночку та или иная мутация:

Мутатор	Бинарный парсер	Парсер HTML
Битфлиппинг	+	-
Байтфлиппинг	+	-
Сложение/вычитание значений	+	-
Замена байтов, вордов, двордов особыми значениями	+	-
Замена отдельных байтов случайными значениями	+	-/+
Удаление блоков байтов	+	+
Замена блоков байтов	+	+
Сплайсинг	+	+
Вставка из словаря	±	++

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

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

Из диаграмм видно, что влияние мутаторов не одинаково и их распределение меняется в зависимости от тестируемой программы.

Это изображение я взял из доклада «MOPT: Optimized Mutation Scheduling for Fuzzers», авторы которого как раз и придумали механизм, решающий проблему неэффективных мутаций. Как видно из названия доклада, механизм называется MOpt (Optimized Mutation Scheduling, оптимизированное расписание мутаций).

MOpt основан на измененном эвристическом алгоритме Particle Swarm Optimization (PSO, оптимизация роя частиц). Цель PSO — нахождение глобальных максимумов или минимумов. Наглядно это показано на иллюстрации алгоритма, содранной с «Википедии»:

Допустим, есть некоторая функция от нескольких координат $inline$ . Инициализация алгоритма PSO:

Создается много точек, равномерно расположенных на области определения функции.
Для каждой точки случайно генерируются параметры $r_0, r_1 \in (0,1)$ .
Каждой точке присваивается скорость, в соответствии с которой она должна двигаться.

Итерация алгоритма:

Каждая точка проверяет значение функции, соответствующее ее позиции.
Если значение функции выше (ниже) всех ранее пройденных позиций этой точки, то позиция запоминается как локальная лучшая $L_{best}$ .
Если значение функции выше (ниже) всех пройденных позиций всех точек, то позиция запоминается как глобальная лучшая $G_{best}$ .
Скорость каждой точки меняется:

$\vec{v}_{new}=\omega*\vec{v}_{old}+ \phi_g*r_0*\vec{d}_g+\phi_l*r_1*\vec{d}_l$

где $\vec{d}_g, \vec{d}_l$ — векторы с началом в текущей позиции точки и концом в лучшей глобальной и локальной позициях соответственно, а $\omega, \phi_g, \phi_l$ — константы, которые нужно выбрать разработчику.
Позиция точки обновляется в соответствии с ее скоростью.

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

В алгоритме MOpt понятие роя изменено. Каждый рой содержит по одной частице на каждый используемый оператор, но одновременно используется несколько роев. Каждая частица путешествует по пространству с одной координатой $x \in [x_{min},x_{max}]$ , где $0<x_{min}<x_{max}\le 1$ . Координата описывает вероятность выбора данного оператора при фаззинге. Перед использованием все значения внутри одного роя нормализуются.

$L_{best}$ каждой частицы определяется по ее локальной эффективности, которая высчитывается как количество интересных тест-кейсов, сгенерированных с участием этого оператора, поделенное на количество вызовов этого оператора за определенный период. Значение $inline$ с наибольшей локальной эффективностью и запоминается в качестве $L_{best}$ .

$G_{best}$ вычисляется отлично от алгоритма PSO. Вместо использования одного из $L_{best}$ MOpt высчитывает глобальную эффективность каждого оператора: количество интересных тест-кейсов, полученных с его использованием, поделенное на общее количество вызова оператора. Далее MOpt высчитывает распределение эффективностей всех операторов и для каждого оператора принимает $G_{best}$ как пропорцию глобальной эффективности одного оператора ко всему распределению (нормализует).

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

Механизм MOpt в действии можно описать так:

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

Вот иллюстрация различных роев из того же самого доклада.

Так MOpt решает проблему повышения эффективности мутаций.

Посмотрим на MOpt в деле. Возьмем программу, где новые ветви зависят от количества токенов bug во вводе. Если попытаться профаззить этот код с использованием MOpt (и еще LTO — он нужен, чтобы добавить bug в автоматически сгенерированный словарь), то мы увидим, что после нахождения первой новой ветви фаззер почти моментально найдет и abort.

int main(){
    unsigned char buffer[0x100]={0};
    read(STDIN_FILENO, buffer, 0x100);
    int count = 0;
    for (int i=0; i<6; i++){
        if (memcmp("bug",buffer+i*6,3)==0)
            count=count+1;
    }
    if (count>2)
        printf("Almost there\n");
    if (count>4)
        abort();
}

Покрыть максимум ветвей: LAF-Intel / Redqueen / Autodict / Value Profile

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

Давайте посмотрим, какие основные проблемы могут помешать фаззеру. (Один такой случай я описал в предыдущей статье, когда говорил об ограничениях Greybox-фаззеров в сравнении с символическим исполнением. Но подобные кейсы мы учитывать не будем.)

Пример проблемного кода:

/*  magic  number  example  */
if(u64(input)==u64("MAGICHDR"))
    bug (1);
/*  nested  checksum  example  */
if(u64(input)==sum(input+8, len -8))
    if(u64(input +8)==sum(input+16, len -16))
        if(input [16]== ’R’ &&  input [17]== ’Q’)
            bug (2);

Здесь есть две серьезные проблемы для фаззинга:

Наличие тяжелых условий с малой вероятностью их выполнения (например, сравнение с 8-байтовым MAGIC).
Наличие проверочных сумм (особенно вложенных).

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

В нашем случае размер сравнения составляет 8 байтов. Это значит, вероятность его прохождения при подаче случайных данных — ~ $\frac{1}{2^{64}}$ . Рассчитывать на выполнение такого условия случайно можно только в случае, если вы готовы фаззить годами на кластере машин. Учитывая, что при строковых сравнениях длина может быть и больше, уверенно заключаем: нужно более надежное и эффективное решение проблемы, чем LTO.

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

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

Вот какие решения этих двух проблем существуют:

Сидеть читать код, выдирать токены, добавлять в словарь для фаззинга, плакать.
Использовать решатели.
LAF-Intel (технология AFL++, решает только первую проблему).
Redqueen (технология AFL++).
Autodict (технология libFuzzer и afl-clang-lto, справляется только с первой проблемой).
Value Profile, оно же профилирование значений (технология libFuzzer, снимает только первую проблему).

Дальше в статье мы сначала рассмотрим механизмы, задействованные в AFL++, а потом — в libFuzzer.

LAF-Intel

LAF-Intel просто раскладывает код сравнения больших значений с константами на побайтовые сравнения.

Было:

if (input == 0xabad1dea) {
  /* terribly buggy code */
} else {
  /* secure code */
}

Стало:

if (input >> 24 == 0xab){
  if ((input & 0xff0000) >> 16 == 0xad) {
    if ((input & 0xff00) >> 8 == 0x1d) {
      if ((input & 0xff) == 0xea) {
        /* terrible code */
        goto end;
      }
    }
  }
}
/* good code */

Аналогично раскладывается сравнение строк. Было:

if (!strcmp(directive, "crash")) {
  bug();
}

Стало:

if(directive[0] == 'c') {
  if(directive[1] == 'r') {
    if(directive[2] == 'a') {
      if(directive[3] == 's') {
        if(directive[4] == 'h') {
          if(directive[5] == 0) {
            bug();
}

Switch преобразуется таким образом, чтобы обеспечить минимальное количество сравнений. Изначальный вид:

switch(x) {
  case 0x11ff:
    /* handle case 0x11ff */
    break;
  case 0x22ff:
    /* handle case 0x22ff */
    break;
  default:
    /* handle default */
}

После преобразования:

if(x >> 24 == 0) {
  if((x & 0xff0000) >> 16 == 0x00) {
    if((x & 0xff) == 0xff) {
      if((x & 0xff00) >> 8 == 0x11) {
        /* handle case 0x11ff */
        goto after_switch;
      } else if((x & 0xff00) >> 8 == 0x22) {
        /* handle case 0x22ff */
        goto after_switch;
      } else {
        goto default_case;
      }
    }
    goto default_case;
  }
  goto default_case;
}

Иными словами, LAF-Intel преобразует покрытие данных в покрытие ветвей.

Преобразование затрагивает все сравнения и вызовы специальных функций (memcmp, strcmp и др.). При этом потери в производительности минимальны, так что способ оказался весьма эффективным.

Чтобы использовать LAF-Intel при помощи AFL++, надо перед компиляцией экспортировать переменную среды:

export AFL_LLVM_LAF_ALL=1

Redqueen

Redqueen — это волшебная техника, основанная на «угадывании», которая даже может проходить проверочные суммы. Она использует механизм input-to-state correspondence (соответствие ввода состоянию), который пытается найти соответствие между вводом и аргументами сравнений: CMP, memcmp и др.

Redqueen работает следующим образом:

Заполняет ввод или его части псевдослучайными значениями.
Собирает аргументы инструкций и функций сравнения.
Ищет значения аргументов в исходном вводе. Этот шаг выполняется с учетом ряда преобразований:
- Plain (прямое без модифицирования).
- Zero/SignExtend (числовые расширения).
- Reverse (little-endian big-endian).
- C-String (берет всё до NULL-байта).
- Memory(n) (представление как аргумент memcmp, берет ограниченное количество байтов).
- ASCII (представление целого числа в ASCII).
Если совпадение найдено, то создает несколько вариантов значения аргумента:
- Равное тому, с которым сравнивается.
- Меньше.
- Больше.
Использует обратное преобразование на каждом из полученных вариантов и подставляет в соответствующее место в вводе. Если срабатывание не было случайным, то теперь должна быть пройдена новая ветвь.

Пример для наглядности:

Название	Значение
Исходный код	u64(input) == u64(“MAGICHDR”)
Тест-кейс	TestSeedInput
Сравнение, как его видит Redqueen	deeStesT == RDHCIGAM (0x6465655374736554 == 0x524448434947414d)
Вариации (меньше, равно, больше)	RDHCIGAL RDHCIGAM RDHCIGAN
Сгенерированные мутации	TestSeedInput -> LAGICHDRInput TestSeedInput -> MAGICHDRInput TestSeedInput -> NAGICHDRInput

Проблему с MAGIC мы таким образом явно решили.

А что насчет проблемы с проверочными суммами? Даже если использовать дорогую инструментацию, которая будет работать по принципу Redqueen, выдирая значение и подставляя в нужное место в input, все равно вызывать PUT на каждую мутацию придется два раза:

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

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

Redqueen использует другой механизм:

Детектирует сравнение с проверочной суммой.
Временно накладывает патч, убирающий проверку.
Если обнаруживает интересный тест-кейс, снимает патч.
Подставляет проверочную сумму для интересного тест-кейса.

Детектирование происходит по следующему принципу:

Один аргумент сравнения удовлетворяет условию input-to-state correspondence.
Второй постоянно меняется при фаззинге.

В итоге техника Redqueen:

Может справиться с 90% проблем, связанных со сравнениями.
Сама патчит проверочные суммы и потом решает их.
Довольно медленная: во-первых, потому что при первых исполнениях нового тест-кейса использует тяжелую инструментацию; во-вторых, потому что использует много анализа.
Отлично подходит для текстовых форматов, потому что минимально изменяет исходные данные перед сравнением.

Включить Redqueen в AFL++ (там она называется CMPLOG) можно, выставив соответствующую переменную среды перед компиляцией:

export AFL_LLVM_CMPLOG=1

Autodict

Про AFL++ закончили — теперь посмотрим, какие технологии для решения тех же проблем есть в libFuzzer.

Самая простая — это Autodict. Как и LTO, она собирает токены, с которыми производится сравнение, и генерирует из них словарь для фаззинга.

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

А вот работа Autodict на практике. В этом коде на определенных позициях должно три раза встретиться слово bug, чтобы функция вернула 1:

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    int k=0;
    for (size_t i=0; (i+3)<Size; i=i+3){
        if (!memcmp("bug",Data+i,3)) k=k+1;
    }
    if (k==3) return 1 // same as abort;
    return 0;  
}

Autodict позволяет libFuzzer моментально найти такую строку:

В логе фаззинга можно увидеть, как libFuzzer находит ветви, подставляя bug:

enter image description here

Value Profile

Это альтернативный LAF-Intel метод для прохода сложных сравнений, который встроен в libFuzzer. Только вместо разбиения сравнений на меньшие и легкопроходимые здесь используется покрытие данных.

Как работает Value Profile:

В PUT на каждое сравнение добавляется специализированная инструментация.
При проходе сравнения libFuzzer производит XOR аргументов.
Высчитывает количество выставленных битов в результате.
Если такое количество битов на данном сравнении еще не встречалось, сгенерированный тест-кейс добавляется в корпус.

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

Минусом метода является дикое раздутие корпуса. Но в целом он неплох.

Например, есть такая PUT:

int LLVMFuzzerTestOneInput(const char* Data, size_t Size){
    unsigned int x;
    if (Size<4) return 0;
    x=*(unsigned int*)Data;
    x=((x^0x11111111)>>5) | ((x^0x33333333)<<27);
    if (x==0xdeadbeef) return 1;
    return 0;
}

С выключенным Value Profile нам придется долго ждать, пройдет ли это сравнение libFuzzer. Включаем Value Profile — проходит моментально:

По умолчанию этот метод в libFuzzer выключен.

Итог

Фаззеры очень круто изменились за последние несколько лет и превратились в мощный инструмент для исследования безопасности программ.

Я не рассказал про все улучшения и механики — их слишком много. Чейнджлог AFL++ активно обновляется, а вся сфера фаззеров динамично развивается. Из интересного можно еще посмотреть entropic в libFuzzer, поддержку qemu, механизмы минимизации корпуса и многое другое. Если хотите почитать исследования, то большинство из них собрано здесь: Recent Papers Related To Fuzzing.

Удачи в тестировании и поиске уязвимостей!

Greybox-фаззинг: level up. Как улучшали фаззеры