evenharder's profile image

evenharder

January 17, 2020 17:30

C/C++의 undefined behavior

C , C++

C나 C++에 있어서 가장 곤혹스러운 요소 중 하나인 undefined behavior는 입문자부터 숙련자에 이르기까지 까다로운 디버깅을 요합니다. 흔히 나오는 코딩 실수인 배열 인덱스 오류도 undefined behavior이며, 온라인 저지 등에서는 최적화 옵션이 켜지면서 전혀 다른 효과가 일어날 수 있습니다. 꼭 C++에만 국한된 이야기는 아니지만, C++ undefined behavior의 주된 요인 중 하나인 signed integer overflow는 2019년에만 1247개의 CVE 취약점을 낳았습니다. 그렇다고 모든 사람이 C/C++ 스펙을 머릿속에 넣어야 하는 것도 아닐 뿐더러 그럴 수도 없습니다. 이 포스트에서는 undefined behavior의 정의와 대표적인 undefined behavior, 그리고 그 영향을 서술해보고자 합니다.

Undefined behavior란?

기본적으로 C++ 컴파일러는 겉에서 보기에 행동이나 결과(observable behavior)가 동일하다면, 코드의 로직을 변경하여 컴파일할 수 있습니다. 이를 as-if rule이라고 합니다. 그러나 몇몇 경우에선 표준이 observable behavior를 정의하지 않았거나, 구현체에게 맡기기도 합니다. 이런 경우가 5가지로 분류됩니다.

  • ill-formed : 프로그램이 syntax error나 semantic error 등이 있어 C++ 컴파일러가 이에 대한 에러/경고 메시지를 출력하는 경우입니다. 이런 경우에는 C++ spec에 ill-formed 등으로 명시가 되어 있습니다.

    • 예시 : decltype({1, 3})은 ill-formed입니다.

  • ill-formed no diagnostic required : ill-formed이나 컴파일러가 감지할 수 없는 경우입니다. link 과정에서 감지되어 에러가 발생할 수도 있으며, 실행시의 행동은 정의되지 않습니다.

    다음은 여기에 해당되는 것 같은 두 개의 코드입니다.

    // linking error, undefined reference to `derp::x'
struct derp { static int x; };
int main() { return derp::x; }

    // Lorem<T> -> Lorem<T*> -> Lorem<T**> -> ...
template<class T> class Lorem {Lorem<T*> lorem; };
int main() { return Lorem<int>()->ipsum; }

    두 번째 코드는 컴파일 에러가 나긴 하지만 흥미로워서 소개하였습니다.

  • implementation-defined behavior : 구현체마다 프로그램이 다른 행동을 보일 수는 있으나, 각 행동에 따른 결과가 문서화되어야 있어야 합니다.

    • 예시로 std::type_t의 타입, 1바이트가 몇 비트인지 등이 있습니다.
    • 문서화된 예시로는 g++ 7.5.0의 이 문서가 있습니다.

  • unspecified behavior : 구현체마다 프로그램이 다른 행동을 보일 수는 있으며, 각 행동에 따른 결과가 문서화되어있을 필요는 없습니다. 그러나 일반적으로 유효한 범위 내의 행동을 합니다.

    • 대표적인 예시로 evaluation order가 있습니다. return p() + q() + r();의 경우 임의의 순서로 함수가 호출될 수 있습니다.

  • undefined behavior : 어떤 결과가 나올지 정의되어 있지 않으며, 때문에 프로그램의 의미가 없어집니다. 운이 좋으면 프로그래머가 의도한 방향으로 조용히 컴파일될 수도 있으며, 아니면 조용히 내부적으로 계산이 잘못 되어가고 있을 수도 있고, 급격한 런타임 에러를 맞이할 수도 있습니다. 몇몇 단순한 undefined behavior는 컴파일러가 친절하게 잡아주기도 합니다.

Undefined behavior가 나는 대표적인 코드는 다음과 같습니다.

#include <climits>
#include <cstdio>

int main() {
    printf("%d\n", (INT_MAX + 1) < 0); // signed integer overflow is UB
    return 0;
}

이 프로그램을 컴파일하여 실행하면 출력값이 1 이든 0이든 42든 Lorem ipsum dolor sit amet이든 모두 올바른 결과가 됩니다. 가상의 C++ 구현체가 이 코드를 컴파일할 때 어떻게 할지 말 그대로 정의가 되어 있지 않기 때문입니다. 때문에 비교 연산자가 있는데도 불구하고 0이나 1이 아닌 다른 값이 출력될 수도 있습니다. 어쩌면 출력조차 안 되고 런타임 에러가 나거나, 루트 파티션이 포맷될 수도 있습니다.

