IOCCC 2015 endoh2.cの仕組み

IOCCC 2015で公開されているendoh2.cの仕組みを確認した時のメモです。

IOCCCというのはThe International Obfuscated C Code Contest(国際難読化Cコードコンテスト)の略で

デモ動画

endoh2.cがどんなプログラムかは、下記のYoutube動画をみるとわかりやすいです。

動作の確認

動画でイメーシが掴めたら、実際に手元の環境で再現してみます。
今回はDockerでcentos7のコンテナを作って試しました。

まずは、準備としてdockerコンテナを作ってソースを取得します。

# 起動
$ docker run --name endoh2 -it centos:centos7 /bin/bash

# パッケージのインストール
[root@2bc6df9fb819 ~]# yum install wget gcc -y
...
Installed:
  gcc.x86_64 0:4.8.5-36.el7                                                          wget.x86_64 0:1.14-18.el7

Dependency Installed:
  cpp.x86_64 0:4.8.5-36.el7           glibc-devel.x86_64 0:2.17-260.el7       glibc-headers.x86_64 0:2.17-260.el7       kernel-headers.x86_64 0:3.10.0-957.1.3.el7
  libgomp.x86_64 0:4.8.5-36.el7       libmpc.x86_64 0:1.0.1-3.el7             mpfr.x86_64 0:3.1.1-4.el7

Complete!


# ソースのダウンロード
[root@2bc6df9fb819 ~]# wget http://ioccc.org/2015/endoh2/prog.c
--2018-12-15 08:34:04--  http://ioccc.org/2015/endoh2/prog.c
Resolving ioccc.org (ioccc.org)... 206.197.161.153
Connecting to ioccc.org (ioccc.org)|206.197.161.153|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 829 [text/plain]
Saving to: 'prog.c'

100%[==============================================================================================================================>] 829         --.-K/s   in 0s

2018-12-15 08:34:04 (15.7 MB/s) - 'prog.c' saved [829/829]

ダウンロードしたファイルをcatで表示させると、確かにHello worldが出力されるソースが表示されます。

[root@2bc6df9fb819 ~]# cat prog.c
int main(){ printf("Hello, world!\n"); }

gccでコンパイルして実行すると、なぜか"Hello, world!"の文字ではなく、元のソースコードが出力されます。

[root@2bc6df9fb819 ~]# gcc -w -o prog prog.c
[root@2bc6df9fb819 ~]# ./prog
int main(){ printf("Hello, world!\n"); }

仕方がないので結果をtmp.cの名前で別ファイルに出力し、その結果をコンパイルすると、またソースコードが主力されます???

[root@2bc6df9fb819 ~]# ./prog > tmp.c
[root@2bc6df9fb819 ~]# gcc -w -o tmp tmp.c
[root@2bc6df9fb819 ~]# ./tmp
int main(){ printf("Hello, world!\n"); }

種明かし

作成した2ファイルですが、ls -lでファイルサイズを調べてみると829byteもあります。
先ほどcatした結果は40文字しかないのでこれはおかしいです。

[root@2bc6df9fb819 ~]# ls -l *.c
-rw-r--r-- 1 root root 829 May  7  2018 prog.c
-rw-r--r-- 1 root root 829 Dec 15 08:38 tmp.c

ファイの中身を16進ダンプするとファイル中身をみることができます。

