《深入理解計算機系統》配套實驗：Bomblab

終於要開始做大名鼎鼎的BombLab了！

首先是一些準備工作

lab下載地址：http://csapp.cs.cmu.edu/3e/labs.html

第二個的Bomblab的 self-study handout就是

在做這個lab前，首先要確定使用的調試工具。我試過gdbtui（難用，顯示有問題）和ddd（難用+丑），最後選擇了cgdb。

cgdb最新版本增加了顯示彙編代碼的功能，和bomblab搭配的很棒。

目前（2017/11/21),apt-get源下載到的cgdb仍然不是最新版本，需要到官網下載：

https://cgdb.github.io/

不知道為什麼github clone之後，make總報錯，所以我選擇了從官網下載文件然後按照它的install說明文件編譯安裝。

在安裝完後，在terminal中輸入cgdb， 就可以打開cgdb了。

首先要大概看一下cgdb的中文手冊，如果熟悉vim的話大概10分鐘就能看完。（什麼你不會用vim？那你還是去用gdbtui吧）

cgdb中文手冊

當然你還需要一些必須的x86-64彙編知識(CSAPP第三章） 以及 一份gdb簡易使用指南

http://csapp.cs.cmu.edu/3e/docs/gdbnotes-x86-64.pdf

Phase1

在最新版本的cgdb中，在cgdb模式下輸入

：set disasm

可以顯示反彙編代碼（程序必須處於運行狀態）,如圖：

此處我使用ctrl + W實現了左右分屏

注意到程序需要從stdin或文件中讀取輸入，所以我們需要給程序指定輸入，避免程序卡死在讀取輸入的system call上。

（gdb）run <in

in文件是之前已經解出的炸彈內容；沒有解出來的就隨便寫好了（反正我們的炸彈不會連接到伺服器然後爆炸扣分，所以炸多少次都可以）

設置斷點，逐條語句運行到phase1（）函數，然後使用

(gdb) stepi

單條指令調試工具，進入phase1（）函數，查看該函數反彙編代碼。

（用gdb的同學可以用disas命令，具體的看上面的gdb指南）。

從第四行往後的內容很容易理解，大概就是調用一個判斷兩個字元串是否一樣的函數，如果返回0（函數名為not equal，所以返回0 就是兩個字元串相同），即%eax寄存器內值為0的話就通過，否則引爆炸彈。

我們很容易猜到這個函數要接受兩個參數（廢話，不然怎麼比較兩個字元串），其中一個參數是調用phase_1()的參數input，也就是用戶輸入，另一個參數是奇怪的東西，輸出來看看：

(gdb) x/s 0x4024000x402400: "Border relations with Canada have never been better."

好了，Phase1 我們就做完了。

Phase2

相比Phase1， Phase2可以說難了很多。

首先在phase_2（）處打上斷點：

(gdb) break phase_2 Breakpoint 1 at 0x400efc

然後運行，si逐步調試：

(gdb) run <in(gdb) si

可以看到這裡調用了一個名為read_six_numbers的函數，並且傳入了兩個參數：一個參數是input的地址（也就是我們輸入的字元串），另一個參數是開闢的棧空間的地址。

進入這個函數，發現這個函數裡面就可能會引爆炸彈：

具體做的大概看一下，就是傳了好多參數，調用sscanf，這些參數還都是地址。

那麼這個函數的作用我們就能猜到了：從輸入的字元串中讀取6個數字出來，並且存儲到之前開闢的棧空間內。

而這個函數內引爆炸彈的觸發條件，應該就是input是否由6個數字組成（經過測試也的確如此，在把輸入改成6個數字後，就能順利通過read_six_numbers函數）

提示：這裡如果陷入了一個共享庫函數（sscanf之類),可以用finish命令快速退出

那我們就先把in里phase2的密碼暫時改成1 2 3 4 5 6.百度得知sscanf的參數順序，然後我們依次用print命令輸出調用sscanf（）的參數是啥，可以發現最後這6個數依次被存儲在了

%rsp, %rsp + 4, %rsp + 8, %rsp + 12, %rsp + 16, %rsp + 20

然後我們回到phase_2,按照流程走一遍（很簡單，就在紙上寫一下幾個寄存器值的變化），題目答案就出來了。

Phase3

這一關可以說是很弱智了。

首先還是在phase_3處打上斷點，然後stepi逐條指令執行：

