DEIM Forum 2023 5b-6

識別パターンマイニングを用いた自動バグ限局
杉森 裕斗†

中村 篤祥††† 北海道大学工学部情報エレクトロニクス学科 〒 060–0814 札幌市北区北 14 条西 9 丁目†† 北海道大学大学院情報科学研究院 〒 060–0814 札幌市北区北 14 条西 9 丁目
E-mail: †{sugimori,atsu}@ist.hokudai.ac.jp
あらましソフトウェアに含まれるバグの原因箇所を自動で特定するため、自動バグ限局手法の研究が盛んに行われている。既存手法として、テストケース実行の結果と実行経路を利用する方法が提案されている。同手法ではテスト
ケース実行においてどの行を通過したかという情報のみを使用しており、その順番は考慮されていない。本論文では
バグ限局効率向上のため、実行順序を記録した実行トレースを使用し、識別パターンマイニングを適用する手法を提案する。識別シーケンシャルパターンマイニングはクラス分けされたシークエンスデータの中からクラスを特徴づけるパターンを発見するデータマイニング技術である。失敗したテストケース実行を特徴づけるパターンにはバグが含まれている可能性が高いと考えられる。実験の結果、提案手法によるバグ限局効率は全体として低下したが、バグの種類によっては向上するものがあることがわかった。
キーワード ソフトウェア開発,

バグ限局, データマイニング, 識別パターンマイニングスを同論文で提案されている線形実行ブロックのトレースに変

1 はじめにデバッグは、ソフトウェア開発において多大なコストが掛かる作業である [3]。デバッグの中でもバグの原因箇所を特定する作業をバグ限局と呼ぶ。この作業は開発経験とプログラムに対する理解を持った技術者が行う必要がある。手動のデバッグは
コード全体の再確認や、コードの複数箇所にブレークポイント
をはり、変数の値を確認する作業が必要になるため、手間と費用がかかる。
そこで、バグ限局コスト削減のため自動バグ限局の研究が盛んに行われている [1, 4, 7, 8, 9, 10, 12]。その手法はプログラ
ムの静的解析やバグレポートを利用したもの、テストケース実行時の通過ステートメント情報を利用したものなど、様々である。本論文ではテストケース実行におけるプログラム内のス
テートメントの実行順序であるトレースを使用し、識別パター
ンマイニングを用いた自動バグ限局手法を提案する。
識別パターンマイニングとはクラスづけされたデータにおいて、そのクラスを特徴づけるようなパターンを発見するデータ
マイニング技術である。識別パターンマイニングは様々な分類問題に応用されている [5, 6]。バグの含まれているプログラム
において、失敗したテスト実行トレースを特徴づけるパターンにはバグの原因となっているステートメントが含まれている可能性が高いと考えられる。このようなパターンを抽出すること
でバグ限局に利用できる。
関連研究換される。これにより計算量が削減される。全てのトレースから N グラムを生成し、その中から失敗トレースにおいて頻出なものを抽出する。抽出された N グラムは失敗トレースにおける信頼度によってランキングされ、ランキングが高い N グラムに含まれるステートメントから順に検査する。
機械学習を応用した手法としてニューラルネットワークを用いたバグ限局手法も提案されている [9]。入力には各テストケー
スで通過したステートメントを表したカバレッジベクトル c、
出力にはその結果を表した結果ベクトル r を用いる。カバレッ
ジベクトルの要素 ci は、そのテストケースにおいてステートメ
ント si が実行された場合に 1、実行されなかった場合には 0 となる。結果ベクトルの要素 rm は、m 番目のテストが失敗した
場合に 1、成功した場合 0 となる。このデータから、実行されたステートメントとその結果の関係を学習する。その後、仮想テストケースとして一つのステートメントのみを通過したケー
スを入力する。つまり、ci = 1 それ以外は０としたベクトルを入力する。これを全てのステートメントに対して行う。この時の出力値は 0 以上 1 未満の値を取る。その値がステートメント

