Why3 Verification Platform — Program Verification with Multiple Provers

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

Why3 is a platform for deductive program verification that translates verification conditions to multiple backend provers — SMT solvers (Z3, CVC5), SAT solvers, and interactive proof assistants (Coq, Isabelle) — choosing the strongest tool for each proof obligation.

Learning Path

flowchart LR
  A["Hoare Logic"] --> B["Why3 Platform
Multi-Prover Verification"]
  B --> C["Dafny & Verified Programming"]
  B --> D["Industrial Formal Verification"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Hoare logic basics, first-order logic, and familiarity with at least one SMT Solver.

What Is Why3?

Why3 is a platform that separates two concerns: generating verification conditions from annotated programs, and proving those conditions using external provers. The user writes programs in WhyML, a language with built-in contracts. Why3 generates weakest-precondition verification conditions and dispatches them to Z3, CVC5, Alt-Ergo, or Coq.

This multi-prover approach is Why3's key advantage: arithmetic checks go to SMT solvers, inductive proofs go to Coq, and each prover handles what it is best at.

Step-by-Step: Basic WhyML Program

Step 1: Install Why3

sudo apt-get install why3
why3 config detect

Step 2: Write a Simple Verified Function

module SimpleMath

  use int.Int

  let add_one (x: int) : int
    ensures { result = x + 1 }
  =
    x + 1

  let add (a: int) (b: int) : int
    ensures { result = a + b }
  =
    a + b

end

Step 3: Prove It

why3 prove simple_math.mlw

Expected output:

simple_math.mlw: SimpleMath.add_one: Valid (0.01s)
simple_math.mlw: SimpleMath.add: Valid (0.01s)

Step 4: Python Simulation

def add_one(x):
    result = x + 1
    assert result == x + 1, "Postcondition violated"
    return result

def add(a, b):
    result = a + b
    assert result == a + b, "Postcondition violated"
    return result

print(f"add_one(5) = {add_one(5)}")
print(f"add(3, 7) = {add(3, 7)}")

Expected output:

add_one(5) = 6
add(3, 7) = 10

Step-by-Step: Loop Invariants in Why3

Step 1: Write a Loop with Invariant

module SumProgram

  use int.Int

  let sum_to_n (n: int) : int
    requires { n >= 0 }
    ensures { result = n * (n + 1) / 2 }
  =
    let sum = ref 0 in
    let i = ref 0 in
    while !i <= n do
      invariant { 0 <= !i <= n + 1 }
      invariant { !sum = (!i - 1) * !i / 2 }
      variant   { n - !i }
      sum := !sum + !i;
      i := !i + 1
    done;
    !sum

end

Step 2: Prove with Different Backends

# Try multiple provers
why3 prove --prover "Z3" sum_program.mlw
why3 prove --prover "Alt-Ergo" sum_program.mlw
why3 prove --prover "CVC5" sum_program.mlw

Expected output:

sum_program.mlw: SumProgram.sum_to_n: Valid (0.02s) -- Z3
sum_program.mlw: SumProgram.sum_to_n: Valid (0.03s) -- Alt-Ergo
sum_program.mlw: SumProgram.sum_to_n: Valid (0.02s) -- CVC5

Step 3: Python Equivalent

def sum_to_n(n):
    assert n >= 0
    total = 0
    i = 0
    while i <= n:
        assert 0 <= i <= n + 1
        assert total == (i - 1) * i // 2
        total += i
        i += 1
    result = total
    assert result == n * (n + 1) // 2
    return result

print(f"sum_to_n(10) = {sum_to_n(10)}")

Expected output:

sum_to_n(10) = 55

Step-by-Step: Array Verification

Step 1: Verify Array Bounds

module ArraySum

  use int.Int
  use array.Array

  let array_sum (a: array int) : int
    requires { length a >= 0 }
    ensures { true }
  =
    let s = ref 0 in
    for i = 0 to length a - 1 do
      invariant { !s = sum a[0..i-1] }
      s := !s + a[i]
    done;
    !s

end

Step 2: Model Array Sum in Python

def array_sum(arr):
    total = 0
    for i in range(len(arr)):
        assert 0 <= i < len(arr)
        total += arr[i]
    return total

arr = [1, 2, 3, 4, 5]
print(f"array_sum([1,2,3,4,5]) = {array_sum(arr)}")

Expected output:

array_sum([1,2,3,4,5]) = 15

Multi-Prover Strategy

Why3 can dispatch different verification conditions to different provers:

class MultiProver:
    def __init__(self):
        self.provers = {}

    def add_prover(self, name, can_handle_fn):
        self.provers[name] = can_handle_fn

    def dispatch(self, vc):
        for name, can_handle in self.provers.items():
            if can_handle(vc):
                print(f"Dispatching to {name}: {vc[:50]}...")
                return name
        return "Coq (manual)"

def is_arithmetic(vc):
    return "+" in vc or "*" in vc or "int" in vc.lower()

def is_array(vc):
    return "array" in vc.lower() or "select" in vc.lower()

def is_quantified(vc):
    return "forall" in vc or "exists" in vc

mp = MultiProver()
mp.add_prover("Z3", lambda vc: is_arithmetic(vc))
mp.add_prover("CVC5", lambda vc: is_array(vc))
mp.add_prover("Alt-Ergo", lambda vc: not is_quantified(vc))

vcs = [
    "forall x:int. x + 0 = x",
    "select(store(a, i, v), i) = v",
    "x + y > 0 -> x > -y]
]
for vc in vcs:
    print(f"VC dispatched to: {mp.dispatch(vc)}")

Expected output:

VC dispatched to: Z3
VC dispatched to: CVC5
VC dispatched to: Z3

Common Errors

1. Writing Unprovable Loop Invariants

The invariant must be strong enough to imply the postcondition and preserved by the loop body. Test invariants with small examples first.

2. Forgetting the Variant for Termination

Why3 requires a variant clause for total correctness. Without it, only partial correctness is verified.

3. Using a Single Prover

Different provers excel at different theories. Always try multiple backends. If all fail, use Coq for interactive proof.

4. Ignoring Why3 IDE

The Why3 IDE shows unsolved verification conditions with goals and hypotheses. Use it to debug failing proofs.

5. Not Using Algebraic Data Types

WhyML supports algebraic data types. For verified data structures, define recursive types and prove properties by structural induction.

Practice Questions

Q1: What is the main advantage of Why3 over single-prover verifiers?

Why3 can dispatch verification conditions to multiple backend provers, using the best tool for each subproblem.

Q2: What is a verification condition in Why3?

A logical formula generated from the program and its annotations using weakest-precondition calculus, which must be proved valid.

Q3: How does Why3 handle non-linear arithmetic?

Why3 sends non-linear arithmetic goals to SMT solvers that support non-linear arithmetic (Z3, CVC5). If they fail, users can prove them interactively in Coq.

Q4: What is the WhyML language?

A programming language with built-in contracts, type inference, algebraic data types, and pattern matching, designed for verification.

Q5: Can Why3 verify C or Java code directly?

No. Why3 verifies WhyML programs. To verify C or Java, use front-ends like Frama-C (for C) that translate to WhyML.

Challenge

Write a WhyML program that implements binary search on a sorted array. Annotate it with preconditions (sorted array), postconditions (correct index or -1), and loop invariants. Prove it using Z3 and Alt-Ergo. Then verify termination using a variant.

FAQ

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