date: 2020-05-04
本實(shí)驗(yàn)中博主采用對(duì) objdump -D 令生成的文本進(jìn)行分析求解（需要有基本的匯編知識(shí)曙砂，了解各種指令以及棧幀結(jié)構(gòu)骆莹，之后的討論中不會(huì)對(duì)此進(jìn)行介紹），gdb 調(diào)試僅在求解 secret_phase 時(shí)使用。
博主的部分?jǐn)?shù)據(jù)有進(jìn)行改動(dòng)酸休，故答案與官網(wǎng)的不同乞巧，但解法相同口蝠，可作參考學(xué)習(xí)器钟。
- 實(shí)驗(yàn)環(huán)境：Windows10 系統(tǒng)下 VMware 虛擬機(jī) Ubuntu12.04 桌面版 32 位
- 原址鏈接：http://csapp.cs.cmu.edu/3e/labs.html
phase_1
phase_1的主體是一個(gè)簡(jiǎn)單的函數(shù)調(diào)用
block 1
08048b50 <phase_1>:
8048b50: 83 ec 1c sub $0x1c,%esp
; strings_not_equal(char*, "I was trying to give Tina Fey more material.")
8048b53: c7 44 24 04 64 a2 04 movl $0x804a264,0x4(%esp)
8048b5a: 08
8048b5b: 8b 44 24 20 mov 0x20(%esp),%eax; %eax = input
8048b5f: 89 04 24 mov %eax,(%esp); %eax = input
8048b62: e8 2d 05 00 00 call 8049094 <strings_not_equal>
首先調(diào)用 strings_not_equal 函數(shù)，分析 %esp 可以了解到它有兩個(gè)參數(shù)妙蔗。第一個(gè)參數(shù)是 phase_1 傳入的字符串傲霸，第二個(gè)參數(shù)是應(yīng)該是一個(gè)字面值，存儲(chǔ)在內(nèi)存中的 0x804a264 處眉反，如下：
804a261: 65 2e 00 49 20 gs add %cl,%cs:%gs:0x20(%ecx)
804a266: 77 61 ja 804a2c9 <_IO_stdin_used+0x1a5>
804a268: 73 20 jae 804a28a <_IO_stdin_used+0x166>
804a26a: 74 72 je 804a2de <_IO_stdin_used+0x1ba>
804a26c: 79 69 jns 804a2d7 <_IO_stdin_used+0x1b3>
804a26e: 6e outsb %ds:(%esi),(%dx)
804a26f: 67 20 74 6f and %dh,0x6f(%si)
804a273: 20 67 69 and %ah,0x69(%edi)
804a276: 76 65 jbe 804a2dd <_IO_stdin_used+0x1b9>
804a278: 20 54 69 6e and %dl,0x6e(%ecx,%ebp,2)
804a27c: 61 popa
804a27d: 20 46 65 and %al,0x65(%esi)
804a280: 79 20 jns 804a2a2 <_IO_stdin_used+0x17e>
804a282: 6d insl (%dx),%es:(%edi)
804a283: 6f outsl %ds:(%esi),(%dx)
804a284: 72 65 jb 804a2eb <_IO_stdin_used+0x1c7>
804a286: 20 6d 61 and %ch,0x61(%ebp)
804a289: 74 65 je 804a2f0 <_IO_stdin_used+0x1cc>
804a28b: 72 69 jb 804a2f6 <_IO_stdin_used+0x1d2>
804a28d: 61 popa
804a28e: 6c insb (%dx),%es:(%edi)
804a28f: 2e 00 00 add %al,%cs:(%eax)
轉(zhuǎn)換一下就能得到字符串 "I was trying to give Tina Fey more material."昙啄。
block 2
; if (strings_not_equal(/**/))
8048b67: 85 c0 test %eax,%eax
8048b69: 74 05 je 8048b70 <phase_1+0x20>
; explode_bomb()
8048b6b: e8 36 06 00 00 call 80491a6 <explode_bomb>
8048b70: 83 c4 1c add $0x1c,%esp
8048b73: c3 ret
第二塊判斷 strings_not_equal 的返回值，若 true 則 explode_bomb禁漓，若 false 則 return 說(shuō)明 phase_1 的答案為 "I was trying to give Tina Fey more material."跟衅。
code
以下是根據(jù)匯編指令還原的代碼（功能相同，但代碼不一定完全相同）：
int string_length(char* str)
{
int count = 0;
while (str[count])
++count;
}
int strings_not_equal(char* str1, char* str2)
{
int len1 = string_length(str1), len2 = string_length(str2), i;
if (len1 != len2)
return 0;
for (i = 0; i < len1; ++i)
if (str1[i] != str2[i])
return 0;
return 1;
}
void phase_1(char* str)
{
if (!strings_not_equal(str, "I was trying to give Tina Fey more material."))
explode_bomb();
}
phase_2
phase_2的主體是一個(gè)簡(jiǎn)單的for循環(huán)
block 1
08048b74 <phase_2>:
8048b74: 56 push %esi
8048b75: 53 push %ebx
8048b76: 83 ec 34 sub $0x34,%esp
; read_six_numbers(char* str, unsigned arr[])
8048b79: 8d 44 24 18 lea 0x18(%esp),%eax; %eax = arr
8048b7d: 89 44 24 04 mov %eax,0x4(%esp); 0x4(%esp) = arr
8048b81: 8b 44 24 40 mov 0x40(%esp),%eax; %eax = str = input
8048b85: 89 04 24 mov %eax,(%esp); (%esp) = str
8048b88: e8 4e 07 00 00 call 80492db <read_six_numbers>
首先調(diào)用 read_six_numbers 函數(shù)播歼，分析 %esp 可以了解到它有兩個(gè)參數(shù)伶跷，第一個(gè)參數(shù)是 phase_2 傳入的字符串，第二個(gè)參數(shù)在此處暫時(shí)無(wú)法確定（暫且記作數(shù)組 arr ）秘狞，但肯定是用于存放至少 6 個(gè)整數(shù)的叭莫。
block 2
; if (arr[0] != 1)
8048b8d: 83 7c 24 18 01 cmpl $0x1,0x18(%esp)
8048b92: 74 05 je 8048b99 <phase_2+0x25>
; explode_bomb()
8048b94: e8 0d 06 00 00 call 80491a6 <explode_bomb>
第二塊判斷第一個(gè)整數(shù)是否為 1，若 false 則 explode_bomb烁试。
block 3
; for (p = arr + 1; p != arr + 6; p++)
8048b99: 8d 5c 24 1c lea 0x1c(%esp),%ebx; %ebx = arr + 1
8048b9d: 8d 74 24 30 lea 0x30(%esp),%esi; %esi = arr + 6
; if (*(p - 1) + *(p - 1) != *p)
8048ba1: 8b 43 fc mov -0x4(%ebx),%eax; %eax = *(p - 1)
8048ba4: 01 c0 add %eax,%eax; %eax = *(p - 1) + *(p - 1)
8048ba6: 39 03 cmp %eax,(%ebx)
8048ba8: 74 05 je 8048baf <phase_2+0x3b>
; explode_bomb()
8048baa: e8 f7 05 00 00 call 80491a6 <explode_bomb>
8048baf: 83 c3 04 add $0x4,%ebx
8048bb2: 39 f3 cmp %esi,%ebx
8048bb4: 75 eb jne 8048ba1 <phase_2+0x2d>
; loop for
8048bb6: 83 c4 34 add $0x34,%esp
8048bb9: 5b pop %ebx
8048bba: 5e pop %esi
8048bbb: c3 ret
- 第三塊首先將
0x1c(%esp)和0x30(%esp)分別存入了%ebx和%esi雇初。0x1c(%esp)是arr[1]的地址，0x30(%esp)是arr[6]的地址 - 之后比較地址
%ebx - 4中的值與地址%ebx中的值（即比較arr[i]與arr[i-1]）减响，若arr[i-1] + arr[i-1] != arr[i]則explode_bomb - 最后進(jìn)行迭代循環(huán)靖诗，結(jié)束之后
return
總體分析，則第三塊代碼實(shí)現(xiàn)的功能就是判斷 arr 中后一個(gè)元素是否是前一個(gè)元素的兩倍支示，同時(shí)第二塊代碼中保證了 arr[0] 為 1刊橘，所以可以得出答案為 1 2 4 8 16 32。
code
arr 為何是 unsigned 而不是 int 在之后的 phase 中會(huì)得到體現(xiàn)颂鸿。
void read_six_numbers(char* str, unsigned arr[])
{
if (sscanf(str, "%d %d %d %d %d %d", arr, arr + 1, arr + 2, arr + 3, arr + 4, arr + 5) <= 5)
explode_bomb();
}
void phase_2(char* str)
{
unsigned arr[6];
int* p;
read_six_numbers(str, arr);
if (arr[0] != 1)
explode_bomb();
for (p = arr + 1; p != arr + 6; p++)
if (*(p - 1) + *(p - 1) != *p)
explode_bomb();
}
phase_3
phase_3的主體是一個(gè)switch...case結(jié)構(gòu)
block 1
08048bbc <phase_3>:
8048bbc: 83 ec 3c sub $0x3c,%esp
; sscanf(char* str, "%d %c %d", unsigned* pvar1, char* pvar2, int* pvar3)
8048bbf: 8d 44 24 28 lea 0x28(%esp),%eax; %eax = &var3
8048bc3: 89 44 24 10 mov %eax,0x10(%esp); pvar3 = &var3
8048bc7: 8d 44 24 2f lea 0x2f(%esp),%eax; %eax = &var2
8048bcb: 89 44 24 0c mov %eax,0xc(%esp); pvar2 = &var2
8048bcf: 8d 44 24 24 lea 0x24(%esp),%eax; %eax = &var1
8048bd3: 89 44 24 08 mov %eax,0x8(%esp); pvar1 = &var1
8048bd7: c7 44 24 04 ba a2 04 movl $0x804a2ba,0x4(%esp); "%d %c %d"
8048bde: 08
8048bdf: 8b 44 24 40 mov 0x40(%esp),%eax
8048be3: 89 04 24 mov %eax,(%esp)
8048be6: e8 85 fc ff ff call 8048870 <__isoc99_sscanf@plt>
; if (sscanf(/**/) <= 2)
8048beb: 83 f8 02 cmp $0x2,%eax
8048bee: 7f 05 jg 8048bf5 <phase_3+0x39>
; explode_bomb()
8048bf0: e8 b1 05 00 00 call 80491a6 <explode_bomb>
第一塊調(diào)用 sscanf 函數(shù)促绵，傳入 5 個(gè)參數(shù)，分別是：
-
char*:phase_3的參數(shù) -
char*:"%d %c %d" -
unsigned:var1 -
char:var2 -
int:var3
讀取完之后檢查讀取成功的個(gè)數(shù)嘴纺，說(shuō)明 phase_3 應(yīng)當(dāng)輸入 2 個(gè)整數(shù)和 1 個(gè)字符败晴。
之后的代碼中分析可得第三個(gè)參數(shù)必須為 unsigned
block 2
; if (var1 <= 7)
8048bf5: 83 7c 24 24 07 cmpl $0x7,0x24(%esp)
8048bfa: 0f 87 f9 00 00 00 ja 8048cf9 <phase_3+0x13d>
; switch (var1)
8048c00: 8b 44 24 24 mov 0x24(%esp),%eax; %eax = var1
8048c04: ff 24 85 e0 a2 04 08 jmp *0x804a2e0(,%eax,4); *(0x08048c0b + 4 * var1)
; case 0
; if (var3 != 488)
8048c0b: b8 75 00 00 00 mov $0x75,%eax; %eax = 'u'
8048c10: 81 7c 24 28 e8 01 00 cmpl $0x1e8,0x28(%esp)
8048c17: 00
8048c18: 0f 84 e5 00 00 00 je 8048d03 <phase_3+0x147>
8048c1e: e8 83 05 00 00 call 80491a6 <explode_bomb>
8048c23: b8 75 00 00 00 mov $0x75,%eax; %eax = 'u'
8048c28: e9 d6 00 00 00 jmp 8048d03 <phase_3+0x147>
; case 1
; if (var3 != 341)
8048c2d: b8 78 00 00 00 mov $0x78,%eax; %eax = 'x'
8048c32: 81 7c 24 28 55 01 00 cmpl $0x155,0x28(%esp)
8048c39: 00
8048c3a: 0f 84 c3 00 00 00 je 8048d03 <phase_3+0x147>
8048c40: e8 61 05 00 00 call 80491a6 <explode_bomb>
8048c45: b8 78 00 00 00 mov $0x78,%eax; %eax = 'x'
8048c4a: e9 b4 00 00 00 jmp 8048d03 <phase_3+0x147>
; case 2
; if (var3 != 868)
8048c4f: b8 70 00 00 00 mov $0x70,%eax; %eax = 'p'
8048c54: 81 7c 24 28 64 03 00 cmpl $0x364,0x28(%esp)
8048c5b: 00
8048c5c: 0f 84 a1 00 00 00 je 8048d03 <phase_3+0x147>
8048c62: e8 3f 05 00 00 call 80491a6 <explode_bomb>
8048c67: b8 70 00 00 00 mov $0x70,%eax; %eax = 'p'
8048c6c: e9 92 00 00 00 jmp 8048d03 <phase_3+0x147>
; case 3
; if (var3 != 103)
8048c71: b8 62 00 00 00 mov $0x62,%eax; %eax = 'b'
8048c76: 83 7c 24 28 67 cmpl $0x67,0x28(%esp)
8048c7b: 0f 84 82 00 00 00 je 8048d03 <phase_3+0x147>
8048c81: e8 20 05 00 00 call 80491a6 <explode_bomb>
8048c86: b8 62 00 00 00 mov $0x62,%eax; %eax = 'b'
8048c8b: eb 76 jmp 8048d03 <phase_3+0x147>
; case 4
; if (var3 != 805)
8048c8d: b8 63 00 00 00 mov $0x63,%eax; %eax = 'c'
8048c92: 81 7c 24 28 25 03 00 cmpl $0x325,0x28(%esp)
8048c99: 00
8048c9a: 74 67 je 8048d03 <phase_3+0x147>
8048c9c: e8 05 05 00 00 call 80491a6 <explode_bomb>
8048ca1: b8 63 00 00 00 mov $0x63,%eax; %eax = 'c'
8048ca6: eb 5b jmp 8048d03 <phase_3+0x147>
; case 5
; if (var3 != 968)
8048ca8: b8 70 00 00 00 mov $0x70,%eax; %eax = 'p'
8048cad: 81 7c 24 28 c8 03 00 cmpl $0x3c8,0x28(%esp)
8048cb4: 00
8048cb5: 74 4c je 8048d03 <phase_3+0x147>
8048cb7: e8 ea 04 00 00 call 80491a6 <explode_bomb>
8048cbc: b8 70 00 00 00 mov $0x70,%eax; %eax = 'p'
8048cc1: eb 40 jmp 8048d03 <phase_3+0x147>
; case 6
; if (var3 != 372)
8048cc3: b8 67 00 00 00 mov $0x67,%eax; %eax = 'g'
8048cc8: 81 7c 24 28 74 01 00 cmpl $0x174,0x28(%esp)
8048ccf: 00
8048cd0: 74 31 je 8048d03 <phase_3+0x147>
8048cd2: e8 cf 04 00 00 call 80491a6 <explode_bomb>
8048cd7: b8 67 00 00 00 mov $0x67,%eax; %eax = 'g'
8048cdc: eb 25 jmp 8048d03 <phase_3+0x147>
; case 7
; if (var3 != 633)
8048cde: b8 61 00 00 00 mov $0x61,%eax; %eax = 'a'
8048ce3: 81 7c 24 28 79 02 00 cmpl $0x279,0x28(%esp)
8048cea: 00
8048ceb: 74 16 je 8048d03 <phase_3+0x147>
8048ced: e8 b4 04 00 00 call 80491a6 <explode_bomb>
8048cf2: b8 61 00 00 00 mov $0x61,%eax; %eax = 'a'
8048cf7: eb 0a jmp 8048d03 <phase_3+0x147>
; explode_bomb()
8048cf9: e8 a8 04 00 00 call 80491a6 <explode_bomb>
8048cfe: b8 6a 00 00 00 mov $0x6a,%eax
第二塊有大量的重復(fù)指令，簡(jiǎn)單分析可得是一個(gè) switch...case 結(jié)構(gòu)栽渴。
首先保證 var1 不大于 7尖坤，之后根據(jù) var1 的值去內(nèi)存中取值進(jìn)行跳轉(zhuǎn)：
804a2df: 00 0b add %cl,(%ebx)
804a2e1: 8c 04 08 mov %es,(%eax,%ecx,1)
804a2e4: 2d 8c 04 08 4f sub $0x4f08048c,%eax
804a2e9: 8c 04 08 mov %es,(%eax,%ecx,1)
804a2ec: 71 8c jno 804a27a <_IO_stdin_used+0x156>
804a2ee: 04 08 add $0x8,%al
804a2f0: 8d 8c 04 08 a8 8c 04 lea 0x48ca808(%esp,%eax,1),%ecx
804a2f7: 08 c3 or %al,%bl
804a2f9: 8c 04 08 mov %es,(%eax,%ecx,1)
804a2fc: de 8c 04 08 0a 00 00 fimul 0xa08(%esp,%eax,1)
總共 8 種跳轉(zhuǎn)情況，要求 var1 的值必須為 0-7闲擦，但最開(kāi)始時(shí)只檢查了 var1 是否小于 7糖驴，而如果要保證程序能正常運(yùn)行僚祷，則需要滿足 var1 不能為負(fù)值，所以 var1 應(yīng)當(dāng)為 unsigned贮缕，以確保其值的范圍在 0-7。
由于各個(gè) case 的結(jié)構(gòu)相同俺榆，區(qū)別只有值感昼，故只分析 case 0：將字面值 75 ( 字符 'u' ) 存入 %eax，之后比較字面值 0x1e8 與 var3罐脊，若不相同則 explode_bomb定嗓，相同則 break。
所以我們輸入的第三個(gè)整數(shù)應(yīng)當(dāng)與第一個(gè)整數(shù)相關(guān)萍桌。
block 3
; if (var2 == %al)
8048d03: 3a 44 24 2f cmp 0x2f(%esp),%al
8048d07: 74 05 je 8048d0e <phase_3+0x152>
; explode_bomb()
8048d09: e8 98 04 00 00 call 80491a6 <explode_bomb>
8048d0e: 83 c4 3c add $0x3c,%esp
8048d11: c3 ret
比較 var2 與 block 3 中存入 %eax 的值宵溅，若不同則 explode_bomb，若相同則 return上炎，說(shuō)明輸入的字符應(yīng)當(dāng)與第一個(gè)整數(shù)相關(guān)恃逻。
總體分析，可以發(fā)現(xiàn)輸入的字符和第三個(gè)整數(shù)都與第一個(gè)整數(shù)相關(guān)藕施，根據(jù) var1 的不同可以有 7 種答案：{ "0 u 488", "1 x 341", "2 p 868", "3 b 103", "4 c 805", "5 p 968", "6 g 372", "7 a 633" }寇损。
code
如果寄存器夠用，則變量不會(huì)寫(xiě)入內(nèi)存裳食。
void phase_3(char* str)
{
unsigned var1;
int var3;
char var2, ans;
if (sscanf(str, "%d %c %d", &var1, &var2, &var3) <= 2)
explode_bomb();
switch (var1) {
case 0:
ans = 'u';
if (var3 != 488)
explode_bomb();
break;
case 1:
ans = 'x';
if (var3 != 341)
explode_bomb();
break;
case 2:
ans = 'p';
if (var3 != 868)
explode_bomb();
break;
case 3:
ans = 'b';
if (var3 != 103)
explode_bomb();
break;
case 4:
ans = 'c';
if (var3 != 805)
explode_bomb();
break;
case 5:
ans = 'p';
if (var3 != 968)
explode_bomb();
break;
case 6:
ans = 'g';
if (var3 != 372)
explode_bomb();
break;
case 7:
ans = 'a';
if (var3 != 633)
explode_bomb();
break;
default:
ans = 'j';
explode_bomb();
}
if (var2 != ans)
explode_bomb();
}
phase_4
phase_4的主體是一個(gè)遞歸函數(shù)func4的調(diào)用
block 1
08048d7f <phase_4>:
8048d7f: 83 ec 2c sub $0x2c,%esp
; sscanf(char* str, "%d %d", int* pvar1, int* pvar2)
8048d82: 8d 44 24 1c lea 0x1c(%esp),%eax; %eax = &var2
8048d86: 89 44 24 0c mov %eax,0xc(%esp); pvar1 = &var2
8048d8a: 8d 44 24 18 lea 0x18(%esp),%eax; %eax = &var1
8048d8e: 89 44 24 08 mov %eax,0x8(%esp); pvar2 = &var1
8048d92: c7 44 24 04 a3 a4 04 movl $0x804a4a3,0x4(%esp); "%d %d"
8048d99: 08
8048d9a: 8b 44 24 30 mov 0x30(%esp),%eax; %eax = str
8048d9e: 89 04 24 mov %eax,(%esp); (%esp) = str
8048da1: e8 ca fa ff ff call 8048870 <__isoc99_sscanf@plt>
第一塊是一個(gè)與 phase_3 中類(lèi)似的 sscanf矛市，相比之下只讀取了兩個(gè)整數(shù)。
block 2
; if (sscanf(/**/) == 2 && var1 >= 0 && var1 <= 14)
; if (sscanf(/**/) == 2)
8048da6: 83 f8 02 cmp $0x2,%eax
8048da9: 75 0d jne 8048db8 <phase_4+0x39>
; if (var1 >= 0)
8048dab: 8b 44 24 18 mov 0x18(%esp),%eax
8048daf: 85 c0 test %eax,%eax
8048db1: 78 05 js 8048db8 <phase_4+0x39>
; if (var1 <= 14)
8048db3: 83 f8 0e cmp $0xe,%eax
8048db6: 7e 05 jle 8048dbd <phase_4+0x3e>
; else
; explode_bomb()
8048db8: e8 e9 03 00 00 call 80491a6 <explode_bomb>
第二塊是對(duì) var1 的一個(gè)檢測(cè)诲祸，要求 var1 在范圍 0-14 之間浊吏。
block 3
; func4(var1 , 0, 14)
8048dbd: c7 44 24 08 0e 00 00 movl $0xe,0x8(%esp)
8048dc4: 00
8048dc5: c7 44 24 04 00 00 00 movl $0x0,0x4(%esp)
8048dcc: 00
8048dcd: 8b 44 24 18 mov 0x18(%esp),%eax
8048dd1: 89 04 24 mov %eax,(%esp)
8048dd4: e8 39 ff ff ff call 8048d12 <func4>
第三塊調(diào)用了函數(shù) func4，傳入了三個(gè)參數(shù)：
-
int: 變量var1 -
int: 字面值0 -
int: 字面值14
block 4
; if (func4(/**/) == 4 && var2 == 4)
; if (func4 == 4)
8048dd9: 83 f8 04 cmp $0x4,%eax
8048ddc: 75 07 jne 8048de5 <phase_4+0x66>
; if (var2 == 4)
8048dde: 83 7c 24 1c 04 cmpl $0x4,0x1c(%esp)
8048de3: 74 05 je 8048dea <phase_4+0x6b>
; explode_bomb()
8048de5: e8 bc 03 00 00 call 80491a6 <explode_bomb>
8048dea: 83 c4 2c add $0x2c,%esp
8048ded: c3 ret
第四塊是對(duì) func4 函數(shù)的返回值和變量 var2 的檢測(cè)救氯，要求兩者都為 4找田。
總體分析，phase_4 類(lèi)似 phase_1径密，主體是對(duì)一個(gè)函數(shù)的調(diào)用與返回值檢測(cè)午阵，但是 phase_4 中的函數(shù)是一個(gè)遞歸調(diào)用的函數(shù)，在下一節(jié)中我們具體分析 func4 這個(gè)遞歸函數(shù)享扔。
code
void phase_4(char* str)
{
int var1, var2;
if (sscanf(str, "%d %d", &var1, &var2) == 2 && var1 >= 0 && var1 <= 14)
if (func4(var1, 0, 14) == 4 && var2 == 4)
return;
explode_bomb();
}
func4
func4的主體是一個(gè)if...else分支結(jié)構(gòu)底桂，進(jìn)行遞歸調(diào)用的判斷
block 1
; func4(int var1, int var2, int var3)
08048d12 <func4>:
8048d12: 83 ec 1c sub $0x1c,%esp
; initial
8048d15: 89 5c 24 14 mov %ebx,0x14(%esp)
8048d19: 89 74 24 18 mov %esi,0x18(%esp)
8048d1d: 8b 54 24 20 mov 0x20(%esp),%edx; %edx = var1
8048d21: 8b 44 24 24 mov 0x24(%esp),%eax; %eax = var2
8048d25: 8b 5c 24 28 mov 0x28(%esp),%ebx; %ebx = var3
8048d29: 89 d9 mov %ebx,%ecx; %ecx = var3
第一塊是一個(gè)初始化，騰出了 %ebx 和 %esi 兩個(gè)寄存器惧眠，并將參數(shù)存入了寄存器籽懦。
block 2
; %ecx = (var3 - var2) / 2 + var2
8048d2b: 29 c1 sub %eax,%ecx; %ecx = var3 - var2
8048d2d: 89 ce mov %ecx,%esi; %esi = var3 - var2
8048d2f: c1 ee 1f shr $0x1f,%esi; %esi = (unsigned)(var3 - var2) >> 31
; %ecx = var3 - var2 + (unsigned)(var3 - var2) >> 31
8048d32: 01 f1 add %esi,%ecx
; %ecx = (int)(var3 - var2 + (unsigned)(var3 - var2) >> 31) >> 1
8048d34: d1 f9 sar %ecx
; %ecx = (int)(var3 - var2 + (unsigned)(var3 - var2) >> 31) >> 1 + var2
8048d36: 01 c1 add %eax,%ecx
第三塊是幾條運(yùn)算指令，逐步分析得到一個(gè)表達(dá)式 (int)(var3 - var2 + (unsigned)(var3 - var2) >> 31) >> 1 + var2氛魁，如果熟悉的話很快就能反應(yīng)過(guò)來(lái)前面的是一個(gè)除法暮顺，簡(jiǎn)化之后的表達(dá)式為 (var3 - var2) / 2 + var2厅篓，當(dāng)然可以進(jìn)一步簡(jiǎn)化為 (var2 + var3) / 2，運(yùn)算的結(jié)果都是相同的捶码。
block 3
; if ((var3 - var2) / 2 + var2 > var1)
8048d38: 39 d1 cmp %edx,%ecx
8048d3a: 7e 17 jle 8048d53 <func4+0x41>
; return func4(var1, var2, (var3 - var2) / 2 + var2 - 1) * 2
8048d3c: 83 e9 01 sub $0x1,%ecx; %ecx = (var3 - var2) / 2 + var2 - 1
8048d3f: 89 4c 24 08 mov %ecx,0x8(%esp); 0x8(%esp) = (var3 - var2) / 2 + var2 - 1
8048d43: 89 44 24 04 mov %eax,0x4(%esp); 0x4(%esp) = var2
8048d47: 89 14 24 mov %edx,(%esp); (%esp) = var1
8048d4a: e8 c3 ff ff ff call 8048d12 <func4>
8048d4f: 01 c0 add %eax,%eax; %eax = func4 * 2
8048d51: eb 20 jmp 8048d73 <func4+0x61>
; else
; return 0
8048d53: b8 00 00 00 00 mov $0x0,%eax; %eax = 0
; else if ((var3 - var2) / 2 + var2 < var1)
8048d58: 39 d1 cmp %edx,%ecx
8048d5a: 7d 17 jge 8048d73 <func4+0x61>
; return func4(var1, (var3 - var2) / 2 + var2 + 1, var3) * 2 + 1
8048d5c: 89 5c 24 08 mov %ebx,0x8(%esp); 0x8(%esp) = var3
8048d60: 83 c1 01 add $0x1,%ecx; %ecx = (var3 - var2) / 2 + var2 + 1
8048d63: 89 4c 24 04 mov %ecx,0x4(%esp); 0x4(%esp) = (var3 - var2) / 2 + var2 + 1
8048d67: 89 14 24 mov %edx,(%esp); (%esp) = var1
8048d6a: e8 a3 ff ff ff call 8048d12 <func4>
8048d6f: 8d 44 00 01 lea 0x1(%eax,%eax,1),%eax; %eax = func4 * 2 + 1
8048d73: 8b 5c 24 14 mov 0x14(%esp),%ebx
8048d77: 8b 74 24 18 mov 0x18(%esp),%esi
8048d7b: 83 c4 1c add $0x1c,%esp
8048d7e: c3 ret
第三塊是對(duì)遞歸調(diào)用的判斷羽氮，結(jié)構(gòu)并不復(fù)雜，很快就能分析出來(lái)惫恼，接下來(lái)要做的就是找合適的輸入使它的返回值為 4档押。
code
// int func4(int var1, int var2, int var3)
// {
// if ((var2 + var3) / 2 > var1)
// return func4(var1, var2, (var2 + var3) / 2 - 1) * 2;
// else if ((var2 + var3) / 2 < var1)
// return func4(var1, (var2 + var3) / 2 + 1, var3) * 2 + 1;
// else
// return 0;
// }
int func4(int var1, int var2, int var3)
{
if ((var3 - var2) / 2 + var2 > var1)
return func4(var1, var2, (var3 - var2) / 2 + var2 - 1) * 2;
else if ((var3 - var2) / 2 + var2 < var1)
return func4(var1, (var3 - var2) / 2 + var2 + 1, var3) * 2 + 1;
else
return 0;
}
代入法
一種取巧的解法，只需要實(shí)現(xiàn) func4祈纯，然后將所有可能的輸入代入計(jì)算即可令宿。由于只有 15 種情況，所以手算也是可行的腕窥，這里不作過(guò)多介紹了粒没。
分析法
func4 的分支共有 3 條：
func4 * 2func4 * 2 + 10
終止條件是 (var2 + var3) / 2 == var1。
想要得到 4簇爆，至少需要 1 次 +1癞松，否則無(wú)論如何計(jì)算結(jié)果都只能為 0。而經(jīng)過(guò)簡(jiǎn)單的推導(dǎo)冕碟，我們發(fā)現(xiàn)前 2 次為 +1 不可能計(jì)算出 4拦惋，因?yàn)榍?2 次為 +1 的解集為 ，不包含
4安寺，所以結(jié)果只能是 1 次 +1 與 2 次 *2厕妖。
列公式如下
由于除法是整除，所以化簡(jiǎn)不一定能計(jì)算出精確的答案挑庶，但可以計(jì)算出一個(gè)大概的區(qū)間言秸，然后逐個(gè)代入計(jì)算。由于情況較少迎捺，所以直接代入 式計(jì)算可能會(huì)更快举畸。
計(jì)算結(jié)果：0 0 4 0 2 2 6 0 1 1 5 1 3 3 7，所以 phase_4 的答案為 2 4凳枝。
phase_5
phase_5的主體是一個(gè)do...while的循環(huán)結(jié)構(gòu)
block 1
08048dee <phase_5>:
8048dee: 83 ec 2c sub $0x2c,%esp
; sscanf(char* str, "%d %d", int* pvar1, int* pvar2)
8048df1: 8d 44 24 1c lea 0x1c(%esp),%eax; %eax = &var2
8048df5: 89 44 24 0c mov %eax,0xc(%esp); pvar1 = &var2
8048df9: 8d 44 24 18 lea 0x18(%esp),%eax; %eax = &var1
8048dfd: 89 44 24 08 mov %eax,0x8(%esp); pvar2 = &var1
8048e01: c7 44 24 04 a3 a4 04 movl $0x804a4a3,0x4(%esp); "%d %d"
8048e08: 08
8048e09: 8b 44 24 30 mov 0x30(%esp),%eax; %eax = str
8048e0d: 89 04 24 mov %eax,(%esp); (%esp) = str
8048e10: e8 5b fa ff ff call 8048870 <__isoc99_sscanf@plt>
與 phase_4 完全相同的 sscanf 函數(shù)抄沮。
block 2
; if (sscanf(/**/) <= 1)
8048e15: 83 f8 01 cmp $0x1,%eax
8048e18: 7f 05 jg 8048e1f <phase_5+0x31>
; explode_bomb()
8048e1a: e8 87 03 00 00 call 80491a6 <explode_bomb>
; else
8048e1f: 8b 44 24 18 mov 0x18(%esp),%eax; %eax = var1
8048e23: 83 e0 0f and $0xf,%eax; %eax = var1 & 15
8048e26: 89 44 24 18 mov %eax,0x18(%esp); var1 = var1 & 15
; if(var1 & 15 != 15)
8048e2a: 83 f8 0f cmp $0xf,%eax
8048e2d: 74 2a je 8048e59 <phase_5+0x6b>
8048e2f: b9 00 00 00 00 mov $0x0,%ecx; %ecx = 0
8048e34: ba 00 00 00 00 mov $0x0,%edx; %edx = 0
第二塊首先對(duì)讀取的結(jié)果進(jìn)行檢測(cè)，如果正確無(wú)誤則對(duì)第一個(gè)整數(shù) var1 取低 4 位岖瑰，判斷是否不等于 15叛买，所以輸入的 var1 只需要滿足低 4 位相同就可以得到相同的計(jì)算結(jié)果。
block 3
; int phase_5_arr[] = {10, 2, 14, 7, 8, 12, 15, 11, 0, 4, 1, 13, 3, 9, 6};
; do
8048e39: 83 c2 01 add $0x1,%edx; %edx = %edx + 1
8048e3c: 8b 04 85 00 a3 04 08 mov 0x804a300(,%eax,4),%eax; %eax = phase_5_arr[var1]
8048e43: 01 c1 add %eax,%ecx; %ecx = 0 + phase_5_arr[var1]
8048e45: 83 f8 0f cmp $0xf,%eax;
8048e48: 75 ef jne 8048e39 <phase_5+0x4b>
; while (phase_5_arr[var1] != 15)
8048e4a: 89 44 24 18 mov %eax,0x18(%esp); var1 = %eax
接 block 2 中的 if(var1 & 15 != 15)蹋订，當(dāng)條件成立時(shí)進(jìn)入 do...while 循環(huán)率挣。
地址 0x804a300 應(yīng)該是一個(gè)數(shù)組的首地址（博主命名為 phase_5_arr ），其中的元素應(yīng)該為：{10, 2, 14, 7, 8, 12, 15, 11, 0, 4, 1, 13, 3, 9, 6}露戒，共 15 個(gè)元素椒功。
0804a300 <array.2957>:
804a300: 0a 00 or (%eax),%al
804a302: 00 00 add %al,(%eax)
804a304: 02 00 add (%eax),%al
804a306: 00 00 add %al,(%eax)
804a308: 0e push %cs
804a309: 00 00 add %al,(%eax)
804a30b: 00 07 add %al,(%edi)
804a30d: 00 00 add %al,(%eax)
804a30f: 00 08 add %cl,(%eax)
804a311: 00 00 add %al,(%eax)
804a313: 00 0c 00 add %cl,(%eax,%eax,1)
804a316: 00 00 add %al,(%eax)
804a318: 0f 00 00 sldt (%eax)
804a31b: 00 0b add %cl,(%ebx)
804a31d: 00 00 add %al,(%eax)
804a31f: 00 00 add %al,(%eax)
804a321: 00 00 add %al,(%eax)
804a323: 00 04 00 add %al,(%eax,%eax,1)
804a326: 00 00 add %al,(%eax)
804a328: 01 00 add %eax,(%eax)
804a32a: 00 00 add %al,(%eax)
804a32c: 0d 00 00 00 03 or $0x3000000,%eax
804a331: 00 00 add %al,(%eax)
804a333: 00 09 add %cl,(%ecx)
804a335: 00 00 add %al,(%eax)
804a337: 00 06 add %al,(%esi)
804a339: 00 00 add %al,(%eax)
804a33b: 00 05 00 00 00 53 add %al,0x53000000
%edx 記錄 do...while 循環(huán)執(zhí)行的次數(shù)捶箱，循環(huán)體內(nèi)將 phase_5_arr (定義為) 內(nèi)的元素逐個(gè)相加并存入 %ecx，初始索引為輸入的 var1动漾，之后每次的索引是上一次循環(huán)的元素值丁屎，直到元素值為 15 時(shí)退出循環(huán)（phase_5_arr 可以看作是一個(gè)存放鏈表鏈節(jié)的數(shù)組）。
block 4
; if (%edx == 15)
8048e4e: 83 fa 0f cmp $0xf,%edx;
8048e51: 75 06 jne 8048e59 <phase_5+0x6b>
; if (%ecx == var2)
8048e53: 3b 4c 24 1c cmp 0x1c(%esp),%ecx
8048e57: 74 05 je 8048e5e <phase_5+0x70>
; explode_bomb()
8048e59: e8 48 03 00 00 call 80491a6 <explode_bomb>
8048e5e: 83 c4 2c add $0x2c,%esp
8048e61: c3 ret
首先檢測(cè)循環(huán)的次數(shù)谦炬，要求循環(huán)次數(shù)為 15悦屏，而phase_5_arr 的元素個(gè)數(shù)就是 15，說(shuō)明這 15 個(gè)鏈節(jié)形成了一個(gè)鏈表键思，輸入的 var1 應(yīng)當(dāng)為鏈表的表頭。
再檢測(cè)累加的值是否與輸入的第二個(gè)整數(shù) var2 相等甫贯，要求 var2 與運(yùn)算結(jié)果相同吼鳞。
總體分析，phase_5 要求輸入鏈表的表頭以及各個(gè)鏈節(jié)的和叫搁，所以答案為 5 115赔桌，0-15 中缺失的元素為 5。
code
void phase_5(char* str)
{
int var1, var2, count, sum;
if (sscanf(str, "%d %d", &var1, &var2) <= 1)
explode_bomb();
var1 = var1 & 15;
if (var1 != 15) {
count = sum = 0;
do {
++count;
var1 = phase_5_arr[var1];
sum += var1;
} while (var1 != 15);
}
if (count != 15 || sum != var2)
explode_bomb();
}
phase_6
phase_6的結(jié)構(gòu)比較復(fù)雜渴逻，存在許多分支以及嵌套的循環(huán)疾党，跳轉(zhuǎn)指令互相交錯(cuò)
block 1
08048e62 <phase_6>:
8048e62: 56 push %esi
8048e63: 53 push %ebx
8048e64: 83 ec 44 sub $0x44,%esp
; read_six_numbers(char* str, unsigned arr[])
8048e67: 8d 44 24 10 lea 0x10(%esp),%eax; %eax = arr
8048e6b: 89 44 24 04 mov %eax,0x4(%esp); 0x4(%esp) = arr
8048e6f: 8b 44 24 50 mov 0x50(%esp),%eax; %eax = str
8048e73: 89 04 24 mov %eax,(%esp); (%esp) = str
8048e76: e8 60 04 00 00 call 80492db <read_six_numbers>
調(diào)用了 phase_2 中出現(xiàn)過(guò)的 read_six_numbers，將在之后逐步分析為什么應(yīng)該是 unsigned 數(shù)組惨奕。
block 2
8048e7b: be 00 00 00 00 mov $0x0,%esi; %esi = 0
; do
8048e80: 8b 44 b4 10 mov 0x10(%esp,%esi,4),%eax; %eax = arr[%esi]
8048e84: 83 e8 01 sub $0x1,%eax; %eax -= arr[%esi] - 1
; if (arr[%esi] - 1 > 5)
8048e87: 83 f8 05 cmp $0x5,%eax
8048e8a: 76 05 jbe 8048e91 <phase_6+0x2f>
; explode_bomb()
8048e8c: e8 15 03 00 00 call 80491a6 <explode_bomb>
; if (++%esi == 6)
; break
8048e91: 83 c6 01 add $0x1,%esi; %esi += 1
8048e94: 83 fe 06 cmp $0x6,%esi
8048e97: 74 33 je 8048ecc <phase_6+0x6a>
; for (%ebx = %esi, %ebx <= 5; ++%ebx)
8048e99: 89 f3 mov %esi,%ebx; %ebx = %esi
8048e9b: 8b 44 9c 10 mov 0x10(%esp,%ebx,4),%eax; %eax = arr[%ebx]
; if (arr[%esi-1] == arr[%ebx])
8048e9f: 39 44 b4 0c cmp %eax,0xc(%esp,%esi,4)
8048ea3: 75 05 jne 8048eaa <phase_6+0x48>
; explode_bomb()
8048ea5: e8 fc 02 00 00 call 80491a6 <explode_bomb>
8048eaa: 83 c3 01 add $0x1,%ebx; %ebx += 1
8048ead: 83 fb 05 cmp $0x5,%ebx
8048eb0: 7e e9 jle 8048e9b <phase_6+0x39>
; loop for
8048eb2: eb cc jmp 8048e80 <phase_6+0x1e>
; while (true)
首先將 %esi 置 0雪位，用于記錄循環(huán)的次數(shù)，當(dāng) %esi == 6 時(shí)退出循環(huán)梨撞。
循環(huán)體內(nèi)首先判斷當(dāng)前元素減 1 之后是否大于 5雹洗，若是則 explode_bomb，此處元素的類(lèi)型將會(huì)影響結(jié)果卧波。若為 int时肿，則輸入的值只需要不大于 5 即可，可以為負(fù)數(shù)港粱；若為 unsigned螃成，則輸入的值的范圍必須為 1-6。
判斷完元素值之后查坪，循環(huán)計(jì)數(shù) +1寸宏，判斷是否退出循環(huán)，若不退出循環(huán)咪惠，則進(jìn)入 for 循環(huán)击吱。
for 循環(huán)中首先將 %esi 存入 %ebx，作為 for 循環(huán)的迭代變量遥昧。循環(huán)體內(nèi)比較 arr[%ebx] 與 arr[%esi-1] 的值覆醇，如果相等則 explode_bomb朵纷，直至變量完所有元素。
綜合分析以上兩個(gè)循環(huán)永脓，可以發(fā)現(xiàn)其功能是判斷輸入的元素是否存在相同元素袍辞，如果存在則 explode_bomb，所以輸入的元素應(yīng)當(dāng)不重復(fù)常摧。如果類(lèi)型為 unsigned搅吁，則進(jìn)一步約束為 1-6，且每個(gè)值出現(xiàn) 1 次落午。
block 3
; do
8048eb4: 8b 52 08 mov 0x8(%edx),%edx; %edx = %edx -> next
8048eb7: 83 c0 01 add $0x1,%eax; %eax += 1
8048eba: 39 c8 cmp %ecx,%eax
8048ebc: 75 f6 jne 8048eb4 <phase_6+0x52>
; while (++%eax != arr[%ebx])
8048ebe: 89 54 b4 28 mov %edx,0x28(%esp,%esi,4); nodes[%esi] = %edx
8048ec2: 83 c3 01 add $0x1,%ebx; %ebx += 1
8048ec5: 83 fb 06 cmp $0x6,%ebx
8048ec8: 75 07 jne 8048ed1 <phase_6+0x6f>
; while (%ebx != 6)
; else
8048eca: eb 1c jmp 8048ee8 <phase_6+0x86>
8048ecc: bb 00 00 00 00 mov $0x0,%ebx; %ebx = 0
; do
8048ed1: 89 de mov %ebx,%esi; %esi = %ebx
8048ed3: 8b 4c 9c 10 mov 0x10(%esp,%ebx,4),%ecx; %ecx = arr[%ebx]
8048ed7: b8 01 00 00 00 mov $0x1,%eax; %eax = 1
8048edc: ba 3c c1 04 08 mov $0x804c13c,%edx; %edx = 0x804c13c
; if (arr[%ebx] > 1)
8048ee1: 83 f9 01 cmp $0x1,%ecx
8048ee4: 7f ce jg 8048eb4 <phase_6+0x52>
; else
8048ee6: eb d6 jmp 8048ebe <phase_6+0x5c>
第三塊是兩個(gè)嵌套的 do...while 循環(huán)谎懦，但是外層循環(huán)中代碼并非按順序分布，所以可能難以理解溃斋。
外層循環(huán)的起點(diǎn)為 8048ed1界拦，其之前的地址為 8048ecc 的指令是循環(huán)計(jì)數(shù)的初始化指令，不在循環(huán)體內(nèi)梗劫。
外層循環(huán)首先執(zhí)行以下操作：
- 將外層循環(huán)計(jì)數(shù)器
%ebx的值存入%esi中 - 將
arr[%ebx]存入%ecx - 令內(nèi)存循環(huán)計(jì)數(shù)器
%eax = 1 - 令
%edx = 0x804c13c
0804c13c <node1>:
804c13c: a6 cmpsb %es:(%edi),%ds:(%esi)
804c13d: 01 00 add %eax,(%eax)
804c13f: 00 01 add %al,(%ecx)
804c141: 00 00 add %al,(%eax)
804c143: 00 48 c1 add %cl,-0x3f(%eax)
804c146: 04 08 add $0x8,%al
0804c148 <node2>:
804c148: 4b dec %ebx
804c149: 03 00 add (%eax),%eax
804c14b: 00 02 add %al,(%edx)
804c14d: 00 00 add %al,(%eax)
804c14f: 00 54 c1 04 add %dl,0x4(%ecx,%eax,8)
804c153: 08 af 01 00 00 03 or %ch,0x3000001(%edi)
0804c154 <node3>:
804c154: af scas %es:(%edi),%eax
804c155: 01 00 add %eax,(%eax)
804c157: 00 03 add %al,(%ebx)
804c159: 00 00 add %al,(%eax)
804c15b: 00 60 c1 add %ah,-0x3f(%eax)
804c15e: 04 08 add $0x8,%al
0804c160 <node4>:
804c160: a2 00 00 00 04 mov %al,0x4000000
804c165: 00 00 add %al,(%eax)
804c167: 00 6c c1 04 add %ch,0x4(%ecx,%eax,8)
804c16b: 08 3a or %bh,(%edx)
0804c16c <node5>:
804c16c: 3a 03 cmp (%ebx),%al
804c16e: 00 00 add %al,(%eax)
804c170: 05 00 00 00 78 add $0x78000000,%eax
804c175: c1 04 08 c8 roll $0xc8,(%eax,%ecx,1)
0804c178 <node6>:
804c178: c8 02 00 00 enter $0x2,$0x0
804c17c: 06 push %es
804c17d: 00 00 add %al,(%eax)
804c17f: 00 00 add %al,(%eax)
804c181: 00 00 add %al,(%eax)
查看地址單元享甸，發(fā)現(xiàn) %edx 存儲(chǔ)的應(yīng)該是 node1 的首地址，分析這幾個(gè) node 的內(nèi)存結(jié)果梳侨，猜測(cè)其結(jié)構(gòu)應(yīng)該為：
struct node {
int value;
int id;
struct node* next;
};
每一個(gè) node 分別指向編號(hào) +1 的 node蛉威，形成一個(gè)鏈表。
完成值的設(shè)置之后走哺，判斷當(dāng)前數(shù)組元素是否大于 1蚯嫌，若是則進(jìn)入內(nèi)層循環(huán)，若否則跳過(guò)內(nèi)層循環(huán)割坠。
內(nèi)存循環(huán)執(zhí)行如下操作：
-
%edx = %edx -> next齐帚，將指針指向下一節(jié)點(diǎn) -
%eax += 1，再判斷%eax是否等于當(dāng)前數(shù)組元素彼哼，若是則退出循環(huán)对妄，若否則內(nèi)層循環(huán)迭代
所以內(nèi)層循環(huán)的功能應(yīng)該是找到編號(hào)與當(dāng)前數(shù)組元素相等的節(jié)點(diǎn)，由于編號(hào)為 1-6敢朱，因此如果要避免死循環(huán)剪菱，則數(shù)組元素必須為 1-6，所以元素類(lèi)型應(yīng)當(dāng)為 unsigned拴签。
內(nèi)層循環(huán)結(jié)束之后（或當(dāng)前數(shù)組元素是否大于 1 ）孝常，將指向的節(jié)點(diǎn)的首地址存入數(shù)組 arr 之后的地址中，如果以 arr 進(jìn)行表示則是存入 arr[6 + %esi]蚓哩。由于 %esi 是外層循環(huán)計(jì)數(shù)器构灸，值在不停增加，所以 arr 之后應(yīng)當(dāng)還有一個(gè)數(shù)組岸梨，用于存放指向 node 的指針喜颁，記作 struct node* nodes[]稠氮。
總體分析上述內(nèi)外層循環(huán)，發(fā)現(xiàn)實(shí)現(xiàn)的功能是按照數(shù)組元素的值半开，將相應(yīng)編號(hào)的節(jié)點(diǎn)依次存入節(jié)點(diǎn)數(shù)組（通過(guò)指針訪問(wèn)隔披，并沒(méi)有存入相應(yīng)的地址）中。
block 4
; 循環(huán)展開(kāi)
8048ee8: 8b 5c 24 28 mov 0x28(%esp),%ebx; %ebx = nodes[0]
8048eec: 8b 44 24 2c mov 0x2c(%esp),%eax; %eax = nodes[1]
8048ef0: 89 43 08 mov %eax,0x8(%ebx); nodes[0]->next = nodes[1]
8048ef3: 8b 54 24 30 mov 0x30(%esp),%edx; %edx = nodes[2]
8048ef7: 89 50 08 mov %edx,0x8(%eax); nodes[1]->next = nodes[2]
8048efa: 8b 44 24 34 mov 0x34(%esp),%eax; %eax = nodes[3]
8048efe: 89 42 08 mov %eax,0x8(%edx); nodes[2]->next = nodes[3]
8048f01: 8b 54 24 38 mov 0x38(%esp),%edx; %edx = nodes[4]
8048f05: 89 50 08 mov %edx,0x8(%eax); nodes[3]->next = nodes[4]
8048f08: 8b 44 24 3c mov 0x3c(%esp),%eax; %eax = nodes[5]
8048f0c: 89 42 08 mov %eax,0x8(%edx); nodes[4]->next = nodes[5]
8048f0f: c7 40 08 00 00 00 00 movl $0x0,0x8(%eax); nodes[5]->next = NULL
第四塊按節(jié)點(diǎn)數(shù)組中的順序寂拆，將上一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)奢米，結(jié)合 block 3 可以發(fā)現(xiàn)，兩塊指令實(shí)現(xiàn)的功能是按照輸入的數(shù)組對(duì)節(jié)點(diǎn)進(jìn)行了重新的排列纠永，形成了一個(gè)新的鏈表鬓长。
block 5
8048f16: be 05 00 00 00 mov $0x5,%esi; %esi = 5
; do
8048f1b: 8b 43 08 mov 0x8(%ebx),%eax; %eax = %ebx->next
8048f1e: 8b 10 mov (%eax),%edx; %edx = %ebx->next->value
; if (%ebx->value > %ebx->next->value)
8048f20: 39 13 cmp %edx,(%ebx)
8048f22: 7e 05 jle 8048f29 <phase_6+0xc7>
; explode_bomb()
8048f24: e8 7d 02 00 00 call 80491a6 <explode_bomb>
8048f29: 8b 5b 08 mov 0x8(%ebx),%ebx; %ebx = %ebx->next
8048f2c: 83 ee 01 sub $0x1,%esi; %esi -= 1
8048f2f: 75 ea jne 8048f1b <phase_6+0xb9>
; while (--%esi)
第五塊是一個(gè)簡(jiǎn)單的 do...while 循環(huán)，首先將計(jì)數(shù)器置為 5尝江，然后進(jìn)入循環(huán)痢士。同時(shí)需要注意到，在 block 4 中茂装，nodes[0] 存入 %ebx 之后 %ebx 的值沒(méi)有被覆寫(xiě)，所以 %ebx 中存儲(chǔ)的是 nodes[0] 的首地址善延。
for 循環(huán)中首先將 %ebx 指向的下一個(gè)節(jié)點(diǎn)存入 %eax少态，將下一個(gè)節(jié)點(diǎn)的值存入 %edx。然后判斷當(dāng)前節(jié)點(diǎn)的值是否大于下一節(jié)點(diǎn)的值易遣，若是則 explode_bomb彼妻，若否則計(jì)數(shù)器 -1，循環(huán)迭代直至計(jì)數(shù)器為 0豆茫。
總體分析侨歉，phase_6 的要求我們按各節(jié)點(diǎn)值的大小從小到大進(jìn)行排序，然后將各節(jié)點(diǎn)的順序輸入揩魂。
由于節(jié)點(diǎn)值為 [ 0x1a6, 0x34b, 0x1af, 0xa2, 0x33a, 0x2c8 ]幽邓，所以答案為 4 1 3 6 5 2。
code
void phase_6(char* str)
{
unsigned arr[6];
struct node* nodes[6];
int i, j, index;
struct node* p;
read_six_numbers(str, arr);
i = 0;
do {
if (arr[i] - 1 > 5)
explode_bomb();
if (++i == 6)
break;
for (j = i; j <= 5; ++j)
if (arr[i - 1] == arr[j])
explode_bomb();
} while (1);
i = 0;
do {
index = 1;
p = &node1;
if (arr[i] > 1)
do
p = p->next;
while (++index != arr[i]);
nodes[i] = p;
} while (++i != 6);
nodes[0]->next = nodes[1];
nodes[1]->next = nodes[2];
nodes[2]->next = nodes[3];
nodes[3]->next = nodes[4];
nodes[4]->next = nodes[5];
nodes[5]->next = NULL;
p = nodes[0];
i = 5;
do {
if (p->value > p->next->value)
explode_bomb();
p = p->next;
} while (--i);
}
secret_phase_entrance
secret_phase 并沒(méi)有在主函數(shù)中直接調(diào)用火脉，我們需要先找到它的入口牵舵。匯編指令中直接有標(biāo)注 secret_phase 的地址，我們找到調(diào)用它的地方即可倦挂，就在 phase_defused 中畸颅。
phase_defused
0804932b <phase_defused>:
804932b: 81 ec 8c 00 00 00 sub $0x8c,%esp
; 哨兵
8049331: 65 a1 14 00 00 00 mov %gs:0x14,%eax
8049337: 89 44 24 7c mov %eax,0x7c(%esp)
804933b: 31 c0 xor %eax,%eax
; if (*(int*)0x804c3cc == 6)
804933d: 83 3d cc c3 04 08 06 cmpl $0x6,0x804c3cc
8049344: 75 72 jne 80493b8 <phase_defused+0x8d>
; sscanf(char* str, "%d %d %s", int var1, int var2, char* s)
8049346: 8d 44 24 2c lea 0x2c(%esp),%eax
804934a: 89 44 24 10 mov %eax,0x10(%esp); 0x10(%esp) = s
804934e: 8d 44 24 28 lea 0x28(%esp),%eax
8049352: 89 44 24 0c mov %eax,0xc(%esp); 0xc(%esp) = var2
8049356: 8d 44 24 24 lea 0x24(%esp),%eax
804935a: 89 44 24 08 mov %eax,0x8(%esp); 0x08(%esp) = var1
804935e: c7 44 24 04 a9 a4 04 movl $0x804a4a9,0x4(%esp); "%d %d %s"
8049365: 08
8049366: c7 04 24 d0 c4 04 08 movl $0x804c4d0,(%esp);
804936d: e8 fe f4 ff ff call 8048870 <__isoc99_sscanf@plt>
; if (sscanf(/**/) == 3)
8049372: 83 f8 03 cmp $0x3,%eax
8049375: 75 35 jne 80493ac <phase_defused+0x81>
; strings_not_equal(char*, "DrEvil")
8049377: c7 44 24 04 b2 a4 04 movl $0x804a4b2,0x4(%esp); "DrEvil"
804937e: 08
804937f: 8d 44 24 2c lea 0x2c(%esp),%eax; %eax = s
8049383: 89 04 24 mov %eax,(%esp); (%esp) = s
8049386: e8 09 fd ff ff call 8049094 <strings_not_equal>
; if (strings_not_equal(/**/))
; return
804938b: 85 c0 test %eax,%eax
804938d: 75 1d jne 80493ac <phase_defused+0x81>
; "Curses, you've found the secret phase!"
804938f: c7 04 24 78 a3 04 08 movl $0x804a378,(%esp)
8049396: e8 65 f4 ff ff call 8048800 <puts@plt>
; "But finding it and solving it are quite different..."
804939b: c7 04 24 a0 a3 04 08 movl $0x804a3a0,(%esp)
80493a2: e8 59 f4 ff ff call 8048800 <puts@plt>
80493a7: e8 dc fb ff ff call 8048f88 <secret_phase>
; "Congratulations! You've defused the bomb!"
80493ac: c7 04 24 d8 a3 04 08 movl $0x804a3d8,(%esp)
80493b3: e8 48 f4 ff ff call 8048800 <puts@plt>
80493b8: 8b 44 24 7c mov 0x7c(%esp),%eax
80493bc: 65 33 05 14 00 00 00 xor %gs:0x14,%eax
80493c3: 74 05 je 80493ca <phase_defused+0x9f>
80493c5: e8 06 f4 ff ff call 80487d0 <__stack_chk_fail@plt>
80493ca: 81 c4 8c 00 00 00 add $0x8c,%esp
80493d0: c3 ret
我們直接來(lái)分析什么時(shí)候觸發(fā) secret_phase。首先來(lái)看 0x804c3cc 這個(gè)地址方援，我們直接找到相應(yīng)的指令處：
0804c3cc <num_input_strings>:
804c3cc: 00 00 add %al,(%eax)
發(fā)現(xiàn)它的命名是 num_input_strings没炒，字面意思就是輸入的字符串的個(gè)數(shù)，這大概率就是答題的次數(shù)犯戏，再搜索一下哪里出現(xiàn)了這個(gè)地址送火，并對(duì)它進(jìn)行了寫(xiě)值：
080491cd <read_line>:
8049287: a1 cc c3 04 08 mov 0x804c3cc,%eax
804928c: 8d 50 01 lea 0x1(%eax),%edx
804928f: 89 15 cc c3 04 08 mov %edx,0x804c3cc
最終我們?cè)?read_line 中找到了它拳话，整個(gè)匯編指令中只有這第三行指令對(duì)它進(jìn)行了寫(xiě)值，再結(jié)合上面的兩條指令漾脂，我們發(fā)現(xiàn)是對(duì)其進(jìn)行了自增 1 的操作假颇，符合我們的猜測(cè)。由于 read_line 部分指令太多骨稿，也沒(méi)有必要進(jìn)行分析笨鸡，我們?nèi)?gdb 中進(jìn)行一下驗(yàn)證：
可以看到結(jié)果與我們分析的完全符合。
接著往下走坦冠，我們發(fā)現(xiàn)調(diào)用了 sscanf 函數(shù)形耗，讀取了兩個(gè)整數(shù)和一個(gè)字符串，但是直接去指令中找辙浑，我們發(fā)現(xiàn)被讀取的字符串是空的激涤，所以這個(gè)字符串在運(yùn)行時(shí)應(yīng)當(dāng)發(fā)生了改變，我們接著之前的 gdb 查看一下：
很顯然是我們輸入的 phase_4 的答案判呕，而這個(gè) sscanf 還讀取了一個(gè)字符串 "DrEvil"倦踢，顯然我們 phase_4 的答案輸入 2 4 DrEvil 就能進(jìn)入 secret_phase：
至此，我們已經(jīng)找到了 secret_phase 的入口侠草，接下來(lái)就是解決它辱挥。
secret_phase
secret_phase的主體如phase_4是一個(gè)遞歸函數(shù)的調(diào)用
08048f88 <secret_phase>:
8048f88: 53 push %ebx
8048f89: 83 ec 18 sub $0x18,%esp
; read_line()
8048f8c: e8 3c 02 00 00 call 80491cd <read_line>; str = read_line()
; strtol(str, 0, 10)
8048f91: c7 44 24 08 0a 00 00 movl $0xa,0x8(%esp)
8048f98: 00
8048f99: c7 44 24 04 00 00 00 movl $0x0,0x4(%esp)
8048fa0: 00
8048fa1: 89 04 24 mov %eax,(%esp)
8048fa4: e8 37 f9 ff ff call 80488e0 <strtol@plt>
8048fa9: 89 c3 mov %eax,%ebx; %ebx = %eax
8048fab: 8d 40 ff lea -0x1(%eax),%eax; %eax = %eax-1
; if (%eax-1 > 1000)
8048fae: 3d e8 03 00 00 cmp $0x3e8,%eax
8048fb3: 76 05 jbe 8048fba <secret_phase+0x32>
; explode_bomb()
8048fb5: e8 ec 01 00 00 call 80491a6 <explode_bomb>
; fun7()
8048fba: 89 5c 24 04 mov %ebx,0x4(%esp); 0x4(%esp) = %ebx
8048fbe: c7 04 24 88 c0 04 08 movl $0x804c088,(%esp); (%esp) = (int*)0x804c088
8048fc5: e8 6d ff ff ff call 8048f37 <fun7>
; if (fun7 != 4)
8048fca: 83 f8 04 cmp $0x4,%eax
8048fcd: 74 05 je 8048fd4 <secret_phase+0x4c>
; explode_bomb()
8048fcf: e8 d2 01 00 00 call 80491a6 <explode_bomb>
; else
; "Wow! You've defused the secret stage!"
8048fd4: c7 04 24 94 a2 04 08 movl $0x804a294,(%esp)
8048fdb: e8 20 f8 ff ff call 8048800 <puts@plt>
8048fe0: e8 46 03 00 00 call 804932b <phase_defused>
8048fe5: 83 c4 18 add $0x18,%esp
8048fe8: 5b pop %ebx
8048fe9: c3 ret
主體并不復(fù)雜，約束條件僅有 边涕，然后將其作為
fun7 的第二個(gè)參數(shù)晤碘。我們觀察第一個(gè)參數(shù)：
0804c088 <n1>:
804c088: 24 00 and $0x0,%al
804c08a: 00 00 add %al,(%eax)
804c08c: 94 xchg %eax,%esp
804c08d: c0 04 08 a0 rolb $0xa0,(%eax,%ecx,1)
804c091: c0 04 08 08 rolb $0x8,(%eax,%ecx,1)
0804c094 <n21>:
804c094: 08 00 or %al,(%eax)
804c096: 00 00 add %al,(%eax)
804c098: c4 (bad)
804c099: c0 04 08 ac rolb $0xac,(%eax,%ecx,1)
804c09d: c0 04 08 32 rolb $0x32,(%eax,%ecx,1)
發(fā)現(xiàn)是一個(gè)類(lèi)似 node 的節(jié)點(diǎn)（還有很多就不貼上來(lái)了），不過(guò)似乎有兩個(gè)指針功蜓，所以這個(gè)結(jié)構(gòu)應(yīng)該會(huì)比鏈表復(fù)雜园爷，可能是雙向鏈表或樹(shù)或圖。
最后要滿足 fun7 的返回值為 4式撼，那我們就進(jìn)入 fun7 一探究竟童社。
code
void secret_phase(char* str)
{
char* str;
unsigned x;
str = read_line();
x = strtol(str, 0, 10);
if (x - 1 > 1000)
explode_bomb();
if (fun7(&n1, x) != 4)
explode_bomb();
printf("Wow! You've defused the secret stage!");
}
fun7
; fun7(n* p, int var)
08048f37 <fun7>:
8048f37: 53 push %ebx
8048f38: 83 ec 18 sub $0x18,%esp
8048f3b: 8b 54 24 20 mov 0x20(%esp),%edx; %edx = p
8048f3f: 8b 4c 24 24 mov 0x24(%esp),%ecx; %ecx = var
; if (p != NULL)
8048f43: 85 d2 test %edx,%edx
8048f45: 74 37 je 8048f7e <fun7+0x47>
8048f47: 8b 1a mov (%edx),%ebx; %ebx = p->value
; if (p->value > var)
8048f49: 39 cb cmp %ecx,%ebx;
8048f4b: 7e 13 jle 8048f60 <fun7+0x29>
; fun7(p->left, var)
8048f4d: 89 4c 24 04 mov %ecx,0x4(%esp); 0x4(%esp) = var
8048f51: 8b 42 04 mov 0x4(%edx),%eax; %eax = p->left
8048f54: 89 04 24 mov %eax,(%esp); (%esp) = p->left
8048f57: e8 db ff ff ff call 8048f37 <fun7>
8048f5c: 01 c0 add %eax,%eax; return fun7 * 2
8048f5e: eb 23 jmp 8048f83 <fun7+0x4c>
; else
8048f60: b8 00 00 00 00 mov $0x0,%eax; return 0
; else if (p->value != var)
8048f65: 39 cb cmp %ecx,%ebx
8048f67: 74 1a je 8048f83 <fun7+0x4c>
; fun7(p->right, var)
8048f69: 89 4c 24 04 mov %ecx,0x4(%esp); 0x4(%esp) = var
8048f6d: 8b 42 08 mov 0x8(%edx),%eax; %eax = p->right
8048f70: 89 04 24 mov %eax,(%esp); (%esp) = p->right
8048f73: e8 bf ff ff ff call 8048f37 <fun7>
8048f78: 8d 44 00 01 lea 0x1(%eax,%eax,1),%eax; return fun7 * 2 + 1
8048f7c: eb 05 jmp 8048f83 <fun7+0x4c>
; else
8048f7e: b8 ff ff ff ff mov $0xffffffff,%eax; return -1
8048f83: 83 c4 18 add $0x18,%esp
8048f86: 5b pop %ebx
8048f87: c3 ret
跟 func4 幾乎是一個(gè)模子里刻出來(lái)的，只不過(guò)多了一步判斷 p 是否指向 NULL端衰，若是則返回 -1叠洗。
在 p != NULL 時(shí)，共有三條分支：
-
p->value > var:return fun7(p->left, var) * 2 -
p->value < var:return fun7(p->right, var) * 2 + 1 -
p->value == var:return 0
這時(shí)候也確定了 n 具有兩個(gè)指針旅东，我們來(lái)分析一下它們之間的關(guān)系：
"n1": {
"value": 36,
"n21": {
"value": 8,
"n31": {
"value": 6,
"n41": { "value": 1 },
"n42": { "value": 7 }
},
"n32": {
"value": 22,
"n43": { "value": 20 },
"n44": { "value": 35 }
}
},
"n22": {
"value": 50,
"n33": {
"value": 45,
"n45": { "value": 40 },
"n46": { "value": 47 }
},
"n34": {
"value": 107,
"n47": { "value": 99 },
"n48": { "value": 1001 }
}
}
}
確定了這是一棵二叉樹(shù)灭抑，同時(shí)樹(shù)的高度為 4。結(jié)合之前的三條分支抵代，得到我們的任務(wù)是在第 4 步時(shí)計(jì)算出 4腾节。
步長(zhǎng)只有 4，即使是窮舉也很快，我們得到的唯一的解是：{ "0", "fun7 * 2 + 1", "fun7 * 2", "fun7 * 2" }案腺，滿足的比較關(guān)系從根節(jié)點(diǎn)開(kāi)始為：{ '<', '<', '>', '==' }庆冕，在樹(shù)中尋找到路徑：n1 -> n21 -> n31 -> n42，答案為 7劈榨。
code
int fun7(struct n* p, int var)
{
if (p == NULL)
return -1;
if (p->value > var)
return fun7(p->left, var) * 2;
if (p->value != var)
return fun7(p->right, var) * 2 + 1;
return 0;
}
后記
至此 bomblab 也算是告一段落访递，這個(gè)實(shí)驗(yàn)的確是花費(fèi)了不少功夫，包括最初的摸索同辣，到后來(lái)的嫻熟拷姿，成長(zhǎng)也是很大。而寫(xiě)這篇博客花費(fèi)的時(shí)間也許超過(guò)了我做實(shí)驗(yàn)的時(shí)間旱函。
在此响巢，我非常感謝你能閱讀完這一篇長(zhǎng)長(zhǎng)的文章，也希望你能有所收獲棒妨，你的每一次點(diǎn)擊都是對(duì)我莫大的鼓勵(lì)??踪古。
個(gè)人博客：https://wilfredshen.cn/
