{'fraction_non_alphanumeric': 0.03610675039246468, 'fraction_numerical': 0.01103202081675663, 'mean_word_length': 4.681368356750153, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Falsification of Cyber-Physical Systems using Bayesian Optimization

Cyber-physical systems (CPSs) are usually complex and safety-critical; hence, it is difficult and important to guarantee that the system's requirements, i.e., specifications, are fulfilled. Simulation-based falsification of CPSs is a practical testing method that can be used to raise confidence in the correctness of the system by only requiring that the system under test can be simulated. As each simulation is typically computationally intensive, an important step is to reduce the number of simulations needed to falsify a specification. We study Bayesian optimization (BO), a sample-efficient method that learns a surrogate model that describes the relationship between the parametrization of possible input signals and the evaluation of the specification. In this paper, we improve the falsification using BO by; first adopting two prominent BO methods, one fits local surrogate models, and the other exploits the user's prior knowledge. Secondly, the formulation of acquisition functions for falsification is addressed in this paper. Benchmark evaluation shows significant improvements in using local surrogate models of BO for falsifying benchmark examples that were previously hard to falsify. Using prior knowledge in the falsification process is shown to be particularly important when the simulation budget is limited. For some of the benchmark problems, the choice of acquisition function clearly affects the number of simulations needed for successful falsification.


Introduction
Cyber-physical systems (CPSs) [1] are often both complex and safety-critical. A commonly used approach for assessing correctness is testing. The main objective is to find inputs that falsify given specifications; such inputs define counterexamples.
For many industrial systems, no explicit mathematical models are available for analysis, and only simulations of the system are possible. Thus, in this paper, we assume that a black-box model that represents the system under test (SUT) is available, and the black-box model can be simulated. For many industrial CPSs also, simulating the system might be computationally expensive, and it is thus desirable to reduce the number of simulations needed during falsification. In simulation-based falsification using optimization, the objective is to reduce the number of tests, i.e., simulations, by using an optimization method to decide on the next set of input signals from evaluating the results from previous simulations. A key challenge is selecting an efficient optimization method and the type of information that an optimizer should use to decide on the next set of input signals. When the SUT is given as a black-box model, the optimization A different and more practical approach would be to use an approach that does not require input from the practitioner. TuRBO [13] is such a method that is based on trust regions. A trust region (TR) [14] is a subset of the input space centered at the current-best solution where the objective function is approximated locally. Instead of focusing on a linear embedding, TuRBO searches the objective function locally with a sequence of local optimization runs. Using trust regions where a probabilistic model is trained similarly to the global BO framework helps against overexploiting and thus provides a balance between exploration and exploitation. In some practical applications of falsification, the objective function can be constant in large regions and may have discontinuities. In such situations, vanilla BO would have difficulties learning anything credible. However, this limitation can be easily omitted by shrinking the search locally within a trust region as done in TuRBO. Even though the final performance of BO depends crucially on the selection of an acquisition function (i.e., how exploration and exploitation of the search space are done in BO) [15,16,17], the current literature for falsification using BO mostly neglects this effect. Depending on an application, there can be a preference for one acquisition function over another. Moreover, an algorithm's performance heavily depends on how well the acquisition function balances exploration and exploitation. For example, one acquisition function can be used to emphasize model uncertainty more than the prediction, while another acquisition function can be used to accelerate convergence but might stagnate easily. To address this issue, in addition to the default choice with Thompson Sampling (TS) [15], TuRBO is modified, as part of this work, to use the lower confidence bound (LCB) [16], and an adjusted version of the probability of improvement (PI) [17] that emphasizes more failure events as our primary goal is to find configurations that falsify the SUT.
For certain falsification problems, there is prior knowledge about where a falsified point can potentially be located. Such an example is corner points, i.e., values at the boundaries of the allowed input ranges, that are shown to be likely to falsify many falsification problems; this is further discussed in [18]. In such situations, prior knowledge can be incorporated into the model-based method to increase efficiency. The recent works, BOPrO [19] and πBO [5] propose how to incorporate the prior injection about the optimal solution in BO, which allows the practitioner to emphasize certain regions that potentially a falsified point can be located. The methods can forget incorrect prior knowledge and eventually converge to an optimal solution. To our knowledge, injecting a prior belief about the falsifiable area has never been evaluated for falsification of CPSs.
These mentioned limitations and shortcomings can be one of the reasons why BO has not yet received much attention in the falsification community. Moreover, since the initial work [9] on BO was proposed a few years ago, the new standard benchmark problems for falsification have emerged [20,21]. Therefore, a new study on BO optimization for falsification is necessary. We make the following contributions: (i) We study state-of-the-art Bayesian optimization methods for the falsification of cyber-physical systems. (ii) We present a detailed acquisition function analysis and tailor it to model the structure of the falsification problem setting. (iii) We perform a comprehensive evaluation on a representative collection of benchmarks demonstrating that Bayesian optimization outperforms the state-of-the-art falsification methods for some specifications and examples. This paper is organized as follows: Section 2 reviews the related work briefly. Section 3 introduces the first falsification process briefly, then the BO method. Section 4 introduces the used methods in this paper. The evaluation results on the benchmark examples are discussed in Section 5. Finally, Section 6 summarizes the contributions.

Related Work
In [22,18], both optimization-free and optimization-based methods were evaluated for falsification. Optimization-free methods include random search, approaches based on evaluating extreme values within the allowed parameter ranges, termed corners, and a combination of these.
While SNOBFIT [23], a model-based approach, showed the best performance for falsification in [22], a direct-search method named Line-Search falsification (LSF) [18], developed specifically for falsification problems was, in general, more efficient on falsification than SNOBFIT. LSF was proposed following the good performance of the randomness properties in different fields together with explicit prioritization of boundary cases of the parameter space. Simply put, LSF combines random exploration with local search by generating random lines in the parameter space and optimizing over line segments. Even though the LSF method could falsify most benchmark examples with fewer simulations better than others, it is a direct-search method that does not try to learn a surrogate model of the objective function.
Previously, BO has been studied for falsification of CPSs in [9,24,25,26]. In [24], BO was adapted to be used for conjunctive requirements where the focus was on solving problems with many requirements. In [25], the Gaussian process upper confidence bound (GP-UCB) was used for the falsification of conditional safety properties, which means that whenever an antecedent condition holds, a safety property should hold. In order to find the region of the input search space in which the antecedent condition holds, Gaussian process regression was used. The GP-UCB algorithm for conditional safety was further improved in [26] by focusing on points that satisfy the antecedent. GP-UCB approach can be used for moderate dimension spaces of approximately up to 10 dimensions. For high-dimensional parameter spaces, however, this method is infeasible. In [9], REMBO, which is the first proposed BO method suitable for high-dimensional problems, is used for falsification of CPSs. REMBO uses a random linear embedding to create a low-dimensional subspace suitable for BO. In [9], it is shown that BO is comparable w.r.t. other optimization methods such as CMA-ES [27] for falsification of CPSs. REMBO uses a random linear embedding to create a low-dimensional subspace suitable for BO. In REMBO, a Gaussian process model is trained on a low-dimensional space where the original high-dimensional input space for evaluations is derived via inverse random projection. As a result, the points outside the search domain are convex-projected to the boundary, upper or lower bound, leading to over-exploration of the boundary region. However, defining the optimal size of a linear embedding in REMBO is a challenging task in practice. Moreover, in [9], the authors used different low dimension evaluations for each example, and there is no clear suggestion on which is optimal. In addition, the benchmark examples used in this work have been replaced by new benchmarking problems used in the falsification community [20,21]. The limitations of REMBO, such as a nonlinear distortion in the objective function and having a low probability that a linear embedding can contain an optimum, are addressed in ALEBO [12] by utilizing a Mahalanobis kernel and sampling a linear embedding from the unit hypersphere. Alternatively, a linear embedding can be defined using hashing and sketching as done in HeSBO [11]. However, the performance of both methods still heavily depends on the optimal selection of the size of a linear embedding which is challenging to know in practice.
Instead of defining a low-dimensional embedding that is challenging in practice, methods such as TuRBO [13], that use trust regions to build surrogate models locally, can be used. A Gaussian process model can be trained more efficiently by splitting an ambient space into multiple trust regions. In particular, TuRBO is found to be one of the most effective methods evaluated in [28] for tuning hyperparameters.
Despite being a popular method for optimizing expensive black-box functions, BO does not incorporate the expertise of domain experts if it is available. In this situation, BO wastes function evaluation on bad design choices that the expert already knows will not work. Hence, [19,5] propose BO methods, which allow the practitioner to inject their knowledge into the optimization process as priors about what parts of the input space are more promising to exploit. In [19], a user-provided prior distribution is combined with a data-driven model to form a pseudo-posterior. Still, this approach does not allow arbitrary priors to be integrated. Further, this method is not allowing different acquisition functions. A generalized approach, πBO, is proposed in [5] to address these issues. In contrast to other works, while being conceptually simple, πBO can easily be integrated with existing BO works and different acquisition functions. Furthermore, the work provides a theoretical guarantee proving convergence at regular rates independently of the prior.
In this paper, we investigate how TuRBO, a BO method for high-dimensional problems, and πBO, a BO method for including prior knowledge, can be used for falsification. We propose the modification of the TuRBO method with different acquisition functions and evaluate them on benchmark problems and compare them with other state-of-art methods.

Falsification of Cyber-Physical Systems
The process of optimization-based falsification is shown in Fig. 1. Initially, a generator creates input signals to the system based on an input parametrization. The input parameters x ∈ R n with n, as the number of parameters, are used to generate an input trace describing a sequence of input vectors, x s i [k], where k ranges from the start to the end of the simulation, for the input signals. For example, a sinusoidal signal can be parameterized using the amplitude and the period or a piecewise constant signal by the values and time instants at which the signal changes value. Next, a simulator generates simulation traces of output signals x s o , where the SUT is simulated with the x s i as inputs. x s , the combination of both x s i and x s o are used with the specification ϕ, possibly containing temporal operators, to evaluate the specification using a quantitative semantics.  [29].
A quantitative semantics determines whether the specification is satisfied and a measure of to what extent the specification is fulfilled. If the specification is falsified, the process ends. However, if it is not falsified, a parameter optimizer generates a new set of parameters for the input generator, and a new simulation of the system takes place. Mapping between the input parametrization and the objective value y ∈ R of the selected quantitative semantics is taken as a black-box function f ϕ (x s ) : X −→ R. A common convention in falsification is to let y = f ϕ (x s ) < 0 denote that the specification is falsified. Thus, minimizing the objective function f ϕ (x s ) should guide us to a point with f ϕ (x s falsified ) < 0 if the system is possible to falsify. With slight abuse of notation, we will write f (x) as shorthand for f ϕ .
In falsification, the specification is often modeled using signal temporal logic (STL) or metric interval temporal logic (MITL) with their quantitative semantics defined in [30] and [31], respectively. In this paper, STL specifications are used.

Signal Temporal Logic
The syntax of STL [32] is defined as follows: where the predicate µ is µ ≡ µ(x s ) > 0 and x s is a signal; ϕ and ψ are STL formulas; [a,b] denotes the globally operator between times a and b (with a < b); ♦ [a,b] denotes the finally operator between a and b.
The satisfaction of the formula ϕ for the discrete signal x s , consisting of both inputs and outputs to the SUT, at the discrete-time instant k is defined as: Two quantitative semantics defined for STL are Max and Additive. Both of these can be expressed in terms of VBools [29], but in this paper, we focus on using Max since it is the most widely used quantitative semantics in falsification. A VBool v, z is a combination of a Boolean value v (true , or false ⊥) together with a real number z that is a measure of how true or false the VBool is. This value will estimate how convincingly a test passed or how severely it failed. The quantitative semantics defines this value.
The and-operator is defined as Using the de Morgan laws, the or operator can be defined in terms of and, as: The always operator over an interval [a, b] is straightforwardly defined in terms of and-operator, as where ϕ is a finite sequence of VBools defined for all the discrete-time instants in [a, b].
Furthermore, the eventually operator is for both semantics defined over an interval [a, b] in terms of always-operator, as:

Bayesian Optimization
BO [4] assumes a probabilistic belief about the mapping between the input parametrization x and the objective value y. Designing an acquisition function guides the optimization procedure to the optimal solution by selecting adequate configurations for evaluation. While different regression models such as random forest can work as a surrogate model, a probabilistic model in BO is typically based on Gaussian processes regression [33]. In principle, Gaussian process regression defines the output of a simulation-based falsification as p(y) = GP(y; µ, K), where µ is a prediction mean value, and K is a covariance that returns similarity between points where σ( We summarize the main steps of BO for falsification in Algorithm 1. At the start, we need to evaluate the objective function f (x) on an initial number of samples that is noted here as M , line 1. Defining the initial points in the search space X ⊆ R n , where n is the dimensional parameter space, is typically done by randomly selecting parameters within the allowed range, line 3. After evaluating f (x), if the specification is falsified at any of the initial samples, lines 4-5, the algorithm terminates with the falsified point. Otherwise, we create the initial sample set based on an initial probabilistic model, line 7. Using the trained probabilistic model, we can decide which configuration to evaluate next.
A key challenge is a trade-off between exploring regions of the parameter space not yet explored versus investigating areas around the most promising parameter values yet found. This trade-off is called the exploration-exploitation dilemma. Balancing adequately between exploring yet unexplored areas and exploiting promising regions determines the efficiency of the falsification process. Too much exploitation results in a greedy optimization where a surrogate model can easily be trapped in a local minimum. Vice versa, too much exploration would result in an inefficient performance where a surrogate model evolves with every new iteration without any exploitation. Therefore, an acquisition function that balances exploration vs. exploitation is used to select the next configuration for evaluation. Since an acquisition function is built on top of a surrogate model with a clear analytical form, optimizing it can be done efficiently. In general, acquisition functions come with different concepts in exploring and exploiting, which we discuss in Section. 4.

Algorithm 1 Bayesian Optimization for falsification
1: Input: Input space X ⊆ R n , the initial design size M , the max number of simulations N . 2: Output: A falsified design -if possible, to find within the given simulation budget.
, {Sample random configurations from the uniform distribution and evaluate using simulation.} 4: if the specification is falsified at one of {xi} M i=1 then 5: return The falsified point {Falsification is successful.} 6: else 7: {Collect the initial design set.} 8: for (j = 1, 2, . . . , N) do 9: x * ←− argmin x∈X α(x, Dj−1) {Train a probabilistic model as p(y|D) = GP(y; µ y|D , K y|D ) with Dj−1 and find the next configuration x * .} 10: y * ←− f (x * ) {Evaluate the objective function by using simulation followed by the quantitative semantics.} 11: if y * < 0 then 12: return x * {Falsification is successful.} 13: else 14: The algorithm selects the next configuration x * for evaluation by optimizing a predefined acquisition function, line 9. Once evaluated by simulating the SUT with the generated input from the parameters x * , the corresponding objective value y * is checked, line 10. If y * < 0, we have found a falsifying configuration, and the optimization procedure ends, lines 11-12. Otherwise, the sample set D is updated, lines 13-14, and the previous steps are repeated. This continues until the total number of simulations, N , is exhausted, lines 8-16.

Method
The cost of using the Gaussian process for the surrogate model scales cubic with the number of samples evaluated, see [33]. High-dimensional applications typically require more evaluations to converge, so using vanilla BO in this setting becomes impractical [11,34]. Furthermore, it is noted that BO searches more the edges, the lower and upper bounds of the input ranges, of the search space in high-dimensional applications, this results in suboptimal performance [10,13]. In [13], this is mitigated by building multiple local probabilistic models in an approach called TuRBO.

Turbo
TuRBO, a trust-region BO method, utilizes a sequence of local optimization runs using independent probabilistic models to overcome the problem of overexploiting. Furthermore, an implicit multi-armed bandit strategy at each iteration addresses the global optimization where a local run is selected for additional evaluations. Locally, a hyperrectangle centered at the current best solution is created with the predefined length, which is noted as a trust region. Within these local bounds, a local surrogate model is trained. Using standard acquisition functions, TuRBO finds the best-next configuration x * for evaluation. If the best-next evaluation f (x * ) is better than the current best solution, then the trust region is expanded. Otherwise, it is shrunk. The default acquisition function used in TuRBO is Thompson sampling (TS). To demonstrate the usage of TuRBO in falsification and preferably w.r.t. the global BO methods, our work covers a detailed study on the selection of an acquisition function. As part of this work, TuRBO has been modified to work with Lower Confidence Bound (LCB) [16], and a version of Probability of improvement (PI) [17].

Thompson Sampling (TS)
TS [15] is a simple yet effective approach for handling the exploration-exploitation dilemma in Bayesian optimization. Once we have a trained surrogate model, the concept is to greedily sample a configuration from the posterior with the lowest value, and sampling from the posterior generates TS's randomness.

Lower Confidence Bound (LCB)
Each prediction made by a surrogate model comes with the confidence interval explained with a corresponding standard deviation. The standard deviation is a measure of uncertainty. Thus, LCB has been introduced to leverage this measure for exploration and exploitation. It refers to the lower bound of the uncertainty of the surrogate model. In this paper, we consider the minimization problem where the lower bound is of interest; for maximization problems, the Upper Confidence Bound (UCB) is used instead. The best-next configuration x * is [16] where the parameter β ∈ R ≥ 0 balances exploitation and exploration. Note that the arg min of a black-box function returns a set since more than one value might achieve the minimum. Small β values mean more greedy exploitation, while large values mean more exploration. Defining an optimal value for β is an open question, in this work, we use a well-known formulation used in practice [35], β = 0.125 log(2j + 1), where j is the number of simulations.

Probability of Improvement (PI)
PI [17] defines the probability that the best-next configuration x * leads to an improvement with respect to a target value τ , which ideally can be seen as the optimal solution f min . Thus, we write where Φ is the standard normal cumulative distribution function. As the optimal solution f min is unknown, τ is typically defined as the current best solution. Thus, if a potential configuration has an associated predicted value smaller than the current best solution, then the optimization procedure is not improving. Scaling the difference between the current best solution and a prediction value with the standard deviation creates the exploitation nature of PI. Because of maximizing the improvement, the best-next x * is In the literature, the fraction in Eq. (3) is sometimes referred to as the U-function [36]. Instead maximizing Eq. (3), we can minimize the U-function as The formulation in Eq. (4) with the absolute value of |µ(x * ) − τ | is also found in reliability analysis, where the objective is to approximate the probability of failure. Using the absolute value here improves the threshold between failure and non-failure events. In reliability analysis, the best-next configuration x * close to τ from any side is sufficient for evaluating [36,37]. As we are only interested in falsification for CPSs (i.e., having values less than 0), defining τ ≤ 0 emphasizes failure events [36,37]. In the present study, we experiment with two choices, τ = 0 and τ = 1.

Incorporating prior belief
In certain situations, the practitioner has an available prior belief about the potential location of the optimum [19,5]. While this source of information might be available, vanilla BO fails to incorporate it. Therefore, the work previously done in [19,5] proposed how to modify BO to inject this prior. In particular, the latest algorithm πBO [5] is conceptually simpler w.r.t. the previous work. The objective is to modify an acquisition function by multiplying it with a predefined probability distribution π(x) as for the j-th iteration with j ∈ {1, . . . , N }. β * ∈ R + is a hyperparameter that is used as the practitioner's confidence about the prior knowledge. Here, a probability distribution π(x) serves to describe our belief about the optimum. For example, in falsification, falsified points for several benchmark examples are located at the edges of the search space, making it easy to falsify if this information is known [18]. Therefore, in the present study, we defined π(x) as a U-shaped distribution where the edges are weighted more than the inside area. Even though the prior can be wrong, BO can still converge the optimal solution as a result of the forgetting factor in Eq. (5) as proven in [5]. By raising π(x) in Eq. (5) to a power of β * /j, the wrong prior decays towards zero with growing j.

Experimental Evaluation
We evaluate the proposed BO methods on benchmark examples from [20], and [21] which are introduced briefly in appendix A. For the benchmark problems in [20], two variants of input signals are considered Instance 1 and Instance 2, respectively. Instance 1 allows arbitrary piecewise continuous input signals, while Instance 2 is restricted to constrained input signals. The problems such as AT, CC, NN, and SC include both Instance 1 and Instance 2 type, while the problem AFC, WT, and F16 do not include different types of instances. Additionally, three benchmark problems from [21] are included, i.e., AT , modulator ∆ − Σ, and SS.

Experimental Setup
The performance of the proposed BO methods compared to vanilla BO is compared against state-of-the-art methods found in the literature, such as HCR (i.e., an optimization-free method) and line-search falsification LSF method (i.e., a direct-search optimization method). We set up the experiments using Breach [38], with Max semantics [30,29]. As BO methods require a set of initial samples to start the process, we set the initial number of samples to 2 · n, where n is the number of input parameters (i.e., the dimensionality of the optimization problem). For the LSF method, the maximum number of iterations to improve a single line is set to three. The presented results for LSF use Option 4, which works with lines extending beyond the boundaries of input ranges and thus has a higher chance of resulting in corner values; see [18] for more details. The HCR method starts with a corners point, and the next point is a uniform random (UR) point. It switches between the corners and UR points until the maximum number of simulations, N = 1000, is reached or a falsified point is found. The number of corners is limited and depends on the dimensionality of the SUT since there are 2 n corners. If the maximum number of corners is reached, HCR continues using only random input points.
In Tables 1-2 In these tables, the first column denotes the specifications; the second refers to which instance is used to evaluate the specification. The third column shows the number of dimensions, and the rest of the columns contain the evaluation results for vanilla BO, TuRBO with the different acquisition functions TS, LCB, and PI; πBO, LSF, and HCR, respectively. Two different target values are considered for PI, τ = 0, and τ = −1. Each falsification is set to have 1000 maximum number of simulations. Since the falsification process contains random elements, we repeat the falsification process 20 times. Two values are presented for each specification; the first is the relative success rate of falsification in percent. There are 20 falsification runs for each parameter value and specification; thus, the success rate will be a multiple of 5%. The second value, inside parentheses, is the average number of simulations (rounded) per successful falsification.

Results
While Table 1 includes the benchmark examples that can be easily falsified using a straightforward approach such as HCR, Table 2 covers the hard examples and specifications where the number of simulations to falsify easily exceeds the maximum simulation budget [18]. In particular, in Table 1, these selected specification are ϕ AT 6 -ϕ AT of this example performs as well as HCR and better than other optimization-based methods. When vanilla BO is used for high-dimensional applications, exploration of the edges is more frequent because optimizing an acquisition function is difficult and prone to significant errors. Hence, vanilla BO searches for more edges and likely more corners. As a result, vanilla BO falsifies ϕ AT 2 within a few simulations. On the other hand, πBO also shows a good performance here because it emphasizes more the corners following our prior U-shaped distribution. TuRBO is prone to explore fewer corner points as the search is limited to local trust regions. In particular, TS is not always successful, while PI and LCB require more simulations than HCR and vanilla BO. (ω = 3500) performing among the top optimization-based methods, but not better than HCR that only require 5 simulations.
For ϕ CC 2 of instance 2, πBO and vanilla BO work similarly to HCR and much better than other optimization-based methods. This specification can be falsified at some of the corner points. Among TuRBO results, PI (τ = −1) and TS perform better than LCB and PI (τ = 0), which are successful only 90% and 75%, respectively.
The benchmark example ϕ N N 2 is falsified with HCR with 100% and using 83 simulations on average. In contrast, vanilla BO is the only optimization-based method that is successful in each independent trial. Based on the evaluation of falsified points, we observe that this specification is falsifiable where at least some input parameters are at the upper or lower bound of input ranges. Hence, vanilla BO and HCR performed better than TuRBO. TuRBO never evaluates the corner points, or the points are on the bound of the input ranges. However, πBO does not falsify efficiently, only 35% are successfully falsified; it might be because the number of dimensions is increased, and hence the efficiency of πBO drops.
SS is a two-dimensional synthetic example that tricks the optimizing algorithms that try to estimate gradients to search in the wrong direction. For all specifications of SS, HCR, vanilla BO, LSF, and importantly πBO provide better results than TuRBO. Both input parameters are defined within the range [−1, 1] in this special case. The target specification is falsified at the corner point x T = [1, 1] and close to it. The gradient cannot point toward the falsification area if the initial samplings of First Input and Second Input are approximately in the ranges (−1, 1) and (−1, 0.8), respectively when γ = 0.7, which is a threshold parameter in this example. Hence, the three methods HCR, vanilla BO, LSF, and πBO that can search the corner points which lead that all falsify this example better than TuRBO. On the other hand, TuRBO searches more within the input ranges. Thus, it is difficult for TuRBO to approach the failure area with a local hyperrectangle trust region that is centered at the best solution found. A larger value for γ such as (γ = 0.8) and (γ = 0.9) results in a smaller failure surface. Thus, the performance of TuRBO drops additionally with the best performance with PI (τ = 0) as 70% and LCB as 55% for (γ = 0.8) and (γ = 0.9), respectively.
Next, we discuss the benchmark examples noted here as the hard examples because an optimization-free method such as HCR cannot falsify them. The results are provided in Table 2. For the specifications, 7-9, of AT example, HCR, vanilla BO, and πBO cannot falsify them. These specifications are not falsifiable close to corners or edges. In particular, emphasizing the corners as done in πBO is wrong. However, as a result of the forgetting factor, πBO still converges to the optimal solution as it was successful in only one run out of 20 runs in ϕ AT 7 . Like any other global BO approach in a high-dimensional setting, the efficiency of πBO eventually drops significantly as the bias of a Gaussian process to exploit the edges of the search space is emphasized. In TuRBO, this shortcoming is handled, as shown in the results for the hard examples. In TuRBO, the training of a Gaussian process is done locally within a trust region that shrinks and expands based on the performance. Hence, the inherent presence of regions with large posterior uncertainty commonly found in the global BO approach due to the curse of dimensionality is reduced. The performance of TuRBO is similar regardless of the acquisition function used. Compared to LSF, more simulations are needed.
In the AT , we can see a clear advantage of TuRBO over other BO methods and state-of-the-art approaches. For ϕ AT 6 , with both (T = 10), (T = 12), LCB is successful in each run, with 161 and 43 average on simulations respectively, while LSF is only successful 30 and 95%. Another BO method, πBO, also demonstrates a good performance for ϕ AT 6 , with 95% success rate when (T = 10) and 100% when (T = 12). Because the dimensionality for these specifications is moderate, πBO forgets the wrong prior and eventually converges to the falsified areas. Vanilla BO is not successful in falsifying these specifications because simulations are mostly evaluated at the edges that are not falsifiable. ϕ AT 7 is one specification that is a hard example to be falsified with a specific feature. The STL formula of this specification is ϕ AT 7 = ¬ ( [0,1] gear == 1) ∧ ( [2,4] gear == 2) ∧ ( [5,7] gear == 3) ∧ ( [8,10] gear == 3) ∧ ( [12,15] gear == 2) . In general, it is impossible to determine how close we are to fulfilling equality predicates, such as gear == 1, gear == 2, or gear == 3. In other words, if the gear is 1, for example, the objective value using Max semantics will be a positive constant value if the specification is fulfilled, otherwise, a negative constant value. For simplicity, we assume that the positive constant value is 1 while the negative constant value is -1. In this specification, always-operators are combined in one big conjunction. The first always-operator checks to see whether gear == 1 between t = 0 sec and t = 1 sec or not. If it is satisfied, the always-operator has the total objective value min([1, 1, . . . , 1]) = 1, which means that the gear is always equal to 1 in t = [0, 1]. Similarly, for the gear == 2 and gear == 3 at other times, the specification has a positive constant value of 1. On the other hand, if the specification is not satisfied at any time we will have something like min([1, −1, . . . , 1]) = −1. Since the Max yields the same value for different inputs, model-based methods such as BO cannot learn anything meaningful to sufficiently explore and exploit the given search space. The main assumption of BO is that the target function should be sufficiently smooth. TS and PI (τ = 0) provide slightly better performance compared to LCB and PI (τ = −1) with a 45% success rate. Because TS puts more emphasis on exploitation than other methods, it is expected to show better performance. Other methods balance equally between exploitation and exploration, which is useless in this specific case. Even though the learning is not adequate,TuRBO, and πBO can still falsify this example but not always, as shown in Table 2.
For both instances in ϕ CC 4 , we see a significant advantage of using TuRBO w.r.t. other optimization-based or optimization-free methods. For Instance 1, there is not much difference between the performance of TuRBO with different acquisition functions, although LCB performs slightly better with 80%. TuRBO performs much better than other optimization methods, e.g., 40% increasing rate than LSF. For Instance 2, there is a difference between the performance of PI when the target value is specified differently. By evaluating the objective value of the falsified point in each run of this specification, we could understand that the global optimum is close to and less than −1. Hence, having a target of 0 does not provide good results. This specification was one of the hardest benchmark examples evaluated in [18] where the proposed method, LSF, was able to falsify ϕ CC 4 in 10% of the runs. As it can be seen from Table 2 Table 2. The plotted values show how many successful falsifications (x-axis) were completed in less than always simulations (y-axis, logarithmic scale).
fewer simulations for falsification than other methods and has a success rate of 95%. Based on the evaluation collected from this example, we could conclude that the falsification, in this case, happens in a small region of the search space. Therefore, random approaches might not be a good choice to find this small region. A target of −1 is appropriate since the minimum achievable object value is close to -1.
In the benchmark example ϕ N N 2 (Instance 2), LSF performs the best with the success rate of 45%, exceeding especially TuRBO with 5, 10, and 15%. Based on the evaluation of the falsified point, there are reasons why all other methods are not successful in falsifying for each trial. First, this specification is falsifiable, where at least some input parameters are at the upper or lower bound of the input interval. The falsifiable region is small, close to the boundaries.
For the modulator example, vanilla BO and πBO slightly work better than others in falsifying each trial. These results demonstrate that πBO works well when the number of dimensions is relatively small. For F 16, TuRBO with PI (τ = 0) provides a better result with a success rate of 85% compared to other methods.
To examine and study the performance of different optimization-based methods, an aggregated comparison is provided in Fig. 2 with the hard specifications presented in Table 2. As shown in Fig. 2 and evident from our early discussion, TuRBO falsifies more benchmark examples with fewer simulations if we select LCB w.r.t. other acquisition functions such as PI (τ = −1), PI (τ = 0) and the default TS. TuRBO with LCB falsified 5 specifications out of 11 that are specified as the hard examples in Table 2 with the success rate of 100%, while TS and PI (τ = −1) could falsify four specifications similarly as LSF. PI (τ = 0) falsified 2 specifications similarly to πBO. On the other hand, vanilla BO is successful only for one specification in each trial. By taking the average of these success rates, we can see that LCB provides the best performance on average, with a success rate of 79.55%. Other acquisition functions have the average success rate as follows TS with 75.90%; PI (τ = −1) with 75.45%, PI (τ = 0) with 69.54%, LSF with 64.54%, πBO with 38.18%, and finally, vanilla BO with 15.90%.

Discussion
The performance of each evaluated BO method depends on the SUT. vanilla BO, which is the standard global BO method, showed a good performance for those specifications and examples that can be falsified at boundaries of input spaces or corners. When the number of dimensions is high vanilla BO searches the edges more because the prediction error and the uncertainty of the surrogate model at the edges become large. On the other hand, using local regions, exploration and exploitation in TuRBO are limited to local trust regions, which results in less efficient falsification compared to vanilla BO for those easily falsifiable examples where failure points are at corners. However, the efficiency of TuRBO increases with the number of dimensions showing a remarkable performance even for hard examples that are not falsified with other methods. Compared to the other BO methods for high-dimensional settings, such as the previously proposed REMBO [10], TuRBO does not need any setup, it can be used as an out-of-box tool. The πBO allows injecting prior knowledge about a failure region. πBO has shown good performance for those examples that are easily falsified at corners due to the U-shaped distribution that was used as prior knowledge based on previous falsification experiments. Even though πBO does not scale well in a high dimensional setting, it still shows good performance for a moderate number of dimensions of the input space.
Comparing the performance of different acquisition functions in TuRBO, LCB showed the best performance. LCB depends on mean and variance, not on the target value, as PI does. A challenging aspect of the LCB is choosing the optimal value for β. TS, on the contrary, does not require any parameters to be selected. Choosing the best target value for PI is difficult as it depends on the application and knowing where the optimal value is. This information is, in general, unknown to us. While the default setting in BO is to use the best-current value, we here assume constant values of 0 and −1 to emphasize failure points. For those specifications with minimum optima between (−1, 0), PI does not perform well because it assumes that −1 is the lowest objective value and neglects the failure points having an objective value > −1 from the surrogate model, that indeed falsifies the specification. Objective function values calculated using the Max semantics can be constant in large regions. It means the same objective function value for different input parameters. Hence, optimization methods cannot get any sense of direction from the objective function. A benefit of using TS as an acquisition function is its randomness which may detect falsified points where there is no information from the objective function to guide the optimization process. As TS is focused more on exploitation, it is more efficient w.r.t. other acquisition functions.

Conclusion
In this work, we evaluate Bayesian Optimization (BO) for the falsification of cyber-physical systems (CPSs). BO learns the system under test to carefully select the next test to execute. We modify BO in several ways to make it more efficient for falsification than vanilla BO. In particular, we show how the trust region-based BO approaches can efficiently handle falsification problems with a high number of dimensions. We also show how prior knowledge can be injected into BO.
While previous work does not account for the practicality of BO, our study provides a friendly environment for a practitioner where BO can be used as an out-of-box tool. In particular, two prominent BO methods πBO and TuRBO are proposed for falsification. We provide a comprehensive evaluation demonstrating that these BO methods are efficient for solving falsification problems. As shown in our experiments, TuRBO is vastly superior to other state-of-the-art methods for specifications that are high-dimensional and difficult to falsify, and this without requiring any information from the practitioner. πBO allows injecting prior knowledge about falsification if available. For benchmark examples with a smaller number of input parameters for optimization, πBO performed as well as or even better than HCR when the specifications are falsifiable on corners or boundaries. Having a correct prior about falsification, such as the U-shaped distribution that emphasizes corners, can indeed increase the efficiency and reduce the number of simulations needed for falsification. Additionally, we covered an overall evaluation of different acquisition functions in TuRBO and proposed how to modify them for falsification. Based on the evaluation, using a LCB in TuRBO is the optimal choice as it is less challenging to set up the parameters that result in a good performance on evaluated benchmark examples.
Automatic Transmission (AT ) The two inputs to the model are 0 ≤ throttle ≤ 100 and 0 ≤ brake ≤ 500 [46]. This example has different specifications and a different input range for the brake compared to the ARCH example presented, AT . There are 7 control points for throttle and 3 for brake distributed uniformly with pchip interpolation.
Third Order ∆ − Σ Modulator The third order ∆ − Σ modulator has one input U , three states x 1 , x 2 , x 3 , and three initial conditions Static Switched (SS) The static switched system is a model without any dynamics inspired by [48] with two inputs in the range [−1, 1]. Three different values are considered for parameter γ = 0.7, 0.8, 0.9.

B Other Experiments on ARCH Benchmark
The results for the benchmark examples that can be falsified easily with a few simulations regardless of which optimization method are presented in Table 4-6. Table 4 and 5 refers to result for the specifications of AT , CC, and N N systems with Instance 1 and Instance 2, respectively. On the other hand, Table 6 includes the results for the specifications of AT , ϕ ∆−Σ 1 , W T and AF C systems that only one input instance are evaluated on them.   with Instance 2 and ϕ SC 1 with both instances in Table 7. While ϕ AT 1 , with 8 dimensions, shown in Table 4, can be easily falsified, its high-dimensional version with 40 dimensions is hard to falsify, as seen in Table 7. For the SC problem, [49] demonstrated that by combining a Simulated Annealing global search with an optimal control-based local search on the infinite-dimensional input space, it is possible to falsify this specification. However, this is not a black-box approach. In [50], the SC problem is shown to be falsified by using a pulse generator as the input generator. By optimizing over the period, it is possible to find the right period that falsifies this specification.

D An Aggregated Comparison
An aggregated comparison among all methods, including benchmark examples from the appendix, is shown in Fig. 3. In general, TuRBO shows good performance w.r.t. state-of-the-art methods. In particular, selecting LCB provides better results than LSF. However, PI and TS are less efficient than LSF, which was specifically developed to solve falsification problems.