A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical
  Systems
  Autonomous cyber-physical systems (CPS) can improve safety and efficiency for
safety-critical applications, but require rigorous testing before deployment.
The complexity of these systems often precludes the use of formal verification
and real-world testing can be too dangerous during development. Therefore,
simulation-based techniques have been developed that treat the system under
test as a black box operating in a simulated environment. Safety validation
tasks include finding disturbances in the environment that cause the system to
fail (falsification), finding the most-likely failure, and estimating the
probability that the system fails. Motivated by the prevalence of
safety-critical artificial intelligence, this work provides a survey of
state-of-the-art safety validation techniques for CPS with a focus on applied
algorithms and their modifications for the safety validation problem. We
present and discuss algorithms in the domains of optimization, path planning,
reinforcement learning, and importance sampling. Problem decomposition
techniques are presented to help scale algorithms to large state spaces, which
are common for CPS. A brief overview of safety-critical applications is given,
including autonomous vehicles and aircraft collision avoidance systems.
Finally, we present a survey of existing academic and commercially available
safety validation tools.
