Libc Heap

Heap Basics

Heap je u suštini mesto gde program može da skladišti podatke kada zahteva podatke pozivajući funkcije kao što su malloc, calloc... Štaviše, kada ova memorija više nije potrebna, postaje dostupna pozivajući funkciju free.

Kao što je prikazano, to je odmah nakon što se binarni fajl učita u memoriju (proverite odeljak [heap]):

Basic Chunk Allocation

Kada se zatraži skladištenje nekih podataka u heap, određeni deo heap-a se alocira za njih. Ovaj prostor će pripadati bini i samo će zatraženi podaci + prostor zaglavlja bina + minimalni offset veličine bina biti rezervisani za chunk. Cilj je da se rezerviše što manje memorije bez otežavanja pronalaženja gde se svaki chunk nalazi. Za to se koristi informacija o metapodacima chunk-a da bi se znalo gde se nalazi svaki korišćeni/slobodni chunk.

Postoje različiti načini za rezervaciju prostora, uglavnom zavisno od korišćenog bina, ali opšta metodologija je sledeća:

• Program počinje zahtevajući određenu količinu memorije.

• Ako u listi chunk-ova postoji neki dostupan dovoljno veliki da ispuni zahtev, biće korišćen.

• To može čak značiti da će deo dostupnog chunk-a biti korišćen za ovaj zahtev, a ostatak će biti dodat u listu chunk-ova.

• Ako u listi nema dostupnog chunk-a, ali još uvek ima prostora u alociranoj heap memoriji, menadžer heap-a kreira novi chunk.

• Ako nema dovoljno prostora u heap-u da se alocira novi chunk, menadžer heap-a traži od kernela da proširi memoriju alociranu za heap i zatim koristi ovu memoriju za generisanje novog chunk-a.

• Ako sve ne uspe, malloc vraća null.

Napomena: ako zatražena memorija pređe prag, mmap će biti korišćen za mapiranje zatražene memorije.

Arenas

U multithreaded aplikacijama, menadžer heap-a mora sprečiti race conditions koje bi mogle dovesti do rušenja. U početku, to je postignuto korišćenjem globalnog mutex-a kako bi se osiguralo da samo jedna nit može pristupiti heap-u u isto vreme, ali to je izazvalo probleme sa performansama zbog uskog grla izazvanog mutex-om.

Da bi se to rešilo, ptmalloc2 alokator heap-a je uveo "arene", gde svaka arena deluje kao odvojeni heap sa svojim vlastitim podacima strukture i mutex-om, omogućavajući više niti da obavljaju operacije na heap-u bez ometanja jedna druge, sve dok koriste različite arene.

Podrazumevana "glavna" arena upravlja operacijama na heap-u za aplikacije sa jednom niti. Kada se nove niti dodaju, menadžer heap-a im dodeljuje sekundarne arene kako bi smanjio sukobe. Prvo pokušava da poveže svaku novu nit sa neiskorišćenom arenom, kreirajući nove ako je potrebno, do limita od 2 puta broj CPU jezgara za 32-bitne sisteme i 8 puta za 64-bitne sisteme. Kada se dostigne limit, niti moraju deliti arene, što dovodi do potencijalnog sukoba.

Za razliku od glavne arene, koja se širi korišćenjem brk sistemskog poziva, sekundarne arene kreiraju "subheaps" koristeći mmap i mprotect kako bi simulirale ponašanje heap-a, omogućavajući fleksibilnost u upravljanju memorijom za multithreaded operacije.

Subheaps

Subheaps služe kao rezerve memorije za sekundarne arene u multithreaded aplikacijama, omogućavajući im da rastu i upravljaju svojim regionima heap-a odvojeno od glavnog heap-a. Evo kako se subheaps razlikuju od inicijalnog heap-a i kako funkcionišu:

1. Inicijalni Heap vs. Subheaps:

• Inicijalni heap se nalazi direktno nakon binarnog fajla programa u memoriji, i širi se korišćenjem sbrk sistemskog poziva.

• Subheaps, koje koriste sekundarne arene, kreiraju se putem mmap, sistemskog poziva koji mapira određeni memorijski region.

