# Robust Domain-Free Domain Generalization
with Class-aware Alignment

###### Abstract

While deep neural networks demonstrate state-of-the-art performance on a
variety of learning tasks, their performance relies on the assumption that
train and test distributions are the same, which may not hold in real-world
applications. Domain generalization addresses this issue by employing multiple
source domains to build robust models that can generalize to unseen target
domains subject to shifts in data distribution. In this paper, we propose
Domain-Free Domain Generalization (DFDG), a model-agnostic method to achieve
better generalization performance on the unseen test domain without the need
for source domain labels. DFDG uses novel strategies to learn domain-invariant
class-discriminative features. It aligns class relationships of samples
through class-conditional soft labels, and uses saliency maps, traditionally
developed for post-hoc analysis of image classification networks, to remove
superficial observations from training inputs. DFDG obtains competitive
performance on both time series sensor and image classification public
datasets.

Index Terms—  Domain generalization; data distribution shift, model robustness

##  1 INTRODUCTION

While deep neural networks have widely acclaimed classification performance in
diverse fields, their performance is often reliant on the assumption that all
the train and test examples are sampled from the same distribution. In
practical applications, though, changes in the data generation regimes are
common during operation, effectively causing a shift in the data distribution
that can significantly deteriorate model performance [1, 2, 3]. This not only
compromises the accuracy of the existing deep model, but also the
applicability if there are no available samples from the new distribution. In
response to such issues, _domain adaptation_ algorithms [4] aim at learning a
model aligning the source distribution(s) and the new target distribution
through a common feature representation space. For training, these methods
require a sufficient amount of source samples and target inputs, and in some
cases additional target labels. In the more extreme field of _domain
generalization_ [5, 6, 7, 8], no target samples are available at train time.
The goal is to learn a robust model that can directly generalize when unseen
new data distributions arise. This allows to address many realistic scenarios
in which the model needs to be deployed in the wild and new data cannot be
collected for constant retraining. For example, in object recognition, new
images of the same object with different background types may be encountered
[6, 9]; in fault diagnosis from sensing devices, new operating conditions may
display unseen signals [10]; or, in speech recognition, an arbitrary number of
unknown speakers may emerge [3].

A core aim of domain generalization is to find a common representation space
of the multiple source domains such that the class-discriminative information
is captured and the domain-specific statistics are ignored [8, 7, 11, 12]. A
popular approach is to minimize the discrepancy among the marginal
distributions of input features [13] or the class-conditional distributions
[14]. One important limitation is the need for domain labels to identify the
groupings of samples for alignment [9]. Typically in domain adaptation and
generalization literature, dataset labels are used as domain labels. This
restrains the applicability of the methods since domain labels may be
unavailable in practice, and dataset labels cannot replace domain labels in
cases where samples of a dataset are drawn from a mixture of domains, take for
example photos taken with different devices on social media websites if device
type is the domain.

Fig. 1: Overview: DFDG learns domain-invariant class-discriminative features
without the use of domain labels by (a) aligning class relationships of
samples in the same class to the class centroid, and (b) masking superficial
observations (e.g. domain-specific backgrounds) from training inputs guided by
saliency maps.

Aiming at a widely applicable domain generalization problem, in this work we
propose a Domain-Free Domain Generalization (DFDG) method that learns domain-
invariant class-discriminative features without the need for domain labels. As
illustrated in Figure 1, we propose novel strategies for:

  * •

Model regularization to learn domain-invariant features without domain labels
by aligning soft labels conditioned on the classes to the class centroid;

  * •

Automatic augmentation of inputs to remove superficial, less class-
discriminative observations through saliency maps.

DFDG is model-agnostic and does not require expert knowledge for feature
engineering, which renders it suitable for learning tasks in general. In our
experiments, we consider both time series sensor and image classification
benchmarks, and demonstrate that DFDG offers competitive performance compared
to state-of-the-art methods. Although saliency maps are developed and
conventionally used for image-based applications [15], our results show
empirically that the technique can also be applied on time series sensor data.

##  2 RELATED WORKS

###  2.1 Combining source models

With multiple source domains, some works predict for new domains by training a
model for each source and combining the respective predictions [11, 16, 17].
Similarly, some meta-learning frameworks select models for unseen target
datasets by exhaustively training all candidate models on each source dataset,
and select the final model by matching features and statistics between source
and target datasets [18, 19]. These methods require storing a model for each
source domain. In DFDG, only a single model is trained and stored.

###  2.2 Learning domain-invariant features

Many previous works for domain generalization focus on the goal of learning
domain-invariant features which are class discriminative. This can be achieved
through auxiliary losses with known domain labels. Besides the classification
loss, the objective function also includes a domain alignment loss to reduce
the distance between samples from different domains [8]. This has been
implemented through meta-learning [7, 14, 20], or directly minimizing the
distance between feature representations of different domains [5, 13]. Some
works have an additional separation loss to maximize the distance between
samples from different classes to encourage local clustering [5, 14]. In the
case where domain labels are unknown, [9] shows that samples can be clustered
into latent domains and then aligned. Knowledge of accurate domain labels
cannot always be assumed in real-world applications, hence we work in the most
general setting where domain labels are unavailable.

###  2.3 Learning robust features

Learning features that aim to improve model performance in general by being
robust to sample variations at training are found to improve generalization
performance in new domains. Popular approaches to learn robust features is to
perturb the network [12] or representations during training. Domain-specific
representations are removed either from the latent feature space [21] or from
the observed input space [22], but these techniques are specific to image
inputs. [6] zeros out penultimate-layer feature representations associated
with the highest gradient in the final classification layer so that the
network learns other features for classification. [23] regularizes the network
through an auxiliary self-supervised task to learn spatial correlations within
an image.

Other works propose to extrapolate to unseen target distributions by
generating adversarial samples [24] or by enforcing equality in training risks
across domains [25]. The latter implies that the worst-performing domain may
be improved at the cost of other domains.

##  3 Problem setup

We describe the problem setup and notations used in this paper. We denote the
set of $K$ source domains as $\mathcal{D}_{S}=\\{D_{1},\dots,D_{K}\\}$ and the
unseen target domain as $D_{t}$. For each domain $D$, samples are drawn from a
fixed distribution $\left(X^{(D)},Y^{(D)}\right)\sim P^{(D)}$ where $X$ and
$Y$ are the predictor and response variables. We denote the observed samples
as
$\left\\{\left(\boldsymbol{x}^{(D)}_{i},\boldsymbol{y}^{(D)}_{i}\right)\right\\}_{i=1}^{N_{D}}$
for a sample size of $N_{D}$. We focus on classification tasks in this paper,
so $\boldsymbol{y}_{i}$ is a one-hot vector of the true class label in $C$
classes. No sample from the target domain $D_{t}$ is available at the training
and validation stages of model learning. In the domain-free setting, we
further assume that domain labels are unavailable, which is a realistic
assumption for data collection. The aim is to train a model $f$ parameterized
by $\theta$ to achieve good classification performance on the target domain
$D_{t}$.

A common strategy for classification is to estimate the class probabilities
for an input $\boldsymbol{x}_{i}$. Let $\boldsymbol{p}_{i}$ be the soft labels
or vector of class probabilities for input $\boldsymbol{x}_{i}$ as learned by
the model $f$, that is,
$\boldsymbol{p}_{i}=\text{softmax}(f(\boldsymbol{x}_{i};\theta))$ where
$\text{softmax}(\boldsymbol{a})[c]=\frac{\exp{(a_{c})}}{\sum_{j=1}^{C}\exp{(a_{j})}}$
with $a_{c}$ denoting the element of vector $\boldsymbol{a}$ corresponding to
class $c$. The predicted class is the class with the highest probability in
$\boldsymbol{p}_{i}$.

##  4 PROPOSED METHOD: DFDG

A key concept in domain generalization is to learn representations which are
domain-invariant but class-discriminative. To train the model for
classification, we use the cross-entropy loss as the base objective for each
batch of samples with indices $B$:

$\ell_{ce}=-\frac{1}{|B|}\sum_{i\in
B}\boldsymbol{y}_{i}^{T}\log(\boldsymbol{p}_{i}).$ (1)

where $\boldsymbol{y}_{i}$ is the one-hot vector of the true label and
$\boldsymbol{p}_{i}$ is the soft label estimated for sample $i$. Additionally,
DFDG learns soft labels $\boldsymbol{p_{i}}$’s such that they are aligned
across source domains. We combine this with input augmentation so that model
training focuses on class-discriminative inputs.

###  4.1 Regularizing for class relationship alignment

Constraining the model by aligning features from different domains tends to
learn features that are more robust and applicable across domains, and less
domain-specific. Being overly reliant on domain-specific features risks
overfitting to the source domains and hence poor performance on out-of-
distribution samples where these features are absent. Instead of aligning
intermediate features, DFDG aligns the estimated soft labels which are lower
dimensional and reflects relationships between class concepts. Alignments in
the label space have been applied in domain adaption and domain generalization
problems where domain labels are known [14, 26, 27]. Without domain labels, we
propose an alignment loss:

$\displaystyle\ell_{align}$
$\displaystyle=\sum_{c=1}^{C}\frac{1}{|B(c)|}\sum_{i\in
B(c)}\|\boldsymbol{p}_{i}-\mu(c)\|_{2}^{2}$ (2) $\displaystyle\mu(c)$
$\displaystyle=\frac{1}{|B(c)|}\sum_{i\in B(c)}\boldsymbol{p}_{i}$ (3)

where for each class $c$, $B(c)=\\{i|i\in B,y_{i}=c\\}$ are indices of
samples, $\mu(c)$ is the cluster center for the corresponding class, and
$\boldsymbol{p}_{i}$ is the vector of soft labels for sample $i$. The
regularization encourages samples from the same class to have similar class
relationships regardless of their domains. The complete objective function
with this alignment regularization is

$L=\ell_{ce}+\alpha\ell_{align}$ (4)

with hyperparameter $\alpha$ balancing the effects from the two parts.

###  4.2 Masking superficial observations

The presence of superficial or domain-specific observations in the input space
can lead to overfitting to training data if the model learns to rely on these
observations for the classification task. We use the term ‘observation’ here
to denote a pixel in an image and a reading at one time step for a time series
as examples. In images, these superficial observations can be pixels for
backgrounds or styles. We propose augmenting $m\%$ of the samples in each
batch at training to mask superficial observations by perturbing the
observations least relevant to the desired classification task. We perturb by
randomly shuffling the least relevant observations, hence preserving the
overall statistics of the input. The intuition is that the trained model will
be more robust to variations in these superficial observations in the target
domain.

While a binary map that exactly pinpoints the location of class-discriminative
features in the input is the most desirable and has been found to improve
classification performance [28], such accurate maps require human-in-the-loop
processing and cannot be readily available for most datasets. Our strategy
also differs from feature muting [29] that sets a fixed number of features to
zero, which can drastically change sample statistics and risk muting useful
features through the fixed threshold. In DFDG, we use SmoothGrad saliency maps
[15] to rank the relevance of each observation. Saliency maps are developed to
explain decisions made by neural network models for image classification by
assigning a saliency score to each pixel [15, 30]. A ‘vanilla’ gradient-based
saliency map $g(\boldsymbol{x},c)$ of an input image $\boldsymbol{x}$ for
class $c$ is obtained by differentiating the class logit of model $f$ with
respect to $\boldsymbol{x}$ and taking the square element-wise:

