Bins & Memory Allocations

Reading time: 21 minutes

tip

Ucz się i ćwicz AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Ucz się i ćwicz GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Wsparcie HackTricks

Podstawowe informacje

Aby poprawić efektywność przechowywania kawałków, każdy kawałek nie znajduje się tylko w jednej liście powiązanej, ale istnieje kilka typów. Są to pojemniki i jest 5 typów pojemników: 62 małych pojemników, 63 dużych pojemników, 1 nieposortowany pojemnik, 10 szybkich pojemników i 64 pojemniki tcache na wątek.

Początkowy adres każdego nieposortowanego, małego i dużego pojemnika znajduje się w tej samej tablicy. Indeks 0 jest nieużywany, 1 to nieposortowany pojemnik, pojemniki 2-64 to małe pojemniki, a pojemniki 65-127 to duże pojemniki.

Pojemniki Tcache (Cache na wątek)

Mimo że wątki starają się mieć własny sterta (zobacz Arenas i Subheaps), istnieje możliwość, że proces z dużą liczbą wątków (jak serwer WWW) będzie dzielić stertę z innymi wątkami. W takim przypadku głównym rozwiązaniem jest użycie blokad, które mogą znacznie spowolnić wątki.

Dlatego tcache jest podobny do szybkiego pojemnika na wątek w tym, że jest to pojedyncza lista powiązana, która nie łączy kawałków. Każdy wątek ma 64 pojedynczo powiązane pojemniki tcache. Każdy pojemnik może mieć maksymalnie 7 kawałków tej samej wielkości w zakresie od 24 do 1032B na systemach 64-bitowych i od 12 do 516B na systemach 32-bitowych.

Kiedy wątek zwalnia kawałek, jeśli nie jest zbyt duży, aby można go było przydzielić w tcache, a odpowiedni pojemnik tcache nie jest pełny (już 7 kawałków), zostanie przydzielony tam. Jeśli nie może trafić do tcache, będzie musiał poczekać na blokadę sterty, aby móc wykonać operację zwolnienia globalnie.

Kiedy kawałek jest przydzielany, jeśli istnieje wolny kawałek o potrzebnym rozmiarze w Tcache, zostanie użyty, jeśli nie, będzie musiał poczekać na blokadę sterty, aby móc znaleźć jeden w globalnych pojemnikach lub stworzyć nowy.
Istnieje również optymalizacja, w tym przypadku, mając blokadę sterty, wątek napełni swoje Tcache kawałkami sterty (7) o żądanym rozmiarze, więc w przypadku potrzeby więcej, znajdzie je w Tcache.

Dodaj przykład kawałka tcache
c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunk;
chunk = malloc(24);
printf("Address of the chunk: %p\n", (void *)chunk);
gets(chunk);
free(chunk);
return 0;
}

Skompiluj to i zdebuguj z punktem przerwania w opcode ret z funkcji main. Następnie z gef możesz zobaczyć używaną bin tcache:

bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=1] ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

Struktury i funkcje Tcache

W poniższym kodzie można zobaczyć max bins i chunks per index, strukturę tcache_entry stworzoną w celu uniknięcia podwójnych zwolnień oraz tcache_perthread_struct, strukturę, którą każdy wątek używa do przechowywania adresów do każdego indeksu kosza.

tcache_entry i tcache_perthread_struct
c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c

/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_MAX_BINS		64
# define MAX_TCACHE_SIZE	tidx2usize (TCACHE_MAX_BINS-1)

/* Only used to pre-fill the tunables.  */
# define tidx2usize(idx)	(((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

/* When "x" is from chunksize().  */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
/* When "x" is a user-provided size.  */
# define usize2tidx(x) csize2tidx (request2size (x))

/* With rounding and alignment, the bins are...
idx 0   bytes 0..24 (64-bit) or 0..12 (32-bit)
idx 1   bytes 25..40 or 13..20
idx 2   bytes 41..56 or 21..28
etc.  */

/* This is another arbitrary limit, which tunables can change.  Each
tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 7

/* Maximum chunks in tcache bins for tunables.  This value must fit the range
of tcache->counts[] entries, else they may overflow.  */
# define MAX_TCACHE_COUNT UINT16_MAX

[...]

typedef struct tcache_entry
{
struct tcache_entry *next;
/* This field exists to detect double frees.  */
uintptr_t key;
} tcache_entry;

