Tour de IOCCC: 1986/stein

typedef char*z;O;o;_=33303285;main(b,Z)z Z;{b=(b>=0||(main(b+1,Z+1),*Z=O%(o=(_%25))+'0',O/=o,_/=25))&&(b<1||(O=time(&b)%0250600,main(~5,*(z*)Z),write(1,*(z*)Z,9)));}

짧은 프로그램은 언제나 어떤 역할을 하는지 알아 보기 쉽지 않습니다. main 함수 재귀 호출을 하면 더더욱.

뭘 하는 프로그램인가?

이 프로그램은 현재 UTC 시각을 출력합니다. 조금 꼬인 방법으로요.

이 프로그램은 컴파일된 프로그램 이름과 인자를 매우 많이 타는 프로그램이기 때문에 가급적이면 다음과 같은 방법을 그대로 따라서 컴파일하시길 바랍니다. 사실 힌트에 적혀 있는 컴파일 방법은 최근 시스템에서 사용하기에 매우 곤란한 면이 있지요.¹

간단하게 설명하면 stein이라는 이름으로 컴파일을 한 뒤 UTC라는 인자를 줘서 실행하면 됩니다. 이 때 PATH 환경 변수를 .로 선택해서 ./stein이 아니라 그냥 stein으로 실행할 수 있게 해야 합니다.

$ gcc stein.c -o stein
$ PATH=. stein UTC
183703UTC

사실은 프로그램 이름이 다섯 글자이고 인자가 세 글자이면 이 프로그램은 보통 큰 문제 없이 실행됩니다. (일부 운영체제에서는 처음 여섯 글자는 제대로 나오지만 그 다음이 깨져 나올 수도 있습니다. 여기에 대해서는 코드를 분석하면서 설명합니다.)

좀 더 "안전한" 결과를 얻기 위해서는 프로그램 이름을 아홉글자나 그 이상이 되도록 바꾸면 되겠습니다... 만 별 쓸모는 없군요.

$ gcc stein.c -o SHOWUTCCLOCK
$ ./SHOWUTCCLOCK
183947UTC

어떻게 동작하는가?

일단 적절히 공백을 추가하는 것으로 시작합니다.

typedef char *z;
O;
o;
_ = 33303285;

main(b, Z)
    z Z;
{
    b =
        (b >= 0 || (
            main(b+1, Z+1),
            *Z = O % (o = (_%25)) + '0',
            O /= o,
            _ /= 25)) &&
        (b < 1 || (
            O = time(&b) % 0250600,
            main(~5, *(z*)Z),
            write(1, *(z*)Z, 9)));
}

이 main 함수는 전통적인 K&R 선언으로 되어 있습니다. 이 선언의 특징은 함수 인자의 형을 괄호 안에 쓰는 게 아니라 괄호 뒤에 쓴다는 데 있는데, 코드에 따라서는 생략할 수 있기도 합니다. (이 경우 인자를 넘길 때 형 체크를 하지 않습니다.) 위의 경우 b의 형은 생략되었으므로 int로 가정하고, Z의 형은 z, 즉 char *가 되겠습니다. 따라서 현대적인 문법으로는,

typedef char *z;
O;
o;
_ = 33303285;

int main(int b, char *Z)
{
    b =
        (b >= 0 || (
            main(b+1, Z+1),
            *Z = O % (o = (_%25)) + '0',
            O /= o,
            _ /= 25)) &&
        (b < 1 || (
            O = time(&b) % 0250600,
            main(~5, *(z*)Z),
            write(1, *(z*)Z, 9)));
    return 0;
}

이 됩니다. 또 하나 신경 쓰이는 것은 변수 선언인데, 변수 선언 앞에 형이 없군요. -_-; 이것도 마찬가지로 K&R 시절의 잔재로 정확히 똑같은 이유로 int로 암시적으로 선언되는 변수입니다. 따라서,

a, b, c;

