Deep Dive into Probabilistic Delta Debugging: Insights and Simplifications

给定一个元素列表L和L表现出的属性，ddmin是一个广泛采用于测试输入最小化和软件去膜的自动消除无关元素的测试输入最小化算法。最近，ProbDD作为ddmin的一个高级变体被提出并取得了最先进的性能。ProbDD利用贝叶斯优化预测L中每个元素是必要的可能性，并统计决定每次应该移除哪些元素以及多少个元素。尽管其结果令人印象深刻，但ProbDD的理论概率模型很复杂，其驱动其卓越性能的具体因素尚未得到研究。 在本文中，我们进行了ProbDD的首次深入理论分析，澄清了概率和子集大小变化趋势，同时简化了概率模型。为了补充这一分析，我们进行了实证实验，包括成功率分析、消融研究以及权衡和限制分析，以更好地理解和揭示这一最先进算法。我们的成功率分析展示了ProbDD如何通过跳过试图删除子集补集和先前尝试过的子集的低效查询来解决ddmin的瓶颈问题。消融研究揭示了ProbDD中的随机性对效率没有显著影响。 基于这些发现，我们提出了CDD，ProbDD的简化版本，同时简化了理论和实现的复杂性。此外，CDD的性能验证了我们的关键发现。在测试输入最小化和软件去膜的76个基准测试中进行全面评估，结果显示尽管简化了，CDD可以实现与ProbDD相同的性能。这些见解为未来测试输入最小化算法的研究和应用提供了有价值的指导。

论文旨在深入理解ProbDD算法的性能优势和概率模型，以及简化其复杂性并提出一种新算法CDD。

ProbDD算法通过贝叶斯优化预测每个元素在测试输入中的重要性，并统计决定每次删除哪些元素。CDD算法是ProbDD的简化版本，通过减少理论和实现上的复杂性来提高性能。

论文进行了成功率分析、消融研究和分析权衡和限制等实验，发现ProbDD算法通过跳过无效查询来解决ddmin算法的瓶颈，随机性对效率没有显著影响。CDD算法在测试输入最小化和软件去膜的76个基准测试中表现良好。

最近的相关研究包括ddmin算法和其他测试输入最小化算法。