[CSAPP] Ch 3. 프로그램의 기계수준 표현 : (9) 이기종 자료구조, (10) 기계수준 프로그램에서 제어와 데이터의 결합

  3.9 이기종 자료구조

 

  C는 서로 다른 유형의 객체를 연결해서 자료형을 만드는 두 가지 방법을 제공한다.

    (1) 구조체 : struct 키워드를 사용해서 선언, 다수의 객체를 하나의 단위로 연결

    (2) 공용체 : union 키워드로 선언, 하나의 객체를 여러 개의 다른 자료형으로 참조될 수 있도록 함

 

 

  3.9.1  구조체

 

  C struct 선언은 서로 다른 유형의 객체들을 하나의 객체로 묶어주는 자료형을 생성한다. 하나의 구조체 내의 서로 다른 컴포넌트들은 이름을 이용해서 참조된다. 구조체의 구현은 구조체의 모든 컴포넌트들이 메모리의 연속된 영역에 저장되며, 구조체의 포인터가 첫 번째 바이트의 주소라는 점에서 배열과 유사하다. 컴파일러는 각 필드의 byte offset을 가리키는 각 구조체 유형에 관한 정보를 관리하며, 메모리 참조 인스트럭션의 변위로 이 오프셋을 사용하여 구조체 원소 참조를 생성한다.

 

  일례로, 다음의 구조체 선언을 살펴보자.

struct rec {
    int i;
    int j;
    int a[2];
    int *p;
};

 

  이 구조체는 네 개의 필드를 갖는다. 두 개의 4byte 정수, 두 개의 4byte 정수로 이루어진 배열, 8byte 정수형 포인터, 총 24byte.

  배열 a가 구조체에 들어 있는 점에 주목해보자. 그림 상단에 표시한 숫자들은 구조체에서의 위치를 오프셋으로 표시한 것이다.

  구조체의 각 필드에 접근하기 위해서 컴파일러는 구조체 주소에 적절한 오프셋 값을 더하는 코드를 생성한다. 예를 들어, struct rec* 자료형의 변수 r이 레지스터 %rdi에 저장된다고 가정하자. 그러면 다음의 코드는 r->i 필드를 r->j로 복사한다.

필드 i의 오프셋이 0이기 때문에 이 필드의 주소는 간단히 r의 값이다. 필드 j에 저장하기 위해서 코드는 r의 주소에 오프셋 4를 더해준다.

  구조체 내 객체의 포인터를 생성하기 위해서 필드의 오프셋을 구조체의 주소에 더해준다. 예를 들어, 포인터 &(r->a[1])은 오프셋 8+4·1=12를 더해서 얻는다. 레지스터 %rdi에 저장된 포인터 r과 레지스터 %rsi의 long integer 변수에 대해서는 포인터 &(r->a[i])를 다음과 같이 한 개의 인스트럭션으로 생성할 수 있다.

마지막 예제로, 다음의 코드는

r->p = &r->a[r->i + r->j];

r값이 레지스터 %rdi에 저장된 상태에서 다음과 같이 구현된다.

  위 예제들에서 나타난 것과 같이, 구조체에서 다른 필드를 선택하는 것은 컴파일 시에 완벽하게 처리된다. 기계어 코드는 필드 선언이나 이름에 관한 정포를 포함하지 않는다.

 

 

 

  3.9.2  공용체

  공용체 (Union)는 C언어의 자료형 체제를 회피해서 하나의 객체가 다수의 자료형에 따라 참조될 수 있도록 해준다. 공용체를 선언하는 문법은 구조체와 동일하나 그 의미는 매우 다르다. 다른 필드들이 메모리의 다른 블록을 참조하는 것이 아니라 동일한 블록을 참조한다.

  다음의 선언문을 살펴보자.

struct S3 {
	char c;
	int i[2];
	double v;
};

union U3 {
	char c;
	int i[2];
	double v;
};

x86-64 리눅스 컴퓨터에서 컴파일 될 때 S3, U3필드의 오프셋 크기는 다음과 같다.

(S3에서 i의 오프셋이 1이 아니라 왜 4인지, 왜 v가 오프셋이 9나 12가 아닌 16인지는 잠시 뒤로에 설명)

공용체 U3 * 자료형의 포인터 p에 대해서 p->c, p->i[0], p->v같은 참조들은 모두 자료구조의 시작 부분을 참조하게 된다. 또한 공용체의 전체 크기는 구성하는 필드 중에서 크기가 가장 큰 것과 동일하게 된다는 점을 발견할 수 있다.

 

  공용체는 여러 가지 측면에서 유용할 수 있지만, C언어의 자료형 체제에서 제공하는 안전망을 피해가기 때문에 오히려 치명적인 버그를 발생시킬 수도 있다. 한 가지 응용은 어떤 자료구조의 서로 다른 두 개의 필드를 상호 배타적으로 사용한다는 점을 미리 알고있는 경우다. 이 경우에는 구조체보다는 공용체로 이 두 개의 필드를 선언하면 전체 할당된 공간을 줄일 수 있다.

  예를 들어, 각 잎새노드는 값을 가지며 각 내부 노드들은 데이터값 없이 두 개의 자식 노드의 포인터를 갖는 이진 트리 구조체를 구현한다고 하자. 이것을 다음과 같이

struct node_s {
	struct node_s *left;
	struct node_s *right;
	double data[2];
};

선언한다면, 각 노드는 32byte가 소요되고, 이 중에 절반은 각 노드에서 낭비된다.

 

반면에, 만일 노드를 다음과 같이 선언한다면, 모든 노드는 단 16byte만을 필요로 한다.

union node_u {
	struct {
		union node_u *left;
		union node_u *right;
	} internal;
	double data[2];
};

만일 n이 union node_u * 타입의 노드라면, 잎새 노드의 데이터를 n->data[0] 형태로 참조하며, 내부 노드의 자식들은 n->internal.left와 n->internal.right로 참조할 수 있다.

  이런 인코딩 방식을 사용하면 주어진 노드가 잎새 노드인지 내부 노드인지 구분할 수 없다. 일반적인 방법으로는 공용체에서 다른 여러가지 선택을 정의하는 열거형(enummerated) 자료형을 사용하고, 태그 필드와 공용체를 포함하는 구조체를 만드는 것이다.

