本文目標

• 了解連結器與常見的連結方式
• Lazy-binding
• 建立對 elf file format 的基本認知

連結器的用途

連結器讓我們能夠對各個獨立文件進行編譯與組譯，這樣的好處顯而易見: 當一個專案有多個檔案時，如果僅修改一個檔案，我們不需要重新編譯全部的程式碼，而是編譯更動的程式再做連結即可。

靜態連結與動態連結

上圖取自該網站。

靜態連結

多數人對於程式執行的第一個步驟便是執行 main() 函式，實際上卻不是這麼一回事。
假設有一支程式是以靜態連結的方式編譯，該程式被執行後的大致步驟如下:

./program -> fork() -> execve("./program", *argv[], *envp[])

執行 execve() 後，執行緒會從作業系統的 user_mode 切換至 kernel_mode 繼續執行:

sys_execve() -> do_execve() -> search_binary_handler() -> load_elf_binary()

載入執行檔的 binary 資料後，再切換回 user_mode 繼續執行:

_start -> main

關於系統呼叫 fork() 以及 execve() ，可以參考作業系統章節以更深入的了解它，至於本篇的重點則會聚焦在執行檔 elf 身上。

靜態連結的缺陷

上面所提到的方法便是靜態連結，這個方式會在程式運行之前將所有的 Library 進行連結與載入，如果有多個程式都使用到某一個很大的 Library ，便會產出不小的效能開銷。
此外，若使用靜態連結綁定的 Library 被發現有設計錯誤，即使該 Library 的作者已經將他更新，使用靜態連結的程式中仍是綁定舊有的 Library 。

動態連結

為了解決上述的問題，現今的系統會採用 Dynamic linking 的設計，這樣做會有以下優點:

• 動態連結的 Library 只有在第一次載入時會產生動態開銷，之後都會採取 Fast linking 的方式做載入。
• 如果有多個程式依賴同一個 Library ，那這個動態連結庫也只會被加載一次。

補充:
使用動態連結產生的程式碼與傳統的方式沒有太大的差異，最大的差別是，跳轉的目標並不是實際的函式，而是帶有三條指令的 Stub function 。
Stub function 會查詢主記憶體中的 Table 找出實際函式的位置再進行跳轉。
也因為第一次呼叫函式時，該函式並沒有被載入到主記憶體中 (Table 中找不到實體位置)，所以在第一次調用函式時會產生額外的開銷。

./program -> fork() -> execve("./program", *argv[], *envp[])

執行 execve() 後，執行緒會從作業系統的 user_mode 切換至 kernel_mode 繼續執行:

sys_execve() -> do_execve() -> search_binary_handler() -> load_elf_binary()

載入執行檔的 binary 資料後，再切換回 user_mode 繼續執行:

ld.so -> _start -> libc_start_main() -> _init -> main

上面的 ld.so 便是動態連結器，它會負責按照可執行檔案運作時的需要載入與連結 shared library 。

Lazy-binding

當程式是利用 Dynamic linking 的方式做連結時，其函式位址會在執行週期才確定。這樣做的好處顯而易見: 程式引入的 library 的函式有千百個，但在執行周其中並不會都使用到，當函式被呼叫時再去載入它，就可以大幅提升執行效率。

判別是否為 Lazy-binding 的方法:
當我們利用逆向工具查看組合語言時，如果有發現 call function 的形式如 call puts@plt ，就代表該函式會在執行期間才做載入。

• GOT: Global Offset Table

  GOT 其實就是一個存放函式指標的陣列。

  用來記錄在 ELF file 中用到的 Shared library 中符號的絕對地址， GOT 主要涵蓋以下內容:

  • .dynamic
    動態連結的資訊。

  • .got
    儲存全域變數的位址。

  • .got.plt

    Name	Description

    | address of .dynamic | 指向 GOT 的 .dynamic |
    | link_map | 一個鍊結串列，用來紀錄用到的 Library |
    | dl_runtime_resolve | 找出函式的位址 |

  • .data

• PLT: Procedure Linkage Table

流程

• 程式碼中呼叫了 func
• 執行 func@plt
• func@plt 會跳到 GOT 的 .got.plt 尋找 func 的位置
• 將 func 的 id 推入 Stack 中。
• 由於 func 是第一次呼叫，所以沒辦法順利在 .got.plt 找到函式位址，這時系統就會把 func 的位址寫進 .got.plt 當中。
• 如此一來，等到 func 第二次被呼叫時，就可以直接找到其位址。

AIS3 2021 - Write me

#include <stdlib.h>
#include <stdio.h>
int main()
{
    setvbuf(stdin, 0, 2, 0);
    setvbuf(stdout, 0, 2, 0);
    void *systemgot = 0x404028;
    void *scanfgot = 0x404040;
    //void *systemgot = (void *)((long long)(*(int *)(systemptr+2))+(long long)(systemptr+6));
    *(long long *)systemgot = (long long)0x0;

    printf("Address: ");
    void *addr;
    long long v;
    scanf("%ld",&addr);
    printf("Value: ");
    scanf("%ld",&v);
    *(long long *)addr = (long long)v;
    *(long long *)scanfgot = (long long)0x0;
    printf("OK! Shell for you :)\n");
    system("/bin/sh");
    return 0;
}