si の疑惑値となり、この値が大きい順から検査する。この手法はさらに RBF ニューラルネットワークを用いた手法へと拡張されている [13]。
また、プログラムスライスを利用したバグ限局手法も提案されている [12]。プログラムスライスとはある変数の値に関係するステートメントの集合である。この手法は、「テストが失敗した時、出力に関係するスライスにバグが含まれている」という実行トレースに対するデータマイニング技術を応用したバグ考えに基づいている。テストが失敗した時のスライスとテスト

限局手法として N グラムを用いた手法が提案されている [8]。

が成功したときのスライスの差を考えることで、バグが含まれN グラムとはシークエンスの長さ N の連続部分列である。こる可能性のあるステートメントの範囲を絞り込むことができる。

の手法では、まずテスト実行におけるステートメントのトレー

識別パターンマイニングはバグ検知にも応用されている。バグ検知とは、プログラムの実行履歴からそのプログラムにバグが含まれているかを判断する技術である。バグが検知された場

トをバグを含む可能性が高い順に並べる問題を考える。

合、テストを追加しバグ限局を行う。[11] ではテストトレース
における頻出パターンを特徴として分類器を学習する手法を提案している。まず実行トレースから反復頻出パターンを抽出する。反復頻出パターンとはそれぞれのトレースにおいて出現した回数を考慮した頻出パターンである。このパターンからさらに識別パターンを抽出する。実行トレースにおける識別パター
ンの出現回数からそのプログラムにバグが含まれているかどうかを判断する。バグ検知においては抽出されたパターンに対応するコードの行にバグが含まれているかではなく、プログラムのどこかにバグが含まれているかを判断する。本稿では識別パ
ターンマイニングをバグ限局に用いるため、パターンに対応するコードの行にバグが含まれるようなパターンを抽出する手法の開発を目的とする。

2 問題設定3 従来手法 SBFL
自動バグ限局とは、プログラムのバグの位置を特定する、
デバッグ支援技術である。spectrum based fault localization(SBFL) はテストの結果と実行経路からソースコード上でバグの含まれている位置を特定する手法である [4, 10]。具体的な手法は、まずそれぞれのテストの実行結果の記録と実行された
ソースコード上の行番号の記録を収集する。その記録をもとに、各ステートメント s にバグが含まれている可能性となる「疑惑値」を算出し、その値が高い順にコードを検査していく。疑惑
値の計算方法は様々だが、最も一般的である tarantula[4] の指標 suspiciousness(s) は以下の通りである

suspiciousness(s) =n 行からなるプログラムを P とする。P 内のソースコードの

f ailed(s)totalf ailed
passed(s)f ailed(s)+ totalf
totalpassed
ailed

(1)

実行可能ステートメントの集合を S = {s1 , s2 , ..., sk } とする。

た だ し 、totalf ailed は 失 敗 テ ス ト ケ ー ス の 総 数 を 表 し 、

実行可能ステートメントとは、ソースコードにおいて変数宣言やtotalpassed は成功テストケースの総数を表す。また、プロ

空行を除いた、実行可能なステートメントである。このプログラ

グラム上のあるステートメント s を実行し、かつ失敗したテス

ムに対するテスト集合を T = {t1 , t2 , ..., , tm } とする。各テスト

ト数を f ailed(s)、成功したテスト数を passed(s) と表す。

ti は入力 Ii と期待される出力 Yi の組 ti = (Ii , Yi ) で表される。

SBFL は「そのステートメントを通過し、失敗したテストのテスト ti において、入力 Ii を与えられた際の実行されたステー

割合が高いほどバグの原因となっている可能性が高い。」といトメントを実行順に並べた列を Xi = (x1 , x2 , ..., xl )(xj ∈ S)

う直感に基づき、指標が考案されている。

