Flow-insensitive Static Analysis for Detecting Integer Anomalies in Programs

Author(s): Dipanwita Sarkar, Muthu Jagannathan, Jay Thigarajan, Ramanathan Venkatapathy
Venue: IASTED Conference on Software Engineering
Date: 2007


Language: C/C++
Defect Types: Integer overflow, integer underflow, buffer overrun vulnerabilities
Uses Annotations: Yes
Requires Annotations: No
Sound: No
Flow-sensitive: No
Context-sensitive: No

This paper presents a new method for finding integer anomalies in C and C++ programs. Integer anomalies occur when integer-type variables can potentially overflow or underflow. When coding, programmers sometimes make assumptions about the results of integer arithmetic (example: x + y > x where x, y are unsigned integers). The method presented in this paper attempts to detect where these (implicit) assumptions are made in code and find places where those assumptions could be violated. There are many places where integer anomalies can occur in code, but this method focuses solely on integer anomalies which could result in security vulnerabilities. The method works by traversing the source's AST and labeling each integer expression node as range-bound or -unbound and each graph edge with a arithmetic relationship constraint (x + y > x). The method then traverses the AST again to find relationship constraints that are violated by unbound integer expressions. These violations are the n flagged as warnings. The authors state scalability as a primary goal, which leads them to examine each function as a separate unit instead of taking the call graph into account. Since the method cannot reason across inter-procedure boundaries, the authors provide a set of annotations that developers can use to provide hints to the analysis tool.

The authors implemented their technique in PREfast, which is a Microsoft tool to perform static analysis and provide an AST framework to external analysis tools. They evaluated their method on 15 different future Microsoft products (although they don't specify which products) ranging from 300 to 9,500 KLOC. Examining each function separately allows the method to run quickly; it took between 8 and 45 minutes to run on the target programs. Although the times seem long, the authors point out that the runtime is actually comparable to the compile time considering the size of the code. The method found over 2200 defects total and generated a total of 182 false positives. These results give an overall false positive rate of only 8.16 percent. The restriction to security-related integer anomalies may reduce its attractiveness for some projects, but the low false positive rate along with the compile-time-comparable runtime make this tool a good candidate for real-world projects.