静的情報と動的情報を用いた プログラムスライス計算法

Presentation on theme: "静的情報と動的情報を用いた プログラムスライス計算法"— Presentation transcript:

1 静的情報と動的情報を用いた プログラムスライス計算法
芦田佳行 井上研究室

2 発表内容 プログラムスライス 静的情報と動的情報を併用するスライス計算法の提案 各手法の評価，考察 動的スライス 静的スライス
Call-Markスライス Statement-Markスライス D3スライス 部分解析法 各手法の評価，考察

3 研究の背景 ソフトウェアシステムの巨大化，複雑化 テスト工程のコストの増大(開発コストの50～80%) テスト(フォールトの検出)
デバッグ(フォールト位置の特定，修正) フォールト位置の特定を効率良く行うための一手法 として，プログラムスライスが提案されている．

4 プログラムスライス ある文のある変数(スライス基準)の値に影響を与える文の集合 誤った値の変数をスライシング 基準に指定する．
フォールトに関連の深い部分が スライスとして抽出される．

5 動的スライス 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else
制御依存関係(CD) a データ依存関係(DD) 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 入力がc=0の場合の実行系列 e7: writeln(d); e1: a:=3; e2: b:=2; e3: readln(c); e4: if c=0 then e5: d:=a e6: e:=b+a; e7: writeln(d); e8: writeln(e); e1: a:=3; e3: readln(c); e4: if c=0 then e5: d:=a d e b c a データ依存関係の説明 制御依存関係の説明 実行系列が長くなってしまう場合が多く，それに対応する節点を準備するのに多くのメモリが必要で，かつその解析に多くの時間を必要とする． この方法は，あまり現実的ではない． 9: writeln(d);

6 静的スライス 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else
8: e:=b+a; 10: writeln(e); 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 9: writeln(d); 特定のテストデータを考慮せず，ずべての実行系列についての可能性を考える． 配列やポインタの詳細な解析ができない． d スライスサイズの増加

7 本研究では，静的情報と動的情報の両方を用いた
研究の目的 コスト: 静的スライスに近づける． スライス結果: 動的スライスに近づける． 本研究では，静的情報と動的情報の両方を用いた いくつかのスライス抽出技法を提案する．

8 Statement-Mark (Call-Mark)スライス
文(関数呼び出し文)の実行履歴を用いて，実行されていない文をスライス結果から除外する． PDG 静的解析 グラフ探索 実行 文の 実行履歴 スライス基準

9 配列，ポインタ解析 配列やポインタの静的解析の限界 2: a[1]:=3; 3: readln(b); 4: c:=a[b]+4;
5: writeln(c); ポインタ 1: a:=0; 2: b:=2; 3: c:=&a; 4: *c:=4+b; 5: writeln(a); a a b 配列についてのみ説明． ポインタについても，同様な問題がある． ? c

10 D3スライスの特徴 データ依存関係: 動的に解析 制御依存関係: 静的に解析 依存グラフの節点: ソースプログラムの各文
配列やポインタ，構造体の詳しい解析 制御依存関係: 静的に解析 実行時のコスト削減 依存グラフの節点: ソースプログラムの各文 メモリ使用量の抑制

11 D3スライス PDG’ 制御依存 関係解析 依存辺 の追加 PDG データ 依存関係 実行 & 解析 グラフ探索 スライス基準

12 データ依存関係解析 1: a[0]:=0; 2: a[1]:=3; 3: readln(b); 4: a[b]:=2;
5: c:=a[0]+4; 6: writeln(c); 1: a[0]:=0; 各変数がどこで定義されたか 2: a[1]:=3; a[0] a[1] b c 3: readln(b); b e s4 s s e s4 s s3 s5 e s1 s s e s4 s s3 s5 e s1 s e s 4: a[b]:=2; a[0] 5: c:=a[0]+4; c 6: writeln(c);

13 各手法の違い

14 評価方法 本手法を，すでに試作しているスライシングツール (対象言語: Pascal)に実装し，有効性を確認する． 比較手法 静的スライス
動的スライス Call-Mark Statement-Mark D3スライス 計測項目 スライスサイズ 解析時間(静的解析) 実行時間(動的解析)

15 計測結果(1) スライスサイズ(行) P1: カレンダー表示プログラム(88行) P2: 酒屋問題(387行)

16 計測結果(2) 解析時間(静的解析)[ms] 実行時間(動的解析)[ms] (Celeronｰ450MHｚ with 128MB)

17 考察

18 まとめと今後の課題 静的情報と動的情報を併用するスライス計算法を提案し，評価した．
Statement-Markスライス D3スライス これらの手法を使い分けることで，効率良いフォールト位置の特定が期待できる． 新しいスライスツールへの本手法の適用 複数手法の使い分けの指針となるようなメトリクスの提案?

19 動的スライス(説明無し) 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a
6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 入力がc=0の場合の実行系列 e1: a:=3; e3: readln(c); e4: if c=0 then e5: d:=a e1: a:=3; e2: b:=2; e3: readln(c); e4: if c=0 then e5: d:=a e6: e:=b+a; e7: writeln(d); e8: writeln(e); e7: writeln(d); a d e b c 9: writeln(d);

20 静的スライス(説明無し) 9: writeln(d); 1: a:=3; 2: b:=2; 3: readln(c);
4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 10: writeln(e);

21 動的スライス(説明あり) 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a
6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); 入力がc=0の場合の実行系列 e7: writeln(d); e1: a:=3; e2: b:=2; e3: readln(c); e4: if c=0 then e5: d:=a e6: e:=b+a; e7: writeln(d); e8: writeln(e); e1: a:=3; e3: readln(c); e4: if c=0 then e5: d:=a d e b c a a 9: writeln(d);

22 静的スライス(説明あり) 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a
6: else 7: d:=a+1; 8: e:=b+a; 10: writeln(e); 9: writeln(d); 1: a:=3; 2: b:=2; 3: readln(c); 4: if c=0 then 5: d:=a 6: else 7: d:=a+1; 8: e:=b+a; 9: writeln(d); 10: writeln(e); d

23 Call-Markスライス (1) ソースプログラムを静的に解析し，PDGを作る．
(2) 入力データを与えてプログラムを実行し，各関数呼び出し文が実行されたかどうか調べる． (3) 実行されていない文，その文につながる辺をPDGから取り除く． (4) スライシング基準からスライスを計算する．

24 Statement-Markスライス (1) ソースプログラムを静的に解析し，PDGを作る．
(2) 入力データを与えてプログラムを実行し，各文が実行されたかどうか調べる． (3) 実行されていない文，その文につながる辺をPDGから取り除く． (4) スライシング基準からスライスを計算する．

25 発表内容 プログラムスライス 静的情報と動的情報を併用するスライス計算法の提案 各手法の評価，考察 静的スライス 動的スライス
Statement-Markスライス D3スライス 各手法の評価，考察