$g(\boldsymbol{x},c)=\left(\frac{\partial
f(\boldsymbol{x},\theta)[c]}{\partial\boldsymbol{x}}\right)^{\circ 2}$ (5)

where each saliency score reflects the amount of influence that a small change
in a pixel has on the class logit. SmoothGrad denoises the saliency map by
averaging $n$ replicates of $g(\boldsymbol{x},c)$ where Gaussian noise
$N(0,\sigma^{2})$ is added to $\boldsymbol{x}$ in each replicate, and we
denote the resulting SmoothGrad saliency map as $sg(\boldsymbol{x},c)$. We fix
$n=25$ and $\sigma=0.15$, the default in [31], throughout our experiments. We
apply the technique on time series as well as image data.

We rank how class-discriminative an observation is by its saliency score.
Observations below a threshold is masked and shuffled. The threshold is the
$q^{th}$ percentile of the saliency scores of a image, uniformly sampled from
$[0,qMax]$ where $qMax$ is the maximum threshold percentile. In this sampling
scheme, less relevant observations will be masked more often and the model
will be less reliant on them. Figure 1 shows examples of saliency maps and
masked input images for $q=70$.

##  5 EXPERIMENTS

We evaluate DFDG on 3 public datasets: Bearings fault classification from
vibration sensor signals, HHAR heterogeneous human activity recognition from
motion sensor signals and PACS image classification. We report classification
accuracy by treating each domain in turn as the unseen target domain and the
rest as source domains. Details of the datasets and implementation
configurations can be found in Section 5.1. For all datasets, we compare with
TrainAll which is a vanilla training of source samples, RSC [6] which is a
robustness method using feature muting that has achieved state-of-the art
performance for image classification including PACS, and MMLD [9] which
clusters samples into latent domains using convolutional feature statistics
and aligns the domains with a discriminator network.

###  5.1 Datasets and implementation

Bearings Dataset: The Case Western Reserve University
(CWRU111https://csegroups.case.edu/bearingdatacenter/pages/welcome-case-
western-reserve-university-bearing-data-center-website) Bearings dataset is
widely used for rolling element bearings diagnostics in rotating machines
[32]. Vibration signals are collected with 12kHz sampling rate under 8
different working conditions or domains [32]. The operating conditions
comprise 4 loading torques and two different locations (drive end, fan end).
The system has three major types of faults, namely inner-race fault (IF),
outer-race fault (OF), and ball fault (BF), and each fault type occurs with
three different dimensions 0.007, 0.014, 0.021 inches. Overall, we have 10
classes with 9 faulty classes and 1 healthy class. We extracted samples of
length 4096 by applying a sliding window with shift size 290 [33]. We use a
6-layer convolutional neural network (CNN) as feature extractor and a 3-layer
fully-connected network as classifier.

HHAR: The HHAR
dataset222http://archive.ics.uci.edu/ml/datasets/heterogeneity+activity+recognition
consists of sensor readings to classify six activities, namely Biking,
Standing, Sitting, Walking, Stair down, and Stair up. Gyroscope and
accelerometer motion sensors in 8 smartphones and 4 smartwatches are used for
monitoring. Nine different users execute these activities without predefined
order while carrying the devices. We treat each user as a domain and,
following a recent work on domain adaption [34], we focus on data from 8
smartphones with accelerometer sensors, pre-processed as in that work. We use
a 3-layer CNN as feature extractor and a 1-layer fully-connected network for
classification [35].

PACS: PACS is an image classification dataset333
http://www.eecs.qmul.ac.uk/~dl307/project_iccv2017 containing images from 4
styles or domains, namely Photo, Art painting, Cartoon and Sketch. Each domain
has a total of 7 classes: dog, elephant, giraffe, guitar, horse, house and
person. Following [6, 9, 23], we use a ResNet18 network architecture and apply
the same image augmentations to the samples, namely random cropping to 80-100%
size, horizontal flipping, color jittering and conversion to grayscale.

We fix DFDG hyperparameters $\alpha=0.1$, $m=50$ and $qMax=70$, with further
ablation studies in Section 5.3. During training, the alignment regularization
and input masking strategies are randomly alternated across batches of size
128. The time series sensor datasets are trained for 2000 iterations, and PACS
is trained for 3000 iterations. The learning rate is $0.001$, and decayed by
factor $0.1$ after $80\%$ iterations. To prevent classes from being
unrepresented in batches, minority classes are upsampled uniformly at random,
keeping a minority-to-majority class ratio of at least $0.5$ in each batch.
All the results are averaged over runs from 3 different seeds.
RSC444https://github.com/DeLightCMU/RSC and MMLD555https://github.com/mil-
tokyo/dg_mmld were run using their open-source implementations on the same
seeds.

###  5.2 Generalization performance

Table 1 shows the classification performance on unseen target domains for the
Bearings dataset. Since time series may be less distinguishable across domains
than images, clustering with convolutional feature statistics as originated
from image stylization [9] may have resulted in incorrect latent domains and
hence negative transfer in MMLD. Our proposed DFDG improves average
classification accuracy by 2.83% over the baseline TrainAll. Combining DFDG
with RSC, by randomly alternating between the two strategies across batches at
training, attains the best accuracy of $84.65\%$. This shows that DFDG can
complement other domain generalization methods. Figure 2 plots the
2-dimensional t-SNE representations of DFDG features. From Figure 2(a),
samples from the same class tend to cluster together. For exceptions such as
the class “BF: 0.021” where there are two clusters, observe from the
corresponding Figure 2(b) that one cluster correspond to domains (A, B, C, D)
with drive-end bearings location, and the other correspond to domains (E, F,
G, H) with fan-end bearings location. Samples from the same location are
clustered closer together due to greater inter-domain similarity.

(a) Marked by class

(b) Marked by domain

Fig. 2: t-SNE of Bearings features from DFDG trained with target domain H, demonstrating per-class clustering across domains. Target | Accuracy ($\%$)
---|---
| TrainAll | RSC | MMLD | DFDG | DFDG+RSC
A | 52.33 | 68.43 | 65.70 | 66.60 | 68.23
B | 90.50 | 91.10 | 95.37 | 89.30 | 90.90
C | 92.90 | 97.60 | 89.33 | 89.67 | 92.47
D | 74.97 | 77.73 | 65.87 | 77.73 | 77.97
E | 70.73 | 70.33 | 64.20 | 73.40 | 74.77
F | 88.53 | 86.40 | 79.03 | 91.50 | 90.23
G | 87.20 | 90.20 | 86.83 | 91.40 | 94.30
H | 85.20 | 90.50 | 75.53 | 85.30 | 88.37
Avg | 80.30 | 84.04 | 77.73 | 83.13 | 84.65
Table 1: Bearings: Classification accuracy for 10 fault types  Target | Accuracy ($\%$)
---|---
| TrainAll | RSC | MMLD | DFDG
A | 43.27 | 41.28 | 45.82 | 36.76
B | 48.91 | 44.54 | 60.43 | 70.91
C | 49.15 | 47.68 | 46.73 | 54.63
D | 45.73 | 52,23 | 49.93 | 62.60
E | 46.59 | 44.80 | 52.88 | 66.40
F | 41.98 | 43.02 | 46.95 | 69.28
G | 30.36 | 29.99 | 43.90 | 60.64
H | 54.84 | 57.75 | 52.38 | 47.30
I | 40.86 | 40.59 | 47.19 | 55.07
Avg | 45.15 | 45.23 | 49.58 | 58.18
Table 2: HHAR: Classification accuracy for 6 activities  Target | Accuracy ($\%$)
---|---
| TrainAll | RSC | MMLD | DFDG
Art | 78.73 | 80.37 | 78.99 | 79.23
Cartoon | 74.30 | 76.84 | 77.06 | 75.84
Photo | 94.55 | 94.99 | 95.41 | 95.45
Sketch | 76.19 | 74.40 | 62.56 | 77.87
Avg | 80.94 | 81.65 | 78.51 | 82.10
Table 3: PACS: Classification accuracy for 7 classes.

Table 2 shows the classification performance on the 9 unseen target users or
domains for the HHAR dataset. Overall, DFDG significantly outperforms the
compared approaches by more than 8%. Additionally, DFDG achieves best accuracy
in 7 out of 9 users.

Table 3 shows the classification performance for the PACS dataset. MMLD
performed irregularly across our runs on the Sketch domain where images have
white backgrounds unlike those in the source domains, and lags clearly behind
the other methods. DFDG improves performance over the baseline TrainAll
uniformly across all 4 domains, and offers the best average accuracy of
$82.10\%$ in this comparison.

###  5.3 Ablation studies

We perform ablation studies on the effects of alignment regularization and
input masking using the Bearings dataset. From Table 4, we see that
regularization and masking both improve classification performance, with the
latter having a larger effect. The exact amount of regularization and masking
that works best varies by dataset.

Regularization | Masking | Avg Accuracy ($\%$)
---|---|---
$\alpha$ | m | qMax |
- | - | - | 79.75
0.01 | - | - | 80.21
0.1 | - | - | 79.97
- | 33 | 30 | 83.21
- | 50 | 70 | 83.42
Table 4: Ablation study of DFDG on Bearings dataset. Hyperparameter values 0
are represented by ’-’ (dash).

We also study the effect of using different saliency maps for input masking on
the Bearings dataset. The vanilla saliency map, which takes the derivative of
the class logit with respect to the input, results in an average
classification accuracy of $80.77\%$. This approach can produce noisy maps
giving poor estimates of how class-discriminative an observation is. In
contrast, SmoothGrad is less noisy, and obtains a noticeably higher accuracy
of $83.42\%$.

##  6 CONCLUSION

In this paper, we proposed DFDG, a model-agnostic method for domain
generalization that does not require domain labels for training. DFDG aligns
class-conditional soft labels and masks superficial observations from training
inputs to learn domain-invariant class-discriminative features. Overall, DFDG
exhibits better performance against competing methods for both time series
sensor and image classification problems. Namely, DFDG outperforms TrainAll
and the state-of-the-art MMLD and RSC on the PACS image dataset and the HHAR
sensor dataset. On the Bearings sensor dataset, RSC obtains a higher accuracy,
however we demonstrate that DFDG can complement this method to achieve the
best accuracy results.

