165 points by zdw 6 days ago | 60 comments | View on ycombinator
mjb 3 days ago |
nanolith 3 days ago |
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.
Taikonerd 3 days ago |
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.
johnbender 3 days ago |
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.
skybrian 3 days ago |
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.
jongjong 3 days ago |
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.
Mikhail_Edoshin 3 days ago |
Written code should by itself look like a logical reasoning sufficient for humans to verify the steps.
cmrx64 3 days ago |
\forall Adv in a game based proof starts ranging over metrologically validated manfucaturing processes
ky3 3 days ago |
"... [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...
alpaylan 3 days ago |
ray2ex 3 days ago |
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.
dboreham 3 days ago |
hbbio 3 days ago |
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...)
antonvs 3 days ago |
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.
bobson381 3 days ago |
jdw64 3 days ago |
NooneAtAll5 3 days ago |
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?
dropdropteam 3 days ago |
undefined 3 days ago |
emscb 3 days ago |
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.