[subfigure]position=bottom

# Misbehaviour Prediction for Autonomous Driving Systems

Andrea Stocco  0000-0001-8956-3894 Università della Svizzera
ItalianaLuganoSwitzerland<EMAIL_ADDRESS>,  Michael Weiss  Università
della Svizzera ItalianaLuganoSwitzerland<EMAIL_ADDRESS>,  Marco Calzana
Università della Svizzera ItalianaLuganoSwitzerland<EMAIL_ADDRESS>and
Paolo Tonella  Università della Svizzera ItalianaLuganoSwitzerland
<EMAIL_ADDRESS>
###### Abstract.

Deep Neural Networks (DNNs) are the core component of modern autonomous
driving systems. To date, it is still unrealistic that a DNN will generalize
correctly in all driving conditions. Current testing techniques consist of
offline solutions that identify adversarial or corner cases for improving the
training phase, and little has been done for enabling online healing of DNN-
based vehicles.

In this paper, we address the problem of estimating the confidence of DNNs in
response to unexpected execution contexts with the purpose of predicting
potential safety-critical misbehaviours such as out of bound episodes or
collisions. Our approach SelfOracle is based on a novel concept of self-
assessment oracle, which monitors the DNN confidence at runtime, to predict
unsupported driving scenarios in advance. SelfOracle uses autoencoder and
time-series-based anomaly detection to reconstruct the driving scenarios seen
by the car, and determine the confidence boundary of normal/unsupported
conditions.

In our empirical assessment, we evaluated the effectiveness of different
variants of SelfOracle at predicting injected anomalous driving contexts,
using DNN models and simulation environment from Udacity. Results show that,
overall, SelfOracle can predict 77% misbehaviours, up to 6 seconds in advance,
outperforming the online input validation approach of DeepRoad by a factor
almost equal to 3.

††copyright: none

##  1\. Introduction

Self-driving cars are one of the emerging technologies nowadays, and possibly
the standard way of transportation in the future. Such autonomous driving
systems receive data from a multitude of sensors, and analyze them in real
time using deep neural networks (DNNs) to determine the driving parameters for
the actuators.

To test such complex software systems, companies perform a limited number of
expensive in-field tests, driving a car on real world streets, or within
closed-course testing facilities (Cerf, 2018). This provides detailed sensor
data of the vehicle that are recorded, played back, and recreated within a
simulator to obtain comprehensive test scenarios. Simulation-based test
scenarios allow re-testing new autopilot releases on a large numbers of
nominal conditions, as well as challenging (e.g., adverse weather) and
dangerous circumstances (e.g., a pedestrian suddenly crossing the road), at a
low cost (Cerf, 2018).

The potentially unlimited number of testable driving scenarios, combined with
the lack of human interpretability of the internal functioning of DNNs
(Alvarez-Melis and Jaakkola, 2018), makes it difficult to predict the
vehicle’s (mis-)behaviour with respect to unforeseen edge-case scenarios.
Misbehaviours span a wide range of situations, associated with different
degrees of severity, from cases where the car does not drive smoothly (e.g.,
excessively high derivative of the steering angle over time), to safety-
critical failures and casualties (The Verge, 2019, 2016; Electrek, 2016a, b).
In this respect, promptly detecting unexpected, untested behaviours is of
paramount importance, so as to make sure that human-driven or self-healing
corrective actions take place to ensure safety.

In this paper, we tackle the self-assessment oracle problem for autonomous
driving system, i.e., the problem of monitoring the confidence level of a DNN-
based autonomous driving system in order to timely predict the occurrence of
future misbehaviours. The problem is critical because a failure in detecting
an unexpected condition may have severe consequences (i.e., a fatal crash),
whereas false alarms, even if not dangerous, may cause driver’s discomfort and
negatively affect the driving experience. Creating a self-assessment oracle
that evaluates the confidence of a DNN at runtime, and predicts whether the
system is within a low-confidence zone, is a largely unexplored research
problem.

Challenges arise because unexpected driving conditions are, by definition,
unknown at training time, otherwise they would be used to train a better DNN
(Campos et al., 2016). As a consequence, the problem being addressed belongs
to the unsupervised class of data analysis, and we have to infer the
unexpected only by looking at the normal driving scenarios. Moreover, the
ensemble of possible misbehaviours for a DNN-based system is vast and
necessarily domain-dependent, being associated with deviations from the
functional requirements.

In recent years, researchers have proposed solutions for testing autonomous
driving systems software (Gopinath et al., 2018; Gambi et al., 2019; Pei et
al., 2017; Tian et al., 2018; Zhang et al., 2018; Abdessalem et al., 2018; Ben
Abdessalem et al., 2016, 2018; Gopinath et al., 2018). A number of approaches
propose input generation techniques that produce corner/adversarial cases,
used to improve the robustness of self-driving car modules by re-training (Pei
et al., 2017; Tian et al., 2018; Zhang et al., 2018; Kim et al., 2019). Other
works target test case generation to expose faults for extreme conditions,
such as the vehicle colliding with a pedestrian (Ben Abdessalem et al., 2018),
or driving off the road (Gambi et al., 2019). All these approaches concern
offline solutions for improving the robustness and reliability of DNNs,
achieved by enhancing the training data and the autopilot module, which are
extended to include underrepresented critical scenarios. To the best of our
knowledge, no existing work is focused on online confidence estimation for
self-driving vehicles with the aim of anticipating the occurrence of
misbehaviours so as to enable self-healing procedures that can avoid future
failures.

In this paper, we propose a novel self-assessment oracle for autonomous
vehicles based on confidence estimation, probability distribution fitting, and
time series analysis. Our technique is implemented in a tool called
SelfOracle, which leverages reconstruction-based techniques from the deep
learning (DL) field to analyze spatiotemporal historical driving information.
The reconstruction error is used as a black-box confidence estimation for the
DNN. During probability distribution fitting, SelfOracle captures the
behaviour of the self-driving car under nominal conditions, and fits a Gamma
distribution to the observed data. Analytical knowledge of Gamma’s parameters
allows SelfOracle to estimate an optimal confidence threshold, as a trade-off
between prediction of all misbehaviours (the stricter the threshold, the
better), and probability of false alarms (reduced when threshold is higher).
By observing a decreasing confidence trend over time, SelfOracle can
anticipate a misbehaviour by recognizing unexpected conditions timely enough
to enable healing actions (e.g., manual or automated disengagement).

We have evaluated the effectiveness of SelfOracle on the Udacity simulator of
self-driving cars (Udacity, 2017a), using DNNs available from the literature.
We have modified the simulator to being able to inject unexpected driving
conditions in a controllable way (i.e., day/night cycle, rain, or snow). Such
injected conditions are by construction disjoint from those used to train the
DNNs. In our experiments on 72 simulations, SelfOracle is able to safely
anticipate 77% out of bound episodes/crashes, up to 6 seconds in advance. The
corresponding false alarm rate in nominal driving conditions is 1%. A
comparative experiment with the online input validation strategy of DeepRoad
(Zhang et al., 2018) shows that SelfOracle achieves substantially superior
misbehaviour prediction on all the considered effectiveness metrics (e.g.,
twice as high in terms of AUC-PR and almost three times higher in terms of
FPR).

Our paper makes the following contributions:

Technique:

An unsupervised technique for misbehaviour prediction based on confidence
estimation, probability distribution fitting and time series analysis,
implemented in the tool SelfOracle, which is available (SelfOracle, 2019).

Simulator:

An extension of the Udacity simulator to inject unexpected driving conditions
dynamically during the simulation.

Evaluation:

An empirical study showing that the reconstruction error used by SelfOracle
for time series analysis is a promising confidence metric for misbehaviour
prediction, outperforming the online input validation approach of DeepRoad.

Dataset:

A dataset of 765 labeled simulation-based collision and out-of-bound episodes
that can be used to evaluate the performance of prediction systems for
autonomous driving cars.

##  2\. Background

DNN-based Autonomous Vehicles. Self-driving cars (SDC, hereafter) have
benefited from many technological advancements both in hardware and in
software. Data gathered by LIDAR sensors, cameras, and GPS are analyzed in
real time by advanced Deep Neural Networks (DNN) which govern over the actual
maneuvers of the car (i.e., steering, braking, acceleration). In order to
manage a wide variety of driving scenarios, SDCs necessitate a large amount of
driving data, combining nominal and adversarial scenarios (BGR Media, LLC,
2018).

To date, it is still unlikely for a DNN to generalize correctly to the
plethora of driving situations met everyday by human drivers. As such, a
component monitoring the confidence of the DNN may promptly detect when the
SDC is entering a low-confidence zone, and activate healing strategies that
bring the vehicle to a safe state.

In self-driving cars, depending on the level of autonomy, the self-healing
procedure can either involve the human driver, or can be delegated to an
automated system.111https://www.nhtsa.gov/technology-innovation/automated-
vehicles-safety At both levels, early and accurate misbehaviour prediction is
an essential precondition to enable safe healing, and an overall pleasant
driving experience.