(gdb) break phase_3Breakpoint 1 at 0x400f43(gdb) run <inStarting program: /home/fanese/Documents/CSAPP/bomb/bomb <in

反彙編得到的phase_3代碼如圖所示

看到了熟悉的sscanf（）函數。我們可以看到這裡用到了

%rdi, %rsi, %rdx, %rcx

四個寄存器。根據x86-64 寄存器傳參規則，第一個寄存器存儲的就是調用phase_3時的那個input參數，可以不管；第二個參數是關鍵，指定了格式化字元串讀取的格式，這裡是一個地址。

所以我們把這個第二個參數輸出來看一下：

(gdb) x/s 0x4025cf0x4025cf: "%d %d"

可以得知這次的輸入是兩個整數。

好了，我們退出去，修改in文件，把第三行改為1 2， 繼續調試。

第八行顯示把%eax 和1比較。%eax 存儲的是sscanf函數的返回值，百度得知是正確讀取到的參數個數，所以為2.

在sscanf執行完畢後，我們根據x86-64寄存器傳參規則，可以確定第一個數被存儲在%rsp + 8位置， 第二個數被存儲在%rsp + 12位置。當然可以在gdb中使用如下命令驗證：

(gdb) x/wd $rsp+80x7fffffffddc8: 1

繼續執行，第11行可以看到將第一個參數與7進行比較。因為這裡我們假設第一個參數為1，所以會跳轉。

不停的逐指令執行，到第32行，可以看到將第二個參數與0x137（311）比較，如果不等於就引爆炸彈，所以我們退出去，將第二個參數改成311.

然後炸彈就被拆掉了。

Phase4

這個Phase4有一點小難度。

首先還是和之前一樣的設置斷點，然後查看反彙編源代碼：

(gdb) break phase_4(gdb) run <in

可以看到開始的部分和Phase3是差不多的，所以退出去把in文件的第四行改成1 2兩個數。

注意，為了敘述方便，從此處開始，將兩個參數稱作x y。

接著逐條指令調試，在第10行，有一個x 與 14的比較。因為第12行就會引爆炸彈，所以第11行的條件跳轉指令必須執行，也就是 x <= 14.

因為我們假設的x為1， 繼續逐步調試。

接下來可以看到，程序設置了幾個寄存器的值，並調用了一個名為fun4的函數。根據x86-64寄存器調用規則，可以確定函數的調用情況為：

fun4(x, 0, 4)

傳入的是三個int類型變數，所以不用擔心這個函數去修改內存，所以我們先看這個函數之後的部分。

如果已經進入了這個函數，可以使用

(gdb) disassemble phase_4

在gdb窗口調出phase_4 函數的反彙編代碼。

根據fun4之後的反彙編代碼，很容易看出只有當fun4（）返回0 且y == 0，才能解除炸彈。

接下來我們深入函數：

注意到只有%rdi 存儲了我們的x，而在2 - 9行的反彙編代碼都沒有出現%rdi， 所以放心的逐步調試，直到第10行，比較%edi和 %ecx的值。

(gdb) print/d $ecx$17 = 7

查看%ecx寄存器的值，並把這個值作為x， 輸入後發現炸彈已經被解除。

Phase5

Phase5就是真的有點難了。

還是和之前一樣，設置斷點，運行，然後逐指令調試：

經過百度，第四行的內容是和stack-protecter有關的，暫時不管。

可以看到第八行調用了對字元串求長度的函數，之後如果長度不是6就引爆炸彈。所以退出去將in的第五行改為「abcdef」，繼續調試。

然後都是一些簡單的mov操作，可以先在紙上記錄一下。

到了13行，我們需要看一下這句話是什麼意思。

0x000000000040108b <+41>: movzbl (%rbx,%rax,1),%ecx

大概意思是取內存的這個位置的一個位元組，然後零拓展到32位，存儲到%ecx寄存器里去。

根據之前的操作，%rbx存放的應該是我們input的起始位置，驗證一下：

(gdb) x/s $rbx0x6038c0 <input_strings+320>: "abcdef"

此時的%rax寄存器值為0，那麼這條指令也就是把我們輸入的第一個字元（a）的ASCII碼存儲到了%ecx寄存器中。

14-15行把%ecx寄存器的值移到了%ecx寄存器中。（cl是%ecx寄存器的低8位訪問方式）

第16行：

0x0000000000401096 <+52>: and $0xf,%edx

把%edx寄存器的高28位清0，只保留低4位。

