MIT Finds Overflow Bugs
Written by Mike James   
Wednesday, 08 April 2015

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.


odometerAn 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. 

odometer

More Information

Targeted Automatic Integer Overflow Discovery Using Goal-Directed Conditional Branch Enforcement Sidiroglou-Douskos, Stelios; Lahtinen, Eric; Rittenhouse, Nathan; Piselli, Paolo; Long, Fan; Kim, Deokhwan; Rinard, Martin

Related Articles

Code Digger Finds The Values That Break Your Code       

Code Hunt - New Coding Game From Microsoft Research       

Microsoft Research creates a JavaScript malware scanner

Free Combinatorial Testing Tool

Code into PDF flow charts

New tool detects RegEx security weakness

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter

 

Banner


Swift 6 Improves Linux Support
23/09/2024

Apple has released Swift 6, with improvements to support for writing concurrent code, specifically a new, optional language mode that analyzes your code at compile-time and diagnoses possible data rac [ ... ]



Watch The Oregon Programming Language Summer School Lectures
20/09/2024

Each year, the Oregon Programming Language Summer School covers topics in the foundations of programming languages. All the recordings of the lectures that took place during this year's event are now  [ ... ]


More News

 

kotlin book

 

Comments




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

 

Last Updated ( Wednesday, 08 April 2015 )