Formal Verification is Not the Silver Bullet
Written by Crista
Let me walk you through an example that illustrates the title of this blog post.
Sorting
Everyone knows what sorting a sequence of numbers is: take an unsorted input like [7, 2, 10, 12, 3] and produce a sorted output [2, 3, 7, 10, 12]. Every computer scientist knows how to implement a variety of sorting algorithms, from Quick Sort to Bubble Sort. But can you specify the sorting procedure, formally? What exactly do we expect from sorting algorithms? How do we tell that one of them is correct and another is incorrect?
Formal specification, Act 1
Without further ado, let’s give it a first try at a formally specifying the properties that a sorted sequence must have:
predicate Sorted(s: seq<int>) {
forall i, j :: 0 <= i < j < |s| ==> s[i] <= s[j]
}
What this says is that, given a sequence of integers, they are “sorted” when for every pair of slots i, j in the sequence, if 0 <= i < j < length(sequence), then the value at slot i is less or equal to the value of slot j.
Pretty simple, right? It captures the essence of a sorted sequence.
OK, let’s implement a sorting method that complies with this formal specification. Here’s one:
method Sort(a: seq<int>) returns (r: seq<int>)
ensures Sorted(r)
{
r := [];
}
If you run this method through the verifier, it will tell you that it is kosher! Here’s VS Code showing the happy green line on the left:

Yep, the method Sort is formally verified to comply with its formal specification, “Sorted”: the returned sequence r complies with the property that for every pair of slots i, j, if 0 <= i < j < length(sequence), then the value at slot i is less or equal to the value of slot j.
In case you didn’t notice, this method is not sorting anything. It’s returning an empty sequence. So it trivially complies with the Sorted predicate, because there is no pair of slots i, j between 0 and… 0… and the formal specification targets such pairs… that don’t exist here… there’s nothing to prove wrong… we just didn’t say anything about existence of such pairs…
Formal specification, Act 2: Fine, it can’t be empty
But, of course, you’re smarter than that. When asked to formally specify the properties of a sorted sequence, you would immediately think of this trap, and avoid it by stating conditions and properties related to the length of the sequences: they can’t be zero and they need to be the same length. You would think of that, right? RIGHT? The incorrect method will be flagged as such. Here’s the scary red line that proves this method is incorrect (ah!):

Let’s bring the happy green line back by making sure the sorting procedure complies with this new specification:

Wait, what? You give it [7, 2, 10, 12, 3], it returns [1, 1, 1, 1, 1], and the verifier says it’s correct?! What’s going on?!
Well, yeah. The specified properties are met: the returned sequence has the same length as the input one, both non-empty, and for every pair i, j between 0 and the common length, r[i] <= r[j], because they’re all 1.
Formal specification, Act 3: err… ok, same elements
Let’s fix the formal specification. C’mon, the returned sequence needs to have the same elements as the given one! Here’s the scary red line again proving that this is not a sorting method because it doesn’t return the same elements:

OK, let’s fix it again to comply with the new rule:

There’s a lot more going on in this implementation of Sort, but the green line is reassuring. It complies with the specification! Great! It must be a correct sorting method. Let’s give it the sequence [3, 2, 1, 1, 1] as input.
What? [1, 2, 3, 3, 3] ??? What the heck??? It should return [1, 1, 1, 2, 3]. These aren’t the same elements! oh wait… they are the “same” elements; they just repeat differently. What exactly did we say about that? hmm… nothing.
Formal specification, Act 4: This is it, right?
method Sort(a: seq<int>) returns (r: seq<int>)
requires |a| > 0
ensures |r| == |a|
ensures Sorted(r)
ensures multiset(r) == multiset(a) // same elements including multiplicity
Maybe.
Hopefully by now you realized that we’re playing formal spec wack-a-mole, and you feel a bit uneasy about your ability to formally specify what it is to sort a sequence of numbers. How many more sneaky edge cases are there?! In Act 3, you wanted “same elements” and you wrote “forall x :: x in a <==> x in r” but you meant to say something stronger “multiset(r) == multiset(a)”. You just wrote something weaker. At every attempt, the verifier checks that your code matches your spec. It cannot check that your spec matches what you meant.
Now imagine having to formally specify something not as trivial as sorting.
Is It the Right Question?
Even if the formal specification matches 100% what you mean by “sorting”, it may still miss things that matter. Here are a few things that this formal spec misses that may be important:
- Stability. Sorting a sequence of integers is simple; sorting a sequence of objects on a certain key (e.g. [{David, 23}, {Ana, 17}, {Peter, 23}) requires having to deal with more options. For example, you may end up with [{Ana, 17}, {David, 23}, {Peter, 23}] or [{Ana, 17}, {Peter, 23}, {David, 23}]. The meaning of sorting objects on keys may not be exactly the same as the meaning of sorting the keys themselves.
- Complexity. The formal spec says nothing about complexity of the method. An O(n²) sort satisfies the spec as well as an O(n log n) one. This may matter. The usual approach is to pick a cost model (e.g. “count comparisons” or “count loop iterations”), instrument the code to track that cost, and prove a bound on it.
- The model vs. the machine. Dafny’s
intis a mathematical integer. Production code uses 32- or 64-bit integers. The best anecdote here is the binary search midpoint bug:mid = (low + high) / 2overflows for large arrays. This bug was in the JDK’sArrays.binarySearchfor about nine years, and the algorithm came from Bentley’s Programming Pearls, where it was presented with a formal verification. The proof was valid over mathematical integers, but the code didn’t run on mathematical integers. Read Joshua Bloch’s 2006 Google Research blog post, “Nearly All Binary Searches and Mergesorts are Broken,” if you want to hear it from the pro.
This list is not exhaustive, and I don’t know of any methodology to list exhaustive properties that may matter for a given problem. This is even more important: are we asking the right questions?
The AI Announcements
Sidebar: Lean-specific traps
I know Dafny much better than I know Lean (I’m a computer scientist, not a mathematician), so I can’t really make a strong incursion there, but some of its traps are well-known. One of them is the existence of vacuous hypotheses: if a theorem’s assumptions contradict each other, anything follows. Look, Ma, I’m proving the RiemannHypothesis!
theorem amazing (n : ℕ) (h1 : n > 5) (h2 : n < 3) : RiemannHypothesis := by
omega
This says: “For every natural number n, if n > 5 and n < 3, then the Riemann Hypothesis holds.” The theorem prover says: QED. I say: DUH.
Who’s checking the existence of vacuous hypotheses in a 17 million-line proof?
What these announcements really are
When someone says a result “has a Lean proof,” what’s actually guaranteed is narrow but real: the proof correctly establishes the formal statement, relative to Lean’s kernel and whatever axioms were used. This is strong and very cool. What’s not guaranteed:
- The formal statement matches the informal claim. Someone, human or model, translated English mathematics into Lean, and that translation is the Act 3 problem. This — misformalization — is the most important thing to check, and it requires a human who reads Lean. I’m sorry to disappoint, but Claude sometimes lies to you.
- The hypotheses aren’t vacuous and the definitions mean what their names suggest. Just like a definition called
Sortedis just a name until you read its body, a definition calledIsPrimeis just a name until you read its body. Again, I’m sorry, but Claude sometimes lies to you.
Formal verification moves the question from “is this proof correct?” to “does the formal spec say what we mean?“, “are these the right assumptions?” and even “is this the right thing to prove?” These questions are still answered by people. A proof under the wrong formal spec is not the right proof. And a proof under the right spec may still miss something important that wasn’t specified.
While I believe this change of pace is, indeed, a major progress, it is disheartening to see people accepting the results as fait-accomplis without proper human verification.
