CN112732577A

CN112732577A - Evolution generation method for multi-task software test case

Info

Publication number: CN112732577A
Application number: CN202110028394.1A
Authority: CN
Inventors: 党向盈; 巩敦卫; 姚香娟; 鲍蓉; 姜代红; 阮少伟; 陈磊; 厉丹; 李子龙; 包季楠; 袁偲朕
Original assignee: Xuzhou University of Technology
Current assignee: Xuzhou University of Technology
Priority date: 2020-08-03
Filing date: 2021-01-14
Publication date: 2021-04-30
Also published as: CN112699050A; CN112699054A; CN112699053B; CN112699054B; CN112699052A; CN112699053A; CN112699052B; CN112732583A; CN112699045A; CN112732582A; CN112699051A; CN112699051B; CN112732583B

Abstract

The invention discloses an evolution generation method of a multi-task software test case, which aims to convert a variation test problem into a traditional coverage path test problem according to the performability of a variation branch and a program path and efficiently generate the test case with defect detection capability by adopting a multi-task parallel mode. Firstly, statically analyzing the execution correlation between the variation branches and the program paths, and dividing the variation branches with the same execution paths into the same group; then, establishing a multi-task optimization model for the multiple groups of variation branches based on the variation test cases covered by the paths; and finally, solving the model by using a multi-population genetic algorithm, and efficiently generating a test case with defect detection capability by adopting a multi-task parallel mode. The invention groups the variant branches according to the paths, adopts the traditional mature path testing method, is beneficial to improving the software testing efficiency, and generates the test case with high defect detection capability.

Description

Evolution generation method for multi-task software test case

Technical Field

The invention relates to the field of computer software testing, in particular to a method for evolutionary generation of a multi-task software test case.

Background

Software testing refers to detecting defects of certain software or software systems by manual or automatic methods. Variant testing is a powerful but expensive testing technique, especially with respect to test data acquisition that kills large numbers of variants. The variant branch is composed of the original sentence and its variant sentences. The true branch of the variant branch is overwritten by a test datum indicating that the corresponding variant was killed under the weak variant test criterion.

A tested program generally generates a plurality of variants, and a plurality of test cases are also needed for killing the variants; moreover, these test cases require the original program and the variant to be executed simultaneously, and thus the efficiency of the variant test is usually low. In order to overcome the above-mentioned drawbacks, Papadakis et al propose a new Software testing method in the article "automatic testing and testing of systematic execution, systematic testing and search-based testing" published in 2011 "Software Quality Journal" 19. The problem that they kill variants based on weak variant test criteria translates into the problem of coverage of true branches of variant conditional sentences. For this reason, for the statements s and s' before and after mutation, the mutation conditional statement "if s!is constructed based on the necessary conditions for the weak mutation test! The true branch is a mark sentence, which is called a variant branch for short; then, these variant branches are inserted in front of the pre-variant statement s of the original program, so that a new tested program is formed. Then, the test case of the variant branch of the new program can be covered, and the variant corresponding to the variant branch can be killed based on the weak variant test criterion. The advantage of this is that the variant test case can be generated by using the existing test case generation method of the traditional structure test.

The variant branch is mutated according to the original sentence, and for the variant branch inserted into the path to which the original sentence belongs, whether the new path after the alteration can be executed or not needs to be analyzed, the variant branch and the subsequent node of the original sentence in the path need to be analyzed, and the execution relationship is difficult to obtain directly and needs to be obtained through static analysis. If the variant branch can be determined to be merged into a certain path, the path is still executable, so that the problem of generating the killed variant can be converted into the problem of generating the test case covering the path. If a plurality of variant branches can be merged into the path, the variant branches can be solved and killed on the basis of the grouping of the execution paths, and can be converted into a multi-path test generation problem to establish a multi-task optimization model. And finally, solving by adopting a plurality of group genetic algorithms.

