ELF Symbol Resolving

2019-12-12 security ELF

這邊其實可以當成是 Lazy binding 的後篇,在 Lazy binding in ELF 中,只講到表層觀察到的現象

也就是 GOT、PLT 等相交互的運作,但細部的如 function 是如何被"找"到的還是一個黑盒子

這邊試著一步步用gdb手解一次並且留個紀錄

Lab.

為了用 gdb 方便追蹤,這邊用自己編譯的 glibc

實驗環境我用的是 ubuntu:16.04 in docker,下面是概略建置過程

apt update

apt install -y wget gcc-multilib gawk make libgetopt-complete-perl gdb vim

wget https://ftp.gnu.org/gnu/libc/glibc-2.19.tar.gz

tar zxvf glibc-2.19.tar.gz

cd glibc-2.19.tar.gz && mkdir build32 && mkdir 32

cd build32

CC="gcc -m32" CXX="g++ -m32" CFLAGS="-g -g3 -ggdb -gdwarf-4 -Og" CXXFLAGS="-g -g3 -ggdb -gdwarf-4 -Og" ../configure --prefix=/root/glibc-2.19/32 --host=i686-linux-gnu

make && make install

下面是實驗使用到的 binary source code

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

int main(void) {
	puts("Hello, world!");
	return 0;
}

// gcc -g -m32 -Wl,--dynamic-linker=/root/glibc-2.19/32/lib/ld-2.19.so,--rpath=/root/glibc-2.19/32/lib hello.c -o hello

ELF Header

既然我們的目標是 function 怎麼被找到的,則必然要知道 ELF 中有哪些資料可以參考

p/x *(Elf32_Ehdr*)0x8048000

$1 = {
  e_ident = {0x7f, 0x45, 0x4c, 0x46, 0x1, 0x1, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  e_type = 0x2, 
  e_machine = 0x3, 
  e_version = 0x1, 
  e_entry = 0x8048340, 
  e_phoff = 0x34, 
  e_shoff = 0x1a48, 
  e_flags = 0x0, 
  e_ehsize = 0x34, 
  e_phentsize = 0x20, 
  e_phnum = 0x9, 
  e_shentsize = 0x28, 
  e_shnum = 0x24, 
  e_shstrndx = 0x21
}

上面內容可以對應到 readelf -h hello,這邊主要看 e_phoff 表示 program header table 的位址 offset 是多少,其次 e_phnum 表示 program header 的數量

有了這兩個資訊之後就可以找到 program header table 了

p/x *(Elf32_Phdr*)(0x8048000+0x34)@9

$2 = ...
  {
    p_type = 0x2, 
    p_offset = 0xf0c, 
    p_vaddr = 0x8049f0c, 
    p_paddr = 0x8049f0c, 
    p_filesz = 0xf0, 
    p_memsz = 0xf0, 
    p_flags = 0x6, 
    p_align = 0x4
  } ...

這邊要找 p_typePT_DYNAMI 的 program header 也就是 2

p_vaddr 就表示了他的位址,其實就是 p_offset + 0x8048000

.dynamic Section

.dynamic section 是由 Elf32_Dyn 所組成的陣列

下面 gdb 指令印出的列表,就是 readelf -d a.out 的輸出結果對應

Tag Type 對應 d_tag、Name/Value 對應 d_val 或是 d_ptr

p/x *(Elf32_Dyn*)0x8049f0c@20

$3 = ...
  {
    d_tag = 0x5, 
    d_un = {
      d_val = 0x804822c, 
      d_ptr = 0x804822c
    }
  }, {
    d_tag = 0x6, 
    d_un = {
      d_val = 0x80481dc, 
      d_ptr = 0x80481dc
    }
  },
  ...
  {
    d_tag = 0x17, 
    d_un = {
      d_val = 0x80482c0, 
      d_ptr = 0x80482c0
    }
  ...
  }}
  
set $dynstr = (char*)0x804822c
set $dynsym = (Elf32_Sym*)0x80481dc
set $rel = (Elf32_Rel*)0x80482c0

這邊只列出會用到的部分

  • d_tag = DT_STRTAB(0x5)
    • String Table(.dynstr)
  • d_tag = DT_SYMTAB(0x6)
    • Symbol Table(.dynsym)
  • d_tag = DT_JMPREL(0x17)
    • Relocation Table(.rel.plt)

.rel.plt

Lazy binding in ELF 提過,第一次 function call 會優先跳到 PLT[0] 去執行

PLT[0]:
push *(GOT + 4)
jmp  *(GOT + 8)

foo@plt:
jmp   *(foo@GOT)
push  n         # .got.plt+0x6
jmp   PLT[0]

push n 做的是將 function index 壓入 stack 中, n 就表示第幾個 relocation entry

在這個例子中 puts 的 n = 0

p/x $rel[0]

$4 = {
  r_offset = 0x804a00c, 
  r_info = 0x107
}
  • r_offset
    • function 位址在哪,也是在第一次 function call 後會被修正的地方
  • r_info
    • 由 Relocation type 與 symbol index 組成
    • Relocation type = r_info & 0xff
    • symbol index = r_info » 8
  • 內容可以對應到 readelf -r hello

symbol index 就代表他在 .dynsym 是第幾個 symbol entry

.dynsym Section

