BombLab

<深入理解计算机系统>Bomb Lab实验解析
CS:APP - Bomb Lab

如果在gdb调试的出现Permission deny的问题可以调整bomb的权限

chmod 777 bomb

基本知识

Bomb lab 主要考察对应汇编代码的阅读和理解能力,以及使用gdb调试工具

x86-64架构调用函数时参数传递使用的寄存器和栈地址

%rdi	%rsi	%rdx	%rcx	%r8	%r9	(%rsp)	(%rsp+8)	(%rsp+...)

return -> %rax

x86-64寄存器

QQ图片20221015171443

操作数指示符

as123gsz

常用汇编

mov S,D : 把S的值传给D,具体的S见操作数指示符

lea A,B : 计算A表达式的值传给B

cmp A,B : 对 B-A 的值进行判断, gl(有符号) ab(无符号)

test A,B : A&B

je : 等于0跳转

jne : 不等于0跳转

GDB

调试使用到的指令

注 : 括号表示完成指令名中可以被省略的部分

命令	用途
gdb bomb	使用gdb调试可执行文件bomb
disas(semble) phase_1	反汇编函数phase_1
disas 0x402400	反汇编地址0x402400附近的函数
x/s 0x400544	以字符串的形式输出,字符串在内存中的首地址为0x400544
x/d 0x400544	以整数的形式输出,整数在内存中的首地址为0x400544
x/x 0x400544	以16进制的形式输出
x/4x 0x400544	以16进制的形式输出四个字节的数据
x/a 0x400544	以指针的形式
b(reak) *0x400da4	在0x400da4地址处打断点
b phase_5	在phase_5函数入口地址打断点
b 74	在源代码74行打断点
r(un)	运行可执行文件
r input.txt	运行可执行文件,传入一个参数,参数名是input.txt
c(ontinue)	从断点处继续运行
k(ill)	停止调试当前运行的程序
q(uit)	退出调试
i(nfo) r(egister)	打印所有整数寄存器及其内容
i r rax	打印rax寄存器及其内容
i b	打印所有断点
d(elete) 1	删除断点1

gdb 调试利器
gdb文档

开始之前

解压文件之后可以看到三个文件 bomb 是本次实验使用的可执行文件, bomb.c 是源代码中的主函数部分, README是介绍文件

浏览 bomb.c 可以看到它在开头引用了

#include "support.h"
#include "phases.h"

所以可以看出 bomb.c 只是源文件的一部分, bomb 是由多个文件一起编译得到的,提供 bomb.c 文件实际上是为了给读者一个清晰的bomb lab思路

使用 gdb bomb 进入调试

实验报告

phase_1

使用 disas phase_1 查看第一关汇编

0x0000000000400ee0 <+0>:     sub    $0x8,%rsp
0x0000000000400ee4 <+4>:     mov    $0x402400,%esi               # esi = 0x402400
0x0000000000400ee9 <+9>:     call   0x401338 <strings_not_equal> # 比较 edi esi 两个字符串是否相同
0x0000000000400eee <+14>:    test   %eax,%eax                    # 相同返回0,不相同返回1
0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>        # 应该相同
0x0000000000400ef2 <+18>:    call   0x40143a <explode_bomb>
0x0000000000400ef7 <+23>:    add    $0x8,%rsp
0x0000000000400efb <+27>:    ret

前一步使用 read_line 读取了一行输入,输入被读入了

edi指向用户输入的字符串的首地址, strings_not_equal 函数的作用是判断两个字符串是否不相同,不相同返回1,相同返回0

如果有耐心阅读可以稍微解释一下strings_not_equal的汇编细节,也可以省略

0x402400指向的字符串通过 x/s 0x402400 查看是 "Border relations with Canada have never been better."

所以第一关的答案是

Border relations with Canada have never been better.

phase_2

disas phase_2 ,先看第一部分

0x0000000000400efc <+0>:     push   %rbp
0x0000000000400efd <+1>:     push   %rbx
0x0000000000400efe <+2>:     sub    $0x28,%rsp
0x0000000000400f02 <+6>:     mov    %rsp,%rsi                    #rsi = rsp
0x0000000000400f05 <+9>:     call   0x40145c <read_six_numbers>

查看 read_six_numbers 函数反汇编

0x000000000040145c <+0>:     sub    $0x18,%rsp
0x0000000000401460 <+4>:     mov    %rsi,%rdx                        # rdx = rsp
0x0000000000401463 <+7>:     lea    0x4(%rsi),%rcx                   # rcx = rsp + 4
0x0000000000401467 <+11>:    lea    0x14(%rsi),%rax                  # rax = rsp + 20
0x000000000040146b <+15>:    mov    %rax,0x8(%rsp)                   # (rsp+8) = rsp + 20
0x0000000000401470 <+20>:    lea    0x10(%rsi),%rax                  # rax = rsp + 16
0x0000000000401474 <+24>:    mov    %rax,(%rsp)                      # (rsp) = rsp + 16
0x0000000000401478 <+28>:    lea    0xc(%rsi),%r9                    # r9 = rsi + 12
0x000000000040147c <+32>:    lea    0x8(%rsi),%r8                    # r8 = rsi + 8
0x0000000000401480 <+36>:    mov    $0x4025c3,%esi                   # esi = 0x4025c3
0x0000000000401485 <+41>:    mov    $0x0,%eax                        # eax = 0
0x000000000040148a <+46>:    call   0x400bf0 <__isoc99_sscanf@plt>   # 调用sccanf函数
0x000000000040148f <+51>:    cmp    $0x5,%eax                        # 返回值应该大于5,即至少读取六个
0x0000000000401492 <+54>:    jg     0x401499 <read_six_numbers+61>
0x0000000000401494 <+56>:    call   0x40143a <explode_bomb>
0x0000000000401499 <+61>:    add    $0x18,%rsp
0x000000000040149d <+65>:    ret

sccanf 的作用是从字符串中提取得到格式化的值

查看 0x4025c3 的字符串为 "%d %d %d %d %d %d",即接收六个整数(int),所以输入应该为空格分隔的六个整数

rdi = 用户输入字符串的首地址

rsi = 0x4025c3(读取的格式,六个整数)

rdx = rsp

rcx = rsp+4

r8 = rsp+8

r9 = rsp+12

(rsp) = rsp+16

(rsp+8) = rsp+20

根据x86-64架构调用函数时参数传递使用的寄存器和栈地址的规则

// 假设输入是 1 2 3 4 5 6 -> 字符串
int sccanf("1 2 3 4 5 6","%d %d %d %d %d %d",rdx,rsi,r8,r9,(rsp),(rsp+8)) -> rax

所以通过 sscanf 从字符串中读取的六个整数分别存放在(rsp),(rsp+4),...等连续六个位置

再看第二部分,

 0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)             # 第一个输入的整数(number[0])应该为 1
 0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
 0x0000000000400f10 <+20>:    call   0x40143a <explode_bomb>
 0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>
 0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax         # eax = (rbx-4)=(rsp)=number[0]
 0x0000000000400f1a <+30>:    add    %eax,%eax               # eax = 2*number[0]
 0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)             # (rbx) = eax, 即 (rsp+4)=number[1]=eax=2*number[0]
 0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
 0x0000000000400f20 <+36>:    call   0x40143a <explode_bomb>
 0x0000000000400f25 <+41>:    add    $0x4,%rbx               # rbx += 4,开始循环
 0x0000000000400f29 <+45>:    cmp    %rbp,%rbx               # 判断是否越界,越界则结束
 0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
 0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
 0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx          # rbx = rsp+4 (number[1])
 0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp         # rbp = rsp+0x18 (0x18=24,相当于数组的边界number[6])
 0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>
 0x0000000000400f3c <+64>:    add    $0x28,%rsp
 0x0000000000400f40 <+68>:    pop    %rbx
 0x0000000000400f41 <+69>:    pop    %rbp
 0x0000000000400f42 <+70>:    ret

阅读汇编,可知第一个输入的(rsp),也就是number[0]应该为1,之后的数字应该依次乘2,也就是一个首项为1,公比为2的等比数列,一共六个输入,所以答案为

1 2 4 8 16 32

phase_3

0x0000000000400f43 <+0>:     sub    $0x18,%rsp
0x0000000000400f47 <+4>:     lea    0xc(%rsp),%rcx
0x0000000000400f4c <+9>:     lea    0x8(%rsp),%rdx
0x0000000000400f51 <+14>:    mov    $0x4025cf,%esi
0x0000000000400f56 <+19>:    mov    $0x0,%eax
0x0000000000400f5b <+24>:    call   0x400bf0 <__isoc99_sscanf@plt>

查看 x/s 0x4025cf 得到 "%d %d",所以输入应该为空格分隔的两个整数

第一个值保存在rdx,也就是(rsp+8),第二个值保存在(rsp+12)

