WO2024232193A1 - Information processing device, information processing method, and computer program - Google Patents

Abstract

Provided is an information processing device that generates a test code having high coverage.　This information processing device is equipped with: an analysis unit that analyzes a source code so as to collect type information for the source code and generate an object initialization function; a symbol execution driver generation unit that uses the type information and the object initialization function to generate a symbol execution driver; a symbol execution unit that executes the symbol execution driver generated by the symbol execution driver generation unit so as to generate a test case; and a test code generation unit that generates test code for feeding the test case generated by the symbol execution unit into a program to be tested and executing the same.

Description

Information processing device, information processing method, and computer program

The technology disclosed in this specification (hereinafter referred to as "this disclosure") relates to an information processing device and information processing method that perform processing related to program development, and a computer program.

In software development, program behavior that differs from the specifications or is not expected by the developer is a defect, and all defects must be corrected and eliminated before release. Testing is performed to detect program defects and ensure operation. For example, testing is performed by creating test cases with inputs and outputs described in the specifications or expected by the developer, and checking whether the program returns the correct output for the input. If the correct output is not returned for the input, or if an exception (fault) occurs and the program does not operate, it is determined to be a defect. The developer then analyzes the program to identify the cause and correct the program logic. To ensure high quality and reliability of the program, tests must be performed with high coverage.

JP 2018-45325 A

The objective of this disclosure is to provide an information processing device, an information processing method, and a computer program that perform processing to generate high-coverage test code.

The present disclosure has been made in consideration of the above problems, and a first aspect thereof is:
an analysis unit that analyzes source code to collect type information of the source code and generate object initialization functions;
a symbolic execution driver generator that generates a symbolic execution driver using the type information and an object initialization function;
a symbolic execution unit that executes the symbolic execution driver generated by the symbolic execution driver generation unit to generate a test case;
a test code generation unit that generates a test code for applying the test cases generated by the symbol execution unit to a program under test and executing the program;
The information processing device includes:

The analysis unit performs static analysis on the program to be tested, which is written in a statically typed language, and examines the types of variables created by the function that calls the function to be tested and the functions that pass them, thereby narrowing down the types of arguments to be passed to the function to be tested.

The analysis unit also instruments the dynamically typed language program under test so that the types of variables passed to the function under test are output as an execution trace immediately before the function under test is called, passes input to the instrumented program, executes it, collects the execution trace, and analyzes the type information and objects of the variables passed to the function under test from the collected execution trace.

The analysis unit also performs instrumentation to output, as an execution trace, the methods that were called from when an object was created until it was deleted, and the order in which they were called, so that the method sequence for initializing each object can be collected, and analyzes the execution trace to generate an object initialization function.

The symbolic execution driver generation unit initializes and symbolizes variables to be passed to the function to be tested, and generates a symbolic execution driver consisting of code that simply calls the function to be tested.

The test code generation unit executes the symbol execution driver generated by the symbol execution driver generation unit on a symbol execution engine, and generates test code for the function to be tested using the test cases generated as input values.

In addition, a second aspect of the present disclosure is
an analysis step of analyzing the source code to generate type information and object initialization functions for the source code;
a symbolic execution driver generation step of generating a symbolic execution driver using the type information and an object initialization function;
a symbolic execution step of executing the symbolic execution driver generated in the symbolic execution driver generation step to generate a test case;
a test code generation step of generating test code for applying the test cases generated in the symbol execution step to a program under test and executing the program;
The information processing method includes the steps of:

In addition, a third aspect of the present disclosure is
an analysis unit that analyzes the source code and generates type information and object initialization functions for the source code;
a symbolic execution driver generator that generates a symbolic execution driver using the type information and an object initialization function;
a symbolic execution unit that executes the symbolic execution driver generated by the symbolic execution driver generation unit to generate test cases;
a test code generation unit that generates a test code for applying the test cases generated by the symbol execution unit to a program to be tested and executing the program;
It is a computer program written in a computer-readable form to cause a computer to function as a

The computer program according to the third aspect of the present disclosure defines a computer program written in a computer-readable format to realize a specified process on a computer. The computer program can be provided to a computer capable of executing various program codes in a computer-readable format via a storage medium or communication medium, such as an optical disk, magnetic disk, or semiconductor memory, or a communication medium such as a network. By installing the computer program according to the third aspect of the present disclosure on a computer via any of the media, a cooperative effect is exerted on the computer, and the same effect as that of the information processing device according to the first aspect of the present disclosure can be obtained.

According to the present disclosure, it is possible to provide an information processing device, information processing method, and computer program that, when testing a program, analyzes source code and automatically generates argument type information and object initialization functions to create meaningful test cases.

Note that the effects described in this specification are merely examples, and the effects brought about by this disclosure are not limited to these. Furthermore, this disclosure may have additional effects in addition to the effects described above.

Further objects, features and advantages of the present disclosure will become apparent from the following detailed description based on the embodiments and the accompanying drawings.

FIG. 1 is a diagram showing a functional configuration of an automatic test generation device 100 to which the present disclosure is applied. FIG. 2 is a flowchart showing an example of a processing procedure for automatically generating test code for a source code. FIG. 3 is a diagram showing an example of the hardware configuration of the information processing device 2000.

The following describes the embodiments of the present disclosure with reference to the drawings in the following order:

