💻 computer science

SEAL: Symbolic Execution with Separation Logic (Competition Contribution)

SEAL ist ein modularer, prototypischer statischer Analysator zur Verifizierung von Programmen mit unbeschränkten verknüpften Datenstrukturen, der Separation Logic und den SMT-basierten Astral-Solver nutzt, um kompetitive Ergebnisse in der Kategorie LinkedLists zu erzielen, während er gleichzeitig eine signifikante Erweiterbarkeit für die zukünftige Entwicklung bietet.

Ursprüngliche Autoren: Tomáš Brablec, Tomáš Dacík, Tomáš Vojnar

Veröffentlicht 2026-02-09

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Tomáš Brablec, Tomáš Dacík, Tomáš Vojnar

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen zu verifizieren, ob eine komplexe, sich ständig verändernde Stadt aus Straßen und Gebäuden sicher zu navigieren ist. Sie müssen sicherstellen, dass niemand von einer Brücke fällt (ein „NULL-Pointer-Dereferenz“-Fehler), dass niemand versucht, ein Gebäude abzureißen, das bereits nicht mehr existiert (ein „Use-after-free“-Fehler) und dass niemand versehentlich ein Gebäude zweimal niederreißt (ein „Double-free“-Fehler).

Genau das tut SEAL, aber anstatt einer Stadt analysiert es Computerprogramme, die komplexe, sich verändernde Listen von Daten verwalten (wie zum Beispiel verkettete Listen).

Hier ist die Erklärung, wie das Paper SEAL erläutert, aufgeschlüsselt in einfache Konzepte:

1. Die Kernidee: Ein spezialisierter Detektiv

Die meisten Werkzeuge, die diese Programme prüfen, sind wie Detektive, die für jede Art von Verbrechen ein spezifisches, starres Regelwerk verwenden. SEAL ist anders. Es verwendet eine allgemeine „Logik-Engine“ namens ASTRAL.

Betrachten Sie ASTRAL als einen superintelligenten Übersetzer. Wenn SEAL auf ein komplexes Rätsel stößt, wie Daten im Speicher miteinander verbunden sind, übersetzt es dieses Rätsel in eine Sprache, die ein standardmäßiger, leistungsstarker Computer-Solver (ein sogenannter SMT-Solver) perfekt versteht. Dies macht SEAL sehr flexibel. Es ist wie ein Detektiv, der die Sprache wechseln kann, um mit jedem Experten zu sprechen, anstatt an einen einzigen Dialekt gebunden zu sein.

2. Die Herausforderung: Unendlich vs. Endlich

Die Programme, die SEAL prüft, beinhalten oft verkettete Listen – Ketten von Daten, bei denen ein Element auf das nächste verweist.

Das Problem: Einige Listen sind kurz und fest definiert (wie eine Kette aus 3 Gliedern). Andere sind unbeschränkt (unbounded), was bedeutet, dass sie 10 Glieder lang sein könnten, oder 10.000 oder unendlich.
Die Schwierigkeit: Zu versuchen, jede mögliche Länge einer unendlichen Kette zu prüfen, ist für einen Computer unmöglich. Es würde ewig dauern.
SEALs Trick: SEAL nutzt eine Technik namens Abstraktion. Stellen Sie sich vor, Sie betrachten einen sehr langen Zug. Anstatt jedes einzelne Waggon zu zählen, sagt SEAL: „Okay, das ist ein ‚langer Zug‘.“ Es ersetzt die unordentlichen Details in der Mitte der Kette durch ein einziges, ordentliches Label (ein „Prädikat“). Dies ermöglicht es dem System, über die gesamte Kette zu argumentieren, ohne sich in den Details zu verlieren.

3. Wie es funktioniert: Der „Shape“-Analyzer

SEAL ist ein „Shape-Analyzer“. Es schaut nicht nur auf Zahlen; es betrachtet die Form des Speichers.