這一題將 GOT 中的 system() 清掉了，所以我們需要將它重新指向 PLT ，輸入:

Address: 4210728 (0x404028)
Value: 4198480 (0x401050)

即可獲得 Flag 。
至於為何是輸入 4198480 呢?我們先使用 IDA 打開 elf 檔案並查看 GOT :

_got_plt        segment qword public 'DATA' use64
.got.plt:0000000000404000                 assume cs:_got_plt
.got.plt:0000000000404000                 ;org 404000h
.got.plt:0000000000404000 _GLOBAL_OFFSET_TABLE_ dq offset _DYNAMIC
.got.plt:0000000000404008 qword_404008    dq 0                    ; DATA XREF: sub_401020↑r
.got.plt:0000000000404010 qword_404010    dq 0                    ; DATA XREF: sub_401020+6↑r
.got.plt:0000000000404018 off_404018      dq offset puts          ; DATA XREF: _puts+4↑r
.got.plt:0000000000404020 off_404020      dq offset __stack_chk_fail
.got.plt:0000000000404020                                         ; DATA XREF: ___stack_chk_fail+4↑r
.got.plt:0000000000404028 off_404028      dq offset system        ; DATA XREF: _system+4↑r
.got.plt:0000000000404028                                         ; main+5D↑o
.got.plt:0000000000404030 off_404030      dq offset printf        ; DATA XREF: _printf+4↑r
.got.plt:0000000000404038 off_404038      dq offset setvbuf       ; DATA XREF: _setvbuf+4↑r
.got.plt:0000000000404040 off_404040      dq offset __isoc99_scanf
.got.plt:0000000000404040                                         ; DATA XREF: ___isoc99_scanf+4↑r
.got.plt:0000000000404040                                         ; main+65↑o
.got.plt:0000000000404040 _got_plt        ends

對照基指可以得知 system() 會噴進 PLT 的第三個位址:

plt:0000000000401026 ; ---------------------------------------------------------------------------
.plt:000000000040102D                 align 10h
.plt:0000000000401030 ; [0000000F BYTES: COLLAPSED FUNCTION sub_401030. PRESS CTRL-NUMPAD+ TO EXPAND]
.plt:000000000040103F                 align 20h
.plt:0000000000401040 ; [0000000F BYTES: COLLAPSED FUNCTION sub_401040. PRESS CTRL-NUMPAD+ TO EXPAND]
.plt:000000000040104F                 align 10h
.plt:0000000000401050 ; [0000000F BYTES: COLLAPSED FUNCTION sub_401050. PRESS CTRL-NUMPAD+ TO EXPAND]
.plt:000000000040105F                 align 20h
.plt:0000000000401060 ; [0000000F BYTES: COLLAPSED FUNCTION sub_401060. PRESS CTRL-NUMPAD+ TO EXPAND]
.plt:000000000040106F                 align 10h
.plt:0000000000401070 ; [0000000F BYTES: COLLAPSED FUNCTION sub_401070. PRESS CTRL-NUMPAD+ TO EXPAND]
.plt:000000000040107F                 align 20h
.plt:0000000000401080 ; [0000000F BYTES: COLLAPSED FUNCTION sub_401080. PRESS CTRL-NUMPAD+ TO EXPAND]
.plt:000000000040108F                 align 10h
.plt:000000000040108F _plt            ends
.plt:000000000040108F

Lazy-loading 造成的安全性問題

Lazy-binding 雖能夠大幅度的提升程式的執行效率，但也因為該機制需要 GOT 能夠被寫入，所以如果有有心人士將 PLT 的對應位置改成 system call 的位置，那呼叫 plt function 時便會變呼叫 system call ，這點需要特別注意。

淺談目的檔

a.out 是舊版類 Unix 系統中用於執行檔、目的碼和後來系統中的函式庫的一種檔案格式，這個名稱的意思是組譯器輸出。
-- 維基百科

a.out 最早可以追朔到第一版 UNIX 作業系統上。對!就是那個搭載在 PDP-7 與 PDP-11 的 UNIX 作業系統。
隨著 UNIX 與 UNIX like 被越來越多人使用，我們可以在這些作業系統上看到他的身影。

a.out 的結構

a.out 檔案主要包含(最多)七個部分，參考 C 語言定義:

/*
 * Header prepended to each a.out file.
 */
struct exec {
    long      a_magic;   /* magic number */
    unsigned  a_text;    /* size of text segment */
    unsigned  a_data;    /* size of initialized data */
    unsigned  a_bss;     /* size of uninitialized data */
    unsigned  a_syms;    /* size of symbol table */
    unsigned  a_entry;   /* entry point */
    unsigned  a_trsize;  /* size of text relocation */
    unsigned  a_drsize;  /* size of data relocation */
};

