[CSAPP] BombLab (Phase 6)
결과 화면
진행 과정
코드 길이가 지금까지의 모든 phase중 가장 긴 것 같다. 보자마자 숨이 막혔다…
<+0> ~ <+24> register를 stack에 저장하여 현재 상태 보존하고 stack pointer를 0x68만큼 줄여 여러 변수와 데이터를 저장할 공간을 확보하는 전형적인 초기화 및 스택 설정 과정을 거친다.
<+26> ~ <+32> %rsp를 %r12에 저장하고 read_six_numbers라는 함수를 호출한다. 안봐도 6개 정수를 입력받겠구나 싶었다. 일단 이 함수를 disassemble 해보자.
다행히 이 친구는 그닥 길지 않다. 차근차근 살펴보자.
<+0> ~ <+29> 뭔가 비슷한 instruction들이 반복되는 것 같다. <+41>을 보니 sscanf함수가 호출되고, 이 형식을 확인해보니 역시나 여섯 개의 정수를 입력받았다. %rsi 값을 %rdx로 복사하는 것을 보니, %rsi는 메모리에서 배열이 시작하는 주소를 담았을 것 같다.
이제 계속 %rsi에서 0x4, 0x8, 0xc, 0x10, 0x14만큼 떨어진 값을 %rcx나 %rax에 load하고 일부는 stack에 push하고 있다. 입력된 6개의 정수값을 저장할 메모리상의 위치를 지정해주고 있다.
<+36> ~ <+41> 입력을 받기 위해 %eax를 초기화하고 sscanf 함수를 호출하여 6개의 정수를 입력받는다. 입력값이 저장될 위치는 다음과 같다.
+46> ~ <+60> %eax값을 통해 입력 개수를 검증하고(5개 이하이면 폭탄 터짐), stack pointer를 증가시켜 초기 상태를 복원하고, 종료 후 반환한다.
다시 phase_6 함수로 돌아왔다.
<+37> ~ <+43> %r13d를 0으로 초기화하고 <+82>로 점프
<+82> ~ <+95> %r12값에 %rsp값(사용자 입력이 저장된 메모리 주소)이 저장되어 있는데 이를 %rbp에 복사하므로 이는 입력된 값을 가리키는 포인터로 사용될 것이다.
(%r12)로 사용자가 입력한 첫 정수값을 가져와 %eax에 저장하고, %eax에서 1만큼 뺀 후 5와 값을 비교하여 5보다 크다면 폭탄을 만나러 가야한다(범위 Issue 피하기 위해 1빼고 unsigned 비교하는 ja 사용). ja instruction이 unsigned 비교를 함에 다시 유의하자. 사용자가 입력하는 모든 수는 1~6 범위 내에 있어야 한다.
<+97> ~ <+105> 첫 번째 입력 값이 5보다 작은 경우 %r13d에 1을 더하고, 6과 %r13d를 비교하여 값이 같으면 <+160>으로 분기하고 아닌 경우 %r13d 값을 %ebx에 복사한 후 <+60>으로 점프한다. 6개의 입력받은 정수에 대한 처리를 다 했는지 검증하는 부분이고, %r13d는 카운터 역할을 하겠다.
<+60> ~ <+69> 어떤 처리를 해줄까? movslq로 %ebx레지스터의 값을 64비트로 확장하여 %rax에 저장해준다. 현재 참조하는 값이 어디 있을지 나타내는 index 역할을 하겠구나. %eax에는 현재 사용자가 입력한 첫 번째 정수값이 저장되어 있는데, ‘%rsp + %rax * 4’의 주소에서 read_six_numbers로 입력받은 6개의 숫자 중 하나를 가져와서 %eax에 저장한다. 그리고 이 값과 %rbp에 있는 주소에 있는 값을 비교하여 같지 않으면 <+52>로 점프하고, 같을 경우 폭탄을 만난다. 여기서 입력받은 6개의 수 순서에서 같은 수가 연속되는 경우는 없다는 힌트를 얻을 수 있다.
<+52> ~ <+58> 폭탄을 만나고 싶지 않아 52로 점프했다. %ebx에 1을 더하고 5와 비교해서 5보다 크면 78로 점프하라는, 즉 입력값 6개에 대한 검증이 다 끝났는지 확인하는 부분을 다시 만났다. 이런 식으로 루프가 생기는구나. <+78> ~ <+105>까지 확인하고, 모든 값을 잘 입력했음을 가정하고 다음에 코드에서 어떤 일이 일어나는지 보기위해 <+160>으로 점프해보자.
<+160> %esi 값을 초기화하고 <+138>로 점프하래서 또 점프함.
<+138> ~ <+146> %rsp+%rsi*4의 주소에서 가져온 값을 %ecx에 저장한다. %eax값에 1을 복사하고 %rip에서 0x202bfe만큼 떨어진 주소를 %rdx에 넣어주는데, 옆에 # 0x204230
노드의 첫 번째 필드에는 8byte 값이, 다음 필드에는 다음 노드의 8byte 주소가 적혀있는 것 같다. 6개의 노드가 보여야 할 것 같은데 node6은 안보여서 node5의 두 번째 필드로 node6의 값까지 확보했다. 즉 node1~node6은 linked list 형태로 저장되어있음을 알 수 있다.
<+153> %ecx값이랑 1을 비교해서 %ecx가 더 크면 <+112>로 가고, 아니면 <+123>으로 가라고 한다. <+112>로 가봤다. (이 경우 첫 번째 입력 값은 2~6)
<+112> ~ <+121> %rdx에서 0x8만큼 떨어진 곳에 있는 값을 다시 %rdx에 저장하고(다음 노드 주소 가져와서 저장하는 격), %eax에 1을 더하고 %ecx와 %eax값을 비교해서 같지 않으면 다시 <+112>로 오는 루프이다. 이 루프는 사용자가 입력한 숫자에 해당하는 linked list의 node를 찾을 때까지 계속됨.
<+123> ~ <+136> 만약 같은 숫자를 찾았으면 <+123>에 도달함. %rsi에 1더하고 6이랑 비교해서 같으면 <+167>로 가라고 함. 같지 않으면 다시 <+138>로 이동하여 과정을 반복
<+167> ~ <+230> %rsp에서 일정 오프셋만큼 떨어져있는 값(노드가 저장되어있는 주소)을 메모리로 옮겨 써서 사용자가 입력한 값으로 linked list를 만든다. %ebp에 값 5를 복사하여 <+241>로 분기. (최종 %rax=6번째 입력값 노드 주소, %rbx=첫 번째 노드 입력값 주소, %rdx=5번째 노드 입력값 주소) (+원래 %rsp에서 0x20(%rsp)에 사용자가 입력한 첫 번째 숫자에 해당하는 노드 주소 ~ 8바이트씩 커지며 6번째 입력한 노드 주소까지 저장되어있음)
<+241> ~ <+251> %rbx가 가리키는 node의 다음 필드(다음 노드의 주소가 저장되어 있음)에서 가져온 값을 %rax에 저장하고, 이 값을 %eax에 옮기고, 이 값과 (%rbx)에 저장되어있는 값(현재 노드의 값)을 비교하여 %eax의 값이 현재 노드의 값보다 작거나 같을 경우 <+232>로 점프하고(루프 발견) 아닐 경우 폭탄을 만남. 여기서 내가 입력한 6개 수는 각각 노드의 번호를 의미할 것이고, 이들의 값이 내림차순이 되도록 수의 순서를 조정해야 함을 알 수 있음.
<+232> ~ <+239> 현재 노드의 next field를 읽어와 %rbx에 저장하고(현재 노드에서 다음 노드로 이동) %rbx가 다음 노드의 주소를 가리킴. %ebp는 아까 <+236>에서 5의 값을 넣어줬는데 하나씩 감소하는 것을 보니 역시 루프 카운터의 역할을 수행하고, 0이 될 때까지 노드 비교가 계속 일어날 것임을 알 수 있음.
다시 노드들의 상태를 나타내는 이 사진을 보자.
값은 node6 < node5 < node2 < node3 < node1 < node4 순서이다. 입력 값은 ‘4 1 3 2 5 6’이 되어야 한다.
<+258> ~ <+284> 스택 상태 확인 및 resource 정리 후 끝남.
정답
4 1 3 2 5 6
Leave a comment