AI Made Formal Verification Mainstream—and That's Exactly Why 'Formally Verified' No Longer Means Bug-Free
Formal Verification Is Not Verifiable
AI has flooded the world with formally verified software, but the label hides a fragile chain of trusted components—models, provers, and definitions—that no one reviews. Drawing on examples like CompCert, seL4, and binary verification, I argue we must abandon the blanket term 'formally verified' and instead specify exactly which properties of which system were proven, under what assumptions.
If AI has 10x'd the volume of software in the world, it has perhaps 1000x'd the volume of "formally verified software" in the world.
- johnbender
> This allows us to (1) elide modelling the semantics of the high level programming language, we can instead model the semantics of the machine--presumably simpler semantics
ISAs are pretty complicated and reasoning about programs in that context is hard which is why we have high level languages.
> This distinction in terminology used to be a colloquially accepted notion, when we heard "CompCert is a formally verified compiler" or "seL4 is a formally verified microkernel" we assumed the authors did not verify vacuous or trivial properties, because the work of verification itself was held to a high standard that highly affected the reputation of the researcher.
CompCert has also had extensive empirical evaluation to vet the theorems. Famously the CSmith paper (https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf) has this rather choice quote:
> As of early 2011, the under-development version of CompCert is the only compiler we have tested for which Csmith cannot find wrong-code errors. This is
not for lack of trying: we have devoted about six CPU-years to the task. The apparent unbreakability of CompCert supports a strong
argument that developing compiler optimizations within a proof framework, where safety checks are explicit and machine-checked,
has tangible benefits for compiler users.
At my work we've extended this to CPU millennia. I hasten to add this of course doesn't rule out the possibility of poorly formed assumptions in the semantics etc (it's empirical aft […]
- mjb
> For any first-order universally quantified property of a program we can write as a property-based test, I think we will be able to generate proofs at the binary level, against architecture models that have themselves been validated by millions of hours of testing. The challenge of extending this to multi-threaded programs, distributed systems, [..] will be years more of work we must conduct across thousands of verification engineers and researchers.
I expect the distributed and concurrent version of this will come more quickly. In fact, I would be willing to bet that by EOY 2030 the bar mentioned here of single threaded software will be met for multi-threaded and distributed systems under non-adversarial failure modes. This is significantly more aggressive than most in the field (and I'm field-adjacent at best), but given the rate of progress I think it's actually a rather conservative bet (the really aggressive bet would be "July 2027").
> The more "bouba" a piece of software or a given layer is, the harder it is to talk about what makes it correct. We can always talk about some correct attributes, but to talk about a uniform notion of correctness is not possible in my opinion.
I largely agree with this, although I do think we're going to see more progress than expected in quantifying (and therefore verifying) usability and "look and feel" aspects of software. The risk is that this happens in a "narrow" way that forces all 'correct' software to look and feel the same, beca […]
- skybrian
When there's a language specification and everyone agrees to use it, it means that "should this code compile" has a clear meaning and so does "compiler bug."
Perhaps having common packages containing shared specifications for other desirable properties will be the way to go? From the user's point of view, the tool should act like a linter.
Where will trust come from? For a popular software project, it's from having a trusted team to maintain it and lots of people (and bots) watching them. The result would be that someone can use the linter without needing to verify much themselves.
And sure, you should be able to write and prove your own, custom properties too, but hopefully it will build on shared definitions.
- Taikonerd
> A great example of this is the recent "binary verification" approach, where instead of proving facts about the programs themselves, we prove facts about the compiled binaries of those programs.
This is an interesting argument; I can see pros and cons here.
I'm not a formal-methods guy, but I'd imagine the reason that you might want to prove facts about the programs themselves is that they encode higher-level information "for free" -- such as, this function returns a Person.
IIRC, there was research into special compilers that would produce TAL: Typed Assembly Language. The idea was that TAL could carry annotations that would be helpful to provers.
- Mikhail_Edoshin
Assuming we can mechanically verify that a program matches a specification our next logical move would be to keep only the specification and generate the program mechanically.
Written code should by itself look like a logical reasoning sufficient for humans to verify the steps.