当前位置 博文首页 > 周小伦:超精讲-逐例分析CS:APP-LAB2-Bomb!(上)

    周小伦:超精讲-逐例分析CS:APP-LAB2-Bomb!(上)

    作者:周小伦 时间:2021-01-30 18:24

    0. 环境要求

    关于环境已经在lab1里配置过了这里要记得安装gdb

    安装命令 sudo yum install gdb

    实验的下载地址 http://csapp.cs.cmu.edu/3e/labs.html

    gbd的命令地址 http://csapp.cs.cmu.edu/2e/docs/gdbnotes-x86-64.pdf

    知乎同款连接 https://zhuanlan.zhihu.com/p/339461318

    这里我们需要使用objdump -d ./bomb >> bomb.s反汇编工具来得到汇编代码。

    下面就开始举世盛名bomb 实验吧

    1. 第一关

    1. 粗读 main 函数

        initialize_bomb();
      
         printf("Welcome to my fiendish little bomb. You have 6 phases with\n");
         printf("which to blow yourself up. Have a nice day!\n");
          /* Hmm...  Six phases must be more secure than one phase! */
         input = read_line();             /* Get input                   */
         phase_1(input);                  /* Run the phase               */
         phase_defused();                 /* Drat!  They figured it out!
      

      通过简单的阅读理解应该知道这里面的phase_1 就是我们的第一关了,然后根据函数名称 input = read_line() 应该是要验证我们的输入是否合理,我们先乱输入一个看看先运行起来

      (gdb) r
      Starting program: /csapp/bomb/bomb 
      warning: Error disabling address space randomization: Operation not permitted
      Welcome to my fiendish little bomb. You have 6 phases with
      which to blow yourself up. Have a nice day!
      

      输入hello wordl

      hello world
      BOOM!!!
      The bomb has blown up.
      [Inferior 1 (process 67) exited with code 010]
      

      果然??了下面开始分析我们的汇编代码来尝试得到结果

    2. 阅读bomb.s 理清思路

      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   
      

      这个逻辑应该是很简单的不熟悉汇编代码的同学可以参考一下csapp原书的第三章

      • 1 行分配栈帧

      • 2 行把立即数0x402400 放到寄存器esi中那我们知道这是用来第二个参数的寄存器

      • 3-4 行 调用 strings_not_equal 函数然后判断返回值是否为0,如果是0就跳到400ef7然后恢复栈帧结束否则就调用explode_bomb引爆炸弹所以核心就在于strings_not_equal函数

    3. 阅读strings_not_equal 函数

      emm 这个函数太长就只放重点了 我们重点关注esi寄存器因为上面我们传递了一个参数

       40133f:	48 89 f5             	mov    %rsi,%rbp
       40134a:	48 89 ef             	mov    %rbp,%rdi
       40134d:	e8 c9 ff ff ff       	callq  40131b <string_length> 
       40135c:	0f b6 03             	movzbl (%rbx),%eax
       401363:	3a 45 00             	cmp    0x0(%rbp),%al
      

      这里我们可以发现他把m[rbx]->eax 然后比较m[rbp]al寄存器里面的值(也就是%eax里面的值)

      这就是说我们需要比较的就是在0x402400位置处的字符串和题目预定输入的字符串是否相同,中间有很多判断字符串长度是否相同的代码请大家自行阅读吧。所以我们可以查看0x402400位置的值然后直接输入这个结果就好

      (gdb) x/s 0x402400
      0x402400:	"Border relations with Canada have never been better."
      
      

      我们输入Border relations with Canada have never been better.就可以拆掉第一个炸弹

    2. 第二关

    首先还是差不多的代码逻辑对于输入进行判断,合格就可以通过

        input = read_line();
        phase_2(input);
        phase_defused();
        printf("That's number 2.  Keep going!\n");
    
    1. 慢读phase_2的汇编代码
      400efe:	48 83 ec 28          	sub    $0x28,%rsp
      400f02:	48 89 e6             	mov    %rsp,%rsi
      400f05:	e8 52 05 00 00       	callq  40145c <read_six_numbers>
      400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
    
    • 分配大小为40字节的栈帧然后把栈帧指针传递给%rsi寄存器接下来调用read_six_numbers
    1. 转入read_six_numbers函数
    000000000040145c <read_six_numbers>:
      40145c:	48 83 ec 18          	sub    $0x18,%rsp
      401460:	48 89 f2             	mov    %rsi,%rdx
      401463:	48 8d 4e 04          	lea    0x4(%rsi),%rcx
      401467:	48 8d 46 14          	lea    0x14(%rsi),%rax
      40146b:	48 89 44 24 08       	mov    %rax,0x8(%rsp)
      401470:	48 8d 46 10          	lea    0x10(%rsi),%rax
      401474:	48 89 04 24          	mov    %rax,(%rsp)
      401478:	4c 8d 4e 0c          	lea    0xc(%rsi),%r9
      40147c:	4c 8d 46 08          	lea    0x8(%rsi),%r8
      401480:	be c3 25 40 00       	mov    $0x4025c3,%esi
      401485:	b8 00 00 00 00       	mov    $0x0,%eax
      40148a:	e8 61 f7 ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
      40148f:	83 f8 05             	cmp    $0x5,%eax
      401492:	7f 05                	jg     401499 <read_six_numbers+0x3d>
      401494:	e8 a1 ff ff ff       	callq  40143a <explode_bomb>
      401499:	48 83 c4 18          	add    $0x18,%rsp
      40149d:	c3                   	retq   
    

    简单分析一下这个汇编代码这个需要我们输入6个数字然后进行比较这里还有如果数字不满足6个的健壮性判断

    下面按顺序构建sscanf所需要的参数

    首先我们分析一下sscanf函数

    (gdb) x/s 0x4025c3
    0x4025c3: "%d %d %d %d %d %d"

    我们发现sscanf函数所需要的第二个参数居然是这样的格式这就表示我们会依次把六个数读入到他所传递的3-8个参数里面我们知道3-6个参数可以用寄存器传递剩下的两个参数则要利用栈帧来传递

    • %rsi 存储在phase_2里面传入的%rsp的值也就是栈帧的起始地址

      我们查看%esi的值发现居然是这样那么就表示我们的sscanf函数需要的是

    • %rdx,由%rsi给出,%rsi又由phrase_2%rsp给出,所以phrase2中的%rsp地址处存放sscanf中第一个输入的值

    • %rcx也就是在phase_2%rsp+0x4中存放着第二个值

    • %r8也就是在phase_2%rsp+0x8中存放着第三个值

    • %r9也就是在phase_2%rsp+0xc中存放着第四个值

    • 在该函数的%rsp 中存放着第五个值也就是我们把0x10(%rsi),%rax放进了rsp

    • 在该函数的%rsp+0x8 中存放着第六个值也就是我们把0x14(%rsi),%rax放进了rsp

    上面就是对所有值的分析下面我们来依次分析这些值

    上面的描述会比较乱,这里用一个非常丑的图来表示这个参数的构造过程1st表示第一个参数依次类推。
    3. 回到phase_2

      400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
      400f0e:	74 20                	je     400f30 <phase_2+0x34>
      400f10:	e8 25 05 00 00       	callq  40143a <explode_bomb>
      400f15:	eb 19                	jmp    400f30 <phase_2+0x34>
      400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
      400f1a:	01 c0                	add    %eax,%eax
      400f1c:	39 03                	cmp    %eax,(%rbx)
      400f1e:	74 05                	je     400f25 <phase_2+0x29>
      400f20:	e8 15 05 00 00       	callq  40143a <explode_bomb>
      400f25:	48 83 c3 04          	add    $0x4,%rbx
      400f29:	48 39 eb             	cmp    %rbp,%rbx
      400f2c:	75 e9                	jne    400f17 <phase_2+0x1b>
      400f2e:	eb 0c                	jmp    400f3c <phase_2+0x40>
      400f30:	48 8d 5c 24 04       	lea    0x4(%rsp),%rbx
      400f35:	48 8d 6c 24 18       	lea    0x18(%rsp),%rbp
      400f3a:	eb db                	jmp    400f17 <phase_2+0x1b>
      400f3c:	48 83 c4 28          	add    $0x28,%rsp
      400f40:	5b                   	pop    %rbx
      400f41:	5d                   	pop    %rbp
      400f42:	c3                   	retq   
    
    • (rsp) 这里有一个和1的比较可以发现这里必须等于1不然直接引爆炸弹了所以第一个值就是1

    • (%rsp+0x4)

       400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
       400f1a:	01 c0                	add    %eax,%eax
       400f1c:	39 03                	cmp    %eax,(%rbx)
      

      这三行就是关键代码因为我们在跳转之后把rsp+0x4赋给了rbp 那上述代码的前两行就是把rsp里的值翻倍然后放到rsp+0x4 也就是第二个参数是2

    剩下的过程就可以循环了六个数分别应该是1,2,4,8,16,32

    Phase 1 defused. How about the next one?
    1 2 4 8 16 32
    That's number 2.  Keep going!
    

    3. 第三关

    好家伙我倒要看看complex code 有多复杂逻辑 首先还是一样都是判断输入是否合法

        /* I guess this is too easy so far.  Some more complex code will
         * confuse people. */
        input = read_line();
        phase_3(input);
        phase_defused();
        printf("Halfway there!\n");
    
    

    1. 阅读phase_3

     400f43:	48 83 ec 18          	sub    $0x18,%rsp
     400f47:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
     400f4c:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
     400f51:	be cf 25 40 00       	mov    $0x4025cf,%esi
     400f56:	b8 00 00 00 00       	mov    $0x0,%eax
     400f5b:	e8 90 fc ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
     400f60:	83 f8 01             	cmp    $0x1,%eax
     400f63:	7f 05                	jg     400f6a <phase_3+0x27>
    
    • 分配栈帧

    • 利用%rdx 也就是0x8+%rsp和利用%rcx 也就是0xc+%rsp传递sscanf函数用的第三和第四个参数

    • 第二个参数为一个常数0x4025cf随后调用<__isoc99_sscanf@plt> 这里注意一下sscanf如果调用成功的话会返回2这里如果成功的话会跳转到400f6a这里读入的rdxrcx的值就是我们输入的第一个和第二个数

    2. 继续阅读phase_3

      400f6a:	83 7c 24 08 07       	cmpl   $0x7,0x8(%rsp)
      400f6f:	77 3c                	ja     400fad <phase_3+0x6a>
      400f71:	8b 44 24 08          	mov    0x8(%rsp),%eax
      400f75:	ff 24 c5 70 24 40 00 	jmpq   *0x402470(,%rax,8)
      400f7c:	b8 cf 00 00 00       	mov    $0xcf,%eax
      400f81:	eb 3b                	jmp    400fbe <phase_3+0x7b>
      400f83:	b8 c3 02 00 00       	mov    $0x2c3,%eax
      400f88:	eb 34                	jmp    400fbe <phase_3+0x7b>
      400f8a:	b8 00 01 00 00       	mov    $0x100,%eax
      400f8f:	eb 2d                	jmp    400fbe <phase_3+0x7b>
      400f91:	b8 85 01 00 00       	mov    $0x185,%eax
      400f96:	eb 26                	jmp    400fbe <phase_3+0x7b>
      400f98:	b8 ce 00 00 00       	mov    $0xce,%eax
      400f9d:	eb 1f                	jmp    400fbe <phase_3+0x7b>
      400f9f:	b8 aa 02 00 00       	mov    $0x2aa,%eax
      400fa4:	eb 18                	jmp    400fbe <phase_3+0x7b>
      400fa6:	b8 47 01 00 00       	mov    $0x147,%eax
      400fab:	eb 11                	jmp    400fbe <phase_3+0x7b>
      400fad:	e8 88 04 00 00       	callq  40143a <explode_bomb>
      400fb2:	b8 00 00 00 00       	mov    $0x0,%eax
      400fb7:	eb 05                	jmp    400fbe <phase_3+0x7b>
      400fb9:	b8 37 01 00 00       	mov    $0x137,%eax
      400fbe:	3b 44 24 0c          	cmp    0xc(%rsp),%eax
      400fc2:	74 05                	je     400fc9 <phase_3+0x86>
      400fc4:	e8 71 04 00 00       	callq  40143a <explode_bomb>
      400fc9:	48 83 c4 18          	add    $0x18,%rsp
      400fcd:	c3                   	retq   
    
    1. %rdx里的值必须小于等于7否则直接爆炸然后关键来了我们把第一个输入的值传给%eax然后在就是一步关键操作

    2. 我们要跳转到m[0x402470+r[%rax]*8]这里我们以传入的第一个参数也就是%rdx的值为0为例子那我要跳转的地址就是m[0x402470] check 一下这里面是什么值

      (gdb) x/x 0x402470
      0x402470:	0x00400f7c
      

      可以发现我们接下来要跳到0x400f7c这里去

    3. 节选有关代码分析

        400f7c:	b8 cf 00 00 00       	mov    $0xcf,%eax
        400f81:	eb 3b                	jmp    400fbe <phase_3+0x7b>
        400fbe:	3b 44 24 0c          	cmp    0xc(%rsp),%eax
        400fc2:	74 05                	je     400fc9 <phase_3+0x86>
        400fc4:	e8 71 04 00 00       	callq  40143a <explode_bomb>
        400fc9:	48 83 c4 18          	add    $0x18,%rsp
      

      这里我们先把0xcf传递给%eax 然后比较0xc(%rsp)也就是我们输入的第二个参数如果和eax相等则完成这表示0 和 0xcf=207 就是一个合法答案

    0 207
    Halfway there!
    

    ? 这里注意我们的第一个参数可以任取<=7的任何数然后去查看不同的地址得到不同的跳转地址也就会有不同 的答案这里再给出一个例子如果第一个参数为1那么m[0x402470+r[%rax]*8]=m[0x402470+8]也就是我们 要去看一下m[0x402478]

    (gdb) x/x 0x402478
    0x402478:	0x00400fb9
    

    ? 这次变成了另一地址我们接着分析一下后面会发生什么事

     400fb9:	b8 37 01 00 00       	mov    $0x137,%eax
     400fbe:	3b 44 24 0c          	cmp    0xc(%rsp),%eax
     400fc2:	74 05                	je     400fc9 <phase_3+0x86>
     400fc4:	e8 71 04 00 00       	callq  40143a <explode_bomb>
     400fc9:	48 83 c4 18          	add    $0x18,%rsp
     400fcd:	c3                   	retq   
    

    ? 那这就是判断第二个参数是否等于0x137下面我们来试试1 和 311是否可以

    1 311
    Halfway there!
    

    可以发现也是可以的其他例子就不在演示了

    4. 第四关

    好家伙考察数学能力开冲

     /* Oh yeah?  Well, how good is your math?  Try on this saucy problem! */
        input = read_line();
        phase_4(input);
        phase_defused();
        printf("So you got that one.  Try this one.\n");
    

    1.读phase_4

      40100c:	48 83 ec 18          	sub    $0x18,%rsp
      401010:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
      401015:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
      40101a:	be cf 25 40 00       	mov    $0x4025cf,%esi
      40101f:	b8 00 00 00 00       	mov    $0x0,%eax
      401024:	e8 c7 fb ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
      401029:	83 f8 02             	cmp    $0x2,%eax
      40102c:	75 07                	jne    401035 <phase_4+0x29>
    

    前面的代码几乎和上面的没差,rdx存储了我们读入的第一个参数rcx存储了我们读入的第二个参数这里同样有对sscanf的判断如果不成功直接爆炸

    2.继续分析phase_4

    	40102e:	83 7c 24 08 0e       	cmpl   $0xe,0x8(%rsp)
      401033:	76 05                	jbe    40103a <phase_4+0x2e>
      401035:	e8 00 04 00 00       	callq  40143a <explode_bomb>
      40103a:	ba 0e 00 00 00       	mov    $0xe,%edx
      40103f:	be 00 00 00 00       	mov    $0x0,%esi
      401044:	8b 7c 24 08          	mov    0x8(%rsp),%edi
      401048:	e8 81 ff ff ff       	callq  400fce <func4>
      40104d:	85 c0                	test   %eax,%eax
      40104f:	75 07                	jne    401058 <phase_4+0x4c>
      401051:	83 7c 24 0c 00       	cmpl   $0x0,0xc(%rsp)
      401056:	74 05                	je     40105d <phase_4+0x51>
      401058:	e8 dd 03 00 00       	callq  40143a <explode_bomb>
      40105d:	48 83 c4 18          	add    $0x18,%rsp
      401061:	c3                   	retq 
    

    这里我们需要把m[rsp+8]=r[%rdx] 的值和0xe比较。我们设第一个输入的参数是aa > 0xe则直接爆炸。否则我们构建对调用func4的参数func4(0x8(%rsp),0,0xe) 这里的第一个参数就是我们的a注意后面的我们把0和m[0xc(%rsp)]=r[%rcx] 进行比较如果想等则退出也就表示了我们第二个参数必须为0

    3.去看func4

    对于代码的分析直接写到注释上了

    0000000000400fce <func4>:(a,0,0xe)
      400fce:	48 83 ec 08          	sub    $0x8,%rsp  //分配栈帧
      400fd2:	89 d0                	mov    %edx,%eax  // %eax=0xe
      400fd4:	29 f0                	sub    %esi,%eax  // %eax=%eax-0=0xe
      400fd6:	89 c1                	mov    %eax,%ecx  // %ecx=%eax=0xe
      400fd8:	c1 e9 1f             	shr    $0x1f,%ecx //对%ecx的值逻辑右移31位
      400fdb:	01 c8                	add    %ecx,%eax  //%eax=%eax+%ecx=0xe
      400fdd:	d1 f8                	sar    %eax       //%eax=%eax>>1=0x7
      400fdf:	8d 0c 30             	lea    (%rax,%rsi,1),%ecx //%ecx=0x7+0x0=0x7
      400fe2:	39 f9                	cmp    %edi,%ecx  //%ecx-%edi=0x7-a
      400fe4:	7e 0c                	jle    400ff2 <func4+0x24>  //if <=0 则跳转
    

    我们可以看到对于我们输入的第一个参数a 存在if a>=7 则会跳转到400ff2 我们不妨输入a=7

    下面看一下0x400ff2

     400ff2:	b8 00 00 00 00       	mov    $0x0,%eax    //返回值为0
     400ff7:	39 f9                	cmp    %edi,%ecx    //再一次比较%ecx-%edi=0x7-a 
     400ff9:	7d 0c                	jge    401007 <func4+0x39> // if a<=7 则跳出
     400ffb:	8d 71 01             	lea    0x1(%rcx),%esi  // 否则我们把%esi++重写执行
     400ffe:	e8 cb ff ff ff       	callq  400fce <func4>
     401003:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
     401007:	48 83 c4 08          	add    $0x8,%rsp
     40100b:	c3                   	retq   
    

    可以发现这是一个简单的for 循环我们直接用a=7 直接卡了这个循环的边界条件直接可以过掉本题

    非常迅速的做完了第四个嘿嘿

    7 0
    So you got that one.  Try this one.
    

    不过本着学习的目的我们还是要知道这整个递归函数都发生了什么。在网上随便找了一个版本的c语言代码来分析一下

    void func4(int x,int y,int z)  //y的初始值为0,z的初始值为14,t->%rax,k->%ecx
    {
      int t=z-y;
      int k=t>>31;
      t=(t+k)>>1;
      k=t+y;
      if(k>x)
      {
        z=k-1;
        func4(x,y,z);
        t=2t;
        return;
      }
      else
       {
         t=0;
         if(k<x)
         {
            y=k+1;
            func4(x,y,z);
            t=2*t+1;
            return;
         }
         else
         {
             return;
         }
       }
    }
    

    分析得x = k的时候,t=0,即 %eax 为 0 。然后就可以回到 phase_4 。

    bk