ELF実行ファイルのメモリ配置はどのように決まるのか

Linux x64環境において、ELF実行ファイル、共有ライブラリ、スタック領域、ヒープ領域のアドレスがどのように決まるのかについてのメモ。

環境

Ubuntu 12.04 LTS 64bit版

$ uname -a
Linux vm-ubuntu64 3.11.0-15-generic #25~precise1-Ubuntu SMP Thu Jan 30 17:39:31 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 12.04.4 LTS
Release:        12.04
Codename:       precise

$ gcc --version
gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

実行時のメモリマップを確認してみる

まずは、ヒープ領域を使う適当なプログラムを用意する。

/* hello.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char *buf;
    buf = malloc(20);
    strncpy(buf, "Hello, world!", 20);
    puts(buf);
    return 0;
}

コンパイルし、gdbを使ってメモリマップを表示させてみる。

$ gcc hello.c

$ gdb -q a.out
Reading symbols from /home/user/tmp/a.out...(no debugging symbols found)...done.
(gdb) b puts
Breakpoint 1 at 0x400470
(gdb) r
Starting program: /home/user/tmp/a.out
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000

Breakpoint 1, 0x00007ffff7a8ace0 in puts () from /lib/x86_64-linux-gnu/libc.so.6
(gdb) i proc
process 5927
cmdline = '/home/user/tmp/a.out'
cwd = '/home/user/tmp'
exe = '/home/user/tmp/a.out'
(gdb) shell cat /proc/5927/maps
00400000-00401000 r-xp 00000000 08:01 1182040                            /home/user/tmp/a.out
00600000-00601000 r--p 00000000 08:01 1182040                            /home/user/tmp/a.out
00601000-00602000 rw-p 00001000 08:01 1182040                            /home/user/tmp/a.out
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7ffff7a1a000-7ffff7bcf000 r-xp 00000000 08:01 2097169                    /lib/x86_64-linux-gnu/libc-2.15.so
7ffff7bcf000-7ffff7dcf000 ---p 001b5000 08:01 2097169                    /lib/x86_64-linux-gnu/libc-2.15.so
7ffff7dcf000-7ffff7dd3000 r--p 001b5000 08:01 2097169                    /lib/x86_64-linux-gnu/libc-2.15.so
7ffff7dd3000-7ffff7dd5000 rw-p 001b9000 08:01 2097169                    /lib/x86_64-linux-gnu/libc-2.15.so
7ffff7dd5000-7ffff7dda000 rw-p 00000000 00:00 0
7ffff7dda000-7ffff7dfc000 r-xp 00000000 08:01 2097185                    /lib/x86_64-linux-gnu/ld-2.15.so
7ffff7fee000-7ffff7ff1000 rw-p 00000000 00:00 0
7ffff7ff8000-7ffff7ffa000 rw-p 00000000 00:00 0
7ffff7ffa000-7ffff7ffc000 r-xp 00000000 00:00 0                          [vdso]
7ffff7ffc000-7ffff7ffd000 r--p 00022000 08:01 2097185                    /lib/x86_64-linux-gnu/ld-2.15.so
7ffff7ffd000-7ffff7fff000 rw-p 00023000 08:01 2097185                    /lib/x86_64-linux-gnu/ld-2.15.so
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0                          [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
(gdb) quit

ここで、gdbがASLRを無効にしていることに注意する。 上の結果から、主なアドレスをまとめると次のようになる。

• 0x400000: 実行ファイルの実行可能領域
• 0x600000: 実行ファイルの実行不可領域
• 0x602000: ヒープ領域
• 0x7ffff7a1a000: 共有ライブラリ（libc）
• 0x7ffffffde000: スタック領域

実行ファイルのメモリ配置について

実行ファイルのメモリ配置は、PIEでない場合リンク時に決まる。 readelfコマンドでセクション情報を表示させると、アドレスの項目に実際のアドレスが入っていることがわかる。

$ readelf -S a.out
There are 30 section headers, starting at offset 0x1148:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         0000000000400238  00000238
       000000000000001c  0000000000000000   A       0     0     1
  [ 2] .note.ABI-tag     NOTE             0000000000400254  00000254
       0000000000000020  0000000000000000   A       0     0     4

(snip)

  [18] .ctors            PROGBITS         0000000000600e28  00000e28
       0000000000000010  0000000000000000  WA       0     0     8
  [19] .dtors            PROGBITS         0000000000600e38  00000e38
       0000000000000010  0000000000000000  WA       0     0     8

(snip)

  [25] .bss              NOBITS           0000000000601030  00001030
       0000000000000010  0000000000000000  WA       0     0     8

(snip)

このアドレスは、リンカが使うリンカスクリプトによって決められている。 コンパイル時にリンカにverboseオプションをつけると、使われているリンカスクリプトを表示させることができる。

$ gcc -Wl,--verbose hello.c
GNU ld (GNU Binutils for Ubuntu) 2.22
  Supported emulations:
   elf_x86_64
   elf32_x86_64
   elf_i386
   i386linux
   elf_l1om
   elf_k1om
using internal linker script:
==================================================
/* Script for -z combreloc: combine and sort reloc sections */
OUTPUT_FORMAT("elf64-x86-64", "elf64-x86-64",
              "elf64-x86-64")
