ファジングと統計学

はじめに

本稿ではファジングのシードスケジューリング問題に対する統計学的なアプローチについてまとめる。統計学、強化学習の基礎、特に二項分布と標本検定および多腕バンディット問題については既知とする。
ファジングとはソフトウェアのバグ(特に脆弱性)を発見するためのソフトウェアテストの一種で、テスト対象のプログラムに多種多様な入力を与えて実行し、何らかの不具合を生じさせた入力を記録していくテスト方式だ。勿論複数の入力が同一のバグ(root cause)を引き起こしている可能性もあるため、これらの記録された入力はファジング後のトリアージというプロセスでバグと1:1に対応する様にDeduplication(重複除去)され、データベースに記録される。この一連の流れをファジングキャンペーンという。

GoogleのOSS-Fuzzの例

ランダムテストとの最大の違いは、ファジングはプログラムを実行した際の状態の変化を観測(Observation)し次回の入力生成のヒントとしてフィードバックする事だ。プログラム実行に際してどの程度の情報まで観測するかによってファジングは以下の3種類に分類される。

Blackbox Fuzzing	プログラムの終了ステータスのみ観測する
Whitebox Fuzzing	プログラムの意味論まで観測する
Greybox Fuzzing	プログラムの部分的な情報を観測する

Whitebox Fuzzingはある入力に対してプログラムを実行した際、実行されたコードフロー上の全てのロジックを記録し、他の新たなフローを生成するための条件をSMTソルバで導く事で次の入力を生成する。いわゆるSymbolic Executionがこれに分類される。
Greybox Fuzzingの部分的な情報というのはかなり曖昧な定義だが、多くはプログラムを実行した際のカバレッジ情報が使用される。これを特にCoverage based (Greybox) Fuzzingと呼ぶ。
例えばAFLはある入力を実行した際に通ったエッジカバレッジを観測し、今まで見たことの無いエッジを通るとその入力を優先的に保持するようになっている。

FCS(Fuzzing Configuration Schedule)

さてでは本題のシードスケジューリング問題について説明する。
VALENTIN J.M¹によれば、ファジングのアルゴリズムは概略すると以下のようになる。

本稿で扱うのは上記のループ内でシードスケジューリングを行っているSchedule()アルゴリズムである。ファジングにおけるシードとは入力ファイルの事を表すと思って差し支えない。ファザーはまずInitial Seedと呼ばれる初期のシードを元に次の入力を生成し、フィードバック情報を元にConfUpdate()でシードプールに追加する。ただしPEACHファザーのようにシードが具体的な値ではなく入力値生成のためのメタ情報を使用するGeneration based Fuzzingと呼ばれる手法も存在するため、シードをさらに一般化した"Fuzzing Configuraion"と呼ぶのが普通である。本稿ではシードスケジューリングもとい、より一般化した**Fuzzing Configuration Schedule (FCS)**について扱う。

Grey/White box FCS

ファジングの目的は与えられた時間内により多くのバグを検出する事である。そのため、ある段階でどのシード(Configuration)を選択するかという問題は効率の良いファジングを設計する上で重要なファクターとなる。
シンプルな例としてAFLは生成したシードの中で最もプログラムの実行時間が短かった物を優先的に選択するようにしている。これは時間コストの低いシードを選ぶ事で、与えられた時間内により多くのシード生成を行おうという戦略だ。これに対してAFLFast ²はシードによって実行されたプログラムパスを記録し、より少ないプログラムパスを通ったシードを優先的に選ぶ。あるいはAFLGo ³のように特定のプログラムロケーションにたどり着きやすいシードを優先する戦略やstatic analysisと組み合わせる物 ⁴、White box Fuzzingへの応用 ⁵等様々な研究がある。

統計学的アプローチによるBlack box FCS

