who3411のブログ

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

これまで調べてきたファジングの話

この記事は静大情報LT大会(IT) Advent Calendar 2018の21日目の記事になります。

adventar.org

はじめに

今年度は、静大情報LTで情報危機管理コンテストやボゴソートの話をしていたものです。

最近はまともなアウトプットを一切行っていなかったので、この機会にファジングに関する話をしようと思います。また折角ブログとして投稿するので、5分では語りきれないような内容について書こうと思います。

ちなみに、この記事にプログラムはほとんど出てきません。プログラムを読みたい、という方がいらっしゃいましたら、先日ブログに書いた、こちらの記事を読むことをお勧めします。

who3411.hatenablog.com

注意

注意深く調べてはいますが、この記事の情報が必ずしも全て正しいわけではありません。予めご了承した上で読んでいただければと思います。

ファジング

ファジングとは、プログラムに対して自動的に生成した大量のデータを送ることで、データを送ったプログラム側の応答や挙動を確認する、脆弱性診断やテスト手法の1つです。また、ファジングを行うためのソフトウェアやツールのことを、ファザーと言います。ファザーには、American Fuzzy LopやlibFuzzerなどがあり、多くの脆弱性が発見されたりしています。

近年の出来事だと、あらかじめ用意されたプログラムの脆弱性を発見・パッチ記述・攻撃コード作成といった流れを自動化するコンテストであるDARPA Cyber Grand Challengeにおいて、決勝まで進出したDrillerやAFLFastなどがファジングを使用しています。またファジングと機械学習を組み合わせることで、ファジングの性能をあげる研究も行われています。

このようなファジングに関して、今回は歴史や動向を話すことができたらと思います。

ファジングの歴史

1990年にMillerらによって発表された論文時点では、大量に生成したデータを用いて、クラッシュやハングを検出するのみでした。大量のデータを生成するプログラムと、対話型プログラム用に記事デバイスファイルを作成するプログラムを使用することで、様々なプログラムに対してファジングを実施するというものでした。1995年の論文では、GUIベースのツールや、ネットワーク、システムライブラリなどに対してファジングをかけた結果が記載されました。

1998年、フィンランドのオウル大学でPROTOSプロジェクトが行われました。このプロジェクトでは、プロトコルの脆弱性に関するファジングを行うもので、多くの脆弱性を発見することに成功しました。PROTOSプロジェクトは、2002年にCodenomiconという商用のファジングに関する会社の設立まで行く様になりました。Codenomicon社は、OpenSSLに含まれていた脆弱性であるHeartbleedを検出するなど、多くの活躍をしています。

Codenomicon社が設立された2002年、Dave AitelがSPIKEという、オープンソースでプロトコルのファジングを行うことができるツールを開発・公表しました。SPIKEでは、ブロックサイズ情報を記録しておくことで、多くのヘッダがネストされるネットワークのようなシステムに対しても、ファジングを行うことができる様になっています。またDave Aitelは、sharefuzzという環境変数に対するファジングも公表しました。初期にはプログラムの入力のみ対象にしていたファジングが、ネットワークやプロトコル、環境変数など、だんだん範囲が広がって行く様になりました。

その後、ファイルやブラウザなど、だんだんと対象とする範囲が広がっていきながら、多くのファジングが登場する様になっていきます。

ファジングの分類

ファジングでは、主に3つの視点での分類が存在します。

  1. 入力をどの様に生成するか
  2. プログラムに入力する際の構造を認識しているか
  3. プログラム自体の構造を認識しているか

以降、それぞれの視点での説明を行っていきます。

入力の生成方法

入力の生成方法では、主に以下の2つが存在します。

  • 突然変異ベース: 入力の元となるようなデータであるシードを突然変異させて行くことで、その突然変異したものを入力データとして利用する方法(ex: シード"hello" →突然変異→ "hellm")。この方法の場合、シードの中身にあるデータによって、脆弱性の発見率が左右する場合があります。
  • 生成ベース: 何も情報がない状態か、入力のモデル(最初の2バイトは数字、続く4バイトは文字列…といった情報が続いたもの)がある状態から入力データを生成する方法。この方法の場合、突然変異ベースのシードを必要としないので、脆弱性の発見率を左右するようなものはありません。

