The art of exploiting heap overflow, part 5
The art of exploiting heap overflow, part 5
Memory chunks
All memory chunks of ptmalloc have same header structures (interchangeably we call it metadata), only depends on its status: if they are a free chunk or an allocated one. When we request a memory chunk from ptmalloc, its metadata is always allocated together with it, ptmalloc adds the size of its header to the request size and always stores its header in the beginning of a chunk. Thus, it is easy to find or modify its header given the address of the user data returned by malloc(). This is the fundamental of exploiting heap based overflow.
malloc()
For an allocated chunk, basically only its size needs to be stored, remember free() does not have a size parameter? You can think it as:
free()
size
struct malloc_chunk { INTERNAL_SIZE_T mchunk_prev_size; INTERNAL_SIZE_T mchunk_size;};
For a free chunk, it is usually put in a “freelist”, either singly linked or doubly linked. Thus its metadata has to contain one or two pointers to chain it, and the size. Something like:
struct malloc_chunk { INTERNAL_SIZE_T mchunk_prev_size; INTERNAL_SIZE_T mchunk_size; struct malloc_chunk* fd; struct malloc_chunk* bk;};
The pointer names are confusing, fd is short for forward and bk is short for backward. To make them more familiar, you can think fd as next and think bk as prev since they are for singly or doubly linked list.
fd
forward
bk
backward
fd
next
bk
prev
Note, in the code there is only one struct malloc_chunk, the pointers are “added” once we free() the chunk and are “erased” once we return it back to user again.
struct malloc_chunk
free()
Quiz: Given a memory address returned bymalloc(X), can you find out what X is?
malloc(X)
Now, the most important question, how does an arena manages free chunks? For performance consideration, each arena uses different kinds of lists to chain its free chunks, take a look at the core of an arena header:
struct malloc_state{ /* 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];};
As previously mentioned, memory chunks are not allocated directly by OS one by one each time, instead glibc caches them by:
For the first case, glibc employs a special “top chunk” (defined as top in struct malloc_state) which already represents “the rest” of an arena, it is the last resort for allocation, never linked in any freelist, and always sits on at top of an arena. It can grow, when an adjacent chunk being freed consolidates to it, or when the arena itself has to extend; it can shrink when we split a smaller chunk from it.
top
struct malloc_state
Splitting also happens when we can’t find an existing chunk with same size but have to find the next larger chunk to split. This is what binmap and last_remainder are used for. In this case, the remainder chunk is also put into unsorted bin.
binmap
last_remainder
For the second case, it depends on the size of the chunk, it is put into different lists or bins:
fastbinsY[]
struct malloc_state
fastbinsY[0]
fastbinsY[9]
- Normal bins: Defined as bins[] in struct malloc_state. There are 3 kinds of normal bins:
bins[]
struct malloc_state
2.1 Unsorted bins: bins[1] . This is a temporary bin which holds the chunks being moved to either small bins or large bins. This is mainly for reuse purpose. This is a doubly linked list and contains chunks with various sizes. Note: unsorted bin is the only place from where we move chunks to either small bins or large bins.
bins[1]
2.2 Small bins: bins[2] ~ bins[63] . Similar to fast bins, these 62 bins hold chunks of 8-byte, 16-byte, 24-byte… 496-byte. But, these chunks could be coalesced if adjacent. They are doubly linked in FIFO order.
bins[2]
bins[63]
2.3 Large bins: bins[64] ~ bins[126] . They hold chunks between 512 bytes and 128Kbytes. Each bin holds a different range of sizes, therefore they have to be sorted (in decreasing order) and coalesced if necessary.
bins[64]
bins[126]
Chunks larger than 128K are directly allocated by mmap().
mmap()
Q: How fast bins have overlaps with small bins?
Chunks are not moved from fast bins to small bins, however, if a chunk is allocated from a small bin, it will be possibly returned to a fast bin after freed.
Q: Do two successive malloc()’s always allocate adjacent chunks?
Of course not. This totally depends on the state of the heap, for a daemon process running for a long time, its heap could be fragmented a lot, it is really hard to know where the next malloc() gets a free chunk. The existing articles on Internet show you naive examples just for education purpose, they start from the initial state so their malloc()’s are easy to predict. Do not mislead by the illusion.
Clearly, ptmalloc is a first-fit memory allocator.