動的データ依存関係解析を用いた Javaプログラムスライス手法 廣瀬 航也† 大畑 文明† 井上 克郎†‡ †大阪大学大学院 基礎工学研究科 ‡奈良先端科学技術大学院大学 情報科学研究科

発表内容 プログラムスライス 動的データ依存関係解析を用いた Javaプログラムスライス手法の提案 提案手法の実装 まとめと今後の課題 静的スライス 動的スライス Dependence Cacheスライス 動的データ依存関係解析を用いた Javaプログラムスライス手法の提案 提案手法の実装 まとめと今後の課題 2019/2/25 ソフトウェアサイエンス研究会

フォールト位置の特定を効率よく行う一手法 プログラムスライス 背景 ソフトウェアの大規模化，複雑化 テスト工程のコストの増大 テスト (フォールトの検出) デバッグ (フォールト位置の特定，修正) フォールト位置の特定を効率よく行う一手法 プログラムスライス 2019/2/25 ソフトウェアサイエンス研究会

プログラムスライス ある文のある変数(スライス基準)の値に 影響を与えうる文の集合 maxの値が誤っている maxをスライス基準に指定 scanf("%d", &a); scanf("%d", &b); max = a; min = b; if ( a < b) { max = b; min = a; } printf("%d", max); scanf("%d", &a); scanf("%d", &b); max = a; min = b; if ( a > b) { max = b; min = a; } printf("%d", max); maxの値が誤っている maxをスライス基準に指定 maxに関係ある部分を抽出 2019/2/25 ソフトウェアサイエンス研究会

プログラムスライスの計算手法 1. 依存関係解析 2. プログラム依存グラフ(PDG)構築 3. グラフ探索 データ依存関係 (DD) 制御依存関係 (CD) 2. プログラム依存グラフ(PDG)構築 節点: 文，条件節を表す 辺: 節点間の依存関係を表す 3. グラフ探索 スライス基準に対応する節点 から辺を逆向きにたどる 2019/2/25 ソフトウェアサイエンス研究会

プログラムスライスの計算手法 (例) 28 30 31 11 16 17 18 19 3 5 6 8 27 スライス基準(30,x) 28 a b x c sum 1: #include <stdio.h> 2: 3: float absolute(float x) 4: { 5: if (x < 0) { 6: x = -1 * x; 7: } 8: return x; 9: } 10: 11: float ave(int a, int b, int c) 12: { 13: int sum; 14: float x; 15: 16: sum = a + b + c; 17: x = (float)sum / 3.0; 18: x = absolute(x); 19: return x; 20: } 21: 22: int main(void) 23: { 24: int a, b, c; 25: float x; 26: 27: printf("Input a b c ?"); 28: scanf("%d %d %d", &a, &b, &c); 29: 30: x = ave(a, b, c); 31: printf("Ave = %9.3f\n", x); 32: return 0; 33: } スライス基準(30,x) 1: #include <stdio.h> 2: 3: float absolute(float x) 4: { 5: if (x < 0) { 6: x = -1 * x; 7: } 8: return x; 9: } 10: 11: float ave(int a, int b, int c) 12: { 13: int sum; 14: float x; 15: 16: sum = a + b + c; 17: x = (float)sum / 3.0; 18: x = absolute(x); 19: return x; 20: } 21: 22: int main(void) 23: { 24: int a, b, c; 25: float x; 26: 27: printf("Input a b c ?"); 28: scanf("%d %d %d", &a, &b, &c); 29: 30: x = ave(a, b, c); 31: printf("Ave = %9.3f\n", x); 32: return 0; 33: } 28 31 11 16 17 18 19 3 5 6 8 27 a b x c sum 1: #include <stdio.h> 2: 3: float absolute(float x) 4: { 5: if (x < 0) { 6: x = -1 * x; 7: } 8: return x; 9: } 10: 11: float ave(int a, int b, int c) 12: { 13: int sum; 14: float x; 15: 16: sum = a + b + c; 17: x = (float)sum / 3.0; 18: x = absolute(x); 19: return x; 20: } 21: 22: int main(void) 23: { 24: int a, b, c; 25: float x; 26: 27: printf("Input a b c ?"); 28: scanf("%d %d %d", &a, &b, &c); 29: 30: x = ave(a, b, c); 31: printf("Ave = %9.3f\n", x); 32: return 0; 33: } 30 スライス基準(30,x) 11: float ave(int a,int b,int c) 12: { 18: x = absolute(x); 20: } 3: float absolute(float x) 4: { 5: if (x < 0) { 6: x = -1 * x; 7: } 8: return x; 9: } 制御依存関係 return call 5: if (x < 0) { 6: x = -1 * x; 7: } 制御依存関係 16: sum = a + b + c; 17: x = (float)sum / 3.0; データ依存関係 sum 28 30 31 11 16 17 18 19 3 5 6 8 27 a b x c sum : DD : CD 2019/2/25 ソフトウェアサイエンス研究会

静的スライス 全ての起こりうる実行系列について解析 対象: ソースコード 配列やポインタの詳細な 解析が困難 1: a = 3; 2: b = 2; 3: scanf("%d", &c); 4: if ( c == 0 ) 5: d = a; 6: else 7: d = a + 1; 8: e = a + b; 9: printf("%d", d); 10: printf("%d", e); 2019/2/25 ソフトウェアサイエンス研究会

動的スライス ある特定の入力データにおける 実行系列について解析 対象: 実行系列 - 入力が 0 の場合 - 1: a = 3; 2: b = 2; 3: scanf("%d", &c); 4: if ( c == 0 ) 5: d = a; 6: else 7: d = a + 1; 8: e = a + b; 9: printf("%d", d); 10: printf("%d", e); 2019/2/25 ソフトウェアサイエンス研究会

