Décompiler le flot de contrôle : comment Glass.NET reconstruit boucles et if/else à partir d'un tas de sauts

Voici une chose qui surprend la première fois qu’on la voit : il n’y a pas de while dans un assembly .NET compilé. Pas de for, pas de foreach, pas de else. Le compilateur C# les abaisse tous vers la même poignée de primitives — instructions en ligne droite et sauts — et jette la structure. Le travail d’un décompilateur est de la remettre, et il ne peut pas le faire en la lisant, car elle n’est écrite nulle part. Il doit la reconstruire à partir de la seule forme des sauts.

Cet article parcourt le pipeline qu’exécute Glass.NET pour y parvenir : d’une liste plate d’opcodes IL à un graphe de flot de contrôle, aux dominateurs, aux boucles, aux if/else — puis la partie honnête, où le flot de contrôle est formé de telle sorte qu’aucune boucle propre n’existe et où la seule chose fidèle à imprimer est une étiquette et un goto.

Le vocabulaire de flot de contrôle de l’IL est minuscule

Tout ce qui est structuré en C# se ramène à quatre sortes d’instructions. Saut inconditionnel : br target. Sauts conditionnels : brtrue/brfalse (et les formes comparer-et-sauter beq, bgt, blt, …) qui dépilent une valeur et sautent ou tombent en dessous. Et la table de saut : switch (t1, t2, …) qui indexe une liste de cibles. Voilà tout le répertoire. Une boucle for l’utilise ; un while aussi ; une réécriture truffée de goto de l’un ou l’autre aussi. Considérez une simple somme :

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

Le compilateur émet la boucle classique « test en bas » — initialiser, sauter vers la condition, corps, incrément, condition, sauter en arrière si vrai :

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

Rien dans ce flux ne dit « boucle for ». Il y a un saut arrière (blt.s IL_0006) et un saut avant (br.s IL_0010). Que le résultat s’imprime en for, en while ou en goto est entièrement une décision que prend le décompilateur à partir de la structure des sauts. Réussissez-la et vous récupérez le for ; ratez-la et vous obtenez une soupe de goto qui fonctionne mais qui est laide.

Étape 1 : découper en blocs de base

La première transformation change la liste plate en blocs de base. Un bloc de base est une suite maximale d’instructions avec exactement une façon d’entrer (le haut) et une de sortir (le bas) : aucun saut n’atterrit au milieu et aucun n’en part. La règle de découpe est mécanique : un nouveau bloc commence à l’entrée de la méthode, à chaque cible de saut et immédiatement après chaque instruction de saut. Appliquez-la à Sum et vous obtenez quatre blocs :

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

La méthode est maintenant un ensemble de nœuds reliés par des arêtes — un graphe de flot de contrôle. Chaque saut devient une arête ; un saut conditionnel donne à un bloc deux successeurs (pris et chute) ; un switch lui en donne plusieurs. C’est la structure de données sur laquelle opère chaque étape suivante.

Étape 2 : les dominateurs décident qui gouverne qui

Le graphe construit, la question centrale est l’accessibilité sous garde : quels blocs ne peuvent être atteints qu’en passant d’abord par un autre bloc. Cette relation est la domination. Le bloc X domine le bloc Y si tout chemin de l’entrée de la méthode vers Y passe par X. L’entrée domine tout ; un en-tête de boucle domine tout son corps ; les deux bras d’un if sont chacun dominés par le bloc qui teste la condition.

Glass calcule l’arbre des dominateurs avec l’algorithme itératif standard de flot de données (ou Lengauer–Tarjan sur les grandes méthodes), donnant à chaque bloc son dominateur immédiat — le bloc le plus proche qui doit s’exécuter avant lui. Les dominateurs sont ce qui permet aux étapes suivantes d’être des décisions plutôt que des conjectures :

• Un saut conditionnel dont il domine les deux successeurs est un if (et peut-être un else) : le bloc de test gouverne les deux bras, et le premier bloc qu’aucun bras ne domine mais que les deux atteignent est l’endroit où les bras se rejoignent — l’instruction après le if.
• Une arête arrière vers un bloc qui domine sa source est une boucle. Ce qui nous amène à celle qui compte le plus.

Étape 3 : les arêtes arrière sont des boucles

Une arête arrière est une arête d’un bloc B vers un bloc H où H domine B. L’intuition est exacte : si tout chemin vers B devait passer par H, alors une arête de B vers H signifie que le contrôle revient à un point par lequel il était garanti d’être passé — c’est la définition d’une boucle, et H en est l’en-tête. Dans Sum, ici B3 domine B1 et B2 (on ne peut atteindre le corps sans passer par le test), et la chute B2 → B3 revient au dominateur. B3 est l’en-tête ; {B1, B2, B3} est la boucle naturelle — l’en-tête plus tout bloc pouvant atteindre la queue de l’arête arrière sans passer par l’en-tête.