考慮到%edx里存儲的是一個字元的ASCII碼，我們得到的是這個ASCII碼的低4位。

第17行

0x0000000000401099 <+55>: movzbl 0x4024b0(%rdx),%edx

這條指令的意思是，從（0x4024b0 + %rdx）這個位置取一個位元組，進行零拓展之後，得到的值放到%edx裡面去。

媽耶，我們怎麼知道這是個啥東西？

別急，輸出來看一下：

(gdb) x/s 0x4024b00x4024b0 <array.3449>: "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

原來是一個字元串。那麼我們做的就是：以輸入字元的低4位作為索引，去訪問這個字元串的一個字元，並存儲到%edx里。

第18行

0x00000000004010a0 <+62>: mov %dl,0x10(%rsp,%rax,1)

把這個得到的值存儲到了內存中，起始位置為%rsp + 16

第19-20行：

0x00000000004010a4 <+66>: add $0x1,%rax20│ 0x00000000004010a8 <+70>: cmp $0x6,%rax

就是說把上述的步驟重複6次：存儲到%rsp + 16 %rsp + 17,......%rsp + 21 的位置。

那麼我們就重複執行，看看直到%rax 為6（循環結束），之後bomb會幹什麼。

可以用watch變數的方式觀察%rax的變化：

(gdb) watch $raxWatchpoint 2: $raxOld value = 5New value = 6

然後用

(gdb) delete 2

刪除這個watchpoint.

第22行，在%rsp + 22位置插入了一個byte，值為0，其實就是給字元串加上了『』

現在我們可以輸出看一下這個得到的字元串是什麼了：

(gdb) x/s $rsp+160x7fffffffddc0: "aduier"

接下來就進入easy模式了：可以看到調用了strings_not_equal函數，待比較的字元串地址放在了%esi里，那麼我們就輸出位於%esi的字元串，看看到底是什麼：

(gdb) x/s $esi0x40245e: "flyers"

之後的指令就是說，根據我們輸入生成的字元串需要和「flyers"比較。如果相同就可以。

那麼我們依次去那個字元串里找"f" "l" "y"等字元，然後去ASCII表查詢哪個字元的低4位滿足條件。

那麼Phase5 我們就完成了.

Phase6

這一關的確很有難度！不愧是BOSS關！

建議想嘗試的讀者空出大於2小時的時間，一口氣把這一關做完（作者花了2小時），所獲得的成就感是無與倫比的。

好了，廢話不多說，我們開始吧。

首先我們看到了我們的老朋友read_six_numbers，所以退出去把in第6行改成1 2 3 4 5 6，再進入程序進行調試。

下面把我們輸入的6個數稱為a1， a2， a3，a4, a5, a6

在掉用完這個函數後，我們輸入的6個數被依次存儲在

%rsp, %rsp + 4， %rsp + 8, %rsp + 12, %rsp + 16, %rsp + 20

接著我們逐指令執行，發現之後的代碼依次保證了如下的條件，如果不滿足就引爆炸彈：

a1 <= 6; a1 != a2; a1 != a3; a1 != a4; a1 != a5; a1 != a6

然後我們會發現第二次執行和之前差不多，只是條件改成了

a2 <= 6; a2 != a3; a2 != a4; a2 != a5; a2 != a6 ;

所以這一段代碼的意思是所有輸入的數不能相同，並且都小於等於6.

接下來的代碼比較難看懂了。。主要是這一句：

mov 0x8(%rdx),%rdx

仔細想想CSAPP講過的結構體對齊，就知道這是一個鏈表

Node* ptr = &A;ptr = ptr -> next;

的彙編形式代碼。

那麼首先我們要把這個鏈表每個節點的值和地址都寫在紙上。

下面一長串指令其實就是根據我們輸入數的值創建對應的鏈表節點，每個值和一個節點的地址、值對應。也就是說，我們給根據輸入的值得到了一個鏈表。

再接下來的代碼實際上把得到的鏈表進行了排序——使得第i個鏈表對應我們的第i個輸入。

最後是一個判斷：假如經過排序的鏈表的值是嚴格單調遞增的，就解除了炸彈。

那麼，我們根據鏈表每個節點的val域的值，就得到了這個鏈表的順序，以及輸入的值。

因為最後一個phase是幾天前做的了，現在回憶具體細節已經不太清楚，但是相信讀者只要堅持，一定能解除炸彈的。