Confidence Measures in DNNs. The prediction must consider DNN uncertainties
originating from the measurements in response to possible adverse
environmental conditions in which the SDC operates. The confidence level of a
SDC can be measured through white-box or black-box techniques. White-box
monitoring of the internal behaviour of a DNN component. For simple
classifiers, measuring softmax probabilities, or information theoretic metrics
such as entropy, and mutual information (Shannon, 1948) may suffice. For more
complex networks such as those than operate on a SDC, softmax probabilities
and entropy are known to be unreliable confidence estimators (Vasudevan et
al., 2019). Moreover, white-box metrics require a transparent access to the
network, and substantial domain-knowledge for the creation of nontrivial
probabilistic models that approximate the network’s uncertainty.

Black-box techniques, differently, model the SDC uncertainty by monitoring the
relation between the current input (images) and the input data used during
training. For instance, consider a SDC which has been trained only with images
representing highways. If images representing a narrow city street are given
to the DNN, the model will still output steering angles, but ideally we would
like to warn the SDC of a drop in the confidence level. The main advantages of
black-box confidence metrics consist in being independent from the specific
SDC architecture, requiring no modifications to the existing DNN model because
they use information which is readily available for analysis, and in being,
therefore, highly generalizable. In this paper, we focus on black-box
confidence estimation, because softmax probabilities and entropy are known to
be unreliable confidence estimators to model complex DNN networks (Vasudevan
et al., 2019). We next describe autoencoders and time series analysis, which
are the main building blocks of our approach.

Figure 1. Confidence levels of NVIDIA’s DAVE-2 (Bojarski et al., 2016) in
response to changing driving scenarios. The picture shows frames captured
during the execution of the SDC along one of our testing tracks, under
different conditions: (Lap 1) sun, (Lap 2) light rain, (Lap 3) sun, and (Lap
4) heavy rain. The picture juxtaposes the reconstruction error by the anomaly
detector of SelfOracle, which is used as a proxy for the DNN confidence. We
can notice that the reconstruction error is low when the car drives under
sunny conditions (i.e., conditions similar to those observed during training),
whereas the error increases moderately with adverse conditions (the car does
no longer follow the center of the road), and grows above a given threshold
when facing heavy rainy conditions at night time (which cause the SDC to drive
off the road).

Autoencoders. An autoencoder (AE) is a DNN designed to reconstruct its own
input. It consists of two sequentially connected components (an encoder, and a
decoder) that are arranged symmetrically. The simplest form of autoencoder
(SAE) is a three-layer DNN: the input layer, the hidden layer, and the output
layer. The hidden layer encodes any given input
$\boldsymbol{x}\in\mathcal{R}^{D}$ to its internal representation (code)
$\boldsymbol{z}\in\mathcal{R}^{Z}$ with a function
$f(\boldsymbol{x})=\boldsymbol{z}$. Usually $Z\ll D$. The output layer
(decoder) decodes the encoded input with a reconstruction function
$g(\boldsymbol{z})=\boldsymbol{x^{\prime}}$, where $\boldsymbol{x^{\prime}}$
is the reconstructed input $\boldsymbol{x}$. The autoencoder minimises a loss
function $\mathcal{L}(\boldsymbol{x},g(f(\boldsymbol{x})))$, which measures
the distance between the original data and its low-dimensional reconstruction.
A widely used loss function in autoencoders is the Mean Squared Error (MSE).

The input and output layers of autoencoders have the same number of nodes. If
multiple hidden layers are used, the architecture is referred to as deep
autoencoder (DAE). The surge of novel kinds of DNNs has correspondingly
produced variants of autoencoders based on such architectures. For example,
convolutional autoencoders (Masci et al., 2011) allow learning powerful
spatial-preserving relationship within images at a lower training time with
respect to fully dense layers. Another interesting proposal are variational
autoencoders (VAE) that are able to model the relationship between the latent
variable $\boldsymbol{z}$ and the input variable $\boldsymbol{x}$ by learning
the underlying probability distribution of observations using variational
inference (An and Cho, 2015).

Time Series Analysis. Traditional feedforward DNNs assume that all inputs and
outputs are independent of each other. However, learning temporal dependencies
between inputs or outputs is important in tasks involving continuous streams
of data. Thus, a predictive model can take advantage of information from the
previous inputs/outputs, to enhance its predictive capability.

Time series analysis can be applied to the output sequence produced by a DNN
to identify the trend and predict future values. Among the numerous models
available for time series analysis, the most widely used ones are
autoregressive (AR), integrated (I) and moving average (MA) models, along with
their combinations. An AR model of order $k$ predicts the next value $x_{t}$
as a linear combination of past values $x_{t-1},\ldots,x_{t-k}$:

(1) $x_{t}=\alpha_{0}+\sum_{i=1}^{k}{\alpha_{i}x_{t-i}}+\epsilon_{t}$

where coefficients $\alpha_{0},\ldots,\alpha_{k}$ can be estimated by the
least square method and $\epsilon_{t}$ represents the error term.

Processing of a sequence of inputs can be achieved by recurrent neural
networks (RNN) equipped with long short-term memory (LSTM) (Hochreiter and
Schmidhuber, 1997), which is capable of dealing with both short and long range
dependencies. In LSTM, outputs are influenced not only by the current input
but also by the state of the RNN, which encodes the entire history of past
inputs. A forget gate layer of LSTM decides what information to keep/remove
from the previous network state whereas an additive gate decides how to update
the state based on the current input.

##  3\. Problem formulation

We focus on SDCs that perform behavioural cloning, i.e., the DNN learns the
lane keeping (Gambi et al., 2019) behaviour from a human driver. Models such
as the ones by NVIDIA (Bojarski et al., 2016) or the Udacity self-driving
challenge (Udacity, 2017b) are trained with visual inputs (i.e., images) from
car-mounted cameras that record the driving scene, paired with the steering
angles from the human driver. The DNN then “learns how to drive” by
discovering underlying patterns within the training images representing the
shape of the road, and predicting the corresponding steering angle.

Figure 2. Model Training under Nominal Driving Behaviour.

For a classification problem (e.g., hand-written digit recognition), a
misbehaviour can be defined as an input that can be confidently labeled by
humans while it is misclassified by a DNN. Differently, for a regression
problem such a definition is more troublesome, because there is no expected
outcome for an individual output of the DNN and it is only the overall
behaviour resulting from the DNN predictions that may or may not be
acceptable, depending on the specific application domain.

In steering angle prediction, it is challenging to decide if the steering
angle produced by a DNN is wrong, because the optimal steering angle is
generally unknown for a new test scenario and even if it were known, the
amount of difference between predicted and expected steering angle that
qualifies as an error is difficult to decide a priori. It is instead more
realistic to figure out whether a chain of inaccurate predictions, regardless
of the amount of deviation from the optimal angles, ultimately leads to a
misbehaviour of the system.

In fact, the definition of misbehaviour should be decoupled from the notion of
correct/wrong DNN output, being instead linked to the ability of a DNN of
abstracting from the training examples and learning how to drive in different
ways/conditions. It is the task of the DNN to generalize the training
knowledge to make the model robust w.r.t. slightly different conditions from
those observed in the training set. For instance, if the SDC is facing a
90-degree bend, the DNN may decide to steer at a certain steering angle
$\theta$ if the car speed is 60 mph, or $\frac{\theta}{2}$ if the speed is 30
mph.

###### Definition 1 (Misbehaviour of a DNN).

A DNN exhibits a misbehaviour in a given test scenario if the overall system
that contains the DNN does not respect its requirements due to the outputs
produced by the DNN.

In the autonomous driving domain, there are many possible misbehaviours,
associated with the different requirements that such systems are supposed to
realize. Safety requirement violations are by far the most critical
requirements, as a misbehaviour in the steering component may cause a crash of
the vehicle with potential casualties. However, in general, a SDC might
violate also other driving requirements, e.g., related to ride comfort
(Burkhard et al., 2018), such as excessive derivative of the steering angle,
unstable movement around the centerline, or excessive deceleration. All these
could also be considered as misbehaviours by our definition.

In this paper, we focus on the prediction of two safety-critical
misbehaviours: (1) collisions, and (2) out-of-bound episodes (OBEs). The
rationale for this choice are as follows. First, they represent the vital
requirement to be satisfied and thoroughly tested (i.e., the car should stay
in lane and avoid whatsoever collision), without which autonomous driving
vehicles would be hardly accepted in production. Moreover, leveraging a
simulation environment such as Udacity’s (Udacity, 2017a), allows us to: (1)
safely test such critical scenarios, (2) precisely define, observe and measure
them, in order to support crash analysis and reproduction.

Thus, the problems we want to address in this paper are: (1) recognizing when
a self-driving car is within a low-confidence area because of an unexpected
execution context, and (2) predicting such situation timely enough so as to
take countermeasures before the vehicle may crash or drive off road.

##  4\. Approach

The goal of our approach is to monitor the confidence level of a SDC as it
runs and to promptly predict whether drops in confidence correlate with
potential future misbehaviours. Our approach works in an end-to-end fashion,
analyzing directly the input data as retrieved by the car (an image from the
center camera), making the approach independent from the specific architecture
of the self-driving component, requiring no modifications to the existing DNN
model, and being therefore, highly generalizable.

