CS:APP Lab 2 - Bomb Lab - 帶彩蛋

彩蛋在最後。

列出一些很有用的命令

$ gdb bomb$ objdump -d bomb > bomb.s# ctrl + x, ctrl + a 切換至 TUI 模式方便查看# help 大概才是最有用的命令吧(滑稽)(gdb) help(gdb) help x# 添加 breakpoint 在函數 phase_1 上(gdb) b phase_1# 添加 breakpoint 在對應的地址上(gdb) b *0x40124d# step in = step instruction = stepi(gdb) si# step out = finish(gdb) fin# step over = next instruction = nexti(gdb) ni# 從頭開始運行(gdb) run# 列印寄存器內容 print(gdb) p $rdi# 將內容看做 char(gdb) p/c $rdi# 解引用內容 x = eXamine(gdb) x $rdi# 常數地址(gdb) x 0x402400# 以字元串解析 s = string(gdb) x/s $rsp+0x10# 按 word (4 bytes) 為寬度顯示 6 個 16進位數字# x = heXadecimal(gdb) x/6wx $rsp

Phase 1

0x400ee0 <phase_1> sub $0x8,%rsp0x400ee4 <phase_1+4> mov $0x402400,%esi0x400ee9 <phase_1+9> callq 0x401338 <strings_not_equal>0x400eee <phase_1+14> test %eax,%eax0x400ef0 <phase_1+16> je 0x400ef7 <phase_1+23>0x400ef2 <phase_1+18> callq 0x40143a <explode_bomb>0x400ef7 <phase_1+23> add $0x8,%rsp0x400efb <phase_1+27> retq

可以看到 phase_1() 裡面調用了判斷函數 strings_not_equal()。後邊緊跟著 test %eax, %eax,是對剛剛的函數返回值的判斷。

運行到上面的第三行時使用 x/s $esi 可以列印出對應的字元串。或者繼續跳進函數,查看第一個參數也可以得到 x/s $rdi,第二個參數 x/s $rsi 會得到你輸入的字元串。

作者說每次下載的到的答案都是不一樣的。

我的答案是:

Border relations with Canada have never been better.

Phase 2

像上一個一樣進入 phase_2() 函數中,直接分析彙編:

<+0>: push %rbp<+1>: push %rbx<+2>: sub $0x28,%rsp<+6>: mov %rsp,%rsi<+9>: callq 0x40145c <read_six_numbers><+14>: cmpl $0x1,(%rsp)<+18>: je 0x400f30 <phase_2+52><+20>: callq 0x40143a <explode_bomb><+25>: jmp 0x400f30 <phase_2+52><+27>: mov -0x4(%rbx),%eax<+30>: add %eax,%eax<+32>: cmp %eax,(%rbx)<+34>: je 0x400f25 <phase_2+41><+36>: callq 0x40143a <explode_bomb><+41>: add $0x4,%rbx<+45>: cmp %rbp,%rbx<+48>: jne 0x400f17 <phase_2+27><+50>: jmp 0x400f3c <phase_2+64><+52>: lea 0x4(%rsp),%rbx<+57>: lea 0x18(%rsp),%rbp<+62>: jmp 0x400f17 <phase_2+27><+64>: add $0x28,%rsp<+68>: pop %rbx<+69>: pop %rbp<+70>: retq

+9 位置是讀取六個數字的函數,可以看到 +6 位置把棧指針傳入為第二個參數,看一下函數內容:

<+0>: sub $0x18,%rsp<+4>: mov %rsi,%rdx<+7>: lea 0x4(%rsi),%rcx<+11>: lea 0x14(%rsi),%rax<+15>: mov %rax,0x8(%rsp)<+20>: lea 0x10(%rsi),%rax<+24>: mov %rax,(%rsp)<+28>: lea 0xc(%rsi),%r9<+32>: lea 0x8(%rsi),%r8<+36>: mov $0x4025c3,%esi<+41>: mov $0x0,%eax<+46>: callq 0x400bf0 <__isoc99_sscanf@plt><+51>: cmp $0x5,%eax<+54>: jg 0x401499 <read_six_numbers+61><+56>: callq 0x40143a <explode_bomb><+61>: add $0x18,%rsp<+65>: retq

