疑わしいプログラムセグメントの発見

4. 方法、仮定、手順

我々の新しいソリューションである RULER（Resource Usage vuLnerability identifiER）は、機械と人間の革新的な統合を切り開くものであり、これにより、高度な STRU 脆弱性を正確に検出しながら、大規模なソフトウェアにスケールする。RULER は、Atlas プラットフォーム上に Eclipse プラグインの集合として構築されている。RULER は先に述べた分析指針を取り入れ、次の分類にわたる、プログラム分析に固有の課題に取り組むためのツールと手段の集合を備える。

1. AC/SC 脆弱性のためのループのモデル化
2. 実行パスに依存する解析
3. 組み合わせ可能で、精度の境界を考慮した解析
4. 対話型でプログラム可能な what-if 推論
5. 脆弱性のメカニズムをモデル化するための高水準の抽象化。

4.1 アーキテクチャ図

RULER のシステムアーキテクチャを図 1 に示す。

4.2 疑わしいプログラムセグメントの発見

4.2.1 ループカタログ

RULER は、Wei ら [5] による Decompiled Loop Identification アルゴリズムを用いて、与えられた Jimple コード内のループを検出でき、ループカタログは各ループの特性を表にまとめる。RULER は、65 の属性からなるループの要約を計算する。その属性には次のものが含まれる。

• ソースとの対応
• ループの単調性
• ループの反復回数の上限
• 到達可能性
• 他のループ、分岐、ラムダループとの包含関係
• サブシステムとの相互作用
• コールサイト（Java Development Kit（JDK）のものと JDK 以外のもの）に関するパスの要約

図 2 に、ループカタログビューのスクリーンショットを示す。各列は 1 つの特性に対応し、各行はアプリケーション内の 1 つのループヘッダーに対応する。

ループカタログの使用を開始するには、ビューの「Load loops」セクションで「All」をクリックする。

分析者は、列の見出しをクリックして、そのループの特性に関してループ（行）を並べ替えることができる。分析者はループの一部を選択でき、その選択によって Atlas グラフ内の対応するループヘッダーも選択され、Smart Views を駆動するのに使える。特定のサブシステムとの相互作用を表す列のセルを選択すると、「Subsystem Interaction」と「Subsystem Interaction PCG」の Smart Views の焦点がそのサブシステムに切り替わる。

ループの選択は、ビューの内容を制御するのにも使える。選択したループは保持することも、（ソフト）削除することもでき、選択を反転することもできる。分析者は、選択したループにタグを付けることも、特定のタグを持つループを読み込むこともできる。「All」をクリックすると、すべてのループが再び読み込まれる。これは、カタログ内のループを他の解析や Smart Views と組み合わせやすくするために重要である。

4.2.2 分岐カタログ

RULER は、与えられたアプリ内の分岐を特徴付ける機能を備えている。これらの特性には、分岐の位置（プロジェクト、メソッドなど）、その分岐を含むループやその分岐が支配するループ、その分岐が終了条件であるかどうか、その分岐が支配するさまざまなサブシステムへのコールサイトに関する情報が含まれる。計算された分岐の特性はすべて、eXtensible Common Software Graph（XCSG）のタグと属性として Atlas グラフに保存される。

分岐カタログビューは、分析者がアプリ内の分岐を閲覧し、絞り込むためのグラフィカルなインターフェースを提供する。ループカタログビューと同様に、分岐カタログビューでは、分析者はすべての分岐、または指定したタグ名を持つ分岐を読み込める。各行は 1 つの分岐に対応し、分析者は列の見出しをクリックして、その特性に関して行を並べ替えることができる。各列は 1 つの特性に対応し、全部で 44 の特性が提供される。

表内の分岐を選択すると、Atlas グラフ内のその分岐も選択され、Smart Views がそれに応答する。特定のサブシステムとの相互作用を表す列のセルを選択すると、「Subsystem Interaction」と「Subsystem Interaction PCG」の Smart Views の焦点がそのサブシステムに切り替わる。分析者は、分岐の一部を選択してビューの内容を管理でき、その選択をビューに保持することも、ビューから削除することも、選択を反転することもできる。

