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

phase_4

func4

__isoc99_sscanf

__isoc99_sscanf

phase2에서 __isoc99_sscanf 함수에 알아낸 사실들을 정리하면 다음과 같습니다.

  1. 입력한 정수가 %rdi에서 저장된 문자열에서 배열형태로 변환됩니다.
  2. 첫번째 원소를 가리키는 포인터가 %rsp에 저장됩니다.
  3. 입력한 정수의 개수를 %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를 분석하기 전에 우리가 문제를 해결하기위해 필요한 조건들을 정리해보겠습니다.

 

  1. 입력한 첫번째 숫자는 0 이상 14 이하를 만족해야한다.
  2. 입력한 두번째 숫자는 7 이어야 한다.
  3. %edx, %esi, %edi가 인자로 전달되며 그 값들은 다음과 같습니다. R[%edx] = 14, R[%esi] = 0, R[%edi] = 입력한 첫번째 정수
  4. 리턴값이 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

+ Recent posts

티스토리툴바