## References

  * [1] G-Q. Jiang, P. Xie, X. Wang, M. Chen, and Q. He,  “Intelligent fault diagnosis of rotary machinery based on unsupervised multiscale representation learning,”  Chinese Journal of Mechanical Engineering, vol. 30, no. 6, pp. 1314–1324, 2017.
  * [2] A. Stisen, H. Blunck, S. Bhattacharya, T. S. Prentow, M. B. Kjærgaard, A. Dey, T. Sonne, and M. M. Jensen,  “Smart devices are different: Assessing and mitigating mobile sensing heterogeneities for activity recognition,”  in Proceedings of the 13th ACM conference on embedded networked sensor systems, 2015, pp. 127–140.
  * [3] J. Gideon, M. Mcinnis, and E. Mower Provost,  “Improving cross-corpus speech emotion recognition with adversarial discriminative domain generalization (addog),”  IEEE Transactions on Affective Computing, vol. PP, pp. 1–1, 05 2019\.
  * [4] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J.W. Vaughan,  “A theory of learning from different domains,”  Machine Learning, vol. 79, no. 1, pp. 151–175, 2010.
  * [5] S. Motiian, M. Piccirilli, D. A. Adjeroh, and G. Doretto,  “Unified deep supervised domain adaptation and generalization,”  in ICCV, 2017.
  * [6] Z. Huang, H. Wang, E.P. Xing, and D. Huang,  “Self-challenging improves cross-domain generalization,”  in ECCV, 2020.
  * [7] Y. Balaji, S. Sankaranarayanan, and R. Chellappa,  “MetaReg: Towards domain generalization using meta-regularization,”  in NeurIPS. 2018.
  * [8] I. Albuquerque, J. Monteiro, M. Darvishi, T. H. Falk, and I. Miltliagkas,  “Generalizing to unseen domains via distribution matching,”  ArXiv, 2020.
  * [9] Toshihiko M. and Tatsuya H.,  “Domain generalization using a mixture of multiple latent domains,”  in AAAI, 2020.
  * [10] H. Zheng, R. Wang, Y. Yang, Y. Li, and M. Xu,  “Intelligent fault identification based on multisource domain generalization towards actual diagnosis scenario,”  IEEE Transactions on Industrial Electronics, vol. 67, no. 2, pp. 1293–1304, 2020.
  * [11] M. Mancini, S. R. Bulò, B. Caputo, and E. Ricci,  “Best sources forward: Domain generalization through source-specific nets,”  ICIP, 2018.
  * [12] D. Li, J. Zhang, Y. Yang, C. Liu, Y-Z. Song, and T. M. Hospedales,  “Episodic training for domain generalization,”  ICCV), 2019.
  * [13] H. Li, S. J. Pan, S. Wang, and A. C. Kot,  “Domain generalization with adversarial feature learning,”  in ICCV, 2018.
  * [14] Q. Dou, D. Coelho de Castro, K. Kamnitsas, and B. Glocker,  “Domain generalization via model-agnostic learning of semantic features,”  in NeurIPS, 2019.
  * [15] D. Smilkov, N. Thorat, B. Kim, F. Viégas, and M. Wattenberg,  “Smoothgrad: removing noise by adding noise,”  Workshop on Visualization for Deep Learning, ICML, 2017.
  * [16] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, et al.,  “Matching networks for one shot learning,”  in NeurIPS, 2016.
  * [17] A. D’Innocente and B. Caputo,  “Domain generalization with domain-specific aggregation modules,”  in Pattern Recognition. 2019, pp. 187–198, Springer International Publishing.
  * [18] T. S. Talagala, R. J. Hyndman, and G. Athanasopoulos,  “Meta-learning how to forecast time series,”  Tech. Rep., Monash University, Dept. of Econometrics and Business Statistics, 2018.
  * [19] C. Lemke and B. Gabrys,  “Meta-learning for time series forecasting and forecast combination,”  Neurocomputing, vol. 73, no. 10, pp. 2006 – 2016, 2010.
  * [20] D. Li, Y. Yang, Y-Z. Song, and T. M. Hospedales,  “Learning to generalize: Meta-learning for domain generalization,”  in AAAI, 2018.
  * [21] H. Wang, Z. He, Z.C. Lipton, and E. Xing,  “Learning robust representations by projecting superficial statistics out,”  ICLR, 2019.
  * [22] N. Somavarapu, C-Y. Ma, and Z. Kira,  “Frustratingly simple domain generalization via image stylization,”  ArXiv, 2020.
  * [23] F. Carlucci, A. D’Innocente, S. Bucci, B. Caputo, and T. Tommasi,  “Domain generalization by solving jigsaw puzzles,”  in CVPR, 2019.
  * [24] R. Volpi, H. Namkoong, O. Sener, J. Duchi, V. Murino, and S. Savarese,  “Generalizing to unseen domains via adversarial data augmentation,”  in NeurIPS, 2018.
  * [25] D. Krueger, E. Caballero, J. Jacobsen, A. Zhang, J. Binas, R. Le Priol, and A. C. Courville,  “Out-of-distribution generalization via risk extrapolation (Rex),”  ArXiv, 2020.
  * [26] G. Kang, L. Jiang, Y. Yang, and A. Hauptmann,  “Contrastive adaptation network for unsupervised domain adaptation,”  in CVPR, 2019.
  * [27] S. Cicek and S. Soatto,  “Unsupervised domain adaptation via regularized conditional alignment,”  in ICCV, 2019.
  * [28] X. Li, Y. Zhang, J. Zhang, Y. Chen, H. Li, I. Marsic, and R. Burd,  “Region-based activity recognition using conditional GAN,”  in ACM International Conference on Multimedia, 2017.
  * [29] D. Schiller, T. Huber, F. Lingenfelser, M. Dietz, A. Seiderer, and E. Andre,  “Relevance-based feature masking: Improving neural network based whale classification through explainable artificial intelligence,”  in Interspeech, 2019.
  * [30] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra,  “Grad-cam: Visual explanations from deep networks via gradient-based localization,”  in ICCV, 2017.
  * [31] People+AI Research (PAIR),  “Saliency methods,” https://github.com/PAIR-code/saliency, 2020\.
  * [32] W. A Smith and R. B Randall,  “Rolling element bearing diagnostics using the case western reserve university data: A benchmark study,”  Mechanical Systems and Signal Processing, vol. 64, pp. 100–131, 2015.
  * [33] W. Zhang, G. Peng, C. Li, Y. Chen, and Z. Zhang,  “A new deep learning model for fault diagnosis with good anti-noise and domain adaptation ability on raw vibration signals,”  Sensors, vol. 17, no. 2, pp. 425, 2017.
  * [34] Garrett Wilson, Janardhan Rao Doppa, and Diane J. Cook,  “Multi-source deep domain adaptation with weak supervision for time-series sensor data,”  in SIGKDD, 2020.
  * [35] Y. Liu, Y-M. Zhang, X-Y. Zhang, and C-L. Liu,  “Adaptive spatial pooling for image classification,”  Pattern Recognition, vol. 55, pp. 58–67, 2016.


# Lightweight Encryption and Anonymous Routing in NoC based SoCs

Subodha Charles, and Prabhat Mishra An early version of this work has appeared
as a non-reviewed book chapter for the general audience [1].S. Charles is with
the Department of Electronic and Telecommunication Engineering, University of
Moratuwa, Colombo, Sri Lanka. e-mail<EMAIL_ADDRESS>Mishra is with the
Department of Computer & Information Science & Engineering, University of
Florida, Gainesville, Florida, USA. e-mail<EMAIL_ADDRESS>
###### Abstract

Advances in manufacturing technologies have enabled System-on-Chip (SoC)
designers to integrate an increasing number of cores on a single SoC.
Increasing SoC complexity coupled with tight time-to-market deadlines has led
to increased utilization of Intellectual Property (IP) cores from third-party
vendors. SoC supply chain is widely acknowledged as a major source of security
vulnerabilities. Potentially malicious third-party IPs integrated on the same
Network-on-Chip (NoC) with the trusted components can lead to security and
trust concerns. While secure communication is a well-studied problem in the
computer networks domain, it is not feasible to implement those solutions on
resource-constrained SoCs. In this paper, we present a lightweight encryption
and anonymous routing protocol for communication between IP cores in NoC based
SoCs. Our method eliminates the major overhead associated with traditional
encryption and anonymous routing protocols using a novel secret sharing
mechanism while ensuring that the desired security goals are met. Experimental
results demonstrate that existing security solutions on NoC can introduce
significant (1.5X) performance degradation, whereas our approach provides the
same security features with minor (4%) impact on performance.

###### Index Terms:

Encryption, Anonymous Routing, Network-on-Chip, System-on-Chip, Hardware
Security

##  I Introduction

The growth of general purpose as well as embedded computing devices has been
remarkable over the past decade. This was mainly enabled by the advances in
manufacturing technologies that allowed the integration of many heterogeneous
components on a single System-on-Chip (SoC). The tight time-to-market
deadlines and increasing complexity of modern SoCs have led manufacturers to
outsource intellectual property (IP) cores from potentially untrusted third-
party vendors [2, 3]. Therefore, the trusted computing base of the SoC should
exclude the third-party IPs. In fact, measures should be taken since malicious
third-party IPs (M3PIP) can launch passive as well as active attacks on the
SoC [4]. Such attacks are possible primarily because the on-chip
interconnection network that connects SoC components together, popularly known
as Network-on-Chip (NoC), has visibility of the entire SoC and the
communications between IP cores. Previous efforts have developed
countermeasures against stealing information [5], snooping attacks [6], and
even causing performance degradation by launching denial-of-service (DoS)
attacks [7]. In this paper, we present a countermeasure for M3PIPs operating
under the following architecture and threat models.

Threat Model:  Figure 1 shows an SoC with heterogeneous IPs integrated on a
Mesh NoC. The two nodes marked as $S$ (source) and $D$ (destination) are
trusted IPs communicating with each other. M3PIPs integrated on the SoC (nodes
shown in red) have the following capabilities when packets pass through their
routers:

  * •

They can steal information if data is sent as plaintext.

  * •

If data is encrypted and header information is kept as plaintext, they can
gather packets generated from the same source and intended to the same
destination and launch complex attacks such as linear/differential
cryptanalysis since they belong to the same communication session.

  * •

When multiple M3PIPs are present on the same NoC, they can share information
and trace messages.

  * •

An M3PIP can compromise the router attached to it and gather information
stored in the router. This can leak routing information. Assuming only some of
the IPs are acquired from untrusted third-party vendors, all routers will
never be compromised at the same time.

Figure 1: Overview of a typical SoC architecture with IPs integrated on a Mesh
NoC.

It is not feasible to utilize traditional security methods (encryption,
authentication, etc.) in resource-constrained embedded devices. Previous
studies explored lightweight security architectures to mitigate threats.
Previous work on lightweight encryption proposed smaller block and key sizes,
less rounds of encryption and other hardware optimizations [8]. Irrespective
of the optimizations, these methods still have complex computations that take
several cycles. In this paper, we propose a Lightweight Encryption and
Anonymous Routing protocol for NoCs (LEARN) that requires only few addition
and multiplication operations for encryption. We are able to eliminate the
traditional encryption methods consisting of ciphers and keys entirely by
using the secret sharing approach proposed by Shamir [9] without compromising
the security guarantees. Furthermore, our framework supports anonymous routing
such that an intermediate node can neither detect the origin nor the
destination of a packet. Major contributions of this paper can be summarized
as follows:

  * •

We propose an anonymous routing scheme that hides both source and destination
information making the packets untraceable. Launching attacks on encrypted
data passing through a given router becomes more difficult when the packets
are untraceable and origins are unknown.

  * •

