6 ms·

The Case Against Formal Verification, 50 Years Later

95 points by ghuntley 1mo ago

ScribeSEOAI 1mo ago
i am shocked
gr_norm 1mo ago
The title may be slightly misleading if you haven't bothered to read the article. It's responding to a famous paper from 1979 critiquing formal verification. The article ends up disagreeing with most of its strongest claims in hindsight, though a couple appear to remain worthwhile.
bananaflag 1mo ago
> Real-world systems are too messy to be specified I agree with this counterargument. I mean, you can verify that Euclid's algorithm computes the GCD. Or that quicksort produces a sorted version of the input array. But how do you verify Facebook? Facebook computes what? For some programs, the shortest descriptions of what they do are the programs themselves. Edit: I agree with the replies that you can verify individual parts and properties, like with testing.
- IsTom 1mo ago
  Anything with a GUI seems really daunting to specify. And then later you need to update specs to match GUI if you make any changes and you need to decide which is wrong: the implementation of the specification.
  - sincerely 1mo ago
    I’m not even sure what would be gained by formal verification of a GUI
    - IsTom 1mo ago
      Well, to prevent bugs in this layer, I guess? To not have things out-of-date or clickable when they shouldn't be or not have layout suddenly becoming garbled.
  - black_knight 1mo ago
    There are approaches to GUI which are closer to formal specification than what is currently in use. Look at HotDrink for instance: https://tt.utu.fi/soft/hotdrink-gui-programming-with-dataflow-constraint-systems/ https://tt.utu.fi/soft/hotdrink-gui-programming-with-dataflo...
- gr_norm 1mo ago
  Agree in part, but remember that formal verification need not be done in full. By analogy, we don't avoid testing simply because everything under the sun can't be tested. Even simple things like verifying that certain API endpoints are idempotent, or as a few steps up, that the datastores used by Facebook have distributed consistency and fault-tolerance properties, are of enormous utility.
  - ip26 1mo ago
    Exactly, it feels dishonest that this point is so rarely brought up in essays on formal methods. You can do things like prove that all possible faults are always caught, or any memory that is accessed has first been malloc’d, or that the API endpoint will always respond (liveness). These are often both easy to specify and difficult to guarantee with conventional testing.
  - demibabs 1mo ago
    I’m a bit confused as to what makes formal verification different from extensive testing.
    - gr_norm 1mo ago
      To a first approximation, formal verification can guarantee some property holds for every possible run of the program, rather than just the tested ones. It's a lot more powerful than it sounds, because this unlocks the ability to talk about qualities of programs that cannot be tested (effectively or at all). Hyperproperties like confidentiality, integrity, and availability tend to be quite difficult to test, for instance.
    - japgolly 1mo ago
      1) With formal verification you can prove properties about your system. With extensive testing you can also do the same but you need to take care and make sure you cover all possible cases. 2) With formal verification you can easily test things that are normally hard to cover by traditional testing. For example, if you want to test if that a postgres randomly goes offline, you don't lose any data, it's pretty hard to cover with extensive testing, whereas with formal verification you just say "postgres exists, it has state and can be online/offline, it can go online/offline at anytime" and you're covered.
- ocschwar 1mo ago
  > But how do you verify Facebook? Facebook computes what? You start by verifying the permissions structure for Facebook posts. And by verifying the shortest, least complex functions in Facebook's server side code base.
  - AlotOfReading 1mo ago
    The final proof you get from formal methods is often irrelevant in my opinion. Most of the benefit comes from architecting the system so as much as possible can be verified and forcing yourself to make intentional decisions on the edge cases. The results are for other people. I'm not sure you want to create a record of intentional decisions if you're at Facebook though.
- dgacmu 1mo ago
  Facebook runs a number of quite complex internal distributed systems - databases, caches, proxies, etc. all of these are amenable to various forms of formal verification, and verifying them is the kind of thing that helps prevent outages and data loss.
- lysace 1mo ago
  Yes. No Silver Bullet (1986) said that 40 years ago.
  - jm4rc05 1mo ago
    I’ll add that all the glorious specs we wrote last week is can and will be useless tomorrow. No spec survive real life vanity
- brians 1mo ago
  Well. Facebook has invested a fortune in proving that its systems follow expected properties of respecting consent—that all the data flows that happen are permitted. That turns out to be helpful for them in avoiding fines.
- dwohnitmok 1mo ago
  > For some programs, the shortest descriptions of what they do are the programs themselves. There is almost no real-world program for which this is true. One corollary of this would be that it is impossible to refactor the program to be any cleaner, which is not true for basically any large real-world program. Another corollary of this is that no observable aspect of a program could be changed without breaking user expectations, but this too is almost always wrong (e.g. almost always, but not 100% via e.g. the famous xkcd comic about spacebar heating, a global performance optimization would be viewed as good).
mpweiher 1mo ago
"The counterpoint is that specifications are closer to informal requirements than implementations are (and thus a mistake is easier to spot)." I found exactly the opposite to be true when I took formal verification at university, and that was the major point that made formal specification / verification unattractive to me.
- gr_norm 1mo ago
  Part of it may be that you need experience writing formal specifications just as you need experience writing programs; everyone has a lot of the second, but little of the first. They're related skills, but not the same. The first is a much more abstract (but also much more concise and powerful) method of reasoning. This sort of skill hasn't been taught well in CS education yet, owing to the fact that the underlying languages and tools were too niche.
- AgentOrange1234 1mo ago
  I think it very much depends on the domain. For instance, I've seen specs for floating point ops that were 1-3 pages compared to 30,000 lines of RTL. That holds pretty well for many other cases. For example, a properties like decompress(compress(x)) = x are beautifully simple compared to the details of the algorithms, and are pretty compelling correctness evidence.
