Bins & Memory Allocations

Reading time: 23 minutes

tip

Leer & oefen AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Leer & oefen GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Ondersteun HackTricks

Basiese Inligting

Om die doeltreffendheid van hoe stukke gestoor word te verbeter, is elke stuk nie net in een gekoppelde lys nie, maar daar is verskeie tipes. Dit is die bins en daar is 5 tipes bins: 62 klein bins, 63 groot bins, 1 ongesorteerde bin, 10 vinnige bins en 64 tcache bins per draad.

Die aanvanklike adres van elke ongesorteerde, klein en groot bins is binne dieselfde array. Die indeks 0 is ongebruik, 1 is die ongesorteerde bin, bins 2-64 is klein bins en bins 65-127 is groot bins.

Tcache (Per-Draad Cache) Bins

Alhoewel drade probeer om hul eie heap te hê (sien Arenas en Subheaps), is daar die moontlikheid dat 'n proses met baie drade (soos 'n webbediener) sal eindig om die heap met ander drade te deel. In hierdie geval is die hoofoplossing die gebruik van sluiters, wat die drade aansienlik kan vertraag.

Daarom is 'n tcache soortgelyk aan 'n vinnige bin per draad op die manier dat dit 'n enkele gekoppelde lys is wat nie stukke saamvoeg nie. Elke draad het 64 enkel-gemerkte tcache bins. Elke bin kan 'n maksimum van 7 stukke van dieselfde grootte hê wat wissel van 24 tot 1032B op 64-bis stelsels en 12 tot 516B op 32-bis stelsels.

Wanneer 'n draad 'n stuk vrymaak, as dit nie te groot is om in die tcache geallokeer te word nie en die onderskeie tcache bin nie vol is nie (alreeds 7 stukke), sal dit daar geallokeer word. As dit nie na die tcache kan gaan nie, sal dit moet wag vir die heap sluiter om die vrye operasie globaal te kan uitvoer.

Wanneer 'n stuk geallokeer word, as daar 'n vrye stuk van die nodige grootte in die Tcache is, sal dit dit gebruik, as nie, sal dit moet wag vir die heap sluiter om een in die globale bins te kan vind of 'n nuwe een te skep.
Daar is ook 'n optimalisering, in hierdie geval, terwyl die heap sluiter gehou word, sal die draad sy Tcache vul met heap stukke (7) van die aangevraagde grootte, so in geval dit meer nodig het, sal dit dit in Tcache vind.

Voeg 'n tcache stuk voorbeeld by
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;
}

Compile dit en debuge dit met 'n breekpunt in die ret opcode van die hooffunksie. Dan kan jy met gef die tcache bin in gebruik sien:

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)

Tcache Strukture & Funksies

In die volgende kode is dit moontlik om die max bins en chunks per index te sien, die tcache_entry struktuur wat geskep is om dubbele vrye te vermy en tcache_perthread_struct, 'n struktuur wat elke draad gebruik om die adresse na elke indeks van die bin te stoor.

tcache_entry en 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;

Die funksie __tcache_init is die funksie wat die ruimte vir die tcache_perthread_struct objek skep en toewys.

tcache_init kode
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));
}

}

Tcache Indekse

Die tcache het verskeie bins afhangende van die grootte en die aanvanklike punte na die eerste stuk van elke indeks en die hoeveelheid stukke per indeks is binne 'n stuk geleë. Dit beteken dat dit moontlik is om die stuk met hierdie inligting (gewoonlik die eerste) te vind, wat dit moontlik maak om al die tcache aanvanklike punte en die hoeveelheid Tcache stukke te vind.

Vinige bins

Vinige bins is ontwerp om geheue-toewysing vir klein stukke te versnel deur onlangs vrygestelde stukke in 'n vinnige-toegangstruktuur te hou. Hierdie bins gebruik 'n Laaste-In, Eerste-Uit (LIFO) benadering, wat beteken dat die meest onlangs vrygestelde stuk die eerste is om hergebruik te word wanneer daar 'n nuwe toewysingsversoek is. Hierdie gedrag is voordelig vir spoed, aangesien dit vinniger is om van die bokant van 'n stapel (LIFO) in te voeg en te verwyder in vergelyking met 'n ry (FIFO).

Boonop, vinige bins gebruik enkel-gelinkte lyste, nie dubbel-gelinkte nie, wat die spoed verder verbeter. Aangesien stukke in vinige bins nie saamgevoeg word met bure nie, is daar geen behoefte aan 'n komplekse struktuur wat verwydering uit die middel toelaat nie. 'n Enkel-gelinkte lys is eenvoudiger en vinniger vir hierdie operasies.

