Anatomía de un decompilador

Este capítulo no introduce ninguna técnica nueva. Recompone las de los veintitrés anteriores en el orden en que un decompilador real las aplica, y explica por qué ese orden es el que es, dónde está cada fase con respecto a todo lo anterior, y qué falla cuando falla.

24.1 El pipeline

   +-------------------------------------------------------------+
   |  0. Carga: secciones, reubicaciones, simbolos, metadatos     |
   +----------------------------+--------------------------------+
                                v
   +-------------------------------------------------------------+
   |  1. Desensamblado: bytes -> instrucciones          (cap. 3)  |<--+
   +----------------------------+--------------------------------+   |
                                v                                    |
   +-------------------------------------------------------------+   |
   |  2. Construccion del CFG: dominadores, bucles      (cap. 4)  |<-+|
   +----------------------------+--------------------------------+  ||
                                v                                   ||
   +-------------------------------------------------------------+  ||
   |  3. Elevacion a IR: banderas explicitas            (cap. 3)  |  ||
   +----------------------------+--------------------------------+  ||
                                v                                   ||
   +-------------------------------------------------------------+  ||
   |  4. Forma SSA sobre registros                  (cap. 12, 13) |  ||
   +----------------------------+--------------------------------+  ||
                                v                                   ||
   +-------------------------------------------------------------+  ||
   |  5. Analisis de valores (VSA) y de punteros    (cap. 8, 18)  |--+|
   +----------------------------+--------------------------------+   |
                                v                                    |
   +-------------------------------------------------------------+   |
   |  6. Recuperacion de variables; SSA sobre memoria (cap. 16)   |   |
   +----------------------------+--------------------------------+   |
                                v                                    |
   +-------------------------------------------------------------+   |
   |  7. Interprocedural: prototipos, resumenes  (cap. 10, 11, 17)|---+
   +----------------------------+--------------------------------+
                                v
   +-------------------------------------------------------------+
   |  8. Recuperacion de tipos                          (cap. 19) |
   +----------------------------+--------------------------------+
                                v
   +-------------------------------------------------------------+
   |  9. Simplificacion: SCCP, GVN, DCE            (cap. 15, 22)  |
   +----------------------------+--------------------------------+
                                v
   +-------------------------------------------------------------+
   | 10. Estructuracion de control                       (cap. 4) |
   +----------------------------+--------------------------------+
                                v
   +-------------------------------------------------------------+
   | 11. Emision de pseudocodigo                                  |
   +-------------------------------------------------------------+

Las tres flechas de retroceso son lo esencial. El pipeline no es lineal: el análisis de valores descubre destinos de saltos indirectos que amplían el CFG, lo que obliga a rehacer el desensamblado, la construcción del CFG y la forma SSA; y el análisis interprocedural cambia los prototipos, lo que cambia lo que las llamadas leen y escriben, lo que cambia el análisis de punteros. Cada vuelta es la iteración del capítulo «7», aplicada al pipeline entero en lugar de a un solo análisis.

24.2 Fase 0: carga

Antes de que empiece nada de lo anterior hay que resolver el formato: qué secciones hay, cuáles son ejecutables, dónde está el punto de entrada, qué símbolos y reubicaciones existen, qué bibliotecas se importan.

Es la única fase puramente mecánica del pipeline, y sin embargo determina mucho de lo que viene después. La información de depuración, si existe, cortocircuita varias fases posteriores: da los nombres, los tipos, las fronteras de las funciones y los prototipos, es decir, precisamente lo que los capítulos «8», «10», «18» y «19» se esfuerzan en reconstruir. De ahí que la diferencia entre analizar un binario con símbolos y uno sin ellos sea de orden de magnitud.

Las tablas de excepciones —.eh_frame en ELF, .pdata en PE— merecen mención aparte: contienen información sobre las fronteras de las funciones y sobre el desenrollado de la pila que un binario sin símbolos suele conservar, y son la mejor fuente disponible para delimitar funciones.

24.3 Fases 1 y 2: del byte al grafo

El desensamblado y la construcción del CFG se tratan juntos porque son el mismo problema, por el círculo vicioso del capítulo «1»: para saber qué bytes son instrucciones hay que saber a dónde salta el control, y para eso hay que analizar los valores, para lo que hace falta el CFG.

Del capítulo «3»: barrido lineal frente a descenso recursivo, sus dos fallos característicos, y las heurísticas que los complementan —firmas de prólogos, tablas de excepciones, reconocimiento de patrones de tabla de saltos por compilador—. Del capítulo «4»: bloques básicos, dominadores, postdominadores, dependencia de control, bucles naturales, y la comprobación de reducibilidad.

