first_fit

c

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

int main()
{
        fprintf(stderr, "This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.\n");
        fprintf(stderr, "glibc uses a first-fit algorithm to select a free chunk.\n");
        fprintf(stderr, "If a chunk is free and large enough, malloc will select this chunk.\n");
        fprintf(stderr, "This can be exploited in a use-after-free situation.\n");

        fprintf(stderr, "Allocating 2 buffers. They can be large, don't have to be fastbin.\n");
        char* a = malloc(0x512);
        char* b = malloc(0x256);
        char* c;

        fprintf(stderr, "1st malloc(0x512): %p\n", a);
        fprintf(stderr, "2nd malloc(0x256): %p\n", b);
        fprintf(stderr, "we could continue mallocing here...\n");
        fprintf(stderr, "now let's put a string at a that we can read later \"this is A!\"\n");
        strcpy(a, "this is A!");
        fprintf(stderr, "first allocation %p points to %s\n", a, a);

        fprintf(stderr, "Freeing the first one...\n");
        free(a);

        fprintf(stderr, "We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at %p\n", a);

        fprintf(stderr, "So, let's allocate 0x500 bytes\n");
        c = malloc(0x500);
        fprintf(stderr, "3rd malloc(0x500): %p\n", c);
        fprintf(stderr, "And put a different string here, \"this is C!\"\n");
        strcpy(c, "this is C!");
        fprintf(stderr, "3rd allocation %p points to %s\n", c, c);
        fprintf(stderr, "first allocation %p points to %s\n", a, a);
        fprintf(stderr, "If we reuse the first allocation, it now holds the data from the third allocation.\n");
}

第一次malloc分配的地址是1st malloc(0x512): 0x5613955532a0 第二次malloc分配的地址是2nd malloc(0x256): 0x5613955537c0

之后将变量a中的内容换成string类型的“this is a A!”,会发现地址不变。

之后将第一个malloc的地址free之后，再次malloc一个小于第一次malloc大小的数据，会发现allocator重新分配的chunk还是之那一个。

疑问：这里重新分配的chunk是否大小还是之前的大小，还是0x500？答：应该是0x500.

GDB调试时可以看到当malloc分配空间时是将空间中先填充入‘’0‘’.

疑

并且这里可以看到两个连续的chunk之间会有一个0x8的空间：0x2a0-0x7c0 = 0x520 = 0x512+0x8: 这八字节中存放的是啥先存疑：

free（a）之后可以看到：

0x7fffffffdde8 —▸ 0x5555555592a0 —▸ 0x7ffff7fa6ce0 (main_arena+96) —▸ 0x555555559a10 ◂— 0x0

至于这里：0x555555559a10 ◂— 0x0也为看懂，存疑：

text
这里的地址是chunk中data空间的地址，当malloc分配一块空间时，会将空间中的数据初始化为0.

bin链(136个)：

fast bin(10个)：单链表结构，故所有分配操作（？存疑）都只对链表尾操作。fasi bin不会对相邻的free chunk进行合并（为了提高效率），单个fast bin中的chunk都是一样大小的，并且从第一个fast bin中chunk的大小到最后一个fast bin中的chunk大小为累加16字节（暂时不清楚分不分x86和x64），如第一个fast bin中chunk大小均为32Bytes，第二个fast bin中的chunk大小则为48字节，以此类推；**第一次mallo时，fast bin未初始化，当分配0x16~0x80字节大小空间时就会向下寻找small bin中的chunk

引用：堆漏洞挖掘中的bins分类(fastbin、unsorted bin、small bin、large bin)

当应用层通过malloc函数第一次申请的chunk属于16字节~80字节之间时，因为初始化的时候fast bin支持的最大内存大小以及所有fast bin链表都是空的，所以它也不会交由fast bin来处理，而是向下传递交由small bin来处理，如果small bin也为空的话就交给unsorted bin处理。

那么，fast bin如何进行初始化哪？当我们第一次调用malloc(fast bin)的时候，系统执行_int_malloc函数，该函数首先会发现当前fast bin为空，就转交给small bin处理，进而又发现small bin 也为空，就调用malloc_consolidate函数对malloc_state结构体进行初始化。malloc_consolidate函数主要完成以下几个功能：

