[CS:APP] BombLab Phase3 해설

main

 

<+148> : main함수에서 read_line의 반환값이 %rdi에 저장되는 것으로보아, 입력한 문자열이 %rdi에 저장됨을 추론할 수 있습니다.

   0x0000555555401214 <+138>:	callq  0x555555400f00 <puts@plt>
   0x0000555555401219 <+143>:	callq  0x555555401b0d <read_line>
   0x000055555540121e <+148>:	mov    %rax,%rdi
   0x0000555555401221 <+151>:	callq  0x55555540136d <phase_3>

 

테스트 결과 일치함을 확인할 수 있었습니다.

(gdb) x/s $rdi
0x555555604760 <input_strings+160>:	"50 100"

---

__isoc99_sscanf 분석

 

phase2에서 __isoc99_sscanf 함수에 대해 이미 알아낸 사실들이 많습니다.

1. 입력한 정수가 %rdi에서 저장된 문자열에서 배열형태로 변환됩니다.
2. 첫번째 원소를 가리키는 포인터가 %rsp에 저장됩니다.
3. 입력한 정수의 개수를 %rax에 반환합니다.

따라서 50 100을 입력했을 때 오른쪽의 상황을 가집니다.

 

---

Phase_3

Dump of assembler code for function phase_3:
   0x000055555540136d <+0>:	sub    $0x18,%rsp
   0x0000555555401371 <+4>:	mov    %fs:0x28,%rax
   0x000055555540137a <+13>:	mov    %rax,0x8(%rsp)
   0x000055555540137f <+18>:	xor    %eax,%eax
   0x0000555555401381 <+20>:	lea    0x4(%rsp),%rcx
   0x0000555555401386 <+25>:	mov    %rsp,%rdx
   0x0000555555401389 <+28>:	lea    0x1a5d(%rip),%rsi        # 0x555555402ded
   0x0000555555401390 <+35>:	callq  0x555555400fc0 <__isoc99_sscanf@plt>
   0x0000555555401395 <+40>:	cmp    $0x1,%eax
   0x0000555555401398 <+43>:	jle    0x5555554013b3 <phase_3+70>
   0x000055555540139a <+45>:	cmpl   $0x7,(%rsp)
   0x000055555540139e <+49>:	ja     0x5555554013eb <phase_3+126>
   0x00005555554013a0 <+51>:	mov    (%rsp),%eax
   0x00005555554013a3 <+54>:	lea    0x1796(%rip),%rdx        # 0x555555402b40
   0x00005555554013aa <+61>:	movslq (%rdx,%rax,4),%rax
   0x00005555554013ae <+65>:	add    %rdx,%rax
   0x00005555554013b1 <+68>:	jmpq   *%rax
   0x00005555554013b3 <+70>:	callq  0x555555401a90 <explode_bomb>
   0x00005555554013b8 <+75>:	jmp    0x55555540139a <phase_3+45>
   0x00005555554013ba <+77>:	mov    $0x8c,%eax
   0x00005555554013bf <+82>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c1 <+84>:	mov    $0x3be,%eax
   0x00005555554013c6 <+89>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c8 <+91>:	mov    $0x79,%eax
   0x00005555554013cd <+96>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013cf <+98>:	mov    $0x2c9,%eax
   0x00005555554013d4 <+103>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013d6 <+105>:	mov    $0x379,%eax
   0x00005555554013db <+110>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013dd <+112>:	mov    $0x347,%eax
   0x00005555554013e2 <+117>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013e4 <+119>:	mov    $0x39a,%eax
   0x00005555554013e9 <+124>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013eb <+126>:	callq  0x555555401a90 <explode_bomb>
   0x00005555554013f0 <+131>:	mov    $0x0,%eax
   0x00005555554013f5 <+136>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013f7 <+138>:	mov    $0x123,%eax
   0x00005555554013fc <+143>:	cmp    %eax,0x4(%rsp)
   0x0000555555401400 <+147>:	je     0x555555401407 <phase_3+154>
   0x0000555555401402 <+149>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401407 <+154>:	mov    0x8(%rsp),%rax
   0x000055555540140c <+159>:	xor    %fs:0x28,%rax
   0x0000555555401415 <+168>:	jne    0x55555540141c <phase_3+175>
   0x0000555555401417 <+170>:	add    $0x18,%rsp
   0x000055555540141b <+174>:	retq
   0x000055555540141c <+175>:	callq  0x555555400f20 <__stack_chk_fail@plt>

 

---

<+40 ~ 49>

   0x0000555555401395 <+40>:	cmp    $0x1,%eax
   0x0000555555401398 <+43>:	jle    0x5555554013b3 <phase_3+70>
   0x000055555540139a <+45>:	cmpl   $0x7,(%rsp)
   0x000055555540139e <+49>:	ja     0x5555554013eb <phase_3+126>

   0x00005555554013b3 <+70>:	callq  0x555555401a90 <explode_bomb>

   0x00005555554013eb <+126>:	callq  0x555555401a90 <explode_bomb>

<+40> : 현재 R[%eax]는 입력한 숫자의 개수입니다. 입력한 숫자의 개수를 1과 비교합니다.

 

<+43> : 만약 1 이하라면 <+70>으로 점프합니다. <+70>은 폭탄이므로, 입력하는 숫자의 개수는 2개 이상이어야 합니다. (50을 입력했다고 가정했으므로 폭탄이 터집니다.)

 

<+45> : (%rsp)는 입력한 첫번째 숫자입니다. 첫번째 숫자와 7을 비교합니다.

 

