眞鍋 雄貴，石尾 隆 大阪大学 ※論文リストでの表記順序と， 発表順序は異なりますのでご注意ください

Presentation on theme: "眞鍋 雄貴，石尾 隆 大阪大学 ※論文リストでの表記順序と， 発表順序は異なりますのでご注意ください"— Presentation transcript:

1 眞鍋 雄貴，石尾 隆 大阪大学 ※論文リストでの表記順序と， 発表順序は異なりますのでご注意ください
F05: Debugging 眞鍋 雄貴，石尾 隆 大阪大学 ※論文リストでの表記順序と， 発表順序は異なりますのでご注意ください

2 Partial Replay of Long-Running Applications
論文著者：Alvin Cheung, Armando Soloar-Lezama, and Samuel Madden (MIT CSAIL) 担当者：眞鍋雄貴（大阪大学）

3 背景・目的 プログラム実行の再現 プログラムを実行する時にログを記録し，そのログを用いてプログラムの実行を再現する
バグを起こしている正確な位置を調べるのに用いる 問題点 通常の実行時に大きなオーバーヘッドがかかる 非常に大きなログを生成してしまう Symbolic executionを用いてオーバーヘッドを削減する手法 ログをとる部分を減らす 足りない部分をSymbolic executionで実行することで補足し，オーバーヘッドを減らす 既存の手法は実行の最初から再現するため，現状のSymbolic executionエンジンでは何か月も動くようなプログラムの実行を再現できない ⇒実行の途中から部分的にリプレイできるようにする

4 主な貢献 プログラムの実行の途中から再現するプログラム実行の再現手法を提案 提案手法を用いたデバッガ（bbr）を実装した．
特徴 チェックポイントを設定 ある特定処理に設定したり，パラメータによる設定も行える ログは最後のチェックポイント到達時点から，プログラムが停止するまでの部分だけ残す チェックポイントに到達したとき，その時点の状態をスナップショットとして取る ログとスナップショットに基づき．Symbolic executionを用いて，チェックポイントから実行を再現する チェックポイント到達 プログラム停止 C C 時刻 通常の実行 ログを残す部分 スナップショット （チェックポイントを取れること，ログを残すのはチェックポイントから欠陥起こして止まるまでだけ残す，Symbolic executionで足りない部分を埋める） Symbolic execution による再現

5 記録するもの ログとして 条件分岐の値 分岐をどう進んだかが決定的に定まる アクセスされた配列のインデックス スナップショットとして
その時点でのスタック 開いているファイルの状態

6 評価 目的：オーバーヘッドとログの圧縮効果の測定
手法:6個のアプリケーションの実行を対象に，提案手法と他のログの取り方との間で実行時間とログサイズを比較する． 結果 オーバーヘッドは平均10%(1~33%)で他より小さい ログも他の手法より小さい その他の実験結果から，提案手法によりデバッグできることも示されている(4.2節) 図はCheung et.al., “Partial Replay of Long-Running Applications” p141より

7 Fault Localization for Data-Centric Programs
論文著者：Diptikalyan Saha, Mangala Gowri Nanda, Pangaj Dhoola, V. Krishna Nandivada, Vibha Shinha(IBM Research-India) , Satish Chandra(IBM T. J. Watson Research Ctr) 担当者：眞鍋雄貴（大阪大学）

8 背景・目的 目的：ABAPで記述されたデータ中心プログラムに対するプログラムエラーの高速な解決の支援
ABAP：SAP-ERPで使用される手続型＋宣言型言語 データ中心プログラム：データベースなどにある大規模なデータ集合を処理する プログラムスライスを用いた 欠陥の局所化 ある変数について正常な値と，異常な値をとる場合，それぞれの場合におけるスライスの差分に欠陥がある可能性が高い 本研究では動的スライスを用いる 図はSaha et.al., “Fault Localization for Data-Centric Programs” pp.157より

9 データ中心プログラム における問題 従来のfield-row sensitiveな動的スライスではデータベースの要素の追加削除が起こったとき，スライス基準に影響を与えうるかわからない キーの値によっては影響が出ないことがある ⇒キーとその値を考慮する データ中心プログラムでは，従来の実行系列に基づく差分検出では差が出ない場合がある ⇒実行時の振る舞いの差異を考慮する 図はSaha et.al., “Fault Localization for Data-Centric Programs” pp.158より

