Formal Methods and Conformance Testing - or - What are we testing anyway?

In this paper, we will show the correlation between the notion of implementation relations known from formal methods and ideas of conformance testing. We will show that the implementation relations realized through the practical testing of systems come from a family of parameterized implementation relations. We will also show that for glass box testing, implementation relations parameterized by test purposes converge to the may-testing preorder of DeNicola and Hennessy, while for black box testing, implementation relations parameterized by test cases converge to a may-testing preorder of the behavior visible at the interface to the environment.