Accelerating test case reduction

Test cases play an important role in testing and debugging software. Large complex test cases are hard to comprehend and can hinder these tasks. Thus, reducing test cases is crucial for understanding and fixing defects in software. Given a test case with a property of interest, such as demonstrating a bug in the software under test, the goal of test case reduction is to create a smaller variant of the test case that still exhibits the bug. To generate this smaller variant, a reducer searches over a set of smaller candidates by applying transformations to the original test case. For each candidate, the reducer queries an oracle to verify whether the desired properties still hold. If they do, the search continues from the new smaller variant. Reducers stop when they see no more reduction opportunities or time out. Even when automated, test case reduction is slow and time-consuming due to repeated trial and error with smaller candidates. This causes interruptions that adversely affect a developer's productivity. The goal of this dissertation is to accelerate test case reduction by proposing new techniques that address some of the limitations in the field. In particular, we suggest generalized techniques that reduce test cases of various domains by traversing their parse trees and applying reduction to the nodes. To this end, we improve the theoretical bounds and empirical performance of the well-known Delta Debugging algorithm by converting its quadratic worst case time complexity into linear. We propose novel tree traversal orders that remove more of the test case earlier. We train machine learning models, capable of avoiding candidates that do not adhere to a domain's validity constraints. We further leverage models that guide reduction towards generating candidates that are likely to be valid. These guiding models make their suggestions based on the reduction progress. Our empirical results on a set of real-world test cases from multiple domains are promising and demonstrate the practical value of our techniques. More specifically, we obtain an average improvement of around 60% in reduction time compared to the state of the art when reducing C, Rust and Go programs.