Часть 1. QInst: лучше день потерять, потом за пять минут долететь (пишем инструментацию тривиально) +9


В предыдущей части я приблизительно описал, как можно загрузить eBPF функции из ELF-файла. Теперь пришла пора перейти от фэнтези к советским мультикам, и следуя мудрому совету, потратив один раз некоторое количество усилий, сделать универсальный инструмент инструментации (или, сокращённо, УИИ!!!). При этом я воспользуюсь антипаттерном проектирования «Золотой молоток» и сооружу инструмент из относительно знакомого мне QEMU. Бонусом за это мы получим кросс-архитектурную инструментацию, а также инструментацию на уровне целого виртуального компьютера. Инструментация будет вида «небольшой нативный so-шничек + небольшой .o-файл с eBPF». При этом eBPF-функции будут подставляться перед соответствующими инструкциями внутреннего представления QEMU перед оптимизацией и кодогенерацией.


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


#include <stdint.h>

extern uint8_t *__afl_area_ptr;
extern uint64_t prev;

void inst_qemu_brcond_i64(uint64_t tag, uint64_t x, uint64_t y, uint64_t z, uint64_t u)
{
    __afl_area_ptr[((prev >> 1) ^ tag) & 0xFFFF] += 1;
    prev = tag;
}

void inst_qemu_brcond_i32(uint64_t tag, uint64_t x, uint64_t y, uint64_t z, uint64_t u)
{
    __afl_area_ptr[((prev >> 1) ^ tag) & 0xFFFF] += 1;
    prev = tag;
}

Что же, пора загрузить нашего эльфа в Матрицу. Ну, как загрузить, скорее вмазать распылить.


Как уже упоминалось в статье про QEMU.js, один из режимов работы QEMU — это JIT-генерация хостового машинного кода из гостевого (потенциально, для совершенно другой архитектуры). Если в прошлый раз я реализовывал свой бекенд кодогенерации, то в этот раз я собираюсь обрабатывать внутреннее представление, вклинившись непосредственно перед оптимизатором. Произвольное ли это решение? Нет. Есть надежда, что оптимизатор срежет лишние углы, выкинет ненужные переменные и т.д. Насколько я понимаю, он, собственно, и занимается простыми и быстро выполнимыми вещами: проталкиванием констант, выкидыванием выражений вроде «x := x + 0» и удалением недостижимого кода. А уж его у нас может получиться порядочное количество.


Конфигурация сборочных скриптов


Первым делом давайте добавим наши файлы исходных текстов: tcg/bpf-loader.c и tcg/instrument.c в Makefile-ы. Вообще говоря, есть желание когда-нибудь запихнуть это в upstream, поэтому сделать в итоге нужно будет по уму, но пока я просто безусловным образом добавлю эти файлы в сборку. А параметры буду принимать в лучших традициях AFL — через переменные среды. Кстати, тестировать я это буду опять именно на инструментации для AFL.


Просто поищем упоминание «соседа» — файла optimize.c с помощью grep -R и ничего не найдём. Потому что искать надо было optimize.o:


--- a/Makefile.target
+++ b/Makefile.target
@@ -110,7 +110,7 @@ obj-y += trace/
 obj-y += exec.o
 obj-y += accel/
 obj-$(CONFIG_TCG) += tcg/tcg.o tcg/tcg-op.o tcg/tcg-op-vec.o tcg/tcg-op-gvec.o
-obj-$(CONFIG_TCG) += tcg/tcg-common.o tcg/optimize.o
+obj-$(CONFIG_TCG) += tcg/tcg-common.o tcg/optimize.o tcg/instrument.o tcg/bpf-loader.o
 obj-$(CONFIG_TCG_INTERPRETER) += tcg/tci.o
 obj-$(CONFIG_TCG_INTERPRETER) += disas/tci.o
 obj-$(CONFIG_TCG) += fpu/softfloat.o

Так вот ты какое, метапрограммирование на C...


Для начала допишем bpf-loader.c из прошлой серии кодом, выдёргивающим точки входа, соответствующие операциям QEMU. И поможет нам в этом загадочный файл tcg-opc.h. Выглядит он так:


