Slashdot Mirror
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.
bad programmers can now sink to new lows...
So you just jump to an address outside of the loop and hope that your loop invariant hasn't been violated?
If the software wasn't written properly to begin with, what metric are we now using to establish it is operating "properly" ?
A loop, by its nature, continues. If that didn't make sense, start reading this sentence again.
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've found that tasks waiting on resources without a reasonable timeout (or sometimes no timeout at all) and refusing to respond to outside stimuli are more often the problem than a task stuck in an infinite loop.
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..
Harald
So we've solved the halting problem.
By making it the user's problem?
Wait a second...
Last
Put a counter in all your loops. If the counter hits some arbitrarily ridiculous number throw an exception.
This goes contrary to my management's belief that if anything goes wrong the program should "crash and burn".
You are in a maze of twisty little branches. All alike.
>_
*this space intentionally left blank
"One of the four pointers saying 'come and see', and I saw, and beheld a white
Now if only they could get the software development unstuck from an infinite loop of project management, powerpoint slides, and TPS reports.
...if it goes into an infinite loop while trying to rescue another piece of code?
sig not found
Listen to your management. Generally: failing silently is worse than failing noisily (is worse than not failing at all of course).
In any case, your technique—unless you do a lot more analysis of your software than your comment suggests—will lead to a) lots of watchdog code cluttering up the logic and b) the software failing when it’s run on more data than you expected.
One thing I noticed in the article was this:
and because of some fundamental results in computer science, “I know for a fact that he’ll never be able to get it exactly right.” But, Weimer says, “The vast majority of infinite loops he will be able to figure out.”
Does this we can't get above a certain percentage of correct predictions, or does it mean that more and more work will converge towards 100% (99.5, 99.9%, 99.999% etc. etc.)
Why OpalCalc is the best Windows calc
You mean like the Zune Leap Year Bug which causes them to be unusable for a few days?
Well, there's spam egg sausage and spam, that's not got much spam in it.
Escaping the RDF.
Thanks, I'll be here all week. Tip your waitstaff.
Well, there's spam egg sausage and spam, that's not got much spam in it.
All these endless loops which i created just to let some background threads executing....
I thought this would be about how to get away from Apple headquarters.
Boy do I feel silly....
If you can escape the loop, it's by definition NOT an infinite loop, right?
This story was posted here last week, with many of same snarky observations.
I seem to remember the old norton crash-guard/anti-freeze utility that was somewhat useful in getting around problems like infinite loops in old Windows programs.
I'm pretty sure the way this worked takes advantage of the fact that windows programs are essentially structured as message-processing co-routines plugged into a infinite scheduling loop (the windows loop). Although mostly, messages are posted, sometimes these messages can go re-entrant and if poorly coded cause an infinite loop. Anti-freeze could be then "sprayed" on the app which would then try to insert or delete messages in the program's processing loop to help it exit the re-entrant part loop and go back to the main scheduling loop. Often this would work well enough to enter the "Save" menu processing part of the program to avoid losing work. It also attempted to handle traps effectively (things that often happen when a program runs past the end of an array if it's in an infinite loop) by suspending the main flow of the program and inserting another message and thread to try an allow for limited operation (like "Save" menu processing).
Unfortunatly, this technology wouldn't be that effective in todays environment (basically, it probably could be classified as malware/spyware so the defenses against malware/spyware woud probably prevent it from working), but it seems like bulding this into an application code development infrastructure seems like it might be a good idea...
From TFA: Jolt works in conjunction with a compiler, a program that translates code written in a high-level programming language into rudimentary instructions that a computer can understand. When an application is being compiled, Jolt marks the beginnings and ends of all the loops indicated in the source code. If the compiled application later stalls, Jolt simply forces it to skip ahead to the first instruction following the loop it’s stuck in.
.Net, for example, a .pdb gets generated when you compile in debug mode. You can certainly then attach a debugger to a program stuck in an infinite loop and tell the debugger to jump to the code following the loop. It sounds like they're just doing this in some automated way.
Wouldn't this be like using a symbol file? In
Of course this completely ignores any benefit of compiler optimization when compiled without symbols in "release" mode. Not to mention making it impractical to obfuscate your code to prevent disassembly. Seems like a really bad idea overall.
Back in my days as a software tester, that's basically what I would do when I suspected something was looping. Wedge a debugger into the running process, see how far the program counter was going, and see what registers were changing, and a quick look at the autos in the current stack frame. (Most autos would be in registers: this was not an x86-based system.)
I made no attempt to get the program to continue, though; once I was pretty sure it was in a loop, I'd then work out the minimum necessary circumstances to trigger it and log a bug report.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
This solution serves NO purpose unless it is also accompanied by a modal dialog with this text:
Infinite loop detected! Do you want to break the infinite loop?
With one button labelled "OK".
In my own code, even.
tasks(723) drafts(105) languages(484) examples(29106)
If that's a real use case scenario, thing must be really different in MIT than they are in the real world. Users, even with a technical background don't have a clue about what an infinite loops looks like, let alone open a debug and move out of it.
If that's the target audience, not having the overhead of the automatic detection for the other 99% and letting the tech savy fend for themselves with the debugger. Also, the scope is too limited.
As the paper itself says, it doesn't "detect loops due to recursion or unstructured control ". It could probably be fooled by some busy waiting loop.
Doesn't seem like a serious paper, or something that solves a serious problem.
Different solution. This isn't a watchdog, this is a, "hey, this program's been here before. And once it's been here, it'll go there. And then there. And then here. And it won't stop."
One bright side: The song that never ends...will.
tasks(723) drafts(105) languages(484) examples(29106)
I'm running on a micro-controller you insensitive clods!
The standard teaching language at Cornell in the mid-70s was PL/C, Cornell's version of the IBM PL/I Checkout Compiler. It didn't "fix" infinite loops, but if "fixed" a lot of simple syntax errors and some runtime errors like "divide by zero" or out-of-bounds array indexes.
Sure, it wasn't always reliable, and could even cause infinite loops rather than preventing them, but it still let you speed up the code-keypunch-wait-run-debug cycle a lot. Fixing the syntax errors meant that you could usually identify all your syntax errors in one run (especially simple ones like forgetting a statement-delimiting semicolon or using the wrong number of closing parentheses), and could often find where you had logic errors even though it didn't always do the right thing (e.g. replacing an out-of-bounds array index with "1" was seldom correct, but it told you you'd done something wrong.) Since the development cycle typically included "wait for a keypunch", "wait to put your cards in the reader" and "wait for your batch job to come out of the printer", and the computer labs got overcrowded when CS100 projects were due, this was a big win.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
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"!
Free unix account: freeshell.org
The Amiga could be soldered to add a button that would trigger the Non Maskable Interrupt, pressing this would throw you back into AsmOne if you got stuck :)
Can I light a sig ?
And listen to Riker this time around.
Just make 1 false. However, I can foresee a few unwanted side effects...
I found one in a shipping version of Xcode 4 last week. Steps to reproduce:
1. Create a project containing a library.
2. Drag the library into its own "Link Binary With Libraries" box.
3. Build.
It's not as uncommon as you think when you're dealing with apps that maintain complex, potentially cyclic (or at least heavily cross-linked) data structures under the hood.
Check out my sci-fi/humor trilogy at PatriotsBooks.
Moving the instruction pointer out of the loop could do more harm than good. It puts the code in an unverifiable state. I'd much rather get a crash dump with some sort of InfiniteLoopHereException.
The algorithm is:
1: Enter infinite loop
2. Invoke Jolt to escape from infinite loop.
3: GOTO 1
The state of an app is a lot more than just the state of the variables within the app.
For example, if you're reading from (and not writing to) a file, you have a file pointer that changes. If you get back to the same point in the FSM with a different file pointer value, it's not the exact same state. If the file pointer has the same value, it is. If you're writing to the file, it gets a lot more complicated rather quickly, but you get the basic idea.
Check out my sci-fi/humor trilogy at PatriotsBooks.
Hey, have you heard about the new Cray 2 computer? It is so fast, it can finish an infinite loop in under 10 seconds!
(That is how I heard it. They probably told the same joke about the IBM 360. Modern supercomputers aren't much faster at infinite loops, but they can do 20,000 at once.)
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
I have seen this case. It is not for infinite loops but just too long to process. I have seen it before in my preoptimized code. Usually when I give java script too much data.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
waiting for them to compile seems a lot like waiting for a lineprinter
Not the same thing...
The browser sets a timer and calls the javascript interpreter. When the call returns, it clears the timer. If the timer goes off before the call returns, it asks if you want to stop javascript. Maybe javascript was in an infinite loop. Maybe it was performing a complex task and was just about to quit on it's own accord. The timer doesn't differentiate.
This approach is a deeper probe (like being fisted by popeye vs your girlfriend sticker her finger in your asshole) -- it monitors the program state to find infinite loops.
Do you even lift?
These aren't the 'roids you're looking for.
bad start cookie
This reminds me of the Windows 7 Fault Tolerant Heap. When the OS detects frequent crashes of a program it may 'shim' the memory management operations (malloc/free) to prevent future crashes. This can, for instance, prevent a crash when a program references recently free'd memory; the OS will deliberately leak that memory and the program keeps on spinning. Double frees can also be automatically mitigated. The heuristics involved will actually analyze the results of these efforts and back out the 'shims' if necessary.
not intended for use in a nuclear installation
Lurking at the bottom of the gravity well, getting old
... Norris joke in here somewhere...
If you disagree with me on social issues, then it's pretty clear that you are a narrow-minded bigot.
What if you don't have an infinite loop, but your random input data make you look like one?
Any off-nominal condition I can detect and repair becomes a nominal condition. And I have well-tested code handling all nominal conditions. Thanks for the new design pattern, though. It'll come in handy.
From the subject line, I was sure this would be an article about career advice. Ah well, back to grind.
...is it really infinite?
I'm sure that'll go swimmingly! What's an indeterminate state between friends?
There are three valid ways to "handle" an infinite loop. Most commonly, just keep looping until the user kills the program. In the embedded world, the most common is that a watchdog timer hard resets the device. In some cases, use alarm and let SIGALRM terminate the program (possibly after a bit of debug log is written).
Otherwise, if the loop can be infinite due to external conditions, it should be handled by the programmer so things can be put in a determinate state.
Watchdog timers are common. I've seen the timer fire on my DirecTV receiver a few times. However, those strobe reset rather than trying to surgically exit a loop.
I would argue they are much more correct since reset is a well defined state.
The undecidable nature of the halting problem
...is true only of Turing machines, which have unbounded memory. In some ways, a linear bounded automaton is a better model for realizable computation than a Turing machine, and the halting problem is decidable on these.
You mean ... I can finally stop washing my hair!
Replace "throw an exception" with "kill myself with a core dump" and you have yourself a deal! I mean something like SIGABRT (a.k.a. abort()) or SIGQUIT. I can see value in preventing infinite loops, because faulty program exits tend reveal their errors more "naturally" than hung programs.
But exceptions are baaaad in this case. Exceptions can be caught and ignored. An infinite loop like this is a logic error and the entire program state must be considered suspect/unreliable.
Either this works for high-level stuff only or there is a _lot_ of magic added for the benefit of shoddy programmers getting away scot-free.
People have bad habits forming, but if they rely on other means to circumvent their own stupidity, then it really is enforcing bad habits to the core....how about just being smarter with your logical thinking?
Corollary: Don't use MS Word.
This was not your typical university project or even a system written by programmers. I used this technique in a monstrous behemoth ported from mainframe, most "API's" had been written over the past 40 years by non-programmers.... in Fortran. The whole system is one huge point of failure waiting to happen. If you think this is funny, it probably is, but the circumstances warranted this technique, because infinite loops happened more often than your average customer is willing to tolerate.
Comment removed based on user account deletion
how often do you actually find infinite loops (that you KNOW are infinite loops) in software that's actually been released?
Never, because I can't be sure. Though, when a program freezes up (happens almost daily to me) and one of my CPUs jumps to 100% usage and sits there for a few minutes, I get suspicious. I've never put any other structures that do that in my code (besides near infinite loops), so I am forced to assume: infinite loops.