[Hacking] / [Pwnable - How2Heap] Heap exploitation : calc_tcache_idx.c

원본 문서 : https://github.com/shellphish/how2heap

GitHub - shellphish/how2heap: A repository for learning various heap exploitation techniques.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>


struct malloc_chunk {

  size_t      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  size_t      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if 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 free. */
  struct malloc_chunk* bk_nextsize;
};

/* The corresponding word size.  */
#define SIZE_SZ (sizeof (size_t))

#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
			  ? __alignof__ (long double) : 2 * SIZE_SZ)

/* The corresponding bit mask value.  */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

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

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

/* When "x" is from chunksize().  */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

/* When "x" is a user-provided size.  */
# define usize2tidx(x) csize2tidx (request2size (x))

int main()
{
    unsigned long long req;
    unsigned long long tidx;
	fprintf(stderr, "This file doesn't demonstrate an attack, but calculates the tcache idx for a given chunk size.\n");
	fprintf(stderr, "The basic formula is as follows:\n");
    fprintf(stderr, "\tIDX = (CHUNKSIZE - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT\n");
    fprintf(stderr, "\tOn a 64 bit system the current values are:\n");
    fprintf(stderr, "\t\tMINSIZE: 0x%lx\n", MINSIZE);
    fprintf(stderr, "\t\tMALLOC_ALIGNMENT: 0x%lx\n", MALLOC_ALIGNMENT);
    fprintf(stderr, "\tSo we get the following equation:\n");
    fprintf(stderr, "\tIDX = (CHUNKSIZE - 0x%lx) / 0x%lx\n\n", MINSIZE-MALLOC_ALIGNMENT+1, MALLOC_ALIGNMENT);
    fprintf(stderr, "BUT be AWARE that CHUNKSIZE is not the x in malloc(x)\n");
    fprintf(stderr, "It is calculated as follows:\n");
    fprintf(stderr, "\tIF x + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE(0x%lx) CHUNKSIZE = MINSIZE (0x%lx)\n", MINSIZE, MINSIZE);
    fprintf(stderr, "\tELSE: CHUNKSIZE = (x + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK) \n");
    fprintf(stderr, "\t=> CHUNKSIZE = (x + 0x%lx + 0x%lx) & ~0x%lx\n\n\n", SIZE_SZ, MALLOC_ALIGN_MASK, MALLOC_ALIGN_MASK);
    while(1) {
        fprintf(stderr, "[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): ");
        scanf("%llx", &req);
        tidx = usize2tidx(req);
        if (tidx > 63) {
            fprintf(stderr, "\nWARNING: NOT IN TCACHE RANGE!\n");
        }
        fprintf(stderr, "\nTCache Idx: %llu\n", tidx);
    }
    return 0;
}

원본 전문 코드는 이렇고,

struct malloc_chunk {

  size_t      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  size_t      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if 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 free. */
  struct malloc_chunk* bk_nextsize;
};

 
 이 struct malloc_chunk은 glibc의 malloc 구현에서 사용하는 내부 구조체로, 힙(Heap) 메모리에서의 청크(chunk)를 관리하는 데 사용된다. 이 구조는 특히 free chunk (해제된 메모리 블록)를 관리하기 위한 메타데이터이다. 
-> 할당된 chunk는 mchunk_size필드만 유효하게 사용됨
-> free된 chunk는 나머지 포인터 (fd, bk, fd_nextsize, bk_nextsize)를 통해 bin(free list)에 연결됨
-> glibc malloc 은 fastbin, smallbin, largebin 같은 다양한 bin을 관리하며, 이 포인터들을 이용해 효율적으로 동작함
-> 구조체는 실제로 사용자에게 반환되는 포인터보다 앞쪽에 위치한 메타데이터이므로, 버그나 익스플로잇 시 이 구조체를 덮는 것이 핵심임
 

/* The corresponding word size.  */
#define SIZE_SZ (sizeof (size_t))

#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
			  ? __alignof__ (long double) : 2 * SIZE_SZ)

 