context: read_six_numbers()

看到用了 sscanf 函數,再次跳進可以查看參數 %rdirsi 分別是格式和你的輸入,格式就是用空格分割的六個數字。

從 +7 位置開始到 +32 都是在為 sscanf 的參數準備,+0 位置移動棧指針,就是為了六個數字的空間。

content: phase_2()

那麼回到外層,可以知道 +14 的地方是在判斷第一個數字是否為 1。

接下來跳到 +52 到 +62 這段是取下一個數字的棧地址並判斷是否取完。

跳到 +27 到 +32 可以看出來就是在判斷這個數字是否是上一個的兩倍。到這裡基本上可以猜到六個數字了。

調到 +41 到 +45 移動位置。

最後答案是:

1 2 4 8 16 32

Phase 3

<+0>: sub $0x18,%rsp<+4>: lea 0xc(%rsp),%rcx<+9>: lea 0x8(%rsp),%rdx<+14>: mov $0x4025cf,%esi<+19>: mov $0x0,%eax<+24>: callq 0x400bf0 <__isoc99_sscanf@plt><+29>: cmp $0x1,%eax<+32>: jg 0x400f6a <phase_3+39><+34>: callq 0x40143a <explode_bomb><+39>: cmpl $0x7,0x8(%rsp)<+44>: ja 0x400fad <phase_3+106><+46>: mov 0x8(%rsp),%eax<+50>: jmpq *0x402470(,%rax,8)...<+106>: callq 0x40143a <explode_bomb>...<+118>: mov $0x137,%eax<+123>: cmp 0xc(%rsp),%eax<+127>: je 0x400fc9 <phase_3+134><+129>: callq 0x40143a <explode_bomb><+134>: add $0x18,%rsp<+138>: retq

同之前的操作一樣,這次看起來有些長,但是其實有一半不需要看,所以這裡就不列出來了。

運行到 +19 位置後即可直接查看 %esi 也就是 0x4025cf 為地址的內存裡面存著 "%d %d",所以可以確定輸入為兩個數字,+29 和 +32 位置也可以看出同樣的意思。

接下來 +4 和 +9 分別設定了 sscanf() 的第三和第四參數,所以 0x8(%rsp) 內存位置是你輸入的第一個數字,+39 和 +44 很明顯這個數字小於 7 即可。

來到 +50 這裡有一個 *,實際跳轉是 0x402470(,%rax,8) 地址裡面所存儲的地址,可以不用去管他,ni 會幫你跳到該到的位置。

實際回來到 +118 的位置,接下來的三行就同上了,結果是要求等於 0x137 也就是 311。

最後答案可以是:

1 311

Phase 4

<+0>: sub $0x18,%rsp<+4>: lea 0xc(%rsp),%rcx<+9>: lea 0x8(%rsp),%rdx<+14>: mov $0x4025cf,%esi<+19>: mov $0x0,%eax<+24>: callq 0x400bf0 <__isoc99_sscanf@plt><+29>: cmp $0x2,%eax<+32>: jne 0x401035 <phase_4+41><+34>: cmpl $0xe,0x8(%rsp)<+39>: jbe 0x40103a <phase_4+46><+41>: callq 0x40143a <explode_bomb><+46>: mov $0xe,%edx<+51>: mov $0x0,%esi<+56>: mov 0x8(%rsp),%edi<+60>: callq 0x400fce <func4><+65>: test %eax,%eax<+67>: jne 0x401058 <phase_4+76><+69>: cmpl $0x0,0xc(%rsp)<+74>: je 0x40105d <phase_4+81><+76>: callq 0x40143a <explode_bomb><+81>: add $0x18,%rsp<+85>: retq

