Brainf*ckを、直接実行可能バイナリにコンパイルした話

なんとなくカレンダーを埋めたいという衝動に駆られるので記事を書きます。

おととい書いたELFを書く話によって、僕らは事実上任意の機械語列をELFにすることができるようになりました。次は、当然任意のBrainf*ckで書かれたプログラムをコンパイルできるようになるべきです。

つまり今度の目標は、「与えられたBrainf*ckのプログラムを実行可能なELFに変換する」ということになります。

コンパイラというと、実際は、機械語を直接吐き出すのではなく、一度アセンブリ言語やなんらかの中間言語を生成して、そのあとでアセンブラ等によって機械語を吐き出すという形なものが書きやすく一般的(一般性を十分担保できるほど僕はコンパイラの実装を読んでいないが)な気がしますが、今回は、bfのコードを受け取って直接機械語に翻訳してみようと思います。

というのも課題の指定がそうなので。課題ではコンパイラそのものもアセンブリ言語で書く必要がありますが、とりあえず方針を立てる意味でもPythonで書いてみようと思います。またPowerPCではなくx86-64上のLinuxで動くプログラムについて考えます(なのでこの記事は課題そのものではないです)。

keystone engine

そうはいっても、吐き出す機械語をマニュアルを読んで生成するのはさすがに億劫なので、keystone engineという、CTFしているとたまに見かけるAssembly Frameworkの力を借ります。実際これで遊んでみたのを記録にしようと思っただけという話でもあります。

Keystoneを使うと次のように、アセンブリを対応する機械語に変換してくれます。

In [2]: from keystone import *

In [3]: ks = Ks(KS_ARCH_X86, KS_MODE_64)

In [4]: def asm(code):
   ...:     c, _ = ks.asm(code)
   ...:     return ''.join([chr(x) for x in c])
   ...:

In [5]: asm("mov rax, 1")
Out[5]: 'H\xc7\xc0\x01\x00\x00\x00'

In [6]: asm("nop")
Out[6]: '\x90'

In [7]: asm("jmp 0")
Out[7]: '\xeb\xfe'

書いたもの

現状はこんな感じで書いています。bfの仕様としては、とりあえず、めんどいのでメモリは100000バイトの領域を0x900000からmmapで確保するという適当なことをしてはいます。当然領域外へ出たら壊れます。 ここらへんちゃんとELF上に書いておけばいい話ではあるんですが、それをやるよりmmapした方が(書くのが)速いし、全体のサイズが小さいという話があるので、まぁ気が向いたらみたいなところが強い

あとはこれをアセンブリで書き出すだけではありますが、面倒なので気合いが出ればやろうという感じ

実行

せっかくなので、いくつかのbfのコードを実際にコンパイルしてみました。例えば、先日のesolangのCodeGolf大会で、@satosさんが書いた「与えられた2進数が三角数かどうか判定」するプログラムを実際に実行してみました(回答自体はTSGのGithubからみられます)。

ubuntu@ubuntu-xenial:~/ctf/experiment$ ./bf
00000011
00110111
10100101
00011111
01011001
10010100
00111100
01101000
11001000
01011011
10001000
10111110
01000010
01110011
10011001
10101100
00001010
01101001
00101101
11111101
11100111
00001000
00001111
10101011
00110010
11110111
00011100
11110110
00000000
10110001
01111000
00100011
01001110
10010000
00000110
00000001
00110011
00010101
10000101
11010010
00010101
01111101
00100001
01011010
00101110
11001010
11100000
00100100
10111110
00111110
11000000011110101111101100101010101101011000000110

一応正しく動いていそうです。

ちなみにコンパイルしたあとのバイナリをディスアセンブルすると、

enter image description here

こんな感じになります。Rev問だったら地獄ですね?

実際、同じ処理をペタペタ貼り付けているだけなので、ここらへんもう少し効率化とかすると楽しいかもしれません。