5 ms·
Verdi – Formally Verifying Distributed Systems (2016)
- awinter-py 9y agoIt's awesome that these tools exist, but the verification codebase for Raft is 10s of thousands of lines of specification & proof files. Just installing verdi on linux nearly bested me (some interaction btwn ocaml package management, coq, and native code). I tried running the verification suite and gave up after 10 or 20 minutes of full CPU. TLA has warts too -- the only way I could interact with it is via a custom java IDE. It would be great to see lighter-weight, more accessible ways to embed proofs in real-world programs and run them in test suites.
- __s 9y agoOn the lightweight end there's https://github.com/catseye/Maxixe https://github.com/catseye/Maxixe
- naasking 9y ago> It would be great to see lighter-weight, more accessible ways to embed proofs in real-world programs and run them in test suites. Not sure what this means exactly. Do you mean extracting the part of the proof that can't be verified statically, for whatever reason, as some kind of test suite?
- awinter-py 9y agoI think I'm asking for something in between a mathematically verifiable proof and fuzzing. A lightweight way to translate runnable code into a symbolic execution environment that can be exercised (not necessarily verified) exhaustively or stochastically. There are relatively few functions that I want to do this for, and I'm okay with doing some manual work to define the possible inputs and how the functions talk to each other (i.e. mock out network / filesystem / database).
- pron 9y ago> TLA has warts too -- the only way I could interact with it is via a custom java IDE. Why? What problems did you run into with TLA+?
- awinter-py 9y agocouldn't figure out how to run https://github.com/ongardie/raft.tla https://github.com/ongardie/raft.tla
- pron 9y agoWhat do you mean by "run"? Check in the TLC model checker? You need to first write a configuration that you want to check. Lamport's Specifying Systems has full documentation for using the model checker from the command line. But if you're a beginner, you might be better off using the IDE, at least at first, as it helps you write a configuration very easily. Also, I would recommend starting with a simpler specification (there are lots of examples available). Otherwise, the checker would just work for a while and spit out "OK", and won't mean much to you.
- hwayne 9y agoI wrote a step-by-step tutorial to using the IDE. Hope it helps! https://learntla.com/pluscal/toolbox/ https://learntla.com/pluscal/toolbox/
- sriram_malhar 9y agoI liked the layered approach in the IronFleet paper. IronFleet: Proving Practical Distributed Systems Correct https://www.microsoft.com/en-us/research/publication/ironfleet-proving-practical-distributed-systems-correct/ https://www.microsoft.com/en-us/research/publication/ironfle... It uses TLA for the distributed protocol part, and Hoare style verification for sequential code, which has excellent toolchain support.
- relyio 9y agoRemember, two years ago James Wilcox and Doug Woos were formally proving Raft's linearizable semantics using Verdi: https://news.ycombinator.com/item?id=10017549 https://news.ycombinator.com/item?id=10017549
- appleflaxen 9y agoYes; because it's mentioned in the article: > Both the Verdi framework and our verified Raft implementation are open-source. Please feel free to submit comments, issues, and pull requests on either repository. [1] https://github.com/uwplse/verdi-raft https://github.com/uwplse/verdi-raft
- nickpsecurity 9y agoYou might find this interesting: https://blog.acolyer.org/2017/05/29/an-empirical-study-on-the-correctness-of-formally-verified-distributed-systems/ https://blog.acolyer.org/2017/05/29/an-empirical-study-on-th...
- palmskog 9y agoSome new developments of the framework in the last two years: - packaging via OPAM to separate framework code and system code - support for specifying and proving liveness properties - support for proving Abadi/Lamport style refinement mappings between systems The following workshop paper gives an overview of current and upcoming work: http://conf.researchr.org/event/CoqPL-2017/main-verification-of-implementations-of-distributed-systems-under-churn http://conf.researchr.org/event/CoqPL-2017/main-verification...
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- im_down_w_otp 9y agoCurrently stuck between a rock and a hard place with things like this. Many of the other formal verification tools make it very easy to have your implementation drift or be entirely unmoored from your specification, but they let you keep working at a level of abstraction from your problem that's still very familiar. Though things like SMACK and DiVinE are helping to decrease the gap between spec and code. Using things like Coq + program extraction brings the overlap between spec and implementation into much, much closer alignment, but brings with it additional problems. Writing a complex program in a very abstract language further away from an engineer's typical problem domain, being fairly limited in types of languages supported for extraction, and/or still having to have an awful lot of faith in the extractor (which itself is unverified as near as I can tell) are all things that are currently keeping me out of Coq for immediate use cases. The good news though is that there's a lot of fairly high-profile work being done (like Verdi) to increasingly bring formal methods to increasingly complex software problems in ways that make using formal methods more approachable and usable, and that's truly wonderful.
- nickpsecurity 9y agoTry TLA+ (learntla.com) for concurrency, Alloy Analyzer for structure, and SPARK or Frama-C for code-level stuff. See if you can feed TLA+ or Alloy properties into stuff like SPARK. E-SPARK did that with Event-B. These are the low-hanging fruit for verification vs full build out in Coq or Isabelle. Then, you write checkers for it to apply testing like KLEE, property-based, or fuzz testing. These will get you close to full verification with less work. Each of the three languages has been used in a lots of CompSci and industrial work. Note that SPIN is similar to TLA+ and you can Google its industrial use for ideas of TLA+ power in concurrency analysis.
- pron 9y agoJava also has code-level specification language called JML, with a rich set of verification tools[1] (in fact, Frama-C's specification language, ACSL, was heavily inspired by JML). Also, if you know TLA+, there's little reason to learn Alloy as well, as TLA+ is a superset of its features (as well as of Event-B, and you can compile TLA+ to Event-B to use its tools[2]) SPIN is not so similar to TLA+, as its language, Promella, is relatively low-level, while TLA+ allows an arbitrary level of detail, and so is well suited to specify very large, very complex applications, rather than small, well-contained ones. Also, if you absolutely must write proofs and have the considerable resources, I believe that Promella requires proving in Isabelle (which takes a long time to learn), while TLA+ has its own user-friendly proof language that hides Isabelle under the covers. [1]: E.g. http://www.openjml.org/ http://www.openjml.org/ and there are others. [2]: https://www3.hhu.de/stups/prob/index.php/The_ProB_Animator_and_Model_Checker https://www3.hhu.de/stups/prob/index.php/The_ProB_Animator_a...