[Heap Explploitation] ptmalloc2

Memory Allocator (Malloc)

• dlmalloc
• ptmalloc2 : glibc 메모리 할당자
• jemalloc
• tcmalloc
• libumem

Chunk

동적 할당된 힙 메모리는 chunk 라고 불리며, malloc_chunk 구조체를 사용한다.

• Allocate Chunk

  malloc , calloc 등 동적 메모리 할당 함수를 통해 할당된 chunk 이다.

• Free Chunk

  free 등 동적 메모리 해제 함수를 통해 해제된 chunk 이다..

• Top Chunk

  힙 메모리의 마지막에 위치해 있는 chunk 이다. 메모리 할당 요청이 들어왔을 때, 사용할 Free Chunk가 없을 때 Top Chunk에서 쪼개어 사용한다.

• Last Remainder Chunk

  Free Chunk가 쪼개지고 남은 chunk 이다. 연속된 작은 사이즈의 할당 요청이 들어왔을 때 비슷한 주소에 heap chunk가 할당되는 할당의 지역성을 유지시키기 위해 사용된다.

malloc_chunk structure

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      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;
};

prev_size

• 이전의 heap chunk가 해제되었을 경우 해제된 heap chunk의 크기를 저장한다.
• 이전의 heap chunk가 IN-USE chunk가 되거나, 이전 chunk가 해제되기 전까지는 이전 chunk의 데이터가 저장될 공간으로 사용된다.

size

• 현재 할당된 heap chunk의 크기를 저장한다.
• 맨 끝의 3bit는 flag 비트로 사용된다.
  • PREV_INUSE (P) : 이전 heap chunk가 해제된 경우 설정된다.
  • IS_MMAPPED (M) : mmap() 을 통해 할당 받은 Chunk일 경우 설정된다.
  • NON_MAIN_ARENA (A) : main_arena 가 관리하지 않는 Chunk 일 때 설정된다.

    /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
    #define PREV_INUSE 0x1
      
    /* extract inuse bit of previous chunk */
    #define prev_inuse(p)       ((p)->size & PREV_INUSE)
      
    /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
    #define IS_MMAPPED 0x2
      
    /* check for mmap()'ed chunk */
    #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
      
    /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
       from a non-main arena.  This is only set immediately before handing
       the chunk to the user, if necessary.  */
    #define NON_MAIN_ARENA 0x4
      
    /* check for chunk from non-main arena */
    #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
  

fd

• free 전

  실제로 데이터 영역의 시작 부분이기 때문에 해당 주소부터 데이터가 저장된다.

• free 후

  다음 Free Chunk의 주소가 저장된다.

bk

• 이전 Free Chunk의 주소가 저장된다.

fd_nextsize

• 크기가 큰 chunk 포인터가 저장되는 주소로 현재 heap chunk 보다 작은 heap chunk의 주소를 가리킨다.

bk_nextsize

• 크기가 큰 chunk 포인터가 저장되는 주소로 현재 heap chunk 보다 큰 heap chunk의 주소를 가리킨다.

Bins

Free Chunk(해제된 heap chunk)는 메모리 관리 효율을 높이기 위해서 bin 이라는 freelist 구조체를 통해 관리되는데, 크기에 따라서 다양한 bin 에 저장된다.

• 메모리 해제 시 해제하려는 영역을 bin에 추가, 할당 요청 시 bin 에 추가된 영역을 제거 후 해당 영역을 다시 사용한다.

Fastbin

fastbin에 포함되는 chunk 범위는 다음과 같다.

• 32비트 아키텍처 : 16 ~ 64바이트
• 64비트 아키텍처 : 32 ~ 128바이트

/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST            1
#endif

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
#endif

Smallbin

• 32비트 아키텍처 : ~ 512 바이트
• 64비트 아키텍처 : ~ 1024 바이트

#define NBINS             128
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)

Largebin

• 32비트 아키텍처 : 512 바이트 ~
• 64비트 아키텍처 : 1024 바이트 ~

#define largebin_index_32(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

#define largebin_index_32_big(sz)                                            \
  (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

#define largebin_index(sz) \
  (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
   : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
   : largebin_index_32 (sz))

Unsortedbin

fastbin을 제외한 해제된 모든 free chunk와 chunk 분할 후 남는 chunk는 unsorted bin에 먼저 저장된다.

• double-linked list로 관리하며 FIFO(First In First Out)을 사용한다.

Arena

Arena는 ptmalloc2에서 스레드 단위로 heap memory를 저장하는 장소이다.

main_arena

main_arena 는 malloc_state 구조체를 사용하여 heap memory를 관리한다.

• brk 시스템 콜을 사용하여 할당된 heap memory를 효율적으로 관리한다.

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

malloc_state 의 구조체는 다음과 같다.

• main_arena 는 mutex 를 통해 여러 스레드가 실행 중에 메모리 간섭을 방지한다.
• 또한 heap chunk를 관리하기 위한 배열이 선언되어 있다.

struct malloc_state
{
  /* Serialize access.  */
  mutex_t 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;
};