また場合によっては、突然変異ベースと生成ベースを組み合わせた手法も存在します。

プログラムに入力する構造の認識

プログラムに入力する構造の認識の有無によって、以下の2つに分かれます。

  • smart fuzzer(スマートファザー): 入力のモデル(最初の2バイトは数字、続く4バイトは文字列…といった情報が続いたもの)を使用しながらファジングを行う手法。ヘッダが多く使用されるネットワークプロトコルなどに対しては有効な手法ですが、プログラムごとに入力モデルを用意する必要があり、コストがかかります。
  • dumb fuzzer(ダムファザー?): 入力モデルを使用せずにファジングを行う手法。入力モデルがない分、有効となる入力を生成できる可能性は低くなりますが、汎用的にファジングを行うことができます。

プログラム自体の構造の認識

プログラム自体の構造の認識では、主に以下の3つが存在します。

  • ホワイトボックス: プログラムの内部構造を知っている状態で行うファジング。到達しにくい場所にある脆弱性を発見することもできますが、プログラムの分析自体に時間がかかる可能性が高いです。
  • グレーボックス: プログラムの内部構造は不明だが、プログラムの動作などを監視して情報を収集しながら行うファジング。ホワイトボックスと違って内部構造はわかりませんが、プログラムの動作を介して、ある程度プログラムにあった入力を生成することができます。
  • ブラックボックス: プログラムの内部構造を全く知らない状態で行うファジング。グレーボックスと違って情報収集も行わないので、完全にランダムな入力データの生成を行いますが、並列化や高速化が可能です。

様々なファジング

近年、様々なファジングが提案・発表されています。ここでは、その一部について見ていこうと思います。

オープンソース・製品

オープンソースや製品化されているファザーは多く存在しますが、4つのファザーについて話したいと思います。

Taof

Windows上で動作する、HTTPサーバやFTPサーバといったネットワークを介するファジングを行います。クライアントとサーバの間に立ってデータ収集を行うことで、情報を収集します。

Peach

ソフトウェア全般に対してファジングを行うことができます。XMLファイルを用いて、ファジングの対象となる値の形式などを決めることで入力モデルを作成し、そのモデルに沿った値を生成していきます。こうすることで、ヘッダのような、予め形式の決まっているプログラムに対してのファジングを行うことが可能となっています。

AFL(American Fuzzy Lop)

ファジングを行うプログラムのコンパイル時に計測用のコードを埋め込み、ファジングの実行時には、埋め込んだ計測用コードによって情報を収集します。計測用コードでは、「どの計測用コードからどの計測用コードへ移動したか」を見ることで、新しい遷移があったかを検出します。(ex: これまではA→Bの遷移しかなかったが、新しく生成した入力ではA→Cへ遷移した)

AFLの簡単な動作説明は以下の通りです。

  1. シードとなる値を複数用意し、その中から1つ選択する。
  2. 選択したシードを突然変異させ、プログラムへの入力する。
  3. プログラム実行後、新しい場所へ遷移した入力などがあれば、その入力をシードに追加する。

libFuzzer

libFuzzerは、AFLと同様、遷移に関する情報を利用したカバレッジベースのファジングを行います。またAFLとの互換性もあり、例えばAFLである程度プログラムに対してファジングを行った後で、libFuzzerで同じプログラムのファジングを途中から行うことができます。

libFuzzerでは、通常のファジングだけでなく、特定の関数のみを対象としたファジングを行うことができます。この手法はメモリ内ファジング(In Memory Fuzzing)と呼ばれており、特定の関数をテストするには持ってつけの機能と言えます。

AFLの派生

AFLでは、AFLを利用した多くのファザーが存在します。ここでは、そのようなファザーについて話していきます。

ちなみに、AFLはC言語で記述されているのですが、様々な言語で使えるようになっているようです。例えば、KelinciはAFLをJavaで使えるようにしたもので、afl.rsはAFLをRustで使える様にしたものです。

AFLFast

AFLでは、1つのシードを選択すると、そのシードを元に突然変異を複数回実行します。またシードはキュー(FIFO)の構造になっているため、後ろの方に脆弱性を発見しやすいようなシードがあったとしても、選ばれるのはかなり先のことになってしまいます。

