Heap-Exploitation-base-knowledge-notes

发表于 | 分类于 | | 本文总阅读量 次

Heap Exploitation

Base Knowledge

malloc_chunk

1
2
3
4
5
6
7
8
9
10
11
struct malloc_chunk{
    INTERNAL_SIZE_T        mchunk_prev_size;    /*Size of previous chunk (if free)        */
    INTERNAL_SIZE_T        mchunk_size;         /*Size in bytes, including overhead        */
    struct malloc_chunk* fd;                    /*double links  ----  used only if free.*/
    struct malloc_chunk* bf;
    /*only used for large blocks: pointer to next larger size*/
    struct malloc_chunk* fd_nextsize;
    struct malloc_chunk* bk_nextsize;
}
typedef struct malloc_chunk* mchunkptr;

Allocated chunk

mem is the pointer which is returned to the user.

Free chunk

Free chunks maintain themselves in a circular doubly linked list.

  1. P(PREV_INUSE): 0 when previous chunk (not the prev chunk in the linked list, but the one directly before it in memory) is free (and hence the size of previous chunk is stored in the first field). The very first chunk allocated has this bit set. If the bit set to 1, we cannot determine the size of the previous chunk.
  2. M(IS_MMAPPED): The chunk is obtained through mmap. The other two bits are ignored. mmapped chunks are neither in an arena, not adjacent to a free chunk.
  3. A(NON_MAIN_ARENA): 0 for chunks in the main arena. Each thread spawned received its own arena and for those chunks, this bit is set.

PS: fastbins are not included in the set described above.

malloc_state

This structure represents the details of an Arena. The main threads arena is a global variable and not part of the heap segment.Arena headers( malloc_chunk structures) for other threads are themselves stored in the heap segment. Non main arena can have multiple heaps associated with them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct    malloc_state {
    __libc_lock_define (, mutex);
    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 bin[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 threands 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;

Bins and Chunks

A bin is a list (doubly or singly linked list) of free (non-allocated) chunks. Bins are differentiated based on the size of chunks they contain:

  1. Fastbin
  2. Unsorted bin
  3. Small bin
  4. Large bin

PS: Unsorted, small and large bins are maintained using a single array:

1
2
typedef struct malloc_chunk * mchunkptr;
mchunkptr bins[]; //Array of pointers to chunks

Fastbins

The 10 types of fastbins each have chunks of size: 16, 24, 32, 40, 48, 56, 64, 72, 80 and 88. Sizes mentioned here include metadata as well. To store chunks, 4 fewer bytes will be available (on a platform where pointers use 4 bytes). Only prev_size and size field of this chunk will hold meta data for allocated chunks.

PS: No two contiguous free fast chunks coalesce together, which is not different with normal bins.

Unsorted bin

There is only 1 unsorted bin. Small and large chunks, when freed, end up in this bin. The primary purpose of this bin is to act as a cache layer to speed up allocation and deallocation requests.

Small bins

Each small bin maintains a doubly-linked list. Insertions happen at “HEAD” while removals happen at the ‘TAIL’(in a FIFO manner).
The 64 bins have sizes: 16, 24, …… 504 bytes.

PS: While freeing, small chunks may be coalesced toghether before ending up in unsorted bins.

Large bins

Each large bin maintains a doubly-linked list. A particular chunks of different sizes, sorted in decreasing order. Insertions and removal happed at any position within the list.

The first 32 bins contain chunks which are 64 bytes apart:

1st bin: 512 - 568 bytes
2nd bin: 576 - 632 bytes
…
…

Top chunk

It is the chunk which borders the top of an arena. While servicing ‘malloc’ requests, it is used as the last resort. If still more size is required, it can grow using the sbrk system call. The PREV_INUSE flag is always set for the top chunk.

Last remainder chunk

It is the chunk obtained from the last split. Sometimes, when exact size chunks are not available, bigger chunks are split into two. One part is returned to user whereas the other becomes the last remainder chunk.

Internal functions

arena_get(ar_ptr, size)

Acquires an arena and locks the corresponding mutex.

  • ar_ptr is set to the pointer to the corresponding arena.
  • size is set to how much memory will be required immediately.

sysmalloc [TODO]

sysmalloc handles malloc cases requiring more memory from the system.
On entry, it is assumed that assumed that av->top does not have enough space to service request for nb bytes, thus requiring that av->top be extended or replaced.

void alloc_perturb(char *p, size_t n)

If perturb_byte (tunable parameter for malloc using M_PERTURB) is non-zero (by default it is 0), sets the n bytes pointed to by p to be equal to perturb_byte ^ 0xff.

调用alloc_perturb对用户使用的内存进行初始化，之后就会返回该内存的指针（在_int_malloc(mstate av, size_t bytes)函数中)

void free_perturb(char *p, size_t n)

If perturb_byte (tunable parameter for malloc using M_PERTURB) is non-zero (by default it is 0), sets the n bytes pointed to by p to be equal to perturb_byte.

void malloc_init_state(mstate av)

  1. For non fast bins, create empty circular linked lists for each bin.
  2. Set FASTCHUNKS_BIT flag for av.
  3. Initialize av->top to the first unsorted chunk.

This is a defined macro which removes a chunk from a bin.

  1. Check if chunk size is equal to the previous size set in the next chunk.
  2. Check if P->fd->bk == P and P->bk->fd == P.
  3. Adjust forward and backward pointers of neighboring chunks (in list) to facilitate remova:
    1. Set P->fd->bk = P->bk
    2. Set P->bk->fd = P->fd

void malloc_consolidate(master av)

This is a specialized version of free().

malloc_consolidate函数主要完成以下几个功能：

  1. 首先判断当前malloc_state结构体中的fast bin是否为空，如果为空就说明整个malloc_state都没有完成初始化，需要对malloc_state进行初始化。
  2. malloc_state的初始化操作由函数malloc_init_state(av)完成，该函数先初始化除fast bin之外的所有的bins，再初始化fast bins。