The main working assumption is that a prediction model trained on normal data
should learn the normal time series patterns. When the model is used on a SDC
in the field, it should worsen its performance as the car approaches
previously unseen regions as compared to normal, known regions (Figure 1).
Then, what’s needed is a way to set up a good decision boundary in order to
timely alert the human driver (NHTSA Level 4) or the main self-driving
component (NHTSA Level 5) about triggering self-healing.

We now detail each step of our approach, which consists of two main phases:
(1) model training under nominal driving behaviour, and (2) field usage of the
trained model.

###  4.1. Training of SelfOracle under Nominal Driving Behaviour

Figure 2 illustrates the training phase of our approach, which consists of
several steps.

####  4.1.1. Reconstructor

The first step consists in retrieving a model of normality from the training
driving scenarios. Thus, in the training set, we capture the visual input
stream of the SDC under nominal situations.

Then, we train our driving scenario reconstructor with such “normal”
instances. Let us consider a training set
$\boldsymbol{X}=\\{x_{1},x_{2},\ldots,x_{n}\\}$ of $n$ image frames, where the
index $i\in[1:n]$ of $x_{i}\in\boldsymbol{X}$ represents the discrete time
$t$.

Depending on the considered architecture, a reconstructor can be singled-image
or sequence-based. For singled-image reconstructors, only one image frame is
considered at a time. When the discrete time is $t=i$, $x_{i}$ is the input
and the reconstructor recreates it into $x^{\prime}_{i}$. For sequence-based
reconstructors, assuming $k$ image frames preceding $x_{i}$ are used to
reconstruct $x_{i}$, the sequence $\langle x_{i-k},\ldots,x_{i-1}\rangle$ is
the input used to output $x^{\prime}_{i}$, a prediction of the actual current
frame $x_{i}$. For instance, for $k=3$ and $i=4$, the reconstructor considers
the sequence $\langle x_{1},x_{2},x_{3}\rangle$ in order to predict the
current frame $x_{4}$.

At the end of this task, each reconstruction error
$e_{i}=d(x_{i},x^{\prime}_{i})$ can be computed, where $d$ is a proper
distance function (e.g., Euclidean distance). This results in the set of
reconstruction errors $\boldsymbol{E}=\\{e_{1},e_{2},\ldots,e_{n}\\}$,
available for all elements in the training set
$\boldsymbol{X}=\\{x_{1},x_{2},\ldots,x_{n}\\}$.

Figure 3. Fitted Gamma distribution of reconstruction errors from a VAE on the
Dave2 dataset.

####  4.1.2. Probability Distribution Fitting

We build a model of normality for the reconstruction errors
$\boldsymbol{E}=\\{e_{1},e_{2},\ldots,e_{n}\\}$ collected in nominal driving
conditions. We use probability distribution fitting to obtain a statistical
model of normality and using such model we determine a threshold $\theta$ that
brings the expected false alarm rate in nominal conditions below some
acceptable, configurable level $\epsilon$ (e.g., $\epsilon=10^{-3}$ or
$\epsilon=10^{-4}$).

The reconstruction error $e=d(x,x^{\prime})$ can be computed by comparing the
individual pixels of the images $x$ and $x^{\prime}$ and taking the mean
pixel-wise squared error. Assuming images have width $W$, height $H$ and $C$
channels (usually, 3 RGB channels for colour images), the reconstruction error
is defined as follows:

(2)
$d(x,x^{\prime})=\frac{1}{WHC}\sum_{i=1,j=1,c=1}^{W,H,C}{(x[c][i,j]-x^{\prime}[c][i,j])^{2}}$

With some reasonable approximation, we can assume that the pixel-wise error
$e[c][i,j]=x[c][i,j]-x^{\prime}[c][i,j]$ follows a normal distribution with
pixel dependent variance: $e[c][i,j]\sim\mathcal{N}(0,\sigma_{c,i,j})$.
Correspondingly, the sum of the squares of pixel-wise errors $e[c][i,j]$ will
be a gamma distribution: $e=d(x,x^{\prime})\sim\Gamma(\alpha,\beta)$. We get a
gamma instead of a $\chi^{2}$ distribution because pixel-wise errors have
different (channel/pixel dependent) and non-unitary variances.

Definition of Gamma Distribution. Gamma is a probability model for a
continuous variable on $[0,\infty)$ which is widely used in engineering,
science, and business, to model continuous variables that are always positive
and have skewed distributions.

The probability density function of a random variable
$x\sim\Gamma(\alpha,\beta)$ is:

(3) $f(x)=\frac{\beta^{\alpha}}{\Gamma(\alpha)}x^{\alpha-1}e^{-\beta x}\hskip
14.45377ptx>0;\ \alpha,\beta>0$

where $\alpha$ is the shape parameter (which affects the shape of the
distribution), $\beta$ is the rate parameter (or inverse scale, which
stretches/shrinks the distribution) and $\Gamma$ is the gamma function. When
$\alpha$ is large, the gamma distribution closely approximates a normal
distribution with the advantage that the gamma distribution has non-zero
density only for positive real numbers.

The gamma function $\Gamma$ can be seen as a solution to the interpolation
problem of finding a smooth curve that connects the points $(n,m)$ with
$m=(n-1)!$ at any positive integer value for $n$. Such a definition was
extended to all complex numbers with a positive real part by Bernoulli, as a
solution to the following integral:

(4) $\Gamma(z)=\int_{0}^{\infty}{x^{z-1}e^{-x}dx}\hskip
14.45377pt\mathfrak{R}(z)>0;$

Figure 4. Usage Scenario of SelfOracle.

Fitting the Gamma Distribution. One powerful method to estimate the parameters
of a (gamma) distribution that fit the data (reconstruction errors) best is by
maximum likelihood estimation (MLE). The likelihood function reverses the
roles of the variables: in Equation 3, the values of $x$ are known, so they
are the fixed constants, whereas the unknown variables are the parameters
$\alpha$ and $\beta$. MLE involves calculating the values of these parameters
so as to obtain the highest likelihood of observing the values of $x$ when the
given parameters are supplied to $f$.

Under the assumption of independence of the data, the likelihood of the data
given the parameters of the distribution is conveniently defined as the
logarithm of the joint probability of the data for a given choice of the
parameters. In the case of a gamma distribution, with a dataset consisting of
reconstruction errors $\boldsymbol{E}=\\{e_{1},e_{2},\ldots,e_{n}\\}$, we get:

(5)
$\displaystyle\mathcal{L}(\alpha,\beta;\boldsymbol{E})=\frac{1}{n}\sum_{i=1}^{n}{\log
f(e_{i}|\alpha,\beta)}=$ (6) $\displaystyle n(\alpha-1)\overline{\log
e}-n\log\Gamma(\alpha)-n\alpha\log\beta-n\overline{e}/\beta$

where $\overline{e}$ ($\overline{\log e}$) is the mean (log) reconstruction
error over $\boldsymbol{E}$. To find the values of parameters $\alpha$ and
$\beta$ that maximize $\mathcal{L}$ we have to find a solution to the
equations: (1) $\partial\mathcal{L}/\partial\alpha=0$; (2)
$\partial\mathcal{L}/\partial\beta=0$. The second equation can be easily
solved analytically, resulting in $\beta=\overline{e}/\alpha$. By substituting
the value of $\beta$ into the first equation we get an equation that
unfortunately cannot be solved analytically. However, the Newton method can
iteratively converge to the solution quite quickly. The output of such
numerical estimation will be the pair of parameters $\alpha$ and $\beta$ of
the gamma distribution that best fit the reconstruction errors.

Example of Threshold Estimation. Let us consider a set of reconstruction
errors. Figure 3 shows the histogram of those produced on the Dave2 dataset
when the reconstructor is a VAE. On such dataset the MLE method estimates the
following gamma parameters: $\alpha=15$; $\beta=392$. With these parameter
values, the plot of the gamma distribution is the red line in Figure 3. We can
notice a good agreement between the histogram and the estimated probability
distribution.

Let us assume that we are willing to accept a false alarm rate
$\epsilon=10^{-2}$. The threshold $\theta$ with a probability mass above the
threshold equal to $10^{-2}$ can be easily obtained as the inverse of the
cumulative gamma distribution $F(x)$: $\theta=F^{-1}(1-\epsilon)$. This
ensures that the cumulative probability of values $\leq\theta$ is
$1-\epsilon$, leaving only a probability of $\epsilon$ to the tail following
$\theta$. We use the estimated $\theta$ as threshold to distinguish anomalous
conditions (reconstruction error $\geq\theta$) from normal ones
(reconstruction error $<\theta$).

###  4.2. Usage Scenario

Figure 4 shows how SelfOracle is used online for misbehaviour prediction after
model training (i.e., after fitting the gamma distribution and estimating the
threshold $\theta$). Misbehaviour prediction is executed online as the SDC
drives. In this phase, the SDC generates data continuously and the
reconstructor recreates the incoming stream of images. The sequence of
reconstruction errors is passed through the autoregressive model $f$ and the
resulting, filtered error is compared against the threshold $\theta$, which
determines whether an anomaly is detected or not. In the former case, self-
healing is triggered and the SDC is brought to a safe state.