AFLFastでは、まずシードを選択してから突然変異を実行する回数を調整するようにしました。基本的にはAFLよりも突然変異回数を少なくなるにしており、6種類の実行回数の計算式が存在します。またシードの選択方法は、他のシードが遷移していない場所に遷移しているパスや、選択回数の少ないシードを優先的に選択するようにしました。

結果として、AFLFastは前期のDARPA CGCで決勝まで進出していることからも、この方法は有効だったと言えます。

AFLGo

AFLGoでは、現在地にとなる場所と目的地となる場所の距離を求めることで、目的地まで到達することを目標としたものです。関数の呼び出し関係を表すコールグラフや、プログラムの全経路をグラフ化した制御フローグラフなどを用いることで、距離の計算を行います。

aflpin

aflpinは、計測用コードを埋め込んでいない実行ファイルに対して、Intel Pinを利用することでAFLの様にファジングを実行しようというものです。ですが、近年ではaflpinがうまく動かないことが増えてきて、代わりにafl-pinを使用する必要が出てきました。

CollAFL

CollAFLは、AFLで収集する情報をより正確に提供し、シード選択時ポリシーを改良したファザーです。実は、AFLでは、対象となるプログラムによっては100%正確な遷移情報を収集することができません。この問題は、情報収集時にハッシュ衝突が発生するからです。

それに対して、CollAFLでは、貪欲法を用いることで、全てのハッシュが衝突しないようにしておきます。またシード選択については、AFLのキュー形式ではなく、メモリアクセス操作が多い入力などを優先して選択する様にしています。

他解析手法との組み合わせ

シンボリック実行やテイント解析など、他の解析手法と組み合わせたファザーが存在します。ここでは、それらを紹介していきます。なおシンボリック実行とテイント解析については、以下の通りです。

  • シンボリック実行: プログラムの変数や入力を一つのシンボルとして扱うことで、実行パスの制約を維持する手法です。シンボリック実行やコンコリック実行については、このスライドが凄く分かりやすかったです。なおコンコリック実行は、シンボリック実行で求めた制約を元に、実際に値を生成・入力する手法です。
    • 下の図のように、プログラムをパスとして考えてみましょう。右図の緑の部分にいきたいとします。その時、それぞれの緑の部分に行くために必要となる論理式は緑の部分に記述されています。この論理式通りの値を出力することができたら、全ての箇所に遷移することができます。
    • 注意点として、シンボリック実行やコンコリック実行では、時間がかかることはもちろん、条件式が多すぎるとパスが多くなりすぎるという問題もあります。

f:id:who3411:20181221193915p:plain
プログラムとパスの関係

  • テイント解析: パケットやファイル、標準入力といった外部から入力される値が格納されているメモリ番地を、「汚染された」状態とみなして、その伝搬を追跡する手法です。
    • 「汚染された」データと「汚染されていない」データを計算した時、計算結果も「汚染された」データとなっていきます。
    • 「汚染された」データ周りの命令が脆弱性に繋がりそうか確認すれば、入力データ周りの情報収集を行うことができます。

Driller

Drillerは、ファジングとコンコリック実行を交互に行うことで、深い位置にある脆弱性を発見するためのファザーです。具体的な手順は以下の通りになっています。

  1. テストケースを入力
  2. ファジングを実施し、新たな遷移が不可能となった時に手順3へ
  3. 不可能となった区間に対してコンコリック実行を実施
  4. 手順3の実行結果から得られた値をファジングの入力へ
  5. 手順2から手順4を繰り返す

BuzzFuzz

BuzzFuzzは、動的テイント解析を使用したファザーです。初期準備として、シードの値を入力としてプログラムを実行し、その際に動的テイント解析を利用することで、影響を与える入力バイトを記録します。そして、この時に得た入力バイトの位置を記憶しておくことで、ファジングによって変化させる値の位置を決定します。

VUzzer

