Partie 15 - La unsorted bin - mécanismes de protection (2/4)

La unsorted bin : mécanismes de protection (2/4)

Protections selon les versions

Comme pour le tcache, voyons maintenant quelles protections ont été ajoutées à la unsorted bin au fil du temps.

• 2.11 : Contrôle de l’intégrité des deux liens entre la unsorted bin et le dernier bloc lors de l’insertion d’un bloc libre ;
• 2.28 : Contrôle de l’intégrité des deux liens entre le bloc à retirer (victim) et son prédécesseur lors du retrait de victim (au moment d’une allocation par exemple) ;
• 2.29 : Ajout de plusieurs vérifications lors de la recherche d’un bloc libre, adaptée à l’allocation demandée, dans la unsorted bin.

Un bloc désigné comme victim est un bloc qui va potentiellement être retiré de la unsorted bin, pour satisfaire une allocation par exemple.

Version 2.11 - Contrôle de l’intégrité des liens d’un bloc inséré

❌ Messages d’erreur associés :

1. malloc(): corrupted unsorted chunks ;
2. malloc(): corrupted unsorted chunks 2 ;
3. free(): corrupted unsorted chunks.

Lors de la version 2.11 de la glibc, un contrôle d’intégrité est ajouté dans le fameux fichier malloc.c. Il ne s’agit pas de trois vérifications distinctes mais d’une seule et même vérification présente aux trois endroits suivants :

1. lors de l’ajout d’un reste dû au fractionnement d’un bloc libre de la unsorted bin ;
2. lors de l’ajout d’un reste (dans la unsorted bin) dû au fractionnement d’un bloc libre de la small bin ou large bin ;
3. lorsqu’un bloc vient d’être libéré et qu’il doit être ajouté à la unsorted bin.

La vérification effectuée est la suivante :

bck = unsorted_chunks(av);
fwd = bck->fd;
if (__builtin_expect (fwd->bk != bck, 0)) // Vérification ici
{
	errstr = "free(): corrupted unsorted chunks";
	goto errout;
}

Lorsque l’on n’a pas l’habitude de lire le code source de malloc.c, on a très rapidement une migraine en essayant de déchiffrer de tête les différentes expressions 🤯. Faisons cela ensemble.

Tout d’abord, il faut savoir que unsorted_chunks(av) pointe vers la unsorted bin. À chaque fois que vous lirez unsorted_chunks(av) vous pouvez le traduire par “unsorted_bin de l’arène courante”. Pour rappel, voici ce que l’on entend par unsorted bin en mémoire :

Cela revient en quelque sorte à considérer la unsorted bin comme si c’était un bloc en mémoire avec un champ fd et bk.

En décortiquant les éléments utilisés lors de la vérification, cette dernière peut être décrite in fine de cette manière : if(unsorted_bin->fd->bk != unsorted_bin). Cela consiste à vérifier l’intégrité de ces deux liens surlignés en 🟡 :

Finalement la vérification consiste à dire : “si je pars de la unsorted bin et que je fais un pas en avant puis un pas en arrière, suis-je retombé au même endroit ?”.

Version 2.28 - Contrôle de l’intégrité des liens d’un bloc à retirer

❌ Message d’erreur associé : malloc(): corrupted unsorted chunks 3.

Ce message d’erreur ressemble beaucoup à ceux de la précédente vérification (version 2.11). Toutefois, la vérification mise en place diffère un peu. Jetons-y un œil :

bck = victim->bk;

// (...)

/* remove from unsorted list */
if (__glibc_unlikely (bck->fd != victim))
	malloc_printerr ("malloc(): corrupted unsorted chunks 3");

En décortiquant l’expression utilisée dans la condition nous obtenons ceci : if (victim->bk->fd != victim).

Cette fois-ci, la vérification peut être traduite par : “si je pars du bloc à retirer (victim) et que je fais un pas en arrière puis un pas en avant, suis-je retombé au même endroit ?”

Prenons l’exemple suivant où le premier bloc A est le bloc à retirer :

