# Sparse Linear Centroid-Encoder: A Convex Method for Feature Selection

Tomojit Ghosh<EMAIL_ADDRESS>
Department of Mathematics
Colorado State University
Fort Collins, CO 80523 ,USA Michael Kirby<EMAIL_ADDRESS>
Department of Mathematics
Colorado State University
Fort Collins, CO 80523, USA Karim Karimov<EMAIL_ADDRESS>
Department of Mathematics
Colorado State University
Fort Collins, CO 80523, USA

###### Abstract

We present a novel feature selection technique, Sparse Linear Centroid-Encoder
(SLCE). The algorithm uses a linear transformation to reconstruct a point as
its class centroid and, at the same time, uses the $\ell_{1}$-norm penalty to
filter out unnecessary features from the input data. The original formulation
of the optimization problem is nonconvex, but we propose a two-step approach,
where each step is convex. In the first step, we solve the linear Centroid-
Encoder, a convex optimization problem over a matrix $A$. In the second step,
we only search for a sparse solution over a diagonal matrix $B$ while keeping
$A$ fixed. Unlike other linear methods, e.g., Sparse Support Vector Machines
and Lasso, Sparse Linear Centroid-Encoder uses a single model for multi-class
data. We present an in-depth empirical analysis of the proposed model and show
that it promotes sparsity on various data sets, including high-dimensional
biological data. Our experimental results show that SLCE has a performance
advantage over some state-of-the-art neural network-based feature selection
techniques.

##  1 Introduction

In the era of Big Data and AI supercomputing, there are unparalled
opportunities for knowledge discovery from data. Deep neural networks and
transformers have had a transformative impact on how scientists, and engineers
approach modeling and predictive analytics. While incredibly powerful, the
modeling capabilities of these neural networks are often hard to explain,
i.e., they perform well for reasons that are poorly understood. The tendency
is to embrace complexity and large parameter sets, rather than simplicity and
explainability. In this paper we present a relatively simple neural network
architecture that has surprisingly good performance even with limited data.

The main modeling question we address here is the existence of a reduced input
feature set capable of classifying the phenomenon of interest, and further, if
there exists a linear data reduction mapping to facilitate their discovery. We
are motivated along this path given the success nonlinear architectures, e.g.,
deep feature selection (DFS) (Li et al., 2016) and Centroid Encoder (Ghosh and
Kirby, 2022). For example, the basic idea of Centroid Encoder is to use an
autoencoder neural network architecture where the targets at the decoder
output are the centroids of the class. The result is a dimensionality reducing
transformation, i.e., the encoder, that can be used for classification.

Motivated in part by this autoencoder architecture, in this work we propose a
linear feature selection tool with a new optimization problem. We exploit the
linearity of the mapping to create a two step algorithm with each step being
convex. The two steps are alternated and consist of data fitting and
sparsification. The major appeal of this approach is the simplicity of the
resulting model, the reduced set of explanatory features and the fact
that–given each problem is convex–much less data is actually required to learn
the model.

Why are we modeling small data sets in the era of Big Data? While advances in
technology have made the acquisition of certain types of health data possible,
the ethical issues surrounding the collection of samples from human and animal
subjects make this data extremely limited in comparison to data sets generated
by scraping the internet. Note that in addition to the limited number of
available points $p$, the dimension of each sample $n$ can be relatively
large, e.g., omics data, so the assumption is that, at least for many
biological data sets, $n\gg p$.

Promoting sparsity with an $\ell_{1}$ penalty for feature selection is now
widely used, e.g., (Tibshirani, 1996; Fonti and Belitser, 2017; Muthukrishnan
and Rohini, 2016; Marafino et al., 2015; Shen et al., 2011; Lindenbaum and
Steinerberger, 2021; Candes et al., 2008; Daubechies et al., 2010; Bertsimas
et al., 2017; Xie and Huang, 2009). Support Vector Machines (Cortes and
Vapnik, 1995) have also been used extensively for feature selection, see
(Marafino et al., 2015; Shen et al., 2011; Sokolov et al., 2016; Guyon et al.,
2002; O’Hara et al., 2013; Chepushtanova et al., 2014). Group Sparse ANN
(Scardapane et al., 2017) used group Lasso (Tibshirani, 1996) to impose the
sparsity on a group of variables instead of a single variable. An unsupervised
feature selection technique based on the autoencoder architecture has been
proposed (Han et al., 2018). Additional examples of nonlinear archtictures
include (Balın et al., 2019; Yamada et al., 2020; Singh et al., 2020;
Taherkhani et al., 2018).

The contents of this paper is as follows: In Section 2 we propose a two step
optimization problem for convex linear feature selection. In Section 3 we
explore the robustness of the methodology including the sensitivity of the
method on the sparsity parameter, and the consistency of the features
selected. In Section 4 we do a comparative analysis of the proposed algorithm
with benchmark datasets. Finally we offer conclusions in Section 5.

##  2 Sparse Optimization using Linear Centroid-Encoder

Consider a data set $X=\\{x_{i}\\}_{i=1}^{N}$ with $N$ samples and $M$ classes
where $x_{i}\in\mathbb{R}^{d}$. Note each sample of data matrix $X$ is
represented by a column. The classes are denoted by $C_{j},j=1,\dots,M$ where
the indices of the data associated with class $C_{j}$ are denoted $I_{j}$. We
define centroid of each class as $c_{j}=\frac{1}{|C_{j}|}\sum_{i\in
I_{j}}x_{i}$ where $|C_{j}|$ is the cardinality of class $C_{j}$. Now we
define a matrix of class means $\tilde{C}\in\mathbb{R}^{d\times n}$ where the
$i$’th column of $\tilde{C}$ is the centroid associated with the class of the
$i$’th column of $X$. Note $\tilde{C}$ will have non-unique entries as long as
$M<n$. For example, consider the data set
$X=\\{x_{1},x_{2},x_{3},x_{4},x_{5}\\}$ which has two classes $C_{1},C_{2}$
where $I_{1}=\\{1,3,5\\}$ and $I_{2}=\\{2,4\\}$. Taking $c_{1},c_{2}$ as the
corresponding centroids we have
$\tilde{C}=\\{c_{1},c_{2},c_{1},c_{2},c_{1}\\}$. With this setup first we will
describe Linear Centroid-Encoder (LCE) which is the starting point of our
sparse algorithm.

###  2.1 Linear Centroid-Encoder (LCE)

The goal of LCE is to provide the linear transformation of the data to $k$
dimensions that best approximates the class centroids. Let
$A\in\mathbb{R}^{d\times k}$ be the transformation matrix. The unknown matrix
${A}$ may be determined by the following optimization problem

$\displaystyle\underset{A}{minimize}\;\;\|\tilde{C}-{A}{A}^{T}X\|_{F}^{2}$ (1)

Notice that the objective function in Equation (1) is a convex function of
$A$. Let $\mathcal{L}(A)=\frac{1}{2}\|\tilde{C}-{A}{A}^{T}X\|_{F}^{2}$. The
gradient of $\mathcal{L}$ is readily calculated as:

$\displaystyle\frac{\partial\mathcal{L}}{\partial
A}=AA^{T}XX^{T}A+XX^{T}AA^{T}A-(\tilde{C}X^{T}+X\tilde{C}^{T})A$ (2)

###  2.2 Sparse Linear Centroid-Encoder (SLCE)

Let $B\in\mathbb{R}^{d\times d}$ be a diagonal matrix with $b_{j,j}$ are the
diagonal entries. If we left-multiply $X$ by $B$, i.e, $BX$, then each
component $x_{i,j}$ of a the sample $x_{i}$ will be multiplied by $b_{j,j}$ as
shown below:

$BX=\begin{bmatrix}b_{1,1}\;\;0\;\;\ldots\;\;0\\\
0\;\;b_{2,2}\;\;\ldots\;\;0\\\ \vdots\hskip 21.33955pt\vdots\hskip
21.33955pt\vdots\\\ 0\;\;0\;\;\ldots\;\;b_{d,d}\\\
\end{bmatrix}\begin{bmatrix}x_{1,1}\;\;x_{2,1}\;\;\ldots\;\;x_{n,1}\\\
x_{1,2}\;\;x_{2,2}\;\;\ldots\;\;x_{n,2}\\\ \vdots\hskip 28.45274pt\vdots\hskip
28.45274pt\vdots\\\ x_{1,d}\;\;x_{2,d}\ldots\;\;x_{d,n}\\\
\end{bmatrix}=\begin{bmatrix}b_{1,1}x_{1,1}\;\;b_{1,1}x_{2,1}\;\;\ldots\;\;b_{1,1}x_{n,1}\\\
b_{2,2}x_{1,2}\;\;b_{2,2}x_{2,2}\;\;\ldots\;\;b_{2,2}x_{n,2}\\\ \vdots\hskip
35.56593pt\vdots\hskip 42.67912pt\vdots\\\
b_{d,d}x_{1,d}\;\;b_{d,d}x_{2,d}\ldots\;\;b_{d,d}x_{d,n}\\\ \end{bmatrix}$

With this setup, we introduce the Sparse Linear Centroid-Encoder below:

$\displaystyle\underset{A,B}{minimize}\;\;\|\tilde{C}-{A}{A}^{T}(BX)\|_{F}^{2}\;\;+\lambda|diag(B)|_{1}$
(3)

where $\lambda$ is a hyperparameter. The $\ell_{1}$-norm will drive most of
the $b_{j,j}$ to near zero. As an effect the corresponding elements or
features of $x_{i}$ will be ignored. Hence the the model will work as a linear
feature detector. It’s noteworthy that our aim is to reconstruct the class
centroids $c_{j}$ of a sample $x_{i}$ with fewer features. Equation 3 is a
non-convex model over the matrices $A,B$. Notice, the optimization becomes
convex if we fix one matrix and solve over the other. Hence the solution comes
following two convex steps: in the first step we keep $B$ fixed and solve over
$A$ and in the second step we freeze $A$ and solve over $B$. The
hyperparameter $\lambda$ in Equation 5 controls the sparsity. A higher value
will drive most of the $b_{j,j}$ to near zero producing a sparser solution
than a solution with lower $\lambda$. Therefore $\lambda$ is the knob which
controls the sparsity of our model.

Comment of Convexity: The optimization problem of SLCE is non convex over the
matrices $A,B$. But if we optimize over one matrix keeping other one fixed,
then the problem becomes convex as shown below:

$\displaystyle\underset{A}{minimize}\;\;\|\tilde{C}-{A}{A}^{T}(BX)\|_{F}^{2}\;\;+\lambda|diag(B)|_{1}$
(4)

$\displaystyle\underset{B}{minimize}\;\;\|\tilde{C}-{A}{A}^{T}(BX)\|_{F}^{2}\;\;+\lambda|diag(B)|_{1}$
(5)

