動的情報を利用したJavaスライスシステム～メソッド

動的情報を利用したJavaスライスシステム
～メソッド間動的データ依存関係の適用と
ユーザインターフェース部の試作～
藤井将人
井上研究室
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
背景
ソフトウェアの大規模化，複雑化
テスト工程のコストが増大
フォールトの検出・位置の特定・修正
フォールト位置の特定を効率よく行える一手法
プログラムスライス
プログラムスライス：プログラム中の，ある変数
に対して影響を与える文の集合
1
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラムスライス計算手順
1. 依存関係解析
a=7
データ依存関係解析
b=m(a)
制御依存関係解析 max=a;
2.
データ依存関係
1: a=7;
2: b=m(a);
3: max=a; 制御依存関係
if (a>b)
プログラム依存グラフ（PDG）構築
4: if (a>b)
5: max=b;
節点: 文，条件節
6: print(max);
max=b
print(max)
辺: 節点間の依存関係
3. PDG探索m(int x)
m1: int m(int x){
m2: return x-3}
スライス基準に対応する節点
から辺を逆向きにたどる
return x-3
2
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
Javaスライスシステム
システム概要
依存関係解析部
DCスライス
– データ依存関係解析：動的
– 制御依存関係解析：静的
＋
メソッド間データ依存関係解析：動的
– メソッド間データ依存関係：
メソッド呼び出し文と各メソッドとの依存関係
ユーザインターフェース(GUI)部
スライス結果を表示
3
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
ユーザインターフェース
スライス基準を指定し、スライス結果を表示
主な機能
スライスにあたる文の背景に色を挿入
GUI内からプログラムのコンパイル・実行が可能
複数のファイルにわたるプログラムに対応
開発言語：
Java
サイズ：
約3100行
4
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
手法提案の背景
Calling-Context（呼び出し経路）を特定できない問題
A(){
・・
k=g;
a=M(k);
print(a);
・・
}
int M(int x){
・・
return m;
}
B(){
・・
c=M(b);
・・
}
依存関係の存在しない,
メソッドBもスライスに含まれる
Calling-Contextを考慮した解析を行うことで，
スライスサイズを削減できる
5
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
提案手法
メソッド間データ依存関係解析を動的に行う
メソッド間データ依存関係：
メソッド呼び出し文と各メソッドとの依存関係
アルゴリズム概要
PDG構築時に，メソッド間データ依存辺に実行履歴
(index)を付加する
indexに沿ってPDGを探索する
6
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
履歴付加アルゴリズム
indexを用意
1.呼び出し,returnのたびに依存辺にindexをインクリメント
して付加
2.他のメソッドの変数を直接参照するときはindexをインク
リメントせずに付加
index=4
index=3
index=5
index=6
index=9
main(){
・・
g=5;
A();
B();
・・
}
4
4
A(){
・・
k=g;
a=M(k);
print(a);
・・
}
5
6
int M(int x){
・・
return m;
}
8
9
7
B(){
・・
c=M(b);
・・
}
7
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
履歴付きPDG探索アルゴリズム
index値に沿って探索
探索可能な依存辺のうち，最後にたどった履歴付き依
存辺のindex値より小さく，かつ最大値をもつような依存
辺だけをたどる
main(){
・・
g=5;
A();
B();
・・
}
4
4
A(){
・・
k=g;
a=M(k);
print(a);
・・
}
5
6
int M(int x){
・・
return m;
}
8
9
B(){
・・
c=M(b);
・・
}
7
スライスに含まれない=Calling-Context解決
8
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
評価実験
提案手法をJavaスライスシステムに実装
比較手法
メソッド間依存辺にだけ履歴をつける手法(本提案手法)
すべての依存辺に履歴をつける手法(all)
辺を引くたびにindexをインクリメントする
indexが小さい辺を探索
提案手法
all
履歴をつけない手法（DCスライス）
スライスサイズ(行)
42
40
最大index値
3700 21000
PDG構築時間(s)
55
331
PDG探索時間(s)
7
510
DC
83
ー
14
3.5
Sortプログラム
再帰呼び出し
ループ
241行
9
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
まとめと今後の課題
まとめ
動的にメソッド間データ依存関係を解析する手法の提
案
スライスシステムにおけるGUI部の試作
今後の課題
本提案手法の有効性の評価
ループ・再帰呼び出しの存在するプログラムに対する解
析の効率化
10
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
11
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
スライスの有効性
拡張酒屋問題プログラムにおける，(941行)に対する
スライス評価実験
デバッグ時間
スライス使用
スライス不使用
122分
155分
12
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
実験結果
提案手法
スライスサイズ(行)
最大index値
PDG構築時間(ms)
PDG探索時間(ms)
9
6
3072
583
スライスサイズ(行)
プログラム2
ループ
32行
最大index値
PDG構築時間(ms)
PDG探索時間(ms)
all
8
20
3566
784
DC
13
ー
14
942
提案手法
all
14
80
3155
784
14
0
2769
1101
プログラム1
メソッド呼び出し
21行
DC
14
ー
2718
1060
13
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
手法提案の背景
Calling-Context問題：
main(){
・・
g=5;
A();
B();
・・
}
A(){
・・
k=g;
a=M(k);
print(a);
・・
}
int M(int x){
・・
return m;
}
B(){
・・
c=M(b);
・・
}
呼び出し経路を特定できないため,
メソッドBも探索される
Calling-Contextを考慮した解析を行うことで，
スライスサイズを削減できる
14
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
GUI
オープンファイル名
＋
解析ファイル名
メニューバー
ファイル
ツールバー
ファイル情報
実行結果
15
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University

Download Report