# CS:APP Bomb Lab 解題筆記
###### tags: `cs:app`
Bomb Lab 對應第三章『程序的機器級表示』，提供已編譯的二進制文件 `bomb`，執行時會要求使用者輸入六個字串，只要其中一個內容有錯誤，炸彈就會爆。我們必需透過 `gdb` 等除錯工具，進行反編譯及逆向工程，找出正確的六個字串拆除炸彈
## Phase_1
以 `gdb` 開啟 `bomb` ，隨意輸入字串 (我實驗時使用 `abcd`)。我們先透過 `disas` 反編譯觀察 `phase_1` 函式的機器語言表示，該函式呼叫了 `strings_not_equal` 並測試該函數的回傳值，若符合條件則通過 `phase_1`，反之則觸發 `explode_bomb`。
另外，透過命令 `print (char *) 0x402400` 發現該記憶體位置儲存的內容為字串 `Border relations with Canada have never been better.`
```cpp
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
```
1. 進到 `strings_not_equal`，該函式呼叫了兩次 `string_length`，且分別帶入不同的參數
2. 觀察暫存器 `%rdi` & `%rsi` 的值，發現為 `abcd`(輸入) & `Border relations with Canada have never been better.`
3. 我們再觀察儲存兩次函式呼叫回傳值的寄存器 `%r12d` & `%rax`，推測 `string_length` 應該是用來計算字串長度
```cpp
(gdb) print (int*)$eax
$26 = (int *) 0x34
(gdb) print (int*)$r12d
$27 = (int *) 0x4
```
4. 若 3. 的兩個數字不相等，則回傳 `1` 觸發炸彈，否則進入 `40135f ~ 40137f` 逐字比較兩字串的內容，若有不相等的情況則回傳 `1`，若全部相等則回傳 `0`，其實從這邊就可以猜到答案是 `0x402400` 中儲存的字串
```cpp
strings_not_equal
0x0000000000401338 <+0>: push %r12
0x000000000040133a <+2>: push %rbp
0x000000000040133b <+3>: push %rbx
0x000000000040133c <+4>: mov %rdi,%rbx
0x000000000040133f <+7>: mov %rsi,%rbp
0x0000000000401342 <+10>: callq 0x40131b <string_length>
0x0000000000401347 <+15>: mov %eax,%r12d
0x000000000040134a <+18>: mov %rbp,%rdi
0x000000000040134d <+21>: callq 0x40131b <string_length>
0x0000000000401352 <+26>: mov $0x1,%edx
0x0000000000401357 <+31>: cmp %eax,%r12d
0x000000000040135a <+34>: jne 0x40139b <strings_not_equal+99>
0x000000000040135c <+36>: movzbl (%rbx),%eax
0x000000000040135f <+39>: test %al,%al
0x0000000000401361 <+41>: je 0x401388 <strings_not_equal+80>
0x0000000000401363 <+43>: cmp 0x0(%rbp),%al
0x0000000000401366 <+46>: je 0x401372 <strings_not_equal+58>
0x0000000000401368 <+48>: jmp 0x40138f <strings_not_equal+87>
0x000000000040136a <+50>: cmp 0x0(%rbp),%al
0x000000000040136d <+53>: nopl (%rax)
0x0000000000401370 <+56>: jne 0x401396 <strings_not_equal+94>
0x0000000000401372 <+58>: add $0x1,%rbx
0x0000000000401376 <+62>: add $0x1,%rbp
0x000000000040137a <+66>: movzbl (%rbx),%eax
0x000000000040137d <+69>: test %al,%al
0x000000000040137f <+71>: jne 0x40136a <strings_not_equal+50>
0x0000000000401381 <+73>: mov $0x0,%edx
0x0000000000401386 <+78>: jmp 0x40139b <strings_not_equal+99>
0x0000000000401388 <+80>: mov $0x0,%edx
0x000000000040138d <+85>: jmp 0x40139b <strings_not_equal+99>
0x000000000040138f <+87>: mov $0x1,%edx
0x0000000000401394 <+92>: jmp 0x40139b <strings_not_equal+99>
0x0000000000401396 <+94>: mov $0x1,%edx
0x000000000040139b <+99>: mov %edx,%eax
0x000000000040139d <+101>: pop %rbx
0x000000000040139e <+102>: pop %rbp
0x000000000040139f <+103>: pop %r12
0x00000000004013a1 <+105>: retq
```
觀察 `string_length` ，函數不斷地迭代將字串的指標及計數器 `+1`，直到遇到 `\0`，所以其功用確實是計算字串長度
```cpp
string_length
0x000000000040131b <+0>: cmpb $0x0,(%rdi)
0x000000000040131e <+3>: je 0x401332 <string_length+23>
0x0000000000401320 <+5>: mov %rdi,%rdx
0x0000000000401323 <+8>: add $0x1,%rdx
0x0000000000401327 <+12>: mov %edx,%eax
0x0000000000401329 <+14>: sub %edi,%eax
0x000000000040132b <+16>: cmpb $0x0,(%rdx)
0x000000000040132e <+19>: jne 0x401323 <string_length+8>
0x0000000000401330 <+21>: repz retq
0x0000000000401332 <+23>: mov $0x0,%eax
0x0000000000401337 <+28>: retq
```
## Phase_2
1. 程式進入 `read_six_numbers` 中讀取 6 個數字，並將結果存在 stack 中
2. 讀取後跳到`400f30`，將存放數字的低位及高位 Stack 地址存在暫存器 `%rbx` & `%rbp` 中
3. 觀察 `400f17 ~ 400f2e`，將整數從低 4 位取出後乘上 2，再與高 4 位比較是否相同，並比較 5 次(`(%rbp - %rbx)/4`)，每一次移動 4 個 byte，代表==輸入的數字應該為等比級數，乘冪為 2==
5. 最後看到 `400f0a` ，程式比較 stack 最低位的數字是否等於 `1`，由此可推斷答案為 ==`1 2 4 8 16 32`==
```cpp
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
```
觀察 `read_six_numbers` 的機器級表示
1. 將記憶體位置 `0x4025c3` 的字串印出，推測應該是 `scanf` 的 format，所以我們的輸入應該為 `N1 N2 N3 N4 N5 N6`
```cpp
print (char*) 0x4025c3 = "%d %d %d %d %d %d"
```
經測試發現無論輸入多少數字，編譯器為指標配置的空間總是 `0x18`，代表 `scanf` 固定接收 6 個整數型態的指標，參考 Linux Programmer's Manual，若指標數量少於 format 要求，屬於未定義行為
3. 如果仔細觀察 `phase_2` & `read_six_numbers` 的程式碼，其實輸入可以高於 6 個數字，超過的部份將被忽略，以下節自 Linux Programmer's Manual
>If the number of conversion specifications in format exceeds the number of pointer arguments, the results are undefined. If the number of pointer arguments exceeds the number of conversion specifications, then the excess pointer arguments are evaluated, but are otherwise ignored.
```cpp
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
```
## Phase_3
這題的解法與 `phase_2` 雷同，我們先從記憶體位置 `0x4025cf` 觀察 `scanf` 的輸入格式
```cpp
(gdb) print (char* ) 0x4025cf
$1 = 0x4025cf "%d %d"
```
由以下兩行知道變數將儲存於 stack `%rsp+8 & %rsp+12`
```cpp
0x0000000000400f47 <+4>: lea 0xc(%rsp),%rcx
0x0000000000400f4c <+9>: lea 0x8(%rsp),%rdx
```
利用 `scanf` 取得兩個數字後，程式先比對第一個數字是否大於 7，若大於 7 則觸發炸彈
```cpp
0x0000000000400f6a <+39>: cmpl $0x7,0x8(%rsp)
0x0000000000400f6f <+44>: ja 0x400fad <phase_3+106>
...
0x0000000000400fad <+106>: callq 0x40143a <explode_bomb>
```
接著程式會從記憶體位置 `0x402470 + 8 x %rax` 取址並跳轉到該地址，我們假設 %rax 的值為 `0~8` 取址觀察，==發現 `0~7` 都有對應 `phase_3` 的程式計數器==，將一個特定數值存入 %rax
```cpp
0x0000000000400f75 <+50>: jmpq *0x402470(,%rax,8)
(gdb) print /x *0x402470
$11 = 0x400f7c
(gdb) print /x *0x402478
$12 = 0x400fb9
(gdb) print /x *0x402480
$13 = 0x400f83
(gdb) print /x *0x402488
$14 = 0x400f8a
(gdb) print /x *0x402490
$15 = 0x400f91
(gdb) print /x *0x402498
$16 = 0x400f98
(gdb) print /x *0x4024a0
$17 = 0x400f9f
(gdb) print /x *0x4024a8
$18 = 0x400fa6
(gdb) print /x *0x4024b0
$19 = 0x7564616d
```
最後程式跳轉到 `400fbe` ，==%rax 與第二個輸入的數字必需相同==才不會引爆炸彈。所以這ㄧ題其實有 8 種可行的數字組合，分別為 ==[0 207], [1 311], [2, 707], [3, 256], [4 389], [5 206], [6 682], [7 327]== (皆已轉換為十進位表示)
```cpp
0x0000000000400fbe <+123>: cmp 0xc(%rsp),%eax
```
```cpp
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
```
## Phase_4
與 `phase_3` 相同，要求使用者輸入兩個數字 `N1 N2`。先比較第一個數字，若大於 `14` 則觸發炸彈，否則進入 `func4`，輸入的參數為 `0xe(%edx), 0x0(%esi) & N1(edi)`
```cpp
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>
```
以下為 `func4` 的機器語言表示，使用到遞迴呼叫，單純用看得實在看不出端倪
```cpp
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
```
看一看決定不要浪費時間，直接把這段組合語言轉成 C code，並觀察使用者第一個輸入 `C = 0~14` 的輸出
```cpp
#include <stdio.h>
int func4(int A, int B, int C) {
int n1 = A - B;
int n2 = n1;
n1 += n2 >> 31;
n1 = n1 >> 1;
n2 = n1 + B;
if (n2 > C) {
n1 = func4(n2-1, B, C);
n1 += n1;
}
else {
n1 = 0;
if (n2 < C) {
n1 = func4(A, n2+1, C);
n1 += n1 + n1 + 1;
}
}
return n1;
}
int main()
{
for (int i = 0; i < 15; i++) {
int res = func4(14, 0, i);
printf("Input: %d %d %d, Result: %d\n", 14, 0, i, res);
}
return 0;
}
Input: 14 0 0, Result: 0
Input: 14 0 1, Result: 0
Input: 14 0 2, Result: 4
Input: 14 0 3, Result: 0
Input: 14 0 4, Result: 2
Input: 14 0 5, Result: 2
Input: 14 0 6, Result: 8
Input: 14 0 7, Result: 0
Input: 14 0 8, Result: 1
Input: 14 0 9, Result: 1
Input: 14 0 10, Result: 7
Input: 14 0 11, Result: 1
Input: 14 0 12, Result: 4
Input: 14 0 13, Result: 4
Input: 14 0 14, Result: 13
```
知道 `func4` 的輸出 `res` 後我們再回到 `phase_4`，程式會先確認 `res` 是否為 0，不為 0 則觸發炸彈，接著確認使用者第二個輸入是否為 0，同樣若不為 0 則觸發炸彈，綜合 `res` 可以得知本題共有 4 種可行的數字組合，分別為 ==[0 0], [1 0], [3 0], [7 0]==
```cpp
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
```
```cpp
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
```
## Phase_5
這題與 `phase_1` 類似，程式一開始先比對使用者輸入是否為 6 個字節
```cpp
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>
```
接著程式設立一個 counter = 0，並從 stack 中將使用者輸入逐字取出
```cpp
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
```
取出後程式使用 `& 0xf` 將字節的低四位取出，並將該值加上 `0x4024b0` 後取出一個字節，先來看看 `0x4024b0` 裡面儲存的字串
```cpp
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
0x00000000004010a8 <+70>: cmp $0x6,%rax
0x00000000004010ac <+74>: jne 0x40108b <phase_5+41>
```
```cpp
(gdb) print (char *) 0x4024b0
$7 = 0x4024b0 <array> "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
```
光看字串可能以為答案是 `ctrl-c`，不過想著應該不會跟第一題一樣，我們繼續往下看
程式會將從 `0x4024b0` 擷取到的 6 個字串存入 `%rdi`，並將擷取的結果跟另一個存在 `0x401338` 的字串進行比較，判斷是否相同
```cpp
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>
...
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
```
嘗試印出兩個字串，發現當輸入為 `abcdef` 時，抓到的文字為 `aduier` ，在句子中是連續的位置，如果對比 ASCII 編碼可以發現 `a~f` 的編碼為 `0x61~0x66`，對這些數字進行 `& 0xf` 操作得到`1~6`，剛好就是 `aduier` 各個字母在句子中的索引
```cpp
(gdb) print (char *) $rdi
$11 = 0x7fffffffd780 "aduier"
(gdb) print (char *) $rsi
$12 = 0x40245e "flyers"
```
由上述解析可以推斷，輸入字串 ==ASCII 編碼的低 4 位==必需符合 `flyers` 在句子中的位置，觀察 `flyers` 各個字母在句子中最先出現的位置分別為 `9 15 14 5 6 7`，所以這題的答案為 ==`ionefg`==
```cpp
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
```
## Phase_6
最後一題的難度提昇不少，對輸入有更多的限制，而且求解過程還有點迂迴，總共花了約 6 個小時才成功，但拆除炸彈的那一瞬間非常有的成就感，此外藉由這個 Lab 學習並熟練 `gdb` 的使用方法，是收穫滿滿的一次 Lab
這題要求使用者輸入 6 個數字 `N1 N2 N3 N4 N5 N6`，前面配置 stack 及將輸入存入 stack 的過程就不贅述，我們從 `0x40110b <+23>` 的位置看起。
`0x40110b ~ 0x401151` 是本題的第一階段
1. 將 `N1` 所在的 stack 位置暫存至 `%r14` 待後續程式使用，並建立計數器 `T1` 儲存於 `%r12d`
2. 將 `%r13` 值存到 `%rsb` 中，此時 `%r13` 儲存的是 `%rsp` 的位置。`0x401117 <+35>` 將 `N1` 讀取出來後剪掉 1，並與 5 比較，若大於 5 則觸發炸彈
3. 程式跳轉至 `0x401128 <+52>` 將計數器 `T1` +1 並與 6 進行比較，直到計數器等於 6 時才會跳到 `0x401153 <+95>`，代表第 2 點的比較過程要執行 6 次
4. `0x401132 <+62> ~ 0x401138 <+68>` 設立另一個計數器 `T2` (從 `T1` 開始)，並從 `%rsp + T2 * 4` 讀取使用者的輸入，再與目前存在`%rbp` 的數字比較，若相等的話則觸發炸彈`
5. 從 `0x401132 <+62>, 0x401145<+81>~0x40114b <+87>` 可以發現程式會從 stack 取出 `6 - T1` 次數字
6. 比較完成後更新 `%r13` 儲存的記憶體位置(`%rsp + T1 * 4`)，跳回 `0x401114 <+32>`，重複 1 ~ 6 的步驟
仔細思考上面的 6 個步驟，不難發現程式從第一個輸入開始，==每次抓出一個輸入 `Nx` 且該數字 `-1` 不得大於 5==。接著程式迭代讀取 `Nx` 之後的所有使用者輸入，並==確認這些數字是否與 `Nx` 相同==，若相同則觸發炸彈。假設這些數字存於陣列 `A` 中，寫成虛擬碼如下，從這邊我們可以確定 ==`N1 ~ N6` 都小於等於 6，且數字不得重複==
```cpp
for (int i = 0; i != 6; i++) {
int nx = A[i];
if ((nx - 1) > 5) explode();
for (int j = i + 1; j <= 5; j++) {
if (A[j] == nx) explode();
}
}
```
```cpp
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>
```
`0x401153<+95> ~ 0x40116d<+121>` 這一段比較單純
1. 程式先將 `%rsp + 24` 的位置存於 `%rsi`
2. `r14` 此時儲存 `%rsp` 的位置，將使用者輸入從 stack 中讀取後，以 7 減去該值並存回相同記憶體位置
3. 完成後讀取下一個使用者輸入並重複步驟 2，直到完成所有輸入
4. 所以這段程式碼在替換使用者輸入，==將 `N1 ~ N6` 更新為 `7-N1, 7-N2,..., 7-N6`==
```cpp
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>
```
接下來進入本題個人認為最困難的部份，多數時間都花在這一個 part 上，不過解出來後覺得，雖然程式碼看起來很多很可怕，但靜下心來仔細觀察，其實沒有想像中複雜
首先程式初始化一個新的計數器 `T3` 儲存於 `%rdi`，並從 stack 中讀取(更新後)使用者輸入存入 `%ecx`，並與 1 進行比較，若小於等於 1 走 `0x401183 <+143>` 分支，否則走 `0x401176 <130>` 分支
```cpp
0x000000000040116f <+123>: mov $0x0,%esi
...
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>
```
1. 觀察 `0x4011a4 <+176>` 與 `0x401183 <+143>` 可以發現，無論是哪個分支，程式都會將記憶體位置 `0x6032d0` 存入 `%edx`
2. 如果走 `<+130>` 分支，程式會不斷地以 `*(%rdx+8)` 儲存的記憶體位置更新 `%rdx`，直到 `%eax` 的數字與讀取的(更新後)使用者輸入相同
3. 如果走 `<+143>` 分支，則程式直接將 `0x6032d0` 存入 `%edx` 中
4. 分支操作完成後，進入 `<+148>` 將 `%rdx` 儲存的記憶體位置存入 stack `%rsp + 2 * T3 + 32`
5. 更新計數器 `T3`，並確認是否等於 `24`，所以這一整段程式碼會執行 6 次
6. 搭配 `N1~N6` 不大於 6 的限制(`7-N1 ~ 7-N6` 也不大於 6)，代表當 `N = 6` 時會走 `<+143>` 分支，其他數字 (1~5) 都會走 `<+130>` 分支，以下列出各輸入(更新前)數字對應的記憶體位置
```cpp
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>
(gdb) print *(int *) 0x6032d8
$7 = 6304480
(gdb) print *(int *) 0x6032e8
$9 = 6304496
(gdb) print *(int *) 0x6032f8
$10 = 6304512
(gdb) print *(int *) 0x603308
$11 = 6304528
(gdb) print *(int *) 0x603318
$12 = 6304544
6 --> 0x6032d0
5 --> 0x6032e0
4 --> 0x6032f0
3 --> 0x603300
2 --> 0x603310
1 --> 0x603320
```
得到所有數字對應的記憶體位置後，程式進入最後一個環節
1. 將 `%rsp+32` 中記憶體位置儲存的值存入 `%rcx`
2. 將 `%rsp + 40` & `%rsp + 80` 分別存入 `%rax` & `%rsi`
3. 將 `%rax` 記憶體位置儲存的值存入 `%rcx + 8` 的位置
4. 更新 `%rax = %rax + 8` 並確認 `%rax` 是否等於 `%rsi` ，若利用 `%rdx` 更新 `%rcx`
```cpp
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>
```
我們先以輸入 `1 2 3 4 5 6` 來測試，可以看到此時 `%rcx` 儲存記憶體位置 `0x603320`，對應到第一個使用者輸入， `%rax` 裡頭存著一個記憶體位置 `0x603310`，對應到第二個使用者輸入
```cpp
(gdb) print (int) $rcx
$1 = 6304544
(gdb) print *(int *) $rax
$2 = 6304528
```
這時 `*(%rcx)+8 = 0x603328` 儲存 `0x603310`，而 `%rcx` 被更新為 `0x603310`，依序列印出值後可以發現以下對應關係
```cpp
0x603328 --> 0x603310
0x603318 --> 0x603300
0x603308 --> 0x6032f0
0x6032f8 --> 0x6032e0
0x6032e8 --> 0x6032d0
```
我們將 `0x6032d0 ~ 0x603328` 的值列舉如下(記憶體位置都轉為十六進制)，發現 `0x6032d0, 0x6032e0,...,0x603320` 已經存在數字 `332 168 924 691 477 443`
```cpp
(gdb) print *(int*) 0x6032d0
$33 = 332
(gdb) print *(int*) 0x6032d8
$34 = 0
(gdb) print *(int*) 0x6032e0
$35 = 168
(gdb) print *(int*) 0x6032e8
$36 = 0x6032d0
(gdb) print *(int*) 0x6032f0
$37 = 924
(gdb) print *(int*) 0x6032f8
$38 = 0x6032e0
(gdb) print *(int*) 0x603300
$39 = 691
(gdb) print *(int*) 0x603308
$40 = 0x6032f0
(gdb) print *(int*) 0x603310
$41 = 477
(gdb) print *(int*) 0x603318
$42 = 0x603300
(gdb) print *(int*) 0x603320
$43 = 443
(gdb) print *(int*) 0x603328
$44 = 0x603310
```
進入最後一段程式碼
1. 設置計數器並存於 `%ebp`
2. 讀取儲存於 `%rbp+8` 記憶體位置的數值
3. 與 `%rbx` 儲存的記憶體位置的數值做比較，如果小於步驟 2 取出的數值，則觸發炸彈
4. 更新 `%rbx` 的值並重複 2. & 3. 的步驟共 5 次
```cpp
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>
```
我們先印出 `%rbx` 儲存的記憶體位置，可以發現裡頭儲存第一個輸入對應的記憶體位置
```cpp
(gdb) print (int) ($rbx)
$47 = 0x603320
```
我們再印出 `*(%rsb+8)`，為第二個輸入對應的記憶體位置
```cpp
(gdb) print *(int*) ($rbx+8)
$45 = 0x603310
```
看到這邊邏輯就很清楚了，前一段程式碼在做的事情，類似於建立兩個陣列，一個為存取第 N 個輸入對應的記憶體位置，放在 stack 中; 另一個存取第 N+1 個輸入對應的記憶體位置，放在地址 `&Nx+8`，如下圖所示(N1~N6 為 `332 168 924 691 477 443` 的任意不重複排列)
而每一次比較，輸入 N 對應的值都必須大於 N + 1 對應的值，我們再回頭看一下序列 `332 168 924 691 477 443`，不難想像使用者輸入必需讓==這一串數字從大到小依序讀取==，也就是 `3 4 5 6 1 2` 的順序，但因為使用者輸入在程式中段被修改為 `7-N`，所以本題最終的答案是 ==`4 3 2 1 6 5`==
```cpp
4 --> 0x6032f0 --> 924
3 --> 0x603300 --> 691
2 --> 0x603310 --> 477
1 --> 0x603320 --> 443
6 --> 0x6032d0 --> 332
5 --> 0x6032e0 --> 168
```
```cpp
phase_6
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
```
## Reference
1. [Computer Systems: A Programmer’s Perspective, 3/E (CS:APP3e)](http://csapp.cs.cmu.edu/3e/labs.html)
Sign in with Wallet
Connect another wallet