Automated Software Testing with Metaheuristic Techniques

by Eugenia Díaz, Raquel Blanco and Javier Tuya

Software testing is an expensive, difficult and time-consuming process. The use of techniques for automating the generation of software test cases is very important as it can reduce the time and cost of this process. We have used two methods for automatic generation of test cases: Tabu Search and Scatter Search. These methods had not been previously used for this task.

Software testing is the process of executing a program in order to find errors in its source code. It has been estimated that software testing involves more than 50 per cent of software development. This cost can be significantly reduced with the use of automated generators.

Previous works in automatic structural testing used the metaheuristic techniques Simulated Annealing and mainly Genetic Algorithms, but there exist other metaheuristic techniques that have been used successfully in other engineering fields. In our work, we have automated the test case generation by means of two metaheuristic search techniques called Tabu Search and Scatter Search, which had not been used for this kind of problems yet. We have developed two different algorithms that explore the program control flow graph (whose nodes represent statements and whose edges represent the flow of control between statements) to determine the test cases that attain the desired code coverage. Both source code instrumentation and the test case generation are fully automated.

Test Case Generation using Tabu Search
Tabu Search is a metaheuristic search technique based on that of the next k neighbours, while maintaining a tabu list (memory) that avoids repeating the search in the same area of the solution space.

The algorithm use the control flow graph, which stores relevant information (for example the best tests and their costs). The goal is to automatically obtain branch coverage.

One of the main characteristics of Tabu Search is that it has short-term memory and long-term memory, along with their corresponding handling strategies. In our approach, short-term memory stores the tests that have been the best for the goal node and long-term memory stores the worst tests during the search process. In our approach, short-term memory stores the tests that have been the best for the goal node and long-term memory stores the worst tests during the search process.

In each iteration, the goal of the algorithm is to cover a node that has not been covered yet. Once we have established the sub-goal node, n neighbours are generated starting from the best-known test for its parent node. Once the tests candidates are generated, we verify whether these are tabu tests, in which case they are rejected. If a candidate is not tabu (not in memory), it is executed with the program under test and if it has been the best test known for some of the nodes that it has reached, it is stored as the best test for the node.

Test Case Generation using Scatter Search
Scatter Search is an evolutionary method which works on a solutions set, called Reference Set. The solutions in this set are combined in order to obtain better new solutions than the original ones. The reference set stores the better solutions that have been generated so far. To determine if a solution is good, its quality and its diversity are considered.

The test case generator based on Scatter Search use the control flow graph in order to determine the covered branches. Each node has a solution set and the algorithm will try to make the sets as diverse as possible, using a diversity function to generate solutions that can cover different branches of the program.
The goal of the algorithm is to obtain the maximum branch coverage, ie, they must be solutions that allow covering all the nodes of the control flow graph. Since these solutions are stored in the nodes, our goal is, therefore, that all the nodes have at least one element in their solutions set.

Results
We present the results obtained with the well known classify triangle benchmark, whose control flow graph can be seen in Figure 1.

Figure 1: Triangle control flow graph.	Figure 2: accumulated coverage in per cent versus generated test cases.

The graph in Figure 2 represents the number of test cases generated for out two algorithms (Tabu Search and Scatter Search) in comparison with a random algorithm. The range used for input variables is 10 bits. The vertical axis represents the accumulative percentage of branch coverage and the horizontal axis the number of test cases generated in logarithmic scale.
The random algorithm obtains the worst result and it is not able to achieve full coverage. Both Tabu Search and Scattter Search algorithms reach 100 % coverage and they generate less test cases than random algorithm. The Tabu Search algorithm gives the best result.

This work was funded by the Department of Science and Technology (Spain) under the National Program for Research, Development and Innovation, project TIC2001-1143-C03-03 (ARGO).

Please contact:
Eugenia Díaz, Raquel Blanco, Javier Tuya
University of Oviedo, Spain
Tel: +34 985 18 24 97
E-mail: {eugenia, rblanco, tuya}lsi.uniovi.es