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 search-based 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.

151 pages

Thesis Committee:
Christian Kästner (Chair)
Claire Le Goues
Heather Miller
Abhik Roychoudhury (National University of Singapore)

James D. Herbsleb, Director, Institute for Software Research
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu