CN108399127B - Class integration test sequence generation method - Google Patents

Abstract

The invention provides a generation method of a class integration test sequence, which comprises the following steps: 1) acquiring all classes and the relations between the classes from a source code of an object-oriented system; 2) obtaining a class priority table from a class diagram in a UML design document for an object-oriented system; 3) and automatically generating the class integration test sequence through a genetic algorithm. And repeating the process to finally obtain a group of optimal (the test cost for constructing the test pile is minimum) class test sequence results. The invention solves the problems that the initial population has no constraint condition in the class integration test sequence problem, the overall quality of the initial population is poor, the convergence speed and the optimization result are influenced, and the optimization effect is not accurate due to the one-sidedness and the irrationality of the individual evaluation standard to a certain extent. The method not only improves the overall quality of the population and accelerates the convergence speed, but also strengthens the optimizing capability of the genetic algorithm, improves the optimizing accuracy, further improves the testing efficiency and precision, and can better meet the actual needs.

Description

A kind of integration test sequence generation method

technical field

The invention belongs to the technical field of software testing, and particularly relates to a method for generating a test-like sequence in the problem of generating a test-like sequence in an integration test.

Background technique

Object-oriented programs do not have an obvious hierarchical module structure like process-oriented programs. The connection between objects is through message passing. A message will cause a chain reaction and form a method call chain. The static structure that reflects the call relationship is a complex network structure. Therefore, where to start testing and how to determine an integration test sequence are questions for further study. The test sequence of classes is related to the time and cost of software defect discovery. Therefore, it is an important research problem to determine the integration test sequence of classes.

The existing work mainly measures the pros and cons of a class integration test sequence by the size of the test pile cost. Generating a class test sequence requires breaking some inter-class dependencies until there are no loops. The process of breaking dependencies between classes means building test stubs, at a cost. Therefore, while eliminating all the loops of inter-class dependencies, the less expensive it is to build test stubs, the better. However, it is usually impossible to directly measure or estimate the cost of test piles, and certain indicators are required. At present, the indicators for evaluating the cost of test piles are mainly from two aspects: the overall complexity of the test piles constructed during the generation process of the integration test test sequence or the number of the test piles constructed.

The generation problem of class integration test sequence is essentially an optimization problem, and it is also an NP-complete (hard) problem. The existing solutions include graph theory-based methods and search-based methods. Among them, the method based on graph theory cannot be applied to large-scale programs due to its own limitations, and can only be used for small-scale programs. Existing search-based methods include methods based on genetic algorithm, methods based on simulated annealing algorithm, methods based on particle swarm optimization, methods based on ant colony algorithm and NSGA-II. The generation of optimal class ensemble test sequences requires multiple transformations, and "simulated annealing algorithms can arbitrarily approximate a stationary distribution only if the number of transformations is at least the square of the size of the solution space". For the generation of class integration test sequences, the size of the solution space is the factorial of the number of classes, so the scale of the number of transformations is approximately the exponential of the number of classes. If an arbitrary approximation method is used to generate the optimal class integration test sequence that converges to the global, the execution time of the simulated annealing algorithm will increase exponentially. For a system under test with a large number of classes, the running time is unbearable, making the algorithm infeasible. In the NP problem, it can converge in a finite time to get an ideal solution. For example, when the number of classes is too large, the formed class sequence grows exponentially, which greatly increases the scale of the solution space. When using the particle swarm optimization algorithm to solve, it is easy to fall into the local optimal solution. The use of ant colony algorithm cannot guarantee to find the optimal solution of the problem, but can only guarantee to find the better or acceptable solution of the problem. Genetic algorithm has better robustness and can converge to obtain ideal solution in finite time in NP problems. The selection of the fitness function directly affects the convergence speed of the genetic algorithm and whether it can find the optimal solution. Existing schemes often use the overall complexity of the test pile as a fitness function to evaluate the quality of an individual (class integration test sequence). However, simply taking the overall complexity of the constructed test piles or the number of test piles as the fitness function is one-sided and inaccurate, resulting in poor optimization results and restricting the generation of optimal solutions to a certain extent. Some test-like sequence generation methods that use the overall complexity of the test pile as the fitness function cannot meet the actual needs, but should comprehensively consider the overall complexity of the built test pile and the number of test piles. Therefore, it is necessary to design Reasonable fitness function to evaluate the pros and cons of class integration test sequences.

SUMMARY OF THE INVENTION

