Title: Debuggers Should Go Backwards

Author:

Date: 02 December 2005 06:00:00 +00:00 or Fri, 02 December 2005 06:00:00 +00:00

Summary:

Body:

Introduction

The computer science community has shown a woeful lack of interest in debugging, which given the huge economic cost of debugging is somewhat mysterious. However, there may be signs of "green shoots" in the desert landscape of debugging tools. There are many tools and techniques that offer significant improvement over the trusty printf, and over the past year or two there have been some particularly noteworthy developments, including analytical tools such as Valgrind [Seward-], along with a new breed of debuggers: bidirectional debuggers. These allow the programmer to step their program backwards as well as forwards, and so are much more helpful than traditional debuggers in taking the programmer to the source of their bug.

A Brief History of Debugging

Debugging is as old as programming itself. Maurice Wilkes said [Wilkes] of his experiences writing some of the world's first programs in 1949:

As soon as we started programming, we found to our surprise that it wasn't as easy to get programs right as we had thought. Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs.

Despite high-level languages and other paradigm-shifting changes since 1949, most programmers still spend most of their time debugging. In his seminal book The Mythical Man Month [Brooks], Frederic Brooks claimed that even the best programmers produce only ten lines of debugged code per day. In the 1995 revised edition he says this alarming statistic is as true as ever. The operative word here is debugged. A programmer may write 50 lines of code on the first two hours of Monday morning - the remainder of their week will be spent trying to get those 50 lines to work correctly.

Computing's Dirty Little Secret

Henry Lieberman of MIT used his guest editorial of the Communications of the ACM [Lieberman] to talk about what he calls "the dirty little secret of computer science". That month's publication is subtitled The Debugging Scandal and What to Do About It. In his editorial he says:

What borders on scandal is the fact that the computer science community as a whole has largely ignored the debugging problem. This is inexcusable, considering the vast economic cost of debugging.

If you were programming in 1997, you'll know that little has changed since Lieberman's call to arms. Given the enormous economic costs of debugging, and the size of the market this therefore implies, the lack of attention on debugging aids is somewhat puzzling. Sure, there are have been a few interesting projects around debugging over the years, but not much relative to the amount of research on operating systems, languages, or just about anything else. One might suppose that part of the reason is that these are difficult problems to solve, but then language or operating system1 design and implementation isn't exactly easy. We suspect the relative lack of effort spent on debugging is as much due to the lack of 'glamour' associated with it, as it is to do with the problems being difficult ones.

Are Things Getting Better or Worse?

While there has been some recent progress in programming and debugging tools (see sections 2 and 3), two trends in computer science are threatening to offset these advances.

The first is multithreading. More and more modern applications are multithreaded. And with SMP/multicore CPUs becoming mainstream and clock frequencies flat-lining, if we want to exploit the power in future generations of processors its likely our programs will need to become more multithreaded still.

If multithreading is making debugging harder, today's security concerns are "raising the bar" when it comes to the quality standards that modern software must meet. Yesterday's pathological/theoretical concerns that were never likely to bite in real life are today's security vulnerabilities.

Today's Debugging Tools

This section reviews some of the techniques commonly used to debug today's code. It is by no means exhaustive; the intent is merely to give examples of the more common techniques.

We classify the different debugging techniques into three groups, listed below.

Programmatic Techniques

Here programmers modify or write their program in order to help find the bugs.

Print Statements. This classic is still the most widely used technique. In some senses the technique's wide use reflects its simplicity and convenience (it's rare that this technique isn't an option). But in other ways the fact that print statements remain our number-one way of debugging code is a reflection on the inadequacy of mainstream debugging tools.
Assertions. An invaluable tool; most good programmers use assertions liberally.
Language Support. If you're lucky enough to be using a 'safe language' (e.g. Java or Python) then there are many classes of bugs that just can't happen (e.g. memory corruption bugs). Sadly, there are still many jobs where these languages just aren't an option, and one needs to use lower level languages such as C/C++ (or even assembler).
Test-suites. There is no excuse for not having a test-suite for programming projects of even modest size. Not only do they help identify new bugs quickly, if used properly they can be an excellent way of preventing regressions.

