CSAPP 2e Bomb Lab 笔记
本文最后更新于 230 天前,其中的信息可能已经有所发展或是发生改变。

这个Lab训练的是分析汇编代码和使用GDB调试的能力。题目是一个二进制文件bomb,和只包含main函数的bomb.c,使用者需要借助工具,在六个Phase中分别输入对应的文本,来解除“炸弹”。一旦输入错误,就会“引爆炸弹”。

每个人生成的bomb内容可能不尽相同,但思路相似,这里只以我做到的版本为例。

实验文件(是32位)https://git.cyp0633.icu/cyp0633/CSAPP-labs/src/branch/master/LAB3-bomblab

环境:Ubuntu 22.04, GDB 12.0.90

参考资料:

前期准备

最基础的一点是,你需要对汇编语言有一定的了解,起码能够大概熟悉CSAPP前三章的内容。

正如上文所说,最好先熟悉一下GDB的使用,边写边查也不是不行,但很容易拖慢速度。可以看看https://www.cnblogs.com/acceptedzhs/p/13161213.html,或者参考资料1中的gdb命令速查,非常有用。可以在GDB中执行layout asm 来打开下面的视图,事半功倍:

GDB分屏

此外,还需要准备一份反汇编代码,objdump -d bomb > bomb.s就可以将bomb反汇编,并将代码保存到bomb.s中。也可以在GDB中进行反汇编。当然,1800行的汇编代码应该不会有人去完全研究,所以只能结合调试来做。

你还需要一个能够计算十六进制的计算器。如果你使用Windows,可以使用自带计算器;在Linux下,可以使用Python。

除此之外,如果你有二进制文件分析的经验,你也可以直接使用angr等工具直接找到答案,达成速通。

Phase 1

查看bomb.c得到Phase 1相关的C代码。

    input = read_line();             /* Get input                   */
    phase_1(input);                  /* Run the phase               */
    phase_defused();                 /* Drat!  They figured it out!
				      * Let me know how they did it. */
    printf("Phase 1 defused. How about the next one?\n");

可以看出,程序先使用read_line()函数读取输入,并让input变量指向它。然后将其传给phase_1。此时char指针应该存储在4(%esp)中。然后查看phase_1的反汇编代码。包括read_line之类的函数并不需要详细了解,因为我们可以很容易看出来它干了什么。

08048b90 <phase_1>:
 8048b90:	83 ec 1c             	sub    $0x1c,%esp
 8048b93:	c7 44 24 04 0c a2 04 	movl   $0x804a20c,0x4(%esp)
 8048b9a:	08 
 8048b9b:	8b 44 24 20          	mov    0x20(%esp),%eax
 8048b9f:	89 04 24             	mov    %eax,(%esp)
 8048ba2:	e8 43 05 00 00       	call   80490ea <strings_not_equal>
 8048ba7:	85 c0                	test   %eax,%eax
 8048ba9:	74 05                	je     8048bb0 <phase_1+0x20>
 8048bab:	e8 45 06 00 00       	call   80491f5 <explode_bomb>
 8048bb0:	83 c4 1c             	add    $0x1c,%esp
 8048bb3:	c3                   	ret    

程序看起来像是构建了strings_not_equal的两个参数,test指令用于判断返回的值是否为0(参见 Stack Overflow),如果为0代表不相等,就跳转到explode_bomb

我们可以直接从两个参数入手,一个是我们输入的内容,另一个0x804a20c自然就指向了我们想要的字符串。进入gdb,打断点,使用x/s 0x804a20c读取那个位置的字符串,然后输入c继续运行,将其输入即可。解出Phase 1答案是“You can Russia from land here in Alaska.”。

建议将断点打到read_line上,如果打到phase_1上,便无法在读到答案之后输入文字,可能要炸一次炸弹。

Phase 1解决

Phase 2

关键词:循环

main函数中关于Phase 2的部分和Phase 1差不多,那么我们直接来看反汇编。

08048bb4 <phase_2>:
 8048bb4:	56                   	push   %esi
 8048bb5:	53                   	push   %ebx
 8048bb6:	83 ec 34             	sub    $0x34,%esp
 8048bb9:	8d 44 24 18          	lea    0x18(%esp),%eax
 8048bbd:	89 44 24 04          	mov    %eax,0x4(%esp)
 8048bc1:	8b 44 24 40          	mov    0x40(%esp),%eax
 8048bc5:	89 04 24             	mov    %eax,(%esp)
 8048bc8:	e8 4f 06 00 00       	call   804921c <read_six_numbers>
 8048bcd:	83 7c 24 18 00       	cmpl   $0x0,0x18(%esp)
 8048bd2:	75 07                	jne    8048bdb <phase_2+0x27>
 8048bd4:	83 7c 24 1c 01       	cmpl   $0x1,0x1c(%esp)
 8048bd9:	74 1f                	je     8048bfa <phase_2+0x46>
 8048bdb:	e8 15 06 00 00       	call   80491f5 <explode_bomb>
 8048be0:	eb 18                	jmp    8048bfa <phase_2+0x46>
 8048be2:	8b 43 f8             	mov    -0x8(%ebx),%eax
 8048be5:	03 43 fc             	add    -0x4(%ebx),%eax
 8048be8:	39 03                	cmp    %eax,(%ebx)
 8048bea:	74 05                	je     8048bf1 <phase_2+0x3d>
 8048bec:	e8 04 06 00 00       	call   80491f5 <explode_bomb>
 8048bf1:	83 c3 04             	add    $0x4,%ebx
 8048bf4:	39 f3                	cmp    %esi,%ebx
 8048bf6:	75 ea                	jne    8048be2 <phase_2+0x2e>
 8048bf8:	eb 0a                	jmp    8048c04 <phase_2+0x50>
 8048bfa:	8d 5c 24 20          	lea    0x20(%esp),%ebx
 8048bfe:	8d 74 24 30          	lea    0x30(%esp),%esi
 8048c02:	eb de                	jmp    8048be2 <phase_2+0x2e>
 8048c04:	83 c4 34             	add    $0x34,%esp
 8048c07:	5b                   	pop    %ebx
 8048de9:	83 7c 24 18 0e       	cmpl   $0xe,0x18(%esp)
 8048dee:	76 05                	jbe    8048df5 <phase_4+0x38>
 8048c08:	5e                   	pop    %esi
 8048c09:	c3                   	ret    