同樣的方法會知道和上面一樣是兩個數字,+34 這裡第一個數字要小於 0xe 也就是 14,接下來會調用一個有遞歸的函數 func4()

先來到 +69 這裡可以看到第二個數字需要為 0

因為輸入已經確定到一個很小的範圍了,其實到這裡不看下去也是可以的,直接給出答案 1 0

當然為了拆掉會炸飛自己的炸彈,你可能不會這麼草率(滑稽)

<+0>: sub $0x8,%rsp<+4>: mov %edx,%eax<+6>: sub %esi,%eax<+8>: mov %eax,%ecx<+10>: shr $0x1f,%ecx<+13>: add %ecx,%eax<+15>: sar %eax<+17>: lea (%rax,%rsi,1),%ecx<+20>: cmp %edi,%ecx<+22>: jle 0x400ff2 <func4+36><+24>: lea -0x1(%rcx),%edx<+27>: callq 0x400fce <func4><+32>: add %eax,%eax<+34>: jmp 0x401007 <func4+57><+36>: mov $0x0,%eax<+41>: cmp %edi,%ecx<+43>: jge 0x401007 <func4+57><+45>: lea 0x1(%rcx),%esi<+48>: callq 0x400fce <func4><+53>: lea 0x1(%rax,%rax,1),%eax<+57>: add $0x8,%rsp<+61>: retq

從外部可以看出這個函數有三個參數,分別是你輸入的數字,0 和 14。可以說到 +13 為止的操作都沒什麼實際作用,+15 這裡 14 右移了一位,變成了 7 。

到 +17 這裡為止結果就是把第三個參數 14 除以二 7 放進了 %ecx,如果大於你輸入的數字繼續。

7 - 1 放入第三個參數,遞歸調用自己。三個參數分別是你輸入的數字,0 和 6。

這個時候已經可以判斷輸入 1 是正確的了。

最後答案可以是:

1 0

Phase 5

<+0>: push %rbx<+1>: sub $0x20,%rsp<+5>: mov %rdi,%rbx<+8>: mov %fs:0x28,%rax<+17>: mov %rax,0x18(%rsp)<+22>: xor %eax,%eax<+24>: callq 0x40131b <string_length><+29>: cmp $0x6,%eax<+32>: je 0x4010d2 <phase_5+112><+34>: callq 0x40143a <explode_bomb><+39>: jmp 0x4010d2 <phase_5+112><+41>: movzbl (%rbx,%rax,1),%ecx<+45>: mov %cl,(%rsp)<+48>: mov (%rsp),%rdx<+52>: and $0xf,%edx<+55>: movzbl 0x4024b0(%rdx),%edx<+62>: mov %dl,0x10(%rsp,%rax,1)<+66>: add $0x1,%rax<+70>: cmp $0x6,%rax<+74>: jne 0x40108b <phase_5+41><+76>: movb $0x0,0x16(%rsp)<+81>: mov $0x40245e,%esi<+86>: lea 0x10(%rsp),%rdi<+91>: callq 0x401338 <strings_not_equal><+96>: test %eax,%eax<+98>: je 0x4010d9 <phase_5+119><+100>: callq 0x40143a <explode_bomb><+105>: nopl 0x0(%rax,%rax,1)<+110>: jmp 0x4010d9 <phase_5+119><+112>: mov $0x0,%eax<+117>: jmp 0x40108b <phase_5+41><+119>: mov 0x18(%rsp),%rax<+124>: xor %fs:0x28,%rax<+133>: je 0x4010ee <phase_5+140><+135>: callq 0x400b30 <__stack_chk_fail@plt><+140>: add $0x20,%rsp<+144>: pop %rbx<+145>: retq

不要太過畏懼長度,因為後面還有更長的。+24 之前的直接略過,關於 mov %fs:0x28, %rax 周圍的語句,是一個棧檢查的操作,這裡有個解釋:Stackoverflow - Why does this memory address have a random value?

