CSAPP | Lab2-Bomb Lab 深入解析_csapp lab2

Lab2 Bomb Lab

实验概述

Bomb Lab提供一个无法编译的C文件bomb.c，以及一个二进制可执行文件bomb，当运行bomb文件时，它会要求输入6个字符串，如果其中的任何一句是错的，炸弹就会“爆炸”。我们必须利用调试工具gdb和反汇编工具objdump，对bomb进行逆向分析，依次找到满足要求的6个字符串，从而“拆除”炸弹

这个实验很有趣，老师为整个实验提供了一个故事主题：对抗DrEvil，拆除炸弹。同时，这个实验非常考察耐心和阅读汇编的能力，而且可以学习使用调试工具gdb

首先看bomb.c文件

bomb.c中共有6个函数phase_1~phase_6，每个函数都会从输入中读取input，即要输入的字符串。phase_defused函数用于判断炸弹是否被拆除。猜测phase函数中可能会有像exit(0)的终止方式，当输入的字符串不正确时，就会提前终止phase函数，导致炸弹拆除失败

在后面你会看到，函数<explode_bomb>会调用exit，使程序提前终止。你要做的就是阅读汇编程序，然后推出一个**不会使控制到达<explode_bomb>**的字符串，这样的字符串就是答案

注意：不要忽略一些函数名，以及bomb.c中的部分注释，它们能提供很多有用的信息

Tools

• 程序调试工具：gdb
• 反汇编工具：objdump

可以先学习一下gdb和objdump的基本操作，再进行实验

GDB使用详解 - 知乎 (zhihu.com)

Linux下反编译命令objdump快速学习总结（附实例操作）_linux反编译-CSDN博客

本实验中，可以使用gdb指令x查看内存中的数据，也可以设置断点，进行调试

gdb调试命令：

查看内存数据：

首先使用objdump对bomb文件反汇编，获得反汇编文件bomb.s

objdump -d bomb > bomb.s
1

然后加载bomb文件，进入gdb调试模式

gdb ./bomb
1

开始拆弹！

phase_1

可以在shell中使用disas命令，对phase_1反汇编，也可以在bomb.s文件中查找函数名phase_1

使用disas命令反汇编phase_1：

(gdb)disas phase_1
1

• 第1行，为函数分配栈帧（8 bytes）

• 第2行，赋值，%rsi=0x402400，这像是一个内存地址，不妨查看一下这个地址处的数据，使用命令：

  x/s 0x402400 # 这个指令用于以字符串格式查看存储在内存地址 0x402400 处的数据
  1

  结果如下：

  

• 第3行，调用函数<strings_not_equal>，从这个函数名可以知道，它是用来判断字符串是否相等的，而第2行对%rsi进行赋值，就是在设定参数。那么按照参数寄存器的顺序，%rdi存放第一个参数，指向我们传入的字符串**（实际上寄存器中存放的是这个字符串的地址，用“指向”描述不准确，但是为了便于理解和说明，我会用“指向”来描述寄存器的这种情况）**。<strings_not_equal>会判断%rdi与%rsi所指向的字符串是否相同，猜测相同的话，会返回0(%rax=0)

• 第4、5行，判断%eax == 0，若%eax为0，则跳转至第7行，释放栈帧，函数结束；若%rax != 0，则跳至第6行，调用<explode_bomb>函数，炸弹爆炸。所以你输入的字符串要保证与%rsi所指向的字符串相同，使%eax为0，函数正常结束，而不会调用<explode_bomb>，使函数提前结束。这就是拆弹的方法——保证控制流不会到达<explode_bomb>

answer

答案就是这句话：

Border relations with Canada have never been better.

可以将答案存放到一个txt文件中，然后使用命令./bomb xxx.txt（xxx换成你的txt文件名），这样就可以保留前面phase的答案，不需要依次输入答案

phase_1比较简单，但由于是第一道，可能不太了解lab的目的，所以会导致思路不畅。这很正常，跟着phase_1解析做一遍就好了

phase_2

阅读汇编代码，我的方法是先用自然语言逐条描述，对于判断分支，先将一个分支分析到底，再分析下一个分支；若需要的话，可以将分析过程转换为C语言，去除汇编中冗余的部分，使过程清晰；对于过于冗长的代码，需要分段来看，每一段可能是一个循环过程，一个判断过程，两个循环之间 或 循环、判断之间的过程

先看前几行

• 第1、2行，将被调用者保存寄存器的值入栈
• 第3行，为函数分配大小为0x28=40个字节的栈帧
• 第4行，赋值，%rsi = %rsp，使%rsi也指向栈顶

此时栈的情况：

这个图源自(99+ 封私信 / 83 条消息) 大猫咋 - 知乎 (zhihu.com)，感谢学长的分享

反汇编<read_six_numbers>：

