Désassemblage linéaire vs récursif

Jusqu’ici, vous avez traité le code d’un échantillon comme une boîte noire : vous avez lu ses en-têtes, ses imports et ses chaînes, et vous avez mesuré son entropie. À partir de ce module, vous ouvrez la boîte. Le premier outil que vous prenez en main est un désassembleur, qui retransforme les octets de code machine en instructions telles que mov, call et ret.

On est tenté de voir le désassemblage comme une simple table de correspondance : l’octet C3 est ret, point. Traduire une instruction est effectivement mécanique. La difficulté est de décider quels octets traduire, et où commence chaque instruction. Si vous vous trompez là-dessus, le listing que vous passez des heures à lire est une fiction. Cette leçon présente les deux stratégies classiques, les points où chacune casse, et pourquoi la réponse compte autant quand l’auteur du binaire cherche activement à vous tromper.

Ce qu’un désassembleur doit décider

Une section de code n’est qu’une suite d’octets. Rien n’y indique « une instruction commence ici » ou « ces huit octets sont un pointeur, pas du code ». Un désassembleur statique doit en déduire deux choses :

1. Où se trouve le code. Quelles plages d’octets contiennent des instructions, et lesquelles contiennent des données (tables de sauts, constantes, chaînes, bourrage d’alignement) qui se trouvent simplement dans une section exécutable ?
2. Où commence chaque instruction. Sur x86 et x86-64, une instruction fait entre 1 et 15 octets. Sa longueur dépend des préfixes, de l’opcode, des octets ModRM et SIB, et de la taille de l’éventuel déplacement et de la valeur immédiate (voir l’encodage des instructions x86). On ne connaît la longueur d’une instruction qu’en la décodant : un seul point de départ erroné décale donc toutes les instructions qui suivent.

Les architectures à largeur fixe comme AArch64 rendent la seconde question presque gratuite (chaque instruction fait 4 octets, alignés), ce qui explique que les données mêlées au code y posent un problème bien moindre. Le x86 est dense : presque toutes les valeurs d’octet sont un opcode ou un préfixe valide, si bien qu’un désassembleur qui part du mauvais endroit tombe rarement sur une erreur évidente. Il affiche simplement un charabia d’apparence plausible.

Voici les sept premiers octets d’une fonction jouet, décodés de deux façons :

bytes:   eb 01 e8 8d 47 01 c3

follow the jmp (what the CPU does)       decode the next byte (linear sweep)
  +0  eb 01      jmp  +3                   +0  eb 01            jmp  +3
  +3  8d 47 01   lea  eax,[rdi+1]          +2  e8 8d 47 01 c3   call rel32 0xc301478d
  +6  c3         ret

Les deux colonnes sont du x86 valide. Seul le flot de contrôle vous dit laquelle le CPU exécute réellement. Cet exemple n’a rien d’hypothétique : c’est la première fonction que vous construirez dans le lab.

Balayage linéaire

La stratégie la plus simple décode une section de code du début à la fin : décoder l’instruction au premier octet, avancer de sa longueur, recommencer jusqu’au bout. objdump -d fonctionne ainsi, tout comme ndisasm et la boucle « désassemble ce tampon » que la plupart des gens écrivent en premier.

  .text  ┌────┬──────┬────┬───────────┬────┬─────┐
         │ i1 │  i2  │ i3 │    i4     │ i5 │ ... │   decode, advance, decode...
         └────┴──────┴────┴───────────┴────┴─────┘
          ───────────────────────────────────────►

Point fort : la couverture. Le balayage linéaire examine chaque octet ; il ne rate donc jamais une fonction simplement parce que rien ne l’appelle de façon visible. Le code atteint uniquement via un pointeur de fonction, un callback enregistré auprès de l’OS ou une table de méthodes virtuelles apparaît quand même dans le listing.

Point faible : il ignore tout des données. Chaque fois que des octets qui ne sont pas du code se trouvent dans une section exécutable, le balayage linéaire les décode quand même :

