エイリアス関係を考慮した Javaプログラム用静的スライシングツール 井上研究室 山中祐介 y-yamank@ics.es.osaka-u.ac.jp

背景 ソフトウェアの大規模化・複雑化 プログラム言語の高級化 プログラムの理解や保守が困難なものになっている プログラム解析 うっとこの発表 2019/6/10 背景 ソフトウェアの大規模化・複雑化 プログラム言語の高級化 プログラムの理解や保守が困難なものになっている プログラム解析 プログラムスライス エイリアス解析 ‥ 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 壱

プログラムスライス プログラムにおける、ある文のある変数（スライス基準）の値に影響を与える文の集合 特定の機能やエラーに関係ある部分の抽出が可能 1: a = 3; 2: if(a > 0) 3: b = a; 4: else 5: c = a; 6: a = b + 2; スライス基準<6, b>に 対するスライス 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 弐

スライスの計算過程 依存関係解析 プログラム依存グラフ(PDG)の 構築 PDG探索 1: a = 3; 2: if(a > 0) データ依存関係 制御依存関係 プログラム依存グラフ(PDG)の 構築 節点：各プログラム文 有向辺：文間の依存関係 PDG探索 スライス基準に対応する節点から 有向辺を逆向きに探索 1: a = 3; 2: if(a > 0) 3: b = a; 4: else 5: c = a; 6: a = b + 2; a a b 1 2 3 5 6 1 2 3 5 6 1 2 3 5 6 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 参

エイリアス関係 同じメモリ空間を指す可能性がある式間の同値関係 エイリアス関係が発生する箇所 エイリアス集合 引数の参照渡し 参照変数 ポインタを介した間接参照 エイリアス集合 エイリアス関係にある式の集合 1: a = new Integer(1); 2: b = new Integer(2); 3: c = b; 4: System.out.println(c); 5: c = a; 6: System.out.println(c); 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 四

エイリアス解析 静的解析によりエイリアス集合を求めること オブジェクト指向言語に対して静的解析を行う際に有効 オブジェクト指向言語には動的束縛や多態などの実行時決定要素が多い 実行時決定要素の特定がある程度可能 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 伍

既存のスライス手法の問題点 既存のオブジェクト指向言語を対象とした依存関係解析手法では、エイリアス関係の考慮について言及されていない a b 1: class A { 2: int n; 3: } 1: A a = new A(); 2: A b; 3: b = a; 4: a.n += 1; 5: System.out.println(b.n); a.nとb.nは同じメモリ領域にあるので、4行目から5行目に メンバ変数nに関するデータ依存関係があるはず 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 六

研究の目的 Javaを対象とするエイリアス関係を考慮した静的スライス計算手法の提案、実装 既存の手法より正確なデータ依存関係の抽出が期待できる オブジェクト指向言語特有の実行時決定要素に対する解析が容易になる 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 七

提案手法の方針 エイリアス関係を考慮したデータ依存関係の抽出を行うため3種類の表を用意 前提としてエイリアス解析が終了している 文番号：変数vが最後に定義された文の番号 エイリアスID：エイリアス集合を区別するためのID 前提としてエイリアス解析が終了している 必要に応じてエイリアス集合の情報の取得が可能である 変数表 文番号、エイリアスID エイリアス表 エイリアスID メンバ変数表 メンバ変数、変数表 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 八

適用例(1行目) 同一のエイリアス集合に 属しているためIDは同じ aは参照変数であるため エイリアス集合を計算し エイリアス表を用意 1: class A { 2: int n; 3: } 式 ID 1:a 01 1:new 3:a 3:b 4:a 5:b IDに対するメンバ変数表を用意 メンバ変数はn 変数表にIDを記入 1: A a = new A(); 2: A b = new A(); 3: b = a; 4: a.n += 1; 5: System.out.println(b.n); 変数表 メンバ変数表 変数 文番号 ID a 1 ID メンバ変数 文番号 01 n 1 01 aの変数表を用意、文番号は1 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 九

適用例(2行目) 新しいエイリアス集合 IDは02 bは参照変数であるためエイリアス 集合を計算しエイリアス表を用意 1: class A { 2: int n; 3: } bは参照変数であるためエイリアス 集合を計算しエイリアス表を用意 式 ID 1:a 01 1:new 3:a 3:b 4:a 5:b 式 ID 2:b 02 2:new 1: A a = new A(); 2: A b = new A(); 3: b = a; 4: a.n += 1; 5: System.out.println(b.n); 変数表 メンバ変数表 IDに02を記入 IDに対するメンバ変数表を用意 変数 文番号 ID a 1 01 b 2 02 変数 文番号 ID a 1 01 b 2 変数 文番号 ID a 1 01 ID メンバ変数 文番号 01 n 1 02 2 ID メンバ変数 文番号 01 n 1 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾

適用例(3行目) 3:bはエイリアス表に含まれている 同一のIDからa,bは 変数bは定義されているため ため変数表のIDを01に変更 1: class A { 2: int n; 3: } 式 ID 1:a 01 1:new 3:a 3:b 4:a 5:b 式 ID 2:b 02 2:new 1: A a = new A(); 2: A b = new A(); 3: b = a; 4: a.n += 1; 5: System.out.println(b.n); a 変数aは参照されているため 1～3へのデータ依存関係を抽出 変数bは定義されているため 文番号を3に変更 3:bはエイリアス表に含まれている ため変数表のIDを01に変更 同一のIDからa,bは 同じメモリ領域を参照している ことがわかる 変数表 メンバ変数表 変数 文番号 ID a 1 01 b 3 変数 文番号 ID a 1 01 b 2 02 変数 文番号 ID a 1 01 b 3 02 ID メンバ変数 文番号 01 n 1 02 2 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾壱

適用例(4行目) aとnは参照されているため 1～4へのデータ依存関係を抽出 nは定義されているため文番号を4に変更 エイリアス表 1: class A { 2: int n; 3: } 式 ID 1:a 01 1:new 3:a 3:b 4:a 5:b 式 ID 2:b 02 2:new 1: A a = new A(); 2: A b = new A(); 3: b = a; 4: a.n += 1; 5: System.out.println(b.n); a a,n aとnは参照されているため 1～4へのデータ依存関係を抽出 nは定義されているため文番号を4に変更 変数表 メンバ変数表 変数 文番号 ID a 1 01 b 3 ID メンバ変数 文番号 01 n 4 02 2 ID メンバ変数 文番号 01 n 1 02 2 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾弐

適用例(5行目) b,nは参照されているため3～5,4～5の データ依存関係を抽出 エイリアス表 1: class A { 2: int n; 3: } 式 ID 1:a 01 1:new 3:a 3:b 4:a 5:b 式 ID 2:b 02 2:new 1: A a = new A(); 2: A b = new A(); 3: b = a; 4: a.n += 1; 5: System.out.println(b.n); a a,n b n b,nは参照されているため3～5,4～5の データ依存関係を抽出 変数表 メンバ変数表 変数 文番号 ID a 1 01 b 3 ID メンバ変数 文番号 01 n 4 02 2 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾参

各種情報はフレームワークの既存ライブラリから取得 スライシングツールの実現 我々の研究グループで開発しているJavaプログラム解析フレームワークにスライス計算ライブラリを追加 スライス計算ライブラリ PDG構築部 入力：Javaプログラムの意味解析木とエイリアス集合情報 出力：プログラム依存グラフ スライス計算部 ユーザ要求に応じたスライス計算 各種情報はフレームワークの既存ライブラリから取得 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾四

Javaプログラム解析フレームワーク エイリアス解析 ライブラリ エイリアス フローグラフ XML データベース プログラム依存グラフ スライス計算 ライブラリ ソースコード Java XML-意味解析木 変換ライブラリ 抽象構文木 構文解析 ライブラリ GUI ユーザ 意味解析木 意味解析 ライブラリ 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾伍

評価実験 解析対象プログラム 実験環境 P1：サンプルプログラム(2クラス、24行) P2：簡易ドローツール(3クラス、323行) CPU：Pentium4 1.5Ghz メモリ：512MB OS：FreeBSD 5.0-CURRENT 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾六

評価(解析コスト) コスト削減のためには、どのライブラリを PDG構築の対象に含めるか選択が必要 PDG構築までのコスト うっとこの発表 2019/6/10 評価(解析コスト) PDG構築までのコスト 解析対象が参照しているJDKクラスライブラリを含む P1の総クラス数:272、P2の総クラス数：876クラス P2はP1と比べて遥かにコストが大きい 解析時間(秒) メモリ使用量(MB) プログラム 総時間 P1 17.2 P2 67.8 プログラム 合計 P1 149 P2 457 コスト削減のためには、どのライブラリを PDG構築の対象に含めるか選択が必要 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾七

エイリアスを無視した場合のスライスは正確な 評価(スライスサイズ) 解析対象プログラムのみ(JDKクラスライブラリは含まない) エイリアスを考慮した方がスライスサイズが大きい 増加した文はエイリアス関係にある参照変数がもたらす依存関係 スライスサイズ(行) プログラム エイリアス考慮 エイリアス無視 P1 8 6 P2 42 30 エイリアスを無視した場合のスライスは正確な ものといえないため考慮することが重要 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾八

まとめと今後の課題 オブジェクト指向言語を対象とするエイリアス関係を考慮した静的スライス計算手法の提案、実装 今後の課題 より正確な依存関係の抽出が可能 Javaプログラム解析フレームワークへの追加実装でスライシングツールを実現 今後の課題 スレッド、例外を含めた複雑な制御構造の解析への対応 大規模システムに対する適用実験 PDG構築対象の選択を可能にすることでのコスト削減 平成拾伍年弐月拾八日 二○○二年度修士論文発表会 拾九

終劇