BombLab - Phase 6

beans_I·2024년 3월 6일
0

[23-2] 시스템 프로그래밍 

목록 보기
6/6

Phase6

Phase 6의 핵심은 사용자가 입력한 순서에 따라 미리 정의된 연결 리스트의 순서를 재배열하고, 재배열된 리스트가 특정 조건(내림차순 정렬)을 만족하는지 검사하는 과정을 역추적하는 것이다.

1. 초기 설정 및 입력

phase_6가 시작되면, 먼저 사용자 입력을 받고 검증을 위한 초기 설정을 진행한다.

  • <+28> ~ <+31>: mov %rsp, %r13와 mov %r13, %rsi를 통해 스택 포인터(%rsp)의 주소를 %r13과 %rsi에 복사한다.
  • <+34>: callq <read_six_numbers>를 호출하여 6개의 정수를 입력받는다. 입력된 정수들은 %rsi가 가리키는 스택 위치부터 순서대로 저장된다.
  • <+39> ~ <+46>: %r12에 스택 시작 주소를 저장하고, 바깥쪽 루프의 카운터로 사용할 %r14d를 0으로 초기화한 뒤, <+87>로 점프한다.

2. 이중 반복문을 통한 입력값 검증

이 단계의 핵심은 이중 반복문을 통해 사용자가 입력한 6개의 숫자가 1에서 6 사이의 중복되지 않는 정수인지를 검사하는 것이다.

바깥쪽 루프

이 루프는 입력된 6개의 숫자를 순서대로 하나씩 검사 대상으로 선택한다.

 <+90>          : %eax = *(r%13)
 <+94>          : %eax -= 1
 <+97>,<+100>   : if %eax > 5 then <explode_bomb>
 <+102>         : ％r14d += 1
 <+106>, <+110> : if %r14d == 6 then goto<+117>
 <+112>         : %ebx = %r14d
 <+115>         : goto <+65>
  • <+87> mov %r13, %rbp: 현재 검사할 숫자의 주소(%r13에 저장된 값, 초기 루프 진입 기준 %rsp에 저장된 값)를 %rbp에 저장한다.
  • <+90> ~ <+100>: (조건 1: 범위 검사) 현재 검사 중인 숫자((%r13))가 1에서 6 사이의 값인지 확인한다. 만약 (값 - 1)이 5보다 크면(ja 명령어), 즉 값이 1~6 범위를 벗어나면 폭탄이 터진다.
  • <+102> ~ <+110>: 바깥쪽 루프의 카운터 %r14d를 1 증가시키고, 6개의 숫자를 모두 검사했는지 확인한다.
  • <+115> jmp <phase_6+65>: 안쪽 루프로 진입한다.

안쪽 루프

안쪽 루프는 바깥쪽 루프에서 선택된 하나의 숫자가 배열 내 다른 숫자들과 중복되는지 검사한다.

<+65>       : %rax = %ebx //signed extension, %ebx = %r14d
<+68>       : %eax = *(4*(%rax)+%rsp)
<+71>/<+74> : if %*(rbp) != %eax then goto <+57>
<+76>       : <explode_bomb>
<+57>       : %ebx += 1 // 원래 이전 주소의 명령어지만, 이해를 위해 여기에 작성함
<+60>/<+63> : if %ebx>5 then goto <+83>
// 이어서 <+65> 다시 실행
  • <+65> ~ <+68>: 안쪽 루프의 카운터 %ebx를 이용해 비교할 다른 숫자의 값((%rsp + %rax*4))을 가져온다.
  • <+71> ~ <+76>: (조건 2: 중복 검사) 바깥쪽 루프에서 선택된 숫자(%rbp)와 안쪽 루프에서 선택된 다른 숫자가 같은지 비교한다. 만약 두 값이 같다면(jne가 실행되지 않으면) 중복된 것이므로 폭탄이 터진다.
  • <+57> ~ <+63>: 안쪽 루프의 카운터 %ebx를 1 증가시키고, 모든 비교를 마쳤는지 확인한다.

다음 숫자로 이동

<+83> %r13 += 4
// 이어서 <+87> 실행
  • <+83> add $0x4, %r13: 하나의 숫자에 대한 범위 및 중복 검사가 모두 끝나면, 포인터 %r13을 4바이트 증가시켜 다음 입력 숫자를 가리키게 한다.
  • <+87>: 다시 바깥쪽 루프의 시작점으로 돌아가 다음 숫자 검사를 계속한다.

