Libc Heap

Основи Хіпу

Хіп — це, по суті, місце, де програма може зберігати дані, коли запитує дані, викликаючи функції, такі як malloc, calloc... Більше того, коли ця пам'ять більше не потрібна, вона стає доступною, викликаючи функцію free.

Як показано, це просто після того, як бінарний файл завантажується в пам'ять (перевірте розділ [heap]):

Основне Виділення Чанків

Коли запитується зберігання деяких даних у хіпі, для них виділяється певний обсяг хіпу. Цей обсяг буде належати біну, і лише запитані дані + простір заголовків біну + мінімальний зсув розміру біну будуть зарезервовані для чанка. Мета полягає в тому, щоб зарезервувати якомога менше пам'яті, не ускладнюючи пошук, де знаходиться кожен чанк. Для цього використовується інформація про метадані чанка, щоб знати, де знаходиться кожен використаний/вільний чанк.

Існують різні способи резервування простору, в основному залежно від використаного біна, але загальна методологія є такою:

• Програма починає з запиту певної кількості пам'яті.

• Якщо в списку чанків є доступний, достатньо великий, щоб задовольнити запит, він буде використаний.

• Це може навіть означати, що частина доступного чанка буде використана для цього запиту, а решта буде додана до списку чанків.

• Якщо в списку немає доступного чанка, але в виділеній пам'яті хіпу ще є місце, менеджер хіпу створює новий чанк.

• Якщо недостатньо місця в хіпі для виділення нового чанка, менеджер хіпу запитує у ядра розширити пам'ять, виділену для хіпу, а потім використовує цю пам'ять для створення нового чанка.

• Якщо все не вдається, malloc повертає null.

Зверніть увагу, що якщо запитувана пам'ять перевищує поріг, mmap буде використано для відображення запитуваної пам'яті.

Арени

У багатопотокових додатках менеджер хіпу повинен запобігати умовам гонки, які можуть призвести до збоїв. Спочатку це робилося за допомогою глобального м'ютекса, щоб забезпечити доступ лише одного потоку до хіпу в один момент часу, але це викликало проблеми з продуктивністю через вузьке місце, викликане м'ютексом.

Щоб вирішити цю проблему, аллокатор хіпу ptmalloc2 ввів "арени", де кожна арена діє як окремий хіп зі своїми власними структурами даних та м'ютексом, що дозволяє кільком потокам виконувати операції з хіпом без перешкоджання один одному, якщо вони використовують різні арени.

За замовчуванням "основна" арена обробляє операції з хіпом для однопотокових додатків. Коли додаються нові потоки, менеджер хіпу призначає їм вторинні арени, щоб зменшити конкуренцію. Спочатку він намагається приєднати кожен новий потік до невикористаної арени, створюючи нові, якщо це необхідно, до межі 2 разів кількості ядер ЦП для 32-бітних систем і 8 разів для 64-бітних систем. Коли межа досягається, потоки повинні ділити арени, що може призвести до потенційної конкуренції.

На відміну від основної арени, яка розширюється за допомогою системного виклику brk, вторинні арени створюють "субхіпи" за допомогою mmap та mprotect, щоб імітувати поведінку хіпу, що дозволяє гнучко управляти пам'яттю для багатопотокових операцій.

Субхіпи

Субхіпи слугують резервами пам'яті для вторинних арен у багатопотокових додатках, дозволяючи їм рости та управляти своїми власними регіонами хіпу окремо від основного хіпу. Ось як субхіпи відрізняються від початкового хіпу та як вони працюють:

1. Початковий Хіп vs. Субхіпи:

• Початковий хіп розташований безпосередньо після бінарного файлу програми в пам'яті, і він розширюється за допомогою системного виклику sbrk.

• Субхіпи, які використовуються вторинними аренами, створюються через mmap, системний виклик, який відображає вказану область пам'яті.

1. Резервування Пам'яті з mmap:

• Коли менеджер хіпу створює субхіп, він резервує великий блок пам'яті через mmap. Це резервування не виділяє пам'ять негайно; воно просто позначає область, яку інші системні процеси або алокації не повинні використовувати.

• За замовчуванням зарезервований розмір для субхіпу становить 1 МБ для 32-бітних процесів і 64 МБ для 64-бітних процесів.

1. Поступове Розширення з mprotect:

• Зарезервована область пам'яті спочатку позначена як PROT_NONE, що вказує на те, що ядро не повинно виділяти фізичну пам'ять для цього простору поки що.

• Щоб "зрости" субхіп, менеджер хіпу використовує mprotect, щоб змінити дозволи сторінок з PROT_NONE на PROT_READ | PROT_WRITE, спонукаючи ядро виділити фізичну пам'ять для раніше зарезервованих адрес. Цей покроковий підхід дозволяє субхіпу розширюватися за потреби.

• Як тільки весь субхіп вичерпується, менеджер хіпу створює новий субхіп для продовження алокації.

heap_info

Ця структура виділяє відповідну інформацію про хіп. Більше того, пам'ять хіпу може бути не безперервною після більше алокацій, ця структура також зберігатиме цю інформацію.

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

