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

静的情報と動的情報を用いた
Javaプログラムスライス計算法
広瀬航也
井上研究室
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
発表内容
プログラムスライス
静的スライス
動的スライス
Dependence Cache スライス
Javaプログラムスライス手法の提案
適用例
提案手法の実装
評価
まとめと今後の課題
2015/10/1
2
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
背景
ソフトウェアの大規模化，複雑化
テスト工程のコストの増大
テスト (フォールトの検出)
デバッグ (フォールト位置の特定，修正)
フォールト位置の特定を効率よく行う一手法
プログラムスライス
2015/10/1
3
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラムスライス
ある文のある変数(スライス基準)の値に
影響を与えうる文の集合
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に関係ある部分を抽出
2015/10/1
4
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
プログラムスライスの計算手法
1. 依存関係解析
データ依存関係 (DD)
制御依存関係 (CD)
2.
PDG
制御依存関係
データ依存関係
制御依存関係
10:
a=
if
(a 1;
< 1){
10:
me(5);
1
5
2
CALL ……
RETURN a
…
b =me(int
b a;
= a; a)
プログラム依存グラフ(PDG)構築 20:20:void
{3 return;
7 6} 4
節点: 文，条件節を表す
辺: 節点間の依存関係を表す
3. グラフ探索
8
スライス基準に対応する節点
から辺を逆向きにたどる
2015/10/1
5
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
静的・動的スライス
静的スライス
ソースコードを対象に静的依存関係解析
全ての起こりうる実行を考慮した解析
スライスサイズが大きい
動的スライス
ある入力に関する実行系列を対象に動的依存関係解
析
実行時の解析コストが大きい
2015/10/1
6
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
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.
2015/10/1
7
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
動的データ依存関係解析
一時記憶: キャッシュ
各変数が最後に定義された文の文番号を保存
アルゴリズム
ある文である変数が定義される
文番号をキャッシュに保存
10: a = 1;
…
20: b = a;
ある文である変数が使用される
最後に定義された文をキャッシュから取得
取得した文から現在の文に依存辺を引く
a
キャッシュ
a
b ・・・
10
- ・・・
(文20実行時)
2015/10/1
8
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
各スライス手法の比較
静的スライス DCスライス動的スライス
DD解析
静的
動的
動的
CD解析
静的
静的
動的
依存グラフのプログラムプログラム
実行系列
節点
の各文
の各文
スライスサイズ: 静的  DC  動的
解析時間: 静的 > DC > 動的
実行時間: 動的 > DC > 静的
2015/10/1
9
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
スライス対象: オブジェクト指向言語
近年ソフトウェア開発環境で多く利用される
オブジェクト指向言語における実行時決定要素
配列の添字
オブジェクトへの参照
動的束縛
静的解析では限界がある
2015/10/1
10
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
提案手法
オブジェクト指向言語に対応したDCスライス
データ依存関係解析: 動的
制御依存関係解析: 静的
メソッド間の制御依存関係解析: 動的
オブジェクトへの参照の解析
動的束縛の解析
動的スライスと比較して実行時解析のコストの増加を抑
えることができる
2015/10/1
11
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
オブジェクト指向言語への対応 (DD解析)
各メンバ変数のキャッシュを
その変数が属するクラス内に保持する
クラスCのメンバ変数vのキャッシュ
クラスCのCache型メンバ変数として宣言
インスタンスごとにキャッシュを保持する
インスタンスを区別した解析
キャッシュ管理の単純化
2015/10/1
12
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
DD解析の適用例
P
P
P
int
1:
2:
3:
4:
5:
6:
7:
8:
9:
a;
b;
c;
d;
Cache aCache;=
Cache bCache;=
Cache cCache;=
Cache dCache;=
a = new P();
b = new P();
c = new Q();
a.data = 10;
b.data = 20;
c.data = 30;
d = a.data + c.data;
System.out.print(d);
System.out.print(b.data);
1
2
3
7
data = 10
data
dataCache
dataCache
=4
data = 20
dataCache
=5
class P
int data;
Cache dataCache;
class Q extends P
data = 30
data
dataCache
dataCache
=6
2015/10/1
13
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
オブジェクト指向言語への対応
(メソッド間CD解析)
オブジェクト
データとそれを操作するメソッドの組み合わせ
カプセル化
データへのアクセスはメソッドを通して行う
動的束縛
実行中のオブジェクトのクラスに基づき適切なオーバーライドメソッ
ドを選択する
動的なメソッド間の制御依存関係解析
呼び出されるメソッドを一意に決定
スライスサイズを小さくすることができる
2015/10/1
14
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
メソッド間CD解析の適用例
int a; Cache aCache;
P b; Cache bCache;
1:
2:
3:
4:
5:
6:
7:
a = read();
if (a > 0)
b = new P();
else
b = new Q();
b.data = 10;
a = b.calc();
class P
int data;
Cache dataCache;
int calc()
{
return data*2;
}
class Q extends P
int calc()
{
return data/2;
}
2015/10/1
15
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
本手法の実装
対象言語: Java
プリプロセッサとしての実装
スライス対象プログラムソースにそれ自身を解析する命
令を付加する
コンパイル, 実行
通常の実行と動的解析,PDG構築
開発言語: Java (JDK1.3.0_01, JavaCC2.0)
61クラス, 約10,000行(+12,000行[自動生成])
2015/10/1
16
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
評価
CGIプログラム
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]
通常実行解析付実行
138
582
消費メモリ [Kbyte]
通常実行解析付実行
478
645
(Celeron500MHz, 128MB, Windows98, Java1.3.0_01)
2015/10/1
17
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
まとめと今後の課題
まとめ
Javaプログラムスライス手法を提案
動的データ依存関係解析
動的メソッド間制御依存関係解析
スライスサイズの減少
今後の課題
例外処理への対応
マルチスレッドへの対応
2015/10/1
18
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
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() }
2015/10/1
19
2000年度修士論文発表会
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
20
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University
静的解析コスト
実行時間 [ms]
静的解析
命令付加
コンパイル
合計
通常 (スライス無し)
6,480
6,480
消費メモリ [Kbyte]
通常
372
本手法
3,207
本手法
6,100
540
6,760
13,400
ソース [行]
通常
223
本手法
1,754
2015/10/1
21
2000年度修士論文発表会
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
22
2000年度修士論文発表会
Software Engineering Research Group, Graduate School of Engineering Science, Osaka University

Download Report