Generating Android Tests Using Novelty Search

Search-based approaches have become a standard technique in automated Android testing. However, deceptive fitness landscapes make it difficult to find optimal solutions in a reasonable time. An alternative to classical search algorithms is offered by novelty search algorithms, which replace classical coverage-based fitness functions with a fitness function that rewards chromosomes based on how different, i.e., novel, they are compared to prior solutions. An open question is how to best quantify novelty for Android tests. In this paper, we therefore study two alternative approaches: First, we use a k-nearest neighbours (kNN) approach to determine the novelty in terms of coverage; second, we quantify the novelty of a chromosome based on the second-order uncertainty derived from subjective logic. We integrated both approaches into the open source Android test generator MATE and study its performance on 108 complex apps. Our experiments suggest that novelty search represents a promising alternative but requires further research to fully unleash its power: While both novelty search variants outperform a random-based exploration, they cannot yet compete with the state-of-the-art many-objective search algorithm MIO.