CSAW CTF 2014
https://ctf.isis.poly.edu/scoreboard
前回 (HITCON CTF 2014) 参加した時に、これは面白いけど一人でやると真剣にしんどいなーと思ったので、まわりの人を適当に誘ってチームで参加してみました。名前のアイデアが誰もなかったので、僕が適当に決めた nop-or という名前で。由来は自社名。
僕は真剣にやるけど他の人は暇な時に適当でよいよーというスタンスだったんだけど、妙に真剣に参加してくれる人が多くて、結果は13位。予想より良い結果だったと思う。
残った問題は cryptography * 2 と recon * 2 だけ。チームが全部解けてると、 write-up 見なくてもどういう問題でどう解いたのか勉強が終了してて、それも良いなと思った。
メンバーは僕以外は全員初参加で、7人くらいいたんだっけ？ ksnctf を紹介してあった人もいたので、少しだけ練習した人もいたけど、そういう人達は一生懸命 "FLAG_" という文字列を探してたりして、むしろ練習は逆効果だったのではないか。
僕は簡単な問題は初参加の人たちが景気付けに解いてくれるだろーという期待のもと、バイナリばかり読んでた。初参加の人が楽しめるようにという少しの配慮と、自分がバイナリだけ読みたいという本音が混じった一石二鳥の作戦だった。あとで思うに別に少しの配慮はいらなかった。
時系列で
saturn (Exploitation 400)
ほどほどに難しそうなやつ、てことで400。もう内容覚えてないけど3つくらいコマンドがあって、1つ目のコマンドで得た情報を2つ目にわたすと良いとかそんなだっけ。超簡単で、なんだこのコンテストレベル低いて聞いてたけど低すぎないか…と思ってたが、後になって思うとほどほどに難しかった。むしろ例年よりは難化していたらしい。
trivia 10 一問を他の人が解いた直後がこれということで、簡単さがしのばれます。というか他の人が起きてくるころには解けてたと思う…
pybabbies (Exploitation 200)
これは他の人がやると良さそうな問題だなーと思ってたら、まさに向いてそうな @phoenixstarhiro が起きてきたので、やってみたら、と勧めてみたらサックリと解いておでかけしに行った。かっこいい。
s3 (Exploitation 300)
ish も見てたのだけど、どうも s3 の方が簡単な気がしてきたのでこっちにシフト。 key value store を CUI で操作する。
あまり理屈はわかってないけど、作ったキーを更新してから表示すると、何故か最初に渡した文字列におもむろに call してくれるという問題だった。やることは簡単だけど、コードがでかくて読むのがめんどくさかったなあと思った。
やること簡単と言いつつ、 x86-64 の shellcode を書くのに少しだけ時間がかかっていかんなと思った。 syscall のかわりに int 0x80 と書いたりとね…
dumpster diving (Forensics 100)
起きてきた @mayahjp が Firefox のコアがーとか言ってる。コアか少し面白そうだな解くのは任せるにしても、問題の雰囲気見てみるかと objdump -s してみる…と flag{...} があって解けてしまった。 "FLAG_" を探していたらしい…
Obscurity (Forensics 200)
@mayahjp がマウスドラッグしたらフラグあった楽勝とか言ってた。おいこれなんで 200 なんだと思った。
why not sftp? (Forensics 200)
@mayahjp が wireshark の使いかたを理解して瞬殺した。おいこれなんで略。
bo (Exploitation 100)
これも strings で瞬殺されてた。実行する必要すら無いてすごい。
Big Data (Networking 100)
@mayahjp が wireshark ながめてログの文字つないでいけば良いと気付いたぽい。今思うとこの人エスパー力問われる問題の悪口言いながらエスパー力問題ばっか解いてるな、ツンデレかな…
eggshells (Reverse Engineering 100)
fork bomb が入ってるので、二人くらいのマシンが破壊される。誰だったかが utils.pyc を strings して終了。 strings で 3 問解けるとか…
psifer school (Cryptography 200)
明らかに簡単な問題が解かれ終わって、 free lunch is over なムードになったころ、少しずつ進めていた omoikane さんが解く。暗号 3 つ詰め合わせって感じ？
ish (Exploitation 300)
ish わからないな、スタックの一部を表示させることはできるんだけど、どうやってもスタックずれないような？と思ってた。少し寝て起きたあと、いややっぱ明らかにスタックの一部を表示させることができるんだから、どっかずらせる場所あるだろうと思ったら意味不明に alloca ぽいことしてる場所があったので、適当にずらせると判明。
わかってからも適切な調整が結構大変だった。まぁ良い問題だったのかなと思うんだけど、コードやけに大きいなぁというのと、 shell 実行したいな…と思うのとで不満気味であった。
csaw2013reversing2.exe (Reverse Engineering 200)
おにゅーのマシンを買ってきたとか言ってた @ttuusskk が別におにゅーじゃない Windows で windbg で step 実行しながらメモリ見てたらあったとか言って解いた。
wololo (Exploitation 400)
地道に iOS 用ぽい ARM コードを gas に喰わせられるように変換できるスクリプトを書いて、あとは実行しながらデータベースを調整していったら解けた。変換なんてしなくても読めばわかる気もするんだけど、動いてるものが無いものを考えるの苦手なんだよな。よく考えるとコード読みとかも gdb 使ってやるとか結構多い。
Julian Cohen (Recon 100)
@mayahjp が起きたらヒントが出てたとかで、アカウント作って解いた。
aerosol can (Reverse Engineering 500)
この問題は大変だけどやるだけの問題に見えて、そのやるだけ度が簡単そうなら解いちゃおう、と僕も見てたのだけど、その大変度合いがすさまじそうだったので、早い段階で放棄した。そしたら @phoenixstarhiro が根性で解いた。正直時間内に解けないかもな、と思ってたので、やはりこの人の根性はすごいなと思った。
greenhornd (Exploitation 400)
いやーしんどかった。バグの位置は教えてくれてるので、ちょっとしたチェックを理解すれば、あとはちょっと ROP してメモリ確保してから shellcode を渡すだけなんだけど、なんせ Windows なんだ…
例のごとく exe を linux のメモリ空間に mmap して実行したいとこだけ実行できるようにしながら、任意コード実行できるようにした。
shellcode は shell-storm で適当に拾ってきた cmd.exe 動かすやつだとうまく使えなくて、まぁ AppJailLauncher てのがシステムコールをいくつかつぶしていて、問題に書いてある通り ReadFile WriteFile だけで解けて趣旨なのかな、と理解した。しかしそんなことはなくて cmd.exe 動かせたらしい…
さてこれのためのコードを書くのはすごく大変だった。とりあえず kernel32.dll 内の関数の位置が EC2 で借りた Windows 2012 Server と同じ CreateFile なら動くよ、ってのを書いてみたが、本番環境では動かない。うーんまあ Windows 8 って言ってるから違うんだろうなぁと。 @ttuusskk が Windows 8 あるとのことで kernel32.dll をくれたのはいいが、どう見てもこれは 64bit バイナリでござる。
まぁ勉強もかねて Export Table 読むコード書くか、と書いた。ただ疲れていたので、無駄に時間がかかった。あと昔同じようなコード書いた記憶があるね…
そんでそれをアセンブリに手で変換。めんどくさいめんどくさい。。できた！と思うも動かない。まぁ Windows のバージョン依存はなくなっているので、自分の Windows 7 マシンで試してみると、たしかにクラッシュしている。
最初は shellcode 実行開始時点で ebp が腐っているという、自分の凡ミスだったんだけど、あとは gas の謎のバグとたたかっていた。なんでクラッシュするのーと windbg で step 実行していくとなぜか call が少しズレる。実際コード見てみるとズレてるので、なんか gas のバグだったんだと思う。 label のまわりに nop を入れまくって回避。 linux 上で windows バイナリ作って、それを windows にコピーして windbg 、ていうイテレーションがめんどくさくてめんどくさくて…
とまあ解けたけど気力が燃えつきた。
xorcise (Exploitation 500)
@tzik_tack が地道にがんばっていた。進捗を聞くと、 return address が書きかえられて、その下の stack に好きなデータを 128 byte だか書けるようになった、とか言っている。えっそれもうおわってるんじゃ…と思ってハラハラしてたんだけど、 greenhornd 終わって燃えつきかけだったので、進捗を共有してた docs を見てみる。
これはすごいなーと感心する。ループの中でループ変数が変わってて、これは大変だ、と思う。しかし感心するけど、ここまで行ったら、んーやはりこの問題終わってるように見えるよ…と手元で同じのを再現してみて、僕が pass 取れるコードを作ると同時くらいに @tzik_tack も終了。
あとはなんか簡単な手続きで flag をもらえたぽい。
hashes (Web 300)
何人かが頑張っていた。主に @mayahjp と @ttuusskk かな。 @mayahjp が jQuery が古いとか言うので、 jQuery の脆弱性を僕がぐぐってみたところ、トップに CVE 。見てみると location.hash て書いてある。これじゃね、と言ったら @mayahjp がすごい勢いで色々やって flag をもぎとっていた。
weissman (Reverse Engineering 300)
aerosol can で燃えつきてないのがすごい @phoenixstarhiro が、地道にフォーマットを解釈していって、読みにくい jpg を復元して解いた。いやー感心した。
Fluffy No More (Forensics 300)
これも主に @mayahjp と @ttuusskk が色々探してた。諦めて @mayahjp が寝たあとで、少し僕も見てみるかとファイルを展開とかしてみる。多い！こんなもん見る気起きない、とあきらめる。しかし彼らの残した記録を読んでみると、なにやら不審な pdf の URL がある。
ファイル一つなら読む気力残ってるな、と pdf に決め打ってながめる。そういえば steganography 的なの見てないな、と画像を取り出したくなった。でもよく知ってる画像のヘッダは中に無いぽい。 dff-gui とかいうファイル解析ツールにかけてみる…が、 pdf はサポートされてないぽい気がした。
うーんどういうふうに画像入ってるのかな、と中身を lv でながめてると、どうも圧縮されてるらしい記述がある。そして圧縮されててすごくサイズが小さいところとかもある。これ flag 隠しそうな場所じゃね、と思う。
deflate を自分で展開するのがめんどくさかったので、適当にぐぐって調べてみる。ねむくて珍妙なコマンドラインインターフェイスの理解に時間がかかったけど、展開できた。あとは lv でふたたびながめてると \xXX\xXX と続く不審な文字列。ちょっと見るとこれ ASCII の範囲じゃん、と irb に入れたら flag ゲット。まぁ pdf 取るところまでをやったのがえらいと思う…
cfbsum (Cryptography 300) 解けなかった
@kinaba が最初の方考えてたけどわからないまま歩きに行ってしまったので、少しだけ遊んでみたりした。最初よくわからんなーという感じだったんだけど、 CFB でぐぐると、ああこういうのがあるのかと勉強になった。 initialization vector を guess するのかな、と思って、実際それがあってたぽい？ので、早い段階で CFB というのを理解してやってみていれば…と少し悔やまれる。
Feal (Cryptography 300) 解けなかった
omoikane さんががんばってたけど解けなかったようだった。この手のやつ解けた試しがないから write-up 読もうと思う…
Recon * 2
左はよくわからない。右は dota2 ならゲームっ子として解かねば！と思って色々探したけどわからなかった。
まとめ
チームでやると負担がかなり少ないなあと感じた。一人でやると、バイナリ読みたいけど、みんなが解いてるアレをやってみた方がいいかな…とか気が散るんだよね。というかチームでプログラミングコンテストに参加したのってはじめてな気がしますね…
irbrc を書いたら ruby 1.9 とだいぶ和解できた話
いつも言ってることだけど、 ruby 1.9 からの m17n のせいで、バイナリツールとしての ruby が色々不便になって、参っていました。特に、 'a' の ASCII code を知るのに、
irb(main):001:0> 'a'[0] => "a"
とかやるクセがついてて、これで "a" と出るとか、そういう比較的どうでもいいところで参ってました。
しかしまぁどの環境も ruby 1.9 以降になってるわけで、なんとかしないとなーということで、 IRB の inspector いじって色々やってみて、結果として 1.8 時代より便利になって、最近は割と普通に使えている。
https://github.com/shinh/test/blob/master/.irbrc
何をしてるかというと、評価した結果が文字とか数値だった場合に、補助情報を色々出すようにしてある。で、
irb(main):001:0> 'a' => a (97) irb(main):002:0> 99 => 99 (0x63 'c') irb(main):003:0> 2**25 => 33554432 (0x2000000 33M) irb(main):005:0* 0xf7e04000 + 0x41060 => 4158935136 (0xf7e45060 4158M)
などなど。最初の2つは文字と数字の変換結果がついでに出てて便利みたいな話。3つ目は 33M など、数字のだいたいの大きさが出ると便利という話。最後のはアドレス計算とかで特に最近こういうのよくやるので、 16 進数出てると便利。
それ以外にも色々歴史的にちょっとずつ足している機能があって、よく使うのだと、
irb(main):016:0> (99999*29999).cint => -1295097295 (0x..fb2ce6231)
31bit overflow してる時に、 C の整数だといくつ、ってのが意外とぱっとわからなかったりするので。 cuint もあるけど、まぁそっちはあまり使わない。
irb(main):010:0> asm("xchg eax, edx")
000000 92 >.<
000001
=> nil
irb(main):011:0> disasm("\x55\x57\x31\ff")
/tmp/irb_disasm20140904-6135-1vk633j: file format binary
Disassembly of section .data:
00000000 <.data>:
0: 55 push %ebp
1: 57 push %edi
2: 31 0c 66 xor %ecx,(%esi,%eiz,2)
=> nil
HITCON CTF 2014
CTF ていう、セキュリティコンテスト的なやつ、前から少し気になってたんだけど、おすすめしてもらったこともあって初参加してみました。結果は 20 位。大変たのしかった。
リポジトリ: https://github.com/shinh/hitcon-ctf-2014
vash 10
練習的なやつ。いきなりホームディレクトリに flag てファイルがあるので、それの中身を提出してみるが、ダメ。おかしーなーと find とかして他のファイルを探してみるけど、特に何もなく。
そのうちわかるだろう、と、あまり気にせず次へいった。真相は運営のアレコレでまだ submit が動いてなかったらしい。 TLE とか ICFPC とかの脱力運営に慣れてるので、こういうのでハマらない…
rsaha
RSA を解け的な問題。ただし、通常 m^e mod n だけしか教えてもらえないはずなのに、 (m+1)^e mod n もわかる。
これは3次の項が消えるので、 e が phi(n) と互いに素という条件を満たせてなくて、ダメってことかな…と思った。正しいかは知らない。そうだとして、はてこの間違った e を選んだ時の破りかたなんてわからないぞ…と考えてた。
ついでに web service を攻撃する系も見てみるが、よくわからない…と考えてるうちにバイナリ問題が追加されたのでそっちへ。
rsbo 150
ディスアセンブリ見てると心がいやされるなーと。いやされる。なんだか知らんが、おもむろに flag のファイルを読んだあと、メモリをクリアしてから意味不明な入出力をする、という素晴らしいプログラムらしい。
入力の部分、 0x70 確保してから最大 0x80 読むとかしてて、少しだけあふれちゃっているようなので、ありがたく return address を書き換えさせていただこうと思う。しかしあふれてる量が少なすぎるので、これどーしたもんかなーと考えてた気がする。あと RWX な領域もないし、 RELRO も入ってた…と思う。
しかしまぁ案ずるより生むがやすしで、実際はじめてみると、 0x80 読む関数に一段階目でもう一回飛んで、今度は大幅に色々書けるので、 return to libc で適当に open から return した先が引数の stack ぶん捨てて ret するコード片で、そこから read に行って引数捨てて write に飛ぶ、みたいな経路を作ってやった。
都合の良いコード片は ROPgadget というやつを見つけたので、それを使って探してみた。これ便利だな。
あたり前のように書いてるが、人生二度目の buffer overflow で実際に攻撃してみた経験なので楽しかった。
ここで vash も投稿できると気付いて2問。 3:42 (3時間42分経過という意味)
ty 150
rsbo やってる最中に増えてたバイナリ問題をやる。 Aarch64 です。 Aarch64 の objdump とかは入れてあったんだけど、 gcc とか qemu の使う lib とかがセットアップされてなかったので、入れながら他の問題眺めたりとか。
この問題は、なんか入力を受けて、そのコードを実行してくれます、と。ただし、実行する前に /dev/urandom からの入力との xor を取るので、ランダムなコードを実行することになって死ぬ。
ええとどうやったんだっけ。これまたオーバーフローさせれるんで、 /dev/urandom を open した fd の入ってるスタックの中身を 0 に変えてやって、 stdin からゼロを流し込んで xor を no-op 化する、て感じだったと思う。
あとは Aarch64 のコードを頑張って書いてやる感じ。 Aarch64 てことを除けば前の問題の方が難しかったと思う。しかし data 領域が実行可能ってのは、もはや馴染みがなくて、違和感があるっていうか、最初はどうやって protect 外そうとか無駄なこと考える感じになっていた。 6:52
tarmful 128
他の問題にハマってる間に、 tarmful という雑用ぽい問題が増える。単に 1024 回、ヘンなファイル名とか経由しながら圧縮されてるファイルを展開するだけ。適当なスクリプトで解決。 9:32
hop 350
ハマってた問題だと思う。 Windows バイナリがあって、 flag を入力すると Correct! てでるようになってるんだけど、単に strcmp してくれてるわけじゃなくて、入力1文字ごとに jmp table でどこかに飛んで、ってのを繰り返して判定しているらしい。 jmp table の関係を探らないといけない。
さて Windows バイナリですよ…ということで WINE を使っていたものの、イマイチ不便で、 cygwin64 などをセットアップしてみたり、しかし Windows というやつも不慣れで不便だなぁ…となる。このあたりでパスワードをチェックする部分は特にシステムの関数とか呼ばない気がしてた。
それなら比較的お得意のやつですなーと、 Linux 上で Windows バイナリ内のそのチェックする部分をロードしてみてやる。うまく動く。こうなりゃしめたもんと、 jmp table の連鎖になってることとか、そういう構造がすぐわかる。
でー、 jmp table の連鎖からグラフ構造ができたのだけど、しかしこのグラフ構造、最短経路を取れば正解というわけではなく、ちょうど40文字で到達できるパスが正解という感じ。どうすればいいんだこれは、とはまる。
バイナリの内容わかってから解けないのはくやしいなーと思いながら寝る。
起きてから、アレコレとやってるうちに、それぽい単語が頻繁に出たりしてくるので、それを正解と仮定してアレコレ調整…みたいなことをやってると、正解に辿りつく。 15:05
TLE でもこういうのあった気がするなー。
mid
これはハマって解けなかった問題。 ACM ICPC 形式の問題ということで、長い数値列の median を求めよと。ただしメモリ制限が厳しいので頑張ってね、と。
んー pipe かな、てことで pipe にデータを置いてやるプログラムを作る。しばしバグとか取って、んーこれでいいと思うんだけどなーというものが全然通らない。
最初は bss 領域使うとなぜかメモリリミットが実は越えてたとかで、そっちも修正したり。でも最後まで通らなかった。終わったあとの話によると pipe でいいらしいし、 return まで行ってから sleep すると 1 秒余計に消費するので、答えが間違ってたってことですかねえ…しかしテストケースはそれなりにあるんだけど。
polyglot 500
mid や callme 、あるいは他の問題に無駄な時間を使ってるあいだに、 polyglot という問題が追加される。超得意分野なので、俺を誰だと思ってる的な余裕で瞬殺。いや、それなりには苦労した。 Haskell, Python, C は意外と polyglot 力が低い言語なんですよ。
この問題は最初の解答者だったらしく、主催からどんな解答だったん? みたいなメールが来る。このあとたしか寝た。 22:25
sha1lcode 300
callme と 24 にハマりすぎてたので、他のバイナリぽいの見るか…と見る。なんだこれは得意分野じゃないか。
自由な入力を、 SHA1 してコード領域に置いてから実行する、って話。適当にランダムな SHA1 結果のコードを見てみるも、当然ながら使えそうなものは無い、からもっとちゃんと狙ってやらないといけない。
高度な数学とか使わなくても、適当に探せば 2,3 bytes のコード片は見つかることは、 ShaFuck を潰した時 にもやったので、同じことをやる。
今回は、先頭に次の code chunk の終端 2,3 bytes 前に jmp するコード片と、終端でなんか 1 命令実行するコード片を探した。 36:38
ducky 250
なんか (){}; を使わずに C コードを書けという、どこかで見たような話が…技を借りるぞーということで kik さんの技を使って倒す。 37:34
24 256
いやーハマっていた。与えられた4つの数字と、四則演算子を組み合わせまくって Python3 で eval して、その結果を 24 にするクイズを 24 回解けというもの。
普通に Ruby で書いて、累乗とか // も必要かーと足して、色々足して、でも最後の問題が解けない。最後はヘンな工夫がいるのかなーとずっと考えていた。
しかしどうも結論としては Ruby で書いてたせいで、 Python のシミュレーションが不十分だったらしく、手であれこれやってるうちに、アレっこれ Python は複素数出るからこれかな…とかやってるうちに、複素数使わず手で解けた。
反省としては、嫌いでも Python 使いましょう。 39:49
callme 350
長い時間考えてた問題。ほぼ諦めて日曜の深夜に寝て、月曜の朝起きてから、解法らしきものが見つかって、なんとかまにあった。
sprintf での buffer overflow があるんだけど、 stack smashing protector がかかってるので、 return address を書き変えたところで、 ret するまでに __stack_chk_fail する。
しばらく勘違いしてたんだけど、この問題はよく見ると RWX なページはあるし、 RELRO もかかってない。つまりなんでもいいから RWX なとこに飛べばそれで勝ちで、そこが問題の本質なんだなぁとか考えるもわからない。
しょうがないので起きてからやったのは等価ぽい C のコードを書いてみたりして。生システムコールで入出力してるとかが気になったりしたけど、たぶん関係なかった。
でまぁ C のコードながめてると、 sprintf に渡してる書き込み先は stack なんだけど、よく考えると format 文字列自体も stack のだいぶ高位のアドレスなんだよな、と気付く。つまり sprintf で書いてる最中に format 文字列が変化して、当初の予定よりどんどん伸びていく…技が可能だ。つまり、 "%s%s\n\0" みたいな format だったはずなのに、自由に設定できる2個目の %s を解決してみると、 "aaaa%d%d%d.." みたいな感じで書きかわってるーみたいなことができると。
あとは、なんであるか不明機能であるところの %n を使って、 __stack_chk_fail の GOT をいじって RWX な自由な空間に飛ばしてやる。思うに __stack_chk_fail の GOT とか、もうちょい防衛してやってもいい気がするんだけど。
あと、これで死ぬ時に行く先である、 __fortify_fail は stack の argv[0] を出力しようとするから、書き変えてやれば memory exposure になる とか知って少し脱力した。今回 SSP に対する攻撃手段を色々調べていて、今回は全く役に立たなかったというかむしろ混乱したけど、しかし勉強になった。
あとは時間に間に合うかーという感じで、あれこれやって、あわてて shell code 書いて、なんとか通った。 shell code くらいはいい感じのを自分で作っておくと良いんだろうな。 46:50
感想
たいへん楽しかった。普段は守る側…に自分が直接いるわけではなく、しかし守る側の人を比較的近い距離で眺める、みたいなことが多いだけに、知ってる知識を逆側に使えるのは楽しい。曖昧な理解になってるところがハッキリするのも良い。
MD5 とか RSA とか、暗号系も興味があるんだけど、全く手が出なかったのは残念だった。まぁ一人だと時間的にもキツいが、それでも勉強しておきたい感はある。ネットワーク系も手が出なかったんだけど、しかしそっちはそもそも興味があまりなくて…
あと一人は楽しいものの、やはりキツい。問題が増える速度の方が解く速度より圧倒的にはやい。チームでやってる人は、何人くらいでやってるのかなぁ。こういうルールだと、組んでやるのもやってみたくはある。
ICFPC 2014
総じておだやかに楽しかった。
https://github.com/shinh/icfpc2014
1日目
初日、21時から問題を読む。んー普通だなーと思いつつとりあえず寝る。
起きて Lambda-man の AI を書きはじめる。普通だと思ったけど、 Lisp マシンってこういうふうな感じなんだなぁ、と、知らなかったので普通に勉強になった。とりあえず思った通りに動くものを作ろうということで、アセンブラを Ruby 上の DSL として書く。オペランドの数と型のチェックと、ラベルの解決をするくらいのやつ。
なんとなく何ができるかわかったところで、これはアセンブラ直書きは大変だし変更に弱い…ってことで、そのアセンブラの上に高級言語を作る必要を感じる。素直に Lisp でもいいけど、あまり Lisp 書き慣れてないので、 Ruby 上の DSL をもう1レイヤ重ねることにした。あとは beflisp の知見を生かして、 LLVM bitcode からの変換ってのも考えたんだけど、そういうのがしたければ複数人がいないとな、て感じ。
きちんと理解する時間がもったいなかったので、 Lisp マシンぽいところなのか、難しそうな命令は無視して、 store 命令を使いまくって、普通にローカル変数をいじりまくるような作りにした。こういうのは書き慣れてるので、割とするっと書ける。引数用に用意された frame だけではローカル変数を置けないなーと思ったので、全ての関数は引数と local 変数を置けるもっと広い frame を作ってから、実際の実装に関数 call する、ってことにした。関数呼び出しのオーバーヘッドが大きくなるけど、関数をあまり呼ばない作りにすれば問題ない。コードサイズの制限はゆるいし、命令キャッシュとか無いわけで、 Ruby のレイヤで関数作ってやれば、 template みたいな感じでコードサイズが大きくなる方向でコードの再利用はできるし。
で、できた DSL で、とりあえず時間とともに移動方向を順番に変えるような AI を作ってみた。これは書きにくいなーということで、 AI を書きながら、色々書きやすくしたりした。まぁそれほど良いものでは無いけど、これで最終日まで戦えるかな、って程度にはなった。
各地点への最短距離を調べるコードを DSL 上で書く。配布されてた3つのマップはクリアできるようになった。よく死ぬのが微妙なんで、敵をある程度避けるようにした。直線上で向きあう動きと、2マスだったかそのくらい接近するのを避けるようにする。
最短距離を調べるコードは getXY とか setXY 的な処理をしまくっていたので、デカいマップで不安だった。これは無理かなぁと思いつつデカいマップで試してみると、当然ダメ。
しょうがないので、最短距離調べるアプローチより弱くなるだろうな…と思いつつ、スコア源に引かれる重力モデルを実装してみる。これでもデカいマップはきつかったけど、速度的にはかなり良くなってたので、見る範囲をしぼったりして対処。しかしやはり弱くなる。
ていうかヘンなところにひっかかったりする。なるべく1ターン前のところに戻るのはイヤがるようにしたりすると、まぁまぁ動くようになる。しかしやはり弱くなったように感じる。
あと1時間くらいでライトニング終わるなーというところで、あ、自分からの近距離だけの map に対してだけ最短距離調べるようにして、それとのハイブリッドにしたらいいんじゃね、と気付いて実装したらかなり良くなった。ただこの時のコードには、左端と上端にいる時に動作が不審になるバグがあったと最終日に気付いた。
この Lambda-man の DSL は Ruby のコードと DSL ぽい部分が混じりまくって (Ruby のループの中で DSL の whileP とかいうループが回ったりしている) 見た目がすごいことになってるのだけど、割と私一人が書くぶんには大丈夫程度のものが、割とスルっと書けたので満足することにした。
うーん ghost の AI も書くのかーとなるとシミュレータも書かないとだなー盛り沢山だなぁ、シミュレータの言語は何にしようかなぁ、と寝る。
2日目
2日目にシミュレータを書く、ってのは割と恒例ではある。言語は GC が欲しいな、ってことで Go にした。 D 言語と悩んだけど、既に入ってた Go に軍配が上がった。 Go はまぁちょくちょく触れるけど、書きやすいよね。 Google 社員的にはノリにすごい慣れてるんだよな。 C++ でもこんな感じのコード書いてるよなあ、っていう。あ、 Chrome とかはだいぶ違うけど。
で、 ghost や lambda-man の処理系は、拍子抜けするくらい簡単に作れたのだけど、そこからがこれも恒例の、ゲームロジックの挙動が微妙に違う祭り。ひとつひとつ仕様の読解/理解ミスを正していく。これはいつも以上にドキュメントが量も多くて細かいところに不明なところが多くて大変だった。途中である程度あってりゃいい気もしてやめようかと思ったけど、まぁ信用できない部品を放置するのは ICFPC ではやばい、っていう経験則からがんばった。
最後はリファレンスインプリのバグまで再現して、あとまあ同時にイベントが起きた時のコーナーケースにミスはあるだろうけど、ってあたりまでやって、終了。しかし、途中で、リファレンスインプリのバグはご丁寧に修正されてしまったので、リファレンスインプリと不整合な結果を返すのは我慢して戦うことになってしまった…
次は ghost を書いてみる。今度は Lambda-man 用のアセンブラをちょっといじって ghost アセンブラを Ruby 上に作る。んーなんか 256 instruction くらいならこれでいいんじゃね、ってことで、それで良いことに。
どういうのがいいのかなぁと考える。素直に襲いかかるやつと、一箇所をひたすら防衛するやつ、とかを考えた。後者はいかにも弱そうなので、襲いかかるやつを作ってみた。適当に作ると、これが結構強い。 Lambda-man が虐殺されている様を見るに、あーこれは効率良く pill を集めるとかよりは、避けゲーかなーと思う。
ただ、適当に作った素直に襲いかかるやつは、最初のサンプルマップの初期位置にひっかかる。あたりまえである。というわけでランダム要素とかをちょっと入れてみる。だいぶ良くなるが、まだみんな同じ行動しがちで意味がない。他の AI の案が思いつかなかったので、もうちょっと散らすことにした。具体的には本家パックマンを参考に Lambda-man が向かってる先を目指す、っていうヒネりが無いやつ。
このへんで、はて一通り提出できる体裁はととのったが、はてどこに力を入れるべきか…と考えつつ寝る。
3日目
なにすっぺかなーと考えつつ、細かいバグとかをなおす。感覚としては、 Lambda-man にもっと高度なプログラム的に賢いことをさせるべきだ、ってのがあった。例えば ghost をシミュレーションして短期間の未来予測をするとか、グラフ構造を作って危険な道とか安全な道とか考えて動かすとか、そういうの。
ただこれは与えられてる clock cycle であるとか、自分のアルゴリズム知識的なことと、あとそもそも ghost は適当に襲いかかるだけでも Lambda-man には結構脅威、ってことから、なんかやってみるかなー別にいいか…ってのを繰り返してるうちに終了した。まぁやんなくて良かったんじゃないかなーと思ってるが、謎。
というわけで、なんか割と作りたい雰囲気のものができてしまっているので、細かい完成度上げに使った地味な一日になった。あと途中で昼寝した。 ICPFC 中に5回寝たのはたぶん新記録。
地味なんだけど、結構 AI の細かい作りこみみたいなの、わりと好きなようで、1日だけだと結構たのしい。
まず、 ghost 強すぎ…ってことで Lambda-man の回避装置をちょっとマシにしてみる。いまいち。ていうか Lambda-man 死ぬ時はだいたい挟まれてるのよね。未来予測とかグラフ作りをそれなりにやらないと、たぶん不幸な未来を避けるのは難しい。ていうかこれ普通に考えると運ゲーにならねー、でも賢い人はこの状況で Lambda-man 生かせるのかな…とか思う。
さて死ぬのは諦めた。しかし怯えてる ghost は得点が高いし、 fruit も得点が高いので、こいつらを優先的に喰うことにしよう、てなことをやる。このへんから一人イタチごっこがはじまる。
あ、私の ghost 、 Lambda-man に襲いかかりすぎるあまり、殺すのはいいんだけど得点渡しすぎてる…と思ったので、怯えモードの時は行くところの優先順位を逆転させてやる。逃げ AI 。
うーん ghost 食いにくくなったのかな、と power pill の隣に待機して、 ghost が近寄ってきたら power pill を食って ghost を食べる、ってのを実装する。いくらなんでも無限に待つとザコ AI 相手に power pill の隣でウロウロしてるだけで終わってしまうので、timeout なんかを実装してやりつつ。
あ、私の ghost 、待ちラムダーマンにやられて、標準 AI より得点渡してる…と気付いたので、 Lambda-man が power pill に近い時には怯えモードにしてやる。逃げる逃げる。
なんとなく Lambda-man の生存率が高くなってる。あたりまえだが怯えモードの時に画面の端までいってしまうので、 Lambda-man の power pill 隣待機作戦は、 ghost 喰うのには成功しないものの、その後しばらく安全に移動できるようになっちゃってるぽい。なるほどということで Lambda-man から遠い時は襲いかかるモードにする。
こういう感じの細かい調整をまぁいろいろ。 Lambda-man が一手で ghost を食える時は喰うとか、なるべくがんばって fruit は喰うであるとか、 ghost も最初の頃に入れたランダムな挙動が Lambda-man に近付いてる時とか逃げてる時に出す必要は無いなーとやめてみたりとか、そういうの。
感想
面白かった、と思う。評判があまり芳しくないぽいのはまぁわかる。問題に面白みは足りないと思う。まぁ L:tG とかと比べるのは酷。ただ、分量は多いので、こういうのは一人でやってると無理ゲー感はあるものの、楽しい。 ICFPC って、結構終わってから、誰かと組みたかったな…と思う年はあるのだけど、今回はそうではなかった。ま、そんなに成績は良くないだろうけど、あーなんか色々やったなー的な充実感があった。
あと今回結構、色んなところで(私が一人でやるという前提に立てば)正しい選択を結構できたのではないかな…という感はある。まぁ、このへんは毎年、あーがんばったなーと思いつつ、他の人の思いもよらない作戦に、あーこのくらいは思いつけるべきだった…って思ってるんだけど。まぁ、今回はそういう裏技が思いつきにくい、割と素直な問題だったと思うんだけど…
2D Lisp
beflisp.bef が 1次元 Lisp しかサポートしてないのはけしからん、と言われてその通りだなぁと思ったので、 lisp2d.c てのを書いて beflisp2d.bef を生成してみました。 bc2bef.cc は全くいじる必要がありませんでした。 Befunge コードが C 書くだけで作れるってのはラクチンですね…
で、こんなコードが動きます。2次元であることに面白い意味を持たせるアイデアが無かったので、単に 2D レイアウトできるようになっただけです。 Befunge 同様コードが交差できるのは少しオシャレ。気をつけないと括弧のつもりで使った v が文字列の一部になったりするので、書くのはかなり大変
(defun fizzbuzz ^ (fizzbuzz 1) @
^ zzuB ( 0 (5 n dom)
i ^
f v ^ q
( eq ^
^ fi) ^ v m
e o
q l f d
i i
n (mod n 15) 0) Fizzbuzz v n
1 q 3
0 e v
1 (if v
v 0
t v
n n
i i F
l r i
p ^ z
(if v ^ z
1
n
v
n v
v
+ v
v zzubzzif )
beflisp.bef と LLVM Befunge backend
https://github.com/shinh/beflisp
Lisp インタプリタを作りました。今度は Befunge で。
https://github.com/shinh/beflisp/blob/master/beflisp.bef
コードを見ればわかりますが、手書きは諦めました。 前回の sed と違って Befunge は数値演算は素直に提供してくれてるので、アドレス計算なんかをするプリミティブが提供しやすいです。ただ、 Befunge-93 は文字列とか関数コールという概念が無いので、手動でフロー管理するのは地獄でしょうね…
ということで、 C で lisp を書いて、それを clang で LLVM bitcode に変換してから、トランスレータで Befunge に変換、という構成になっています。
実装
トランスレータは任意の C コードを Befunge に変換できるようなレベルには全然達していません。例えば型は全部 32bit 決め打ちです。内部実装知ってないとどういう C コードなら通るかとかわかりにくいでしょうし、内部実装知ってる私にもあまりわかってません。ていうかなんで動いてるんだろうっていう感じ。全体的に投げ槍な実装なんで。
LLVM bitcode からトランスレートされた Befunge コードってのは、あたりまえですが割とデバッグが大変です。しょうがないので小さな C プログラムを一つずつ動くようにしていく感じでやりました。あとデバッグしやすいように元に bitcode を実行しない領域に置いてあります。
大変だったのはまずブランチとかですかね。立体的にコード配置するのはデタラメに大変に決まってるので直線的に実行したいので。スタックトップが真ならスタックの2番目を採用、偽なら3番目を採用、ってことができるプリミティブを作ってそれをあちこちで使う感じにしました。ブランチといえば当然 PHI もダルいったらありゃしない。
LLVM のバックエンドの書く作法を調べるのが面倒だし、 LLVM のバックエンド用の共通基盤が Befunge みたいな素頓狂な実行モデルにうまいこと適合するとは思いがたかったので、 bitcode 読んでからは全自力です。レジスタアロケーションだけやってもらえたりするとラクに生成されたコードを小さくできるんですが…
機能としては前回の sed と同じはずです。前回のテストコードは全部パスしてますし、 FizzBuzz on Lisp on Lisp on Befunge も動いています。すごく遅くて、半分で 1 時間とかかかってますけど。
TODO
レジスタアロケーションをやるってのと、ブランチの高速化、ってのがあります。このふたつやればもう少し実用的な速度になるんでないかなぁと。
というのは、前者は、現状 SSA の結果は全部スタックに残していっていて、スタックがまあまあ遠いところにあるんでアクセスにかかる命令数が多いということがあり。
後者はもっとひどい話で、現状どこかで jmp や call があると、必ずプログラムの一番先頭まで戻ってから次に実行する場所を線型探索してます。そうでなくてちゃんと差分だけ動くようにすれば、近くへの jmp とかが劇的に速くなるかと思います。
あとは free が実装されてないってのがひどいんですけど、当然のことながら実装するとすごく遅くなっちゃうと思われるので、だるいかなあと。
まとめ
Befunge はまともな言語
