CSAPP Bomb Lab 解析

發表於 分類於 閱讀次數： Waline： 文章字數： 43k

做完了 CSAPP Bomb Lab，寫一篇解析。

題目要求

運行一個二進制文件 bomb，它包括六個”階段(phase)”，每個階段要求學生通過 stdin 輸入一個特定的字串。如果輸入了預期的字串，那麼該階段被”拆除”，進入下一個階段，直到所有炸彈被成功”拆除”。否則，炸彈就會”爆炸”，列印出”BOOM!!!”

環境

這個系統是在 x86_64 Linux 上運行的，而筆者的環境是 ARM 架構的 macOS (Apple Silicon)。

弄了半天 docker，虛擬化一個 x86_64 Ubuntu 出來，結果裡面的 gdb 不能用，不想折騰。

發現 educoder 上面有環境，可以直接用，而且免費，於是就在 educoder 上面完成了本實驗。

地址：https://www.educoder.net/paths/6g398fky

前置知識

本實驗要求掌握 gdb 的一些指令。

1. 啟動與退出 (Startup & Exit)

指令 縮寫 描述
gdb executable - 啟動 GDB 並載入可執行文件。
run [args] r 開始運行程序。如果有命令行參數，跟在後面（如 r input.txt）。
quit q 退出 GDB。
start - 運行程序並在 main 函數的第一行自動暫停（省去手動打斷點的麻煩）。
set args ... - 設置運行時的參數（在 r 之前使用）。

2. 斷點管理 (Breakpoints)

指令 縮寫 描述 範例
break <loc> b 設置斷點。支持函數名、行號、檔案名:行號。 b main
b 15
b file.c:20
info breakpoints i b 查看當前所有斷點及其編號 (Num)。 -
delete <Num> d 刪除指定編號的斷點。不加編號則刪除所有。 d 1
disable/enable <Num> - 暫時禁用或啟用某個斷點（保留配置但不生效）。 disable 2
break ... if <cond> - 條件斷點：僅當條件為真時才暫停（非常有用）。 b 10 if i==5

3. 執行控制 (Execution Control)

指令 縮寫 描述 區別點
next n 單步跳過。執行下一行程式碼。 如果遇到函數調用，不進入函數內部，直接執行完該函數。
step s 單步進入。執行下一行程式碼。 如果遇到函數調用，進入函數內部逐行除錯。
continue c 繼續運行，直到遇到下一個斷點或程序結束。 -
finish - 執行直到當前函數返回。 當你不小心 s 進了一個不想看的庫函數時，用這個跳出來。
until <line> u 運行直到指定行號。 常用於快速跳出循環。

4. 查看數據 (Inspection)

指令 縮寫 描述
print <var> p 列印變數的值。支持表達式（如 p index + 1）。
display <var> - 持續顯示。每次程序暫停時，自動列印該變數的值（適合跟蹤循環中的變數）。
info locals - 列印當前棧幀中所有局部變數的值。
whatis <var> - 查看變數的數據類型。
ptype <struct> - 查看結構體或類的具體定義（成員列表）。
x /nfu <addr> x 查看記憶體。n是數量，f是格式(x=hex, d=dec, s=str)，u是單位(b=byte, w=word)。
例如：x/10xw &array (以16進制顯示數組前10個word)。

5. 堆棧與上下文 (Stack & Context)

指令 縮寫 描述
backtrace bt 查看調用棧。顯示程序崩潰時的函數調用路徑（從 main 到當前函數）。
frame <Num> f 切換到指定的堆棧幀（配合 bt 看到的編號）。切換後可以用 p 查看該層函數的局部變數。
list l 顯示當前行附近的原始碼。

6. 提升體驗：TUI 模式 (Text User Interface)

  • layout src：螢幕分為兩半，上面顯示原始碼和當前執行行，下面是命令窗口。（強烈推薦）
  • layout asm：顯示匯編代碼。
  • layout split：同時顯示原始碼和匯編。

反匯編

我們可以使用 objdump 直接進行反匯編，查看匯編原始碼。

1
objdump -d bomb > bomb.asm

我們可以觀察到，幾個 phase 其實是幾個函數，phase_x()。

strings

在終端輸入：

1
strings bomb

這會把 bomb 文件裡所有連續的可列印字元（ASCII）都列印出來。

Phase 1

我們先看看 phase_1 長什麼樣子，disas phase_1

1
2
3
4
5
6
7
8
9
10
Dump of assembler code for function phase_1:
   0x0000000000400ee0 <+0>:     sub    $0x8,%rsp
   0x0000000000400ee4 <+4>:     mov    $0x402400,%esi
   0x0000000000400ee9 <+9>:     callq  0x401338 <strings_not_equal>
   0x0000000000400eee <+14>:    test   %eax,%eax
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>
   0x0000000000400ef2 <+18>:    callq  0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    $0x8,%rsp
   0x0000000000400efb <+27>:    retq   
End of assembler dump.

sub $0x8,%rsp 是設置棧幀，在這裡不用管。

mov $0x402400,%esi 和 callq 0x401338 <strings_not_equal> 似乎進行了字串的 strcmp。

接下來 je 0x400ef7 <phase_1+23> 就很明顯了，如果相等跳出炸彈。

設置斷點，b phase_1

之後運行程序，r，隨便輸入一些內容，就可以觸發斷點

以字串形式查看 0x402400 所指向的記憶體：x/s 0x402400

1
0x402400:       "Border relations with Canada have never been better."

我們找到了答案。

Phase 2

還是先反匯編：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Dump of assembler code for function phase_2:
   0x0000000000400efc <+0>:     push   %rbp
   0x0000000000400efd <+1>:     push   %rbx
   0x0000000000400efe <+2>:     sub    $0x28,%rsp
   0x0000000000400f02 <+6>:     mov    %rsp,%rsi
   0x0000000000400f05 <+9>:     callq  0x40145c <read_six_numbers>
   0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)
   0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:    callq  0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax
   0x0000000000400f1a <+30>:    add    %eax,%eax
   0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)
   0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:    callq  0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:    add    $0x4,%rbx
   0x0000000000400f29 <+45>:    cmp    %rbp,%rbx
   0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx
   0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp
   0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:    add    $0x28,%rsp
   0x0000000000400f40 <+68>:    pop    %rbx
   0x0000000000400f41 <+69>:    pop    %rbp
   0x0000000000400f42 <+70>:    retq   
End of assembler dump.

0x0000000000400f05 <+9>: callq 0x40145c <read_six_numbers> 這裡看到 read_six_numbers

我們可以反匯編 read_six_numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Dump of assembler code for function read_six_numbers:
   0x000000000040145c <+0>:     sub    $0x18,%rsp
   0x0000000000401460 <+4>:     mov    %rsi,%rdx
   0x0000000000401463 <+7>:     lea    0x4(%rsi),%rcx
   0x0000000000401467 <+11>:    lea    0x14(%rsi),%rax
   0x000000000040146b <+15>:    mov    %rax,0x8(%rsp)
   0x0000000000401470 <+20>:    lea    0x10(%rsi),%rax
   0x0000000000401474 <+24>:    mov    %rax,(%rsp)
   0x0000000000401478 <+28>:    lea    0xc(%rsi),%r9
   0x000000000040147c <+32>:    lea    0x8(%rsi),%r8
   0x0000000000401480 <+36>:    mov    $0x4025c3,%esi
   0x0000000000401485 <+41>:    mov    $0x0,%eax
   0x000000000040148a <+46>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x000000000040148f <+51>:    cmp    $0x5,%eax
   0x0000000000401492 <+54>:    jg     0x401499 <read_six_numbers+61>
   0x0000000000401494 <+56>:    callq  0x40143a <explode_bomb>
   0x0000000000401499 <+61>:    add    $0x18,%rsp
   0x000000000040149d <+65>:    retq   
