形式化验证不可验证
Formal Verification Is Not Verifiable

原始链接: https://alperenkeles.com/posts/formal-verification-is-not-verifiable/

AI 将形式化验证推向主流,提升了其规模与经济价值。但"形式化验证"常被夸大:证明本身容易信任,而其定义、模型与证明器构成一个可能失效的庞大可信基础。相比之下,测试能产生具体、可人工审查的缺陷报告,因此更可验证。二进制验证缩小了这一可信表面,但并未消除。准确的说法是"验证系统的特定属性",而非"已验证的软件"。AI 证明的爆炸性增长使细微差别与警告至关重要。某些软件,尤其是面向用户的"bouba"层,抗拒统一的正确性证明,不过许多属性仍可被证明。作者对二进制层面上的单线程、一阶属性持乐观态度,而多线程、分布式与高阶属性仍然更难。测试与探索仍将是验证模型、建立信任的关键。

Hacker News 新 | 过去 | 评论 | 问 | 展示 | 工作 | 提交 登录 形式化验证不可验证 (alperenkeles.com) 6 点 由 zdw 1 小时前 | 隐藏 | 过去 | 收藏 | 讨论 帮助 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 申请 YC | 联系 搜索:
相关文章

原文

AI is making formal verification go mainstream...

...I wrote in December 2025, well, after the last 12 months I believe it is hard to argue otherwise. AI has made formal verification go mainstream.

Not only did the number of formal verification startups skyrocket, Claude also wrote a billion lines of Rocq for a single verification project, everyone from the creator of Claude Code to the Vercel CEO, lead Codex/Cursor developers is talking about formal verification. The early startups have started to show economic value in software on top of simply producing math proofs: Theorem's binary verification work with Anthropic, Harmonic verifying C programs and hardware designs... With the cybersecurity risk going through the roof, formal verification is not just easier, it is also getting more economically valuable.

The questions people ask now are not "how can we prove X", but rather "what can we prove about X"; or "what is left that we can't prove"? These are good questions to ask, I am writing this post in part to answer them; and in part as a follow-up to last year's post "Test, don't (just) verify". To tease the ending, I am very optimistic about formal verification, but I think people mean lots of different things when they say something is "formally verified", which I will try to break down into the parts I'm optimistic and pessimistic about.

Let's start from the title, I'm what an SF person would call a "verifiability-pilled" person, I've argued for long (well, 2 years) that verifiability was the limit of how much leverage AI can give us; my rough long-term view is that we will build our technology stack around these spikes of verifiable components in our systems. Nowadays, when verifiability is mentioned formal verification very quickly jumps into the discussion. However, somehow, formally verified systems can still have bugs, and when I hear someone has formally verified their systems I am genuinely not filled with a flow of confidence in the correctness of their system. On the other hand, when someone says they found a bug in a system, I am fairly confident that they did so. I argue that this is because testing is verifiable, it produces a well-defined, reviewable, understandable object, a good old bug report. Testing is verifiable (by a HUMAN) as in UI components are verifiable, that's why they're both very easy to use AI with.

Formal verification on the other hand has "verified" components that require no external review, the proofs; and hard to verify components, the definitions themselves, the underlying models of the object we are proving facts about, the provers that are doing the verification. The claim of formal verification is also very strong--formal verification makes forall claims, testing makes exists claims--any mistake in any of the hard-to-verify components might lead to the downfall of the proofs.

There are a few paths to make formal verification more "verifiable", the simplest is to reduce the amount or the size of these trusted components. 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 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--and also drop our reliance on compiler correctness (which really isn't a good idea, compilers have many bugs); (2) avoid modelling semantics of not one, but many high level languages, because source level verification requires you to model every language separately, but at the binary level they all converge to the same model.

This however, in my opinion, solves a small part of the problem. The trusted surface is still huge, you have both the machine semantics and the Linux process semantics in your trusted computing base, both of which need extra validation. More importantly though, talking about "formally verifying X" is still a mistake, the specifically correct term is "formally verifying X properties of Y". 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. It is actually a huge disservice to the scientific method and formal verification community to say we assumed these things, because in reality these works have undergone extensive peer review, people have built other formally verified systems on them, and they had bugs. However, just as AI has shaken up code review in software engineering, it has a similar, even more aggressive effect on proof engineering. 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. This democratization affects our traditional validation strategies in almost every domain, but the more niche a field originally was, the more crucially affected it is due to this change in volume.

It is my opinion that we must as soon as possible abolish the notion of "formally verified software", nuance has to arise. Every discussion of formal verification must come with a list of caveats, a precise understanding of what is trusted, what is proven and what is not. Some of this is already here, new Lean proofs are discussed under the possibility of a kernel soundness bug an LLM could've exploited, comparator is becoming the standard device for validating a new Lean proof, major announcements like Anthropic<>Theorem crash freeness verification as well as Google DeepMind's Signal verification state the limitations of the proof as well as the trusted computing base.

It is also important to develop a conversation around bugs in software with formally verified attributes. It is normal for software to have bugs! This is not an indictment of software engineers but the result of the inherent complexity of software; a complex software system deals with not millions or billions, but trillions of different types of events. Engineers constrain this complexity by building layers of abstractions, capturing complex behavior behind manageable, general patterns of well-tested primitives. However, as these layers come closer to the users, the mathematically well-defined abstractions are harder to create. The easiest way to think about this is to imagine a piece of software like a car, the engine is similar to the database, both well-engineered, both providing a simple interface; the car seat is similar to the user interface, there is no mathematical formula for it, there are general guidelines, there are user demands, there are aesthetic choices, in the end it feels "bouba", compared to the engine or the database which feels more "kiki".

A spiky "kiki" shape labeled the engine and the database, and a rounded "bouba" shape labeled the seat and the user interface, with an arrow from closer to the machine to closer to the user

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. That means to talk about formally verifying bouba software is a hopeless endeavour, and any statements of "formally verifying everything" or "bug-free software" need a huge asterisk next to it.

We can't prove bouba software correct, but we can prove plenty of things about it. For general properties of software we can specify, regardless of whether these facts show up in the inner kiki layers or outer bouba layers, I am very optimistic about proving them. Specifically in the context of single-threaded programs, I think our existing proof frameworks give us the latitude to prove large, real production systems with the help of machine-generated proofs. I had previously made a personal bet that we might solve single-threaded code translation by 2030; I'm now at the stage where I believe we can not only solve translation, but single-threaded program verification as well. 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, higher-order properties, non-functional properties, real deployment settings will be years more of work we must conduct across thousands of verification engineers and researchers.

In solving these challenges, I think random testing and random exploration in general will prove to be invaluable tools. A test execution is a measurement, so it produces information about the real underlying system that we can leverage to falsify, harden and validate the models we use for verification. The verifiability of testing will continue to be a huge driving force of its adoption as well as a gateway into the rest of formal methods, and maybe it will even help us trust when we hear software is "formally verified" instead of wondering what was left out or when someone will find a bug in there.

联系我们 contact @ memedata.com