とし、これをトレースと呼ぶ。ti における実際の出力を Ai と

表 1 の suspiciousness(s) の値は tarantula の指標を用いてする。このテストの出力が期待出力 Yi と異なっていた場合、つ疑惑値を計算したものである。この場合、検査の優先順位が最

まり Ai ̸= Yi のときテストは失敗したとする。パターン b は実も高いステートメントは s4 , s5 、次に s1 , s2 , s6 、最後に s3 とな

行可能ステートメント列で表され、トレース Xi に b が連続部る。バグが含まれている s5 の優先順位が高くなっていること

分列として現れるとき、パターン b はトレース Xi に出現するがわかる。

という。b が出現するトレースの集合を Occ(b) で表現すると、パターン b のトレース Xi における出現は Xi ∈ Occ(b) で表現される。
それぞれのトレース Xi に、そのテストが成功したか失敗したかを表すクラス ci ∈ {0, 1} が与えれているものとする。ただし、ti が成功した場合 ci = 0、失敗した場合 ci = 1 とする。
それぞれのテストのトレース Xi とそのテストのクラス ci を

di = (Xi , ci ) のように順序対で表現すると、全てのテストにおけるトレースとそのテスト結果は D = {d1 , d2 , ..., dm } で表される。

4 提案手法
従来手法では、テスト実行経路の情報として、どのステート
メントを通ったかという情報のみが使用されており、その順番は考慮されていなかった。本研究では、精度向上のため、実行経路をシークエンスデータとして扱う自動バグ限局手法を提案する。

4. 1 識別シークエンスパターンマイニング
識別シークエンスパターンマイニングとは、クラスづけされ表 1 に示すサンプルプログラム P は自然数 n に対してたシークエンスデータが与えられた際に、そのクラスを特徴づ⌊ n2 ⌋ を求めるプログラムである。このプログラムに対してテけるようなパターンを発見するデータマイニング技術である。

ストケース T = {t1 , t2 , t3 } を実行したとする。この時各テシークエンスのパターンに対し、識別力を表す指標（識別スコ

ストケースにおけるトレースは X1 = (s1 , s2 , s4 , s5 , s6 ), X2 =ア）を計算することでそのパターンがクラスの分類においてど(s1 , s2 , s3 , s6 ), X3 = (s1 , s2 , s3 , s6 ) であり、結果を組み合わせたれだけ有用であるかを計算することができる。頻出パターンに

順序対で表現すると、d1 = (X1 , 1), d2 = (X2 , 0), d3 = (X3 , 1)

対し識別スコアを計算し、ある閾値以上のスコアを持つパターと な る 。す べ て の テ ス ト に お け る ト レ ー ス と そ の 結 果 はンを識別パターンとして抽出する手法が提案されている [2]。指D = {d1 , d2 , d3 } である。

標には情報利得やフィッシャースコアが使用される。テストに

本稿では、実行可能ステートメント集合 S 、トレースとテス

対するトレースと結果の集合 D に対して、パターン b がトレー

ト結果の集合 D が与えられたとき、S に属するステートメン

スに出現するとき 1、出現しないとき 0 の値をとる変数を Xb 、

表1

サンプルプログラム P

ステートメント

プログラム Ps1

scanf(%d, &n)

〇

〇

〇

0.5

s2

if(a%2 == 0){

〇

〇

〇

0.5

s3

ans = n/2}s4else if(a%2 == 1){

s5
s6

t1 (1, 0) t2 (4, 2) t3 (5, 2) suspiciousness(s)〇ans = (n+1)/2} #bugreturn(ans)result(failed:1, passed:0)

0

〇

〇

〇

〇

1
0.5

〇

〇

〇

1

0

1

1

テスト結果 (0 または 1) を表す変数を C とした場合、パターン

Algorithm 1 Fault Localizationb に対する情報利得 IGb は以下のように定義される。

Require:S: 実行ステートメント集合,

