Separation Logic — Reasoning About Pointers and Heap

In this tutorial, you'll learn about Separation Logic. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Separation Logic extends Hoare logic to reason about programs that manipulate pointers and heap-allocated data, enabling modular verification of linked data structures.

Learning Path

flowchart LR
  A["First-Order Logic"] --> B["Separation Logic
Pointers & Heap"]
  B --> C["Invariant Generation"]
  B --> D["Correct-by-Construction"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Hoare logic basics, C Programming with pointers, and first-order logic.

What Is Separation Logic?

Standard Hoare logic cannot reason about aliasing — Two Pointers referring to the same memory location. Separation Logic introduces the separating conjunction P ∗ Q, meaning P and Q hold for disjoint parts of the heap.

The frame rule lets you verify a function once and reuse the proof in any context where the function's footprint is disjoint from other data.

Step-by-Step: Heap Model

Step 1: Define the Heap

class Heap:
    def __init__(self):
        self.store = {}  # address -> value

    def alloc(self, value):
        addr = id(self.store)
        self.store[addr] = value
        return addr

    def read(self, addr):
        return self.store.get(addr)

    def write(self, addr, value):
        self.store[addr] = value

    def dealloc(self, addr):
        if addr in self.store:
            del self.store[addr]

Step 2: Separating Conjunction

Two heap regions are disjoint if they share no addresses:

def disjoint(h1, h2):
    return not (set(h1.store.keys()) & set(h2.store.keys()))

h1 = Heap()
h1.store = {1: "a", 2: "b"}
h2 = Heap()
h2.store = {3: "c"}

print(f"Disjoint: {disjoint(h1, h2)}")
h3 = Heap()
h3.store = {1: "d"}
print(f"Disjoint with overlap: {disjoint(h1, h3)}")

Expected output:

Disjoint: True
Disjoint with overlap: False

Step-by-Step: Specifying Linked Lists

Step 1: Define List Segment Predicate

A singly-linked list segment from pointer p to q:

class list_seg:
    def __init__(self, start, end, heap):
        self.start = start
        self.end = end
        self.heap = heap

    def check(self):
        if self.start == self.end:
            return True
        # start has a valid node pointing further
        curr = self.start
        while curr != self.end:
            node = self.heap.read(curr)
            if node is None:
                return False
            curr = node.get("next")
            if curr is not None and curr == self.start:
                return False  # cycle
        return True

heap = Heap()
n1_addr = heap.alloc({"val": 1, "next": None})
n2_addr = heap.alloc({"val": 2, "next": None})
node1 = heap.read(n1_addr)
node1["next"] = n2_addr
heap.write(n1_addr, node1)

seg = list_seg(n1_addr, None, heap)
print(f"List segment valid: {seg.check()}")

Expected output:

List segment valid: True

Step-by-Step: Verifying a Pointer Swap

Step 1: Specification

def swap(heap, x, y):
    # precondition: x |-> a ∗ y |-> b
    # postcondition: x |-> b ∗ y |-> a
    a = heap.read(x)
    b = heap.read(y)
    heap.write(x, b)
    heap.write(y, a)
    return heap

heap = Heap()
addr1 = heap.alloc(10)
addr2 = heap.alloc(20)
swap(heap, addr1, addr2)
print(f"addr1: {heap.read(addr1)}, addr2: {heap.read(addr2)}")

Expected output:

addr1: 20, addr2: 10

Step 2: Frame Rule Application

The frame rule says: if {P} C {Q} is valid, then {P ∗ R} C {Q ∗ R} is valid for any R disjoint from C's footprint.

This means verifying swap once suffices for any context.

Common Errors

1. Assuming Non-Aliased Pointers

The most common error in heap verification: two function parameters may point to the same location. Separation Logic catches this.

2. Missing the Frame Rule

When a function modifies only a portion of the heap, the frame rule preserves the rest. Failing to apply it loses information about unchanged data.

3. Cyclic Data Structures

Linked list predicates must explicitly forbid cycles. A cycle breaks the inductive definition of list segments.

4. Dangling Pointers After Free

After deallocation, the pointer becomes invalid. Separation Logic tracks liveness through heap predicates.

5. Overlapping Footprints

Two functions with overlapping heap footprints cannot be composed with the frame rule. Restructure code to minimize aliasing.

Practice Questions

Q1: What does P ∗ Q mean in Separation Logic?

P and Q hold for disjoint parts of the heap. They refer to separate memory regions with no overlapping addresses.

Q2: What is the frame rule?

If {P} C {Q} holds, then {P ∗ R} C {Q ∗ R} holds for any R whose footprint is disjoint from C's modified locations.

Q3: How does Separation Logic handle null pointers?

Null is treated as a special value, not a heap location. The predicate x |-> v requires x to be a valid, non-null address.

Q4: What is a symbolic heap?

A symbolic representation of heap state used in automated Separation Logic tools, consisting of spatial predicates and pure formulas.

Q5: Name a tool based on Separation Logic.

Facebook Infer, VeriFast, GRASShopper, and Smallfoot all use Separation Logic for heap verification.

Challenge

Implement a simple doubly-linked list insertion in C. Write a Separation Logic specification for the insert operation (before and after). Show that the specification implies the list remains well-formed after insertion. Use VeriFast or manual reasoning.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.