プログラム静的解析手法の効率化と 解析フレームワークの構築に関する研究 大阪大学 大学院基礎工学研究科 情報数理系専攻 ソフトウェア科学分野 大畑 文明

ソフトウェアの品質改善、開発作業の生産性向上の必要性 背景 ソフトウェアの大規模化による、開発作業の複雑化 高品質ソフトウェアを効率よく開発する要求の高まり ソフトウェアの品質改善、開発作業の生産性向上の必要性 プログラム解析: プログラムからその性質やふるまいを抽出し、それを開発者に提供することでソフトウェア開発を支援する技法

プログラム静的解析 プログラム静的解析: 対象プログラムの実行を必要としないプログラム解析技法で、一般に対象プログラムのソースコードに対して行われる プログラム静的解析により得られる解析情報(例) データフロー 制御フロー 抽象構文木 クラス階層 …

問題点 既存のプログラム解析手法は、 解析精度の向上 ある解析対象に特化した手法の提案及び実装 を重視してきた (a) 解析の効率 (b) 解析コストと解析精度のトレードオフ制御 (c) 解析情報の二次利用 への配慮が不足している 配慮が必要になった背景と、具体的な目標について述べる。

プログラミング言語の高級化、プログラムの大規模化 (a) 効率 プログラミング言語の高級化、プログラムの大規模化 解析コストの増大 目標 解析アルゴリズムの効率化 解析手順の効率化

求められるコストと精度のバランスは、目的によって様々 (b) トレードオフ制御 解析コストと解析精度はトレードオフ関係 解析コストを抑えると、解析精度が低下する 解析精度を向上させると、解析コストは増大する 求められるコストと精度のバランスは、目的によって様々 目標 トレードオフ制御を考慮した解析アルゴリズム

(c) 二次利用 二次利用を想定していない実装 目標 解析により得られた情報はメモリ上にのみ記憶される 別の解析での利用を考慮していたとしても、特定のプログラミング言語によるAPIを要求する 目標 二次利用を考慮し、その利用者への制約の少ない、解析情報データベース

目的 (a) 効率、(b) トレードオフ制御、(c) 二次利用 を考慮したプログラム静的解析手法及び、プログラム解析フレームワークの構築に関する研究を行った (a)に重点を置き、プログラムスライス計算、エイリアス解析、意味解析木構築の効率化手法をそれぞれ提案 (b)、(c)については、各効率化手法の中で議論 提案したプログラム解析手法に基づく、Javaを対象とするプログラム解析フレームワークの構築

論文の構成 第1章 . まえがき 第2章. プログラム依存グラフの節点集約による スライス計算の効率化 [1-1,1-3] 第1章 . まえがき 第2章. プログラム依存グラフの節点集約による スライス計算の効率化 [1-1,1-3] → プログラムスライス計算の効率化 … (a),(b)に配慮 第3章. エイリアス情報のモジュール化による エイリアス解析の効率化 [1-2] → エイリアス解析の効率化 … (a),(b)に配慮 第4章. XMLデータベースを利用した プログラム解析の効率化 [1-6] → 意味解析木構築の効率化 … (a),(c)に配慮 第5章. むすび

節点集約によるスライス計算の効率化 [論文の2章] プログラムスライス 節点集約 依存関係の局所性を利用した節点集約法 節点分解を伴う節点集約法 Pascalスライスシステム - Osaka Slicing System (OSS) - 評価 まとめ

プログラムスライス プログラムスライス: ある文のある変数(スライス基準)の値に影響を与える可能性のある文の集合 適用分野 プログラムデバッグ プログラム理解 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a; 5: d = b; } 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a; 5: d = b; } スライス基準<5, b>に対するスライス

PDGによるスライス計算 計算過程 … スライス計算のグラフ到達問題への置き換えによる Phase 1: 定義、参照変数の抽出 Phase 3: プログラム依存グラフ (PDG) の構築 節点: プログラム文 辺: プログラム文間の依存関係 Phase 4: PDGによるスライス抽出

