3.1.3 FlowMiner
正確でスケーラブルな部分プログラム解析のために、表現力があり簡潔な情報フローの要約を、ライブラリからどのようにマイニングできるか。
この問いに取り組む我々の研究は、ソフトウェアライブラリに依存するプログラムを分析するための技術的進歩につながった。
静的プログラム分析ツールはソフトウェア工学の分野にとって極めて重要であり、我々はそれによってコードをコンパイルし、リファクタリングし、検証し、理解できる。最近のソフトウェアは再利用可能なライブラリやフレームワークの上に構築されるため、プログラム全体の解析は法外に高コストである。そのため、ツールは代わりに部分プログラム解析、すなわちプログラムの実装の真部分集合の解析を行わなければならない。これらのコンポーネントのデータフローの意味論が欠けていると、セキュリティ上重要な解析を含む多くのユースケースに、問題となる隔たりが生じる。手書きのモデル、ヒューリスティック、動的に推論された仕様など、これを克服しようとするこれまでの試みは、多くの解析のユースケースにとって粗すぎ、不正確さをもたらす。
2014 年の追加のシード資金の支援を受けて、我々は、Java ライブラリのバイナリから表現力のあるデータフローの要約をマイニングし、完全かつ正確な部分プログラム解析を可能にするツール FlowMiner の開発を始めた。この研究は最近完了し、Tom Deering の博士研究の一部となっている。我々の知る限り、コンテキスト、型、フィールド、オブジェクト、フローを区別する形で使える、きめ細かい要約を作成したのは我々が初めてである。我々は簡潔さも重視している。正確な利用にとって重要ではないフローの詳細は、正確さにとって重要な要素の間の単純なエッジに省略される。その結果、FlowMiner が抽出する要約は、サイズが元のライブラリより 1 桁小さい。我々の手法の主な特徴は次のとおりである。(i) Java ライブラリから、きめ細かい要約のデータフローの意味論を抽出する新しいアルゴリズム、(ii) 元のライブラリに対する要約の簡潔さ、(iii) 要約を格納する数学的抽象として多重属性付き有向グラフを用いる、グラフによる要約のパラダイム、(iv) 既存の解析ツールで使える移植可能な形式で要約を保存する、上記のオープンソース実装（FlowMiner）、(v) 最もよく使われている Java ライブラリのいくつかによる、我々の研究の検証。我々は、我々の要約の特性を、ほかの最先端のツールによる要約の特性と比較して論じる。また、我々の研究によって、既存の解析ツールが、Android アプリケーションにおいてこれまで扱われていなかったデータフローを正確に扱えるようになることも示す。
3.1.3.1 表現力と簡潔さの両立
ライブラリのデータフローの意味論を要約する際には、ライブラリ内の特定の重要な成果物が、そのデータフローにとって不可欠となる。たとえば、要約をフィールドを区別する形で使うのであれば、個々のフィールドの定義が存在しなければならず、ライブラリのコールバックを捉えるのであれば、個々のコールサイトを保持しなければならない。たとえば、我々は、フィールドの定義を保持しない場合、要約したフィールドのフローの 93.07% が偽陽性になることを実証的に示している。したがって、フィールド、メソッドのコールサイト、リテラル値、メソッドの形式パラメータと非形式パラメータ、そして戻り値は、いずれも要約のデータフローに保持しなければならない、フローの重要な成果物である。
一方で、代入の def-use 連鎖の一部のような重要でない特徴は、それらが関わるパスに価値を加えず、要約では抽象化して取り除ける。FlowMiner は、興味のないフローの詳細を省略し（パスを直接のエッジに置き換え）、データフローにとって不可欠な重要な成果物と、それらの間の到達可能性の情報を含む抽象データフローグラフを得る。このグラフは、元のプログラムグラフよりはるかに簡潔である。これにより、健全性を保ちながら、元のライブラリと比べて大幅な削減とスケーラビリティの向上を実現できる。言い換えれば、FlowMiner の要約に保持されるフローは、まさに実行時に実際に起こりうるフローである。
3.1.3.2 検証
我々は、よく使われているライブラリの要約が、元のプログラムよりはるかに小さいにもかかわらず、ほかの最先端の要約手法よりも表現力があり正確であることを示すことで、FlowMiner を検証した。我々の要約は、平均して、元のライブラリのプログラムグラフのノードの 26.89% とエッジの 16.32% しか含まないことがわかった。
3.1.3.3 オープンソース
我々は、我々のアルゴリズムのオープンソースのリファレンス実装である FlowMiner を提供している。FlowMiner は、ライブラリのソースコードまたはバイトコードから要約を抽出し、それを移植可能でツールに依存しない形式でエクスポートする。FlowMiner の研究は Tom Deering の博士論文でより詳しく述べられており、この研究に基づく論文が投稿される予定である。このツールは次のサイトで入手できる：http://powerofpi.github.io/FlowMiner/