라고만 쓰면 int 변수가 세 개 선언됩니다. 좀 그럴듯하게 보이긴 하지만 옛날 코드니까 지금 쓰면 뺨 맞기 딱 좋은 코드입니다. 하여간 여기에도 형을 명시적으로 넣겠습니다.

typedef char *z;
int O;
int o;
int _ = 33303285;

int main(int b, char *Z)
{
    b =
        (b >= 0 || (
            main(b+1, Z+1),
            *Z = O % (o = (_%25)) + '0',
            O /= o,
            _ /= 25)) &&
        (b < 1 || (
            O = time(&b) % 0250600,
            main(~5, *(z*)Z),
            write(1, *(z*)Z, 9)));
    return 0;
}

||와 &&로 만들어진 수식은 어렵지 않게 if 문으로 바꿀 수 있습니다. 여기에 대해서는 이 기법을 매우 많이 사용하는 1988/litmaath 같은 코드에 자세히 설명되어 있습니다.

또 하나 중요한 것은, b 변수는 대입은 되지만 그 과정이 코드 맨 마지막에 일어나기 때문에 (사실 b에 대입하는 문장은 main 함수에 있는 유일한 문장입니다!) 대입이 의미가 없습니다. 이걸 고려해서 코드를 if 문으로 고치겠습니다.

typedef char *z;
int O;
int o;
int _ = 33303285;

int main(int b, char *Z)
{
    int lhs, rhs;

    if (b >= 0) {
        /* b >= 0이 1이므로 나머지 식과 상관 없이 해당 식은 1 */
        lhs = 1;
    } else {
        lhs = (
            main(b+1, Z+1),
            *Z = O % (o = (_%25)) + '0',
            O /= o,
            _ /= 25);
    }

    if (lhs) {
        /* 이 식은 &&로 연결되어 있으므로 lhs가 참일 때만 실행된다. */
        if (b < 1) {
            /* 마찬가지 이유로 해당 식은 1 */
            rhs = 1;
        } else {
            rhs = (
                O = time(&b) % 0250600,
                main(~5, *(z*)Z),
                write(1, *(z*)Z, 9));
        }
    }

    return 0;
}

콜론으로 구분된 문장은 손쉽게 독립된 문장으로 나눌 수 있습니다. 또한 rhs는 b에 대입하는 것과 마찬가지 이유로 전혀 쓰이지 않는 변수이지요.

typedef char *z;
int O;
int o;
int _ = 33303285;

int main(int b, char *Z)
{
    int lhs;

    if (b >= 0) {
        lhs = 1;
    } else {
        main(b+1, Z+1);
        *Z = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
        lhs = _;
    }

    if (lhs) {
        if (!(b < 1)) {
            O = time(&b) % 0250600;
            main(~5, *(z*)Z);
            write(1, *(z*)Z, 9);
        }
    }

    return 0;
}

이제 코드에서 b에 따라 흐름이 어떻게 변하는지 살펴 봅시다. (왜 하필 b냐 하면 조건문에 들어 있는 변수가 그것 밖에 없거든요.) 일단 b가 1보다 크거나 같을 때 main 함수는 다음과 같아지고,

int main_positive(int b, char *Z)
{
    int lhs;

    assert(b >= 1);

    if (b >= 0) { /* 항상 참 */
        lhs = 1;
    } else {
        main(b+1, Z+1);
        *Z = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
        lhs = _;
    }

    if (lhs) { /* 항상 참 */
        if (!(b < 1)) { /* 항상 참 */
            O = time(&b) % 0250600;
            main(~5, *(z*)Z);
            write(1, *(z*)Z, 9);
        }
    }

    return 0;
}

b가 0일 때는 다음과 같이 되며,

int main_zero(int b, char *Z)
{
    int lhs;

    assert(b == 0);

    if (b >= 0) { /* 항상 참 */
        lhs = 1;
    } else {
        main(b+1, Z+1);
        *Z = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
        lhs = _;
    }

    if (lhs) { /* 항상 참 */
        if (!(b < 1)) { /* 항상 거짓 */
            O = time(&b) % 0250600;
            main(~5, *(z*)Z);
            write(1, *(z*)Z, 9);
        }
    }

    return 0;
}

