Proofs are useful insofar as the formal specification is sound. The problem is that building a sound formal specification is the hard part, and it's not something that LLMs are going to be particularly good at. Yes, they can write a formal specification. But, is this formal specification sound? Is it usable? Is it applicable? Is it complete? This all requires human level reasoning and perhaps beyond to verify.
Once you have a sound formal specification, building proofs that software follows this specification is actually fairly straightforward. LLMs aren't doing any magic here.
In my experience, LLMs are surprisingly good at it. Especially transforming user-visible promises (like "all transactions are replicated to three nodes before being acknowledged") into high-quality specifications. I'm not entirely clear on what it means, specifically, for this transformation to be sound or unsound. What definition do you have in mind?
What have you tried that isn't working?
Completeness is harder, for sure. Maybe not tractable, especially in context of the whole universe (which is a point OP makes). Applicability is pretty easy - it's a NLU problem, and we're pretty good at those so far.
I can give a real-life example. WPA2 was formally verified at the protocol level, but the formal specification -- while reviewed by multiple humans -- was flawed, which directly led to the KRACK attack.
The Needham-Schroeder Public-Key Protocol failed to include the responder's identity in the protocol, which led to a man-in-the middle attack found via model checking. This is despite numerous proofs -- some even machine-checked -- of implementations against specification.
When cryptocurrencies had their formal methods moment a few years ago, there were numerous vulnerabilities and attacks found in cryptocurrency protocols despite claims of being formally verified, and despite much of this verification being published in Rocq, Lean, etc. If the specifications are unsound or flawed, then the implementations will also be. While in these cases, it's quite clear that the folks performing the formal methods work were likely inexperienced, I don't see how an LLM will create anything more sound.
Remember that an LLM is trained on publicly available information. It's not going to make a leap above and beyond what has been published openly, and much of what has been published with respect to security is related to student projects (e.g. "Let's build a formally verified AES implementation") or one-off applications, some of which, like WPA2 KRACK, have incomplete specifications.
This is a difficult problem that experienced proof engineers get wrong, after performing rounds of threat modeling and review.
It's not just a matter of competence: it's a matter of knowledge, experience, and tenacity. Currently, frontier model companies are trying to tackle the problem of their models writing potentially unsafe software by demonstrating that their models can build formal proofs. However, someone who lacks formal verification experience, the domain knowledge to make such software safe, or the understanding to combine the two into formal specifications will build bad proofs, because the formal specifications will be unsound. LLMs don't necessarily improve this outcome. An inexperienced engineer, with or without LLM assistance, is just as likely to not add a property to verify that nonces aren't re-used as the WiFi Alliance.
WPA2 wasn't designed by a single individual. It was designed by a committee of people including respected cryptographers and information security folks. They missed the fact that nonces could be re-used in the design, and they trusted the formal specifications that lacked a check on nonce re-use. It happens. Unfortunately, formal specifications tend to trap folks into a sense of complacency. Soundness is a hard problem, and if it's not solved, folks will make bad assumptions. "But, it's been formally verified..."
Could LLMs accelerate tactics and Curry-Howard level hole filling of specifications? Absolutely. But, they aren't likely to do much better than humans at building sound specifications. This is a difficult problem, for experienced humans with a narrow specialization in formal methods.
In this case a reasonable conclusion would be that there are no sufficiently competent people and we should act on that basis. Or, at least, that we have no reliable way of marrying sufficient competence with the right problems.
I think OP is referring to more of a fundamental problem that a spec has to be written down, and if it's not then AI is just guessing. Often it makes very good guesses, but it can fundamentally never solve the problem of producing a complete specification when the user hasn't got a "complete" picture in their mind.
In my own practical experience this is now what software development is about. If you can specify what you want, AI can implement it. But specifying it is actually very time consuming and hard.
In a sense every prompt you send to an LLM is a specification. And its tedious to write all those prompts, I feel. You have to be very precise, and also write it all into the prompt. And even then answers I get from the LLM are often lacking so I have to prompt again, and then often the LLM replies that it now agrees its previous answer indeed was wrong or inapplicable.
One obvious issue is that an LLM can claim it has formally verified your spec, only for careful inspection to reveal that the spec was subtly changed in some way during translation. Meanwhile the LLM continues to claim it implemented the spec exactly, then pulls a "you're absolutely right and here's why" when you point out the issue.
I think everyone who has used LLMs for coding will have run into this at some point, so it's not very convincing that LLMs are good at this sort of thing.
We have the case of the paper version of OpenAI's Navier-Stokes work turning out to be describing something slightly different from the Lean formalization, as a more public example.
> 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, because that sameness correlates with the learned definition of 'correct'.
> 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.
Love the idea of quantifying/verifying usability - maybe it isn't one thing but it's like an envelope, a 2d (or many-d) region, since we recoil at there being just one correct solution to what feels subjective and range-y
I'm nobody when it comes to formal verification, but I believe there are a lot of simplifications to be made if you have additional assumptions about your system, e.g. information can't be extracted through side channels, or that proxy you use is airtight, or that operating system your systems is designed to run on schedules the tasks correctly. All of these things might not be true, but assuming they're not true is a PITA (and only present under adversarial situations) and leads to a question why don't we completely verify what's underneath first, which is reasonable but not cost-effective.
> 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.
> 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 after all) but it helps to build evidence that we have the theorems and semantic design right. More generally differential testing of this sort offers a possible way forward to build evidence in favor of theorem statements beyond expert examination.
> 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.
Anyone that seriously participates in this work practices this. The whole community. More importantly this is precisely the point of writing down a theorem so that we can closely examine the assumptions. To abuse the CompCert example yet further it's now entirely possible to draw the envelope of assumptions, which are many for a non-toy compiler: https://arxiv.org/html/2201.10280v2.
Last note, I like the kiki bouba diagram if only because it evinces the problematic "round cow" assumption and how that doesn't pan out for real software.
Almost all of the ISA modeling I have seen is done on Arm where there is a published model, or occasionally Risc-V. No one seems to formally model x86!
> 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.
Exactly. Binary verification can often struggle with problems that are completely trivial when looking at the source code. For example "where can this indirect JMP jump to?" requires full-program analysis and may worst-case require solving the halting problem, but "what code can execute when I invoke this trait function?" is easy.
As far as I understand, the binary-level verification lifts high level specifications to simpler binary-level specifications. For instance, imagine a simple property:
```rust
fn prop(a: X, b: X) -> bool {
a == b
}
```
You prove that the compiled `prop` function will always return `bool`, which might be that a particular register gets written `1` after every call to `prop`. Maybe TAL would allow for more complex properties to be written at the binary level instead of doing this trick.
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.
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.
This is exactly what I've been focused on. I think Lean is one of the few, maybe only programming language expressive and powerful enough to do it effectively
Absolute best-case scenario you've just reinvented the compiler, because in practice any sufficiently-detailed specification is going to look an awful lot like programming. Any kind of high-level plaintext "the program should not crash or get in an infinite loop" or "make the design pop" isn't going to work, after all.
Even if it does work, a specification will never catch every detail. Any undergrad can come up with a formal specification for a sorting algorithm and prove that some simple ones follow it. But while both a worst-case O(n log n) Timsort and a best-case O(n^2) Selection Sort might technically be guaranteed to sort your data, the two are definitely not interchangeable!
What I mean us that. Let's take the GCD algorithm. We do need to construct it in such a way that we are sure we get the GCD of two numbers. Whether the algorithm also stops after a finite number of steps is a part of the main construction. There is no need for two specs.
And there is no way to verify the main spec because how do you describe the GCD part? Maybe the idea of a generic verifier of finiteness looks appealling as a common task, a subroutine: here is the specific GCD part and we check finiteness with a standart checker. But it goes against the very fabric of programming, because in programming we sort of reuse logical checks, use interdependencies between variables a generic routine won't know about.
Mechanizing the metatheory and being aggressive about systems modeling can produce refinement cascades reaching more deeply than ever thought possible and (verified!) approximations straight down to physics really can do crazy things (a la Lanyon). And even selfediting verifiers/reflective verified theorem provers a la https://github.com/emberian/svenvs (which combines hol-reflection and candle). Formal representations with of engineering and scientific processes is almost completely unexplored.
\forall Adv in a game based proof starts ranging over metrologically validated manfucaturing processes
"... [B]egin with cleaning up our language by no longer calling a bug a bug but by calling it an error. It is much more honest because it squarely puts the blame where it belongs, viz. with the programmer who made the error. The animistic metaphor of the bug that maliciously sneaked in while the programmer was not looking is intellectually dishonest as it disguises that the error is the programmer's own creation."
EWD 1036: On the cruelty of really teaching computing science [0]
> [That it is normal to have bugs] 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.
To which Dijkstra has this to say about the source of the complexity:
"Many software projects carried out in the past have been overly complex and, consequently, full of bugs and patches. Mainly the following two circumstances have been responsible for this:
1. dramatical increase of processor speeds and memory sizes, which made it seem as if the sky were the limit; only after the creation of a number of disastrously complicated systems it dawned upon us, that our limited thinking ability was the bottleneck;
2. a world that in its desire to apply those wonderful new machines became over-ambitious; many programmers have yielded to the pressure to stretch their available programming technology beyond its limits; this was not a very scientific behaviour, but perhaps stepping beyond the limit was necessary for discovering that limit's position."
EWD 648: "Why is software so expensive?" An explanation to the hardware designer. [1]
I hazard a third: a receiving population geewhized and subsequently hoodwinked into accepting low standards as an inevitable trade-off for all the societal benevolence that software has wrought.
I disagree with EWD, I find the distinction between a "bug" and an "error" helpful. In any robustly engineered system, existence of a bug means that multiple errors have been made by multiple people. Singling out "the programmer who made the error" is not only unhelpful, it's misleading and disingenuous to even try.
If I write an Outlook networking server that handles 100k req/s, and it fails in production when someone points 200k req/s at it, there is a bug. Whose error is it? Is it my fault for writing a component that only handles 100k req/s? Is it the code-reviewer who didn't catch that it only handles 100k req/s? Is it the team lead who told the programmer it needed to handle 100k req/s? Is it the project manager who assigned this task to a junior engineer who can't be trusted to know that the system might need to handle more than 100k req/s? Is it the business leaders who laid off everyone who knew it would need to handle way more than 100k req/s? Is it the engineers who wrote load tests that didn't reach 200k req/s? Is it the operations team that configured this in a way where it can get 200k req/s?
In reality any one of these people could have made a decision that avoided this bug. There are always many errors on the critical path of a bug, identifying "the root cause" means you have already made a leap in logic and concluded which issue(s) you are planning on addressing and which you have decided are not worth tackling.
> In any robustly engineered system, existence of a bug means that multiple errors have been made by multiple people.
You don't find it at all odd to claim a "robustly engineered system" but then also find "multiple errors" in it? Or perhaps by "robustly" you mean a great deal of resources was thrown at it?
Forgive me, for I fall short of Dijkstra's advice here: "A programmer that talks sloppily is just a disaster. Excellent mastery of his native tongue is my first selection criterion for a prospective programmer; good taste in mathematics is the second important criterion." [0]
Back to reading the dictionary for me.
> If I write an Outlook networking server that handles 100k req/s, and it fails in production when someone points 200k req/s at it, there is a bug.
You're right: If there's no standard of correctness, then there are no errors. Ex falso quodlibet.
What do you think of Hoare / Dijkstra's approach of having pre and post conditions for every piece of code? It seems like the kind of structure that allows to talk about properties of code in a intelligible way (the classical example being a sort function with pre-condition 'a list' and post-condition 'the same list but sorted').
If you have dependent types then that approach is essentially the strongly typed version, and I think you're proposing a more gradually typed alternative?
Thank you for engaging with it sincerely! I’m not very convicted on my bet, but what do you say to pick a specific target (say SQLite?), and I claim that by July 2027 we still won’t be able to take a Rigger property (say NoRec), and prove that it holds for every single database and query in a single threaded context? (Maybe 500$ to the charity of other side’s choice, I’m not sure how this stuff works so feel free to correct me)
From an app developer’s perspective, using formal verification for the software we build sounds like sci-fi. Not only are there tons of billions of use cases to handle, but the requirements and user stories themselves are rarely solid: quite the opposite, they are usually vague and volatile. PMs often don't know exactly what they want, so they just monitor metrics and come up with a new *great* idea day to day. With that situation, you have no choice but to accept that degree of uncertainty.
However, I believe formal verification could have progress by letting agents finally be able to design&build production systems. Many of these systems are fairly boilerplate, mixture of pre-existing features. And for those tasks, what agents really need is the ability to test their designs with realtime feedback and refine their implementation in a loop, and finally produce usable product.
It is true that PMs/Customer/User often don't know exactly what they want. The real value of formal validation is just to chase them getting to know what whey want or what is not whey want before the system compiled or pushed to product.
My prediction is that formal verification will add zero value to most software projects. Even if we could generate infinite lines of formal proofs at zero cost, it would still add almost no value to most projects and those projects would still have bugs; but the bugs would be in the spec itself; which, in its most detailed form, would be extremely complex for the vast majority of projects.
In the worst case, formal verification just gives AI agents extra unnecessary work which pollutes their context and biases them towards unnecessarily complex architectures. So it could even end up causing more harm than good.
Some people want to take the real world and make it into something fully predictable and immutable. That's not how reality works. The only constant in our reality, is change.
Nothing changes (Parmenides) and everything changes (Heraclitus) are just points of view. When they are useful, we use one or the other.
Formalizing some aspects of a program has a lot of advantages, and some limitations. Your argument could be used against science, reducing speech to characters on a page, or any other number of very useful things.
> In the worst case, formal verification just gives AI agents extra unnecessary work which pollutes their context and biases them towards unnecessarily complex architectures.
It could, everything is possible. But in general formal verification gives ai deterministic checks that cost "nothing" (they run as deterministic programs). If one thing ai likes is an external oracle to guide it.
In summary, formal verification is not perfect, but it is a big improvement.
Surely it's "formal verification is not formally verifiable." It's verifiable in the scientific sense, of e.g. trying to falsify it, and continuing to fail to do so improves confidence in the result.
Formal verification gets you closer to that confidence. Whether it's worth the effort varies case-by-case, but there are cases where it's quite valuable.
I'd take the most radical perspective here and say that it never ends.
People point out verification has been laborious to date because humans have to write all the proof and LLMs can write it instead.
But the bigger reason IMO is that verification right now is the equivalent of writing Rust applications with no crates besides stdlib
We're only going to get more and more lemmas as building blocks, CSlib is doing what Mathlib did for CS foundations like algos and data structures. I think there are many more opportunities to make building blocks and modules for formalism and have been working on a framework for formal spec with the intent of being able to encompass a much larger breadth of software within an algebraic model by default instead of hand-verifying from scratch
I think you're possibly mixing the Church-Turing Thesis (anything effectively computable is computable by a Turing machine) with the Halting Problem (deciding whether an arbitrary program finishes is undecidable), and maybe also with Gödel's Second Incompleteness Theorem (a consistent formal system cannot prove its own consistency).
Checking a proof certificate is decidable and formal verification can be used to shrink a large trusted compute base (e.g. millions of lines of application-specific code), down to a much smaller one (e.g. thousands of lines of a given heavily re-used proof kernel).
once again the title does not represent the content
it's fine to talk about what properties of programs are verifiable or not, how ai makes it easier and things like that - but I came in looking for "who verifies the verifier" question
what's the simplest verifier out there? is there trust bootstrap process, at least in theory? what's the minimal seed we have to trust?
> 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.
Proofs are useful insofar as the formal specification is sound. The problem is that building a sound formal specification is the hard part, and it's not something that LLMs are going to be particularly good at. Yes, they can write a formal specification. But, is this formal specification sound? Is it usable? Is it applicable? Is it complete? This all requires human level reasoning and perhaps beyond to verify.
Once you have a sound formal specification, building proofs that software follows this specification is actually fairly straightforward. LLMs aren't doing any magic here.
In my experience, LLMs are surprisingly good at it. Especially transforming user-visible promises (like "all transactions are replicated to three nodes before being acknowledged") into high-quality specifications. I'm not entirely clear on what it means, specifically, for this transformation to be sound or unsound. What definition do you have in mind?
What have you tried that isn't working?
Completeness is harder, for sure. Maybe not tractable, especially in context of the whole universe (which is a point OP makes). Applicability is pretty easy - it's a NLU problem, and we're pretty good at those so far.
I can give a real-life example. WPA2 was formally verified at the protocol level, but the formal specification -- while reviewed by multiple humans -- was flawed, which directly led to the KRACK attack.
The Needham-Schroeder Public-Key Protocol failed to include the responder's identity in the protocol, which led to a man-in-the middle attack found via model checking. This is despite numerous proofs -- some even machine-checked -- of implementations against specification.
When cryptocurrencies had their formal methods moment a few years ago, there were numerous vulnerabilities and attacks found in cryptocurrency protocols despite claims of being formally verified, and despite much of this verification being published in Rocq, Lean, etc. If the specifications are unsound or flawed, then the implementations will also be. While in these cases, it's quite clear that the folks performing the formal methods work were likely inexperienced, I don't see how an LLM will create anything more sound.
Remember that an LLM is trained on publicly available information. It's not going to make a leap above and beyond what has been published openly, and much of what has been published with respect to security is related to student projects (e.g. "Let's build a formally verified AES implementation") or one-off applications, some of which, like WPA2 KRACK, have incomplete specifications.
This is a difficult problem that experienced proof engineers get wrong, after performing rounds of threat modeling and review.
KRACK relies on nonce reuse, which as the word "nonce" implies, is something that you must not do.
Any formal specification that doesn't include the invariant about a nonce not being reused isn't worth anything at all.
So yes, incompetent people can design insecure specs that fail to state even the most basic security properties we know of.
It's not just a matter of competence: it's a matter of knowledge, experience, and tenacity. Currently, frontier model companies are trying to tackle the problem of their models writing potentially unsafe software by demonstrating that their models can build formal proofs. However, someone who lacks formal verification experience, the domain knowledge to make such software safe, or the understanding to combine the two into formal specifications will build bad proofs, because the formal specifications will be unsound. LLMs don't necessarily improve this outcome. An inexperienced engineer, with or without LLM assistance, is just as likely to not add a property to verify that nonces aren't re-used as the WiFi Alliance.
WPA2 wasn't designed by a single individual. It was designed by a committee of people including respected cryptographers and information security folks. They missed the fact that nonces could be re-used in the design, and they trusted the formal specifications that lacked a check on nonce re-use. It happens. Unfortunately, formal specifications tend to trap folks into a sense of complacency. Soundness is a hard problem, and if it's not solved, folks will make bad assumptions. "But, it's been formally verified..."
Could LLMs accelerate tactics and Curry-Howard level hole filling of specifications? Absolutely. But, they aren't likely to do much better than humans at building sound specifications. This is a difficult problem, for experienced humans with a narrow specialization in formal methods.
Do you foresee AIs (not necessarily of the LLM kind) getting smarter enough to build proper proofs?
In this case a reasonable conclusion would be that there are no sufficiently competent people and we should act on that basis. Or, at least, that we have no reliable way of marrying sufficient competence with the right problems.
> there are no sufficiently competent people
The common countermeasure to omissions and mistakes is a social measure: we bring talented people together to work as a team.
Even doing so, failures happen. Wise people know the value of testing.
I regret to inform you that the word nonce implies something else entirely in the UK
I think OP is referring to more of a fundamental problem that a spec has to be written down, and if it's not then AI is just guessing. Often it makes very good guesses, but it can fundamentally never solve the problem of producing a complete specification when the user hasn't got a "complete" picture in their mind.
In my own practical experience this is now what software development is about. If you can specify what you want, AI can implement it. But specifying it is actually very time consuming and hard.
In a sense every prompt you send to an LLM is a specification. And its tedious to write all those prompts, I feel. You have to be very precise, and also write it all into the prompt. And even then answers I get from the LLM are often lacking so I have to prompt again, and then often the LLM replies that it now agrees its previous answer indeed was wrong or inapplicable.
I agree, but that's the job now.
One obvious issue is that an LLM can claim it has formally verified your spec, only for careful inspection to reveal that the spec was subtly changed in some way during translation. Meanwhile the LLM continues to claim it implemented the spec exactly, then pulls a "you're absolutely right and here's why" when you point out the issue.
I think everyone who has used LLMs for coding will have run into this at some point, so it's not very convincing that LLMs are good at this sort of thing.
We have the case of the paper version of OpenAI's Navier-Stokes work turning out to be describing something slightly different from the Lean formalization, as a more public example.
> 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, because that sameness correlates with the learned definition of 'correct'.
> 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.
Strongly agree with this.
There's a pretty interesting product i've wanted to try that combines fuzzing with a deterministic simulation testing: https://antithesis.com/
unfortunately, they don't have any tier suitable for solo devs
Love the idea of quantifying/verifying usability - maybe it isn't one thing but it's like an envelope, a 2d (or many-d) region, since we recoil at there being just one correct solution to what feels subjective and range-y
> under non-adversarial failure modes
There's no distinction to be made if the software is verified. If it fails under adversarial situations, it has failed verification.
I'm nobody when it comes to formal verification, but I believe there are a lot of simplifications to be made if you have additional assumptions about your system, e.g. information can't be extracted through side channels, or that proxy you use is airtight, or that operating system your systems is designed to run on schedules the tasks correctly. All of these things might not be true, but assuming they're not true is a PITA (and only present under adversarial situations) and leads to a question why don't we completely verify what's underneath first, which is reasonable but not cost-effective.
> 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 after all) but it helps to build evidence that we have the theorems and semantic design right. More generally differential testing of this sort offers a possible way forward to build evidence in favor of theorem statements beyond expert examination.
> 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.
Anyone that seriously participates in this work practices this. The whole community. More importantly this is precisely the point of writing down a theorem so that we can closely examine the assumptions. To abuse the CompCert example yet further it's now entirely possible to draw the envelope of assumptions, which are many for a non-toy compiler: https://arxiv.org/html/2201.10280v2.
Last note, I like the kiki bouba diagram if only because it evinces the problematic "round cow" assumption and how that doesn't pan out for real software.
Almost all of the ISA modeling I have seen is done on Arm where there is a published model, or occasionally Risc-V. No one seems to formally model x86!
https://alastairreid.github.io/papers/cav2016_isa_formal.pdf https://www.cl.cam.ac.uk/~pes20/sail/sail-popl2019.pdf
> 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.
Exactly. Binary verification can often struggle with problems that are completely trivial when looking at the source code. For example "where can this indirect JMP jump to?" requires full-program analysis and may worst-case require solving the halting problem, but "what code can execute when I invoke this trait function?" is easy.
As far as I understand, the binary-level verification lifts high level specifications to simpler binary-level specifications. For instance, imagine a simple property:
```rust fn prop(a: X, b: X) -> bool { a == b } ```
You prove that the compiled `prop` function will always return `bool`, which might be that a particular register gets written `1` after every call to `prop`. Maybe TAL would allow for more complex properties to be written at the binary level instead of doing this trick.
> > A great example of this is the recent "binary verification" approach
This is not that recent. The sel4 proof uses this, to be able to use a compiler that's not verified
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.
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.
This is exactly what I've been focused on. I think Lean is one of the few, maybe only programming language expressive and powerful enough to do it effectively
That's kinda what modern programming languages are approaching. Rust for example is much closer to a specification then something like COBOL.
Absolute best-case scenario you've just reinvented the compiler, because in practice any sufficiently-detailed specification is going to look an awful lot like programming. Any kind of high-level plaintext "the program should not crash or get in an infinite loop" or "make the design pop" isn't going to work, after all.
Even if it does work, a specification will never catch every detail. Any undergrad can come up with a formal specification for a sorting algorithm and prove that some simple ones follow it. But while both a worst-case O(n log n) Timsort and a best-case O(n^2) Selection Sort might technically be guaranteed to sort your data, the two are definitely not interchangeable!
What I mean us that. Let's take the GCD algorithm. We do need to construct it in such a way that we are sure we get the GCD of two numbers. Whether the algorithm also stops after a finite number of steps is a part of the main construction. There is no need for two specs.
And there is no way to verify the main spec because how do you describe the GCD part? Maybe the idea of a generic verifier of finiteness looks appealling as a common task, a subroutine: here is the specific GCD part and we check finiteness with a standart checker. But it goes against the very fabric of programming, because in programming we sort of reuse logical checks, use interdependencies between variables a generic routine won't know about.
You can verify some things easily, as long as the proof obligations are easy to review.
And you will catch bugs. Completeness of formal verification is much grander task and it's still the technology of the future.
For instance, we just released this yesterday: https://github.com/okcontract/zean
(tried to post here, but wasn't picked up...)
Mechanizing the metatheory and being aggressive about systems modeling can produce refinement cascades reaching more deeply than ever thought possible and (verified!) approximations straight down to physics really can do crazy things (a la Lanyon). And even selfediting verifiers/reflective verified theorem provers a la https://github.com/emberian/svenvs (which combines hol-reflection and candle). Formal representations with of engineering and scientific processes is almost completely unexplored.
\forall Adv in a game based proof starts ranging over metrologically validated manfucaturing processes
> It is normal for software to have bugs!
"... [B]egin with cleaning up our language by no longer calling a bug a bug but by calling it an error. It is much more honest because it squarely puts the blame where it belongs, viz. with the programmer who made the error. The animistic metaphor of the bug that maliciously sneaked in while the programmer was not looking is intellectually dishonest as it disguises that the error is the programmer's own creation."
EWD 1036: On the cruelty of really teaching computing science [0]
> [That it is normal to have bugs] 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.
To which Dijkstra has this to say about the source of the complexity:
"Many software projects carried out in the past have been overly complex and, consequently, full of bugs and patches. Mainly the following two circumstances have been responsible for this:
1. dramatical increase of processor speeds and memory sizes, which made it seem as if the sky were the limit; only after the creation of a number of disastrously complicated systems it dawned upon us, that our limited thinking ability was the bottleneck;
2. a world that in its desire to apply those wonderful new machines became over-ambitious; many programmers have yielded to the pressure to stretch their available programming technology beyond its limits; this was not a very scientific behaviour, but perhaps stepping beyond the limit was necessary for discovering that limit's position."
EWD 648: "Why is software so expensive?" An explanation to the hardware designer. [1]
I hazard a third: a receiving population geewhized and subsequently hoodwinked into accepting low standards as an inevitable trade-off for all the societal benevolence that software has wrought.
[0] https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD103...
[1] https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD648...
I disagree with EWD, I find the distinction between a "bug" and an "error" helpful. In any robustly engineered system, existence of a bug means that multiple errors have been made by multiple people. Singling out "the programmer who made the error" is not only unhelpful, it's misleading and disingenuous to even try.
If I write an Outlook networking server that handles 100k req/s, and it fails in production when someone points 200k req/s at it, there is a bug. Whose error is it? Is it my fault for writing a component that only handles 100k req/s? Is it the code-reviewer who didn't catch that it only handles 100k req/s? Is it the team lead who told the programmer it needed to handle 100k req/s? Is it the project manager who assigned this task to a junior engineer who can't be trusted to know that the system might need to handle more than 100k req/s? Is it the business leaders who laid off everyone who knew it would need to handle way more than 100k req/s? Is it the engineers who wrote load tests that didn't reach 200k req/s? Is it the operations team that configured this in a way where it can get 200k req/s?
In reality any one of these people could have made a decision that avoided this bug. There are always many errors on the critical path of a bug, identifying "the root cause" means you have already made a leap in logic and concluded which issue(s) you are planning on addressing and which you have decided are not worth tackling.
> In any robustly engineered system, existence of a bug means that multiple errors have been made by multiple people.
You don't find it at all odd to claim a "robustly engineered system" but then also find "multiple errors" in it? Or perhaps by "robustly" you mean a great deal of resources was thrown at it?
Forgive me, for I fall short of Dijkstra's advice here: "A programmer that talks sloppily is just a disaster. Excellent mastery of his native tongue is my first selection criterion for a prospective programmer; good taste in mathematics is the second important criterion." [0]
Back to reading the dictionary for me.
> If I write an Outlook networking server that handles 100k req/s, and it fails in production when someone points 200k req/s at it, there is a bug.
You're right: If there's no standard of correctness, then there are no errors. Ex falso quodlibet.
[0] EWD 648
EWD strikes again, beautifully put as always
Author here, happy to chime in!
What do you think of Hoare / Dijkstra's approach of having pre and post conditions for every piece of code? It seems like the kind of structure that allows to talk about properties of code in a intelligible way (the classical example being a sort function with pre-condition 'a list' and post-condition 'the same list but sorted').
If you have dependent types then that approach is essentially the strongly typed version, and I think you're proposing a more gradually typed alternative?
Good article.
If you want to take the other side of my bet about the timeline, I'd be happy to send a check to a charity of your choice :)
Thank you for engaging with it sincerely! I’m not very convicted on my bet, but what do you say to pick a specific target (say SQLite?), and I claim that by July 2027 we still won’t be able to take a Rigger property (say NoRec), and prove that it holds for every single database and query in a single threaded context? (Maybe 500$ to the charity of other side’s choice, I’m not sure how this stuff works so feel free to correct me)
From an app developer’s perspective, using formal verification for the software we build sounds like sci-fi. Not only are there tons of billions of use cases to handle, but the requirements and user stories themselves are rarely solid: quite the opposite, they are usually vague and volatile. PMs often don't know exactly what they want, so they just monitor metrics and come up with a new *great* idea day to day. With that situation, you have no choice but to accept that degree of uncertainty.
However, I believe formal verification could have progress by letting agents finally be able to design&build production systems. Many of these systems are fairly boilerplate, mixture of pre-existing features. And for those tasks, what agents really need is the ability to test their designs with realtime feedback and refine their implementation in a loop, and finally produce usable product.
It is true that PMs/Customer/User often don't know exactly what they want. The real value of formal validation is just to chase them getting to know what whey want or what is not whey want before the system compiled or pushed to product.
My prediction is that formal verification will add zero value to most software projects. Even if we could generate infinite lines of formal proofs at zero cost, it would still add almost no value to most projects and those projects would still have bugs; but the bugs would be in the spec itself; which, in its most detailed form, would be extremely complex for the vast majority of projects.
In the worst case, formal verification just gives AI agents extra unnecessary work which pollutes their context and biases them towards unnecessarily complex architectures. So it could even end up causing more harm than good.
Some people want to take the real world and make it into something fully predictable and immutable. That's not how reality works. The only constant in our reality, is change.
Nothing changes (Parmenides) and everything changes (Heraclitus) are just points of view. When they are useful, we use one or the other.
Formalizing some aspects of a program has a lot of advantages, and some limitations. Your argument could be used against science, reducing speech to characters on a page, or any other number of very useful things.
> In the worst case, formal verification just gives AI agents extra unnecessary work which pollutes their context and biases them towards unnecessarily complex architectures.
It could, everything is possible. But in general formal verification gives ai deterministic checks that cost "nothing" (they run as deterministic programs). If one thing ai likes is an external oracle to guide it.
In summary, formal verification is not perfect, but it is a big improvement.
Surely it's "formal verification is not formally verifiable." It's verifiable in the scientific sense, of e.g. trying to falsify it, and continuing to fail to do so improves confidence in the result.
Formal verification gets you closer to that confidence. Whether it's worth the effort varies case-by-case, but there are cases where it's quite valuable.
Where does the verification spiral end? I sometimes wonder about that.
I'd take the most radical perspective here and say that it never ends.
People point out verification has been laborious to date because humans have to write all the proof and LLMs can write it instead.
But the bigger reason IMO is that verification right now is the equivalent of writing Rust applications with no crates besides stdlib
We're only going to get more and more lemmas as building blocks, CSlib is doing what Mathlib did for CS foundations like algos and data structures. I think there are many more opportunities to make building blocks and modules for formalism and have been working on a framework for formal spec with the intent of being able to encompass a much larger breadth of software within an algebraic model by default instead of hand-verifying from scratch
It can't end. That's the Church - Turing incompleteness result.
I think you're possibly mixing the Church-Turing Thesis (anything effectively computable is computable by a Turing machine) with the Halting Problem (deciding whether an arbitrary program finishes is undecidable), and maybe also with Gödel's Second Incompleteness Theorem (a consistent formal system cannot prove its own consistency).
Checking a proof certificate is decidable and formal verification can be used to shrink a large trusted compute base (e.g. millions of lines of application-specific code), down to a much smaller one (e.g. thousands of lines of a given heavily re-used proof kernel).
once again the title does not represent the content
it's fine to talk about what properties of programs are verifiable or not, how ai makes it easier and things like that - but I came in looking for "who verifies the verifier" question
what's the simplest verifier out there? is there trust bootstrap process, at least in theory? what's the minimal seed we have to trust?
How does the title not represent the content?
> Formal Verification is not Verifiable
from the article:
> 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.