Кожна купа (основна арена або арени інших потоків) має структуру malloc_state. Важливо зазначити, що структура malloc_state основної арени є глобальною змінною в libc (отже, розташована в пам'яті libc). У випадку **структур malloc_state куп потоків, вони розташовані всередині власної "купи" потоку.

Є кілька цікавих моментів, які варто відзначити з цієї структури (див. код C нижче):

• __libc_lock_define (, mutex); Призначена для забезпечення того, щоб ця структура з купи була доступна лише 1 потоком одночасно

• Прапори:

#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];` містить **вказівники** на **перший і останній шматки** малих, великих і неупорядкованих **бінів** (мінус 2, оскільки індекс 0 не використовується)
* Отже, **перший шматок** цих бінів матиме **зворотний вказівник на цю структуру**, а **останній шматок** цих бінів матиме **прямий вказівник** на цю структуру. Це в основному означає, що якщо ви зможете **викрити ці адреси в основній арені**, ви отримаєте вказівник на структуру в **libc**.
* Структури `struct malloc_state *next;` і `struct malloc_state *next_free;` є зв'язаними списками арен
* Шматок `top` є останнім "шматком", який в основному є **всією залишковою пам'яттю купи**. Як тільки верхній шматок "порожній", купа повністю використана, і потрібно запитати більше пам'яті.
* Шматок `last reminder` виникає в випадках, коли точний шматок не доступний, і тому більший шматок розділяється, а вказівник на залишкову частину розміщується тут.
```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

Ця структура представляє собою певний фрагмент пам'яті. Різні поля мають різне значення для виділених та невиділених фрагментів.

// 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;

Як було зазначено раніше, ці шматки також мають деякі метадані, дуже добре представлені на цьому зображенні:

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

Метадані зазвичай 0x08B, що вказує на розмір поточного шматка, використовуючи останні 3 біти для вказівки:

• A: Якщо 1, він походить з підкучі, якщо 0 - він у головній арені

• M: Якщо 1, цей шматок є частиною простору, виділеного за допомогою mmap, і не є частиною купи

• P: Якщо 1, попередній шматок використовується

Потім, простір для даних користувача, і нарешті 0x08B, щоб вказати розмір попереднього шматка, коли шматок доступний (або для зберігання даних користувача, коли він виділений).

Більше того, коли доступно, дані користувача також використовуються для зберігання деяких даних:

• fd: Вказівник на наступний шматок

• bk: Вказівник на попередній шматок

• fd_nextsize: Вказівник на перший шматок у списку, який менший за сам себе

• bk_nextsize: Вказівник на перший шматок у списку, який більший за сам себе

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

Зверніть увагу, як зв'язування списку таким чином запобігає необхідності мати масив, у якому реєструється кожен окремий шматок.

Вказівники на шматки

Коли використовується malloc, повертається вказівник на вміст, який можна записати (безпосередньо після заголовків), однак, при управлінні шматками, потрібен вказівник на початок заголовків (метаданих). Для цих перетворень використовуються ці функції:

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

Вирівнювання та мінімальний розмір

Вказівник на шматок і 0x0f повинні бути 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);
}

Зверніть увагу, що для розрахунку загального необхідного простору SIZE_SZ додається лише 1 раз, оскільки поле prev_size може використовуватися для зберігання даних, тому потрібен лише початковий заголовок.

Отримати дані про шматок і змінити метадані

Ці функції працюють, отримуючи вказівник на шматок, і корисні для перевірки/встановлення метаданих:

• Перевірити прапори шматка

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

• Розміри та вказівники на інші шматки

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

• Встановіть заголовок і нижній колонтитул (коли використовуються номери частин)

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

• Отримати розмір реальних використовуваних даних всередині блоку

#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;
}

Приклади

Швидкий приклад купи

Швидкий приклад купи з https://guyinatuxedo.github.io/25-heap/index.html, але на arm64:

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

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

Встановіть точку зупинки в кінці основної функції і давайте дізнаємося, де зберігалася інформація:

Можна побачити, що рядок panda був збережений за адресою 0xaaaaaaac12a0 (яка була адресою, наданою у відповіді malloc всередині x0). Перевіряючи 0x10 байт перед цим, можна побачити, що 0x0 представляє, що попередній шматок не використовується (довжина 0) і що довжина цього шматка становить 0x21.

Додаткові зарезервовані простори (0x21-0x10=0x11) походять від доданих заголовків (0x10), а 0x1 не означає, що було зарезервовано 0x21B, але останні 3 біти довжини поточного заголовка мають деякі спеціальні значення. Оскільки довжина завжди вирівняна на 16 байт (на 64-бітних машинах), ці біти насправді ніколи не будуть використані числом довжини.

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

Приклад багатопоточності

Багатопоточність

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

Відлагоджуючи попередній приклад, можна побачити, як на початку є лише 1 арена:

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

Потім, після виклику першого потоку, того, що викликає malloc, створюється нова арена:

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

і всередині неї можна знайти кілька шматків:

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

## Контейнери та виділення/звільнення пам'яті

Перевірте, що таке контейнери, як вони організовані та як пам'ять виділяється і звільняється в:

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

## Перевірки безпеки функцій купи

Функції, пов'язані з купою, виконуватимуть певні перевірки перед виконанням своїх дій, щоб спробувати переконатися, що купа не була пошкоджена:

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

## Посилання

* [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/)