Kontrollfluss dekompilieren: wie Glass.NET Schleifen und if/else aus einem Haufen Sprünge rekonstruiert

Hier ist etwas, das Leute beim ersten Mal überrascht: In einem kompilierten .NET-Assembly gibt es kein while. Kein for, kein foreach, kein else. Der C#-Compiler senkt sie alle auf dieselbe Handvoll Primitive ab — geradlinige Anweisungen und Sprünge — und wirft die Struktur weg. Die Aufgabe eines Decompilers ist, sie wieder einzusetzen, und er kann das nicht durch Lesen tun, weil sie nirgends geschrieben steht. Er muss sie allein aus der Form der Sprünge rekonstruieren.

Dieser Beitrag geht die Pipeline durch, die Glass.NET dafür ausführt: von einer flachen Liste von IL-Opcodes zu einem Kontrollflussgraphen, zu Dominatoren, zu Schleifen, zu if/else — und dann der ehrliche Teil, wo der Kontrollfluss so geformt ist, dass keine saubere Schleife existiert und das einzig Treue, das man drucken kann, ein Label und ein goto ist.

Das Kontrollfluss-Vokabular des IL ist winzig

Alles Strukturierte in C# läuft auf vier Arten von Anweisungen hinaus. Unbedingter Sprung: br target. Bedingte Sprünge: brtrue/brfalse (und die Vergleich-und-Springe-Formen beq, bgt, blt, …), die einen Wert vom Stack nehmen und springen oder durchfallen. Und die Sprungtabelle: switch (t1, t2, …), die eine Liste von Zielen indiziert. Das ist das ganze Repertoire. Eine for-Schleife nutzt es; ein while auch; eine mit goto durchsetzte Umschreibung von beiden auch. Betrachte eine einfache Summe:

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

Der Compiler gibt die klassische „Test unten”-Schleife aus — initialisieren, zur Bedingung springen, Körper, Inkrement, Bedingung, zurückspringen wenn wahr:

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

Nichts in diesem Strom sagt „for-Schleife”. Es gibt einen Rückwärtssprung (blt.s IL_0006) und einen Vorwärtssprung (br.s IL_0010). Ob das Ergebnis als for, while oder goto gedruckt wird, ist ganz eine Entscheidung, die der Decompiler aus der Sprungstruktur trifft. Triff sie richtig und du bekommst das for zurück; triff sie falsch und du bekommst funktionierenden, aber hässlichen goto-Brei.

Schritt 1: in Basisblöcke schneiden

Die erste Transformation verwandelt die flache Liste in Basisblöcke. Ein Basisblock ist eine maximale Folge von Anweisungen mit genau einem Weg hinein (oben) und einem hinaus (unten) — kein Sprung landet in der Mitte und keiner verlässt von der Mitte. Die Schnittregel ist mechanisch: Ein neuer Block beginnt an der Methodeneinfahrt, an jedem Sprungziel und unmittelbar nach jeder Sprunganweisung. Wende sie auf Sum an, und du erhältst vier Blöcke:

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

Nun ist die Methode eine Menge von Knoten mit Kanten dazwischen — ein Kontrollflussgraph. Jeder Sprung wird zu einer Kante; ein bedingter Sprung gibt einem Block zwei Nachfolger (genommen und durchgefallen); ein switch gibt ihm viele. Das ist die Datenstruktur, auf der jeder spätere Schritt arbeitet.

Schritt 2: Dominatoren entscheiden, wer wen beherrscht

Mit dem gebauten Graphen ist die zentrale Frage die Erreichbarkeit unter Wache: welche Blöcke nur erreicht werden können, indem man zuerst durch einen anderen Block geht. Diese Beziehung ist die Dominanz. Block X dominiert Block Y, wenn jeder Pfad von der Methodeneinfahrt zu Y durch X führt. Die Einfahrt dominiert alles; ein Schleifenkopf dominiert seinen ganzen Körper; die beiden Arme eines if werden jeweils von dem Block dominiert, der die Bedingung testet.

Glass berechnet den Dominatorbaum mit dem üblichen iterativen Datenflussalgorithmus (oder Lengauer–Tarjan bei großen Methoden) und gibt jedem Block seinen unmittelbaren Dominator — den nächstgelegenen Block, der vor ihm laufen muss. Dominatoren sind das, was die späteren Schritte zu Entscheidungen statt Raterei macht:

• Ein bedingter Sprung, dessen beide Nachfolger er dominiert, ist ein if (und möglicherweise ein else): Der Testblock beherrscht beide Arme, und der erste Block, den kein Arm dominiert, aber beide erreichen, ist dort, wo sich die Arme vereinen — die Anweisung nach dem if.
• Eine Rückwärtskante zu einem Block, der ihre Quelle dominiert, ist eine Schleife. Was uns zu der wichtigsten bringt.

Schritt 3: Rückwärtskanten sind Schleifen

Eine Rückwärtskante ist eine Kante von einem Block B zu einem Block H, wobei H B dominiert. Die Intuition ist exakt: Wenn jeder Pfad zu B durch H musste, dann bedeutet eine Kante von B zurück zu H, dass das Steuerwerk zu einem Punkt zurückkehrt, durch den es garantiert gekommen ist — das ist die Definition einer Schleife, und H ist ihr Kopf. In Sum dominiert hier B3 B1 und B2 (man kann den Körper nicht erreichen, ohne durch den Test zu gehen), und das Durchfallen B2 → B3 kehrt zum Dominator zurück. B3 ist der Kopf; {B1, B2, B3} ist die natürliche Schleife — der Kopf plus jeder Block, der das Ende der Rückwärtskante erreichen kann, ohne durch den Kopf zu gehen.

