CMU15213 Lab2 Bomb lab

背景知识

objdump -t bomb: 查看符号表(symbol table)。符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。
objdump -d bomb: 反汇编bomb
gdb bomb: 启动GNU Debugger
break <location>: 设置断点
run <args>: 运行程序，args作为参数
disas <func>: 反编译disassemble
info registers: 打印每个寄存器中的hex值
print (/x or /d) $register: 打印%rsp中的hex或decimal值
x $register / x 0xaddress: 打印寄存器或该地址中的值
stepi / nexti: 前进一步

Tips

在成功破解一个炸弹后，将答案放入新建的text文件answer.txt（自定义文件名）中，每个答案单独放一行，最后多打一个回车。这样在破解下一个炸弹时，直接gdb模式下执行r answer.txt便可自动跳过已破解的炸弹，节省时间。

Phase 1

objdump -d bomb > bomb.s反汇编二进制可执行文件bomb，并将输出保存到bomb.s中。打开bomb.s并搜索关键字explode_bomb可以看到，该串关键字第一次出现在phase_1函数中。并且在explode_bomb前还调用了strings_not_equal，当我们输入的字符串匹配时，400ef0指令返回true，stack pointer跳到400ef7，不会触发explode_bomb函数。
phase1-1.png

了解phase_1函数的逻辑后，gdb bomb进入gdb调试模式。首先设置断点，为防止炸弹爆炸，每次在运行gdb时都要先在explode_bomb函数处设置断点：break explode_bomb。

依据x86-64 Architecture Guide，每个寄存器的用途如下表。
phase1-2.png

phase_1函数中400ee4指令让%rsi保存$0x402400，即为strings_not_equal函数的第二个参数，因此很容易想到该函数第一个参数%rdi存的应是用户输入字符串的地址。这样的话，我们通过打印地址0x402400指向的字符串便可知道phase_1应该输入是Border relations with Canada have never been better.了。
phase1-3.png

还有一个奇技淫巧解除phase 1的炸弹。在退出gdb模式的情况下，命令行输入strings bomb查看bomb中所有可输出的字符串。其中下面这一段字符串是我们会用到的，从中提取看起来可能是用于解除炸弹的字符串。
phase1-4.png

1
2
3
4
5
6
7
8
9
Border relations with Canada have never been better.
flyers
maduiersnfotvbyl
%d %d %d %d %d %d: 有一行输入是6个数字
%d %d %s：有一行输入是2个数字和一个字符串
DrEvil
%s %d %[a-zA-z ]
csapp
;*3$"

重新进入gdb模式并在explode_bomb和phase_1处设置断点，输入第一个候补字符串Border relations with Canada have never been better.后发现成功解除第一个炸弹！

Phase 2

phase 2调用的是read_six_numbers函数，说明要输入6个数字。
phase2.png

我们观察读取数字后的指令。

1
2
3
4
5
6
7
8
9
10
11
12
400f0a和400f0e: 若(%rsp)不等于1，则触发炸弹，若等于1，则跳到400f30
	-> 第一个数字为1
400f30:         %rbx = %rsp + 4
400f35:         %rbp = %rsp + 24
400f3a:         跳回400f17
400f17:         %eax = (%rbx - 4) = (%rsp)
400f1a:         %eax += %eax
400f1c和400f1e: 拿%eax与(%rbx)比较，也就是拿第一个数字的两倍与第二个数字作比较，
					      若不相等，则触发炸弹，若相等，则跳到400f25
400f25:         %rbx = %rbx + 4 = %rsp + 8
400f29:         拿%rbp与%rbx比较，若不相等，则跳回400f17
	-> 循环判断是否满足：第n个数字 = 第n-1个数字的两倍

因此，phase 2的输入应为1 2 4 8 16 32。

Phase 3

phase3.png

phase 3有三个可能引爆炸弹的地方。第一处炸弹(400f65)是当用户输入不符合格式要求时。由于我们知道sscanf函数签名为int sscanf ( const char * s, const char * format, ...);，存第二个参数的%rsi存的是输入格式。通过在400f56设置断点并打印%rsi，可知phase 3应输入两个数字。

1
2
3
4
5
6
(gdb) break *0x400f56
Breakpoint 2 at 0x400f56
(gdb) run
Breakpoint 2, 0x0000000000400f56 in phase_3 ()
(gdb) print (char *)$rsi
$2 = 0x4025cf "%d %d"

依据400f6a和400f6f指令，第二处炸弹(400fad)是当(%rsp + 8) > 7时引爆，说明输入的第一个数必须 ≤ 7。从400f71到400fab可以看出，该段代码的逻辑是根据%rax的值跳到不同地址来执行命令，上层也就是switch语句。假设第一个数为0，则会进入400f7c分支，%eax赋值为0xcf，跳到400fbe后，比较%eax与输入的第二个数，若不相等，则引爆第三处炸弹。因此phase 3其中一个解是0 207。

Phase 4

phase4-1.png

与phase 3同理，通过在40101f设置断点并打印%rsi，可知phase 4应输入两个数字。