<+49> : 7보다 크거나 0보다 작으면(ja는 unsigned 연산이므로) <+126>으로 점프합니다. 폭탄이므로 첫번째 숫자는 0이상, 7이하 여야합니다.

---

여기서부터는 0 291을 입력했다고 가정합니다.

 

<+51 ~ 68>

 

   0x00005555554013a0 <+51>:	mov    (%rsp),%eax
   0x00005555554013a3 <+54>:	lea    0x1796(%rip),%rdx        # 0x555555402b40
   0x00005555554013aa <+61>:	movslq (%rdx,%rax,4),%rax
   0x00005555554013ae <+65>:	add    %rdx,%rax
   0x00005555554013b1 <+68>:	jmpq   *%rax

 

<+51> : %eax에 입력한 첫번째 숫자를 저장합니다.

 

<+54> : <+54> 코드를 진행할 때의 R[%rip]는 <+61>의 주소, 0x00005555554013aa입니다. (%rip, PC는 다음 실행할 명령어의 주소를 가리킨다.)

즉, R[%rdx] = 0x1796 + 0x00005555554013aa = 0x555555402b40 가 됩니다.

 

<+61> : %rax는 입력한 첫번째 숫자를 의미하는데, 0이상 7이하의 숫자를 가지는 숫자에 4를 곱해서 %rdx에 더한값이 가리키는 주소의 값을 %rax에 저장합니다. R[%rdx] + 4 * R[%rax]의 참조 값은 gdb test로 알아낼 수 있었습니다.

 

첫번째 숫자	R[%rdx] + 4 * R[%rax]	%rax = M[R[%rdx] + 4 * R[%rax]] Hex, Dec
0	0x555555402b40	0xffffffffffffe8b7, -5961
1	0x555555402b44	0xffffffffffffe87a, -6022
2	0x555555402b48	0xffffffffffffe881, -6015
3	0x555555402b5c	0xffffffffffffe888, -6008
4	0x555555402b60	0xffffffffffffe88f, -6001
5	0x555555402b64	0xffffffffffffe896, -5994
6	0x555555402b68	0xffffffffffffe89d, -5987
7	0x555555402b7c	0xffffffffffffe8a4, -5980

 

<+65> : %rax에 %rdx를 한번 더 더합니다. ( R[%rdx] is 0x555555402b40, 93824990849856(demical)  )

 

<+68> : %rax가 가진 주소값으로 점프합니다. %rax 숫자별로 점프하는 곳을 표시하고 정리하면 밑과 같습니다.

 

 

첫번째 숫자	%rax Hex, Dec	jump <+ ? >
0	0x5555554013F7, 93824990843895	<+138>
1	0x5555554013BA, 93824990843834	<+77>
2	0x5555554013C1, 93824990843841	<+84>
3	0x5555554013C8, 93824990843848	<+119>
4	0x5555554013CF, 93824990843855	<+98>
5	0x5555554013D6, 93824990843862	<+105>
6	0x5555554013DD, 93824990843869	<+112>
7	0x5555554013E4, 93824990843876	<+119>

 

---

<77 ~ 138>

 

   0x00005555554013ba <+77>: mov    $0x8c,%eax
   0x00005555554013bf <+82>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c1 <+84>: mov    $0x3be,%eax
   0x00005555554013c6 <+89>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c8 <+91>: mov    $0x79,%eax
   0x00005555554013cd <+96>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013cf <+98>: mov    $0x2c9,%eax
   0x00005555554013d4 <+103>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013d6 <+105>: mov    $0x379,%eax
   0x00005555554013db <+110>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013dd <+112>: mov    $0x347,%eax
   0x00005555554013e2 <+117>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013e4 <+119>: mov    $0x39a,%eax
   0x00005555554013e9 <+124>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013eb <+126>: callq  0x555555401a90 <explode_bomb>
   0x00005555554013f0 <+131>: mov    $0x0,%eax
   0x00005555554013f5 <+136>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013f7 <+138>: mov    $0x123,%eax

 

첫번째 숫자에 따라 점프해서 %eax에 값을 저장하고 있습니다.

각 숫자별로 정리하면 다음과 같습니다.

 

첫번째 숫자	jump <+ ? >	Demical : R[%eax]
0	<+138>	291
1	<+77>	140
2	<+84>	958
3	<+119>	922
4	<+98>	713
5	<+105>	889
6	<+112>	839
7	<+119>	922

---

<143 ~ 174>

 

   0x00005555554013fc <+143>:	cmp    %eax,0x4(%rsp)
   0x0000555555401400 <+147>:	je     0x555555401407 <phase_3+154>
   0x0000555555401402 <+149>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401407 <+154>:	mov    0x8(%rsp),%rax
   0x000055555540140c <+159>:	xor    %fs:0x28,%rax
   0x0000555555401415 <+168>:	jne    0x55555540141c <phase_3+175>
   0x0000555555401417 <+170>:	add    $0x18,%rsp
   0x000055555540141b <+174>:	retq

 

<+143> : 0x4(%rsp) 는 우리가 입력한 두번째 숫자를 의미합니다. 두번째 숫자와 R[%eax]를 비교하고 있습니다.

 

<+147> : 만약 위에서 정리한 R[%eax]와 두번째 숫자가 같다면 <+154>로 점프합니다.

 

<+149> : 만약 두번째 숫자가 R[%eax]와 다르다면, 폭탄이 터지게 되므로 두번째 숫자와 R[%eax]가 같아야함이 밝혀졌습니다.

---

즉 답은 다음과 같습니다.

 

첫번째 숫자	두번째 숫자
0	291
1	140
2	958
3	922
4	713
5	889
6	839
7	922