💻 computer science

SEAL: Symbolic Execution with Separation Logic (Competition Contribution)

SEAL is een modulaire, prototype statische analyzer voor het verifiëren van programma's met onbegrensde gelinkte datastructuren die gebruikmaakt van separation logic en de SMT-gebaseerde Astral solver om competitieve resultaten te behalen in de LinkedLists-categorie, terwijl het een aanzienlijke uitbreidbaarheid biedt voor toekomstige ontwikkeling.

Oorspronkelijke auteurs: Tomáš Brablec, Tomáš Dacík, Tomáš Vojnar

Gepubliceerd 2026-02-09

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tomáš Brablec, Tomáš Dacík, Tomáš Vojnar

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://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 probeert te verifiëren of een complexe, voortdurend veranderende stad van wegen en gebouwen veilig is om doorheen te navigeren. Je moet ervoor zorgen dat niemand van een brug valt (een "NULL-pointer dereference"), dat niemand probeert een gebouw te slopen dat al weg is (een "use-after-free" fout), en dat niemand per ongeluk twee keer een gebouw neerhaalt (een "double-free" fout).

Dit is precies wat SEAL doet, maar in plaats van een stad, analyseert het computerprogramma's die complexe, verschuivende lijsten met gegevens beheren (zoals gelinkte lijsten).

Hier is hoe het artikel SEAL uitlegt, onderverdeeld in eenvoudige concepten:

1. Het kernidee: Een gespecialiseerde detective

De meeste tools die deze programma's controleren, zijn als detectives die een specifieke, rigide regelset gebruiken voor elk type misdaad. SEAL is anders. Het gebruikt een algemene "logica-engine" genaamd ASTRAL.

Beschouw ASTRAL als een super-slimme vertaler. Wanneer SEAL een complexe puzzel ziet over hoe gegevens in het geheugen met elkaar verbonden zijn, vertaalt het die puzzel naar een taal die een standaard, krachtige computer-solver (een zogenaamde SMT-solver) perfect begrijpt. Dit maakt SEAL zeer flexibel. Het is alsof je een detective hebt die van taal kan wisselen om met elke expert te praten, in plaats van vast te zitten aan slechts één dialect.

2. De uitdaging: Oneindig versus eindig

De programma's die SEAL controleert, bevatten vaak gelinkte lijsten (linked lists) — ketens van gegevens waarbij één item naar het volgende wijst.

Het probleem: Sommige lijsten zijn kort en vast (zoals een ketting van 3 schakels). Anderen zijn onbegrensd (unbounded), wat betekent dat ze 10 schakels lang kunnen zijn, of 10.000, of oneindig.
De moeilijkheid: Het proberen te controleren van elke mogelijke lengte van een oneindige keten is onmogelijk voor een computer. Het zou eeuwig duren.
SEAL's truc: SEAL gebruikt een techniek genaamd abstractie. Stel je voor dat je naar een zeer lange trein kijkt. In plaats van elke wagon te tellen, zegt SEAL: "Oké, dit is een 'lange trein'." Het vervangt de rommelige details van het midden van de keten door een enkele, nette label (een "predicaat"). Hierdoor kan het over de hele keten redeneren zonder de details uit het oog te verliezen.

3. Hoe het werkt: De "vorm"-analyser

SEAL is een "vorm-analyser" (shape analyzer). Het kijkt niet alleen naar getallen; het kijkt naar de vorm van het geheugen.

Symbolische heaps: Het maakt een kaart van het geheugen met behulp van "symbolische heaps". Denk hierbij aan een blauwdruk die zegt: "Hier is een blok geheugen, en dit is verbonden met dit andere blok."
De Loop Fixpoint: Wanneer een programma in een lus draait (dezelfde actie herhaalt), controleert SEAL of de "vorm" van het geheugen is gestabiliseerd. Als de vorm in de huidige ronde "veilig genoeg" lijkt vergeleken met de vorige ronde, stopt het met controleren en verklaart het de lus veilig.

4. Huidige sterktes en zwaktes

Het artikel geeft toe dat SEAL nog een prototype is (een vroege versie), maar het heeft enkele indrukwekkende statistieken:

Het goede nieuws (Sterktes):

De "Onbegrensde" Club: In een recente wedstrijd waren er 20 tools die programma's met oneindige lijsten probeerden te verifiëren. Slechts vier tools slaagden. SEAL was een van hen.
Toekomstig potentieel: Omdat SEAL die flexibele "vertaler" (ASTRAL) gebruikt, is het gemakkelijker om het nieuwe vormen te leren. De auteurs geloven dat ze het uiteindelijk kunnen leren om complexe structuren zoals bomen (trees) of skip-lists (die lijken op meerlaagse snelwegen voor gegevens) te hanteren, waar andere tools moeite mee hebben.