이러한 undefined behavior는 자칫하면 보안 허점으로 이어질 수 있으며, 컴파일러 최적화와 연계될 경우 기상천외한 실행 결과들이 나올 수 있습니다. 그럼 이제 undefined behavior의 대표적인 예시를 알아보도록 하겠습니다.

Undefined behavior의 예시

undefined behavior(이하 UB)는 이곳저곳에서 날 수 있지만 가장 흔하게 마주할 수 있는 것들은 다음과 같습니다.

초기화가 안 된 변수의 사용

초기화가 안 된 변수에 접근하는 것은 UB입니다. 예를 들면 다음과 같습니다.

contest* search_contest(int id){
    bool is_found; // not initialized
    contest* con;
    for(int i = 0; i < some_vector.size(); i++)
    {
        if(some_vector[i].some_value == id) {
            is_found = true;
            con = some_vector[i].some_ptr;
            break;
        }
    }
    if(is_found)
        return con;
    else
        return nullptr;
}

contest가 잘 발견되면 is_found에 true가 들어가겠지만, 그렇지 않으면 초기화되지 않은 is_found의 값에 접근하게 됩니다. 몇몇 컴파일러에서는 기본적으로 특정한 값으로 초기화되기도 하지만, 최적화 옵션에 따라 해당 값이 레지스터로 옮겨가 무시무시한 일이 일어날 수도 있습니다.

때문에, 다음 코드에 대해

#include <cstdio>
int main() {
    bool p;
    if(p)   puts("p is true");
    if(!p)  puts("p is false");
    return 0;
}

출력이

p is true
p is false

가 될 수도 있습니다. 옛날 버전의 GCC에서 관찰되었다고 합니다.

부호 있는 정수형의 overflow

부호 있는 정수형(int, long 등)의 overflow는 UB입니다. 때문에 위에도 있었던

#include <climits>
#include <cstdio>

int main() {
    printf("%d\n", (INT_MAX + 1) < 0); // signed integer overflow is UB
    return 0;
}

에선 무슨 일이 일어날지 모릅니다. 비슷한 예시로 다음 코드가 있습니다.

#include <cstdio>

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x+1 > x); // signed integer overflow is UB
    return 0;
}

몇몇 컴파일러의 경우, 저 x+1 > x을 분석하여 x가 INT_MAX가 아닐 때는 참이고, x가 INT_MAX가 아닐 때는 UB이므로 아예 true로 대체하는 최적화를 시행하기도 합니다.

조금 까다로운 예시로 나눗셈이 있습니다.

#include <climits>
#include <cstdio>

int main() {
    printf("%d\n", INT_MIN / -1); // signed integer overflow is UB
    return 0;
}

int가 32비트라면 INT_MIN은 $-2^{31}$이 되는데, 이를 -1로 나누면 $2^{31}$이 되어버려 int의 범위를 벗어나게 됩니다.

부호 없는 정수형에 대한 overflow는 올바르게 정의되어 있습니다.

왼쪽/오른쪽 시프트

일반적으로, 부호 있는 정수 자료형의 비트 개수 이상 / 음수 시프트는 UB입니다. 예를 들어 1 << 32는 UB입니다. 또, C/C++ 버전에 따라 시프트했을 때 부호 비트를 침범했을 때도 UB인 경우가 있습니다. 이렇게 설계된 이유는 C가 만들어질 때 CPU의 shift instruction이 각자 달랐던 것 때문으로 추정됩니다. 또 시프트하는 범위를 굳이 체크하지 않음으로서 프로그램의 성능을 유지할 수 있습니다.

범위를 벗어난 배열 접근

말 그대로 범위를 벗어난 배열 접근은 UB입니다. int a[4];가 선언되어 있을 때 a[-1], a[5] 등으로 접근하는 것이 대표적인 예시입니다. 운이 좋으면 아무 의미 없는 공간에 접근할 수도 있지만, 메모리 상의 return address를 덮어쓰는 암울한 일이 일어날 수도 있고, 함수가 통째로 이상하게 변조될 수도 있습니다. 만약 저런 범위를 벗어난 포인터를 기반으로 다시 참조를 하면 (예시 : int b[3][2]가 주어졌을 때 b[-1][0] 접근) 디버깅의 늪에 빠질 수도 있습니다.

C를 만들 때 배열 범위에 해당하는지 확인을 할 수 없어서 UB로 처리한 것이 아니라, 포인터별로 범위를 지정하면서 넘기는 과정이 그대로 성능 저하로 이어지기 때문에 그런 것 같습니다.

유효하지 않은 포인터의 역참조