A. Overview B. Configuration of automatic test generation tool B-1. Generation of type information B-1-1. Static analysis B-1-2. Dynamic analysis B-2. Generation of object initialization functions B-2-1. Dynamic analysis B-2-2. Generation of new method sequences B-2-2-1. Random generation B-2-2-2. Mutation B-2-2-3. Use of machine learning B-2-2-4. Evaluation of generated method sequences B-2-3. Generation of object initialization functions B-3. Generation of symbolic execution driver B-4. Symbolic execution and test code generation C. Test code generation processing procedure D. Configuration of information processing device

A. Overview In statically typed languages such as C/C++, ambiguous type expressions such as void pointers can be used. In dynamically typed languages, there is no need to specify the type of arguments passed to functions, so values or objects of any type can be passed. The exact type of variable passed to a function cannot be known until the program is executed.

To automatically generate effective test code with high coverage, the user (such as the program developer) must add type annotations to each function that uses a void pointer or each function in a dynamically typed language. Without these annotations, meaningless tests that simply pass a null pointer to a function that uses a void pointer, tests that cause null pointer dereference exceptions, or huge test cases that use all types used in the program as input will be generated.

In object-oriented languages, if the object of the class being tested or the object of the class being passed to the function being tested is not properly initialized, the processing of the class or function being tested may not be executed correctly. For example, consider the linked list (bidirectional list) class. The linked list class provides methods such as add (adding and inserting an element), size (getting the number of elements), get (getting the object stored in an element), set (replacing an element), and remove (deleting an element). When generating a test for the remove method (a method that deletes one node from the linked list), you must execute the add method to add one node to the linked list before executing the remove method, so that the linked list is not empty, otherwise the processing you actually want to test in the remove method (processing to delete a node) will not be executed. However, it is not possible to know exactly how to initialize an object before testing a method without actually running and analyzing the program. In other words, in the case of object-oriented languages, the behavior you actually want to test is not performed, and meaningless test cases are generated. For this reason, users need to create functions to be used for object initialization and pass them to the automatic test code generation tool.

In short, to automatically generate meaningful tests with high coverage that reflect the user's design intent, it is necessary for the user to input type information annotations and object initialization functions. However, it is a very cumbersome task for the user to provide type information and object initialization functions for all functions to be tested, and it places a heavy burden on the user.

For example, a test support device has been proposed that uses annotations to automatically generate drivers and stubs for functions to be tested in a dynamic typed language, while generating correct test drivers and stubs even when incorrect annotations (comments in the source code) are added (see Patent Document 1). Here, a test driver is a program for calling and executing functions and classes to be tested. Also, a stub is a dummy function and class that is called by the functions and classes to be tested (stubs may be created so that tests can be performed even for functions and classes that are difficult to test because they access a network or database). This test support device repeatedly modifies the driver so that the error is eliminated when an undefined method of an object given as a test case is called in the function to be tested, and ultimately generates a correct test driver. However, it is a very cumbersome task for the user to add annotations to all functions to be tested, which places a heavy burden on the user.

In this disclosure, we propose a technology for automatically generating high-coverage test code by analyzing source code and automatically generating type information and object initialization functions. According to this disclosure, meaningful test code with high coverage that reflects the user's design intent can be automatically generated, even if the user does not provide type information for the source code or initialization functions for objects.

　An automatic test code generation tool to which the present disclosure is applied does not require the user to input type annotations or object initialization functions. In addition, an automatic test code generation tool to which the present disclosure is applied can generate test code with restricted types for void pointers and function arguments in dynamically typed languages, and can generate test code that uses object initialization functions.

In this specification, the terms "test code," "test case," and "coverage" are used with the following meanings:

Test code: This is the source code for providing various test cases to the program and executing them.
Test case: An input given to the program under test.
Coverage: In this specification, "coverage" refers to line coverage, which is the percentage of which lines of source code are executable and which are not.

"Source code" and "program" both refer to computer programs, but the former refers to a data format that is easy for humans to understand and write, such as a programming language, while the latter program refers to a format that has been built into an executable format. Also, "function" and "method" are synonymous, but a function that belongs to an object is called a "method."

B. Configuration of the Automatic Test Generation Tool FIG. 1 shows a schematic functional configuration of an automatic test generation device 100 to which the present disclosure is applied. The automatic test generation device 100 inputs source code, and outputs test code for executing the source code by providing various test cases. A downstream test execution device (not shown) can execute a high-coverage test of the source code using the test code generated by the automatic test generation device 100. The automatic test generation device 100 can be realized using a general information processing device such as a personal computer (PC). The automatic test generation device 100 may also be a device that is physically integrated with the test execution device.

The automatic test generation device 100 shown in FIG. 1 includes a type information generation unit 101, an object initialization function generation unit 102, a symbol execution driver generation unit 103, a symbol execution unit 104, and a test code generation unit 105.

The type information generation unit 101 is configured to analyze the source code of the test target and generate type information. Similarly, the object initialization function generation unit 102 is configured to analyze the source code of the test target and generate an object initialization function. Therefore, since the automatic test generation device 100 automatically generates type information and object initialization functions internally, it is possible to automatically generate meaningful test code with high coverage even if the user does not provide type information of the source code or initialization functions of objects.

B-1. Generation of Type Information In this section B-1, we will explain how the type information generator 101 generates type information necessary for generating tests with high coverage and little waste.

B-1-1. When the source code to be tested for static analysis is written in a statically typed language, the type information generating unit 101 first performs a static analysis to find out what type of variables are created in the function that calls the function to be tested and passed as arguments to the function to be tested, thereby narrowing down the types of variables to be passed to a certain number of functions.