OUTPUT_ARCH(i386:x86-64)
ENTRY(_start)
SEARCH_DIR("/usr/x86_64-linux-gnu/lib64"); SEARCH_DIR("=/usr/local/lib/x86_64-linux-gnu"); SEARCH_DIR("=/usr/local/lib64"); SEARCH_DIR("=/lib/x86_64-linux-gnu"); SEARCH_DIR("=/lib64"); SEARCH_DIR("
=/usr/lib/x86_64-linux-gnu"); SEARCH_DIR("=/usr/lib64"); SEARCH_DIR("=/usr/local/lib"); SEARCH_DIR("=/lib"); SEARCH_DIR("=/usr/lib");
SECTIONS
{
  /* Read-only sections, merged into text segment: */
  PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000)); . = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS;
  .interp         : { *(.interp) }
  .note.gnu.build-id : { *(.note.gnu.build-id) }
  .hash           : { *(.hash) }
  .gnu.hash       : { *(.gnu.hash) }
  .dynsym         : { *(.dynsym) }
  .dynstr         : { *(.dynstr) }

(snip)

  /* Adjust the address for the data segment.  We want to adjust up to
     the same address within the page on the next page up.  */
  . = ALIGN (CONSTANT (MAXPAGESIZE)) - ((CONSTANT (MAXPAGESIZE) - .) & (CONSTANT (MAXPAGESIZE) - 1)); . = DATA_SEGMENT_ALIGN (CONSTANT (MAXPAGESIZE), CONSTANT (COMMONPAGESIZE));

(snip)

}


==================================================
attempt to open /usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crt1.o succeeded
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crt1.o
attempt to open /usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crti.o succeeded
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crti.o

(snip)

attempt to open /usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crtn.o succeeded
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crtn.o
ld-linux-x86-64.so.2 needed by /lib/x86_64-linux-gnu/libc.so.6
found ld-linux-x86-64.so.2 at /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2

リンカスクリプトを見ると、read-onlyセクションがtextセクションとして0x400000から配置されていることがわかる。 また、データセグメントは次のメモリページとなるように調整されていることがわかる。

対応するソースコードは、GNU binutilsのldディレクトリにある。 リンカスクリプトのELF用テンプレートは次のファイルである。

• [binutils] ld/scripttempl/elf.sc

テンプレート中で参照されているTEXT_START_ADDRは次のファイルで定義されている。

• [binutils] ld/emulparams/elf_x86_64.sh

TEXT_START_ADDR=0x400000
MAXPAGESIZE="CONSTANT (MAXPAGESIZE)"
COMMONPAGESIZE="CONSTANT (COMMONPAGESIZE)"

ここで、CONSTANT (MAXPAGESIZE)、CONSTANT (COMMONPAGESIZE)の値には、次のファイルの定義が参照される。

• [binutils] bfd/elf64-x86-64.c

#define ELF_MAXPAGESIZE                     0x200000
#define ELF_MINPAGESIZE                     0x1000
#define ELF_COMMONPAGESIZE                  0x1000

上の定義においてELF_MAXPAGESIZEが0x200000であるため、データセグメントは0x400000+0x200000=0x600000から始まることとなる。 なお、これらの値はリンカオプションにより変更することも可能である。

$ gcc -Wl,-Ttext-segment=0x8048000,-z,max-page-size=0x1000 hello.c

$ readelf -S a.out
There are 30 section headers, starting at offset 0x1158:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         0000000008048238  00000238
       000000000000001c  0000000000000000   A       0     0     1
  [ 2] .note.ABI-tag     NOTE             0000000008048254  00000254
       0000000000000020  0000000000000000   A       0     0     4
       ...
  [18] .ctors            PROGBITS         0000000008049e28  00000e28
       0000000000000010  0000000000000000  WA       0     0     8
  [19] .dtors            PROGBITS         0000000008049e38  00000e38
       0000000000000010  0000000000000000  WA       0     0     8
       ...

