If possible, describe platforms/languages/symbolic formats supported and if full support is provided (historical states back) or partially (only code can rerun with no rescue for states).
Further information about performance or resources needed is welcome but optional.
I have never used a debugger with the ability to step backward. I just did a Google search and didn't find much...
I did find this: http://video.google.com/videoplay?docid=3897010229726822034
Searching for "Bill Lewis debugger" led me to: http://undo-software.com/undodb%5Fabout.html
The ability to step backward implies preserving a lot of state: if you change a variable in one line of code, and then you want to step backward, presumably the variable should revert to its previous value. If you change a register, it should revert to its previous value, and that includes the flags register. If you allocated memory, presumably it should be de-allocated. And so on. It's a big job in general. It looks like this debugger is using copy-on-write technology to actually do all this. I guess if a virtual machine like VirtualBox is possible, so is this.
This is still not a mainstream feature. One feature I have commonly seen is the ability to "set the next line". Say you call a function and it returns a value that surprises you; you set the "next line" to the line before the function, and then single-step into the function. Microsoft Visual Studio debugger can do this and so can gdb (the jump command). This ability is of limited use if the function corrupted the stack. Then, you really need to start over!
Computers have gotten so fast, it's much less painful to start over from the beginning than it used to be. You can just set a breakpoint before the point where you want to go back, and re-run the program from the beginning.
Dr. Scheme, also known as PLT Scheme, will let you step backwards and forwards in a Scheme program. Full support for maintaining the state, as far as I can tell, though I haven't used it much. Runs on Windows, Mac and Linux.
The new IntelliTrace historical debugger feature in Visual Studio 2010 seems to fit what you're asking for. See Debugging With IntelliTrace:
Debugging with IntelliTrace, available in Microsoft Visual Studio 2010 Ultimate, provides an enhanced picture of your application compared with traditional debuggers. Traditional debuggers show you the state of your application at the current time with limited information about events that occurred in the past. You must either infer events that occurred in the past, based on the state of your application at the current time, or restart the application to re-create past events. With IntelliTrace, you can actually see events that occurred in the past and the context in which they occurred. This reduces the number of restarts that are required to debug your application and the possibility that an error will fail to reproduce when you rerun the application.