Aiming at the characteristics of large scale of object-oriented program classes and complex relationships between classes, and the difficulty of determining the class integration test sequence, and overcoming the problem of poor optimization effect in the prior art, the present invention provides a class integration test based on genetic algorithm The sequence generation method utilizes the evolutionary characteristics of the population in the genetic algorithm to generate the optimal solution one by one, and solves the problem of generating class test sequences in the integration testing of object-oriented programs.

The present invention is realized according to the following technical solutions:

A kind of integration test sequence generation method, including:

A data collection module for obtaining class and inter-class relationship information, and obtaining a class priority table; and

The class integration test sequence generation module is implemented as follows:

Step A, read all classes and inter-class relationship information in the data collection module;

Step B, read the class priority table in the described data collection module,

Step C. Automatically generate a class integration test sequence through a genetic algorithm.

Preferably, the specific implementation process of the step C is:

Step 1: Encode the class;

Step 2: Randomly generate an initial population P whose size is 2-3 times the number of classes under the constraints of the priority information given by the class priority table;

Step 3: Construct a fitness function to evaluate the pros and cons of individuals;

Step 4: Calculate the fitness value of each individual in the population P, and use the weighted average of the overall complexity of the test piles and the total number of test piles as the individual evaluation criteria;

Step 5: According to the fitness value of each individual, assign different selection probabilities Ps to the individual, and select 2-3 times the number of classes from the initial population P by roulette to generate a new population P' ;

Step 6: According to the input crossover probability Pc, make the parent individuals in the population P' to cross each other in pairs, carry out the legality test of the crossed individuals, retain the legal individuals, and discard the illegal individuals;

Step 7: According to the input mutation probability Pm, rearrange the gene segment of the parent individual, and perform the legitimacy test of the generated new individual;

Step 8: Repeat steps 4 to 7 for several times, and the final result of the class test sequence is the optimal solution, and the optimal test sequence minimizes the testing cost of constructing the test pile.

Preferably, in step 3, when constructing the fitness function for evaluating the strengths and weaknesses of the individual, two indicators, the overall complexity of constructing the test piles and the number of the constructed test piles, are comprehensively considered;

The calculation of the overall complexity of the test pile needs to rely on the complexity of all the single test piles constructed, and when measuring the complexity of a single test pile, the objective entropy weight method is used to determine the attribute complexity used. and weights of method complexity.

Preferably, in step 3, the fitness function representation method is as follows:

Among them, Fitness represents the fitness function, and the right side of the equation represents the weighted average of the overall complexity of the test piles and the total number of test piles; OCplx and NStub are the overall complexity of the test piles and the test piles spent to generate a class integration test sequence, respectively. The total number of ; W _OCplx and W _NStub are the weights of the overall complexity of the test piles and the total number of test piles, respectively, the value is between [0, 1], and satisfies W _OCplx + W _NStub =1.

Preferably, in step five,

Among them, Fi represents the fitness value of the ith individual, and N represents the number of individuals in the population.

Preferably, in the sixth step, the crossover probability Pc is 0.5.

Preferably, in the seventh step, the mutation probability Pm is taken as 1/G;

Among them, G is the number of genes in an individual, that is, the number of classes.

Preferably, the data collection module obtains the class and the relationship information between classes and is specifically implemented as follows:

Obtain all class information, triples describing inter-class relationships, and inter-class coupling information from the source code of an object-oriented system.

Preferably, all class information, triples describing relationships between classes, and coupling information between classes are obtained from the source code of the program to be tested through the open source analysis tool SOOT; all class information, triples describing relationships between classes are obtained from the source code of the program under test; The group and inter-class coupling information is stored in the class information file and the triple information file of the inter-class relationship, respectively.

Preferably, the specific implementation of the data collection module for obtaining the class priority table is as follows:

Obtain the class priority table from the class diagram in the UML design document of the object-oriented system.

Beneficial effects of the present invention:

(1) The generation problem of class integration test sequence is an NP problem, and the current methods are mainly based on graph theory and search-based methods. Among them, the method based on graph theory cannot be applied to large-scale programs due to its own limitations, and can only solve the problem of generating integration test sequences for small-scale programs. Existing search-based methods are slow to converge to the optimal solution, and are still far from practical applications. Through the generation technology of class integration test sequence based on genetic algorithm, the invention utilizes coding in genetic algorithm, generation of initial population, design of fitness function, individual evaluation, selection, crossover, mutation, etc. to continuously evolve the population, and gradually generate the optimal solution , to solve the class integration test sequence generation problem.