If we initialize $b_{j,j}$ to 1 of matrix $B$, then Equation (4) is equivalent
to Equation (1) which is the LCE cost. First, we solve this optimization which
is convex over the set of $\mathbb{R}^{d\times k}$ matrices $A$. The domain is
a convex set, as convex combination of two $\mathbb{R}^{d\times k}$ matrices
is also a $\mathbb{R}^{d\times k}$ matrix. The cost function
$f(A)=\|\tilde{C}-{A}{A}^{T}X\|_{F}^{2}$ is also convex as any norm is a
convex function (Boyd and Vandenberghe, 2004). The second part of the
optimization, i.e., Equation 5 is also convex. The domain is a convex set as
any convex combination of two $\mathbb{R}^{d\times d}$ diagonal matrices is
also a $\mathbb{R}^{d\times d}$ diagonal matrix. The function
$g(B)=\|\tilde{C}-{A}{A}^{T}(BX)\|_{F}^{2}\;\;+\lambda|diag(B)|_{1}$ is a
combination of Frobenius and $\ell_{1}$ norm which are convex. Hence $g(B)$ is
a convex function as it’s a combination of two convex functions (Boyd and
Vandenberghe, 2004).

###  2.3 Training of SLCE

As mentioned before, SLCE is a two-step convex algorithm. In the first step,
we search for a solution for the matrix $A$ using Equation 1 with an embedding
dimension set to 5 for all data sets. In this step, we train the model until
the absolute value of the difference of the costs of two consecutive
iterations becomes less than equal to $10^{-6}$. After that, we fix the matrix
$A$ and introduce the diagonal matrix $B$ with diagonal entries set to 1. We
run the model for ten iterations without applying the $\ell_{1}$ penalty to
adjust the parameters of $B$. After which, we use the $\ell_{1}$ penalty on
the diagonal elements of $B$ for $2000$ iterations. Throughout the training
process, we use a fixed learning rate of 0.002. We don’t use mini-batches but
train on the entire training set with Adam optimizer (Kingma and Ba, 2015). We
implemented SLCE in PyTorch (Paszke et al., 2017) to run on GPUs on Tesla V100
GPU machines. We will provide the code with a dataset as supplementary
material.

Hyperparameter Tuning: SLCE uses two hyperparameters: the embedding dimension
$k$ and the sparsity parameter $\lambda$. In all of our experiments in the
article, we fixed $k=5$. To tune $\lambda$, we did a two-fold cross-validation
on a training partition with ten repeats to pick a suitable $\lambda$ for a
data set. We chose $\lambda$ from the range $0.04\dots 0.5$ and the optimal
values are kept in Table 1

Hyperparameter | Dataset
---|---
ALLAML | GLIOMA | SMK_CAN | Prostate_GE | GLI_85 | CLL_SUB
$\lambda$ | $0.10$ | $0.30$ | $0.05$ | $0.20$ | $0.25$ | $0.04$
Table 1: Data set specific sparsity parameter $\lambda$ used in our bench
marking experiment.

##  3 Analysis of SLCE

We did an array of analysis of the proposed model and we present the details
here.

###  3.1 Feature Sparsity

Figure 1: Sparsity analysis of SLCE on Pancan data set for three different
choices of $\lambda$. In each case, we plotted the absolute value of weights
of the diagonal elements ($b_{jj}$) of matrix $B$ in descending order. These
plots suggest the model induces sparsity on the input features, driving most
weights to near zero. Notice that as $\lambda$ decreases, the model selects a
larger set of features.

The proposed model induces sparsity by minimizing the $\ell_{1}$-norm of the
diagonal matrix $B$. The hyperparameter $\lambda$ acts as a regulator to
control feature sparsity; a higher value will generate a sparser solution
selecting a small set of features from the input data, whereas a smaller value
will pick a large group of variables. Figure 1 shows the sparsity analysis
using the high-dimensional Pancan data with $20,531$ features. We split the
data set into a $50:50$ ratio of train and test and run SLCE on the training
partition. The model promotes feature sparsity by enforcing a significant
number of $b_{jj}$ to near zeros ($10^{-4}$ to $10^{-8}$). For example, the
model only selects $887$ out of $20,531$ variables of original data when
$\lambda=0.5$. As expected, the number of chosen features starts to increase
for smaller values of $\lambda$.

###  3.2 Analysis of Feature Cut-Off

The experiment with feature sparsity shows that the $\ell_{1}$-norm drives a
lot of diagonal elements of matrix $B$ to near zero, which is pretty clear
from the three sparsity plots. Here we answer the question of finding out all
the features whose absolute weight is significantly higher than the rest. In
Figure 2, we plot the ratio of the absolute weight of two consecutive
$b_{jj}$’s for three values of $\lambda$. The plot suggests that the ratio is
maximum at a specific location. For example, when $\lambda=0.5$, the location
is 887, and for $\lambda=0.25$, the location is 2155. Hence one can ignore the
features after this position. This location matches the position of the elbow
in the sparsity plot in the previous analysis. In all of our experiments, we
observe the consistent behavior of the ratio plot, which we use to pick out
the significant variables in each run.

Figure 2: Demonstration of feature cut off using ratio of two consecutive
weights.

###  3.3 Feature Selection Stability

Figure 3: Demonstration of stability of SLCE features on Pancan data set. We
ran the model with three choices of $\lambda$ five times each. The Venn
diagram shows the intersection of those five feature sets.

Here we analyze how stable the proposed model is regarding the number of
selected features over multiple trials. We also check the overlap of the
feature sets over several runs to check how similar they are. To this end, we
run our model five times on the Pancan data for three different values of
$\lambda$ and then compare the feature sets. Figure 3 shows the results.
Notice that, in each case, the number of features the model selects is
consistent. For example, when $\lambda=0.5$, the model picks 887, 884, 886,
889, and 886 variables with an overlap of 876 resulting a Jaccard similarity
of 0.9766. Similarly we found a high Jaccard index of 0.9393 and 0.9006 for
$\lambda=$ $0.25$ and $0.125$ respectively. High Jaccard scores indicate that
the feature sets have a lot of commonality over different runs.

###  3.4 Discriminative Power of SLCE Features

Now we focus on whether the selected variables help separate the classes,
i.e., the discriminative power of selected features. We compare the PCA
embedding of Pancan data using all features vs. SLCE-selected features. First,
we create the PCA embedding on the training set with all $20,531$ features and
show the training and test samples in 3D using a scatter plot. After that, we
fit the training set by SLCE with $\lambda=0.5$; pick the selected $887$
features, create a PCA embedding of the training and test samples using the
selected features, and compare the 3D scatter plot with the first one as shown
in Figure 4. The embedding with all the features doesn’t separate the five
classes, whereas PCA does create five distinct blobs of data, one for each
tumor type with the SLCE features. Notice that the test samples are also
mapped closer to the corresponding training data.

Figure 4: Demonstration of discriminative power of SLCE features on Pancan
data set. On the left, we show the three dimensional PCA-embedding done with
all the features. On the right, we show the PCA embedding with 887 SLCE
features.

##  4 Experimental Results

We present the comparative evaluation of our model on various data sets using
several feature selection techniques.

###  4.1 Experimental Details

Dataset | No. Features | No. of Classes | No. of Samples | Domain
---|---|---|---|---
ALLAML | 7129 | 2 | 72 | Biology
GLIOMA | 4434 | 4 | 50 | Biology
SMK_CAN | 19993 | 2 | 187 | Biology
Prostate_GE | 5966 | 2 | 102 | Biology
GLI_85 | 22283 | 2 | 85 | Biology
CLL_SUB | 11340 | 3 | 111 | Biology
PanCan | 20531 | 5 | 801 | Biology(RNA-Seq)
Table 2: Descriptions of the data sets used for benchmarking experiments.

We use seven high-dimensional biological (see Table 2) to compare SLCE with
Penalized Fisher’s Linear Discriminant Analysis (PFLDA) (Witten and
Tibshirani, 2011) and three neural network-based models to run benchmarking
experiments. We implemented PFLDA in Python to compare and contrast with SLCE.
Apart from comparing classification result, we also check the sensitivity of
sparsity parameter of these two linear models. For benchmarking with ANN-based
methods, we picked the published results from the article Singh et al. (2020),
except for Stochastic Gates (Yamada et al., 2020), which we ran by ourselves
using authors code from GitHub. We followed the same experimental methodology
described in (Singh et al., 2020) for an apples-to-apples comparison. This
approach permitted a direct comparison of FsNet, Supervised CAE using the
authors’ best results. The experiment follows the following workflow:

  * •

Split each data sets into training and test partition using 50:50 ratio.

  * •

Run SLCE on the training set to extract top $K\in\\{10,50\\}$ features.

  * •

Using the top $K$ features train a one hidden layer ANN classifier with $500$
ReLU units to predict the test samples.

  * •

Repeat the classification 20 times and report average accuracy.

###  4.2 Result: SLCE vs PFLDA

Table 3 compares classification accuracies using the top features of PFLDA and
SLCE. We should note that in our experiments we found PFLDA to be very
sensitive to the choice of $\lambda$, which controls sparsity. For example,
setting $\lambda=0.021$ works for the model on ALLAML data, but appears to
behave spuriously for a value of 0.0215 returning no non-zero features, see
Figure 5. We also found that the PFLDA model’s performance depends
significantly on the data dimension becoming increasingly sensitive as the
ambient dimension grows. For example, we observed that the PFLDA model
abruptly sets the values of the weights of all the features to zero if
$\lambda$ exceeds a threhold as shown in Figure 6; in other words, no features
are selected.

Data set | Top 10 features | Top 50 features | All Features
---|---|---|---
PFLDA | SLCE | PFLDA | SLCE | ANN
ALLAML | $92.7$ | 94.1 | $95.8$ | 96.1 | $89.9$
Prostate_GE | $90.7$ | 91.2 | $88.3$ | 90.7 | $75.9$
GLIOMA | 59.9 | $58.8$ | $66.2$ | 69.2 | $70.3$
SMK_CAN | $66.6$ | 67.3 | $68.6$ | 70.9 | $65.7$
GLI_85 | 85.8 | $84.9$ | $85.3$ | 85.5 | $79.5$
CLL_SUB | $52.5$ | 62.9 | $52.3$ | 75.3 | $56.9$
Table 3: Comparison of mean classification accuracy of PFLDA, and SLCE
features on six real-world high-dimensional biological data sets. The
prediction rates are averaged over twenty runs on the test set. The result on
the last columns is computed using all the features from one hidden layer
neural network with 500 ReLU units.  Figure 5: Sparsity analysis of PFLDA on
ALLAML data using different values of $\lambda$. Figure 6: Sparsity analysis
of PFLDA on Prostate_GE data using different values of $\lambda$.

Due to this limitation of PFLDA, the model took significant time to find a
suitable $\lambda$. Returning to the comparison in Table 3, we see that
generally, the SLCE features produce better classification performance than
PFLDA. The top 50 SLCE features more accurately predict the test samples than
the top 50 PFLDA features in all the cases. In the ’Top 10 features’ group,
SLCE performed better in four out of six cases. These results establish the
performance advantage of our proposed method over PFLDA. The last column of
the table shows the accuracy with all the features using a single hidden layer
neural network classifier with 500 ReLU units. Notice that the classification
using top 50 SLCE features is better than all features, except for GLIOMA.

###  4.3 Result: SLCE vs ANN-Based Models

