[Bomb Lab] Phase 4, 재귀 함수 호출의 assembly code

Assembly Code of phase_4()

gdb를 켜고 bomb 실행 파일의 phase_4  함수를 disassemble해보면 다음과 같다.

24줄에 scanf 함수를 호출하는 부분이 보이는데, 이전 phase들의 경험을 토대로 생각해보면 뭔가 사용자 입력을 받는데, 여기서는 레지스터 eax가 2와 같을 때만 실행을 이어가므로 입력의 길이가 2여야 한다는 것을 알 수 있다.

 

입력은 완료된 뒤의 첫 번째 분기인 34줄에 breakpoint를 걸어본다. 임의로 1 2 3이라는 3개의 숫자를 입력으로 넣었는데, 폭탄이 터지지 않고 34줄까지 실행된다. 이 때의 레지스터 값들을 출력했을 때, 레지스터 eax의 값이 2인 것으로 보아 scanf 함수가 입력 2개가 되면 자동으로 종료되는 것으로 추측해볼 수 있다.

 

입력 값 2개는 스택에 저장되어 있다

34줄에서 비교의 대상이 되는 스택 포인터 + 8의 주소 값에 해당하는 메모리를 찍어보면 첫 번째 사용자 입력이 들어있으며, +12에는 두 번째 입력이 들어 있다. cmp 명령어와 jbe 명령어의 해석을 통해 1번째 입력에 대한 조건을 찾을 수 있다. x86 assembly가 처음일 때 비교의 순서가 헷갈리는데,

 

cmp operand b, operand a

 

는 a-b를 계산하여 flag들이 설정된다. 위의 명령어는

 

cmp 0xe(=14), 1st input

 

이고, jbe는 jump below or equal이므로, 1번째 input이 14보다 더 작거나 같을 때 jump가 일어난다는 뜻이다. 여기서는 jump가 일어나야 폭탄이 안 터지는 것이므로, 1번째 input의 조건은 14보다 작거나 같은 것이다.

 

func4 호출

60줄에서 func4 함수를 호출하고, 그 이전에 46, 51, 56줄의 세 번의 move 명령어를 통해 함수 argument 레지스터를 미리 설정해둔다. edx, esi, edi는 순서대로 함수의 3, 2, 1번째 argument이고 각각을

 

edx(=3번째 arg) = 14

esi(=2번째 arg) = 0

edi(=1번째 arg) = 1번째 입력

 

로 설정한다. 그리고 함수가 종료되었을 때를 먼저 보면, 65줄과 67의 분기에 의해 함수의 return 값이 저장되는 eax 레지스터가 0이어야 한다. 그렇지 않으면 76줄로 가서 폭탄이 터진다. 69, 74줄에서는 2번째 입력 값이 0인지를 비교하여 같을 때만 함수가 무사히 종료되는데, 이를 통해 2번째 입력 값이 0이어야 한다는 조건을 알 수 있다.

 

함수 func4가 아직 어떻게 생겼는지는 모르지만, 1번째 입력이 14 이하의 숫자여야 한다는 조건에 추가적으로 함수가 0을 return하도록 해야 한다.

 

이제 함수 func4가 어떻게 생겼는지를 살펴보자.

 

먼저 15줄의 sar 명령어에 operand가 1개만 있는 것이 좀 낯설어보이는데, 검색을 해보니 shift amount가 1인 경우 이와 같이 생략하여 표현하기도 한다고 한다. 아래 링크를 참고하였다.

링크: https://stackoverflow.com/questions/12813962/sar-command-in-x86-assembly-with-one-parameter

SAR command in X86 assembly with one parameter

func4는 재귀함수의 형태이다. 중간중간 분기문과 함께 다시 func4를 호출하는 부분이 있다.

func4: 재귀함수의 분석

func4는 parameter를 3개 받는다. 10줄의 명령어는 ecx 레지스터를 31-bit right shift하는 것인데, ecx 레지스터 자체가 32-bit 크기라는 것을 생각했을 때, MSB만 남긴다는 뜻(다른 관점에서는 0 또는 1)인데, phase 4를 푸는 과정에서 크게 중요하지는 않아서 그냥 0이라고 일단 두었다.

 

20줄에서 cmp 연산을 하기 전까지 arithmetic 명령어들을 통해 eax와 ecx 레지스터의 값을 조작한다. 22줄의 jle 명령어는 jump less or equal 이므로, jump가 일어나지 않는 조건은 ecx 레지스터 값이 edi 레지스터 값보다 큰 경우이다. 이 경우에는 재귀가 일어난다. 함수의 argument인 edx 레지스터를 바꿔주고(24줄), 재귀 호출을 하고(27줄), 종료된 뒤에는 eax 레지스터의 2배, 즉 재귀 호출했던 함수의 return 값의 2배를 return 하게 된다.

 

이제 36줄을 보면 여기서 eax 레지스터를 0으로 설정하는데, 이 값이 우리가 원하는 값이다. 다만, 41줄에서 다시 cmp, jump 명령어가 있어서 재귀 호출하는 부분이 있는데, cmp operand 대상이 20줄과 똑같은 것을 알 수 있다. 재귀 호출을 하는 조건은 ecx 레지스터 값이 edi 레지스터 값보다 작은 경우이다. 여기도 45, 48, 53줄에 걸쳐 비슷한 재귀 호출의 코드가 나타나는 것을 알 수 있다.

 

지금까지 정리한 내용을 c code 스타일로 나타낸 것은 다음과 같다.

재귀 호출이 일어나면서 어떤 동작을 하는지 구체적으로 따져보지는 않았지만, 여기서 원하는 것은 처음에 func4 함수를 호출했을 때 한 번도 재귀 호출이 안 일어나는 것이다. 그러면 바로 0을 return 할 것이다. assembly 명령어 level에서 보자면, ~22줄 -> 36~43줄 -> 57줄로 수행되는 것이다.

 

처음 함수를 호출했을 때, func4(1번째 입력, 0, 14)와 같이 호출된다. 이 때, edi는 1번째 입력, ecx는 14/2=7이다. 이 두 값이 같아야 하므로, 1번째 입력이 7이어야 한다.

 

사실, 재귀 함수 내부를 분석하지는 않았으므로, 재귀 함수 내에서 반복적으로 0만 return할 수도 있다. 다만, 여기서는 바로 재귀 호출을 피할 방법이 있으므로, 그렇게 하는 것이 문제의 의도일 것이다. 재귀 함수 자체도 식의 꼴이 깔끔하지는 않아서 그 내부 분석을 시킬 의도는 없어 보인다.

 

한 예로 10 0을 입력으로 준다면 아래와 같이 함수의 return 값이 5가 나온 것을 알 수 있다.

 

이제 구한 정답인 7 0을 입력해보면,

c 소스 코드에서 볼 수 있는 문자열이 출력되는 것을 확인할 수 있다.

 

재귀 함수 호출이 assembly level에서 어떻게 작성되는지 알 수 있었다. 함수의 argument 레지스터를 바꿔준 뒤, 함수를 호출하고, return 값 레지스터 eax를 활용해 다시 eax에 값을 할당함으로써 함수를 종료시키는 형태로 구성된다. phase 4를 해결하려면, 비교-분기 문에서 재귀 호출로 한 번도 안 들어가는 조건을 찾는 것이었다.