動的スライスを用いたバグ修正前後の
実行系列の差分検出手法の提案
大阪大学大学院情報科学研究科
松村 俊徳, 石尾 隆, 井上 克郎
1
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
背景
ソフトウェア開発においてデバッグ作業によ
り，プログラムに対して変更が加えられる
デバッグ作業は複数のタスクから構成され，
それぞれのタスクを支援する様々な技術が提
案されている
バグの発見 – testing
原因の特定 – fault localization
バグの修正 – bug fix
バグ修正の影響分析 – change impact analysis
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
バグ修正の影響分析
開発者のバグ修正作業
プログラムを修正する
実行に失敗していたテストが成功するようになり，バグ
の修正が完了したことを確認する
開発者の関心事
実際にデバッグの前後でプログラムの実行がどう
変わったのか?
もしかするとデバッグ作業に伴うプログラムの変
更で，意図しない動作の変更が起きていないか？
3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
Change Impact Analysis
プログラムに変更を加えたことにより影響がでる
可能性のある部分を求める技術
代表的な手法
Call Graph
メソッド呼び出し関係をもとに計算する．コストは小さいが不正
確である
Static Slicing
静的依存関係をもとに保守的な計算をする．他2つと比べて大き
な出力結果となる
Dynamic Slicing
動的依存関係をもとに計算する．実行に依存するため，安全性は
保証していない
4
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2つの実行の比較
Differential Slicing
同一プログラムの２つの実行を比較する
異なる計算結果となった原因を過去に遡る方向に依存関
係をたどることで求める
Relative Debugging
異なる2つのプログラムを同時に実行し，比較しつつ作業
が行えるデバッガである
バグの修正により実際にどのような動作の変化があっ
たかを求める手法ではない
5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
提案
バグ修正前後の動的スライスを比較すること
で，プログラムの動作の差分を検出する手法
を提案する
動的プログラム依存グラフがプログラムの動作を
表現していると考える
修正対象を基準としたフォワードスライスを計算
し比較することで，変更により実際に起きた影響
を求める
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
サンプルプログラム
int i;
If( foo(1,2) > 0){
i = 0;
}else{
i = 1;
}
System.out.println(i);
int foo(int op1, int op2){
return op1 + op2;
}
変更
int foo(int op1, int op2){
return op1 - op2;
}
7
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
フォワードスライス
修正前
return
if(foo)
i=0
print(i)
if(foo)
i=1
print(i)
修正後
return
i=1は今まで実行されていなかった
print(i)はiの定義元が異なっている
バグ修正の影響を受けている
8
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
フォワードスライスの比較方法
単純なグラフ比較
２つのフォワードスライスの差分を検出可能
フォワードスライスでは命令の1回の実行が1頂点となり，グラフが
巨大であるため比較のコストが高い
頂点の集合比較
グラフの比較に比べコストが低い
命令が実行されたか否かしか判断しないため，検出漏れが多くなる
グラフ上の経路の比較
グラフを経路という形に分解して比較する
フォワードスライスでは，分岐や合流が多数存在するため，経路数が
組み合わせ爆発を起こす
9
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
フォワードスライスの比較方法
フォワードスライス内の各頂点に対して，その頂点に到
達する経路上に存在する頂点集合を求める
経路という情報を，頂点集合に変換し比較を行う
情報としては削る形となるが，組み合わせ爆発を考慮しなくて
すむ
2つのフォワードスライス間で片方にのみ固有な頂点を
差分として検出する
頂点集合の等しい頂点が，もう一方のフォワードスライスに存
在しない場合に固有な頂点であるとする
10
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
フォワードスライス
修正前
return
if(foo)
i=0
print(i)
{}
{if(foo)}
{if(foo), i = 0}
if(foo)
i=1
print(i)
{}
{if(foo)}
{if(foo), i = 1}
修正後
return
11
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
提案手法の手順
1. 実行の記録
2. 動的プログラム依存グラフの計算
3. 動的フォワードスライスの計算
4. 動的フォワードスライスの比較
12
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
手順1：実行の記録
プログラム P1, P2
(バグ修正の前, 後)
実行
トレース1
実行
トレース2
実行記録命令
埋め込みツール
プログラム P1’, P2’
Execute P’
on a JVM
13
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
手順2：動的プログラム依存グラフの計算
実行
トレース1
実行
トレース2
実行再現ツール
動的プログラム依存グラフ
依存関係はJavaバイトコード単位で求める
依存辺の集合を求め，ファイルに書き出す
メモリ上に保持しておくのには限界がある
14
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
手順3：動的フォワードスライスの計算
フォワードスライス
の計算
動的プログラム依存グラフ
フォワードスライス
バグ修正によって変更されたメソッドを基準
としてフォワードスライスを計算する
対象となるメソッド内部の依存辺はスライス
内に含めない
15
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
手順4：動的フォワードスライスの比較
固有な頂点の抽出
フォワードスライス
固有な頂点
トポロジカルソートを行い，頂点を根から順にソートする
ソート順に頂点を訪問し，子ノードに対して経路上の頂点集
合情報を伝播させていき，各頂点に対する経路上の頂点集合
を計算する
2つのフォワードスライス間に固有な頂点を差分として検出
する
16
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{}
３
４
{}
{}
１
5
6
{}
{}
{}
17
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,2,5}
{1,2,3,5}
１
5
6
{}
{1}
{1,5}
18
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{}
３
４
{}
{}
１
5
6
{}
{}
{}
ソート順：１，５，６，２，３，４
19
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{}
{}
１
5
6
{}
{1}
{}
ソート順：１，５，６，２，３，４
20
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,5}
{}
１
5
6
{}
{1}
{1,5}
ソート順：１，５，６，２，３，４
21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,5}
{}
１
5
6
{}
{1}
{1,5}
ソート順：１，５，６，２，３，４
22
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,2,5}
{}
１
5
6
{}
{1}
{1,5}
ソート順：１，５，６，２，３，４
23
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,2,5}
{1,2,3,5}
１
5
6
{}
{1}
{1,5}
ソート順：１，５，６，２，３，４
24
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,2,5}
{1,2,3,5}
１
5
6
{}
{1}
{1,5}
ソート順：１，５，６，２，３，４
25
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
経路上の頂点集合情報の伝播
２
{1}
３
４
{1,2,5}
{1,2,3,5}
１
5
6
{}
{1}
{1,5}
計算時間：𝑂( 𝑉 ∗ |𝐸| )
26
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
適用実験
実験対象
バグ修正データセットDefects4jに収録されてい
るApache Commons Langのバグ10個を対象
バグ修正前後のバージョンでの，全てのテスト
ケースを実行し差分を検出
ライブラリは実行の観測から除外
実験環境
OS：Ubuntu14.04
CPU： Intel Xeon 2.90GHz
メモリ：256G
27
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
計算時間
#
実行の記録 [s]
PDGの計算 [s]
スライス計算 [s]
スライス比較 [s]
1
185 / 187
5,507 / 5,261
884 / 760
0.019 / 0.015
2
184 / 185
5,429 / 5,374
763 / 762
0.004 / 0.001
3
186 / 184
5,293 / 5,174
796 / 662
0.014 / 0.010
4
187 / 191
5,482 / 5,372
1,189 / 1637
N/A
5
186 / 185
5,274 / 5,286
1,234 / 1,224
0.003 / 0.001
6
189 / 188
5,320 / 5,171
2,546 / 2,916
NA
7
189 / 185
5,470 / 5,439
1,231 / 1,203
0.022 / 0.012
8
91 / 93
2,601 / 2,565
366 / 350
0.001 / 0.001
9
104 / 104
2,932 / 2,895
1,272 / 1918
1,231.148 /
1,909.242
10
104 / 107
2,906 / 2,795
427 / 416
0.616 / 0.400
28
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
フォワードスライス
#
頂点 [個]
辺 [本]
経路 [通り]
固有な頂点 [個]
1
6,260 / 6,996
11,024 / 12,321
3.57×10^18 /
3.57×10^18
0 / 42
2
1,298 / 1,326
1,364 / 1,404
319 / 337
1/7
3
6,015 / 6,078
10,591 / 10,705
3.57×10^18/
3.57×10^18
0/3
4
51,491,332 /
51,491,332
97,249,586 /
97,249,586
3.57×10^18/
3.57×10^18
N/A
5
329 / 396
389 / 462
136 / 167
0 / 19
6
83,584,442 /
83,586,850
156,272,662 /
156,277,095
2.01×10^18/
2.06×10^18
N/A
7
4,603 / 4,812
8,002 / 8,373
3.57×10^18/
3.57×10^18
39 / 73
8
0/0
0/0
0/0
0/0
9
68,481,669 /
68,481,483
119,895,430 /
119,895,112
5.32×10^18/
5.32×10^18
2/0
631,407 / 631,407 631,407 / 631,407
131,313 / 131,313
10
0 / 029
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
#1：修正前コード
文字列を数値に変換するメソッド
public static Number createNumber(final String str) throws NumberFormatException {
・
・
・
if (pfxLen > 0) { // we have a hex number
final int hexDigits = str.length() - pfxLen;
if (hexDigits > 16) { // too many for Long
return createBigInteger(str);
}
if (hexDigits > 8) { // too many for an int
return createLong(str);
}
return createInteger(str);
}
桁数で作る数値の型を判断
30
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
#1：修正後コード
public static Number createNumber(final String str) throws NumberFormatException {
・
・
・
if (pfxLen > 0) { // we have a hex number
char firstSigDigit = 0; // strip leading zeroes
for(int i = pfxLen; i < str.length(); i++) {
firstSigDigit = str.charAt(i);
if (firstSigDigit == '0') { // count leading zeroes
pfxLen++;
} else {
break;
}
}
final int hexDigits = str.length() - pfxLen;
if (hexDigits > 16 || (hexDigits == 16 && firstSigDigit > '7')) { // too many for Long
return createBigInteger(str);
}
if (hexDigits > 8 || (hexDigits == 8 && firstSigDigit > '7')) { // too many for an int
return createLong(str);
}
return createInteger(str);
}
31
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
#1:検出された差分
修正前はここで失敗し終了
修正メソッド
public void TestLang747() {
assertEquals(Integer.valueOf(0x8000),
NumberUtils.createNumber("0x8000"));
assertEquals(Integer.valueOf(0x80000), NumberUtils.createNumber("0x80000"));
assertEquals(Integer.valueOf(0x800000), NumberUtils.createNumber("0x800000"));
assertEquals(Integer.valueOf(0x8000000), NumberUtils.createNumber("0x8000000"));
assertEquals(Integer.valueOf(0x7FFFFFFF), NumberUtils.createNumber("0x7FFFFFFF"));
assertEquals(Long.valueOf(0x80000000L), NumberUtils.createNumber("0x80000000"));
assertEquals(Long.valueOf(0xFFFFFFFFL), NumberUtils.createNumber("0xFFFFFFFF"));
修正後は以降も実行される
// Leading zero tests
assertEquals(Integer.valueOf(0x8000000), NumberUtils.createNumber("0x08000000"));
assertEquals(Integer.valueOf(0x7FFFFFFF), NumberUtils.createNumber("0x007FFFFFFF"));
assertEquals(Long.valueOf(0x80000000L), NumberUtils.createNumber("0x080000000"));
assertEquals(Long.valueOf(0xFFFFFFFFL), NumberUtils.createNumber("0x00FFFFFFFF"));
・
・
・
32
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
まとめと今後の課題
バグ修正前後の動的スライスを比較すること
で，プログラムの動作の差分を検出する手法
を提案した
本手法を適用し，差分が検出されれば開発者
がそれを検証することができ，検出されなけ
れば違いがなかったことが保証される
今後の課題として，計算の高速化やスケーラ
ビリティの向上などが挙げられる
33
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
© Copyright 2024 ExpyDoc
