Efficient Exploration and Analysis of Program Repair Search Spaces

QC 20241023

Abstract

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.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-355105