💻 computer science

Scalable Deductive Verification of Data-Level Parallel Programs

Dieser Artikel stellt skalierbare Techniken im VerCors-Verifizierer zur deduktiven Verifizierung datenebenenparalleler Programme vor und implementiert diese, einschließlich der Umformung von Quantoren und einer verbesserten Alias-Behandlung, die gemeinsam die Verifizierungszeit im Durchschnitt um den Faktor 9 reduzieren und zuvor nicht erreichbare Beweise ermöglichen.

Ursprüngliche Autoren: Lars B. van den Haak, Anton Wijs, Marieke Huisman

Veröffentlicht 2026-05-14

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Lars B. van den Haak, Anton Wijs, Marieke Huisman

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 sind der Leiter einer riesigen, hochgeschwindigkeitsfähigen Fabrik (der GPU eines Computers), in der Tausende von Arbeitern (Threads) exakt dieselbe Aufgabe an verschiedenen Rohmaterialstücken (Datenarrays) ausführen. Ihre Aufgabe besteht darin, ein Regelbuch zu verfassen, das beweist, dass diese Arbeiter niemals einen Fehler machen, etwas beschädigen oder sich gegenseitig in die Quere kommen. Dieser Prozess wird als deduktive Verifikation bezeichnet.

Das Papier erklärt jedoch, dass das Verfassen dieses Regelbuchs für moderne Fabriken unglaublich schwierig und langsam ist. Die Autoren Lars, Anton und Marieke haben drei neue Werkzeuge erfunden, um diesen Prozess zu beschleunigen und Probleme zu lösen, die zuvor unmöglich zu beheben waren.

Hier ist, wie sie es getan haben, unter Verwendung einfacher Analogien:

1. Das Problem des „verwirrenden Adressen" (Verschachtelte Quantoren)

Das Problem:
In Ihrer Fabrik könnte es eine Regel geben wie: „Für jeden Arbeiter prüfe die Kiste an der Position WorkerID + (WorkerNumber × 100)."
Für einen Computer-Verifikator ist diese Adresse ein mathematisches Rätsel. Es ist wie der Versuch, ein bestimmtes Haus in einer Stadt zu finden, dessen Adresse als komplexe Gleichung geschrieben ist. Der Computer gerät in die Verlegenheit, herauszufinden, auf welches Haus die Regel zutrifft, und der Verifikationsprozess kommt zum Stillstand.

Die Lösung:
Die Autoren schufen einen mathematischen Übersetzer. Sie nehmen diese verwirrende Gleichung und schreiben sie in eine einfache, direkte Adresse um.

Vorher: „Prüfe die Kiste an ID + (Number × 100)."
Nachher: „Prüfe die Kiste an BoxNumber."

Sie bewiesen, dass diese Übersetzung zu 100 % korrekt ist (unter Verwendung eines separaten, strengen mathematischen Werkzeugs namens Lean). Nun kann der Computer sofort erkennen, welche Kiste zu prüfen ist, ohne die schwere Mathematik betreiben zu müssen. Allein dies machte den Verifikationsprozess im Durchschnitt 9-mal schneller, und in einigen extremen Fällen 150-mal schneller.

2. Das Problem des „Geister-Überlappens" (Aliasing)

Das Problem:
Stellen Sie sich vor, Sie haben zwei Kisten, Kiste A und Kiste B. Der Computer weiß nicht, ob es sich um zwei separate Kisten handelt oder ob sie tatsächlich dieselbe Kiste mit zwei verschiedenen Namen (Aliases) sind. Um auf der sicheren Seite zu sein, muss der Computer jedes mögliche Szenario prüfen, in dem sie sich überlappen könnten. Wenn Sie 100 Kisten haben, explodiert die Anzahl der „Was-wäre-wenn"-Szenarien, sodass die Verifikation ewig dauert.

Die Lösung:
Die Autoren führten zwei neue „Aufkleber" ein, die Sie auf Ihre Daten kleben können:

