Representaciones intermedias — de x86 a TIP, P-Code, VEX y LLVM IR

Ningún análisis serio trabaja sobre el código fuente, y mucho menos sobre el ensamblador. Todos trabajan sobre una representación intermedia (intermediate representation, IR) diseñada para que los algoritmos sean cortos. Este capítulo presenta los dos lenguajes de juguete que se usan de aquí en adelante y los pone en correspondencia con las IR reales que emplean los analizadores de binarios.

3.1 Qué hace buena a una representación intermedia

Un juego de instrucciones real es hostil al análisis por razones que no tienen nada que ver con la teoría. x86-64 tiene más de mil instrucciones; muchas modifican registros que no aparecen en la sintaxis; una sola instrucción puede leer memoria, hacer aritmética, escribir memoria y actualizar seis bits de estado. Escribir un análisis de variables vivas directamente sobre x86 significa escribir mil casos.

Una IR adecuada para el análisis cumple cinco propiedades:

1. Explicitud. Ningún efecto lateral oculto. Si la instrucción modifica el carry flag, la IR contiene una asignación explícita al carry flag.
2. Tamaño reducido. Entre 20 y 70 operaciones, no mil. Los análisis se escriben una vez por operación.
3. Expresiones sin efectos. Evaluar una expresión no cambia el estado. Todo cambio de estado es una asignación.
4. Control explícito. Nada de saltos implícitos, excepciones invisibles o instrucciones que a veces saltan.
5. Tamaños explícitos. Cada valor tiene una anchura conocida en bits. Lo que no está tipado, está dimensionado.

Los lenguajes de juguete que siguen cumplen las cinco por construcción, y por eso permiten presentar los algoritmos sin ruido. Las IR reales de la «sección 3.7 · Las IR de los analizadores de binarios reales» las cumplen a costa de una expansión considerable: una instrucción x86 se convierte típicamente en entre 3 y 15 operaciones de IR.

3.2 TIP, un lenguaje imperativo diminuto

TIP (Tiny Imperative Programming language) es el primero de los dos. Está diseñado para tener una sintaxis mínima y, aun así, contener todas las construcciones que hacen interesante y difícil el análisis estático. Los programas TIP interaccionan con el mundo leyendo enteros de un flujo de entrada y escribiendo enteros en un flujo de salida. Carece deliberadamente de variables globales, funciones anidadas, objetos y anotaciones de tipo.

Expresiones básicas. Todas denotan valores enteros:

Int -> 0 | 1 | -1 | 2 | -2 | ...
Id  -> x | y | z | ...
Exp -> Int
     | Id
     | Exp + Exp | Exp - Exp | Exp * Exp | Exp / Exp
     | Exp > Exp | Exp == Exp
     | ( Exp )
     | input

input lee un entero del flujo de entrada. Los operadores de comparación devuelven 0 para falso y 1 para verdadero.

Sentencias.

Stm -> Id = Exp ;
     | output Exp ;
     | Stm Stm
     | if ( Exp ) { Stm } [ else { Stm } ]
     | while ( Exp ) { Stm }

En las condiciones, 0 se interpreta como falso y cualquier otro valor como verdadero.

Funciones. Una declaración contiene nombre, parámetros, declaración de variables locales, cuerpo y expresión de retorno:

Fun -> Id ( Id , ... , Id ) { [ var Id , ... , Id ; ] Stm return Exp ; }
Exp -> ... | Id ( Exp , ... , Exp )

Funciones como valores. El nombre de una función puede usarse como variable que la referencia, y esos valores pueden asignarse, pasarse como argumento y devolverse. Se añade una forma generalizada de llamada, la llamada indirecta o computed call:

Exp -> ... | Exp ( Exp , ... , Exp )

Ahora lo que se llama es una expresión que evalúa a un valor función. Ese detalle, aparentemente menor, es el que hace difícil el análisis: sin saber a qué apunta la expresión no se puede construir el grafo de llamadas, y sin el grafo de llamadas no se puede analizar. Es el mismo círculo vicioso que plantea un call rax en un binario, y se rompe igual (capítulo «17»).

Un ejemplo con tres funciones:

twice(f, x) {
    return f(f(x));
}
inc(y) {
    return y + 1;
}
main(z) {
    return twice(inc, z);
}

Punteros. Para construir estructuras de datos y reservar memoria dinámicamente:

Exp -> ... | alloc Exp | & Id | * Exp | null
Stm -> ... | * Exp = Exp ;

alloc E reserva una celda nueva en el montón inicializada con el valor de E y devuelve un puntero a ella; & X crea un puntero a una variable del programa; * E desreferencia (una operación de load), y * E1 = E2 escribe a través de un puntero (un store). Punteros y enteros son valores distintos y no hay aritmética de punteros. Esta última restricción es la diferencia más importante entre TIP y un binario real, y se discute en la «sección 3.9 · Lecturas».

x = alloc null;
y = &x;
*x = 42;
z = **y;

Tras la segunda línea, y apunta a la variable x; la tercera escribe 42 en la celda reservada en la primera; la cuarta la lee mediante dos desreferencias.

Registros. Un record es una colección de campos con nombre:

Exp -> ... | { Id : Exp , ... , Id : Exp } | Exp . Id
Stm -> ... | Id . Id = Exp ; | ( * Exp ) . Id = Exp ;

Los registros se pasan por valor y sus campos no pueden ser a su vez registros, aunque sí punteros a registros. Son la aproximación de TIP a los struct de C, y el vehículo con el que el capítulo «19» tratará la recuperación de estructuras.

Programas. Un programa completo es una colección de funciones, Prog -> Fun ... Fun, y la ejecución empieza por la llamada main.

Usaremos las meta-variables I ∈ Int, X ∈ Id, E ∈ Exp, S ∈ Stm, F ∈ Fun, P ∈ Prog, a veces con subíndices.

Tres versiones del factorial en TIP, que reaparecerán más adelante. La iterativa:

iterate(n) {
    var f;
    f = 1;
    while (n > 0) {
        f = f * n;
        n = n - 1;
    }
    return f;
}

La recursiva:

recurse(n) {
    var f;
    if (n == 0) { f = 1; }
    else { f = n * recurse(n - 1); }
    return f;
}

Y una innecesariamente complicada, que usa punteros y una llamada indirecta para calcular lo mismo:

foo(p, x) {
    var f, q;
    if (*p == 0) { f = 1; }
    else {
        q = alloc 0;
        *q = (*p) - 1;
        f = (*p) * (x(q, x));
    }
    return f;
}
main() {
    var n;
    n = input;
    return foo(&n, foo);
}

Esta tercera versión es la interesante: para saber que termina hay que resolver simultáneamente el análisis de punteros y el de flujo de control, porque x es un parámetro que se llama y que se pasa a sí mismo. Es el equivalente en miniatura de un binario con tabla de punteros a función.

3.3 WHILE, el lenguaje etiquetado

El segundo lenguaje de juguete es WHILE. Su diferencia esencial con TIP es que asocia una etiqueta (label) a cada bloque elemental —cada asignación, cada test, cada skip— de forma que se pueda hablar de «el punto de programa ℓ» sin ambigüedad:

a ::= x | n | a1 op_a a2
b ::= true | false | not b | b1 op_b b2 | a1 op_r a2
S ::= [x := a]^{ℓ} | [skip]^{ℓ} | S1 ; S2
    | if [b]^{ℓ} then S1 else S2
    | while [b]^{ℓ} do S

donde op_a son operadores aritméticos, op_b booleanos y op_r relacionales, x ∈ Var, n ∈ Num y ℓ ∈ Lab. Se supone que las etiquetas son únicas dentro de un programa; a los bloques etiquetados se los llama bloques elementales (elementary blocks).

Usaremos WHILE cuando el foco esté en los puntos del programa —análisis de flujo de datos, ecuaciones entry/exit— y TIP cuando el foco esté en los valores y las estructuras de datos. La correspondencia es directa y ninguna de las dos elecciones tiene consecuencias teóricas.

3.4 Normalización

Una sintaxis rica es cómoda para escribir programas, pero incómoda para analizarlos. Por eso se normalizan: se transforman en programas equivalentes sintácticamente más simples. La normalización más útil consiste en aplanar las expresiones anidadas, de modo que las desreferencias sean siempre de la forma *Id en lugar de *Exp, y las llamadas siempre de la forma Id(Id,...,Id). También conviene aplanar las expresiones aritméticas, los argumentos, las condiciones de rama y las expresiones de retorno.

Por ejemplo,

x = f(y + 3) * 5;