For example, consider the function swap, which has the code shown below. This function swap takes a void pointer as an argument.

Any type is allowed for a void pointer, but the type information generation unit 101 refers to the line in the above source code where the function under test is called, and checks what type of variable is passed by the function that called the function under test. In the above source code example, the type information generation unit 101 checks line 7 and finds that the function under test swap is called by function function, and further checks line 5 and finds that function function declares the types of variables x and y that it passes to function swap under test. Therefore, the type information generation unit 101 can narrow down the type passed to function swap under test to type int.

B-1-2. Dynamic AnalysisThe simple static analysis described in B-1-1 above is not enough to accurately narrow down the type for all cases. Also, if the source code to be tested is written in a dynamically typed language, any type of value or object can be stored in the same variable, so it is impossible to determine what type of value or object is passed to the function unless the program is actually run. For such functions, type information is collected by performing the dynamic analysis described in B-1-2.

When performing dynamic analysis, first, the type information generation unit 101 instruments the program under test so that the types of variables to be passed to the functions under test are output as an execution trace immediately before calling each function under test. Next, the type information generation unit 101 passes input to the instrumented program and executes it. At this time, the type information generation unit 101 can generate input to the program using test case generation techniques such as random generation, fuzzing, and symbolic execution. When generating input to a program using fuzzing and symbolic execution, there are techniques for efficiently searching to reach a specific line of the program, and by using such techniques, it is possible to find the input that executes the function under test and efficiently obtain an execution trace.

Then, the type information generation unit 101 generates such test cases and executes the program to be tested using the generated test cases as input for a certain period of time, and from the execution trace collected, analyzes what types of variables and objects are being passed to the function to be tested.

For example, suppose the function to be tested is the function add, which consists of the following code. In the fourth line of this code, the arguments x and y of the function to be tested add are passed as int type, and in the fifth line, the arguments x and y of the function to be tested add are passed as float type.

The type information generation unit 101 performs instrumentation for the above add function so that the types of the variables passed to the function are output as an execution trace, and by inputting and executing a test case generated by a predetermined method, it is possible to obtain an execution trace such as the one shown below. This execution trace includes a trace result in which an int type is passed to the arguments x and y of the test target function add, which corresponds to the fourth line of the source code, and a trace result in which a float type is passed to the arguments x and y of the test target function add, which corresponds to the fifth line of the source code. One of the features of this disclosure is that an automatic test generation tool outputs such an execution trace as an intermediate product.

Therefore, from the above execution trace, the type information generation unit 101 can obtain type information that the arguments x and y of the test target function add may be of type int or of float.

The symbolic execution driver generation unit 103 in the latter stage generates a symbolic execution driver using the type information collected by the type information generation unit 101 through static and dynamic analysis of the source code. However, details of the symbolic execution driver generation will be explained in Section B-3 below.

Fuzzing is a technique for testing the behavior of a program by repeatedly running the program while modifying randomly generated input values or input values received from the user to generate new input values. Fuzzing can be done in two ways: by modifying part of the input values to increase the coverage of the program, or by modifying part of the input values to reach a specific line in the program.

Symbolic execution is a method for comprehensively exploring the behavior of a program by treating the program inputs as symbolic values (symbols) rather than concrete values. The program is executed while collecting the program's branching conditions, and when the search for each execution path is finished, the branching conditions collected up to that point are solved using a constraint solver, making it possible to generate input values that will take that execution path.

B-2. Generation of Object Initialization Functions This section B-2 describes a method for the object initialization function generator 102 to automatically generate object initialization functions that are required to generate high-coverage tests for code to be tested in an object-oriented language.

B-2-1. Dynamic Analysis As explained in B-1-2 above, the object initialization function generation unit 102 instruments the program to be tested, inputs input values generated using test case generation techniques such as random generation, fuzzing, and symbolic execution to the instrumented program, executes the program, and obtains an execution trace.

However, the object initialization function generation unit 102 records, as an execution trace, which methods of an object were called and in what order from the time the object was created to the time it was deleted, so that it can collect the method sequence for initializing each object. For this reason, the object initialization function generation unit 102 instruments the program to be tested so that it outputs the object type name, object identification information, and the called method name as an execution trace immediately before calling a method. The object initialization function generation unit 102 then passes input to the instrumented program, executes it, collects the execution trace, extracts the method sequence for initializing the object from the collected execution trace, and generates an object initialization function from the extracted method sequence.

As an example, we will explain the case where an execution trace is collected for the following code. In this code, an object s1 of the SampleClass class is generated on line 12, and an object s2 of the SampleClass class is generated on line 13. Furthermore, the methods init, setLocation, calc, and finalize of object s1 are called in order on lines 14, 16, 17, and 19, respectively, and the methods init, calc, and finalize of object s2 are called in order on lines 15, 18, and 20, respectively. The object initialization function generation unit 102 performs instrumentation on this code just before calling a method so that the object type name, object identification information, and the name of the called method are output as an execution trace.

The object initialization function generation unit 102 instruments the above code, inputs the generated test cases into the instrumented program, and executes them to collect the object type name (Class), object identification information (id), and called method name (function) as an execution trace, as shown below. Note that the object type name is SampleClass. Also, let us assume that objects s1 and s2 generated from SampleClass are automatically assigned object identification information "1" and "2", respectively.