We develop a lightweight encryption scheme that is based on secret sharing.

  * •

We demonstrate that our approach is lightweight compared to existing
encryption methods as well as traditional anonymous routing methods such as
onion routing.

The remainder of the paper is organized as follows. Section II introduces some
concepts used in this paper and presents related efforts. Section III
motivates the need for our work. Section IV describes our lightweight
encryption and anonymous routing protocol. Section V presents the experimental
results. Section VI discusses possible further enhancements to our approach.
Finally, Section VII concludes the paper.

##  II Background and Related Work

This section introduces some of the key concepts used in our proposed
framework. The first three sections introduce symmetric and asymmetric
encryption, Lagrangian polynomial based interpolation and anonymous routing.
The last section discusses prior work in lightweight encryption and anonymous
routing to explain how our proposed approach differs from them.

###  II-A Symmetric and Asymmetric Encryption

Symmetric Encryption:  A symmetric encryption scheme takes the same key $K$
for both decryption and encryption. The encryption algorithm $E$ produces the
ciphertext $C$ by taking the key $K$ and a plaintext $M$ as inputs, This is
denoted by $C\leftarrow E_{K}(M)$. Similarly, the decryption algorithm $D$
denoted by $M\leftarrow D_{K}(C)$, takes a key $K$ and a ciphertext $C$ and
returns the corresponding $M$. The correctness of the scheme is confirmed when
any sequence of messages $M_{1},...,M_{u}$ encrypted under a given key $K$
produces $C_{1}\leftarrow E_{K}(M_{1})$, $C_{2}\leftarrow E_{K}(M_{2})$,…,
$C_{u}\leftarrow E_{K}(M_{u})$, and is related as $D_{K}(C_{i})=M_{i}$ for
each $C_{i}$.

Asymmetric Encryption:  In asymmetric encryption, also known as public key
encryption, different keys are used for encryption and decryption. Encryption
is done using the public key that is publicly known by all the entities in the
environment. An entity $B$ that wants to send a message $M$ to another entity
$A$ will encrypt the message using $A$’s public key (with public key $PK_{A}$)
to produce ciphertext $C$ denoted by $C\leftarrow E_{PK_{A}}(M)$. The
ciphertext can only be decrypted by $A$’s secret key (private key) $SK_{A}$
corresponding to $PK_{A}$. $SK_{A}$ is known by only $A$, and therefore, only
$A$ can decrypt $C$ to produce $M$ denoted by $M\leftarrow D_{SK_{A}}(C)$.

###  II-B Secret Sharing with Polynomial Interpolation

Shamir’s secret sharing [9] is based on a property of Lagrange polynomials
known as the $(k,n)$ threshold. It specifies that a certain secret $M$ can be
broken into $n$ parts and $M$ can only be recovered if at least $k$ $(k\leq
n)$ parts are retrieved. The knowledge of less than $k$ parts leave $M$
completely unknown. Lagrange polynomials meet this property with $k=n$. A
Lagrange polynomial is comprised of some $k$ points $(x_{0},y_{0})$, …,
$(x_{k-1},y_{k-1})$ where $x_{i}\neq x_{j}$ $(0\leq i,j\leq k-1)$. A unique
polynomial of degree $k-1$ can be calculated from these points:

$L(x)=\sum_{j=0}^{k-1}l_{j}(x)\cdot y_{j},$ (1)

where

$l_{j}(x)=\prod_{i=0,i\neq j}^{k-1}\frac{x-x_{i}}{x_{j}-x_{i}}$ (2)

Any attempt to reconstruct the polynomial with less than $k$ or incorrect
points will give the incorrect polynomial with the wrong coefficients and/or
wrong degree.

$L(x)$ forms the interpolated Lagrange polynomial, and $l_{j}(x)$ is the
Lagrange basis polynomial. In order to a share a secret using this method, a
random polynomial of degree $k-1$ is chosen. It takes the form of
$L(x)=a_{0}+a_{1}x+a_{2}x^{2}+...+a_{k-1}x^{k-1}$. The shared secret $M$
should be set as $a_{0}=M$, and all the other coefficients are chosen
randomly. Then a simple calculation at $x=0$ would yield the secret
($M=L(0)$). In this case, $k$ points on the curve are chosen at random and
distributed together with their respective $l_{j}(0)$ values - the Lagrangian
coefficients. To retrieve $M$, all the parties should share their portions of
the secrets. Once all of the $k$ points and $l_{j}(0)$ coefficients are
combined, then the secret can be computed as:

$M=\sum_{j=0}^{k-1}l_{j}(0)\cdot y_{j},$ (3)

This method makes it easier to compute M without having to recalculate each
$l_{j}(x)$.

###  II-C Anonymous Communication using Onion Routing

Onion routing is widely used in the domain of computer networks when routing
has to be done while keeping the sender anonymous. Each message is encrypted
several times (layers of encryption) analogous to layers of an onion. Each
intermediate router from source to destination (called onion routers) “peels”
a single layer of encryption revealing the next hop. The final layer is
decrypted and message is read at the destination. The identity of the sender
is preserved since each intermediate router only knows the preceding and the
following routers. The overhead of onion routing comes from the fact that the
sender has to do several rounds of encryption before sending the packet to the
network and each intermediate router has to do a decryption before forwarding
it to the next hop. While this can be done in computer networks, adopting this
in resource-constrained NoCs leads to unacceptable performance overhead as
illustrated in Section III.

###  II-D Related Work

The current state-of-the-art in NoC security revolves around protecting
information traveling in the network against side channel [10], physical [11]
and software attacks [12]. Other attacks such as denial-of-service [13, 14]
and buffer overflow [15, 16] have also been explored. However, developing
efficient and flexible solutions at lower costs and minimal impact on
performance as well as how to certify these solutions remain as challenges to
the industry. It is not feasible to adopt the security mechanisms used in the
computer networks domain in NoC based SoCs due to the resource-constrained
nature of embedded devices [17, 18]. Security has to be considered in the
context of other non-functional requirements such as performance, power and
area. The obvious extension is to optimize these security mechanisms to fit
the performance and power budgets of embedded systems. This thought process
has led to prior efforts on securing NoC-based SoC [19, 5, 12], which tried to
eliminate complex encryption schemes such as AES and replace them with
lightweight encryption schemes. Intel’s TinyCrypt, a cryptographic library
with a small footprint, is built for resource constrained devices [20]. It
provides basic functionality to build a secure system with minor overhead. It
provides SHA-256 hash functions, message authentication, a psuedo-random
number generator which can run using minimal memory, encryption, and the
ability to create nonces111A nonce is a random number that is used only once
during the lifetime of a cryptographic operation. and challenges. Apart form
Intel TinyCrypt, several researches have proposed other lightweight encryption
solutions in the Internet-of-Things (IoT) domain [21, 22]. However, all of
these solutions follow the traditional encryption method which takes a key and
a plaintext as inputs to produce the ciphertext. The complex cryptographic
operations required for such methods incur considerable overhead. In contrast,
we propose a method where each router along the routing path contributes a
portion of the message such that the message changes at each router and only
the destination receives the entire message. This can be implemented using
very few addition and multiplication operations leading to a lightweight
solution for secure communication.

Existing work on anonymous routing (e.g., onion routing, mix-nets, dining
cryptographers, etc.) considers mobile ad-hoc networks (MANETS) [23, 24, 25]
as well as computer and vehicular networks [26]. The idea behind the widely
used onion routing is explained in Section II-C. The main challenge in using
these anonymous routing protocols in resource-constrained SoCs is that the
protocol uses decryption (“peeling the onion”) at each hop leading to
unacceptable performance overhead. Optimized anonymous routing protocols in
MANETS (e.g., [24]) use an on-demand lightweight anonymous routing protocol
that eliminates per-hop decryption. However, the MANETS environment is
fundamentally different from an NoC. Their work cannot address the unique
communication requirements of an NoC as well as not designed for task-
migration and context switching. To the best of our knowledge, our work is the
first attempt in developing an anonymous routing protocol for NoC based SoCs.

##  III Motivation

Security and performance is always a trade-off in resource-constrained
systems. While computer networks with potentially unlimited resources can
accommodate very strong security techniques such as AES encryption and onion
routing, utilizing them in resource-constrained NoCs can lead to unacceptable
overhead. To evaluate this impact, we ran FFT, RADIX (RDX), FMM and LU
benchmarks from the SPLASH-2 benchmark suite [27] on an $8\times 8$ Mesh NoC-
based SoC with 64 IPs using the gem5 simulator [28] considering three
scenarios:

  * •

No-Security: NoC does not implement encryption or anonymous routing.

  * •

Enc-only: NoC secures data by encrypting before sending into the network.
However, it does not support anonymous routing.

  * •

Enc-and-AR: Data encryption as well as anonymous routing achieved by onion
routing.

We assumed a 12-cycle delay for encryption/decryption when simulating Enc-only
and Enc-and-AR according to the evaluations in [19]. More details about the
experimental setup is given in Section V-A. Results are shown in Figure 2. The
values are normalized to the scenario that consumes the most time. Enc-only
shows 42% (40% on average) increase in NoC delay (total NoC traversal delay
for all packets) and 9% (7% on average) increase in execution time compared to
the No-Security implementation. Enc-and-AR gives worse results with 83% (81%
on average) increase in NoC delay leading to a 41% (33% on average) increase
in execution time when compared with No-Security. In other words, Enc-and-AR
leads to approximately 1.5X performance degradation. When security is
considered, No-Security leaves the data totally vulnerable to attackers, Enc-
only secures the data by encryption and Enc-and-AR provides an additional
layer of security with anonymous routing. The overhead of Enc-only is caused
by the complex mathematical operations, and the number of cycles required to
encrypt each packet. Onion routing used in Enc-and-AR aggravates this by
requiring several rounds of encryption before injecting the packet into the
network as well as decryption at each hop (router). Added security has less
impact on execution time compared to NoC delay since execution time also
includes the time for instruction execution and memory operations in addition
to NoC delay. In many embedded systems, it would be unacceptable to have
security at the cost of 1.5X performance degradation. It would be ideal if the
security provided by Enc-and-AR can be achieved while maintaining performance
comparable to No-security. Our approach tries to achieve this goal by
introducing a lightweight encryption and anonymous routing protocol as
described in the next section.

(a) NoC delay

(b) Execution time

Figure 2: NoC delay and execution time comparison across different levels of
security.

##  IV Lightweight Encryption and Anonymous Routing Protocol

This section describes our proposed approach - Lightweight Encryption and
Anonymous Routing protocol for NoCs (LEARN). By utilizing secret sharing based
on polynomial interpolation [9], LEARN negates the need for complex
cryptographic operations to encrypt messages. A forwarding node would only
have to compute the low overhead addition and multiplication operations to
hide the contents of the message. As the message passes through the forwarding
path, its appearance is changed at each node, which makes the message’s
content and route safe from eavesdropping attackers as well as internal ones.
The following sections describe our approach in detail. First, we provide an
overview of our framework in Section IV-A. Next, Section IV-B and Section IV-C
describe the two major components of our proposed routing protocol (route
discovery and data transfer). Finally, Section IV-D outlines how to
efficiently manage relevant parameters during anonymous routing.