• Tables de sauts. Une instruction switch compilée en saut indirect utilise souvent une table d’adresses ou de décalages. GCC et Clang placent ces tables dans une section de données en lecture seule, mais MSVC en a historiquement placé certaines dans .text, juste après la fonction.
• Constantes en ligne et literal pools. L’assembleur écrit à la main, certaines bibliothèques d’exécution et beaucoup de shellcode gardent leurs données à côté du code qui les utilise.
• Bourrage. Les compilateurs alignent le début des fonctions avec des séquences de nop ou des octets int3 (0xCC). Ceux-ci se décodent sans dommage, mais d’autres octets de remplissage non.
• Octets parasites délibérés. Des octets insérés par un obfuscateur précisément *parce qu’*ils font dérailler un balayage linéaire.

Décoder des données comme du code cause deux types de dégâts. Les données elles-mêmes deviennent des instructions absurdes, ce qui est gênant mais généralement reconnaissable. Pire, la dernière « instruction » absurde peut déborder de la fin des données et avaler les premiers octets du vrai code. Le désassembleur est alors désynchronisé : il décode du vrai code à partir du mauvais décalage.

Le x86 se resynchronise — tôt ou tard

La bonne nouvelle, c’est que le décodage x86 a tendance à se recaler tout seul. Un décodage mal aligné produit quelques instructions bidon, et tôt ou tard l’une d’elles se termine pile sur une vraie frontière d’instruction ; à partir de là, les deux flux concordent. Dans le lab, vous mesurerez ce phénomène sur un vrai binaire : la plupart des points de départ mal alignés se recalent après une ou deux instructions bidon, et rares sont ceux qui en demandent plus de cinq.

La mauvaise nouvelle, c’est ce qui se perd entre-temps. Ces quelques instructions sont justement celles que les données ont avalées, et l’une d’elles peut être le call ou le saut conditionnel qui compte. Une cible de branchement qui tombe au milieu d’une instruction de votre listing est le symptôme classique : le code dit « va à l’adresse X », mais le désassembleur n’affiche aucune instruction commençant en X.

Astuce : Les symboles masquent la désynchronisation. objdump reprend le décodage à chaque symbole qu’il connaît : un binaire non strippé se resynchronise donc gratuitement au début de chaque fonction. Strippez le binaire, et le même octet parasite peut corrompre la fin d’une fonction et le début de la suivante.

Descente récursive

La seconde stratégie décode en suivant le flot de contrôle, comme le ferait le CPU. Elle part d’adresses dont on sait qu’elles contiennent du code et traite chaque branchement comme un pointeur vers d’autre code :

• Graines : le point d’entrée indiqué par l’en-tête du fichier, les fonctions exportées, les symboles si le binaire en a (voir ELF pour les analystes de malwares et Imports, exports et IAT).
• Décoder les instructions les unes après les autres à partir d’une graine.
• Sur un jmp, mettre la cible en file d’attente et arrêter ce parcours ; les octets qui suivent un saut inconditionnel ne sont pas atteints depuis ce point.
• Sur un saut conditionnel, mettre la cible en file d’attente et continuer, car les deux issues sont possibles.
• Sur un call, mettre la fonction appelée en file d’attente et (en général) continuer, en supposant qu’elle retourne.
• Sur ret ou hlt, arrêter ce parcours.
• Recommencer jusqu’à ce que la file de travail soit vide.

  entry ──► push rbx
            ...
            call add_one ─────────────► add_one: jmp L1 ──┐
            ...                                   (junk)  │ never decoded
            ret                              L1:  lea ◄───┘
                                                  ret

Comme elle ne décode jamais d’octets qu’aucun chemin n’atteint, la descente récursive enjambe les données en ligne et les octets parasites placés après un saut inconditionnel. C’est pourquoi tous les désassembleurs interactifs sérieux reposent sur elle.

Point faible : elle ne voit que ce qu’elle peut suivre.

• Branchements indirects. jmp rax, call [rip+X] et call [r12+rbx*8] ont des cibles qui n’existent qu’à l’exécution. Les tables de switch, les appels virtuels, les callbacks et tous les appels via la table des imports entrent dans cette catégorie.
• Code non atteint. Une fonction dont la seule référence est un pointeur stocké dans les données (routine de démarrage d’un thread, procédure de fenêtre, entrée d’une table de gestionnaires) n’a aucun call entrant ; elle ne sert donc jamais de graine.
• Fonctions qui ne retournent pas. Après call exit ou call abort, le compilateur peut placer quelque chose sans rapport : la fonction suivante, du bourrage ou une table de sauts. Un désassembleur qui suppose que tout appel retourne le décode comme du code en séquence ; un désassembleur qui sait que la fonction appelée ne retourne jamais s’arrête correctement. Se tromper sur cette liste, dans un sens comme dans l’autre, produit des erreurs.
• Les deux branches d’un saut sont supposées vivantes. Si un saut conditionnel ne peut en réalité aller que d’un côté, l’« autre » branche mène à des octets que le CPU n’exécute jamais, et le désassembleur les décode quand même.