10 主な貢献 Key based Slicing 従来のfield-row sensitiveな動的スライスアルゴリズムに，key-value pairの集合を入力とする，データベースへの変更がkey-value pairと関係があるかを調べる処理が追加された動的スライスアルゴリズム Semantic Difference Corner-case Differences: 実行された各文について，特殊な状況が起こっているかどうか 特殊な状況は各文の種類に対して設定されている Mutation Differences: 正常系のスライスに影響を与えないよう，異常系のスライスが正常系のスライスと同じふるまいになるようにするにソースコードを変異させたとき，その変異部分 提案手法により，出力における行の欠落もわかる

11 評価 目的：Key based slicing, Semantic diff, 出力における行の欠落の評価
手法：提案手法をIBM Global Bussiness Servicesに組み込んだものを用い，バグのある13のABAPサンプルについて欠陥箇所を特定する． 結果：13プログラム中12のプログラムで欠陥箇所を特定できた．また，そのうち9プログラムのバグは従来の手法では見つからない． 図はSaha et.al., “Fault Localization for Data-Centric Programs” p165より

12 論文著者：George K. Baah, Andy Podgurski, Mary Jean Harrold 担当者：石尾 隆（大阪大学）
Mitigating the Confounding Effects of Program Dependencies for Effective Fault Localization 論文著者：George K. Baah, Andy Podgurski, Mary Jean Harrold 担当者：石尾 隆（大阪大学）

13 論文の概要 統計的な Fault Localization 手法 既存研究から続く考え方： 失敗テストケースで実行された文のほうが，
成功テストケースで実行された文よりも疑わしい プログラム文の疑わしさを求める方法が研究のポイント 提案手法： 成功・失敗のテストケースが「同じ条件で，その文を実行した」と言えるようにテストケースを選択 文の実行に影響を与える文のカバレッジを比較 著者らの従来手法では動的制御依存を考慮していたが，今回は動的データ依存も加えた

14 アプローチの基本モデル 論文 Figure 1 テストケース5個 基本モデル: Equation (1) 文 s がテスト失敗に テスト対象
関与している度合い τ = E[Y1] – E[Y0] Y1: sを実行した文がテストに 失敗するとき1，成功するとき 0 となる確率変数． Y0: sを実行しなかった文が テストに失敗するとき1， そうでないとき0 . E[Y1] = Y1の期待値． すなわち，sを実行した文が テストに失敗する確率． テスト対象 プログラム 各文のカバレッジ. 実行したら1. テストの成否. 失敗したら1.

15 Confounding Effect の問題
１つの条件分岐が複数の文の実行を制御する 　　　　　　　　  単純なカバレッジでは違いを区別できない 成功と失敗をそれぞれ公平にサンプリングしていない　 統計的モデルの適用に相応しくない 同一のIF文（3行目）に 制御されるすべての文で τ の値が同じになってしまう

16 本研究の提案 文 s の評価値 τ を決める「対等な」 テストケースの選択法
Dynamic PDG から， s への依存辺を持つ文の集合 D を取り出す 文を頂点とし，動的な依存関係を辺とするPDG　(SDGではない) 各テストケースを，D のカバレッジを表現するベクトルに変換する テストケースが， D の各文を実行していたら 1, そうでなければ 0 の値として，|D| 個の要素の数値ベクトルとする． ベクトル間のマハラノビス距離を求め，成功テストケースと失敗テストケースの組を，距離が近いものから，できるだけ多く取り出す． 「文 s が実行された状況ができるだけ近い」成功テストケースと失敗テストケースの組を選んでいくことになる マハラノビス距離で，相関を考慮

17 既存手法との組み合わせ テストケースの組が取り出せない場合は，著者らの従来手法で推定
ある文 s を実行したテストケースがすべて成功である場合や，類似度が低い場合にこちらの処理を使う Equation (6): 「文 s が実行されたかどうか」と「文 s に動的制御依存を与える文が実行されたかどうか」の２つの値から，テストケースの失敗を表現する線形回帰モデル データ依存が入っていないことには注意

18 評価実験 プログラム文を，文の評価値 τ でソートしたとき，バグ修正の対象となった文が，何番目に来るかで評価
τ の値に従って上位から順に調べた場合の開発者の労力を評価 評価値が同じ文は，すべて同時に調査対象となると考える 既存手法 Tarantula, Ochiai との比較実験で改善を示した 50%程度のバグには，既存手法よりも良い結果を出す．改善幅は0.05%～60% 20%程度のバグには，既存手法よりも悪い結果を出す

19 おわり