1. Введение: можно ли превратить омлет обратно в сырое яйцо?

В повседневной разработке компилятор (GCC, Clang/LLVM, MSVC) переводит понятный человеку исходный код на C, C++ или Rust в машинный исполняемый файл (PE-файл .exe в Windows или ELF в Linux). Но что, если нужно пройти этот путь в обратном направлении — например, когда вирусолог исследует шифровальщик, аудитор безопасности проверяет закрытый драйвер или инженеры поддерживают 25-летнюю систему, исходный код которой утерян? Можно ли подать машинный бинарник на вход декомпилятору (Decompiler) и получить исходный код на C?

В мире реверс-инжиниринга есть знаменитый афоризм: «Компиляция похожа на взбивание и жарку яиц для приготовления омлета; декомпиляция — это попытка превратить готовый омлет обратно в сырые яйца в скорлупе».

С точки зрения математики и теории информации функция компиляции $\mathcal{C}: \text{Source} \to \text{Binary}$ представляет собой неинъективное отображение «многие-к-одному» с потерей информации. Бесконечное множество различных исходных программ — отличающихся именами переменных, комментариями, конструкциями циклов (for против while) и встроенными (inlined) функциями — после оптимизации (-O2, -O3) компилируются в абсолютно идентичную последовательность байтов. Поскольку условная энтропия $H(\text{Source} \mid \text{Binary}) > 0$ строго положительна, однозначной обратной функции $\mathcal{C}^{-1}$ не существует. Более того, согласно теореме Райса и проблеме остановки Тьюринга, точное отделение кода от данных, статическое разрешение косвенных переходов (jmp rax) и анализ алиасинга указателей в общем случае математически неразрешимы (undecidable).

И всё же современные промышленные декомпиляторы — IDA Pro (Hex-Rays), открытая Агентством национальной безопасности США Ghidra, Binary Ninja и angr — ежедневно превращают мегабайты машинного кода в чистый, структурированный псевдокод на C. В этой статье мы разберём шесть ключевых алгоритмических этапов современного декомпилятора.

2. Что уничтожает компиляция: прямой конвейер

1. Фронтенд (лексический/синтаксический анализ и проверка типов $\to$ IR): комментарии, макросы #define, псевдонимы typedef, имена локальных переменных и синтаксический сахар исчезают при переводе в промежуточное представление (LLVM IR).
2. Оптимизатор среднего уровня (-O2 / -O3): подстановка функций (Inlining) стирает границы между функциями; размотка циклов (Loop Unrolling) и SIMD-векторизация меняют структуру управления; снижение стоимости операций (Strength Reduction) заменяет целочисленное деление x / 10 умножением на магическую константу с фиксированной точкой (imul 0x66666667).
3. Распределение регистров и strip: бесконечное число виртуальных SSA-регистров отображается путём раскраски графа всего на 16 физических регистров общего назначения x86-64. В результате один и тот же физический регистр rax многократно переиспользуется для совершенно разных переменных разных типов, а утилита strip удаляет таблицу символов (.symtab) и отладочную информацию DWARF.

  flowchart TD
    subgraph Forward ["Прямая компиляция (Необратимая потеря информации)"]
        S1["Исходный код высокого уровня (.c / .cpp / .rs)<br/>Имена, Structs, Typedefs, циклы"]
        S2["Промежуточное представление (LLVM IR)<br/>Стирание сахара, инлайнинг, размотка циклов"]
        S3["Очищенный машинный бинарник (.exe / ELF)<br/>Переиспользование регистров, стирание типов, плоские переходы"]
        S1 -->|"Фронтенд"| S2 -->|"Оптимизатор и Бэкенд"| S3
    end

    subgraph Backward ["Обратная декомпиляция (Алгоритмическая реконструкция)"]
        D1["1. Дизассемблирование<br/>Поток байтов в инструкции (Линейный vs Рекурсивный обход)"]
        D2["2. Подъём в IR (Lifting) и SSA-форма<br/>Явные флаги, разделение времён жизни, цепочки Def-Use"]
        D3["3. Анализ стека и вывод типов на решётках<br/>Восстановление указателей, смещений struct и знаковости"]
        D4["4. Структурирование потока управления (AST)<br/>Деревья доминаторов и свёртка без goto (DREAM)"]
        D1 --> D2 --> D3 --> D4
    end

    S3 ==>|"Вход декомпилятора"| D1

3. Этап 1: Дизассемблирование — отделение инструкций от данных

В архитектурах с переменной длиной инструкций, таких как x86-64 (от $1$ до $15$ байт), компиляторы часто размещают неизменяемые данные — в частности, таблицы переходов (Jump Tables) для операторов switch — прямо внутри кодовой секции .text.

1. Линейный проход (Linear Sweep, objdump -d): декодирует байты подряд от начала до конца и ошибочно интерпретирует встроенные таблицы переходов как ложные инструкции.
2. Рекурсивный обход (Recursive Traversal, IDA Pro / Ghidra): стартует с известных точек входа (main, экспортируемые функции) и следует по реальному графу потока управления вдоль переходов (je, jmp, call). Для разрешения косвенных переходов (jmp [rbx + rcx*8]) декомпилятор использует обратный слайсинг и анализ множеств значений (Value-Set Analysis, VSA), находя проверку границ cmp rcx, 12; ja default и определяя размер таблицы.