Der „Eindeutig"-Aufkleber: Dieser besagt: „Ich verspreche, dass diese Kiste die einzige ihrer Art in diesem Raum ist. Keine andere Kiste kann sich am selben Ort befinden." Dies sagt dem Computer: „Machen Sie sich keine Sorgen um Überlappungen; diese sind hier unmöglich."
Der „Unveränderlich"-Aufkleber: Dieser besagt: „Diese Kiste ist aus Stein gefertigt. Niemand kann ändern, was sich darin befindet." Da sie sich nie ändert, kann der Computer sie wie eine einfache, unveränderliche Liste behandeln, anstatt wie ein komplexes, sich verschiebendes Objekt.

Durch die Verwendung dieser Aufkleber verschwendet der Computer keine Zeit mehr mit dem Prüfen von Überlappungen, die nicht existieren.

3. Das Problem des „monolithischen Blocks" (Kernel-Extraktion)

Das Problem:
Manchmal erhalten die Fabrikarbeiter einen riesigen, 1.000-seitigen Handbuch, das sie auf einmal lesen müssen. Das ist überwältigend und langsam.

Die Lösung:
Die Autoren schlagen vor, dieses riesige Handbuch in kleinere, separate Broschüren aufzuteilen. Sie schufen ein Werkzeug, das automatisch die große Fabrikaufgabe in kleinere, unabhängige Jobs aufteilt, jeden einzelnen separat verifiziert und dann die Ergebnisse zusammenführt. Dies hält den Arbeitsspeicher des Computers klar und fokussiert.

Der Realwelt-Test

Die Autoren testeten diese Werkzeuge an zwei Arten von echten „Fabriken":

