American Fuzzy LopとIntel Pinを組み合わせたい
この記事はセキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2018の18日目の記事になります。
はじめに
セキュリティキャンプ全国大会2017で参加させていただいたwho3411です。最近ファザーであるAmerican Fuzzy Lopに、動的解析を組み合わせようとわちゃわちゃしていました。この記事は、最終的にAmerican Fuzzy Lopと動的バイナリ計測ツールであるIntel Pinを組み合わせて遊びたいと思います。なお、American Fuzzy Lopのコードリーディング時に使用していたhackmdを公開します。American Fuzzy Lopのコードリーディングをする方の助けになればと思います。(する方がいればの話ですが…)
ファジング
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で収集した情報も含めてファジングを行うようにすることをゴールとしていきます。そのために、以下のような手順で進めていこうと思います。
- AFLがファジングを実行するまでの流れを知る
- AFLとIntel Pinを組み合わせる方法を探る
- 実際に組み合わせてみる
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
へ遷移することで、ループ処理となる。
上記の内容を簡単にまとめると、こんな感じになります。
- 最初に計測コードに入ったら、環境変数
SHM_ENV_VAR
から共有メモリ用の値を取得し、その値を利用して共有メモリにアタッチする。 - 後述するAFLのforkserver用の受信用ディスクリプタである
FORKSRV_FD + 1
に対して、4バイトのデータをwrite
する。 - 後述するAFLのforkserver用の送信用ディスクリプタである
FORKSRV_FD
から4バイトのデータをread
する。 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]
を加算することで、遷移情報を記録している。
- 子プロセスの終了後、
FORKSRV_FD + 1
からwaitpid
の引数であるstatus
をwrite
し、ステップ3へ戻る。
一言で言ってしまえば、プログラム中の遷移情報を計測している、というだけです。あと面白いのは、fork
を行い、AFL本体とやり取りを行うための親プロセスを常駐させている点です。(これのおかげで、プログラムを実行するごとに shmat
などを行う必要がなくなっています)ちなみに、AFL本体では共有メモリ trace_bits
の情報を使用することで、効率的にファジングを行うようにしています。
計測用コードとファジングの関係性
前記の計測用コードでは、 FORKSRV_FD
と FORKSRV_FD + 1
を用いてAFL本体とのやり取りを行っていました。やり取りの際、どのようなデータを送っているか、またAFL本体ではどのような処理を行っているのかを知る必要があります。その部分を知るために、ファジングを行うafl-fuzzを見て、流れを確認しようと思います。なおafl-fuzzのコードリーディングでは、以下のサイトが非常に参考になりました。
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]++
にあたるコードを挿入する。
- 条件分岐命令の手前に
という感じに、色々と読んだ上でやり方を考えていたら、こんなリポジトリを発見しました。
どうやら、やろうと思っていたことが全部含まれているようです。このリポジトリでは、以下のような処理を行うコードが用意されています。
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のコードは、それぞれ以下にあります。
プログラムを正常に実行できた場合、以下のような画面が出るはずです。このafl-pin-slowfuzzでは、実際のSlowFuzzとは異なりますが、AFL本来の機能に加えて、命令実行数の多い入力を生成しやすいように設計してあります。
おわりに
今書いた記事を見返してみて雰囲気しか伝わらなさそうな気がしてます
いかがだったでしょうか。おそらく、この記事を読んだ大半の方が、最初に「ファジング」という用語を聞いて、どのようなものか理解できなかったのではないかと思います。ファジングは海外では結構認知度があるように感じられるのですが、どうも日本ではあまり話題を聞かない気がします。
今回はIntel Pinを組み合わせましたが、他にもシンボリック実行ツールを組み合わせたものや、テイント解析を組み合わせたものなど、様々な種類が存在します。また発見したい入力についても、脆弱性の発生するもの、速度が遅くなるものなど、様々です。
そういえば、最近[1812.00140] Fuzzing: Art, Science, and Engineeringという、ファジングに関する調査論文が出たようです。(恥ずかしながら、まだ読めていません…)この論文のFig. 1を見ると、IEEE S&P 2018で発表されたCollAFLやAngoraなど、最新のものまで紹介されているようです。 ACM CCS 2018で発表されたHawkeyeはないので、そこまで最新のものはないのかもしれません。(近日、別のアドベントカレンダーで、いくつかのファジングの論文について話そうと思っていたのですが、どうしましょう…)
もっと日本でファジングに関する話が活発に聞けたらなぁと思う今日この頃です。というところで、技術的な内容が多くて理解できない部分があったかもしれませんが、本記事は以上となります。明日はmoppoi5168さんのBadUSB関係のお話です。お楽しみに!