Defibrillator for stalled software

August 3, 2011
Defibrillator for stalled software
Graphic: Christine Daniloff

It’s happened to everyone: You’re using a familiar piece of software to do something you’ve done a thousand times before — say, find a particular word in a document — and all of a sudden the program just stops working. You click the cursor and move the mouse, but nothing changes on-screen, and finally you just quit the program, losing whatever work you’d done since the last time you saved.

Often, a stalled program has gone into what computer scientists call an infinite loop, where it keeps executing a single block of code over and over. At the 25th European Conference on Object-Oriented Programming in Lancaster, England, in July, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) presented a new tool that automatically interrupts infinite loops and moves on to the next line of code in the computer program. In tests, their system restored five different programs to stable enough states that data could be saved and the programs exited safely; in the majority of cases, the programs also provided at least a partial solution to the computations they were trying to perform when they got hung up.

Loops are among the most basic building blocks of computer programs. They allow a programmer to specify, in a single step, a procedure that has to be performed on many pieces of data in sequence. For instance, the search function in a word processor might have to look at thousands of individual letters in even a fairly short document, comparing each of them to the letters in a search term. If it doesn’t find a match, it will move onto the next letter and “loop” back to re-execute the code that does the comparing.

Wheel spinning

A commercial program might contain tens of thousands of loops, and a slight error in the code for any one of them could lead to an infinite loop, in which the computer doesn’t know when to stop repeating the same operation. Computer science professor Martin Rinard and his graduate students Michael Carbin, Sasa Misailovic and Michael Kling developed a software tool that they call Jolt, which recognizes infinite loops by monitoring the program’s use of memory. A computer user who’s worried that his or her computer has entered an infinite loop could activate Jolt, which would take a series of “snapshots” of the computer’s memory after each iteration of a loop.

“The snapshots could be completely different,” explains Carbin, who is first author on the paper. “That can be an indicator that your program is computing. It may be doing something useful for you, so maybe you don’t want to break out of this. But if it’s not, and it has exactly the same state, then clearly it’s stuck in an infinite loop.”

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.

Keeping tabs on all the loops in a program, however, causes it to run 7 or 8 percent slower, Carbin says. And getting commercial software developers to use Jolt when compiling their code could be a tall order. So the CSAIL researchers are working on a version of Jolt that operates directly on compiled applications, whose instructions consist entirely of fixed-length sequences of binary numbers. This binary version of Jolt, the researchers explain, will be called Bolt.

Course correction

Bolt uses the same infinite-loop detection mechanism that Jolt did, and in early tests, it seems to work well with binary files. The steeper challenge is determining what instruction to jump to once a loop has been identified. A function written in a high-level programming language might invoke other functions, which could invoke still other functions. But at the binary level, those nested function calls just look like a long list of numbers. Figuring out where one function ends and another begins is no easy task.

But Kling has developed a clever algorithm that can identify the highest-level function in operation at a given time — the one that has initiated all the others — which could help Bolt orient itself. And even if the system can’t make an informed decision, Rinard explains, it could just start hopping around to new instructions at random, until it finds one that breaks the impasse.

Randomly modifying code on the fly may sound antithetical to the whole idea of computer engineering, but it’s an approach that’s paid off for Rinard’s group, in research on websites that can weather malicious attacks and software that adjusts to changing hardware conditions, among other things.

“The vast majority of software engineering or programming-language researchers are shackled to this notion of full correctness or full soundness: You can’t change anything in the program if there’s even the possibility of getting a slightly wrong answer,” says Westley Weimer, an assistant professor of computer science at the University of Virginia. “One of the things that’s really characterized Martin’s research over the last 10 or 15 years is casting off the shackles of soundness in favor of approaches that are probably correct but dramatically more useful in real life.”

Weimer acknowledges that for Bolt, determining what instruction to jump to is a “difficult” problem, and because of some fundamental results in , “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.” There might be a few instances where Bolt will guess wrong, Weimer says. “But the comparison — and this is important for this kind of work — is that if he doesn’t jump, you’re stuck in an infinite loop. The comparison is not that it was working fine and he messed it up.”

Explore further: Boosting ‘green’ computing with new approach to programming

Related Stories

Real-world programming in the classroom

October 28, 2010

In undergraduate computer-science classes, homework assignments are usually to write programs, and students are graded on whether the programs do what they're supposed to. Harried professors and teaching assistants can look ...

Streamlined rules for robots

June 13, 2011

With the explosion of the Internet and the commoditization of autonomous robots (such as the Roomba) and small sensors (such as the ones in most cell phones), computer scientists have become more and more interested in distributed ...

Free tool kit to assist big-data scientists

July 19, 2011

Two years ago, during a cyberinfrastructure meeting convened by the U.S. National Science Foundation, principal investigators from across the country found their scientific concerns begin to converge.

For software developers, more speed and mobility

December 14, 2010

Across the globe, technology and innovation are becoming increasingly more reliant on mobility and accessibility. For software developers working on highly complex projects, that means being able to save their work quickly ...

Computer learns language by playing games

July 12, 2011

Computers are great at treating words as data: Word-processing programs let you rearrange and format text however you like, and search engines can quickly find a word anywhere on the Web. But what would it mean for a computer ...

Recommended for you

Automated safety systems are preventing car crashes

August 23, 2017

Safety systems to prevent cars from drifting into another lane or that warn drivers of vehicles in their blind spots are beginning to live up to their potential to significantly reduce crashes, according to two studies released ...

Newest solar cells underperform in cloudy countries

August 22, 2017

To determine how efficient new solar cells convert sunlight into electricity, small sample cells are tested under ideal conditions. However, the reported efficiency is not very representative of the actual annual yield when ...

Google to serve next version of Android as 'Oreo"

August 22, 2017

An upcoming update to Google's Android software finally has a delectable name. The next version will be known as Oreo, extending Google's tradition of naming each version after a sweet treat.

Forget oil, Russia goes crazy for cryptocurrency

August 16, 2017

Standing in a warehouse in a Moscow suburb, Dmitry Marinichev tries to speak over the deafening hum of hundreds of computers stacked on shelves hard at work mining for crypto money.

Researchers clarify mystery about proposed battery material

August 15, 2017

Battery researchers agree that one of the most promising possibilities for future battery technology is the lithium-air (or lithium-oxygen) battery, which could provide three times as much power for a given weight as today's ...


Adjust slider to filter visible comments by rank

Display comments: newest first

2.7 / 5 (3) Aug 03, 2011
A wise man once said that an ounce of prevention is better than a pound of cure, and brother, let me tell you, this is one steaming pile of cure.
3.7 / 5 (3) Aug 03, 2011
Anything that beats Ctrl-Alt-Del would be an improvement...
3.9 / 5 (7) Aug 03, 2011
Sigh! Tools exist which can guarantee that a program will never get stuck in a loop like this. More important the tools check for other problems that can be caused by the interaction of multiple threads. These tools are used all the time in safety-critical applications.

Unfortunately, there are lots of cowboys out there programming, and a lot of them live in or around Redmond, Washington. They believe that they have a better idea than a program about whether or not their code can get stuck in a loop. (You know where I would love to stick them. ;-)

On the other hand, most of the reason they don't know better is that they have only learned programming languages in the C family. The problem is that a good real-time diagnostic is often difficult for C code. (You want a diagnostic that points to the bad line of your code, not somewhere 50 pages later in someone else's code.)
3 / 5 (2) Aug 04, 2011
Excellent! - When do we start using it in aircraft and nuclear reactors?

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.