JP5884657B2 - Program, test case generation method, and test case generation apparatus - Google Patents

Description

  The present technology relates to a technology for generating test data for a program.

  Test cases prepared for testing a program include data (referred to as test input) to be input to the test target program and expected results. Expected results are obtained based on the specifications of the program to be tested. For example, the expected result is set as the value of the output data of the test target program.

  In test case generation, it is desirable to generate test inputs so that instructions, branches, or execution paths in a program are comprehensively executed during a test. In other words, increasing code coverage is an issue.

  In addition to test input generation based on human judgment, there are a method of generating test inputs randomly and a method of generating test inputs according to predetermined rules (data range and data format). However, these methods have a problem that code coverage is difficult to increase because test input is not generated by reflecting the code and specifications of the program. In addition, if the number of test cases is increased in order to increase code coverage, the number of duplicate test cases increases.

  If a white box test is assumed, there is a method of statically analyzing the source code to extract a branch condition and generating a test input based on the branch condition. According to this method, the test input can be determined according to the actual conditions of the program source code, so that it is easy to avoid duplication of test cases. However, since the program is not actually executed, test cases are lost.

  On the other hand, there is a method called symbolic execution that generates a test input while executing a program. In this method, the program is executed with a special value called a symbol value, without setting a specific value for a variable in the program.

  Here, an example in which a class is a test target is shown. FIG. 1 shows an example of a test target class. Assume that the method “method1” included in the class “TargetClass” is to be tested.

  The variables input to the method “method1” are int type “a” and int type “b”. Each input variable is a primitive type variable. The processing code is determined by “if (a! = 0)” 101 branch processing, “if (a> 5)” 103 branch processing, and “if (a! = 0)” 105 determination. Branch processing and branch processing based on the determination of “if (b <= 0)” 109 are included. The processing code includes an arithmetic process “b = b + 1;” 107 and an arithmetic process “a = b / a;” 111.

  A flow diagram schematically showing the processing of FIG. 1 is shown in FIG. The first half flow includes four routes 201 to 207. The route 201 passes when the condition “a == 0” is satisfied. The route 203 passes when the condition “a! = 0”, the condition “a> 5”, and the condition “a == 0” are satisfied. The route 205 passes when the condition “a! = 0”, the condition “a> 5”, and the condition “a! = 0” are satisfied. The route 207 passes when the condition “a! = 0”, the condition “a <= 5”, and the condition “b = b + 1” are satisfied. The route 207 includes a calculation process of “b = b + 1”.

  The latter half flow includes two routes 209 and 211. The route 209 passes when the condition “b> 0” is satisfied. The route 211 passes when the condition “b <= 0” is satisfied. The route 209 includes a calculation process of “a = b / a”.

  Formally, since four routes of the first half flow and two routes of the second half flow can be arbitrarily combined, eight routes are considered as a whole. In this example, in order to dynamically generate a test case, it is conceivable that the input variable a and the input variable b have symbol values.

  When performing symbolic execution, a driver (referred to as a symbol execution driver) for invoking a method to be subjected to symbolic execution is prepared. The symbolic execution unit activates the symbol execution driver and executes the processing code of the program to be symbolically executed via the symbol execution driver.

  FIG. 3 shows an example of a symbol execution driver that calls the method “method1” shown in FIG. The symbol execution driver class “SymbolicDriver” will be described. Reference numeral 301 denotes a code relating to the declaration of the symbol variable. A symbol variable is a variable that holds a symbol value. With this declaration, int type “P1” and int type “P2” become symbol variables. “TestFunc ();” 303 is a code indicating the execution start position. “Target.method1 (P1, P2);” 305 is code for calling the target method. By setting “P1” and “P2” as arguments, the symbol variable “P1” is assigned to the input variable “a”, and the symbol variable “P2” is assigned to the input variable “b”.

  If the target program includes branch processing related to symbol variables, the paths that can be branched are comprehensively executed by dividing them into a plurality of execution patterns. Then, when executing the execution pattern, a condition (referred to as a path condition) that the symbol value must satisfy in order to establish the determination that led to the execution pattern is generated. For example, when the branch process is a bi-branch type, an execution pattern in which the conditional expression related to the symbol variable is true and an execution pattern in which the conditional expression related to the symbol variable is false are executed separately. When executing an execution pattern for which the conditional expression is true, a path condition is generated for the conditional expression to be true. When executing an execution pattern for which the conditional expression is false, the conditional expression is false. Generate a path condition to become When the branch process is a multi-branch type, another execution pattern is executed for each selection candidate of the conditional expression related to the symbol variable. Then, a path condition for the conditional expression to be a selection candidate is generated.

  FIG. 4 shows an example of a test case generated by symbolic execution with the method “method1” shown in FIG. 1 as a test target.

  The path condition (P1 == 0) and path condition (P2> 0) of case number 1 are obtained by the execution pattern combining the route 201 and the route 209 shown in FIG. Then, test inputs “P1 = 0, P2 = 1” are obtained as values satisfying these path conditions. According to this test case, when the input variable a is set to 0, the input variable b is set to 1 and the method “method1” is executed, the route 201 and the route 209 are passed.

  The path condition (P1 == 0) and the path condition (P2 <= 0) of case number 2 are obtained by the execution pattern combining the route 201 and the route 211 shown in FIG. Then, test inputs “P1 = 0, P2 = 0” are obtained as values satisfying these path conditions. According to this test case, when the input variable a is set to 0, the input variable b is set to 0, and the method “method1” is executed, the route 201 and the route 211 are passed.

  The path condition (P1! = 0), path condition (P1> 5), and path condition (P2 <= 0) of case number 3 are obtained by the execution pattern combining the route 205 and the route 211 shown in FIG. Then, test inputs “P1 = 6, P2 = 0” are obtained as values satisfying these path conditions. According to this test case, when the input variable a is set to 6 and the input variable b is set to 0 and the method “method1” is executed, the route 205 and the route 211 are passed.

  The path condition (P1! = 0), path condition (P1> 5), and path condition (P2> 0) of case number 4 are obtained by the execution pattern combining the route 205 and the route 209 shown in FIG. Then, test inputs “P1 = 6, P2 = 1” are obtained as values satisfying these path conditions. According to this test case, when the input variable a is set to 6 and the input variable b is set to 1 and the method “method1” is executed, the route 205 and the route 209 are passed.

  The path condition (P1! = 0), path condition (P1 <= 5), and path condition (P2 + 1 <= 0) of case number 5 are obtained by the execution pattern combining the route 207 and the route 211 shown in FIG. . Then, test inputs “P1 = 1, P2 = −1” are obtained as values satisfying these path conditions. According to this test case, when the input variable a is set to 1 and the input variable b is set to −1 and the method “method1” is executed, the route 207 and the route 211 are passed. In this example, the result of the arithmetic processing “b = b + 1” of the route 207 is reflected in the subsequent condition determination.

  The path condition (P1! = 0), path condition (P1 <= 5), and path condition (P2 + 1> 0) of case number 6 are obtained by an execution pattern in which the route 207 and the route 209 shown in FIG. A test input “P1 = 1, P2 = 0” is obtained as a value satisfying these path conditions. According to this test case, when the input variable a is set to 1 and the input variable b is set to 0 and the method “method1” is executed, the route 207 and the route 209 are passed. Also in this example, the result of the arithmetic processing “b = b + 1” of the route 207 is reflected in the subsequent condition determination.

  A! Since there is no value of a that satisfies the condition of = 0 and satisfies the condition of a == 0, the route 203 is not reached. That is, the execution pattern combining the route 203 and the route 209 and the execution pattern combining the route 203 and the route 211 do not have a value that satisfies the path condition for the symbol variable. Such an execution pattern is not a test case because it cannot be executed.

  When the pass condition can be satisfied, test cases such as case number 1 to case number 6 can be generated. Thus, high code coverage can be expected by generating test cases while executing a program.

  However, what can be handled as symbolic variables in symbolic execution is mainly primitive variables such as numeric values and boolean values. An object type variable is generally used for a program written in an object-oriented programming language, and a test case cannot be generated by symbolic execution for a program that uses such a variable as a test input.