End of assembler dump.

看到有一行 callq 0x400bf0 <__isoc99_sscanf@plt>，調用了 sscanf

我們看一眼 $0x4025c3，x/s 0x4025c3，得到 %d %d %d %d %d %d，確實是讀了六個數字。

函數調用時，參數多於六個，就會丟到棧裡面去。我們看到：

1
2
3
4
5
6
7
8
0x0000000000401460 <+4>:     mov    %rsi,%rdx
0x0000000000401463 <+7>:     lea    0x4(%rsi),%rcx
0x0000000000401467 <+11>:    lea    0x14(%rsi),%rax
0x000000000040146b <+15>:    mov    %rax,0x8(%rsp)
0x0000000000401470 <+20>:    lea    0x10(%rsi),%rax
0x0000000000401474 <+24>:    mov    %rax,(%rsp)
0x0000000000401478 <+28>:    lea    0xc(%rsi),%r9
0x000000000040147c <+32>:    lea    0x8(%rsi),%r8

參數順序：rdi, rsi, rdx, rcx, r8, r9，超過了六個參數。rsp 為棧頂指針，多於六個的參數存在棧上。

於是讀取的六個數字依次存為：rsi, rsi+4, rsi+8, rsi+12, rsi+16 (0x10 = 16), rsi+20 (0x14 = 20)

再回到 phase_2

1
0x0000000000400f02 <+6>:     mov    %rsp,%rsi

棧頂指針作為參數傳入了 read_six_numbers，因此，這六個數字應該是在 phase_2 對應棧幀的棧上

1
2
3
0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)
0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
0x0000000000400f10 <+20>:    callq  0x40143a <explode_bomb>

這裡判斷棧頂元素是否是 1，也就是說第一個元素是否是 1

之後跳轉到了 0x400f30

1
2
3
4
5
6
7
8
9
10
11
12
0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax
0x0000000000400f1a <+30>:    add    %eax,%eax
0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)
0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
0x0000000000400f20 <+36>:    callq  0x40143a <explode_bomb>
0x0000000000400f25 <+41>:    add    $0x4,%rbx
0x0000000000400f29 <+45>:    cmp    %rbp,%rbx
0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx
0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp
0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>

這裡很顯然是一個循環，依次讀取六個數位（每次移動四個位元組，正好是 int 的長度）

1
2
3
0x0000000000400f1a <+30>:    add    %eax,%eax
0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)
0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>

這六個數字，後一個是前一個的兩倍。

於是我們可以得到答案：1 2 4 8 16 32

我們也可以把代碼翻譯成 C 語言：

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i < 6; i++) {
    // mov -0x4(%rbx), %eax 
    int previous = num[i-1];
    // add %eax, %eax
    int expected = previous + previous; 
    // cmp %eax, (%rbx)
    if (num[i] != expected) {
        explode_bomb();
    }
}

Phase 3

反匯編：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Dump of assembler code for function phase_3:
   0x0000000000400f43 <+0>:     sub    $0x18,%rsp
   0x0000000000400f47 <+4>:     lea    0xc(%rsp),%rcx
   0x0000000000400f4c <+9>:     lea    0x8(%rsp),%rdx
   0x0000000000400f51 <+14>:    mov    $0x4025cf,%esi
   0x0000000000400f56 <+19>:    mov    $0x0,%eax
   0x0000000000400f5b <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000400f60 <+29>:    cmp    $0x1,%eax
   0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)
   0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax
   0x0000000000400f75 <+50>:    jmpq   *0x402470(,%rax,8)
   0x0000000000400f7c <+57>:    mov    $0xcf,%eax
   0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:    mov    $0x2c3,%eax
   0x0000000000400f88 <+69>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:    mov    $0x100,%eax
   0x0000000000400f8f <+76>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:    mov    $0x185,%eax
   0x0000000000400f96 <+83>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:    mov    $0xce,%eax
   0x0000000000400f9d <+90>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:    mov    $0x2aa,%eax
   0x0000000000400fa4 <+97>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:    mov    $0x147,%eax
   0x0000000000400fab <+104>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>:   callq  0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>:   mov    $0x0,%eax
   0x0000000000400fb7 <+116>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>:   mov    $0x137,%eax
   0x0000000000400fbe <+123>:   cmp    0xc(%rsp),%eax
   0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>:   callq  0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>:   add    $0x18,%rsp
   0x0000000000400fcd <+138>:   retq

看著有點複雜，觀察到 sscanf

看一眼 0x4025cf，x/s 0x4025cf，得到 %d %d，看起來是輸入了兩個整數

1
2
0x0000000000400f47 <+4>:     lea    0xc(%rsp),%rcx
0x0000000000400f4c <+9>:     lea    0x8(%rsp),%rdx

這兩個整數依次存為 rsp+8, rsp+c

1
2
0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)
0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>

這裡判斷了第一個數，如果這個數大於 7，就會引爆

1
2
0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax
0x0000000000400f75 <+50>:    jmpq   *0x402470(,%rax,8)

我們把第一個整數存入 eax，這裡很明顯是一個 switch 的跳轉表：0x402470 + 8*rax

eax 和 rax 實際上是同一個東西，前者是這個暫存器的前 32 位，後者是這個暫存器的完整 64 位，這是歷史遺留產物，實際上，還有 ax, ah, al，為了向後相容而保留。

我們來讀取 10 個，x/10x 0x402470，得到：

1
2
3
0x402470:       0x00400f7c      0x00000000      0x00400fb9      0x00000000
0x402480:       0x00400f83      0x00000000      0x00400f8a      0x00000000
0x402490:       0x00400f91      0x00000000

這是 switch 語句的跳轉表，與匯編代碼中對應。

我們隨便選一個就能得到正確答案，如，0 對應 0x00400f7c

1
2
3
4
5
6
0x0000000000400f7c <+57>:    mov    $0xcf,%eax
0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
...
0x0000000000400fbe <+123>:   cmp    0xc(%rsp),%eax
0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
0x0000000000400fc4 <+129>:   callq  0x40143a <explode_bomb>

第二個數和 eax 比較，相等就拆除成功

我們得到第二個數 0xcf = 207

於是，答案是 0 207

實際上，答案並不唯一，觀察代碼可以知道，每一個 switch 分支中，都對應了一個第二個整數的正確答案。

Phase 4

反編譯：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Dump of assembler code for function phase_4:
   0x000000000040100c <+0>:     sub    $0x18,%rsp
   0x0000000000401010 <+4>:     lea    0xc(%rsp),%rcx
   0x0000000000401015 <+9>:     lea    0x8(%rsp),%rdx
   0x000000000040101a <+14>:    mov    $0x4025cf,%esi
   0x000000000040101f <+19>:    mov    $0x0,%eax
   0x0000000000401024 <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
   0x0000000000401035 <+41>:    callq  0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx
   0x000000000040103f <+51>:    mov    $0x0,%esi
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi
   0x0000000000401048 <+60>:    callq  0x400fce <func4>
   0x000000000040104d <+65>:    test   %eax,%eax
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
   0x0000000000401058 <+76>:    callq  0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    $0x18,%rsp
   0x0000000000401061 <+85>:    retq   
