[Paper] 扩展 Delta Debugging 最小化用于基于光谱的故障定位

Source: arXiv - 2601.04689v1

概述

本文提出了 DDMIN‑LOC，一种将 Delta Debugging Minimization（DDMIN）与 Spectrum‑Based Fault Localization（SBFL）相结合的新技术。通过利用 DDMIN 生成的最小导致失败的输入并将其输入 SBFL，该方法即使在仅有单个失败测试用例的情况下，也能定位可疑的代码位置——尤其适用于处理字符串输入的程序。

关键贡献

• 混合故障定位流水线：引入 DDMIN‑LOC，它通过 DDMIN 自动生成一套通过/失败的输入，并将其提供给 SBFL 算法。
• 单一失败输入需求：仅需一个观察到的失败，即可工作，省去大量测试框架的需求。
• 广泛的 SBFL 兼容性：使用五种流行的 SBFL 公式进行评估（Tarantula、Ochiai、GenProg、Jaccard、DStar）。
• 实证验证：在来自 QuixBugs 和 Codeflaws 基准的 136 个真实错误程序上进行测试，显示错误语句常常排名在前 3 位。
• 实际效率：在大多数情况下，开发者只需检查不到可执行行的 20 % 即可定位错误。

方法论

1. 输入最小化 (DDMIN)
   • 从单个导致失败的字符串输入开始。
   • 系统地删除或缩减输入的部分（例如字符、子串），同时保持失败不变，收敛到 最小 的诱发失败的输入。
2. 测试套件生成
   • DDMIN 产生的每个中间输入都在程序上执行。
   • 结果标记为 passing（通过，未崩溃）或 failing（崩溃/复现错误）。
3. 光谱收集
   • 对每次执行，工具记录哪些语句和谓词被执行。
   • 这产生一个覆盖矩阵，将输入（行）与程序元素（列）关联起来。
4. SBFL 评分
   • 将覆盖矩阵和通过/失败标签输入经典的 SBFL 公式（例如 Jaccard）。
   • 每条语句得到一个 可疑度 分数，反映它在失败运行与通过运行中出现的频率差异。
5. 排序与展示
   • 可以将多个 SBFL 公式的分数合并（例如取平均）或单独查看。
   • 最终的排序列表呈现给开发者，排名最高的语句最有可能是故障位置。

结果与发现

• Jaccard 始终优于其他公式，通常在检查不到五分之一的代码后即可定位错误。
• 在所有基准测试中，无论使用哪种失败输入种子，错误语句几乎总是出现在排名前三的位置。
• 即使初始失败输入非常复杂（例如包含嵌套结构的长字符串），该方法仍保持稳健。

实际意义

• Rapid Debugging for Input‑Driven Apps: 处理文本数据的工具（解析器、编译器、配置加载器、Web API）可以集成 DDMIN‑LOC，从单个崩溃报告自动生成聚焦的“调试检查清单”。
• Lightweight CI Integration: 只需一个失败的测试，CI 流水线即可在任何意外失败时触发 DDMIN‑LOC，而无需完整的回归套件。
• Enhanced Developer Tooling: IDE 插件可以直接在编辑器中显示排名最高的可疑代码行，缩短寻找根本原因的时间。
• Security Vulnerability Triage: 对于发现崩溃的模糊测试活动，DDMIN‑LOC 能快速定位易受攻击的代码区域，加速补丁开发。
• Educational Use: 学习调试的学生可以看到系统化的输入缩减如何与覆盖率分析结合，产生可操作的洞见。

限制与未来工作

• String‑Input Restriction: 当前实现假设程序的主要输入是字符串；二进制或多模态输入需要预处理或使用不同的最小化器。
• Scalability of DDMIN: 对于极大的输入，迭代最小化可能会耗时；自适应采样或并行执行可以缓解此问题。
• SBFL Formula Sensitivity: 虽然在研究中 Jaccard 表现最佳，但最佳公式可能因领域而异；可以探索自动选择器。
• Dynamic Features: 严重依赖反射、JIT 编译或外部状态（文件、网络）的程序可能产生噪声光谱，降低定位准确性。
• Future Directions: 将 DDMIN‑LOC 扩展以通过语法感知的最小化处理结构化输入（JSON、XML），集成基于机器学习的排序，并在更大、工业级代码库上进行评估。

作者

• Charaka Geethal Kapugama

论文信息

• arXiv ID: 2601.04689v1
• 分类: cs.SE
• 出版时间: 2026年1月8日
• PDF: 下载 PDF