First Fit

Reading time: 4 minutes

First Fit

Wenn Sie Speicher in einem Programm mit glibc freigeben, werden verschiedene "Bins" verwendet, um die Speicherblöcke zu verwalten. Hier ist eine vereinfachte Erklärung von zwei gängigen Szenarien: unsortierte Bins und Fastbins.

Unsortierte Bins

Wenn Sie einen Speicherblock freigeben, der kein schneller Block ist, gelangt er in den unsortierten Bin. Dieser Bin fungiert wie eine Liste, in die neue freigegebene Blöcke an den Anfang (den "Kopf") hinzugefügt werden. Wenn Sie einen neuen Speicherblock anfordern, schaut der Allokator von hinten (dem "Schwanz") in den unsortierten Bin, um einen Block zu finden, der groß genug ist. Wenn ein Block aus dem unsortierten Bin größer ist als das, was Sie benötigen, wird er aufgeteilt, wobei der vordere Teil zurückgegeben wird und der verbleibende Teil im Bin bleibt.

Beispiel:

• Sie reservieren 300 Bytes (a), dann 250 Bytes (b), geben a frei und fordern erneut 250 Bytes (c) an.
• Wenn Sie a freigeben, gelangt es in den unsortierten Bin.
• Wenn Sie dann erneut 250 Bytes anfordern, findet der Allokator a am Schwanz und teilt es auf, wobei der Teil zurückgegeben wird, der Ihrer Anfrage entspricht, und der Rest im Bin bleibt.
• c wird auf das vorherige a zeigen und mit den a's gefüllt sein.

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

Fastbins

Fastbins werden für kleine Speicherstücke verwendet. Im Gegensatz zu unsortierten Bins fügen Fastbins neue Stücke am Kopf hinzu, was ein Last-in-First-out (LIFO) Verhalten erzeugt. Wenn Sie ein kleines Speicherstück anfordern, zieht der Allocator vom Kopf des Fastbins.

Beispiel:

• Sie allokieren vier Stücke von jeweils 20 Bytes (a, b, c, d).
• Wenn Sie sie in beliebiger Reihenfolge freigeben, werden die freigegebenen Stücke am Kopf des Fastbins hinzugefügt.
• Wenn Sie dann ein 20-Byte-Stück anfordern, gibt der Allocator das zuletzt freigegebene Stück vom Kopf des Fastbins zurück.

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

Weitere Referenzen & Beispiele

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: Erzeuge ein Benutzerobjekt, gib es frei, erzeuge ein Objekt, das den freigegebenen Chunk erhält und schreibe darauf, überschreibe die Position von user->password vom vorherigen. Wiederverwende den Benutzer, um die Passwortüberprüfung zu umgehen.
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Das Programm erlaubt das Erstellen von Notizen. Eine Notiz hat die Notizinformationen in einem malloc(8) (mit einem Zeiger auf eine Funktion, die aufgerufen werden könnte) und einen Zeiger auf ein anderes malloc(<size>) mit dem Inhalt der Notiz.
• Der Angriff besteht darin, 2 Notizen (note0 und note1) mit größeren malloc-Inhalten als der Notizinfo-Größe zu erstellen und sie dann freizugeben, damit sie in den Fast Bin (oder tcache) gelangen.
• Erstelle dann eine weitere Notiz (note2) mit einer Inhaltsgröße von 8. Der Inhalt wird in note1 sein, da der Chunk wiederverwendet wird, wo wir den Funktionszeiger ändern könnten, um auf die Gewinnfunktion zu zeigen und dann Use-After-Free für note1 zu verwenden, um den neuen Funktionszeiger aufzurufen.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Es ist möglich, etwas Speicher zu allocieren, den gewünschten Wert zu schreiben, ihn freizugeben, ihn erneut zu allocieren und da die vorherigen Daten noch vorhanden sind, wird er gemäß der neuen erwarteten Struktur im Chunk behandelt, was es ermöglicht, den Wert zu setzen, um das Flag zu erhalten.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• In diesem Fall ist es notwendig, 4 in einen bestimmten Chunk zu schreiben, der der erste ist, der allociert wird (auch nachdem alle zwangsweise freigegeben wurden). Bei jedem neu allocierten Chunk wird seine Nummer im Array-Index gespeichert. Dann, allociere 4 Chunks (+ den ursprünglich allocierten), der letzte wird 4 enthalten, gib sie frei und erzwinge die Neuallokation des ersten, der den letzten freigegebenen Chunk verwenden wird, der den 4 enthält.