PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Anthony Corso, Robert J. Moss, Mark Koren, Ritchie Lee, Mykel J. Kochenderfer

arXiv:2005.02979v3cs.LGcs.AIeess.SYstat.ML

TL;DR

Safety-critical CPS need rigorous testing, but formal verification may not scale and real-world testing can be dangerous. This survey reviews black-box simulation algorithms for safety validation, finding failures and estimating failure probabilities, and reports coverage of optimization, path planning, reinforcement learning, importance sampling, decomposition, applications, and tools. Its practical scope is bounded by scalability challenges and assumptions or failure modes associated with particular techniques.

  • Problem

    Complex safety-critical CPS require validation, while formal verification and real-world testing can be impractical.

  • Method

    The paper surveys black-box safety validation algorithms spanning optimization, path planning, reinforcement learning, importance sampling, decomposition techniques, applications, and tools.

  • Results

    The survey identifies optimization, path planning, and reinforcement learning for finding falsifying examples, and importance sampling for estimating failure probabilities, including rare failures.

  • Takeaways & Limitations

    Black-box validation provides algorithms and tools for testing complex CPS through simulated disturbances without requiring system internals.

  • Takeaways & Limitations

    Validation scalability is constrained by large disturbance and state spaces, while some techniques also depend on state availability or can struggle with rare failures.

Abstract

from arXiv · show

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.

1. Introduction

Safety-critical CPS require rigorous validation because their complexity limits formal verification and makes real-world testing dangerous. This survey focuses on black-box simulation methods for finding failures, estimating failure likelihood, and scaling validation.

  • Safety-critical CPS failures can cause serious consequences, including loss of life and property.
  • Safety validation uses simulation to test environmental disturbances against specified safety properties and assess failure probability.
  • Black-box methods avoid assumptions about system internals, enabling validation across broader classes of complex systems.
  • The survey covers falsification, most-likely failure analysis, and failure probability estimation.
  • Optimization, path planning, reinforcement learning, and importance sampling are surveyed, alongside decomposition techniques for scalability.

2. Preliminaries

The paper models safety validation around a system, environment, safety property, and disturbance process. It distinguishes validation from verification and defines falsification, most-likely failure analysis, and failure probability estimation as core tasks.

  • A safety validation problem consists of a system M, environment E, and safety property ψ defined over environment-state trajectories.
  • An adversary selects disturbances whose probability density models environmental likelihood and may be learned from data or specified by experts.
  • The environment transitions according to dynamics that depend on the system, environment, and disturbances, with disturbances treated as the only variable affecting the system.
  • Falsification searches for a disturbance trajectory violating the specification, whereas most-likely failure analysis searches for the failure trajectory with maximum likelihood.
  • Failure probability estimation computes the probability that the specification is violated under the disturbance model.

3. Overview of Solution Techniques

Safety validation proceeds by defining a safety property and search cost, selecting an algorithm suited to the system and task, and running it until a counterexample or sufficient coverage is obtained.

  • Validation begins by defining a safety property, then an appropriate cost function to guide the search.
  • The algorithm is selected according to the system, environment, and safety validation task.
  • Execution continues until a counterexample is discovered or the space of possible scenarios has been sufficiently covered.

3.1 Safety Specification with Temporal logic

Formal specification languages reduce ambiguity and support numerical evaluation of trajectories. Signal temporal logic is widely used to express safety properties for real-valued CPS signals over time.

  • Formal specification languages are preferred because they reduce ambiguity and permit efficient numerical evaluation of state trajectories.
  • Temporal logic describes properties of signals over time through formulas that evaluate to Boolean values.
  • Signal temporal logic is widely used for CPS safety validation and supports formulas over real-valued signals.
  • One example requires an autonomous vehicle to reach its goal within 100 seconds, while another constrains aircraft separation over time.

3.2 Cost Functions

