fuzzilli – это фаззер для javascript-движков от команды googleprojectzero. Его отличительная черта – это FuzzIL, промежуточный язык, который можно мутировать и затем транслировать в js. Этот язык обеспечивает мутированному js семантическую валидность: даже после нескольких раундов изменений в коде остается логика, с которой движок будет работать.


Движки, которые можно фаззить



В этом списке V8, Spidermonkey, XS и duktape уже поддерживают работу с fuzzilli. А остальные движки можно пропатчить и начать фаззинг, патчи включены в состав инструмента.


С помощью fuzzilli уже найдено много интересных багов типа OOB. Разберемся, как он устроен.


Содержание


1. FuzzIL
2. Реализация
3. Мутаторы
3.1. Input mutator
3.2. Operation Mutator
3.3. Combine Mutator
3.4. Splice Mutator
4. Инструментация
5. Исполнение скрипта
6. CVE-2019-8518
7. Вывод


FuzzIL


FuzzIL – это промежуточное представление js, и самое интересное в нем – это мутаторы для FuzzIL. Как они генерируют валидный js-код?


Мутировать js-код можно на следующих уровнях:


  • текст скрипта (изменение случайных байт)
  • синтаксическое дерево AST (вырезать/вставлять случайное поддерево)

Первый способ не сильно отличается:


$ ./js_shell < /dev/urandom

Движок просто отбросит все предлагаемые варианты.


Способ с деревьями лучше: мутатор производит синтаксически правильный js-код. Например, вот такой:


    if(y > 0){
        ...
        /* type confusion */
        ...
    }

    let y = 0;

Но, несмотря на это, в логике ошибка все-таки есть: переменная y здесь используется до своего объявления. Это вызовет исключение, а возможный баг type confusion останется неотловленным.


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


Пример программы на FuzzIL:


1  v0 <− LoadInt ’ 0’
2  v1 <− LoadInt ’10’
3  v2 <− LoadInt ’ 1’
4  v3 <− Phi v0
5  BeginFor v0, ’<’, v1, ’+’, v2 −> v4
6  v6 <− BinaryOperation v3, ’+’, v4
7  Copy v3, v6
8  EndFor
9  v7 <− LoadString ’Result :’
10 v8 <− BinaryOperation v7, ’+’, v3
11 v9 <− LoadGlobal ’console’
12 v10 <− CallMethod v9, ’log’, [v8]

У FuzzIL нет синтаксиса, но представлять программу как-то надо, поэтому этот пример написан на некотором псевдокоде.


Транслятор у FuzzIL есть, и этот же пример на js будет выглядеть так:


1  const v0 =  0;
2  const v1 = 10;
3  const v2 =  1;
4  let v3 = v0;
5  for (let v4 = v0; v4 < v1; v4 = v4 + v2) {
6    const v6 = v3 + v4;
7    v3 = v6;
8  }
9  const v7 = ”Result: ”;
10 const v8 = v7 + v3;
11 const v9 = console;
12 const v10 = v9.log(v8);

Или:


1 let v3 = 0;
2 for (let v4 = 0; v4 < 10; v4++) {
3 v3 = v3 + v4;
4 }
5 console.log(”Result: ” + v3);

fuzzilli умеет транслировать и так и так.


Чтобы описать мутаторы, нужно немного поговорить о реализации FuzzIL.


Реализация


fuzzilli и FuzzIL написаны на языке Swift.


Проиллюстрировать классы, которые реализуют программу на FuzzIL, поможет диаграмма:



Типом данных, отвечающим за итоговый js -скрипт, является class Program.


Программа – это набор операций вместе с их входными и выходными переменными.


Например, операция LoadInteger:


class LoadInteger: Operation {
    let value: Int64

    init(value: Int64) {
        self.value = value
        super.init(numInputs: 0, numOutputs: 1, attributes: [.isPure, .isMutable])
    }
}
/*
v0 <− LoadInt ’ 0’
*/

LoadProperty:


class LoadProperty: Operation {
    let propertyName: String

    init(propertyName: String) {
        self.propertyName = propertyName
        super.init(numInputs: 1, numOutputs: 1, attributes: [.isMutable])
    }
}

/*
v1 <- LoadProperty v0, '__proto__'
*/