The object initialization function generation unit 102 can extract, from the information obtained by the above execution trace, a method sequence that indicates what methods were called and in what order for the object to be passed to the function under test from the time the object to be passed to the function under test was generated until the function under test was called. By summarizing the above execution trace for each object's identification information, the object initialization function generation unit 102 can obtain the following two method sequences: method sequence 1 corresponding to object s1 and method sequence 2 corresponding to object s2.

Method sequence 1: init → setLocation → calc → finalize
Method sequence 2: init → calc → finalize

Note that the process of acquiring the execution trace by the object initialization function generation unit 102 described in section B-2-1 can be performed together with the process performed by the type information generation unit 101 described in section B-1-2 above. One of the features of the present disclosure is that the automatic test generation tool outputs such an execution trace as an intermediate product (ibid.).

B-2-2. Creation of a new method sequence There are cases where the information from the execution trace described in B-2-1 above is insufficient. For this reason, the object initialization function generation unit 102 creates a new method sequence using the method described in B-2-2, and adds it to create an object initialization function.

There are three ways to generate a method sequence: random generation, mutation, and machine learning. Each generation method is explained below.

B-2-2-1. Random Generation In this method, a sequence is randomly generated from among the public methods of the object passed to the function under test.

B-2-2-2. Mutation In this method, a new method sequence is generated by modifying part of the method sequence extracted by the dynamic analysis described in B-2-1 above. There are three ways to modify part of the method sequence: adding a method, deleting a method, and modifying a method.

Adding a Method: Randomly select one of the object's public methods and insert it at a random position in the method sequence.
Method deletion: Randomly select one method from the sequence and delete it.
Method modification: Randomly select one method from the set of methods and replace it with another public method.

B-2-2-3. Use of Machine Learning In this method, the execution trace collected by the dynamic analysis described in B-2-1 above is used to learn what methods of the object passed to the test target function are called before the test target function is called. For example, by learning from naming conventions that when the test target function is remove**, functions such as add**, init**, and insert** tend to be called before calling such a method, even if the test target function does not appear in the execution trace, a sequence of methods that must be executed before calling the test target function can be generated.

B-2-2-4. Evaluation of generated method sequence The object initialization function generation unit 102 evaluates the new method sequence generated by modifying it using at least one of the above-mentioned random generation, mutation, and machine learning methods, deletes unnecessary method sequences that do not contribute to coverage, and leaves only method sequences that can increase coverage.

Specifically, the object initialization function generation unit 102 generates a test driver using the newly generated method sequence, and performs fuzzing and symbolic execution on the test driver to measure coverage. Only those method sequences that cover lines that cannot be reached by existing method sequences are retained, and those that do not are deleted. The object initialization function generation unit 102 repeats this process for a fixed period of time, or until coverage no longer improves.

For example, consider the case where a method change is made to the method sequence 1: init → setLocation → calc → finalize shown in section B-2-1 above. As an example, a mutation (method change) can be used to change the method setLocation included in method sequence 1 to another method, finalize, to generate a new method sequence 1': init → finalize → calc → finalize as shown below.

Method sequence 1': init → finalize → calc → finalize

If the calc method is a function for which tests are to be generated, a test driver like the one below is generated, and fuzzing and symbolic execution are performed on this test driver.

At this time, the coverage of calc is measured. If the unreached lines of the calc method can be covered, new method sequence 1' is added as a method sequence of SampleClass. On the other hand, if the unreached lines of the calc method cannot be covered, this new method sequence 1' is deleted, and in the future, when creating a new method sequence, no changes will be made to make it the same as method sequence 1'.

B-2-3. Generation of Object Initialization Function The object initialization function generation unit 102 generates an object initialization function that initializes an object using a newly generated method sequence according to the explanation in B-2-2 above. When the calc method in the above SampleClass example is the function for which test generation is to be performed, the object initialization function generation unit 102 generates an object initialization function for each method sequence generated as explained in B-2-2 above. Specifically, the object initialization function generation unit 102 generates the following object initialization function for the above method sequence 1 (init→setLocation→calc→finalize):

In addition, the object initialization function generation unit 102 generates the following object initialization function for the above method sequence 2 (init→calc→finalize).

B-3. Generation of Symbol Execution Driver The symbol execution driver generation unit 103 generates code to be run on the symbol execution engine, i.e., a symbol execution driver, from the source code received as input, the type information generated by the type information generation unit 101 (see B-1 above), and the object initialization function generated by the object initialization function generation unit 102 (see B-2 above).

The symbolic execution driver is code that simply initializes and symbolizes variables to be passed to the function under test, and calls the function under test. When generating a symbolic execution driver, the symbolic execution driver generation unit 103 uses the type information generated by the type information generation unit 101 and the object initialization function generated by the object initialization function generation unit 102. If the function under test is a function that receives a void pointer as an argument, or is a function in a dynamically typed language, the symbolic execution driver generation unit 103 initializes variables with a type that may be passed to the function, based on the type information generated by the type information generation unit 101. If there is a possibility that multiple types may be passed, the symbolic execution driver generation unit 103 generates a symbolic execution driver separately for each type.

In the example of the add function shown in section B-1-2 above, type information indicating that variables of type int and type float may be passed to the function under test can be obtained from the type information generation unit 101. In this case, the symbol execution driver generation unit 103 generates a symbol execution driver for each of the int and float types separately. In other words, the symbol execution driver generation unit 103 generates a symbol execution driver such as the one below, which passes an int type as an argument.

The symbol execution driver generation unit 103 also generates a symbol execution driver like the one below, which passes a float type as an argument.

