Ptmalloc算法：UAF

堆利用中较为常见的漏洞，利用了“free”函数本身的缺陷，对已经置空的指针进行操作

UAF一般有以下几种情况：

内存块被释放后，其对应的指针被设置为 NULL ，然后再次使用，自然程序会崩溃
内存块被释放后，其对应的指针没有被设置为 NULL ，然后在它下一次被使用之前，没有代码对这块内存块进行修改，那么程序很有可能可以正常运转
内存块被释放后，其对应的指针没有被设置为 NULL，但是在它下一次使用之前，有代码对这块内存进行了修改，那么当程序再次使用这块内存时，就很有可能会出现奇怪的问题

UAF漏洞主要是后两种，被置空的指针被称为“dangling pointer”

数据结构bins

简单来说bin就是free chunk的容器

ptmalloc 把大小相似的 chunk，用双向链表连接起来，这样就形成了一个 bin，ptmalloc 一共维护了 128 个这样的 bin，并使用数组来存储这些 bin 如下：（32位）

从第2个到第64个bin是small bin，small bin中的chunk大小相同，small bin是一个双向链表

在某一条bin中(chunk大小相同)按照「先入先出」（FIFO 的规则）进行排序，也就是说，刚被释放的放在前面

bins分类：fast bin，small bin，unsorted bin，large bin

bin链都是由当前线程的arena管理的

Fast bin

Fast bin可以看着是 small bins 的一小部分 cache ，设计初衷就是进行快速的小内存分配和释放

概念：chunk 的大小在32字节~128字节（0x20~0x80）的 chunk 称为“fast chunk”（大小不是 malloc 时的大小，而是在内存中 struct malloc_chunk 的大小，包含前2个成员）

特征：

Fast bin是 单向链表 只有 FD 指针
Fast chunk 不会对其他 free chunk 进行合并
系统将属于 Fast bin 的 chunk 的 PREV_INUSE 位总是设置为1
Fast bin 中无论是添加还是移除 fast chunk，都是对“链表头”进行操作，而不会对某个中间的 fast chunk 进行操作

使用次序：后入先出（可以类比一下栈）

释放时：将此 chunk 插入到该 Fast bin 的“链表头”
申请时：优先申请 Fast bin “链表头”处的 chunk（从前向后申请）

通常情况下：

如果chunk大小小于“0x40(32位) / 0x80(64位)”，那么该chunk会直接存入Fast bin
如果内存请求小于“0x40(32位) / 0x80(64位)”，那么程序会优先在 Fast bin 中查找

#include<stdio.h>
#include <stdlib.h>

int main()
{
	unsigned int *p1,*p2,*p3,*p4,*p5,*p6;
	unsigned int *a,*b,*c;
	
	p1=malloc(0x50);
	printf("%p\n",p1-4);
	p2=malloc(0x50);
	printf("%p\n",p2-4);
	p3=malloc(0x50);
	printf("%p\n",p3-4);
	p4=malloc(0x50);
	printf("%p\n",p4-4);
	p5=malloc(0x50);
	printf("%p\n",p5-4);
	p6=malloc(0x50);
	printf("%p\n",p6-4);
	
	free(p1); // 直接插入表头
	free(p3);
	free(p5);
	printf("--------------\n");
	printf("fastbin:%p -> %p -> %p\n",p5-4,p3-4,p1-4);

	a=malloc(0x50); // 从表头开始申请
	b=malloc(0x50);
	c=malloc(0x50);
	printf("--------------\n");
	printf("%p\n",a-4);
	printf("%p\n",b-4);
	printf("%p\n",c-4);
	printf("--------------\n");

	return 0;
}

➜  [/home/ywhkkx/桌面] ./test 
0x56000683a000
0x56000683a470
0x56000683a4d0
0x56000683a530
0x56000683a590
0x56000683a5f0
--------------
fastbin:0x56000683a590 -> 0x56000683a4d0 -> 0x56000683a000
--------------
0x56000683a590
0x56000683a4d0
0x56000683a000
--------------