0x0000000000400f60 <+29>:    cmp    $0x1,%eax               # 获取的值应该大于1
0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
0x0000000000400f65 <+34>:    call   0x40143a <explode_bomb>
0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)          # 第一个值应该小于等于7
0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax          # eax = number[0]
0x0000000000400f75 <+50>:    jmp    *0x402470(,%rax,8)      # 跳转到0x402470+8*number[0]的位置
0x0000000000400f7c <+57>:    mov    $0xcf,%eax
0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
0x0000000000400f83 <+64>:    mov    $0x2c3,%eax
0x0000000000400f88 <+69>:    jmp    0x400fbe <phase_3+123>
0x0000000000400f8a <+71>:    mov    $0x100,%eax
0x0000000000400f8f <+76>:    jmp    0x400fbe <phase_3+123>
0x0000000000400f91 <+78>:    mov    $0x185,%eax
0x0000000000400f96 <+83>:    jmp    0x400fbe <phase_3+123>
0x0000000000400f98 <+85>:    mov    $0xce,%eax
0x0000000000400f9d <+90>:    jmp    0x400fbe <phase_3+123>
0x0000000000400f9f <+92>:    mov    $0x2aa,%eax
0x0000000000400fa4 <+97>:    jmp    0x400fbe <phase_3+123>
0x0000000000400fa6 <+99>:    mov    $0x147,%eax
0x0000000000400fab <+104>:   jmp    0x400fbe <phase_3+123>
0x0000000000400fad <+106>:   call   0x40143a <explode_bomb>
0x0000000000400fb2 <+111>:   mov    $0x0,%eax
0x0000000000400fb7 <+116>:   jmp    0x400fbe <phase_3+123>
0x0000000000400fb9 <+118>:   mov    $0x137,%eax
0x0000000000400fbe <+123>:   cmp    0xc(%rsp),%eax          #number[1]应该等于eax
0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
0x0000000000400fc4 <+129>:   call   0x40143a <explode_bomb>
0x0000000000400fc9 <+134>:   add    $0x18,%rsp
0x0000000000400fcd <+138>:   ret

这里 <+50>:jmp *0x402470(,%rax,8) 显然是一个跳转的地址,既然已经知道number[0]的值小于等于7,这里显然应该>=0,所以我们可以使用 x/a + 地址 依次查看从 0x402470 的跳转位置,得到的结果如下

(gdb) x/a 0x402470                      # 对应number[0] = 0
0x402470:       0x400f7c <phase_3+57>
(gdb) x/a 0x402478                      # 对应number[0] = 1
0x402478:       0x400fb9 <phase_3+118>
(gdb) x/a 0x402480                      # 对应number[0] = 2
0x402480:       0x400f83 <phase_3+64>
(gdb) x/a 0x402488                      # 对应number[0] = 3
0x402488:       0x400f8a <phase_3+71>
(gdb) x/a 0x402490                      # 对应number[0] = 4
0x402490:       0x400f91 <phase_3+78>
(gdb) x/a 0x402498                      # 对应number[0] = 5
0x402498:       0x400f98 <phase_3+85>
(gdb) x/a 0x4024a0                      # 对应number[0] = 6
0x4024a0:       0x400f9f <phase_3+92>
(gdb) x/a 0x4024a8                      # 对应number[0] = 7
0x4024a8:       0x400fa6 <phase_3+99>

那么根据第一个输入可以得到不同的跳转地址,接下来只需要根据跳转的位置后面跟的 mov指令就可以得到number[1]的值了

所以第三关的答案不唯一,以下任何一组答案都可以通过

phase_4

0x000000000040100c <+0>:     sub    $0x18,%rsp
0x0000000000401010 <+4>:     lea    0xc(%rsp),%rcx                 # number[1]
0x0000000000401015 <+9>:     lea    0x8(%rsp),%rdx                 # number[0]
0x000000000040101a <+14>:    mov    $0x4025cf,%esi                 # %d %d
0x000000000040101f <+19>:    mov    $0x0,%eax
0x0000000000401024 <+24>:    call   0x400bf0 <__isoc99_sscanf@plt>
0x0000000000401029 <+29>:    cmp    $0x2,%eax
0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)                 # number[0]<=14
0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
0x0000000000401035 <+41>:    call   0x40143a <explode_bomb>
0x000000000040103a <+46>:    mov    $0xe,%edx                      # edx = 14
0x000000000040103f <+51>:    mov    $0x0,%esi                      # esi = 0
0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi                 # edi = number[0]
0x0000000000401048 <+60>:    call   0x400fce <func4>               # 进入func4
0x000000000040104d <+65>:    test   %eax,%eax                      # 返回值应为0
0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)                 # number[1]=0
0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
0x0000000000401058 <+76>:    call   0x40143a <explode_bomb>
0x000000000040105d <+81>:    add    $0x18,%rsp
0x0000000000401061 <+85>:    ret

