技術者ブログ

ファジング(Fuzzing)が便利

コンピュータにランダムに生成させたデータを入力とし、ソフトウェアの予期せぬ挙動を観測・発見する手法がファジングです。脆弱性発見の文脈で使われることが多いですが、一般的なごく普通のソフトウェア開発でも便利に使うことができます。私もこれまでに何度か、開発中の関数にファジングを行うことで、想定できていなかったバグを見つけたことがあります。

ファジングの大きな魅力の1つは、個人の想像力を超えることができる点です。開発をテスト駆動で進めているとしても、必要となるテストをすべて網羅できていない場合が多々あります。テスト駆動開発はあくまでも個人(あるいはチームメンバー)が見つけることができたテストしか実行できないので、その人の能力や想像力を超えることができません。しかしファジングであれば、人が考えもつかないようなパターンを試してくれます。もちろんファジングもブルートフォース的に全パターンを試すわけではないので、まだ抜けがある可能性はありますが、近年のコンピュータの性能の向上は著しいため、かなりの高確率で良いテストを発見してくれます。

JSONパーサの実装でのファジング

今回、JSONパーサを独自に実装する機会がありました。そのコードをチームメンバーに読んでもらった際に、以下のようなパターン(数値を指数形式で記述したもの)はValidなJSONであるが、私が実装したパーサだとエラーになるのではないか、という指摘を受けました。

[ 1.797693e+308 ]

試してみたところ、確かにそのとおりでした。このバグは、私が上記パターンを想定できていなかったことが原因でした。そして、なるほど...と思ったのと同時に、「このようなパターンはファジングで発見できそうだな」と思いつきました。

ファジングでは通常ランダムにデータを入力しながらソフトウェアが落ちたり重くなったりする状況を待ちますが、今回のケースのJSONパーサのように期待される挙動がはっきりしている場合には、「既存の実装との挙動の差を見る」というアプローチが可能になります。具体的には

• ランダムなデータを生成する
• 既に完成している(信頼できる)パーサに食わせる
• 開発中のパーサに食わせる
• どちらか片方だけがパースエラーになる場合を見つけ、その原因を調べる

というアプローチです。このアイデアはどう考えてもうまく行くだろうと思ったのですが、今回については予想外の展開となりました。

実装ごとの仕様がバラバラ

ファジングを開始したところ、あっという間に探していたデータが見つかりました。つまり、一方のパーサではエラーとなるが、もう一方のパーサは正常だと判断するものです。しかし実際にその中身を確認したところ、JSONの仕様としては間違っているものでした。このとき使った既存のJSONパーサは、ある程度データがInvalidなものでも、うまいこと受け入れて処理しよう、というようなゆるいスタンスで作成されていたのです。逆に私が開発していた(開発途中の)パーサは、正しくエラーとしていました。

これではファジングの目的が達成できないので、別のJSONパーサ実装を持ってきて同じことをしました。しかし、今度はまたちょっと違うパターンのデータで同じ現象になりました。こちらのパーサも、やはりJSONの仕様としては不正であるデータを、正しいものとして扱ってしまうのです。

そこで考えを変えて、さらに1つ既存のJSONパーサを持ってきて、以下のようにファジングすることで、一応の目的を達成することができました。このとき、上に書いたような指数のパターンもファジングによって発見できることを確認しました。

• ランダムなデータを生成する
• 既存の3つのパーサすべてに食わせる
• 開発中のパーサに食わせる
• 既存の3つのパーサ全てが「正常」と判断したが、開発中のパーサが「エラー」とした場合を見つけ、原因を調査する

ちょっと事前に考えていたのとは別の方法となりましたが、一応、ファジングによって想像できていなかったテストを発見する、という目的は達成できました。

カオスすぎるJSONパーサの世界

それにしても、JSONは比較的シンプルな仕様であるにも関わらず、ここまでパーサごとの差があるとは驚きました。このカオスっぷりを皆さんもすぐ試せるように、こちらのリポジトリを用意してみました。

使い方はシンプルで、

gradle run

とするだけです。

ここでは下記の5つのJSONパーサ(いずれもJava製)に対してファジングを行います。

• JSON.orgの実装
• GSON
• Quick-JSON
• JSONIC
• MongoDB(JavaDriver)

それぞれの出自についてはbuild.gradleファイルを参照してください。

ファジングによって、この5つの実装それぞれについて、「そのパーサだけが正常と判断し、他の4つのパーサは皆エラーとする」ようなデータを見つけます。え？そんなデータがあり得るの...と感じるかと思いますが、見事に見つかります。