第12行调用了sscanf函数，第12行以上在为sscanf设置参数

sscanf的函数原型如下：

int sscanf(const char *str, const char *format, ...);
1

这个函数的作用是从字符串 str 中根据指定的格式 format 提取数据，并将提取的数据按照格式存储到后续参数中，然后返回读到的数据个数。

根据参数寄存器的顺序，可以判断%rdi存放str的地址，%rsi存放格式format（%d %s···），其余的寄存器存放str要存入的地址

第10行，赋值，%rsi= 0x4025c3，查看这个地址的内容：

说明传入的字符串是6个整数

到达第12行时，寄存器%rdx~%r9的值如下：

%rsi指向phase_2的栈顶，可以看到程序使用%rsi来保存原函数phase_2的栈顶地址，并通过对%rsi的运算获得phase_2中的内存地址

同时，函数还设定了两个参数存放在栈上：M[%rsp]=%rsi+0x10,M[%rsp+0x8]=%rsi+0x14

当前栈的情况：

这个函数共有6个参数，传入了6个指针，其中4个存放在寄存器中，2个存放在<read_six_numbers>的栈中。由于通过栈传递参数时，所有的数据大小都向8的倍数看齐(csapp p169)，所以没有使用%rsp+0x4的空间存放参数

%rdi指向我们输入的字符串，sscanf将该字符串存放在M[%rsi],M[%rsi+0x4],M[%rsi+0x8],M[%rsi+0xc],M[%rsi+0x10],M[%rsi+0x14]

第13、14、15行出于程序健壮性的考虑，比较%eax与5，若%eax>5，则释放栈帧，函数返回；若%esx<=5，说明传入sscanf的数字个数≤5个，则引爆炸弹

回到phase_2：

<read_six_numbers>返回时，%rsp与%rsi都指向栈顶，此时这个字符串存放在M[%rsp],M[%rsp+0x4],M[%rsp+0x8],M[%rsp+0xc],M[%rsp+0x10],M[%rsp+0x14]

我们阅读接下来的汇编代码来确定这六个整数，使用自然语言描述这个过程（6~25行）：

然后绘制栈的图像，记录寄存器的值，进行一遍这个过程，要避免引爆炸弹。这样就能了解这个过程在做什么

使用C语言描述这个过程：

//如果栈顶元素不为1，则引爆炸弹
//rsp、rbx、rbp是整型指针，eax是整型变量
if(*rsp != 1)
{
    exit(0);
}
rbx = rsp + 1;	//rbx指向栈中的第二个元素
rbp = rsp + 6;	//rbp指向栈中的第七个元素
do
{
    eax = *(rbx-1);	//eax指向rbx的前一个元素，初始时指向栈顶元素
    eax *= 2;
    //如果CurrentNum != PreviousNum * 2，则引爆炸弹
    if(*(rbx) != eax)
    {
        exit(0);
    }
    rbx++;	//rbx指向下一个元素
}while(rbx != rsp);	//当rbx指向第七个元素的时候，结束循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

上面的分析说明栈中的六个整数要满足 **CurrentNum = PreviousNum * 2，栈顶元素=1，**所以从栈顶元素到栈中的第六个元素，依次是：1 2 4 8 16 32

下面就是这六个数字的顺序问题，参照传参时寄存器使用顺序：

由此可得，字符串中六个整数依次存放在：M[%rsp],M[%rsp+0x4],M[%rsp+0x8],M[%rsp+0xc],M[%rsp+0x10],M[%rsp+0x14]，对应从栈顶元素到栈中的第六个元素

answer

1 2 4 8 16 32

phase_2还是很有含金量的，考察了函数调用，栈帧空间的使用，传参过程、指针知识，建议好好分析一下

phase_3

• 这道题也调用了sscanf函数（第6行），在第4行对%esi赋值，参照phase_2，可知%esi存放的是传入sscanf的字符串的格式，查看一下：

由此可知，传入的字符串是两个整数

• 第2、3行，赋值，%rdx指向M[0x8+%rsp]，%rcx指向M[0xc+%rsp]。在第6行调用sscanf函数时，%rdx、%rcx作为参数，传递两个要存放字符串的地址，所以传入的字符串依次读入到M[%rsp+0x8],M[%rsp+0xc]中

• 第7、8、9行，比较%eax与1，这是出于程序健壮性的考虑，%eax存放sscanf读到的字符个数，当读入的字符≤1个时（%eax<=1），即引爆炸弹；当读入的字符个数≥2个时（%eax>1），跳转至第10行

• 第10、11、12行，比较M[0x8+%rsp]与7的大小，若M[0x8+%rsp]<=7，且M[0x8+%rsp]>=0（使用ja进行判断，将M[0x8+%rsp]转换为无符号数再判断）则对%eax赋值，%eax=M[0x8+%rsp]；否则，引爆炸弹。所以要令M[0x8+%rsp]与%eax相等