D: トレースと結果の集合 θ0 : 頻度の閾値IGb = H(C) − H(C|Xb )(2)

1: #step1 テストトレースをブロックトレース変換
2: for (Xi , ci ) ∈ D do

ただし、H(C) は C のエントロピー、H(C|X) は X で条件づ

3:

けた C の条件付エントロピーである。

4: end for

D におけるパターン b に対するフィッシャースコア F rb の定Convert statement trace Xi′ to block trace

5: #step2 失敗トレース頻出パターン抽出
6: F ← {b|supf (b) >= θ0 }

義を次に示す。

7: #step3 識別スコア計算∑1
F rb =

2i=0 ni (µi − µ)∑12i=0 ni σi(3)

ただし、ni はクラス i におけるデータ数、µi はクラス i における Xb の値の平均、σi はクラス i における Xb の値の標準偏差、µ は全データにおける Xb の値の平均を表す。

8: for f ∈ F do
9:scoreb ← calc score(b, D)

10: end for
11: #step4 ステートメントランキング
12: Sort s in descending order of max{scoreb |si ∈ f }13: Examine s from rank 1

4. 2 自動バグ限局アルゴリズム
提 案 す る ア ル ゴ リ ズ ム を Algorighm 1 に 示 す。こ の ア

step1 テストトレースを基本ブロックのトレースへ変換

ル ゴ リ ズ ム は 、テ ス ト ト レ ー ス と そ の 実 行 結 果 の デ ー タ

テストにおけるステートメントの実行順序を記録したトレー

D = {d1 , d2 , ..., dm }、実 行 可 能 ス テ ー ト メ ン ト 集 合 S =スをプログラム基本ブロックのトレースへと変換する。基本プ{s1 , s2 , ..., sk }、頻出パターンマイニングにおける頻度の閾

ロック内には分岐を含まないので同じブロック内のステートメ

値 θ0 を入力としてバグが含まれている可能性の高いステート

ントは必ず同じ順序で実行される。そのため、ステートメント

メントのランキングを出力する。収集されたテストトレースはトレースをブロックトレースに変換することで実行順序の情

まずプログラム基本ブロックのトレースに変換される (step1)。

報を損なうことなくトレースの長さを小さくすることができ。

プログラム基本ブロックとは、内部に分岐や合流を持たないス

これにより、パターン抽出における計算量を削減することがでテートメントの列である。基本ブロック内の最初のステートメ

きる。

ントが実行されると、同じブロックに含まれるステートメント

ブロックトレースへの変換を厳密に行うためにはプログラム

も必ず順次実行される。次に失敗トレースから頻出パターンをの構文解析が必要となる。プログラムの構文解析は言語依存で抽出する (step2)。失敗トレースに頻出なパターンにはバグがあり、言語ごとの解析ツールが必要となる。そこで実験では、含まれている可能性が高いと考えられるが、成功トレースにおトレースのシーケンスにおいて各ステートメントの前後に実行

いても頻出である可能性もある。失敗トレースと成功とレースされるステートメントが常に同じであるか否かでブロックを推の両方において頻出なパターンは単にプログラムの実行時に必定する。この推定により実際より荒いブロック分割が得られるず実行されるだけであり、バグが含まれている可能性が高いとが、頻度分析における影響はない。

は考えられない。そこで、失敗トレースと成功トレースそれぞれにおける頻度にどれだけの差があるかを表す指標として (情報利得またはフィッシャースコア) を計算する (step3)。この値が大きいパターンは失敗トレースを代表するようなパターンであると考えられる。最後にステートメントに対するスコアをこの指標を用いて計算し、ランキングする (step4)。このランキ
ング順にステートメントを検査することで早いバグ発見を可能にする。