La différence avec la vérification de la version 2.11 est que le point de départ est le premier bloc de la unsorted bin et non pas la unsorted bin elle-même.

Version 2.29 - Ajout de plusieurs vérifications

❌ Messages d’erreur associés :

1. malloc(): invalid size (unsorted) ;
2. malloc(): invalid next size (unsorted) ;
3. malloc(): mismatching next->prev_size (unsorted) ;
4. malloc(): unsorted double linked list corrupted ;
5. malloc(): invalid next->prev_inuse (unsorted).

Wow 😮. Ça fait pas mal de contrôles en plus 🥵 ! Je vous propose de les voir petit à petit, un à un.

1️⃣ malloc(): invalid size (unsorted) ➡️ contrôle de la taille min et max

Dans la fonction malloc, une recherche est réalisée dans la unsorted bin en partant du début (via unsorted_bin->bk) afin de trouver un potentiel bloc victim répondant aux exigences de l’allocation demandée.

Un contrôle est alors rapidement réalisé sur ce potentiel bloc de la unsorted bin :

size = chunksize (victim);

// (...)

if (__glibc_unlikely (size <= 2 * SIZE_SZ)  
|| __glibc_unlikely (size > av->system_mem))
	malloc_printerr ("malloc(): invalid size (unsorted)");

La fonction chunksize retourne la taille du bloc en prenant en compte les métadonnées. Il s’agit, en d’autre termes, de la taille que l’on trouve dans les métadonnées sans prendre en considérations les bits d’informations (PREV_INUSE etc.) :

La valeur de SIZE_SZ est de :

• 8 en 64 bits ;
• 4 en 32 bits.

Quant à av->system_mem, il s’agit de la taille de l’espace mémoire alloué pour le tas. Par exemple :

Au final, la taille size doit être :

• strictement supérieure à 8 (32 bits) ou 0x10 (64 bits) ;
• inférieure ou égale à la taille totale du tas.

Il est possible que la valeur minimale de size aboutisse in fine à 0x10 octets (sur 32 bits) ou 0x20 octets (sur 64 bits), en raison de contraintes d’alignement imposées sur les blocs du tas par d’autres vérifications internes.

2️⃣ malloc(): invalid next size (unsorted) ➡️ contrôle de la taille min et max du bloc suivant

En ce qui concerne cette vérification, c’est fastoche, il s’agit du même contrôle de taille sauf que cette fois-ci cela s’applique sur le bloc situé en dessous de victim (conformément à la taille size indiquée dans les métadonnées de victim) :

mchunkptr next = chunk_at_offset (victim, size);

// (...)

if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
|| __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
	malloc_printerr ("malloc(): invalid next size (unsorted)");

3️⃣ malloc(): mismatching next->prev_size (unsorted) ➡️ contrôle de cohérence entre size et prev_size

Cette vérification n’est pas très compliquée à comprendre, la voici :

size = chunksize (victim);
mchunkptr next = chunk_at_offset (victim, size);

// (...)

if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
	malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");

Cela consiste à se poser cette question : “est-ce que la taille size du bloc victim est égale à la taille prev_size du bloc suivant ?”. En effet, quand un bloc est libéré et placé dans la unsorted bin, le champ prev_size du bloc suivant est rempli avec la taille du bloc libéré.

Dans l’exemple ci-dessous, un bloc de 0x100 octets se retrouve dans la unsorted bin (après fractionnement), la valeur de size et prev_size sont, dans ce cas, cohérentes :

Cette erreur peut survenir lorsque l’on corrompt le champ prev_size pour forcer la consolidation de deux blocs en vue d’une attaque exploitant la unsorted bin.

4️⃣ malloc(): unsorted double linked list corrupted ➡️ contrôle de l’intégrité du bloc victim

Comme d’habitude, voici la partie du contrôle qui nous intéresse :

victim = unsorted_chunks (av)->bk
bck = victim->bk;

if (__glibc_unlikely (bck->fd != victim)
|| __glibc_unlikely (victim->fd != unsorted_chunks (av)))
	malloc_printerr ("malloc(): unsorted double linked list corrupted");

