Partie 3 - Organisation de la heap - les corbeilles

Organisation de la heap : les bins (ou corbeilles)

Nous avons précédemment vu le fonctionnement de deux champs des métadonnées : prev_size et size. Il reste encore 4 champs à explorer :

• fd et bk ;
• fd_nextsize et bk_nextsize (uniquement utilisés dans les très gros blocs).

Afin de mieux comprendre à quoi servent ces champs, je vous propose de voir leur utilisation au sein des différentes bins (ou corbeilles) histoire de ne pas les aborder seulement en surface.

Fonctionnement des différentes bins

Nous avons précédemment vu que les blocs libérés allaient dans des corbeilles pour des raisons d’optimisation. Néanmoins, nous ne sommes pas allés dans les détails du fonctionnement de ces différentes corbeilles :

• combien y en a-t-il ?
• quelles sont les différences entre elles ?
• comment sont liés les blocs libérés dans une corbeille ?
• comment est choisi le bloc à réutiliser parmi la liste de blocs d’une même corbeille ?

Tâchons de fournir des éléments de réponse à ces questions. Vous aurez une réponse complète lorsque l’on aura introduit, au fur et à mesure que l’on avance, tous les détails liés au tas.

La liste des types de corbeilles auxquelles nous allons nous intéresser est la suivante :

• tcache (thread cache) ;
• fastbin ;
• unsorted bin ;
• small bin ;
• large bin.

Voici un résumé très succinct des différentes corbeilles :

Nom	Ordre de réutilisation des blocs	Type de liste	Consolidation possible ?	Utilisation
Tcache	LIFO	Liste chaînée	Non	Petits et moyens blocs
Fastbins	LIFO	Liste chaînée	Non (sauf dans certains cas)	Petits blocs
Unsorted Bin	FIFO	Liste doublement chaînée circulaire - non triée	Oui	Stockage temporaire de moyens et grands blocs
Small Bins	FIFO	Liste doublement chaînée circulaire	Oui	Petits et moyen blocs
Large Bins	LIFO	Liste doublement chaînée circulaire - triée	Oui	Blocs de très grande, grande et moyenne taille

Les corbeilles sont listées ci-dessus avec un ordre bien précis. C’est généralement dans cet ordre que vous les trouverez listées dans gdb et c’est aussi dans cet ordre qu’elles sont généralement utilisées.

Ainsi, si un bloc libéré a une taille lui permettant d’aller à la fois dans une fastbin et le tcache, il ira en priorité dans le tcache. Idem pour les trois autres corbeilles, si un bloc libéré a une taille lui permettant d’aller dans l’unsorted bin, une small bin (ou large bin s’il est de très grande taille) il ira d’abord dans l’unsorted bin.

Le résumé ci-dessus est très sommaire. Un résumé bien plus détaillé nous attend à la fin des différents chapitres consacrés au tas 👀.

Les arènes

Avant d’entrer dans les détails de chaque corbeille, intéressons-nous d’abord au système d’arène (ou arena 🇬🇧). Nous en avions brièvement parlé lors du précédent chapitre lorsque nous avons parlé du bit NON_MAIN_ARENA. En reprenant l’analogie des corbeilles et du recyclage, l’arène est en quelque sorte une déchetterie intelligente.

Source

L’arène répertorie les différentes corbeilles ainsi que diverses informations, comme :

• l’adresse mémoire où est située chaque corbeille ;
• la taille maximum d’un bloc pouvant aller dans une corbeille en particulier.

L’arène dispose d’autres informations liées au tas comme l’adresse du bloc du sommet ainsi que l’adresse de la prochaine arène. En effet, il est possible d’utiliser plusieurs arènes dans les programmes utilisant plusieurs fils d’exécution afin de ne pas bloquer une seule et même arène à chaque fois qu’un fil d’exécution doit faire une allocation dynamique sur le tas.

Il existe toujours au moins une arène, celle qui est initialement créée lorsque le programme est lancé, il s’agit de l’arène principale (ou main arena 🇬🇧). En général, les challenges de heap en pwn n’utilisent qu’un seul fil d’exécution. De ce fait, dans la majorité des cas vous n’aurez à prendre en compte qu’une seule arène : l’arène principale.

En somme, l’arène permet une gestion globale et d’avoir une vue synthétique sur l’état du tas et des corbeilles.

Si vous êtes amenés à lire un peu de code source provenant de la glibc, il est possible vous que trouviez la présence d’un paramètre av de type malloc_state comme ici. Il s’agit tout simplement d’un pointeur vers l’arène du bloc courant.

Je précise ce point car cette information n’est pas facile à trouver.

📋 Synthèse

Comprendre le fonctionnement des différentes corbeilles est crucial dans le domaine du pwn dans le tas. Il existe plusieurs types de corbeilles, chacune ayant ses spécificités en termes de tailles, de gestion des blocs etc.

Nous avons évoqué le système des arènes. Pour l’instant il n’est pas nécessaire de comprendre comment cela fonctionne en détail. Il suffit de garder en tête que c’est la principale entité utilisée pour la gestion globale de tous les types de corbeilles.

Lors des prochains chapitres, nous analyserons les différents types de corbeilles et nous nous intéresserons principalement à :

• leur fonctionnement ;
• le nombre et la taille des blocs gérés ;
• les protections implémentées ;
• les métadonnées d’un bloc libre de chaque type de corbeille.

Dans chacun de ces chapitres, nous irons de plus en plus dans les détails. À un certain stade, si vous n’arrivez plus à suivre ou que certaines notions vous semblent abstraites, n’hésitez pas à passer à un autre chapitre et y revenir le jour où vous aurez besoin de plus de détails concernant un type de corbeilles en particulier.

C’est vraiment important que vous compreniez que les prochains chapitres, concernant les différents types de corbeilles, ne sont pas à lire de manière mécanique et linéaire.

Il y a beaucoup trop d’informations pour que l’on puisse les retenir en une fois. Une bonne méthodologie serait de les survoler, les lire en diagonale et de les relire de plus en plus en profondeur jusqu’à ce que les diverses informations soient gravées dans le marbre.

Si vous souhaitez tout de même les lire un à un de manière linéaire, je vous souhaite bon courage 😆 !