Title: Validity-Preserving Delta Debugging via Generator Trace Reduction Show Chinese title

Title: 通过生成器跟踪缩减的保持有效性的Delta调试

Abstract: Reducing test inputs that trigger bugs is crucial for efficient debugging. Delta debugging is the most popular approach for this purpose. When test inputs need to conform to certain specifications, existing delta debugging practice encounters a validity problem: it blindly applies reduction rules, producing a large number of invalid test inputs that do not satisfy the required specifications. This overall diminishing effectiveness and efficiency becomes even more pronounced when the specifications extend beyond syntactical structures. Our key insight is that we should leverage input generators, which are aware of these specifications, to generate valid reduced inputs, rather than straightforwardly performing reduction on test inputs. In this paper, we propose a generator-based delta debugging method, namely GReduce, which derives validity-preserving reducers. Specifically, given a generator and its execution, demonstrating how the bug-inducing test input is generated, GReduce searches for other executions on the generator that yield reduced, valid test inputs. The evaluation results on five benchmarks show that GReduce significantly outperforms the state-of-the-art syntax-based reducer Perses: 28.5%, 34.6%, 75.6% in size of those from Perses with 17.5%, 0.6%, 65.4% time taken by Perses, and also outperforms the state-of-the-art choice-sequence-based reducer Hypothesis, demonstrating the effectiveness, efficiency, and versatility of GReduce. Show Chinese abstract

Abstract: 减少触发错误的测试输入对于高效的调试至关重要。 Delta调试是为此目的最流行的方法。 当测试输入需要符合某些规范时，现有的Delta调试实践会遇到有效性问题：它盲目地应用简化规则，生成大量不满足所需规范的无效测试输入。 当规范超出语法结构时，这种整体效果和效率的下降变得更加明显。 我们的关键见解是，我们应该利用了解这些规范的输入生成器来生成有效的简化输入，而不是直接对测试输入进行简化。 在本文中，我们提出了一种基于生成器的Delta调试方法，即GReduce，它能够推导出保持有效性的简化器。 具体而言，给定一个生成器及其执行，展示导致错误的测试输入是如何生成的，GReduce会在生成器上搜索其他执行，以产生简化且有效的测试输入。 在五个基准上的评估结果表明，GReduce显著优于最先进的基于语法的简化器Perses： 在大小方面分别高出28.5%、34.6%、75.6%，而Perses所花费的时间分别为17.5%、0.6%、65.4%，并且还优于最先进的基于选择序列的简化器Hypothesis，证明了GReduce的有效性、效率和通用性。