3 ms·
No new breakthroughs in formal proofs or deriving programs, just incremental progress. The cost of formal methods stays high. The high cost means that it does
by nabla9 10y ago
No new breakthroughs in formal proofs or deriving programs, just incremental progress. The cost of formal methods stays high. The high cost means that it does not work well with iterative programming, or changes in specs.
So far only some military and safety critical applications and parts of Intel's silicon have been worth of the cost.
I took my first course in formal methods using the book Programming: The Derivation of Algorithms by A. Kaldewaij. It would be perfectly reasonable to implement something similar to Kaldewaij's guarded programming language today over some other programming language and use it to derive formally proven programs if someone really values the correctness. It would be also cool and fun but not for everyone.
- philipkglass 10y agoI hope that one of these days (years?) we might start seeing formally verified versions of code for dealing with standards that don't change rapidly and that have proved to be security problems in the past. I'm thinking of things like font rasterizers, TIFF readers, full PDF readers, and JavaScript engines intended for browsers.
- nickpsecurity 10y agoThe problem with many of these formats is they're Turing-Complete languages with input driving what they do. The input is also malicious. So, the solution so far is to isolate and mediate such things with verification going into the mechanisms for that. An example of one for exactly your types of programs is Microsoft's Xax: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/xax-osdi08.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... My preferred approach is the old-school method of highly-assured microkernels that just separate everything else from one another. Here's a browser OS based on that principle: https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Tang.pdf https://www.usenix.org/legacy/event/osdi10/tech/full_papers/...
- sliverstorm 10y agoAren't microprocessors Turing-Complete machines that undergo formal verification?
- nickpsecurity 10y agoThe kind of verification they undergo varies considerably. The amount of errata in modern CPU's shows both they're not fully verified for correctness and that the verification they get works wonders given number of components & interactions. Even if fully verified, the verification would be that the Turing-Complete hardware properly implemented a model of the Turing-Complete hardware. That kind of buys us nothing in terms of whether we'll know if programs are malicious or contain them, eh? And look at the giant, losing game that followed between the mice and the well-fed cats. It's why safety-critical systems often used deterministic, state-machines running on simple MCU's or PLC's. :)
- nabla9 10y agoIn the examples you mention (document readers) the bugs become security problems because programs have too much privileges. Easiest way to remove security problems is not to remove bugs, but remove privileges. Privilege revocation, privilege separation, W^X work wonders. Protocols like https, ssl and cryptography and operating systems would be my first choices.
- nickpsecurity 10y ago"No new breakthroughs in formal proofs or deriving programs, just incremental progress. The cost of formal methods stays high. The high cost means that it does not work well with iterative programming, or changes in specs." That's a load of crap. SPARK lets you practically throw together embedded programs with code-level proofs. CompCert was a huge leap over the non-optimizing, toy compilers that came before it. CRYPTOL specified algorithms at high level with C generation. LANGSEC is automating secure parsers. Another did protocols. The seL4 project included AutoCorres that can pull HOL specs right out of C projects. Verisoft gave us a full stack with processor (VAMP), C-like language, compiler, OS, and apps. Myreen and Davis have verified ASM, LISP, ML, extraction, provers, and hardware. Rockwell-Collins has a flow from Simulink models to specs and SPARK code for their mathematically-secure AAMP7G. Recent work verifies non-interference and other properties down to the gates. There's been a ton of work knocking out whole categories of problems with no effort followed by other work that lets us do full verifications with a fraction of prior effort. You should read up on successes like those before claiming nothing has been going on. Heck, lets skip to one of the best where non-experts verify an ext2 filesystem in fraction of the labor it took to do seL4: https://ts.data61.csiro.au/publications/nictaabstracts/8956.pdf https://ts.data61.csiro.au/publications/nictaabstracts/8956....
- nabla9 10y agoWhat you describe is software tool chains that can take formally verified (or partially verified) code and spit out lower level code that is also formally verified. There is no theoretical breakthrough there just lots of new tools. Actually writing that code is still slow process.
- nickpsecurity 10y agoI think you should describe what counts as a theoretical breakthrough to you. The rest of us seem to think that writing some flowcharts or nearly English code in 10 minutes with a verified application coming out is a mix of great advances in theory and tooling over the years. Sure didn't do that in the COBOL days. Another example is the K framework where they just use rewrite rules in a decidable logic with some supported tooling. That specific theory, their logical strategy, let them do a whole semantics for C with undefined behavior included in just a few thousands lines of specs. In form of KCC, it can also be used as a compiler. The oldest one, from co-inventor of software engineering, let you specify functional, structural, and resource requirements in a logical notation with the tool synthesizing about everything else for you. That was 001 Tool Suite. The thing is, I can only imagine tools getting much better than that because any development will require human brains turning problem descriptions, constraints, etc into precise statements. Which is what specs are. That we're already at spec-to-code synthesis and proof for some of these tools seems like something that can't be hand-waived away as "no theoretical breakthrough there just lots of new tools."