図 3 に、分岐カタログビューのスクリーンショットを示す。

4.2.3 型とコールサイトのカタログ

型とコールサイトのカタログにより、分析者は型を検索し、閲覧し、絞り込み、選択できる。アプリ、JDK、またはアプリが使用するその他のライブラリ内の参照とコールサイトも同様である。ループカタログビューや分岐カタログビューと同様に、分析者は列の見出しをクリックして、型、参照、またはコールサイトのその特性に関して行を並べ替えることができる。型は、型名、タグ名、またはコレクションの型階層における Java のルート型（Iterable や Map など）を拡張しているかどうかを指定して選択できる。分析者は、選択したコレクションの型、参照、コールサイト（さらに必要に応じて、それらを含むループやそれらを支配する分岐）を、ユーザーインターフェースから表示したり、タグ付けしたりできる。これにより、その結果をシェルクエリ、Smart Views、サブシステムの相互作用ビューと組み合わせられる。このビューにより、分析者はアプリ内のコレクション、選択した型の参照から到達可能なループ、関連するコールサイトをすばやく見つけられるため、成果物を絞り込むのに役立つ。図 4 に、型とコールサイトのカタログビューのスクリーンショットを示す。

4.2.4 ラムダループのカタログ

Java 8 は Java に関数型プログラミングの概念を導入し、言語にラムダ式を追加した。ラムダ式はループを形成するのに使える。これは暗黙のループであり、たとえば java.util.stream.Collector.filter() のようなコールサイトによって作られるループである。RULER は、ラムダループと呼ぶこのようなループを検出できる。ラムダループカタログは、各ラムダループの特性を表にまとめる。全部で 15 のラムダループの特性を一覧にし、それには次のものが含まれる。

• ソースとの対応
• ループを形成する API
• 到達可能性
• ループや分岐との包含関係

各列は 1 つの特性に対応し、各行はアプリケーション内の 1 つのラムダ式に対応する。図 5 に、ラムダループカタログのスクリーンショットを示す。ラムダループカタログの使用を開始するには、ビューの「Load lambda loops」セクションで「All」をクリックする。

分析者は、列の見出しをクリックして、そのラムダループの特性に関してラムダループ（行）を並べ替えることができる。分析者はラムダループの一部を選択でき¹、その選択によって Atlas グラフ内の対応するラムダ式のノードも選択され、Smart Views を駆動するのに使える。特定のサブシステムとの相互作用を表す列のセルを選択すると、「Subsystem Interaction」と「Subsystem Interaction PCG」の Smart Views の焦点がそのサブシステムに切り替わる。

¹ 複数選択は macOS と Windows 10 で利用できる

ラムダループの選択は、ビューの内容を制御するのにも使える。選択したラムダループは保持することも、（ソフト）削除することもでき、選択を反転することもできる。分析者は、選択したラムダループにタグを付けることも、特定のタグを持つラムダループを読み込むこともできる。「All」をクリックすると、すべてのラムダループが再び読み込まれる。これは、カタログ内のラムダループを他の解析や Smart Views と組み合わせやすくするために重要である。

4.2.3 ループコールグラフ

ループコールグラフ（LCG）は、コールグラフの誘導部分グラフであり、ループを含むメソッドとそれらの間のコールグラフだけを残したものである。LCG は、手続き間のネストを理解するために、ループ内のコールサイトに関する知識を取り入れる。

4.2.4 射影制御グラフ

可能な実行パスの数は非常に多くなりうるが、関心のある基準に照らしたそれらのパスに沿った異なる振る舞いの数は、はるかに少ないことがある。射影制御グラフ（PCG）は、制御フローグラフ（CFG）から導かれる簡潔なグラフであり、CFG のパスは AC 脆弱性と SC 脆弱性に関連する振る舞いに基づいて同値類にまとめられる。

