[how2heap] calc_tcache_idx.c

Lecture: cal_tcache_idx.c

https://github.com/shellphish/how2heap/blob/master/calc_tcache_idx.c

how2heap/calc_tcache_idx.c at master · shellphish/how2heap

 

 

Environment : Ubuntu 18.04.5 LTS / ldd (Ubuntu GLIBC 2.27-3ubuntu1.6) 2.27

 

Lecture Code:

 

#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;
}

 

Background:

malloc_chunk 구조체는 malloc.c 에 정의된 청크 구조체이다. 

 

SIZE_SZ 매크로는 size_t의 크기를 저장한다. size_t는 32bit에서 4byte, 64bit에선 8byte이다.

 

MALLOC_ALIGNMENT 매크로는 시스템에서 요구하는 최소 정렬 크기를 정의하는 매크로이다. 

 

64bit에선 SIZE_SZ 가 8이고, 64bit Linux 에선 __alignof__(long double) 은 16(byte) 이다(long double 변수형은 시스템 아키텍처에 따라 다르다).

 

정의된 식에 의하면 __alignof__(long double)이 더 큰 경우 __alignof__(long double) 값을 쓰고, 그렇지 않다면 (2 * SIZE_SZ) 를 쓰므로 여기서 MALLOC_ALIGNMENT 는 16이다.

 

MALLOC_ALIGN_MASK 매크로는 정렬을 위해서 사용되는 정렬 마스킹 매크로이다.

 

MALLOC_ALIGNMENT 값에서 -1을 함으로 이 값은 15가 되는데, 이를 16진수로 표현하면 0xF이다. 이진수로 표현하면 1111이다. 이 값을 통해서 추후 메모리 주소의 하위 4비트를 제거(또는 검사)한다.

 

MIN_CHUNK_SIZE 매크로는 메모리 할당에 사용할 수 있는 최소 청크 크기를 정의해준다. 

 

이 때 offsetof 함수는 첫 번째 인자로 넘겨준 구조체에서 두 번째 인자까지의 오프셋 값을 반환한다.

 

여기서는 malloc_chunk 구조체의 fd_nextsize 멤버 이전까지의 오프셋을 계산하므로, MIN_CHUNK_SIZE 는mchunk_prev_size(64bit에서 8) + mchunk_size(64bit에서 8) + fd(64비트 포인터, 8) + bk(64비트 포인터, 8) = 32 이다. 

 

MINZISE 매크로는 메모리 할당 시 정렬된 청크의 최소 크기를 정의한다. 

 

MIN_CHUNK_SIZE는 32, MALLOC_ALIGN_MASK는 15, ~MALLOC_ALIGN_MASK는 ~15로 16진수로는 0xFFFFFFF0이다. 따라서 이 값은 47 & 0xFFFFFFF0 = 32이다. 

 

request2size(req) 매크로는 사용자가 요청한 청크 크기를 실제 메모리 할당 크기로 변환하는 매크로이다. 

 

req 파라미터는 요청 크기를 의미하며, 이 req 값에다가 SIZE_SZ(=8) + MALLOC_ALIGN_MASK(=15) 를 더한 값이 MINSIZE 보다 작다면 MINSIZE 를 청크 크기로 사용하고, 그렇지 않다면 ((req) + 8 + 15) & 0xFFFFFFF0)을 사용한다.

 

예를 들어 요청 크기, 즉 req가 0x300 이라고 가정해보면 0x300 + 0x8(SIZE_SZ) + 0xF(MALLOC_ALIGN_MASK) = 0x317 이고 이는 MINSIZE=0x20(32) 보다 크므로 0x317 & 0xFFFFFFF0인 0x310 값을 실제로 할당받게된다.

만약 req 가 0x9 미만일 경우에는 MINSIZE 값인 0x20(32)를 쓸 것이다. (req 가 9 이상인 경우에는 항상 32보다 큰 값을 합으로 가지기 때문에, 역으로 보면 9보다 작은 경우에만 MINSIZE 를 크기로 할당한다.)

 

csize2tidx, usize2tidx 매크로는 청크 크기를 받아 tcache 배열의 인덱스를 계산하는 매크로이다. 

 

