Lecture 09: Machine-Level Programming V: Advanced Topics

Memory Layout

---

x86-64 Linux Memory Layout

x86-64는 이론상 64비트까지의 주소를 가질 수 있지만, 실제로는 47비트만을 사용하므로 128TB의 메모리 공간을 나타낼 수 있다. (최대 0x7FFFFFFFFFFF)

Segment
Stack
↓
⋮
Shared libraries
↑
Heap
Data
Text
⋮

• 일반적으로 스택의 크기는 8MB이다.

  $ limit
  ⋮
  stacksize       8MB
  ⋮
  

  스택 포인터가 스택 바깥의 메모리에 접근하려고 하면 세그멘테이션 오류(segmentation fault)가 발생한다.

• 프로그램이 실행될 때, 디스크에 저장되어 있는 공유 라이브러리(Shared library)를 메모리에 로드한다. 이러한 과정을 동적 링킹(Dynamic linking)이라 한다.

• 힙(Heap)은 malloc()과 같은 함수를 통해 동적으로 할당되는 메모리 영역이다. 스택과 반대로, 주소가 높아지는 방향으로 공간을 할당한다.

• 데이터(Data) 영역에는 전역 변수들이 저장되며, 컴파일 타임에 그 크기가 결정된다.

• 텍스트(Text) 영역에는 실행 가능한 명령어들이 저장된다.

Memory Allocation Example

char big_array[1L<<24];   /* 16 MB */
char huge_array[1L<<31];  /*  2 GB */

int global = 0;

int useless() { return 0; }

int main() {
    void *p1, *p2, *p3, *p4;
    int local = 0;
    p1 = malloc(1L<<28);  /* 256 MB */
    p2 = malloc(1L<<8);   /* 256  B */
    p3 = malloc(1L<<32);  /*   4 GB */
    p4 = malloc(1L<<8);   /* 256  B */
    ⋮
}

Data	Address	Segment
local	0x7ffe4d3be87c	Stack
p1	0x7f7262a1e010	Heap
p3	0x7f7162a1d010	↓
p4	0x8359d120	↑
p2	0x8359d010	Heap
big_array	0x80601060	Data
huge_array	0x601060
main()	0x40060c	Text
useless()	0x400590

힙 영역을 보면 크기가 작은 것들은 낮은 주소에서부터, 큰 것들은 높은 주소에서부터 할당되는 것을 볼 수 있다. 지나치게 많은 할당 요청을 받으면, 양 쪽의 힙 영역이 서로 충돌하기에 이르러 할당에 실패하게 된다.

그 사이에 있는 메모리를 참조하려고 하면, 일반적으로 세그멘테이션 오류가 발생한다.

Buffer Overflow

---

앞서 경계 밖의 값에 접근하여 버퍼 오버플로(Buffer overflow)가 발생하는 예시¹를 본 적 있다. 이렇듯 C 프로그램에서는 엉뚱한 메모리를 참조하기 쉬우므로, 필요한 경우에 경계 검사를 수행하지 않으면 보안 취약점으로 이어질 수 있다.

String Library Code

할당된 버퍼보다 입력 문자열의 크기가 클 경우, 경계 검사 없이 문자열을 저장하는 라이브러리 함수들이 문제를 일으킬 수 있다. 다음은 표준 입력으로부터 문자열을 읽어 버퍼에 저장하는 라이브러리 함수 gets()이다.

char *gets()(char *dest) {
    int c = getchar();
    char *p = dest;
    while (c != EOF && c != '\n') {
        *p++ = c;
        c = getchar();
    }
    *p = '\0';
    return dest;
}

gets()를 포함한 코드를 컴파일하면 경고 메시지가 나타난다.