Japanese Unexamined Patent Publication No. 2011-191985 JP 2012-068869 A JP 2009-087355 A

  Accordingly, an object of the present technology is, in one aspect, to generate test data suitable for a program using object type variables.

  The test case generation method according to the present embodiment uses (A) one or a plurality of symbol variables including a control variable indicating a state of an object type variable input to a test target program, and an object corresponding to the control variable For each execution pattern in the driver for invoking the type variable initialization and the test target program and the test target program to be called, the first one or more symbol variables to be satisfied in the execution of the driver and the test target program A symbolic execution process for generating a first test case including the first pass condition and a satisfaction value of one or more symbol variables for the first pass condition; and (B) for each execution pattern In addition, the second parameter that the object type variable should satisfy as the state in the execution of the program under test is First generation processing for generating a condition, and (C) for each execution pattern, a condition to be satisfied by a control variable is omitted from the first path condition included in the first test case, and a second path condition is added. A second generation process for determining a third path condition and generating a second test case including the third path condition and a satisfaction value of one or more symbol variables; and (D) a third path condition. When there are a plurality of second test cases having the same meaning, the second test case among the plurality of second test cases having the same third pass condition is omitted, and the remaining second test case is omitted. And an extraction process for extracting a test case.

  Test data suitable for programs using object type variables can be generated.

FIG. 1 is a diagram illustrating an example of a test target class. FIG. 2 is a diagram illustrating an example of a flow. FIG. 3 is a diagram illustrating an example of a symbol execution driver. FIG. 4 is a diagram illustrating an example of a test case. FIG. 5 is a diagram illustrating an example of a test target class. FIG. 6 is a diagram illustrating an example of a library. FIG. 7 is a diagram illustrating an example of a sample form. FIG. 8 is a diagram illustrating an example of a symbol execution driver. FIG. 9 is a diagram illustrating an example of a control variable table. FIG. 10 is a diagram illustrating a configuration example related to a preparation process in the test case generation apparatus. FIG. 11 is a diagram illustrating an example of a preparation process flow. FIG. 12 is a diagram illustrating an example of a driver generation processing flow. FIG. 13 is a diagram illustrating an example of a symbol variable declaration processing flow. FIG. 14 is a diagram illustrating an example of a control variable declaration processing flow. FIG. 15 is a diagram illustrating an example of a member declaration processing flow. FIG. 16 is a diagram illustrating an example of an initialization code processing flow. FIG. 17 is a diagram illustrating an example of a nulling process flow. FIG. 18 is a diagram illustrating an example of a class determination processing flow. FIG. 19 is a diagram illustrating an example of an object type variable initialization process flow. FIG. 20 is a diagram illustrating an example of an object designation command processing flow. FIG. 21 is a diagram showing an example of a primitive declaration processing flow. FIG. 22 is a diagram illustrating an example of a target class initialization process flow. FIG. 23 is a diagram illustrating an example of a target method call processing flow. FIG. 24 is a diagram illustrating an example of a control variable table generation processing flow. FIG. 25 is a diagram illustrating a configuration example related to symbolic execution processing in the test case generation device. FIG. 26 is a diagram illustrating an example of a pattern table. FIG. 27 is a diagram illustrating an example of a symbol variable table. FIG. 28 is a diagram illustrating an example of an object table. FIG. 29 a is a diagram illustrating an example of the first test case. FIG. 29 b is a diagram illustrating an example of the first test case. FIG. 29c is a diagram illustrating an example of the first test case. FIG. 30 is a diagram illustrating an example of the object path condition. FIG. 31 is a diagram illustrating an example of a symbolic execution process flow. FIG. 32 is a diagram illustrating an example of an initialization process flow. FIG. 33 is a diagram illustrating an example of an execution pattern processing flow. FIG. 34 is a diagram illustrating an operation example of execution pattern processing. FIG. 35 is a diagram illustrating an example of an object specifying process flow. FIG. 36 is a diagram illustrating an operation example of execution pattern processing. FIG. 37 is a diagram illustrating an example of a search processing flow. FIG. 38 is a diagram illustrating an operation example of object path condition generation. FIG. 39 is a diagram illustrating an example of an object path condition generation processing flow. FIG. 40 is a diagram illustrating an operation example of object path condition generation. FIG. 41 is a diagram illustrating an example of a memory state. FIG. 42 is a diagram illustrating an example of a memory state. FIG. 43 is a diagram illustrating a configuration example related to path condition update and test case extraction in the test case generation apparatus. FIG. 44 is a diagram showing an outline of path condition update. FIG. 45 is a diagram illustrating an example of a second test case generation process flow. FIG. 46 a is a diagram illustrating an example of the second test case. FIG. 46 b is a diagram illustrating an example of the second test case. FIG. 46c is a diagram illustrating an example of the second test case. FIG. 47 is a diagram illustrating an example of the third test case. FIG. 48 is a diagram illustrating an example of a test case extraction process flow. FIG. 49 is a diagram illustrating an example of the configuration of a computer.

  FIG. 5 shows an example of the test target class. Here, it is assumed that the operation of the test target method “targetMethod2” included in the test target class “TargetClass” is tested. The test target method “targetMethod2” is configured to input an object type variable “obj1” and an object type variable “obj2”.

  FIG. 6 shows an example of a library. Class A, class B, and class C are used in the above-described test target class “TargetClass”. Class A holds member variable a1. Class B inherits class A. That is, B is a child class of the parent class A. Class B holds member variable b1. Class C also inherits class A. That is, C is also a child class of the parent class A.

  The method “calcPathCondition (Object obj, String name)” held by the class “SymbolExecUtil” is an object designation command. The object designation command is a command for designating an object type variable that is a calculation target of a path condition. When an object designation command is called during symbolic execution, the object path condition after this command is calculated for the instance referred to by “obj”. The object designation command also designates the use of name as a variable name indicating obj in the object path condition. However, nothing is done even if an object designation command is called during normal program execution.

  The test case generation device generates a symbol execution driver based on the test target class and a library used by the test target class (for example, class A, class B, and class C). The symbol execution driver is a driver that performs an initial setting and a test target call. The test case generation apparatus uses a sample form to generate a symbol execution driver.

  FIG. 7 shows an example of a symbol execution driver sample form. The symbol variable declaration area 701 is an area for setting a symbol variable declaration. The target class initialization area 703 is an area for setting the initialization of the target class. The initialization code area 705 is an area for setting a code for initializing an object type variable that is a calculation target of a path condition. The object designation command area 707 is an area for setting an object designation command. A target method call area 709 is an area for setting a target method call instruction.

  FIG. 8 shows an example of a symbol execution driver generated using the sample form.

A code 801, a code 803, a code 805, and a code 807 are codes for declaring a symbol variable related to the object type variable P1. Codes 801 and 803 are control variable declarations, and codes 805 and 807 are member symbol variable declarations. Both control variables and member symbol variables are symbol variables.

  A code 809 is a code indicating an execution start position by symbolic execution. A code 811 is a code for initializing the target class. A code 813 is a code for declaring an object type variable. The code 815 is a code that performs null determination of an object type variable and substitution of a null value. The process in else is closed by a code 819. A code 817 is a code for initializing an object type variable according to a class type. A code 821 is an object designation command that designates an object type variable as a path condition calculation target. A code 823 is a code for calling a class to be tested.

  In the preparation stage, a control variable table is also generated based on the test target class. FIG. 9 shows an example of the control variable table. The control variable indicates the state of the object type variable input to the test target method. In this example, the control variable P1_cull indicates whether or not the object type variable P1 is null. If the value of the control variable P1_cull is true, it means that the object type variable P1 is null, which is synonymous with the semantic expression “P1 == null”. If the value of the control variable P1_cull is false, it means that the object type variable P1 is not null, which is synonymous with the semantic expression “P1! = Null”.

  In this example, the control variable P1_cClass indicates the actual class type of the object type variable. When the value of the control variable P1_cClass is 0, it means that the actual type of the object type variable P1 is class A, which is synonymous with the semantic expression “P1 instance of A”. When the value of the control variable P1_cClass is 1, it means that the actual type of the object type variable P1 is class B, which is synonymous with the semantic expression “P1 instanceof B”. When the value of the control variable P1_cClass is other than 0 or 1, it means that the actual type of the object type variable P1 is class C, which is synonymous with the semantic expression “P1 instanceof C”. Note that the variable input method is not limited to the argument format as long as it can be referred to.

  First, preparation processing for generating a symbol execution driver and a control variable table by the test case generation apparatus will be described. FIG. 10 shows a configuration example related to the preparation process in the test case generation apparatus. The test case generation apparatus includes a reception unit 1001, a target class storage unit 1003, a library storage unit 1005, a sample form storage unit 1007, a driver generation unit 1009, a driver storage unit 1011, a control variable table generation unit 1013, and a control variable table storage unit. 1015.

  The receiving unit 1001 is configured to receive a target class and a library. The target class storage unit 1003 is configured to store the target class. The library storage unit 1005 is configured to store a library. The sample form storage unit 1007 stores sample forms in advance. The driver generation unit 1009 is configured to generate a symbol execution driver. The driver storage unit 1011 is configured to store a symbol execution driver. The control variable table generation unit 1013 is configured to generate a control variable table. The control variable table storage unit 1015 is configured to store a control variable table.

  FIG. 11 shows an example of a preparation process flow. The accepting unit 1001 accepts the target class and the library (S1101). Then, the driver generation unit 1009 performs driver generation processing (S1103). Subsequently, the control variable table generation unit 1013 performs control variable table generation processing (S1105). The control variable table generation process (S1105) will be described later with reference to FIG.

  FIG. 12 shows an example of a driver generation processing flow. The driver generation unit 1009 first reads a sample form from the sample form storage unit 1007 (S1201). Then, the driver generation unit 1009 performs symbol variable declaration processing (S1203).

  FIG. 13 shows an example of a symbol variable declaration processing flow. The driver generation unit 1009 identifies an input variable of the target method (S1301). For example, in FIG. 5, “A obj1” and “A obj2” are input variables. In the example of FIG. 1, “int a” and “int b” are input variables as input variables.

  Then, the driver generation unit 1009 repeats the following process for each input variable (S1303).