Figure 3: Overview of our proposed framework (LEARN)

###  IV-A Overview

LEARN has two main phases as shown in Figure 3. When an IP wants to
communicate with another IP, it first completes the “Route Discovery” phase.
The route discovery phase sends a packet and discovers the route, distributes
the parameters among participants. Then the “Data Transfer” phase transfers
the message securely and anonymously. The route discovery phase includes a
three-way handshake between the sender and the destination nodes. The
handshake uses 3 out of the 4 main types of packets sent over the network with
the fourth type being used in the second phase. The 4 main packet types are:

  1. 1.

$RI$ (Route Initiate) - flooded packet from sender $S$ to destination $D$ to
initialize the conversation.

  2. 2.

$RA$ (Route Accept) - packet sent from $D$ to accept new connection with $S$.

  3. 3.

$RC$ (Route Confirmation) - sent from $S$ to distribute configuration
parameters with intermediate nodes.

  4. 4.

$DT$ (Data) - the data packet from $S$ to $D$ that is routed anonymously
through the NoC.

Algorithm 1 outlines the major steps of LEARN. During the three-way handshake,
a route between $S$ and $D$ is discovered. Each router along the routing path
is assigned with few parameters that are used when transferring data - (i)
random nonces to represent preceding and following routers (line 3), and (ii)
a point in a random polynomial together with its Lagrangian coefficient (line
4). This marks the end of the first phase which enables the second phase -
“Data Transfer”. The second phase uses the parameters assigned to each router
to forward the original message through the route anonymously while hiding its
contents. Anonymous routing is achieved by using the random nonces which act
as virtual circuit numbers (VCN). When transferring data packets, the
intermediate routers will only see the VCNs corresponding to the preceding
router and the following router which reveals no information about the source
or the destination (line 8). Encryption is achieved using the points in the
random polynomial and their corresponding Lagrangian coefficients. Each router
along the path changes the contents of the message in such a way that only the
final destination will be able to retrieve the entire message (line 7).

Algorithm 1 \- Major steps of LEARN

1:Phase I - Route Discovery

2:for all $r\in$ routers do

3: $r\leftarrow\upsilon_{i},\upsilon_{j}$ $\triangleright$ nonces to identify
VCNs

4: $r\leftarrow(x_{k},y_{k},b_{k})$ $\triangleright$ a point in a random
polynomial

5:Phase II - Data Transfer

6:while $r\neq destination$ do

7: $m\leftarrow{\cal F}(m,(x_{k},y_{k},b_{k}))$ $\triangleright$ modify
message

8: $r\leftarrow getNextHop(\upsilon_{i},\upsilon_{j})$ $\triangleright$ get
next hop

LEARN improves performance by replacing complex cryptographic operations with
addition/multiplication operations that consume significantly less time during
the data transfer phase. The overhead occurs during the first phase (route
discovery) that requires cryptographic operations. However, this is performed
only a constant number of times (once per communication session). Since the
route discovery phase happens only once in the beginning of a communication
session, the cost for route discovery gets amortized over time. This leads to
significant performance improvement.

Note that the route discovered at the route discovery stage will remain the
same for the lifetime of the task. In case of context switching and/or task
migration, the first phase will be repeated before transferring data. Each IP
in the SoC that uses the NoC to communicate with other IPs follows the same
procedure. The next two sections describe these two phases in detail. A list
of notations used to illustrate the idea is listed in Table I. The superscript
“$i$” is used to indicate that the parameter is changed for each packet of a
given packet type.

TABLE I: Notations used to illustrate LEARN $OPK_{S}^{(i)}$ |  one-time public key (OPK) used by the source to uniquely identify an $RA$ packet
---|---
$OSK_{S}^{(i)}$ |  | private key corresponding to $OPK_{S}^{(i)}$
---
$\rho$ |  random number generated by the source
$PK_{D}$ |  the global public key of the destination
$SK_{D}$ |  | the private key corresponding to $PK_{D}$
---
$TPK_{A}^{(i)}$ |  temporary public key of node $A$
$TSK_{A}^{(i)}$ |  | the private key corresponding to $TPK_{A}^{(i)}$
---
$K_{S-A}$ |  symmetric key shared between $S$ and $A$
$\upsilon_{A}$ |  randomly generated nonce by node $A$
$b_{i}$ |  | Lagrangian coefficient of a given point $(x_{i},y_{i})$
---
$E_{K}(M)$ |  a message $M$ encrypted using the key $K$

###  IV-B Route Discovery

The route discovery phase performs a three-way handshake between the sender
$S$ and destination $D$. This includes broadcasting the first packet - RI from
$S$ with the destination $D$, getting a response (RA) from $D$ acknowledging
the reception of RI, and finally, sending RC with the parameters required to
implement polynomial interpolation based secret sharing. Figure 4 shows an
illustrative example of parameters (using only four nodes) shared and stored
during the handshake.

Figure 4: Steps of the three-way handshake and the status of parameters at the
end of the process.

The initial route initiate packet ($RI$) takes the form:

$\\{RI\>\|\>OPK_{S}^{(i)}\>\|\>E_{PK_{D}}(OPK_{S}^{(i)}\>\|\>\rho)\>\|\>TPK_{S}^{(i)}\\}$

The first part of the message indicates the type of packet being sent, $RI$ in
this case. $OPK_{S}^{(i)}$ refers to the one-time public key associated with
the sender node. This public key together with its corresponding private key
$OSK_{S}^{(i)}$ change with each new conversation or $RI$. This change allows
for a particular conversation to be uniquely identified by these keys, which
are saved in its route request table. $\rho$ is a randomly generated number by
the sender that is concatenated with the $OPK_{S}^{(i)}$ and then encrypted
with the destination node’s public key $PK_{D}$ as a global trapdoor [29].
Since $PK_{D}$ is used to encrypt, only the destination is able to open the
trapdoor using $SK_{D}$. Then the $TPK_{S}^{(i)}$ is attached to show the
temporary key of the forwarding node, which is initially the sender. The
temporary keys are also implemented as one-time trapdoors to ensure security.

The next node, $r1$, to receive the $RI$ messages goes through a few basic
steps. Firstly, it checks for the $OPK_{S}^{(i)}$ in its key mapping table,
which would indicate a duplicated message. Any duplicates are discarded at
this step. Next, $r1$ will attempt to decrypt the message and retrieve $\rho$.
Success would indicate that $r1$ was the intended recipient $D$. If not, $r1$
replaces $TPK_{S}^{(i)}$ with its own temporary public key $TPK_{r1}^{(i)}$
and broadcasts:

$\\{RI\>\|\>OPK_{S}^{(i)}\>\|\>E_{PK_{D}}(OPK_{S}^{(i)}\>\|\>\rho)\>\|\>TPK_{r1}^{(i)}\\}$

$r1$ also logs $OPK_{S}^{(i)}$ and $TPK_{S}^{(i)}$ from the received message
and $TSK_{r1}^{(i)}$ corresponding to $TPK_{r1}^{(i)}$ in its key mapping
table. This information is used later when an $RA$ message is received from
$D$.

$D$ will eventually receive the $RI$ message and will decrypt using $SK_{D}$.
This will allow $D$ to retrieve $OPK_{S}^{(i)}$ and $\rho$ from
$E_{PK_{D}}(OPK_{S}^{(i)}\>\|\>\rho)$. Then to verify that the $RI$ has not
been tampered with, $D$ will compare the plaintext $OPK_{S}^{(i)}$ and the now
decrypted $OPK_{S}^{(i)}$. If they are different, the $RI$ is simply
discarded. Otherwise, $D$ sends a $RA$ (route accept) message:

$\\{RA\>\|\>E_{TPK_{r2}^{(i)}}(E_{OPK_{S}^{(i)}}(\rho\>\|\>\upsilon_{D}\>\|\>K_{S-D}))\\}$
(4)

$RA$, like $RI$ in the previous message, is there to indicate message type.
$D$ generates a random nonce, $\upsilon_{D}$, to serve as a VCN and a randomly
selected key $K_{S-D}$ to act as a symmetric key between $S$ and $D$. $D$
stores $\upsilon_{D}$ and $K_{S-D}$ in its key mapping table. It also makes an
entry in its routing table indexed by $\upsilon_{D}$, the VCN. The
concatenation of $\rho$, $\upsilon_{D}$, and $K_{S-D}$ is then encrypted with
the $OPK_{S}^{(i)}$, so that only $S$ can access that information. Then the
message is encrypted again by $TPK_{r2}^{(i)}$, $r2$’s temporary public key,
with $r2$ being the node that delivered $RI$ to $D$.

Once $r2$ receives the $RA$, it decrypts it using its temporary private key,
$TSK_{r2}^{(i)}$, and follows the same steps as $D$. It generates its own
nonce, $\upsilon_{r2}$, and shared symmetric key, $K_{S-r2}$, to be shared
with $S$. Both the nonce and symmetric key are then concatenated to the $RA$
message and encrypted by $S$’s public key, $OPK_{S}^{(i)}$, so that only $S$
can retrieve that data. This adds another layer of encrypted content to the
message for $S$ to decrypt using $OSK_{S}^{(i)}$. Similar to $D$, $r2$ also
stores $\upsilon_{r2}$ and $K_{S-r2}$ in its key mapping table and routing
table. It then finds the temporary public key for the previous node in the
path from its key mapping table - $TPK_{r1}^{(i)}$ and encrypts the message.
The message sent out by $r2$ looks like:

$\\{RA\>\|\>E_{TPK_{r1}^{(i)}}(E_{OPK_{S}^{(i)}}(E_{OPK_{S}^{(i)}}(\rho\>\|\>\upsilon_{D}\>\|\>K_{S-D})\\\
\>\|\>\upsilon_{r2}\>\|\>K_{S-r2}))\\}$ (5)

This process is repeated at each node along the path until the $RA$ packet
makes it way back to $S$. The entire message at that point is encrypted with
$TPK_{S}^{(i)}$, which is stripped away using $TSK_{S}^{(i)}$. Then $S$ can
“peel” each layer of the encrypted message by $OSK_{S}^{(i)}$ to retrieved all
the VCNs, shared symmetric keys, and also, $\rho$. $\rho$ is used to
authenticate that the entire message came from the correct destination and was
not changed during the journey.

Once $S$ completes authentication of the received RA packet, it randomly
generates $k+1$ points $(x_{0},y_{0}),(x_{1},y_{1}),...,(x_{k},y_{k})$ on a
$k$ degree polynomial $L(x)$ as shown in Figure 5. $k+1$ is the number of
nodes in the path from $S$ to $D$. $S$ then uses these points to calculate the
Lagrangian coefficients, $b_{0},b_{1},...,b_{k}$, using:

$b_{j}=\prod_{i=0,i\neq j}^{k}\frac{x_{i}}{x_{i}-x_{j}}$ (6)

Using the generated data, $S$ constructs a route confirmation (RC) packet:

$\\{RC\>\|\>\upsilon_{r1}\>\|\>E_{K_{S-r1}}(x_{1}\>\|\>y_{1}\>\|\>b_{1}\>\|\>\upsilon_{r2}\>\|\>E_{K_{S-r2}}(x_{2}\>\|\>y_{2}\\\
\>\|\>b_{2}\>\|\>\upsilon_{D}\>\|\>E_{K_{S-D}}(x_{3}\>\|\>y_{3}\>\|\>b_{3})))\\}$
(7)

Similar to the case in RA and RI, RC in the packet refers to the packet type.
The rest of the message is layered much like the previous $RA$ packet. Each
layer contains the $\upsilon_{*}$ for each node concatenated with secret
information that is encrypted with the shared key $K_{S-*}$, where *
corresponds to $r1,r2$ or $D$ in our example (Figure 4). The ($\upsilon_{*}$,
$K_{S-*}$) pair was generated by each node during the RA packet transfer phase
and the values were stored in the key mapping tables as well as entries
indexed by the VCNs created in the routing table. Therefore, each node can
decrypt one layer, store incoming and outgoing VCNs together with the secret,
and pass it on to the next node to do the same. For example, $r1$ receiving
the packet can observe that the incoming VCN is $\upsilon_{r1}$. It then
decrypts the first layer using the symmetric key $K_{S-r1}$, that is already
stored in the key mapping table, and recovers the secret $(x_{1},y_{1},b_{1})$
as well as the outgoing VCN $\upsilon_{r2}$. It then updates the entry indexed
by $\upsilon_{r1}$ in its routing table with the secret tuple and the outgoing
VCN. Similarly, each router from $S$ to $D$ can build its routing table.

Figure 5: Lagrangian polynomials $L(x)$ and $L^{\prime}(x)$ together with the
selected points.

###  IV-C Data Transfer

The path set up can now be used to transfer messages from $S$ to $D$
anonymously. For each conversation, $k+1$ points were generated on a random
curve $L(x)$ chosen by $S$. During the last step of the route discovery phase
(RC packet), $S$ kept $(x_{0},y_{0},b_{0})$ for itself and distributed each
node on the discovered path a different point, $(x_{i},y_{i})$ (where $1\leq
i\leq k$), with the corresponding Lagrangian coefficient $b_{i}$. If $S$ wants
to send the message $M$ to $D$, $S$ has to generate a new $k$ degree
polynomial $L^{\prime}(x)$ which is defined by the $k$ points distributed to
nodes except for $(x_{0},y_{0})$, i.e., points $(x_{i},y_{i})$ where $(1\leq
i\leq k)$ and a new point $(0,M)$. This makes $L^{\prime}(0)=M$ with $M$ as
the secret message, according to the explanation in Section II-B. $S$ then
changes its own point $(x_{0},y_{0})$ to $(x_{0},y^{\prime}_{0}$) where
$y^{\prime}_{0}=L^{\prime}(x_{0})$, making sure the point retained by $S$ is
also on the curve L’(x) as shown in Figure 5. It is important to note that
every coefficient $b_{i}$, and every point distributed to nodes along the
route remain unchanged. For this scenario, considering Equation 3, we can
derive:

$M=y^{\prime}_{0}b_{0}+\sum_{i=1}^{k}b_{i}\cdot y_{i}$ (8)

To transfer a secret message, $M$, from $S$ to $D$ anonymously, $S$ constructs
data transfer ($DT$) packet with the form:

$\\{DT\>\|\>\upsilon_{r1}\>\|\>y^{\prime}_{0}b_{0}\\}$ (9)

$DT$, like every other packet, has an indicator of packet type at the front of
the packet - $DT$. $\upsilon_{r1}$ is the VCN of the next node.
$y^{\prime}_{0}b_{0}$ is the portion of the message $M$ that is constructed by
$S$. Once $r1$ receives the $DT$ packet, it adds its own portion of the
message, $y_{1}b_{1}$, to $y^{\prime}_{0}b_{0}$. It also uses its routing
table to find the VCN of the next node and replaces the incoming VCN by the
outgoing VCN in the $DT$ packet. Therefore, the message received by $r2$ has
the form:

$\\{DT\>\|\>\upsilon_{r2}\>\|\>y^{\prime}_{0}b_{0}+y_{1}b_{1}\\}$ (10)

Next, $r2$ repeats the same process and forwards the packet:

$\\{DT\>\|\>\upsilon_{D}\>\|\>y^{\prime}_{0}b_{0}+y_{1}b_{1}+y_{2}b_{2}\\}$
(11)

to $D$. Eventually, $D$ will be able to retrieve the secret message,
$M=y^{\prime}_{0}b_{0}+y_{1}b_{1}+y_{2}b_{2}+y_{3}b_{3}$ by adding the last
portion $y_{3}b_{3}$ constructed using the part of the secret $D$ shared.
Using this method, neither an intermediate node nor an eavesdropper in the
middle will be able to see the full message since the message $M$ is
incomplete at every intermediate node and is fully constructed only at the
destination $D$.

###  IV-D Parameter Management

To ensure the efficient implementation of LEARN, an important aspect needs to
be addressed - the generation and management of keys and nonces. However, this
is beyond the scope of this paper and many previous studies have addressed
this problem in several ways. One such example is the work done by Lebiednik
et al. [30]. In their work, a separate IP called the key distribution center
(KDC) handles the distribution of keys. Each node in the network negotiates a
new key with the KDC using a pre-shared portion of memory that is known by
only the KDC and the corresponding node. The node then communicates with the
KDC using this unique key whenever it wants to obtain a new key. The KDC can
then allocate keys depending on whether it is symmetric/asymmetric encryption,
and inform other nodes as required. The key request can delay the
communication. But once keys are established, it can be used for many times
depending on the length of the encrypted packet before refreshing to prevent
linear distinguishing attacks. In our approach, the keys are only used during
the route discovery phase, and the discovered route will remain the same for
the lifetime of the task unless context switching or task migration happens.
Therefore, key refreshing will rarely happen and the cost for the initial key
agreement as well as the route discovery phase will be amortized.

##  V Experimental Results

This section presents results to evaluate the efficiency of our approach
(LEARN). We first describe the experimental setup. Next, we compare the
performance of LEARN with traditional encryption and anonymous routing
protocols introduced in Section III. Finally, we discuss the area overhead and
security aspects of LEARN.

###  V-A Experimental Setup

Extending the results presented in Figure 2, LEARN was tested on an $8\times
8$ Mesh NoC-based SoC with 64 IPs using the gem5 cycle-accurate full-system
simulator [28]. The NoC was built using the “GARNET2.0” model that is
integrated with gem5 [31, 18]. The route discovery phase of our approach
relies on the $RI,RA,$ and $RC$ packets traversing along the same path to
distribute the keys and nonces. Therefore, the topology requires bidirectional
links connecting the routers. While we experimented on a Mesh NoC, there are
many other NoC topologies that can adopt LEARN where all links are
bidirectional as evidenced by academic research [31] as well as commercial
SoCs [32].

Each encryption/decryption is modelled with a 12-cycle delay [19].
Computations related to generating the random polynomial and deciding the $k$
points is assumed to consume 200 cycles. To accurately capture congestion, the
NoC was modeled with 3-stage (buffer write, route compute + virtual channel
allocation + switch allocation, and link traversal) pipelined routers with
wormhole switching and 4 virtual channel buffers at each input port. Each link
was assumed to consume one cycle to transmit packets between neighboring
routers. The delays were chosen to be consistent with the delays of components
in the gem5 simulator.

We used the default gem5 and Garnet2.0 configurations for packet sizes,
virtual channels and flow control. In addition to the four main types of
packets described in Section IV-A, the $DT$ packets can be further divided
into two categories as control and data packets. For example, in case of a
cache miss, a memory request packet (control packet) is injected into the NoC
and the memory response packet (data packet) consists of the data block from
the memory. The address portion of a control $DT$ packet consists of 64 bits.
In the data $DT$ packet, in addition to the 64-bit address, 512 bits are
reserved for the data block. A credit-based, virtual channel flow control was
used in the architecture. Each data VC and control VC was allocated buffer
depths of 4 and 1, respectively.

LEARN was tested using 6 real benchmarks (FFT, RADIX, FMM, LU, OCEAN,
CHOLESKY) from the SPLASH-2 benchmark suite and 6 synthetic traffic patterns:
uniform random (URD), tornado (TRD), bit complement (BCT), bit reverse (BRS),
bit rotation (BRT), transpose (TPS).  Out of the 64 cores, 16 IPs were chosen
at random and each one of them instantiated an instance of the task. The
packets injected into the NoC when running the real benchmarks were the memory
requests/responses. We used 8 memory controllers that provide the interface to
off-chip memory which were placed on the boundary of the SoC. This memory
controller placement adheres to commercial SoC architectures such as Intel’s
Knights Landing (KNL) [32]. An example to illustrate the IP placement is shown
in Figure 6.

When running real benchmarks, the packets get injected to the NoC when there
are private cache misses and the frequency of that happening depends on the
characteristics of the benchmark. When running synthetic traffic patterns,
packets were injected into the NoC at the rate of 0.01 packets/node/cycle. For
synthetic traffic patterns, the destinations of injected packets were selected
based on the traffic pattern. For example, uniform random selected the
destination from the remaining IPs with equal probability whereas bit
complement, complemented the bits of the source address to get the destination
address, etc.. The choices made in the experiments were motivated by the
architecture/threat model and the behavior of the gem5 simulator. However,
LEARN can be used with any other NoC topology and task/memory controller
placement.

Figure 6: $8\times 8$ Mesh NoC architecture used to generate results including
trusted nodes running the tasks and communicating with memory controllers
while untrusted nodes can potentially have malicious IPs.

###  V-B Performance Evaluation

Figure 7 shows performance improvement LEARN can gain when running real
benchmarks. We compare the results from LEARN against the three scenarios
considered in Figure 2. Compared to the No-Security scenario, LEARN consumes
30% more time (28% on average) for NoC traversals (NoC delay) and that results
in only 5% (4% on average) increase in total execution time. Compared to Enc-
and-AR which also implements encryption and anonymous routing, LEARN improves
NoC delay by 76% (74% on average) and total execution time by 37% (30% on
average). We can observe from the results that the performance of LEARN is
even better than Enc-Only, which provides encryption without anonymous
routing. Overall, LEARN can provide encryption and anonymous routing consuming
only 4% performance overhead compared to the NoC that does not implement any
security features.

(a) NoC delay

(b) Execution time

Figure 7: NoC delay and execution time comparison across different security
levels using real benchmarks.

The same experiments were carried out using synthetic traffic traces, and
results are shown in Figure 8. Since synthetic traffic patterns only simulate
NoC traffic and do not include instruction execution and memory operations,
only NoC delay is shown in the figure. Compared to Enc-and-AR, LEARN improves
performance by 76% (72% on average).

Figure 8: NoC delay comparison across different levels of security when
running synthetic traffic patterns.