b가 음수일 때는 다음과 같이 됩니다.

int main_negative(int b, char *Z)
{
    int lhs;

    assert(b < 0);

    if (b >= 0) { /* 항상 거짓 */
        lhs = 1;
    } else {
        main(b+1, Z+1);
        *Z = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
        lhs = _;
    }

    if (lhs) {
        if (!(b < 1)) { /* 항상 거짓 */
            O = time(&b) % 0250600;
            main(~5, *(z*)Z);
            write(1, *(z*)Z, 9);
        }
    }

    return 0;
}

여기서 제가 /* 항상 참 */과 /* 항상 거짓 */이라고 써 놓은 부분은 말 그대로 해당 b 범위에서 항상 참이거나 거짓인 부분을 나타낸 것입니다. 해당하는 if 문들을 정리하면 코드를 다음과 같이 정리할 수 있습니다. (main 함수도 이제 새로 만든 함수들을 호출하게 해야 한다는 걸 기억합시다)

#include <assert.h>

typedef char *z;
int O;
int o;
int _ = 33303285;

int main(int b, char *Z); /* 재귀 호출을 위해 미리 선언 */

int main_zero(int b, char *Z)
{
    assert(b == 0);

    return 0;
}

int main_negative(int b, char *Z)
{
    assert(b < 0);

    main(b+1, Z+1);
    *Z = O % (o = (_%25)) + '0';
    O /= o;
    _ /= 25;
    return 0;
}

int main_positive(int b, char *Z)
{
    assert(b >= 1);

    O = time(&b) % 0250600;
    main(~5, *(z*)Z);
    write(1, *(z*)Z, 9);
    return 0;
}

int main(int b, char *Z)
{
    if (b >= 1) return main_positive(b, Z);
    if (b < 0) return main_negative(b, Z);
    return main_zero(b, Z);
}

...코드가 심하게 줄어 든 기분이 들면 제대로 보신 게 맞습니다. 원래 많이 정리되어야 정상입니다.

main 함수로 재귀호출하는 코드는 두 개가 있습니다. 하나는 main_positive에 있는데 b가 항상 ~5, 즉 -6으로 고정되어 있으므로 main_negative에 대한 호출로 바꿀 수 있습니다. 다른 하나는 main_negative에 있는데 이 경우 b+1이 0이냐 음수냐에 따라 뭘 호출할 지 결정되겠지요. 일단 둘 다 if 문으로 처리하기로 합시다.

#include <assert.h>

typedef char *z;
int O;
int o;
int _ = 33303285;

int main_zero(int b, char *Z)
{
    assert(b == 0);

    return 0;
}

int main_negative(int b, char *Z)
{
    assert(b < 0);

    if (b+1 < 0) {
        main_negative(b+1, Z+1);
    } else {
        main_zero(b+1, Z+1);
    }
    *Z = O % (o = (_%25)) + '0';
    O /= o;
    _ /= 25;
    return 0;
}

int main_positive(int b, char *Z)
{
    assert(b >= 1);

    O = time(&b) % 0250600;
    main_negative(-6, *(z*)Z);
    write(1, *(z*)Z, 9);
    return 0;
}

int main(int b, char *Z)
{
    if (b >= 1) return main_positive(b, Z);
    if (b < 0) return main_negative(b, Z);
    return main_zero(b, Z);
}

main 함수에 전달되는 b 인자는 사실 우리가 잘 알고 있는 argc에 해당합니다. (이름이 다르다고 의미가 다른 건 아니겠죠?) argc는 항상 0보다 큰, 양수 값을 가지고 있으므로, 우리는 처음에 main_positive를 호출하게 됩니다. 이제 main 함수를 직접 호출하는 코드가 없으므로 우리는 마음껏 main 함수에 이 사실을 반영할 수 있습니다.

#include <assert.h>

typedef char *z;
int O;
int o;
int _ = 33303285;

int main_zero(int b, char *Z)
{
    assert(b == 0);

    return 0;
}

