Decompilar el flujo de control: cómo Glass.NET reconstruye bucles y if/else a partir de un montón de saltos

Aquí va algo que sorprende a la gente la primera vez que lo ve: no hay while en un ensamblado .NET compilado. Ni for, ni foreach, ni else. El compilador de C# los baja todos al mismo puñado de primitivas —instrucciones en línea recta y saltos— y tira la estructura. El trabajo de un decompilador es volver a ponerla, y no puede hacerlo leyéndola, porque no está escrita en ninguna parte. Tiene que reconstruirla solo a partir de la forma de los saltos.

Esta entrada recorre la tubería que ejecuta Glass.NET para lograrlo: de una lista plana de opcodes de IL a un grafo de flujo de control, a dominadores, a bucles, a if/else, y luego la parte honesta, donde el flujo de control está formado de tal modo que no existe un bucle limpio y lo único fiel que imprimir es una etiqueta y un goto.

El vocabulario de flujo de control del IL es diminuto

Todo lo estructurado en C# se reduce a cuatro tipos de instrucción. Salto incondicional: br target. Saltos condicionales: brtrue/brfalse (y las formas comparar-y-saltar beq, bgt, blt, …) que sacan un valor y saltan o caen por debajo. Y la tabla de salto: switch (t1, t2, …) que indexa una lista de destinos. Ese es todo el repertorio. Un bucle for lo usa; también un while; también una reescritura plagada de goto de cualquiera de los dos. Considera una suma sencilla:

int Sum(int[] xs)
{
    int total = 0;
    for (int i = 0; i < xs.Length; i++)
        total += xs[i];
    return total;
}

El compilador emite el clásico bucle «prueba al final» —inicializar, saltar a la condición, cuerpo, incremento, condición, saltar hacia atrás si es verdadero:

IL_0000: ldc.i4.0        // total = 0
IL_0001: stloc.0
IL_0002: ldc.i4.0        // i = 0
IL_0003: stloc.1
IL_0004: br.s   IL_0010   // jump to the condition test
IL_0006: ldloc.0          // -- body: total += xs[i]
IL_0007: ldarg.0
IL_0008: ldloc.1
IL_0009: ldelem.i4
IL_000a: add
IL_000b: stloc.0
IL_000c: ldloc.1          // -- i++
IL_000d: ldc.i4.1
IL_000e: add
IL_000f: stloc.1
IL_0010: ldloc.1          // -- condition: i < xs.Length
IL_0011: ldarg.0
IL_0012: ldlen
IL_0013: conv.i4
IL_0014: blt.s  IL_0006   // if i < len, branch back to body
IL_0016: ldloc.0
IL_0017: ret

Nada en ese flujo dice «bucle for». Hay un salto hacia atrás (blt.s IL_0006) y uno hacia delante (br.s IL_0010). Si el resultado se imprime como un for, un while o un goto es enteramente una decisión que toma el decompilador a partir de la estructura de saltos. Aciértalo y recuperas el for; falla y obtienes una sopa de goto que funciona pero es fea.

Paso 1: cortar en bloques básicos

La primera transformación convierte la lista plana en bloques básicos. Un bloque básico es una tirada maximal de instrucciones con exactamente una manera de entrar (arriba) y una de salir (abajo): ningún salto aterriza en medio y ninguno sale desde el medio. La regla para cortar es mecánica: un nuevo bloque empieza en la entrada del método, en cada destino de salto e inmediatamente después de cada instrucción de salto. Aplícala a Sum y obtienes cuatro bloques:

B0  IL_0000..IL_0004   total=0; i=0; br IL_0010          (-> B3)
B1  IL_0006..IL_000b   total += xs[i]                    (-> B2, fallthrough)
B2  IL_000c..IL_000f   i++                               (-> B3, fallthrough)
B3  IL_0010..IL_0014   test i < len; blt IL_0006         (-> B1 or B4)
B4  IL_0016..IL_0017   return total

Ahora el método es un conjunto de nodos con aristas entre ellos —un grafo de flujo de control. Cada salto se vuelve una arista; un salto condicional da a un bloque dos sucesores (tomado y caída); un switch le da muchos. Esta es la estructura de datos sobre la que opera cada paso posterior.

Paso 2: los dominadores deciden quién gobierna a quién

Con el grafo construido, la pregunta central es la alcanzabilidad bajo guarda: qué bloques solo pueden alcanzarse pasando primero por algún otro bloque. Esa relación es el dominio. El bloque X domina al bloque Y si todo camino desde la entrada del método a Y pasa por X. La entrada domina todo; una cabecera de bucle domina todo su cuerpo; los dos brazos de un if están cada uno dominados por el bloque que prueba la condición.

Glass calcula el árbol de dominadores con el algoritmo iterativo estándar de flujo de datos (o Lengauer–Tarjan en métodos grandes), dando a cada bloque su dominador inmediato —el bloque más cercano que debe ejecutarse antes que él. Los dominadores son lo que permite que los pasos posteriores sean decisiones en lugar de conjeturas:

• Un salto condicional cuyos dos sucesores domina es un if (y posiblemente un else): el bloque de prueba gobierna ambos brazos, y el primer bloque que ningún brazo domina pero ambos alcanzan es donde los brazos se juntan —la sentencia tras el if.
• Una arista hacia atrás a un bloque que domina su origen es un bucle. Lo cual nos lleva al que más importa.