####  4.2.1. Time-aware Anomaly Score Prediction

The reconstruction error $e_{t}$ at time $t$ might be susceptible to single-
frame outliers, which are not expected to have a big impact on the driving of
the car, but would indeed make the misbehaviour predictor falsely report an
anomalous context. For this reason, we smooth such noisy oscillations by
applying an autoregressive filter: the sequence of reconstruction errors is
passed to a module that performs time series-analysis. In Figure 4, this
corresponds to the AR filter $f$. The output of this filter, instead of the
raw reconstruction error $e_{t}$, is compared with the threshold $\theta$ to
recognize unexpected driving conditions. In our experiments we used a simple
AR model (see Equation 1) with $\alpha_{0}=0$ and $\alpha_{i}=1/k$ for
$i=1,\ldots,k$.

##  5\. Empirical Evaluation

###  5.1. Research Questions

We consider the following research questions:

RQ1 (effectiveness): How effective is SelfOracle in predicting anomalies for
autonomous vehicles? What are the best reconstructors to use?

RQ2 (prediction): How does the misbehaviour predictions of SelfOracle change
as we increase the reaction period (i.e., we anticipate the time of
prediction)?

RQ3 (comparison): How does SelfOracle compare with DeepRoad’s (Zhang et al.,
2018) online input validation?

###  5.2. Self Driving Car Models

We evaluate our framework on three existing DNN-based SDCs: NVIDIA’s DAVE-2
(Bojarski et al., 2016), Epoch (Team Epoch, 2016), and Chauffeur (Team
Chauffeur, 2016). We choose these models because they are publicly available,
thus they can be trained and evaluated on the simulator. Moreover, they have
been objects of study of other testing works (Pei et al., 2017; Tian et al.,
2018). DAVE-2 consists of three CNNs, followed by five fully-connected layers.
Chauffeur uses a CNN to extract the features of input images, and a RNN to
predict the steering angle from 100 previous consecutive images. Epoch
consists of a single CNN model.

###  5.3. Simulation Platform

A major problem in anomaly detection research is the lack of labeled benchmark
datasets (Campos et al., 2016), and the self-driving car domain is no
exception. Unlike previous works (Zhang et al., 2018; Tian et al., 2018; Pei
et al., 2017), we cannot rely on existing driving image datasets such as the
ones released by Udacity (Udacity, 2017c), because they lack any episode of
crash, or cars driving off road whatsoever. Moreover, our definition of
misbehaviour (Section 3) requires the creation of a set of “controllable”
unexpected conditions that may potentially cause them, along with a way to
precisely record them. Thus, to investigate the effectiveness of our approach
in predicting safety-critical misbehaviours, we evaluated SelfOracle in the
Udacity simulator (Udacity, 2017a).

The Udacity simulator is developed with Unity (unity, 2019), a popular cross-
platform game engine. The simulator provides two default tracks, for testing
DNNs models. The simulator executes in two modes: (1) training mode, in which
the user manually controls the car while the simulator records her actions,
and (2) autonomous mode, in which the car is controlled by an external agent,
such as a DNN-based autonomous driving system. Moreover, we added a third
track (track3, 2019) to the existing set, and we implemented two additional
components, namely, an unexpected context generator, and a collision/OBE
detection system.

####  5.3.1. Unexpected Context Generator

First, we developed a method to gradually inject unseen conditions during
testing mode (i.e., conditions diverse from the training mode’s defaults). The
first condition deals with illumination and introduces a day/night cycle
component to gradually change the light condition of the track during the
simulation. The effect is customizable and consists of smooth
increase/decrease of brightness/darkness over a fixed period (60 s in our
experiments). The second kind of unexpected condition deals with weather. We
implemented rain, snow and mist effects, with a variable intensity during the
simulation. For the implementation, we used a specific Unity component called
Particle System (particle-system, 2019) which can simulate the physics of a
cluster of particles with high performance. Rain particles emission rate
ranges between a minimum of 100 (light rain) to a maximum of 10,000
particles/s (heavy rain); fog between [100..2,000] particles/s, and snow
between [100..800] particles/s. Figure 5 shows a few examples.

Figure 5. (top) Day/night cycle (sunrise, day, night) and (bottom) weather
effects (snowy Lake Track, foggy Jungle Track, and rainy Mountain Track).

####  5.3.2. Collision/OBE Detection System

Following our definition of safety-critical misbehaviours, we implemented an
automated collision/OBE detection system (ACODS) that records any unwanted
interaction of the SDC with the environment, allowing us to experiment the
effectiveness of SelfOracle at anticipating such episodes during the
occurrence of unexpected scenarios (Section 5.3.1).

Figure 6. Simulator crash/OBE detection.

We implemented ACODS based on colliders, which are consolidated building
blocks of modern game engines to simulate the physical interaction between
objects. We approximate the car body with a geometry mesh, and implemented a
collider callback that informs the simulator of any physical interaction of
the car with scene objects. When the car “hits” the road, then it means the
car is actually on track, whereas when the car “collides” with any other
object, the callback registers whether it is a crash against some object
(Figure 6 (left)), or whether it is an OBE (Figure 6 (right)).

Secondly, we implemented an automatic restart mechanism that restores the SDC
to a safe position after a crash/OBE, allowing us to record multiple
simulations without the need for manual restart.

###  5.4. Procedure

####  5.4.1. Data Generation (Training Set)

Training data were collected by the authors in training mode by performing 10
laps on each track, following two different track orientations (normal,
reverse). Overall, we obtained a dataset of 124,638 training images (at 10-13
fps), divided as follows: 32,243 for Track 1 (Lake), 51,422 for Track 2
(Jungle), and 40,973 for Track 3 (Mountain). Differences depend on the track
lengths. To allow a smooth driving and a correct behaviour capture (i.e., lane
keeping), the maximum driving speed was set to 30 mph, the default in the
Udacity simulator.

####  5.4.2. SDC Model Setup & Training

All SDCs models were trained on 41,546 images from the central camera. We used
data augmentation as a consolidated practice for building more reliable and
generalizable SDCs, limiting the lack of image diversity in the training data.
Specifically, 60% of the data was augmented through different image
transformation techniques (e.g., flipping, translation, shadowing,
brightness). We cropped the images to 66 x 200, and converted them from RGB to
YUV colour space. All SDC models were trained for 500 epochs with batch size
of 256 on a machine featuring an i9 processor, 32 GB of memory, and an Nvidia
GPU 2080 TI with 11GB of memory. Basically, the training was meant to create
solid models for testing, i.e., able to drive multiple laps on each track
under nominal conditions without showing any misbehaviour in terms of
crash/OBE.

####  5.4.3. Evaluation Set

To collect the evaluation data, we executed 72 simulations (2 laps each) in
autonomous mode (3 SDC x 8 conditions x 3 tracks). As in data generation, the
maximum speed was set to 30 mph. Specifically, for each SDC and for each
track, we performed 1 simulation in the same normal conditions as the training
set. This allows us to estimate the number of false alarms (false positives)
in nominal conditions. Second, we performed 4 simulations activating in turn a
single unexpected condition: day/night cycle, rain, snow, fog. Third, we
performed 3 simulations activating in turn a combined condition: day/night
cycle + rain, day/night cycle + snow, day/night cycle + fog.

In our experiments, we used a value of 60 s both for the day/night cycle and
for the loop between the minimum and maximum intensity of the effects. This
value was chosen empirically given the relatively short speed of the SDC, and
the small length of the tracks, and allowed us to test the behaviour of the
SDC on each of the track subsets under all possible conditions. For example,
the bridge part of Track1 (Lake) has been driven on under both
dawn/day/sunset/night conditions (day/night cycle) and minimal/maximal
intensity of rain/fog/snow.

Overall, we obtained a dataset of 778,592 images, divided as follows: 188,032
for Track 1 (Lake), 260,064 for Track 2 (Jungle), and 208,064 for Track 3
(Mountain) with unknown conditions and 33,088 for Track 1, 46,272 for Track 2
and 43,072 for Track 3 in known conditions.

Figure 7. Labelling of Anomalous and Normal Windows in Driving Stream.

####  5.4.4. SelfOracle’s Configurations

We used four autoencoders taken from existing guidelines (keras, [n.d.]): (1)
_SAE_ (simple autoencoder with a single hidden layer), (2)  _DAE_ (deep five
layers fully-connected autoencoder), (3)  _CAE_ (convolutional autoencoder
alternating convolutional and max-pooling layers), and (4)  _VAE (variational
autoencoder)_.

All autoencoders take as input a single image. We added images taken by the
side cameras of the car (left, right) to allow better generalization, even
though, during testing, autoencoders are not used for prediction. Lastly, we
performed further data augmentation on 60% of the inputs, as described in
Section 5.4.2.

