finding deadlocks in large concurrent java programs using genetic algorithms
Model checking is a fully automatic technique for checking concurrent software properties in which the states of a concurrent system are explored in an explicit or implicit way. However, the state explosion problem limits the size of the models that are possible to check. Genetic Algorithms (GAs) are metaheuristic techniques that have obtained good results in problems in which exhaustive techniques fail due to the size of the search space. Unlike exact techniques, metaheuristic techniques cannot be used to verify that a program satisfies a given property, but they can find errors on the software using a lower amount of resources than exact techniques. In this paper, we compare a GA against classical exact techniques and we propose a new operator for this problem, called memory operator, which allows the GA to explore even larger search spaces. We implemented our ideas in the Java PathFinder (JPF) model checker to validate them and present our results. To the best of our knowledge, this is the first implementation of a Genetic Algorithm in this model checker.
genetic algorithm model checking memory operator graph search