End of assembler dump.

我們還是看到 sscanf

讀一下 0x4025cf，得到 %d %d，看起來又是讀兩個數字，分別存入 rdx, rcx

接著往下讀，jbe 0x40103a，要求 rdx <= 14

1
2
3
0x000000000040103a <+46>:    mov    $0xe,%edx
0x000000000040103f <+51>:    mov    $0x0,%esi
0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi

明顯在傳參，調用了 func4

我們先不急著看 func4，接著往下讀

1
2
3
4
0x000000000040104d <+65>:    test   %eax,%eax
0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
...
0x0000000000401058 <+76>:    callq  0x40143a <explode_bomb>

回顧一下暫存器知識，eax 在這裡是函數的返回值，這裡要求返回值等於 0

1
2
0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)
0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>

這裡要求讀取到的第二個數是 0，算是得到了半個答案

接下來我們看 func4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Dump of assembler code for function func4:
   0x0000000000400fce <+0>:     sub    $0x8,%rsp
   0x0000000000400fd2 <+4>:     mov    %edx,%eax
   0x0000000000400fd4 <+6>:     sub    %esi,%eax
   0x0000000000400fd6 <+8>:     mov    %eax,%ecx
   0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx
   0x0000000000400fdb <+13>:    add    %ecx,%eax
   0x0000000000400fdd <+15>:    sar    %eax
   0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx
   0x0000000000400fe2 <+20>:    cmp    %edi,%ecx
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36>
   0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx
   0x0000000000400fe9 <+27>:    callq  0x400fce <func4>
   0x0000000000400fee <+32>:    add    %eax,%eax
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    $0x0,%eax
   0x0000000000400ff7 <+41>:    cmp    %edi,%ecx
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>
   0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi
   0x0000000000400ffe <+48>:    callq  0x400fce <func4>
   0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax
   0x0000000000401007 <+57>:    add    $0x8,%rsp
   0x000000000040100b <+61>:    retq   
End of assembler dump.

這個代碼裡面包含遞迴，我們可以手動把這段代碼翻譯到 C 語言：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// edx = 14, esi = 0, edi = a
int func4(int edi, int esi, int edx){
    int mid = l + ((r-l)>>1);
    if(mid <= a){
        if(mid==a){
            return 0;
        }
        l = mid + 1;
        return 2*func4(a, l, r) + 1;
    }else{
        r = mid - 1;
        return 2*func4(a, l, r);
    }
}

這是二分尋找，我們很容易得到答案 a=7，於是返回 0

得到最終的答案 7 0

1
2
3
4
5
6
7
0x0000000000400fd2 <+4>:     mov    %edx,%eax
0x0000000000400fd4 <+6>:     sub    %esi,%eax
0x0000000000400fd6 <+8>:     mov    %eax,%ecx
0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx
0x0000000000400fdb <+13>:    add    %ecx,%eax
0x0000000000400fdd <+15>:    sar    %eax
0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx

這一段代碼就是在計算 mid，非常好理解，但是有個問題：shr $0x1f,%ecx 是在做什麼？

偏置

整數除法要求向零捨入。對於正數，向下捨入；對於負數，向上捨入。除以2的冪可以用右移操作替代。

但是，對於補碼右移，很可能出現捨入錯誤。

我們進行右移的時候，其實是捨去了最低位，是一種向下取整

當我們執行右移 x >> k 時：高位部分的權重全部除以了 $2^k$，變成了整數結果。低位部分（餘數）直接被丟棄了。

對於負數而言，這一操作進行了向下取整，但我們要求對負數進行向上取整。

因此，我們需要引入偏置。

於是 (x+(1<<k)-1)>>k 得到 $\lceil x/2^k \rceil$

也就是下面這兩行的含義

1
2
0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx
0x0000000000400fdb <+13>:    add    %ecx,%eax

Phase 5

我們先disas看代碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Dump of assembler code for function phase_5:
   0x0000000000401062 <+0>:     push   %rbx
   0x0000000000401063 <+1>:     sub    $0x20,%rsp
   0x0000000000401067 <+5>:     mov    %rdi,%rbx
   0x000000000040106a <+8>:     mov    %fs:0x28,%rax
   0x0000000000401073 <+17>:    mov    %rax,0x18(%rsp)
   0x0000000000401078 <+22>:    xor    %eax,%eax
   0x000000000040107a <+24>:    callq  0x40131b <string_length>
   0x000000000040107f <+29>:    cmp    $0x6,%eax
   0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>
   0x0000000000401084 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000401089 <+39>:    jmp    0x4010d2 <phase_5+112>
   0x000000000040108b <+41>:    movzbl (%rbx,%rax,1),%ecx
   0x000000000040108f <+45>:    mov    %cl,(%rsp)
   0x0000000000401092 <+48>:    mov    (%rsp),%rdx
   0x0000000000401096 <+52>:    and    $0xf,%edx
   0x0000000000401099 <+55>:    movzbl 0x4024b0(%rdx),%edx
   0x00000000004010a0 <+62>:    mov    %dl,0x10(%rsp,%rax,1)
   0x00000000004010a4 <+66>:    add    $0x1,%rax
   0x00000000004010a8 <+70>:    cmp    $0x6,%rax
   0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>
   0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)
   0x00000000004010b3 <+81>:    mov    $0x40245e,%esi
   0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi
   0x00000000004010bd <+91>:    callq  0x401338 <strings_not_equal>
   0x00000000004010c2 <+96>:    test   %eax,%eax
   0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>:   callq  0x40143a <explode_bomb>
   0x00000000004010cb <+105>:   nopl   0x0(%rax,%rax,1)
   0x00000000004010d0 <+110>:   jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>:   mov    $0x0,%eax
   0x00000000004010d7 <+117>:   jmp    0x40108b <phase_5+41>
   0x00000000004010d9 <+119>:   mov    0x18(%rsp),%rax
   0x00000000004010de <+124>:   xor    %fs:0x28,%rax
   0x00000000004010e7 <+133>:   je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>:   callq  0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>:   add    $0x20,%rsp
   0x00000000004010f2 <+144>:   pop    %rbx
   0x00000000004010f3 <+145>:   retq   
End of assembler dump.

很快識別出來，這一段代碼中有兩個記憶體地址：0x4024b0 0x40245e

讀一下：

1
2
0x4024b0 <array.3449>:  "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
0x40245e:       "flyers"

第一個 array.3449 是一個字串，我們就記為 a[]

上面的代碼可以分個段

1
2
3
4
5
6
7
8
9
10
11
0x0000000000401062 <+0>:     push   %rbx
0x0000000000401063 <+1>:     sub    $0x20,%rsp
0x0000000000401067 <+5>:     mov    %rdi,%rbx
0x000000000040106a <+8>:     mov    %fs:0x28,%rax
0x0000000000401073 <+17>:    mov    %rax,0x18(%rsp)
0x0000000000401078 <+22>:    xor    %eax,%eax
0x000000000040107a <+24>:    callq  0x40131b <string_length>
0x000000000040107f <+29>:    cmp    $0x6,%eax
0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>
0x0000000000401084 <+34>:    callq  0x40143a <explode_bomb>
0x0000000000401089 <+39>:    jmp    0x4010d2 <phase_5+112>