Sobald Glass Kopf und Schleifenkörper hat, ist das Strukturieren eine Frage der Darstellung:

• Ist der Test des Kopfes der einzige Ausgang der Schleife und sitzt oben am Körper, drucke ein while.
• Endet der Körper in einem erkennbaren Induktionsschritt (i++) über einer kurz vor der Schleife initialisierten und im Kopf getesteten Variablen, drucke ein for — deshalb kommt Sum als for zurück, nicht als while (true) mit einem if break.
• Ist der Test unten (der Kopf fällt unbedingt in den Körper und der Sprung ist am Ende), drucke ein do…while.

Keine davon ist „im” IL. Es ist der Decompiler, der die Form der natürlichen Schleife liest und das C# wählt, das denselben Graphen wieder ausgibt. Der Graph ist die Quelle der Wahrheit; das Schlüsselwort ist eine Darstellungsentscheidung.

Schritt 4: Vorwärtssprünge werden zu if / else

Alles, was keine Schleifenkante ist, ist ein Vorwärtssprung, und Vorwärtssprünge, die die Methode nicht verlassen, strukturieren sich in Bedingungen. Nimm einen Block, der in brfalse L mit einem Durchfallen endet: Das Durchfallen ist das then, der Block bei L ist dort, wo sich das then wieder vereint — oder, wenn das then selbst in einem unbedingten br über eine zweite Region endet, ist diese zweite Region das else. Der Vereinigungspunkt wird wieder mit Dominanz gefunden: Es ist der früheste vom Test dominierte Block, den beide Arme erreichen. Eine Kette solcher Tests mit einer gemeinsamen Vereinigung ist eine else if-Leiter; eine switch-Anweisung mit ihrer Sprungtabelle und einer gemeinsamen Vereinigung ist eine switch-Anweisung. Die Kurzschlüsse &&/|| fallen aus derselben Maschinerie — sie sind nur Bedingungen, deren Arme Ziele teilen — und so faltet Glass zwei brfalse in ein einziges if (a && b) statt in ein verschachteltes Paar.

Der ehrliche harte Fall: irreduzibler Kontrollfluss

Alles Obige nahm an, der Graph sei reduzibel — dass jeder Zyklus einen einzigen Eingang hat, einen einzigen Kopf, an den man ein while hängen kann. Der meiste vom Compiler erzeugte IL ist reduzibel, weil C#s strukturierte Anweisungen nur Schleifen mit einem Eingang erzeugen können. Aber nicht aller, und ein Decompiler, der etwas anderes vorgibt, erzeugt falschen Code.

Eine irreduzible Region ist ein Zyklus mit zwei oder mehr Eintrittspunkten — das Steuerwerk kann von mehr als einer Stelle mitten in die Schleife springen. Kein while oder for kann das ausdrücken, weil eine strukturierte Schleife genau einen Kopf hat. Man erhält irreduzible Graphen aus bestimmten goto-Mustern, aus einigen Compiler-Absenkungen und — nicht zufällig — aus Obfuskatoren, die den Kontrollfluss gezielt abflachen und verwirren, um das Strukturieren zu vereiteln.

Ein Decompiler hat genau drei ehrliche Antworten und keine vierte:

1. Knotenspaltung — einen der Eingangsblöcke duplizieren, sodass jeder Eingang seine eigene Kopie bekommt, was den Graphen auf Kosten wiederholten Codes reduzibel macht. Korrekt, aber es kann die Ausgabe aufblähen.
2. Kontrollierter Dispatch — eine synthetische Zustandsvariable und ein while (true) { switch (state) … } einführen, das die Sprünge simuliert. Das ist ironischerweise genau das, was die Kontrollfluss-Abflachungs-Obfuskierung erzeugt, also ist es treu, aber nicht schön, es wieder auszugeben.
3. Labels und goto — eine strukturierte Form für diese Region aufgeben und genau das drucken, was das IL tut: beschriftete Blöcke und goto dazwischen.

Glass.NETs Regel ist, alles zu strukturieren, was es rechtmäßig kann, und nur für die Regionen auf Labels und goto zurückzufallen, die wirklich keine strukturierte Form haben — nie ein sauberes while zu fabrizieren, wo der Graph es nicht stützt. Ein goto in Glass’ Ausgabe ist daher Information, kein Versagen: Es bedeutet, dass das Original wirklich Kontrollfluss hatte, den C#s strukturierte Anweisungen nicht ausdrücken können, was an sich wissenswert ist, wenn du auf absichtlich abgeflachten Code starrst.

Warum dies das Rückgrat des ganzen Decompilers ist

Jede „wie dekompiliert Glass X”-Geschichte — yield-Zustandsmaschinen, async/await, das Pattern-Matching-switch, das try/finally von using — steht am Ende auf dieser Schicht. Diese höheren Erkenner laufen nachdem die Methode in Blöcke geschnitten, als Graph gebaut, dominiert und strukturiert wurde, weil sie auf die Form des strukturierten Kontrollflusses passen, nicht auf rohe Opcodes. Mach die Kontrollfluss-Rekonstruktion richtig, und das switch (state) einer Zustandsmaschine ist ein sauberer Graph, den du in einen Iterator zurückfalten kannst; mach sie falsch, und jeder Erkenner darüber passt gegen Rauschen. Die Sprünge sind alles, was das IL dir gibt. Die Schleifen und die ifs sind etwas, das der Decompiler sich verdient.