# Distilling Deep RL Models Into Interpretable Neuro-Fuzzy Systems

Arne Gevaert, Jonathan Peck and Yvan Saeys  Department of Applied Mathematics
and Statistics
Ghent University, Ghent, Belgium
Email: {arne.gevaert, jonathan.peck<EMAIL_ADDRESS>
###### Abstract

Deep Reinforcement Learning uses a deep neural network to encode a policy,
which achieves very good performance in a wide range of applications but is
widely regarded as a black box model. A more interpretable alternative to deep
networks is given by neuro-fuzzy controllers. Unfortunately, neuro-fuzzy
controllers often need a large number of rules to solve relatively simple
tasks, making them difficult to interpret. In this work, we present an
algorithm to distill the policy from a deep Q-network into a compact neuro-
fuzzy controller. This allows us to train compact neuro-fuzzy controllers
through distillation to solve tasks that they are unable to solve directly,
combining the flexibility of deep reinforcement learning and the
interpretability of compact rule bases. We demonstrate the algorithm on three
well-known environments from OpenAI Gym, where we nearly match the performance
of a DQN agent using only 2 to 6 fuzzy rules.

###### Index Terms:

Neuro-fuzzy, Distillation, DQN, Reinforcement Learning.

##  I Introduction

Recently, significant progress has been made in the field of Deep
Reinforcement Learning, with advances in a wide variety of application
domains, such as arcade game playing [1], continuous control [2], and beating
professional players in the game of Go [3]. Most of these advances have been
made using deep neural networks, which are widely regarded as black boxes [4,
5]. This means that the inner workings of a deep neural network are difficult
to understand, making interpretation of the learned policy by humans a
difficult task. However, interpretability is a critical property of machine
learning models in many application domains, including legal and medical
applications [6]. Recent EU legislation even requires many machine learning
models to be interpretable by default [7].

An alternative to deep neural networks is the use of fuzzy controllers. These
controllers consist of a set of fuzzy IF-THEN rules (e.g. “IF temp IS low THEN
output IS high”), which can make them much more interpretable than neural
networks, provided they are relatively compact. Fuzzy controllers can either
be constructed manually using expert knowledge [8] or they can be learned from
data [9]. A popular type of fuzzy controller that can be learned from data is
the neuro-fuzzy controller [10]. In this case, the calculations are organised
in a neural network-like structure. The gradient of the output is then
calculated using backpropagation and the parameters are optimized using
gradient descent. Neuro-fuzzy controllers have successfully been applied in a
wide variety of domains, including nonlinear modeling of dynamic systems [11],
control of robotic systems [12] and power systems [13].

A possible approach to improve the interpretability of deep reinforcement
learning algorithms is to replace the deep neural network with a neuro-fuzzy
controller. In this work, we apply this approach to the Deep Q-Network (DQN)
algorithm [1]. Unfortunately, as will be shown in the results in Section VII,
simply replacing the neural network in the DQN algorithm with a neuro-fuzzy
controller does not yield satisfying results on even the simplest
environments. We therefore propose a policy distillation algorithm [14] to
distill the knowledge from a trained deep Q-network into a compact neuro-fuzzy
controller. We extend the original policy distillation algorithm with a pre-
processing and post-processing step and introduce specific regularization
terms to maximize model interpretability. We show how this approach allows us
to train compact neuro-fuzzy controllers to solve tasks that they are unable
to solve by direct reinforcement learning, combining the flexibility of deep
Q-learning with the interpretability of compact neuro-fuzzy controllers.

We first give an overview of related work in section II. Next, we explore the
DQN algorithm in section III and policy distillation in section IV. In section
V, we describe the mechanisms behind the neuro-fuzzy controller used in this
work. The complete algorithm is described in detail in section VI. We then
apply the algorithm to a number of problems in section VII and conclude in
section VIII.

##  II Related Work

The technique of knowledge distillation has originally been applied to
compress an ensemble of models into a single neural network for classification
[15]. This greatly reduces the computational cost of inference while retaining
the superior performance of the ensemble model. The extension of this
technique to the domain of reinforcement learning is called policy
distillation [14]. Not only can the size of a deep Q-network (DQN) greatly be
reduced using policy distillation, but it is also possible to merge several
task-specific networks into a single, more general DQN.

Although the original purpose of distillation is compression and
generalization, it can also be applied to improve interpretability of models.
In this case, the knowledge from a (large) model is distilled into a more
interpretable representation, such as decision trees [16] or soft decision
trees [4]. This same reasoning has also been applied to reinforcement learning
and policy distillation [17]. The knowledge encoded by a deep Q-network or an
explicit policy network can analogously be distilled into a representation
that is considered more interpretable. In this work, we use neuro-fuzzy
controllers as a target model to distill the knowledge represented by a deep
Q-network. A recent overview of techniques to increase the explainability of
reinforcement learning algorithms is given by [18].

##  III The DQN Algorithm

In (deep) reinforcement learning, an agent interacts with an environment by
taking actions in that environment. When the agent takes an action
$a\in\mathcal{A}$, the environment responds with a resulting state
$s\in\mathcal{S}$ and a reward $r\in\mathbb{R}$. The agent then takes a new
action $a^{\prime}$, to which the environment responds with a new state
$s^{\prime}$ and reward $r^{\prime}$. This cycle continues until some end
state or a maximum number of iterations is reached. The goal of reinforcement
learning is to maximize the total reward $r$ over some time period.

DQN aims to train a policy that maximizes the return
$R=\sum_{t=0}^{\infty}\gamma^{t}r_{t}$, where $\gamma$ is a constant between 0
and 1 that controls the importance that the agent assigns to rewards that are
further in the future. The deep neural network in DQN is trained to
approximate the optimal action-value function
$Q^{\ast}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ that tells us
what the return would be, if a given action $a$ is taken in state $s$, and an
optimal policy is followed afterwards. This function can be used to construct
the optimal policy: $\pi^{\ast}(s)=\arg\max_{a}Q^{\ast}(s,a)$.

The algorithm works by interacting with the environment and saving transitions
$(s,a,s^{\prime},r)$ into a replay memory $D$. After each step, a batch of
transitions $B$ is sampled from $D$, and the neural network is trained to
minimize the loss function
$\mathcal{L}=(Q(s,a)-(r+\gamma\max_{a^{\prime}}(Q(s^{\prime},a^{\prime}))))^{2}$.
This loss function is derived from the Bellman equation, and ensures that the
network will converge to the optimal action-value function $Q^{\ast}$ [1].

##  IV Policy Distillation

Distillation is a method to transfer knowledge from a teacher model $T$ to a
student model $S$. In supervised learning, this is done by using the output
distributions of the teacher to train the student [15]. As these output
distributions (soft targets) contain confidence levels of the teacher over all
output classes, they contain more information than the original labels (hard
targets), allowing the student model to learn more efficiently. However, the
output distribution for a fully trained teacher model usually has the correct
class at very high probability, with all the other classes very close to 0. As
such, the soft target hardly provides any information beyond the ground truth
labels encoded in the original hard targets. For this reason, the original
softmax output function $\sigma(\bm{z})$ of the teacher network is replaced
with a temperature softmax function $\sigma_{\tau}(\bm{z})$ that converts each
logit, $z_{i}$, computed for each class into a probability, $q_{i}$, by
comparing $z_{i}$ with the other logits:

$q_{i}=\sigma_{\tau}(\bm{z})_{i}=\frac{\exp(z_{i}/\tau)}{\sum_{j}\exp(z_{j}/\tau)}$
(1)

Note that, if the temperature $\tau=1$, we obtain the original softmax
function. If $\tau>1$, the result of this function is a smoothed version of
the normal softmax. The student is then trained on these smoothened
distributions using the classical cross-entropy loss function.

Policy distillation is the application of this idea to reinforcement learning
agents. In [14], a dataset is built by having the teacher model interact with
the environment and recording the encountered states and output Q-values. The
student is then trained to mimic this behaviour (see Figure 1a). As we require
the student to output Q-values, which do not form valid probability
distributions, we replace the cross-entropy loss with a temperature Kullback-
Leibler divergence loss:

$\mathcal{L}_{KL}(\bm{q}^{T},\bm{q}^{S})=\sigma_{\tau}(\bm{q}^{T})\ln\frac{\sigma_{\tau}(\bm{q}^{T})}{\sigma(\bm{q}^{S})}$
(2)

Where $\bm{q}^{T}$ is the output of the teacher model and $\bm{q}^{S}$ the
output of the student model. Note that the output of a softmax function on a
vector of Q-values is usually a very smooth probability distribution, as
Q-values often have very small yet important differences. For this reason, the
temperature $\tau$ in policy distillation is usually lower than 1, resulting
in sharper probability distributions.

More recent advances in policy distillation have shown better empirical
results if an $\epsilon$-greedy student policy is followed during distillation
[19, 20, 21]. This means that, for some small $\epsilon$ (e.g. $0.05$), a
random action is chosen with probability $\epsilon$ and the student’s action
is chosen with probability $1-\epsilon$. The student is then trained on the
output of the teacher for visited states, rather than building a dataset by
having the teacher interact with the environment (see Figure 1b). A possible
explanation for this performance improvement is that the teacher policy is
deterministic, while the student policy changes as the student is trained.
This leads to a better exploration of the environment if student trajectories
are followed. A schematic overview of both approaches is shown in Figure 1.

##  V Fuzzy Sets and Neuro-Fuzzy Control

Fuzzy sets form an extension of the classical notion of a mathematical set
[22]. In a classical set, every element is either a member or not a member of
the set. For a fuzzy set, the membership of an element in the set can take any
value between 0 (not a member) and 1 (entirely a member). A fuzzy set $A$ in
$\mathbb{R}$ is therefore often written as a membership function
$A:\mathbb{R}\rightarrow[0,1]$, mapping an input $x$ to its membership degree.

Neuro-fuzzy control applies this notion of fuzzy sets to create control
systems, by defining a number of fuzzy IF-THEN rules and composing them to
create a function approximator [9]:

IF $x_{1}$ is $A_{11}$ AND $\dots$ AND $x_{m}$ is $A_{m1}$
---
THEN $\bm{y}$ is $f_{1}(x_{1},\dots,x_{m})$
IF $x_{1}$ is $A_{12}$ AND $\dots$ AND $x_{m}$ is $A_{m2}$
THEN $\bm{y}$ is $f_{2}(x_{1},\dots,x_{m})$
$\cdots$
IF $x_{1}$ is $A_{1n}$ AND $\dots$ AND $x_{m}$ is $A_{mn}$
THEN $\bm{y}$ is $f_{n}(x_{1},\dots,x_{m})$

(a) Teacher trajectories

(b) Student trajectories

Figure 1: Comparison between policy distillation using teacher trajectories
and policy distillation using student trajectories. In this work, the approach
in Figure 1b is used.

Where $n$ is the number of fuzzy rules, $m$ is the number of input dimensions,
$\bm{x}=(x_{1},...,x_{m})$ is the input vector, $\bm{y}$ is the output vector,
each $A_{ij}$ is a fuzzy set in $\mathbb{R}$ (for input dimension $i$ and
fuzzy rule $j$), and each $f_{j}$ is differentiable w.r.t. its inputs (in
practice, linear or constant functions are used). The degree of activation of
the $j$-th fuzzy rule is calculated as a triangular norm (T-norm) [23] of the
membership degrees of each input $x_{i}$ in the corresponding set $A_{ij}$. A
T-norm is the fuzzy extension of a boolean AND-operation, in the form of a
two-argument function $T:\mathbb{R}^{2}\rightarrow[0,1]$. Any T-norm is
defined to be associative, and can therefore be extended to any number of
arguments by repeated application:
$T(x_{1},x_{2},...,x_{n})=T(x_{1},T(x_{2},\dots,T(x_{n-1},x_{n})\dots)$ In
most cases, the product T-norm and Gaussian membership functions are used. The
degrees of activation are then calculated as:

$\displaystyle A_{ij}(x_{i})$
$\displaystyle=\exp(-\frac{x_{i}-\mu_{ij}}{\sigma_{ij}})$ (3) $\displaystyle
R_{j}$ $\displaystyle=\prod_{i=1}^{m}A_{ij}(x_{i})$ (4)

Where $\mu_{ij}$ and $\sigma_{ij}$ are learned parameters representing the
center and standard deviation of the Gaussian membership function for input
dimension $i$ and fuzzy rule $j$. Inference is then performed by calculating
the activation for each rule using (4), normalizing these activations to sum
to 1, and calculating the output as a weighted sum of the output functions
using the activations as weights:

$\displaystyle\bar{R_{i}}$ $\displaystyle=\frac{R_{i}}{\sum_{j=1}^{n}R_{j}}$
(5) $\displaystyle\hat{\bm{y}}$
$\displaystyle=\sum_{i=1}^{n}\bar{R_{i}}f_{i}(x_{1},\dots,x_{m})$ (6)

Since the operations in (3), (4), (5) and (6) are all differentiable w.r.t.
the parameters $\\{\mu_{ij}\\}$, $\\{\sigma_{ij}\\}$ and the parameters of
$\\{f_{j}\\}$, backpropagation and gradient descent can be used to optimize
these parameters. In other words, the system can be formulated and trained
like a type of neural network, hence the name neuro-fuzzy controller.

##  VI Methods

We first discuss the details of the neuro-fuzzy architecture used in the
distillation process in section VI-A. The complete algorithm consists of three
steps: pre-processing, distillation and post-processing. We discuss these
steps in sections VI-B, VI-C and VI-D respectively. Finally, we discuss some
regularization techniques used to improve the interpretability of the
resulting neuro-fuzzy controller in section VI-E.

###  VI-A Neuro-Fuzzy Control using Weighted T-Norms

We extend the neuro-fuzzy controller from section V using a weighted T-norm
[24]. This is an extension of a normal T-norm, where an extra weight $w_{i}$
is associated with each argument: $T(x_{1},x_{2};w_{1},w_{2})$. This weight
expresses the importance of the corresponding argument. If all weights $w_{i}$
are 1, we retrieve the original T-norm: $T(x_{1},x_{2};1,1)=T(x_{1},x_{n})$.
If $w_{i}=0$, then the argument $x_{i}$ has no influence on the output of the
function. The weighted extension of the product T-norm is calculated as
follows:

$T_{P}(x_{1},\dots,x_{n};w_{1},\dots,w_{n})=\prod_{i=1}^{n}x_{i}^{w_{i}}$ (7)

This extension is incorporated into the model from section V by changing (4)
into the following:

$R_{j}=\prod_{i=1}^{m}A_{ij}(x_{i})^{w_{ij}}$ (8)

and adding the parameters $\\{w_{ij}\\}$ to the set of trainable parameters
for the model. We also restrict the values for $w_{ij}$ to be non-negative and
divide weights $w_{ij}$ by the maximal weight for their corresponding rule
$\max_{i}\\{w_{ij}\\}$ before applying (8). This ensures that the most
important fuzzy set in the antecedent of a rule always has an importance value
of 1.

###  VI-B Pre-Processing

Clustering algorithms can be used to find a good initialization for neuro-
fuzzy controllers [25]. Given a dataset of $m$-dimensional input vectors $I$
and corresponding $n$-dimensional output vectors $U$, any clustering algorithm
that outputs a set of centroid points (e.g. K-means) can be used to initialize
a neuro-fuzzy controller as follows:

  1. 1.

Construct the matrix $M$ by concatenating every input vector $\bm{v}_{i}\in I$
to its corresponding output vector $\bm{u}_{i}\in U$.

  2. 2.

Apply a clustering algorithm to the matrix $M$ to retrieve a set of centroid
points $C=\\{\bm{c}_{i}\\}$.

  3. 3.

Split every centroid point into an input vector $\bm{v}_{\bm{c}_{i}}$ and
output vector $\bm{u}_{\bm{c}_{i}}$.

  4. 4.

Define for every couple $(\bm{v}_{\bm{c}_{i}},\bm{u}_{\bm{c}_{i}})$ the fuzzy
rule: IF $\bm{x}$ is $\bm{v}_{\bm{c}_{i}}$ THEN $\bm{y}$ is
$\bm{u}_{\bm{c}_{i}}$.

We construct a dataset $(I,U)$ by having the teacher model $T$ interact with
the environment. At every time step, the state vector $\bm{s}$ generated by
the environment and the Q-vector $\bm{q}$ generated by $T$ are saved as the
input and output vectors respectively. We then apply the procedure above using
a Gaussian Mixture Model on this constructed dataset. The main advantage of a
GMM is the fact that it allows us to specify a number of clusters a priori,
and provides us with a covariance matrix for each cluster. By restricting this
matrix to be diagonal, we retrieve an estimate for the width of the
corresponding fuzzy sets.

###  VI-C Distillation

We apply policy distillation as described in IV using an $\epsilon$-greedy
student policy. The student model $S$ is initialized using the procedure
described in VI-B. We use the neuro-fuzzy controller using weighted T-norms
discussed in section VI-A with constant output functions:
$f_{j}(\bm{x})=\bm{y}_{j}$. This allows us to easily interpret the consequents
of fuzzy rules as actions, namely the action corresponding to the highest
Q-value in $\bm{y}_{j}$. As loss function, we use the temperature KL-
divergence (Eq. 2) with temperature $\tau=0.1$. The complete algorithm is
described in Algorithm 2.

Input $T$: Teacher (DQN)
Output $S$: Student (neuro-fuzzy controller)

1:Initialize replay memory $D$ of size $N$

2:for all episodes do

3: Get initial state vector $\bm{s}$

4: while episode not done do

5: Select action $a$ using $\epsilon$-greedy student policy

6: Execute action $a$, receive next state $\bm{s}^{\prime}$

7: $\bm{q}^{T}\leftarrow T(\bm{s})$

8: Save $(\bm{s},\bm{q}^{T})$ in $D$

9: $\bm{s}\leftarrow\bm{s}^{\prime}$

10: Sample minibatch $D^{\prime}\leftarrow\\{(\bm{s}_{i},\bm{q}^{T}_{i})\\}$
from $D$

11: Perform an optimization step on $S$ using $D^{\prime}$

12: end while

13:end for

Figure 2: Distillation algorithm

###  VI-D Post-Processing

The distillation algorithm tends to create very similar fuzzy sets in the rule
antecedent parts. This leads to a lack of transparency in the rule base. We
mitigate this problem by merging similar fuzzy sets. We do this by calculating
the Jaccard index between fuzzy sets and iteratively merging the most similar
fuzzy sets, as long as the similarity between these sets is greater than a
certain threshold value. This threshold value is chosen as a hyperparameter,
in this work we use $\alpha=0.95$. The new, merged fuzzy set is then again a
candidate for merging in the next iterations. Two sets $A_{ik}$ and $A_{il}$
(the fuzzy sets for input dimension $i$ in fuzzy rule $k$ and $l$,
respectively) are merged as follows [25]:

$\displaystyle\bar{\mu}$
$\displaystyle=\frac{n_{ik}\mu_{ik}+n_{il}\mu_{il}}{n_{ik}+n_{il}}$
$\displaystyle\bar{\sigma}$
$\displaystyle=\frac{n_{ik}\sigma_{ik}+n_{il}\sigma_{il}}{n_{ik}+n_{il}}$

Where $n_{ik}$ and $n_{il}$ are the number of sets that have been merged to
create $A_{ik}$ and $A_{il}$ respectively. This formula assigns more weight to
sets that are the result of many merges, so that the result of $n$ merges is
the average of the values for the $n+1$ merged sets. The full algorithm is
described in Algorithm 3.

Since we use weighted T-norms, every rule has an importance weight associated
to every input dimension. We simplify the rule base further in a second post-
processing step by removing terms in the antecedents with importance weight
smaller than $0.01$. This allows us to only consider the actually important
input dimensions for every rule.

1:$n_{ij}\leftarrow 1,\forall$ input dimension $i$, fuzzy rule $j$

2:for all Input dimension $i$ do

3: while $\max\limits_{k\neq l}(J(A_{ik},A_{il}))>\alpha$ do

4: $(k,l)\leftarrow\arg\max\limits_{k\neq l}(J(A_{ik},A_{il}))$

5: $\mu^{\prime}\leftarrow\frac{n_{ik}\mu_{ik}+n_{il}\mu_{il}}{n_{ik}+n_{il}}$

6:
$\sigma^{\prime}\leftarrow\frac{n_{ik}\sigma_{ik}+n_{il}\sigma_{il}}{n_{ik}+n_{il}}$

7:
$A^{\prime}(x)\leftarrow\exp(-(\frac{x-\mu^{\prime}}{\sigma^{\prime}})^{2})$

8: Replace $A_{ik}$, $A_{il}$ with $A^{\prime}$

9: end while

10:end for

Figure 3: Antecedent set merging

###  VI-E Regularization

In order to produce fuzzy rule bases that can easily be simplified using the
post-processing techniques described in section VI-D, we introduce two
regularization terms during the distillation process. The first term
encourages sets with similar $\mu$ values to grow towards each other, so they
can easily be merged after training:

$\mathcal{L}_{merge}=\sum_{i=1}^{m}\sum_{k=1}^{n}\sum_{l=1}^{n}\frac{\sqrt{(\sigma_{ik}-\sigma_{il})^{2}}}{1+\sqrt{(\mu_{ik}-\mu_{il})^{2}}}$

The first sum iterates over the $m$ input dimensions, while the second and
third sums each iterate over the $n$ fuzzy rules. This regularization term is
large if the distance between two centers is small, but the difference in
standard deviation of the sets is large. This indicates strongly overlapping
sets that cannot be merged easily. Such pairs of sets are also often difficult
to interpret.

The second term is an L1 regularization on the T-norm importance weights. We
first normalize the weights by dividing each weight by the largest importance
weight for the corresponding rule. This prevents the weights from taking
arbitrarily small values, as the same normalization is applied before
calculation of the weighted T-norm (see section VI-A). The first sum again
iterates over the $m$ input dimensions, and the second sum iterates over the
$n$ fuzzy rules.

$\mathcal{L}_{tnorm}=\sum_{i=1}^{m}\sum_{j=1}^{n}\frac{w_{ij}}{\max\limits_{k\in\\{1,\dots,n\\}}w_{ik}}$
(9)

The complete loss can be written as:

$\mathcal{L}=\mathcal{L}_{KL}(\bm{Q}^{T},\bm{Q}^{S})+\lambda_{m}\mathcal{L}_{merge}+\lambda_{t}\mathcal{L}_{tnorm}$
(10)

Where $\bm{Q}^{T}$ and $\bm{Q}^{S}$ are batches of 64 teacher and student
output vectors respectively. $\lambda_{m}$ and $\lambda_{t}$ are
hyperparameters that indicate the weight of the regularization terms. In this
work, we use $\lambda_{m}=1$ and $\lambda_{t}=0.5$.

##  VII Results

We apply both the distillation algorithm and naive substitution in DQN (in
which we simply substitute the deep neural network in DQN with a neuro-fuzzy
controller) to three different OpenAI Gym [26] environments: CartPole,
MountainCar and LunarLander. In the CartPole environment, the agent is tasked
to balance a pole attached to a cart by applying a force of +1 or -1 to the
cart. In the MountainCar environment, an underpowered car on a one-dimensional
track is positioned between two hills. The goal is to drive the car up the
right hill, by driving back and forth to build momentum. Finally, in the
LunarLander environment the agent controls a 2D space ship and needs to land
it on a landing platform. The results are summarized in Figure 4. In all three
cases, the teacher model was a deep Q-network with 64 hidden nodes followed by
a BatchNorm layer111Models retrieved from https://github.com/araffin/rl-
baselines-zoo.

In all three environments, we see that naive substitution of the deep neural
network with a neuro-fuzzy controller is unable to learn a satisfying policy.
Figure 4 shows results obtained using the same number of rules as used in the
distillation algorithm. Experiments with double or triple the number of rules
had similar results, even when run for more than three times the number of
episodes.

In the CartPole and MountainCar environments, we used two fuzzy rules to
encode the student policy. This is the absolute minimum of rules, as a single
fuzzy rule would effectively encode a constant policy. The CartPole
environment has two available actions (push left, push right), so the two
rules can be interpreted as “when to move the cart left/right”. Remarkably,
the MountainCar environment has three actions (push left, no push, push
right). This means the fuzzy policy only uses two of the three available
actions, never using the “no push” action. In both environments, we see very
fast convergence, after 10 episodes for CartPole and only 5 episodes for
MountainCar, although MountainCar has more variance in the reward which can
mostly be attributed to variance in starting conditions.

Lunarlander is the most challenging environment. It has 8 input dimensions,
two of which (ground left and ground right) take only two discrete values (1
or 0). This causes the system to define degenerate fuzzy sets, which
negatively affects both performance and interpretability. This is a limitation
of the distillation algorithm, and finding intelligent ways to incorporate
discrete inputs in neuro-fuzzy systems is a possible direction for future
research. In this case, the best results were achieved by simply ignoring the
two discrete inputs. We tested the algorithm with both 4 or 6 fuzzy rules.
With 4 fuzzy rules (which is the number of available actions), the system is
able to match teacher performance in about half of the cases. More consistent
performance is reached with 6 rules, at the cost of system simplicity.

(a) CartPole

(b) MountainCar

(c) LunarLander (4 rules)

(d) LunarLander (6 rules)

Figure 4: Distillation results. We ran the distillation process 50 times for
each environment. Each figure shows the median, first quantile and third
quantile of the achieved reward for a given environment using the distillation
algorithm (blue curve) and using naive substitution of the deep Q-network with
a neuro-fuzzy controller (orange curve). The green line indicates the median
reward achieved by the teacher agent over 50 episodes.

We now give some examples of the resulting neuro-fuzzy controllers created by
the distillation algorithm. The fuzzy sets are shown in graphs, combined with
a table describing the accompanying fuzzy rules (see Figures 5, 6, and 7). The
opacity of the background color in the table shows the importance of the set
in the corresponding fuzzy rule. For example, the first row of the table in
Figure 5 should be read as: “IF position IS A0_0 with importance 0.07, AND
angle IS A2_0 with importance 0.07, AND velocity at tip is A3_0 with
importance 1.0, THEN the output is (2.88, -1.70)”. The outputs are the
Q-values for the available actions, so this rule pushes the cart to the left.

###  VII-A CartPole

Figure 5 shows a resulting neuro-fuzzy controller for the CartPole
environment. We can see that every input dimension has clearly distinguishable
“low” and “high” sets. The algorithm also assigned very low importance
($<0.01$) to each of the fuzzy sets in the second input dimension, which
caused them to be masked away in the post-processing step. This means that the
controller effectively learned that this input dimension is not necessary to
complete the task. We also see a very sharp contrast in importance values of
the rules, with almost all importance assigned to the v_tip dimension
(velocity at the tip of the pole). We can conclude from this that the velocity
at the tip of the pole is considered as much more important than the other
dimensions by this agent.

(a)

p_x | angle | v_tip | output
---|---|---|---
A0_0 | A2_0 | A3_0 | (2.88, -1.70)
A0_1 | A2_1 | A3_1 | (-0.01, 1.18)
(b)

Figure 5: Fuzzy sets (top) and rules (bottom) for the distilled CartPole
agent. All fuzzy sets for v_x were removed by the post-processing step,
effectively removing this input. Intensity of the background color (bottom) is
proportional to the importance weight of the corresponding fuzzy set.

###  VII-B MountainCar

Figure 6 shows a resulting controller on the MountainCar environment. We can
see very similar results to those obtained with CartPole. In this case, the
algorithm again ignores one of the two input dimensions, reaching the same
performance as the teacher using only the velocity of the car. This makes
sense, as the optimal policy can be viewed as simply “amplifying” the current
velocity (going left to build up potential energy or going right to try and
reach the goal) until the goal is reached.

(a)

v_x | output
---|---
A1_0 | (4.61, 0.47, -9.53)
A1_1 | (-0.42, -0.50, 2.62)
(b)

Figure 6: Fuzzy sets (top) and rules (bottom) for the distilled MountainCar
agent. All fuzzy sets for p_x were removed by the post-processing step,
meaning that the controller is only influenced by v_x.

###  VII-C LunarLander

Finally, we show a 4-rule neuro-fuzzy controller that matches teacher
performance on the LunarLander environment in Figure 7. The input now consists
of 8 dimensions, but the last two (gnd_left and gnd_right) are discarded as
they only take two discrete values (1 or 0). Incorporating those discrete
features causes the system to define degenerate fuzzy sets, which negatively
affects both performance and interpretability, a limitation of the algorithm.
The rules are now not as easily interpretable as in the CartPole and
MountainCar environments because of the relatively large number of input
dimensions, but fuzzy partitions are still mostly interpretable and the system
is able to identify a subset of input dimensions that is significantly more
important than the others, namely v_y (vertical velocity) and v_a (angular
velocity). Although we cannot easily and intuitively summarize the entire
policy, this still brings some insight into the inner workings of the system.

(a)

p_x | p_y | v_x | v_y | angle | v_a | output
---|---|---|---|---|---|---
- | - | - | - | A4_0 | A5_0 | (-3.10, 2.21, 1.34, -2.40)
A0_1 | A1_1 | A2_1 | A3_1 | A4_1 | A5_2 | (-8.90, -0.63, 5.04, -2.37)
A0_2 | A1_2 | A2_2 | A3_2 | A4_2 | A5_2 | (0.82, -6.59, -0.45, 3.80)
- | A1_3 | A2_3 | A3_3 | A4_3 | A5_3 | (2.84, 4.15, -3.03, -2.93)
(b)

Figure 7: Fuzzy sets (top) and rules (bottom) for the distilled LunarLander
agent. Intensity of the background color (bottom) is proportional to the
importance weight of the corresponding fuzzy set.

##  VIII Discussion

Although this technique is feasible for certain environments, there are some
obvious limitations to the neuro-fuzzy architecture. First of all, it only
makes sense to use this architecture if input features carry a semantic
meaning. If the input consists of raw pixel values for example, we cannot
reasonably expect fuzzy rules defined on these inputs to be interpretable. A
possible direction for future work could be to explore techniques for
extracting disentangled representations (e.g. using Variational Auto-Encoders
[27]) and to use these representations as input features for a neuro-fuzzy
controller.

In conclusion, we have demonstrated how distillation can be used to train
compact neuro-fuzzy controllers to solve tasks that they are unable to solve
directly. This technique opens the path to a new way of creating fuzzy
controllers: instead of manually designing a compact fuzzy controller, or
training a (much less compact) neuro-fuzzy controller, we can first train a
neural network to solve a task using Q-learning and then automatically distill
this policy into a compact neuro-fuzzy controller. Although this approach was
demonstrated only on toy environments in this work, it could be applied to
real-world control systems such as robotic control [12] or non-linear modeling
of dynamic systems [11]. Finally, more future work can be done to combine this
technique with existing literature in the field of (neuro-)fuzzy control. This
includes using alternative membership functions, training techniques [28] or
techniques for rule base simplification [29].

## References

  * [1] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” Dec. 2013.
  * [2] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” in _4th International Conference on Learning Representations, ICLR 2016 - Conference Track Proceedings_. International Conference on Learning Representations, ICLR, 2016.
  * [3] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. Van Den Driessche, T. Graepel, and D. Hassabis, “Mastering the game of Go without human knowledge,” _Nature_ , vol. 550, no. 7676, pp. 354–359, Oct. 2017.
  * [4] N. Frosst and G. Hinton, “Distilling a neural network into a soft decision tree,” Nov. 2017.
  * [5] G. Montavon, W. Samek, and K.-R. Müller, “Methods for interpreting and understanding deep neural networks,” Jun. 2017.
  * [6] J. R. Zech, M. A. Badgeley, M. Liu, A. B. Costa, J. J. Titano, and E. K. Oermann, “Confounding variables can degrade generalization performance of radiological deep learning models,” Jul. 2018.
  * [7] P. Voigt and A. von dem Bussche, _EU General Data Protection Regulation (GDPR) : A Practical Guide._ Springer International, 2018.
  * [8] P. Martin Larsen, “Industrial applications of fuzzy logic control,” _International Journal of Man-Machine Studies_ , vol. 12, no. 1, pp. 3–10, 1980.
  * [9] J. S. R. Jang, “ANFIS: Adaptive-network-based fuzzy inference system,” _IEEE Transactions on Systems, Man and Cybernetics_ , vol. 23, no. 3, pp. 665–685, 1993.
  * [10] J.-S. Jang and C.-T. Sun, “Neuro-fuzzy modeling and control,” _Proceedings of the IEEE_ , vol. 83, no. 3, pp. 378–406, Mar. 1995.
  * [11] Ł. Bartczuk, A. Przybył, and K. Cpałka, “A new approach to nonlinear modelling of dynamic systems based on fuzzy rules,” _International Journal of Applied Mathematics and Computer Science_ , vol. Vol. 26, no. no. 3, 2016.
  * [12] A. Chatterjee, K. Pulasinghe, K. Watanabe, and K. Izumi, “A particle-swarm-optimized fuzzy-neural network for voice-controlled robot systems,” _IEEE Transactions on Industrial Electronics_ , vol. 52, no. 6, pp. 1478–1489, Dec. 2005.
  * [13] K. Shihabudheen, S. K. Raju, and G. Pillai, “Control for grid-connected DFIG-based wind energy system using adaptive neuro-fuzzy technique,” _International Transactions on Electrical Energy Systems_ , vol. 28, no. 5, p. e2526, 2018.
  * [14] A. A. Rusu, S. G. Colmenarejo, C. Gulcehre, G. Desjardins, J. Kirkpatrick, R. Pascanu, V. Mnih, K. Kavukcuoglu, and R. Hadsell, “Policy distillation,” Nov. 2015.
  * [15] G. Hinton, O. Vinyals, and J. Dean, “Distilling the knowledge in a neural network,” Mar. 2015.
  * [16] X. Liu, X. Wang, and S. Matwin, “Improving the interpretability of deep neural networks with knowledge distillation,” _IEEE International Conference on Data Mining Workshops, ICDMW_ , vol. 2018-Novem, pp. 905–912, Feb. 2019.
  * [17] Y. Coppens, K. Efthymiadis, T. Lenaerts, and A. Nowe, “Distilling Deep Reinforcement Learning Policies in Soft Decision Trees,” p. 7.
  * [18] E. Puiutta and E. M. S. P. Veith, “Explainable Reinforcement Learning: A Survey,” in _Machine Learning and Knowledge Extraction_ , ser. Lecture Notes in Computer Science, A. Holzinger, P. Kieseberg, A. M. Tjoa, and E. Weippl, Eds. Cham: Springer International Publishing, 2020, pp. 77–95.
  * [19] W. M. Czarnecki, S. M. Jayakumar, M. Jaderberg, L. Hasenclever, Y. W. Teh, S. Osindero, N. Heess, and R. Pascanu, “Mix & match-agent curricula for reinforcement learning,” Tech. Rep.
  * [20] S. Schmitt, J. J. Hudson, A. Zidek, S. Osindero, C. Doersch, W. M. Czarnecki, J. Z. Leibo, H. Kuttler, A. Zisserman, K. Simonyan, and S. M. A. Eslami, “Kickstarting deep reinforcement learning,” Mar. 2018.
  * [21] E. Parisotto, J. L. Ba, and R. Salakhutdinov, “Actor-mimic: Deep multitask and transfer reinforcement learning,” Nov. 2015.
  * [22] L. A. Zadeh, “Fuzzy logic and approximate reasoning - In memory of Grigore Moisil,” _Synthese. An International Journal for Epistemology, Methodology and Philosophy of Science_ , vol. 30, no. 3-4, pp. 407–428, Sep. 1975.
  * [23] E. P. E. P. Klement, R. Mesiar, and E. Pap, _Triangular Norms_. Springer Netherlands, 2000.
  * [24] R. R. Yager, “Weighted triangular norms using generating functions,” _International Journal of Intelligent Systems_ , vol. 19, no. 3, pp. 217–231, Mar. 2004.
  * [25] R. P. Paiva and A. Dourado, “Interpretability and learning in neuro-fuzzy systems,” in _Fuzzy Sets and Systems_ , vol. 147, Oct. 2004, pp. 17–38.
  * [26] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “OpenAI gym,” Jun. 2016.
  * [27] E. Mathieu, T. Rainforth, N. Siddharth, and Y. W. Teh, “Disentangling disentanglement in variational autoencoders,” Tech. Rep.
  * [28] D. Hein, A. Hentschel, T. Runkler, and S. Udluft, “Particle swarm optimization for generating interpretable fuzzy reinforcement learning policies,” _Engineering Applications of Artificial Intelligence_ , vol. 65, pp. 87–98, Oct. 2017.
  * [29] M. Setnes, R. Babuška, U. Kaymak, and H. R. Van Nauta Lemke, “Similarity measures in fuzzy rule base simplification,” Tech. Rep. 3, 1998.


NVD

    National Vulnerability Database
IoT

    Internet-of-Things
CVE

    Common Vulnerabilities and Exposures
CPE

    Common Platform Enumeration
DDoS

    Distributed Denial of Service
FACT

    Firmware Analysis and Comparison Tool
ISA

    Instruction Set Architecture
GPL

    GNU General Public License
SDK

    Software Development Kit

# Towards Reliable and Scalable Linux Kernel CVE Attribution in Automated
Static Firmware Analyses

René Helmke and Johannes vom Dorp  Fraunhofer FKIE, Bonn, Germany, Email:
{rene.helmke<EMAIL_ADDRESS>
###### Abstract

In vulnerability assessments, software component-based CVE attribution is a
common method to identify possibly vulnerable systems at scale. However, such
version-centric approaches yield high false-positive rates for binary
distributed Linux kernels in firmware images. Not filtering included
vulnerable components is a reason for unreliable matching, as heterogeneous
hardware properties, modularity, and numerous development streams result in a
plethora of vendor-customized builds. To make a step towards increased result
reliability while retaining scalability of the analysis method, we enrich
version-based CVE matching with kernel-specific build data from binary images
using automated static firmware analysis. We open source an attribution
pipeline that gathers kernel configuration and target architecture to dry
build the present kernel version and filter CVEs based on affected file
references in record descriptions. In a case study with 127 router firmware
images, we show that in comparison to naive version matching, our approach
identifies 68% of all version CVE matches as false-positives and reliably
removes them from the result set. For 12% of all matches it provides
additional evidence of issue applicability. For 19.4%, our approach does not
improve reliability because required file references in CVEs are missing.

##  I Introduction

Safety, security, and privacy threats arise alongside embedded system markets.
Growing device numbers111https://iot-analytics.com/number-connected-iot-
devices/, Accessed: 2022-09-05. inflate attack surfaces, raising impact and
scope of newly found software vulnerabilities in domains pivotal to society
[1, 2, 3, 4]. Thus, it is important to maintain the software security of these
systems.

Embedded devices boot into _firmware_ : lightweight software packages tailored
to the device’s use case and limited resources [5]. Similar to general purpose
operating systems, they consolidate services, drivers, and interfaces, but in
contrast are highly specialized towards their purpose. Minimizing costs,
vendors commonly rely on Software Development Kits, which make heavy use of
open source. This gives the advantage of large development communities quickly
providing patches when security issues arise.

Linux serves as configurable, modifiable, slim, and powerful system layer in
many firmware images [6, 7]. It is open source, modular, and supports flavors
of the MIPS and ARM Instruction Set Architectures commonly used in embedded
devices. Vendors configure kernel builds to include all required functions,
remove unused components, and add custom functionality. The compiled kernel is
then distributed in binary form as part of the firmware.

As of 2022, there are over 2,900 Common Vulnerabilities and Exposures (CVE)
documenting security issues of varying severity affecting different Linux
kernel versions [8]. Yet, the firmware of various widely spread devices
contains obsolete or end of life kernels [6, 7]. This raises questions about
device exploitability regarding well-known vulnerabilities.

Intuitively, reproducible exploitation of the target provides undeniable proof
for CVE attribution. However, science has yet to find scalable and effective
methods for such dynamic verification in binary analysis [9, 10].
Heterogeneous system properties require custom solutions: For example, exploit
code may be unavailable for the target ISA [10]. Resource constraints and
missing build chains pose further challenges, as devices might be the only
testing platforms available[9]. Emulation and re-hosting are options, but
require substantial efforts to establish device compatibility [11, 12, 9].

Static analysis serves heuristics to find _imperfect_ proof for CVE
attribution, e.g., verifying code presence[13]. However, many approaches do
not scale well as they require considerable manual work and deep knowledge of
each CVE [10]. Parts are automatable, but needed data may be unavailable or
incorrect in repositories [14, 15]. Also, automation becomes increasingly
challenging in lights of proprietary formats, obfuscation, compiler
optimizations, and symbol stripping [5, 10].

In lack of applicable methods, large-scale approaches like firmware analysis
tools [16, 17, 18] and studies [7, 6, 19] commonly attribute bugs by matching
versions against CVE databases. Trading in reliability for applicability,
their results need manual verification but may raise awareness for potential
security issues.

In 2020, we used version matching as part of a large-scale empirical study on
home router security [7]. For the Linux kernel, this method proves
exceptionally unreliable: Due to custom build configurations, we can not
assume that kernels include components flagged as vulnerable for the subject
version. E.g., CVEs affecting hardware drivers that vendors removed from their
builds are not applicable, but the method does not cover this factor – leading
to false-positive matches.

Qualitative evaluation of our approach showed high false-positive rates as
build customizations for a control group of firmware samples were taken into
account. While the large result set might still be useful for analysts, more
precise methods are needed to reduce manual verification efforts [10].

To improve the reliability of version-based Linux CVE attribution in large-
scale scenarios, we enrich the process with kernel-specific data from
automated static firmware analysis. We extract kernel configurations from
binary images and reconstruct the kernel build process to identify included
components with file-level granularity. Hereby, we reduce the set of false-
positive matches requiring further manual verification.

In the following, we provide:

  1. 1.

A description of our methodology for Linux CVE attribution, based solely on
binary kernel representations.

  2. 2.

An empirical evaluation in which we compare our approach against naive
version-based CVE matching using the 2020 Home Router Security Report [7]
dataset.

Furthermore, we release the implementation of the methodology used for the
evaluation as open source to the public222https://github.com/fkie-cad/cve-
attribution-s2, Accessed: 2022-09-05..

##  II Background & Related Work

There are various automation approaches to discover and attribute security
issues in binary targets. Aside of version-based matching against
vulnerability repositories, they include code similarity and patch analysis
[20], taint analysis and symbolic execution [21], fuzzing [22], and various
emulation-based methods [9]. While we acknowledge substantial work done in
these directions, we point out their limited applicability in large-scale
analyses due to resource constraints, low emulation success rates, and missing
bootstrap data [10, 9].

Focusing on large-scale attribution of known security issues in firmware, this
section first discusses the scientific need for sound data as foundation of
reliable bug attribution (II-A). Then, we present attribution methods applied
in large-scale firmware security studies (II-B).

For comprehensive surveys on state of the art research and the problem space,
especially in terms of scalability and automation, we refer to Qasem et al.
[10] and Wright et al. [9].

###  II-A Sound Data as Foundation for Reliable Bug Attribution

Detail information on known vulnerabilities lays the foundation of reliable
bug attribution [10]. The community-driven CVE catalog [8] is the largest data
source and de facto standard for vulnerability identification. For each
tracked issue, there is an identifier, description, and follow-up references.
The derivative National Vulnerability Database (NVD) [23] adds data on
severity and impact scores, but also lists affected products and their
versions. The latter is encoded in an identification scheme, the Common
Platform Enumeration (CPE) [23].

Records vary in information quantity and quality. E.g., Sanguino and Uetz [15]
show that errors in CPE assignments, but also data inconsistencies harm
soundness. Code similarity approaches like [5] exemplify that pivotal data can
be missing or is hard to obtain, as they require access to ground truth
embedded in commits and patches. If CVEs affect closed source projects,
issuers will not share technical details on fixes in public. For open source,
Tan et. al. [14] show that code collection remains challenging: Patches are
unreferenced, not marked, incorrect, or hide in bug tracker discussions.

Thus, researchers construct small datasets of selected CVEs that their
proposed techniques can ingest for evaluation [10]. For each CVE, this implies
in-depth investigation, additional data aggregation, and technical bug
knowledge, which limits the applicability of previously mentioned approaches
for large-scale scenarios. The Vulncode-DB [24] addressed this issue and
annotated CVE data with fine-granular technical information, but got
discontinued due to bootstrapping problems.

As for Linux kernel CVEs, issuers embed references to bug locations in the
project’s source tree in CVE short descriptions [8]. In combination with
extracted build configurations from firmware, the proposal in this paper takes
advantage of this observation to identify components built into the kernel.

The _linuxkernelcves.org_ [25] project argues that for Linux’s many version
streams, contributors, and distributors, there is inaccuracy in CPE data to
precisely track affected versions. They crawl commit references in CVEs from
Linux distribution sources, e.g., Ubuntu and Android bug trackers, to
determine the first patch appearance in mainline kernels. However, while [25]
host a regularly updated dataset, they stress that their CVE post-processing
code has neither been evaluated nor published yet – result reliability is
unknown.

Figure 1: Our methodology describes a two-staged static analysis pipeline:
First, we extract, analyze, and annotate ingress firmware images to detect
kernel version, configuration, and architecture (left). Then, we fetch the
corresponding mainline kernel sources, install the configuration, and perform
a dry build to generate a file build log. In combination with a version-
filtered list of potentially attributable CVEs, we eliminate all records that
do not include affected component source files we witnessed during the dry
build.

###  II-B Static Bug Attribution in Large-Scale Firmware Analyses

In 2014, Costin et al. [6] execute a quantitative study on embedded device
security by analyzing 32.000 firmware images. They implement pattern-based
heuristics and specify indicators of security malpractice in firmware images,
e.g., hardcoded passwords, cryptographic material, but also included
application version numbers to attribute CVEs. Their static analysis yields
CVE matches in userspace applications of 693 firmware images. While they
inspect Linux kernel versions, these are not included in the bug attribution.
Furthermore, [6] report unsolved challenges in result verification, as not
only CVE data is incomplete, but also vendors may custom-patch affected files.
Since 2014, cross-architecture code similarity methods have drastically
improved and may be used as imprecise measure for verification in this case,
e.g., FirmUp [5]. However, acquiring and processing patches for thousands of
CVEs to bootstrap code similarity methods deems infeasible based on the
imprecise CVE repositories.

Zhao et al. [19] develop FirmSec, a large-scale static analysis pipeline to
empirically study vulnerabilities introduced by third-party components and
software in IoT devices. Here, a novelty is that they identify software
versions by extracting syntactical and control-flow graph features. They
construct a repository of 1,191 third party components and then extract
matching features out of the component’s corresponding source files. However,
they neither consider vendor-specific build configurations nor the Linux
kernel.

Similar to [6], we assess and compare the state of firmware security of 127
home routers available on German markets in our whitepaper Home Router
Security Report 2020 [7]. Using the automated Firmware Analysis and Comparison
Tool (FACT) [16], we also implement pattern-based heuristics to detect best
practice violations in firmware images. E.g., we analyze the usage of exploit
mitigation techniques like stack canaries and non-executable bits in userspace
binaries. To quantize the differences between used Linux kernels in devices
from a security perspective, we identified their versions, matched them
against the NVD [23] using CPE, and reported the results. Subsequent
discussions and observations proved that attributing CVEs only based on kernel
version leads to high false-positive rates and in effect to high manual
verification effort and low chance of adoption. On top of the issues of
uncertainty in CVE databases and unidentifiable vendor patches, we found that
the kernel’s high modularity, heterogeneity, and vendor-specific builds
inflated false-positives: Qualitative analysis showed that we matched for CVEs
in components that were verifiable absent in the build – as for some firmware
samples we were able to extract the kernel configuration to identify included
components.

We could not find any related work examining this Linux kernel-specific
problem in CVE attribution. Yet, we observed consistent information in
databases to identify components and their files affected by a CVE. In
combination with our observation of extractable build configurations, we
identify a research gap and possibility to reliably reduce false-positive
matches in kernel CVE attribution.

##  III Methodology

This section describes our proposed methodology to enrich the version-based
Linux kernel CVE attribution process with build-specific annotations. We show
an automated static analysis pipeline that finds and extracts kernel
configurations, dry builds the found kernel version, and filters CVEs based on
affected version and build log-included files.

Figure 1 provides an overview of our methodology. We establish a two-stage
process: In the first and left-hand stage, we unpack, analyze, and annotate
each file of an ingress firmware image. Gathered information includes Linux
kernel version, ISA, and kernel build configuration. In the second and right-
hand stage, we leverage upon said data to perform the actual CVE attribution
and filtering step. Yellow boxes in Figure 1 mark components this paper
contributes.

In the two following subsections III-A and III-B, we provide

⬇

1strings:

2 $v = /Linux version \d\\.\d{1,2}\\.\d{1,3}(-[\d\w.-]+)?/ nocase ascii wide

3

4condition:

5 $v and no_text_file

Listing 1: Software Components YARA rule to identify Linux kernel versions.
_no_text_file_ is a custom rule excluding _text/*_ MIME types.

detailed technical insights on each stage and step. We finish with a short
example of CVE-2017-17864 in III-C to demonstrate the added attribution
reliability our approach offers.

###  III-A Gather Kernel Information via Static Firmware Analysis

For stage one, we apply and enhance the firmware analysis tool FACT [16],
which is maintained at our research group. FACT is open source, comes with a
variety of firmware container unpackers, and provides a plugin system with
ready-to-use analysis modules we can leverage for kernel version and ISA
detection. In the following, we describe all pipeline steps that are of
importance for the proposed attribution methodology.

Consider an arbitrary firmware image. After submitting it to the pipeline,
FACT’s Unpack Scheduler tries to identify container formats. Choosing from a
palette of custom extractors and integrated tools like binwalk [26], it
recursively extracts or decompresses file contents until all options are
exhausted.

The Analysis Scheduler receives each extracted file and applies a
preconfigured set of analysis plugins. These implement heuristics, e.g., based
on YARA [27] rules, third party tools like checksec [28], or custom analysis
implementations. Analyzed files and their annotated results are stored in the
Result Database & File Storage.

Our methodology depends on the results of three plugins: Software Components,
Kernel Configuration, and Architecture Detection. While FACT already provides
the former and latter, this paper contributes the new Kernel Configuration
plugin.

The Software Components plugin applies YARA rules to detect various software
components along with their version. One of the rules, a part of which is
shown in Listing 1, detects the Linux kernel and its version.

We contribute the Kernel Configuration plugin, which detects and extracts
Linux kernel build information. Stage two of our pipeline requires this data
to filter out CVEs applicable to components excluded from the build.

Figure 2 illustrates the plugin’s high-level control flow. Not explicitly
stated edge transitions lead to analysis termination. Inside a firmware,
kernel configurations may be present in different plain text and binary
formats. Thus, depending on the file’s MIME type, the plugin differentiates
between kernel-related binary files and plain text. Here, plain text is the
most straightforward case, as the plugin then checks for headers and build
configuration directives. An example plain text configuration can be found in
the Debian Repositories333https://salsa.debian.org/kernel-
team/linux/-/blob/master/debian/config/arm64/config, Accessed: 2022-09-05..

Figure 2: High-level control flow of the Kernel Configuration analysis plugin.
It detects configurations in plain text files, kernel images, and modules.
Decompression takes place if needed. Results are annotated to the file.

Another way to obtain the configuration is by making use of an enabled
CONFIG_IKCONFIG444https://github.com/torvalds/linux/blob/master/init/Kconfig,
Accessed: 2022-09-05. directive: When it is set to Y during the firmware
kernel’s build time, a copy of the configuration is embedded into the binary
image – either as inline string or compressed container. If it is set to M,
said information is outsourced to a kernel module. Thus, if the file is either
a kernel image or module, our plugin searches for a magic word that is
prepended to the inline string. Once found, we apply a set of signatures to
detect the correct format of the embedded configuration and annotate our
findings to the analyzed file. Otherwise, we seek for embedded containers, try
to extract them, and again check for magic word and format.

The Architecture Detection plugin identifies target ISAs using four different
measures. For executable files in ELF format, it parses the e_machine and
e_flags fields of the file header. For kernel configurations, it searches for
the presence of architecture-specific feature directives. E.g.,
ARM64_USE_LSE_ATOMICS is only supported by the ARMv8 specification.
Furthermore, the plugin detects and parses CPU information from device trees
[29] – a widely spread bootloader-to-operating-system interface which also
lists system hardware and its properties. Finally, the plugin does also rely
on MIME databases to identify any file type that might leak target platform
information.

###  III-B Build Log-assisted CVE Attribution

The build log-assisted CVE attribution is the second stage of our proposed
analysis pipeline in Figure 1. Here, we first use FACT’s REST API to
consolidate the kernel version, kernel build configuration, and detected
target ISA.

Then, the Kernel Downloader fetches version sources from _kernel.org_. Note
that the assumption of vendors using a mainline, i.e., unmodified, kernel is
false in general due to custom patching and additional proprietary components.
Large parts of Linux are licensed under the GNU General Public License (GPL)
and, thus, modifications must be published555https://www.gnu.org/licenses/gpl-
faq.html, Accessed: 2022-09-05.. However, for two reasons we could not find a
scalable way to obtain these versions: First, some vendors distribute packages
through individual processes on
request666https://www.zyxel.com/form/gpl_oss_software_notice.shtml, Accessed:
2022-09-05.. Second, the required build tools do not have to be part of the
package – which is pivotal to our pipeline.

Dry Build is the next step in Figure 1: We set the target ISA and install the
extracted kernel build configuration in the downloaded kernel source code.
Then, we execute a dry run via make, which does not compile the kernel but
prints each compilation recipe instead. This approach has the advantage of low
computational overhead and does not require cross-compilation environment
bootstrapping. The goal of this step is to gather a list of source files from
the build log, which our pipeline _witnessed_ to be included in the kernel.

The CVE Fetcher executes simultaneously. Here, we query the NVD [23] dataset
for all Linux kernel CVEs and filter out all records that do not refer CPEs
stating the extracted Linux kernel version to be vulnerable. The resulting set
of potentially applicable CVEs is the output of version-based attribution.

Finally, the File Filter step combines the outputs of CVE Fetcher and Dry
Build: As we observed that Linux kernel CVEs state the affected source files
in their short description, records from the version-based result set can be
eliminated. We reduce it by removing every CVE that does not reference an
affected file we witnessed in the build log.

###  III-C Short Example - CVE-2017-17863

To demonstrate the practical addition of our Linux kernel CVE attribution
pipeline, we shortly present an example using
CVE-2017-17863777https://nvd.nist.gov/vuln/detail/CVE-2017-17863, Accessed:
2022-09-05.. The record description states an invalid memory access due to an
integer overflow in kernel/bpf/verifier.c. Also, CPE states that kernel
versions from 4.9 to 4.9.71 are vulnerable.

Consider a firmware sample with Linux kernel 4.9.60 and the underlying kernel
configuration. Naive version-based matching reports a positive match as the
version is within CPE range. However, if the configuration shows that BPF
support is disabled because CONFIG_BPF is set to N, all associated source
files, including kernel/bpf/verifier.c, are excluded from the compilation.
Thus, our proposed attribution method does not witness the affected file
presence during the dry build step: CVE-2017-1786 is a false-positive match
and we can eliminate it from the result set.

##  IV Case Study

We perform a case study to evaluate the reliability of our enriched version-
based Linux kernel CVE attribution in large-scale static analyses. For this
purpose, we let our pipeline analyze the Home Router Security Report 2020 [7]
corpus, which vendors reported to yield high false-positive rates using
version-based CVE matching. We raise two research questions:

  * R1

Our methodology requires access to specific information in firmware samples
and CVE repositories. How many samples and CVEs fulfill these modalities? _How
applicable is our approach in a real-world scenario?_

  * R2

With version-based CVE matching as baseline, _what impact has the methodology
on result reliability?_

In the following subsections, we first provide detailed information on our
experiment and used dataset (IV-A). Then, we present the results and analyze
them within the context of both stated research questions (IV-B and IV-C,
respectively).

###  IV-A Experiment & Firmware Corpus

Experiment Execution. We deploy our static analysis CVE attribution pipeline
on a system with AMD Ryzen 7 2700x processor and 32 GiB DDR4 RAM, running
Ubuntu 20.04.4 LTS. FACT v4.0 (commit 38df4883) is used in the first pipeline
stage. We extract each firmware of the Home Router Security Report 2020 [7]
corpus and apply the required analysis plugins CPU Architecture, Software
Components, and Kernel Configuration (cf., Section III-A). The second pipeline
stage executes on the same machine based on a snapshot of the NVD [23] – taken
on 2022-08-30. The snapshot has records for 2,910 Linux kernel CVEs
attributable through CPE. For each component in our system, we collect details
on ingress and egress data, including plugin results, version-based CVE
matches, and filtering decisions.

Firmware Corpus. The analyzed Home Router Security Report [7] corpus is
publicly documented888https://github.com/fkie-cad/embedded-evaluation-
corpus/blob/master/2020/FKIE-HRS-2020.md, Accessed: 2022-09-05.,
reconstructable, and consists of firmware from 127 home routers available in
the european market. Devices of seven well-known vendors are included: ASUS,
AVM, D-Link, Linksys, Netgear, TP-Link, and Zyxel. Samples were scraped on
2020-03-27.

Figure 3 shows the distribution of Linux kernel versions detected by FACT
across all firmware images. Numbers in parentheses and on top of bars count
sample sizes per vendor and kernel. Patch levels are clustered by major and
minor release for illustrative purposes, but are considered during CVE
attribution. Across all 127 samples, 121 binary distributed Linux kernels from
v2.4.20 to v4.4.60 are included. 11 firmware images are not analyzable due to
failed operating system analysis or unpacking errors. Note that firmware can
contain multiple kernels, e.g., embedded devices may consist of subcomponents
running their own systems.

Figure 4 shows the relative architecture distribution across all samples,
clustered by vendor. MIPS and ARM ISAs dominate the corpus, both in big and
little endian. It includes different word lengths, but the majority of devices
uses 32-bit. The ISA is unknown for 24 samples. More detailed insights into
the corpus can be found in [7].

We argue that the corpus is of sufficient size to demonstrate applicability,
but also choose it to investigate the reliability of matches we reported in
[7] using naive version-based Linux kernel CVE attribution. Furthermore, it
offers heterogeneous properties beneficial for our case study, as it covers
Linux kernels from three major releases, widely-spread ISAs, and devices of
multiple vendors. A drawback is that other device classes than home routers
are missing.

Figure 3: Kernel version distribution of the subject Home Router Security
Report 2020 dataset [7], which was scraped on 2020-03-27. Patch versions are
clustered by major and minor release. Across 127 firmware images from 7
different vendors, FACT found 121 Linux kernels between v2.4.20 and v4.4.60.
For 11 samples, no operating system could be identified (_unk._). Figure 4:
Relative CPU Architecture Distribution across all firmware samples, clustered
by vendor. MIPS and ARM, both in big and little endianess are prevalent in
this firmware corpus of home router devices. Figure 5: Filter verdict
distribution of our pipeline relative to the baseline CVE attribution results
for each of the 44 analyzed kernels. Each entry on the horizontal axis
represents a unique firmware. We classify them into four different verdict
confidence categories. With high confidence, our methodology marks around
$68.37\%$ of all baseline matches as false-positive and $12.04\%$ as true-
positive candidates (medians). Relative path matches with medium confidence
match verdict are negligible with $0.19\%$.

###  IV-B R1 Analysis – Applicability in Real-World Scenarios

How applicable is our approach in real-world large-scale automated firmware
analyses? To find answers to this question we identify two methodological
requirements that must be fulfilled for each firmware and Linux CVE,
respectively:

  1. S1

FACT firmware extraction and plugin analyses of stage one must succeed to
consolidate the kernel version, ISA, and kernel configuration.

  2. S2

CVE descriptions must reference affected files to filter vulnerable components
not included in the kernel build.

Using the firmware corpus, we evaluate egress and ingress data of each step in
the proposed pipeline with regards to these requirements. Table I shows the
results. Highlighted rows designate effective requirement fulfillment rates
over all analyzed firmware images and Linux kernel CVEs.

S1 Requirement (FACT Analysis Success)
---
| FW Matches [#] | Fulfilled$\left[\frac{\text{FW Matches}}{\text{FWs Total}}\right]$
Extraction | 116 | $0.9133$
Kernel Version | 116 | $0.9133$
Architecture Detection | 103 | $0.8110$
Kernel Configuration | 44 | $0.3464$
S2 Requirement (File Reference in Linux Kernel CVE)
|  CVE Matches | Fulfilled$\left[\frac{\text{CVE Matches}}{\text{CVEs Total}}\right]$
Full Path Reference | 1743 | $0.5990$
File Only Reference | 129 | $0.0443$
No Reference | 1038 | $0.3567$
TABLE I: Method Applicability Analysis for the Firmware Corpus

For requirement S1, FACT successfully extracts 116 out of 127 firmware images.
The analyses detect at least one kernel version in all extractable firmware,
and ISAs in 103 of them. However, our Kernel Configuration plugin finds build
information in only 44. As this plugin depends on results from previous
analyses (cf., Section III), the matches are a subset of the extracted
firmware images with identified ISA and kernel version. With missing Kernel
Configurations as limiting factor of method applicability, $34.64\%$ of all
analyzed firmware samples fulfill requirement S1. This rate is explainable
considering that a) IKCONFIG must be explicitly enabled to embed kernel
configurations into binary representations and b) it is common practice for
vendors to strip and obfuscate valuable analysis information from firmware.

For requirement S2 (affected files must be referenced in Linux kernel CVE
descriptions), data analysis over all Linux CVEs inside the NVD yields three
different categories: Files are either referenced as Full Path relative to the
kernel’s source tree, or the reference is File Only (location in the source
tree is unknown), or No Reference exists at all. Table I distributes all 2,910
Linux kernel CVEs across these classes, showing that the proposed approach is
applicable to $1,872$ ($64.33\%$) kernel CVEs. For CVEs with no included file
reference, the approach falls back to version-based CVE matching and, thus,
can not add value to result reliability.

###  IV-C R2 Analysis – Impact on CVE Attribution Result Reliability

With version-based Linux kernel CVE matching as baseline, what impact has our
attribution pipeline on result reliability? We approach research question R2
by analyzing the attribution results of all 44 firmware images our methodology
is applicable to (cf., Section IV-B). Subject samples include kernels ranging
from v3.4.0 to v4.4.60. Out of these, only one still receives mainline updates
at the time of this evaluation (4.4.x).

The baseline method attributes a median of 1,196 CVEs per firmware image,
which is roughly $40\%$ of _all_ Linux kernel CVEs present in the NVD. A
possible explanation lies within unsound and/or unmaintained CVE records in
the NVD [15, 14]. Yet, such imprecise data would also imply the existence of
false-negatives that should have been attributed to the kernel version, but
were not due to incorrect CPE. An argument in favor of these results is the
amount of end of life kernels in the dataset. However, based on the results we
present in the following paragraphs, there is reason to assume that the
baseline yields exceedingly high false-positive rates.

Version-based CVE attribution is an intermediate result of our methodology
(cf., Section III). To estimate the impact our pipeline has on result
reliability, we consolidate all decisions of the build-log assisted filtering
to classify them into four categories of verdict confidence:

  * •

Applicable (High) – CVE references affected files and full file path is
witnessed in build log.

  * •

Not Applicable (High) – CVE references affected files but none of them is
present in the build log.

  * •

Applicable (Medium) – CVE references affected files, but does not state full
file paths. A file was matched and seen in the build log, but ambiguity exists
due to duplicate names in the source tree.

  * •

Applicable (Low) – No file references, we can not decide on applicability and
fall back to version-based matching.

The idea is to map persuasiveness of additional evidence the pipeline gathers
within a trial: File matches are witnesses for CVE applicability, but not
every match is equally credible.

Figure 5 shows the filter verdict distribution of our pipeline relative to the
baseline CVE attribution results for each analyzed kernel. Versions are
ordered from oldest (left) to newest (right). Note that a single kernel was
found in each one of the 44 analyzed samples. Thus, each entry on the
horizontal axis represents a unique firmware. In the following, all discussed
distribution values are medians across all samples.

The proposed Linux kernel CVE attribution methodology is able to make a medium
to high confidence decision for $80.6\%$ of all version-based matches. The
portion of high confidence applicable CVE matches is $12.04\%$. Relative path
matches yielding medium confidence applicability are negligible with $0.19\%$.
As indicated by the bottom bars belonging to the class of Not Applicable
(High), our pipeline attributes $68.37\%$ of all version-based CVE matches as
_false-positives_ and filters them out of the result set. In numbers - out of
the median 1,196 matches per firmware, we reduce the set of potentially
applicable CVEs to roughly 378. Thus, we significantly reduce the result set
of potentially applicable CVEs requiring manual verification by analysts and
vendors. The portion of low confidence applicability due to missing file
references is $19.4\%$. Unfortunately, for this class of matches our
methodology does not generate added value.

##  V Limitations

We identify methodological shortcomings in three dimensions: applicability,
sound ground truth, and functionality.

In terms of applicability, our Linux kernel CVE attribution pipeline is bound
to FACT’s static analysis success. If the kernel version, ISA, and build
configuration remain unknown, our method can not identify possibly included
components for reliable CVE filtering. Then, the pipeline becomes
inapplicable. Yet, the case study in Section IV shows that (in the used
firmware corpus) there is still a considerable amount of firmware fulfilling
all requirements.

As for sound ground truth, reliable and true-positive CVE attribution is
limited by the quality of its underlying dataset. If Linux kernel CVE records
do not reference truly affected versions and source files, the proposed
mechanisms introduce false-positive, but also false-negative matches. In this
case, result reliability is negatively affected. Our assumption of vendors
using mainline kernels is another limiting factor that affects reliability,
but a methodical necessity due to missing insider information. Vendors may
cherry-pick patches or introduce custom fixes, which are not detectable by our
approach. While some of the modifications might be obtainable through GPL
portals, we identify the issue of scalable accessibility.

Regarding functional limits, we stress the inherited limitations of static
analyses. They may use heuristics to find indicators of possible bug presence,
but can hardly serve definitive proof – which requires triggering the bug.

Finally, the conducted case study is limited in its validity, as the used
corpus is missing in device class heterogeneity.

##  VI Conclusion

In this paper, we focused on improving result reliability of version-based CVE
matching for the special case of binary Linux kernels in large-scale static
firmware analyses. Heterogeneous hardware properties, modularity, numerous
development streams, and vendor-specific builds cause high false-positive
rates. This is because the attribution method does not check for vulnerable
component presence in binary images when filtering CVEs.

Despite general automation issues due to unsound or incomplete data in CVE
repositories and common challenges in binary firmware analyses, we found
supplementary filter data in Linux issue descriptions and firmware samples to
reduce the set of false-positive matches in scale. We enriched naive version-
based CVE matching with a static attribution pipeline that detects kernel
configurations and ISAs in firmware images to reconstruct the kernel build
process and guess included source files. This data then serves as filter using
kernel CVEs where affected files are explicitly stated.

The case study shows that, with the limitations discussed in Section V in
mind, our approach is scalable and moderately applicable: For $34.64\%$ of all
127 considered home router firmware images, the technical requirements are
fulfilled and about $65\%$ of all Linux kernel CVEs reference affected files
in their description.

With naive version-based matching as baseline, the introduced approach
generates a high confidence filter verdict for $80.6\%$ of all considered CVEs
and reduces the result set by $68.37\%$: CVEs affecting components probably
absent from binary kernel samples are successfully eliminated. While a non-
negligible amount of CVEs that our method can not reliably filter remains, we
conclude that the proposed attribution pipeline is a promising step towards
more reliable and scalable static CVE attribution. Security analysts are still
required to verify the true applicability of a bug, but our systematic and
automated filtering may at least reduce their manual efforts.

Stage one of our pipeline is part of the publicly available FACT [16], stage
two is a set of standalone scripts available at https://github.com/fkie-
cad/cve-attribution-s2, and our case study corpus is documented for
reconstruction at https://github.com/fkie-cad/embedded-evaluation-corpus.

##  VII Future Work

In future work, we want to address missing device class heterogeneity present
in our case study corpus. Aside of identifying and implementing additional
filter criteria, we evaluate options to combine the proposed methodology with
_linuxkernelcves.org_ [25]. The CPE data used for version matching is of
varying quality [15] and may introduce false-positives and -negatives not
caught by our methodology. A more fine-granular commit-based version tracking
as offered by [25] is a promising addition to our pipeline. However, a
thorough review of the automatically applied method is required before
adapting this data source over the de-facto standard of the NVD.

## References

  * [1] A. Giri _et al._ , “Internet of Things (IoT): A Survey on Architecture, Enabling Technologies, Applications and Challenges,” in _Proc. of the 1st International Conference on Internet of Things and Machine Learning (IML ’17)_. Liverpool, United Kingdom: Association for Computing Machinery, 2017, pp. 1–12. [Online] https://doi.org/10.1145/3109761.3109768
  * [2] H. Xu _et al._ , “A Survey on Industrial Internet of Things: A Cyber-Physical Systems Perspective,” _IEEE Access_ , vol. 6, pp. 78 238–78 259, 2018. [Online] https://doi.org/10.1109/ACCESS.2018.2884906
  * [3] S. M. R. Islam _et al._ , “The Internet of Things for Health Care: A Comprehensive Survey,” _IEEE Access_ , vol. 3, pp. 678–708, 2015. [Online] https://doi.org/10.1109/ACCESS.2015.2437951
  * [4] N. Neshenko _et al._ , “Demystifying IoT Security: An Exhaustive Survey on IoT Vulnerabilities and a First Empirical Look on Internet-Scale IoT Exploitations,” _IEEE Communications Surveys & Tutorials_, vol. 21, no. 3, pp. 2702–2733, 2019. [Online] https://doi.org/10.1109/COMST.2019.2910750
  * [5] Y. David, N. Partush, and E. Yahav, “FirmUp: Precise Static Detection of Common Vulnerabilities in Firmware,” in _Proc. of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’18)_. Williamsburg, USA: Association for Computing Machinery, 2018, p. 392–404. [Online] https://doi.org/10.1145/3173162.3177157
  * [6] A. Costin _et al._ , “A Large-Scale Analysis of the Security of Embedded Firmwares,” in _Proc. of the 23rd USENIX Conference on Security Symposium (SEC ’14)_. San Diego, USA: USENIX Association, 2014, p. 95–110. [Online] https://dl.acm.org/doi/10.5555/2671225.2671232
  * [7] P. Weidenbach and J. vom Dorp, _Home Router Security Report 2020_. Fraunhofer Institute for Communication, Information Processing and Ergonomics (FKIE), Technical Report, 2020. [Online] https://www.fkie.fraunhofer.de/en/press-releases/Home-Router.html
  * [8] The MITRE Corporation, “Official CVE Program Database,” Accessed: 2022-09-05. [Online] https://www.cve.org/
  * [9] C. Wright _et al._ , “Challenges in Firmware Re-Hosting, Emulation, and Analysis,” _ACM Computing Surveys_ , vol. 54, no. 1, pp. 1–36, 2021. [Online] https://doi.org/10.1145/3423167
  * [10] A. Qasem _et al._ , “Automatic Vulnerability Detection in Embedded Devices and Firmware: Survey and Layered Taxonomies,” _ACM Computing Surveys_ , vol. 54, no. 2, pp. 1–42, 2021. [Online] https://doi.org/10.1145/3432893
  * [11] D. Chen _et al._ , “Towards Automated Dynamic Analysis for Linux-based Embedded Firmware,” in _Proc. of the 2016 Symposium on Network and Distributed System Security (NDSS ’16)_. San Diego, USA: Internet Society, 2016, pp. 1–16. [Online] https://doi.org/10.14722/ndss.2016.23415
  * [12] M. Kim _et al._ , “FirmAE: Towards Large-Scale Emulation of IoT Firmware for Dynamic Analysis,” in _Proc. of the 2020 Annual Computer Security Applications Conference (ACSAC ’20)_. Austin, USA: Association for Computing Machinery, 2020, p. 733–745. [Online] https://doi.org/10.1145/3427228.3427294
  * [13] S. Lipp, S. Banescu, and A. Pretschner, “An Empirical Study on the Effectiveness of Static C Code Analyzers for Vulnerability Detection,” in _Proc. of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’22)_. Virtual, Republic of Korea: Association for Computing Machinery, 2022, p. 1–12. [Online] https://doi.org/10.1145/3533767.353438
  * [14] X. Tan _et al._ , “Locating the Security Patches for Disclosed OSS Vulnerabilities with Vulnerability-Commit Correlation Ranking,” in _Proc. of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS ’21)_. Virtual, Republic of Korea: Association for Computing Machinery, 2021, p. 3282–3299. [Online] https://doi.org/10.1145/3460120.3484593
  * [15] L. A. Benthin Sanguino and R. Uetz, “Software Vulnerability Analysis Using CPE and CVE,” _ArXiv_ , 2017. [Online] https://doi.org/10.48550/arXiv.1705.05347
  * [16] Fraunhofer FKIE, “FACT - Firmware Analysis and Comparison Tool,” Accessed: 2022-09-05. [Online] https://github.com/fkie-cad/FACT_core
  * [17] ONEKEY GmbH, “ONEKEY Automated Firmware Analysis Platform,” Accessed: 2022-09-05. [Online] https://onekey.com/
  * [18] NetRise Inc., “NetRise Platform - Next-Generation Firmware & IoT Security Platform,” Accessed: 2022-09-05. [Online] https://www.netrise.io/
  * [19] B. Zhao _et al._ , “A Large-Scale Empirical Analysis of the Vulnerabilities Introduced by Third-Party Components in IoT Firmware,” in _Proc. of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’22)_. Virtual, South Korea: Association for Computing Machinery, 2022, p. 442–454. [Online] https://doi.org/10.1145/3533767.3534366
  * [20] I. U. Haq and J. Caballero, “A Survey of Binary Code Similarity,” _ACM Computing Surveys_ , vol. 54, no. 3, pp. 1–38, 2021. [Online] https://doi.org/10.1145/3446371
  * [21] R. Baldoni _et al._ , “A Survey of Symbolic Execution Techniques,” _ACM Computing Surveys_ , vol. 51, no. 3, pp. 1–39, 2018. [Online] https://doi.org/10.1145/3182657
  * [22] V. J. Manès _et al._ , “The Art, Science, and Engineering of Fuzzing: A Survey,” _IEEE Transactions on Software Engineering_ , vol. 47, no. 11, pp. 2312–2331, 2021. [Online] https://doi.org/10.1109/TSE.2019.2946563
  * [23] National Institute of Standards and Technology, “National Vulnerability Database,” Accessed: 2022-09-05. [Online] https://nvd.nist.gov/
  * [24] R. Habalov and T. Schmid, “Vulncode-DB,” Accessed: 2022-09-05. [Online] https://www.vulncode-db.com/
  * [25] N. Luedtke and Contributors, “Linux Kernel CVEs,” Accessed: 2022-09-05. [Online] https://www.linuxkernelcves.com/
  * [26] Microsoft, “Binwalk,” Accessed: 2022-09-05. [Online] https://github.com/ReFirmLabs/binwalk
  * [27] Google, “YARA - The pattern matching swiss knife for malware researchers (and everyone else),” Accessed: 2022-09-05. [Online] https://virustotal.github.io/yara/
  * [28] T. Klein and B. Davis. checksec.sh. [Online] https://github.com/slimm609/checksec.sh
  * [29] Linaro Ltd., “DeviceTree Specification,” Release v0.4-rc1, 2021. [Online] https://github.com/devicetree-org/devicetree-specification/releases/download/v0.4-rc1/devicetree-specification-v0.4-rc1.pdf

  *[CVE]: Common Vulnerabilities and Exposures
  *[CVEs]: Common Vulnerabilities and Exposures
  *[ISA]: Instruction Set Architecture
  *[NVD]: National Vulnerability Database
  *[CPE]: Common Platform Enumeration
  *[IoT]: Internet-of-Things
  *[FACT]: Firmware Analysis and Comparison Tool
  *[ISAs]: Instruction Set Architecture
  *[GPL]: GNU General Public License
  *[CPEs]: Common Platform Enumeration