這裡是前面初始化的部分，我們可以看到預留了棧空間，應該是讀取了一個字串，長度為 6，存在棧上。

1
2
3
4
5
6
7
8
9
10
11
12
0x00000000004010d2 <+112>:   mov    $0x0,%eax
0x00000000004010d7 <+117>:   jmp    0x40108b <phase_5+41>
...
0x000000000040108b <+41>:    movzbl (%rbx,%rax,1),%ecx
0x000000000040108f <+45>:    mov    %cl,(%rsp)
0x0000000000401092 <+48>:    mov    (%rsp),%rdx
0x0000000000401096 <+52>:    and    $0xf,%edx
0x0000000000401099 <+55>:    movzbl 0x4024b0(%rdx),%edx
0x00000000004010a0 <+62>:    mov    %dl,0x10(%rsp,%rax,1)
0x00000000004010a4 <+66>:    add    $0x1,%rax
0x00000000004010a8 <+70>:    cmp    $0x6,%rax
0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>

以上是一個 for 循環，循環 6 次，取 edx 的後四位，這是一個 0~15 的數，記為 i，於是把 a[i] 加入棧中對應位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)
0x00000000004010b3 <+81>:    mov    $0x40245e,%esi
0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi
0x00000000004010bd <+91>:    callq  0x401338 <strings_not_equal>
0x00000000004010c2 <+96>:    test   %eax,%eax
0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
0x00000000004010c6 <+100>:   callq  0x40143a <explode_bomb>
0x00000000004010cb <+105>:   nopl   0x0(%rax,%rax,1)
0x00000000004010d0 <+110>:   jmp    0x4010d9 <phase_5+119>
...
0x00000000004010d9 <+119>:   mov    0x18(%rsp),%rax
0x00000000004010de <+124>:   xor    %fs:0x28,%rax
0x00000000004010e7 <+133>:   je     0x4010ee <phase_5+140>
0x00000000004010e9 <+135>:   callq  0x400b30 <__stack_chk_fail@plt>
0x00000000004010ee <+140>:   add    $0x20,%rsp
0x00000000004010f2 <+144>:   pop    %rbx
0x00000000004010f3 <+145>:   retq

這裡有價值的片段只有

1
2
3
4
5
6
7
8
9
0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)
0x00000000004010b3 <+81>:    mov    $0x40245e,%esi
0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi
0x00000000004010bd <+91>:    callq  0x401338 <strings_not_equal>
0x00000000004010c2 <+96>:    test   %eax,%eax
0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
0x00000000004010c6 <+100>:   callq  0x40143a <explode_bomb>
0x00000000004010cb <+105>:   nopl   0x0(%rax,%rax,1)
0x00000000004010d0 <+110>:   jmp    0x4010d9 <phase_5+119>

這是比較字串。

我們不難發現，這道題的邏輯是查表映射：程序會把輸入字元對 16 取模得到的數值作為索引，去尋找那個長字串（maduiers…）中的字元。 為了讓最終取出來的字元拼成 flyers，我們需要反向尋找 flyers 中每個字母在表中對應的下標位置，然後構造一個輸入字串，使其每一位的 ASCII 碼模 16 後正好等於這些下標。

這個過程可以總結為： Input Char -> ASCII Hex -> AND 0xF (取後4位) -> Table Index -> Lookup Table Char -> Target “flyers”

於是我們可以得到答案 ionefg 或者 IONEFG

其實還可以有一些其他答案，留給讀者去發現

Phase 6

先看代碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
0x00000000004010f4 <+0>:     push   %r14
0x00000000004010f6 <+2>:     push   %r13
0x00000000004010f8 <+4>:     push   %r12
0x00000000004010fa <+6>:     push   %rbp
0x00000000004010fb <+7>:     push   %rbx
0x00000000004010fc <+8>:     sub    $0x50,%rsp
0x0000000000401100 <+12>:    mov    %rsp,%r13
0x0000000000401103 <+15>:    mov    %rsp,%rsi
0x0000000000401106 <+18>:    callq  0x40145c <read_six_numbers>
0x000000000040110b <+23>:    mov    %rsp,%r14
0x000000000040110e <+26>:    mov    $0x0,%r12d
0x0000000000401114 <+32>:    mov    %r13,%rbp
0x0000000000401117 <+35>:    mov    0x0(%r13),%eax
0x000000000040111b <+39>:    sub    $0x1,%eax
0x000000000040111e <+42>:    cmp    $0x5,%eax
0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>
0x0000000000401123 <+47>:    callq  0x40143a <explode_bomb>
0x0000000000401128 <+52>:    add    $0x1,%r12d
0x000000000040112c <+56>:    cmp    $0x6,%r12d
0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>
0x0000000000401132 <+62>:    mov    %r12d,%ebx
0x0000000000401135 <+65>:    movslq %ebx,%rax
0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax
0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)
0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>
0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
0x0000000000401145 <+81>:    add    $0x1,%ebx
0x0000000000401148 <+84>:    cmp    $0x5,%ebx
0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>
0x000000000040114d <+89>:    add    $0x4,%r13
0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>
0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi
0x0000000000401158 <+100>:   mov    %r14,%rax
0x000000000040115b <+103>:   mov    $0x7,%ecx
0x0000000000401160 <+108>:   mov    %ecx,%edx
0x0000000000401162 <+110>:   sub    (%rax),%edx
0x0000000000401164 <+112>:   mov    %edx,(%rax)
0x0000000000401166 <+114>:   add    $0x4,%rax
0x000000000040116a <+118>:   cmp    %rsi,%rax
0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>
0x000000000040116f <+123>:   mov    $0x0,%esi
0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx
0x000000000040117a <+134>:   add    $0x1,%eax
0x000000000040117d <+137>:   cmp    %ecx,%eax
0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>
0x0000000000401183 <+143>:   mov    $0x6032d0,%edx
0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)
0x000000000040118d <+153>:   add    $0x4,%rsi
0x0000000000401191 <+157>:   cmp    $0x18,%rsi
0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183>
0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx
0x000000000040119a <+166>:   cmp    $0x1,%ecx
0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>
0x000000000040119f <+171>:   mov    $0x1,%eax
0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx
0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>
0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx
0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax
0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi
0x00000000004011ba <+198>:   mov    %rbx,%rcx
0x00000000004011bd <+201>:   mov    (%rax),%rdx
0x00000000004011c0 <+204>:   mov    %rdx,0x8(%rcx)
0x00000000004011c4 <+208>:   add    $0x8,%rax
0x00000000004011c8 <+212>:   cmp    %rsi,%rax
0x00000000004011cb <+215>:   je     0x4011d2 <phase_6+222>
0x00000000004011cd <+217>:   mov    %rdx,%rcx
0x00000000004011d0 <+220>:   jmp    0x4011bd <phase_6+201>
0x00000000004011d2 <+222>:   movq   $0x0,0x8(%rdx)
0x00000000004011da <+230>:   mov    $0x5,%ebp
0x00000000004011df <+235>:   mov    0x8(%rbx),%rax
0x00000000004011e3 <+239>:   mov    (%rax),%eax
0x00000000004011e5 <+241>:   cmp    %eax,(%rbx)
0x00000000004011e7 <+243>:   jge    0x4011ee <phase_6+250>
0x00000000004011e9 <+245>:   callq  0x40143a <explode_bomb>
0x00000000004011ee <+250>:   mov    0x8(%rbx),%rbx
0x00000000004011f2 <+254>:   sub    $0x1,%ebp
0x00000000004011f5 <+257>:   jne    0x4011df <phase_6+235>
0x00000000004011f7 <+259>:   add    $0x50,%rsp
0x00000000004011fb <+263>:   pop    %rbx
0x00000000004011fc <+264>:   pop    %rbp
0x00000000004011fd <+265>:   pop    %r12
0x00000000004011ff <+267>:   pop    %r13
0x0000000000401201 <+269>:   pop    %r14
0x0000000000401203 <+271>:   retq