PDGによるスライス計算(例) b = 5 d = b c = a if (a > 0) a = b + b b a b = 5 } 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a: 5: d = b; } b = 5 d = b c = a if (a > 0) a = b + b b = 5 d = b c = a if (a > 0) a = b + b b a 1: b = 5; 2: a = b + b; 3: if(a > 0) { 4: c = a; 5: d = b; }

Phase 2: 依存関係解析 が最も解析コストを要する 節点集約 Phase 2: 依存関係解析 が最も解析コストを要する 節点集約: 通常各文の依存情報は対応するPDG節点に保持させるが、複数文の依存情報を1つのPDG節点に保持させる PDGの節点数及び辺数の減少 (a) 効率 への配慮 解析アルゴリズムの効率化

集約の制御 節点集約アルゴリズムは、集約の程度を制御するためのパラメータ limit (limit  0) を持つ b = 5 a = b + b c = a d = b if (a > 0) a,b a 集約あり (limit = 1) b = 5 a = b + b d = b c = a if (a > 0) b a 集約あり (limit = 0) b = 5 d = b c = a if (a > 0) a = b + b b a 集約なし b = 5; a = b+b; if (a > 0) { c = a; d = b; } 集約あり (limit = ) 集約

集約の応用 (2つの節点集約法) 依存関係の局所性を利用した節点集約法 (limit « ) 精度低下の少ない、時間コスト及び空間コスト削減 節点分解を伴う節点集約法 (limit = ) 精度低下のない、時間コスト削減 節点分解が必要であるため、空間コストは増加 (b) トレードオフ制御 への配慮 トレードオフ制御を考慮した解析アルゴリズム

依存関係の局所性を利用した節点集約法 依存関係の局所性: 集約対象となる文集合が持つ、依存関係の類似性 b = 5 a = b + b 局所性が強い文同士の集約では、精度低下が少ない b = 5 a = b + b c = a d = b if (a > 0) a,b a 集約あり (limit = 1) b = 5 a = b + b d = b c = a if (a > 0) b a 集約あり (limit = 0) b = 5 d = b c = a if (a > 0) a = b + b b a 集約なし 集約

節点分解を伴う節点集約法 依存関係の分類とその抽出方針 b = 5 d = b c = a if (a > 0) a = b + b 手続き間 (繰り返し解析が必要): 集約後に抽出 手続き内 (繰り返し解析が不要): 分解後に抽出 b = 5 d = b c = a if (a > 0) a = b + b b a 集約なし c b = 5; a = b+b; if (a > 0) { c = a; d = b; } … … = a; … = c; 集約あり (limit = ) a c b = 5; a = b+b; if (a > 0) { c = a; d = b; } … … = a; … = c; 集約あり (limit = ) 可能な限りの集約を行い、手続き間をまたぐような依存関係の抽出コストを削減する。 集約節点内には手続き内で閉じた依存関係しか存在しないため、分解時に容易に抽出することができる。 分解

Pascalスライスシステム - Osaka Slicing System (OSS) - 開発 言語: C ツールキット: Tcl/Tk コード: 12,000行

評価 OSSに対してPascalプログラムを適用し、既存手法との比較を行った 既存手法: 節点集約を行わない 提案手法: 節点集約(及び節点分解)を行う プログラム[概要] 行 手続き P1 [チケット予約] 333 14 P2 [酒屋問題] 429 18 P3 [小計算問題の集合] 449 30 P4 [ソーティング] 831 22

考察 依存関係の局所性を利用した節点集約 節点分解を伴う節点集約 解析コスト(時間): 5～30%の削減 解析コスト(空間): 5～40%の削減 解析精度: 1～3%の低下 節点分解を伴う節点集約 解析コスト(時間): 15～60%の削減 解析コスト(空間): 約10%の増加 解析精度: 低下はなし