step2 失敗テストトレース頻出パターン抽出
失敗したテスト実行ブロックトレース Xi に対し、頻出パター
ンマイニングを行う。本論文においては、抽出されたパターンにバグが含まれている必要がある。そのため、頻出パターン抽出は失敗したテストの実行トレースに対して行い、成功したテストのトレースは用いない。失敗トレースにおけるパターン bの頻度を表す関数 supf (b) は次のように表される。

supf (b) =|{dj ∈ D|cj = 1, Xj′ ∈ Occ(b)}||{dj ∈ D|cj = 1}|(4)ただし | · | は集合’·’ の要素数を表す。頻度の閾値を θ0 とする

5. 1 対象プログラムと、supf (b) >= θ0 を満たすパターン b を頻出であるとし、頻出パターンの集合を F を求める。

る Siemens suite を使用した。このプログラムセットには、C

連続頻出パターンは一般化接尾辞木を用いると総入力長の線を用いて作成された 7 つのプログラムがあり、それぞれのプ

実験には、多くのバグ限局手法の実験において使用されてい形時間で求めることができる。

ログラムには、正しいバージョンと、バグを含んだ複数のバー

step3 識別スコア計算

ジョンが作成されている。バグを含むバージョンはそれぞれ一

頻出パターンマイニングで発見されたパターン集合 F に含まれるパターン b に対して識別スコアを計算する。本論文では指標として情報利得またはフィッシャースコアを使用し、自動バグ限局における有用性を比較する。パターン b において、

θ=

つのバグを含んでいる。Siemens suite に関する詳細な情報は[7] を参照されたい。
このプログラムセットには様々な種類のバグが含まれているが、コードの欠落によって引き起こされるバグ、定数および変数定義によるバグを含むバージョンは対象外とした。SBFL お|{dj ∈ D|Xj′ ∈ Occ(b)}|よび提案手法ではこの種のバグの位置を推定することができな|D|

