Automated Programming and Program Repair

In my talk, I first reflect on the challenges of integrating automated programming into software projects maintained by humans. I then introduce the problem of input repair, particularly in the context of complex documents and document processors, with the goal of discussing the applicability of modern LLM-based code repair techniques.

The task of Fault Localization is an important part of the software debugging process, as it requires a lot of effort and investment. Additionally, it directly impacts the quality of the produced code.

With the emergence of LLMs and their potential, there is an opportunity to apply them to Fault Localization as well. However, discovering the best way to integrate known techniques with LLMs is a challenge.

Thus, this presentation shows some initial results on how the use of LLMs for Fault Localization, utilizing a few facts, can be reasonable, and which scenarios still face challenges for applying more complex methods. Moreover, an architecture was presented that aims to enrich the necessary inputs, such as better problem descriptions, for the optimal performance of these tools.

The initial results show that, for some simpler problems, using a generic LLM (GPT-3.5 and Llama 3) with a good human description or an artificial description yields reasonable results. However, in more complex scenarios, the combination of LLM with heuristics (spectrum-based) shows more promising outcomes.

In this talk, I will cover a few related themes. First, I will share my views on how modern LLMs are upending the field of software engineering with capabilities that only a few years ago required creative solutions. Next, I’ll describe how at Google we have been working on weaving AI capabilities in developer workflows, how we collect developer data, and how we prioritize our work (based on the a recent blog post https://research.google/blog/ai-in-software-engineering-at-google-progress-and-the-path-ahead/.). I will then change tracks a bit and discuss the importance of evals for software engineering tasks; the more real the better. Finally, I will segue into our preliminary investigation into understanding our own bug database at Google, and how it may compare in distribution to SWEBench. I’ll share our preliminary experience with agentic ways of resolving these internal bugs.

As one of the major infrastructures of society, software must be accessible to everyone, regardless of their physical abilities or socioeconomic status. However, the stark reality is that much software remains inaccessible or challenging to use for individuals with disabilities, creating a significant digital divide. To repair those accessibility issues, I will present our works using machine learning to automatically repair those issues i.e., generating missing labels for interactive icons in the GUI based on computer vision, and generating meaningful hint-text for text blanks in mobile applications with LLM.

Locating and fixing software faults is time-consuming and resource-intensive. Traditional methods like Spectrum-Based Fault Localization (SBFL) suffer from low accuracy, while learning-based approaches require large datasets and are computationally expensive. Recent advancements in Large Language Models (LLMs) show promise in improving fault localization, but they still face challenges such as token limits and difficulties with large projects. To address this, we introduce LLM4FL, an LLM-agent-based approach that combines SBFL with a divide-and-conquer strategy. By using multiple LLM agents and prompt chaining, LLM4FL navigates codebases and localizes faults more effectively. In tests using Defects4J, LLM4FL outperformed AutoFL by 19.27% in Top-1 accuracy and surpassed state-of-the-art methods like DeepFL and Grace, without task-specific training. Coverage splitting and method ordering further boosted accuracy by up to 22%.

Code generated by language models is often flawed. And yet, LLMs can produce a lot of useful code. How is a developer to decide whether a given generated fragrment of code should be used or not? We consider this to be a joint human-AI decision problem, where it vitally important for the AI (LLM) to reveal to the AI some trustworthy indication of the expected likelihood of the code being correct.

Existing work on the application of automated program repair (APR) techniques in industry suggest that providing explanations for automatically generated patches could help developer adoption of such tools. We first define criteria for satisfying explanations of patches, then propose the Automated Scientific Debugging (AutoSD) technique, inspired by human developer debugging frameworks, to uncover facts about the debugging scenario and integrate these facts with hypotheses about what is causing the bug. We present our empirical results demonstrating that AutoSD achieves comparable repair performance with other techniques, and that explanations could help developers assess the correctness of patches generated by AutoSD.

Automated program repair (APR) techniques successfully fixed programs bugs, but it still follows the process of classical debugging, which is not quite different from a manual debugging process. Although the techniques are fully or partially automated, we have to wait for a bug report or symptoms, reproduce it, localize it, and fix it. However, it might not be necessary to follow the classical and reactive process. What if we can proactively change the source code first to fix a bug?

This talk addresses a series of our initial work on proactive debugging applied to specific bug types, such as memory leaks in single-page web applications and blocking-call bugs in reactive applications. In particular, the talk demonstrates the effectiveness of pattern-based patch generation as the first step of proactive debugging. To show the effectiveness of proactive debugging, the work conducts a series of experiments. The results show that the proactive process significantly helps the developers address bugs in real software systems. The talk illustrates further challenges to improve the activities for proactive debugging, such as fully automated evidence collection and patch generation techniques.

Automated program repair (APR) aims to automatize the process of repairing software bugs in order to reduce the cost of maintaining software programs. Moreover, the success (given by the accuracy metric) of APR approaches has increased in recent years. However, no previous work has considered the energy impact of repairing bugs automatically using APR. The field of green software research aims to measure the energy consumption required to develop, maintain, and use software products. This paper combines, for the first time, the APR and Green software research fields. We have as main goal to define the foundation for measuring the energy consumption of the APR activity. We measure the energy consumption of ten traditional program repair tools for Java and ten fine-tuned Large-Language Models (LLM) on source code trying to repair real bugs from Defects4J, a set of real buggy programs. The initial results from this experiment show the existing trade-off between energy consumption and the ability to correctly repair bugs: Some APR tools are capable of achieving higher accuracy by spending less energy than other tools.

Recent research shows that including bug-related facts (categories of the information), such as stack traces and GitHub issues, enhances LLMs’ bug-fixing abilities. To determine the optimal facts and quantity, we studied over 19K prompts with various fact combinations to repair 314 BugsInPy benchmark bugs. Each fact, from syntactic details to unexplored semantic information like angelic values, proved beneficial in fixing specific bugs. Notably, effectiveness is non-monotonic: too many facts reduce performance. We defined the fact selection problem to find the optimal facts for each task, developing MANIPLE, a model that selects facts tailored to a given bug, outperforming existing methods and repairing 17% more bugs than the best alternative.

Code changes are an integral part of the software development process. Many code changes are meant to improve the code without changing its functional behavior, e.g., refactorings and performance improvements. Unfortunately, validating whether a code change preserves the behavior is non-trivial, particularly when the code change is performed deep inside a complex project. This talk presents ChangeGuard, an approach that uses learning-guided execution to compare the runtime behavior of a modified function. The approach is enabled by the novel concept of pairwise learning-guided execution and by a set of techniques that improve the robustness and coverage of the state-of-the-art learning-guided execution technique. Our evaluation applies ChangeGuard to a dataset of 224 manually annotated code changes from popular Python open-source projects and to three datasets of code changes obtained by applying automated code transformations. Our results show that the approach identifies semantics-changing code changes with a precision of 77.1% and a recall of 69.5´%, and that it detects unexpected behavioral changes introduced by automatic code refactoring tools. In contrast, the existing regression tests of the analyzed projects miss the vast majority of semantics-changing code changes, with a recall of only 7.6%. We envision our approach being useful for detecting unintended behavioral changes early in the development process and for improving the quality of automated code transformations.

LLMs can generate code that is highly similar to that written by humans. However, current models are trained to generate each file separately, as is standard practice in natural language processing. They thus fail to generate meaningful tests. My work leverages software artifacts like code and natural language specifications to make LLM-based test generation more reliable and useful. This includes (1) CAT-LM, a LLM trained to explicitly consider the mapping between code and test files to improve the quality of tests generated. This not only ensures code correctness, but also optimizes for other software testing metrics such as pass/compile rate and code coverage. (2) DiffSpec, a prompt chaining based framework that leverages artifacts like specification documents, bug reports, and code implementations for generating differential tests using LLMs. We evaluate DiffSpec on eBPF and Wasm, and generated over 500 differentiating tests that found real bugs.

With the advent of LLMs in automatic programming, the interest in trusted automatic programming via LLMs increases. Unfortunately, it is difficult to give any guarantees about code generated from LLMs, partly also because a detailed specification of the intended behavior is usually not available. In this talk we show how to alleviate this lack of functionality specifications by aligning automatically generated code via LLMs, automatically generated formal specifications (obtained from natural language using LLMs), as well as tests. The conformance between generated programs, generated specifications, and tests – does not provide absolute guarantees but enhances trust. Establishing such conformance also helps us uncover the likely intended program behavior.

Researchers have made significant progress in automating the software development process in the past decades. Recent progress in Large Language Models (LLMs) has significantly impacted the development process, where developers can use LLM-based programming assistants to achieve automated coding. Nevertheless, software engineering involves the process of program improvement apart from coding, specifically to enable software maintenance (e.g. bug fixing) and software evolution (e.g. feature additions). We propose an automated approach for solving GitHub issues to autonomously achieve program improvement. In our approach called AutoCodeRover, LLMs are combined with sophisticated code search capabilities, ultimately leading to a program modification or patch. In contrast to recent LLM agent approaches from AI researchers and practitioners, our outlook is more software engineering oriented. We work on a program representation (abstract syntax tree) as opposed to viewing a software project as a mere collection of files. Our code search exploits the program structure in the form of classes/methods to enhance LLM’s understanding of the issue’s root cause, and effectively retrieve a context via iterative search. The use of spectrum-based fault localization using tests, further sharpens the context, as long as a test-suite is available. Experiments on SWE-bench-lite (300 real-life GitHub issues) show increased efficacy in solving GitHub issues (19% on SWE-bench-lite), which is higher than the efficacy of the recently reported SWE-agent. In addition, AutoCodeRover achieved this efficacy with significantly lower cost (on average, $0.43 USD), compared to other baselines. We posit that our workflow enables autonomous software engineering, where, in future, auto-generated code from LLMs can be autonomously improved.

AI-driven program repair uses AI models to repair buggy software by producing patches. Rapid advancements in AI surely impact state-of-the-art performance of program repair. Yet, grasping this progress requires frequent and standardized evaluations. We propose RepairBench, a novel leaderboard for AI-driven program repair. The key characteristics of RepairBench are: 1) it is execution-based: all patches are compiled and executed against a test suite, 2) it assesses frontier models in a frequent and standardized way. RepairBench leverages two high-quality benchmarks, Defects4J and GitBug-Java, to evaluate frontier models against real-world program repair tasks. We publicly release the evaluation framework of RepairBench. We will update the leaderboard as new frontier models are released.

