> [!abstract] 概要 > テストケースが与えられ、プログラムが失敗する。テストケースのどの状況が特定の障害に関与しているのか。デルタデバッギングアルゴリズムは、ある障害を引き起こすテストケースを、なお障害を再現する最小テストケースへ汎化・簡略化する。また、通過テストケースと失敗テストケースの差分を分離する。事例研究では、Mozilla ウェブブラウザが 95 のユーザー操作後にクラッシュした。プロトタイプ実装はこの入力を自動的に 3 つの関連ユーザー操作に簡略化した。同様に、896 行の HTML を障害を引き起こす 1 行に簡略化した。この事例研究では 139 回の自動テスト実行、すなわち 500 MHz PC 上で 35 分を要した。 ## 論文情報 - **タイトル**: Simplifying and Isolating Failure-Inducing Input - **著者**: [[Andreas Zeller]]（Universität des Saarlandes）、Ralf Hildebrandt（DeTeLine） - **媒体**: IEEE Transactions on Software Engineering, Vol. 28, No. 2 - **発表年**: 2002年2月 ## 概要 デルタデバッギングは、プログラムの障害を引き起こす入力を自動的に簡略化・分離する手法である。2 つのアルゴリズムを提案する。ddmin は障害を引き起こすテストケースを 1-最小（任意の単一変更を除去すると障害が消える）になるまで簡略化する。dd は ddmin を拡張し、通過テストケースと失敗テストケースの間の 1-最小障害誘発差分を分離する。 ## 問題設定 - **入力**: 障害を引き起こすテストケース c✘（変更の集合）と、正常に動作するテストケース c✔（通常は空入力） - **出力**: ddmin では c✘ の 1-最小部分集合、dd では c✔ と c✘ の間の 1-最小差分 - **前提**: テスト関数 test が各テストケースに対して PASS（✔）、FAIL（✘）、UNRESOLVED（?）のいずれかを返す。入力は変更 δ₁, ..., δₙ に分解可能 ## 提案手法 ### ddmin: 最小化デルタデバッギングアルゴリズム テストケースを n 個の部分集合 Δ₁, ..., Δₙ に分割し、以下の 4 規則を再帰的に適用する。 1. **部分集合への縮小**: いずれかの Δᵢ 単独でテストが失敗すれば、Δᵢ を新たなテストケースとして粒度 n=2 で再帰 2. **補集合への縮小**: いずれかの ∇ᵢ = c'✘ \ Δᵢ でテストが失敗すれば、∇ᵢ を新たなテストケースとして粒度 n−1 で再帰 3. **粒度の増加**: いずれのテストも失敗しなければ、部分集合数を 2n に倍増して再試行 4. **完了**: 粒度が |c'✘| に達したら（各部分集合が単一変更）、結果は 1-最小 **Figure 5: ddmin アルゴリズムの形式定義** ![[_attachments/delta-debugging/fig05-ddmin-algorithm.png]] (Figure 5. 最小化デルタデバッギングアルゴリズム ddmin の形式定義。4 つの分岐規則と再帰不変条件を示す。) ### dd: 汎用デルタデバッギングアルゴリズム ddmin を拡張し、失敗テストケースの縮小だけでなく通過テストケースの拡大も行う。テストが通過するたびに通過テストケース c'✔ を拡大し、失敗するたびに c'✘ を縮小する。ddmin の 4 規則に加え、2 つの規則を追加する。 5. **補集合への増加**: c'✘ \ Δᵢ が通過すれば、c'✘ \ Δᵢ を新たな通過テストケースとして採用 6. **部分集合への増加**: c'✔ ∪ Δᵢ が通過すれば、c'✔ ∪ Δᵢ を新たな通過テストケースとして採用 **Figure 15: dd アルゴリズムの形式定義** ![[_attachments/delta-debugging/fig15-dd-algorithm.png]] (Figure 15. 汎用デルタデバッギングアルゴリズム dd の形式定義。ddmin を拡張し、通過テストケースの拡大規則を加えた 6 分岐。) ### 簡略化と分離の違い - **簡略化**（ddmin）: テストケースの各部分を関連性ある（除去すると障害が消える）ものにする - **分離**（dd）: テストケースの 1 つの関連部分を特定する（その特定部分を除去すると障害が消える） 分離は簡略化より効率的だが、プログラマが通過テストケースの共通文脈を念頭に置く必要がある。 ## 新規性 - テストケース簡略化を自動化した**最初の汎用手法**。従来は手動の二分探索か、特定ドメイン向けの手法しかなかった - ddmin と dd の 2 アルゴリズムにより、簡略化（全要素の関連性確認）と分離（単一の障害誘発差分の特定）の両方を形式化 - 先行研究 dd' (Zeller, 1999) との差異: dd' は単調性を仮定し 1-最小性を保証しない。dd は単調性を仮定せず 1-最小差分を保証 ## 実験設定 - **実験環境**: Linux PC、500 MHz Pentium III。WYNOT プロトタイプ実装 - **対象プログラム**: GCC 2.95.2、Mozilla（Netscape 6 相当）、UNIX ユーティリティ 6 種（NROFF、TROFF、FLEX、CRTPLOT、UL、UNITS） - **テストケース**: GCC バグ（C ソースコード）、Mozilla バグ #24735（HTML + ユーザー操作）、Miller のファズ入力（10³〜10⁶ 文字、16 種） - **評価指標**: 最小化後の入力サイズ、テスト実行回数、テスト精度（低精度 vs 高精度=バックトレース比較） **Figure 8: GCC 入力 bug.c の最小化過程** ![[_attachments/delta-debugging/fig08-gcc-minimization.png]] (Figure 8. GCC 入力 bug.c の最小化過程。横軸はテスト実行回数、縦軸は入力サイズ。755 文字から 77 文字へ約 800 回のテストで簡略化。) ## 実験結果 ### GCC - 755 文字の C プログラム → **77 文字**の 1-最小テストケースに簡略化（731 テスト、34 秒） - dd による分離では **59 テスト**で 2 文字の障害誘発差分を特定（ddmin の 731 テストに対し大幅削減） - GCC 最適化オプション 31 個の中から、障害を防ぐオプション（`-ffast-math`、`-fforce-addr`）を 7 テストで特定 ### Mozilla - 711 の X イベント中 95 のユーザー操作 → **3 操作**に簡略化（82 テスト、21 分） - 896 行の HTML → **1 行** `<SELECT NAME="priority" MULTIPLE SIZE=7>` に簡略化（57 テスト） - 文字単位の追加簡略化で `<SELECT>` の 8 文字に到達 - dd による分離では **7 テスト**で 1 文字 `<` が障害誘発差分として特定 ### UNIX ファズ入力 - 6 ユーティリティ × 16 ファズ入力 = 96 テスト中 42 回（43%）クラッシュ - バッファオーバーラン型（FLEX: 2,121 文字、UL: 516 文字）と不正コマンド型（NROFF: 2 文字、CRTPLOT: 1 文字）に分類 - 高精度テスト（バックトレース比較）では最小化結果が大きくなる（NROFF: 低精度 2 文字 → 高精度 60 文字） - dd は ddmin に比べ大幅にテスト回数を削減。ファズ入力でも dd は対数的テスト回数で 1 文字差分を分離 **Figure 6: 粒度増加を伴うテストケース最小化の詳細例** ![[_attachments/delta-debugging/fig06-minimization-example.png]] (Figure 6. 変更 1, 7, 8 が最小テストケースとなる例。粒度を 2→4→8 と増加させながら、各部分集合とその補集合をテストする 19 ステップの過程。) **Figure 16: GCC 入力の障害誘発差分の絞り込み** ![[_attachments/delta-debugging/fig16-narrowing-difference.png]] (Figure 16. dd アルゴリズムによる障害誘発差分の絞り込み。59 テストで通過テストケースと失敗テストケースの差分が 2 文字に収束する過程。) **Figure 17: 特定された障害誘発差分** ![[_attachments/delta-debugging/fig17-failure-inducing-difference.png]] (Figure 17. 特定された障害誘発差分。`mult` 関数内の `i = i + j + 1;` の代入を除去すると障害が消えることを示す。) ## 考察 - テスト精度の選択がトレードオフを生む。高精度（バックトレース完全一致）では最小化結果が大きくなるが、元の障害と同一の障害を再現する。低精度では別の障害に収束する可能性がある - 分離（dd）は簡略化（ddmin）より常に効率的だが、結果の解釈にプログラマの文脈理解が必要 - 入力構造の知識（文法など）を活用すれば、構文的に妥当な部分集合のみを生成でき、UNRESOLVED の削減と性能向上が期待できる（本論文では未実装） - プログラム解析（スライシング）との相補性: 解析は因果関係を否定（依存関係のない文を除外）し、テストは因果関係を証明（変更による障害消失を確認）する ## 強み / 弱点・課題 ### 強み - 入力構造に関する事前知識を必要としない汎用手法 - 1-最小性の形式的保証と計算量の理論的解析 - GCC・Mozilla・UNIX ユーティリティへの実証で実用性を示した - 自動回帰テストとの統合が容易（障害検出 → 自動簡略化のパイプライン） ### 弱点・課題 - 最悪計算量が O(n²) で、大規模入力（FLEX の 6,749 文字ファズ入力で 37,000 テスト以上）では実用的でない場合がある - 入力を平坦な原子リストとして扱うため、木構造入力（XML、AST）では効率が悪い（→ HDD [[@2006__ICSE__HDD - Hierarchical Delta Debugging]] で解決） - 単調性の欠如（変更の取り消しが可能な場合）への対処は未解決。`<A></A><B>` の例で、`</A>` が `<A>` の障害を取り消すケースが指摘されている - テスト関数が決定論的再現を前提としており、非決定論的障害への適用は困難