共有ライブラリのメモリ配置について

共有ライブラリは、実行ファイルで指定されたELFインタプリタ（/lib/ld-linux.so.2）がmmapにより配置する。 具体的には、次のような順序で関数が呼ばれていく。

• [svn] Index of /branches/eglibc-2_15/libc

[sysdeps/x86_64/dl-machine.h] _start
[elf/rtld.c] _dl_start
[elf/rtld.c] _dl_start_final
[elf/dl-sysdep.c] _dl_sysdep_start
[elf/rtld.c] dl_main
[elf/dl-deps.c] _dl_map_object_deps
[include/dlfcn.h] _dl_catch_error
[elf/dl-deps.c] openaux
[elf/dl-load.c] _dl_map_object
[elf/dl-load.c]  _dl_map_object_from_fd

setarchコマンドでASLRを無効化した上で、straceコマンドを使い実行時のシステムコールをトレースしてみる。

$ setarch x86_64 -R strace ./a.out >/dev/null
execve("./a.out", ["./a.out"], [/* 18 vars */]) = 0
brk(0)                                  = 0x1402000
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7ff8000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=26780, ...}) = 0
mmap(NULL, 26780, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7ffff7ff1000
close(3)                                = 0
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
open("/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\200\30\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1815224, ...}) = 0
mmap(NULL, 3929304, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7ffff7a1a000
mprotect(0x7ffff7bcf000, 2097152, PROT_NONE) = 0
mmap(0x7ffff7dcf000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1b5000) = 0x7ffff7dcf000
mmap(0x7ffff7dd5000, 17624, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7ffff7dd5000
close(3)                                = 0
...
write(1, "Hello, world!\n", 14)         = 14
exit_group(0)                           = ?

上の結果から、libcのメモリを確保する際におけるmmapの第一引数はNULLとなっており、実際に配置されるアドレス0x7ffff7a1a000はmmapが決めていることがわかる。

mmapが確保するメモリアドレスの初期値は、LinuxカーネルがELF実行ファイルを読み込む際に決められる。 具体的には、次のような順序で関数が呼ばれていく。

• Linux/fs/binfmt_elf.c
• Linux/fs/exec.c
• Linux/arch/x86/mm/mmap.c

[fs/binfmt_elf.c] load_elf_binary
[fs/exec.c] setup_new_exec
[arch/x86/mm/mmap.c] arch_pick_mmap_layout
[arch/x86/mm/mmap.c] mmap_base

ここで、mmap_base関数は次のようになっている。

 54 #define MIN_GAP (128*1024*1024UL + stack_maxrandom_size())
 55 #define MAX_GAP (TASK_SIZE/6*5)
    ...
 85 static unsigned long mmap_base(void)
 86 {
 87         unsigned long gap = rlimit(RLIMIT_STACK);
 88 
 89         if (gap < MIN_GAP)
 90                 gap = MIN_GAP;
 91         else if (gap > MAX_GAP)
 92                 gap = MAX_GAP;
 93 
 94         return PAGE_ALIGN(TASK_SIZE - gap - mmap_rnd());
 95 }

ASLRが無効の場合、stack_maxrandom_size()かつmmap_rnd() == 0となる。 ここで、rlimit(RLIMIT_STACK)の値をulimitコマンドで調べてみると次のようになる。

$ ulimit -s
8192

ulimitコマンドはキロバイト単位、rlimit(RLIMIT_STACK)はバイト単位であるため、この場合gap == 8192*1024となる。 これはMIN_GAPよりも小さいため、gapはMIN_GAPに補正される。

また、TASK_SIZEに関する定義をまとめると次のようになる。

• Linux/arch/x86/include/asm/processor.h
• Linux/arch/x86/include/asm/page_types.h
• Linux/include/uapi/linux/const.h

833 #ifdef CONFIG_X86_32
    ...
893 #else
894 /*
895  * User space process size. 47bits minus one guard page.
896  */
897 #define TASK_SIZE_MAX   ((1UL << 47) - PAGE_SIZE)
898 
899 /* This decides where the kernel will search for a free chunk of vm
900  * space during mmap's.
901  */
902 #define IA32_PAGE_OFFSET        ((current->personality & ADDR_LIMIT_3GB) ? \
903                                         0xc0000000 : 0xFFFFe000)
904 
905 #define TASK_SIZE               (test_thread_flag(TIF_ADDR32) ? \
906                                         IA32_PAGE_OFFSET : TASK_SIZE_MAX)
907 #define TASK_SIZE_OF(child)     ((test_tsk_thread_flag(child, TIF_ADDR32)) ? \
908                                         IA32_PAGE_OFFSET : TASK_SIZE_MAX)
909 
910 #define STACK_TOP               TASK_SIZE
911 #define STACK_TOP_MAX           TASK_SIZE_MAX
    ...
935 #endif /* CONFIG_X86_64 */

  7 /* PAGE_SHIFT determines the page size */
  8 #define PAGE_SHIFT      12
  9 #define PAGE_SIZE       (_AC(1,UL) << PAGE_SHIFT)
 10 #define PAGE_MASK       (~(PAGE_SIZE-1))

 19 #define __AC(X,Y)       (X##Y)
 20 #define _AC(X,Y)        __AC(X,Y)

以上をもとに、mmap_baseが返すアドレスを計算してみる。

$ python
Python 2.7.3 (default, Feb 27 2014, 19:58:35)
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> PAGE_SHIFT = 12
>>> PAGE_SIZE = 1L << PAGE_SHIFT
>>> TASK_SIZE_MAX = (1L << 47) - PAGE_SIZE
>>> TASK_SIZE = TASK_SIZE_MAX
>>> MIN_GAP = 128*1024*1024L
>>> hex(TASK_SIZE)
'0x7ffffffff000L'
>>> hex(TASK_SIZE - MIN_GAP)
'0x7ffff7fff000L'

これは、一番最初にmmapで配置されるld-linux.soのメモリ領域の底となっている。

スタック領域のメモリ配置について

スタック領域のメモリ配置も、LinuxカーネルがELF実行ファイルを読み込む際に決められる。 具体的には、binfmt_elf.cのload_elf_binary関数にある次のコードが対応する。

• Linux/fs/binfmt_elf.c

737         /* Do this so that we can load the interpreter, if need be.  We will
738            change some of these later */
739         retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP),
740                                  executable_stack);
741         if (retval < 0) {
742                 send_sig(SIGKILL, current, 0);
743                 goto out_free_dentry;
744         }
745         
746         current->mm->start_stack = bprm->p;

