Heap Basics

Understanding the basics of the heap

Malloc Structure

// https://github.com/bminor/glibc/blob/master/malloc/malloc.c
struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk, if it is free. */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;                /* double links -- used only if this chunk is 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 this chunk is free. */
  struct malloc_chunk* bk_nextsize;
};

typedef struct malloc_chunk* mchunkptr;

The important thing is how the chunk's user data section contains fd and bk pointers to other free chunks which is usually exploited

Example - Allocated Chunk

Take note of where the User Data is placed

Example - Freed Chunk

Notice the overlap at offset 0x10?

On x64 systems, the heap chunk header is a size of 0x10 bytes and 0x8 on x32.

Binning

When a chunk is freed, it will usually insert it in one of the bin lists. Upon another allocation, the heap will see if there are bins that fit the size required that could be reused for memory efficiency.

Type	Size	Description
Fast Bins	0x20 - 0x80	Consist of 7 linked lists referred to by their idx Uses LIFO Usually the first list libc looks at (if tcache is not available)
Tcache Bins	0x18 - 0x408 (x64) 0xC - 0x204 (x32)	Similar to fastbins but faster, thread specific. Can only hold 7 chunks at a specific time, will use other bins if full

Unsorted Bins

• Cache used to make memory allocation quicker

• When a program frees a chunk and chunk cannot be allocated in a tcache or fast bin and is not colliding with the top chunk (holds the large unallocated data)

• It first tries to merge it with any neighbouring free chunks to create a larger block of free memory. Then, it places this new chunk in a general bin called the "unsorted bin" -> will be useful later for libc leaks

To prevent consolidation with top chunk, allocate a small chunk in between our freed chunks and the top chunk, just to prevent that consolidation.

Allocation and Freeing Summary (no checks - got from hacktricks)

Allocation Order

1. __libc_malloc tries to get a chunk from the tcache, if not it calls _int_malloc

2. _int_malloc :

   1. Tries to generate the arena if there isn't any

   2. If any fast bin chunk of the correct size, use it

      1. Fill tcache with other fast chunks

   3. If any small bin chunk of the correct size, use it

      1. Fill tcache with other chunks of that size

   4. If the requested size isn't for small bins, consolidate fast bin into unsorted bin

   5. Check the unsorted bin, use the first chunk with enough space

      1. If the found chunk is bigger, divide it to return a part and add the reminder back to the unsorted bin

      2. If a chunk is of the same size as the size requested, use to to fill the tcache instead of returning it (until the tcache is full, then return the next one)

      3. For each chunk of smaller size checked, put it in its respective small or large bin

   6. Check the large bin in the index of the requested size

      1. Start looking from the first chunk that is bigger than the requested size, if any is found return it and add the reminders to the small bin

   7. Check the large bins from the next indexes until the end

      1. From the next bigger index check for any chunk, divide the first found chunk to use it for the requested size and add the reminder to the unsorted bin

   8. If nothing is found in the previous bins, get a chunk from the top chunk

   9. If the top chunk wasn't big enough enlarge it with sysmalloc

Free Order

1. If the address is null don't do anything

2. If the chunk was mmaped, mummap it and finish

3. Call _int_free:

   1. If possible, add the chunk to the tcache

   2. If possible, add the chunk to the fast bin

   3. Call _int_free_merge_chunk to consolidate the chunk is needed and add it to the unsorted list

Exploitation

Copied from here

+--------------------+----------------------------+-----------------------+
|   Bug Used         |  Bin Attack                |   House               |
+--------------------+----------------------------+-----------------------+
|                    |  Fast Bin Attack           |   House of Spirit     |
|   Double Free      |  tcache attack             |   House of Lore       |
|   Heap Overflow    |  Unsorted Bin Attck        |   House of Force      |
|   Use After Free   |  Small / Large Bin Attck   |   House of Einherjar  |
|                    |  Unsafe Unlink             |   House of Orange     |
+--------------------+----------------------------+---------------------

References

malloc & sysmalloc | HackTricks

free | HackTricks

Heap Exploitation - Nightmare