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.
Compensating for failure to design properly at the compiler level scares me.
Sure, I've written infinite loops, and encountered them while debugging. But how often do you actually find infinite loops (that you KNOW are infinite loops) in software that's actually been released?
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
This is an interesting, and no doubt fairly useful piece of software, but, now, correct me if I'm wrong - if a program is coded as a finite state machine there'd be instances of duplicate states that can appear to be "hung," in which case this software would only do harm, no?
So we've solved the halting problem.
By making it the user's problem?
Wait a second...
Pretty sure most browsers do this now. (even IE, even Flash actually)
When loop has been running too long, it halts and asks if the user wants to continue running it.
I'm guessing it is a whole different ball-game when it comes to interpreted versus compiled?
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.
This is done routinely on the Parallax Propeller multicore microcontroller. In general, CPU cores can easily watchdog each other.
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
Sounds like Norton CrashGuard, a Symantec product that came out in the mid-90's bundled with Norton Navigator and, if I recall correctly, PC Handyman.
Disclosure: I worked for Symantec at the time and made a major contribution to CrashGuard - the background graphic.
Presumably, one would not use it on a finite state machine.
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?
I'm not sure if you're going for a funny, or if you are a terrible programmer.
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
Bypass the interface
I imagine the software does the best it can to look at everything involved in arriving at the loop and tries to take the user to the nearest user-interruptable point just before the loop occured. If the program could also keep track of registers and variables for some number of changes or period of time, then it could even restore any relevant variables to what they were at the exact moment it decides to take you back to, and with all that work why not also make it spit out debugging for the state it had to break out of? Does this thing do all that? Who wants to write something like that?
Wow, cool idea! If it's good enough you can just roll it into the program and it'll work like you want (end sarcasm).
This sounds like a terrible ID for programs written by people for a specific goal. It could be useful for artificial intelligence. We could presume that a learning algorithm would make the infinite loop mistake sometimes.. Being able to break from the loop and try something else would be useful.
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".
Seems your keyboard handler was stuck in an infinite loop, so I jumped out of the loop for you. You can thank me later...
It's east, look at the post below mine
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.
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...
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.
There is no duplicate state
A duplicate state is forbidden by quantum mechanics
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.
waiting for them to compile seems a lot like waiting for a lineprinter
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.
I hate things that make badly written or poorly configured software "mostly" work. How about something that makes software fail unless it's written correctly in the first place?
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.
Oh. Debugging code. I thought this was about escaping Apple.
It just works on iOS
(joke, funny, haha... lighten up)
We all know Linux is great it does infinite loops in 5 seconds. (unsourced alas)
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