  Black-box testing has been extensively applied to test models of
Cyber-Physical systems (CPS) since these models are not often amenable to
static and symbolic testing and verification. Black-box testing, however,
requires to execute the model under test for a large number of candidate test
inputs. This poses a challenge for a large and practically-important category
of CPS models, known as compute-intensive CPS (CI-CPS) models, where a single
simulation may take hours to complete. We propose a novel approach, namely
ARIsTEO, to enable effective and efficient testing of CI-CPS models. Our
approach embeds black-box testing into an iterative approximation-refinement
loop. At the start, some sampled inputs and outputs of the CI-CPS model under
test are used to generate a surrogate model that is faster to execute and can
be subjected to black-box testing. Any failure-revealing test identified for
the surrogate model is checked on the original model. If spurious, the test
results are used to refine the surrogate model to be tested again. Otherwise,
the test reveals a valid failure. We evaluated ARIsTEO by comparing it with
S-Taliro, an open-source and industry-strength tool for testing CPS models. Our
results, obtained based on five publicly-available CPS models, show that, on
average, ARIsTEO is able to find 24% more requirements violations than S-Taliro
and is 31% faster than S-Taliro in finding those violations. We further
assessed the effectiveness and efficiency of ARIsTEO on a large industrial case
study from the satellite domain. In contrast to S-Taliro, ARIsTEO successfully
tested two different versions of this model and could identify three
requirements violations, requiring four hours, on average, for each violation.