The driver generation unit 1009 determines whether the type of the input variable is an object type or a primitive type (S1305). For example, if the input variable is “A obj1”, it is determined to be an object type, and if the input variable is “int a”, it is determined to be a primitive type.

  First, a case where the input variable type is determined to be an object type will be described. The driver generation unit 1009 performs control variable declaration processing (S1307).

  FIG. 14 shows an example of a control variable declaration process flow. The driver generation unit 1009 determines a null control variable name according to the convention (S1401). In this example, the null control variable name for the i-th input variable is “Pi_cull”. Then, the driver generation unit 1009 adds a line of “@Symbolic (“ true ”)” to the symbol variable declaration area 701 of the sample form (S1403), and further adds a line of “public static Boolean;” (S1405). Then, the driver generation unit 1009 inserts a Boolean type null control variable name (S1407). Furthermore, the driver generation unit 1009 may substitute a specific value for the null control variable. In this way, for example, the declaration 801 shown in FIG. 8 is generated.

  Subsequently, the driver generation unit 1009 determines an actual type control variable name according to the convention (S1409). In this example, the actual control variable name for the i-th input variable is “Pi_cClass”. The driver generation unit 1009 adds a line “@Symbolic (“ true ”)” to the symbol variable declaration area 701 of the sample form (S1411), and further adds a line “public static int;” (S1413). Then, the driver generation unit 1009 inserts an int type actual control variable name (S1415). The driver generation unit 1009 may substitute a specific value for the actual control variable. In this way, for example, the declaration 803 shown in FIG. 8 is generated.

  Returning to the processing of FIG. 13, the driver generation unit 1009 performs member declaration processing (S1309).

  FIG. 15 shows an example of the member declaration processing flow. The driver generation unit 1009 repeats the following processing for each member variable that can be held as an object type variable (S1501). The driver generation unit 1009 determines a member symbol variable name according to the convention (S1503). In this example, the member symbol variable name for the member variable M of the i-th input variable is “Pi_mM”. The driver generation unit 1009 adds a line of “@Symbolic (“ true ”)” to the symbol variable declaration area 701 of the sample form (S1505), and further adds a line of “public static;” (S1507). Then, the driver generation unit 1009 inserts a data type (S1509), and inserts a member symbol variable name (S1511). The driver generation unit 1009 may substitute a specific value for the member symbol variable. In this way, for example, declarations 805 and 807 shown in FIG. 8 are generated. The driver generation unit 1009 determines whether all member variables have been processed (S1513). If it is determined that there is a member variable that has not been processed, the process returns to S1501. If it is determined that all member variables have been processed, the driver generation unit 1009 finishes the process and returns to S1311 in FIG.

  Returning to the processing of FIG. 13, the driver generation unit 1009 performs initialization code processing (S1311).

  FIG. 16 shows an example of an initialization code processing flow. The driver generation unit 1009 determines an object type variable name according to the convention (S1601). In this example, the i-th input variable name is “Pi” regardless of whether it is a primitive type variable or an object type variable. The driver generation unit 1009 adds an object type variable declaration to the initialization code area 705 of the sample form (S1603). Specifically, a class type and an object variable name are set. In this way, for example, the declaration 813 shown in FIG. 8 is generated.

  Subsequently, the driver generation unit 1009 performs null processing (S1605). FIG. 17 shows an example of a nulling process flow. The driver generation unit 1009 adds a determination control code to the initialization code area 705 of the sample form (S1701). In this example, “if () {} else {}” (line feed omitted) shown in 815 and 819 in FIG. 8 is added as a determination control code. The driver generation unit 1009 inserts a null determination condition (S1703). In this example, a null control variable name is inserted in () of the if statement. If the determination of the “if” statement is true, the driver generation unit 1009 adds an instruction to assign null to the null control variable name (S1705), and ends the process.

  Returning to the processing of FIG. 16, the driver generation unit 1009 performs class determination processing (S1607). The driver generation unit 1009 sets, for example, a code 817 in FIG. 8 in the class determination process (S1607).

  FIG. 18 shows an example of the class determination processing flow. The driver generation unit 1009 adds a branch control code to the initialization code area 705 of the sample form (S1801). In this example, “switch () {case: break; case: break; default: break;}” (line feed omitted) is added as a branch control code when the determination of the if statement is false. The driver generation unit 1009 inserts a branch condition (S1803) and ends the process. In this example, the actual control variable name “P1_cClass” is inserted in () of the switch statement, and “0” and “1” are inserted after each case.

  Returning to the processing of FIG. 16, the driver generation unit 1009 performs object type variable initialization processing (S1609). In the object type variable initialization process (S1609), the driver generation unit 1009 sets an initialization code for each class type that is a candidate for the type of the object type variable.

  FIG. 19 shows an example of an object type variable initialization process flow. The driver generation unit 1009 repeats the following processing for each candidate class type (S1901). The driver generation unit 1009 adds an object type variable generation instruction (S1903). For example, when the class type is A, a code of “(object type variable) = new A ();” is added. The driver generation unit 1009 further adds a member initialization command for member variables that can be held in the candidate class type (S1905). Specifically, a code of “(member variable) = (member symbol variable name);” is added. The driver generation unit 1009 determines whether or not all candidate class types have been processed (S1907). If it is determined that there is an unprocessed class type, the driver generation unit 1009 returns to S1901. If it is determined that all candidate class types have been processed, the driver generation unit 1009 finishes the process and returns to the process of FIG. In this way, for example, the code 817 shown in FIG. 8 is set. Further, the driver generation unit 1009 finishes the process of FIG. 16 and returns to S1313 of FIG.

  Returning to the processing of FIG. 13, the driver generation unit 1009 performs an object designation command process (S1313). The driver generation unit 1009 sets, for example, the code 821 shown in FIG. 8 in the object designation command processing (S1313).

  FIG. 20 shows an example of an object designation command processing flow. The driver generation unit 1009 adds a line of an object designation command “SymbolExecUtil.calcPathCondition ();” to the object designation command area 707 of the sample form (S2001). The driver generation unit 1009 inserts the object type variable name into the argument of the object designation command (S2003).

  In addition, the driver generation unit 1009 identifies a path condition variable name (S2005). The path condition variable name is a variable name used when generating a path condition for the object type variable. In this example, the path condition variable name is the same as the object type variable name. The driver generation unit 1009 inserts the path condition variable name into the argument of the object designation command (S2007). The driver generation unit 1009 finishes the process of FIG. 20, and returns to S1317 of FIG.

  Next, returning to the processing of FIG. 13, the case where the type of the input variable is determined to be a primitive type in S1305 will be described.

  If the input variable type is determined to be a primitive type in S1305, the driver generation unit 1009 performs a primitive declaration process (S1315). FIG. 21 shows an example of a primitive declaration processing flow. The driver generation unit 1009 determines a primitive variable name according to the convention (S2101). In this example, the i-th input variable name is “Pi” regardless of whether it is a primitive type variable or an object type variable. The driver generation unit 1009 adds a line of “@Symbolic (“ true ”)” to the symbol variable declaration area 701 of the sample form (S2103). The driver generation unit 1009 adds a line “public static;” (S2105). The driver generation unit 1009 inserts the data type of the primitive type variable (S2107). The driver generation unit 1009 inserts a symbol variable name (S2109). In this way, for example, the code 301 in FIG. 3 is set. When the driver generation unit 1009 finishes the process of FIG. 21, the process returns to S1317 of FIG.

  Returning to the processing of FIG. 13, the driver generation unit 1009 determines whether or not all the arguments have been processed (S1317). If it is determined that there is an argument that has not been processed, the driver generation unit 1009 returns to S1301. If it is determined that all the arguments have been processed, the driver generation unit 1009 finishes the process in FIG. 13 and returns to S1205 in FIG.

  Returning to the process of FIG. 12, the driver generation unit 1009 sets a code for initializing the target class in the target class initialization process (S1205).

  FIG. 22 is a diagram illustrating an example of a target class initialization process flow. The driver generation unit 1009 adds a line “TargetClass target = new ();” to the target class initialization area 703 of the sample form shown in FIG. 7 (S2201). The driver generation unit 1009 identifies the target class name (S2203), inserts it before “()” (S2205), and ends the process. In this way, the code 811 shown in FIG. 8 is set.

  When the process of FIG. 22 is completed, the process returns to the process of FIG. 12, and the driver generation unit 1009 performs a target method call process (S1207).

  FIG. 23 shows an example of the target method call processing flow. The driver generation unit 1009 adds a line “target. ();” To the target method call area 709 of the sample form shown in FIG. 7 (S2301). The driver generation unit 1009 identifies the target method name (S2303) and inserts it after “.” (S2305). Further, the driver generation unit 1009 inserts a variable name to be set as an argument (S2307) and ends the process. The driver generation unit 1009 finishes the target method call process (S1207) of FIG. 12, and further finishes the driver generation process (S1103) of FIG.

  Next, returning to the process of FIG. 11, the control variable table generation process shown in S1105 will be described. The control variable table generation unit 1013 generates, for example, the control variable table shown in FIG. 9 in the control variable table generation process.

  FIG. 24 shows an example of a control variable table generation processing flow. The control variable table generation unit 1013 identifies the input variable of the target method (S2401), and repeats the following processing for each input variable (S2403). The control variable table generation unit 1013 determines whether the type of the input variable is an object type or a primitive type (S2405). If it is determined that the type of the input variable is a primitive type, the control variable table generation unit 1013 performs S2417.

  If it is determined that the type of the input variable is an object type, the control variable table generation unit 1013 sets the null control variable name determined in S1401 of FIG. 14 (S2407). Then, the control variable table generating unit 1013 sets true and a semantic expression (S2409). The semantic expression is “(object type variable name) == null”. The control variable table generation unit 1013 further sets false and a semantic expression (S2411). The semantic expression is “(object type variable name)! = Null”.

  Next, the control variable table generation unit 1013 sets the actual control variable name determined in S1409 of FIG. 14 (S2413). Further, the control variable table generation unit 1013 sets a value indicating a candidate class and a semantic expression (S2415). According to the value, “(object type variable name) instanceof (candidate class name)”. The control variable table generating unit 1013 determines whether all input variables have been processed (S2417). If it is determined that there is an input variable that has not been processed, the control variable table generation unit 1013 returns to S2403. If it is determined that all input variables have been processed, the control variable table generation unit 1013 finishes the process, returns to FIG. 11, and ends the preparation process.

  In this way, in the preparation process, by generating the symbol execution driver and the control variable table, it is possible to save labor in the test case generation work.

  Next, symbolic execution processing will be described. FIG. 25 is a diagram illustrating a configuration example related to symbolic execution processing in the test case generation device. The test case generation apparatus further includes an execution unit 1017, a pattern table storage unit 1019, a symbol variable table storage unit 1021, a specification unit 1023, an object table storage unit 1025, a first test case storage unit 1027, a first generation unit 1029, and an object. A path condition storage unit 1031 is included.

  The execution unit 1017 is configured to perform symbolic execution and generate a first test case. The pattern table storage unit 1019 is configured to store a pattern table that associates program patterns, memory condition patterns, and path condition patterns. The pattern table storage unit 1019 will be described later with reference to FIG.

  The symbol variable table storage unit 1021 is configured to store a symbol variable table that associates a symbol variable with its type. The specifying unit 1023 is configured to perform a process of generating an object table specifying the position where the entity of the object type variable is stored. The object table storage unit 1025 is configured to store an object table. The first test case storage unit 1027 is configured to store a first test case set that is a set of first test cases. The first generation unit 1029 is configured to perform processing for generating an object path condition that the object type variable should satisfy based on the object table. The object path condition storage unit 1031 is configured to store object path conditions.

  FIG. 26 shows an example of the pattern table. The pattern table associates pattern numbers, program patterns, memory condition patterns, and path condition patterns. The object path condition pattern derived from the expression pattern included in the program is defined. Furthermore, in addition to the pattern of formulas included in the program, a memory condition pattern is also defined in the case of determining by adding a memory condition.

  When the memory condition pattern is not set, the path condition pattern is derived from the program pattern. When the memory condition pattern is set, the path condition pattern is derived from the program pattern and the memory condition pattern.

  “OBJX” and “OBJY” indicate object variables for which object path conditions are calculated. For example, as shown in pattern number 1, when an instruction in the program includes an expression “OBJX == null”, “OBJX == null” is derived as a path condition.

  “TX” indicates a type. For example, as shown in pattern number 3, when an instruction in the program includes an expression “OBJX instance of TX”, “OBJX instance of TX” is derived as a path condition.

  “.Member” indicates access to a member variable. For example, as shown in pattern number 5, when an instruction in the program includes an expression “OBJX.member”, “OBJX! = Null” is derived as a path condition.

  “.Method ()” indicates a method call. For example, as shown in pattern number 6, when an instruction in the program includes an expression “OBJX.method ()”, “OBJX! = Null” is derived as a path condition.

  “VX” and “VY” indicate variables that are not targets for calculating the object path condition. For example, as shown in the pattern number 7, if the instruction in the program includes the expression “OBJX == VX” and the memory state is “VX == null”, the path condition is “OBJX == null "is derived.

  FIG. 27 shows an example of a symbol variable table stored in the symbol variable table storage unit 1021. Thus, the symbol variable table storage unit 1021 associates the symbol variable with its type.

  FIG. 28 shows an example of an object table stored in the object table storage unit 1025. As shown in FIG. 28, the object type variable name for which the object path condition is calculated, the reference ID, and the path condition variable name are associated with each other. The reference ID is information for referring to an instance of an object type variable. The path condition variable name is a variable name of an object type variable used in the object path condition. The object type variable name may be omitted.

  FIGS. 29 a to 29 c show examples of the first test case set stored in the first test case storage unit 1027. A case number for identifying a test case, a test input, and a symbol path condition are associated with each other. The first test case is generated by symbolic execution processing.

  FIG. 30 shows an example of object path conditions stored in the object path condition storage unit 1031. A case number for identifying a test case is associated with an object path condition. For example, case number 1 indicates that “P1_cnull == true ＝ P2_cnull == true” is an object path condition. The object path condition is generated by the first generation unit 1029.

  Next, symbolic execution processing will be described. FIG. 31 shows an example of a symbolic execution process flow. The execution unit 1017 first performs initialization processing (S3101).

  FIG. 32 shows an example of an initialization process flow. The execution unit 1017 generates a symbol variable table (S3201). The symbol variable table is extracted from the symbol variable declaration of the symbol execution driver. The symbol variable table is used to specify symbol variables. The execution unit 1017 identifies the execution start position (S3203). The execution start position is specified by the code 809 in FIG. The execution unit 1017 assigns a new record to the first test case (S3205). At this time, a case number is also assigned. The execution unit 1017 ends the process and returns to S3103 in FIG.

  Returning to the processing of FIG. 31, the execution unit 1017 performs execution pattern processing (S3103). In the execution pattern process, a process for each execution pattern is performed. FIG. 33 shows an example of an execution pattern processing flow. The execution unit 1017 specifies commands in order from the execution start position (S3301). The execution unit 1017 determines whether there is an instruction (S3303). If it is determined that there is no command, it is the end point of the execution pattern, so the execution unit 1017 completes the processing result and ends the processing (S3305). When the execution unit 1017 finishes the process, the process returns to S3105 in FIG.

  If it is determined in S3303 in FIG. 33 that there is an instruction, the execution unit 1017 determines whether the instruction is an object designation instruction (S3307). The object designation command is, for example, the code 821 shown in FIG. If it is determined that the instruction is not an object designation instruction, the execution unit 1017 moves the process to S3311. If it is determined that the command is an object designation command, the specifying unit 1023 performs an object specifying process (S3309).

  Here, an example of execution pattern processing for determining an object designation command will be described. FIG. 34 shows an operation example of execution pattern processing. The transition of instructions in the symbol execution driver and the target method is indicated by arrows. In the condition determination of “if (P1_cull)”, “true” is determined, and the symbol path condition “P1_cull == true” is generated. Further, in the condition determination of “if (P2_cull)”, “true” is determined, and a symbol path condition “P2_cull == true” is generated.

  In the lines of “SymbolicExecUil.calcPathCondition (P1,“ P1 ”);” and “SymbolicExecUil.calcPathCondition (P2,“ P2 ”);”, the object specifying command is determined, and the object specifying process is performed.

  Subsequently, the object specifying process (S3309) of FIG. 33 will be described. FIG. 35 shows an example of an object specifying process flow. The identifying unit 1023 identifies an object type variable name that is an argument of the object designation command (S3501). In the example of FIG. 34, “P1” and “P2” are object type variable names, respectively. The specifying unit 1023 passes the object type variable name to the execution unit 1017, and acquires a reference ID for referring to the object type variable instance from the execution unit 1017 (S3503). At this time, the execution unit 1017 operates to receive an object type variable name and return a reference ID for referring to the instance of the object type variable. The identifying unit 1023 identifies the path condition variable name that is an argument of the object designation command (S3505). In the example of FIG. 34, “P1” and “P2” are path condition variable names, respectively. The specifying unit 1023 adds the object type variable name, the reference ID, and the path condition variable name to the record of the target table (S3507). The identification unit 1023 finishes the process and returns to S3311 of FIG.

  Returning to the processing of FIG. 33, the execution unit 1017 analyzes the instruction specified in S3301 (S3311), and determines whether or not the instruction is a branch instruction. (S3313). If it is determined that the instruction is not a branch instruction, then the flow shifts to S3317. If it is determined that the instruction is a branch instruction, the execution unit 1017 selects a branch that has not yet been selected as a path (S3315). Then, the execution unit 1017 calculates a symbol path condition for the selected branch (S3317). However, there are cases where it is determined in S3313 that the instruction is not a branch instruction and the symbol path condition is not calculated. Since the calculation of the symbol path condition is the same as in the case of conventional symbolic execution, description thereof is omitted.

  Subsequently, the first generation unit 1029 performs an object path condition generation process (S3319). The object path condition generation process will be described later with reference to FIGS.

  The execution unit 1017 determines whether the path condition can be satisfied (S3321). When it is determined that the path condition cannot be satisfied, since the path that cannot be executed (for example, 203 in FIG. 2) is included, the execution unit 1017 interrupts the processing result (S3323). If it is determined that the path condition can be satisfied, the execution unit 1017 executes the command (S3325) and returns to S3301.

  FIG. 36 shows an operation example of the next execution pattern process of FIG. When it reaches “return 0” in FIG. 34 and determines that there is no next instruction as shown in S3303 and S3305 in FIG. 33, the processing result is completed and the execution pattern processing is once completed. Then, an unexecuted path is selected. Specifically, the backtrack returns to the branch point where there is an unselected branch, and the unselected branch is set as the execution start position of the next path. In the example of FIG. 36, the determination result “false” of the next execution start position “if (P2_cull)” is selected. At this time, a known symbol path condition “P1_cull == true” obtained up to the execution start position “if (P2_cull)” is specified and set as a new symbol path condition. Then, a symbol path condition “P2_cull == false” is generated.

  Returning to the processing of FIG. 31, the execution unit 1017 determines whether the processing result in the execution pattern processing of S3103 is interrupted or complete (S3105). If it is determined that the processing result is interruption, the execution unit 1017 does not generate a test case. If it is determined that the processing result is complete, the execution unit 1017 generates a test case (S3107). Specifically, the execution unit 1017 obtains a satisfaction value of the symbolic path condition and sets the satisfaction value as a test input.

  Next, the execution unit 1017 performs a search process (S3109). In the search process, the next path is searched.

  FIG. 37 shows an example of a search processing flow. The execution unit 1017 selects an unexecuted path (S3701). Specifically, as shown in FIG. 36, the execution unit 1017 returns to the branch point where there is an unselected branch by backtracking, and sets the unselected branch as the execution start position of the next path. The execution unit 1017 determines whether or not there is an unexecuted path (S3703). When an unselected branch is not found by backtracking, the execution unit 1017 determines that there is no unexecuted path, and sets the processing result as no path (S3705). Then, the execution unit 1017 ends the process and returns to S3111 in FIG.

  If an unselected branch is found by backtracking, the execution unit 1017 determines that there is an unexecuted path and allocates a new record for the first test case (S3707). Then, the execution unit 1017 identifies a known symbolic path condition above the branch point, and adds it to the new symbolic path condition of the first test case (S3709). Then, the execution unit 1017 determines that the processing result has a path (S3711), and ends the processing. Then, the process returns to S3111 in FIG.

  Returning to the processing of FIG. 31, the execution unit 1017 determines whether the processing result of the search processing (S3109) is a path or no path (S3111). If it is determined that the processing result of the search process (S3109) is “pass”, the execution unit 1017 returns to the process of S3103 and continues the symbolic execution process. If it is determined that the processing result of the search process (S3109) is that there is no path, the execution unit 1017 ends the symbolic execution process.

  Next, the above-described object path condition generation process (S3319 in FIG. 33) will be described.

  Here, FIG. 38 shows an operation example of object path condition generation. In the example of FIG. 38, an expression “obj1! = Null” indicating a branch selected from the condition determination instruction “if (obj1! = Null)” is obtained. Then, the ID “100” that is the reference destination of the operand “obj1” is specified. Since this reference destination ID “100” matches the reference ID “100” in the object table, it is determined that the variable of this operand is a calculation target of the object path condition. Then, the program pattern “OBJX! = Null” corresponding to the expression “obj1! = Null” is specified in the pattern table, and the object path condition “P1” is based on the path condition pattern “OBJX! = Null” corresponding to the program pattern. ! = Null "is generated. At this time, the path condition variable name “P1” corresponding to the reference ID “100” is used. In this example, since the memory condition pattern is not set, the state of the memory is not determined.

  FIG. 39 shows an example of an object path condition generation process flow. The first generation unit 1029 specifies an expression from the instruction (S3901), and the first generation unit 1029 specifies an operand variable (S3903). In the case of a condition determination instruction, the first generation unit 1029 specifies an expression indicating the selected branch.

  The first generation unit 1029 acquires the reference destination ID of the variable from the execution unit 1017 (S3905). At this time, the first generation unit 1029 passes the variable name to the execution unit 1017. On the other hand, the execution unit 1017 operates so as to return an ID for referring to the instance by the variable name. The first generation unit 1029 determines whether or not the acquired reference destination ID matches any reference ID in the object table (S3907). If it is determined that the acquired reference destination ID does not match any reference ID in the object table, the first generation unit 1029 ends the process and returns to S3321 in FIG.

  If it is determined in S3907 in FIG. 39 that the acquired reference destination ID matches any reference ID in the object table, the first generation unit 1029 specifies a program pattern corresponding to the formula specified in S3901. (S3909). If the expression specified in S3901 is negative, it may be replaced with an affirmative expression and compared with the program pattern. The first generation unit 1029 determines whether there is a memory condition pattern corresponding to the program pattern in the pattern table (S3911). If it is determined that there is no memory condition pattern corresponding to the program pattern in the pattern table, the first generation unit 1029 moves to S3917.

  If it is determined that there is a memory condition pattern corresponding to the program pattern in the pattern table, the first generation unit 1029 acquires memory information related to the memory condition pattern (S3913). For example, the first generation unit 1029 passes the variable name corresponding to “VX” to the execution unit 1017, and the execution unit 1017 returns the value of the variable stored in the memory or null. Alternatively, in another example, the first generation unit 1029 passes a request for inquiring whether or not the object type variable corresponding to “OBJX” is null to the execution unit 1017, and the execution unit 1017 receives the object type corresponding to “OBJX”. Returns an answer indicating whether the variable is null.

  Then, the first generation unit 1029 determines whether or not the memory information matches the memory condition pattern (S3915). If it is determined that the memory information does not match the memory condition pattern, the first generation unit 1029 ends the process and returns to S3321 in FIG.

  If it is determined that the memory information matches the memory condition pattern, the first generation unit 1029 generates an object path condition (S3917). Specifically, a path condition pattern corresponding to the program pattern is specified, and an object path condition is generated based on the path condition pattern. At this time, an object variable (for example, “OBJX”) in the path condition pattern is replaced with a path condition variable name (for example, ““ P1 ””) corresponding to the object variable (“for example, P1”) corresponding to the object variable. Convert to As described above, the specified expression is in the negative form. When the program pattern is specified by replacing the expression with the positive form, the object path condition is also converted from the positive form to the negative form. Then, the first generation unit 1029 stores the generated object path condition in the object table storage unit 1025 in association with the case number (S3919).

  FIG. 40 shows an operation example of object path condition generation following FIG. In the example of FIG. 40, assuming that false is selected by the condition determination instruction “if (obj1 instance of B)”, an expression “! (Obj 1 instance of B)” indicating a branch is obtained. Then, the ID “100” that is the reference destination of the operand “obj1” is specified. Since this reference destination ID “100” matches the reference ID “100” in the object table, it is determined that the variable of this operand is a calculation target of the object path condition. Then, the program pattern “OBJX instance of TX” corresponding to the expression “obj1 instance of B” is specified in the pattern table, and the object path condition “! (P1 instance of TX) is determined based on the path condition pattern“ OBJX instance of TX ”corresponding to the program pattern. B) ". At this time, the path condition variable name “P1” corresponding to the reference ID “100” is used. Also, “TX” is replaced with the corresponding “B”. In this example, since the expression is in negative form, the object path condition is also in negative form.

  The aforementioned reference ID is information for referring to an instance of an object variable. FIG. 41 shows an example of the memory state. In the stack, a variable name, a type, and a reference ID are stored for each variable. Instances are stored in the heap. The instance is configured to be identified by the reference ID. For example, when acquiring the value of the member variable “obj1.a1”, the reference ID “100” corresponding to the variable name “obj1” is specified based on the stack information, and the reference ID “100” is further specified. The value of the member variable is acquired from the instance specified by “”. In normal execution, a specific value is set for the member variable. In symbolic execution, a symbol value is set for the member variable declared as a symbol variable. In the figure, “symbol_P1_ma1” and “symbol_P2_ma1” are examples of symbol values.

  The same instance may be referenced from multiple variables. FIG. 42 shows an example of referring to the same instance from a plurality of variables. For example, when acquiring the value of the member variable “(B) obj1.b1”, a class B type variable “tmp1” indicating the same instance as “obj1” is prepared in the stack by internal processing. Then, the reference ID “100” corresponding to the variable name “tmp1” is specified, and the value of the member variable is acquired from the instance specified by the reference ID “100”. In this case as well, symbol values are set for the member variables declared as symbol variables. In the figure, “symbol_P1_mb1” is an example of a symbol value.

  As described above, the first test case set and the object path condition are generated by the symbolic execution process. The first test case set of 26 shown in FIGS. 29a to 29c covers possible combinations of states of object type variables. The state of an assumed object type variable can be read according to a symbol path condition including “P1_cull”, “P2_cull”, “P1_cClass”, or “P2_cClass” as control information.

  However, the symbol path condition including these control information is generated by branching in the initialization code of the symbol execution driver (for example, 815 and 817 in FIG. 8), and is used for branching in the program under test. Not based. Therefore, it can be said that the path condition including the control information is inappropriate data for determining the code coverage for the test target program, although it is useful for extracting the test cases without missing them.

  On the other hand, the object path condition is a path condition by branching regarding the state of the object type variable in the test target program, and can be said to be appropriate data for determining the code coverage for the test target program.

  In the path condition update process described below, a second test case with the object path condition added is generated except for the symbol path condition including the control variable included in the first test case. The second test case has an in-target path condition suitable for determining code coverage for the program to be tested.

  In the test case extraction process following the path condition update process, a third test case set is generated by excluding duplicate test cases from the second test case set. The code coverage by the third test case set is equal to the code coverage by the second test case set.

  Next, the path condition update process and the test case extraction process will be described. FIG. 43 is a diagram illustrating a configuration example related to path condition update and test case extraction in the test case generation apparatus. The test case generation apparatus further includes a second generation unit 1033, a second test case storage unit 1035, an extraction unit 1037, a third test case storage unit 1039, and a test case output unit 1041. The second generation unit 1033 operates to update the path condition and generate a second test case. The second test case storage unit 1035 is configured to store the second test case set. The extraction unit 1037 operates to extract the third test case from the second test case set. The third test case storage unit 1039 is configured to store a third test case set that is a set of third test cases. The test case output unit 1041 operates to output the third test case set.

  FIG. 44 shows an outline of path condition update. Of the symbol path conditions of the first test case, only the symbol path condition not including the control variable is copied to the in-target path condition of the second test case. In the example of FIG. 44, the symbol path condition “(P2_ma1> P1_ma1)” is copied to the in-target path condition. Since the symbol path condition “P1_cull == false” includes the control variable “P1_cull”, it is not copied to the in-target path condition. Similarly, since the symbol path condition “P1_cClass == 0” includes the control variable “P1_cClass”, it is not copied to the in-target path condition. Similarly, since the symbol path condition “P2_cull == false” includes the control variable “P2_cull”, it is not copied to the in-target path condition. Similarly, since the symbol path condition “P2_cClass == 0” includes the control variable “P2_cClass”, it is not copied to the in-target path condition.

  Further, the object path condition is copied to the in-target path condition of the second test case. The object path condition is converted into a condition format to be satisfied by the control variable at the time of copying. In the example of FIG. 44, the object path condition “P1! = Null” is converted into the in-target path condition “P1_cull == false”. The object path condition “! (P1 instance of B)” is converted into the in-target path condition “P1_cClass! = 1”. The object path condition “P2! = Null” is converted into the in-target path condition “P2_cnull == false”. The object path condition “(P2.ma1> P1.ma1)” is converted into the in-target path condition “(P2_ma1> P1_ma1)”. Since the in-target path condition “(P2_ma1> P1_ma1)” overlaps with the symbol path condition, only one in-target path condition is set. In this way, it is assumed that part of the object path condition and the symbol path condition overlap.

  By converting to the format of the condition that the control variable should satisfy, it becomes easier to grasp the relationship with the test input.

  Further, the test input of the first test case is copied to the test input of the second test case.

  Test input “P1_cull = false”, test input “P1_cClass = 0”, test input “P1_ma1 = 0”, test input “P2_cull = false”, test input “P2_cClass = 0”, test input “P2_ma1 = 1 "is copied from the first test case to the second test case.

  FIG. 45 shows an example of a second test case generation process flow. The second generation unit 1033 repeats the following process for each case number (S4501). The second generation unit 1033 further repeats the following process for each symbol path condition (S4503). The second generation unit 1033 determines whether the symbol path condition includes a control variable name (S4505). If it is determined that the symbol path condition does not include the control variable name, the second generation unit 1033 copies the symbol path condition (S4507). On the other hand, when it is determined that the symbol path condition includes the control variable name, the second generation unit 1033 does not copy the symbol path condition. The second generation unit 1033 determines whether all symbol path conditions have been processed (S4509). If it is determined that there is an unprocessed symbol path condition, the second generation unit 1033 returns the process to S4503. If it is determined that all symbol path conditions have been processed, the second generation unit 1033 moves the process to S4511.

  Subsequently, the second generation unit 1033 repeats the following process for each object path condition (S4511). The second generation unit 1033 identifies a semantic expression that matches the object path condition in the control variable table (S4513). The second generation unit 1033 identifies the control variable name and value corresponding to the semantic expression, generates an in-target path condition using the control variable and value, and adds it to the second test case (S4515). For example, in the example of FIG. 44, the control variable name “P1_cull” and the value “false” corresponding to the semantic expression “P1! = Null” that matches the object condition “P1! = Null” are specified. Then, the in-target path condition “P1_cull == false” is generated.

  This is a case where the object path condition has a negative form, and the semantic expression may be specified by replacing the object path condition with a positive form. In this case, the in-target path condition is generated by replacing the path condition using the control variable and the value with a negative form.

  For example, the semantic expression “P1 instance of B” is identified by replacing the negative form object path condition “! (P1 instance of B)” with the positive form “P1 instance of B” in the example of FIG. Then, the control variable name “P1_cClass” and the value “1” corresponding to the semantic expression “P1 instanceof B” are specified, the path condition “P1_cClass == 1” is generated, and the in-target path condition “P1_cClass” is replaced with the negative form. ! = 1 ”is generated.

  Note that member variables that are not control variables may be converted into the in-target path condition according to the conversion rules for member variables. In the example of FIG. 44, for example, in the conversion rule, it is defined that “P2.ma1” corresponds to “P2_ma1” and “P1.ma1” corresponds to “P1_ma1”, the object condition “P2.ma1”. > P1.ma1 ”is converted into the in-target path condition“ P2_ma1> P1_ma1 ”.

  As shown in FIG. 44, the symbol path condition “P2_ma1> P1_ma1” regarding the symbol variable “P1_ma1” and the symbol variable “P2_ma1” has the same content. When the contents are the same, only one target path condition is set. The second generation unit 1033 determines whether all object path conditions have been processed (S4517). If it is determined that there is an object path condition that has not been processed, the process returns to S4511.

  On the other hand, if it is determined that all object path conditions have been processed, the second generation unit 1033 copies the test input of the first test case to the second test case (S4519). The second generation unit 1033 determines whether all case numbers have been processed (S4521). If it is determined that there is a case number that has not been processed, the second generation unit 1033 returns the process to S4501. If all case numbers have been processed, the second generation unit 1033 ends the process.

  An example of the second test case is shown in FIGS. 46a to 46c. A second test case corresponding to the first test case is generated. For example, the second test cases of case number 1 to case number 4 have the same in-target path condition “P1_cnull == true”. Case number 1 to case number 4 indicate that the same route of the test target program is passed. In the test case of case number 1, when the test input “P1_cull = true” and the test input “P2_cnull = true” are input and the target class shown in FIG. 5 is executed, “if (obj1! = Null)” is false. And the route that ends with “return 0” is passed. Further, in the test case of case number 2, when the test input “P1_cull = true”, the test input “P2_cull = false” and the test input “P2_cClass = 0” are input and the target class shown in FIG. 5 is executed Similarly, “if (obj1! = Null)” is determined to be false, and a route ending with “return 0” is taken. Furthermore, in the test case of case number 3, when the test input “P1_cull = true”, the test input “P2_cull = false”, and the test input “P2_cClass = 1” are input and the target class shown in FIG. 5 is executed Similarly, “if (obj1! = Null)” is determined to be false, and a route ending with “return 0” is taken. Furthermore, in the test case of case number 4, when the test input “P1_cull = true”, the test input “P2_cull = false”, and the test input “P2_cClass = −1” are input and the target class shown in FIG. 5 is executed Similarly, “if (obj1! = Null)” is determined to be false, and a route ending with “return 0” is passed. As described above, since a plurality of test cases passing through the same route of the program to be tested are redundant, it is desirable to reduce them.

  FIG. 47 shows an example of the third test case. In this example, the test case with the smallest case number among the plurality of second test cases passing through the same route is moved to the third test case, and the other cases are excluded. For example, among the second test cases of case number 1 to case number 4, the second test case of case number 1 is moved to the third test case set, but the second test case of case number 2 to case number 4 is the second test case. 3 Not transferred to test case set.

  FIG. 48 is a diagram illustrating an example of a test case extraction process flow. The extraction unit 1037 repeats the following process for each second test case (S4801). The extraction unit 1037 determines whether there is a third test case having the same path condition as that of the second test case (S4803). That is, the extraction unit 1037 determines whether or not a third test case having the same pass condition as the second test case pass condition is stored in the third test case storage unit 1039. If it is determined that there is a third test case having the same pass condition as the pass condition of the second test case, the extraction unit 1037 advances the process to S4807.

  If it is determined that there is no third test case having the same pass condition as the pass condition of the second test case, the extraction unit 1037 adds the second test case to the third test case (S4805). That is, the extraction unit 1037 stores the second test case in the third test case storage unit 1039. The extraction unit 1037 determines whether or not all the second test cases have been processed (S4807). If it is determined that there is a second test case that has not been processed, the process returns to S4801. If it is determined that all the second test cases have been processed, the extraction unit 1037 outputs the third test case set (S4809) and ends.

  The path condition update process and the test case extraction process described above may be performed continuously or separately. By performing the path condition update process and the test case extraction process, it is possible to reduce the number of test cases without reducing the code coverage that has been enhanced by the symbolic execution using the control variable.

  Although one embodiment of the present technology has been described above, the present technology is not limited to this. For example, the functional block configuration described above does not necessarily correspond to the actual program module configuration.

  The configuration of each storage area described above is an example, and the configuration as described above is not necessarily required. Further, in the processing flow, the processing order can be changed if the processing result does not change. Further, it may be executed in parallel.

  The test case generation device described above is a computer device, and as shown in FIG. 49, a memory 2501, a CPU (Central Processing Unit) 2503, a hard disk drive (HDD: Hard Disk Drive) 2505, and a display device. A display control unit 2507 connected to 2509, a drive device 2513 for the removable disk 2511, an input device 2515, and a communication control unit 2517 for connecting to a network are connected by a bus 2519. An operating system (OS: Operating System) and an application program for executing the processing in this embodiment are stored in the HDD 2505, and are read from the HDD 2505 to the memory 2501 when executed by the CPU 2503. The CPU 2503 controls the display control unit 2507, the communication control unit 2517, and the drive device 2513 according to the processing content of the application program, and performs a predetermined operation. Further, data in the middle of processing is mainly stored in the memory 2501, but may be stored in the HDD 2505. In an embodiment of the present technology, an application program for performing the above-described processing is stored in a computer-readable removable disk 2511 and distributed, and installed from the drive device 2513 to the HDD 2505. In some cases, the HDD 2505 may be installed via a network such as the Internet and the communication control unit 2517. Such a computer apparatus realizes various functions as described above by organically cooperating hardware such as the CPU 2503 and the memory 2501 described above and programs such as the OS and application programs. .

  The embodiment described above is summarized as follows.

  The program according to the first embodiment uses (A) one or a plurality of symbol variables including a control variable indicating a state of an object type variable input to a test target program, and an object type corresponding to the control variable. For each execution pattern in the driver for initiating the variable and invoking the test target program and in the called test target program, the first variable to be satisfied by one or more symbol variables in the execution of the driver and the test target program A symbolic execution process for calculating a path condition and generating a first test case including a first path condition and a satisfaction value of one or more symbol variables for the first path condition; and (B) for each execution pattern The second path condition to be satisfied by the object type variable as a state in the execution of the test target program The first generation process to be generated, and (C) the first pass condition included in the first test case for each execution pattern, the condition to be satisfied by the control variable is omitted, and the second pass condition is added. And (D) the third path condition is synonymous with the second generation process of generating a second test case including the third path condition and a sufficiency value of one or more symbol variables. When there are a plurality of second test cases, any one of the plurality of second test cases having the same third pass condition is omitted, and the remaining second test case The computer executes an extraction process for extracting.

  Since the symbolic execution process as described above is executed, it is possible to improve the coverage of the test case in the test target program including the branch process related to the state of the object type variable.

  Furthermore, since test cases are narrowed down as described above, test cases that do not contribute to improvement in coverage can be eliminated. In other words, even among test cases having different conditions to be satisfied by the control variable, if the second path condition is common, the execution route in the test target program is the same. Therefore, waste can be reduced by omitting one of the test cases.

  In the symbolic execution process, an instruction to be executed may be specified from among a plurality of instructions included in the test target program. In this case, in the first generation process, the position for referring to the entity of the variable included in the instruction to be executed is specified, and the position for storing the object type variable coincides with the position for reference. In this case, the second path condition may be generated based on the instruction to be executed.

  In this way, when the position for referring to the entity of the variable included in the instruction to be executed matches the position where the entity of the object type variable is stored, the second is determined based on the instruction to be executed. Therefore, it is possible to obtain a path condition for an object type variable that is not a symbol variable.

  In the symbolic execution process, the first instruction included in the driver and including the object type variable is specified, the object type variable is specified based on the first instruction, and the specified object type variable You may make it make a computer perform the specific process which specifies the position where an entity is stored.

  In this way, the object type variable is specified based on the first instruction included in the driver, and the position where the entity of the object type variable is stored is specified. Therefore, the driver generates the second path condition. You will be able to give instructions. Therefore, it is not necessary to modify the program to be tested.

  In the second generation process, the second path condition may be converted into a format of a condition that the control variable should satisfy.

  In this way, since the second path condition is converted into the format of the condition that the control variable should satisfy, the path condition and the satisfaction value of the symbol variable in the branch related to the state of the object type variable are both represented by the control variable. Therefore, it becomes easy to grasp these relationships.

  The state may be specified by whether or not the object type variable is null.

  In this way, it is possible to generate a test case of a program including a branch depending on whether or not the object type variable is null.

  The state may be specified by the class type of the object type variable.

  In this way, it is possible to generate a test case of a program including a branch by the class type of the object type variable.

  The plurality of symbol variables may include a symbol variable indicating a member of an object type variable.

  In this way, it is possible to generate a test case for a program including a branch by a member of an object type variable.

  The plurality of symbol variables may include a symbol variable indicating a primitive type variable input to a test target program.

  In this way, it is possible to generate a test case for a program including a branch by a primitive type variable.

  In the extraction process, a plurality of second test cases having the same third pass condition may be omitted except for one second test case.

  In this way, the number of test cases can be reduced.

  A program for causing a computer to perform the processing according to the above method can be created. The program can be a computer-readable storage medium such as a flexible disk, a CD-ROM, a magneto-optical disk, a semiconductor memory, a hard disk, or the like. It is stored in a storage device. Note that intermediate processing results are temporarily stored in a storage device such as a main memory.

  The following supplementary notes are further disclosed with respect to the embodiments including the above examples.

