Javaプログラム用スライスシステムの制御依存関係解析

Javaバイトコードの
動的依存解析情報を用いた
スライシングシステムの実現
大阪大学大学院情報科学研究科
梅森文彰誉田謙二横森励士井上克郎
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
1
研究の背景
ソフトウェアの大規模化・複雑化によって
テスト工程のコストが増大
フォールトの検出やフォールト位置の特定・修正（デバッ
グ）に時間がかかるようになった
フォールト位置の特定を効率よく行う手法
プログラムスライス
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
2
研究の目的
近年のソフトウェア開発環境ではオブジェクト指向
言語 Javaが多く利用されている
実利用を考慮したスライシングシステムはあまり実現
されていない
Javaを対象とするスライシングシステムの構築
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
3
Javaを対象とするスライシングシステムの構築
Javaの特徴
多くの実行時決定要素の存在
配列の添字、オブジェクトへの参照、動的束縛
例外処理、並列処理
静的な解析のみでは十分な解析精度が得られない
動的な解析のみでは多大な解析コストがかかる
静的な解析と動的な解析を組み合わせた
DC（Dependence Cache）スライスをJavaに適用
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
4
プログラムスライス
ある文のある変数(スライス基準)の値に
影響を与えうる文の集合
1:
2:
3:
4:
5:
6:
7:
scanf("%d", &a);
scanf("%d", &b);
max = a;
min = b;
if ( a > b) {
max = b;
min = a;
}
8: printf("%d", max);
maxの値が誤っている
maxをスライス基準に指定
maxに関係ある部分を抽出
関連のあるプログラム文のみを抽出する
ことで、デバッグ対象を限定することがで
き、フォールト位置特定を効率よく行う
ことができる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
5
スライス - 計算手順 1. 依存関係解析
制御依存関係(CD)解析
データ依存関係(DD)解析
2. プログラム依存グラフ(PDG)構築
節点: プログラム文やバイトコード命令
辺: 節点間の依存関係
3. スライス計算
スライス基準に対応するPDG節点から
有向辺を逆向きにたどる
到達可能な節点集合に対応する文が
求めるスライス
DD
CD
1: scanf(“%d”,&i);
2: if (i < 5) {
3: a = 1;
4: b = 0;
5: i = i + 1;
6: }
7: printf(“%d”,i);
プログラム依存グラフ
1
2
3
4
5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
7
6
DCスライス
制御依存関係解析：静的
実行時のコスト削減
データ依存関係解析：動的
配列やポインタ，構造体の詳しい解析
PDG節点：ソースプログラムの各文やバイトコードの
各命令
メモリ使用量の抑制
動的スライスより低コストで、静的スライスより高
精度なスライス計算が可能
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
7
DCスライスにおける動的データ依存関係解析
一時記憶：キャッシュ
各データと1対1対応するように用意する
各データを最後に定義した命令を保持する
アルゴリズム
10: a = 1;
データが定義されたとき
a
11: c = 4;
12: b = a;
定義した文をキャッシュに保存
データが参照されたとき
キャッシュ
最後に定義した文をキャッシュから取得 a b c
10
11
取得した文と実行中の文との間に
（文12実行時）
発生するデータ依存関係を抽出
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
8
既存のDCスライス実現手法とその問題点
ソースコード埋め込みによるDCスライス計算†
ソースコードに解析命令を付加し、
コンパイル・実行することにより
動的情報を持つPDGを構築
1 : a = 10;
2 : b = a + 1;
問題点
構文制約によりソースコードの埋め込み
位置が制限される
クラスファイルしか存在しないクラスを
介した依存関係解析の実現が困難
解析精度の低下
1’: def(a, 1);
1 : a = 10;
2’: ref(a, 2);
2’: def(b, 2);
2 : b = a + 1;
F.Ohata, K.Hirose, M.Fujii and K.Inoue:“A Slicing Method for Object-Oriented Programs Using
Lightweight Dynamic Information”, Proceedings of 8th Asia Pacific Software Engineering
Conference , pp.273-280, Macau, China, December (2001).
†
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
9
提案する実現手法
「Javaバーチャルマシン（JVM）に基づく動的データ依存関係解析」
JVMを機能拡張することにより、実行時にバイトコード上でのデータ依
存関係を動的に抽出する
バイトコード上での制御依存関係も定義し，静的に解析する
利点
解析精度の向上
コードの埋め込みを行わないため、構文制約の影響を受けず、解析精度の低下を
防止
クラスファイルしか存在しないクラスを介した依存関係の抽出も可能
細粒度の解析の実現
バイトコードの各命令をPDG節点とすることで、ソースコードの各文を節点とした場合
と比べ細粒度の解析が可能
ユーザへの負担の軽減
通常の実行を行うだけでDCスライス計算に必要な情報を取得することができる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
10
Javaスライシングシステムの構成
ソースコード
int i = 0;
if (i < 5) {
i++;
}
スライス基準
iconst_0
Javaコンパイラ
istore_1
1:
iconst_0
1:
0
2:
isotre_1
2:
i=
3:
iconst_5
3:
5
4:
iload_1
4:
i
5:
if_cmpge L8
5:
<
6:
iinc 1 1
6:
i++
nop
7:
<
return
8:
main
7:
8:
L8:
CD
DD
スライサ
Java
バーチャルマシン
制御依存関係
解析ツール
iconst_5
iload_1
if_cmpge
L8
iinc 1 1
L8: nop
スライス結果
return
静的制御依存関係
通常の実行結果
動的データ依存関係
int i = 0;
if (i < 5) {
i++;
}
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
11
Javaスライシングシステム – 計算手順 Phase 1: ソースコード・バイトコード対応表の出力
Phase 2: バイトコードに対する依存関係解析
(a)：静的制御依存関係解析
(b)：動的データ依存関係解析
Phase 3: PDGによるスライス計算
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
12
Phase1:ソースコード・バイトコード対応表の出力
コンパイル時に、ソースコードのトークン列とバイトコー
ドとの対応を抽出
int i = 0;
if (i < 5) {
i++;
}
iconst_0
0
istore_1
i=
iconst_5
5
iload_1
i
if_cmpge L8
<
iinc 1 1
L8:
nop
return
i++
<
main
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
13
Phase 2(a):
静的制御依存関係解析†
バイトコード間の制御依存関係を静的に解析
手順
基本ブロックの分割
制御フローグラフの構築
制御依存関係の抽出
iconst_0
istore_1
iconst_5
iload_1
if_cmpge L8
iconst_0
istore_1
iconst_5
iload_1
iconst_0
istore_1
iconst_5
iload_1
if_cmpge L8
iinc 1 1
L8:
if_cmpge L8
iinc 1 1
iinc 1 1
nop
L8:nop
return
return
†Andrew.W:
L8:
nop
return
Modern Compiler Implementation in C, 1998
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
14
Phase 2(b): 動的データ依存関係解析
Java バーチャルマシン
s1:
s2:
s3:
s4:
iconst_0
iconst_5
iadd
istore_0
ローカル変数
0
5
スタック
5
5
0
対応するキャッシュ
データ依存関係
0
s4
s2
s1
s3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
15
Phase 3: PDGによるスライス計算
スライス基準に対応するPDG節点から有向辺を逆
向きにたどることで、スライスを抽出
手順
対応表による、スライス基準(S)からスライス基準(B)への変
換
PDG(B)の構築およびその探索
対応表による、スライス(B)からスライス(S)への変換
スライス、スライス基準、PDGに対し、バイトコード、ソースコー
ドそれぞれに関するものを、(S)、(B)を用いて表す。
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
16
Javaスライシングシステム - 実装 Phase 1:
ソースコード・バイトコード対応表の出力
Javaコンパイラの機能拡張
言語:Java、行数:約3,000行(約42,000行)
Phase 2
(a):
バイトコードに対する静的制御依存関係解析
バイトコードダンプツールの機能拡張
言語:C、行数:約1,600行(約4,000行)
(b):
バイトコードに対する動的データ依存関係解析
Java バーチャルマシンの機能拡張
言語:C、行数:約1,100行(約520,000行)
Phase 3:
PDGによるスライス計算
スライサの作成
言語:C、行数:約1,200行
()内は機能拡張後のツールにおけるコード総行数を表す
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
17
評価（1/2）
ソートプログラム（5クラス・231行）
（Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2）
JVM実行時間 [ms]
通常実行解析付実行
341
3,089
JVM消費メモリ [Kbytes]
通常実行解析付実行
4,178
26,091
多くのコストがかかるものの、現実的な数値
バイトコードを単位とする細粒度の解析
JDKライブラリに対するデータ依存関係解析
ソースコード・バイトコードの対応関係を簡単化するため、
バイトコードの最適化を行っていない
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
18
評価（2/2）
動的スライスとの比較
構築されるPDGの節点数
提案手法動的スライス
34,956 1,808,051
スライスサイズ [行（全体に対する割合）]
静的スライス
提案手法
動的スライス
スライス基準1 79（34.2%） 51（22.1%） 51（22.1%）
スライス基準2 27（11.7%） 25（10.8%） 23（10.0%）
動的スライスに比べ十分に小さいコストでのスライス計算
静的スライスに比べ高い解析精度のスライス結果
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
19
まとめ
細粒度Javaスライシングシステムの試作
ソースコード・バイトコードの対応表の出力
バイトコードに対する静的制御依存関係解析
JVMを用いた動的データ依存関係解析
PDGによるスライス計算
高精度のスライスを低コストで抽出可能
今後の課題
バイトコードの最適化に対応したバイトコード・ソースコー
ド対応表の作成
実際のプログラム開発におけるシステムの適用
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
20

Download Report