Phase 13: Tools & Protocols

Leur mise en place est un processus de mise en œuvre de la stratégie de référencement.

Type: Build

Languages: Python, C

Prerequisites: Phase 13 · 32 (ELF from scratch), Phase 13 · 33 (disassembly and control flow)

Time: ~150 minutes

Objectifs d'apprentissage

• L'ascenseur décode les instructions x86-64 dans une petite IR avec des drapeaux explicites, des charges, des magasins, des succursales, des appels et des retours.
• Transformer les espaces de cadre en variables locales et les registres d'arguments du système V en paramètres.
• Construisez un SSA minimal avec des fonctions phi sur les frontières de domination, puis remplacez, simplifiez et supprimez le code mort.
• Récupérer if- Je suis là .ifavec else- Je suis là .while, et do whiledu graphique de contrôle des flux avec des post-dominateurs et des bords arrière.
• Expliquez le multiplication par 0x66666667comme une division par 10 et prouver l'identité.
• Lisez le pseudocode Ghidra pour les mêmes fonctions ligne par ligne et nommez l'instruction, ou la devinette, derrière chaque différence.

Le problème

Vous avez demandé à Rea le pseudocode de percent_changedans ledger-x86_64-O1.oGhidra 12.1.4 a répondu en dix secondes:

cCopyundefined1  [16] percent_change(int param_1,int param_2,ulong param_3)

{
  long lVar1;
  undefined1 auVar2 [16];
  undefined1 auVar3 [16];
  
  if (param_1 != 0) {
    lVar1 = (long)((param_2 - param_1) * 100);
    auVar3._0_8_ = lVar1 / (long)param_1 & 0xffffffff;
    auVar3._8_8_ = lVar1 % (long)param_1 & 0xffffffff;
    return auVar3;
  }
  auVar2._8_8_ = 0;
  auVar2._0_8_ = param_3;
  return auVar2 << 0x40;
}

La source est de quatre lignes.intvaleurs et rendements un int. Ghidra rapporte une valeur de retour de 16 octets et un troisième paramètre que la source ne dispose pas. Les seize octets de code machine sont corrects, et Ghidra a décodé chacun d'eux correctement. La signature est une devinette, et rien dans le texte ne le marque comme un.

réa renvoie ce texte comme le procedure_pseudo_codeLa limite est "Pseudocode est la sortie du décompilateur Ghidra, pas source originale et pas texte équivalent à la sortie Hopper".compare_functionsL'outil diffère du pseudocode en tant que lignes de texte. Son propre enregistrement de dimension dit "Assembly is opaque provider text" et que la normalisation de relocation est indisponible.

Le premier résultat de la décompilée étaitFUN_00406400(void)Je vous appelle .__ftol()L'interface de l'instruction affichait une entrée de pile et une expression x87.

Cette leçon construit la dérivation que le décompilateur cache. Vous commencez par les 56 instructions que la leçon 33 décode, les relevez à un IR, renommez en SSA, simplifiez et structurez. Ensuite, vous placez votre pseudocode à côté de celui de Ghidra pourpercent_change- Je suis là .grade, et totalLes tests compilent votre sortie avec le clang et le font contre la source sur une grille d'entrée.

La fixation et l'oracle

code/fixtures/ledger.cest le fichier partagé de cette partie du cours:

cCopyint percent_change(int before, int after) {
    if (before == 0) return 0;
    return (after - before) * 100 / before;
}

int grade(int score) {
    switch (score / 10) {
    case 10:
    case 9: return 4;
    case 8: return 3;
    case 7: return 2;
    case 6: return 1;
    default: return 0;
    }
}

int total(const int *values, int count) {
    int sum = 0;
    for (int i = 0; i < count; i++) sum += values[i];
    return sum;
}

grade_labelLes trois fonctions ci-dessus sont celles que cette leçon teste.

L' objet a été construit avec clang -target x86_64-unknown-linux-gnu -O1 -fno-asynchronous-unwind-tables -c ledger.c- Le .-O0l'objet est placé à côté pour la section de la fente de pile. code/fixtures/README.mdIl contient les deux commandes, le SHA-256 de chaque objet, et la commande réa qui a produit les fixations Ghidra.

L' oracle du décodeur est llvm-objdump -d -rLe texte pour les deux objets est engagé commeledger-x86_64-O1.objdump.txtet ledger-x86_64-O0.objdump.txtUn test analyse ces fichiers et compare chaque instruction par adresse, par octets et par texte AT&T. Cela couvre les 56 instructions à l'adresse -O1et chaque instruction à -O0- Quand ?llvm-objdumpest installé sur le chemin fixé, un deuxième test le fait vivre et compare à nouveau.

Je vous en prie .percent_changeComme l' oracle l' imprime:

textCopy0000000000000000 <percent_change>:
       0: 85 ff                        	testl	%edi, %edi
       2: 74 09                        	je	0xd <percent_change+0xd>
       4: 29 fe                        	subl	%edi, %esi
       6: 6b c6 64                     	imull	$0x64, %esi, %eax
       9: 99                           	cltd
       a: f7 ff                        	idivl	%edi
       c: c3                           	retq
       d: 31 c0                        	xorl	%eax, %eax
       f: c3                           	retq

