Skip to main content

Accelerating test case reduction

Resource type
Thesis type
(Thesis) Ph.D.
Date created
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.
144 pages.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Sumner, Nick
Member of collection
Download file Size
etd22465.pdf 1.72 MB

Views & downloads - as of June 2023

Views: 59
Downloads: 4