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.

Comments

Sounds good - but expensive.

[bigtallmofo]

From reading about this earlier, it is a very exciting technology for embedded systems. It does seem a bit expensive though:

Hindsight will go into beta sites in May, with production slated for July. Incremental cost over Simics is around $5,000 per seat, but Hindsight won't target single seats. A typical engagement, including Simics, Hindsight and some initial model development, is estimated at $200,000 to $300,000 for a software development group with 10 to 20 seats.

That's just nutty...

[The Desert Palooka]

With Simics Hindsight it is now possible to step back just before the error and then run forward again, providing another opportunity to reproduce the error and look more closely at what occurs in detail, without having to re-launch the program. Simics Hindsight can even unboot an operating system, running the code backwards until it reaches the initial hardware launch instruction after a hardware reset.

That would be quite nice... It almost seems like a shuttle head or what not for programmers... Rewind, play, slow motion and so on... I know they said it's the first complete one, but is there anything else out there like this?

Re:That's just nutty...

[paulsnx2]

The only way to "back up" execution is to save your state as you go. In Computational Theory, this amounts to the fact that, given a particular UTM in a particular state (state, position on the tape, values on the tape) an infinite number of UTMs exist which, at some point in their execution, arrive at a state equal to that particular state. (we leave the proof to the reader)

Thus the only way to "back up" computation is to know the past of that machine, i.e. a state log of the execution of the program.

BTW, I wrote a Rules Engine for the State of Texas and the Texas TIERS project. I logged each state change as the decision tables are executed, and then wrote a tool that uses this log to wind forward and backward the state of the rules engine. This does exactly for policy what these guys are claiming for program development.

I provided a tree view of the execution through the decision tables, and a state view that allows you to "jump" to the the place in execution where a particular variable was last set (from the perspective of where you happen to be in the execution of your program). I'd expect they also provide such features.

Execution logs (especially very complete logs) are make the implementation of very wonderful and magical debugging tools possible.

BTW, I don't know if they have attempted to patent the use of execution logs in the implemenation of such tools, but if so my TIERS work is quite clearly documented in a Federal/state project, and clearly uses these techniques and dates back to 2002 or so. I've used the technique to do this far before that, but I'm not sure if it is publicly documented.

Paul

Re:That's just nutty...

[VAXman]

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.

Re:That's just nutty...

[Hynee]

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?

Try this UTM program:

Set A and B to the values 1 and 2
Add values of A and B and put them in C
Put value x1 and y1 into A and B

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.

UI

[GigsVT]

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.

Not necessarily

[spookymonster]

From their website, you can get a free academic version of the software as well. At least, that's what the site says (I didn't register to download it, so I can't confirm).

Mirror

[tabkey12]

Mirror of the PDF

Never underestimate the Slashdot Effect!

Virtualization layer for checkpointing and steppin

[jaxdahl]

This seems to create a virtualization layer where checkpoints are saved periodically, then instructions are single stepped through. So to step back, it goes to the first checkpoint before the instruction you want to step back to, then it single steps up to that point. This would aid in kernel-level debugging where data structures might be overwritten from almost anywhere in the computer that can access the kernel space -- no need to set a watchpoint then reboot and wait for the next error to occur.

But what about external events

[bangzilla]

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?

Re:But what about external events

[tesmako]

Since it is based on the whole-system simulator Simics -- Yes, it does assume that the app runs in isolation, since all external stuff is just simics simulations.

Re:But what about external events

[LiquidCoooled]

No, you got it all wrong.

This product is a cleverly disguised time machine.
You can actually rollback and reverse to actually see the initial "First post!" remark, and undo the slashdot effect.

If you look closely, you can also see the cognative response from Hemos as he clicked Accept on this submission.

Too good to be true...

[Leadhyena]

I can see how this software can come in real handy, but it won't work in every situation. It states in TFA that Hindsight doesn't do the naive approach of recording every instrction, but rather takes snapshots and tries to fill in the gaps. There are many types of calculations out there (think The Game of Life or other CAs) that by their nature cannot be reversed, so all of those states would have to be stored or it would be mathematically impossible to calculate the reverse steps.