ASLRが無効な場合、randomize_stack_top(STACK_TOP) == STACK_TOPとなる。 共有ライブラリのパートで示した定義を参照すると、STACK_TOP == TASK_SIZE == 0x7ffffffff000であることがわかる。 これはスタック領域の底となっている。

この後は、setup_arg_pages関数にある次のコードによりスタックサイズが決められ、その分の領域が確保される。

• Linux/fs/exec.c

723         stack_expand = 131072UL; /* randomly 32*4k (or 2*64k) pages */
724         stack_size = vma->vm_end - vma->vm_start;
725         /*
726          * Align this down to a page boundary as expand_stack
727          * will align it up.
728          */
729         rlim_stack = rlimit(RLIMIT_STACK) & PAGE_MASK;
730 #ifdef CONFIG_STACK_GROWSUP
731         if (stack_size + stack_expand > rlim_stack)
732                 stack_base = vma->vm_start + rlim_stack;
733         else
734                 stack_base = vma->vm_end + stack_expand;
735 #else
736         if (stack_size + stack_expand > rlim_stack)
737                 stack_base = vma->vm_end - rlim_stack;
738         else
739                 stack_base = vma->vm_start - stack_expand;
740 #endif
741         current->mm->start_stack = bprm->p;
742         ret = expand_stack(vma, stack_base);

ここではstack_expand = 131072UL == 0x20000ULかつrlim_stack == 0x800000であるから、stack_base == vma->vm_start - stack_expandとなる。 これにguard pageとして確保される領域のサイズ0x1000をさらに引くと0x7ffffffde000となり、確認したスタック領域のアドレスと一致する。

ヒープ領域のメモリ配置について

ヒープ領域のベースアドレスは、基本的にはbssセグメントのあるページの次のページとなる。 これは、ヒープ領域がbrkシステムコールを使って確保されるためである。 brkシステムコールはデータセグメントの境界を変更するものであり、ヒープ領域はこの境界を拡張する形で確保される。

ヒープ領域の確保は、初めてmalloc関数が呼ばれたタイミングで行われる。 具体的には、mallocのエイリアスであるpublic_mALLOcから、_int_malloc、sYSMALLOcの順の進み、次のコードでメモリ領域が確保されることになる。

