アメリカンファジーロップの話です．
アメリカンファジーロップ
- うさぎ
- もふもふ
※画像はWikipediaから(PublicDomain)
ファジング
American Fuzzy Lopの前に，まずファジング(Fuzz Testing)について簡単に説明します．
ざっくり言うと，機械的に生成したテストデータでソフトウェアの挙動を見る手法です．最近は脆弱性診断なんかで良く使われています．ブラックボックステストによく使われますが，実際はブラックボックステストに限定してはいません．
ファジングのためのツールをFuzzerといいます．もふもふ．
改めて American Fuzzy Lop
afl https://code.google.com/p/american-fuzzy-lop/
「実用的なバイナリ用のFuzzer実装」と書かれています．
他の手法だとカバレッジを上げるのが難しかったが，コンパイル時にコード操作したり，遺伝的アルゴリズムでデータを生成することでカバレッジ上げているようです．
vulnerability trophy case のページを見てみると，BashのShellshockのCVE-2014-6277とCVE-2014-6278が記憶に新しいですね．
ちょっと面白そうだったので，とりあえず動かしてみます．
ダウンロード
Google Codeのリポジトリは空なので，tgzをダウンロードします．
$ wget http://lcamtuf.coredump.cx/afl.tgz
$ tar -vxzf afl.tgz
(注意：記事を書く前は，0.45bでしたが，改めて見たら0.47bになってます．何か変わっているかもしれません)
x86とARM(experimental)の実装が入っています．JVM用とか書けばScalaやJavaのコードに対しても実行できるのかも(？)．
依存ライブラリも無くてかなり小さな実装です．
コンパイル
gccとかは事前に環境整ってる前提です．
64ビット環境の場合は，config.h を編集して，#define USE_64BITのコメントアウトされた行を有効にしてください．(有効にせずビルドしても，USE_64BITを有効にしろというエラーが出るので気づくと思います)
$ make
gccフロントエンドのラッパーであるafl-gccやafl-asが生成されていれば大丈夫です．
実行
とりあえず，aflに入っている，test-instr.cで試してみます．中身を見れば分かりますが，標準入力から与えられた最初のバイトが'0'であるかチェックするだけのプログラムです．
$ ./afl-gcc -O3 test-instr.c
mkdir test_in
echo -n 'hoge' > test_in/hello
./afl-fuzz -i test_in -o test_out ./a.out
test_in/hello等に適当な初期データを与えて上げる必要があります(中身は何でも良いです)
VM上で試しましたがexec speedは2000/secくらいでした．
実行はずっと続くので，favored pathsあたりの値を見て，適当に止めます．
今回の例だとpathsは2なので一瞬で100%になると思います．
実行後(実行中でも)test_out/queueを見ると，どんなデータでプログラムの実行経路が変わったのかがわかります．
$ ls -l test_out/queue
-rw-rw-r-- 2 kawahira kawahira 4 11月 15 21:55 2014 id:000000,orig:hello
-rw------- 1 kawahira kawahira 2 11月 15 21:55 2014 id:000001,src:000000,op:havoc,rep:32,+cov
中身を見てみると"hoge"(初期データ) と "0\xfc"(ちゃんと0から始まっている)がありました．
もうちょっと見てみる
さっきの例は先頭の1バイトで条件分岐するだけの例だったので，ランダムなデータを生成していても可能な例でした．
なので，ちょっとだけ
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int mystrcmp(char const *a, char const *b) {
do if (*a - *b) break; while(*++a & *++b);
return *a - *b;
}
int main(int argc, char** argv) {
char buf[8] = {0};
if (read(0, buf, 8) < 4) {
exit(1);
}
if (mystrcmp(buf, "chino") == 0)
printf("こころぴょんぴょん\n");
else if (mystrcmp(buf, "rize") == 0)
printf("ロップイヤーもいいかもしれない\n");
else if (mystrcmp(buf, "syaro") == 0)
printf("土下座かわいい\n");
exit(0);
}
こんなプログラムを食わせてみると，cXXXXX → chXXXX → chiXXXXX …… と順番にmystrcmpのループを抜けるタイミングが違うデータが生成されて，最終的にchinoという文字列でifの経路が変わるのを検出できます．
ただ，10分くらい実行しただけでは，rizeやsyaroには到達しませんでした．"riXX"や"syXX"は試していたようなので放っておけばそのうち通るのだとは思います．
適当に手元にあったプログラムに対して実行した感じだと，他のライブラリ(標準ライブラリ含む)内で分岐していたり，．(なので上の例ではmystrcmp作っています)．
説明にstatic linkしろと書いてあるので，libcとかも静的リンクすれば中を見てくれるのかもしれません．
Pulling JPEGs out of thin air
Jpegデコーダに対して１日実行したら，Jpegとしてデコード可能なバイト列が生成された！という話です．
(もちろんデコード不可能なパターンやエラーになるパターンも生成されるし，本来はこちらが重要なんだろうと思います)
ランダムなデータを生成してvalidなJpegファイルになる可能性はほぼ０ですが，ヘッダ，ハフマンテーブル，DCTデータが正しく生成されたときにコードの実行経路が変わっていくことで最終的に正常にデコードされるjpegファイルが出来上がってるようです．
まとめ
- 実行された経路を観察しながら遺伝的アルゴリズムでテストデータを変更してカバレッジを上げる
- ティッピーはアメリカンファジーロップではありません
- 「ご注文はAmerican Fuzzy Lopですか？」これが書きたかっただけです
- 中身はついでです