PCG のパスの集合は、CFG のパスの同値類と 1 対 1 に対応する。PCG は STAC に固有のイベントに関して計算され、そのイベントには (1) DLI アルゴリズム [5] で検出されたループヘッダー、(2) ループを含む関数への呼び出しチェーンを持つコールサイト、(3) ループ制御変数を変更する文が含まれうる。直感的には、PCG は、イベントノードと、グラフ内の到達可能性を反映するために必要な箇所に新たに追加したエッジによって誘導される部分グラフである。Tamrawi ら [6] は、PCG の形式的な定義を与え、PCG を構築する効率的なアルゴリズムを示している。

PCG に関する詳細とドキュメントは、次のサイトで参照できる：https://ensoftcorp.github.io/pcg-toolbox。

4.2.5 ループ終了依存グラフ

ループ終了依存グラフ（LTD）は、与えられたループの終了条件のデータフロー依存関係を示す。入力としてループヘッダーと印付けされた制御フローノードを受け取り、そのループの終了依存グラフ（TDG）を出力する。最初は、グラフのルートだけが表示される。

4.2.6 テイント解析

RULER は、アプリケーション全体を対象とするテイントを計算する。これは下流の自動化で使われ、外部から制御される入力が到達しうるプログラムの特徴に注意を向けさせる。ただし、RULER が入力を外部から制御されるとみなすかどうかにかかわらず、アプリケーション内の任意の場所のデータ依存を対話的に追跡するのにも使える。テイントは Atlas のデータフローに基づいており、推移的な操作を改善し、より簡潔なデータ依存グラフを提供するための修正がいくつか加えられている。

RULER は、主に既存のデータフローエッジにタグを追加することによって、さらにコールサイトのエッジにもタグを追加することによって、XCSG グラフにテイントを追加する。この変換により、ライブラリメソッドの呼び出しはデータフローにおける演算子ノードのような形になる。下の図 6 では、呼び出されるメソッドは Apache commons ライブラリの CommandLineParser.parse() である。XCSG は通常、図中のすべてのエッジを使ってコールサイトを表すが、破線はデータフロー（XCSG.DataFlow_Edge）であるのに対し、実線はコールサイトに渡されるパラメータを表すことに注意されたい。テイントのエッジは緑で示されている。データフローだけを使うと、フローはパラメータから呼び出されるメソッドの本体へ渡り、戻り値は呼び出し元のコールサイトへ戻る。テイントのオーバーレイを提供することで、RULER は、入力引数からメソッドの戻り値へ直接流れるコールサイトのビューを提供できる。

図 7 は、File オブジェクトから main メソッドの String 引数へさかのぼる、テイントグラフの一部を示している。この File オブジェクトは、パスワードの鍵ファイルを表す。テイントグラフを AST のように読むと、ファイル名が -w オプションで制御されていることがわかる。補足：テイントの実装は、コンストラクタの引数が新しいオブジェクトを「テイント」することを保証する副作用として、サイクルを作る。

4.2.7 サブシステムのタグ付け

我々は、JDK の Application Programming Interface（API）を機能別の分類に分けた。これを JDK のサブシステムと呼ぶ。サブシステムのタグ付けの枠組みは、将来の新しいサブシステムの追加に対応している。このタグ付けは、メソッドやループと JDK 内の特定の API 群との相互作用を調べるのに役立つ。既定では、RULER は入出力（IO）サブシステムとの相互作用を計算するように構成されている。

サブシステムの名前と、各サブシステムに API が含まれる主なパッケージ/クラスを表 1 にまとめる。

サブシステムの階層のグラフを図 8 に示す。このグラフのエッジは包含関係を表す。たとえば、SPLITERATOR_SUBSYSTEM から ITERATOR_SUBSYSTEM へのエッジは、SPLITERATOR_SUBSYTEM が ITERATOR_SUBSYSTEM に含まれることを意味する。