Method for test case reduction based on program behavior slices

摘要

The present invention provides a method of test cases reduction based on program behavior slices. In the present invention, during a static analysis stage, analyzing a control flow and an information flow of a program according to input program codes, extracting control dependence and data dependence of the program; calculating potential dependence of the program according to the control dependence and the data dependence of the program; on the basis of the control dependence, the data dependence and the potential dependence, constructing combination dependence of the program; during a dynamic execution stage, according to an execution path and the dependence relation, calculating program behavior slices covered by the path and program behavior slices uncovered by the path, and guiding symbolic execution to generate a path capable of covering new program slices according to the uncovered program behavior slices.

主权项

1. A method of test cases reduction based on program behavior slices, comprising:
S1) analyzing control flow and information flow of a under test program and extracting a control dependence and a data dependence of the under test program, according to the under test program and by using a static program analysis method; S2) calculating a potential dependence of the under test program, according to the control dependence and the data dependence of the under test program; S3) constructing a combination dependence of the under test program in a program control flow graph, according to the control dependence, the data dependence and the potential dependence of the under test program; S4) randomly generating an initial path by using a symbolic execution method, and storing a test case corresponding to the initial path to a valid test suite; S5) calculating a program behavior slices covered by the new path, wherein the initial path is executed at the first time, and the calculation includes: for each branch node executed by the path, calculating the program behavior slices on the path, wherein, the program behavior slices of anode m on the path contains all nodes conforming to the following characters: the nodes have an interact relation on the path with the node m by the control dependence, the data dependence, the potential dependence, the combination dependence or their transition; S6) calculating a program behavior slices uncovered by the new path wherein the initial path is executed at the first time, and the calculation includes: according to the dependence relation, calculating all the branches required to be negated on the path and calculating the program behavior slices of the negated branches on the path; S7) updating the uncovered program behavior slices, including: deleting the program behavior slices covered by the new path and adding program behavior slices uncovered by the new path; S8) if the uncovered program behavior slices is null, i.e., there are no uncovered program behavior slices, going to Step S10); otherwise, going to Step S9); S9) selecting one piece of program behavior slices from the uncovered program behavior slices according to breadth first algorithm, guiding symbolic execution to generate a test path, if the test path is valid, storing its corresponding test case to the test suite and going to the Step S5); if no valid path is generated, deleting the selected program behavior slice from the uncovered program behavior slices and going to the Step S8); and S10) outputting the valid test suite which covers all the program behavior slices of the program.