In this lightning talk, I will discuss some of our recent efforts of debugging and fixing fairness issues in machine learning and thoughts about possibly reusing some of the techniques for improving trustworthiness of automated code repair.

Recent techniques use deep learning techniques, including Large Language Models, for automatic programming including automated program repair. An important question is, whether adding more data to train deep learning models or adding domain knowledge to the models is a more promising or effective direction to improve automatic programming.  I will discuss existing studies and techniques that answer this question positively or negatively:

Programming requires the awareness of programming language knowledge, such as the syntax, the typing system, and the semantics. Such knowledge is not easily learnable from end-to-end training. In this talk I will introduce a series of work that integrates programming language knowledge into neural models.

APR has been actively researched for the last 15 years, introducing various approaches such as template-based, learning-based, and semantics-based approaches. In particular, the repairability of APR tools has been significantly improved over the years. For example, jGenProg, introduced in 2017, could correctly fix only 2% of the 224 bugs in the Defects4J benchmark, while the latest tool, SRepair, can correctly fix 45% of the 695 bugs in the extended benchmark. This is a remarkable achievement in the field of APR.

While research on repairability should continue, there is another important aspect of APR that has received relatively less attention: APR efficiency. More recent APR tools using template-based or learning-based approaches employ a simplistic method for patch-space exploitation. They simply enumerate the patch candidates in a predefined order based on the suspiciousness scores of the program locations to which the patch candidates are applied. Such an approach is suboptimal because it does not consider the runtime information obtained during the repair process.

In this talk, I present the two recent works we did to improve APR efficiency. We show how the APR scheduling algorithm can be viewed as a multi-armed bandit problem, and how this viewpoint can be used to improve APR efficiency.

The slides for this talk are available at the following link: https://www.jooyongyi.com/slides/Seminar/Dagstuhl/2024/APR_from_fuzzing_perspective.html

In recent years, Large Language Models (LLMs), such as GPT-4 and Claude-3.5, have shown impressive performance in various downstream applications. In this talk, I will discuss the potential impact of modern LLMs on automated programming, including both program repair and synthesis (e.g., AlphaRepair, ChatRepair, and Agentless). In addition, I will also talk about our recent work on rigorous testing/benchmarking of LLMs in automated programming (e.g., EvalPlus and SWE-bench Lite-S).