💻 computer science

Enhancing Symbolic Execution of Programs for Interprocedural Control Flow Path Feasibility Analysis

Dit artikel stelt een gerichte symbolische executiemethode voor die wordt verbeterd met automatische symboliserings- en loop-boundingstrategieën om de haalbaarheid van interprocedurale controleflowpaden efficiënt te verifiëren, waarbij een superieure recall en precisie wordt aangetoond vergeleken met bestaande tools zoals KLEEF wanneer toegepast op real-world projecten en statische analyse-integratie.

Oorspronkelijke auteurs: Hovhannes Movsisyan, Hripsime Hovhannisyan, Tigran Avagyan, Hayk Aslanyan

Gepubliceerd 2026-07-08

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Hovhannes Movsisyan, Hripsime Hovhannisyan, Tigran Avagyan, Hayk Aslanyan

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een detective bent die een misdaad probeert op te lossen in een enorm, gebouw met meerdere verdiepingen (het computerprogramma). Jouw taak is om te controleren of een specifieke route die het politierapport beschrijft, daadwerkelijk mogelijk is.

Het politierapport (de "statische analyse") zegt: "De verdachte ging vanuit de lobby, via de trap naar boven, door de keuken, en sprong toen uit het raam."

Echter, wanneer je naar de blauwdrukken kijkt, besef je dat de trap niet verbonden is met de keuken, of dat het raam dichtgeschilderd is. Het politierapport was een "vals alarm"—een pad dat op papier mogelijk lijkt, maar in de werkelijkheid fysiek onmogelijk is.

Dit papier introduceert een nieuwe, slimmere manier voor detectives om deze routes te controleren zonder overweldigd te raken door de enorme omvang van het gebouw. Hier is hoe het werkt, met behulp van eenvoudige analogieën:

1. Het Probleem: De "Pad-explosie"

Traditioneel detectivewerk probeert elk enkel mogelijk pad in het gebouw te controleren om te zien waar de verdachte naartoe had kunnen gaan. In een enorm gebouw met duizenden kamers en eindeloze gangen, duurt dit eeuwig. De detective raakt verdwaald in de enorme hoeveelheid mogelijkheden (een probleem genaamd "pad-explosie") en raakt uitgeput (computerbronnen) voordat hij het antwoord heeft gevonden.

2. De Oplossing: "Gericht" Detectivewerk

De auteurs stellen een methode voor genaamd Directed Symbolic Execution. In plaats van doelloos rond te dwalen, krijgt de detective een specifieke kaart van de route die gecontroleerd moet worden.

De Truc: Als de kaart zegt dat de verdachte Links ging, negeert de detective alle "Rechtse" bochten. Ze volgen alleen het specifieke pad in kwestie, waardoor alle doodlopende wegen en irrelevante kamers worden overgeslagen. Dit maakt het werk veel sneller.

3. Omgaan met de "Onbekenden" (Automatische Symbolisering)

In het echte leven kan een detective een kamer tegenkomen waar de meubels nog niet zijn verplaatst, of een deur met een slot waarvan hij de sleutel niet heeft. In computerprogramma's zijn dit "onbekende waarden" (zoals variabelen die nog niet zijn ingesteld).

De Oude Manier: De detective stopt en zegt: "Ik kan niet verder omdat ik niet weet wat er in deze kamer is."
De Nieuwe Manier: De detective zegt: "Oké, laten we doen alsof deze kamer alles zou kunnen bevatten." Ze behandelen het onbekende als een "mysteriebox" die met elke gewenste waarde gevuld kan worden om het pad werkbaar te maken.
De Magie: Het papier leert de detective hoe ze deze mysterieboxen automatisch kunnen afhandelen, inclus':
- Niet-geïnitialiseerde variabelen: Lege kamers.
- Externe functies: Deuren die worden gecontroleerd door een buurman (een ander programma) waar de detective niet in kan kijken.
- Pointers: Een briefje dat zegt: "Ga naar het kamernummer dat op dit stukje papier geschreven staat." De detective leert het briefje te volgen, zelfs als het nummer verandert.

4. Het Probleem van de Oneindige Gang (Loop Bounding)

