Escaping Infinite Loops

twocentplain writes in with an MIT news release about Jolt, a research project designed to unfreeze software stuck in an infinite loop (for a subset of infinite loops). It uses a combination of static instrumentation (using LLVM) and a run time watchdog that checks the program state during loop iteration; when a duplicate state is detected it permits the user to take one a few actions to escape the loop. The authors claim it works well enough that the program can often continue operating properly. The original paper contains detailed case studies.

Comments

Loop invariants

[Anonymous Coward]

So you just jump to an address outside of the loop and hope that your loop invariant hasn't been violated?

Really interesting

[Harald Paulsen]

That's really interesting.
That's really interesting.
That's really interesting.
That's really interesting.
That's really interesting.
# duplicate state detected, jumping loop
Daisy, daisy, give me your answer do..

Halting Problem

[krovisser]

So we've solved the halting problem.

By making it the user's problem?

Wait a second...

Re:Halting Problem

[AdmiralXyz]

Joking aside, this really has nothing to do with the Halting Problem, because the Halting Problem is a statement about Turing machines, which have unbounded space. Actual computers are not Turing machines: because they have finite memory, they have a finite (though very large) number of states, and are actually finite-state automata.

Here, the Halting Problem doesn't really apply, because if all else fails, you can (in theory) take every combination of programs up to N bits in length, and every combination of inputs up to M bits in length, and make a table of size 2^(N + M) saying whether a given program halts on a given input by running it and looking for a duplicate state. Of course that's impossible in the real world, but it does demonstrate that there's nothing about this research that's violating established principles of computer science.

And in a sense, that seems to be what they're doing here: checking "has this program existed in this exact same state before?", because if it has, you're in an infinite loop. I seriously doubt it's as effective in the real world as they claim though: in my experience infinite loops simply don't happen in computing anymore. If your computer locks up, it's probably because you're in deadlock, or waiting on the disk or the network.

Re:Halting Problem

[dido]

True, as Marvin Minsky had once said: "...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine..." Emphasis in original. BUT, don't let that statement deceive you, as the number of states available to even a computer with very modest memory is so large that even the word 'astronomical' doesn't do it justice. For instance, my first real computer, a humble Commodore 64, with only 64K of memory, can have a total of 2^524288 (65536 * 8) states, something of the order of 1e157826 (yes, 157,826 zeroes after your one!) states. To give some idea of just how big that number of states is, were you to try to cycle through all such states at the astounding rate of 1e17 states per second (a theoretical 100 petahertz machine capable of cracking 56-bit DES keys in less than one second), it would still take 1e157801 years to go through them all. The heat death of the universe will have taken place after less than a thousandth part of that time has elapsed. As such Minsky goes on to say: "...the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness [of] the state diagram may not carry a great deal of significance." (Marvin Minsky quotes come from Computation, Finite and Infinite Machines, 1967).

Re:Easy...

[Baloroth]

I always thought the best method of getting out of infinite loops was to not have infinite loops. Everybody loves watchdogs and timers but they would be a reactive fix rather than a proactive fix.

I always thought the best method of getting out of infinite loops was to not have infinite loops. Everybody loves watchdogs and timers but they would be a reactive fix rather than a proactive fix.

Illiac had infinite loop detection

[uigrad_2000]

Here at the U of I, we built the 4th computer ever made: the Illiac

24 hours a day, an operator would sit at the computer to operate it. "Software" or jobs would be submitted by faculty. When one finished, the operator would load the next one.

Since only one job could be running at a time, it was quite important to detect infinite loops. The last bit of the ALU was connected to a speaker, and would produce sound similar to static when the computer was running correctly. If an infinite loop was encountered, then the static would suddenly hum a pitch, and the operator would kick out the job, and move to the next.

As the story goes, the very first machine music was written by a math professor, and submitted as an Illiac job, as a prank on the operator. Sometime around 3am, the operator picked up the next job and fed it to the machine. Immediately, the Illiac began playing "Hail to the Orange"!

Re:More like "Escaping non-Infinite Loops"

[kwiqsilver]

So...if the computer eventually gives in to entropy, it's not an infinite loop?