who3411のブログ

情報系の勉強やイベントの参加に関するブログ(をしたい)です。

American Fuzzy LopとIntel Pinを組み合わせたい

この記事はセキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2018の18日目の記事になります。

adventar.org

はじめに

セキュリティキャンプ全国大会2017で参加させていただいたwho3411です。最近ファザーであるAmerican Fuzzy Lopに、動的解析を組み合わせようとわちゃわちゃしていました。この記事は、最終的にAmerican Fuzzy Lopと動的バイナリ計測ツールであるIntel Pinを組み合わせて遊びたいと思います。なお、American Fuzzy Lopのコードリーディング時に使用していたhackmdを公開します。American Fuzzy Lopのコードリーディングをする方の助けになればと思います。(する方がいればの話ですが…)

AFL解析中…解析中 - HackMD

ファジング

American Fuzzy Lop(以下、AFLと呼ぶ)は、簡単に言うと、ファジングを行うための軽量なファザーです。この時点で、「ファジング？」「ファザー？」となると思うので説明しておくと、

  • ファジング: プログラムに対して自動的に生成した大量のデータを送って、送られたプログラム側の応答や挙動を確認することで、脆弱性診断やテストを行う手法
  • ファザー: ファジングを行うためのソフトウェア、またはツール

です。ファジングにはブラックボックス，グレーボックス、ホワイトボックスなど、様々な種類のファジングがありますが、AFLはグレーボックスになります。雑に説明すると、

  • ブラックボックス: プログラムの中身がわからない状態
  • グレーボックス: プログラムの中身はわからないけど、計測などを行って情報を収集する
  • ホワイトボックス: プログラムの中身がわかっている状態

みたいな感じです。AFLは、後述しますが、ファジングをかけるプログラム側に計測用のアセンブリを入れ込んで計測を行います。

動的バイナリ計測(Dynamic Binary Instrumentation)

Intel Pinは、簡単に言うと、動的バイナリ計測(Dynamic Binary Instrumentation, DBI)を行うことができるツールです。DBIは、実行中のプログラムに対してコードを挿入する技術ですが、Intel Pinでは、プログラムの実行中だけではなく、ロード時点でもコードを挿入することができます。

Intel Pinの、プログラムの実行中にコードを挿入する方法では、命令単位、基本ブロック単位、トレース単位の3種類があり、トレース単位が最も大きい単位になっています。なので、トレース単位は複数の基本ブロック単位を含んでいる可能性があり、また基本ブロック単位は複数の命令単位を含んでいる可能性があります。

Intel Pinは、多くのマニュアルコードがあり、例えばプログラム全体で実行された命令数をカウントするプログラムや、読み書きされたメモリアドレスをファイルに出力するプログラムなどがあります。詳しくは、Intel Pinのサイトを見ることをお勧めします。

AFLとIntel Pinを組み合わせる手順

今回は、AFLがプログラム中に入れ込んでいる計測用のアセンブリだけではなく、Intel Pinで収集した情報も含めてファジングを行うようにすることをゴールとしていきます。そのために、以下のような手順で進めていこうと思います。

  1. AFLがファジングを実行するまでの流れを知る
  2. AFLとIntel Pinを組み合わせる方法を探る
  3. 実際に組み合わせてみる

AFLがファジングを実行するまでの流れ

AFLでは、AFL用のコンパイラであるafl-gccでコンパイルを行い、ファジング本体であるafl-fuzzでファジングを行います。afl-gccを読んで見ると、色々とコンパイルオプションをつけた上でgccでコンパイルしているようでした。その中で重要なのが -B オプションで、これはgcc内部で実行されるプログラムである cpp 、 cc1 or cc1plus 、 as 、 ld のディレクトリを指定するオプションです。このオプションで、afl-gccはカレントディレクトリを指定しています。AFLディレクトリ直下をみてみると、 as が存在しています。これは、AFL用のアセンブラであるafl-asのシンボリックリンクで、つまりafl-asを見れば良さそうです。

afl-asの計測用コードの内容

