[論文]Spectrum-based Software Fault Localization: A Survey of Techniques, Advances, and Challenges

動的情報を活用した故障箇所特定手法,技術をまとめた論文

内容をまとめるための個人的なメモ
大学院生がまとめたものなので、間違っている内容があるかもしれないです.
この記事は論文を大学院生が個人的なメモと勉強のためにまとめた内容です。
引用元論文: Souza, Higor & Chaim, Marcos & Kon, Fabio. (2016). Spectrum-based Software Fault Localization: A Survey of Techniques, Advances, and Challenges.

1.はじめに

障害の定義はプログラムが予期しない動作をすることである.
故障箇所の特定はソフトウェア開発プロセスにおいてコストのかかかる作業であり, 開発コストの最大75%を占めるといわれている.
最も頻繁に行われるのはprint文やブレークポイントの挿入などだが、このような手動のアプローチはコストがかかる。

1.1 動機と範囲

SFL: spectrum-based Fault Localization(SFL)
Coverage-based Fault Localization(CAB)
利用可能なSFLの技術は増えているが、実際には使われていないことも多い。その原因として、それらの技術が既知のプログラムを使って評価されているため、実際の複雑で大規模なシステムには適応できるかは不明orできないことが挙げられる。

2 コンセプトとセミナリー・スタディー

ここでは用語の定義と代表的な研究の歴史的概要が紹介される。

2.1 用語の定義

フォルト(fault)、エラー(error)、故障(failures) はプログラムの実行中に予期せぬ動作をが発生する３つの段階を表す。

フォルト(fault)はプログラム内の誤ったステップ、プロセス、データ定義のことである。フォルトはプログラムを書いた開発者によって挿入される。fault=bug, defect
誤差(error)
誤差(error)は厄介な単語であり、fault,failuresなどの意味で使われることもある。特別な意味でのエラーは計算された値と正しい値との間の差異である。エラーは実行されたフォルトがプログラムの状態を変更するときに使われる。エラーを表現するための他の用語としては感染や異常など。
-失敗(failures)
失敗とはシステムがその機能を期待された要件で実行できないことを表す。失敗はよきせぬ出力として観察される。プログラムのエラーが誤った出力をもたらす場合に発生する。
クラッシュはプログラムの実行を中断することで、見かけ上の動作をする障害。ミスは障害を生み出す人間の行動である。
シードされた故障
フォルト局在化の技術の評価対象プログラムによく使われる方法。
モニタリング検出のために意図的に挿入されたfaultのことである。
faultは実験目的で手動挿入したり突然変異(mutation)で挿入される。
本物のfaultsとはソフトウェア開発中に自然に発生したもの。
ランキング指標
故障箇所の特定ではランキングメトリクスが使われる。故障箇所の特定に関する研究では、ランキング指標を
「テクニック」
「リスク評価式」
「メトリック」
「ヒューリスティック」
「ランキングヒューリスティック」
「係数」
「類似性係数」などの異なる用語で表現している。
プログラムエンティティ
プログラムの一部のことである

2.2　デバッグ技術の歴史

バグの言葉の誕生はエジソンの時代らしい。
1940年代後半にカーバード大学のMerk 2コンピュータが死んだ蛾によって回路がショートし、突然停止したことに由来するらしい(hee)
デバッグを自動化する技術はいくつか提案されている。

EXtendable Debugging and Monitoring
System (EXDAMS) [14]
LAURA
PROgram UnderSTanding (PROUST)
Language Assertion Drive Debugging INterpreter (ALADDIN)
アサーションを利用した技術
Program Error-Locating Assistant System (PELAS)
プログラムの依存性に基づいた最初の故障箇所特定技術
プログラムスライシング
欠陥を特定するための実行サイコロ
同音異義語のランキング指標を用いてステートメントの怪しさを計算する Tarantula
静的解析に基づく手法

実際のデバッグには print 文やシンボリックデバッガが普及してる。これらの多くは産業界で開発されたプログラムには対応できない。また、実際のデバッグの現場で評価されていないことも理由の一つ。Parnin と Orso は、開発者の行動が、ローカライゼーション技術の提案者が期待するものとは異なる可能性があることを示した[111]。

