33 ms·
CreuSAT: Formally verified SAT solver written in Rust and verified with Creusot
- Animats 4y agoNice.
- Jweb_Guru 4y agoIn addition to the project itself being very cool and useful (you can count the number of verified SAT solvers that can solve most problems in modern SAT competitions on two fingers!), it's also an impressive demonstration of its toolchain, which essentially exploits the fact that the purely safe fragment of Rust (augmented with a handful of types that use unsafe code like Vec, which I believe have been proven compatible with the rest of Creusot in another recent paper) behaves like a functional language. This allows borrow-checked Rust code to be treated purely functionally in safe contexts, which allows exploiting the large amount of existing software tailored to proving purely functional specifications, without having to worry about memory-related side conditions, separation logic, etc. This has always been the hope for Rust verification tools (that Rust would scale to these kinds of large proofs better than other industrial imperative languages due to the restrictions of the borrow checker), and I think this is the first real practical indication that that is indeed the case. Both in terms of verification time and additional verification code, it weighs in at a small fraction of that of the only other verified solver with comparable performance on SAT benchmarks (IsaSAT), which is extracted using code generation from Isabelle (which is a full proof assistant), while other attempts to produce verified SAT solvers directly from imperative code fall far short of its performance because they do not implement any of the difficult optimizations (presumably due to the amount of extra proof effort required). Incidentally, another paper has come out at basically the same time making a similar observation, Aeneas: https://arxiv.org/abs/2206.07185 https://arxiv.org/abs/2206.07185, which uses a resizable hash map as its case study. Since it just came out, it does not have any larger proof developments yet that could be used as comparison, and it has somewhat different goals, but overall I am also excited about it and am very hopeful for the future of verification tools that integrate directly with Rust code like these two, as I think they are one of the more promising avenues towards the regular integration of verified code with more "ordinary" projects.
- jerf 4y agoDoes the proof encompass some sort of proof of amount of RAM consumption in it, presumably bounded by some characteristic of the problem presented? Regardless, this is very impressive, and one of the first things to raise my eyebrows w.r.t. formal proofs being possibly useful in the real world in a long time. If safe Rust can function as the bridge between the "practical" world and the world of proofs, that alone would be enough to justify Rust's existence.
- Jweb_Guru 4y agoNo, it does not. This is mentioned as a limitation in the paper (it does, however, handle things like integer overflows correctly). I believe with some suitable extensions, it would be possible to prove invariants like this as well, but IMO functional correctness is a pretty good start!
- Sarek 4y agoIt does assume enough RAM, as it has no way of knowing how much RAM the target machine will have. It is thus correct with regards to the model specified by Rust, but a program which is proven correct in Creusot may get an OOM-error. A note here is that it will not provide the wrong answer due to insufficient memory, but it will crash. Proving some upper bound on the amount of memory used (and potentially gracefully exiting) should be possible, but I have not prioritised it, as OOM has not been an issue.
- jerf 4y ago"has no way of knowing how much RAM the target machine will have" That's why I phrased it in terms of a bound based on some characteristic of the problem. But I was just asking for information. I know it's a well-known problem. To be honest the fact that we're even seriously discussing this as something that may be doable is a huge step forward. AIUI, previous state of the art on real languages would have this as hopelessly pie-in-the-sky. I think in many cases memory bound is uninteresting; one could examine a vector implementation and be satisfied that it won't explode unnecessarily. After all, we do exactly that on non-proved implementations without too much fear all the time. SAT just came to mind as a problem where that could be an interesting thing to be able to prove.
- eutectic 4y agoI thought proof checking tools mostly negated the need for verified sat solvers.
- Jweb_Guru 4y agoProducing the proofs (especially for UNSAT) is often very time consuming, and verifying them can be subtle (and if an incorrect proof is produced, you still have to deal with that case somehow...). It's not so much that they negate the need for verified SAT solvers as that creating and maintaining a verified SAT solver was considered much too difficult to justify the proof effort required. If the goal can be accomplished with an order of magnitude less effort, that calculus changes somewhat.
- zozbot234 4y agoSAT solving is the subtle and time consuming part. A valid SAT proof certificate can be verified efficiently.
- Jweb_Guru 4y agoI'm referring to producing the certificate as the time-consuming part, not the verification time (I disagree that verification is not subtle, but I suppose that doesn't matter as there are verified verifiers). For example, many SAT solvers no longer attempt to provide "pure" resolution proofs because they are too expensive to produce, which restricts the kinds of techniques you see used in competition. In fact, producing certificates efficiently is an active research area, which wouldn't be the case if certificate production had negligible cost, e.g. see https://lmcs.episciences.org/9357/pdf https://lmcs.episciences.org/9357/pdf.
- xavxav 4y agoSAT comp gives you 5x the solving time to check your proof, which is indicative that checking isn’t so simple (though it is on paper)
- Sarek 4y agoGenerating a proof and checking it is definitely a step up, but it does have a few issues. - SAT is in NP, and UNSAT is in CoNP. This means that proofs take a lot of space to store and a lot of time to check. Proofs are usually run with 5x the time limit of the initial solve, and still end up timing out. - Proofs are (currently) based on resolution, which means that research on efficient solving techniques which can not be efficiently modelled as resolution is not being prioritised. This is touched on briefly in the first 2 talks of Randy Bryant on: https://fm.csl.sri.com/SSFT22/#splogic https://fm.csl.sri.com/SSFT22/#splogic. I think the talks in general are among the better for understanding a SAT solver like CreuSAT.
- xavxav 4y agoHi! I’m the author of Creusot, Sarek did some amazing work on CreuSAT, he also had to teach himself formal verification and SAT solving along the way. If you have any questions about CreuSAT or Creusot, I’d be happy to answer
- rch 4y agoAt first glance I didn't see a license in the repo. Am I missing it?
- OscarCunningham 4y agoHow does it compare to kissat in terms of speed?
- dralley 4y agoSome usage examples and performance comparisons against other solvers (e.g. minisat, varisat) would be nice.
- xavxav 4y agoCheck out Sarek’s thesis in the evaluation section: https://sarsko.github.io/_pages/SarekSkotåm_thesis.pdf https://sarsko.github.io/_pages/SarekSkotåm_thesis.pdf. In general it’s roughly at the level of microsat so worse than minisat and kissat, but not garbage either.
- netr0ute 4y agoWill there be a version of this for the College Board type of SAT?
- jerf 4y agoThat's not possible; it's well known that the College Board SAT is inconsistent: https://www.youtube.com/watch?v=POMX80Q11O0 https://www.youtube.com/watch?v=POMX80Q11O0 https://www.youtube.com/watch?v=Xh5coE5wJ2I https://www.youtube.com/watch?v=Xh5coE5wJ2I
- bergenty 4y agoThose examples are mistakes the test makers made. It doesn’t make the test “inconsistent”.
- newca12 4y agoUnsurprisingly, we can see a growing interest in the Rust ecosystem regarding formal verification. I try to keep https://github.com/newca12/awesome-rust-formalized-reasoning https://github.com/newca12/awesome-rust-formalized-reasoning up to date. I will add CreuSAT shortly. The goal is to have an overview of what is actually Rust powered. Long term goal is to identify best practices and provide usefull common libraries.
- bjornsing 4y agoSo can CreuSAT be used as a backend for Creusot? A “self-hosted” SAT-solver, in the sense that it can prove its own correctness, that would certainly give you a speaking slot at some conference. But also a philosophical dilemma I guess. :)
- Sarek 4y agoThis was asked in the Rust Zulip as well, and is actually the original idea which this thesis evolved from (Xavier said something along the lines of "My supervisor and I have talked about how cool it would be to have a solver which verifies itself"). The short answer is that it should be possible to write a Why3 driver for CreuSAT which allows it to handle basic propositional reasoning, and that one would probably need to add some theories. The a bit longer answer: Getting it to work as a backend should probably not be all that hard, and it should probably be possible to make it able to prove some things as well. Getting it to verify itself would probably be very hard. As it stands, the proof needs Alt-Ergo, CVC4 and Z3 (all of which are really good) to pass, and some of the obligations take a long time. A solver capable of verifying itself would (I imagine) have to put much more emphasis on having only simple proofs which were solvable using a minimal amount of theories, and would probably have to run for a very long time. I dunno, would be a fun project, and I guess one could decide after having tried to prove for instance Friday (the super naive solver) if it is at all worth pursuing.
- thesz 4y agoThis project uses one-way translation of Rust code into WhyML through Creusot. This translation is not formally guaranteed to be correct or semantics-preserving. Ideally, the code produced by Creusot should be translated back to Rust by a tool from Creusot or someone else. This way it is possible to use fixed point iteration, just like AST pretty-printer and parser for programming language syntax. This is more or less an approach taken by verification team of Buran (USSR's space shuttle) software. They took Fortran code and compiled it into executable code. The executable code was then manually translated back into Fortran and discrepancies analyzed. This way they found several errors in Fortran compiler. Buran made fully automatic landing in late 80-s. Contemporary verifiers should do the same automatically.
- jasinjames 4y agoFascinating anecdote. Where can I read more about this?
- thesz 4y agoI don't know where you can read more. There are resources in Russian, but buran.ru is not quite functioning right now. I remember that story from the time when I worked with guys from Russian CQG team, who, in turn, worked in CQG with the member of the Buran's software engineering team. It was 15 years ago.
- xavxav 4y agoIndeed, Creusot itself is not formally verified, but we have verified the metatheory in our paper RustHornBelt: https://people.mpi-sws.org/~dreyer/papers/rusthornbelt/paper.pdf https://people.mpi-sws.org/~dreyer/papers/rusthornbelt/paper.... Actually verifying the translation that Creusot produces would definitely be interesting future work, but I'm not sure it's where the best 'bang for the buck' is found right now, though I try to ensure the underlying translation would remain simple to formalize.
- rowanG077 4y agoIs it guaranteed that Rust -> WhyML -> Rust Would ever yield a fixed point?
- hinkley 4y agoThere's a whole undiscovered country of writing software that is both mathematically sound and intuitively sound. I had a long list of hopes and dreams in the late 90's of what I'd hoped software would be by now. I got about half of my wishes, and some of them were weird for me because I went from bitter struggles to get even lip service to some of those things, to two jobs later having them taken for granted. It's weird to brace for push back and then have people nod and change the subject. This is one of the wishes I have for 2040, that we continue to prove the ergonomics of type theory and escape analysis, and that having succeeded there, we start normalizing other domains of provably correct code. If you can do that for SAT solvers, maybe we'll start writing other kinds of AI in such a manner.
- danuker 4y agoThere is TLA+ for verifying specifications. Here is a talk by its creator: https://www.youtube.com/watch?v=-4Yp3j_jk8Q https://www.youtube.com/watch?v=-4Yp3j_jk8Q
- asimpletune 4y agoI have wondered at times if the reason why we don't have those things is because, in such an environment, 20th century management might not work. Basically, "the curse of lisp", although I don't mean lisp specifically in this case, but rather languages and tooling that unleashes the power of formal verification and, in a larger way, the power of math. It's conceivable that in an alternate universe an individual engineer's productivity could be so high, because of math, that one developer would replace a whole team from our universe, and bugs would be extremely rare and mostly restricted to UI. From that point of view, the theory says, it's harder to build teams and these super charged developers are natural information silos. Or, in other words, it feels like the tech choices made have demonstrated a slight preference of less efficient developers that all understand a shared problem (e.g. this team is responsible for testing, or this team builds integrations with APIs, or another team parses unstructured data into structured data), over technology that would aid or formalize many aspects of those kinds of problems and others. Also, in such a world, I feel that software engineering would be much more abstract, and it probably wouldn't be approachable to those who aren't legitimately fascinated and interested in this stuff. Sort of like how I've never met anyone in my life who studied Math just to get rich, even though you can become phenomenally wealthy if you do. More likely though the answer is complicated and it's a mix of historical accident, what I mentioned, and a slew of other factors. Nonetheless, I too think it would be so cool if I could spend my time writing programs that write programs that write programs, all guaranteed to match how I stated the problem's invariants. I could spend the majority of my time really understanding the requirements and assumptions, as opposed to actually implementing the features.
- joshlk 4y agoWhat are some practical applications for a SAT solver?
- Jweb_Guru 4y agoVerifying programs, for one thing--CreuSAT actually calls out to no less than three different SAT solvers in the course of automatically discharging its proof obligations :) More generally, SAT solving is useful whenever you have something that can be represented as a circuit, which is an extremely large class of problems. Indeed, SAT can be proven to be polynomial-time equivalent to any problem in NP (which you can read as "any decision problem whose yes solution is efficiently verifiable"), which includes many useful problems: common examples include the traveling salesman problem, detecting hamiltonian cycles, subgraph isomorphism (interestingly, graph isomorphism is no longer believed to be NP-complete), graph coloring, and many others (which in turn often have easy reductions from other extremely useful problems). Since SAT solvers have received so much optimization work, in practical cases these problems are very often solved by reducing them to some variant of a satisfiability problem, rather than trying to solve them directly. It is even more useful when combined with theories that can compute special cases (like arithmetic on natural numbers) much more efficiently, which is known as an SMT solver (satisfiability modulo theory). Sometimes, the theories are undecidable, which means the SMT solver is allowed to report "don't know" or run forever in some cases (in practice, people then massage the inputs to try to get them within the solvable cases). This is the form in which SAT solvers are used most often. There are a ton of applications, but an immediate one is determining whether version constraints in a package manager (which may include equalities, inequalities, etc.) can all be simultaneously satisfied (and producing a satisfying assignment). There are a lot of good examples, though, which is why SMT solvers are so ubiquitous in the literature when it comes to "how do we do this really hard thing?" (e.g. they are often critical components of program synthesis). Sorry if this wasn't that helpful--it's a very broad topic and I'm sure many people here can give you a much better answer!
- k0k0r0 4y agoAnother SAT developer here. Most prominently, SAT Solvers are used in the design and construction of CPUs. See the EDA Challenge of the SAT Competition 2021.
- _8j50 4y agoI am actually having to learn about SAT solvers. Is there any newbie friendly resource you think might help?
- mbrodersen 4y agoExcellent work. Kudos to the author(s). I have been looking for a way to write verified performant practical software for a long time, and CreuSAT is an example of how it can be done using Creusot. Thanks!