Stel je een gang voor die in een cirkel loopt. Als de verdachte blijft lopen, zou hij theoretisch eeuwig door kunnen blijven lopen.

Het Probleem: Als de detective elke stap in een oneindige lus probeert te simuleren, zal hij nooit klaar zijn.
De Oplossing: De detective stelt een regel in: "Ik zal niet meer dan 4 keer rond deze lus lopen." Als de lus na 4 keer nog steeds doorgaat, dwingt de detective de verdachte om de lus te verlaten en het hoofdpad te vervolgen.
Waarom het werkt: Dit voorkomt dat de detective vast komt te zitten in een eindeloze cirkel, waardoor hij de onderzoek van de specifieke route kan voltooien, zelfs als dat betekent dat hij sommige zeer lange, repetitieve stappen overslaat.

5. De Resultaten: De Liegers Betrappen

De auteurs hebben hun nieuwe detectivemethode getest op echte software (zoals de GNU Coreutils, de basisinstrumenten op een computer) en een beroemde testsuite genaamd "Juliet".

Nauwkeurigheid: Ze ontdekten dat hun methode 95,3% van de paden die daadwerkelijk mogelijk waren, correct identificeerde.
Het Opruimen van Valse Alarmen: Wanneer ze deze methode gebruikten om het werk van andere beveiligingstools (zoals MLH, Infer en Clang) te dubbelchecken, was het een game-changer.
- Eén tool (MLH) rapporteerde 666 valse alarmen. De nieuwe methode filterde ze er allemaal uit, waardoor er nul valse alarmen overbleven terwijl alle echte bugs behouden bleven.
- Een andere tool (KLEEF) maakte het eigenlijk erger toen deze de paden probeerde te controleren, door te crashen of bijna alle echte bugs te missen. De nieuwe methode bleef sterk en accuraat.

Samenvatting

Beschouw dit papier als een nieuwe set instructies voor een robotdetective. In plaats van het hele universum aan mogelijkheden te verkennen, doet de robot het volgende:

Richt zich alleen op het specifieke pad dat gecontroleerd moet worden.
Stelt zich mogelijkheden voor voor alles wat hij niet weet (zoals lege kamers of mysterieuze sloten).
Dwingt zichzelf om te stoppen met rondjes lopen als een gang te lang doorgaat.

Het resultaat is een systeem dat veel beter is in het onderscheiden van een echt beveiligingsrisico en een vals alarm, zonder moe of verward te raken.

Technische Samenvatting: Verbetering van Symbolische Executie voor de Haalbaarheidsanalyse van Interprocedurale Controlestroompaden

Probleemstelling

Statische analyse is een schaalbare techniek voor softwarebeveiliging en betrouwbaarheid, maar kampt frequent met een hoog aantal vals-positieven. Deze vals-positieven ontstaan vaak doordat statische analysers controlepaden rapporteren in een Interprocedurale Control Flow Graph (ICFG) die theoretisch mogelijk zijn, maar tijdens de runtime feitelijk onhaalbaar zijn door semantische beperkingen (bijv. tegenstrijdige variabelenwaarden). Het bepalen of een specifiek pad in een programma's ICFG uitvoerbaar is, staat bekend als padhaalbaarheidsanalyse (path feasibility analysis).

Hoewel symbolische executie een krachtige techniek is voor het verifiëren van padhaalbaarheid door paden te verkennen met behulp van symbolische waarden en SMT-solvers, staat het voor twee primaire uitdagingen wanneer het op dit specifieke probleem wordt toegepast:

Resourcevraag en Padexplosie: Standaard symbolische executie probeert alle bereikbare paden te verkennen, wat leidt tot een exponentiële groei van de toestanden, met name bij de aanwezigheid van lussen en complexe vertakkingen.
Automatiseringstekorten: Bestaande engines vereisen vaak handmatige configuratie om om te gaan met variabelen met onbekende waarden (bijv. niet-geïnitialiseerd geheugen, externe functieretouren of pointerargumenten), wat een volledige automatische integratie met statische analysetools belemmert.

Methodologie