VUzzerは、静的解析と動的解析を行うことで、効率的に入力データを生成するファザーです。具体的な手順は以下の通りです。

  1. 実行ファイルを静的解析する。
    • アセンブリの"cmp"命令や"lea"命令に当たる部分を調査する。
  2. これまで得た情報を元に入力を生成し、実行ファイルを実行する。
  3. 手順2の実行時に得られた情報を元に、次に実施する変異戦略などを求めるための計算を行う。
  4. 手順2に戻る

Munch

Munchは、ファジングとシンボリック実行を組み合わせたファザーです。ファジング→シンボリック実行の順に実行するFSモードと、シンボリック実行→ファジングの順に実行するSFモードの2つが存在します。

fFuzz

fFuzzは、ファジングとシンボリック実行を組み合わせたファザーです。fFuzzでは、以下の2つの最適化手法を用いることで、脆弱性の発見を最適化します。

  1. 冗長なテストケースの破棄
  2. パス爆発の発生を抑える選択的シンボリック実行エンジン

QSYM

QSYMは、ファジングと組み合わせることを前提として、コンコリック実行のパフォーマンスのボトルネックとなる部分を分析し、ファジングのサポートに適したコンコリック実行の作成を行っています。具体的には、命令レベルでシンボリック実行を行ったり、繰り返し実行しているブロックを検出して、その部分をコンコリック実行の対象から取り除いたりします。

その他の手法

ファジングでは、上であげた以外にも、様々な種類が存在します。ここでは、その他の手法を記載していきます。

kAFL

kAFLは、カーネルのファジングを可能としたファザーです(AFLの派生なのですが、カーネル関係として記述しています)。KVM上でファジングを行う対象となるカーネルを起動させて、QEMU上でファジングを実行します。入力した動作をトレースする方法として、Intel PTを使用しています。

正しく理解するには必要となる知識が多いのですが、今回は省略しています。わからない専門用語などがある方は「カーネルもファジングできるんだ〜」くらいに思っておいてもらえば幸いです。「カーネルって何？」という人がいれば調べてみましょう。

SlowFuzz

SlowFuzzは、脆弱性といったものを見つけるのではなく、実行速度が低下するような入力を見つけ出すファジングです。実行速度を遅くするため、シードを選択する際の方法としても、実行速度の遅くなるようんあものを優先的に追加するようにしています。SlowFuzzについては、先日あげた記事(「はじめに」と同じ記事です)で、AFLとIntel Pinを組み合わせた実装を行いましたので、よろしければそちらもご覧いただけると、より理解が深まるかと思います。

SemFuzz

SemFuzzは、gitログやCVEといった脆弱性に関係した情報を収集することで、攻撃用の入力を自動的に生成するファザーです。具体的な手順は以下の通りです。

  1. CVEとgitログを、自然言語処理を使って分析し、影響のあるバージョン、脆弱性の種類・機能、重要な変数、システムコールなどを抽出します。
  2. 対象のバージョンとなる仮想マシンを起動し、ファジング環境を準備します。
  3. 手順1で抽出した情報を利用して、シード入力を生成してファジングを実行します。

SSFuzzer

SSFuzzerは、AFLのような遷移情報や、Vuzzerのような比較命令に焦点を当てた方法とは異なり、関数呼び出しやメモリアクセスなどといった情報を利用することでファジングを行います。情報収集の際、プログラムをデコンパイルすることで、どのような関数が呼び出されているか、などを判定します。CVEの多い関数呼び出しを行っているもの、メモリアクセスの頻度が多いものなどは点数を大きくして、エラーハンドリングが行われているものは点数を小さくします。

Skyfire

Skyfireは、XMLファイルのような高度な構造化が必要とされるファイルを入力とするプログラムに対して、効率的なシードを生成する手法です。ファジングそのものではないのですが、入力生成まで行っていること、最終的にSkyfireとAFLを組み合わせた実験などを行っていることなどから、この場で紹介します。この手法では、確率文脈依存文法(PCSG)と呼ばれるものに学習を行わせて、学習した内容にしたがって入力を生成します。

ここでは、PCSGに代わって、ディープラーニングといった学習アルゴリズムを適用できる可能性をあげています。実際に機械学習を用いたファジングが出てきている現状では、Skyfireは改良できるかもしれません。

IOTFUZZER