Table 4 presents the classification performance using the top features of
Feature Selection Network (FsNet), Supervised Concrete Autoencoder (SCAE),
Stochastic Gate (STG), and Sparse Linear Centroid-Encoder (SLCE). Note that
apart from SLCE, the other methods are neural network-based nonlinear models.
We also present the classification accuracy for each data set using all the
features under the column ”All Fea.” Generally, feature selection helps to
improve classification accuracies. From the category of top ten features,
FsNet produces the best result in three cases, followed by SLCE, with the best
accuracy in two cases. SCAE surpasses the other two models in GLI_85 data.
Notice Stochastic Gates doesn’t perform competitively in this category. On the
other hand, STG is the top-performing model in one case in the top 50 features
category, where SLCE outperforms the other models in the remaining five data
sets. Notice that the performance of FsNet doesn’t improve with more features
(e.g., GLIOMA); in fact, the accuracies drop in CLL_SUB, GLI_85, SMK_CAN. We
observe the same trend for SCAE in those three data sets. In contrast, SLCE
and STG benefit from more features. Considering all the twelve classification
tasks, our proposed method performed the best in seven cases, followed by
FsNet (three best results).

Data set | Top 10 features | Top 50 features | All
---|---|---|---
FsNet | SCAE | STG | SLCE | FsNet | SCAE | STG | SLCE | Fea.
ALLAML | $91.1$ | $83.3$ | $81.0$ | 94.1 | $92.2$ | $93.6$ | $88.5$ | 96.1 | $89.9$
Prostate_GE | $87.1$ | $83.5$ | $82.3$ | 91.2 | $87.8$ | $88.4$ | $85.0$ | 90.7 | $75.9$
GLIOMA | 62.4 | $58.4$ | $62.0$ | $58.8$ | $62.4$ | $60.4$ | 70.4 | $69.2$ | $70.3$
SMK_CAN | 69.5 | $68.0$ | $65.2$ | $63.1$ | $64.1$ | $66.7$ | $68.0$ | 70.9 | $65.7$
GLI_85 | $87.4$ | 88.4 | $72.2$ | $84.9$ | $79.5$ | $82.2$ | $81.0$ | 85.5 | $79.5$
CLL_SUB | 64.0 | $57.5$ | $54.4$ | $62.9$ | $58.2$ | $55.6$ | $63.2$ | 75.3 | $56.9$
Table 4: Comparison of mean classification accuracy of FsNet, SCAE, STG, and
SLCE features on six real-world high-dimensional biological data sets. The
prediction rates are averaged over twenty runs on the test set. Numbers for
FsNet and SCAE are being reported from (Singh et al., 2020). The result on the
last columns is computed using all the features from one hidden layer neural
network with 500 ReLU units.

We analyzed the STG’s ability to promote feature sparsity using ALLAML and
GLIOMA. We took three values of $\lambda$ to be 0.01, 0.1 and 1.0 to fit the
model on a training partition. After that we plotted the probability of the
gates in descending order. Figure 7 presents the sparsity plot. Notice the
model failed to promote feature sparsity on these two data sets. Er observed
the similar pattern for other data sets as well.

Figure 7: Sparsity analysis of Stochastic Gates on ALLAML and GLIOMA data
using three values of $\lambda$.

##  5 Discussion, Conclusion and Limitations

In this research work, we proposed a novel feature selection model, Sparse
Linear Centroid-Encoder (SLCE). We presented a convex training approach for
SLCE in two steps. Being linear, it is well suited for low sample size and
high-dimensional biological data sets. The model doesn’t require an exhaustive
search of network architecture and other training-related hyperparameters,
typical to a neural network-based model. The convex training approach
guarantees that each step has a global solution that is advantageous compared
to nonconvex methods. Unlike other linear and non-linear methods, e.g., Lasso,
and Sparse SVM, the model doesn’t use the response variable in data fitting;
instead, SLCE finds a linear transformation to reconstruct a sample as its
class centroid followed by a sparse training using $\ell_{1}$-norm. These
innovations make our model unique.

SLCE also enjoys the benefits of a single model for multiclass data—the
feature selection mechanism using a diagonal matrix work globally over all the
classes on the data set. This aspect of SLCE makes it attractive over other
linear techniques, e.g., Lasso and SSVM, where a binary feature selection
method is used as a multiclass method by one-against-one(OAO) or one-against-
all (OAA) class pairs. These models will suffer a combinatorial explosion when
the number of classes increases. Our model also has a significant benefit over
Penalized Fisher’s Discriminant Analysis for multiclass problems. PFLDA
induces sparsity in all directions making it hard to find a single set of
features necessary for all the FLDA directions. In contrast, our proposed
method searches for a global group of features in the feature selection stage.
Unlike PFLDA, our model is not sensitive to the sparsity-inducing parameter
$\lambda$.

We showed that the model successfully enforces sparsity on numerous biological
data sets using $\ell_{1}$-norm. The sparsity parameter controls the number of
selected features as expected. The visualization experiment with the Pancan
data shows how the model select discriminative feature that improves the PCA
embedding. We also found that the variables chosen over multiple runs have
many similarities regarding feature count and feature overlap. The
visualization with the Venn diagram and the Jaccard index supports the claim.

The extensive benchmarking with six biological data sets and five methods
provides evidence that the features of SLCE often produce better
generalization performance than other state-of-the-art models. Apart from the
linear method PFLDA, we compared SLCE with four ANN-based state-of-the-art
feature selection techniques and found that it produced the best result in six
cases out of twelve classification experiments. Unlike Stochastic Gates, we
have found that our model consistently sparsifies the input features for
biological datasets. The strong generalization performance, coupled with the
ability to sparsify input features, establishes the value of our model as a
linear feature detector.

SLCE, in its current form, maps a sample to its class centroid while applying
sparsity. The features may not be discriminatory if two class centroids are
close in the ambient space. Adopting a cost that also caters to separating the
classes may be beneficial. Our model may not be the right choice for the cases
where class centroids make little sense, e.g., natural images. The current
scope of the work doesn’t allow us to investigate other optimization
techniques, e.g., proximal gradient descent, trimmed Lasso, etc., which we
plan to explore in the future.

## References

  * Balın et al. (2019) Muhammed Fatih Balın, Abubakar Abid, and James Zou.  Concrete autoencoders: Differentiable feature selection and reconstruction.  In _International conference on machine learning_ , pages 444–453. PMLR, 2019.
  * Bertsimas et al. (2017) Dimitris Bertsimas, Martin S Copenhaver, and Rahul Mazumder.  The trimmed lasso: Sparsity and robustness.  _arXiv preprint arXiv:1708.04527_ , 2017.
  * Boyd and Vandenberghe (2004) Stephen Boyd and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge University Press, USA, 2004.  ISBN 0521833787.
  * Candes et al. (2008) Emmanuel J Candes, Michael B Wakin, and Stephen P Boyd.  Enhancing sparsity by reweighted l1 minimization.  _Journal of Fourier analysis and applications_ , 14(5):877–905, 2008.
  * Chepushtanova et al. (2014) Sofya Chepushtanova, Christopher Gittins, and Michael Kirby.  Band selection in hyperspectral imagery using sparse support vector machines.  In _Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery XX_ , volume 9088, page 90881F. International Society for Optics and Photonics, 2014.
  * Cortes and Vapnik (1995) Corinna Cortes and Vladimir Vapnik.  Support vector machine.  _Machine learning_ , 20(3):273–297, 1995.
  * Daubechies et al. (2010) Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, and C Sinan Gunturk.  Iteratively reweighted least squares minimization for sparse recovery.  _Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences_ , 63(1):1–38, 2010.
  * Fonti and Belitser (2017) Valeria Fonti and Eduard Belitser.  Feature selection using lasso.  _VU Amsterdam Research Paper in Business Analytics_ , 30:1–25, 2017.
  * Ghosh and Kirby (2022) Tomojit Ghosh and Michael Kirby.  Supervised dimensionality reduction and visualization using centroid-encoder.  _Journal of Machine Learning Research_ , 23(20):1–34, 2022.
  * Guyon et al. (2002) Isabelle Guyon, Jason Weston, Stephen Barnhill, and Vladimir Vapnik.  Gene selection for cancer classification using support vector machines.  _Machine learning_ , 46(1):389–422, 2002.
  * Han et al. (2018) Kai Han, Yunhe Wang, Chao Zhang, Chao Li, and Chao Xu.  Autoencoder inspired unsupervised feature selection.  In _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 2941–2945. IEEE, 2018.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Li et al. (2016) Yifeng Li, Chih-Yu Chen, and Wyeth W Wasserman.  Deep feature selection: theory and application to identify enhancers and promoters.  _Journal of Computational Biology_ , 23(5):322–336, 2016.
  * Lindenbaum and Steinerberger (2021) Ofir Lindenbaum and Stefan Steinerberger.  Randomly aggregated least squares for support recovery.  _Signal Processing_ , 180:107858, 2021.
  * Marafino et al. (2015) Ben J Marafino, W John Boscardin, and R Adams Dudley.  Efficient and sparse feature selection for biomedical text classification via the elastic net: Application to icu risk stratification from nursing notes.  _Journal of biomedical informatics_ , 54:114–120, 2015\.
  * Muthukrishnan and Rohini (2016) R Muthukrishnan and R Rohini.  Lasso: A feature selection technique in predictive modeling for machine learning.  In _2016 IEEE international conference on advances in computer applications (ICACA)_ , pages 18–20. IEEE, 2016.
  * O’Hara et al. (2013) Stephen O’Hara, Kun Wang, Richard A Slayden, Alan R Schenkel, Greg Huber, Corey S O’Hern, Mark D Shattuck, and Michael Kirby.  Iterative feature removal yields highly discriminative pathways.  _BMC genomics_ , 14(1):1–15, 2013.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  In _NIPS-W_ , 2017.
  * Scardapane et al. (2017) Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini.  Group sparse regularization for deep neural networks.  _Neurocomputing_ , 241:81–89, 2017.
  * Shen et al. (2011) Li Shen, Sungeun Kim, Yuan Qi, Mark Inlow, Shanker Swaminathan, Kwangsik Nho, Jing Wan, Shannon L Risacher, Leslie M Shaw, John Q Trojanowski, et al.  Identifying neuroimaging and proteomic biomarkers for mci and ad via the elastic net.  In _International Workshop on Multimodal Brain Image Analysis_ , pages 27–34. Springer, 2011.
  * Singh et al. (2020) Dinesh Singh, Héctor Climente-González, Mathis Petrovich, Eiryo Kawakami, and Makoto Yamada.  Fsnet: Feature selection network on high-dimensional biological data.  _arXiv preprint arXiv:2001.08322_ , 2020.
  * Sokolov et al. (2016) Artem Sokolov, Daniel E Carlin, Evan O Paull, Robert Baertsch, and Joshua M Stuart.  Pathway-based genomics prediction using generalized elastic net.  _PLoS computational biology_ , 12(3):e1004790, 2016.
  * Taherkhani et al. (2018) Aboozar Taherkhani, Georgina Cosma, and T Martin McGinnity.  Deep-fs: A feature selection algorithm for deep boltzmann machines.  _Neurocomputing_ , 322:22–37, 2018.
  * Tibshirani (1996) Robert Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 58(1):267–288, 1996.
  * Witten and Tibshirani (2011) Daniela M Witten and Robert Tibshirani.  Penalized classification using fisher’s linear discriminant.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 73(5):753–772, 2011.
  * Xie and Huang (2009) Huiliang Xie and Jian Huang.  Scad-penalized regression in high-dimensional partially linear models.  _The Annals of Statistics_ , 37(2):673–696, 2009\.
  * Yamada et al. (2020) Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger.  Feature selection using stochastic gates.  In _International Conference on Machine Learning_ , pages 10648–10659. PMLR, 2020.


