一句话：首次理论解析 ProbDD，并提出简化算法 CDD，在 76 个基准上保持同等性能。
ddmin 是经典测试输入最小化算法，用于从输入列表 L 中删除与性质 ψ 无关的元素；其变体 ProbDD 借助贝叶斯优化估计元素相关性并达到当前最优性能，但其概率模型复杂、性能来源未被充分解释。本文首次对 ProbDD 做深入理论分析，阐明概率与子集规模的变化趋势并简化概率模型，辅以成功率分析、消融实验及权衡与局限考察。结果揭示 ProbDD 通过跳过删除子集补集和已尝试子集等低效查询来突破 ddmin 瓶颈，且随机性对效率无显著影响。基于此，作者提出简化算法 CDD；在测试输入最小化与软件去膨胀的 76 个基准上，CDD 达到与 ProbDD 相同性能。
Given a list$L$of elements and a property$\psi$that$L$exhibits, ddmin is a classic test input minimization algorithm that aims to automatically remove$\psi$-irrelevant elements from$L$. This algorithm has been widely adopted in domains such as test input minimization and software debloating. Recently, ProbDD, a variant of ddmin, has been proposed and achieved state-of-the-art performance. By employing Bayesian optimization, ProbDD estimates the probability of each element in$L$being relevant to$\psi$, and statistically decides which and how many elements should be deleted together each time. However, the theoretical probabilistic model of ProbDD is rather intricate, and the underlying details for the superior performance of ProbDD have not been adequately explored. In this paper, we conduct the first in-depth theoretical analysis of ProbDD, clarifying the trends in probability and subset size changes and simplifying the probability model. We complement this analysis with empirical experiments, including success rate analysis, ablation studies, and examinations of trade-offs and limitations, to further comprehend and demystify this state-of-the-art algorithm. Our success rate analysis reveals how ProbDD effectively addresses bottlenecks that slow down ddmin by skipping inefficient queries that attempt to delete complements of subsets and previously tried subsets. The ablation study illustrates that randomness in ProbDD has no significant impact on efficiency. These findings provide valuable insights for future research and applications of test input minimization algorithms. Based on the findings above, we propose CDD, a simplified version of ProbDD, reducing the complexity in both theory and implementation. CDD assists in 1 validating the correctness of our key findings, e.g., that probabilities in ProbDD essentially serve as monotonically increasing counters for each element, and 2 identifying the main factors that truly contribute to ProbDD's superior performance. Our comprehensive evaluations across 76 benchmarks in test input minimization and software debloating demonstrate that CDD can achieve the same performance as ProbDD, despite being much simplified.
DOI 原文 ·
@inproceedings{paperbot8910,
title = {Toward a Better Understanding of Probabilistic Delta Debugging},
author = {Mengxiao Zhang and Zhenyang Xu and Yongqiang Tian and Xinru Cheng and Chengnian Sun},
booktitle = {ICSE},
year = {2025},
doi = {10.1109/icse55347.2025.00117}
}