Z3入门用户求教：如何利用循环不变量验证C代码循环？

Hey there! Let's walk through how to verify your array initialization loop using Z3 and a loop invariant—this is a great first example for getting started with program verification in Z3.

First, let's recap your example code:

int a[10],i; 
for(i = 0; i<10; i++) { 
    a[i] = 0; 
}

Our goal is to prove that after the loop finishes, every element of a[0] to a[9] is equal to 0.

Step 1: Define the Loop Invariant #

A loop invariant is a condition that holds in three key scenarios:

• Before the loop starts (initialization step)
• After every iteration of the loop (preservation step)
• When the loop terminates, it lets us conclude our desired property

For your loop, the right invariant captures two critical facts:

1. The index i stays within valid bounds (0 ≤ i ≤ 10)
2. All elements of a before index i are already set to 0

Formally, that's:

Inv(i, a) = 0 ≤ i ≤ 10 ∧ (∀ k. 0 ≤ k < i → a[k] = 0)

Step 2: Implement Verification with Z3's Python API #

Z3's Python interface is perfect for beginners—it's readable and lets you test conditions incrementally. Here's a complete, annotated example:

from z3 import *

# Declare our variables: a is an array of integers, i is an integer index
a = Array('a', IntSort(), IntSort())
i = Int('i')
k = Int('k')  # Helper variable for universal quantification

# Define our loop invariant
inv = And(
    0 <= i, i <= 10,
    ForAll(k, Implies(And(0 <= k, k < i), a[k] == 0))
)

# 1. Verify the invariant holds initially (i=0, a is any array)
initial_solver = Solver()
initial_solver.add(Not(Implies(i == 0, inv)))
print("Initial condition check:", initial_solver.check())
# If this returns "unsat", our invariant holds initially (no counterexamples)

# 2. Verify the invariant is preserved through one loop iteration
preservation_solver = Solver()
# Assume invariant holds before iteration, and loop condition is true
preservation_solver.add(inv)
preservation_solver.add(i < 10)
# Simulate executing the loop body: new_i = i+1, new_a sets a[i] to 0
new_i = i + 1
new_a = Store(a, i, 0)
# Check if invariant holds for the updated i and a
preservation_solver.add(Not(substitute(inv, (i, new_i), (a, new_a))))
print("Preservation check:", preservation_solver.check())
# "unsat" means the invariant can't be broken by an iteration

# 3. Verify that termination gives us our desired property
termination_solver = Solver()
# Loop terminates when i=10, and invariant still holds
termination_solver.add(inv)
termination_solver.add(i == 10)
# Our desired end state: all elements a[0] to a[9] are 0
desired = ForAll(k, Implies(And(0 <= k, k < 10), a[k] == 0))
termination_solver.add(Not(desired))
print("Termination property check:", termination_solver.check())
# "unsat" means our desired property is guaranteed

Step 3: Interpret the Results #

When you run this code, all three checks should return unsat. That's exactly what we want! It means Z3 couldn't find any counterexamples to our claims—so our invariant is valid, and we've proven the loop behaves as expected.

Let's break down each result:

• Initial condition: There's no way for i=0 to violate the invariant (the "for all k < 0" condition is vacuously true, since there are no such k).
• Preservation: If the invariant holds before an iteration and i<10, it must hold after setting a[i] to 0 and incrementing i.
• Termination: When i=10 and the invariant holds, every element a[0] to a[9] must be 0—exactly what we set out to prove!

Key Takeaways for Beginners #

• Loop invariants are the bridge between loop execution and your desired end state—spend time refining them for your specific problem.
• Z3 works by hunting for counterexamples; if it can't find any (unsat), your claim is mathematically valid.
• Start with small, simple loops like this before tackling more complex code—this builds intuition for how invariants and Z3 work together.

内容的提问来源于stack exchange，提问作者user9182793