• [glibc] malloc/malloc.c

  /* Request enough space for nb + pad + overhead */

  size = nb + mp_.top_pad + MINSIZE;

  /*
    If contiguous, we can subtract out existing space that we hope to
    combine with new space. We add it back later only if
    we don't actually get contiguous space.
  */

  if (contiguous(av))
    size -= old_size;

  /*
    Round to a multiple of page size.
    If MORECORE is not contiguous, this ensures that we only call it
    with whole-page arguments.  And if MORECORE is contiguous and
    this is not first time through, this preserves page-alignment of
    previous calls. Otherwise, we correct to page-align below.
  */

  size = (size + pagemask) & ~pagemask;

  /*
    Don't try to call MORECORE if argument is so big as to appear
    negative. Note that since mmap takes size_t arg, it may succeed
    below even if we cannot call MORECORE.
  */

  if (size > 0)
    brk = (char*)(MORECORE(size));

ここで、nb + mp_.top_pad + MINSIZEは「mallocで要求されたサイズ＋領域を取得する際のベースサイズ＋malloc_chunkの最小サイズ」を意味する。 最初に書いたコードではnb == 20であり、malloc_chunkの定義からMINSIZE == 32である。 そして、mp_.top_padのデフォルト値はDEFAULT_TOP_PADであり、これは次のように定義されている。

• [glibc] sysdeps/generic/malloc-machine.h

#ifndef DEFAULT_TOP_PAD
# define DEFAULT_TOP_PAD 131072
#endif

したがって、size == 20 + 131072 + 32 == 0x20034となり、ページサイズの倍数に揃えられることでこれは0x21000となる。 メモリの確保はMORECORE(size)により行われるが、これに関する定義をまとめると次のようになる。

• [glibc] malloc/malloc.c
• [glibc] malloc/morecore.c
• [glibc] misc/sbrk.c

#define MORECORE         (*__morecore)
void *(*__morecore)(ptrdiff_t) = __default_morecore;

/* Allocate INCREMENT more bytes of data space,
   and return the start of data space, or NULL on errors.
   If INCREMENT is negative, shrink data space.  */
__malloc_ptr_t
__default_morecore (increment)
     __malloc_ptrdiff_t increment;
{
  __malloc_ptr_t result = (__malloc_ptr_t) __sbrk (increment);
  if (result == (__malloc_ptr_t) -1)
    return NULL;
  return result;
}
libc_hidden_def (__default_morecore)

/* Extend the process's data space by INCREMENT.
   If INCREMENT is negative, shrink data space by - INCREMENT.
   Return start of new space allocated, or -1 for errors.  */
void *
__sbrk (intptr_t increment)
{
  void *oldbrk;

  /* If this is not part of the dynamic library or the library is used
     via dynamic loading in a statically linked program update
     __curbrk from the kernel's brk value.  That way two separate
     instances of __brk and __sbrk can share the heap, returning
     interleaved pieces of it.  */
  if (__curbrk == NULL || __libc_multiple_libcs)
    if (__brk (0) < 0)       /* Initialize the break.  */
      return (void *) -1;

  if (increment == 0)
    return __curbrk;

  oldbrk = __curbrk;
  if ((increment > 0
       ? ((uintptr_t) oldbrk + (uintptr_t) increment < (uintptr_t) oldbrk)
       : ((uintptr_t) oldbrk < (uintptr_t) -increment))
      || __brk (oldbrk + increment) < 0)
    return (void *) -1;

  return oldbrk;
}
libc_hidden_def (__sbrk)
weak_alias (__sbrk, sbrk)

つまり、sbrk関数を経由してbrkシステムコールが呼ばれることになる。 brkシステムコールは変更後の境界のアドレスを引数に取る。 一方、sbrk関数は増分を引数に取り、brkシステムコールを2度呼ぶことにより境界のアドレスを増減させる関数である。

setarchコマンドでASLRを無効にした上で、straceコマンドにより実行時のシステムコールをトレースしてみる。

$ setarch x86_64 -R strace ./a.out >/dev/null
execve("./a.out", ["./a.out"], [/* 18 vars */]) = 0
...
brk(0)                                  = 0x602000
brk(0x623000)                           = 0x623000
fstat(1, {st_mode=S_IFCHR|0666, st_rdev=makedev(1, 3), ...}) = 0
ioctl(1, SNDCTL_TMR_TIMEBASE or TCGETS, 0x7fffffffe478) = -1 ENOTTY (Inappropriate ioctl for device)
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7ff7000
write(1, "Hello, world!\n", 14)         = 14
exit_group(0)                           = ?

上の結果から、mallocが呼ばれるタイミングでbrkシステムコールが2度呼ばれ、0x21000だけヒープ領域が確保されていることがわかる。 具体的には、一度目のbrkで現在の境界アドレスを取得し、二度目のbrkで増減後の境界アドレスがセットされている。

ASLRによるアドレスのランダム化

