US 7,861,226 B1Granted

Constraint solver to code based test data generation for improving software reliability and security

AssigneeAvaya Inc.

InventorsDennis C. Episkopos, J. Jenny Li, Howell S. Yee, David M. Weiss

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present invention is directed to automatically analyzing software systems for identifying faults or bugs and/or detection of malicious code. In various embodiments, the present invention measures code coverage for high priority invocable program elements, uses a relaxed coverage estimation technique that, instead of guaranteeing which code units will be executed, guarantees that at least a certain number of code units will be executed, determines and solves constraints in code to identify infeasible paths containing one or more selected nodes, determines, for a composite data type, a range of values for each of at least two non-composite data fields, and/or translates, prior to code analysis complex code into simpler code having fewer operators.

Claims18

Dependent claims

A method for generating test cases for testing software code, comprising:

(a) identifying, by a processor, a path through the software code, wherein the path comprises a selected high priority code unit and wherein the path is determined using a representation of a flow graph for the software code;
(b) determining, by a processor, constraints in a set of code units that, if satisfied, cause the path to be executed and, if violated, indicate an occurrence of a fault in execution of the software code;
(c) solving, by a processor, the constraints for determining input data to the software code;
wherein the solving step comprises the substeps:
(c1) determining whether a selected path is infeasible, wherein a path is infeasible when there are at least first and second contradictory constraints;
(c2) when the selected path is infeasible, rejecting the selected path and returning to step (a) to identify a next path;
(c3) when the selected path is feasible, traversing the selected path and, for each further node along the selected path, adding, to the determined constraints, any additional constraints on data identified by the code units of the further node that would force the execution of the code units identified by a next following node along the path;
(d) determining, by a processor, a corresponding data set satisfying the constraints;
and
(e) generating, by a processor, from the data set, test code for executing the software code in a manner that causes execution of the software code to perform the set of code units.

7 more elements

A method for generating test cases for testing software code, comprising:

(a) determining, by a processor, constraints in a set of selected code units that, if satisfied, cause the software code to be executed and, if violated, indicate an occurrence of a fault in execution of the software code, wherein the set of code units are associated with a selected path through the software code;
(b) determining, by a processor, for at least one composite data type having an instantiation accessed by the constraints, a range of values for each of at least two non-composite data fields of the instantiation;
wherein the solving step comprises the substeps:
determining whether a selected path is infeasible, wherein a path is infeasible when there are at least first and second contradictory constraints;
when the selected path is infeasible, rejecting the selected path and returning to step (a) to determine a next path;
when the selected path is feasible, traversing the selected path and, for each further node along the selected path, adding, to the determined constraints, any additional constraints on data identified by the code units of the further node that would force the execution of the code units identified by a next following node along the path;
(c) solving, by a processor, the constraints to determine input data to the software code, wherein the range for at least one of the non-composite data fields is used for solving the constraints;
and
(d) generating, by a processor, test data for providing the input data to the software code.

6 more elements

A method for generating test data for testing software code, comprising:

(a) translating, by a processor, first software code into a corresponding second software code having a reduced number of data operator types compared to the first software code;
and identifying a path throughsecond software code, wherein the path comprises a selected high priority code unit and wherein the path is determined using a representation of a flow graph for the software code;
(b) thereafter determining, by a processor, constraints in the set of selected code units of the second software code that, if satisfied, cause the second software code to be executed and, if violated, indicate an occurrence of a fault in execution of the second software code;
(c) solving, by a processor, the constraints for determining input data to the second software code;
wherein the solving step comprises the substeps:
(c1) determining whether a selected path is feasible, wherein a path is feasible when there are at least first and second contradictory constraints;
(c2) when the selected path is infeasible, rejecting the selected path and returning to step (a) to determine a next path;
(c3) when the selected path is feasible, traversing the selected path and, for each further node along the selected path, adding, to the determined constraints, any additional constraints on data identified by the code units of the further node that would force the execution of the code units identified by a next following node along the path;
(d) determining, by a processor, a corresponding data set satisfying the constraints;
and
(e) generating, by a processor, from the data set, test code for executing the second software code in a manner that causes execution of the second software code to perform the set of code units.

8 more elements

Dependencies are inferred from the claim text.