Falsification of Hybrid Systems Using Adaptive Probabilistic Search

Gidon Ernst, Sean Sedwards, Zhenya Zhang, Ichiro Hasuo

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

We present and analyse an algorithm that quickly finds falsifying inputs for hybrid systems. Our method is based on a probabilistically directed tree search, whose distribution adapts to consider an increasingly fine-grained discretization of the input space. In experiments with standard benchmarks, our algorithm shows comparable or better performance to existing techniques, yet it does not build an explicit model of a system. Instead, at each decision point within a single trial, it makes an uninformed probabilistic choice between simple strategies to extend the input signal by means of exploration or exploitation. Key to our approach is the way input signal space is decomposed into levels, such that coarse segments are more probable than fine segments. We perform experiments to demonstrate how and why our approach works, finding that a fully randomized exploration strategy performs as well as our original algorithm that exploits robustness. We propose this strategy as a new baseline for falsification and conclude that more discriminative benchmarks are required.

Original languageEnglish
Article number3459605
JournalACM Transactions on Modeling and Computer Simulation
Volume31
Issue number3
DOIs
Publication statusPublished - Jul 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modelling and Simulation
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Falsification of Hybrid Systems Using Adaptive Probabilistic Search'. Together they form a unique fingerprint.

Cite this