分開來看：

1
2
3
4
5
6
7
8
0x00000000004010f4 <+0>:     push   %r14
0x00000000004010f6 <+2>:     push   %r13
0x00000000004010f8 <+4>:     push   %r12
0x00000000004010fa <+6>:     push   %rbp
0x00000000004010fb <+7>:     push   %rbx
0x00000000004010fc <+8>:     sub    $0x50,%rsp
0x0000000000401100 <+12>:    mov    %rsp,%r13
0x0000000000401103 <+15>:    mov    %rsp,%rsi

這一段是設置棧幀

1
0x0000000000401106 <+18>:    callq  0x40145c <read_six_numbers>

這裡讀了 6 個數字，我們在 Phase 2 已經看到，這六個數字存在從 rsp 開始的一個數組中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
0x000000000040110b <+23>:    mov    %rsp,%r14
0x000000000040110e <+26>:    mov    $0x0,%r12d
0x0000000000401114 <+32>:    mov    %r13,%rbp
0x0000000000401117 <+35>:    mov    0x0(%r13),%eax
0x000000000040111b <+39>:    sub    $0x1,%eax
0x000000000040111e <+42>:    cmp    $0x5,%eax
0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>
0x0000000000401123 <+47>:    callq  0x40143a <explode_bomb>
0x0000000000401128 <+52>:    add    $0x1,%r12d
0x000000000040112c <+56>:    cmp    $0x6,%r12d
0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>
0x0000000000401132 <+62>:    mov    %r12d,%ebx
0x0000000000401135 <+65>:    movslq %ebx,%rax
0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax
0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)
0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>
0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
0x0000000000401145 <+81>:    add    $0x1,%ebx
0x0000000000401148 <+84>:    cmp    $0x5,%ebx
0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>
0x000000000040114d <+89>:    add    $0x4,%r13
0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>

此處代碼構建了一個典型的嵌套循環結構：外層循環由 %r12d 計數，內層循環則由 %ebx 控制。

1
2
3
4
5
6
0x0000000000401117 <+35>:    mov    0x0(%r13),%eax
0x000000000040111b <+39>:    sub    $0x1,%eax
0x000000000040111e <+42>:    cmp    $0x5,%eax
...
0x000000000040114d <+89>:    add    $0x4,%r13
0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>

首先分析外層循環：它通過 %r13 指針遍歷輸入數組，首要任務是進行邊界檢查，確保讀取到的每一個數字都小於或等於 6。

再來看內層循環：

1
2
3
4
5
6
7
8
9
0x0000000000401132 <+62>:    mov    %r12d,%ebx
0x0000000000401135 <+65>:    movslq %ebx,%rax
0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax
0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)
0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>
0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
0x0000000000401145 <+81>:    add    $0x1,%ebx
0x0000000000401148 <+84>:    cmp    $0x5,%ebx
0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>

這裡從當前外層數字開始，判斷數組之後的每一個數位（int 類型，4 位元組，故 (%rsp,%rax,4) 獲得當前數字），判斷這個數字是否和外層數字相同。

於是，我們發現，這一層循環判斷輸入的每個數字是否互不相同。

總結一下，這個嵌套循環檢查我們的輸入是否是六個互不相同的小於等於 6 的數字

1
2
3
4
5
6
7
8
9
0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi
0x0000000000401158 <+100>:   mov    %r14,%rax
0x000000000040115b <+103>:   mov    $0x7,%ecx
0x0000000000401160 <+108>:   mov    %ecx,%edx
0x0000000000401162 <+110>:   sub    (%rax),%edx
0x0000000000401164 <+112>:   mov    %edx,(%rax)
0x0000000000401166 <+114>:   add    $0x4,%rax
0x000000000040116a <+118>:   cmp    %rsi,%rax
0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>

這裡又有一個循環。前文已知，r14 就是 rsp，也就是棧指針。這裡遍歷每一個數 x，重新賦值，x = 7-x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
0x000000000040116f <+123>:   mov    $0x0,%esi
0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx
0x000000000040117a <+134>:   add    $0x1,%eax
0x000000000040117d <+137>:   cmp    %ecx,%eax
0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>
0x0000000000401183 <+143>:   mov    $0x6032d0,%edx
0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)
0x000000000040118d <+153>:   add    $0x4,%rsi
0x0000000000401191 <+157>:   cmp    $0x18,%rsi
0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183>
0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx
0x000000000040119a <+166>:   cmp    $0x1,%ecx
0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>
0x000000000040119f <+171>:   mov    $0x1,%eax
0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx
0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>

先讀取輸入的元素 x，如果小於等於 1，把 edx 賦值為 0x6032d0，然後把 x 放在一個臨時數組中，然後繼續到下一個元素，直到遍歷完整個數組 (0x18 = 24 = 4*6)

如果元素 x 大於 1，把 eax 賦值為 1，edx 賦值為 0x6032d0，之後執行 x-1 次 mov 0x8(%rdx),%rdx 操作

這裡疑似是鍊表，出現了記憶體地址 0x6032d0，我們來看看：

1
2
3
4
5
6
7
(gdb) x/12xg 0x6032d0
0x6032d0 <node1>:       0x000000010000014c      0x00000000006032e0
0x6032e0 <node2>:       0x00000002000000a8      0x00000000006032f0
0x6032f0 <node3>:       0x000000030000039c      0x0000000000603300
0x603300 <node4>:       0x00000004000002b3      0x0000000000603310
0x603310 <node5>:       0x00000005000001dd      0x0000000000603320
0x603320 <node6>:       0x00000006000001bb      0x0000000000000000

這裡注意，在 64 位系統中，指針占用 8 位元組（即 64 位）。

顯然是鍊表，0x8(%rdx) 代表 next 指針

故上述操作得到一個數組，設輸入數組的第 i 個數為 x，數組中第 i 個數對應鍊表中第 x 個數的地址。

1
2
3
0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx
0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax
0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi

這裡是一些初始化。rsi 是邊界指針，標記循環的終止。0x20 到 0x50 正好 6*8=48

1
2
3
4
5
6
7
8
0x00000000004011ba <+198>:   mov    %rbx,%rcx
0x00000000004011bd <+201>:   mov    (%rax),%rdx
0x00000000004011c0 <+204>:   mov    %rdx,0x8(%rcx)
0x00000000004011c4 <+208>:   add    $0x8,%rax
0x00000000004011c8 <+212>:   cmp    %rsi,%rax
0x00000000004011cb <+215>:   je     0x4011d2 <phase_6+222>
0x00000000004011cd <+217>:   mov    %rdx,%rcx
0x00000000004011d0 <+220>:   jmp    0x4011bd <phase_6+201>

這裡遍歷了我們剛才得到的鍊表地址數組。寫成 C 語言或許更好理解。

