MIT Boffins Reveal Groundbreaking Integer Overflow Debugger

bug

New algorithm can identify integer overflows, one of the most widely encountered bugs in computer programs

Researchers at the MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) are to demonstrate a new algorithm that could dramatically improve the stability of computer programs in the future.

The new algorithm will be shown at the Association for Computing Machinery’s International Conference on Architectural Support for Programming Languages and Operating Systems, and it identifies integer overflows, one of the most commonly encountered bugs in computer programs.

Integer Overflows

At the moment there are a variety of techniques to identify integer overflows, but according to the researchers, all these current methods have their drawbacks. They believe they have a better solution, after they tested their algorithm on five common open-source programs.

Traditional techniques discovered three bugs with those five common open-source programs, but the new algorithm apparently found all three known bugs, as well as 11 new ones.

Bug (c) bofotolux, Shutterstock 2014The researchers revealed that variables used by computer programs come with a few standard types, such as floating-point numbers, which can contain decimals. Alternatively they can contain characters or even integers, which are whole numbers.

Every time the program creates a new variable, it assigns it a fixed amount of space in memory,” said the MIT researchers. If a program tries to store too large a number at a memory address reserved for an integer, the operating system will simply lop off the bits that don’t fit.

“It’s like a car odometer,” said Stelios Sidiroglou-Douskos, a research scientist at CSAIL and first author on the new paper. “You go over a certain number of miles, you go back to zero.”

Integer overflow don’t crash a program by themselves, and it is true that they are sometimes used by  programmers to perform certain types of computations more efficiently. But if a program tries to do something with an integer that has overflowed, problems can occur.

The researchers highlight when the integer represents the number of pixels in an image the program is processing. If the program allocates memory to store the image, but its estimate of the image’s size is off by several orders of magnitude, the program will crash.

But the researchers have identified a way to track these problems down, and when their system discovered that a program has reached a point at which an integer is involved in a potentially dangerous operation – like a memory allocation – their system dubbed DIODE (for Directed Integer Overflow Detection) can analyse the problem.

“DIODE provides an effective mechanism for finding dangerous integer overflows that affect memory allocation sites, the source of many critical security vulnerabilities,” said Cristian Cadar, a senior lecturer in computing at Imperial College London.

“DIODE is based on symbolic execution, a state-of-the-art technique that provides the ability to automatically explore and analyse paths through a program by modelling these paths as mathematical formulas. In DIODE, symbolic execution is specifically optimised to find integer overflows that affect memory allocation sites, by enhancing it with a novel exploration mechanism that enables it to synthesise dangerous inputs that reach the overflow target. On the practical side, DIODE operates directly on binaries, making it easy to find critical bugs and security vulnerabilities.”

Bug Bounties

The ability to track down and identify bugs is a potentially lucrative business, and some researchers can make money from so-called “bug bounties, where large firms offer financial rewards for the discovery of bugs and vulnerabilities in their offerings.

Last year, Google revealed the existence of Project Zero, which is a team that is tasked  to spot and fix critical vulnerabilities before they can be used in cyber attacks.

Google’s bug hunting team however has not proved popular with its tech rivals such as Apple and Microsoft, as the team tends to publicly disclose bugs if the vendor has not fixed it within the allotted time frame.

How well do you know network security? Try our quiz and find out!