건드리면 안 되는 포인터를 역참조하는 것 또한 UB입니다. 유효하지 않은 포인터란 초기화 되지 않은 포인터, 할당이 해제된 포인터, 배열 등을 순회할 때 범위를 벗어난 포인터, realloc 함수에 전달된 포인터 등을 포함합니다. 또, NULL 포인터를 역참조하는 것도 UB입니다 (SIGTRAP 시그널이 반드시 호출되지 않습니다).

다음은 포인터와 관련된 UB 코드 중 하나입니다.

#include <iostream>
#include <cstdlib>
int main() {
    int *p = (int*)std::malloc(sizeof(int));
    int *q = (int*)std::realloc(p, sizeof(int));
    *p = 1; // UB access to a pointer that was passed to realloc
    *q = 2;
    if (p == q) // UB access to a pointer that was passed to realloc
        std::cout << *p << *q << '\n';
}

출력으로 12가 나올 수 있습니다.

side-effect가 없는 무한 루프

side-effect란 간단히 생각하면 외부 변수를 변경하는 행동이라 할 수 있습니다. 전역 변수를 수정하거나, thread를 만들거나, I/O 실행 등등이 side-effect입니다. 이러한 side-effect가 없는 무한 루프는 UB입니다. 가장 유명한 예시인 “페르마의 마지막 정리 반증하기”가 있습니다.

다음 C++ 코드를 특정 컴파일러에서 실행하면, 놀랍게도 페르마의 마지막 정리를 반증했다고 주장합니다.

#include <iostream>
 
int fermat() {
  const int MAX = 1000;
  int a=1,b=1,c=1;
  // Endless loop with no side effects is UB
  while (1) {
    if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
    a++;
    if (a>MAX) { a=1; b++; }
    if (b>MAX) { b=1; c++; }
    if (c>MAX) { c=1;}
  }
  return 0;
}
 
int main() {
  if (fermat())
    std::cout << "Fermat's Last Theorem has been disproved.\n";
  else
    std::cout << "Fermat's Last Theorem has not been disproved.\n";
}

overflow는 무시하고, fermat 함수의 while 루프는 함수의 지역 변수인 a, b, c만 접근하고 변경하기 때문에 UB입니다. 컴파일러가 보기에 무한 루프 다음의 return 0;은 도달할 수 없고, 벗어날 수 있는 유일한 방법은 return 1;이기 때문에 위 코드는 다음과 같이 최적화될 수 있습니다.

int fermat() {
  return 1;
}

페르마의 마지막 정리를 반증하는 쌍을 찾았을 때 이를 출력하라고 하면 side-effect가 생기므로, 비로소 컴파일러가 무한 루프에 빠지게 됩니다.

Sequence Point 관련 UB

i = ++i + i++; 같은 코드가 UB라는 점은 들어보셨을 수도 있을 것 같습니다. 이는 sequence point라는 개념과 관련이 있는데, C++ 버전에 따라 상이하기도 하여 본 포스트에서 다루지는 않습니다. 다만 cppreference.com의 이 문서가 상세히 설명하고 있으니 해당 사이트를 참고하여 주시기 바랍니다.

Undefined behavior의 장단점

UB의 단점은 명확합니다. 위험합니다. UB가 이상하게 일어나면 프로그램 전체가 의미없어질 수도 있습니다. 보안 약점으로 이어지기도 합니다. 배열 인덱스를 벗어나도 Java나 Python, 그 외의 최신 프로그래밍 언어처럼 안전장치가 있는 것도 아닙니다 (OOP를 도입한 C++는 다양한 안전장치를 도입했지만, 유효하지 않은 iterator를 잘못 건드리면 UB인 것은 마찬가지입니다). 게다가 정적(statically) 분석만으로 코드가 UB를 포함하는지 아닌지 판별하는 문제는 정지 문제(halting problem)와 동치입니다. 어려운 일입니다. 어찌 보면 언어 습득 난이도를 올렸다고도 할 수 있겠습니다.

UB의 (유일한) 장점은 역시 효율성 및 최적화입니다. 체크를 덜 해도 되니 컴파일러 입장에서는 명령어를 덜 추가할 수 있고, UB 코드를 잘 이용하여 의미 없는 if문 등을 제거할 수 있기 때문입니다. 운영체제나 임베디드 등에서 주로 사용되는 C의 입장에서는 속도가 최우선적이기 때문입니다. 그리고 몇몇 상황에서는 효율성은 다른 무엇보다도 우선시되는 요소일 수 있습니다.

참고 자료

컴파일러 최적화와 UB의 상관관계, 그리고 debug 모드와 release 모드의 차이와 관련된 방대한 이야기가 서술된 Surviving the Release Version도 참고해주시기 바랍니다.