Regression Test Case Optimization (RTCO) Techniques Analysis

Abstract: This research paper reviews different metaheuristic techniques used in Regression Test Case Optimization (RTCO) by various researchers. The research also emphases on the most used objective function for analyzing the efficiency and effectiveness of the technique used. This research has used a theoretical approach to examine different metaheuristic techniques used in RTCO. The Genetic algorithm is the chief technique used in the dominion of RTCO followed by swarm particle optimization, bee colony optimization and firefly optimization. It was also noted that Average Percentage of Fault Detected (APFD) was the most used metrics to assess the effectiveness of metaheuristic techniques in RTCO.

The objective of this study is to present a concise review of

Introduction

1. Introduction Regression testing is an important activity of maintenance phase. The modifications or changes made to a software and its effect on already existing functionality can be determined by performing regression testing. The prime motive to expedite regression testing is to ratify that no new error are generated into earlier tested code as the consequence of successful regression testing in an error. The Test case that identifies an error is considered to be of great importance. Regression testing helps in checking that changes assimilated do not lead to unwanted errors and behavior in the code.
2. Substantial difficulty in regression testing is the choice of a weighty subclass of test cases. Research carried out in [5] and [6] identifies most prevalent criteria’s in the domain of regression test case optimization.  Different features of test cases like coverage details at several levels of granularities, test history, fault detection rate, association between modules of the software, execution cost, common execution patterns, input-output correlation, etc. are used in regression testing. These are some of the traditional ways of regression test cases optimization. However, consequences of ineffective testing can be overall low quality product giving inaccurate and unreliable results henceforth unhappy users leading to direct or indirect financial losses.

Being important part of software development, it is essential to associate regression-testing   techniques and incorporate other efficient algorithm so as to make regression test case optimization more effective.

Nature-inspired algorithms are present set of unique problem-solving methodologies or approaches that have drawn attention for their high effectiveness. Many researches have shown there interest in Metaheuristic search techniques for regression test case optimization. This technique stand as a high-level structure, which exploit heuristic to find solution for problems at a practical computational amount.

This paper reviews different metaheuristic techniques used in regression test case optimization by various researchers. This research also focuses on the most used objective function to analyses the effectiveness of the different techniques implemented.

1. Review of Literature

Patrick [15] explained and estimated various different metaheuristic techniques and reflected their properties in the respect to test data generation. They stated that fitness function plays an imperative role in determining the effectiveness of techniques. Kaur and Bhatt [9] made regression testing effective by using hybrid particle swarm optimization (HPSO). They achieved hybridization by combining particle swarm optimization and genetic algorithm. Mittal and Sangwan [11] focussed on the problem to select the fitness metric for the purpose of determining the most appropriate search technique for regression testing. Alsariera et al.  [1] benchmarked bat-inspired testing strategy (BTS) for test case optimization. Gladston te al. [8] proposed an immune prioritization algorithm (IPA) for the test case optimization. Their technique is evaluated by using three fitness metrics namely APSC, APDC, APBC.

Sahoo et al. [19] proposed a methodology for the test case generation and optimization using Firefly Algorithm (FA). Fister et al. [7] discussed various Chaos based Firefly Algorithm (CFA), their taxonomy and chaotic maps used frequently in CFA by various authors. Shingal and Gaur [20] improvised firefly algorithm with bresenham line code algorithm for test case prioritization. Solanki et al. [23] suggested a modified Ant Colony Optimization (m-ACO) technique and performed its comparative study with other meta-heuristic techniques. Singhal et al. [22] compared the two nature inspired algorithms – Bee Colony Optimization (BCO) and Ant Colony Optimization (ACO). Various metrics as AE, ASR, AETR were used to compared the techniques.

