11 ms·
The Case for Formal Verification (2013)
- dkarapetyan 13y agoYes on all counts. I never understood why the TDD culture was happy to write down a complicated function and then only verify that on input 2 the output was 4. It always seemed backwards to me especially when you could have just as easily verified that in the REPL and called it a day. To me TDD on its own is just glorified documentation and tells me nothing about the actual properties of the software. Formal proofs and verification on the other hand is definitely something everyone should be striving towards especially for foundational components of computing, e.g. compilers, virtual machines, kernels, security/network protocols, etc.
- hyp0 13y agoMore like glorious documentation: verified to be up to date... and has examples. As others mentioned, regression testing is about the only really useful correctness step. There's also motivation, to keep on track for what is actually needed. Also it helps you write an API, rather than just implementation: the tests are a client. (On the downside, these extra clients depedence on your API, also make it more work to change that interface, giving it more inertia). Plus: who shall test the tests? NB: I'm not a TDD adherent, never used it, so take what I say with a grain of salt: it's just my own reasoning + what I've heard from people who've tried it.
- noselasd 13y agoOne big advantage is regression testing - which is why you don't just test it in a REPL and forget about it.
- ryanobjc 13y agoTotally agree here, manually verifying a chunk of code once, for example early on in the dev lifecycle, then having it exist inside a big system is really the "EE" way of doing things. But the reality is you gotta dig deep and change stuff, after all how often does an engineer dive in and change how a transistor works (laws of physics be damned!) I feel like overall software quality has been harmed by the emphasis of mathematical proof of code. The problem is that it's not currently possible (for a variety of reasons, including underspecified languages, math, research and many others) to formally verify, end-to-end, a real world system (eg: Oracle Database, Salesforce.com CRM, etc). Over promising on software proof, and under delivering has diverted attention away from relatively simple and "boring" practices to increase code quality. While people in this thread are mocking TDD, the reality is most code I have seen in a production setting is really bad. Unit tests that aren't, test runs that take 4 hours, complete lack of tests, opaque tests that are hard to debug, and hard to fix. A lot of TDD and agile code/clean code says "let's make the code easier to read, have unit, real unit tests, for everything and refactor and get rid of cruft as often". While these are TOOLS and judicious application applies, in a production code scenario there is often no justification, other than ignorance (always fixable!) to disregard good advice! To summarize the good advice: - make code easy to read at a glance - code should be self-documenting (refinement of the above) - units should be testable independently - tests should exist at higher levels, such as integration and end-to-end tests Just like the 10 commandments, you don't have to believe in Agile or XP to agree with these basic things.
- CHY872 13y agoI'm sorry, but I don't believe this point has any merit with regards to this discussion. Formal verification was seen as the future for large systems for some short time in the latter half of the 20th century, and since then no one has seriously suggested verifying programs of millions lines of code. The point that is made here (quite sensibly) is that in many cases, by verifying small parts of your codebase (a few hundred lines, perhaps), you can rule out whole classes of bugs. To give some useful real-life exampled, in OCaml (or at least in Standard ML), if a program compiles one can know that it will never crash (i.e. leave the control of the system - it might still abort) unless the compiler has a bug (and there's now a verified ML compiler for x64). Other useful properties might be to prove that a driver terminates (Microsoft SLAM/T2) and so will never hang the system, or a compiler that produces code semantically equivalent to the spec of the language. You say that software quality has been harmed by the emphasis of mathematical proof of code - I just don't see how this can be the case. In a typical education, a student will see two types of proving code - in an algorithms class, where it is required in order to show that the algorithm solves the problem (and totally separately to actually building software systems), and in the formal verification/model class, which I doubt is taught at many universities and is almost certainly optional. If someone enters the workforce without sufficient knowledge of test driven development, isn't taught at their place of work and writes bad code, there's a nice long list of people they can blame (their bosses, the people reviewing their code, their style book, their examiners, their lecturers, etc.) but it's not valid to blame formal verification for this, no more than it is valid to blame the hypothetical course on FPGA programming they took at some point. Yes, test driven development is great, but it is totally complementary to this sort of thing.
- Pacabel 13y agoYour description of TDD is a pretty blatant misrepresentation of the actual philosophy and techniques. Furthermore, I think that you're ignoring that TDD tries to be a practical solution to certain real-world problems. This means that trade-offs are made in the name of creating software that works sufficiently well, while keeping expenses in check. Sure, extensive formal verification of all software would probably bring some benefit in terms of correctness and perhaps security. But you're not considering the cost involved. So far, such verification has only proven to be possible in rather limited situations, namely where there are significant resources available, or in academic exercises. Maybe this will change in the future, but in the present it's generally far more cost-effective to use a statically-typed programming language along with some form of automated testing. That gives many of the benefits of more formal methods of verification, but while also avoiding many of the costs, even if the end result doesn't conform to some theoretical idea of "perfection".
- daleharvey 13y agoReally confused at why this comment is being so harshly downvoted, it seems fairly accurate, possibly downplaying how useful formal verification may be in the future, but the parent is most definitely misrepresenting the practicality and usefulness of TDD
- ryanobjc 13y agoI also agree, have some upboats. The reality is that programming is an engineering endeavor, and in the face of limited resources, we have to choose the tools that can offer realistic benefits now. Formal verification is not that tool for most projects right now. Would instagram or even facebook be better off? Most people would, correctly, say no. And ultimately in the end, nearly all software (including quite a bit of open source software!) is written in pursuit of business reasons, and has to answer to that.
- sanxiyn 13y agoI'd think the security of Facebook privacy settings will be improved by, for example, lightweight modelling using Alloy. Alloy would catch bugs like this one: http://mashable.com/2011/12/06/facebook-bug-zuckerberg-photos/ http://mashable.com/2011/12/06/facebook-bug-zuckerberg-photo... When I read about that bug in the past, I thought "this would be a great example to use for Alloy".
- betterunix 13y agoThe problem with proofs is that you need to know what to prove, and that is hard. Even formalizing something as seemingly simple as sorting is tough for most programmers. If your formalization of whatever you wanted to implement is wrong, then your proof is worthless -- you have only proved that your program does something other than what it was supposed to do. It's not that TDD is perfect, but it is a pragmatic approach to reducing bugs and it helps a lot in preventing regressions.
- Dewie 13y agoWriting a specification for sorting sounds a lot easier than actually writing a sorting algorithm. Though admittedly I have never used a programming language where I could try to encode this property in a type.
- chriswarbo 13y agoWhy are imperfect programs and test suites useful, yet imperfect specifications are worthless? It's not all black-and-white. Specifications, like test suites, contain many properties. The problems of specifying slightly-wrong behaviour on edge-cases might be more than offset by the security guarantees that are gained. Also, note that many properties are built on each other and specifications will grow and change along with the software. Incorrect properties are often incompatible, but unlike tests which may never hit the incompatible cases, a verification tool will refuse to accept such incompatibilities.
- AnimalMuppet 13y agoThe article was talking about security. Security errors in specifications can be edge-case-like stuff. Or... Back in the day, Microsoft very deliberately designed Outlook so that it could execute a file by having the user click on it. That was in the spec. It was also an enormous security hole. It wasn't just an edge case - the security hole was the essence of what the spec required. If you get a spec like that, formal verification can do to things. It can tell you that yes, your code does what the spec says, without introducing any (additional) security bugs. That's somewhat useful, but it won't save you if the spec itself is the security bug. Or, formal verification might be able to tell you that the spec itself is a security problem. That might not be called "verification", though - it might be called "theorem proving" or some such. It's in the same neighborhood, though.
- ryanobjc 13y agoWhile you are correct, I'm not really sure how I feel about you mocking documentation really. I guess communicating with your coworkers is pretty passe?
- dkarapetyan 13y agoI am not mocking documentation.
- ryanobjc 13y ago"just glorified documentation" I think it's pretty well understood that calling something "glorified" is making fun of it. Perhaps I guess you meant to mock TDD but it also seems like you are mocking writing documentation. While it could cut either way I guess, I decided to take a snap judgement (like 99% of your readers) and call you out on it. Sorry.
- biot 13y agoDon't make the mistake of thinking the pattern "[something perceived as greater than X] is just glorified X" calls into question the value of X. Rather, it's the perception of being greater that is being called into question. If I say "soda is just glorified water" do you think I'm mocking water and that I don't think water is vital for all life on this planet?
- sliverstorm 13y agoPerhaps because formal verification is hard & very expensive? For starters, where does an open source project come up with an entire compute farm...
- betterunix 13y agoYou can do formal verification with tools like Coq using a laptop. The real issue is that writing a formal specification is hard even for small problems; writing a formal spec for something like TLS would be harder than actually implementing TLS.
- sliverstorm 13y agoCool! I do hardware, I guess software is probably easier to compute.
- betterunix 13y agoAh, you might have been thinking of techniques basic on SAT and ATPG solving. What makes software different is this: https://en.wikipedia.org/wiki/Curry-Howard_Correspondence https://en.wikipedia.org/wiki/Curry-Howard_Correspondence Basically, checking a proof of correctness for software is equivalent to type checking (for a very fancy type system).
- 0x0 13y agoIt can still be useful documentation. Four years later and after a couple rounds of heavy refactoring, it's nice to verify that 2+2 still equals 4.
- platz 13y agoPerhaps Test Driven Design is more about producing a certain kind of design, rather than about guarantees about correctness.
- stormbrew 13y agoI find it strange to think that TDD and formal verification are at odds with each other. For it to be backwards to write dynamic tests, you seem to be suggesting that it is actually worse than doing neither. I also don't see how it can be documentation, glorified or otherwise, and not tell you anything about the properties of the software. Really there are perhaps three practical levels of knowledge about what a piece of code does: - It does something. - If I give it X it gives me Y (for some finite set of X). - It will never do Z (for some finite set of Z). The first is the state most software is in most of the time. The second is achievable with tests and some kinds of static analysis. The last is probably only achievable with formal analysis and code that fits the constraints of that formal analysis. But both levels are at least an improvement on nothing at all. Having functional and documenting tests does bring meaningful knowledge about some subset of what the code does, even if it isn't the be-all and end-all of code analysis. So I don't see how you can dismiss it so easily, when to me it's just a step on that striving you mention in your final sentence. For the moment it is perhaps true that the good is the enemy of the great on this, but that will become less true as the tools get better. After all, even this article talks about only formally verifying part of the code of a web browser. Until and unless formally verifying the entire thing becomes possible, you still probably need the Acid tests to demonstrate its capabilities and help prevent regression.
- dkarapetyan 13y agoSuppose I tell you 3 + 2 = 5 and 2 + 3 = 5. Did you learn anything non-trivial about + from those two examples? Did you learn that x + y = y + x for all x and y or that x + (y + z) = (x + y) + z? You can sample as many points as you want and you'll still be no wiser as to how + behaves and how it interacts with * or that the implementation of + even respects any of those properties. If you're going to put in the effort to generate unit tests then why not go a bit further and formally verify the correct functionality? All this is just a roundabout way of saying I don't write unit tests. There is no value in it when I have convinced myself each subcomponent is correct and that composition of those subcomponents preserves correctness. You can write all the unit tests in the world and if you don't verify that the composition of your components preserves the correctness properties those tests are meant to verify then you might as well not have written those tests because now you have created a false sense of security. If you can verify the kernel pieces of your code and then the composition mechanisms then you're done. You don't need to verify the entire thing as long as the entire thing is built with the kernel pieces and verified composition mechanisms that preserve correctness. I also suspect we are still talking about separate classes of software. For your run of the mill twitter clone if it makes the corporate overlords happy then write as many unit tests as you want because it doesn't make a difference either way. But if we're talking about actual fundamental software like OS kernels and compilers then I don't think you can have enough formal verification.
- dllthomas 13y agoIt's a lot easier to be sure that you are correctly checking that 2 + 2 = 4, than to verify that you're proving the right thing. If you have your proof in hand, and unit tests, you should be more confident than if you have just your proof. Vice versa as well, of course (and probably more so) but that doesn't mean you shouldn't test properties of your code.
- ramidarigaz 13y agoRelevant: I attended LambdaConf yesterday at CU Boulder, and there was a _great_ intro workshop for Idris, which is in the same domain as Coq. Idris is similar to Haskell (it's actually written in Haskell), but with a dependent type system, a tactic-based theorem prover like Coq has, and a bunch of other fun features.
- tluyben2 13y agoIdris is really worth checking out if you have any interest in this kind of stuff. I used Coq and now am playing with Idris and F*; the latter two feel good and practical. With an FP background they are easy to pick up.
- jnbiche 13y agoI've also been playing around with these two. I have a little Haskell and some OCaml, but very little understanding of the mathmatics involved in dependent typing, so I'm struggling but still very interested. Wish there were an accessible guide like "Learn you a Haskell" for Idris. By the way, for anyone interested in these two languages with dependent typing, you can try out both Idris and F* online, without installing anything: http://www.tryidris.org/console http://www.tryidris.org/console http://rise4fun.com/FStar/tutorial/guide http://rise4fun.com/FStar/tutorial/guide
- tluyben2 13y agoMy background is theoretical CS (2 of my professors were pupils of Dijkstra and they were quite particular about formal verification as you can imagine) so that helps; it's good for anyone with an interest in this to read books like 'A discipline of programming' by Dijkstra or more modern books about it (and if you really like it, continue on to Pierce who is the types guy and when I read his some of his work the first time I kind of wondered wth we were doing in programming while this guy already figured it out to such an extent ;). It all starts to make more sense after some of the theoretical basis. I guess; I don't know how much years of writing formal proofs on pen & paper 20 years ago influenced me in reading this stuff.
- 13y ago
- Igglyboo 13y agoCan someone explain why CompCert is not more popular? A formally verified compiler seems to be much more useful than something that can produce bugs.
- dkarapetyan 13y agoFor one you can still write buggy software in it and for another there are some limitations that can be potential deal breakers: http://compcert.inria.fr/compcert-C.html http://compcert.inria.fr/compcert-C.html. That links spells out some of the limitations.
- ahomescu1 13y agoIt doesn't support all of C99 [1]. In real-world code, you need that, plus the GNU extensions (the clang developers put in a lot of work into making clang fully compatible with gcc, going as far as accepting the same command-line switches). 1 - http://compcert.inria.fr/compcert-C.html#subset http://compcert.inria.fr/compcert-C.html#subset
- nullc 13y agoConsidering that the parts of C99 that it doesn't support are also not supported by MSVC I can't imaging that that alone is much of a big deal. The prohibition on commercial use is a much bigger barrier, I expect.
- ahomescu1 13y agoMSVC supports C++ instead (AFAIK, it has most of C++11 implemented), while CompCert doesn't compile C++ at all.
- vilhelm_s 13y agoIt's not free software (the license permits educational and research but commercial use). I guess selling compilers to people is a hard problem in itself. :)
- cwzwarich 13y ago
- comex 13y agoSomewhat off topic and very speculative, but I'm curious how feasible it would be to propagate safety proofs through compilation - not just formulaic memory safety rules but hopefully also arbitrary behavioral proofs - all the way down from a source language to machine code, so that essential properties could be formally verified without needing to either trust a compiler or use a provably correct one, in the latter case with corresponding difficulty of modification and low optimization level. The compiler would still have to be modified to do the propagation, and a machine code model and verifier constructed, but theoretically this would be easier than proving the whole thing works correctly. I guess Typed Assembly Language works along these lines: http://www.cs.cornell.edu/talc/ http://www.cs.cornell.edu/talc/ but I haven't read up on the papers, and it seems outdated. My imaginary end goal (not that I'd be able to do anything remotely as ambitious myself, but I still like to think about it) is an operating system where all code is run in kernel mode after being checked for safety - like Singularity OS but without trusting a compiler. Perhaps that trust doesn't actually matter very much, since the compiler is unlikely to contain too many exploitable bugs (AFAIK most Java vulnerabilities are not related to the JIT, for instance), and there are plenty of other places in such an operating system bugs could hide anyway. But it's inelegant to require all code to go through a single compiler. For example, it would be cooler if the assembly verifier were not baked into the system, but simply a program proven to correctly check whether some code is safe in the machine code model; if you (any user) could prove a JIT never generates unsafe code, you could submit the JIT in place of the verifier, and run wild with it without going through any slow compilation or verification processes.
- betterunix 13y agoOn the topic of trusting compilers: http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/
- dkarapetyan 13y agoWhat exactly is doing the verification? Another program, no? In which case why would you trust that program any more than the compiler that generated the machine code? At some point you must trust something to be correct. Whether that's the compiler or something else doesn't really change anything.
- wsxcde 13y agoCoq is an interactive theorem-prover, which is exactly what it sounds like. You prove your theorems more or less by typing out the proofs and the system mechanically verifies that each step in your proof is sound. I've used Coq and I'll be honest. This is unquestionably a solid way to prove things about your program but it is too much of pain to expect this to have significant adoption in the "real" world. In the hardware world, there's been a lot of progress in automated verification thanks to modern model checkers [1,2] (which incidentally build on modern SAT, and in some cases SMT, solvers [3-6]). The nice thing about model checkers is that you just specify the property you want proven and let the verifier crunch away and it will (hopefully) come up with a proof or a counterexample. This has been successful enough that there are companies like JASPER and OneSpin which make money by selling hardware companies formal verification tools. I worked with JASPER's tools in the recent-ish past and one of the big things they seem to have done is make the tool much more usable. With the JASPER tool, it was much less of a pain to configure the model checker, abstract away parts of the design, keep track of the properties specified and proven, examine counter example traces and so forth than I was expecting. A lot of this sort of thing doesn't get done in academic tools like ABC because it doesn't count as research. But such improvements are extremely important if you want to push adoption of formal tools in an industrial setting. And from what I can see the emphasis on usability seems to paying off for JASPER. Model checking in software has been less successful because the state explosion problem is much more pronounced but there have been notable success stories like Microsoft Research's SLAM project [7]. And I definitely think there is an opportunity here to build upon the algorithmic progress in automated verification in order to build tools that are much usable in a software setting. [1] http://ecee.colorado.edu/~bradleya/ic3/ http://ecee.colorado.edu/~bradleya/ic3/ [2] http://www.eecs.berkeley.edu/~alanmi/abc/abc.htm http://www.eecs.berkeley.edu/~alanmi/abc/abc.htm [3] https://www.princeton.edu/~chaff/zchaff.html https://www.princeton.edu/~chaff/zchaff.html [4] http://minisat.se/ http://minisat.se/ [5] http://fmv.jku.at/picosat/ http://fmv.jku.at/picosat/ [6] http://z3.codeplex.com/ http://z3.codeplex.com/ [7] http://research.microsoft.com/en-us/projects/slam/ http://research.microsoft.com/en-us/projects/slam/
- rossjudson 13y agoI get what you're saying about the state explosion problem, but the article specifically calls out the idea of proving a lack of negative behaviors. It seems to me it might be quite useful to be able to prove, for example, that a program never reads memory at random, or that it never exceeds the bounds of any allocated buffer. That's a different problem scale than "prove the whole thing works as specified".
- userbinator 13y agoI think one of the biggest barriers to formal verification is that it is, for lack of a better term, "too formal". There's a bunch of other terminology, language, etc. you have to learn, and the learning curve is steep. For someone who just wants to prove a few pre/post-conditions on some functions (that's why I looked into Coq originally - and gave up because it was too hard), it's too much. There is a feeling that it is too theoretical. I eventually found it easier to prove what I needed to, manually.
- jnbiche 13y agoBingo, unfortunately. I've been able to learn functional programming in Haskell and OCaml without any formal academic background, but looking at Coq, Agda, Idris, and F*, I despair of learning them without more accessible tutorials or a PhD in computer science concentrating on type theory. My first intro to Haskell was through "Learn you a Haskell". I think without that type of introduction, I never would have progressed past basic pattern matching and folds/maps/filters. I need something similar for dependent typing.
- gsnedders 13y agoThere's Learn You An Agda at <https://github.com/liamoc/learn-you-an-agda> https://github.com/liamoc/learn-you-an-agda>, though it never got that far. (I've done comparatively little with theorem provers (v. model checkers), so I can't point you anywhere that useful!)
- solomatov 13y agoAll these tutorials won't teach you how to use coq or agda. The main problem is that in order to use coq or agda, you need to learn Martin-Lof type theory (or calculus of inductive constructions, which is a similar formalism to MLTT) first, and learn to write code later. Otherwise everything will seem like a magic. There are however, good books on the topic: * Type Theory and Functional Programming (http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/) * Programming in Martin-Lof type theory (http://www.cse.chalmers.se/research/group/logic/book/ http://www.cse.chalmers.se/research/group/logic/book/)
- meowface 13y agoI had no idea sqlite put so much effort into testing. 84,300 lines of production code with 91,452,500 lines of testing code is pretty damn crazy. I assume a lot of that code may be auto-generated, but it's still impressive regardless.
- jarrett 13y agoWill formal verification ever be possible for systems composed of a bunch of heterogeneous components working together? I'm thinking of a web application, where the software's behavior depends on the interaction of client-side scripts, stylesheets, server-side programs, databases, caching layers, and probably other components, all operating in the request-response cycle that fragments behavior into a bunch of separate runs of the various programs.
- dkarapetyan 13y agoWhy not? Each of those things can be treated as black boxes with well-defined interfaces.
- gsnedders 13y agoCertainly — it's just another parallel system. This is something things like CSP (Communicating Sequential Processes) — and see FDR2/FDR3 for programmatic verification — excel at.
- Confusion 13y agoFormal verification and testing are not mutually exclusive and should ideally both be used. If you read this article and conclude that formal verification is the way to go and writing tests is unnecessary, then you are failing to appreciate the concessions Metzger makes. Take e.g. but Quark's formal verification doesn't try to show that the entire Web browser is correct, and doesn't need to -- it shows that some insecure behaviors are simply impossible. *Those* are much simpler to describe. Let's assume this is true: we can write interesting programs of relevant size and complexity and prove they are secure. Then we still need a whole bunch of tests to show the program actually does what its users want it to do, because formally specifying that behavior is hard.
- shlomifr 13y agoThis is very relevant in the light of Heartbleed. Core security code should be verified formally, there is no other way to guarantee correctness of implementation.
- dllthomas 13y agoVerified formally, tested, audited, and whatever else we can throw at it.
- jeffreyrogers 13y agoIf my understanding of model checking is correct (which I believe is the primary method of formal verification) I don't think this would help much in the case of Heartbleed. The Heartbleed error had to do with an expression being in the wrong scope if I recall correctly. (I think someone forgot to put brackets around an if statement that contained two expressions). In this case the model would be correct, but the implementation would be wrong. So I don't think formal verification would be of much help. That said, I think there are a number of static analysis tools that would pick up on the error, so a combination of approaches would work. And of course, it would be great if we could verify that our security critical code was sound in theory, even if we can't necessarily verify that our implementation is free of coding errors, so I agree with your main argument. Of course, whether we're at the point where doing this verification is feasible in practice is another matter unto itself.
- vertex-four 13y ago> I think someone forgot to put brackets around an if statement that contained two expressions That was Apple's goto fail. Heartbleed was caused by out of bounds memory access.
- jderick 13y agoIt is also possible to apply model checking or theorem proving directly to the implementation. Doing so would be able to catch any sort of error that a static analysis tool would. Of course, static analysis typically scales better and would be a good place to start for catching this type of error.
- a-saleh 13y agoAs a q/a by profession, I allways wonder, how to have some better assurances that the software I have does what it is supposed to. I believe I have even incidentaly reimplemented quick-check on several occasions. When we were working in Clojure for a little while, I wondered if it might be possible to combine contracts and logic programming, to verify that contracts don't contradict each other on compile ... and then I realized, that for more complex constraints I might need to solve halting problem. On the other hand, I remember how much productivity I gained, after I wrapped our json library in simple macro, that verified that the data I feed it conforms to schema (that was before prismatics schema existed, or even core.typed).
- jderick 13y agoLet me also recommend any interested in theorem proving check out ACL2. It is based on lisp and might be easier to get started with than Coq. There is a pretty cool website that lets you run it in a browser here along with a basic tutorial: http://tryacl2.org/ http://tryacl2.org/