# Neural Decoding with Optimization of Node Activations

Eliya Nachmani, Yair Be’ery E. Nachmani is with the School of Electrical
Engineering, Tel-Aviv University, Tel-Aviv 6997801, Israel, and also with
Facebook AI Research, Menlo Park, CA 94025, (e-mail: enk100@gmail.com)Y.
Be’ery is with the School of Electrical Engineering, Tel-Aviv University, Tel-
Aviv 6997801, Israel (e-mail:ybeery@eng.tau.ac.il).

###### Abstract

The problem of maximum likelihood decoding with a neural decoder for error-
correcting code is considered. It is shown that the neural decoder can be
improved with two novel loss terms on the node’s activations. The first loss
term imposes a sparse constraint on the node’s activations. Whereas, the
second loss term tried to mimic the node’s activations from a teacher decoder
which has better performance. The proposed method has the same run time
complexity and model size as the neural Belief Propagation decoder, while
improving the decoding performance by up to $1.1dB$ on BCH codes.

###### Index Terms:

Information Theory, Deep learning, Error Correcting Codes, Neural decoder.

##  I Introduction

Deep learning has become in last years an effective tool for communication
tasks, for example, MIMO detection[1, 2], modulation and demodulation [3, 4,
5], equalization[6], learning encoders and decoders [7] designing new codes
[8] which outperform codes for feedback channels [9, 10], feedback decoders
[11] and decoding[12, 7].

Decoding error-correcting codes with novel deep learning techniques is an
emerging research field. The Neural Belief Propagation (NBP) [12] was the
first deep neural decoder that provide an improvement over the vanilla Belief
Propagation decoder. Over the last few years, a large research effort to
further improve the deep neural decoders was made to obtain better bit-error-
rate decoding. Most of the previous work has tried to find better neural
architecture to improve the decoder’s performance. For example, Vasic et
al.[13] proposed a neural decoder that has activation functions that emulate
message update functions. Their proposed method achieves higher throughput at
the cost of additional decoding complexity. Nachmani et al. [14] proposed an
hypernetwork decoder that uses graph neural networks as a neural decoder that
improves the NBP decoder with additional decoding complexity. Choukroun et al.
[15] suggested a Transformer neural decoder which improves the hypernetwork
decoder at the cost of additional complexity. Chen et al. [16] showed that a
neural decoder with a shift-invariant structure on the weights further
improves the NBP results. Their method uses a bigger parity check matrix which
increases the decoding complexity of the decoder. Another line of work tried
to change the loss function to improve the performance. Lugosch et al. [17]
introduced a novel syndrome loss function that penalizes the neural decoder
for producing outputs that do not correspond to valid codewords. The proposed
method yields decoders with improved bit-error-rate with no additional
decoding complexity. A pruned version of the neural decoder has been proposed
in [18] which removes irrelevant check nodes. Another main research direction
in the information theory community was to find sparse parity check matrices
[19], which resulted in better decoding performance. For example, in [20] very
sparse matrices achieve performance that is close to the Shannon limit. The
sparse parity check matrices result in a sparse Tanner graph which indicates
that sparse constraint may improve the neural decoding architectures.

As we can observe, previous work have tried to improve the results by changing
the neural architecture, the loss function at the output layer or finding
better sparse parity check matrix. Therefore, one can ask whether a direct
node optimization can further improve the results, since it gives direct
gradient updates to the neural decoder that produce better learning. In this
paper we propose to use two novel loss terms that optimize the decoders nodes:
(i) sparse node loss and (ii) knowledge distillation loss. Sparse activation
regularization [21] is a well known technique that imposes sparse constrained
on the activation with new loss function term. Since we know that sparse
parity check matrices lead to better decoding performance, we propose teaching
the neural network decoder with sparse nodes. Therefore, the proposed neural
sparse decoder behaves as a neural decoder with sparse parity check matrix. As
expected, our simulation shows that the learned neural sparse decoders gives
large improvement over the baseline. Knowledge distillation is a basic
technique in deep learning where one uses a teacher network to guide the
training of a smaller student neural network [22]. We propose to use the
knowledge distillation method by an expert teacher network to constraint the
nodes of the proposed neural decoder. The student tries to decode the
transmitted codeword with a novel loss term that mimics the teacher node
activations. Our simulations shows that we can further gain improvement when
using the knowledge distillation loss.

Since our method adds new loss terms to the training, the method preserves the
same complexity run-time as the original neural decoder. Furthermore, our
method does not have additional weights and has the same model size as the
baseline neural decoder. Our paper makes the following contributions:

  * •

We present novel sparse node activation loss.

  * •

We present a knowledge distillation loss term.

  * •

We demonstrate that each of the new loss terms (and both combined) improves
the results of the baseline methods by a large margin without adding
computational complexity.

##  II Background

In this section, we will briefly explain the Belief Propagation (BP) decoder
for a communication scheme for Binary Phase Shift Keying (BPSK) and binary
code. We will use similar notations as in Lugosch et al. [23] and recap the
offset min-sum BP decoder [24] as well as the neural min-sum decoder [23].
Denote the block code length by $n$, the transmitted and received information
vector as $X\in\mathbb{R}^{n}$ and $Y\in\mathbb{R}^{n}$ respectively. The
transmitted vector $X$ has $-1,+1$ values since we consider BPSK modulation.
The received vector $Y$ at the receiver is given by $Y=X+Z$, where
$Z\in\mathbb{R}^{n}$ is the channel noise. For additive white Gaussian noise
(AWGN) channel, the input vector to the BP decoder is the log-likelihood-ratio
(LLR). The $v$’th element $l_{v}$ of the LLR vector is given by:

$l_{v}=\log\frac{\Pr\left(Y_{v}=y_{v}|X_{v}=-1\right)}{\Pr\left(Y_{v}=y_{v}|X_{v}=+1\right)}=\frac{2y_{v}}{\sigma^{2}}$
(1)

where $y_{v}$ is the channel output, $\sigma^{2}$ is the known channel noise
variance, and $X_{v}$ is the $v$’th element of the transmitted vector $X$. The
BP decoder exchanged messages between variable and check nodes layers
iteratively. The variable and check layers obtain from the Tanner graph of the
parity check matrix. The variable and check layer contain variable and check
nodes respectively. An edge $e$ connects $c$ check nodes to $v$ variable node
if the $(c,v)$ entry in the parity check matrix contains $1$. The message from
the variable node $v$ to check node $c$ is given by:

$\mu_{v,c}(t)=l_{v}+\sum_{c^{\prime}\in\mathcal{N}(v)\backslash
c}\mu_{c^{\prime},v}(t-1)$ (2)

where $t$ is the number of iterations, $\mathcal{N}(v)$ is the neighbors’
check nodes of the variable node $v$. For $t=0$, the initial message is zero,
i.e. $\mu_{v,c}(0)=0$. The message from check node $c$ to the variable node
$v$ is given by:

$\mu_{c,v}(t)=\max\left(\min_{v^{\prime}\in\mathcal{M}(c)\backslash
v}(|\mu_{v^{\prime},c}(t)|)-\beta,0\right)\cdot\\\
\cdot\prod_{v^{\prime}\in\mathcal{M}(c)\backslash
v}\textrm{sign}(\mu_{v^{\prime},c}(t))$ (3)

where $\mathcal{M}(c)$ is the neighbors’ variable nodes of the check node $c$
and $\beta$ are the correlation offset. Note that the message in Eq.3 is an
approximation of the optimal message, with reduced complexity. Lugosch et al.
[23] proposed to replace Eq.3 of the offset min-sum BP decoder with:

$\mu_{c,v}(t)=\max\left(\min_{v^{\prime}\in\mathcal{M}(c)\backslash
v}(|\mu_{v^{\prime},c}(t)|)-\beta_{c,v}(t),0\right)\cdot\\\
\cdot\prod_{v^{\prime}\in\mathcal{M}(c)\backslash
v}\textrm{sign}(\mu_{v^{\prime},c}(t))$ (4)

where $\beta_{c,v}(t)$ are learnable parameters for each edge from check node
$c$ to variable node $v$. After $t$ iterations, the soft output vector
$s_{v}(t)$ is given by:

$s_{v}(t)=l_{v}+\sum_{c^{\prime}\in\mathcal{N}(v)}\mu_{c^{\prime},v}(t)$ (5)

The output bits at the final iteration $T$ can be extracted with a hard
slicer:

$\hat{x}_{v}(t)=\begin{cases}1,&\text{if }s_{v}(t)>0\\\
0,&\text{otherwise.}\end{cases}$ (6)

The neural min-sum decoder uses a stochastic gradient descent in order to find
$\beta_{c,v}(t)$ parameters that improve the performance of the offset min-sum
BP decoder. The loss function is cross-entropy:

$\mathcal{L}_{ce}=-\frac{1}{n}\sum_{v}B_{v}\textrm{log}(\sigma(s_{v}))+(1-B_{v})\textrm{log}(1-\sigma(s_{v}))$
(7)

where $\sigma$ is the sigmoid activation function, and $B_{v}=(1-X_{v})/2$ is
the bit corresponding to transmitted symbol $X_{v}$.

##  III Method

We suggest adding sparse node activation loss and knowledge distillation loss
to the training procedure of the neural min-sum decoder [23]. The sparse node
activation loss is obtained by adding an $L_{p}$ norm on the check and
variable nodes. Furthermore, the knowledge distillation loss imposes an
additional constraint on the check nodes. We suggest using the knowledge
distillation method by incorporating a teacher decoder into the training
procedure. We recommend using the following component: (i) A teacher decoder
and (ii) A student neural decoder. At test time, decoding is performed using
the student neural decoder.

Figure 1: Our method. The Tanner graph for a linear block code with $n=5$. The
teacher decoder has $T_{teacher}=4$ iterations whereas the student neural
decoder has $T_{student}=2$ iterations. The look ahead parameter was set to
$t_{o}=2$.

###  III-A The Architecture

Our proposed method uses a min-sum decoder as a teacher (i.e. without any
training), and a neural min-sum decoder as a student decoder. The specific
implementation of the student neural network is based on the neural min-sum
decoder [23]. It should be noted that one can also use different Neural Belief
propagation decoders like the neural Sum-Product [12] as the neural decoder. A
diagram of the proposed method is shown in Fig. 1. Denote by $T_{teacher}$ and
$T_{student}$ the number of iterations in the teacher and student decoders
respectively. Since the teacher decoder should have better bit-error-rate
results than the student neural decoder, we set $T_{teacher}>T_{student}$.

###  III-B The Knowledge Distillation Loss Term

We propose to constrain the nodes of the neural decoder using the knowledge
distillation method. The knowledge distillation method uses an expert teacher
network (vanilla min-sum decoder, i.e. without learnable parameters) and a
novel loss term that imitates the teacher’s node activations. Since the
teacher network has more layers, imitating the teacher’s node activations,
will result in lower decoding error. Therefore, we propose a new loss function
to guide the training of the neural decoders. Denote by
$\mu_{c,v}^{teacher}(t)$ and $\mu_{c,v}^{student}(t)$ the teacher and student
check node messages at iteration $t$, respectively. The knowledge distillation
training tried to transfer knowledge from the teacher network into the student
network. In other words, the student network messages $\mu_{c,v}^{student}(t)$
at iteration $t$ tried to mimic the teacher network messages
$\mu_{c,v}^{teacher}(t+t_{o})$ at iteration $t+t_{o}$. Where $t_{o}$ is a look
ahead parameter, and it controls the expert level of the teacher network. At
training, the knowledge distillation method will generate a vector of LLR
values with the same encoded bits vector for the teacher and the student
networks, and apply the following loss function:

$\mathcal{L}_{kd}(t)=\sum_{v=1}^{n}\sum_{c^{\prime}\in\mathcal{N}(v)}\left\|\sigma(\mu_{c^{\prime},v}^{teacher}(t+t_{o}))-\sigma(\mu_{c^{\prime},v}^{student}(t))\right\|_{p}^{p}$
(8)

where $p$ is the norm order and $\sigma$ is the sigmoid activation function.
We apply the sigmoid function $\sigma$ in order to bound the messages
$\mu_{c,v}^{student}(t)$ to range $[0,1]$. The overall distillation loss
function $\mathcal{L}_{kd}$ is given by the summing over $T_{student}$
iterations:

$\mathcal{L}_{kd}=\sum_{t=1}^{T_{student}}\mathcal{L}_{d}(t)$ (9)

###  III-C The Sparse Node Activation Loss Term

Sparse parity check matrix leads to higher decoding performance [20].
Therefore, we suggest a neural network decoder with sparse node activations.
The suggested neural sparse decoder functions as a neural decoder with a
sparse parity check matrix. Sparse node activations can be achieved with a
sparse loss term. The proposed sparse loss term is obtained by using a $L_{p}$
norm on variable and check nodes over the student network:

$\mathcal{L}_{s}(t)=\sum_{v=1}^{n}\sum_{c^{\prime}\in\mathcal{N}(v)}\left\|\sigma(\mu_{c^{\prime},v}^{student}(t))\right\|_{p}^{p}+\\\
+\sum_{c=1}^{n-k}\sum_{v^{\prime}\in\mathcal{M}(c)}\left\|\sigma(\mu_{v^{\prime},c}^{student}(t))\right\|_{p}^{p}$
(10)

where we use the same $p$ value as in the knowledge distillation loss terms.
We observe that the $p$ parameter is important for successful training since
larger $p$ increases the gradient. We ran experiments to check the best $p$
value for training; further explanation will be given in the results section.
Furthermore, we apply the sigmoid $\sigma$ function over the variables and
check nodes in order to squeeze the range to $[0,1]$. Summing the sparse loss
term at each iteration $t$, we obtain the overall sparse loss term:

$\mathcal{L}_{s}=\sum_{t=1}^{T_{student}}\mathcal{L}_{s}(t)$ (11)

###  III-D The Combined Loss Term

The overall loss is a linear combination of the cross entropy loss Eq.7, the
knowledge distillation loss Eq.9 and the sparse node activation loss Eq.11
$\mathcal{L}=\mathcal{L}_{ce}+\alpha\mathcal{L}_{kd}+\gamma\mathcal{L}_{s}$
where we set $\alpha=1$ and $\gamma=0.01$.

###  III-E Complexity Analysis

The inference complexity is similar to the neural min-sum decoder. Both have
the same number of layer and the same number of non-zero weights in the Tanner
graph.

|
---|---
(a) | (b)
|
(c) | (d)
Figure 2: BER for various values of SNR for BCH codes. (a) BCH (63,45) with a
right-regular parity check matrix, (b) BCH (63,45) trained with a cycle
reduced parity check matrix, (c) BCH (63,45) with a right-regular parity check
matrix trained with different $p$ values. (d) BCH (63,45) with a right-regular
parity check matrix, BER curve during training sparse node activation loss.
Figure 3: BER for various values of SNR for BCH (63,36) & BCH (127,99) codes
trained with a cycle reduced parity check matrix. The number of iterations set
to $T=5$ in all decoders.

##  IV Results

The proposed architecture trained on Bose–Chaudhuri–Hocquenghem (BCH) codes
[25]. The parity check matrices and the generator matrices are taken from [26]
except for the cycle reduced parity check matrices that are based on [27]. For
the training and test set, we randomly generated codewords that transmitted
over an additive white Gaussian noise (AWGN) channel. Each batch contained
$360$ examples. Furthermore, the batch contained codewords with SNR values of
$1dB,...,8dB$ with $45$ examples per SNR value. Moreover, the loss function is
the mean value of the combined loss $\mathcal{L}$ for each example in the
batch. The teacher network had $T_{teacher}=30$ layers while the student
network trained with $T_{student}=5$ iterations, the look-ahead parameter is
$t_{o}=25$. The norm order $p$ was set to $12$. The learning rate was set to
$0.01$. We ran the Monte-Carlo simulation and obtained the Bit-Error-Rate
(BER) for SNR values from $1dB$ to $10dB$.

In Fig.2(a) we provide the BER figures for BCH (63,45) code with a right-
regular parity check matrix. As can be seen, our proposed decoder improves the
Min-Sum Belief Propagation decoder by up to $1.5dB$ for large SNR values
($6-10dB$), and $1dB$ for medium and small SNR values ($1-5dB$). Moreover, our
proposed decoder improves the Neural Belief Propagation (NBP) [23] decoder by
$1.1dB$ for larger SNR values ($8-10dB$), and up to $0.75dB$ improvement for
medium SNR values ($6-7dB$). For smaller SNR values ($1-5dB$) our proposed
method achieves the same decoding results as the Neural Belief Propagation
(NBP) decoder. It should be noted that our method has the same run-time
complexity and model size as the Neural Belief Propagation (NBP) decoder.
Fig.2(b) provides the BER figures for BCH (63,45) code with a cycle reduced
parity check matrix. As can be seen, our proposed method improves the Min-Sum
Belief Propagation decoder by up to $0.75dB$ for large SNR values. Moreover,
the proposed method improved the Neural Belief Propagation (NBP) [23] decoder
by $0.6dB$ for larger SNR values. We also compared our method to the Deep
Active Learning Decoder [28], and found that it improves by the large gap
$1.8dB$ the Deep Active Learning Decoder. Moreover, the Deep Active Learning
Decoder is based on the Sum-Product decoder which has better results than the
Min-Sum decoder which is the underline decoder for our method. For the low SNR
regime, the Deep Active Learning Decoder achieves better BER with an
improvement of up to $0.3dB$. However, it comes with a cost of error-floor at
the high SNR regime. It is left for future research to combine the active
learning decoder with our method for better BER in the low SNR regime. In
Fig.3 we provide the BER for BCH (63,36) code with a cycle reduced parity
check matrix. We can observe a large improvement of up to $1.1dB$ for large
SNR values when compared to the Min-Sum Belief Propagation decoder. When
compared to the Neural Belief Propagation (NBP) [23] decoder, our proposed
method improves the results by $0.7dB$ for larger SNR values. For small SNR
values, our proposed method has a small degradation ($0.2dB$) in the
performance when compared to the Neural Belief Propagation (NBP) decoder. The
source of the degradation is the knowledge distillation loss term which gets
worse results in the low SNR regime (see the ablation section for more
details). Possible sources for the degradation can be explained by the fact
that the knowledge distillation loss term does not use the ground truth bits
at training, while the Neural Belief Propagation (NBP) decoder uses this
additional information. Fig.3 presents the BER for larger BCH code (127,99)
with a cycle reduced parity check matrix. As can be observed from the figure,
our method improves the Min-Sum Belief Propagation decoder by $1.4dB$ for high
SNR values. Furthermore, it improves the performance of the Neural Belief
Propagation (NBP) by up to $1.0dB$ in the high SNR regime.

Ablation Analysis  In Fig.2(a) we evaluate the contribution of different
components of our method with an ablation analysis for the BCH(63,45) code. We
compared our method with (i) a neural decoder that trains only with the
knowledge distillation loss (cyan curve), (ii) a neural decoder that trains
with the sparse node activation loss (red curve), and (iii) the teacher min-
sum decoder with $T=30$ iterations (green curve). As we can observe, our
method (magenta curve) achieves the best results which demonstrates the
advantage of our complete method. Furthermore, we can observe that without the
sparse node activation loss (i) and without the knowledge distillation loss
(ii) we have a degradation of $0.5dB$ and $0.3dB$ respectively. This shows
that the sparse node activation loss gives more improvement than that
knowledge distillation loss. The teacher min-sum decoder (iii) can be regarded
as lower bound to (i). We can observe that training only with the knowledge
distillation loss (i) leads to degradation in the low SNR regime ($3-6dB$).
The degradation is alleviated when training with the cross-entropy loss.

Training With Different $L_{p}$ Norms  Fig.2(c) provides the BER curve for
different $L_{p}$ norms. We use the BCH (63,45) code with a right-regular
parity check matrix, and test it for $p=2,4,6,8,10,12,14,16$. As we can
observe the curve congregates for $p$ value that is greater than $12$.
Therefore, we choose to use $p=12$ in our simulations. Furthermore, we observe
that $p=12$ leads to sparse activations without zeroing the whole activations.

Training The Sparse Node Activation Loss  Fig.2(d) provides the BER curve
during training with the sparse node activation only (i.e. without the cross-
entropy loss and the knowledge distillation loss). We use the BCH (63,45) code
with a right-regular parity check matrix, and we plot the BER curve after each
epoch. As we can observe, after two epochs the training improves the BER curve
drastically at a high SNR regime. However, for a low SNR regime, it gives high
degradation in the BER performance. We can also observe that after three
epochs, the training explodes and the BER curve has a worse performance
compared to the previous epochs. Moreover, after four epochs, the BER curve
has an inferior performance compare to all previous epochs. The phenomena of
training exploding is reasonable since the neural decoder is trained to output
zero activation at the variable and check nodes which gives the wrong
estimation to the transmitted codeword. However, we can observe that during
training the sparse node activation loss leads to high improvement of BER in a
high SNR regime.

##  V Conclusion

We propose new learning loss terms for neural belief propagation decoding. The
new learning loss terms use sparse constraints on the variable and check
nodes, furthermore, it uses a teacher network to guide the training of the
neural network. The proposed method shows improvement of up to $1.1dB$ in the
high SNR regime. Moreover, the method has the same run-time complexity and the
same model size as the baseline methods. The sparse constraint on neural
decoders is an interesting research direction and it is left for future work
to discover whether other sparse constraints (for example - weights) can
improve the performance of the neural decoder. The usage of Teacher-Student
learning for Neural Belief Propagation can also be beneficial for other
applications, such as online learning (when the ground truth is unknown). For
example, it would be interesting to see the improvement when the student
network is trained with changing real-world data. Furthermore, it also left
for future research to apply the proposed method to the neural Polar factor
graph decoder [29].

## Acknowledgments

We thank Uriel Singer and Monica Broido for the helpful discussion. The
contribution of Eliya Nachmani is part of a Ph.D. thesis research conducted at
Tel Aviv University.

