Wong.Chu.Pan_Thesis_2021.pdf (3.11 MB)
Download file

Beyond Configurable Systems: Applying Variational Execution to Tackle Large Search Spaces

Download (3.11 MB)
posted on 30.04.2021, 20:27 by Chu Pan WongChu Pan Wong
Variations are ubiquitous in software. Some variations are intentionally introduced, e.g., to provide extra functionalities or tweak certain program behavior, while some variations are speculatively generated to achieve certain search goals, such as mutating a buggy program to repair a bug. Although program variations provide great flexibility, their interactions are difficult to manage, as the number of possible
interactions grows exponentially with the number of variations. There is increasing evidence showing the importance of studying interactions among variations in
various domains, such as testing highly configurable systems, secure information flow tracking, higher-order mutation testing, and automatic program repair. In this
thesis, we tackle large search spaces of interactions among variations. Among existing approaches that study interactions of intentional variations, a recent dynamic analysis technique called variational execution has been shown to be promising. Variational execution can efficiently analyze many variations and keep track of their interactions accurately, by aggressively sharing redundancies of program executions. While existing use of variational execution has focused on intentional variations, we argue that variational execution is also useful for studying
interactions among speculative variations, which remains an open challenge despite many years of research.
To study interactions among speculative variations, we set out to improve the scalability and extensibility of variational execution by using transparent bytecode transformation. With an improved implementation of variational execution, not only can we extend existing work on intentional variations, but also open new avenues for analyzing speculative variations in higher-order mutation testing and
automatic program repair. Automatic program repair and higher-order mutation testing often use searchbased
techniques to find optimal or good enough solutions in huge search spaces of speculative variations. As search spaces continue to grow, finding solutions that require interactions of multiple variations can become challenging. To tackle
the huge search spaces, we propose to encode the search problems as Boolean satisfiability problems, using variational execution and SAT solving techniques to
iterate all solutions efficiently. For automatic program repair, our approach can systematically explore the search space to find high-quality multi-edit patches. For higher-order mutation testing, our approach can find a complete set of solutions with regard to a given search space, enabling further study on their characteristics to understand their nature and learn useful insights to inspire new ideas, such as lightweight but more effective heuristics-based search strategies.




Degree Type



Institute for Software Research

Degree Name

  • Doctor of Philosophy (PhD)


Christian Kästner Claire Le Goues Heather Miller Abhik Roychoudhury