Many Independent Objective Estimation of Distribution Search for Android Testing

Search-based test generation techniques have shown promising results when applied to Android. The most common approach is to use genetic algorithms, but defining adequate crossover and mutation operators is challenging for Android testing: The actions that form tests are often state-dependent, which implies that they cannot be arbitrarily re-arranged without leading to non-executable tests. In this paper, we therefore investigate the use of estimation of distribution algorithms (EDAs), which are search algorithms where probability distributions over the input space are adapted and sampled instead of using explicit variation operators. We introduce MIOEDA, a many-objective search algorithm that integrates the Many Objective Independent (MIO) search algorithm, which was specifically designed for test generation, with estimation of distribution search, thus enabling the search for code coverage without requiring classical variation operators. Using our implementation of MIOEDA as part of the open source Android test generator MATE for an evaluation study on 100 Android apps demonstrates that MIOEDA can serve as a successful replacement of search algorithms based on traditional variation operators.