Animats 1mo ago
I haven't seen the Lipton/Perlis/De Millo paper in years. I was around for that argument. Which really dates me. Those guys were pushing for mutation analysis.[1] That's a test for the test suite - you make some random change to the program and see if the test suite catches it. Fuzzing is related to that concept. It's taken way too long for verification to catch on. Here's where I was almost 50 years ago.[2] Part of the problem is that most of the interest came from people in love with the formalism. The notations used by most researchers were terrible, as is pointed out in the Lipton/Perlis/De Millo paper. You want a notation that matches the programming language. We had the basic architecture back then - use a SAT solver on the easy stuff, and something with some AI capability on the hard stuff. We had the Oppen-Nelson simplifier, the first SAT solver, for the easy stuff. We had the Boyer-Moore prover for the hard stuff. It's Good Old Fashioned AI, and very good for the late 1970s. The SAT solver knocks off over 90% of the verification conditions. Then you want verification notation that creates hard but abstract problems for the AI solver. Like writing two asserts in a row, with the hard problem being to prove the second one from the first. We didn't have enough compute back then. It took about 45 minutes on a VAX 11/780 for the Boyer-Moore prover to build up number theory from something similar to the Peano axioms. Now it takes about a second. I ported the Boyer-Moore prover to GNU Common LISP a few years ago, just to see it live again.[3] With LLMs to do the grunt work, this is a lot less labor-intensive. And it's really needed to keep LLM garbage under control. Given a concrete goal against which to optimize, LLM coding is much more effective. Formal specifications are still hard to write, but there are many important areas of software for which the specification is simple but an efficient implementation is hard. File systems. Databases. Networking. Some kinds of control systems. Stuff that really needs to work right. [1] https://en.wikipedia.org/wiki/Mutation_testing https://en.wikipedia.org/wiki/Mutation_testing [2] https://www.animats.com/papers/verifier/verifiermanual.pdf https://www.animats.com/papers/verifier/verifiermanual.pdf [3] https://github.com/John-Nagle/nqthm https://github.com/John-Nagle/nqthm
- pfdietz 1mo ago
  > We didn't have enough compute back then. The problem here is that more compute also helps testing. So it's not clear verification will pull ahead over just doing more testing, especially if there's any manual part of the verification workflow. The bugs that remain after testing become more and more difficult to stimulate. > That's a test for the test suite - you make some random change to the program and see if the test suite catches it. Fuzzing is related to that concept. Mutation testing is kind of orthogonal to random input testing or fuzzing. In fact, one can use the latter to automatically kill mutants in the former, which is very useful in automatically constructing enhanced test suites. You still need to determine what the correct behavior is for each new test input.
Almondsetat 1mo ago
Everyone knows that the weak link is the specification. But this is a spurious argument, since, by definition, if you guarantee the implementation the only thing that's left exposed is the spec itself. At least you're reducing the attack surface
- amelius 1mo ago
  And you can put the specification in the manual of the software so the user knows what they're dealing with.
  - heikkilevanto 1mo ago
    But can you make a mere user read and understand that specification?
    - amelius 1mo ago
      Not all users are the same and that's OK. Just like not everybody needs to read and verify the Linux kernel. Also note that a specification can be input to other tools, such as a formal verification system for an encompassing system.
amelius 1mo ago
If normal warranty rules applied to software, then software companies would be out of business very quickly. Maybe with formal verification the laws around that can change?
- david-gpu 1mo ago
  Software is buggy when people are more willing to buy the cheaper buggy software vs the higher price of more robust software. When people want more robust software, they pay for it and it is delivered. None of the modern world would work without immense amounts of highly robust software you don't even think about, from your bank, to the airplane you fly on.
  - amelius 1mo ago
    I don't understand what you're trying to say here. If I sell a car that doesn't start half of the time, I can just say "well people pay more for cars that always work, you chose to spend less so you got what you deserved"?
    - ncruces 1mo ago
      They're saying the software that makes the car start was more expensive than the software that allows you to play music in the car.
    - otterley 1mo ago
      For used vehicles, we already have that in practice; when you sell a vehicle “as is,” that’s putting a buyer on notice that that they’re going to bear the risk of future failure. Similarly, when you buy a cooler at Wal-Mart for $25, you know it’s not going to perform the same as a $250 Yeti model.
      - deleted 1mo ago
        [deleted]
- perching_aix 1mo ago
artemonster 1mo ago
The case against it is very simple: fixing your shit in software world is super easy - just release a patch! From a perspective of hardware world where fixing a single bug can cost you up to couple of million - we have for every code producing engineer up to 3 verification engineers that pseudo-randomly fuzz your design against all possible stimuli and collect coverage. Software world wouldnt bother because fixing shit is just so easy. If you regress to shipping golden CDs and next bugfix only via expansion packs - maybe you can get your shit together and start shipping good software again
- artemonster 1mo ago
  and if producing a single CD copy would cost you a fortune then C-Suite business MBA morons would beg (or even mandate) you to use formal verification methods