The multi-population genetic algorithm is a high-performance genetic algorithm, which divides a population into a plurality of sub-populations, and each sub-population is responsible for optimizing a target, so that an optimal solution can be found in a parallel mode.

Disclosure of Invention

The invention provides a multitask software test case evolution generation method for solving the problem that the generation efficiency of test cases for detecting numerous software defects in the prior art is low.

The technical scheme adopted by the invention is as follows: a multitask software test case evolution generation method comprises the following steps:

s1: grouping variant branches based on the correlation of the execution of the paths, namely, statically analyzing the execution correlation of the variant branches and the program paths, and dividing the variant branches with the same execution paths into the same group, specifically:

let the tested program be G, and the executable path set of G be P ═ P₁,P₂…, record the path

Wherein s is_iIs P_iA certain statement on, s_i+1Is s is_iThe successor statement of (1); to s_iFruit of Chinese wolfberryMutation is performed to obtain a mutation branch M_j，M_jIs denoted as M_j(1)；

S1.1: determination of M by static analysis_j(1) And s_i+1The execution relationship of (1); if M is_j(1) Execution, s_i+1Can also be performed, then at P_iTo be M_j,M_j(1) Insertion of s_iGet a path

Can judge P_i' is also an executable path;

s1.2: if M is_j(1) Execution, s_i+1Must not execute, then find path P in P_j，P_jComprises s_iAnd s is_iS is followed by_j≠s_i+1. Then, M was judged by static analysis_j(1) Execution of the sum of_jExecuting the relationship; fruit of fruit M_j(1) Execution, s_jCan also be performed at P_jTo be M_j(1) Is inserted into s_iFront face was obtained of P'_j；

S1.3: to P_iPerforming mutation on the other sentences to obtain some variant branches, judging the execution relation according to the methods in S1.1 and S1.2, and inserting the variant branches into P_iOr on other paths; for P_i', corresponding variant branch set, denoted as

Wherein | P_i' | is the number of variant branches, then P_i' can be expressed as

S1.4: the sentence of different paths in P is mutated, the generated variant branches are inserted into G to obtain a new tested program G ', and a new path set P' containing variant branches is obtained₁',P'₂,…,P'_qQ is the number of paths, and all the variant branches are based on the pathsIs divided into q groups;

s2: constructing a variation test case generation multitask optimization model, namely establishing a variation test case generation multitask optimization model based on path coverage for a plurality of groups of variation branches, wherein the specific method comprises the following steps:

will generate killing

The test case problem is converted into the coverage path P_i' test case problem, coverage P_iThe optimization model for test case generation of' can be expressed as:

max(f_i(X))

s.t.X∈D(X)

wherein D (X) is the value range formed by X; f. of_i(X) is an objective function, which may be defined as the similarity of paths;

for q paths, a multi-task optimization model is established, which can be expressed as:

T¹:max(f₁(X))

s.t.X∈D(X)

T²:max(f₂(X))

s.t.X∈D(X)；

...

T^q:max(f_q(X))

s.t.X∈D(X)

；

s3: generating a variant test case of the multi-task coverage path, namely solving the model constructed in the step S2 by using a multi-population genetic algorithm, and evolving to generate the test case, wherein the specific algorithm is as follows:

set the population as U ═ U₁,U₂,…,U_q}, sub-population U_iCorresponding subtask TⁱIs responsible for generating the overlay path P_iThe test case of' generates initial population, calculates the adaptive value of the evolution individual, implements selection, crossing, and mutation genetic operations in respective tasks;

step 1: setting the value of a control parameter required by the algorithm;

step 2: initializing q sub-populations;

step 3: judging whether the termination condition is met, if so, turning to Step 7;

step 4: for P_i', calculating U_iI-1, 2, …, q, the fitness of the evolved individual f_i(U_i)；

Step 5: judge U_iWhether the individual in (1) is a subtask TⁱIs covered with_i' test case? If yes, saving the individual and the path P covered by the individual_i', end U_iEvolution of (1), deletion of subtask TⁱThe optimization problem of (2);

