Papers › Toward a Better Understanding of Probabilistic Delta Debugging
Toward a Better Understanding of Probabilistic Delta Debugging
Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Xinru Cheng, Chengnian Sun
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Given a list L of elements and a property that L exhibits, ddmin is a well-known test input minimization algorithm designed to automatically eliminate irrelevant elements from L. This algorithm is extensively adopted in test input minimization and software debloating. Recently, ProbDD, an advanced variant of ddmin, has been proposed and achieved state-of-the-art performance. Employing Bayesian optimization, ProbDD predicts the likelihood of each element in L being essential, and statistically decides which elements and how many should be removed each time. Despite its impressive results, the theoretical probabilistic model of ProbDD is complex, and the specific factors driving its superior performance have not been investigated. In this paper, we conduct the first in-depth theoretical analysis of ProbDD, clarifying trends in probability and subset size changes while simplifying the probability model. Complementing this analysis, we perform empirical experiments, including success rate analysis, ablation studies, and analysis on trade-offs and limitations, to better understand and demystify this state-of-the-art algorithm. Our success rate analysis shows how ProbDD addresses bottlenecks of ddmin by skipping inefficient queries that attempt to delete complements of subsets and previously tried subsets. The ablation study reveals that randomness in ProbDD has no significant impact on efficiency. Based on these findings, we propose CDD, a simplified version of ProbDD, reducing complexity in both theory and implementation. Besides, the performance of CDD validates our key findings. Comprehensive evaluations across 76 benchmarks in test input minimization and software debloating show that CDD can achieve the same performance as ProbDD despite its simplification. These insights provide valuable guidance for future research and applications of test input minimization algorithms.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections