Regression Test Suite Minimization Using Modified Artificial Ecosystem Optimization Algorithm

Introduction

Software development life cycle comprises of various stages including an inevitable one called maintenance. Regression testing is conducted during maintenance and consumes almost 50-60% of total software development cost. Apart from it timely delivery of software products within budget in every maintenance activity is still a big challenge for industry. Hence, there exists a scope of improvement to reduce time and cost by improving the regression testing process (Augustsson, 2012).

Regression test case optimization is an effective way to overcome such issues.  There exist three different types of regression test suite optimization such as: Minimization, Selection and Prioritization (Yoo & Harman, 2010). Test suite minimization works by reducing the size of the original test suite that satisfies some test adequacy criteria. Test case selection focuses on selecting a subset of test cases from the original test suite. Test case prioritization on the other hand doesn’t reduce the size of the original test suite rather it reorders the existing test cases in some order so that they achieve some test adequacy criteria in decreasing/increasing order. In this paper author focuses on Test Case Minimization technique. To better understand the problem first we present a formal description of problem statement. “Software is a collection of programs  with test suites  respectively. For a program  the test suite  consists of a set of reusable test cases  . F denotes the K faults exist in   which can be covered by . We derive a minimized subset of test suite    such as :  where L < M. All the faults F must be covered from the test suite  to achieve the desired fault coverage.”

Software products are evolutionary in nature and hence the test suite size keeps growing with every maintenance cycle. So, retest whole test suite after maintenance becomes very costly and time consuming. Regression test suite minimization is an effective solution to reduce time and effort required during regression testing. But the test case minimization becomes complex and transform to a NP hard problem, due to the presence of redundant test cases in existing test suite.

Literature revealed that various heuristic and Meta heuristic approaches have been applied to solve the test case minimization problems. But the scope of optimization still exists. Various nature inspired optimization algorithm such as Bat Search algorithm, Harris Hawk Optimization algorithm, Crow Search algorithm etc. (Kaur et al., 2017; Kaur at al., 2020; Chaudhary et al., 2019) have been utilized for regression test case optimization but there exist a room for improvement.

In this paper a new approach for Test Suite Minimization using Hybrid Artificial Ecosystem Optimization algorithm has been proposed.  The main contribution of the paper is as follows: 

• Proposed Test Case Minimization approach using Artificial Ecosystem Optimization (AEO) algorithm.
• Updated the performance of proposed approach by changing exploration and exploitation process of AEO.
• Rigorous statistical analysis have been conducted which reflects the superiority of proposed approach for test case Minimization over Bat Search algorithm, , Harris Hawk Optimization algorithm, Crow Search algorithm etc. (Kaur et al., 2017; Kaur et al., 2020; Chaudhary et al., 2019).

The structure of this paper is as follows. Section-2 briefly discusses the related works in the same area. Section-3 describes the proposed approach. Section-4 discloses the experimental setup and formulate the research questions. Section-5 report the results and answer the research questions formulated. Section 6 discusses the threat to validity and finally, section-6 concludes the paper with future extension of the proposed work.

Related Work

Test Suite Minimization became important if the test suites are not maintained properly, this may result in enormous test execution cost and diminish the regression testing benefits. Various researchers have conducted various studies in test suite minimization and reduction.

Test suite size plays an important role in maintain testing cost, to reduce the test suite size a heuristic approach has been proposed  which identify and eliminate the redundant & obsolete test cases based on different degree of essentialness for data flow testing (Harrold et al., 1993). To find out an optimal subset of test suite an another heuristic approach based on GRE (Greedy Redundant and Essential) has been proposed (Chen & Lau, 1998a). Lee and Chung proposed another approach for selecting optimal subset of test suite by utilizing enhanced zero–one optimal path set selection method (Chung & Lee, 1997; Lee & Chung, 2000). Chen and Lau performed a simulation study on above discussed approaches and concluded that no single approach performs better than other two approaches in all the cases and solve the test suite minimization problem using divide and conquer approach for finding minimal and optimal representative test subsets (Chen & Lau, 1998b, 2003).  A bi-criteria decision making model for test suite minimization considering  test suite size and  error detection rate as two criteria has been proposed (Black et al., 2004).  Sprenkle et al. compared the applied approaches (Harrold et al., 1993; Black et al., 2004) for user-session-based testing of different web applications (Sprenkle et al., 2005). Jeffery et al. modified the Harrold, Gupta and Jean, 1993 approach keeping selective redundant test cases and claimed better performance (Jeffrey & Gupta, 2005; Jeffrey & Gupta, 2007).