先不考慮 a_magic ，以下為七個區塊的解說:

• header (必備)

包含核心將二進位檔案載入入記憶體並執行所需的參數，也包含對動態連結器 ld 的指引。

以 C 語言程式為例，經過 gcc 編譯為 a.out 檔案後，會在 header 紀錄各個區塊所需要的大小。

• text section
  Text section 存放程式執行時被載入記憶體的機器碼和相關資料。

• data section
  已初始化的資料。

  int a = 0;
  

• text relocation
  包含連結編輯器在合併二進位檔案時修改文字段指標的記錄。

• data relocation
  與文字重定位一節類似，但是給資料段指標用的。

• symbol table
  Symbol table 包含 linker editor 用於交叉參照不同二進位檔案中變數和函式 (符號)。

  The symbol table is an array of nlist.
  -- FreeBSD Manual Pages

  至於 nlist 的結構，我們也可以參考 Linux 中的實作:

  struct nlist {
    union {
      char *n_name;
      struct nlist *n_next;
      long n_strx;
    } n_un;
    unsigned char n_type;
    char n_other;
    short n_desc;
    unsigned long n_value;
  };
  

• string table
  包含對應於符號表的字串。

屬於 a.out 的魔術

a.out 有以下多種變體:

• OMAGIC
  OMAGIC 除了必備的 header 以外，其後緊隨了 text section 和 data section ， Kernel 會將這兩個部分讀入可讀寫的記憶體當中。
• NMAGIC
  NMAGIC 與 OMAGIC 類似，差別在 data section 出現在 text section 結束後的下一頁，並且 text section 在 NMAGIC 格式為唯讀狀態。
• ZMAGIC
  ZMAGIC 格式加入了對按需分頁的支援， text section 和 data section 的長度需要是頁寬的整數倍。
• QMAGIC
  Binary file 通常會被載入到虛擬位址池的底端，以通過段錯誤擷取對空指標的解除參照。 a.out 的 Header 與 text section 的第一頁合併，通常會省下一頁的記憶體。
• CMAGIC
  舊版的 Linux 使用此格式來存放核心轉儲。

有些專業術語用中文表示會讓原意跑掉，如果對 MAGIC 真的很感興趣的話可以參考 Stackoverflow 上的問答串。

如何編譯出 a.out 檔案

若沒有指定 gcc 的輸出 -o 選項，在預設情況下， gcc 會直接把 C 語言編譯為 a.out 檔案。

可執行與可鏈結格式

a.out 的構造非常簡易，也因為這個特性， a.out 無法支援較為複雜的功能，如: 動態連結與載入等。
目前，主流的 UNIX Like 都已改採 .elf 格式作為標準的目的檔格式。

可執行與可鏈結格式 (Executable and Linkable Format) 簡稱為 elf 格式，我們通常會在編譯 C 語言程式時看到 .elf 檔案。

• .text: 放置已編譯的程式碼 (組合語言)
• .rodata: ro 表示 read-only ，該段落會放置常數
• .data: 放置已初始化的全域變數或是靜態的區域變數
• .bss: 未初始化的全域變數或是靜態的區域變數
• .debug: 此段放置除錯資訊，可以幫助我們更順利的進行程式分析 (GDB)

使用 Binutils 查看 ELF

使用 --help 選項查看 readelf 有哪些功能可用:

readelf --help

一般來說， readelf 提供了以下功能:

• -a, --all: 等同於 -h -l -s -S -r -d -V -A -I
• -h, --file-header: 查看 ELF 文件的檔頭
• -l, --program-headers, --segments: 顯示 Program headers
• -S, --section-headers: 顯示 section's header

使用 Binutils 對 ELF 反組譯

使用 --help 選項查看 objdump 有哪些功能可用:

objdump --help

objdump 僅有兩大功能:

• -D: 反組譯
• -S: 將 ELF 反組譯並與 C Source code 混合輸出

透過上面的介紹可以了解到 elf 檔案在執行週期與連結時期時會用不同的觀點存取檔案，也因為 elf 檔案非常複雜，讀者有興趣的話可以參考陳鍾誠老師的教學文章。

總結

最初規劃文章的時候本來想要用一篇講完組譯器與連結器，後來越寫越多乾脆連可執行文件與 lazy-binding 也一起補上了，希望能幫助到正在觀看文章的你 : )

Reference

• Linux 的目的檔格式 - a.out 與 ELF 之設計原理
• 維基百科
• FreeBSD Manual Pages
• 教科書：系統程式- 第 5 章、連結與載入
• RISC-V 手冊
• GOT and PLT of elf file
• GOT and PLT for pwning.
• Lazy binding
• GOT和PLT原理簡析
• Execution