💻 computer science

Predicate Subtypes in VerCors

This paper presents a prototype implementation in the VerCors program verifier that adds support for predicate subtypes to specify variable range constraints, featuring automatic specification generation, the ability to combine multiple subtypes, and a strict mode for enhanced overflow checking.

Original authors: Tycho Dubbeling (University of Twente), Marieke Huisman (University of Twente), Ömer Şakar (University of Twente)

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tycho Dubbeling (University of Twente), Marieke Huisman (University of Twente), Ömer Şakar (University of Twente)

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 building a house of cards. In the world of computer programming, the "cards" are variables (like numbers or lists), and the "house" is the software. Usually, when you declare a variable, you just say, "This is a number." But in reality, not just any number will do. Maybe you need a number that is never zero (so you don't divide by it), or a number that fits inside a tiny box (so it doesn't break the system).

This paper introduces a new feature for a tool called VerCors, which is like a super-smart inspector that checks if your house of cards will stand up before you even build it. The new feature is called Predicate Subtypes.

Here is the breakdown of how this works, using some everyday analogies:

1. The Problem: The "Any Number" Mistake

Imagine you tell a construction worker, "Bring me a brick." They might bring you a giant boulder, a tiny pebble, or a real brick. If your wall needs a specific size, the boulder will crash the whole thing.

In programming, if you tell the computer, "This variable is an integer," the computer assumes it can be any integer, from negative infinity to positive infinity. But in the real world (and in specific programs), we often need to say, "This integer must be between 0 and 100," or "This integer must never be zero."

Without this feature, the computer might miss a mistake where a number gets too big (an overflow) or becomes zero when it shouldn't, causing the program to crash later.

2. The Solution: The "Special Label" (Predicate Subtypes)

The authors added a way to put a special label on your variables. Instead of just saying "This is a number," you can say:

"This is a Non-Zero Number."
"This is a Short Number (between -128 and 127)."
"This is a Valid Index (a number that fits inside this specific list)."

In the paper, they call these Predicate Subtypes. Think of it like a VIP pass. If a variable has the "Non-Zero" VIP pass, the computer knows it is strictly forbidden to be zero.

3. How the Inspector Works (Automatic Checks)

The coolest part of this paper is that the VerCors tool does the heavy lifting automatically. You don't have to write a hundred different checks to make sure your numbers are safe.

The Magic Translator: When you write int x with a "Non-Zero" label, VerCors acts like a translator. It secretly rewrites your code behind the scenes to add safety checks.
The Guard at the Door: Every time you try to put a new value into that variable, VerCors puts a guard at the door. The guard checks: "Does this new value satisfy the label?"
- If you try to put 0 into a "Non-Zero" variable, the guard stops you and says, "Error! This doesn't fit the label."
- If you try to put 5, the guard says, "All clear!"

4. The "Strict Mode": Checking the Journey, Not Just the Destination

This is the most clever part of the paper. Sometimes, the final result is fine, but the journey to get there was dangerous.

The Analogy: Imagine you are driving a car that can only carry 100 pounds of cargo.

Normal Mode: You load 50 pounds, drive over a bridge that collapses under 200 pounds, and then drop off 50 pounds. The final weight is 50 (safe), but you crashed the bridge on the way!
Strict Mode: The car has a "Strict" label. This means every single step of the journey must stay under 100 pounds. Even if you are just doing a quick math calculation in the middle of the road, the computer checks if that temporary number is safe.

The paper introduces a "Strict Arithmetic" mode. If you turn this on, VerCors checks every tiny math operation (like x - 2) to make sure it doesn't temporarily explode the size limit, even if the final answer is safe. This is crucial for preventing "overflows" (when a number gets too big for the computer to handle).

5. Mixing and Matching Labels

Just like you can wear a hat and a scarf at the same time, you can combine these labels.

You can say a variable must be Non-Zero AND Positive.
You can say it must be Either a Short Number OR a Long Number.
You can even say "If it's not Null, then it must be Length 3."

The tool handles all these complex combinations automatically, turning them into simple safety checks that the computer can understand.

Why Does This Matter?

In the past, programmers had to manually write safety checks everywhere, which is tedious and easy to mess up. Or, they had to use very rigid systems that couldn't handle complex rules.

This paper shows that VerCors can now:

Understand complex rules about your data (like "this list must have exactly 3 items").
Automatically check that those rules are never broken, even in the middle of a calculation.
Catch dangerous overflows before the program ever runs, saving time and preventing crashes.

Summary

Think of Predicate Subtypes as giving your computer a pair of smart glasses. Instead of just seeing "a number," the computer sees "a number that must be between 0 and 100." The VerCors tool then acts as a strict bouncer, checking every single time a number tries to enter a room (or a variable) to make sure it's wearing the right ID badge. If it's not, the bouncer stops the program before it can cause a disaster.

1. Problem Statement

Program verification often requires specifying constraints on variable values (e.g., a divisor must be non-zero, an array index must be within bounds, or an integer must not overflow). While standard type systems define broad categories (e.g., int), they often lack the expressiveness to enforce specific value ranges or logical properties without resorting to verbose manual annotations.