typedef enum { N_LEAF, N_INTERNAL } nodetype_t;
struct node_t {
	nodetype_t type;
	union {
		struct {
			struct node_t *left;
			struct node_t *right;
		} internal;
		double data[2];
	} info;
};

  이 구조체는 총 24byte를 필요로 한다. 4byte는 type을 위해, 8byte를 각각 info.internal.left와 info.internal.right 또는 16byte를 info.data에 사용한다. 이 경우, 공용체를 사용해서 얻는 이득은 최종 코드가 이상해진다는 점을 고려하면 비교적 크지 않다. 필드에 더 많은 자료구조에서는 이러한 이득이 더 중요할 수 있다.

 

  공용체는 서로 다른 자료형의 비트 패턴에 접근하는 데도 사용될 수 있다. 예를 들어, 다음 코드는 double에서 unsigned long 타입의 값을 생성한다.

 

unsigned long u = (unsigned long) d;

 

값 u는 d의 정수 표현이 된다. d가 0.0인 경우를 제외하고, u의 비트 표현은 d와는 매우 다른 것이 된다. 이제 double에서 unsigned long형의 값을 생성하는 다음 코드를 살펴보자.

unsigned long double2bits(double d) {
    union {
        double d;
        unsigned long u;
    } temp;
    temp.d = d;
    return temp.u;
};

이 코드에서 인자를 공용체에 한 개의 자료형을 이용해서 저장하고, 다른 하나를 이용해서 접근한다. 결과적으로 u는 3.11절 에서 설명할, 부호비트, 지수, 유효숫자 필드를 포함해서 d와 동일한 비트 표현을 갖게 된다. u의 숫자 값은 d가 0.0인 경우 외에는 d의 값과는 연관성이 없게 된다.

  서로 다른 크기의 자료형들을 한데 묶기 위해 공용체를 사용할 때는 바이트 순서 문제가 중요해질 수 이싿. 예를 들어, 두 개의 4byte unsigned로 주어진 비터 패턴을 사용해서 8byte double을 만드는 프로시저를 작성한다고 하자.

double uu2double(unsigned word0, unsigned word1)
{
    union {
        double d;
        unsigned u[2];
    } temp;
    
    temp.u[0] = word0;
    temp.u[1] = word1;
    return temp.d;
}

x86-64 같은 리틀 엔디안(little-endian) 컴퓨터에서 인자 word0는 d의 낮은 순서 4byte가 되지만, word1은 높은 순서 4byte가 된다. 빅 엔디안 컴퓨터에서는 두 인자의 역할이 뒤바뀐다.

 

 

 

  3.9.3  데이터의 정렬

 

  많은 컴퓨터 시스템들은 기본 자료형들에 대해 사용 가능한 주소를 제한하고 있어서 어떤 객체의 주소는 어떤 값 K(일반적으로 2, 4, 8)의 배수가 되도록 요구한다. 이러한 정렬제한은 프로세서와 메모리 시스템 간의 인터페이스를 구성하는 하드웨어의 설계를 단순화한다. 예를 들어, 어떤 프로세서는 항상 8의 배수인 주소로 메모리에서 8byte를 인출한다고 하자. 만일 모든 double 값이 주소가 8의 배수로 정렬될 것이라고 보장할 수 있다면, 이 값은 하나의 메모리 연산으로 읽거나 쓸 수 있다. 그렇지 않다면, 객체가 두 개의 8byte 메모리 블록에 걸쳐서 나누어져 있을 수 있으므로 메모리에 두 번 접근해야 할 수 있다.

  x86-64 하드웨어는 데이터의 정렬(Data Alignment)과 상관없이 정확하게 동작할 것이다. 그러나 intel은 메모리 시스템 성능을 개선하기 위해서 데이터가 정렬될 것을 추천한다. 이들의 정렬 규칙은 모든 K의 원시 객체들은 K의 배수로 주소를 가져야 한다는 원칙에 기초한다. 이 규칙이 다음과 같은 정렬을 의미한다는 것을 알 수 있다.

 

  정렬은 자료형 내의 모든 객체들이 각각으 ㅣ정렬 제한사항을 만족하는 방법으로 조직되고 할당되도록 강요된다. 컴파일러는 어셈블리 코드에 디렉티브(directives)들을 삽입하여 전역 데이터를 위하여 원하는 정렬을 표시한다. 예를 들어, assembly-code declaration of jump table는 다음과 같은 디렉티브를 2번 줄에 포함한다.

   .align 8

이것은 다음에 오는 데이터(이 경우에는 점프 테이블의 시작)가 8의 배수인 주소로 사작하도록 보장해준다. 각 테이블으 ㅣ원소가 8byte 길이를 가지므로 다음의 원소들은 8byte 정렬제한을 준수할 것이다.

 

  구조체가 관련된 코드에서 컴파일러는 구조체의 각 원소드링 각각의 정렬 요구사항을 만족하도록 필드 할당 시 빈 공간을 삽입힌다. 그러면 구조체는 자신의 시작주소가 가져야 하는 정렬 요건이 정해진다.

  예를 들어, 다음의 구조체 선언을 살펴보자.

 

struct S1 {
	int i;
	char c;
	int j;
};

컴파일러가 다음의 그리에 표시한 것과 같이 최소 크기인 9byte 할당을 사용했다고 가정하자.

그러면, 필드 i(오프셋 0)와 j(오프셋 5) 모두에 대해 4byte 정렬요건을 만족시키는 것은 불가능해진다. 대신에 컴파일러는 필드 c와 j 사이에 3byte 공간을 삽입한다.