Safety validation uses cost functions to guide searches toward disturbances that violate safety properties or represent likely failures. The survey describes application-specific safety measures, temporal-logic robustness, likelihood terms, and penalties for exploration or implausible disturbances.

  • Cost-function role: Cost functions guide disturbance searches toward trajectories that are less safe and can identify counterexamples efficiently.The cost is defined over disturbance trajectories through the system and environment dynamics.
  • Application-specific costs: For collision avoidance, miss distance is a common cost, while control-system non-convergence can use Lyapunov-like functions, neural networks, or support vector machines.
  • Temporal-logic robustness: Temporal-logic robustness measures how closely a trajectory approaches violating its specification, with negative values indicating violation.Large robustness indicates safe separation from violation; low positive values indicate proximity to violation.
  • Temporal-logic robustness: Robustness objectives can be difficult to optimize because they may be non-smooth or dominated by larger-magnitude state variables.Proposed responses include smooth approximations, convex transformations, normalization, and selecting among per-variable robustness values.
  • Likelihood and search heuristics: Most-likely failure analysis incorporates disturbance likelihood or penalties for low-likelihood disturbances, with additional terms available for coverage and domain constraints.Traffic-law constraints are one example of a domain-specific heuristic for adversarial driving scenarios.
  • Likelihood and search heuristics: Sequential methods can assign costs to incomplete state-disturbance trajectories, rewarding disturbance log probabilities while penalizing trajectories that do not end in failure.Adaptive stress testing uses this structure for most-likely failure analysis.

3.3 Overview of Algorithms

The survey organizes safety-validation algorithms by the information they use, simulator requirements, and validation task. Optimization, path planning, reinforcement learning, and importance sampling offer different ways to search failures or estimate failure probabilities, with distinct scalability and state-information trade-offs.

  • Overview: The survey distinguishes algorithm categories by information requirements, simulated-environment requirements, and target safety-validation task.
  • Optimization: Black-box optimization searches disturbance trajectories without gradients, but non-convex objectives can contain many local minima.Global methods and combined global-local search are used to address this difficulty.
  • Optimization: Optimization requires only disturbance inputs and safety-metric outputs, but its search over the full trajectory space scales exponentially with the time horizon.This makes optimization attractive when simulator state is unavailable, while limiting performance on long-horizon problems.
  • Path planning: Path planning uses environment state to construct disturbance trajectories toward failure states and can reuse trajectory segments in high-dimensional spaces.Sampling-based planners such as RRT operate with black-box simulators, and RRT has been used extensively for CPS safety validation.
  • Path planning: Path planning can struggle with small reachable sets, stochastic transitions, deterministic replay requirements, and long horizons requiring very large trees.
  • Reinforcement learning: Reinforcement learning learns a state-dependent disturbance policy, naturally handles stochastic environments, and can address long horizons with episodic reset-and-step simulators.Its drawbacks include sample inefficiency and complex, sometimes brittle training procedures.
  • Importance sampling: Importance sampling increases failure likelihood under a proposal distribution and reweights failures to estimate failure probability with fewer samples.The proposal must assign positive probability wherever the target failure density is positive.
  • Importance sampling: Importance sampling seeks to approximate an optimal zero-variance proposal, but that proposal is unavailable because the cost is black-box and failure probability is the quantity being estimated.Algorithms therefore estimate the optimal importance distribution rather than construct it directly.

3.4 Coverage Metrics

Coverage metrics provide stopping criteria when testing has infinitely many possible scenarios. The survey covers probability-based, disturbance-trajectory, and reachable-state coverage, while noting that unreachable states can limit state-space coverage.

  • Coverage overview: Testing completion can be assessed using failure probability, disturbance-trajectory coverage, or reachable-state coverage.
  • Probability coverage: Probability-based testing can use hypothesis tests or confidence intervals over Bernoulli failure outcomes to determine whether failure probability is below a threshold.Frequentist and Bayesian approaches provide alternative estimation procedures.
  • Probability coverage: Importance sampling reduces the sampling burden for strict safety thresholds by drawing failures more often and weighting samples during hypothesis testing or estimation.A poorly chosen or inefficient proposal distribution can undermine this benefit.
  • Trajectory-space coverage: Trajectory-space coverage measures how well sampled disturbance trajectories represent the possible trajectory space, with testing potentially ending when coverage approaches one.
  • Trajectory-space coverage: Dispersion and star discrepancy quantify different aspects of trajectory coverage: empty-region radius and uniformity of point distribution.Grid-based dispersion trades computational cost against fidelity, while discrepancy approaches zero when subregions receive their volume-proportional share.
  • State-space coverage: State-space coverage can be more efficient for prohibitively large trajectory spaces and has been used with rapidly exploring random trees.
  • State-space coverage: Unreachable states can cap state-space coverage below its termination threshold, so growth below a specified threshold can provide an alternative stopping condition.Growth measures how much coverage increases as samples are added.

