Wasserstein Generative Adversarial Networks for Online Test Generation for Cyber Physical Systems

The input to the simulator is a sequence of points in the plane which the provided simulator interface interpolates to a road. See Figure 1 for roads defined by $6$ points. Not all sequences are valid: intersecting roads and roads with steep turns are disallowed. Moreover, a road must fit in a map of $200\times 200$ units. An efficient black-box validator for candidate roads is provided by the SBST 2021 CPS competition (Panichella et al., 2021).

Generating valid tests by randomly choosing sequences of plane points is difficult, so we opted to use the feature representation described in (et al., 2021). For us, a test is a vector in $\mathbb{R}^{d}$ whose components are curvature values in the range $[-0.07,0.07]$. Given a test, we fix the initial point to be the bottom midpoint of the map and the initial direction to be directly up. Then we numerically integrate the curvature values with a fixed step length $15$ to obtain $d$ more points. Fixing the initial point and direction is justified by noting that the test fitness (maximum $\mathsf{BOLP}$) should be translation and rotation invariant.

This feature representation makes random search of valid roads more feasible. In our experiments, we set $d=5$ and we estimated that then the probability of a test being valid equals $0.48$. On the other hand, we estimated that a sequence of $6$ plane points with components chosen uniformly randomly in $[0,200]$ corresponds to a valid road with probability $0.0036$. For both estimates, we generated $5000$ random roads.

Let $\mathcal{T}$ be the set of failing tests in the test space $[-0.07,0.07]^{d}$. Our aim is to learn online a mapping $G$ from a latent space $[-1,1]^{d^{\prime}}$ to the test space such that uniform sampling of the latent space yields samples of $\mathcal{T}$ via the map $G$. To achieve this, we train this generator $G$ as a WGAN (Arjovsky et al., 2017). In this setting, $G$ is a neural network and it is trained to minimize the Wasserstein distance between the distribution of $G$ and the real data distribution $\mathcal{T}$. This is accomplished with the help of a critic $C$ (also a neural network) which, informally speaking, is trained to distinguish between tests in $\mathcal{T}$ and outside of it.

Training the WGAN traditionally requires having a training data sample from $\mathcal{T}$ in advance. Since we do not have such data, an alternative approach is needed. We propose to begin from a set $\mathcal{R}$ of random valid tests and update it using an analyzer $A$ (also trained online). We execute the tests of $\mathcal{R}$ on the SUT to know $f(t)$ for all $t\in\mathcal{R}$. We use this data to train $A$ (a neural network) to approximate the mapping $f$. We may now use the generator $G$ to produce valid tests and estimate their fitness by $A$ without consulting the SUT (recall that a validator is available). When we have found a valid test which is estimated by $A$ to have high fitness, we execute it on the SUT and add the test and its outcome to $\mathcal{R}$.

Training the WGAN directly on $\mathcal{R}$ treats all tests equally which is counterproductive as $\mathcal{R}$ can contain many low-fitness tests. We propose to create a training batch from $\mathcal{R}$ which is biased towards high-fitness tests and train the WGAN on it. Ideally $G$ becomes more able to generate high-fitness tests and $A$ gets more accurate as more data is available. The analyzer $A$ does not need to be perfect; it just needs to drive the training towards high-fitness tests.

It has been observed that WGANs, like GANs, can produce novel variations of their training data (Arjovsky et al., 2017) so, whenever the fitness function $f$ is well-behaved on the test space (e.g., it is locally continuous) and the random search is representative enough, the generator should eventually produce high-fitness tests, some of which belong to $\mathcal{T}$. Failing this could be taken as an indication that faults do not exist.

Our experiments confirm that Algorithm 1 can expose many faults of the SUT of the SBST 2021 CPS testing competition showing empirically the validity of the above ideas. This achieves the first quality criterion of a test generator. WGANs have been shown to avoid the so-called GAN mode collapse in which a generator produces the same output over and over (Arjovsky et al., 2017). We observe this in our experiments as we typically find clusters of failing tests that are largely different from each other. This achieves the second quality criterion.

