Japanese - Ht

Libc Heap

ヒープの基礎

ヒープは、プログラムが**malloc、callocなどの関数を呼び出してデータを要求するときにデータを格納できる場所です。さらに、このメモリが不要になった場合は、free** 関数を呼び出すことで利用可能になります。

バイナリがメモリにロードされる直後に表示されるように、ヒープはその後に配置されています（[heap] セクションを確認）:

チャンクの基本的な割り当て

ヒープにデータを格納するよう要求されると、ヒープの一部がそれに割り当てられます。このスペースはビンに属し、要求されたデータ + ビンヘッダのスペース + 最小ビンサイズオフセットだけがチャンクのために予約されます。目標は、各チャンクの場所を見つけるのが複雑にならないように、可能な限り最小限のメモリを予約することです。そのために、メタデータチャンク情報が使用され、どこに使用中/空きのチャンクがあるかを知るために使用されます。

使用されるビンによって主に異なるスペースの予約方法がありますが、一般的な方法論は次のとおりです:

  • プログラムは一定量のメモリを要求して開始します。

  • チャンクのリストに要求を満たすのに十分な大きさの空きがあれば、それが使用されます。

  • これは、利用可能なチャンクの一部がこの要求に使用され、残りがチャンクリストに追加されることさえ意味するかもしれません。

  • リストに利用可能なチャンクがない場合でも、割り当てられたヒープメモリにはまだスペースがある場合、ヒープマネージャは新しいチャンクを作成します。

  • 新しいチャンクを割り当てるためのヒープスペースが十分でない場合、ヒープマネージャはカーネルにヒープに割り当てられたメモリを拡張するように要求し、そのメモリを使用して新しいチャンクを生成します。

  • すべてが失敗した場合、malloc は null を返します。

要求されたメモリがしきい値を超える場合は、要求されたメモリをマップするために mmap が使用されることに注意してください。

アリーナ

マルチスレッドアプリケーションでは、ヒープマネージャはクラッシュにつながる可能性のある競合状態を防止する必要があります。最初は、グローバルミューテックスを使用して、一度に1つのスレッドだけがヒープにアクセスできるようにすることでこれを行っていましたが、これによりパフォーマンスの問題が発生しました。

これを解決するために、ptmalloc2ヒープアロケータは「アリーナ」を導入しました。ここでは、各アリーナが独自のデータ構造とミューテックスを持つ別々のヒープとして機能し、異なるアリーナを使用すれば複数のスレッドが互いに干渉せずにヒープ操作を実行できます。

デフォルトの「メイン」アリーナは、単一スレッドアプリケーションのためにヒープ操作を処理します。新しいスレッドが追加されると、ヒープマネージャはセカンダリアリーナを割り当てて競合を減らします。まず、新しいスレッドを未使用のアリーナに割り当てようとし、必要に応じて新しいアリーナを作成し、32ビットシステムではCPUコア数の2倍まで、64ビットシステムでは8倍までの制限まで新しいスレッドをアタッチしようとします。制限に達すると、スレッドはアリーナを共有する必要があり、競合が発生する可能性があります。

メインアリーナがbrkシステムコールを使用して拡張するのに対し、セカンダリアリーナはmmapとmprotectを使用して「サブヒープ」を作成し、ヒープの動作をシミュレートしてメモリをマルチスレッド操作のために柔軟に管理します。

サブヒープ

サブヒープは、マルチスレッドアプリケーションのセカンダリアリーナにとってメモリリザーブとして機能し、メインヒープとは異なるヒープ領域を独自に成長および管理できます。以下は、サブヒープが初期ヒープとどのように異なり、どのように動作するかです:

  1. 初期ヒープとサブヒープ:

  • 初期ヒープはプログラムのバイナリの直後に配置され、sbrkシステムコールを使用して拡張されます。

  • セカンダリアリーナで使用されるサブヒープは、指定されたメモリ領域をマップするmmapを介して作成されます。

  1. mmapを使用したメモリリザーブ:

  • ヒープマネージャがサブヒープを作成すると、mmapを介して大きなメモリブロックを予約します。この予約はメモリを即座に割り当てるのではなく、他のシステムプロセスや割り当てが使用しない領域を単に指定します。

  • デフォルトでは、32ビットプロセスのサブヒープの予約サイズは1 MB、64ビットプロセスの場合は64 MBです。

  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];` には、小さな、大きな、未整列の**bins**の最初と最後のチャンクへの**ポインタ**が含まれています（-2はインデックス0が使用されていないためです）
* したがって、これらのbinsの**最初のチャンク**には、この構造体への**逆ポインタ**があり、これらのbinsの**最後のチャンク**には、この構造体への**前方ポインタ**があります。つまり、メインアリーナでこれらのアドレスを**リーク**できれば、**libc**内の構造体へのポインタを取得できます。
* 構造体`struct malloc_state *next;` と `struct malloc_state *next_free;` はアリーナのリンクリストです
* `top`チャンクは最後の「チャンク」であり、基本的に**ヒープの残りのスペース全体**です。`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;

以前にコメントされたように、これらのチャンクにはメタデータも含まれており、この画像で非常によく表現されています：

メタデータは通常、現在のチャンクサイズを示す0x08Bであり、最後の3ビットを使用して次のように示されます：

  • A：1の場合、サブヒープから来ている。0の場合、メインアリーナにある。

  • M：1の場合、このチャンクはmmapで割り当てられたスペースの一部であり、ヒープの一部ではない。

  • P：1の場合、前のチャンクが使用中である。

その後、ユーザーデータのスペース、最後に、チャンクが利用可能な場合は前のチャンクサイズを示すために0x08Bがあります（または割り当てられている場合はユーザーデータを格納するため）。

さらに、利用可能な場合、ユーザーデータはいくつかのデータも含んでいます：

  • fd：次のチャンクへのポインタ

  • bk：前のチャンクへのポインタ

  • fd_nextsize：自分よりも小さい最初のチャンクへのポインタ

  • bk_nextsize：自分よりも大きいリスト内の最初のチャンクへのポインタ

リストをこの方法でリンクすることで、すべてのチャンクが登録されている配列を持つ必要がなくなることに注目してください。

チャンクポインタ

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

チャンクデータを取得してメタデータを変更する

これらの関数は、チャンクへのポインタを受け取り、メタデータをチェック/設定するのに役立ちます：

  • チャンクのフラグをチェック

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

  • ビットの継続

/* 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");
}

main 関数の最後にブレークポイントを設定し、情報が格納されている場所を見つけましょう：

0xaaaaaaac12a0 に文字列 panda が格納されていることがわかります（これは x0 内の malloc によって返されたアドレスでした）。その前の 0x10 バイトをチェックすると、0x0 が 前のチャンクが使用されていないこと（長さ 0）を表し、このチャンクの長さが 0x21 であることがわかります。

追加されたヘッダー（0x10）から来る余分なスペース（0x21-0x10=0x11）は、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).png" alt=""><figcaption></figcaption></figure>

その後、最初のスレッド、つまりmallocを呼び出すスレッドを呼び出した後、新しいアリーナが作成されます：

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

そしてその中にいくつかのチャンクが見つかります：

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

## Bins & Memory Allocations/Frees

どのようにビンが構成され、メモリが割り当てられ、解放されるかを確認する：

<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

ヒープに関与する関数は、そのアクションを実行する前にヒープが破損していないかを確認するために、特定のチェックを実行します：

<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/)
PreviousFormat Strings TemplateNextBins & Memory Allocations

Last updated