phase_4的主体就是 func4 这个函数

这里不难看出是一个递归函数,三个参数,返回值为int,不妨设

int func4(int x, int y, int z) {
  // edi   esi   edx
}

0x0000000000400fce <+0>:     sub    $0x8,%rsp
0x0000000000400fd2 <+4>:     mov    %edx,%eax            # eax = z
0x0000000000400fd4 <+6>:     sub    %esi,%eax            # eax = z-y = 14
0x0000000000400fd6 <+8>:     mov    %eax,%ecx            # ecx = 14
0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx           # ecx >>= 31
                                                         # ecx = 0 if ecx >=0 else 1
0x0000000000400fdb <+13>:    add    %ecx,%eax            # eax += ecx
0x0000000000400fdd <+15>:    sar    %eax                 # eax >> 1 #(y-z)/2
0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx   # [temp] = ecx = rax+rsi = (y-z)/2+z = (y+z)/2
0x0000000000400fe2 <+20>:    cmp    %edi,%ecx
0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36>  # if (temp-x<=0)
0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx      # z = temp-1
0x0000000000400fe9 <+27>:    call   0x400fce <func4>     # 递归调用
0x0000000000400fee <+32>:    add    %eax,%eax            # return 2*func4(x,y,temp-1)
0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
0x0000000000400ff2 <+36>:    mov    $0x0,%eax            # eax = 0 (递归出口)
0x0000000000400ff7 <+41>:    cmp    %edi,%ecx
0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>  # if (temp>=x) -> 这里其实等价于 temp == x
0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi       # esi = temp+1
0x0000000000400ffe <+48>:    call   0x400fce <func4>     # 递归调用
0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax# return 2*func4(x,temp+1,z)+1
0x0000000000401007 <+57>:    add    $0x8,%rsp
0x000000000040100b <+61>:    ret

所以等价的C语言代码为

int func4(int x, int y, int z) {
  int temp = z-y;
  if (temp < 0) temp+=1;
  temp = temp/2 + y; // temp = (y+z)/2
  if (temp <= x) {
    if (temp >= x) return 0; // 相当于 temp == x
    else {
      return 2*func4(x,temp+1,z)+1;
    }
  } else {
    return 2*func4(x,y,temp-1);
  }
}

在 phase_4 中调用的函数是 func4(number[0],0,14), 函数的返回值应为0

观察可知递归的出口返回0,所以 number[0] = 7 即可通过 temp==x 这条判断返回. 由phase_4的剩余汇编可知第二个参数 number[1]应为0

所以本题答案为

7 0

phase_5

最开始这里使用了 stack canary(栈金丝雀)用来保护栈

用途是确保 0x18(%rsp) 的数值在函数前后没有发生改动,如果发生改动则执行 <__stack_chk_fail@plt> 调用系统函数 __stack_chk_fail 跳出,从而防止栈溢出

简单来说就是,防止输入的字符串过长导致栈溢出

Why does this memory address %fs:0x28 ( fs[0x28] ) have a random value?
What sets fs:[0x28] (stack canary)?

接着判断了输入的字符串应该长度为6

0x000000000040107a <+24>:    callq  0x40131b <string_length>
0x000000000040107f <+29>:    cmp    $0x6,%eax
0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>
0x0000000000401084 <+34>:    callq  0x40143a <explode_bomb>

接着是本次程序的主逻辑判断

0x0000000000401067 <+5>:     mov    %rdi,%rbx                     # rbx = rdi (输入字符串首地址)
...
0x00000000004010d2 <+112>:   mov    $0x0,%eax
...
0x000000000040108b <+41>:    movzbl (%rbx,%rax,1),%ecx            # 取出字符 input[%rax]
0x000000000040108f <+45>:    mov    %cl,(%rsp)
0x0000000000401092 <+48>:    mov    (%rsp),%rdx
0x0000000000401096 <+52>:    and    $0xf,%edx                     # 只使用低4位
0x0000000000401099 <+55>:    movzbl 0x4024b0(%rdx),%edx           # ...

可以通过gdb查看地址 0x4024b0 的字符串

(gdb) x/s 0x4024b0
0x4024b0 <array.3449>:  "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

由于只有低4位(0-15),所以会被映射到的就是 maduiersnfotvbyl

所以可知这里利用了输入字符串的低4位作为索引,找到这里的一个字符,取出来