Étape 1: Bytes à l'instruction

La leçon 33 a construit le décodeur. Cette leçon garde une petite copie de sorte que le code fonctionne par lui-même. La copie couvre exactement les opcodes qui ont été émis pourledger.cà-O0et -O1Pour tout ce qui soulevait .DecodeErroravec l'adresse et le octet opcode.

Le décodeur suit l'ordre des octets du SDM Intel, volume 2, section 2.1. Les préfixes viennent en premier, puis le code op, puis ModR/M, puis SIB, puis le déplacement, puis le immédiat.0x40à 0x4F, qui doit être directement devant le code op. REX.W sélectionne un opérand de 64 bits, REX.R étend le regdans le champ, REX.X élargit l'indice SIB et REX.B élargit r/mLa section 2.1.3 définit les trois champs ModR/M mod- Je suis là .reg, et r/m, et les trois champs de SIB scale- Je suis là .index, et baseEn mode 64 bits,mod = 00avec r/m = 101déplaceur de 32 bits par rapport à l'instruction suivante (section 2.2.1.6).

Le leaq (%rip), %rcxàgrade+0x23est de 7 octets avec un déplacement zéro.R_X86_64_PC32.rodata+0x10à l' équilibre 0x36Le soulèverain le résolve à l'étape 3.

Étape 2: Blocs et dominateurs

Un bloc de base est une séquence d'énoncés avec une entrée en haut et une sortie en bas.build_blocks()collecte les leaders: l'entrée de la fonction, chaque cible de saut à l'intérieur de la fonction, et chaque adresse après un saut ou un retour. Chaque bloc obtient des successeurs de sa dernière instruction.jmpIl y en a un.retIl n'en a pas, et un bloc qui se termine par une instruction ordinaire passe au prochain leader.

totalà-O1Il est composé de cinq blocs:

immediate_dominators()L'algorithme de l'interface est l'algorithme itératif de Cooper, Harvey et Kennedy (2001). Il passe les blocs dans un ordre post-revers et intersecte les dominateurs des prédécesseurs traités jusqu'à ce que rien ne change.totalIl est écrit que0x44dominent0x50Il dit aussi que0x50Il se domine à travers le bord arrière, c'est ainsi que la phase 8 trouve la boucle.

La même fonction fonctionne deux fois plus. dominance_frontiers()utilise pour l' ASS à l' étape 5. post_dominators()Il le fait sur le graphique inversé avec un nœud de sortie virtuel pour trouver des joints à l'étape 8.

Étape 3: Levé à une petite IR

L' IR dispose de six types de déclarations: Assign- Je suis là .Store- Je suis là .Branch- Je suis là .Jump- Je suis là .IndirectJump, et Return. Les expressions sont constantes, variables, opérations binaires avec une largeur, casts (sext- Je suis là .zext- Je suis là .truncIl existe cinq formes supplémentaires qui seront ensuite simplifiées:Flags- Je suis là .Cond- Je suis là .Concat- Je suis là .SignFill, et Symbolic- Je suis désolé .

Les registres sont des variables nommées par leur famille de 64 bits.%eaxest une Assignà raxavec une largeur de 32 et une lecture de %eaxest une lecture de raxEn mode 64 bits, une écriture 32 bits s'étend à zéro dans le registre complet, de sorte qu'une lecture ultérieure de 64 bits de la même valeur est une zextLe lecteur ne connaît pas la définition de la portée, il enregistre donc la largeur de lecture et permet à SSA d'insérer le moule à l'étape 5.

Les drapeaux sont une variable

Chaque instruction qui définit les codes de condition écrit une variable nommée flags, et chaque saut conditionnel le lit.cmp a, bécrit cmp(a, b), une test a, bécrit test(a, b), et subécrit la même chose cmpLa forme comme effet secondaire.jccdevient Branch(Cond(cc, flags), target, fallthrough)Le code de condition décide de l'opérateur de comparaison lorsque les deux se rencontrent à l'étape 6:

xorl %eax, %eaxest soulevé directement à eax = 0Les drapeaux qu' il dépose sont écrits comme:addLes drapeaux de style qui ne sautent pas dans le fichier.xorL' idiome est important dans grade, où Ghidra l'a perdu.

L'équipement de transport

cltdremplir%edxavec le signe de %eax- Je suis là .idivl %edidivise la paire de 64 bits %edx:%eaxpar %edi, met le quotient dans %eax, et le reste en %edxLe soulèvent écrit la paire dans un nom temporairedividendLa phrase restante est ensuite la vieille.%eaxDans le SSA, la moitié supérieure apparaît commesignfillLe simplificateur réduit la paire à la moitié inférieure, et la division devient une 32-bit /- Je suis désolé .

Les emplacements à -O0