C’est ce dernier point que les obfuscateurs exploitent le plus, comme vous le verrez plus bas.

Ce que font les vrais outils : descente récursive plus heuristiques

IDA, Ghidra et Binary Ninja partent tous de la descente récursive, puis comblent les trous qu’elle laisse à l’aide d’heuristiques :

Le point sur .pdata mérite d’être souligné pour les analystes Windows. L’ABI Windows x64 exige des informations de déroulement (unwind) pour que les exceptions puissent parcourir la pile ; un PE 64 bits normal embarque donc une liste exacte des bornes de ses fonctions. Les désassembleurs s’en servent pour amorcer l’analyse, et vous pouvez la lire vous-même ; la leçon suivante le fait précisément. Vous avez croisé .pdata comme « une section parmi d’autres » dans Sections PE. C’est l’une des plus utiles.

Ces heuristiques expliquent aussi pourquoi deux outils peuvent être en désaccord sur un même binaire. Quand IDA affiche une fonction que Ghidra ne voit pas, ou inversement, l’un des deux a appliqué une heuristique que l’autre a ignorée. Connaître les algorithmes sous-jacents vous dit auquel faire confiance pour une région donnée.

Attention : Des heuristiques agressives échangent des faux négatifs contre des faux positifs. L’« Aggressive Instruction Finder » de Ghidra et les options similaires trouvent davantage de code dans les binaires strippés, mais transforment aussi des données en fonctions bidon. Utilisez-les à dessein, sur une copie de votre projet, et vérifiez ce qu’elles ajoutent.

Comment les obfuscateurs exploitent les deux stratégies

Les auteurs de malwares (logiciels malveillants) savent quelles hypothèses fait chaque stratégie, et les techniques d’anti-désassemblage sont conçues pour casser précisément ces hypothèses. Un module ultérieur traite l’anti-désassemblage en profondeur ; en voici la version courte, pour que vous reconnaissiez les motifs quand votre listing a l’air faux :

• Octet parasite après un saut toujours pris. Un jmp inconditionnel par-dessus un octet comme 0xE8 (l’opcode de call rel32). Le balayage linéaire décode l’octet parasite comme un call de cinq octets, avalant les quatre octets suivants de vrai code. La descente récursive gère ce cas correctement.
• Prédicat opaque avec des octets parasites sur la branche morte. Remplacez le jmp par un saut conditionnel dont l’issue est fixe, comme xor ecx, ecx suivi de jz. Le CPU prend toujours le branchement, mais un désassembleur suppose les deux branches vivantes : la descente récursive décode donc aussi les octets parasites, et les deux décodages entrent en collision. Voir prédicats opaques.
• Instructions chevauchantes. Un octet qui est à la fois le dernier octet d’une instruction et le premier de l’instruction réellement exécutée ensuite. La séquence de deux octets EB FF est un jmp dont la cible est son propre second octet, où FF C0 se décode en inc eax. Aucun listing linéaire ne peut montrer les deux interprétations d’un même octet à la fois.
• Code généré à l’exécution. Le code déchiffré ou patché à l’exécution (code auto-modifiant, packers) n’est tout simplement pas dans le fichier ; aucune stratégie statique ne peut le retrouver. C’est le domaine de l’unpacking (dépaquetage) et de l’analyse dynamique.

Lab : deux désassembleurs, un octet parasite

Il vous faut un GCC Linux x86-64 (natif sous Linux, ou un compilateur croisé comme x86_64-linux-gnu-gcc sous macOS), binutils, Python 3 et un environnement virtuel avec capstone et pyelftools. Ghidra est facultatif. Le programme est inoffensif : il affiche deux nombres.

