Method and system for generating a computer program test suite using dynamic symbolic execution

• US 5,761,408 A
• Filed: 02/12/1996
• Issued: 06/02/1998
• Est. Priority Date: 01/16/1996
• Status: Expired due to Term

• Current Assignee: Parasoft Corporation
• Original Assignee: Parasoft Corporation
• Inventors: Salvador, Roman, Kolawa, Adam K., Hicken, Wendell T., Strickland, Bryan R.
• Primary Examiner(s): Canney, Vincent P.
• Application Number:
  US08/599,719
• Time in Patent Office: 841 Days
• Field of Search: 395/183.14, 395/183.01, 364/267, 364/280, 364/267.91, 364/708
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/3676 for coverage analysis
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites

Abstract

A method and system for generating a test suite for a computer program. The computer program comprises program statements and program variables, including at least one input statement having one or more input variables, that are grouped into code blocks and stored in a program database. The test suite comprises sets of inputs. Each of the sets of inputs corresponds to each of the input statements. The program statements corresponding to a candidate code block are read from the program database. Each of the input variables for each input statement and each of the program variables are represented in symbolic form as a symbolic memory value and transforming each program statement dependent on such an input variable into a symbolic expression. A trial set of inputs for each of the input statements is created by finding a solution to the symbolic expression comprising actual input values corresponding to each symbolic memory value using dynamic symbolic exeuction. An execution run of the computer program is performed using the trial set of inputs and analyzing results obtained from the execution run for coverage of the candidate code block. The trial set of inputs are stored into the test suite if coverage of the candidate code block was obtained.

Claims

1. A method using a computer for generating a test suite for a computer program, the computer program comprising program statements and program variables, including at least one input statement having one or more input variables, grouped into code blocks and stored in a program database, the test suite comprising sets of inputs, each of the sets of inputs corresponding to each of the input statements, comprising the steps of:

reading the program statements corresponding to a candidate code block from the program database;

representing each of the input variables for each input statement and each of the program variables in symbolic form as a symbolic memory value and transforming each program statement dependent on such an input variable into a symbolic expression;

creating a trial set of inputs for each of the input statements by finding a solution to the symbolic expression comprising actual input values corresponding to each symbolic memory value using dynamic symbolic exeuction;

performing an execution run of the computer program using the trial set of inputs and analyzing results obtained from the execution run for coverage of the candidate code block; and

storing the trial set of inputs into the test suite if coverage of the candidate code block was obtained.

2. A method according to claim 1, further comprising the steps of:

creating a trial set of inputs for each of the input variables for each input statement using a pseudo random number generator.

3. A method according to claim 1, further comprising the step of:

building a parse tree for hierarchically representing a syntactical structuring of the program statements by associating one or more nodes in the parse tree with each such program statement and each such program variable.

4. A method according to claim 3, the step of transforming further comprising the steps of:

sequentially selecting the nodes in the parse tree representing one of the program statements;

symbolically executing the program statement corresponding to the selected nodes using the symbolic memory values for each of the input variables and the program variables contained in the program statement; and

creating a symbolic expression based on results obtained from the symbolic execution.

5. A method according to claim 4, further comprising the steps of:

building a symbolic memory for hierarchically representing each of the symbolic memory values by associating one or more nodes in the symbolic memory with each such symbolic memory value;

determining whether the program statement modifies a memory location in a memory used by the computer program to store and retrieve data values; and

writing such memory location modifications into the symbolic memory in symbolic form.

6. A method according to claim 5, further comprising the steps of:

determining whether the program statement is an external procedure call whose program statements are unknown; and

resolving the external procedure call by at least one of the steps of;

referencing a symbolic run-time library for storing external procedures and executing such a stored external procedure corresponding to the external procedure call using the symbolic memory values for each of the input variables and the program variables contained in the external procedure call;

or

mapping each of the symbolic memory values for each of the input variables and the program variables contained in the external procedure call to a non-symbolic value and executing the external procedure call using such non-symbolic values.

7. A method according to claim 6, further comprising the steps of:

determining whether the selected program statement contains a branch condition;

converting each branch condition into a symbolic expression by replacing each of the input variables and the program variables contained in the branch condition with a symbolic memory value; and

finding such a trial set of inputs for resolving the branch condition to take such actual input values that will force execution of the candidate code block.

8. A method according to claim 1, further comprising the step of:

instrumenting the computer program with instrumentation function calls comprising at least one of an instrumentation function call for coverage analysis, an instrumentation function call for block flow analysis or an instrumentation function call for branch condition analysis.

9. A method according to claim 1, further comprising the step of:

maintaining a program database for flow information as to paths of execution occurring in the computer program by breaking down the program statements into the code blocks and storing the code blocks in the program database.

10. A system for generating a test suite for a computer program, the computer program comprising program statements and program variables, including at least one input statement having one or more input variables, grouped into code blocks and stored in a program database, the test suite comprising sets of inputs, each of the sets of inputs corresponding to each of the input statements, comprising:

means for reading the program statements corresponding to a candidate code block from the program database;

means for representing each of the input variables for each input statement and each of the program variables in symbolic form as a symbolic memory value and means for transforming each program statement dependent on such an input variable into a symbolic expression;

means for creating a trial set of inputs for each of the input statements by finding a solution to the symbolic expression comprising actual input values corresponding to each symbolic memory value using dynamic symbolic execution;

means for performing an execution run of the computer program using the trial set of inputs and means for analyzing results obtained from the execution run for coverage of the candidate code block; and

means for storing the trial set of inputs into the test suite if coverage of the candidate code block was obtained.

11. A method using a computer for creating a symbolic expression using dynamic symbolic execution for use in generating a test suite for a computer program, the computer program comprising program instructions and program variables, including input variables, the program instructions represented as nodes organized into a hierarchical parse tree, the program variables and input variables represented in symbolic form as symbolic memory values in nodes organized into a symbolic memory, comprising the steps of:

reading a node for representing a program instruction from the parse tree;

obtaining symbolic memory values for each such program variable and each such input variable used by the program instruction from the symbolic memory; and

symbolically interpreting the program instruction using the symbolic memory values instead of actual values for each such program variable and each such input variable used by the program instruction to create the symbolic expression.

12. A method according to claim 11, further comprising the steps of:

determining whether the program instruction influences a branch condition occurring in one of the program instructions; and

skipping the step of symbolically interpreting such a program instruction.

13. A method according to claim 11, wherein the computer program uses a memory having a plurality of locations to store and retrieve data values, further comprising the steps of:

determining whether the program instruction modifies one of the locations in the memory; and

modifying the symbolic memory by writing a modification in symbolic form using the symbolic memory values for each such program variable and each such input variable used by the program instruction.

14. A method according to claim 11, further comprising the steps of:

determining whether the program instruction corresponds to an external procedure call whose program instructions are unknown; and

resolving the external procedure call.

15. A method according to claim 14, the step of resolving further comprising the steps of:

maintaining a symbolic run-time library for storing commonly used external functions;

replacing each such program variable and each such input variable used by the external procedure call with its corresponding symbolic memory value;

replacing the external procedure call with its matching commonly used function from the internal symbolic run-time library; and

producing such a symbolic expression using the corresponding memory values and the matched commonly used external function.

16. A method according to claim 14, the step of resolving further comprising the steps of:

mapping each such symbolic memory value used by the external procedure call to a non-symbolic value; and

executing an object code function corresponding to the external procedure call using each such mapped non-symbolic value.

17. A method according to claim 11, further comprising the steps of:

determining whether a next program instruction is unknown; and

resolving the next program instruction when the next instruction is unknown due to a branch condition.

18. A method according to claim 17, the step of resolving further comprising the steps of:

identifying the branch condition causing the next program instruction to be unknown;

transforming the branch condition into a real valued function that can be evaluated to a value that is less than or substantially equal to 0; and

determining a path condition associated with the branch condition.

19. A method according to claim 18, further comprising the step of:

replacing each such program variable and each such input variable used by the branch condition with its corresponding symbolic memory value.