세 가지 함수를 분석하겠습니다.
phase_4
func4
__isoc99_sscanf
__isoc99_sscanf

phase2에서 __isoc99_sscanf 함수에 알아낸 사실들을 정리하면 다음과 같습니다.
- 입력한 정수가 %rdi에서 저장된 문자열에서 배열형태로 변환됩니다.
- 첫번째 원소를 가리키는 포인터가 %rsp에 저장됩니다.
- 입력한 정수의 개수를 %rax에 반환합니다.
따라서 50 100 을 입력했다면 오른쪽의 상황을 가집니다.
phase_4
Dump of assembler code for function phase_4:
=> 0x0000555555401455 <+0>: sub $0x18,%rsp
0x0000555555401459 <+4>: mov %fs:0x28,%rax
0x0000555555401462 <+13>: mov %rax,0x8(%rsp)
0x0000555555401467 <+18>: xor %eax,%eax
0x0000555555401469 <+20>: lea 0x4(%rsp),%rcx
0x000055555540146e <+25>: mov %rsp,%rdx
0x0000555555401471 <+28>: lea 0x1975(%rip),%rsi # 0x555555402ded
0x0000555555401478 <+35>: callq 0x555555400fc0 <__isoc99_sscanf@plt>
0x000055555540147d <+40>: cmp $0x2,%eax
0x0000555555401480 <+43>: jne 0x555555401488 <phase_4+51>
0x0000555555401482 <+45>: cmpl $0xe,(%rsp)
0x0000555555401486 <+49>: jbe 0x55555540148d <phase_4+56>
0x0000555555401488 <+51>: callq 0x555555401a90 <explode_bomb>
0x000055555540148d <+56>: mov $0xe,%edx
0x0000555555401492 <+61>: mov $0x0,%esi
0x0000555555401497 <+66>: mov (%rsp),%edi
0x000055555540149a <+69>: callq 0x555555401421 <func4>
0x000055555540149f <+74>: cmp $0x7,%eax
0x00005555554014a2 <+77>: jne 0x5555554014ab <phase_4+86>
0x00005555554014a4 <+79>: cmpl $0x7,0x4(%rsp)
0x00005555554014a9 <+84>: je 0x5555554014b0 <phase_4+91>
0x00005555554014ab <+86>: callq 0x555555401a90 <explode_bomb>
0x00005555554014b0 <+91>: mov 0x8(%rsp),%rax
0x00005555554014b5 <+96>: xor %fs:0x28,%rax
0x00005555554014be <+105>: jne 0x5555554014c5 <phase_4+112>
0x00005555554014c0 <+107>: add $0x18,%rsp
0x00005555554014c4 <+111>: retq
0x00005555554014c5 <+112>: callq 0x555555400f20 <__stack_chk_fail@plt>
<+28>
__isoc99_sscanf 함수의 인자로 %rsi에 "%d %d"를 담아 전달합니다.
(gdb) x/s 0x555555402ded
0x555555402ded: "%d %d"
<+35>
1. "%d %d"를 전달해서 함수를 호출했으므로 두 개의 정수를 입력해야한다고 판단할 수 있습니다.
2. %rsp에 정수배열의 포인터가 저장됩니다.
3. %rax에 입력한 정수의 개수가 저장됩니다.
<+40 ~ 43>
0x000055555540147d <+40>: cmp $0x2,%eax
0x0000555555401480 <+43>: jne 0x555555401488 <phase_4+51>
0x0000555555401488 <+51>: callq 0x555555401a90 <explode_bomb>
<+40> : 입력한 정수의 개수를 2와 비교합니다.
<+43> : 입력한 정수의 개수가 2가 아니라면 <+51>로 점프하고 폭탄이 터지므로, 입력해야하는 정수의 개수는 2개입니다.
<+45 ~ 69>
0x0000555555401482 <+45>: cmpl $0xe,(%rsp)
0x0000555555401486 <+49>: jbe 0x55555540148d <phase_4+56>
0x0000555555401488 <+51>: callq 0x555555401a90 <explode_bomb>
0x000055555540148d <+56>: mov $0xe,%edx
0x0000555555401492 <+61>: mov $0x0,%esi
0x0000555555401497 <+66>: mov (%rsp),%edi
0x000055555540149a <+69>: callq 0x555555401421 <func4>

<+45> : (%rsp)는 오른쪽 그림과 같이 입력한 첫번째 정수입니다. 첫번째 정수와 14를 비교합니다.
<+49> : unsigned비교이므로 첫번째 정수가 0 미만, 14 초과라면 <+51>로 이동합니다.
<+51> : 폭탄이 터집니다. 즉 첫번째 정수는 0 이상 14 이하를 만족해야합니다.

