A program is a state machine (frequently, a nondeterministic one). A bug is a bad state transition rule.0,1 An execution witness is the states and state transitions encountered on a particular run of a program, which serves to demonstrate some interesting property.
If an execution witness exhibits a bad state, then there must be a bug, but it is not always obvious where the bug is, because it is not always obvious at what point the state became bad. Frequently, a bug produces a subtly bad state, which a benign transition later turns into a more overtly bad state. Hence, it is difficult to debug.
A debugger is a query engine over the states and transitions of a buggy execution witness.
Existing debuggers were not designed with this in mind. They were, I guess, designed for smaller, simpler programs running on computers with few resources. They tend to have a sequential bent; this is cheap to implement, and for small programs, the sequentiality serves to create a narrative explanation—it tells a story—which is very intuitive.
For large programs, however, the sequential format only obscures—a narrative view becomes superfluous as the narrative becomes inordinately large—the sequential debugger is a hindrance rather than a help.
Most programs behave nondeterministically. Frequently, a bug can be isolated to a deterministic component. The extent to which this is possible is to some extent a function of programming style; a style which attempts to encapsulate nondeterminism has advantages similar to the strictly stronger ‘functional style’ which attempts to encapsulate all side effects.
However, it is sometimes necessary to debug concurrent code.2 In these cases, an execution witness to a bug is a very valuable thing. A traditional debugger will allow you to single-step through such an execution witness once and once only; if you would like to step through it again, you must re-run the program and hope you get lucky. Solutions to this have been developed, under the names ‘time-travel debugging’ and ‘deterministic replay’, with the most prominent recent example being rr.
On the user interface side of things, these include an important generalisation of classic sequential debugging: you can step backwards. However, they do not, generally, to my knowledge, allow for the debugging of a live process. Another limitation of rr is that, although it can record multithreaded programs with fairly little overhead, it can only use a single processor at a time; this limits scalability and means that certain bugs will never manifest and others will have a much lower likelihood of manifesting than they might. I suspect that it is possible to implement scalable deterministic replay with fairly low time overhead in practice on commodity hardware by exploiting thread-locality (c.f.); this should be explored.
The debugger should allow the program to be changed while debugging. Attendant are:
What are logs and traces? Whereas an execution witness comprises the full body of states and state transitions, a log contains only a subset of them. Another way to view this is that a log corresponds to a class of execution witnesses that contain the log. Logs aid debugging by constraining the state-space search for an execution witness containing a particular bug.5
Further, the queries performed in a given debugging session will consider only a subset of states and state transitions—i.e., a log—hence, given a log, we do not search for an execution witness, but for another log. Sometimes, the second log will be completely contained within the first.
This suggests an alternate definition of ‘bug’: a program is buggy if it admits an execution witness which exhibits a bad state transition. This definition, which borrows from the concurrency semantics literature, is attractive because it may be easier to reason about bad states or state transitions than bad state transition rules.
This also suggests an optimisation strategy for deterministic replay. In order to debug a particular bug, we don't need a particular execution witness in order to debug it; we just need any execution witness that exhibits the same bug. This allows the execution recording to throw away unnecessary information and nondeterministically recreate something isomorphic on demand. It can be difficult to specify when two witnesses witness the ‘same’ bug; but it can be more or less reasonable in case of a crash or obvious invariant violation. (The alternate witness may not exhibit the same crash, but so long as it exhibits some crash, it still helps solve some bug!)
I should suggest some incremental steps that debuggers could take to move towards a more holistic view of state (though I suspect a ground-up reimagining of both the technology and the user interface is warranted, to get the best possible results).
Herein, I have broadly assumed that the user’s code is in error, and that the language implementation, the debugger, and the rest of the system are collaborating to try to help find the error. Usually, this is the case, but not always; what should we do when it is not?
I do not have much to add here to the existing body of knowledge on the topic, but I will make a couple of observations.
First, traditional designs for optimising compilers are not very good, and one of their faults is propensity for bugs. In the future, I will write about how to make optimising compilers that have fewer bugs (among many other virtues).
Second, system bugs tend not to be self-concealing, so more expressive debugging tools are frequently effective in debugging themselves or other system components.
Third, having more effective tools for analysing programs’ runtime states makes it easier to identify inconsistencies in those states, and therefore to identify system bugs.