Keywords

1 Introduction

Every software system enters into the maintenance phase after release and keeps evolving continuously to provide the functionality required and to incorporate changing customer needs. Regression testing is an activity that tries to find any bugs introduced during the maintenance phase. One approach is to re-run all the test cases available from an earlier version of the software system [1]. But it is often too costly in terms of time and effort required to rerun all the test cases and is practically infeasible [2]. Two approaches have therefore emerged to optimize the regression test suite—Regression Test Case Selection and Prioritization [3]. The focus of this paper is on Regression Test Case Selection for re-execution to reduce the overall effort. Selecting the test cases would give the opportunity to optimize some performance goals like minimize execution time and maximize fault coverage.

The objective of this paper is to use two nature inspired metaheuristic techniques—Ant Colony Optimization and Hybrid Particle Swarm Optimization in testing for the purpose of minimizing the time required in regression testing by selecting the test cases and compare their performance. These two algorithms were empirically evaluated on flex object from the SIR repository and results of both the algorithms are compared on the basis of Fault Coverage and Execution Time. Results indicate that hybrid Particle Swarm Optimization outperforms the Ant Colony Optimization algorithm.

Rest of the paper is organized as follows: Sect. 2 briefly discusses the Regression Testing and states the Regression Test Case selection Problem. Sections 3 and 4 give an overview of the Ant Colony Optimization and Hybrid Particle Swarm Optimization algorithms respectively. Section 5 presents experimental design and results obtained results. Section 6 discusses the results. Finally Conclusion and Future work conclude the paper.

2 Problem Definition

2.1 Regression Testing

Primary purpose of Regression Testing is to increase the performance of software systems in terms of productivity and efficiency and to ensure quality assurance of applications [4]. The main objective of regression testing is to assure that the modification in one part of the software does not adversely affect the other parts of the software [5].

2.2 Regression Test Case Selection

Regression Test Case Selection is choosing a subset of test cases from the existing set of test cases that are necessary to validate the modified software. It reduces the testing cost by reducing the number of test cases to test the modified program [6, 7].

We consider following two criteria for the selection of test cases:

2.2.1 Fault Coverage

The aim is to maximize the Fault coverage. Let T = {TI, T2, …, Tn} indicates a test suite and F = {Fl,F2, …,Fm} indicates faults covered by a test case [8]. F(Ti) indicates a function which returns the subset of faults covered by a test case. Then, the fault coverage of a test suite is given by

$$ {\text{Fault Coverage}} = 100\,*\,\mathop \sum \limits_{t = 1}^{s} \mathop {\bigcup }\limits_{t = 1}^{s} \left\{ {F\left( {Ti} \right)} \right\}/k $$
(1)

where s reflects the selected test cases and k is the total number of selected test cases.

2.2.2 Execution Time

The execution time should be minimized. Execution time is defined as the total time required to execute a test [9]. The total Execution time of selected test cases is given by

$$ \mathop \sum \limits_{t = 1}^{s} Time $$
(2)

where s = selected test cases.

However test case selection could reduce the rate of detection of faults because the effectiveness of a test suite could decrease with the decrease in the size of a test suite.

3 Ant Colony Optimization for Optimizing Test Suites

Ants demonstrate complexity in their social behavior which has been attracting the attention of humans since a long time. Apparently the most marked behavior is the formation of ant streets. The most astonishing behavioral pattern demonstrated by ants is that they are able to find the shortest path from its nest to food source. It is proven that this behavior is the result of communication by a hormone called pheromone, an odorous chemical substance ants deposit and smell [10]. Computer scientists are simulating real ants in artificial ants and one such example is ant colony optimization.

Description of Algorithm

  1. 1.

    Test Cases are treated as a graph.

  2. 2.

    Each node on the graph has a specific score.

  3. 3.

    All ants start from the same place i.e. first node.

  4. 4.

    Ants deposit pheromone on the paths i.e. edges between two nodes.

  5. 5.

    Ants move on any node within 20 nodes from node number.

  6. 6.

    Ant follows route with [τ]*[η] probability.

  7. 7.

    η = (Number of faults)/(execution_time).

  8. 8.

    τ = τ + τ0 * ρ.

  9. 9.

    where ρ = 0.9.

  10. 10.

    τ0 = 1/Cnn; where Cnn is distance between current and next node.

  11. 11.

    Ants can only move forward.

  12. 12.

    Pheromone is appended on the paths.

4 Hybrid Particle Swarm Optimization for Test Case Selection