<+56> : %edx에 14를 저장합니다.
<+61> : %esi에 0을 저장합니다.
<+66> : %edi에 첫번째 정수를 저장합니다.
<+69> : 바로 func4를 호출하는것으로 보아 %edx, %esi, %edi가 함수의 인자로 작동한다고 추측할 수 있습니다.
<+72 ~ 69>
0x000055555540149f <+74>: cmp $0x7,%eax
0x00005555554014a2 <+77>: jne 0x5555554014ab <phase_4+86>
0x00005555554014a4 <+79>: cmpl $0x7,0x4(%rsp)
0x00005555554014a9 <+84>: je 0x5555554014b0 <phase_4+91>
0x00005555554014ab <+86>: callq 0x555555401a90 <explode_bomb>
0x00005555554014b0 <+91>: mov 0x8(%rsp),%rax
0x00005555554014b5 <+96>: xor %fs:0x28,%rax
0x00005555554014be <+105>: jne 0x5555554014c5 <phase_4+112>
0x00005555554014c0 <+107>: add $0x18,%rsp
0x00005555554014c4 <+111>: retq
0x00005555554014c5 <+112>: callq 0x555555400f20 <__stack_chk_fail@plt>
<+74> : func4가 리턴된 후의 R[%eax]는 여전히 2(입력한 정수 개수는 항상 두개여야 함이 보장되었다)거나 func4의 리턴값 둘 중 하나일겁니다. 그 값을 7과 비교합니다.
<+77> : 만약 R[%eax]가 7이 아니면 <+86>으로 이동해서 폭탄이 터지므로, func4는 리턴값이 존재하는 함수임을 알 수 있습니다.
그리고 그 func4의 리턴값은 7이 나오도록 인자를 전달해야합니다.
<+79> : 0x4(%rsp)는 입력한 두 번째 숫자입니다. 두번째 숫자와 7을 비교합니다.
<+84> : 두번째 숫자가 7과 같은지 비교합니다.
<+86> : 두번째 숫자가 7이 아니면 폭탄이 터지므로, 두번째 숫자는 7 이어야합니다.
<이후> : 일반적인 함수를 마치려는 코드입니다.
func4를 분석하기 전에 우리가 문제를 해결하기위해 필요한 조건들을 정리해보겠습니다.
- 입력한 첫번째 숫자는 0 이상 14 이하를 만족해야한다.
- 입력한 두번째 숫자는 7 이어야 한다.
- %edx, %esi, %edi가 인자로 전달되며 그 값들은 다음과 같습니다. R[%edx] = 14, R[%esi] = 0, R[%edi] = 입력한 첫번째 정수
- 리턴값이 7이 되도록 인자를 전달해야하는데, R[%edx]와 R[%esi]는 14와 0으로 정해져있습니다. 즉 R[%edi]를 리턴값이 7이 되도록 전달해야합니다. 다시말하면 첫번째 정수를 리턴값이 7이 나오도록 입력해야합니다.
func4
Dump of assembler code for function func4:
0x0000555555401421 <+0>: push %rbx
0x0000555555401422 <+1>: mov %edx,%eax
0x0000555555401424 <+3>: sub %esi,%eax
0x0000555555401426 <+5>: mov %eax,%ebx
0x0000555555401428 <+7>: shr $0x1f,%ebx
0x000055555540142b <+10>: add %eax,%ebx
0x000055555540142d <+12>: sar %ebx
0x000055555540142f <+14>: add %esi,%ebx
0x0000555555401431 <+16>: cmp %edi,%ebx
0x0000555555401433 <+18>: jg 0x55555540143d <func4+28>
0x0000555555401435 <+20>: cmp %edi,%ebx
0x0000555555401437 <+22>: jl 0x555555401449 <func4+40>
0x0000555555401439 <+24>: mov %ebx,%eax
0x000055555540143b <+26>: pop %rbx
0x000055555540143c <+27>: retq
0x000055555540143d <+28>: lea -0x1(%rbx),%edx
0x0000555555401440 <+31>: callq 0x555555401421 <func4>
0x0000555555401445 <+36>: add %eax,%ebx
0x0000555555401447 <+38>: jmp 0x555555401439 <func4+24>
0x0000555555401449 <+40>: lea 0x1(%rbx),%esi
0x000055555540144c <+43>: callq 0x555555401421 <func4>
0x0000555555401451 <+48>: add %eax,%ebx
0x0000555555401453 <+50>: jmp 0x555555401439 <func4+24>