Prakashet al. [16] proposed a relevancy based metric that is defined on the basis of historical execution of the test cases. Bhasin [3] presented a fitness function that is determined by the cost and priority of the test suite under consideration. Bhasin and Gera [2] accomplished the task of the test case optimization by proposing time aware minimization technique used in [3].Zhang et al. [26] gave Regression Mutation Testing (ReMT) for speeding up mutation testing.Li et al. [10] evaluated five search techniques three greedy algorithms and two metaheuristic techniques. Their study also focuses on choice of the fitness metrics. Sihan [21] in the study performed simulation experiments on five algorithms to compare them. For comparing the techniques Average Percentage Requirement Coverage (APRC) was used as the criteria.

Briand et al. [4] enhanced the test case in object oriented system by merging genetic algorithm with inter-class coupling. Nagar et al. [12 ] used cuckoo search algorithm to put forward the test case selection and prioritization algorithm. Error detection in the minimum time by the test case was considered as the criteria. Srivatsava et al. [24] optimized test case path by altering firefly algorithm by introducing guidance matrix for graph traversal and defining applicable objective function. Panda and Sarangi [14] compared Artificial Bee Colony (ABC), Differential Evolution (DE) and genetic algorithm (GA). Their results stated that ABC performs better than the others.

Raju [18] used three different methods for test case prioritization -test case weights, clustering techniques and genetic algorithm. This research also compared their effectiveness on the basis of APFD metrics. Raamesh [17] integrated the use of the genetic algorithm, bird flocking algorithm and feature selection to prioritize the test cases. Pachauri [13] reviewed and compared various metaheuristic techniques for the branch coverage.

2. Objectives

The principal objective of this study is to identify various metaheuristic algorithm and the most promising fitness function used by various researchers to determine the effectiveness of these algorithms in regression test case optimization.

3. Research Methodology

Theoretical approach is assimilated to achieve the objective of this research. The theoretical approach comprises of the research papers from diverse databases like IEEE Explore, ACM Digital Library, Springer, Elsevier and online journals. These databases cover significant journals, workshops and conference proceedings for the regression testing. This paper analysed twenty different research papers, one book [25] and three Ph.D. theses related to regression test case optimization using metaheuristic optimization.

4. Metaheuristic Optimization Algorithms

Algorithms are categorized into two subgroups – deterministic and stochastic. Maximum number of conventional algorithms are deterministic. A Stochastic algorithm is further classified into two divisions: heuristic and metaheuristic. Heuristic means to find out by trial and errors. Worthy solutions to a hard optimization problem can be found in a practical amount of time, but it does not assure that optimal solutions will be extended. A Heuristic algorithm is further advanced into metaheuristic algorithm [25]. At this point meta means “higher level”, these algorithms are mostly superior to simple heuristics. But, the new trend inclines to name all stochastic algorithms with the local search randomization as metaheuristic. Randomization delivers a decent way to move from local search to a global search. Hence, mostly all metaheuristic algorithms are suitable to perform global optimization [25].

Two major constituents of any metaheuristic algorithms are diversification and intensification.  Diversification allows the solutions to explore the search space at global level. Intensification is to confine the search in the local region by exploiting the information to find an appropriate solution. Amalgamation of these two main modules will ensure that global optimality is reachable.

Nature inspired metaheuristic algorithms [25] constituted the most used algorithms to the optimization problems.  Swarm Intelligence (SI) and bio-inspired algorithm received much attention in the recent years. SI algorithm such as ant colony optimization, bee colony optimization, cuckoo search, swarm optimization and firefly algorithm have many leads over conventional algorithm. There are many popular, nature-inspired algorithms used for the optimization.

