更适合北大宝宝体质的 Bomb Lab 踩坑记

2 个月前(已编辑)
/ ,
84
AI 生成的摘要
文章详细介绍了CSAPP课程中Bomb Lab的解题过程。它首先强调了理解和分析汇编代码的重要性,然后逐步介绍了如何通过观察、分析和使用gdb工具来解决每个Phase的问题。其中详细解释了如何安全地拆解炸弹、读懂汇编指令、使用gdb的各种命令以及解析复杂的条件分支和循环。最后,作者通过自己的经验强调了实践和耐心对于理解底层编程的重要性。

写在前面:我写本篇博文的目的是为了帮助同学们更好的完成 lab,而不是完全的直接帮你把 lab 写完,且不说每个人的炸弹都不一样,如果你完全的照搬我的方法,而不去思考每条汇编指令的意义,去学习它们,那么你一定会在考试中吃大亏。

在做这个 lab 之前,推荐安装 VS Code x86 and x86_64 Assembly 扩展,以获得汇编的语法高亮。

在 Bomb lab 里,我们需要拆除一系列的炸弹,每个炸弹都有一个密码,我们需要通过输入正确的密码来拆除炸弹。如果输入错误,炸弹就会爆炸,而每次爆炸,我们都会失去 0.5 分(上限 20 分)

所以,对于程序一无所知的我们,显然不能直接莽撞地直接去猜密码,而是需要借助拆弹工具 gdb 来帮忙防止爆炸,同时通过阅读源码和反编译出的汇编代码来分析程序的逻辑,从而找到正确的密码。

阅读源码

想要拆弹,肯定首先要阅读源码。这个 lab 的源码在 bomb.c 中,可以看到这个程序的主要逻辑大概是:

可以看到,这个程序的每个阶段都是通过 phase_x 函数来实现的,而 phase_x 函数的参数是 input,也就是我们输入的字符串。所以,我们的目标就是找到每个阶段的 input,然后通过分析 phase_x 函数来找到正确的 input

首先让我们来反编译一下整个 bomb 这个二进制程序:

阅读源码,我们发现每个 phase 都大概具有如下结构:

可以看到,每个 phase 内都有一个类似于 jne 的条件跳转指令,跳转到 explode_bomb 函数,也就是说,如果我们的输入不正确,就会引爆炸弹。那么,一个很重要的事情,就是在其真正进入引爆流程之前,我们一定要打断这个函数的执行。

这就需要使用到 gdb 工具了。

有关 gdb 的具体指令简介,在书上的 3.10.2 小节,我推荐大家在做 bomb lab 之前一定要提前看一下。

在此,我只介绍一些我在做这个 lab 时用到的一些指令。

指令简称描述
rrun开始执行程序,直到下一个断点或程序结束
qquit退出 GDB 调试器
ninexti执行下一条指令,但不进入函数内部
sistepi执行当前指令,如果是函数调用则进入函数
bbreak在指定位置设置断点
ccont从当前位置继续执行程序,直到下一个断点或程序结束
pprint打印变量的值
x打印内存中的值
disas反汇编当前函数或指定的代码区域
layout asm显示汇编代码视图
layout regs显示当前的寄存器状态和它们的值

我一般启动 gdb bomb 后,都会首先使用 layout asmlayout regs 开启视图,方便分析。

关于 px,最重要的就是记得 p 命令用于打印表达式的值,而 x 命令则主要用于检查内存的内容。几个常用示例如下:

关闭 layout 的方式为,按下 Ctrl + x,然后再按下 a

这些命令在 / 后面的后缀(如 2x2dsg20c)指定了查看内存的方式和数量。具体来说:

  • 第一个数字(如 220)指定要查看的单位数量。
  • 第二个字母(如 xdsgc)指定单位类型和显示格式,其中:
    • x 代表十六进制。
    • d 代表十进制。
    • s 代表字符串。
    • g 代表 giant,即 8 字节。
    • c 代表字符。

安全化炸弹

一个随时会引爆的炸弹总是让人胆战心惊,但如果是一个安全的炸弹,那我们就可以放心地去拆弹了。

把炸弹安全化的方式有两种,它们都需要分析 objdump 反汇编出的代码,然后:

  • 找到相关代码,再利用 hexedit 工具修改二进制码,替换条件跳转指令或者使用 nop 无义指令替换危险指令。
  • 找到相关代码,再利用 gdb 工具为危险函数或者危险指令设置断点,并对于断点处进行编程,跳过危险指令或者修改寄存器的值来控制条件跳转,使得炸弹不会爆炸。

在此,我仅介绍第二种方法。

gdb 有一个很实用的功能,就是我们可以使用 .gdbinit 文件来设置 gdb 进入时的一些默认配置,这样我们就不用每次都手动输入一大堆的指令。

为了实现此功能,我们首先进行如下配置:

然后,我们打开 ./.gdbinit 文件,输入如下内容:

因为每年的炸弹可能不一样,所以授人以鱼不如授人以渔,我在此详细的介绍一下如何安全化炸弹的过程,请大家自行阅读自己的代码,调整其中的参数,以适配自己的炸弹。

