[Bomb Lab] Phase 6, linked list operation의 assembly code

Read six numbers 함수

마지막 phase라서 그런지 assembly code 길이가 가장 길다. 풀이 순서대로 일부만 첨부하기로 한다. read_six_numbers 함수에서 유추할 수 있듯이, 사용자 입력으로 6개의 숫자를 넣어본다. 처음으로 분기가 있는 42줄에 breakpoint를 걸어둔다. 폭탄이 터지지 않고 실행을 이어가려면 jump가 일어나야 하고, eax 레지스터 값이 5보다 작거나 같아야 한다.

35줄에서 r13 레지스터 값을 base address로 하여 eax 레지스터에 값을 할당하므로, 이 주소를 찍어보았더니 입력했던 6개의 숫자가 들어있다. 즉, eax 레지스터에는 사용자 입력 1번째 숫자가 들어가고, 다시 1을 빼주므로, 1번째 숫자는 6 이하여야 한다는 결론을 얻는다.

 

일단 1 2 3 4 5 6 에서 1번째 숫자 조건은 우연히 맞았으므로, 실행을 이어가본다.

 

65~87줄: 입력 숫자를 0과 비교하는 반복문

다음 분기 지점인 71줄에 breakpoint를 걸어두고 실행을 이어갔다. 레지스터 r12는 0으로 초기화되어 있고, 52줄에서 1을 더한다. 68줄에서 eax 레지스터에는 2번째 입력 숫자가 저장된다. 71줄의 비교를 보면, 이 값이 0이 아니어야 하는데, 즉 2번째 입력 숫자가 1번째 숫자와 같지 않아야 한다라는 정보를 얻는다. 이번에도 우연히 맞았으므로 실행을 이어갈 수 있다.

 

81, 84, 87줄을 보면 반복 횟수가 5인 반복문임을 알 수 있다. 2~6번째 숫자가 1번째 입력과 같은지 여부를 차례로 검사하는 코드이다. 모두 달라야 무사히 넘어갈 수 있다. 이번에도 입력이 조건을 만족했으므로, 실행을 이어갈 수 있다.

 

반복문을 탈출하는 첫 지점인 89줄에 breakpoint를 걸어두고 실행을 이어가면 무사히 이어갈 수 있다.

 

Outer loop: 비교의 대상이 되는 숫자를 이동시킨다

그 전에는 1번째 숫자와 같은지 여부를 비교했다면, 89줄에서 rbp 레지스터 값을 4 증가시킴으로써 이제 2번째 숫자와 비교할 것임을 알 수 있다. 이제 assembly code를 분석해보면, 대략 다음과 같은 2중 loop이라는 결론을 얻는다.

코드를 assembly를 번역하는 느낌이다 보니 다소 부자연스러운 면은 있지만, 어쨌든 정리하자면 6개의 숫자는 6 이하의 값이어야 하며, 모두 다른 숫자여야 한다. 예시 입력 값이 이 조건을 만족시켰으므로, 2중 loop를 탈출한 95줄까지 무사히 수행된 것을 확인하였다.

 

이제 뒷 부분의 코드로 넘어가기로 한다.

반복문 108~121줄: 입력 값에 대한 연산

그 다음 반복문은 108~121줄이다. rax 레지스터는 1번째 입력을 가리키는 것으로 시작하고, 마지막 입력까지 가리키도록 이동한다. (114줄에서 rax 레지스터에 4씩 더한다.)

 

110줄을 보면 edx 레지스터에 7 - 기존 사용자 입력 을 저장하고, 이를 기존 사용자 입력이 저장된 위치에 저장한다. 즉, 사용자 입력 i를 7-i로 바꾼다는 것이다. 이제 스택 포인터가 가리키는 곳의 6개 연속된 숫자를 찍어보면, 7에서 뺀 값으로 대체된 것을 확인할 수 있다.

 

반복문: 130~181줄: 스택에 노드 순서 저장

163줄로 jump를 하게 되는데, 이번에도 반복문 단위로 살펴본다.

처음에 rsi 레지스터는 0으로 초기화되어 있다. ecx 레지스터에 7-a1 (a1: 1번째 입력값으로 표시하기로 한다.)을 할당하고 1보다 작거나 같은지를 검사한다.

 

지금 예시 입력 값에서는 그렇지 않으므로 169줄에서 jump하지 않고, 171줄이 수행된다. 176줄에서 edx에 상수 값을 할당하는데, 이 주소의 메모리를 찍어보면 <node 1>이라는 표시와 함께 332라는 숫자가 출력된다.

 

jump 이후에 수행하게 되는 130줄에 보면 rdx 레지스터 값을 (rdx+8) 주소의 메모리 값으로 바꿔주는데, 이를 출력해보면 <node 2>와 168이라는 숫자가 출력된다. 이를 통해 node라는 struct로 구성된 linked list가 있다는 것을 알 수 있다. 일단 이를 좀 따라가보면 아래와 같은 linked list를 얻는다.

