EvoGPT: Leveraging LLM-Driven Seed Diversity to Improve Search-Based Test Suite Generation

Probleemstelling

Automatische unit-testgeneratie is cruciaal voor softwarekwaliteit, maar bestaande methoden kampen met specifieke beperkingen:

• Search-Based Software Testing (SBST): Methoden zoals EvoSuite gebruiken evolutionaire algoritmen (EA) om test suites te optimaliseren op basis van code coverage. Hoewel effectief, lijden ze vaak onder premature convergentie (stagnatie in lokale optima) en genereren ze test suites met beperkte semantische diversiteit, vooral voor complexe gedragingen.
• Large Language Models (LLM): Nieuwe LLM-gebaseerde benaderingen (zoals TestART) kunnen syntactisch correcte en menselijk leesbare tests genereren. Echter, deze methoden hebben vaak moeite met het verkennen van complexe invoerruimtes, lijden onder hallucinaties, en missen de mogelijkheid om iteratief te verbeteren zonder externe feedback. Ze vertonen vaak een gebrek aan diepgaande semantische exploratie.

Het paper stelt dat een hybride aanpak nodig is die de sterktes van beide werelden combineert, maar benadrukt dat de sleutel ligt in het bewust in stand houden van semantische diversiteit tijdens het generatie- en optimalisatieproces, in plaats van LLM's slechts eenmalig te gebruiken voor initialisatie.

Methodologie: Het EvoGPT Systeem

EvoGPT is een hybride systeem dat LLM's en evolutionaire algoritmen integreert in twee hoofdprocessen:

1. Generatie van de Initiële Populatie
In plaats van één enkele LLM-aanroep, gebruikt EvoGPT een diversiteitsgestuurde strategie:

• Meerdere Agents: Er worden vijf verschillende LLM-agenten geïnstancierd, elk met een unieke combinatie van systeemprompts en temperatuurinstellingen.
  • Prompts: Variëren van "standaard unit testing" tot "creatieve agents" die zich richten op edge cases, lange objectketens of specifieke assertiepatronen.
  • Temperatuur: Variërende waarden (bijv. 0.3 tot 0.8) om de stochasticiteit en variatie in de gegenereerde output te controleren.
• Generatie-Reparatie Lus: Elke gegenereerde test wordt onderworpen aan een reparatielus (geïnspireerd door TestART). Bij compileer- of runtime-fouten wordt de stack trace geanalyseerd en wordt de test automatisch of via de LLM gerepareerd.
• Coverage Enhancement: Na reparatie wordt een coverage-analyse uitgevoerd (met JaCoCo). De LLM wordt vervolgens gevraagd om aanvullende tests te genereren die specifiek de nog niet gedekte takken (branches) in de code aanpakken.
• Resultaat: Dit levert een initiële populatie van 25 semantisch diverse test suites op.

2. Populatie-Optimalisatie (Evolutionary Algorithm)
De initiële populatie wordt geoptimaliseerd door een aangepast Evolutionair Algoritme (EA):

• Fitness Functie: Een gewogen som van drie metrics: Mutation Score (MSCT, 50%), Branch Coverage (BCCT, 30%) en Line Coverage (LCCT, 20%).
• Operatoren: Selectie (ranked selection), Crossover (combinatie van test suites) en Mutatie (veranderingen in literals, verwijdering van statements/asserties).
• Plateau-ontsnapping (Stagnatie-detectie): Als het EA vastloopt (geen significante verbetering gedurende $\tau$ generaties), wordt een LLM-injectie-mechanisme geactiveerd.
  • De vijf diverse LLM-agenten worden opnieuw aangeroepen om specifieke tests te genereren voor de nog niet gedekte branches.
  • Deze nieuwe tests worden geïnjecteerd in de beste huidige test suite om het EA uit lokale optima te helpen en de zoekruimte te verbreden.

Belangrijkste Bijdragen

1. Hybride Architectuur: Een effectief systeem dat LLM's niet alleen gebruikt voor initialisatie, maar ook strategisch inzet tijdens stagnatie in de evolutionaire zoektocht.
2. Diversiteitsmechanisme: Het bewijs dat het gebruik van meerdere prompts en temperaturen cruciaal is voor het genereren van semantisch diverse test suites. Dit voorkomt dat de zoektocht te snel convergeert naar een lokaal optimum.
3. Empirische Validatie: Uitgebreide evaluatie op de Defects4J-benchmark (17 Java-projecten) met vergelijkingen tegen state-of-the-art baselines.
4. Ablatiestudies: Het aantonen dat naieve integratie van LLM en EA onvoldoende is; de specifieke combinatie van diversiteit, reparatie en plateau-ontsnapping is noodzakelijk voor de prestaties.

Resultaten

EvoGPT werd getest op Defects4J en vergeleken met EvoSuite (SBST-baseline) en TestART (LLM-baseline).

• Prestaties: EvoGPT overtreft beide baselines significant in alle drie de metrics:
  • Line Coverage (LCCT): 92% (EvoGPT) vs. 83% (TestART/EvoSuite).
  • Branch Coverage (BCCT): 90% (EvoGPT) vs. 79-80% (Baselines).
  • Mutation Score (MSCT): 87% (EvoGPT) vs. 78% (TestART) en 69% (EvoSuite).
  • Dit komt neer op een gemiddelde verbetering van 10% ten opzichte van de baselines.
• Statistische Significantie: Wilcoxon-signed-rank tests bevestigen dat de verbeteringen statistisch significant zijn ($p < 0.001$) met grote effectgroottes (Cliff's delta $\ge 0.75$).
• Ablatie-onderzoek:
  • Alleen LLM (zonder EA) presteert slechter dan de hybride aanpak.
  • Alleen EA (met vaste LLM-initialisatie) levert slechts een marginale verbetering.
  • De toevoeging van temperatuur-diversiteit en prompt-diversiteit zorgt voor aanzienlijke verbeteringen.
  • Plateau-ontsnapping met diverse prompts is essentieel voor de uiteindelijke prestatie.
• Kosten en Tijd: EvoGPT is duurder ($0.32 per klasse) en langzamer (8 minuten per klasse) dan baselines vanwege API-calls en iteratieve evaluatie. Echter, de paper betoogt dat deze kosten gerechtvaardigd zijn voor de aanzienlijke stijging in testkwaliteit en foutopsporing.

Betekenis en Conclusie

Het paper demonstreert dat de combinatie van LLM's en evolutionaire zoekalgoritmen voor testgeneratie pas echt effectief wordt wanneer semantische diversiteit actief wordt gestuurd. Het gebruik van variërende prompts en temperaturen zorgt voor een bredere exploratie van de zoekruimte, wat de beperkingen van zowel pure SBST (stagnatie) als pure LLM-methoden (oppervlakkige validatie) overbrugt.

EvoGPT bewijst dat een hybride aanpak, waarbij LLM's zowel dienen als zaadbron (seeding) als mechanisme om uit lokale optima te ontsnappen, leidt tot test suites met superioriteit in code coverage en foutopsporing. Dit opent de weg voor toekomstig onderzoek naar kostenefficiënte strategieën en de uitbreiding naar andere programmeertalen en grootschalige industriële codebases.