Basies, wat hier gebeur, is dat die kop (die pointer na die eerste stuk om te kontroleer) altyd na die laaste vrygestelde stuk van daardie grootte wys. So:

  • Wanneer 'n nuwe stuk van daardie grootte toegeken word, wys die kop na 'n vrye stuk om te gebruik. Aangesien hierdie vrye stuk na die volgende een om te gebruik wys, word hierdie adres in die kop gestoor sodat die volgende toewysing weet waar om 'n beskikbare stuk te kry
  • Wanneer 'n stuk vrygestel word, sal die vrye stuk die adres na die huidige beskikbare stuk stoor en die adres na hierdie nuut vrygestelde stuk sal in die kop geplaas word

Die maksimum grootte van 'n gelinkte lys is 0x80 en hulle is georganiseer sodat 'n stuk van grootte 0x20 in indeks 0 sal wees, 'n stuk van grootte 0x30 sou in indeks 1 wees...

caution

Stukke in vinige bins is nie as beskikbaar gestel nie, so hulle word vir 'n tyd as vinige bin stukke gehou in plaas daarvan om saam te voeg met ander vrye stukke rondom hulle.

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)
Voeg 'n fastbin chunk voorbeeld by
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;
}

Let op hoe ons 8 stukke van dieselfde grootte toewys en vrymaak sodat hulle die tcache vul en die agtste een in die vinnige stuk gestoor word.

Kompileer dit en debugeer dit met 'n breekpunt in die ret opcode van die main funksie. Dan kan jy met gef sien dat die tcache bin vol is en een stuk in die vinnige bin is:

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

Ongeordende bin

Die ongeordende bin is 'n kas wat deur die heap-bestuurder gebruik word om geheue-toewysing vinniger te maak. Hier is hoe dit werk: Wanneer 'n program 'n stuk vrymaak, en as hierdie stuk nie in 'n tcache of vinnige bin toegeken kan word nie en nie met die boonste stuk bots nie, plaas die heap-bestuurder dit nie onmiddellik in 'n spesifieke klein of groot bin nie. In plaas daarvan probeer dit eers om dit saam te voeg met enige naburige vrye stukke om 'n groter blok vrye geheue te skep. Dan plaas dit hierdie nuwe stuk in 'n algemene bin genaamd die "ongeordende bin."

Wanneer 'n program vir geheue vra, kontroleer die heap-bestuurder die ongeordende bin om te sien of daar 'n stuk van genoeg grootte is. As dit een vind, gebruik dit dit onmiddellik. As dit nie 'n geskikte stuk in die ongeordende bin vind nie, beweeg dit al die stukke in hierdie lys na hul ooreenstemmende bins, hetsy klein of groot, gebaseer op hul grootte.

Let daarop dat as 'n groter stuk in 2 helfte gesplit is en die res groter is as MINSIZE, dit weer in die ongeordende bin geplaas sal word.

So, die ongeordende bin is 'n manier om geheue-toewysing te versnel deur onlangs vrygemaakte geheue vinnig te hergebruik en die behoefte aan tydrowende soektogte en saamvoegings te verminder.

caution

Let daarop dat selfs al is stukke van verskillende kategorieë, as 'n beskikbare stuk met 'n ander beskikbare stuk bots (selfs al behoort hulle oorspronklik aan verskillende bins), sal hulle saamgevoeg word.

Voeg 'n ongeordende stuk voorbeeld by
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;
}

Let op hoe ons 9 stukke van dieselfde grootte toewys en vrymaak sodat hulle die tcache vul en die agtste een in die onsortering bin gestoor word omdat dit te groot is vir die fastbin en die negende een nie vrygemaak is nie, so die negende en die agtste word nie saamgevoeg met die boonste stuk nie.

Kompileer dit en debugeer dit met 'n breekpunt in die ret opcode van die main funksie. Dan kan jy met gef sien dat die tcache bin vol is en een stuk in die onsortering bin is:

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.

Klein Bins

Klein bins is vinniger as groot bins maar stadiger as vinnige bins.

Elke bin van die 62 sal stukke van dieselfde grootte hê: 16, 24, ... (met 'n maksimum grootte van 504 bytes in 32bits en 1024 in 64bits). Dit help met die spoed om die bin te vind waar 'n spasie toegeken moet word en om inskrywings op hierdie lyste in te voeg en te verwyder.

So word die grootte van die klein bin bereken volgens die indeks van die bin:

  • Kleinste grootte: 2*4*indeks (bv. indeks 5 -> 40)
  • Grootste grootte: 2*8*indeks (bv. 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)

Funksie om tussen klein en groot bins te kies:

c
#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
Voeg 'n klein stuk voorbeeld by
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;
}