CLBlast: Eine Bibliothek mit Standardmathematischen Operationen, die in Grafik und KI verwendet wird.
Radio Telescope Pipeline: Ein komplexes System zur Verarbeitung von Signalen aus dem Weltraum (speziell ein Algorithmus namens „Padre").

Die Ergebnisse:

Geschwindigkeit: Im Durchschnitt machten die neuen Methoden die Verifikation 9-mal schneller. Bestimmte Aufgaben wurden 150-mal schneller.
Erfolg: Am wichtigsten ist, dass sie in der Lage waren, die Radio Telescope Pipeline vollständig zu verifizieren. Vor diesen Werkzeugen war dieses spezifische System zu komplex, um verifiziert zu werden; der Computer würde aufgeben und sagen: „Ich kann nicht beweisen, dass dies sicher ist." Mit den neuen Werkzeugen gelang es ihnen erfolgreich, die Sicherheit zu beweisen.

Zusammenfassung

Stellen Sie sich die Autoren als Mechaniker vor, die einen sehr langsamen, verstopften Motor reparierten.

Sie vereinfachten die Kraftstoffleitungen (durch Umformulierung der mathematischen Adressen), damit der Motor reibungsloser läuft.
Sie kennzeichneten die Teile (Eindeutig/Unveränderlich-Aufkleber), damit der Motor keine Zeit damit verschwendet, nach Teilen zu suchen, die nicht existieren.
Sie zerlegten den Motor in kleinere Teile, um sie einzeln zu bearbeiten.

Das Ergebnis ist eine Maschine, die viel schneller läuft und nun Aufgaben bewältigen kann, die zuvor zu schwer waren, um sie zu heben.

Technische Zusammenfassung: Skalierbare deduktive Verifikation von datenebenenparallelen Programmen

Problemstellung
Die deduktive Verifikation von datenebenenparallelen Programmen (z. B. GPU-Kernels unter Verwendung von CUDA, OpenCL oder SYCL) steht vor erheblichen Skalierbarkeitsproblemen. Diese Programme manipulieren typischerweise große Arrays und Matrizen, was zu formalen Verträgen führt, die reich an verschachtelten Quantoren sind. Die identifizierten Hauptengpässe sind:

Quantoren-Instantiierung: SMT-Löser haben Schwierigkeiten mit verschachtelten Quantoren, die arithmetische Ausdrücke in Array-Indizes enthalten (z. B. A[i * stride + offset]). Die Standard-E-Matching-Verfahren (trigger-basierte Instantiierung) erfordern Trigger, die einfache Muster sind; arithmetische Operationen innerhalb von Trigger verhindern oft, dass der Löser geeignete Instantiierungen findet, was zu einem Verifikationsversagen oder übermäßiger Laufzeit führt.
Alias-Reasoning: Programme, die mehrere Arrays oder Matrizen verwenden, erfordern oft eine Analyse, ob diese Strukturen sich überlappen (Aliasing). In der Separation-Logik erzeugt die Verifikation nicht-überlappender Berechtigungen für potenziell überlappende Arrays eine quadratische Anzahl von Beweisverpflichtungen, was die Verifikationszeit drastisch erhöht.

Methodik
Die Autoren schlagen drei integrierte Techniken vor, die innerhalb von VerCors implementiert sind, einem deduktiven Programmverifizierer, der auf einer berechtigungsbasierten Separation-Logik und der Zwischenverifikationssprache Viper basiert.

Quantoren-Umschreibung zur Trigger-Generierung:
Die Arbeit stellt ein Verfahren vor, um Ausdrücke mit verschachtelten oder komplexen Quantoren in äquivalente Formen mit einzelnen Quantoren und arithmetikfreien Triggern umzuschreiben.
- Mechanismus: Die Methode identifiziert lineare arithmetische Indexierungsmuster der Form $f(x_1, \dots, x_k) = \sum a_i x_i + b$ . Sie definiert eine bijektive Abbildung (inverse Funktion $f^{-1}$ ) vom linearen Index zurück zu den ursprünglichen quantifizierten Variablen.
- Transformation: Der ursprüngliche Quantor $\forall x_1, \dots, x_k; \dots; R(A[f(x_1, \dots, x_k)], \dots)$ wird umgeschrieben zu $\forall x; Y(x); R(A[x], f^{-1}(x))$ . Dies ermöglicht es, dass $A[x]$ als gültiger Trigger für den SMT-Löser dient.
- Korrektheit: Die Korrektheit des Verfahrens wird formal mit dem Lean-Theorembeweiser (ca. 2500 Zeilen Code) bewiesen, wodurch sichergestellt wird, dass der umgeschriebene Quantor unter spezifischen Bedingungen bezüglich Schranken und Koeffizienten logisch äquivalent zum Original ist.
Eindeutige und unveränderliche Typqualifikatoren:
Um Aliasing und Berechtigungs-Overhead zu adressieren, führen die Autoren zwei Typqualifikatoren ein:
- Immutable (Unveränderlich): Gibt an, dass Daten, auf die ein Pointer zeigt, während der Ausführung nicht verändert werden. Dies ermöglicht es dem Verifizierer, die Daten als mathematische Sequenzen anstelle von veränderbaren Heap-Blöcken zu modellieren, wodurch die Notwendigkeit der Berechtigungsverfolgung entfällt und die Komplexität von Heap-Snapshots reduziert wird.
- Unique (Eindeutig): Weist Pointern eine Eindeutigkeitsnummer zu. Pointer mit unterschiedlichen Eindeutigkeitsnummern garantieren, dass sie nicht aliasieren. Dies ermöglicht es dem Verifizierer, nicht-überlappende Arrays in distincte Felder im Viper-Backend zu kodieren, wodurch die quadratische Explosion von Snapshot-Vergleichen verhindert wird, die zum Prüfen auf Aliasing erforderlich wären.
- Integration: Diese Qualifikatoren sind mit bestehenden Bibliotheken kompatibel und ermöglichen eine flexible Typprüfung, sodass Funktionen, die nicht-eindeutige Arrays erwarten, dennoch eindeutige akzeptieren können, wenn die Eindeutigkeitsbedingungen eingehalten werden.
Extraktion des Kernel-Body:
Die Autoren stellen fest, dass die Verifikation monolithischer GPU-Kernels oft langsamer ist, aufgrund des schieren Volumens an Informationen, das dem SMT-Löser vorgelegt wird. Sie schlagen eine automatisierte Extraktionsstrategie vor, bei der der Kernel-Body in eine separate Funktion mit eigenem Vertrag verschoben wird. Diese Modularisierung reduziert die Kontextgröße für den Löser und verbessert die Leistung.

Hauptbeiträge

Formales Umschreibungsverfahren: Eine mathematisch bewiesene Methode, um verschachtelte Quantoren mit arithmetischen Indizes in Formen mit einzelnen Quantoren zu flachen, die für E-Matching geeignet sind, implementiert in VerCors.
Typbasierte Reduktion von Aliasing: Die Einführung der Qualifikatoren unique und immutable, um den Verifizierer explizit über Speicherlayout und Veränderbarkeit zu führen, was den Suchraum für Aliasing-Prüfungen erheblich reduziert.
Umfassende Evaluation: Eine groß angelegte experimentelle Evaluation, die Folgendes abdeckt:
- CLBlast-Bibliothek: Eine Suite von OpenCL-Kernels, die Basic Linear Algebra Subprograms (BLAS) implementieren.
- Radio-Telescope-Pipeline: Eine Fallstudie, die den Padre-Algorithmus und andere optimierte parallele CPU-Programme umfasst, die aus der Halide-DSL generiert wurden.
Verfügbarkeit des Artefakts: Alle experimentellen Daten, der Lean-Beweis und die spezifische verwendete VerCors-Version werden in einem begleitenden Artefakt bereitgestellt.

Ergebnisse
Die Experimente zeigen erhebliche Verbesserungen in der Skalierbarkeit und den Erfolgsquoten:

CLBlast-Kernels: Die Anwendung der kombinierten Techniken (Umschreibung, unique/immutable-Typen und Extraktion) führte zu einer durchschnittlichen Reduktion der Verifikationszeit um den Faktor 9. Bei spezifischen Ausreißern (z. B. dem xger-Kernel) war die Verifikation 150-mal schneller. Entscheidend ist, dass die Kombination der Techniken die Verifikation von Kernels (wie xger und xher2) ermöglichte, die zuvor unverifizierbar oder sehr instabil waren (in vielen Läufen fehlschlagend).
Radio-Telescope-Pipeline: Die Techniken ermöglichten die Verifikation des perform_iteration-Algorithmus (Padre), die in früheren Studien nicht erreichbar war. Die Verifikationszeiten für erfolgreiche Fälle wurden je nach spezifischem Algorithmus und Konfiguration um Faktoren zwischen 1,2 und 3,4 reduziert.
Abhängigkeit von der Umschreibung: Die Autoren stellen fest, dass ohne das Quantoren-Umschreibungsverfahren keines der berichteten Experimente überhaupt verifiziert werden konnte, was seine fundamentale Rolle unterstreicht.

Bedeutung
Die Arbeit behauptet, dass diese Techniken fundamentale Engpässe in der deduktiven Verifikation von datenparallelen Programmen adressieren. Durch die Automatisierung der Generierung geeigneter Trigger für komplexe Array-Zugriffe und die Reduktion des Overheads des Aliasing-Reasonings durch Typqualifikatoren ermöglichen die Autoren die Verifikation komplexer, realer GPU- und paralleler CPU-Kernels, die zuvor nicht durchführbar waren. Die Arbeit schließt die Lücke zwischen theoretischer Separation-Logik und praktischer, skalierbarer Verifikation von Hochleistungsrechnungscode und demonstriert spezifisch den Erfolg beim Padre-Algorithmus, der in der Verarbeitung von Radioteleskop-Daten verwendet wird. Die Autoren betonen, dass zwar eine manuelle Umschreibung möglich ist, die automatische Erkennung und Anwendung dieser Muster jedoch für die strukturierte, automatisierte Verifikation von GPU-Kernels unerlässlich ist.

1. Das Problem des „verwirrenden Adressen" (Verschachtelte Quantoren)

2. Das Problem des „Geister-Überlappens" (Aliasing)

3. Das Problem des „monolithischen Blocks" (Kernel-Extraktion)

Der Realwelt-Test

Zusammenfassung

Mehr davon