À -O0Clang garde tous les locaux dans le cadre.percent_changemagasins %edià -0x8(%rbp)et %esià -0xc(%rbp)Le soulevant les surveille.pushq %rbpsuivie de movq %rsp, %rbpAprès ce prologue, une mémoire avec base.%rbp, sans indice, et un déplacement devient une variable nommée local_<hex>- Je suis là .-0x8(%rbp)est local_8- Je suis là .-0xc(%rbp)est local_c- Je suis désolé .

Les instructions de cadre elles-mêmes ne produisent pas d'IR, et ne le font pas non plus subqet addqsur%rspTout autre opéra de mémoire reste unLoadou Store- Je suis désolé .

Relocations

Le leaq (%rip), %rcxdans gradeLe déplacement à l'offset0x36dit R_X86_64_PC32.rodata+0x10Le lien écriraS + A - PDans le champ.Sest l'adresse de .rodata- Je suis là .Aest l' additif 0x10, et PL'instruction compute ensuitenext_ip + disp = (P + 4) + S + A - P = S + A + 4- Je suis désolé .

Le lecteur de calcul utilise la même arithmétique sans lien.0x10 + 4 = 0x14- L' IR ditrcx = &.rodata+0x14, et la table là-bas tient les cinqintvaleurs 1, 2, 3, 4, 4- Je suis désolé .

Étape 4: Parametres de la convention d'appel

Le système V AMD64 psABI, section 3.2.3, passe les arguments de classe INTEGER en %rdi- Je suis là .%rsi- Je suis là .%rdx- Je suis là .%rcx- Je suis là .%r8- Je suis là .%r9Le résultat est renvoyé en%raxet puis ...%rdxLa section 3.2.1 précise que %rbp- Je suis là .%rbx, et %r12à travers %r15Tout le reste appartient à l'appelant.

collect_params()Il est vrai qu'une règle est appliquée: un registre d'arguments qui est lu avant toute écriture dans la fonction est un paramètre.%rsiet jamais%rdiIl a encore deux paramètres.percent_changeIl lit%ediet %esi, donc il a .param_1et param_2- Je suis là .gradeIl ne lit que %edi- Je suis là .totalIl lit%rdicomme base de 64 bits et %esicomme un compte de 32 bits.

Maintenant, c'est Ghidra qui est là.param_3Il y a une explication.idivlécrit %rdx, et le psABI permet un retour à 128 bits INTEGER en %rax:%rdxDans un fichier objet il n'y a pas d'appelant pour dire combien large est la valeur de retour.

Sur le chemin de zéro,xorl %eax, %eaxIl écrit seulement .%eaxGhidra a lu .%rdxIl y a une entrée de la fonction, et cette entrée est devenue param_3La signature est une devinette sur les parties que les instructions laissent ouvertes.

Étape 5: SSA, Un nom par définition

Après avoir levé,gradeécrit raxquatre fois et rcx- Je l'ai fait trois fois. Cytron, Ferrante, Rosen, Wegman et Zadeck (1991) définissent la forme de l'affectation statique unique. Chaque variable est attribuée exactement une fois, et les fonctions phi aux points de jonction sélectionnent parmi les définitions qui les atteignent. Leur construction a deux étapes. La section 5.1 place les fonctions phi à l'aide de frontières de domination, et la section 5.2 renommée chaque définition et utilisation avec une marche sur l'arbre dominateur.insert_phis()et rename()Suivez ces deux sections.

L' inscription de l' ASS totalmontre ce que produit la construction:

textCopyblock 0x44 -> 0x50
  ecx_1 = esi_0
  edx_1 = 0
  eax_1 = 0
block 0x50 -> 0x50, 0x5b
  eax_2 = phi(0x44: eax_1, 0x50: eax_3)
  rdx_2 = phi(0x44: edx_1, 0x50: rdx_3)
  flags_2 = phi(0x44: flags_1, 0x50: flags_5)
  flags_3 = add(eax_2, load32(rdi_0 + rdx_2 * 4))
  eax_3 = eax_2 + load32(rdi_0 + rdx_2 * 4)
  flags_4 = inc(rdx_2, 1)
  rdx_3 = rdx_2 + 1
  flags_5 = cmp(zext64(ecx_1), rdx_3)
  if jne(flags_5) goto 0x50 else goto 0x5b

La version 0 d'un registre est sa valeur à l'entrée. esi_0et rdi_0Les paramètres sont les paramètres.0x50Il a deux prédécesseurs, le bloc de configuration et lui-même, donc chaque variable avec une définition dans la boucle obtient un phi là.flags_2Le SSA le place dans le cas où il serait mort.flagsIl a des définitions dans les deux prédécesseurs, et la phase 6 le supprime parce que rien ne le lit.

La modification de nomme répare également les largeurs. edx_1 = 0est une définition de 32 bits et rdx_3 = rdx_2 + 1est de 64 bits, donc le phi rdx_2La lecture de la lettre est plus large.%rcxdans cmpq %rdx, %rcxest de 64 bits alors que sa définition ecx_1 = esi_0est de 32 bits, donc l'utilisation devient zext64(ecx_1)Chaque personnage du pseudocode final vient de cette règle.

La partie "light" est la sortie de l'ASS. coalesce_webs()Le système de calcul de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la valeur de la