read_six_numbers很容易让人联想,本题的答案是六个数字。

浅看一眼read_six_numbers函数的反汇编(不需要全看懂),可以得出六个数字的地址是0x8(%esp)一直到0x1c(%esp),对应phase_2中从0x18(%esp)开始(也可以在gdb中对比寄存器得出)。由0x8048bd4的语句来看,如果第二个数不是2,就会触发explode_bomb;由0x8048bcd,如果第一个数不是0,也会爆炸。

0x8048be20x8048c02似乎是一个循环。8048bfa8048bfe的两条lea语句是这个循环的初始化部分,因为这只在0x8048bd9处被调用,正常来说则会跳过这两段。如果这六个数用C形容为int num[6],那么esi就是num+6,是循环的界限,ebx的初值就是num+2,是循环的起始(前两个数已经验证过了),相当于int i=2

初始化之后开始看循环体,从0x8048be20x8048bf6。首先给eax寄存器赋值为num[i-1]+num[i-2],然后将其与num[i]比较。如果不相等,就爆炸。否则,将ebx增4,相当于i++。再将其与边界esi比较,如果不相等,继续循环。

这样,这六个数字的规律就出现了:是前面多了一个0的斐波那契数列,0,1,1,2,3,5。

Phase 2解决

Phase 3

关键词:跳转表

Phase 3反汇编代码太长了,就不一股脑放出来了。

 8048c0a:	83 ec 3c             	sub    $0x3c,%esp
 8048c0d:	8d 44 24 2c          	lea    0x2c(%esp),%eax
 8048c11:	89 44 24 10          	mov    %eax,0x10(%esp)
 8048c15:	8d 44 24 27          	lea    0x27(%esp),%eax
 8048c19:	89 44 24 0c          	mov    %eax,0xc(%esp)
 8048c1d:	8d 44 24 28          	lea    0x28(%esp),%eax
 8048c21:	89 44 24 08          	mov    %eax,0x8(%esp)
 8048c25:	c7 44 24 04 5e a2 04 	movl   $0x804a25e,0x4(%esp)
 8048c2c:	08 
 8048c2d:	8b 44 24 40          	mov    0x40(%esp),%eax
 8048c31:	89 04 24             	mov    %eax,(%esp)
 8048c34:	e8 27 fc ff ff       	call   8048860 <__isoc99_sscanf@plt>

反汇编代码中,一上来就像是构建了一个调用函数的参数列表,似乎有五个参数,均为4字节。往下看,果不其然调用了sscanf。在Shell中执行man sscanf查看Linux自带手册,发现它类似于scanf,只不过输入源是指定的字符串。对照参数列表,发现0x804a25e处是固定的,不随外界改变,同时又在0x4(%esp)即第二个参数位置,那么很可能是format部分。执行print (char*)0x804a25e,得到"%d %c %d",这就对应了第3、4、5个参数(设为int a,char b,int c)的格式了。这里记下,**a = esp+0x8**b = esp+0xc**c = esp+0x10,由leal指令反推, *a = esp+0x28*b = esp+0x27*c = esp+0x2c

 8048c39:	83 f8 02             	cmp    $0x2,%eax
 8048c3c:	7f 05                	jg     8048c43 <phase_3+0x39>
 8048c3e:	e8 b2 05 00 00       	call   80491f5 <explode_bomb>
 8048c43:	83 7c 24 28 07       	cmpl   $0x7,0x28(%esp)
 8048c48:	0f 87 f5 00 00 00    	ja     8048d43 <phase_3+0x139>
 8048c4e:	8b 44 24 28          	mov    0x28(%esp),%eax
 8048c52:	ff 24 85 70 a2 04 08 	jmp    *0x804a270(,%eax,4)

然后将sscanf的返回值与2比较。查看手册得,它会返回格式化字符串中匹配到参数的数量。如果少于3个参数,一样会引爆炸弹。它还会将0x28(%esp)即a与7比较,如果大于7,也会引爆炸弹,那么第一个数的取值被限制在了0~7。

之后很明显是一个跳转表的结构,看起来像来自一个switch语句,大胆猜测是第一个参数为0-7的每种结果。比较简单的一种方法,是在跳转表跳转语句处打断点,将a直接先代入0-7中的一种,步进查看分支的地址,也可以分别使用p/x *address来直接把完整的跳转表挖出来。这里以a = 0为例,其他的应该也差不多。

 8048c59:	b8 68 00 00 00       	mov    $0x68,%eax
 8048c5e:	81 7c 24 2c 8b 01 00 	cmpl   $0x18b,0x2c(%esp)
 8048c65:	00 
 8048c66:	0f 84 e1 00 00 00    	je     8048d4d <phase_3+0x143>
 8048c6c:	e8 84 05 00 00       	call   80491f5 <explode_bomb>
 8048c71:	b8 68 00 00 00       	mov    $0x68,%eax
 8048c76:	e9 d2 00 00 00       	jmp    8048d4d <phase_3+0x143>

