A Greedy Particle Swarm Optimization Strategy for T-way Software Testing

INTRODUCTION

In the complex software systems, such as those used in industrial applications, there is a large number of possible test cases due to the different input parameters the system may accept. These parameters and their interactions with each other must be considered to ensure the accurate detection of different software bugs (Qu et al., 2007). However, exhaustive testing is often impossible due to time and resource limitations (Lei et al., 2008). As a result, there still exists a need for a more intelligent mechanism to ensure that such interaction coverage is approached systematically with a minimum number of test cases. For solving such a problem, combinatorial strategy used which is a method or mechanism for selecting test cases using a combination of test input parameters (Beizer, 1990).

Due to the complexity of search space in the combinatorial interaction problems, different techniques have been used to deal with this search process. Artificial intelligent techniques have been regarded as being especially adequate search strategies, since they are able to deal with search for optimization (Afzal et al., 2009). Two of the well known algorithms are Genetic Algorithm (GA) and Ant Colony Algorithm (ACA). However, other heuristic search techniques have started to compete with GA and ACA such as Particle Swarm Optimization (PSO) in the context of algorithm simplicity and performance (Wang et al., 2011; Marinakis and Marinaki, 2010a; Marinakis and Marinaki, 2010b; Pant et al., 2008). Recent literature showed that PSO outperforms GA and ACA in different cases of optimization problems (Windisch et al., 2007).

Motivating by those researches, this paper a new test suite generation strategy for t-way combinatorial testing (whereby, t indicates the interaction strength) based on Particle Swarm Optimization, namely PSTG. PSTG complements our earlier work on pairwise testing (Ahmed and Zamli, 2011) to investigate the use of PSO for testing when t = 2. In addition to its impressive results against other strategies in case of test case size, PSTG generates one test case at a time.

Particle swarm optimization: Particle swarm optimization is a mechanism that tries to manipulate a certain number of candidate solutions at once (Chettih et al., 2011; Qasem and Shamsuddin, 2010). The whole population is called swarm and the solutions are called particles (Jie et al., 2008; Poli, 2008). Each solution represented by a particle that works in the search space to find a better position or solution of the problem. As a popular optimization method, PSO has been used during the last years since it showed a number of advantages in comparison to other optimization methods. As compared to other artificial intelligent optimization methods, PSO has few parameters to regulate and can be easily merged with the environment that needs optimization. In additions, PSO does not need the calculation of derivatives that the knowledge of good solutions is kept by all particles and that particle share the information with others in the swarm (Ganjali, 2008; Yap et al., 2011; Padhy, 2009; Sutha and Kamaraj, 2008).

With the starting of the optimization process in PSO, each particle has a random position and updates its position iteratively in the hope of finding better solutions. This is done with each particle by holding the essential information about its movement (Marinakis and Marinaki, 2010a; Marinaki et al., 2010). These information including its position currently (x_i), its velocity currently (v_i), personal best or the position that it has achieved so far which is denoted by (pBest_i) of particle i, local best or the position that it has achieved in its neighborhood which is denoted by (lBest_i) and the global best or the position it has achieved in the whole swarm which is denoted by (gBest_i). The manipulation of the particles around the search space is restricted by a certain update and positions rule as follows (Windisch et al., 2007; Ganjali, 2008):

(1)

(2)

where, t is iteration number or time, d is the dimension, j the particle index, w is the inertia weight, r and r’ are two random factors which are two random real numbers between 0 and 1 and c, c’ are acceleration coefficients that are adjusting the weight between components. Pursuant to such updated rule, each particle update its velocity for better movement around the search space and the new velocity used to find the new position of the particles depending on a cost factor that controls this movement.

A strategy for t-way test suite generation: In test suite generation, we are mainly dealing with parameters and values and we want to find optimal test cases that cover most of the interaction elements. We introduce each particle as a vector. Since each test case has (D) parameters, as a result, the particle or the vector is (D) dimension also. We can illustrate this vector by the notation: X_j = (X_j,1, X_j,2,X_j,d………, X_j,D).

Referring to Fig. 1, our test suite generation strategy will start by receiving the parameters and values. The strategy immediately manipulates all parameters’ values. Then, the algorithm will generate all t-way combinations named Ps that contains all t-interaction element combinations of parameters’ values that are not been covered yet (step 4).


Fig. 1:	A test case generation procedure for PSO

When a test case is found for Ts that can cover more t-interaction elements, the strategy removes the t-combinations which are covered by this test case, from Ps list. The strategy continues its running until Ps list get empty (step 6). The strategy randomly initializes each particle in the swarm search space with its associated parameter values (step 7). It compares each particle which represents a test case, with the list of t-interaction element PS (steps 9 and 20).

EXPERIMENTAL RESULTS

To justify and evaluate the efficiency of our strategy in term of the generated test suite size, we made comparison with some existing strategies and tools based on well-known benchmarks. These strategies are IPOG with its tool FireEye (Lei et al., 2007), WHITCH, Jenny, TConfig and TVG. The comparison aims to study the growth in the generated test suite size in terms of strength of coverage (t). We adopt two different set of experiment conducted by Lei et al. (2007) and Bryce et al. (2005).

All strategies are employed within our environment which consisted of a desktop PC with Windows XP, 2.8 GHz Core 2 Due CPU, 2 GB of RAM and JDK 1.5 installed.

Table 1 and 2 showed the results obtained for the two set of experiments. Each table represents the smallest test suit size obtained. The cells were marked NS (not supported) indicate that the tool cannot generate the test case for a specific configuration and the cells were marked NA (not available) indicate that the results were unavailable.

Referring to the above tables, we note that our PSTG strategy scales well against other strategies in most cases. Referring to Table 1, PSTG produces optimal sizes in case of t equals to 2 and 4 while in case of t equals to 3 and 5 it can compete the other strategies except the optimal one.

Table 1:	Comparison with existing algorithms

NS: Not supported, NA: Not available

Table 2:	P and V constants (10, 2) but t varied up to 6

NS: Not supported, NA: Not available

WHITCH appeared to produce satisfactory results in case of small value of t (maximum of 4) and not producing results beyond that. Similarly, TConfig and TVG do not produce any specific results for more than one day of running in case of t>4. Jenny produce a reasonable result in case of t equals to 5 while it cannot produce results in case of t equals to 6.

With the multiple domain (variable) configurations in Table 2, also PSTG scales well against others in most cases. In most of the tests PSTG can produce the most optimum; however, when it is not the most optimum in some cases, it still can compete with most of the other none optimum strategies.

CONCLUSION

We have proposed and illustrated our efficient strategy, namely, PSTG for t-way combinatorial test case generation using a novel approach by combining the greedy fashion of particle swarm optimization technique with the software test case generation to gain near optimal solution. The main concern of our algorithm is optimization in term of size of the resulting test sets. From the experiment results, we can state that no single strategy can claim absolute dominance over other strategies for all configuration since it is an NP-complete problem (Lei et al., 2007; Lei and Tai, 1998). PSTG performs better than other strategies in term of size in most cases but it cannot be the most optimal strategy for all configuration sets. We are currently developing our PSTG strategy to release the beta version of the PSTG tool.

ACKNOWLEDGMENT

This research is partially funded by the generous fundamental grants-“Investigating t-way Test Data Reduction Strategy Using Particle Swarm Optimization Technique” from Ministry of Higher Education (MOHE) and the USM Research University grants-“Development of variable-strength interaction testing strategy for t-way Test Data generation ” and the short term grant-“Development of interaction testing tool for pairwise coverage with seeding and constraints”. The first author, Bestoun S. Ahmed, is a recipient of the USM fellowship.