a.首先判断当前malloc_state结构体中的fast bin是否为空，如果为空就说明整个malloc_state都没有完成初始化，需要对malloc_state进行初始化。

b.malloc_state的初始化操作由函数malloc_init_state(av)完成，该函数先初始化除fast bin之外的所有的bins，再初始化fast bins。

那么当再次执行malloc(fast chunk)函数的时候，此时fast bin相关数据不为空了，就可以使用fast bin。

unsort bin（1个）：当释放过大或者过小的chunk时就会将chunk放到unsort bins中。

small bin ：大小小于0x400的small chunk。

large bin

malloc的初始化，第一次调用malloc时会先从fast bin或者unsort bin中找合适的内存空间，但是一般都会找不到，找不到之后就会调用malloc_initialized函数进行初始化

这里可以看一下chunk的地址处：（这里malloc实际分配的空间大小大于我们需要的大小，这里可能仅仅只是为了合适，（也不排除有其他的可能），但是我这里看了别的人分配的，多出来的大小和我的多出来的不一样，说明这多出来的大小不是固定的或者说不是有目的性的，所以可能只是为了合适）

可以看到第一个malloc的地址和第二个malloc的地址分别是0x00005555555592a0和0x00005555555597c0，而我们这里选择查看这两个地址-0x10的地方是因为malloc返回时地址指向的都是chunk的usr的data部分的地址：

free之后再看第二个chunk：

这里就可以看到第一个0x8字节是pre_size，里面放的是：0x520刚好是前一个被free的chunk的大小。

第三个malloc之后再看分配的chunk大小为：

很明显还是和第一个chunk一样大的0x521字节。

这里用

python
gcc -fsanitize=address -g first_fit.c

重新编译再次执行便有更加详细的调试信息：

python
❯ ./a.out
This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.
glibc uses a first-fit algorithm to select a free chunk.
If a chunk is free and large enough, malloc will select this chunk.
This can be exploited in a use-after-free situation.
Allocating 2 buffers. They can be large, don't have to be fastbin.
1st malloc(0x512): 0x61a000000080
2nd malloc(0x256): 0x616000000080
we could continue mallocing here...
now let's put a string at a that we can read later "this is A!"
first allocation 0x61a000000080 points to this is A!
Freeing the first one...
We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at 0x61a000000080
So, let's allocate 0x500 bytes
3rd malloc(0x500): 0x61a000000680
And put a different string here, "this is C!"
3rd allocation 0x61a000000680 points to this is C!
=================================================================
==17255==ERROR: AddressSanitizer: heap-use-after-free on address 0x61a000000080 at pc 0x7f9fa39c0f89 bp 0x7ffc0207d3f0 sp 0x7ffc0207cb68
READ of size 2 at 0x61a000000080 thread T0
    #0 0x7f9fa39c0f88 in printf_common ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors_format.inc:553
    #1 0x7f9fa39c18be in __interceptor_vfprintf ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:1664
    #2 0x7f9fa39c19ce in __interceptor_fprintf ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:1721
    #3 0x55ebce3cc793 in main /home/hyrink/how2heap/first_fit.c:35
    #4 0x7f9fa3764d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #5 0x7f9fa3764e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #6 0x55ebce3cc1a4 in _start (/home/hyrink/how2heap/a.out+0x11a4)

0x61a000000080 is located 0 bytes inside of 1298-byte region [0x61a000000080,0x61a000000592)
freed by thread T0 here:
    #0 0x7f9fa3a17517 in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:127
    #1 0x55ebce3cc5c2 in main /home/hyrink/how2heap/first_fit.c:25
    #2 0x7f9fa3764d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

previously allocated by thread T0 here:
    #0 0x7f9fa3a17867 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55ebce3cc3e1 in main /home/hyrink/how2heap/first_fit.c:13
    #2 0x7f9fa3764d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

SUMMARY: AddressSanitizer: heap-use-after-free ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors_format.inc:553 in printf_common
Shadow bytes around the buggy address:
  0x0c347fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c347fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c347fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c347fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c347fff8000: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c347fff8010:[fd]fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c347fff8020: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c347fff8030: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c347fff8040: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c347fff8050: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c347fff8060: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==17255==ABORTING

目录

first_fit

疑