그 결과 j는 오프셋 8을 가지게 되고, 전체 구조체의 크기는 12byte가 된다. 뿐만 아니라, 컴파일러는 모든 struct S1* 형의 포인터 p가 4byte 정렬을 만족하도록 보장해준다. 이전의 표시방법을 사용해서 포인터 p가 값 x_p를 갖는다고 하자. 그러면 x_p는 4의 배수가 되어야 한다. 이것은 p->i(주소 x_p)와 p->j(주소 x_p + 8) 모두 각각의 4byte 정렬 요건을 만족하도록 보장해 준다.

 

  추가로, 컴파일러는 구조체의 마지막에 0을 채워서 구조체 배열에서 각 원소가 각각의 정렬 요건을 만족하도록 해준다. 예를 들어, 다음의 구조체 선언을 살펴보자.

struct S2 {
	int i;
	int j;
	char c;
};

만일 이 구조체를 9byte 내에 저장하려 한다면, 구조체의 시작주소가 4byte 정렬 요건을 만족시키도록 해서 필드 i와 j에 대한 정렬 요건을 여전히 만족시킬 수 있다. 그렇지만, 다음의 선언문을 살펴보자.

    struct S2 d[4];

9byte 할당을 사용한다면 d의 각 원소들의 정렬 요건을 만족시킬 수 없다. 왜냐하면 이 원소들은 x_d, x_d+9, x_d + 18, x_d + 27의 주소를 갖기 때문이다. 그 대신에, 컴파일러는 구조체 S2에 대해서 마지막 3byte를 낭비하는 공간으로 추가해서 12byte를 할당한다.

이 방법을 사용해서 d의 원소들은 x_d, x_d+12, x_d + 24, x_d + 36을 주소로 갖는다. x_d가 4의 배수를 만족하면, 모든 정렬제한은 만족될 수 있다.

 

 

 

  3.10  기계수준 프로그램에서 제어와 데이터의 결합

 

  지금까지 우리는 머신코드가 프로그램의 제어를 구현한 방법과 서로 다른 자료구조를 구현한 방법을 각각 따로 살펴보았다. 이번 절에서 우리는 데이터와 자료가 상호작용하는 방식을 살펴보겠다. 먼저 C언어에서 가장 심오한 개념이지만 프로그래머들이 가장 적은 이해를 하고 있는 포인터를 자세히 살펴보겠다. 기계수준 프로그램을 이해하는 것이 실제 많은 시스템에서 중요한 보안취약성인 버퍼 오버플로우를 어떻게 이해할 수 있게 해주는지 살펴본다. 마지막으로 함수가 요구하는 스택 저장공간의 양이 실행때마다 달라지는 경우를 기계수준 프로그램이 어떻게 구현하는지를 조사한다.

 

 

  3.10.1  포인터 이해하기

 

  포인터는 C언어에서 핵심 특징이다. 이들은 다른 자료구조 내 원소들에 대한 참조를 생성하는 통일된 방법으로서의 역할을 수행한다. 포인터들은 초보 프로그래머들에게는 혼란의 원인을 제공하지만, 그 아래에 깔려있는 개념은 매우 간단하다. 이 절에서는 포인터의 일부 주요 원리를 강조하고, 이들의 기계어 코드로의 매핑을 설명한다.

 

• 포인터는 연관된 자료형을 갖는다. 이 자료형은 어떤 종류의 객체를 이 포인터가 가리키는가를 의미한다. 다음과 같은 포인터 선언을 예제로 사용하면,

          int   *ip;

          char  **cpp;

       변수 ip는 int형 객체로의 포인터이지만, cpp는 자기 자신이 char형 객체의 포인터인 객체를 가리키는 포인터이다. 일반적으로 만일 객체가 가료형 T를 갖고 있다면, 포인터는 자료형 T*를 갖는다. 특수한 void*형은 범용(generic) 포인터를 표시한다. 예를들면, malloc함수는 범용 포인터를 리턴하며, 이것은 할당 연산의 명시적 또는 암묵적 형변환(casting)을 통해서 자료형을 갖는 포인터로 변환된다. 포인터 자료형은 기계어 코드에 속한 개념은 아니다. 이들은 C언어가 프로그래머들로 하여금 오류를 피할 수 있도록 돕기 위해 제공하는 추상화 개념이다.

 

