@2006__ICSE__HDD - Hierarchical Delta Debugging

# HDD: Hierarchical Delta Debugging > [!abstract] 概要 > プログラムを失敗させる入力は通常大規模であり、しばしば障害と無関係な情報を含む。そのため、入力を単純化することがデバッグの助けになる。Delta Debugging アルゴリズムは、失敗誘発入力をすべて最小化するために適用可能な汎用的な技術である。本論文では HDD、すなわち木構造入力(XML など)に対して Delta Debugging を大幅に高速化し、かつ出力品質を向上させるシンプルだが効果的なアルゴリズムを提案する。入力を一つのフラットなアトミックリストとして扱う代わりに、データの構造そのものに対して Delta Debugging を適用する。特に、元の Delta Debugging アルゴリズムを入力の各レベルに対して、最も粗いレベルから最も細かいレベルへと順に適用する。これにより、入力の大きな無関係部分を早期に取り除ける。生成されるすべての入力設定は構文的に正しく、不確定な設定のテストに費やす時間を削減する。HDD を実装し、GCC および Mozilla のバグ報告データベースから得た実際の失敗誘発入力で評価した結果、HDD は元の Delta Debugging アルゴリズムよりも桁違いに少ないテストケース数で、より小さく出力できることを確認した。 ## 論文情報 | 項目 | 内容 | |---|---| | タイトル | HDD: Hierarchical Delta Debugging | | 著者 | [[Ghassan Misherghi]]、[[Zhendong Su]] | | 所属 | Department of Computer Science, University of California, Davis | | 会議 | ICSE 2006(May 20–28, 2006, Shanghai, China) | | 出版 | ACM, ISBN 1-59593-085-X | | URL | https://www.cs.purdue.edu/homes/xyzhang/fall07/Papers/hdd.pdf | ## 概要プログラマはデバッグに多くの時間を費やす。ソフトウェアメンテナンスはあらゆるプログラミング活動の中で最も時間を要するとされており、失敗を引き起こすテストケースを最小化することがデバッグを簡略化する上で有効である。Delta Debugging(ddmin)はこの作業を自動化するが、入力が XML や C プログラムのように木構造(階層構造)を持つ場合、フラットなリスト扱いでは非効率になる。 HDD はこの問題を解決するために、入力の階層構造をそのままデルタデバッギングに活かす手法を提案する。木の各レベルを粗いものから細かいものへと順に ddmin で最小化することで、上位レベルで大きなサブツリーを早期に除去し、テスト回数を劇的に削減する。先行研究: [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]](Zeller & Hildebrandt 2002)の ddmin アルゴリズムが基盤。HDD は ddmin を木構造に拡張したものと位置付けられる。 ## 問題設定 - **入力サイズの問題**: 失敗を誘発するテストケースは通常大きく、デバッグに不要な情報を多数含む。 - **ddmin の限界**: 元の Delta Debugging アルゴリズムは入力をフラットなリストとして扱う。XML や C プログラムのような木構造入力では、構文的に無効な中間設定(タグの片方だけ削除など)が多数生成され、テストのほとんどが「不確定(inconclusive)」に終わる。ddmin は正規言語向きだが、文脈自由文法で記述される言語には HDD が適している。 - **ユースケース**: プログラミング言語(コンパイラへの入力としての AST)・HTML/XML・ビデオコーデック・UI インタラクション記録など、文脈自由文法で定義される再帰的なデータ構造を持つ入力全般。 ## 提案手法 ### HDD アルゴリズム HDD はパース済みの入力木を受け取り、以下のステップを繰り返す: 1. **初期化**: 木のレベル 0(ルート直下)から開始する。 2. **ノードのタグ付け**: 現在のレベルにあるすべてのノードを列挙して識別子を付与する(`TAG_NODES`)。 3. **最小設定の発見**: 現在のレベルのノード集合に対して `DDMIN` を実行し、失敗を誘発する最小設定 `minconfig` を求める。 4. **プルーニング**: `minconfig` に含まれないノードを木から除去する(`PRUNE`)。 5. **次のレベルへ**: レベルをインクリメントし、ノードが存在する限り Step 2 へ戻る。 ``` procedure HDD(input tree): level ← 0 nodes ← TAG_NODES(input tree, level) while nodes ≠ ∅ do minconfig ← DDMIN(nodes) PRUNE(input tree, level, minconfig) level ← level + 1 nodes ← TAG_NODES(input tree, level) end while ``` このアルゴリズムでは、上位レベルで多くの不要なサブツリーを一度に除去できるため、下位レベルで処理すべきノード数が大幅に減少する。 ### 直感的な例下図は、架空の C プログラムの AST に HDD を適用する例を示す。 **図2a: 元の AST** ![[wiki/sources/_attachments/hdd/image-003-001.png]] **図2b: HDD 適用後の最小化 AST** ![[wiki/sources/_attachments/hdd/image-003-002.png]] **図3: 最初の反復後の AST(第1レベルを最小化した状態)** ![[wiki/sources/_attachments/hdd/image-004-001.png]] HDD は第1レベルで `f()` のみが必要と判定し、その後のレベルで `int y`・`while` ループとその本体(`y--`)のみが必要と判定する。結果として `f() { int y; while (0) { y--; } }` という最小プログラムが得られる。 ### HDD+・HDD* - **HDD+**: HDD の貪欲フェーズ後に、木のノードを BFS 順に1個ずつ除去しようとする1-tree-最小性保証フェーズを追加。最悪 O(n²) 回のテストを実行。 - **HDD\***: HDD を繰り返し呼び出し、1回の呼び出しで1つも除去できなくなるまで続ける。最悪 O(n³) だが実際には HDD+ と大差ないことが多い。 ### 構文的有効性の保持 HDD は木操作の際に構文的に正しい設定のみを生成することを意図している。これは「木操作モジュール(tree manipulator)」が担う。必須の子ノードを持つノード(例: `while` 文の条件)については、削除ではなく最小の代替フラグメント(例: `0`)を挿入することで対処する。 ## 新規性 ### ddmin との本質的な違い | 観点 | ddmin | HDD | |---|---|---| | 入力の扱い | フラットなリスト | 木の各レベルを独立に処理 | | 生成する設定の構文的正しさ | 保証なし(多くの無効設定が生成) | 原則として構文的に正しい設定のみ | | 得意な言語クラス | 正規言語 | 文脈自由言語 | | 最小性保証 | 1-minimal | 1-tree-minimal を保証しない(HDD+/HDD* は保証) | | 実際のテスト回数 | ddmin 基準 | 構造的な入力ではほぼ桁違いに少ない | ### 最小性の理論的分析グローバル最小性(GMT: Global tree Minimality problem)は NP 完全であることが証明された。ヒッティング集合問題(NP 完全)からの多項式時間帰着による証明。したがって、HDD も ddmin も大域最小性は目指さず、局所的な最小性(1-tree-minimal)を目標とする。 HDD 自体は 1-minimal や 1-tree-minimal を保証しない(上位レベルで除去後、下位レベルの要素がその上位レベルで再度除去されない)。ただし実際には ddmin より良い出力品質を示すことが多い。 ## 実験設定実験は2つの設定で行われた: ### GCC 実験 - GCC 2.95.2 のバグを誘発する C プログラムに対して適用。 - AST 操作モジュールを Elsa(C/C++ パーサー)の拡張として実装。 - テストケース: `bug.c`(277 トークン)、`boom7.c`(420 トークン)、`cache.c`(25011 トークン)、`cache-min.c`(145 トークン)。 - 比較対象: ddmin、HDD、HDD*。 ### XML 実験(Mozilla) - Mozilla ウェブブラウザの XML 処理バグ(セグメンテーション障害)を誘発する XSLT 文書に適用。 - XML ツリー操作モジュールを DOM API を用いた 150 行未満の Python コードで実装。 - テストケース: `ms-tour.xsl`(433 行)、`uiwrapperauto.xsl`(66 行)。 - 比較対象: ddmin、ddmin-line、HDD、HDD*。 ## 実験結果 ### GCC 結果(表1) | ファイル | サイズ(トークン) | ddmin テスト数 | HDD テスト数 | HDD\* テスト数 | ddmin 出力サイズ | HDD 出力サイズ | HDD\* 出力サイズ | |---|---|---|---|---|---|---|---| | bug.c | 277 | 680 | 86 | 164 | 53 | 51 | 51 | | boom7.c | 420 | 3727 | 144 | 304 | 102 | 57 | 19 | | cache.c | 25011 | 1743 | 191 | 327 | 62 | 61 | 58 | | cache-min.c | 145 | 1074 | 114 | 182 | 71 | 59 | 59 | HDD は概ね 1 桁以上少ないテスト回数で、同等以下のサイズの出力を生成する。`boom7.c` では ddmin の出力(`102 トークン`)に対して HDD は `57 トークン`、HDD\* は `19 トークン`と大幅に小さい。`cache.c`(25011 トークン)は ddmin でも処理可能だったが、HDD は 9 分の 1 以下のテスト回数で達成。 ### XML 結果(表2) | ファイル | サイズ(行) | ddmin テスト数 | HDD テスト数 | ddmin 出力(行) | HDD 出力(行) | |---|---|---|---|---|---| | ms-tour.xsl | 433 | 失敗(メモリ枯渇) | 124 | — | 8 | | uiwrapperauto.xsl | 66 | 5757 | 105 | 46 | 15 | `ms-tour.xsl`(433 行の XSLT)では ddmin が 4GB RAM を使い切ってメモリ枯渇に陥り最小化に失敗したのに対し、HDD は 124 テストで 8 行の出力に成功。出力サイズで 10 倍以上の差が生じた。 ## 考察 - HDD が有効なのは「入力の構造と失敗箇所が階層的に整理されている」場合である。木が深くバランスが良いほど、上位レベルで大量のサブツリーを一掃でき、テスト回数が劇的に減少する。 - 逆に、`cache.c` のように大量のヘッダファイルのプロトタイプがフラットに並ぶ場合は、1レベル目がほぼフラットリストになり HDD の利点が薄れる。それでも HDD は ddmin より1桁以上少ないテスト回数を達成している。 - XML は「厳密な文脈自由文法」「深いネスト」「タグペアの対称性」という特性から HDD にとって理想的な対象であり、実験でも顕著な差が見られた。 - ddmin の出力は構文的に不正になることがある(例: `(long int)(signed short) (var0=9>(var1=var1=8))"""`という非パーサブルな文字列)のに対し、HDD は常に構文的に正しい出力を生成する。 ## 強み / 弱点・課題 ### 強み - 木構造入力に対して ddmin より桁違いに少ないテスト回数で高品質な最小化が可能。 - 生成される設定が構文的に正しいため、パーサーが早期に失敗する「不確定」テストが大幅に減少する。 - XML では 150 行未満の Python コードで実装可能なほど、木操作モジュールの実装が比較的容易。 - 出力が元の構造に近い形を保つため、開発者が読みやすい。 ### 弱点・課題 - **木操作モジュールの実装コスト**: パーサー・アンパーサー・プルーニングの実装が各言語で必要。C/C++ では Elsa パーサーの拡張でも多くの制限があり実装が煩雑だった。 - **レベル間の依存関係**: 異なるレベルのノード間に依存関係がある場合(例: C の変数宣言と参照が異なる深さ)、HDD が依存をまたぐ最小化に失敗することがある。HDD* の複数回実行で部分的に解決可能。 - **1-tree-最小性の非保証**: HDD 基本版は 1-minimal も 1-tree-minimal も保証しない。HDD+・HDD* は保証するが追加テストコストが発生する。 - **文脈自由文法からの自動生成が困難**: CFG から木操作ルーティンを自動生成するアイデアは有望だが、リスト構造のフラット化や構文的妥当性の保証といった課題が残る。 - **Elsa パーサーの制限**: 特定のリスト型が不変(immutable)であるなど、実装上の制約があった。 ## 関連 - [[Ghassan Misherghi]] — 筆頭著者、UC Davis - [[Zhendong Su]] — 共著者、UC Davis - [[階層的デルタデバッギング]] — 本論文が提案するアルゴリズムの概念ページ - [[@2002__IEEE TSE__Simplifying and Isolating Failure-Inducing Input]] — Zeller & Hildebrandt の ddmin(基盤となる先行研究)