El resultado de esta fase es una hipótesis, no un hecho, y todo lo posterior hereda su error. Los bloques marcados como unresolved son la deuda que el resto del pipeline tendrá que pagar.

24.4 Fase 3: elevación a IR

Traducir cada instrucción máquina a una secuencia de operaciones elementales con banderas y efectos explícitos, según el capítulo «3». Es la fase que hace tratable todo lo demás, y también donde se introducen las primeras aproximaciones: ninguna IR modela la arquitectura completa, y los huecos —instrucciones privilegiadas, extensiones vectoriales, comportamiento ante excepciones— son vías por las que un binario adversario puede hacer mentir al análisis.

La decisión de diseño más visible es el tratamiento de las banderas: eager, como P-Code, que las calcula todas explícitamente y es fácil de analizar pero produce mucha IR; o perezoso, como VEX, que las representa mediante cc_op/cc_dep y es rápido pero difícil de analizar.

24.5 Fase 4: SSA sobre registros

Construir la forma SSA con el algoritmo del capítulo «13», tomando como «variables» los registros arquitectónicos, las banderas y los temporales de la IR. Es sorprendentemente barato: el número de variables está acotado por la arquitectura.

Lo que se gana es lo del capítulo «12»: separar los usos independientes del mismo registro. Es el paso que convierte un desensamblado en algo con estructura de datos analizable, y la base de todo lo que sigue. Las φ con argumento ⊥ son ya un primer diagnóstico: señalan parámetros no reconocidos o predecesores que faltan en el CFG.

Lo que no se resuelve aquí es la memoria: [rbp-0x18] sigue siendo una operación, no una variable.

24.6 Fases 5 y 6: valores, punteros y memoria

Ésta es la fase decisiva, y la que más determina la calidad del resultado final.

Análisis de valores (capítulo «8»), en la forma de VSA: regiones de memoria —global, un marco por procedimiento, una por sitio de asignación— e intervalos con paso. Necesita widening, y de ahí vienen los rangos [0, +∞) que uno ve en las herramientas.

Análisis de punteros (capítulo «18»): Andersen o Steensgaard adaptados, con celdas abstractas que llevan región y desplazamiento porque la aritmética de punteros es constante en un binario. Su precisión fija el techo de todo lo demás.

Recuperación de variables: particionar cada región según los desplazamientos y tamaños accedidos. Es lo que convierte [rbp-0x18] en una variable local, y base+8 en un campo. Se apoya en los dos análisis anteriores y suele ir acompañada de la identificación de estructuras agregadas.

SSA sobre memoria (capítulo «16»): con las variables recuperadas, se aplica HSSA. Cada variable recuperada se convierte en una variable virtual; cada escritura potencialmente aliasada genera una χ; cada lectura potencial y cada llamada generan μ; y las versiones cero absorben lo que no se sabe.

Aquí se materializa la observación del capítulo «16»: el techo de precisión del decompilador lo fija el análisis de alias. Y aquí es donde la intervención del analista rinde más: declarar un tipo de estructura equivale a suministrar a mano la partición que el análisis no pudo calcular.

24.7 Fase 7: interprocedural

Inferencia de prototipos (capítulo «10»): los parámetros son lo que la función lee antes de escribir —variables vivas a la entrada, capítulo «6»— y el retorno es lo que escribe y el llamador lee. Es análisis intraprocedural puesto al servicio de una pregunta interprocedural.

Grafo de llamadas (capítulo «17»): resolver call rax mediante análisis de flujo de control basado en restricciones, y las llamadas virtuales de C++ mediante reconstrucción de vtables y CHA/RTA. Cada resolución amplía el grafo y realimenta la fase 5.

Resúmenes de función (capítulos «10» y «11»): qué lee, qué escribe, qué devuelve, si puede no retornar. Para las funciones de biblioteca vienen de una base de datos; para las del binario se calculan por punto fijo sobre el grafo de llamadas. Un resumen ausente obliga a suponer lo peor, y suponer lo peor en una llamada invalida todo lo que se sabía sobre la memoria.

Análisis de taint (capítulo «11»), si el objetivo es buscar vulnerabilidades: IFDS sobre el CFG explotado, con las fuentes y sumideros configurados.

24.8 Fase 8: tipos

Inferencia de tipos por subtipado, no por unificación, según el capítulo «19»: las fuentes de información en un binario se contradicen, y un sistema de igualdades no tendría solución. El resultado es un intervalo de tipos por variable, y lo que el decompilador muestra es una elección dentro de ese intervalo.

