Software nudges frozen computers out of infinite loops
By Ben Coxworth
August 3, 2011
There are few things as maddening as being in the middle of a task on a computer, and having the software freeze up on you. This can be particularly enraging if you haven't backed up your work recently, and you know that the only way of "thawing out" the program will be to execute a force quit - your work will be lost, all because the (insert word of your choice here) computer didn't know what to do next. Fortunately, however, researchers from MIT's Computer Science and Artificial Intelligence Laboratory have developed a tool that jolts stalled programs back into action.
Programs commonly contain thousands of loops, that allow the computer to perform the same task over and over, such as systematically comparing each letter in a document to those in a search term. Should there be a slight error in the code, however, the computer can get stuck in an infinite loop, performing the exact same function indefinitely - it could keep comparing the same letter, for instance, instead of moving on to the next one.
In order to get computers out of infinite loops, MIT computer science professor Martin Rinard and his graduate students Michael Carbin, Sasa Misailovic and Michael Kling have created a software tool that is appropriately named Jolt. When activated by a user who thinks their computer might have frozen up, Jolt takes a series of "snapshots" of the computer's memory after each run of a loop. If all of those snapshots are identical, then the machine is indeed stuck in an infinite loop.
Jolt then instructs the computer to move on to the next instruction within the program. In order to be able to do that, however, Jolt must first be aware of the beginning and end points of all the loops within the program's source code. This requires it to also be used by software developers, when their complex programming language is being compiled into computer-friendly binary.
Getting developers to use Jolt could be asking a lot, however, plus it causes programs to run 7 to 8 percent slower. To get around these limitations, Rinard and his team are now working on a binary edition of the software, called Bolt. It is able to work directly on compiled, binary versions of programs. One of the challenges in the development of Bolt is the identification of the beginning and end points of loops in binary code - whereas such points are relatively easy to spot in programming language, they can difficult to locate within the strings of numbers that make up binary.
Kling has addressed this problem by developing an algorithm that allows Bolt to identify the highest-level function that is running in a program at any one time. If that still doesn't provide enough information, then Bolt could conceivably even just start searching for new instructions at random, until it finds one that allows the program to move on. Although going to that next instruction might not be the perfect choice for the smooth running of the program, it would at least get the computer out of the loop, so that the user's work could be saved.
The MIT team presented Jolt at the 25th European Conference on Object-Oriented Programming in Lancaster, England, last month.