ecx에 7-a1이 저장되어 있는데, 이 값의 크기만큼 linked list 노드를 건너뛴다. 예를 들어 지금은 ecx에 6이 들어있으므로, 6번 건너뛴 것이다. 그래서 141줄에 breakpoint를 찍은 뒤 rdx가 가리키는 값을 찍어보면 node 6이다. 148줄에서는 이 값을 메모리에 할당한다. base address가 rsp+32이고, 하나의 반복마다 offset이 8씩 증가한다. (rsi는 4씩 증가하는데, 곱하기 2를 해주므로.) 스택에 연이어 노드의 정보를 저장할 것임을 알 수 있다.

 

163줄에서 이제 ecx 레지스터에 7-a2를 할당하며 다음 반복을 수행한다. 분석을 이 정도로 해두고, 반복문이 종료되었을 때의 결과를 살펴보자. 이 때 rsp+32부터 어떤 값이 저장되어 있는지를 확인하면 된다.

여기까지를 정리해보면, 입력이 1 2 3 4 5 6이었는데, 입력 값을 7 - x로 바꿔주어서 6 5 4 3 2 1이 되었고, 이 값만큼 노드를 뒤로 이동시켜 스택에 저장해서 node 6, node 5, ... , node 1과 같은 순서로 저장이 되어 있다.

 

반복문 201~220줄: linked list 노드들의 연결 바꾸기

183, 188, 193줄에서는 주소 값을 레지스터에 저장하는데, mov, lea 명령어의 차이에 유의하여 잘 해석할 필요가 있다. 먼저, rbx 레지스터에는 rsp+32에 담겨있는 값, 즉 node 6의 주소 값을 저장한다. 한편, rax, rsi 레지스터는 각각 rsp+40, rsp+80을 저장하게 된다.

 

그리고 여기서 node에 대한 index notation을 정의해야 하는데, 코드 그대로의 node 1~6이 우리가 입력한 값에 따라 스택에는 다른 순서로 들어가게 된다. 스택 기준으로 셀 때는 스택 기준이라고 언급하기로 한다. 예를 들어 node 6은 스택 기준 1번째 node이다.

 

그 다음 반복문은 201~220줄임을 알 수 있고, 반복문 조건 검사는 212, 215줄이다. 204줄에서 rdx 레지스터에는 스택 기준 2번째 node의 주소 값이 들어 있다. 그리고 레지스터 rcx+8를 주소로 하는 메모리 값에는 스택 기준 1번째 node의 다음 노드 주소가 저장되어 있다. 스택의 순서와 기존 저장된 순서가 다를텐데, 이 명령어를 통해서 linked list의 연결을 스택 기준 순서로 바꾸어주는 것이다.

 

이번에도 반복문을 탈출한 직후인 222줄에 breakpoint를 걸고 linked list의 구조를 확인해보기로 한다.

rsp+32는 여전히 스택 기준 1번째 node를 가리키고 있다는 사실로부터, 스택 기준 1번째 node인 node 6의 주소를 얻어서 접근할 수 있다. 그리고, node 6에 연결된 노드를 offset 8을 더해 접근해보면 스택 기준 2번째 node였던 node 5이다. 즉, 이 반복문을 통해 입력한 숫자 순서대로 linked list의 연결을 바꾸어준 것이다.

 

222줄에서 rdx+8에 0을 넣어주는 것은 마지막 node는 다음 노드를 가리키지 않도록 하기 위함이다.

 

반복문 235~257줄:

235줄에서 rax 레지스터에는 스택 기준 1번째 노드의 next address를 저장한다. 현재 입력 기준으로는 node 5의 주소를 값으로 가진다. 이어서 239줄에서는 rax 레지스터 값을 주소로 하여 값을 읽어서 다시 eax 레지스터에 저장하고, 이는 스택 기준 2번째 node이자, node 5의 값이다. 241줄에서는 rbx 레지스터가 스택 기준 1번째 node를 가리키고 있으므로, 스택 기준 1, 2번째 node의 값을 비교한다. explode를 피하려면 jump가 일어나야 하고, 1번째 node가 더 크거나 같아야 한다.

 

이러한 반복을 2, 3번째, ... , 5, 6번째 node끼리 이어나간다. 즉, 스택 기준으로 node는 내림차순 정렬되어 있어야 한다.

 

node 3->4->5->6->1->2 순서로 스택에 저장되어야 한다. 그런데, 스택의 순서는 입력 기준 7-x와 같이 뒤바뀐 뒤 결정된다는 것을 고려하면 입력은 4, 3, 2, 1, 6, 5로 들어와야 한다.

 

이제 정답을 입력하면 모든 bomb lab을 성공적으로 통과할 수 있다.

 

이번 phase 6은 assembly code도 길고, 반복문이 많이 등장하여 시간이 오래 걸렸다. 다만, 반복문 하나에 해당하는 명령어의 수가 많지는 않으므로, 반복문 단위로 코드를 끊으며 이해하는 것이 요구되었다. 또한 linked list의 경우, 스택의 주소, 스택에 저장된 node의 주소, 다음 node의 주소 등 메모리 주소와 관련되어 헷갈리는 것이 많았다. 예를 들어, 스택을 통해 노드에 접근하려면 먼저 스택 포인터로 스택 값에 접근한 후, 그 값을 다시 주소로 하여 메모리에 접근해야 노드에 접근할 수 있는 구조이다.