Formal Verification Is Not Verifiable (alperenkeles.com)

83 points by zdw 3 days ago

23 comments:

by cmrx64 22 minutes ago

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

by mjb 4 hours ago

> 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.

by tcoff91 4 hours ago

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

by Fripplebubby 2 hours ago

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

by skybrian 3 hours ago

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.

by Taikonerd 4 hours ago

> 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.

by alpaylan 2 hours ago

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.

by nanolith 3 hours ago

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.

by mjb 2 hours ago

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.

by nanolith 40 minutes ago

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.

by erichocean 17 minutes ago

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.

by nanolith 4 minutes ago

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.

by ky3 5 hours ago

> 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...

by sirclueless 2 hours ago

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.

by ky3 22 minutes ago

> 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

by alpaylan 2 hours ago

EWD strikes again, beautifully put as always

by ray2ex an hour ago

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.

by alpaylan 4 hours ago

Author here, happy to chime in!

by mjb 2 hours ago

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 :)

by alpaylan 2 hours ago

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)

by erichocean 4 minutes ago

> 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?

We can do this today, what a weird thing to bet on.

by NooneAtAll5 2 hours ago

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?

by alpaylan 2 hours ago

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.

Data from: Hacker News, provided by Hacker News (unofficial) API