Therefore, I can't see their approach being foolproof, and the over-obvious advertisement (this is what normal debugging toolbars look like, but they don't have a nifty step-one-back feature) seems too bright to be withot caveat. At $5,000 a seat I'd say buyer beware.

Re:Too good to be true...

[CausticPuppy]

There are many types of calculations out there (think The Game of Life or other CAs) that by their nature cannot be reversed, so all of those states would have to be stored or it would be mathematically impossible to calculate the reverse steps.

It also says in TFA that it doesn't actually calculate the reverse steps, so it doesn't matter if it's mathematically impossible.

What it does do is take complete snapshots every (for example) 100 steps. In order to move "backwards" a step, it returns to the previous breakpoint (a known state) and goes forward 99 steps.
Then it returns to the same breakpoint and goes forward 98 steps. And so on. So from your perspective, you see the 99th step, 98th, 97th, and on down. It only LOOKS like it's running backwards.

This would even work for the game of life.

So the performance tradeoff would be this:
More frequent breakpoints causes forward execution to be slower because it's spending more time saving data at regular intervals for breakpoints, but "reverse" execution would be faster because it has to iterate fewer steps from the previous breakpoint.

The Omniscient Debugger?

[Anonymous Coward]

http://www.lambdacs.com/debugger/debugger.html/

Seems like this has been done before, at least for java apps...

BSOL?

[bunyip]

So, would reversible computing let me have a Blue Screen Of Life?

That would be so cool...

Alan.

Thats simple...

[Anonymous Coward]

just invert the micro clock signal so everything runs backwards :)

Not by a decade.

[Murmer]

This technology has existed, in GPL form, for ten years. It's just had exactly zero uptake.

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.

Reversible Computing != Reversible Execution

[Anonymous Coward]

Reversible computing is a way of computing without (permenantly) consuming energy. Look it up if you're not familiar, because it's pretty interesting.

Anyway, the headline is misleading.

OCaml anyone?

[fab13n]

OCaml as been offering timestamps and backward debugging for years, in addition of a great programming language (backward debugger's implementation is based on Unix's forking and copy-on-write, so running it on windows requires cygwin). Simply compile your stuff to byte-code rather than with the native optimizing compiler, run the debugger and use backstep/backward just as you used to do with step/forward. Breakpoints block execution in both directions.

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...

Any relation to ReVirt?

[eddy]

ReVirt:

The ability to replay the execution of a virtual machine is useful in many ways besides intrusion analysis. For example, it enables one to replay and debug any portion of a prior execution. We have built an extension to gdb that uses virtual-machine replay to provide the illusion of time travel. In particular, we provide the ability to do reverse debugging, though commands such as reverse watchpoint and reverse breakpoint. graph. See our paper in USENIX 2005 for details.

Elephants never forget

[same_old_story]

John McCarthy has been talking about giving programming langues the notion of time for quite some time (no pun intended).

In this paper, he proposes the Elephant language that can refer to the past in computer programs.

Pretty cool stuff!

Is This Really New?

[Ginnungagap42]

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.

checkpoint the hard disk too?

[goombah99]

the state of a computer is not the state of the memory. it includes the hard disk as well. to give one tiny example: the vvirtual memory. to give a better example, if a program overwrites a file you have to check point back over that too. to give an even better example, if you were debuggin a disk defragmenting program every bit on the disk could move.

Come from?

[AJWM]

Reverse execution? Are we finally going to see an implementation of the COME FROM statement?

(See also the entry in the jargon file.)

Mod parent up

[Animats]

That's impressive technology. And it needs to be better known. Reverse-stepping has been available for gdb under Linux since at least 1999, and nobody knows it. So please, mod the parent up.

This has real potential. Beta versions of programs should run with this installed, so the core dump can be stepped backwards to the trouble spot. This could make Linux software significantly more reliable.