In addition, when an object is passed as an argument to the function to be tested, the symbolic execution driver generation unit 103 checks whether or not there is a function that can initialize the object among the object initialization functions generated by the object initialization function generation unit 102 as described above. If such a function exists, the symbolic execution driver generation unit 103 calls the function to initialize the object, and inserts code into the symbolic execution driver that initializes and symbolizes variables passed as arguments to the object initialization function.

In the case of the above SampleClass example, the symbol execution driver generation unit 103 generates, for example, the following code for the object initialization function of the above method sequence 1 (init → setLocation → calc → finalize). The symbol execution driver generation unit 103 inserts into the symbol execution driver code that initializes and symbolizes variables passed as arguments to the object initialization function.

B-4. Symbolic Execution and Test Code Generation The symbolic execution unit 104 executes the symbolic execution driver generated by the symbolic execution driver generation unit 103 on the symbolic execution engine to generate test cases. Then, the test code generation unit 105 generates test code for the function to be tested using the test cases generated by the symbolic execution unit 105 as input values.

At this time, if necessary, the test code generation unit 105 generates test code using the object initialization function generated by the object initialization function generation unit 102. In the case of the above SampleClass example, the test code generation unit 105 generates test code such as the following using the object initialization function generated by the object initialization function generation unit 102.

C. Test Code Generation Processing Procedure Fig. 2 shows, in the form of a flowchart, an example of a processing procedure for automatically generating test code from source code in the automatic test generation device 100 according to the present embodiment. The processing procedure for generating test code will be described below with reference to Fig. 2.

If the source code to be tested is written in a statically typed language and static analysis is to be performed on the source code to be tested (Yes in step S201), the type information generation unit 101 first performs static analysis to find out what type of variables are created in the function that calls the function to be tested and what types are passed as arguments to the function to be tested, thereby narrowing down the types of variables passed to a certain number of functions and collecting type information (step S202).

When performing dynamic analysis on the source code to be tested (Yes in step S203), such as when simple static analysis alone is not sufficient to accurately narrow down the types for all cases, or when the source code to be tested is written in a dynamically typed language, the type information generating unit 101 performs a first instrumentation on the program to be tested so that the types of variables to be passed to the functions to be tested are output as an execution trace immediately before calling each function to be tested (step S204).

The object initialization function unit 102 also performs a second instrumentation on the program under test to output, as an execution trace, which methods of an object were called and in what order from when the object was created until when it was deleted, so that a method sequence for initializing each object can be collected (step S205).

Next, inputs to the program are generated using test case generation techniques such as random generation, fuzzing, and symbolic execution (step S206). The generated inputs are then passed to the program instrumented in steps S204 and S205, and the program is executed to obtain an execution trace as an intermediate product. In practice, the execution trace is collected by generating test cases in steps S206 and S207 and executing the program to be tested with the generated test cases as input for a certain period of time.

The type information generation unit 101 obtains type information on the types of variables to be passed to the function under test from the execution trace (see, for example, Table 1) that describes the types of variables to be passed to the function under test (step S208).

The object initialization function generation unit 102 also collects a method sequence for initializing each object from an execution trace that records, in order, the type name of the called object, the object's identification information, and the called method name (step S209).

Furthermore, the object initialization function generation unit 102 generates a new method sequence using at least one of random generation, mutation, and use of a machine learning model (step S210). In step S210, among the newly generated method sequences, only those that can increase coverage more than the method sequence generated in step S209 may be kept, and the rest may be deleted.

Then, the object initialization function generation unit 102 generates an object initialization function for each method sequence obtained in the preceding steps S209 and S210 (step S211).

Then, the symbolic execution driver generation unit 103 generates a symbolic execution driver using the type information collected by the type information generation unit 101 through static and dynamic analysis of the source code (step S212). If there is a possibility that multiple types will be passed, the symbolic execution driver generation unit 103 generates a symbolic execution driver for each type separately. In addition, the symbolic execution driver generation unit 103 checks whether there is a function that can initialize the object among the object initialization functions generated by the object initialization function generation unit 102 as described above, and if such a function exists, it calls the function to initialize the object, and inserts code into the symbolic execution driver that initializes and symbolizes variables to be passed as arguments to the object initialization function.

Then, the symbol execution unit 104 executes the symbol execution driver generated by the symbol execution driver generation unit 103 on the symbol execution engine to generate test cases (step S213).

The test code generation unit 105 generates test code for the function to be tested using the test cases generated by the symbol execution unit 105 as input values (step S214), and outputs this to the downstream test execution device, thereby terminating this process.

D. Configuration of Information Processing Device In this section D, the hardware configuration of an information processing device that can operate as the automatic test generation device 100 will be described.

FIG. 3 shows an example of the hardware configuration of an information processing device 2000. This information processing device 2000 includes a CPU (Central Processing Unit) 2001, a ROM (Read Only Memory) 2002, a RAM (Random Access Memory) 2003, a host bus 2004, a bridge 2005, an expansion bus 2006, an interface unit 2007, an input unit 2008, an output unit 2009, a storage unit 2010, a drive 2011, and a communication unit 2013.

The CPU 2001 controls the overall operation of the information processing device 2000 in accordance with various programs. The ROM 2002 stores in a non-volatile manner the programs (basic input/output system, etc.) and computational parameters used by the CPU 2001. The RAM 2003 is used to load programs used in the execution of the CPU 2001, and to temporarily store parameters such as working data that change as appropriate during program execution. Programs loaded into the RAM 2003 and executed by the CPU 2001 include, for example, various application programs and an operating system (OS).