上面是a = 0分支的汇编代码。首先给eax赋值,这个之后会用到。然后比较了c与0x18b即395,不相等则会引爆炸弹。如果相等,则再次进行一次跳转:

 8048d4d:	3a 44 24 27          	cmp    0x27(%esp),%al
 8048d51:	74 05                	je     8048d58 <phase_3+0x14e>
 8048d53:	e8 9d 04 00 00       	call   80491f5 <explode_bomb>
 8048d58:	83 c4 3c             	add    $0x3c,%esp
 8048d5b:	c3                   	ret    

比较al与b,不相等的话引爆炸弹。al是将eax的0-7位拎出来。eax = 0x68 = 0x0000 0068,那么al = 0x68。不记得的话,也可以通过GDB执行info registers al查看。在Shell执行man ascii打开ASCII码表,寻找HEX=68,对应的是h。

于是我们得出了a、b、c的值。a和c的值是联动的,一个组合为0和395,而b固定为h。

Phase 3解决

Phase 4

关键词:递归

 8048dbd:	83 ec 2c             	sub    $0x2c,%esp
 8048dc0:	8d 44 24 1c          	lea    0x1c(%esp),%eax
 8048dc4:	89 44 24 0c          	mov    %eax,0xc(%esp)
 8048dc8:	8d 44 24 18          	lea    0x18(%esp),%eax
 8048dcc:	89 44 24 08          	mov    %eax,0x8(%esp)
 8048dd0:	c7 44 24 04 af a3 04 	movl   $0x804a3af,0x4(%esp)
 8048dd7:	08 
 8048dd8:	8b 44 24 30          	mov    0x30(%esp),%eax
 8048ddc:	89 04 24             	mov    %eax,(%esp)
 8048ddf:	e8 7c fa ff ff       	call   8048860 <__isoc99_sscanf@plt>
 8048de4:	83 f8 02             	cmp    $0x2,%eax
 8048de7:	75 07                	jne    8048df0 <phase_4+0x33>
 8048de9:	83 7c 24 18 0e       	cmpl   $0xe,0x18(%esp)
 8048dee:	76 05                	jbe    8048df5 <phase_4+0x38>

这道题一开始也调用了sscanf,和Phase 3差不多。那么方法也一样,熟练地使用print (char*)0x804a3af,得到格式化的形式为"%d %d",就是两个整型。设两个参数分别为a、b,那么有*a = esp + 0x18*b = esp + 0x1c。如果参数不为2个,就会引爆炸弹。

后面还将a与0xe即14(无符号)比较,限制$a \le 14$时跳转到0x08048df5,否则引爆炸弹。那么这个地方干了什么呢?

 8048df5:	c7 44 24 08 0e 00 00 	movl   $0xe,0x8(%esp)
 8048dfc:	00 
 8048dfd:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
 8048e04:	00 
 8048e05:	8b 44 24 18          	mov    0x18(%esp),%eax
 8048e09:	89 04 24             	mov    %eax,(%esp)
 8048e0c:	e8 4b ff ff ff       	call   8048d5c <func4>
 8048e11:	85 c0                	test   %eax,%eax
 8048e13:	75 07                	jne    8048e1c <phase_4+0x5f>
 8048e15:	83 7c 24 1c 00       	cmpl   $0x0,0x1c(%esp)
 8048e1a:	74 05                	je     8048e21 <phase_4+0x64>
 8048e1c:	e8 d4 03 00 00       	call   80491f5 <explode_bomb>
 8048e21:	83 c4 2c             	add    $0x2c,%esp
 8048e24:	c3                   	ret    

这一段先为func4的调用构建了参数,func4的三个参数分别是a、0和0xe即14。然后分别校验了两个条件,是func4的返回值即eax = 0和b=0。既然输入文本的两个部分约束都给出了,只需要枚举$0 \le a \le 14,\ b=0$的每一种可能,总能够找到至少一个答案。幸运的是,试出的第一个组合0 0就是一个解。

但是为了追求完美,我们还需要看看func4干了什么。设传入的三个参数分别为x、y、z,则:

08048d5c <func4>:
 8048d5c:	56                   	push   %esi ;save registers
 8048d5d:	53                   	push   %ebx
 8048d5e:	83 ec 14             	sub    $0x14,%esp ;allocate stack
 8048d61:	8b 54 24 20          	mov    0x20(%esp),%edx ;edx=x
 8048d65:	8b 44 24 24          	mov    0x24(%esp),%eax ;eax=y
 8048d69:	8b 5c 24 28          	mov    0x28(%esp),%ebx ;ebx=z
 8048d6d:	89 d9                	mov    %ebx,%ecx ;ecx=z
 8048d6f:	29 c1                	sub    %eax,%ecx ;ecx=z-y
 8048d71:	89 ce                	mov    %ecx,%esi ;esi=z-y
 8048d73:	c1 ee 1f             	shr    $0x1f,%esi ;esi is sign bit of z-y, biased bit
 8048d76:	01 f1                	add    %esi,%ecx ;ecx=z-y+sign(z-y)
 8048d78:	d1 f9                	sar    %ecx ;ecx=(z-y)/2
 8048d7a:	01 c1                	add    %eax,%ecx ;ecx=y+(z-y)/2=(y+z)/2
 8048d7c:	39 d1                	cmp    %edx,%ecx ;(z+y)/2<=x?
 8048d7e:	7e 17                	jle    8048d97 <func4+0x3b> ;if so, goto 0x8048d97
 8048d80:	83 e9 01             	sub    $0x1,%ecx ;ecx--
 8048d83:	89 4c 24 08          	mov    %ecx,0x8(%esp) ;z(func4)=ecx
 8048d87:	89 44 24 04          	mov    %eax,0x4(%esp) ;y(func4)=eax
 8048d8b:	89 14 24             	mov    %edx,(%esp) ;x(func4)=edx=x
 8048d8e:	e8 c9 ff ff ff       	call   8048d5c <func4> ;recursive call
 8048d93:	01 c0                	add    %eax,%eax ;eax=eax+eax (return value)
 8048d95:	eb 20                	jmp    8048db7 <func4+0x5b> ;return eax
 8048d97:	b8 00 00 00 00       	mov    $0x0,%eax ;eax=0
 8048d9c:	39 d1                	cmp    %edx,%ecx ;ecx<=x?
 8048d9e:	7d 17                	jge    8048db7 <func4+0x5b> ;if so, return 0
 8048da0:	89 5c 24 08          	mov    %ebx,0x8(%esp) ;z(func4)=ebx
 8048da4:	83 c1 01             	add    $0x1,%ecx ;ecx++
 8048da7:	89 4c 24 04          	mov    %ecx,0x4(%esp) ;y(func4)=ecx
 8048dab:	89 14 24             	mov    %edx,(%esp) ;x(func4)=edx=x
 8048dae:	e8 a9 ff ff ff       	call   8048d5c <func4> ;recursive call
 8048db3:	8d 44 00 01          	lea    0x1(%eax,%eax,1),%eax ;eax=2*eax+1, return value
 8048db7:	83 c4 14             	add    $0x14,%esp ;restore stack pointer
 8048dba:	5b                   	pop    %ebx ;restore registers
 8048dbb:	5e                   	pop    %esi
 8048dbc:	c3                   	ret    