vkaku 1mo ago
I think that this is a bit of a clickbaity title but the social aspects of verification are real. It's like 80% of the work after raising a PR is just socializing ideas and getting people to agree on stuff
pron 1mo ago
The problem is that the people getting good results with AI-assisted formal methods are the same people who get good results with formal methods without AI assistance. They then extrapolate the benefits they are getting from AI today to what it may do for others in the future, and this is where we get into trouble. There's a lot of art to using formal methods around how to specify the system at the right level of abstraction (to make verification tractable) and how to specify the correctness properties so they can be easily evaluated. Even with AI assistance as it currently exists, users need to know formal methods well enough to at least understand the specification of the system and the correctness properties, which requires ~90% of the effort of learning formal methods in the world before AI. But the real hope is that one day AI will be able to use formal methods correctly on its own, benefitting those who don't know formal methods. AI can sometimes do that today, but sometimes isn't good enough for people who don't know formal methods. It is certainly possible that soon enough AI will be able to do this more reliably, but then we get into the hard problem of speculating the "AI future". It is very hard to predict what an AI that can take over the art of using formal methods cannot do. Predicting that AI will be able to do that yet not be able to collect requirements and build software autonomously, or even come up with the idea for what software to build in the first place, or even replace the software's users seems arbitrary to me. In other words, if people think AI will take care of the verification letting us focus on requirement validation, my question would be, why wouldn't an AI that knows how to verify also know how to validate the requirements? For that matter, why wouldn't it also know how to replace the users altogether?
perching_aix 1mo ago
It reads like not much has changed, and given what the two underlying issues are, that's not surprising. I've been considering getting into formal verification, but the learning curve and the illusions of rigor angle are keeping me away so far. It's great that an agent can now figure out a formal spec on my behalf and check the program it generates on my behalf for compliance, but that doesn't make me any better equipped to keep it all honest end to end. The hard part is gone, remains the hard part. Anecdotally, what I've been doing with agents instead is I made more things declarative. Config, policy, etc. manifests can be linted for syntax and schema compliance, and the logic only has to be written once. The agents can then go ham emitting their silly little JSONs or whatever, the risk is a lot more bounded that way. Just gotta be mindful to not smuggle in too much logic, and not walking the configuration complexity clock too hard, and all remains well. I feel with agents this is now more scalable, but maybe I'll come to think different later.
- nylonstrung 1mo ago
  I don't think issues like syntax and schema compliance are the level of problems where verification comes into play In this case it's more that the underlying declarative systems function as they should across any possible states or configurations You mentioned policy and the policy language Cedar uses Lean formal verification in this way, not to verify that the specific policies users create are sound but to ensure that the declarative policy engine itself cannot produce any invalid or unwanted configurations
_tgxm 1mo ago
Suppose I write a distributed algorithm in Rust. To verify it, I might describe the algorithm again in TLA+, model-check that specification, and prove that it satisfies the properties I care about. Now I have two artifacts: TLA+ specification --> proved Rust implementation --> runtime But the proof establishes something like: TLA_Spec => Safety What I actually need is: Rust_Program => Safety I believe this is called model-code gap and there are ways to address it but I haven't found an easy-to-follow approach.
- david-gpu 1mo ago
  I last touched formal verification methods 20 years ago. Back then, Coq had the capacity to automatically transform your proof into OCaml. I would have expected that this would have only gotten better with time.
  - djsjajah 1mo ago
    It’s been renamed recently. Maybe a few times. I think it’s rocq now. [1] [1] https://rocq-prover.org/docs https://rocq-prover.org/docs
    - Nail2680 1mo ago
      Huh, I missed all of that. The linked discussion about the renaming from your link was a bit odd: https://discourse.rocq-prover.org/t/coq-community-survey-2022-results-part-iv-and-itp-paper-announcement/2001#renaming-coq-8 https://discourse.rocq-prover.org/t/coq-community-survey-202... It seemed to me from the survey that most people didn't want it changed or didn't care, but due to anglophone users they decided to change it anyway.
- black_knight 1mo ago
  I saw a fascinating talk by Clément Pit‑Claudel on closing this gap. I don’t have references handy but his website seems like a starting place: https://pit-claudel.fr/clement/ https://pit-claudel.fr/clement/ As I remember it, he was formalising compilation by connecting the semantics of the higher level to the lower level one inside the proof assistant, so that proofs would carry through.
somat 1mo ago
The question I always have is "why would the formal verification be any more correct than the program it is verifying?", Note: not bugs in the verification engine, but the spec made for the program. It is not a big deal, I think formal verification is a very useful tool to help one approach correctness, but let me explain myself. When a program is written it is trying to solve a problem, when it solves that problem correctly it has no bugs, and when it solves that problem incorrectly those are bugs. For complex problems it turns out to be very difficult(impossible) to solve them correctly. Why is there an assumption that the formal verification spec will be any more correct than the program itself? They are both trying to solve very complex problems. I was trying to get a feel for this by reading through the sel4 git changes trying to figure out how many bug fixes were for the OS and how many were for the spec. No real conclusion unfortunately. because they almost always have to fix both at the same time. a bug found in the OS means you have a bad spec and a bug found in the spec means your OS probably has a bug.
- pfdietz 1mo ago
  Empirically, we can look at something like CompCert, which formally verified a substantial section of a C compiler. Subsequent high volume random testing with Csmith found no bugs in the formally verified section (unlike in every other C compiler tested with Csmith). It should be noted that the verification performed was specifically about whether the compiler would produce incorrect code; cases where it would crash or error and not produce code would not be considered errors of verification. This would enable (for example) a coloring register allocator to be adjoined with some code that checked whether the coloring was correct and abort if not.
  - pseudohadamard 1mo ago
    The problem with CompCert is that it produces really bad code, below the level of gcc -O0, about the level of the eternally-in-progress compiler project you worked on in your Programming Languages 370 course. So you can get most of the benefits of CompCert by running a standard compiler with -O0.
    - 29d ago
