Earlier quoted context omitted.
The state explosion problem is becoming less of an issue in software nowadays because of the massive improvement in SAT/SMT solvers. The topic of this post is not about model checking, but I believe still interesting. One big improvement when it came to verification came from symbolic execution [1], in which the verifier looks for assertion violations by representing variables as a set of constraints. At each asserti…
> A more recent improvement has been to unwind loops a bound number of times, encoding the whole program as a logical statement that is only satisfied by input that will trigger an assertion error. The technical term for this is bounded model checking (BMC).
The Case for Formal Verification (2013)
101–110 of 113 posts
Re: The Case for Formal Verification (2013)
#102Earlier quoted context omitted.
I 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…
I'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-photo... When I read about that bug in the past, I thought "this would be a great example to use for Alloy".
[0] http://www.doc.ic.ac.uk/project/examples/2007/271j/suprema_o...
Re: The Case for Formal Verification (2013)
#103Relevant: 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.
Re: The Case for Formal Verification (2013)
#104Earlier quoted context omitted.
Ok, so in retrospect I didn't mean that for OCaml. Certainly it is true for Standard ML [1, 2, 3], or rather, the parts of the language that use the underlying native code (IO etc) are generally smaller pieces of code for which the correctness properties are hopefully more easily tested and verified. In any case, I believe my point still stands on the whole :) [1] http://www.cl.cam.ac.uk/teaching/1314/FoundsCS/fcs-no…
friends of mine have still segfaulted mlton-compiled SML programs. as I understand it, you need to have a bisimulation-based proof that shows equivalence in states between ML and x86, and as far as I know that just hasn't been done. until then you have the risk of a bug in some aspect of the compiler, which has happened, emitting code that produces a crash or something else bad.
Re: The Case for Formal Verification (2013)
#105Earlier quoted context omitted.
Of course, one will attempt to also find equivalence classes for the states! The code long x = user_input(); if (x == 0) { violate_model(); } else { do_something(); } you would expect by any reasonable implementation to collapse the system into just two equivalent states that can be tested.
Ah, but finding equivalence classes of states is quite tricky! Obviously the naive approach of enumerating states and assigning them to equivalence classes is dead on arrival. You might be hinting at examining control flow predicates with your example. This technique is called predicate abstraction and underlies a lot of the SLAM effort. It works in certain scenarios - A statement which more or less captures the stat…
It works quite well for short programs, actually - the KLEE people (or maybe it was DART) found bugs in busybox, GNU Coreutils etc.
The current approach is to instead of traversing your control flow tree explicitly (which means you're doing a tree search over a potentially infinite tree), converting the program such that it produces a logical statement that can be solved by an SMT solver, that is satisfiable iff there is an input that leads to a bug within that bounded number of loop unwindings.
With fun C++ metaprogramming, you can actually get this to happen natively (i.e. the parts that aren't reliant on input get run natively) which leads to a massive speedup o
I don't believe it to be model checking, although it might use model checking techniques. I could be wrong, I'm only familiar with a few aspects.
Re: The Case for Formal Verification (2013)
#106Earlier quoted context omitted.
friends of mine have still segfaulted mlton-compiled SML programs. as I understand it, you need to have a bisimulation-based proof that shows equivalence in states between ML and x86, and as far as I know that just hasn't been done. until then you have the risk of a bug in some aspect of the compiler, which has happened, emitting code that produces a crash or something else bad.
My first opportunity to whip this one out :) https://cakeml.org/popl14.pdf
Re: The Case for Formal Verification (2013)
#107Earlier quoted context omitted.
The 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 appr…
Why 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 alon…
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.
Re: The Case for Formal Verification (2013)
#108Can someone explain why CompCert is not more popular? A formally verified compiler seems to be much more useful than something that can produce bugs.
In the second form above, main is called with argc equal to zero and argv equal to the NULL pointer. The program does not, therefore, have access to command-line arguments.
Re: The Case for Formal Verification (2013)
#109Earlier quoted context omitted.
If 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 imp…
It 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.
Re: The Case for Formal Verification (2013)
#110Coq 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 har…
I'd love to use proofs that my software is good; but after reading the 43 page "coq in a hurry" document, I still have no idea how to prove that "print 2 + 2" prints out "4", let alone how to apply it to any of my real world apps :( Mostly it seems formal proof stuff looks a lot like my memories of the functional programming world -- lots of one-letter variable names and unicode symbols, no code comments, any word th…