1. Introducción: ¿se puede convertir una tortilla de nuevo en huevos crudos?

En el desarrollo de software cotidiano, un compilador (como GCC, Clang/LLVM o MSVC) traduce código fuente legible en C, C++ o Rust a un ejecutable en código máquina (un archivo PE .exe en Windows o ELF en Linux). Pero ¿qué ocurre cuando necesitamos ir en sentido contrario: cuando un analista de seguridad disecciona un ransomware, un ingeniero audita un controlador propietario o una empresa necesita mantener un sistema crítico de hace 25 años cuyo código fuente se perdió? ¿Podemos introducir el binario en un descompilador (Decompiler) y recuperar el código fuente C original?

Un famoso aforismo de la ingeniería inversa resume el desafío: «Compilar es como batir huevos para hacer una tortilla; descompilar es intentar convertir la tortilla de nuevo en huevos crudos dentro de su cáscara».

Desde la matemática y la teoría de la información, la función de compilación $\mathcal{C}: \text{Source} \to \text{Binary}$ es una aplicación muchos-a-uno (no inyectiva) con pérdida de información. Infinitos programas fuente distintos —que difieren en nombres de variables, comentarios, bucles (for frente a while) o funciones inline— producen tras la optimización (-O2, -O3) exactamente la misma secuencia de bytes. Como la entropía condicional es $H(\text{Source} \mid \text{Binary}) > 0$, no existe una función inversa única $\mathcal{C}^{-1}$ que recupere lo que fue físicamente borrado por la compilación y la eliminación de símbolos (strip). Más aún, por el teorema de Rice y el problema de la parada de Turing, separar con exactitud código y datos, resolver todos los destinos de un salto indirecto (jmp rax) o decidir el aliasing de punteros son problemas matemáticamente indecidibles en el caso general.

Sin embargo, los descompiladores industriales modernos —como IDA Pro (Hex-Rays), Ghidra (publicado por la NSA), Binary Ninja y angr— transforman a diario megabytes de ensamblador en pseudocódigo C sorprendentemente limpio y estructurado. En este artículo analizamos las seis etapas algorítmicas de un descompilador moderno.

2. Qué destruye la compilación: la tubería directa

1. Frontend (Análisis léxico, sintáctico y de tipos $\to$ IR): comentarios, macros #define, alias typedef, nombres de variables locales y azúcar sintáctico desaparecen al bajar a la representación intermedia (LLVM IR).
2. Optimizador Middle-End (-O2 / -O3): la expansión inline disuelve las fronteras entre funciones; el desenrollado de bucles (Loop Unrolling) y la vectorización SIMD transforman la estructura de control; la reducción de fuerza (Strength Reduction) sustituye una división entera x / 10 por una multiplicación de punto fijo con una constante mágica (imul 0x66666667).
3. Asignación de registros Backend y strip: infinitos registros virtuales SSA se proyectan mediante coloración de grafos sobre apenas 16 registros físicos en x86-64. En consecuencia, un mismo registro físico como rax se reutiliza para docenas de variables inconexas de distintos tipos, mientras que strip borra la tabla de símbolos (.symtab) y la información DWARF.

  flowchart TD
    subgraph Forward ["Compilación directa (Pérdida irreversible de información)"]
        S1["Código fuente de alto nivel (.c / .cpp / .rs)<br/>Nombres, Structs, Typedefs, bucles estructurados"]
        S2["IR de Middle-End (LLVM IR)<br/>Azúcar sintáctico borrado, funciones inline, bucles desenrollados"]
        S3["Binario máquina sin símbolos (.exe / ELF)<br/>Reutilización de registros, tipos borrados, saltos planos"]
        S1 -->|"Frontend"| S2 -->|"Optimizador y Backend"| S3
    end

    subgraph Backward ["Descompilación inversa (Reconstrucción algorítmica)"]
        D1["1. Desensamblado<br/>Flujo de bytes a instrucciones (Barrido lineal vs. Recorrido recursivo)"]
        D2["2. Elevación IR y Transformación SSA<br/>Banderas explícitas, división de rangos de vida, cadenas Def-Use"]
        D3["3. Marco de pila e Inferencia de tipos en retículo<br/>Recuperación de punteros, desplazamientos de structs y signo"]
        D4["4. Estructuración de flujo de control (Recuperación AST)<br/>Árboles dominadores y plegado sin goto (DREAM)"]
        D1 --> D2 --> D3 --> D4
    end

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

3. Etapa 1: Desensamblado — separar instrucciones de datos

En arquitecturas de longitud de instrucción variable como x86-64 ($1$ a $15$ bytes), los compiladores suelen incrustar datos de solo lectura —en especial tablas de salto (Jump Tables) para sentencias switch— directamente dentro de la sección de código .text.

1. Barrido lineal (Linear Sweep, objdump -d): decodifica secuencialmente byte tras byte, pero interpreta erróneamente las tablas de salto incrustadas como instrucciones falsas.
2. Recorrido recursivo (Recursive Traversal, IDA Pro / Ghidra): parte de los puntos de entrada conocidos (main, símbolos exportados) y sigue el grafo de flujo de control real a través de los saltos (je, jmp, call). Para resolver saltos indirectos (jmp [rbx + rcx*8]), el descompilador emplea rebanado hacia atrás (Backward Slicing) y análisis de conjuntos de valores (Value-Set Analysis, VSA) para localizar la comprobación de límites cmp rcx, 12; ja default y deducir el tamaño de la tabla.

