Applying the Enhanced Snow Ablation Optimizer to Generate Data Flow-Based Test Data

Abstract

Software quality can be effectively ensured by software testing. The creation of test data is a key component of software testing automation. One unresolved issue is how to automatically create test data sets for the data flow coverage criterion. Search-based software testing (SBST) is a technique that employs meta-heuristic search algorithms to generate test data. In this paper, a method of automatic test data generation for data flow coverage criterion based on the enhanced snow ablation optimizer (ESAO) is proposed. First, the snow ablation optimizer (SAO) is enhanced to improve the efficiency of the algorithm through the Latin hypercube sampling (LHS) initialization strategy and warming strategy. Second, the construction of the fitness function is considered in terms of both definition node and use node. Third, the data flow-based test cases are automatically generated based on the ESAO. This method of generating test cases that cover all definition-use pairs (DUPs) improves the efficiency and coverage of test case generation, and thus improves the efficiency of software testing.

1. Introduction

To improve the quality and reliability of the software system, thorough testing is carried out before delivery [1,2,3]. About half of the costs associated with software development are incurred during the testing phase [4,5]. The intelligence of software testing can markedly improve the testing efficiency, in which the automatic generation of test data is part and parcel of realizing the intelligence of software testing [6]. Test cases are obtained by analyzing the program under test (PUT), and the methodology is based on structured coverage criteria, which are effective in finding the sources of defects in the PUT. Structured coverage criterion typically consists of control flow coverage criterion and data flow coverage criterion [7]. Control flow coverage criterion is concerned with providing the PUT with reasonable test cases to execute different logical structures. It contains condition coverage, statement coverage, path coverage, branch coverage, decision coverage, etc. Among them, path coverage has the strongest ability to detect errors [8]. However, it cannot detect all defects in the PUT, and the problem of path explosion occurs when there may be countless paths in the PUT with loops. In this case, covering all paths through testing is difficult to achieve. In addition, in actual programs, not every path can be executed, and many paths are unreachable due to dependencies between conditions, in which case the requirement of path coverage cannot be satisfied. Compared to control flow testing (CFT), data flow testing (DFT) focuses on the data–flow interactions in the program and is generally more effective. Because the data flow coverage criteria check the definition–use relationships between variables, and the most basic requirement for program correctness is that the desired output is available for any given input. This association between inputs and outputs is achieved precisely by correlating the definitions and uses of a series of variables in the program. Furthermore, there is a finite number of paths that meet the requirements of the DFT. It can be said that the DFT checks not only the definition –use relationships between variables, but also the control flow in the program [9]. Therefore, the research on DFT is very valuable and necessary. Generating test data that satisfy the adequacy criterion for DFT requires a significant amount of time, and solving this problem automatically will efficiently lessen the labor intensity of software testers and improve the efficiency of software testing. Considering the test data generation process as a sampling process in the input space of PUT, the problem is transmuted into an optimization problem [10].

In recent years, numerous meta-heuristic algorithms (MAs) have been utilized to automatically generate test data for software [11]. SBST, a branch of search-based software engineering (SBSE), employs MAs to generate test data [12]. These algorithms include artificial bee colony (ABC) [13], ant colony optimization (ACO) [14], differential evolution (DE) [15], genetic algorithm (GA) [16], particle swarm optimization (PSO) [17], etc. Girgis [18] applied GA to DFT for the first time and used the all-uses coverage criteria. Nayak et al. [19] and Singla et al. [20] used the PSO algorithm to DFT. Vivanti et al. [21] employed GA for object-oriented programs and conducted DFT. Varshney and Mehrotra [22] put forward GA with the integrated elite strategy for test case generation under data flow coverage criteria. Kumar et al. [23] utilized an accelerating PSO algorithm to generate data flow dependency test data for a program under the guidance of a new fitness function. Rauf [24] developed a data flow generator named DFG, using the ACO algorithm to obtain test data sets that meet all definition-use coverage criteria. Jiang et al. [25] presented a novel test data generation method called evolutionary data flow test generation (EDTG), which includes two stages: DUPs reduction phase and test data generation phase based on GA. Varshney and Mehrotra [26] formulated a hybrid global search method, which combined the adaptive PSO algorithm and DE algorithm to generate test cases covering data flow by neighborhood search strategies, so as to enhance the search ability of the method. Sheoran et al. [27] applied an ABC algorithm to fulfil global and local searches to extract DFT paths. Ghiduk et al. [28] came up with a path-testing method, which employed the PSO algorithm to build test paths to meet the all-uses criterion. Ji et al. [29] described an improved GA-based test data generation method for smart contract DFT to generate high coverage test cases efficiently. SAO is a latest intelligent optimization algorithm developed by Deng and Liu [30], a promising meta-heuristic technique. Since it was proposed on 1 September 2023, SAO has attracted widespread attention. It has been applied to many fields such as engineering optimization [31], computer vision [32], unmanned aerial vehicle path planning [33], photovoltaic power generation forecasting [34], etc. Compared with some classical MAs, SAO has the merits of flexible framework, less parameter configuration, fast convergence and high precision, which can balance the exploitation and exploration of algorithms and prevent premature convergence [35,36]. Therefore, this paper studies the application of SAO to generate test data oriented to data flow criteria.

The main contributions of this article are as follows:

• An enhanced SAO, namely, the ESAO approach is proposed, which utilizes the LHS initialization strategy and the warming strategy to improve the overall optimization efficiency of the approach.

• The effectiveness of the proposed approach is verified by the CEC2017 benchmark test suite. According to the experimental results of 30 benchmark functions, the LHS initialization strategy makes the algorithm more uniformly distributed in the initial solution space, which lays the foundation for the evolutionary optimization of the approach. The warming strategy increases the diversity of the population and effectively avoids the defect that the algorithm is easy to fall into the local extreme value.

• The proposed method is used for data flow-based test data generation, and the fitness function fully considers the definition nodes and use nodes, which fully reflects the data flow coverage criterion. Through 10 actual benchmark programs, the proposed method not only improves the efficiency of generating test data, but also generates test data with high coverage rate.

The rest of the article is organized as follows. Section 2 provides background information, including DFT and basic SAO. Section 3 elaborates on the proposed approach. Section 4 performs the verification experiment. Finally, conclusions and future works are presented in Section 5.

2. Background

2.1. Data Flow Testing (DFT)

DFT is testing the data–flow relationships, i.e., testing the definition of variables and the use of variables in a PUT, and the goal of testing is to generate test cases to cover data–flow relationships.

Definition 1.

Control flow graph (CFG). A CFG is a directed graph $G=(V,E,Entry,Exit)$, with a unique entry node $Entry$ and a unique exit node $Exit$. Where $V$ is a set of nodes, denoting the statements or basic modules of a program and $E$ is a set of edges. Each edge is an ordered node pair $(n_i,n_j)$, which denotes a possible control transfer from $n_i$ to $n_j$.

Definition 2.

Definition-use pair (DUP). A DUP consists of a definition and a use of the same variable. Suppose, given a variable $V$, a statement is said to be a definition of $V$ if it is an assignment to $V$, and a statement is said to be a use of $V$ if the execution of the statement requires the value of $V$. In CFG, if there exists a control flow path between the definition node of variable $X$ and the use node of variable $X$, and no redefinition node about variable $X$ appears between the paths, these two nodes constitute a test goal DUP, denoted as a triple $(var,def,use)$. Among them, $var$ represents a variable, $def$ symbolizes the definition node of variable $var$, and $use$ represents the use node of variable $var$.

Definition 3.

A variable $var$ redefinition node, also known as a killing of $var$. It is a redefinition of a variable that appears in a sub-path from the definition node $def$ to the use node $use$.

Before generating test cases satisfying the data flow coverage criterion, the test objectives to be covered need to be analyzed based on the CFG and the data flow coverage criterion, i.e., the DUPs. In the process of generation, the data flow coverage criteria are: the all-defs criterion, the all p-uses criterion, the all c-uses criterion, the all-uses criterion, the all du-paths criterion, the all p-uses/some c-uses criterion, the all c-uses/some p-uses criterion [37]. The overall properties of these relationships are shown in Figure 1. The criterion at the end of the arrow in Figure 1 is contained in the criterion at the start of the arrow. A great deal of experimental studies have shown that the all-uses criterion is the most effective and practical criterion in the whole family of data flow criteria. Therefore, this paper chooses the all-uses criterion as the test criterion. If and only if the test cases are made to follow the $\mathrm{DUP}$ from definition to use, then the program satisfies the all-uses criterion.

Table 1 shows a MaxMin program whose function is to obtain the maximum and minimum values of three integers. The first column in Table 1 represents the row number of each row of the program. Figure 2 shows the corresponding CFG for this program, with a corresponding number in each node which indicates the line number information of the program in Table 1. In Figure 2, node 6 is the use node, and the nodes that reach node 6 are 0, 1, 3, 5. Node 0 is the definition node in relation to the variable $c$, and nodes 1, 3, 5 are the definition nodes concerning the variable $max$. Therefore, there are four DUPs at node 6: DUP (c,0,6), DUP (max,1,6), DUP (max,3,6), and DUP (max,5,6). All the DUPs of this program are shown in Table 2.

2.2. Snow Ablation Optimizer (SAO)

