💻 computer science

SEAL: Symbolic Execution with Separation Logic (Competition Contribution)

SEAL is a modular, prototype static analyzer for verifying programs with unbounded linked data structures that leverages separation logic and the SMT-based Astral solver to achieve competitive results in the LinkedLists category while offering significant extensibility for future development.

Original authors: Tomáš Brablec, Tomáš Dacík, Tomáš Vojnar

Published 2026-02-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Tomáš Brablec, Tomáš Dacík, Tomáš Vojnar

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 trying to verify that a complex, ever-changing city of roads and buildings is safe to navigate. You need to make sure no one falls off a bridge (a "NULL-pointer dereference"), no one tries to demolish a building that's already gone (a "use-after-free" error), and no one accidentally knocks down a building twice (a "double-free" error).

This is exactly what SEAL does, but instead of a city, it analyzes computer programs that manage complex, shifting lists of data (like linked lists).

Here is how the paper explains SEAL, broken down into simple concepts:

1. The Core Idea: A Specialized Detective

Most tools that check these programs are like detectives who use a specific, rigid rulebook for every type of crime. SEAL is different. It uses a general-purpose "logic engine" called ASTRAL.

Think of ASTRAL as a super-smart translator. When SEAL sees a complex puzzle about how data is connected in memory, it translates that puzzle into a language that a standard, powerful computer solver (called an SMT solver) understands perfectly. This makes SEAL very flexible. It's like having a detective who can switch languages to talk to any expert, rather than being stuck speaking only one dialect.

2. The Challenge: Infinite vs. Finite

The programs SEAL checks often involve linked lists—chains of data where one item points to the next.

The Problem: Some lists are short and fixed (like a chain of 3 links). Others are unbounded, meaning they could be 10 links long, or 10,000, or infinite.
The Difficulty: Trying to check every single possible length of an infinite chain is impossible for a computer. It would take forever.
SEAL's Trick: SEAL uses a technique called abstraction. Imagine you are looking at a very long train. Instead of counting every single car, SEAL says, "Okay, this is a 'long train'." It replaces the messy details of the middle of the chain with a single, neat label (a "predicate"). This allows it to reason about the whole chain without getting lost in the details.

3. How It Works: The "Shape" Analyzer

SEAL is a "shape analyzer." It doesn't just look at numbers; it looks at the shape of the memory.

Symbolic Heaps: It creates a map of the memory using "symbolic heaps." Think of this as a blueprint that says, "Here is a block of memory, and it connects to this other block."
The Loop Fixpoint: When a program runs in a loop (repeating the same action), SEAL checks if the "shape" of the memory has stabilized. If the shape in the current round looks "safe enough" compared to the previous round, it stops checking and declares the loop safe.

4. Current Strengths and Weaknesses

The paper admits SEAL is still a prototype (an early version), but it has some impressive stats:

The Good News (Strengths):

The "Unbounded" Club: In a recent competition, there were 20 tools trying to verify programs with infinite lists. Only four tools succeeded. SEAL was one of them.
Future Potential: Because SEAL uses that flexible "translator" (ASTRAL), it is easier to teach it new shapes. The authors believe they can eventually teach it to handle complex structures like trees or skip-lists (which are like multi-level highways for data) that other tools struggle with.

The Bad News (Weaknesses):

Limited Vocabulary: SEAL currently only understands a small subset of the C programming language. It can't handle complex math with numbers or many types of pointers yet.
Guessing Game: Sometimes, SEAL has to guess what kind of data structure a piece of code is building. If it guesses wrong (e.g., thinking a complex structure is just a simple list), it might miss a bug or give a "I don't know" answer.
False Positives: Because it uses abstractions (simplifying the details), it might sometimes think a program is unsafe when it's actually fine. The paper notes that they could fix this by re-running the check without simplification, but that takes more time.

5. The Bottom Line

SEAL is a new, modular tool designed to prove that programs managing complex, infinite data chains are safe. While it isn't perfect yet and doesn't understand every feature of the C language, its unique design—using a general translator to solve logic puzzles—makes it one of the few tools capable of handling the hardest types of memory safety problems. The authors hope that by keeping the system flexible, they can make it even better in future competitions.

Technical Summary: SEAL – Symbolic Execution with Separation Logic

Problem Statement

The verification of programs manipulating unbounded linked data structures remains a significant challenge in static analysis. While many tools rely on bounded model checking or specialized heuristics, these approaches often struggle with the complexity of reasoning about arbitrary list lengths and complex memory shapes. Furthermore, existing separation logic (SL) based analysers frequently couple analysis with dedicated, non-modular solvers, limiting their extensibility and ability to integrate with other logical theories.

Methodology

