Automated Program Repair using Program Analysis and Machine Learning Techniques

Software maintenance is tricky, tedious, time-consuming and expensive. Automated program repair (APR) aims at finding patches for buggy programs automatically. Given a buggy program and corresponding test suite, most APR systems follow a locate-generate-validate workflow, which first locates the buggy statements and then repeatedly generates and validates candidate patches until a plausible patch passes the test. In this thesis, we mainly focus on two critical but relatively orthogonal repair steps, fault localization (FL) and repair operator prediction. Besides, we aim at developing an end-to-end APR tool for common bug types like null dereferences. We adopt two types of advanced techniques, program analysis and machine learning. Static and dynamic program analysis techniques can help with analyzing the root causes of bugs and pruning unsatisfiable candidates. Machine learning, especially modern deep learning models, can guide the repair process by learning from the correct code. First, we introduce FLIP, an FL tool that efficiently combines spectrum- and mutation-based FL families. We leverage and extend the predicate switching to infer fault locations no matter whether the mutated predicate can overturn a failed test case or not and compute a new ranking list with a joint inference combining program coverage and mutation inferences. Second, we propose M3V, a multi-modal multi-view context embedding approach for predicting repair operators. Given a fault location, we represent its program context with two modalities: multi-view graphs that capture data- and control- dependences and texts that capture high-level semantics in natural language. With the context embeddings generated by M3V, a classifier is trained from correct code to predict repair operators. Third, we design an end-to-end repair tool, VFIX, for fixing null dereferences in Java. We use value-flow analysis to precisely locate the fault and guide the patch generation. Specifically, we formulate the fault localization for null dereferences as a congestion calculation problem and design value-flow-aware repair operators to prune unsatisfiable patch candidates before validation. We describe the methodologies, implementations, and evaluations of FLIP, M3V, and VFIX in this thesis. The experimental results demonstrate that all of the three proposed approaches have met their design goals