• 모든 포인터는 특정 값(특정 자료형을 갖는 어떤 객체의 주소)을 가진다. 특수값인 NULL (0) 값은 포인터가 아무 곳도 가리키지 않는 것을 의미한다.
• 포인터는 &연산자를 사용해서 만든다. 이 연산자는 lvalue로 구분되는 C언어의 모든 수식에 적용될 수 있으며, lvalue는 할당문의 좌측에 올 수 있는 식을 의미한다. 여기에는 변수들, 구조체, 공용체, 배열의 원소들이 해당된다. 연산자 '&'의 기계어 코드 구현은 leap 인스트럭션을 사용해서 식의 값을 계산한다는 것을 이미 학습했으며, 이 인스트럭션은 메모리 참조의 주소를 계산하기 위해 설계되었다.
• 포인터는 * 연산자를 사용해서 역참조한다. 그 결과는 포인터와 연관된 자료형을 갖는 값을 가져온다. 역참조는 정해진 주소에 저장하거나 주소로부터 값을 가져오는 등의 메모리 참조를 사용해서 구현한다.
• 배열과 포인터는 밀접한 관련이 있다. 배열의 이름은 마치 포인터 변수처럼 참조될 수 있다(그러나 변경될 수는 없다). 배열의 참조(예. a[3] )는 포인터 연산이나 역참조[예. *(a+3) ]와 완벽하게 동일한 효과를 갖는다. 배열 참조와 포인터 연산은 객체의 크기에 따라 오프셋을 조절해야 한다. 포인터 p에 대한 식 p+i를 값 p를 사용해서 작성할 때, 최종 주소는 p + L · i로 계산된다. 여기서 L은 p와 연관된 자료형의 크기이다.
• 한 종류의 포인터에서 다른 종류로의 자료형 변환은 그 종류만 바뀔 뿐 값은 변화가 없다. 형변환의 한 가지 효과는 포인터 연산의 크기변환을 변경하는 것이다. 예를 들어, 만일 p가 값 p를 갖는 자료형 char*의 포인터라면 식 (int*)p+7은 p + 28을 계산하며, (int*)(p+7)은 p+7을 계산한다(형변환이 덧셈보다 우선순위를 갖는다!).
• 포인터는 함수를 기리킬 수도 있다. 이것은 프로그램의 다른 부분에서 호출할 수 있는 코드에 대한 참조를 저장하거나 넘겨줄 수 있는 강력한 기능을 제공한다. 예를 들어, 만일 어떤 함수가 다음과 같이 정의된다면,

                int   fun(int x, int *p);

       포인터 fp를 다음과 같이 선언하고 함수에 할당할 수 있다.

                int (*fp)(int, int *);

                fp = fun;

       그러고 나서, 이 포인터를 사용해서 함수를 호출할 수 있다.

                int  y = 1;

                int  result = fp(3, &y);

       함수 포인터의 값은 함수의 기계어 표현에서 첫 인스트럭션의 주소이다.

 

 

  3.10.2  실제 적용하기: GDB 디버거 사용하기

 

  GNU 디버거인 GDB는 기계어 프로그램의 런타임 평가 및 분석에 유용한 기능을 제공한다. 우리는 이 책에 포함된 예제와 문제들을 통해서 단순히 코드를 살펴보는 것만으로 프로그램의 동작을 유추해 보았다. GDB를 사용하면, 프로그램의 실행을 정교하게 제어하면서 실행되는 프로그램을 관찰하여 프로그램의 동작을 분석할 수 있다.

  그림 1은 기계어 수준의 x86-64 프로그램을 다룰 때 도움이 되는 GDB 명령들을 보여준다. OBJDUMP를 실행하여 프로그램의 역어셈블된 형태를 얻는 것도 큰 도움이 된다. 다음의 예제는 역어셈블한 파일을 GDB상에서 실행하는 과정에 대한 것이다. GDB를 다음과 같은 명령으로 실행한다.

              linux> gdb prog

※ 그림 1. GDB 명령어 예시. 이 예제들은 GDB가 기계어 수준 프로그램의 디버깅을 위해 지원하는 기능을 보여준다.

  일반적인 방법은 브레이크포인트(breakpoint)를 프로그램에서 관심이 있는 부분 근처에 설정하는 것이다. 함수의 시작 직후나 프로그램의 특정 주소에 설정할 수 있다. 프로그램 실행중에 브레이크포인트를 만나게 되면, 프로그램은 실행을 중단하고, 제어를 사용자에게 넘긴다. 브레이크포인트로부터 레지스터나 메모리 위치의 값을 다양한 형식으로 조사할 수 있다. 또한, 한 번에 몇 개의 인스트럭션만 실행하여 프로그램을 단일 단계로 실행할 수 있으며, 다음 브레이크포인트 위치까지 프로그램을 진행할 수도 있다.

  예제에서 제안하는 것처럼 GDB는 특이한 명령어 문법을 가지고 있지만, 온라인 도움말 기능(GDB에서 help명령)을 제공하여 이러한 단점을 보완하고 있다. GDB의 명령어줄 인터페이스를 사용하는 대신, 많은 프로그래머들은 GDB의 그래픽 사용자 인터페이스인 DDD를 선호한다.

 

 

  3.10.3  범위를 벗어난 메모리 참조와 버퍼 오버플로우

 

  C에서는 배열참조 시 범위를 체크하지 않으며, 지역변수들이 스택에 보존용 레지스터들과 리턴 주소 같은 상태정보와 함께 스택에 저장된다는 것을 배웠다. 이러한 조합때문에 심각한 프로그램 에러가 발생할 수 있는데, 스택에 저장된 상태정보가 범위를 벗어난 배열의 원소에 대한 쓰기 작업에 의해 변경되는 것이다. 그러고 나서 프로그램이 레지스터값을 재적재하거나 이렇게 변경된 상태정보를 사용해서 ret 인스트럭션을 실행할 때, 심각한 결과를 초래한다.

  특히 일반적인 상태손실의 원인은 버퍼 오버플로우라고 알려져있다. 일반적으로 어떤 문자배열이 스택에 스트링을 가지고 할당되어 있지만, 스트링의 크기는 배열에 할당된 공간을 초과한다. 이는 아래의 프로그램 예제를 통해 실행해 볼 수 있다.

/* Implementation of library function gets() */
char *gets(char *s)
{
    int c;
    char *dest = s;
    while ((c = getchar()) != ’\n’ && c != EOF)
    *dest++ = c;
    if (c == EOF && dest == s)
		/* No characters read */
		return NULL;
	*dest++ = ’\0’; /* Terminate string */
	return s;
}

/* Read input line and write it back */
void echo()
{
    char buf[8]; /* Way too small! */
    gets(buf);
    puts(buf);
}

 

  위의 코드는 gets 라이브러리 함수의 심각한 문제를 나타내는 함수의 구현을 보여준다. 표준 입력으로부터 한 줄을 읽어들이고 엔터 키나 오류 상황이 발생했을 때 멈추는 함수이다. 이 프로그램은 이 스트링을 인자 s라는 위치에 복사하고, 스트링의 마지막에 널문자를 추가한다. gets의 사용을 보여주기 위해 표준 입력에서 한 줄을 읽어들여서 다시 그것을 화면에 출력해주는 echo 함수를 구현하였다.

  gets함수의 문제는 전체 스트링을 저장할 수 있는 공간이 충분히 할당되었는지 결정할 방법이 없다는 것이다. 위 echo 예제에서, 의도적으로 버퍼의 크기를 매우 작게 설정하였다(8byte). 길이가 7byte보다 더 긴 스트링들은 모두 범위초과 쓰기를 발생한다.

  echo에 대한 GCC의 어셈블리 코드 번역은 스택이 어떻게 구성되었는지 유추할 수 있다.

 