1. Rezervacija Memorije sa mmap:

• Kada menadžer heap-a kreira subheap, rezerviše veliki blok memorije putem mmap. Ova rezervacija ne alocira memoriju odmah; jednostavno označava region koji drugi sistemski procesi ili alokacije ne bi trebali koristiti.

• Podrazumevana veličina rezervisane subheap memorije je 1 MB za 32-bitne procese i 64 MB za 64-bitne procese.

1. Postepeno Širenje sa mprotect:

• Rezervisana memorijska oblast je inicijalno označena kao PROT_NONE, što ukazuje da kernel još uvek ne mora da alocira fizičku memoriju za ovaj prostor.

• Da bi "rastegao" subheap, menadžer heap-a koristi mprotect da promeni dozvole stranica sa PROT_NONE na PROT_READ | PROT_WRITE, podstičući kernel da alocira fizičku memoriju za prethodno rezervisane adrese. Ovaj postepeni pristup omogućava subheap-u da se širi po potrebi.

• Kada se ceo subheap iscrpi, menadžer heap-a kreira novi subheap kako bi nastavio alokaciju.

heap_info

Ova struktura alocira relevantne informacije o heap-u. Štaviše, heap memorija možda neće biti kontinuirana nakon više alokacija, ova struktura će takođe čuvati te informacije.

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