(2) The present invention combines relevant parameter configuration, uses genetic algorithm to sort the classes of the system to be tested, and provides a scientific solution for testers to perform integrated testing of the system. The generation technology of the class integration test sequence based on the genetic algorithm provided by the invention considers the priority information of the class when generating the initial population, and generates the initial population under the constraint of the class priority, which overcomes the previous initial population without any constraints. , the individual fitness value is low, and the overall quality is poor, which affects the convergence speed and optimization results. It not only loses randomness, but also improves the overall quality of the population and strengthens the optimization ability of the genetic algorithm.

(3) The present invention comprehensively considers the overall complexity of the constructed test piles and the number of constructed test piles, and uses these two indicators as the evaluation criteria of individual strengths and weaknesses, which not only breaks the prior art that does not allow deletion, inheritance, aggregation, etc. The limitation of strong dependencies also overcomes the previous use of the overall complexity of the constructed test piles or the number of constructed test piles as the individual evaluation criteria, resulting in an inaccurate optimization effect, which restricts the generation of the optimal solution to a certain extent. The problem is more reasonable and can better meet the actual needs.

Description of drawings

Fig. 1 is the structure diagram of the present invention;

Fig. 2 is the flow chart of obtaining class and its related information in the data collection module in Fig. 1;

Fig. 3 is the flow chart of obtaining the class priority table in the data collection module in Fig. 1;

FIG. 4 is a flow chart of the realization of the class integration test sequence generation module using the genetic algorithm in FIG. 1 .

Detailed ways

The present invention will be further described below through specific embodiments in conjunction with the accompanying drawings.

As shown in Figure 1, the present invention includes two parts: a data collection module and a class integration test sequence generation module using a genetic algorithm, wherein:

Data collection module: used to obtain class and inter-class relationship information, and class priority table. This module serves as the input information of the class integration test sequence generation module, provides basic information and priority information for the class integration test sequence generation module, and serves as the constraint information for generating the initial population in the class integration test sequence generation module.

Class integration test sequence generation module: Read all classes, inter-class relationships, inter-class coupling information and priority information in the data collection module. Input the parameters N, I, Pc, Pm set when generating the test sequence, N represents the population size, I represents the number of iterations, Pc represents the crossover probability, Pm represents the mutation probability, call the genetic algorithm, and the output result is the optimal class Integration test sequence.

As shown in Figure 2, the specific implementation of the data collection module (acquiring classes and their related information) in the present invention is as follows: obtain all class information, triples describing the relationship between classes, and coupling information between classes from the source code of the object-oriented system (including property complexity and method complexity).

As shown in FIG. 3 , the specific implementation of the data collection module (obtaining the class priority table) in the present invention is as follows: the class priority table is obtained from the class diagram in the UML design document of the object-oriented system.

As shown in Figure 4, the concrete realization of the class integration test sequence generation module using genetic algorithm in the present invention is as follows:

1) Read all classes and inter-class relationship information in the data collection module;

2) read the class priority table in the data collection module,

3) Automatically generate class integration test sequence through genetic algorithm, including eight steps, including encoding, generating initial population, constructing fitness function, evaluating individual, selecting operation, crossover operation and mutation operation, as shown in Figure 4.

The specific implementation process of the class integration test sequence generation module is as follows:

Step 1: Encode the class: a set of classes represented by labels represents an individual, such as a class cluster {A, B, C}, a possible individual is (B, C, A) sequence, and a possible population is {(B C A),(B A C),…};

Step 2: Input the parameters N, I, Pc, Pm set when generating the test sequence, read the class information and its priority information in the data collection module, and generate a scale of N under the constraint of class priority (N is the class 2-3 times the number) of the initial population P (a set of class test sequences);

Step 3: Construct a fitness function, which is used to evaluate the pros and cons of individuals. The construction method is as follows:

An individual represents a class integration test sequence, and the fitness function representation method is shown in formula (1). Among them, Fitness represents the fitness function, and the right side of the equation represents the weighted average of the overall complexity of the test piles and the total number of test piles.

Among them, OCplx and NStub are the overall complexity of the test piles and the total number of test piles to generate a class integration test sequence respectively; W _OCplx and W _NStub are the weight of the overall complexity of the test piles and the total number of test piles, respectively, take The value is between [0, 1] and satisfies W _OCplx +W _NStub =1, the present invention takes W _OCplx =W _NStub =0.5.

表示生成一个类集成测试序列o所花费的测试桩的总体复杂度OCplx(o)的标准化形式，满足公式(2)：in formula (1)

Represents the normalized form of the overall complexity OCplx(o) of the test stubs spent to generate a class integration test sequence o, which satisfies Equation (2):