0x00000000004010a0 <+62>:    mov    %dl,0x10(%rsp,%rax,1)         # 保存到 (rsp+%rax+0x10)的位置
0x00000000004010a4 <+66>:    add    $0x1,%rax
0x00000000004010a8 <+70>:    cmp    $0x6,%rax
0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>         # 遍历所有字符
0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)
0x00000000004010b3 <+81>:    mov    $0x40245e,%esi                # 另一个字符串
0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi               # 判断字符串相同
0x00000000004010bd <+91>:    callq  0x401338 <strings_not_equal>
0x00000000004010c2 <+96>:    test   %eax,%eax
0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>

查看另一个字符串

(gdb) x/s 0x40245e
0x40245e:       "flyers"

所以为了使这两个字符串相同,我们需要做的就是输入一个六位的字符串,将这个字符串的ascii值的低四位作为索引,在 maduiersnfotvbyl 字符串中查找对应的字符,去匹配 flyers

所以索引应该为

9 15 14 5 6 7

查找字符的ASCII码值有多种方式

ASCII码对照表

输入 man ascii 打开相关信息查看

所以本题答案也不唯一,大小写都可以,也有多个映射,这里给出一个答案

ionefg

phase_6

0x00000000004010fc <+8>:     sub    $0x50,%rsp
0x0000000000401100 <+12>:    mov    %rsp,%r13
0x0000000000401103 <+15>:    mov    %rsp,%rsi
0x0000000000401106 <+18>:    callq  0x40145c <read_six_numbers>

首先是之前分析过的读取六个整数,保存在 (rsp) 的位置

0x0000000000401100 <+12>:    mov    %rsp,%r13                  # r13 = rsp
...
0x000000000040110b <+23>:    mov    %rsp,%r14
0x000000000040110e <+26>:    mov    $0x0,%r12d                 # r12d = 0
0x0000000000401114 <+32>:    mov    %r13,%rbp
0x0000000000401117 <+35>:    mov    0x0(%r13),%eax             # eax = number[i]
0x000000000040111b <+39>:    sub    $0x1,%eax
0x000000000040111e <+42>:    cmp    $0x5,%eax
0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>      # eax-1 <= 5
0x0000000000401123 <+47>:    callq  0x40143a <explode_bomb>
0x0000000000401128 <+52>:    add    $0x1,%r12d                 # r12d += 1
0x000000000040112c <+56>:    cmp    $0x6,%r12d
0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>      # 外层循环,判断所有的六个数
0x0000000000401132 <+62>:    mov    %r12d,%ebx
0x0000000000401135 <+65>:    movslq %ebx,%rax
0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax
0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)
0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>      # 判断六个数每两个数都不相同
0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
0x0000000000401145 <+81>:    add    $0x1,%ebx
0x0000000000401148 <+84>:    cmp    $0x5,%ebx
0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>      # 内层循环,判断五次(最后一个不需要判断)

所以这段代码的意思就是判断一下输入的六个数都有应该小于等于6,而且这里使用的是 jbe 无符号判断,所以也eax-1也应该大于等于0,即所有的数大于等于1,并且每两个数都不相同.

从这里我们可以看出这应该是一个1-6的全排列中的一种情况

0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi            # 设置循环终点
0x0000000000401158 <+100>:   mov    %r14,%rax
0x000000000040115b <+103>:   mov    $0x7,%ecx
0x0000000000401160 <+108>:   mov    %ecx,%edx
0x0000000000401162 <+110>:   sub    (%rax),%edx                # (rax) = 7-(rax)
0x0000000000401164 <+112>:   mov    %edx,(%rax)
0x0000000000401166 <+114>:   add    $0x4,%rax
0x000000000040116a <+118>:   cmp    %rsi,%rax
0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>

这里的汇编就是将栈内的六个数a都变成7-a

0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx        # ecx = number[rsi]
0x000000000040119a <+166>:   cmp    $0x1,%ecx
0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>    # 如果 number[rsi] == 1,只有一种情况
0x000000000040119f <+171>:   mov    $0x1,%eax
0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx
0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>    # ...

我们不为1的情况,他会跳转到+130的位置,这里出现了一个地址 0x6032d0,并且将 eax 设为1

0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx
0x000000000040117a <+134>:   add    $0x1,%eax
0x000000000040117d <+137>:   cmp    %ecx,%eax
0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>

接下来做循环, 使用 mov 0x8(%rdx),%rdx 不断地赋值,直到 eax == ecx,这种操作可以看出应该是一个链表的跳转

我们可以使用 x/a 来查看这个指针指向的位置,注意+8

