静的情報と動的情報を用いた Javaプログラムスライス計算法 2019/5/7 静的情報と動的情報を用いた Javaプログラムスライス計算法 広瀬 航也 井上研究室 2000年度修士論文発表会

発表内容 プログラムスライス Javaプログラムスライス手法の提案 まとめと今後の課題 静的スライス 動的スライス Dependence Cache スライス Javaプログラムスライス手法の提案 適用例 提案手法の実装 評価 まとめと今後の課題 2019/5/7 2000年度修士論文発表会

フォールト位置の特定を効率よく行う一手法 プログラムスライス 背景 ソフトウェアの大規模化，複雑化 テスト工程のコストの増大 テスト (フォールトの検出) デバッグ (フォールト位置の特定，修正) フォールト位置の特定を効率よく行う一手法 プログラムスライス 2019/5/7 2000年度修士論文発表会

プログラムスライス ある文のある変数(スライス基準)の値に 影響を与えうる文の集合 maxの値が誤っている maxをスライス基準に指定 1: scanf("%d", &a); 2: scanf("%d", &b); 3: max = a; 4: min = b; 5: if ( a < b) { 6: max = b; 7: min = a; } 8: printf("%d", max); maxの値が誤っている maxをスライス基準に指定 maxに関係ある部分を抽出 2019/5/7 2000年度修士論文発表会