[root@2bc6df9fb819 ~]# cat prog.c | od -t x1
0000000 69 6e 74 20 6d 61 69 6e 28 29 7b 20 70 72 69 6e
0000020 74 66 28 22 22 29 3b 7b 63 68 61 72 2a 70 2c 73
0000040 5b 39 39 39 5d 3d 22 69 08 08 08 08 08 08 08 08
0000060 08 08 08 08 08 08 08 08 08 08 08 08 08 6e 74 20
0000100 6d 61 69 6e 28 29 7b 20 70 72 69 6e 74 66 28 7e
0000120 7e 29 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0000140 08 08 08 08 08 08 08 3b 7b 63 68 61 72 2a 70 2c
0000160 73 5b 39 39 39 5d 3d 7e 25 73 08 08 08 08 08 08
0000200 08 08 08 08 08 08 08 08 08 08 08 08 08 7e 2c 2a
0000220 71 3d 73 2c 63 3b 66 6f 72 28 70 3d 36 32 2a 2a
0000240 7e 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0000260 08 08 08 08 08 7e 2b 71 3b 71 3c 73 2b 34 33 35
0000300 3b 63 3d 71 2d 73 3e 2a 7e 73 08 08 08 08 08 08
0000320 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 7e
0000340 7c 7c 63 3e 38 3f 2a 70 2b 2b 3d 63 2d 33 35 3f
0000360 2a 7e 7d 08 08 08 08 08 08 08 08 08 08 08 08 08
0000400 08 08 08 08 08 08 08 7e 3c 63 3f 33 34 3a 63 3a
0000420 39 32 3a 30 2c 70 5b 2a 7e 08 08 08 08 08 08 08
0000440 08 08 08 08 08 08 08 08 08 08 08 7e 5d 3d 30 29
0000460 63 3d 2a 71 2b 2b 3b 2a 70 3d 32 2b 2a 7e 08 08
0000500 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0000520 08 7e 3b 70 72 69 6e 74 66 28 73 2b 36 32 2a 2a
0000540 7e 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0000560 08 7e 2c 73 29 3b 7d 72 65 74 75 72 6e 28 2a 7e
0000600 23 30 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0000620 08 08 5f 08 48 08 48 5f 08 65 08 65 5f 08 6c 08
0000640 6c 5f 08 6c 08 6c 5f 08 6f 08 6f 5f 08 2c 08 2c
0000660 5f 08 20 08 20 5f 08 77 08 77 5f 08 6f 08 6f 5f
0000700 08 72 08 72 5f 08 6c 08 6c 5f 08 64 08 64 5f 08
0000720 21 08 21 23 6e 7e 29 3b 20 7d 08 08 08 08 08 08
0000740 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 22
0000760 2c 2a 71 3d 73 2c 63 3b 66 6f 72 28 70 3d 36 32
0001000 2a 2a 22 08 08 08 08 08 08 08 08 08 08 08 08 08
0001020 08 08 08 08 08 08 08 22 2b 71 3b 71 3c 73 2b 34
0001040 33 35 3b 63 3d 71 2d 73 3e 2a 22 73 08 08 08 08
0001060 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0001100 08 22 7c 7c 63 3e 38 3f 2a 70 2b 2b 3d 63 2d 33
0001120 35 3f 2a 22 7d 08 08 08 08 08 08 08 08 08 08 08
0001140 08 08 08 08 08 08 08 08 08 22 3c 63 3f 33 34 3a
0001160 63 3a 39 32 3a 30 2c 70 5b 2a 22 08 08 08 08 08
0001200 08 08 08 08 08 08 08 08 08 08 08 08 08 22 5d 3d
0001220 30 29 63 3d 2a 71 2b 2b 3b 2a 70 3d 32 2b 2a 22
0001240 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08 08
0001260 08 08 08 22 3b 70 72 69 6e 74 66 28 73 2b 36 32
0001300 2a 2a 22 08 08 08 08 08 08 08 08 08 08 08 08 08
0001320 08 08 08 22 2c 73 29 3b 7d 72 65 74 75 72 6e 28
0001340 2a 22 5c 30 08 08 08 08 08 08 08 08 08 08 08 08
0001360 08 08 08 08 5f 08 48 08 48 5f 08 65 08 65 5f 08
0001400 6c 08 6c 5f 08 6c 08 6c 5f 08 6f 08 6f 5f 08 2c
0001420 08 2c 5f 08 20 08 20 5f 08 77 08 77 5f 08 6f 08
0001440 6f 5f 08 72 08 72 5f 08 6c 08 6c 5f 08 64 08 64
0001460 5f 08 21 08 21 5c 6e 22 29 3b 20 7d 0a

