Exploration with Multiple State Groupings

Exploration algorithms are relevant to the industrial practice of generating test cases from an abstract state machine whose runs define the predicted behavior of the software system under test. In this paper we describe a new exploration algorithm that allows multiple state grouping functions to simultaneously guide the search for states that are interesting or relevant for testing. In some cases, our algorithm allows exploration to be optimized from exponential to linear complexity. The paper includes an extended example that illustrates the use of the algorithm with the Spec Explorer tool developed as Microsoft Research.