Testing, Optimization, and Games

As systems become larger and more complex, there is a growing need for the development of effective automated methods to test them to ensure their correct functioning. We will discuss algorithmic problems arising in the testing of reactive systems (i.e. systems that interact with their environment), modeled by various types of state machines. The goal is to design test sequences so that we can deduce desired information about the given system under test, such as whether it conforms to a given specification model, or whether it satisfies given requirement properties. Test generation can be approached from different points of view - as an optimization problem of minimizing cost and maximizing the effectiveness of the tests; as a game between tester and system under test; or as a learning problem. We touch on some of these aspects and related algorithmic questions.