首先得把func4的代码分析一遍,顺便写点注释,走一步看一步,把每一步要干什么先弄明白。0x8048d73处取符号位加上去的操作是一个偏置,为了让算术右移1位和除以2的行为一致,可以阅读CSAPP原书来了解。光看汇编来分析整体行为有一定的难度,我们不妨试着把它“意译”成C代码。(感谢 @404NotFound 的提醒,第10行条件应为a==x

int func4(int x, int y, int z)
{
    int a = (y + z) / 2, ret;
    if (a > x)
    {
        a--;
        ret = func4(x, y, a);
        return 2 * ret;
    }
    if (a == x)
    {
        return 0;
    }
    a++;
    ret = func4(x, a, z);
    return ret * 2 + 1;
}

可以代入a的各个情况,自行跑一跑这个函数,记录返回0的情况,很容易跑出来所有答案。

Phase 4解决

Phase 5

关键词:不同长度的MOV指令

这道题比较抽象,难度不仅仅在汇编上。

 8048e25:	53                   	push   %ebx
 8048e26:	83 ec 28             	sub    $0x28,%esp
 8048e29:	8b 5c 24 30          	mov    0x30(%esp),%ebx
 8048e2d:	65 a1 14 00 00 00    	mov    %gs:0x14,%eax
 8048e33:	89 44 24 1c          	mov    %eax,0x1c(%esp)
 8048e37:	31 c0                	xor    %eax,%eax
 8048e39:	89 1c 24             	mov    %ebx,(%esp)
 8048e3c:	e8 8a 02 00 00       	call   80490cb <string_length>
 8048e41:	83 f8 06             	cmp    $0x6,%eax
 8048e44:	74 4c                	je     8048e92 <phase_5+0x6d>
 8048e46:	e8 aa 03 00 00       	call   80491f5 <explode_bomb>
 8048e4b:	90                   	nop
 8048e4c:	8d 74 26 00          	lea    0x0(%esi,%eiz,1),%esi

这一段的主要作用就是检查了输入字符串的长度,限制了长度为6。有几处代码不太好理解:%gs:似乎保证了栈的完整性(见 此处);异或自身是比较快的将寄存器置0的方式(见 此处);而0x8048e4c处的指令,其实是又一个nop(见 此处)。此外,我们设*a = 0x14 + eax,这段代码还令a=0x14=20, ebx=esp+0x30。

 8048e52:	0f b6 14 03          	movzbl (%ebx,%eax,1),%edx
 8048e56:	83 e2 0f             	and    $0xf,%edx
 8048e59:	0f b6 92 90 a2 04 08 	movzbl 0x804a290(%edx),%edx
 8048e60:	88 54 04 15          	mov    %dl,0x15(%esp,%eax,1)
 8048e64:	83 c0 01             	add    $0x1,%eax
 8048e67:	83 f8 06             	cmp    $0x6,%eax
 8048e6a:	75 e6                	jne    8048e52 <phase_5+0x2d>

一个jmp指令带我们到了0x8048e92,粗看一眼结构像个循环。给eax赋初值0之后,就又跳到了0x8048e52。循环内的部分就是如上所示。在这里,eax从0到6的每一次循环中:

  • 将ebx+eax处的字符截取低4位,存入edx
  • edx作为索引,在0x804a290+edx处取1个字节
  • 将这个字节存到esp+0x15+eax

自然会想到取0x804a290中的内容,是”maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?”,因为索引只有4位,所以有效的只有“So”前面的部分。可以看出,经过这个循环,在0x15+esp处形成了另一个长度为6的字符串。

 8048e6c:	c6 44 24 1b 00       	movb   $0x0,0x1b(%esp)
 8048e71:	c7 44 24 04 67 a2 04 	movl   $0x804a267,0x4(%esp)
 8048e78:	08 
 8048e79:	8d 44 24 15          	lea    0x15(%esp),%eax
 8048e7d:	89 04 24             	mov    %eax,(%esp)
 8048e80:	e8 65 02 00 00       	call   80490ea <strings_not_equal>
 8048e85:	85 c0                	test   %eax,%eax
 8048e87:	74 10                	je     8048e99 <phase_5+0x74>

循环之后,call了一个strings_not_equal,显然其中一个参数是我们刚刚形成的字符串,另一个在0x804a257。读取它,结果是”bruins”。不算结束符号,正好六个字符。如果两个字符串相等的话,炸弹就可以解除了。我们所要做的,就是反推六个索引字符。每个字符只需要结尾四位符合索引值、属于可打印的值就可以了,所以可以有多种答案,比如“-&#$(‘”。

上面的流程,可以用一张图表示:

图解

好了,又解决一道题。

Phase 5解决

Phase 6

关键词:链表

本Phase核心部分跳来跳去的,巨难。第一部分是熟悉的读6个数字,设*a=0x10+esp,这里就不再赘述了。

 8048eca:	be 00 00 00 00       	mov    $0x0,%esi ;set esi as i, i=0
 8048ecf:	8b 44 b4 10          	mov    0x10(%esp,%esi,4),%eax ;eax = a[i]
 8048ed3:	83 e8 01             	sub    $0x1,%eax ;eax = a[i] - 1
 8048ed6:	83 f8 05             	cmp    $0x5,%eax ;compare eax with 5
 8048ed9:	76 05                	jbe    8048ee0 <phase_6+0x2f> ;if a[i] <= 5, dont explode
 8048edb:	e8 15 03 00 00       	call   80491f5 <explode_bomb>
 8048ee0:	83 c6 01             	add    $0x1,%esi ;i++
 8048ee3:	83 fe 06             	cmp    $0x6,%esi ;if i < 6, jump to 8048eef
 8048ee6:	75 07                	jne    8048eef <phase_6+0x3e>
 8048ee8:	bb 00 00 00 00       	mov    $0x0,%ebx
 8048eed:	eb 38                	jmp    8048f27 <phase_6+0x76>
 8048eef:	89 f3                	mov    %esi,%ebx ;ebx=j=i
 8048ef1:	8b 44 9c 10          	mov    0x10(%esp,%ebx,4),%eax ;eax = a[j]
 8048ef5:	39 44 b4 0c          	cmp    %eax,0xc(%esp,%esi,4) ;compare a[i-1] and a[j]
 8048ef9:	75 05                	jne    8048f00 <phase_6+0x4f> ;if a[i-1] == a[j], explode
 8048efb:	e8 f5 02 00 00       	call   80491f5 <explode_bomb>
 8048f00:	83 c3 01             	add    $0x1,%ebx ;j++
 8048f03:	83 fb 05             	cmp    $0x5,%ebx ;if j<=5, jump to 8048ef1
 8048f06:	7e e9                	jle    8048ef1 <phase_6+0x40>
 8048f08:	eb c5                	jmp    8048ecf <phase_6+0x1e> ;jump to next i of outer loop

上面是第二部分,代码里写了注释,包含了我对此代码的初步分析。观察可得,esi 和 ebx 是两个循环变量,对于每个esi,ebx 都要变一个来回,这证明了实际上是两层循环,esi设为i,是外层循环的循环变量,ebx设为j,是内层循环的循环变量。用C表示可能会好懂些:

for (int i = 0; i < 6;)
{
    if ((a[i] - 1 > 5 || a[i] - 1 < 0) && a[i] != 0)
    {
        explode_bomb();
    }
    i++;
    for (int j = i; j <= 5; j++)
    {
        if (a[i - 1] == a[j])
        {
            explode_bomb();
        }
    }
}

简单来说,就是保证了数组a中值均小于等于6,且两两不相等。或者说,是1-6的一个排列(减1正是为了去除0的情况)。循环完成后,跳转到0x8048f27,进入第三部分。从这里开始就变得十分抽象了,但暂时没有懂的话不用急,会懂的。

 8048f27:	89 de                	mov    %ebx,%esi
 8048f29:	8b 4c 9c 10          	mov    0x10(%esp,%ebx,4),%ecx
 8048f2d:	83 f9 01             	cmp    $0x1,%ecx
 8048f30:	7e e4                	jle    8048f16 <phase_6+0x65>
 8048f32:	b8 01 00 00 00       	mov    $0x1,%eax
 8048f37:	ba 3c c1 04 08       	mov    $0x804c13c,%edx
 8048f3c:	eb cc                	jmp    8048f0a <phase_6+0x59>

在这段代码运行之前,在0x8048eed处,ebx 已经被归零了,这里大胆猜测它是一个索引变量,这里将其设为k。而按照这个来推断的话,ecx 首先被赋值a[k]。然后分了ecx是否小于等于1的情况(没有0,相当于是否等于1),如果不是,先给eax赋1,再将edx赋一个像是地址的立即数。eax 可能是另一个索引变量,这里设为l。这里先来看 ecx=1的情况。

 8048f16:	ba 3c c1 04 08       	mov    $0x804c13c,%edx
 8048f1b:	89 54 b4 28          	mov    %edx,0x28(%esp,%esi,4)
 8048f1f:	83 c3 01             	add    $0x1,%ebx
 8048f22:	83 fb 06             	cmp    $0x6,%ebx
 8048f25:	74 17                	je     8048f3e <phase_6+0x8d>

将1单独拎出来,或许和单独构建之后的数依赖的某种头有关。这里也将刚刚遇见过的一个立即数赋给了edx,那么不得不对其产生怀疑,那就用GDB进行一个内存的读。

读取edx即0x804c13c处的结果

比较难想到的一点是,你直接读取0x804c13c处的一个word,是读不到什么有用的信息的,但也不是完全无迹可寻。首先引人注意的是这个变量的名字”node1″,让人不由得考虑链表的结构:如果能够依据此扩展显示的范围,向上图一样多显示几个word,就能够发现端倪。这样很容易能够推断出node的结构:4个字节的内容,4个字节的序号,4个字节的下一节点地址。接着往下读,发现node从1到6,可能对应了刚刚我们输入的六个值。即使不一次读3个也没关系,也能够观察到node标签。

很巧的是,8048f1b处的基址0x28,正好和a数组基址0x10差了24个字节,也就是6个双字变量。那么上面的汇编代码所要做的事情,就是将编号为1的节点地址存储到a数组之后。之后将ebx也就是k自增1,如果等于6则跳出这个循环,否则直接fallthrough。按理说,单单是a[k]=1的情况不需要又是自增又是判断。那么,如果不为1呢?

 8048f32:	b8 01 00 00 00       	mov    $0x1,%eax
 8048f37:	ba 3c c1 04 08       	mov    $0x804c13c,%edx
 8048f3c:	eb cc                	jmp    8048f0a <phase_6+0x59> 

 8048f0a:	8b 52 08             	mov    0x8(%edx),%edx
 8048f0d:	83 c0 01             	add    $0x1,%eax
 8048f10:	39 c8                	cmp    %ecx,%eax
 8048f12:	75 f6                	jne    8048f0a <phase_6+0x59>
 8048f14:	eb 05                	jmp    8048f1b <phase_6+0x6a>

我在这里拼接了两段汇编代码,它们原本并不是连续的。现在edx寄存器保存了刚刚链表的首节点地址,而0x8048f0a处的指令,是将edx+8中的内容赋给edx。再次联想到刚刚所说的节点结构,每个节点地址+8位置的变量正是保存了下一个节点地址,这相当于C语言中的p = p -> next。然后将eax即l自增1,直到l = a [k]。那么C语言代码大概是这样:

do
{
    p = p->next;
    l++;
} while (l != a[i]);
asm("jmp 0x8048f1b");

接下来跳转到0x8048f1b,这也是刚刚a[k]=1的情况中,越过赋初值的语句处。

 8048f1b:	89 54 b4 28          	mov    %edx,0x28(%esp,%esi,4)
 8048f1f:	83 c3 01             	add    $0x1,%ebx
 8048f22:	83 fb 06             	cmp    $0x6,%ebx
 8048f25:	74 17                	je     8048f3e <phase_6+0x8d>

这块代码的行为应该不需要过多解释了,两部分结合来看,所做的事情就是将第a[k]个节点的地址,填入esp+0x28这个数组(设置为n)中的第k个位置。连起来,翻译成C语言:

int l;
node *head = 0x804c13c, *p, *n[6];
for (int k = 0; k < 6; i++)
{
    if (a[k] == 1)
    {
        n[k] = head;
    }
    else
    {
        p = head;
        l = 1;
        do
        {
            p = p->next;
            l++;
        } while (l != a[k]);
        n[k] = p;
    }
}

从0x8048f3e开始,到0x8048f5a,是第四部分。

 8048f3e:	8b 5c 24 28          	mov    0x28(%esp),%ebx
 8048f42:	8d 44 24 2c          	lea    0x2c(%esp),%eax
 8048f46:	8d 74 24 40          	lea    0x40(%esp),%esi
 8048f4a:	89 d9                	mov    %ebx,%ecx
 8048f4c:	8b 10                	mov    (%eax),%edx
 8048f4e:	89 51 08             	mov    %edx,0x8(%ecx)
 8048f51:	83 c0 04             	add    $0x4,%eax
 8048f54:	39 f0                	cmp    %esi,%eax
 8048f56:	74 04                	je     8048f5c <phase_6+0xab>
 8048f58:	89 d1                	mov    %edx,%ecx
 8048f5a:	eb f0                	jmp    8048f4c <phase_6+0x9b>
 8048f5c:	c7 42 08 00 00 00 00 	movl   $0x0,0x8(%edx)

这一段的主要作用是将各节点按照在n中的顺序重新连起来,并将尾节点next设为null。它遍历了p中5对相邻两节点的组合,并对每个组合,将前一个节点连到后一个节点上,而它的关键就在0x8049f4e:将后一个节点的地址写入到前一个节点的next部分。对这一段要整体去把握,如果尝试理解每一句的意思是很有困难的。

 8048f63:	be 05 00 00 00       	mov    $0x5,%esi
 8048f68:	8b 43 08             	mov    0x8(%ebx),%eax
 8048f6b:	8b 00                	mov    (%eax),%eax
 8048f6d:	39 03                	cmp    %eax,(%ebx)
 8048f6f:	7d 05                	jge    8048f76 <phase_6+0xc5>
 8048f71:	e8 7f 02 00 00       	call   80491f5 <explode_bomb>
 8048f76:	8b 5b 08             	mov    0x8(%ebx),%ebx
 8048f79:	83 ee 01             	sub    $0x1,%esi
 8048f7c:	75 ea                	jne    8048f68 <phase_6+0xb7>

进入第五部分,这一部分干的事情是将上面提到的5个组合反向遍历一遍,并要求前一个节点的值大于等于后一个,即要求最后链表的值是降序排列的。 现在题目的条件就完全显露出来了,我们可以根据节点的值来确定输入六个数的顺序。按原顺序(重新连接之前),可以得出:

十六进制值0x12d0x360x2470x3e60x27c0xd0
十进制值30154583998636208
链表数字转换

第一个当然要选择最大的,就是998,对应4;第二个是636,对应5……这样推出答案,就是4 5 3 1 6 2。

Phase 6解决

Secret Phase

关键词:二叉搜索树

bomb.c中,作者已经暗示了一个missing的secret phase的存在。但是第六个phase完成后,程序会自动退出,所以我们首先需要另辟蹊径,找一个能够call出secret phase的地方,而它就在phase_defused中。

在每次phase结束之后,都会调用一次phase_defused。而它的反汇编代码中,有很多跳转语句可能直接跳过secret phase的调用过程。那么直接先分析它的反汇编代码。

 8049366:	81 ec 8c 00 00 00    	sub    $0x8c,%esp
 804936c:	65 a1 14 00 00 00    	mov    %gs:0x14,%eax
 8049372:	89 44 24 7c          	mov    %eax,0x7c(%esp)
 8049376:	31 c0                	xor    %eax,%eax
 8049378:	83 3d c8 c3 04 08 06 	cmpl   $0x6,0x804c3c8
 804937f:	75 72                	jne    80493f3 <phase_defused+0x8d>

这是第一个可能跳过的地方。它将0x804c3c8指向的内容和0x6相比,查到在这之外有read_lineskip调用了这个地址,但我懒得分析,于是在0x8049378处打断点,在每次运行到此处的时候观察它的值(可以用GDB的display功能)。结果是十分巧合的,每解开一个phase,这个变量都会+1。

0x804c3c8的内容

而这个变量的label正好叫num_input_string,代表已经输入的字符串数量,再结合下一行代码来看,如果没有输够六个,就直接跳过去。也就是说,只有在第六个phase之后,才有机会进入secret phase。

 8049381:	8d 44 24 2c          	lea    0x2c(%esp),%eax
 8049385:	89 44 24 10          	mov    %eax,0x10(%esp)
 8049389:	8d 44 24 28          	lea    0x28(%esp),%eax
 804938d:	89 44 24 0c          	mov    %eax,0xc(%esp)
 8049391:	8d 44 24 24          	lea    0x24(%esp),%eax
 8049395:	89 44 24 08          	mov    %eax,0x8(%esp)
 8049399:	c7 44 24 04 09 a4 04 	movl   $0x804a409,0x4(%esp)
 80493a0:	08 
 80493a1:	c7 04 24 d0 c4 04 08 	movl   $0x804c4d0,(%esp)
 80493a8:	e8 b3 f4 ff ff       	call   8048860 <__isoc99_sscanf@plt>
 80493ad:	83 f8 03             	cmp    $0x3,%eax
 80493b0:	75 35                	jne    80493e7 <phase_defused+0x81>

这是第二个可能跳过的地方。我们先前已经熟悉了sscanf的参数设定,这次使用GDB读取0x804a409的字符串,得到”%d %d %s”,这意味着我们需要输入两个数和一个字符串。跳过的条件是少于三个参数。

这里奇怪的是,为什么在没有输入的情况下,仍然有0x804c4d0作为源字符串?在运行到此处时读取它,发现在使用原正确答案输入的时候,读取到的是”0 0″,恰巧和Phase 4的正解之一相同。为了进一步验证这一想法,可以尝试将第四题的所有正解代入,比对输入的正解和读取到的字符串,此处不再详述。结果是确实相同。

再想到Phase 4也使用了sscanf,多余的参数并不会影响识别,所以第四题必须多输入一个字符串。

 80493b2:	c7 44 24 04 12 a4 04 	movl   $0x804a412,0x4(%esp)
 80493b9:	08 
 80493ba:	8d 44 24 2c          	lea    0x2c(%esp),%eax
 80493be:	89 04 24             	mov    %eax,(%esp)
 80493c1:	e8 24 fd ff ff       	call   80490ea <strings_not_equal>
 80493c6:	85 c0                	test   %eax,%eax
 80493c8:	75 1d                	jne    80493e7 <phase_defused+0x81>

这一段将0x804a412指向的字符串(读取得”DrEvil”)与0x2c+esp处的字符串(即刚刚多输入的那个)相比,如果不相等则跳过。

现在进入Secret Phase的条件就很清楚了:在第四题的答案后加入一串”DrEvil”。按要求输入后,果然弹出了几行文字提示,进入了传说中的Secret Phase。下面是它的部分反汇编代码:

 8048fd9:	e8 8e 02 00 00       	call   804926c <read_line>
 8048fde:	c7 44 24 08 0a 00 00 	movl   $0xa,0x8(%esp)
 8048fe5:	00 
 8048fe6:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
 8048fed:	00 
 8048fee:	89 04 24             	mov    %eax,(%esp)
 8048ff1:	e8 da f8 ff ff       	call   80488d0 <strtol@plt>

首先调用了一个read_line,读取一行字符串。然后构建了strtol的三个参数,分别是刚刚输入的字符串、0和10。在Shell中输入man strtol 来查看文档,内容如下。

strtol手册内容

可以看到这个函数的功能是将一个字符串转换为长整型。第一个参数是字符串的起始地址;第二个参数是结束地址,这里传入一个0代表NULL;第三个参数则是进制,这里为10。返回值是转换结果。

那么这一整串代码的作用,就是输入一个整数。

 8048ff6:	89 c3                	mov    %eax,%ebx
 8048ff8:	8d 40 ff             	lea    -0x1(%eax),%eax
 8048ffb:	3d e8 03 00 00       	cmp    $0x3e8,%eax
 8049000:	76 05                	jbe    8049007 <secret_phase+0x32>

这部分代码的作用是限制读取的整数在$[1,1001]$范围内,减一是为了去除0。

 8049007:	89 5c 24 04          	mov    %ebx,0x4(%esp)
 804900b:	c7 04 24 88 c0 04 08 	movl   $0x804c088,(%esp)
 8049012:	e8 6d ff ff ff       	call   8048f84 <fun7>
 8049017:	83 f8 05             	cmp    $0x5,%eax
 804901a:	74 05                	je     8049021 <secret_phase+0x4c>

这部分调用了fun7,参数分别是像一个地址的立即数和刚刚输入的数。如果返回值为5,则成功解决Secret Phase。

下面是fun7的部分反汇编代码。

 8048f88:	8b 54 24 20          	mov    0x20(%esp),%edx
 8048f8c:	8b 4c 24 24          	mov    0x24(%esp),%ecx
 8048f90:	85 d2                	test   %edx,%edx
 8048f92:	74 37                	je     8048fcb <fun7+0x47>

首先很容易看出来fun7一开始是检查edx是否为0,但暂时不知道那两个mov是什么意思。瞥一眼后面的代码,发现edx后面的地址多次作为参数被递归调用,于是决定看一眼edx。

edx指向及后面一部分内存的内容

label后面有序号,预示着后面可能还有值的存在,将预览范围扩展到下一个label出现前,发现排列有一定的规律。这一块内存似乎表示了一个三元组,由值和两个地址构成,符合一个二叉树节点的形式。按照这个形式把它组织起来,如下图。节点并不是按顺序组织的,写的时候对每个节点只写其值和左右字节点的地址,会更方便。

画出的二叉树

我们惊奇地发现这是一棵二叉搜索树,而且是十分平衡的AVL树,刚刚筛选范围在$[1,1001]$的目的,正是保证输入的值有位置可放。GDB读到的label符合一个$nxy$的格式,$x$代表层数(从1开始),$y$代表从左开始数的序号,如$n46$正好是第四行第六个节点。传入fun7的第一个参数是AVL树的当前节点地址(而从secret_phase调用时是根节点地址),第二个参数是我们输入的数,分别放置在edx和ecx中,设为node *pint num。test指令的目的是检查当前节点是否存在(如果不存在则地址为0,相当于NULL),不存在则返回-1。

 8048f94:	8b 1a                	mov    (%edx),%ebx
 8048f96:	39 cb                	cmp    %ecx,%ebx
 8048f98:	7e 13                	jle    8048fad <fun7+0x29>

这段代码比较了nump->val,如果前者不小于后者,则跳转。首先来看num < p->val的情况。

 8048f9a:	89 4c 24 04          	mov    %ecx,0x4(%esp)
 8048f9e:	8b 42 04             	mov    0x4(%edx),%eax
 8048fa1:	89 04 24             	mov    %eax,(%esp)
 8048fa4:	e8 db ff ff ff       	call   8048f84 <fun7>
 8048fa9:	01 c0                	add    %eax,%eax
 8048fab:	eb 23                	jmp    8048fd0 <fun7+0x4c>

这部分调用了fun7(p->left, num),然后把返回值乘以2再返回。

 8048fad:	b8 00 00 00 00       	mov    $0x0,%eax
 8048fb2:	39 cb                	cmp    %ecx,%ebx
 8048fb4:	74 1a                	je     8048fd0 <fun7+0x4c>

继续比较nump->val,如果相等,返回0。那么剩下的就是num > p->val的情况。

 8048fb6:	89 4c 24 04          	mov    %ecx,0x4(%esp)
 8048fba:	8b 42 08             	mov    0x8(%edx),%eax
 8048fbd:	89 04 24             	mov    %eax,(%esp)
 8048fc0:	e8 bf ff ff ff       	call   8048f84 <fun7>
 8048fc5:	8d 44 00 01          	lea    0x1(%eax,%eax,1),%eax
 8048fc9:	eb 05                	jmp    8048fd0 <fun7+0x4c>

调用func7(p->right, num),然后把返回值乘2加1再返回。

可以看到,func7所做的就是“搜索”的操作,我们所期望的返回值5就是根据输入数和节点的关系,通过一层一层递归中的运算构建出来的。借此,我们可以反推num在树中的位置。

首先num肯定存在于树中,因为如果不存在,必会返回-1,无法通过计算得到。很容易能够得到唯一解:$5=((0 \times 2+1) \times 2) \times 2+1$,也就是从根节点出发,路径为右、左、右,得出输入的值为0x2f,即47。

在对应的位置输入47(我这里直接暴力改寄存器和内存了),Secret Phase也就被解决了。

Secret Phase解决

如果你看到这里的话,那我大概可以祝贺你成功解开了Bomb Lab。如果给予足够的时间,Bomb Lab是可以带来很多乐趣的,可以说是一个非常巧妙的实验。从一片汇编代码中挖出数据结构再到理清逻辑,是非常有成就感的事情。如果你想对Bomb Lab有更多的研究,可以查看下面的GitHub仓库,里面疑似是Bomb Lab的指导者源码,用于生成炸弹。但如果你还没做完,建议不要进入查看,毕竟正推就没什么意思了,你说呢?

评论

  1. 404NotFound
    Windows Chrome 100.0.4896.88
    8月前
    2022-4-16 0:42:37

    第四关递归函数的第十行应该是 a == x 叭?(

    • 博主
      404NotFound
      Linux Firefox 99.0
      8月前
      2022-4-16 8:50:44

      感谢提醒,已更正。

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