Particle Swarm Optimization is a population based memory using optimization technique. In PSO, each particle has its own position vector and velocity vector [11]. Position vector represents a possible solution to a problem and also a velocity vector. In testing, position means rank assigned to a test case in a test suite, whereas the velocity is the coverage or the execution time taken by a test case. Every particle stores its best position seen so far and also the best global position obtained through interaction with its neighbor particles. Particle Swarm Optimization algorithm guides its search by adjusting the velocity vector and Position of particles. Objective function is responsible for moving the particles. Particles which are very far from the optimal solution have higher velocity as compared to the particles that are very near to the optimal solution. Many variants of PSO with Genetic Algorithm, Gravitational Search Algorithm, Krill Herd and Cuckoo Search Algorithm etc. has been used by previous researchers to solve many optimization problems like frame selection in image processing, aircraft landing, feature selection in software defect prediction, quadratic assignment problem etc. [11,12,13,14,15,16,17,18,19].

This paper presents Hybrid PSO with Genetic Algorithm for test case selection. The algorithm uses Crossover and Mutation operator of genetic Algorithm and uses the Velocity Vector of PSO to guide the particles to Global Best Solution.

Description of Algorithm

  1. 1.

    Read Test cases from the text file and choose them randomly from the test suite.

  2. 2.

    Read execution time and statements covered by each test case.

  3. 3.

    Set MAX_VEL, MIN_VEL, MAX_LEN, MIN_LEN, TOTAL_PARTICLES and MAX_ITER.

  4. 4.

    Initialize each particle with zero Velocity and random Length. Each Particle contains set of Test Cases.

  5. 5.

    for i = 0 to MAX_ITER.

    1. i.

      Evaluate Fitness of Each Particle.

    2. ii.

      Use Bubble sort to sort Particles in the ascending order of their fitness level.

    3. iii.

      Set Velocity of Each Particle.

    4. iv.

      Update Each Particle on the basis of the changes required (Particle with bad fitness level have higher changes).

    5. v.

      Apply Mutation with 1, 2 and 5% rate on each particle.

    6. vi.

      Determine Global and Local Optimal Values.

5 Experimental Design and Results

Our Empirical study addresses the following research questions:

  • RQ1: Which algorithm is optimal for Regression Test Case selection?

  • RQ2: How much saving can we achieve by Regression Test Case selection for the benchmark problem?

We have used Flex—Fast Lexical Analyzer as the object under test which is available in open source from Software Artifact Infrastructure Repository [20]. It consists of 567 test cases and 19 seeded faults and execution time of each test case. Test cases have been numbered from T1 to T567 and faults have been numbered from f1 to f19. We ran both the algorithm on the input data set and collected results. We have considered bi-objective optimization as we want to maximize the fault coverage and minimize the execution time.

Table 1 above displays the results obtained upon execution of Ant Colony Optimization Algorithm on the input data set.

Table 1 Results of ant colony optimization
Full size table

Table 2 above display the best results obtained upon execution of Hybrid Particle Swarm Optimization algorithm for particle size 30 and mutation probabilities of 1%, 2% and 5% respectively. Particle size was kept constant at 30 in each run and algorithm was executed 30 times for 500 numbers of iterations to avoid any biases.

Table 2 Result of Hybrid PSO at mutation probability 1, 2 and 5%
Full size table

6 Discussion on Results

Table 3 above displays the combined results of both the algorithms. It can easily be seen from the statistics below that the results are quite satisfactory. In case of ACO less than 11% of test cases have been able to detect 84.2% of the faults and requires only 8.7% of total time including the running time of the algorithm. Hybrid PSO algorithm has been run for 30 particles and for 500 iterations in each run and the best of 30 runs has been taken as the observed result as follows for Mutation Probability 1%, 2% and 5% respectively. Hybrid PSO is able to detect 84.21% faults with only 0.7% of the total test cases which is a very cost efficient in comparison of ACO, though the running time of Hybrid PSO is much more than ACO. Although hundred percent of the faults have not been identified this is still a great achievement since the tradeoff is quite high.

Table 3 Combined Results of ACO and Hybrid PSO
Full size table

It is evident from the results that both the algorithms are optimal for regression test case selection which answers our research question 1. Hybrid PSO outperforms ACO in number of test cases selected but requires more time to run itself than ACO. We can save around 90% of the execution time through test case selection which answers our research question 2.

7 Conclusion and Future Scope

Primary focus of this paper was to present a comprehensive comparison of two meta-heuristic algorithms in the domain of software testing. Extensive experiments were conducted on the benchmark object flex and results obtained answered the research questions in study. This allows future researchers to conduct this kind of study for number of metaheuristic algorithms on number of benchmark problems.