Simulated annealing is simplest stochastic algorithm designed and influences by the properties of the metal annealing process. Genetic Algorithm (GA) is an evolutionary algorithm. It has three key operators: crossover, mutation and selection. Differential Evolution (DE) is to an extent strongly similar to the traditional mutation operator in their search pattern. Ant algorithm copies foraging behavior of ants which incorporates pheromones chemical messenger as an pointer to a problem solution. Bees colony can be divided into three groups: scouts, onlooker and employed bees. Employee and scout bees carries out randomization. Honey relates to the selection process. There is no crossover here. Particle swarm optimization (PSO) relates to swarm behavior, viz. bird and fish schooling in nature. Firefly Algorithm (FA), related to flashing patterns and behavior of fireflies. Cuckoo search is a latest addition to nature- inspired metaheuristic algorithms. It relates to brood parasitism in some cuckoo species. The Bat Algorithm (BA), inspired by echolocation behavior of microbats. Another musical- inspired algorithm is Harmony Search (HS) algorithm. It is metaheuristic algorithm and not swarm- intelligence based. The flower pollination algorithm was influenced by pollination process in flowering plants  (FPA) [25].

5. Results and Analysis

This paper recognized various metaheuristic optimization techniques used with traditional techniques for test case optimization in regression testing. As it is evident from the TABLE I it can be stated that the metaheuristic techniques are being used extensively for test case optimization.

Table 1: Regression Test Case Optimization Using Metaheuristic Techniques

Authors	Metaheuristic Technique used	Algorithm Proposed	Metric/ Fitness function used
Patrick (2016). [15]	Hill Climbing, Evolutionary Algorithm, Swarm Intelligence.	–	Mutation Score, Independent Path Coverage
Kaur and Bhatt (2011). [9]	Particle Swarm Optimization and Genetic Algorithm.	Hybrid particle Swarm Optimization Algorithm (HPSO)	Average Percentage of Fault Detected (APFD)
Mittal and Sangwan(2015). [11]	Artificial bee Colony, Genetic Algorithm, Ant Colony Optimization, Bee Colony Optimization, Particle Swarm Optimization.	–	APFD
Alsariera et al. (2016). [1]	Bat Algorithm	Bat-inspired Testing Strategy (BTS)
Gladston te al. (2016). [8]	Immune Genetic Algorithm (IGA)	Immune Prioritization Algorithm (IPA)	Average Percentage Statement Covered (APSC), Average Percentage Decision Covered (APDC), Average Percentage Block Covered (APBC).
Sahoo et al. (2016). [19]	Firefly Algorithm (FA)	Proposed
Fister et al. (2015). [7]	Chaos- based Firefly Algorithm (CFA)
Shingal and Gaur (2016). [20]	Firefly Algorithm	Firefly Algorithm with Bresenham line code.
Solanki et al. (2016). [23]	m-ACO (Modified Ant Colony Optimization), Genetic Algorithm (GA), Bee Colony Optimization (BCO), Ant Colony Optimization (ACO).	APFD, Percentage of Test Suite Required for Complete Fault Coverage (PTR).
Singhal et al. (2016). [22]	Ant Colony Optimization (ACO) and Bee Colony Optimization (BCO)	Average Efficiency (AE), Average Percentage of Test Suite Size Reduction (ASR), Percent Average Execution Time Reduction (AETR).
Prakash et al. (2015). [16]	Random Forest and Genetic Algorithm.
Bhasin (2014). [3]	Genetic Algorithm	APFD
Bhasin and Gera (2013). [2]	Artificial intelligence approach called Genetic Algorithm	Fitness function proposed
Zhang et al. (2012). [26]	Regression Mutation Testing (ReMT)	Mutation specific Test Prioritization (MTP).
Li et al. (2007).  [10]	Hill Climbing and Genetic Algorithm compared with variants of greedy algorithm.	APBC, APDC, APSC.
Sihan (2010). [21]	Hill Climbing and Genetic Algorithm compared with variants of greedy algorithm	Average percentage Requirement Coverage (APRC).
Briand et al. (2002) [4]	Genetic Algorithm clubbed with inter-class coupling measurement.
Nagar et al. (2015). [12]	Cuckoo search algorithm.	Test case selection and prioritization algorithm proposed using cuckoo search.	Fitness value of best test case sequence/ route.
Srivatsava et al. (2013). [24]	Firefly algorithm using state transition diagram and control flow graph.	Guidance matrix
Panda and Sarangi (2013). [14]	Binary Genetic Algorithm (BGA), Differential Evolution, Artificial Bee Colony Optimization, used with control flow graph.	Proposed algorithm	APFD, The Goal-Question-Metric Approach (GQM)
Raju (2015). [18]	Genetic algorithm and clustering technique.
Raamesh 2014. [17]	Feature selection, Birds flocking algorithm and Genetic algorithm	Minimum Redundancy Maximum Relevance feature selection algorithm	APFD, APSC, APBC, Average Percentage of Path Covered (APFC), Average Percentage of Fault Detected based on Cost Metric (APFDc)
Pachauri 2012. [13]	Genetic Algorithm, Binary Particle Swarm Optimization, Quantum Particle Swarm, Clonal Selection Algorithm.	Fitness function used and Normalized Branch Distance used.

