Accelerating Delta Debugging through Probabilistic Monotonicity Assessment
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908407215161344 |
|---|---|
| author | Tao, Yonggang Xue, Jingling |
| author_facet | Tao, Yonggang Xue, Jingling |
| contents | Delta debugging assumes search space monotonicity: if a program causes a failure, any supersets of that program will also induce the same failure, permitting the exclusion of subsets of non-failure-inducing programs. However, this assumption does not always hold in practice. This paper introduces Probabilistic Monotonicity Assessment (PMA), enhancing the efficiency of DDMIN-style algorithms without sacrificing effectiveness. PMA dynamically models and assesses the search space's monotonicity based on prior tests tried during the debugging process and uses a confidence function to quantify monotonicity, thereby enabling the probabilistic exclusion of subsets of non-failure-inducing programs. Our approach significantly reduces redundant tests that would otherwise be performed, without compromising the quality of the reduction.
We evaluated PMA against two leading DDMIN-style tools, CHISEL and ProbDD. Our findings indicate that PMA cuts processing time by 59.2% compared to CHISEL, accelerates the reduction process (i.e., the number of tokens deleted per second) by 3.32x, and decreases the sizes of the final reduced programs by 6.7%. Against ProbDD, PMA reduces processing time by 22.0%, achieves a 1.34x speedup in the reduction process, and further decreases the sizes of the final reduced programs by 3.0%. These findings affirm PMA's role in significantly improving delta debugging's efficiency while maintaining or enhancing its effectiveness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11614 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accelerating Delta Debugging through Probabilistic Monotonicity Assessment Tao, Yonggang Xue, Jingling Software Engineering Delta debugging assumes search space monotonicity: if a program causes a failure, any supersets of that program will also induce the same failure, permitting the exclusion of subsets of non-failure-inducing programs. However, this assumption does not always hold in practice. This paper introduces Probabilistic Monotonicity Assessment (PMA), enhancing the efficiency of DDMIN-style algorithms without sacrificing effectiveness. PMA dynamically models and assesses the search space's monotonicity based on prior tests tried during the debugging process and uses a confidence function to quantify monotonicity, thereby enabling the probabilistic exclusion of subsets of non-failure-inducing programs. Our approach significantly reduces redundant tests that would otherwise be performed, without compromising the quality of the reduction. We evaluated PMA against two leading DDMIN-style tools, CHISEL and ProbDD. Our findings indicate that PMA cuts processing time by 59.2% compared to CHISEL, accelerates the reduction process (i.e., the number of tokens deleted per second) by 3.32x, and decreases the sizes of the final reduced programs by 6.7%. Against ProbDD, PMA reduces processing time by 22.0%, achieves a 1.34x speedup in the reduction process, and further decreases the sizes of the final reduced programs by 3.0%. These findings affirm PMA's role in significantly improving delta debugging's efficiency while maintaining or enhancing its effectiveness. |
| title | Accelerating Delta Debugging through Probabilistic Monotonicity Assessment |
| topic | Software Engineering |
| url | https://arxiv.org/abs/2506.11614 |