# A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical Systems

arXiv: https://arxiv.org/abs/2005.02979 · HTML: https://mlsanity.com/paper/2005.02979/

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2020.

## Built on by (most cited first, 30 of 71)

- [The Waymo Open Sim Agents Challenge](https://mlsanity.com/paper/2305.12032/) (2023)
- [Vehicle trajectory prediction works, but not everywhere](https://mlsanity.com/paper/2112.03909/) (2021)
- [OVERT: An Algorithm for Safety Verification of Neural Network Control Policies for Nonlinear Systems](https://mlsanity.com/paper/2108.01220/) (2021)
- [From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligence](https://mlsanity.com/paper/2110.15245/) (2021)
- [A Survey on Scenario-Based Testing for Automated Driving Systems in High-Fidelity Simulation](https://mlsanity.com/paper/2112.00964/) (2021)
- [Building reliable sim driving agents by scaling self-play](https://mlsanity.com/paper/2502.14706/) (2025)
- [SceneDiffuser++: City-Scale Traffic Simulation via a Generative World Model](https://mlsanity.com/paper/2506.21976/) (2025)
- [How Do We Fail? Stress Testing Perception in Autonomous Vehicles](https://mlsanity.com/paper/2203.14155/) (2022)
- [How Generalizable Is My Behavior Cloning Policy? A Statistical Approach to Trustworthy Performance Evaluation](https://mlsanity.com/paper/2405.05439/) (2024)
- [Finding Critical Scenarios for Automated Driving Systems: A Systematic Literature Review](https://mlsanity.com/paper/2110.08664/) (2021)
- [Distributionally Robust Statistical Verification with Imprecise Neural Networks](https://mlsanity.com/paper/2308.14815/) (2023)
- [Failures Are Fated, But Can Be Faded: Characterizing and Mitigating Unwanted Behaviors in Large-Scale Vision and Language Models](https://mlsanity.com/paper/2406.07145/) (2024)
- [Fairness and Bias in Robot Learning](https://mlsanity.com/paper/2207.03444/) (2022)
- [Finding Failures in High-Fidelity Simulation using Adaptive Stress Testing and the Backward Algorithm](https://mlsanity.com/paper/2107.12940/) (2021)
- [RoboMD: Uncovering Robot Vulnerabilities through Semantic Potential Fields](https://mlsanity.com/paper/2412.02818/) (2024)
- [Part-X: A Family of Stochastic Algorithms for Search-Based Test Generation with Probabilistic Guarantees](https://mlsanity.com/paper/2110.10729/) (2021)
- [Diffusion-Based Failure Sampling for Evaluating Safety-Critical Autonomous Systems](https://mlsanity.com/paper/2406.14761/) (2024)
- [Formalizing and Evaluating Requirements of Perception Systems for Automated Vehicles using Spatio-Temporal Perception Logic](https://mlsanity.com/paper/2206.14372/) (2022)
- [Bayesian Safety Validation for Failure Probability Estimation of Black-Box Systems](https://mlsanity.com/paper/2305.02449/) (2023)
- [A Step Towards Efficient Evaluation of Complex Perception Tasks in Simulation](https://mlsanity.com/paper/2110.02739/) (2021)
- [Risk-Driven Design of Perception Systems](https://mlsanity.com/paper/2205.10677/) (2022)
- [Falsification of Learning-Based Controllers through Multi-Fidelity Bayesian Optimization](https://mlsanity.com/paper/2212.14118/) (2022)
- [Conversational Code Generation: a Case Study of Designing a Dialogue System for Generating Driving Scenarios for Testing Autonomous Vehicles](https://mlsanity.com/paper/2410.09829/) (2024)
- [ARC: Adversarially Robust Control Policies for Autonomous Vehicles](https://mlsanity.com/paper/2107.04487/) (2021)
- [I Know You Can't See Me: Dynamic Occlusion-Aware Safety Validation of Strategic Planners for Autonomous Vehicles Using Hypergames](https://mlsanity.com/paper/2109.09807/) (2021)
- [Certifiable Deep Importance Sampling for Rare-Event Simulation of Black-Box Systems](https://mlsanity.com/paper/2111.02204/) (2021)
- [Causal Scene BERT: Improving object detection by searching for challenging groups of data](https://mlsanity.com/paper/2202.03651/) (2022)
- [Sample-Based Bounds for Coherent Risk Measures: Applications to Policy Synthesis and Verification](https://mlsanity.com/paper/2204.09833/) (2022)
- [Wasserstein Generative Adversarial Networks for Online Test Generation for Cyber Physical Systems](https://mlsanity.com/paper/2205.11060/) (2022)
- [Model-based Validation as Probabilistic Inference](https://mlsanity.com/paper/2305.09930/) (2023)

## Abstract (arXiv)

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.