[CS:APP] BombLab Phase5 해설

phase_5

Dump of assembler code for function phase_5:
=> 0x00005555554014ca <+0>:	push   %rbx
   0x00005555554014cb <+1>:	mov    %rdi,%rbx
   0x00005555554014ce <+4>:	callq  0x55555540176f <string_length>
   0x00005555554014d3 <+9>:	cmp    $0x6,%eax
   0x00005555554014d6 <+12>:	jne    0x555555401509 <phase_5+63>
   0x00005555554014d8 <+14>:	mov    %rbx,%rax
   0x00005555554014db <+17>:	lea    0x6(%rbx),%rdi
   0x00005555554014df <+21>:	mov    $0x0,%ecx
   0x00005555554014e4 <+26>:	lea    0x1675(%rip),%rsi        # 0x555555402b60 <array.3417>
   0x00005555554014eb <+33>:	movzbl (%rax),%edx
   0x00005555554014ee <+36>:	and    $0xf,%edx
   0x00005555554014f1 <+39>:	add    (%rsi,%rdx,4),%ecx
   0x00005555554014f4 <+42>:	add    $0x1,%rax
   0x00005555554014f8 <+46>:	cmp    %rdi,%rax
   0x00005555554014fb <+49>:	jne    0x5555554014eb <phase_5+33>
   0x00005555554014fd <+51>:	cmp    $0x3a,%ecx
   0x0000555555401500 <+54>:	je     0x555555401507 <phase_5+61>
   0x0000555555401502 <+56>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401507 <+61>:	pop    %rbx
   0x0000555555401508 <+62>:	retq
   0x0000555555401509 <+63>:	callq  0x555555401a90 <explode_bomb>
   0x000055555540150e <+68>:	jmp    0x5555554014d8 <phase_5+14>

---

<+1 ~ 12>

 

   0x00005555554014cb <+1>:	mov    %rdi,%rbx
   0x00005555554014ce <+4>:	callq  0x55555540176f <string_length>
   0x00005555554014d3 <+9>:	cmp    $0x6,%eax
   0x00005555554014d6 <+12>:	jne    0x555555401509 <phase_5+63>

<+1> : 전에 분석했듯이 우리가 입력한 것들은 한줄의 문자열로 %rdi에 저장됩니다. 그리고 이를 %rbx에도 저장합니다.

 

<+4> : string_length도 phase_1에서 분석했었듯이 레지스터 %rdi와 %rdx로 이루어져 그 간격을 %rax에 저장해서 반환하는 함수입니다.

 

<+9> : 그 반환값을 6과 비교합니다.

 

<+12> : 반환값, 즉 문자열의 길이가 6이 아니라면 <+63>으로 점프해서 폭탄이 터지므로, 입력하는 문자열의 길이는 6이어야합니다.

   0x0000555555401509 <+63>:	callq  0x555555401a90 <explode_bomb>

---

<+14 ~ 36>

 

   0x00005555554014d8 <+14>:	mov    %rbx,%rax
   0x00005555554014db <+17>:	lea    0x6(%rbx),%rdi
   0x00005555554014df <+21>:	mov    $0x0,%ecx
   0x00005555554014e4 <+26>:	lea    0x1675(%rip),%rsi        # 0x555555402b60 <array.3417>
   0x00005555554014eb <+33>:	movzbl (%rax),%edx
   0x00005555554014ee <+36>:	and    $0xf,%edx

 

<+14> : %rax에 %rbx가 가지고 있는 포인터를 복사합니다.

 

<+17> : %rdi에 0x6(%rbx), 즉 6번째 문자를 저장합니다.

 

<+21> : %ecx에 0을 저장합니다.

 

<+26> : 배열을 저장하는것으로 추측됩니다.

 

<+33> : (%rax)는 문자열의 첫번째 문자입니다. 이를 %edx에 저장합니다.

 

<+36> : 첫번째 문자를 15와 &연산합니다. 영어 문자가 대소문자든 숫자문자든 아무상관없이 정수 1부터 26까지 순서대로 대응되도록 해줍니다.

 

 