afl-asを見てみると、計測用のコードを挿入した上で、オプションをいくつかつけて本来の as を実行していました。計測用コードは、複数箇所挿入されていました。計測用コードにはいくつかの条件がありますが、基本的には j + m 以外の命令( je 、 jl などの条件分岐)の手前に挿入します。

また、計測用コードは以下のような手順になっています。(詳しく読まなくてもいいという人は、以下の箇条書き部分を飛ばしてください)

  • いくつかのレジスタを保存し __afl_maybe_log に遷移する。この時、 rcx に id(乱数 % MAPSIZE) を格納しておく。なお乱数は、アセンブリコード挿入時点で確定しているため、ファジング実行ごとに変化する訳ではない。(MAPSIZEは、65536である)
  • AHにフラグを保存し、__afl_global_area_ptr の値を確認し、0であれば __afl_setup に遷移する。また0でなければ __afl_store に遷移する。
    • __afl_store では prev_id ^ id を行い rcx に格納した後、 prev_id を __afl_prev_loc に格納し1ビットシフトする。最後に、 __afl_prev_loc の該当する位置をインクリメントし、そのまま __afl_return へ入る。
    • __afl_return では、保存したフラグを復帰したのち、ret命令を行う
  • __afl_setup_failure が0でなければ、 __afl_return に遷移する。
  • __afl_setup_failure が0であれば、 __afl_global_area_ptr の値を取り出しテストを行ったのち、 __afl_setup_first に遷移する
  • 様々なレジスタを保存したのち、 r12 にスタックポインタを保存して rsp を0x10減算したのち、 rsp の下位4ビットを0にする。
    • 減算して下位4ビットを0にするのは、スタックは16bit境界であることを前提としているため
  • .AFL_SHM_ENV の環境変数を取得し、 結果が0であれば __afl_setup_abort へ遷移する
    • __afl_setup_abort では、保存したレジスタを復帰したのち、 __afl_return へ遷移する
  • 結果が0でなければ、結果を atoi で数値に変換する。
  • その後、 shmat で共有メモリを作成する。この時、 shmat の結果が-1であれば __afl_setup_abort へ遷移する。
  • shmat の結果である共有メモリアドレスを __afl_area_ptr および __afl_global_area_ptr に保存し、 rdx へ格納しておく。そしてそのまま __afl_forkserver へ入る。
  • 2度 rdx をプッシュしたのち、 FORKSRV_FD + 1 のファイルディスクリプタに対してデータを write する。戻り値が4でなければ __afl_fork_resume へ遷移する。
    • __afl_fork_resume では、共有メモリのクローズ、スタック領域からレジスタへの復帰を行い、 __afl_store へ遷移する。
  • 戻り値が4であった場合、そのまま __afl_fork_wait_loop へ入る。
  • FORKSRV_FD のファイルディスクリプタに対してファイルを read する。戻り値が4でなければ __afl_die へ遷移する。
    • __afl_die では、 exit(0) に相当する命令が実行される。
  • 4であれば、 fork() を行う。この時、戻り値が0未満であれば __afl_die へ遷移し、0であれば __afl_fork_resume へ遷移する。
    • この時、 FORKSRV_FD および FORKSRV_FD + 1 がクローズされるため、生成された子プロセスは通常のプログラム実行へと遷移していく。(main関数の最初に __afl_maybe_log が実行されるため)
  • 次に __afl_fork_pid へ戻り値である子プロセスIDを格納し、子プロセスIDを FORKSRV_FD + 1 のファイルディスクリプタに対して write する。
  • その後、子プロセスIDに対して waitpid を実行し、戻り値が0以下であれば __afl_die へ遷移する。そうでなければ、waitpid で取得した status を子プロセスに対して FORKSRV_FD + 1 を経由して write する。
  • 最後に __afl_fork_wait_loop へ遷移することで、ループ処理となる。