se normaliza a

t1 = y + 3;
t2 = f(t1);
x = t2 * 5;

donde t1 y t2 son variables frescas, de modo que cada sentencia realice una sola operación. La forma resultante, en la que todas las expresiones salvo la parte derecha de una asignación son variables, se conoce como A-normal form.

3.5 Árboles sintácticos y grafos de flujo de control

Hay dos representaciones estructurales, y la elección entre ellas depende de si el análisis es sensible al orden de ejecución.

Los árboles sintácticos abstractos (abstract syntax trees, AST) son adecuados para análisis insensibles al flujo (flow-insensitive): análisis de tipos (capítulo «19»), de flujo de control (capítulo «17») y de punteros (capítulo «18»). Esos análisis ignoran el orden de las sentencias, lo que hace del AST una representación cómoda: basta recorrerlo extrayendo restricciones.

Los grafos de flujo de control (control flow graph, CFG) son necesarios para análisis sensibles al flujo, en particular el análisis de flujo de datos del capítulo «6». La idea se remonta a los primeros analizadores de los compiladores optimizadores, a finales de los sesenta.

Un CFG es un grafo dirigido cuyos nodos corresponden a sentencias y cuyas aristas representan el flujo de control posible. Por comodidad, y sin pérdida de generalidad, se supone que un CFG tiene siempre un único punto de entrada, entry, y un único punto de salida, exit; pueden pensarse como sentencias vacías. Si v es un nodo, pred(v) denota el conjunto de predecesores y succ(v) el de sucesores. En un programa completamente normalizado, cada nodo corresponde a una sola operación.

Para las sentencias simples el CFG se construye inductivamente: la asignación, la salida y el retorno dan un solo nodo. La composición S1 ; S2 conecta la salida de S1 con la entrada de S2. El condicional y el bucle:

    if (E) { S1 } else { S2 }          while (E) { S }

           +-----+                          +-----+
           |  E  |                     +--->|  E  |----+
           +--+--+                     |    +--+--+    |
          /       \                    |       |       |
     +---+-+     +-+---+               |    +--+--+    |
     | S1  |     | S2  |               |    |  S  |    |
     +---+-+     +-+---+               |    +--+--+    |
          \       /                    +-------+       |
           +-----+                                     v

El capítulo «4» se ocupa por completo del CFG: cómo se obtiene de un binario, y qué estructura tiene.

3.6 El problema previo: desensamblar

Todo lo anterior presupone que sabemos qué instrucciones hay. En un binario, eso ya es un resultado de análisis.

En arquitecturas de instrucción de longitud variable —x86 y x86-64, principalmente— el flujo de bytes no indica dónde empieza cada instrucción. Hay dos estrategias clásicas, ambas incorrectas:

Barrido lineal (linear sweep). Se decodifica desde el principio de la sección de código, instrucción tras instrucción, hasta el final. Es lo que hace objdump -d. Es completo —no se salta nada— pero se descarrila en cuanto encuentra datos embebidos entre instrucciones: decodifica la tabla de saltos como si fuera código y a partir de ahí queda desalineado, a veces durante decenas de instrucciones.

Descenso recursivo (recursive descent). Se empieza por los puntos de entrada conocidos y se sigue el flujo de control: tras un salto incondicional se continúa en el destino, tras un condicional en ambos, tras una llamada en el retorno. Es lo que hace IDA. No decodifica datos como código, pero es incompleto: el código alcanzable sólo mediante saltos indirectos no se descubre, y una función a la que sólo se llega por puntero a función queda invisible.

  bytes:  ... EB 02  FF C8  90 90 90  FF E0 ...
                |     |      |         |
   lineal:      jmp +2; dec eax; nop nop nop; jmp rax
                       ^^^^^^^ datos decodificados como codigo

   recursivo:   jmp +2 ----> nop nop nop; jmp rax
                             (dec eax nunca se decodifica: correcto)
                                          |
                                          +--> destino desconocido:
                                               el analisis se detiene

Ninguna de las dos es satisfactoria y las herramientas reales combinan ambas con heurísticas: firmas de prólogos de función, información de las secciones .eh_frame y de los símbolos si están, reconocimiento de patrones de tabla de saltos generados por cada compilador conocido, y análisis de valores para acotar los destinos indirectos. En la investigación reciente aparecen además el desensamblado por superconjunto (superset disassembly), que decodifica desde todos los desplazamientos posibles y deja que el análisis posterior descarte los imposibles, y el desensamblado probabilístico, que asigna verosimilitudes.

