Partie 2 - Théorie de la heap - structures internes et métadonnées

Théorie de la heap : structures internes et métadonnées

Lors du précédent chapitre, nous avons introduit les principaux mécanismes liés au tas à savoir :

• l’allocation ;
• la libération ;
• le fonctionnement du top chunk ;
• la présence de corbeilles.

Avant d’aller plus loin, il est nécessaire de nous focaliser sur les métadonnées des blocs. En effet, les métadonnées sont cruciales pour diverses raisons :

• les métadonnées contiennent des informations sur un bloc : sa taille, son statut (utilisé/libre) etc. ;
• lorsqu’un bloc est libéré, les métadonnées permettent de lier les blocs appartenant à une même corbeille les uns aux autres en utilisant notamment des pointeurs ;
• la majorité des techniques d’exploitation dans le tas reposent sur l’exploitation des métadonnées.

Les métadonnées : prev_size et size

Intéressons-nous aux deux premiers champs des métadonnées, à savoir : prev_size et size.

En 64 bits

Découvrons ensemble le fonctionnement des métadonnées. Prenons le cas d’un programme 64 bits qui ne fait qu’une allocation :

void *a = malloc(1);

Cette fois-ci, zoomons davantage sur le tas afin de voir comment est réellement structuré le bloc que nous venons d’allouer :

Le bloc alloué est ce qui est entouré en rouge 🔴.

Le bloc du sommet n’est pas représenté ici par souci de clarté mais il est bien présent dans le tas.

Mais ce n’est pas un bloc, il a une forme totalement bizarre 🙄.

En effet ce n’est pas un bloc rectangulaire. Il est nécessaire de redoubler d’attention ici afin de comprendre comment sont imbriqués les différents blocs ensemble.

Décortiquons ce bloc :

• En gris (nom du champ : prev_size) : nous verrons à quoi ce champ sert lorsqu’il y aura plusieurs blocs dans le tas. Pour l’instant, comme il n’y a aucun bloc qui précède celui-ci, le champ gris est constitué d’octets nuls : 0x0000000000000000.
• En jaune 🟡 (nom du champ : size): ce champ fait partie des métadonnées du bloc. Il contient la taille du bloc mais aussi d’autres informations. Il s’agit d’un OU logique de la taille du bloc avec 3 autres informations :
  • Size : qui est la taille du bloc alloué ici 0x20 ( et non 0x28 car le champ en gris n’est pas comptabilisé). Egalement, ne confondez pas la taille du bloc (délimitée en rouge) avec la taille des données utilisables (en bleu) qui est de 0x18 octets.
  • A (ou NON_MAIN_ARENA): 3ème bit de poids faible qui vaut 1 si le bloc n’appartient pas à l’arène principale, 0 sinon. Nous verrons au prochain chapitre ce que sont les arènes. Considérez pour l’instant que dans un programme ayant un seul fil d’exécution, ce bit vaut toujours 0. Ici ce bit vaut donc 0.
  • M (ou IS_MMAPPED) : 2ème bit de poids faible qui vaut 1 si le bloc a été alloué par mmap, 0 sinon. Ici ce bit vaut donc 0.
  • P (ou PREV_INUSE): 1er bit de poids faible qui vaut 0 si le champ prev_size est utilisé, 1 sinon. Oui je sais, cela paraît paradoxal car le nom de ce bit est PREV_INUSE et non PREV_NOT_INUSE, ce qui prête à confusion 😅. Pour l’instant nous n’avons pas vraiment besoin de savoir à quoi il sert. Ici ce bit vaut 1.
  • La valeur de ce champ est ici : 0x20 | b'000' | b'00' | b'1' == 0x21
• En bleu 🔵 : ce sont les données réellement utilisées et utilisables par l’utilisateur. D’ailleurs, dans cet exemple, le pointeur a pointe vers 0x500000000010 car malloc(1) retourne un pointeur vers 0x500000000010 et non pas 0x500000000000 étant donné que la gestion des métadonnées est totalement opaque du point de vue de l’utilisateur. La taille totale des données utilisables est ici de 0x18. Vous comprenez désormais pourquoi malloc(0x19) alloue un bloc de 0x30 octets plutôt que de 0x20 ; cela permet de ne pas empiéter sur les métadonnées 🟡 du prochain bloc.

J’imagine déjà vos têtes 😵‍💫🥴🫨 à ce stade 😆. Si vous êtes perturbés par cette manière de structurer un bloc, c’est normal, elle ne ressemble pas forcément à ce que l’on aurait pu s’imaginer.

Ce qui est compliqué avec le tas est qu’il y a beaucoup de notions, de mécanismes et de mots clés qu’il n’est pas possible d’assimiler en une fois. Vous reviendrez sûrement plus tard relire ces chapitres avec une nouvelle manière de percevoir les choses. C’est en faisant plusieurs challenges d’exploitation de heap que vous allez marquer au fer rouge ces différentes notions.

Néanmoins, nous avons besoin des bases avant d’entamer la partie pratique qui arrivera dans quelques chapitres.

Poursuivons notre lancée et voyons ce que donne l’exécution de ce bout de code où le premier bloc est libéré :

void *A = malloc(1);
void *B = malloc(1);

free(A);

Cela peut se résumer ainsi :

1. état initial : les deux allocations de 0x20 octets ont été réalisées ;
2. free(0x500000000010) : lorsque le premier bloc est libéré, il va dans la corbeille adéquate (non représentée ici). Cela n’a pas changé les métadonnées du champ mchunk_size 🟡 du bloc libéré, ni du bloc suivant. En effet, comme il s’agit d’un petit bloc libéré, il n’est pas sujet à consolidation. Le champ prev_size du bloc A est donc inutilisé. Il en est de même pour le bit P (PREV_INUSE) du bloc B qui reste égal à 1 étant donné que le champ prev_size du précédent bloc n’est pas utilisé.

