dino 10PI'S BLOG丨十派的玩具箱
← 返回首页

CSAPP · Bomblab

5655 字 · 约 13 分钟 #CSAPP ▣ posts/courses/csapp ✎ 编辑

2026.10.26更新：出于兴趣，新增符号执行部分！

最近真没写什么其他好玩的东西，所以拿课堂作业报告水一水Blog。 因为写这个的时间很有限，可能不像datalab那样精致，是边做边记的，逻辑有点混乱，也有不少错误。

Bomblab的另一种做法：符号执行

2026.10.26写。这里的符号执行解法只是一种有趣的拓展，并不在CSAPP的课程范围内。

符号执行 是一种测试技术，在软件质量保障与测试（董震老师）的课程上有所讲解。其思想是，我们可以在有分支时把输入数据视作一个“符号”而不是一个具体的值，收集符号所满足的条件，最后根据约束条件反过来求解这个符号值的范围或具体值。

例如：

int f(int x) {
    int y = x * 2;
    if (y == 10) {
        BUG();          // 我们想让它执行到这里
    }
    return 0;
}

我们对上述条件收集得到的是 solve(2α == 10) → α = 5 。

接下来我们尝试解决 Bomblab 。

从符号执行的角度思考 Bomblab ，我们可以把输入看作符号变量，把 explode_bomb 当作需要避开的分支，让求解器搜索满足条件的输入。

pip install angr

以 phase_1 为例：

import angr, claripy

proj = angr.Project("bomb", auto_load_libs=False)                         # (1)
sym = lambda n: proj.loader.main_object.get_symbol(n).rebased_addr        # (2)

buf = 0x700000                                                            # (3)
state = proj.factory.call_state(sym("phase_1"), buf)                      # (4)
data = claripy.BVS("data", 8 * 64)                                        # (5)
state.memory.store(buf, data)                                             # (6)
state.add_constraints(data.get_byte(63) == 0)                             # (7)

simgr = proj.factory.simgr(state)                                         # (8)
simgr.explore(find=sym("phase_1") + 0x17, avoid=sym("explode_bomb"))      # (9)
print(simgr.found[0].solver.eval(data, cast_to=bytes).split(b"\0")[0])    # (10)

以下是原始汇编的内容，方便对比：

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

接下来我们来逐行讲解。

先记住 data 就是符号执行当前正在猜的一个未知数据。

  • (1) 将 bomb 这个二进制导入进来。模板代码。
  • (2) 构造了一个用来取地址的辅助函数。
  • (3) buf 是我们随便挑的地址，用来存指向 data 的指针，要求与程序中已有的段不冲突。
  • (4) 把函数签名对应到符号执行的初始状态。它建立了一个“正在调用 phase_1 ”的初始状态。这个状态的第一个参数是函数地址 phase_1 ，后面的参数按照函数调用的参数顺序，对应 rdi ，rsi 等等。这里用了 buf 来充当 phase_1 的第一个参数：即原始函数读输入字符串的寄存器 rdi 。
  • (5) 造符号变量。模板代码。
  • (6) 把符号数据 data 写到内存地址 buf 处。这样的话程序从 buf 读的时候读到的就是 data 。
  • (7) 添加了一条符号执行的约束：data 必须以 \0 结尾（并假设它含 \0 在内的长度不超过64字节）。
  • (8) 是模板代码。
  • (9) 求解。这一行的语义是我们本章的核心：找到目标分支（这里是 phase_1+0x17 ），避免 explode_bomb 分支。
  • (10) 把求解结果转回来输出。

在官方 self-study 的炸弹上运行，phase_1 的输出是 Border relations with Canada have never been better. 。换一颗炸弹，解出的字符串不同，代码流程完全相同。

虽然看着很玄乎，但这个方法确实是可以解决相关问题的。

我在 WSL 上用 angr 9.2.213 测试了官方 self-study 的 phase_6：

  • 从 read_six_numbers 返回后的指令开始，把六个整数设为符号变量。
  • 执行上述代码（目标为 0x4011f7 ，避开 explode_bomb ）。
  • 使用 angr 的深度优先搜索功能（目的是控制内存占用）

约 147.21 秒得到 4 3 2 1 6 5 即正确答案。

符号执行可以解决问题，对于简单问题速度也比较快，但不会解释输入为什么成立；关卡和循环一多还会出现路径爆炸（符号执行的缺点），通常仍然需要逐关求解。

两种方式可以配合使用：angr （及其他的符号执行工具）负责求解，gdb 和反汇编负责理解程序。

