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

Abstract

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.

References in corpus (4)

• Adaptive Monte Carlo via Bandit Allocation
• The Adaptive Stress Testing Formulation
• Adaptive Stress Testing for Autonomous Vehicles
• A Versatile Approach to Evaluating and Testing Automated Vehicles based on Kernel Methods

Cited by in corpus (9)

• Formal Certification Methods for Automated Vehicle Safety Assessment
• Weakly Supervised Reinforcement Learning for Autonomous Highway Driving via Virtual Safety Cages
• Probabilistic Metamodels for an Efficient Characterization of Complex Driving Scenarios
• Bayesian Safety Validation for Failure Probability Estimation of Black-Box Systems
• On the Adversarial Scenario-based Safety Testing of Robots: the Comparability and Optimal Aggressiveness
• Vectorized Scenario Description and Motion Prediction for Scenario-Based Testing
• Policy Testing with MDPFuzz (Replicability Study)
• Anticipating Accidents through Reasoned Simulation
• A Step Towards Efficient Evaluation of Complex Perception Tasks in Simulation