The performance improvement of LEARN comes from the fact that once the path
has been set up for the communication between any two IPs, the overhead caused
to securely communicate between the two IPs (data transfer phase) while
preserving route anonymity is much less. The notable overhead occurs at the
route discovery phase due to complex cryptographic operations. The
intermediate nodes encrypt/decrypt packets to exchange parameters securely.
Yet, these complex cryptographic operations are performed only a constant
number of times. Majority of the work is done at the source which selects
points to be distributed among intermediate nodes after constructing a curve,
calculates the Lagrangian coefficients of the selected points, and performs
several rounds of encryption/decryption during the three-way handshake. Once
the routing path is setup, packets can be forwarded from one router to the
other by a simple table look-up. No per-hop encryption and decryption is
required to preserve anonymity. The security of a message is ensured by
changing the original message at each node using a few addition and
multiplication operations which incur significantly fewer extra delays. Since
the route discovery phase happens only once during the lifetime of a task
unless context switching and/or task migration happens, and there is only a
limited number of communications going on between IPs in an SoC, the cost
during the route discovery phase gets amortized over time. When running real
benchmarks, we observed a packet ratio of 1:1:1:6325 on average for
$RI:RA:RC:DT$, respectively. For synthetic traffic patterns, the same ratio
was observed to be 1:1:1:1964. This leads to a significant performance
improvement compared to the traditional methods of encryption and anonymous
routing.

###  V-C Area Overhead of the Key Mapping Table

The key mapping table is an extra table compared to No-Security approach used
to implement our anonymous routing protocol. The key mapping table adds a row
for each session. Therefore, the size of the key mapping table is linearly
proportional to the number of sessions. If at design time, it is decided to
have a fixed size for the key mapping table, it is possible for the key
mapping table at a router to be full after adding sessions, and in that case,
new sessions cannot be added through that router. Therefore, the size has to
be decided according to the communication requirements.

The maximum number of communication pairs in an $8\times 8$ Mesh is
$\binom{64}{2}\times 2=4032$ (assuming two-way communication between any pair
out of the 64 nodes). Depending on the address mapping, only some node pairs
(out of all the possible node pairs) communicate. Our simulations consisted of
256 unique node pairs. In the worst case, if we assume each communication
session has one common router, the key mapping table should be $256\times
row\\_size$ big. If each entry in the key mapping table is 128 bits, the total
size becomes 20kB. However, in reality, not all communication sessions
overlap. It is also important to note that except for the Session ID in the
key mapping table, the other entries can be overwritten once route discovery
phase is complete. Therefore, it is possible to allocate a fixed size key
mapping table during design time and yet keep the area overhead low.

###  V-D Security Analysis

In this section, we discuss the security and privacy of messages transferred
on the NoC using LEARN.

Security of messages:  The security of messages is preserved by the $(k,n)$
threshold property of Lagrangian polynomials discussed in Section II-B.
Therefore, unless an intermediate node can gather all points distributed among
the routers in the routing path together with their Lagrangian coefficients,
the original message cannot be recovered. Our threat model states that the
source and destination are trusted IPs, and also, only some of the IPs are
untrusted. Therefore, all routers along the routing path will never be
compromised at the same time. The threat comes from malicious IPs sitting on
the routing path and eavesdropping to extract security critical information.
LEARN ensures that intermediate nodes that can be malicious, cannot recover
the original message during the data transfer phase by changing the message at
each hop. The complete message can only be constructed at the destination.
During route discovery phase, each packet is encrypted such that only the
intended recipient can decrypt it. The key and nonce exchange is also secured
according to the mechanism proposed in Section IV-D. Therefore, LEARN ensures
that no intermediate M3PIP can gather enough data to recover the plaintext
from messages.

Anonymity of nodes in the network:  LEARN preserves the anonymity of nodes in
the network during all of its operational phases. When the source sends the
initial RI packet to initiate the three-way handshake, it doesn’t use the
identity of the destination. Instead, the source uses the global public key of
the destination ($PK_{D}$) and sends a broadcast message on the network. When
the RI packet propagates through the network, each intermediate node saves a
temporary public key of its predecessor. This temporary public key is then
used to encrypt data when propagating the RA packet so that unicast messages
can be sent to preceding nodes without using their identities. Random nonces
and symmetric keys are assigned to each node during the RA packet propagation
which in turn is used by the RC packet to distribute points and Lagrangian
coefficients to each node. Data transfer is done by looking up the routing
table that consists of the nonces representing incoming and outgoing VCNs.
Therefore, the identities of the nodes are not revealed at any point during
communication.

Anonymity of routes taken by packets:  In addition to preserving the anonymity
of nodes, LEARN also ensures that the path taken by each packet is anonymous.
Anonymity of the routing path is ensured by two main characteristics. (i) The
message is changed at each hop. Therefore, even if there are two M3PIPs on the
same routing path, information exchange among the two M3PIPs will not help in
identifying whether the same message was passed through both of them. The same
message appears as two completely different messages when passing through two
different nodes. (ii) The routing table contains only the preceding and
following nodes along the routing path. An M3PIP compromising a router will
only reveal information about the next hop and the preceding hop. Therefore,
the routing paths of all packets remain anonymous.

##  VI Discussion

In this section, we discuss possible alternatives to our design choices from
both design overhead and security perspectives. Most importantly, we discuss
security solutions to defend against attacks when an attacker is aware of our
security mechanism.

###  VI-A Feasibility of a Separate Service NoC

Modern SoCs use multiple physical NoCs to carry different types of packets
[33, 32]. The KNL architecture used in Intel Xeon-Phi processor family uses
four parallel NoCs [32]. The Tilera TILE64 architecture uses five Mesh NoCs,
each used to transfer packets belonging to a certain packet type such as main
memory, communication with I/O devices, and user-level scalar operand and
stream communication between tiles [33]. The decision to implement separate
physical NoCs is dependent on the performance versus area trade-off. If only
one physical NoC is used to carry all types of packets, the packets must
contain header fields such as $RI,RA,RC,DT$ to distinguish between different
types. The buffer space is shared between different packet types. The SoC
performance can deteriorate significantly due to these factors coupled with
the increasing number of IPs in an SoC. On the other hand, contrary to
intuition, due to the advancements in chip fabrication processes, additional
wiring between nodes incur minimal overhead as long as the wires stay on-chip.
Furthermore, when wiring bandwidth and on-chip buffer capacity is compared,
the more expensive and scarce commodity is the on-chip buffer area. If
different packet types are carried on NoC using virtual channels and buffer
space is shared [34], the increased buffer spaces and logic complexity to
implement virtual channels becomes comparable to another physical NoC. A
comprehensive analysis of having virtual channels versus several physical NoCs
is given in [35].

It is possible to use two physical NoCs - one for data ($DT$) packet transfers
and the other to carry packets related to the handshake ($RI,RA,RC$). However,
in our setup, the potential performance improvement from a separate service
NoC was not enough to justify the area and power overhead. We envision that
our security mechanism to be a part of a suite of NoC security countermeasures
that can address other threat models such as denial-of-service, buffer
overflow, etc. The service NoC will be effective in such a scenario where more
service type packets (e.g., DoS attack detection related packets [7]) are
transferred through the NoC.

###  VI-B Obfuscating the Added Secret

An attacker who is aware of our security mechanism can try to infer a
communication path by observing the incoming and outgoing packets at a router.

Since each intermediate node adds a constant value ($y_{i}b_{i}$) to the
received DT packet, the difference between incoming and outgoing DT packets at
each node will be the same for a given virtual circuit. For this attack to
take place, two consecutive routers have to be infected by attackers and they
have to collaborate. Alternatively, a Trojan in a router has to have the
ability to observe both incoming and outgoing packets at the router. While
these are strong security assumptions, it is important to address this
loophole. In this Section, we propose a countermeasure against such an attack.
Even in the presence of such an attack, the secret message cannot be inferred
since the complete message is only constructed at the destination and
according to our threat model, we assume that the source and destination IPs
are trustworthy.

This can be solved by changing the shared secret at each node for each
message. However, generating and distributing secrets for each node per
message can incur significant performance overhead. Therefore, we propose a
solution based on each node updating its own secret. According to Equation 6,
to derive a new Lagrangian coefficient $b_{i}$, the $x$ coordinates should be
changed. The source can easily do it for each message by changing both $x_{0}$
and $y_{0}$ when a new message needs to be sent. In other words, rather than
changing the point ($x_{0}$,$y_{0}$) to ($x_{0}$,$y_{0}^{\prime}$), it should
be changed to ($x_{0}^{\prime}$,$y_{0}^{\prime}$). However, the new
$x_{0}^{\prime}$ now has to be sent to each intermediate node for them to be
able to calculate the new secrets using:

$b^{\prime}_{j}=b_{j}\cdot\frac{x^{\prime}_{0}}{x^{\prime}_{0}-x_{j}}\cdot\frac{x_{0}-x_{j}}{x_{0}}$
(12)

We want to avoid such communications for performance as well as security
concerns. An alternative is to use a function $\mathcal{F}(x_{0},\delta)$ that
can derive the next $x$-coordinate starting from the initial $x_{0}$.

$x_{0}^{\prime}=\mathcal{F}(x_{0},\delta)$ (13)

where $\mathcal{F}(x_{0},\delta)$ can be a simple incremental function such as
$\mathcal{F}(x_{0},\delta)=x+\delta$. $\delta$ can be a constant. To increase
security, $\delta$ can be picked using a psuedo-random number generator (PRNG)
seeded with the same value at each iteration. Using such a method will change
the shared secrets at each iteration and that will remove correlation between
incoming and outgoing packets at a node.

###  VI-C Hiding the Number of Layers

Another potential vulnerability introduced by our approach is that attackers
who are aware of our protocol, can infer how far they are from the source and
destination based on the size of the RA and RC packets. However, except for
the corner case where the source/destination are at the edge of a certain
topology, there can be more than one choice for potential source/destination
candidates. In our experiments, we use the Mesh topology in which from the
perspective of any node, there can be more than one node that is at distance
$d$ away. However, the attacker can reduce the set of possible
source/destination candidates for a given communication stream. Therefore,
depending on the security requirements, this vulnerability can be addressed
using the mechanism proposed in this section.

After receiving the RI Packet, when the $RA$ packet is initiated at $D$, $D$
generates $m$ $\langle$nonce, key$\rangle$ pairs
($\langle\upsilon_{D}^{1},K_{S-D}^{1}\rangle,\langle\upsilon_{D}^{2},K_{S-D}^{2}\rangle,...,\langle\upsilon_{D}^{m},K_{S-D}^{m}\rangle$)
and adds $m$ layers to the packet. As a result, the $RA$ packet sent from $D$
to $r2$ takes the form:

$\\{RA\>\|\>E_{TPK_{r2}^{(i)}}(E_{OPK_{S}^{(i)}}(...E_{OPK_{S}^{(i)}}(E_{OPK_{S}^{(i)}}(\rho\>\|\>\upsilon_{D}^{1}\\\
\>\|\>K_{S-D}^{1})\>\|\>\upsilon_{D}^{2}\>\|\>K_{S-D}^{2})...\>\|\>\upsilon_{D}^{m}\>\|\>K_{S-D}^{m}))\\}$