Let us explain the pseudocode of our WOGAN algorithm Algorithm 1. Its main structure is similar to the OGAN algorithm of (Porres et al., 2021). Initially a population of $N$ random tests is created and executed on the SUT. On each round of the outer loop, the analyzer $A$ is trained on the current tests $T$ and their fitnesses $F$, and the WGAN consisting of the generator $G$ and the critic $C$ is trained on a biased batch of samples from $T$ (see the next paragraph). Then candidate tests are produced by $G$ in the inner loop until a valid test whose fitness $A$ estimates to be high enough has been produced. The acceptance threshold is lowered on each iteration in order to find suitable candidates reasonably fast. The accepted test is added to the test suite along with its fitness. Finally a parameter $\alpha$ controlling the biased batching is updated. The algorithm terminates when the time budget is exhausted.

Let us then describe how the biased batches are formed. Partition the interval $[0,1]$ (the range of $f$) into $B$ contiguous bins of length $1/B$. Put each test in $T$ to a bin according to its fitness. We weight the bins and sample $M$ bins ($M$ is the batch size) according to this weighting. The biased batch is formed by choosing a test uniformly randomly (without replacement) from each sampled bin. The weights are chosen according to a shifted sigmoid function $1/(1+\exp(-(x+\alpha)))$. The parameter $\alpha$ increases linearly from $0$ to $3$ during the execution. Thus initially low-fitness tests have a chance of being selected, encouraging exploration, whereas later only high-fitness tests are likely to be sampled.

The goal of the test generation is to generate a test suite with as many failing tests as possible within a time budget of $2$ hours. A test is considered failed if its fitness (maximum $\mathsf{BOLP}$) exceeds $0.95$. No speed limit is imposed on the simulator AI. We report the results of $20$ repeated experiments for each algorithm.

We use the version $0.24.0.1$ of the BeamNG.tech simulator as in the current 2022 iteration of the competition. The lane assist AI used is the one provided by BeamNG.tech. The data was collected on a desktop PC running Windows 10 Education with Intel i9-10900X CPU, Nvidia GeForce RTX 3080 GPU, and 64 GB of RAM.

We train the WGAN using gradient penalty as in (Gulrajani et al., 2017). The critic and generator both use a dense neural network of two hidden layers with $128$ neurons and ReLU activations. The analyzer has two hidden layers with $32$ neurons and ReLU activations. The WGAN is trained with the default settings of (Gulrajani et al., 2017) and learning rate $0.00005$ as suggested in (Arjovsky et al., 2017). The analyzer is trained with the Adam optimizer with learning rate $0.001$ and beta parameters $0$ and $0.9$. These settings yielded good performance, but we did not attempt to determine the best parameters empirically.

We updated the Frenetic algorithm to use the latest version of the simulator. We also set the number of roads for the initial random search to $60$ which is the same as in WOGAN. Due to the changes, we consider that the version of Frenetic used in this article is not equivalent to the one presented in (et al., 2021) and its results are not comparable.

Notice that Frenetic produces roads defined by variable number of points. Its random search builds roads with $20\pm 5$ points and the genetic algorithm rules can change this number. As stated above, WOGAN considers only roads defined by $6$ points which is a much lower number. We opted not to change Frenetic in order to keep our modified Frenetic as close as possible to the original.

The results indicate that our approach can achieve performance comparable to an algorithm using more domain-specific knowledge. Thus we have experimentally validated that our WOGAN algorithm fulfills the first quality criterion of finding many failing tests.

The diversities of the test suites are reported in Figure 3 and additional statistics are found in Table 1. Intuitively the set of failing tests for random search should be diverse. Therefore Figure 3 indicates that WOGAN and Frenetic both succeed at producing reasonably diverse failing tests according to the selected diversity measure. The diversity values for WOGAN and Frenetic are statistically different (at significance level $0.05$): the Wilcoxon signed-rank test reports a $p$-value of $0.0001$ under the null hypothesis that the median of differences is $0$. We remark that the roads generated by Frenetic are based on a higher number of plane points, so they are by nature more varied. We conclude that we have shown evidence that WOGAN fulfills the second quality criterion of being able to generate diverse failing tests. It is true that the data suggests that WOGAN removes diversity, but accurately assessing the situation would require a deeper study of the tradeoffs between our conflicting quality criteria.