5 ms·
sel4 shows that an endgame is possible wrt to memory safety, it's formally verfied to be memory safe. It's sitting at ~25 to 1, proof code to implementation co
by monocasa 8y ago
sel4 shows that an endgame is possible wrt to memory safety, it's formally verfied to be memory safe.
It's sitting at ~25 to 1, proof code to implementation code. I think you could probably get that down to 5 to 1 or so by treating a lot of the work they did as a library. The proof covers a full equivalence from abstract spec to machine code, and you could reuse a lot of that. Sort of how it's not fair to include the LOC of your compiler even though you need that for your program ultimately.
- chillacy 8y agoBut does formal verification even help when you're up against side channel attacks on the hardware? Like the branch predictor or DRAM memory access timing.
- monocasa 8y agoWith a model of the full system, quite possibly. That's one of the things that makes me so excited for RISC-V.
- sempron64 8y agoI don't know of any technique to model or avoid timing attacks that wouldn't drastically slow down execution to the point of being impractical.
- deleted 8y ago[deleted]
- xiphias2 8y agoReinforcement learning can be used to improve theorem proving, but it probably needs more research: https://arxiv.org/abs/1805.07563 https://arxiv.org/abs/1805.07563
- rurban 8y agoNope, sel4 is unsafe against modern Spectre/Meltdown attacks. Only Fiasco was recently made safe against these. Secondly, Microsoft's own SecureMemZero is insecure against those attacks. It only applies a trivial compiler barrier, but no memory barrier, so you cannot use it to securely delete sensitive memory.
- pron 8y agoThat's not an endgame if the resources required to block an attack are significantly greater than those required to make one. Moreover, verification is done with respect to specific properties that ensure no attacks of a particular kind. The more kinds of attacks you need to defend yourself from, the harder you need to work (and you will miss some). Not saying we're not making steps in the right direction, but no one thinks it's an endgame.
- monocasa 8y agoIt's an endgame wrt to memory safety (like I said). sel4 is memory safe. All the other mitigations like ASLR, canaries, etc are just hacks around the fact that proving memory safety of existing codebases is a Sisyphean task. And getting down to 5/1 proof to implemention is within the realm of what unit tests you should be writing anyway, so it's not that much of an economic investment.
- pron 8y agoI am not at all against formal verification. In fact, I evangelize it and use it myself quite a bit. But it is important to understand that it is very, very far from being a miracle cure. All software proofs prove correctness of specific theorems about a program given certain axioms. Those axioms must include, at the very least, the conformance of the hardware to some specification. But hardware can, at best, conform to the specification with some probability. For example, when you write `mov rax, [rdx]` it is not true that the computer will, 100% move the contents of the address pointed to by rdx into rax, only that it will do so with some high probability. Therefore, any proof about a software system (as opposed to an algorithm, which is an abstract mathematical entity) is a proof of a theorem of the form, "as long as the system behaves according to my assumptions, it will exhibit behaviors consistent with my conclusions." And that is even assuming that your conclusions cover all possible attacks. As it is generally impossible to formalize the concept of an arbitrary attack, you generally prove something far weaker. But none of this is even the biggest limitation of formal verification. The biggest would be its cost and lack of scalability. seL4 is about 1/5 the size of jQuery, and it is probably the largest piece of software ever verified end-to-end using deductive formal proofs as a verification technique. However much the effort of a similar technique can be reduced, it doesn't scale linearly with the size of the program (it may if the program does the same things, but usually larger programs are much more complex and have many more features).