1. Introdução: é possível transformar uma omelete de volta em ovos crus?

No desenvolvimento de software cotidiano, um compilador (como GCC, Clang/LLVM ou MSVC) traduz código-fonte legível em C, C++ ou Rust para um executável nativo em código de máquina (um arquivo PE .exe no Windows ou ELF no Linux). Mas o que acontece quando precisamos seguir na direção oposta — quando um analista de segurança disseca um ransomware, um engenheiro audita um driver proprietário ou uma empresa precisa manter um sistema legado de 25 anos cujo código-fonte foi perdido? Podemos alimentar o binário em um descompilador (Decompiler) e recuperar o código-fonte C original?

Um famoso aforismo da engenharia reversa resume o desafio: “Compilar é como quebrar ovos para fazer uma omelete; descompilar é tentar transformar a omelete de volta em ovos crus dentro da casca."

Do ponto de vista da matemática e da teoria da informação, a função de compilação $\mathcal{C}: \text{Source} \to \text{Binary}$ é um mapeamento muitos-para-um (não injetivo) com perda de informação. Infinitos programas-fonte distintos — diferindo em nomes de variáveis, comentários, laços (for vs. while) ou funções inline — compilam sob otimização (-O2, -O3) para exatamente a mesma sequência de bytes. Como a entropia condicional é $H(\text{Source} \mid \text{Binary}) > 0$, não existe uma função inversa única $\mathcal{C}^{-1}$ capaz de recuperar o que foi fisicamente apagado pela compilação e pela remoção de símbolos (strip). Pior ainda: pelo teorema de Rice e pelo problema da parada de Turing, separar com exatidão código e dados, resolver estaticamente todos os destinos de um salto indireto (jmp rax) ou decidir o aliasing de ponteiros são problemas matematicamente indecidíveis no caso geral.

Ainda assim, descompiladores industriais modernos — como IDA Pro (Hex-Rays), Ghidra (lançado pela NSA), Binary Ninja e angr — transformam diariamente megabytes de assembly em pseudocódigo C surpreendentemente limpo e estruturado. Neste artigo, dissecamos os seis estágios algorítmicos de um descompilador moderno.

2. O que a compilação destrói: o pipeline direto

1. Frontend (Análise léxica, sintática e de tipos $\to$ IR): comentários, macros #define, apelidos typedef, nomes de variáveis locais e açúcar sintático desaparecem ao descer para a representação intermediária (LLVM IR).
2. Otimizador Middle-End (-O2 / -O3): a expansão inline dissolve as fronteiras entre funções; o desenrolamento de laços (Loop Unrolling) e a vetorização SIMD transformam a estrutura de controle; a redução de força (Strength Reduction) substitui uma divisão inteira x / 10 por uma multiplicação em ponto fixo por uma constante mágica (imul 0x66666667).
3. Alocação de registradores Backend e strip: infinitos registradores virtuais SSA são mapeados via coloração de grafos nos apenas 16 registradores físicos do x86-64. Consequentemente, um mesmo registrador físico como rax é reutilizado para dezenas de variáveis desconexas de tipos diferentes, enquanto strip apaga a tabela de símbolos (.symtab) e as informações DWARF.

  flowchart TD
    subgraph Forward ["Compilação direta (Perda irreversível de informação)"]
        S1["Código-fonte de alto nível (.c / .cpp / .rs)<br/>Nomes, Structs, Typedefs, laços estruturados"]
        S2["IR de Middle-End (LLVM IR)<br/>Açúcar sintático apagado, funções inline, laços desenrolados"]
        S3["Binário de máquina sem símbolos (.exe / ELF)<br/>Reutilização de registradores, tipos apagados, saltos planos"]
        S1 -->|"Frontend"| S2 -->|"Otimizador e Backend"| S3
    end

    subgraph Backward ["Descompilação reversa (Reconstrução algorítmica)"]
        D1["1. Desmontagem (Disassembly)<br/>Fluxo de bytes para instruções (Varredura linear vs. Travessia recursiva)"]
        D2["2. Elevação IR e Transformação SSA<br/>Flags explícitas, divisão de tempo de vida, cadeias Def-Use"]
        D3["3. Quadro de pilha e Inferência de tipos em reticulado<br/>Recuperação de ponteiros, deslocamentos de structs e sinal"]
        D4["4. Estruturação de fluxo de controle (Recuperação AST)<br/>Árvores dominadoras e dobramento sem goto (DREAM)"]
        D1 --> D2 --> D3 --> D4
    end

    S3 ==>|"Entrada no descompilador"| D1

3. Estágio 1: Desmontagem — separando instruções de dados

Em arquiteturas de instruções de tamanho variável como x86-64 ($1$ a $15$ bytes), os compiladores frequentemente embutem dados somente leitura — especialmente tabelas de salto (Jump Tables) de comandos switch — diretamente dentro da seção de código .text.

1. Varredura linear (Linear Sweep, objdump -d): decodifica sequencialmente byte a byte, mas interpreta erroneamente tabelas de salto embutidas como instruções falsas.
2. Travessia recursiva (Recursive Traversal, IDA Pro / Ghidra): parte dos pontos de entrada conhecidos (main, símbolos exportados) e segue o grafo de fluxo de controle real através dos desvios (je, jmp, call). Para resolver saltos indiretos (jmp [rbx + rcx*8]), o descompilador usa fatiamento reverso (Backward Slicing) e análise de conjuntos de valores (Value-Set Analysis, VSA) para localizar a verificação de limites cmp rcx, 12; ja default e deduzir o tamanho da tabela.