いためである。また、GDB を用いて正常にトレースを取得す|{dj ∈ D|ci = 1|
|D|ることができないテストも対象外とした。結果として、6 プロ

p=グラム、71 バージョンにおいて実験を行った。

|{dj ∈ D|cj = 1, Xj′ ∈ Occ(b)}|q=|{Xj′ ∈ Occ(b)|正しいバージョンにおける各プログラムの総実行可能ステー
トメント数を表 2 に示す。

とする。θ はパターン b を含むトレースの割合、p は失敗したテ
表2ストの割合、q はパターンを通過したテストにおいて失敗した

各プログラムの実行可能ステートメント数

テストの割合を表す。頻出パターンマイニングにおいては失敗

プログラム実行可能ステートメント数したテストのトレースのみを使用したが、本手順においては成print tokens

159

print tokens2

171

これらの定義を用いると、(2) 式よりパターン b における情報

schedule128

schedule2

117

利得は

tot info

55

tcas

112

功したテストのトレースを含めた全てのトレースを使用する。

IGb (C|X) = −p log p − (−θq log q − θ(1 − q) log(1 − q)
+ (θq − p) log

p − θq1−θ+ (θ(1 − q) − (1 − q)) log(1 − p) − θ(1 − q)
)
1−θ
(5)

θ(p − q)2p(1 − p)(1 − θ) − θ(p − q)2

評価指標として、EXAM を用いる。これは、バグの原因箇所を発見するまでに検査する必要のあるコードの割合を表す。
この値が小さいと優れたバグ限局手法であると言える。

と計算され、フィッシャースコアはF rb =

5. 2 評 価 指 標

実験に使用したプログラムは正しいバージョンを改変するこ(6)と計算される [2]。

tarantula の指標 (1) では通過頻度が小さくても通過した時の失敗割合が高ければスコアは高くなる。情報利得やフィッシャー
スコアでは通過頻度が小さいパターンは分類に寄与しないた
め、小さくなるようにできている。

とでバグを含んだバージョンを作成している。その多くはある一つのステートメントを変更したものであるが、複数ステート
メントに渡って変更されているバージョンも存在する。この場
合は、変更されたステートメントの集合に含まれるステートメ
ントのうちいずれかに到達した時点でバグを発見したものとする。
場合によっては、複数の異なるステートメントに対して同じ

step4 ステートメントランキング

疑惑値が与えられる。バグが含まれるステートメントと同じ疑惑値が与えられたステートメントが複数存在する時、そのス

頻出パターン f の要素であるブロックのいずれかがステー
トメント s を要素として持つとき、si が f に含まれるとし、

si ∈ f と表記する。各ステートメント si のスコアを、それを含むパターンの識別スコアの最大値とし、そのスコアでランキ

テートメントの集合を SF とおくと、⌊ |S2F | ⌋ 行目でバグを含んだステートメントに到達したものとする。

5. 3 実行トレースの収集
実行トレースの収集には GDB を用いた。収集されたトレーングする。

スは計算量削減のため、ステートメントのトレースからプログ

5 実

験

本章では実験に用いたデータと、各手法を比較するための評
価方法について述べる。

ラム基本ブロックのトレースに変換し、実験に使用した。基本
ブロックへの変換は次のように行なった。
（ 1 ） GDB のログからソースコードにおける行番号の実行順序

を抜き出し、ステートメントトレースとする。
（ 2 ） 全テストのステートメントトレースを走査し、各ステート
メントの直前、直後に実行されるステートメント集合を求める。
（ 3 ） 次の条件 a または b を満たすステートメントをブロックの入り口とする。

a プログラムの最初に実行される
b 直前に実行されるステートメントが分岐点となっている。
図1

提案手法と既存手法 tarantula の比較（ 4 ） ブロックの入り口から直後に実行されるステートメントをたどっていき、分岐点に到達したところで終了する。
（ 5 ） 入り口から走査してきたステートメント列を一つのブロッ
クとする。
（ 6 ） 全てのステートメントトレースをもう一度走査し、ステー
トメントとブロックを対応づけ、ブロックトレースとする。

7. 1 自動バグ限局指標
表 3 に、情報利得とフィッシャースコアを比較し、より早くバグを発見できたバージョン数を示す。情報利得の方が早くバグを見つけられたバージョン数は多いが、その差は全体の 7%である。よって自動バグ限局においてはこの二つの指標の有用性は同程度であると考えられる。

バグを含んだバージョンと正しいバージョンの出力を比較し、さらに自動バグ限局におけるスコアの有用性を比較するため、

正しいバージョンの出力と異なるテストを失敗テストとした。

ステートメントではなく頻出パターンに対して tarantula のス
コアを適用した場合を考える。パターン b に対する tarantula

5. 4 頻度の閾値設定

スコアは式 (1) より

頻出パターンマイニングに用いる頻度の閾値 θ0 は、0.25 から 1.0 まで 0.25 刻みで設定し、それぞれの結果を比較した。その結果、情報利得では 0.25 および 0.5、フィッシャースコアでsuspiciousness(b) =は 0.25 に設定すると最も良い結果が得られた。提案手法におけるスコアは頻度が低いとその値も低くなるため、これ以上小(7)と表される。ただし、さい頻度をにする必要はない。これ以降の結果は θ0 を 0.25 に

f ailed(b) = |{dj ∈ D|cj = 1, Xj′ ∈ Occ(b)}|設定したときのものである。

6 結

f ailed(b)totalf ailed
passed(b)f ailed(b)+ totalf
totalpassed
ailed

果

passed(b) = |{dj ∈ D|cj = 0, Xj′ ∈ Occ(b)}|提案手法および既存手法の実験結果を示す。提案手法と既存

図 2 は提案手法と tarantula スコアを頻出パターンに適用し手法 tarantula の結果を比較した結果を図 1 に示す。青の線がた場合の結果である。この図から、提案手法と tarantula スコ

情報利得、赤の線がフィッシャースコアを指標とした結果であアの大きな差は見られない。つまり、本研究において従来手法

り、黒の線は既存手法 tarantula の結果である。横軸は EXAMと比べてバグ限局効率が改善しなかった理由はスコアではなくを表し、縦軸は発見したバグの累積の割合を表している。

パターン抽出にあると考えられる。

例えば、tarantula における横軸の値 40%、縦軸の値が 75%の点は、全体の 40%のステートメントを検査することで全てのバグのうち 75%を発見できることを表している。
この図から、検査ステートメントの割合が約 40%に至るまで
は既存手法である tarantula の方がバグを早く発見できていると言える。しかし、40%以降は提案手法の方が早くバグを発見できている。

7 考察

既存手法と提案手法のバグ限局効率の違いについて議論する。
図2

提案手法とパターンに対する tarantula スコアの比較

表 3 EXAM を用いた情報利得とフィッシャースコアの比較
指標

バージョン数

情報利得

32

フィッシャースコア

27

同じ

12

7. 2 パターンの長さ
次に、パターン抽出方法のバグ限局効率への影響を考える。
提案手法ではステートメントのトレースをブロックトレースに変換し、ブロックトレースからパターンを抽出している。同じパターンに含まれるステートメントは同じスコアを与えられる

図 3 best EXAM と worst EXAM の比較

ため、大きなパターンのスコアが高いと、検査の優先順位が同
じステートメントの数が多くなってしまう。そのため、たとえ

ステートメントが通過したかという記録しか使用されないたバグが含まれているパターンに高いスコアが与えられたとしてめ、一方の分岐のみに誤りがあっても、もう一方の分岐の正常も、そのパターンが大きいと、EXAM の値は大きくなる。そな動作時も通るため分岐条件ステートメントの tarantula のスのため、提案手法が少ないステートメント検査数でバグを発見

コアは低下する。

できなかった要因として、ステートメントとパターンの粒度の違いが考えられる。

今回実験に用いた 71 バージョンのバグうち、20 バージョン
が if 文の分岐条件の改変によるバグであっった。この 20 バー

粒度の差によるバグ限局効率への影響を考察するために、best

ジョンで提案手法と既存手法を比較すると、情報利得または

EXAM と worst EXAM の結果を図 2 に示す。best EXAM とフィッシャースコアを用いた手法が tarantula より優れた結果

はバグが含まれるステートメントと同じスコアのステートメンを出したバージョン数は 14 であった。

トを検査する際に一番最初にバグの入ったステートメントが検査されるとした時の EXAM の値である。worst EXAM は反このことから、提案手法は分岐条件にバグを含む場合に既存手法よりも早くバグを発見することができると考えられる。

対にバグが入ったステートメントが一番最後に検査されるとした時の EXAM の値である。つまり、バグが含まれるステート

8 今後の課題

メントと同じスコアが与えられたステートメントが他に存在する時の最良の結果と最悪の結果である。IG は情報利得、Fr は

本論文では識別パターンマイニングを用いたバグ自動限局手

フィッシャースコア、tar は既存手法 tarantula の結果であり、法を提案した。テスト実行情報をシークエンスデータとして扱それぞれの best EXAM を実線、worst EXAM を破線で表し

うことによるバグ限局効率向上が期待された。

ている。best と worst の差が大きいとき、同じスコアが与えられるステートメント数が多いと言える。
図 3 から、提案手法は best EXAM と worst EXAM の値の差が大きく、既存手法 tarantula はその差が提案手法より小さしかし、提案手法では多くのバージョンで既存手法と比べた
バグ限局効率の向上はなされなかった。そのため、バグ限局効率改善のためパターンステートメントのスコアの付け方を改良する必要がある。

い。また、フィッシャースコアの best EXAM と tarantula の提案手法はバグを含むパターンに高いスコアを付けるが、そ

bestEXAM を比べると、フィッシャースコアの方が精度が良の長さが大きいため、検査範囲を絞り込むことができていな

い。情報利得の場合も、tarantula と同程度の精度であることい。そこで、バグの含まれる可能性の低いステートメントの除がわかる。

外や、ステートメントのスコアをそれを含むパターンのスコア

つまり、バグを含むパターンが高スコアになっているもののの最大値とするのではなく平均値にするような、ステートメン

その長さがひじょうに大きいため、その中間で割合では提案手

トのスコアに差がつくスコアの付けによってバグ限局効率の改法は既存手法よりも良いバグ限局効率とならなかったと言える。

善が期待できる。

抽出されるパターンが長いと、同じスコアが与えられるステー
トメント数が多くなるため精度が低下する。

7. 3 バグの種類
提案手法が既存手法より早く見つけられたバグの種類について分析する。提案手法はテスト実行情報をシークエンスとして捉えていることが既存手法との相違点である。これにより、if文による条件分岐のような実行経路制御におけるバグを見つけやすいと考えられる。if 文の条件式を通過したあと、どの分岐先に進んだかが記録されているためである。従来手法ではどの

文

献[1] R. Abreu, P. Zoeteweij, et al. An evaluation of similarity
coeﬃcients for software fault localization. 2006 12th Paciﬁc
Rim Int l Symposium on Dependable Computing (PRDC06), pp. 39–46, 2006.
[2] H. Cheng, X. Yan, J. Han, and C. Hsu. Discriminative frequent pattern analysis for eﬀective classiﬁcation. In ICDE,
2007[3] B. Hailpern and P. Santhanam. Software debugging, testing,and veriﬁcation. IBM Systems Journal, 41(1):4–12, 2002.
[4] Jones, J.A., Harrold, M.J., Stasko, J.: Visualization of test

[5]
[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

information to assist fault localization. In: Proceedings ofthe 24th International Conference on Software Engineering,
2002.
B. Liu, W. Hsu, and Y. Ma. Integrating classiﬁcation and association rule mining. In Proc. of KDD, pages 80–86, 1998.
H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, andC. Watkins. Text classiﬁcation using string kernels. Journalof Machine Learning Research, 2:419– 444, 2002.
M. Hutchins, H. Foster, T. Goradia and T. Ostrand, Experiments on the eﬀectiveness of dataﬂow- and controlﬂowbased test adequacy criteria, Proceedings of the 16th International Conference on Software Engineering, Sorrento,
Italy, pp. 191–200, 1994
S. Nessa, M. Abedin, W. Eric Wong, L. Khan, and Y. Qi,
Fault localization using N-gram analysis, in Proc. Int.
Conf. Wireless Algorithms, Syst, pp. 548–559, 2009.
W. E. Wong and Y. Qi, BP Neural Network-based Eﬀective
Fault Localization, International Journal of Software Engineering and Knowledge Engineering 19(4):573-597, June
2009.
W. E. Wong, V. Debroy, Y. Li, and R. Gao, Software fault
localization using DStar (D*) in Proceedings of 6th International Conference of Software Security Rel., Washington,
D.C., USA, pp. 21–30, 2012.
D. Lo, H. Cheng, J. Han, Classiﬁcation of Software Behaviors for Failure Detection: A Discriminative Pattern Mining Approach, Proceedings of the 15th ACM SIGKDD, pp.
557-566, 2009.
H. Agrawal, J. R. Horgan, S. London, and W. E. Wong,
Fault Localization using Execution Slices and Dataﬂow
Tests, in Proceedings of the 6th IEEE International Symposium on Software Reliability Engineering, pp. 143-151,
Toulouse, France, October 1995.
W. E. Wong, Y. Shi, Y. Qi, and R. Golden, Using an RBF
Neural Network to Locate Program Bugs, in Proceedingsof the 19th IEEE International Symposium on Software Reliability Engineering, pp. 27-38, Seattle, Washington, USA,
November 2008.