ibarrajo 1mo ago
I’ve been vibe coding a lot of Lean this year. What i found is that it is amazing once you determine and the invariants that are essential to the guarantees you want to keep. I built my own formally verified workflow engine, it was easy but mostly because i already knew the pitfalls and the foundational pillars of Cadence and Temporal. Also, it doesnt seem like common knowledge, but you can export libraries that compile to C from lean. With them you do get performant code that that has been verified and easily call them as C bindings from elsewhere. Lean itself does not have a good IO stack in general but its good enough for small projects. There is a caveat to exporting libs or native_decide in general. Once you export into C, ABI its now outside of the scope of the Lean kernel which means that bugs can creep in from the compiler itself.
- solomonb 1mo ago
  Did you have previous experience with formal verification and/or dependent types?
- nylonstrung 1mo ago
  I'd love to hear more about your workflow engine, I think the expressiveness of lean and the type system makes it extremely well suited for stuff like that I do agree that the lack of IO and libs in lean isn't really a drawback when there's a very clear interop path already
- sroerick 1mo ago
  I'd love to know more about your experience on this, generally. What have you been doing in Lean? How have you approached this?
- deterministic 28d ago
  Please write an article about this.
deleted 1mo ago
[deleted]
jongjong 1mo ago
Although I will admit that formal verification is looking better now than it ever did, and it's probably easier to generate proofs for those few simple safety-critical systems which benefit from it, I'm still bearish about it for the mainstream case. I agree with "Even if fully automatic verification were within reach, it would be detrimental". Formal verification proofs make the same trade-off as overly fine-grained unit tests; they lock-down the current implementation and thus significantly reduce operational agility; because, if you make a modification to the code, you may have to re-generate the entire proof again. Proofs thus lock down sub-optimal abstractions and implementations. For many kinds of software, requirement changes are a daily occurrence and proofs would get in the way of making the required changes. Even with complete, zero-cost automation of proof-generation, with no prompting or user-intervention (which would require the AI to have internalized a complete, perfect world-model), there would still be an incentive problem; when engineers see a lot of proofs and/or fine-grained unit tests, they are often reluctant to make the necessary refactoring to meet new requirements. Existing (counter-productive, flawed) abstractions become part of the lingo of the team and it becomes literally impossible to move off of them; yet they create a lasting barrier for new team members and when implementing new features. The biggest problem though is that many modern software issues are flaws in the requirements (the spec itself), not in the implementation. The requirements are often produced by business people who often have a vague idea about what they want; requirements usually contain subtle contradictions or conflicts which have to be resolved. Having worked on projects with clean, well architected code, requirements issues are by far the most common issue. On my last project, I kept coming back to my business/product co-founder with questions like: "You said that this checkbox should be on this page; but for a different onboarding flow, you said that it should be impossible for that specific user role to see/select this checkbox and the backend processing relies on this fact for reasons X, Y and Z..." or "You said to apply a filter to the collection and keep narrowing down the set as the user moves through the stages in the flow, but now you want to add a step which expands the set again with data from a different source; so now we can't just update the filter against a single collection; we need to make a separate table to hold the data from different sources; that will require some refactoring and it adds overhead since now we have to keep a lot of data per-user and we need to account for malicious spam-scenarios, etc... We can't just hold all the state in the URL (for bookmark) anymore... Users can't just share filters with each other anymore to restore the same app state across account boundaries." In my last project, most of the work was trying to figure out what my co-founder wanted and it turns out that the idea he had in his head about the system was not logically consistent across all of its parts; a fact we only discovered after months of implementation. Also, he did not understand some of the technical limitations in terms of what kinds of data a free public API would give us access to; and that turned out to have been fundamentally incompatible with business objectives and the target market. His refusal to pivot to a premium market (where the user may have been able and willing to pay to cover the additional downstream API costs) marked the end of the project. The project was logically impossible from the start given the hard constraints of what platform to rely on, what our costs would be and what the target audience was. If we need formal verification, it would have to be for the requirements themselves, evaluated against the technical constraints. We don't need formal verification of the code. Correct code is a mostly solved problem if you break down the typical software system into its sub-parts and identify the right platforms (e.g. CRUD, edge functions, data ingestion, data processing...) Correct requirements are a far bigger problem.
txhwind 1mo ago
With agent asssistance, we don't need writing annoying formal spec and proof anymore. Then formal verification can be a practical and useful tool in daily programming, especially for "deep module" whose spec is much simpler than implementation.
deterministic 28d ago
I was fully prepared to hate this article, given the long list of previous “I have no clue how formal proof tools work, yet have strong opinions about how useless they are” articles. Instead, I was pleasantly surprised by how balanced it was. What convinced me that formally proving software correct is possible were seL4, CompCert, and my own experience proving small projects correct using Lean and Rocq. seL4: The US military and NSA tried to break seL4. They failed. CompCert: Researchers tested CompCert against five leading commercial and open-source C compilers. Every compiler except CompCert had bugs. Not just a few, but hundreds. CompCert had zero. And there are now many more commercial examples of software being formally proven correct. Maybe in the future the difference between being a programmer and being a Software Engineer will be that the software you write is proven correct. That might actually happen with the help of AI.
jochenm 24d ago
I agree that a correctness proof for a complete, large program will always have the problem that the specification itself might be buggy. So integration tests will hardly ever become unnecessary. But as others have already pointed out, even then formal verification of critical parts of a program can be useful. I would like to add that it can also be of great value if one can "only" prove that a program will never trigger undefined behaviour, or cause a runtime error. For C programs, that would, of course, be particularly helpful. But even in safe Rust, there can be (in my understanding, I haven't yet used Rust myself) runtime errors in the form of panics. And if your medical device stops working, because the software attempted an out-of-bounds read or write and was therefore aborted with a panic, that isn't really fun. Better to prove statically that such invalid accesses will never occur. And this is still for safe Rust - not even considering unsafe code. Similar arguments hold for other system-level programming languages, I guess, even if they are considered safer than C or C++.

95 points by ghuntley 1mo ago

i am shocked

The title may be slightly misleading if you haven't bothered to read the article. It's responding to a famous paper from 1979 critiquing formal verification. The article ends up disagreeing with most of its strongest claims in hindsight, though a couple appear to remain worthwhile.

bananaflag 1mo ago

> Real-world systems are too messy to be specified I agree with this counterargument. I mean, you can verify that Euclid's algorithm computes the GCD. Or that quicksort produces a sorted version of the input array. But how do you verify Facebook? Facebook computes what? For some programs, the shortest descriptions of what they do are the programs themselves. Edit: I agree with the replies that you can verify individual parts and properties, like with testing.

IsTom 1mo ago
Anything with a GUI seems really daunting to specify. And then later you need to update specs to match GUI if you make any changes and you need to decide which is wrong: the implementation of the specification.
- sincerely 1mo ago
  I’m not even sure what would be gained by formal verification of a GUI
  - IsTom 1mo ago
    Well, to prevent bugs in this layer, I guess? To not have things out-of-date or clickable when they shouldn't be or not have layout suddenly becoming garbled.
- black_knight 1mo ago
  There are approaches to GUI which are closer to formal specification than what is currently in use. Look at HotDrink for instance: https://tt.utu.fi/soft/hotdrink-gui-programming-with-dataflow-constraint-systems/ https://tt.utu.fi/soft/hotdrink-gui-programming-with-dataflo...
gr_norm 1mo ago
Agree in part, but remember that formal verification need not be done in full. By analogy, we don't avoid testing simply because everything under the sun can't be tested. Even simple things like verifying that certain API endpoints are idempotent, or as a few steps up, that the datastores used by Facebook have distributed consistency and fault-tolerance properties, are of enormous utility.
- ip26 1mo ago
  Exactly, it feels dishonest that this point is so rarely brought up in essays on formal methods. You can do things like prove that all possible faults are always caught, or any memory that is accessed has first been malloc’d, or that the API endpoint will always respond (liveness). These are often both easy to specify and difficult to guarantee with conventional testing.
- demibabs 1mo ago
  I’m a bit confused as to what makes formal verification different from extensive testing.
  - gr_norm 1mo ago
    To a first approximation, formal verification can guarantee some property holds for every possible run of the program, rather than just the tested ones. It's a lot more powerful than it sounds, because this unlocks the ability to talk about qualities of programs that cannot be tested (effectively or at all). Hyperproperties like confidentiality, integrity, and availability tend to be quite difficult to test, for instance.
  - japgolly 1mo ago
    1) With formal verification you can prove properties about your system. With extensive testing you can also do the same but you need to take care and make sure you cover all possible cases. 2) With formal verification you can easily test things that are normally hard to cover by traditional testing. For example, if you want to test if that a postgres randomly goes offline, you don't lose any data, it's pretty hard to cover with extensive testing, whereas with formal verification you just say "postgres exists, it has state and can be online/offline, it can go online/offline at anytime" and you're covered.
