MIT develops new tool that can interrupt infinite loops

http://bostinnovation.com/2011/08/02/mit-researchers-develop-tool-to-resuscitate-frozen-programs/

by pgatzke • 15 years ago

106 67 15 years ago

Seems to me like this sort of thing could be pretty good for advanced users who understand it's limitations and potential failure modes, but a nightmare waiting to happen for everyone else.

And of course I'm also inclined to suggest that advanced users would be better off attaching gdb to the process to get done what they need to, then coredumping and contacting the developer...

prolepunk2• 15 years ago

First of all the solution of this problem is computationally impossible so this tool makes me feel realy uneasy I'd never use it -- it would actually make predictable easily reproducible bugs impossible to report when this tool is activated. It makes an assumption that infinite loops are just stuck with a false condition and nothing else is affected by that, which I believe is fundametally false.

adrianN• 15 years ago

It appears to take memory snapshots. If it detects a repeat in the snapshots it knows that the program will loop indefinitely. Of course it can't detect all infinite loops, but a sizeable subset.

_delirium2• 15 years ago

In theory I believe it can actually detect all infinite loops, for an extremely generous definition of "can detect". On a finite-memory machine, a computation fails to halt iff it eventually repeats a state, which it must do in finite time, since there are only finitely many possible states (the finite-ness is what makes the halting problem not apply). However, that finite time might be extremely large, perhaps longer than the age of the universe. A http://en.wikipedia.org/wiki/Busy_beaver function gives an upper bound on how long it can be.

But yeah, the practical use is to tell you when a computation is already looping, for the large subset of infinite loops that result in states being repeated relatively quickly.

prolepunk2• 15 years ago

It only takes memory snapshots to find next end-of-loop instruction in binary code to jump to it, with source equivalent of it being:

   while True:
      if loop_var > 9000:
        break
      loop_var += 1

My main complaint that might as well detect a repeat in snapshot but I really doubt that it detects extraneous changes in loop variables that might be caused by stray infinite loop logic.

From programming perspective it's better to crash hard and let the error be known rather than fail silently and introduce more sublte errors.

From user perspective, what is the point of saving file in a program that is falling over when you could potentially save a corrupt file and instead of retaining some of the work the user will end up with a blob of useless data. I guess you could do Save As... and then manually compare changed data with last save. Still I'd be extremelly suspicious of it.

MostAwesomeDude3• 15 years ago

I thought the message at the end about people expecting full correctness was a bit off; after all, if we expected fully-correct programs, we would be proving them instead of writing C.

ezyang• 15 years ago

They're poking fun at the formal methods community, which spends a lot of time doing research in this direction. Percolation of these techniques back to industry has been... less than stellar.

chrisfarms• 15 years ago

Can't think of a use-case for this? .... maybe if you have some seriously "legacy" process running somewhere that loves to stall but patching is not an option for some obscure reason? ... space probes?

mhd• 15 years ago

The RunStop key?

interesse• 15 years ago

Not even a single mention of the halting problem?

simonsarris• 15 years ago

I was surprised too. I expected a mention of it, and a link to the poetic and intuitive proof-story of why its a problem would be good for the story too.

In case other HNers haven't read Scooping the Loop Snooper, I (re)submitted it:

http://news.ycombinator.com/item?id=2838488

scott_s2• 15 years ago

The old thread with discussions on why the proof works: http://news.ycombinator.com/item?id=1321899

achompas2• 15 years ago

Noob question time: what's the halting problem?

romaniv• 15 years ago

It's mathematically impossible to write a program that always correctly determines whether an arbitrary piece of code will halt (rather than get stuck in an infinite loop). Making that determination is referred to as halting problem.

DasIch2• 15 years ago

Basically the halting problem states that it is impossible to determine whether or not a given program halts under the assumption that it is executed in a turing complete machine.

Due to the fact that a program is a composition of programs which at the lowest level are loops and instructions this also means that it is impossible to determine whether or not a loop halts.