4. Black-Box Optimization

Black-box optimization methods adapt general-purpose global-search techniques to safety validation, including simulated annealing, evolutionary algorithms, Bayesian optimization, and ant-colony optimization. Modifications address constraints, temporal discretization, interpretability, stochastic costs, and scalability.

  • Overview: The survey covers simulated annealing, evolutionary algorithms, Bayesian optimization, and extended ant-colony optimization for black-box safety validation.
  • Simulated annealing: Simulated annealing performs stochastic search over disturbance trajectories, accepting higher-cost candidates probabilistically according to a temperature-controlled rule.
  • Simulated annealing: Hit-and-run transitions preserve disturbance constraints by sampling a direction, line-searching a feasible interval, and sampling within that interval.The step distribution can be adjusted using the acceptance ratio, and per-dimension step selection avoids overrestricting less-constrained dimensions.
  • Simulated annealing: Input-signal-space optimization adds an outer search over disturbance-trajectory length to optimize temporal discretization alongside trajectory values.This targets problems where disturbance frequency content is salient.
  • Evolutionary algorithms: Evolutionary algorithms generate candidate inputs through population-based selection, crossover, and mutation, and can optimize temporal-logic failure descriptions.Failure descriptions can improve interpretability and provide engineering insight into failure modes.
  • Bayesian optimization: Bayesian optimization uses a surrogate model to select promising disturbance trajectories when evaluations are costly or stochastic.Each iteration updates the surrogate and chooses the next trajectory using an exploration or improvement criterion.
  • Bayesian optimization: Gaussian processes struggle with large dimensions and many samples, motivating SOAR’s global-local search and random-embedding dimensionality reduction.
  • Ant-colony optimization: Extended ant-colony optimization represents disturbance trajectories as graph paths and deposits pheromone in cells visited by low-cost trajectories.

5. Path Planning

Path-planning methods frame safety validation as searching environment-state spaces for disturbance trajectories that reach failure states, adapting sampling and tree growth to black-box, continuous, or high-dimensional settings.

  • Rapidly Exploring Random Tree: RRT grows a tree by sampling goal states, selecting nearby nodes, simulating disturbances, and adding resulting states until a stopping criterion is met.Termination can occur after a maximum iteration count, a falsifying trajectory, or sufficient tree coverage.
  • Adaptive Sampling: Uniform goal sampling can be inefficient when reachable states occupy only part of the state space, motivating biased sampling toward reachable or low-coverage regions.Guided-RRT weights regions and samples goals within the selected region to increase tree coverage.
  • Neighbor Selection: Nearest-neighbor selection strongly affects RRT performance because Euclidean distance ignores system reachability, reachable-set boundaries, and trajectory costs.Alternative metrics can use estimated travel time, domain knowledge, simulations, failure history, or state-dependent cost.
  • RRT Variants: RRT variants use multiple trees, backward connections, and optimization-assisted transitions to improve exploration while retaining black-box simulation.RRFT assigns trees to parameter choices, while backward RRT starts from sampled failure states and connects toward earlier states.
  • Multiple Shooting Methods and Las Vegas Tree Search: Multiple shooting connects sampled trajectory segments into candidate paths, while LVTS grows disturbance trajectories using stochastic expansion and adaptive time discretization.These approaches modify path planning for black-box falsification and large state spaces.