1
2
3
4
5
6
7
8
9
Node *current = node_ptrs[0]; // %rbx, %rcx 初始化
int i = 1; // 對應 %rax 指向 node_ptrs[1]

while (i < 6) {
    Node *next_node = node_ptrs[i]; // mov (%rax), %rdx
    current->next = next_node;      // mov %rdx, 0x8(%rcx)
    current = next_node;            // mov %rdx, %rcx
    i++;                            // add $0x8, %rax
}

這一個循環對於鍊表結構進行了修改。

1
0x00000000004011d2 <+222>:   movq   $0x0,0x8(%rdx)

這句話則把最後一個節點的 next 賦值為 NULL，確保鍊表結構

接下來又有一個循環：

1
2
3
4
5
6
7
8
9
0x00000000004011da <+230>:   mov    $0x5,%ebp
0x00000000004011df <+235>:   mov    0x8(%rbx),%rax
0x00000000004011e3 <+239>:   mov    (%rax),%eax
0x00000000004011e5 <+241>:   cmp    %eax,(%rbx)
0x00000000004011e7 <+243>:   jge    0x4011ee <phase_6+250>
0x00000000004011e9 <+245>:   callq  0x40143a <explode_bomb>
0x00000000004011ee <+250>:   mov    0x8(%rbx),%rbx
0x00000000004011f2 <+254>:   sub    $0x1,%ebp
0x00000000004011f5 <+257>:   jne    0x4011df <phase_6+235>

遍歷鍊表，確保鍊表倒序排列。

看到這裡，我們就可以得到答案了：

1
2
3
4
5
6
7
(gdb) x/12xg 0x6032d0
0x6032d0 <node1>:       0x000000010000014c      0x00000000006032e0
0x6032e0 <node2>:       0x00000002000000a8      0x00000000006032f0
0x6032f0 <node3>:       0x000000030000039c      0x0000000000603300
0x603300 <node4>:       0x00000004000002b3      0x0000000000603310
0x603310 <node5>:       0x00000005000001dd      0x0000000000603320
0x603320 <node6>:       0x00000006000001bb      0x0000000000000000

找到鍊表值的倒序索引即可，注意值是 int 類型，只取後四位。於是可以得到 3 4 5 6 1 2

但我們還要注意，輸入進行過 7-x 操作（見上文），所以我們調整答案 4 3 2 1 6 5

最後一個 Phase 有點複雜，巧妙融合了嵌套循環校驗、數組映射變換以及鍊表重組等多種技術。

隱藏關

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* Hmm...  Six phases must be more secure than one phase! */
input = read_line();             /* Get input                   */
phase_1(input);                  /* Run the phase               */
phase_defused();                 /* Drat!  They figured it out!
      * Let me know how they did it. */
printf("Phase 1 defused. How about the next one?\n");

/* The second phase is harder.  No one will ever figure out
 * how to defuse this... */
input = read_line();
phase_2(input);
phase_defused();
printf("That's number 2.  Keep going!\n");

/* I guess this is too easy so far.  Some more complex code will
 * confuse people. */
input = read_line();
phase_3(input);
phase_defused();
printf("Halfway there!\n");

/* Oh yeah?  Well, how good is your math?  Try on this saucy problem! */
input = read_line();
phase_4(input);
phase_defused();
printf("So you got that one.  Try this one.\n");

/* Round and 'round in memory we go, where we stop, the bomb blows! */
input = read_line();
phase_5(input);
phase_defused();
printf("Good work!  On to the next...\n");

/* This phase will never be used, since no one will get past the
 * earlier ones.  But just in case, make this one extra hard. */
input = read_line();
phase_6(input);
phase_defused();

bomb 代碼中，每一個 phase 後都運行 phase_defused。我們來看看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Dump of assembler code for function phase_defused:
   0x00000000004015c4 <+0>:     sub    $0x78,%rsp
   0x00000000004015c8 <+4>:     mov    %fs:0x28,%rax
   0x00000000004015d1 <+13>:    mov    %rax,0x68(%rsp)
   0x00000000004015d6 <+18>:    xor    %eax,%eax
   0x00000000004015d8 <+20>:    cmpl   $0x6,0x202181(%rip)        # 0x603760 <num_input_strings>
   0x00000000004015df <+27>:    jne    0x40163f <phase_defused+123>
   0x00000000004015e1 <+29>:    lea    0x10(%rsp),%r8
   0x00000000004015e6 <+34>:    lea    0xc(%rsp),%rcx
   0x00000000004015eb <+39>:    lea    0x8(%rsp),%rdx
   0x00000000004015f0 <+44>:    mov    $0x402619,%esi
   0x00000000004015f5 <+49>:    mov    $0x603870,%edi
   0x00000000004015fa <+54>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x00000000004015ff <+59>:    cmp    $0x3,%eax
   0x0000000000401602 <+62>:    jne    0x401635 <phase_defused+113>
   0x0000000000401604 <+64>:    mov    $0x402622,%esi
   0x0000000000401609 <+69>:    lea    0x10(%rsp),%rdi
   0x000000000040160e <+74>:    callq  0x401338 <strings_not_equal>
   0x0000000000401613 <+79>:    test   %eax,%eax
   0x0000000000401615 <+81>:    jne    0x401635 <phase_defused+113>
   0x0000000000401617 <+83>:    mov    $0x4024f8,%edi
   0x000000000040161c <+88>:    callq  0x400b10 <puts@plt>
   0x0000000000401621 <+93>:    mov    $0x402520,%edi
   0x0000000000401626 <+98>:    callq  0x400b10 <puts@plt>
   0x000000000040162b <+103>:   mov    $0x0,%eax
   0x0000000000401630 <+108>:   callq  0x401242 <secret_phase>
   0x0000000000401635 <+113>:   mov    $0x402558,%edi
   0x000000000040163a <+118>:   callq  0x400b10 <puts@plt>
   0x000000000040163f <+123>:   mov    0x68(%rsp),%rax
   0x0000000000401644 <+128>:   xor    %fs:0x28,%rax
   0x000000000040164d <+137>:   je     0x401654 <phase_defused+144>
   0x000000000040164f <+139>:   callq  0x400b30 <__stack_chk_fail@plt>
   0x0000000000401654 <+144>:   add    $0x78,%rsp
   0x0000000000401658 <+148>:   retq   
1
0x00000000004015d8 <+20>:    cmpl   $0x6,0x202181(%rip)        # 0x603760 <num_input_strings>

這裡要求六關全部通過之後才能進入 secret_phase

我們可以設置條件斷點：b phase_defused if num_input_strings == 6

注意到：

1
0x0000000000401630 <+108>:   callq  0x401242 <secret_phase>

這裡有非常多的記憶體地址，其中：

1
2
3
4
5
6
(gdb) x/s 0x402619
0x402619:       "%d %d %s"
(gdb) x/s 0x603870
0x603870 <input_strings+240>:   "7 0"
(gdb) x/s 0x402622
0x402622:       "DrEvil"

判斷 Phase 4 輸入之後是否有一個字串 DrEvil，如果有，進入隱藏關！