Het slechte nieuws (Zwaktes):

Beperkte woordenschat: SEAL begrijpt momenteel slechts een klein deelverzameling van de C-programmeertaal. Het kan nog geen complexe wiskunde met getallen of veel soorten pointers aan.
Een gokspel: Soms moet SEAL raden welk type gegevensstructuur een stuk code aan het bouwen is. Als het een foutieve gok doet (bijvoorbeeld denken dat een complexe structuur gewoon een simpele lijst is), kan het een bug missen of een "ik weet het niet"-antwoord geven.
Vals positieven: Omdat het abstracties gebruikt (het vereenvoudigen van details), kan het soms denken dat een programma onveilig is terwijl het eigenlijk wel veilig is. Het artikel merkt op dat ze dit kunnen oplossen door de controle opnieuw uit te voeren zonder vereenvoudiging, maar dat kost meer tijd.

5. De kern van de zaak

SEAL is een nieuwe, modulaire tool die is ontworpen om te bewijzen dat programma's die complexe, oneindige gegevensketens beheren, veilig zijn. Hoewel het nog niet perfect is en nog niet alle functies van de C-taal begrijpt, maakt het unieke ontwerp — het gebruik van een algemene vertaler om logische puzzels op te lossen — het een van de weinige tools die in staat is om de moeilijkste problemen met geheugiveiligheid aan te pakken. De auteurs hopen dat ze, door het systeem flexibel te houden, het in de toekomst nog beter kunnen maken in wedstrijden.

Technische Samenvatting: SEAL – Symbolische Executie met Separation Logic

Probleemstelling

De verificatie van programma's die onbegrensde gelinkte datastructuren manipuleren, blijft een significante uitdaging in statische analyse. Hoewel veel tools vertrouwen op bounded model checking of gespecialiseerde heuristieken, worstelen deze benaderingen vaak met de complexiteit van het redeneren over willekeurige lijstlengtes en complexe geheugenvormen. Bovendien koppelen bestaande op separation logic (SL) gebaseerde analysers zich vaak aan specifieke, niet-modulaire solvers, wat hun uitbreidbaarheid en het vermogen om te integreren met andere logische theorieën beperkt.

Methodologie

SEAL is een statische analyzer ontworpen voor de verificatie van programma's die onbegrensde gelinkte datastructuren manipuleren. Het maakt gebruik van forward abstract interpretation over formules van separation logic (SL). De kernmethodologie onderscheidt zich door een modulaire architectuur die de analyse-engine schoon scheidt van de logische redeneermachine.

Kerncomponenten

Abstract Domein (Symbolische Heaps):
- SEAL representeert abstracte geheugentoestanden als symbolische heaps, wat SL-formules zijn van de vorm $\exists x_1, \dots, x_m. \phi_1 * \dots * \phi_n$ .
- Atomaire formules ( $\phi_i$ $ϕ_{i}$ ) bevatten:
  - Pure formules: Beschrijvingen van pointer (dis)gelijkheden of restricties op niet-pointer waarden.
  - Points-to atomen: Beschrijvingen van enkelvoudige heap cellen.
  - Inductieve predicaten: Beschrijvingen van onbegrensde sequenties van pointers (bijv. lijsten).
  - Vrij geheugen: Een speciale predicaat die expliciet vrijgegeven geheugen representeert dat nog steeds bereikbaar is.