ocschwar 1mo ago
> But how do you verify Facebook? Facebook computes what? You start by verifying the permissions structure for Facebook posts. And by verifying the shortest, least complex functions in Facebook's server side code base.
- AlotOfReading 1mo ago
  The final proof you get from formal methods is often irrelevant in my opinion. Most of the benefit comes from architecting the system so as much as possible can be verified and forcing yourself to make intentional decisions on the edge cases. The results are for other people. I'm not sure you want to create a record of intentional decisions if you're at Facebook though.
dgacmu 1mo ago
Facebook runs a number of quite complex internal distributed systems - databases, caches, proxies, etc. all of these are amenable to various forms of formal verification, and verifying them is the kind of thing that helps prevent outages and data loss.
lysace 1mo ago
Yes. No Silver Bullet (1986) said that 40 years ago.
- jm4rc05 1mo ago
  I’ll add that all the glorious specs we wrote last week is can and will be useless tomorrow. No spec survive real life vanity
brians 1mo ago
Well. Facebook has invested a fortune in proving that its systems follow expected properties of respecting consent—that all the data flows that happen are permitted. That turns out to be helpful for them in avoiding fines.
dwohnitmok 1mo ago
> For some programs, the shortest descriptions of what they do are the programs themselves. There is almost no real-world program for which this is true. One corollary of this would be that it is impossible to refactor the program to be any cleaner, which is not true for basically any large real-world program. Another corollary of this is that no observable aspect of a program could be changed without breaking user expectations, but this too is almost always wrong (e.g. almost always, but not 100% via e.g. the famous xkcd comic about spacebar heating, a global performance optimization would be viewed as good).

mpweiher 1mo ago

"The counterpoint is that specifications are closer to informal requirements than implementations are (and thus a mistake is easier to spot)." I found exactly the opposite to be true when I took formal verification at university, and that was the major point that made formal specification / verification unattractive to me.

gr_norm 1mo ago
Part of it may be that you need experience writing formal specifications just as you need experience writing programs; everyone has a lot of the second, but little of the first. They're related skills, but not the same. The first is a much more abstract (but also much more concise and powerful) method of reasoning. This sort of skill hasn't been taught well in CS education yet, owing to the fact that the underlying languages and tools were too niche.
AgentOrange1234 1mo ago
I think it very much depends on the domain. For instance, I've seen specs for floating point ops that were 1-3 pages compared to 30,000 lines of RTL. That holds pretty well for many other cases. For example, a properties like decompress(compress(x)) = x are beautifully simple compared to the details of the algorithms, and are pretty compelling correctness evidence.

