Genetic Algorithms for MUtation Testing (GAMUT)

Dr Robert M. Hierons

Department of Information Systems and Computing, Brunel University

1. Overview of the problem

Meta-heuristic algorithms

Many problems may be represented in terms of searching for values that minimising the value of some function, often called the objective function. Where there may be local minima, traditional approaches such as hill-climbing can fail through finding one of these minima rather than the global minimum. Meta-heuristic algorithms, such as Genetic Algorithms, Simulated Annealing, and Tabu search, are designed to avoid getting stuck at local minima. It has thus been found that they are able to solve a wide range of problems.

1.2 Mutation testing

Software testing is a vital yet expensive part of the software development process, studies suggesting that it often consumes in the order of fifty percent of the total development budget (see, for example, [1]). Thus approaches that automate or semi-automate sections of software testing may significantly improve the efficiency and quality of the software development process.

Mutation testing is based upon seeding the implementation with a fault (mutating it), by applying a mutation operator, and determining whether testing identifies this fault. A mutated program is called a mutant and if a test case distinguishes between the mutant and the original program it is said to kill the mutant. The idea behind mutation testing is quite simple: given an appropriate set of mutation operators, if a test set kills the mutants generated by these operators then, since it is able to find these small differences, it is likely to be good at finding real faults.

Mutation testing may be used to judge the effectiveness of a test set: the test set should kill all the mutants. Similarly, test generation may be based on mutation testing: tests are generated to kill the mutants. Interestingly, many test criteria may be represented using mutation testing by simply choosing appropriate mutation operators.

While mutation testing is a powerful and general technique, a number of associated problems have limited its practical impact. One of these problems is that the standard set of mutation operators may lead to a vast number of mutants. However, it has been noted that this problem can be reduced by an appropriate choice of mutation operators ([6,5]). The following are the other main practical problems.

  1. While a mutant is syntactically different from the initial program it may have the same behaviour as the program: a mutant may be equivalent to the original program. Clearly equivalent mutants can never be killed and thus it is important, but often difficult, to identify them. Some approaches to detecting equivalent mutants ([7, 3, 2]) and reducing the number of equivalent mutants produced ([3, 2]) have been introduced.
  2. Some mutants, called stubborn mutants, may be non-equivalent but difficult to kill.

Project Objectives

GAMUT will explore the application of meta-heuristic algorithms (such as Genetic Algorithms) to assist in solving the problems outlined above. While meta-heuristic algorithms have already been successfully used to generate tests that achieve full branch coverage ([4]), they have yet to be applied to mutation testing, where the challenges are quite different. The project will investigate the following issues.

  1. How can meta-heuristics be used to detect equivalent mutants and kill stubborn mutants?
  2. Which meta-heuristic algorithms are most effective when applied to these problems?

References

  1. Boehm B. W., 1981, Software Engineering Economics, Prentice-Hall.
  2. Harman M., Hierons R. M. and Danicic S., The Relationship between Program Dependence and Mutation Testing, submitted to Mutation 2000.
  3. Hierons R.M., Harman M. and Danicic S., 1999, Using Program Slicing to Assist in the Detection of Equivalent Mutants, The Journal of Software Testing, Verification, and Reliability, 9 4, pp. 233-262.
  4. Jones B. F., Eyres D. E. and Sthamer H.-H., 1998, A Strategy for using Genetic Algorithms to Automate Branch and Fault-Based Testing, The Computer Journal, 41 2, pp. 98-107.
  5. Mresa E. S. and Bottaci L., 1999, Efficiency of Mutation Operators and Selective Mutation Strategies: An Empirical Study, The Journal of Software Testing, Verification, and Reliability, 9 4, pp. 205-232.
  6. Offut A. J., Lee A., Rothermel G., Untch R. H. and Zapf C., 1996, An experimental determination of sufficient mutant operators, ACM Transactions on Software Engineering and Methodology, 5 2, pp.99-118.
  7. Offut A. J. and Pan J., 1996, Detecting equivalent mutants and the feasible path problem, Proceedings of the Annual Conference on Computer Assurance (COMPASS 96), Gaithersburg. Maryland, U.S.A., pp.224-236