炸弹的执行有如下流程:

首先,在开始时校验是否被本地化,如果检测到被本地化,则直接退出

由于我们没有通过修改二进制码的方式来本地化炸弹,所以我们不需要处理这里,但还是给出一个跳过这个 if 语句的 gdb 调试方法供参考:

然后,在每个 phase 里检验是否输入了正确的密码,如果输入错误则调用 explode_bomb 函数,打印 BOOM!!!,并在其中调用 send_msg 函数,向服务器发送通知

我们的代码,通过在 call 1fb1 <send_msg> 这一句处设置断点,然后直接跳到 call 1390 <exit@plt> 这一句处,完整的跳过了 send_msg 函数的执行,从而使得服务器无从知道我们的炸弹爆炸了。

这对应我们的 .gdbinit 文件中的如下代码:

其中两个断点的计算方式为:

由于 explode_bomb 函数的地址为 0x211b,而 call send_msg 指令的地址为 0x215f,所以 call send_msg 指令的偏移量为 0x215f - 0x211b = 0x44

同理,call exit 函数的地址为 0x219c,所以 call exit 函数的偏移量为 0x219c - 0x211b = 0x81

或许你会问为什么不直接使用 b 0x215fb 0x219c 来设置断点?这是因为我们的炸弹每次运行的地址都不一样,所以我们需要使用相对地址来设置断点。而这点你会在后续学习第七章链接的时候有所了解,或者是在做下一个 Attack Lab 的时候就会知道了,这就是地址随机化(Address Space Layout Randomization,ASLR)。

最后,在每个 phase 里,如果输入正确,则调用 phase_defused 函数,同服务器进行通信,(同学学号报一下,给你加创新学分),将你输入的字符串发送到服务器进行远程校验,避免你在本地使用 gdb 跳过 explode_bomb 函数的执行的情况。

类似于上面的修改,我们的代码通过在进入 phase_defused 函数的第一句话处设置断点,然后直接跳到 ret 这一句处,避免了同服务器的通信:

其中,断点的计算方式为:

由于 phase_defused 函数的地址为 0x2331,而 ret 指令的地址为 0x235b,所以 ret 指令的偏移量为 0x235b - 0x2331 = 0x2A

这里的跳转其实似乎并不是必要的,我在这里必须使用这段跳转的原因是我是在 DDL 已经过了情况下重新做这个 lab 写教程的,此时测评服务器已经拒绝接收 Bomb lab 的任何请求,所以如果不加这段会报 HTTP 错误,进而导致整个程序退出。

而如果你是在 DDL 之前做这个 lab,那么你完全不需要这段代码,因为将你的输入发送到服务器进行远程校验正是你所需要的。

当然,如果你不放心,你也可以将之加入到你的 .gdbinit 中,只不过你会缺少成功拆弹的提示,只能凭借运行逻辑来判断是否成功拆弹罢了。

注:尽管 phase_defused 函数内有调用 send_msg 函数,但是我们并没有修改 send_msg 函数的执行,而是在炸弹爆炸(即触发 explode_bomb)了的时候,跳过了 send_msg 函数的执行,所以这里的 send_msg 函数仍然会被正常执行,不用担心。反之,在炸弹爆炸的情况下,其会跳转并调用 exit 函数,所以也不会运行到 phase_defused 函数处。

启动拆弹:

当你完成上述一切操作的时候,你应该就能获得如下的效果:

safety-bomb

safety-bomb

注:这里输入的 psol.txt 中,phase 1 的答案正确,而 phase 2 的答案错误。

于是我们可以看到,我们的炸弹现在即使被引爆,也不会通知到服务器(不然我这个超过 DDL 的尝试会直接导致程序终止),这下我们就可以放心地去拆弹了(而且但它依然能正确的打印爆炸信息供我们识别!)。

Phase 1

首先,我们通过查找 bomb.asm,找到反编译出的 phase_1 函数的代码,然后阅读一下:

考虑到这是大多数同学接触到的第一段汇编代码,所以我在此详细地介绍一下这段代码的含义。

  1. endbr64:一句无关紧要的指令,用于防止 ROP 攻击,我们可以忽略它。

  2. sub $0x8,%rsp:将栈指针(%rsp)向下移动 8 个字节,为 call 指令的返回地址腾出空间。

  3. lea 0x2a69(%rip),%rsi:正如书上所提到的,leaq 指令全称为 load effective address,加载有效地址,但它并不会真的去访存然后再反算地址,它就是简单的把计算出来的地址放到你所需要的地方,所以它经常被用于做一些计算。

    这里的 lea 指令的含义是,将内存 0x2a69(%rip) 处的地址(也就是 0x2a69 + 0x17a7 = 0x4210)赋值给 %rsi。注意 %rip 这个东西的值不是它所处的这行代码的地址,而是下一条!同时,%rsi 代表的是函数运行的第二个参数。

    为什么 %rip 的值不是它所处的这行代码的地址,而是下一条?

    当你学完第四章处理器体系结构的时候,你就会知道。

    在这里做个简要的说明就是,当 CPU 读取并执行这条指令的时候,由于它已经读取完这条指令,所以 %rip 程序计数器的值已经指向了下一条指令的地址,而不是这条指令的地址。

  4. call 1db8 <strings_not_equal>:调用 strings_not_equal 函数。也即首先将 %rip 的值(也就是下一条指令的值,0x17ac)压入栈中,然后跳转到 strings_not_equal 函数的地址处执行。注意这里由于我们从 main 函数到这里一直没有修改 %rdi (也就是存放第一个参数的寄存器)的值,所以我们传入的第一个参数实际上是 mainread_line 函数的返回值(见 0x15b6 处),也就是我们输入的字符串的地址。而第二个参数就是我们上一条指令传入的 %rsi,它的内容也是一个地址,指向内存 0x2a69 的位置。

  5. test %eax,%eax:将 %eax 寄存器的值与其自身进行与运算,然后将结果存入 %eax。并且同时设置条件码(Condition Code),其中有一个叫做 ZF 的标志位,如果 %eax 的值为 0,则 ZF 为 1,否则为 0。

  6. jne 17b5 <phase_1+0x1d>jne 指令在上一条指令结果非 0 的情况下跳转,其具体的判断条件为 ZF = 0(这里可以参照书 P135 页,或者 3.6.1 章条件码),也就是说,如果 ZF 为 0(这对应我们调用 strings_not_equal 返回了一个非零值,代表我们没能成功匹配),则跳转到 0x17b5 的地方,也就是 call explode_bomb 的语句,进而引爆炸弹。

  7. add $0x8,%rsp:只有当上一条指令没有跳走的情况下才会执行(这代表我们答对了)。将栈指针(%rsp)向上移动 8 个字节,恢复栈指针的位置。

  8. ret:返回,将栈顶的值(也就是 0x17ac)赋值给 %rip,再将栈指针向上移动 8 个字节,恢复栈指针的位置,然后跳转到 %rip 所指向的地址处继续执行。相当于 phase_1 这个函数执行完毕,返回到 main 函数的 0x15be 处继续执行。

  9. call 211b <explode_bomb>:调用 explode_bomb 函数,也是首先将 %rip 的值(也就是下一条指令的值,0x17ba)压入栈中,然后跳转到 explode_bomb 函数的地址处执行。当 explode_bomb 函数执行完毕后,会返回到下一条指令,也即 0x17ba 处继续执行。

  10. jmp 17b0 <phase_1+0x18>:无条件跳转到 0x17b0 处,即进入(7)处,完成 phase_1 的退出流程,还原栈针,返回。

这里写的真的很细碎,但我还是觉得对于初学者而言可能恰恰需要的就是这种细碎的解释,所以如果你觉得你掌握的很好了,那你随便扫两眼就行了。

所以,我们得到了解决这个 phase 的关键信息,就是我们要使用 gdb 在执行 call strings_not_equal 之前,获取到 %rsi 的值(也就是正确答案),就可以了。

首先我们打开 psol.txt,随便输入一行字符串,比如

然后,我们打开 gdb,并且设置断点:

运行截图如下:

phase1

phase1

从而我们得到了 phase 1 的正确答案:

使用两次 Ctrl+D (这标志着我们的输入结束,即 EOF )退出 gdb,然后将正确答案写入到 psol.txt 第一行:

然后重新运行程序:

phase1-finish

phase1-finish

可以发现我们已经正常的从 phase_1 函数返回了,而没有进入 send_msg 函数,而是返回到 bomb.c 中的下一句 phase_defused 函数的执行处了。这就代表我们已经成功的完成了 phase 1。

由于我为了规避服务器超期检查,使用 gdb 跳过了 phase_defused 函数的执行,但你们如果前面没有做这个操作而是正常执行的话,那么服务器应该就会收到你的答案并更新 AutoLab 的成绩了。

可以看到,继续执行后就进入了 phase 2。

Phase 2

依旧是先找到 phase_2 函数的代码:

其实这段代码对于如今的我而言已经是非常简单的了,尽管我尽可能地以初学者的角度讲述,但是我还是可能会忘记一些当时的困惑,所以如果你有任何问题,欢迎在评论区或者 issue 中提出。

直接对着反汇编出来的代码在脑子里空想可能并不是一个很好的办法(除非你真的可以用你的大脑模拟出一台计算机来),所以我建议你找一张纸或者在 iPad 上用 GoodNotes 之类的软件画一下这段代码的流程图,并一行一行地标注,大概了解其运行逻辑后,再结合 gdb 来调试,我当时的笔记大概就长这样:

phase2-notes

phase2-notes

我们首先来阅读 phase_2 函数的代码。

这一段代码是一个很典型的函数开头,使用 endbr64 来防止 ROP 攻击,然后压栈 %rbx

回忆一下, %rbx 是一个被调用者保存的寄存器,除了 %rbx 之外还有 %rbp%r12%r15,你可以通过 %rbx%rbp 中的 b 是 Backup 的首字母来记忆,另外再强记一下 %r12%r15 就行了。