(gdb) x/a 0x6032d0
0x6032d0 <node1>:       0x10000014c
(gdb) x/a 0x6032d8
0x6032d8 <node1+8>:     0x6032e0 <node2>
(gdb) x/a 0x6032e8
0x6032e8 <node2+8>:     0x6032f0 <node3>
(gdb) x/a 0x6032f8
0x6032f8 <node3+8>:     0x603300 <node4>
(gdb) x/a 0x603308
0x603308 <node4+8>:     0x603310 <node5>
(gdb) x/a 0x603318
0x603318 <node5+8>:     0x603320 <node6>

这里可以看出来是六个node,且跳转的次数对应ecx.所以现在的对应关系如下

输入	1	2	3	4	5	6
rdx的值	?	0x6032e0	0x6032f0	0x603300	0x603310	0x603320

循环的终点就是将这个指针的值赋给 (rsp+2*rsi+0x20)的位置

0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)   # 这里的 rsi 是输入字符串的索引 0/4/8/12/16/20
0x000000000040118d <+153>:   add    $0x4,%rsi
0x0000000000401191 <+157>:   cmp    $0x18,%rsi               # 0x18 对应的值是24(24/4=6),也即是外层循环的终点
0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183>
0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx       # 否则 ecx 赋值下一个数字

而如果是 ecx == 1 的情况,就是直接将 0x6032d0 赋值给 edx

0x0000000000401183 <+143>:   mov    $0x6032d0,%edx
0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)

所以现在是

输入	1	2	3	4	5	6
rdx的值	0x6032d0	0x6032e0	0x6032f0	0x603300	0x603310	0x603320
保存在栈中的位置	(rsp+0x20)	(rsp+0x28)	(rsp+0x30)	(rsp+0x38)	(rsp+0x40)	(rsp+0x48)

最后当外层循环结束之后跳转到 +183 继续执行

0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx          # 栈中第一个地址
0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax          # rax = rsp+0x28
0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi          # rsi 是结束的位置
0x00000000004011ba <+198>:   mov    %rbx,%rcx
0x00000000004011bd <+201>:   mov    (%rax),%rdx              # 栈中下一个地址
0x00000000004011c0 <+204>:   mov    %rdx,0x8(%rcx)           # 将下一个地址赋给 (第一个地址+8)的内存单元
0x00000000004011c4 <+208>:   add    $0x8,%rax
0x00000000004011c8 <+212>:   cmp    %rsi,%rax
0x00000000004011cb <+215>:   je     0x4011d2 <phase_6+222>
0x00000000004011cd <+217>:   mov    %rdx,%rcx
0x00000000004011d0 <+220>:   jmp    0x4011bd <phase_6+201>

这段汇编做的事情就是将栈中六个地址串起来,每一个地址+8的内存单元保存着下一个地址

这里举一个例子,比如我们输入的是 3 1 5 2 4 6,那么先经过一次 7-x 的操作变成了 4 6 2 5 3 1. 然后这个数据保存到ecx中作为从 0x6032d0跳转的次数

那么按照这个顺序,现在保存到栈中的数据就应该依次是

20221108181508

由于之前跳转的时候node123456之间存在着索引,这里就是将原本的索引破坏掉,创建一个一个新的链表,新的一组指针索引

例如原先 0x6032e0(node2) 的下一跳 0x6032e8 的值是 0x6032f0(node3),现在就变成了 0x603310(node5)

接着就是最后的一步了

0x00000000004011d2 <+222>:   movq   $0x0,0x8(%rdx)
0x00000000004011da <+230>:   mov    $0x5,%ebp                # rbx 在+183做了赋值 = (rsp+20),栈中第一个地址
0x00000000004011df <+235>:   mov    0x8(%rbx),%rax           # rax = 下一跳的地址
0x00000000004011e3 <+239>:   mov    (%rax),%eax              # rax = (rax)
0x00000000004011e5 <+241>:   cmp    %eax,(%rbx)              # 比较第一个地址内存值和第二个地址的内存值
0x00000000004011e7 <+243>:   jge    0x4011ee <phase_6+250>   # 递减排序
0x00000000004011e9 <+245>:   callq  0x40143a <explode_bomb>
0x00000000004011ee <+250>:   mov    0x8(%rbx),%rbx
0x00000000004011f2 <+254>:   sub    $0x1,%ebp
0x00000000004011f5 <+257>:   jne    0x4011df <phase_6+235>

我们可以使用gdb查看当前节点地址的值

(gdb) x/d 0x6032d0
0x6032d0 <node1>:       332
(gdb) x/d 0x6032e0
0x6032e0 <node2>:       168
(gdb) x/d 0x6032f0
0x6032f0 <node3>:       924
(gdb) x/d 0x603300
0x603300 <node4>:       691
(gdb) x/d 0x603310
0x603310 <node5>:       477
(gdb) x/d 0x603320
0x603320 <node6>:       443

