How to do bidirectional or reverse debugging of programs?

The latest gdb version 7.0 (released this week) supports reverse debugging on a number of platforms (eg. native i386 and x86_64 linux, VMware workstation, UndoDB, and Simics simulators from Virtutech). ftp://ftp.gnu.org/pub/gdb

It works with the latest preview / pre-release of VMware workstation 7.0, which also supports reverse debugging of MSWindows guests using Visual Studio debugger. Get a free trial download of workstation 7.0 at http://communities.vmware.com/community/beta/workstation, and find some helpful usage tips here at http://communities.vmware.com/docs/DOC-10714

The newly released gdb-7.0 includes reverse debugging capability for native linux x86 and x86_64. You can debug any linux program as usual, turn on the "recording" feature, and from that point on, if you step forward too far, you can step backward or reverse-continue to a breakpoint.