Dependence Cache(DC)スライス データ依存関係解析: 動的 制御依存関係解析: 静的 1: a[0] = 0; 2: a[1] = 3; 3: scanf("%d",&b); 4: a[b] = 2; 5: c = a[0]+4; 6: printf("%d", c); 配列の各要素を区別 ポインタの指すメモリを区別 解析コストの増加を抑える ことができる 1: a = 0; 2: b = 2; 3: c = &a; 4: *c = 4+b; 5: printf("%d", a); 2019/2/25 ソフトウェアサイエンス研究会

動的データ依存関係解析 (1/2) 変数vが文sで定義されたことを保存する データ依存関係 動的解析 文sで定義された変数vが文tで使用されたとき 　vに関するsからtへのデータ依存関係が存在 動的解析 文tの実行の際に，使用される変数vが どの文(s)で定義されたのか 変数vが文sで定義されたことを保存する 2019/2/25 ソフトウェアサイエンス研究会

動的データ依存関係解析 (2/2) キャッシュの内容 キャッシュの更新/データ依存辺の追加 各変数が最後に定義された文の文番号 ある文である変数が 定義される 文番号をキャッシュに保存 使用される 最後に定義された文をキャッシュから取得 取得した文から現在の文に依存辺を引く 2019/2/25 ソフトウェアサイエンス研究会

配列の各要素を区別した解析 入力が 0 の場合 1: a[0] = 0; 2: a[1] = 3; 3: scanf("%d", &b); 4: a[b] = 2; 5: c = a[0] + 4; 6: printf("%d", c); キャッシュ c b a[1] a[0] - キャッシュ c b a[1] a[0] 1 2 3 4 5 b - 3 2 4 5 3 2 4 - 3 2 1 - 2 1 - - 1 a[0] c 2019/2/25 ソフトウェアサイエンス研究会

各スライス手法の比較 静的解析 動的解析 静的 DD/CD - プログラム の各文 動的 実行系列 DC CD DD 依存グラフの 節点 2019/2/25 ソフトウェアサイエンス研究会

スライス対象: Java 近年ソフトウェア開発環境で多く利用される Javaにおける実行時決定要素 静的解析では限界がある 配列の添字 オブジェクトへの参照 動的束縛 例外 並列処理 静的解析では限界がある 2019/2/25 ソフトウェアサイエンス研究会

提案手法 オブジェクト指向言語に対応したDCスライス データ依存関係解析: 動的 制御依存関係解析: 静的 メソッド間の制御依存関係解析: 動的 オブジェクトへの参照の解析 動的束縛の解析 動的スライスと比較して実行時解析のコストの増加を抑えることができる 2019/2/25 ソフトウェアサイエンス研究会

オブジェクト指向言語への対応 各メンバ変数のキャッシュを その変数が属するクラス内に保持する オブジェクトごとの解析 キャッシュ管理の単純化 クラスcのメンバ変数vのキャッシュ クラスcのCache型メンバ変数“vCache” オブジェクトごとにキャッシュを保持する オブジェクトごとの解析 キャッシュ管理の単純化 2019/2/25 ソフトウェアサイエンス研究会

メソッド間の制御依存関係解析 動的なメソッド間の制御依存関係解析 オブジェクト カプセル化 Javaの動的束縛 データとそれを操作するメソッドの組み合わせ カプセル化 データへのアクセスはメソッドを通して行う Javaの動的束縛 実行中のオブジェクトのクラスに基づき適切なオーバーライドメソッドを選択する 動的なメソッド間の制御依存関係解析 2019/2/25 ソフトウェアサイエンス研究会

動的束縛に関する問題の解決 動的解析により，呼び出すメソッドを一意に決定できる 3 6 1 5 11 21 22 12 2 3 6 1 5 a b i 3 6 1 5 11 21 22 12 2 a b i 3 6 1 5 11 21 22 12 2 a b i クラス C int a; X b; 1: read(a); 2: if(a<0) 3: b = new X(); 4: else 5: b = new Y(); 6: b.m(a); クラス X 11: m(int i) { 12: print(“X”, i); 13: } クラス Y extends X 21: m(int i) { 22: print(“Y”, i); 23: } 2019/2/25 ソフトウェアサイエンス研究会

実装 (1/2) インタプリタ方式 プリプロセッサ方式 インタプリタが実行，解析を行う あらゆる実行時情報を取得可能 実現に大きな手間がかかる 実行速度が遅い プリプロセッサ方式 ソースにそれ自身を解析する命令を付加する 実現が比較的容易 JVMを選択可能 (JITによる高速実行) 2019/2/25 ソフトウェアサイエンス研究会

実装 (2/2) ソース スライス基準 プリプロセッサ コンパイラ UI 静的解析 ソース ＋ 解析命令 バイトコード ＋ 解析コード スライサ Java Virtual Machine PDG 動的解析 2019/2/25 ソフトウェアサイエンス研究会

解析命令の付加 変換 ある文である変数が 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/2/25 ソフトウェアサイエンス研究会

まとめ Javaプログラムスライス手法を提案 動的なデータ依存関係解析 動的なメソッド間制御依存関係解析 実行時決定要素の詳細な解析 オブジェクトを区別した解析 動的束縛に関する問題の解決 2019/2/25 ソフトウェアサイエンス研究会

今後の課題 提案手法の実装 提案手法の実験的評価 並列処理への対応 例外処理への対応 スライスサイズ 実行時使用メモリ 実行時間 2019/2/25 ソフトウェアサイエンス研究会

各スライス手法の比較 スライスサイズ (行) 静的 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/2/25 ソフトウェアサイエンス研究会