根据值递减关系,对应的索引应该是 0x6032f0 -> 0x603300 -> 0x603310 -> 0x603320 -> 0x6032d0 -> 0x6032e0

查一下之前的表格可以得到

输入	1	2	3	4	5	6
rdx的值	0x6032d0	0x6032e0	0x6032f0	0x603300	0x603310	0x603320
保存在栈中的位置	(rsp+0x20)	(rsp+0x28)	(rsp+0x30)	(rsp+0x38)	(rsp+0x40)	(rsp+0x48)

所以对应的输入应该是 3 4 5 6 1 2,因为之前是7-x,所以应该反过来,所以最终的答案就是

4 3 2 1 6 5

secret_phase

六个关卡都通过了就会提示实验通关,但是bomb实验还有一个隐藏关卡,注意到在 bomb.c 的最后有一行注释

/* Wow, they got it!  But isn't something... missing?  Perhaps
 * something they overlooked?  Mua ha ha ha ha! */

这说明其实还有谜题没有解开,我们可以使用 disas main 来查看所有的步骤,并没有发现遗漏,都是 phase_x + phase_defused 的模式,所以问题一定是出现在 phase_defused 之中

进行反汇编 disas phase_defused之后就可以发现存在一个隐藏关卡

0x0000000000401630 <+108>:   callq  0x401242 <secret_phase>

所以我们需要阅读这段汇编寻找到如何进入这个函数

0x00000000004015c4 <+0>:     sub    $0x78,%rsp
0x00000000004015c8 <+4>:     mov    %fs:0x28,%rax
0x00000000004015d1 <+13>:    mov    %rax,0x68(%rsp)
0x00000000004015d6 <+18>:    xor    %eax,%eax
0x00000000004015d8 <+20>:    cmpl   $0x6,0x202181(%rip)        # 0x603760 <num_input_strings>
0x00000000004015df <+27>:    jne    0x40163f <phase_defused+123>

这里的 0x603760 应该是一个整数(因为它在和立即数6进行比较),可以根据命名推测大概率是输入的字符串的个数,如果能输入六次字符串并且还运行到这里显然前面的六关都通过了,我们可以稍后使用gdb打断点的方式来验证我们的猜想

0x00000000004015e1 <+29>:    lea    0x10(%rsp),%r8
0x00000000004015e6 <+34>:    lea    0xc(%rsp),%rcx
0x00000000004015eb <+39>:    lea    0x8(%rsp),%rdx
0x00000000004015f0 <+44>:    mov    $0x402619,%esi                 # 输入格式化
0x00000000004015f5 <+49>:    mov    $0x603870,%edi                 # 输入的字符串
0x00000000004015fa <+54>:    callq  0x400bf0 <__isoc99_sscanf@plt>
0x00000000004015ff <+59>:    cmp    $0x3,%eax                      # 三个结果

x/s 0x402619 可以看到sscanf的输入格式化是 "%d %d %s", 两个整数一个字符串,但是获取的输入地址是 0x603870 这个我们并不知道是哪一个字符串,如果现在使用 x/s 查看只会得到一个空字符串,那么很有可能这里保存着我们输入的字符串,我们可以稍后使用gdb打断点的方式来验证我们的猜想并且确定是哪一关输入的字符串

0x0000000000401604 <+64>:    mov    $0x402622,%esi
0x0000000000401609 <+69>:    lea    0x10(%rsp),%rdi
0x000000000040160e <+74>:    callq  0x401338 <strings_not_equal>
0x0000000000401613 <+79>:    test   %eax,%eax

接着判断了字符串是否相同, x/s 0x402622 查看到最后一个 %s 对应的字符串应该是 "DrEvil"

我们先在 <+54> 也就是调用 sccanf之前打一个断点 b *0x4015fa,然后使用 r input.txt 进行调试

bomb提供了一个参数用于从文件中读取内容,所以每一关完成之后我们都可以把答案写在一个文件里(input.txt),然后直接运行它就可以了,从文件中读完所有的内容之后再会切换到STDIN

(gdb) x/d 0x603760
0x603760 <num_input_strings>:   6
(gdb) x/s 0x603870
0x603870 <input_strings+240>:   "7 0"

这里也验证了我们之前的猜想,输入六次进入到这里的时候 num_input_strings 是6,并且 0x603870 地址对应的字符串是 7 0这是我们第四关的答案,所以需要在第四关后面追加一个字符串 DrEvil 就可以进入隐藏关卡了