如果是ai来做，它会怎么找各个入口？

炸弹一般没有 strip，nm bomb | grep -E 'phase_|explode_bomb|read_line|phase_defused|secret_phase' 可以直接列出各关的函数名和地址（地址因炸弹而异）。官方 self-study 的 bomb.tar 中包含 bomb.c，main 中的调用顺序是 read_line() → phase_n() → phase_defused()，入口和调用链可以直接看出来。

b phase_1          # 断在各关入口
b read_line        # 查看这一关读入的原始字符串
b explode_bomb     # 定位炸点，反推未满足的分支
x/s $rdi           # 进入 phase_1 时，rdi 指向输入
disas /r phase_1   # 连同机器码一起反汇编，查看立即数

查找炸点可以用 objdump -d bomb | grep -B1 "call.*explode_bomb"，各关的炸点会按地址顺序列出。遇到不认识的 call 时，可以先确认它是否为 strings_not_equal、read_six_numbers 这类小函数，再查看它引用的数据。

隐藏关由 phase_defused 触发：它会在每关结束后调用一次，但只有六关全部通过后（num_input_strings == 6）才进行检查——把 phase_4 的输入按 %d %d %s 再解析一次，多出的字符串等于 DrEvil（strings bomb 可以搜到）时才会调用 secret_phase。因此 phase_4 的输入写成 5 15 DrEvil 即可触发隐藏关。

效果截图

各phase答案:

sudo hostnamectl set-hostname ubuntu

Brownie, you are doing a heck of a job.
0 1 1 2 3 5
0 u 81
5 15 DrEvil
5>:?70
5 1 2 3 6 4
50

secret_phase: 二叉树搜索

读入整数，整数，字符串 b secret_phase edx: a esi: 0 rdi: &input_str rbx: rax=int(input_str)=input_int rax: input_int - 1 u<=0x3e8(1000), so 1 ≤ input_int ≤ 1001 esi: input_int x/512x 0x604110

24 8 32 (50) 6 16 2d 6b 1 7 14 23 28 2f(47) 63 3e9(1001)

要求fun7的返回值为1 fun7 参数1: edi=edx，开始时是树的根节点 参数2: esi，input_int

if (input_int >= 根节点的值): +28 eax = 0 edx = input_int时直接跳出返回 否则参数1: edi根节点变右节点，嵌套一层，但注意这里是call而不是jump，意味着过去完还要回来的，而且保存返回值 走右边: 返回值翻倍再加一 < : +15 去左节点: 返回值翻倍

但注意上述返回值的变化是从叶到根生效，是倒序的 所以大于就往右走，小于就往左走 既然返回值为1，而返回值初始为0，往右走一步就跳出就可以，意味着被调用函数返回值为0，之后向右执行一步得到1，返回即可。 注意读到的0x32等于50。

phase_6: 链表排序

读入六个整数 rsi: %rsp，其实是&num1

循环1开头: r12: &num1 r13d: 0 rbp: &num1 eax: num1 - 1 unsigned <= 5 要求 1 <= num1 ≤ 6 r13d: 1 执行满六次之后跳+134

循环2: +73到+98 ebx: 1 eax: num2 要求num1 != num2 ebx++，小于等于5时继续循环这一块，如上执行五次， 要求num1 != num2, num2 != num3, num3 != num4, num4 != num5, num5 != num6

循环1结尾: +100 r12: &num1→&num2 所以意味着以上类似要求执行了6次， 即要求 1 <= num1, ..., num6 ＜= 6 之后跳134

+134 esi = 0 +139开始是第三循环体 ecx = num1 eax = 1 edx = node1 if (num1＞1): goto 106 else (num1 == 1): goto 117

+117 rsp+20 = node1 再执行5次，也就是挑好了合适的，numx的值为y则对应nodey

+159跳出第三循环体，进入第四循环（其实还有第五循环套在这一层外面） rbx=node1，不是->val

第四循环 rax=node1 rsi=node6 rcx=node1->val?还是node1? node1吧 循环体：+177 rdx=node2 node1->next=node2? rax=node2 rcx=node2 总之第四循环就是把node1到6按顺序连起来 吧

+197跳出第四循环，回到第五循环 node6->next = null ebp=5 rax=node2->val 要求node1->val > node2->val rbx变node2，ebp--，循环五次意味着节点值从node1到node6递减 因此只要找合适的num值使前述节点排列成递减即可，即值顺序为 5 1 2 3 6 4。