Dahoon<EMAIL_ADDRESS>Kon-Woo<EMAIL_ADDRESS>Sunghoon
<EMAIL_ADDRESS>Jaeha<EMAIL_ADDRESS>Daegu Gyeongbuk
Institute of Science and Technology (DGIST),
Daegu, Korea Hongik University,
Seoul, Korea Zero-Data Based Repeated Bit Flip Attack

# ZeBRA: Precisely Destroying Neural Networks with Zero-Data Based Repeated
Bit Flip Attack

###### Abstract

In this paper, we present Zero-data Based Repeated bit flip Attack (ZeBRA)
that precisely destroys deep neural networks (DNNs) by synthesizing its own
attack datasets. Many prior works on adversarial weight attack require not
only the weight parameters, but also the training or test dataset in searching
vulnerable bits to be attacked. We propose to synthesize the attack dataset,
named distilled target data, by utilizing the statistics of batch
normalization layers in the victim DNN model. Equipped with the distilled
target data, our ZeBRA algorithm can search vulnerable bits in the model
without accessing training or test dataset. Thus, our approach makes the
adversarial weight attack more fatal to the security of DNNs. Our experimental
results show that 2.0$\times$ (CIFAR-10) and 1.6$\times$ (ImageNet) less
number of bit flips are required on average to destroy DNNs compared to the
previous attack method. Our code is available at
https://github.com/pdh930105/ZeBRA.

##  1 Introduction

Recent advances in deep neural networks (DNNs) have led the proliferation of
DNN-assisted applications such as computer vision, machine translation,
recommendation system, playing games, and robotics, to name a few [Redmon et
al.(2016)Redmon, Divvala, Girshick, and Farhadi, Brown et al.(2020)Brown,
Mann, Ryder, Subbiah, Kaplan, Dhariwal, Neelakantan, Shyam, Sastry, Askell,
Agarwal, Herbert-Voss, Krueger, Henighan, Child, Ramesh, Ziegler, Wu, Winter,
Hesse, Chen, Sigler, Litwin, Gray, Chess, Clark, Berner, McCandlish, Radford,
Sutskever, and Amodei, Liu et al.(2020)Liu, Duh, Liu, and Gao, Covington et
al.(2016)Covington, Adams, and Sargin, Mnih et al.(2013)Mnih, Kavukcuoglu,
Silver, Graves, Antonoglou, Wierstra, and Riedmiller, Huang et al.(2019)Huang,
Zambelli, Kay, Martins, Tassa, Pilarski, and Hadsell]. Moreover, as safety-
critical applications are widely adopting deep learning, i.e., medical imaging
[Kaissis et al.(2020)Kaissis, Makowski, Ruckert, and Braren], self-driving
cars [Grigorescu et al.(2020)Grigorescu, Trasnea, Cocias, and Macesanu], and
intelligent robots [Melis et al.(2017)Melis, Demontis, Biggio, Brown, Fumera,
and Roli], the robustness of DNN models is getting extremely important. For
instance, an adversary can alter the behavior of the DNN model deployed in a
self-driving car to misclassify traffic signs [Morgulis et al.(2019)Morgulis,
Kreines, Mendelowitz, and Weisglass]. Thus, deep learning researchers need to
carefully identify and understand the unexpected blind spots of DNNs. There
are two different ways of attacking the DNN model: i) adding imperceptible
noise to input data (adversarial examples) and ii) moving decision boundaries
by changing the weight parameters (adversarial weight attack). Adversarial
examples are trained/optimized to move away from the correct labels for
classification tasks [Szegedy et al.(2014)Szegedy, Zaremba, Sutskever, Bruna,
Erhan, Goodfellow, and Fergus]. These examples have the attacking ability even
after they are printed and photographed with a smartphone [Kurakin et
al.(2017)Kurakin, Goodfellow, and Bengio] or fed into other DNNs with
different parameters and/or architectures [Szegedy et al.(2014)Szegedy,
Zaremba, Sutskever, Bruna, Erhan, Goodfellow, and Fergus]. On the contrary,
the adversarial weight attack changes the values of weight parameters by
flipping bits of the DNN model [Rakin et al.(2019)Rakin, He, and Fan, Rakin et
al.(2021)Rakin, He, Li, Yao, Chakrabarti, and Fan]. The prior work, named bit
flip attack (BFA), presents an efficient way of finding vulnerable bits in the
DNN model via iterative bit search (Figure 1).

To perform the iterative search for finding bits to be flipped, the BFA
requires DNN model parameters, i.e., weight ($\theta$) and batch normalization
parameters ($\mu$, $\sigma$), and the training or test dataset. An adversary
may have the read privilege of the model parameters or can perform model
extraction techniques as demonstrated in [Jagielski et al.(2020)Jagielski,
Carlini, Berthelot, Kurakin, and Papernot, Juuti et al.(2019)Juuti, Szyller,
Marchal, and Asokan]. However, it may not be possible to access the training
dataset as the DNN model is trained at cloud servers. In addition, the test
dataset may be collected in real-time and it becomes impossible to get enough
amount of data for the precise attack. As discussed in Sec. 4.2, the attack
performance of the BFA varies a lot by how the data is sampled. To overcome
such limitations, we propose Zero-data Based Repeated bit flip Attack (ZeBRA
in Figure 1).

Figure 1: The overview of the proposed attack method (ZeBRA). The difference
between the prior work [Rakin et al.(2019)Rakin, He, and Fan] and ZeBRA is the
required access to the actual dataset for the attack.

##  2 Related Work

###  2.1 Adversarial Attacks on DNN Models

Most of the studies on attacking deep learning models are based on generating
adversarial examples. Adversarial examples are inputs that are extremely
difficult to distinguish by human eyes but successfully fool the DNN models.
There are many prior work that try to train good adversarial examples with
imperceptible perturbations from the original images [Goodfellow et
al.(2015)Goodfellow, Shlens, and Szegedy, Kurakin et al.(2017)Kurakin,
Goodfellow, and Bengio, Moosavi-Dezfooli et al.(2016)Moosavi-Dezfooli, Fawzi,
and Frossard, Szegedy et al.(2014)Szegedy, Zaremba, Sutskever, Bruna, Erhan,
Goodfellow, and Fergus]. Rather than solving an optimization problem, authors
in [Baluja and Fischer(2017)] propose a neural network that transforms an
input image to an adversarial example. Recently, adversarial weight attack has
been emerged as a new domain of the DNN attack method [Rakin et
al.(2019)Rakin, He, and Fan, Rakin et al.(2021)Rakin, He, Li, Yao,
Chakrabarti, and Fan, Zhao et al.(2019)Zhao, Wang, Gongye, Wang, Fei, and
Lin]. The BFA presents an iterative algorithm that searches for bits in the
parameter space that increase the DNN loss the most [Rakin et al.(2019)Rakin,
He, and Fan]. With multiple iterations, the BFA successfully destroys the DNN
model and makes it a random predictor. In the BFA, however, the adversary
needs to have a privilege of accessing weights of the victim DNN model as well
as the training or test dataset to perform the iterative bit search [Rakin et
al.(2019)Rakin, He, and Fan]. Moreover, the same research group demonstrated a
targeted BFA (T-BFA) to make the DNN model output the same classification
result on any inputs [Rakin et al.(2021)Rakin, He, Li, Yao, Chakrabarti, and
Fan]. Still, it suffers from the need of the actual dataset in searching bits
to be flipped.

###  2.2 Flipping Bits by Physical Attack

To make the adversarial weight attack feasible, there has to be a way to
physically change the weight parameters stored in the memory system. Recently,
several memory fault injection techniques are developed that threaten the the
integrity of DNN models [Agoyan et al.(2010)Agoyan, Dutertre, Mirbaha,
Naccache, Ribotta, and Tria, Roscian et al.(2013)Roscian, Sarafianos,
Dutertre, and Tria, Kim et al.(2014)Kim, Daly, Kim, Fallin, Lee, Lee,
Wilkerson, Lai, and Mutlu]. Especially, repeated accesses to a specific row of
the main memory, i.e., dynamic RAM (DRAM), effectively cause bit flips in
neighboring rows at predictable bit locations [Kim et al.(2014)Kim, Daly, Kim,
Fallin, Lee, Lee, Wilkerson, Lai, and Mutlu]. This cell-level attack is widely
known as the row-hammer and its impact gets more severe as the memory
technology scales down for higher cell density [Mutlu and Kim(2019)]. It is
even possible to gain kernel privileges on real systems by user-level programs
as demonstrated by Google [Seaborn and Dullien(2016)]. Moreover, a mobile
system with an embedded GPU can be controlled by the adversary using the row-
hammer attack [Frigo et al.(2018)Frigo, Giuffrida, Bos, and Razavi]. As the
on-chip memory, i.e., static RAM (SRAM), of a mobile device has a limited
capacity ($<$ 2MB), the weight parameters are stored in the DRAM making them
vulnerable to the row-hammer attack. In this work, we provide a simple yet
effective method of generating synthetic data that can be utilized for the
precise bit flip attack.

##  3 ZeBRA: Adversarial Weight Attack with Distilled Target Data

In most cases, the adversary may not have the privilege of accessing the
training dataset or a DNN could be trained over the cloud. In addition, the
test dataset may be collected in real-time by associated sensors, e.g.,
cameras in self-driving cars, or may not be easily accessed due to privacy
issues, e.g., personal health records or encrypted data. In any of these
scenarios, it is impossible to perform the BFA on the pre-trained DNN model.
Note that the BFA requires to compute the loss by feeding in the training or
test dataset to identify the most vulnerable bits. In this work, we propose to
repeatedly generate synthetic data, named distilled target data, that follows
the statistics of the pre-trained model, i.e., the mean and the standard
deviation at each batch normalization layer. With the use of distilled target
data, the bit flip attack becomes more precise compared to the attack using a
limited set of training dataset (refer to Sec. 4.2).

###  3.1 Distilled Target Data

To perform the iterative bit search, we extract the synthetic data from the
DNN model itself (i.e., distilled data). The distilled data has been presented
in [Cai et al.(2020)Cai, Yao, Dong, Gholami, Mahoney, and Keutzer] to analyze
the impact of quantization on the DNN accuracy. However, the previous
distilled data is not associated with any target labels as it is simply used
to check the KL divergence between the model output without quantization and
the one with quantization. To analyze the bit sensitivity of the DNN model
during the iterative bit search (refer to Sec. 3.2), the synthetic data should
have two properties: i) accurately estimate the DNN loss (cross entropy loss)
and ii) accurately estimate the weight gradients (distilled loss). Thus, we
assign target labels to the distilled data while generating them in the
proposed distilled target data. According to our analysis, the distilled data
of a given class behaves similarly to the actual training dataset with the
same label111More details are presented in Section B of the supplementary
material.. Moreover, we introduce a hyper-parameter, i.e. total loss bound
$\epsilon_{loss}$, that improves the attack performance.