Various metaheuristic techniques that have gained popularity in regression test case optimization are as follows: hill climbing [10, 15, 21], evolutionary algorithm [15],  swarm intelligence[15] and its variants like (particle swarm optimization [9], hybrid particle swarm optimization [9], particle swarm optimization [11], binary particle swarm optimization and quantum particle swarm [13]), genetic algorithm [2, 3, 4, 10,  11, 13, 16, 17, 18, 21, 23] and its variant (immune genetic algorithm [8], binary genetic algorithm [14]), bee colony [11, 22, 23]and its variants (artificial bee colony [11, 14]), ant colony optimization [11, 22, 23 ] and its variants (modified ant colony optimization [23]), Bat inspired testing strategy [1], firefly algorithm [19, 20, 24] and its variants (chaos based firefly algorithm [7]), random forest technique[16], mutation testing [26], cuckoo search algorithm [12], feature selection and bird flocking algorithm [17], clonal selection algorithm [13]. After referring to the Table 1 It is apparent that authors have accomplished  to design and find alternatives of the metaheuristic techniques.

Genetic algorithm is the leading technique used in the dominion of the test case optimization trailed by swarm particle optimization, bee colony optimization and firefly optimization.

The effectiveness of the metaheuristic techniques and their variants has been measured by different fitness function and metrics. As it is evident from Table 1 that APFD metrics dominates its presence followed by APSC, APDC, APBC.

6. Conclusion and Future

The application of the metaheuristic algorithm to solve regression test case optimization problem belongs to relatively new field. The review in this area shows a positive incline towards the introduction of metaheuristic techniques in the regression test case optimization. This can be viewed as a resolution of optimization problem that was difficult to result satisfactorily before. The study identified that metaheuristic techniques have been augmented with traditional ways of test case optimization to give effective results in lesser time. The study also caters to identify some of the fitness functions that can determine the effectiveness of various metaheuristic techniques used by the author or proposed by the same. The future work shall propose a hybrid metaheuristic technique for the regression test case optimization.

References