上記のGrey/White box FCSではカバレッジやプログラムパスといったフィードバックを使用していたがBlack Box Fuzzerの場合はどうだろうか？ 初めに説明したとおりBlack Box Fuzzingはプログラムの終了ステータスしか観測しないため、得られるフィードバック情報は非常に少ない。
そこで、CMUのCERTチームはBFFというBlack Box Fuzzerを開発し、選択された各シードに対してそのシードから一定数の入力を生成、その中に含まれるバグを引き当てた入力の割合**(#bugs/#runs)が大きいシードを優先的に選択するようなアルゴリズムを提案した。⁶
厳密に言えばファジングのあるシードに対するミューテションとは、確率pでバグを引き当てるシードから一定数の入力を生成するベルヌーイ試行**とみなす事ができ、この際の二項分布はポアソン分布に近似出来る(確率pが非常に小さいため)。
実際に私がCERT BFFを使って二項分布をダンプさせた際に開発したパッチを下に載せる。

diff --git a/bff-2.8/batch.sh b/bff-2.8/batch.sh
index a7fb5ef22a..6c0af417df 100755
--- a/bff-2.8/batch.sh
+++ b/bff-2.8/batch.sh
@@ -66,7 +66,8 @@ contains() {
 scriptlocation=`echo "$(cd "$(dirname "$0")"; pwd)/"`
 echo Script location: $scriptlocation/bff.py
 platform=`uname -a`
-PINURL=https://software.intel.com/sites/landingpage/pintool/downloads/pin-3.0-76991-gcc-linux.tar.gz
+#PINURL=https://software.intel.com/sites/landingpage/pintool/downloads/pin-3.0-76991-gcc-linux.tar.gz
+PINURL=https://software.intel.com/sites/landingpage/pintool/downloads/pin-3.2-81205-gcc-linux.tar.gz
 if ( contains "$platform" "Darwin Kernel Version 11" ); then
     mypython="/Library/Frameworks/Python.framework/Versions/2.7/bin/python"
 else
diff --git a/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py b/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py
index 2fed07c3c3..47fd90477a 100644
--- a/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py
+++ b/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py
@@ -60,7 +60,8 @@ class BanditArmBase(object):
         self.successes = 0
         self.trials = 0
         self.probability = None
-
+        self.successratio = {}
+        
         # initialize probability
         self.update()
 
@@ -79,6 +80,7 @@ class BanditArmBase(object):
         '''
         self.successes += successes
         self.trials += trials
+        self.successratio[successes] = self.successratio.get(successes, 0) + trials
         self._update_p(successes, trials)
         if self.probability is None:
             logger.debug("MAB arm: %s", self)
@@ -86,7 +88,13 @@ class BanditArmBase(object):
         elif not (0.0 <= self.probability <= 1.0):
             logger.debug("MAB arm: %s", self)
             raise BanditArmError('probability must be between 0.0 <= {:f} <= 1.0'.format(self.probability))
-
+        if self.trials <= 0:
+            return
+        with open(str(id(self)) + ".dat", "w") as fp:
+            fp.write("# {} trials\n".format(self.trials))
+            for s in list(range(self.successes + 1)):
+                if s in self.successratio:
+                    fp.write("{} {}\n".format(s, float(self.successratio[s]) / float(self.trials)))
     def _update_p(self, *_unused_args):
         '''
         Internal method, ensure that self.probability gets assigned
diff --git a/bff-2.8/configs/bff.yaml b/bff-2.8/configs/bff.yaml
index 79d4d074a8..15197c559d 100644
--- a/bff-2.8/configs/bff.yaml
+++ b/bff-2.8/configs/bff.yaml
@@ -11,7 +11,7 @@
 #
 ##############################################################################
 campaign:
-    id: convert v5.2.0
+    id: LAVA-M v5.2.0
 
 
 ##############################################################################
@@ -31,8 +31,8 @@ campaign:
 #
 ##############################################################################
 target:
-    program: ~/convert
-    cmdline_template: $PROGRAM $SEEDFILE /dev/null
+    program: ~/who-lava
+    cmdline_template: $PROGRAM $SEEDFILE
 
 
 ##############################################################################
@@ -53,7 +53,7 @@ target:
 ##############################################################################
 
 directories:
-    seedfile_dir: seedfiles/examples
+    seedfile_dir: seedfiles/who
     working_dir: ~/fuzzing
     results_dir: results
 
diff --git a/bff-2.8/seedfiles/who/f1.utmp b/bff-2.8/seedfiles/who/f1.utmp
new file mode 100644
index 0000000000..b30aa294cf
Binary files /dev/null and b/bff-2.8/seedfiles/who/f1.utmp differ
diff --git a/bff-2.8/seedfiles/who/f2.utmp b/bff-2.8/seedfiles/who/f2.utmp
new file mode 100644
index 0000000000..201990c980
Binary files /dev/null and b/bff-2.8/seedfiles/who/f2.utmp differ
diff --git a/bff-2.8/seedfiles/who/f3.utmp b/bff-2.8/seedfiles/who/f3.utmp
new file mode 100644
index 0000000000..841846d9b8
Binary files /dev/null and b/bff-2.8/seedfiles/who/f3.utmp differ

patch

各シードに対して充分な数の入力生成(試行数)があれば(#bugs/#runs)をそのまま評価値として使用可能だが、あるシードから生成可能な全ての入力を試す事は不可能に近い。
そこで彼らは各シードに対しておおよそ500個程度の入力を生成しそこから標本検定として95%信頼区間の上限値UCB(Upper Confidence Bound)を評価値として使用している。このUCBが大きなシード程高確率で選択されるようにFCSを設計したわけだ。

ファジングにおける多腕バンディット問題

さて、前節で説明した標本推定によるBlack box FCSはいわゆるオンラインアルゴリズムであり、あるシードが一体いくつのバギーな入力を含んでいるかという正しい情報は不明な状態である。よって試行回数を増やせば増やすほどUCBの質も上がっていく。
ではシードプールに含まれるシードの内、一体どのシードの試行回数を増やすべきだろうか？ これはいわゆる探索(Exploration)と利用(Exploitation)のジレンマである。
各シードは前節で説明したUCBによって"バグの引当やすさ"という評価値が計算できる。ではある段階でこの評価値が最も高いシードをずっと試すべきだろうか？ あるいは他のシードを選んで試行回数を増やせば、より高い評価値が得られる物があるのではないか？
このジレンマに対しCERT BFFはϵ-greedyとEXP3を採用している。

重み付きクーポンコレクター問題とノーフリーランチ定理

しかし実は前節のCERT BFFによるFCSには問題がある。生成された入力がバギーであるか無いかの0/1でしか区別していない点だ。一番初めの節でも説明したとおり、基本的にファジングにおけるバギーな入力というのは複数の入力が同一のバグを踏んでいる可能性がある。例えばあるシードに対して下記のような入力が生成されたとしよう。

0, 0, 0, 1, 0, 1, 0, 0, 1, 1,

これは10個の試行回数で確率pのバギーな入力を4個生成したベルヌーイ試行だ。しかし実際にトリアージを行いバグ(root cause)ごとにラベル付けすると以下のようになる事がある。

0, 0, 0, 1, 0, 2, 0, 0, 2, 2,

実際にはラベル1と2の2種類のバグしか引いていなかったわけだ。しかしながらCERT BFFのFCSではこれも4個とカウントして標本検定を行ってしまう。
Maverick Woo⁷はこの問題を指摘し、従来のベルヌーイ試行によるFCSでは正しい検定が行えていない事を示した。実際CERT BFFを用いたファジングキャンペーンでもEXP3の最小リグレット数を下回るようなバグ数が多く現れた。これは従来のシードの評価方法ではトリアージを通した後のバグ数とかけ離れてしまう事の一つの証拠となっている。
そこでより正確な統計モデルを使用したいが、どうしたものだろうか。先程の試行をもう一度載せる。

0, 0, 0, 1, 0, 2, 0, 0, 2, 2,

仮に他のシードから同じく10個の入力を生成した場合、今度は以下のようになったとしよう。

0, 0, 0, 1, 0, 2, 0, 0, 3, 4,

こちらのシードはどうやら4種類のバグを発見できたらしい。この場合直感的にも後者のシードを優先して選択すべきだろう。

つまりある試行回数の中で、N種類あるバグのうちより多くの種類のバグを引き当てるシードを優先したい。
これはまさにクーポンコレクター問題としてモデル化できるではないか。それぞれのバグの引き当てる確率は異なるため正確には重み付きクーポンコレクター問題 (WCCP)を使用する。
しかし残念な事にWCCPはクーポンの重みの分布が分かっていなければモデル化が出来ない。
つまりこれの意味する所は、あらゆるプログラムに対するBlack Box FCSを最適化する戦略はノーフリーランチの定理より存在しないという事だ。 Maverick Woo⁷はこれを示すと共に、折半案としてRule of Threeと呼ばれる手法の提案、さらに正しい最適なFCSの値を動的計画法を用いたオフラインアルゴリズムで求めるFuzzSimというシステムを開発した。少々マニアックなのでこれらの詳細については興味のある方は論文を見て欲しい。

ちなみにMaverick Woo先生は私のCMUでの指導教員である。

おわりに

さて今回はファジングに対する統計学的なアプローチの一つとしてBlack Box FCSを紹介した。他にも最初期のInitial Seedの選び方として統計モデルを用いた研究⁸もあるので興味がある方は。

Reference

1. VALENTIN J.M. MANÈS et al. Fuzzing: Art, Science, and Engineering 2019 ↩

2. Marcel Bohme et al. Coverage-based Greybox Fuzzing as Markov Chain [CCS 16] ↩

3. Marcel Böhme et al. Directed Greybox Fuzzing [CCS 17] ↩

4. Song Wang et al. QTEP: Quality-Aware Test Case Prioritization [ESEC/FSE 17] ↩

5. Sang Kil Cha et al. Program-Adaptive Mutational Fuzzing [IEE S&P 15] ↩

6. Allen D. Householder et al. Probability-Based Parameter Selection for Black-Box Fuzz Testing [CMU/SEI-2012-TN-019] ↩

7. Maverick Woo et al. Scheduling Black-box Mutational Fuzzing [CCS 13] ↩ ↩²

8. Alexandre Rebert et al. Optimizing Seed Selection for Fuzzing [USENIX Sec 14] ↩