6. Reinforcement Learning

Reinforcement-learning methods search disturbance sequences with tree-based planning or learned value functions and policies, adapting representation and exploration to the disturbance space.

  • Monte Carlo Tree Search: MCTS repeatedly selects, expands, rolls out, and backpropagates disturbance choices to maximize estimated reward under a stopping criterion.Stopping can depend on computational budget, wall-clock time, or the best solution’s reward.
  • Monte Carlo Tree Search: MCTS can combine exploration with global optimization, but optimizing every new tree node increases computational cost and makes budget allocation critical.GNM improved significantly with MCTS, whereas CMA-ES benefited less because it already includes an exploration strategy.
  • Deep Reinforcement Learning: DRL represents value functions, state-action values, or policies with deep neural networks and has been applied to falsification and most-likely failure analysis.DQN uses replay-buffer data reuse for sample efficiency but is incompatible with large or continuous disturbance spaces.
  • Deep Reinforcement Learning: Continuous disturbance spaces require policy networks that output disturbances or distribution parameters, whereas DQN applies when disturbances are discrete.Policy-gradient methods support continuous spaces but may require many simulations because they cannot learn off-policy; actor-critic methods add value-function learning and data reuse.
  • Deep Reinforcement Learning: A practical challenge for black-box DRL is requiring simulator observations after each disturbance, which may be difficult for large, high-fidelity simulators.Final-state results or partial data may be easier to access than the true simulator state at every timestep.

7. Importance Sampling Algorithms

Importance sampling algorithms estimate rare failure probabilities by concentrating simulation effort on likely failures. The survey covers parametric, non-parametric, supervised-learning, and state-dependent approaches, along with their practical limitations and applications.

  • The surveyed importance sampling methods include cross-entropy, multilevel splitting, classification-based, and state-dependent approaches.They target failure-probability estimation using increasingly structured models of disturbance likelihood and simulator state.
  • Cross-Entropy Method: Cross-entropy iteratively fits a proposal distribution q(x; θ) toward the optimal importance distribution by minimizing KL-divergence.When the distribution family is a natural exponential family, the parameter update corresponds to maximum likelihood estimation.
  • Cross-Entropy Method: Rare failures can prevent cross-entropy convergence when all samples are safe, motivating adaptive safety thresholds with quantile levels ρ = [0.01, 0.2].The threshold is updated so a chosen fraction of samples falls below it at each iteration.
  • Multilevel Splitting: Multilevel splitting estimates rare-event probabilities through threshold levels and conditional probabilities, using resampling and Markov chain Monte Carlo.Its non-parametric formulation avoids an explicit proposal family and scales better to larger dimensions.
  • Classification-Based Importance Sampling: Classification-based importance sampling combines safe-versus-unsafe disturbance classifiers with proposal distributions concentrated near the estimated decision boundary.Methods use space-filling samples, supervised models, SVM boundaries, and Gaussian mixtures; they are most applicable when failures are relatively easy to find.
  • State-Dependent Importance Sampling: State-dependent importance sampling learns q(x | s) for each simulation state and estimates failure probability through approximate Bellman-equation solutions.Local approximation dynamic programming and Monte Carlo policy evaluation are reported as successful solution approaches.

8. Problem Decomposition Techniques

Problem decomposition addresses poor scalability in black-box safety validation by dividing large disturbance and state spaces into tractable subproblems. The surveyed approaches decompose simulator components or machine-learned components, then combine or analyze the resulting subproblems.

  • Safety-validation algorithms often scale poorly to large disturbance and state spaces, motivating decomposition into more tractable subproblems.Black-box assumptions prevent decomposition methods that require factoring the transition function, but state- and action-space generalization remains applicable.
  • 8.1 State Space Decomposition: State-space decomposition separates simulator state and disturbance spaces into independent components and searches for failures within each component.Subproblem policies can be fused using arithmetic operations such as mean, maximum, or minimum.
  • 8.1 State Space Decomposition: Simple policy fusion may miss interactions among disturbance components, so a global correction factor can be learned from full-simulation rollouts.The correction factor is trained by comparing estimated failure probabilities with actual discounted returns.
  • 8.1 State Space Decomposition: State-space decomposition has been shown to increase the number of failures found in a complex driving environment with a large disturbance space.
  • 8.2 Compositional Approach with Machine Learning Components: A compositional approach for machine-learned components replaces a high-dimensional component with an abstraction, compares idealized and poor behaviors, and isolates a region of interest.A separate analyzer then identifies high-dimensional inputs causing failures, such as perception misclassifications.
  • 8.2 Compositional Approach with Machine Learning Components: The compositional approach found counterexamples in a neural-network perception system used by an autonomous vehicle.