이러한 이중 루프 구조를 통해, 프로그램은 입력된 6개의 모든 숫자가 1~6 사이의 고유한 값인지 철저히 검증한다. 따라서 이 단계를 통과하기 위한 첫 번째 조건은 다음과 같이 정리할 수 있다.

정답 조건:
[ 1에서 6 사이의 중복되지 않는 정수 6개를 입력 ]

3. 입력값 변환 (x -> 7-x)

첫 번째 입력값 검증을 통과하면, <+117>부터 <+144>까지의 반복문을 통해 입력된 6개의 숫자를 새로운 값으로 변환하는 작업을 루프문을 돌면서 수행한다.

루프 설정

<+117>: %rcx = (%r12+24) // <+34> -> %r12 = %rsp, 따라서 마지막 입력 정수의 다음 주소
<+122>: %edx = 7
<+127>: %eax = %edx
<+129>: %eax -= *(%r12) // 최초 진입 시, %eax = 7- ‘첫 번째 입력 정수’ <+133> *(%r12) = %eax
<+137>: %r12 += 4 // 다음 입력한 정수로 이동
<+141>, <+144>: if %r12 != %rcx then goto <+127>
  • <+117> lea 0x18(%r12),%rcx: %rcx에 루프의 종료 지점(마지막 입력 정수의 다음 주소)을 저장한다.
  • <+122> mov $0x7,%edx: 변환에 사용할 상수 7을 %edx에 저장한다.

루프 본문

이 루프는 %r12 포인터를 이용해 6개의 입력값을 순회하며 다음 연산을 수행한다.

  • <+129> sub (%r12),%eax: %eax에 저장된 7에서 현재 포인터(%r12)가 가리키는 입력값 x를 뺀다 (7 - x).
  • <+133> mov %eax,(%r12): 위에서 계산된 7 - x 값을 원래의 메모리 위치에 덮어쓴다.
  • <+137> add $0x4,%r12: 포인터 %r12를 4바이트 증가시켜 다음 입력값을 가리키게 한다.
  • <+144> jne <+127>: 포인터가 루프 종료 지점에 도달하지 않았으면 루프의 처음으로 돌아간다.

이 과정을 통해, 사용자가 입력했던 6개의 숫자는 (7 - 원래 숫자)라는 규칙에 따라 모두 새로운 값으로 변환된다. 예를 들어, 1 2 3 4 5 6을 입력했다면 이 단계가 끝난 후 메모리에는 6 5 4 3 2 1이 저장된다.

4. 연결 리스트 노드 매핑

입력값 변환이 끝나면, <+146>부터 <+199>까지 이어지는 복잡한 반복문을 통해 변환된 숫자와 사전에 작성된 연결 리스트의 노드를 연결하는 작업을 수행한다.

이 코드의 전체적인 목적은 변환된 숫자 [n1, n2, n3, n4, n5, n6] 순서에 맞춰, 각 숫자에 해당하는 <node_n1>, <node_n2>, ... 의 메모리 주소를 찾아 스택의 새로운 배열에 저장하는 것이다.

반복문 진입

  • <+146> ~ <+151>: %esi을 0으로 초기화한 뒤, <+179>로 분기한다.

1) 메인 루프 시작 (구간 A)

<+179> ~ <+199> 구간은 6번 반복되는 메인 루프의 시작점이다. 각 반복마다 현재 순서에 해당하는 변환된 값을 가져와서, 이 값이 1보다 큰지 확인한다. 이 값에 따라 중첩 루프를 실행할지 건너뛸지를 결정한다.

<+179> %ecx = *(4*(%rsi)+%rsp)
<+182> %eax = 1
<+187> %rdx = 0x555555604230 //<node1>의 주소. 이게 뭔지는 좀있다 보자.
<+194>~<+197> if %ecx > 1 then goto <+153><+199> goto<+164>
  • <+179>: 현재 순서(%rsi)에 해당하는 변환된 값을 %ecx에 가져온다.
  • <+187>: 포인터 %rdx를 연결 리스트의 시작인 <node1>의 주소로 초기화한다. GDB를 이용해 이 주소부터 메모리를 분석하면, 각 노드가 다음과 같은 규칙적인 구조를 가짐을 알 수 있다.
    • 0x0 ~ 0x3 (4바이트): 노드가 가진 고유의 값
    • 0x4 ~ 0x7 (4바이트): 노드의 인덱스 (1~6)
    • 0x8 ~ 0xf (8바이트): 다음 노드를 가리키는 포인터
  • <+194> ~ <+197>: 변환된 값이 1보다 큰지 확인한다.
    • 값이 1인 경우: <node1>을 찾아야 하므로 이미 %rdx에 올바른 주소가 있다. 따라서 중첩 루프(구간 B)를 건너뛰고 바로 저장 단계(구간 C)로 간다.
    • 값이 1보다 큰 경우: n번째 노드를 찾기 위해 중첩 루프(구간 B)로 진입한다.

