phase_4의 앞부분을 보면 다른 phase들처럼 sscanf 가 호출된다.
0000000000001775 <phase_4>:
1775: f3 0f 1e fa endbr64
1779: 48 83 ec 18 sub $0x18,%rsp
177d: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
1784: 00 00
1786: 48 89 44 24 08 mov %rax,0x8(%rsp)
178b: 31 c0 xor %eax,%eax
178d: 48 8d 4c 24 04 lea 0x4(%rsp),%rcx
1792: 48 89 e2 mov %rsp,%rdx
1795: 48 8d 35 71 1c 00 00 lea 0x1c71(%rip),%rsi # 340d <array.3473+0x28d>
179c: e8 4f fb ff ff callq 12f0 <__isoc99_sscanf@plt>
17a1: 83 f8 02 cmp $0x2,%eax
17a4: 75 06 /--- jne 17ac <phase_4+0x37>
17a6: 83 3c 24 0e | cmpl $0xe,(%rsp)
17aa: 76 05 /----|--- jbe 17b1 <phase_4+0x3c>
17ac: e8 ef 05 00 00 | \--> callq 1da0 <explode_bomb>이전과 같은 구조로 이번에도 두개의 정수를 입력받는다는 것을 알 수 있다. 이번에는 입력한 정수가 정확히 2개일 경우에만 폭탄이 터지지 않는다.
- 1st argument (%rdi): 사용자가 입력한 문자열.
- 2nd argument (%rsi): %d %d
- 3rd argument (%rdx): %rsp. 배열 arr
- 4th argument (%rcx): %rsp + 0x4 -> arr[1]
다음 내용을 보자.
0000000000001775 <phase_4>:
# ...
17a1: 83 f8 02 cmp $0x2,%eax
17a4: 75 06 /--- jne 17ac <phase_4+0x37>
17a6: 83 3c 24 0e | cmpl $0xe,(%rsp) # 14
17aa: 76 05 /----|--- jbe 17b1 <phase_4+0x3c>
17ac: e8 ef 05 00 00 | \--> callq 1da0 <explode_bomb>
17b1: ba 0e 00 00 00 \-------> mov $0xe,%edx
17b6: be 00 00 00 00 mov $0x0,%esi
17bb: 8b 3c 24 mov (%rsp),%edi
17be: e8 71 ff ff ff callq 1734 <func4>
# ...2개의 정수를 입력받으면 첫 번째 정수 arr[0]이 0xe(14)이하여야 explode_bomb을 jump한다. 그리고다음과 같이 3개의 인자를 전달해 func4 함수를 호출한다.
- 1st argument (%rdi): arr[0]
- 2nd argument (%rsi): 0
- 3rd argument (%rdx): 14
func4 함수를 확인해본다.
0000000000001734 <func4>:
1734: f3 0f 1e fa endbr64
1738: 48 83 ec 08 sub $0x8,%rsp
173c: 89 d0 mov %edx,%eax
173e: 29 f0 sub %esi,%eax
1740: 89 c1 mov %eax,%ecx
1742: c1 e9 1f shr $0x1f,%ecx
1745: 01 c1 add %eax,%ecx
1747: d1 f9 sar %ecx
1749: 01 f1 add %esi,%ecx
174b: 39 f9 cmp %edi,%ecx
174d: 7f 0c /--- jg 175b <func4+0x27>
174f: b8 00 00 00 00 | mov $0x0,%eax
1754: 7c 11 /---|--- jl 1767 <func4+0x33>
1756: 48 83 c4 08 /---|---|--> add $0x8,%rsp
175a: c3 | | | retq
175b: 8d 51 ff | | \--> lea -0x1(%rcx),%edx
175e: e8 d1 ff ff ff | | callq 1734 <func4>
1763: 01 c0 | | add %eax,%eax
1765: eb ef +---|------- jmp 1756 <func4+0x22>
1767: 8d 71 01 | \------> lea 0x1(%rcx),%esi
176a: e8 c5 ff ff ff | callq 1734 <func4>
176f: 8d 44 00 01 | lea 0x1(%rax,%rax,1),%eax
1773: eb e1 \----------- jmp 1756 <func4+0x22>
인자들의 계산부분을 먼저 확인해보자.
0000000000001734 <func4>:
1734: f3 0f 1e fa endbr64
1738: 48 83 ec 08 sub $0x8,%rsp
173c: 89 d0 mov %edx,%eax
173e: 29 f0 sub %esi,%eax
1740: 89 c1 mov %eax,%ecx
1742: c1 e9 1f shr $0x1f,%ecx
1745: 01 c1 add %eax,%ecx
1747: d1 f9 sar %ecx
1749: 01 f1 add %esi,%ecx
# ...%rdi: arg1(arr[0]), %rsi: arg2(0), %rdx: arg3(14)이다. 여기서 레지스터 간의 연산을 보면 아래와 같다.
- 173c: %eax = arg3
- 173e: %eax = arg3 - arg2
- 1740: %ecx = arg3 - arg2
- 1742: %ecx = (arg3 - arg2) >> 31 (logical)
- 1745: %ecx = %ecx + (arg3 - arg2)
- 1747: %ecx = %ecx >> 1 (arith.)
- 1749: %ecx = %ecx + arg2
1742 줄을 보면, 31만큼 locigal right shift를 수행한다. 즉, 여기서 %ecx는 arg3 - arg2의 부호를 의미한다. arg3 - arg2가 양수라면 %ecx = 0, 음수라면 %ecx = -1이다. 이 값에 (arg3 - arg2)를 더하고 절반으로 나눈다. 즉, 이는 음수의 경우 nearlest even rounding을 위한 보정이다. 만약 arg3 - arg2가 15라면, %ecx는 15/2 = 7.5이므로 8이 되고, -15인 경우도 (-15 -1)/2 = -7.5이므로 -8이 되어 양수와 음수의 경우 모두 중간값을 계산한다. 마지막으로 1749 줄에서 arg2를 더해준다. 즉, 위의 연산은 다음과 같다.
(arg3 - arg2)/2 + arg2이는 arg3과 arg2의 중간값이 된다. 이제 다음 부분을 보자.
0000000000001734 <func4>:
# ...
174b: 39 f9 cmp %edi,%ecx
174d: 7f 0c /--- jg 175b <func4+0x27>
174f: b8 00 00 00 00 | mov $0x0,%eax
1754: 7c 11 /---|--- jl 1767 <func4+0x33>
1756: 48 83 c4 08 /---|---|--> add $0x8,%rsp
175a: c3 | | | retq
175b: 8d 51 ff | | \--> lea -0x1(%rcx),%edx
175e: e8 d1 ff ff ff | | callq 1734 <func4>
1763: 01 c0 | | add %eax,%eax
1765: eb ef +---|------- jmp 1756 <func4+0x22>
1767: 8d 71 01 | \------> lea 0x1(%rcx),%esi
176a: e8 c5 ff ff ff | callq 1734 <func4>
176f: 8d 44 00 01 | lea 0x1(%rax,%rax,1),%eax
1773: eb e1 \----------- jmp 1756 <func4+0x22>%ecx(arg3와 arg2의 중간값)와 arg1(arr[0])을 비교한다. %ecx를 median이라 정의하고 따라가보자.
median > arr[0]이면 arg3 = median - 1로 정의하고 다시 func4를 호출한다. recursion 구조이다. 나머지도 쭉 따라가보면, 다음과 같은 구조임을 알 수 있다.
int func4(int arg1, int arg2, int arg3) {
int median = (arg3 - arg2) / 2 + arg2;
int ret;
if(median > arg1){
func4(arg1, arg2, median - 1);
ret += ret;
}
else{
ret = 0;
if (median < arg1){
func4(arg1, median + 1, arg3);
ret += ret + 1;
}
}
return ret;
}이는 이진탐색을 수행하는 코드로, 결국 func4는 arr1을 arg2와 arg3의 범위 내에서 이진탐색을 수행하고, 탐색 경로에 따라 반환값이 조정된다.
위와 같은 이진 트리에서 루트 노드인 7을 기준으로 arg1값이 루트 노드보다 크다면 ret을 2배 + 1하고 오른쪽 서브 트리를 탐색한다. 작다면 ret을 2배하고 왼쪽 서브 트리를 탐색한다. 다시 phase_4 함수를 보자.
17be: e8 71 ff ff ff callq 1734 <func4>
17c3: 83 f8 05 cmp $0x5,%eax
17c6: 75 07 /--- jne 17cf <phase_4+0x5a>
17c8: 83 7c 24 04 05 | cmpl $0x5,0x4(%rsp)
17cd: 74 05 /---|--- je 17d4 <phase_4+0x5f>
17cf: e8 cc 05 00 00 | \--> callq 1da0 <explode_bomb>
17d4: 48 8b 44 24 08 \------> mov 0x8(%rsp),%rax
17d9: 64 48 33 04 25 28 00 xor %fs:0x28,%rax
17e0: 00 00
17e2: 75 05 /--- jne 17e9 <phase_4+0x74>
17e4: 48 83 c4 18 | add $0x18,%rsp
17e8: c3 | retq
17e9: e8 62 fa ff ff \--> callq 1250 <__stack_chk_fail@plt>func4의 return value가 5가 아니면 17cf로 jump해 폭발하고, arr[1]이 5가 아니면 폭발한다.
func4에서 ret이 5라는 것은 마지막 recursion의 return 부터 역으로 거슬러가면 다음과 같은 구조임을 알 수 있다.
1st recursion: ret == 5
2nd recursion: ret == 2
3rd recursion: ret == 1
4th recursion: ret == 0
즉, 오른쪽 탐색 -> 왼쪽 탐색 -> 오른쪽 탐색을 수행해야 ret이 5가 된다. 이진트리를 참고하면 이를 만족하는 값은 10으로, phase_4의 정답은 10 5가 된다.
(gdb) set args psol.txt
(gdb) break explode_bomb
Breakpoint 1 at 0x1da0
(gdb) info breakpoint
Num Type Disp Enb Address What
1 breakpoint keep y 0x0000000000001da0 <explode_bomb>
(gdb) run
Starting program: /home/origami0352/bomb4/bomb psol.txt
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
Phase 1 defused. How about the next one?
That's number 2. Keep going!
Halfway there!
10 5
So you got that one. Try this one.
^Cphase_4 클리어
psol.txt 추가
Wow! Brazil is big.
1 2 4 8 16 32
0 984
10 5