• 第13行，跳至一个间接引用的地址，该地址存放在M[0x402470+8*%rax]中，由上一步分析可知，0<=M[0x8+%rsp]<=7，所以%eax也要在[0,7]内取值。不妨试试%eax=1，则跳转的地址存放在M[0x402478]中，查看一下内容：

  

  将跳转至第31行。再试试%eax=2，看看跳转的地址是什么——查看M[0x402480]：

  

  将跳转至第16行。这两个跳转地址都可以，而且这两个地址下面的过程除了赋值不同外，其它均相同，所以答案会有两个。接下来以跳转至第16行为例
  

• 第16行，赋值，%eax=0x2c3，十进制为707，然后跳转至第32行

• 第32、33、34行，比较%eax与M[0xc+%rsp]的大小，若%eax = M[0xc+%rsp]，则跳转至第35行，释放栈帧，函数结束；否则会引爆炸弹。所以要令%eax与M[0xc+%rsp]相等，即M[0xc+%rsp]= 0x2c3 = 707

• 由于我们选择%eax=2，跳转至第16行，所以M[0x8+%rsp]=%eax=2

根据寄存器传参顺序，可知传入的字符串为：M[0x8+%rsp],M[0xc+%rsp]，即为2 707

若选择%eax=1，则M[0x8+%rsp]=%eax=1，最终M[0xc+%rsp]= %eax = 311，传入的字符串为1 311

answer

答案有两个，任选其一即可

1 311 or 2 707

phase_3与phase_2思路相仿，都是用sscanf将我们输入的字符串读到函数的栈中，然后根据一系列判断条件，推得栈中的数值。相比于phase_2，难度不大

phase_4

对phase_4反汇编：

• 前6行与phase_3相同，%rdx与%rcx指向M[%rsp+0x8]和 M[%rsp+0xc]，第6行调用sscanf读入我们输入的字符串，然后将字符串传入到M[%rsp+0x8]和 M[%rsp+0xc]

  和phase_3一样，%esi存放的是传入sscanf的字符串的格式，查看一下：

  

  由此可知，传入的字符串是两个整数

• 第7行，比较%eax与2的大小，若%eax != 2，则引爆炸弹；若%eax=2，则跳转至第9行。

• 第9行，比较M[0x8+%rsp]与14的大小，若M[0x8+%rsp]≤14，则跳转至第12行；若M[0x8+%rsp]>14，则引爆炸弹。所以要令M[0x8+%rsp]≤14

• 第12、13、14行，赋值，%edx=0xe，%esi=0，%edi= M[0x8+%rsp]

• 第15行，调用函数< func4 >，第12~14行的赋值是为该函数设置参数

• 第16、17行，< func4 >结束调用，比较返回值%eax与0，若%eax != 0，则引爆炸弹；若%eax=0，则跳至第18行。所以要令返回值%eax=0，这个条件可以用于分析函数< func4 >的执行过程

• 第18、19、20行，比较M[%rsp+oxc]与0的大小，若M[%rsp+0xc]=0，释放栈帧，函数结束；否则，引爆炸弹。所以要令M[%rsp+0xc]=0

使用C语言描述这个过程：

