F05 - qwik.jp

F05: Debugging
眞鍋雄貴，石尾隆
大阪大学
※論文リストでの表記順序と，
発表順序は異なりますのでご注意ください
1
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
Partial Replay of LongRunning Applications
論文著者：Alvin Cheung, Armando
Soloar-Lezama, and Samuel
Madden (MIT CSAIL)
担当者：眞鍋雄貴（大阪大学）
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
背景・目的
• プログラム実行の再現
– プログラムを実行する時にログを記録し，そのログを用いてプ
ログラムの実行を再現する
– バグを起こしている正確な位置を調べるのに用いる
• 問題点
– 通常の実行時に大きなオーバーヘッドがかかる
– 非常に大きなログを生成してしまう
• Symbolic executionを用いてオーバーヘッドを削減する手法
– ログをとる部分を減らす
– 足りない部分をSymbolic executionで実行することで補足し，
オーバーヘッドを減らす
• 既存の手法は実行の最初から再現するため，現状のSymbolic
executionエンジンでは何か月も動くようなプログラムの実行を再
現できない
⇒実行の途中から部分的にリプレイできるようにする
3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
主な貢献
•
•
•
プログラムの実行の途中から再現するプ
ログラム実行の再現手法を提案
提案手法を用いたデバッガ（bbr）を実
装した．
チェックポイント
到達
プログラム
特徴
C
C
停止
– チェックポイントを設定
時刻
• ある特定処理に設定したり，パラ
メータによる設定も行える
通常の実行
– ログは最後のチェックポイント到達
時点から，プログラムが停止するま
スナップショットログを残す部分
での部分だけ残す
• チェックポイントに到達したとき，
その時点の状態をスナップショッ
トとして取る
Symbolic execution
– ログとスナップショットに基づき．
による再現
Symbolic executionを用いて，
チェックポイントから実行を再現す
る
4
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
記録するもの
• ログとして
– 条件分岐の値
• 分岐をどう進んだかが決定的に定まる
– アクセスされた配列のインデックス
• スナップショットとして
– その時点でのスタック
– 開いているファイルの状態
5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価
• 目的：オーバーヘッドとログの圧
縮効果の測定
• 手法:6個のアプリケーションの実
行を対象に，提案手法と他のログ
の取り方との間で実行時間とログ
サイズを比較する．
• 結果
– オーバーヘッドは平均
10%(1~33%)で他より小さ
い
– ログも他の手法より小さい
• その他の実験結果から，提案手法
によりデバッグできることも示さ
れている(4.2節)
図はCheung et.al., “Partial Replay of LongRunning Applications” p141より
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
Fault Localization for DataCentric Programs
論文著者：Diptikalyan Saha, Mangala Gowri
Nanda, Pangaj Dhoola, V. Krishna Nandivada,
Vibha Shinha(IBM Research-India) , Satish
Chandra(IBM T. J. Watson Research Ctr)
担当者：眞鍋雄貴（大阪大学）
7
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
背景・目的
• 目的：ABAPで記述されたデー
タ中心プログラムに対するプ
ログラムエラーの高速な解決
の支援
– ABAP：SAP-ERPで使用さ
れる手続型＋宣言型言語
– データ中心プログラム：
データベースなどにある大
規模なデータ集合を処理す
る
• プログラムスライスを用いた
欠陥の局所化
– ある変数について正常な値
と，異常な値をとる場合，
それぞれの場合におけるス
ライスの差分に欠陥がある
可能性が高い
– 本研究では動的スライスを
用いる
図はSaha et.al., “Fault Localization for DataCentric Programs” pp.157より
8
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
データ中心プログラム
における問題
• 従来のfield-row sensitiveな
動的スライスではデータベー
スの要素の追加削除が起こっ
たとき，スライス基準に影響
を与えうるかわからない
– キーの値によっては影響が
出ないことがある
⇒キーとその値を考慮する
• データ中心プログラムでは，
従来の実行系列に基づく差分
検出では差が出ない場合があ
る
⇒実行時の振る舞いの差異を
考慮する
図はSaha et.al., “Fault Localization for Data9
Centric Programs”
pp.158より
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
主な貢献
• Key based Slicing
– 従来のfield-row sensitiveな動的スライスアルゴリズムに，
key-value pairの集合を入力とする，データベースへの変
更がkey-value pairと関係があるかを調べる処理が追加さ
れた動的スライスアルゴリズム
• Semantic Difference
– Corner-case Differences: 実行された各文について，特
殊な状況が起こっているかどうか
• 特殊な状況は各文の種類に対して設定されている
– Mutation Differences: 正常系のスライスに影響を与えな
いよう，異常系のスライスが正常系のスライスと同じふる
まいになるようにするにソースコードを変異させたとき，
その変異部分
• 提案手法により，出力における行の欠落もわかる
10
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価
•
•
•
目的：Key based slicing, Semantic diff, 出力における行の欠落の評価
手法：提案手法をIBM Global Bussiness Servicesに組み込んだものを用
い，バグのある13のABAPサンプルについて欠陥箇所を特定する．
結果：13プログラム中12のプログラムで欠陥箇所を特定できた．また，そ
のうち9プログラムのバグは従来の手法では見つからない．
図はSaha et.al., “Fault Localization for Data-Centric Programs” p165より
11
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
Mitigating the Confounding Effects
of Program Dependencies
for Effective Fault Localization
論文著者：George K. Baah, Andy Podgurski,
Mary Jean Harrold
担当者：石尾隆（大阪大学）
12
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
論文の概要
• 統計的な Fault Localization 手法
– 既存研究から続く考え方：
失敗テストケースで実行された文のほうが，
成功テストケースで実行された文よりも疑わしい
• プログラム文の疑わしさを求める方法が研究のポイント
– 提案手法：成功・失敗のテストケースが「同じ条件で，そ
の文を実行した」と言えるようにテストケースを選択
• 文の実行に影響を与える文のカバレッジを比較
• 著者らの従来手法では動的制御依存を考慮していたが，
今回は動的データ依存も加えた
13
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
アプローチの基本モデル
論文 Figure 1
テストケース5個
テスト対象
プログラム
基本モデル: Equation (1)
文 s がテスト失敗に
関与している度合い
τ = E[Y1] – E[Y0]
Y1: sを実行した文がテストに
失敗するとき1，成功するとき
0 となる確率変数．
Y0: sを実行しなかった文が
テストに失敗するとき1，
そうでないとき0 .
各文のカバレッジ.
実行したら1.
E[Y1] = Y1の期待値．
すなわち，sを実行した文が
テストに失敗する確率．
14
テストの成否.
失敗したら1.
Software
Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
Confounding Effect の問題
• １つの条件分岐が複数の文の実行を制御する
 単純なカバレッジでは違いを区別できない