(Appendix 1)
Using one or a plurality of symbol variables including a control variable indicating the state of the object type variable input to the test target program, initialization of the object type variable according to the control variable and calling of the test target program For each execution pattern in the driver and the test target program to be called, calculate a first path condition that the one or more symbol variables should satisfy in the execution of the driver and the test target program, and A symbolic execution process for generating a first test case including a first pass condition and a sufficiency value of the one or more symbol variables with respect to the first pass condition;
For each execution pattern, a first generation process for generating a second path condition that the object type variable should satisfy as the state in the execution of the test target program;
For each execution pattern, from the first path condition included in the first test case, a condition that the control variable should satisfy is omitted, and a third path condition is obtained by adding the second path condition; A second generation process for generating a second test case including the third pass condition and the sufficiency value of the one or more symbol variables;
When there are a plurality of the second test cases in which the third pass condition is synonymous, any one of the second test cases in which the third pass condition is synonymous. An extraction process for omitting the test case and extracting the remaining second test case;
A program that causes a computer to execute.

(Appendix 2)
In the symbolic execution process, an instruction to be executed is specified from among a plurality of instructions included in the test target program,
In the first generation process, the position for referring to the entity of the variable included in the instruction to be executed is specified, and the position where the entity of the object type variable is stored matches the position for referring The program according to claim 1, wherein the second path condition is generated based on the instruction to be executed.