Посмотреть все операции можно в Operations.swift


За создание программы отвечают ProgramBuilder и CodeGenerators. Каждый генератор производит свой специфический фрагмент FuzzIL кода. Например, IntegerGenerator создает инструкцию LoadInteger со случайным параметром, а IfElseGenerator – условный блок:


CodeGenerator("IntegerGenerator") { b in
        b.loadInt(b.genInt())
}

/*...*/

CodeGenerator("IfElseGenerator", input: .boolean) { b, cond in
    b.buildIfElse(cond, ifBody: {
        b.generateRecursive()
    }, elseBody: {
        b.generateRecursive()
    })
}

Таких генераторов десятки. Некоторые из них вызывают другие генераторы, как IfElseGenerator, чтобы код внутри блока получился интереснее.


Когда новая программа создана, она подвергается анализу через:


  • VariableAnalyzer
  • ScopeAnalyzer
  • ContextAnalyzer
  • DeadCodeAnalyzer

Проверяются переменные, их типы и области видимости. Учитывается, что переменные внутри конструкций for, while не должны быть видны снаружи. А переменные, определенные снаружи, должны быть видны внутри, если используются:


let v2 = 10;
for(let v4 = v2; v4 < 100; v4++){...}

Проверяются блоки: если есть операция BeginWhileLoop, то должен быть и EndWhileLoop. И наоборот: если есть конец блока EndWhileLoop, то должно быть и начало BeginWhileLoop.


Типы: Unknown, Integer, Float, String, Boolean, Object, Function. Проверка типов не допустит, например, такой код:


let v0 = 1;
v0.slice(1); // Exception: TypeError: v0.slice is not a function

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


После всех проверок код транслируется в текст. За трансляцию отвечает class JavaScriptLifter. В этот класс заложены правила того, как представлять инструкции в текстовом виде.


switch instr.op {
    case let op as LoadInteger:
        /*...*/
    case let op as LoadBigInt:
        /*...*/
    case let op as LoadProperty:
        /*...*/
    case let op as BeginForLoop:
        /*...*/
    /*...*/
}

Мутаторы


  • input mutator
  • operation mutator
  • combine mutator
  • splice mutator

Input mutator


Мутирует входные аргументы-переменные.


1 // Before Mutation
2 . . .
3 v16 <− CallFunction v1, v6, v9, v3
4
5 // After Mutation
6 . . .
7 v16 <− CallFunction v1, v12, v9, v3

Учитывается область видимости; переменная v12 из того же скоупа, что и все остальные.
Если невозможно найти замену, то кандидат вернется на свое место.


Operation Mutator


Мутирует параметр операций, если он у них есть.


У объектов операций помимо входных и выходных переменных есть еще и параметры. Например, у LoadInteger это value, у LoadPropertypropertyName, а у CallMethodmethodName.


Combine Mutator


1 // Program 1
2 v0 <− LoadString ’bar’
3 v1 <− CreateObject ’foo’, v0
4
5 // Program 2
6 v0 <− LoadInt ’ 1337 ’
7 v1 <− LoadGlobal ’console’
8 v2 <− CallMethod v1, ’log’, [v0]
9
10 // Combined program
11 v0 <− LoadInt ’ 1337 ’
12 v1 <− LoadString ’bar’
13 v2 <− CreateObject ’foo’, v1
14 v3 <− LoadGlobal ’console ’
15 v4 <− CallMethod v3, ’log’, [v0]

Splice Mutator


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


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

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


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


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


В каждом базовом блоке размещается вызов sanitizer_cov_trace_pc_guard:


struct shmem_data {
    uint32_t num_edges;
    unsigned char edges[];
};

struct shmem_data* __shmem;

/*...*/

extern "C" void __sanitizer_cov_trace_pc_guard(uint32_t *guard) {

    uint32_t index = *guard;

    if (!index) return;

    __shmem->edges[index / 8] |= 1 << (index % 8);
    *guard = 0;
}

Здесь guard – указатель на индекс блока, __shmem->edges – массив, с которым работают, как с битмапом.


Как уже упоминалось, часть движков поддерживает инструментацию fuzzilli. Чтобы инструментировать, например, v8, нужно указывать флаг v8_fuzzilli=true в процессе сборки v8. К счастью, сборка всех движков автоматизирована и помнить о флагах не нужно – в составе есть скрипты для этого. А если инструментация не поддерживается, то там же есть и патчи.