typedef struct _heap_info
{
mstate ar_ptr; /* Arena for this heap. */
struct _heap_info *prev; /* Previous heap. */
size_t size;   /* Current size in bytes. */
size_t mprotect_size; /* Size in bytes that has been mprotected
PROT_READ|PROT_WRITE.  */
size_t pagesize; /* Page size used when allocating the arena.  */
/* Make sure the following data is properly aligned, particularly
that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
MALLOC_ALIGNMENT. */
char pad[-3 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

malloc_state

Svaka heap (glavna arena ili druge arene niti) ima malloc_state strukturu. Važno je napomenuti da je glavna arena malloc_state struktura globalna promenljiva u libc (stoga se nalazi u libc memorijskom prostoru). U slučaju malloc_state struktura heap-ova niti, one se nalaze unutar vlastitog "heap"-a niti.

Postoje neke zanimljive stvari koje treba primetiti iz ove strukture (vidi C kod ispod):

• __libc_lock_define (, mutex); je tu da osigura da se ova struktura iz heap-a pristupa od strane 1 niti u isto vreme

• Zastavice:

#define NONCONTIGUOUS_BIT (2U)

#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0) #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0) #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT) #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)

* `mchunkptr bins[NBINS * 2 - 2];` sadrži **pokazivače** na **prvi i poslednji chunk** malih, velikih i nesortiranih **bins** ( -2 je zbog toga što se indeks 0 ne koristi)
* Stoga, **prvi chunk** ovih bins će imati **povratni pokazivač na ovu strukturu** i **poslednji chunk** ovih bins će imati **napredni pokazivač** na ovu strukturu. Što u suštini znači da ako možete l**eak-ovati ove adrese u glavnoj areni** imaćete pokazivač na strukturu u **libc**.
* Strukture `struct malloc_state *next;` i `struct malloc_state *next_free;` su povezane liste arena
* `top` chunk je poslednji "chunk", koji je u suštini **sva preostala memorija heap-a**. Kada je top chunk "prazan", heap je potpuno iskorišćen i treba da zatraži više prostora.
* `last reminder` chunk dolazi iz slučajeva kada tačno veličine chunk nije dostupna i stoga je veći chunk podeljen, a pokazivač preostalog dela se ovde postavlja.
```c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1812

struct malloc_state
{
/* Serialize access.  */
__libc_lock_define (, mutex);

/* Flags (formerly in max_fast).  */
int flags;

/* Set if the fastbin chunks contain recently inserted free blocks.  */
/* Note this is a bool but not all targets support atomics on booleans.  */
int have_fastchunks;

/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];

/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;

/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;

/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];

/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];

/* Linked list */
struct malloc_state *next;

/* Linked list for free arenas.  Access to this field is serialized
by free_list_lock in arena.c.  */
struct malloc_state *next_free;

/* Number of threads attached to this arena.  0 if the arena is on
the free list.  Access to this field is serialized by
free_list_lock in arena.c.  */
INTERNAL_SIZE_T attached_threads;

/* Memory allocated from the system in this arena.  */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};

malloc_chunk

Ova struktura predstavlja određeni deo memorije. Različita polja imaju različita značenja za alocirane i nealokirane delove.

// https://github.com/bminor/glibc/blob/master/malloc/malloc.c
struct malloc_chunk {
INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk, if it is free. */
INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
struct malloc_chunk* fd;                /* double links -- used only if this chunk is free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size.  */
struct malloc_chunk* fd_nextsize; /* double links -- used only if this chunk is free. */
struct malloc_chunk* bk_nextsize;
};

typedef struct malloc_chunk* mchunkptr;

Kao što je prethodno komentarisano, ovi delovi takođe imaju neke metapodatke, veoma dobro predstavljene na ovoj slici:

https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png

Metapodaci su obično 0x08B koji označava trenutnu veličinu dela koristeći poslednja 3 bita da označi:

• A: Ako je 1, dolazi iz podheap-a, ako je 0, u glavnoj areni je

• M: Ako je 1, ovaj deo je deo prostora dodeljenog sa mmap i nije deo heap-a

• P: Ako je 1, prethodni deo je u upotrebi

Zatim, prostor za korisničke podatke, i konačno 0x08B da označi veličinu prethodnog dela kada je deo dostupan (ili da čuva korisničke podatke kada je dodeljen).

Štaviše, kada je dostupan, korisnički podaci se koriste da sadrže i neke podatke:

• fd: Pokazivač na sledeći deo

• bk: Pokazivač na prethodni deo

• fd_nextsize: Pokazivač na prvi deo u listi koji je manji od sebe

• bk_nextsize: Pokazivač na prvi deo u listi koji je veći od sebe

https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png

Obratite pažnju kako povezivanje liste na ovaj način sprečava potrebu za imanjem niza gde se svaki pojedinačni deo registruje.

Pokazivači na delove

Kada se koristi malloc, vraća se pokazivač na sadržaj koji može biti napisan (odmah nakon zaglavlja), međutim, kada se upravlja delovima, potreban je pokazivač na početak zaglavlja (metapodaci). Za ove konverzije koriste se ove funkcije:

// https://github.com/bminor/glibc/blob/master/malloc/malloc.c

/* Convert a chunk address to a user mem pointer without correcting the tag.  */
#define chunk2mem(p) ((void*)((char*)(p) + CHUNK_HDR_SZ))

/* Convert a user mem pointer to a chunk address and extract the right tag.  */
#define mem2chunk(mem) ((mchunkptr)tag_at (((char*)(mem) - CHUNK_HDR_SZ)))

/* The smallest possible chunk */
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))

/* The smallest size we can malloc is an aligned minimal chunk */

#define MINSIZE  \
(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

Poravnanje i minimalna veličina

Pokazivač na deo i 0x0f moraju biti 0.

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/generic/malloc-size.h#L61
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

// https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/i386/malloc-alignment.h
#define MALLOC_ALIGNMENT 16


// https://github.com/bminor/glibc/blob/master/malloc/malloc.c
/* Check if m has acceptable alignment */
#define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)

#define misaligned_chunk(p) \
((uintptr_t)(MALLOC_ALIGNMENT == CHUNK_HDR_SZ ? (p) : chunk2mem (p)) \
& MALLOC_ALIGN_MASK)


/* pad request bytes into a usable size -- internal version */
/* Note: This must be a macro that evaluates to a compile time constant
if passed a literal constant.  */
#define request2size(req)                                         \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
MINSIZE :                                                      \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

/* Check if REQ overflows when padded and aligned and if the resulting
value is less than PTRDIFF_T.  Returns the requested size or
MINSIZE in case the value is less than MINSIZE, or 0 if any of the
previous checks fail.  */
static inline size_t
checked_request2size (size_t req) __nonnull (1)
{
if (__glibc_unlikely (req > PTRDIFF_MAX))
return 0;

/* When using tagged memory, we cannot share the end of the user
block with the header for the next chunk, so ensure that we
allocate blocks that are rounded up to the granule size.  Take
care not to overflow from close to MAX_SIZE_T to a small
number.  Ideally, this would be part of request2size(), but that
must be a macro that produces a compile time constant if passed
a constant literal.  */
if (__glibc_unlikely (mtag_enabled))
{
/* Ensure this is not evaluated if !mtag_enabled, see gcc PR 99551.  */
asm ("");

req = (req + (__MTAG_GRANULE_SIZE - 1)) &
~(size_t)(__MTAG_GRANULE_SIZE - 1);
}

return request2size (req);
}

Napomena da se za izračunavanje ukupnog potrebnog prostora SIZE_SZ dodaje samo jednom jer se polje prev_size može koristiti za skladištenje podataka, stoga je potrebna samo početna glava.

Dobijanje podataka o delu i izmene metapodataka

Ove funkcije rade tako što primaju pokazivač na deo i korisne su za proveru/postavljanje metapodataka:

• Proveri oznake dela

// From https://github.com/bminor/glibc/blob/master/malloc/malloc.c


/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

/* extract inuse bit of previous chunk */
#define prev_inuse(p)       ((p)->mchunk_size & PREV_INUSE)


/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2

/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)


/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
from a non-main arena.  This is only set immediately before handing
the chunk to the user, if necessary.  */
#define NON_MAIN_ARENA 0x4

/* Check for chunk from main arena.  */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)

/* Mark a chunk as not being on the main arena.  */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)

• Veličine i pokazivači na druge delove

/*
Bits to mask off when extracting size

Note: IS_MMAPPED is intentionally not masked off from size field in
macros for which mmapped chunks should never be seen. This should
cause helpful core dumps to occur if it is tried by accident by
people extending or adapting this malloc.
*/
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

/* Like chunksize, but do not mask SIZE_BITS.  */
#define chunksize_nomask(p)         ((p)->mchunk_size)

/* Ptr to next physical malloc_chunk. */
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))

/* Size of the chunk below P.  Only valid if !prev_inuse (P).  */
#define prev_size(p) ((p)->mchunk_prev_size)

/* Set the size of the chunk below P.  Only valid if !prev_inuse (P).  */
#define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))

/* Ptr to previous physical malloc_chunk.  Only valid if !prev_inuse (P).  */
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))

/* Treat space at ptr + offset as a chunk */
#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))

• Insue bit

/* extract p's inuse bit */
#define inuse(p)							      \
((((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size) & PREV_INUSE)

/* set/clear chunk as being inuse without otherwise disturbing */
#define set_inuse(p)							      \
((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size |= PREV_INUSE

#define clear_inuse(p)							      \
((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE)


/* check/set/clear inuse bits in known places */
#define inuse_bit_at_offset(p, s)					      \
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size & PREV_INUSE)

#define set_inuse_bit_at_offset(p, s)					      \
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE)

#define clear_inuse_bit_at_offset(p, s)					      \
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))

• Postavite zaglavlje i podnožje (kada se koriste chunk brojevi)

/* Set size at head, without disturbing its use bit */
#define set_head_size(p, s)  ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))

/* Set size/use field */
#define set_head(p, s)       ((p)->mchunk_size = (s))

/* Set size at footer (only when chunk is not in use) */
#define set_foot(p, s)       (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))

• Dobijte veličinu stvarnih upotrebljivih podataka unutar dela

#pragma GCC poison mchunk_size
#pragma GCC poison mchunk_prev_size

/* This is the size of the real usable data in the chunk.  Not valid for
dumped heap chunks.  */
#define memsize(p)                                                    \
(__MTAG_GRANULE_SIZE > SIZE_SZ && __glibc_unlikely (mtag_enabled) ? \
chunksize (p) - CHUNK_HDR_SZ :                                    \
chunksize (p) - CHUNK_HDR_SZ + (chunk_is_mmapped (p) ? 0 : SIZE_SZ))

/* If memory tagging is enabled the layout changes to accommodate the granule
size, this is wasteful for small allocations so not done by default.
Both the chunk header and user data has to be granule aligned.  */
_Static_assert (__MTAG_GRANULE_SIZE <= CHUNK_HDR_SZ,
"memory tagging is not supported with large granule.");

static __always_inline void *
tag_new_usable (void *ptr)
{
if (__glibc_unlikely (mtag_enabled) && ptr)
{
mchunkptr cp = mem2chunk(ptr);
ptr = __libc_mtag_tag_region (__libc_mtag_new_tag (ptr), memsize (cp));
}
return ptr;
}

Primeri

Brzi Heap Primer

Brzi heap primer sa https://guyinatuxedo.github.io/25-heap/index.html ali u arm64:

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

void main(void)
{
char *ptr;
ptr = malloc(0x10);
strcpy(ptr, "panda");
}

Postavite prekid na kraju glavne funkcije i hajde da saznamo gde je informacija sačuvana:

Moguće je videti da je string panda sačuvan na 0xaaaaaaac12a0 (što je adresa koju je vratio malloc unutar x0). Proveravajući 0x10 bajtova pre, moguće je videti da 0x0 predstavlja da prethodni deo nije korišćen (dužina 0) i da je dužina ovog dela 0x21.

Dodatni prostori rezervisani (0x21-0x10=0x11) dolaze od dodate zaglavlja (0x10) i 0x1 ne znači da je rezervisano 0x21B, već poslednja 3 bita dužine trenutnog zaglavlja imaju neka posebna značenja. Pošto je dužina uvek usklađena sa 16 bajtova (na 64-bitnim mašinama), ovi bitovi se zapravo nikada neće koristiti za broj dužine.

0x1:     Previous in Use     - Specifies that the chunk before it in memory is in use
0x2:     Is MMAPPED          - Specifies that the chunk was obtained with mmap()
0x4:     Non Main Arena      - Specifies that the chunk was obtained from outside of the main arena

Primer višedretvenosti

Višedretvenost

```c #include #include #include #include #include

void* threadFuncMalloc(void* arg) { printf("Hello from thread 1\n"); char* addr = (char*) malloc(1000); printf("After malloc and before free in thread 1\n"); free(addr); printf("After free in thread 1\n"); }

void* threadFuncNoMalloc(void* arg) { printf("Hello from thread 2\n"); }

int main() { pthread_t t1; void* s; int ret; char* addr;

printf("Before creating thread 1\n"); getchar(); ret = pthread_create(&t1, NULL, threadFuncMalloc, NULL); getchar();

printf("Before creating thread 2\n"); ret = pthread_create(&t1, NULL, threadFuncNoMalloc, NULL);

printf("Before exit\n"); getchar();

return 0; }

</details>

Debugging prethodnog primera moguće je videti kako na početku postoji samo 1 arena:

<figure><img src="../../.gitbook/assets/image (1) (1) (1) (1) (1) (1) (1) (1) (1).png" alt=""><figcaption></figcaption></figure>

Zatim, nakon pozivanja prvog threada, onog koji poziva malloc, kreira se nova arena:

<figure><img src="../../.gitbook/assets/image (1) (1) (1) (1) (1) (1) (1) (1) (1) (1).png" alt=""><figcaption></figcaption></figure>

i unutar nje mogu se naći neki chunks:

<figure><img src="../../.gitbook/assets/image (2) (1) (1) (1) (1) (1).png" alt=""><figcaption></figcaption></figure>

## Bins & Memory Allocations/Frees

Proverite koji su bins i kako su organizovani i kako se memorija alocira i oslobađa u:

<div data-gb-custom-block data-tag="content-ref" data-url='bins-and-memory-allocations.md'>

[bins-and-memory-allocations.md](bins-and-memory-allocations.md)

</div>

## Heap Functions Security Checks

Funkcije uključene u heap će izvršiti određene provere pre nego što izvrše svoje akcije kako bi pokušale da osiguraju da heap nije oštećen:

<div data-gb-custom-block data-tag="content-ref" data-url='heap-memory-functions/heap-functions-security-checks.md'>

[heap-functions-security-checks.md](heap-memory-functions/heap-functions-security-checks.md)

</div>

## References

* [https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/](https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/)
* [https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/](https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/)