## References

  * [1] N. Samuel, T. Diskin, and A. Wiesel, “Learning to detect,” _IEEE Transactions on Signal Processing_ , 2019.
  * [2] N. Shlezinger, R. Fu, and Y. C. Eldar, “Deep soft interference cancellation for mimo detection,” in _ICASSP 2020 IEEE International Conference on Acoustics, Speech and Signal Processing_.
  * [3] S. Ramjee, S. Ju, D. Yang, X. Liu, A. E. Gamal, and Y. C. Eldar, “Fast deep learning for automatic modulation classification,” _arXiv preprint arXiv:1901.05850_ , 2019.
  * [4] K. M. Cohen, S. Park, O. Simeone, and S. Shamai, “Learning to learn to demodulate with uncertainty quantification via bayesian meta-learning,” _arXiv preprint arXiv:2108.00785_ , 2021.
  * [5] S. Ramjee, S. Ju, D. Yang, X. Liu, A. E. Gamal, and Y. C. Eldar, “Ensemble wrapper subsampling for deep modulation classification,” _arXiv preprint arXiv:2005.04586_ , 2020.
  * [6] A. Caciularu and D. Burshtein, “Unsupervised linear and nonlinear channel equalization and decoding using variational autoencoders,” _IEEE Transactions on Cognitive Communications and Networking_ , 2020.
  * [7] N. Weinberger, “Generalization bounds and algorithms for learning to communicate over additive noise channels,” _IEEE Transactions on Information Theory_ , 2021.
  * [8] H. Kim, Y. Jiang, S. Kannan, S. Oh, and P. Viswanath, “Deepcode:feedback codes via deep learning,” in _Advances in Neural Information Processing Systems_ , 2018.
  * [9] S. Ginzach, N. Merhav, and I. Sason, “Random-coding error exponent of variable-length codes with a single-bit noiseless feedback,” in _IEEE Information Theory Workshop_ , 2017.
  * [10] A. Ben-Yishai and O. Shayevitz, “The gaussian channel with noisy feedback:improving reliability via interaction,” in _International Symposium on Information Theory_. IEEE, 2015.
  * [11] S. Shayovitz and M. Feder, “Universal active learning via conditional mutual information minimization,” _Journal on Selected Areas in Information Theory_ , 2021.
  * [12] E. Nachmani, Y. Be’ery, and D. Burshtein, “Learning to decode linear codes using deep learning,” in _54th Annual Allerton Conference on Communication, Control, and Computing_. IEEE, 2016.
  * [13] B. Vasić, X. Xiao, and S. Lin, “Learning to decode ldpc codes with finite-alphabet message passing,” in _2018 Information Theory and Applications Workshop_.
  * [14] E. Nachmani and L. Wolf, “Hyper-graph-network decoders for block codes,” in _Advances in Neural Information Processing Systems_ , 2019.
  * [15] Y. Choukroun and L. Wolf, “Error correction code transformer,” _arXiv preprint arXiv:2203.14966_ , 2022.
  * [16] X. Chen and M. Ye, “Cyclically equivariant neural decoders for cyclic codes,” _International Conference on Machine Learning_ , 2021.
  * [17] L. Lugosch and W. J. Gross, “Learning from the syndrome,” in _52nd Asilomar Conference on Signals, Systems, and Computers_ , 2018.
  * [18] A. Buchberger, C. Häger, H. D. Pfister, L. Schmalen, and A. G. Amat, “Pruning neural belief propagation decoders,” in _IEEE International Symposium on Information Theory_ , 2020.
  * [19] R. Gallager, “Low-density parity-check codes,” _IRE Transactions on information theory_ , vol. 8, no. 1, pp. 21–28, 1962.
  * [20] D. J. MacKay, “Good error-correcting codes based on very sparse matrices,” _IEEE transactions on Information Theory_ , 1999.
  * [21] M. Kurtz, J. Kopinsky _et al._ , “Inducing and exploiting activation sparsity for fast neural network inference,” in _37th International Conference on Machine Learning_ , 2020.
  * [22] G. Hinton, O. Vinyals, J. Dean _et al._ , “Distilling the knowledge in a neural network,” _arXiv preprint arXiv:1503.02531_ , vol. 2, no. 7, 2015\.
  * [23] L. Lugosch and W. J. Gross, “Neural offset min-sum decoding,” in _IEEE International Symposium on Information Theory_ , 2017.
  * [24] J. Chen, A. Dholakia, E. Eleftheriou, M. P. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of ldpc codes,” _IEEE transactions on communications_ , 2005.
  * [25] R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes,” _Information and control_ , 1960.
  * [26] M. Helmling, S. Scholl, F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and N. Wehn, “Database of Channel Codes and ML Simulation Results,” www.uni-kl.de/channel-codes, 2019.
  * [27] T. R. Halford and K. M. Chugg, “Random redundant soft-in soft-out decoding of linear block codes,” in _International Symposium on Information Theory_. IEEE, 2006.
  * [28] I. Be’ery, N. Raviv, T. Raviv, and Y. Be’ery, “Active deep decoding of linear codes,” _IEEE Transactions on Communications_ , 2019.
  * [29] W. Xu, Z. Wu _et al._ , “Improved polar decoder based on deep learning,” in _International workshop on signal processing systems_. IEEE, 2017.


# Understanding Consumer Preferences for Movie Trailers from EEG using Machine
Learning

Pankaj Pandey  Computer Science and Engineering
Indian Institute of Technology Gandhinagar
Gujarat, India
<EMAIL_ADDRESS>Raunak Swarnkar  Centre for Cognitive & Brain Sciences
Indian Institute of Technology Gandhinagar
Gujarat, India
<EMAIL_ADDRESS>Shobhit Kakaria  Centre for Cognitive and Brain
Sciences
Indian Institute of Technology Gandhinagar
Gujarat, India
<EMAIL_ADDRESS>Krishna Prasad Miyapuram  Centre for Cognitive
and Brain Sciences
Computer Science and Engineering
Indian Institute of Technology Gandhinagar
Gujarat, India
<EMAIL_ADDRESS>
###### Abstract

Neuromarketing aims to understand consumer behavior using neuroscience. Brain
imaging tools such as EEG have been used to better understand consumer
behavior that goes beyond self-report measures which can be a more accurate
measure to understand how and why consumers prefer choosing one product over
another. Previous studies have shown that consumer preferences can be
effectively predicted by understanding changes in evoked responses as captured
by EEG. However, understanding ordered preference of choices was not studied
earlier. In this study, we try to decipher the evoked responses using EEG
while participants were presented with naturalistic stimuli i.e. movie
trailers. Using Machine Learning techniques to mine the patterns in EEG
signals, we predicted the movie rating with more than above-chance, 72%
accuracy. Our research shows that neural correlates can be an effective
predictor of consumer choices and can significantly enhance our understanding
of consumer behavior.

###### Index Terms:

Neuromarketing, EEG, Machine Learning, Discrete Wavelet Decomposition

## Introduction

Consumer neuroscience systematically aims to understand consumer behavior and
underlying preferences through the lens of psychology, neuroscience, marketing
and economics [1]. Currently, consumer research relies on the stimulus-reponse
model to capture the underlying brain processes. The development of human
neuroscience tools to understand the latent mechanisms gave rise to progress
of using neuroscience to effectively understand what the consumer prefers
going beyond the traditional subjective scores[2, 3]. Understanding what
contributes to the observed behavior by complex, naturalistic stimuli has
immense importance in marketing research [4, 5, 6]. Preferences of consumers
have been widely studied using other modes than self-reported measures. The
idea of ’preference’ has been historically approached differently in
psychology, economics, marketing and neuroscience. One neuroscience study has
shown that behavior preferences can be attributed to brain activity in the
ventromedial prefronal (vmPFC) cortex and ventral striatum [7].

Electroencephalography (EEG) is being recently used as a tool to understand
the neural correlates of consumer behavior due to its advantage of providing
temporal resolution of stimulus-response . Previous research suggests using
EEG to understand the patterns of brain activity of participants watching
advertisements to understand their buying preferences [8]. The main motivation
behind this current study is to understand consumer neuroeconomics from a
machine learning perspective, primarily to understand movie preferences, which
is a line of research that has not received much attention. For instance, the
US movie box office revenue is above $10 Billion per year. However, invest-
ing in such projects is risky. It has been found that only 36% of movies
achieve a break-even over the production cost, in terms of profits. Movie
producers spend huge amounts on movie trailers and use different marketing
techniques to gauge consumer reactions, and eventually, box-office earnings.
Study used EEG for predicting brain responses to movie trailers based on
individual consumer preferences, where brainwave signals in the beta frequency
oscillation range were found to be a good predictor for like/dislike of a
movie trailer [9]. In another work, EEG was used to study consumer behavior
where it was found that future choices in terms of which product a consumer
will prefer buying, was predicted using EEG [10].

In this study, we study consumer behavior in terms of movie trailer
preferences using both neural and behavioral measures, with the main aim to
use pattern recognition techniques to understand evoked responses in EEG. The
present study tries to systematically investigate whether neural correlates
can be a valuable predictor of individual choice preferences.

## Materials and Methods

###  -A Experiment Design

The dataset was collected using a 128 channel Net Station
Electroencephalography (EEG) device from 18 healthy individuals (13 were men,
and 5 were women) at Indian Institute of Technology, Gandhinagar. The mean age
of participants was 22.4 years within the range of 18-26 years. No participant
reported any history of neurological or psychiatric disorder. Fifteen
participants were right-handed, and three were left-handed. Data acquisition
was done using EGI Netstation 5.2. The experiment consisted of 12 trial
blocks. In the experiment, every subject was asked to watch 12 trailers of
upcoming movies, and after each trailer, there were four questions to be
answered on a likert scale of 1-5:

  1. 1.

Rating

  2. 2.

Familiarity

  3. 3.

Purchase Intent

  4. 4.

Willigness to Spend

Lastly, participants were asked to report an ordered pref- erence to arrange
the movies in descending order, the movie trailers they liked the most to
least preferred. Experiment Design is shown in fig. 1.

Figure 1: Experiment design

This step consisted of removal of data points in the dataset that were
erroneous. Those samples where the electrodes were not in proper location, or
not in contact with the scalp, were excluded from the dataset before further
processing. EEG signal is susceptible to noise or artefacts and has to be
corrected as part of the signal pre-processing step as mentioned in the below.
All the pre-processing was performed using EEGLab Package in MATLAB [11].
Further, bad channels were rejected using Artifact Subspace Reconstruction
using Makato’s Pre-processing pipeline [12]. Re-referencing was performed
across all channels. The following artefacts were identified and removed.

####  -A1 Physiological Artefacts

Electrooculogram (EOG): This is the electrical noise gener- ated by eye blink
and cornea movement that is captured in the EEG signal and has to be removed.
It can be estimated as the change of potential in electrodes near the eyes at
Fp1- Fp2 (Fronto Parietal). Fluttering of the eyelids appears as a 3Hz –10Hz
signal, and hence was removed using Band Pass filters.

Electromyogram (EMG): This is the electrical “noise” gener- ated by muscle
activity. Facial Muscle movement; swallowing, grimacing, chewing can be
captured in EEG and has to be removed. This noise commonly appears in the
frontal and temporal electrodes.

####  -A2 External Artefacts

Physical movement: This can lead to lose contact of electrode due to abrupt
physical movement of subjects and is captured as a high amplitude, low
frequency noise. Electrode Contact: Poor electrode contact gives rise to low
frequency artifacts and all such trials were removed which had lost any
electrode contacts.

###  -B Feature Extraction

In order to extract features from EEG signals, a well- established method is
to decompose the mother wavelet into sub-frequency bands. There are primarily
5 types of frequency bands as shown in table I.

TABLE I: Frequency Bands Frequency Band | Frequency Range(Hz)
---|---
Delta | 0-3.5
Theta | 4-7
Alpha | 8-13
Beta | 14-30
Gamma | 30-60

A general method for decomposition is to use Fast Fourier Transform. But since
EEG electrode signal is non-stationary, FFT might not be the best alternative
[13, 14, 15]. Instead, we used Discrete Wavelet Transform (DWT) Method (db-8
wavelet) using Mat- lab Wavelet Toolbox to extract two features, Power and En-
tropy for all 5 frequency sub-bands in range of 0-60 Hz, across all 128
channels.

