Back to results
US 7,624,304 B2Granted
Defect detection for integers
AssigneeMicrosoft Corporation
InventorsJayaraman Thiagarajan, Ramanathan Venkatapathy
Life of this patent
Estimating the term…
Abstract
Various techniques can be used to detect programming defects relating to the use of integers. A data structure can be created to represent ordering relationships in software instructions. Such ordering relationships can represent common unsound programmer assumptions. After annotating the data structure, unvalidated ordering relationships can be identified. Validation can use both explicit and implicit techniques. Filtering can be used to focus on only significant integer expressions, such as those used in buffer operations. For example, buffer accesses that attempt out-of-bounds buffer accesses due to integer overflow can be detected.
Claims12
One or more computer-readable storage media having computer-executable instructions for performing a method comprising:
- for a set of one or more integer expressions in a plurality of program instructions, responsive to encountering the one or more integer expressions, creating representations of ordering relationships between respective of the one or more integer expressions, wherein the ordering relationships represent a programmer assumption that an integer will not overflow or underflow;
- determining which of the ordering relationships are explicitly validated by one or more of the program instructions, the one or more of the program instructions, when executed, performing a bounds check to determine whether one of the one or more ordering relationships are satisfied;
- and
- identifying one or more ordering relationships that are not explicitly validated by the program instructions as unvalidated ordering relationships, wherein the unvalidated ordering relationships are indicative of at least one defect in the program instructions;
- wherein the creating representations of ordering relationships comprises creating a graph having directed edges, the graph comprising a first node representing a first one of the one or more integer expressions, a second node representing a second one of the one or more integer expressions, the first and second nodes connected by a directed edge representing at least one of the ordering relationships, the at least one of the ordering relationships relating the integer expressions represented by the first and second nodes and based at least on a greater than, a less than, a less than or equal to, a greater than or equal to, or an equal to relationship.
2 more elements
One or more computer-readable storage media having computer-executable instructions for implementing a software defect detection tool comprising:
- a store operable to store a representation of program instructions, wherein the representation identifies ordering relationships between integer expressions of the program instructions created responsive to detecting the integer expressions in the program instructions, the ordering relationships representing a programmer assumption that an integer will not overflow or underflow, the representation comprising a graph having directed edges, a first node representing a first one of the integer expressions, a second node representing a second one of the integer expressions, the first and second nodes connected by a directed edge representing at least one of the ordering relationships, the at least one of the ordering relationships relating the integer expressions represented by the first and second nodes and based at least on a greater than, a less than, a less than or equal to, a greater than or equal to, or an equal to relationship;
- and
- a processing engine operable to evaluate the representation of program instructions to determine whether the program instructions include arithmetic comparison operations that validate the ordering relationships between integer expressions of the program instructions thereby identifying at least one software defect related to integer anomalies within the program instructions.
A computer-implemented method of identifying defects in program instructions, the method comprising:
- responsive to encountering one or more operators in the program instructions, creating representations of ordering relationships between integer expressions associated with the one or more operator, wherein the ordering relationships represent a programmer assumption that an integer will not overflow or underflow
- determining which of the ordering relationships are explicitly validated by one or more of the program instructions, the one or more program instructions, when executed, performing a bounds check to determine whether one or more of the ordering relationships are satisfied;
- identifying whether one or more of the integer expressions are related to buffer processing;
- and
- in a computer, responsive to the determining and the identifying, identifying a portion of the program instructions associated with the one or more operators as associated with a potential integer overflow or a potential integer underflow, wherein the identifying a portion of the program instructions omits consideration of execution flow within the program instructions;
- wherein the creating representations of ordering relationships comprises creating a graph having directed edges, the graph comprising a first node representing a first one of the integer expressions, a second node representing a second one of the integer expressions, the first and second nodes connected by a directed edge representing at least one of the ordering relationships, the at least one of the ordering relationships relating the integer expressions represented by the first and second nodes and based at least on a greater than, a less than, a less than or equal to, a greater than or equal to, or an equal to relationship.
3 more elements
One or more computer-readable storage media having computer-executable instructions for performing a method of identifying defects in program instructions, the method comprising:
- responsive to encountering one or more operators in the program instructions, creating representations of ordering relationships between integer expressions associated with the one or more operators, wherein the ordering relationships represent a programmer assumption that an integer will not overflow or underflow
- determining which of the ordering relationships are explicitly validated by one or more of the program instructions, the one or more of the program instructions, when executed, performing a bounds check to determine whether one or more of the ordering relationships are satisfied;
- identifying whether one or more of the integer expressions are related to buffer processing;
- and
- responsive to the determining and the identifying, identifying a portion of the program instructions associated with the one or more operators as associated with a potential integer overflow or a potential integer underflow, wherein the identifying a portion of the program instructions omits consideration of execution flow within the program instructions;
- wherein the creating representations of ordering relationships comprises creating a graph having directed edges, the graph comprising a first node representing a first one of the integer expressions, a second node representing a second one of the integer expressions, the first and second nodes connected by a directed edge representing at least one of the ordering relationships, the at least one of the ordering relationships relating the integer expressions represented by the first and second nodes and based at least on a greater than, a less than, a less than or equal to, a greater than or equal to, or an equal to relationship, at least one of the first and second nodes representing an integer expression comprising at least two program variables referenced by the program instructions.
3 more elements
Dependencies are inferred from the claim text.