De auteurs stellen een methode voor van gerichte symbolische executie (directed symbolic execution) die specifiek is ontworpen voor het verifiëren van de haalbaarheid van een vooraf gedefinieerde set ICFG-paden. In tegen tegenstelling tot traditionele symbolische executie, die de gehele toestandsruimte verkent, stuurt deze aanpak de executie strikt naar een doelpad, waardoor de exploratie van ongerelateerde vertakkingen wordt geëlimineerd.

De methodologie steunt op vier kerntechnische componenten:

1. Gerichte Executie en Pruning

Het algoritme neemt een set toegestane basisblokken ( $S_{allowed}$ ) en een set vereiste mijlpalen ( $S_{req}$ ) als input. Tijdens de executie:

Pruning: Bij elk vertakkingspunt wordt elke opvolgende basisblok die niet tot $S_{allowed}$ behoort, weggefilterd (gepruned), waardoor de engine wordt voorkomen dat deze irrelevante coderegionen verkent.
Verificatie: Een pad wordt als haalbaar beschouwd als de executie het doelblok ( $B_{target}$ ) bereikt terwijl alle blokken in $S_{req}$ zijn bezocht en men binnen $S_{allowed}$ is gebleven.

2. Automatische Symboliseringstrategieën

Om een volledig automatische analyse mogelijk te maken zonder gebruikersinterventie, introduceren de auteurs strategieën om waarden te symboliseren die normaal gesproken onbekend of concreet zijn in standaard executie:

Entry-Point Parameters: Alle parameters van de functie waar de padanalyse begint, worden gesymboliseerd.
verwerkt als symbolische objecten met onbeperkte waarden, in plaats van ongedefinieerd gedrag of concrete initialisatie te veroorzaken.
- Externe Functies:
  - Retouren: Retouren van externe functies (wiens body niet beschikbaar is) worden gesymboliseerd.
  - Pointerargumenten: Geheugenlocaties die worden gerefereerd door niet-constante pointerargumenten van externe aanroepen worden opnieuw gesymboliseerd om rekening te houden met zijeffecten.
  - Speciale Globalen: Specifieke afhandeling wordt toegepast op errno (wordt symbolisch gemaakt na externe aanroepen) en environ (gemodelleerd als een vaste set symbolische variabelen met vaste lengtes om niet-terminatie tijdens stringvergelijkingen te voorkomen).
Functiepointers en Virtuele Functies: Het systeem lost potentiële doelwitten voor functiepointers en virtuele aanroepen op door virtuele tabellen en functiesignaturen te analyseren, waarbij symbolische toestanden worden gesplitst (forked) voor alle geldige kandidaten.

3. Flexibel Geheugenmodel

Het paper introduceert een geheugenmodel dat symbolische pointers ondersteunt zonder te vertrouwen op fixed-size array allocaties.

Lazy Allocatie: Geheugenobjecten worden niet aangemaakt totdat de symbolische pointer wordt gederefereerd.
Aliasing Afhandeling: Wanneer een symbolische pointer wordt gederefereerd, overweegt de engine aliasing-scenario's. Het splitst de symbolische toestand om scenario's te verkennen waarbij de pointer naar een bestaand geheugenobject verwijst (met overeenkomende of afwijkende offsets) versus een volledig nieuw geheugenlocatie. Dit maakt de analyse van complexe datastructuren zoals gelinkte lijsten en bomen mogelijk zonder hun grootte vooraf te definiëren.

4. Loop Bounding Strategie

Om padexplosie in lussen te beperken, gebruikt de methode een loop-bounding strategie:

Een maximaal aantal iteraties ( $C_{max}$ ) wordt gedefinieerd.
Als een symbolische toestand een lus meer dan $C_{max}$ keer binnenkomt, dwingt de engine de toestand om de lus te verlaten via beschikbare exit-edges.
Cruciaal is dat geheugenlocaties die tijdens de uitvoering van de lus zijn beschreven, worden gesymboliseerd vóór de gedwongen exit. Dit zorgt ervoor dat de engine nog steeds paden kan verkennen die afhankelijk zijn van de zijeffecten van de lus, zelfs als het exacte aantal iteraties wordt afgekort. Dit introduceert een afweging tussen volledigheid en schaalbaarheid, waarbij de bereikbaarheid van de doeldefectlocatie prioriteit krijgt.

Belangrijkste Bijdragen

