Препринты ИСП РАН

Preprints of the Institute for System Programming of RAS, Preprint 23, 2011

Igor Burdonov, Alexander Kosachev. Nonconforming traces elimination from specification. Pp. 1-219.


The paper describes the optimization of testing as checking the correspondence (conformance) of implementation to the given specification during test experiments. Tests are generated from specification traces. However, as this paper shows, some traces in the specification do not occur in any conforming implementations. Test generated from such nonconforming traces are knowingly “redundant”. So, for test optimization purpose, there is a task to eliminate nonconforming traces from specification. To do that, we propose the corresponding transformation of the specification (we call it ∇-completion) with additional requirement: the class of conforming implementations is unchanged and there is still possibility to test all implementations that could be tested against the initial specification. The proposed algorithms are suitable for the wide range of conformance relations parameterized with some interaction semantics based on test stimuli and observations. For finite semantics and finite initial specification, these algorithms perform the required transformation in finite time and result in a finite specification.

Keywords: interaction semantics, refusals, destruction, divergence, conformance, safe testing, traces, LTS, test generation

Back to the list of preprints