In the ZeBRA, we first generate random input data
$\mathbf{x}^{d}\in\mathbb{R}^{C\times W\times H}$ in a range of $[-1,1]$, and
a random target label $\hat{y}=\\{0,...,N_{C}-1\\}$. The $C$, $W$, $H$ and
$N_{C}$ represent the number of input channels, input width, input height and
number of classes, respectively. We mini-batch the input $\mathbf{x}^{d}$ and
obtain the one-hot encoded target label
$\hat{\mathbf{y}}\in\mathbb{R}^{N_{C}}$ of the class $\hat{y}$ with the batch
size $B_{distill}$. Given the mini-batch input data
$\mathbf{X}^{d}\in\mathbb{R}^{B_{distill}\times C\times W\times H}$ and one-
hot encoded target labels $\hat{\mathbf{Y}}\in\mathbb{R}^{B_{distill}\times
N_{C}}$, a cross entropy loss is computed by

$\begin{split}\mathcal{L}_{CE}=\mathcal{L}(f(\theta;\mathbf{X}^{d}),\hat{\mathbf{Y}})=-\sum_{i=1}^{B_{distill}}\hat{\mathbf{Y}}_{i}\cdot\log(\mathbf{Y}_{i})^{\intercal},\
\ \mathbf{Y}=f(\theta;\mathbf{X}^{d}),\end{split}$ (1)

where $f(\theta;\mathbf{X}^{d})$ is the output probability (typically, after
the softmax layer) computed by running the DNN model with weight parameters
$\theta\in\mathbb{R}^{n}$ for the given input data $\mathbf{X}^{d}$. As
another objective in generating the distilled target data is to resemble the
statistics of the DNN model, a distilled loss is used as additional loss term.
The distilled loss is defined as

$\mathcal{L}_{Distill}=\sum_{i=0}^{L-1}||\widetilde{\mu_{i}}^{d}-\mu_{i}||_{2}^{2}+||\widetilde{\sigma_{i}}^{d}-\sigma_{i}||_{2}^{2},$
(2)

where $\widetilde{\mu_{i}}^{d}$ and $\widetilde{\sigma_{i}}^{d}$ are the
average and standard deviation of feature maps at layer $i$ when
$\mathbf{X}^{d}$ is fed into the DNN model with ‘$L$’ layers. The $\mu_{i}$
and $\sigma_{i}$ are the stored mean and standard deviation for the $i$th
batch normalization layer. Then, the total loss is defined as

$\mathcal{L}_{total}=\lambda_{CE}\cdot\mathcal{L}_{CE}+\lambda_{Distill}\cdot\mathcal{L}_{Distill}.$
(3)

The generation of the distilled target data now becomes the optimization
problem of finding $\mathbf{X}^{d}$ that minimizes $\mathcal{L}_{total}$. A
typical gradient descent is used to iteratively update $\mathbf{X}^{d}$ until
it reaches the total loss bound $\epsilon_{loss}$. The $\lambda$s are used to
control the strength of convergence to the model statistics and/or the target
label. This distillation process, i.e., distill_target_data() in line 14 of
Alg. 1, is repeated until it generates $B_{attack}$ samples forming an attack
batch $\mathbf{X}_{attack}^{d}$ to be used during the iterative bit search.
Note that $B_{attack}$ is a multiple of $B_{distill}$. Here, the definition of
an attack batch is a set of data points used for selecting bits to be flipped
in the ZeBRA.

###  3.2 Workflow of ZeBRA Algorithm

The main advantage of the distilled target data is that we no longer need
either the training or test dataset for the adversarial weight attack. More
importantly, we can easily generate a new attack batch for the bit search
process resulting in a more precise DNN weight attack. Alg. 1 summarizes the
overall process of the ZeBRA in selecting the well performing attack batch,
i.e., a set of distilled target data, and searching the vulnerable bits to be
flipped. It consists of two main parts: i) generating the distilled target
data for the bit search process and ii) iteratively searching bits to be
flipped.

The only required data for the ZeBRA is DNN model parameters, i.e., weight
($\theta$) and batch normalization parameters ($\mathbf{\mu}$,
$\mathbf{\sigma}$). Then, we set the target accuracy ($A_{target}$) and the
maximum number of bit flips to allow ($N_{b}^{\text{max}}$). The algorithm
generates a new set of distilled target data, $\mathbf{X}_{attack}^{d}$ with
size $B_{attack}$, if the attack fails to reach $A_{target}$ with bit flips
less than $N_{b}^{\text{max}}$. As the ZeBRA can generate distilled target
data multiple times, we repeatedly generate the data until the bit flip attack
satisfies the attack performance. For the evaluation of the attack
performance, we prepare the distilled target data just for the validation,
called distilled validation data, prior to line 7 in Alg. 1. More details on
the generation of distilled validation data, $\mathbf{X}_{valid}^{d}$, will be
discussed in Sec. 4.3.

1 Input: Model parameters $\theta$, $\mathbf{\mu}$, $\mathbf{\sigma}$,

2 Target accuracy $A_{target}$,

3 Attack/distill batch size $B_{attack}$, $B_{distill}$,

4 Maximum # of bit flips $N_{b}^{\text{max}}$

5 Output: Modified weight parameters $\theta_{attack}$,

6 Required # of bit flips $N_{attack}$

7while  _$A_{target}$ $<$ $A_{attack}$_ do

8 % 1\. Generation of distilled target data

9 $\mathbf{X}_{attack}^{d}$ = [], $\mathbf{\hat{Y}}_{attack}$ = [] ;

10 $T\leftarrow B_{attack}/B_{distill}$ ;

11 for  _$i\leftarrow 1$ to $T$_ do

12 Initialize input data: $\mathbf{X}^{d}\sim
U(-1,1)\in\mathbb{R}^{B_{distill}\times C\times W\times H}$

13 Initialize one-hot encoded target labels:
$\mathbf{\hat{Y}}\in\mathbb{R}^{B_{distill}\times N_{C}}$

14 $\mathbf{X}_{attack}^{d}\leftarrow$
[$\mathbf{X}_{attack}^{d}|$distill_target _data ($\mathbf{X}^{d}$,
$\mathbf{\hat{Y}}$, $\theta$, $\mathbf{\mu}$, $\mathbf{\sigma}$,
$\epsilon_{loss}$)] ;

15
$\mathbf{\hat{Y}}_{attack}\leftarrow[\mathbf{\hat{Y}}_{attack}|\mathbf{\hat{Y}}]$

16 % 2\. Iterative bit search

17 $N_{attack}\leftarrow N_{b}^{\text{max}}$;

18 for  _$k\leftarrow 1$ to $N_{b}^{\text{max}}$_ do

19 $\theta_{attack}\leftarrow$layerwise_bit_search($\theta$,
$\mathbf{X}_{attack}^{d}$, $\hat{\mathbf{Y}}_{attack}$, $\mathbf{\mu}$,
$\mathbf{\sigma}$) ;

20 $A_{attack}\leftarrow f(\theta_{attack};\mathbf{X}_{valid}^{d})$ ;

21 $\theta\leftarrow\theta_{attack}$ ;

22 if  _$A_{target}$ $>$ $A_{attack}$_ then

23 $N_{attack}\leftarrow k$;

24 break;

25

26

27

return $N_{attack}$, $\theta_{attack}$

Algorithm 1 ZeBRA Algorithm

After the attack data $\mathbf{X}_{attack}^{d}$ is obtained, we can perform
the iterative bit search to identify the most vulnerable bit at each
iteration. Here, the vulnerable bit ‘$b_{i,l}$’ at layer $l$ has the largest
$\partial\mathcal{L}/{\partial b_{i,l}}$ where $\mathcal{L}(\cdot)$ is the
cross entropy loss of a given DNN model in Eq. (1). Thus, the synthesized
attack data should accurately estimate the DNN loss $\mathcal{L}$. This is the
intuition behind considering $\mathcal{L}_{CE}$ in Eq. (3) when forging the
attack data. In addition, the bit sensitivity $\partial\mathcal{L}/{\partial
b_{i,l}}$ can be computed by
$(\partial\mathcal{L}/{\partial\theta_{l}})\cdot(\partial\theta_{l}/{\partial
b_{i,l}})$. Thus, accurately estimating the weight gradients, i.e.,
$\partial\mathcal{L}/{\partial\theta_{l}}$, is important in finding vulnerable
bits. Since computing $\partial\mathcal{L}/{\partial\theta_{l}}$ involves
multiplications between the backpropagated gradients and input feature maps,
the attack data should approximate the statistics of feature maps at each
layer. This is why we consider $\mathcal{L}_{Distill}$ in Eq. (3) when
generating the attack data.

The layerwise_bit_search() in line 19 of Alg. 1 is identical to the one
presented in [Rakin et al.(2019)Rakin, He, and Fan]. We briefly explain the
process here for the sake of completeness. At the $k$-th iteration, as a first
step, the most vulnerable bit $b_{l}^{k}$ at layer $l$ is exclusively selected
and the inference loss $\mathcal{L}_{l}^{k}$ is computed with the bit
$b_{l}^{k}$ flipped (in-layer search). The loss $\mathcal{L}_{l}^{k}$ is
defined as

$\mathcal{L}_{l}^{k}=\mathcal{L}(f(\theta_{attack}^{k};\mathbf{X}_{attack}^{d}),\hat{\mathbf{Y}}),$
(4)

where $\theta_{attack}^{k}$ is the weight parameter obtained by flipping the
bit $b_{l}^{k}$ from $\theta_{attack}^{k-1}$. As a second step, we identify
the $j$-th layer with the maximum loss $\mathcal{L}_{j}^{k}$ and perform the
permanent bit flip at $b_{j}^{k}$ (cross-layer search). As the bit $b_{j}^{k}$
is permanently flipped, it is kept flipped at subsequent iterations. At each
bit flip attack being executed, the post-attack accuracy ($A_{attack}$) is
evaluated by using distilled validation data $\mathbf{X}_{valid}^{d}$. If
$A_{attack}$ is lower than $A_{target}$, the bit search process is terminated.
At last, the modified weight parameters and the number of bit flips are
returned. If the attack fails, the ZeBRA repeats generating the new attack
batch (thus, named Zero-data Based Repeated bit flip Attack).

##  4 Attack Performance of ZeBRA

In this section, we compare the attack performance of ZeBRA to BFA on various
DNN models222The code for the ZeBRA will be available at
https://github.com/pdh930105/ZeBRA.. The novelty of the proposed ZeBRA
algorithm is in that we do not need either training or test dataset, unlike
the BFA. To allow the BFA to work, we assume that the BFA can sample a mini-
batch from the actual dataset, e.g., $B_{attack}=64$, for the iterative bit
search.