phase_4(char* rdi)	//rdi指向我们输入的字符串，是一个字符指针
{
    int* rdx = rsp + 2;	//rdx指向栈空间0x8+%rsp，第2行
    int* rcx = rsp + 3;	//rcx指向栈空间0xc+%rsp，第3行
    int eax = 0;	    //第5行
    eax = sscanf(rdi, "%d %d", rdx, rcx);	//第6行，调用sscanf函数，并将返回值（读入的字符个数）存放在eax中
    //第7、8行，程序健壮性检验，若读入的字符不是2个，则引爆炸弹
    if(eax != 2)
    {
        exit(0);
    }
    //第9、10、11行，比较 M[0x8+%rsp] 与 14 的大小，若M[0x8+%rsp]>14，或M[0x8+%rsp]<0，则引爆炸弹
    if((unsigned)(*rdx) > 14)
    {
        exit(0);
    }
    int edx = 11;	//第12行
    int esi = 0;	//第13行
    int edi = *(rsp + 2);	//第14行
    eax = func4(edi, esi, edx);	//第15行，调用函数func4
    //第16~17行，比较%eax与0的大小，若%eax !=0,则引爆炸弹
    if(eax != 0)
    {
        exit(0);
    }
    //第18~22行，比较M[0x8+%rsp]与0的大小，若M[0x8+%rsp] != 0，则引爆炸弹
    if(*(rsp+3) != 0)
    {
        exit(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

分析上述过程，为避免引爆炸弹，需要满足：传入两个整数的字符串；调用func4后，eax=0；M[0xc+%rsp]=0

现在来分析func4：

这是一个递归函数，转换为C语言：

//初始值:edi=M[0x8+%rsp],esi=0x0,edx=0xe
int func4 ( int edi, int esi, int edx )
{// 返回值为eax
    eax = edx - esi;  //第2、3行
    
    //这个部分实际上在做eax/2 在C语言中，eax/2会直接向0舍入，具体的细节看不见，在汇编中，你会看到如何一步步巧妙地根据eax的正负（不需要判断），使eax/2向0舍入
    unsigned offest = (unsigned)eax;
    offest = offest >> 31;	//第5行，对eax进行逻辑右移，目的是得到符号位（eax<0, offest=1;eax>0, offest=0）但不能直接获得，要转换为无符号数再移位
    int shift = (int)offest;	//若无符号数参与计算，则整个式子都转换为无符号数运算，所以要先将offest转换为有符号数，再参与下面的运算
    eax = (eax + shift) >> 1;  //第7行，对eax进行算术右移
 
    ecx = eax + esi;  //第8行
    if(edi < ecx) 
        return  2 * func4(edi, esi, edx - 1); //第13行
    else if (edi > ecx)
        return  2 * func4(edi, esi + 1, edx) + 1; //第20行
    else
        return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

当程序进行首次判断时，计算可得eax=7，ecx=7。一种可能的执行过程：程序进入第三个分支（edi == ecx），func4结束调用，返回0。这满足%eax=0的要求，所以M[0x8+%rsp]=7

现在分析一下eax/2的部分：

• 若eax≥0，则offest = 0（正数的符号位为0），那么(eax+0) >> 1就是eax/2
• 若eax<0，则offest = 1（负数的符号位为1），那么(eax+1)>>1等同于(eax+ (1<<1)-1)>>1，也就是书上的公式：(eax+(1<<k)-1)>>k，此时k=1，使eax/2能向0舍入

这个设置很巧妙，不需要判断正负（书上有一道练习题，需要判断正负再除以2^k），就能计算出eax/2（向0舍入）

回到phase_4，可以得到M[0x8+%rsp] = 7，M[0xc+%rsp]= 0，这也是我们输入的字符串的内容

answer

7 0

phase_4的代码风格与前两道类似，中间做了一个逆向分析：已知函数的返回值，逆向分析函数的运行过程，难度不大

phase_5

对phase_5反汇编

phase_5比较长，我们分块分析

part1

• 第3行，赋值，%rbx=%rdi，%rdi是用来传递参数的第一个寄存器，所以猜测%rdi指向我们输入的字符串，使用%rbx储存%rdi是为了避免在函数调用中，丢失%rdi的值
• 第4，5行，把fs段偏移0x28的一个数据储存到%rsp+0x18处，这是为了防止缓存区溢出。
• 第6行，%eax与%eax自己异或，效果是将%eax清0
• 第7行，调用函数<string_length>，从名字上可以看出，它的用处是统计传入的字符串的长度，并返回长度。这里%rdi作为参数，指向我们输入的字符串，所以这个函数会统计我们传入的字符串的长度，并将这个长度值返回到%eax中
• 第8~11行，用于判断我们传入的字符串长度是否为6，若不是6，则引爆炸弹。**所以我们要传入一个长度为6的字符串。**当传入的字符串长度为6时，跳转至0x4010d2，将%eax清0。再跳转至0x40108b

part1告诉我们要传入一个长度为6的字符串

part2

part2是一个for循环过程

初始%rax=0，%rbx=%rdi，指向我们传入的字符串，不妨设这个字符串为str

• 第1行，将%rbx+%rax处1个字节的内容传递给%ecx，由于%rbx指向str，所以%rbx+%rax指向str[%rax]，%rax是索引。这一行等价于将str[%rax]传递给%ecx

• 第2、3、4行，%cl是%rcx的低8位，第2、3行将%ecx的低8位传递给%edx中。在第4行中，%edx做了与操作，目的是保留%ecx的低4位的值，也就是字符str[%rax]anscii码的低4位的值。例如当前str[%rax]=b，b的anscii码的位表示为：0110 0010，所以此时%edx = 0010 = 2

• 第5行，赋值，%edx = M[0x4024b0+%rdx]，查看一下0x4024b0的内容：

  

  0x4024b0处存放了一个字符串，设这个字符串为str1，那么M[0x4024b0+%rdx]就是str1[%rdx]，这一行等同于将字符str1[%edx]保存在%edx中。延续str[%rax]=b的例子，此时%edx=0010=2，str1[%rdx]就是str1[2]=d，所以当前%edx保存字符d

• 第6行，赋值，M[0x10+%rsp+%rax]=%dl，%dl是%edx的低8位。这一步将%edx保存的字符传入栈中保存，%rax仍然是索引，这个字符串的起始位置为%rsp+0x10，不妨设这个字符串为str2。这一行等同于str2[%rax]=%edx。延续上面的例子，str2[%rax]中保存字符d

• 第7行，比较%eax与6，若%eax != 6，则跳转至第1行，循环这个过程

设字符str[%rax]的低4位的值为ebx，则str2[%rax]存放了str1[ebx]。所以，当我们知道str2[%rax]的内容时，就可以参照str1，得到索引ebx的值，即得到str[%rax]的低4位的值，进而逆推str[%rax]的内容。

例如我们已知str2[3]为d，参照str1，d是str1[2]，所以ebx=2，说明str[3]的低4位为 0010，由于str[3]的高四位未知，所以可能有多个答案，其中一个为字符b：0110 0010，则str[3]=b

这个过程写成C语言：

str1 = "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?";
//str是我们传入的字符串，str1是0x4024b0处存放的字符串，str2是存放在函数栈中的字符串，起始地址为ox10+%rsp
for(rax=0; rax<6; rax++)
{
    ecx = str[rax];		//第1行
    edx = ecx & 0xf;	//第2~4行,edx只保留ecx的低4位
    str2[rax] = str1[edx];	//第5~6行
}
1
2
3
4
5
6
7
8

由str2、str1与str的关系，我们可以逆推str。所以接下来要确定str2的内容

part3

part2中的循环结束后，执行part3

• 第1行，赋值，M[0x16+%rsp]=0，参照part2中str2的起始位置，这一步是在str2的末尾添加 ‘\0’

• 第2、3行，设置参数，其中%rdi指向str2，%rsi存放0x40245e，查看一下这个地址存放的内容：

  

  0x40245e处存放一个字符串：“flyers”，%rsi指向这个字符串

• 第4~7行，调用函数<strings_not_equal>，这个函数在phase1中见过，若传入的两个字符串相同，则返回0（%eax=0）。结合上面设定的参数，这个函数在判断str2与“flyers”是否相同，若不同(%eax!=0)，则引爆炸弹。若相同(%eax = 0)，则跳至第12行，函数结束

由part3，我们可以确定str2的内容为：”flyers“

最后一步，根据part2中总结出的关系，我们开始由str2和str1逆推str

str1：“maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?”

str2：“flyers"

• 当rax=0时，str2[0]=f,f出现在str1[9]，所以str[0]的低4位为9：1001
• 当rax=1时，str2[1]=l,l出现在str1[15]，所以str[1]的低4位为15：1111
• 当rax=2时，str2[2]=y,y出现在str1[14]，所以str[2]的低4位为14：1110
• 当rax=3时，str2[3]=e,e出现在str1[5]，所以str[3]的低4位为5：0101
• 当rax=4时，str2[4]=r,r出现在str1[6]，所以str[4]的低4位为6：0110
• 当rax=5时，str2[5]=s,s出现在str1[7]，所以str[5]的低4位为7：0111

由于只知道字符的低4位，所以可能有多组答案，这里根据a的anscii码二进制为 0110 0001，获得一组字符为：ionefg

answer

ionefg

phase_5较复杂，part2和part3环环相扣：part2给出str2、str1与str的关系，part3即给出str2的内容，结合已知的str1，即可逆推得到str，设计的非常巧妙

通过phase_5，我们第一次接触了较长，较复杂的汇编过程，解读方法就是模块化分析，在阅读代码的过程中将代码分块，每块可能是一个循环过程，一个判断过程，两个循环之间 或 循环、判断之间的过程；同时，将汇编代码转换为C语言或伪代码，能剔除汇编中冗余的部分，精简过程，帮助我们把握这个过程的核心行为（可参照对part2的解读）

phase_6

这么长的汇遍代码，一个屏幕都没有放下，不过没有关系，经过phase_5的试炼，我们已经可以从容面对复杂的汇编代码了

还是模块化分析，共分为6个部分

part1

• 前几行是保存参数，分配栈帧
• 第9行中调用了<read_six_numbers>，我们在phase_2中已经详细分析并画了图。这个函数调用的结果是调用者的栈上按顺序存储输入的6个数

返回后，栈及指针情况如下：

图源自(99+ 封私信 / 83 条消息) 大猫咋 - 知乎 (zhihu.com)，感谢学长的分享

part1将我们输入的6个数字读入到栈中

part2

这是一个双层循环，外层：%r12d为索引，逐步+1，循环的条件为%r12d<6；内层：%rbx为索引，逐步+1，循环的条件为%rbx≤5

这个过程很乱，可以先用自然语言把这一部分描述一遍，然后再走一遍，观察寄存器%r12d、%r13d、%rax、%rbx的变化

第二部分的C语言代码：

r13 = rsp; //rsp指向数组n的第一个节点，n=rsp
//r13指向n[r12d]，初始时r13指向num[0]
//这个双循环类似冒泡排序，目的是检测这六个数字是否为[1,2,3,4,5,6]的任意排序
for(r12d=0; r12d<6; r12d++)
{
    (unsigned)rax = *r13;	//读取r13指向的数值num[r12d]，并转换为无符号数
    //若rax-1 > 0x5，则爆炸，程序结束
    //这里很巧妙，使用无符号数-1来检验r13所指的元素数值是否在1~6内，如果*r13<=0，那么rax-1是一个极大的数（当*r13=0时，rax=0，但是rax-1是一个极大的数，这就是-1的用处———>检验*r13==0）
    if(rax-1 > 5)	
    {
        exit(0);
    }
    //各个元素之间进行数值比较，检验是否有两个元素的数值相等
    for(rbx=r12d+1; rbx<=5; rbx++)
    {
        //若 *(r13+rbx) 与 *r13相等，则爆炸，程序结束
        if(*(r13+rbx) == *r13)
        {
            exit(0);
        }
    }
    r13++;	//r13指向下一个元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

part2检测这六个数字是否为[1,2,3,4,5,6]的任意排序（六个数字在1~6之间，且任意两个数字不相等）

part3

又是一个循环，比part2简单

part3的C语言代码：

rsi = 6+rsp;	//rsi指向数组最后一个数字的下一个位置
rax = rsp;		//rsp指向第一个数字n[0]
ecx = 7;		//ecx赋值为7
//循环，遍历这6个节点
do
{
    *rax = 7 - *rax;	//rax指向的数组元素的值 = 7 - 该元素的值
    rax++;	//rax指向下一个元素
}while(rax != rsi);
1
2
3
4
5
6
7
8
9

part3将这六个int变为7-int，此时数组num仍然是[1,2,3,4,5,6]的任意排序

part4

这又是一个双层循环，外层：rsi为索引，逐步+0x4，循环条件为rsi<0x18；内层：rax为索引，逐步+1，循环条件为rax != rcx

看到0x6032d0，做了5个半phase了，是不是有点想法了：它会不会是一个指针呢？我们查看一下它的内容：

后面的6304480之类的是什么呢？我们再用16进制的格式查看一下0x6032d的内容：

我们会发现0x6032d0~0x603320，第三列均为一个地址，而且每个地址之间相差16个字节。我们可以认为这是一个链表，前两列是链表中节点的数据域，第三列是节点的指针域，它的形式如下：

struct node{
    int val;
    int number;
    struct node* next;
}
// node[1]->next = node[2],...以此类推
1
2
3
4
5
6

我们写出part4的C代码：

for(rsi=0; rsi<0x18; rsi+=0x4)
{
    rcx = *(rsp+rsi);
    if(rcx <= 1)		//实际上，rcx至少为1，所以它等价于 rcx == 1
    {
        rdx = 0x6032d0;(链表第一个节点的地址)
        *(0x20 + rsp + 2*rsi) = rdx;	//在栈中的 (8+%rsp+2*rsi) 的空间内（从栈顶地址+0x20的位置开始，偏移量为2 *rsi），存放第 n[rsi] 个链表节点的地址
    }else
    {
        rdx = 0x6032d0;
        for(rax=1; rax != rcx; rax++)
        {
            rdx = *(rdx + 0x8);	//根据gdb，一个节点有16个字节，前8个字节为数据域，后8个字节为下一个节点的地址，所以rdx+0x8是下一个节点的地址，rdx = *(rdx+0x8)意味着rdx指向下一个节点
        }
        *(0x20 + rsp + 2*rsi) = rdx;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第四部分的结果是：在栈中的 M[0x20+%rsp+2*rsi] 的空间内（从栈顶地址+0x20的位置开始，偏移量为2 *rsi），存放第 n[rsi] 个链表节点的地址，其中，链表的第一个节点地址为0x6032d0，每一个节点的数据域为8个字节，指针域为8个字节

比如，当rsi=1时，假设n[1]为4，则在 M[0x20+%rsp+2]处存放第4个节点的地址

此时，栈的情况为：

part5

part5的C语言实现：

rbx = M[0x20+rsp];	//rbx存放了&node[n[0]]
rax = 0x28+rsp;		//指向存放&node[n[1]]的内存单元
rsi = 0x50+rsp;		//指向末尾，存放&node[n[5]]的内存单元 的下一个单元
rcx = rbx;			//与rbx相同，rcx指向node[n[0]]
do
{
    rdx = M[rax];	    //设当前rax指向 存放&node[n[i]] 的内存单元，则rdx存放了&node[n[i]]
    M[rcx+0x8] = rdx;	//将节点node[n[i-1]]的指针域修改为&node[n[i]]，使节点node[n[i-1]]指向node[n[i]]
    rax = rax+0x8;		//rax指向下一个内存单元————存放有 &node[n[i+1]] 的内存单元
    rcx = rdx;			//rcx指向节点node[n[i]]
}while(rax != rsi)
1
2
3
4
5
6
7
8
9
10
11

part5实现的效果是：将链表节点的顺序调换成数组中的顺序

原来链表中各个节点的情况：

假设数组n = 3,2,6,5,1,4，则part5结束后，各个节点的顺序为：

924 3
168 2
443 6
477 5
332 1
691 4
1
2
3
4
5
6

part6

分析一下part5结束后，部分寄存器的值：

• %rax：%rsp+0x50，指向 存放&node[n[5]]的内存单元 的下一个单元
• %rdx：%rsp+0x48，指向 存放&node[n[5]]的内存单元
• %rbx：M[%rsp+0x20]，指向 节点node[n[0]]

part6反汇编：

• 第2行，赋值，%ebp = 5
• 第3、4行，将node[n[1]]的数据读出来，赋值给%eax
• 第5行，比较M[%rbx]与%eax，就是在比较node[n[0]]的数据与node[n[1]]的数据
• 第6、7行，若node[n[0]]≥node[n[1]]，则跳转至第8行；否则，引爆炸弹
• 第8行，赋值，%rbx = M[0x8+%rbx]，使rbx指向下一个内存单元。对于现在这个过程而言，就是使rbx指向 存放&node[n[1]] 的内存单元
• 第9、10行，%ebp--，若%ebp不为0，则跳转至第3行。可以看出这是一个循环过程，而%ebp就是用于计数的

将这个过程转换为C语言：

/*
初始：rbx指向node[n[0]]
*/
for(ebp=5; ebp>0; ebp--)
{
    rax = rbx->next->data;	//rax为rbx指向的下一个节点的数据data
    if(rbx->data < eax)	//若rbx指向的节点的data < rbx指向的节点的data,则爆炸
    {
        exit(0);
    }
    rbx = rbx->next;	//rbx指向下一个节点
}
函数结束.
1
2
3
4
5
6
7
8
9
10
11
12
13

第六部分检测 当前的链表中（已调整为数组顺序了），是否满足curArrayValue >= nextArrayValue，即降序排列的

由于链表节点data是降序排列的，根据节点中的数据（已知），就可以得到调整后链表中各节点的顺序，进而求出数组n的各个元素的值

原始链表顺序：

按照数组顺序调整后的链表顺序：

924(3)->691(4)->477(5)->443(6)->332(1)->168(2)

故n各个元素为：3 4 5 6 1 2

但是别忘了，在part3中，对数组n进行了运算：n[i] = 7-n[i]，所以原始数组的各个元素为：4 3 2 1 6 5，即为传入的参数

answer

4 3 2 1 6 5

phase_6是很有挑战性的，代码非常长，而且有双重循环这样的复杂结构，会很难分析。对于这样长的汇编代码，我们在分析的时候应该将其划分为多个部分，每个部分可能是一个循环过程，一个判断过程，两个循环之间 或 循环、判断之间的过程。这样的模块化分析过程能帮助我们理清思路，看懂程序的行为

同时，phase_6中出现了与链表有关的代码，链表各个节点有数据域和指针域，如果节点（初始地址为add）的数据域是8个字节，就可以使用M[add+0x8]读取该节点的指针域内容，即为下一个节点的地址。使用add = M[add+0x8]，即可使add指向下一个节点

secret_phase

终于将6个phase都完成了（我也是这么以为的 :-），但我在看别人的博客时，发现竟然还有一个secret_phase!

我打开bomb.s，按照顺序，应该是在phase_6的下面，然后发现了：

这个secret_phase就是隐藏的彩蛋，可是我不能输入对应secret_phase的字符串，难道我还漏掉了什么？

在bomb.c中，每一个phase函数的下面都有一个phase_defused函数，它应该是用来检验炸弹是否被拆除的，secret_phase作为一个隐藏的炸弹，是不是也与phase_defused有关呢？

进入secret_phase

根据上面的猜想，我们查看phase_defused代码：

简要分析一下phase_defused函数：

• 查看第10行给的内存地址：

  

• 再查看一下第11行的内存地址：

  

  这里竟然是空的。

• 第12、13、14行，调用sscanf函数，如果读入的字符不是3个的话，那么就会跳转到26行。而25行调用secret_phase函数，所以当读入的字符不等于3个时，会导致secret_phase不能被调用。所以初步判断，要输入一个有3个参数的字符串来调用secret_phase函数。再结合第10行内存地址的内容，可以判断这里输入一个有两个整数，一个字符串的字符串

• 第15~19行，%esi=0x402622，%rdi=0x10+%rsp,然后调用函数strings_not_equal，比较%rdi和%rsi中两个字符串。若两个字符串不相同，则%eax!=0，就跳转至第26行，同样会导致secret_phase不能被调用，所以输入的这个字符串应该与%esi中保存的字符串相同。对于第15行的 0x402622，猜测它可能是储存这个字符串的位置，使用gdb命令来查看一下：

  

  这应该是字符串中%s对应的内容——DrEvil。然而字符串的前两个整数还没能确定，而第11行的0x603870就是存放了这两个整数，我们打断点看一下：

  

这个地方我疑惑很久，不知道这个字符串是怎么输进去的（第6个phase答案输进去后程序就结束了），但看到了<input_strings+240>，说明这是我们输入的字符串，再对照了一下psol.txt（我把答案写到这里了，避免重复输入），这不就是phase_4的答案吗！我试着将DrEvil输入到7 0 的后面，终于进入了secret_phase!

解决secret_phase

• 第2~5行，赋值，%edx=0xa，%esi=0x0，%rdi=%rax，保存 我们输入的字符串的地址

• 第6行，调用函数strtol，strtol函数原型：

  

  第2~5行都是在传参数，其中%rdi保存了我们输入的字符串的地址，是要转换的字符串。strtol函数将这个字符串中的 数字字符串 转换为 长整型的数字，比如字符串“12345”可以转换为长整型的数字12345

• 第8~11行，%eax = %eax-1，然后比较%eax与0x3e8(1000)，若%eax-1≥0x3e8，则跳转至第12行；否则，引爆炸弹

• 第12、13行，传参，%esi=%ebx，%edi=0x6030f0，%ebx存放了由字符串转换的数字（第7行），对应我们输入的字符串。查看一下0x6030f0处的内容，发现也有很多单元是空的，所以我们再打断点看一下（运行时，要输入一个范围在1~1001的数字字符串，避免触发第11行的炸弹）：

  

  发现0x6030f0处也存放了一个结构体，而且它有两个指针，一个数值。当我们将它绘制出来时，会发现各个节点构成了一棵树，将这棵树的节点定义为：

  typedef struct node
  {
      long data;
      struct node* lchild;
      struct node* rchild;
  }NODE;
  1
  2
  3
  4
  5
  6

• 第14~17行，调用了一个函数< fun7 >，然后比较返回值%eax与2，若%eax=2，则跳至第18行；否则，引爆炸弹

• 第18~22行，释放栈帧，函数结束

由上述分析可知，我们要使fun7的返回值%eax为2，接下来分析fun7

反汇编fun7：

这是一个递归函数，转换为C语言：

//初始，rdi=0x6030f0，esi=由字符串转换的数字
if(rdi == NULL)	//若rdi为空指针，则引爆炸弹，退出程序
{
    exit(0);
}
edx = rdi->data;	
//比较 rdi->data 与 esi
if(edx <= esi)
{
    eax = 0;
    if(edx == esi)
    {
        return eax;
    }
    rdi = rdi->rchild;	//rdi指向右孩子
    fun7(rdi, esi);	    //递归调用
    eax = 2*eax + 1;
}else 
{
    rdi = rdi->lchild;	//rdi指向左孩子
    fun7(rdi, esi);	    //递归调用
    eax *= 2;
}

return eax;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• case1：若rdi->data == esi，则返回0
• case2：若rdi->data < esi，则rdi指向其右孩子，继续递归调用。当递归结束时，返回2*eax+1
• case3：若rdi->data > esi，则rdi指向其左孩子，继续递归调用。当递归结束时，返回2*eax

rdi指向的树：

为了使eax为2，一种可能的递归过程为：

调用1：case3（rdi->data > esi），rdi指向8 ，继续递归 -> 调用2：case2（rdi->data < esi），rdi指向22，继续递归 -> 调用3：case1（rdi->data==esi），递归结束，返回

返回时，eax的变化：

调用3：eax=0 -> 调用2：eax=2*eax+1=1 -> 调用1：eax=2 *eax=2，fun7最终返回2，满足%eax=2的要求

所以esi=22，即我们输入的字符串为22

answer

22

编写这个实验的老师太有趣了，还做了一个隐藏的phase等待我们破解。进入隐藏的phase并解决这个phase都很有难度，可以看出实验的设计者很用心。我们也见到了树在汇编中的实现方式，对比phase6中链表的实现方式，树的每个节点只不过增加了一个指针，还是用访问内存的方式读取这两个指针的内容——lchild：M[0x8+%rdi]；rchild：M[0x10+%rdi]。对fun7递归函数的逆向分析也不是第一次见到，我们在phase4中对fun4也进行了逆向分析，由函数的返回值推断这个函数的执行过程

答案汇总（psol.txt）

可以使用命令./bomb psol.txt将psol.txt中的内容作为答案依次传递给bomb，避免重复输入字符串

结语

这个实验很有趣，也很有挑战性，整个实验涵盖了第三章的大部分知识，难度层层递进，并展示了链表和树在汇编中的实现方式。很值得一做！