SECCON 2019 決勝 の Challenge 4 follow-me-again を振り返る
2019/12/21(土)から2019/12/22(日)の2日間にかけてSECCONの決勝が開催されました。 私は友利奈緒としてChallenge 4の出題をしました。好評なようで良かったです。 今年は国内大会と国際大会が同じスケジュール・問題セットで実施されました。 試合時間は6時間+6時間と長期戦でしたね。本当にお疲れさまでした。 私の問題を粘って解いてくれたチームが多く感謝します。 こちらも約30チーム日本語・英語問わず問い合わせが来たり、致命的なバグの修正を競技時間中に行ったりと大変でした…。 (リカバリーはできたものの、本番中に大きなやらかし3つして迷惑かけてごめんなさい。
い つ も の #SECCON pic.twitter.com/9Z5vvxFizi
— 友利奈緒ちゃん (@K_atc) 2019年12月21日
さて、私が出題した問題は follow-me-again です。今年の予選で出題した follow-me は実はこれの予告編でした。 皆さん、どこまでちゃんと解けましたか? follow-me は与えられたバイナリと実行トレース(実行された分岐命令と分岐結果の時系列の並び)から、実行パスを割り出し、そのパスを通るような入力を求めるという問題です。 Write-upはチェックしましたが、
手計算で制約を解く(実行トレースに出現するユニークな分岐命令が少ないので可能)
各分岐命令におけるセマンティクスを手作業でz3で制約式として表現してから、トレースをもとに制約を解く
お手製のファザーを使う
あたりが主だっていました。楽しんでもらえて嬉しいですが、ファジングを除き特定のバイナリに依存した解法が好まれており、私は不満でした。 が、ここまでの流れは完全に計算通りでした(CV 夜神月)。 決勝で私が目指したのは、バイナリが変化したときにも適用できるような一般的な解法をプレイヤーに実施してもらうことです。
決勝の follow-me-again は、SECCON決勝のルールに則る形でAtttackとDefenseのフェーズに分かれています。 Attackは、Defenseの雰囲気を掴んでもらうためのサニタイズ問題1問、暗号やCPUエミュレータの実装に関する知識を問う3問の構成です。 回答状況を見ると2日目に提出が多かったので後回ししてくれたのでしょう。期待通りです。 最初に着手して欲しかったのがDefenseです。 Defenseは、予選と同様計算機を模したバイナリと実行トレースが与えられそれと同じ実行パスを通る入力を求める問題が1時間毎に出題されます。 それを早解きしたチームが得点できます(SECCONのDefense Pointの仕様上、早く解くほどDefense Pointを得られます)。
GitHubに問題とソルバーを雑に置いたので見てみてください。
https://github.com/K-atc/follow-me-again-public
決勝の結果は私好みでした。 Attackは、4問中2問正解が中央値に落ち着きました。全完(すばらしい!)が数チームといういい塩梅の結果です。 Defenseは、国内はkimiyuki(ぼっちーむで国内2位の実力者)と dodododo(国内1位)の争いがありましたが、kimiyukiが大半のポイントを獲得しました。 国際は4チームくらいが奪い合っていましたが、2日目の午後辺りからnoranekoが完全に抑えました。 国内も国際も1番手と2番手の提出時刻の差が10秒や40秒の熾烈な争いとなりました。 限られた数チームが僅差で争う――こうやって難易度調整がうまくいくとうれしいですね。
残り90分!がんばえー
— 友利奈緒ちゃん (@K_atc) 2019年12月22日
残りは国内勢が国内・国際のDefense Pointを抑えちゃうか??
#SECCON pic.twitter.com/YGnpOlOQFL
ここで友利賞のお知らせです。 国内・国際大会それぞれで最も優れたソルバーを書いたチームを表彰します :tada: 奈緒、賞品はありません。あしからず。
国内大会の友利賞は~~~~ kimiyuki です!おめでとうございます! 受賞の理由は、まともに早く動くソルバーを国内で唯一作れたことです。 シンボリック実行に逃げずに貪欲法を使ったソルバーも評価高いです。Weite-up待ってます(´へωへ`*)
国際大会の友利賞は~~~~noraneco です!おめでとうございます! ベスト・オブ友利賞も差し上げます! 受賞の理由は、国際のDefense Pointを抑えたその性能、第11、12ラウンドで今までの流れを断ち切ったバイナリに対しても途切れずに即答するその性能です。 kimiyuki ソルバーは第11ラウンドで3回分のDefense Pointを取り逃してもったいなかったです。 ではWeite-up待ってます(´へωへ`*)
…まぁ彼らのソルバーは2,3分かかるようですが、私のソルバーは10秒です。まだまだですね(とはいえ私のソルバーを見れば分かると思いますが、時間の制約上仕方ないです)。
最後に、遊んでくれた皆様ありがとうございました! Challenge 4のおかげで学びと実践のある2日間になったなら嬉しいです。
おまけ:問題を1問も解けなかった人へ
問題を解くうえで前提知識が足りてなかったのでしょう。 最近のバイナリ解析を学んでみてください。キーワードとしては、DBI、シンボリック実行、Intel Software Development Manual、です。 どれもアカデミア方面でバイナリ解析や脆弱性検出で必要な知識なので、触りだけでも理解しておくと今後の人生で役立つでしょう。 Intel SDMは、分岐命令のジャンプ有無の計算方法がどこに書かれているのかを覚えて、読み解けるようになりましょう。
初学者向けの参考書籍として、Practical Binary Analysis | No Starch Press をおすすめします。
Special Thanks
Attackの問題で、x86エミュレータの rkoder/emu_x86 をお借りしました。素直な実装で使いやすかったです。