###  -C Feature Elimination

Since the feature set had a large number of features consisting of 5 DWT
features for both Power and Entropy, two feature elimination techniques were
used:

  1. 1.

Recusrive Feature Elimination: This algorithm ranks the features by
associating the weights with features and prune the features as per the
weights. It forms the smaller set after each iteration and terminate until the
given (k) number of features is achieved.

  2. 2.

Sequential Backward Selection (SBS): A greedy search technique to reduce
dimensions of the feature vector from a d space to lower dimensional k space.

These two methods were used to select features which were further trained with
the set of classifiers.

###  -D Machine Learning Classifiers

Choosing the correct set of Machine Learning models is a crucial step for
classification. 9 Machine Learning classifiers were used to predict the
labelled class using the extracted feature set, which includes: k Nearest
Neighbors, Random Forest, Quadratic Discriminant Analysis, Decision Tree,
Multilayer Perceptron, Gaussian Naive Bayes, Gaussian Process Classifier,
Ridge Classifier, Support Vector Classifier. Every classifier was trained with
a Cross-Validation set and test for performance using the test set. The hyper-
parameters of the classifiers were tuned iteratively. We trained the models
using python. [16, 17].

###  -E Results

The total sample size of 216 data points was divided into train set with 151
and test set with 65 samples. All the 4 bands were found to have
discriminating information for the classifier. Machine learning classifiers
were then used to train and were tested accordingly, with the top 5
classifiers using 10 Fold Cross-Validation with their results as shown in
table II

TABLE II: Classification Performance Classifier | Feature Elimination | Test Accuracy
---|---|---
kNN | RFE | 0.7237
Random Forest | SBS | 0.7069
kNN | SBS | 0.6923
Multi-layer Perceptron | SBS | 0.6769

##  I Discussion

The use of EEG in Neuromarketing to understand consumer behavior is an
important area of research given its wide implications. Machine learning
techniques have aided immensely in this regard, to decode the information in
EEG signals. In this study, we attempted to find whether consumer preferences
can be predicted using EEG signals and achieved high accuracy to predict
ratings. The main aim to predict ordered preference of movie trailer still
needs to be studied, which is the primary goal of this study. However, using
EEG for consumer research has its own challenges. EEG signals have a low
Signal-to-Noise ratio and hence, it becomes a challenge to accurately process
the signal. Sensitivity to various artefacts also poses problems in the data
cleaning process. Better signal processing techniques could further improve
the Signal-to-Noise ratio and could improve classification performance which
needs to be explored. However, the most significant challenge faced was the
small n-large-p problem i.e. large number of features as compared to number of
samples. One limitation of our work is that we had averaged the feature values
across channels, which may have led to loss of information. One way to resolve
this would be to use dimensionality reduction techniques. We made a
preliminary attempt to use PCA but did not get any significant improvements.
Using non-linear dimensionality reduction techniques such as t-SNE and UMAP
which are considered to be the state-of-the-art techniques need to be further
explored. Deep Learning techniques have been found to be quite powerful when
learning internal representations of features, which could be significant as a
dimensionality reduction step, which can be further explored.

## References

  * [1] D. Ariely and G. S. Berns, “Neuromarketing: the hope and hype of neuroimaging in business,” _Nature reviews neuroscience_ , vol. 11, no. 4, pp. 284–292, 2010.
  * [2] M. Hsu and C. Yoon, “The neuroscience of consumer choice,” _Current opinion in behavioral sciences_ , vol. 5, pp. 116–121, 2015.
  * [3] R. B. Silberstein and G. E. Nield, “Brain activity correlates of consumer brand choice shift associated with television advertising,” _International Journal of Advertising_ , vol. 27, no. 3, pp. 359–380, 2008\.
  * [4] M. Hubert and P. Kenning, “A current overview of consumer neuroscience,” _Journal of Consumer Behaviour: An International Research Review_ , vol. 7, no. 4-5, pp. 272–292, 2008.
  * [5] J. P. Dmochowski, M. A. Bezdek, B. P. Abelson, J. S. Johnson, E. H. Schumacher, and L. C. Parra, “Audience preferences are predicted by temporal reliability of neural processing,” _Nature communications_ , vol. 5, no. 1, pp. 1–9, 2014.
  * [6] H. Plassmann, T. Ambler, S. Braeutigam, and P. Kenning, “What can advertisers learn from neuroscience?” _International Journal of Advertising_ , vol. 26, no. 2, pp. 151–175, 2007.
  * [7] S. M. McClure, J. Li, D. Tomlin, K. S. Cypert, L. M. Montague, and P. R. Montague, “Neural correlates of behavioral preference for culturally familiar drinks,” _Neuron_ , vol. 44, no. 2, pp. 379–387, 2004.
  * [8] Y. J. Wang and M. S. Minor, “Validity, reliability, and applicability of psychophysiological techniques in marketing research,” _Psychology & Marketing_, vol. 25, no. 2, pp. 197–232, 2008.
  * [9] M. A. Boksem and A. Smidts, “Brain responses to movie trailers predict individual preferences for movies and their population-wide commercial success,” _Journal of Marketing Research_ , vol. 52, no. 4, pp. 482–492, 2015.
  * [10] D. Kang, J. Kim, D.-P. Jang, Y. S. Cho, and S.-P. Kim, “Investigation of engagement of viewers in movie trailers using electroencephalography,” _Brain-Computer Interfaces_ , vol. 2, no. 4, pp. 193–201, 2015.
  * [11] A. Delorme and S. Makeig, “Eeglab: an open source toolbox for analysis of single-trial eeg dynamics including independent component analysis,” _Journal of neuroscience methods_ , vol. 134, no. 1, pp. 9–21, 2004.
  * [12] Makoto. Makoto’s preprocessing pipeline. [Online]. Available: https://sccn.ucsd.edu/wiki/Makoto’s\\_preprocessi\\\ng\\_pipeline
  * [13] J. Gross, “Analytical methods and experimental approaches for electrophysiological studies of brain oscillations,” _Journal of neuroscience methods_ , vol. 228, pp. 57–66, 2014.
  * [14] M. R. Azim, M. S. Amin, S. A. Haque, M. N. Ambia, and M. A. Shoeb, “Feature extraction of human sleep eeg signals using wavelet transform and fourier transform,” in _2010 2nd International Conference on Signal Processing Systems_ , vol. 3. IEEE, 2010, pp. V3–701.
  * [15] A. Hamad, E. H. Houssein, A. E. Hassanien, and A. A. Fahmy, “Feature extraction of epilepsy eeg using discrete wavelet transform,” in _2016 12th international computer engineering conference (ICENCO)_. IEEE, 2016, pp. 190–195.
  * [16] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg _et al._ , “Scikit-learn: Machine learning in python,” _the Journal of machine Learning research_ , vol. 12, pp. 2825–2830, 2011.
  * [17] S. Raschka, “Mlxtend: Providing machine learning and data science utilities and extensions to python’s scientific computing stack,” _The Journal of Open Source Software_ , vol. 3, no. 24, Apr. 2018. [Online]. Available: http://joss.theoj.org/papers/10.21105/joss.00638


Verilog ‘’“‘$ vlogconstantstyle vlogdefinestyle vlogsystemstyle

#  PSOFuzz: Fuzzing Processors with
Particle Swarm Optimization

