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

• US 5,784,553 A
• Filed: 04/30/1997
• Issued: 07/21/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.
• Primary Examiner(s): Canney, Vincent P.
• Application Number:
  US08/846,639
• Time in Patent Office: 447 Days
• Field of Search: 395/183.14, 395/182.13, 395/183.13, 395/701, 364/275.5, 364/280.4, 364/489, 364/488, 364/578
• 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 written in the JAVA programming language. The JAVA program comprises program statements and program variables represented as JAVA source code and compiled by a JAVA compiler into JAVA bytecodes, 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 a pth in the program. 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 that depend on them 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 obtained using dynamic symbolic execution. The trial set of inputs are stored into the test suite if coverage of the candidate code block was obtained. A dynamic symbolic execution consists of a symbolic execution of the program performed along the path that corresponds to the trial set of actual inputs. The first input to the program is generated randomly. From that first input, inputs satisfying any coverage criteria can be obtained by performing the above procedure iteratively.

Claims

1. A system for generating a test suite for use in testing a computer program written in the JAVA progamming language, the computer program having been compiled by a JAVA compiler into JAVA bytecodes, comprising:

means for symbolically executing instructions of the computer program represented by the JAVA bytecodes to determine values of program variables of the computer program at selected points of execution and for finding input values to the computer program resulting in complete test coverage of the computer program according to a predetermined criteria based on the symbolic execution; and

means for storing the input values as a test suite for testing the computer program.

2. The system of claim 1 wherein the symbolic execution means comprises:

means for reading the JAVA bytecodes and for performing numeric and symbolic execution of the JAVA bytecodes.

3. The system of claim 2, wherein the reading and performing means comprises:

a numeric JAVA virtual machine for performing numeric execution of the JAVA bytecodes; and

a symbolic virtual machine for performing symbolic execution of the JAVA bytecodes.

4. The system of claim 3, wherein the symbolic virtual machine reads application class definitions and application native methods from the JAVA bytecodes, and library class definitions and library native methods from standard JAVA class libraries.

5. The system of claim 3, wherein the symbolic virtual machine comprises:

a symbolic class and method area;

a symbolic execution engine;

a symbolic heap;

a symbolic local variable stack; and

a symbolic operand stack.

6. The system of claim 3, wherein the symbolic virtual machine outputs symbolic expressions and path conditions for all required branch conditions of the computer program.

7. The system of claim 2, wherein the symbolic execution means further comprises:

means for generating sets of input values for the computer program.

8. The system of claim 7, wherein the symbolic execution means further comprises:

means for coordinating operations performed by the reading and performing means, and the generating means, and for directing the storing means to store the input values.

9. The system of claim 8, wherein the symbolic execution means further comprises:

means for resolving undefined external references in the computer program.

10. The system of claim 8, wherein the symbolic execution means further comprises:

means for determining which JAVA methods in an independent and incomplete module of the computer program need to be called and for determining arguments that need to be passed into the JAVA methods for undefined external references.

11. The system of claim 10, wherein the determining means comprises:

means for generating symbolic values input to the computer program for all undefined external references present in the independent and incomplete module.

12. The system of claim 8, wherein the symbolic execution means further comprises:

means for detecting potential runtime errors in instructions of the computer program caused by values of the program variables.

13. The system of claim 1, further comprising:

means for parsing the JAVA bytecodes and for inserting instrumentation information into the JAVA bytecodes.

14. The system of claim 13, wherein the symbolic execution means comprises means for performing error checking of the computer program based on the instrumentation information.

15. The system of claim 13, wherein the symbolic execution means comprises means for generating statistical data of execution of instructions of the computer program based on the instrumentation information.

16. A method using a computer for generating a test suite for a computer program written in the JAVA programming language, the computer program comprising program statements and program variables and being represented as JAVA bytecodes after being compiled by a JAVA compiler, the computer program including at least one input statement having one or more input variables, grouped into code blocks, 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 JAVA bytecodes;

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 execution of the JAVA bytecodes;

interpreting the JAVA bytecodes using the trial set of inputs and analyzing results obtained 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.

17. A method according to claim 16, the step of transforming further comprising the steps of:

selecting one of the program statements in the JAVA bytecodes;

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

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

18. A method according to claim 17, 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.

19. A method according to claim 18, 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.

20. A method according to claim 16, further comprising the step of:

instrumenting the JAVA bytecodes 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.

21. A method according to claim 16, 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.

22. A system for generating a test suite for a computer program written in the JAVA programming language, the computer program comprising program statements and program variables and represented as JAVA bytecodes after being compiled by a JAVA compiler, the computer program 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 JAVA bytecodes;

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 of the JAVA bytecodes;

means for interpreting the JAVA bytecodes using the trial set of inputs and means for analyzing results obtained 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.

23. A method of operating a computer system for performing dynamic symbolic execution by a symbolic virtual machine of a computer program written in the JAVA programming language and represented as JAVA bytecodes after being compiled by a JAVA compiler, the computer system having a memory, the method comprising the steps of:

reading a JAVA bytecode to be executed;

writing memory modifications into selected memory areas of the symbolic virtual machine when the JAVA bytecode being executed modifies a location in computer system memory;

resolving any undefined external references included in the JAVA bytecode; and

repeating the reading, writing and resolving steps for all JAVA bytecodes in the computer program.

24. A computer-implemented method of detecting runtime errors in a computer program written in the JAVA programming language, the computer program being represented by JAVA bytecodes after being compiled by a JAVA compiler, the computer-implemented method comprising the steps of:

reading the JAVA bytecodes;

obtaining at least one input value for the computer program;

symbolically executing an instruction of the computer program represented in the JAVA bytecodes;

examining all symbolic expressions on which the instruction depends based on the symbolic execution; and

storing the at least one input value in a test database and marking the at least one input value as an input that generates a runtime error when a solution to the symbolic expressions generates an error condition.

25. A computer-implemented method of generating a test suite for a module of an incomplete application program written in the JAVA programming language having undefined external references or a missing main method, the application program being represented by JAVA bytecodes after being compiled by a JAVA compiler, the computer-implemented method comprising the steps of:

reading the JAVA bytecodes for the module;

determining a sequence of JAVA methods to be called in the module and arguments to be passed to the JAVA methods;

performing symbolic interpretation of the sequence of JAVA methods of the JAVA bytecodes by calculating symbolic expressions for the JAVA methods and using the symbolic expressions to determine input values causing a predetermined testing criteria to be satisfied;

storing the input values in a test suite database when solutions for the predetermined testing criteria based on the symbolic expressions are found for the input values; and

repeating the determining and performing steps when solutions are not found for the predetermined testing criteria based on the symbolic expressions.

26. A computer-implemented method of inserting instrumentation information into JAVA bytecodes produced by compiling a computer program written in the JAVA programming language, comprising the steps of:

reading the JAVA bytecodes and the computer program;

creating a parse tree for the computer program and analyzing the parse tree to identify points in the computer program where instrumentation can be inserted;

analyzing the JAVA bytecodes and instrumenting the JAVA bytecodes at the identified points; and

writing a new set of JAVA bytecodes including the instrumentation information.