Animats 1mo ago

I haven't seen the Lipton/Perlis/De Millo paper in years. I was around for that argument. Which really dates me. Those guys were pushing for mutation analysis.[1] That's a test for the test suite - you make some random change to the program and see if the test suite catches it. Fuzzing is related to that concept. It's taken way too long for verification to catch on. Here's where I was almost 50 years ago.[2] Part of the problem is that most of the interest came from people in love with the formalism. The notations used by most researchers were terrible, as is pointed out in the Lipton/Perlis/De Millo paper. You want a notation that matches the programming language. We had the basic architecture back then - use a SAT solver on the easy stuff, and something with some AI capability on the hard stuff. We had the Oppen-Nelson simplifier, the first SAT solver, for the easy stuff. We had the Boyer-Moore prover for the hard stuff. It's Good Old Fashioned AI, and very good for the late 1970s. The SAT solver knocks off over 90% of the verification conditions. Then you want verification notation that creates hard but abstract problems for the AI solver. Like writing two asserts in a row, with the hard problem being to prove the second one from the first. We didn't have enough compute back then. It took about 45 minutes on a VAX 11/780 for the Boyer-Moore prover to build up number theory from something similar to the Peano axioms. Now it takes about a second. I ported the Boyer-Moore prover to GNU Common LISP a few years ago, just to see it live again.[3] With LLMs to do the grunt work, this is a lot less labor-intensive. And it's really needed to keep LLM garbage under control. Given a concrete goal against which to optimize, LLM coding is much more effective. Formal specifications are still hard to write, but there are many important areas of software for which the specification is simple but an efficient implementation is hard. File systems. Databases. Networking. Some kinds of control systems. Stuff that really needs to work right. [1] https://en.wikipedia.org/wiki/Mutation_testing https://en.wikipedia.org/wiki/Mutation_testing [2] https://www.animats.com/papers/verifier/verifiermanual.pdf https://www.animats.com/papers/verifier/verifiermanual.pdf [3] https://github.com/John-Nagle/nqthm https://github.com/John-Nagle/nqthm

pfdietz 1mo ago
> We didn't have enough compute back then. The problem here is that more compute also helps testing. So it's not clear verification will pull ahead over just doing more testing, especially if there's any manual part of the verification workflow. The bugs that remain after testing become more and more difficult to stimulate. > That's a test for the test suite - you make some random change to the program and see if the test suite catches it. Fuzzing is related to that concept. Mutation testing is kind of orthogonal to random input testing or fuzzing. In fact, one can use the latter to automatically kill mutants in the former, which is very useful in automatically constructing enhanced test suites. You still need to determine what the correct behavior is for each new test input.

Almondsetat 1mo ago

Everyone knows that the weak link is the specification. But this is a spurious argument, since, by definition, if you guarantee the implementation the only thing that's left exposed is the spec itself. At least you're reducing the attack surface

amelius 1mo ago
And you can put the specification in the manual of the software so the user knows what they're dealing with.
- heikkilevanto 1mo ago
  But can you make a mere user read and understand that specification?
  - amelius 1mo ago
    Not all users are the same and that's OK. Just like not everybody needs to read and verify the Linux kernel. Also note that a specification can be input to other tools, such as a formal verification system for an encompassing system.

amelius 1mo ago

If normal warranty rules applied to software, then software companies would be out of business very quickly. Maybe with formal verification the laws around that can change?

david-gpu 1mo ago
Software is buggy when people are more willing to buy the cheaper buggy software vs the higher price of more robust software. When people want more robust software, they pay for it and it is delivered. None of the modern world would work without immense amounts of highly robust software you don't even think about, from your bank, to the airplane you fly on.
- amelius 1mo ago
  I don't understand what you're trying to say here. If I sell a car that doesn't start half of the time, I can just say "well people pay more for cars that always work, you chose to spend less so you got what you deserved"?
  - ncruces 1mo ago
    They're saying the software that makes the car start was more expensive than the software that allows you to play music in the car.
  - otterley 1mo ago
    For used vehicles, we already have that in practice; when you sell a vehicle “as is,” that’s putting a buyer on notice that that they’re going to bear the risk of future failure. Similarly, when you buy a cooler at Wal-Mart for $25, you know it’s not going to perform the same as a $250 Yeti model.
    - deleted 1mo ago
      [deleted]
perching_aix 1mo ago

artemonster 1mo ago

The case against it is very simple: fixing your shit in software world is super easy - just release a patch! From a perspective of hardware world where fixing a single bug can cost you up to couple of million - we have for every code producing engineer up to 3 verification engineers that pseudo-randomly fuzz your design against all possible stimuli and collect coverage. Software world wouldnt bother because fixing shit is just so easy. If you regress to shipping golden CDs and next bugfix only via expansion packs - maybe you can get your shit together and start shipping good software again

artemonster 1mo ago
and if producing a single CD copy would cost you a fortune then C-Suite business MBA morons would beg (or even mandate) you to use formal verification methods

vkaku 1mo ago

I think that this is a bit of a clickbaity title but the social aspects of verification are real. It's like 80% of the work after raising a PR is just socializing ideas and getting people to agree on stuff

pron 1mo ago

