Heap analysis with radare2

Before diving into radare2, I'm going to introduce a series of concepts related to heap that will be necessary to understand to proceed with the post. Anyway, I will explain them further in their respective sections.

Allocator

An allocator is a module that manages the heap of a program. Thus, it is easier for a programmer to use it, through the malloc and free functions. In this post, we will review the glibc allocator, which is a fork of the ptmalloc2 allocator. However, there are more allocators, like jemalloc or tcmalloc.

Chunks

Chunks, as the name suggests, are chunks of memory that can be used to store any type of data. This are allocated for the program by using the malloc, calloc or realloc functions, and released with free. Chunks are found in a memory region known as heap.

Heap

A heap is a contigous region of memory which can be splitted to create chunks. Each heap belongs to an arena, and several can exists in the same program. The main heap is allocated in the memory region named [heap].

Arena

A arena is composed by a malloc_state structure, where bins are stored, and one or several heaps. A program can hold many arenas, that are created when new threads are spawned. The initial arena is the main_arena.

Bins

Bins are lists of chunks that are available to be used. There are different types of bins, that are used based on the situation. These are:

• Unsorted Bin -> Bin to insert chunks quickly, before insert them in other bins.

• Small bins -> For small chunks.

• Large bins -> For large chunks.

• Fast bins -> Cache bins for very small chunks.

• Tcaches -> Cache bins that allows to several threads to access to small chunks without blocking the arena.

Also, I will let explanations for some interesting phenomenons that happens in the memory management:

Consolidation

It happens when a process asks for a chunk bigger than those that a small bin can contain (and also the fast bins). In the consolidation the chunks of the fast bins are moved to the unsorted bin, thus allowing these to merge between them to avoid fragmentation, since it is expected that the program will require big chunks.

Tcaches Recharging

When the allocator is searching for chunks in a fast bin or an small bin, it takes the opportunity to moved as many chunks to the tcaches as it can. This also happens when it is discarding chunks from the unsorted bin. This way the tcaches are full of chunks and the locks of the arena are decreased.

In this post, I will describe these entities with more detail. However, in case you need more help to understand the topic, you can check the following resources:

• glibc wiki: MallocInternals

• Heap exploitation book

• Azeria Labs: Understanding the glibc heap implementation

• Understanding glibc malloc

Moreover, in order to practice, you should check the how2heap repository, which teach different heap exploiting techniques.

Furthermore, I would like to clarify that the data shown in this article was get from my personal experiments and revisions of code of different glibc versions. To perform my tests, I have used the glibc versions 2.32, 2.28 and 2.19, in a x86 computer, with programs of 32 and 64 bits.

Notwithstanding, glibc allows to adjust several parameters that can change its behaviour, so use this as an orientation, but not as an absolute truth. If you are not sure about a certain aspect, the best approach is to do your own experiments. ;)

Now, let's go to the topic.

Note: You shouldn't have too much problem with the radare2 commands shown in this post, even if you are a radare2 begginer. Otherwise, you can check any tutorial like this by Megabeets.

The first thing to do is open our program with radare2. We need to start radare2 with the debugger in order to analyze the heap, so we have to use the flag -d in the command line:

r2 -d ./heapshow

After radare2 is running with a program (and a code analysis was done if it is needed), we can set a breakpoint with db to stop the program execution and exploring the memory. You can also use Ctrl-c in the middle of the execution to let radare2 to take the control.

Once the execution was stopped, to explore the heap you can use the commands of the dmh group.

• d -> Debug commands.

• dm -> Memory maps commands.

• dmh -> Heap commands.

Moreover, you can view the heap commands help with dmh?:

[0x5624802e1193]> dmh?
Usage:  dmh   # Memory map heap
| dmh                                          List chunks in heap segment
| dmh @[malloc_state]                          List heap chunks of a particular arena
| dmha                                         List all malloc_state instances in application
| dmhb @[malloc_state]                         Display all parsed Double linked list of main_arena's or a particular arena bins instance
| dmhb [bin_num|bin_num:malloc_state]          Display parsed double linked list of bins instance from a particular arena
| dmhbg [bin_num]                              Display double linked list graph of main_arena's bin [Under developemnt]
| dmhc @[chunk_addr]                           Display malloc_chunk struct for a given malloc chunk
| dmhf @[malloc_state]                         Display all parsed fastbins of main_arena's or a particular arena fastbinY instance
| dmhf [fastbin_num|fastbin_num:malloc_state]  Display parsed single linked list in fastbinY instance from a particular arena
| dmhg                                         Display heap graph of heap segment
| dmhg [malloc_state]                          Display heap graph of a particular arena
| dmhi @[malloc_state]                         Display heap_info structure/structures for a given arena
| dmhm                                         List all elements of struct malloc_state of main thread (main_arena)
| dmhm @[malloc_state]                         List all malloc_state instance of a particular arena
| dmht                                         Display all parsed thread cache bins of all arena's tcache instance
| dmh?                                         Show map heap help

