💻 computer science

Automated Loop Detection and Iteration Count Analysis in Binary Code

Dit artikel presenteert een geautomatiseerde, schaalbare methode die interprocedurele statische analyse combineert met controleflow- en data-afhankelijkheidstracking om natuurlijke lussen nauwkeurig te detecteren en hun iteratieaantallen te bepalen in geoptimaliseerde binaire code, waarbij een hoge precisie en schaalbaarheid wordt bereikt op real-world software en benchmark-suites.

Oorspronkelijke auteurs: Hayk Aslanyan, Garnik Khroyan, Shake Hakobyan, Hripsime Hovhannisyan

Gepubliceerd 2026-07-08

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Hayk Aslanyan, Garnik Khroyan, Shake Hakobyan, Hripsime Hovhannisyan

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 enorme, eeuwenoude bibliotheek hebt vol boeken geschreven in een geheime, gecodeerde taal. Dit is jouw binair code—de ruwe, gecompileerde instructies die een computer daadwerkelijk uitvoert. Je wilt weten hoe vaak een specifiek verhaal in het boek zichzelf herhaalt voordat het stopt. In de wereld van programmeren wordt dit een "loop" genoemd.

Er zit echter een addertje onder het gras. Voordat het boek bij jou komt, heeft een zeer efficiënte redacteur (de compiler) het verhaal herschreven. Ze hebben de hoofdstuktitels verwijderd, de paragrafen door elkaar gehusseld en eenvoudige woorden vervangen door complexe symbolen. Proberen de herhalingen te tellen door naar de oorspronkelijke verhaalopzet (de broncode) te kijken, is onmogsame omdat de definitieve versie er totaal anders uitziet.

Dit artikel presenteert een nieuwe geautomatiseerde detectietool die ontworpen is om deze geheime, gecodeerde taal direct te lezen en twee grote vragen te beantwoorden:

Waar loopt het verhaal in een loop? (Loop Detectie)
Hoe vaak herhaalt het zich precies? (Iteratie-telling)

Hieronder volgt hoe de tool werkt, onderverdeeld in eenvoudige stappen:

1. De Kaartenmaker (Disassembly & Control Flow)

Eerst werkt de tool als een cartograaf. Het neemt de ruwe, rommelige code en tekent een kaart van het gebouw.

Het breekt de code af in "kamers" (genaamd basic blocks).
Het tekent pijlen die laten zien welke deuren naar welke kamers leiden.
Het zoekt naar achterafjes: paden waar je van een kamer terug kunt lopen naar een vorige kamer die je al hebt bezocht. Dit is de definitie van een loop.
Het Doel: Om "Natural Loops" te vinden. Denk aan een draaimolen met een enkele poort waar je doorheen moet gaan. De tool negeert chaotische structuren met meerdere toegangspunten (wat zeldzaam is, ongeveer 10% van de gevallen) omdat deze te rommelig zijn om nauwkeurig te analyseren.

2. De Detective (Data Dependency)

Zodra de kaart is getekend, wordt de tool een detective die een specifieke verdachte volgt: de Iteratievariabele.

Dit is de "teller" in het verhaal (zoals een personage genaamd "Jan" die telt "1, 2, 3...").
De tool volgt de "use-def chains". Stel je een spoor van kruimels voor. Als de code zegt "Jan voegt 1 toe aan zijn score", volgt de tool de kruimel terug om te zien waar Jan zijn score vandaan kreeg.
Het controleert: Beïnvloedt dit personage de beslissing om de loop te stoppen? Update dit personage zijn eigen score elke keer dat de loop draait? Zo ja, dan is hij de Iteratievariabele.

3. De Calculator (Het oplossen van de vergelijking)

Nu de tool weet wie er telt en hoe diegene telt, werkt de tool als een wiskundige.

Het stelt drie vragen:
1. Wat was het startgetal? (bijv. Jan begint bij 0).
2. Hoe verandert het getal? (bijv. Jan voegt elke keer 1 toe).
3. Wanneer eindigt het verhaal? (bijv. Stop wanneer Jan 10 bereikt).
De tool simuleert de instructies (zoals een kleine repetitie) om deze getallen te achterhalen.
Het lost vervolgens een eenvoudige wiskundige vergelijking op om te voorspellen hoe vaak de loop zal draaien voordat hij de "Stop"-teken bereikt.

Hoe goed is het? (De Resultaten)

De auteurs hebben hun detectietool getest op real-world software (zoals de tools die worden gebruikt om bestanden te beheren in Git of de tekstverwerker NeoVim) en een standaard testsuite genaamd de Mälardalen WCET benchmark.

