Skip to content
This repository was archived by the owner on Mar 15, 2022. It is now read-only.

Latest commit

 

History

History
79 lines (45 loc) · 9.32 KB

algorithm_ja.md

File metadata and controls

79 lines (45 loc) · 9.32 KB

AFLFast

AFLFastとは

https://github.com/mboehme/aflfast

AFLFast1は、Michał Zalewskiによって開発されたAFLを拡張したファザーです。本稿で触れないAFLの基本的なアルゴリズムについてはAFL/algorithm_ja.mdを参照してください。 AFLFastを開発したMarcel Böhmeのチームは、AFLがあるシードから生成した入力のほとんどが同じパスを通り、興味深い挙動を示す他のパスはあまり通らないことを発見しました。これらの挙動を改善することによって、脆弱性に起因したバグを引き起こす入力をAFLのおよそ7倍高速に発見できるようになりました。AFLFastは、AFLの拡張として広く受け入れられており、AFLベースの研究のベースラインとして用いられていることからfuzzufでも実装されています。

CLI上での使用方法

fuzzufではAFLFastはAFLと同様に使えます。次のようにして実行します。

fuzzuf aflfast --in_dir=path/to/initial/seeds/ -- path/to/PUT @@

指定可能なグローバルなオプションはAFLと同様です。AFLのオプションについてはAFL/algorithm_ja.mdを参照してください。 なお、現時点ではAFLFast固有のローカルなオプションはなく、CLIでのスケジュールのオプションが未実装なため、CLIからはFASTのみが利用できます。

アルゴリズム概要

AFLにおける問題点は、入力生成の効率にありました。あるパス i を実行するシードからパス j を実行する入力が発見されるためには、シードから生成される入力の数（以降エネルギーと呼びます）が重要な要素となります。エネルギーが大きすぎる場合は、最も効果的な手法であっても効率が悪いことが知られており2、エネルギーが小さすぎる場合はそもそもパス j を実行する入力が発見できません。AFLでは、このエネルギーをシードのみから一意に決定できる式によって割り当てており、過不足が発生しています。

これに対し、AFLFastに実装されているFASTという手法はエネルギーを指数関数的に割り当てます。すなわち、あるシードが最初にファジングされたときはエネルギーが極めて低く、そのシードが選択されるたびにより多くのエネルギーが割り当てられ、生成される入力の数が増えていきます。このアルゴリズムによって、新しいパスを発見するのに必要なエネルギーをより効率的に発見することができるようになります。

パワースケジュールについて

AFLFastで使用可能な p(i) を計算するためのパワースケジュールは5種類あります。

EXPLOIT: exploitation-based constant schedule

AFLを含むほとんどのグレーボックスファザーでは、実行時間やカバレッジ、生成時間からスコア \alpha(i) を計算し、エネルギーにはこの値をそのまま用います。

p(i) = \alpha(i)

EXPLORE: exploration-based constant schedule

探索ベースのスケジュールはEXPLOITと同様に定数ですが、1以上の定数 \beta を用いて次の式で計算されます。

p(i) = \frac{\alpha(i)}{\beta}

これは計算された \alpha(i) を採用しつつ、かなり低いエネルギーを割り当てます。

COE: Cut-Off Explonential

カットオフ指数は高頻度のパスがファジングされるのを防ぎ、低頻度のパスになるまでファジングしないためのスケジュールです。 頻度の閾値 \mu は発見されたパスの集合 S^{+} と i を通る入力の数 f(i) を用いて、次の式によって定義されます。

\mu = \frac{\sum_{i \in S^{+}} f(i)}{|S^{+}|}

f(i) が \mu より大きい場合は、他のシードをファジングしてもなお多くファジングされるとみなせるため優先度が低く設定され、再度 \mu を下回るまで p(i) が 0 に設定され、ファジングされません。

f(i) が \mu 以下の場合、p(i) は s(i) （t_i が選ばれた回数）と M （ファジングのイテレーションごとに生成される入力値の数の上限）を用いて、次の式によって計算されます。

p(i) = \textrm{min}\left(\frac{\alpha(i)}{\beta} \cdot 2^{s(i)}, M\right)

\frac{\alpha(i)}{\beta} = 1 におけるCOEスケジュールがクラッシュを見つけるまでの入力生成数は、AFLが256,000つだったのに対し4,000と、非常に効率的に入力を生成できることが実験的に判明しています。

FAST: exponential schedule

COEを拡張した指数スケジュールでは、 f(i) > \mu の場合にファジングしないのではなく、 f(i) に反比例した p(i) を設定します。

p(i) = \textrm{min}\left(\frac{\alpha(i)}{\beta} \cdot \frac{2^{s(i)}}{f(i)} , M\right)

f(i) を分母にすることで、ファジングされる頻度が少ないパスにいることが理由でファジングされなかったパスをファジングできるようになります。また指数的な増加をするので、ファジングされる頻度が少ないパスでも確実にファジングできるようになります。

LINEAR: linear schedule

線形スケジュールは以下の式で表され、 p(i) は指数的ではなく線形的に増加します。

p(i) = \textrm{min}\left(\frac{\alpha(i)}{\beta} \cdot \frac{s(i)}{f(i)}, M\right)

QUAD: quadratic schedule

二次スケジュールは以下の式で表され、 p(i) は二次関数的に増加します。

p(i) = \textrm{min}\left(\frac{\alpha(i)}{\beta} \cdot \frac{s(i)^2}{f(i)}, M\right)

参考文献

Footnotes

  1. Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage-based Greybox Fuzzing as Markov Chain. In Proceedings of the 23rd ACM Conference on Computer and Communications Security (CCS’16). ↩

  2. Marcel Bohme and Soumya Paul. 2015. A Probabilistic Analysis of the Efficiency of Automated Software Testing. In IEEE Transactions on Software Engineering (TSE'15). ↩