The description gives you an idea of what can be done with each one, but I will show you some examples to a better understanding.

Tip: You can use ? after a command to show it help.

An arena is composed by a malloc_state and one or various heaps. Also, a process can hold one or many arenas, based on the threads number. The threads can share an arena if it is necessary. The initial arena is called main_arena.

To identify the arenas of a process, the malloc_state structures must be located in memory. You can do this with the dmha command:

[0x55e517c4f1da]> dmha
main_arena @ 0x7f393d58fc40
thread arena @ 0x7f3938000020

The output shows the addresses of the arenas malloc_states. In this process, apart from the main_arena, there is another arena that is probably being used by a second thread.

Once arenas are located, radare2 can be used to display more details of each one. In case of examining the main_arena, it is not necessary to specify its memory address, since radare2 uses it automatically.

Each arena has a malloc_state structure. Its definition is the following:

# define INTERNAL_SIZE_T size_t
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk *mfastbinptr;

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

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

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

It stores plenty of information about the arena. The most interesting members are the following:

• fastbinsY -> The fast bins, which are 10. For each one, there is a pointer to the first chunk in the fast bin. In there are no chunks, the pointer is set to 0 (NULL).

• top -> The address of the heap top chunk.

• last_remainder -> The address of the last_remainder chunk. When a chunk is splitted into 2, in order to create an smaller chunk to return to the program, the chunk that remains free is the last_remainder. It is referenced for efficiency.

• bins -> The bins, which are 127, although the first isn't used. Inside this attribute the unsorted bin, the small bins and the large bins are contained. For each bin, 2 pointers are used, fd e bk, that points to the first and last chunk of the bin. In case of bin is empty, then this pointers points to the entry itself.

• next -> The address of the next malloc_state.

• system_mem -> Current heap size.

In order to show an arena malloc_state, you can use the dmhm command. If not address is specified, then it shows the info about the main_arena:

[0x55e517c4f1da]> dmhm
malloc_state @ 0x7f3938000020

struct malloc_state main_arena {
  mutex = 0x00000000
  flags = 0x00000002
  fastbinsY = {
 Fastbin 01
 chunksize: == 0032 0x0,
 Fastbin 02
 chunksize: == 0048 0x0,
 Fastbin 03
 chunksize: == 0064 0x0,
 Fastbin 04
 chunksize: == 0080 0x0,
 Fastbin 05
 chunksize: == 0096 0x0,
 Fastbin 06
 chunksize: == 0112 0x0,
 Fastbin 07
 chunksize: == 0128 0x0,
 Fastbin 08
 chunksize: == 0144 0x0,
 Fastbin 09
 chunksize: == 0160 0x0,
 Fastbin 10
 chunksize: == 0176 0x0,
}
  top = 0x7f3938000f00,
  last_remainder = 0x0,
  bins {
 Bin 001: Unsorted Bin [ chunksize: undefined 0x7f3938000020->fd = 0x7f3938000080, 0x7f3938000020->bk = 0x7f3938000080, 
 Bin 002:              ┌ chunksize: == 000032  0x7f3938000030->fd = 0x7f3938000090, 0x7f3938000030->bk = 0x7f3938000090, 
 Bin 003:              │ chunksize: == 000048  0x7f3938000040->fd = 0x7f39380000a0, 0x7f3938000040->bk = 0x7f39380000a0, 
 ......................│....
 Bin 031:              │ chunksize: == 000496  0x7f3938000200->fd = 0x7f3938000260, 0x7f3938000200->bk = 0x7f3938000260, 
 Bin 032:   Small Bins │ chunksize: == 000512  0x7f3938000210->fd = 0x7f3938000270, 0x7f3938000210->bk = 0x7f3938000270, 
 Bin 033:              │ chunksize: == 000528  0x7f3938000220->fd = 0x7f3938000280, 0x7f3938000220->bk = 0x7f3938000280, 
 ......................│....
 Bin 063:              │ chunksize: == 001008  0x7f3938000400->fd = 0x7f3938000460, 0x7f3938000400->bk = 0x7f3938000460, 
 Bin 064:              └ chunksize: == 001024  0x7f3938000410->fd = 0x7f3938000470, 0x7f3938000410->bk = 0x7f3938000470, 
 Bin 065:              ┌ chunksize: >= 001088  0x7f3938000420->fd = 0x7f3938000480, 0x7f3938000420->bk = 0x7f3938000480, 
 Bin 066:              │ chunksize: >= 001152  0x7f3938000430->fd = 0x7f3938000490, 0x7f3938000430->bk = 0x7f3938000490, 
 ......................│....
 Bin 095:              │ chunksize: >= 003008  0x7f3938000600->fd = 0x7f3938000660, 0x7f3938000600->bk = 0x7f3938000660, 
 Bin 096:   Large Bins │ chunksize: >= 003072  0x7f3938000610->fd = 0x7f3938000670, 0x7f3938000610->bk = 0x7f3938000670, 
 Bin 097:              │ chunksize: >= 003136  0x7f3938000620->fd = 0x7f3938000680, 0x7f3938000620->bk = 0x7f3938000680, 
 ......................│....
 Bin 126:              │ chunksize: >= 524288  0x7f39380007f0->fd = 0x7f3938000850, 0x7f39380007f0->bk = 0x7f3938000850, 
 Bin 127:              └ chunksize: remaining 0x7f3938000800->fd = 0x7f3938000860, 0x7f3938000800->bk = 0x7f3938000860, 
  }
  binmap = {0x0,0x0,0x0,0x0}
  next = 0x7f393d58fc40,
  next_free = 0x0,
  system_mem = 0x21000,
  max_system_mem = 0x21000,
}

(The output is stripped for the sake of space)

In this output we can see different information. For example, there are no chunks in the fast bins, the heap size is 0x21000 bytes and there isn't last remainder.

Wait, where are the tcaches? Well, they are in other place since they were created to avoid threads from blocking the malloc_state. The tcaches are stored in another place, in the tcache_perthread_struct, which can be found in the heap (since the glibc version 2.26).

Chunks are chunks of memory from heap that are created through calls to the malloc family and released by using free.

At the beginning, the heap only has one chunk, the top chunk, and when new chunks are requested, the top chunk is splitted to create new chunks of the required size. In case of the requested chunk size is too big, then the chunk is allocated by using mmap.

Moreover, for efficiency reasons, the chunks are aligned to 8 bytes addreses in 32 bits and to 16 bytes in 64 bits. This means that the chunk size is always a multiple of 8 in 32 bits and a multiple of 16 in 64 bits. However, there is an exception. Since glibc 2.26, in x86 or i386 architecture, used in most of the personal computers and servers, the chunks are always aligned to 16, regarless of the program bits.

Furthermore, cause chunks are aligned to certain memory addresses, it is not possible to create a chunk of any size, so several malloc invocations with different sizes in a near range creates a chunk of the same size.

For instance, both malloc(100) and malloc(101) would reserve a chunk of the same size, that would be 112 bytes in 64 bits. In case you want to calculate the chunk size based on a malloc call size, you can use the following snippet or the gmcalc tool.

You can check the program architecture and bits in radare2 with i:

[0x7f8491e94090]>i~machine[1-]
AMD x86-64 architecture
[0x7f8491e94090]> i~bits[1]
64

This time we have a x86 program of 64 bits.

In order to get the glibc version, you can look the memory maps with dm and search for libc:

[0x557602f15189]> dm~libc:0[9]
/usr/lib/x86_64-linux-gnu/libc-2.32.so

You can spot the version 2.32 in the glibc filename.

Back to the topic, in every chunk we can find the malloc_chunk structure:

# define INTERNAL_SIZE_T size_t

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;