※ 그림 2. echo 함수에서 스택 구성. 문자형 배열 buf는 저장된 상태의 아랫부분이다. buf로 범위를 초과해서 쓰게 되면 프로그램의 상태가 손상된다.

  그림 2.는 echo를 실행하는 동안의 스택 구성을 나타낸다. 프로그램읜 스택포인터에서 24를 빼서 스택에 24byte를 할당한다(2번 줄). gets와 puts로의 호출 시에 인자로 사용하기 위해 %rsp가 %rdi로 복사된다는 사실로 알 수 있는 것처럼 문자 buf는 스택의 탑에 위치한다. buf와 저장된 리턴 포인터 사이의 16byte는 사용되지 않는다. 사용자가 최대 7문자를 입력하는 한, gets가 리턴하는 문자열은(종료 NULL문자를 포함해서) buf에 할당된 공간에 알맞게 저장된다. 보다 더 긴 스트링을 입력한다면, gets는 스택에 저장된 정보의 일부를 덮어쓰게 된다.

  23개의 문자 스트링까지는 심각한 결과가 발생하지 않지만, 이 이상의 경우 리턴 포인터의 값과 추가적으로 저장된 상태까지도 손상될 것이다. 만일 리턴주소의 저장된 값이 손상되면, ret 인스트럭션(8번 줄)은 프로그램을 전혀 예상하지 못한 곳으로 점프하게 할 것이다. 이러한 동작들은 모두 C코드에서 가능하지 않을 것처럼 보였다. gets 같은 함수들에 의한 범위초과형 메모리 쓰기의 충격은 프로그램을 기계어 수준에서 공부해야 할 수 있는 내용이다.

  위에 제시한 echo함수의 코드는 간단하지만, 허술하다. 보다 개선된 버전은 함수 fgets를 이용하는 것인데, 여기서는 읽어들일 최대 바이트 수를 인자로 사용한다. 일반적으로 gets나 저장공간을 오버플로우하게 되는 함수를 사용하는 것은 나쁜 프로그래밍 습관으로 평가한다. 안타깝게도 strcpy, strcat, sprintf와 같이 자주 사용되는 많은 라이브러리 함수들은 대상 버퍼의 크기를 나타내는 아무런 수단도 없이 일련의 바이트를 생성할 수 있는 특성을 갖는다. 이러한 조건들은 버퍼 오버플로우시 취약성이 될 수 있다.

 

  버퍼 오버플로우의 보다 치명적인 사용은 일반적으로 프로그램이 하지 않을 기능들을 실행하도록 하는 것이다. 이것은 컴퓨터 네트워크 상의 시스템 보안성을 공격하는 가장 일반적인 방법 중의 하나이다. 일반적으로 탐색 코드(exploit code)라고 하는 실행코드를 바이트 인코딩한 탐색코드를 가리키는 포인터로 리턴 주소를 덮어쓰는 약간의 추가적인 바이트들을 포함하는 스트링을 입력한다. ret 인스트럭션을 실행하면 탐색코드로 점프하게 된다.

  공격의 한 가지 유형으로, 탐색코드는 시스템 콜을 이용해서 쉘 프로그램을 시작하고, 공격자에게 여러 가지 운영체제 기능을 제공한다. 다른 형태로 탐색 코드는 허용되지 않은 기능을 실행하고, 손상된 스택을 복구하며, ret를 한 번 더 실행해서 외형적으로는 호출자에게 정상적인 리턴이 발생한 것처럼 하기도 한다.

  예를 들면, 1988년 11월의 유명했던 인터넷 웜은 네 개의 다른 방법을 사용해서 인터넷 상의 많은 컴퓨터에 접속으르 획득했다. 한 가지 방법이 바로 FINGER 명령의 요청을 처리하는 FINGER 데몬인fingerd로의 버퍼 오버플로우 공격이었다. FINGER 명령을 적절한 스트링과 함께 호출하면 웜이 데몬으로 하여금 원격지에서 버퍼 오버플로우를 발생시키고, 원격지 시스템에 웜이 접근할 수 있도록 하는 코드를 실행한다. 일단 웜이 시스템에 접속을 획득하면, 웜은 자신을 복제하고 컴퓨터의 모든 자원을 점유한다. 그 결과 보안 전문가가 웜을 제거하는 방법을 결정할 수 있들 때까지 수백 대의 컴퓨터가 동작하지 않았다. 웜을 만든 사람은 경찰에 잡혀서 기소되었다. 그는 3년간의 보호관찰과 400시간의 공공봉사, 그리고 1천만원의 벌금을 선고받았다. 그렇지만, 지금 이 순간에도 버퍼 오버플로우 공격에 취약한 보안 약점이 계속해서 발견되고 있다. 이런 이유로 보다 조심스런 프로그램이 요구되는 것이다. 외부 환경으로의 인터페이스는 "철통검증"해서 외부의 에이전트 프로그램이 시스템에 오동작을 일으키지 못하도록 해야 한다.

 

 

  3.10.4  버퍼 오버플로우 공격 대응 기법

  버퍼 오버플로우 공격은 은밀하여 컴퓨터 시스템에 많은 문제를 야기했기 때문에 최신 컴파일러와 운영체제는 이들 공격이 실행되기 어렵게 하는 방법과 침입자가 버퍼 오버플로우 공격을 통해서 시스템의 제어권을 획득할 수 있는 방법을 제한하는 방법을 구현하였다. 이 절에서는 리눅스 GCC 최신 버전에서 제공하는 기법을 살펴본다.

 

  (1) 스택 랜덤화

  공격자는 탐색 코드를 시스템에 삽입하기 위해서 공격 스트링 내에 코드뿐만 아니라 코드로의 포인터까지 집어넣어야 한다. 이 포인터를 만들기 위해서는 스트링이 위치하게 될 스택의 주소를 알아야 한다. 역사적으로 프로그램의 스택 주소는 쉽게 예측할 수 있었다. 동일한 프로그램과 운영체제 버전을 실행하는 모든 시스템에서 스택의 위치는 컴푸터간에 매우 안정적인 값을 갖는다. 그래서 예를 들어 공격자가 ㅇ리반적인 웹 서버가 사용하는 스택 주소를 결정하기 위해서는 많은 컴퓨터에서 동작하는 공격을 만들 수 있어야 한다. 전염성 질병에서처럼 많은 시스템은 보안 단일문화(securitt monoculture)라고 부르는 현상인 완전히 동일한 바이러스 변종에 취약하였다.

  스택 랜덤와의 아이디어는 스택의 위치를 프로그램의 매 실행마다 다르게 해주는 것이다. 그래서 비록 많은 컴퓨터가 동일한 코드를 샐행하고 있을지라도 이들은 모두 완전히 다른 스택주소를 사용하게 된다. 이 방법은 예를 들어 프로그램의 시작 시 스택에 alloca함수를 사용하여 0부터 nbyte 사이의 랜덤 크기 공간을 할당해서 스택에 정해진 크기의 공간을 할당한다. 이렇게 할당된 공간은 프로그램에서 사용하지 않지만, 이렇게 함으로써 프로그램의 매 실행마다 모든 이후의 스택 위치가 변경되도록 해준다. 할당의 범위 n은 너무 커서 공간을 낭비하지 말아야 하며, 스택 주소에 충분한 변화를 줄 정도로 큰 값을 유지해야 한다.

  다음의 코드는 전형적인 스택 주소를 결정하는 간단한 방법을 알려준다.

  이 코드는 단순히 main 함수의 지역변수 주소를 출력하고 이싿. 32비트 보드의 리눅스 컴퓨터에서 이 코드를 1만번 실행하면 주소는 0xff7fc59c에서 0xffffd09c까지 약 2^23 범위를 갖는다. 64비트 모드의 보다 최신 컴퓨터에서 실행하면, 주소가 0x7fff0001b698에서 0x7ffffffaa4a8까지 약 2^32 범위를 갖는다.

  스택 랜덤화는 리눅스 시서템에서의 표준 기법이 되었다. 이것은 주소공간 배치 랜덤화(ASLR)라고 하는 보다 넓은 종류의 기술에 속한다. ASLR을 사용하면 프로그램 코드, 라이브러리 코드, 스택, 전역변수, 힙(heap) 데이터를 포함하는 여러 프로그램의 부분들이 프로그램이 매번 실행할 때마다 메모리의 다른 지역에 로딩된다. 이것은 하나의 컴퓨터에서 실행하는 프로그램은 다른 컴퓨터의 동일한 프로그램과 서로 다른 주소 매핑을 갖는것을 의미한다. 이 방법은 여러 종류의 공격을 방지한다.

 

  그렇지만, 전체적으로 볼 때 집요한 공격자가 반복적으로 주소를 바꿔가며 무지막지하게 공격하면 랜덤화를 극복할 수 있다. 일반적인 기법은 여러 개의 nop("no-op"이라고 읽고 "no operation"이라는 의미) 인스트럭션을 실제 탐색코드 앞에 삽입하는 것이다. 이 인스트럭션을 실행하는 것은 프로그램 카운터를 다음 인스트럭션으로 이동하는 것 외에는 아무 효과도 없다. 공격자가 이 인스트럭션들 중간에 주소를 추측할 수 있다면, 프로그램은 이 코드 블록을 실행하고 탐색코드를 찾을 수 있다. 이러한 코드 블록을 부르는 일반적인 용어는 "nop sled"로, 프로그램이 코드 내에서 "slides" 한다는 개념을 표현한다. 만일 256byte의 nop sled를 설정하면, n=2^23에 걸친 랜덤화는 2^15 = 32,768회 시도로 깰 수 있다. 64비트의 경우는 2^24 = 16,777,216회 시도해야 하므로 보다 더 어렵다. 스택 랜덤화와 여러 가지 ASLR의 측면은 시스템을 성공적으로 공격하기 위해 요구되는 노력을 증가시키기 때문에 바이러스나 웜이 퍼지는 속도를 상당히 줄일 수 있으나, 완벽한 대책을 제공할 수는 없다.

 

  (2) 스택 손상 검출

  두 번째 방어 방법은 스택이 손상되는 것을 감지하는 것이다. echo 함수의 예제에서 손상이 대개 프로그램이 지역 버퍼의 경계를 벗어날 때 발생한다는 것을 알 수 있다. C에서 배열의 경계를 넘는 쓰기 작업을 방지하는 안정적인 방법은 존재하지 않는다. 그 대신, 프로그램은 해로운 효과가 발생하기 전에 이러한 쓰기 작업이 발생하는 것을 감지하는 시도를 할 수 있다.

  최신 GCC에는 스택 보호 코드를 버퍼 오버플로우를 감지하기 위해 생성된 코드에 추가하는 기법을 구현하고 있다. 이 아이디어는 지역 버퍼와 나머지 스택 상태 값 사이에 그림 3.에 나타낸 것과 같이 특별한 카나리(canary) 값을 저장하는 것이다. 이 카나리 값은 보호값(guard value)이라고도 불리며, 프로그램의 매 실행마다 랜덤으로 생성되므로 공격자가 값을 쉽게 추정하기 어렵다. 레지스터 상태를 복원하고 함수로부터 리턴하기 전에 프로그램은 카나리 값이 이 함수나 호출한 함수의 동작에 의해 변경되었는지를 체크해야 한다. 만일 변경되었다면, 프로그램은 에러를 발생시키면서 종료한다.

  최신 GCC 버전에서는 함수가 스택 오버플로우에 취약한지를 판단하려 하며, 이러한 종류의 오버플로우 감지 기능을 자동으로 삽입한다. 사실, 스택 오버플로우 예제에서 명령줄 옵션으로 -fno-stack-protector를  사용해서 GCC가 이러한 코드를 추가하는 것을 방지했어야 한다. 함수 echo를 이 옵션 없이 컴파일해서 스택 보호기가 동작하게 되면, 다음과 같은 어셈블리 코드를 얻게 된다.

  함수의 이번 버전은 메모리에서 한 개의 값을 가져와서 스택에 %rsp로부터 buf를 위해 할당된 영역 바로 다음, 즉 오프셋 8 위치에 저장한다. 인스트럭션 인자 %fs:40은 카나리 값이 메모리로부터 세그먼트 주소를 사용해서 읽어들여진다는 것을 나타낸다. 세그먼트 주소방식은 80286 시절부터 유래한 주소 방식으로 최신 컴퓨터에서는 거의 찾아보기 어렵다. 카나리 값을 특별한 세그먼트에 저장해서 "read only"로 표시할 수 있으며, 따라서 공격자가 저장된 카나리 값을 변경할 수 없게 된다. 레지스터 상태를 복원하고 리턴하기 전에 함수는 스택에 저장된 값을 카나리 값과 비교하면(11번 줄의 xorq 인스트럭션 사용). 만일 두 값이 ㄹ일치하면 xorq 인스트럭션은 0이 되고, 함수는 정상적으로 종료한다. 0이 아닌 값이 된다면 스택의 카나리 값이 변경되었으며, 코드는 에러 처리 루틴을 호출하게 된다.

  스택 보호는 버퍼 오버플로우 공격에 의해 프로그램 스택에 저장된 상태의 손상을 방지하는 데 유용하다. 이 방식은 매우 작은 성능 저하를 가져올 뿐이며, 그것은 특히 GCC가 함수 내에 char 타입의 지역 버퍼가 있는 경우에만 이 코드를 삽입하기 때문이다. 물론 실행하는 프로그램의 상태를 손상시키는 다른 방법들이 있지만, 스택의 취약성을 줄이는 것이 많은 일반적인 공격전략을 약화시킨다.

 

  (3) 실행코드 영역 제한하기

  마지막 방법은 공격자가 실행코드를 시스템에 추가할 가능성을 제거하는 것이다. 한 가지 방법은 어느 메모리 영역이 실행코드를 저장할지를 제한하는 것이다. 일반적인 프로그램에서 컴파일러가 만든 코드를 저장하는 메모리 부분만이 실행 가능하면 된다. 다른 부분들은 읽기와 쓰기만 허용하도록 제한할 수 있다. 가상메모리 공간은 대개 2048 또는 4096 byte를 갖는 페이지들로 논리적으로 나누어진다.하드웨어는 사용자 프로그램과 운영체제 커널에게 허용된 접근형태를 나타내는 서로 다른 메모리 보호의 형태를 지원한다. 많은 컴퓨터는 세 개의 접근 형태에 걸친 제어를 허용한다-읽기(메모리에서 데이터 읽기), 쓰기(메모리에 데이터 저장하기), 실행하기(메모리 내용을 기계어 수준의 코드로 취급하기). 역사적으로 x86 아키텍처는 읽기와 실행 접근 제어를 1비트 플래그에 통합하였으며, 따라서 읽기허용으로 표시된 페이지는 모두 실행 가능하였다. 스택은 읽기 기능과 쓰기 기능으로 유지되어야 했으며, 따라서 스택의 바이트들도 실행 가능하였다. 일부 페이지들을 읽기 가능하면서 실행 불가능하게 하기 위한 여러가지 방법들이 구현되었지만, 대개가 상당한 비효율을 발생시켰다.

 

  보다 최근에 AMD는 "NX"(no-excute) 비트를 그들의 64비트 프로세서를 위한 메모리 보호 내에 추가하였고, 이 방법으로 읽기와 쓰기 접근이 분리되었으며, 인텔도 이 방법을 채택하였다. 이 기능으로 스택은 읽기와 쓰기는 가능하지만 실행할 수 없도록 표시될 수 있으며, 페이지가 실행 가능한지 체크하는 것도 하드웨어에서 효율성 저하 없이 실행된다.

  일부 프로그램에서는 동적으로 코드를 생성하고 실행하는 기능을 요구한다. 예를 들어 "적시(just-in-time" 컴파일 기술은 실행 성능을 개선하기 위해 자바와 같이 인터프리트 언어로 작성된 프로그램을 위한 코드를 동적으로 생성한다. 최초의 프로그램을 작성할 때 런타임시스템이 실행코드를 컴파일러가 생성한 부분에만 제한할 수 있을지 여부는  언어와 운영체제에 다라 달라진다.

 

  이 절에서 다룬 방법들ㅡ랜덤화, 스택보호, 실행코드를 저장할 수 있는 메모리 부분 제한하기ㅡ은 프로그램의 버퍼 오버플로우 취약성을 최소화하기 위해 사용되는 가장 일반적인 세 가지 기법이다. 이들의 공통점은 프로그래머들에게는 특별하게 요구되는 것이 없으면서 성능을 거의 감소시키지 않는다는 것이다. 이들 각각은 취약성을 별도로 줄여주며, 함께 사용하면 보다 효과적이다. 불행하게도 여전히 컴퓨터를 공격하는 방법이 존재하며, 웜과 바이러스는 많은 컴퓨터의 무결성을 지속적으로 훼손하고 있다.

 

 

 

  3.10.5  가변크기 스택 프레임 지원하기

  우리는 지금까지 다양한 함수들에 대한 머신코드들을 살펴보았지만, 이들은 공통적으로 할당되어야 하는 스택 프레임의 크기를 컴파일러가 미리 결정할 수 있다는 특징이 있었다. 그렇지만 일부 함수들은 가변적인 지역저장공간 크기를 필요로 한다. 예를 들어 이런 경우는 함수가 스택에 임의의 크기의 바이트를 할당하는 표준함수인 alloca를 호출할 때 일어난다. 또한 이것은 이 코드가 가변크기의 지역배열을 선언할 때 일어날 수 있다.

  비록 이번 절에서 설명하는 정보가 어떻게 프로시저가 구현되는지에 관한 일면을 올바르게 고려되어야겠지만, 이 점에 관해서 설명은 뒤로 미루어두었는데, 그 이유는 이 부분이 배열과 정렬에 대한 이해를 필요로 하기 때문이다.