Nauwkeurigheid: Wanneer de tool wel een antwoord gaf, was het 100% correct. Het heeft nooit een foutief antwoord gegeven.
Dekking: Het vond het juiste antwoord voor ongeveer 60% van de loops in de testsuite.
Vergelijking: Het vond meer correcte antwoorden dan andere populaire tools (zoals LLVM) gecombineerd met een decompiler, waarbij het 27 extra loops vond die de anderen misten.
Snelheid: Het is snel genoeg om praktisch bruikbaar te zijn. Het kan 1 miljoen bytes aan code verwerken in minder dan 20 seconden. Het heeft enorme programma's succesvol geanalyseerd (zoals Git, die 23 MB groot is) zonder vast te lopen.

De Beperkingen

De tool is geen toverstaf voor elke loop. Hij werkt het best op "Natural Loops" (enkele toegangspoort) waarbij de teller op een rechte, voorspelbare lijn verandert (zoals het toevoegen van 1 of 2).

Als een loop meerdere manieren heeft om binnen te komen, slaat de tool deze over.
Als de teller op een vreemde, niet-lineaire manier verandert (zoals het willekeurig springen), kan de tool de wiskundige vergelijking niet oplossen en slaat hij deze over.
Momenteel spreekt de tool alleen de taal van AArch64 (een specifiek type processorarchitectuur die in veel moderne telefoons en servers wordt gebruikt).

Samenvatting

Kortom, dit artikel introduceert een slim, geautomatiseerd systeem dat de "geheime code" van computerprogramma's leest. Het tekent een kaart om loops te vinden, volgt de specifieke variabelen die de herhalingen tellen, en gebruikt wiskunde om precies te voorspellen hoe lang die loops zullen draaien. Het is een zeer nauwkeurige tool voor het begrijpen van hoe geoptimaliseerde software zich gedraagt, wat cruciaal is om ervoor te zorgen dat real-time systemen (zoals die in auto's of medische apparaten) niet in een oneindige loop terechtkomen.

Technische Samenvatting: Geautomatiseerde Loopdetectie en Iteratiegetal-analyse in Binaire Code

Probleemstelling
Nauwkeurige analyse van loops is cruciaal voor prestatievoorspelling, kwetsbaarheidsdetectie en Worst-Case Execution Time (WCET)-analyse. Echter, agressieve compiler-optimalisaties transformeren of elimineren vaak loops op broncodeniveau, wat een aanzienlijke divergentie creëert tussen de broncode en de gecompileerde binaire code. Bestaande technieken voor loop-analyse zijn voornamelijk ontworigest voor broncode of hoogwaardige intermediate representations (zoals LLVM IR) die type-informatie en gestructureerde control flow behouden. Bijgevolg hebben deze methoden moeite met geoptimaliseerde binaire bestanden waarbij loopgrenzen zijn vertroebeld, type-informatie verloren is gegaan en interprocedurale data-afhankelijkheden moeilijk te volgen zijn. Een fundamentele uitdaging blijft de precieze bepaling van iteratiegetallen op binair niveau, wat essentieel is voor het detecteren van oneindige loops en het berekenen van de WCET, terwijl huidige tools een gebrek hebben aan automatisering, schaalbaarheid en het vermogen om architectuurspecifieke semantiek zonder handmatige annotaties af te handelen.

Methodologie
De auteurs stellen een volledig geautomatiseerd, schaalbaar, interproceduraal statisch analyseframework voor dat direct werkt op binaire code (specifiek AArch64). De methodologie verloopt via drie primaire stadia:

Control Flow en Data Dependency Analyse:
- Disassemblie en CFG Generatie: Het proces begint met het disassembleren van de binaire code met behruik van Radare2 om assembly-instructies te extraheren en Control Flow Graphs (CFGs) voor individuele functies te construeren.
- Natural Loop Detectie: Het systeem construeert dominator- en post-dominatorbomen met behulp van het Lengauer-Tarjan algoritme. Het identificeert natuurlijke loops door back edges te detecteren (edges die een knoop verbinden met een van de dominators van die knoop). De methode groepeert back edges op basis van hun bestemming (loop header) en verzamelt alle vertices die de bron van de back edge kunnen bereiken zonder de header te passeren, waarmee de loop body wordt gedefinieerd. Deze aanpak richt zich expliciet op natuurlijke loops (single entry point), waarbij erkend wordt dat niet-natuurlijke loops (multiple entry points) ongeveer 10% van de loops in geoptimaliseerde binaire bestanden uitmaken.
- Data Dependency Constructie: Het systeem berekent reaching definitions met behulp van een worklist-algoritme op basis van basic blocks om de prestaties te optimaliseren. Vervolgens construeert het use-def chains om te volgen hoe variabele definities zich voortplanten door instructies, functieaanroepen en returns.
Identificatie van Iteratievariabelen:
- Het algoritme identificeert conditionele branch-instructies die de terminatie van de loop controleren.
- Het volgt use-def chains terug vanaf deze branches om variabelen te vinden die de conditie beïnvloeden.
- Het isoleert variabelen die hun eigen waarden bijwerken op basis van voorgaande iteraties (self-updating variables) binnen cyclische use-def chains. Deze worden geïdentificeerd als iteratievariabelen.
Bepaling van het Iteratiegetal:
- De methode beperkt de precieze berekening tot loops die voldoen aan een specifiek structureel model: een enkele iteratievariabele, een enkele loopconditie en lineaire updates.
- Parameter Extractie: Door middel van instructie-niveau emulatie (via de ESIL-engine van Radare2) bepaalt de tool de initiële waarde van de iteratievariabele, de vergelijkingsconstanten en de update-coëfficiënten ( $c$ en $d$ in de vorm $i_n = c \cdot i_{n-1} + d$ ).
- Vergelijking Oplossen: Het systeem construeert een recurrente relatie die het gedrag van de loop representeert. Het lost de closed-form oplossing op om het exacte aantal iteraties ( $n$ ) te bepalen dat vereist is om aan de terminatieconditie te voldoen. Het algoritme bevat ook controles om oneindige loops te detecteren op basis van de relatie tussen de trend van de iteratievariabele en de vergelijkingsoperator.