上記の内容を簡単にまとめると、こんな感じになります。

  1. 最初に計測コードに入ったら、環境変数 SHM_ENV_VAR から共有メモリ用の値を取得し、その値を利用して共有メモリにアタッチする。
  2. 後述するAFLのforkserver用の受信用ディスクリプタである FORKSRV_FD + 1 に対して、4バイトのデータを write する。
  3. 後述するAFLのforkserver用の送信用ディスクリプタである FORKSRV_FD から4バイトのデータを read する。
  4. fork を行い、子プロセスは本来のプログラムを実行し、親プロセスは FORKSRV_FD + 1 から子プロセスidを write し、 waitpidによって子プロセスの終了を待つ。
    • 子プロセスは、今後計測用コードに入るたびに、「どの計測用コードからどの計測用コードへ遷移したのか」という情報を、ステップ1でアタッチした共有メモリに追加していく。
    • 共有メモリは64KBあるため、計測用コードを識別するidは16ビットになっている。
    • 遷移前の計測用コードのidを prev_id 、遷移先の計測用コードのidを cur_id 、共有メモリを trace_bits とした時、 trace_bits[(prev_id >> 1) ^ cur_id] を加算することで、遷移情報を記録している。
  5. 子プロセスの終了後、 FORKSRV_FD + 1 から waitpid の引数である status を write し、ステップ3へ戻る。

一言で言ってしまえば、プログラム中の遷移情報を計測している、というだけです。あと面白いのは、fork を行い、AFL本体とやり取りを行うための親プロセスを常駐させている点です。(これのおかげで、プログラムを実行するごとに shmat などを行う必要がなくなっています)ちなみに、AFL本体では共有メモリ trace_bits の情報を使用することで、効率的にファジングを行うようにしています。

計測用コードとファジングの関係性

前記の計測用コードでは、 FORKSRV_FD と FORKSRV_FD + 1 を用いてAFL本体とのやり取りを行っていました。やり取りの際、どのようなデータを送っているか、またAFL本体ではどのような処理を行っているのかを知る必要があります。その部分を知るために、ファジングを行うafl-fuzzを見て、流れを確認しようと思います。なおafl-fuzzのコードリーディングでは、以下のサイトが非常に参考になりました。

shimasyaro.hatenablog.com

afl-fuzzでは、forkserverと呼ばれる仕組みが用意されています。計測用コードの説明でも何度か出てきましたが、forkserverは、前記の計測用コードの親プロセスに当たります。つまり、

  • afl-fuzz: forkserverとやり取りを行い、プログラムを実行してもらう。
  • forkserver: afl-fuzzとやり取りを行い、 fork によってプログラムを実行する。

という感じです。forkserverの設定は、afl-fuzzの init_forkserver 関数を読むと書いてあります。 init_forkserver では、 fork を行い、子プロセスから execv によって計測用コードを埋め込んだプログラムを実行しています。最後に、forkserverから4バイトのデータを受け取ることができたら init_forkserver を終了します。

次にforkserverが出てくるのは、afl-fuzzの run_taget 関数です。 run_taget では、forkserverとやり取りをすることで、プログラムを実行してもらいます。まずafl-fuzzからforkserverに向けて、4バイトのデータを write します。次にforkserverから子プロセスidを受け取り、最後にforkserverから子プロセスの終了ステータスを受け取ります。

AFLとIntel Pinを組み合わせる方法

AFLとIntel Pinを組み合わせるには、以下のようなことをすれば良さそうです。

  • ファジングの対象となるプログラムを実行するより前に、共有メモリ trace_bits を用意しておく。
    • 環境変数 SHM_ENV_VAR の値を利用して、 shmat によって共有メモリをアタッチする。
  • ファジングの対象となるプログラムの実行直前に、forkserverにあたるコードを実行する。
    • 「afl-asの計測用コードの内容」でまとめたステップ2から5にあたるコードを実行する。
  • trace_bits[(prev_id >> 1) ^ cur_id] を加算して遷移情報を記録する部分を作成する。
    • 条件分岐命令の手前に trace_bits[(prev_id >> 1) ^ cur_id]++ にあたるコードを挿入する。

という感じに、色々と読んだ上でやり方を考えていたら、こんなリポジトリを発見しました。

github.com

