Flow-insensitive Static Analysis for Detecting Integer Anomalies in Programs

This paper describes a static analysis algorithm to detect potential integer anomalies in software. Integer anamolies take place when arithmetic operations on integer values yield new values that cannot be represented in the range for the integer type. Two common integer anomalies are integer overflow and integer underflow. Unexpected behavior can result if an attempt is made to represent a value outside the range of the integer type. Such anomalies in integers representing buffer sizes can lead to serious buffer overruns that compromise the security of a system. In this paper, we present a flow-insensitive static analysis algorithm that detects such missing integer range validations. We walk the AST, build a constraint graph that records range relationships between variables, and use this to ensure that all interesting uses of integers have been verified. Although the analysis is not sound or complete, its performance is significantly better than a flow-sensitive approach. We ran the analysis on approximately 50 MLOC from future versions of Microsoft products. We successfully uncovered and fixed over 2000 such anomalies with an overall noise rate of as low as 6.76 percent.