1. Créez le fichier C et un fichier assembleur écrit à la main contenant deux fonctions jouets :

   /* lab1.c - a harmless program whose helpers live in tricks.S */
   #include <stdio.h>
   
   int add_one(int x);    /* jmp over a junk byte               */
   int times_two(int x);  /* always-taken jz over a junk byte   */
   
   int main(void) {
       printf("%d %d\n", add_one(41), times_two(21));
       return 0;
   }

   /* tricks.S - two toy functions with an inserted junk byte */
           .intel_syntax noprefix
           .text
           .globl add_one
   add_one:
           jmp     1f              /* unconditional: skip the junk      */
           .byte   0xE8            /* first byte of "call rel32"        */
   1:      lea     eax, [rdi+1]
           ret
   
           .globl times_two
   times_two:
           xor     ecx, ecx        /* ZF = 1, so the jz is always taken */
           jz      2f
           .byte   0xE8
   2:      lea     eax, [rdi+rdi]
           ret
   
           .section .note.GNU-stack,"",@progbits

2. Compilez, gardez une copie strippée et préparez Python :

   x86_64-linux-gnu-gcc -O1 -o lab1 lab1.c tricks.S    # or plain gcc on Linux
   x86_64-linux-gnu-strip -o lab1_stripped lab1
   python3 -m venv venv && ./venv/bin/pip install capstone pyelftools

   Pour faire la même chose sous Windows, compilez avec x86_64-w64-mingw32-gcc et désassemblez avec x86_64-w64-mingw32-objdump -d. Notez que le premier argument entier y arrive dans ecx et non dans edi : les fonctions jouets renvoient donc d’autres nombres, mais la leçon de désassemblage est identique.

3. Balayage linéaire : désassemblez la copie strippée avec objdump et trouvez les deux fonctions juste après main (les adresses seront différentes sur votre système) :

   x86_64-linux-gnu-objdump -d -M intel lab1_stripped

     401116:	5b                   	pop    rbx
     401117:	c3                   	ret
     401118:	eb 01                	jmp    40111b <printf@plt+0xeb>
     40111a:	e8 8d 47 01 c3       	call   ffffffffc34158ac <printf@plt+0xffffffffc301487c>
     40111f:	31 c9                	xor    ecx,ecx
     401121:	74 01                	je     401124 <printf@plt+0xf4>
     401123:	e8 8d 04 3f c3       	call   ffffffffc37f15b5 <printf@plt+0xffffffffc33f0585>
     401128:	0f 1f 84 00 00 00 00 	nop    DWORD PTR [rax+rax*1+0x0]

   Les vrais lea et ret des deux fonctions ont disparu, avalés par deux call impossibles vers des adresses hors du programme. Deux cibles de branchement, 40111b et 401124, pointent au milieu de ces appels : c’est votre alarme de désynchronisation. Le flux se recale une instruction plus loin.