/* There is one of these for each thread, which contains the
per-thread cache (hence "tcache_perthread_struct").  Keeping
overall size low is mildly important.  Note that COUNTS and ENTRIES
are redundant (we could have just counted the linked list each
time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
uint16_t counts[TCACHE_MAX_BINS];
tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

Funkcja __tcache_init to funkcja, która tworzy i przydziela miejsce dla obiektu tcache_perthread_struct.

kod tcache_init
c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3241C1-L3274C2

static void
tcache_init(void)
{
mstate ar_ptr;
void *victim = 0;
const size_t bytes = sizeof (tcache_perthread_struct);

if (tcache_shutting_down)
return;

arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
if (!victim && ar_ptr != NULL)
{
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}


if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);

/* In a low memory situation, we may not be able to allocate memory
- in which case, we just keep trying later.  However, we
typically do this very early, so either there is sufficient
memory, or there isn't enough memory to do non-trivial
allocations anyway.  */
if (victim)
{
tcache = (tcache_perthread_struct *) victim;
memset (tcache, 0, sizeof (tcache_perthread_struct));
}

}

Indeksy Tcache

Tcache ma kilka pojemników w zależności od rozmiaru, a początkowe wskaźniki do pierwszego kawałka każdego indeksu oraz ilość kawałków na indeks znajdują się wewnątrz kawałka. Oznacza to, że lokalizując kawałek z tymi informacjami (zwykle pierwszym), można znaleźć wszystkie początkowe punkty tcache oraz ilość kawałków Tcache.

Szybkie pojemniki

Szybkie pojemniki są zaprojektowane, aby przyspieszyć alokację pamięci dla małych kawałków poprzez przechowywanie niedawno zwolnionych kawałków w strukturze szybkiego dostępu. Te pojemniki używają podejścia Last-In, First-Out (LIFO), co oznacza, że najbardziej niedawno zwolniony kawałek jest pierwszym, który zostanie ponownie użyty, gdy pojawi się nowe żądanie alokacji. To zachowanie jest korzystne dla szybkości, ponieważ szybciej jest wstawiać i usuwać z góry stosu (LIFO) w porównaniu do kolejki (FIFO).

Dodatkowo, szybkie pojemniki używają pojedynczo powiązanych list, a nie podwójnie powiązanych, co dodatkowo poprawia szybkość. Ponieważ kawałki w szybkich pojemnikach nie są łączone z sąsiadami, nie ma potrzeby skomplikowanej struktury, która pozwalałaby na usuwanie z środka. Pojedynczo powiązana lista jest prostsza i szybsza dla tych operacji.

W zasadzie, co się tutaj dzieje, to to, że nagłówek (wskaźnik do pierwszego kawałka do sprawdzenia) zawsze wskazuje na ostatnio zwolniony kawałek tego rozmiaru. Więc:

  • Gdy nowy kawałek jest alokowany tego rozmiaru, nagłówek wskazuje na wolny kawałek do użycia. Ponieważ ten wolny kawałek wskazuje na następny do użycia, ten adres jest przechowywany w nagłówku, aby następna alokacja wiedziała, skąd wziąć dostępny kawałek
  • Gdy kawałek jest zwalniany, wolny kawałek zapisze adres do aktualnie dostępnego kawałka, a adres do tego nowo zwolnionego kawałka zostanie umieszczony w nagłówku

Maksymalny rozmiar listy powiązanej wynosi 0x80 i są one zorganizowane tak, że kawałek o rozmiarze 0x20 będzie w indeksie 0, kawałek o rozmiarze 0x30 będzie w indeksie 1...

ostrzeżenie

Kawałki w szybkich pojemnikach nie są ustawione jako dostępne, więc są utrzymywane jako kawałki szybkich pojemników przez pewien czas, zamiast móc łączyć się z innymi wolnymi kawałkami je otaczającymi.

c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Fastbins

An array of lists holding recently freed small chunks.  Fastbins
are not doubly linked.  It is faster to single-link them, and
since chunks are never removed from the middles of these lists,
double linking is not necessary. Also, unlike regular bins, they
are not even processed in FIFO order (they use faster LIFO) since
ordering doesn't much matter in the transient contexts in which
fastbins are normally used.

Chunks in fastbins keep their inuse bit set, so they cannot
be consolidated with other free chunks. malloc_consolidate
releases all chunks in fastbins and consolidates them with
other free chunks.
*/

typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
Dodaj przykład kawałka fastbin
c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunks[8];
int i;

