動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案 大阪大学大学院情報科学研究科 松村 俊徳, 石尾 隆, 井上 克郎

背景 ソフトウェア開発においてデバッグ作業により，プログラムに対して変更が加えられる デバッグ作業は複数のタスクから構成され，それぞれのタスクを支援する様々な技術が提案されている バグの発見 – testing 原因の特定 – fault localization バグの修正 – bug fix バグ修正の影響分析 – change impact analysis バグ修正の影響分析を対象としている

バグ修正の影響分析 開発者の関心事 開発者のバグ修正作業 実際にデバッグの前後でプログラムの実行がどう変わったのか? プログラムを修正する 実行に失敗していたテストが成功するようになり，バグの修正が完了したことを確認する 開発者の関心事 実際にデバッグの前後でプログラムの実行がどう変わったのか? もしかするとデバッグ作業に伴うプログラムの変更で，意図しない動作の変更が起きていないか？ バグ修正作業において，開発者はプログラムを修正し， 開発者の関心事として ～といったことが挙げられます． 本研究では，このような関心事に答える事を目標とします．

Change Impact Analysis プログラムに変更を加えたことにより影響がでる可能性のある部分を求める技術 代表的な手法 Call Graph メソッド呼び出し関係をもとに計算する．コストは小さいが不正確である Static Slicing 静的依存関係をもとに保守的な計算をする．他2つと比べて大きな出力結果となる Dynamic Slicing 動的依存関係をもとに計算する．実行に依存するため，安全性は保証していない

2つの実行の比較 Differential Slicing Relative Debugging 同一プログラムの２つの実行を比較する 異なる計算結果となった原因を過去に遡る方向に依存関係をたどることで求める Relative Debugging 異なる2つのプログラムを同時に実行し，比較しつつ作業が行えるデバッガである バグの修正により実際にどのような動作の変化があったかを求める手法ではない 3:00 本研究では，バグ修正前後の実行を比べており， 2つの実行を比べる研究もされていおり，

提案 バグ修正前後の動的スライスを比較することで，プログラムの動作の差分を検出する手法を提案する 動的プログラム依存グラフがプログラムの動作を表現していると考える 修正対象を基準としたフォワードスライスを計算し比較することで，変更により実際に起きた影響を求める データの流れと実行制御を

サンプルプログラム int foo(int op1, int op2){ return op1 + op2; } 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; }

フォワードスライス 修正前 修正後 return if(foo) i = 0 print(i) return if(foo) i = 1 print(i)はiの定義元が異なっている バグ修正の影響を受けている

フォワードスライスの比較方法 単純なグラフ比較 頂点の集合比較 グラフ上の経路の比較 ２つのフォワードスライスの差分を検出可能 　フォワードスライスでは命令の1回の実行が1頂点となり，グラフが巨大であるため比較のコストが高い 頂点の集合比較 グラフの比較に比べコストが低い 　命令が実行されたか否かしか判断しないため，検出漏れが多くなる グラフ上の経路の比較 グラフを経路という形に分解して比較する 　フォワードスライスでは，分岐や合流が多数存在するため，経路数が組み合わせ爆発を起こす サンプルコードを記述

フォワードスライスの比較方法 フォワードスライス内の各頂点に対して，その頂点に到達する経路上に存在する頂点集合を求める 経路という情報を，頂点集合に変換し比較を行う 情報としては削る形となるが，組み合わせ爆発を考慮しなくてすむ 2つのフォワードスライス間で片方にのみ固有な頂点を差分として検出する 頂点集合の等しい頂点が，もう一方のフォワードスライスに存在しない場合に固有な頂点であるとする サンプルコードを記述

フォワードスライス 修正前 修正後 return if(foo) i = 0 print(i) return if(foo) i = 1 {} {if(foo)} {if(foo), i = 0} 修正後 return if(foo) i = 1 print(i) 7:00 以上が手法の説明になります． {} {if(foo)} {if(foo), i = 1}

提案手法の手順 実行の記録 動的プログラム依存グラフの計算 動的フォワードスライスの計算 動的フォワードスライスの比較

手順1：実行の記録 プログラム P1, P2 (バグ修正の前, 後) 実行記録命令 埋め込みツール プログラム P1’, P2’ 実行 トレース1 実行 トレース2 Execute P’ on a JVM

手順2：動的プログラム依存グラフの計算 依存関係はJavaバイトコード単位で求める 依存辺の集合を求め，ファイルに書き出す 実行 トレース1 実行 トレース2 実行再現ツール 動的プログラム依存グラフ 依存関係はJavaバイトコード単位で求める 依存辺の集合を求め，ファイルに書き出す メモリ上に保持しておくのには限界がある

手順3：動的フォワードスライスの計算 バグ修正によって変更されたメソッドを基準としてフォワードスライスを計算する 動的プログラム依存グラフ バグ修正によって変更されたメソッドを基準としてフォワードスライスを計算する 対象となるメソッド内部の依存辺はスライス内に含めない

手順4：動的フォワードスライスの比較 固有な頂点の抽出 フォワードスライス 固有な頂点 トポロジカルソートを行い，頂点を根から順にソートする ソート順に頂点を訪問し，子ノードに対して経路上の頂点集合情報を伝播させていき，各頂点に対する経路上の頂点集合を計算する 2つのフォワードスライス間に固有な頂点を差分として検出する 9:00 以上が手順の説明となります．

経路上の頂点集合情報の伝播 ２ ３ ４ {} {} {} １ 5 6 { } {} {}

経路上の頂点集合情報の伝播 ２ ３ ４ {1} {1,2,5} {1,2,3,5} １ 5 6 { } {1} {1,5}

経路上の頂点集合情報の伝播 ２ ３ ４ {} {} {} １ 5 6 { } {} {} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 ２ ３ ４ {1} {} {} １ 5 6 { } {1} {} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 ２ ３ ４ {1} {1,5} {} １ 5 6 { } {1} {1,5} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 ２ ３ ４ {1} {1,5} {} １ 5 6 { } {1} {1,5} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 ソート順：１，５，６，２，３，４ ２ ３ ４ １ 5 6 {1} {1,2,5} {} { } {1} {1,5} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 ソート順：１，５，６，２，３，４ ２ ３ ４ １ 5 6 {1} {1,2,5} {1,2,3,5} { } {1,5} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 ソート順：１，５，６，２，３，４ ２ ３ ４ １ 5 6 {1} {1,2,5} {1,2,3,5} { } {1,5} ソート順：１，５，６，２，３，４

経路上の頂点集合情報の伝播 計算時間：𝑂( 𝑉 ∗|𝐸| ) ２ ３ ４ １ 5 6 {1} {1,2,5} {1,2,3,5} { } 計算時間：𝑂( 𝑉 ∗|𝐸| ) ２ ３ ４ {1} {1,2,5} {1,2,3,5} １ 5 6 { } {1} {1,5}

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

計算時間 # 実行の記録 [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,231.148 / 1,909.242 10 104 / 107 2,906 / 2,795 427 / 416 0.616 / 0.400 メモリが足りなかった理由

フォワードスライス # 頂点 [個] 辺 [本] 経路 [通り] 固有な頂点 [個] 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 実行の観測対象外に関連するバグであったために

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

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

#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")); ・ 修正後は以降も実行される

まとめと今後の課題 バグ修正前後の動的スライスを比較することで，プログラムの動作の差分を検出する手法を提案した 本手法を適用し，差分が検出されれば開発者がそれを検証することができ，検出されなければ違いがなかったことが保証される 今後の課題として，計算の高速化やスケーラビリティの向上などが挙げられる