As an additional sequence-based reconstructor, we also implemented an LSTM
consisting of two LSTM-layers and one convolutional layer. For implementation
details, we made our code publicly available in the replication package
accompanying this paper (SelfOracle, 2019).

Baseline. We use the input validation technique of DeepRoad (Zhang et al.,
2018) as baseline for SelfOracle. Unfortunately, authors did not make their
code available; therefore, we implemented of our own version according to the
description in the paper. For input validation, DeepRoad uses the pre-trained
VGG19 ImageNet classifier (Simonyan and Zisserman, [n.d.]) to extract style
and feature vectors from a given image. Principal Component Analysis (PCA) is
then used to reduce all style and feature vectors, concatenated into a matrix,
to three dimensional representations, which support distance/similarity
estimation. To allow a fair comparison, we integrated it within SelfOracle as
reconstructor. However, unlike autoencoders, DeepRoad is computationally very
expensive and memory demanding (due to the size of the matrix supplied to
PCA). In the paper, authors reduced their training set to 600 images, which
were resized to 120x90. During input validation, the three dimensional
representation of an online input image is compared to the nominal images by
measuring the average of the top-100 minimum distances from the training set.

Our own implementation relaxed the restrictions above by considering a
training set consisting of 3,000 randomly sampled images (i.e., $5\times$
improvement w.r.t. the original implementation described in the paper),
resized to 224x224, which is the default input size for VGG19 (Keras, [n.d.]).
Keeping the fraction of the training set ($\frac{1}{6}$) constant, we compute
similarity based on the average of the top-500 minimal distances. For
implementation details, we made our code publicly available in the replication
package accompanying this paper (SelfOracle, 2019).

###  5.5. Evaluation of Simulation Results

To allow a fair comparison with our baseline DeepRoad, we evaluated all
approaches offline, by splitting the evaluation set of recorded images in
_windows of consecutive frames_ , which we labelled as either anomalous or
normal (Figure 7). In anomalous windows, SelfOracle is expected to predict the
shortly-following misbehavior.

####  5.5.1. Labelling of Anomaly and Normal Windows in Evaluation Data

Let $\boldsymbol{X}=\\{x_{1},x_{2},\ldots,x_{n}\\}$ be the sequence of
considered images (frames). Misbehaviors are represented as
$m_{j}\in\\{0,1\\}$, where $m_{j}=1$ iff a misbehavior is recorded at
$x_{j}\in\boldsymbol{X}$. We define a healing period as a sequence of $h$
misbehaviour-free frames following a misbehaviour at time $t$. We define a
reaction period as a sequence of $r$ misbehaviour-free frames preceding a
misbehaviour at time $t^{\prime}$ and not intersecting any healing period. We
define an anomalous window as $a$ consecutive misbehaviour-free frames
followed by a reaction period that does not intersect any healing period. We
define a normal window as $b$ consecutive misbehaviour-free frames followed by
an anomalous window, or a normal window that does not intersect any healing
period. This is illustrated graphically in Figure 7. Formally, assuming any
misbehavior recorded at time $t\in[1{:}n]$, i.e., $m_{t}=1$:

  * •

window $x_{t+1}$ to $x_{t+h}$ is labelled as healing period if $m_{t}=1$ and
$m_{j}=0\>\forall j\in[t+1{:}t+h]$;

  * •

furthermore, the window $x_{t+1}$ to $x_{k-1}$ is also labelled as healing
period if $m_{k}=1$ with $k>t$ and $k-t-1<h$, and $m_{j}=0\>\forall
j\in[t+1{:}k-1]$;

  * •

window $x_{t-r}$ to $x_{t-1}$ is labelled as reaction period iff $m_{t}=1$,
$m_{j}=0\>\forall j\in[t-r{:}t-1]$ and no healing period contains any frame
from $x_{t-r}$ to $x_{t-1}$;

  * •

window $x_{i}$ to $x_{i+a-1}$ is labelled as anomaly window iff a reaction
period starts at $x_{i+a}$, $m_{j}=0\>\forall j\in[i{:}i+a-1]$ and no healing
period contains any frame from $x_{i}$ to $x_{i+a-1}$;

  * •

window $x_{i}$ to $x_{i+b-1}$ is labelled as normal window iff an anomaly or a
normal window starts at $x_{i+b}$, $m_{j}=0\>\forall j\in[i{:}i+b-1]$ and no
healing period contains any frame from $x_{i}$ to $x_{i+b-1}$.

Moreover, if $m_{j}=0$ for all $j\in[k{:}n]$, all consecutive windows of size
$b$ starting within $x_{k}$ to $x_{n-r-a-1}$ which do not intersect any
healing period are labelled as normal. The labelling described above ensures
that after the last misbehavior in a sequence, $h$ _healing images_ are
ignored (i.e., not labeled) before another anomaly or normal window is
defined. $h$ must be chosen high enough that the car is back safely on the
road when the next windows are labelled. Furthermore, $r$ images occur in
between an anomaly window in which the system is supposed to predict the
upcoming misbehavior, and the actual misbehavior. This period would, in
practice, be used by the self-healing system to execute countermeasures
against the predicted future misbehavior. Intuitively, misbehavior prediction
is expected to be much harder as the value of $r$ increases. In our
experiments, we set the value of $n=b=30$ frames (i.e., normal/anomalous
windows), which is $\approx$3s.222In our setting, Udacity frame rate was
approximately 10/12 fps. The size of the healing window was set to $h=60$ (¿
5s) frames, and the size of the reaction window to $r=50$ (¿ 4s) frames.

####  5.5.2. Metrics used for Analysis

If the loss score for an image is higher than the automatically estimated
threshold $\theta$ (Section 4.2), SelfOracle triggers an alarm. Consequently,
a true positive is defined when SelfOracle triggers an alarm during an
anomalous window, early enough to predict a misbehavior. Conversely, a false
negative occurs when SelfOracle does not trigger an alarm during an anomalous
window, thus failing at predicting a mis-behaviour in time for triggering
self-healing. A false positive represents a false alarm by SelfOracle, whereas
true negative cases occur when SelfOracle detects correct detection of
normality.

We assume that a single alarm immediately starts the self healing system, such
that multiple consecutive alarms within the healing time have no effect.
Correspondingly, once a FP occurs and the self healing system is running,
additional consecutive FP windows have no effect in practice and are thus
excluded from our analysis.

Our goal is to achieve (1) high recall, or true positive rate (TPR, defined as
TP/TP+FN), i.e., true alarms, while (2) minimizing the complement of
specificity, or false positive rate (FPR, defined as FP/TN+FP), i.e.,
labelling safe situations as unsafe. We are also interested in F1-score
($F_{1}=2\cdot\frac{\text{Precision}\times\text{Recall}}{\text{Precision}+\text{Recall}}$)
because, in practice, it is informative to have a high F1-score at a given
threshold.

We also consider two widely adopted threshold-independent metrics for
evaluating classifiers at various thresholds settings such as AUC-ROC (area
under the curve of the Receiver Operating Characteristics), and AUC-PRC (area
under the Precision-Recall curve).

###  5.6. Results

Table 1. Evaluation Results for all variants of SelfOracle across all SDCs. Best strategies are highlighted. |  |  $\epsilon=0.05$, $1-\epsilon=0.95$ |  $\epsilon=0.01$, $1-\epsilon=0.99$
---|---|---|---
|  | Unexpected | Nominal | Unexpected | Nominal
| AUC-PRC$\boldsymbol{\uparrow}$ | AUC-ROC$\boldsymbol{\uparrow}$ | TP | FP | TN | FN | TPR$\boldsymbol{\uparrow}$ | FPR$\boldsymbol{\downarrow}$ | F1 | Prec. | FPR$\boldsymbol{\downarrow}$ | TP | FP | TN | FN | TPR$\boldsymbol{\uparrow}$ | FPR$\boldsymbol{\downarrow}$ | F1 | Prec. | FPR$\boldsymbol{\downarrow}$
DAVE-2 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
VAE | 0.354 | 0.902 | 149 | 304 | 1,970 | 47 | 0.760 | 0.134 | 0.459 | 0.329 | 0.042 | 107 | 183 | 2,959 | 89 | 0.546 | 0.058 | 0.440 | 0.369 | 0.003
DAE | 0.330 | 0.891 | 104 | 210 | 2,679 | 92 | 0.531 | 0.073 | 0.408 | 0.331 | 0.041 | 21 | 55 | 4,063 | 175 | 0.107 | 0.013 | 0.154 | 0.276 | 0.010
SAE | 0.336 | 0.891 | 138 | 260 | 1,877 | 58 | 0.704 | 0.122 | 0.465 | 0.347 | 0.050 | 108 | 183 | 2,665 | 88 | 0.551 | 0.064 | 0.444 | 0.371 | 0.002
CAE | 0.290 | 0.821 | 6 | 22 | 4,208 | 190 | 0.031 | 0.005 | 0.054 | 0.214 | 0.024 | 0 | 0 | 4,282 | 196 | 0 | 0 | n.a. | n.a. | 0
LSTM | 0.357 | 0.903 | 16 | 34 | 3,990 | 177 | 0.083 | 0.008 | 0.132 | 0.320 | 0 | 7 | 12 | 4,119 | 186 | 0.036 | 0.003 | 0.066 | 0.368 | 0
DeepRoad | 0.198 | 0.780 | 65 | 344 | 3,170 | 131 | 0.332 | 0.098 | 0.215 | 0.159 | 0.054 | 44 | 250 | 3,651 | 152 | 0.225 | 0.064 | 0.180 | 0.150 | 0.037
Epoch |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
VAE | 0.391 | 0.904 | 158 | 331 | 1,952 | 51 | 0.756 | 0.145 | 0.453 | 0.323 | 0.049 | 106 | 169 | 2,858 | 103 | 0.507 | 0.056 | 0.438 | 0.386 | 0.001
DAE | 0.399 | 0.895 | 112 | 188 | 2,720 | 97 | 0.536 | 0.065 | 0.440 | 0.373 | 0.042 | 24 | 34 | 3,653 | 185 | 0.115 | 0.009 | 0.180 | 0.414 | 0.010
SAE | 0.386 | 0.883 | 147 | 284 | 2,026 | 62 | 0.703 | 0.123 | 0.459 | 0.341 | 0.050 | 120 | 175 | 2,838 | 89 | 0.574 | 0.058 | 0.476 | 0.407 | 0.002
CAE | 0.310 | 0.822 | 6 | 23 | 3,661 | 203 | 0.029 | 0.006 | 0.050 | 0.207 | 0.020 | 0 | 0 | 3,731 | 209 | 0 | 0 | n.a. | n.a. | 0
LSTM | 0.385 | 0.879 | 23 | 34 | 3,503 | 175 | 0.116 | 0.010 | 0.180 | 0.404 | 0.001 | 7 | 13 | 3,592 | 191 | 0.035 | 0.004 | 0.064 | 0.350 | 0
DeepRoad | 0.213 | 0.807 | 70 | 308 | 2,917 | 139 | 0.335 | 0.096 | 0.239 | 0.185 | 0.053 | 43 | 201 | 3,240 | 166 | 0.206 | 0.058 | 0.190 | 0.176 | 0.040
Chauffeur |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
VAE | 0.242 | 0.951 | 98 | 392 | 3,700 | 23 | 0.810 | 0.096 | 0.321 | 0.200 | 0.049 | 81 | 267 | 5,391 | 40 | 0.669 | 0.047 | 0.345 | 0.233 | 0.002
DAE | 0.203 | 0.944 | 78 | 281 | 5,045 | 43 | 0.645 | 0.053 | 0.325 | 0.217 | 0.051 | 13 | 95 | 7,730 | 108 | 0.107 | 0.012 | 0.114 | 0.120 | 0.009
SAE | 0.241 | 0.931 | 96 | 354 | 3,650 | 25 | 0.793 | 0.088 | 0.336 | 0.213 | 0.056 | 86 | 240 | 5,177 | 35 | 0.711 | 0.044 | 0.385 | 0.264 | 0.003
CAE | 0.172 | 0.909 | 7 | 34 | 8,127 | 114 | 0.058 | 0.004 | 0.086 | 0.171 | 0.023 | 0 | 0 | 8,229 | 121 | 0 | 0 | n.a. | n.a. | 0
LSTM | 0.240 | 0.945 | 11 | 41 | 7,879 | 111 | 0.090 | 0.005 | 0.126 | 0.212 | 0 | 4 | 12 | 8,035 | 118 | 0.033 | 0.002 | 0.058 | 0.250 | 0
DeepRoad | 0.098 | 0.797 | 37 | 594 | 5,564 | 84 | 0.306 | 0.097 | 0.098 | 0.059 | 0.055 | 23 | 458 | 6,551 | 98 | 0.190 | 0.065 | 0.076 | 0.048 | 0.042
Totals |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
VAE | 0.320 | 0.924 | 405 | 1027 | 7,622 | 121 | 0.770 | 0.119 | 0.414 | 0.283 | 0.046 | 294 | 619 | 11,208 | 232 | 0.559 | 0.052 | 0.409 | 0.322 | 0.002
DAE | 0.301 | 0.911 | 294 | 679 | 10,444 | 232 | 0.559 | 0.061 | 0.392 | 0.302 | 0.045 | 58 | 184 | 15,446 | 468 | 0.110 | 0.012 | 0.151 | 0.240 | 0.009
SAE | 0.312 | 0.907 | 381 | 898 | 7,553 | 145 | 0.724 | 0.106 | 0.422 | 0.298 | 0.052 | 314 | 598 | 10,680 | 212 | 0.597 | 0.053 | 0.437 | 0.344 | 0.002
CAE | 0.255 | 0.864 | 19 | 79 | 15,996 | 507 | 0.036 | 0.005 | 0.061 | 0.194 | 0.022 | 0 | 0 | 16,242 | 526 | 0 | 0 | n.a. | n.a. | 0
LSTM | 0.329 | 0.915 | 50 | 109 | 15,372 | 463 | 0.098 | 0.007 | 0.149 | 0.315 | 0 | 18 | 37 | 15,746 | 495 | 0.035 | 0.002 | 0.063 | 0.327 | 0
DeepRoad | 0.159 | 0.799 | 172 | 1246 | 11,651 | 354 | 0.327 | 0.097 | 0.177 | 0.121 | 0.054 | 110 | 909 | 13,442 | 416 | 0.209 | 0.063 | 0.142 | 0.108 | 0.040

Effectiveness (RQ1). Table 1 presents the effectiveness results on a per-SDC
model basis. Columns 2 and 3 show threshold-independent measures of AUC-PRC
and AUC-ROC. The remaining of the table shows the effectiveness metrics across
two confidence thresholds that we found interesting for analysis and
correspond to $\epsilon=0.05$ and $\epsilon=0.01$ (at lower values of
$\epsilon$, both FPR and TPR get close to zero, making the misbehaviour
predictor useless).

Overall, LSTM and VAE are the best performing reconstructors on the AUC-PRC
and AUC-ROC metrics. Columns 12 and 21 (Nominal/FPR) show FPR under conditions
similar to those of the training set. Values are almost always near to zero
and occasionally even equal to zero (this is indicated by omitting the
decimals) across the variants of SelfOracle. This is an empirical validation
of the accuracy of the gamma distribution as a statistical model for the
reconstruction errors. In fact, at $\epsilon=0.05$ most FPR reported in column
12 are very close to the theoretical value, 0.05 (see, e.g., rows under
Totals). At $\epsilon=0.01$ some values drop to zero. This means that in those
configurations SelfOracle will raise no false alarm when the SDC drives in
nominal conditions. For instance, with both thresholds, LSTM never raised
false alarms within the 23,728 considered normal windows .

In terms of TPR (to be maximized) and FPR (to be minimized), the best
reconstructors are VAE and SAE, with comparable overall performance: 77%, 11%
(TPR, FPR of VAE) and 72%, 10% (SAE) at $\epsilon=0.05$; 55%, 5% (VAE) and
59%, 5% (SAE) at $\epsilon=0.01$. It can be noticed that FPR is higher than
$\epsilon$ (10% vs 5% and 5% vs 1%) with both reconstructors. This is
expected, since we are measuring FPR in tracks with injected anomalies. These
tracks differ substantially from the nominal tracks even in conditions not so
extreme as to cause a misbehaviour, hence inflating the FPR a bit. However, we
can notice that even in such non nominal conditions, the FPR remains low and
not too far from the theoretical prediction $\epsilon$.

We can answer to RQ1 by noticing that with reconstructors VAE and SAE we
achieve a FPR in nominal conditions close to the theoretical expectations
(resp. 5% and 1%, in the two considered configurations); that in anomalous
conditions FPR increases by a moderate amount (resp., +5% and +4%); and that
the achieved TPR is quite high (with VAE, SAE, resp. 77%, 72% and 55%, 59%).

Prediction (RQ2). Figure 8 shows the PRC-AUC of the various configurations of
SelfOracle over different reaction periods. The general trend is that
predictions get harder when the SDC is far from a critical scenario, having a
longer reaction period to prevent the misbehavior, but quite surprisingly
there is no drop in performance as we move away from the misbehaviour. Our
explanation of this unexpected finding is that the tracks used for the
evaluation of the approach contain always a relatively high degree of
anomalous features, which might trigger a self-healing reaction. Occasionally,
the level of detected anomalies surpasses the threshold and the misbehaviour
predictor raises an alarm. Correspondingly, although slightly reduced, the
signals of an upcoming misbehaviour exist in images quite far (even 60 frames
or around 6s) from the misbehaviour.

We can answer to RQ2 by noticing that the performance of SelfOracle degrades
smoothly as we anticipate the prediction (AUC-PRC remains quite high even 6s
before the misbehaviour), but we should also remark that this result must be
taken with care and might be partially due to the characteristics of the
considered tracks, which contain a continuously and smoothly increasing degree
of injected anomalies by design.

