M*: Multidisciplinar Multiobjective Metaheuristics

| TIN2008-06491-C04-01 Ministerio de Ciencia e Innovación (Spain)
| UMA - University of Málaga



list 26th Oct 2011. Incoming, coordination meeting, UMA (Málaga) [AGENDA]

list 11th Mar 2011. Incoming, coordination meeting, UC3M (Leganés) [AGENDA]

list [Engineering Optimization] Special issue on Multiobjective Metaheuristics for Multidisciplinary Engineering Applications

list 16th Jul 2010. Incoming, coordination meeting, UEX (Cáceres)

list [META'10] Special Session on Real Parameter Optimization: From Benchmarking To Real World Applications

list 5th Feb 2010. Coordination meeting, ULL (La Laguna)

list 14th Dec 2009. Coordination meeting, UMA (Málaga)

list 3rd Jul 2009. First Problem's Workshop, UMA (Málaga)

list 17th April 2009. Problem descriptions, instances, codes ... [+]

list 2nd April 2009. M* Web Site Launched




Automatic Test Case Generation


Software Testing is one of the most important phases of the software development process. The objective of software testing is to find errors in the software and to assure its correctness with a high probability. An automatic test case generator is a tool that proposes a set of test cases to be run on a given program in order to check if the program satifies the functional or non-functional requirements. This problem has received much attention from the Search-Based Software Engineering (SBSE) community [1] and Evolutionary Algorithms have been the preferred optimization technique in this field of research.

We can distinguish four large paradigms in search-based software testing that differ in the kind of information they use to generate the test cases and the final goal of the search: structural testing, functional testing (black box), grey-box testing, and non-functional testing. We focus here in structural testing, which has been the most popular.






In structural testing the test case generator uses the structural information of the program to guide the search of new test cases (for this reason it is also called white-box testing). Usually, this structural information is gathered from the control flow graph of the program. The final goal of this search is to find a set of test cases that execute every testable element under consideration (statements, branches, conditions, etc.). In order to compare the quality of different test case sets a coverage measure is usually defined. This measure is the ratio between the number of testable elements (branches for example) executed by te test case set and the total number of testable elements in the program. There exist several coverage measures defined in the literature, some examples are: statement coverage, branch coverage, and condition coverage. Increasing the coverage and decreasing the number of test cases of a set are the two main objectives in this problem.

The automatic test case generation is usually applied in the context of unit testing. In this case the element to test is a function with several parameters. A test case is a list of input values for the parameters of the function. The automatic test case generator breaks down the global objective into several partial objectives consisting of executing each particular testable element of the program. For example, if we use branch coverage we can identify six partial objectives in the fragment of the control flow graph shown above: to make branch condition one true, to make branch condition one false, etc. Then, each partial objective can be treated as an optimization problem in which the function to be minimized is a distance between the current input and an input satisfying the partial objective. The way in which this distance is computed depends on the branch condition (for details see [2]). In order to solve such minimization problems, global search techniques like evolutionary algorithms can be used.


Test programs

Here we publish the benchmark of test functions used in ref. [2]

Program LoC Arguments Description Source
triangle 53 3 Classify triangles Ref. [3]
gcd 38 2 Greatest Common Denominator F. Chicano
calday 72 3 Calculate the day of the week C Recipes
crc 82 13 Cyclic Redundant Code C Recipes
insertion 47 20 Sort by insertion method C Recipes
shell 58 20 Sort by shell method C Recipes
quicksort 143 20 Sort by quicksort method C Recipes
heapsort 72 20 Sort by heapsort method C Recipes
select 200 21 kth element of an unordered list C Recipes
bessel 245 2 Bessel Jn and Yn functions C Recipes
sa 332 23 Simulated Annealing for TSP C Recipes

Related Bibliography and Papers

[1] Phil McMinn, Search-based Software Test Data Generation: A Survey, Software Testing, Verification and Reliability 14(2), pp. 105-156

[2] E. Alba and F. Chicano, Observations in using Parallel and Sequential Evolutionary Algorithms for Automatic Software Testing, Computers & Operations Research, 35 (10): 3161-3183

Last Updated: 14/12/09
For any question or suggestion, click here to contact with us.
joomla counter | Webmaster | Contact Us | ©2009 M* UMA