a	b	c	d	e	f	g	h	i	j	k	l
A	B	C	D	E	F	G	H	I	J	K	L
'1'	'2'	'3'	'4'	'5'	'6'	'7'	'8'	'9'
↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓
1	2	3	4	5	6	7	8	9	10	11	12

 

m

n

o

p

q

r

s

t

u

v

w

x

y

z

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

13

14

15

16

17

18

19

20

21

22

23

24

25

26

 

 

---

<+39 ~ 68>

   0x00005555554014f1 <+39>:	add    (%rsi,%rdx,4),%ecx
   0x00005555554014f4 <+42>:	add    $0x1,%rax
   0x00005555554014f8 <+46>:	cmp    %rdi,%rax
   0x00005555554014fb <+49>:	jne    0x5555554014eb <phase_5+33>
   0x00005555554014fd <+51>:	cmp    $0x3a,%ecx
   0x0000555555401500 <+54>:	je     0x555555401507 <phase_5+61>
   0x0000555555401502 <+56>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401507 <+61>:	pop    %rbx
   0x0000555555401508 <+62>:	retq
   0x0000555555401509 <+63>:	callq  0x555555401a90 <explode_bomb>
   0x000055555540150e <+68>:	jmp    0x5555554014d8 <phase_5+14>

 

<+39> : %rsi에 정보를 알기 힘든 배열을 저장했었습니다. 그리고 이 <+39>의 operand에서 %rsi의 배열을 4바이트를 단위로 접근함을 알 수 있습니다. 즉 %rsi는 4바이트 int형 정수배열이 저장되었다는 관점으로 볼 수 있습니다.

 

(gdb) x/30dw $rsi
0x555555402b60 <array.3417>:	2	10	6	1
0x555555402b70 <array.3417+16>:	12	16	9	3
0x555555402b80 <array.3417+32>:	4	7	14	5
0x555555402b90 <array.3417+48>:	11	8	15	13
0x555555402ba0:	2032168787	1948284271	1802398056	1970239776
0x555555402bb0:	1851876128	1869902624	1752440944	1868701797
0x555555402bc0:	1998611053	543716457	1819440227	539779885
0x555555402bd0:	2032168804	4158831

 

때문에, 4바이트 단위로 끊어서 메모리에 저장된 값을 출력하면 다음과 같습니다.

 

30개를 출력해보았더니, 16개까지는 인위적으로 값을 집어넣은듯한 값이 있고 그 이후로는 쓰레기 값이 있기때문에 우선 사용할것같은 16개까지만 적었습니다. 

 

 

그리고 이 배열의 입력한 첫번째 문자에서 15와 &연산한 값만큼 한칸씩 이동해서 나온 element를 %ecx에 저장합니다.

저는 "abcdef"를 입력했다고 가정했기 때문에, 첫번째 element인 2를 저장합니다.

 

<+42> : %rax에 1을 더합니다.

 

<+46> :  %rax와 %rdi를 비교합니다.

 

<+49> : %rax와 %rdi가 다르면 <+33>으로 점프합니다.

 

<+51> : %rax와 %rdi가 같으면 58과 %ecx를 비교합니다.

 

<+54> : 58이면 <+61>로 점프해서 문제가 해결됩니다.

 

---

<결론>

상황을 관찰해보면,

%rax는 배열을 첫번째 요소에서 마지막 요소까지 순회합니다.

순회하면서, 각 입력한 문자가 위의 정수 배열의 인덱스 역할을 하며 인덱스가 가리키는 정수를 %ecx에 누적합니다.

 

그리고 마지막 요소의 순회까지 끝나면 R[%ecx]가 58이 되어야 합니다.

즉, 우리가 입력해야하는 문자열은 각 문자가 1부터 9로 대응되며 그 합이 58이 되는 문자열이고 답은 너무나도 많습니다.

 

몇가지 예시만 들어보면,

우선 58을 위의 배열에 있는 숫자 중에서 6개 숫자의 합으로 분리해야하므로,

10 + 10 + 10 + 16 + 9 + 3 으로 분리할 수 있습니다.

각 숫자의 인덱스는 1 1 1 5 6 7 이고, 1 1 1 5 6 7로 대응되는 문자들은 아래를 포함하여 너무나 많은 조합이 가능합니다.

aaaefg, 111567, AAAEFG, a1156G