反汇编 disas secret_phase之后发现这个函数并不复杂

0x0000000000401242 <+0>:     push   %rbx
0x0000000000401243 <+1>:     callq  0x40149e <read_line>
0x0000000000401248 <+6>:     mov    $0xa,%edx              # 十进制
0x000000000040124d <+11>:    mov    $0x0,%esi
0x0000000000401252 <+16>:    mov    %rax,%rdi
0x0000000000401255 <+19>:    callq  0x400bd0 <strtol@plt>

即将字符串转为10进制的整数(long类型)

0x000000000040125a <+24>:    mov    %rax,%rbx
0x000000000040125d <+27>:    lea    -0x1(%rax),%eax
0x0000000000401260 <+30>:    cmp    $0x3e8,%eax                  # x-1 <= 1000
0x0000000000401265 <+35>:    jbe    0x40126c <secret_phase+42>
0x0000000000401267 <+37>:    callq  0x40143a <explode_bomb>
0x000000000040126c <+42>:    mov    %ebx,%esi                    # esi = x
0x000000000040126e <+44>:    mov    $0x6030f0,%edi               # 一个地址
0x0000000000401273 <+49>:    callq  0x401204 <fun7>
0x0000000000401278 <+54>:    cmp    $0x2,%eax                    # 返回值应该为2
0x000000000040127b <+57>:    je     0x401282 <secret_phase+64>
0x000000000040127d <+59>:    callq  0x40143a <explode_bomb>

输入的整数应该小于等于 1001, 接着edi是一个地址,esi是输入的整数,调用 fun7,并且返回值应为2

假设fun7的形参如下

int fun7(long *p, long x) {
  return;
}

0x0000000000401204 <+0>:     sub    $0x8,%rsp
0x0000000000401208 <+4>:     test   %rdi,%rdi                  # 如果p==0(即空地址),返回-1
0x000000000040120b <+7>:     je     0x401238 <fun7+52>
0x000000000040120d <+9>:     mov    (%rdi),%edx                # edx = *p
0x000000000040120f <+11>:    cmp    %esi,%edx                  # if (*p <= x)
0x0000000000401211 <+13>:    jle    0x401220 <fun7+28>
0x0000000000401213 <+15>:    mov    0x8(%rdi),%rdi             # p = p + 0x8
0x0000000000401217 <+19>:    callq  0x401204 <fun7>            # 再次调用
0x000000000040121c <+24>:    add    %eax,%eax                  # return 2*fun7(p+0x8,x)
0x000000000040121e <+26>:    jmp    0x40123d <fun7+57>
0x0000000000401220 <+28>:    mov    $0x0,%eax
0x0000000000401225 <+33>:    cmp    %esi,%edx                  # if (*p == x) return 0
0x0000000000401227 <+35>:    je     0x40123d <fun7+57>
0x0000000000401229 <+37>:    mov    0x10(%rdi),%rdi            # p = p + 0x10
0x000000000040122d <+41>:    callq  0x401204 <fun7>            # 再次调用
0x0000000000401232 <+46>:    lea    0x1(%rax,%rax,1),%eax      # return 2*fun7(p+0x10,x)+1
0x0000000000401236 <+50>:    jmp    0x40123d <fun7+57>
0x0000000000401238 <+52>:    mov    $0xffffffff,%eax           # return -1
0x000000000040123d <+57>:    add    $0x8,%rsp
0x0000000000401241 <+61>:    retq

所以整体的思路还是很清晰的,这应该是一个二叉树的结构,如果大于则+16,如果小于则+8,类似root->left,root->right的情况

那么我们就可以从地址 0x6030f0 出发,左右左右的跳转,完整的画出这棵二叉树

20221109185152

这段程序对应的C代码如下

int fun7(long *p, long x) {
  if (p == 0) return -1;
  if (*p <= x) {
    return 2*fun7(p+16,x)+1; // 向右
  } else {
    if (*p == x) return 0;
    else return 2*fun7(p+8,x); // 向左
  }
}

预期结果是2那么根据if分支的选项满足这个输出的结果应该是 2(2(0)+1), 对应 左-右(22); 和 2(2(2*(0))+1), 对应 左-右-左(20)

在第四关后面追加一个字符串 DrEvil 就可以进入隐藏关卡了

所以本题答案有两个

22
20

完整答案

注意如果是使用 input.txt 然后运行 ./bomb input.txt, 最后结尾需要有一个换行!

Border relations with Canada have never been better.
1 2 4 8 16 32
0 207
7 0 DrEvil
ionefg
4 3 2 1 6 5
20

关于 @plt

回答1

回答2