21 ms·
How Did Software Get So Reliable Without Proof? (1996) [pdf]
- intrasight 11y agoHow did living things get so reliable without proof?
- pmiller2 11y agoLiving things aren't very reliable. They don't last very long, in general, and their replication mechanism is highly error-prone.
- mitchtbaum 11y agoI get that we have mouths, vocal chords, lungs, brains, etc. It simply shocks me that some fellow humans use them to ridicule those things.. Once machines start making fun of us as they heal themselves (something we can do too.. go Life), I believe I'll get their humor, or what have you. I wonder if with their "big brains" some of them will still feel so inclined to speak unkindly about Earth's chemicals and processes that their bodies use.
- deleted 11y ago[deleted]
- ktRolster 11y agoNeither is software, for that matter.
- humbledrone 11y agoThat's an extremely narrow view of life. A broader view might be that life on Earth began a few billion years ago, and has managed to hang on ever since. Do you realize that you are, most likely, the direct descendant of one of those early lifeforms? Every single one of your ancestors, for billions of years, has managed to produce viable offspring in an unimaginably long chain of living organisms. How can you call that unreliable? Sure, bits of your DNA are being corrupted every second. Sure, tens of billions of your human cells die and are cast away each day. And, sure, each agglomeration of cells we call a human only lasts a few tens of years. But life has enough redundancies, contingency plans, and diversity that it will in all likelihood keep going for a long, long time. Having a single instance of a particular organism last for a long time just isn't what life is about. If you look at the full context of what life is doing, it is way goddamn more reliable than anything humans have designed, proofs or not.
- pmiller2 11y agoI agree with your argument as far as it goes, but if you're responding to me, you're making a straw man argument. I was saying that living things (i.e. individual organisms) aren't very reliable; you're saying that life is very resilient. That's a true statement, but utterly non-responsive to the point I was making.
- taneq 11y agoIndividual organisms are incredibly reliable when you consider the range of functions they perform. Compare, say, a quadcopter drone (or any other small air vehicle) with a parrot. Lifespan without service or repair? Drone, weeks. Parrot, decades. Autonomy before recharging/refueling? Drone, 20 minutes. Parrot, hours to days. Cognitive faculties? Drone, slim to none. Parrot, long term autonomous in complex environments. Reproduction? We can't build things that do that at all yet, let alone pack one into a 1kg autonomous aircraft. Yes, we can build simple machines to replicate one function of a living creature, and those machines will be more reliable over short durations, but only because they are orders of magnitude simpler. You might as well call an LCD screen "unreliable" because it won't outlast a photograph.
- nnq 11y agoFrom modern evolutionary biology's perspective "individual organisms" are NOT the "basic units/modules etc." of life. The basic ones are genes at the core informational level level and species at more loose and macro level. So the living things to software analogy would be more like: - gene == source code of a program's module (like an "independently testable unit of code" - natural-selection + sex-based recombination are actually the tests) - ... (organizational levels with with no direct analogy to software go in between) - individual organism == set of processes (running instances of programs) running together with heavy inter-process communication Then at a higher level, genes and their manifestations constitute the "hardware" (more like a VM), run the software called "memes", with its own organizational patterns that are outside the field of biology. What you call living thing or individual organism is, from "life's perspective", closer to a transient group of running processes that can be killed at any time because their sources and binaries are safely stored as genes or memes. Your body and your psychological self are closer to "running threads of nginx on a particular server handling a particular set of requests" than to "the program nginx itself" in source or binary form :)
- landryraccoon 11y agoCompared to what? Some trees are very old. There's a bristlecone pine tree in California that has been around since before man knew how to smelt iron. What reproduces better than living things? Virtually nothing made by human beings is expected to last that long, let alone something as complex and intricate as a tree is. Some buildings, by luck and continuous maintenance, may last as long - but they don't self reproduce and only stay standing through massive ongoing repair.
- pmiller2 11y agoTrue enough, but for every bristlecone pine or ancient yew tree, there are billions of bacteria that live mere days and insects that live a few weeks or months. In addition to vastly outnumbering them, I would wager that all the insects and bacteria of the world probably outweigh all the 500+ year old trees currently in existence.
- mc808 11y agoTo really stretch the analogy, there are also millions (perhaps billions) of short-lived, abandoned software projects that never grew into something big and reliable. They're less interesting because it's usually pretty obvious why they failed.
- gozur88 11y agoOh? We don't even begin to have the technology to create a self-replicating, self-repairing machine that can be expected to last 70 years or so of active service. One that slowly gets better over time as the error-prone replication turns up the odd improvement.
- jacquesm 11y agoYou should not look at 'life' as single organisms but as a system of organisms and as such it is very reliable. Once it started it lasted for billions of years, and over time managed to exhibit an extreme shift in complexity using roughly the same basic mechanisms. The only things we've made that are more reliable than life are buildings that don't move (and are still prone to catching fire every now and then), anything with moving parts needs constant maintenance to get even a couple of years of use out of it.
- pron 11y agoThe answer to a slightly different question is quite simple: how did life get so reliable? First, we should define what it is that it is reliable at. Particular organisms are, of course, far from reliable, but if we look at life as a whole, it is very reliable in doing one thing: ensuring that at any time there's at least a single copy of the program (genetic matter) that is in a runnable condition. How is it so reliable at that? 1. The goal is rather simple. 2. The time and energy (the computational effort) required to arrive at that first viable self-replicating molecule was huge. 3. The computational effort of the constant required maintenance is also similarly huge.
- intrasight 11y agoThank you for understanding. Both the OP's and my question are interesting. Considering both together is sublime.
- DawkinsGawd 11y agoLife is not reliable.
- gefh 11y agoIt turns out software was only reliable in the dimensions we we carefully looking at. I'm not sure 'proof' would have helped any - we might well have proved that, say, Flash could successfully display any valid animation you could throw at it without even thinking about whether it was also pwning your machine.
- Sanddancer 11y agoProofs in software are more complicated than that. For something like flash, you could have proofs that it handles corrupt, either intentionally or unintentionally, data without blowing up. Then again, I'm one to believe that we need to focus more on capabilities systems, and other ways to ensure applications can only do what they want to do. Look at something like the rowhammer attack. Being able to break out of a sandbox through completely valid code is something we should be looking at mitigating as well.
- gefh 11y agoRowhammer is a great example of something that a perfectly reasonable looking proof would have missed!
- lmm 11y agoMost of the security vulnerabilities involve C undefined behaviour. Any proven-correct program necessarily won't invoke undefined behaviour. (We could also have used memory-safe languages)
- raverbashing 11y agoCorrect, but "undefined behaviour" sometimes mean "defined by machine" I mean, pretty much the same way as int or size_t has a machine type size dependency
- lmm 11y agoNot true in theory or in practice. "Undefined behaviour" has a specific meaning in terms of the C standard, distinct from "implementation-defined behaviour" like the size of int or size_t. And in practice, writing beyond the bounds of an array almost always leads to arbitrary code execution (remote in the case of a networked program), double free almost always leads to arbitrary code execution, signed integer overflow on newer compilers sometimes leads to arbitrary code execution, ...
- Retra 11y agoAll programming is proof. You just don't often know what exactly it is you're proving. Anyway, the point is moot: software is not that reliable. It's good at the common case, and is very brittle at the edge cases. That's my experience anyway.
- trentmb 11y agoI was a math major and while trying to get a job in programming I got asked how I felt my skills in mathematics would transition to programming- The language (spec) is my set of axioms, the standard library existing theorems, and my program the proof. It's kinda drab now that I think about it, but for a 'firing from the hip' answer I still stand by it.
- qohen 11y agoNot so drab -- that sort of thinking can lead to a pretty big deal, namely, the Curry-Howard Isomorphism[0]. From the linked WP page: In other words, the Curry–Howard correspondence is the observation that two families of formalisms that had seemed unrelated—namely, the proof systems on one hand, and the models of computation on the other—were, in the two examples considered by Curry and Howard, in fact structurally the same kind of objects. If one now abstracts on the peculiarities of this or that formalism, the immediate generalization is the following claim: a proof is a program, the formula it proves is a type for the program. More informally, this can be seen as an analogy that states that the return type of a function (i.e., the type of values returned by a function) is analogous to a logical theorem ... and that the program to compute that function is analogous to a proof of that theorem. This sets a form of logic programming on a rigorous foundation: proofs can be represented as programs, and especially as lambda terms, or proofs can be run. (Of course, in the context of those job interviews you mentioned, this sort of thing would probably be overkill, unless the job involved functional-programming...in which case, though, they might well not have asked you how your "skills in mathematics would transition to programming" in the first place :-) ). [0] https://en.wikipedia.org/wiki/Curry–Howard_correspondence https://en.wikipedia.org/wiki/Curry–Howard_correspondence
- DawkinsGawd 11y ago
- seanwilson 11y agoThe paper is talking about rigorous formal mathematical proofs of correctness like in the sense of of the seL4 kernel (https://sel4.systems/Info/FAQ/ https://sel4.systems/Info/FAQ/) where they have confirmed the kernel is completely free of bugs such as buffer overflows, null pointer exceptions, use-after-free, etc.
- ktRolster 11y agoOf course, there might be bugs in the specification (the proof the made was that the kernel matches the specification)
- seanwilson 11y ago> Of course, there might be bugs in the specification (the proof the made was that the kernel matches the specification) Nothing is perfect, but this approach catches more bugs than any other technique. Also, some specifications are simple to specify e.g. it's not hard to specify that an array index must be within the bounds of the array and if you did get this wrong you'd notice quickly as you'd be unable to prove obvious facts are correct.
- ktRolster 11y agobut this approach catches more bugs than any other technique Have you seen the specification for sel4? It's fairly complex.
- plugnburn 11y agoSystems for processing highly classified governmental/military confidential information often are required (depending on the country laws) to provide formal proof of their entire work. Other than that (and because it is too expensive to run such an analysis) people just need to look at the code to check whether it's doing what it's supposed to do.
- pron 11y ago> Specialisation involves a deep commitment to a narrow selection of presentation, reasoning methods, paradigm, language and application area, or even a particular application. The whole point of the specialisation in formal methods is to restrict the notational framework as far as necessary to achieve some formal goal, but nevertheless to show that the restrictions do not prevent successful application to a surprisingly wide range of problems. This is the reason why specialist research into formal methods can run the risk of being very divisive. An individual researcher, or even a whole community of researchers, becomes wholly committed to a particular selection of specialisations along each of the axes: say an operational or an algebraic presentation of semantics, bisimulation or term rewriting as a proof method, … The attraction of such a choice can be well illustrated in certain applications, such as the analysis of the alternating bit protocol or the definition of the stack as an abstract data type. The perfectly proper challenge of the research is to push outwards as far as possible the frontiers of the convenient application of the particular chosen formalism. But that is also the danger: the rush to colonise as much of the available territory can lead to imperialist claims that deny to other specialisms their right to existence. Any suggestion of variation of standard dogma is treated as akin to treason. This tendency can be reinforced by the short-sightedness of funding agencies which encourage exaggerated claims to the universal superiority of a single notation and technique. > The consequences of the fragmentation of research into rival schools is inevitable: the theorists become more and more isolated, both from each other and from the world of practice, where one thing is absolutely certain: that there is no single cure for all diseases. There is no single theory for all stages of the development of the software, or for all components even of a single application program. Ideas, concepts, methods, and calculations will have to be drawn from a wide range of theories, and they are going to have to work together consistently, with no risk of misunderstanding, inconsistency or error creeping in at the interfaces. One effective way to break formal barriers is for the best theorists to migrate regularly between the research schools, in the hope that results obtained in one research specialisation can be made useful in a manner acceptable by the other. The interworking of theories and paradigms can also be explored from the practical end by means of the case study, chosen as a simplified version of some typical application. In my view, a case study that constructs a link between two or more theories, used for different purposes at different levels of abstraction, will be more valuable than one which merely presents a single formalisation, in the hope that its merits, compared with rival formalisations, will be obvious. They usually are, but unfortunately only to the author.
- taneq 11y ago"Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth
- seanwilson 11y agoSurely code you haven't proved correct is going to have way more bugs in it than code you tried to prove is correct? Maybe I'm misunderstanding but this quote is always posted as if it's some kind of rebuttal against formal methods.
- jon-wood 11y agoI think the point he was making is that while its been proven to correctly do what it was built to do, that may not actually be anything like what the user needs it to do. How many intricately specified software projects have failed because the spec bore no correlation to user needs?
- DawkinsGawd 11y agoI always thought that correctness (in computer science) only asserted that an algorithm acted as specified. For example, say the specification was: The input accepts an element in the set of real numbers, and the corresponding output is that number added to the next element in the set of natural numbers. If this algorithm is used to dispense some type of medication, and I enter 3.1 and it murders you with 10 grams of alprazolam... well.... the algorithm is still correct.
- seanwilson 11y ago> I always thought that correctness (in computer science) only asserted that an algorithm acted as specified. For example, say the specification was: The input accepts an element in the set of real numbers, and the corresponding output is that number added to the next element in the set of natural numbers. Nobody is saying the formal proof approach will find all bugs, just that it helps find more bugs compared to not using it. You could make the same argument with acceptance testing: unless you specifically tried 3.1 as the input during testing, it might not give you the output you expect. Formal proof can be complimentary to traditional automated tests and QA.
- amelius 11y ago> How Did Software Get So Reliable Lol!
- DawkinsGawd 11y agoI haven't gotten a chance to read the entire paper however the reference to the Therac-25 in the beginning was slightly tilted. Yes - it was a programmatic error that dispersed a deadly amount of radiation. But, if I remember correctly, the Therac-25 is often used in Software/Computer Engineering ethics classes as an instance in which a hardware safety mechanism would be appropriate. So while the article is right that a software malfunction did disperse a deadly amount of radiation, the fix for this isn't necessarily a software solution