Special Case Diagnosis/Analysis Tools

Some of the most interesting developments in debugging in recent years have come in the forms of tools that help programmers ?nd particular classes of errors in their programs. Some notable examples are:

Purify. [Hastings-] This tool instruments a running process and finds common memory access violations. The full version is available for Solaris and sold as part of IBM's Rational tool-suite for several thousand dollars.
BoundsChecker. [boundschecker] Plugs into VisualStudio and finds many common errors in programs by instrumenting running programs. In a broad sense this is your answer to Purify if you're running on Microsoft Windows (although the details are quite different).
Valgrind. [Seward-, Nethercote-] Started life as a sort of open source version of Purify, but has grown in to something much more generic. More recent versions of Valgrind allow one to plug several different 'skins' into the Valgrind core in order to check for many different classes of bug (e.g. touching unallocated memory, or potential deadlock conditions).
Coverity. [Coverity] A commercial product born out of an interesting research project [Engler-] that extended gcc to find common errors at source code level. Before going commercial their tool found over 2,000 bugs in the Linux kernel. Sadly, you can't buy the Coverity software - their consultants come to your organisation and run their magic on your source code (they don't advertise their prices, but it is presumably a safe bet that they don't come cheap!).
Code coverage tools. Code coverage tools such as gcov are (in our experience) woefully rarely used. Most programmers are very surprised to see just how little of their code is covered by their test-suite (if they even have one).
Hardware protection. Most modern computer systems have memory management hardware to catch illegal memory access when they happen. Many CPUs have other debugging features, such as the Intel's debug registers that can generate a debug exception whenever a specific virtual address is accessed. These can be particularly useful when faced with obscure memory corruption bugs.

General-Purpose Debuggers

Special-case tools can be very useful for debugging. However, such tools are only useful if your bug is of a certain well-known kind (e.g. accessing a variable from two threads without protecting it with a mutex, or accessing unallocated memory). If your bug doesn't fit neatly into one of these categories, such tools don't offer any help.

That's one of the reasons why general-purposes debuggers tend to be used more frequently than do the kinds of special-case tools presented in section 2. However, today's general purposes debuggers have a major flaw: they let the programmer single-step their program forwards, but debugging involves thinking backwards. To debug a program is to reason backwards from the point of failure to determine the cause of that failure. On the first page of their book, The Practice of Programming[Kernighan-], Brian Kernighan and Rob Pike give the following advice to programmers when debugging:

Reason back from the state of the crashed program to determine what could have caused this. Debugging involves backwards reasoning, like solving murder mysteries. Something impossible occurred, and the only solid information is that it really did occur. So we must think backwards from the result to discover the reasons.

Many programmers use debuggers only to examine a program's state, and then reason backwards from here. Most of a debugger's intelligence is geared towards letting the programmer single-step forwards, but that's of limited help. To be really useful, a debugger needs to help the programmer walk through the program's execution in reverse.

Bidirectional Debuggers

Bidirectional debuggers walk the programmer though their program backwards as well as forwards. The ability to step backwards from a fault to diagnose its cause massively eases the burden of debugging - the programmer can now get straight to the source of the bug.

The aforementioned Kernighan and Pike go on to say in their book:

If it's a hard bug, you'll be making it happen over and over as you track down the problem.

Bidirectional debuggers herald an end to this running a program again and again looking for the source of a bug; instead the programmer can just rewind and play forwards the program, 'honing in' on the source of their bug.

Bidirectional Debuggers for Java