where OCplx _min =Min{OCplx(ok ), _k =1,2,...} and OCplx _max =Max{OCplx(ok ), _k =1,2,...}, k is the class test the number of sequences.

Among them, the calculation method of the overall complexity OCplx() of the test piles spent to generate a test sequence is as formula (3):

Among them, t represents the number of relationships between classes, and the test pile complexity SCplx(i,j) represents the degree of coupling between two classes i, j with dependencies, that is, the complexity of a single test pile, which can be calculated by standardized Weighted geometric mean calculation, such as formula (4):

Among them, A(i,j) and M(i,j) are the attribute complexity and method complexity obtained in the data collection module respectively; W _A and W _M are the weights of the attribute complexity and method complexity, respectively, take The value is between [0,1] and W _A + W _M =1.

In order to be more objective, the present invention adopts the entropy weight method to determine the specific values of W _A and W _M. details as follows:

Assuming that there are m inter-class relationships (the value of m is determined according to the system to be tested) and n evaluation indicators, the present invention has two evaluation indicators, namely attribute complexity A(i,j) and method complexity M(i ,j), then n=2; construct a standard matrix R=(r _xy ) _m*n , as shown in formula (5):

Among them, m represents the number of inter-class relationships in the system to be tested, r _xy represents the evaluation value of the x-th inter-class relationship under the y-th index, here, y=1, 2, when y=1, r _x1 represents the influence of the attribute complexity of the x-th inter-class relationship; when y=2, r _x2 represents the influence of the method complexity of the x-th inter-class relationship, 1≤x≤m;

Then, calculate the proportion p _xy of the index value of the x-th inter-class relationship under the y-th (y=1,2) index:

The information entropy e _j of the y-th index is shown in formula (7).

Finally, the weight of the y-th indicator is calculated, as shown in formula (8):

Wherein, when y=1, w1 represents the weight W _A of the attribute complexity index, and when y=2, w2 represents the weight W _M of the method complexity index.

表示生成一个类集成测试序列o所花费的测试桩的总个数NStub的标准化形式，表示为公式(9)：in formula (1)

Represents the normalized form of the total number of test piles NStub spent to generate a class integration test sequence o, expressed as formula (9):

Among them, NStub _min =Min{NStub(o _k ),k=1,2,...} and NStub _max =Max{NStub(o _k ),k=1,2,...}, k is the class test the number of sequences.

Step 4: Calculate the fitness value of each individual in the population P, take the fitness function constructed in step 3 as the evaluation standard, that is, take the weighted average of the overall complexity of the test piles and the total number of test piles as the individual fitness the calculation method of the value;

Step 5: According to the fitness value of each individual, assign different selection probability Ps to the individual (the calculation method is shown in the following formula, where Fi represents the fitness value of the ith individual, and N represents the number of individuals in the population), using The roulette method selects individuals with 2-3 times the number of classes from the initial population P to generate a new population P';

Step 6: According to the input crossover probability Pc (take 0.5), the parent individuals in the population P' are crossed in pairs, and the legality of the crossed individuals is checked, the legal individuals are retained, and the illegal individuals are discarded;

Step 7: According to the input mutation probability Pm (take 1/G, G is the number of genes in an individual, that is, the number of classes), rearrange the gene segments of the parent individual, and verify the legitimacy of generating a new individual test;

Step 8: Repeat steps 4 to 7 for 100 times, and the obtained quasi-integration test sequence is the optimal solution.

The following provides that the class integration test sequence generation method of the present invention is applied to a specific example:

We conducted experiments on three systems: JBoss, JHotDraw and MyBatis. The details of these three systems are shown in Table 1.

Table 1 Information of experimental subjects

a http://www.jboss.org/jbossas/downloads.html–subsystem used:management of JBoss(version 6.0.0M5):is a Java application server;

b http://sourceforge.net/projects/jhotdraw/–package used:org.jhotdraw.draw of JHotDraw(version 7.5.1):framework for the creation ofdrawing editors;

c http://code.google.com/p/mybatis/downloads/list:data mapperframework that makes easier the use a relational database with OOapplication;

The above three URLs give the sources of three systems: JBoss, JHotDraw and MyBatis.

The operating system used in the experiment is Windows 8, the CPU is Core i5 dual-core (2.6GHz), and the physical memory is 4G. The running time required to generate the class test sequence is shown in Table 2. Compared with the generation method of the class integration test sequence which takes the overall complexity of the test pile as the fitness, the present invention can find the optimal class integration test sequence faster under the same population number.