-> 해당 코드는 glibc의 malloc 구현에서 정렬 기준을 정의함. 힙 메모리의 효율성과 안정성을 확보하기 위해 메모리는 특정 단위로 정렬되어야 하며, MALLOC_ALIGNMENT는 그 최소 단위를 정의한다.
-> size_t는 시스템에 따라 4바이트(32비트) 또는 8바이트(64비트)
-> SIZE_SZ는 malloc_chunk 내부 필드의 크기를 의미.
-> MALLOC_ALIGNMENT는 할당 시 메모리 정렬 기준을 나타내고 이 값은 일반적으로 시스템 아키텍처에 따라 16 또는 32가 된다.
2 * SIZE_SZ: 최소한 size_t 두 개 만큼 정렬 -> 일반적으로 16바이트
__alignof__ (long double) : long double 타입의 정렬 기준으로 보통 16바이트 이상이다.
=> 이 둘 중 더 큰 값을 선택해 메모리 정렬 기준으로 사용하게 됨.

/* The corresponding bit mask value.  */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

MALLOC_ALIGN_MASK는 주소나 크기를 정렬된 값으로 반올림하거나, 정렬되지 않은 비트를 무시할 때 사용이 된다. 
-> MALLOC_ALINGMENT가 16이면 MALLOC_ALIGN_MASK는 16-1인 15가 되고, 이를 16진수로 표현하면 0xF가 됨.
=> 하위 비트 중 정렬 단위보다 작은 비트를 가리는 마스크 역할을 함.
 

/* The smallest possible chunk */
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))

-> 힙 구조에서 chunk의 최소 크기를 정의
-> offsetof(struct malloc_chunk, fd_nextsize)는 구조체에서 fd_nextsize 필드가 시작되는 바이트 오프셋을 구하고, 즉 fd_nextsize 바로 전까지의 크기가 최소 chunk 크기라는 뜻이다.

/* The smallest size we can malloc is an aligned minimal chunk */
#define MINSIZE  \
  (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

-> MINSIZE는 실제로 malloc()이 최소로 할당할 수 있는 크기를 의미하고, MIN_CHUNK_SIZE가 예시로 32이고, MALLOC_ALIGN_MASK가 15(16바이트 정렬 방식에서)라면,
-> MINSIZE = ((32 + 15) & ~15) = 47 & ~15 = 47 & -16 = 32 -> 맞는 듯하지만, 실은 48이 됨.

/* When "x" is from chunksize().  */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

-> x는 chunk의 크기로 해당 매크로는 해당 크기가 tcache에서 몇 번째 bin 인덱스인지 계산해줌.
+) Tcache는 크기별로 정렬된 bin 배열(tcache_entry)을 최대 64개 (TCACHE_MAX_BINS)까지 유지

/* When "x" is a user-provided size.  */
# define usize2tidx(x) csize2tidx (request2size (x))

-> 사용자가 malloc(x)처럼 요청한 크기가 tcache의 몇 번재 bin에 들어갈지를 구할 때 사용됨. 
x : 사용자가 malloc(x)로 요청한 크기
request2size(x) : 요청 크기 -> 내부 chunk 크기로 변환, 헤더 크기(SIZE_SZ) + 정렬 -> 최소 MINSIZE 이상으로 커짐
csize2tidx(...) : chunk 크기를 tcache의 인덱스로 변환
 

