5 ms·
Has anyone here ever used Coq to verify a non-trivial piece of production software? What was the experience like? (I have experience with other formal methods,
by pron 10y ago
Has anyone here ever used Coq to verify a non-trivial piece of production software? What was the experience like? (I have experience with other formal methods, a good amount of TLA+ and tiny a bit of Alloy and Why3, but I've never used Coq)
- progval 10y agoThere is CompCert, a C compiler
- pron 10y agoYes, I know about CompCert, but it took painstaking work by a world expert, and even he doesn't seem too thrilled about the process. So I'd love to hear a first-person account.
- maxiepoo 10y agoCompCert took painstaking work by many world experts, it was certainly not some heroic one-man effort by Xavier.
- nonsens3 10y agoSorry for the offtopic, but have you ever used TLA+ to verify a non-trivial piece of production software? I recently found out about it, and was wondering if there are good public use-case details on it! I know Amazon has used it for some of their production systems, such as S3, and DynamoDB, but couldn't find many details.
- martincmartin 10y agoThis is the one paper I know of: http://research.microsoft.com/en-us/um/people/lamport/tla/amazon.html http://research.microsoft.com/en-us/um/people/lamport/tla/am... I know of some small scale use at Facebook (where I work), where it has been used to verify a non-trivial protocol under various combinations of failures.
- nonsens3 10y agoThanks. This is also the paper I was referring to.
- technion 10y agoI've been referred to this paper before when asking this question. Whilst it does discuss that Amazon used TLA+ in nontrivial circumstances, it's still a long mental leap to me to get to "TLA+ for AWS S3 looked like this, and this is the sort of bug it helped quash". It'd be great to see some of that sort of thing.
- pron 10y agoIf you want to see what TLA+ specifications of distributed systems look like, there's this lecture series, each on a different distributed algorithm: https://github.com/tlaplus/DrTLAPlus https://github.com/tlaplus/DrTLAPlus The kind of bugs you find when verifying distributed systems is, if this machine was in that state and that message was in transit, and then the other machine failed, then data was lost". Basically, because formal verification of this kind ensures the specification is correct, it will find any kind of bug there is. But it's those bugs that are either a result of a severe flaw in the design, or bugs that would be hard to find in testing but their results may be serious, that make this worthwhile.
- pron 10y agoYes (well, it's not in production just yet; it's a fairly complex distributed database, for which I verified consistency in the face of faults), and I gotta say -- I enjoyed every minute of it! It has some objective qualities and some subjective ones. The objective ones (as confirmed by others) are that it's easy to learn and you can get productive very fast. I immediately started specifying the large project after two weeks of going through Lamport's tutorial[1]. The other objecive benefit is that it has a model checker. Deductively verifying such large specifications (while possible) is simply infeasible (or, rather, unaffordable and an overkill) -- regardless of the tool you use. The subjective benefit is that the conceptual model quickly clicked for me, personally. I've never liked the aesthetics of modeling arbitrary computations as functions, and the TLA formalism handles sequential, concurrent and parallel computations in the same, extremely elegant way (and allows using the same proof technique regardless of the kind of algorithm, if you want to use the proof assistant). It made me understand what computation is, and how different computations relate to one another, a lot better. The concept -- without the technicalities of TLA+ -- is nicely overviewed in [2]. That said, formal methods are never easy because rigorous reasoning about complex algorithms isn't easy, but it beats hunting down bugs (especially in distributed systems) that are very hard to catch and may be catastrophic; it is also very satisfying. I've found TLA+ to add very little "accidental complexity" to this difficult problem. [1]: https://research.microsoft.com/en-us/um/people/lamport/tla/hyperbook.html https://research.microsoft.com/en-us/um/people/lamport/tla/h... [2]: https://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf https://research.microsoft.com/en-us/um/people/lamport/pubs/...
- wyager 10y agoWhile I think Coq is usually used for mathematical proofs rather than program verification, I know there are a number of formally verified data structures written in Coq that have also been directly translated to other languages. See e.g. https://www.cs.princeton.edu/~appel/papers/redblack.pdf https://www.cs.princeton.edu/~appel/papers/redblack.pdf
- aseipp 10y agoA friend of mine used Coq to implement and verify a linear scan register allocator, to be used in the backend of a compiler for his job. He did this on his own over the course of several months, having not known Coq at all beforehand (though he was a Haskell programmer). The LSRA is also extractable as a Haskell library, so they can use it in their compiler: http://hackage.haskell.org/package/linearscan http://hackage.haskell.org/package/linearscan From what I understand from John, implementing it was quite a challenge. It's certainly not for the faint of heart, but it is not completely impossible. In any case, they seem to have had success with this project and are moving onto working on other components of the project, from what I can tell. That said, from my own personal experience, you're probably a lot better off trying to see if you can formulate your problems in a more domain-specific way and leverage tools for that. Full blown general theorem proving is much more difficult, and I try to think of it more as something to resort to if easier approaches don't work. We still haven't entirely wrapped our heads around the fundamentals like equality (just because it's fundamental doesn't mean it's simple), so there's still a lot of work to be done in the DT world. DTs are one of those cases where I feel the curve is very much exponential: getting 98% of the "correctness" of any given piece of code is actually not that difficult. But going from 98% to 99.9999%, like Coq offers? It's outrageously hard. Sometimes that 1.9999% is absolutely mandatory to have, though (considering CompCert is used in e.g. AirBus/aerospace software, yeah, the extra 1.9999% is possibly vital). For most people, it isn't. Even in Haskell, I tend to stay away from super-advanced type level features, because they can introduce incidental complexity, and Haskell is already somewhere around that 95% mark anyway. With enough type level stuff, it can probably get to about 98%, but with some incidental complexity. So in the vast majority of cases I don't stand to gain much, unless things get extreme... (And personally, out of any theorem prover, I'm most excited for Lean as opposed to Coq, because I like: its speed, and it has many useful features like directly being able to use it to program through meta definitions and the Lean virtual machine, its API and automation features -- and things like C++ code generation.)
- pron 10y agoThank you! > We still haven't entirely wrapped our heads around the fundamentals like equality (just because it's fundamental doesn't mean it's simple), so there's still a lot of work to be done in the DT world. Yeah, even though in the end the proof techniques are similar in algorithms that are complex enough (invariants, refinement), I think that DTs in particular add a lot of accidental complexity (but that's because they try to do more than "just" verification). The difficulty of equality is not fundamental to computations -- it's an artifact of the functional formalism... > But going from 98% to 99.9999%, like Coq offers? It's outrageously hard. That's absolutely true. Much of the problem has to do with the fact that for 100% you need to do end-to-end verification, which means you must reason about the programming language's syntactic constructs, yet with semantics that still generalize and can be reduced (abstracted) to global properties. That's a tall order. > I'm most excited for Lean I'll give it a look. I really enjoy TLAPS, the TLA+ proof assistant, but I'm always interested to see what else is out there.