1
2
3
4
5
6
(gdb) break *0x40101f
Breakpoint 2 at 0x40101f
(gdb) run
Breakpoint 2, 0x000000000040101f in phase_4 ()
(gdb) print (char *)$rsi
$2 = 0x4025cf "%d %d"

根据40102e和401033可知，输入的第一个数需小于14才不会引爆炸弹。40103a到401048是调用func4函数，函数参数依次为(%rdi, %rsi, %rdx) = (输入第一个数, 0, 14)。若函数返回值不等于0，则引爆炸弹。从401051和401056看出，输入的第二个数必须等于0才不会引爆炸弹。接下来我们看看func4函数在做什么。
phase4-2.png

首先可以看出func4函数是个递归函数。通过400ff7和400ff9可看出，跳出递归的条件是第二个和第三个函参经过一串运算后的结果≥第一个函参。这里，我们当然可以翻译上面的汇编语言弄清func4函数的每一步，但是在Recitation课助教有提到过，这个lab的目的不在于此，所以我们可以通过尝试的方法试出7 0是一个能解除炸弹的输入。

Phase 5

phase5-1.png

phase 5首先检查输入是否是长度为6的字符串。40108b到4010ac是for循环，循环自变量为%rax，从0加到6，使循环进行了6次，所以可以断定这个循环就是用来遍历输入字符串里每个字符的。那么遍历字符用来做什么呢？我们从循环内部的头开始看，因为%rbx在401067处被赋值为输入字符串的首地址，所以40108b是将%rcx赋值为字符的ASCII值。401099处我们看到有一个常量。设置断点并打印地址0x4024b0所存储的值。这个字符串常量是用来干嘛的呢？
phase5-2.png

不如往下看看，在4010bd处调用strings_not_equal函数，通过在4010b8设置断点并打印%rsi可知for循环后输入应变为flyers。
phase5-3.png

所以猜测，我们的输入是为了给0x4024b0存的字符串常量提供偏移量，在for循环里依次选择字符，以与flyers相等。因此，偏移量依次为9(1001), 15(1111), 14(1110), 5(0101), 6(0110), 7(0111)。由于401096处将0xf与%edx相与，所以我们只要保证输入字符ASCII值的低4位等于偏移量即可。其中ionefg是一个正确答案。
phase5-4.png

Phase 6

phase 6的代码很长，我们分段来看。

第1段

phase6-1.png

与phase 2相同，phase 6要输入6个数字。一开始%r13存储的是输入数组的首地址(4001100)，在40114d处%r13被更新成数组下一个元素的地址。根据401117-401121可知，数组每个元素都要小于等于6，否则会引爆炸弹。第二枚炸弹在401140处，若当前元素等于数组中其他元素，会引爆炸弹。

第2段

phase6-2.png

0x18 = 24 = 4bytes/int x 6ints，所以%rsi存的是输入数组的边界地址，用来在40116a处判断是否越界。%r14在40110b处被赋值为数组的首地址，所以%rax即为数组首地址。这段代码的作用就是用7减去数组元素，并将结果替换原有值。

第3段

phase6-3.png

从头走一遍代码可知，%esi存的是数组下标，%ecx存的是数组第%esi个元素。在401181和4011a4处都出现了一个地址常量0x6032d0，通过设置不同长度参数打印该地址存储的内容后，发现这其实是个链表数据结构。第一列为结点值，第二列为结点编号，第三列为下一个结点的地址（即next pointer），第四列为空。再看401188指令，该指令的作用是将第%ecx个元素的地址存储在以(0x20 + %rsp)为基址，2*%rsi为偏移量的地址中。举个例子，假设输入数组为[3, 4, 5, 6, 1, 2]，则依次会将链表第3个结点、第4个结点、……、第2个结点的首地址存到新地址中。该操作等价于将输入数组重新排序。
phase6-4.png

第4段

phase6-5.png

有了第3段的基础，第4段的作用便较容易猜测。取新地址中两个连续结点node1, node2，令node1.next = node2。

第5段

phase6-6.png

这段的作用是判断新地址存的链表是否为递减序列，若不是，则会引爆炸弹。

总和

综上所述，phase 6的操作总结如下。

  1. 判断是否输入数组每个元素nums[i] ≤ 6，且输入数组没有重复元素。
  2. nums[i] = 7 - nums[i]
  3. 依据数组元素值重排为递减序列。

因此，根据0x6032d0地址中链表的结点值从大到小排序，则排序后的链表为[3, 4, 5, 6, 1, 2]。再倒推第二步，7 - [3, 4, 5, 6, 1, 2] = [4, 3, 2, 1, 6, 5]，即为输入的6个数。

结果

6个炸弹全部成功破解！
result.png

参考资料

https://blog.csdn.net/vcomp/article/details/51485776?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control
ASCII表：https://bournetocode.com/projects/GCSE_Computing_Fundamentals/pages/3-3-5-ascii.html
Phase 6：https://blog.csdn.net/zjwreal/article/details/80925989
Phase 6：http://zpalexander.com/binary-bomb-lab-phase-6/