int main()
{
    unsigned long long req;
    unsigned long long tidx;
	fprintf(stderr, "This file doesn't demonstrate an attack, but calculates the tcache idx for a given chunk size.\n");
	fprintf(stderr, "The basic formula is as follows:\n");
    fprintf(stderr, "\tIDX = (CHUNKSIZE - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT\n");
    fprintf(stderr, "\tOn a 64 bit system the current values are:\n");
    fprintf(stderr, "\t\tMINSIZE: 0x%lx\n", MINSIZE);
    fprintf(stderr, "\t\tMALLOC_ALIGNMENT: 0x%lx\n", MALLOC_ALIGNMENT);
    fprintf(stderr, "\tSo we get the following equation:\n");
    fprintf(stderr, "\tIDX = (CHUNKSIZE - 0x%lx) / 0x%lx\n\n", MINSIZE-MALLOC_ALIGNMENT+1, MALLOC_ALIGNMENT);
    fprintf(stderr, "BUT be AWARE that CHUNKSIZE is not the x in malloc(x)\n");
    fprintf(stderr, "It is calculated as follows:\n");
    fprintf(stderr, "\tIF x + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE(0x%lx) CHUNKSIZE = MINSIZE (0x%lx)\n", MINSIZE, MINSIZE);
    fprintf(stderr, "\tELSE: CHUNKSIZE = (x + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK) \n");
    fprintf(stderr, "\t=> CHUNKSIZE = (x + 0x%lx + 0x%lx) & ~0x%lx\n\n\n", SIZE_SZ, MALLOC_ALIGN_MASK, MALLOC_ALIGN_MASK);
    while(1) {
        fprintf(stderr, "[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): ");
        scanf("%llx", &req);
        tidx = usize2tidx(req);
        if (tidx > 63) {
            fprintf(stderr, "\nWARNING: NOT IN TCACHE RANGE!\n");
        }
        fprintf(stderr, "\nTCache Idx: %llu\n", tidx);
    }
    return 0;
}

-> tcache idx를 주어진 chunk size 계산에 쓰는 방법을 알려주기 위해 작성되었다.
-> 기본 공식은 아래와 같다. 

#tcache index를 계산하는 공식
fprintf(stderr, "\tIDX = (CHUNKSIZE - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT\n");

추가로, 현재 값들은 64 비트 시스템에서 구동되고 있음
IDX를 계산할 때 아래의 공식을 따름. 

#IDX 계산 공식
fprintf(stderr, "\tIDX = (CHUNKSIZE - 0x%lx) / 0x%lx\n\n", MINSIZE-MALLOC_ALIGNMENT+1, MALLOC_ALIGNMENT);

 
-> x는 실제 CHUNKSIZE가 아니며, 내부적으로 request2bin을 통해 계산된다.

fprintf(stderr, "\tIF x + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE(...) THEN CHUNKSIZE = MINSIZE\n");

-> 너무 작은 크기면 chunk가 최소 크기(MINSIZE)로 맞춰짐

fprintf(stderr, "\tELSE: CHUNKSIZE = (x + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK) \n");
fprintf(stderr, "\t=> CHUNKSIZE = (x + 0x%lx + 0x%lx) & ~0x%lx\n\n\n", SIZE_SZ, MALLOC_ALIGN_MASK, MALLOC_ALIGN_MASK);

-> 요청한 x 바이트를 malloc(x)했을 때 내부에서 계산되는 chunk size는 SIZE_SZ(헤더)와 MALLOC_ALIGN_MASK(정렬 올림 보정)을 더한 뒤 MALLOC_ALIGNMENT 단위로 올림함.

    while(1) {
        fprintf(stderr, "[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): ");
        scanf("%llx", &req);
        tidx = usize2tidx(req);
        if (tidx > 63) {
            fprintf(stderr, "\nWARNING: NOT IN TCACHE RANGE!\n");
        }
        fprintf(stderr, "\nTCache Idx: %llu\n", tidx);

-> while이 항상 참으로 설정되어 무한 루프임.
-> CTRL+C를 눌러야 종료됨.
-> 사용자에게 malloc(x)에서 쓰는 x값을 16진수로 입력하라고 안내중인데, %llx로 입력값을 unsigned long long 형식의 16진수로 읽음 -> req 변수에 저장됨
 
- request2size(x) -> 사용자가 입력한 요청 크기 -> 내부 chunk 크기 (CHUNKSIZE)로 변환 (SIZE_SZ 더하고 MALLOC_ALIGNMENT로 올림. 최소 MINSIZE 보장)
- csize2tidx(CHUNKSIZE) -> 그 chunk size가 tcache에서 몇 번째 인덱스인지 계산
- glibc tcache는 최대 64개의 bin(0~63)만 사용.
- 인덱스가 64 이상이면 -> 해당 크기의 청크는 tcache 관리 대상이 아니지만, fastbin, smallbin, largebin 등에 들어가며, "이 크기로는 tcache 공격이 안 된다"는 뜻의 경고이기도 함.