結果を眺めてみると、妙に08の表示が多いことに気づきます。asciiコード表で0x08は何かを調べてみるとBackSpaceの文字コードだということがわかりました。

catコマンドはbackspaceの文字コードを解釈するので、一部の文字が消されて結果としてprintf()だけのプログラムが出力されていたという仕組みでした。

元のコードをチェックする

それでは元のソースコードはどうなっているのでしょうか?

確認のため、prog.cから0x08のbackspace文字を取り除いてファイルの中身をみてみます。今回は0x08の文字を除去するのにsedを使いました。

[root@2bc6df9fb819 ~]# sed prog.c -e "s/\x08//g"
int main(){ printf("");{char*p,s[999]="int main(){ printf(~~);{char*p,s[999]=~%s~,*q=s,c;for(p=62**~~+q;q<s+435;c=q-s>*~s~||c>8?*p++=c-35?*~}~<c?34:c:92:0,p[*~~]=0)c=*q++;*p=2+*~~;printf(s+62**~~,s);}return(*~#0_HH_ee_ll_ll_oo_,,_  _ww_oo_rr_ll_dd_!!#n~); }",*q=s,c;for(p=62**""+q;q<s+435;c=q-s>*"s"||c>8?*p++=c-35?*"}"<c?34:c:92:0,p[*""]=0)c=*q++;*p=2+*"";printf(s+62**"",s);}return(*"\0_HH_ee_ll_ll_oo_,,_  _ww_oo_rr_ll_dd_!!\n"); }

すると、上記のようにコードの本体が出力されてきました。

このままでは読みづらいので適当にインデントを入れてみます。

int main(){ 
    printf("");
    {
        char *p, s[999]="int main(){ printf(~~);{char*p,s[999]=~%s~,*q=s,c;for(p=62**~~+q;q<s+435;c=q-s>*~s~||c>8?*p++=c-35?*~}~<c?34:c:92:0,p[*~~]=0)c=*q++;*p=2+*~~;printf(s+62**~~,s);}return(*~#0_HH_ee_ll_ll_oo_,,_  _ww_oo_rr_ll_dd_!!#n~); }", *q=s, c;

        for( p = 62 * *"" + q; q<s+435; c = q-s > *"s" || c>8 ? *p++ = c-35?*"}" < c ? 34 : c : 92 : 0, p[*""] = 0 )
            c = *q++;

        *p = 2 + *"";
        printf(s+62**"",s);
    }
    return(*"\0_HH_ee_ll_ll_oo_,,_  _ww_oo_rr_ll_dd_!!\n");
}

ざっくり概要を説明すると、sという文字配列に元のソースコードを再現できるタネが入っていて、これをforで加工したのちprintfで出力するという仕組みです。

gccでこのプログラムを実行すると、元のソースコードをstdoutに出力するプログラムが出来上がります。このように、自分自身のソースコードを出力するプログラムのことをQuine(クワイン)と言います。

"元のソースコードを"と書いたのですが本当に元のソースコードを出力しているかは、以下のように16進ダンプをdiffしてみるとわかります。

[root@2bc6df9fb819 ~]# od prog.c -t x1 > prog.hexk
[root@2bc6df9fb819 ~]# od tmp.c -t x1  > tmp.hex
[root@2bc6df9fb819 ~]# diff prog.hex tmp.hex

diffの結果が出力されなかったので、

後始末

作ったdocker環境はdocker rmコマンドで削除しておきます

[root@2bc6df9fb819 ~]# exit
exit

$ docker ps -a
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS                      PORTS               NAMES
2bc6df9fb819        centos:centos7      "/bin/bash"              About an hour ago   Exited (0) 9 seconds ago                        endoh2

$ docker rm endoh2
endoh2

Amazonでおトクに買い物する方法