Time-Staging Enhancement of Hybrid System Falsification
For researchers and engineers working on verification of hybrid systems, this incremental method improves falsification efficiency.
The paper introduces time staging, a technique that enhances optimization-based falsification of hybrid systems by exploiting the time-causal structure of signals, showing dramatic performance increases in realistic examples.
Optimization-based falsification employs stochastic optimization algorithms to search for error input of hybrid systems. In this paper we introduce a simple idea to enhance falsification, namely time staging, that allows the time-causal structure of time-dependent signals to be exploited by the optimizers. Time staging consists of running a falsification solver multiple times, from one interval to another, incrementally constructing an input signal candidate. Our experiments show that time staging can dramatically increase performance in some realistic examples. We also present theoretical results that suggest the kinds of models and specifications for which time staging is likely to be effective.