> Task :run [ES]8Z0\`<E44I2] [$by;] [/*/l] [gF\NF.L] ['?_\'] -------------------------------- Testing >>> [ES]8Z0\`<E44I2] JSON.org:OK GSON::com.google.gson.JsonSyntaxException: com.google.gson.stream.MalformedJsonException: Use JsonReader.setLenient(true) to accept malformed JSON at line 1 column 6 path $ Quick-JSON::com.codesnippets4all.json.exceptions.JSONParsingException: @Key-Heirarchy::root/ @Key:: , or } is expected...@Position::9 JSONIC::net.arnx.jsonic.JSONException: 1: 予期しない文字'8'が見つかりました。[ES]8 <- ? MongoDB::com.mongodb.util.JSONParseException: [ES]8Z0\`<E44I2] ^ -------------------------------- Testing >>> [$by;] JSON.org::org.json.JSONException: Expected a ',' or ']' at 5 [character 6 line 1] GSON:OK Quick-JSON::com.codesnippets4all.json.exceptions.JSONParsingException: @Key-Heirarchy::root/a[0]/ @Key:: Illegal character '$' is identified while parsing for VALUE_TOKEN...@Position::6 JSONIC::net.arnx.jsonic.JSONException: 1: 予期しない文字';'が見つかりました。[$by; <- ? MongoDB::com.mongodb.util.JSONParseException: [$by;] ^ -------------------------------- Testing >>> [/*/l] JSON.org::org.json.JSONException: Missing value at 1 [character 2 line 1] GSON::com.google.gson.JsonSyntaxException: com.google.gson.stream.MalformedJsonException: Unterminated comment at line 1 column 6 path $[0] Quick-JSON:OK JSONIC::net.arnx.jsonic.JSONException: 1: 配列が閉じていません。[/*/l] <- ? MongoDB::com.mongodb.util.JSONParseException: [/*/l] ^ -------------------------------- Testing >>> [gF\NF.L] JSON.org::org.json.JSONException: Expected a ',' or ']' at 4 [character 5 line 1] GSON::com.google.gson.JsonSyntaxException: com.google.gson.stream.MalformedJsonException: Unterminated array at line 1 column 5 path $[1] Quick-JSON::com.codesnippets4all.json.exceptions.JSONParsingException: @Key-Heirarchy::root/a[0]/ @Key:: Illegal character '\' is identified while parsing for VALUE_TOKEN...@Position::8 JSONIC:OK MongoDB::com.mongodb.util.JSONParseException: [gF\NF.L] ^ -------------------------------- Testing >>> ['?_\'] JSON.org::org.json.JSONException: Unterminated string at 7 [character 8 line 1] GSON::com.google.gson.JsonSyntaxException: com.google.gson.stream.MalformedJsonException: Unterminated string at line 1 column 8 path $[0] Quick-JSON::com.codesnippets4all.json.exceptions.JSONParsingException: @Key-Heirarchy::root/a[0]/ @Key:: Quote/COMMA/] is expected. Unexpected EOF...@Position::13 JSONIC::net.arnx.jsonic.JSONException: 1: 文字列が閉じていません。['?_\'] <- ? MongoDB:OK BUILD SUCCESSFUL in 12s 2 actionable tasks: 1 executed, 1 up-to-date

ファジングなので、実行するたびに異なる結果となります。上記の例は、次のような意味になります。

[ES]8Z0\`<E44I2] というデータは、JSON.orgのパーサのみ正常と判断する

[$by;] というデータは、GSONのパーサのみ正常と判断する

[/*/l]

というデータは、Quick-JSONのパーサのみ正常と判断する

[gF\NF.L] というデータは、JSONICのパーサのみ正常と判断する

['?_\'] というデータは、MongoDBのパーサのみ正常と判断する

鋭い人は何となく原因になりそうな要素がわかるかと思いますが、それにしてもここまでバラバラとは驚きです。

ここで行ったような「5種類のパーサの実装の差を見つける」ようなことも、仮にコードを人が読んで行うとしたら非常に労力がかかりますが、ファジングだと効率よく見つけることができます。ソフトウェア開発や調査において、ファジングでしかできないことがある、ということがよくわかります。

まとめ

今回は「普通の開発でもファジングが結構便利に使える」という感じでブログを書こうと思っていたのですが、いつの間にかJSONパーサのカオスな世界を紹介する記事に変貌してしまいました。パーサごとに「入力が乱れていてもやさしく扱ってあげよう」みたいな哲学があったりなかったりするようなので、挙動の差があるようです。

例に挙げた5つのパーサはどれもJavaの実装ですが、他の言語用のパーサでも同じようなことになっているかもしれません。あまり深入りしたくない世界を見てしまった感じです。