• 成功と失敗をそれぞれ公平にサンプリングしていない
 統計的モデルの適用に相応しくない
同一のIF文（3行目）に
制御されるすべての文で
τ の値が同じになってしまう
15
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
本研究の提案
文 s の評価値 τ を決める「対等な」テストケースの選択法
1.
Dynamic PDG から， s への依存辺を持つ文の集合 D を取り出す
•
2.
文を頂点とし，動的な依存関係を辺とするPDG
(SDGではない)
各テストケースを，D のカバレッジを表現するベクトルに変換する
•
3.
テストケースが， D の各文を実行していたら 1, そうでなければ 0 の値と
して，|D| 個の要素の数値ベクトルとする．
ベクトル間のマハラノビス距離を求め，成功テストケースと失敗テス
トケースの組を，距離が近いものから，できるだけ多く取り出す．
•
•
「文 s が実行された状況ができるだけ近い」成功テストケースと失敗テス
トケースの組を選んでいくことになる
マハラノビス距離で，相関を考慮
16
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
既存手法との組み合わせ
テストケースの組が取り出せない場合は，著者ら
の従来手法で推定
– ある文 s を実行したテストケースがすべて成功である場合や，
類似度が低い場合にこちらの処理を使う
– Equation (6): 「文 s が実行されたかどうか」と「文 s に動的
制御依存を与える文が実行されたかどうか」の２つの値から，
テストケースの失敗を表現する線形回帰モデル
• データ依存が入っていないことには注意
17
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
評価実験
• プログラム文を，文の評価値 τ でソートしたとき，バグ修正
の対象となった文が，何番目に来るかで評価
– τ の値に従って上位から順に調べた場合の開発者の労力を
評価
– 評価値が同じ文は，すべて同時に調査対象となると考える
• 既存手法 Tarantula, Ochiai との比較実験で改善を示した
– 50%程度のバグには，既存手法よりも良い結果を出す．
改善幅は0.05%～60%
– 20%程度のバグには，既存手法よりも悪い結果を出す
18
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
おわり
19
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Download Report