It is the oldest bug - overflow has dogged any attempt to create a good program ever since we started writing code. Now MIT has an improved system to find overflow bugs by examining code.

An overflow bug occurs when any arithmetic produces a result that is too big to be represented in the available hardware. In the early days of programming it was a particular problem because 8-bit hardware was the norm and most arithmetic quickly runs out of bits and causes an overflow. Even today 8-bit hardware is found in embedded devices and medical devices provide an example where an unexpected overflow can mean the difference between life and death.

There have been previous attempts to detect overflow problems by examining code, but the new approach by the MIT team is claimed to be significantly better - finding all the overflow bugs found by the previous methods and some. The new algorithm was tested on five open source projects and it found the three bugs that the previous analysis had located plus 11 more. 

The way that it works is to first analyse the program's flow graph, i.e. the number of possible ways through the program's code. Each input applied to the program results in it following a single path through the flow graph. In principle, you can find all overflow errors by starting at the beginning and keeping track of what happens to the data. In practice this quickly becomes overwhelmed by the number of possible paths. This means that the current overflow finders tend to find problems early in the code but not deep in the flow graph.

The new approach, created by researchers at CSAIL, takes a single sample input, tracks it through the flow graph and records the symbolic expression corresponding to the operations performed on it. Whenever an operation occurs that could be damaged by an integer overflow the system, named DIODE for Directed Integer Overflow Detection, records the corresponding symbolic expression. The clever part is that DIODE next works out an input that that might cause an integer overflow. The reason why it is only "might" is that it is possible that the system has input checks that cause the program to take the constructed input to a different part of the flow graph where an overflow doesn't occur. 

If DIODE does find an overflow it can provide debug information consisting of the input and the location of the overflow. It also operates directly on the x86 binary files, making testing of deployed code possible. 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info