まとめ 節点集約によるスライス計算効率化手法の提案 OSSによる提案手法の実装、及びその評価 今後の課題 依存関係の局所性を利用した節点集約法 節点分解を伴う節点集約法 OSSによる提案手法の実装、及びその評価 (a) 効率、(b) トレードオフ制御 への配慮 今後の課題 ポインタ変数の存在するプログラムへの適用 大規模プログラムに対する評価実験

モジュール化によるエイリアス解析の効率化 [論文の3章] エイリアス AFGによるエイリアス解析 Javaエイリアス解析ツール - Java Alias Analysis Tool (JAAT) - 評価 まとめ

エイリアス エイリアス: ある文のある式(エイリアス基準)と同一メモリ領域を指す可能性のある式の集合 適用分野 コンパイラ最適化 スライス計算の前処理 プログラムデバッグ、プログラム理解 1: Integer a, b, c; 2: a = new Integer(1); 3: b = new Integer(2); 4: System.out.println(b); 5: c = a; 6: System.out.println(c); 1: Integer a, b, c; 2: a = new Integer(1); 3: b = new Integer(2); 4: System.out.println(b); 5: c = a; 6: System.out.println(c); エイリアス基準<6, c>に対するエイリアス

エイリアス解析手法における問題点 (1/2) エイリアス解析全般における問題点 スケーラビリティ: 実行順に従ってプログラム全体を解析しなければならないため、大規模プログラムへの適用におけるコストは膨大なものになる 利用分野に適した解析手法: プログラムデバッグ、プログラム理解に利用する場合、求めるエイリアスのみを即座に抽出できることが望まれる スケーラビリティに配慮するための、モジュール解析 エイリアスを効率よく抽出するための、オンデマンド解析 の重要性

エイリアス解析手法における問題点 (2/2) OOプログラムに対するエイリアス解析における問題点 インスタンスを区別した解析: 同一クラスのインスタンスが属性に関するエイリアス情報を共有する方式では、解析精度が低くなる しかし、単純にインスタンスの数だけエイリアス情報を生成してしまうと多大な空間コストが必要になるため、インスタンスを区別した解析は実現されてない エイリアスを効率よく抽出するための、オンデマンド解析 の重要性

AFGによるエイリアス解析 (方針) 方針: 2フェーズ方式 Phase 1: メソッド内エイリアス解析 (モジュール解析) メソッド単位に解析結果が保持される インスタンス共通のエイリアス情報 の抽出 Phase 2: メソッド間エイリアス解析 (オンデマンド解析) メソッド単位の解析結果を結びつける インスタンス独自のエイリアス情報 の抽出 (a) 効率 への配慮 解析アルゴリズムの効率化

AFGによるエイリアス解析 (計算過程) 計算過程 … エイリアス解析のグラフ到達問題への置き換えによる Phase 1: エイリアスフローグラフ (AFG) の構築 … メソッド内エイリアス解析 節点: 参照型の式 辺: 式間のエイリアス関係 Phase 2: AFGによるエイリアス計算 … メソッド間エイリアス解析

AFGによるエイリアス解析 (例: 単純式) [Phase 1 ～ Phase 2] 1: Integer a, b, c; 2: a = new Integer(1); 3: b = new Integer(2); 4: System.out.println(b); 5: c = a; 6: System.out.println(c); 1: Integer a, b, c; 2: a = new Integer(1); 3: b = new Integer(2); 4: System.out.println(b); 5: c = a; 6: System.out.println(c); a new Integer(1) new Integer(2) b c a new Integer(1) new Integer(2) b c a new Integer(1) new Integer(2) b c 1: Integer a, b, c; 2: a = new Integer(1); 3: b = new Integer(2); 4: System.out.println(b); 5: c = a; 6: System.out.println(c);