  /* 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;
};
typedef struct malloc_chunk* mchunkptr;

Note: The INTERNAL_SIZE_T type is a alias for size_t, which is 8 bytes long in 64 bits and 4 bytes in 32 bits.

Note: The member mchunk_prev_size is known as prev_size in older versions, so I will use this last name since is more compact. Same to mchunk_size, which was usually called size.

The prev_size (mchunk_prev_size) field indicates the previous chunk size when it is free. In the other case, the previous chunk can use this prev_size field to store arbitrary data.

       .-----------.
       | prev_size |
       | size      | free chunk
 chunk | fd        |
       | bk        |
    ---|-----------|---
       | prev_size | <- previous chunk size
       | size      | allocated chunk
 chunk | prevdata  |
       | prevdata  |
    ---|-----------|---  
       | prevdata  | <- previous chunk data
 chunk | size      |     
       | ....      |     
       '-----------'

When the previous chunk is released, then the glibc writes in the prev_size field it size. Also, the flag PREV_INUSE of the size field is set to 0, as we will see.

The size (mchunk_size) field indicates the chunk size, it includes the header (prev_size + size).

In 32 bits, the minimum chunk size is 16 bytes, and 32 bytes in 64 bits. Therefore, even the calls to malloc(0) will return a chunk of these sizes:

• 32 bits: malloc(0) -> 16 bytes. 8 bytes of data and 8 bytes of header.

• 64 bits: malloc(0) -> 32 bytes. 16 bytes of data and 16 bytes of header.

Moreover, since every chunk is a multiple of 8, then the 3 least significant bits aren't used to indicate the size. These bits are used as flags with special meanings:

• P (PREV_INUSE) -> First bit is set (0x1) if the previous chunk is free.

• M (IS_MMAPPED) -> Second bit is set (0x2) if the chunk was created with mmap.

• N ou A (NON_MAIN_ARENA) -> Third bit is set (0x4) if the chunk is not in the main_arena.

      chunk
 .--------------.
 | prev_size     |
 | size  |N|M|P| | <-- special flags
 | fd            |
 | bk            |
 | fd_nextsize   |
 | bk_nextsize   |
 '---------------'

The next fields, fd and bk, are pointers used by the free chunks in the bins to create links by pointing to the next an previous chunk in the same bin, respectively.

                 .----------------------------------------------------------.
                 |   entry               chunk                  chunk       |
                 |   .----.          .-----------.          .-----------.   |
                 '-> | XX | <-.  .-> | prev_size | <-.  .-> | prev_size | <-|--.
                     | YY |   |  |   | size      |   |  |   | size      |   |  |
malloc_state.bins[i] | fd |---|--'   | fd -------|---|--'   | fd -------|---'  |
                   .-| bk |   '------| bk        |   '------| bk        |      |
                   | '----'          '-----------'          '-----------'      |
                   '-----------------------------------------------------------'

Otherwise, when the chunk is being used, these pointers are useless and their space can store arbitrary data of the program. Actually, when a chunk is allocated by using malloc, the returned pointer doesn't point to the beginning of the chunk, but fd address.

                  chunk
              .-----------.
              | prev_size |
              | size      |
malloc(x) --> | fd        |
              | bk        |
              '-----------'

Lastly, the pointers fd_nextsize and bk_nextsize are used by large bins, that contains chunks with different sizes. Thus, these pointers are used to point to the beggining of the chunks with the next (larger) or previous (smaller) size, respectively.

    .------------<-------------------<-----------------------<----------------------<---.
    |   entry               chunk                  chunk                    chunk       |
    |   .----.        .-------------.         .------------.          .-------------.   |
    '-> | XX |<-.  .->| prev_size   |<--. .-> | prev_size   |<-.  .-->| prev_size   | <-|--.
        | YY |  |  |  | size (0x520)|   | |   | size (0x520)|  |  |   | size (0x510)|   |  |
bins[i] | fd |--|->'  | fd ---------|>--|-'   | fd          |>-|--|   | fd ---------|>--'  |
      .-| bk |  '----<| bk          |   |----<| bk          |  '--|--<| bk          |      |
      | '----'        | fd_nextsize |>. |     | fd_nextsize |     |   | fd_nextsize |>-.   |
      |             .<| bk_nextsize | | |     | bk_nextsize |     | .<| bk_nextsize |  |   |
      |             | '-------------' | |     '-------------'     | | '-------------'  |   |
      |             '----------->-----'-|->--------->---------->--' |                  |   |
      |                                 |                           |                  |   |
      |                                 '---<---------------<-------'---<-------<------'   |
      |                                                                                    |
      '------>--------->----------------->------------------>----------------->------------'

Ultimately, a chunk can hold store different information based on its state:

   allocated           free               free
                                       (large bin)
 .-----------.     .-----------.     .-------------.
 | prev_size |     | prev_size |     | prev_size   |
 | size      |     | size      |     | size        |
 | userdata  |     | fd        |     | fd          |
 | userdata  |     | bk        |     | bk          |
 | userdata  |     | userdata  |     | fd_nextsize |
 | userdata  |     | userdata  |     | bk_nextsize |
 | userdata  |     | userdata  |     | userdata    |
 | userdata  |     | userdata  |     | userdata    |
 '-----------'     '-----------'     '-------------'

It should be noted that in the moment a chunk is released by free, the data remains unaltered, except for those fields overwritten with the pointers used by the bins. It is responsibility of the programmer to erase that data and/or assume that chunks will contain "random" data.

To show a chunk in radare2, you can use the dmhc command with its address preceded by @. For example dmhc @0x5583f1f1f270:

[0x5583f0e61282]> dmhc @0x5583f1f1f270
struct malloc_chunk @ 0x5583f1f1f270 {
  prev_size = 0x0,
  size = 0x20,
  flags: |N:0 |M:0 |P:1,
  fd = 0x5583f1f1f2a0,
  bk = 0x5583f1f1f010,
}
chunk data = 
0x5583f1f1f280  0x00005583f1f1f2a0  0x00005583f1f1f010   .....U.......U..

In this case the chunk is in a bin (it is not indicated in the chunk, but I'm telling you). Thus fd and bk point to other bin chunks (or the bin entry in the malloc_state).

You can note that chunk data shows the same bytes as fd and bk, this is because when chunk is being used, data starts in fd.

The following example shows a used chunk:

[0x5624802e1193]> dmhc @0x562482199250
struct malloc_chunk @ 0x562482199250 {
  prev_size = 0x0,
  size = 0x410,
  flags: |N:0 |M:0 |P:1,
  fd = 0x6f77206f6c6c6568,
  bk = 0xa646c72,
  fd-nextsize = 0x0,
  bk-nextsize = 0x0,
}
chunk data = 
0x562482199260  0x6f77206f6c6c6568  0x000000000a646c72   hello world.....
0x562482199270  0x0000000000000000  0x0000000000000000   ................
...
...

Here, you can appreciate that fd and bk values are too weird to be in a bin, and chunk data shows that data is the string hello world, so you can imagine that chunk is being used, even if it is not explicitly indicated in the chunk metadata (we should check the next chunk P flag).

If you don't specify an address, dmhc will try to parse the current address as a chunk. This can lead to parse weird data like the following:

[0x55cb6f22e1cc]> dmhc
struct malloc_chunk @ 0x55cb6f22e1cc {
  prev_size = 0xbf00000e7f358d48,
  size = 0xfffe73e800000000,
  flags: |N:0 |M:0 |P:1,
  fd = 0xc3c900000000b8ff,
  bk = 0x80c48348e5894855,
  fd-nextsize = 0x358d480000001dba,
  bk-nextsize = 0x1bf00000e72,
}
chunk too big to be displayed

We can see that chunk size is huge, so we can imagine that there is no chunk in that address.

Heaps are large contigous memory regions, where chunks are created. The main heap is created with the sbrk syscall and its memory region is called [heap]. The rest of the heaps are created through mmap.

As we said before, when it is created, a heap only contains a big chunk called top chunk, that is splitted to create new chunks when their are required.

Moreover, when it is necessary, the heap size can be increased, by using sbrk or mmap (depends on how the heap was created).

    initial heap                 heap                       heap
   .-----------.             .-----------.             .-----------.
   |           |   malloc    |   chunk   |             |   chunk   |
   |           | ----------> |           |             |           |
   |           |             |-----------|             |-----------|
   |           |   malloc    |   chunk   |             |   chunk   |
   |           | ----------> |           |             |           |
   | top_chunk |             |-----------|             |-----------|
   |           |             |           |   malloc    |   chunk   |
   |           |             | top_chunk | ----------> |           |
   |           |             |           |             |-----------|
   |           |             |           |   malloc    |   chunk   |
   '-----------'             '-----------' ----------> |           |
                                              |        |-----------|
                                              | sbrk   |           |
                                              '------> | top_chunk |
                                                       |           |
                                                       '-----------'

This scheme shows how the top_chunk is splitted after several malloc calls. Also sbrk is used when more heap is required.

We also have to know that huge chunks are created by calling mmap directly, without using any heap.

You can check if the main heap exists by examinating the memory maps with dm:

[0x5614183471c2]> dm~heap]
0x0000561418c3f000 - 0x0000561418c60000 - usr   132K s rw- [heap] [heap]

In order to list the heap chunks, you can use the dmh command:

[0x5564c637d1dd]> dmh

  Malloc chunk @ 0x5564c76f9250 [size: 0x3f0][free]
  Malloc chunk @ 0x5564c76f9640 [size: 0x120][allocated]
  Top chunk @ 0x5564c76f9760 - [brk_start: 0x5564c76f9000, brk_end: 0x5564c771a000]

You should be able to examinate the heap of any arena, however, when I tried to show the heap of a thread arena, radare2 indicates that it is corrupted:

[0x56159e0e21d8]> dmha
main_arena @ 0x7f6066b3fc40
thread arena @ 0x7f6060000020
[0x56159e0e21d8]> dmh 0x7f6060000020

  Malloc chunk @ 0x7f6060000b50 [corrupted]
   size: 0x0
   fd: 0x0, bk: 0x0

  Top chunk @ 0x7f6060000f00 - [brk_start: 0x7f6060000000, brk_end: 0x7f6060021000]

I reported this issue so I hope it will be resolved. Moreover, when I run the program in 32 bits, radare2 shows perfectly the thread arena, however the main_arena is corrupted. ¯\_(ツ)_/¯

Additionally, the heaps created by mmap hold a heap_info structure at the beginning:

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.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

This structure indicates, in the ar_ptr member, the address of the arena to which the heap belongs.

We can inspect the heap_info of the arena heaps with dmhi:

[0x559dfb80022e]> dmhi @0x7f3bd8000020
malloc_info @ 0x7f3bd8000000 {
  ar_ptr = 0x7f3bd8000020
  prev = 0x0
  size = 0x21000
  mprotect_size = 0x21000
}

However, due to the main arena is in a predefined position, a heap_info structure is not necessary. Therefore radare2 will return the following error if you try to inspect the heap_info of the main_arena:

[0x559dfb80022e]> dmhi @0x7f3bdd14cba0
main_arena does not have an instance of malloc_info

Why does it say malloc_info instead of heap_info? I'm don't know…

Bins are lists with chunks that are not being used. A chunk must be in one bin at the same time. The bin choosen to insert a chunk is a complex topic, which depends heavily on the chunk size, but also in other optimization factors.

Actually, the algorithms used to insert and remove chunks from bins are designed to be efficient. As a consequence, they can behave in a unpredictable way at first sight. The best approach to understand them is to play with a program to become familiar with the bins behaviour.

There are 5 types of bin, that can be divided in 2 groups. The "regular" bins or double linked, and the cache bins or singled linked.

The doubled linked bins use the fd and bk pointers. They are FIFO (First In First Out) queues, where the chunks are inserted at the beginning and searched starting by the end. These bins are:

• Unsorted bin -> Bin where chunks are inserted without any order, before being inserted in large bins or small bins.

• Small bins -> To small chunks. The size is the same for all chunks in the same small bin.

• Large bins -> To large chunks. They can contain chunk with different sizes that are sorted based on it.

On the other hand, the single linked bins only use the fd pointer. They are LIFO (Last In First Out) queues, since the chunks are inserted and searched in the beginning of the bin. These bins are:

• Fast bins -> Cache bins for the smallest chunks.

• Tcaches (Thread Caches) -> Cache bins that allow several threads to access to small chunks at the same time.

In the case chunks that fits in several bins, usually in tcaches, fast bins and small bins, the order is the following:

1. Tcaches -> Chunks are inserted in tcaches always that it is possible, both through free calls and tcache recharging.

2. Fast bins -> Chunks are inserted in fast bins when tcaches are full.

3. Small bins -> Chunks are inserted in small bins if the tcaches are full and the chunk does not fit in a fast bin.

   Double linked Bins

The double linked (fd and bk) bins are:

• Unsorted bin

• Small bins

• Large bins

These bins can be found in the malloc_state bins member. This attribute contains a pair of pointers fd and bk for each bin, that point to the first and last chunk, respectively. If there are no chunks, these pointers point to the bin entry itself.

We can show the doubled linked bins with the dmhb command:

[0x7f8491e94090]> dmhb
  Bin 001:
  double linked list unsorted bin {
    0x7f8491df1ca0->fd = 0x7f8491df1ca0
    0x7f8491df1ca0->bk = 0x7f8491df1ca0
  }
  Bin 002:
  double linked list small bin {
    0x7f8491df1cb0->fd = 0x7f8491df1cb0
    0x7f8491df1cb0->bk = 0x7f8491df1cb0
  }
  Bin 003:
  double linked list small bin {
    0x7f8491df1cc0->fd = 0x7f8491df1cc0
    0x7f8491df1cc0->bk = 0x7f8491df1cc0
  }
..............| Stripped Output |...................
  Bin 064:
  double linked list small bin {
    0x7f8491df2090->fd = 0x5637a11c0030->fd = 0x7f8491df2090
    0x7f8491df2090->bk = 0x5637a11c0030->bk = 0x7f8491df2090
  }
  Bin 065:
  double linked list large bin {
    0x7f8491df20a0->fd = 0x7f8491df20a0
    0x7f8491df20a0->bk = 0x7f8491df20a0
  }
..............| Output stripped |...................
 Bin 126:
  double linked list large bin {
    0x7f8491df2470->fd = 0x7f8491df2470
    0x7f8491df2470->bk = 0x7f8491df2470
  }
 Bin 127:
  double linked list large bin {
    0x7f8491df2480->fd = 0x7f8491df2480
    0x7f8491df2480->bk = 0x7f8491df2480
  }

}

(The output is stripped for the sake of space)

In order to show only the bins that contains some chunk, we can filter the dmhb output with grep:

[0x7f8491e94090]> dmhb | grep -E 'fd =.+=' -C 2
 Bin 064:
  double linked list small bin {
    0x7f8491df2090->fd = 0x5637a11c0030->fd = 0x7f8491df2090
    0x7f8491df2090->bk = 0x5637a11c0030->bk = 0x7f8491df2090
  }

To show an specific bin, you can specify the bins desired index in dmhb:

[0x7f8491e94090]> dmhb 64
 Bin 064:
  double linked list small bin {
    0x7f8491df2090->fd = 0x5637a11c0030->fd = 0x7f8491df2090
    0x7f8491df2090->bk = 0x5637a11c0030->bk = 0x7f8491df2090
  }

                 .----------------------------------------------------------.
                 |   entry               chunk                  chunk       |
                 |   .----.          .-----------.          .-----------.   |
                 '-> | XX | <-.  .-> | prev_size | <-.  .-> | prev_size | <-|--.
                     | YY |   |  |   | size      |   |  |   | size      |   |  |
malloc_state.bins[1] | fd |---|--'   | fd -------|---|--'   | fd -------|---'  |
                   .-| bk |   '------| bk        |   '------| bk        |      |
                   | '----'          '-----------'          '-----------'      |
                   '-----------------------------------------------------------'

[0x55b3cb19b27d]> dmhb 1
  Bin 001:
  double linked list unsorted bin {
    0x7ff8f1a9eca0->fd = 0x55b3cce31370->fd = 0x55b3cce31f90->fd = 0x7ff8f1a9eca0
    0x7ff8f1a9eca0->bk = 0x55b3cce31f90->bk = 0x55b3cce31370->bk = 0x7ff8f1a9eca0
  }

[0x55f3489b8250]> dmhb 1:0x7fbd44000020
  Bin 001:
  double linked list unsorted bin {
    0x7fbd44000080->fd = 0x7fbd44000080
    0x7fbd44000080->bk = 0x7fbd44000080
  }

                 .----------------------------------------------------------.
                 |   entry               chunk                  chunk       |
                 |   .----.          .-----------.          .-----------.   |
                 '-> | XX | <-.  .-> | prev_size | <-.  .-> | prev_size | <-|--.
                     | YY |   |  |   | size      |   |  |   | size      |   |  |
malloc_state.bins[i] | fd |---|--'   | fd -------|---|--'   | fd -------|---'  |
                   .-| bk |   '------| bk        |   '------| bk        |      |
                   | '----'          '-----------'          '-----------'      |
                   '-----------------------------------------------------------'

[0x7f8491e94090]> dmhb | grep 'small bin' -B 1 -A 3
 Bin 002:
  double linked list small bin {
    0x7f87dc2d77c8->fd = 0x202f000->fd = 0x202f040->fd = 0x7f87dc2d77c8
    0x7f87dc2d77c8->bk = 0x202f040->bk = 0x202f000->bk = 0x7f87dc2d77c8
  }
 Bin 003:
  double linked list small bin {
    0x7f87dc2d77d8->fd = 0x7f87dc2d77d8
    0x7f87dc2d77d8->bk = 0x7f87dc2d77d8
  }
..............| Output stripped |...................
 Bin 062:
  double linked list small bin {
    0x7f87dc2d7b88->fd = 0x7f87dc2d7b88
    0x7f87dc2d7b88->bk = 0x7f87dc2d7b88
  }
 Bin 063:
  double linked list small bin {
    0x7f87dc2d7b98->fd = 0x7f87dc2d7b98
    0x7f87dc2d7b98->bk = 0x7f87dc2d7b98
  }
 Bin 064:
  double linked list small bin {
    0x7f87dc2d7ba8->fd = 0x7f87dc2d7ba8
    0x7f87dc2d7ba8->bk = 0x7f87dc2d7ba8
  }

[0x7f87dbf4bc37]> dmhb | grep 'small bin' -B 1 -A 3 | grep -E 'fd =.+=' -C 2
 Bin 002:
  double linked list small bin {
    0x7f87dc2d77c8->fd = 0x202f000->fd = 0x202f040->fd = 0x7f87dc2d77c8
    0x7f87dc2d77c8->bk = 0x202f040->bk = 0x202f000->bk = 0x7f87dc2d77c8
  }

    .------------<-------------------<-----------------------<----------------------<---.
    |   entry               chunk                  chunk                    chunk       |
    |   .----.        .-------------.         .------------.          .-------------.   |
    '-> | XX |<-.  .->| prev_size   |<--. .-> | prev_size   |<-.  .-->| prev_size   | <-|--.
        | YY |  |  |  | size (0x520)|   | |   | size (0x520)|  |  |   | size (0x510)|   |  |
bins[i] | fd |--|->'  | fd ---------|>--|-'   | fd          |>-|--|   | fd ---------|>--'  |
      .-| bk |  '----<| bk          |   |----<| bk          |  '--|--<| bk          |      |
      | '----'        | fd_nextsize |>. |     | fd_nextsize |     |   | fd_nextsize |>-.   |
      |             .<| bk_nextsize | | |     | bk_nextsize |     | .<| bk_nextsize |  |   |
      |             | '-------------' | |     '-------------'     | | '-------------'  |   |
      |             '----------->-----'-|->--------->---------->--' |                  |   |
      |                                 |                           |                  |   |
      |                                 '---<---------------<-------'---<-------<------'   |
      |                                                                                    |
      '------>--------->----------------->------------------>----------------->------------'

[0x5583f0e61282]> dmhb | grep 'large' -B 1 -A 3
 Bin 065:
  double linked list large bin {
    0x7f981ba440a0->fd = 0x7f981ba440a0
    0x7f981ba440a0->bk = 0x7f981ba440a0
  }
 Bin 066:
  double linked list large bin {
    0x7f981ba440b0->fd = 0x7f981ba440b0
    0x7f981ba440b0->bk = 0x7f981ba440b0
  }
..........................................
 Bin 110:
  double linked list large bin {
    0x7f981ba44370->fd = 0x5583f1f1ff90->fd = 0x7f981ba44370
    0x7f981ba44370->bk = 0x5583f1f1ff90->bk = 0x7f981ba44370
  }
..........................................
 Bin 126:
  double linked list large bin {
    0x7f981ba44470->fd = 0x7f981ba44470
    0x7f981ba44470->bk = 0x7f981ba44470
  }
 Bin 127:
  double linked list large bin {
    0x7f981ba44480->fd = 0x7f981ba44480
    0x7f981ba44480->bk = 0x7f981ba44480
  }

[0x5583f0e61282]> dmhb | grep 'large' -B 1 -A 3 | grep -E 'fd =.+=' -C 2
 Bin 110:
  double linked list large bin {
    0x7f981ba44370->fd = 0x5583f1f1ff90->fd = 0x7f981ba44370
    0x7f981ba44370->bk = 0x5583f1f1ff90->bk = 0x7f981ba44370
  }

                               .-----------.     .-----------.
                           .-> | prev_size | .-> | prev_size | .-> 0x0
                           |   | size      | |   | size      | |
malloc_state.fastbinsY[i] -'   | fd -------|-'   | fd -------|-'
                               | bk        |     | bk        |
                               '-----------'     '-----------'

[0x5627a3a97306]> dmhf
fastbinY {
 Fastbin 01
  fastbin 1 @ 0x7f6e9df65c50 {
   0x5627a47d9760->fd = 0x5627a47d9740->fd = 0x5627a47d9720
  }
 Fastbin 02
  Empty bin  0x0
 Fastbin 03
  Empty bin  0x0
 Fastbin 04
  Empty bin  0x0
 Fastbin 05
  Empty bin  0x0
 Fastbin 06
  Empty bin  0x0
 Fastbin 07
  Empty bin  0x0
 Fastbin 08
  Empty bin  0x0
 Fastbin 09
  Empty bin  0x0
 Fastbin 10
  Empty bin  0x0
}

[0x56173d3ee355]> dmhf | grep -w 'fastbin' -A 2
  fastbin 1 @ 0x7fcf8b64ec50 {
   0x56173f36d760->fd = 0x56173f36d740->fd = 0x56173f36d720
  }
--
  fastbin 4 @ 0x7fcf8b64ec68 {
   0x56173f36d9b0
  }

typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  struct tcache_perthread_struct *key;
} tcache_entry;

typedef struct tcache_perthread_struct
{
  uint16_t counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

                                            .-----------.        .-----------.
                                            | prev_size |        | prev_size |
                                            | size      |        | size      |
tcache_perthread_struct.entries[i].next --> | fd (next) |------->| fd (next) |---> 0x0
            ^     ^             .----------<| bk (key)  |  .----<| bk (key)  |
            |     '-------------'           '-----------'  |     '-----------'
            '----------------------------------------------'

[0x7f8491e94090]> dmht
Tcache main arena @ 0x7f8491df1c40
bin : 1, items : 3, fd :0x5637a11c0000->0x5637a11be830->0x5637a11bffd0
bin : 2, items : 2, fd :0x5637a11bd910->0x5637a11bfd30
bin : 3, items : 2, fd :0x5637a11c0430->0x5637a11bfd70
bin : 5, items : 1, fd :0x5637a11bfb20
bin :33, items : 1, fd :0x5637a11bd620
bin :59, items : 1, fd :0x5637a11bf6c0

[0x563d885dc2e4]> dmht
Tcache main arena @ 0x7f4222dfbba0

I will let you here some common errors that can arise when your are examinating the heap.

[0x7f94f6c29090]> dmha?
Warning: Can't find glibc mapped in memory (see dm)

[0x557602f15189]> dm~libc:0[9]
/usr/lib/x86_64-linux-gnu/libc-2.32.so

[0x000010c0]> dmha
dbg.glibc.tcache = 1
Warning: Can't find arena mapped in memory (see om)

[0x55b07c433207]> dmha
No Heap section

[0x55b07c433221]> dm~heap]
0x000055b07da3b000 - 0x000055b07da5c000 - usr   132K s rw- [heap] [heap]

[0x7f9694a1b8cb]> dmht
Tcache main arena @ 0x7f9694bbdba0
bin : 3, items : 7, fd :0x55d1c5dfc530->0x55d498c3991c->0xffffffffffffffef

[0x7f9694a1b8cb]> dmhf | grep -w 'fastbin' -A 2
  fastbin 4 @ 0x7f9694bbdbc8 {
   0x55d1c5dfc8b0->fd = 0x55d498c395bc Linked list corrupted

#define PROTECT_PTR(pos, ptr) \
  ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
#define REVEAL_PTR(ptr)  PROTECT_PTR (&ptr, ptr)

[0x7f9694a1b8cb]> e dbg.glibc.demangle = true

[0x7f9694a1b8cb]> dmht
Tcache main arena @ 0x7f9694bbdba0
bin : 3, items : 7, fd :0x55d1c5dfc530->0x55d1c5dfc4c0->0x55d1c5dfc450->0x55d1c5dfc3e0->0x55d1c5dfc370->0x55d1c5dfc300->0x55d1c5dfc290

[0x7f9694a1b8cb]> dmhf | grep -w 'fastbin' -A 2
  fastbin 4 @ 0x7f9694bbdbc8 {
   0x55d1c5dfc8b0->fd = 0x55d1c5dfc840->fd = 0x55d1c5dfc7d0->fd = 0x55d1c5dfc760->fd = 0x55d1c5dfc6f0->fd = 0x55d1c5dfc680->fd = 0x55d1c5dfc610->fd = 0x55d1c5dfc5a0
  }

Well, I hope that this walk for the heap with radare helps you to perform heap analysis in the future.

Happy hacking ;)

• radare2

• r2con 2016 - n4x0r Heap Analysis

• glibc wiki: MallocInternals

• Heap exploitation book

• Azeria Labs

• Understanding glibc malloc

• how2heap

• tutorial de Megabeets

• Safe-Linking

• cheatsheet