The ubiquitous presence of software has made its failures a huge source of cost. To avoid this cost, fixing buggy programs is essential. As manual bug fixing, also known as debugging, is notoriously resource demanding, researchers have proposed to replace it with automated program repair (APR) approaches. As input, an APR approach takes a specification and a buggy program that violates the specification; it then tries to generate a patched program that complies with the specification and correctly implements the expected behavior. To ensure APR is practical and can replace manual debugging, we have to make it efficient.

APR works in two major phases: search space exploration, and search space analysis. In the search space exploration phase, the APR approach predicts the potentially faulty parts of the code (fault localization) and replaces them with various alternatives to generate patches (patch generation). In this phase, finding the best alternatives requires extensive and costly analysis, which makes patch generation a key to APR efficiency. In the search space analysis phase of APR, the patches generated in the exploration phase are analyzed to identify a correct patch with an automated patch assessment and a manual patch assessment component. The automated patch assessment aims at minimizing the number of patches that require manual assessment for identifying a correct patch. As the human expertise needed for manual patch assessment is the most valuable development resource, strong automated and manual patch assessment techniques are crucial for efficient APR.

In this thesis, we aim at improving the efficiency of three main components involved in the exploration and analysis of APR search spaces: patch generation, automated patch assessment, and manual patch assessment. For this purpose, the thesis makes five contributions as follows.

We make two contributions to make patch generation efficient. First, we introduce Sorald, a template-based APR approach for fixing SonarJava static warnings. Sorald employs accurately designed templates to generate exactly one patch that is highly likely to fix the bug. The lightweight patch generation technique and the small search space that needs little analysis makes Sorald an efficient APR approach. Our second contribution is CigaR, an iterative LLM-based APR tool that fixes bugs that cause a test failure. CigaR uses three carefully designed prompts and two prompting strategies to generate likely correct patches with minimal LLM token cost.

We also make two other contributions to make automated patch assessment efficient. First, we propose LighteR, a lightweight tool for estimating the potential of fix templates used by template-based APR approaches. LighteR compares fix templates against developer-made bug-fixes to assess if the templates follow the modification patterns used by experts. The result of this assessment is used to rank the patches based on the potential of templates used for their generation. This ranking is used to prioritize patches for manual assessment and thus, finding the correct patch with minimal manual analysis. Our second contribution to APR automated patch assessment is Mokav. Mokav is an execution-driven iterative LLM-based tool that generates tests to differentiate between patches. The generated tests help to group APR patches into separate clusters. Only one patch from each of the clusters requires manually analysis. This makes APR efficient by significantly reducing the manual patch assessment effort.

Our last contribution is Collector-Sahab, which aims at helping code reviewers better understand behavioral changes caused by patches. Given two versions of a program P \& Q, Collector-Sahab collects the execution trace of both P \& Q. It next compares the traces and identifies runtime differences at variable and return value level. Finally, it augments the code diff between P \& Q with a concise selection of extracted runtime differences. This code augmentation helps code reviewers to better understand the behavior of APR patches and thus, reduces human effort needed for manual patch assessment.

To sum up, in this thesis we aim at making APR useful in practice by improving its efficiency. For this purpose, we propose novel methods to make patch generation, automated patch assessment, and manual patch assessment efficient.

Programvara används i många olika sammanhang vilket gör dess misslyckanden till en enorm kostnadskälla. För att undvika denna kostnad är det viktigt att fixa buggiga program. Eftersom manuell buggfixning, även känd som debugging, är notoriskt resurskrävande, har forskare föreslagit att den ska ersättas med tillvägagångssätt för automatiserad programreparation (APR). Som input tar en APR-metod en specifikation och ett buggigt program som bryter mot specifikationen; den försöker sedan generera ett korrigerat program som överensstämmer med specifikationen och korrekt implementerar det förväntade beteendet. För att säkerställa att APR är praktiskt användbart och kan ersätta manuell felsökning, måste vi se till att det görs effektivt.