2) 중첩 루프: 노드 탐색 (구간 B)

<+153> ~ <+162> 구간은 중첩 루프에 해당한다. 변환된 값이 1보다 클 때만 실행되며, 연결 리스트의 시작(<node1>)부터 next 포인터를 따라가며 목표한 <node_n>을 찾는 역할을 한다.

<+153> %rdx = *(%rdx+8)
<+157> %eax += 1 // <+182>에서 1로 초기화
<+160>, <+162> if %eax != %ecx then goto +153 // <+179>
  • <+153>: %rdx = *(%rdx+8) 명령어를 통해 연결 리스트의 다음 노드로 이동한다.
  • <+157> ~ <+162>: 카운터(%eax)를 1씩 증가시키며, 목표한 n번째 노드를 찾을 때까지(즉, 카운터가 n이 될 때까지) 노드 이동을 반복한다.
  • 이 루프가 끝나면 %rdx는 목표한 <node_n>의 주소를 정확히 가리키게 된다.

3) 결과 저장 및 메인 루프 반복 (구간 C)

<+164> ~ <+177> 구간은 노드 탐색이 끝난 후 실행된다. 찾아낸 노드의 주소를 스택의 새로운 배열에 저장하고, 메인 루프의 카운터(%rsi)를 1 증가시킨 뒤, 6번의 반복이 끝났는지 확인하여 다음 반복으로 넘어가거나 전체 루프를 종료한다.

<+164> *(8*(%rsi)+%rsp+32) = %rdx
<+169> %rsi += 1
<+173>/<+177> if %rsi == 6 then goto <+201>
// <+179>부터 다시 시작.
  • <+164>: 찾아낸 노드의 주소(%rdx)를 스택에 새로 만드는 포인터 배열 (%rsp + 32 + %rsi * 8) 위치에 저장한다.
  • <+169>: 메인 루프 카운터 %rsi를 1 증가시킨다.
  • <+173> ~ <+177>: 6개의 숫자를 모두 처리했는지 확인하고, 그렇지 않으면 다시 메인 루프의 시작(<+179>)으로 돌아간다.

이 과정을 통해 스택에 새로운 포인터 배열이 어떻게 만들어지는지 구체적인 예시로 확인할 수 있다.사용자 입력값에서 변환된 숫자 배열이 [3, 1, 2, 4, 5, 6]이라고 가정하자.

  1. 첫 번째 반복 (%rsi=0, 변환값=3): 3 > 1이므로 중첩 루프가 실행된다. 포인터는 <node1>에서 시작하여 next를 두 번 따라가 <node3>에 도달한다. 스택의 첫 번째 위치 (%rsp+32)에 <node3>의 주소가 저장된다.
  2. 두 번째 반복 (%rsi=1, 변환값=1): 1 > 1이 아니므로 중첩 루프를 건너뛴다. 포인터는 <node1>에 머무른다. 스택의 두 번째 위치 (%rsp+40)에 <node1>의 주소가 저장된다.
  3. 세 번째 반복 (%rsi=2, 변환값=2): 2 > 1이므로 중첩 루프가 실행된다. 포인터는 <node1>에서 next를 한 번 따라가 <node2>에 도달한다. 스택의 세 번째 위치 (%rsp+48)에 <node2>의 주소가 저장된다.

이 과정을 6번 반복하면, 스택에는 최종적으로 [<node3> 주소, <node1> 주소, <node2> 주소, <node4> 주소, <node5> 주소, <node6> 주소]가 순서대로 저장된다. 이 포인터 배열은 다음 단계인 연결 리스트 재배열에 사용된다.

4. 연결 리스트 재배열