입력한 첫번째 정수를 a(0 <= a <= 14)라고 가정하면,
전달되는 인자는 R[%edx] = 14, R[%esi] = 0, R[%edi] = a 입니다.
우리는 a값을 통해서 리턴값이 7이 되도록 해야합니다.
<+1 ~ 5>
0x0000555555401422 <+1>: mov %edx,%eax
0x0000555555401424 <+3>: sub %esi,%eax
0x0000555555401426 <+5>: mov %eax,%ebx

<+7 ~ 14>
0x0000555555401428 <+7>: shr $0x1f,%ebx
0x000055555540142b <+10>: add %eax,%ebx
0x000055555540142d <+12>: sar %ebx
0x000055555540142f <+14>: add %esi,%ebx

<+7> : %ebx에 31번 오른쪽으로 shift합니다. 이는 %ebx의 부호를 추출한다고 이해할 수 있습니다.
<+10> : %ebx에 %eax를 더합니다.
<+12> : %ebx를 부호를 고려한 채 오른쪽으로 한번 shift합니다. 이는 %ebx를 2로 나눈것과 같습니다.
<+14> : %ebx에 %edi에 더합니다.
여기까지 계산한 식을 정리하면 오른쪽과 같습니다.
<+16 ~ 27>
0x0000555555401431 <+16>: cmp %edi,%ebx
0x0000555555401433 <+18>: jg 0x55555540143d <func4+28>
0x0000555555401435 <+20>: cmp %edi,%ebx
0x0000555555401437 <+22>: jl 0x555555401449 <func4+40>
0x0000555555401439 <+24>: mov %ebx,%eax
0x000055555540143b <+26>: pop %rbx
0x000055555540143c <+27>: retq
<+16> : R[%ebx]와 R[%edi]를 비교합니다.
<+18> : 만약 %ebx가 더 크면 <+28>로 점프합니다.
<+20> : 다시 비교합니다.
<+22> : 만약 %ebx가 더 작으면 <+40>으로 점프합니다.
<+24> : 크지도 않고 작지도 않으니, R[%ebx] == R[%edi] 입니다. 그러면 %ebx를 %eax에 넣어 return합니다.
<+28 ~ 50>
0x000055555540143d <+28>: lea -0x1(%rbx),%edx
0x0000555555401440 <+31>: callq 0x555555401421 <func4>
0x0000555555401445 <+36>: add %eax,%ebx
0x0000555555401447 <+38>: jmp 0x555555401439 <func4+24>
0x0000555555401449 <+40>: lea 0x1(%rbx),%esi
0x000055555540144c <+43>: callq 0x555555401421 <func4>
0x0000555555401451 <+48>: add %eax,%ebx
0x0000555555401453 <+50>: jmp 0x555555401439 <func4+24>
R[%ebx] > R[%edi]
- <+28> : R[%edx] = R[%rbx] - 1 을 진행합니다.
- <+31> : 코드의 처음으로 돌아가서 재귀호출합니다.
R[%ebx] > R[%edi]
- <+40> : R[%esi] = R[%rbx] + 1 을 진행합니다.
- <+34> : 코드의 처음으로 돌아가서 재귀호출합니다.
func4 결론
코드를 잘 보시면 이분탐색을 진행하는 코드임을 알 수 있습니다.
검색 범위는 0부터 14까지인데, %esi는 최소값을 담당하고 %edx를 담당합니다.
검색 대상은 우리가 입력한 첫번째 숫자인 %edi입니다.
그리고 %edx와 %esi의 중간 인덱스를 %ebx에 저장해서 그 값을 Target인 %edi와 비교해서 분기합니다.결론적으로 리턴값은 검색을 성공했을 때의 %ebx 입니다.
리턴값이 7이어야한다는건, 검색을 성공했을 때의 인덱스가 7이어야한다는겁니다.
또한 검색을 성공했다는건 R[%ebx] == R[%edi] 임을 의미하므로, 검색 대상인 첫번째 숫자가 7이어야함을 의미합니다.
인덱스와 그 값이 완전히 똑같은 배열에서 왜 이분탐색을 돌리는지는 의문이지만,
결론적으로 첫번째 숫자가 7, 두번째 숫자가 7이어야하므로 답은 다음과 같습니다.
7 7
'CS:APP' 카테고리의 다른 글
[CS:APP] BombLab Phase6 해설 (0) | 2023.10.20 |
---|---|
[CS:APP] BombLab Phase5 해설 (0) | 2023.10.20 |
[CS:APP] BombLab Phase3 해설 (0) | 2023.10.20 |
[CS:APP] BombLab Phase2 해설 (0) | 2023.10.19 |
[CS:APP] BombLab Phase1 해설 (0) | 2023.10.19 |