Vous remarquerez que l’adresse donnée en paramètre à free() n’est pas l’adresse du bloc mais l’adresse des données du bloc. Ce qui est logique car void *A pointe vers 0x500000000010, donc free(A) revient à appeler free(0x500000000010).

Dans le précédent chapitre, nous n’avions pas parlé de ce détail car nous avions ignoré les métadonnées. Désormais, il faudra prendre en compte cette différence pour ne pas être perturbé par la suite.

Que se serait-il passé si le bloc libéré était un bloc de grande taille ? Modifions la taille du premier bloc libéré :

void *A = malloc(0x700);
void *B = malloc(1);

free(A);

Cela donne ceci :

1. état initial : les deux allocations sont effectuées. Nous remarquons qu’un bloc de 0x710 octets a été alloué alors que l’on a utilisé malloc(0x700). Rappelez-vous, la taille réellement demandée est de 0x700 + 8 en prenant en compte le champ mchunk_size 🟡 du prochain bloc alloué. Ensuite, 0x708 est aligné sur 0x10 octets, ce qui donne la taille finale du bloc : 0x710 ;
2. free(0x500000000010) : le premier bloc est libéré et mis dans sa corbeille correspondante (non représentée ici). Étant donné qu’il s’agit d’un bloc de grande taille pouvant être consolidé avec d’autres blocs, le champ prev_size est saisi. Cela implique que le bit P du bloc suivant (bloc B) soit mis à 0.

Il aurait quelle tête le bloc du sommet si on l’affichait avec ses métadonnées ?

En affichant le bloc du sommet, cela donne :

Après tout, le bloc du sommet est un bloc comme les autres ?

La taille du top chunk est ici de 0x1000 octets, cela ne reflète pas la réalité. La taille du bloc du sommet est généralement de l’ordre de 0x21000 octets.

Euh là je comprends plus trop 😵‍💫. prev_size fait partie des métadonnées à la fin du bloc A ou au début du bloc B ?

Officiellement, le champ prev_size appartient aux métadonnées du bloc B, et non à celles du bloc A. Dans les schémas précédents, nous avons délibérément choisi de ne pas inclure prev_size dans l’encadré rouge du bloc suivant. Cela vise à éviter toute confusion et à souligner que ce champ est exploité par le bloc précédent tant que celui-ci reste en cours d’utilisation.

En effet, ce champ n’a de sens pour un bloc donné que si le précédent bloc est libéré et qu’il a une taille lui permettant d’être consolidé. Voici comment est structuré un bloc dans la libc :

struct malloc_chunk {

  INTERNAL_SIZE_T mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

Pour l’instant nous avons seulement vu les deux premiers membres, à savoir mchunk_prev_size (ou prev_size pour les intimes) et mchunk_size. Nous verrons les 4 autres dans le prochain chapitre consacré aux différentes corbeilles.

Par souci de concision, prev_size désignera mchunk_prev_size et size désignera mchunk_size lorsque l’on parlera de métadonnées.

Comme vous pouvez le constater, le champ mchunk_prev_size est considéré comme le premier membre des métadonnées d’un bloc (chunk). Ainsi, si vous lisez, dans le code source de la libc, une expression du type chunk->mchunk_prev_size, il s’agit du premier champ (les 8 premiers octets) du bloc chunk.

Pour résumer, voici les deux métadonnées que nous avons vues lors de ce chapitre :

• mchunk_prev_size : lorsque le bloc précédant le bloc courant est libéré et qu’il a une taille permettant la consolidation, la taille du précédent bloc est insérée dans ce champ. Cela permet de savoir qu’en partant d’un bloc B et en revenant de mchunk_prev_size octets en arrière, on tombe sur le bloc libre A ;
• mchunk_size : OU logique de 4 éléments :
  • La taille du bloc (en prenant en compte les métadonnées, sauf prev_size)
  • A (NON_MAIN_ARENA):
    • 0 si le bloc fait partie de l’arène principale
    • 1 sinon
  • M (IS_MMAPPED) :
    • 1 si le bloc a été alloué par mmap
    • 0 sinon
  • P (PREV_INUSE):
    • 0 si le précédent bloc est libre et que sa taille lui permet d’être consolidé (grande taille)
    • 1 sinon

Pour ce qui est des bits NON_MAIN_ARENA et IS_MMAPPED, ils seront généralement nuls dans des challenges de pwn ayant un seul fil d’exécution.

En revanche, PREV_INUSE est très important en pwn car en le modifiant il est possible de totalement chambouler le tas et réussir, in fine, une exécution de code arbitraire 😊. D’autant plus que l’on pourrait penser que ce bit est toujours nul dans le cas où le précédent bloc est libre alors qu’il y a des conditions supplémentaires.

En 32 bits

En 32 bits ça marche comment 🤔 ?

Pour les exemples utilisés dans ce chapitre, le principe est le même. Les deux principales différences sont :

• la taille minimale d’un bloc qu’il est possible d’allouer est de 0x10 (au lieu de 0x20) ;
• la taille des champs constituant les métadonnées est sur 4 octets (au lieu de 8).

📋 Synthèse

Nous avons exploré les métadonnées des blocs dans la heap et leur importance pour l’allocation, la libération et l’exploitation dans le tas :

• prev_size :
  • contient la taille du bloc précédent (uniquement si ce dernier est libre et consolidable) ;
  • permet de remonter au bloc précédent pour des opérations de consolidation.
• size : contient la taille du bloc et d’autres informations sur le bloc via un OU logique

Ces métadonnées sont essentielles pour le fonctionnement du tas, mais également pour plusieurs techniques d’exploitation dont nous traiterons ultérieurement.