ejames• 15 years ago

The halting problem:

Given a program and an input, determine whether that program, given that input, will ever halt, or if it will loop infinitely.

One of the fundamentals of academic computer science is learning that it is mathematically impossible to solve the halting problem - which is why the grandparent comment simply notes "the halting problem" with no further explanation; it's a famous problem. (Don't feel bad, everyone has to learn something the first time!)

The poem linked elsewhere in this comment tree is a simple and pithy description of the mathematical proof.

For (many) more details, Wikipedia has plenty of information.

onan_barbarian3• 15 years ago

The halting problem is an profound bit of theoretical CS well-explained on this thread.

However, the actual halting problem is moot in most of the references I see to it, as the halting problem is usually misused by the half-educated to make claims that 'nothing useful can ever be inferred about the behavior of any program, ever'.

For example, we built a tool to either estimate a reasonable ceiling on the stack usage (whole-program) or give up; it works very well and can detect when the structure of the program prevents this tool from operating correctly (nasty stack mischief or stack adjustments appearing in 'unusual' places). Quite useful for us, especially because we control the source code and know that we don't do naughty things to our own stack.

Entertainingly, on the way to build this tool, we encountered at a couple screeds about how this problem just plain can't be solved because it's equivalent to 'solving the halting problem'. Well, yes - in theory, but no - in practice.

DasIch2• 15 years ago

The halting problem doesn't apply.

w01fe• 15 years ago

Does your computer have an infinite tape?

jerf• 15 years ago

This wasn't written for "us". Look at the homepage: http://bostinnovation.com/

matthavener• 15 years ago

I've done this with MS Word and the VS debugger. Word crashed while I was editing a huge document. I simply skipped a few instructions down, returned to Word, saved the document, and restarted Word. When your options are either 1) crash, or 2) possibly recover to some working state, it's pretty easy to choose option 2.

edge17• 15 years ago

i wish i could do that for safari

1amzave• 15 years ago

You probably can:

  $ gdb /Applications/Safari.app/Contents/MacOS/Safari $PID

iTunes, annoyingly, uses Apple's stupid little "please don't ptrace me" flag, which is a minor inconvenience, but fairly readily circumventable.

zwischenzug• 15 years ago

Aren't event loops infinite loops where memory might be unchanged for a long time?

tedunangst• 15 years ago

Presumably the user would not activate Jolt in that case. And technically, unless the loop uses polling, it's not an infinite loop because the program isn't even running.

eps• 15 years ago

Even an event-driven loop needs to cycle now and then to service timers.

sidww2• 15 years ago

A good autosave mechanism seems to be a much better solution than this. While that would mean the loss of a little bit of data, it seems better than saving a potentially corrupt file or incorrectly inferring that a loop is infinite.

Phargo• 15 years ago

This seems like the software equivalent of smacking a car starter with a hammer to get it to turn.

jonsen• 15 years ago

Well more like smacking a Toyotas accellerator to get it to stop ;-)

nickdunkman• 15 years ago

I think the better way to do this would be to throw a "JoltException" which you could catch in your program if you wanted to, like any other exception.

It seems like it'd be a huge mess to try to write code succeeding the loop which tries to handle the case where your loop code didn't complete like you expected it to.

spambot2• 15 years ago

OP looks like a spammer for bostinnovation.com: http://news.ycombinator.org/submitted?id=pgatzke

civilian• 15 years ago

There's a fuzzy line between spammer & contributor.

spambot2• 15 years ago

I made the comment because Reddit has some bostinnovation.com spammers: http://www.reddit.com/user/joeymullette & http://www.reddit.com/user/chezral

I'm guessing they have employees who just post to social news sites.

SoftwareMaven2• 15 years ago

The only way this would be valuable for every day use would be for programs that produce "close" output. Think of things like large scale simulations where sub-simulations might go infinite, but if they do and this causes the output of the sub-simulation to change, it isn't likely to cause major changes in the macro-simulation.

