힙은 기본적으로 프로그램이 malloc, calloc와 같은 함수를 호출하여 데이터를 요청할 때 데이터를 저장할 수 있는 장소입니다. 또한, 이 메모리가 더 이상 필요하지 않을 때는 free 함수를 호출하여 사용 가능하게 됩니다.
보시다시피, 이는 바이너리가 메모리에 로드된 직후에 위치합니다 ( [heap] 섹션을 확인하세요):
Basic Chunk Allocation
힙에 저장할 데이터가 요청되면, 힙의 일부 공간이 할당됩니다. 이 공간은 빈에 속하며 요청된 데이터 + 빈 헤더의 공간 + 최소 빈 크기 오프셋만큼이 청크를 위해 예약됩니다. 목표는 각 청크의 위치를 찾는 것을 복잡하게 만들지 않으면서 가능한 최소한의 메모리만 예약하는 것입니다. 이를 위해 메타데이터 청크 정보를 사용하여 사용 중인/비어 있는 청크의 위치를 알 수 있습니다.
공간을 예약하는 방법은 사용된 빈에 따라 다르지만, 일반적인 방법론은 다음과 같습니다:
프로그램은 특정 양의 메모리를 요청하는 것으로 시작합니다.
청크 목록에 요청을 충족할 수 있을 만큼 큰 사용 가능한 청크가 있다면, 그것이 사용됩니다.
이는 사용 가능한 청크의 일부가 이 요청에 사용되고 나머지가 청크 목록에 추가될 수 있음을 의미할 수 있습니다.
목록에 사용 가능한 청크가 없지만 할당된 힙 메모리에 여전히 공간이 있다면, 힙 관리자는 새로운 청크를 생성합니다.
새로운 청크를 할당할 충분한 힙 공간이 없다면, 힙 관리자는 커널에 힙에 할당된 메모리를 확장해 달라고 요청하고, 이 메모리를 사용하여 새로운 청크를 생성합니다.
모든 것이 실패하면, malloc은 null을 반환합니다.
요청된 메모리가 임계값을 초과하면, **mmap**이 요청된 메모리를 매핑하는 데 사용됩니다.
Arenas
멀티스레드 애플리케이션에서 힙 관리자는 충돌로 인한 경쟁 조건을 방지해야 합니다. 처음에는 전역 뮤텍스를 사용하여 한 번에 하나의 스레드만 힙에 접근할 수 있도록 했지만, 이는 뮤텍스에 의한 병목 현상으로 인해 성능 문제를 일으켰습니다.
이를 해결하기 위해 ptmalloc2 힙 할당자는 "아레나"를 도입했습니다. 여기서 각 아레나는 자체 데이터 구조와 뮤텍스를 가진 별도의 힙으로 작용하여, 서로 다른 아레나를 사용하는 한 여러 스레드가 힙 작업을 수행할 수 있습니다.
기본 "메인" 아레나는 단일 스레드 애플리케이션의 힙 작업을 처리합니다. 새로운 스레드가 추가되면, 힙 관리자는 경쟁을 줄이기 위해 보조 아레나를 할당합니다. 먼저 각 새로운 스레드를 사용되지 않는 아레나에 연결하려고 시도하며, 필요할 경우 새로운 아레나를 생성합니다. 32비트 시스템의 경우 CPU 코어 수의 2배, 64비트 시스템의 경우 8배까지 제한이 있습니다. 제한에 도달하면 스레드는 아레나를 공유해야 하며, 이는 잠재적인 경쟁으로 이어질 수 있습니다.
메인 아레나와 달리 brk 시스템 호출을 사용하여 확장되는 보조 아레나는 mmap 및 mprotect를 사용하여 "서브힙"을 생성하여 힙 동작을 시뮬레이션하고, 멀티스레드 작업을 위한 메모리 관리의 유연성을 제공합니다.
Subheaps
서브힙은 멀티스레드 애플리케이션에서 보조 아레나를 위한 메모리 예비 공간으로 작용하여, 메인 힙과 별도로 자신의 힙 영역을 성장시키고 관리할 수 있게 합니다. 서브힙이 초기 힙과 어떻게 다른지 및 작동 방식은 다음과 같습니다:
초기 힙 vs. 서브힙:
초기 힙은 프로그램의 바이너리 바로 뒤에 메모리에 위치하며, sbrk 시스템 호출을 사용하여 확장됩니다.
보조 아레나에서 사용되는 서브힙은 지정된 메모리 영역을 매핑하는 시스템 호출인 mmap을 통해 생성됩니다.
mmap을 통한 메모리 예약:
힙 관리자가 서브힙을 생성할 때, mmap을 통해 큰 메모리 블록을 예약합니다. 이 예약은 즉시 메모리를 할당하지 않으며, 다른 시스템 프로세스나 할당이 사용하지 않아야 할 영역을 지정하는 것입니다.
기본적으로 서브힙의 예약 크기는 32비트 프로세스의 경우 1MB, 64비트 프로세스의 경우 64MB입니다.
mprotect를 통한 점진적 확장:
예약된 메모리 영역은 처음에 PROT_NONE으로 표시되어, 커널이 이 공간에 물리적 메모리를 할당할 필요가 없음을 나타냅니다.
서브힙을 "확장"하기 위해, 힙 관리자는 mprotect를 사용하여 페이지 권한을 PROT_NONE에서 PROT_READ | PROT_WRITE로 변경하여, 커널이 이전에 예약된 주소에 물리적 메모리를 할당하도록 합니다. 이 단계별 접근 방식은 서브힙이 필요에 따라 확장될 수 있게 합니다.
서브힙이 모두 소진되면, 힙 관리자는 새로운 서브힙을 생성하여 할당을 계속합니다.
heap_info
이 구조체는 힙의 관련 정보를 할당합니다. 또한, 추가 할당 후 힙 메모리가 연속적이지 않을 수 있으며, 이 구조체는 그 정보를 저장합니다.
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/arena.c#L837typedefstruct _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 mprotectedPROT_READ|PROT_WRITE. */size_t pagesize; /* Page size used when allocating the arena. *//* Make sure the following data is properly aligned, particularlythat sizeof (heap_info) + 2 * SIZE_SZ is a multiple ofMALLOC_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개의 스레드만 접근할 수 있도록 보장하기 위해 존재합니다.
* `mchunkptr bins[NBINS * 2 - 2];`는 **작고, 큰 및 정렬되지 않은 **bins**의 **첫 번째 및 마지막 청크**에 대한 **포인터**를 포함합니다 (인덱스 0이 사용되지 않기 때문에 -2입니다).
* 따라서, 이러한 bins의 **첫 번째 청크**는 이 구조체에 대한 **역방향 포인터**를 가지며, **마지막 청크**는 이 구조체에 대한 **정방향 포인터**를 가집니다. 이는 기본적으로 **메인 아레나에서 이러한 주소를 l**eak**할 수 있다면, **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.cstruct 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;};typedefstruct 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. */#definechunk2mem(p) ((void*)((char*)(p) + CHUNK_HDR_SZ))/* Convert a user mem pointer to a chunk address and extract the right tag. */#definemem2chunk(mem) ((mchunkptr)tag_at (((char*)(mem) - CHUNK_HDR_SZ)))/* The smallest possible chunk */#defineMIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))/* The smallest size we can malloc is an aligned minimal chunk */#defineMINSIZE \(unsignedlong)(((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#defineMALLOC_ALIGN_MASK (MALLOC_ALIGNMENT -1)// https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/i386/malloc-alignment.h#defineMALLOC_ALIGNMENT16// https://github.com/bminor/glibc/blob/master/malloc/malloc.c/* Check if m has acceptable alignment */#definealigned_OK(m) (((unsignedlong)(m) & MALLOC_ALIGN_MASK) ==0)#definemisaligned_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 constantif passed a literal constant. */#definerequest2size(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 resultingvalue is less than PTRDIFF_T. Returns the requested size orMINSIZE in case the value is less than MINSIZE, or 0 if any of theprevious checks fail. */staticinlinesize_tchecked_request2size (size_t req) __nonnull (1){if (__glibc_unlikely (req > PTRDIFF_MAX))return0;/* When using tagged memory, we cannot share the end of the userblock with the header for the next chunk, so ensure that weallocate blocks that are rounded up to the granule size. Takecare not to overflow from close to MAX_SIZE_T to a smallnumber. Ideally, this would be part of request2size(), but thatmust be a macro that produces a compile time constant if passeda 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);}returnrequest2size (req);}
Note that for calculating the total space needed it's only added SIZE_SZ 1 time because the prev_size field can be used to store data, therefore only the initial header is needed.
청크 데이터 가져오기 및 메타데이터 변경
이 함수들은 청크에 대한 포인터를 받아 작동하며 메타데이터를 확인/설정하는 데 유용합니다:
청크 플래그 확인
// 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 */#definePREV_INUSE0x1/* extract inuse bit of previous chunk */#defineprev_inuse(p) ((p)->mchunk_size & PREV_INUSE)/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */#defineIS_MMAPPED0x2/* check for mmap()'ed chunk */#definechunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtainedfrom a non-main arena. This is only set immediately before handingthe chunk to the user, if necessary. */#defineNON_MAIN_ARENA0x4/* Check for chunk from main arena. */#definechunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) ==0)/* Mark a chunk as not being on the main arena. */#defineset_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
다른 청크에 대한 크기 및 포인터
/*Bits to mask off when extracting sizeNote: IS_MMAPPED is intentionally not masked off from size field inmacros for which mmapped chunks should never be seen. This shouldcause helpful core dumps to occur if it is tried by accident bypeople extending or adapting this malloc.*/#defineSIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)/* Get size, ignoring use bits */#definechunksize(p) (chunksize_nomask (p) &~(SIZE_BITS))/* Like chunksize, but do not mask SIZE_BITS. */#definechunksize_nomask(p) ((p)->mchunk_size)/* Ptr to next physical malloc_chunk. */#definenext_chunk(p) ((mchunkptr) (((char*) (p)) +chunksize (p)))/* Size of the chunk below P. Only valid if !prev_inuse (P). */#defineprev_size(p) ((p)->mchunk_prev_size)/* Set the size of the chunk below P. Only valid if !prev_inuse (P). */#defineset_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))/* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). */#defineprev_chunk(p) ((mchunkptr) (((char*) (p)) -prev_size (p)))/* Treat space at ptr + offset as a chunk */#definechunk_at_offset(p, s) ((mchunkptr) (((char*) (p)) + (s)))
/* Set size at head, without disturbing its use bit */#defineset_head_size(p, s) ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))/* Set size/use field */#defineset_head(p, s) ((p)->mchunk_size = (s))/* Set size at footer (only when chunk is not in use) */#defineset_foot(p, s) (((mchunkptr) ((char*) (p) + (s)))->mchunk_prev_size = (s))
청크 내부의 실제 사용 가능한 데이터 크기를 가져옵니다.
#pragmaGCCpoisonmchunk_size#pragmaGCCpoisonmchunk_prev_size/* This is the size of the real usable data in the chunk. Not valid fordumped heap chunks. */#definememsize(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 granulesize, 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;}
문자열 panda가 0xaaaaaaac12a0에 저장된 것을 볼 수 있습니다 (이는 x0 내의 malloc에 의해 응답으로 제공된 주소입니다). 0x10 바이트 이전을 확인하면 0x0이 이전 청크가 사용되지 않음을 나타내고 이 청크의 길이는 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 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).png" alt=""><figcaption></figcaption></figure>
그런 다음, 첫 번째 스레드를 호출한 후, malloc을 호출하는 스레드에서 새로운 아레나가 생성됩니다:
<figure><img src="../../.gitbook/assets/image (1) (1) (1) (1) (1) (1) (1).png" alt=""><figcaption></figcaption></figure>
그 안에는 몇 개의 청크가 있습니다:
<figure><img src="../../.gitbook/assets/image (2) (1) (1) (1).png" alt=""><figcaption></figcaption></figure>
## Bins & Memory Allocations/Frees
bins가 무엇인지, 어떻게 구성되어 있는지, 메모리가 어떻게 할당되고 해제되는지 확인하세요:
<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/)