4 ms·
Here's a recent survey of some work: https://courses.cs.washington.edu/courses/cse551/15sp/projects/qz2013-danyangz-jrw12.pdf https://courses.cs.washington.edu
by nickpsecurity 10y ago
Here's a recent survey of some work:
https://courses.cs.washington.edu/courses/cse551/15sp/projects/qz2013-danyangz-jrw12.pdf https://courses.cs.washington.edu/courses/cse551/15sp/projec...
Let's look at numbers of some to see what happens:
1. Jitk. In-kernel interpreter for firewall rules. 2300 lines spec, 3510 lines code.
2. ExpressOS. Uses C# and verifiable Dafny language with annotations that feed into prover. The annotations were 2.8% of code.
3. seL4. This is kind of project that makes it seem like specs and proofs are huge. That's cuz people forget what they're specifying: an abstract CPU + imperative programming + kernel + safety/security properties + equivalence. Writing that in code also takes a lot of lines but they didn't have to in C past kernel. Anyway, this one is (a) for executable spec 5,700loc Haskell + 13,000loc Isabelle and (b) for implementation 8,700loc of C/ASM + 15,000loc Isabelle. They went full proof instead of code review. That added 200,000Kloc of proof steps with a good chunk automated.
4. VCC on Microsoft Hyper-V. Similar problem to 3 where this manages a CPU/machine. Total size was around 100,000loc last I checked. Verifying 20%... 20,000loc... took 13,500loc annotations. Verification automated.
5. Verdi protocol verifier. Spec/code reported is: Key-value store 41/138; Primary-backup 20/134; Raft algorithm 170/520; Verdi itself 148/220. Always smaller in its specs.
So, it's clear that the specs range from being tiny to smaller than code in most cases with heaviest, hardest efforts taking more specs. Proofs range from automated to manual.