![](https://habrastorage.org/webt/jw/wm/9i/jwwm9iiwuhuwvorbyptlxumgwpi.png)
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
, поможет диаграмма:
![](https://habrastorage.org/webt/5s/_i/tk/5s_itkmgran6uowndc9ekbe1tqa.jpeg)
Типом данных, отвечающим за итоговый 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
, у LoadProperty
– propertyName
, а у CallMethod
– methodName
.
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
- 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
- Issue 939316: Turbofan may read a Map pointer out-of-bounds when optimizing Reflect.construct
- Issue 944062: JSCallReducer::ReduceArrayIndexOfIncludes fails to insert Map checks
- CVE-2019-5831: Incorrect map processing in V8
- Issue 944865: Invalid value representation in V8
- CVE-2019-5841: Bug in inlining heuristic
- CVE-2019-5847: V8 sealed/frozen elements cause crash
- CVE-2019-5853: Memory corruption in regexp length check
- Issue 992914: Map migration doesn't respect element kinds, leading to type confusion
- CVE-2020-6512: Type Confusion in V8
- CVE-2020-16006: Memory corruption due to improperly handled hash collision in DescriptorArray
- CVE-2021-37991: Race condition during concurrent JIT compilation
Вывод
fuzzilli
– это фаззер для js
-движков, который обеспечивает большее покрытие кода, потому что генерирует и синтаксически и семантически валидный код, то есть настоящие js
-скрипты. В этой статье мы разобрали, как оно работает.
Еще больше деталей есть в трудах:
FuzzIL: Coverage Guided Fuzzing for JavaScript Engines
The hunt for Chromium issue 1072171
Fuzzing JavaScript Engines with Fuzzilli
Если занимаетесь поиском багов в js
, может пригодиться.