※ 그림 3. 프레임 포인터를 사용해야 하는 함수. 가변길이 배열은 스택 프레임의 크기가 컴파일 시에 결정될 수 없다는 것을 의미한다.

  그림 3(a)의 코드는 가변크기 배열을 포함하는 함수의 예를 보여준다. 이 함수는 n개의 포인터들의 지역배열 p를 선언하며, n은 첫 번째 인자로 주어진다. 이것은 스택에 8n바이트를 할당을 요구하게되며, 여기서 n의 값은 함수의 호출 때마다 달라진다. 그래서 컴파일러는 얼마만큼의 공간이 함수의 스택프레임을 위해 할당되어야 하는지 결정할 수 없다. 뿐만 아니라, 이 프로그램은 지역변수 i의 주소에 대한 참조를 생성하고, 그래서 이 변수는 또한 스택에 저장되어야 한다. 실행되는 동안에 이 프로그램은 지역변수 i와 배열 p의 원소들에 모두 접근할 수 있어야 한다. 리턴할 때 이 함수는 스택 프레임을 반환하고 스택 포인터를 저장되었던 리턴주소의 위치로 설정한다.

 

  가변크기 스택프레임을 처리하기 위해 x86-64 코드는 레지스터 %rbp를 이용해서 프레임포인터(frame pointer-어떤 경우는 베이스 포인터-base pointer라고 부르며, 따라서 %rbp에서 문제 bp를 사용한 것을 볼 수 있다.)로 사용한다. 프레임 포인터를 사용할 때, 스택 프레임은 그림 4의 vfame함수의 경우에서 보여준 것과 같이 구성된다. %rbp 레지스터는 피호출자 저장 레지스터이기 때문에 이 코드는 스택에 이전 버전의 %rbp를 보관한다. 그 후 이 함수가 실행되는 동안 계속 %rbp를 현 위치로 가리키도록 유지하며, 이것은 고정길이 지역변수들(ex. i같은)을 %rbp에 대한 상대적인 오프셋 값으로 참조한다.

  그림 3(b)는 함수 vfame을 위해 GCC가 생성한 코드의 일부분을 보여준다. 이 함수의 시작 부분에서 스택 프레임을 설정하고 배열 p를 위한 공간을 할당하는 코드를 볼 수 있다. 이 코드는 현재의 %rbp 값을 스택에 푸시하고, %rbp를 이 스택 위치로 가리키도록 설정하는 것으로 시작한다(2~3번 줄). 다음으로, 16byte를 스택에 할당하는데, 첫 8byte는 지역변수 i를 저장하는 데 사용하며, 두 번째 8byte는 사용하지 않는다. 그러고 나서, 배열 p를 위한 공간을 할당한다(5~11번 줄). 이 프로그램이 11번 줄에 도달하는 순간에는 (1) 스택에 최소 8n byte를 할당하였으며, (2) 이 할당된 영역 내에 배열 p를 배치하였으며, 따라서 최소 8n byte가 사용 가능하다는 것만 설명하는 것으로 충분하다.