基本的に、binfmt_elf.cのload_elf_binary関数でELFファイルが読み込まれる際に行われる。

PIEの場合の実行ファイル

load_elf_binary関数の次の箇所が関係する。

• Linux/fs/binfmt_elf.c

795                 vaddr = elf_ppnt->p_vaddr;
796                 if (loc->elf_ex.e_type == ET_EXEC || load_addr_set) {
797                         elf_flags |= MAP_FIXED;
798                 } else if (loc->elf_ex.e_type == ET_DYN) {
799                         /* Try and get dynamic programs out of the way of the
800                          * default mmap base, as well as whatever program they
801                          * might try to exec.  This is because the brk will
802                          * follow the loader, and is not movable.  */
803 #ifdef CONFIG_ARCH_BINFMT_ELF_RANDOMIZE_PIE
804                         /* Memory randomization might have been switched off
805                          * in runtime via sysctl or explicit setting of
806                          * personality flags.
807                          * If that is the case, retain the original non-zero
808                          * load_bias value in order to establish proper
809                          * non-randomized mappings.
810                          */
811                         if (current->flags & PF_RANDOMIZE)
812                                 load_bias = 0;
813                         else
814                                 load_bias = ELF_PAGESTART(ELF_ET_DYN_BASE - vaddr);
815 #else
816                         load_bias = ELF_PAGESTART(ELF_ET_DYN_BASE - vaddr);
817 #endif
818                 }
819 
820                 error = elf_map(bprm->file, load_bias + vaddr, elf_ppnt,
821                                 elf_prot, elf_flags, 0);
822                 if (BAD_ADDR(error)) {
823                         send_sig(SIGKILL, current, 0);
824                         retval = IS_ERR((void *)error) ?
825                                 PTR_ERR((void*)error) : -EINVAL;
826                         goto out_free_dentry;
827                 }

これはELFのプログラムヘッダでタイプがPT_LOADとなっているエントリを読み込む箇所である。 PIEの場合ELF自身のタイプはET_DYNとなるため、load_biasは0となる。 そして、次に示すelf_map関数から、mmapによってメモリ領域が確保される。

• Linux/fs/binfmt_elf.c

335 static unsigned long elf_map(struct file *filep, unsigned long addr,
336                 struct elf_phdr *eppnt, int prot, int type,
337                 unsigned long total_size)
338 {
339         unsigned long map_addr;
340         unsigned long size = eppnt->p_filesz + ELF_PAGEOFFSET(eppnt->p_vaddr);
341         unsigned long off = eppnt->p_offset - ELF_PAGEOFFSET(eppnt->p_vaddr);
342         addr = ELF_PAGESTART(addr);
343         size = ELF_PAGEALIGN(size);
344 
345         /* mmap() will return -EINVAL if given a zero size, but a
346          * segment with zero filesize is perfectly valid */
347         if (!size)
348                 return addr;
349 
350         /*
351         * total_size is the size of the ELF (interpreter) image.
352         * The _first_ mmap needs to know the full size, otherwise
353         * randomization might put this image into an overlapping
354         * position with the ELF binary image. (since size < total_size)
355         * So we first map the 'big' image - and unmap the remainder at
356         * the end. (which unmap is needed for ELF images with holes.)
357         */
358         if (total_size) {
359                 total_size = ELF_PAGEALIGN(total_size);
360                 map_addr = vm_mmap(filep, addr, total_size, prot, type, off);
361                 if (!BAD_ADDR(map_addr))
362                         vm_munmap(map_addr+size, total_size-size);
363         } else
364                 map_addr = vm_mmap(filep, addr, size, prot, type, off);
365 
366         return(map_addr);
367 }

ここで、PIEでコンパイルした実行ファイルのプログラムヘッダを調べてみる。

$ gcc -fPIE -pie hello.c

$ readelf -l a.out