+24 看函數名也可以得知識計算你輸入字元串的長度,進去查看可以看到是通過檢查字元串結尾的 0 來判斷長度的,這裡就不列出來了。緊接的兩行要求你輸入的字元串長度為 6

經過 +112 行的清零之後回到 +41,接下來到 +74 這段行程一個 while 循環,可以看出是在遍歷字元串,逐句閱讀可以得到這段的操作是,取得當前字元的數字的低4位值,從起始點 0x4024b0 內存位置偏移剛剛的數字量後得到的數據放入棧空間。通過查看剛剛的內存位置可以看到以下內容:

maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?

+81 到 +96 這裡可以看出是要和剛剛組成的字元串與地址 0x40245e 上的字元串比較,查看內存可以看到內容是 flyers。可以理解成一個有字典的加密。

最後答案可以是:

9?>567

Phase 6

嗯,這是最長的了。這從頭到尾分析一遍,當然這可能並不是最好最快的辦法,但是能保證對代碼理解清晰。

# 初始化<+0>: push %r14<+2>: push %r13<+4>: push %r12<+6>: push %rbp<+7>: push %rbx<+8>: sub $0x50,%rsp # 讀取 6 個數字<+12>: mov %rsp,%r13<+15>: mov %rsp,%rsi<+18>: callq 0x40145c <read_six_numbers><+23>: mov %rsp,%r14<+26>: mov $0x0,%r12d-------------------------------------------------- # 這個嵌套循環用於判斷所有的數字都不一樣且都小於等於 6 則通過 # 判斷是否小於等於 6,否則爆炸<+32>: mov %r13,%rbp<+35>: mov 0x0(%r13),%eax<+39>: sub $0x1,%eax<+42>: cmp $0x5,%eax<+45>: jbe 0x401128 <phase_6+52><+47>: callq 0x40143a <explode_bomb># %r12d 相當於 i,循環 6 # %ebx 相當於 j,循環 i <+52>: add $0x1,%r12d<+56>: cmp $0x6,%r12d<+60>: je 0x401153 <phase_6+95> # 跳出循環<+62>: mov %r12d,%ebx # j = i # 判斷兩個數字相等,相等則爆炸<+65>: movslq %ebx,%rax<+68>: mov (%rsp,%rax,4),%eax<+71>: cmp %eax,0x0(%rbp)<+74>: jne 0x401145 <phase_6+81><+76>: callq 0x40143a <explode_bomb> # j += 1, j <= 5<+81>: add $0x1,%ebx<+84>: cmp $0x5,%ebx<+87>: jle 0x401135 <phase_6+65><+89>: add $0x4,%r13<+93>: jmp 0x401114 <phase_6+32>--------------------------------------------------- # %rsi 存儲 6 個數字後的空間 # %rax 存儲棧頂 # %ecx = 7<+95>: lea 0x18(%rsp),%rsi<+100>: mov %r14,%rax<+103>: mov $0x7,%ecx # 循環 7 減去每一個數字再放回去 # 結束之後 %esi 置零<+108>: mov %ecx,%edx<+110>: sub (%rax),%edx<+112>: mov %edx,(%rax)<+114>: add $0x4,%rax<+118>: cmp %rsi,%rax<+121>: jne 0x401160 <phase_6+108><+123>: mov $0x0,%esi<+128>: jmp 0x401197 <phase_6+163>---------------------------------------------------- # 這一段最終的結果是按照減過的數字作為序號順序 # 把鏈表的地址拿出放進棧空間 # 鏈表定址循環<+130>: mov 0x8(%rdx),%rdx<+134>: add $0x1,%eax<+137>: cmp %ecx,%eax<+139>: jne 0x401176 <phase_6+130><+141>: jmp 0x401188 <phase_6+148> # 這個地址是鏈表的第一個節點地址 # 查看方式及內容單獨列在下面<+143>: mov $0x6032d0,%edx # 將當前節點地址移入棧空間<+148>: mov %rdx,0x20(%rsp,%rsi,2)<+153>: add $0x4,%rsi<+157>: cmp $0x18,%rsi<+161>: je 0x4011ab <phase_6+183> # 按順序取減過的數字<+163>: mov (%rsp,%rsi,1),%ecx<+166>: cmp $0x1,%ecx<+169>: jle 0x401183 <phase_6+143><+171>: mov $0x1,%eax<+176>: mov $0x6032d0,%edx<+181>: jmp 0x401176 <phase_6+130>------------------------------------------------------ # 反轉鏈表初始化 # %rbx 是鏈表最後一個節點地址 # %rax 是鏈錶鏈表最後一個節點存儲下一個結點地址的地址 # %rsi 是棧空間存儲鏈表順序的結尾<+183>: mov 0x20(%rsp),%rbx<+188>: lea 0x28(%rsp),%rax<+193>: lea 0x50(%rsp),%rsi<+198>: mov %rbx,%rcx # 按照棧空間存儲的順序把鏈表結點存儲的地址修正<+201>: mov (%rax),%rdx<+204>: mov %rdx,0x8(%rcx)<+208>: add $0x8,%rax<+212>: cmp %rsi,%rax<+215>: je 0x4011d2 <phase_6+222><+217>: mov %rdx,%rcx<+220>: jmp 0x4011bd <phase_6+201> # 清空最後一個處理的節點存儲的地址<+222>: movq $0x0,0x8(%rdx)<+230>: mov $0x5,%ebp------------------------------------------------------ # %rbx 沒有變化過還是鏈表第一個節點的地址 # 檢查鏈表是否從大到小排列<+235>: mov 0x8(%rbx),%rax<+239>: mov (%rax),%eax<+241>: cmp %eax,(%rbx)<+243>: jge 0x4011ee <phase_6+250><+245>: callq 0x40143a <explode_bomb> # 未到達鏈表結尾時循環<+250>: mov 0x8(%rbx),%rbx<+254>: sub $0x1,%ebp<+257>: jne 0x4011df <phase_6+235><+259>: add $0x50,%rsp<+263>: pop %rbx<+264>: pop %rbp<+265>: pop %r12<+267>: pop %r13<+269>: pop %r14<+271>: retq