The CPU 2001, ROM 2002, and RAM 2003 are interconnected by a host bus 2004 that is composed of a CPU bus and the like. The CPU 2001 can execute various application programs in an execution environment provided by the OS through the cooperative operation of the ROM 2002 and RAM 2003, thereby realizing various functions and services. If the information processing device 2000 is a personal computer, the OS is, for example, Microsoft's Windows (registered trademark), Unix (registered trademark), or a successor OS to the OS. The application programs also include an automatic test code generation tool, a test support program that uses the generated test code to support program testing, and the like.

The host bus 2004 is connected to the expansion bus 2006 via the bridge 2005. The expansion bus 2006 is, for example, a PCI (Peripheral Component Interconnect) bus or PCI Express, and the bridge 2005 is based on the PCI standard. However, the information processing device 2000 does not need to be configured such that the circuit components are separated by the host bus 2004, the bridge 2005, and the expansion bus 2006, and may be implemented such that almost all circuit components are interconnected by a single bus (not shown).

The interface unit 2007 connects peripheral devices such as an input unit 2008, an output unit 2009, a storage unit 2010, a drive 2011, and a communication unit 2013 in accordance with the standard of the expansion bus 2006. However, not all of the peripheral devices shown in FIG. 3 are necessarily required, and the information processing device 2000 may further include peripheral devices not shown. Furthermore, the peripheral devices may be built into the main body of the information processing device 2000, or some of the peripheral devices may be externally connected to the main body of the information processing device 2000.

The input unit 2008 is composed of an input control circuit that generates an input signal based on an input from a user and outputs it to the CPU 2001. If the information processing device 2000 is a personal computer, the input unit 2008 may include a keyboard, a mouse, a touch panel, and may also include a camera and a microphone. The output unit 2009 includes display devices such as a liquid crystal display (LCD) device, an organic EL (Electro-Luminescence) display device, and an LED (Light Emitting Diode).

The storage unit 2010 stores files such as programs (applications, OS, etc.) executed by the CPU 2001 and various data. The storage unit 2010 is configured with a large-capacity storage device such as an SSD (Solid State Drive) or HDD (Hard Disk Drive), but may also include an external storage device.

The removable storage medium 2012 is a storage medium configured in a cartridge format, such as a microSD card. The drive 2011 performs read and write operations on the inserted removable storage medium 113. The drive 2011 outputs data read from the removable storage medium 2012 to the RAM 2003 or the storage unit 2010, and writes data on the RAM 2003 or the storage unit 2010 to the removable storage medium 2012.

The communication unit 2013 is a device that performs wireless communication such as Wi-Fi (registered trademark), Bluetooth (registered trademark), and cellular communication networks such as 4G and 5G. The communication unit 2013 may also have terminals such as a Universal Serial Bus (USB) and a High-Definition Multimedia Interface (HDMI (registered trademark)), and may further have a function of performing HDMI (registered trademark) communication with USB devices such as scanners and printers, displays, etc.

The information processing device 2000 can also operate as a test execution device that uses test code generated by the automatic test generation device 100 to test a test target program. Also, one information processing device 2000 can operate as both the automatic test generation device 100 and the test execution device. The information processing device 2000 is configured using, for example, a PC, and operates as the automatic test generation device 100 and the test execution device by executing a specific computer program.

The present disclosure has been described in detail above with reference to specific embodiments. However, the present disclosure should not be interpreted as being limited to the above-described embodiments, and it is self-evident that a person skilled in the art can modify or substitute the embodiments without departing from the gist of the present disclosure. Furthermore, the effects described in this specification are merely examples, and the effects brought about by the present disclosure are not limited, and there may be additional effects not described in this specification.

The present disclosure can be applied to an automatic test generation tool for programs whose source code is written in a variety of programming languages, including statically typed languages, dynamically typed languages, and object-oriented languages, to free users from burdensome and extremely cumbersome tasks such as interpreting the types of variables used in the source code and adding object initialization functions.

In short, this specification has described the present disclosure in the form of examples, and the contents of this specification should not be interpreted in a restrictive manner. The claims should be taken into consideration in determining the gist of this disclosure.

The series of processes described in this specification can be executed by hardware, software, or a combination of hardware and software. When executing processes by software, a program recording the processing sequence related to the realization of this disclosure is installed in memory within a computer built into dedicated hardware and executed. It is also possible to install a program in a general-purpose computer capable of executing various processes and execute the processes related to the realization of this disclosure.

The program can be stored in advance in a recording medium installed in the computer, such as a HDD, SSD, or ROM. Alternatively, the program can be temporarily or permanently stored in a removable recording medium, such as a flexible disk, a CD-ROM (Compact Disc Read Only Memory), an MO (Magneto optical) disk, a DVD (Digital Versatile Disc), a BD (Blu-Ray Disc (registered trademark)), a magnetic disk, or a USB (Universal Serial Bus) memory. Using such removable recording media, a program related to the realization of the present disclosure can be provided as so-called package software.

The program may also be transferred wirelessly or wired from a download site to a computer via a network such as a WAN (Wide Area Network) such as a cellular network, a LAN (Local Area Network), or the Internet. The computer can receive the program transferred in this way and install it on a large-capacity storage device such as an HDD or SSD within the computer.

In addition, this disclosure can also be configured as follows:

(1) an analysis unit that analyzes source code to collect type information of the source code and generate object initialization functions;
a symbolic execution driver generator that generates a symbolic execution driver using the type information and an object initialization function;
a symbolic execution unit that executes the symbolic execution driver generated by the symbolic execution driver generation unit to generate a test case;
a test code generation unit that generates a test code for applying the test cases generated by the symbol execution unit to a program under test and executing the program;
An information processing device comprising:

(2) The analysis unit performs a static analysis of a program to be tested in a statically typed language, and investigates the types of variables created by a function that calls the function to be tested and the functions that pass the variables, thereby narrowing down the types of arguments to be passed to the function to be tested.
The information processing device according to (1) above.

(3) The analysis unit instruments a program to be tested in a dynamically typed language so as to output, as an execution trace, the types of variables to be passed to the function to be tested immediately before calling the function to be tested, passes an input to the instrumented program, executes the program, and collects an execution trace; and analyzes type information and objects of the variables to be passed to the function to be tested from the collected execution trace.
The information processing device according to any one of (1) or (2) above.

(3-1) the analysis unit generates inputs to the program under test using at least one of random generation, fuzzing, and symbolic execution;
The information processing device according to (3) above.

(3-2) When using at least one of fuzzing and symbolic execution, the analysis unit uses a technique for efficiently searching to reach a specific line of a program to find an input that executes a function under test and obtains an execution trace.
The information processing device according to (3-1) above.

(4) The analysis unit performs instrumentation to output, as an execution trace, methods that are called from when an object is created until it is deleted and the order in which the methods are called, so that a method sequence for initializing each object can be collected, and generates an object initialization function by analyzing the execution trace.
The information processing device according to any one of (1) to (3) above.

(4-1) The analysis unit instruments a test target program in an object-oriented language so as to output an object type name, object identification information, and the called method name as an execution trace immediately before invoking a method, passes an input to the instrumented program, executes the program, and collects an execution trace, extracts a method sequence for initializing the object from the collected execution trace, and generates an object initialization function from the extracted method sequence.
The information processing device according to (4) above.

(4-2) The analysis unit extracts, from the execution trace, a method sequence indicating what methods were called and in what order for the object to be passed to the function under test from the time the object was generated until the function under test was called;
The information processing device according to (4) above.

(5) generating inputs for the instrumented program using at least one of the following techniques: random generation, fuzzing, and symbolic execution;
The information processing device according to any one of (3) and (4) above.

(6) The analysis unit further generates a new method sequence and adds the new method sequence to the method sequence extracted from the execution trace, thereby generating an object initialization function.
The information processing device according to (4) above.

(6-1) The analysis unit executes the test driver generated using the new method sequence to measure coverage, and keeps only the method sequence that covers lines that cannot be reached by the existing method sequence, and deletes the method sequence that does not cover the lines.
The information processing device according to (6) above.

(7) The analysis unit randomly generates a new method sequence from among public methods of an object to be passed to a function under test.
The information processing device according to (6) above.

(8) The analysis unit modifies a part of the method sequence extracted from the execution trace to generate a new method sequence.
The information processing device according to (6) above.

(9) The analysis unit modifies the method sequence extracted from the execution trace by adding a part of methods randomly selected from public methods of the object.
The information processing device according to (8) above.

(10) The analysis unit modifies the method sequence extracted from the execution trace by deleting some of the methods selected at random.
The information processing device according to (8) above.

(11) The analysis unit replaces a randomly selected part of methods with another public method to modify the method sequence extracted from the execution trace.
The information processing device according to (8) above.

(12) The analysis unit generates a sequence of methods that need to be executed before calling the function to be tested by using machine learning that learns, from the execution trace, which method of an object to be passed to the function to be tested is to be called.
The information processing device according to (6) above.

(13) The analysis unit measures coverage by performing fuzzing or symbolic execution on the test driver generated using the new method sequence created by adding the changes, and leaves only the method sequence that covers lines that cannot be reached by the existing method sequence.
The information processing device according to any one of (8) to (12) above.

(14) The symbolic execution driver generation unit initializes and symbolizes variables to be passed to the function under test, and generates a symbolic execution driver consisting of a code for simply calling the function under test.
14. The information processing device according to claim 13,

(15) In the case of a function that receives a void pointer as an argument and a function of a dynamically typed language, the symbolic execution driver generation unit initializes and symbolizes variables with a type that may be passed to the function to be tested based on the collected type information, thereby generating a symbolic execution driver.
The information processing device according to (14) above.

(16) When an object is passed as an argument of a function to be tested, the symbol execution driver generation unit initializes the object by calling a function capable of initializing the object in the generated object initialization function, and inserts a code for initializing and symbolizing a variable to be passed as an argument of the object initialization function into the symbol execution driver.
The information processing device according to (14) above.

(17) The test code generation unit generates a test code for a function to be tested by executing the symbol execution driver generated by the symbol execution driver generation unit on a symbol execution engine and using the test case generated as an input value.
17. The information processing device according to claim 15, wherein the information processing device is a

(17-1) The test code generation unit generates test code using the object initialization function generated by the analysis unit, as necessary.
The information processing device according to (17) above.

(18) an analysis step of analyzing the source code to generate type information and an object initialization function for the source code;
a symbolic execution driver generation step of generating a symbolic execution driver using the type information and an object initialization function;
a symbolic execution step of executing the symbolic execution driver generated in the symbolic execution driver generation step to generate a test case;
a test code generation step of generating test code for applying the test cases generated in the symbol execution step to a program under test and executing the program;
An information processing method comprising the steps of:

(19) an analysis unit that analyzes source code and generates type information and an object initialization function for the source code;
a symbolic execution driver generator that generates a symbolic execution driver using the type information and an object initialization function;
a symbolic execution unit that executes the symbolic execution driver generated by the symbolic execution driver generation unit to generate test cases;
a test code generation unit that generates a test code for applying the test cases generated by the symbol execution unit to a program to be tested and executing the program;
A computer program written in a computer-readable form to cause a computer to function as a

100: Automatic test generation device, 101: Type information generation unit, 102: Object initialization function generation unit, 103: Symbol execution driver generation unit, 104: Symbol execution unit, 105: Test code generation unit, 2000: Information processing device, 2001: CPU, 2002: ROM
2003: RAM, 2004: host bus, 2005: bridge, 2006: expansion bus, 2007: interface section, 2008: input section, 2009: output section, 2010: storage section, 2011: drive, 2012: removable recording medium, 2013: communication section

Claims (19)

an analysis unit that analyzes source code to collect type information of the source code and generate object initialization functions;
a symbolic execution driver generator that generates a symbolic execution driver using the type information and an object initialization function;
a symbolic execution unit that executes the symbolic execution driver generated by the symbolic execution driver generation unit to generate a test case;
a test code generation unit that generates a test code for applying the test cases generated by the symbol execution unit to a program under test and executing the program;
An information processing device comprising: The analysis unit performs a static analysis on a program to be tested in a statically typed language, and investigates the types of variables created by a function calling the function to be tested and the functions to be passed to the function, thereby narrowing down the types of arguments to be passed to the function to be tested.
The information processing device according to claim 1 . The analysis unit instruments the program under test so as to output, as an execution trace, the types of variables to be passed to the function under test immediately before calling the function under test, passes an input to the instrumented program, executes the program, and collects the execution trace, and analyzes type information and objects of the variables passed to the function under test from the collected execution trace.
The information processing device according to claim 1 . the analysis unit performs instrumentation so as to output, as an execution trace, methods that have been called from the time an object is created until the time it is deleted and the order in which the methods have been called, so that a method sequence for initializing each object can be collected, and generates an object initialization function by analyzing the execution trace;
The information processing device according to claim 1 . generating inputs for the instrumented program using at least one of the following techniques: random generation, fuzzing, and symbolic execution;
The information processing device according to claim 3 . the analysis unit further generates a new method sequence and adds the new method sequence to the method sequence extracted from the execution trace, thereby generating an object initialization function.
The information processing device according to claim 4. The analysis unit randomly generates a new method sequence from among public methods of an object to be passed to a function under test.
The information processing device according to claim 6. the analysis unit modifies a part of the method sequence extracted from the execution trace to generate a new method sequence.
The information processing device according to claim 6. the analysis unit adds some methods randomly selected from public methods of the object to modify the method sequence extracted from the execution trace;
The information processing device according to claim 8. the analysis unit deletes some of the methods selected at random to modify the method sequence extracted from the execution trace;
The information processing device according to claim 8. the analysis unit replaces a randomly selected portion of the methods with another public method to modify the method sequence extracted from the execution trace;
The information processing device according to claim 8. The analysis unit generates a sequence of methods that need to be executed before calling the function to be tested, using machine learning that has learned from the execution trace which method of the object to be passed to the function to be tested will be called.
The information processing device according to claim 6. The analysis unit measures coverage by performing fuzzing or symbolic execution on the test driver generated using the new method sequence created by making the above changes, and leaves only the method sequence that covers lines that cannot be reached by the existing method sequence.
The information processing device according to claim 8. the symbolic execution driver generation unit initializes and symbolizes variables to be passed to the function under test, and generates a symbolic execution driver consisting of a code that only calls the function under test;
The information processing device according to claim 1 . the symbolic execution driver generation unit generates a symbolic execution driver by initializing and symbolizing variables with types that may be passed to the function under test based on the collected type information;
The information processing device according to claim 14. When an object is passed as an argument of a function to be tested, the symbol execution driver generation unit initializes the object by calling a function capable of initializing the object in the generated object initialization function, and inserts a code for initializing and symbolizing a variable to be passed as an argument of the object initialization function into the symbol execution driver.
The information processing device according to claim 14. the test code generation unit executes the symbol execution driver generated by the symbol execution driver generation unit on a symbol execution engine, and generates a test code for the function to be tested using the test case as an input value.
The information processing device according to claim 1 . an analysis step of analyzing the source code to generate type information and object initialization functions for the source code;
a symbolic execution driver generation step of generating a symbolic execution driver using the type information and an object initialization function;
a symbolic execution step of executing the symbolic execution driver generated in the symbolic execution driver generation step to generate a test case;
a test code generation step of generating test code for applying the test cases generated in the symbol execution step to a program under test and executing the program;
An information processing method comprising the steps of: an analysis unit that analyzes the source code and generates type information and object initialization functions for the source code;
a symbolic execution driver generator that generates a symbolic execution driver using the type information and an object initialization function;
a symbolic execution unit that executes the symbolic execution driver generated by the symbolic execution driver generation unit to generate test cases;
a test code generation unit that generates a test code for applying the test cases generated by the symbol execution unit to a program to be tested and executing the program;
A computer program written in a computer-readable form to cause a computer to function as a