Het paper claimt de volgende bijdragen:

Een gericht symbolisch executie-algoritme voor het bepalen van de haalbaarheid van elk ICFG-pad in een gespecificeerde set.
Volledig automatische symboliseringstrategieën voor variabelen met onbekende waarden, externe functieretouren en pointerargumenten.
Een geheugenmodel dat symbolische pointerredenering en aliasing ondersteunt zonder fixed-size beperkingen.
Een loop-bounding algoritme dat iteraties beperkt zonder de symbolische executie van het pad te beëindigen.
Een empirische evaluatie op real-world software en de Juliet test suite.

Experimentele Resultaten

De methode is geïmplementeerd als een extensie van de KLEE symbolische executie engine (v3.1) en geëvalueerd met de volgende datasets:

1. Real-World Path Verification (GNU Coreutils)

Dataset: 234 unieke ICFG-paden geëxtraheerd uit GNU Coreutils, variërend van 22 tot 1.218 basisblokken.
Resultaat: De tool behaalde een recall van 95,3%, waarbij 223 van de 234 paden succesvol werden geverifieerd.
Observatie: 49 paden vereisten de loop-bounding strategie. De studie merkte op dat een Breadth-First Search (BFS) strategie incidenteel noodzakelijk was om doeltoestanden te vinden in complexe loop-scenario's waar Depth-First Search (DFS) de toestand niet binnen de tijdslimiet kon bereiken.

2. Integratie met MLH Static Analyzer

Setup: De methode is geïntegreerd in de MLH statische analyse tool en getest op de Juliet Test Suite (CWE-401: Memory Leak).
Resultaat: Integratie verhoogde de precisie van de tool van 56% naar 100% terwijl een recall van 100% behouden bleef. De methode heeft succesvol alle vals-positieven geëlimineerd zonder ware positieven te verliezen.

3. Vergelijking met KLEEF

Setup: De voorgestelde methode is vergeleken met KLEEF (een gespecialiseerde KLEE-afgeleide) met behulp van rapporten van Infer en de Clang Static Analyzer (CSA) op de Juliet Test Suite (CWE-415 en CWE-416).
Resultaat:
- Infer: KLEEF verlaagde de F1-score van 1.0 naar 0.0 (het crashte op 60 rapporten en classificeerde alle ware positieven als onhaalbaar). De voorgestelde methode behield de F1-score op 1.0.
- CSA: KLEEF verlaagde de F1-score van 0.766 naar 0.058. De voorgestelde methode behield de F1-score op 0.767 (verbeterde de precisie licht door enkele vals-positieven te filteren terwijl de recall op 100% bleef).
Analyse: De auteurs schrijven het falen van KLEEF toe aan het onvermogen om specifieke externe functie-aanroepen en symbolische pointer-arithmetiek te verwerken, wat leidde tot voortijdige beëindiging.

Betekenis en Claims

Het paper positioneert dit werk als een praktische oplossing om de kloof te overbruggen tussen de schaalbaarheid van statische analyse en de precisie van symbolische executie. De auteurs claimen dat door symbolische executie te richten en symbolisering te automatiseren, de methode ineffectieve paden gerapporteerd door statische analysers effectief kan filteren.

De betekenis ligt in het vermogen om:

Te automatiseren: Het verificatieproces zonder handmatige configuratie van symbolische variabelen.
Complexe geheugenmodellen te hanteren: (pointers, dynamische allocatie) die vaak andere tools doen falen of vaste benaderingen vereisen.
Statische Analyse Metrieken te verbeteren: Specifiek demonstreert de methode het vermogen om vals-positieven te elimineren (precisie verhogen) zonder de detectie van echte kwetsbaarheden op te offeren (recall behouden).

De auteurs erkennen een afweging tussen volledigheid en schaalbaarheid vanwege de loop-bounding strategie, maar beargumenteren dat voor het specifieke doel van het valideren van statische analyse-rapporten, het prioriteren van de bereikbaarheid van de doellocatie een aanvaardbaar compromis is. Toekomstig werk stelt voor om de analyse te parallelliseren en gespecialiseerde state selection strategieën te ontwikkelen om de efficiëntie verder te verbeteren.