MIT Algorithm Lays Path to Safer Code
- By Dian Schaffhauser
- 03/25/15
A team of MIT researchers has come up with a system that can generate inputs to trigger intentional integer overflows to help identify
security vulnerabilities in code. Integer overflow errors make up a prime target for code injection attacks by malicious hackers. Although a
number of techniques have been developed over the years to identify them, none is foolproof because integer overflows are frequently used for
legitimate programming purposes too.
The new algorithm created in MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) was tested against five open source
programs that had previously been checked; the new technique found three known bugs and 11 new ones. (In fact, the researchers noted, at least
four of the new overflow errors still exist in current versions of some of those applications.)
The new system, named DIODE (for Directed Integer Overflow Detection), follows a two-step process. First, it identifies "sanity checks" on
relevant input fields; then it generates inputs that satisfy those sanity checks to trigger the overflow.
Typically, if input doesn't pass a sanity check, the program gives an error or warning message and stops processing the input. Because
DIODE is intended to trigger an overflow, it follows a dodgy path, built as a mathematical formula. It feeds the program a single sample input.
As the program chews on the input, the system records each operation performed on it by adding new terms to what's known as a "symbolic
expression."
When the program reaches a point at which an integer is involved in a potentially dangerous operation — such as a memory allocation — DIODE
records the state of the symbolic expression. The initial test input may not trigger an overflow, but DIODE can analyze the symbolic
expression to come up with an input that will.
Then DIODE seeds the program with its new input. If it fails that check, it imposes a new constraint on the symbolic expression and
computes a new overflow-triggering input. This process continues until the system either finds an input that can pass the checks but still
trigger an overflow or concludes that triggering an overflow is impossible. When DIODE finds a trigger value, it reports it for the
developers to address.
Interestingly, DIODE doesn't have to work on source code; it can operate on the executable version of the program, enabling the program's
users to capture information and report it to the developers as evidence of a security vulnerability.
The paper that explains DIODE, "Targeted Automatic Integer Overflow Discovery Using Goal-Directed Conditional Branch Enforcement," was
presented this month at the Association for Computing Machinery's International Conference on Architectural Support for Programming Languages
and Operating Systems (ASPLOS) in Istanbul.
About the Author
Dian Schaffhauser is a former senior contributing editor for 1105 Media's education publications THE Journal, Campus Technology and Spaces4Learning.