K. Chatterjee,
L. de Alfaro,
R. Majumdar.
The Complexity of Coverage.
Technical Report UCSC-SOE-08-03, School of Engineering,
University of California, Santa Cruz, CA, USA. April 2008.
Abstract
PDF
Abstract
We study the problem of generating a test sequence that achieves
maximal coverage for a reactive system under test. We formulate the
problem as a repeated game between the tester and the system, where
the system state space is partitioned according to some coverage
criterion and the objective of the tester is to maximize the set of
partitions (or coverage goals) visited during the game. We show the
complexity of the maximal coverage problem for non-deterministic
systems is PSPACE-complete, but is NP-complete for deterministic
systems. For the special case of non-deterministic systems with a
re-initializing "reset" action, which represent running a new test
input on a re-initialized system, we show that the complexity is again
co-NP-complete. Our proof technique for reset games uses randomized
testing strategies that circumvent the exponentially large memory
requirement in the deterministic case.