step 6: comparison U_iCarrying out genetic operations such as selection, crossing, mutation and the like on the performances of different evolved individuals to generate a new population, and turning to Step 3;

step 7: and stopping evolution and outputting a test case set.

Preferably, the objective function f in step S2_i(X) by path similarity representation:

wherein, | P_i' | is P_i' number of upper nodes; i P (X) Δ P_i' | is from the beginning of the procedure, P (X) and P_i' number of identical nodes on.

Preferably, there are two termination conditions in Step3, one is to generate the expected test case, i.e. q becomes 0; the other is population evolution to maximum number of iterations.

Preferably, the adaptive value is defined by an adaptive value function fitniss_i(X) determining, from the objective function, an fitness function:

fitniss_i(X)＝f_i(X)。

the invention has the beneficial effects that:

(1) the invention adopts static analysis to determine the correlation between the input variable and the path execution, and groups the variation branches according to the execution paths, thereby converting the variation test problem into the traditional path coverage problem. The method is beneficial to reference the mature method of the traditional path test and improves the efficiency of the variation test.

(2) For a plurality of variant branches contained in one path, a test case generation model covering one path can be established, and for a plurality of paths, a multitask test case generation optimization model can be established. Each path corresponds to one subtask, which is beneficial to converting a complex test problem into a plurality of subproblems and reducing the test cost.

(3) The multi-population genetic algorithm optimizes a plurality of test targets in parallel, can search in a parallel mode, and can improve the searching efficiency.

Drawings

FIG. 1 is a general flowchart of a method for evolution generation of a multi-tasking software test case according to the present invention;

fig. 2 is an exemplary procedure in an embodiment of the present invention.

Detailed Description

As shown in fig. 1, a general flowchart of a method for evolution generation of a multi-task software test case is provided in the present invention. The method comprises the following steps:

step S1: performing a relevance group mutation branch based on the path to which it belongs:

let the executable path set of G be P ═ P₁,P₂…, record the path

Wherein s is_iIs P_iA certain statement on, s_i+1Is s is_iIs followed by a statement of (1). To s_iPerforming mutation to obtain a mutation branch M_j， M_jIs denoted as M_j(1)。

S1.1: by static analysis, M is judged_j(1) And s_i+1If M is_j(1) Execution, s_i+1Can also be performed, then at P_iIn the above, M can be_j,M_j(1 insertion s)_iGet a path

Because M is_j(1) Is composed of_iObtained by performing mutation, and sub-path "M_j,M_j(1),s_i,s_i+1"is an executable path, and can judge P_i' is also an executable path.

S1.2: if M is_j(1) Execution, s_i+1Must not execute, then find path P in P_j，P_jComprises s_iAnd s is_iS is followed by_j≠s_i+1. Then, M was judged by static analysis_j(1) Execution of the sum of_jThe relationship is executed. Fruit of fruit M_j(1) Execution, s_jCan also be performed at P_jIn the above, M can be_j(1) Is inserted into s_iFront face was obtained of P'_j。

S1.3: to P_iThe other sentences are mutated to obtain variant branches, the execution relation is judged according to the same method, and the variant branches are inserted into the P_iOr other paths. For P_i', corresponding variant branch set, denoted as

Wherein | P_i' | is the number of variant branches, then, P_i' can be expressed as

And

are respectively a path P_i' the first and last variant branches above and their true branches.