/*
 * DEF(name, oargs, iargs, cargs, flags)
 */

/* predefined ops */
DEF(discard, 1, 0, 0, TCG_OPF_NOT_PRESENT)
DEF(set_label, 0, 0, 1, TCG_OPF_BB_END | TCG_OPF_NOT_PRESENT)

/* variable number of parameters */
DEF(call, 0, 0, 3, TCG_OPF_CALL_CLOBBER | TCG_OPF_NOT_PRESENT)

DEF(br, 0, 0, 1, TCG_OPF_BB_END)
// ...

Что за чепуха? А дело просто в том, что его не подключают в шапке исходника — нужно определить макрос DEF, включить этот файл, и сразу удалить макрос. Видите, у него даже guard-ов нет.


static const char *inst_function_names[] = {
#define DEF(name, a, b, c, d) stringify(inst_qemu_##name),
#include "tcg-opc.h"
#undef DEF
  NULL
};

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


ELF64_ST_BIND(sym->st_info) == STB_LOCAL || ELF64_ST_TYPE(sym->st_info) != STT_FUNC

Остальные сверяем со списком.


Привязываемся к потоку выполнения


Теперь нужно встать где-то на потоке выполнения механизма кодогенерации, и ждать, пока мимо не проплывёт интересующая инструкция. Но для начала нужно определить свои функции instrumentation_init, tcg_instrument и instrumentation_shutdown в файле tcg/tcg.h и прописать их вызовы: инициализацию — после инициализации бекенда, инструментацию — прямо перед вызовом tcg_optimize. Казалось бы, instrumentation_shutdown можно повесить в instrumentation_init на atexit и не париться. Я тоже так думал, и оно, скорее всего, так и заработает в режиме эмуляции полной системы, а вот в режиме usermode-эмуляции QEMU транслирует системные вызовы exit_group и иногда exit в вызов функции _exit, которая все эти atexit-handler-ы игнорирует, поэтому разыщем её в linux-user/syscall.c и впишем перед ней вызов нашего кода.


Интерпретируем байткод


Вот и настало время почитать, что же нам сгенерировал компилятор. Это удобно сделать с помощью llvm-objdump с параметром -x, а лучше сразу -d -t -r.


Пример вывода
$ ./compile-bpf.sh 

test-bpf.o:     file format ELF64-BPF

Disassembly of section .text:
0000000000000000 inst_brcond_i64:
       0:       18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00         r2 = 0 ll
                0000000000000000:  R_BPF_64_64  prev
       2:       79 23 00 00 00 00 00 00         r3 = *(u64 *)(r2 + 0)
       3:       77 03 00 00 01 00 00 00         r3 >>= 1
       4:       7b 32 00 00 00 00 00 00         *(u64 *)(r2 + 0) = r3
       5:       af 13 00 00 00 00 00 00         r3 ^= r1
       6:       57 03 00 00 ff ff 00 00         r3 &= 65535
       7:       18 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00         r4 = 0 ll
                0000000000000038:  R_BPF_64_64  __afl_area_ptr
       9:       79 44 00 00 00 00 00 00         r4 = *(u64 *)(r4 + 0)
      10:       0f 34 00 00 00 00 00 00         r4 += r3
      11:       71 43 00 00 00 00 00 00         r3 = *(u8 *)(r4 + 0)
      12:       07 03 00 00 01 00 00 00         r3 += 1
      13:       73 34 00 00 00 00 00 00         *(u8 *)(r4 + 0) = r3
      14:       7b 12 00 00 00 00 00 00         *(u64 *)(r2 + 0) = r1
      15:       95 00 00 00 00 00 00 00         exit