usize2tidx 는 최종적으로 csize2tidx 를 이용해서 계산된다. csize2tidx 는 입력받은 크기 x(request2size(req) 를 통해서 나온 정렬된 크기)를 인자로 받아서 idx 를 계산한다. 여기선 (x - 32(MINSIZE) + 16(MALLOC_ALIGNMENT) - 1) / 16(MALLOC_ALIGNMENT) 이다.

 

예를 들어 0x300 을 요청 크기(req)로 받아들였다고 가정해보자. usize2tidx 에 의해서 request2size(0x300) 을 통해서 구한 0x310이 csize2tidx 인자로 들어가게 된다.

이것을 위의 식에 대입해보면 (0x310 - 0x20 + 0x10 - 0x1) / 0x10 이며, 이 값은 0x2F(47)이 된다.

 

다시 말해서 0x300 크기의 청크를 할당하면 tcache 배열의 47번째 인덱스에 할당된다는 이야기이다. 

 

참고로 tcache의 최대 크기 1032 byte 를 넘는 1033 byte (0x409)는 인덱스를 계산해보면 64가 나오고, 이는 tcache 배열의 인덱스 범위를 초과한다(인덱스는 0~63까지 존재한다.)

 

Analyze:

위 코드는 요청한 청크 크기가 몇 번째 tcache 인덱스에 들어갈 지 계산해서 출력해준다.

 

만약 tcache 의 가용범위를 벗어나는 크기를 입력하면 "NOT IN TCACHE RANGE"를 출력해준다.

 

 

혹시 이것이 실제 힙 메모리 구조와 동일한 동작을 진행하는지 궁금해서 확인해보았는데, 실제 메모리 할당 시 청크의 크기를 결정하는 것은 이러한 알고리즘을 통해서 정해지지 않는다...

 

실제 청크 크기 정렬은 malloc.c 에 정의된 sysmalloc 이라는 함수에서 진행된다.

아래에 대략적인 코드를 가져왔다. (실제로는 더 길다)

 

void* sysmalloc(INTERNAL_SIZE_T nb, mstate av)
{
  mchunkptr old_top;
  INTERNAL_SIZE_T old_size;
  char*     brk;
  char*     snd_brk;
  INTERNAL_SIZE_T front_misalign;
  INTERNAL_SIZE_T correction;
  char*     aligned_brk;
  mchunkptr p;
  mchunkptr remainder;
  unsigned long remainder_size;
  INTERNAL_SIZE_T size;
  void*     new_top;
  void*     old_end;

  size = nb + MALLOC_ALIGNMENT;
  brk = (char*)(MORECORE(size));
  if (brk == (char*)(MORECORE_FAILURE)) {
    return 0;
  }

  /* Align the pointer */
  aligned_brk = (char*)align_ptr(brk);

  /* Calculate the offset */
  front_misalign = (INTERNAL_SIZE_T)(aligned_brk - brk);
  if (front_misalign > 0) {
    correction = MALLOC_ALIGNMENT - front_misalign;
    aligned_brk += correction;
  }

  /* The new top chunk starts at aligned_brk */
  new_top = aligned_brk;

  /* Update the top chunk size */
  p = (mchunkptr)new_top;
  p->size = (size - front_misalign) & ~PREV_INUSE;

  return chunk2mem(p);
}

 

핵심적인 부분만 추출해서 뽑아왔다.

 

이 코드를 보면 'front_misalign' 이라는 변수때문에 청크 크기가 오히려 줄어드는 경우도 있다는 걸 알 수 있다.

 

 예제 코드에선 청크의 크기가 무작정 늘어나는 경우밖에 보여주지 않는데, 실제로는 작아질 수도 있다는 이야기이다.

 

이 변수의 의의는 정렬된 청크의 앞 바이트를 제거하는 것이다. 참고로 front_misalign 변수는 정렬의 기준이 되는 매크로인 MALLOC_ALIGN_MASK 를 가지고 만들어진다. (이 함수에는 없고 malloc.c에 정의되어있다.)

 

Reference:

 

https://elixir.bootlin.com/glibc/glibc-2.27/source

Glibc source code (glibc-2.27) - Bootlin