int main_negative(int b, char *Z)
{
    assert(b < 0);

    if (b+1 < 0) {
        main_negative(b+1, Z+1);
    } else {
        main_zero(b+1, Z+1);
    }
    *Z = O % (o = (_%25)) + '0';
    O /= o;
    _ /= 25;
    return 0;
}

int main_positive(int b, char *Z)
{
    assert(b >= 1);

    O = time(&b) % 0250600;
    main_negative(-6, *(z*)Z);
    write(1, *(z*)Z, 9);
    return 0;
}

int main(int b, char *Z)
{
    /* 처음 호출 때는 항상 b가 양수임 */
    return main_positive(b, Z);
}

main_positive를 호출하는 곳이 main 뿐이므로 그냥 함수를 합쳐도 되겠지요.

#include <assert.h>

typedef char *z;
int O;
int o;
int _ = 33303285;

int main_zero(int b, char *Z)
{
    assert(b == 0);

    return 0;
}

int main_negative(int b, char *Z)
{
    assert(b < 0);

    if (b+1 < 0) {
        main_negative(b+1, Z+1);
    } else {
        main_zero(b+1, Z+1);
    }
    *Z = O % (o = (_%25)) + '0';
    O /= o;
    _ /= 25;
    return 0;
}

int main(int b, char *Z)
{
    O = time(&b) % 0250600;
    main_negative(-6, *(z*)Z);
    write(1, *(z*)Z, 9);
    return 0;
}

비슷한 과정을 거치면 main_negative도 main 함수 안에 합칠 수 있습니다. 어떻게 합칠 지는 함수가 호출되는 순서로부터 알 수 있지요.

처음에 main(..., ...)가 호출됩니다. 이 안에서,
- O가 설정됩니다.
- main_negative(-6, ...)가 호출됩니다. 이 안에서,
  - main_negative(-5, ...)가 호출됩니다. 이 안에서,
    - ...
      - main_negative(-1, ...)가 호출됩니다. 이 안에서,
        main_zero(0, ...)가 호출됩니다.
        나머지 코드가 실행됩니다. (b는 -1)
      - 나머지 코드가 실행됩니다. (b는 -2)
    - ...
  - 나머지 코드가 실행됩니다. (b는 -6)
- write를 호출합니다.

재귀 호출을 루프로 바꿀 때 매우 조심해야 하는 점은 호출 순서와 실제 루프를 돌려야 하는 순서가 반대일 수도 있다는 것입니다. 이 경우 재귀 호출을 먼저 한 뒤 함수 몸체를 실행하기 때문에, 실제로 함수 몸체는 반대로, 즉 b가 -1부터 -6까지 변화하면서 실행됩니다. Z도 유사하게, 원래 main에 들어 온 Z를 Z0이라고 하면 Z0+5부터 Z0까지 변화하겠죠. 이를 반영하면,

typedef char *z;
int O;
int o;
int _ = 33303285;

int main(int b, char *Z0)
{
    char *Z;
    O = time(&b) % 0250600;
    Z = *(z*)Z0;
    Z += 5;
    for (b = -1; b >= -6; b--) {
        *Z = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
        Z--;
    }
    write(1, *(z*)Z0, 9);
    return 0;
}

Z를 직접 옮기는 대신에 b를 곧바로 사용할 수 있도록 고쳐 봅시다. 이러려면 b를 굳이 -1에서 -6으로 변화시킬 필요 없이 5부터 0까지 변화시키게 하는 게 더 간단하겠죠. b는 루프 안에서 사용되지 않으므로 충분히 가능한 일입니다.

typedef char *z;
int O;
int o;
int _ = 33303285;

int main(int b, char *Z0)
{
    char *Z;
    O = time(&b) % 0250600;
    Z = *(z*)Z0;
    for (b = 5; b >= 0; b--) {
        *(Z+b) = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
    }
    write(1, *(z*)Z0, 9);
    return 0;
}