综上，这次phase没有a[i] = 7 - a[i]，应该相对还行。

phase_5

版本1: 数组对应

输入字符串长度为6 %rax: &字符串，之后右移，属于循环变量 %rbx: &字符串 %rdi: 字符串结尾，属于循环条件 %ecx: 0 %edx: 第一个字符与0xf，即取低四位作为数组下标，对应出另一个整数，加到%ecx中 观察x/16 0x402780得到如下关系：

在跳回之前我们观察结束条件，%ecx=0x3f=63，也就是六个字符的下标对应出的数字之和为63. 可取16+15+14+13+3+2，即下标为5, 14, 10, 15, 7, 0, 比如可以取48+这些数：5>:?70 注意不能用32+这些数，因为空格会在类scanf的函数中读值时自动被忽略掉。

版本2: 数组跳转

数组下标 值 数组下标 值
0 a 8 0
1 2 9 4
2 e a 1
3 7 b d
4 8 c 3
5 c d 9
6 f e 6
7 b f 5

第一个数只取最低四位做入口，x/不能等于0xf 第一个数edx加完后 = 0xf，执行15次 第二个数等于rcx

读出该程序干的事情是加15次数组元素，其中最后一次一定加的是f，我们需要输入的是第一个下标以及加和。 不妨倒推，f+6+e+2+1 +a+0+8+4+9 +d+b+7+3+c = 115 那么我们第一个下标对应值c，即入口是5，加和是115。

phase_4: 二分查找

读入整数： rcx(arg4) = rsp + 4 = &num2 rdx(arg3) = rsp = &num1 esi(arg2) = "%d %d"

需要我们输入两个整数，盲猜可以进secret phase。 要求0 <= num1 <= 0xe， rdx = 0xe(arg3) 上界 esi = 0(arg2) 下界 edi = num1(arg1) call func4, 要求返回值等于0xf 要求num2=0xf，此时phase_4全部结束

func4 传入了三个参数: num1(edi), 0(下界, esi)，0xe(上界, rdx) eax = 0xe - 0 = 0xe ebx = 0xe 逻辑右移 0x1f=31位，变0了吧，目测是看符号位 eax = 0xe + 0 = 0xe，算术右移变0b111=7，也就是做了作差除以2下取整 ebx = 0x(7 + 0)=0x7，中点值 跳+33 eax=0x7 ebx>=num1时直接返回 ... 是二分查找，差值是符号判断，如果上面的差值为负值，则ebx得1，挪一挪eax，防止死循环的，所以不去考虑它也完全没关系

可以暴力从0x0到0xe直接试一遍，虽然容易手误 如果要仔细推理：在num为0到14，low初始为0，high初始为14的情况下怎样返回15呢？ 尤其是，为什么num == 5时会返回15？因为我们每次都加了每次计算出的中间值， 所以： 左右端点为0和14时返回值+7， 左右端点为0和6时返回值+3； 左右端点为4和6时返回值+5。 返回值初始为0，完成上述查找得到返回15。

phase_3: 跳转表

注意输入是 %d %c %d 分别传到 %rsp+10, %rsp+f, %rsp+14，换回了数字 数字 字符的顺序 num1 unsigned > 7时，炸 也就是说0 <= num1 ≤ 6， 根据num1的值跳到跳转表相应位置，从而执行相应switch的结构。 既然switch的default执行+319，我们先不看跳转表，直接看+319。 传入的%c等于%rax的最低位字符即可。 接下来看跳转表。 我们用 x/a 0x402740发现为+77，意味着%rax=num1=0时，执行+77，此时： %eax=0x75，num2 = 0x51=81。所以c = 0x75=u即可，这个字符可通过 Alt + 小键盘117 得到。 答案为 0 u 81

phase_2: 斐波那契数列

%rsi参数2的值是%rsp，给read_six_numbers 利用read_six_numbers将参数3-8读入%rsi, %rsi+4, ..., %rsi+14共六处，对应于%rsp, %rsp+4, ..., %rsp+14共六处 num1=0 num2=1 %rbx=&num1 %rbp=&num5

%eax = num2 = 1 num2 += num1 = 1 num3 = %eax = 1 %rbx = &num2

%eax = num3 = 1 %eax += num2 = 1+1=2 num4 = %eax = 2

0 1 1 2 3 5

phase_1: 比较字符串

strings_not_equal的返回值(%eax)为0就跳出去，意味着要求All strings are created equal. 识得唔识得啊。

从相应位置读入所需字符串即可。

评论