Paso 3: las aristas hacia atrás son bucles

Una arista hacia atrás es una arista de un bloque B a un bloque H donde H domina a B. La intuición es exacta: si todo camino a B tenía que pasar por H, entonces una arista de B de vuelta a H significa que el control regresa a un punto por el que estaba garantizado que había pasado —esa es la definición de un bucle, y H es su cabecera. En Sum, aquí B3 domina a B1 y B2 (no puedes alcanzar el cuerpo sin pasar por la prueba), y la caída B2 → B3 regresa al dominador. B3 es la cabecera; {B1, B2, B3} es el bucle natural —la cabecera más todo bloque que pueda alcanzar la cola de la arista hacia atrás sin pasar por la cabecera.

Una vez que Glass tiene la cabecera y el cuerpo del bucle, estructurar es una elección de presentación:

• Si la prueba de la cabecera es la única salida del bucle y está en lo alto del cuerpo, imprime un while.
• Si el cuerpo termina en un paso de inducción reconocible (i++) sobre una variable inicializada justo antes del bucle y probada en la cabecera, imprime un for —por eso Sum vuelve como un for, no como un while (true) con un if break.
• Si la prueba está abajo (la cabecera cae al cuerpo incondicionalmente y el salto está al final), imprime un do…while.

Ninguna de estas está «en» el IL. Son el decompilador leyendo la forma del bucle natural y eligiendo el C# que vuelve a emitir el mismo grafo. El grafo es la fuente de la verdad; la palabra clave es una decisión de representación.

Paso 4: los saltos hacia delante se vuelven if / else

Todo lo que no es una arista de bucle es un salto hacia delante, y los saltos hacia delante que no salen del método se estructuran en condicionales. Toma un bloque que termina en brfalse L con una caída: la caída es el then, el bloque en L es donde el then se vuelve a unir —o, si el propio then termina en un br incondicional por encima de una segunda región, esa segunda región es el else. El punto de unión se halla con el dominio de nuevo: es el bloque más temprano dominado por la prueba que ambos brazos alcanzan. Una cadena de tales pruebas con una unión compartida es una escalera else if; una instrucción switch con su tabla de salto y una unión común es una sentencia switch. Los cortocircuitos &&/|| caen de la misma maquinaria —no son más que condicionales cuyos brazos comparten destinos— que es como Glass pliega dos brfalse en un solo if (a && b) en vez de un par anidado.

El caso difícil honesto: flujo de control irreducible

Todo lo anterior supuso que el grafo es reducible —que todo ciclo tiene una única entrada, una única cabecera de la que colgar un while. La mayor parte del IL generado por el compilador es reducible, porque las sentencias estructuradas de C# solo pueden producir bucles de entrada única. Pero no todo lo es, y un decompilador que finja lo contrario produce código incorrecto.

Una región irreducible es un ciclo con dos o más puntos de entrada —el control puede saltar al medio del bucle desde más de un sitio. Ningún while ni for puede expresar eso, porque un bucle estructurado tiene exactamente una cabecera. Obtienes grafos irreducibles de ciertos patrones de goto, de unas pocas bajadas del compilador y —no por accidente— de ofuscadores que aplanan y enredan el flujo de control específicamente para derrotar la estructuración.

Un decompilador tiene exactamente tres respuestas honestas, y ninguna cuarta:

1. División de nodos —duplicar uno de los bloques de entrada para que cada entrada tenga su propia copia, haciendo el grafo reducible a costa de código repetido. Correcto, pero puede disparar el tamaño de la salida.
2. Despacho controlado —introducir una variable de estado sintética y un while (true) { switch (state) … } que simule los saltos. Esto es, irónicamente, exactamente lo que produce la ofuscación por aplanamiento de flujo de control, así que reemitirlo es fiel pero no bonito.
3. Etiquetas y goto —renunciar a una forma estructurada para esa región e imprimir exactamente lo que hace el IL: bloques etiquetados y goto entre ellos.

La regla de Glass.NET es estructurar todo lo que legítimamente puede y recurrir a etiquetas y goto solo en las regiones que de verdad no tienen forma estructurada —nunca fabricar un while limpio donde el grafo no lo soporta. Un goto en la salida de Glass es por tanto información, no un fallo: significa que el original realmente tenía flujo de control que las sentencias estructuradas de C# no pueden expresar, lo cual en sí vale la pena saber cuando miras código que fue aplanado a propósito.

Por qué esto es la columna vertebral de todo el decompilador

Cada historia de «cómo decompila Glass X» —máquinas de estado de yield, async/await, el switch de coincidencia de patrones, el try/finally de using— acaba apoyándose en esta capa. Esos reconocedores de alto nivel corren después de que el método se haya cortado en bloques, grafado, dominado y estructurado, porque coinciden sobre la forma del flujo de control estructurado, no sobre opcodes crudos. Haz bien la reconstrucción del flujo de control y el switch (state) de una máquina de estado es un grafo limpio que puedes plegar de vuelta en un iterador; hazla mal y cada reconocedor por encima está coincidiendo contra ruido. Los saltos son todo lo que el IL te da. Los bucles y los if son algo que el decompilador se gana.