Very little code is written that way, but when code is written that way, it allows much more interesting things to happen in software and hardware both.

scott_s2• 15 years ago

I think you missed the obvious examples of content-creation applications like Word or Photoshop, where you could interrupt an infinite loop, save progress, then restart.

SoftwareMaven2• 15 years ago

I didn't miss them. I think those will be much harder to reliably interrupt loops, especially around file I/O. That infinite loop was caused by bad state and those programs (currently) don't handle bad state well.

malkia• 15 years ago

It's common for the runtime of game scripting language to have infinite loop detections - for example if loop takes more than 5ms and hasn't reached (or called) specific point/mark then it's reported, stopped or restarted.

But going to the next line...

onan_barbarian3• 15 years ago

This is a good line of investigation. I don't understand all the harrumphing here, except possibly as a means of self-congratulations at to why the harrumpher in question didn't bother inventing this tool themselves and how they understand the "halting problem" in a way not known at MIT.

As the economist famously joked in response to 'how are you'... "Compared to what?" The comparison here is to killing the program and losing all the data.

Obviously there are some big limitations on this - especially given that the state of the program isn't necessarily entirely defined in terms of the process itself, but also a series of possibly stateful network connections and os resources.

Another big limitation is that a straight-up infinite loop at the level of the binary isn't necessarily the only way that a program could get stuck - we could be going around quite a complex loop at the binary level in response to an _interpreted_ loop, and killing the whole interpreter isn't necessarily going to return the program into a usable state.

That being said, what else are you going to do in this case? A number of the alternate solutions here seem to involve time travel.

Some fun possibilities - if you can replicate the OS state, and there's no important network state held open by the program, you can make a bunch of copies of the broken program and try lots of different approaches. You might also be able to fire up the program cleanly, get to the main event loop, identify what that looks like, and just magically splice that state back on top of the broken program in the hope that whatever is happening in global data structures is self-contained enough to recover from.

I understand that there are many reasons why this probably won't work... that being said, the baseline here is zero (especially if the users are made very aware that this program isn't a safety net of any kind and don't become more careless thinking that there's a magic 'fixit' program out there).

mcarbin• 15 years ago

I'm one of the authors of this paper and this comment pretty much hits it on the head. Jolt is an investigation in developing tools to help users get more use out of their programs when the alternative is failure. Because the reality is that there will always be programs that fail.

Most of the comments here are pretty fair about where Jolt might not be applicable (busy loops) and how this approach could be integrated with development; we touch on many these points in the paper (already linked by someone in the comments).

All of our emails are on the interwebs, so feel free to ping us if you want more information.

brandonwang• 15 years ago

What if you wrote an infinite loop, and wanted it that way?

There are plenty of legitimate uses for an infinite loop, a REPL, a server, etc.

AltIvan• 15 years ago

Oh look! there is a little note: "Do not use if you need an infinite loop not to stop."

jheriko• 15 years ago

my experience from debugging is that breaking out of a loop in this way is very hit and miss - coupling that with my experience of common office software failures being hard crashes rather than hangs and i can't imagine this tool being /that/ useful. I'd much rather have a tool that does autosaving at a very regular interval - I've written many throwaway tools for that in the past mostly when dealing with old versions of excel being abused to solve database/code problems... still this is better than nothing i guess

as for the nature of the halting problem meaning this can't work??? that only displays a lack of understanding...

all in all this article and the comments reinforce my view that academia diverges too far from the practical realities of software development. sure we need academic research and education, i won't deny it, but the noise making should be reserved for after practical success has actually occurred.

adamdoupe• 15 years ago

Link to the full paper for those interested: http://people.csail.mit.edu/rinard/paper/ecoop11.pdf

netmau5• 15 years ago

TLDR: Power button or inconsistent results, now you can choose.

MIT develops new tool that can interrupt infinite loops

Related Stories