再來看看隱藏關的代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Dump of assembler code for function secret_phase:
   0x0000000000401242 <+0>:     push   %rbx
   0x0000000000401243 <+1>:     callq  0x40149e <read_line>
   0x0000000000401248 <+6>:     mov    $0xa,%edx
   0x000000000040124d <+11>:    mov    $0x0,%esi
   0x0000000000401252 <+16>:    mov    %rax,%rdi
   0x0000000000401255 <+19>:    callq  0x400bd0 <strtol@plt>
   0x000000000040125a <+24>:    mov    %rax,%rbx
   0x000000000040125d <+27>:    lea    -0x1(%rax),%eax
   0x0000000000401260 <+30>:    cmp    $0x3e8,%eax
   0x0000000000401265 <+35>:    jbe    0x40126c <secret_phase+42>
   0x0000000000401267 <+37>:    callq  0x40143a <explode_bomb>
   0x000000000040126c <+42>:    mov    %ebx,%esi
   0x000000000040126e <+44>:    mov    $0x6030f0,%edi
   0x0000000000401273 <+49>:    callq  0x401204 <fun7>
   0x0000000000401278 <+54>:    cmp    $0x2,%eax
   0x000000000040127b <+57>:    je     0x401282 <secret_phase+64>
   0x000000000040127d <+59>:    callq  0x40143a <explode_bomb>
   0x0000000000401282 <+64>:    mov    $0x402438,%edi
   0x0000000000401287 <+69>:    callq  0x400b10 <puts@plt>
   0x000000000040128c <+74>:    callq  0x4015c4 <phase_defused>
   0x0000000000401291 <+79>:    pop    %rbx
   0x0000000000401292 <+80>:    retq   
End of assembler dump.

看到 strtol，知道這裡讀入了一個整數

1
2
3
4
5
0x000000000040125a <+24>:    mov    %rax,%rbx
0x000000000040125d <+27>:    lea    -0x1(%rax),%eax
0x0000000000401260 <+30>:    cmp    $0x3e8,%eax
0x0000000000401265 <+35>:    jbe    0x40126c <secret_phase+42>
0x0000000000401267 <+37>:    callq  0x40143a <explode_bomb>

要求讀取的整數小於等於 1001。注意 jbe 是無符號數的跳轉檢查，所以這裡其實也隱性限制了下限。所以嚴格的輸入限制是 [1, 1001] 之間的整數。

1
2
3
0x000000000040126c <+42>:    mov    %ebx,%esi
0x000000000040126e <+44>:    mov    $0x6030f0,%edi
0x0000000000401273 <+49>:    callq  0x401204 <fun7>

傳參，進入 fun7

1
2
3
4
0x0000000000401278 <+54>:    cmp    $0x2,%eax
0x000000000040127b <+57>:    je     0x401282 <secret_phase+64>
0x000000000040127d <+59>:    callq  0x40143a <explode_bomb>
0x0000000000401282 <+64>:    mov    $0x402438,%edi

這裡要求 fun7 的返回值等於 2

接下來我們看看 fun7，手動分個段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Dump of assembler code for function fun7:
   0x0000000000401204 <+0>:     sub    $0x8,%rsp
   0x0000000000401208 <+4>:     test   %rdi,%rdi
   0x000000000040120b <+7>:     je     0x401238 <fun7+52>
   
   0x000000000040120d <+9>:     mov    (%rdi),%edx
   0x000000000040120f <+11>:    cmp    %esi,%edx
   0x0000000000401211 <+13>:    jle    0x401220 <fun7+28>
   
   0x0000000000401213 <+15>:    mov    0x8(%rdi),%rdi
   0x0000000000401217 <+19>:    callq  0x401204 <fun7>
   0x000000000040121c <+24>:    add    %eax,%eax
   0x000000000040121e <+26>:    jmp    0x40123d <fun7+57>
   
   0x0000000000401220 <+28>:    mov    $0x0,%eax
   0x0000000000401225 <+33>:    cmp    %esi,%edx
   0x0000000000401227 <+35>:    je     0x40123d <fun7+57>
   0x0000000000401229 <+37>:    mov    0x10(%rdi),%rdi
   0x000000000040122d <+41>:    callq  0x401204 <fun7>
   0x0000000000401232 <+46>:    lea    0x1(%rax,%rax,1),%eax
   0x0000000000401236 <+50>:    jmp    0x40123d <fun7+57>
   
   0x0000000000401238 <+52>:    mov    $0xffffffff,%eax
   
   0x000000000040123d <+57>:    add    $0x8,%rsp
   0x0000000000401241 <+61>:    retq   
End of assembler dump.

遍歷當前 rdi 之後的兩個指針，遞迴，有點像二叉樹。我們來看看初始參數：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(gdb) x/60xg 0x6030f0
0x6030f0 <n1>:  0x0000000000000024      0x0000000000603110
0x603100 <n1+16>:       0x0000000000603130      0x0000000000000000
0x603110 <n21>: 0x0000000000000008      0x0000000000603190
0x603120 <n21+16>:      0x0000000000603150      0x0000000000000000
0x603130 <n22>: 0x0000000000000032      0x0000000000603170
0x603140 <n22+16>:      0x00000000006031b0      0x0000000000000000
0x603150 <n32>: 0x0000000000000016      0x0000000000603270
0x603160 <n32+16>:      0x0000000000603230      0x0000000000000000
0x603170 <n33>: 0x000000000000002d      0x00000000006031d0
0x603180 <n33+16>:      0x0000000000603290      0x0000000000000000
0x603190 <n31>: 0x0000000000000006      0x00000000006031f0
0x6031a0 <n31+16>:      0x0000000000603250      0x0000000000000000
0x6031b0 <n34>: 0x000000000000006b      0x0000000000603210
0x6031c0 <n34+16>:      0x00000000006032b0      0x0000000000000000
0x6031d0 <n45>: 0x0000000000000028      0x0000000000000000
0x6031e0 <n45+16>:      0x0000000000000000      0x0000000000000000
0x6031f0 <n41>: 0x0000000000000001      0x0000000000000000
0x603200 <n41+16>:      0x0000000000000000      0x0000000000000000
0x603210 <n47>: 0x0000000000000063      0x0000000000000000
0x603220 <n47+16>:      0x0000000000000000      0x0000000000000000
0x603230 <n44>: 0x0000000000000023      0x0000000000000000
0x603240 <n44+16>:      0x0000000000000000      0x0000000000000000
0x603250 <n42>: 0x0000000000000007      0x0000000000000000
0x603260 <n42+16>:      0x0000000000000000      0x0000000000000000
0x603270 <n43>: 0x0000000000000014      0x0000000000000000
0x603280 <n43+16>:      0x0000000000000000      0x0000000000000000
0x603290 <n46>: 0x000000000000002f      0x0000000000000000
0x6032a0 <n46+16>:      0x0000000000000000      0x0000000000000000
0x6032b0 <n48>: 0x00000000000003e9      0x0000000000000000
0x6032c0 <n48+16>:      0x0000000000000000      0x0000000000000000

確實是一顆二叉樹！（這裡的 60 是我試出來的）

fun7 傳入的參數為 rdi 和 esi

1
2
3
4
5
6
0x0000000000401208 <+4>:     test   %rdi,%rdi
0x000000000040120b <+7>:     je     0x401238 <fun7+52>
...
0x0000000000401238 <+52>:    mov    $0xffffffff,%eax
0x000000000040123d <+57>:    add    $0x8,%rsp
0x0000000000401241 <+61>:    retq

如果遍歷到葉子結點，直接返回 0xffffffff。

1
2
3
0x000000000040120d <+9>:     mov    (%rdi),%edx
0x000000000040120f <+11>:    cmp    %esi,%edx
0x0000000000401211 <+13>:    jle    0x401220 <fun7+28>