The problem is that the people getting good results with AI-assisted formal methods are the same people who get good results with formal methods without AI assistance. They then extrapolate the benefits they are getting from AI today to what it may do for others in the future, and this is where we get into trouble. There's a lot of art to using formal methods around how to specify the system at the right level of abstraction (to make verification tractable) and how to specify the correctness properties so they can be easily evaluated. Even with AI assistance as it currently exists, users need to know formal methods well enough to at least understand the specification of the system and the correctness properties, which requires ~90% of the effort of learning formal methods in the world before AI. But the real hope is that one day AI will be able to use formal methods correctly on its own, benefitting those who don't know formal methods. AI can sometimes do that today, but sometimes isn't good enough for people who don't know formal methods. It is certainly possible that soon enough AI will be able to do this more reliably, but then we get into the hard problem of speculating the "AI future". It is very hard to predict what an AI that can take over the art of using formal methods cannot do. Predicting that AI will be able to do that yet not be able to collect requirements and build software autonomously, or even come up with the idea for what software to build in the first place, or even replace the software's users seems arbitrary to me. In other words, if people think AI will take care of the verification letting us focus on requirement validation, my question would be, why wouldn't an AI that knows how to verify also know how to validate the requirements? For that matter, why wouldn't it also know how to replace the users altogether?

perching_aix 1mo ago

It reads like not much has changed, and given what the two underlying issues are, that's not surprising. I've been considering getting into formal verification, but the learning curve and the illusions of rigor angle are keeping me away so far. It's great that an agent can now figure out a formal spec on my behalf and check the program it generates on my behalf for compliance, but that doesn't make me any better equipped to keep it all honest end to end. The hard part is gone, remains the hard part. Anecdotally, what I've been doing with agents instead is I made more things declarative. Config, policy, etc. manifests can be linted for syntax and schema compliance, and the logic only has to be written once. The agents can then go ham emitting their silly little JSONs or whatever, the risk is a lot more bounded that way. Just gotta be mindful to not smuggle in too much logic, and not walking the configuration complexity clock too hard, and all remains well. I feel with agents this is now more scalable, but maybe I'll come to think different later.

nylonstrung 1mo ago
I don't think issues like syntax and schema compliance are the level of problems where verification comes into play In this case it's more that the underlying declarative systems function as they should across any possible states or configurations You mentioned policy and the policy language Cedar uses Lean formal verification in this way, not to verify that the specific policies users create are sound but to ensure that the declarative policy engine itself cannot produce any invalid or unwanted configurations

_tgxm 1mo ago

Suppose I write a distributed algorithm in Rust. To verify it, I might describe the algorithm again in TLA+, model-check that specification, and prove that it satisfies the properties I care about. Now I have two artifacts: TLA+ specification --> proved Rust implementation --> runtime But the proof establishes something like: TLA_Spec => Safety What I actually need is: Rust_Program => Safety I believe this is called model-code gap and there are ways to address it but I haven't found an easy-to-follow approach.

david-gpu 1mo ago
I last touched formal verification methods 20 years ago. Back then, Coq had the capacity to automatically transform your proof into OCaml. I would have expected that this would have only gotten better with time.
- djsjajah 1mo ago
  It’s been renamed recently. Maybe a few times. I think it’s rocq now. [1] [1] https://rocq-prover.org/docs https://rocq-prover.org/docs
  - Nail2680 1mo ago
    Huh, I missed all of that. The linked discussion about the renaming from your link was a bit odd: https://discourse.rocq-prover.org/t/coq-community-survey-2022-results-part-iv-and-itp-paper-announcement/2001#renaming-coq-8 https://discourse.rocq-prover.org/t/coq-community-survey-202... It seemed to me from the survey that most people didn't want it changed or didn't care, but due to anglophone users they decided to change it anyway.
black_knight 1mo ago
I saw a fascinating talk by Clément Pit‑Claudel on closing this gap. I don’t have references handy but his website seems like a starting place: https://pit-claudel.fr/clement/ https://pit-claudel.fr/clement/ As I remember it, he was formalising compilation by connecting the semantics of the higher level to the lower level one inside the proof assistant, so that proofs would carry through.

somat 1mo ago

The question I always have is "why would the formal verification be any more correct than the program it is verifying?", Note: not bugs in the verification engine, but the spec made for the program. It is not a big deal, I think formal verification is a very useful tool to help one approach correctness, but let me explain myself. When a program is written it is trying to solve a problem, when it solves that problem correctly it has no bugs, and when it solves that problem incorrectly those are bugs. For complex problems it turns out to be very difficult(impossible) to solve them correctly. Why is there an assumption that the formal verification spec will be any more correct than the program itself? They are both trying to solve very complex problems. I was trying to get a feel for this by reading through the sel4 git changes trying to figure out how many bug fixes were for the OS and how many were for the spec. No real conclusion unfortunately. because they almost always have to fix both at the same time. a bug found in the OS means you have a bad spec and a bug found in the spec means your OS probably has a bug.

pfdietz 1mo ago
Empirically, we can look at something like CompCert, which formally verified a substantial section of a C compiler. Subsequent high volume random testing with Csmith found no bugs in the formally verified section (unlike in every other C compiler tested with Csmith). It should be noted that the verification performed was specifically about whether the compiler would produce incorrect code; cases where it would crash or error and not produce code would not be considered errors of verification. This would enable (for example) a coloring register allocator to be adjoined with some code that checked whether the coloring was correct and abort if not.
- pseudohadamard 1mo ago
  The problem with CompCert is that it produces really bad code, below the level of gcc -O0, about the level of the eternally-in-progress compiler project you worked on in your Programming Languages 370 course. So you can get most of the benefits of CompCert by running a standard compiler with -O0.
  - 29d ago

ibarrajo 1mo ago

