CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 6

时间:2021-08-10 15:12:09

phase_6的代码很长,不过很有结构,按功能划分首先来看第一段:

00000000004010f4 <phase_6>:
  4010f4:	41 56                	push   %r14
  4010f6:	41 55                	push   %r13
  4010f8:	41 54                	push   %r12
  4010fa:	55                   	push   %rbp
  4010fb:	53                   	push   %rbx
  4010fc:	48 83 ec 50          	sub    $0x50,%rsp
  401100:	49 89 e5             	mov    %rsp,%r13
  401103:	48 89 e6             	mov    %rsp,%rsi
  401106:	e8 51 03 00 00       	callq  40145c <read_six_numbers>
  40110b:	49 89 e6             	mov    %rsp,%r14
  40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d
  401114:	4c 89 ed             	mov    %r13,%rbp # the start of the outer while loop
  401117:	41 8b 45 00          	mov    0x0(%r13),%eax
  40111b:	83 e8 01             	sub    $0x1,%eax
  40111e:	83 f8 05             	cmp    $0x5,%eax
  401121:	76 05                	jbe    401128 <phase_6+0x34> # looping every number, every number is within [1,6] (integer)
  401123:	e8 12 03 00 00       	callq  40143a <explode_bomb>
  401128:	41 83 c4 01          	add    $0x1,%r12d
  40112c:	41 83 fc 06          	cmp    $0x6,%r12d
  401130:	74 21                	je     401153 <phase_6+0x5f> # the exit of the outer while loop
  401132:	44 89 e3             	mov    %r12d,%ebx
  401135:	48 63 c3             	movslq %ebx,%rax          # the start of the inner for loop
  401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
  40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
  40113e:	75 05                	jne    401145 <phase_6+0x51> # none of num1 ~ num6 can be the same
  401140:	e8 f5 02 00 00       	callq  40143a <explode_bomb>
  401145:	83 c3 01             	add    $0x1,%ebx
  401148:	83 fb 05             	cmp    $0x5,%ebx
  40114b:	7e e8                	jle    401135 <phase_6+0x41> # the end of the inner for loop
  40114d:	49 83 c5 04          	add    $0x4,%r13 
  401151:	eb c1                	jmp    401114 <phase_6+0x20> # the end of the outer while loop
push是为保护原来的值,最后会pop回去。重要的在401100开始,将rsp的值赋给r13和rsi后调用read_six_numbers,这个函数在phase_2中我们遇到过,作用是将我们输入的6个数字存储在从rsi所存储地址开始的连续24个字节中,这里由于rsi已经被赋予了rsp的值,我们输入的6个数字被存储在rsp标记的连续24个字节中

接着是一个准备:rsp的值赋给r14,r12等于0

这个准备后是401114,我们会在后面看到这是一个while循环的开始,r13的值被赋给rbp,r13所指值被赋给eax,接着eax减去1,然后与5比较,在401121我们看到它必须小于等于5,否则触雷;接着r12加一,然后与6比较,如果不是6,就将r12赋给ebx,再将其赋给eax(这是内部for循环的开始),

接着关键的一步是,rsp+4*rax所指的值被赋给了eax,eax将会与rbp所指向的值比较,在40113e看见必须不相等,否则触雷,如果成功跳过,将ebx加上一后,ebx与5比较,直到ebx大于5,都要跳回401135(for循环的开始)

这两个循环嵌套做了什么呢?首先看外部的while,它将r13所指向的值减一与5比较,r13已经被赋予rsp的值,它指向的是num1,我们输入的第一个数,考虑到比较法是jbe,这个数必须是在[1,6]上的整数。r12被加上1,这个值是用来判断有多少个输入数已经被减一和5比较过了,它在值为6时标记退出,这时所有数都被比较过。

既然r12标记了现在比较的是哪一个数,r12被赋给ebx和rax,rax存储它的值后,rsp+4*rax就是它的下一个数,40113e表明这两个数不能相等,其后ebx而40114b的跳跃表明rax又加上1,rsp+4*rax就是下下个数,依旧不能与一开始的数相等... 这样一圈下来,比如r12是1的话,num1就不能与num2,num3...num6中任何一个相等

而在40114b满足后,r13被加上4,然后跳回while loop的开始,这时一切都一样,只是r13指向num2了,同样的套路进行下去,直到r13指向num6才结束

现在可以回答:这两个循环检查了我们输入的6个整数,它们全都要在[1,6]上,并且两两不相等