查看當前節點的值，如果值大於 esi：

1
2
3
4
5
6
7
0x0000000000401213 <+15>:    mov    0x8(%rdi),%rdi
0x0000000000401217 <+19>:    callq  0x401204 <fun7>
0x000000000040121c <+24>:    add    %eax,%eax
0x000000000040121e <+26>:    jmp    0x40123d <fun7+57>
...
0x000000000040123d <+57>:    add    $0x8,%rsp
0x0000000000401241 <+61>:    retq

訪問左子節點，返回值乘以二

如果當前節點的值和 rsi 相等：

1
2
3
4
5
6
0x0000000000401220 <+28>:    mov    $0x0,%eax
0x0000000000401225 <+33>:    cmp    %esi,%edx
0x0000000000401227 <+35>:    je     0x40123d <fun7+57>
...
0x000000000040123d <+57>:    add    $0x8,%rsp
0x0000000000401241 <+61>:    retq

直接返回

否則，訪問右子節點：

1
2
3
4
5
6
7
0x0000000000401229 <+37>:    mov    0x10(%rdi),%rdi
0x000000000040122d <+41>:    callq  0x401204 <fun7>
0x0000000000401232 <+46>:    lea    0x1(%rax,%rax,1),%eax
0x0000000000401236 <+50>:    jmp    0x40123d <fun7+57>
...
0x000000000040123d <+57>:    add    $0x8,%rsp
0x0000000000401241 <+61>:    retq

返回值乘以二再加一

我們可以用 C 語言翻譯上述代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
long fun7(struct Node *node, int target_val) {
    // 1. 如果節點為空
    if (node == NULL) {
        return -1; // 對應匯編中的 mov $0xffffffff, %eax
    }

    int current_val = node->value; // mov (%rdi), %edx

    // 2. 如果當前節點值 > 目標值 (target_val < current_val)
    // 匯編邏輯：cmp %esi, %edx -> jle (跳過) -> 否則執行這裡
    if (current_val > target_val) {
        // 遞迴調用左子節點 (偏移量 0x8)
        // 對應 callq fun7, 然後 add %eax, %eax
        return 2 * fun7(node->left, target_val);
    }
    
    // 3. 如果當前節點值 == 目標值
    // 匯編邏輯：cmp %esi, %edx -> je (跳轉到返回0)
    if (current_val == target_val) {
        return 0; // 找到目標，返回 0
    }

    // 4. 如果當前節點值 < 目標值
    // 匯編邏輯：此時只剩下這種情況
    // 遞迴調用右子節點 (偏移量 0x10)
    // 對應 callq fun7, 然後 lea 0x1(%rax,%rax,1) -> 2*rax + 1
    return 2 * fun7(node->right, target_val) + 1;
}

我們再來看看二叉樹的結構，根據：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(gdb) x/60xg 0x6030f0
0x6030f0 <n1>:  0x0000000000000024      0x0000000000603110
0x603100 <n1+16>:       0x0000000000603130      0x0000000000000000
0x603110 <n21>: 0x0000000000000008      0x0000000000603190
0x603120 <n21+16>:      0x0000000000603150      0x0000000000000000
0x603130 <n22>: 0x0000000000000032      0x0000000000603170
0x603140 <n22+16>:      0x00000000006031b0      0x0000000000000000
0x603150 <n32>: 0x0000000000000016      0x0000000000603270
0x603160 <n32+16>:      0x0000000000603230      0x0000000000000000
0x603170 <n33>: 0x000000000000002d      0x00000000006031d0
0x603180 <n33+16>:      0x0000000000603290      0x0000000000000000
0x603190 <n31>: 0x0000000000000006      0x00000000006031f0
0x6031a0 <n31+16>:      0x0000000000603250      0x0000000000000000
0x6031b0 <n34>: 0x000000000000006b      0x0000000000603210
0x6031c0 <n34+16>:      0x00000000006032b0      0x0000000000000000
0x6031d0 <n45>: 0x0000000000000028      0x0000000000000000
0x6031e0 <n45+16>:      0x0000000000000000      0x0000000000000000
0x6031f0 <n41>: 0x0000000000000001      0x0000000000000000
0x603200 <n41+16>:      0x0000000000000000      0x0000000000000000
0x603210 <n47>: 0x0000000000000063      0x0000000000000000
0x603220 <n47+16>:      0x0000000000000000      0x0000000000000000
0x603230 <n44>: 0x0000000000000023      0x0000000000000000
0x603240 <n44+16>:      0x0000000000000000      0x0000000000000000
0x603250 <n42>: 0x0000000000000007      0x0000000000000000
0x603260 <n42+16>:      0x0000000000000000      0x0000000000000000
0x603270 <n43>: 0x0000000000000014      0x0000000000000000
0x603280 <n43+16>:      0x0000000000000000      0x0000000000000000
0x603290 <n46>: 0x000000000000002f      0x0000000000000000
0x6032a0 <n46+16>:      0x0000000000000000      0x0000000000000000
0x6032b0 <n48>: 0x00000000000003e9      0x0000000000000000
0x6032c0 <n48+16>:      0x0000000000000000      0x0000000000000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
graph TD
    N1((36)) --> N21((8))
    N1 --> N22((50))

    N21 --> N31((6))
    N21 --> N32((22))

    N22 --> N33((45))
    N22 --> N34((107))

    N31 --> N41((1))
    N31 --> N42((7))

    N32 --> N43((20))
    N32 --> N44((35))

    N33 --> N45((40))
    N33 --> N46((47))

    N34 --> N47((99))
    N34 --> N48((1001))

要求最終輸出為 2，2 = 1*2

先向左，再向右，然後找到了答案。

於是，我們得到答案 22

總結

於是，最終答案是：

1
2
3
4
5
6
7
Border relations with Canada have never been better.
1 2 4 8 16 32
0 207
7 0 DrEvil
ionefg
4 3 2 1 6 5
22

最後讓 AI 生成一段小結

CSAPP Bomb Lab 是一個非常經典的實驗，它不僅是一次對匯編語言 (x86-64) 的深度練習，更是一場邏輯推理的解謎遊戲。

回顧整個拆彈過程，我們經歷了從簡單到複雜的演進：

  1. 基礎控制流：從 Phase 1 的字串比較，到 Phase 2 的循環與棧上數組操作。
  2. 高級控制流：Phase 3 展示了 switch 語句如何通過跳轉表實現，Phase 4 則通過遞迴讓我們深入理解了棧幀的生長與銷毀以及二分尋找算法。
  3. 數據操縱：Phase 5 的位運算與字元數組索引映射，考察了對指針和記憶體定址的敏感度。
  4. 數據結構：Phase 6 的鍊表重排以及隱藏關卡的二叉搜索樹（BST），讓我們看到了高級數據結構在匯編層面的具體形態（指針即地址）。

在這個過程中，gdb 是最強大的武器。熟練掌握斷點設置、暫存器查看 (i r) 和記憶體檢查 (x/) 是通關的關鍵。同時，我們也深刻體會到了編譯器最佳化的“智慧”（如利用 lea 進行算術運算、利用無符號數比較合併上下界檢查）和 C 語言與機器碼之間的映射關係。

當看到終端最終列印出 “Congratulations! You’ve defused the bomb!” 時，所有的查表、計算和堆棧分析都是值得的。希望這篇解析能對你理解計算機底層系統有所幫助。 Happy Hacking!