hacktricks/binary-exploitation/heap/README.md

# 힙

## 힙 기초

힙은 프로그램이 **`malloc`**, `calloc` 등의 함수를 호출하여 데이터를 요청할 때 데이터를 저장할 수 있는 공간입니다. 더불어, 이 메모리가 더 이상 필요하지 않을 때는 **`free`** 함수를 호출하여 사용 가능한 상태로 만듭니다.

힙은 메모리에 로드되는 이진 파일 바로 뒤에 위치하며( `[heap]` 섹션 확인), 요청된 데이터를 저장하기 위해 힙에 일정 공간이 할당됩니다. 이 공간은 bin에 속하며 요청된 데이터 + bin 헤더 공간 + 최소 bin 크기 오프셋만이 청크에 대해 예약됩니다. 각 청크가 어디에 있는지 찾기 어렵지 않게 최소한의 메모리만 예약하는 것이 목표입니다. 이를 위해 메타데이터 청크 정보를 사용하여 각 사용 중 또는 빈 공간이 어디에 있는지 알 수 있습니다.

공간을 예약하는 방법은 주로 사용된 bin에 따라 다르지만 일반적인 방법은 다음과 같습니다:

* 프로그램은 일정량의 메모리를 요청합니다.
* 청크 목록에 요청을 충족할 수 있는 충분히 큰 공간이 있는 경우 해당 공간이 사용됩니다.
* 이는 심지어 사용 가능한 청크의 일부가 이 요청에 사용되고 나머지는 청크 목록에 추가될 수 있음을 의미할 수 있습니다.
* 목록에 사용 가능한 청크가 없지만 할당된 힙 메모리에 여전히 공간이 있는 경우 힙 관리자는 새로운 청크를 생성합니다.
* 새로운 청크를 할당할 힙 공간이 충분하지 않은 경우 힙 관리자는 커널에게 힙에 할당된 메모리를 확장하도록 요청한 다음 이 메모리를 사용하여 새로운 청크를 생성합니다.
* 모든 것이 실패하면 `malloc`은 null을 반환합니다.

요청된 **메모리가 임계값을 초과하는 경우**, **`mmap`**이 요청된 메모리를 매핑하는 데 사용됩니다.

### 아레나

**다중 스레드** 애플리케이션에서 힙 관리자는 충돌로 인한 충돌을 방지해야 합니다. 초기에는 **전역 뮤텍스**를 사용하여 한 번에 한 스레드만 힙에 액세스할 수 있도록 보장했지만, 이는 뮤텍스로 인한 병목 현상으로 인해 **성능 문제**를 일으켰습니다.

이를 해결하기 위해 ptmalloc2 힙 할당기는 "아레나"를 도입했는데, **각 아레나**는 **자체 데이터 구조 및 뮤텍스**를 가진 **별도의 힙** 역할을 하여 서로 간섭하지 않고 여러 스레드가 힙 작업을 수행할 수 있도록 합니다.

기본 "main" 아레나는 단일 스레드 애플리케이션의 힙 작업을 처리합니다. **새로운 스레드**가 추가되면 힙 관리자는 **충돌을 줄이기 위해** 그들에게 **보조 아레나**를 할당합니다. 먼저 각 새 스레드를 사용하지 않은 아레나에 연결하려고 시도하며 필요한 경우 새로운 것을 만들어 32비트 시스템의 CPU 코어 수의 2배 한도까지, 64비트 시스템의 경우 8배까지 생성합니다. 한도에 도달하면 **스레드는 아레나를 공유**해야 하므로 잠재적인 충돌이 발생합니다.

주 아레나가 `brk` 시스템 호출을 사용하여 확장하는 반면, 보조 아레나는 `mmap` 및 `mprotect`를 사용하여 "서브힙"을 생성하여 힙 동작을 모방하여 다중 스레드 작업에 대한 메모리 관리를 유연하게 할 수 있습니다.

### 서브힙

