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];` は**小さな、大きな、未ソートの** **ビン**の**最初と最後のチャンク**への**ポインタ**を含みます（-2はインデックス0が使用されていないためです）。
* したがって、これらのビンの**最初のチャンク**はこの構造体への**逆ポインタ**を持ち、これらのビンの**最後のチャンク**はこの構造体への**前方ポインタ**を持ちます。これは基本的に、**メインアリーナでこれらのアドレスをl**eakできれば、**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);
}

注意：必要な総スペースを計算する際、prev_size フィールドはデータを格納するために使用できるため、SIZE_SZ は1回だけ追加されることに注意してください。したがって、初期ヘッダーのみが必要です。

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

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

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

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

メイン関数の終わりにブレークポイントを設定し、情報がどこに保存されているかを見てみましょう：

文字列pandaが0xaaaaaaac12a0に保存されていることがわかります（これはx0内のmallocによって返されたアドレスです）。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).png" alt=""><figcaption></figcaption></figure>

次に、最初のスレッド、mallocを呼び出すスレッドを呼び出すと、新しいアリーナが作成されます：

<figure><img src="../../.gitbook/assets/image (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).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/)