Bomb-lab是针对CSAPP中对应的第三章内容:提供一个二进制对象文件bomb
,实验也提供了bomb.c文件,但是没有头文件,所以不能编译;在运行时,会要求用户输入对应6个phase的字符串,任何一个不正确,炸弹都会爆炸。
lab的具体内容可以在官网中下载,所有的lab代码在GitHub上。
前期准备
首先我们反汇编可执行文件bomb
,得到汇编代码。
1 | $ objdump -d bomb > disassemble.asm |
phase_1
首先我们定位到main函数,在264行,这里可以对比以下C代码和汇编代码,可以发现都是一一对应的。然后直接找到phase_1,如下所示:
1 | 0000000000400ee0 <phase_1>: |
寄存器%esi是默认的第二个参数储存寄存器,直接存储了值0x402400,然后调用函数strings_not_equal,我们可以跳到strings_not_equal函数,可以发现这个函数应该是一个比较两个string是否相等的函数(其实可以仔细看看这个函数的实现,但是这里不详述)。
然后我们就可以gdb调试了,如下:
1 | $ gdb bomb |
根据以上分析可以发现,程序将输入的字符串存储进默认的第一个参数储存寄存器%rdi,将固定地址0x402400的字符串存储到默认的第二个参数储存寄存器%rsi(%esi取其低32位),然后调用strings_not_equal函数对比这两个参数,那么我们可以大胆猜想,希望我们输入的即为字符串Border relations with Canada have never been better.
,如下:
1 | $ ./bomb |
可以发现,phase_1还是比较简单的。
phase_2
和前面一题一样,进去以后发现调用了read_six_numbers函数,字面意思就是读取6个数,需要注意的是,这时候如第四行所示sub $0x28,%rsp
,在栈内留下了0x28大小的空间,且mov %rsp,%rsi
将此时的栈地址赋值给了%rsi寄存器。
1 | 0000000000400efc <phase_2>: |
然后我们进入read_six_numbers函数,上来第2行就预留了0x18大小的空间,这是为6个int大小的整数准备的。
1 | 000000000040145c <read_six_numbers>: |
后面的操作看起来有些奇怪,其实理解了sscanf函数的形式就理解了,sscanf函数的在这里有8个输入参数,第一个参数是input;第二个参数是模式串,如下,在执行到sscanf函数前查看%rsi:
1 | (gdb) i registers rsi |
第三到第八个参数是读取后6个值的存储地址,分别为%rdx,%rcx,%r8,%r9.(%rsp),8(%rsp)处,对应着0x00(%rsi),0x4(%rsi),0x8(%rsi),0xc(%rsi),0x10(%rsi),0x14(%rsi),0x18(%rsi),最重要的是,我们要记住,在执行mov $0x4025c3,%esi
之前,%rsi存储的值是phase_2刚进来执行完sub $0x28,%rsp
时的栈帧值,故而相当于将sscanf的结果输出到phase_2预留的栈帧中。
从read_six_numbers返回到phase_2函数后,根据以上分析,在下列第7行时,%rsp存储的地址上存储的就是输入6个数中的第一个数,根据代码是和1相比较,如果不等就bomb,所以第一个数一定是1。
1 | 0000000000400efc <phase_2>: |
如果第一个数是1,则跳往0x400f30地址,这里将接下来的下一个地址赋值给%rbx,将最大的地址赋值给%rbp,然后跳往0x400f17。从0x400f17开始的代码含义是,拿后一个数和前数的两倍进行比较,相等就跳入0x400f25,不相等就爆炸;而0x400f25处的代码是和最大的地址进行比较,这类似于于for循环的计数。所以很明显可以看出,输出的就是以1开头,2为公比,一共6个的等比数列,即{1,2,4,8,16,32},如下:
1 | $ ./bomb |
phase_3
我们继续查看phase_3的汇编代码,可以看到调用sscanf函数来读取参数。
1 | 0000000000400f43 <phase_3>: |
然后第二个参数地址是0x4025cf,在gdb调试中查看,可以发现是读取两个整数。
1 | (gdb) x /s 0x4025cf |
继续查看,发现返回值是和1进行比较,需要大于1,而sscanf的返回值表示读取的个数,我觉得这是不严谨的地方,其实输入两个以上的数字也不会报错。
1 | ... |
接下来对读取的第一个数,也就是输入的第一个数和7比较,只要0-7都是可以的。然后间接跳转到一个地址,这个地址是多少取决于输入的第一个数。
1 | ... |
我们看看这个数随着我们输入的数的变化。
1 | (gdb) x 0x402470 # 输入的第一个数为0 |
发现跳往这些步骤的操作都是一样,即将第二个数与某一个固定的数对比,相等才能通过,譬如当第一个数为0时,第二个数必须为0xcf,也就是207,总结下来如下表:
输入第一个数 | 输入的第二个数 |
---|---|
0 | 207 |
1 | 311 |
2 | 707 |
3 | 256 |
4 | 389 |
5 | 206 |
6 | 682 |
7 | 327 |
以输入第一个参数等于0为例,如下:
1 | $ ./bomb |
phase_4
我们发现phase_4的前面几行和phase_3没有区别,说明也是读入两个整数,第一个参数需要比14小;然后通过输入func4中进行比对,需输出为0,且func4有三个入参,其中第一个参数x
即为我们输入的第一个参数,第二个参数y
为0,第三个参数z
为14(0xe),func4应该是比较复杂的函数,还用到了递归,但是我们可以走最简单的路线,也就是当满足x=((z-y)+((z-y)>>31))/2+y
时,带入参数,即x=7
时,func4输出为0,这种情况最为简单。
1 | 0000000000400fce <func4>: |
第二个参数需要和0相等,取0即可,所以可以输入:7 0,如下(其它情况就不列举了):
1 | $ ./bomb |
phase_5
首先进入phase_5会进行一系列的常规操作,然后调用了string_length函数,结果和6比较,不相等则bomb,所以应当输入一个长度为6的字符串。然后直接跳转到4010d2地址,这里只是将eax寄存器置零后再跳转到40108b位置。
1 | 0000000000401062 <phase_5>: |
接下来就进入到正题了,可以发现,401067行将输入的第一个参数传递给了rbx,我们可以用指令在gdb上查看,发现正是输入字符串的地址。再回到40108b行,这一行将从rbx开始的第一个byte输入到ecx中,其实也就是我们输入的第一个参数,然后将这个数进行了传来传去传到rdx中,最后和0xf进行与操作,并将结果存入rdx。然后将地址0x4024b0(%rdx)的那个byte存入edx,并最后存入0x10(%rsp,%rax,1)(注意此时rax=0),即此地址从0x10(%rsp)开始,后续会持续6此,每次持续中将rax加一,结合前面的操作,可知是将输入的字符串中6个字符依次取出进行以上操作作为索引,从地址0x4024b0(%rdx)依次取出字符组成的字符串和存储在0x40245e处的字符串进行对比,使之相等即能通过测试,而两处的字符串分别为:
1 | (gdb) x /s 0x4024b0 |
分析一下可知,和0xf与操作只能得到0-15的索引,而字符串”maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?”前十六个里面(”maduiersnfotvbyl”)包含了”flyers”的每个字符,所以可以取成功。譬如,’f’在索引9处,我们可以取字符’I’(0x49);’l’在索引15处,我们可以取字符’O’(0x4f);’y’在索引14处,我们可以取字符’N’(0x4e);’e’在索引5处,我们可以取字符’E’(0x45);’r’在索引6处,我们可以取字符’F’(0x46);’s’在索引7处,我们可以取字符’G’(0x47)。最后答案如下:
1 | $ ./bomb |
当然,这题还有很多满足条件的答案。
phase_6
phase_6的代码如下:
1 | 00000000004010f4 <phase_6>: |
代码很长,分析如下:
首先保护现场,压栈操作;然后依次读取了6个数,可以记作a0-a5;大循环,要求ai<=6,包含小循环,要求任意的ai!=aj (i>j);然后操作ai=7-ai;最后会发现一个地址,这个地址是一个链表,几经查找才打印出以下信息:
1 | p /x *0x6032d0@24 |
可以分析出,这个链表有6个元素,分别是{val, index, next, 0, val, index, next, 0, …}这样的排列。
最后一段逻辑是将第a0, a1, …, a4个节点的next设置为第a1, a2, …, a5个节点,第a5个节点的next为空,要求链表每个节点的值要大于他的next节点的值,否则爆炸。
根据以上打印的链表值,从大到小应该是3 4 5 6 1 2的顺序排列,而经过前面ai=7-ai的变化,所以应该是4 3 2 1 6 5。
我们将以上答案写进一个名为anwser的文件中,如下:
1 | Border relations with Canada have never been better. |
运行如下:
1 | $ ./bomb answer |
secret_phase
secret_phase函数不是在main函数里调用的,而是在phase_defused函数里调用的,这个不查看反汇编代码很难察觉,是个隐藏关。
phase_defused的代码如下:
1 | 00000000004015c4 <phase_defused>: |
我们注意4015d8行,这里把常数6和一个固定地址603760(即常量num_input_strings的地址)进行对比,当不等时直接退出函数,相等时继续执行4015e1后的代码。后面的代码其实挺好理解的,即调用sscanf函数,我们查看以下两个地址:
1 | (gdb) x /s 0x402619 |
第一个正是读入两个整数一个字符串,第二个地址正式phase_4中的输入(说明我们仅输入两个数无法触发secret_phase),然后会将这个输入分别装到0x8(%rsp),0xc(%rsp)和0x10(%rsp)中,再拿0x10(%rsp)中的字符串和0x402622地址的字符串对比,如果相等才会触发secret_phase。
1 | (gdb) x /s 0x402622 |
所以我们在phase_4的输入中外加字符串”DrEvil”即可触发secret_phase,其函数如下:
1 | 0000000000401242 <secret_phase>: |
总结起来就是输入一个数,通过strtol函数转化为long型(不允许超过0x3e8),然后将这个数作为第二个参数输入fun7,第一个参数是立即数0x6030f0,我们继续进入fun7。
1 | 0000000000401204 <fun7>: |
以下均参考csapp-Bomblab总结。
fun7是一个递归函数,总结起来就是下面:
1 | if ( [rdi] > esi ) |
我们希望fun7的返回值是2,而2 = ((((0*2)*2)*2…)*2+1)*2
,因此第一个调用需要进入第一分支,第二次调用(第一次递归)进入第二个分支,后续如果还有,则不能进入第二分支。所以我们查看一下从0x6030f0之后的地址内容:
1 | (gdb) x /60a 0x6030f0 |
从节点的关系可以看出这是一个二叉树,[rdi + 0x8]是左儿子的地址,[rdi + 0x10]是右儿子的地址,且该二叉树的深度只有4,根据以上分析,只有root->Lch->Rch和root->Lch->Rch->Lch这两种情况,即<n32>节点和<n43>节点两种情况,即输入值是0x16=22和0x14=20,这就是这题的答案。
答案
我们将这些答案写在answer文件中,文件和运行结果分别如下:
1 | Border relations with Canada have never been better. |
1 | $ ./bomb answer |