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.
From a practical point of view, however, it's the same argument we write unit and integration tests. We accept error rates in the program under test, the test, the test harness, the programming language, the operating system, the hardware, and the universe. The goal is reduce the error rates enough you can ship something you can get paid for and won't get sued for later before you starve to death.
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.
It is quite believable that it's easier to describe what a program should result in versus actually programming it to produce that result - especially in the most common settings targeted by verification, which is to say imperative, stateful programs or algortihms with a high degree of non-obvious optimisations. The simplest example is a sorting algorithm, which normally has a trivial spec but a non-trivial state at each step.
Interestingly, some specs are actually programs themselves, as has also been true for many on-paper specs which are actually reference implementations. Research using programs-as-specs is still pretty valuable, since in some domains a simpler program is actually the right and useful way to talk about a messier one.
This is obvious for the central cases of a program. It becomes less and less true when going toward the edge cases, especially for a wide array of input.
Complex specs becoming programs is IMHO the direct effect of that (defining what we want is just that burdensome, and special cases we haven't though of will still have a coherent definition in the spec), and we fall back to the base "is this spec even correct" issue the parent points out.
So for pedagogical purposes, can you tell us what you think the trivial spec is?
For a list of items I and an operator LEQ which returns bool for any pair of items in I, SORT() returns a list S such that:
1. Every item in I is present exactly once in S
2. For each consecutive pair of items (S_i, S_j) in S, LEQ(S_i, S_j) is true.
aka, one item in I is missing in your output.
Also, SORT(1,2,3,4) = 1,2,3,4,7
but I do take the view that ( 1, 2, 3, 4, 5, 5, 6 ) is a list of seven values (perhaps the number of dollars in the pockets of seven distinct unique people) and when sorted the output should also have seven items that correspond to the seven input items.
> Also ...
Yeah, that needs tightening up by pastel8739
L = [(5,foo), (2,bar), (2,baz),...]
SORT(L, key=first) # or however it'd be specified
> You need a way to differentiate the two 5s
As there's no unique filtering or other reduction going on here, there's a permutation chain from input to output.
SORT ( 3, 2, 5, 5 ) ->> ( 2, 3, 5, 5 ) and
SORT ( 3, 2, 5, 5 ) ->> ( 2, 3, 5, 5 )
( I'm teasing, perhaps )
Every item in I is present exactly once in S
You have that /s tag, but this is actually the problem with pastel8739's spec as written.
>> 1. Every item in I is present exactly once in S
This actually does require inigyou's example to be the result of calling SORT when you cannot distinguish repeated items from each other.
SORT([1,1]) => [1,1]
pastel8739's spec also doesn't exclude the possibility of inserting new values (so long as they aren't duplicates of items in the source list).
2. If the comparison implements a strict total order, the output is sorted according to it.
However, that specification is not trivial. Almost nobody correctly articulates property 1 when first encountering the problem if they do not already know the answer or are already aware it is a trick question (and even then most software developers still fail).
Furthermore, that also sidesteps the problem of formally specifying what a permutation is. Unless you have a grab bag of already proven powerful theorems, the author is most likely also going to make a error doing that as well even if we start at a proof abstraction level comparable to normal programming.
Reality is that trivial problems admit trivially wrong specifications exceedingly easily. There is little reason to assume that much more complicated problems that are hard to even articulate will magically support obviously correct specifications that are simpler and more understandable than the code.
More then theorem proving what attracts to Lean is that it's type system is insanely powerful, indexed dependant inductive and quotient types allow the realization of "making invalid states unrepresentable" to a degree no other language can, except perhaps a custom DSL built with Racket
One must remember that Lean wasn't made for math, it ended up succeeding in that vertical because it was expressive enough to represent the extensive design space mathematicians were dealing with
And I think that's equally applicable to specs and business logic
The easiest way to demonstrate this is to write two implementations of an algorithm. One with no optimizations, the other with optimizations.
The formal verification can then be a proof the optimizations maintain the semantics of the simpler version and you can focus your review on the simpler version.
E.g. finding a general solution for a cubic polynomial is difficult. Proving that a solution is correct is conceptually trivial: substitute a solution for x, and simplify. Many mathematical problems are well-defined in this way.
In the case of a compiler (CompCert), the program is already, in part, being written according to the language spec. So that definition can be used in verifying a compiler. In a domain where there is no standard specification or required properties, then coming up with a spec is hard (probably as hard as coming up with a solution).
(It doesn't. Because formal verification is hard. See cve-rs for how to corrupt memory without unsafe. Rust has stated they do not intend to fix cve-rs.)
It is a nothingburger problem because one is going to have that problem as well even when not employing formal methods. Except without FM the spec will be in natural language and therefore it will be impossible to mechanically verify the end product with it. And since natural language specs are highly liable to be ambiguous or contain unintended holes, LLMs won't save us either.
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.
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
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.
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.
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.
I would say Ada SPARK solves this problem.
The analogy I'd make is to the idea of "type driven development" that buf/protoc represent, where one defines their types and schema in proto and then types for specific languages are generated from that
The limitations there however is that proto is not a programming language and inflexible/inexpressive whereas Lean is one of the most expressive languages to date
The two are different artifacts for different jobs. The same is true for code and architecture. That they have an impedance mismatch is a feature.
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.
Proving a specific implementation in a specific language is really the domain of that language or tools targeting that language.
In digital design for example, SystemVerilog has a whole sub-language for specifying formal properties that can be proved in simulation or with tools that prove the properties mathematically.
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
[2] https://www.animats.com/papers/verifier/verifiermanual.pdf
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.
A useful practical way to look at formal methods is "just" as testing on steroids, rather than as competition for testing. The pros and cons are mostly the same: Depending very much on their skill level, the practitioner gets a definite but finite improvement in correctness and particularly resistance to regressions, for the cost of additional upfront time and ongoing friction during maintenance. The main difference is the amount of "punch" in each passing spec requirement, which can be equivalent to an infinite number of concrete passing tests. (In the other direction: Ordinary testing using a few handpicked example (input, expected output) pairs is formal verification, just of an especially thin kind.)
Sitting in between ordinary manual tests and formal verification of entire program properties is property-based testing like Haskell Quickcheck, which offer some of the benefits of both.
Ah, but if you have specifications, you should have the ability to generate unlimited numbers of tests. Handpicked examples aren't needed. The great advance in testing with increase in compute power was the realization that carefully handcrafted tests are silly; just blast huge amounts of randomness at the system and use cheap compute to save expensive human effort.
I think it's a common experience to implement some well-defined data structure or algorithm and use the clear specification of its behavior to randomly test it, to then discover this flushes out all the bugs.
Also note that a specification can be input to other tools, such as a formal verification system for an encompassing system.
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?
It's like 80% of the work after raising a PR is just socializing ideas and getting people to agree on stuff
Maybe with formal verification the laws around that can change?
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.
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.
Businesses would be able to rubber stamp a "Verification of Correctness", and the government could parade this political achievement around to people not knowing better, satiating their hunger for better quality software (supposedly).
In the meantime, programs would indeed feel like they became better. Except that'd be less due to them being formally verified, and more because generating all the formal verification artifacts would practically require using agents, and those agents would incidentally produce better work than what's currently typical. Not the least because people would more readily pose tough requirements to them, without regard for the difficulty.
Eventually we'd then get back where we started, with programs being flawed, just flawed in a consistent way from some arbitrary perspective (so as to still pass formal verification, of course). Since regulation would be obsessed with the rubber stamp rather than anything else, the businesses would continue to float about as usual. The only thing that'd change would be the nature of the issues.
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.
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.
I'm not sure you want to create a record of intentional decisions if you're at Facebook though.
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).
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.
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.
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