서브힙은 다중 스레드 애플리케이션의 보조 아레나에 대한 메모리 예비로 작동하여 메인 힙과 별도로 자체 힙 영역을 성장하고 관리할 수 있습니다. 서브힙이 초기 힙과 어떻게 다른지 및 작동하는 방식은 다음과 같습니다:

1. **초기 힙 대 서브힙**:
* 초기 힙은 메모리에 프로그램의 바이너리 바로 뒤에 위치하며 `sbrk` 시스템 호출을 사용하여 확장됩니다.
* 보조 아레나에서 사용되는 서브힙은 `mmap`을 통해 생성되며 지정된 메모리 영역을 매핑하는 시스템 호출입니다.
2. **`mmap`을 사용한 메모리 예약**:
* 힙 관리자가 서브힙을 생성하면 `mmap`을 통해 큰 메모리 블록을 예약합니다. 이 예약은 즉시 메모리를 할당하지 않고 다른 시스템 프로세스나 할당이 사용하지 않아야 하는 영역을 지정합니다.
* 기본적으로 32비트 프로세스의 서브힙에 대한 예약 크기는 1MB이며, 64비트 프로세스의 경우 64MB입니다.
3. **`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` 청크는 정확한 크기의 청크가 사용 불가능한 경우에 발생하며, 따라서 더 큰 청크가 분할되고 포인터가 남은 부분이 여기에 배치됩니다.
```c
// 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

이 구조체는 메모리의 특정 청크를 나타냅니다. 다양한 필드는 할당된 청크와 할당되지 않은 청크에 대해 다른 의미를 가지고 있습니다.
```c
// 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;
```
이전에 설명한 대로, 이러한 청크들에는 메타데이터가 있습니다. 이 이미지에서 잘 표현되어 있습니다:

<figure><img src="../../.gitbook/assets/image (1242).png" alt=""><figcaption><p><a href="https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png">https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png</a></p></figcaption></figure>

메타데이터는 일반적으로 현재 청크 크기를 나타내는 0x08B로 표시되며, 마지막 3비트를 사용하여 다음을 나타냅니다:

* `A`: 1이면 하위 힙에서 가져온 것이고, 0이면 주 힙에 있습니다.
* `M`: 1이면 mmap으로 할당된 공간의 일부이며, 힙의 일부가 아닙니다.
* `P`: 1이면 이전 청크가 사용 중입니다.

그런 다음 사용자 데이터를 위한 공간이 있고, 마지막으로 청크가 사용 가능할 때 이전 청크 크기를 나타내는 0x08B가 있습니다(또는 할당될 때 사용자 데이터를 저장하는 데 사용됩니다).

또한 사용 가능한 경우 사용자 데이터는 몇 가지 데이터를 포함하기도 합니다:

* 다음 청크를 가리키는 포인터
* 이전 청크를 가리키는 포인터
* 목록에서 다음 청크의 크기
* 목록에서 이전 청크의 크기

<figure><img src="../../.gitbook/assets/image (1243).png" alt=""><figcaption><p><a href="https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png">https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png</a></p></figcaption></figure>

{% hint style="info" %}
이러한 방식으로 목록을 연결함으로써 모든 단일 청크가 등록되어 있는 배열이 필요하지 않도록 합니다.
{% endhint %}

### 퀵 힙 예제

[https://guyinatuxedo.github.io/25-heap/index.html](https://guyinatuxedo.github.io/25-heap/index.html)의 퀵 힙 예제를 arm64로 변환한 것입니다.
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void main(void)
{
char *ptr;
ptr = malloc(0x10);
strcpy(ptr, "panda");
}
```
메인 함수 끝에 중단점을 설정하고 정보가 저장된 위치를 찾아봅시다:

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

문자열 '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](bins-and-memory-allocations.md)
{% endcontent-ref %}

## 힙 함수 보안 검사

힙과 관련된 함수는 해당 작업을 수행하기 전에 일정한 검사를 수행하여 힙이 손상되지 않았는지 확인하려고 합니다:

{% content-ref url="heap-functions-security-checks.md" %}
[heap-functions-security-checks.md](heap-functions-security-checks.md)
{% endcontent-ref %}

## 참고 자료

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