- Het domein houdt nauwkeurige integerwaarden bij binnen een configureerbaar bereik (standaard $[-5, 5]$ ). Toestanden op programmapunten worden gerepresenteerd als disjuncties (verzamelingen) van symbolische heaps.
Abstractie en Widening:
- Om loops en oneindige toestanderuimtes te behandelen, voert SEAL widening uit door geheugenvormen te generaliseren. Dit houdt in dat compatibele ruimtelijke predicaten (points-to of list predicaten) worden gevonden en samengevoegd tot een enkele list predicaat, mits de koppelingslocatie niet wordt aangestuurd door externe pointers of programmavariabelen.
- Het systeem houdt minimale lijstlengtes bij tot een vaste limiet om acycliciteit-garanties tijdens abstractie te waarborgen.
- Predicate Guessing: Momenteel raadt SEAL de verwachte inductieve predicaat voor C-structuren vóór de analyse op basis van het aantal velden (bijv. één zelf-referentiëel veld $\to$ SLL; twee $\to$ DLL). Deze heuristiek kan leiden tot misclassificatie (bijv. een structuur bedoeld als een geneste lijst die wordt geclassificeerd als een dubbel gelinkte lijst).
De ASTRAL Solver:
- In tegenstelling tot de meeste SL-gebaseerde tools die dedicated heuristieken gebruiken voor verzadigbaarheid en entailment, vertrouwt SEAL op ASTRAL, een algemene separation logic solver.
- ASTRAL vertaalt SL-formules naar SMT-theorieën (specifiek bitvectors en arrays) met behulp van een grens op predicate unfolding.
- De vertaalde formules worden doorgegeven aan de BITWUZLA SMT-solver.
- ASTRAL ondersteunt gebruikersgedefinieerde inductieve predicaten, waardoor SEAL zijn eigen predicaten kan definiëren zonder ingebouwde solver-ondersteuning voor deze.
Analyse Mechanica:
- Loop Fixpoints: Een fixpoint wordt bereikt wanneer de entailment tussen de huidige loop iteratie toestand ( $S$ ) en de vorige iteratie toestand ( $T$ ) geldig is. Dit wordt benaderd door te controleren of er voor elke heap in $S$ , een heap in $T$ bestaat die deze entailt.
- Interprocedurale Analyse: Functie aanroepen worden geoptimaliseerd met behulp van summaries (precondition/postcondition paren).
- Simplificatie: Het systeem past syntactische simplificaties toe, zoals het reduceren van equivalentieklassen en het verwijderen van variabelen die buiten scope vallen.

Belangrijkste Bijdragen

Modulaire Architectuur: Door de abstracte interpretatie-engine te scheiden van de logische redeneermachine via ASTRAL, bereikt SEAL een ontwerp dat bedoeld is om gemakkelijker uit te breiden en te combineren met redeneren in andere theorieën.
General-Purpose Solving: De integratie van ASTRAL stelt SEAL in staat om SMT-solvers te gebruiken voor SL entailment en verzadigbaarheid, waardoor het geen behoef even aan custom, dedicated solvers voor elke specifieke variant van de logica nodig heeft.
Verificatie van Onbegrensde Lijsten: De tool is in staat om programma's te verifiëren die onbegrensde gelinkte lijsten manipuleren, een categorie waarin veel concurrerende tools falen.

Experimentele Resultaten

SEAL nam deel aan de MemSafety-LinkedLists categorie van de SV-COMP competitie.

Algemene Prestaties: Op de volledige set van 134 programma's verifieerde SEAL 55 als "True" (correct) en vond 4 "False" (bugs), waarbij 75 geen resultaat rapporteerden.
Unbounded Lists Subset: Op de subset van 69 programma's die redeneren over onbegrensde datastructuren vereisen, verifieerde SEAL 14 programma's als correct en vond 2 bugs.
Vergelijking:
- SEAL presteerde beter dan 2LS (die slechts 3 onbegrensde programma's verifieerde).
- SEAL verifieerde minder programma's dan PREDATORHP (46) en CPACHECKER (40), die beide symbolic memory graphs (SMGs) gebruiken.
- SEAL was een van de slechts vier analysers die in staat waren om programma's met onbegrensde lijsten in deze categorie te verifiëren.

Betekenis en Claims

Het artikel positioneert SEAL als een veelbelovend prototype met een specifieke focus op uitbreidbaarheid in plaats van directe brute prestatiedominantie.

Toekomstig Potentieel: De auteurs beweren dat het modulaire ontwerp van de tool en de afhankelijkheid van ASTRAL een sterke fundering bieden voor het ondersteunen van complexe datastructuren die niet gemakkelijk door SMG's gerepresenteerd kunnen worden, zoals skip-lists en bomen.
Beperkingen: Als een vroeg prototype ondersteunt SEAL momenteel slechts een subset van C (beperkte pointer aritmetiek, specifieke integer tracking) en vertrouwt het op heuristische predicate guessing, wat kan leiden tot false positives of het onvermogen om schendingen te rapporteren wanneer integer informatie ontbreekt.
Roadmap: De auteurs zijn van plan om de selectie van predicaten tijdens de analyse te verbeteren, inductieve predicaten te synthetiseren uit voorbeelden, en potentieel SEAL in te bedden als een abstract domein binnen het Frama-C EVA framework om complexere niet-pointer waarden te behandelen.

Samenvattend demonstreert SEAL dat een algemene, op SMT gebaseerde benadering van separation logic solving een levensvatbaar en uitbreidbaar alternatief is voor gespecialiseerde heuristieken, wat een pad biedt naar het verifiëren van complexe, onbegrensde datastructuren in toekomstige competities.