Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Programming

Escaping Infinite Loops 204

Posted by Unknown Lamer from the pc-losering dept.
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.
This discussion has been archived. No new comments can be posted.

Escaping Infinite Loops More

Escaping Infinite Loops

Comments Filter:

  • yipes (Score:2, Insightful)

    by Anonymous Coward

    bad programmers can now sink to new lows...

    • 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

      • waiting for them to compile seems a lot like waiting for a lineprinter

        • The free batch-job handler that most student projects used gave you 1 second of CPU time and 6-10 pages of output (depending on the year.) But if things were busy, it might take an hour between the time you queue up to put your cards into the reader and the time your printout arrives. A few years later, I was taking a compiler course at night, and could either do my work on a VAX shared with about 30-40 other people, or on a mainframe running a somewhat odd version of Unix, which usually only had a coup

    • Yes and no. Once the infinite loop had been detected, it can also be reported and characterized.

      Granted, it's no insurance policy against a faulty mission-control system on an airplane or in a nuclear facility, but it does represent an interesting facet of quality control.

    • Yeah, it's no different from ON ERROR RESUME NEXT, with the added benefit of adding a cost to correct programs.

      They'd have to save the state of the whole machine on every watchdog tick. Hashing the whole memory is out of question, you'd need to hash just pages written to since the last tick, and that requires setting up page faults on the rest (or some custom architecture with generational memory, also costly).

      Plus, there's absolutely no way to resume from such a loop when you detect it and still have the

  • Loop invariants (Score:4, Insightful)

    by Anonymous Coward on Tuesday August 02, 2011 @05:09PM (#36964980)
    So you just jump to an address outside of the loop and hope that your loop invariant hasn't been violated?
    • Comment removed based on user account deletion

      • >>My thought exactly. Not to mention that other operations performed by the loop (that are obviously malfunctioning) may be necessary for the program to proceed correctly even if they don't affect the loop invariant.

        I guess MAYBE if you write code defensively throughout your codebase, it might work. Though it seems a recipe for disaster unless it'd be a worse disaster for your code to freeze up. (Medical equipment, maybe? Yikes.) But programmers that are cautious to validate all their input and output

        • Don't your average, bog-standard windows programs run in an infinite loop? Does this account for that?

          • No, as you can see from the following, the standard Win32 message pump isn't an infinite loop...

            while(GetMessage(&Msg, NULL, 0, 0) > 0)
            {
                    TranslateMessage(&Msg);
                    DispatchMessage(&Msg);
            }

    • The loop invariant (assuming you know what it is) is not the state of your program, but only the state of your loop!

      If after several loops the state of the program is not changing, the loop obviously is not doing anything and is an endless loop ... well that was simple, don't get how you failed to see that.

      • I think it's a bit more complicated than that. If the loop were polling a device or address or something outside of the state of the program, the loop very well could be 'infinite' by that definition, but not malfunctioning.

      • Re: (Score:2)

        by arth1 ( 260657 )

        If after several loops the state of the program is not changing, the loop obviously is not doing anything and is an endless loop ...

        This is a false assumption. It may be reading a hardware value that hasn't changed yet - the state of the program will be the same.
        Or it might be running a loop that should run forever with the same state in normal conditions. Like a watchdog.

  • The authors claim... (Score:3)

    by Nikker ( 749551 ) on Tuesday August 02, 2011 @05:10PM (#36964986)

    The authors claim it works well enough that the program can often continue operating properly.

    If the software wasn't written properly to begin with, what metric are we now using to establish it is operating "properly" ?

    • Re: (Score:2)

      by drpimp ( 900837 )
      Not to mention that if you just jump out of the loop, the software state is probably (in most cases) invalid anyhow. Not that you are any worse off then just leaving it hung, but killing the process will most likely still be required unless it's a well written threaded app of sorts, but we probably wouldn't be having this discussion if that was the case now anyway right?

      • Re: (Score:2)

        by Urkki ( 668283 )

        Not to mention that if you just jump out of the loop, the software state is probably (in most cases) invalid anyhow.

        These days many programs are event based. I'd say there's a decent chance, that program is left in valid state, especially if loop is broken at the condition, and remaining code in the function is allowed to execute before function returns to the main event loop.

        • It could however open up new security holes. What today is a simple DOS (sending a packet that makes your software loop for ever) could now possible be turned into an exploit since the loop is terminated with whatever status it has now (which the attacker knows since he can play with the same software).

      • Re: (Score:2)

        by sjames ( 1099 )

        Actually, you could be in a much worse condition. With it hung, you don't then end up working with it's invalid output. If you let it continue it might return "SUCCESS" and cause further processing on garbage output.

    • It does the thing you made it to do in the amount of time you want it to do it.

    • Re: (Score:2)

      by Hatta ( 162192 )

      Isn't it impossible to determine a priori whether a given piece of software will halt? How can you then say that any software that doesn't halt isn't acting properly?

      • IANACS, but this seems different to the halting problem: if the program is a FSM (not the Noodly One) then one that repeatedly enters the same state with a short period is possibly in an infinite loop. The halting problem is more a question of being able to tell if a program given an input ever reaches its end without actually running it

        • Re: (Score:2)

          by bondsbw ( 888959 )

          Not really. Running the program/input in question is an option, so long as the executing environment itself always halts. It must somehow detect that the program/input in question does not halt, but then halt itself while returning that fact.

          The undecidable nature of the halting problem indicates that there is no executing environment for which this is true for all possible programs and inputs.

          This software appears to be able to answer that question for some programs and inputs.

          • The undecidable nature of the halting problem

            ...is true only of Turing machines, which have unbounded memory. In some ways, a linear bounded automaton [wikipedia.org] is a better model for realizable computation than a Turing machine, and the halting problem is decidable on these.

        • Re: (Score:3)

          by IICV ( 652597 )

          The halting problem is more a question of being able to tell if a program given an input ever reaches its end without actually running it

          Nope, that is incorrect. The Halting Problem is being able to tell if an arbitrary program will ever halt on a given input, even if you are allowed to run it. That's what makes it tricky, because even if you run a program for X time and it doesn't terminate, maybe you just didn't run it long enough - maybe if you run it for 2X time, it will terminate.

          The thing is, the thin

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

    • Re:Easy... (Score:5, Funny)

      by Baloroth ( 2370816 ) on Tuesday August 02, 2011 @05:14PM (#36965054)

      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.

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

    • Re: (Score:2)

      by sdBlue ( 844590 )
      One might argue that the function that is waiting on the resource with no timeout is itself an infinite loop (as to whether or not this fix would fix that, it would of course depend on error checking code being present and correct, after the loop exits...)

      • Good point. A task forever stuck in a wait state pending on a resource allocation would resemble an infinite loop. Though a task that's stuck in the pending queue by the scheduler may not ever show up as an infinite loop since it doesn't actually get scheduled to run anything. I wonder how a task like that would be handled differently than one with an actual infinite loop.

  • Really interesting (Score:4, Funny)

    by Harald Paulsen ( 621759 ) on Tuesday August 02, 2011 @05:11PM (#36965018) Homepage

    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 (Score:4, Funny)

    by krovisser ( 1056294 ) * on Tuesday August 02, 2011 @05:13PM (#36965042)
    So we've solved the halting problem.

    By making it the user's problem?

    Wait a second...
    • Isn't that the standard reply from developers and tech support?

    • Re:Halting Problem (Score:5, Interesting)

      by AdmiralXyz ( 1378985 ) on Tuesday August 02, 2011 @05:32PM (#36965282)
      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.

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

        Provided you had an infinite amount of computer time.

        Tell me, does the following program halt:

        very long int h = 1;
        while(h)
        h = hash(h);

        does it halt of

        • Even in theory you can't solve the halting problem on a finite amount of computer time since you can construct programs where the hash function takes an arbitrary (2^(size of memory)) amount of time to loop, and it may not cycle through zero.

          Sorry, but this is not correct. In the example you provided, you can determine whether the program will halt or run forever because h, however long it may be, can only take a finite number of values, and so the act of hashing h over and over is guaranteed to be periodic. Just keep running the program, keeping track of which values of h have been generated, until h = 0 (output HALTS) or until you see an already seen value of h (output DOES NOT HALT).

      • Re:Halting Problem (Score:4, Insightful)

        by dido ( 9125 ) <dido&imperium,ph> on Tuesday August 02, 2011 @09:51PM (#36967588)

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

      • No, it's still the halting problem. The GP was correct. They can't actually know if the program is in an infinite loop (halting problem) so they guess. Then, because they might be wrong they ask the user if they want to take an action to stop what "may" be an infinite loop. They've offloaded the real decision to a human and used a simple heuristic to help inform the human.

    • This doesn't solve the general case halting problem, only a specific subset of it. I could see this being useful in debugging phase of development, but not really for end users.
  • 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?

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

    • No it means that no Computer Program can work out whether a program is in an infinite loop or not (Halting Problem), so he'll have to use heuristics to work it out. You can't get a 100% , because if you did you would have violated something which is mathematically proven.

      • Re: (Score:2)

        by Twinbee ( 767046 )

        Yes, but my question was not if you could reach 100%, but whether you could *arbitrarily close* to 100% given enough effort.

        • Since we're talking about heuristics, given enough programs you could train it/program to be pretty close. But then you'd end up with a ton of false positives so its not very worth it. Plus the idea of force-exiting an infinite loop is a bad either anyway, so I'm not sure its worth it in any case.

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

      It means one of those two things is true, yes.

    • Re: (Score:2)

      by dgatwood ( 11270 )

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

      Depending on what you mean by "work", either the latter or none of the above. The ability to detect a repeated state in a finite state machine is dependent on two things:

      • Number of states your storage can hold. The more complex the app, the more states you have. The bigger the set of possible states, the more states you can go through
  • Escaping the RDF.

    Thanks, I'll be here all week. Tip your waitstaff.

  • All these endless loops which i created just to let some background threads executing....

  • when a duplicate state is detected it permits the user to take one a few actions to escape the loop.

  • Anyone remember Norton Crash-guard/anti-freeze (Score:3)

    by slew ( 2918 ) on Tuesday August 02, 2011 @05:42PM (#36965410)

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

    • Re: (Score:3)

      by ZiggyM ( 238243 )
      yes I had that [norton?] antifreeze program too over 15 years ago. It gave you the option to jump out of an infinite loop (at your own risk) and most of the time that was good enough to unfreeze the entire (16 bit) computer, save your files.

    • This reminds me of the Windows 7 Fault Tolerant Heap [technet.com]. 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'

  • From TF Paper

    Subject: Thanks

    I was writing a document in Word this morning, and after about an hour of unsaved work, Word went into an infinite loop that made the application completely frozen. So, having listened to your talks too many times, I got my debugger, paused the program, changed the program counter to a point a few instructions past the end of the loop, and let it keep running from there. Word went back to working as if nothing had ever happened. I was able to finish my document, save it, and c

  • I'm running on a micro-controller you insensitive clods!

  • Illiac had infinite loop detection (Score:5, Interesting)

    by uigrad_2000 ( 398500 ) on Tuesday August 02, 2011 @05:59PM (#36965608) Homepage Journal

    Here at the U of I, we built the 4th computer ever made: the Illiac [wikipedia.org]

    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"!

    • Fourth computer? Plenty of electronic computers were built in the 1940s before Illiac I, more than ten . Also, what happens if a program is doing algorithm where ALU is the same until some unique condition met? That's hardly a foolproof method of infinite loop detection
    • Probably would have gotten an even stronger response if it had played "On Wisconsin".
    • I listen for repeated hard drive noise when a machine seems to have hung. A lot of the time you can hear a "click...clickclickclick...click" repeating again and again (or something similar; usually a bit more complex) when it really has hung.

    • It's really cool to hear an early example of listening to code. "RAM scanning" was popular on the Amiga many years ago, and it was pretty easy to guess what kind of data was present in the system's memory just by listening to it. Images, code, pre-calculated tables, and text all had unique sounds, so just pumping some memory into the speaker was way faster than looking at a bitmap screen offset or using a hex editor. I used to be able to rip Soundtracker music from games with only a sound editor and noth

  • Just make 1 false. However, I can foresee a few unwanted side effects...

  • The algorithm is:

    1: Enter infinite loop
    2. Invoke Jolt to escape from infinite loop.
    3: GOTO 1

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

  • ... Norris joke in here somewhere...

  • What if you don't have an infinite loop, but your random [dilbert.com] 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.

  • Yow! (Score:2)

    by sjames ( 1099 )

    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 thi

    • Re: (Score:2)

      by emt377 ( 610337 )

      In the embedded world, the most common is that a watchdog timer hard resets the device.

      This only works if the watchdog poke isn't inside the infinite loop.

      I actually think this is an excellent tool, not so much to notify users but as a debugging and test aid. Add it to valgrind/helgrind. Tell me when an iteration of a loop doesn't result in a change in state - this is clearly an anomaly and tells me it is dependent on an external condition to unwedge. Loops which are intended to wait for external events (like a spin lock or other atomic operation) I can flag as such to exempt from the inst

      • Re: (Score:2)

        by sjames ( 1099 )

        Detecting an infinite loop as a debugging tool is quite a different matter! I agree that that is a useful thing. Detecting the loop and resetting in a production embedded system is also good if the detection isn't too much load on the system and it doesn't have false positives.

        My objection is to the idea of just moving to the next line and assuming all is fine now.

    • I imagine this could be useful for debuggers. Of course I didn't RTFA.

Slashdot Top Deals

Math is like love -- a simple idea but it can get complicated. -- R. Drabek

Close