接着再将 %rsp 栈针减去 0x20(注意是十六进制,也就是 32 个字节)扩大栈,然后使用 mov %fs:0x28,%rax%fs 段寄存器中的 0x28 处的值(也就是 0x28 + %fs 处的值)赋值给 %rax,再复制到栈指针往上 24 个字节处(也就是 %rsp + 0x18 处)存储起来。

这代表了一个你在后续 Attack lab 中会遇到的东西,叫做 “金丝雀值(Canary Value)”,用于防止缓冲区溢出攻击(Buffer Overflow Attack)。这个值会在函数的结尾处进行校验,如果发现被修改了,就会抛出异常,阻止程序继续执行。

我们也可以看到,在函数的结尾处,会将 %fs 段寄存器中的 0x28 处的值(也就是 0x28 + %fs 处的值)赋值给 %rax,然后与之前保存在栈中的金丝雀值进行异或运算,如果结果不为 0,则说明金丝雀值被修改了,就会抛出异常,阻止程序继续执行(call 1290 <__stack_chk_fail@plt> 一句)。

为什么要使用 fs 段寄存器?

这是因为 fs 段寄存器是一个特殊的寄存器,它的值是由操作系统决定的,而不是由程序决定的,所以它的值是不会被修改的,这样就可以防止被恶意修改。

这段代码是 phase_2 的核心语句。我为它添加了额外的注释,希望能够方便大家理解。

这段代码是很经典的汇编循环语句,通过维护一个循环变量 %ebx,来控制循环的次数与计算每次访存的地址,它很类似于下面的 C 语言代码:

注意一个 int 类型需要 4 个字节来存储,这就是为什么我们计算变址的时候要乘以比例因子 4。

尽管我们现在已经知道了核心的代码逻辑,但是我们还有一件事情不确定,那就是 read_six_numbers 函数的具体实现。它决定了读入的六个数字是如何被存储的,所以我们还是需要阅读一下它的代码:

回忆一下 sscanf 函数的签名:

  • str:指向要读取的字符串。
  • format:指定输入格式控制。
  • ...:可变数量的额外参数,用于存储从 str 中按照 format 指定的格式提取出的数据。

返回值:成功返回成功匹配并赋值的数据项个数。

还是谨记 x86 的函数调用约定:

  • %rdi:第一个参数
  • %rsi:第二个参数
  • %rdx:第三个参数
  • %rcx:第四个参数
  • %r8:第五个参数
  • %r9:第六个参数
  • %rax:返回值

超出六个参数的部分,会被压入栈中。压栈顺序为从右到左,注意 栈是向下增长 的,所以第七个参数(也就是第一个开始不能被寄存器传递的参数)会被压在最下方(见课本图 3.25):

process-stack

process-stack

这里我们可以看到,调用 sscanf 函数的时候,我们传入了 7 个参数,其中前 6 个参数都是通过寄存器传递的,%rdi 是从 main 函数继承来的指向我们输入字符串的指针,%rsi 指向一个相对于 %rip 定位的字符串(这里你们会在第七章链接的地方学到,是一个重定向),指向一个应该是 "%d %d %d %d %d %d" 的字符串,然后 %rdx%r9 以及计算后压栈的 %rax 分别是指向我们要存储的六个数字的地址。

我们可以在 gdb 中使用 x/s $rsi 来查看 %rsi 指向的字符串,验证我们的猜想:

果不其然:

phase2-sscanf

phase2-sscanf

观察读入的顺序,%rdx 的值为 %rsi,也就是我们在 phase_2 中调用 read_six_numbers 函数时传入的 %rsp,即栈指针,这里会存放第 1 个读入的数字,然后以此类推依次向上存入后续的五个数字。

现在,我们已经彻底搞清楚了 phase_2 的逻辑:它调用 read_six_numbers 读入 6 个数字,将第 1 个数字存在栈顶,然后依次向上存储其余的 5 个数字,随后开启一个循环,首先对比第一个数字是否为 1,然后对比五次下一个数字是否为前一个数字的两倍,如果不是,就爆炸。

于是我们得到 phase 2 的答案:

将其写入 psol.txt 的第二行:

然后重新使用 gdb 运行程序,记得先在 .gdbinit 中注释掉 b phase_1 这个我们已经不需要的断点:

phase2-finish

phase2-finish

成功通过第二关!

Congratulations!

如果一切顺利的话,你甚至可以像我一样完全不借助 gdb 查看寄存器和内存的变化状况,仅仅通过阅读反汇编出来的代码就能够完成这个任务!

这种阅读能力是你必须要训练的,因为考试的时候你是没有办法使用 gdb 的,所以你必须要能够在没有调试器的情况下,通过阅读汇编代码来理解程序的运行逻辑。

Phase 3

phase 3 的反汇编代码看起来长的可怕:

从这个 phase 起,我将不再提供反汇编代码的逐行注释,这并不是因为我懒 好吧我承认,其实有点,而是因为我希望你们经过前两个 phase 的详细讲解,能够学会独立地阅读反汇编代码。