(Appendix 3)
In the symbolic execution process, a first instruction included in the driver and including the object type variable is specified,
The program according to claim 2, further comprising: specifying the object type variable based on the first instruction, and causing the computer to execute a specifying process for specifying the position where the entity of the specified object type variable is stored. .

(Appendix 4)
The program according to any one of additions 1 to 3, wherein, in the second generation process, the second path condition is converted into a format of a condition to be satisfied by the control variable.

(Appendix 5)
The program according to any one of appendices 1 to 4, wherein the state is specified by whether or not the object type variable is null.

(Appendix 6)
The program according to any one of appendices 1 to 4, wherein the state is specified by a class type of the object type variable.

(Appendix 7)
The program according to any one of appendices 1 to 6, wherein the plurality of symbol variables include a symbol variable indicating a member of the object type variable.

(Appendix 8)
The program according to any one of appendices 1 to 7, wherein the plurality of symbol variables include a symbol variable indicating a primitive type variable input to the test target program.

(Appendix 9)
The program according to any one of appendices 1 to 8, wherein the extraction process excludes a plurality of second test cases other than the second test case among the plurality of second test cases having the same third pass condition.

(Appendix 10)
Using one or a plurality of symbol variables including a control variable indicating the state of the object type variable input to the test target program, initialization of the object type variable according to the control variable and calling of the test target program For each execution pattern in the driver and the test target program to be called, calculate a first path condition that the one or more symbol variables should satisfy in the execution of the driver and the test target program, and A symbolic execution process for generating a first test case including a first pass condition and a sufficiency value of the one or more symbol variables with respect to the first pass condition;
For each execution pattern, a first generation process for generating a second path condition that the object type variable should satisfy as the state in the execution of the test target program;
For each execution pattern, from the first path condition included in the first test case, a condition that the control variable should satisfy is omitted, and a third path condition is obtained by adding the second path condition; A second generation process for generating a second test case including the third pass condition and the sufficiency value of the one or more symbol variables;
When there are a plurality of the second test cases in which the third pass condition is synonymous, any one of the second test cases in which the third pass condition is synonymous. An extraction process for omitting the test case and extracting the remaining second test case;
A test case generation method executed by a computer.

