💻 computer science

Scalable Deductive Verification of Data-Level Parallel Programs

This paper presents and implements scalable techniques in the VerCors verifier for deductively verifying data-level parallel programs, including quantifier rewriting and improved alias handling, which collectively reduce verification time by an average factor of 9 and enable previously unobtainable proofs.

Original authors: Lars B. van den Haak, Anton Wijs, Marieke Huisman

Published 2026-05-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lars B. van den Haak, Anton Wijs, Marieke Huisman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head of a massive, high-speed factory (a computer's GPU) where thousands of workers (threads) are performing the exact same task on different pieces of raw material (data arrays). Your job is to write a rulebook to prove that these workers will never make a mistake, break anything, or step on each other's toes. This process is called deductive verification.

However, the paper explains that writing this rulebook for modern factories is incredibly difficult and slow. The authors, Lars, Anton, and Marieke, have invented three new tools to make this process faster and to solve problems that were previously impossible to fix.

Here is how they did it, using simple analogies:

1. The "Confusing Address" Problem (Nested Quantifiers)

The Problem:
In your factory, you might have a rule like: "For every worker, check the box at position WorkerID + (WorkerNumber × 100)."
To a computer proof-checker, this address is a math puzzle. It's like trying to find a specific house in a city where the address is written as a complex equation. The computer gets stuck trying to figure out which house the rule applies to, and the verification process grinds to a halt.

The Solution:
The authors created a mathematical translator. They take that confusing equation and rewrite it into a simple, direct address.

Before: "Check the box at ID + (Number × 100)."
After: "Check the box at BoxNumber."

They proved this translation is 100% correct (using a separate, rigorous math tool called Lean). Now, the computer can instantly see which box to check without doing the heavy math. This alone made the verification process 9 times faster on average, and in some extreme cases, 150 times faster.

2. The "Ghost Overlap" Problem (Aliasing)

The Problem:
Imagine you have two boxes, Box A and Box B. The computer doesn't know if they are two separate boxes or if they are actually the same box with two different names (aliases). To be safe, the computer has to check every possible scenario where they might overlap. If you have 100 boxes, the number of "what if" scenarios explodes, making the verification take forever.

The Solution:
The authors introduced two new "stickers" you can put on your data:

The "Unique" Sticker: This says, "I promise this box is the only one of its kind in this room. No other box can be in the same spot." This tells the computer, "Don't worry about overlaps; they are impossible here."
The "Immutable" Sticker: This says, "This box is made of stone. No one can change what's inside it." Because it never changes, the computer can treat it like a simple, unchangeable list rather than a complex, shifting object.

By using these stickers, the computer stops wasting time checking for overlaps that don't exist.

3. The "Monolithic Block" Problem (Kernel Extraction)

The Problem:
Sometimes, the factory workers are given one giant, 1,000-page instruction manual to read all at once. It's overwhelming and slow.

The Solution:
The authors suggest breaking that giant manual into smaller, separate booklets. They created a tool that automatically splits the big factory task into smaller, independent jobs, verifies each one separately, and then puts the results together. This keeps the computer's memory clear and focused.

The Real-World Test

The authors tested these tools on two types of real-world "factories":

CLBlast: A library of standard math operations used in graphics and AI.
Radio Telescope Pipeline: A complex system used to process signals from space (specifically an algorithm called "Padre").

The Results:

Speed: On average, the new methods made the verification 9 times faster. Some specific tasks became 150 times faster.
Success: Most importantly, they were able to verify the Radio Telescope Pipeline completely. Before these tools, this specific system was too complex to verify; the computer would give up and say, "I can't prove this is safe." With the new tools, they successfully proved it was safe.

Summary

Think of the authors as mechanics who fixed a very slow, clogged engine.

They simplified the fuel lines (rewriting the math addresses) so the engine runs smoother.
They labeled the parts (Unique/Immutable stickers) so the engine doesn't waste time checking for parts that don't exist.
They broke the engine down into smaller pieces to work on them individually.

The result is a machine that runs much faster and can now handle jobs that were previously too heavy to lift.

Technical Summary: Scalable Deductive Verification of Data-Level Parallel Programs

Problem Statement
Deductive verification of data-level parallel programs (e.g., GPU kernels using CUDA, OpenCL, or SYCL) faces significant scalability challenges. These programs typically manipulate large arrays and matrices, leading to formal contracts rich in nested quantifiers. The primary bottlenecks identified are:

Quantifier Instantiation: SMT solvers struggle with nested quantifiers containing arithmetic expressions in array indices (e.g., A[i * stride + offset]). Standard E-matching (trigger-based instantiation) requires triggers to be simple patterns; arithmetic operations within triggers often prevent the solver from finding suitable instantiations, leading to verification failure or excessive time.
Alias Reasoning: Programs utilizing multiple arrays or matrices often require reasoning about whether these structures overlap (aliasing). In separation logic, verifying non-overlapping permissions for potentially overlapping arrays generates a quadratic number of proof obligations, drastically increasing verification time.

Methodology
The authors propose three integrated techniques implemented within VerCors, a deductive program verifier based on permission-based separation logic and the Viper intermediate verification language.

Quantifier Rewriting for Trigger Generation:
The paper introduces a procedure to rewrite expressions with nested or complex quantifiers into equivalent forms with single quantifiers and arithmetic-free triggers.
- Mechanism: The method identifies linear arithmetic indexing patterns of the form $f(x_1, \dots, x_k) = \sum a_i x_i + b$ . It defines a bijective mapping (inverse function $f^{-1}$ ) from the linear index back to the original quantified variables.
- Transformation: The original quantifier $\forall x_1, \dots, x_k; \dots; R(A[f(x_1, \dots, x_k)], \dots)$ is rewritten to $\forall x; Y(x); R(A[x], f^{-1}(x))$ . This allows $A[x]$ to serve as a valid trigger for the SMT solver.
- Correctness: The procedure's correctness is formally proven using the Lean theorem prover (approx. 2500 lines of code), ensuring the rewritten quantifier is logically equivalent to the original under specific conditions regarding bounds and coefficients.
Unique and Immutable Type Qualifiers:
To address aliasing and permission overhead, the authors introduce two type qualifiers:
- Immutable: Indicates that data pointed to by a pointer does not change during execution. This allows the verifier to model the data as mathematical sequences rather than mutable heap blocks, eliminating the need for permission tracking and reducing the complexity of heap snapshots.
- Unique: Assigns a uniqueness number to pointers. Pointers with different uniqueness numbers are guaranteed not to alias. This allows the verifier to encode non-overlapping arrays into distinct fields in the Viper backend, preventing the quadratic explosion of snapshot comparisons required to check for aliasing.
- Integration: These qualifiers are compatible with existing libraries and allow for flexible type checking, ensuring that functions expecting non-unique arrays can still accept unique ones if the uniqueness constraints are respected.
Kernel Body Extraction:
The authors observe that verifying monolithic GPU kernels is often slower due to the sheer volume of information presented to the SMT solver. They propose an automated extraction strategy where the kernel body is moved into a separate function with its own contract. This modularization reduces the context size for the solver, improving performance.

Key Contributions

Formal Rewrite Procedure: A mathematically proven method to flatten nested quantifiers with arithmetic indices into single-quantifier forms suitable for E-matching, implemented in VerCors.
Type-Based Aliasing Reduction: The introduction of unique and immutable qualifiers to explicitly guide the verifier on memory layout and mutability, significantly reducing the search space for aliasing checks.
Comprehensive Evaluation: A large-scale experimental evaluation covering:
- CLBlast Library: A suite of OpenCL kernels implementing Basic Linear Algebra Subprograms (BLAS).
- Radio Telescope Pipeline: A case study involving the Padre algorithm and other optimized parallel CPU programs generated from the Halide DSL.
Artifact Availability: All experimental data, the Lean proof, and the specific VerCors version used are provided in an accompanying artifact.

Results
The experiments demonstrate substantial improvements in scalability and success rates:

CLBlast Kernels: Applying the combined techniques (rewriting, unique/immutable types, and extraction) resulted in an average verification time reduction by a factor of 9. In specific outliers (e.g., the xger kernel), verification was 150 times faster. Crucially, the combination of techniques enabled the verification of kernels (like xger and xher2) that were previously unverifiable or highly brittle (failing in many runs).
Radio Telescope Pipeline: The techniques allowed for the verification of the perform_iteration algorithm (Padre), which was previously unobtainable in earlier studies. Verification times for successful cases were reduced by factors ranging from 1.2 to 3.4 depending on the specific algorithm and configuration.
Dependency on Rewriting: The authors note that without the quantifier rewriting procedure, none of the reported experiments could be verified at all, highlighting its foundational role.

Significance
The paper claims that these techniques address fundamental bottlenecks in the deductive verification of data-parallel programs. By automating the generation of suitable triggers for complex array accesses and reducing the overhead of alias reasoning through type qualifiers, the authors enable the verification of complex, real-world GPU and parallel CPU kernels that were previously infeasible. The work bridges the gap between theoretical separation logic and practical, scalable verification of high-performance computing code, specifically demonstrating success on the Padre algorithm used in radio telescope data processing. The authors emphasize that while manual rewriting is possible, the automatic detection and application of these patterns are essential for the structured, automated verification of GPU kernels.

1. The "Confusing Address" Problem (Nested Quantifiers)

2. The "Ghost Overlap" Problem (Aliasing)

3. The "Monolithic Block" Problem (Kernel Extraction)

The Real-World Test

Summary

More like this