Étape 6: Simplifier, remplacer, supprimer le code mort

optimize()Le simplificateur réécrit les expressions vers le bas avec ces règles:

La substitution avant déplace une définition dans son seul usage. La règle a trois conditions. L'utilisation est dans le même bloc. L'utilisation est une déclaration et non un phi. Lorsque la définition contient une charge, aucun magasin ou appel ne se trouve entre la définition et l'utilisation. Une constante ou une adresse de section est substituée n'importe où sauf dans un phi, car un argument phi doit rester une variable pour le web.

Le code mort supprime une assignation ou un phi dont la destination n'est pas utilisée et dont l'expression n'a pas d'appel.percent_changele reste edx_2 = dividend_1 % edi_0Il est mort, donc il va en premier.edx_1 = signfill(eax_1)Il est donc remplacé par dividend_1 = edx_1:eax_1- Je suis désolé .

La règle de la paire réduit alorssignfill(eax_1):eax_1à eax_1, et la division devient eax_1 / edi_0- Maintenant .eax_1 = esi_1 * 100a une seule utilisation et esi_1 = esi_0 - edi_0Les deux sont utilisés dans la déclaration de retour.flagsLes définitions ont été remplacées par les conditions de branche et disparaissent.

cCopyreturn (param_2 - param_1) * 100 / param_1;

Le 0x66666667 est multiplié par

gradeDivise le score par 10 et le clang émet non idivIl émet .imulq $0x66666667, %rax, %raxAlors ...sarq $0x22, %rcxDans une copie, alors shrq $0x3f, %raxLe compilateur choisit un multiplicateur.met un quart .sPour chaquexdans la gamme, (x * m) >> sdoit être égale x / d- Je suis désolé .

Je vous en prie .m = 0x66666667 = 1717986919et s = 34Les calculs sont corrects:2^34 / 10 = 1717986918.4, et le plafond est 1717986919L' erreur estm * 10 - 2^34 = 6Pour que l' identité soit conservée sur tous les 32 bits .x, les temps d' erreur 2^31Il doit rester en dessous.2^34, donc l'erreur doit être au maximum 8.(x * m) >> 34égale floor(x / 10)pour chaque non négatif int- Je suis désolé .

Pour négatif xLe plancher tourne à l'écart de zéro tandis que le C tourne vers zéro. shrq $0x3fextrait le bit de signalisation du produit, qui est 1 exactement quand xL'ajout corrige l'arrondissement.

magic_divisor(m, s)Il teste une paire de candidats.dcomme le quotient entier de 2^spar met essaiedet d + 1Il accepte undseulement lorsque mest égal au plafond de 2^s / det l'erreur de la liaison est maintenue.s = 33donned = 5, ce qui est exact, parce que 0x66666667est aussi le plafond de 2^33 / 5- Un test vérifie l' identité contrec_div(x, 10)Les valeurs de l'indice de valeur sont les valeurs de l'indice de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de valeur de .intLa portée.

Avec reconnaissance,gradeIl litecx_1 = param_1 / 10 - 6;Avec la reconnaissance désactivée, la démo imprime la forme brute:

cCopyrax_1 = (long)param_1 * 0x66666667;
ecx_1 = (int)(rax_1 >> 34) + (int)((unsigned long)rax_1 >> 63) - 6;

Les deux compiler et les deux calculer les mêmes valeurs. Gardez le commutateur. Lorsque vous lisez le code d'un compilateur que vous n'avez pas étudié, la forme brute est la plus honnête.

Étape 7: Les types d'utilisation

Le code machine a des largeurs et aucun type. infer_types()Il est possible de faire des tests de la taille de la toile, en utilisant les données de la toile.int, et un web 64 bits est longUn web qui est la base d' un accès à un élémentbase[idx]avec des éléments de 4 octets est int *Le type pointer se répand sur les copies et les phis, donc local_8 = param_1à-O0fait les deux int *. Le type de retour est la largeur de la valeur dans le returnLes déclarations.

Le résultat pour totalest int total(int *param_1, int param_2)Ghidra a écrit:int total(long param_1,uint param_2)Le soulevant a utilisé la charge à l'échelle comme indice.*(int *)(param_1 + uVar2 * 4)- Je ne vois pas non plus .const, et aucun ne peut le dire .int *de unsigned *- Je suis désolé .

Lee, Avgerinos et Brumley (TIE, NDSS 2011) récupèrent le type de cadre en tant que résolution de contraintes sur un réseau. Le résultat est une limite supérieure et une limite inférieure au lieu d'une hypothèse. Noonan, Loginov et Cok (Retypd, PLDI 2016) ajoutent polymorphisme et récursion.constCette leçon utilise les deux règles les moins chères de cette ligne de travail et nomme ce qu'ils ne peuvent pas voir.

L'arithmétique non signée est conservée dans les expressions et non dans les types de variables. jaaprès cmpl $0x4, %ecxdes empreintes comme (unsigned int)ecx_1 > 4, et shrqdes empreintes comme (unsigned long)rax_1 >> 63. Les variables restent signées de sorte que le lecteur voit la valeur du registre et le seul endroit où l'instruction la traite comme non signée.