Comparison (RQ3). In our experiments, SelfOracle is constantly superior to
DeepRoad at predicting misbehaviours. Results of AUC-PRC and AUC-ROC show
significant improvements across all thresholds, and regardless of the
technique being used and the reaction period considered (in Figure 8, DeepRoad
is the lowest curve). With $\epsilon=0.05$ (resp. $\epsilon=0.01$), VAE and
SAE (see Table 1) expose more than twice the misbehaviours exposed by
DeepRoad, with a TPR = 77%, 72% vs 32% (resp., 55%, 59% vs 20%), at comparable
false positive rate FPR = 11%, 10% vs 9% (resp., 5% vs 6%).

While reimplementing DeepRoad, we noticed its high computational cost that
makes it quite unsuitable for online misbehaviour prediction. SDC
manufacturers use much larger training datasets than the one we used for our
empirical study and differently from autoencoders such as VAE and SAE,
DeepRoad is quite sensitive to the size of the training set, which must be
sub-sampled dramatically to make the approach applicable. On the contrary,
autoencoders seem a very promising option, given their relatively simple
architecture. In particular, SAE is very efficient, yet it has comparable
performance as the more sophisticated VAE. Hence, as an input validation
framework, DeepRoad has shown to be both computationally very expensive and
inaccurate, which makes it less promising and desirable than SelfOracle for
online misbehaviour prediction.

Our answer to RQ3 is that SelfOracle outperforms DeepRoad in all respects:
computational cost, accuracy of misbehaviour prediction (see TPR) and
minimization of false alarms (see FPR and AUC-PRC).

Figure 8. Misbehavior prediction capability over time.

###  5.7. Threats to Validity

Internal validity. We compared all variants of SelfOracle and DeepRoad under
identical parameter settings, and on the same evaluation set. The main threat
to internal validity concerns our custom implementation of unexpected
conditions within the simulator. However, this was a mandatory choice, since
we are not aware of open source driving simulators that can inject unexpected
execution contexts in a controllable way. Another possible threat may be the
choice and the training of our own SDCs, which may exhibit a large number of
misbehaviour if trained inadequately. We mitigated this threat by training and
fine-tuning the best publicly available driving models. Our own implementation
of DeepRoad may be another threat to internal validity, that we mitigated by
developing an implementation which improves the original one by processing
$5\times$ more information.

External validity. We used a limited number of self-driving systems in our
evaluation, as well as tracks, which pose a threat in terms of
generalizability of our results. We tried to mitigate this threat by choosing
popular subjects developed with real-world frameworks (e..g, Keras).

Reproducibility. All our results, the source code of SelfOracle, the
simulator, and all subjects are available (SelfOracle, 2019), making the
evaluation repeatable and our results reproducible.

##  6\. Related Work

Adversarial Input Generation. Adversarial generation approaches aim at
generating inputs that trigger inconsistencies between multiple autonomous
driving systems (Pei et al., 2017), or between the original and transformed
driving scenarios (Tian et al., 2018; Zhang et al., 2018; Müller et al.,
2015). These works exploit the well-known fragility of DNNs to adversarial
examples. Therefore, their main use-case concerns the identification of
underrepresented scenarios in the training data (e.g., snowy weather
condition) to support re-training and better generalization after re-training.
The only comparable technique is the online input validation of DeepRoad
(Zhang et al., 2018), for which we carried out an explicit comparison in our
empirical study, finding poor performance when used for online misbehaviour
prediction.

Despite the different goal (test generation vs misbehaviour prediction), we
share with these works the problem of how to empirically validate the proposed
technique in the absence of a precise oracle that defines the expected
behaviour of a self-driving car. The prevalent choice in test generators (Tian
et al., 2018; Zhang et al., 2018; Müller et al., 2015; Pei et al., 2017) is to
address the oracle problem by differential testing, i.e., by comparing the
behaviours of multiple DNNs, or by metamorphic testing, i.e., by comparing the
behaviour before and after applying a metamorphic transformation to the input.
Approaches based on verification are also being under investigation (Gopinath
et al., 2018). In this paper, we adopt a precise definition of DNN
misbehaviour, which gives us a very accurate functional oracle, with no need
for differential testing, metamorphic testing, or verification.

Search-based Generation. Abdessalem et al. (Abdessalem et al., 2018; Ben
Abdessalem et al., 2016, 2018) combine genetic algorithms and machine learning
to test a pedestrian detection system. Mullins et al. (Mullins et al., 2018)
use Gaussian processes to drive the search towards yet unexplored regions of
the input space, whereas Gambi et al. (Gambi et al., 2019) propose AsFault, a
search-based test generator for autonomous vehicles based on procedural
content generation. AsFault uses search operators which mutate and recombine
road segments to construct road networks for testing the lane keeping
functionality of self-driving cars. Their goal is to generate extreme and
challenging roads, maximizing the number of observed OBEs, while our goal is
to avoid OBEs by predicting misbehaviours.

Anomaly Detection for Time Series. Anomaly detection for self-driving vehicles
has been studied from a security perspective. For example, Narayanan et al.
(Narayanan et al., 2016) use a Hidden Markov Model to detect malicious
behaviours from real vehicles, and issue alerts while a vehicle is in
operation. Taylor et al. (Taylor et al., 2016) use LSTM neural networks to
detect car’s controller area network (CAN) bus attacks, whereas Marchetti et
al. (Marchetti et al., 2016) used an information theoretic approach. Lin et
al. (Lin et al., 2010) used the Mahalanobis distance between multiple sensor
data to identify unusual events in Unmanned Aerial Vehicles (UAVs). However,
their approach is not image-based and thus is not comparable with our work.
Moreover, ours is the first approach that detects unexpected driving
conditions for the prediction of misbehaviours of an autonomous vehicle to
enable self-healing.

##  7\. Conclusions and Future Work

In this paper, we studied the problem of estimating the confidence of the DNN-
based autonomous in response to unexpected execution contexts. Our tool
SelfOracle was able to anticipate by several seconds many potentially safety-
critical misbehaviours, such as out of bound episodes or collisions, with a
low false alarm rate, outperforming the input validator of DeepRoad. Future
work concerns devising novel metrics of DNN confidence, including white-box
ones, with a potential for hybridization. It would be also interesting to
characterize and predict other kind of misbehaviours (e.g., derivative of
steering angle) as well as implementing confidence-guided self-healing within
the simulator. We believe that our promising results in online misbehaviour
detection, united with the availability of a labeled dataset of crashes and a
simulation environment, can foster novel approaches for online prediction and
self-healing of autonomous driving systems.