※ 그림 4. 함수 vframe에 대한 스택 프레임 구조. 이 함수는 레지스터 %rbp를 프레임 포인터로 이용한다.

 

  초기화 루프를 위한 코드는 어떻게 지역변수들 i와 p가 참조되는지의 예를 보여준다. 13번 줄은 배열 원소 p[i]가 q로 설정되는 것을 보여준다. 이 인스트럭션은 p의 시작주소로 레지스터 %rcx에 있는 값을 사용한다. 지역변수 i가 갱신되고(15번 줄) 읽히는(17번 줄) 경우들을 볼 수 있다. i의 주소는 -8(%rbp)를 참조해서ㅡ즉, 프레임 포인터에 상대적으로 오프셋 -8 떨어진ㅡ 주어진다.

  프레임 포인터는 이 함수의 끝에서 leave 인스트럭션을 이용해서 자신의 이전 값으로 복원된다(20번 줄). 이 인스트럭션은 인자를 하나도 갖지 않는다. 이것은 다음의 두 인스트럭션을 실행하는 것과 동일하다.

즉, 스택 포인터는 먼저 저장된 %rbp 값의 위치로 설정되며, 그 후 이 값은 스택에서 팝되어 %rbp에 저장된다. 이 인스트럭션의 조합은 전체 스택 프레임을 반환하는 효과를 낸다.

  초기의 x86 버전에서는 프레임 포인터가 매 함수 호출 시에 사용되었다. x86-64 코드에서는 vframe에서와 같이 스택 프레임이 가변크기일 가능성이 있는 경우에만 사용된다. 역사적으로 대부분의 컴파일러들은 IA32 코드를 생성할 때 프레임 포인터를 사용하였다. 최근의 GCC 버전들은 이런 관습을 포기하였다. 모든 함수들이 %rbp를 피호출자-저장 레지스터로 취급하는 한, 프레임코드를 사용하는 코드와 그렇지 않은 코드를 혼합해서 사용하는 것이 허용된다는 점에 주목하자. 4번 줄의 subq 인스트럭션을 실행한 수의 스택 포인터의 값을 나타낸다고 하자. 이 인스트럭션은 지역변수 i의 공간을 할당한다. x_2는 7번 줄의 subq를 실행한 후의 스택 포인터의 갑을 나타낸다. 이 인스트럭션은 지역배열 p를 위한 저장공간을 할당한다. 마지막으로 p가 10~11번 줄의 인스트럭션들에서 레지스터 %r8과 %rcx에 할당된 값을 나타낸다고 하자. 이들 레지스터들은 모두 배열 p를 참조하기 위해 이용된다.

 

  그림 4의 오른쪽은 s_1, s_2, p로 나타낸 위치들을 보여준다. 또한 이는 s_1과 p값들 사이에 e_2 byte의 오프셋이 있을 수 있다는 것을 보여준다. 이 공간은 이용되지 않을 것이다. 배열 p와 s_2로 나타낸 위치 사이에는 오프셋 e_2 byte가 존재할 수도 있다.