###  4.1 Experimental Setup

Datasets and DNN Models: As test benchmarks, we select the two well-known
image classification datasets: CIFAR-10 [Krizhevsky et al.(2010)Krizhevsky,
Nair, and Hinton] and ImageNet [Krizhevsky et al.(2012)Krizhevsky, Sutskever,
and Hinton]. The CIFAR-10 has 10 different object classes while ImageNet has
1,000 different classes. Each dataset is divided into training, validation and
test datasets. The BFA (baseline) in our experiments samples a mini-batch from
the training dataset for the bit search process (it may not be possible in the
real-world scenario). Note that the ZeBRA generates its own attack batches
prior to the bit search process. The runtime overhead of generating the attack
data is discussed in Sec. 4.4. For CIFAR-10 dataset, four different ResNet
models (ResNet-20/32/44/56) are used for evaluating the attack performance of
the ZeBRA [He et al.(2015)He, Zhang, Ren, and Sun]. For ImageNet dataset,
VGG11, Inception-v3, ResNet-18/34/50 and MobileNetV2 are used for the
evaluation [Simonyan and Zisserman(2014), Szegedy et al.(2015)Szegedy,
Vanhoucke, Ioffe, Shlens, and Wojna, He et al.(2015)He, Zhang, Ren, and Sun,
Sandler et al.(2019)Sandler, Howard, Zhu, Zhmoginov, and Chen]. All the
experiments are conducted on NVIDIA GeForce RTX 2080Ti (11GB memory).

Selection of ZeBRA Hyper-parameters: There are several hyper-parameters to be
determined to perform an effective bit flip attack with the ZeBRA. They are
mini-batch size $B_{distill}$, coefficients $\lambda_{CE}$ and
$\lambda_{Distill}$ in Eq. (3), and total loss bound $\epsilon_{loss}$. We fix
$B_{attack}$ of the ZeBRA to 64 that matches the mini-batch size of the BFA.
To verify the sole impact of the distilled target data
$\mathbf{X}_{attack}^{d}$ and its associated hyper-parameters, the distilled
validation data $\mathbf{X}_{valid}^{d}$ in line 20 of Alg. 1 is replaced with
the actual validation dataset $\mathbf{X}_{valid}$ of CIFAR-10 or ImageNet.
The impact of using the distilled validation data instead of the actual
validation dataset will be discussed in Sec. 4.3.

To select the optimal hyper-parameters for generating distilled target data,
we tested different hyper-parameters on ResNet-20 with CIFAR-10 dataset. The
ResNet-20 model is quantized to 8bit333The quantized DNN model is more robust
to bit flips than the one in floating-point representation [Liu et
al.(2017)Liu, Wei, Luo, and Xu, Rakin et al.(2019)Rakin, He, and Fan].. Tests
on other network architectures, quantization levels (6bit and 4bit), or
dataset (ImageNet) show similar trends as shown in Table 1. We generated 40
different sets of $\mathbf{X}_{attack}^{d}$ for each hyper-parameter
combination {$\lambda_{CE}$, $\lambda_{Distill}$, $\epsilon_{loss}$} and
obtained the minimum number of bit flips to achieve $A_{target}=10$% (i.e.,
making a random predictor). As a result, we select $B_{distill}=16$,
$B_{attack}=64$, $\lambda_{CE}=0.2$, $\lambda_{Distill}=0.1$, and
$\epsilon_{loss}=10$ when generating $\mathbf{X}_{attack}^{d}$ for the rest of
our experiments. Note that the ZeBRA fails to attack the model with random
data ($\lambda_{CE}=0$ and $\lambda_{Distill}=0$) proving that the distilled
target data is definitely required to perform an effective attack.

Table 1: The attack performance of ZeBRA at different hyper-parameter
combinations of ($\lambda_{CE}$, $\lambda_{Distill}$, $\epsilon_{loss}$) on
ResNet-20 with CIFAR-10 dataset: The ZeBRA outputs the minimum number of bit
flips, i.e., only 8 bits, with $\lambda_{CE}=0.2$, $\lambda_{Distill}=0.1$,
and $\epsilon_{loss}=10$

ResNet-20 (CIFAR-10) |  $\lambda_{CE}$ = 0 |  $\lambda_{CE}$ = 0.1 |  $\lambda_{CE}$ = 0.2 |  $\lambda_{CE}$ = 0.5 |  $\lambda_{CE}$ = 1.0
---|---|---|---|---|---
$\epsilon_{loss}$ = 1 | 10 | 100 | 1 | 10 | 100 | 1 | 10 | 100 | 1 | 10 | 100 | 1 | 10 | 100
Bit Flips (Best / Mean) |  $\lambda_{Distill}$ = 0 | 40 / 40 | 40 / 40 | 40 / 40 | 40 / 40 | 40 / 40 | 40 / 40 | 18 / 25 | 40 / 40 | 40 / 40 | 8 / 22 | 40 / 40 | 40 / 40 | 8 / 23 | 40 / 40 | 40 / 40
$\lambda_{Distill}$ = 0.1 | 13 / 31 | 10 / 13 | 40 / 40 | 15 / 29 | 9 / 11 | 40 / 40 | 17 / 30 | 8 / 12 | 40 / 40 | 15 / 28 | 10 / 28 | 40 / 40 | 13 / 27 | 12 / 26 | 40 / 40
$\lambda_{Distill}$ = 0.2 | 15 / 34 | 9 / 24 | 40 / 40 | 17 / 33 | 16 / 24 | 40 / 40 | 24 / 36 | 15 / 26 | 40 / 40 | 14 / 35 | 21 / 29 | 40 / 40 | 10 / 35 | 23 / 30 | 40 / 40
$\lambda_{Distill}$ = 0.5 | 21 /38 | 18 / 30 | 40 / 40 | 17 / 37 | 15 / 28 | 40 / 40 | 26 / 38 | 14 / 27 | 40 / 40 | 21 / 37 | 9 / 27 | 40 / 40 | 19 / 37 | 15 / 26 | 28 / 39
$\lambda_{Distill}$ = 1.0 | 20 / 37 | 16 / 30 | 10 / 15 | 19 / 33 | 13 / 31 | 11 / 12 | 22 / 37 | 16 / 33 | 10 / 13 | 22 / 37 | 14 / 29 | 10 / 11 | 17 / 35 | 13 / 29 | 9 / 11

###  4.2 Comparison to BFA

####  4.2.1 Comparison on CIFAR-10

A random predictor has classification accuracy of 10%, due to CIFAR-10 dataset
has 10 classes, which is target accuracy for each attack method. Four
different ResNet models (ResNet-20/32/44/56) are selected as benchmarks to
evaluate the attack performance. The ResNet models at various quatization
levels (8bit, 6bit and 4bit) are tested. Table 2 summarizes the attack
performance of the BFA and the proposed ZeBRA on CIFAR-10 dataset.

The both BFA and ZeBRA are performed 50 times with different seed values.
Again, it is challenging for the BFA to obtain 50 different mini-batches from
the actual dataset while the ZeBRA can easily self-generate any number of
mini-batches. As our experimental result shows it is not guaranteed for the
BFA to obtain the minimum number of bit flips, i.e., 8.58 bits on average,
without accessing the large amount of training dataset. The mean and standard
deviation of the required number of bit flips to fully destroy a given DNN
model are large for the BFA: 30.3/15.4, 23.5/12.2, 30.8/13.3, and 22.4/10.5
for ResNet-20, ResNet-32, ResNet-44, and ResNet-56 (8bit), respectively.
Similar statistics are observed for 6bit and 4bit quantized models as provided
in Table 2. In addition, 26% of trials on average failed in attacking the DNN
model ($N_{b}^{\text{max}}$ is set to 50). This implies that the selection of
a mini-batch for the BFA significantly impacts the attack performance.

On the contrary, the ZeBRA has freedom in generating the attack dataset. The
attack performance for 50 trials of the ZeBRA is summarized in Table 2. With
the ZeBRA, the minimum number of bit flips to completely destroy the DNN model
is 9.50 bits on average (0.92 bits higher than the BFA). However, in the
ZeBRA, it is guaranteed to achieve the minimum number of bit flips as we can
examine the model as much as we can before physically attacking the DNN model,
e.g., via row-hammering. In addition, none of the trials failed which implies
that the ZeBRA is more reliable. The mean and standard deviation of the
required number of bit flips are 2.0$\times$ and 8.3$\times$ smaller than the
BFA on average.

Table 2: The comparison of the attack performance between the BFA and the
proposed ZeBRA on CIFAR-10 dataset

Model |  Quant. Level ($N_{Q}$) |  Original Accuracy (Top-1 [%]) | BFA | ZeBRA
---|---|---|---|---
| Bit Flips
---
(Best)
| Bit Flips
---
(Worst)
| Mean
---
/ Stdev
| Avg. Accuracy
---
After Attack
| Bit Flips
---
(Best)
| Bit Flips
---
(Worst)
| Mean
---
/ Stdev
| Avg. Accuracy
---
After Attack
ResNet-20 | 8bit | 92.41 | 8 | 50 (fail) | 30.3 / 15.4 | 10.05 | 8 | 11 | 10.5 / 0.9 | 10.00
6bit | 92.18 | 7 | 50 (fail) | 24.6 / 17.6 | 10.07 | 9 | 10 | 9.8 / 0.4 | 10.00
4bit | 87.59 | 6 | 50 (fail) | 16.6 / 11.1 | 9.99 | 9 | 15 | 14.4 / 1.6 | 9.77
ResNet-32 | 8bit | 92.77 | 7 | 50 (fail) | 23.5 / 12.2 | 10.08 | 9 | 13 | 10.6 / 0.8 | 10.00
6bit | 92.55 | 10 | 50 (fail) | 22.4 / 10.2 | 10.05 | 9 | 13 | 9.8 / 1.2 | 10.00
4bit | 92.20 | 10 | 50 (fail) | 18.7 / 9.6 | 10.01 | 10 | 19 | 14.5 / 3.0 | 9.96
ResNet-44 | 8bit | 93.34 | 11 | 50 (fail) | 30.8 / 13.3 | 10.07 | 14 | 20 | 18.5 / 1.4 | 10.00
6bit | 93.08 | 9 | 50 (fail) | 26.2 / 12.2 | 10.04 | 11 | 18 | 14.9 / 1.9 | 10.00
4bit | 87.83 | 9 | 50 (fail) | 26.7 / 14.7 | 10.08 | 9 | 16 | 13.5 / 1.5 | 10.00
ResNet-56 | 8bit | 93.50 | 8 | 50 (fail) | 22.4 / 10.5 | 10.01 | 9 | 18 | 13.4 / 2.3 | 10.00
6bit | 93.32 | 10 | 50 (fail) | 27.2 / 13.2 | 10.01 | 7 | 17 | 13.2 / 1.9 | 10.00
4bit | 89.61 | 8 | 50 (fail) | 46.0 / 11.1 | 10.70 | 10 | 16 | 13.8 / 1.3 | 10.00

####  4.2.2 Comparison on ImageNet