1. Alsariera YA, Nasser AB, Zamli KZ. Benchmarking of Bat-inspired Interaction Testing Strategy. IJCSIE. 2016 June;7(1).
2. Bhasin H, Gera A. Novel Time Aware Regression Testing Technique. International Journal on Computer Science and Engineering. 2013 May 1;5(5):430.
3. Bhasin H. Cost-priority cognizant regression testing. ACM SIGSOFT Software Engineering Notes. 2014 Jun 4;39(3):1-7.
4. Briand LC, Feng J, Labiche Y. Using genetic algorithms and coupling measures to devise optimal integration test orders. InProceedings of the 14th international conference on Software engineering and knowledge engineering 2002 Jul 15 (pp. 43-50). ACM.
5. Dhareula P, Ganpati A. Prevalent criteria’s in regression test case selection techniques: An exploratory study. InGreen Computing and Internet of Things (ICGCIoT), 2015 International Conference on 2015 Oct 8 (pp. 871-876). IEEE.
6. Dhareula P, Ganpati A. Identification of attributes for test case reusability in regression test selection techniques. InComputing for Sustainable Global Development (INDIACom), 2016 3rd International Conference on 2016 Mar 16 (pp. 1144-1147). IEEE.
7. Fister I, Perc M, Kamal SM. A review of chaos-based firefly algorithms: perspectives and research challenges. Applied Mathematics and Computation. 2015 Feb 1;252:155-65.
8. Gladston A, Nehemiah K, Narayanasamy P, Kannan A. Test case prioritization for regression testing using immune operator. The International Arab Journal of Information Technology. 2016 Nov 1;13(6).
9. Kaur A, Bhatt D. Hybrid particle swarm optimization for regression testing. International Journal on Computer Science and Engineering. 2011 May;3(5):1815-24.
10. Li Z, Harman M, Hierons RM. Search algorithms for regression test case prioritization. IEEE Transactions on software Engineering. 2007 Apr;33(4).
11. Mittal S, Sangwan OP. Metaheuristic Based Approach to Regression Testing. International Journal of Computer Science and Information Technologies. 2015; 6(3): 2597-2605.
12. Nagar R, Kumar A, Singh GP, Kumar S. Test case selection and prioritization using cuckoos search algorithm. InFuturistic Trends on Computational Analysis and Knowledge Management (ABLAZE), 2015 International Conference on 2015 Feb 25 (pp. 283-288). IEEE.
13. Pachauri A. Software test data generation using metaheuristic search based techniques. http://shodhganga.inflibnet.ac.in/handle/10603/22181. 2012.
14. Panda MA, Sarangi PP. Performance Analysis of Test Data Generation for Path Coverage Based Testing using Three Meta-Heuristic Algorithms. International Journal of Computer Science and Informatics. 2013;3(2):34-41.
15. Patrick M. Metaheuristic Optimisation and Mutation-Driven Test Data Generation. In Computational Intelligence and Quantitative Software Engineering 2016 (pp. 89-115). Springer International Publishing.
16. Prakash K, Prasad SU, Krishna DG. Recommendation and Regression Test Suite Optimization Using Heuristic Algorithms. In Proceedings of the 8th India Software Engineering Conference 2015 Feb 18 (pp. 202-203). ACM.
17. Raamesh L. Integrated multi objective test case prioritization system. http://ir.inflibnet.ac.in:8080/jspui/handle/10603/38627. 2014.
18. Raju S. Multi factor approach for effective Regression testing using test case Optimization. http://ir.inflibnet.ac.in:8080/jspui/handle/10603/38627. 2015;
19. Sahoo RK, Mohapatra DP, Patra MR. A Firefly Algorithm Based Approach for Automated Generation and Optimization of Test Cases. International Journal of Computer Science and Engineering. 2016 Aug;4(8): 2347-2693.
20. Shingal RS, Gaur P. Test Case Prioritization for Regression Testing Based on Firefly Algorithm. International Research Journal of Computers and Engineering. 2016 Dec; 4(1).
21. Sihan L. A simulation study on some search algorithms for regression test case prioritization. InProceedings of the 2010 10th International Conference on Quality Software, IEEE Computer Society 2010.
22. Singhal S, Gupta S, Suri B, Panda S. Multi-deterministic Prioritization of Regression Test Suite Compared: ACO and BCO. In Advanced Computing and Communication Technologies 2016 (pp. 187-194). Springer Singapore.
23. Solanki K, Singh Y, Dalal S. Experimental analysis of m-ACO technique for regression testing. Indian Journal of Science and Technology. 2016 Aug 18;9(30).
24. Srivatsava PR, Mallikarjun B, Yang XS. Optimal test sequence generation using firefly algorithm. Swarm and Evolutionary Computation. 2013 Feb 28;8:44-53.
25. Yang XS. Nature-inspired optimization algorithms. Elsevier; 2014 Feb 17.
26. Zhang L, Marinov D, Zhang L, Khurshid S. Regression mutation testing. In Proceedings of the 2012 International Symposium on Software Testing and Analysis 2012 Jul 15 (pp. 331-341). ACM.