## 定義 デルタデバッギング（Delta Debugging）は、プログラムの障害を引き起こす入力（テストケース）を自動的に簡略化・分離する手法である。[[Andreas Zeller]] と Ralf Hildebrandt が 2002 年に提案した（[[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]]）。2 つの核心アルゴリズムからなる。 - **ddmin**: 障害テストケースを 1-最小（任意の単一変更を除去すると障害が消える）になるまで簡略化する。テストケースを n 個の部分集合に分割し、部分集合のテスト → 補集合のテスト → 粒度増加 → 完了の 4 規則を再帰適用する。最悪計算量 O(n² + 3n)、最良 O(log n)。 - **dd**: ddmin を拡張し、通過テストケースと失敗テストケースの間の 1-最小障害誘発差分を分離する。通過テストケースの拡大規則を追加し、両端から差分を狭めるブランチ・アンド・バウンド的探索を行う。UNRESOLVED が無ければ O(log n) で単一の障害誘発変更を特定。 核となる前提: テスト関数 test が PASS / FAIL / UNRESOLVED を返し、入力は変更の集合に分解可能であること。入力構造の事前知識は不要だが、構造知識があれば性能が向上する。 ## 横断的知見 - ddmin は入力を平坦な原子リストとして扱うため、木構造入力（XML、AST、HTML DOM）では大量の構文的に不正なテストケースが生成され、UNRESOLVED が増加して効率が悪化する。HDD（[[@2006__ICSE__HDD - Hierarchical Delta Debugging]]）は入力の木構造をレベルごとに ddmin に適用することでこの問題を解決し、桁違いのテスト回数削減を達成した（Source: [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]], [[@2006__ICSE__HDD - Hierarchical Delta Debugging]]） - デルタデバッギングの「テストケース最小化」パラダイムは逐次プログラムの入力から分散システムの実行へと拡張された。DEMi（[[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]]）は外部イベント（障害注入）と内部イベント（メッセージ送受信）を区別し、スケジュール探索を組み合わせることで分散実行の最小化を実現した（Source: [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]], [[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]]） - テスト精度と最小化結果のトレードオフは本質的である。低精度（クラッシュの有無のみ）では小さい結果が得られるが別の障害に収束する可能性があり、高精度（バックトレース完全一致）では結果が大きくなるが元の障害を保持する。この精度設計は後続研究でも再帰的に現れる課題である（Source: [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]]） ## 未解決の問い - 非決定論的障害（並行性バグ、タイミング依存バグ）に対するデルタデバッギングの適用方法。テスト関数が決定論的再現を前提としており、再現困難なバグへの拡張は open - 変更の取り消し（undoing changes）問題: `<A></A><B>` のように、ある変更が別の変更の障害を取り消す場合、簡略化結果が誤った障害原因を指す可能性がある。単調性の欠如への体系的対処は未解決 - プログラム解析（スライシング）とデルタデバッギングの体系的統合: 解析で候補を絞り、テストで因果を証明する相補的アプローチの実用的フレームワーク ## 関連 - [[階層的デルタデバッギング]] — 木構造入力への拡張（HDD） - [[分散実行最小化]] — 分散システムへの拡張（DEMi） - [[Fault Localization]] — 障害箇所特定の上位概念 - [[根本原因分析]] — 根本原因診断との関係 ## 出典 - [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]] - [[@2006__ICSE__HDD - Hierarchical Delta Debugging]] - [[@2016__NSDI__Minimizing Faulty Executions of Distributed Systems]]