接下来看看第二段:

  401153:    48 8d 74 24 18           lea    0x18(%rsp),%rsi
  401158:    4c 89 f0                 mov    %r14,%rax
  40115b:    b9 07 00 00 00           mov    $0x7,%ecx
  401160:    89 ca                    mov    %ecx,%edx # the start of a while loop
  401162:    2b 10                    sub    (%rax),%edx
  401164:    89 10                    mov    %edx,(%rax) # num1=7-num1, num2=7-num2, ... ,num6=7-num6
  401166:    48 83 c0 04              add    $0x4,%rax
  40116a:    48 39 f0                 cmp    %rsi,%rax
  40116d:    75 f1                    jne    401160 <phase_6+0x6c> # the exit of a while loop, looped for 6 times
rsi标记了rsp+24,结束地址,rax存储r14,这时r14还存着rsp的值,然后ecx被赋成7,7被赋给edx,然后用edx减去eax处的值,把这个值存在eax处,接着eax+4,回到赋值给edx的地方,直到eax遇到rsi。这个循环的作用是把每个我们输入的num变成7-num

然后:

  40116f:	be 00 00 00 00       	mov    $0x0,%esi
  401174:	eb 21                	jmp    401197 <phase_6+0xa3>
  401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx # start of the loop
  40117a:	83 c0 01             	add    $0x1,%eax
  40117d:	39 c8                	cmp    %ecx,%eax
  40117f:	75 f5                	jne    401176 <phase_6+0x82>
  401181:	eb 05                	jmp    401188 <phase_6+0x94>
  401183:	ba d0 32 60 00       	mov    $0x6032d0,%edx
  401188:	48 89 54 74 20       	mov    %rdx,0x20(%rsp,%rsi,2) # make rsi+32+x store the location of the nodes according to numi order
  40118d:	48 83 c6 04          	add    $0x4,%rsi
  401191:	48 83 fe 18          	cmp    $0x18,%rsi
  401195:	74 14                	je     4011ab <phase_6+0xb7> #exit 
  401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx
  40119a:	83 f9 01             	cmp    $0x1,%ecx
  40119d:	7e e4                	jle    401183 <phase_6+0x8f>
  40119f:	b8 01 00 00 00       	mov    $0x1,%eax
  4011a4:	ba d0 32 60 00       	mov    $0x6032d0,%edx
  4011a9:	eb cb                	jmp    401176 <phase_6+0x82>
这一部分的循环不像for和while loop那样有结构,最好画一张图。rsi被赋成0后跳转401197,ecx被赋成rsp+rax所指向的值,然后与1比较,

如果小于等于1则跳到401183:edx赋成0x6032d0,rdx被赋给rsp+2*rsi+32所指向的为止,然后rsi加上4,与24比较,如果相等则跳出这个循环,否则将ecx被赋值成rsp+rsi所指向的值,继续与1比较的过程

不妨假设我们输入的第一个数就是6,所以从401174跳到401197,

ecx到这里变成了1,这样满足40119d的跳跃条件,跳到401183,edx赋成6032d0,然后把rdx存到rsp+32的位置(这时rsi是0),然后rsi加上4

6032d0那里存着什么呢? 用x/a命令看,那里存着一个数 0x0000014c,并且看起来是一个node1(终端显示)

这个node是什么结构的呢?401176处,rdx被赋值成rdx+8所指向的东西,看看0x6032d8,那里存着0x6032e0(node2的地址)

这样就能猜出来,node是一个结构体,含有两个量,第一个是整型数,第二个则是一个指针指向下一个node,这其实就是一个链表:

0x6032d0 <node1>:    0x10000014c    0x6032e0 <node2>
0x6032e0 <node2>:    0x2000000a8    0x6032f0 <node3>
0x6032f0 <node3>:    0x30000039c    0x603300 <node4>
0x603300 <node4>:    0x4000002b3    0x603310 <node5>
0x603310 <node5>:    0x5000001dd    0x603320 <node6>
0x603320 <node6>:    0x6000001bb    0x0 (注意每个整型数的第一个数字只代表这是第几个node,不是整型数的值的一部分)
那么上面的循环体在做什么?稍微观察可以看到,它的退出条件只有rsi==24,而rsi从0开始每次增加4,总共要处理6次

