一般的なループ終了パターンのカタログ化によるディープファジング

提案

一般に、自明でないプログラムを通る実行パスは、ファズテスターがそのすべてを実行するには多すぎる。ファザーがプログラムのエントリポイントから前方へたどる間に出会う分岐命令は、それぞれ左右に分かれる道の選択を迫り、脆弱性を探して調べなければならないパスの数を倍にする。倍化が繰り返されると、ファザーは完全なカバレッジに近づく前に必然的に資源を使い果たす。従来のファザーによるプログラム文のカバレッジの中央値はおよそ 20% である [WAN2020]。革新的な American Fuzzy Lop（AFL）グレーボックスファザーでさえ、改良条件/判定カバレッジは 15% にとどまる [RAN2022]。カバーされない領域に未発見の脆弱性が潜んでいることは疑いない。

我々は、潜在的な脆弱性からプログラムのエントリポイントへ後方にたどり、その潜在的な脆弱性に到達できる具体的なテスト入力の記号的な記述を得て、脆弱性を確認または否定するファジング手法を開発する近年のいくつかの取り組みを調査した [STE2016, KIM2019, ZHU2019]。この後方探索は、前方探索型のファザーが分岐点とみなす if-then-else 制御構造の分岐を、パスの数を倍にしない合流点に変えることで資源を節約する。しかし、ループを実装する分岐に対しては何の助けにもならない。後方探索型のファザーも、前方探索型のファザーと同様に、繰り返しによってすべての資源を消費しかねないループの終了条件を見つけ出さなければならない。我々は次の知見を示す。

1. ループの分岐を if-then-else の分岐と同じ手法で扱う現在のやり方は、よい結果をもたらす見込みが低い。ループに対する手法は、終了条件を認識し、それに焦点を当てなければならない。
2. 任意の一般的なループの終了条件を正しく特定できる自動解析という、実現不可能な理想に近づこうとする取り組み [RIC1953] は方向を誤っている。実世界のソフトウェアにおけるループの広範な実証研究を行えば、その大多数が、終了条件を実際に理解しカタログ化できる、扱える数の特定の一般的なループパターンのいずれかに一致することがおそらく判明するであろう。

我々は、不完全なカタログであっても、後方探索型のファザーが現在最良のファザーよりも多くのループを効率よく通過し、それによって、これまで発見されていない脆弱性が潜んでいる可能性の高い、プログラムの制御フローのより深い部分に到達できるようになるという仮説を立てる。

DARPA/I2O の Space/Time Analysis for Cybersecurity（STAC）プログラムにおける我々の先行研究は、広範な研究によって優れたファジングを可能にするのに十分な一般的ループパターンがカタログ化されるであろうという、ある程度の確信を我々に与えている。この研究では、ループの振る舞いを特徴付け、アルゴリズム計算量攻撃とサイドチャネル攻撃に対する脆弱性を特定するための、ヒューマン・イン・ザ・ループの新しいプログラム分析手法とツールを開発し実証した。我々はこれらの解析を用いて、STAC プログラムの 18 個のチャレンジアプリケーションと 4 つの人気のあるオープンソースライブラリから抽出した 5000 個のループについて、小規模ながら意義のある調査を行った。この調査により、調査したループの 78.4% をカバーする 14 個の一般的なループ終了パターンのカタログが得られた。下のヒストグラムに示すように、最も多いパターンが最も大きなカバレッジに寄与している [AWA2017]。

我々の解析手法は、高保証ソフトウェア（例えば Boeing 787）の検証を高速化する先行研究に基づく、ヒューマン・オン・ザ・ループの手法である。我々は、ソフトウェアの制御フローとデータフローを属性付きグラフとして捉えるグラフデータベースを構築し、一連のプログラム分析の結果でそのグラフに注釈を付ける。これにより、ユーザーは、一枚岩の解析器では不可能なほど高度なループパターンを構築し、可視化することができる。

ループ終了パターンのカタログによって効率を高めた後方探索型のファジング手法は、従来のファジング手法で発見できるよりも多くのソフトウェアの脆弱性と、プログラムのより深くに潜む脆弱性を、DoD が特定することを可能にしうる。我々は、費用が $500,000 を超えない 1 年間の取り組みとして、(1) Apache web サーバーのような人気のあるインターネットに面したソフトウェアにおけるループ終了パターンのより大規模な調査を行い、(2) これらのループ終了パターンのカタログを用いてループを効率よくたどる後方探索型ファザーを試作し、(3) 関心のあるプログラム地点に到達する入力を生成する実験的な試作品の能力を、AFL のような人気のある対照ファザーの能力と比較することで、我々の仮説を検証することを提案する。