SFL は、テストデータを利用して、疑わしいコードをハイライトする。テスト中に収集されたデータを利用することで、SFL は他のデバッグ手法と比較してオーバーヘッドが少ない傾向にある。

3研究の選択と範囲

ACM Digital Library，IEEE Xplore Digital Library，SpringerLink，および SciVerse Scopus - Elsevierが対象。
品質が認められているジャーナルやカンファレンスで発表されたものが対象となる。
アブストラクトなどを読んで選択するかどうかを決定したらしい。

4. スペクトラムベースの故障診断技術

SFLの多くでは故障したプログラムエンティティを特定するためにランキング指標や統計的指標を用いる。
ジン人工知能に基づく手法も存在する。

4.1 メトリックベースの手法

メトリック・ベースの技術とは、ランキング・メトリックの公式を用いて不具合のあるプログラム・エンティティをピンポイントで特定する技術のことらしい。
これらの手法では、テストから得られるプログラムスペクトル情報を入力として受け取る。そして、各プログラムエンティティに故障の可能性を表すスコアが与えられる。
アイディアは、失敗したテストケースで頻繁に実行されるプログラムエンティティは、より疑わしいということ。

Tarantula[66]
Minus KBC (MKBC) (ランキング指標)
Kulczynski2（人工知能）や McCon（プランクトン群集の研究）-ランキング基準

ランキングメトリクスと組み合わせた手法

失敗した実行のステートメントの値を置き換える技術[62]
失敗した実行でも合格した場合、そのステートメントは最も疑わしいものに分類される(バグが混入している疑い？)
実行中のステートメントの数に応じて、失敗したテストケースのステートメントに異なる重みを割り当てるアプローチ[102]
失敗したテストケースが少なくとも一度は実行された文と、これらのテストケースが実行されなかった文の 2 つのグループを形成する手法[150]
合格したテストケースと失敗したテストケースの類似性に応じて、テストケースに異なる重みを割り当てる手法[16]
合格したテストケースの類似性が高いほどその重みは大きくなる。
これは失敗したテストケースと合格したテストケースの間にはほとんど違いがみられないため、欠陥はより区別しやすいためである。
(どーゆーこと？？？)

4.2 統計学的手法

統計学的手法は娶り行くベースの手法と同様に使用されている。
それぞれの統計的手法はテスト情報を独自に扱う。
述語=predicates

SOBER[87]
ベルヌーイ分布を用いて実行の合格不合格の条件付き確率を用いて述語のバグ関連性を計算する。
故障の局所化のためのバグ予測器として複雑な述語のアイデア[100]
ノンパラメトリックな統計モデルを用いて故障箇所を特定する手法[177]
実行中の述語の分布が非正規であることを観察したらしい。
クロスタブを用いた手法で故障箇所の特定[145]
χ二乗検定を使ってるらしい
最尤推定と線形回帰を用いて SFL リストのチューニング[174]
オッズ比の適用[156]
オッズ比は分類やテキストマイニングでよく使われる手法らしい。
あるイベント(テストの合格、不合格)に関連する変数の強さや弱さを測定する。
失敗したテストケースのプログラム依存性グラフを用いて得られる確率的因果関係グラフ（PCEG）[152]
ベイジアンネットワークの一種を用いて欠陥のあるステートメントの確率を計算する。最も疑わしいステートメントは、他の疑わしいステートメントとより強く接続されているというアイディア。

4.3 機械学習(人工知能)を用いた手法

疑わしいプログラム(バグありの疑い)要素を分類するための入力としてプログラムスペクトルデータを用いた故障箇所の特定に応用される。

サポートベクターマシンを用いて故障箇所を特定する技術[86]
データマイニングのN-gram解析を利用した故障箇所特定[106]
ここで1gramはおそらく1ステートメントを表している。各N-gramが故障箇所に関連する確率を計算する。最も疑わしいN-gramからバグの疑いがあるステートメントのリストを得る。
決定木を用いた故障箇所の特定[97]
この手法では故障に関連する関数呼び出しパターンを特定する。
RBF-NN[143]
ここで用いるニューラルネットワークは各ステートメントを個別に評価してその疑惑度を計算する。最終的にはランキングメトリクスを用いて判断する。
関連性尺度を用いることの評価[91]
オッズ比など統計学で一般的に利用される関連性測定を評価した研究。問題を各エンティティの実行と障害の間の関連性の強さとしてモデル化。これらの関連性測定はSFLの大幅な改善には至らなかったらしい。
機械学習による特徴選択に基づく手法[121]
RELIEFとRELIEF-Fという２つの手法を用いて、欠陥のある可能性に応じて文を分類する。この手法はバグの実行に関連したステートメントの動作の多様性に対応できる。
機械学習の Markov Logic Network を故障箇所特定に利用[169]
動的な情報と静的な情報、事前のバグ知識(過去に見つかった類似のバグの位置)を考慮してモデル化。評価は単一バグのプログラムに対して行われたよう。