Исполнение скрипта


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


  • форк-сервер, как в AFL: размещается в процессе таргета, получает очередную порцию мусора от мастера и делает форк, в котором идет обработка. В этом случае переиспользуется все, что до форк-сервера.


  • REPRL(read-eval-print-reset-loop), как в libfuzzer: в бесконечном цикле исследуемый код ждет и получает данные, обрабатывает, потом сбрасывает состояние на начальное, и по-новой. Здесь переиспользуется все, что до цикла.



Преимущество форк-сервера в том, что его можно разместить где угодно (пример из AFL). REPRL-цикл постоянно на одном месте: (пример V8).


Но производительность вроде бы за REPRL.


Авторы fuzzilli провели измерения для движка JavaScriptCore и оказалось, что REPRL опережает форк-сервер на 6 мс за одну итерацию. Тестом был скрипт, который просто ждет 1 секунду: результат REPRL – 1,001 c, а форк-сервер – 1,007 c. Тест кажется простым, но тем не менее был выбран REPRL.


Как и инструментация, реализация REPRL включена в состав конкретного движка, если он поддерживает работу с fuzzilli.


CVE-2019-8518


Это OOB-баг, найденный в JavaScriptCore/webkit:


const v3 = [1337,1337,1337,1337];
const v6 = [1337,1337];

function v7(v8) {
    for (let v9 in v8) {
        v8.a = 42;
        const v10 = v8[-698666199];
    }
}

while (true) {
    const v14 = v7(v6);
    const v15 = v7(1337);
}

IR-представление функции v7 будет выглядеть примерно так (взято из отчета):


// Loop header
len = LoadArrayLength v8
// Do other loop header stuff

// Loop body
CheckStructure v8, expected_structure_id
StoreProperty v8, 'a', 42
CheckBounds -698666199, len             // Bails out if index is OOB (always in this case...)
GetByVal v8, -698666199                 // Loads the element from the backing storage without performing additional checks

// Jump back to beginning of loop

А вот как JIT-компилятор оптимизирует код:


  • нода CheckStructure изначально проверяет тип массива в теле цикла, однако ее можно вынести, потому что тип массива один и тот же;
  • CheckBounds – остается, потому что есть зависимость от длины массива;
  • GetByVal – выносится, так как не зависит от переменных, определенных внутри цикла.

StructureCheck v8, expected_structure_id
GetByVal v8, -698666199

// Loop header
len = LoadArrayLength v8
// Do other loop header stuff

// Loop body
StoreProperty v8, 'a', 42
CheckBounds -698666199, len

// Jump back to beginning of loop

Поэтому можно читать и писать за пределы массива.


Эксплуатация багов в js-движках – это отдельный жанр. Баг выше было легко описать, поэтому он здесь. Другие находки fuzzilli тоже интересны, но они слишком заковыристые, и их не уместить в пару абзацев. Поэтому здесь они приведены списком.


Баги Gecko/Spidermonkey, Chromium/v8

Gecko/Spidermonkey


  • CVE-2018-12386: IonMonkey register allocation bug leads to type confusions
  • CVE-2019-9791: IonMonkey's type inference is incorrect for constructors entered via OSR
  • CVE-2019-9792: IonMonkey leaks JS_OPTIMIZED_OUT magic value to script
  • CVE-2019-9816: unexpected ObjectGroup in ObjectGroupDispatch operation
  • CVE-2019-9813: IonMonkey compiled code fails to update inferred property types, leading to type confusions
  • CVE-2019-11707: IonMonkey incorrectly predicts return type of Array.prototype.pop, leading to type confusions
  • CVE-2020-15656: Type confusion for special arguments in IonMonkey

Chromium/v8



Вывод


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


Еще больше деталей есть в трудах:



Если занимаетесь поиском багов в js, может пригодиться.

Комментарии (2)


  1. iKBAHT
    30.09.2022 13:31
    +2

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


    1. marxxt Автор
      30.09.2022 13:44

      Это нужно, чтобы в мутированном тесте осталась логика, чтобы тест оставался валидным js скриптом