Let op hoe ons 9 stukke van dieselfde grootte toewys en vrymaak sodat hulle die tcache vul en die agtste een in die onsorteerde bin gestoor word omdat dit te groot is vir die fastbin en die negende een nie vrygemaak word nie, sodat die negende en die agtste nie met die boonste stuk saamgevoeg word nie. Dan toewys ons 'n groter stuk van 0x110 wat die stuk in die onsorteerde bin na die klein bin laat gaan.

Kompileer dit en debugeer dit met 'n breekpunt in die ret opcode van die main funksie. Dan kan jy met gef sien dat die tcache bin vol is en een stuk in die klein bin is:

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.

Grosse bins

Verskil met klein bins, wat stukke van vaste groottes bestuur, elke grosse bin hanteer 'n reeks stukgroottes. Dit is meer buigsaam, wat die stelsel in staat stel om verskeie groottes te akkommodeer sonder om 'n aparte bin vir elke grootte te benodig.

In 'n geheue-toewysingstelsel begin grosse bins waar klein bins eindig. Die reekse vir grosse bins groei progressief groter, wat beteken dat die eerste bin stukke van 512 tot 576 bytes kan dek, terwyl die volgende 576 tot 640 bytes dek. Hierdie patroon hou aan, met die grootste bin wat al die stukke bo 1MB bevat.

Grosse bins is stadiger om te werk in vergelyking met klein bins omdat hulle moet sorteer en soek deur 'n lys van verskillende stukgroottes om die beste pasvorm vir 'n toewysing te vind. Wanneer 'n stuk in 'n grosse bin ingevoeg word, moet dit gesorteer word, en wanneer geheue toegeken word, moet die stelsel die regte stuk vind. Hierdie ekstra werk maak hulle stadiger, maar aangesien groot toewysings minder algemeen is as klein, is dit 'n aanvaarbare ruil.

Daar is:

  • 32 bins van 64B reeks (bots met klein bins)
  • 16 bins van 512B reeks (bots met klein bins)
  • 8 bins van 4096B reeks (gedeeltelik bots met klein bins)
  • 4 bins van 32768B reeks
  • 2 bins van 262144B reeks
  • 1 bin vir oorblywende groottes
Grosse bin groottes kode
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))
Voeg 'n groot stuk voorbeeld toe
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 groot toewysings word uitgevoer, dan word een vrygestel (wat dit in die ongesorteerde bin plaas) en 'n groter toewysing word gemaak (wat die vrye een van die ongesorteerde bin na die groot bin beweeg).

Kompileer dit en debugeer dit met 'n breekpunt in die ret opcode van die main funksie. Dan kan jy met gef sien dat die tcache bin vol is en een stuk in die groot bin is:

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.

Top Chunk

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))

Basies, dit is 'n stuk wat al die tans beskikbare heap bevat. Wanneer 'n malloc uitgevoer word, as daar nie enige beskikbare vrye stuk is om te gebruik nie, sal hierdie top stuk sy grootte verminder om die nodige ruimte te gee.
Die pointer na die Top Chunk word in die malloc_state struktuur gestoor.

Boonop, aan die begin, is dit moontlik om die onsortering stuk as die top stuk te gebruik.

Observeer die Top Chunk voorbeeld
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;
}

Na die kompilering en debuggery daarvan met 'n breekpunt in die ret opcode van main het ek gesien dat die malloc die adres 0xaaaaaaac12a0 teruggegee het en dit is die stukke:

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

Waar dit gesien kan word dat die top chunk op adres 0xaaaaaaac1ae0 is. Dit is geen verrassing nie, want die laaste toegewyse chunk was in 0xaaaaaaac12a0 met 'n grootte van 0x410 en 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0.
Dit is ook moontlik om die lengte van die Top chunk op sy chunk header te sien:

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

Laaste Restant

Wanneer malloc gebruik word en 'n stuk verdeel word (van die ongesorteerde bin of van die boonste stuk byvoorbeeld), word die stuk wat geskep word uit die res van die verdeelde stuk Laaste Restant genoem en sy pointer word in die malloc_state struktuur gestoor.

Toewysingsvloei

Kyk na:

malloc & sysmalloc

Vryvloei

Kyk na:

free

Heap Funksies Sekuriteitskontroles

Kyk na die sekuriteitskontroles wat uitgevoer word deur baie gebruikte funksies in die heap in:

Heap Functions Security Checks

Verwysings

tip

Leer & oefen AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Leer & oefen GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Ondersteun HackTricks