3.7 Las IR de los analizadores de binarios reales

Todas las herramientas serias levantan (lift) el ensamblador a una IR propia antes de analizar nada. Las principales:

Vale la pena mirar dos con detalle, porque representan las dos filosofías opuestas.

P-Code (Ghidra) opera sobre varnodes, tripletas (espacio de direcciones, desplazamiento, tamaño). Los espacios son ram, register, const y unique —este último para temporales del propio P-Code—. La instrucción x86 add eax, ebx se convierte aproximadamente en:

u0:4    = INT_ADD  EAX:4, EBX:4
CF:1    = INT_CARRY  EAX:4, EBX:4
OF:1    = INT_SCARRY EAX:4, EBX:4
SF:1    = INT_SLESS u0:4, 0:4
ZF:1    = INT_EQUAL u0:4, 0:4
EAX:4   = COPY u0:4

Seis operaciones para una instrucción, y todas las banderas explícitas. El decompilador de Ghidra convierte después este P-Code «crudo» a una forma refinada con MULTIEQUAL, que es literalmente la función φ de la forma SSA, e INDIRECT, que modela los efectos de las llamadas sobre valores que podrían estar aliasados. Si alguna vez se ha preguntado qué es un MULTIEQUAL en la ventana de P-Code de Ghidra, la respuesta está en el capítulo «12».

VEX (Valgrind, y por tanto angr) toma la decisión contraria con las banderas. Calcularlas todas en cada operación aritmética es carísimo y casi siempre inútil, porque el 95 % de las veces nadie las lee. VEX las calcula perezosamente: guarda en el estado del invitado los pseudo-registros cc_op, cc_dep1, cc_dep2 y cc_ndep, que describen qué operación produjo las banderas actuales y con qué operandos, y sólo cuando alguien lee una bandera se expande la fórmula correspondiente. Es mucho más rápido y notablemente más difícil de analizar: para saber si ZF está a uno hay que interpretar cc_op.

VEX organiza el código en IRSB (IR super blocks) y usa temporales t0, t1, … que son de asignación única dentro del bloque. Es decir, VEX es SSA local por construcción, aunque no globalmente.

------ IMark(0x401126, 3, 0) ------
t0 = GET:I32(eax)
t1 = GET:I32(ebx)
t2 = Add32(t0, t1)
PUT(cc_op)   = 0x00000003
PUT(cc_dep1) = t0
PUT(cc_dep2) = t1
PUT(eax)     = t2

3.8 Memoria: el problema que TIP esconde

TIP prohíbe la aritmética de punteros. Un binario la practica constantemente: toda variable local es [rbp - 0x18], todo campo de estructura es base + desplazamiento, todo elemento de array es base + índice * escala.

La consecuencia es que, mientras en TIP «variable» y «celda de memoria» son cosas distintas, en un binario todo es memoria hasta que se demuestre lo contrario. La IR levantada de un binario modela la memoria como un único array gigante indexado por direcciones de 64 bits, y sobre ese modelo:

• Dos escrituras a direcciones distintas no interfieren, pero demostrar que son distintas requiere análisis de valores.
• Una escritura a una dirección desconocida puede modificar cualquier cosa, lo que obliga a invalidar todo lo que se sabía.
• Las variables locales no existen: hay que descubrirlas particionando el marco de pila según los desplazamientos observados.

El proceso de recuperar variables a partir de accesos a memoria se llama variable recovery y es uno de los pasos más delicados de un decompilador. Se apoya en el análisis de valores del capítulo «8» y en el análisis de punteros del 18; las extensiones de SSA para memoria del capítulo «16» —en particular HSSA— son la maquinaria que permite tratar accesos a memoria potencialmente aliasados dentro del marco de SSA.

3.9 Lecturas

Para profundizar en las IR concretas: la documentación de P-Code forma parte del repositorio de Ghidra; VEX está descrito en libvex_ir.h de Valgrind y en la documentación de pyvex; el diseño de BIL está publicado por el equipo de BAP en CMU. Sobre desensamblado, el trabajo sobre superset disassembly de Bauman, Lin y Hamlen (2018) es el punto de entrada habitual.