S1.4: similarly, the words of different paths in P are mutated, and the generated variant branches are inserted into G to obtain a new program under test G ', and a new path set P' including the variant branches is obtained as { P ═ P₁',P'₂,…,P'_qAnd q is the number of paths. In this way, all variant branches are divided into q groups based on the execution relationships of the paths to which they belong.

Step S2: constructing a multi-task optimization model generated by the variant test case:

since P is_i' comprises

And P_i' also executable path, then overlay P_i' the test case must be able to kill

This will generate killing

The test case problem is converted into the coverage path P_iThe problem of test case of' can be used for establishing a test case optimization model by using the traditional path covering method.

Cover P_iThe optimization model for test case generation of' can be expressed as:

d (X) is the value range formed by X; f. of_i(X) is an objective function, which may be defined as the similarity of paths. From the beginning of the program, X executes the program traversal path denoted as P (X). P (X) and P_i' the similarity is denoted as f_i(X), can be represented by

In the above formula, | P_i' | is P_i' number of upper nodes; i P (X) Δ P_i' | is from the beginning of the procedure, P (X) and P_i' number of identical nodes on.

Because there are q paths, the test case generation problem for these variant branches can be converted into q subproblems, and therefore, a multi-task optimization model can be established, which can be expressed as:

in the above formula P_i' corresponding subtask Tⁱ。

Step S3: generating a variant test case of the multi-task coverage path:

considering that different subtasks have different optimization models, a multi-task problem can be solved by adopting a multi-population genetic algorithm. In the whole population evolution process, the generation of the driving test case is an adaptive value function fitniss_i(X). From an objective function f_i(X) can be obtained by:

fitniss_i(X)＝f_i(X) (5)

algorithm 1 illustrates a method for solving the generation of multi-tasking test cases using multi-population genetic algorithms. When a multi-population parallel genetic algorithm is adopted for solving, each sub-population evolves to solve a sub-optimization problem, so that the whole population is divided into q sub-populations. Set the population as U ═ U₁,U₂,…,U_q}, sub-population U_iCorresponding subtask TⁱIs responsible for generating the overlay path P_iThe test case of' generates an initial population, calculates an adaptation value of an evolved individual, and performs genetic operations such as selection, crossover, and mutation in their respective tasks.

Algorithm 1: the optimization generation method of the multi-task coverage path test case comprises the following steps:

inputting: u ═ U₁,U₂,…,U_q}，P'＝{P₁',P'₂,…,P'_q}；

And (3) outputting: a test case set T;

step 1: setting the value of a control parameter required by the algorithm;

step 2: initializing q sub-populations;

Step 5: judge U_iIs prepared fromWhether it is a subtask TⁱIs covered with_i' test case? If yes, saving the individual and the path P covered by the individual_i', end U_iEvolution of (1), deletion of subtask TⁱThe optimization problem of (2);

step 7: and stopping evolution and outputting a test case set.

In the algorithm 1, two termination conditions are provided in Step3, one is to generate an expected test case, namely q is changed into 0; the other is population evolution to maximum number of iterations.

The following describes the implementation of the present invention by way of example procedures.

FIG. 2 is a triangle example program source code. FIG. 2(a) shows the source code of triangle program G, and FIG. 2 (b) shows the new program G 'with variant branches inserted'

If for statement 3 "if (x)>z) "performing a mutation to obtain a variant branch M₁“if((x>z)！＝(x>- - -a1)) ", then M₁(1) Execute, statement 5 "if ((x + y)<＝z)！＝(x-y<Z) must also be performed, then M may be used₁,M₁(1) Inserted into the path to obtain P₁'＝1,2,M₁,M₁(1) 3,5,7,9,11,12, which is an executable path by static analysis. In the same manner, M is generated₁,M₂,…,M₇Inserting into different paths to obtain new branch paths containing variation, which are respectively:

P₁'＝1,2,M₁,M₁(1),3,5,M₅,M₅(1),7,9,11,M₆,M₆(1),12

P'₂＝1,2,M₃,M₃(1),3,4,5,M₄,M₄(1),7,8

P₃'＝1,2,M₂,M₂(1),3,5,7,9,M₇,M₇(1),11,13

building a multitask optimization model covering the three paths based on the three paths is as follows:

T¹:max(f₁(X))

s.t.X∈D(X)

