News for hackers. Stuff that matters.
Re:Formal Verification Creates Hacker-Proof Code by nabla9 on Friday October 21, 2016 @01:03PM (#12762238)
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.

Re:Formal Verification Creates Hacker-Proof Code by nickpsecurity on Friday October 21, 2016 @01:27PM (#12762514)
"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....

Re:Formal Verification Creates Hacker-Proof Code by nabla9 on Friday October 21, 2016 @01:54PM (#12762836)
What 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.

Re:Formal Verification Creates Hacker-Proof Code by nickpsecurity on Friday October 21, 2016 @02:02PM (#12762927)
I 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."

Re:Formal Verification Creates Hacker-Proof Code by nabla9 on Friday October 21, 2016 @02:22PM (#12763133)
>I think you should describe what counts as a theoretical breakthrough to you

It would be some new idea in proof theory that would produce significant reduction of required manual work in practical applications, making it easier for humans to work out the proofs and proof assistants help humans.

Linear logic, affine logic, etc. can provide incremental advantages, not breakthroughs.

Re:Formal Verification Creates Hacker-Proof Code by philipkglass on Friday October 21, 2016 @01:14PM (#12762368)
I 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.
Re:Formal Verification Creates Hacker-Proof Code by nickpsecurity on Friday October 21, 2016 @01:32PM (#12762575)
The 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/...

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/...

Re:Formal Verification Creates Hacker-Proof Code by sliverstorm on Friday October 21, 2016 @05:54PM (#12765225)
Aren't microprocessors Turing-Complete machines that undergo formal verification?
Re:Formal Verification Creates Hacker-Proof Code by nickpsecurity on Friday October 21, 2016 @06:53PM (#12765598)
The 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. :)

Re:Formal Verification Creates Hacker-Proof Code by nabla9 on Friday October 21, 2016 @01:39PM (#12762660)
In 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.