APR fungerar i två huvudfaser: sökrumsutforskning och sökrumsanalys. I sökrumsutforskningsfasen förutsäger APR-metoden de potentiellt felaktiga delarna av koden (fellokalisering) och ersätter dem med olika alternativ för att generera patchar (patchgenerering). Att hitta de bästa alternativen  kräver i denna fas omfattande och kostsamma analyser, vilket gör patchgenerering till en nyckel till effektiv APR. I sökrumsanalysfasen av APR analyseras patcharna som genereras i utforskningsfasen för att identifiera en korrekt patch med en automatisk patchbedömning och en manuell komponent för bedömning av patchar. Den automatiska patchbedömningen syftar till att minimera antalet patchar som kräver manuell bedömning för att identifiera en korrekt patch. Eftersom den mänskliga expertis som behövs för manuell patchbedömning är den mest värdefulla utvecklarresursen, är starka automatiserade och manuella patchbedömningstekniker avgörande för effektiv APR.

I den här avhandlingen syftar vi till att förbättra effektiviteten hos tre huvudkomponenter som är involverade i utforskning och analys av APR-sökrum: patchgenerering, automatiserad patchbedömning och manuell patchbedömning. För detta ändamål ger avhandlingen fem bidrag enligt följande.

Vi ger två bidrag för att göra patchgenerering effektiv. Först introducerar vi Sorald, en mallbaserad APR-metod för att fixa statiska varningar som ges av SonarJava. Sorald använder noggrant utformade mallar för att generera exakt en patch som med stor sannolikhet kommer att fixa buggen. Den enkla patchgenereringstekniken och det lilla sökrummet som inte kräver så mycket analys gör Sorald till en effektiv APR-metod. Vårt andra bidrag är CigaR, ett iterativt LLM-baserat APR-verktyg som fixar buggar som orsakar ett testfel. CigaR använder tre noggrant utformade promptar och två promptstrategier för att generera sannolikt korrekta patchar med minimal LLM-tokenkostnad.

Vi ger också två andra bidrag för att göra automatiserad patchbedömning effektiv. Först föreslår vi LighteR, ett enkelt verktyg för att uppskatta potentialen för fixa mallar som används av mallbaserade APR-metoder. LighteR jämför fixa mallar med buggfixar gjorda av utvecklare för att bedöma om mallarna följer modifieringsmönster som används av experter. Resultatet av denna bedömning används för att rangordna patcharna baserat på potentialen hos mallar som används för deras generering. Denna rankning används för att prioritera patchar för manuell bedömning och därmed hitta rätt patch med minimal manuell analys. Vårt andra bidrag till APR automatisk patchbedömning är Mokav. Mokav är ett exekveringsdrivet iterativt LLM-baserat verktyg som genererar tester för att skilja mellan patchar. De genererade testerna hjälper till att gruppera APR-lappar i separata kluster. Endast en patch från varje kluster behöver bedömas manuellt. Detta gör APR effektiv genom att avsevärt minska den manuella patchbedömningen.

Vårt sista bidrag är Collector-Sahab, som syftar till att hjälpa kodgranskare att bättre förstå beteendeförändringar orsakade av patchar. Givet två versioner av ett program P \& Q, samlar Collector-Sahab in exekveringsspår för både P \& Q. Därefter jämförs spåren och körtidsskillnader på variabel- och returvärdesnivå identifieras. Slutligen utökar den koddifferensen mellan P \& Q med ett kortfattat urval av extraherade skillnader vid körning. Denna förstärkning av koden hjälper kodgranskare att bättre förstå beteendet hos APR-patchar och minskar på så sätt den mänskliga ansträngningen som krävs för manuell patchbedömning.

Sammanfattningsvis, i denna avhandling syftar vi till att göra APR användbar i praktiken genom att förbättra dess effektivitet. För detta ändamål föreslår vi nya metoder för att göra patchgenerering, automatiserad patchbedömning och manuell patchbedömning effektiv.