Java programmers have had the benefit of bidirectional debugging for a few years now. The first of these was a research tool by Bill Lewis, known as ODB [Lewis] (the Omniscient Debugger). His research has demonstrated how programmers of varying abilities were able quickly to track down bugs using ODB that otherwise would have taken much longer. At this year's OOPSLA conference, Bill offered $100 to anyone who could present a bug that his debugger could not find - ODB passed the challenge.

There are now commercial bidirectional debuggers for Java: Visicomp's RetroVue [RetroVue] and Omnicore's CodeGuide [Omnicore] are examples. Both have won many awards and accolades in the Java community.

Bidirectional Debugging of Entire Systems

The GreenHills SuperTrace Probe records all state transitions a computer system makes as it executes, and when used in conjunction with their TimeMachine debugger [timemachine] provides programmers with bidirectional debugging of an entire computer system.

Likewise, the recently launched Hindsight [Virtutech] debugger from Virtutech allows bidirectional debugging of a complete system by simulating the hardware with software. Both of these systems are expensive (the GreenHills SuperTrace Probe and TimeMachine debugger retail for $20,000; Virtutech does not have standard pricing for Hindsight), but if you want to debug a complete computer system (usually this means an embedded system or possibly an operating system), then they can be invaluable.

UndoDB: Bidirectional Debugging for C/C++ Programs

UndoDB has recently been released for the GNU/Linux operating system on i386 PCs. It is unique in that it allows bidirectional debugging of a straightforward binary Linux process. No expensive hardware or simulated hardware platform is necessary. Instead, UndoDB takes the form of a wrapper around the widely used GNU debugger, gdb[Gdb]. This means that programmers who are familiar with gdb will feel right at home using UndoDB.

A Few Simple Commands

UndoDB works just like gdb, but adds a few new commands which revolutionise how gdb can be used. There are the new commands bnext, bstep, bnexti, bstepi, bfinish and buntil. These work exactly like their forwards counterparts next, step, nexti, stepi, finish and until, except that instead of stepping the program forwards one or more instructions, the program is reversed. For example, the step command moves the program forward to the next source line, possibly stepping to the first line of a different function if the current line includes a function call. Its bstep counterpart moves the program back one source line, possibly stepping to the last line of a different function if the previous source line included a function call.

See the UndoDB man page [Undodb] for a full description of these commands.

Time

To say UndoDB lets one run programs backwards as well as forwards is not quite accurate. Rather UndoDB allows one to rewind a debugged program to any point in its history, and examine the program's state at that point. In the case of commands such as bstepi this means stepping back to the most recent time a particular source line was executed; by using the bgoton command the programmer can go back to an arbitrary point in the program's history. From any point in history, the user can issue the normal gdb commands such as continue or next to move forwards, as well as the backwards commands such as bnext.

UndoDB measures time using the notion of "simulated nanoseconds". A simulated nanosecond approximates a nanosecond were the program to execute normally, although there is no strict correlation between wall-clock time and simulated nanoseconds. The user can rewind their program almost instantly to any time in its history by passing the requisite simulated nanoseconds argument to the bgoton command. The programmer can find out how many simulated nanoseconds have elapsed in the current debugging session using the bget command.

Critically, no matter how many times the program is rewound and replayed, each instruction happens at exactly the same simulated nanosecond each time. More generally, the program is entirely deterministic: each time the program is at any given simulated nanosecond, it will be exactly the same state.

Where To Next?

The functionality of the current release of UndoDB is somewhat limited. Most notably, it only works on GNU/Linux on i386 or i686, and debugging of multithreaded programs or programs that use signals is not supported. In recognition that this precludes UndoDB's use with a large number of modern computer programs, anyone who buys a commercial-use license before the end of 2005 will receive a free upgrade to UndoDB version 2.0 as soon as it is released. Version 2.0 will include support for multithreaded programs and programs that use signals. (We feel that bidirectional debugging will be particularly effective when used with multithreaded programs, especially given the way programs can be rewound and replayed many times, all entirely deterministically.)

