=========================== Tut10: Exploiting Heap Bugs =========================== Now everyone has experienced tons of stack corruptions from the previous labs. From this lecture, we will play with bugs on the heap, which is typically more complex than the stack-based bugs. 1. Revisiting a heap-based "crackme0x00" ======================================== The "heap" space is the dynamic memory used by a process. Generally, we can allocate a heap memory object by calling malloc() and reclaim it by calling free() when we no longer needed. However, do you know how malloc() and free() internally work on Linux? Do you know where exactly the heap objects locate? And do you know what are the heap bugs and how to exploit them? You will get the answers to these questions in this lab. Let's start our adventure with a new heap-based crackme0x00. ------------------------------------------------------------ #include #include #include #include char password[] = "250382"; int main(int argc, char *argv[]) { setvbuf(stdout, NULL, _IONBF, 0); setvbuf(stdin, NULL, _IONBF, 0); char *buf = (char *)malloc(100); char *secret = (char *)malloc(100); strcpy(secret, password); printf("IOLI Crackme Level 0x00\n"); printf("Password:"); scanf("%s", buf); if (!strcmp(buf, secret)) { printf("Password OK :)\n"); } else { printf("Invalid Password! %s\n", buf); } return 0; } ------------------------------------------------------------ $ make cc -m32 -g -O0 -o crackme0x00 crackme0x00.c /home/vagrant/seclab/bin/checksec.sh --file crackme0x00 RELRO STACK CANARY NX PIE RPATH RUNPATH FILE Partial RELRO No canary found NX enabled No PIE No RPATH No RUNPATH crackme0x00 Here the information shown by checksec.sh is not very important. You can see that now the input is put on a piece of dynamic memory which has a size of 100 and meanwhile the secret password is also placed on the heap inside a memory block with the same size. Our first task is to observe the exact memory location of these two heap objects. Let's check crackme0x00 in gdb. (gdb) disassemble main Dump of assembler code for function main: 0x08048607 <+90>: call 0x8048450 0x0804860c <+95>: mov %eax,0x18(%esp) 0x08048610 <+99>: movl $0x64,(%esp) 0x08048617 <+106>: call 0x8048450 0x0804861c <+111>: mov %eax,0x1c(%esp) 0x08048620 <+115>: movl $0x804a038,0x4(%esp) 0x08048628 <+123>: mov 0x1c(%esp),%eax 0x0804862c <+127>: mov %eax,(%esp) 0x0804862f <+130>: call 0x8048440 0x08048634 <+135>: movl $0x8048740,(%esp) 0x0804863b <+142>: call 0x8048460 0x08048640 <+147>: movl $0x8048758,(%esp) 0x08048647 <+154>: call 0x8048430 0x0804864c <+159>: mov 0x18(%esp),%eax 0x08048650 <+163>: mov %eax,0x4(%esp) 0x08048654 <+167>: movl $0x8048762,(%esp) 0x0804865b <+174>: call 0x80484a0 <__isoc99_scanf@plt> 0x08048660 <+179>: mov 0x1c(%esp),%eax From the assembly, we can see that the function malloc() is invoked for two times. As we are interested in its return value, let's set two breakpoints at the next following instructions, 0x0804860c and 0x0804861c, perspectively and start the program. (gdb) b *0x0804860c Breakpoint 1 at 0x804860c: file crackme0x00.c, line 13. (gdb) b *0x0804861c Breakpoint 2 at 0x804861c: file crackme0x00.c, line 14. (gdb) r Starting program: /home/vagrant/seclab/lab10/_tut/crackme0x00 Breakpoint 1, 0x0804860c in main (argc=1, argv=0xffffd734) at crackme0x00.c:13 13 char *buf = (char *)malloc(100); The breakpoint is triggered! It is the first time the malloc() function is invoked and returns (at line 13). We can check the return value stored in register eax. (gdb) i r eax eax 0x804b008 134524936 As you can see, buf points at 0x804b008 which will store our input. Let's continue the execution. (gdb) c Continuing. Breakpoint 2, 0x0804861c in main (argc=1, argv=0xffffd734) at crackme0x00.c:14 14 char *secret = (char *)malloc(100); The second malloc() returns. Similarly, we can check its return value stored in register eax. (gdb) i r eax eax 0x804b070 134525040 We can now take a look into these two memory blocks. (gdb) x/60wx 0x804b000 0x804b000: 0x00000000 0x00000069 0x00000000 0x00000000 0x804b010: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b020: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b030: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b040: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b050: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b060: 0x00000000 0x00000000 0x00000000 0x00000069 0x804b070: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b080: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b090: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0a0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0b0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0c0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0d0: 0x00000000 0x00020f31 0x00000000 0x00000000 Since we have not give our input and the program has not initialized the secret password, both of these heap objects are empty. However, you might be wondering at this moment: the starting address of the first heap object was 0x804b008 (not 0x804b000). Why didn't it start from 0x804b000? Where does that 8 bytes come from? Let's first take a look at the memory layout of the process. (gdb) info proc mappings process 25806 Mapped address spaces: Start Addr End Addr Size Offset objfile 0x8048000 0x8049000 0x1000 0x0 /home/vagrant/seclab/lab10/_tut/crackme0x00 0x8049000 0x804a000 0x1000 0x0 /home/vagrant/seclab/lab10/_tut/crackme0x00 0x804a000 0x804b000 0x1000 0x1000 /home/vagrant/seclab/lab10/_tut/crackme0x00 0x804b000 0x806c000 0x21000 0x0 [heap] 0xf7e1e000 0xf7e1f000 0x1000 0x0 0xf7e1f000 0xf7fc7000 0x1a8000 0x0 /lib/i386-linux-gnu/libc-2.19.so 0xf7fc7000 0xf7fc8000 0x1000 0x1a8000 /lib/i386-linux-gnu/libc-2.19.so 0xf7fc8000 0xf7fca000 0x2000 0x1a8000 /lib/i386-linux-gnu/libc-2.19.so 0xf7fca000 0xf7fcb000 0x1000 0x1aa000 /lib/i386-linux-gnu/libc-2.19.so 0xf7fcb000 0xf7fce000 0x3000 0x0 0xf7fd9000 0xf7fdb000 0x2000 0x0 0xf7fdb000 0xf7fdc000 0x1000 0x0 [vdso] 0xf7fdc000 0xf7ffc000 0x20000 0x0 /lib/i386-linux-gnu/ld-2.19.so 0xf7ffc000 0xf7ffd000 0x1000 0x1f000 /lib/i386-linux-gnu/ld-2.19.so 0xf7ffd000 0xf7ffe000 0x1000 0x20000 /lib/i386-linux-gnu/ld-2.19.so 0xfffdd000 0xffffe000 0x21000 0x0 [stack] Note that "[heap]" label, it indicates the memory starting from 0x804b000 to 0x806c000 as the heap memory. But the fact is that the first allocated heap object storing our input does not start from 0x804b000. We guess that these 8 bytes including that strange 0x69 is inserted by libc. Let's do a simple calculation. Since we first allocate for 100 bytes and 0x804b008 + 100 = 0x804b06c, which means that the memory space from 0x804b008 to 0x804b06c is all used to store the input. If the libc append 8 bytes ahead of every heap object and considering the returned address of the second heap object is 0x804b070, then the 4 bytes starting at 0x804b068(=0x804b070-0x8) should all belong to the second heap object. Most Linux distributions nowadays use ptmalloc as its malloc implementation in the libc. (A helper link of its source at: http://osxr.org:8080/glibc/source/malloc/malloc.c) In the ptmalloc's implemetation, a memory object is called a "chunk" in libc. The following picture illustrates the exact structure of an allocated "chunk". chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, if freed | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |N|M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Carefully check this picture and all your doubts can be solved. Label "chunk" indicates the real starting address of the heap object in the memory, and the malloc() function always returns the address pointed to by lable "mem" to the program which stores the user data. The first 8 bytes are meta data which consist of the size of previous chunk, if allocated and the size of the chunk. The size of the chunk is usually aligned to a multiple of 8 and include both the size of the meta data and the reuqest size from the program. The first four bytes are a bit special. There are two cases: 1) if the previous chunk is allocated, then these 4 bytes are used to store the data of the previous chunk 2) otherwise, it is used to store the size of the previous chunk. That is why 100 + 8 = 108 while the libc only gives the chunk 0x69(=104 + 1) bytes. Note that the last three bits of the size field of a heap chunk have special meaning (that also explains the heap chunk has a size aligned to 8). The last bit of the size field indicates the previous chunk is inuse if it is set to 1, and that's why the size field has 0x69 instead of 0x68. (Q: What's the usage of the other two bits?) Let's continue the program and check the memory again. That will give you a better understanding of the illustration above. Set a breakpoint after scanf() and give our input. (gdb) b *0x08048660 Breakpoint 3 at 0x8048660: file crackme0x00.c, line 23. (gdb) c Continuing. IOLI Crackme Level 0x00 Password:AAAABBBBCCCCDDDD Breakpoint 3, main (argc=1, argv=0xffffd734) at crackme0x00.c:23 23 if (!strcmp(buf, secret)) { And check the content inside these two heap objects. (gdb) x/s 0x804b008 0x804b008: "AAAABBBBCCCCDDDD" (gdb) x/s 0x804b070 0x804b070: "250382" (gdb) x/60wx 0x804b000 0x804b000: 0x00000000 0x00000069 0x41414141 0x42424242 prev_size size buf data --> 0x804b010: 0x43434343 0x44444444 0x00000000 0x00000000 0x804b020: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b030: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b040: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b050: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b060: 0x00000000 0x00000000 0x00000000 0x00000069 <-- buf data size 0x804b070: 0x33303532 0x00003238 0x00000000 0x00000000 secret data --> 0x804b080: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b090: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0a0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0b0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0c0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804b0d0: 0x00000000 0x00020f31 0x00000000 0x00000000 <-- secret data Does everything now make sense? Note that we use scanf() to write our input directly onto the heap and there is no size limit. And more importantly, the heap chunks are continously placed. Based on your former experience with stack overflows, it is not hard for you to corrupt the stored secret and pass the check at this moment, right? :) NOTE: When ASLR is on, the heap base varies for every run. You can launch the program for multiple times and check the heap base through /proc/$(pidof crachme0x00)/maps. // 1st run $ cat /proc/$(pidof crackme0x00)/maps 08048000-08049000 r-xp 00000000 08:01 395622 /home/vagrant/seclab/lab10/_tut/crackme0x00 08049000-0804a000 r--p 00000000 08:01 395622 /home/vagrant/seclab/lab10/_tut/crackme0x00 0804a000-0804b000 rw-p 00001000 08:01 395622 /home/vagrant/seclab/lab10/_tut/crackme0x00 0927f000-092a0000 rw-p 00000000 00:00 0 [heap] // 2nd run $ cat /proc/$(pidof crackme0x00)/maps 08048000-08049000 r-xp 00000000 08:01 395622 /home/vagrant/seclab/lab10/_tut/crackme0x00 08049000-0804a000 r--p 00000000 08:01 395622 /home/vagrant/seclab/lab10/_tut/crackme0x00 0804a000-0804b000 rw-p 00001000 08:01 395622 /home/vagrant/seclab/lab10/_tut/crackme0x00 09375000-09396000 rw-p 00000000 00:00 0 [heap] And it does not even tightly follow the address space of the process as shown in gdb when ASLR is off. However, we want to emphasize that for ptmalloc, the heap layout and the values of many meta data can be accurately inferred even tons of malloc() and free() have been called in a program. Task: Can you inject a payload to print out "Password OK :)"? 2. Examine the heap by using GDB plugin ======================================== So far we have checked the memory structure of an allocated heap chunk. You can see that the glibc heap implementation (ptmalloc) on Linux is not straightforward and related with additional meta data. As a result, we are going to use a GDB plugin, libheap, to help us check the heap status of a program during its execution. We already installed libheap to the remote servers (computron, cyclonus). If you want to install libheap into your local machine, you can follow the below instructions. Libheap is available at https://github.com/cloudburst/libheap. Use git to fetch it, $ git clone https://github.com/cloudburst/libheap Cloning into 'libheap'... Libheap functions best if we have installed the debugging support of the glibc. (This is not required) $ sudo apt-get install libc6-dbg $ sudo apt-get install libc6-dbg:i386 Libheap is a gdb plugin written in python. It can be easily installed as follows. $ cd libheap $ sudo python3 setup.py install running install running build running build_py creating build/lib ... running install_egg_info Writing /usr/local/lib/python3.4/dist-packages/libheap-0.1.egg-info NOTE: The Python library linked into GDB uses Python 3.x by default on Ubuntu 14.04 including the vagrant VM. As a result, you need to install libheap as a python3 package locally to make it work. Open gdb and import libheap after installation. Make sure that there is no error. $ gdb (gdb) python from libheap import * (gdb) Now we are going to explore more facts about the glibc heap with the help of libheap and the targeted example program is heap-example. Here is the code: ------------------------------------------------------------ #include #include #include void prompt(char *fmt, ...) { va_list args; va_start(args, fmt); vprintf(fmt, args); va_end(args); getchar(); } int main() { void *fb_0 = malloc(16); void *fb_1 = malloc(32); void *fb_2 = malloc(16); void *fb_3 = malloc(32); prompt("Stage 1"); free(fb_1); free(fb_3); prompt("Stage 2"); free(fb_0); free(fb_2); malloc(32); prompt("Stage 3"); void *nb_0 = malloc(100); void *nb_1 = malloc(120); void *nb_2 = malloc(140); void *nb_3 = malloc(160); void *nb_4 = malloc(180); prompt("Stage 4"); free(nb_1); free(nb_3); prompt("Stage 5"); void *nb_5 = malloc(240); prompt("Stage 6"); free(nb_2); prompt("Stage 7"); return 0; } ------------------------------------------------------------ The program simply allocates some heap objects with various sizes and frees them at different timings. It is divided into several stages and at each stage, the program stops and we have a chance to look into the memory by using libheap. Let's launch the program in gdb and arrive at stage 1. Use Ctrl+C to interrupt the execution. The first command is simply "heap", $ gdb heap-example (gdb) python from libheap import * (gdb) r Starting program: /home/vagrant/seclab/lab10/_tut/heap-example Stage 1^C Program received signal SIGINT, Interrupt. 0xf7fdb440 in __kernel_vsyscall () (gdb) heap Arena(s) found: arena @ 0xf7fc6420 It shows that an arena is at 0xf7fca420. The data structure used by ptmalloc to manage unallocataed(free) chunks are called "arena". One arena is in change of one process heap. A process can have a lot of heaps simultaneously and the arena of the initial heap is called "main arena" and here it is at 0xf7fca420. The program allocates 4 heap objects with size 16, 32, 16, 32 in order. We can use libheap command "heapls" to print a listing of all the chunks in the arena. (gdb) heapls ADDR SIZE STATUS sbrk_base 0x804b000 chunk 0x804b000 0x18 (inuse) chunk 0x804b018 0x28 (inuse) chunk 0x804b040 0x18 (inuse) chunk 0x804b058 0x28 (inuse) chunk 0x804b080 0x20f80 (top) sbrk_end 0xffeddfe0 As we expect, that four heap chunks CONTINIOUSLY placed in the memory. (Q: Why the sizes shown above are 0x18 and 0x28 respectively?) Note that this heap starts from 0x804b000 to 0x806c000. A very large heap chunk starting from 0x804b080 to 0x806c000 is not inuse, and it has a special name called "top chunk". Continue the execution (enter anything you like for getchar()) and now we arrive at Stage 2. The 2nd and 4th heap objects are freed. In ptmalloc, the freed chunks are going to be linked into a kind of structures called "bin". The chunk with size from 16~64 bytes (32-bit) belongs to "fastbin". The fastbin is a single linked list. We can use command "fastbins" to have a check. (gdb) fastbins fastbins [ fb 0 ] 0xf7fc8428 -> [ 0x0 ] [ fb 1 ] 0xf7fc842c -> [ 0x0 ] [ fb 2 ] 0xf7fc8430 -> [ 0x0 ] [ fb 3 ] 0xf7fc8434 -> [ 0x804b058 ] (40) [ 0x804b018 ] (40) [ fb 4 ] 0xf7fc8438 -> [ 0x0 ] [ fb 5 ] 0xf7fc843c -> [ 0x0 ] [ fb 6 ] 0xf7fc8440 -> [ 0x0 ] [ fb 7 ] 0xf7fc8444 -> [ 0x0 ] [ fb 8 ] 0xf7fc8448 -> [ 0x0 ] [ fb 9 ] 0xf7fc844c -> [ 0x0 ] Note that in a fastbin, all the heap chunks have the same size. (Q: but their allocation sizes may differ, why?) The heap chunk with a size of 40(=0x28) belongs to the 3rd fastbin, and the head of the linked list is at 0xf7fca434 pointing to our 4th heap chunk and the 4th heap chunk points to the 2nd one. Pay attention to the order of these chunk in the linked list. In fact, the chunk is inserted at the HEAD of its corresponding fastbin. We can use libheap to print out the memory detail of a heap chunk. We take the 4th heap chunk as an example. (gdb) p *(mchunkptr) 0x804b018 $1 = struct malloc_chunk { prev_size = 0x0 size = 0x29 fd = 0x0 bk = 0x0 fd_nextsize = 0x0 bk_nextsize = 0x0 We have explained what is prev_size and what is size before. (Why the prev_size is 0 here?) When a chunk is freed, the first 16 bytes of its data storage are no longer used to store user data. They are used to store pointers pointing forward and backward to the chunks in the same bin. Here "fd" stores the pointer pointing to the 2nd heap chunk in the 3rd fastbin. The "bk" pointer is not used as the fastbin is a single linked list. You can also print out the detail of the 2nd heap chunk. Continue the execution and we arrive at Stage 3. This time all the heap objects we have allocated so far are freed. Issue the command "fastbins" to have a check. (gdb) fastbins fastbins [ fb 0 ] 0xf7fc6428 -> [ 0x0 ] [ fb 1 ] 0xf7fc642c -> [ 0x804b040 ] (24) [ 0x804b000 ] (24) [ fb 2 ] 0xf7fc6430 -> [ 0x0 ] [ fb 3 ] 0xf7fc6434 -> [ 0x804b018 ] (40) [ fb 4 ] 0xf7fc6438 -> [ 0x0 ] [ fb 5 ] 0xf7fc643c -> [ 0x0 ] [ fb 6 ] 0xf7fc6440 -> [ 0x0 ] [ fb 7 ] 0xf7fc6444 -> [ 0x0 ] [ fb 8 ] 0xf7fc6448 -> [ 0x0 ] [ fb 9 ] 0xf7fc644c -> [ 0x0 ] With a smaller size, the 1st chunk and the 3rd chunk are placed into the 1st fastbin. Print out the memory details of these two heap chunks and make sure that you understand why the fields of the meta data have their values in. At this moment, why not printing out the list of all the heap chunks again by using command "heapls". (gdb) heapls ADDR SIZE STATUS sbrk_base 0x804b000 chunk 0x804b000 0x18 (inuse) chunk 0x804b018 0x28 (inuse) chunk 0x804b040 0x18 (inuse) chunk 0x804b058 0x28 (inuse) chunk 0x804b080 0x20f80 (top) sbrk_end 0xffeddfe0 Interestingly, the status of all these heap chunks are still (inuse). Guess how libheap determines whether a heap chunk is inuse or not? It is mainly based on the size field of its next chunk. (Q: Why?) And the fact is that when a heap chunk belonging to the fastbin is freed, the last bit of its next chunk is not cleared. And we also issue another malloc(32) in this stage. Let's check the status of the fastbins again by using command "fastbins". (gdb) fastbins fastbins [ fb 0 ] 0xf7fc6428 -> [ 0x0 ] [ fb 1 ] 0xf7fc642c -> [ 0x804b040 ] (24) [ 0x804b000 ] (24) [ fb 2 ] 0xf7fc6430 -> [ 0x0 ] [ fb 3 ] 0xf7fc6434 -> [ 0x804b018 ] (40) [ fb 4 ] 0xf7fc6438 -> [ 0x0 ] [ fb 5 ] 0xf7fc643c -> [ 0x0 ] [ fb 6 ] 0xf7fc6440 -> [ 0x0 ] [ fb 7 ] 0xf7fc6444 -> [ 0x0 ] [ fb 8 ] 0xf7fc6448 -> [ 0x0 ] [ fb 9 ] 0xf7fc644c -> [ 0x0 ] You can see that the freed chunk at 0x804b058 is used to serve the allocation request. In another word, the fastbin works in a LIFO (Last-In-First-Out) style. Let's allocate some heap chunks whose sizes are out of the fastbin range. Continue the execution and we now arrive at Stage 4. Total 5 heap objects with allocation size 100, 120, 140, 160, 180 are allocated by calling malloc(). Use command "heapls" to print out the chunk list. (gdb) heapls ADDR SIZE STATUS sbrk_base 0x804b000 chunk 0x804b000 0x18 (inuse) chunk 0x804b018 0x28 (inuse) chunk 0x804b040 0x18 (inuse) chunk 0x804b058 0x28 (inuse) chunk 0x804b080 0x68 (inuse) chunk 0x804b0e8 0x80 (inuse) chunk 0x804b168 0x90 (inuse) chunk 0x804b1f8 0xa8 (inuse) chunk 0x804b2a0 0xb8 (inuse) chunk 0x804b358 0x20ca8 (top) sbrk_end 0xffeddfe0 We can see that 5 new heap chunks are created on the heap one by one following the order of malloc() being called. (Q: Why we have these chunk sizes here?) Let's print out the 3nd chunk as an example. (gdb) p *(mchunkptr) 0x804b168 $1 = struct malloc_chunk { prev_size = 0x0 size = 0x91 fd = 0x0 bk = 0x0 fd_nextsize = 0x0 bk_nextsize = 0x0 Move forward to Stage 5, where the 2nd and the 4th (the orders in term of those bigger chunks we allocate later) heap chunks are de-allocated. And issue command "heapls" to print out the chunk list. (gdb) heapls ADDR SIZE STATUS sbrk_base 0x804b000 chunk 0x804b000 0x18 (inuse) chunk 0x804b018 0x28 (inuse) chunk 0x804b040 0x18 (inuse) chunk 0x804b058 0x28 (inuse) chunk 0x804b080 0x68 (inuse) chunk 0x804b0e8 0x80 (F) FD 0xf7fc6450 BK 0x804b1f8 chunk 0x804b168 0x90 (inuse) chunk 0x804b1f8 0xa8 (F) FD 0x804b0e8 BK 0xf7fc6450 chunk 0x804b2a0 0xb8 (inuse) chunk 0x804b358 0x20ca8 (top) sbrk_end 0xffeddfe0 When these heap chunks are freed, they are in fact recycled into an unsorted bin. The chunks inside the unsorted bin can have various sizes. And more importantly, the unsorted bin is a cyclic double linked list. Take a look at the above result, we can find that the 2nd chunk has a backward pointer pointing to the 4th chunk and the 4th chunk has a forward pointer pointing to the 2nd chunk. The head chunk of the unsorted bin is at 0xf7fca450. Pay attention to the order of these two chunks in the unsorted bin. We can print out the memory detail of the freed chunk for more information. Take the 2nd one at 0x804b0e8 as an example. (gdb) p *(mchunkptr) 0x804b0e8 $2 = struct malloc_chunk { prev_size = 0x0 size = 0x81 fd = 0xf7fc6450 bk = 0x804b1f8 fd_nextsize = 0x0 bk_nextsize = 0x0 Q: Try to take a look at the 3rd chunk after the 2nd chunk at 0x804b168. (gdb) p *(mchunkptr) 0x804b168 $3 = struct malloc_chunk { prev_size = 0x80 size = 0x90 fd = 0x0 bk = 0x0 fd_nextsize = 0x0 bk_nextsize = 0x0 Why is the size 0x90 now? And why does the prev_size become 0x80? If you are good with everything so far, we can move forward to Stage 6. This time we allocate a new heap object with size 200. Let's print out the chunk list first, (gdb) heapls ADDR SIZE STATUS sbrk_base 0x804b000 chunk 0x804b000 0x18 (inuse) chunk 0x804b018 0x28 (inuse) chunk 0x804b040 0x18 (inuse) chunk 0x804b058 0x28 (inuse) chunk 0x804b080 0x68 (inuse) chunk 0x804b0e8 0x80 (F) FD 0xf7fc64c8 BK 0xf7fc64c8 (LC) chunk 0x804b168 0x90 (inuse) chunk 0x804b1f8 0xa8 (F) FD 0xf7fc64f0 BK 0xf7fc64f0 (LC) chunk 0x804b2a0 0xb8 (inuse) chunk 0x804b358 0xf8 (inuse) chunk 0x804b450 0x20bb0 (top) sbrk_end 0xffeddfe0 As expected, a new heap chunk with chunk size 0xf8 is generated. However, it seems that the freed 2nd and 4th chunk are not in the unsorted bin any longer. One is linked into a new linked list with the head node at 0xf7fca4c8, and the other one is linked into another linked list which has the head node at 0xf7fca4f0. You can also print out the detail of these two chunks to get more information. So what happend? In fact, when a new malloc request comes, the unsorted bin is traversed (fastbins are naturally skipped) to find out a proper freed chunk. However, both the 2nd chunk and the 4th chunk cannot satisfy the request size. So they are unlinked from the unsorted bin, and then inserted into their corresponding "smallbin" at its TAIL respectively. We can use "smallbins" to check that. (gdb) smallbins ... [ sb 13 ] 0xf7fc64b8 -> [ 0xf7fc64b0 | 0xf7fc64b0 ] [ sb 14 ] 0xf7fc64c0 -> [ 0xf7fc64b8 | 0xf7fc64b8 ] [ sb 15 ] 0xf7fc64c8 -> [ 0xf7fc64c0 | 0xf7fc64c0 ] [ sb 16 ] 0xf7fc64d0 -> [ 0x804b0e8 | 0x804b0e8 ] [ 0xf7fc64c8 | 0xf7fc64c8 ] (128) [ sb 17 ] 0xf7fc64d8 -> [ 0xf7fc64d0 | 0xf7fc64d0 ] [ sb 18 ] 0xf7fc64e0 -> [ 0xf7fc64d8 | 0xf7fc64d8 ] [ sb 19 ] 0xf7fc64e8 -> [ 0xf7fc64e0 | 0xf7fc64e0 ] [ sb 20 ] 0xf7fc64f0 -> [ 0xf7fc64e8 | 0xf7fc64e8 ] [ sb 21 ] 0xf7fc64f8 -> [ 0x804b1f8 | 0x804b1f8 ] [ 0xf7fc64f0 | 0xf7fc64f0 ] (168) [ sb 22 ] 0xf7fc6500 -> [ 0xf7fc64f8 | 0xf7fc64f8 ] [ sb 23 ] 0xf7fc6508 -> [ 0xf7fc6500 | 0xf7fc6500 ] [ sb 24 ] 0xf7fc6510 -> [ 0xf7fc6508 | 0xf7fc6508 ] ... Note that different from the unsorted bin, the chunks in the same smallbin have the same size and it is also a cyclic double linked list. (The number inside the parenthese is the chunk size). Eventually we arrive at Stage 7. This time we de-allocate the 3rd chunk, between the freed 2nd and 4th chunk and then list out all the heap chunks. (gdb) heapls ADDR SIZE STATUS sbrk_base 0x804b000 chunk 0x804b000 0x18 (inuse) chunk 0x804b018 0x28 (inuse) chunk 0x804b040 0x18 (inuse) chunk 0x804b058 0x28 (inuse) chunk 0x804b080 0x68 (inuse) chunk 0x804b0e8 0x1b8 (F) FD 0xf7fc6450 BK 0xf7fc6450 (LC) chunk 0x804b2a0 0xb8 (inuse) chunk 0x804b358 0xf8 (inuse) chunk 0x804b450 0x20bb0 (top) sbrk_end 0xffeddfe0 Surprisingly, you can see that those three freed chunks are consolidated into a new big chunk. It will used to serve for the allocation request in the future. Our adventure ends here. In fact, a lot of interesting facts about the glibc heap implementation have not been covered but you have already gained enough basic knowledge to move forward. Check the references for further information. Last but not least, the source of the glibc heap is always your best helper in this lab (it is available online at https://github.com/lattera/glibc/blob/master/malloc/). No secret is there. p.s.: There could be conflicts between peda and libheap. If you use peda, please use the following command to import libheap as a tentative solution, (gdb) python import libheap