When a bug is found in a piece of software, the root cause is often a bug in someone’s thoughts. One way to better understand a bug is to look at how deep the underlying thought error was. In other words: How many assumptions must be revisited as a result of the bug?
Level 1 — Syntax error, such as using the wrong operator or putting a function’s arguments in the wrong order. These are totally unsurprising.
Level 2 — Implementation error, such as wrongly assuming a pointer is non-null. These require developers to revisit whatever implementation-level assumption was made that lead to an invariant violation. Implementation errors can also occur at the level of algorithm design; textbooks can contain level 2 errors. Incorrect or sloppy theorems may have to be revised in response to level 2 errors.
Level 3 — Design error: the system is structured in such a way that it cannot meet its specification. A web server that runs untrusted code in its address space contains a level 3 bug.
Level 4 — Specification error: the software is solving the wrong problem. Assumptions about the purpose of the system must be revisited.
Level 5 — Framework error: the intellectual scaffolding upon which the software was based contains an error or omission. My favorite example comes from the early days of the development of optimizing compilers when people first confronted difficult questions about whether a particular optimization was legal or not. An entire sub-area of computer science had to be created to answer these questions. Something analogous is happening right now where we lack a framework for creating reliable and secure large-scale, software-intensive systems.
Level 6 — Universe error: a previously-unknown physical law prevents the software from working. If good computers had existed in the 19th century, the first person who tried to implement Maxwell’s demon and the first person who tried to implement a universal discriminator for halting vs. non-halting programs would have encountered errors at level 6. Future level 6 errors may result from efforts to build artificial intelligences.
Something interesting about levels 5 and 6 is that they look more like progress than like errors. This is no coincidence: scientific progress occurs when bugs in our collective thinking are fixed. Thus, we could easily construct a scale for scientific advances that mirrors the scale for software bugs. Einstein and Turing operated at level 6 at least a few times in their lives; many other great scientists work at level 5. A typical MS thesis is at level 2 and a dissertation should be no lower than level 3.
6 responses to “Software Bugs and Scientific Progress”
I would question the status of Level 6. Typically, software is designed primarily with respect to an abstract logical machine, which is beyond the realm of physics. Hence, for example, there are perfectly valid computer programs whose running time would far exceed any physically realistic bounds on the lifetime of the universe — I would not call such programs erroneous.
Hi David, what I was trying to say in Level 6 is that sometimes our understanding of the abstract machine is inadequate, and this inadequacy constitutes the bug. Of course, the universe is just another abstract machine.
I’ve always felt the process of efficient debugging involves having a good intuition about “slippage” (attributed to Douglas Hofstadter?) If there is a problem with your software, you challenge your weakest assumptions first, and until you find the bug, you gradually challenge more and more fundamental assumptions.
It’s interesting how my perspective of compilers has changed dramatically over the course of my programming career. In the beginning, I used to think compilers were wrong all of the time and were usually to blame when my programs didn’t work. Eventually I came to understand that compilers were almost always right, and my understanding was more likely to blame. Now, working closely with edge cases of the semantics of C, I’m back to doubting compilers all of the time 🙂
What is interesting is that languages can be designed to reduce the occurance of errors at many level 1,2,3.
> Level 1 — Syntax error, such as using the wrong operator or putting a function’s arguments in the wrong order. These are totally unsurprising.
For example putting the function’s arguments in the wrong order happen rarely if the language has call “with named-argument support” f(x=1, y=2)..
Using the wrong operator can be reduced also if the operators are correctly named, one couter-example is C’s operators & and &&.
Same with your example of level-2, for example Nice has syntax to distinguish between nullable and non-nullable references, this reduce the probability of such errors.
D has global variables in thread local storage by default.. Even better Joe-E with its object-capability can run untrusted code safely in the same address space..
I think it might be that it is our understanding of the universe which could be represented by some abstract machine. The Universe is a rather more real, like an ARM CPU instead of being like a Java VM.
re: Chucky’s comment – if you doubt the C compiler, then maybe it’s time to write that critical code in assembler ! Another case of deja vu straight from the 60’s.