【連載】なにそれ？あなたの知らないテストの言葉（第6回）：デルタデバッグ(Delta Debugging)

このマンガ連載では普段目にすることが少ない「なにそれ」という用語をピックアップして解説します。

第6回は「デルタデバッグ (Delta Debugging)」です。
デルタデバッグは、機械的に入力や実行条件を削り、失敗の原因や差分を特定する考え方の総称です。DDMIN(the minimizing Delta Debugging：最小失敗ケースの抽出)、DD(general Delta Debugging algorithm：成功と失敗の差分の特定)のアルゴリズムがありますが、今回はDDMINについて説明しています。

DDMINは、Failになる入力を幾つかに分割して、どれか一つとそれ以外をテストして最小失敗ケースを見つける方法です。マンガでは手動で行っていましたが、基本的には自動で行うことを前提としています。

DDMINの流れ

前提として、テスト結果はPass / Fail / Unresolved(結果が不明) の三つとします。
また、結果を不安定にする要因（乱数、タイムアウト、時刻、ネットワークなど）が変動しないように固定や調整しておくことも重要です。

1. 失敗する入力をn分割する。(最初はn=2が多い)
2. 分割したそれぞれの塊をテストする。どれかの塊でFailが出たら、その塊で1.に戻る
3. 分割した全ての塊がPassまたはUnresolvedだった場合、各部分の補集合をテストする。どれかでFailが出たらその塊で1.に戻る
4. 各部分も補集合も全部PassまたはUnresolvedだった場合、nを増やして1.に戻る
5. 失敗する集合からどの要素を一つ抜いてもFailにならなくなる状態(1-minimal)で終える。

DDMINの例

例えば、以下の入力でFailが出たとします。

C =  [a, b, c, d, e, f, g, h]

ここで、実はdとfの組み合わせでバグが発生するとしましょう。

1-1. 分割(n=2)

    O1 = [a, b, c, d], O2 = [e, f, g, h]

1-2. 分割したそれぞれの塊をテスト

    dとfの組み合わせでバグが出るのですから、O1もO2もPassになります。

1-3. 補集合のテスト

    n=2の場合、O1の補集合はO2、O2の補集合はO1ですので全てPassです。

1-4. n=4にして1.に戻ります。

2-1. 分割(n=4)

    O1 = [a, b], O2 = [c, d], O3 = [e, f], O4 = [g, h]

2-2. 分割したそれぞれの塊をテスト

    O1, O2, O3, O4それぞれをテストします。dとfの組み合わせでバグが発生するので全てPassになります。

2-3. 補集合のテスト

    補集合1 = [c, d, e, f, g, h] のテストを行います。dとfの組み合わせで不具合が発生するのでFailとなります。

2-4. C = [c, d, e, f, g, h]を対象に、n=2に戻して1.に戻ります。

    この流れを繰り返します。

5. 最後 C = [d, f]の状態になると、dを抜いてもfを抜いてもFailが発生しなくなります。

    これが1-minimalの状態です。これで最小失敗ケースの特定が終了になります。

二分探索との違い

分割数がn=2のときは二分探索と同じ意味になります。ですが、nを増やしたときに部分と補集合の両方を試すことにより不要部分をそぎ落すという点に違いがあります。またnを増減することで粒度調整をするため、単純な二分探索よりも組み合わせ（相互作用）に強いと言えます。

事例 : 操作ログから最小失敗ケースを特定

Mozillaである操作を行うとクラッシュするというバグがありました。当初の再現手順はユーザーの操作ログで95操作でした。
そこで、クリック/文字入力/メニュー操作など1操作を1要素として扱い、その操作を複数に分割して自動リプレイを行い、Pass/Failを判定するという方法でDDMIN法を適用しました。

結果、95操作のログから、［例：特定メニューの選択 → 特定文字列の入力 → ボタンのクリック］という3操作が組み合わさると必ずクラッシュするという最小失敗ケースを特定しました。
（Zeller & Hildebrandt 2002）

新人さんからわかるソフトウェアテスト解説マンガやYouTubeチャンネルも公開中です。

よろしければこちらもご覧ください。

• マンガでわかるソフトウェアテスト入門テスターちゃん
• YouTube「テスターちゃんねる」

参照論文

Zeller, A. and Hildebrandt, R., “Simplifying and Isolating Failure-Inducing Input,” IEEE Transactions on Software Engineering, 28(2), pp.183–200, 2002. doi:10.1109/32.988498.
Available at: https://www.st.cs.uni-saarland.de/papers/tse2002/tse2002.pdf