Elf file type is DYN (Shared object file)
Entry point 0x6c0
There are 9 program headers, starting at offset 64

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  PHDR           0x0000000000000040 0x0000000000000040 0x0000000000000040
                 0x00000000000001f8 0x00000000000001f8  R E    8
  INTERP         0x0000000000000238 0x0000000000000238 0x0000000000000238
                 0x000000000000001c 0x000000000000001c  R      1
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
  LOAD           0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x00000000000009cc 0x00000000000009cc  R E    200000
  LOAD           0x0000000000000e00 0x0000000000200e00 0x0000000000200e00
                 0x0000000000000238 0x0000000000000248  RW     200000
  DYNAMIC        0x0000000000000e28 0x0000000000200e28 0x0000000000200e28
                 0x0000000000000190 0x0000000000000190  RW     8
  NOTE           0x0000000000000254 0x0000000000000254 0x0000000000000254
                 0x0000000000000044 0x0000000000000044  R      4
  GNU_EH_FRAME   0x00000000000008fc 0x00000000000008fc 0x00000000000008fc
                 0x000000000000002c 0x000000000000002c  R      4
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     8
  GNU_RELRO      0x0000000000000e00 0x0000000000200e00 0x0000000000200e00
                 0x0000000000000200 0x0000000000000200  R      1

 Section to Segment mapping:
  Segment Sections...
   00
   01     .interp
   02     .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .rela.plt .init .plt .text .fini .rodata .eh_frame_hdr .eh_frame
   03     .ctors .dtors .jcr .dynamic .got .got.plt .data .bss
   04     .dynamic
   05     .note.ABI-tag .note.gnu.build-id
   06     .eh_frame_hdr
   07
   08     .ctors .dtors .jcr .dynamic .got

LOADとなっているエントリは二つあり、それぞれ実行可能領域、実行不可領域に対応している。 また、VirtAddr (vaddr)、FileSiz (size) はそれぞれ0、0x9ccおよび0x200e00、0x238となっている。

したがって、ページ境界へのアラインメントも考慮すると、まずaddr = mmap(0, 0x1000, ...)に相当する処理が呼ばれることになる。 この後、load_addr_set = 1およびload_bias = addrが行われるため、次のPT_LOADエントリについてはelf_flagsにMAP_FIXEDがセットされた上でmmap(load_bias + 0x200000, 0x1000, ...)が呼ばれる。 よって、ランダム化が行われるbit数はmmapで確保される場合のbit数と同じである。 具体的なbit数については次で説明する。

共有ライブラリなどmmapで確保される領域

load_elf_binary関数から、setup_new_exec関数、arch_pick_mmap_layout関数、mmap_base関数の順に進みランダム化される。 32bit環境の場合8bit、64bit環境の場合28bit。

• Linux/fs/binfmt_elf.c
• Linux/fs/exec.c
• Linux/arch/x86/mm/mmap.c

735         setup_new_exec(bprm);

1103         arch_pick_mmap_layout(current->mm);

 68 static unsigned long mmap_rnd(void)
 69 {
 70         unsigned long rnd = 0;
 71 
 72         /*
 73         *  8 bits of randomness in 32bit mmaps, 20 address space bits
 74         * 28 bits of randomness in 64bit mmaps, 40 address space bits
 75         */
 76         if (current->flags & PF_RANDOMIZE) {
 77                 if (mmap_is_ia32())
 78                         rnd = get_random_int() % (1<<8);
 79                 else
 80                         rnd = get_random_int() % (1<<28);
 81         }
 82         return rnd << PAGE_SHIFT;
 83 }
 84 
 85 static unsigned long mmap_base(void)
 86 {
 87         unsigned long gap = rlimit(RLIMIT_STACK);
 88 
 89         if (gap < MIN_GAP)
 90                 gap = MIN_GAP;
 91         else if (gap > MAX_GAP)
 92                 gap = MAX_GAP;
 93 
 94         return PAGE_ALIGN(TASK_SIZE - gap - mmap_rnd());
 95 }
    ...
109 /*
110  * This function, called very early during the creation of a new
111  * process VM image, sets up which VM layout function to use:
112  */
113 void arch_pick_mmap_layout(struct mm_struct *mm)
114 {
115         mm->mmap_legacy_base = mmap_legacy_base();
116         mm->mmap_base = mmap_base();
117 
118         if (mmap_is_legacy()) {
119                 mm->mmap_base = mm->mmap_legacy_base;
120                 mm->get_unmapped_area = arch_get_unmapped_area;
121         } else {
122                 mm->get_unmapped_area = arch_get_unmapped_area_topdown;
123         }
124 }

スタック領域

load_elf_binary関数において、randomize_stack_top関数によりページ単位でランダム化が行われる。 ただし、ランダム値がunsigned intすなわち32bit符号なし整数として定義されているため、ランダム化の上限は20bitとなる。 さらに、setup_arg_pages関数内で、arch_align_stack関数によりランダム化が行われるが、ページ境界へのアラインメントが行われるため全体には影響しない。 32bit環境の場合11bit、64bit環境の場合20bit。

• Linux/fs/binfmt_elf.c
• Linux/fs/exec.c
• Linux/arch/x86/kernel/process.c
• Linux/arch/x86/include/asm/elf.h
• Linux/arch/x86/include/asm/page_types.h
• Linux/include/linux/mm.h
• Linux/include/linux/kernel.h
• Linux/include/uapi/linux/kernel.h