Étape 8: Structuration à partir du graphique

Cifuentes (1994), chapitre 6, correspond aux régions du graphique par rapport aux formes d'un langage de haut niveau. Les boucles sont les premières (6.6.1), puis les conditionnels bidirectionnels (6.6.2), puis les conditionnels n-directionnels (6.6.3). Yakdan, Eschweiler, Gerhards-Padilla et Smith (NDSS 2015) prennent l'autre route. Ils dérivent la condition dans laquelle chaque nœud exécute et construisent la structure à partir de ces conditions, sans formes fixes. Leur motivation est une mesure. Hex-Rays sur un échantillon produit 1,571 gotoLes déclarations de 49 514 lignes, une pour 32 lignes, et leur structuration n'ont produit aucune des 1 530 fonctions de base.

structure()Il faut deux faits à partir de l'étape 2.BranchLa boucle naturelle est l'ensemble de blocs qui atteignent la source de la borne arrière sans passer l'en-tête.

Pour uneBranchavec joint j- Le numéro de la liste:

• Si vousjest la cible de saut, émettez if (!cond) { fallthrough region }et continuer à j- Je suis désolé .
• Si vousjest la chute, émetif (cond) { target region }et continuer à j- Je suis désolé .
• Si vousjest la sortie de fonction, les deux bras reviennent.if (cond) {... }et l'autre bras après lui, sans un elseC' est le retour précoce .percent_changeet total- Je suis désolé .
• Sinon émettezif (cond) { target } else { fallthrough }et continuer à j- C' est ça .percent_changeà-O0, où les deux armes se stockent local_4et nous nous retrouverons à l'épilogue.

Pour un en-tête de boucle:

• Si l' en-tête se termine par un Branchavec un successeur en dehors de la boucle, émettez while (cond) { body }- Je suis là .totalà-O0a cette forme: l'en-tête compare local_14avec local_cet les feuilles en .jge- Je suis désolé .
• Si l'en-tête est également le bloc avec le bord arrière, ou le verrou sort à la place, émettez do { body } while (cond);- Je suis là .totalà-O1a cette forme: bloc 0x50ajoute, augmente, compare et saute à elle-même.

Un IndirectJumpfinit un bloc sans successeur. gradeà-O0est une vraie table de saut,jmpq *%raxà travers cinq compensations relatives à .rodata+0x0La leçon 33 résout ces cibles.0x76- Je suis là .0x7f- Je suis là .0x88, et 0x91Les résultats de la recherche ont été obtenus en raison de la présence de la présence de la même substance dans les cellules.switch- Je suis désolé .

Que fait -O1 au commutateur ?

À -O1Clang n' a pas gardé une table de saut pour grade- Il a calculé .score / 10 - 6Il a ensuite chargé la valeur de retour d'un tableau de 5 entrées de intà.rodata+0x14La comparaison non signée est une instruction qui couvre les deux.score / 10 < 6et score / 10 > 10Une différence négative est une valeur non signée importante, elle échoue donc au même contrôle.

La table tient .1, 2, 3, 4, 4Pour les quotients 6 à 10, le switchavec cinq returnLes déclarations sont devenues ifLe soulevageur émet exactement ça, et nomme la table.lookup_14après son décalage de section.

La longueur de la table est une heuristique. table_values()Les lectures de la table commencent à la suivante .rodatacompenser que tout .textLes références de relocation ou à la fin de la section.0x28, la table de grade_labelJe suis un homme .lookup_14Il a(0x28 - 0x14) / 4 = 5Les entrées. la comparaison non signée contre 4 est d'accord. Ghidra ne sait pas la longueur non plus.*(uint *)(&DAT_001000b4 + (ulong)uVar2 * 4), une adresse en octets plus un décalage, et laissez les cinq valeurs pour le lecteur de regarder vers le haut.

Avec Ghidra