Symbolische Heaps: Es erstellt eine Karte des Speichers unter Verwendung von „symbolischen Heaps“. Denken Sie an einen Bauplan, der besagt: „Hier ist ein Speicherblock, und er ist mit diesem anderen Block verbunden.“
Der Loop-Fixpunkt: Wenn ein Programm in einer Schleife läuft (eine Aktion wiederholt), prüft SEAL, ob sich die „Form“ des Speichers stabilisiert hat. Wenn die Form in der aktuellen Runde im Vergleich zur vorherigen Runde „sicher genug“ aussieht, stoppt die Prüfung und deklariert die Schleife als sicher.

4. Aktuelle Stärken und Schwächen

Das Paper gibt zu, dass SEAL noch ein Prototyp (eine frühe Version) ist, aber es weist einige beeindruckende Statistiken auf:

Die guten Nachrichten (Stärken):

Der „Unbounded“-Club: In einem kürzlichen Wettbewerb gab es 20 Werkzeuge, die Programme mit unendlichen Listen verifizierten. Nur vier Werkzeuge waren erfolgreich. SEAL war eines davon.
Zukünftiges Potenzial: Da SEAL diesen flexiblen „Übersetzer“ (ASTRAL) nutzt, ist es einfacher, es mit neuen Formen zu trainieren. Die Autoren glauben, dass sie es schließlich in der Lage sein können, komplexe Strukturen wie Bäume oder Skip-Lists (die wie mehrstufige Autobahnen für Daten funktionieren) zu handhaben, mit denen andere Werkzeuge Schwierigkeiten haben.

Die schlechten Nachrichten (Schwächen):

Begrenztes Vokabular: SEAL versteht derzeit nur eine kleine Teilmenge der Programmiersprache C. Es kann noch kein komplexes Rechnen mit Zahlen oder viele Arten von Pointern handhaben.
Ein Ratespiel: Manchmal muss SEAL raten, welche Art von Datenstruktur ein Stück Code aufbaut. Wenn es falsch rät (z. B. wenn es eine komplexe Struktur fälschlicherweise als eine einfache Liste ansieht), könnte es einen Bug übersehen oder die Antwort „Ich weiß es nicht“ geben.
False Positives: Da es Abstraktionen verwendet (Details vereinfacht), kann es vorkommen, dass SEAL ein Programm als unsicher einstuft, obwohl es eigentlich völlig in Ordnung ist. Das Paper stellt fest, dass sie dies beheben könnten, indem sie die Prüfung ohne Vereinfachung erneut durchführen, aber das nimmt mehr Zeit in Anspruch.

5. Das Fazit

SEAL ist ein neues, modulares Werkzeug, das darauf ausgelegt ist, zu beweisen, dass Programme, die komplexe, unendliche Datenketten verwalten, sicher sind. Obwohl es noch nicht perfekt ist und noch nicht alle Merkmale der C-Sprache versteht, macht sein einzigartiges Design – die Nutzung eines allgemeinen Übersetzers zur Lösung von Logikrätseln – es zu einem der wenigen Werkzeuge, die in der Lage sind, die schwierigsten Probleme der Speichersicherheit zu bewältigen. Die Autoren hoffen, durch die Beibehaltung der Flexibilität des Systems dieses in Zukunft noch besser machen zu können.

Technisches Resümee: SEAL – Symbolische Ausführung mit Separation Logic

Problemstellung

Die Verifizierung von Programmen, die ungebundene verknüpfte Datenstrukturen manipulieren, bleibt eine erhebliche Herausforderung in der statischen Analyse. Während viele Werkzeuge auf Bounded Model Checking oder spezialisierte Heuristiken setzen, haben diese Ansätze oft Schwierigkeiten mit der Komplexität der Argumentation über beliebige Listenlängen und komplexe Speicherformen. Zudem koppeln sich bestehende auf Separation Logic (SL) basierende Analysatoren häufig an dedizierte, nicht-modulare Solver, was deren Erweiterbarkeit und die Fähigkeit zur Integration mit anderen logischen Theorien einschränkt.

