オルタードカーボン………100点!!!!!


最近はヒープ周りを勉強し直しているので、そのメモ。

環境

$ uname -a
Linux ubuntu-xenial 4.4.0-133-generic #159-Ubuntu SMP Fri Aug 10 07:31:43 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ /lib/x86_64-linux-gnu/libc.so.6
GNU C Library (Ubuntu GLIBC 2.23-0ubuntu10) stable release version 2.23, by Roland McGrath et al.
Copyright (C) 2016 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 5.4.0 20160609.
Available extensions:
        crypt add-on version 2.1 by Michael Glad and others
        GNU Libidn by Simon Josefsson
        Native POSIX Threads Library by Ulrich Drepper et al
        BIND-8.2.3-T5B
libc ABIs: UNIQUE IFUNC
For bug reporting instructions, please see:
<https://bugs.launchpad.net/ubuntu/+source/glibc/+bugs>.

GDB でヒープの確保を確認する

まずは GDB でヒープがどのように確保されるのかを確認してみる。

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

int main(int argc,char *argv[])
{
  char *s = argv[1];
  char *buf;

  buf = (char*)malloc(20);
  printf("buf = %p\n", buf);
  strcpy(buf, s);
  printf("%s\n", buf);
  free(buf);
  return 0;
}
$ gcc heap.c
$ ./a.out AAAA
buf = 0602010
AAAA
$ gdb -q ./a.out
Reading symbols from ./a.out...(no debugging symbols found)...done.
gdb-peda$ disas main
Dump of assembler code for function main:
   0x0000000000400646 <+0>:     push   rbp
   0x0000000000400647 <+1>:     mov    rbp,rsp
   0x000000000040064a <+4>:     sub    rsp,0x20
   0x000000000040064e <+8>:     mov    DWORD PTR [rbp-0x14],edi
   0x0000000000400651 <+11>:    mov    QWORD PTR [rbp-0x20],rsi
   0x0000000000400655 <+15>:    mov    rax,QWORD PTR [rbp-0x20]
   0x0000000000400659 <+19>:    mov    rax,QWORD PTR [rax+0x8]
   0x000000000040065d <+23>:    mov    QWORD PTR [rbp-0x10],rax
   0x0000000000400661 <+27>:    mov    edi,0x14
   0x0000000000400666 <+32>:    call   0x400530 <malloc@plt>
   0x000000000040066b <+37>:    mov    QWORD PTR [rbp-0x8],rax
   0x000000000040066f <+41>:    mov    rax,QWORD PTR [rbp-0x8]
   0x0000000000400673 <+45>:    mov    rsi,rax
   0x0000000000400676 <+48>:    mov    edi,0x400744
   0x000000000040067b <+53>:    mov    eax,0x0
   0x0000000000400680 <+58>:    call   0x400510 <printf@plt>
   0x0000000000400685 <+63>:    mov    rdx,QWORD PTR [rbp-0x10]
   0x0000000000400689 <+67>:    mov    rax,QWORD PTR [rbp-0x8]
   0x000000000040068d <+71>:    mov    rsi,rdx
   0x0000000000400690 <+74>:    mov    rdi,rax
   0x0000000000400693 <+77>:    call   0x4004f0 <strcpy@plt>
   0x0000000000400698 <+82>:    mov    rax,QWORD PTR [rbp-0x8]
   0x000000000040069c <+86>:    mov    rdi,rax
   0x000000000040069f <+89>:    call   0x400500 <puts@plt>
   0x00000000004006a4 <+94>:    mov    rax,QWORD PTR [rbp-0x8]
   0x00000000004006a8 <+98>:    mov    rdi,rax
   0x00000000004006ab <+101>:   call   0x4004e0 <free@plt>
   0x00000000004006b0 <+106>:   mov    eax,0x0
   0x00000000004006b5 <+111>:   leave
   0x00000000004006b6 <+112>:   ret
End of assembler dump.
gdb-peda$ b *0x0000000000400666 # call   0x400530 <malloc@plt>
reakpoint 1 at 0x400666
gdb-peda$ b *0x0000000000400693 # call   0x4004f0 <strcpy@plt>
Breakpoint 2 at 0x400693
gdb-peda$ b *0x00000000004006ab # call   0x4004e0 <free@plt>
Breakpoint 3 at 0x4006ab