使用命令查看鏈表,前一個數值是存儲的數據,後一個數值是下一個節點的地址

(gdb) x/12g 0x6032d00x6032d0 <node1>: 0x000000010000014c 0x00000000006032e00x6032e0 <node2>: 0x00000002000000a8 0x00000000006032f00x6032f0 <node3>: 0x000000030000039c 0x00000000006033000x603300 <node4>: 0x00000004000002b3 0x00000000006033100x603310 <node5>: 0x00000005000001dd 0x00000000006033200x603320 <node6>: 0x00000006000001bb 0x0000000000000000

按從大到小的順序序號是, 3 4 5 6 1 2, 但是還要用 7 減一遍

那麼最後答案就有了:

4 3 2 1 6 5

Secret Phase 彩蛋

直接查看完整的彙編代碼可以發現有一個 secret_phase() 的函數,Dr. Evil 還埋了個彩蛋。

首先打兩個斷點,一個在 main() 函數里第一個 read_line() 之前,一個在 secret_phase() 里的 read_line() 之後,這些位置通過查看完整的彙編文件可以找到對應的地址。接著運行到第一個斷點時 call secret_phase() 即可。

<+0>: push %rbx<+1>: callq 0x40149e <read_line><+6>: mov $0xa,%edx<+11>: mov $0x0,%esi<+16>: mov %rax,%rdi<+19>: callq 0x400bd0 <strtol@plt><+24>: mov %rax,%rbx<+27>: lea -0x1(%rax),%eax<+30>: cmp $0x3e8,%eax<+35>: jbe 0x40126c <secret_phase+42><+37>: callq 0x40143a <explode_bomb> # 要運行到這裡,需要輸入一個數字,轉為 long,小於 0x3e8 # fun7 準備參數 # 0x6030f0 處存著一個鏈表,下面會列出內容 # 需要 fun7 的返回值為 2 才能通過<+42>: mov %ebx,%esi<+44>: mov $0x6030f0,%edi<+49>: callq 0x401204 <fun7><+54>: cmp $0x2,%eax<+57>: je 0x401282 <secret_phase+64><+59>: callq 0x40143a <explode_bomb><+64>: mov $0x402438,%edi<+69>: callq 0x400b10 <puts@plt><+74>: callq 0x4015c4 <phase_defused><+79>: pop %rbx<+80>: retq