// Loop to allocate memory 8 times
for (i = 0; i < 8; i++) {
chunks[i] = malloc(24);
if (chunks[i] == NULL) { // Check if malloc failed
fprintf(stderr, "Memory allocation failed at iteration %d\n", i);
return 1;
}
printf("Address of chunk %d: %p\n", i, (void *)chunks[i]);
}

// Loop to free the allocated memory
for (i = 0; i < 8; i++) {
free(chunks[i]);
}

return 0;
}

Zauważ, jak alokujemy i zwalniamy 8 kawałków tej samej wielkości, aby wypełniły tcache, a ósmy jest przechowywany w szybkim kawałku.

Skompiluj to i zdebuguj z punktem przerwania w opcode ret funkcji main. Następnie z gef możesz zobaczyć, że kosz tcache jest pełny, a jeden kawałek znajduje się w szybkim koszu:

bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=7] ←  Chunk(addr=0xaaaaaaac1770, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1750, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1730, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1710, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac16f0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac16d0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0xaaaaaaac1790, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
Fastbins[idx=1, size=0x30] 0x00

Niesortowany kosz

Niesortowany kosz to cache używany przez menedżera pamięci do szybszego przydzielania pamięci. Oto jak to działa: Kiedy program zwalnia kawałek pamięci, a ten kawałek nie może być przydzielony w tcache lub szybkim koszu i nie koliduje z górnym kawałkiem, menedżer pamięci nie umieszcza go od razu w konkretnym małym lub dużym koszu. Zamiast tego najpierw próbuje połączyć go z sąsiednimi wolnymi kawałkami, aby stworzyć większy blok wolnej pamięci. Następnie umieszcza ten nowy kawałek w ogólnym koszu zwanym "niesortowanym koszem."

Kiedy program prosi o pamięć, menedżer pamięci sprawdza niesortowany kosz, aby zobaczyć, czy jest kawałek o wystarczającej wielkości. Jeśli znajdzie taki kawałek, używa go od razu. Jeśli nie znajdzie odpowiedniego kawałka w niesortowanym koszu, przenosi wszystkie kawałki z tej listy do ich odpowiednich koszy, małych lub dużych, w zależności od ich rozmiaru.

Należy zauważyć, że jeśli większy kawałek zostanie podzielony na 2 części, a reszta jest większa niż MINSIZE, zostanie umieszczona z powrotem do niesortowanego kosza.

Tak więc, niesortowany kosz to sposób na przyspieszenie przydzielania pamięci poprzez szybkie ponowne wykorzystanie niedawno zwolnionej pamięci i zmniejszenie potrzeby czasochłonnych wyszukiwań i łączeń.

ostrzeżenie

Należy zauważyć, że nawet jeśli kawałki są różnych kategorii, jeśli dostępny kawałek koliduje z innym dostępnym kawałkiem (nawet jeśli pierwotnie należą do różnych koszy), zostaną połączone.

Dodaj przykład niesortowanego kawałka
c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunks[9];
int i;

// Loop to allocate memory 8 times
for (i = 0; i < 9; i++) {
chunks[i] = malloc(0x100);
if (chunks[i] == NULL) { // Check if malloc failed
fprintf(stderr, "Memory allocation failed at iteration %d\n", i);
return 1;
}
printf("Address of chunk %d: %p\n", i, (void *)chunks[i]);
}

// Loop to free the allocated memory
for (i = 0; i < 8; i++) {
free(chunks[i]);
}

return 0;
}

Zauważ, jak alokujemy i zwalniamy 9 kawałków tej samej wielkości, aby wypełnić tcache, a ósmy jest przechowywany w niesortowanym binie, ponieważ jest za duży dla fastbin, a dziewiąty nie jest zwolniony, więc dziewiąty i ósmy nie są scalane z górnym kawałkiem.

Skompiluj to i zdebuguj z punktem przerwania w opcode ret z funkcji main. Następnie z gef możesz zobaczyć, że bin tcache jest pełny, a jeden kawałek znajduje się w niesortowanym binie:

bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ←  Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] unsorted_bins[0]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→   Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in unsorted bin.

Małe Biny

Małe biny są szybsze niż duże biny, ale wolniejsze niż szybkie biny.

