Combining Static Code Analysis and Large Language Models Improves Correctness and Performance of Algorithm Recognition

Probleemstelling

Ontwikkelaars besteden meer dan de helft van hun tijd aan het begrijpen van broncode. Het automatisch identificeren van algoritmen binnen broncode kan programmalezing (program comprehension), onderhoud en softwarekwaliteit aanzienlijk verbeteren. Echter, het herkennen van algoritmen is een complex probleem; een algemene oplossing is onmogelijk (vanwege het equivalentieprobleem), waardoor bestaande technieken vaak vertrouwen op heuristieken of machine learning.

Recente Large Language Models (LLMs) tonen veelbelovende resultaten in code-taken, maar het toepassen van LLMs op grote codebases voor algoritmedetectie brengt twee grote uitdagingen met zich mee:

1. Rekenkosten en Latentie: Het verwerken van elke code-methode door een LLM is tijdrovend en kostbaar.
2. Afhankelijkheid van namen: Er is onzekerheid of LLMs algoritmen herkennen op basis van de semantiek van de code of simpelweg op basis van de namen van variabelen en functies (bijv. een methode genaamd bubbleSort).

Methodologie

De auteurs voeren een empirische studie uit op het BigCloneEval (BCEval) dataset, een dataset met handmatig geverifieerde algoritme-implementaties uit echte Java-open-sourceprojecten. De studie omvat 7 specifieke algoritmen (o.a. Bubble Sort, Binary Search, Fibonacci, GCD).

De onderzoeksvragen (RQ's) en de bijbehorende methoden zijn als volgt:

• RQ1: Prompting Strategieën:

  • Vergelijking van verschillende prompt-types: een eenvoudige "Ja/Nee"-prompt versus een "Score"-prompt (0-4 schaal).
  • Evaluatie van In-Context Learning (ICL): Het toevoegen van voorbeelden (positieve en/of negatieve) aan de prompt.
  • Evaluatie van Chain-of-Thought (CoT): Het vragen aan het model om stap-voor-stap te redeneren voordat het antwoord geeft.
  • Gebruikte modellen: GPT-4o mini, Llama 3.1 70B Instruct, en Mixtral 8x22B Instruct.

• RQ2: Combinatie met Statische Analyse:

  • Om de runtime te verlagen, worden filterpatronen gebruikt om methoden die duidelijk geen het gezochte algoritme implementeren, te filteren voordat ze naar de LLM worden gestuurd.
  • Twee soorten filters:
    1. Sleutelwoordgebaseerd: Regex-patronen op basis van identificatoren (variabelen, methodenamen).
    2. Structureel: Patronen gebaseerd op de Abstract Syntax Tree (AST) die specifieke structurele kenmerken van algoritmen zoeken (bijv. geneste lussen voor Bubble Sort).
  • Alleen methoden die door de filter passeren, worden door de LLM geanalyseerd.

• RQ3: Invloed van Naam-informatie:

  • Een ablatiestudie waarbij alle identificatoren in de broncode worden obfusceerd (vervangen door willekeurige namen).
  • Dit meet hoe sterk de classificatieprestaties van de LLM afhankelijk zijn van semantische code-inhoud versus oppervlakkige naam-cues.

Belangrijkste Bijdragen

1. Eerste uitgebreide evaluatie van een hybride aanpak die statische code-analyse combineert met LLMs voor algoritmedetectie.
2. Optimalisatie van prompting: Identificatie van de meest efficiënte strategieën (ICL met twee voorbeelden) die een goede balans bieden tussen prestatie en runtime.
3. Hybride filterarchitectuur: Bewijs dat het combineren van lichte statische filters met LLMs de runtime drastisch verlaagt en tegelijkertijd de nauwkeurigheid verbetert.
4. Inzicht in robustheid: Kwantificering van de afhankelijkheid van LLMs van naam-informatie, wat aantoont dat ze ook op code-semantiek vertrouwen.

Resultaten

1. Prompting Strategieën (RQ1):

• Score-prompt vs. Ja/Nee: Beide presteren vergelijkbaar, maar de score-prompt (0-4) biedt meer flexibiliteit om de afweging tussen precisie en recall te sturen.
• In-Context Learning (ICL): Het toevoegen van voorbeelden verbetert de F1-score met 4 tot 8 percentagepunten.
  • De "sweet spot" is twee positieve voorbeelden (2P+0N). Dit levert de grootste verbetering op met een minimale toename in inferentietyd. Meer voorbeelden (bijv. 4P+4N) leveren slechts marginale winst op maar verdubbelen de runtime.
• Chain-of-Thought (CoT): CoT presteerde slechter dan ICL en de baseline voor GPT en Llama, en was aanzienlijk trager (tot 65x langzamer). Voor Mixtral was er een kleine verbetering, maar niet genoeg om de kosten te rechtvaardigen.

2. Combinatie met Statische Analyse (RQ2):

• De combinatie van filters en LLMs is zeer effectief.
• Runtime reductie: Afhankelijk van het filterpatroon worden 72,39% tot 97,50% van de LLM-aanroepen overgeslagen.
• Prestatieverbetering: In tegenstelling tot wat men zou verwachten, verbetert de combinatie de classificatieprestaties.
  • De Prominent Feature (structurele) filters en de Neumüller et al. filters leiden tot hogere precisie en F1-scores dan de LLM alleen.
  • De F1-scores stijgen met tot 12 percentagepunten ten opzichte van de baseline.
  • De filters verwijderen veel "false positives" die de LLM anders zou hebben gemist of verkeerd zou hebben geclassificeerd.

3. Naam-informatie (RQ3):

• Bij het obfusceren van namen daalt de recall met 4-5%, wat logisch is omdat de taak moeilijker wordt.
• De precisie stijgt echter aanzienlijk (tot +17% voor Mixtral), omdat misleidende namen (bijv. een methode sort die geen sortering doet) niet meer leiden tot fouten.
• Het F1-score neemt overall toe met 3 tot 10 percentagepunten.
• Conclusie: LLMs zijn niet uitsluitend afhankelijk van namen; ze kunnen de meeste algoritmen nog steeds herkennen op basis van de code-semantiek, hoewel namen een hulpmiddel zijn.

Significantie en Conclusie

Het artikel concludeert dat een hybride aanpak (statische analyse + LLM) de beste strategie is voor algoritmedetectie in de praktijk.

• Efficiëntie: Het filteren van de dataset voordat de LLM wordt ingeroepen verlaagt de kosten en tijd drastisch (van dagen naar minuten voor grote datasets).
• Kwaliteit: De filters fungeren als een "guardrail" die de LLM beschermt tegen het classificeren van irrelevante code, wat resulteert in hogere precisie en F1-scores dan wanneer de LLM alleen wordt gebruikt.
• Toekomst: De auteurs suggereren de ontwikkeling van IDE-plugins die deze hybride aanpak gebruiken om ontwikkelaars in real-time feedback te geven over gebruikte algoritmen, wat bijdraagt aan betere softwarekwaliteit en onderhoud.

De studie onderstreept dat LLMs krachtige tools zijn, maar dat hun integratie met traditionele statische analyse-technieken noodzakelijk is om schaalbaarheid en betrouwbaarheid te garanderen in real-world software-engineering contexten.