Software testing is a fundamentally undecidable problem: there is no algorithm that can tell you whether your test suite is complete. The best we can do is maximise coverage — statement, branch, path — and trust that more coverage correlates with fewer shipped bugs. The question is: how do we generate high-coverage test suites efficiently?
The Genetic Algorithm Approach
Genetic algorithms (GAs) treat test case generation as an optimisation problem. A chromosome encodes a candidate test input; a fitness function evaluates how much new code it exercises; selection, crossover, and mutation evolve the population toward higher-coverage individuals over successive generations.
In our UPCON 2016 paper, we paired the GA with mutation analysis — a technique that deliberately introduces faults (mutants) into the program and measures whether the test suite detects them. This gives us a richer fitness signal than raw coverage: a test case that covers a line scores higher if it also kills a mutant on that line.
Key Design Decisions
- Chromosome Encoding — We encode method input parameters as typed sequences, with range constraints derived from the method signature and boundary analysis.
- Fitness Function — A weighted combination of branch coverage (60%), mutation kill rate (30%), and execution cost (10%, penalising slow test cases).
- Mutation Operators — Arithmetic operator replacement, relational operator replacement, statement deletion, and variable substitution — the five most common real-world fault classes.
- Termination — The GA runs until 100% branch coverage is achieved or a generation budget (default: 500) is exhausted.
Results on Benchmark Programs
Evaluated on 12 open-source Java utility classes (ranging from 50 to 800 lines), the GA approach achieved a mean branch coverage of 91.4% and a mean mutation kill rate of 83.7%, compared to 71.2% and 61.4% for random test generation. The improvement was most pronounced on programs with complex conditional logic and deeply nested branches.
Extensions We Are Working On
Current active work in the lab extends this framework to web application performance testing (load scenarios) and IoT firmware unit testing, where the execution environment is significantly more constrained than a standard JVM. We are also exploring grammar-based chromosome encodings for programs that accept structured inputs like JSON or XML.