文法を網羅するファジング
論文投稿が終わってしばらく頭を休めていた。毎度のことながら論文書くのはしんどい。他人の成果物のあら探しをするのは簡単だが、いざ自分でアウトプットすると成果物を作り上げる行為のしんどさを思い出す。どんなことであれ自分でアウトプットする気概のある人はリスペクトすべきだなぁ。
ってことで論文メモ。Grammar-based fuzzing について新しめの研究をメモる。
タイトル
Systematically Covering Input Structure
ASE2019
提案手法のツールのリポジトリ
概要
ファジング（fuzzing, fuzz testing）は、テスト対象のエラーを引き起こすような入力値を生成する技術である。ファジングの一種である Grammar-based fuzzing では、特定の文法にしたがって入力値を生成する。本研究では、その文法の生成規則を網羅する入力値の集合を生成する手法を提案する。
具体例があったほうが分かりやすいと思うので、論文の 7 章に載っている例を示す。ここでは、ある関数の入力値が以下の文法によって生成されるとする。OS とデータベースとサーバの種類の組み合わせが文字列によって指定される状況である。
このとき、1-path カバレッジを満たすために以下の3つの入力値が生成される。
"linux-mysql-apache""windows-mssql-apache""windows-mysql-iis"
これらの入力値によって、文法の生成規則に含まれるすべての非終端記号と終端記号が使用される。したがって「ある OS を使ったケースをテストできてない」みたいな悲しい事態が避けられることが保証される。
また、2-path カバレッジのもとでは、文法の生成規則の組み合わせを網羅するため、以下の入力値が追加で生成される。
"windows-mssql-iis"
これによって、データベースとサーバのすべての組み合わせが網羅された。こういう特定の組み合わせによって起こるエラーを検出できるわけである。
論文中では、k-path カバレッジとして一般化されていて、k 個の文法規則の組み合わせを網羅する手法が提案されている。適切な k を設定すると、その範囲において網羅性が担保されるのが手法の強みと言える。当然、k が大きくなるほど生成される入力値の数も増加するので、実用においては適切な k を設定してやる必要がある。
提案手法の入出力
手法の入力
- k: 網羅の基準。k-path カバレッジ（詳細は後述）が網羅される
- grammar: 入力値が従う文法
- depth limit: 生成する入力値の導出木の深さがなるべくこの値以下に収まるようになる
手法の出力
- 入力値（導出木）の集合
- 入力の grammar の k-path カバレッジ が網羅される
k-Path Coverage
研究の前提となるファジングや、Grammar-based fuzzing については論文参照のこと。ここでは、本研究の重要な k-path カバレッジの概念について説明する。
まず、grammar graph という考え方から述べる。このグラフは文法から構築されるものであり、ノードが文法の終端記号または非終端記号に対応し、エッジが各生成規則に対応する。
以下が論文中の grammar graph の例である。
そして、以下が k-path カバレッジの定義である。
Definition 3 (k-Path Coverage): A set of strings achieves k-path coverage if each k-path in the grammar graph occurs at least once in the set of their derivation trees.
文法によって生成された string の集合（つまり入力値の集合であり導出木の集合）が「k-path カバレッジを満たす」とは、grammar graph の k 個のノードからなるすべての経路が少なくとも一回は導出木の集合に含まれている状況である。
たとえば、k=1 のときはグラフ中のすべてのノードが、生成された導出木によって網羅されている状況である。また k=2 のときは、グラフ中のすべてのエッジが導出木によって網羅されている状況である。
本手法では、grammar と ｋ が与えられたとき k-path カバレッジを満たすような導出木（入力値）の集合を生成する。
提案手法：Coverage-Driven Generation
ここから提案手法の詳細を見てゆく。
論文中には明示的に書かれていない暗黙の前提を分かっておいたほうが理解しやすいと思うので先に述べておく。まず、導出木の根は文法の始記号（start symbol）でなければならない。また、導出木の葉は文法の終端記号でなければならない。つまり、導出木を構築するときは、文法の開始記号から徐々に木を展開してゆき、すべての葉が終端記号になるまで展開を続ける必要がある。木を展開する方法は一意ではないため、カバーしたい k-path を定めてもそれをカバーする方法は一意ではない。提案手法では、なるべく効率的に k-path カバレッジを網羅するのが特徴である。
提案手法を k=2 として具体例を用いて説明をする。完全なアルゴリズムは論文参照のこと。
まず、入力の grammar から grammar graph を構築する。たとえば、以下のグラフが構築されるとする。
このグラフからあらかじめすべての 2-paths を列挙しておく。導出木をひとつづつ生成しながら満たされた 2-paths を削除しつつ、すべての 2-paths がなくなるまで以下を繰り返す。
まず、適当な 2-path を選ぶ。たとえば、今回は以下の赤枠で囲った2つのノードをカバーするような導出木を作成したいとする。（図中の ~ や + といったノードはグラフの構築時に作成した仮想的なノードであり、元の文法の生成規則には存在していない。よって、k-path の長さには寄しないものとする。）
ここから具体的に導出木を構築してゆく。スタートは常に文法の開始記号である。ターゲットとなるパスを網羅するような最短経路を求め、それを導出木の一部とする。今回の場合だと以下の青枠で囲ったノードが導出木の一部となる。
しかしながら、この段階では導出木は完全ではない。というのも、導出木の葉が終端記号になっていないものがあるからである。たとえば、 の子である
や
は非終端記号であり、具体的な構造として導出する必要がある。そこで、以下のように葉まで導出する経路として緑色の枠で囲った経路に沿って導出木を展開してゆく。
ここで、現在の導出木の深さが depth limit を超えている場合は最短経路で葉まで導出する。一方で、まだ depth limit に余裕がある場合は、なるべく多くの k-paths を網羅するため、これまで通っていない経路を優先的にたどって葉までの経路を導出する。いずれにせよ、結果として完全な導出木が得られる。
1つの導出木を構築すると、当初狙っていた k-path 以外にも他の k-path がカバーされることがある。それらの k-path はこれからカバーする必要はないので、k-paths の集合から削除する。以上の流れをすべての k-paths がカバーされるまで繰り返す。
評価実験
提案手法を tribble と名付け、先行研究の Grammarinator との比較を行っている。結果として、よりカバレッジの高い入力値が生成できたことと、より珍しい例外を発生させることが確認された。詳しくは論文参照。
Beyond Text Inputs
文法に基づく網羅的な入力値生成は様々なドメインに適用できることが述べられている。たとえば、設定値を生成するのに grammar を定義すれば、その設定値の組み合わせを網羅するような入力値生成として応用できる。また GUI の操作も同様。この部分の話は一般的な Grammar-based Fuzzing に当てはまるので提案固有の強みではないのでは？
所感
- アルゴリズムの説明が1ページくらいに収まっている通り手法そのものはかなり素朴。一方で汎用性は高そう。この論文を査読することを考えると、incremental work であるものの、こういう手法がいまだ世の中にないのであればこれを publish する価値はあると考えたい。それゆえ論文として質が高かったら落としにくい。
- 1 章では、文法の構造によっては既存手法で効率的に入力値を生成できないことが述べられている。これに対して、入力値生成に向くように文法自体を書き換えるアプローチもあると思った。つまり、文法を工夫すれば既存手法でも上手くいく可能性が残っているように感じた。