To generalize the effectiveness of the ZeBRA, we also compared the attack
performance on ImageNet dataset. Note that a random predictor for ImageNet has
classification accuracy of 0.1% (Top-1) and we set the target accuracy to 0.2%
which is identical to the prior work [Rakin et al.(2019)Rakin, He, and Fan].
For the evaluation, we select VGG11, Inception-v3, three different ResNet
models (ResNet-18/34/50), and a mobile-friendly DNN model (MobileNetV2),
quantized at 8bit. Table 3 summarizes the attack performance of the BFA and
the ZeBRA on ImageNet dataset.

Similarly, 50 trials with different seeds are performed for both the BFA and
ZeBRA. As our experimental results show, DNN models trained on ImageNet are
more susceptible to the adversarial weight attack. It requires less than 6
bits to completely destroy the DNN model. We conjecture that decision
boundaries are close to each other for the DNN model on ImageNet as it needs
to partition the feature space into 1,000 different regions. Thus, a slight
modification to decision boundaries significantly impacts the accuracy. The
minimum number of bit flips to destroy the DNN model is 3.83 bits for BFA and
4 bits for ZeBRA on average. Note that the ZeBRA guarantees finding the
minimum number of bit flips without accessing the actual dataset. The mean and
standard deviation of the required number of bit flips are 1.6$\times$ and
3.5$\times$ smaller than the BFA on average (thus, ZeBRA is more precise).

Table 3: The comparison of the attack performance between the BFA and the
proposed ZeBRA on ImageNet dataset

Model | Accuracy |  Original Accuracy [%] | BFA | ZeBRA
---|---|---|---|---
| Bit Flips
---
(Best)
| Bit Flips
---
(Worst)
| Mean
---
/ Stdev
| Avg. Accuracy
---
After Attack
| Bit Flips
---
(Best)
| Bit Flips
---
(Worst)
| Mean
---
/ Stdev
| Avg. Accuracy
---
After Attack
VGG11 | Top-1 | 70.24 | 9 | 35 |  16.48 / 6.46 | 0.18 | 6 | 10 |  8.48 / 0.96 | 0.15
Top-5 | 89.68 | 0.77 | 0.71
Inception-v3 | Top-1 | 76.85 | 2 | 6 |  3.21 / 1.06 | 0.12 | 2 | 4 |  2.5 / 0.87 | 0.15
Top-5 | 93.33 | 3.45 | 1.73
ResNet-18 | Top-1 | 69.50 | 5 | 15 |  8.12 / 1.76 | 0.15 | 6 | 9 |  7.21 / 1.35 | 0.15
Top-5 | 88.97 | 1.52 | 1.69
ResNet-34 | Top-1 | 73.13 | 4 | 17 |  9.53 / 2.81 | 0.15 | 5 | 6 |  5.07 / 0.26 | 0.14
Top-5 | 91.38 | 1.87 | 2.56
ResNet-50 | Top-1 | 75.84 | 2 | 30 |  8.42 / 3.32 | 0.14 | 4 | 6 |  4.70 / 0.92 | 0.15
Top-5 | 92.81 | 0.80 | 1.05
MobileNetV2 | Top-1 | 71.14 | 1 | 8 |  2.65 / 0.031 | 0.14 | 1 | 2 |  1.68 / 0.014 | 0.12
Top-5 | 90.01 | 0.66 | 0.61

A noticeable result is that even 1 bit is enough to change MobileNetV2 into a
random predictor. Figure 3 shows the attention maps at several convolution
layers in MobileNetV2 extracted by Grad-CAM [Selvaraju et al.(2017)Selvaraju,
Cogswell, Das, Vedantam, Parikh, and Batra]. A significant weight change in
the depthwise convolution layer makes a single output channel to have large
values (either positive or negative). Mostly, mobile-friendly DNNs have a
depthwise convolution layer followed by a pointwise (1$\times$1) convolution
layer to reduce the number of computations444More experimental results on
mobile-friendly DNNs are presented in Section C of the supplementary
material.. Thus, the large-valued feature map impacts all output channels
after the 1$\times$1 convolutions. This has a huge impact on the security of
efficient DNNs [Tan and Le(2020), Stamoulis et al.(2019)Stamoulis, Ding, Wang,
Lymberopoulos, Priyantha, Liu, and Marculescu], as they are more fragile to
adversarial weight attacks.

Figure 2: The location of the attention map [Selvaraju et al.(2017)Selvaraju,
Cogswell, Das, Vedantam, Parikh, and Batra] significantly changes by only a
couple of bit flips in MobileNetV2.

Figure 3: The accuracy evaluated by the actual dataset (blue) and the
distilled validation data (red) with 20 ZeBRA trials.

###  4.3 ZeBRA with Distilled Validation Data

So far, we evaluated the attack performance, i.e., line 20 in Alg. 1, using
the actual validation dataset for both the BFA and ZeBRA. This is because we
first have to verify that the distilled target data works well as the attack
data $\mathbf{X}_{attack}^{d}$. However, a genuine zero-data based bit flip
attack is realized when we can evaluate the accuracy with the distilled target
data as well. We call this synthesized data for accuracy evaluation as
distilled validation data $\mathbf{X}_{valid}^{d}$. The
$\mathbf{X}_{valid}^{d}$ is generated once prior to line 7 in Alg. 1 with the
same procedure from line 12 to 15 in Alg. 1. For CIFAR-10 and ImageNet, 3.2k
and 10k images are self-generated. The changes in Top-1 and Top-5 accuracy
after each bit filp attack with 20 ZeBRA trials on ResNet-20 with CIFAR-10 are
provided in Figure 3. The blue curve is the accuracy when the attacked model
$\theta_{attack}$ is evaluated with the actual validation dataset. The red
curve shows the accuracy when $\mathbf{X}_{valid}^{d}$ is used instead. As
expected, there are some gaps as it is extremely difficult to exactly match
the accuracy with the actual dataset. However, the trend of accuracy drop
evaluated by $\mathbf{X}_{valid}^{d}$ follows well with the one evaluated by
the actual dataset.

For better fidelity of the ZeBRA, we add Top-5 target accuracy (e.g., 52% for
CIFAR-10 and 1% for ImageNet) as it is another good measure to check whether
the model became a random predictor or not. As the estimated accuracy with
$\mathbf{X}_{valid}^{d}$ drops faster than the actual accuracy, the resulting
number of bit flips on average by the ZeBRA (reported in Table 4) reduces by
2.4 bits for CIFAR-10 when compared to the result in Table 2. Similar number
of bit flips on average is observed for ImageNet when compared to the result
in Table 3. The average accuracy after attack, however, is higher due to the
error in accuracy estimation (11.3$\sim$15.5%, not 10% for CIFAR-10 and
1.1$\sim$12.3%, not 0.2% for ImageNet). Still, the minimum Top-1 accuracy near
the target accuracy was achieved. Thus, we can say that DNN models are
completely destroyed with the ZeBRA without accessing the actual dataset.

Table 4: The attack performance of ZeBRA with distilled validation dataset on
all benchmarks for CIFAR-10 and ImageNet

Model | ZeBRA w/ Distilled Validation Data (CIFAR-10) | Model | ZeBRA w/ Distilled Validation Data (ImageNet)
---|---|---|---
| Bit Flips
---
(Best)
| Bit Flips
---
(Worst)
| Mean
---
/ Stdev
| Top-1 Accuracy
---
(Min / Avg)
| Bit Flips
---
(Best)
| Bit Flips
---
(Worst)
| Mean
---
/ Stdev
| Top-1 Accuracy
---
(Min / Avg)
ResNet-20 | 7 | 10 | 8.5 / 1.4 | 9.9 / 11.3 | ResNet-18 | 4 | 10 | 5.9 / 1.8 | 0.3 / 8.4
ResNet-32 | 6 | 10 | 7.2 / 1.6 | 10.7 / 13.0 | ResNet-34 | 2 | 10 | 3.4 / 1.7 | 0.4 / 8.4
ResNet-44 | 13 | 19 | 16.3 / 1.4 | 10.1 / 15.5 | Resnet-50 | 3 | 7 | 4.4 / 1.1 | 0.1 / 12.3
ResNet-56 | 8 | 16 | 11.6 / 2.6 | 10.0 / 15.2 | MobileNetV2 | 1 | 4 | 2.4 / 0.8 | 0.1 / 1.1

###  4.4 Runtime of ZeBRA Algorithm

As the ZeBRA requires to distill the attack batch prior to the iterative bit
search, we analyze the runtime overhead compared to the BFA. The runtime for
each stage during the BFA or ZeBRA is reported in Table 5. As the number of
searched bits differs by the DNN models and datasets, we multiply the average
number of bit flips on each benchmark and the runtime for a single bit search
process. The average bit flips reported in Table 2 for CIFAR-10 and Table 3
for ImageNet are used for the BFA. The average bit flips reported in Table 4
are used for the ZeBRA utilizing the distilled validation data for its
accuracy evaluation. Due to the additional data generation process of the
ZeBRA, it takes 1.03$\times$ and 4.18$\times$ longer to perform the iterative
bit search. This runtime overhead is insignificant since the iterative bit
search is performed offline prior to the physical bit flip attack. Thus, the
adversary has little runtime constraint on searching bits to be flipped as
well as generating attack data $\mathbf{X}_{attack}^{d}$. As emphasized by
this work, the attack becomes more effective as training/test datasets are no
longer needed to perform the adversarial weight attack with the proposed
method.

Table 5: The runtime comparison between the BFA (only bit search) and ZeBRA
(data generation + bit search) on various benchmarks

CIFAR-10 | BFA | ZeBRA with $\mathbf{X}_{valid}^{d}$ | ImageNet | BFA | ZeBRA with $\mathbf{X}_{valid}^{d}$
---|---|---|---|---|---
Bit Search (s) | Distill Data (s) | Bit Search (s) | Bit Search (s) | Distill Data (s) | Bit Search (s)
ResNet-20 | 2.03 | 2.09 | 0.57 | ResNet-18 | 5.03 | 4.03 | 3.66
ResNet-32 | 3.53 | 2.36 | 1.08 | ResNet-34 | 15.53 | 40.07 | 5.54
ResNet-44 | 8.32 | 3.26 | 4.40 | ResNet-50 | 21.47 | 13.10 | 11.22
ResNet-56 | 9.41 | 3.89 | 4.87 | MobileNetV2 | 2.09 | 21.36 | 1.90

##  5 Conclusion

We proposed a zero-data based repeated bit flip attack having the ability of
generating its own attack and validation data to perform the bit flip attack.
As the adversary requires less knowledge for the attack, the ZeBRA will become
a significant threat to any safety-critical deep learning applications.
Especially, as demonstrated by this work, mobile-friendly DNN models require
more attention for the improved robustness to adversarial weight attacks. In
terms of the attack performance of the ZeBRA, a better way of generating
distilled validation data needs to be developed to improve the quality of
accuracy estimation which remains as our future work. To improve the quality
of the distilled validation data, we may collect several data samples per
target label and apply deep metric learning to better cluster the synthesized
samples of each target label. Moreover, it will be useful to extend the study
on other important tasks such as semantic segmentation and language modeling.

## Acknowledgment