每次处理中,edx都首先被赋予0x6032d0,如果ecx本身就是1,就省去了40117a到40117f累加eax的过程,因为这时num就是1,指向第一个节点,那么就将rsp+32赋予这个节点的地址

如果eax不是1,就要经过那个累加直到eax==ecx,然后将rsp+32+2*rsi这个地址上存储某个节点的地址

那个节点是哪个呢?从401176可以看出,rdx在每次累加eax后都会变成下一个节点的地址(从第一个开始),那么最后它就变成了num的数值标记的那个节点

所以,这个循环的作用就是,按num1~num6的数值所标顺序在rsp+32到rsp+72这一段地址上存储6个节点的地址

例如,如果我输入1 2 3 4 5 6,在这里变成6 5 4 3 2 1, 节点的存储顺序就是node6 node5 node4 node3 node2 node1

接下来又是一个循环

  4011ab:	48 8b 5c 24 20       	mov    0x20(%rsp),%rbx
  4011b0:	48 8d 44 24 28       	lea    0x28(%rsp),%rax
  4011b5:	48 8d 74 24 50       	lea    0x50(%rsp),%rsi
  4011ba:	48 89 d9             	mov    %rbx,%rcx
  4011bd:	48 8b 10             	mov    (%rax),%rdx #starting a loop
  4011c0:	48 89 51 08          	mov    %rdx,0x8(%rcx) # retail the linked list (set every node's tail pointer to the new next node)
  4011c4:	48 83 c0 08          	add    $0x8,%rax
  4011c8:	48 39 f0             	cmp    %rsi,%rax
  4011cb:	74 05                	je     4011d2 <phase_6+0xde> #exit the loop
  4011cd:	48 89 d1             	mov    %rdx,%rcx
  4011d0:	eb eb                	jmp    4011bd <phase_6+0xc9> 

rsi被赋成rsp+80,不难看出这标记着链表结尾

rbx从rsp+32开始,rax从rsp+40开始,rcx从rsp+32开始

每次循环都将rdx赋成rax所指向的值,然后将rcx+8所指的地址存成rdx,然后rax加8,直到rax等于rsi退出

这个循环的作用很简单,在4011c0处可以看出,这个循环让新排好的node序列中每个node的指针域指向新链表中的下一个node(因为我们可能打乱了原先链表的顺序,需要重连)

  4011d2:	48 c7 42 08 00 00 00 	movq   $0x0,0x8(%rdx)
  4011d9:	00 
  4011da:	bd 05 00 00 00       	mov    $0x5,%ebp
  4011df:	48 8b 43 08          	mov    0x8(%rbx),%rax # the start of a for loop
  4011e3:	8b 00                	mov    (%rax),%eax
  4011e5:	39 03                	cmp    %eax,(%rbx)
  4011e7:	7d 05                	jge    4011ee <phase_6+0xfa>
  4011e9:	e8 4c 02 00 00       	callq  40143a <explode_bomb>
  4011ee:	48 8b 5b 08          	mov    0x8(%rbx),%rbx
  4011f2:	83 ed 01             	sub    $0x1,%ebp
  4011f5:	75 e8                	jne    4011df <phase_6+0xeb> # the end of a for loop
  4011f7:	48 83 c4 50          	add    $0x50,%rsp
  4011fb:	5b                   	pop    %rbx
  4011fc:	5d                   	pop    %rbp
  4011fd:	41 5c                	pop    %r12
  4011ff:	41 5d                	pop    %r13
  401201:	41 5e                	pop    %r14
  401203:	c3                   	retq   
最后一段代码一开始将rdx+8的地方存上0,这也是在完成上个循环的工作:最后一个节点的指针域为NULL

4011da将ebp赋成5,然后循环开始:

rax赋成rbx+8所指的值,也就是下一个节点的地址(rbx在上一个循环中等于rsp+32,第一个节点的地址)

然后rax等于其自身所指的值,也就是节点所存整型数的数值

比较rbx的节点整型值和rax,在4011e7可以看出,前一个节点的整型数值必须更大,否则触雷

然后rbx加上12变成下一个节点的地址,ebp减去1,回到循环开头

这个循环告诉我们,新的链表中每个节点的值都要大于下一个的。

回到0x6032d0开始的那一片链表,比较一下那些数的大小不难发现满足条件的重排链表是: node3 node4 node5 node6 node1 node2

考虑到num变成了7-num,我们一开始的输入就应该是:4 3 2 1 6 5

这样就通过了phase 6