La démo imprime chaque paire.code/fixtures/ghidra/*.jsonLes preuves montrent que Rea est revenu le 10-14 du 2026 .npx -y rea-agents@6.5.0 decompile ledger-x86_64-O1.o <function> --provider ghidra --format jsonChaque disque porteconfidence: observedet authority: shipped-artifactLes revendications contenues dans le texte sont dérivées, et les dossiers ne disent pas lesquelles.

pourcentage_changement

textCopylifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
int percent_change(int param_1, int param_2)   | undefined1  [16] percent_change(int param_1,int param_2,ulong param_3)
{                                              | {
  if (param_1 == 0) {                          |   long lVar1;
    return 0;                                  |   undefined1 auVar2 [16];
  }                                            |   undefined1 auVar3 [16];
  return (param_2 - param_1) * 100 / param_1;  |   if (param_1 != 0) {
}                                              |     lVar1 = (long)((param_2 - param_1) * 100);
                                               |     auVar3._0_8_ = lVar1 / (long)param_1 & 0xffffffff;
                                               |     auVar3._8_8_ = lVar1 % (long)param_1 & 0xffffffff;
                                               |     return auVar3;
                                               |   }
                                               |   auVar2._8_8_ = 0;
                                               |   auVar2._0_8_ = param_3;
                                               |   return auVar2 << 0x40;
                                               | }

La version réparée en code/fixtures/ghidra/ledger-x86_64-O1.ghidra-repaired.cLa fonction de l'indicateur est la même que celle de la source de l'indicateur.

de qualité

textCopylifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
static const int lookup_14[5] = {1, 2, 3, 4, 4}; | uint grade(int param_1)
int grade(int param_1)                         | {
{                                              |   uint uVar1;
  int eax_1;                                   |   uint uVar2;
  int ecx_1;                                   |   
                                               |   uVar2 = param_1 / 10 - 6;
  ecx_1 = param_1 / 10 - 6;                    |   uVar1 = -(param_1 >> 0x1f) ^ (uint)((ulong)((long)param_1 * 0x66666667) >> 0x3f);
  eax_1 = 0;                                   |   if (uVar2 < 5) {
  if ((unsigned int)ecx_1 <= 4) {              |     uVar1 = *(uint *)(&DAT_001000b4 + (ulong)uVar2 * 4);
    eax_1 = lookup_14[(unsigned long)(unsigned int)ecx_1]; |   }
  }                                            |   return uVar1;
  return eax_1;                                | }
}                                              |

le total

textCopylifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
int total(int *param_1, int param_2)           | int total(long param_1,uint param_2)
{                                              | {
  int eax_1;                                   |   int iVar1;
  int ecx_1;                                   |   ulong uVar2;
  long rdx_1;                                  |   
                                               |   if (0 < (int)param_2) {
  if (param_2 <= 0) {                          |     uVar2 = 0;
    return 0;                                  |     iVar1 = 0;
  }                                            |     do {
  ecx_1 = param_2;                             |       iVar1 = iVar1 + *(int *)(param_1 + uVar2 * 4);
  rdx_1 = 0;                                   |       uVar2 = uVar2 + 1;
  eax_1 = 0;                                   |     } while (param_2 != uVar2);
  do {                                         |     return iVar1;
    eax_1 = eax_1 + param_1[rdx_1];            |   }
    rdx_1 = rdx_1 + 1;                         |   return 0;
  } while ((unsigned long)(unsigned int)ecx_1 != rdx_1); | }
  return eax_1;                                |
}                                              |

Le test de comportement compile le texte de Ghidra pour gradeet totalIl y a deux autres.typedefLes lignes et la définition de DAT_001000b4à partir des vingt octets à .rodata+0x14Les deux fonctions correspondent à la source sur la grille.

Ce que la recherche dit sur la lecture du pseudo-code

LLM4Decompile (EMNLP 2024) a mesuré Ghidra seul à 20,12% de réexécutabilité sur HumanEval-Decompile. Environ une fonction sur cinq a recompilé et passé les affirmations qui accompagnent la référence. En raffinant la production de Ghidra avec leur modèle 6.7B, il est passé à 52,74%. DecompileBench (Findings of ACL 2025) a utilisé six décompilateurs industriels et six approches LLM sur 23 400 fonctions provenant de 130 programmes. Les résultats du LLM sont meilleurs et ont une précision de fonctionnalité inférieure de 52,2%.

Liu, Raff et Micinski (arXiv 2609.05370, septembre 2026) expliquent le fossé. Ils ont utilisé 300 fonctions de bibliothèque GitHub et 287 fonctions basées sur CVE. Le modèle de raffinement le plus fort a augmenté le taux de construction de Ghidra de 75 à 90%, tandis que le taux de correspondance comportementale est tombé de 74 à 62%. Les candidats qui ont passé tous les tests dans la référence ont toujours divergé sur les entrées fuzzed. Cela s'est produit dans 4,9% des cas dans huit systèmes, et jusqu'à 13% pour un système. Jusqu'à un dixième des vulnérabilités révélées ont disparu du code raffiné.

Les champs, les types, les calles et les gardes inventés ont remplacé les inconnus visibles que le décompilateur avait laissés dans le texte.

C' est la raison pour laquelle le lifting imprime .(unsigned long)(unsigned int)ecx_1Il imprime une note au lieu d'une lettre.switchpour le saut non résolu, et lookup_14Au lieu d'une étiquette, un modèle invente.code/main.py- Je suis Ghidra.undefined1 [16]C'est la plus belle des modèles.int percent_change(int, int)Le même modèle produira une signature pure et erronée sur la fonction suivante.

Faites-le

Exécutez la démo:

bashCopycd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/main.py

La démo décode les quatre fonctions de la-O1l' objet et compare chaque instruction avec l' engagement llvm-objdumpPour percent_change- Je suis là .grade, et totalIl imprime l'IR avant le SSA, la liste du SSA avec des fonctions phi, et le pseudocode à côté du texte Ghidra.gradeavec la reconnaissance de division désactivée, le -O0versions de percent_change- Je suis là .total, et grade_label, et un résumé:

jsonCopy{
  "functions": ["grade", "grade_label", "percent_change", "total"],
  "instructions": 56,
  "blocks": {"percent_change": 3, "grade": 3, "total": 5, "grade_label": 4},
  "phis": {"percent_change": 0, "grade": 1, "total": 2, "grade_label": 1},
  "objdumpDifferences": 0
}

Lire code/main.pydans cet ordre:

1. read_object()Lire les en-têtes de section, le tableau des symboles et le .relales sections d'un objet ELF64 relocalisable.
2. decode_one()et render_att()Décodez une instruction et imprimez-la comme ça .llvm-objdump- Il le fait.
3. build_blocks()- Je suis là .immediate_dominators(), et dominance_frontiers()construire les faits graphiques.
4. lift_insn()transforme une instruction en déclarations IR et résout les délocalisations.
5. insert_phis()et rename()construire SSA et insérer des lancers de largeur.
6. make_simplifier()- Je suis là .substitute_once(), et remove_dead_code()courir à l' intérieur optimize()- Je suis désolé .
7. collect_params()- Je suis là .coalesce_webs(), et infer_types()nommer et taper les réseaux.
8. structure()avec post_dominators()et natural_loops()émet le corps C.
9. lift_function()connecte les étapes et lift_all()Levez un objet entier avec des signatures de callee.

Utilisez-le

Pour lever une fonction de votre propre objet, construisez-la avec clang -target x86_64-unknown-linux-gnu -cet appelerlift_all(read_object(path))Quand le décodeur monteDecodeError, lire le octet opcode du message et le trouver dans la carte SDM opcode. Puis ajouter une entrée aux tables en haut du fichier. Lorsque le souverain soulève sur un mnemonique, ajouter une règle à lift_insn()- lorsque le constructeur émet ungoto, imprimez le graphique avec IrPrinterChaque addition est petite et chaque addition est vérifiée contrellvm-objdumpou de la claque par les tests existants.

Lorsque Ghidra est installé, exécutez ré sur la même fonction et placez les deux textes côte à côte. Remplissez la table de différence avant de croire l'un ou l'autre texte. Une différence avec une instruction derrière elle est un choix de présentation. Une différence sans instruction derrière elle est une devinette, et la devinette peut être des deux côtés.

Laboratoire interactif

Laboratoire A: une fonction à travers cinq étapes

De la coderépertoire, ouverture Python:

bashCopycd phases/13-tools-and-protocols/34-lifting-to-pseudocode/code
python3 -q

Je vais courir .

pythonCopyfrom main import *
obj = read_object(FIXTURES / "ledger-x86_64-O1.o")
lifted = lift_function(obj, "percent_change")
for insn in lifted.decoded: print(f"0x{insn.address:x}: {insn.raw.hex(' ')}  {insn.att()}")
print(lifted.ir_text)
print(lifted.ssa_text)
print(lifted.pseudocode)

Suivez%eside subl %edi, %esià esi_1 = esi_0 - edi_0à (param_2 - param_1)- Le byte .feest le ModR/M de la subl, avec mod = 11- Je suis là .reg = edi, et r/m = esi- Je suis désolé .

Laboratoire B: le langage de division

pythonCopyprint(lift_function(obj, "grade", recognize_division=False).pseudocode)
print(magic_divisor(0x66666667, 34), magic_divisor(0x66666667, 33), magic_divisor(0x66666667, 31))

La première ligne imprime le multiplicateur brut et les déplacements.10 5 None. Découvrez pourquoi le même multiplicateur se divise par 5 avec un décalage en moins, et pourquoi le décalage 31 ne respecte pas la limite d'erreur.

Laboratoire C: un nouvel objet arrête le décodeur

Construisez le dispositif à -O2et le soulevez:

bashCopyclang -target x86_64-unknown-linux-gnu -O2 -fno-asynchronous-unwind-tables -c fixtures/ledger.c -o "$TMPDIR/ledger-O2.o"
python3 -c 'from main import *; from pathlib import Path; import os; lift_all(read_object(Path(os.environ["TMPDIR"]) / "ledger-O2.o"))'

Le décodeur s' arrête à 0x56avec opcode 81 is outside the fixture subset- Opcode .81est le formulaire de groupe 1 avec un instant de 32 bits.andl $0x7ffffff8, %edx, et clang l' a utilisé dans la boucle vectoriée de total- Ajoutez-le à côté .0x83dans decode_one()Le sous-ensemble augmente une entrée à la fois, et chaque entrée est vérifiée contre llvm-objdump- Je suis désolé .

Laboratoire D: valeur par défaut de Ghidra en classe

pythonCopyprint(ghidra_pseudocode("grade"))
for score in (-25, 0, 59, 60, 100, 115):
    sign = -(score >> 31)
    product_sign = ((score * 0x66666667) & ((1 << 64) - 1)) >> 63
    print(score, sign ^ product_sign)

Chaque rangée imprime 0, Ghidra's uVar1l'expression est correcte et illisible, et l'instruction xorl %eax, %eaxIl le dit en deux octets.

Laboratoire de pratique

Ajouter switchrétablissement pour gradeà-O0- Je suis désolé .

Les exigences:

• Lisez les cinq délocalisations en .rela.rodatade ledger-x86_64-O0.o, chacun R_X86_64_PC32.text+offset, et calculer les cinq cibles de l' affaire à partir du tableau à .rodata+0x0- Je suis désolé .
• Ajouter un Switchterminateur à l'IR avec l'expression index, la liste cible et le défaut de l'indice jaavant le chargement de la table.
• Donnez au bloc de commutateur un successeur par cible pour que les dominateurs, les post-dominateurs et les SSA continuent à travailler.
• Émettezswitch (local_10) { case 0:... }avec un seul casepar cible et l'épilogue partagé après la fusion.
• Gardez le billet pour tout saut indirect dont vous ne pouvez pas attacher la table.
• Compiler le résultat avec le clang et le comparer avec la source sur la grille de scores dans les tests.

Le succès signifiegradeà-O0et gradeà-O1produire la même sortie sur le réseau, avec un switchet nongoto- Je suis désolé .

Artéfacts

Cette leçon produit outputs/skill-lifting-to-pseudocode.md. Utilisez-le pour lever une fonction avec une dérivation pour chaque ligne et pour remplir la table de différence contre le texte d'un décompilateur.

Vérifiez

Exécutez la démo et la suite déterministe:

bashCopycd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/main.py
python3 -m unittest discover -s code/tests -v

La suite comporte 25 tests.

• le décodeur est d'accord avec le compromis llvm-objdumptexte sur chaque instruction des deux objets, et avec un live llvm-objdumplorsqu'il est installé
• REX, ModR/M, SIB et le décalage de champ de déplacement de leaq (%rip), %rcxsont décodés comme le décrit le MDD
• un opcode en dehors du sous-ensemble soulève DecodeErrorau lieu de deviner
• Le lecteur ELF énumère les quatre fonctions et les trois .textdélocalisations
• totalIl y a cinq blocs.0x44dominent0x50, et 0x50est un en-tête de boucle avec lui-même comme le corps
• %rdiet %rsidevenir param_1et param_2, et param_1dans totalest int *
• testet cmpavec je- Je suis là .jle- Je suis là .ja, et jgedevenir ==- Je suis là .<=, non signé >, et <
• SSA place deux fonctions Phi en direct à l' en-tête de boucle de totalet aucun dans percent_change
• le pseudocode de percent_change- Je suis là .grade, et totalest égal au texte attendu
• gradeIl litparam_1 / 10 - 6avec reconnaissance sur et le brut multiplier avec reconnaissance hors
• 0x66666667avec le changement 34 divisé par 10, avec le changement 33 divisé par 5, et l'identité est maintenue sur la grille
• les emplacements de pile à -O0devenir local_4- Je suis là .local_8- Je suis là .local_c, et le pointeur de cadre n' apparaît jamais
• la table à .rodata+0x14Il lit1, 2, 3, 4, 4par le transfert
• le saut indirect dans gradeà-O0est déclaré avec ses quatre blocs non relevés
• Les appareils Ghidra contiennent le retour de 16 bytes, le param_3, le non-simplifié xor, et le long param_1
• Les six unités émises sont compilées avec clang -std=c11 -Wall -Werrorpour x86_64-unknown-linux-gnu
• les fonctions soulevées, le texte Ghidra réparé et la source impriment les mêmes 232 lignes sur la grille d'entrée

Mode de défaillance de la production

Règlement d'exploitation

Traitez le pseudocode comme une dérivation que vous n'avez pas vue. Reproduisez-le à partir des instructions avec un élévateur que vous pouvez lire. Placez les deux textes côte à côte, et écrivez l'instruction ou la devinette derrière chaque ligne qui diffère. Compilez les deux et courez les deux contre la source lorsque vous en avez. Une ligne sans instruction derrière elle reste une devinette peu importe la propreté de sa lecture.

Pour en savoir plus

• Intel SDM Volume 2, chapter 2, Instruction Format
• System V AMD64 psABI, section 3.2, Function Calling Sequence
• Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, TOPLAS 1991
• Cooper, Harvey, Kennedy, A Simple, Fast Dominance Algorithm, 2001
• Cifuentes, Reverse Compilation Techniques, PhD thesis, QUT 1994
• Yakdan et al., No More Gotos, NDSS 2015
• Granlund, Montgomery, Division by Invariant Integers using Multiplication, PLDI 1994
• Lee, Avgerinos, Brumley, TIE, NDSS 2011
• Noonan, Loginov, Cok, Polymorphic Type Inference for Machine Code, PLDI 2016
• LLM4Decompile, EMNLP 2024
• DecompileBench, Findings of ACL 2025
• Liu, Raff, Micinski, When LLM Decompilers Recompile More and Preserve Less, 2026
• rea 6.5.0 Ghidra provider notes
• réa 6.5.0 source à la balise 3b79af2que cette leçon décrit: src/domain/functionComparisonDimensions.ts- Je suis là .website/evidence/dx-ball-sound-pan.md- Je suis désolé .

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.