Small bin

small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致

使用次序：先入先出（可以类比一下食堂排队）

释放时：将此 chunk 插入到该 Small bin 的“链表头”
申请时：优先申请 Small bin “链表尾”处的 chunk（从后向前申请）

#include<stdio.h>
#include <stdlib.h>

int main()
{
	unsigned int *p1,*p2,*p3,*p4;
	unsigned int a,b,c;
	
	p1=malloc(0x80);
	p2=malloc(0x100);
	free(p1);
	p3=malloc(0x40); // 直接插入表头
	p4=malloc(0x100); // 重新分配:把unsortedbin中的chunk转移到smallbin&largebin中
	a=p3+0x10; 
	
	p1=malloc(0x80);
	p2=malloc(0x100);
	free(p1);
	p3=malloc(0x40);
	p4=malloc(0x100);
	p1=malloc(0x80);
	b=p3+0x10;
	
	p2=malloc(0x100);
	free(p1);
	p3=malloc(0x40);
	p4=malloc(0x100);
	c=p3+0x10;

	printf("smallbin:0x5555%x -> 0x5555%x -> 0x5555%x\n",c,b,a);
	p1=malloc(0x30); // 从表尾开始，向前申请
	printf("chunk1:%p\n",p1-4);
	p2=malloc(0x30);
	printf("chunk2:%p\n",p2-4);
	p3=malloc(0x30);
	printf("chunk3:%p\n",p3-4);
	
	return 0;
}

➜  [/home/ywhkkx/桌面] ./test               
smallbin:0x5555a66515b0 -> 0x5555a6651300 -> 0x5555a6651050
chunk1:0x5580a6651050
chunk2:0x5580a6651300
chunk3:0x5580a66515b0

Large bin

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内

概念：大于等于1024字节（0x400）的chunk称之为large chunk，large bin就是用于管理这些largechunk的
large bin链表的个数为63个，被分为6组
largechunk使用 fd_nextsize、bk_nextsize 连接起来的
- fd_nextsize：指向前一个与当前chunk大小不同的第一个空闲块，不包含 bin 的头指针
- bk_nextsize：指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针
合并操作：类似于small bin

#define largebin_index_32(sz)                                                  \
    (((((unsigned long) (sz)) >> 6) <= 38)                                     \
         ? 56 + (((unsigned long) (sz)) >> 6)                                  \
         : ((((unsigned long) (sz)) >> 9) <= 20)                               \
               ? 91 + (((unsigned long) (sz)) >> 9)                            \
               : ((((unsigned long) (sz)) >> 12) <= 10)                        \
                     ? 110 + (((unsigned long) (sz)) >> 12)                    \
                     : ((((unsigned long) (sz)) >> 15) <= 4)                   \
                           ? 119 + (((unsigned long) (sz)) >> 15)              \
                           : ((((unsigned long) (sz)) >> 18) <= 2)             \
                                 ? 124 + (((unsigned long) (sz)) >> 18)        \
                                 : 126)

#define largebin_index_32_big(sz)                                              \
    (((((unsigned long) (sz)) >> 6) <= 45)                                     \
         ? 49 + (((unsigned long) (sz)) >> 6)                                  \
         : ((((unsigned long) (sz)) >> 9) <= 20)                               \
               ? 91 + (((unsigned long) (sz)) >> 9)                            \
               : ((((unsigned long) (sz)) >> 12) <= 10)                        \
                     ? 110 + (((unsigned long) (sz)) >> 12)                    \
                     : ((((unsigned long) (sz)) >> 15) <= 4)                   \
                           ? 119 + (((unsigned long) (sz)) >> 15)              \
                           : ((((unsigned long) (sz)) >> 18) <= 2)             \
                                 ? 124 + (((unsigned long) (sz)) >> 18)        \
                                 : 126)

// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz)                                                  \
    (((((unsigned long) (sz)) >> 6) <= 48)                                     \
         ? 48 + (((unsigned long) (sz)) >> 6)                                  \
         : ((((unsigned long) (sz)) >> 9) <= 20)                               \
               ? 91 + (((unsigned long) (sz)) >> 9)                            \
               : ((((unsigned long) (sz)) >> 12) <= 10)                        \
                     ? 110 + (((unsigned long) (sz)) >> 12)                    \
                     : ((((unsigned long) (sz)) >> 15) <= 4)                   \
                           ? 119 + (((unsigned long) (sz)) >> 15)              \
                           : ((((unsigned long) (sz)) >> 18) <= 2)             \
                                 ? 124 + (((unsigned long) (sz)) >> 18)        \
                                 : 126)

#define largebin_index(sz)                                                     \
    (SIZE_SZ == 8 ? largebin_index_64(sz) : MALLOC_ALIGNMENT == 16             \
                                                ? largebin_index_32_big(sz)    \
                                                : largebin_index_32(sz))

Unsorted bin

没有来得及被其他bin收入的chunk，就会被认为在unsorted bin中

在使用malloc申请内存时，如果在“fastbin”和“smallbin”中都没有找到合适的free chunk，程序就会在unsorted bin中进行遍历，寻找合适的free chunk，不合适的chunk会被排序并 重新分配 到对应的“bins”中

关于bins的内存分配

用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk，当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户，这样可以避免频繁的系统调用，降低内存分配的开销

详细过程：

malloc的时候，不论malloc的大小，ptmalloc首先会去检查每个bins链（除去fastbins链）是否有与malloc相等大小的freechunk，如果没有就去检查bins链中是否有 大的freechunk 可以切割
如果存在，那么就切割大的freechunk，那么切割之后剩余的chunk成为 last remainder chunk ，并且last remainder chunk会被放入到 unsorted bin 中
如果没有 大的free chunk 可以切割，程序就会查询 top chunk ，如果top chunk的大小比用户请求的大小要大的话，就将该top chunk分作两部分：1.用户请求的chunk，2.新的top chunk，否则，就需要扩展heap或分配新的heap了——在 main arena 中通过 sbrk 扩展heap，而在 thread arena 中通过 mmap 分配新的heap

流程图：

UAF的利用姿势

UAF的利用比较简单，重点看下程序的“free模块”，看下哪些指针没有被置空

int main()
{
    char *a;
    a = (char *) malloc(sizeof(char)*10); //申请a
    memcpy(a,"ywhkkx",10);
    printf("a addr:%x,%s\n",a,a);
    free(a); //释放a
    char *b;
    b = (char *)malloc(sizeof(char)*10); //申请相同大小的b
    memcpy(a,"isacaib",10);
    printf("b addr:%x,%s\n",b,b);
    printf("a addr:%x,%s\n",a,a);
    return 0;
}

1
2
3

a addr:6792d2a0,ywhkkx
b addr:6792d2a0,isacaib
a addr:6792d2a0,isacaib

可以发现，“a”和“b”指向了同一片内存：对“a”进行控制，就相当于控制了“b”

UAF利用姿势

利用条件：

“free模块”没有置空指针
可以对chunk进行读写

利用效果：

利用姿势：

一，申请一个chunk，然后释放：

二，修改该chunk的FD指针为“ Malloc_hook - 0x10 ”：

三，再次申请chunk，并进行修改

原理总述：

利用UAF的特性（可以申请到相同的chunk），先在某个chunk的FD指针中写入 “目标地址 - 0x10” ，程序会误以为它是某个chunk，于是会把这片区域当成chunk给申请出来，最后就可以直接修改了

// 如果程序没有提供“修改模块”，则使用Double Free

PS：

基于UAF，可以实现一种被称为Alloc to Stack的技术，和上述操作一致，只不过把“目标地址”换做了栈地址

Wiki上把它归为Fastbin Attack，但它的利用核心还是UAF