Few researchers continued to explore the performance of existing heuristic approaches such as greedy approach, Harrold, GRE and integer linear programming approaches on Java programs (Harrold et al., 1993; Littlewood & Sofer, 1987)(Black et al., 2004; Chen & Lau, 1998a).In their empirical study authors have analyzed the differences and similarity of all the selected approaches (Zhang et al., 2011).To perform early estimation of errors and reduce the testing time and effort, Gupta et al. proposed an approach by utilizing decision table generated from software requirement specification and claimed approx. 33% of saving in cost and time (Gupta et al., 2014). A greedy based approach for coverage based test suite reduction has been proposed and claimed the better code coverage in comparison to Harrold and Black approach  (Harris & Raju, 2015). Khan et al. taken multiple test adequacy criteria’s statement, branch , path adequacy,  requirement and code coverage with minimum size test suite and claimed good performance (Khan et al., 2017). A fault coverage based test suite optimization approach inspired from Harrold approach has been proposed and this approach has further been compared against Greedy, Additional Greedy, HGS, and Enhanced HGS approaches and claimed better accuracy (Agrawal et al., 2019).          

Regression test suite minimization, being an NP problem, various researcher explored its solutions using search-based approaches. Yoo and Harman  proposed a pareto optimal test case selection approach taking coverage and cost as a multi objective criteria (Yoo & Harman, 2007). Maia et al. proposed multi objective approach for test case selection problem by utilizing multi objective genetic algorithm and claimed better performance than random search approach (Loiola & Maia, 2009). Yoo and Harman further utilized pareto optimal multi-objective optimization to solve test suite minimization (Yoo & Harman, 2010). A hybrid technique by combining Bee Colony optimization and genetic algorithm has been proposed, in this approach crossover parameter have been borrowed from genetic algorithm to generate and update the new solutions (Suri et al., 2011). You et al. proposed a genetic algorithm based time aware test suite reduction approach which removes the redundant test cases and minimize the total test case execution time (You & Lu, 2012). A fuzzy logic based approach has been proposed for multi objective test suite minimization problem (Haider et al., 2012), and also performed an empirical analysis (Haider et al., 2013) on computational and fuzzy based approach for safe reduction of test suites. The analysis claimed that the fuzzy based approach is safer then computational approaches for test suite minimization (Haider et al., 2013). Ahmad utilized cuckoo search optimization technique to solve configuration-aware structural testing the results was compared and claimed better then GA, PSO and other similar approaches (Ahmed, 2015). Turner et al. utilized NSGA II approach for test suite minimization on Mockito framework (Drake et al., 2016). Gupta et al. proposed multi objective test suite optimization approach for detection and localization of test cases (Gupta et al., 2020).

The approaches discussed above claim that both heuristic and metaheuristic-based approaches have been proposed to address the test suite minimization problem but still a scope of optimization exists. In this paper first authors have applied original AEO approach for minimizing test case in test suite. In order to improve performance a modified approach is also proposed using Artificial Ecosystem Optimization. The proposed approach is further utilized for test suite minimization.

Proposed Approach: Test Case Minimization Using AEO AND MAEO

Nature is ocean of knowledge and inspiration; it’s an excellent example is ecological system. Nature intelligently maintains a perfect balance in ecological system. Zhao et al.(Weiguo et al., 2019) took inspiration from nature and proposed an effective nature inspired algorithm called  artificial ecosystem-based optimization (AEO) algorithm. AEO mimics the production, consumption, and decomposition behaviour of living creatures (Weiguo et al., 2019). The main aim of every meta-heuristics is to maintain balance between exploration and exploitation during their search process (Yang, n.d.; Kumar et al., 2018). In AEO, production, consumption, and decomposition behaviour is considered as operators (Weiguo et al., 2019). The role of production operator is to maintain the balance among exploitation and exploration behaviour while the consumption operator is utilized for to improve the exploration and at last decomposition operator is utilized to promote the exploitation behaviour. In this paper authors have proposed modified AEO to improvise the exploitation and exploration process by utilizing Equilibrium optimizer (Faramarzi et al., 2020) equations in AEO algorithm for test case minimization problem. Authors have used same problem statement as discussed in introduction section to explain the algorithmic process.  

In order to achieve optimal solution AEO and its modified version follows certain rules (Weiguo et al., 2019):

1. The producer, consumer, and decomposer are three types of organisms included in the ecosystem.
2. As an individual, there is only one producer as well as only one decomposer in the population.
3. Rest of the population is treated as consumers, which are categorized as a carnivore, an herbivore, or an omnivore with equal probability.
4. The energy level of individuals is evaluated by cost function. Higher the value of cost function reflects higher energy of the individual for minimization problem.
5. Production:

The producer is considered as the worst individual of the ecological system, which may produce food energy from natural resources such as water, sunlight & carbon dioxide. The decomposer is the one who provides nutrition to the producer. The producer will be updated or generated from the random value between lower and upper limits of the search space (test suites)  and the decomposer .