Table 2 Run time (ms)

Compared to the existing technology:

The invention solves the problem that the initial population does not have any constraint conditions in the class integration test sequence problem to a certain extent, and the overall quality of the initial population is poor, which further affects the convergence speed and the optimization result, and the one-sidedness and irrationality of individual evaluation standards. The optimization effect is not accurate enough. It not only improves the overall quality of the population and accelerates the convergence speed, but also strengthens the optimization ability of the genetic algorithm, improves the accuracy of optimization, and further improves the test efficiency and accuracy, and can better meet the actual needs.

The above are only the preferred embodiments of the present invention, it should be pointed out: for those of ordinary skill in the art, under the premise of not departing from the principles of the present invention, several improvements and modifications can also be made, and these improvements and modifications should also be regarded as It is the protection scope of the present invention.

Claims (9)

1. A class integration test sequence generation method is characterized by comprising the following steps:

the data collection module is used for acquiring the information of the classes and the relationship between the classes and acquiring a class priority table; and

the class integration test sequence generation module is realized as follows:

a, reading all classes and relationship information among the classes in the data collection module;

b, reading a class priority table in the data collection module;

step C, automatically generating a class integration test sequence through a genetic algorithm;

the step C is realized by the following specific steps:

the method comprises the following steps: encoding the class;

step two: randomly generating initial population P with the quantity 2-3 times of the number of the classes under the constraint of the priority information given by the class priority table;

step three: constructing a fitness function for evaluating the quality of the individual;

step four: calculating the fitness value of each individual in the population P, and taking the weighted average of the overall complexity of the test piles and the total number of the test piles as an individual evaluation standard;

step five: endowing different selection probabilities Ps to the individuals according to the fitness value of each individual, and selecting 2-3 times of individuals from the initial population P in a roulette mode to generate a new population P';

step six: according to the input crossover probability Pc, enabling the parent individuals in the population P' to carry out pairwise crossover, carrying out validity check on the crossed individuals, retaining the legal individuals, and discarding the illegal individuals;

step seven: carrying out gene segment rearrangement on parent individuals according to the input mutation probability Pm, and carrying out validity check on the generated new individuals;

step eight: and repeating the fourth step to the seventh step for multiple times, wherein the finally obtained class test sequence result is the optimal solution, and the optimal test sequence enables the test cost for constructing the test pile to be minimum.

2. The class integration test sequence generation method of claim 1, wherein in step three, when constructing a fitness function for evaluating the quality of an individual, two indexes of the total complexity spent on constructing test piles and the number of constructed test piles are considered comprehensively;

the calculation of the overall complexity of the test pile needs to be based on the complexity of all constructed single test piles, and when the complexity of the single test pile is measured, an objective entropy weight method is adopted to determine the weight of the attribute complexity and the method complexity.

3. The method for generating class integration test sequences according to claim 1, wherein in step three, the fitness function is expressed as follows:

wherein, Fitness represents a Fitness function, and the right side of the equation represents the weighted average of the total complexity of the test piles and the total number of the test piles; OCplx and NStub are the total complexity of the test piles and the total number of the test piles spent on generating a class integration test sequence, respectively; w_OCplxAnd W_NStubThe weights of the total complexity of the test piles and the total number of the test piles are respectively taken as values of [0, 1%]And satisfy W_OCplx+W_NStub＝1。

4. The class integration test sequence generation method of claim 1, wherein in step five,

wherein, Fi represents the fitness value of the ith individual, and N represents the number of individuals in the population.

5. The class integration test sequence generation method of claim 1, wherein: in the sixth step, the cross probability Pc is 0.5.

6. The class integration test sequence generation method of claim 1, wherein: in the seventh step, the variation probability Pm is 1/G;

wherein G is the number of genes, i.e., the number of classes, in an individual.

7. The method for generating a class integration test sequence according to claim 1, wherein the data collection module obtains the class and the relationship information between the classes as follows:

all class information, triples describing the relationships between classes, and inter-class coupling information are obtained from the source code of the object-oriented system.

8. The class integration test sequence generation method of claim 7, wherein: all the class information, the triples describing the inter-class relationship and the inter-class coupling information are acquired from the source code of the program to be tested through an open source code analysis tool SOOT;

all the class information, the triple for describing the relationship between the classes and the coupling information between the classes are respectively stored in the class information file and the triple information file for describing the relationship between the classes.

9. The method of claim 1, wherein the data collection module obtains the class priority table by implementing the following steps:

the class priority table is obtained from class diagrams in a UML design document for an object-oriented system.

Images