CSAPP Lab -- Bomb Lab

csapp.cs.cmu.edu

這個實驗是通過反彙編一個可執行文件，分析彙編代碼來找到六個炸彈的密碼。完成實驗需要熟悉一些比較基礎的彙編知識，掌握GDB的使用。然後就只需要耐心讀彙編，通過GDB查看有用信息，就可以完成這個lab了。

關於GDB，可以參考這個教程。另外，還需要使用objdump -d ./bomb >> bomb.s反彙編工具來得到彙編代碼。

開始

首先定位到main函數對應的機器代碼。分析這段代碼，可以看到前面都是和bomb.c中main()函數對應的。

main開頭是一個if分支語句，機器代碼對應的就是cmp和jmp。繼續分析:

else { printf("Usage: %s [<input_file>]
", argv[0]); exit(8);}

我們會發現對應於這個else部分的機器代碼是這樣的:

400df8: 48 8b 16 mov (%rsi),%rdx 400dfb: be d3 22 40 00 mov $0x4022d3,%esi 400e00: bf 01 00 00 00 mov $0x1,%edi 400e05: b8 00 00 00 00 mov $0x0,%eax 400e0a: e8 f1 fd ff ff callq 400c00 <__printf_chk@plt> 400e0f: bf 08 00 00 00 mov $0x8,%edi 400e14: e8 07 fe ff ff callq 400c20 <exit@plt>

字元串常量會存放在代碼的靜態內存區，所以我們一般都會用一個指針來引用這個字元串常量。所以，只要我們知道了這個地址，就能夠用gdb來print得到這個字元串常量。我們可以在這裡驗證一下，觀察這段機器代碼，可以確定mov $0x4022d3,%esi是在調用printf("Usage: %s [<input_file>]
", argv[0]);這行代碼時用到的。

gdb調試:

(gdb) p (char*)0x4022d3$2 = 0x4022d3 "Usage: %s [<input_file>]
"

結果驗證了這個想法是正確的，所以我們可以利用這個思路來進行接下來的lab。

bomb 1

通過閱讀代碼，找到bomb1對應的函數:

0000000000400ee0 <phase_1>: 400ee0: 48 83 ec 08 sub $0x8,%rsp 400ee4: be 00 24 40 00 mov $0x402400,%esi 400ee9: e8 4a 04 00 00 callq 401338 <strings_not_equal> 400eee: 85 c0 test %eax,%eax 400ef0: 74 05 je 400ef7 <phase_1+0x17> 400ef2: e8 43 05 00 00 callq 40143a <explode_bomb> 400ef7: 48 83 c4 08 add $0x8,%rsp 400efb: c3 retq

根據我們上面的思路，很容易發現這裡把0x402400載入進了%esi作為函數參數，然後調用了string_not_equal函數。所以，那個地址想必就是bomb1的key了。

GDB調試:

(gdb) print (char*)0x402400$4 = 0x402400 "Border relations with Canada have never been better."

輕易找到答案，熱身完畢。

bomb 2

0000000000400efc <phase_2>: 400efc: 55 push %rbp 400efd: 53 push %rbx 400efe: 48 83 ec 28 sub $0x28,%rsp 400f02: 48 89 e6 mov %rsp,%rsi 400f05: e8 52 05 00 00 callq 40145c <read_six_numbers> 400f0a: 83 3c 24 01 cmpl $0x1,(%rsp) 400f0e: 74 20 je 400f30 <phase_2+0x34> 400f10: e8 25 05 00 00 callq 40143a <explode_bomb> 400f15: eb 19 jmp 400f30 <phase_2+0x34> 400f17: 8b 43 fc mov -0x4(%rbx),%eax 400f1a: 01 c0 add %eax,%eax 400f1c: 39 03 cmp %eax,(%rbx) 400f1e: 74 05 je 400f25 <phase_2+0x29> 400f20: e8 15 05 00 00 callq 40143a <explode_bomb> 400f25: 48 83 c3 04 add $0x4,%rbx 400f29: 48 39 eb cmp %rbp,%rbx 400f2c: 75 e9 jne 400f17 <phase_2+0x1b> 400f2e: eb 0c jmp 400f3c <phase_2+0x40> 400f30: 48 8d 5c 24 04 lea 0x4(%rsp),%rbx 400f35: 48 8d 6c 24 18 lea 0x18(%rsp),%rbp 400f3a: eb db jmp 400f17 <phase_2+0x1b> 400f3c: 48 83 c4 28 add $0x28,%rsp 400f40: 5b pop %rbx 400f41: 5d pop %rbp 400f42: c3 retq

找到phase_2，看到開始是用sub $0x28, %rsp分配了一個40bytes的棧空間，然後調用了函數read_six_numbers，根據這個函數的名字，猜想應該是從輸入讀取六個數字。

為了驗證猜想，找到read_six_numbers，發現其中有一行callq 400bf0 <__isoc99_sscanf@plt>調用來庫函數sscanf。並且，利用我們前面的技巧，列印出$0x4025c3地址的字元串：

(gdb) print (char*)0x4025c3$3 = 0x4025c3 "%d %d %d %d %d %d"

可以確定，phase_2是調用了read_six_numbers來讀取六個數字。因此，我們只需要找出這六個數，就可以拆除炸彈了。

繼續分析phase_2:

400f0a: 83 3c 24 01 cmpl $0x1,(%rsp)400f0e: 74 20 je 400f30 <phase_2+0x34>400f10: e8 25 05 00 00 callq 40143a <explode_bomb>

這裡比較了處於棧頂的數和$0x1，如果不相等就會explode，所以確定第一個數就是1。再根據je跳轉，發現這裡將%rsp+0x4和%rsp+0x18對應的值存入了寄存器，然後跳轉到400f17，而這裡將%rbx-4指向的數放入%eax後，對其乘以2再和%rbx對應的數進行比較，如果不相等就會引爆炸彈，否則就是一個循環。

至此，我們可以確定這裡是一個循環，並且每次都是將%rbx-4對應的值乘以2和%rbx對應的值進行比較，也就是說，每次都是將棧中前一個數的兩倍和後一個數比較。因此，可以確定這六個數是一個等比數列，並且第一個數是1。

所以，bomb2的key就是: 1 2 4 8 16 32

bomb 3

0000000000400f43 <phase_3>: 400f43: 48 83 ec 18 sub $0x18,%rsp 400f47: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 400f4c: 48 8d 54 24 08 lea 0x8(%rsp),%rdx 400f51: be cf 25 40 00 mov $0x4025cf,%esi 400f56: b8 00 00 00 00 mov $0x0,%eax 400f5b: e8 90 fc ff ff callq 400bf0 <__isoc99_sscanf@plt> 400f60: 83 f8 01 cmp $0x1,%eax 400f63: 7f 05 jg 400f6a <phase_3+0x27> 400f65: e8 d0 04 00 00 callq 40143a <explode_bomb> 400f6a: 83 7c 24 08 07 cmpl $0x7,0x8(%rsp) 400f6f: 77 3c ja 400fad <phase_3+0x6a> 400f71: 8b 44 24 08 mov 0x8(%rsp),%eax 400f75: ff 24 c5 70 24 40 00 jmpq *0x402470(,%rax,8) 400f7c: b8 cf 00 00 00 mov $0xcf,%eax 400f81: eb 3b jmp 400fbe <phase_3+0x7b> 400f83: b8 c3 02 00 00 mov $0x2c3,%eax 400f88: eb 34 jmp 400fbe <phase_3+0x7b> 400f8a: b8 00 01 00 00 mov $0x100,%eax 400f8f: eb 2d jmp 400fbe <phase_3+0x7b> 400f91: b8 85 01 00 00 mov $0x185,%eax 400f96: eb 26 jmp 400fbe <phase_3+0x7b> 400f98: b8 ce 00 00 00 mov $0xce,%eax 400f9d: eb 1f jmp 400fbe <phase_3+0x7b> 400f9f: b8 aa 02 00 00 mov $0x2aa,%eax 400fa4: eb 18 jmp 400fbe <phase_3+0x7b> 400fa6: b8 47 01 00 00 mov $0x147,%eax 400fab: eb 11 jmp 400fbe <phase_3+0x7b> 400fad: e8 88 04 00 00 callq 40143a <explode_bomb> 400fb2: b8 00 00 00 00 mov $0x0,%eax 400fb7: eb 05 jmp 400fbe <phase_3+0x7b> 400fb9: b8 37 01 00 00 mov $0x137,%eax 400fbe: 3b 44 24 0c cmp 0xc(%rsp),%eax 400fc2: 74 05 je 400fc9 <phase_3+0x86> 400fc4: e8 71 04 00 00 callq 40143a <explode_bomb> 400fc9: 48 83 c4 18 add $0x18,%rsp 400fcd: c3 retq

開始調用了sscanf，按照我們之前的經驗，可以用GDB調試器查看調用的參數，也就是數據輸入的格式，根據mov $0x4025cf,%esi:

(gdb) print (char*)0x4025cf$1 = 0x4025cf "%d %d"

可以得知我們輸入的應該是兩個整數，然後再繼續下面的分析。先是%rax只有大於1，才不會爆炸。然後比較(%rsp+8)對應的值和0x7的大小關係，如果大於7就會爆炸，然後jmpq *0x402470(,%rax,8)進行跳轉。這樣的結構就是switch的特徵！然後再結合後面的若干mov和jmp，可以斷定這是一個switch結構，並且每次跳轉後，都會比較一個常數和%eax中的值，如果相等就會結束，否則會爆炸。

所以，我們推斷，輸入的兩個數中的第一個數應該是索引，然後第二個數就是索引對應的case中的數。

那麼，我們假設查找第二個case，也就是jump table的address+8對應的那個case:

(gdb) print *(0x402470 + 0x8)$2 = 4198329

如我們所料，會得到一個地址，然後轉換成十六進位就是400fb9，而這個對應的就是:

400fb9: b8 37 01 00 00 mov $0x137,%eax。所以，答案中的第二個數應該就是0x137！轉換成十進位就是311。

於是，我們得到了其中的一個答案就是: 1 311。

當然，還有其他的case都能夠正確地通，如2 707等。

bomb 4

000000000040100c <phase_4>: 40100c: 48 83 ec 18 sub $0x18,%rsp 401010: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 401015: 48 8d 54 24 08 lea 0x8(%rsp),%rdx 40101a: be cf 25 40 00 mov $0x4025cf,%esi 40101f: b8 00 00 00 00 mov $0x0,%eax 401024: e8 c7 fb ff ff callq 400bf0 <__isoc99_sscanf@plt> 401029: 83 f8 02 cmp $0x2,%eax 40102c: 75 07 jne 401035 <phase_4+0x29> 40102e: 83 7c 24 08 0e cmpl $0xe,0x8(%rsp) 401033: 76 05 jbe 40103a <phase_4+0x2e> 401035: e8 00 04 00 00 callq 40143a <explode_bomb> 40103a: ba 0e 00 00 00 mov $0xe,%edx 40103f: be 00 00 00 00 mov $0x0,%esi 401044: 8b 7c 24 08 mov 0x8(%rsp),%edi 401048: e8 81 ff ff ff callq 400fce <func4> 40104d: 85 c0 test %eax,%eax 40104f: 75 07 jne 401058 <phase_4+0x4c> 401051: 83 7c 24 0c 00 cmpl $0x0,0xc(%rsp) 401056: 74 05 je 40105d <phase_4+0x51> 401058: e8 dd 03 00 00 callq 40143a <explode_bomb> 40105d: 48 83 c4 18 add $0x18,%rsp 401061: c3 retq

還是之前的套路，分析輸入的應該是兩個整數。然後，phase_4部分其實很簡單，就是讀取輸入的兩個數。然後第一個數作為參數(存入%edi，並且第一個參數小於等於14)，另外0xe和0x0作為第二個和第三個參數來調用函數func4。調用結束後，返回值(%eax)應該是0。根據cmpl $0x0,0xc(%rsp)可知，第二個輸入的數字也應該為0。

接下來，分析函數func4。由前面的分析，這個函數應該有三個參數，接下來只需要給每個寄存器一個名字，然後將彙編代碼轉換成邏輯圖就行了:

設定: %edi -- a, %ecx -- b, %esi -- c, %edx -- d, %eax -- rr = d - cb = (d - c) >> 31r = (r + b) => r = d < c ? (d - c + 1) : (d - c)r >>= 1b = r + cif b <= a: r = 0 if b >= a: return r else: r = func4(a, c, d) return 2*r+1else: r = func4(a, c, b-1) return 2*r

再簡化一下：

def func(a, c, d): b = d < c ? (d+c+1)/2 : (d+c)/2 if b < a: return func(a, b+d, d)*2 + 1 else if b > a: return func(a, c, b-1)*2 else: return 0

根據這個邏輯，如果函數返回值為0，則是b == a的情況，而上面分析到了另外兩個參數c = 0, d = 14，所以此時a = b = (d+c)/2 = 7。

所以，輸入的第一個數應該是7!輸入的第二個數應該是0!

bomb 5

40107a: e8 9c 02 00 00 callq 40131b <string_length> 40107f: 83 f8 06 cmp $0x6,%eax

分析這部分，調用了string_length函數，並且要求返回值為6，所以輸入的應該是一個字元串，而且長度為6。

4010ae: c6 44 24 16 00 movb $0x0,0x16(%rsp) 4010b3: be 5e 24 40 00 mov $0x40245e,%esi 4010b8: 48 8d 7c 24 10 lea 0x10(%rsp),%rdi 4010bd: e8 76 02 00 00 callq 401338 <strings_not_equal> 4010c2: 85 c0 test %eax,%eax 4010c4: 74 13 je 4010d9 <phase_5+0x77>

這裡分別以(%rsp+0x10到%rsp+0x16)的字元串和地址0x40245e的字元串作為參數，調用了函數string_not_equal。根據這段可以肯定，我們需要輸入長度為6的字元串來和存放在地址0x40245e的字元串來進行比較，如果不同，就會Bomb。用GDB可以得到這個字元串是"flyers":

(gdb) print (char*)0x40245e$1 = 0x40245e "flyers"

所以，現在我們的目的就很明確了，如果得到"flyers"。再分析這段:

40108b: 0f b6 0c 03 movzbl (%rbx,%rax,1),%ecx 40108f: 88 0c 24 mov %cl,(%rsp) 401092: 48 8b 14 24 mov (%rsp),%rdx 401096: 83 e2 0f and $0xf,%edx 401099: 0f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx 4010a0: 88 54 04 10 mov %dl,0x10(%rsp,%rax,1) 4010a4: 48 83 c0 01 add $0x1,%rax 4010a8: 48 83 f8 06 cmp $0x6,%rax 4010ac: 75 dd jne 40108b <phase_5+0x29>

在跳轉到這段之前，%eax已經被設置為0。顯而易見，這裡是一個循環，循環條件為%rax != 0x6。所以，這裡就是循環六次，每次都向棧中寫入了一個字元，最後得到的就是"flyers"。但是，這些字元都是怎樣產生的呢？

這裡可以看到，都是從0x4024b0(%rdx),%edx得來的字元，用GDB調試發現:

(gdb) print (char*)0x4024b0$2 = 0x4024b0 <array> "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

這是一條更長的字元串，並且包括了"flyers"的所有字元，所以推測是從這個長字元串取出的字元。而這驗證了我們的猜想:

40108b: 0f b6 0c 03 movzbl (%rbx,%rax,1),%ecx 40108f: 88 0c 24 mov %cl,(%rsp) 401092: 48 8b 14 24 mov (%rsp),%rdx 401096: 83 e2 0f and $0xf,%edx

%rbx存放的是我們輸入的字元串的地址，然後%rax是索引，每次從我們輸入的字元串取出一個字元後，都會對其進行截斷，只取最低4位存放在%edx中，然後這個%edx被用做了從長字元串取字元的索引。

現在我們明白了，就是我們輸入的每個字元，都會取最低4位，然後轉換成數字來作為長字元串 "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"的索引，最後依次取出的字元就是"flyers"！

所以，找出"flyers"在長字元串中的索引分別是:9, 15, 14, 5, 6, 7。為了湊成字元，對每個加上64恰好都是大寫字母的ascii碼:73, 79, 78, 69, 70, 71。

答案就是： IONEFG

bomb 6

4010f4: 41 56 push %r144010f6: 41 55 push %r134010f8: 41 54 push %r124010fa: 55 push %rbp4010fb: 53 push %rbx4010fc: 48 83 ec 50 sub $0x50,%rsp401100: 49 89 e5 mov %rsp,%r13401103: 48 89 e6 mov %rsp,%rsi401106: e8 51 03 00 00 callq 40145c <read_six_numbers>40110b: 49 89 e6 mov %rsp,%r1440110e: 41 bc 00 00 00 00 mov $0x0,%r12d401114: 4c 89 ed mov %r13,%rbp401117: 41 8b 45 00 mov 0x0(%r13),%eax40111b: 83 e8 01 sub $0x1,%eax40111e: 83 f8 05 cmp $0x5,%eax401121: 76 05 jbe 401128 <phase_6+0x34>401123: e8 12 03 00 00 callq 40143a <explode_bomb>

這裡又是用到了前面的read_six_number，所以我們的任務就是尋找6個數。開頭這一部分代碼的意思就是，必須每個數都要小於等於6。

401132: 44 89 e3 mov %r12d,%ebx401135: 48 63 c3 movslq %ebx,%rax401138: 8b 04 84 mov (%rsp,%rax,4),%eax40113b: 39 45 00 cmp %eax,0x0(%rbp)40113e: 75 05 jne 401145 <phase_6+0x51>401140: e8 f5 02 00 00 callq 40143a <explode_bomb>401145: 83 c3 01 add $0x1,%ebx401148: 83 fb 05 cmp $0x5,%ebx40114b: 7e e8 jle 401135 <phase_6+0x41>40114d: 49 83 c5 04 add $0x4,%r13401151: eb c1 jmp 401114 <phase_6+0x20>401153: 48 8d 74 24 18 lea 0x18(%rsp),%rsi401158: 4c 89 f0 mov %r14,%rax40115b: b9 07 00 00 00 mov $0x7,%ecx401160: 89 ca mov %ecx,%edx401162: 2b 10 sub (%rax),%edx401164: 89 10 mov %edx,(%rax)401166: 48 83 c0 04 add $0x4,%rax40116a: 48 39 f0 cmp %rsi,%rax40116d: 75 f1 jne 401160 <phase_6+0x6c>

首先，第一個元素被放在0x(%rbp)中，然後通過增加%ebx的值，循環了五次，也就是把數組後面的五個元素都和第一個元素進行比較，如果相同，就會觸發炸彈。然後，同樣有是一個循環，用來判斷後面的元素依次不同。所以，這個部分就是用來判定每個數都是不同的。另外，對於棧中那六個數，每個數x，都被改成了7-x。

後面這部分就很複雜，剛開始一直沒有看懂。然後發現有一個地址0x6032d0有被用到，所以用GDB列印它的內容可以發現:

(gdb) x 0x6033200x603320 <node6>: 0x000001bb

再結合mov 0x8(%rdx),%rdx可以想到，這個應該是一個鏈表的結構，所以我們再列印出這個地址附近的信息:

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

然後再分析代碼，會發現把我們輸入的數處理後，將其作為鏈表的索引，讀取數據存放在棧中，然後又串連成了鏈表。

4011da: bd 05 00 00 00 mov $0x5,%ebp4011df: 48 8b 43 08 mov 0x8(%rbx),%rax4011e3: 8b 00 mov (%rax),%eax4011e5: 39 03 cmp %eax,(%rbx)4011e7: 7d 05 jge 4011ee <phase_6+0xfa>4011e9: e8 4c 02 00 00 callq 40143a <explode_bomb>4011ee: 48 8b 5b 08 mov 0x8(%rbx),%rbx4011f2: 83 ed 01 sub $0x1,%ebp4011f5: 75 e8 jne 4011df <phase_6+0xeb>

這裡遍歷鏈表，要求鏈表的順序是升序。所以，我們可以根據GDB列印出來的每一個結點的值，來找到數據的排列順序為:3 4 5 6 1 2。然後，7-x後: 4 3 2 1 6 5。

最後，還有隱藏關卡，但是天已經亮了，無力再戰。。