6 ms·
A shallow survey of formal methods for C code
- Grothendieck 12y agoThe current version of the ATS language apparently uses libgmp to avoid the mentioned overflow issue: http://sourceforge.net/p/ats-lang/mailman/message/30692243/ http://sourceforge.net/p/ats-lang/mailman/message/30692243/ .
- minopret 12y agoCompCert is formalized in Coq. It looks possible to represent one's own C source code and its intended behavior using CompCert's proof development. I would not at all suggest that it's easy. Also, CompCert sources are offered only for non-commercial use. http://compcert.inria.fr/doc/index.html http://compcert.inria.fr/doc/index.html
- pascal_cuoq 12y agoThe definitions of the semantics of both the input language and the output language of CompCert are operational. If you want to prove functional properties of programs written in the input language with respect to CompCert's definition, you will probably have to define Hoare-Floyd-style axiomatic semantics and then prove that this definition is equivalent to the operational semantics definition. An informal version of this proof for a toy language already exists in good textbooks (for instance Winskel's The Formal Semantics of Programming Languages). It is just a matter of scaling up to C and scaling down to the formally verified level. I should also point out that there is an ongoing research project that takes the same approach, with “Abstract-interpretation-based static analysis” instead of “verification of functional properties”: http://verasco.imag.fr/wiki/Main_Page http://verasco.imag.fr/wiki/Main_Page
- yoran 12y agoI find formal methods fascinating. To be able to say, no matter what the input is, this thing does exactly what it is supposed to do, is great. I wonder if one day we will be able to use a lighter version of formal methods to web development. I like the concept of Design by Contract, where you specify the pre- and post-conditions and invariants of a function, and it would already be a great step if it would be possible to prove the correctness of individual functions. Kind of the ultimate way of unit testing. I'm wondering how suited (or ill-suited) a language like Javascript is for applying formal methods on it. It's certainly not as "mathematically sound" as a language like Haskell, but then again, if it's possible to apply formal methods on C, then it should be possible to apply formal methods to Javascript too. I'm curious about research happening around this.
- tizoc 12y ago> I wonder if one day we will be able to use a lighter version of formal methods to web development. https://en.wikipedia.org/wiki/Type_system#Type_checking https://en.wikipedia.org/wiki/Type_system#Type_checking
- dons 12y agoMight be a reasonable fit for Cryptol?
- axman6 12y agoSeems everything is a fixed size so it probably would be an excellent fit. You'd probably also get constant time guarantees with Cryptol too right? From memory it wasn't too happy to do anything where the runtime varied.
- pbsd 12y agoSMT solvers have been getting better and better, but they still fail at relatively simple things. I often use them to prove certain low-level optimizations are correct, and sometimes simple things completely choke the solver. The following is a simple example of a popcount implementation, relatively easy to prove correct by a human, but that Z3 (and presumably others, but I haven't tried) is unable to solve in a reasonable amount of time. Using z3py for convenience: from z3 import * def popcount1(x): return Sum([ ZeroExt(6, Extract(i,i,x)) for i in range(64) ]) def popcount2(x): return Extract(6, 0, -Sum([ RotateLeft(x, i) for i in range(64) ])) x = BitVec("x", 64) prove(popcount1(x) == popcount2(x))
- axman6 12y agoIs that second implementation in Hacker's Delight? Also it'd be interesting to see how z3 handles the examples shown there too (the logarithmic time algorithms using x' = (x & b10101010) >> 1 + x & b01010101 x'' = (x' & b11001100) >> 2 + x' & b00110011 or whatever it is)
- pbsd 12y agoNo: Z3 proves the Hacker's Delight* trick almost instantly. The implementation above is not actually faster in practice, so it's rarely used; but its equivalence to popcount relies on Z/2^64Z properties that solvers do not seem familiar with. * This sort of trick is much older than Hacker's Delight, by the way; Knuth tracks it down to the 1950s in Volume 4A.
- TheLoneWolfling 12y agoThis is slightly tangential, but ah well. Thinking of a hypothetical OS here. As much of the OS as possible, and all userland components are bytecode. This bytecode is split into two categories - "safe" bytecode, where none of the operations could cause issues (read: runtime arrays bounds checks, that sort of thing), and "unsafe", which includes a formal proof of "correctness" - that is, a formal proof that it doesn't access memory it hasn't initialized, etc, which the compiler checks for correctness. (Note: the kernel does not do any attempt at making a proof, "just" checking it) The kernel compiles bytecode to machine code before execution, with caching as appropriate (similar to how Python handles compilation, for example). The advantage here is that you can end up running native code everywhere (and also potentially not having to worry about usermode <-> kernel switches, memory segmentation, etc), without having to worry about malicious code. Also, it'll be a lot easier to port. Yes, it's going to be slower. (Although some of that may be offset by lack of context switches and not having to be paranoid about kernel arguments, etc. Considering that the attack surface is small ("just" the bootstrap code and bare-bones HAL), it may be possible to just run everything in ring 0 / cooperative multitasking / flat memory model.)
- jws 12y agoLayers are useful for containing failures. What will happen when you get an undetected memory read error? A precondition of the proofs just left.
- TheLoneWolfling 12y agoHmm. Yeah, that would be a problem, wouldn't it. There are failures that cannot be proven to not occur at compile time, namely, as you mention, hardware errors. ECC will prevent some of these, but not all. So perhaps it should still be layered at the hardware level. (Reminds me of the JVM exploit that relied on waiting for random bitflips in RAM.) (Of course, this is a problem for traditional OSs as well, although the vulnerable area of memory (ring0 data structures / stack / etc) is smaller.) I wonder. It might be possible to express some of that in the proof requirements - "this program must not write to memory owned by another process even if a single bitflip occurs anywhere" - although that would probably balloon the complexity of the proof.