看上去的确很可怕,但我们稍加阅读就可以发现,其中有很多结构十分相同的语句,稍加分析就会发现,其在最开始依旧是使用 sscanf 函数来读入了三个东西(依次设置了 %rdx%rcx%r8 指向栈针上面的特定的位置),通过如下代码可以获得 %rsi 指向的格式字符串(仍旧记得先注释掉我们已经完成的 .gdbinit 中的 b phase_2 断点):

得到输出如下:

于是我们确定了,我们要输入的是一个数字、一个字符、一个数字:

  • 0x10(%rsp):为 %rdx 寄存器指向的位置,因而是第一个存储的数字
  • 0x14(%rsp):为 %r8 寄存器指向的位置,因而是第三个存储的数字
  • 0x18(%rsp):为 %rcx 寄存器指向的位置,因而是第二个存储的字符

继续阅读源码:

我们发现读入后,存在一个校验,将 %rsp + 0x10 处的值(也就是我们输入的第一个数字)与 7 进行比较,如果大于 7,就会跳转到 phase_3+0x159 处,也就是爆炸。

所以第一个数字必须小于等于 7。

接着,这里又一次相对 PC 进行了一个引用,存入 %rdx,再将 %rdx + %rax * 4 处的值赋值给 %rax,接着使用一个间接跳转,跳转到 %rax 处执行。

再结合我们之前发现的代码具有很强的结构相似性,我们可以猜测,这里的代码应该是一个 switch 语句,根据我们输入的第一个数字,跳转到不同的位置执行。

接下来的事情就好办了。随便输入一个符合的字符串,然后观察一下代码会跳到哪里继续执行,然后我们就只用分析那一块的代码就可以了。

在这里,我选择的输入是:

注:213 是 CSAPP 的 CMU 课程号~

将之加入到 psol.txt 的第三行:

然后重新使用 gdb 运行程序:

phase3-switch

phase3-switch

观察到我们跳转到了 194c 这里(以代码检索,不要以地址检索,因为地址随机化了):

回顾一下之前准备 sscanf 的参数的时候,我们知道 0x14(%rsp) 是指向我们输入的第三个数字的,所以这里的代码是在比较我们输入的第三个数字是否为 0x362,稍加计算便知道, 0x362 是十进制的 866,所以这里的代码是在比较我们输入的第三个数字是否为 866,如果不是,就爆炸。

如果这个语句发现匹配的话,那么会继续执行 1956 处的代码,将 %eax 置为 0x71,然后跳转到 1990 处。

继续阅读 1990 处的代码,我们发现,这里又是一个校验,将 0xf(%rsp) 处的值(也就是我们输入的第二个字符)与 %al(对应于 %rax 的低 8 位)进行比较,如果不相等,就爆炸。

而稍加转换,就知道 %al 的值为 0x71,也就是 q,所以这里的代码是在比较我们输入的第二个字符是否为 q

从而我们得到了 phase 3 的答案(之一):

将其写入 psol.txt 的第三行:

然后重新使用 gdb 运行程序:

phase3-finish

phase3-finish

成功通过第三关!

Phase 4

phase 4 的代码量看起来就正常多了:

依旧是老规矩,首先注释掉 .gdbinit 中的 b phase_3 断点,然后使用 gdb 运行程序

得到输出:

从而我们知道,我们需要输入两个数字。根据代码,我们知道,第一个数字会被存储在 %rsp + 0x0 处,第二个数字会被存储在 %rsp + 0x4 处。

继续阅读代码:

我们发现程序首先检验了 %rsp 处的值是否为 5,如果不是,就爆炸。

随后,通过两句 mov 指令,将 %ebp%ebx 置为 0,然后比较 %ebx(%rsp) 处的值。

如果 (%rsp) 处的值小于等于 %ebx,就跳转到 1a4d 处,这代表了这个循环的跳出。然后它会继续继续比较 %ebp0x4(%rsp) 处的值(也就是我们输入第二个参数),如果不相等,就爆炸。

如果不是的话,就将 %ebx 的值赋值给 %edi(代表第一个参数),然后调用 func4 函数,将返回值加到 %ebp 上,然后将 %ebx 加 1(从这里可以看出这个是一个循环标记),然后跳转到 1a3a 处,也就是继续比较 %ebx(%rsp) 处的值。

从而我们可以大致得到 func4 函数的逻辑:

那么接下来的关键,就是分析 func4 函数的逻辑,并确定对于它的返回值累积 5 次后,会得到一个什么样的值。

我们发现,这个函数首先检查了 %edi 的值是否小于等于 0,如果是的话,就返回 0。

如果不是的话,它会先保存(压栈)两个被调用者保存的寄存器 %rbp%rbx,然后将 %edi 的值赋值给 %ebx(保存初始传入的参数),接着比较 %edi 和 1 的大小,判断 %edi 是否为 1。

如果是的话,就跳转到 19ee 处,将 %edi 的值赋值给 %eax,再跳回到 19e1 处,完成对于被调用者保存的寄存器的恢复(弹栈),然后返回。

如果不是的话,就将 %edi 减 1,然后调用 func4 函数,使用返回值 %rax 计算一个 %rax + %rax ,也就是 2 * func(%edi - 1),存入 %ebp

接着,它将 %ebx 减 2,然后再次调用 func4 函数,把新的返回值 %rax 又一次加到 %ebp 上。

