This is a draft version of an article to appear in our departmental newsletter, Significant Bits (with links added).

Nearly all software ships with known bugs, and others are just lurking in the code waiting to be discovered. Some bugs are benign; for example, a page might not display correctly in a browser. But more serious bugs cause programs to crash unexpectedly or leave them vulnerable to attack by hackers. These bugs are difficult for programmers to find and fix. Even when the bugs are critical and security-sensitive, it takes an average of one month between initial bug reports and the delivery of a patch.

Rather than waiting for programmers to fix their bugs, or for hackers to find and exploit them, Professor Emery Berger’s group is designing systems to make software bug-proof. These systems allow buggy programs to run correctly, make them resistant to attack, and even automatically find and fix certain bugs. This work, developed jointly with Ben Zorn at Microsoft Research, was an important influence on the design of the Fault-Tolerant Heap that today makes Windows 7 more resistant to errors.

Defending Against Bugs

Berger and Zorn first developed an error-resistant system called DieHard, inspired by the film featuring Bruce Willis as an unstoppable cop.

DieHard attacks the widespread problem of memory errors. Programs written in the C and C++ programming languages – the vast majority of desktop, mobile, and server applications – are susceptible to memory errors. These bugs can lead to crashes, erroneous execution, and security vulnerabilities, and are notoriously costly to repair.

Berger uses a real-estate analogy to explain the problem of memory errors. Almost everything done on a computer uses some amount of memory—each graphic on an open Web page, for example—and when a program is running, it is constantly “renting houses” (chunks of memory) to hold each item, and putting them back on the market when they are no longer needed. Each “house” has only enough square footage for a certain number of bytes.

Programmers can make a wide variety of mistakes when managing their memory. They can unwittingly rent out houses that are still occupied (a dangling pointer error). They can ask for less space than they need, so items will spill over into another “house” (a buffer overflow). A program can even place a house up for rent multiple times (a double free), or even try to rent out a house that doesn’t exist (an invalid free), leading to havoc when the renter shows up. These mistakes can make programs suddenly crash, or worse: they can make a computer exploitable by hackers.

The way “addresses” are assigned also makes computers vulnerable. Houses (memory locations) with especially desirable valuables, like passwords, will always be on the same lot on the same street. If hackers can locate a password once, they can easily locate the password’s address on anyone’s version of the same program.

DieHard attacks these problems in several ways. First, it completely prevents certain memory errors, like double and invalid frees, from having any effect. DieHard keeps important information, like which houses are rented and which are not (heap metadata), out of a hacker’s reach. Most importantly, DieHard randomly assigns addresses—a password that has a downtown address in one session may be in the suburbs next time around. This randomization not only adds security but also increases resilience to errors, reducing the odds that dangling pointer errors or small or moderate overflows will have any effect.

Exterminating the Bugs

While Professor Berger is more than pleased that the DieHard work has influenced the Windows 7 Fault-Tolerant Heap, he hopes that Microsoft will adopt the technology that Zorn, Berger, and his Ph.D. student Gene Novark designed next, called Exterminator. Exterminator not only finds errors but also automatically fixes them. Exterminator uses a variant of DieHard (called DieFast) that constantly scans memory looking for signs of errors. DieFast places “canaries” – specific random numbers – in unused memory. Just like in a coalmine, a “dead” canary means trouble. When DieFast discovers a dead canary, it triggers a report containing the state of memory.

Exterminator next applies forensic analysis to these reports. With information gleaned from several users running a buggy program, Exterminator can pinpoint the source and location of memory errors. From that point on, Exterminator protects the program from that error by “padding” buggy memory requests to prevent overflows, and delaying premature relinquishing of memory to prevent dangling pointer errors.

Berger notes that since Microsoft already gathers information when programs crash, using techniques similar to those in Exterminator would be a natural next step to quickly find and fix memory errors.

Professor Berger is now tackling the problem of concurrency errors – bugs that are becoming more common with the widespread adoption of multicore CPUs. His group recently developed Grace, a system that prevents concurrency errors in C and C++ programs, and Berger hopes that some version of it will also gain widespread adoption as part of an arsenal to protect programs from bugs.