(Appendix 11)
Using one or a plurality of symbol variables including a control variable indicating the state of the object type variable input to the test target program, initialization of the object type variable according to the control variable and calling of the test target program For each execution pattern in the driver and the test target program to be called, calculate a first path condition that the one or more symbol variables should satisfy in the execution of the driver and the test target program, and An execution unit that performs symbolic execution to generate a first test case including a first pass condition and a satisfaction value of the one or more symbol variables with respect to the first pass condition;
A first generation unit that generates, for each execution pattern, a second path condition that the object type variable should satisfy as the state in the execution of the test target program;
For each execution pattern, from the first path condition included in the first test case, a condition that the control variable should satisfy is omitted, and a third path condition is obtained by adding the second path condition; A second generation unit that generates a second test case including the third pass condition and the sufficiency value of the one or more symbol variables;
When there are a plurality of the second test cases in which the third pass condition is synonymous, any one of the second test cases in which the third pass condition is synonymous. An extraction unit for omitting the test case and extracting the remaining second test case;
A test case generation device having:

701 Symbol variable declaration area 703 Target class initialization area 705 Initialization code area 707 Object specification instruction area 709 Target method call area 1001 Reception unit 1003 Target class storage unit 1005 Library storage unit 1007 Sample form storage unit 1009 Driver generation unit 1011 Driver Storage unit 1013 Control variable table generation unit 1015 Control variable table storage unit 1017 Execution unit 1019 Pattern table storage unit 1021 Symbol variable table storage unit 1023 Identification unit 1025 Object table storage unit 1027 First test case storage unit 1029 First generation unit 1031 Object Pass condition storage unit 1033 Second generation unit 1035 Second test case storage unit 1037 Extraction unit 1039 Third test case Storage unit 1041 Test case output unit