이제 Z0과 Z의 정체(?)를 파헤쳐 봅시다. 본래 main의 두번째 인자는 char **형이어야 합니다. 그리고 실제로 Z0 앞에는 항상 (z*), 즉 (char **)라고 캐스팅을 해서 쓰고 있습니다. 따라서 Z0의 인자는 원래대로 돌릴 수 있겠죠.

int O;
int o;
int _ = 33303285;

int main(int b, char **Z0)
{
    char *Z;
    O = time(&b) % 0250600;
    Z = *Z0;
    for (b = 5; b >= 0; b--) {
        *(Z+b) = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
    }
    write(1, *Z0, 9);
    return 0;
}

이제 b와 Z0의 이름을 멀쩡하게 고치면,

int O;
int o;
int _ = 33303285;

int main(int argc, char **argv)
{
    char *Z;
    O = time(&argc) % 0250600;
    Z = *argv;
    for (argc = 5; argc >= 0; argc--) {
        *(Z+argc) = O % (o = (_%25)) + '0';
        O /= o;
        _ /= 25;
    }
    write(1, *argv, 9);
    return 0;
}

이제 루프 안쪽을 파헤쳐 봅시다. 먼저 *(Z+b)는 문자열 Z를 b만큼 이동시킨 위치에 있는 문자니 Z[b]와 같고, (o = (_%25))라는 식은 바깥 문장으로 바꿔도 되겠군요.

int O;
int o;
int _ = 33303285;

int main(int argc, char **argv)
{
    char *Z;
    O = time(&argc) % 0250600;
    Z = *argv;
    for (argc = 5; argc >= 0; argc--) {
        o = _ % 25;
        Z[argc] = O % o + '0';
        O /= o;
        _ /= 25;
    }
    write(1, *argv, 9);
    return 0;
}

루프 횟수가 고정되어 있으니, 이제 루프를 실제로 돌려 보면서 각 값이 어떻게 되는지 확인해 봅시다. 각 변수의 값은 해당 루프를 모두 끝낸 뒤의 값입니다.

`argc`	`o`	`_`
(루프 시작 전)	-	33303285
0	10	1332131
1	6	53285
2	10	2131
3	6	85
4	10	3
5	3	0

o가 취하는 값은 항상 정해져 있습니다. 위의 코드를 다시 보면 _가 25진수로 쓰여져 있고, o에는 1의 자리부터 순서대로 대입된다고 해석할 수도 있겠습니다. 이제 이걸 배열로 고치도록 하죠.

int O;
int o;
int arr[] = {10, 6, 10, 6, 10, 3};

int main(int argc, char **argv)
{
    char *Z;
    O = time(&argc) % 0250600;
    Z = *argv;
    for (argc = 5; argc >= 0; argc--) {
        o = arr[argc];
        Z[argc] = O % o + '0';
        O /= o;
    }
    write(1, *argv, 9);
    return 0;
}

그럼 o의 값은 무엇일까요? 그 전에 지금껏 O의 값에 대해서는 생각해 보지 않았군요.

O는 처음에 time(&b) % 0250600으로 설정됩니다. time(&b)의 반환값은 현재 유닉스 타임스탬프(UNIX timestamp)로 1970년 1월 1일 자정(UTC)으로부터 지난 초의 숫자를 나타냅니다. 이 글을 쓰고 있는 시점에서 유닉스 타임스탬프는 대략 1232400000 정도 되겠습니다. 그 다음 0250600은 8진수인데, 이는 10진수로 86400입니다. 이제 감이 잡히시지 않습니까?

유닉스 타임스탬프는 UTC로 자정이 될 때 86400으로 나눠 떨어지는 성질을 갖고 있습니다. (원점이 그렇게 설정되었습니다.) 즉 유닉스 타임스탬프를 86400으로 나눈 나머지는 자정으로부터 지난 시간을 초 단위로 나타낸 것입니다. 이 시간을 일단 d라고 해 봅시다. 지금 시각이 12:34:56이라고 하고 d를 구하면 이 값은 45296이 됩니다. 이제 이걸 10, 6, 10, 6, 10, 3으로 나눠 나머지를 취하면,

