Balanced use of obfuscation - Gold award

バランスの良い難読化の使い方 - 金賞

受賞者：Adar Zeitak

動作・解説にジャンプ

引用元：https://www.ioccc.org/2012/zeitak/zeitak.c

審査員・作者による説明：https://www.ioccc.org/2012/zeitak/hint.html

動作

カッコの対応をチェックしてくれるツール。

$ cat incorrect.c
#include <stdio.h>

int main() {
        int i=40;
        printf("%c",(char)(i)));
        return 0;
}

$ gcc -o zeitak zeitak.c

$ ./zeitak < incorrect.c
));

 ^ Error

元ソースコードはカッコが乱用されていて非常にややこしいが、ちゃんとチェックが通る。

$ ./zeitak < zeitak.c
OK

解説

コード形状は、タブ幅4で見る必要がある。 左右に丸カッコ()、上下に横向きにかぎカッコ[]と波カッコ{}が配置されていて、その真ん中に小さくイコールがある。 つまり、カッコの対応が取れていることを表現している。

コードは次の制限を課して書かれている。

残るは、関数呼び出し、キャスト、配列・ポインタ、とのこと。

文字列リテラルの中にあるカッコは無視するようにしているとのことだが、文字列リテラルの中で\"を使っている可能性までは考慮していない。

挙動が比較的単純なので見逃しがちだが、この実装はIOCCCの中でも最悪レベルの難読度だと思う。 腕に覚えがある人は、ぜひ自分で解読を試みてほしい。 以下、解析の結果わかったことを記す。

大まかなアイデアとしては、ASCIIコードでテーブルをルックアップすることで分岐を行う。 しかし、そのアイデアがわかってもメイン処理を読み解くまでには非常に遠い。

難読化の中心は、次の2つの関数からなる。

数字を使わないという制約のために、これらの関数を1と0の代わりに使っている。 ほとんどの変数には__または_が入っている（変数rだけは、__と_に加えて再帰のためにfが入ることもあるので注意）。

制御構造や比較を使わずに値を選択するのも、これらの関数が肝になっている。 変数xに__または_が入っているとき、x(A,B)という式は、x==__ならAに、x==_ならBになる。 つまり、これが値の選択として使える（ただし、x(A,B)ではAもBも必ず評価されることには注意する必要がある）。 変数xをビット反転するにはx(_,__)として呼び出す。

ほぼすべての処理は関数fで行われる。 この関数はかんたんに言えば、1文字読み込み、期待する閉じカッコが来るかどうかを検査する。 関数fは引数aとbを取るが、これは現在期待している閉じカッコの種類を表している。

なお、a == __かつb == __ならば、すでにカッコの対応が取れていないことが判明していて、当該箇所をもう2文字出力するための余分な再帰を行っている状態を表している。

関数fは、文字を読み込んだら、ルックアップテーブルであるlを文字コードで引いて、文字種を表すデータ構造（後述）を変数dに読み込み、それに応じて処理を振り分ける。

実際には、シングルクォートやダブルクォートの場合の処理も行う。非常にややこしい。

最後に、これみよがしに定義されているstructについて。

typedef struct s { struct s* a	   ; struct s* UNUSED; } s;
typedef struct t { struct s* UNUSED; struct s* a	 ; } *t;

UNUSEDというフィールドはアクセスされないが、これはキャストを通してアクセスする。 s型の値から.aのフィールドを読み出すと1つめが得られるが、tにキャストしてから.aを読み出すと2つめが取り出せる。

mainから読み始めると、関数Cがこの2要素のstructをmalloc()しているので、Lispのコンスセルであることに気づく。 よって、非常に重要な役割をあたしているのかと思わせるが、これはひっかけであり、関数Cはmainの中でしか使われていない（関数fの中では、ローカル変数としてCが再定義されている）。 この2要素のstructは、上述の文字種を表すデータ構造と、グローバル変数として使われているだけである。

文字種を表すデータ構造は、2要素のstructを2段にネストして使っており、各要素には__か_のどちらが入るので、4ビットの情報となっている。 各ビットをABCDとして、次のように解釈される。

グローバル変数wは、2要素のstructを3段にネストして使っているので、8ビットの情報になっているが、見落としがなければ4ビットしか使っていないと思う。 1ビットめは最初のカッコに到達したかどうかのフラグ、2ビットめはおそらくクォートの種別、3ビットめと4ビットめはエラー状態だと思う。 このあたりは解析を簡単にするために無視したので、やや自信がない。