Dafny — Verified Programming with Contracts

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

Dafny is a verification-aware programming language that compiles to C# and automatically proves that programs meet their specifications using preconditions, postconditions, and loop invariants.

Learning Path

flowchart LR
  A["First-Order Logic"] --> B["Dafny
Verified Programming"]
  B --> C["Separation Logic"]
  B --> D["Invariant Generation"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Imperative programming in C# or Java. Basic understanding of Propositional Logic and program correctness.

What Is Dafny?

Dafny integrates specification and implementation in one language. You write a method, annotate it with requires (precondition) and ensures (postcondition), and Dafny's verifier proves the method meets its contract.

Dafny uses an SMT Solver (Z3) under the hood to verify correctness automatically.

Step-by-Step: Your First Dafny Method

Step 1: Install Dafny

dotnet tool install --global dafny

Step 2: Write a Verified Method

method Abs(x: int) returns (r: int)
    ensures r >= 0
    ensures r == x || r == -x
{
    if x < 0 {
        r := -x;
    } else {
        r := x;
    }
}

Step 3: Python Equivalent

def abs_verified(x):
    # postcondition: r >= 0 and (r == x or r == -x)
    if x < 0:
        r = -x
    else:
        r = x
    assert r >= 0
    assert r == x or r == -x
    return r

test_cases = [-5, 0, 3, -100]
for t in test_cases:
    r = abs_verified(t)
    print(f"abs({t}) = {r}")

Expected output:

abs(-5) = 5
abs(0) = 0
abs(3) = 3
abs(-100) = 100

Step-by-Step: Loop Invariants

Loops require invariants — properties that hold before, during, and after the loop.

Step 1: Write a Method with a Loop

method Sum(n: nat) returns (s: int)
    ensures s == n * (n + 1) / 2
{
    s := 0;
    var i := 0;
    while i <= n
        invariant 0 <= i <= n + 1
        invariant s == i * (i - 1) / 2
        decreases n - i
    {
        s := s + i;
        i := i + 1;
    }
}

Step 2: Python Verification

def sum_verified(n):
    s = 0
    i = 0
    while i <= n:
        # invariant: s == i * (i - 1) / 2
        assert 0 <= i <= n + 1
        assert s == i * (i - 1) // 2
        s = s + i
        i = i + 1
    # postcondition: s == n * (n + 1) / 2
    assert s == n * (n + 1) // 2
    return s

result = sum_verified(10)
print(f"Sum(10) = {result}")

Expected output:

Sum(10) = 55

Step-by-Step: Array Bounds Verification

Dafny proves every array access is within bounds.

method FindMax(a: array<int>) returns (max: int)
    requires a.Length > 0
    ensures forall i :: 0 <= i < a.Length ==> a[i] <= max
    ensures exists i :: 0 <= i < a.Length && a[i] == max
{
    max := a[0];
    var i := 1;
    while i < a.Length
        invariant 1 <= i <= a.Length
        invariant forall j :: 0 <= j < i ==> a[j] <= max
        invariant exists j :: 0 <= j < i && a[j] == max
    {
        if a[i] > max {
            max := a[i];
        }
        i := i + 1;
    }
}

def find_max_verified(arr):
    assert len(arr) > 0
    max_val = arr[0]
    i = 1
    while i < len(arr):
        # invariant: all elements seen are <= max
        for j in range(i):
            assert arr[j] <= max_val
        if arr[i] > max_val:
            max_val = arr[i]
        i += 1
    # postcondition: all elements <= max and at least one equals max
    assert all(x <= max_val for x in arr)
    assert any(x == max_val for x in arr)
    return max_val

arr = [3, 7, 2, 9, 1, 5]
print(f"Max of {arr} = {find_max_verified(arr)}")

Expected output:

Max of [3, 7, 2, 9, 1, 5] = 9

Common Errors

1. Weak Loop Invariants

If the invariant is too weak, Dafny cannot prove the postcondition. Add enough detail about what the loop has done so far.

2. Missing Decreases Clause

For termination, Dafny needs a decreases expression that strictly decreases each iteration.

3. Quantifier Triggers

forall and exists need proper triggers for SMT solving. Use explicit triggers or avoid heavy quantification.

4. Array Modification After Allocation

Dafny tracks which array indices may have changed. Use framing and modifies clauses for clarity.

5. Non-Linear Arithmetic

Dafny's SMT Solver handles linear arithmetic well but struggles with non-linear (multiplication) beyond simple cases.

Practice Questions

Q1: What does requires specify?

A precondition that callers must satisfy before calling the method.

Q2: What does ensures specify?

A postcondition that the method guarantees after execution.

Q3: Why are loop invariants needed?

They enable Dafny to reason about loops without executing them infinitely. The invariant must hold before the loop, after each iteration, and after the loop exits.

Q4: What is a ghost variable?

A variable used only for verification that does not appear in the compiled code.

Q5: Can Dafny verify pointer-based data structures?

Yes, Dafny supports seq and set types and can reason about linked structures through framing.

Challenge

Write a Dafny method that finds the index of a target value in a sorted array using binary search. Specify the precondition that the array is sorted and the postcondition that the result is -1 (if not found) or the correct index (if found). Prove it using loop invariants.

FAQ

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