Heap

힙 기초

힙은 프로그램이 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로 변경하여 커널이 이전에 예약된 주소에 물리적 메모리를 할당하도록 유도합니다. 이 단계별 접근 방식을 통해 서브힙은 필요에 따라 확장될 수 있습니다.

• 서브힙 전체가 고갈되면 힙 관리자는 계속해서 할당하기 위해 새로운 서브힙을 생성합니다.

메타데이터

이전에 언급한 대로, 이러한 청크에는 메타데이터도 있으며 이 이미지에서 잘 표현되어 있습니다:

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

리스트를 이렇게 연결하는 것은 모든 단일 청크가 등록되는 배열이 필요하지 않도록 합니다.

해제 보호

free 함수의 의도치 않은 또는 의도적인 남용으로부터 보호하기 위해 실행하기 전에 몇 가지 확인을 수행합니다:

• 주소가 8바이트 또는 64비트 경계에 맞게 정렬되어 있는지 확인합니다. 즉, _malloc_은 모든 할당이 정렬되도록 보장하므로 ((address % 16) == 0).

• 청크의 크기 필드가 불가능하지 않은지 확인합니다. 너무 작거나 너무 크거나 정렬되지 않은 크기이거나 프로세스 주소 공간의 끝을 겹치게 할 수 없기 때문입니다.

• 청크가 아레나의 경계 내에 있는지 확인합니다.

• 청크가 이미 해제되었는지 확인합니다. 다음 청크의 시작 부분에 있는 메타데이터에 있는 해당 "P" 비트를 확인하여 이미 해제되었는지 확인합니다.

Bins

Chunks가 저장되는 효율성을 향상시키기 위해 각 chunk는 하나의 연결 리스트에만 있지 않고 여러 유형의 bin이 있습니다. 이들은 bins이며 5 종류가 있습니다: 62 small bins, 63 large bins, 1 unsorted bin, 10 fast bins 그리고 스레드 당 64개의 tcache bins가 있습니다.

Unsorted, small, large bins의 초기 주소는 동일한 배열 내에 있습니다. 인덱스 0은 사용되지 않고, 1은 unsorted bin이며, 2-64는 small bins이고, 65-127는 large bins입니다.

Small Bins

Small bins는 large bins보다 빠르지만 fast bins보다는 느립니다.

62개의 각 bin은 동일한 크기의 chunks를 가집니다: 16, 24, ... (32비트에서 최대 504바이트, 64비트에서 1024바이트). 이는 공간을 할당할 bin을 빠르게 찾고 이러한 목록에 항목을 삽입하고 제거하는 속도를 돕습니다.

Large Bins

고정된 크기의 chunks를 관리하는 small bins과 달리, 각 large bin은 일정 범위의 chunk 크기를 처리합니다. 이는 시스템이 다양한 크기를 별도의 bin 없이 수용할 수 있도록 더 유연하게 만듭니다.

메모리 할당기에서 large bins는 small bins가 끝나는 곳에서 시작합니다. Large bins의 범위는 점진적으로 커지며, 첫 번째 bin은 512에서 576바이트의 chunks를 커버하고, 다음 bin은 576에서 640바이트를 커버합니다. 이 패턴은 계속되어, 가장 큰 bin은 1MB 이상의 모든 chunks를 포함합니다.

Large bins는 작은 bins보다 더 느리게 작동합니다. 왜냐하면 할당에 가장 적합한 chunk를 찾기 위해 다양한 크기의 chunk 목록을 정렬하고 검색해야하기 때문입니다. Large bin에 chunk가 삽입되면 정렬되어야 하며, 메모리가 할당될 때 시스템은 올바른 chunk를 찾아야 합니다. 이 추가 작업으로 인해 large bins는 느리지만, 대부분의 작은 할당이 작은 것보다 적기 때문에 허용할 수 있는 교환입니다.

다음과 같은 것들이 있습니다:

• 64B 범위의 32개 bin

• 512B 범위의 16개 bin

• 4096B 범위의 8개 bin

• 32768B 범위의 4개 bin

• 262144B 범위의 2개 bin

• 나머지 크기를 위한 1개 bin

Unsorted bin

Unsorted bin은 메모리 할당을 빠르게 만들기 위해 힙 관리자가 사용하는 빠른 캐시입니다. 작동 방식은 다음과 같습니다: 프로그램이 메모리를 해제할 때, 힙 관리자는 즉시 특정 bin에 넣지 않습니다. 대신, 주변의 빈 공간과 병합하여 더 큰 빈 메모리 블록을 만듭니다. 그런 다음, 이 새로운 chunk를 "unsorted bin"이라고 불리는 일반 bin에 배치합니다.

프로그램이 메모리를 요청할 때, 힙 관리자는 먼저 unsorted bin을 확인하여 적절한 크기의 chunk가 있는지 확인합니다. 찾으면 즉시 사용하여 다른 bins을 검색하는 것보다 빠릅니다. 적합한 chunk를 찾지 못하면 해제된 chunks를 크기에 따라 올바른 bins(작은 bins 또는 large bins)으로 이동합니다.

따라서 unsorted bin은 최근에 해제된 메모리를 빠르게 재사용하여 메모리 할당을 가속화하고, 시간 소모적인 검색 및 병합이 줄어듭니다.

다른 카테고리의 chunks이더라도 가끔 사용 가능한 chunk가 다른 사용 가능한 chunk와 충돌하는 경우(카테고리가 다르더라도), 병합될 수 있습니다.

Fast bins