이전 단계에서 스택에 생성한 노드 포인터 배열을 기반으로 <+201>부터 <+251>까지의 코드를 통해 기존 연결 리스트의 next 포인터를 재연결한다.

  • <+201> ~ <+211>: 스택에 저장된 첫 번째 노드 포인터와 두 번째 노드 포인터를 각각 %rbx와 %rax에 로드한다. 그리고 mov %rax, 0x8(%rbx) 명령어를 통해 첫 번째 노드의 next 포인터가 두 번째 노드를 가리키도록 수정한다.

이러한 mov 명령어 쌍이 <+251>까지 반복되어, 스택에 저장된 순서대로 6개 노드의 next 포인터가 모두 재연결된다. 결과적으로, 원래 <node1> → <node2> → ... → <node6> 순서였던 연결 리스트는 사용자의 입력값에 따라 완전히 새로운 순서로 재배열된다. 예를 들어, 사용자 입력값에서 변환된 숫자 배열이 3 1 2 4 5 6이었다면, 재배열된 연결 리스트의 순서는 <node3> → <node1> → <node2> → <node4> → <node5> → <node6>가 된다.

5. 검증

마지막으로, 프로그램은 <+275>부터 재배열된 연결 리스트가 올바른 순서인지 검증하는 루프를 실행한다.

검증 로직 분석

  • <+275>: 현재 노드(%rbx)의 next 포인터 값을 %rax에 저장한다. 즉, %rax는 다음 노드의 주소를 가리킨다.
  • <+279>: 다음 노드의 주소(%rax)에 저장된 값을 %eax로 가져온다.
  • <+281>: 현재 노드의 값((%rbx))과 다음 노드의 값(%eax)을 비교한다.
  • <+283>: 비교 결과, 현재 노드의 값이 다음 노드의 값보다 크거나 같으면(jge: Jump if Greater or Equal) 루프의 다음 단계로 안전하게 분기한다. 만약 현재 노드의 값이 더 작으면 폭탄이 터진다.

즉, 바로 재배열된 연결 리스트가 노드의 값을 기준으로 내림차순으로 정렬되어 있어야 한다.

루프제어

  • <+266>: 현재 노드를 다음 노드로 이동시킨다 (rbx = rbx->next).
  • <+270>: 루프 카운터 %ebp를 1 감소시킨다.
  • <+273>: 카운터가 0이 되면(je: Jump if Equal) 루프를 종료하고 폭탄 해체 지점으로 점프한다. 그렇지 않으면 다시 <+275>로 돌아가 다음 노드 쌍을 비교한다.

6. 종합하자면…

지금까지의 모든 분석을 종합하면, Phase 6의 전체 요구 조건은 다음과 같이 정리된다.

  1. 1~6 사이의 중복되지 않는 정수 6개를 입력한다.
  2. 입력된 각 숫자 x는 내부적으로 7 - x로 변환된다.
  3. 프로그램은 이 변환된 숫자 순서에 맞춰 연결 리스트를 재배열한다.
  4. 재배열된 연결 리스트는 반드시 각 노드의 값을 기준으로 내림차순 정렬되어 있어야 한다.

이 모든 조건을 만족하는 유일한 입력값을 찾기 위해, 마지막 4번 조건부터 과정을 역으로 추적해보자. 먼저, 각 노드의 고유 값을 기준으로 내림차순 정렬하여 최종적으로 만들어져야 할 노드의 순서를 결정한다.

노드 이름노드 값정렬 순서
<node4>0x351 (849)1
<node3>0x303 (771)2
<node5>0x1eb (491)3
<node1>0x120 (288)4
<node2>0x66 (102)5
<node6>0x4a (74)6

번외) 빠른 풀이 전략

만약에 시간이 부족하거나 빠르게 풀어야 한다면은, node값들을 확인 후 다음 4가지 케이스에 대해 입력을 진행하면 된다.

  1. 입력값 x 순서가 노드 값의 오름차순이 되도록 하는 경우
  2. 입력값 x 순서가 노드 값의 내림차순이 되도록 하는 경우
  3. 7-x 순서가 노드 값의 오름차순이 되도록 하는 경우
  4. 7-x 순서가 노드 값의 내림차순이 되도록 하는 경우

우선적으로 맞춘 다음, 풀이를 진행하면 된다.

profile
beans_I
노션으로 옮겼습니다. https://beans-i.notion.site/main?pvs=74
이전 포스트

BombLab - Phase 5

0개의 댓글