一句话：提出加权增量调试WDD，按元素权重区分划分，显著提升测试输入最小化的效率与效果。
增量调试（Delta Debugging）是一类广泛用于自动最小化触发缺陷的测试输入的算法，如 ddmin 与 ProbDD。它把输入表示为元素列表，在不同粒度上划分并删除与缺陷无关的部分。现有算法假定列表中各元素没有差异，因此在划分时一视同仁；但实际中元素所代表的片段大小（称为权重）往往相差悬殊，例如占输入 50% 的元素比只占 1% 的元素更可能与缺陷相关，这一假设会损害最小化的效率甚至效果。本文提出加权增量调试（WDD），核心思想是依据元素所代表片段的大小为其赋予权重，并在划分过程中依据权重区分对待不同元素。作者分别将 WDD 应用于 ddmin 与 ProbDD，设计出 W_ddmin 与 W_ProbDD 两个新算法，并在 HDD 与 Perses 两个代表性应用中、跨两种语言的 62 个基准上进行了广泛评估。结果表明，W_ddmin 使 HDD 与 Perses 相比 ddmin 平均少用 51.31% 和 7.47% 的时间，并分别生成小 9.12% 和 0.96% 的结果；W_ProbDD 相比 ProbDD 平均少用 11.98% 和 9.72% 的时间，生成的结果分别小 13.40% 和 2.20%。
Delta Debugging is a widely used family of algorithms (e.g., ddmin and ProbDD) to automatically minimize bug-triggering test inputs, thus to facilitate debugging. It takes a list of elements with each element representing a fragment of the test input, systematically partitions the list at different granularities, identifies and deletes bug-irrelevant partitions. Prior delta debugging algorithms assume there are no differences among the elements in the list, and thus treat them uniformly during partitioning. However, in practice, this assumption usually does not hold, because the size (referred to as weight) of the fragment represented by each element can vary significantly. For example, a single element representing 50% of the test input is much more likely to be bug-relevant than elements representing only 1%. This assumption inevitably impairs the efficiency or even effectiveness of these delta debugging algorithms. This paper proposes Weighted Delta Debugging (WDD), a novel concept to help prior delta debugging algorithms overcome the limitation mentioned above. The key insight of WDD is to assign each element in the list a weight according to its size, and distinguish different elements based on their weights during partitioning. We designed two new minimization algorithms,$\mathbf{W}_{\text{ddmin}}$and$\mathbf{W}_{\text{ProbDD }}$, by applying WDD to ddmin and ProbDD respectively. We extensively evaluated$\mathbf{W}_{\text{ddmin}}$and$\mathbf{W}_{\text{ProbDD }}$in two representative applications, HDD and Perses, on 62 benchmarks across two languages. On average, with$\mathbf{W}_{\text{ddmin }}$, HDD and Perses took 51.31% and 7.47% less time to generate 9.12% and 0.96% smaller results than with ddmin, respectively. With$\mathbf{W}_{\text{ProbDD }}$, HDD and Perses used 11.98% and 9.72% less time to generate 13.40% and 2.20% smaller results than with ProbDD, respectively. The results strongly demonstrate the value of WDD. We firmly believe that WDD opens up a new dimension to improve test input minimization techniques.
DOI 原文 ·
@inproceedings{paperbot8797,
title = {WDD: Weighted Delta Debugging},
author = {Xintong Zhou and Zhenyang Xu and Mengxiao Zhang and Yongqiang Tian and Chengnian Sun},
booktitle = {ICSE},
year = {2025},
doi = {10.1109/icse55347.2025.00071}
}