# 階層的デルタデバッギング ## 定義 階層的デルタデバッギング(Hierarchical Delta Debugging; HDD)は、[[Ghassan Misherghi]] と [[Zhendong Su]] が ICSE 2006 で提案したアルゴリズムである([[@2006__ICSE__HDD - Hierarchical Delta Debugging]])。元の Delta Debugging アルゴリズム(ddmin; [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]]、Zeller & Hildebrandt 2002)が入力をフラットなリストとして扱うのに対し、HDD は木構造入力の各レベルを粗いものから細かいものへと順に ddmin にかける。これにより、上位レベルで不要なサブツリーを一括除去することが可能になり、テストケース数を大幅に削減するとともに、構文的に正しい設定のみを生成できる。 主な特徴: - XML や C プログラム(AST)など、文脈自由文法で記述される木構造入力に適用可能。 - 最悪計算量は ddmin と同じ O(n²) だが、木が深くバランスが良いほど実際のテスト回数は桁違いに少なくなる。 - グローバル最小性の決定問題(GMT)は NP 完全であり、HDD も 1-tree-minimal を基本的に保証しない(HDD+・HDD* 変種は保証するが追加コストが発生する)。 ## 横断的知見 (複数ソースの突き合わせによる知見を蓄積。現時点では HDD の初回 ingest のみ) - HDD を提案した論文自身の評価(GCC・Mozilla の実障害データ)で、ddmin に対してテスト回数で概ね 1 桁以上の削減、出力サイズでも同等以下を達成した。特に XML では ddmin がメモリ枯渇(4GB)で失敗するケースで HDD は 124 回のテストで 8 行への最小化に成功している。(Source: [[@2006__ICSE__HDD - Hierarchical Delta Debugging]]) - ddmin は正規言語向き、HDD は文脈自由言語向きという「言語クラスと手法の適合関係」は、後続の自動テスト最小化研究の重要な知見となっている。(Source: [[@2006__ICSE__HDD - Hierarchical Delta Debugging]]) ## 未解決の問い - HDD 以降のテスト最小化研究(Creduce、Perses、Tree-sitter ベース等)は HDD のどの限界を解決したか？特に「木操作モジュール実装コスト」問題はどの程度自動化されたか？ - HDD が木構造入力について ddmin より有効であることは実証されたが、グローバル最小性との乖離はどの程度か？実際のバグ解析でどの程度問題になるか？ - HDD を LLM 時代のテスト最小化・プロンプト最小化に応用できるか？LLM への入力もある種の構造を持つため、HDD 的な階層的最小化が有効な可能性がある。 - ICSE 2006 以降に HDD が引用・改善された代表的な後継研究はどれか？ ## 関連 - [[@2006__ICSE__HDD - Hierarchical Delta Debugging]] — 提案論文(Misherghi & Su, ICSE 2006) - [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]] — 元の Delta Debugging(ddmin; Zeller & Hildebrandt 2002) - [[Ghassan Misherghi]] — 提案者(筆頭著者) - [[Zhendong Su]] — 提案者(共著者) ## 出典 - [[@2006__ICSE__HDD - Hierarchical Delta Debugging]] — Misherghi & Su, ICSE 2006