## References

  * (1)
  * Abdessalem et al. (2018) Raja Ben Abdessalem, Annibale Panichella, Shiva Nejati, Lionel C. Briand, and Thomas Stifter. 2018\.  Testing Autonomous Cars for Feature Interaction Failures Using Many-objective Search. In _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_ _(ASE 2018)_. ACM, New York, NY, USA, 143–154.  https://doi.org/10.1145/3238147.3238192
  * Alvarez-Melis and Jaakkola (2018) David Alvarez-Melis and Tommi S. Jaakkola. 2018.  Towards Robust Interpretability with Self-Explaining Neural Networks. In _Annual Conference on Neural Information Processing Systems (NeurIPS)_. 7786–7795.
  * An and Cho (2015) Jinwon An and Sungzoon Cho. 2015.  Variational Autoencoder based Anomaly Detection using Reconstruction Probability.
  * Ben Abdessalem et al. (2016) R. Ben Abdessalem, S. Nejati, L. C. Briand, and T. Stifter. 2016.  Testing advanced driver assistance systems using multi-objective search and neural networks. In _2016 31st IEEE/ACM International Conference on Automated Software Engineering (ASE)_. 63–74.
  * Ben Abdessalem et al. (2018) R. Ben Abdessalem, S. Nejati, L. C. Briand, and T. Stifter. 2018.  Testing Vision-Based Control Systems Using Learnable Evolutionary Algorithms. In _2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE)_. 1016–1026.  https://doi.org/10.1145/3180155.3180160
  * BGR Media, LLC (2018) BGR Media, LLC. 2018\.  Waymo’s self-driving cars hit 10 million miles.  https://techcrunch.com/2018/10/10/waymos-self-driving-cars-hit-10-million-miles.  Online; accessed 18 August 2019.
  * Bojarski et al. (2016) Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. 2016\.  End to End Learning for Self-Driving Cars.  _CoRR_ abs/1604.07316 (2016).  http://arxiv.org/abs/1604.07316
  * Burkhard et al. (2018) Georg Burkhard, S. Vos, N. Munzinger, E. Enders, and D. Schramm. 2018.  Requirements on driving dynamics in autonomous driving with regard to motion and comfort. In _18\. Internationales Stuttgarter Symposium_ , Michael Bargende, Hans-Christian Reuss, and Jochen Wiedemann (Eds.). Springer Fachmedien Wiesbaden, Wiesbaden, 683–697.
  * Campos et al. (2016) Guilherme O. Campos, Arthur Zimek, Jörg Sander, Ricardo J. Campello, Barbora Micenková, Erich Schubert, Ira Assent, and Michael E. Houle. 2016\.  On the Evaluation of Unsupervised Outlier Detection: Measures, Datasets, and an Empirical Study.  _Data Min. Knowl. Discov._ 30, 4 (July 2016), 891–927.  https://doi.org/10.1007/s10618-015-0444-8
  * Cerf (2018) Vinton G. Cerf. 2018\.  A Comprehensive Self-driving Car Test.  _Commun. ACM_ 61, 2 (Jan. 2018), 7–7.  https://doi.org/10.1145/3177753
  * Electrek (2016a) Electrek. 2016a.  A Google self-driving car caused a crash for the first time.  https://electrek.co/2016/07/01/understanding-fatal-tesla-accident-autopilot-nhtsa-probe/.  Online; accessed 18 August 2019.
  * Electrek (2016b) Electrek. 2016b.  Tesla Model S driver crashes into a van while on Autopilot.  https://electrek.co/2016/05/26/tesla-model-s-crash-autopilot-video/.  Online; accessed 18 August 2019.
  * Gambi et al. (2019) Alessio Gambi, Marc Mueller, and Gordon Fraser. 2019\.  Automatically Testing Self-driving Cars with Search-based Procedural Content Generation. In _Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_ _(ISSTA 2019)_. ACM, New York, NY, USA, 318–328.  https://doi.org/10.1145/3293882.3330566
  * Gopinath et al. (2018) Divya Gopinath, Guy Katz, Corina S. Păsăreanu, and Clark Barrett. 2018.  DeepSafe: A Data-Driven Approach for Assessing Robustness of Neural Networks. In _Automated Technology for Verification and Analysis_ , Shuvendu K. Lahiri and Chao Wang (Eds.). Springer International Publishing, Cham, 3–19.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Comput._ 9, 8 (Nov. 1997), 1735–1780.  https://doi.org/10.1162/neco.1997.9.8.1735
  * keras ([n.d.]) keras. [n.d.].  Building Autoencoders in Keras.  https://blog.keras.io/building-autoencoders-in-keras.html.  Online; accessed 21 August 2019.
  * Keras ([n.d.]) Keras. [n.d.].  VGG19.  https://keras.io/applications/#vgg19/.  Online; accessed 21 August 2019.
  * Kim et al. (2019) Jinhan Kim, Robert Feldt, and Shin Yoo. 2019.  Guiding Deep Learning System Testing Using Surprise Adequacy. In _Proceedings of the 41st International Conference on Software Engineering_ _(ICSE ’19)_. IEEE Press, Piscataway, NJ, USA, 1039–1049.  https://doi.org/10.1109/ICSE.2019.00108
  * Lin et al. (2010) R. Lin, E. Khalastchi, and G. A. Kaminka. 2010\.  Detecting anomalies in unmanned vehicles using the Mahalanobis distance. In _2010 IEEE International Conference on Robotics and Automation_. 3038–3044.  https://doi.org/10.1109/ROBOT.2010.5509781
  * Marchetti et al. (2016) M. Marchetti, D. Stabili, A. Guido, and M. Colajanni. 2016.  Evaluation of anomaly detection for in-vehicle networks through information-theoretic algorithms. In _2016 IEEE 2nd International Forum on Research and Technologies for Society and Industry Leveraging a better tomorrow (RTSI)_. 1–6.  https://doi.org/10.1109/RTSI.2016.7740627
  * Masci et al. (2011) Jonathan Masci, Ueli Meier, Dan Cireşan, and Jürgen Schmidhuber. 2011.  Stacked Convolutional Auto-Encoders for Hierarchical Feature Extraction. In _Artificial Neural Networks and Machine Learning – ICANN 2011_ , Timo Honkela, Włodzisław Duch, Mark Girolami, and Samuel Kaski (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 52–59.
  * Mullins et al. (2018) Galen E. Mullins, Paul G. Stankiewicz, R. Chad Hawthorne, and Satyandra K. Gupta. 2018.  Adaptive generation of challenging scenarios for testing and evaluation of autonomous vehicles.  _Journal of Systems and Software_ 137 (2018), 197 – 215.  https://doi.org/10.1016/j.jss.2017.10.031
  * Müller et al. (2015) S. Müller, D. Hospach, O. Bringmann, J. Gerlach, and W. Rosenstiel. 2015.  Robustness Evaluation and Improvement for Vision-Based Advanced Driver Assistance Systems. In _2015 IEEE 18th International Conference on Intelligent Transportation Systems_. 2659–2664.  https://doi.org/10.1109/ITSC.2015.427
  * Narayanan et al. (2016) Sandeep Nair Narayanan, Sudip Mittal, and Anupam Joshi. 2016\.  OBD SecureAlert: An Anomaly Detection System for Vehicles. In _IEEE Workshop on Smart Service Systems (SmartSys 2016)_.
  * particle-system (2019) particle-system 2019.  Unity3d Particle System.  https://docs.unity3d.com/ScriptReference/ParticleSystem.html.
  * Pei et al. (2017) Kexin Pei, Yinzhi Cao, Junfeng Yang, and Suman Jana. 2017\.  DeepXplore: Automated Whitebox Testing of Deep Learning Systems. In _Proceedings of the 26th Symposium on Operating Systems Principles_ _(SOSP ’17)_. ACM, New York, NY, USA, 1–18.  https://doi.org/10.1145/3132747.3132785
  * Shannon (1948) Claude Elwood Shannon. 1948\.  A Mathematical Theory of Communication.  _The Bell System Technical Journal_ 27, 3 (7 1948), 379–423.  https://doi.org/10.1002/j.1538-7305.1948.tb01338.x
  * Simonyan and Zisserman ([n.d.]) Karen Simonyan and Andrew Zisserman. [n.d.].  Very Deep Convolutional Networks for Large-Scale Image Recognition.  ([n. d.]).  arXiv:cs.CV/1409.1556v6  VGGNet, https://gist.github.com/baraldilorenzo/07d7802847aaad0a35d3.
  * Taylor et al. (2016) A. Taylor, S. Leblanc, and N. Japkowicz. 2016\.  Anomaly Detection in Automobile Control Network Data with Long Short-Term Memory Networks. In _2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA)_. 130–139.  https://doi.org/10.1109/DSAA.2016.20
  * Team Chauffeur (2016) Team Chauffeur. 2016\.  Steering angle model: Chauffeur.  https://github.com/udacity/self-driving-car/tree/master/steering-models/community-models/chauffeur.  Online; accessed 18 August 2019.
  * Team Epoch (2016) Team Epoch. 2016\.  Steering angle model: Epoch.  https://github.com/udacity/self-driving-car/tree/master/steering-models/community-models/cg23.  Online; accessed 18 August 2019.
  * The Verge (2016) The Verge. 2016\.  A Google self-driving car caused a crash for the first time.  https://www.theverge.com/2016/2/29/11134344/google-self-driving-car-crash-report.  Online; accessed 18 August 2019.
  * The Verge (2019) The Verge. 2019\.  Tesla hit with another lawsuit over a fatal Autopilot crash.  https://www.theverge.com/2019/8/1/20750715/tesla-autopilot-crash-lawsuit-wrongful-death.  Online; accessed 18 August 2019.
  * Tian et al. (2018) Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray. 2018\.  DeepTest: Automated Testing of Deep-neural-network-driven Autonomous Cars. In _Proceedings of the 40th International Conference on Software Engineering_ _(ICSE ’18)_. ACM, New York, NY, USA, 303–314.  https://doi.org/10.1145/3180155.3180220
  * SelfOracle (2019) SelfOracle 2019\.  Mis-Behaviour Prediction for Autonomous Driving Systems.  https://github.com/icse2020submission/misbehavior-prediction/.
  * track3 (2019) track3 2019.  Unity3D Snow Mountain Track.  https://assetstore.unity.com/packages/3d/environments/roadways/mountain-race-track-53775.
  * Udacity (2017a) Udacity. 2017a.  A self-driving car simulator built with Unity.  https://github.com/udacity/self-driving-car-sim.  Online; accessed 18 August 2019.
  * Udacity (2017b) Udacity. 2017b.  Udacity self-driving car’s challenge.  https://github.com/udacity/self-driving-car/.  Online; accessed 18 August 2019.
  * Udacity (2017c) Udacity. 2017c.  Udacity self-driving car’s datasets.  https://github.com/udacity/self-driving-car/tree/master/datasets.  Online; accessed 18 August 2019.
  * unity (2019) unity 2019.  Unity3D.  https://unity.com.
  * Vasudevan et al. (2019) V. T. Vasudevan, A. Sethy, and A. R. Ghias. 2019\.  Towards Better Confidence Estimation for Neural Models. In _ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. 7335–7339.  https://doi.org/10.1109/ICASSP.2019.8683359
  * Zhang et al. (2018) Mengshi Zhang, Yuqun Zhang, Lingming Zhang, Cong Liu, and Sarfraz Khurshid. 2018.  DeepRoad: GAN-based Metamorphic Testing and Input Validation Framework for Autonomous Driving Systems. In _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_ _(ASE 2018)_. ACM, New York, NY, USA, 132–142.  https://doi.org/10.1145/3238147.3238187