Każdy bin z 62 będzie miał kawałki tej samej wielkości: 16, 24, ... (z maksymalnym rozmiarem 504 bajtów w 32 bitach i 1024 w 64 bitach). Pomaga to w szybkości znajdowania binu, w którym powinno być przydzielone miejsce, oraz w dodawaniu i usuwaniu wpisów z tych list.

Tak oblicza się rozmiar małego binu w zależności od indeksu binu:

  • Najmniejszy rozmiar: 2*4*indeks (np. indeks 5 -> 40)
  • Największy rozmiar: 2*8*indeks (np. indeks 5 -> 80)
c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > CHUNK_HDR_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)

Funkcja do wyboru między małymi a dużymi pojemnikami:

c
#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
Dodaj mały przykład kawałka
c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunks[10];
int i;

// Loop to allocate memory 8 times
for (i = 0; i < 9; i++) {
chunks[i] = malloc(0x100);
if (chunks[i] == NULL) { // Check if malloc failed
fprintf(stderr, "Memory allocation failed at iteration %d\n", i);
return 1;
}
printf("Address of chunk %d: %p\n", i, (void *)chunks[i]);
}

// Loop to free the allocated memory
for (i = 0; i < 8; i++) {
free(chunks[i]);
}

chunks[9] = malloc(0x110);

return 0;
}

Zauważ, jak alokujemy i zwalniamy 9 kawałków tej samej wielkości, aby wypełnić tcache, a ósmy jest przechowywany w niesortowanym binie, ponieważ jest za duży dla fastbina, a dziewiąty nie jest zwolniony, więc dziewiąty i ósmy nie są scalane z górnym kawałkiem. Następnie alokujemy większy kawałek o rozmiarze 0x110, co powoduje, że kawałek w niesortowanym binie trafia do małego binu.

Skompiluj to i debuguj z punktem przerwania w opcode ret z funkcji main. Następnie z gef możesz zobaczyć, że bin tcache jest pełny, a jeden kawałek znajduje się w małym binie:

bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ←  Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] small_bins[16]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→   Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 small non-empty bins.

Duże pojemniki

W przeciwieństwie do małych pojemników, które zarządzają kawałkami o stałych rozmiarach, każdy duży pojemnik obsługuje zakres rozmiarów kawałków. To jest bardziej elastyczne, pozwalając systemowi na dostosowanie się do różnych rozmiarów bez potrzeby posiadania osobnego pojemnika dla każdego rozmiaru.

W alokatorze pamięci, duże pojemniki zaczynają się tam, gdzie kończą się małe pojemniki. Zakresy dla dużych pojemników rosną stopniowo, co oznacza, że pierwszy pojemnik może obejmować kawałki od 512 do 576 bajtów, podczas gdy następny obejmuje od 576 do 640 bajtów. Ten wzór się powtarza, a największy pojemnik zawiera wszystkie kawałki powyżej 1MB.

Duże pojemniki działają wolniej w porównaniu do małych pojemników, ponieważ muszą sortować i przeszukiwać listę kawałków o różnych rozmiarach, aby znaleźć najlepsze dopasowanie do alokacji. Gdy kawałek jest wstawiany do dużego pojemnika, musi być posortowany, a gdy pamięć jest alokowana, system musi znaleźć odpowiedni kawałek. Ta dodatkowa praca sprawia, że są wolniejsze, ale ponieważ duże alokacje są mniej powszechne niż małe, jest to akceptowalny kompromis.

Są:

  • 32 pojemniki o zakresie 64B (kolidują z małymi pojemnikami)
  • 16 pojemników o zakresie 512B (kolidują z małymi pojemnikami)
  • 8 pojemników o zakresie 4096B (częściowo kolidują z małymi pojemnikami)
  • 4 pojemniki o zakresie 32768B
  • 2 pojemniki o zakresie 262144B
  • 1 pojemnik dla pozostałych rozmiarów
Kod rozmiarów dużych pojemników
c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