warning: the `gets' function is dangerous and should not be used.

gets()는 1970년대 UNIX의 초기 배포판이 나올 때 작성된 함수로, 보안에 대해 고려하지 않았다. strcpy(), strcat(), scanf() 등 문자열과 관련된 다른 라이브러리 함수들도 마찬가지이다.

Code Injection Attacks

void echo() {
    char buf[4];  /* Way too small! */
    gets(buf);
    puts(buf);
}

void call_echo() {
    echo();
}

echo()는 4바이트 크기의 버퍼를 가지고 있으며, gets()로 문자열을 입력받아 버퍼에 저장한 뒤 puts()를 통해 버퍼에 저장된 문자열을 출력한다.

00000000004006cf <echo>:
    4006cf:     48 83 ec 18             sub    $0x18,%rsp
    4006d3:     48 89 e7                mov    %rsp,%rdi
    4006d6:     e8 a5 ff ff ff          callq  400680 <gets>
    4006db:     48 89 e7                mov    %rsp,%rdi
    4006de:     e8 3d fe ff ff          callq  400520 <puts@plt>
    4006e3:     48 83 c4 18             add    $0x18,%rsp
    4006e7:     c3                      retq

00000000004006e8 <call_echo>:
    4006e8:     48 83 ec 08             sub    $0x8,%rsp
    4006ec:     b8 00 00 00 00          mov    $0x0,%eax
    4006f1:     e8 d9 ff ff ff          callq  4006cf <echo>
    4006f6:     48 83 c4 08             add    $0x8,%rsp
    4006fa:     c3                      retq

-fno-stack-protector 옵션과 함께 컴파일되었다.

그런데 어셈블리 코드를 확인해 보면, 스택에 24바이트의 공간이 할당되어 버퍼로 사용되는 것을 알 수 있다. 프로그램 실행 후 스택의 처음 상태는 다음과 같다.

Content
Stack frame for call_echo()
Return address 0x4006f6 (8 bytes)
Unused (20 bytes)
buf (4 bytes)	← %rsp

여기에 23개의 문자를 입력하면, \0 문자를 포함하여 할당된 24바이트 전체를 사용하게 된다. 이론적으로 버퍼 오버플로에 해당하지만, 실제로는 20바이트의 추가 공간이 있으므로 문제가 되지 않는다. 하지만 24개 이상의 문자를 입력하면, 반환 주소 영역을 침범하여 반환 주소의 바이트 표현이 손상된다.

이러한 원리를 이용해 익스플로잇(exploit) 코드를 삽입하고 반환 주소를 조작함으로써 삽입한 코드를 실행하는 공격을 코드 인젝션(Code injection)이라 한다.

• Morris Worm (1988)²
• Chat Wars (1999)³

Avoid Overflow Vulnerabilites in Code

최대 입력 크기를 지정하는 함수를 사용함으로써 버퍼 오버플로를 방지할 수 있다.

void echo() {
    char buf[4];  /* Way too small! */
    fgets(buf, 4, stdin);
    puts(buf);
}

• gets() → fgets()
• strcpy() → strncpy()
• strcat() → strncat()
• scanf()를 %s와 함께 사용할 때, %4s와 같이 폭(width)을 지정하여 입력 크기를 제한할 수 있다.

System-Level Protections

시스템에도 버퍼 오버플로에 대한 각종 보호 장치가 내장되어 있다. 그 중 하나는 ASLR(Address Space Layout Randomization)로, 프로그램이 실행될 때마다 스택, 힙과 같은 주요 메모리 영역의 시작 주소를 무작위화하여 공격자가 찾기 어렵게 만든다.

static void show_pointer(void *p, char *descr) {
    printf("%s\t%p\n", descr, p);
}

int global = 0;

int useless() { return 0; }

int main ()
{
    void *p1, *p2, *p3, *p4;
    int local = 0;
    void *p = malloc(100);
    show_pointer((void *)&local, "local");
    show_pointer((void *)&global, "global");
    show_pointer((void *)p, "heap");
    show_pointer((void *)useless, "code");
    return 0;
}

$ ./a.out
local   0x7ffe6c6942fc
global  0x60102c
heap    0x1f5a010
code    0x400590
$ ./a.out
local   0x7ffd66ca9bfc
global  0x60102c
heap    0xcea010
code    0x400590
$ ./a.out
local   0x7ffe54cc7ddc
global  0x60102c
heap    0x11f4010
code    0x400590

프로그램을 실행할 때마다 스택과 힙에 할당된 주소가 매번 바뀌는 것을 볼 수 있다.

또 하나의 안전 장치는 NX(Never eXecute) 비트이다. UNIX 파일의 접근 권한처럼, 각 메모리 영역에도 접근 권한을 나타내는 비트 플래그가 존재한다. 과거에는 읽기/쓰기 플래그만이 존재하여 읽기 권한이 있으면 실행 또한 가능했으나, 실행 권한을 나타내는 3번째 비트(NX 비트)가 추가되며 읽기 권한과 실행 권한이 분리되었다. NX 비트를 이용해 주요 메모리 영역을 실행 불가능하게 만듦으로써, 삽입한 코드를 실행해야 하는 코드 인젝션 공격을 방지한다.

Stack Canaries

탄광의 카나리아에서 유래한 이름으로, 카나리아 값(Canary value)을 버퍼 바로 위에 배치하여 함수가 종료될 때 카나리아 값이 변경되었는지 검사한다.

• 카나리아 값은 실행할 때마다 달라진다.
• 문자열에서 널 문자에 대한 공간을 할당하지 않는 경우를 대비해, 최하위 바이트가 항상 0이다.
• GCC에 -fstack-protector 옵션으로 구현되어 있으며, 기본적으로 활성화되어있다.

이번에는 echo()를 -fno-stack-protector 옵션 없이 컴파일해 보자.

echo:
        subq    $24, %rsp
        movq    %fs:40, %rax      ; Get canary
        movq    %rax, 8(%rsp)     ; Place on stack
        xorl    %eax, %eax        ; Erase canary
        movq    %rsp, %rdi
        call    gets
        movq    %rsp, %rdi
        call    puts
        movq    8(%rsp), %rax     ; Retrieve from stack
        xorq    %fs:40, %rax      ; Compare to canary
        je      .L6               ; If same, OK
        call    __stack_chk_fail  ; FAIL
.L6:
        addq    $24, %rsp
        ret

스택 포인터로부터 8바이트 높은 주소에 카나리아 값을 저장한 뒤, 반환 전에 카나리아 값을 검사하여 값이 다르면 오류 메시지를 출력하는 것을 확인할 수 있다.

Return-Oriented Programming Attacks

ASLR은 텍스트 영역을 대상으로 하지는 않기 때문에, 스택이나 힙의 위치를 모르더라도 명령어들의 위치는 알 수 있다. 이를 이용해 가젯(Gadget), 즉 기존에 존재하는 명령어들을 연결하여 공격을 수행하는 것을 반환 지향형 프로그래밍(Return-Oriented Programming, ROP)이라 한다. 각 가젯은 명령어의 시퀀스이며, ret 명령어를 의미하는 바이트 값 0xc3으로 끝난다.

long ab_plus_c(long a, long b, long c) {
    return a * b + c;
}

000000000000112d <ab_plus_c>:
    112d:       48 0f af fe             imul   %rsi,%rdi
    1131:       48 8d 04 17             lea    (%rdi,%rdx,1),%rax
    1135:       c3                      ret

가젯의 주소가 0x1131이라면, lea 명령어부터 수행하므로 %rdi와 %rdx의 값을 더하여 %rax에 저장한다.

void setval(unsigned *p) {
    *p = 3347663060u;
}

000000000000112d <setval>:
    112d:       c7 07 d4 48 89 c7         movl   $0xc78948d4,(%rdi)
    1133:       c3                        ret

가젯의 주소가 0x1130이라면, 48 89 c7 부분부터 수행한다. 이는 movq %rax, %rdi를 의미하므로, %rax의 값을 %rdi에 복사한다. 이처럼 원래 코드와 아무 관련도 없지만, 특정 바이트 패턴과 일치하는 가젯도 존재한다.

Unions

---

Union Allocation

union U1 {
    char c;
    int i[2];
    double v;
} *up;

공용체(Union)는 구조체와 마찬가지로 다양한 타입의 필드를 가질 수 있지만, 크기가 가장 큰 필드에 대해서만 저장 공간을 할당하여 모든 필드가 공유한다.

Offset	0	1	2	3	4	5	6	7	8
Data	c	끝
	i[0]	—	—	→	i[1]	—	—	→	끝
	v	—	—	—	—	—	—	→	끝

공용체의 사용 목적은 여러 값을 다루기 위한 것이 아니라, 메모리를 다양한 방식으로 참조할 수 있도록 별칭을 생성하는 것이다.

typedef union {
    float f;
    unsigned u;
} bit_float_t;

float bit2float(unsigned u) {
    bit_float_t arg;
    arg.u = u;
    return arg.f;
}

이는 (float)u와 같은 형 변환과는 근본적으로 다른 작업이다. 형 변환 시 실제로 비트 값이 바뀌지만, 공용체는 동일한 비트 값을 달리 해석할 뿐이기 때문이다.

Byte Ordering Example

공용체가 포함된 코드는 실행 환경의 바이트 순서⁴에 따라 다른 결과를 얻을 수 있음에 주의해야 한다.

union {
    unsigned char c[8];
    unsigned short s[4];
    unsigned int i[2];
    unsigned long l[1];
} dw;

for (int j = 0; j < 8; j++)
    dw.c[j] = 0xf0 + j;

printf("Characters 0-7 == [%#x, %#x, %#x, %#x, %#x, %#x, %#x, %#x]\n",
        dw.c[0], dw.c[1], dw.c[2], dw.c[3],
        dw.c[4], dw.c[5], dw.c[6], dw.c[7]);
printf("Shorts 0-3 == [%#x, %#x, %#x, %#x]\n",
        dw.s[0], dw.s[1], dw.s[2], dw.s[3]);
printf("Ints 0-1 == [%#x, %#x]\n", dw.i[0], dw.i[1]);
printf("Long 0 == [%#lx]\n", dw.l[0]);

리틀 엔디언 환경:

$ ./little-endian
Characters 0-7 == [0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7]
Shorts 0-3 == [0xf1f0, 0xf3f2, 0xf5f4, 0xf7f6]
Ints 0-1 == [0xf3f2f1f0, 0xf7f6f5f4]
Long 0 == [0xf7f6f5f4f3f2f1f0]

빅 엔디언 환경:

$ ./big-endian
Characters 0-7 == [0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7]
Shorts 0-3 == [0xf0f1, 0xf2f3, 0xf4f5, 0xf6f7]
Ints 0-1 == [0xf0f1f2f3, 0xf4f5f6f7]
Long 0 == [0xf0f1f2f3f4f5f6f7]

References

---

• Carnegie Mellon University. (2015). Lecture 09: Machine-Level Programming V: Advanced Topics. [Online].

Footnote

1. “Lecture 01: Course Overview.” 고양이 볼따구. [Online]. ↩

2. E. H. Spafford. “The Internet Worm Program: An Analysis.” Purdue Univ., Tech. Rep. CSD-TR-823, 1988. [Online]. ↩

3. D. Auerbach. “Chat Wars.” n+1. [Online]. ↩

4. “Lecture 03: Bits, Bytes, and Integers (cont.).” 고양이 볼따구. [Online]. ↩