Fast bins는 최근에 해제된 chunks를 빠른 액세스 구조에 유지하여 작은 chunks에 대한 메모리 할당을 가속화하기 위해 설계되었습니다. 이러한 bins은 후입선출(LIFO) 접근 방식을 사용하며, 가장 최근에 해제된 chunk가 새로운 할당 요청 시 가장 먼저 재사용됩니다. 이 동작은 속도적으로 유리합니다. 스택(LIFO)의 맨 위에서 삽입 및 제거하는 것이 큐(FIFO)보다 빠르기 때문입니다.

또한, fast bins는 단일 연결 리스트를 사용하며 이는 속도를 더 향상시킵니다. Fast bins의 chunks는 이웃과 병합되지 않기 때문에 중간에서 제거를 허용하는 복잡한 구조가 필요하지 않습니다. 단일 연결 리스트는 이러한 작업에 대해 더 간단하고 빠릅니다.

기본적으로 여기서 발생하는 일은 header(사용 가능한 첫 번째 chunk를 가리키는 포인터)가 항상 해당 크기의 최신 해제된 chunk를 가리키도록 하는 것입니다. 따라서:

• 해당 크기의 새로운 chunk가 할당되면, header는 사용할 수 있는 빈 chunk를 가리킵니다. 이 빈 chunk가 사용할 다음 chunk를 가리키고 있으므로, 다음 할당이 어디에서 사용 가능한 chunk를 가져올지 알기 위해 이 주소가 header에 저장됩니다.

• chunk가 해제되면, 빈 chunk는 현재 사용 가능한 chunk의 주소를 저장하고, 이 새로 해제된 chunk의 주소가 header에 저장됩니다.

Fast bins의 chunks는 자동으로 사용 가능한 상태로 설정되지 않으므로, 다른 chunks와 병합할 수 있는 대신 어느 정도의 시간 동안 fast bin chunks로 유지됩니다.

Tcache (Per-Thread Cache) Bins

스레드가 자체 힙을 가지려고 노력하더라도(자세한 내용은 Arenas 및 Subheaps 참조), 많은 스레드(예: 웹 서버)를 가진 프로세스가 다른 스레드와 힙을 공유할 수 있는 가능성이 있습니다. 이 경우, 주요 해결책은 lockers를 사용하는 것이며, 이는 스레드를 상당히 느리게 만들 수 있습니다.

따라서 tcache는 각 스레드 당 하나의 fast bin과 유사한 방식으로 작동합니다. 각 스레드에는 64개의 단일 연결 tcache bins가 있습니다. 각 bin은 64비트 시스템에서 24에서 1032B, 32비트 시스템에서 12에서 516B까지의 7개 동일한 크기의 chunks를 가질 수 있습니다.

스레드가 chunk를 해제하면, tcache에 할당되기에 너무 크지 않고 해당 tcache bin 이미 가득 차지 않았다면, 거기에 할당됩니다. tcache로 이동할 수 없는 경우, 전역 bins에서 free 작업을 수행할 수 있도록 힙 잠금을 기다려야 합니다.

chunk가 할당될 때, Tcache에 필요한 크기의 빈 chunk가 있는 경우 사용하고, 그렇지 않으면 전역 bins에서 찾거나 새로 생성하기 위해 힙 잠금을 기다려야 합니다. 또한 이 경우 최적화가 있으며, 힙 잠금을 사용하는 동안 스레드는 요청된 크기의 힙 chunks(7개)로 Tcache를 채우므로 필요한 경우 Tcache에서 찾을 수 있습니다.

Bins order

할당에 대해:

1. 해당 크기의 Tcache에 사용 가능한 청크가 있다면, Tcache를 사용합니다.

2. 너무 크다면, mmap을 사용합니다.

3. 아레나 힙 락을 획득하고:

   1. 충분히 작은 크기가 있다면, 요청된 크기의 fast bin 청크를 사용하고 fast bin에서 tcache를 미리 채웁니다.

   2. 충분히 큰 청크를 찾기 위해 unsorted 리스트의 각 항목을 확인하고 가능하다면 tcache를 미리 채웁니다.

   3. 요청된 크기에 따라 small bins 또는 large bins를 확인하고 가능하다면 tcache를 미리 채웁니다.

   4. 사용 가능한 메모리에서 새로운 청크를 생성합니다.

      1. 사용 가능한 메모리가 없다면 sbrk를 사용하여 더 많은 메모리를 가져옵니다.

      2. 메인 힙 메모리가 더 이상 확장할 수 없다면, mmap을 사용하여 새 공간을 생성합니다.

   5. 아무것도 작동하지 않으면 null을 반환합니다.

해제에 대해:

1. 포인터가 Null이면 종료합니다.

2. 합법적인 청크인지 확인하기 위해 청크에서 free 상태 확인을 수행합니다.

   1. 충분히 작고 tcache가 가득 차지 않았다면, 해당 위치에 넣습니다.

   2. 비트 M이 설정되어 있다면(힙이 아닌 경우), munmap을 사용합니다.

   3. 아레나 힙 락을 획득합니다:

      1. fastbin에 맞는 경우, 해당 위치에 넣습니다.

      2. 청크가 64KB보다 크다면, 즉시 fastbins를 병합하고 결과로 나온 병합된 청크를 unsorted bin에 넣습니다.

      3. 주변에 해제된 청크와 함께 청크를 뒤로나 앞으로 병합합니다. 이는 small, large, unsorted bins에 해당됩니다.

      4. 헤드의 맨 위에 있다면, 사용되지 않는 메모리로 병합합니다.

      5. 이전 것이 아니라면, unsorted 리스트에 저장합니다.

#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

참고 자료

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