The specific challenges addressed in this paper include:

Expressiveness: Existing type systems in languages like Java or C cannot easily encode complex value constraints (e.g., "an integer between 0 and 128") directly in the type signature.
Verification Overhead: Manually writing preconditions, postconditions, and intermediate assertions for every variable constraint is error-prone and tedious.
Overflow Detection: Standard deductive verifiers often model integers as mathematical integers (unbounded). This abstraction misses critical runtime behaviors like integer overflows, which can lead to undefined behavior or crashes in languages like Java and C.
Decidability: Type checking with predicate subtypes is generally undecidable. Therefore, a mechanism is needed to translate these high-level type constraints into verifiable logical checks without relying on a decidable type-checking algorithm.

2. Methodology

The authors propose an approach to integrate Predicate Subtypes into VerCors, a deductive program verifier for concurrent programs (supporting Java, C, and its own language PVL). The core methodology involves automatically translating predicate subtype declarations into standard contract-based specifications (preconditions, postconditions, and assertions) within VerCors.

Key Technical Mechanisms:

Translation to Contracts: Instead of modifying the core type checker, the system treats predicate subtypes as syntactic sugar.
- Parameters: Subtypes on input parameters are translated into requires clauses (preconditions).
- Return Values: Subtypes on return types are translated into ensures clauses (postconditions).
- Assignments: When a value is assigned to a subtyped variable, an assert statement is automatically generated after the assignment to verify the new value satisfies the predicate.
Composition of Predicates: The system supports combining multiple subtypes using logical operators:
- Conjunction: subtype1 subtype2 (AND)
- Disjunction: subtype1 | subtype2 (OR)
- Implication: subtype1 ==> subtype2
- Negation: !subtype
- Parametrization: Predicates can take arguments (e.g., Index(length)), allowing for dynamic range definitions.
Strict Mode for Overflow Checking: To address the issue of intermediate expression overflows, the authors introduce a strict mode.
- In standard mode, only the final result of an expression needs to satisfy the subtype.
- In strict mode (enabled via a --strict-arithmetic flag), every subexpression must also satisfy the subtype bounds.
- This is implemented by defining a strictInt subtype (e.g., $-2^{31} \le x \le 2^{31}-1$ ) and rewriting all int operations to enforce these bounds at every step.

3. Key Contributions

Automated Specification Generation: The primary contribution is a fully automated mechanism that converts user-defined predicate subtype declarations into standard VerCors specifications (pre/postconditions and assertions). This removes the burden of manual annotation for developers.
Flexible Subtype Composition: The implementation supports complex logical combinations of subtypes (AND, OR, IMPLIES, NOT) and parametrized subtypes, offering greater flexibility than existing tools like Dafny's subset types.
Strict Subtype Checking for Overflows: The introduction of the "strict" keyword and the corresponding --strict-arithmetic flag allows VerCors to detect integer overflows in intermediate expressions, a feature often missing in tools that abstract integers to mathematical integers.
Prototype Implementation in VerCors: The authors integrated this logic into the VerCors compiler pipeline. The process involves:
- Parsing subtype annotations in the Java/PVL grammar.
- Building a syntax tree with TSubtype nodes.
- Rewriting the AST to inline predicates and generate necessary assertions.
- Translating the result to the Viper intermediate representation for verification.

4. Results

Prototype Functionality: The prototype successfully handles predicate subtypes for parameters, return values, and local variables in Java and PVL.
Overflow Detection: The strict mode successfully identifies cases where intermediate calculations (e.g., x - 2 in a range-constrained variable) would overflow, even if the final result is valid.
Comparison with Dafny: The paper notes that while Dafny supports subset types and newtypes, VerCors offers more flexibility in expressing parametrized subtypes and allows for a mix of strict and non-strict checking modes within the same verification workflow.
Proof Obligation Management: The authors chose to inline predicate definitions rather than keeping them as separate function calls. This decision was made to manage the volume of proof obligations, ensuring that the verification effort remains reasonable despite the generation of many assertions.

5. Significance

Enhanced Safety for Concurrent Programs: By automating the specification of value constraints, VerCors becomes more effective at verifying concurrent programs where data races and invalid states (like division by zero or out-of-bounds access) are critical.
Bridging the Abstraction Gap: The ability to switch between mathematical integer abstraction (for easier proving) and strict bounded integer checking (for overflow safety) gives developers fine-grained control over the verification process.
Extensibility: The approach is language-agnostic regarding the underlying logic; it relies on the translation to first-order logic specifications, making it adaptable to other verification backends.
Future Impact: The work lays the groundwork for a standard library of predefined subtypes (e.g., NonNull, SafeIndex) and potential integration with C front-ends, moving closer to a seamless verification experience for real-world software systems.

Limitations and Future Work

The paper acknowledges that the current strict arithmetic implementation is limited to 32-bit signed integers (int) because the VerCors AST currently treats all Java integers as a single mathematical type. Future work aims to distinguish between different integer sizes (e.g., byte, short, long) to support strict checking for all types. Additionally, the authors plan to improve error messages, as the current inlining strategy can obscure the original predicate name when a verification failure occurs.