9. Applications

Black-box safety validation is applied across autonomous vehicles, aircraft, hybrid systems, neural-network controllers, and planning modules. Applications define failures through domain-specific safety criteria, while miss distance commonly provides an optimization heuristic in vehicle and aircraft scenarios.

  • Autonomous Vehicles: Autonomous-car validation commonly uses miss distance as a reward heuristic for finding counterexamples across driving scenarios.Typical scenarios include lane following, intersections, lane changes, and vehicle platooning.
  • Autonomous Vehicles: Driving failures include collisions, traffic-law violations, unsafe lane changes, and excessive deviations from platooning objectives.
  • Aircraft: Aircraft validation covers flight control, collision avoidance, and flight-path planning under disturbances such as wind, pilot inputs, sensor noise, and mission parameters.Failures include degraded flight quality, autopilot disengagement, near mid-air collisions, keep-out-zone violations, and software errors.
  • Other Systems: Black-box validation also targets hybrid systems, including automatic transmissions, thermostats, and wind turbines, using application-specific safety thresholds.
  • Other Systems: Neural-network controllers and planning modules are validated in systems such as steam condensers, hovercraft, free-floating robots, and gridworld agents.These tasks test constraints including acceptable pressure ranges, goal reachability, obstacle avoidance, and required-state visitation.

10. Existing Tools

Existing safety-validation tools range from open-source academic prototypes to commercial software, with falsification as the common core task. They implement optimization, path planning, reinforcement learning, and hybrid techniques, while tool applicability can be constrained by strict temporal-logic interfaces.

  • The surveyed tools include academic prototypes and commercial software, and all available tools perform falsification as their core task.Only TrustworthySearch API also performs failure-probability estimation, while the AST Toolbox also performs most-likely-failure analysis.
  • Academic Tools: S-TaLiRo and Breach have become benchmark standards among open-source falsification tools.
  • Solution Techniques: S-TaLiRo and Breach use optimization, RRT-Rex uses path planning, AST Toolbox and falsify use reinforcement learning, and FalStar combines reinforcement learning with global optimization.
  • Tool Interfaces: Most tools interface with MATLAB and emphasize Simulink models, reflecting industrial use of MATLAB/Simulink for prototyping.
  • Tool Interfaces: Academic falsification-only tools commonly specify requirements in signal or metric temporal logic, but strict temporal-logic requirements may limit applicability.
  • Future Development: Tool availability enables users to provide feedback from specific use cases and experience, while competitions such as ARCH-COMP encourage continued development.

11. Conclusion

The survey frames black-box validation as essential for complex, safety-critical autonomous systems and organizes methods around distinct failure-analysis goals. It covers algorithms, scalability strategies, applications, and available tools.

  • Black-box validation strategies are needed to test increasingly complex safety-critical autonomous systems operating with humans.The conclusion links this need to the high complexity of autonomous systems.
  • The survey distinguishes falsification, most-likely failure analysis, and failure probability estimation as core validation tasks.
  • Global optimization, path planning, and reinforcement learning support falsification, while importance sampling estimates failure probabilities near zero.
  • Problem-decomposition approaches make safety validation more manageable by breaking it into components that address scalability.
  • The survey also reviews black-box validation applications in autonomous driving and flight, along with existing validation tools.
Loading 2005.02979v3…