Une fois que Glass a l’en-tête et le corps de la boucle, structurer est un choix de présentation :

• Si le test de l’en-tête est la seule sortie de la boucle et se trouve en haut du corps, imprimer un while.
• Si le corps se termine par un pas d’induction reconnaissable (i++) sur une variable initialisée juste avant la boucle et testée dans l’en-tête, imprimer un for — c’est pourquoi Sum revient en for, pas en while (true) avec un if break.
• Si le test est en bas (l’en-tête tombe dans le corps inconditionnellement et le saut est à la fin), imprimer un do…while.

Aucune de ces formes n’est « dans » l’IL. Ce sont le décompilateur lisant la forme de la boucle naturelle et choisissant le C# qui réémet le même graphe. Le graphe est la source de vérité ; le mot-clé est une décision de rendu.

Étape 4 : les sauts avant deviennent if / else

Tout ce qui n’est pas une arête de boucle est un saut avant, et les sauts avant qui ne sortent pas de la méthode se structurent en conditionnelles. Prenez un bloc qui se termine par brfalse L avec une chute : la chute est le then, le bloc en L est l’endroit où le then se rejoint — ou, si le then lui-même se termine par un br inconditionnel par-dessus une seconde région, cette seconde région est le else. Le point de jonction se trouve à nouveau par la domination : c’est le bloc le plus précoce dominé par le test que les deux bras atteignent. Une chaîne de tels tests avec une jonction partagée est une échelle else if ; une instruction switch avec sa table de saut et une jonction commune est une instruction switch. Les courts-circuits &&/|| découlent de la même mécanique — ce ne sont que des conditionnelles dont les bras partagent des cibles — ce qui est la façon dont Glass plie deux brfalse en un seul if (a && b) au lieu d’une paire imbriquée.

Le cas difficile et honnête : le flot de contrôle irréductible

Tout ce qui précède supposait le graphe réductible — que tout cycle ait une entrée unique, un en-tête unique auquel accrocher un while. La majeure partie de l’IL généré par le compilateur est réductible, car les instructions structurées de C# ne peuvent produire que des boucles à entrée unique. Mais pas tout, et un décompilateur qui prétend le contraire produit du code faux.

Une région irréductible est un cycle à deux points d’entrée ou plus — le contrôle peut sauter au milieu de la boucle depuis plusieurs endroits. Aucun while ni for ne peut l’exprimer, car une boucle structurée a exactement un en-tête. On obtient des graphes irréductibles de certains motifs de goto, de quelques abaissements du compilateur et — non par hasard — d’obfuscateurs qui aplatissent et emmêlent le flot de contrôle précisément pour vaincre la structuration.

Un décompilateur a exactement trois réponses honnêtes, et aucune quatrième :

1. Dédoublement de nœud — dupliquer l’un des blocs d’entrée pour que chaque entrée ait sa propre copie, rendant le graphe réductible au prix de code répété. Correct, mais cela peut faire exploser la sortie.
2. Répartition contrôlée — introduire une variable d’état synthétique et un while (true) { switch (state) … } qui simule les sauts. C’est, ironiquement, exactement ce que produit l’obfuscation par aplatissement de flot de contrôle, donc le réémettre est fidèle mais pas joli.
3. Étiquettes et goto — renoncer à une forme structurée pour cette région et imprimer exactement ce que fait l’IL : des blocs étiquetés et des goto entre eux.

La règle de Glass.NET est de structurer tout ce qu’il peut légitimement et de ne se rabattre sur des étiquettes et des goto que pour les régions qui n’ont vraiment aucune forme structurée — jamais de fabriquer un while propre là où le graphe ne le supporte pas. Un goto dans la sortie de Glass est donc une information, pas un échec : il signifie que l’original avait vraiment un flot de contrôle que les instructions structurées de C# ne peuvent exprimer, ce qui en soi vaut la peine d’être su quand vous fixez du code aplati à dessein.

Pourquoi ceci est l’épine dorsale de tout le décompilateur

Chaque histoire de « comment Glass décompile X » — machines à états de yield, async/await, le switch de filtrage par motifs, le try/finally de using — finit par reposer sur cette couche. Ces reconnaisseurs de haut niveau s’exécutent après que la méthode a été découpée en blocs, mise en graphe, dominée et structurée, car ils filtrent sur la forme du flot de contrôle structuré, pas sur des opcodes bruts. Réussissez la reconstruction du flot de contrôle et le switch (state) d’une machine à états est un graphe propre que vous pouvez replier en un itérateur ; ratez-la et chaque reconnaisseur au-dessus filtre contre du bruit. Les sauts sont tout ce que l’IL vous donne. Les boucles et les if sont quelque chose que le décompilateur mérite.