Bon, je vous sens chauds, quelle est la première vérification effectuée dans le if ?

Le programme vérifie que victim->bk->fd permet de bien retomber sur victim.

Oui c’est ça ! Vous voyez, vous commencez désormais à avoir l’habitude de ces vérifications 😉. Quid de la deuxième vérification ?

Le programme vérifie que victim->fd pointe vers la unsorted bin. En d’autres termes, il vérifie que victim est bien le premier bloc de la unsorted bin. {: .prompt-info

Effectivement il est possible de le comprendre de cette manière. Néanmoins une question subsiste : pourquoi victim devrait toujours être le premier bloc alors que ce contrôle est effectué dans une boucle qui passe d’un bloc victim à un autre dans la unsorted bin afin de trouver un bloc adéquat pour l’allocation ?

Nous sommes d’accord qu’en début de boucle le premier bloc analysé victim est bien le premier bloc de la unsorted bin. Mais si la taille de ce dernier ne correspond pas à l’allocation demandée, le bloc suivant analysé devient victim auquel cas vicitm->fd ne devrait plus, a priori, pointer vers la unsorted bin. Comment faire coïncider tout cela ?

Traitement des blocs de la unsorted bin

Pour répondre à cette problématique, revenons à un point essentiel du fonctionnement de la unsorted bin : les blocs libres ont une chance d’être réutilisés, s’ils ne le sont pas, ils sont recyclés dans les small bins et large bins. C’est un peu comme le goulag quoi.

Pour chaque bloc victim de la unsorted bin :

• si la taille du bloc victim est exactement la même que celle de l’allocation ➡️ victim est retiré de la unsorted bin et retourné par malloc ;
• sinon, si la taille du bloc victim est plus grande que celle de l’allocation ➡️ victim est fractionné : la partie ayant la taille demandée est retournée par malloc tandis que l’autre, à savoir le reste, est mis dans la unsorted bin ;
• sinon, victim est retiré de la unsorted bin et est placé dans une small bin ou large bin en fonction de sa taille.

Un des corollaires de cet algorithme est que, lors de la recherche d’un bloc adéquat dans la unsorted bin, victim est toujours le premier bloc. Pour mieux visualiser ce comportement, prenons le cas de ces deux blocs dans la unsorted bin :

1. le premier bloc : 0x500 octets ;
2. le second bloc : 0x800 octets.

Que va-t-il se passer lorsque malloc(0x800); sera appelé ?

1. le programme analyse le premier bloc A qui devient victim. N’ayant pas la taille suffisante pour l’allocation, il est recyclé dans la large bin (étant donné sa grande taille) ;
2. le programme passe au prochain bloc B qui devient le nouveau bloc victim. Sachant qu’il satisfait la demande en termes de taille, il est donc retourné par malloc ;
3. le bloc B a été alloué, il ne reste plus aucun bloc dans la unsorted bin.

Ça devient plus facile de comprendre comment chaque bloc analysé victim finit par devenir le premier bloc de la unsorted bin non ?

5️⃣ malloc(): invalid next->prev_inuse (unsorted) ➡️ vérification du bit PREV_INUSE du bloc suivant

Passons à la dernière vérification ajoutée lors de la version 2.29 dans la unsorted bin. Elle est plus facile à comprendre que la précédente. Voici le code associé à cette vérification :

mchunkptr next = chunk_at_offset (victim, size);

// (...)

if (__glibc_unlikely (prev_inuse (next)))
	malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

Pour rappel, victim est le bloc courant analysé dans la unsorted bin afin de voir s’il remplit les exigences de l’allocation. next est le bloc situé en dessous de victim (conformément à la taille size de victim). Sachant que victim est un bloc libre, alors le bit PREV_INUSE de next ne devrait pas être activé.

Par exemple, dans le cas où un bloc libre de 0x80 octets (dû à une fragmentation) est présent dans la unsorted bin suivi d’un bloc next de 0x20 octets, voici ce que cela donne :

Si le bit PREV_INUSE de next vaut 1, alors une anomalie est détectée et une erreur est renvoyée.