4. Enregistrez le désassembleur récursif sous recdis.py :

   # recdis.py - a tiny recursive-descent disassembler for x86-64 ELF files
   import sys
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64, CS_GRP_JUMP, CS_GRP_CALL, CS_GRP_RET
   from capstone.x86 import X86_OP_IMM
   from elftools.elf.elffile import ELFFile
   
   STOP = {"jmp", "ret", "hlt", "ud2"}         # no fall-through after these
   
   def load(path):
       elf = ELFFile(open(path, "rb"))
       text = elf.get_section_by_name(".text")
       seeds = {elf.header.e_entry}
       symtab = elf.get_section_by_name(".symtab")  # absent once stripped
       if symtab:
           seeds |= {s["st_value"] for s in symtab.iter_symbols()
                     if s["st_info"]["type"] == "STT_FUNC" and s["st_value"]}
       return text["sh_addr"], text.data(), seeds
   
   def direct_target(insn):
       """Return the target of a direct jmp/jcc/call, or None if indirect."""
       op = insn.operands[0] if insn.operands else None
       return op.imm if op is not None and op.type == X86_OP_IMM else None
   
   def disassemble(base, code, seeds, code_ptr_heuristic=False):
       md = Cs(CS_ARCH_X86, CS_MODE_64)
       md.detail = True
       end = base + len(code)
       insns = {}                                 # address -> instruction
       todo = [a for a in seeds if base <= a < end]
       while todo:
           addr = todo.pop()
           while base <= addr < end and addr not in insns:
               insn = next(md.disasm(code[addr - base:], addr, 1), None)
               if insn is None:                   # undecodable bytes: give up here
                   print(f"  ! invalid opcode at {addr:#x}")
                   break
               insns[addr] = insn
               if insn.group(CS_GRP_JUMP) or insn.group(CS_GRP_CALL):
                   target = direct_target(insn)
                   if target is not None:
                       todo.append(target)
                   else:
                       print(f"  ? indirect {insn.mnemonic} {insn.op_str} at {addr:#x}")
               elif code_ptr_heuristic:
                   # an immediate that points into .text may be a code pointer
                   for op in insn.operands:
                       if op.type == X86_OP_IMM and base <= op.imm < end:
                           todo.append(op.imm)
               if insn.mnemonic in STOP or insn.group(CS_GRP_RET):
                   break
               addr += insn.size                  # fall through (also after call)
       return insns
   
   def report(insns):
       covered = {}                               # byte address -> owning insns
       for a, i in insns.items():
           for b in range(a, a + i.size):
               covered.setdefault(b, []).append(a)
       for a in sorted(insns):
           i = insns[a]
           clash = {o for b in range(a, a + i.size) for o in covered[b]} - {a}
           flag = "  <-- overlaps " + ", ".join(hex(c) for c in sorted(clash)) if clash else ""
           print(f"{a:#x}: {i.bytes.hex(' '):<24} {i.mnemonic} {i.op_str}{flag}")
   
   if __name__ == "__main__":
       base, code, seeds = load(sys.argv[1])
       insns = disassemble(base, code, seeds, "--code-pointers" in sys.argv)
       report(insns)
       print(f"{len(insns)} instructions, {sum(i.size for i in insns.values())}"
             f" of {len(code)} .text bytes reached")

   Le cœur est la liste de travail de disassemble : dépiler une adresse, décoder jusqu’à une instruction d’arrêt, empiler chaque cible de branchement direct. La fonction report signale toute paire d’instructions qui revendiquent le même octet.

5. Lancez-le sur le binaire strippé, avec le seul point d’entrée comme graine :

   ./venv/bin/python recdis.py lab1_stripped

     ? indirect call qword ptr [rip + 0x2f6e] at 0x401064
   0x401040: 31 ed                    xor ebp, ebp
   ...
   0x40105d: 48 c7 c7 e7 10 40 00     mov rdi, 0x4010e7
   0x401064: ff 15 6e 2f 00 00        call qword ptr [rip + 0x2f6e]
   0x40106a: f4                       hlt
   12 instructions, 43 of 353 .text bytes reached

   La descente récursive pure a trouvé _start et rien d’autre. _start passe l’adresse de main à la bibliothèque C dans rdi, puis appelle __libc_start_main indirectement via la GOT. Il n’y a aucun call main direct à suivre.

6. Activez l’heuristique des pointeurs de code, qui traite les valeurs immédiates pointant dans .text comme du code candidat :

   ./venv/bin/python recdis.py lab1_stripped --code-pointers

   0x401118: eb 01                    jmp 0x40111b
   0x40111b: 8d 47 01                 lea eax, [rdi + 1]
   0x40111e: c3                       ret
   0x40111f: 31 c9                    xor ecx, ecx
   0x401121: 74 01                    je 0x401124
   0x401123: e8 8d 04 3f c3           call 0xffffffffc37f15b5  <-- overlaps 0x401124, 0x401127
   0x401124: 8d 04 3f                 lea eax, [rdi + rdi]  <-- overlaps 0x401123
   0x401127: c3                       ret   <-- overlaps 0x401123
   ...
   70 instructions, 221 of 353 .text bytes reached

   mov rdi, 0x4010e7 sert maintenant de graine pour main, et de là pour les deux fonctions. Dans add_one, l’octet parasite est simplement sauté : la descente récursive l’emporte. Dans times_two, elle décode les deux branches du je toujours pris, si bien que le call parasite et les vrais lea/ret se chevauchent. Votre outil signale au moins le conflit ; un listing linéaire devrait choisir l’un des deux.