$D$ stores the $\langle$nonce, key$\rangle$ pairs in its key mapping table.
When $S$ receives the $RA$ packet, $S$ cannot distinguish whether the $m$
pairs were generated from multiple nodes or one node. Therefore, when the $RC$
packet is generated at $S$, instead of generating $k+1$ points (corresponding
to the number of nodes in the path), the number of generated points depends on
the number of $\langle$nonce, key$\rangle$ pairs received. During $RC$ packet
transfer, each intermediate node along the routing path stores points (VCNs
and secrets) corresponding to the nonces stored in the key mapping table. As a
result, nodes can receive multiple secrets which can then be used during the
data transfer phase. Depending on the required level of security, $m$ can vary
and also, each intermediate node can add multiple layers to the $RA$ packet.

This method hides the correlation between the number of nodes and the length
of the routing path, and therefore, eliminates the said vulnerability.
However, this increases the performance penalty. Figure 9 shows an extension
of Figure 7 which considers the modification proposed in Section VI-B and
Section VI-C. LEARN improves NoC delay by 69% (67% on average) and total
execution time by 34% (27% on average). Comparing with the results in Section
V-B, the average total execution time improvement has been reduced by 3% (from
30% on average to 27% on average) to accommodate the added security. Even
then, LEARN enables significant performance improvement compared to
traditional approaches.

(a) NoC delay

(b) Execution time

Figure 9: NoC delay and execution time comparison across different security
levels using real benchmarks considering the enhanced security features
outlined in Section VI-B and Section VI-C.

##  VII Conclusions

Security and privacy are paramount considerations during electronic
communication. Unfortunately, we cannot implement well-known security
solutions from computer networks on resource constrained SoCs in embedded
systems and IoT devices. Specifically, these security solutions can lead to
unacceptable performance overhead. In this paper, we proposed a lightweight
encryption and anonymous routing protocol that addresses the classical trade-
off between security and performance. Our approach uses a secret sharing based
mechanism to securely transfer data in an NoC based SoC. Packets are changed
at each hop and the complete packet is constructed only at the destination.
Therefore, an eavesdropper along the routing path is unable to recover the
plaintext of the intended message. Data is secured using only a few addition
and multiplication operations which allows us to eliminate complex
cryptographic operations that cause significant performance overhead. Our
anonymous routing protocol achieves superior performance compared to
traditional anonymous routing methods such as onion routing by eliminating the
need for per-hop decryption. Experimental results demonstrated that
implementation of existing security solutions on NoC can introduce significant
(1.5X) performance degradation, whereas our approach can provide the desired
security requirements with minor (4%) impact on performance.

## Acknowledgments

This work was partially supported by the National Science Foundation (NSF)
grant SaTC-1936040.

## References

  * [1] S. Charles and P. Mishra, “Lightweight anonymous routing for on-chip interconnects,” in _Network-on-Chip Security and Privacy_ , P. Mishra and S. Charles, Eds. Springer Nature, 2021\.
  * [2] Y. Huang, S. Bhunia, and P. Mishra, “Scalable test generation for trojan detection using side channel analysis,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 11, pp. 2746–2760, 2018.
  * [3] F. Farahmandi, Y. Huang, and P. Mishra, _System-on-Chip Security: Validation and Verification_. Springer Nature, 2019.
  * [4] P. Mishra, S. Bhunia, and M. Tehranipoor, _Hardware IP security and trust_. Springer, 2017.
  * [5] J. Sepúlveda, A. Zankl, D. Flórez, and G. Sigl, “Towards protected mpsoc communication for information protection against a malicious noc,” _Procedia computer science_ , vol. 108, pp. 1103–1112, 2017.
  * [6] S. V. R. Chittamuru, I. G. Thakkar, V. Bhat, and S. Pasricha, “SOTERIA: Exploiting process variations to enhance hardware security with photonic NoC architectures,” in _2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC)_. IEEE, 2018, pp. 1–6.
  * [7] S. Charles, Y. Lyu, and P. Mishra, “Real-time detection and localization of dos attacks in noc based socs,” in _2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 2019, pp. 1160–1165.
  * [8] H. K. Kapoor, G. B. Rao, S. Arshi, and G. Trivedi, “A security framework for noc using authenticated encryption and session keys,” _Circuits, Systems, and Signal Processing_ , vol. 32, no. 6, pp. 2605–2622, 2013.
  * [9] A. Shamir, “How to share a secret,” _Communications of the ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [10] C. Reinbrecht, A. Susin, L. Bossuet, G. Sigl, and J. Sepúlveda, “Side channel attack on noc-based mpsocs are practical: Noc prime+ probe attack,” in _Proceedings of the 29th Symposium on Integrated Circuits and Systems Design: Chip on the Mountains_. IEEE Press, 2016, p. 15.
  * [11] V. Y. Raparti and S. Pasricha, “Lightweight mitigation of hardware trojan attacks in noc-based manycore computing,” in _Proceedings of the 56th Annual Design Automation Conference 2019_. ACM, 2019, p. 48.
  * [12] D. M. Ancajas, K. Chakraborty, and S. Roy, “Fort-nocs: Mitigating the threat of a compromised noc,” in _Proceedings of the 51st Annual Design Automation Conference_. ACM, 2014, pp. 1–6.
  * [13] S. Charles, Y. Lyu, and P. Mishra, “Real-time detection and localization of distributed dos attacks in noc based socs,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2020.
  * [14] T. Boraten, D. DiTomaso, and A. K. Kodi, “Secure model checkers for network-on-chip (noc) architectures,” in _2016 International Great Lakes Symposium on VLSI (GLSVLSI)_. IEEE, 2016, pp. 45–50.
  * [15] S. Lukovic and N. Christianos, “Enhancing network-on-chip components to support security of processing elements,” in _Proceedings of the 5th Workshop on Embedded Systems Security_. ACM, 2010, p. 12.
  * [16] L. Fiorin, G. Palermo, and C. Silvano, “A security monitoring service for nocs,” in _Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis_. ACM, 2008, pp. 197–202.
  * [17] U. Y. Ogras, P. Bogdan, and R. Marculescu, “An analytical approach for network-on-chip performance analysis,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 29, no. 12, pp. 2001–2013, 2010.
  * [18] S. Charles, C. A. Patil, U. Y. Ogras, and P. Mishra, “Exploration of memory and cluster modes in directory-based many-core cmps,” in _IEEE/ACM International Symposium on Networks-on-Chip (NOCS)_. IEEE, 2018, pp. 1–8.
  * [19] K. Sajeesh and H. K. Kapoor, “An authenticated encryption based security framework for noc architectures,” in _2011 International Symposium on Electronic System Design_. IEEE, 2011, pp. 134–139.
  * [20] Intel, “Using TinyCrypt Library, Intel Developer Zone, Intel.” _Online. https://software.intel.com/en-us/node/734330_ , 2016.
  * [21] E. R. Naru, H. Saini, and M. Sharma, “A recent review on lightweight cryptography in IoT,” in _2017 International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud)(I-SMAC)_. IEEE, 2017, pp. 887–890.
  * [22] S. Babar, A. Stango, N. Prasad, J. Sen, and R. Prasad, “Proposed embedded security framework for internet of things (iot),” in _2011 2nd International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace & Electronic Systems Technology (Wireless VITAE)_. IEEE, 2011, pp. 1–5.
  * [23] J. Kong and X. Hong, “ANODR: anonymous on demand routing with untraceable routes for mobile ad-hoc networks,” in _Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing_. ACM, 2003, pp. 291–302.
  * [24] Y. Qin, D. Huang, and V. Kandiah, “OLAR: On-demand lightweight anonymous routing in MANETs,” in _Proc. Fourth Int’l Conf. Mobile Computing and Ubiquitous Networking (ICMU’08)_. Citeseer, 2008, pp. 72–79.
  * [25] W. Liu and M. Yu, “AASR: authenticated anonymous secure routing for MANETs in adversarial environments,” _IEEE transactions on vehicular technology_ , vol. 63, no. 9, pp. 4585–4593, 2014.
  * [26] W. Yuan, “An anonymous routing protocol with authenticated key establishment in wireless ad hoc networks,” _International Journal of Distributed Sensor Networks_ , vol. 10, no. 1, p. 212350, 2014.
  * [27] S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta, “The SPLASH-2 programs: Characterization and methodological considerations,” _ACM SIGARCH computer architecture news_ , vol. 23, no. 2, pp. 24–36, 1995.
  * [28] N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti _et al._ , “The gem5 simulator,” _ACM SIGARCH Computer Architecture News_ , vol. 39, no. 2, pp. 1–7, 2011.
  * [29] J. Katz, A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone, _Handbook of applied cryptography_. CRC press, 1996\.
  * [30] B. Lebiednik, S. Abadal, H. Kwon, and T. Krishna, “Architecting a secure wireless network-on-chip,” in _2018 Twelfth IEEE/ACM International Symposium on Networks-on-Chip (NOCS)_. IEEE, 2018, pp. 1–8.
  * [31] N. Agarwal, T. Krishna, L.-S. Peh, and N. K. Jha, “GARNET: A detailed on-chip network model inside a full-system simulator,” in _2009 IEEE international symposium on performance analysis of systems and software_. IEEE, 2009, pp. 33–42.
  * [32] A. Sodani, R. Gramunt, J. Corbal, H.-S. Kim, K. Vinod, S. Chinthamani, S. Hutsell, R. Agarwal, and Y.-C. Liu, “Knights landing: Second-generation intel xeon phi product,” _Ieee micro_ , vol. 36, no. 2, pp. 34–46, 2016\.
  * [33] D. Wentzlaff, P. Griffin, H. Hoffmann, L. Bao, B. Edwards, C. Ramey, M. Mattina, C.-C. Miao, J. F. Brown III, and A. Agarwal, “On-chip interconnection architecture of the tile processor,” _IEEE micro_ , vol. 27, no. 5, pp. 15–31, 2007.
  * [34] J.-P. Diguet, S. Evain, R. Vaslin, G. Gogniat, and E. Juin, “Noc-centric security of reconfigurable soc,” in _First International Symposium on Networks-on-Chip (NOCS’07)_. IEEE, 2007, pp. 223–232.
  * [35] Y. J. Yoon, N. Concer, M. Petracca, and L. P. Carloni, “Virtual channels and multiple physical networks: Two alternatives to improve noc performance,” _IEEE Transactions on computer-aided design of integrated circuits and systems_ , vol. 32, no. 12, pp. 1906–1919, 2013.

|  Subodha Charles is a Senior Lecturer in the Department of Electronics and
Telecommunications Engineering, University of Moratuwa, Sri Lanka. He received
his Ph.D in Computer Science from the University of Florida in 2020. His
research interests include hardware security and trust, embedded systems and
computer architecture.
---|---
|  Prabhat Mishra is a Professor in the Department of Computer and Information
Science and Engineering at the University of Florida. He received his Ph.D. in
Computer Science from the University of California at Irvine in 2004. His
research interests include embedded and cyber-physical systems, hardware
security and trust, computer architecture, energy-aware computing, formal
verification, system-on-chip validation, machine learning, and quantum
computing. He currently serves as an Associate Editor of ACM Transactions on
Embedded Computing Systems and IEEE Transactions on VLSI Systems. He is an
IEEE Fellow and ACM Distinguished Scientist.
---|---