# Part-X: A Family of Stochastic Algorithms for Search-Based Test Generation with Probabilistic Guarantees

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 89 references that are in the map.
- First posted on arXiv 20 Oct 2021.

## Builds on (most cited first, 19 of 19)

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical Systems](https://mlsanity.com/paper/2005.02979/) (2020)
- [AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search](https://mlsanity.com/paper/1903.11059/) (2019)
- [Compositional Falsification of Cyber-Physical Systems with Machine Learning Components](https://mlsanity.com/paper/1703.00978/) (2017)
- [Simulation-based Adversarial Test Generation for Autonomous Vehicles with Machine Learning Components](https://mlsanity.com/paper/1804.06760/) (2018)
- [Sample-Efficient Neural Architecture Search by Learning Action Space](https://mlsanity.com/paper/1906.06832/) (2019)
- [RTAMT: Online Robustness Monitors from STL](https://mlsanity.com/paper/2005.11827/) (2020)
- [Falsification of Cyber-Physical Systems Using Deep Reinforcement Learning](https://mlsanity.com/paper/1805.00200/) (2018)
- [On-Line Monitoring for Temporal Logic Robustness](https://mlsanity.com/paper/1408.0045/) (2014)
- [Multiscale Gaussian Process Level Set Estimation](https://mlsanity.com/paper/1902.09682/) (2019)
- [Time Robustness in MTL and Expressivity in Hybrid System Falsification (Extended Version)](https://mlsanity.com/paper/1505.06307/) (2015)
- [Approximation-Refinement Testing of Compute-Intensive Cyber-Physical Models: An Approach Based on System Identification](https://mlsanity.com/paper/1910.02837/) (2019)
- [Verifying Controllers Against Adversarial Examples with Bayesian Optimization](https://mlsanity.com/paper/1802.08678/) (2018)
- [Falsification of Cyber-Physical Systems with Robustness-Guided Black-Box Checking](https://mlsanity.com/paper/2005.02126/) (2020)
- [PSY-TaLiRo: A Python Toolbox for Search-Based Test Generation for Cyber-Physical Systems](https://mlsanity.com/paper/2106.02200/) (2021)
- [An Active Learning Approach to the Falsification of Black Box Cyber-Physical Systems](https://mlsanity.com/paper/1705.01879/) (2017)
- [Fast Falsification of Hybrid Systems using Probabilistically Adaptive Input](https://mlsanity.com/paper/1812.04159/) (2018)
- [An Efficient Algorithm for Monitoring Practical TPTL Specifications](https://mlsanity.com/paper/1612.03140/) (2016)
- [Two-Layered Falsification of Hybrid Systems guided by Monte Carlo Tree Search](https://mlsanity.com/paper/1803.06276/) (2018)

## Built on by (most cited first, 6 of 6)

- [Requirement falsification for cyber-physical systems using generative models](https://mlsanity.com/paper/2310.20493/) (2023)
- [Tolerance of Reinforcement Learning Controllers against Deviations in Cyber Physical Systems](https://mlsanity.com/paper/2406.17066/) (2024)
- [DiCriTest: Testing Scenario Generation for Decision-Making Agents Considering Diversity and Criticality](https://mlsanity.com/paper/2508.11514/) (2025)
- [Learning test generators for cyber-physical systems](https://mlsanity.com/paper/2410.03202/) (2024)
- [Non-linear Multi-objective Optimization with Probabilistic Branch and Bound](https://mlsanity.com/paper/2506.04554/) (2025)
- [A Consistency-Centric Approach to Set-Based Optimization with Multiple Models of Unranked Fidelity](https://mlsanity.com/paper/2605.04051/) (2026)

## Abstract (arXiv)

Requirements driven search-based testing (also known as falsification) has proven to be a practical and effective method for discovering erroneous behaviors in Cyber-Physical Systems. Despite the constant improvements on the performance and applicability of falsification methods, they all share a common characteristic. Namely, they are best-effort methods which do not provide any guarantees on the absence of erroneous behaviors (falsifiers) when the testing budget is exhausted. The absence of finite time guarantees is a major limitation which prevents falsification methods from being utilized in certification procedures. In this paper, we address the finite-time guarantees problem by developing a new stochastic algorithm. Our proposed algorithm not only estimates (bounds) the probability that falsifying behaviors exist, but also it identifies the regions where these falsifying behaviors may occur. We demonstrate the applicability of our approach on standard benchmark functions from the optimization literature and on the F16 benchmark problem.