gdb-peda$ r `python -c 'print "A"*20'`
Starting program: /home/vagrant/shared/heap/a.out `python -c 'print "A"*20'`
[----------------------------------registers-----------------------------------]
RAX: 0x7fffffffe7d3 ('A' <repeats 20 times>)
RBX: 0x0
RCX: 0x0
RDX: 0x7fffffffe5b0 --> 0x7fffffffe7e8 ("XDG_SESSION_ID=2")
RSI: 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
RDI: 0x14
RBP: 0x7fffffffe4b0 --> 0x4006c0 (<__libc_csu_init>:    push   r15)
RSP: 0x7fffffffe490 --> 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
RIP: 0x400666 (<main+32>:       call   0x400530 <malloc@plt>)
R8 : 0x400730 (<__libc_csu_fini>:       repz ret)
R9 : 0x7ffff7de7ab0 (<_dl_fini>:        push   rbp)
R10: 0x846
R11: 0x7ffff7a2d740 (<__libc_start_main>:       push   r14)
R12: 0x400550 (<_start>:        xor    ebp,ebp)
R13: 0x7fffffffe590 --> 0x2
R14: 0x0
R15: 0x0
EFLAGS: 0x206 (carry PARITY adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x400659 <main+19>:  mov    rax,QWORD PTR [rax+0x8]
   0x40065d <main+23>:  mov    QWORD PTR [rbp-0x10],rax
   0x400661 <main+27>:  mov    edi,0x14
=> 0x400666 <main+32>:  call   0x400530 <malloc@plt>
   0x40066b <main+37>:  mov    QWORD PTR [rbp-0x8],rax
   0x40066f <main+41>:  mov    rax,QWORD PTR [rbp-0x8]
   0x400673 <main+45>:  mov    rsi,rax
   0x400676 <main+48>:  mov    edi,0x400744
Guessed arguments:
arg[0]: 0x14
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffe490 --> 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
0008| 0x7fffffffe498 --> 0x200400550
0016| 0x7fffffffe4a0 --> 0x7fffffffe7d3 ('A' <repeats 20 times>)
0024| 0x7fffffffe4a8 --> 0x0
0032| 0x7fffffffe4b0 --> 0x4006c0 (<__libc_csu_init>:   push   r15)
0040| 0x7fffffffe4b8 --> 0x7ffff7a2d830 (<__libc_start_main+240>:       mov    edi,eax)
0048| 0x7fffffffe4c0 --> 0x0
0056| 0x7fffffffe4c8 --> 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x0000000000400666 in main ()

malloc が呼ばれるところで breakpoint 。mov edi,0x14 で指定したとおりに 20 byte 確保されることがわかる。

gdb-peda$ n
[----------------------------------registers-----------------------------------]
RAX: 0x602010 --> 0x0
RBX: 0x0
RCX: 0x7ffff7dd1b20 --> 0x100000000
RDX: 0x602010 --> 0x0
RSI: 0x602020 --> 0x0
RDI: 0x7ffff7dd1b20 --> 0x100000000
RBP: 0x7fffffffe4b0 --> 0x4006c0 (<__libc_csu_init>:    push   r15)
RSP: 0x7fffffffe490 --> 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
RIP: 0x40066b (<main+37>:       mov    QWORD PTR [rbp-0x8],rax)
R8 : 0x602000 --> 0x0
R9 : 0xd ('\r')
R10: 0x7ffff7dd1b78 --> 0x602020 --> 0x0
R11: 0x0
R12: 0x400550 (<_start>:        xor    ebp,ebp)
R13: 0x7fffffffe590 --> 0x2
R14: 0x0
R15: 0x0
EFLAGS: 0x206 (carry PARITY adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x40065d <main+23>:  mov    QWORD PTR [rbp-0x10],rax
   0x400661 <main+27>:  mov    edi,0x14
   0x400666 <main+32>:  call   0x400530 <malloc@plt>
=> 0x40066b <main+37>:  mov    QWORD PTR [rbp-0x8],rax
   0x40066f <main+41>:  mov    rax,QWORD PTR [rbp-0x8]
   0x400673 <main+45>:  mov    rsi,rax
   0x400676 <main+48>:  mov    edi,0x400744
   0x40067b <main+53>:  mov    eax,0x0
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffe490 --> 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
0008| 0x7fffffffe498 --> 0x200400550
0016| 0x7fffffffe4a0 --> 0x7fffffffe7d3 ('A' <repeats 20 times>)
0024| 0x7fffffffe4a8 --> 0x0
0032| 0x7fffffffe4b0 --> 0x4006c0 (<__libc_csu_init>:   push   r15)
0040| 0x7fffffffe4b8 --> 0x7ffff7a2d830 (<__libc_start_main+240>:       mov    edi,eax)
0048| 0x7fffffffe4c0 --> 0x0
0056| 0x7fffffffe4c8 --> 0x7fffffffe598 --> 0x7fffffffe7b3 ("/home/vagrant/shared/heap/a.out")
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
0x000000000040066b in main ()

malloc の戻り値は RAX に格納され、 0x602010 となっている。つまり、これが buf のアドレス。

gdb-peda$ i proc map
process 6114
Mapped address spaces:

          Start Addr           End Addr       Size     Offset objfile
            0x400000           0x401000     0x1000        0x0 /home/vagrant/shared/heap/a.out
            0x600000           0x601000     0x1000        0x0 /home/vagrant/shared/heap/a.out
            0x601000           0x602000     0x1000     0x1000 /home/vagrant/shared/heap/a.out
            0x602000           0x623000    0x21000        0x0 [heap]
      0x7ffff7a0d000     0x7ffff7bcd000   0x1c0000        0x0 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7bcd000     0x7ffff7dcd000   0x200000   0x1c0000 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7dcd000     0x7ffff7dd1000     0x4000   0x1c0000 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7dd1000     0x7ffff7dd3000     0x2000   0x1c4000 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7dd3000     0x7ffff7dd7000     0x4000        0x0
      0x7ffff7dd7000     0x7ffff7dfd000    0x26000        0x0 /lib/x86_64-linux-gnu/ld-2.23.so
      0x7ffff7fe6000     0x7ffff7fe9000     0x3000        0x0
      0x7ffff7ff7000     0x7ffff7ffa000     0x3000        0x0 [vvar]
      0x7ffff7ffa000     0x7ffff7ffc000     0x2000        0x0 [vdso]
      0x7ffff7ffc000     0x7ffff7ffd000     0x1000    0x25000 /lib/x86_64-linux-gnu/ld-2.23.so
      0x7ffff7ffd000     0x7ffff7ffe000     0x1000    0x26000 /lib/x86_64-linux-gnu/ld-2.23.so
      0x7ffff7ffe000     0x7ffff7fff000     0x1000        0x0
      0x7ffffffde000     0x7ffffffff000    0x21000        0x0 [stack]
  0xffffffffff600000 0xffffffffff601000     0x1000        0x0 [vsyscall]

gdb-peda$ c
Continuing.
buf = 0x602010

strcpy が呼び出される前のヒープの状態は次のような感じ。

gdb-peda$ x/10wx 0x602010
0x602010:       0x00000000      0x00000000      0x00000000      0x00000000
0x602020:       0x00000000      0x00000000      0x00000411      0x00000000
0x602030:       0x20667562      0x7830203d

呼び出された後は次のようになる。

gdb-peda$ n
gdb-peda$ x/10wx 0x602010
0x602010:       0x41414141      0x41414141      0x41414141      0x41414141
0x602020:       0x41414141      0x00000000      0x00000411      0x00000000
0x602030:       0x20667562      0x7830203d

first-fit algorithm

glibc malloc では十分大きなスペースがあると、そこを chunk として使用する。
このアロケーションの様子は以下のプログラムで確認できる。

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

int main()
{

	char* a = malloc(512);
	char* b = malloc(256);
	char* c;

	printf("1st malloc(512): %p\n", a);
	printf("2nd malloc(256): %p\n", b);
	strcpy(a, "AAAA");
	printf("a = %p : %s\n", a, a);

	printf("free a\n");
	free(a);

	printf("a will at %p\n", a);

	c = malloc(500);
	printf("3rd malloc(500): %p\n", c);
	strcpy(c, "CCCC");
	printf("c = %p : %s\n", c, c);
	printf("a = %p : %s\n", a, a);
}

afree したあとに 512 byte 以下を malloc すると、既に開放されている a の領域が使用されることが確認できる。

$ gcc heap.c
$ ./a.cout
1st malloc(512): 0x1fe4010
2nd malloc(256): 0x1fe4220
a = 0x1fe4010 : AAAA
free a
a will at 0x1fe4010
3rd malloc(500): 0x1fe4010
c = 0x1fe4010 : CCCC
a = 0x1fe4010 : CCCC

double-free

同じリソースに対して、2回 free するとメモリリークが発生したりする。2回続けて free すると glibc が検知して double free or corruption(fasttop) と怒られてSEGVするが、以下の例ではそれを bypass し a を2回解放している。
このときの fastbins の状態について簡単にコメントに書いている。

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

int main()
{
	printf("Allocating 3 buffers.\n");
	int *a = malloc(8);
	int *b = malloc(8);
	int *c = malloc(8);

	printf("1st malloc(8): %p\n", a);
	printf("2nd malloc(8): %p\n", b);
	printf("3rd malloc(8): %p\n", c);

	printf("Free a\n");
	free(a); // head -> a -> tail

	// free(a); // => bypass double free or corruption (fasttop)

	printf("Free b\n");
	free(b); // head -> b -> a -> tail
	printf("Free a\n");
	free(a); // head -> a -> b -> a -> tail

	printf("1st malloc(8): %p\n", malloc(8)); // head -> b -> a -> tail ( a を返した )
	printf("2nd malloc(8): %p\n", malloc(8)); // head -> a -> tail ( b を返した )
	printf("3rd malloc(8): %p\n", malloc(8)); // head -> tail ( a を返した )
}
$ ./a.out
Allocating 3 buffers.
1st malloc(8): 0x162f420
2nd malloc(8): 0x162f440
3rd malloc(8): 0x162f460
Free a
Free b
Free a
1st malloc(8): 0x162f420
2nd malloc(8): 0x162f440
3rd malloc(8): 0x162f420 # => a が2回返ってくる

dup into stack などについてはまた今度。

ref

glibc  c