Concurrent Java Test Generation as a Search Problem

A Random test generator generates executable tests together with their expected results. In the form of a noise-maker, it seeds the program with conditional scheduling primitives (such as yield()) that may cause context switches. As a result different interleavings are potentially produced in different executions of the program. Determining a-priori the set of seeded locations required for a bug to manifest itself is rarely possible.This work proposes to reformulate random test generation of concurrent Java programs as a search problem. Hence, it allows applying a set of well known search techniques from the domain of AI to the input space of the test generator. By iteratively refining the input parameters fed to the test generator, the search process creates testing scenarios (i.e. interleavings) that maximizes predefined objective functions. We develop geneticFinder, a noise-maker that uses a genetic algorithm as a search method. We demonstrate our approach by maximizing two objective functions: the high manifestation rate of concurrent bugs and the exporting of a high degree of debugging information to the user. Experimental results show our approach is effective.