AFGによるエイリアス解析 (例: 限定式) [Phase 2: “b.result()”] Step 1: bに関するエイリアス計算 エイリアス: A(b) Step 2: A(b)に関する情報の抽出 型: Calcクラス メソッド: Calc::Calc(), Calc::add(), Calc::result() Step 3: result()に関するエイリアス計算 class Test { Calc a = new Calc(); Calc b = new Integer c; Test() { a.inc(); b.add(1); c = b.result(); } class Test { Calc a = new Calc(); Calc b = new Integer c; Test() { a.inc(); b.add(1); c = b.result(); } class Test { Calc a = new Calc(); Calc b = new Integer c; Test() { a.inc(); b.add(1); c = b.result(); } class Test { Calc a = new Calc(); Calc b = new Integer c; Test() { a.inc(); b.add(1); c = b.result(); } public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i);} public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i);} public class Calc { Integer i; public Calc() {i = new Integer(0); } public void inc() { i = new Integer(i.intValue() + 1); } public void add(int c) { i = new Integer(i.intValue() + c); public Integer result() {return(i);}

AFGによるエイリアス解析 (アルゴリズム) アルゴリズム: フェーズごとに定義可能 Phase 1: メソッド内エイリアス解析 → AFG構築アルゴリズム Phase 2: メソッド間エイリアス解析 → AFG探索アルゴリズム (変更が容易) (b) トレードオフ制御 への配慮 トレードオフ制御を考慮した解析アルゴリズム

Javaエイリアス解析ツール - Java Alias Analysis Tool (JAAT) - 開発 言語: C++ ツールキット: GTK-- コード: 32,000行

評価 JAATに対しJavaプログラムを適用し、提案手法の有効性を検証 プログラム サンプルプログラム 関連するクラスライブラリ ファイル [概要] ファイル 行 TextEditor 1 915 802 114,887 [テキストエディタ] (0.1%) (0.8%) (99.9%) (99.2%) WeirdX 47 16,703 815 115,977 [Xサーバ] (5.5%) (12.6%) (94.5%) (87.4%) ANTLR 129 18,775 267 33,847 [構文解析生成] (32.6%) (35.7%) (67.4%) (64.3%) DynamicJava 242 32,037 825 119,564 [Javaインタプリタ] (22.7%) (21.1%) (77.3%) (78.9%)

考察 (1/3) 解析コスト(時間) Phase 1: AFG構築: モジュール化により、前もってクラスライブラリを解析しておくことができる サンプルプログラムに対するエイリアス解析において、クラスライブラリ全体を再解析する必要はない プログラム サンプルプログラム[sec] 関連するクラスライブラリ[sec] TextEditor 0.001 100 WeirdX 14 101 ANTLR 12 23 DynamicJava 56 110

考察 (2/3) Phase 2: AFGによるエイリアス計算: オンデマンド解析を採用しているため、メソッド間のエイリアス解析はその都度行う必要があるが、そのコストは十分に小さい プログラム [ms] TextEditor 0.65 WeirdX 0.29 ANTLR 0.17 DynamicJava 0.07

考察 (3/3) 解析精度(エイリアス集合の平均要素数) 既存手法: インスタンスを区別しない解析 提案手法: インスタンスを区別した解析 提案手法による解析精度の向上を確認 プログラム 区別する[個] 区別しない[個] TextEditor 4.42 8.31 WeirdX 15.37 24.54 ANTLR 5.94 18.77 DynamicJava 9.16 17.19

まとめ モジュール化によるエイリアス解析効率化手法の提案 JAATによる提案手法の実装、及びその評価 今後の課題 2フェーズで構成 (モジュール解析、オンデマンド解析) AFGを利用 JAATによる提案手法の実装、及びその評価 (a) 効率、(b) トレードオフ制御 への配慮 今後の課題 AFGデータベースの構築 例外処理、スレッドへの対応

むすび (a) 効率、(b) トレードオフ制御、(c) 二次利用 を考慮した3つのプログラム静的解析手法の提案 XMLデータベースを利用した プログラム解析の効率化手法 … (a),(c) Javaプログラム解析フレームワーク JAFの構築