There are many other features that are planned for releases subsequent to 2.0. This includes support for other architectures (such as x86-64, ARM or MIPS), and other operating systems (such as Microsoft Windows, Apple's OS X, or the various flavours of BSD).

Also planned are advanced debugging features, such as the ability to change state at a point in the program's history and then replay (thus "rewriting history") or to find the most recent time in a program's history that completely arbitrary criteria were met (such as some expression evaluating to true).

Conclusion

Debugging has for too long been computing's dirty little secret. But things are beginning to change. Among a few new debugging technologies to emerge over the past few years, bidirectional debugging in particular promises to revolutionise the way programs are debugged, drastically reducing development times and at the same time improving software quality.

In the short time Java bidirectional debuggers have been available they have already shown impressive results. Of particular relevance to readers of this publication are new tools that bring bidirectional debugging to C and C++ programmers. For programmers who are writing code that controls the computer system directly (i.e. low-level embedded programmers and operating system programmers), the GreenHills TimeMachine debugger [timemachine] and the Simics Hindsight [Virtutech] debuggers offer compelling (if expensive) solutions. For programmers of C/C++2 on GNU/Linux, UndoDB extends the familiar gdb with bidirectional debugging capabilities.

Some have said that bidirectional debugging represents the biggest change to the way we debug software since the first symbolic debuggers appeared many decades ago. We agree.

References

[Brooks] Frederic Brooks. The Mythical Man Month: Essays on Software Engineering, Anniversary Edition. Addison-Wesley, 1995.

[RetroVue] Visicomp corp. RetroVue Java Software Visualization Tool. http:// visicomp.com/product/retrovue/index.html.

[boundschecker] Compuware Corporation. Compuware boundschecker for devpartner. http://www.compuware. com/products/devpartner/bounds. htm.

[Coverity] Coverity Corporation. Breakthrough technology to find catastrohpic flaws in source code. http://coverity.com/.

[Engler-] Dawson R. Engler, David Yu Chen, and Andy Chou. 'Bugs as inconsistent behavior: A general approach to inferring errors in systems code' in Symposium on Operating Systems Principles, pages 57-72, 2001.

[Gdb] The Free Software Foundation. Gdb: The gnu project debugger. http://gnu.org/ software/gdb.

[Hastings-] R. Hastings and B. Joyce. 'Purify: Fast detection of memory leaks and access errors' in Proceedings of the Winter USENIX Conference, December 1992.

[Kernighan-] Brian Kernighan and Rob Pike. The Practice of Programming. Addison Wesley, 1999.

[Lewis] Bill Lewis. Omniscient debugging. http://lambdacs.com/debugger/debugger.html.

[Lieberman] Henry Lieberman. 'The debugging scandal and what to do about it.' Communications of the ACM, April 1997.

[Nethercote-] Nicholas Nethercote and Julian Seward. 'Valgrind: A program supervision framework' in Proceedings of the Third Workshop on Runtime Verification (RV'03), Boulder, Colorado, USA, July 2003.

[Pike] Rob Pike. Systems Software Research is Irrelevant. http://cm.bell-labs.com/ who/rob/utah2000.ps, February 2000.

[Seward-] Julian Seward, Nicholas Nethercote, Jeremy Fitzhardinge, et al. Valgrind. http://www.valgrind.org/.

[timemachine] Green Hills Software. Green hills timemachine. http://www.ghs.com/products/ timemachine.html.

[Omnicore] Omnicore Software. Omnicore website. http://omnicore.com.

[Undodb] Undo Software. Undodb man page. http://undo-software.com/ undodb_man.

[Virtutech] Virtutech. Simics hindsight. http://www.virtutech.com/ products/simics-hindsight.html.

[Wilkes] Maurice Wilkes. Familiar and unfamiliar quotations. http:// www.norvig.com/quotations.html.

Notes:

More fields may be available via dynamicdata ..