Claims (6)

Using one or a plurality of symbol variables including a control variable indicating the state of the object type variable input to the test target program, initialization of the object type variable according to the control variable and calling of the test target program For each execution pattern in the driver and the test target program to be called, calculate a first path condition that the one or more symbol variables should satisfy in the execution of the driver and the test target program, and A symbolic execution process for generating a first test case including a first pass condition and a sufficiency value of the one or more symbol variables with respect to the first pass condition;
For each execution pattern, a first generation process for generating a second path condition that the object type variable should satisfy as the state in the execution of the test target program;
For each execution pattern, from the first path condition included in the first test case, a condition that the control variable should satisfy is omitted, and a third path condition is obtained by adding the second path condition; A second generation process for generating a second test case including the third pass condition and the sufficiency value of the one or more symbol variables;
When there are a plurality of the second test cases in which the third pass condition is synonymous, any one of the second test cases in which the third pass condition is synonymous. An extraction process for omitting the test case and extracting the remaining second test case;
A program that causes a computer to execute. In the symbolic execution process, an instruction to be executed is specified from among a plurality of instructions included in the test target program,
In the first generation process, the position for referring to the entity of the variable included in the instruction to be executed is specified, and the position where the entity of the object type variable is stored matches the position for referring The program according to claim 1, wherein the second path condition is generated based on the instruction to be executed. In the symbolic execution process, a first instruction included in the driver and including the object type variable is specified,
3. The computer according to claim 2, further comprising: specifying the object type variable based on the first instruction, and causing the computer to execute a specifying process for specifying the position where the entity of the specified object type variable is stored. program. The program according to any one of claims 1 to 3, wherein, in the second generation process, the second path condition is converted into a format of a condition to be satisfied by the control variable. Using one or a plurality of symbol variables including a control variable indicating the state of the object type variable input to the test target program, initialization of the object type variable according to the control variable and calling of the test target program For each execution pattern in the driver and the test target program to be called, calculate a first path condition that the one or more symbol variables should satisfy in the execution of the driver and the test target program, and A symbolic execution process for generating a first test case including a first pass condition and a sufficiency value of the one or more symbol variables with respect to the first pass condition;
For each execution pattern, a first generation process for generating a second path condition that the object type variable should satisfy as the state in the execution of the test target program;
For each execution pattern, from the first path condition included in the first test case, a condition that the control variable should satisfy is omitted, and a third path condition is obtained by adding the second path condition; A second generation process for generating a second test case including the third pass condition and the sufficiency value of the one or more symbol variables;
When there are a plurality of the second test cases in which the third pass condition is synonymous, any one of the second test cases in which the third pass condition is synonymous. An extraction process for omitting the test case and extracting the remaining second test case;
A test case generation method executed by a computer. Using one or a plurality of symbol variables including a control variable indicating the state of the object type variable input to the test target program, initialization of the object type variable according to the control variable and calling of the test target program For each execution pattern in the driver and the test target program to be called, calculate a first path condition that the one or more symbol variables should satisfy in the execution of the driver and the test target program, and An execution unit that performs symbolic execution to generate a first test case including a first pass condition and a satisfaction value of the one or more symbol variables with respect to the first pass condition;
A first generation unit that generates, for each execution pattern, a second path condition that the object type variable should satisfy as the state in the execution of the test target program;
For each execution pattern, from the first path condition included in the first test case, a condition that the control variable should satisfy is omitted, and a third path condition is obtained by adding the second path condition; A second generation unit that generates a second test case including the third pass condition and the sufficiency value of the one or more symbol variables;
When there are a plurality of the second test cases in which the third pass condition is synonymous, any one of the second test cases in which the third pass condition is synonymous. An extraction unit for omitting the test case and extracting the remaining second test case;
A test case generation device having:

Images