T²:max(f₂(X))

s.t.X∈D(X)

T³:max(f₃(X))

s.t.X∈D(X)

when the multi-population genetic algorithm is adopted for solving, the number of the sub-populations is set to be 3, and the sub-population scale is set to be 5. The evolution algebra of the multiple group genetic algorithms was set to 3000. The genetic operation adopts roulette selection, single-point crossing and single-point mutation, and the crossing probability and the mutation probability are respectively 0.9 and 0.3. Finally, based on algorithm 2, a test set of killed variant branches is obtained { (23,23,23), (22,50,21), (57,57,60) }.

Claims

1. A multitask software test case evolution generation method is characterized by comprising the following steps: the method comprises the following steps:

Wherein s is_iIs P_iA certain statement on, s_i+1Is s is_iThe successor statement of (1); to s_iPerforming mutation to obtain a mutation branch M_j，M_jIs denoted as M_j(1)；

Can judge P'_iIs also an executable path;

s1.2: if M is_j(1) Execution, s_i+1Must not execute, then find path P in P_j，P_jComprises s_iAnd s is_iS is followed by_j≠s_i+1. Then, M was judged by static analysis_j(1) Execution of the sum of_jExecuting the relationship; if M is_j(1) Execution, s_jCan also be performed at P_jTo be M_j(1) Is inserted into s_iFront face was obtained of P'_j；

S1.3: to P_iPerforming mutation on the other sentences to obtain some variant branches, judging the execution relation according to the methods in S1.1 and S1.2, and inserting the variant branches into P_iOr on other paths; to P'_iThe corresponding variant branch set is denoted as

Wherein | P'_iL is the number of variant branches, then P'_iCan be expressed as

S1.4: the method includes the steps of performing mutation on words of different paths in P, inserting the generated variant branches into G to obtain a new program G ', and obtaining a new path set P ' { P '₁,P′₂,…,P′_qQ is the number of paths, and all the variation branches are divided into q groups based on the execution relation of the paths;

will generate killing

Test case question of (1) is converted to coverage Path P'_iTest case question of (1), cover P'_iThe optimization model generated by the test case in (2) can be expressed as:

max(f_i(X))

s.t.X∈D(X)

set the population as U ═ U₁,U₂,…,U_q}, sub-population U_iCorresponding subtask TⁱResponsible for generating overlay Path P'_iIn each task, generating an initial population, calculating an adaptation value of an evolved individual, and carrying out genetic operations such as selection, crossing, mutation and the like;

step 1: setting the value of a control parameter required by the algorithm;

step 2: initializing q sub-populations;

step 4: to P'_iCalculate U_iI-1, 2, …, q, the fitness of the evolved individual f_i(U_i)；

Step 5: judge U_iWhether the individual in (1) is a subtask TⁱOf'_iIs there a test case? If so, the individual and the route P 'covered by the individual are saved'_iTerminate U_iEvolution of (1), deletion of subtask TⁱThe optimization problem of (2);

step 6: comparison U_iThe performance of different evolutionary individuals in the population, selection, crossover, and variationPerforming operation, generating a new population, and turning to Step 3;

step 7: and stopping evolution and outputting a test case set.

2. The method for evolution generation of the multi-task software test case according to claim 1, wherein: target function f in step S2_i(X) through Path similarity representation

Wherein, | P'_iL is P'_iThe number of upper nodes; l P (X) Δ P'_iL is from the program, P (X) and P'_iThe number of the same nodes.

3. The method for evolution generation of the multi-task software test case according to claim 1, wherein: two termination conditions exist in Step3, one is to generate an expected test case, namely q is changed into 0; the other is population evolution to maximum number of iterations.

4. The method for evolution generation of the multi-task software test case according to claim 2, wherein: said adaptation value is defined by the function fitniss_i(X) determining, from the objective function, an adaptive value function:

fitniss_i(X)＝f_i(X)。