動的スライスを用いた バグ修正前後の実行系列の比較

Presentation on theme: "動的スライスを用いた バグ修正前後の実行系列の比較"— Presentation transcript:

1 動的スライスを用いた バグ修正前後の実行系列の比較
石尾 隆 大阪大学 ※本スライドは 松村 俊徳（2016年3月修了），石尾，井上： 動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案 SIGSE 2016年3月の発表をもとに構成しています

2 背景 デバッグ作業によってプログラムを修正したとき，「他に影響がない修正ができた」ことを確認したい デバッグ作業の手順
テストによるバグの発見 特定のテスト実行の分析による原因の特定 バグの修正 バグ修正結果のテストによる確認 回帰テストの実施による影響の有無の確認

3 アプローチ バグ修正の前後のテスト実行を比較して，その変化を検出する テスト自体によって確認できること：
バグに対応するテストが通るようになる バグに関係ないテストの結果に変化がない 本手法で追加で確認できること： その修正に起因する変数の値の計算手順の変化の有無 その修正に起因する計算途中での条件分岐の変化の有無 　バグ修正に起因しない変化は許容する

4 変化は観測しやすい，変化がないことは確認しにくい
カバレッジで一部の変化は検出可能 今まで実行されなかった命令が実行されるようになる，など 一方で，カバレッジに変化がないから影響がなかった，というのは根拠に乏しい 「影響がない」といえるくらい強い基準が必要 厳しくメモリの状態を比較すると，実行ごとに変化するデータ（現在日時など）に反応してしまう

5 既存研究： 影響波及解析 プログラムに変更を加えたことにより影響がでる可能性のある部分を求める技術は存在する 代表的な手法
Call Graph 修正したメソッドを呼び出しているメソッドはテストが必要である．コストは小さいが不正確なことも． Static Slicing 修正したメソッドの実行結果を使う可能性のあるメソッドはテストが必要である．範囲が広すぎて使い物にならないことがある Dynamic Slicing 修正したメソッドの実行結果を使っていたメソッドはテストが必要である．テスト依存なので少しあやしい．

6 既存研究：デバッグ用の実行の比較 Differential Slicing Relative Debugging
同一プログラムの２つの実行（問題が起きる場合と起きない場合）を比較する 異なる計算結果となった原因を過去に遡る方向に依存関係をたどることで求める 修正されたプログラムの実行の比較ではない Relative Debugging 2つの似ているプログラムを同時に実行して，メモリ状態に差が起きた時点で実行を一時停止するデバッガ 差異があった場所で停止することはできるが，差異の情報を整理はしてくれない

7 本研究の提案 バグ修正前後の動的スライスを比較し，Java プログラムの動作の差分を検出する 動的スライス：
　命令１回ずつの実行の関係を表現するグラフ 命令間でデータが流れた 条件分岐によって実行することを決定した 修正されたメソッドを基点としたスライスが異なれば，実際に影響を受けている 変数の値が変わっただけでは検出しない それによって経路が変わったら検出する

8 サンプルプログラム boolean foo(int i, int i2){ return i1 < i2; } int i;
If( foo(1,2) ){ i = 0; }else{ i = 1; } System.out.print(i); 変更 boolean foo(int i, int i2){ return i1 > i2; }

9 フォワードスライス 修正前 修正後 return if(foo) i = 0 print(i) return if(foo) i = 1
命令１回ずつの実行を，データフローと制御条件で連結したもの 修正前 データフロー 条件分岐 データフロー return if(foo) i = 0 print(i) 修正後 return if(foo) i = 1 print(i) i=1は今まで実行されていなかった print(i)はiの定義元が異なっている バグ修正の影響を受けている

10 フォワードスライスの比較方法 単純なグラフ比較 頂点や辺の集合比較 グラフ上の経路の比較 ２つのフォワードスライスの差分を検出可能
　グラフが巨大になると計算コストが高くつく 頂点や辺の集合比較 カバレッジ計算（命令網羅率，分岐網羅率）に相当 グラフの比較に比べコストは低いが，検出漏れが多くなる グラフ上の経路の比較 グラフを経路という形に分解して比較する 　フォワードスライスでは，分岐や合流が多数存在するため，経路数が組み合わせ爆発を起こす

11 アプローチ： 経路上の頂点集合の比較 修正前 修正後 return if(foo) i = 0 print(i) return
メソッドの戻り値が通過する経路上の頂点集合に差がある＝動作が異なる 修正前 return if(foo) i = 0 print(i) {} {if(foo)} {if(foo), i = 0} 修正後 return if(foo) i = 1 print(i) {} {if(foo)} {if(foo), i = 1}

12 試作した実装の計算手順 実行 トレース1 実行 トレース2 JUnit 実行 実行再現ツール 実行記録命令 プログラム P1, P2
（バグ修正前，後） 実行記録命令 埋め込みツール プログラム ＋実行記録命令 実行 トレース1 実行 トレース2 動的プログラム依存グラフ 実行再現ツール

13 適用実験 実験対象 実験環境 バグ修正データセットDefects4jに収録されているApache Commons Langのバグ10個を対象
バグ修正前後のバージョンでの，全てのテストケースを実行し差分を検出 ライブラリは実行の観測から除外 実験環境 OS：Ubuntu14.04 CPU： Intel Xeon 2.90GHz メモリ：256GB

14 計算時間 # 実行の記録 [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 / 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, / 1, 10 104 / 107 2,906 / 2,795 427 / 416 0.616 / 0.400

15 フォワードスライスの比較結果 # 頂点 [個] 辺 [本] 経路 [通り] 固有な頂点 [個] 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 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 7 4,603 / 4,812 8,002 / 8,373 39 / 73 8 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 10 631,407 / 631,407 131,313 / 131,313

16 #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); 桁数で作る数値の型を判断

17 #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);

18 #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(0x ), NumberUtils.createNumber("0x ")); assertEquals(Integer.valueOf(0x7FFFFFFF), NumberUtils.createNumber("0x7FFFFFFF")); assertEquals(Long.valueOf(0x L), NumberUtils.createNumber("0x ")); assertEquals(Long.valueOf(0xFFFFFFFFL), NumberUtils.createNumber("0xFFFFFFFF")); // Leading zero tests assertEquals(Integer.valueOf(0x ), NumberUtils.createNumber("0x ")); assertEquals(Integer.valueOf(0x7FFFFFFF), NumberUtils.createNumber("0x007FFFFFFF")); assertEquals(Long.valueOf(0x L), NumberUtils.createNumber("0x ")); assertEquals(Long.valueOf(0xFFFFFFFFL), NumberUtils.createNumber("0x00FFFFFFFF")); ・ 修正後は以降も実行される このメソッドは他の機能の実行でも利用されているが，それらのデータフロー，条件分岐には変化なし

19 まとめと今後の課題 バグ修正前後のプログラムの実行を比較する手法を試作した 今後の課題 修正によって影響された範囲だけを差分として見る
実行した日時の違いなど，異なる要因による変化と区別できる 差分が検出されれば，正しい影響か開発者が確認 検出されなければ違いがなかったと言えそう 今後の課題 判定の高速化，厳密化：現在取り組み中 開発者に有益な情報に絞った結果の表示：修正によって条件分岐が変化した if 文のリストの抽出など? 「予想通り影響を受けた・受けていない」といえるものでないと開発者が確認できない