This work was supported in part by Samsung Research Funding Incubation Center
of Samsung Electronics (SRFC-IT1902-03), the National Research Foundation of
Korea (NRF) under Grant NRF-2019R1G1A1008751, and the Institute of Information
and Communications Technology Planning and Evaluation (IITP) Grant funded by
the Korean Government (MSIT) (IITP-2021-2018-0-01433; ITRC support program,
and No. 2019-0-00533; Research on CPU vulnerability detection and validation).
We also thank Dr. Deliang Fan and Adnan Siraj Rakin for their valuable inputs.

## References

  * [Agoyan et al.(2010)Agoyan, Dutertre, Mirbaha, Naccache, Ribotta, and Tria] Michel Agoyan, Jean-Max Dutertre, Amir-Pasha Mirbaha, David Naccache, Anne-Lise Ribotta, and Assia Tria.  How to flip a bit?  In _Proceedings of the IEEE International On-Line Testing Symposium_ , page 235–239, 2010.  10.1109/IOLTS.2010.5560194.  URL https://doi.org/10.1109/IOLTS.2010.5560194.
  * [Baluja and Fischer(2017)] Shumeet Baluja and Ian Fischer.  Adversarial transformation networks: Learning to generate adversarial examples.  _arXiv:1703.09387_ , 2017.
  * [Brown et al.(2020)Brown, Mann, Ryder, Subbiah, Kaplan, Dhariwal, Neelakantan, Shyam, Sastry, Askell, Agarwal, Herbert-Voss, Krueger, Henighan, Child, Ramesh, Ziegler, Wu, Winter, Hesse, Chen, Sigler, Litwin, Gray, Chess, Clark, Berner, McCandlish, Radford, Sutskever, and Amodei] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * [Cai et al.(2020)Cai, Yao, Dong, Gholami, Mahoney, and Keutzer] Yaohui Cai, Zhewei Yao, Zhen Dong, Amir Gholami, Michael W. Mahoney, and Kurt Keutzer.  ZeroQ: A novel zero shot quantization framework.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [Covington et al.(2016)Covington, Adams, and Sargin] Paul Covington, Jay Adams, and Emre Sargin.  Deep neural networks for youtube recommendations.  In _Proceedings of the ACM Conference on Recommender Systems (RecSys)_ , page 191–198, 2016.  10.1145/2959100.2959190.  URL https://doi.org/10.1145/2959100.2959190.
  * [Frigo et al.(2018)Frigo, Giuffrida, Bos, and Razavi] Pietro Frigo, Cristiano Giuffrida, Herbert Bos, and Kaveh Razavi.  Grand pwning unit: Accelerating microarchitectural attacks with the GPU.  In _IEEE Symposium on Security and Privacy (SP)_ , pages 195–210, 2018.  10.1109/SP.2018.00022.
  * [Goodfellow et al.(2015)Goodfellow, Shlens, and Szegedy] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  _arXiv:1412.6572_ , 2015.
  * [Grigorescu et al.(2020)Grigorescu, Trasnea, Cocias, and Macesanu] Sorin Grigorescu, Bogdan Trasnea, Tiberiu Cocias, and Gigel Macesanu.  A survey of deep learning techniques for autonomous driving.  _Journal of Field Robotics_ , 37(3):362–386, Apr 2020.  ISSN 1556-4967.  10.1002/rob.21918.
  * [He et al.(2015)He, Zhang, Ren, and Sun] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  _arXiv:1512.03385_ , 2015.
  * [Huang et al.(2019)Huang, Zambelli, Kay, Martins, Tassa, Pilarski, and Hadsell] Sandy H. Huang, Martina Zambelli, Jackie Kay, Murilo F. Martins, Yuval Tassa, Patrick M. Pilarski, and Raia Hadsell.  Learning gentle object manipulation with curiosity-driven deep reinforcement learning.  _arXiv:1903.08542_ , 2019.
  * [Jagielski et al.(2020)Jagielski, Carlini, Berthelot, Kurakin, and Papernot] Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Papernot.  High accuracy and high fidelity extraction of neural networks.  In _USENIX Security Symposium_ , pages 1345–1362, August 2020.  ISBN 978-1-939133-17-5.
  * [Juuti et al.(2019)Juuti, Szyller, Marchal, and Asokan] Mika Juuti, Sebastian Szyller, Samuel Marchal, and N. Asokan.  PRADA: Protecting against DNN model stealing attacks.  _arXiv:1805.02628_ , 2019.
  * [Kaissis et al.(2020)Kaissis, Makowski, Ruckert, and Braren] Georgios A. Kaissis, Marcus Makowski, Daniel Ruckert, and Rickmer F. Braren.  Secure, privacy-preserving and federated machine learning in medical imaging.  _Nature Machine Intelligence_ , 2:305–311, 2020.
  * [Kim et al.(2014)Kim, Daly, Kim, Fallin, Lee, Lee, Wilkerson, Lai, and Mutlu] Yoongu Kim, Ross Daly, Jeremie Kim, Chris Fallin, Ji Hye Lee, Donghyuk Lee, Chris Wilkerson, Konrad Lai, and Onur Mutlu.  Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors.  In _ACM/IEEE International Symposium on Computer Architecture (ISCA)_ , pages 361–372, 2014.  10.1109/ISCA.2014.6853210.
  * [Krizhevsky et al.(2010)Krizhevsky, Nair, and Hinton] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  CIFAR-10 (Canadian Institute for Advanced Research).  https://www.cs.toronto.edu/k̃riz/cifar.html, 2010.  [Online; accessed 03-March-2021].
  * [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton] Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton.  ImageNet classification with deep convolutional neural networks.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 1097–1105, 2012.  URL https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf.
  * [Kurakin et al.(2017)Kurakin, Goodfellow, and Bengio] Alexey Kurakin, Ian Goodfellow, and Samy Bengio.  Adversarial examples in the physical world.  _arXiv:1607.02533_ , 2017.
  * [Liu et al.(2020)Liu, Duh, Liu, and Gao] Xiaodong Liu, Kevin Duh, Liyuan Liu, and Jianfeng Gao.  Very deep transformers for neural machine translation.  _arXiv:2008.07772_ , 2020.
  * [Liu et al.(2017)Liu, Wei, Luo, and Xu] Y. Liu, L. Wei, B. Luo, and Q. Xu.  Fault injection attack on deep neural network.  In _IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_ , pages 131–138, 2017.  10.1109/ICCAD.2017.8203770.
  * [Melis et al.(2017)Melis, Demontis, Biggio, Brown, Fumera, and Roli] Marco Melis, Ambra Demontis, Battista Biggio, Gavin Brown, Giorgio Fumera, and Fabio Roli.  Is deep learning safe for robot vision? adversarial examples against the iCub humanoid.  _arXiv:1708.06939_ , 2017.
  * [Mnih et al.(2013)Mnih, Kavukcuoglu, Silver, Graves, Antonoglou, Wierstra, and Riedmiller] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv:1312.5602_ , 2013.
  * [Moosavi-Dezfooli et al.(2016)Moosavi-Dezfooli, Fawzi, and Frossard] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  DeepFool: A simple and accurate method to fool deep neural networks.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2574–2582, 2016.  10.1109/CVPR.2016.282.
  * [Morgulis et al.(2019)Morgulis, Kreines, Mendelowitz, and Weisglass] Nir Morgulis, Alexander Kreines, Shachar Mendelowitz, and Yuval Weisglass.  Fooling a real car with adversarial traffic signs.  _arXiv:1907.00374_ , 2019.
  * [Mutlu and Kim(2019)] Onur Mutlu and Jeremie S. Kim.  Rowhammer: A retrospective.  _arXiv:1904.09724_ , 2019.  URL http://arxiv.org/abs/1904.09724.
  * [Rakin et al.(2019)Rakin, He, and Fan] Adnan Siraj Rakin, Zhezhi He, and Deliang Fan.  Bit-flip attack: Crushing neural network with progressive bit search.  In _IEEE International Conference on Computer Vision (ICCV)_ , 2019\.
  * [Rakin et al.(2021)Rakin, He, Li, Yao, Chakrabarti, and Fan] Adnan Siraj Rakin, Zhezhi He, Jingtao Li, Fan Yao, Chaitali Chakrabarti, and Deliang Fan.  T-BFA: Targeted bit-flip adversarial weight attack.  _arXiv:2007.12336_ , 2021.
  * [Redmon et al.(2016)Redmon, Divvala, Girshick, and Farhadi] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  _arXiv:1506.02640_ , 2016.
  * [Roscian et al.(2013)Roscian, Sarafianos, Dutertre, and Tria] C. Roscian, A. Sarafianos, J. Dutertre, and A. Tria.  Fault model analysis of laser-induced faults in SRAM memory cells.  In _Workshop on Fault Diagnosis and Tolerance in Cryptography_ , pages 89–98, Aug 2013.  10.1109/FDTC.2013.17.
  * [Sandler et al.(2019)Sandler, Howard, Zhu, Zhmoginov, and Chen] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  MobileNetV2: Inverted residuals and linear bottlenecks.  _arXiv:1801.04381_ , 2019.
  * [Seaborn and Dullien(2016)] M. Seaborn and T. Dullien.  Exploiting the DRAM RowHammer bug to gain kernel privileges.  In _BlackHat_ , 2016.
  * [Selvaraju et al.(2017)Selvaraju, Cogswell, Das, Vedantam, Parikh, and Batra] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-CAM: Visual explanations from deep networks via gradient-based localization.  In _IEEE International Conference on Computer Vision (ICCV)_ , pages 618–626, 2017.  10.1109/ICCV.2017.74.
  * [Simonyan and Zisserman(2014)] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv:1409.1556_ , 2014.
  * [Stamoulis et al.(2019)Stamoulis, Ding, Wang, Lymberopoulos, Priyantha, Liu, and Marculescu] Dimitrios Stamoulis, Ruizhou Ding, Di Wang, Dimitrios Lymberopoulos, Bodhi Priyantha, Jie Liu, and Diana Marculescu.  Single-path NAS: Designing hardware-efficient convnets in less than 4 hours.  _arXiv:1904.02877_ , 2019.
  * [Szegedy et al.(2014)Szegedy, Zaremba, Sutskever, Bruna, Erhan, Goodfellow, and Fergus] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  _arXiv:1312.6199_ , 2014.
  * [Szegedy et al.(2015)Szegedy, Vanhoucke, Ioffe, Shlens, and Wojna] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  _arXiv:1512.00567_ , 2015.  URL http://arxiv.org/abs/1512.00567.
  * [Tan and Le(2020)] Mingxing Tan and Quoc V. Le.  EfficientNet: Rethinking model scaling for convolutional neural networks.  _arXiv:1905.11946_ , 2020.
  * [Zhao et al.(2019)Zhao, Wang, Gongye, Wang, Fei, and Lin] Pu Zhao, Siyue Wang, Cheng Gongye, Yanzhi Wang, Yunsi Fei, and Xue Lin.  Fault sneaking attack: A stealthy framework for misleading deep neural networks.  In _Proceedings of the Design Automation Conference (DAC)_ , pages 1–6, 2019.  ISBN 9781450367257.  10.1145/3316781.3317825.