4. Etapa 2: Elevación a IR (Lifting) y forma SSA (Static Single Assignment)

Las instrucciones nativas tienen complejos efectos secundarios implícitos (un simple sub eax, ebx en x86 modifica seis banderas de estado: ZF, CF, SF, OF, PF, AF). El descompilador eleva (Lifting) primero el código nativo a una representación intermedia independiente de la CPU (P-code en Ghidra, Microcode en Hex-Rays) y la transforma a forma SSA (Static Single Assignment), donde cada variable se asigna exactamente una vez (insertando funciones $\phi$ $\text{rax}_3 = \phi(\text{rax}_1, \text{rax}_2)$ en las uniones de flujo):

• Eliminación de banderas muertas: más del $90\%$ de los cálculos de banderas no leídos por saltos condicionales se eliminan al instante mediante las cadenas Def-Use.
• Propagación de expresiones: la definición ZF_2 = (eax_2 == 0) se sustituye directamente dentro de if (ZF_2) para reconstruir if (eax_2 == 0).
• División de rangos de vida (Live-Range Splitting): las redes SSA disjuntas que compartían el registro físico rax se separan automáticamente en variables locales C independientes (int v1; frente a Node *v2;).

5. Etapa 3: Análisis de pila e inferencia de tipos mediante retículos (Lattice)

Aunque el código máquina carece de tipos explícitos, la semántica de las instrucciones impone restricciones algebraicas de tipo:

• Con signo (int) frente a sin signo (unsigned int): los saltos condicionales jg / jl (Greater/Less), la división con signo idiv, el desplazamiento aritmético sar y la extensión de signo movsxd demuestran un entero con signo (int); mientras que ja / jb (Above/Below), div, el desplazamiento lógico shr y la extensión con ceros movzx demuestran un entero sin signo (unsigned int).
• Reconstrucción de punteros y struct: desreferenciar [rbx] genera la restricción $\text{ptr}(\tau)$. Acceder a múltiples desplazamientos constantes ([rbx + 0], [rbx + 8], [rbx + 16]) revela un puntero a una estructura compuesta struct S *.
• Retículo de tipos (Type Lattice) y unificación: siguiendo a Alan Mycroft (1999) y el sistema TIE (CMU), el descompilador organiza los tipos en un retículo parcialmente ordenado $(\mathcal{L}, \sqsubseteq)$ entre $\top$ (vector de bits bruto) y $\bot$ (conflicto de tipos / union), resolviendo las desigualdades de subtipo mediante el ínfimo (Meet $\sqcap$).

  flowchart TD
    TOP["⊤ (Top: Vector bruto de N bits bit64)"]
    NUM["num64 (Escalar entero o puntero)"]
    FLT["float64 (Doble IEEE 754: addsd, mulsd)"]
    SINT["int64_t (Con signo: sar, idiv, jg, jl, movsxd)"]
    UINT["uint64_t (Sin signo: shr, div, ja, jb)"]
    PTR["ptr(τ) (Puntero: desreferencia [reg])"]
    STRUCT["struct S* (Puntero a struct: accesos [reg + offset])"]
    BOT["⊥ (Bottom: Conflicto de tipos → Cast o Union)"]

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

6. Etapa 4: Estructuración del flujo de control — eliminar los goto para recuperar if y while

Para plegar el grafo de flujo de control (CFG) en un árbol sintáctico abstracto (AST) estructurado (Cifuentes 1994), el descompilador calcula el árbol dominador y el árbol post-dominador:

1. Detección de bucles naturales: una arista de retroceso (Back-Edge) $n \to h$ donde $h$ domina a $n$ ($h \text{ dom } n$) define un bucle natural con cabecera $h$ (while, for o do-while).
2. Detección de ramas (if-then-else): el post-dominador inmediato de un nodo condicional marca el punto exacto donde converge el diamante if-else.
3. Estructuración sin goto (Algoritmo DREAM): incluso ante grafos irreducibles generados por optimizaciones, el algoritmo DREAM («No More Gotos», Yakdan et al. 2015) calcula las condiciones booleanas de alcanzabilidad (Reaching Conditions) y aplica minimización lógica para garantizar código C 100 % libre de goto.

7. Límites de la descompilación: camuflaje de optimización, ofuscación y descompiladores neuronales (LLM)

Mientras que los ofuscadores (OLLVM, VMProtect) atacan el análisis estático mediante aplanamiento del flujo de control (CFF), predicados opacos, aritmética booleana mixta (MBA, $x+y \equiv (x\oplus y) + 2(x\land y)$) y ofuscación por virtualización (traducción a un bytecode aleatorio propio), en la década de 2020 los descompiladores neuronales basados en LLM (LLM4Decompile) combinan el análisis formal con inteligencia artificial estadística para inferir nombres significativos de variables y funciones y reescribir código altamente optimizado en C natural.