555 static unsigned long randomize_stack_top(unsigned long stack_top)
556 {
557         unsigned int random_variable = 0;
558 
559         if ((current->flags & PF_RANDOMIZE) &&
560                 !(current->personality & ADDR_NO_RANDOMIZE)) {
561                 random_variable = get_random_int() & STACK_RND_MASK;
562                 random_variable <<= PAGE_SHIFT;
563         }
564 #ifdef CONFIG_STACK_GROWSUP
565         return PAGE_ALIGN(stack_top) + random_variable;
566 #else
567         return PAGE_ALIGN(stack_top) - random_variable;
568 #endif
569 }
570 
571 static int load_elf_binary(struct linux_binprm *bprm)
572 {
            ...
737         /* Do this so that we can load the interpreter, if need be.  We will
738            change some of these later */
739         retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP),
740                                  executable_stack);
741         if (retval < 0) {
742                 send_sig(SIGKILL, current, 0);
743                 goto out_free_dentry;
744         }
745         
746         current->mm->start_stack = bprm->p;
            ...
1007 }

675         stack_top = arch_align_stack(stack_top);
676         stack_top = PAGE_ALIGN(stack_top);
677 
678         if (unlikely(stack_top < mmap_min_addr) ||
679             unlikely(vma->vm_end - vma->vm_start >= stack_top - mmap_min_addr))
680                 return -ENOMEM;
681 
682         stack_shift = vma->vm_end - stack_top;
683 
684         bprm->p -= stack_shift;
685         mm->arg_start = bprm->p;

456 unsigned long arch_align_stack(unsigned long sp)
457 {
458         if (!(current->personality & ADDR_NO_RANDOMIZE) && randomize_va_space)
459                 sp -= get_random_int() % 8192;
460         return sp & ~0xf;
461 }

290 /* 1GB for 64bit, 8MB for 32bit */
291 #define STACK_RND_MASK (test_thread_flag(TIF_ADDR32) ? 0x7ff : 0x3fffff)

  8 #define PAGE_SHIFT      12
  9 #define PAGE_SIZE       (_AC(1,UL) << PAGE_SHIFT)

 73 #define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)

 49 #define ALIGN(x, a)             __ALIGN_KERNEL((x), (a))

  9 #define __ALIGN_KERNEL(x, a)            __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
 10 #define __ALIGN_KERNEL_MASK(x, mask)    (((x) + (mask)) & ~(mask))

ヒープ領域

load_elf_binary関数において、arch_randomize_brk関数によってランダム化される。 32bit環境、64bit環境どちらの場合も13bit。

• Linux/fs/binfmt_elf.c
• Linux/arch/x86/kernel/process.c
• Linux/drivers/char/random.c

957 #ifdef arch_randomize_brk
958         if ((current->flags & PF_RANDOMIZE) && (randomize_va_space > 1)) {
959                 current->mm->brk = current->mm->start_brk =
960                         arch_randomize_brk(current->mm);
961 #ifdef CONFIG_COMPAT_BRK
962                 current->brk_randomized = 1;
963 #endif
964         }
965 #endif

463 unsigned long arch_randomize_brk(struct mm_struct *mm)
464 {
465         unsigned long range_end = mm->brk + 0x02000000;
466         return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
467 }

1691 /*
1692  * randomize_range() returns a start address such that
1693  *
1694  *    [...... <range> .....]
1695  *  start                  end
1696  *
1697  * a <range> with size "len" starting at the return value is inside in the
1698  * area defined by [start, end], but is otherwise randomized.
1699  */
1700 unsigned long
1701 randomize_range(unsigned long start, unsigned long end, unsigned long len)
1702 {
1703         unsigned long range = end - len - start;
1704 
1705         if (end <= start + len)
1706                 return 0;
1707         return PAGE_ALIGN(get_random_int() % range + start);
1708 }

ランダム化bit数のまとめ

	PIE実行ファイル 共有ライブラリ	スタック領域	ヒープ領域
32bit	8bit	11bit	13bit
64bit	28bit	20bit	13bit

関連リンク

• H. J. Lu - PATCH: Getting MAXPAGESIZE from ELF_MAXPAGESIZE
• プログラムはどう動くのか? ～ ELFの黒魔術をかいまみる
• malloc(3)のメモリ管理構造 | VA Linux Systems Japan株式会社
• ASLR, setarch -RL, prelink, PIE and LD_USE_LOAD_BIAS - memologue
• Linux kernel ASLR Implementation | xorl %eax, %eax
• Stack Smashing as of Today (Black Hat Europe 2009)