[CSAPP] BombLab (Phase 4)

결과 화면

진행 과정

<+0> ~ <+18> 스택 공간 확보, stack pointer로부터 4바이트 떨어진 주소를 %rdx에 로드하는데, 입력을 저장한다.

<+20> ~ <+35> sscanf로 사용자에게 입력받음. 지난 phase에서 입력 포맷을 알아냈던 방법과 같이 이번에도 %rsi에 저장된 주소의 값을 가져와서 확인함. 두 개의 정수를 입력해야하는 것을 알아냈다. 이는 스택에 쌓이고, 그후 %rsp는 두 번째 입력값을 가리키고 있을 것. (이때 %rdx에 첫 인자, %rcx에 두 번째 인자를 전달함을 잘 기억하자 앞에서 초기화할 때 phase_3과는 다르게 %rsp값을 %rcx에 복사했다. 주의)

<+40> ~ <+43> sscanf가 형식에 맞게 데이터를 추출하여 그 개수를 %eax에 저장하므로 값을 확인. 만약 2개가 아닐 경우 폭탄 터짐.

<+45> ~ <+54> 입력받은 두 번째 값을 %eax레지스터에 복사하고 2를 뺀다. 이를 2와 비교해서 그보다 작거나 같은 경우에 점프하여 다음 줄 폭탄을 피하므로, 또 jbe가 unsigned number를 비교하므로 두 번째 입력값은 3,4만 가능.

<+61> ~ <+69> %esi레지스터에 입력받은 두 번째 값을 복사하고, %edi 레지스터에 7을 넣은 후 func4함수를 호출한다. <+74>줄을 살짝 엿보니 %eax엔 func4의 반환값이 있어, 이 값이 첫 번째 인자와 일치해야 한다. func4 함수를 disassemble 해보자.

---

func4 코드 속에 func4가 너무 많다… 재귀호출인가보다…

<+0> 함수 반환값이 될 %eax레지스터 값을 0으로 초기화한다.

<+5> %edi가 자기자신을 AND연산, 이 값이 0이하인 경우(즉, %edi의 값이 0인 경우) zero flag 설정됨

<+7> jle(jump if less or equal) instruction은 zero flag와 sign flag기준으로 분기(%edi값이 0이거나 음수) <+16>으로 가라해서 가보면 계산된 결과를 반환하고 함수가 종료됨.

<+9> ~ <+14> %esi값을 %eax에 옮김. %edi가 1인지 확인 후 1이 아니라면 <+18>로 점프, 1이라면 <+16> 들어와서 return

<+18> ~ <+25> 현재 레지스터 값을 스택에 저장하고(나중에 복구할 것임. 얼리는 느낌으로…) 첫 번째 인자 값을 %r12d, 두 번째 인자 값을 %ebx로 옮김.

<+27> ~ <+30> %edi에서 1을 뺀 값을 다시 %edi에 저장, 재귀적으로 func4 호출함 (%edi가 1씩 감소하며 재귀 호출 진행)

문제 풀이의 갈피를 잡기 위해 재귀호출에서 반환된 경우를 가정하고 코드를 더 살펴보자.

<+35> ~ <+45> %edi에서 2뺀 값을 %edi에 저장하고, 원래의 첫 번째 인자 값을 %esi에 복원후 또 func4 호출하여 재귀호출 진행함. 1빼고 2빼서 재귀 돌리는게 피보나치 수열의 냄새가 난다.

<+50> ~ <+56> %eax 값에 %ebp 값을 더해주고, 얼려뒀던 stack을 pop하여 return한다.

이걸 어떻게 풀까? 지금까지 나온 조건은 첫 번째 정수의 값이 5 이상이라는 것, 두 번째 정수는 재귀호출을 후 반환한 값이어야 하는 것. 일단 5(함수 인자로는 2가 빠진 3이 전달될 것)를 일반성을 잃지 않고 가정하여 풀어나가보기로 했다. func4(int %edi, int %edx)라 했을 때 %edi가 0보다 작으면 0을 반환하고, 1이면 %esi를 반환하고. 나머지의 경우 base case에 도달할 때까지 재귀호출을 하고 return값을 다 더하는 것이니. 조금 생각을 해보자.

func4함수는 f(n,a)=f(n-1)+f(n-2)+a 형식을 갖고 있다 (n>1). 여기서 n은 첫 입력값-2이므로 3~5의 이상의 적절한 수를 넣고 재귀식을 잘 계산하면 다음과 같이 답이 나온다.

• 입력한 인자가 스택에 어떻게 저장되는지 이해하기 위해, stack pointer 개념을 잘 잡아야 한다…

정답

99 3 or 132 4