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

[frobnoid]

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.

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

[zootm]

There's an academically interesting (I'm assured :)) Java system similar to this called Bdbj. I'm not sure if it's useful in a real context, but I assume it is to some degree.

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

[matman]

Not only that, just try to undo a "i += rand()" type of statement... or user input... or a network call. Most network protocols do not support "forget the last three statements and roll back in state". :)

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.

Re:That's just nutty...

[foobsr]

but is there anything else out there like this?

Yes, in the museum.

The debugger that came with BS3 on the TR440 had an option that enabled you to step back a defined (small due to lack of space for saving) number of steps if you set the appropriate switch when compiling. Very cool feature - 30 years ago !

CC.

Re:That's just nutty...

[pVoid]

Every instruction produces a deterministic calculation and can be reversed, right?

Wrong.

mov eax, 0
mov eax, [eax]
xor eax, eax
jmp eax
imul eax , 0
...

Basically any code that moves any data is crunching some other data. Given that RISC and CISC processors are Load/Store based architectures, that makes for pretty much a majority of cases.

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.

Re:UI

[TuringTest]

Furthermore, this won't work for finding bugs on concurrent programs due to race conditions or parallel threads corrupting a shared resource.

Those bugs might be catched if the environment would record instructions one-by-one, but as is you may find a bug in your execution, roll back to the checkpoint and find that the bug is gone in the replay. Hey, that would be funny if it happened on a TV football game...

Re:UI

[DanShearer]

The beauty of full systems simulation is that you are simulating the full system :-) So UI interactions also take place in the simulated world.

The trick is to have a simulator fast enough so that you can do UI interactions, because the user isn't in the simulated world. As it happens Simics is fast enough and this is exactly how it works. I'm on the Simics product team, and one way we have of proving the point is to run operating systems and their applications backwards for which we cannot have the source code, eg Microsoft Windows. If someone still thinks we've inserted magic tricks after seeing CLOCK.EXE launched, run backwards and then unlaunch, well, there's not a lot more we can do. That also illustrates the point of the whole computer plus OS running backwards, not just a particular application.

You can get humorously stuck actually with UI interactions... if you run forward to a certain point going point click etc, and then have an animated discussion with somebody for five minutes having forgotten to pause the simulation... unless you do something clever when you engage the reverse gear you have to sit and wait for nothing to un-happen for five minutes until you see the UI get reversed!

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.

Re:But what about external events

[G. W. Bush Junior]

Then the example in TFA is pretty bad.
It's exactly an example of an external packet containing a wrong checksum.

If the system is in isolation, you would have to come up with the idea of sending a malformed packet yourself instead of just letting it run until it crashed. that doesn't seem a very likely thing to try.

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.

Wow !

[Digital Warfare]

Now when I'm playing online, when I die I can rewind.

I can hear it now, "Godlike!"

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.

Problems with platform emulalators

[selectspec]

Hindsight is a service within their platform emulator. While it sounds nifty, and I'm all for it... emulators never behaive the same as the real platform... especially in embedded environments. The timing of peripherals is never the same on the emulator as the platform. The result is that lots of time is spent debugging the emulator environment that bares little fruit for the platform environment.

What would be far more useful, would be to write tools that took advantage of many of the onboard hardware debugging capabilities of some of the common embedded chip architectures.

The trick...

[Professor S. Brown]

If you read the article carefully, it does actually say. Basically they've optimised the printf() and scanf() functions, from the standard C libraries, to a very high degree. Using these optimised functions allows them to literally run the processor backwards, with a little help from Euler Integration to approximate the execution path. Its very clever indeed.

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.

Re:Not by a decade.

[mec]

Wow, what to say?!

First, it was kind of silly to name the program the same as my user name, but I never found a better name for it than "my trace-and-replay debugger".

My original plan was to write this for Solaris and sell it, hence the insistence on tracing and replaying without modifying the target program or the operating system, and that's why the replay controller messes with gdb's mind, so that it can work with a stock gdb rather than needing gdb extensions.

I developed a Linux version first because it was so cheap and simple to throw Slackware on my computer. And, well, it turns out that I'll probably never need a Solaris version, because Linux sure has become big enough and rewarding enough for me.

Versions 0.1, 0.2, and 0.3 took 15 months of full-time work, living on my savings and writing code on a little Linux box.

After version 0.3, several bad things happened:

Technical butterfly-chasing: the tracer needs to know about all possible ioctl calls that the target program makes, and Linux was adding and changing ioctls faster than I could check the patch diffs to update them. (That's how I came to write the kernel change summaries for a while). The obvious solution is to trace about 20 common ioctl's and throw all the rest in a big worst-case box that says "this ioctl might touch all of memory". One of the problems of working alone: nobody else around to notice the obvious solution.

Moving up the management chain: anybody who runs a one-person operation knows about this. It's one thing to write a proof-of-concept program. It's another thing to push it out, start a community, market it, manage all the communication with users and co-developers. I failed at that.

Fade-out: after the proof-of-concept worked, I noticed I'd spent 15 months full time, and I did make the milestone of seeing test programs run. I lost some interest and went and did something else.

Version 0.3 still has one good use: to help defend against anybody else that files a patent for technology like this. I released in November 1995.

Some responses:

Zogger and Animats, that's exactly the use case, the user in the field runs the tracer, then mails a big log back to the developer. This gets very useful when the user has unique resources that the developer doesn't, for a program like a network server. I don't know much about dtrace, but I think dtrace is just more comprehensive kernel reporting information, not fundamentally "video-taping the user process".

Mebane, I think the answer is: in 1995, I sucked at explaining things to people. Specifically, back then, I was into the "macho flash" school of communication: "this debugger is the best thing since breakpoint debugging, it will solve problems you didn't even think could be solved, etc". I should have just done a very simple demo walkthrough of printf("%d\n", gettimeofday()).

Auxon and Skubeedooo, yeah, it was a lot about marketing.

Jeff Mahoney: I agree, Hindsight looks much more powerful. But Hindsight is also more resource-intensive: they have to simulate a whole CPU.

MenTaLguY: I would be happy to chat with anybody who wants to do a revival. The mec@shout.net contact address still works.

And the whatever-happened-to-mec line: I worked for Cygnus/Red Hat for several years on gdb. My current job is with Google.

Reverse Execution of Code? Haha! Oh wait...

[AceJohnny]

We've seen a few april fools claiming to be able to run code backwards. This is impossible, at the lowest level. For example, take the logical OR: C = A + B (excuse the layout, the top line is the value of B, the first column the value of A)

A\B | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |

We know the result, C. How do we know if A, B, or both was 1? We lost information (2 bits of info became 1), and cannot get it back. So at first I dismissed any ridiculous claims of reverse execution. But we aren't the 1st of April...

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?

Re:Reverse Execution of Code? Haha! Oh wait...

[0x461FAB0BD7D2]

How do we know if A, B, or both was 1?

There is a way to do this, although it is a bit ugly. The reverse-runner forks the program into 3, one for each of the possibilities. It then continues this until values have been solved.

It would produce a decision tree, and the debugger could work backwards.

Of course, this is purely theoretical. If A and B were strings, the number of processes would be infinite, in which case heuristics would be required, and it wouldn't be perfect.

Re:Reverse Execution of Code? Haha! Oh wait...

[HidingMyName]

Reverse execution is possible at the source level, but it requires generation of extra data structures to handle operations that don't correspond to invertible functions. This approach has been applied with some success to high performance simulations to give a "lightweight rollback", by Peters and Carothers in An Algorithm for Fully Reversible Optimistic Parallel Simulation.

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.

Hmm...

[thed00d]

Interesting, but will it work on a dead badger running GNU/Linux? Cause thats where do all my development work.

Where do they store the entropy?

[goombah99]

If computing is reversable then the system is not losing information. All that entropy has to go somewhere. while built up heat can radiate away on the fan, the entropy must keep building up. At some point its going to explode!

more seriously, that would mean that there is no crypto on these machines since all encoding would be reversible.

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.

Re:reversible computing == low energy computing

[TeknoHog]

The term "reversible computing" has also been used for a type of circuit that does not consume energy, other than entropy, for computation.

I think you got it just the wrong way.

Traditional computers generate entropy because of the information destroyed. Entropy created is necessarily associated with heat. With reversible computing there is no entropy increase, which in theory means less heat produced and less energy consumption.

Re:!tsop tsrif

[gorjusborg]

C'mon, this is funny!

It's friday people, lighten up :)

Damn misleading articles.

[PxM]

I was getting excited since I thought they had actually created a practical reversible computing hardware system. The idea behind true reversible computing is that information flow in computation is linked to the energy lost as heat during computing. Von Neumann showed that there was a hard limit on the amount of energy needed everytime a bit of information is lost dependent on Boltzmann's constant and temperature of the system. The ultimate goal is to have a computer that looks a lot like particle physics where the rules are completely time-symmetric. I.e. if I reverse the flow of time, the laws of physics will still run properly and allow me to reconstruct all the previous states from the present one. While the principle of quantum reversibility (sometimes called the "conservation of information law") you can't do the same with most binary operations since all the common ones except NOT take in 2 bits and output 1 bit. Thus, it is impossible to run the system in reverse and reconstruct those two bits from that one bit. This has the adverse effect of wasting energy as heat into the environment.

It's and interesting field that's going to take off as Moore's Law slows down due to wasted heat. A good starting page with links for the interested is here.

--
Free iPod? Try a free Mac Mini
Or a free Nintendo DS, GC, PS2, Xbox
Wired article as proof

Re:Damn misleading articles.

[fraudrogic]

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

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

Re:Come from?

[Tablizer]

Personally, I like Evangelical Fortran. It has a GOTO HELL statement.

RTFA

[p3d0]

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.

They take periodic system checkpoints and then work forward to the instruction preceeding the one you started from. There's no reason the Game of Life wouldn't be amenable to this.

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.

From the website...

[ghost1911]

This is especially significant when you consider 50% of a software engineer's time is spent debugging software.

They assume that programmers... DEBUG! Hah!

There are a few issues but...

[Morticae]

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.

Replay with nondeterministic events

[DavidHopwood]

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.

The first language I know of that supported replay is the Abundance database language, back in 1986. Also see http://c2.com/cgi/wiki?ReversibleProgrammingLangua ge.