4. Estágio 2: Elevação para IR (Lifting) e forma SSA (Static Single Assignment)

As instruções nativas possuem efeitos colaterais implícitos complexos (um simples sub eax, ebx em x86 modifica seis flags de estado: ZF, CF, SF, OF, PF, AF). O descompilador eleva (Lifting) primeiro o código nativo para uma representação intermediária independente de CPU (P-code no Ghidra, Microcode no Hex-Rays) e a transforma para a forma SSA (Static Single Assignment), onde cada variável recebe atribuição exatamente uma vez (inserindo funções $\phi$ $\text{rax}_3 = \phi(\text{rax}_1, \text{rax}_2)$ nas junções de fluxo):

• Eliminação de flags mortas: mais de $90\%$ dos cálculos de flags não lidos por saltos condicionais são eliminados instantaneamente via cadeias Def-Use.
• Propagação de expressões: a definição ZF_2 = (eax_2 == 0) é substituída diretamente dentro de if (ZF_2) para reconstruir if (eax_2 == 0).
• Divisão de tempo de vida (Live-Range Splitting): redes SSA disjuntas que compartilhavam o registrador físico rax são separadas automaticamente em variáveis locais C independentes (int v1; vs. Node *v2;).

5. Estágio 3: Análise de pilha e inferência de tipos via reticulados (Lattice)

Embora o código de máquina não tenha tipos explícitos, a semântica das instruções impõe restrições algébricas de tipo:

• Com sinal (int) vs. sem sinal (unsigned int): saltos condicionais jg / jl (Greater/Less), divisão com sinal idiv, deslocamento aritmético sar e extensão de sinal movsxd provam um inteiro com sinal (int); enquanto ja / jb (Above/Below), div, deslocamento lógico shr e extensão com zeros movzx provam um inteiro sem sinal (unsigned int).
• Reconstrução de ponteiros e struct: desreferenciar [rbx] gera a restrição $\text{ptr}(\tau)$. Acessar múltiplos deslocamentos constantes ([rbx + 0], [rbx + 8], [rbx + 16]) revela um ponteiro para uma estrutura composta struct S *.
• Reticulado de tipos (Type Lattice) e unificação: seguindo Alan Mycroft (1999) e o sistema TIE (CMU), o descompilador organiza os tipos em um reticulado parcialmente ordenado $(\mathcal{L}, \sqsubseteq)$ entre $\top$ (vetor de bits bruto) e $\bot$ (conflito de tipos / union), resolvendo as desigualdades de subtipo pelo ínfimo (Meet $\sqcap$).

  flowchart TD
    TOP["⊤ (Top: Vetor bruto de N bits bit64)"]
    NUM["num64 (Escalar inteiro ou ponteiro)"]
    FLT["float64 (Double IEEE 754: addsd, mulsd)"]
    SINT["int64_t (Com sinal: sar, idiv, jg, jl, movsxd)"]
    UINT["uint64_t (Sem sinal: shr, div, ja, jb)"]
    PTR["ptr(τ) (Ponteiro: desreferência [reg])"]
    STRUCT["struct S* (Ponteiro de struct: acessos [reg + offset])"]
    BOT["⊥ (Bottom: Conflito de tipos → Cast ou Union)"]

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

6. Estágio 4: Estruturação do fluxo de controle — eliminando goto para recuperar if e while

Para dobrar o grafo de fluxo de controle (CFG) em uma árvore sintática abstrata (AST) estruturada (Cifuentes 1994), o descompilador calcula a árvore dominadora e a árvore pós-dominadora:

1. Detecção de laços naturais: uma aresta de retorno (Back-Edge) $n \to h$ onde $h$ domina $n$ ($h \text{ dom } n$) define um laço natural com cabeçalho $h$ (while, for ou do-while).
2. Detecção de ramos (if-then-else): o pós-dominador imediato de um nó condicional marca o ponto exato onde o diamante if-else converge.
3. Estruturação sem goto (Algoritmo DREAM): mesmo diante de grafos irredutíveis gerados por otimizações, o algoritmo DREAM (“No More Gotos”, Yakdan et al. 2015) calcula as condições booleanas de alcançabilidade (Reaching Conditions) e aplica minimização lógica para garantir código C 100% livre de goto.

7. Limites da descompilação: camuflagem de otimização, ofuscação e descompiladores neurais (LLM)

Enquanto ofuscadores (OLLVM, VMProtect) atacam a análise estática via achatamento do fluxo de controle (CFF), predicados opacos, aritmética booleana mista (MBA, $x+y \equiv (x\oplus y) + 2(x\land y)$) e ofuscação por virtualização (tradução para um bytecode aleatório próprio), na década de 2020 os descompiladores neurais baseados em LLMs (LLM4Decompile) combinam análise formal com inteligência artificial estatística para inferir nomes significativos de variáveis e funções e reescrever código altamente otimizado em C idiomático.