Chen Chen∗,†, Vasudev Gohil∗,†, Rahul Kande†, Ahmad-Reza Sadeghi‡, and
Jeyavijayan (JV) Rajendran†
†Texas A&M University, USA, ‡Technische Universität Darmstadt, Germany
†{chenc, gohil.vasudev, rahulkande<EMAIL_ADDRESS>
<EMAIL_ADDRESS>∗These authors contributed equally to
this work.

###### Abstract

Hardware security vulnerabilities in computing systems compromise the security
defenses of not only the hardware but also the software running on it. Recent
research has shown that hardware fuzzing is a promising technique to
efficiently detect such vulnerabilities in large-scale designs such as modern
processors. However, the current fuzzing techniques do not adjust their
strategies dynamically toward faster and higher design space exploration,
resulting in slow vulnerability detection, evident through their low design
coverage.

To address this problem, we propose PSOFuzz, which uses particle swarm
optimization (PSO) to schedule the mutation operators and to generate initial
input programs dynamically with the objective of detecting vulnerabilities
quickly. Unlike traditional PSO, which finds a single optimal solution, we use
a modified PSO that dynamically computes the optimal solution for selecting
mutation operators required to explore new design regions in hardware. We also
address the challenge of inefficient initial seed generation by employing PSO-
based seed generation. Including these optimizations, our final formulation
outperforms fuzzers without PSO. Experiments show that PSOFuzz achieves up to
$\mathbf{15.25\times}$ speedup for vulnerability detection and up to
$\mathbf{2.22\times}$ speedup for coverage compared to the state-of-the-art
simulation-based hardware fuzzer.

###### Index Terms:

Hardware Security, Security Vulnerabilities, Fuzzing, Particle Swarm
Optimization

##  I Introduction

Hardware designs are becoming increasingly complex to meet the rising need for
custom hardware and increased performance. However, as the design complexity
grows, verification dominates the development lifecycle—over 70% of resources
are spent to verify the security of a hardware design [1]. Therefore, a
verification technique that can expose design flaws/vulnerabilities as early
as possible is critical [2, 3, 4, 5].

Recent research has shown that coverage feedback-based fuzzers can effectively
detect security vulnerabilities in modern processors and achieve coverage
faster than traditional hardware verification techniques such as random
regression[6, 7, 8, 9, 10, 11, 12, 13]. Fuzzers start with seed inputs and
apply predefined mutation operators on current inputs to generate new inputs.
Fuzzers utilize one or several coverage metrics to track the activity caused
by the inputs in the hardware and guide themselves to generate inputs that
explore new hardware regions, thereby accelerating vulnerability detection.
These fuzzers successfully found vulnerabilities that execute undefined
behaviors, compromise memory isolation, lead to privilege escalations, etc.,
in hardware designs. Due to their promising potential, semiconductor giants
such as Intel and Google are actively developing new and efficient hardware
fuzzers for vulnerability detection [14, 10].

Though hardware fuzzing is promising, its coverage increment usually stagnates
quickly, leaving design spaces unexplored and vulnerabilities undetected. One
of the main reasons is that all the existing hardware fuzzers schedule the
mutation operators and generate seeds using static schemes, and lack feedback-
guided dynamic updates via interaction with the coverage achieved and the
complexity of the hardware (more details in Sec. V) [6, 9, 11, 10, 12, 8, 7,
13]. For example, [9] generates input instructions with the same operands to
verify the renaming strategies in out-of-order processors. However, this
strategy is not optimal for processors without renaming strategies. While [11]
uses profiling to analyze the correlation between the mutation operators and
the processor instructions, the scheduling is static throughout fuzzing and
does not update with coverage achieved. Therefore, to dynamically adjust the
schedule of mutation operators and seed generation, we develop an approach to
equip any hardware fuzzer with particle swarm optimization (PSO) targeting
faster vulnerability detection and coverage achievement.

PSO is a bio-inspired algorithm that uses a swarm consisting of multiple
particles to find the optimal solution in a high-dimensional space [15]. Since
fuzzers usually run multiple threads in parallel to accelerate the design
space exploration, we model the scheduler of each thread’s mutation operations
as a particle. The probability distribution of each mutation operator being
selected composes the position of a particle. Each particle updates its
position based on the highest coverage achieved by itself and the highest
coverage achieved by the swarm in the current iteration.

Researchers have used PSO in software fuzzing to find the optimal probability
distribution of mutation operators [16]. Results show a significant
improvement over the fuzzers without PSO. However, one cannot simply use their
technique for hardware fuzzing for the following reasons: (i) They assume a
static optimal probability distribution of the mutation operators, which is
not true for hardware fuzzing. Our experiments show that if a static
distribution is used, two critical vulnerabilities are not detected even after
using PSO (more details in Sec. III-B and IV). (ii) They use randomly
generated programs as seeds, which is not ideal for hardware fuzzing (more
details in Sec. III-C). To successfully apply PSO to hardware fuzzing, we must
address two critical challenges:

  * •

Challenge 1: Saturation of Particles’ Performance. Naively applying PSO to
hardware fuzzing results in the particles converging to a fixed position
leading to a lack of coverage improvement and vulnerabilities undetected.

  * •

Challenge 2: Ineffective Seed Generation. The seeds from which the fuzzing
loop starts strongly affect the coverage achieved. Traditional fuzzers use
either statically or randomly generated seeds, which results in slower
coverage increments. Moreover, the performance of applying PSO to hardware
fuzzing is also subject to the seed: poor quality seeds result in poor
coverage.

We address these challenges by designing specific solutions (in Sec. III-B and
III-C) that result in faster vulnerability detection and coverage achievement.
In particular, we augment PSO with a reset strategy to schedule mutation
operators dynamically. Moreover, we employ PSO to select high-quality seed
inputs resulting in faster coverage. Overall, the main contributions of this
work are as follows:

  1. 1.

To the best of our knowledge, we develop the first technique that uses the PSO
algorithm to schedule the mutation operators and generate seed inputs in
hardware fuzzing.

  2. 2.

We overcome challenges in adapting PSO to hardware fuzzers. In particular, we
develop optimizations to reset the particles for selecting mutation operators
and a novel PSO-based seed generation algorithm for hardware fuzzers.

  3. 3.

We evaluate PSOFuzz on three widely-used open-source RISC-V processors and
achieve up to $15.25$$\times$ speedup in detecting vulnerabilities and up to
$2.22\times$ speedup in achieving coverage compared to the state-of-the-art
simulation-based fuzzer without PSO.

##  II Background

###  II-A Hardware Processor Fuzzers

Hardware processor fuzzers iteratively generate testing inputs (i.e., inputs
or tests) such as binary executables to detect vulnerabilities in target
hardware (i.e., design-under-test (DUT)). These fuzzers mainly consist of a
seed generator, mutation engine, feedback engine, and vulnerability detector
[9, 11, 13, 12]. The seed generator generates an initial set of tests called
seeds. Fuzzer simulates the hardware with these seeds to generate feedback and
output. The feedback engine captures the activity in hardware, such as
toggling of the value of flip-flops [11], as coverage data during simulation.
The mutation engine modifies the tests that achieve new coverage (i.e.,
interesting tests) to create new tests. For example, the Bitflip mutation
operator flips one random bit in the test [17]. The vulnerability detector
detects vulnerabilities in hardware by comparing its output with the output of
a golden-reference model (GRM) [11, 9, 13].

Existing hardware fuzzers use static mutation operator scheduling and seed
generation schemes which cannot dynamically adjust based on the complexity of
hardware and the coverage achieved, slowing down vulnerability detection and
design space exploration (more details in Sec. III and V).

###  II-B PSO Algorithm

PSO is a bio-inspired algorithm that allocates multiple particles to
iteratively search for an optimal solution [15]. The position of a particle is
a candidate solution and is updated based on its velocity. The velocity is
determined by the best position the particle ever achieved and the best
position the entire swarm ever achieved. A particle’s velocity, $v_{i}$, and
position, $p_{i}$, are updated as

$\displaystyle\begin{split}v_{i}(t+1)&=k\times
v_{i}(t)+r_{1}\times(l_{i}^{best}(t)-p_{i}(t))\\\
&+r_{2}\times(g^{best}(t)-p_{i}(t))\end{split}$ (1)
$p_{i}(t+1)=p_{i}(t)+v_{i}(t+1)$ (2)

Here, $l_{i}^{best}(t)$ represents the best position the particle $i$ ever
achieved since the beginning (i.e., $t=0$), and $g^{best}(t)$ represents the
best position ever achieved by any particle in the swarm. $k$ is a pre-defined
constant, and $r_{1}$ and $r_{2}$ are two random displacement weights that
decide how fast the particle $i$ will move toward $l_{i}^{best}(t)$ and
$g^{best}(t)$, respectively.

PSO has been widely applied to optimize the performance of applications due to
its searching efficiency and convergence speed [18]. Though the solutions
found by PSO are heuristic results, they are usually close to the real global
optimum [19]. The software community has also leveraged PSO (e.g., MOpt [16])
to detect vulnerabilities (e.g., memory crashes) in programs. However, for
hardware fuzzing, the optimal probability distribution of the mutation
operators changes with coverage achieved so far, and the quality of seeds
greatly affects the performance of the fuzzer. Hence, MOpt cannot be applied
for hardware fuzzing directly.

##  III PSOFuzz: Fuzzing Processors with PSO

In this section, we first formulate the problem of selecting optimal mutation
operators as a PSO problem. However, the formulation has critical limitations,
such as saturation of particles’ performance and inefficient seed generation.
We analyze these limitations and devise appropriate solutions, resulting in a
final formulation that outperforms fuzzers without PSO.

###  III-A Selecting Mutation Operators Using PSO

Most existing hardware fuzzers select mutation operators uniformly at random,
i.e., they have an equal probability of selecting from all possible mutation
operators [6, 11, 13, 8, 7, 12, 10, 9]. This is not ideal as mutation
operators have varying impacts on covering new points in hardware. The
following example demonstrates this.

Listing 1: Code snippet from CVA6 [20] processor (simplified to improve
readability)

⬇

1unique case (instr.opcoderightbracket

2 ...

3 CSRRS: begin

4 if (instr.rs1 ==  5'b0rightbracket

5 instruction_o.op =  CSR_READ;// c1

6 else

7 instruction_o.op =  CSR_SET; // c2

Motivational Example. Consider a component from the decoder module in the CVA6
[20] processor as shown in Listing 1. When decoding the CSRRS rd, csrReg, rs1
instruction, the processor performs CSR_READ (line 5) or CSR_SET (line 7)
operation on the control and status register (CSR), csrReg, based on the
register operand rs1 (line 4). Assume the coverage points $c_{1}$ and $c_{2}$
in the if-else block as shown in line 5 and line 7. Suppose the instruction in
the current input is CSRRS x16, stvec, x0. The value of rs1 for this
instruction is 0. Hence the if condition evaluates to True, and the CSR_READ
operation is performed on the CSR, stvec, covering the point $c_{1}$. Now, our
objective, when mutating this input, is to cover $c_{2}$. Also, suppose we
have only two mutation operators in this toy example: Bitflip, which flips one
bit of the operand, rs1, and OpcodeMut, which mutates the opcode to another
opcode. If both mutation operators are equally likely to be selected, the
probability of covering $c_{2}$ after mutation is $(0.5\times 0)+(0.5\times
1)=0.5$. On the other hand, if we assign a higher weight to Bitflip, say
$0.9$, the probability of covering $c_{2}$ is $(0.1\times 0)+(0.9\times
1)=0.9$. So, selecting mutation operators with equal probability is not ideal.
To address this problem, we formulate the problem of finding the optimal
weights for the mutation operators as a PSO problem, as explained next.

Notation. Let $M$ be an ordered list of all mutation operators (i.e., $M[j]$
is the $j^{\text{th}}$ mutation operator). Let
$W^{M}=[w^{M}_{1},w^{M}_{2},\ldots,w^{M}_{|M|}]$ be a weight vector for the
$|M|$ operators. So, $w^{M}_{j}$ is the weight of the $j^{\text{th}}$ mutation
operator $M[j]$. Note that since we interpret the weights as the probabilities
of selecting the mutation operators, we normalize the weights so that
$\sum_{j=1}^{|M|}w^{M}_{j}=1$ and $w^{M}\geq 0,\forall w^{M}\in W^{M}$.

Particles. We associate a particle with one thread of the fuzzer. Since
fuzzers run multiple, say $|N|$, threads simultaneously, we have a swarm of
$|N|$ particles associated with the fuzzer. Each of these $|N|$ threads has a
different weight vector $W_{i}^{M}$ for mutating the inputs in its thread.
Each such $W_{i}^{M}$ is assigned as the position $p_{i}^{M}$ of the
corresponding particle $i^{M}$ ($M$ indicates that the particle refers to
mutation operators). Mathematically, $W_{i}^{M}=p_{i}^{M}$.

Local Best Position. Following PSO, we assign the local best position,
$l_{i}^{best,M}$, of a particle as the best position of that particle so far.
In our case, we define a position at iteration $t_{2}$, $p_{i}^{M}(t_{2})$, as
better than the position at iteration $t_{1}$, $p_{i}^{M}(t_{1})$, if and only
if $p_{i}^{M}(t_{2})$ results in higher coverage than $p_{i}^{M}(t_{1})$.

Global Best Position. Likewise, following PSO, we assign a single global best
position, $g^{best,M}$, as the best position of all particles in the swarm.

Fig. 1 illustrates the high-level flow of this formulation. Like other
hardware fuzzers, we generate a set of seeds, which are simulated to obtain
their coverage information. Then, we use this coverage information to update
the $L^{best,M}=[l_{1}^{best,M},l_{2}^{best,M},\ldots,l_{|N|}^{best,M}]$ and
the $g^{best,M}$. Then, we update the velocities ($v_{i}^{M}$) and positions
($p_{i}^{M}$) of all particles according to Eqs. (1) and (2). We sample the
mutation operators according to the updated positions ($p_{i}^{M}$), i.e.,
mutation operator weights ($W_{i}^{M}$), and perform the mutations to generate
new tests. These new tests are simulated to obtain coverage, and the cycle
continues. After several iterations, the particles are expected to converge to
the optimal solution.

Figure 1: Flow for integrating PSO in TheHuzz.

This preliminary solution provides a way to find a weight distribution of the
mutation operators. However, it has two critical limitations, as explained
below.

Figure 2: Selection probability trend for all mutation operators for CVA6 [20]
(a) without and (b) with reset

###  III-B Reset Particles and Seeds

Challenge 1: Saturation of Particles’ Performance. Traditional PSO is designed
so that the particles converge to an optimum (ideally the global optimum) in
the solution space. However, for fuzzing hardware, one must find new coverage
points in each iteration that have not been covered. In other words, the
optimal solution (i.e., the weights of the mutation operators) changes based
on the coverage achieved so far, as explained in the following example.

Motivational Example. Refer to Listing. 1 with two coverage points, $c_{1}$
and $c_{2}$. Without loss of generality, assume two mutation operators $m_{1}$
and $m_{2}$ with the following property: $\mathcal{P}(c_{1}|m_{1})=0.9$ and
$\mathcal{P}(c_{1}|m_{2})=0.2$, where $\mathcal{P}(c_{i}|m_{j})$ denotes the
probability of covering $c_{i}$ conditioned on the event that mutation
operator $m_{j}$ is used.111Note that since the coverage points belong to two
different mutually exclusive and exhaustive branches,
$\mathcal{P}(c_{2}|m_{1})=0.1$ and $\mathcal{P}(c_{2}|m_{2})=0.8$. Suppose
during the first iteration ($t=1$), the weights for the two mutation operators
are equal, i.e., $0.5$. Then, the probability of covering $c_{1}$,
$\mathcal{P}(c_{1})^{t=1}=(0.5\times 0.9)+(0.5\times 0.2)=0.55$, and
$\mathcal{P}(c_{2})^{t=1}=(0.5\times 0.1)+(0.5\times 0.8)=0.45$. Now, if
$c_{1}$ is covered in the first iteration, then, for the second iteration
($t=2$), having equal weights for both operators results in
$\mathcal{P}(c_{2})^{t=2}=\mathcal{P}(c_{2})^{t=1}=0.45$. On the other hand,
if we have a larger weight for $m_{2}$, say $0.9$, then
$\mathcal{P}(c_{2})^{t=2}=(0.1\times 0.1)+(0.9\times 0.8)=0.73$. In fact, to
maximize the likelihood of covering $c_{2}$ in the second iteration, the
weight for $m_{2}$ should be $1$.

This simple example shows that to maximize the likelihood of covering the
maximal number of points with the minimal number of iterations (i.e., input
tests), the weights of the mutation operators should be decided dynamically
based on the coverage achieved so far. However, during our experiments with
the preliminary PSO formulation, we observe that the positions of the
particles ($p_{i}^{M}$) saturate after a few iterations because their
velocities ($v_{i}^{M}$) become zero according to Eq. (1). In other words, the
weights of selecting the mutation operators ($W_{i}^{M}$) stagnate very
quickly. Fig. 2 (a) demonstrates this phenomenon for the CVA6 processor. The
particles saturate within $50$ iterations. Due to this, the preliminary
formulation fails to detect critical vulnerabilities (more details in Sec.
IV).

Solution 1. To address challenge 1, we reset the position ($p_{i}^{M}$) and
velocity ($v_{i}^{M}$) of the particles that saturate, i.e., that do not yield
new coverage. Resetting removes saturating particles and replaces them with
new particles, leading to new weights for the mutation operators
($W_{i}^{M}$). Along with resetting the position and velocity of the saturated
particle, we also reset the associated seed because the position and velocity
of a particle are a function of the seed it started from (as seen in Fig. 1).
Using the same seed when resetting the particle will likely lead to the
exploration of design space that has already been explored by that particle.
This is suboptimal since our objective is to cover new regions in the design.

The condition for resetting the particles and their seeds is decided based on
the coverage trend in recent iterations. We reset when there is no improvement
in coverage for $\beta^{M}$ consecutive iterations. Here, $\beta^{M}$ controls
the trade-off between runtime and exploitation of learned knowledge by the
particles. Larger values of $\beta^{M}$ can lead to a deeper exploration of
design but will incur runtime overhead since the particles are not reset
quickly after they saturate. On the other hand, smaller values of $\beta^{M}$
can reduce runtime but will make the algorithm similar to random exploration,
which will not cover deeper regions of the design.

Fig. 2 (b) shows the positions of the particles for different mutation
operators after implementing this solution for CVA6. When the particles
saturate, they are reset (along with the associated seeds), resulting in
higher coverage speedup (as seen in Table II). Algorithm 1 details how this
solution is incorporated using a reset monitor, RstMon. It takes as input a
set of particles, their $L^{best}$, resetting threshold ($\beta$), a variable
to count the number of consecutive iterations with no improvement ($Ct$), and
a function $\mathcal{F}$ that returns the fitness (i.e., coverage) of a
particle. The algorithm iterates over all particles and compares the coverage
with the particle’s local best coverage (lines 2 and 3). If a particle’s
coverage is more than its local best coverage, the local best is updated, and
the counter ($Ct$) is reset (lines 4 and 5). Otherwise, the counter is
incremented, indicating no improvement in coverage for one more consecutive
iteration for that particle (line 7). If the counter exceeds the threshold
$\beta$ for a particle, that particle is added to the set of particles to be
reset, $rst\\_P$ (lines 8 and 9). Finally, the algorithm updates the global
best ($g^{best}$) using all particles’ local bests (line 10).

Input: $P,L^{best},\beta,Ct,\mathcal{F}$

Output: $L^{best},g^{best},Ct,rst\\_P$

1

2$rst\\_P\leftarrow\phi$

3

4for  _$i\in P$_ do

5 if  _$\mathcal{F}(p_{i}) >\mathcal{F}(L^{best}[i])$_ then

6 $L^{best}[i]\leftarrow p_{i}$

7 $Ct[i]\leftarrow 0$

8

9 else

10 $Ct[i]\leftarrow Ct[i]+1$

11

// add particle to the reset set

12 if  _$Ct[i] >\beta$_ then

13 $rst\\_P\leftarrow rst\\_P\cup\\{i\\}$

14

15

16

17$g^{best}\leftarrow\text{particle with highest }L^{best}$

18return $L^{best},g^{best},rst\\_P,Ct$

19

Algorithm 1 RstMon: Reset monitor Figure 3: PSOFuzz framework.

###  III-C Seed Generation Using PSO

Challenge 2: Ineffective Seed Generation. A drawback of existing hardware
fuzzers (as well as our preliminary formulation) is that they use a static
probability distribution of instructions to generate the seeds [6, 11, 13, 8,
7, 12]. However, the optimal set of instructions required by the seeds to
trigger new coverage points changes with time during fuzzing.222An example
similar to the one described in Sec. III-B can demonstrate this, but we omit
it in the interest of space. Moreover, the performance of each particle for
mutation operators ($i^{M}$), i.e., the number of iterations it survives, is
highly related to the quality of its seed.

Solution 2. To address this problem of static distribution of instructions for
seed generation, we devise a dynamic seed generation algorithm using PSO. The
idea is to map the problem of identifying optimal probabilities of the
instructions for seeds as a PSO problem. Next, we discuss this formulation.

Notation. Let $T$ be an ordered list of instruction types, such as R-type and
I-type [21]. Let $W^{T}=[w^{T}_{1},w^{T}_{2},\ldots,w^{T}_{|T|}]$ be the
weight vector for the $|T|$ instruction types. So, $w^{T}_{j}$ is the weight
of the $j^{\text{th}}$ instruction type $T[j]$, and
$\sum_{j=1}^{|T|}w^{T}_{j}=1$ and $w^{T}\geq 0,\forall w^{T}\in W^{T}$.

Particles. Similar to the PSO formulation for selecting mutation operators
(Sec. III-A), we associate a particle with one thread of the fuzzer. So, there
are a total of $|N|$ particles in the swarm, where $|N|$ is the number of
fuzzer threads. Suppose that each seed consists of a sequence of $|O|$
instructions. Then, for each of the $|N|$ threads being run simultaneously, we
have a different weight vector $W_{i}^{T}$ (which contains $|O|\times|T|$
entries, one for each of the $|T|$ instruction types for each of the $|O|$
instructions in the seed).

Each weight vector $W_{i}^{T}$ is assigned as the position $p_{i}^{T}$ of the
corresponding particle $i^{T}$. Here, the $T$ in the superscript indicates
that the particle is for the instruction types, as opposed to the $M$ in the
particles for selecting mutation operators in Sec. III-A. Mathematically,
$W_{i}^{T}=p_{i}^{T}$.

Local Best Position. Following PSO, we assign the local best position,
$l_{i}^{best,T}$, of a particle as the best position (i.e., the probabilities
of the instruction types) of that particle so far. Since this PSO is for seed
generation, the objective it aims to maximize is the quality of the generated
seed. We measure the quality of a particle for selecting instruction types
($i^{T}$) as the number of iterations the associated particles for selecting
mutation operators ($i^{M}$) survive. For instance, for a given particle,
$i^{T}$, if at iteration $t_{1}$ and $t_{2}$, its associated particle for
selecting mutation operators ($i^{M}$) survived for $150$ and $200$
iterations, respectively (as explained in Sec. III-B), then $p_{i}^{T}(t_{2})$
is better than $p_{i}^{T}(t_{1})$.

Global Best Position. Likewise, following PSO, we assign a single global best
position, $g^{best,T}$, as the best position of all particles in the swarm.

The high-level flow of this PSO for seed generation is very similar to that of
the PSO for selecting mutation operators. We start with randomly initialized
particles and update their velocities and positions according to Eqs. (1) and
(2), respectively. Moreover, learning from the prior pitfall of saturation of
particles’ performance (Sec. III-B), we also reset the particles for this PSO-
based seed generation when they saturate. Since the quality of a particle for
selecting instruction types ($i^{T}$) is measured by the number of iterations
its corresponding particle for selecting mutation operators ($i^{M}$)
survives, we reset $i_{T}$ when its corresponding $i^{M}$ is reset $\beta^{T}$
consecutive times. Similar to $\beta^{M}$, $\beta^{T}$ controls the trade-off
between runtime and exploitation of learned knowledge by $i^{T}$s.

###  III-D Putting it All Together

Fig. 3 shows the PSOFuzz framework, which includes PSO formulation along with
the resetting of seeds and particles for selecting mutation operators as well
as the PSO formulation for seed generation. The PSO formulation of seed
generation guides the seed generator by selecting the instruction type from
the instruction set architecture (ISA) pool. Once the instruction type is
sampled, the seed generator randomly selects an opcode of that instruction
type and then the operands to create the instruction. These instructions are
then used to create the seeds, which are added to the input test database. The
DUT is simulated with the tests to obtain coverage. This coverage data is used
to update the particles’ velocities and positions through their local and
global bests and the reset monitor. The updated positions are used to generate
seeds and mutate tests in the subsequent iterations.

Input: $DUT,t_{limit},tc,\beta^{M},\beta^{T},k$

Output: $cov$: total coverage achieved

// initialization

1 $t\leftarrow 0$, $cov\leftarrow 0$, $tests\leftarrow\phi$

2 Initialize $P^{M},V^{M},P^{T},V^{T}$

3 Initialize $L^{best,M}$ to $P^{M}$ and $g^{best,M}$ to $p_{0}^{M}$

4 Initialize $L^{best,T}$ to $P^{T}$ and $g^{best,T}$ to $p_{0}^{T}$

5

6$Ct^{M}\leftarrow 0$, $Ct^{T}\leftarrow 0$

7 $rst\\_P^{M}\leftarrow\phi$, $rst\\_P^{T}\leftarrow\phi$

8 $tests\leftarrow GenSeed(P^{T},tests,rst\\_P^{M})$

9 while  _$(cov <tc)$ and $(t<t_{limit})$_ do // main loop

10 $\mathcal{F}^{M},cov\leftarrow Simulate(DUT,tests)$

11 $L^{best,},g^{best,M},rst\\_P^{M},Ct^{M}\leftarrow
RstMon(P^{M},L^{best,M},\beta^{M},Ct^{M},\mathcal{F}^{M})$

12 if  _$rst\\_P^{M}\neq\phi$_ then // update PSO seed

13 $\mathcal{F}^{T}\leftarrow CalcFitness(rst\\_P^{M},P^{T})$

14

15 $L^{best,T},g^{best,T},rst\\_P^{T},Ct^{T}\leftarrow
RstMon(P^{T},L^{best,T},\beta^{T},Ct^{T},\mathcal{F}^{T})$

16

17 $P^{T},V^{T}\leftarrow
UpdatePV(P^{T},V^{T},L^{best,T},g^{best,T},rst\\_P^{T},k)$

18 $P^{M},V^{M}\leftarrow
UpdatePV(P^{M},V^{M},L^{best,M},g^{best,M},rst\\_P^{M},k)$ // gen. seeds for
reset particles

19 $tests\leftarrow GenSeed(P^{T},tests,rst\\_P^{M})$

// mutate tests for other particles

20 $tests\leftarrow Mut(P^{M},tests,\\{i^{M}|i^{M}\notin rst\\_P^{M}\\})$

21

22return $cov$

23

Algorithm 2 PSOFuzz

Algorithm 2 details the steps of PSOFuzz. It takes the DUT, a user-defined
time limit, $t_{limit}$, a user-defined target coverage, $tc$, the thresholds
for resetting the PSOs for mutation operators and seed generation, $\beta^{M}$
and $\beta^{T}$, and the constant, $k$, used to update the velocities of the
particles (Eq. (1)). We fuzz the DUT and return the coverage achieved, $cov$.
First, we initialize all required variables for PSO
($P^{M},V^{M},P^{T},V^{T},L^{best,M},g^{best,M},L^{best,T},g^{best,T}$). We
also initialize the saturation counters ($Ct^{M},Ct^{T}$) along with the sets
indicating particles that need to be reset because of saturation
($rst\\_P^{M},rst\\_P^{T}$). Next, on line 7, we use the positions $P^{T}$ to
generate the initial set of seed $tests$. Then, the main fuzzing loop starts
on line 8, which iterates until either the target coverage ($tc$) is achieved
or the runtime exceeds the time limit, $t_{limit}$. In each iteration of the
fuzzing loop, we first simulate the DUT with the generated $tests$ to obtain
the function $\mathcal{F}^{M}$ (which calculates the fitness of the particles)
and the coverage achieved so far, $cov$ (line 9). Next, on line 10, this
$\mathcal{F}^{M}$ is used to calculate the local and global bests for the
particles for mutation operators and to decide which particles need to be
reset according to $\beta^{M}$ following Algorithm 1. Then, skipping ahead on
line 15, the velocities and the positions of the particles for mutation
operators are updated, and on lines 16 and 17, the new $tests$ are generated
for both particles that are reset and not reset, respectively.

Additionally, on line 11, we check if any of the particles for the mutation
operators needs to be reset, i.e., $rst\\_P^{M}\neq\phi$, and calculate the
number of iterations those particles survived (i.e., fitness) and return
$\mathcal{F}^{T}$ on line 12. This $\mathcal{F}^{T}$ is used to calculate the
local and global bests for the particles for seed generation and to decide
which ones to reset according to $\beta^{T}$ on line 13. Finally, on line 14,
the velocities and the positions of the particles for seed generation are
updated.

##  IV Evaluation

TABLE I: Vulnerability detection speedup compared to TheHuzz [11]. N.D.
denotes “not detected.”

Processor | Vulnerability | CWE |  TheHuzz [11] | PSO | PSO+Reset | PSO+Reset+Seed (PSOFuzz)
---|---|---|---|---|---|---
# Tests | # Tests | Speedup | # Tests | Speedup | # Tests | Speedup
CVA6 [20] |  | V1: Access invalid addresses
---
without throwing exceptions.
CWE-1252 | $3.52\times 10^{2}$ | $1.38\times 10^{2}$ | $2.55\times$ | $5.71\times 10^{2}$ | $0.62\times$ | $2.32\times 10^{2}$ | $1.52\times$
| V2: Decode multiplication
---
instructions incorrectly.
CWE-440 | $2.71\times 10^{3}$ | $5.09\times 10^{3}$ | $0.53\times$ | $1.80\times 10^{3}$ | $1.50\times$ | $4.51\times 10^{2}$ | $6.01\times$
| V3: Access unimplemented
---
CSRs and return X-values.
CWE-1281 | $4.75\times 10^{3}$ | N.D. | N.D. | $8.56\times 10^{2}$ | $5.54\times$ | $5.70\times 10^{3}$ | $0.83\times$
| V4: Cache coherency
---
violation undetected.
CWE-1202 | $1.83\times 10^{2}$ | $1.23\times 10^{4}$ | $0.01\times$ | $1.70\times 10^{1}$ | $10.76\times$ | $1.20\times 10^{1}$ | $\mathbf{15.25\times}$
| V5: Decode the FENCE.I
---
instruction incorrectly.
CWE-440 | $6.80\times 10^{1}$ | $4.50\times 10^{2}$ | $0.15\times$ | $1.80\times 10^{1}$ | $3.78\times$ | $1.35\times 10^{2}$ | $0.50\times$
| V6: Incorrect exception type
---
in instruction queue.
CWE-1202 | $5.55\times 10^{3}$ | $1.94\times 10^{4}$ | $0.29\times$ | $5.39\times 10^{2}$ | $10.30\times$ | $1.26\times 10^{3}$ | $4.40\times$
| V7: Some illegal instructions
---
without throwing exceptions.
CWE-1242 | $9.30\times 10^{1}$ | N.D. | N.D. | $2.54\times 10^{2}$ | $0.37\times$ | $7.40\times 10^{1}$ | $1.26\times$
Rocket Core [22] |  | V8: EBREAK does not
---
increase instruction count.
CWE-1201 | $1.67\times 10^{3}$ | $6.67\times 10^{3}$ | $0.25\times$ | $1.07\times 10^{3}$ | $1.56\times$ | $4.10\times 10^{2}$ | $4.07\times$

In this section, we evaluate the speed of PSOFuzz in detecting vulnerabilities
and achieving coverage on three popular open-sourced RISC-V [21] processors.

###  IV-A Evaluation Setup

We use the state-of-the-art simulation-based processor fuzzer, TheHuzz [11] as
a baseline for all evaluations.333Following [11], we implemented TheHuzz in
Python. To ensure that the enhancements in results exclusively stem from PSO
adaptation, we integrate PSO schemes into TheHuzz’s mutation engine and seed
generator. In addition to reporting the results for our final formulation,
PSOFuzz, which is also denoted as PSO+Reset+Seed, we also report the results
for (i) the preliminary formulation, PSO, which includes the PSO-based
mutation operator selection, but neither the resetting solution (Solution 1),
nor the PSO-based seed generation technique (Solution 2), and (ii) the
intermediate formulation, PSO+Reset, which includes the PSO-based mutation
operator selection with reset, but not PSO-based seed generation.

Following [11], we set the number of simultaneous threads and hence the number
of particles, $|N|$, as $10$ and the number of instructions in each program,
$|O|$, as $20$. To have a balanced impact of exploration (due to velocity) and
exploitation (due to local and global bests), we set $k$ (Eq. (1)) as $0.5$.
Based on empirical observations, we set $\beta^{M}=\beta^{T}=3$, as a larger
$\beta$ will cause runtime overhead, while a smaller $\beta$ will make PSOFuzz
generate test cases similar to random exploration, as discussed in Sec. III-B.

Since most commercial processors are close-sourced, we evaluate PSOFuzz using
three widely-used open-sourced processors from RISC-V [21] ISA: CVA6 [20],
BOOM [23], and Rocket Core [22]. Existing hardware processor fuzzers use
similar open-sourced processors for their evaluation [9, 11, 13]. CVA6
supports out-of-order execution (OoO) and a custom single instruction-multiple
data (SIMD) floating point unit. Rocket Core is an in-order processor. BOOM is
a superscalar processor built using the components of Rocket Core. Moreover,
all of these processors are capable of booting Linux operating system while
CVA6 is commercially used to build processors for high-security applications
[24]. Therefore, these processors with different complexity form a diverse
benchmark set to evaluate PSOFuzz.

We use Synopsys VCS [25] as the simulation tool and Chipyard [26] as the
system-on-chip (SoC) simulation environment. To ensure a fair comparison, we
ran experiments on each benchmark for 24 hours and repeated them thrice. We
demonstrate our results using the branch coverage metric, which is highly
related to vulnerability detection [27]. We use a Linux-based CPU running at
2.6GHz, with 64 threads and 512GB of RAM for our experiments.

###  IV-B Vulnerability Detection

The vulnerability detection strategy used by our techniques (PSO, PSO+Reset,
PSO+Reset+Seed) compares the processor’s outputs with that of a GRM. Many
existing fuzzers use a similar detection strategy [11, 9, 13, 12]. The
strategy compares the architectural states of the processor and the GRM for
each executed instruction. The architectural states include the instructions
committed; any exceptions triggered; the general purpose registers (GPRs)
modified; the CSRs modified; the privilege level of the processor; and the
memory address and data accesses. A mismatch in architectural states indicates
a potential vulnerability in the processor. Similar to [11, 9, 13, 12], we use
Spike [28], the RISC-V ISA emulator, as the GRM.

Comparison with TheHuzz. Table I shows the number of tests and the speedup of
our techniques compared to TheHuzz. PSOFuzz detects all the vulnerabilities
detected by TheHuzz up to $15.25$$\times$ faster. The results also show the
necessity of using the reset strategy for PSO. Naïve PSO is slower than
TheHuzz in detecting vulnerabilities because its particles are likely
exploring the design spaces that have already been explored, as mentioned in
Sec. III-B. PSO+Reset performs better than PSO due to resetting the particles,
allowing it to dynamically select the optimal mutation operators. It also
outperforms PSO+Reset+Seed (PSOFuzz) in detecting some vulnerabilities, such
as V3, because PSOFuzz initially spends time exploring the optimal
probabilities for seed generation. However, PSOFuzz achieves the highest
speedup compared to TheHuzz and other PSO techniques for most vulnerabilities
because it uses the optimal probabilities for both seed generation and
instruction mutation, efficiently exploring different regions of the design
space.

TABLE II: Coverage improvement compared to TheHuzz [11].

Core |  TheHuzz [11] | PSO | PSO+Reset | PSO+Reset+Seed (PSOFuzz)
---|---|---|---|---
Total | Total | Increment | Speedup | Total | Increment | Speedup | Total | Increment | Speedup
CVA6 [20] | $6214$ | $6074$ |  $-2.25$$\%$ |  $0.25$$\times$ | $6334$ |  $2.00$$\%$ |  $6.39$$\times$ | $6277$ |  $1.00$$\%$ | $\mathbf{2.22}\times$
BOOM [23] | $23086$ | $23052$ |  $-0.15$$\%$ |  $0.73$$\times$ | $23088$ |  $0.01$$\%$ |  $1.11$$\times$ | $23092$ |  $0.01$$\%$ |  $1.25$$\times$
Rocket Core [22] | $11947$ | $11846$ |  $-0.85$$\%$ |  $0.10$$\times$ | $11864$ |  $-0.06$$\%$ |  $0.23$$\times$ | $11958$ |  $0.09$$\%$ |  $1.72$$\times$

Figure 4: Coverage achieved compared to TheHuzz [11] for (a) CVA6 [20], (b)
BOOM [23], and (c) Rocket Core [22].

###  IV-C Coverage Achievement

We now compare the capability of our techniques in achieving coverage against
TheHuzz, as coverage achieved is a proxy metric to the extent of design
verified and determines its readiness to tape out [29]. Across the three
processors, PSO optimizations achieve up to $6.39$$\times$ speedup compared to
TheHuzz while obtaining up to $2$% more coverage after fuzzing for 24 hours
with more than 20K tests, as shown in Table II. Fig. 4 shows the mean and
standard deviation of coverage achieved with respect to the number of input
tests.

PSOFuzz outperforms PSO+Reset on Rocket Core and BOOM because the PSO-based
seed generation dynamically adjusts the optimal set of instructions required
to cover new points. While PSOFuzz is slower than PSO+Reset on CVA6, it still
outperforms TheHuzz and PSO techniques.

Among the three processors, PSOFuzz achieves the fastest speedup
($2.22$$\times$) and highest coverage increment ($1.00$%) on CVA6, which is
the complex processor with OoO and SMID features. This is because the PSO
optimizations aid in covering the hard-to-reach coverage points in the custom
floating point unit of CVA6, which are difficult to cover with static mutation
operator scheduling schemes. Even on the remaining processors, BOOM and Rocket
Core, PSOFuzz achieves faster coverage (up to 1.72${}\times$) compared to
TheHuzz and covers more points than TheHuzz. The speedup on these processors
is less than that of CVA6 because Rocket Core is a simple processor compared
to CVA6 while BOOM is built by duplicating most of the components of Rocket
Core. Hence, TheHuzz covers more than $87\%$ of their points, resulting in
less scope for improvement for PSOFuzz.

In summary, PSOFuzz detects vulnerabilities and achieves coverage faster than
TheHuzz on all three processors, demonstrating the necessity of dynamic
scheduling of mutation operators and seed generation.

##  V Related Work

This section describes the existing hardware fuzzers, their limitations, and
how PSOFuzz addresses those limitations.

RFUZZ [6] uses mux-toggle coverage to capture the activity in the select
signals of MUXes. It schedules mutation operators statically, similar to AFL
fuzzer [17]. Also, mux-toggle coverage is not scalable to large designs such
as BOOM [9]. HyperFuzzing [7] is an SoC fuzzer that defines security
properties and uses AFL fuzzer’s static mutation operator scheduling and
random seed generation to detect vulnerabilities. DirectFuzz [8] modifies
RFUZZ to perform directed fuzzing on specific modules of the target hardware.
However, it uses similar static schemes as RFUZZ.

Processor fuzzer DIFUZZRTL [9] uses activity in the control registers as
coverage to address the scalability issues of RFUZZ. It uses grammar-based
mutation operators inspired by AFL. But, it generates seeds randomly and uses
static mutation operator scheduling schemes. BugsBunny [12] fuzzes specific
target signals in the hardware using DIFUZZRTL as the base fuzzer. Hence, its
mutation operator scheduling and seed generation schemes are static. Trippel
et al. [10] convert hardware to a software model and fuzz using AFL fuzzer
with static mutation scheduling. TheHuzz [11] is another processor fuzzer that
uses different types of code coverage metrics to capture activity in the
combinational and sequential logic of the hardware. It also uses a profiler to
optimize the mutation scheduling. However, this optimization is static for a
given processor and does not change with the coverage achieved.

A recent hardware fuzzer HyPFuzz [13] attempts to address the slower coverage
speeds of hardware fuzzers by combing formal tools with fuzzing. This
optimization to fuzzing is orthogonal to PSOFuzz as HyPFuzz also uses static
mutation operator scheduling and seed generation schemes which can be
optimized through our PSO techniques.

In summary, all of the existing hardware fuzzers use static mutation operator
scheduling and seed generation schemes and cannot dynamically adjust their
strategies for the target hardware and coverage achieved. In contrast, we
propose PSOFuzz, a PSO-guided fuzzer, to demonstrate how hardware fuzzers can
be equipped with PSO optimizations to improve their vulnerability detection
and coverage achievement speeds.

##  VI Discussion

In this section, we discuss possible extensions to improve PSOFuzz and
hardware fuzzing in general.

Dynamically Identifying Optimal Solutions. Though the reset strategy works
well in practice, it is a heuristic that modifies the PSO algorithm. In the
future, we plan to model and analyze the impact of resetting threshold
($\beta$) on the capability of vulnerability detection and design space
exploration of PSOFuzz. Moreover, we will also evaluate the performance of
other meta-heuristic algorithms, such as simulated annealing [30] and
differential evolution [31], and identify the ideal one for hardware fuzzing.

Leveraging Prior Knowledge for Initialization. One key way to improve its
performance is by initializing with a good starting point [32]. PSOFuzz
initializes particles’ positions randomly. However, we can use the static
schemes of existing fuzzers to initialize the particles. For example, the
static probabilities from the profiling state of TheHuzz can be used as the
initial position of particles to select the mutation operators.

##  VII Conclusion

Processor fuzzers, which rely on the mutation of input tests, have shown
promise in detecting vulnerabilities. However, they use static scheduling
strategies for mutation and seed generation, which is not ideal. To overcome
this limitation, we develop a novel PSO-based framework, PSOFuzz, that can be
integrated with any fuzzer to find optimal scheduling strategies. To ensure
better vulnerability detection performance, we augment naïve PSO with (i) a
reset strategy that allows it to find dynamic selection probabilities for
mutation operators and (ii) a PSO-based seed generation algorithm.
Experimental results with the state-of-the-art simulation-based hardware
fuzzer demonstrate that PSOFuzz can speed up vulnerability detection by up to
$15.25\times$ and coverage achievement by up to $2.22\times$. In conclusion,
PSOFuzz addresses a critical limitation of existing processor fuzzers and
significantly improves the effectiveness and efficiency of processor
verification.

##  VIII Acknowledgement

Our research work was partially funded by the US Office of Naval Research (ONR
Award #N00014-22-1-2279), by Intel’s Scalable Assurance Program, and by the
European Union (ERC, HYDRANOS, 101055025). Any opinions, findings,
conclusions, or recommendations expressed herein are those of the authors and
do not necessarily reflect those of the US Government, the European Union, or
the European Research Council.

## References

  * [1] S. Fine and A. Ziv, “Coverage Directed Test Generation for Functional Verification using Bayesian Networks,” _Design Automation Conference_ , 2003\.
  * [2] J. Rajendran, V. Vedula, and R. Karri, “Detecting Malicious Modifications of Data in Third-party Intellectual Property Cores,” 2015.
  * [3] G. Dessouky _et al._ , “HardFails: Insights into Software-Exploitable Hardware Bugs,” _28th USENIX Security Symposium_ , 2019.
  * [4] A.-R. Sadeghi, J. Rajendran, and R. Kande, “Organizing The World’s Largest Hardware Security Competition: Challenges, Opportunities, and Lessons Learned,” 2021.
  * [5] C. Chen _et al._ , “Trusting the Trust Anchor: Towards Detecting Cross-Layer Vulnerabilities with Hardware Fuzzing,” 2022.
  * [6] K. Laeufer _et al._ , “RFUZZ: Coverage-Directed Fuzz Testing of RTL on FPGAs,” _IEEE/ACM International Conference on Computer-Aided Design_ , pp. 1–8, 2018.
  * [7] S. K. Muduli, G. Takhar, and P. Subramanyan, “HyperFuzzing for SoC Security Validation,” _ACM/IEEE International Conference on Computer-Aided Design_ , pp. 1–9, 2020.
  * [8] S. Canakci _et al._ , “Directfuzz: Automated Test Generation for RTL Designs using Directed Graybox Fuzzing,” _ACM/IEEE Design Automation Conference_ , pp. 529–534, 2021.
  * [9] J. Hur _et al._ , “DIFUZZRTL: Differential Fuzz Testing to Find CPU Bugs,” _IEEE Symposium on Security and Privacy_ , pp. 1286–1303, 2021.
  * [10] T. Trippel _et al._ , “Fuzzing Hardware Like Software,” _USENIX Security Symposium_ , 2022.
  * [11] R. Kande _et al._ , “TheHuzz: Instruction Fuzzing of Processors Using Golden-Reference Models for Finding Software-Exploitable Vulnerabilities,” _USENIX Security Symposium_ , pp. 3219–3236, 2022.
  * [12] H. Ragab _et al._ , “BugsBunny: Hopping to RTL Targets with a Directed Hardware-Design Fuzzer,” _SILM_ , Jun. 2022. [Online]. Available: https://download.vusec.net/papers/bugsbunny_silm22.pdf
  * [13] C. Chen _et al._ , “HyPFuzz: Formal-Assisted Processor Fuzzing,” _arXiv preprint arXiv:2304.02485_ , 2023.
  * [14] IntelLabs, “Pre-Silicon Hardware Fuzzing Toolkit,” https://github.com/IntelLabs/PreSiFuzz, 2023, last accessed on 05/21/2023.
  * [15] J. Kennedy and R. Eberhart, “Particle swarm optimization,” _IEEE international conference on neural networks_ , 1995.
  * [16] C. Lyu _et al._ , “MOpt: Optimized Mutation Scheduling for Fuzzers.” _USENIX Security Symposium_ , pp. 1949–1966, 2019.
  * [17] lcamtuf, “American Fuzzy Lop (AFL) Fuzzer.” 2014, Last accessed on 05/21/2023. [Online]. Available: http://lcamtuf.coredump.cx/afl/technical_details.txt
  * [18] Z.-H. Zhan _et al._ , “Adaptive Particle Swarm Optimization,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , 2009.
  * [19] Y. Shi and R. Eberhart, “A Modified Particle Swarm Optimizer,” _IEEE international conference on evolutionary computation proceedings._ , 1998.
  * [20] F. Zaruba and L. Benini, “The Cost of Application-Class Processing: Energy and Performance Analysis of a Linux-Ready 1.7-GHz 64-Bit RISC-V Core in 22-nm FDSOI Technology,” _IEEE Transactions on Very Large Scale Integration Systems_ , vol. 27, no. 11, pp. 2629–2640, Nov 2019.
  * [21] RISC-V, “RISC-V Webpage,” https://riscv.org/, 2021, Last accessed on 05/21/2023.
  * [22] K. Asanović _et al._ , “The Rocket Chip Generator,” no. UCB/EECS-2016-17, Apr 2016. [Online]. Available: http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-17.html
  * [23] J. Zhao _et al._ , “SonicBOOM: The 3rd Generation Berkeley Out-of-Order Machine,” _Fourth Workshop on Computer Architecture Research with RISC-V_ , May 2020.
  * [24] H. C. GmbH, “MiG-V – Made in Germany RISC-V,” 2022, Last accessed on 05/21/2023. [Online]. Available: https://hensoldt-cyber.com/mig-v/
  * [25] “VCS,” https://www.synopsys.com/verification/simulation/vcs.html, 2023, Last accessed on 05/21/2023.
  * [26] A. Amid _et al._ , “Chipyard: Integrated Design, Simulation, and Implementation Framework for Custom SoCs,” _IEEE Micro_ , vol. 40, no. 4, pp. 10–21, 2020.
  * [27] A. Mockus, N. Nagappan, and T. T. Dinh-Trong, “Test Coverage and Post-Verification Defects: A Multiple Case Study,” pp. 291–301, 2009.
  * [28] RISC-V, “SPIKE Source Code,” https://github.com/riscv/riscv-isa-sim, 2023, last accessed on 05/21/2023.
  * [29] Synopsys, “Accelerating Verification Shift Left with Intelligent Coverage Optimization,” https://www.synopsys.com/cgi-bin/verification/dsdla/pdfr1.cgi?file=ico-wp.pdf, 2022, Last accessed on 05/21/2023.
  * [30] D. Bertsimas and J. Tsitsiklis, “Simulated Annealing,” _Statistical science_ , 1993.
  * [31] K. V. Price, “Differential Evolution,” _Handbook of Optimization: From Classical to Modern Approach_ , pp. 187–214, 2013.
  * [32] D. Simpson _et al._ , “Penalising model component complexity: A principled, practical approach to constructing priors,” 2017.