4.4実行モデル

SFLのもう一つの手法はテスト実行結果から実行モデルを構築すること。実行モデルとは、テストの合格と失敗のパターンを表すもの。
したがって、期待されるパターンを満たす、もしくは逃れるエンティティを特定するために使用される。

失敗した実行から合格した実行を生成する手法[135]
失敗した実行の枝の結果(AST的な？)を合格する実行が得られるまで切り替える。結果（出力）は合格する実行で構成されたブランチのリスト。切り替えプロセスは最後の実行ブランチから始まり、徐々に根本に行くイメージ。開発者は生成されたランが正しいかを確認する必要がある。
不具合が発生する可能性の高いメソッドを示す手法の提案[79]
統合テストの情報を利用し、クローズド・アイテムセット・マイニング・アルゴリズムを利用して実行された各メソッドのメソッドコールパターンを補足する。これらのメソッドはパターンの最高スコアに応じてランク付けされるよう。（ランキングメトリクス）

4.5 プログラム依存性に基づく手法

欠陥のあるコードの抜粋を強調するための手法。
プログラム依存データ、プログラムスライス、プログラムエンティティを区別するための重みの割り当てなどプログラムの分析情報を使用する技術が存在する。

落合的なメトリックを用いて制御とデータの動的依存性の類似性を計算する手法の提案[163]
この類似性は依存性と不正なプログラムの動作との相関関係を示す。疑似スコアは各ステートメントの制御依存性とデータ依存性の類似度の最大値を考慮して得られる。
故障箇所特定のために提示するエンティティの数を減らすための手法[64]
通過したテストでのみ実行されるエンティティ、passとfailの療法で実行されるエンティティ、他の制御に依存するブランチの３つのレベルでエンティティを除外するフィルタリング
エンティティの実行回数から類似性を計算してプロファイリング
同じコード領域、同じ擬似性の値を持つエンティティをグループ化するグルーピングの３つ。
プログラム構造から得られる情報を利用して故障箇所特定を改善する手法[84]
いくつかの構造はステートメントに影響を与えSFL技術によって誤って分類されやすくなるとしている。メイン関数内にバグがある場合と下位モジュールにバグがある場合のスペクトラムデータの違いによる誤判別や、判別の難易度上昇など。
プログラムスライシングの３つのバリデーションの提案[170]
データスライシング、フルスライシング、関連性のあるスライシング
SFLとプログラムスライスを組み合わせた手法の提案[140]
failのテストのスライスに属さない全てのプログラム要素を削除する。残った要素のバグがあるかの怪しさを計算するために、各要素の実行頻度と、テストケースにおける要素の貢献度を考慮する。
貢献度とは、実行された全ての要素を考慮した上で、ある要素が実行された割合のことである。
-ステートメントをいくつかのカテゴリに分けてスコアを計算する手法[105]

4.6 SFL技術の組み合わせ

ランキングメトリクスに基づく多くの技術が登場したことにより、それらを組みわせる手法がいくつか登場する。

HSS[69]
２つのランキングメトリクスをかけわせることでプログラムにバグがある可能性を計算している。
Genetic Programming (GP)を用いたいくつかのランキング指標[162]
GPを用いて作成したランキング指標のうち6個が比較のために用いたランキング指標よりも優れていたそう。
k-means法を用いたクラスタリング手法[20]
SFLとIRFL(Information Retrieval-based fault localization)の組み合わせの手法[82]
IRFLはバグレポートを用いて疑わしいリストを作成する[123].
失敗したテストケースのプログラム要素と、バグレポートに関連する単語を組み合わせることでメソッドレベルでバグがある可能性があるものを表示する。

