<- Back
Comments (30)
- johnbender> This allows us to (1) elide modelling the semantics of the high level programming language, we can instead model the semantics of the machine--presumably simpler semanticsISAs 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.
- mjb> For any first-order universally quantified property of a program we can write as a property-based test, I think we will be able to generate proofs at the binary level, against architecture models that have themselves been validated by millions of hours of testing. The challenge of extending this to multi-threaded programs, distributed systems, [..] will be years more of work we must conduct across thousands of verification engineers and researchers.I expect the distributed and concurrent version of this will come more quickly. In fact, I would be willing to bet that by EOY 2030 the bar mentioned here of single threaded software will be met for multi-threaded and distributed systems under non-adversarial failure modes. This is significantly more aggressive than most in the field (and I'm field-adjacent at best), but given the rate of progress I think it's actually a rather conservative bet (the really aggressive bet would be "July 2027").> The more "bouba" a piece of software or a given layer is, the harder it is to talk about what makes it correct. We can always talk about some correct attributes, but to talk about a uniform notion of correctness is not possible in my opinion.I largely agree with this, although I do think we're going to see more progress than expected in quantifying (and therefore verifying) usability and "look and feel" aspects of software. The risk is that this happens in a "narrow" way that forces all 'correct' software to look and feel the same, 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.
- Mikhail_EdoshinAssuming 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.
- skybrianWhen there's a language specification and everyone agrees to use it, it means that "should this code compile" has a clear meaning and so does "compiler bug."Perhaps having common packages containing shared specifications for other desirable properties will be the way to go? From the user's point of view, the tool should act like a linter.Where will trust come from? For a popular software project, it's from having a trusted team to maintain it and lots of people (and bots) watching them. The result would be that someone can use the linter without needing to verify much themselves.And sure, you should be able to write and prove your own, custom properties too, but hopefully it will build on shared definitions.
- Taikonerd> A great example of this is the recent "binary verification" approach, where instead of proving facts about the programs themselves, we prove facts about the compiled binaries of those programs.This is an interesting argument; I can see pros and cons here.I'm not a formal-methods guy, but I'd imagine the reason that you might want to prove facts about the programs themselves is that they encode higher-level information "for free" -- such as, this function returns a Person.IIRC, there was research into special compilers that would produce TAL: Typed Assembly Language. The idea was that TAL could carry annotations that would be helpful to provers.
- cmrx64Mechanizing 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
- nanolithProofs 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.
- ky3> 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...
- ray2exFrom 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.
- alpaylanAuthor here, happy to chime in!
- antonvsSurely 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.
- jdw64Where does the verification spiral end? I sometimes wonder about that.
- NooneAtAll5once again the title does not represent the contentit'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" questionwhat'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[flagged]
- anonundefined
- emscb[dead]