Slashdot Mirror

← Back to Stories (view on slashdot.org)

Escaping Infinite Loops

Posted by Unknown on 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.

27 of 204 comments (clear)

  1. yipes by Anonymous Coward · · Score: 2, Insightful

    bad programmers can now sink to new lows...

  2. Loop invariants by Anonymous Coward · · Score: 4, Insightful

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

    1. Re:Loop invariants by FrankieBaby1986 · · Score: 2

      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.

      --
      ERROR: SIG NOT FOUND (A)bort, (R)etry, (F)ail?:
  3. The authors claim... by Nikker · · Score: 2

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

    --
    A loop, by its nature, continues. If that didn't make sense, start reading this sentence again.
    1. Re:The authors claim... by newcastlejon · · Score: 2

      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

      --
      If God forks the Universe every time you roll a die, he'd better have a damned good memory.
    2. Re:The authors claim... by F.Ultra · · Score: 2

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

    3. Re:The authors claim... by IICV · · Score: 2

      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 thing a lot of CS people don't know or forget, is that a lot of the time when we say something is hard or impossible, what we're really saying is "there exists at least one case for which this is hard or impossible".

      So, you know, Travelling Salesman? Not that hard, if there's only a hundred nodes or so. Especially if it's the subset of the TSP we see in reality; in real life, moving a little bit east will put you a little bit closer to everything in the east, which is not true at all in the general TSP.

      Halting Problem? Totally doable, on a lot of the programs you're likely to see out in the real world; after all, they're all supposed to terminate. It's not like people write programs that loop trickily on purpose specifically to confuse halting problem solving programs. A well written halting problem program could probably catch like 80-90% of unintentional infinite loops.

  4. Really interesting by Harald+Paulsen · · Score: 3, Funny

    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
    1. Re:Really interesting by grimmjeeper · · Score: 2

      I'm sorry Dave. I'm afraid I just can't do that.

  5. Halting Problem by krovisser · · Score: 4, Funny

    So we've solved the halting problem.

    By making it the user's problem?

    Wait a second...

    1. Re:Halting Problem by AdmiralXyz · · Score: 4, Interesting

      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.

      --
      Dislike the Electoral College? Lobby your state to join the National Popular Vote Interstate Compact.
    2. Re:Halting Problem by serviscope_minor · · Score: 2

      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 hash == md5? sha1? whirlpool? some PRNG?

      What if very long int is 2^32 bits long?

      Will the program terminate?

      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.

      Also, as well as infinite time, you need infinity squared memory.

      --
      SJW n. One who posts facts.
    3. Re:Halting Problem by dido · · Score: 3, Insightful

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

      --
      Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
    4. Re:Halting Problem by benhattman · · Score: 2

      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.

  6. Re:Easy... by Baloroth · · Score: 4, Funny

    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.

    --
    "None can love freedom heartily, but good men; the rest love not freedom, but license." --John Milton
  7. Re:Infinite loops aren't the real problem by sdBlue · · Score: 2

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

  8. Re:Another advanced techiique to escape invinite l by Anonymous Coward · · Score: 2, Informative

    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.

  9. Re:Does This Really Happen? by UnknowingFool · · Score: 2

    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.
  10. Re:Easy... by gl4ss · · Score: 2

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

    this is the infinite loop watch-- yo dawg, it seems you like repeating so we put an infinite loop in your infinite loop.

    --
    world was created 5 seconds before this post as it is.
  11. Anyone remember Norton Crash-guard/anti-freeze by slew · · Score: 2

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

    1. Re:Anyone remember Norton Crash-guard/anti-freeze by ZiggyM · · Score: 2

      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.

  12. Illiac had infinite loop detection by uigrad_2000 · · Score: 5, Interesting

    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
    1. Re:Illiac had infinite loop detection by Waccoon · · Score: 2

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

      I wish I could still do that on a PC. It'd be cool to see what a memory looks and sounds like with a modern OS, even though it'd probably be fragmented to hell.

  13. Re:More like "Escaping non-Infinite Loops" by kwiqsilver · · Score: 3, Insightful

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

  14. A Great Solution by camionbleu · · Score: 2

    The algorithm is:

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

  15. Re:Easy... by ObsessiveMathsFreak · · Score: 2

    Mother of God.... It's FORKING!!!

    --
    May the Maths Be with you!
  16. LBA vs. Turing by tepples · · Score: 2

    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.