4. Этап 2: Подъём в IR (Lifting) и статическое однократное присваивание (SSA)

Машинные инструкции полны неявных побочных эффектов (одна инструкция sub eax, ebx в x86 перезаписывает сразу шесть флагов состояния: ZF, CF, SF, OF, PF, AF). Декомпилятор сначала поднимает (Lifting) нативный код в архитектурно-независимое промежуточное представление (P-code в Ghidra, Microcode в Hex-Rays), а затем переводит его в SSA-форму (Static Single Assignment), где каждой переменной значение присваивается ровно один раз (с $\phi$-функциями $\text{rax}_3 = \phi(\text{rax}_1, \text{rax}_2)$ в узлах слияния):

• Удаление мёртвых флагов: более $90\%$ вычислений флагов, которые нигде не читаются, мгновенно удаляются по цепочкам Def-Use.
• Продвижение выражений: определение ZF_2 = (eax_2 == 0) подставляется прямо в if (ZF_2), восстанавливая условие if (eax_2 == 0).
• Разделение времён жизни регистров (Live-Range Splitting): несвязанные SSA-сети, использовавшие один физический регистр rax, автоматически распадаются на независимые локальные переменные C (int v1; и Node *v2;)!

5. Этап 3: Анализ кадра стека и вывод типов на решётках (Lattice Type Inference)

Хотя в машинном коде нет явных типов, семантика инструкций процессора накладывает строгие алгебраические ограничения на типы:

• Знаковые (int) против беззнаковых (unsigned int): условные переходы jg / jl (Greater/Less), знаковое деление idiv, арифметический сдвиг sar и знаковое расширение movsxd доказывают знаковый тип (int); переходы ja / jb (Above/Below), div, логический сдвиг shr и нулевое расширение movzx доказывают беззнаковый тип (unsigned int)!
• Восстановление указателей и структур (struct): разыменование [rbx] порождает ограничение $\text{ptr}(\tau)$, а обращения по константным смещениям ([rbx + 0], [rbx + 8], [rbx + 16]) раскрывают структуру составного типа struct S *.
• Решётка типов (Type Lattice) и унификация: следуя работе Алана Майкрофта (1999) и системе TIE (CMU), декомпилятор упорядочивает все типы в частично упорядоченную решётку $(\mathcal{L}, \sqsubseteq)$ между $\top$ (сырой битовый вектор) и $\bot$ (конфликт типов / union), глобально решая систему неравенств через точную нижнюю грань (Meet $\sqcap$).

  flowchart TD
    TOP["⊤ (Top: Сырой N-битный вектор bit64)"]
    NUM["num64 (Скалярное число или указатель)"]
    FLT["float64 (Double IEEE 754: addsd, mulsd)"]
    SINT["int64_t (Знаковый: sar, idiv, jg, jl, movsxd)"]
    UINT["uint64_t (Беззнаковый: shr, div, ja, jb)"]
    PTR["ptr(τ) (Указатель: разыменование [reg])"]
    STRUCT["struct S* (Указатель на структуру: [reg + offset])"]
    BOT["⊥ (Bottom: Конфликт типов → Cast или Union)"]

    TOP --> NUM
    TOP --> FLT
    NUM --> SINT
    NUM --> UINT
    UINT --> PTR
    PTR --> STRUCT
    SINT --> BOT
    STRUCT --> BOT
    FLT --> BOT

6. Этап 4: Структурирование потока управления — от графа goto к if и while

Чтобы свернуть плоский граф потока управления (CFG) во вложенное абстрактное синтаксическое дерево (AST) (Cifuentes 1994), декомпилятор строит дерево доминаторов и дерево постдоминаторов:

1. Выделение естественных циклов: обратная дуга (Back-Edge) $n \to h$, где $h$ доминирует над $n$ ($h \text{ dom } n$), определяет цикл с заголовком $h$ (while, for или do-while).
2. Слияние ветвлений (if-then-else): непосредственный постдоминатор условного узла указывает точную вершину слияния ромба if-else.
3. Структурирование без goto (алгоритм DREAM): даже для неприводимых графов (Irreducible CFG) алгоритм DREAM («No More Gotos», Yakdan et al. 2015) вычисляет булевы условия достижимости (Reaching Conditions) и минимизирует логические формулы, гарантируя генерацию кода на C на 100 % без операторов goto!

7. Пределы декомпиляции: оптимизации, обфускация и нейросетевые LLM-декомпиляторы

В то время как обфускаторы (OLLVM, VMProtect) разрушают статический анализ с помощью выпрямления потока управления (CFF), непрозрачных предикатов, смешанной булевой арифметики (MBA, $x+y \equiv (x\oplus y) + 2(x\land y)$) и виртуализации кода (компиляции в случайный проприетарный байткод), в 2020-х годах появились нейросетевые LLM-декомпиляторы (LLM4Decompile), которые объединяют формальный анализ со статистическим ИИ для восстановления осмысленных имён переменных и перевода агрессивно оптимизированного кода в естественный C.