Las fuentes: la instrucción usada, el tamaño del acceso, los prototipos conocidos, la clase de comparación, y la RTTI si existe. La más valiosa con diferencia es la de los prototipos de biblioteca, lo que explica que las bases de datos de firmas importen tanto.

24.9 Fase 9: simplificación

Ahora el código está en una forma analizable y se le aplican las optimizaciones del compilador, en el sentido inverso al habitual: no para hacerlo rápido, sino para hacerlo legible.

• SCCP (capítulo «15»): propaga constantes y marca ramas inalcanzables. Es el que resuelve saltos indirectos sencillos y colapsa predicados opacos.
• GVN (capítulo «22»): unifica valores congruentes, colapsa código duplicado y ataca las expresiones MBA.
• Eliminación de código muerto (capítulo «6», sobre SSA): un recorrido de alcanzabilidad hacia atrás desde los efectos observables.
• Propagación de copias y simplificación algebraica: deshacer las copias de destrucción de SSA del compilador original y reconocer los idiomas que dejó el generador de código (capítulo «23»): xor r,r como cero, lea como aritmética, shr/imul como división por constante.
• Reconocimiento de variables de inducción (capítulo «23»): convierte aritmética de punteros en indexación de arrays.
• Deshacer la if-conversion (capítulo «23»): reintroducir condicionales donde el compilador los eliminó.

Todo esto se itera hasta punto fijo, porque cada transformación habilita a las otras.

24.10 Fase 10: estructuración

Reconstruir if, while, for y switch a partir del CFG, según el capítulo «4»: análisis estructural clásico, que colapsa esquemas conocidos y emite goto para lo que no encaja; o estructuración por condiciones de alcanzabilidad, que produce código sin goto a costa de condiciones más complejas.

Es aquí donde se paga la irreducibilidad: un grafo irreducible no admite expresión estructurada sin duplicar código, y el resultado es el while(1) con goto que todos hemos visto.

24.11 Fase 11: emisión

Traducir la IR estructurada a pseudo-C: fusionar las φ-webs en variables locales, dar nombres, emitir declaraciones con los tipos inferidos, y componer las expresiones deshaciendo la normalización del capítulo «3» —es decir, reconstruyendo árboles de expresión a partir de las operaciones elementales—.

Las asignaciones que aparecen aquí y no corresponden a ninguna instrucción del binario son las copias de destrucción de SSA del capítulo «13»: aparecen cuando una φ-web contiene variables que interfieren.

24.12 Dónde está cada capítulo

Y los capítulos «1», «2» y «21» no corresponden a ninguna fase: son los que dicen qué se puede esperar del conjunto.

24.13 Qué falla, y por qué

24.14 Los tres límites que no se van a mover

Conviene cerrar recordando lo que no depende de la herramienta.

El primero es el teorema de Rice, y el argumento de diagonalización del capítulo «2». No hay ni habrá un decompilador exacto, ni siquiera para programas que siempre terminan. Lo que mejora versión a versión es el margen de sobra, no su existencia.

El segundo es la elección del dominio abstracto, y el resultado de optimalidad del capítulo «21». Un análisis pierde precisión por tres causas distintas —el dominio, las funciones de transferencia, y la formulación por ecuaciones frente a la solución sobre caminos— y las tres tienen remedios distintos e incompatibles entre sí en coste. Al diseñar o al elegir una herramienta conviene saber cuál de las tres domina en el caso concreto.

Y el tercero es que la información destruida por el compilador no está. El capítulo «1» hacía el inventario: nombres, tipos, la asignación muerta que se eliminó, la estructura de control que se reescribió. Ninguna cantidad de análisis recupera lo que no está en el binario; lo que un decompilador produce es un programa equivalente, no el programa original. Confundir ambas cosas es el error conceptual más caro de la disciplina.

Con esas tres cosas claras, todo lo demás es ingeniería, y bastante buena.

24.15 Lecturas

Este capítulo recompone, en el orden del pipeline, las técnicas de los capítulos anteriores.

Para el pipeline en sí, las referencias son la tesis de Cristina Cifuentes, Reverse Compilation Techniques (1994), que sigue siendo la exposición fundacional; el trabajo de Balakrishnan y Reps sobre CodeSurfer/x86, que es la realización más completa de las fases 5 y 6; los artículos de Yakdan et al. sobre estructuración sin goto; y la documentación de arquitectura del decompilador de Ghidra, que es el pipeline completo mejor documentado que existe en código abierto. El apéndice «E» recoge las referencias completas.