4 ms·
"After I read the book, I've come to understand that general-purpose static type system can never prove unequivocally that a generic program works. That's what
by Animats 5y ago
"After I read the book, I've come to understand that general-purpose static type system can never prove unequivocally that a generic program works. That's what Church, Turing, and Gödel proved."
Oh, not that again. If a program is close to undecidable, it's broken.
Microsoft ran into this with the Static Driver Verifier. If they couldn't prove that a driver could not blow up the kernel after the prover had cranked for a few minutes, the driver is rejected. Really, if you don't have easily proven decidabilty in your device driver, it has no business going into production.
- infogulch 5y agoI'd like to see the industry move towards proof-carrying code. This takes decideability checking one step farther: not only does your driver have to be decideable, you have to prove that ahead of time and include a proof that can be checked in linear-time right along with the binary. At that point even signatures become redundant; you don't need to trust any central authority if you have proof of the programs validity right there.
- Animats 5y agoYou still need some criterion to verify against. The Static Driver Verifier is successful because its criterion is just "will not blither all over memory" or make an incorrect API call. Passing the check doesn't mean the driver will drive the device properly, but it shouldn't crash the kernel. Or offer buffer overflow exploits.
- Joker_vD 5y agoYes, those exactly are criteria that PCC was developed in mind with: "examples of safety properties that are covered in this paper are memory safety and compliance with data access policies, resource usage bounds, and data abstraction boundaries" (from the abstract of [0]). That's what safety is, after all: that something bad does not happen. [0] George C. Necula, Peter Lee. Safe, Untrusted Agents using Proof-Carrying Code. 1998. http://www.cs.cmu.edu/afs/cs/project/pop-10/member/petel/www/publications/lncs98.pdf http://www.cs.cmu.edu/afs/cs/project/pop-10/member/petel/www...
- daxfohl 5y agoIsn't Microsoft still trying to make a proven TLS implementation? If that takes really smart people years and years to do, I don't see much hope for the rest of us on line of business apps.
- infogulch 5y agoYes, choosing the right criteria / spec to prove against is a big task, and one that is not done at all today. Mathematicians sometimes say that fully describing the problem can be more work than actually proving it with a particular solution, and I imagine there's some parallels between that and the criteria vs proof problem you mention here. If there's a biggest problem it's that nobody cares about a good spec so nobody will pay for it.
- pjmlp 5y agoFor that to happen the industry needs to care more about quality, and that will only happen when liability becomes a real thing across the industry and not only in highly critical software.
- deleted 5y ago[deleted]
- dkersten 5y agoI think it also dosen't really matter, in practice. While it would be nice to have a language where, if it compiles, its provably correct (for some definition of correct, defined by whatever the language states, I guess), we don't need that extreme to be useful. I've personally found myself dissatisfied with dynamically typed languages after spending the bulk of the past ten years writing in them (Clojure and Python mainly), because the kinds of errors that I most commonly find in my own code are ones that even basic static types like in Java or even C++ can detect (basic type mismatches) while in dynamic languages, to catch these early, the unit tests need to have exercised that particular case. The problem with that is it puts the burden of thinking of and testing for these cases on me, but we all know that exhaustive tests are rare and hard to maintain. Property-based testing helps, but again, it depends on the data generated whether or not a type mismatch will get tested. Statically typed languages prevent this type of bug, this makes them useful to me, even if they can't prove the absence of all bugs or can't prove that a program won't halt.
- naasking 5y ago> Really, if you don't have easily proven decidabilty in your device driver, it has no business going into production. In other words: "Every system is either so simple there are obviously no errors or so complex there are no obvious errors." ~ Hoare