鏈表的內容如下,稍微處理了一下,方便觀察:

0x6030f0 <n1>: 36 0x6031100x603100 <n1+16>: 0x603130 null0x603110 <n21>: 8 0x6031900x603120 <n21+16>: 0x603150 null0x603130 <n22>: 50 0x6031700x603140 <n22+16>: 0x6031b0 null0x603150 <n32>: 22 0x6032700x603160 <n32+16>: 0x603230 null0x603170 <n33>: 45 0x6031d00x603180 <n33+16>: 0x603290 null0x603190 <n31>: 6 0x6031f00x6031a0 <n31+16>: 0x603250 null0x6031b0 <n34>: 107 0x6032100x6031c0 <n34+16>: 0x6032b0 null0x6031d0 <n45>: 40 null0x6031e0 <n45+16>: null null0x6031f0 <n41>: 1 null0x603200 <n41+16>: null null0x603210 <n47>: 99 null0x603220 <n47+16>: null null0x603230 <n44>: 35 null0x603240 <n44+16>: null null0x603250 <n42>: 7 null0x603260 <n42+16>: null null0x603270 <n43>: 20 null0x603280 <n43+16>: null null0x603290 <n46>: 47 null0x6032a0 <n46+16>: null null0x6032b0 <n48>: 1001 null0x6032c0 <n48+16>: null null

稍微觀察一下就發現這是個二叉樹,還是個滿二叉樹。左邊的標記已經標示出每個節點的位置。把樹畫出來你還會發現這個是個二叉排序樹。

詳細分析 fun7:

<+0>: sub $0x8,%rsp # 指針為空返回 -1<+4>: test %rdi,%rdi<+7>: je 0x401238 <fun7+52> # 輸入的數字和當前節點數字比較<+9>: mov (%rdi),%edx<+11>: cmp %esi,%edx<+13>: jle 0x401220 <fun7+28> # 當前節點數字 大於 輸入的數字 # 取左指針繼續遞歸 fun7<+15>: mov 0x8(%rdi),%rdi<+19>: callq 0x401204 <fun7> # 設上方返回值為 x # return x + x <+24>: add %eax,%eax<+26>: jmp 0x40123d <fun7+57> # 如果輸入的數字和當前節點數字 相等 # return 0<+28>: mov $0x0,%eax<+33>: cmp %esi,%edx<+35>: je 0x40123d <fun7+57> # 當前節點數字 小於 輸入的數字 # 取右指針繼續遞歸 fun7<+37>: mov 0x10(%rdi),%rdi<+41>: callq 0x401204 <fun7> # 設上方的返回值為 x # x = x + x + 1 # return x<+46>: lea 0x1(%rax,%rax,1),%eax<+50>: jmp 0x40123d <fun7+57> # return -1<+52>: mov $0xffffffff,%eax<+57>: add $0x8,%rsp<+61>: retq

那麼答案已經可以得到了:

22Wow! Youve defused the secret stage!

推薦閱讀:

CS:APP配套實驗4:Cache Lab筆記
關於CSAPP這本神書
如何取得32位無符號數二進位表示是否含有奇數個1?
請問popl %esp這個語句有什麼用處?
CS:APP配套實驗3:Attack Lab筆記

TAG:CSAPP | 操作系統 | 計算機科學 |