4.7 メトリックベースの手法比較

複数のメトリクスベースの手法を組み合わせる研究もあれば、どのメトリクスが優れているかを比較する研究も存在する。

33のメトリクスを比較した研究[104]
SFLの7つのメトリクスを比較した研究[92]
ランキングメトリス実際の故障とシードされた故障では異なる結果を示す[112][110]
ランキングメトリクスの性能は研究の設定によって異なる可能性があるため、いくつかの要因を考慮する必要がある。

5 プログラムスペクトラム

プログラムスペクトルは様々なプログラムの構造を表すことができる。カバレッジタイプには、ステートメント、ブロック、述語、関数やメソッド呼び出し、またその他のスペクトルが含まれる。
異なるカバレッジタイプを組み合わせる研究もあるよう。

5.1 スペクトルの種類

SFL技術で最も使われるエンティティはステートメントらしい。
ステートメントを調査すると欠陥のある場所までたどり着けるが、それを発見するまでに多くのステートメントを調査する必要がある点が課題。
述語とは、分岐や返り値、スカラペアなどの文のこと。

失敗した実行とpassの実行を比較し、最も類似したpassの実行を求める手法[51]
この類似性は述語の結果とその実行順序を比較することで測定される。出力はfail実行によってのみ実行された述語で構成されたレポート。
メソッドコールシーケンスを用いた手法[27]
クラスごとのシーケンスセットを用いて、一回の失敗実行と数回の合格実行でシーケンスが異なるクラスは欠陥があることが疑われる。
ソフトウェアコンポーネント間のインタラクションメソッド呼び出しのシーケンス）に関する情報を収集する技術[93]
passのテストケースの相互作用モデルを生成する。このモデルを失敗し他モデルの相互作用と比較することで怪しいメソッドコールを特定する。

6 フォールト

実際のソフトウェア開発では複数のバグが同時に発生する。そうなると実行時の挙動は変化し、SFL技術の性能にも影響を与える。またフォールトにも様々な種類が存在し、その特徴もSFL技術の性能に影響する。このセクションではフォールトに関する懸念事項が説明されている。

6.1 複数の故障

SFL技術の多くは単一バグを持つプログラムを用いて評価されている。また、単一故障のプログラムに特化して提案された手法もある[3, 104, 169]
流石にこれでは使えないので、複数欠陥をもつプログラムに対しても評価が行われるようになった。

述語と故障した実行を分類するためにバイ・クラスター化プロセスを用いた手法[181]
他の手法として類似した不具合のあるテストケースを特定することが挙げられる。
特定の故障に最も類似したテストケースをグループ化することで、複数の故障に対するデバッグを並列化する手法の提案[67]
凝集型階層クラスタリングを利用している。
故障クラスタに影響を与える要因の調査[39]
複数の故障があることによってプロファイルや出力が異なる故障では、故障クラスタリングのプロセスを損なう可能性があることを示している。
これらの研究を活用してソースのセマンティック情報を利用して故障クラスタリングを改善する技術の発表[40]
故障に類似度を距離を用いて比較する手法[88]
故障のシグネチャを抽出し、他の故障からの距離を計算する関数を利用して同じ故障に関連するものをグループ化する。
純粋な故障クラスタを得ることは不可能であると主張、その上で複数の故障を対象とした並列デバッグに影響を与える要因を調査[55]
不可能なわけ→そのクラスタには各故障に完全に関連する実体と、故障したテストケースが含まれる必要がある。
また、この研究ではバグレースという複数のクラスターに欠陥が存在する場合についても議論しているよう。
線型計画法を用いた手法[32]
この手法では失敗した全てのテストケースを説明する一連のステートメントを返す。
失敗したテストケースのみを使用する手法の提案[127]
これらのテストケースのエンティティは同じ確率で故障しているよう。この手法で障害を説明できるメソッドの組み合わせが明らかになるらしい。
Zoltar-Mと呼ばれる多重故障のための手法[3]
MBDを用いて既存の故障に関連するステートメント郡を所得。
単一の故障でfailするテストケースと複数の故障でfailするテストケースを区別する手法[165]
失敗したテストケースと最も類似したpassのテストケースとの間の距離を計算する。複数の故障がある場合、距離が大きいテストは関連性がある可能性が高い。

続く