Manual creation of tests to ensure the quality of software artefacts is a difficult and labour intensive task. Automatic test generation on the other hand (e.g., using a tool like Randoop) usually requires little or no help from the developers — but often ends up creating too many tests of little value. Various techniques have been proposed to optimise test case generation by targeting only the most relevant tests, such as, genetic algorithms.
One of the major issues with such optimisation scenario is that there are various perspectives on what is a good test – hence no universally accepted definition of the `best’ test. For instance some developers consider line coverage (how many lines of the code are executed by the tests) as the most important criterion; while others don’t see it as very relevant (a line only executed is not really thoroughly stressed: there could be many different ways of testing a line) and they prefer mutation-based criterion. Some managers want tests that are quick (if execution time of the tests is a important); while some developers prefer tests that are smaller (often more readable).
The main optimisation technique used to address such complex problem is called Multi-objective optimisation (MOO) – it aims at optimising several conflicting goals at the same time. It is very popular with practitioners, who tend to deal with complex optimisation problems. The goal of this project is to adapt a test generation platform (Evosuite) to the MOO case, and in particular the students will implement an existing MOO algorithm (e.g., NSGA-II, SPEA2) as an extension of the Genetic Algorithm (GA) implemented in the EvoSuite tool.
Possible objectives of the project:
- Design and implementation of simple (greedy, local search, genetic) algorithms for the (mono-objective) time tabling problem
- Evaluation of these techniques on a benchmark
- Definition of the test generation problem as a multi-objective problem and evaluation of various simple (greedy, local search, genetic) algorithms on the problem
- Adaptation of the benchmark in the multi-objective context
- Design and implementation of hybrid metaheuristics to address the multi-objective definition of the problem
- Design and implementation of a 3 step metaheuristic
- Evaluation of these metaheuristics
Reading:
- http://www.evosuite.org/ (a tool that uses, among other things, genetic algorithms for test generation)
- http://jmetal.sourceforge.net/ (reference implementation of multi-objective algorithms)