動的データ依存関係解析を用いたJavaプログラムスライ

動的データ依存関係解析を用いた
Javaプログラムスライス手法
廣瀬航也†
大畑文明†
井上克郎†‡
†大阪大学大学院
基礎工学研究科
‡奈良先端科学技術大学院大学情報科学研究科
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
発表内容
プログラムスライス
静的スライス
動的スライス
Dependence Cacheスライス
動的データ依存関係解析を用いた
Javaプログラムスライス手法の提案
提案手法の実装
まとめと今後の課題
2015/10/1
2
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
背景
ソフトウェアの大規模化，複雑化
テスト工程のコストの増大
テスト (フォールトの検出)
デバッグ (フォールト位置の特定，修正)
フォールト位置の特定を効率よく行う一手法
プログラムスライス
2015/10/1
3
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラムスライス
ある文のある変数(スライス基準)の値に
影響を与えうる文の集合
scanf("%d", &a);
scanf("%d", &b);
max = a;
min = b;
if ( a >
< b) {
max = b;
min = a;
}
printf("%d", max);
maxの値が誤っている
maxをスライス基準に指定
maxに関係ある部分を抽出
2015/10/1
4
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラムスライスの計算手法
1. 依存関係解析
データ依存関係 (DD)
制御依存関係 (CD)
2. プログラム依存グラフ(PDG)構築
節点: 文，条件節を表す
辺: 節点間の依存関係を表す
3. グラフ探索
スライス基準に対応する節点
から辺を逆向きにたどる
2015/10/1
5
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラムスライスの計算手法 (例)
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: }
call
制御依存関係
制御依存関係
28 データ依存関係
11
3
3: float absolute(float x)
a b c
b c
x
4:5:{ if (x <a 0)
{
5:
if (x =
{b* +x;c; 5
16
30
6: sum
x<=
-1
16:
a0)+
sum
6:
x
=
-1
*
x;
7: xx =
} (float)sum
17:
/ 3.0;x
sum
x
7:
}
31
6 return
8:
return x; 17
9: }
x
x
27ave(int18
8 c)
11: float
a,int b,int
x
12: {
18:
x = absolute(x);
19
: DD
スライス基準(30,x)
20: }
: CD
2015/10/1
6
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
静的スライス
全ての起こりうる実行系列について解析
対象: ソースコード
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);
2015/10/1
7
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
動的スライス
ある特定の入力データにおける
実行系列について解析
- 入力が 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);
2015/10/1
8
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
Dependence Cache(DC)スライス
データ依存関係解析: 動的
制御依存関係解析: 静的
配列の各要素を区別
ポインタの指すメモリを区別
解析コストの増加を抑える
ことができる
1:
2:
3:
4:
5:
6:
a[0] = 0;
a[1] = 3;
scanf("%d",&b);
a[b] = 2;
c = a[0]+4;
printf("%d", c);
1:
2:
3:
4:
5:
a = 0;
b = 2;
c = &a;
*c = 4+b;
printf("%d", a);
2015/10/1
9
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
動的データ依存関係解析 (1/2)
データ依存関係
文sで定義された変数vが文tで使用されたとき
vに関するsからtへのデータ依存関係が存在
動的解析
文tの実行の際に，使用される変数vが
どの文(s)で定義されたのか
変数vが文sで定義されたことを保存する
2015/10/1
10
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
動的データ依存関係解析 (2/2)
キャッシュの内容
各変数が最後に定義された文の文番号
キャッシュの更新/データ依存辺の追加
ある文である変数が
定義される
– 文番号をキャッシュに保存
使用される
– 最後に定義された文をキャッシュから取得
– 取得した文から現在の文に依存辺を引く
2015/10/1
11
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
配列の各要素を区別した解析
入力が 0 の場合
b
a[0]
c
1:
2:
3:
4:
5:
6:
a[0] = 0;
a[1] = 3;
scanf("%d", &b);
a[b] = 2;
c = a[0] + 4;
printf("%d", c);
キャッシュ
キャッシュ
a[0]
cc
a[0] a[1]
a[1] bb
1-4
4
2-23-35-51-
2015/10/1
12
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
各スライス手法の比較
DC
静的
動的
DD/CD
CD
静的解析
DD
DD/CD
動的解析
依存グラフのプログラムプログラム
実行系列
節点
の各文
の各文
スライスサイズ: 静的  DC  動的
解析時間: 静的 > DC > 動的
実行時間: 動的 > DC > 静的
2015/10/1
13
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
スライス対象: Java
近年ソフトウェア開発環境で多く利用される
Javaにおける実行時決定要素
配列の添字
オブジェクトへの参照
動的束縛
例外
並列処理
静的解析では限界がある
2015/10/1
14
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
提案手法
オブジェクト指向言語に対応したDCスライス
データ依存関係解析: 動的
制御依存関係解析: 静的
メソッド間の制御依存関係解析: 動的
オブジェクトへの参照の解析
動的束縛の解析
動的スライスと比較して実行時解析のコストの増加を抑
えることができる
2015/10/1
15
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
オブジェクト指向言語への対応
各メンバ変数のキャッシュを
その変数が属するクラス内に保持する
クラスcのメンバ変数vのキャッシュ
クラスcのCache型メンバ変数“vCache”
オブジェクトごとにキャッシュを保持する
オブジェクトごとの解析
キャッシュ管理の単純化
2015/10/1
16
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
メソッド間の制御依存関係解析
オブジェクト
データとそれを操作するメソッドの組み合わせ
カプセル化
データへのアクセスはメソッドを通して行う
Javaの動的束縛
実行中のオブジェクトのクラスに基づき適切なオーバーライドメソッ
ドを選択する
動的なメソッド間の制御依存関係解析
2015/10/1
17
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
動的束縛に関する問題の解決
動的解析により，呼び出すメソッドを一意に決定で
きる
1
クラス C
int a; X b;
1:
2:
3:
4:
5:
6:
read(a);
if(a<0)
b = new X();
else
b = new Y();
b.m(a);
a
クラス X
11: m(int i) {
12: print(“X”, i);
13: }
クラス Y extends X
21: m(int i) {
22: print(“Y”, i);
23: }
2
3
5
b
11
i
12
b
6
a
a
21
i
22
2015/10/1
18
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
実装 (1/2)
インタプリタ方式
インタプリタが実行，解析を行う
あらゆる実行時情報を取得可能
実現に大きな手間がかかる
実行速度が遅い
プリプロセッサ方式
ソースにそれ自身を解析する命令を付加する
実現が比較的容易
JVMを選択可能 (JITによる高速実行)
2015/10/1
19
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
実装 (2/2)
ソース
プリプロセッサ
スライス基準
コンパイラ
UI
静的解析
ソース＋
解析命令
バイトコード＋
解析コード
スライサ
Java
Virtual Machine
PDG
スライス
動的解析
2015/10/1
20
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
解析命令の付加
1
2
3
4
5
:
:
:
:
:
int a = 10;
int b = 20;
int c;
c = a + b;
println(c);
変換
ある文である変数が
定義される(def): 文番号を保存
使用される(ref): 最後に定義され
た文から依存辺を引く
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);
2015/10/1
21
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
まとめ
Javaプログラムスライス手法を提案
動的なデータ依存関係解析
動的なメソッド間制御依存関係解析
実行時決定要素の詳細な解析
オブジェクトを区別した解析
動的束縛に関する問題の解決
2015/10/1
22
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
今後の課題
提案手法の実装
提案手法の実験的評価
スライスサイズ
実行時使用メモリ
実行時間
並列処理への対応
例外処理への対応
2015/10/1
23
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
各スライス手法の比較
P1
P2
P3
スライスサイズ (行)
DC
静的
動的
20.7 15.0
4.7
182 15.7
5.3
187
61
7.7
P1: カレンダー表示 (88行)
P2: 酒屋問題 (387行)
P3: 拡張酒屋問題 (941行)
P1
静的解析時間 (ms)
DC
静的
動的
14
4.5
N/A
実行時間 (ms)
DC
静的
動的
52
55
184
P2
P3
219
710
19
48
N/A
N/A
(Celeron-450MHz, 128MB)
P1
P2
P3
46
49 4,649
4,869 5,274 38,969
2015/10/1
24
ソフトウェアサイエンス研究会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University

Download Report