0000000000000080 inst_brcond_i32:
      16:       18 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00         r2 = 0 ll
                0000000000000080:  R_BPF_64_64  prev
      18:       79 23 00 00 00 00 00 00         r3 = *(u64 *)(r2 + 0)
      19:       77 03 00 00 01 00 00 00         r3 >>= 1
      20:       7b 32 00 00 00 00 00 00         *(u64 *)(r2 + 0) = r3
      21:       af 13 00 00 00 00 00 00         r3 ^= r1
      22:       57 03 00 00 ff ff 00 00         r3 &= 65535
      23:       18 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00         r4 = 0 ll
                00000000000000b8:  R_BPF_64_64  __afl_area_ptr
      25:       79 44 00 00 00 00 00 00         r4 = *(u64 *)(r4 + 0)
      26:       0f 34 00 00 00 00 00 00         r4 += r3
      27:       71 43 00 00 00 00 00 00         r3 = *(u8 *)(r4 + 0)
      28:       07 03 00 00 01 00 00 00         r3 += 1
      29:       73 34 00 00 00 00 00 00         *(u8 *)(r4 + 0) = r3
      30:       7b 12 00 00 00 00 00 00         *(u64 *)(r2 + 0) = r1
      31:       95 00 00 00 00 00 00 00         exit
SYMBOL TABLE:
0000000000000000 l    df *ABS*           00000000 test-bpf.c
0000000000000000 l    d  .text           00000000 .text
0000000000000000         *UND*           00000000 __afl_area_ptr
0000000000000080 g     F .text           00000080 inst_brcond_i32
0000000000000000 g     F .text           00000080 inst_brcond_i64
0000000000000008 g     O *COM*           00000008 prev

Если попробовать поискать описание опкодов eBPF, то обнаруживается, что в очевидных местах (исходниках и man-страницах ядра Linux) есть описания, как это использовать, как компилировать и т.д. После чего натыкаешься на страничку команды инструмента iovisor с удобным неофициальным справочником по eBPF.


Инструкция занимает одно 64-битное слово (некоторые — два) и имеет вид


struct {
  uint8_t opcode;
  uint8_t dst:4;
  uint8_t src:4;
  uint16_t offset;
  uint32_t imm;
};

Те, что занимают два слова, просто состоят из первой инструкции со всей логикой и «прицепа» с ещё 32-мя битами immediate-значения и очень хорошо заметны на objdump-овском дизассемблере.


Сами опкоды тоже имеют регулярную структуру: младшие три бита — это класс операции: 32-битное ALU, 64-битное ALU, load/store, условные переходы. Поэтому их очень удобно в лучших традициях QEMU реализовывать на макросах. Не буду проводить подробную инструкцию по кодовой базе мы не на code review, лучше расскажу про подводные камни.


Первая моя проблема заключалась в том, что я сделал ленивый аллокатор регистров eBPF в виде QEMU-вских local_temp, и стал бездумно передавать вызов этой функции в макрос. Получилось как в известном меме: «Мы вставили тебе абстракцию в абстракцию, чтобы ты мог генерировать инструкцию, пока генерируешь инструкцию». Post factum я уже сейчас плохо понимаю, что тогда сломалось, но с порядком генерируемых инструкций, по-видимому, творилось нечто странное. После этого я сделал аналоги функций tcg_gen_... для запихивания новых инструкций в середину списка, принимающих операнды как аргументы функции, и порядок стал автоматически таким, как надо (поскольку аргументы полностью вычисляются ровно один раз перед вызовом).


Вторая проблема заключалась в попытках запихнуть TCG const как операнд произвольной инструкции при виде immediate операнда в eBPF. Суля по уже упоминавшемуся tcg-opc.h, состав списка аргументов операции строго фиксирован: n входных аргументов, m выходных и k константных. Кстати, при отладке подобного кода очень помогает передать QEMU аргумент командной строки -d op,op_opt или даже -d op,op_opt,out_asm.


Возможные аргументы
$ ./x86_64-linux-user/qemu-x86_64 -d help
Log items (comma separated):
out_asm         show generated host assembly code for each compiled TB
in_asm          show target assembly code for each compiled TB
op              show micro ops for each compiled TB
op_opt          show micro ops after optimization
op_ind          show micro ops before indirect lowering
int             show interrupts/exceptions in short format
exec            show trace before each executed TB (lots of logs)
cpu             show CPU registers before entering a TB (lots of logs)
fpu             include FPU registers in the 'cpu' logging
mmu             log MMU-related activities
pcall           x86 only: show protected mode far calls/returns/exceptions
cpu_reset       show CPU state before CPU resets
unimp           log unimplemented functionality
guest_errors    log when the guest OS does something invalid (eg accessing a
non-existent register)
page            dump pages at beginning of user mode emulation
nochain         do not chain compiled TBs so that "exec" and "cpu" show
complete traces
trace:PATTERN   enable trace events