I’ve been vibe coding a lot of Lean this year. What i found is that it is amazing once you determine and the invariants that are essential to the guarantees you want to keep. I built my own formally verified workflow engine, it was easy but mostly because i already knew the pitfalls and the foundational pillars of Cadence and Temporal. Also, it doesnt seem like common knowledge, but you can export libraries that compile to C from lean. With them you do get performant code that that has been verified and easily call them as C bindings from elsewhere. Lean itself does not have a good IO stack in general but its good enough for small projects. There is a caveat to exporting libs or native_decide in general. Once you export into C, ABI its now outside of the scope of the Lean kernel which means that bugs can creep in from the compiler itself.

solomonb 1mo ago
Did you have previous experience with formal verification and/or dependent types?
nylonstrung 1mo ago
I'd love to hear more about your workflow engine, I think the expressiveness of lean and the type system makes it extremely well suited for stuff like that I do agree that the lack of IO and libs in lean isn't really a drawback when there's a very clear interop path already
sroerick 1mo ago
I'd love to know more about your experience on this, generally. What have you been doing in Lean? How have you approached this?
deterministic 28d ago
Please write an article about this.

deleted 1mo ago

[deleted]

jongjong 1mo ago

Although I will admit that formal verification is looking better now than it ever did, and it's probably easier to generate proofs for those few simple safety-critical systems which benefit from it, I'm still bearish about it for the mainstream case. I agree with "Even if fully automatic verification were within reach, it would be detrimental". Formal verification proofs make the same trade-off as overly fine-grained unit tests; they lock-down the current implementation and thus significantly reduce operational agility; because, if you make a modification to the code, you may have to re-generate the entire proof again. Proofs thus lock down sub-optimal abstractions and implementations. For many kinds of software, requirement changes are a daily occurrence and proofs would get in the way of making the required changes. Even with complete, zero-cost automation of proof-generation, with no prompting or user-intervention (which would require the AI to have internalized a complete, perfect world-model), there would still be an incentive problem; when engineers see a lot of proofs and/or fine-grained unit tests, they are often reluctant to make the necessary refactoring to meet new requirements. Existing (counter-productive, flawed) abstractions become part of the lingo of the team and it becomes literally impossible to move off of them; yet they create a lasting barrier for new team members and when implementing new features. The biggest problem though is that many modern software issues are flaws in the requirements (the spec itself), not in the implementation. The requirements are often produced by business people who often have a vague idea about what they want; requirements usually contain subtle contradictions or conflicts which have to be resolved. Having worked on projects with clean, well architected code, requirements issues are by far the most common issue. On my last project, I kept coming back to my business/product co-founder with questions like: "You said that this checkbox should be on this page; but for a different onboarding flow, you said that it should be impossible for that specific user role to see/select this checkbox and the backend processing relies on this fact for reasons X, Y and Z..." or "You said to apply a filter to the collection and keep narrowing down the set as the user moves through the stages in the flow, but now you want to add a step which expands the set again with data from a different source; so now we can't just update the filter against a single collection; we need to make a separate table to hold the data from different sources; that will require some refactoring and it adds overhead since now we have to keep a lot of data per-user and we need to account for malicious spam-scenarios, etc... We can't just hold all the state in the URL (for bookmark) anymore... Users can't just share filters with each other anymore to restore the same app state across account boundaries." In my last project, most of the work was trying to figure out what my co-founder wanted and it turns out that the idea he had in his head about the system was not logically consistent across all of its parts; a fact we only discovered after months of implementation. Also, he did not understand some of the technical limitations in terms of what kinds of data a free public API would give us access to; and that turned out to have been fundamentally incompatible with business objectives and the target market. His refusal to pivot to a premium market (where the user may have been able and willing to pay to cover the additional downstream API costs) marked the end of the project. The project was logically impossible from the start given the hard constraints of what platform to rely on, what our costs would be and what the target audience was. If we need formal verification, it would have to be for the requirements themselves, evaluated against the technical constraints. We don't need formal verification of the code. Correct code is a mostly solved problem if you break down the typical software system into its sub-parts and identify the right platforms (e.g. CRUD, edge functions, data ingestion, data processing...) Correct requirements are a far bigger problem.

txhwind 1mo ago

With agent asssistance, we don't need writing annoying formal spec and proof anymore. Then formal verification can be a practical and useful tool in daily programming, especially for "deep module" whose spec is much simpler than implementation.

deterministic 28d ago

I was fully prepared to hate this article, given the long list of previous “I have no clue how formal proof tools work, yet have strong opinions about how useless they are” articles. Instead, I was pleasantly surprised by how balanced it was. What convinced me that formally proving software correct is possible were seL4, CompCert, and my own experience proving small projects correct using Lean and Rocq. seL4: The US military and NSA tried to break seL4. They failed. CompCert: Researchers tested CompCert against five leading commercial and open-source C compilers. Every compiler except CompCert had bugs. Not just a few, but hundreds. CompCert had zero. And there are now many more commercial examples of software being formally proven correct. Maybe in the future the difference between being a programmer and being a Software Engineer will be that the software you write is proven correct. That might actually happen with the help of AI.

jochenm 24d ago

I agree that a correctness proof for a complete, large program will always have the problem that the specification itself might be buggy. So integration tests will hardly ever become unnecessary. But as others have already pointed out, even then formal verification of critical parts of a program can be useful. I would like to add that it can also be of great value if one can "only" prove that a program will never trigger undefined behaviour, or cause a runtime error. For C programs, that would, of course, be particularly helpful. But even in safe Rust, there can be (in my understanding, I haven't yet used Rust myself) runtime errors in the form of panics. And if your medical device stops working, because the software attempted an out-of-bounds read or write and was therefore aborted with a panic, that isn't really fun. Better to prove statically that such invalid accesses will never occur. And this is still for safe Rust - not even considering unsafe code. Similar arguments hold for other system-level programming languages, I guess, even if they are considered safer than C or C++.