SAO is a physical optimization algorithm for simulating the sublimation and melting behavior of snow, developed by Deng and Liu in 2023 [30]. According to physics, snow can change into liquid water or steam. Melting and sublimation are the two physical processes that correspond to these two forms. Snow can be instantly converted into steam via sublimation, or it can be melted directly into liquid water. At the same time, it is important to note that liquid water converted by melting snow can also be converted to steam through evaporation. This is shown in Figure 3.

(1)$X_i(t+1)=\left\{\begin{array}{c}Elite(t)+B{M}_i(t)\otimes ({\theta }_1\times (G(t)-X_i(t))+(1-{\theta }_1)\times (\overline{X}(t)-X_i(t))),i\in inde{x}_a\\ M\times G(t)+B{M}_i(t)\otimes ({\theta }_2\times (G(t)-X_i(t))+(1-{\theta }_2)\times (\overline{X}(t)-X_i(t))),i\in inde{x}_b\end{array}\right.$

where $Elite(t)$ is a random selection of individuals from a group of several elites in the whole swarm; $B{M}_i(t)$ denotes a vector including random numbers following the Gaussian distribution representing the Brownian motion; the sign ⊗ stands for entry-wise multiplications; ${\theta }_1$ denotes a number chosen at random from [0,1]; $X_i(t)$ represents the position of the $i$ th individual in the $t$ generation iteration; $\overline{X}(t)$ represents the central location of the entire population; $inde{x}_a$ and $inde{x}_b$ represent the individual rows of the two sub-populations $P_a$ and $P_b$; $M$ denotes the snowmelt rate.

For the standard Brownian motion, the step size is determined by utilizing the probability density function. Its expression is as follows:

(2)$f_{BM}(x;0,1)={\displaystyle \frac{1}{\sqrt{2\pi }}}\times \exp (-{\displaystyle \frac{x^2}{2}})$

$Elite(t)$ is calculated as follows:

(3)$Elite(t)\in [G(t),X_{second}(t),X_{third}(t),X_c(t)]$

where $G(t)$ represents the current optimal position, and $X_{second}(t)$ and $X_{third}(t)$ represent the second and third best individuals, respectively. $X_c(t)$ denotes the central position in the top 1/2 of the fitness value of the individual. $Elite(t)$ is randomly selected from $G(t)$, $X_{second}(t)$, $X_{third}(t)$, and $X_c(t)$. $X_c(t)$ is calculated as follows:

(4)$X_c(t)={\displaystyle \frac{1}{N_1}}{\displaystyle \sum _{i=1}^{N_1}{X}_i(t)}$

where $N_1$ stands for the number of individuals with the top 1/2 fitness value.

$\overline{X}(t)$ represents the central location of the entire population and is calculated as follows:

(5)$\overline{X}(t)={\displaystyle \frac{1}{N}}{\displaystyle \sum _{i=1}^N{X}_i(t)}$

$M$ is the snowmelt rate, which is calculated as follows:

(6)$M=(0.35+0.25\times {\displaystyle \frac{e^{\frac{t}{t_{\max }}}-1}{e-1}})\times T(t)$

(7)$T(t)=e^{{\displaystyle \frac{-t}{t_{\max }}}}$

where $t_{\max }$ represents the termination criterion.

The flow chart of SAO is shown in Figure 4.

Step 1: Initialize the parameters of SAO, population size $N$, maximum number of iterations $t_{\max }$, and initialize the population position.

Step 2: Calculate the fitness function and reserve the optimal position.

Step 3: Calculate the snowmelt rate $M$.

Step 4: Randomly divide the whole population into two sub-populations.

Step 5: Update individual positions according to the individual position update Formula (1).

Step 6: Calculate the fitness value and update the optimal position.

Step 7: Determine whether the maximum number of iterations is reached, if so, output the optimal position; otherwise, repeat step 2 to step 7.

3. The Proposed Method

In this section, the proposed ESAO is described in detail and applied in test case generation for data flow coverage criterion. First, the LHS initialization strategy and the adaptive warming strategy are developed to enhance the performance of the approach. Second, the construction method of the fitness function is provided by considering definition nodes and use nodes separately. Then, the test data generation model based on the ESAO approach is put forward. Finally, the specific process of generating test data by ESAO is given.

3.1. Latin Hypercube Sampling (LHS) Initialization Strategy

In intelligent optimization algorithms, the population initialization is an indispensable part, and it is found that the initial population plays a key role in the convergence rate and the quality of the final solution [38]. Initialization is the first and critical step in SAO. The population individuals in the standard SAO are initialized randomly within the feasible domain interval using a rand function, as depicted in Figure 5a. This approach generates a higher level of randomness to the population, but does not guarantee uniform coverage across the solution space region. Consequently, it diminishes the efficiency of the subsequent iterations of the algorithm. LHS is a method of uniform sampling in a multidimensional space, which is used to generate a set of samples that are as uniform as possible, with as few repetitions as possible, in a given parameter space. Under the guarantee of randomness and uniformity of the samples, to improve the optimization efficiency of the SAO, the LHS is used to initialize the population, as depicted in Figure 5b. The random sample points are uniformly distributed in the feasible domain, which enriches the diversity of the initial population. In Figure 5, the population size N = 30, dimension dim = 2, interval [0,1]. As can be seen from Figure 5, the population initialization using the LHS strategy is more uniform than the random initialization of the standard SAO, and the diversity of the population is more diverse.

The specific steps of population Initialization are as follows:

Step 1: Determine the population size $N$, and the dimension $D$;

Step 2: Set a hypercube variable of dimension $D$ and variable $x^j\in [lb,ub],j=1,2,\dots ,D.$ Where $lb$ and $ub$ are the upper and lower bounds of the variable, respectively;

Step 3: Divide the domain of definition $[lb,ub]$ of the variable $x^j$ into $N$ equal sub-intervals;

Step 4: Randomly select a point from each sub-interval in each dimension;

Step 5: Combine the points of each dimension extracted to form an initial population.

3.2. Adaptive Warming Strategy

To increase the diversity of the population and avert the occurrence of the premature phenomenon of standard SAO, the method may be able to escape the local optimal solution with the aid of temperature increases. In this paper, the diversity of the solution set is utilized to design an adaptive warming strategy. Each feasible solution generated during the running of the algorithm forms a solution set, and according to the solution set recorded by the algorithm, the relationship between the real-time maximum fitness, $f_{\max }$, and the real-time average fitness value, $f_{avg}$, defines the diversity of the current solution set, $F_{Div}$. The calculation formula is as follows:

(8)$F_{Div}={\displaystyle \frac{f_{\max }-f_{avg}}{f_{\max }}}$

As the $f_{avg}$ value gets closer to $f_{\max }$, it indicates that the diversity of the solution set decreases at this time. With the decrease in population diversity, the greater the possibility of the algorithm tapping into the local optimum, the greater the temperature warming should be. The adaptive warming strategy is as follows:

(9)$T(t)=\left\{\begin{array}{c}{e}^{{\displaystyle \frac{-t}{t_{\max }}}},0.5<F_{Div}\le 1\\ e^{{\displaystyle \frac{-t}{t_{\max }}}}+e^{{\displaystyle \frac{t}{t_{\max }}}},0<F_{Div}\le 0.5\end{array}\right.$

3.3. Design of the Fitness Function

The fitness function is of great importance to the process of generating test cases, which is used to assess the quality of the test cases [39]. The fitness function is applied to estimate the degree of coverage of each test case relative to the objective, which guides the execution of the algorithm and the evolution of the test cases. This article considers definition nodes and use nodes separately to construct the fitness function by the approximate level, branch distance, and killing nodes.

Suppose there are $n$ test targets in the test target $DUPs$, $DUPs=(DU{P}_1,DU{P}_2,\dots ,DU{P}_n)$. There are $m$ test cases in the test case set $X$, $X=\left(X_1,X_2,\dots ,X_m\right)$. In the data flow coverage criterion, the approximate level, is used for measuring the deviation between the $DUP$ covered by the test case $X_i$ and the test objective, denoted as $app(X_i)$. If the $X_i$ covers the test objective, the $app(X_i)$ is 0; otherwise, the $app(X_i)$ is 1. Branch distance represents the branching distance from test case $X_i$ to the node, denoted as $dist(X_i)$. The branch distance is calculated as shown in Table 3.

If the test case executes a branch predicate $a<b$, its branch distance is calculated as shown in Equation (10):

(10)$dist(X_1)=\left\{\begin{array}{c}0\begin{array}{cc},& \end{array}a<b\\ a(X_i)-b(X_i)+k\begin{array}{cc},& \end{array}a\ge b\end{array}\right.$

where $a(X_i)$ and $b(X_i)$ represent the value of $a$ and the value of $b$, respectively, after the test case $X_i$ executes the branching predicate. The constant $k$ is used to deal with boundary cases. When satisfying $a\ge b$, the branch distance of the test case $X_i$ after passing the branching predicate is $a(X_i)-b(X_i)+k$. If there is no constant $k$ and $a$ equal to $b$, the branch distance in the case where $a<b$ is not satisfied is 0. The same branch distance that satisfies the condition of $a<b$ cannot be differentiated; therefore, the constant $k$ is used to distinguish this case. This article sets the value of $k$ to 1.

To prevent $dist(X_i)$ from being too large and weakening the impact of $app(X_i)$ and killing nodes, a normalization operation is performed on $dist(X_i)$ as shown in Equation (11):

(11)$dis{t}^{\prime }(X_i)={\displaystyle \frac{dist(X_i)}{dist(X_i)+1}}$

Therefore, the formula for the definition node or use node for a certain variable during the execution of $X_i$ is shown in Equation (12):

(12)$f(X_i)=app(X_i)+dis{t}^{\prime }(X_i)$

For $\mathrm{DUP}$, a killing node refers to a redefinition node of the same variable, i.e., there exists a redefinition node for the variable between the definition node of the variable and the use node, denoted as $killing$. When test case $X_i$ seeks the fitness value for the jth $\mathrm{DUP}$, if there is a killing node from the definition node to the use node, the value of the $killing$ is set to 1. If there is no killing node, the value of $killing$ is set to 0.

The fitness value of $X_i$ for the jth $DUP$ is expressed by $fit(X_i,DU{P}_j)$, $0<i\le m$ and $0<j\le n$, and the calculation formula is shown in Equation (13):

(13)$fit(X_i,DU{P}_j)=\min (f_{def}(X_i)+f_{use}(X_i)+killing)$

where $f_{def}(X_i)$ indicates the distance from the ith test case to the definition node of the jth $DUP$, $f_{use}(X_i)$ represents the distance from the ith test case to the use node of the jth $DUP$, and $killing$ denotes the information about killing the node.

For all $DUPs$ in the PUT, the test case $X_i$ covers each $DUP$ to calculate its fitness value. The minimum fitness value on the $DUPs$ is taken as the fitness value of the corresponding test case, and all of them are summed up to be the fitness value of that test case set. One test case covers all targets. Consequently, the fitness function for $X_i$ is shown in Equation (14):

(14)$F(X)={\displaystyle \sum _{j=1}^{n}fit(X_i,DU{P}_j)}$

where $j$ represents the jth test target $DUP$, $n$ represents the number of test targets, $0<j<n$.

Suppose a test case set for the program in Figure 2 is $X\{(2,5,4),(4,2,1)\}$. The execution paths for $X_1(2,5,4)$ and $X_2(4,2,1)$ are $(2F,6F,8F)$ and $(2T,6F,8T)$. Since there is no variable $max$ killing node on the execution path, $killing$ is 0. Then, for $DUP(max,3,6)$ in the coverage objective, the fitness value is calculated as follows:

$\begin{array}{c}f(X_1)=f_{def}(X_1)+f_{use}(X_1)+killing\hfill \\ =1+(b-a+1)/((b-a+1)+1)+0+(\max -c+1)/((\max -c+1)+1)+0\hfill \\ =1+(5-2+1)/((5-2+1)+1)+0+(5-4+1)/((5-4+1)+1)+0\hfill \\ =2.467\hfill \end{array}$

$\begin{array}{c}f(X_2)=f_{def}(X_2)+f_{use}(X_2)+killing\hfill \\ =0+(b-a+1)/((b-a+1)+1)+0+(\max -c+1)/((\max -c+1)+1)+0\hfill \\ =0+(2-4+1)/((2-4+1)+1)+0+(4-1+1)/((4-1+1)+1)+0\hfill \\ =0.8\hfill \end{array}$

$\begin{array}{c}\mathrm{In} \mathrm{summary}, fit(X_i,DU{P}_j)=\min (f_{def}(X_i)+f_{use}(X_i)+killing)\hfill \\ =\min (f(X_1),f(X_2))=f(X_2).\hfill \end{array}$

Similarly, the fitness value of the test case relative to all the $DUPs$ in the coverage target is computed and the minimum value of the current $DUPs$ is selected as the final fitness value.

3.4. The Model of Generating Test Data Based on the Enhanced Snow Ablation Optimizer (ESAO)

Figure 6 illustrates the model for generating test data based on the ESAO. Its composition has three main parts, which are CFG construction, data flow analysis, and test data generation. To automate test data generation, it is vital to analyze the program structure to build CFG for the program. In the CFG build phase, the structure of the PUT is built from the source code. To meet the all-uses criteria, the data flow analysis is required to extract the DUPs as the test targets for test data generation. During the data flow analysis phase, the generated CFG is traversed to extract the definition–use relationships of variables and identify the test objective. In the test data generation stage, the source program is examined according to the test objective and the ESAO is applied to iteratively search for the optimal test case.

3.5. The Specific Process of Generating Test Data Based on the Enhanced Snow Ablation Optimizer (ESAO)

Step 1: The PUT is analyzed using the abstract syntax tree (AST) to generate the CFG.

Step 2: Perform the data flow analysis of the PUT to obtain all $DUPs$, $DUPs=\{du{p}_1,du{p}_2,\dots ,du{p}_n\}$ in the program.

The specific steps for calculating all DUPs in the program are as follows, and its flow chart is graphed in Figure 7.

(1) Traverse the CFG of the program using the depth-first traversal method to obtain all paths $P$ of the program;

(2) Define two stacks $ps$ and $ns$ to store paths and nodes in the CFG, respectively;

(3) Start traversing from the head node of CFG. Assuming that $p$ is the current path and $n$ is the current node, firstly, add the current node $n$ to the path $p$, and determine whether there exists a successor node for $n$. If $n$ has only one successor node, traverse the successor node as the current node $n$. If $n$ has multiple successor nodes, for each successor node $m$, push $m$ into the stack $ns$, copy the current path $p$ and create a new path and push it into stack $ps$, and pop up a top element from stack $ps$ and $ns$ as the current path $p$ and the current node $n$, respectively; if $n$ has no successor node, it indicates that the current path has been traversed. Then, determine whether $ps$ and $ns$ are empty, if yes, the path computation is finished; otherwise, pop up a top element from the stacks $ps$ and $ns$ as the current path $p$ and the current node $n$. Finally, for each path computed, traverse the nodes in the path from the bottom upwards. When the use node $u$ of the variable $v$ is encountered, search upwards for the closest definition node $d$ of $v$, and construct the $(v,d,u)$ of the variable $v$. Ultimately, obtain all $DUPs$ in the program.

Step 3: Initialize the parameters of the ESAO, set the maximum number of iterations $t_{\max }$, randomly generate $n$ particles, and initialize the position of the particles $X_i$, $i=1,2,\dots ,N$. Where $X_i=[X_{i1},X_{i2},\dots ,X_{iD}]$.

Step 4: Evaluate the fitness function for each particle using Equation (14).

Step 5: Take a $du{p}_j$ from the $DUPs$ to be tested and $j$ denotes the jth $DUP$ in the set of $DUPs$ to be tested.

Step 6: Record the current optimal position $G(t)$.

Step 7: Determine whether the current fitness function value is 0, if it is 0, indicate that the test case has covered $du{p}_j$, then go to Step 12; otherwise, go to Step 8.

Step 8: Calculate the snowmelt rate $M$.

Step 9: Randomly divide the two populations into two sub-populations and update the positions of the particles separately for each sub-population.

Step 10: Calculate the fitness function for each particle.

Step 11: Update the current optimal position.

Step 12: Update the set of test cases and remove $du{p}_j$ from the $DUPs$. Determine whether the algorithm reaches the termination condition, if yes, go to Step 13; otherwise, go to Step 5.

Step 13: Output the set of test cases and the algorithm ends.

4. Experiment

In this section, the performance of the proposed approach is evaluated. First, the benchmark functions and benchmark programs are introduced in Section 4.1. Then, the parameter settings and evaluation indicators of the algorithm are given in Section 4.2. Finally, the results are reported and analyzed in Section 4.3.

4.1. Experimental Subjects

4.1.1. Benchmark Functions

The CEC2017 benchmark test suite, which contains a series of different types of optimization problems, is used to evaluate the performance of optimization algorithms. As shown in Table 4, the function types are categorized into four types, namely, unimodal functions, multimodal functions, hybrid functions, and composition functions. Among them, the unimodal function possesses a global optimum, which is often applied to verify the exploitation ability of the algorithm. Multimodal functions have a wide variety of local optima and are more complex than unimodal functions. The hybrid functions and composition functions have different features in different areas; therefore, they can mimic the real search space well. Thus, the potential performance of an algorithm can be measured by the optimization-seeking ability of these typical benchmark test suites, and the performance of real-world problems can be reflected by the results of these benchmarks.

4.1.2. Benchmark Programs

Ten benchmark programs were selected for validation in the experiment, which are broadly used in the research of test data generation [40,41,42,43,44,45]. The detailed descriptive information is described in Table 5.

In Table 5, the second column contains the program name and the corresponding provenance. The first column is the program number, the third column indicates the number of variables contained in the program, the fourth column is the number of code lines, the fifth column represents the number of test targets in the program, and the sixth column is the description information of the program.

4.2. Experimental Design

4.2.1. Algorithm Parameters

To verify the performance of the proposed method, the ESAO is compared with the standard SAO [26]. The effectiveness of the algorithm is verified on the CEC2017 benchmark test suite, and the efficiency of data generation based on DFT is verified on the benchmark programs. To avoid the influence on the algorithms due to different parameter settings, the common parameters of two algorithms are set consistently:

• ▪. Population size: 50

• ▪. Search space: [1, 100]

• ▪. Maximum number of iterations: 1000

4.2.2. Evaluation Indicators

To appraise the efficiency and effectiveness of the proposed algorithm, the results of several experiments are used for comprehensive evaluation.

For the test of CEC2017 benchmark functions, the following metrics, Mean, Standard deviation (Std), Best, and Worst, are utilized for comparison.

• ❖. Mean

The mean represents the number of quantities in a set of data that reflect the trend in the concentration of the data, an indicator of the trend in the concentration of the data. Its expression is as follows:

(15)$Mean={\displaystyle \frac{{\displaystyle \sum _{i=1}^n{x}_i}}{n}},$

where $n$ represents the number of data and $x_i$ represents the ith data.

• ❖. Std

The standard deviation reflects the degree of data dispersion. The smaller the standard deviation, the more aggregated the data and the better the repeatability. The larger the standard deviation, the more dispersed the data are and the less the repeatability. Its expression is as follows:

(16)$std=\sqrt{{\displaystyle \frac{{\displaystyle \sum _{i=1}^n(x_i-\overline{x})}}{n}}}$

where $\overline{x}$ represents the average value of the data and $n$ stands for the number of data.

• ❖. Best

The best value and the worst value manifest the ultimate optimal and ultimate worst performance of the algorithm.

(17)$best=\min \{x_1,x_2,\dots ,x_n\}$

• ❖. Worst

(18) $worst=\max \{x_1,x_2,\dots ,x_n\}$

For benchmark programs, the metrics are measured by four performance evaluation metrics: average coverage rate (AvgRat), average search time (AvgTime), average number of evolutionary generations (AvgGen), and success rate (SucRate).

• ❖. AvgRat

The AvgRat indicates the average percentage coverage achieved. It is used to assess the level of which the generated test data cover the test targets. This is calculated as follows:

(19)$AvgRat={\displaystyle \frac{1}{m}}{\displaystyle \sum _{m=1}^{s}Ratio}$

(20)$Ratio={\displaystyle \frac{\left|nCovered\right|}{\left|Test\mathrm{Re}q\right|}}$

where $\left|Test\mathrm{Re}q\right|$ is the total number of test targets, $\left|nCovered\right|$ is the number of test targets that have been covered, and $s$ is the number of experiments.

• ❖. AvgTime

The start time and end time of the execution process were recorded in the experiment. The average search time is calculated as follows. It is a direct measure to evaluate the performance of a method. The calculation method is as follows:

(21)$Avgtime={\displaystyle \frac{1}{m}}{\displaystyle \sum _{m=1}^{s}search\_time}$

(22)$search\_time=end\_time-start\_time$

• ❖. AvgGen

The AvgGen is the average of the number of evolutionary generations that achieve 100% data flow coverage or reach the maximum number of evolutionary generations. It is a commonly used indicator to evaluate the efficiency of a method. The calculation is as follows:

(23)$\mathrm{Avg}Gen={\displaystyle \frac{1}{m}}{\displaystyle \sum _{m=1}^{s}Gen},$

(24)$Gen={\displaystyle \sum _{i=1}^{\left|Test\mathrm{Re}q\right|}nGeneratio{n}_i}$

where $nGeneratio{n}_i$ is the number of iterations required to cover test object $i$, $\left|Test\mathrm{Re}q\right|$ is the total number of test targets, and $s$ is the number of experiments.

• ❖. SucRate

The success rate represents the probability that each experiment will achieve 100% data flow coverage.

(25)$SucRate={\displaystyle \frac{x}{s}}$

where $x$ denotes the number of realizations that achieved 100% coverage and $s$ represents the total number of experiments.

4.3. Experimental Results

4.3.1. CEC2017 Benchmark Functions

The experiments are performed in 30 benchmark test functions of 10 dimensions of the CEC2017. To verify the effectiveness of the method, the ESAO is compared with SAO [30], LSAO (3.1) with LHS initialization only, and TSAO (3.2) with warming strategy only. To avoid the influence of randomness on the results, the common parameters in the algorithms are configured uniformly and 20 independent experiments are conducted for each algorithm. The performance of the algorithms is compared by the mean, standard deviation, best and worst values of the results. The platform of all the experiments is the MATLAB R2021b software and the results are shown in Table 6.

As Table 6 shows, the ESAO improves the optimization search performance of the SAO.

For unimodal functions F1 to F3, the ESAO is overall superior to the SAO. On F1, the ESAO is inferior to the TSAO in terms of the best value, and superior to the other three algorithms in terms of the other three aspects, such as the mean, the standard deviation, and the worst value. On F2 and F3, the best values of the four algorithms are consistent, and all of them find the actual values, but the ESAO is superior to the other three algorithms in the other three aspects. It shows that the ESAO is effective on the unimodal problems.

Regarding the multimodal functions F4 to F10, it can be concluded that the ESAO, on F4, outperforms the other three algorithms in three aspects and is inferior to the TSAO in terms of the standard deviation. The ESAO, on F5, outperforms the other three algorithms in three aspects, and is consistent with the SAO in the best value. The ESAO, on F6, is consistent with the other algorithms in the best value and is in line with the actual value, and is inferior to the TSAO in the other aspects, but superior to the SAO. It shows that the warming strategy is more effective on the F6 function. On F7, the ESAO is better than the other three algorithms in all three aspects, and inferior to the TSAO in the best value. On F8, the ESAO outperforms the other three algorithms in three aspects, is inferior to the LSAO in terms of the best value, but outperforms the SAO. The LHS initialization strategy is more significant on F8. On F9, the ESAO is consistent with the other three algorithms in the best value, consistent with the actual value, superior to the SAO and TSAO in the worst value, consistent with the LSAO, superior to the other three algorithms in the standard deviation, inferior to the LSAO in the mean value, but superior to the SAO and TSAO. On F10, the ESAO outperforms the other three algorithms in the mean and standard deviation, is inferior to the SAO in the best value, but outperforms the LSAO and TSAO, and the ESAO outperforms the LSAO and is inferior to the SAO and TSAO algorithms in the worst value.

For hybrid problems F11 to F20, the experimental results are analyzed as follows. For F11, F13, F14, F15, and F19, the ESAO is inferior to the TSAO in the best value, but superior to the SAO, LSAO, and TSAO in the other three aspects. On F12, the ESAO is inferior to the LSAO in terms of the standard deviation, but superior to the other three algorithms in terms of the best value, and superior to the LSAO and TSAO and inferior to the SAO in terms of the mean value. On F16, the ESAO is inferior to the LSAO in the best value but superior to the other three algorithms in all other aspects. For F17, the TSAO shows better performance on the mean and best value, and the LSAO shows better performance on the standard deviation and the worst value, which shows the effectiveness of the LHS initialization and warming strategies. On F18, the LSAO shows better performance on the standard deviation and worst value, the TSAO shows better performance on the mean value, and the ESAO outperforms the other three algorithms on the best value. On F20, the ESAO outperforms the other three algorithms on the best and worst values, and is worse than the TSAO on the standard deviation and mean, but better than the SAO and LSAO.

For composition functions F21 to F30, the experimental results are analyzed as follows. For F25, F27, and F30, the ESAO outperforms the other three algorithms in all four aspects. On F21, the ESAO outperforms the other three algorithms in the mean, standard deviation, and worst value, and is inferior to the TSAO in the best value, indicating the effectiveness of the warming strategy. On F22 and F26, the ESAO is consistent with the other three algorithms in terms of the best value and better than the other three algorithms in the other three aspects. On F23, the ESAO is inferior to the LSAO in the worst value, but outperforms the other three algorithms in the other three aspects. On F24, the ESAO is consistent with the LSAO in terms of the best value, but outperforms the SAO and TSAO algorithms, and outperforms the other three algorithms in the other three aspects. On F28, the ESAO is consistent with the other three algorithms in terms of the best value, outperforms the other three algorithms in terms of the standard deviation and the mean, and is consistent with the TSAO in terms of the worst value, all of which are superior to the LSAO and SAO algorithms. On F29, the ESAO is inferior to the TSAO in terms of the standard deviation, but performs optimally in all other three aspects.

Overall, the ESAO is better than the SAO, indicating that the LHS initialization strategy improves the convergence accuracy and stability of the algorithm, and the adaptive warming strategy further prevents the algorithm from converging to the local optimal. The combination of the LHS initialization strategy and warming strategy improves the efficiency of the ESAO algorithm.

To exhibit the convergence characteristics of various algorithms more intuitively, the convergence curves of the four algorithms on some test functions are shown in Figure 8, Figure 9, Figure 10, Figure 11, Figure 12, Figure 13, Figure 14, Figure 15, Figure 16, Figure 17, Figure 18, Figure 19, Figure 20, Figure 21, Figure 22 and Figure 23.

From the figure, it can be seen that the SAO, LSAO, and TSAO tend to fall into the local optimum solution in the late iteration, while the convergence curve of the ESAO is decreasing during the iteration process, which is attributed to the fact that the ESAO has added the adaptive warming strategy in the algorithm to avoid the algorithm from falling into the local optimum value. The above experimental results are realistic that the ESAO proposed in this article has strong optimization-seeking ability and stable performance, and can avoid falling into the local optimal more effectively.

4.3.2. Benchmark Programs

Although the benchmark programs are not large, they are diverse and share many of the same structures as the large programs. Hence, we believe that our approach can handle larger programs. Table 7 and Figure 24 display the average number of evolutionary generations and average search time for all programs, and Figure 25 and Figure 26 show the average coverage rate and success rate for all programs, respectively.

From the experimental results in Table 7 and Figure 24, it can be seen that for programs Pro1 to Pro10, the ESAO consumes fewer average evolutionary generations and uses shorter evolutionary time in generating test data. It indicates that the ESAO is more efficient in generating test data for data flow. Meanwhile, the number of evolutionary generations required and evolutionary time consumed will be more for programs with slightly more complex logic, such as Pro1, Pro3, Pro4 and Pro9, but the ESAO is still less than the SAO. Especially, on the Pro9 program, the average number of iterations required by the ESAO is 21.4 generations, while the SAO requires 58.45 generations, and the ESAO is 37.05 generations less than the SAO. At the same time, the ESAO takes 2.5782 s less evolutionary time than the SAO to generate test data.

As can be seen in Figure 25, the ESAO has an overall higher probability than the SAO in covering all definition-use pairs. On Pro1, Pro4, Pro5 and Pro9, the ESAO does not achieve 100% coverage, but it is higher than the SAO. On the other programs, the ESAO reached 100% coverage. From Figure 26, it can be concluded that the ESAO is generally higher than the SAO in terms of the success rate. ESAO is not fully successful on Pro1, Pro4, Pro9 and Pro10, but it is completely successful on the other six algorithms. The SAO achieves full success on only three programs.

5. Discussion

The problem of data-flow test data generation is undecidable and can be expressed as whether a particular execution path of the PUT can be found to override a given DUP. The most widely used approach to solving this problem is the search-based approach, which utilizes MAs to identify test inputs for target DUPs. This paper presents ESAO, a SBST technique, which generates test data for DFT. On the one hand, the initial population is evenly distributed in the solution space by using the LHS initialization strategy, which lays a good foundation for the evolution of the population. Adaptive warming strategies, on the other hand, increase the diversity of populations and prevent algorithms from falling into local extremes. The effectiveness of the proposed method is compared and evaluated by using CEC benchmark functions and benchmark programs. Experimental results show the superiority of the proposed method in terms of the AvgGen, the AvgTime, the AvgRat, and SucRate for all programs. As with other empirical studies, there are some validity threats to the experiment. The external validity mainly lies in the generalization of the experimental results. This paper only uses 10 small and medium-sized projects. Using different programs may result in different combinations of DUP and therefore may result in different iterations and test data. However, all of these benchmark procedures are widely used in test data generation research. These programs are diverse and share much of the same structure as many large programs. Therefore, the proposed method can handle real and complex programs. The internal validity of this study lies in the variables of the ESAO, such as the number of iterations, the range of test cases, and the size of the population. The adoption of these parameters may affect the coverage of the generated test case and the efficiency of the approach. In addition, the time cost of each iteration depends on the actual experimental environment and may vary in different environments. In the experiment, the common parameter configurations of all algorithms are consistent, and each approach is run independently 20 times to calculate the average value, so as to avoid the influence of randomness on the experimental results.

6. Conclusions

As software becomes more complex, the automation of testing tasks becomes increasingly necessary. DFT can not only check the define–use relationship between variables, but also detect faults missed by the CFG. In this paper, an ESAO is proposed and applied to automatically generate test data that satisfy the data flow coverage criteria. This approach is the first attempt to apply the SAO to the test case generation of the data flow criteria. The population initialization strategy of LHS makes the initial population evenly distributed in the solution space, which lays a good foundation for population optimization and accelerates the convergence speed of the algorithm. The adaptive warming strategy increases the diversity of the population, avoids premature convergence of standard SAO, and helps the algorithm to jump out of the local optimal solution. The construction of the fitness function considers not only the definition node, but also the use node. Using the CEC2017 benchmark test suite, it is shown that the proposed ESAO outperforms the SAO and validates the effectiveness of the initialization and warming strategies. Meanwhile, experiments are carried out in the 10 real benchmark programs, and it is shown that the proposed method not only improves the efficiency of generating test data for DFT, but also generates test data with high coverage rate. The ESAO proposed in this paper solves the problem of data flow test data generation, expands the application range of MAs, enriches the theory of test data generation, and provides a new way to solve the problem for practitioners in the software test industry. The data generation model based on the ESAO proposed in this paper provides a new perspective for test case generation, but it still needs further exploration. Future research could be explored simultaneously to cover multiple DUPs, thereby enriching and refining the existing theoretical framework. This paper mainly focuses on the test data generation problem, but it can be extended to a wider field in the future, and the application range of MAs can be broadened. In the future work, we will focus on developing a system for DFT data generation. In addition, we will expand our approach to large-scale open-source programs and real-world software programs.

Author Contributions

Conceptualization, C.J.; methodology, C.J.; software, C.J.; validation, C.J., C.Z. and W.Z.; formal analysis, Q.Z.; investigation, C.Z.; resources, Q.Z.; data curation, C.J.; writing—original draft preparation, C.J.; writing—review and editing, W.Z. and Q.Z.; visualization, C.Z.; supervision, W.Z.; project administration, Q.Z.; funding acquisition, Q.Z. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

Abbreviations

The following abbreviations are used in this manuscript:

ABC	Artificial Bee Colony
ACO	Ant Colony Optimization
AST	Abstract Syntax Tree
AvgGen	Average Number of Evolutionary Generations
AvgRat	Average Coverage Rate
AvgTime	Average Search Time
CFG	Control Flow Graph
CFT	Control Flow Testing
DE	Differential Evolution
DFT	Data Flow Testing
DUP	Definition-use Pair
DUPs	Definition-use Pairs
EDTG	Evolutionary Data-Flow Test Generation
ESAO	Enhanced Snow Ablation Optimizer
GA	Genetic Algorithm
LHS	Latin Hypercube Sampling
MAs	Meta-heuristic Algorithms
PSO	Particle Swarm Optimization
PUT	Program Under Test
SAO	Snow Ablation Optimizer
SBSE	Search-based Software Engineering
SBST	Search-based Software Testing
Std	Standard Deviation
SucRate	Success Rate

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. The data flow test adequacy criteria.

Figure 2. The CFG of MaxMin program.

Figure 3. Snow melts in nature.

Figure 4. The flow chart of SAO.

Figure 5. Population initialization distribution. (a) Random initialization; (b) LHS initialization.

Figure 6. Test data generation model for data flow criteria.

Figure 7. The flow chart for calculating all definition-use pairs in the program.

Figure 8. Convergence curve of F1.

Figure 9. Convergence curve of F2.

Figure 10. Convergence curve of F3.

Figure 11. Convergence curve of F5.

Figure 12. Convergence curve of F10.

Figure 13. Convergence curve of F12.

Figure 14. Convergence curve of F13.

Figure 15. Convergence curve of F14.

Figure 16. Convergence curve of F15.

Figure 17. Convergence curve of F16.

Figure 18. Convergence curve of F20.

Figure 19. Convergence curve of F22.

Figure 20. Convergence curve of F24.

Figure 21. Convergence curve of F26.

Figure 22. Convergence curve of F28.

Figure 23. Convergence curve of F30.

Figure 24. The differential results of the various algorithms.

Figure 25. The average coverage rate for benchmark programs.

Figure 26. The success rate for benchmark programs.

Table 1

MaxMin program.

No.	MaxMin
0	Function F = MaxMin(a,b,c)
1	max = 0; min = 0;
2	if (a > b)
3	max = a; min = b;
4	else
5	max = b; min = a;
	end
6	if max < c
7	max = c;
	end
8	if min > c
9	min = c;
	end
10	fprintf(‘max = %d\n’,max);
	fprintf(‘min = %d\n’,min);

Table 2

All the DUPs of MaxMin program.

Variable	DUPs
a	<a,0,2>, <a,0,3>, <a,0,5>
b	<b,0,2>, <b,0,3>, <b,0,5>
c	<c,0,6>, <c,0,7>, <c,0,8>, <c,0,9>
max	<max,1,6>, <max,3,6>, <max,5,6>, <max,1,10>, <max,3,10>, <max,5,10>, <max,7,10>
min	<min,1,8>, <min,3,8>, <min,5,8>, <min,1,10>, <min,3,10>, <min,5,10>, <max,9,10>

Table 3

The measurement of branch distance.

Branch Predicate (E)	Branch Distance f(E)
Boolean	if true, then 0 else K
a = b	if (a-b) = 0, then 0 else K
a ≠ b	if abs(a-b) ≠ 0, then 0 else K
a > b	if (b − a) < 0, then 0 else (b − a) + K
a ≥ b	if (b − a) ≤ 0, then 0 else (b − a) + K
a < b	if (a − b) < 0, then 0 else (a − b) + K
a ≤ b	if (a − b) ≤ 0, then 0 else (a − b) + K
E1 and E2	f(E1) + f(E2)
E1||E2	min(f(E1), f(E2))

Table 4

CEC2017 benchmark functions.

Type	No.	Functions	Optimal
Unimodal Functions	F1	Shifted and Rotated Bent Cigar Function	100
	F2	Shifted and Rotated Sum of Different Power Function	200
	F3	Shifted and Rotated Zakharov Function	300
Simple Multimodal Functions	F4	Shifted and Rotated Rosenbrock’s Function	400
	F5	Shifted and Rotated Rastrigin’s Function	500
	F6	Shifted and Rotated Expanded Scaffer’s F6 Function	600
	F7	Shifted and Rotated Lunacek Bi_Rastrigin’s Function	700
	F8	Shifted and Rotated Non-Continuous Rastrigin’s Function	800
	F9	Shifted and Rotated Levy’s Function	900
	F10	Shifted and Rotated Schwefel’s Function	1000
Hybrid Functions	F11	Hybrid Function 1 (N = 3)	1100
	F12	Hybrid Function 2 (N = 3)	1200
	F13	Hybrid Function 3 (N = 3)	1300
	F14	Hybrid Function 4 (N = 4)	1400
	F15	Hybrid Function 5 (N = 4)	1500
	F16	Hybrid Function 6 (N = 4)	1600
	F17	Hybrid Function 7 (N = 5)	1700
	F18	Hybrid Function 8 (N = 5)	1800
	F19	Hybrid Function 9 (N = 5)	1900
	F20	Hybrid Function 10 (N = 6)	2000
Composition Functions	F21	Composition Function 1 (N = 3)	2100
	F22	Composition Function 2 (N = 3)	2200
	F23	Composition Function 3 (N = 4)	2300
	F24	Composition Function 4 (N = 4)	2400
	F25	Composition Function 5 (N = 5)	2500
	F26	Composition Function 6 (N = 5)	2600
	F27	Composition Function 7 (N = 6)	2700
	F28	Composition Function 8 (N = 6)	2800
	F29	Composition Function 9 (N = 3)	2900
	F30	Composition Function 10 (N = 3)	3000
Search Range: [−100,100]D.

Table 5

Benchmark programs.

No.	Programs	Vars	LOC	DUPs	Description
Pro1	Triangle classifier(Kumar et al. [23]; Dai et al. [40];Ghiduk and Rokaya [41]; Ghiduk et al. [42]; Mann et al. [43]; Huang et al. [44];Nosrati et al. [45])	3	34	23	Find the triangle type
Pro2	Middle(Kumar et al. [23]; Dai et al. [40];Ghiduk and Rokaya [41]; Nosrati et al. [45])	4	32	19	Find the middle value
Pro3	Power(Ghiduk and Rokaya [41])	2	37	24	Find the value of xy
Pro4	Quadratic equation(Kumar et al. [23]; Mann et al. [43];Nosrati et al. [45])	5	37	20	Find the roots of a quadratic equation
Pro5	Day of the calendar(Kumar et al. [23]; Nosrati et al. [45])	10	121	80	Find the day on a given date
Pro6	Prime(Kumar et al. [23]; Ghiduk et al. [42])	2	27	12	Count the prime numbers in the range from 1 to N
Pro7	Maxmin(Ghiduk et al. [42]; Mann et al. [43])	3	12	14	Find the maximum between three integer numbers
Pro8	Factorial of a number(Kumar et al. [23]; Dai et al. [40]; Ghiduk et al. [42]; Mann et al. [43])	2	21	8	Compute the factorial of the number N
Pro9	Remainder(Ghiduk and Rokaya [41]; Ghiduk et al. [42])	2	49	11	Calculate the remainder of an integer division
Pro10	Gcd(Dai et al. [40]; Nosrati et al. [45])	2	28	17	Greatest common denominator

Table 6

Experimental results of CEC2017.

Function	Metric	SAO	LSAO	TSAO	ESAO
F1	Mean	2.8838e+03	3.5893e+03	2.9243e+03	2.1808e+03
	Std	2.8735e+03	3.0735e+03	2.8720e+03	1.9400e+03
	Best	1.9851e+02	2.1891e+02	1.1200e+02	1.3948e+02
	Worst	9.7546e+03	9.8348e+03	9.4786e+03	7.5738e+03
F2	Mean	2.0000e+02	2.0000e+02	2.0000e+02	2.0000e+02
	Std	1.8794e-04	1.5918e-04	1.6835e-04	8.2670e-05
	Best	2.0000e+02	2.0000e+02	2.0000e+02	2.0000e+02
	Worst	2.0000e+02	2.0000e+02	2.0000e+02	2.0000e+02
F3	Mean	3.1213e+02	3.1718e+02	3.2369e+02	3.0000e+02
	Std	5.4262e+01	5.2719e+01	8.6580e+01	4.2020e-06
	Best	3.0000e+02	3.0000e+02	3.0000e+02	3.0000e+02
	Worst	5.4267e+02	5.0494e+02	6.8085e+02	3.0000e+02
F4	Mean	4.0167e+02	4.0154e+02	4.0162e+02	4.0142e+02
	Std	4.6589e-01	7.0537e-01	4.4315e-01	7.5244e-01
	Best	4.0007e+02	4.0018e+02	4.0001e+02	4.0000e+02
	Worst	4.0255e+02	4.0229e+02	4.0239e+02	4.0210e+02
F5	Mean	5.1231e+02	5.8655e+02	5.1506e+02	5.1098e+02
	Std	5.7092e+00	4.1475e+01	6.9932e+00	3.9172e+00
	Best	5.0298e+02	5.2487e+02	5.0497e+02	5.0298e+02
	Worst	5.2487e+02	6.3332e+02	5.3208e+02	5.1990e+02
F6	Mean	6.0018e+02	6.0017e+02	6.0001e+02	6.0018e+02
	Std	6.0400e-01	5.1520e-01	2.9900e-02	4.1540e-01
	Best	6.0000e+02	6.0000e+02	6.0000e+02	6.0000e+02
	Worst	6.0250e+02	6.0178e+02	6.0012e+02	6.0117e+02
F7	Mean	7.2035e+02	7.1889e+02	7.1832e+02	7.1757e+02
	Std	3.7896e+00	5.0815e+00	3.5304e+00	2.8822e+00
	Best	7.1492e+02	7.1395e+02	7.1297e+02	7.1319e+02
	Worst	7.2957e+02	7.3460e+02	7.2594e+02	7.2422e+02
F8	Mean	8.1307e+02	8.1220e+02	8.1423e+02	8.1139e+02
	Std	6.4333e+00	7.8739e+00	5.9716e+00	5.3485e+00
	Best	8.0497e+02	8.0298e+02	8.0398e+02	8.0398e+02
	Worst	8.2786e+02	8.3840e+02	8.2487e+02	8.2189e+02
F9	Mean	9.0019e+02	9.0005e+02	9.0012e+02	9.0009e+02
	Std	4.5050e-01	1.3970e-01	3.9800e-01	1.0250e-01
	Best	9.0000e+02	9.0000e+02	9.0000e+02	9.0000e+02
	Worst	9.0182e+02	9.0045e+02	9.0173e+02	9.0045e+02
F10	Mean	1.7232e+03	1.9469e+03	1.7256e+03	1.6341e+03
	Std	3.5244e+02	4.1822e+02	3.3911e+02	3.1409e+02
	Best	1.1520e+03	1.3589e+03	1.3571e+03	1.1652e+03
	Worst	2.5576e+03	3.0793e+03	2.0254e+03	2.6096e+03
F11	Mean	1.1131e+03	1.1075e+03	1.1091e+03	1.1060e+03
	Std	2.5405e+01	5.5516e+00	1.2218e+01	5.1684e+00
	Best	1.1011e+03	1.1011e+03	1.1001e+03	1.1010e+03
	Worst	1.2055e+03	1.1235e+03	1.1570e+03	1.1216e+03
F12	Mean	2.6643e+03	9.2308e+03	1.0071e+04	8.6273e+03
	Std	1.1293e+04	4.4503e+03	6.1923e+03	5.3537e+03
	Best	2.1941e+03	3.8534e+03	1.8397e+03	1.5131e+03
	Worst	1.1121e+03	9.1931e+03	2.0161e+04	1.6573e+04
F13	Mean	1.0051e+04	7.4375e+03	9.5826e+03	6.3146e+03
	Std	9.1258e+03	5.4902e+03	6.4092e+03	2.3601e+03
	Best	1.5436e+03	3.1988e+03	1.4970e+03	1.8146e+03
	Worst	3.2049e+04	3.0280e+04	2.2447e+04	1.0954e+04
F14	Mean	9.8897e+03	4.7003e+03	7.8600e+03	4.6778e+03
	Std	8.0890e+03	5.8138e+02	7.8145e+03	3.9882e+02
	Best	1.5587e+03	2.9521e+03	1.4073e+03	3.9489e+03
	Worst	2.6385e+04	5.8350e+03	2.5670e+04	5.0047e+03
F15	Mean	5.1916e+03	3.9928e+03	4.6334e+03	3.9206e+03
	Std	4.6240e+03	6.8281e+02	4.5343e+03	5.5543e+02
	Best	1.5373e+03	2.2890e+03	1.5008e+03	2.7321e+03
	Worst	1.6674e+04	5.6597e+03	1.7040e+04	5.3228e+03
F16	Mean	1.7209e+03	1.6941e+03	1.7215e+03	1.6855e+03
	Std	1.1628e+02	1.0791e+02	1.1705e+02	1.0086e+02
	Best	1.6003e+03	1.6001e+03	1.6008e+03	1.6007e+03
	Worst	1.9859e+03	2.0199e+03	2.0130e+03	1.9496e+03
F17	Mean	1.7773e+03	1.7666e+03	1.7422e+03	1.7601e+03
	Std	8.9786e+01	3.8142e+01	4.0268e+01	4.5652e+01
	Best	1.7056e+03	1.7178e+03	1.7014e+03	1.7055e+03
	Worst	2.1044e+03	1.8391e+03	1.8644e+03	1.8575e+03
F18	Mean	2.2579e+04	1.8003e+04	1.6107e+04	1.9030e+04
	Std	1.0930e+04	9.3451e+03	1.1095e+04	9.6132e+03
	Best	6.1044e+03	3.9917e+03	2.8840e+03	2.1164e+03
	Worst	4.0462e+04	3.4453e+04	4.5914e+04	3.6956e+04
F19	Mean	1.1856e+04	9.8147e+03	1.0252e+04	9.4846e+03
	Std	1.0694e+04	4.2013e+03	9.5693e+03	3.7013e+03
	Best	1.9716e+03	2.0110e+03	1.9535e+03	2.5970e+03
	Worst	3.2677e+04	1.8292e+04	3.2721e+04	1.5758e+04
F20	Mean	2.1140e+03	2.1347e+03	2.0855e+03	2.0868e+03
	Std	7.0005e+01	1.3905e+02	6.4245e+01	6.5539e+01
	Best	2.0093e+03	2.0140e+03	2.0140e+03	2.0013e+03
	Worst	2.2598e+03	2.5603e+03	2.2575e+03	2.2430e+03
F21	Mean	2.3189e+03	2.3189e+03	2.3169e+03	2.3167e+03
	Std	8.1155e+00	7.2364e+00	6.9654e+00	6.7482e+00
	Best	2.3051e+03	2.3078e+03	2.2000e+03	2.3075e+03
	Worst	2.3358e+03	2.3336e+03	2.3329e+03	2.3328e+03
F22	Mean	2.3012e+03	2.4120e+03	2.3132e+03	2.3012e+03
	Std	1.6243e+00	4.9558e+02	5.4939e+01	1.4927e+00
	Best	2.3000e+03	2.3000e+03	2.3000e+03	2.3000e+03
	Worst	2.3062e+03	4.5174e+03	2.5465e+03	2.3056e+03
F23	Mean	2.636.9e+03	2.638.7e+03	2.6381e+03	2.6273e+03
	Std	3.1018e+01	2.1981e+01	2.7907e+01	2.1393e+01
	Best	2.6119e+03	2.6090e+03	2.6159e+03	2.6077e+03
	Worst	2.7566e+03	2.6856e+03	2.7188e+03	2.6929e+03
F24	Mean	2.7474e+03	2.5263e+03	2.7476e+03	2.5000e+03
	Std	8.9146e+00	8.1051e+01	1.0067e+01	2.5555e-13
	Best	2.7375e+03	2.5000e+03	2.7339e+03	2.5000e+03
	Worst	2.7697e+03	2.7772e+03	2.7739e+03	2.5000e+03
F25	Mean	2.9396e+03	2.9310e+03	2.9346e+03	2.9244e+03
	Std	2.1320e+01	2.2498e+01	2.0848e+01	1.9654e+01
	Best	2.8986e+03	2.8996e+03	2.8979e+03	2.8978e+03
	Worst	2.951.0e+03	2.9461e+03	2.9490e+03	2.9451e+03
F26	Mean	3.0174e+03	3.0640e+03	3.0572e+03	2.9459e+03
	Std	2.9363e+02	4.8441e+02	3.4645e+02	7.1609e+01
	Best	2.8000e+03	2.8000e+03	2.8000e+03	2.8000e+03
	Worst	3.8864e+03	4.2146e+03	4.2239e+03	3.0863e+03
F27	Mean	3.1028e+03	3.1128e+03	3.1015e+03	3.0988e+03
	Std	2.5806e+01	3.0913e+01	1.7680e+01	5.9756e+00
	Best	3.0897e+03	3.0895e+03	3.0895e+03	3.0890e+03
	Worst	3.1785e+03	3.1835e+03	3.1560e+03	3.1081e+03
F28	Mean	3.3216e+03	3.2534e+03	3.3258e+03	3.2349e+03
	Std	1.7874e+02	1.5066e+02	1.5239e+02	1.4727e+02
	Best	3.1000e+03	3.1000e+03	3.1000e+03	3.1000e+03
	Worst	3.7318e+03	3.4451e+03	3.4118e+03	3.4118e+03
F29	Mean	3.225.0e+03	3.2429e+06	3.2210e+03	3.2076e+03
	Std	5.1616e+01	6.1662e+01	4.4626e+01	4.6825e+01
	Best	3.1377e+03	3.1528e+03	3.1540e+03	3.1313e+03
	Worst	3.3379e+03	3.4101e+03	3.3348e+03	3.3125e+03
F30	Mean	3.7576e+05	6.7465e+03	3.6878e+05	6.7445e+03
	Std	5.3720e+05	2.6091e+03	5.2938e+05	2.4434e+03
	Best	5.3615e+03	4.3295e+03	5.1979e+03	4.0339e+03
	Worst	1.4167e+06	1.6979e+04	1.6033e+06	1.1824e+04

Table 7

Experimental results of benchmark programs.

No.	AvgGen		AvgTime
	SAO	ESAO	SAO	ESAO
Pro1	43.35	37.95	0.6157	0.5790
Pro2	5.25	4.50	0.5405	0.4850
Pro3	32.50	20.20	1.6327	0.2818
Pro4	46.55	36.70	0.6871	0.4983
Pro5	17.20	10.40	0.1431	0.0176
Pro6	14.50	11.90	0.1703	0.0824
Pro7	4.40	2.50	0.4389	0.2886
Pro8	6.40	4.20	0.1802	0.1562
Pro9	58.45	21.40	2.9895	0.4113
Pro10	6.90	5.50	0.1664	0.1629

References

1. Aleti, A.; Moser, I.; Grunske, L. Analysing the fitness landscape of search-based software testing problems. Autom. Softw. Eng.; 2017; 24, pp. 603-621. [DOI: https://dx.doi.org/10.1007/s10515-016-0197-7]

2. Pachouly, J.; Ahirrao, S.; Kotecha, K.; Selvachandran, G.; Abraham, A. A systematic literature review on software defect prediction using artificial intelligence: Datasets, data validation methods, approaches, and tools. Eng. Appl. Artif. Intell.; 2022; 111, 104773. [DOI: https://dx.doi.org/10.1016/j.engappai.2022.104773]

3. Durelli, V.H.S.; Durelli, R.S.; Borges, S.S.; Endo, A.T.; Eler, M.M.; Dias, D.R.C.; Guimarães, M.P. Machine learning applied to software testing: A systematic mapping study. IEEE Trans. Reliab.; 2019; 68, pp. 1189-1212. [DOI: https://dx.doi.org/10.1109/TR.2019.2892517]

4. Meng, X.; Shujuan, J.; Rongcun, W. Systematic review of test data generation based on intelligent optimization algorithm. Comput. Eng. Appl.; 2018; 54, pp. 16-23.

5. Myers, G.J.; Sandler, C.; Badgett, T. The Art of Software Testing; John Wiley & Sons: Hoboken, NJ, USA, 2011.

6. Jamil, M.A.; Arif, M.; Abubakar, N.S.A.; Ahmad, A. Software testing techniques: A literature review. Proceedings of the 2016 6th International Conference on Information and Communication Technology for the Muslim World (ICT4M); Jakarta, Indonesia, 22–24 November 2016; [DOI: https://dx.doi.org/10.1109/ICT4M.2016.045]

7. Cao, S.; Sun, X.; Bo, L.; Wei, Y.; Li, B. Bgnn4vd: Constructing bidirectional graph neural-network for vulnerability detection. Inf. Softw. Technol.; 2021; 136, 106576. [DOI: https://dx.doi.org/10.1016/j.infsof.2021.106576]

8. Liu, Z.; Qian, P.; Yang, J.; Liu, L.; Xu, X.; He, Q.; Zhang, X. Rethinking smart contract fuzzing: Fuzzing with invocation ordering and important branch revisiting. IEEE Trans. Inf. Forensics Secur.; 2023; 18, pp. 1237-1251. [DOI: https://dx.doi.org/10.1109/TIFS.2023.3237370]

9. Chaim, M.L.; Baral, K.; Offutt, J.; Neto, M.C.; Araujo, R.P.A.D. On subsumption relationships in data flow testing. Softw. Test. Verif. Reliab.; 2023; 33, e1843. [DOI: https://dx.doi.org/10.1002/stvr.1843]

10. Panichella, A.; Kifetew, F.M.; Tonella, P. Automated test case generation as a many-objective optimisation problem with dynamic selection of the targets. IEEE Trans. Softw. Eng.; 2017; 44, pp. 122-158. [DOI: https://dx.doi.org/10.1109/TSE.2017.2663435]

11. Khoshniat, N.; Jamarani, A.; Ahmadzadeh, A.; Haghi Kashani, M.; Mahdipour, E. Nature-inspired metaheuristic methods in software testing. Soft Comput.; 2024; 28, pp. 1503-1544. [DOI: https://dx.doi.org/10.1007/s00500-023-08382-8]

12. McMinn, P. Search-based software test data generation: A survey. Softw. Test. Verif. Reliab.; 2004; 14, pp. 105-156. [DOI: https://dx.doi.org/10.1002/stvr.294]

13. Sahin, O.; Akay, B. A discrete dynamic artificial bee colony with hyper-scout for RESTful web service API test suite generation. Appl. Soft Comput.; 2021; 104, 107246. [DOI: https://dx.doi.org/10.1016/j.asoc.2021.107246]

14. Liu, C.; Wu, L.; Xiao, W.; Li, G.; Xu, D.; Guo, J.; Li, W. An improved heuristic mechanism ant colony optimization algorithm for solving path planning. Knowl.-Based Syst.; 2023; 271, 110540. [DOI: https://dx.doi.org/10.1016/j.knosys.2023.110540]

15. Gao, L.; Bai, S.; Liu, M.; Li, F. Automated test case generation for path coverage using hierarchical surrogate-assisted differential evolution. Appl. Soft Comput.; 2024; 158, 111586. [DOI: https://dx.doi.org/10.1016/j.asoc.2024.111586]

16. Esnaashari, M.; Damia, A.H. Automation of software test data generation using genetic algorithm and reinforcement learning. Expert Syst. Appl.; 2021; 183, 115446. [DOI: https://dx.doi.org/10.1016/j.eswa.2021.115446]

17. Jatana, N.; Suri, B. Particle swarm and genetic algorithm applied to mutation testing for test data generation: A comparative evaluation. J. King Saud Univ.-Comput. Inf. Sci.; 2020; 32, pp. 514-521. [DOI: https://dx.doi.org/10.1016/j.jksuci.2019.05.004]

18. Girgis, M.R. Automatic test data generation for data flow testing using a genetic algorithm. J. Univers. Comput. Sci.; 2005; 11, pp. 898-915.

19. Nayak, N.; Mohapatra, D.P. Automatic test data generation for data flow testing using particle swarm optimization. International Conference on Contemporary Computing; Springer: Berlin/Heidelberg, Germany, 2010; pp. 1-12.

20. Singla, S.; Kumar, D.; Rai, H.M.; Singla, P. A hybrid PSO approach to automate test data generation for data flow coverage with dominance concepts. Int. J. Adv. Sci. Technol.; 2011; 37, pp. 15-26.

21. Vivanti, M.; Mis, A.; Gorla, A.; Fraser, G. Search-based data-flow test generation. Proceedings of the 2013 IEEE 24th International Symposium on Software Reliability Engineering (ISSRE); Pasadena, CA, USA, 4–7 November 2013; pp. 370-379. [DOI: https://dx.doi.org/10.1109/ISSRE.2013.6698890]

22. Varshney, S.; Mehrotra, M. Search-based test data generator for data-flow dependencies using dominance concepts, branch distance and elitism. Arab. J. Sci. Eng.; 2016; 41, pp. 853-881. [DOI: https://dx.doi.org/10.1007/s13369-015-1921-5]

23. Kumar, S.; Yadav, D.K.; Khan, D.A. An accelerating PSO algorithm based test data generator for data-flow dependencies using dominance concepts. Int. J. Syst. Assur. Eng. Manag.; 2017; 8, pp. 1534-1552. [DOI: https://dx.doi.org/10.1007/s13198-017-0626-4]

24. Rauf, A. Data flow testing of UML state machine using ant colony algorithm (ACO). Int. J. Comput. Sci. Netw. Secur.; 2017; 17, pp. 40-44.

25. Jiang, S.; Chen, J.; Zhang, Y.; Qian, J.; Wang, R.; Xue, M. Evolutionary approach to generating test data for data flow test. IET Softw.; 2018; 12, pp. 318-323. [DOI: https://dx.doi.org/10.1049/iet-sen.2018.5197]

26. Varshney, S.; Mehrotra, M. A hybrid particle swarm optimization and differential evolution based test data generation algorithm for data-flow coverage using neighbourhood search strategy. Informatica; 2018; 42, pp. 417-438. [DOI: https://dx.doi.org/10.31449/inf.v42i3.1497]

27. Sheoran, S.; Mittal, N.; Gelbukh, A. Artificial bee colony algorithm in data flow testing for optimal test suite generation. Int. J. Syst. Assur. Eng. Manag.; 2020; 11, pp. 340-349. [DOI: https://dx.doi.org/10.1007/s13198-019-00862-1]

28. Ghiduk, A.S.; Girgis, M.R.; Hassan, E.; Aljahdali, S. Automatic PSO based path generation technique for data flow coverage. Intell. Autom. Soft Comput.; 2021; 29, pp. 147-164. [DOI: https://dx.doi.org/10.32604/iasc.2021.015708]

29. Ji, S.; Zhu, S.; Zhang, P.; Dong, H.; Yu, J. Test-case generation for data flow testing of smart contracts based on improved genetic algorithm. IEEE Trans. Reliab.; 2022; 72, pp. 358-371. [DOI: https://dx.doi.org/10.1109/TR.2022.3173025]

30. Deng, L.; Liu, S. Snow ablation optimizer: A novel metaheuristic technique for numerical optimization and engineering design. Expert Syst. Appl.; 2023; 225, 120069. [DOI: https://dx.doi.org/10.1016/j.eswa.2023.120069]

31. Jia, H.; You, F.; Wu, D.; Rao, H.; Wu, H.; Abualigah, L. Improved snow ablation optimizer with heat transfer and condensation strategy for global optimization problem. J. Comput. Des. Eng.; 2023; 10, pp. 2177-2199. [DOI: https://dx.doi.org/10.1093/jcde/qwad096]

32. Abd Elaziz, M.; Al-qaness, M.A.; Ibrahim, R.A.; Ewees, A.A.; Shrahili, M. Multilevel thresholding aerial image segmentation using comprehensive learning-based snow ablation optimizer with double attractors. Egypt. Inform. J.; 2024; 27, 100500. [DOI: https://dx.doi.org/10.1016/j.eij.2024.100500]

33. Zhou, C.; Li, S.; Xie, C.; Yuan, P.; Long, X. MISAO: A multi-strategy improved snow ablation optimizer for unmanned aerial vehicle path planning. Mathematics; 2024; 12, 2870. [DOI: https://dx.doi.org/10.3390/math12182870]

34. Zhang, X.; Ye, J.; Ma, S.; Gao, L.; Huang, H.; Xie, Q. MISAO: Ultra-short-term photovoltaic power forecasting with multi-strategy improved snow ablation optimizer. Appl. Sci.; 2024; 14, 7297. [DOI: https://dx.doi.org/10.3390/app14167297]

35. Xiao, Y.; Cui, H.; Hussien, A.G.; Hashim, F.A. Msao: A multi-strategy boosted snow ablation optimizer for global optimization and real-world engineering applications. Adv. Eng. Inform.; 2024; 61, 102464. [DOI: https://dx.doi.org/10.1016/j.aei.2024.102464]

36. Zhong, R.; Zhang, C.; Yu, J. Improved snow ablation optimization for multilevel threshold image segmentation. Clust. Comput.; 2024; 28, 16. [DOI: https://dx.doi.org/10.1007/s10586-024-04785-w]

37. Su, T.; Wu, K.; Miao, W.; Pu, G.; He, J.; Chen, Y.; Su, Z. A survey on data-flow testing. ACM Comput. Surv.; 2017; 50, pp. 1-35. [DOI: https://dx.doi.org/10.1145/3020266]

38. Li, Q.; Liu, S.Y.; Yang, X.S. Influence of initialization on the performance of metaheuristic optimizers. Appl. Soft Comput.; 2020; 91, 106193. [DOI: https://dx.doi.org/10.1016/j.asoc.2020.106193]

39. Sahoo, R.R.; Ray, M. PSO based test case generation for critical path using improved combined fitness function. J. King Saud Univ.-Comput. Inf. Sci.; 2020; 32, pp. 479-490. [DOI: https://dx.doi.org/10.1016/j.jksuci.2019.09.010]

40. Dai, X.; Gong, W.; Gu, Q. Automated test case generation based on differential evolution with node branch archive. Comput. Ind. Eng.; 2021; 156, 107290. [DOI: https://dx.doi.org/10.1016/j.cie.2021.107290]

41. Ghiduk, A.S.; Rokaya, M. An empirical evaluation of the subtlety of the data-flow based higher-order mutants. J. Theor. Appl. Inf. Technol.; 2019; 97, pp. 4061-4074.

42. Ghiduk, A.S.; Girgis, M.R.; Shehata, M.H. Reducing the cost of higher-order mutation testing. Arab. J. Sci. Eng.; 2018; 43, pp. 7473-7486. [DOI: https://dx.doi.org/10.1007/s13369-018-3108-3]

43. Mann, M.; Tomar, P.; Sangwan, O.P. Bio-inspired metaheuristics: Evolving and prioritizing software test data. Appl. Intell.; 2018; 48, pp. 687-702. [DOI: https://dx.doi.org/10.1007/s10489-017-1003-3]

44. Huang, R.; Chen, H.; Sun, W.; Towey, D. Candidate test set reduction for adaptive random testing: An overheads reduction technique. Sci. Comput. Program.; 2022; 214, 102730. [DOI: https://dx.doi.org/10.1016/j.scico.2021.102730]

45. Nosrati, M.; Haghighi, H.; Asl, M.V. Using likely invariants for test data generation. J. Syst. Softw.; 2020; 164, 110549. [DOI: https://dx.doi.org/10.1016/j.jss.2020.110549]