Slashdot Mirror
Hindsight: Reversible Computing
One of the more interesting tech pieces that came out this week has been Hindsight [PDF]. Hindsight is made by Virtutech and is billed as the "the first complete, general-purpose tool for reverse execution and debugging of arbitrary electronic systems." The demos were received extremely well and it just looks cool.
They say the way they accomplish this is running the program in some sort of sandbox and taking checkpoints every so often and then when you step back, it actually runs forward from the closest checkpoint and stops one instruction short.
My question is how UI interactions are handled. If the execution between the checkpoint and current-1 instruction includes a UI interaction, it might be very confusing to the programmer to know what or how many UI interactions need to be carried out to accomplish the backstep.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
Yeah, I can see some technical hurdles here ... like storing all old variable/register contents, jump addresses, etc.
How in the world did they pull this off?
Do you like Japanese imports?
It's all very well to be able to run code backwards/forwards/slo-mo/etc, but how to handle non deterministic external events coming in from the network? Does this tool presume that all applications to which it will be applied live in isolation?
Rich people are eccentric. Poor people are strange. Me, I'd be happy with odd.
Take a look at
http://www.lambdacs.com/debugger/debugger.html I'm sure a Hindsight sales person would (correctly) say this isn't a complete solution, but its the closest thing I've seen before this article.
I read this usenet post every now and then when I'm trying to fix something, and it makes me want to cry every time I do.
Mike Hoye
Hindsight seems to work based on a checkpoint mode when running backwards, it goes back to a checkpoint then runs forwards to the expected point. However how does it work with hardware?
Anybody tried this out for real?
Misleading titles? Inflammatory blurbs? Keep in mind that Slashdot is a tabloid.
And what about GUI and other side effects? Debugging a program in which such side-effects are deeply interleaved with algorithmics can be tricky indeed, although smart timestamping from the debugger will reduce glitches. But if you don't know better than randomly mixing algo and front-end in the first place, then you'd better fix the programmer than the program...
Uhh, ladebug on Tru64 has this `snapshot` and rewind feature..this isnt new. Congrats on getting an x86 version going, but lets not pretend you invented the concept.
ReVirt:
Belief is the currency of delusion.
In this paper, he proposes the Elephant language that can refer to the past in computer programs.
Pretty cool stuff!
I remember that several of the older compilers like Borland's Turbo Pascal, Turbo C and Microsoft C and MASM could run reverse execution through the debugger. They also had the "animate" feature that let you step through the code automatically, but slowly so you could watch each line of code as it was executed. I remember setting my PC up with two video cards: a monochrome Hercules card and an EGA card. A lot of the compilers from those days supported mutiple graphics card output - the code would appear on the monochrome monitor and the running executable would appear on the color monitor.
Being able to trace backwards ware extraordinarily useful, and it's one thing I miss in modern compilers. I always assumed that this capability was taken out with the advent of event-driven (GUI) programming. That's when a lot of this kind of functionality seemed to disappear.
A while ago there was a jwz post about being able to run a debugger backwards (for some reason I thought this needed kernel patches). If the checkpointing happened at "machine" level this would be possible regardless of the language...
(Actually someone has already posted the links jwz was talking about)
more seriously, that would mean that there is no crypto on these machines since all encoding would be reversible.
Some drink at the fountain of knowledge. Others just gargle.
The only way to "back up" execution is to save your state as you go.
At first I wasn't sure that your statement was true, but after thinking about it for 30 seconds or so, I realized it definitely was. Every instruction produces a deterministic calculation and can be reversed, right? If we have "ADD EAX, EBX", and know the current values of EAX and EBX, going backwards is easy, right?
Well, one really difficult case is jumps. How do you know what the previous instruction executed was? On X86 this would be pretty difficult since the encodings are non-regular, but even on an ISA with regular encodings it would be non-trivial because it would be difficult to figure whether you got to the instruction via a jump (which could be anywhere in memory), or from the previous instruction.
Add things such as Self-Modifying Code, and you have a real headache. Yes, you definitely need to track state as you go, though I'm not sure you'd need to save anything more than just the Instruction Pointer (which X86 does have a mechanism for). If you know what instructions were executed, it should be pretty easy to backtrack in time. I think.
...you can't do the same with most binary operations since all the common ones except NOT...
I'm not trying to be an ass here, but isn't that why they call NOT a unary operation, because of one operand?
I only mod up parents of "mod parent up" posts...
Try this UTM program:
Now, what UTM's could leave a machine in this state? Remember the states of the Universal Turing Machine are A, B, C, not what's written on the tape, i.e., the instructions.
The answer is, of course, a whole lot, but one simple subset of programs that can leave C in this state is any program like the above one, except the first instruction is Set A and B to values x0 and y0, where x0+y0=1+2=3, which is infinitely many, eg, 2+1=3,3+0=3,4+-1=3, etc. So that's infinitely many programs with the same form as the actual program, but with only a couple of constants changed.
(Note: true Turing Machines states aren't limited to a fixed set, like 0-255 etc, they use an encoding like 0100,1100,110100,111100, which can accomodate any size of number.)
That doesn't quite answer why it's generally complex to run a computer backwards, but you can put any number of instructions in between step 2 and 3, and as long as they don't touch A and B, once you've gone past that last instruction, you have no clue what states A and B were in until you go all the way back to the start of that program.
I guess a good checkpointing algorithm would be to save the states of any registers that are overwritten.
Damn, I already moderated this topic. Now I'll have to log in with my sock puppet to comment.
Since this appears to be a sandbox tool, what's the problem? The only real problem I can see, and that people bring up (since everything else is deterministic in a closed environment) would be random or psuedo random number generation. Could it not (or does it) simply save the results of system clock queries? Since the system clock is used to seed most random number generators, saving the return values and feeding them back could eliminate the problem. Clearly in encryption intensive programs this would act like some kind of memory bomb, but it would solve probably 99.9% of applications. As a safeguard, it could simply be alloted a certain area of memory that, once filled, would return to a 'closest fit' senario.
It is possible to replay the execution of programs that communicate with the outside world, rather than just in an isolated virtual machine: you have to log nondeterministic events. See http://www.erights.org/elang/concurrency/determini sm/overview.html.
a ge.
The first language I know of that supported replay is the Abundance database language, back in 1986. Also see http://c2.com/cgi/wiki?ReversibleProgrammingLangu