The mathematical representation of production operator in AEO is as follows:

where      represents production operator,  represents random test suite,  represents best test suite so far or decomposer,  is a linear weight coefficient between  to maintain balance between random test suite   and decomposer  for updating  (Production operator), r and r1 are random numbers ranges between  ,  denotes the current iteration and TI denotes total iterations. 

In AEO, the linear weight coefficient decreases linearly from 1 to 0 using equation 2, while the proposed MAEO uses exponential function to decrease the value of  from 1 to 0 over the iterations. As shown in figure1 the exploitation and exploration will ranges 70% and 30 %. 

1. Consumption

The consumption operator is performed by all the consumers. Each consumer may eat either a randomly selected lower energy consumer or a producer or both.

In AEO, Levy flight is considered as a mathematical operator to perform random walk-in order to explore the search space. In AEO, Levy flight is proposed as a consumption factor which is a simple free random walk. Each Consumer may use this consumption factor for hunting their food and there are various consumption approaches adopted by different varieties of consumers.

The mathematical representation of consumption operator in AEO is as follows:

1. Herbivore: Herbivore consumer eats only the producer.

1. Carnivore: Carnivore consumer eats only randomly chosen consumer having a high energy level.

1. Omnivore: Omnivore consumers can eat both either a producer or a consumer having a higher energy level.

(7)

and

1. Decomposition

The decomposition is most important operator and very essential process to maintain the functioning of an ecosystem as well as generates required nutrients for producer to help them in their growth. In the process of decomposition, when each individual of the population dies, the decomposer will break down chemically or decay its remains.

Here D (decomposition factor), e and h (weight coefficient) are three main parameters to spread the decomposer to each individual.  

The mathematical representation of consumption operator in AEO is as follows:

In AEO, decomposition balance exploitation behaviour by using equations 8,9,10,11. In MAEO, authors have utilized equations from Equilibrium optimizer (Faramarzi et al., 2020).   

The mathematical representation of decomposition operator in MAEO is as follows:

Generate random vectors of   random number vector of size [1- Dim] ranges between . , GP=0.5 to better maintain exploitation and exploration. The

In Eq. 17 first part of the equation reflects the decomposer represents the best solution so far in this iteration the second term represents the movement in the direction of random consumer which behave like direct search and third term is used for global exploration.

Experimental Setup

Experimental setup contributes significantly to evaluate the quality of any research, keeping this in consideration. We have conducted the research experiments to evaluate the performance of proposed algorithm. The algorithms and their control parameters considered for this study is as follows:

Table 1. Control parameter setting for Experimental Setup

The proposed algorithm as well as existing approach is evaluated on benchmarked dataset consisting of 12 versions of 5 open-source programs. These versions are retrieved from benchmarked Software Artifact Repository in regression testing (Do et al., 2005) under controlled experimental setting. Table 2 present summarized details of fault data.

Table 2. Dataset retrieved and their characteristics

The research questions and research hypothesis section discuss the research questions and hypothesis formed to evaluate the performance of proposed approach over the existing literature.

Research Questions

We have formulated following three research questions to compare the performance of proposed and existing approaches available in literature.

• Research Question 1: How is the performance of the MAEO algorithm as compared to the rest of the algorithm adopted for regression test case minimization problem?
• Research Question 2: Is there any effect of the subject program on the performance of the algorithms?
• Research Question 3: Does minimized test suite size effect fault revealing ability of algorithms?
• Research Question 4: How the computational cost of the MAEO algorithm is as compared to the rest of the algorithm adopted for regression test case minimization problem?

Research Hypothesis

The following hypothesis is designed to answer our research questions RQ1, RQ2 and RQ3 respectively:

Ho: Overall Performance of MAEO = Overall Performance of AEO = Overall Performance of BA= Overall Performance of HHO= Overall Performance of CSA

Ha: Overall Performance of MAEO ≠ Overall Performance of AEO ≠ Overall Performance of BA≠ Overall Performance of HHO ≠ Overall Performance of CSA

Ho: Algorithmic performance is independent of Subject Program

Ha: Algorithmic performance is dependent of Subject Program

Ho: RTM_5 = RTM_10 = RTM_15

Ha: RTM_5 ≠ RTM_10 ≠ RTM_15

Ho: Computational Cost of MAEO = Computational Cost of AEO = Computational Cost of BA= Computational Cost of HHO= Computational Cost of CSA

Ha: Computational Cost of MAEO ≠ Computational Cost of AEO ≠ Computational Cost of BA≠ Computational Cost of HHO ≠ Computational Cost of CSA

Results & Discussion