プログラムスライスの計算手法 1. 依存関係解析 2. プログラム依存グラフ(PDG)構築 3. グラフ探索 データ依存関係 (DD) 制御依存関係 (CD) 2. プログラム依存グラフ(PDG)構築 節点: 文，条件節を表す 辺: 節点間の依存関係を表す 3. グラフ探索 スライス基準に対応する節点 から辺を逆向きにたどる 10: me(5); … 20: void me(int a) { return; } 制御依存関係 CALL RETURN 10: if (a < 1){ … 20: b = a; 制御依存関係 10: a = 1; … 20: b = a; a データ依存関係 PDG 1 2 3 4 5 6 7 8 PDG 1 2 3 4 5 6 7 8 PDG 1 2 3 4 5 6 7 8 2019/5/7 2000年度修士論文発表会

静的・動的スライス 静的スライス 動的スライス ソースコードを対象に静的依存関係解析 全ての起こりうる実行を考慮した解析 ある入力に関する実行系列を対象に動的依存関係解析 スライスサイズが大きい 実行時の解析コストが大きい 2019/5/7 2000年度修士論文発表会

Dependence Cache(DC)スライス† データ依存関係解析: 動的 制御依存関係解析: 静的 配列の各要素を区別 ポインタの指す記憶域を区別 解析コストの増加を抑えることができる † Ashida Y., Ohata F. and Inoue K. :"Slicing Methods Using Static and Dynamic Information'', Proceedings of the 6th Asia Pacific Software Engineering Conference (APSEC'99), pp. 344-350, December 1999. 2019/5/7 2000年度修士論文発表会

動的データ依存関係解析 一時記憶: キャッシュ アルゴリズム 各変数が最後に定義された文の文番号を保存 ある文である変数が定義される 2019/5/7 動的データ依存関係解析 一時記憶: キャッシュ 各変数が最後に定義された文の文番号を保存 アルゴリズム ある文である変数が定義される 文番号をキャッシュに保存 ある文である変数が使用される 最後に定義された文をキャッシュから取得 取得した文から現在の文に依存辺を引く 10: a = 1; … 20: b = a; a キャッシュ a 10 b - ・・・ (文20実行時) 2019/5/7 2000年度修士論文発表会 2000年度修士論文発表会

各スライス手法の比較 DD解析 CD解析 依存グラフの 節点 静的スライス 静的 プログラム の各文 DCスライス 動的 動的スライス 実行系列 スライスサイズ: 静的 ³ DC ³ 動的 解析時間: 静的 > DC > 動的 実行時間: 動的 > DC > 静的 2019/5/7 2000年度修士論文発表会

スライス対象: オブジェクト指向言語 近年ソフトウェア開発環境で多く利用される オブジェクト指向言語における実行時決定要素 配列の添字 オブジェクトへの参照 動的束縛 静的解析では限界がある 2019/5/7 2000年度修士論文発表会

提案手法 オブジェクト指向言語に対応したDCスライス データ依存関係解析: 動的 制御依存関係解析: 静的 メソッド間の制御依存関係解析: 動的 オブジェクトへの参照の解析 動的束縛の解析 動的スライスと比較して実行時解析のコストの増加を抑えることができる 2019/5/7 2000年度修士論文発表会

オブジェクト指向言語への対応 (DD解析) 各メンバ変数のキャッシュを その変数が属するクラス内に保持する クラスCのメンバ変数vのキャッシュ クラスCのCache型メンバ変数として宣言 インスタンスごとにキャッシュを保持する インスタンスを区別した解析 キャッシュ管理の単純化 2019/5/7 2000年度修士論文発表会

DD解析の適用例 = 1 P a; Cache aCache; class P class P P b; Cache bCache; P c; Cache cCache; int d; Cache dCache; class P int data; Cache dataCache; class P data = 10 dataCache = 4 data dataCache = 2 int data; Cache dataCache; = 3 = 7 1: a = new P(); 2: b = new P(); 3: c = new Q(); 4: a.data = 10; 5: b.data = 20; 6: c.data = 30; 7: d = a.data + c.data; 8: System.out.print(d); 9: System.out.print(b.data); data dataCache data = 20 dataCache = 5 class Q extends P data dataCache data = 30 dataCache = 6 2019/5/7 2000年度修士論文発表会

オブジェクト指向言語への対応 (メソッド間CD解析) データとそれを操作するメソッドの組み合わせ カプセル化 データへのアクセスはメソッドを通して行う 動的束縛 実行中のオブジェクトのクラスに基づき適切なオーバーライドメソッドを選択する 動的なメソッド間の制御依存関係解析 呼び出されるメソッドを一意に決定 スライスサイズを小さくすることができる 2019/5/7 2000年度修士論文発表会

メソッド間CD解析の適用例 class Q extends P int calc() { return data/2; } class P int data; Cache dataCache; int calc() { return data*2; } class Q extends P int calc() { return data/2; } int a; Cache aCache; P b; Cache bCache; 1: a = read(); 2: if (a > 0) 3: b = new P(); 4: else 5: b = new Q(); 6: b.data = 10; 7: a = b.calc(); 2019/5/7 2000年度修士論文発表会

本手法の実装 対象言語: Java プリプロセッサとしての実装 通常の実行と動的解析,PDG構築 スライス対象プログラムソースにそれ自身を解析する命令を付加する 通常の実行と動的解析,PDG構築 開発言語: Java (JDK1.3.0_01, JavaCC2.0) 61クラス, 約10,000行(+12,000行[自動生成]) コンパイル, 実行 2019/5/7 2000年度修士論文発表会

評価 CGIプログラム スライスサイズ [行(全体に対する割合)] 静的スライス 本手法 動的スライス スライス基準1 26 (11.7%) 2クラス, 223行 スライスサイズ [行(全体に対する割合)] 静的スライス 本手法 動的スライス スライス基準1 26 (11.7%) 15 ( 6.7%) 15 ( 6.7%) スライス基準2 83 (37.2%) 27 (12.1%) 27 (12.1%) スライス基準3 37 (16.6%) 24 (10.8%) 24 (10.8%) 実行時間 [ms] 消費メモリ [Kbyte] 通常実行 解析付実行 通常実行 解析付実行 138 582 478 645 (Celeron500MHz, 128MB, Windows98, Java1.3.0_01) 2019/5/7 2000年度修士論文発表会

まとめと今後の課題 まとめ 今後の課題 Javaプログラムスライス手法を提案 例外処理への対応 マルチスレッドへの対応 動的データ依存関係解析 動的メソッド間制御依存関係解析 スライスサイズの減少 今後の課題 例外処理への対応 マルチスレッドへの対応 2019/5/7 2000年度修士論文発表会

GUIプログラムへの適用 class DrawPanel extends Panel implements MouseListener,MouseMotionListener { addMouseMotionListener(this); addMouseListener(this); } void mouseDragged(MouseEvent e) void mouseMoved(MouseEvent e) void mousePressed(MouseEvent e) void mouseReleased(MouseEvent e) void mouseClicked(MouseEvent e) class A{ data method() } class B{ data method() } class C{ data method() } class D{ data method() } class E{ data method() } 2019/5/7 2000年度修士論文発表会

各スライス手法の比較 スライスサイズ (行) 静的 DC 動的 P1: カレンダー表示 (88行) P2: 酒屋問題 (387行) 20.7 15.0 4.7 P2 182 15.7 5.3 (Celeron-450MHz, 128MB) P3 187 61 7.7 静的解析時間 (ms) 実行時間 (ms) 静的 DC 動的 静的 DC 動的 P1 14 4.5 N/A P1 52 55 184 P2 219 19 N/A P2 46 49 4,649 P3 710 48 N/A P3 4,869 5,274 38,969 2019/5/7 2000年度修士論文発表会

静的解析コスト 実行時間 [ms] 通常 (スライス無し) 本手法 静的解析 - 6,100 命令付加 - 540 コンパイル 6,480 6,760 合計 6,480 13,400 消費メモリ [Kbyte] 通常 本手法 372 3,207 通常 本手法 223 1,754 ソース [行] 2019/5/7 2000年度修士論文発表会

依存関係解析命令の付加 変換 ある文である変数が 1 : int a = 10; 0 : iniPDG(); 2 : int b = 20; 3 : int c; 4 : c = a + b; 5 : println(c); 0 : iniPDG(); 1’: def(a, 1); 1 : int a = 10; 2’: def(b, 2); 2 : int b = 20; 3’: def(c, 3); 3 : int c; 4’: ref(a, 4); 4’: ref(b, 4); 4’: def(c, 4); 4 : c = a + b; 5’: ref(c, 5); 5 : println(c); 変換 ある文である変数が 定義される(def): 文番号を保存 使用される(ref): 最後に定義された文から依存辺を引く 2019/5/7 2000年度修士論文発表会