SEAL is a static analyser designed for the verification of programs manipulating unbounded linked data structures. It employs forward abstract interpretation over formulae of separation logic (SL). The core methodology distinguishes itself through a modular architecture that cleanly decouples the analysis engine from the logical reasoning engine.

Core Components

Abstract Domain (Symbolic Heaps):
- SEAL represents abstract memory states as symbolic heaps, which are SL formulae of the form $\exists x_1, \dots, x_m. \phi_1 * \dots * \phi_n$ .
- Atomic formulae ( $\phi_i$ $ϕ_{i}$ ) include:
  - Pure formulae: Describing pointer (dis)equalities or constraints on non-pointer values.
  - Points-to atoms: Describing single heap cells.
  - Inductive predicates: Describing unbounded sequences of pointers (e.g., lists).
  - Free memory: A special predicate explicitly represents freed memory that remains reachable.
- The domain tracks precise integer values within a configurable range (default $[-5, 5]$ ). States at program locations are represented as disjunctions (sets) of symbolic heaps.
Abstraction and Widening:
- To handle loops and infinite state spaces, SEAL performs widening by generalizing memory shapes. This involves finding compatible spatial predicates (points-to or list predicates) and joining them into a single list predicate, provided the linking location is not targeted by external pointers or program variables.
- The system tracks minimum list lengths up to a fixed limit to ensure acyclicity guarantees during abstraction.
- Predicate Guessing: Currently, SEAL guesses the expected inductive predicate for C structures before analysis based on field counts (e.g., one self-referential field $\to$ SLL; two $\to$ DLL). This heuristic can lead to misclassification (e.g., a structure intended as a nested list being classified as a doubly-linked list).
The ASTRAL Solver:
- Unlike most SL-based tools that use dedicated heuristics for satisfiability and entailment, SEAL relies on ASTRAL, a general-purpose separation logic solver.
- ASTRAL translates SL formulae into SMT theories (specifically bitvectors and arrays) using a bound on predicate unfolding.
- The translated formulae are passed to the BITWUZLA SMT solver.
- ASTRAL supports user-defined inductive predicates, allowing SEAL to define its own predicates without built-in solver support for them.
Analysis Mechanics:
- Loop Fixpoints: A fixpoint is reached when the entailment between the current loop iteration state ( $S$ ) and the previous iteration state ( $T$ ) is valid. This is approximated by checking if for every heap in $S$ , there exists a heap in $T$ that it entails.
- Interprocedural Analysis: Function calls are optimized using summaries (precondition/postcondition pairs).
- Simplification: The system applies syntactic simplifications, such as reducing equivalence classes and removing out-of-scope variables.

Key Contributions

Modular Architecture: By separating the abstract interpretation engine from the logical reasoning engine via ASTRAL, SEAL achieves a design intended to be easier to extend and combine with reasoning in other theories.
General-Purpose Solving: The integration of ASTRAL allows SEAL to leverage SMT solvers for SL entailment and satisfiability, avoiding the need for custom, dedicated solvers for each specific logic variant.
Unbounded List Verification: The tool is capable of verifying programs with unbounded linked lists, a category where many competing tools fail.

Experimental Results

SEAL participated in the MemSafety-LinkedLists category of the SV-COMP competition.

Overall Performance: On the full set of 134 programs, SEAL verified 55 as "True" (correct) and found 4 "False" (bugs), with 75 reporting no result.
Unbounded Lists Subset: On the subset of 69 programs requiring reasoning about unbounded data structures, SEAL verified 14 programs as correct and found 2 bugs.
Comparison:
- SEAL outperformed 2LS (which verified only 3 unbounded programs).
- SEAL verified fewer programs than PREDATORHP (46) and CPACHECKER (40), both of which use symbolic memory graphs (SMGs).
- SEAL was one of only four analysers capable of verifying programs with unbounded lists in this category.

Significance and Claims

The paper positions SEAL as a promising prototype with a specific focus on extensibility rather than immediate raw performance dominance.

Future Potential: The authors claim that the tool's modular design and reliance on ASTRAL provide a strong foundation for supporting complex data structures that cannot be easily represented by SMGs, such as skip-lists and trees.
Limitations: As an early prototype, SEAL currently supports only a subset of C (limited pointer arithmetic, specific integer tracking) and relies on heuristic predicate guessing, which can lead to false positives or inability to report violations when integer information is missing.
Roadmap: The authors intend to improve predicate selection during analysis, synthesize inductive predicates from examples, and potentially embed SEAL as an abstract domain within the Frama-C EVA framework to handle more complex non-pointer values.

In summary, SEAL demonstrates that a general-purpose, SMT-based approach to separation logic solving is a viable and extensible alternative to specialized heuristics, offering a pathway to verify complex, unbounded data structures in future competitions.