最后,它会弹栈,恢复 %rbx%rbp 的值,然后返回 %eax

于是我们可以得到 func4 函数的逻辑:

从而我们得到这个函数的函数表:

afunc4(a)
00
11
22
35
412

从而我们可以得到,这个 phase 4 中累积 5 次调用 func4 函数得到的 %ebp 的值应该为 20。

其实这里还有一个取巧的办法,就是我们完全不用分析 func4 函数的逻辑,而是直接使用 gdbcmp %ebp,0x4(%rsp) 这一句比较的时候,打印出来 %ebp 的值即可。

最终,我们可以得到 phase 4 的答案:

将其写入 psol.txt 的第四行:

然后重新使用 gdb 运行程序:

phase4-finish

phase4-finish

半途已过!

Phase 5

依旧很长:

老规矩,先注释掉 .gdbinit 中的 b phase_4 断点。

不同于过去的几个 phase,我们发现这里没有调用 sscanf 函数,而是直接调用了 string_length 函数,这个函数的作用是计算字符串的长度。

结合代码,我们得知需要输入的是一个长度为 6 的字符串。

那么,我们首先修改 psol.txt,随便输一个字符串试试:

注意这里是一定要多一行的,否则会识别错误。

继续来看剩下的核心代码:

我们发现,这里首先将 %eax 置为 0,然后比较 %eax 和 5 的大小,如果大于 5,就跳转到 1acb 处。从而我们可以结合之前的经验,立刻推断出这里应该是一个循环,循环的次数为 6 次,而 %eax 即为循环变量。每个循环体内,%rcx 都会被首先赋值为 %eax

继续阅读,发现这里计算变址用到了 %rbx,往上找发现这个寄存器被赋值为 %rdi,而 %rdi 是我们传入的第一个参数,也就是我们输入的字符串。

这里的变址计算等价于从我们输入的字符串中取出一个字符,然后赋值给 %edx。接着,我们发现它对 %edx 进行了一个 and 0xf 的操作。

我们知道,一个字符(char)类型占有 1 个字节,也就是 8 位,而 0xf 的二进制表示为 0000 1111,也就是说,这里的操作等价于将 %edx 的值的高 4 位清零。

接着,它将 %rsi 设置为一个地址,通过反汇编给出的注释我们发现这是一个数组,因而我们使用 gdbx 命令打印出来:

phase5-array

phase5-array

我们发现这个字符数组 / 字符串的内容是:

而后,它又使用之前花了大力气计算来的 %rdx 的值作为下标,从 %rsi 指向的数组中取出一个字符,赋值给 %edx。再取出 %edx 的低 8 位,即 %dl,存入 %rsp + %rcx + 1 处,即从栈顶开始往上存。

使用循环重复这个过程 6 次,我们就可以在 %rsp + 1 开始的 6 个字节中存入 6 个跳来跳去获得到的字符。

1aa4 跳出循环后,我们发现它将 %rsp + 0x7 处的值置为 0,然后将 %rsp + 0x1 处的值赋值给 %rdi(第一个参数),将 %rsp + 0x26d2注意这里和之前不一样!)处的值赋值给 %rsi(第二个参数),然后调用 strings_not_equal 函数判断是否相等。

我们首先使用 gdbx 命令打印出 %rsp + 0x26d2 这里开始的 6 个字符,从而获知我们要凑的字符串是什么:

phase5-devils

phase5-devils

最终,我们发现这里需要匹配上的字符串是:devils

这个过程不可谓不离奇曲折,但是当我们知道了具体的过程之后,就可以很容易地得到答案了。

首先,我们先去维基百科找来一张 ASCII 码表

ascii

ascii

然后我们开启反向解码操作:

  1. 第一个需要的字符为 d,由于我们可以指定的 %rdx 的值的范围为 0 ~ 15(这刚好对应 "So" 前面的 "maduiersnfotvbyl" 这 16 个字符)。其中 d 位于第 3 个,也就是需要选择一个低 4 位为 0010(索引为 2)的字符,选择 b 即可。
  2. 第二个需要的字符为 e,类似地,e 位于可用字符串的第 6 个,也就是需要选择一个低 4 位为 0101(索引为 5)的字符,选择 e 即可。
  3. 第三个需要的字符为 v,类似地,v 位于可用字符串的第 13 个,也就是需要选择一个低 4 位为 1100(索引为 11)的字符,选择 l 即可。
  4. 第四个需要的字符为 i,类似地,i 位于可用字符串的第 5 个,也就是需要选择一个低 4 位为 0100(索引为 4)的字符,选择 d 即可。
  5. 第五个需要的字符为 l,类似地,l 位于可用字符串的第 16 个,也就是需要选择一个低 4 位为 1111(索引为 15)的字符,选择 o 即可。
  6. 第六个需要的字符为 s,类似地,s 位于可用字符串的第 8 个,也就是需要选择一个低 4 位为 0111(索引为 7)的字符,选择 g 即可。

最终,我们可以得到 phase 5 的答案:

将其写入 psol.txt 的第五行:

然后重新使用 gdb 运行程序:

phase5-finish

phase5-finish

拿下!

Phase 6

最后一关了,也是最难的、代码长的最离谱的一关:

仍旧是先注释掉 .gdbinit 中的 b phase_5 断点。

在做这个 phase 之前,我建议大家先做好心理准备,这个 phase 可能光读懂它就需要数个小时,这是我当初做的笔记:

phase6-notes

phase6-notes

略过前面常规的压栈保存被调用者保存寄存器、金丝雀值处理,我们直接进入核心部分:

我们发现,就像 phase 4 一样,这里首先通过 read_six_numbers 函数读入了 6 个数字(依次存放在 %rsp%rsp + 0x18 的 24 个字节处),然后将 %ebp 置为 0,再进行了一个比较 cmp $0x5,%ebp,如果大于 5,就跳转到 1b75 处。

很显然,这里又是一个循环,循环变量为 %ebp,循环次数为 6 次。

接着看 1b5e 开始的几句指令,我们发现每次循环内,首先读出了一个我们输入的数字,然后减 1,再判断是否大于 5,如果大于 5,就跳转到 1b32 处,引爆炸弹。

这告诉我们,我们输入的每个数字必须小于等于 6。

接着跳转回 1b3c 处,继续循环。我们阅读 1b39 ~ 1b54 的这一段指令,可以发现它通过维护了另外一个循环变量 %ebx,来遍历比较了我们输入的第 1 个数字和后面 5 个数字,如果有相等的,就会爆炸。

继续类推,观察到每次退出这个由 %ebx 控制的子循环后,会在 1b56 处将 %r12d 的值存入 %ebp,从而更新外层循环变量。

于是我们不难推断,这类似于一个冒泡排序:

所以这段代码的目的,就是判断我们输入的 6 个数字是否有重复的。

因而我们得知,我们输入的 6 个数字必须是不同的。

所以我们更新 psol.txt,将第 6 行更改为符合要求的数字:

继续看下面的代码:

不难看出这里还是执行了一个循环,循环变量为 %esi,循环次数为 6 次。

继续阅读代码,发现在 1b8e 处读取了一个叫做 node1 的东西的地址到 %rdx,很自然的联想到这应该是一个线性表,而且大概率是一个链表。我们首先使用 gdbx 命令打印出 %rdx 的值:

得到输出:

一下子打印出来 5 个节点,可以看出每个节点的 16 个字节中,最低的 4 个字节是一个大小范围合适的数字,猜测是链表节点的 value 信息,而次低的 4 个字节是一个从 1 开始的递增的数字,猜测是链表节点的 key 信息,而最高的 8 个字节看不出来是个什么东西,所以我们换用 16 进制打印:

得到输出:

再次观察每个节点的最高 8 个字节,结合我们上课学习的知识,我们知道在现在主流的机器中都采用小端法表示,而且为 64 位机器,所以指针的长度是 8 个字节,进而我们可以推测出,每个节点的最高 8 个字节应该是一个指向下一个节点的指针,譬如,对于 node1 来说,他的最高 8 个字节是 0x5f1db130 0x000055ee,也就是正常表示下的 0x000055ee5f1db130,而这个地址正好是 node2 的地址,所以我们可以推测出,每个节点的最高 8 个字节是一个指向下一个节点的指针。

也就是说,这个链表的每个元素大概是这样的:

结合我们之前发现整个循环会被执行 6 次,而这里只有 5 个节点,所以我们猜测 node6 应该是被存放在了别的地方,我们使用 node5 的最高 8 个字节推断出 node6 的首地址为 0x000055ee5f1da080,然后使用 x 命令打印出 node6 的内容:

得到:

发现不知道为啥打印出来是 16 进制,但是我们已经可以从这里看出 node6 的后继指针为 NULL,所以我们可以推断出,node6 是此链表最后的节点。

我们要求它打印出 10 进制:

得到:

从而我们得到了完整的链表内容:

到这里我们已经完全知道这个数据结构长啥样了,所以回去继续看代码(我懒得上下翻,我想大家应该也不想,所以又复制了一遍):

1b95 处开始继续看这个循环,我们发现直到 1b9b 它都会尝试匹配 %eax(不变)和你的输入(变化)的第 %esi 个数字,如果后者小于或等于 %eax ,就跳转到 1b7c 处(同时通过更新 %esi 循环条件进行顺位匹配),而 %eax 又是从 1 开始的,所以它在这里(第 1 次)随便一个 1 ~ 6 的数字都可以通过这个 jle 指令,继续后面的循环。但我们也很容易想到,这里的 %eax 应该会在后续过程中更新,而当它更新到 6 时,那么就只有 6 这个数字可以通过这个 jle 指令。

当通过这个 jle 指令后,进入到 1b9d 处,我们发现它会将 %rdx 更新为 %rdx 的后继指针,然后再将 %eax 加 1,再跳转回 1b95 处,继续循环。

所以我们发现无论什么情况,这里都会往回跳转,唯一跳出的方式是在 1b87 处,将 %esi 更新为 6 时。

