Toward a Better Understanding of Probabilistic Delta Debugging

作者：Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Xinru Cheng, C. P. Sun · 年份：2025 · DOI：10.1109/icse55347.2025.00117 · 被引用次数：6 · 研究领域：Reservoir Engineering and Simulation Methods、Hydraulic Fracturing and Reservoir Analysis

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 pr...