원래 `d`	나중 `d`	나머지
45296	4529	6
4529	754	5
754	75	4
75	12	3
12	1	2
1	0	1

나머지는 6, 5, 4, 3, 2, 1이 되고, 이걸 뒤집어 읽으면 1, 2, 3, 4, 5, 6으로 시각을 시, 분, 초 단위로 나타낸 결과가 됩니다! 따라서 이 프로그램은 상당히 어려운(...) 방법으로 현재 시각을 알려 주는 것입니다.

이제 루프가 어떻게 동작하는지 알았고, 루프가 정확히 6번 실행된다는 것도 알고 있으니 그냥 루프를 없애고 미리 알려진 상수로 코드를 정리하겠습니다. 하는 김에 변수 이름도 정리하죠.

int main(int argc, char **argv)
{
    char *buf;
    int t;

    t = time(&argc) % 86400;
    buf = *argv;

    buf[5] = '0' + t % 10; t /= 10;
    buf[4] = '0' + t % 6; t /= 6;
    buf[3] = '0' + t % 10; t /= 10;
    buf[2] = '0' + t % 6; t /= 6;
    buf[1] = '0' + t % 10; t /= 10;
    buf[0] = '0' + t % 3; t /= 3;

    write(1, buf, 9); /* buf == *argv이므로 */
    return 0;
}

이제 마지막 수수께끼는 write(1, buf, 9) 호출입니다. 이 함수는 유닉스 표준에 정의된 함수로 지정된 파일 서술자(이 경우 1, 즉 표준 출력)에 정해진 버퍼(이 경우 buf)의 내용을 정해진 길이(이 경우 9바이트)만큼 읽어서 출력합니다. 문제는, 우리는 buf의 첫 여섯 바이트는 초기화했지만 나머지 세 바이트는 초기화하지 않았다는 사실입니다. 혹시 buf에 널 문자가 있으면 거기서 끊기는 게 아닐까 생각할 수 있지만, write에는 그런 기능이 없을 뿐만 아니라 그럴 거였으면 애초에 길이를 지정할 이유도 없죠. 나머지 세 바이트는 어디서 왔을까요?

정답은 운영체제마다 다릅니다. buf, 즉 argv[0]의 길이가 9바이트 이상이면 일곱번째 바이트부터 아홉번째 바이트가 출력되고, 위에서 ./SHOWUTCCLOCK으로 호출할 때가 바로 이 경우에 속합니다. 만약 8바이트이면 아홉번째 바이트는 널 문자가 될 것이고요. (write는 널 문자를 특별하게 처리하지 않습니다.) 문제는 8바이트보다 작은 경우인데, 이 경우 원래 문자열의 바깥에 있는 문자를 출력하게 됩니다. 따라서 일부 운영체제에서는 이 때 아무 값이나 출력될 수도 있습니다.

이 프로그램이 웬만한 운영체제에서 동작하는 이유는 argv 배열이 저장되는 방식에 있습니다. 리눅스 등에서 argv[0]과 argv[1], ... 등의 문자열은 사실 다음과 같이 저장됩니다.

"<progname>\0<argument 1>\0<argument 2>\0...\0<argument N>\0\0"

그리고 각 문자열이 시작하는 포인터들을 argv 배열에 저장하게 됩니다. 따라서 프로그램 이름이 정확히 다섯 글자이면, 여섯 바이트를 덮어 씌운 뒤 나머지 세 바이트는 첫 인자의 첫 세 바이트에서 따오게 됩니다. 이것이 stein UTC와 같은 인자가 작동하는 이유입니다.

언제나 그렇듯 이런 코드는 위험하며, 재수 없으면 보안 상에 큰 위험으로 작용할 수도 있습니다. (이런 문제점을 공격하는 기법을 흔히 버퍼 오버플로우[buffer overflow] 익스플로잇이라 하죠.) 이런 코드가 허용되는 것은 IOCCC 뿐임을 다시 한 번 기억합시다.

TODO 이거 설명을 써야 하는데... ↩