由 relocation table(.rel.plt)知道 puts 的 symbol index 是 1

則可以找到 st_namest_value 等關鍵訊息

p/x $dynsym[1]

$5 = {
  st_name = 0x1a, 
  st_value = 0x0, 
  st_size = 0x0, 
  st_info = 0x12, 
  st_other = 0x0, 
  st_shndx = 0x0
}
  • st_name
    • 在 String Table(.dynstr)中的 offset
  • st_value
    • function address
    • 這邊會是空的因為是 binary 本身的 .dynsym
    • 內容可以對應到 readelf -s hello

.dynstr Section

有了 st_name 之後就可以查到 function name 了

p/s $dynstr + $dynsym[1].st_name

$6 = 0x8048246 "puts"

知道要找的 function 是 puts 後,就來到重頭戲了

先回憶一下 PLT[0] 做的兩件事情

PLT[0]:
push *(GOT + 4)
jmp  *(GOT + 8)
  1. 將 link_map 壓入 stack
  2. 跳到 _dl_runtime_resolve

整個運作像是下圖

這邊的 reloc_arg 就是前面講的 n

如同之前提過的 link_map 是一個講 binary 有用到的 library 串起來的 linked_list

所以結構也非常的龐大,這邊講幾個重要的屬性

  • l_next
    • 指向下一個 library
  • l_name
    • 該 library 的 path
  • l_addr
    • library 的載入位址
  • l_info
    • l_info[x] 指向 d_tag = x 的欄位

link_map 第一層是 binary 自己的

在這個例子中,要走兩層才會取到 libc

p/x *(struct link_map*)0xf7f2e920

$7 = {
  l_addr = 0x0, 
  l_name = 0xf7f2ec0c, 
  l_ld = 0x8049f0c, 
  l_next = 0xf7f2ec10, 
  l_prev = 0x0, 
  l_real = 0xf7f2e920, 
  l_ns = 0x0, 
  l_libname = 0xf7f2ec00, ...

set $libc = ((struct link_map*)0xf7f2e920).l_next.l_next

最後要在 libc 裡面找到 puts 這個 function

首先要先用 gnu_hash 取得 puts 的 hash,下面是 python 版的 gnu_hash

def hash(s):
    h = 5381
    
    for x in s:
        h = (h * 33 + ord(x)) & 0xffffffff
        
    return h
    
prin(hex(hash('puts'))) # '0x7c9c7b11'

知道 hash 為 0x7c9c7b11 後要到 hash table 中找,關鍵程式碼如下

char *hash = gnu_hash(SYMBOL_NAME);
int b = l_gnu_buckets[hash % l_nbuckets];
int i = b;
do {
    if (((l_gnu_chain_zero[i] ^ hash) >> 1) == 0)
        goto found_it;
    i++;
} while (l_gnu_chain_zero[i] & 1 == 0)

其中 l_gnu_bucketsl_nbucketsl_gnu_chain_zero 都存在 link_map 中

set $hash = 0x7c9c7b11
set $l_nbuckets = $libc.l_nbuckets
set $l_gnu_buckets = $libc.l_gnu_buckets
set $l_gnu_chain_zero = $libc.l_gnu_chain_zero

set $b = $l_gnu_buckets[$hash % $l_nbuckets]

p/x $b

$8 = 0x1ac

之後就從 0x1ac 的地方開始找

x/12wx &$l_gnu_chain_zero[$b]

0xf7d5c01c:	0x4551669e	`0x7c9c7b11`	0x0af3842d	0xa0396ff6
0xf7d5c02c:	0xaae48db4	0xf87e677d	0x9587f726	0xfc489dc3
0xf7d5c03c:	0x7c96e576	0x45f5d55c	0x7c9c7b15	0x04e475f0

這邊可以看到,我們要找的 hash 就躺在 0xf7d5c01c+4 的地方,所以找到的位置是 0x1ad

雖然 hash 一樣了但是還是要 check 一次 st_name 是否相等,避免 collision

之後就照搬前面講得如何得到 function name 的方法一樣

只不過對象換成 libc 而非 binary 本身

set $dynstr2 = (char*)$libc.l_info[5].d_un.d_val
set $dynsym2 = (Elf32_Sym*)$libc.l_info[6].d_un.d_val
p/s $dynstr2 + $dynsym2[0x1ad].st_name

$9 = 0xf7d68338 "puts"

x/i $libc.l_addr +$dynsym2[0x1ad].st_value

   0xf7dbbf0e <_IO_puts>:	push   ebp

上面先從 libc 的 link_map 中透過 l_info 取得 libc 的 .dynstr.dynsym

並確定該 symbol index 的 st_nameputs 沒錯

最後就是透過 libc 的 l_addr 加上 offset 取得 puts 本人在 libc 裡的位址

最後的最後該位址將被回填到 $rel[0].r_offset 的位置,也就是 puts@got.plt

等到下次該 function 又被呼叫時,就會直接跳到 libc 裡的實作惹

Conclusion

走了一大段路,總算是大致了解 symbol resolve 的過程,這也不是第一次嘗試理解了,貌似時間久了又會忘記,就又走了一次原路…

上面的實驗跟紀錄都是 x86 binary 但 x64 有些許不同,跟之後的 exploit 一併提吧

References