7. Mesurez l’autosynchronisation. Enregistrez ceci sous resync.py, compilez un programme ordinaire sans astuce, et lancez-le :

   # resync.py - how many bogus instructions before a misaligned decode lines up again?
   import sys
   from collections import Counter
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64
   from elftools.elf.elffile import ELFFile
   
   text = ELFFile(open(sys.argv[1], "rb")).get_section_by_name(".text")
   code, base = text.data(), text["sh_addr"]
   md = Cs(CS_ARCH_X86, CS_MODE_64)
   boundaries = {i.address for i in md.disasm(code, base)}   # the true stream
   
   cost = Counter()
   for off in range(len(code) - 32):
       if base + off in boundaries:
           continue                                           # only wrong starts
       for n, insn in enumerate(md.disasm(code[off:], base + off), 1):
           if insn.address + insn.size in boundaries:         # back in step
               cost[n] += 1
               break
       else:
           cost["never"] += 1                                 # hit undecodable bytes
   total = sum(cost.values())
   for n in sorted(k for k in cost if k != "never"):
       print(f"back in step after {n} bogus instruction(s): {cost[n]:4} starts")
   print(f"hit an invalid opcode first:           {cost['never']:4} starts")
   print(f"{total} misaligned starts tested")

   cat > plain.c <<'EOF'
   #include <stdio.h>
   int main(int argc, char **argv) {
       unsigned h = 5381;
       for (int i = 1; i < argc; i++)
           for (char *p = argv[i]; *p; p++)
               h = h * 33 + (unsigned char)*p;
       printf("%08x\n", h);
       return 0;
   }
   EOF
   x86_64-linux-gnu-gcc -O2 -o plain plain.c
   ./venv/bin/python resync.py plain

   back in step after 1 bogus instruction(s):  119 starts
   back in step after 2 bogus instruction(s):   51 starts
   back in step after 3 bogus instruction(s):   26 starts
   back in step after 4 bogus instruction(s):    9 starts
   back in step after 5 bogus instruction(s):    9 starts
   back in step after 6 bogus instruction(s):    5 starts
   back in step after 7 bogus instruction(s):    2 starts
   hit an invalid opcode first:             56 starts
   277 misaligned starts tested

   La sortie de GCC ne place aucune donnée dans .text : son décodage linéaire constitue donc une vérité de référence honnête. Capstone s’arrête sur un opcode invalide, ce qui explique que certains départs ne se recalent jamais ici ; objdump, lui, affiche (bad) et continue.

8. Facultatif, dans Ghidra : importez lab1_stripped, lancez l’auto-analyse avec les options par défaut et allez aux adresses des deux fonctions. Vérifiez si l’octet parasite de add_one est laissé en donnée non définie, comment le conflit de times_two est affiché (regardez dans la fenêtre Bookmarks les signets d’erreur), et si Ghidra a trouvé main sans aucun symbole.

Questions : objdump reprend au symbole times_two dans le lab1 non strippé. Cette reprise aurait-elle compté si l’instruction parasite avait été plus longue d’un octet ? Quelle heuristique a retrouvé main à l’étape 6, et quel faux positif la même heuristique pourrait-elle produire ? Si vous remplaciez l’octet parasite 0xE8 par 0x90 (nop), qu’afficherait chaque désassembleur, et l’astuce cacherait-elle encore quelque chose ? Pourquoi aucune des deux stratégies ne peut-elle déterminer statiquement que le je de times_two est toujours pris ?

À retenir

• Désassembler une instruction est facile ; décider où se trouve le code et où commence chaque instruction est le vrai problème, surtout sur le x86 à longueur variable.
• Le balayage linéaire voit chaque octet mais décode les données comme du code, ce qui désynchronise le flux ; le x86 se recale généralement en quelques instructions, mais les instructions avalées sont perdues.
• La descente récursive suit le flot de contrôle et saute les données, mais rate les cibles des branchements indirects et le code référencé uniquement depuis les données, et gère mal les appels sans retour et les branches jamais prises.
• IDA, Ghidra et Binary Ninja, c’est la descente récursive plus des heuristiques : recherche de prologues, reconstruction des tables de switch, recherche de pointeurs de code, signatures et, sur Windows x64, débuts de fonction tirés de .pdata.
• Des cibles de branchement qui tombent à l’intérieur d’une instruction, et des instructions qui se chevauchent, sont des signes forts d’anti-désassemblage ; examinez ces octets à la main.