まえがき
与えられた入出力を満たすプログラムをなるべく短いバイト数で実現する遊びをショートコーディングまたはコードゴルフと呼ぶ。 後者の名前は、普通のゴルフがなるべく短い打数（stroke）でゴールを目指すことになぞらえてなるべく短いキータイプ（stroke）でプログラムを書くことを表現しているらしい。
C 言語でのコードゴルフで自分が非常に好きな（知った当時とても感銘を受けた）テクニックとして、「ソースコード中に直接バイナリを埋め込む」というものがある。 C のコードゴルフはルール上ソースコードをコンパイラにかけるのでバイナリを直接回答とすることはできないが、
- C 言語での関数呼び出しは単なるバイナリへのジャンプである
- C 言語では文字列リテラルは実行可能ファイルに直接バイナリとして埋め込まれる
ことを考える*1と、「文字列リテラルへのポインタを関数として呼び出す」ことが可能である。
このテクニックを利用して qsort 関数の呼び出しを短いバイト数で実現する方法がこのPDFの 5.3 に載っている*2。
この記事ではセキュリティのためのメモリ保護の影響でこのテクニックは残念ながら今の Linux ではそのままでは動作しないことを紹介する。
埋め込むバイナリの準備
まずセキュリティの前に x86 と x86_64 の関数呼び出し規約の違いにより、前述の PDF のコードはそのままでは動かない。 x86 では関数の引数はスタックに push して渡すことになっているが、 x86_64 では最初の 4 つの引数はレジスタで渡すことになっているためである。 そこで以下の C コードをまず x86_64 のマシン上で普通にコンパイルして出てきたバイナリを埋め込むことにする。
cmp(int*a,int*b){ return*a-*b; }
この関数を gcc -O3 でコンパイルすると、次のような非常に簡明なバイナリになる。
引数が rdi レジスタと rsi レジスタで渡されるので、それらの差を取って return している。
先頭の endbr64 も今回紹介するのとはまた別のセキュリティ機能だが、今は考えないことにする。
0: f3 0f 1e fa endbr64 4: 8b 07 mov (%rdi),%eax 6: 2b 06 sub (%rsi),%eax 8: c3 retq
バイナリを素直に埋め込む
出てきたバイナリを前述の PDF の 5.3 にあるように文字列としてプログラム中に埋め込むと、以下のようになる（#include ... は省略する）。
見やすさのために qsort の引数に直接文字列を渡さずにグローバル変数にしているが本質は変わらない。
char* s= "\xf3\xf\x1e\fa\x8b\a+\x6\xc3"; int main() { int array[] = {3, 1, 2}, size = 3; qsort(array, size, sizeof(int), s); printf("%d %d %d\n", array[0], array[1], array[2]); return 0; }
このソースコードをコンパイルして実行すると、残念ながら以下のように落ちてしまう。
$ gcc test.c (いろいろ警告が出るが関係ないので省略) $ ./a.out Segmentation fault (コアダンプ)
なぜ落ちるか？
前述のプログラムが Segmentation fault になる原因は、通称 W ^ X と呼ばれるセキュリティのためのメモリ保護である。 W ^ X とは、あるメモリページは書き込み可能（Writable）か実行可能（eXecutable）のどちらか一方のみに設定し、両方同時には設定しないようにするという方策のことで、英語の Wikipedia にも説明記事がある（残念ながら日本語はない）。 "^" という表記は xor の意味で、W か X かどちらかのみが 1 だというニュアンスである。
W ^ X は例えばスタック上のバッファにコードを送り込み実行させる攻撃の対策として有効である。
スタック上の値（array や size）はデータでありコードではない「はず」である。
よって読み書きをする可能性はあるが実行される可能性はなく、仮に実行されればそれは恐らく攻撃である。
そこでスタックを格納するメモリページはページテーブル上の管理ビットを writable かつ not executable に設定する。
当然 "\xf3 ... " のような文字列リテラルもデータでありコードではない「はず」なので、
それを格納するメモリページも not executable に設定される（文字列リテラルの場合は書き込みもできない点がスタックとは異なる）。
今回は実行できないメモリページにあるものを無理やり実行しようとしたので Segmentation fault が起きた。
読み書き可能かつ実行可能にすれば動く
呼び出したいバイナリが置かれたメモリページが実行不可能なのが悪いので、「読み書き可能」かつ「実行可能」なメモリ領域を作りそこにバイナリを置けば想定通り動く。
このようなメモリ領域は mmap 関数の第 3 引数に PROT_EXEC と PROT_READ と PROT_WRITE を同時に指定することで確保できる。
前から順に、確保するメモリ領域が実行可能であること、読み込み可能であること、書き込み可能であることを示す。
以上を踏まえ、結局次のようなコードであれば期待通りの動作をする（#include ... は省略する）。
code が実行可能かつ読み書き可能なメモリ領域で、埋め込みたいバイナリをその領域にコピーしてから呼び出している。
mmap の呼び出しがかなり長いので、残念ながらコードゴルフに使うのは難しそうである。
NULL や PROT_EXEC などをベタ書きしても void*c=mmap(0,99,7,34,0,0); とかなり長い。
unsigned char* s= "\xf3\xf\x1e\fa\x8b\a+\x6\xc3"; int main() { int array[] = {3, 1, 2}, size = 3; void* code = mmap(NULL, 4096, PROT_EXEC | PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0); memcpy(code, s, strlen(s)); qsort(array, size, sizeof(int), code); printf("%d %d %d\n", array[0], array[1], array[2]); return 0; }
このコードをコンパイルし実行すると、以下のように見事 array の中身が整列される。
$ gcc test.c $ ./a.out 1 2 3