Methodik

SEAL ist ein statischer Analysator, der für die Verifizierung von Programmen konzipiert wurde, die ungebundene verknüpfte Datenstrukturen manipulieren. Es verwendet vorwärtsgerichtete abstrakte Interpretation über Formeln der Separation Logic (SL). Die Kernmethodik unterscheidet sich durch eine modulare Architektur, die die Analyse-Engine sauber von der logischen Argumentations-Engine entkoppelt.

Kernkomponenten

Abstrakte Domäne (Symbolische Heaps):
- SEAL repräsentiert abstrakte Speicherzustände als symbolische Heaps, welche SL-Formeln der Form $\exists x_1, \dots, x_m. \phi_1 * \dots * \phi_n$ sind.
- Atomare Formeln ( $\phi_i$ $ϕ_{i}$ ) umfassen:
  - Reine Formeln: Beschreiben Pointer-Gleichheit (oder -Ungleichheit) oder Constraints für Nicht-Pointer-Werte.
  - Points-to-Atome: Beschreiben einzelne Heap-Zellen.
  - Induktive Prädikate: Beschreiben ungebundene Sequenzen von Pointern (z. B. Listen).
  - Freier Speicher: Ein spezielles Prädikat repräsentiert explizit freigegebenen Speicher, der weiterhin erreichbar bleibt.
- Die Domäne verfolgt präzise Integer-Werte innerhalb eines konfigurierbaren Bereichs (Standard $[-5, 5]$ ). Zustände an Programmstellen werden als Disjunktionen (Mengen) symbolischer Heaps dargestellt.
Abstraktion und Widening:
- Um Schleifen und unendliche Zustandsräume zu handhaben, führt SEAL Widening durch die Generalisierung von Speicherformen durch. Dies beinhaltet das Finden kompatibler räumlicher Prädikate (Points-to oder Listen-Prädikate) und deren Zusammenführung in ein einzelnes Listen-Prädikat, sofern die Verknüpfungsstelle nicht durch externe Pointer oder Programmvariablen adressiert wird.
- Das System verfolgt minimale Listenlängen bis zu einem festen Limit, um Garantien bezüglich der Azyklizität während der Abstraktion sicherzustellen.
- Prädikat-Vermutung (Predicate Guessing): Derzeit vermutet SEAL das erwartete induktive Prädikat für C-Strukturen vor der Analyse basierend auf der Anzahl der Felder (z. B. ein selbstreferenzielles Feld $\to$ SLL; zwei $\to$ DLL). Diese Heuristik kann zu Fehlklassifizierungen führen (z. B. eine Struktur, die als verschachtelte Liste gedacht ist, wird als doppelt verkettete Liste klassifiziert).
Der ASTRAL Solver:
- Im Gegensatz zu den meisten SL-basierten Werkzeugen, die dedizierte Heuristiken für Erfüllbarkeit und Entailment nutzen, vertraut SEAL auf ASTRAL, einen allgemeingültigen Separation-Logic-Solver.
- ASTRAL übersetzt SL-Formeln in SMT-Theorien (speziell Bitvektoren und Arrays) unter Verwendung einer Schranke für das Entfalten von Prädikaten (Predicate Unfolding).
- Die übersetzten Formeln werden an den BITWUZLA SMT-Solver übergeben.
- ASTRAL unterstützt benutzerdefinierte induktive Prädikate, wodurch SEAL seine eigenen Prädikate definieren kann, ohne dass eine integrierte Solver-Unterstützung für diese vorliegen muss.
Analyse-Mechanik:
- Schleifen-Fixpunkte: Ein Fixpunkt wird erreicht, wenn die Entailment zwischen dem aktuellen Schleifeniterationszustand ( $S$ ) und dem vorherigen Iterationszustand ( $T$ ) gültig ist. Dies wird approximiert, indem geprüft wird, ob für jeden Heap in $S$ ein Heap in $T$ existiert, der ihn entails.
- Interprozedurale Analyse: Funktionsaufrufe werden mittels Summaries (Precondition/Postcondition-Paare) optimiert.
- Vereinfachung: Das System wendet syntaktische Vereinfachungen an, wie etwa die Reduktion von Äquivalenzklassen und das Entfernen von Variablen außerhalb des Gültigkeitsbereichs.