Use "-d trace:help" to get a list of trace events.

Ну так вот, не повторяйте моих ошибок: дизассемблер внутренних инструкций довольно продвинутый, и если вы видите в нём что-то вроде add_i64 loc15,loc15,$554412123213, то вот эта штуковина после знака доллара — вот это нифига не указатель. Точнее, это, конечно, указатель, но, возможно, обвешанный флажками и в роли литерального значения операнда, а не указателя. Всё это применимо, естественно, если вы знаете, что там должно быть какое-то конкретное число, вроде $0 или $ff, так-то вообще не надо бояться указателей. :) Как с этим побороться — просто нужно создать функцию, которая вернёт свежий temp, в который через movi положит нужную константу.


Кстати, если в шапке tcg/tcg.c закомментировать #define USE_TCG_OPTIMIZATIONS, то, внезапно, оптимизация отключится, и будет проще анализировать преобразования кода.


За сим я отправлю заинтересованного в ковырянии QEMU читателя в документацию, даже официальную! А остальным я продемонстрирую обещанную инструментацию для AFL.


Те же и кролик


За полным текстом runtime я, опять же, отошлю читателя в репозиторий, поскольку он (текст) не представляет художественной ценности и честно стырен из qemu_mode из поставки AFL, и вообще, представляет из себя обычный кусок кода на C. А вот как выглядит сама инструментация:


#include <stdint.h>

extern uint8_t *__afl_area_ptr;
extern uint64_t prev;

void inst_qemu_brcond_i64(uint64_t tag, uint64_t x, uint64_t y, uint64_t z, uint64_t u)
{
    __afl_area_ptr[((prev >> 1) ^ tag) & 0xFFFF] += 1;
    prev = tag;
}

void inst_qemu_brcond_i32(uint64_t tag, uint64_t x, uint64_t y, uint64_t z, uint64_t u)
{
    __afl_area_ptr[((prev >> 1) ^ tag) & 0xFFFF] += 1;
    prev = tag;
}

Важно, чтобы у функций-хуков было столько же аргументов, сколько iargs у соответствующей операции QEMU. Два extern-а в шапке будут прилинкованы к рантайму в процессе релокации. В принципе, prev можно было бы прямо здесь и определить, но тогда его нужно определить как static, иначе он упадет в не поддерживаемую мной секцию COMMON. Собственно, мы, фактически, просто переписали псевдокод из документации, но здесь он машиночитаемый!


Для проверки создадим файл bug.c:


#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  char buf[16];
  int res = read(0, buf, 4);
  if (buf[0] == 'T' && buf[1] == 'E' && buf[2] == 'S' && buf[3] == 'T')
    abort();
  return res * 0;
}

А ещё — файл forksrv, который удобно скармливать AFL:


#!/bin/bash

export NATIVE_INST=./instrumentation-examples/afl/afl-native.so
export BPF_INST=./instrumentation-examples/afl/afl-bpf.c.o
exec ./x86_64-linux-user/qemu-x86_64 ./instrumentation-examples/afl/bug

И запустим фаззинг:


AFL_SKIP_BIN_CHECK=1 afl-fuzz -i ../input -o ../output -m none -- ./forksrv

American Fuzzy Lop (кродеться)
1234
T234
TE34
TES4
TEST <- а это уже в crashes, полторы минуты и 2200 запусков спустя

Пока что скорость не ахти, но в оправдание скажу, что здесь (пока что) не используется важная фича оригинального qemu_mode: отправка адресов исполняемого кода в fork server. Зато ничего AFL-ного в кодовой базе QEMU теперь нет, и есть надежда эту обобщённую инструментацию когда-нибудь запихнуть в upstream.


Проект на GitHub




К сожалению, не доступен сервер mySQL