13 KiB
힙
힙 기초
힙은 프로그램이 malloc, calloc 등의 함수를 호출하여 데이터를 요청할 때 데이터를 저장할 수 있는 공간입니다. 더불어, 이 메모리가 더 이상 필요하지 않을 때는 free 함수를 호출하여 사용 가능한 상태로 만듭니다.
힙은 메모리에 로드되는 이진 파일 바로 뒤에 위치하며( [heap] 섹션 확인), 요청된 데이터를 저장하기 위해 힙에 일정 공간이 할당됩니다. 이 공간은 bin에 속하며 요청된 데이터 + bin 헤더 공간 + 최소 bin 크기 오프셋만이 청크에 대해 예약됩니다. 각 청크가 어디에 있는지 찾기 어렵지 않게 최소한의 메모리만 예약하는 것이 목표입니다. 이를 위해 메타데이터 청크 정보를 사용하여 각 사용 중 또는 빈 공간이 어디에 있는지 알 수 있습니다.
공간을 예약하는 방법은 주로 사용된 bin에 따라 다르지만 일반적인 방법은 다음과 같습니다:
- 프로그램은 일정량의 메모리를 요청합니다.
- 청크 목록에 요청을 충족할 수 있는 충분히 큰 공간이 있는 경우 해당 공간이 사용됩니다.
- 이는 심지어 사용 가능한 청크의 일부가 이 요청에 사용되고 나머지는 청크 목록에 추가될 수 있음을 의미할 수 있습니다.
- 목록에 사용 가능한 청크가 없지만 할당된 힙 메모리에 여전히 공간이 있는 경우 힙 관리자는 새로운 청크를 생성합니다.
- 새로운 청크를 할당할 힙 공간이 충분하지 않은 경우 힙 관리자는 커널에게 힙에 할당된 메모리를 확장하도록 요청한 다음 이 메모리를 사용하여 새로운 청크를 생성합니다.
- 모든 것이 실패하면
malloc은 null을 반환합니다.
요청된 메모리가 임계값을 초과하는 경우, **mmap**이 요청된 메모리를 매핑하는 데 사용됩니다.
아레나
다중 스레드 애플리케이션에서 힙 관리자는 충돌로 인한 충돌을 방지해야 합니다. 초기에는 전역 뮤텍스를 사용하여 한 번에 한 스레드만 힙에 액세스할 수 있도록 보장했지만, 이는 뮤텍스로 인한 병목 현상으로 인해 성능 문제를 일으켰습니다.
이를 해결하기 위해 ptmalloc2 힙 할당기는 "아레나"를 도입했는데, 각 아레나는 자체 데이터 구조 및 뮤텍스를 가진 별도의 힙 역할을 하여 서로 간섭하지 않고 여러 스레드가 힙 작업을 수행할 수 있도록 합니다.
기본 "main" 아레나는 단일 스레드 애플리케이션의 힙 작업을 처리합니다. 새로운 스레드가 추가되면 힙 관리자는 충돌을 줄이기 위해 그들에게 보조 아레나를 할당합니다. 먼저 각 새 스레드를 사용하지 않은 아레나에 연결하려고 시도하며 필요한 경우 새로운 것을 만들어 32비트 시스템의 CPU 코어 수의 2배 한도까지, 64비트 시스템의 경우 8배까지 생성합니다. 한도에 도달하면 스레드는 아레나를 공유해야 하므로 잠재적인 충돌이 발생합니다.
주 아레나가 brk 시스템 호출을 사용하여 확장하는 반면, 보조 아레나는 mmap 및 mprotect를 사용하여 "서브힙"을 생성하여 힙 동작을 모방하여 다중 스레드 작업에 대한 메모리 관리를 유연하게 할 수 있습니다.
서브힙
서브힙은 다중 스레드 애플리케이션의 보조 아레나에 대한 메모리 예비로 작동하여 메인 힙과 별도로 자체 힙 영역을 성장하고 관리할 수 있습니다. 서브힙이 초기 힙과 어떻게 다른지 및 작동하는 방식은 다음과 같습니다:
- 초기 힙 대 서브힙:
- 초기 힙은 메모리에 프로그램의 바이너리 바로 뒤에 위치하며
sbrk시스템 호출을 사용하여 확장됩니다. - 보조 아레나에서 사용되는 서브힙은
mmap을 통해 생성되며 지정된 메모리 영역을 매핑하는 시스템 호출입니다.
mmap을 사용한 메모리 예약:
- 힙 관리자가 서브힙을 생성하면
mmap을 통해 큰 메모리 블록을 예약합니다. 이 예약은 즉시 메모리를 할당하지 않고 다른 시스템 프로세스나 할당이 사용하지 않아야 하는 영역을 지정합니다. - 기본적으로 32비트 프로세스의 서브힙에 대한 예약 크기는 1MB이며, 64비트 프로세스의 경우 64MB입니다.
mprotect를 사용한 점진적 확장:
- 예약된 메모리 영역은 초기에
PROT_NONE으로 표시되어 있어 커널이 이 공간에 물리적 메모리를 할당할 필요가 없음을 나타냅니다. - 서브힙을 "확장"하기 위해 힙 관리자는
mprotect를 사용하여 페이지 권한을PROT_NONE에서PROT_READ | PROT_WRITE로 변경하여 커널이 이전에 예약된 주소에 물리적 메모리를 할당하도록 유도합니다. 이 단계별 접근 방식을 통해 서브힙은 필요에 따라 확장될 수 있습니다. - 서브힙 전체가 고갈되면 힙 관리자는 계속해서 할당하기 위해 새로운 서브힙을 생성합니다.
malloc_state
각 힙(주 아레나 또는 다른 스레드 아레나)에는 malloc_state 구조체가 있습니다.
주 아레나 malloc_state 구조체는 libc의 전역 변수임을 알아두는 것이 중요합니다.
스레드의 힙의 malloc_state 구조체의 경우, 스레드 자체 "힙" 내부에 위치합니다.
이 구조체에서 주목할 만한 사항이 있습니다 (아래의 C 코드 참조):
mchunkptr bins[NBINS * 2 - 2];는 작은, 큰 및 정렬되지 않은 bins의 첫 번째 및 마지막 청크에 대한 포인터를 포함합니다 (-2는 인덱스 0이 사용되지 않기 때문입니다).- 따라서 이러한 bins의 첫 번째 청크는 이 구조체로의 역방향 포인터를 가지고 있으며 이러한 bins의 마지막 청크는 이 구조체로의 순방향 포인터를 가지고 있습니다. 이는 기본적으로 주 아레나에서 이러한 주소를 유출하면 libc의 구조체로의 포인터를 얻을 수 있음을 의미합니다.
- 구조체
struct malloc_state *next;및struct malloc_state *next_free;는 아레나의 연결 목록입니다. top청크는 마지막 "청크"으로, 힙의 남은 공간 전체입니다. top 청크가 "비어있는" 경우, 힙은 완전히 사용되었으며 더 많은 공간을 요청해야 합니다.last reminder청크는 정확한 크기의 청크가 사용 불가능한 경우에 발생하며, 따라서 더 큰 청크가 분할되고 포인터가 남은 부분이 여기에 배치됩니다.
// From https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_state
struct malloc_state
{
/* Serialize access. */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* 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;
};
typedef struct malloc_state *mstate;
malloc_chunk
이 구조체는 메모리의 특정 청크를 나타냅니다. 다양한 필드는 할당된 청크와 할당되지 않은 청크에 대해 다른 의미를 가지고 있습니다.
// From https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_chunk
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가 있습니다(또는 할당될 때 사용자 데이터를 저장하는 데 사용됩니다).
또한 사용 가능한 경우 사용자 데이터는 몇 가지 데이터를 포함하기도 합니다:
- 다음 청크를 가리키는 포인터
- 이전 청크를 가리키는 포인터
- 목록에서 다음 청크의 크기
- 목록에서 이전 청크의 크기
https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png
{% hint style="info" %} 이러한 방식으로 목록을 연결함으로써 모든 단일 청크가 등록되어 있는 배열이 필요하지 않도록 합니다. {% endhint %}
퀵 힙 예제
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은 이전 청크가 사용되지 않음을 나타내고 이 청크의 길이가 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
Bins 및 메모리 할당/해제
다음에서는 어떤 것이 bins이며 어떻게 구성되어 있는지, 그리고 메모리가 할당되고 해제되는 방법을 확인하십시오:
{% content-ref url="bins-and-memory-allocations.md" %} bins-and-memory-allocations.md {% endcontent-ref %}
힙 함수 보안 검사
힙과 관련된 함수는 해당 작업을 수행하기 전에 일정한 검사를 수행하여 힙이 손상되지 않았는지 확인하려고 합니다:
{% content-ref url="heap-functions-security-checks.md" %} heap-functions-security-checks.md {% endcontent-ref %}