IOTFUZZERは、IoTファームウェアのメモリ破損に関する脆弱性検出に特化したファジングです。モバイルアプリケーションでのやり取りを確認することで、ファジングを行います。IOTFUZZERの具体的な手順は以下の通りです。

  1. IoTのモバイルアプリケーションのうち、ネットワーク送信イベントをトリガします。
  2. 送信しているメッセージの中から、プログラム実行に関連する値を見つけ出します。
    • 実行ごとに変化している値などがあれば、その値をファジングによって変えることで脆弱性を発見できる可能性があります。
  3. 独自に定義したポリシーに従って手順2で見つけた値を突然変異させて、ファジングの対象とするデバイスに対して送信します。

FUZE

FUZEは、Use-After-Free(UAF)と呼ばれる脆弱性を評価するためのフレームワークで、内部的にファジングを使用しています。FUZEの実行途中において、UAFを引き起こすシステムコールを見つけ出す必要があるのですが、その時点でファジングが使用されます。

Angora

Angoraは、シンボリック実行を用いてパス制約を解決していた各手法に対して、シンボリック実行を用いずにパス制約を解決するものです。

関数呼び出しの引数を考慮(func(input[0])とfunc(input[1])を区別する)したり、条件文に使用される入力バイトを識別したりすることによって、ファジングとシンボリック実行を組み合わせる際の、シンボリック実行の代替となるようなシステムの開発を行っています。

T-Fuzz

T-Fuzzは、ファジングが調べることが難しい「str == ".PNG"」のような、いわゆるサニティチェックの条件文を取り除くことでファジングを行います。

実は、ファジングでは「str == ".PNG"」のような固定値との比較は非常に困難です。画像ファイルを処理するようなプログラムでは、画像のヘッダで使用されるマジックバイト(ファイルの先頭にある、その画像ファイルの種類を示す値)のチェック(サニティチェック)などが行われますが、ファジングはここを通るのが非常に難しいです。そこで、そのような部分は取り除いてしまおうというのが、T-Fuzzの考え方です。

ちなみにプログラムの取り除き方ですが、条件分岐を反転させることで取り除いています。

MoonShine

MoonShineは、プログラムからシステムコールのトレース結果を収集・抽出することで、プログラムにあったシードを自動的に生成する手法です。ファジングそのものではないのですが、ファジングに使用するシードは、ファジングの結果に大きく左右されるため、この場で紹介します。 MoonShineの主な手順は以下の通りです。

  1. トレースするプログラムを実行し、カバレッジ情報の記録やシステムコールのキャプチャを行う。
  2. 手順1で収集した情報からトレース結果を出力する。
  3. 手順2のトレース結果、および手順1のカバレッジ情報から、シードの蒸留を行います。
  4. 手順3で蒸留したシードをファジング実行時のシードとします。

Hawkeye

Hawkeyeは、AFLGoのような静的解析とファジングを組み合わせた手法について、望ましいと思われる特性を実現するための解決策を提案しています。

まず静的解析を用いてコールグラフと制御フローグラフを生成します。そこから、隣接する関数の距離、基本ブロック間の距離、目標位置に到達可能な関数などを計算します。

次にファジングを実施します。具体的な手順は以下の通りです。

  1. 静的解析で収集した情報やシードの優先順位に基づいて、突然変異するシードを選択します。
  2. シードの変異回数、変異戦略といったファジングを行うために必要な情報を決定したのち、突然変異を行います。
  3. 変異した値をプログラムの入力値として、目的のプログラムを実行します。
  4. 目標位置までとの距離などを計算し、シードの優先順位を決定します。
  5. 手順1に戻ります。

おわりに

まだまだ紹介したいものもあったのですが、残りは自分で調べてもらえると幸いです。(アドベントカレンダーの期限まで時間がなかった…)

今回は、詳しい中身を知らずとも、ある程度理解できる様に書いたつもりですが、わかりづらかったらすみません…。

ファジングは、海外では活発なイメージがあるのですが、なぜか日本ではあまり知られていないように思えます。私としては、もっと国内でファジングが流行ってくれたらなぁと思います。

12/21の本記事投稿時点で、次の記事は12/22のhi97_ia16さんによる記事です。お楽しみに！