Belangrijkste Bijdragen

Automatisering op Binair Niveau: Het paper presenteert een methode die interprocedurale statische analyse uitvoert direct op machinecode, waardoor de noodzaak voor broncode of decompileren wordt omzeild.
Interprocedurale Tracking: In tegen tegenstelling tot veel bestaande tools, volgt deze aanpak iteratievariabelen over functie-grenzen heen, waarbij data-afhankelijkheden worden afgehandeld die meerdere procedures beslaan.
Schaalbaarheid: De tool is ontworpen om binaire bestanden van tientallen megabytes (miljoenen regels broncode equivalent) te verwerken.
Architectuur-Specifieke Redenering: De implementatie maakt gebruik van architectuur-specifieke instructie-semantiek (AArch64) om variabele-updates en control flow nauwkeurig te modelleren, wat een gat opvult waar generieke methoden falen door het niet benutten van instructie-niveau details.
Drie-Stadia Algoritme: Een nieuw pipeline die combinaties van dominator-gebaseerde loopdetectie, use-def chain traversie voor variabele-identificatie en vergelijking-gebaseerde oplossing combineert.

Experimentele Resultaten
De auteurs hebben de tool geëvalueerd op real-world open-source projecten (Rsync, Git, NeoVim) en de Mälardalen WCET benchmark suite.

Schaalbaarheid: De tool verwerkte succesvol binaire bestanden tot 26,1 MB (NeoVim). De volledige analyse-pipeline (van disassemblie tot iteratiegetal-detectie) verwerkt 1 MB aan AArch64-code in minder dan 20 seconden.
Loopdetectie: Bij vergelijking met het Angr framework toonde de tool een sterke overeenkomst in loopdetectie, waarbij het de overgrote meerderheid van de natuurlijke loops identificeerde. Analyse van top-level cycli gaf aan dat ongeveer 90% van de cyclische structuren in de geteste binaire bestanden natuurlijke loops zijn, wat de focus op single-entry loops rechtvaardigt.
Nauwkeurigheid van het Iteratiegetal: Op de Mälardalen WCET benchmark suite (171 loops) behaalde de tool 100% precisie en 60,2% recall. Het identificeerde correct de iteratiegetallen voor 103 loops, die allemaal handmatig zijn geverifieerd.
Vergelijking met Baselines: Vergeleken met een baseline die gebruikmaakt van RetDec (decompiler) en LLVM's trip count analyse, bereikte de voorgestelde tool een hogere dekking. Het analyseerde succesvol 27 extra loops die de LLVM-baseline miste, terwijl de 100% precisie behouden bleef. In tests op het Rsync-project identificeerde de tool 8 unieke iteratiegetallen die LLVM miste.

Betekenis en Claims
Het paper claimt dat de ontwikkelde methode kritieke beperkingen van bestaande binaire analyse-tools aanpakt, specifiek het gebrek aan automatisering, het onvermogen om interprocedurale dataflow te volgen zonder handmatige annotaties, en het falen om architectuur-specifieke semantiek te benutten. Door een hoge precisie en een redelijke recall te bereiken op standaard benchmarks, terwijl het schaalt naar grote, real-world binaire bestanden, biedt de aanpak een praktisch fundament voor het verbeteren van WCET-analyse, detectie van beveiligingskwetsbaarheden en prestatie-optimalisatie in omgevingen waar broncode niet beschikbaar is of zwaar geoptimaliseerd is. De auteurs merken op dat de tool momenteel focust op natuurlijke loops en specifieke lineaire update-patronen, en erkennen dat toekomstig werk vereist is om complexere control flow-structuren en aanvullende processor-architecturen te ondersteunen.