Zentrale Beiträge

Modulare Architektur: Durch die Trennung der abstrakten Interpretation von der logischen Argumentations-Engine via ASTRAL erreicht SEAL ein Design, das darauf ausgelegt ist, leichter erweiterbar zu sein und mit der Argumentation in anderen Theorien kombiniert werden zu können.
Allgemeingültiges Lösen: Die Integration von ASTRAL ermöglicht es SEAL, SMT-Solver für SL-Entailment und Erfüllbarkeit zu nutzen, wodurch die Notwendigkeit für kundenspezifische, dedizierte Solver für jede spezifische Logikvariante entfällt.
Verifizierung ungebundener Listen: Das Werkzeug ist in der Lage, Programme mit ungebundenen verknüpften Listen zu verifizieren, eine Kategorie, in der viele konkurrierende Werkzeuge scheitern.

Experimentelle Ergebnisse

SEAL nahm an der Kategorie MemSafety-LinkedLists des SV-COMP-Wettbewerbs teil.

Gesamtleistung: Von den insgesamt 134 Programmen verifizierte SEAL 55 als "True" (korrekt) und fand 4 "False" (Bugs), wobei 75 kein Ergebnis meldeten.
Teilmenge Ungebundene Listen: In der Teilmenge von 69 Programmen, die eine Argumentation über ungebundene Datenstrukturen erfordern, verifizierte SEAL 14 Programme als korrekt und fand 2 Bugs.
Vergleich:
- SEAL übertraf 2LS (welches nur 3 ungebundene Programme verifizierte).
- SEAL verifizierte weniger Programme als PREDATORHP (46) und CPACHECKER (40), die beide Symbolic Memory Graphs (SMGs) verwenden.
- SEAL war einer von nur vier Analysatoren, die in der Lage waren, Programme mit ungebundenen Listen in dieser Kategorie zu verifizieren.

Bedeutung und Ansprüche

Das Paper positioniert SEAL als vielversprechenden Prototyp mit einem spezifischen Fokus auf Erweiterbarkeit statt auf unmittelbare rohe Leistungsdominanz.

Zukünftiges Potenzial: Die Autoren behaupten, dass das modulare Design von SEAL und die Abhängigkeit von ASTRAL eine starke Basis für die Unterstützung komplexer Datenstrukturen bilden, die nicht leicht durch SMGs dargestellt werden können, wie etwa Skip-Listen und Bäume.
Limitierungen: Als früher Prototyp unterstützt SEAL derzeit nur eine Teilmenge von C (begrenzte Pointer-Arithmetik, spezifisches Integer-Tracking) und verlässt sich auf heuristische Prädikat-Vermutungen, was zu False Positives oder der Unfähigkeit führen kann, Verletzungen zu melden, wenn Integer-Informationen fehlen.
Roadmap: Die Autoren beabsichtigen, die Prädikatswahl während der Analyse zu verbessern, induktive Prädikate aus Beispielen zu synthetisieren und SEAL potenziell als abstrakte Domäne in das Frama-C EVA-Framework einzubetten, um komplexere Nicht-Pointer-Werte zu handhaben.

Zusammenfassend zeigt SEAL, dass ein allgemeingültiger, SMT-basierter Ansatz zur Lösung von Separation Logic eine praktikable und erweiterbare Alternative zu spezialisierten Heuristiken darstellt und einen Weg zur Verifizierung komplexer, ungebundener Datenstrukturen in zukünftigen Wettbewerben eröffnet.