Very symmetric JavaScript code
だいぶ前に左右反転させてもだいたい同じに見えるコードを書いたのですが、もうちょっと進化させて、上下反転と、180度回転してもだいたい同じように見えるコードを書いてみました。
デモサイト: http://shinh.skr.jp/obf/very_symmetric_js.html
コード: https://github.com/shinh/hack/blob/master/very_symmetric_js/very_symmetric.js
普通のJS記号ゴルフと比べるとクォートが無いのが多少めんどくさく、あとは左右は一行コメントがあるから簡単なんですが、上下反転と180度回転のコードをコメントですっとばすのがパズルという感じでした。何も考えずに実行するコードの最後に /* と入れただけだと、180度回転した部分に */ が現れてしまってコメントが終わってしまうという。
drdr
オレオレワークフローエンジン作りたくなる病というのがあって、例えば make 系なんかだと Wikipediaに色々書いてあったりします。ワークフローエンジンと総称するのが正しいのか知りませんが、依存グラフを順ぐりに並列に実行していくようなもの、色々あるわけですけど、目的も粒度もバラバラですが以下のようなものは割と似たようなものに見えてます。
- thread pool
- Tensorflow
- make
- Digdag
閑話休題。なんか微妙に10秒程度待ち時間があるような処理があって(クラウドストレージに対する例えば ls とか)、その ls の結果全てに対してまた10秒程度時間がかかるコマンドをまとめて実行、終わったら結果を集計、みたいなことをしたりすることが最近多いです。1週間から1ヶ月ほど10回とか100回使うんだけど、でもそのうち捨てる系のコード。私の場合、よくやる解決と問題点は
- shell script で並列化したいところはバックグラウンド実行+waitで散らして、最後の部分は ruby かなんかで書く: shell script と ruby の2つを管理するのがうっとうしい。多少ややこしいパイプラインを作るの大変
- ruby かなんかでスレッドプール作ってやる: 分散部分のコードがめんどくさい。多少ややこしいパイプラインを作るのがかなりめんどくさい
- make を使う: 動作は理想的なことが多いけど、コードがめんどくさくて、あと宣言的な記述になって、シーケンシャルな記述じゃなくなるので、読みにくく編集しにくい
欲しいことを考えると
- CPU並列は無くても良い
- パフォーマンスは最適でなくて良い
- コマンドが手軽に実行できると良い
- コマンドが失敗したら即座に止まると良い
- shell はミスりやすいから嫌だ
- 処理の後半部分のやりなおしとかのためにチェックポイントを仕込めると良い
で、まあなんか作りはじめてみましたというのがこれ。
https://github.com/shinh/drdr/
あまり良い例が思いつかなかったのですが、自分のスライドのディレクトリにあるスライド全部に対して、それぞれページ数を集計するサンプルがこんな感じ。
URL = "http://shinh.skr.jp/slide/" drdr { # スライド一覧のところを読んできて、 list.ckpt に保存しておく # これ以降のスクリプトに書き損じがあっても、再度ネットワークアクセスは発生しない cmd("curl #{URL}", ckpt: 'list.ckpt') | task{|l| # ここから list.ckpt に依存した処理で、 Apache の directory index を適当にパース l.scan(/href="([a-z].*?)\/"/).map do |m| name = m[0] # スライドのページ数を適当に取ってくる。このコマンド実行は並列に走る cmd("curl #{URL}#{name}/ 2> /dev/null") | task{|l| last_page = 0 l.scan(/(\d+)\.html/) do last_page = [$1.to_i, last_page].max end [name, last_page] } end } | task{|a| # 全部終わったら CSV として出力 a.each do |name, max_page| puts [name, max_page] * "," end } }
などなど。妄想したほど使い勝手良くなってない気がするのですが、しかし自分が使える程度のものにはなってるような気がします。しかし一般的にこういうのはどういう感じで処理してるもんなんでしょうか。なんかいい方法あったら教えてください。。
あと Guild が実装されると計算も並列に走るようになっていい気がしますね
tanlog
最近、 tanlog というのを作って使っていて、割と便利なので紹介してみます。
https://github.com/shinh/test/blob/master/tanlog.rb
元々は同僚と、なんか端末に出たもの前もって lv とか tee に入れておくのって、忘れることあるし、 lv とか tee に流すと isatty が false になって色出ないのうざいよねえ…みたいな話をしてたように思います。 grep については fake_isatty とか作ったりしたんですが、この時 soda さんに仮想端末作ってやる方法があると教えてもらったのを思い出して、 script とかで記録しておいたら…とか話していました。
結果、その同僚は zenlog というのを作って便利になった、とか言ってたのですが、なんか Perl と bash 混じってるとか、コマンドの切れ目をプロンプトで教えるとか微妙…ということで自作したものです。 zenlog に対して tanlog なのはコマンド起動ごとになんかするからです。まあこういうのは人の作ったものを使うというよりはみんな勝手に作ればいい…
tanlog は screen/zsh と一緒に使うことが想定されていて、 preexec で tanlog start して precmd で tanlog end します。 tanlog start は screen のログファイルを指定して /tmp/tanlog/RAW の下に端末出力をダンプしはじめます。 tanlog end はその端末出力を綺麗にして /tmp/tanlog の下にコピーします。
このディレクトリの構造は適当に便利なようになっていて、
- /tmp/tanlog/2017-02-12: ログの実体がある場所
- /tmp/tanlog/TODAY: 今日のディレクトリへのシンボリックリンク
- /tmp/tanlog/TODAY/P: さっき実行したコマンドのログへのシンボリックリンク
- /tmp/tanlog/TODAY/PP: その前実行したコマンドのログへのシンボリックリンク
- /tmp/tanlog/make: makeコマンドのログへのシンボリックリンクがこの下にころがっている
- /tmp/tanlog/make/P: さっき実行した make のログへのシンボリックリンク
などと適当に便利そうなものが入っています。えーと llvm ビルドした時の cmake コマンドはどんな感じだったかな…とか思ったなら
wgrep llvm /tmp/tanlog/cmake/P*
なんてやってます。 wgrep てのは grep を w3m でラップした何かです。
あとは tanlog paths てすると最近実行したコマンドに含まれるパスとかURLぽいものがだーと出るので、それを w3m に喰わせる wl ていうのも使ったりしてます。コマンドが URL 出してくれたけど、それマウスとか screen とかでコピペするのめんどい、て時に使ってます。
https://github.com/shinh/test/blob/master/wl
そのまま他の人が使えるような形にはなってないと思いますが、 screen のログ機能なり script なり使って、とりあえずコマンドの実行結果を全部残しておく、てのはなかなか良いのではないかと思っています。 lv か tee 通すべきかな?とか一瞬逡巡するのが無くなります。実現がハッキーになりすぎるのが残念なところで、こういうことを色々便利にやってくれる screen つき shell みたいなの作りたいなぁとかいうことを割とずっと思っています。
ELVM Compiler Infrastructure について
はじめに
言語実装 Advent Calendar 2016 用です。
ELVMは、コンパイラをフロントエンドと中間言語とバックエンドにわけて、多言語多CPUに対応しよう……というようなLLVMの考え方を、パロディと言っていいレベルにまで単純化したものです。結果として実用性は全くないが、C言語から他言語へのトランスレータを極めて簡単に書け、 Brainfuck などのような難しい言語のコードもC言語を書くだけで生成できる、というようなことを主目的としています。
本当は ELVM のバックエンドを一つ足して、 Brainfuck とかのような難しいターゲットでなければ、こういう感じで手軽に足せますよーということを書こうかと思っていました。しかし、ありがたいことにそういう趣旨だったり、あるいはもっと難しいターゲットについても、既にあれこれと書いていただいたのでした。例えば
- Perl: http://qiita.com/mackee_w/items/5397d6b9215f41c41db1
- Tex: http://hak7a3.hatenablog.com/entry/2016/11/13/153418
- Tex: http://hak7a3.hatenablog.com/entry/2016/12/03/124632
- Vim: http://rhysd.hatenablog.com/entry/2016/12/02/030511
- C++ (constexpr): http://kw-udon.hatenablog.com/entry/2016/12/03/201722
- Unlambda: http://irori.hatenablog.com/entry/elvm-unlambda-part1
など。上のリストは、おおざっぱに、上の方に簡単な雰囲気をつかむのに向いてそうな記事、下の方に謎テクニックを楽しむのに向いてそうな記事を並べてみました。いずれにせよ、こういう記事は中身をよく把握してる私自身より、試行錯誤していただいた他の人達が書いた方がわかりやすいでしょう……ということでなんか違うことを書いてみます。
具体的にはどういうふうに作業を進めたりした…てことを雑に書いていこうかと。技術的な概要は一つ前のこのポストとそこからリンクされてるスライドに書いたので、そっちを参照してください。
sedlisp, beflisp, makelisp, bflisp
色々あって、Esolangですごく簡単なLisp処理系を書く、というのがマイブームになったことがありました。 GNU sed と GNU make は完全手書きでした。sedlisp を書いた時から、 @rui314 さんは「手書きじゃなくて中間層を介して変換した方が良いのではないか」と言っていたのですが、 sed や make だと、計算モデルが違いすぎるので直接書く方がラクかなということと、結果できたものが遅くなりすぎそうだったので、直接書きました。
ですが、 Befunge の時はなにか中間に入れないとキツいと感じたので、 LLVM bitcode から雑に変換する、という方法でやりました。といっても、 LLVM bitcode は任意のものを許すわけではなく、変換器がサポートしてる命令しか吐かないように注意深く書かれた lisp.c を LLVM bitcode にして、そこから Befunge に変換する、というようなやり方でした。
で、 Brainfuck もやってみるかなぁと思った時に、これは自明に Befunge 以上に大変なわけで、まあなんかから変換するしか無いわけです。でも LLVM bitcode て以外に命令セットでかいということは Befunge の時に感じてたので、あまりつきあいたくなかった。じゃあなんかオレオレ中間コードを作るのが良いかな、と考えました。
bfs
で、 bfs という中間形式をデッチ上げました。これは今の ELVM の EIR と同じなんですけど、最初は Brainfuck だけが想定ターゲットだったので、 Brainfuck Assembly 的な理由でこういう名前になっていました。ややこしいんで今後 EIR で統一します。中間形式をでっち上げるのは、まあ適当に決めるだけなので簡単です。
で形式が決まるとCコンパイラをいじることになります。 main しか無いような簡単なコードを書いてみて、x86-64のコードを出力してる部分を順に EIR を吐くように変換して、うまくいったらreturn 42;とか1+2;とか、命令を足しては出てきたx86-64のコードを等価な EIR のコードに変換していく感じでした。
すごく短いプログラムをコンパイルできるようになったら、 EIR のシミュレータを書いたかと思います。命令数が少ないので、 Brainfuck のインタプリタを書く程度プラスアルファくらいの手間でできます。途中、ああ命令だけじゃなくてデータも書けないといけないな、ということで.dataセクションを足したりもしました。
この段階で重要だったのは、C言語で書いたコードをx86-64に変換して実行した結果と、EIRにコンパイルしてシミュレータで動かした結果が同じ、ということをきちんとテストすることでした。なにかまだサポートできてないCの機能を見つけるたびに、C言語でテストを書いて、makeと叩けばx86-64で実行した結果とシミュレータの結果が同じであることをチェックできるようにしてたと思います。
bflisp
C言語→EIRが一通りうまくいってるぽくなってくると、次は EIR を Brainfuck に変換する部分です。これはまあ……大変です。定数ロードとかをかけ算でやるとかは大変だし遅いBF処理系では全く通用しないので、8bitセルのBFで複数セルを使って1byte (当時は1byte==16bit) の情報を扱います。つまり単なる加減命令とかでも、繰上がり下がりの計算がはさまることになって……めんどくさいです。がまあ加減くらいは序の口で。
一番キツかったのは比較命令だったかと思います。上位セルが大きかったら下位は無視してーとか、0と比較する時だけおかしいとか、下位が0の時だけおかしいとか、そういう謎の現象が起きまくりました。load/storeも結構大変だったのですが、比較の後だったから慣れていたというのと、あまりコーナーケースが多くなかったこともあって、どっちかというとどういうレイアウトにするか、っていうデザインが大変だったような気がします。
こういうわけわからない有象無象をデバッグするために、EIRのシミュレータと、EIRからBrainfuckを出力した時のコードに、トレース出力をつけました。具体的には1命令ごとにレジスタの状態を出力する感じです。これでできた巨大なトレース出力を diff していると、喰い違いが出てくる部分がでてきて、そこを見ればバグの原因がわかるので、小さいテストを書いて修正する……というのを繰り返しました。これはオモチャ CPU 作った時にも使ったアプローチで、CPUの時はエミュレータに実行トレースをつけたものと、iverilogでトレースを出してたものを比較してました。でまぁ、なんかうまくいきました。
あとは、C言語→EIRの時に使ったテストケースを、順にEIR→Brainfuckの変換でも正しく動くかをテストしていった感じでした。そんなこんなで lisp.c が Brainfuck の上で動きました。
8cc.bf
さて、lispが動くならCコンパイラ自体もBrainfuckで動かしたいな、ということで色々試しはじめます。まずわかったのは16bitのメモリ空間では、命令もデータも足りない、ということでした。命令の方は、「実際のCPUじゃないんだから、1命令ごとにPCひとつ使う必要ないよね」ってことで、 basic block ごとに PC が変わることになりました。 VLIW と考えても良いかもしれないです。いや良くないでしょうけど。
データの方はちょこざいなこともできなくて足りないので、素直に24bitに拡張しました。命令も拡張しても良かったんでしょうけど、前述の basic block ごとに命令をまとめる作戦は、単純に実行速度の向上にも貢献するのでいずれにせよやって良かったと思います。
あとは少しバグをつぶしたらEIR→Brainfuck側はだいたいできました。足りない libc 関数の用意と、 8cc 側の EIR としてサポートできない記述の修正です。 libc は ARC やオモチャ CPU のために書いたコードや、 Bionic から必要なものをひっこ抜いてきたり自分で書いたりして準備しました。 8cc 側の困った記述というのは、 signed が無いので value >= 0 とかが常に true とか、あとはビットシフトと浮動小数の撤去でした。
そんな感じで 8cc が Brainfuck 上で動きました。5時間ほどかかってセルフホストができて、おおーと思いました。
ELVM
このへんでだいたい満足してたのですが、2点ほど思っていることがありました。
- id:irori さんが Unlambda への変換を実現させて、 8cc.unl を作ってくれたのですが、こういう感じでもっとターゲットを増やすと面白いのではないか
- EIR→Brainfuckの変換はRubyで行なっていたので、完全なセルフホストではなかった。これでは人類からBrainfuckインタプリタ以外が失われた時に対応できない
でまあ、一番大変な 8cc.bf というのはすでに動いてたので、だるいなーと思ってたのです。がまあある日、2つとも一気に解決しよう、で ELVM とかいう景気のいい名前をつけよう、とか思い立ちました。名前とか決まるとやる気出ますね。
でまあ、まずはEIR→ターゲットの部分をCにしつつ、ちゃんとフレームワークぽい感じにしました。実装量はあったけどまあやるだけ。
他の部分は適当ですが、ターゲットを増やすのは割とやりやすくなってるのではないかと思います。なんか適当に周りの言語のコピペしてると、だいたいおかしいところが少しずつ見えてきて、インクリメンタルに作業できるんじゃないかと。特に Makefile がよく書けてると自負してまして、バックエンド書く人は少し Makefile に追記したら make hoge だけで hoge バックエンドに対するテストがたくさん走る感じになってます。
バックエンドを増殖させる
基本部分ができるとバックエンドを増殖させていきました。色々足していると、基盤部分にあった方がいい共通部品なんかが見えていったりしました。
Esoteric 方面の言語だと、 Befunge 、 sed 、 Piet 、 C-INTERCAL あたりはなかなか大変なバックエンドでした。特に経験が無かった C-INTERCAL と、あと Piet はなんか色々大変でした。
Piet はこう、 Befunge みたいな感じでできるかな…と思ってたのですが、コード変換と2次元レイアウトを同時にやるのが大変で、一旦 PietInst とかいう構造体の列にして、それからレイアウトを決めて色を配置する、みたいなことをやりました。つまりもう1つ中間言語を介してるわけです。
INTERCAL はこう、方言多すぎ、仕様多すぎですね。色々やってたのですが、結局 C-INTERCAL がまともに動きそう、ということでこれになりました。 add とか sub とか無いんで、このへんはパズルチックにプリミティブを作ってく感じでした。
反応など
当初は「ヘンなことやってるなあ」くらいに思われる程度だと思っていたのですが、予想以上に反応をいただいて、PRでバックエンドを足していただいたりして嬉しい誤算でした。現状28バックエンド中13バックエンドはPRでいただいた、というのはなかなかなもんだなと。最初の方に Unlambda, Vim, TeX バックエンドを書いてくだださった iroriさん rhysd さん hak7a3 さんには特に感謝する感じです。紹介記事書いていただいたのも後に続く人を増やしていただけたんでないかなと。
その後の展開としては、 C++ constexpr バックエンドのバズりっぷりがなかなか愉快でした。 @llvmweekly や Bjarne Stroustrup がコメントしたりと。あと、チューリングマシンバックエンドを書いていただいた、ND-CSE-30151というアカウントは、どうもこれノッテルダム大学の講義用のアカウントらしく、この講義のテーマにチューリング完全などがあるため、少なくとも授業で紹介くらいはしてくれるのでないかと思います。ジョークプロジェクトが大学の授業で紹介されるというのは、なかなか胸熱です。
あと、 id:irori さんの EsoLang vi のような方向性も面白いですね。改造 8cc が処理できる C 言語で書かれたソフトであれば、 Unlambda やら Brainfuck に変換できちゃうわけです。
まとめ
スライドにも書いたのですが、理論上できるに決まってることでも、実際動かしてみるのは大変だったりして、でも動いたりすると嬉しいもんだなと。どうも私は発見とかがしたいんじゃなくて、そんなのやってどうすんのってこととか、理屈はわかるけどそれ本当に現実的な話としてできるの、てことをやるのが好みなのかなぁと、最近思います。セクシーボイスアンドロボというマンガの主人公が、「私がしたいのは世界にちょっとしたドリームを与えるような、そういうこと」とか言ってたんですが、なんかたぶん、そういうことが目指すところな気がします
言語処理系、文法とかそういう表の部分に注目しがちですけど、バックエンドやそれ以降も面白いですよ、と。たとえば世の中の言語作者はもっとデバッガとかに興味持ってあげて欲しいと思ったりします。
あとはこう、なんか世の中にあるもののパロディーというか似たようなものを適当にでっちあげるというのは、なんかとりあえずやる、ってテーマとしては良いなと思ったりしました。なんか趣味コード書くかっていって、まぁいきなりデカいオープンソースに飛び込むとかすごい有用なもの作る、っていって手が動く人はいいんですけど…
PRは随時募集という感じなので、冬休みの暇潰しなどに、ぜひバックエンドを足してみてください
ELVM Compiler Infrastructure
最近作ってたオモチャがだいたいまとまってきました。
第12回 kernel/vm 勉強会で発表した時のスライド:
http://shinh.skr.jp/slide/elvm/000.html
これは何かというと、前作った bflisp を改良したり整理したりしたもので、 C 言語をシンプルな中間言語 (EIR) に変換する改造 8cc と、その中間言語を Brainfuck をはじめとした他言語に変換するバックエンドから成り立っています。 bflisp との差分は、 Brainfuck 以外のバックエンドを追加しやすくしたり、バックエンドを C で書いて、完全に Brainfuck だけで 8cc.bf を再現することができるようにしたり、という感じです。
特に興味深いであろうバックエンドとしては、 Brainfuck, Unlambda (id:irori さん作), Piet, C-INTERCAL, Befunge, Whitespace などがあります。例えば Lisp を Piet で動かしたりもできるようになりました。 lisp.png を gimp で開いてスクリーンショットを撮ったこの画像なんかは結構お気にいりです。
JavaScript に変換することもできるので、デモサイトは ELVM を使って作った JS で作られています。
http://shinh.skr.jp/elvm/8cc.js.html
スライドにも書きましたが、「チューリング完全な言語互いに等価だからうんぬん…」というような、理論ではそうなんだけど…というようなことが実際確認されるのを見るのはなかなか楽しかったです。コンパイラいじり、 esolangs での計算プリミティブ作成パズル、最小限の libc 作り、など好きなトピックがたくさんあるという意味でも楽しくて良かったです。
Brainfuck interpreter in Ruby's Regexp
Ruby の正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。
https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rb
つまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを
BF_REG =~ bf + BF_SUFFIX
で実行することができます。出力は $~['o0'], $~['o1'], ... に入っているので、
output = '' 256.times do |i| o = $~["o#{i}"] break if !o output += o end
的なコードで取り出すことができます。入力は ! の後に続いてる文字列を入力とする形式。Ruby の正規表現は Turing 完全でないので、無限ループはできないようになっています。
仕様の一覧を並べると
- 8bit Brainfuck
- 入力の終端は -1
- メモリは255番地まで
- 出力文字数は256まで
- 入力文字数は256まで
- Brainfuck命令以外の文字があると正規表現がマッチに失敗する
- 無限ループがあると正規表現がマッチに失敗する(正確には1つのループが256回連続回ったら止まるという仕様なので、本当は止まるコードもマッチ失敗することがありえます)
など。256まで、という制限は実装をラクにするためなので、本質的な制限ではないです、が無限にはできないです(入力文字数は無限にできるかも?)。この程度の制限があっても十分に実用的(?)で、例えば cal.bf も動いています。
$ echo 2016 10 | time ruby bf.rb cal.bf 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ruby bf.rb cal.bf 1147.54s user 0.26s system 99% cpu 19:07.91 total
ただすごく遅くて、 cal.bf の実行に19分とかかかってました。1命令10msとかその程度だと思います。 + とか - が実に遅い。
こんなことできるとはつい最近まで思ってなかったのですが、 HITCON CTF で正規表現力の研鑽を積んだ結果、なんかできるような気がしてきて、やってみたらできました。
今思うに、一番重要なことは後方参照を更新できる、ということだったのかなと思います。 \g で呼び出された中にある後方参照は、呼び出されるたびに値が変わっていくという。
DEFCON CTF 本戦
binjaの現地枠がギリギリ空いてそうだったので、入れてもらいました。思ったことは、みんなすごいなあ、ということと、これしんどいなあということ、ルールはともかくみんなでわちゃわちゃやるの楽しいなということ、あとまあなんと言っても俺ふがいないな、ってことでした。
今回はCTFの前日に優勝賞金2億円のDARPA主催のCyber Grand Challenge(以下CGC)というのが行なわれ、それで優勝したAIを含めて15チームで同じフォーマットで競う、という趣旨でした。CGCはELFベースにABIを簡略化してあり、いつものようにシェルコードを実行するまではやる必要がなく、
- type 1: EIPを指定されたところに飛ばす
- type 2: 特定のアドレスにある、フラグページから4byte取り出す
のいずれかを達成すればOK、というルールでした。
準備
準備の段階では、 bjmit という名前でバイナリに mitigation (日本語でなんと言うのだろう) を入れるツールと、それの評価をするものを作っていました。バイナリジャンルの mitigation というのは ASLR や stack canary なんかがよく使われるものです。 stack canary みたいなのを入れるのはまぁまぁ大変なので、簡単に実装できるものをたくさん準備する、という方針で
- retをフックして戻り先が元々.textだったか、callの直後に戻っているかをチェックする
- jmp/callをフックして戻り先が元々.textだったかをチェックする
- sub esp, XXをフックして未初期化スタックを使わないようにする
- writeシステムコール相当をフックして、フラグページを直接writeできないようにする
- mmap(PROT_EXEC)相当を禁止する
- デフォルトでスタックがRWXなのでRWな空間に引っ越す
- ヒープを適当にrandomizeする
- 共通で使われるコードにある、いらないコードを削除もしくは総取っ替えし、ROPなどに使いにくくする
というような機能を作りました。安易な攻撃には最初の2つが特に効く感じで、前もってサンプルで試してる感じでは、まあ半分強くらいのサンプル攻撃が止まるな、ってところでした。バイナリいじってパフォーマンス(CPUメモリディスク使用量)が落ちると評価が下がってしまうんですが、そのへんもまぁ、問題によっては使えないけどギリギリOKかな、ってレベルでした。
mitigationというのは本質的にあまり意味がないものだと思っていて(おそらく世の中的にもそう思われていて)、やはりそういうゴマかしはさらなる回避策とのイタチごっこになるので、なんらかのsandboxで根本的に根本から断つのが筋というのが最近の流れだと思います。ですが、短期間のコンテストではまあまあ時間かせぎになるし(運が良ければ完治もしうる)、ということで作ってみた感じでした。C++とアセンブリで書き散らかして、2000行くらい。libdisasmとlibdisasm_cfgというのを使った感じ。
初日
練習のために出てきたバイナリが非常に小さく、かつムダな初期化ルーチンが無くなっていたためmitigationを入れるとパフォーマンスの制約を満たさなそう。実際投稿してみて得られる点数は明らかにダメ。あー覚悟はしてたけどbjmit完全にムダだったかな、と思いつつ短期間で使える方法を考える…が思いつかない。
で本番のバイナリは初期化ルーチンが復活してて、手元の確認では問題ないぽい感じになってた…けど投稿してみると実行時間が2倍以上になってるとか言われて泣く。とりあえず速度2倍では0点のはずなので、それはよくないということで焦って、stack overflowしてるところだけmitigateするようないい加減な処置をする。
それでも遅い。そこで、んなわけないだろ!!てかこれ速度で点数引かれてなくね??みたいな感じで混乱しつつ、正当なパッチにした。相変わらず実行時間は2.6倍とか異様なことを言われる不思議大会。
もうこれ何信じたらいいんかわからん…ということでbjmitの積極的な適用ができなくなってしまう。が、この攻撃食らったぽい、というのをmitigationずみのバイナリで試すとたいてい止まっているし、パフォーマンスも手元で測る限りは問題ないし…ということで微妙に使ってみたり使わなかったり、というようなことをしてたと思う。
結論としては手元の評価は間違ってなかったぽいので、最初から手元で大丈夫だと思うだけの全力mitigationをバイナリの内容を考慮に入れつつかけておくべきだった。
2問目を解析してた人がこれはそこらじゅうバグだらけで大変、ということでここを修正すべき、みたいなことを教えてもらって適当にパッチ当てる。ただそれではその時検知されてた問題全ては塞がらなかったぽい…とかやってるうちに、もうこれ相手のバイナリパクろうぜーということで、バイナリパクりゲーになった。
その後出題された3問目もバイナリパクったので、これパッチ担当ていらないよねーと晩に相談する。あとbjmitは見てる限り結構止めてるので信じませんか…というような話もする。
あと運営が時間は内部的には計測できているが、表示上おかしくなっている。明日までに直す努力をするが、本当にできるかはわからない、とか意味不明なことを言っていた。表示上の問題てどう考えてもおかしいので、時間での減点を最初の練習の後くらいにすごくゆるくしたんじゃないかなぁ…と今では邪推している。
2日目
bjmitの評価をしつつ、見つけたバグを眺めていた。ムダに時間を使ったけど、特に発展がなくて残念だった。
とかやってる間に色々と検知できたバグとかの情報が来るので、パッチ書きをする。このへんで色々パッチ書いたけど、どうにも攻撃の数が増加するのにたいしてパッチ書きが後手後手に回ってる感じになる。方針が決まっていればパッチはかなり迅速に書ける準備してあったし実際書けたと思うんだけど、自分でコード読めてないから方針が立たなかったりと。いくつかバグふさいでも全部ふさがってないと更新する意味ないどころか損になる、というルールのせいで、これで全部、とわかるまでどうしてもバイナリ更新に臆病になってしまう。次々と新しいタイプの攻撃を検知してる中、もうバグが無いと確信するのは難しい…
この日から他チームがバックドアを仕込んでくるようになったんだけど、チームの人がバックドアを外す方法を確立しはじめる。結論としてはパッチを頑張って当てるより、バックドア外しの方が良かったのではないかと思う。
このあたりでbjmitがmitigateしただけのバイナリをパクられる。光栄です。bjmitの挙動はチームの人に説明してあるので、チームの人がmitigateを回避するexploitを書いて攻撃して笑う。たしかにある意味mitigateってバックドアみたいなもんだな…とか思う。
謎のパフォーマンス数値表示は相変わらずで、この日は実行時間30倍になってるぜーとか言われてても、点数的には問題ないとかなんとか。
この日、相手チームのバイナリでprogram headerが後ろについてるものがあって、ああたしかにアレ後ろにつけても問題ないよな…とか感心した。program headerを置いてあった領域がcode領域として使えるようになるのでオトク。
2日目が終わった後に、いくつかbjmitに対してやっておいたら良さそうなこととか、適当な自分用ツールなどを整備したりした。
3日目
眠くて疲れて、完全に脳が死んでいた。
前日終了間際に出題された複数バイナリ問題のパッチを準備しておく。開幕早々それを使うと全然動いてないと出て、bjmitのせいかと思ったけどbjmitは無罪でpatchが悪かった。今見るとなんでこんなので動くと思ったの、て感じのパッチで本当にひどい。結構な失点になったぽいので、本当に申し訳ない…
色々バグ探しとかやってたけど、bjmitの運用以外はほとんど意味ない感じになってしまってたと思う。メモリ使用量が増えてる問題があって焦ったけど、運営に聞くと問題ないとのことで、時間に続いてメモリ使用量も不正確だということがわかったりした。本当にひどい。
まとめると
1,3日目ひどくて失点しちゃったのが本当にすいませんすいません…という感じ。1日目はどっちかというと運営が悪いと思うんだけど、3日目は本当にひどかった。まあそれでなくてもパッチ担当はちょっとした失敗が結構でかい失点につながるので、かなりビクビクするルールだなぁ…などと思っていた。それ以外にも、どうもチーム連携みたいなの全然うまくできてないなあ、など反省が多い感じでした。
あとどうもCTF本番もいいんだけど、ツールの準備とかも楽しかったなと。なんかモノ作るの好きなんだなぁと、今更ながら。実際CTF中も私本人は全く信用できないけど、ツールは今思えばまぁまぁ信用できる動作してた気がします…