Given a program with a property of interest, program reduction searches for a smaller program that preserves the property and is easier to understand. Domain agnostic program reducers can reduce programs of multiple languages without extra domain knowledge. Despite their reusability, they may still take hours to run, hindering productivity and scalability. This paper proposes type batched program reduction, which uses machine learning to suggest portions of a program, or batches, that are most likely to be advantageous to reduce at a particular point in the reduction. We also extend this to jointly reduce multiple portions of a program at once, improving the performance further. Suggesting an appropriate order for removing batches from a program along with their potential simultaneous removal enables our reducer to outperform the state of the art reducers in reduction time over a set of large programs from multiple programming languages. This work lays foundations for further improvements in ML guided program reduction.

Given a failing test case, test case reduction yields a smaller test case that reproduces the failure. This process can be time consuming due to repeated trial and error with smaller test cases. Current techniques speed up reduction by only exploring syntactically valid candidates, but they still spend significant effort on semantically invalid candidates. In this paper, we propose a model-guided approach to speed up test case reduction. The approach trains a model of semantic properties driven by syntactic test case properties. By using this model, we can skip testing even syntactically valid test case candidates that are unlikely to succeed. We evaluate this model-guided reduction on a suite of 14 large fuzzer-generated C test cases from the bug repositories of two well-known C compilers, GCC and Clang. Our results show that with an average precision of 77%, we can decrease the number of removal trials by 14% to 61%. We observe a 30% geomean improvement in reduction time over the state of the art technique while preserving similar reduction power.

Test cases play an important role in testing and debugging software. Smaller tests are easier to understand and use for these tasks. Given a test that demonstrates a bug, test case reduction finds a smaller variant of the test case that exhibits the same bug. Classically, one of the challenges for test case reduction is that the process is slow, often taking hours. For hierarchically structured inputs like source code, the state of the art is Perses, a recent grammar aware and queue driven approach for test case reduction. Perses traverses nodes in the abstract syntax tree (AST) of a program (test case) based on a priority order and tries to reduce them while preserving syntactic validity. In this paper, we show that Perses’ reduction strategy suffers from priority inversion, where significant time may be spent trying to perform reduction operations on lower priority portions of the AST. We show that this adversely affects the reduction speed. We propose , a technique for priority aware test case reduction that avoids priority inversion. We implemented and evaluated it on the same set of benchmarks used in the Perses evaluation. Our results indicate that compared to Perses, is able to reduce test cases 1.3x to 7.8x faster and with 46% to 80% fewer queries.

Delta Debugging is a longstanding approach to automated test case reduction. It divides an input into chunks and attempts to remove them to produce a smaller input. When a chunk is successfully removed, all chunks are revisited, as they may become removable from the smaller input. When no chunk can be removed, the chunks are subdivided and the process continues recursively. In the worst case, this revisiting behavior has an O(n^2) running time. We explore the possibility that good test case reduction can be achieved without revisiting, yielding an O(n) algorithm. We identify three independent conditions that can make this reasonable in practice and validate the hypothesis on a suite of user-reported and fuzzer-generated test cases. Results show that on a suite of large fuzzer-generated test cases for compilers, our O(n) approach yields reduced test cases with similar size, while decreasing the reduction time by 65% on average.