而当我们关注 %esi 的时候,我们发下它只有在从 1b9b 跳转到 1b7c 时才会更新,而这个跳转只有在 %eax 没有通过 jle 时才会触发,也就是当 %eax 已经大于你的输入的第 %esi 个数字时,才会触发。此时,%rdx 已经变成了指向你输入的第 %esi 个数字的节点的指针。

所以,我们可以推断出这里的大致逻辑是:

所以,我们可以推断出,这里相当于将我们用户栈上 %rsp + 0x20 开始的一个 nodes 数组中的 6 个元素,依次存放了 6 个指针,分别指向了 6 个节点。顺次为我们输入的数字顺序。

我们可以通过如下方式验证:

得到输出:

回忆一下我们设定的输入是 2 1 3 4 6 5,再结合之前的顺序表:

稍加翻译,得到:

这和我们的预期是一致的。

再接着看剩下的代码。

现在我们已经确定,从 %rsp + 0x20 开始的 6 个 8 字节的内容,是一个指针数组,其中存放了 6 个指针,分别指向了 6 个节点。顺次为第 2 1 3 4 6 5 个节点(即我们的输入)。

接着,从 1ba6 开始,首先把 %rsp + 0x20 指向的值(也就是指向 node2 的指针)放入 %rbx,将 %eax 设置为 1,作为循环变量,然后跳转到 1bc7

1bc7 处,对 %eax 和 5 进行比较,如果小于等于 5,就跳转到 1bb5,否则跳转到 1bcc。由此我们可以推断这是一个循环 5 次的循环,从 1 ~ 5。

回到 1bb5 处,首先将 %eax 符号扩展到 %rdx,然后将 %rsp + %rdx*8 + 0x20 的值存入 %rdx,也就是从 %rsp + 0x20 开始的第 %eax 个指针。

继续,将 %rdx 的值存入 (%rcx + 8),回想第 1 行(1ba6 处),我们知道此时 %rcx 的值是一个指向 node2 的指针,所以这里的操作相当于将 node2next 指针设置为 %rdx 指向的节点。

然后,将 %eax 加 1,将 %rdx 的值存入 %rcx,回到 1bb5 处,继续循环。

由此,我们得到这里的大致逻辑:

也就是说,这里将我们输入的 6 个节点,按照我们输入的顺序,执行了一个重排,重新连接成了一个链表。

原有的链表顺序是:

node1 -> node2 -> node3 -> node4 -> node5 -> node6

现在就成了:

node2 -> node1 -> node3 -> node4 -> node6 -> node5

接着看剩下的代码:

这里首先将 0 存入 (%rcx + 8) 的位置,也就是将之前排序完的最后一个节点(在这里对应 node5)的 next 指针设置为 NULL

然后将 0 存入 %ebp,作为循环变量,跳转到 1be2

1be2 处,比较 %ebp 和 4,如果大于 4,就跳转到 1bf8(对应后续的 phase_6 函数的正常退出流程),否则顺序执行 1be7

1be7 处,将 (%rbx + 8) 的值存入 %rax,回看上一部分的开头,%rbx 的值是指向我们用户栈里的 6 个指针的第 1 个指针的指针,所以这里的操作相当于把这 6 个指针中的第 2 个指针的值存入 %rbx

继续,将 %ebp 加 1,比较其与 4 的大小,如果大于 4,就跳转到 1bf8 正常退出函数,否则顺序执行 1be7

1be7 处,将 (%rbx + 8) 的值存入 %rax,也就是保存下一个节点的地址。

然后使用 (%rax) 读出下一个节点的 value,与对应当前节点的 value(%rbx) 执行比较,如果当前节点的 value 小于等于下一个节点的 value,就跳转到 1bdb 继续判断下一个节点,否则顺序执行到 1bf1 处,调用 explode_bomb 函数,引发爆炸。

所以这里的大致逻辑是:

至此,我们总算搞明白了 phase_6 整个的函数逻辑,可以开始构造正确的输入了。

首先回顾一下我们读出的初始链表长啥样:

将之根据 value 的值,从小到大排序,得到:

现在,这个 nodeNN 信息的顺序,就是我们的答案:

将之添加到 psol.txt 中:

然后重启程序:

phase6-finish

phase6-finish

终于,我们完成了整个实验,我也结束了十数个小时的折磨。

当时做的时候,当你完成的时候应该是有这么一行的,但是现在不知道为什么没了,hhh。

写在结尾:重做 Bomb lab 的感觉真的是挺无聊的,最初做的时候还不知道怎么安全化一个炸弹,每次都胆战心惊,而且当时不太会静态分析源码,大多数情况下都是结合着 gdb 一步一步 ni 观察变化,甚至一次次地去猜... 虽然麻烦,但至少真的有趣,而且真的学到了很多东西。

但是现在,已经考完试的寒假,坚持着来画上十数个小时重做一遍,还要撰写这么长的文章,只能说完全是凭借毅力和强迫症了 hhh

参考

不周山 / 【读厚 CSAPP】II Bomb Lab:这篇文章就是我当时做的时候主要的参考,讲的没我细(没我废话这么多),而且最后一个 phase 不太一样,供参考。

评论区加载中...