Original post by Magnus, from the 0x00sec forum.

Introduction

Most beginners get lost when it comes to exploiting the heap. That’s because there are a lot of techniques that differ depending on the glibc version and other variables, which make them want to throw their computer in the trash.

But it’s not really that complicated. It’s just confusing at first. Stay with me, and I’ll show you the basic heap exploitation techniques and tell you how to move forward.

This article divided into 3 big parts:

1. Glibc Heap Internals
2. Techniques independent of glibc
3. Techniques dependent on glibc

We will talk about how heap works, the most common techniques that can be used everywhere, as well as more specific exploitation techniques that depend on the glibc version.

We will use GDB with the Peda extension (you can use gef or pwndbg if you want), strace, and heaptrace, so please install them first.

Glibc Heap Internals

Most of this section is simply copied from glibc wiki and other resources, so if you want, you can follow the links in References part and read the resources I have provided. More precisely, read them anyway if you want to deepen your knowledge.

From a programmer’s point of view, the heap is simply an alternative memory area to use. While the stack is structured and handled by the compiler, the heap is used more manually. This is true, but this view is too simplistic. In reality, the heap is more structured than the stack. It is divided into more parts and involves many operations, while the stack is quite simple. In this chapter, we will discuss how the heap is organized.

So, first of all, a “heap” is just an area in RAM, like a stack. All the headache magic lies in the logic of how the malloc() maps this area for you. And, like a stack, the heap is organized into several parts:

• Heap
• Arena
• Chunk

Heap

A heap is a single contiguous memory region holding (coalesceable) malloc_chunks. It is allocated with mmap() and always starts at an address aligned to HEAP_MAX_SIZE. (Source)
Each heap contains

1. heap_info structure
2. malloc_state structure
3. Chunks

heap_info is essentially just metadata for the heap, containing data such as size, pointer to the arena, etc.:

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  size_t pagesize; /* Page size used when allocating the arena.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-3 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

Source

When malloc_state, it’s a so called “Arena”

Arena

In order to efficiently handle multi-threaded applications, glibc’s malloc allows for more than one region of memory to be active at a time. Thus, different threads can access different regions of memory without interfering with each other. These regions of memory are collectively called “arenas”. There is one arena, the “main arena”, that corresponds to the application’s initial heap. There’s a static variable in the malloc code that points to this arena, and each arena has a next pointer to link additional arenas. (Source)

Let’s see what we have in arena

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags  */
  int flags;

  /* 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;
};

Source

Each arena keeps track of a special “top” chunk, which is typically the biggest available chunk, and also refers to the most recently allocated heap

“Bins” are another mechanism for optimizing the heap. They store “freed” chunks, so if the program needs to allocate a similar chunk, it will be much faster and more memory-efficient to take that chunk from the bin than to allocate a completely new one.

Fast: Small chunks are stored in size-specific bins. Chunks added to a fast bin (“fastbin”) are not combined with adjacent chunks - the logic is minimal to keep access fast (hence the name). Chunks in the fastbins may be moved to other bins as needed. Fastbin chunks are stored in an array of singly-linked lists, since they’re all the same size and chunks in the middle of the list need never be accessed.

Unsorted: When chunks are free’d they’re initially stored in a single bin. They’re sorted later, in malloc, in order to give them one chance to be quickly re-used. This also means that the sorting logic only needs to exist at one point - everyone else just puts free’d chunks into this bin, and they’ll get sorted later. The “unsorted” bin is simply the first of the regular bins.

Small: The normal bins are divided into “small” bins, where each chunk is the same size, and “large” bins, where chunks are a range of sizes. When a chunk is added to these bins, they’re first combined with adjacent chunks to “coalesce” them into larger chunks. Thus, these chunks are never adjacent to other such chunks (although they may be adjacent to fast or unsorted chunks, and of course in-use chunks). Small and large chunks are doubly-linked so that chunks may be removed from the middle (such as when they’re combined with newly free’d chunks).

Large: A chunk is “large” if its bin may contain more than one size. For small bins, you can pick the first chunk and just use it. For large bins, you have to find the “best” chunk, and possibly split it into two chunks (one the size you need, and one for the remainder). (Source)

Chunk

Chunks are the pieces of memory which programmers use when they call malloc. But under the hood, malloc allocate a little bit more memory to store malloc_chunk structure which is metadata for chunk.

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* bk;  /* for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

Source

Since all chunks are multiples of 8 bytes, the 3 LSBs of the chunk size can be used for flags. These three flags are defined as follows:

A (0x04)
Allocated Arena - the main arena uses the application’s heap. Other arenas use mmap’d heaps. To map a chunk to a heap, you need to know which case applies. If this bit is 0, the chunk comes from the main arena and the main heap. If this bit is 1, the chunk comes from mmap’d memory and the location of the heap can be computed from the chunk’s address.

M (0x02)
MMap’d chunk - this chunk was allocated with a single call to mmap and is not part of a heap at all.

P (0x01)
Previous chunk is in use - if set, the previous chunk is still being used by the application, and thus the prev_size field is invalid. Note - some chunks, such as those in fastbins (see below) will have this bit set despite being free’d by the application. This bit really means that the previous chunk should not be considered a candidate for coalescing - it’s “in use” by either the application or some other optimization layered atop malloc’s original code

Source

In summary

In this part we discussed the internals of glibc memory management. We will need this details when we start the actual hacking in other parts.
Modern glibc malloc also have Thread Local Cache (tcache), which we will cover later in Techniques dependent on glibc part.

References

glibc repo mirror in Github
glibc wiki
Azeria Labs - GLIBC HEAP (Part 1)
Azeria Labs - GLIBC HEAP (Part 2)
SploitFun understanding glibc malloc
HackTricks libc-heap

To comment or discuss this post, please join us on the 0x00sec forum.