3 ms·
> The other 10-20% can be difficult or impossible. Can you explain why a model checker would fall short of the last 10-20%?
by pron 11y ago
> The other 10-20% can be difficult or impossible.
Can you explain why a model checker would fall short of the last 10-20%?
- nickpsecurity 11y agoSorry for late reply. Don't take the number literally: it was a play on something Dr Schell used to say (example in [1]). He pointed out the reason GEMSOS and A1 class included formal verification was to get the last bit of assurance done. The tests proved the presence of specific issues. The model checkers and provers were meant to prove absence of issues. Model checkers often did a search through a number of states checking for invariants but were often limited due to state explosion. So, provers had to be used to show a given design implemented given policy or invariants in all situations. Additionally, show that a refinement to more concrete form preserved equivalence. This is hard work. The lessons learned in 70's and 80's showed you could only do it once you had good mathematical formulations of certain concepts. That explains why the effort vs defects found varied considerably among projects. The other aspect that all of them discovered was the design or code had to be built with verification in mind. As in, certain implementation details were easy to modify, translate, etc while others were either difficult or impossible. You could use model checkers, traditional methods, etc to get pretty far in your assurance argument, maybe even 90-99%. That last bit that fell out of range of tools due to their problems or your implementation choice might be impossible gap to close. So, the highest assurance argument took a combination of strong specs/models, proofs of invariants on all use-cases, minimization of state/complexity in general, and easy-to-analyse implementations. You can actually see this in action if you look at the layering/composition of GEMSOS [1], PSOS [2], KSOS [3], and VAX security Kernels [4]. CompCert's compiler passes applied [5] same rules of thumb. I still say use lighter methods if you have to or can get away with it. There's been a number of software that used model-checking with success at finding flaws and a decent assurance argument. The problem was that they often require you to extrapolate what happens with small amount of states, data, or time to potentially huge amounts. Experience shows many things break down as load intensifies. So, I'd rather know it works in all states. And that's the last piece of assurance case that might be impossible to reach if you didn't design for it from the start. Hope this helps. [1] http://www.iwia.org/2005/Schell2005.PDF http://www.iwia.org/2005/Schell2005.PDF [2] http://www.csl.sri.com/users/neumann/psos.pdf http://www.csl.sri.com/users/neumann/psos.pdf [3] https://c59951.ssl.cf2.rackcdn.com/5085-1255-perrine.pdf https://c59951.ssl.cf2.rackcdn.com/5085-1255-perrine.pdf [4] http://www.cse.psu.edu/~trj1/cse543-f06/papers/vax_vmm.pdf http://www.cse.psu.edu/~trj1/cse543-f06/papers/vax_vmm.pdf [5] http://compcert.inria.fr/ http://compcert.inria.fr/