どうやら、やろうと思っていたことが全部含まれているようです。このリポジトリでは、以下のような処理を行うコードが用意されています。

  • forkserver.c の startForkServer 関数では、forkserverに関する部分を一括して請け負っている。
  • startForkServer 関数は、ファジングの対象となるプログラムを読み込んだ時、Intel Pinで main の最初の命令の手前に startForkServer を実行している。
    • ファジングの対象となるプログラムの main 関数の最初の命令実行後、 PIN_Detach() によって、解析対象プログラムから離れる
    • 以上の動作により、forkserverをintel PINの使用により解決している。
  • ブロック遷移では、 ret 命令ではなく、条件分岐命令かつ分岐先アドレスが命令ポインタからのオフセットか即値でない部分(メモリやレジスタからの値)の場合に trace_bits[(prev_id >> 1) ^ cur_id]++ にあたるコードを実行するようになっている。
    • 乱数 % MAP_SIZE であった id は、分岐先のアドレスを使用することで代用している。

これによって、AFLとIntel Pinを組み合わせたファジングを行うことができるようになりました。

新たな情報を収集したファジングを行う

何を作ろうかと考えた結果、ACM CCS 2017で発表されたSlowFuzzを、AFLとIntel Pinを組み合わせて作ることにしました。通常、ファジングは脆弱性を発見するために用いられますが、SlowFuzzでは実行時間の長くなるような入力を発見します。その際に用いられる情報は、プログラムの命令実行数です(SlowFuzzの実装と正確には違うのですが、今回はより正確な命令実行数を取得するため、「検討」と書かれていた正確な命令追跡を行いました)。なぜ命令実行数にしているか、という点が気になった方がいれば、論文の5.6節を見ることをお勧めします。

さて、上記の通り、SLowFuzzでは命令実行数が必要となります。今回は、Intel Pinを使って命令実行数を取得し、その情報をAFLと共有させるようにしてみましょう。共有する方法ですが、共有メモリである trace_bits を4バイト拡張して、そこに命令実行数を格納するようにしました。共有メモリを拡張するには、afl-fuzzの setup_shm 関数にある shmget の第2引数を、 MAPSIZE から MAPSIZE + 4 にすればできます。拡張した4バイトには、基本ブロック単位で命令実行数を加算していくようにします。

最終的に出来上がったAFLとIntel Pinのコードは、それぞれ以下にあります。

github.com

github.com

プログラムを正常に実行できた場合、以下のような画面が出るはずです。このafl-pin-slowfuzzでは、実際のSlowFuzzとは異なりますが、AFL本来の機能に加えて、命令実行数の多い入力を生成しやすいように設計してあります。

f:id:who3411:20181218053219p:plain
afl-pin-slowfuzzの実行画面

おわりに

今書いた記事を見返してみて雰囲気しか伝わらなさそうな気がしてます

いかがだったでしょうか。おそらく、この記事を読んだ大半の方が、最初に「ファジング」という用語を聞いて、どのようなものか理解できなかったのではないかと思います。ファジングは海外では結構認知度があるように感じられるのですが、どうも日本ではあまり話題を聞かない気がします。

今回はIntel Pinを組み合わせましたが、他にもシンボリック実行ツールを組み合わせたものや、テイント解析を組み合わせたものなど、様々な種類が存在します。また発見したい入力についても、脆弱性の発生するもの、速度が遅くなるものなど、様々です。

そういえば、最近[1812.00140] Fuzzing: Art, Science, and Engineeringという、ファジングに関する調査論文が出たようです。(恥ずかしながら、まだ読めていません…)この論文のFig. 1を見ると、IEEE S&P 2018で発表されたCollAFLやAngoraなど、最新のものまで紹介されているようです。 ACM CCS 2018で発表されたHawkeyeはないので、そこまで最新のものはないのかもしれません。(近日、別のアドベントカレンダーで、いくつかのファジングの論文について話そうと思っていたのですが、どうしましょう…)

もっと日本でファジングに関する話が活発に聞けたらなぁと思う今日この頃です。というところで、技術的な内容が多くて理解できない部分があったかもしれませんが、本記事は以上となります。明日はmoppoi5168さんのBadUSB関係のお話です。お楽しみに！