The experiment is conducted on subject programs under control parameters setting as shown in Table 2 and 3. In this experiment 15 runs of each algorithm is evaluated and means of these runs is utilized for performance evaluation. The values highlighted in bold are best from one or the other viewpoint. Table 3 present the means of dependent variable fault covered.

Table 3. Mean value of Faults Covered by proposed and adopted algorithms on different test suite sizes and subject programs

• Answer to Research Question 1:

The bold highlighted mean values reflect the fault coverage by different approaches on different subject programs and different minimized test suites. The highlighted means reflect that the proposed MAEO performs superior to other compared approaches. However, to confirm the claim of superiority a two- way ANOVA test is performed. The test results will show the effect of independent variables separately and in combination on dependent variable fault coverage. The tests are conducted in SPSS 20 tool and results are shown in Table 4 below.

Table 4. Two-way ANOVA of independent variables (Algorithm, Test suite size, subject program) and their combined effects on fault coverage at 95% Confidence Interval (α = 0.05)

All the significance values listed in column 6 of table 4 are lesser than α, so we can claim that all the approaches are statistically significant from each other. Further we have conducted the post –hoc test Tukey’s HSD at 95% confidence interval to perform a pair wise comparative analysis of approaches for fault coverage and the results are shown in table 5 below:

Table 5. Pair wise Comparison of different algorithms with respect to Fault Coverage at α = 0.05

The results observed from table 5 above shows that the pair wise algorithms is significantly different among others in term of their fault coverage as all the P-values are lesser than α. The result evident from homogenous subset of fault coverage of different algorithms in table 6 answers the Research question1 that proposed MAEO works better than other adopted Algorithms. The MAEO is superior then BA, HHO, CSA and AEO algorithm.

Table 6 Homogenous Subsets of Mean Fault Coverage of Algorithms

• Answer to Research Question 2

Table 3 and Figure 3 also help us to answer our Research Question 2. The figure 3 shows that except flex v4, nano v3 and xmlSec, there is a significant difference in the performance of algorithm. Table 3 also strengthen the claim of research question 2. So, we can conclude that a test suite size of 10 test cases is fair enough to perform regression testing without significantly affecting the fault detection effectiveness of RTM approaches.

• Answer to Research Question 3

Table 3, 7 and Figure 4 answer the 3^rd research question. It can be clearly seen from figure 4 that on 5 test suite size the algorithm performance is less as compare to 10 and 15 test suite size. It can be clearly seen from table 3and 7 that the algorithm performance varies with minimized size of test suite.

Table 7. Homogenous Subsets of Mean Fault Coverage of Test Suite Size

• Answer to Research Question 4

Table 8 and 9 answers the 4^th research question. Table 7 shows that the execution time of MAEO is lesser than AEO and HHO but it is taking much time in comparison to BA and CSA approach. Table 8 also confirm the claim and reject the null hypothesis.

So, it is clear from the table 6, 8 and 9 MAEO is providing better fault coverage as compare to other algorithms and computationally costlier as compare to CSA and BA but better than AEO and HHO.  

Table 8. Execution time of adopting algorithm on Regression Test Case Minimization

Table 9. Tukey HSD test on adopting algorithm for Regression Test Case Minimization

• Threats to Validity

Threats to external validity limit the capability to generalize the results beyond the experiment settings which can be reduced by taking the more realistic experimental setup. To overcome such issues, we have adopted benchmarked subject programs from SIR repository to perform the experiment.

Threat to internal validity mainly affects the independent variables such as algorithms, subject programs and minimized size of test suite in our case. To overcome this threat we adopted algorithms available in literature, similarly subject programs and minimized test suite size. Threat to construct validity reflects the degree up to that the experiment setting imitates the theory. In our case stochastic nature of Meta heuristic algorithms has been addressed by running our experiment 15 times with 500 iterations each to collect the results. Means of these 15 runs has been considered.

Conclusion

Regression test suite minimization is very challenging problem under software maintenance. In each maintenance cycle running all the test cases is costly affair.  To these issues this paper proposes an effective Modified Artificial Ecosystem optimization-based approach for test suite minimization. The proposed MAEO with updated formulation maintains optimal balance in exploration and exploitation for test case minimization problem. All the three research questions are answered through empirical study:

Answer to Research Question 1: The proposed Modified AEO based RTM approach is significantly superior to other adopted approaches.

Answer to Research Question 2: Yes, there is significant impact of subject program on performance of algorithms.

Answer to Research Question 3: Yes, there is impact of minimized test suite size on fault revealing ability of algorithms. The Test suite size of 10 test cases is sufficient in mostly cases.

Answer to Research Question 4: Yes, the computational cost of different metaheuristics is not same. Computational cost of MAEO is higher as compare to BA and CSA but lesser than AEO and HHO.

In future we will focus to generalize this approach to various domains of applications and generalize the approach to select the minimum required test case in suite automatically.