#define largebin_index_32(sz)                                                \
(((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)

#define largebin_index_32_big(sz)                                            \
(((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)

// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz)                                                \
(((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)

#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
: MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
: largebin_index_32 (sz))
Dodaj przykład dużego fragmentu
c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunks[2];

chunks[0] = malloc(0x1500);
chunks[1] = malloc(0x1500);
free(chunks[0]);
chunks[0] = malloc(0x2000);

return 0;
}

2 duże alokacje są wykonywane, następnie jedna jest zwalniana (umieszczając ją w nieposortowanej binie), a następnie dokonywana jest większa alokacja (przenosząc zwolnioną z nieposortowanej biny do dużej biny).

Skompiluj to i zdebuguj z punktem przerwania w opcode ret z funkcji main. Następnie z gef możesz zobaczyć, że bin tcache jest pełny, a jeden kawałek znajduje się w dużej binie:

bash
gef➤  heap bin
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
All tcachebins are empty
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
──────────────────────────────────────────────────────────────────────── Large Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] large_bins[100]: fw=0xaaaaaaac1290, bk=0xaaaaaaac1290
→   Chunk(addr=0xaaaaaaac12a0, size=0x1510, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 large non-empty bins.

Górny kawałek

c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Top

The top-most available chunk (i.e., the one bordering the end of
available memory) is treated specially. It is never included in
any bin, is used only if no other chunk is available, and is
released back to the system if it is very large (see
M_TRIM_THRESHOLD).  Because top initially
points to its own bin with initial zero size, thus forcing
extension on the first malloc request, we avoid having any special
code in malloc to check whether it even exists yet. But we still
need to do so when getting memory from system, so we make
initial_top treat the bin as a legal but unusable chunk during the
interval between initialization and the first call to
sysmalloc. (This is somewhat delicate, since it relies on
the 2 preceding words to be zero during this interval as well.)
*/

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

Zasadniczo, jest to kawałek zawierający wszystkie obecnie dostępne sterty. Gdy wykonywana jest operacja malloc, jeśli nie ma dostępnego wolnego kawałka do użycia, ten górny kawałek zmniejszy swój rozmiar, aby dać potrzebną przestrzeń.
Wskaźnik do Górnego Kawałka jest przechowywany w strukturze malloc_state.

Ponadto, na początku możliwe jest użycie nieposortowanego kawałka jako górnego kawałka.

Obserwuj przykład Górnego Kawałka
c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunk;
chunk = malloc(24);
printf("Address of the chunk: %p\n", (void *)chunk);
gets(chunk);
return 0;
}

Po skompilowaniu i zdebuggowaniu go z punktem przerwania w opcode ret funkcji main zobaczyłem, że malloc zwrócił adres 0xaaaaaaac12a0, a oto kawałki:

bash
gef➤  heap chunks
Chunk(addr=0xaaaaaaac1010, size=0x290, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac1010     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12a0     41 41 41 41 41 41 41 00 00 00 00 00 00 00 00 00    AAAAAAA.........]
Chunk(addr=0xaaaaaaac12c0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12c0     41 64 64 72 65 73 73 20 6f 66 20 74 68 65 20 63    Address of the c]
Chunk(addr=0xaaaaaaac16d0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac16d0     41 41 41 41 41 41 41 0a 00 00 00 00 00 00 00 00    AAAAAAA.........]
Chunk(addr=0xaaaaaaac1ae0, size=0x20530, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  top chunk

Gdzie można zobaczyć, że górny kawałek znajduje się pod adresem 0xaaaaaaac1ae0. To nie jest zaskoczenie, ponieważ ostatnio przydzielony kawałek znajdował się w 0xaaaaaaac12a0 o rozmiarze 0x410, a 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0.
Można również zobaczyć długość górnego kawałka w jego nagłówku kawałka:

bash
gef➤  x/8wx 0xaaaaaaac1ae0 - 16
0xaaaaaaac1ad0:	0x00000000	0x00000000	0x00020531	0x00000000
0xaaaaaaac1ae0:	0x00000000	0x00000000	0x00000000	0x00000000

Ostatni Pozostały

Gdy używana jest funkcja malloc i kawałek jest dzielony (na przykład z nieposortowanej biny lub z górnego kawałka), kawałek utworzony z reszty podzielonego kawałka nazywany jest Ostatnim Pozostałym, a jego wskaźnik jest przechowywany w strukturze malloc_state.

Przepływ Alokacji

Sprawdź:

{{#ref}} heap-memory-functions/malloc-and-sysmalloc.md {{#endref}}

Przepływ Zwolnienia

Sprawdź:

{{#ref}} heap-memory-functions/free.md {{#endref}}

Kontrole Bezpieczeństwa Funkcji Stosu

Sprawdź kontrole bezpieczeństwa wykonywane przez często używane funkcje w stosie w:

{{#ref}} heap-memory-functions/heap-functions-security-checks.md {{#endref}}

Odniesienia

tip

Ucz się i ćwicz AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Ucz się i ćwicz GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Wsparcie HackTricks