# Gaussian Graph with Prototypical Contrastive Learning in E-Commerce Bundle
Recommendation

Zhao-Yang Liu  1234-5678-9012 ,  Liucheng Sun
<EMAIL_ADDRESS>Alibaba GroupHangzhouZhejiangChina ,
Chenwei Weng<EMAIL_ADDRESS>Alibaba
GroupHangzhouZhejiangChina ,  Qijin Chen<EMAIL_ADDRESS>Alibaba
GroupHangzhouZhejiangChina and  Chengfu Huo<EMAIL_ADDRESS>Alibaba GroupHangzhouZhejiangChina

###### Abstract.

Bundle recommendation aims to provide a bundle of items to satisfy the user
preference on e-commerce platform. Existing successful solutions are based on
the contrastive graph learning paradigm where graph neural networks (GNNs) are
employed to learn representations from user-level and bundle-level graph views
with a contrastive learning module to enhance the cooperative association
between different views. Nevertheless, they ignore the uncertainty issue which
has a significant impact in real bundle recommendation scenarios due to the
lack of discriminative information caused by highly sparsity or diversity. We
further suggest that their instance-wise contrastive learning fails to
distinguish the semantically similar negatives (i.e., sampling bias issue),
resulting in performance degradation.

In this paper, we propose a novel Gaussian Graph with Prototypi- cal
Contrastive Learning (GPCL) framework to overcome these challenges. In
particular, GPCL embeds each user/bundle/item as a Gaussian distribution
rather than a fixed vector. We further design a prototypical contrastive
learning module to capture the contextual information and mitigate the
sampling bias issue. Extensive experiments demonstrate that benefiting from
the proposed components, we achieve new state-of-the-art performance compared
to previous methods on several public datasets. Moreover, GPCL has been
deployed on real-world e-commerce platform and achieved substantial
improvements.

Bundle Recommendation, Gaussian Embeddings, Contrastive Learning, Graph Neural
Network

††ccs: Information systems Recommender systems

##  1\. Introduction

Figure 1. Illustration of user-bundle-item relations.

Recommenders are ubiquitous — they’re in many of the apps and tools we use
every day. Recommender systems serve users with personalized items and handle
the increasing online information overload problem. In recent years,
recommendation has evolved into a new form, called bundle recommendation [1,
2], where a collection of items are recommended as a whole (e.g. music
playlist and travel package). In e-commerce, item bundling [3, 4] is an
explainable and widely-used representation of user interests, and provide an
effective strategy to support promotional campaigns (e.g., purchasing a bundle
has a discounted rate). As shown in Figure 1, users can directly interact with
items and bundles. , and a bundle is usually composed of items with identical
or similar attributes.

Developing effective bundle recommendation system algorithms has received
significant attention by scholars and practitioners[5, 6, 7, 8]. The central
issue of the problem is to model a user’s preference for a bundle. As pointed
out in DAM [7], simply adopting the collaborative filtering methods is
technically feasible but does not work well due to the non atomic property of
bundles and highly sparse interactions. The contribution of content-based
models is also limited because there is usually no informative bundle-level
content features as item-level (e.g., category and brand), making bundle
recommendation a non-trivial task. Therefore existing research [6, 8]
recognizes that representation learning plays a pivotal role in the bundle
recommendation tasks, and focuses on how to fully take advantage of the user-
bundle-item co-occurrence information. Specifically, the user/bundle
representations can be inferred from two views [6]:

  * •

Bundle view where the user-bundle interactions are emphasized. For example, as
shown in Figure 1, $user_{1}$ is likely to prefer $bundle_{4}$ because the
behaviorally similar user $user_{2}$ prefers $bundle_{4}$.

  * •

Item view where we utilize the user-item interactions and the bundle-item
affiliation information, e.g., $user_{1}$ may prefer $bundle_{1}$ because she
has been showing interest in $bundle_{1}$’s affiliated items.

In a major advance in 2022, CrossCBR [8] model the two views separately to
perform representation learning, and then enhance the view-aware
representations by fusing them in the following joint optimization stage with
the cross-view contrastive and BPR [9] loss, achieving state-of-the-art (SOTA)
performance.

Despite their success, the previous work suffers from the following
limitations. Firstly, existing approaches [10, 11, 12] mainly focus on
capturing the instance-level similarity but fail to discover the underlying
structure contexts over the whole data distribution. Considering the running
example in Figure 1, $bundle_{1}$ and $bundle_{2}$ share lots of items in
common, thus the distance between their vectors might be close intuitively.
However, the representation in traditional instance-wise contrast learning [8,
13, 14, 15] is not encouraged to encode this contextual semantic structure of
data. Similar bundles may be pushed away with random negative sampling. This
phenomenon, which we call “sampling bias”, can empirically lead to significant
performance degradation [16]. Secondly, the existing studies [7, 5] represent
each node by a single point in a low-dimensional continuous vector space but
fail to incorporate uncertainty which is caused by the lack of discriminative
information. We claim that the uncertainty is inherent when describing a node
by a single point in the real-world e-commerce bundle recommendation. In
practice, a bundle may be composed of a wide range of genres of items (e.g.
$bundle_{1}/bundle_{2}$ in Figure 1), and very limited information could be
learned from its interactions since it is not representative enough. In
addition, a large number of bundles/users with very few interactions are
difficult to represent precisely due to the highly sparsity.

Towards this end, we propose a Gaussian Graph with Prototypical Contrastive
Learning (GPCL) framework to incorporate the uncertainty and discover the
contextual semantic structure of data. In particular, unlike the prior
approaches that represent an instance as a single point vector in a low-
dimensional continuous space, we treat every instance as a Gaussian
distribution consisting of a mean and a variance vector to describe
uncertainty. Then a group of samples from the distribution are generated
through Monte-Carlo sampling as the inputs of subsequent components. In
addition, we design a prototypical contrastive learning module, where a
prototype is defined as a representative embedding for a group of semantically
similar nodes. By allocating the similar nodes to a learned prototype, we then
pull together positive pairs of $\langle$node, prototype$\rangle$ and push
away negative ones instead of pairs of $\langle$node, node$\rangle$. In this
way, the contextual semantic similarity is captured. At the time of writing,
the method was fully deployed on a large e-commerce platform for the bundle
recommendation task. In short, the main contributions are summarized as
follows.

  1. (1)

We present a model architecture agnostic Gaussian embedding module to capture
uncertainty and enhance model representation capability. Learning uncertainty
of embedding produces meaningful representations for modeling the user
preference, and it also enables the downstream exploration and exploitation
strategy in the recommendation systems.

  2. (2)

A novel prototypical contrastive learning is developed to learn node
representations better and further in a self-supervised manner, which can
alleviate the ”sampling bias” issue in the instance-wise contrastive learning
for bundle recommendation.

  3. (3)

Extensive offline experiments demonstrate the state-of-the-art performance of
our method and its effectiveness of each component. We also exhibit the
superiority of our method in a real-world e-commerce production environment.

##  2\. PRELIMINARIES

Before presenting our methodology, we first formally define the problem and
introduce the base model.

###  2.1. Problem Definition

In order to integrate item level information to improve bundle recommendation
accuracy, there are two types of important side information that need to be
modeled, the user’s preference to item and bundle’s composition information.
Let $\boldmath{U}=\\{u_{i}|i=1,2,...,M\\}$,
$\boldmath{I}=\\{i_{j}|j=1,2,....N\\}$ and
$\boldmath{B}=\\{b_{k}|k=1,2,...,O\\}$ denote the sets of users, items and
bundles respectively, where $M,N,O$ is the sizes of corresponding sets. We
define user-bundle and user-item interaction matrix as $X_{M\times
O}=\\{x_{ub}|u\in U\\}$ and $Y_{M\times N}=\\{y_{ui}|u\in U,i\in I\\}$. The
bundle-item affiliation matrix is represented by $Z_{O\times N}=\\{z_{bi}|b\in
B,i\in I\\}$. We define the binary variables $x_{ub},y_{ui},z_{bi}$ that
assume value 1 if and only if user $u$ interacts with bundle $b$ or user $u$
interacts with item $i$, or item $i$ belongs to bundle $b$. As illustrated in
Section 1, users can directly click/purchase/collect items or interact with
bundles, thus X and Y are independent. Based on the historical interactions
and affiliation relations, our goal is to estimate the probability of the user
$u$ interacting with bundle $b$.

###  2.2. Base Model

Due to the success of cross-view contrastive learning for bundle
recommendation in CrossCBR [8], we take it as the base model and also a part
of the GPCL as shown in Figure 3. The key idea is that the bundle-view and
item-view provide complementary but different information about the user-
bundle preference, thus it is worthy to perform representation learning upon
two views separately and further design a contrastive loss (CL) to model the
cooperative association and achieve mutual enhancement.

For the bundle-view, an undirected bipartite user-bundle (U-B) graph is
constructed based on the historical interaction matrix $X$. Then the
prevailing GNN-based recommendation framework LightGCN [17] is adopted as the
encoder to learn the representations of both users and bundles. For the
simplicity of notations, assume that the number of LightGCN layers takes 1,
$e_{u}^{0}$ and $e_{b}^{0}$ are the initialized node vectors of the user $u$
and bundle $b$, then the final representations are denoted as:

(1) $\begin{split}&e_{u}^{B}=\sum_{b\in
N_{u}}\frac{1}{\sqrt{|N_{u}|}\sqrt{|N_{b}|}}e_{b}^{0}\\\ &e_{b}^{B}=\sum_{u\in
N_{b}}\frac{1}{\sqrt{|N_{b}|}\sqrt{|N_{u}|}}e_{u}^{0}\end{split}$

where $N_{u}$ and $N_{b}$ are the neighbor nodes of the user $u$ and bundle
$b$ respectively.

For the item-view, user-item (U-I) graph and bundle-item (B-I) graph are
constructed according to the user-item interactions $Y$ and bundle-item
affiliations $Z$, respectively. Similar to the U-B graph learning, $e_{i}^{0}$
and $e_{u}^{0}$ are the initialized node vectors of the item $i$ and user $u$,
based on U-I graph we have:

(2) $\begin{split}&e_{u}^{I}=\sum_{i\in
N_{u}}\frac{1}{\sqrt{|N_{u}|}\sqrt{|N_{i}|}}e_{i}^{0}\\\ &e_{i}^{I}=\sum_{u\in
N_{i}}\frac{1}{\sqrt{|N_{i}|}\sqrt{|N_{u}|}}e_{u}^{0}\end{split}$

where $N_{i}$ is the neighbor nodes of item $i$. According to the B-I graph,
the neighborhood of the bundle is aggregated by average pooling to get the
representation of bundle $b$ as:

(3) $e_{b}^{I}=\frac{1}{|N_{b}|\sum_{i\in N_{b}}e_{i}^{I}}$

The popular InfoNCE [18] loss is then built upon the cross-view
representations of users and bundles, respectively. More precisely, the
contrastive loss is able to simultaneously encourage the alignment of the same
user/bundle from different views and enforce the separation of different
users/bundles. The contrastive loss $L^{U}_{CL}$ and $L^{B}_{CL}$ are as
follows:

(4) $\begin{split}&L^{U}_{CL}=\frac{1}{|U|}\sum_{u\in
U}-\text{log}\frac{\text{exp}(e_{u}^{B}\cdot e_{u}^{I})/\tau)}{\sum_{v\in
U}\text{exp}((e_{u}^{B}\cdot e_{v}^{I})/\tau)}\\\
&L^{B}_{CL}=\frac{1}{|B|}\sum_{b\in
B}-\text{log}\frac{\text{exp}(e_{b}^{B}\cdot e_{b}^{I})/\tau)}{\sum_{p\in
B}\text{exp}((e_{b}^{B}\cdot e_{p}^{I})/\tau)}\end{split}$

where $\tau$ is the hyper-parameter, and $v,p$ are negative samples. By
summing the two term, we obtain the final cross-view contrastive loss:

(5) $L_{CL}=L_{CL}^{U}+L_{CL}^{B}$

After we obtain the representations of users and bundles from two views, the
prediction is made by:

(6) $y_{u,b}=e_{u}^{B}\cdot e_{b}^{B}+e_{u}^{I}\cdot e_{b}^{I}$

The Bayesian Personalized Ranking (BPR) [14] loss function is adopted as the
main loss:

(7) $L^{BPR}=\sum_{u,b,b^{\prime}}-\text{ln}\sigma(y_{u,b}-y_{ub^{\prime}})$

Finally, the overall training loss is:

(8) $L_{base}=L^{BPR}+\gamma_{CL}*L_{CL}$

where $\gamma_{CL}$ is the weight of the cross-view contrastive loss.

##  3\. METHODOLOGY

In this section, we first propose two core components: Gaussian embedding
module and prototypical contrastive learning module. Then we present the model
learning loss and some discussions. The overall architecture of our proposed
framework GPCL is shown in Figure 3.

###  3.1. Gaussian Embedding

We represent each bundle, user or item with an Gaussian distribution governed
by a mean vector and a covariance matrix. To limit the complexity of the model
and reduce the computational overhead [19, 20], we assume that the random
variable of different dimensions are uncorrelated, thus the covariance matrix
$\Sigma$ is diagonal and can be further represented by a variance vector
$\sigma$. To be specific, each bundle, user or item has two embedding
representations, which are for the mean and variance.

Figure 2. Illustration of Gaussian embedding module.

Figure 3. Model architecture of the proposed GPCL.

For user $u$, we denote the mean embedding as $\mu_{u}\in\mathbb{R}^{D}$ and
variance embedding as $\sigma_{u}\in\mathbb{R}^{D}$, where $D$ is the
embedding dimension. Analogously, we use
$\\{(\mu_{b},\sigma_{b})|\mu_{b}\in\mathbb{R}^{D},\sigma_{b}\in\mathbb{R}^{D}\\}$
and
$\\{(\mu_{i},\sigma_{i})|\mu_{i}\in\mathbb{R}^{D},\sigma_{i}\in\mathbb{R}^{D}\\}$
for user $u$ and item $i$ respectively. In this way, each node is represented
by $2\times D$ parameters.

To maintain numerical stability and non-negativity, the variances are
transformed by ”Exponential Linear Unit” (ELU) [19]:

(9) $\sigma^{\prime}=ELU(\sigma)+1$

Then we can get transformed variances: $\sigma^{\prime}_{u}$,
$\sigma^{\prime}_{b}$ and $\sigma^{\prime}_{i}$. Note that there are many
other activation functions [21], they are also applicable with appropriate
adjustment and could achieve similar performances by our test.

In order to perform back-propagation, we use the reparameterization trick [22]
to obtain the embedding sample as follows:

(10) $e=\mu+\sqrt{\sigma^{\prime}}\times\epsilon$

where $\epsilon\sim N(0,1)$. As shown in Figure 2, we can randomly sample
several times of users/bundles/items as the input of the subsequent modules.
For ease of notation in the following, assume that we only sample once and
their Gaussian embeddings are denoted as $e_{u}$, $e_{b}$ and $e_{i}$,
respectively.

###  3.2. Prototypical Contrastive Learning

The cross-view contrastive learning guarantees mutual enhancement of the two
views. However, as shown in Figure 4, it suffers from the critical ”sampling
bias” issue that similar nodes might be pushed far apart and leading to
performance degradation. To reduce selection bias and obtain a better
representation, we design a prototypical contrastive objective to capture the
correlations between a user/bundle and its prototype. The prototype can be
seen as the context of each user/bundle which represents a group of semantic
neighbors even that they are not structurally connected in the graph.
Regarding the prototype learning as a type of feature clustering for another
view, we can perform prototypical contrastive learning.

Figure 4. Comparison of Instance-wise and prototypical contrastive learning.

The prototypical contrastive learning takes is built on the whole original
node space (including both users and bundles) rather than in-batch data space.
As shown in Figure 5, taking users as the example, let
$U\in\mathbb{R}^{M\times D}$ be the user embedding matrix and we set a
corresponding prototype matrix $C^{U}\in\mathbb{R}^{K\times D}$. If user
representation $e_{u}$ is clustered to prototype $c_{i}^{u}$, the InfoNCE loss
for users is:

(11) $L_{U}^{proto}=\sum_{u\in U}-\text{log}\frac{\text{exp}(e_{u}\cdot
c^{u}_{i})/\tau}{\sum_{c^{u}_{j}\in C^{U}}\text{exp}(e_{u}\cdot c^{u}_{j})}$

Analogously, the InfoNCE loss for bundles is:

(12) $L_{B}^{proto}=\sum_{b\in B}-\text{log}\frac{\text{exp}(e_{b}\cdot
c^{b}_{i})/\tau}{\sum_{c^{b}_{j}\in C^{B}}\text{exp}(e_{u}\cdot c^{b}_{j})}$

By summing the two contrastive losses, we obtain the prototypical contrastive
loss:

(13) $L_{CL}^{proto}=L_{U}^{proto}+L_{B}^{proto}$

Now we present how to implement the prototype generation and learning. The
basic criterion is to assign each user to the nearest prototype where the
similarity is measured by dot product of their vectors. In practice, simply
minimizing the InfoNCE loss under this naïve criterion suffers from the
degeneracy problem since all data samples will be assigned to only a few
prototypes. Hence we need to constrain that prototype assignment is equally
partitioned [23]. Let $S_{U}=UC_{U}^{\top}\in\mathbb{R}^{M\times K}$ be the
similarity score matrix and $Q_{U}\in\mathbb{R}^{M\times K}$ denote the
assignment matrix where each element $q_{up}$ is the probability that user $u$
is assigned to prototype $p$. The assignment of prototypes can be formulated
as a relaxed Optimal Transport (OT) problem:

(14) $\displaystyle\text{max}_{Q_{U}\in\mathcal{Q_{U}}}$
$\displaystyle\text{Tr}(S_{U}Q_{U}^{\top})+\lambda H(Q_{U})$ $\displaystyle
s.t.$ $\displaystyle Q_{U}^{\top}\mathbf{1}_{M}=\frac{1}{K}\mathbf{1}_{K}$
$\displaystyle Q_{U}\mathbf{1}_{K}=\frac{1}{M}\mathbf{1}_{M}$

where $\mathbf{1}_{M}$ and $\mathbf{1}_{K}$ denote the vector of ones in
dimension $M$ and $K$. The objective function is to maximize the total
similarity between the vectors and the prototypes with an entropy
regularization function $H(Q_{U})=-\sum_{ij}Q_{U_{ij}}\text{log}Q_{U_{ij}}$ to
control the smoothness of the assignment. The constraints guarantee that each
prototype is associated with $\frac{M}{K}$ users.

According to Sinkhorn algorithm [24, 23], the optimal solution $Q_{U}^{*}$
takes the form of a normalized exponential matrix:

(15)
$Q_{U}^{*}=\text{Diag}(\boldsymbol{\alpha})\text{exp}\Big{(}\frac{S_{U}}{\lambda}\Big{)}\text{Diag}(\boldsymbol{\beta})$

where $\boldsymbol{\alpha}\in\mathbb{R}^{K}$ and
$\boldsymbol{\beta}\in\mathbb{R}^{B}$ are renormalization vectors. We can
solve it fast by means of fixed-point iteration. After getting the constrained
prototype assignment $Q_{U}^{*}$, the loss function (13) could be computed as:

(16) $L_{OT\\_U}^{proto}=\left\langle Q_{U},-\text{log}S_{U}\right\rangle$

where $\left\langle\cdot\right\rangle$ is the Frobenius dot-product between
two matrices and log is applied element-wise. The loss (13) encourages the
assignment to be as uniform as possible. Similarly, we can get the loss
$L_{OT\\_B}^{proto}$ for bundles. Finally the loss of prototypical contrastive
learning would be

(17) $L_{OT}^{proto}=L_{OT\\_U}^{proto}+L_{OT\\_B}^{proto}$

Note that computing $Q_{U}^{*}$ should not involve backpropagation (BP), while
only the gradients of $U$ and $C$ are needed as illustrated in Figure 5.

Figure 5. The training process of prototypical contrastive learning.

###  3.3. Model Learning and Discussion

####  3.3.1. Model Learning

The overall framework of GPCL is depicted in Figure 3. By combining all the
aforementioned losses, for the $t_{th}$ sample from Gaussian embeddings, the
loss would be:

(18)
$L_{t}=L_{BPR}+\gamma_{CL}*L_{CL}+\gamma_{PCL}*L_{CL}^{proto}+\gamma_{OT}*L_{OT}^{proto}$

where $\gamma_{CL}$, $\gamma_{PCL}$ and $\gamma_{R}$ are hyper-parameters to
balance the four terms, and $L_{BPR}$ is the main loss. If we sample $T$
times, the total loss is

(19) $L=\sum_{t=1,2,...,T}\frac{1}{T}L_{t}$

####  3.3.2. Uncertainty of Prediction

Using Gaussian embeddings for nodes not only makes powerful representations,
but also provides predictive uncertainty estimations [20]. Specifically, the
final prediction score $y_{u,b}$ obeys a Gaussian distribution as well. Its
mean and variance can be obtained by aggregating $T$ different prediction
results. The value of the variance denotes the confidence of the model
prediction. Exploration and exploitation strategy can be further adopted in
real-world scenarios by considering the confidence. We can satisfy user’s
preference and expand the breadth of user’s interest simultaneously, and boost
up long-term utilities such as the social welfare.

####  3.3.3. Original-Data-Level Cluster versus In-Batch-Level Cluster

Usually the the cluster-based contrastive learning approach is implemented at
in-batch level (after encoding), while we perform at original-data level
(before encoding). We claim that in real-world recommendation scenarios, the
number of underlying prototypes can be very large but the diversity of in-
batch samples may be insufficient, thus enforcing the uniform assignment may
lead to performance drop.

##  4\. EXPERIMENT

In this section, we present the details of the experimental setups and the
corresponding results, as well as an online A/B test, to answer the following
questions:

  * •

RQ1: Does our proposed model GPCL achieve the best performance compared to
other baselines?

  * •

RQ2: What is the contribution of various components in our framework?

  * •

RQ3: What is the effect of parameters change on the experiment?

  * •

RQ4: Can GPCL improve the performance of an existing model in a live
recommender system?

Table 1. Statistics of three datasets. DataSet | Youshu | NetEase | iFashion
---|---|---|---
—User— | 8,039 | 18,528 | 53,897
—Bundle— | 4,771 | 22,864 | 42,563
—Item— | 32,770 | 12,3628 | 27,694
—User-Item— | 138,515 | 1,128,065 | 2,290,645
—User-Bundle— | 51,377 | 303,303 | 1,679,708
—Bundle-Item— | 176,667 | 1,778,838 | 164,293
Avg item interactions | 17.23 | 60.88 | 42.50
Avg bundle interactions | 6.39 | 16.32 | 31.17
Avg bundle size | 37.03 | 77.80 | 3.86
Table 2. Results of both GPCL and baselines: the improvement is significant
(p-value $\ll$ 0.01).

Method | Youshu | NetEase | iFashion
---|---|---|---
rec@20 | ndcg@20 | rec@40 | ndcg@40 | rec@20 | ndcg@20 | rec@40 | ndcg@40 | rec@20 | ndcg@20 | rec@40 | ndcg@40
DAM | 0.2082 | 0.1198 | 0.2890 | 0.1418 | 0.0411 | 0.0210 | 0.0690 | 0.0281 | 0.0629 | 0.0450 | 0.0995 | 0.0579
BundleNet | 0.1895 | 0.1125 | 0.2675 | 0.1335 | 0.0391 | 0.0201 | 0.0661 | 0.0271 | 0.0626 | 0.0447 | 0.0986 | 0.0574
BGCN | 0.2347 | 0.1345 | 0.3248 | 0.1593 | 0.0491 | 0.0258 | 0.0829 | 0.0346 | 0.0733 | 0.0531 | 0.1128 | 0.0671
CrossCBR | 0.2801 | 0.1669 | 0.3781 | 0.1941 | 0.0794 | 0.0431 | 0.1206 | 0.0539 | 0.1149 | 0.0885 | 0.1653 | 0.1062
GPCL | 0.2882 | 0.1713 | 0.3963 | 0.2007 | 0.0833 | 0.0441 | 0.1270 | 0.0557 | 0.1216 | 0.0928 | 0.1756 | 0.1118
%Improv. | 2.88% | 2.62% | 4.82% | 3.38% | 4.86% | 2.42% | 5.30% | 3.33% | 5.80% | 4.85% | 6.23% | 5.27%

###  4.1. Experiment Setup

####  4.1.1. Datasets and Metrics

To validate the effectiveness and robustness of our methods, we evaluate on
three public datasets which are widely used for bundle recommendation:

  * •

Youshu 111https://www.youshu.com/ is a book-review dataset [7]. The bundle is
a book list that users may prefer.

  * •

NetEase 222https://music.163.com/ is a music dataset [25]. The playlist
composed of a set of songs acts as the bundle and can be favored/collected by
users.

  * •

iFashion is an outfit dataset where the outfit is made up of individual
fashion items and treated as the bundle [26].

For a fair comparison, we adopt the same data preprocessing as existing
research [8]. The statistics of the datasets are shown in Table 1, where avg
item interactions, avg bundle interactions, avg bundle size stand for the
average number of interacted items per user, the average number of interacted
bundles per user and the average number of affiliated items per bundle. To
measure the validity of predicted preferences, we use Recall@n and NDCG@n as
the metrics where $n\in\\{20,40\\}$.

####  4.1.2. Competitors

For a comprehensive evaluation, we compared our method with previous tailor-
designed models for the bundle recommendation task:

  * •

DAM. DAM [7] designs the attention mechanism to aggregate the item information
of each bundle, and then jointly optimizes the user-bundle and user-item
preference in a multi-task manner.

  * •

BundleNet. In BundleNet [5], the problem is formalized as a link prediction
problem on a user-item-bundle tripartite graph, and is solved by a Relational
Graph Convolutional Network model.

  * •

BGCN. BGCN [6] constructs two separate graphs, i.e., bundle-view graph and
item-view graph. Then the GCN is used to learn representations, and they make
predictions by fusing the representations from two views.

  * •

CrossCBR. Based on BGCN, CrossCBR [8] uses LightGCN [17] to learn the
representations from bundle-view graph and item-view graph separately, and
then employs contrastive learning to model the cooperative association between
the two views to improve performance.

####  4.1.3. Hyper-parameter and Training Settings

Dimension of embedding vectors is 64. We optimize all models with Adam
optimizer, where the learning rate is fixed at $10^{-4}$. The batch size is
set to 2048. Sampling times $T$, $\gamma_{PCL}$ and $\gamma_{R}$ are
additionally imported into our method, and they are explored by the grid
search strategy with the range of {1,2,4,6,8,10}, {0.01, 0.05,
0.1,0.15,0.2,0.25} and {0.01, 0.05, 0.1,0.15,0.2,0.25}. For fairness, other
hyper-parameters are consistent with the CrossCBR [8] such as the temperature
$\tau$ and data augmentation parameters. Each model is trained for 10 times
and we record the model’s average performance results. All the models are
trained using Pytorch 1.7, NVIDIA V100 GPUs.

###  4.2. Overall Performance (RQ1)

Table 2 presents the performance that each approach obtains. Boldface denotes
the best performance and underline indicates the strongest result of the
baselines. We compare GPCL with the baselines. %Improv. measures the relative
improvements of GPCL over the strongest result of the baselines. We have the
following observations:

Graph-based models generally exhibit better results, proving the expressive
power of graph learning for the bundle recommendation task. However, among the
graph-based models, BundleNet performs poorly, and we ascribe this to the
failure of differentiating users’ behavioral similarity and bundles’ content
relatedness. Through modeling user preference in two separate views, BGCN and
CrossCBR achieve significant gains. Aided by contrastive learning, CrossCBR
reaches SOTA performance. Our GPCL can beat the SOTA, i.e., CrossCBR, on all
the three datasets. This demonstrates the effectiveness and robustness of our
method as well as the key innovative components we propose. In the following
sections, we will present more detailed analysis with regard to the proposed
components.

###  4.3. Ablation study (RQ2)

To evaluate the proposed components of GPCL, we conduct a list of ablation
studies as reported in Table 3 where %Improv. measures the relative
improvements over CrossCBR. Due to the space limitation, we only present
rec@20 and ndcg@20 on Youshu and NetEase datasets.

####  4.3.1. Effectiveness of Gaussian Embedding Module

In order to verify whether the Gaussian Embedding Module contributes to the
performance, we first remove the prototypical contrastive learning module from
the model, named Gauss-Emb.

Table 3. Results of ablation methods. Method | Youshu | NetEase
---|---|---
rec@20 | ndcg@20 | rec@20 | ndcg@20
CrossCBR | 0.2801 | 0.1669 | 0.0794 | 0.0431
CrossCBR-2D | 0.2810 | 0.1674 | 0.0792 | 0.0430
Proto-Batch | 0.2785 | 0.1658 | 0.0791 | 0.0430
Gauss-Emb | 0.2828 | 0.1680 | 0.0823 | 0.0438
%Improv. | 0.98% | 0.69% | 3.60% | 1.62%
Proto-CL | 0.2870 | 0.1702 | 0.0809 | 0.0438
%Improv. | 2.45% | 1.95% | 1.83% | 1.62%
GPCL | 0.2882 | 0.1713 | 0.0833 | 0.0441
%Improv. | 2.88% | 2.62% | 4.82% | 2.42%

Gauss-Emb shows a performance decline compared with GPCL but still outperforms
the baseline CrossCBR, demonstrating the effectiveness of modeling
uncertainty.

When Gaussian embedding is introduced, each node is represented by two
$D$-dimensional vectors (i.e., the mean and variance vectors), making the the
number of representation parameters doubled. For a fair comparison, we design
an ablation study to explore the influence of the parameter size. We set the
embedding size of CrossCBR to $2D=128$ during training and obtain CrossCBR-2D.
From Table 3 we observe that on Youshu dataset, the performance of CrossCBR-2D
is just slightly better than CrossCBR while even underperforms CrossCBR-2D on
NetEase dataset, indicating that simply increasing the parameter size has
little effect with respect to the performance.

To demystify the working mechanism behind Gaussian embedding, we further
evaluate our framework particularly against the nodes (users and bundles) with
uncertainties. One of main sources of uncertainties is the marginal (nodes
with few past engagements) nodes, because very little information about their
information can be obtained from historical actions. Therefore we divide the
nodes into four groups by their frequencies and exam the uncertainty captured
by our method. The uncertainty is measured by the learned mean and variance
vector and calculated as follows:

$uncertainty=\sum_{i=1,2,...,D}\frac{\sqrt{\sigma^{\prime}_{i}}}{|\mu_{i}|}$

where $|\cdot|$ represents the absolute value; $\sigma^{\prime}_{i}$ denotes
the $i^{th}$ value of the transformed variance vector and $|\mu_{i}|$ denotes
the the $i^{th}$ value of the mean vector.

Table 4. Uncertainty of nodes with different frequency. Dataset | User-freq | Uncertainty | Tag-freq | Uncertainty
---|---|---|---|---
Youshu | 1-10 | 0.4805 | 1-10 | 27.11
11-30 | 0.2413 | 11-50 | 6.85
31-50 | 0.1642 | 51-200 | 4.06
51- | 0.0787 | 201- | 1.26
NetEase | 1-10 | 0.6585 | 1-10 | 128.0
11-100 | 0.4245 | 11-100 | 28.57
101-200 | 0.1353 | 101-200 | 6.79
201- | 0.0796 | 201- | 6.24

As shown in Table 4, the model assign larger uncertainties to the low-
frequency nodes, which suggests that Gaussian embeddings capture the
confidence of the nodes.

####  4.3.2. Effectiveness of Prototypical Contrastive Learning Module (RQ3)

To evaluate the effectiveness of the prototypical contrastive learning module,
we design Proto-CL by removing Gaussian embedding from GPCL. As expected,
Proto-CL is still better than CrossCBR by a large margin. In conclusion, both
modules, i.e., Gaussian embedding and prototypical contrastive learning,
collaboratively contribute to the performance.

Recall that our prototypical contrastive learning is trained on whole original
nodes. In order to justify the effectiveness of this learning paradigm, we
make a comparison with Proto-Batch where the prototypical contrastive learning
is deployed at in-batch level. As reported in Table 3, Proto-Batch
underperforms baseline CrossCBR on both datasets, which indicates that the
prototypical contrastive learning at whole original node space is necessary to
capture the complete contextual information.

###  4.4. Hyper-parameter study

Our proposed GPCL framework has introduced several vital hyper-parameters,
which may affect performances during training. In this section, we investigate
the importance and sensitivity of these hyper-parameters while fixing the
others.

####  4.4.1. Influence of the number of prototypes

The prototypical contrastive learning module involves two loss
$L_{CL}^{proto}$ and $L_{OT}^{proto}$, where the former is the prototypical
InfoNCE loss and the latter encourage the uniform assignment on the
prototypes. The corresponding two weights $\gamma_{PCL}$ and $\gamma_{OT}$
determine the number of actually assigned prototypes. We evaluate the impact
of prototype number by fixing $\gamma_{OT}$ and varying $\gamma_{CL}$. Figure
6 shows the number of assigned prototypes and the performance (Recall@20 due
to space limitations) with the value of $\gamma_{PCL}$. It can be observed
that either too small or too large $\gamma_{PCL}$ leads to performance drop
and large $\gamma_{PCL}$ could reduce utilization of prototypes. We conjecture
that the model degenerates to the case without prototypes (i.e., each node
acts as a prototype itself) when $\gamma_{PCL}$ is too small, and too large
$\gamma_{PCL}$ brings about assignment collapse (i.e. all nodes are assigned
to few prototypes).

(a) Youshu

(b) NetEase

Figure 6. Sensitivity analysis for the number of prototypes $T$.

####  4.4.2. Influence of Sampling Size

Our proposed Gaussian embedding module has involved a hyper-parameter: the
sampling times $T$. To investigate its importance and sensitivity, we set $T$
from 1 to 8 and the results are shown in Figure 7. From the line chart, we can
observe that as the sampling size grows, the performance improves before the
model reaches a state of complete convergence and then remains stable when $T$
is large.

(a) Youshu_Recall

(b) NetEase_Recall

(c) iFashion_Recall

(d) Youshu_NDCG

(e) NetEase_NDCG

(f) iFashion_NDCG

Figure 7. Sensitivity analysis for sample size $T$.

###  4.5. Online A/B test (RQ4)

To verify the actual benefits of our model, we conduct online A/B test in the
real-world production environment. Our experiments are based on the log data
from a certain industry of the Alibaba’s e-commerce platform. The data covers
2,238,947 users, 2,682,634 items and 7302 bundles where the average number of
affiliated items per bundle is 182. The task is to select proper bundles for
the users to satisfy their preferences. Our goal is to maximize the total
number of paying customers, and we use conversion rate (CVR) and click-
through&conversion rate (CTCVR) as the metrics to evaluate the performance of
the online A/B test.

Due to the limited resources, we only compare our best model GPCL with the
current solution working online. For the control group, we adopt the current
online solution, a simple yet effective strategy where the user-bundle
preference score is calculated by some tailor-designed rules. It has been
deployed for a long time due to its high efficiency and stable performance.
For the experimental group, the preference score is produced by GPCL. The
numbers of users in the control and experimental groups are approximately
identical, each accounting for 50%.

Table 5. Online A/B Test Results. Metric | CVR | CTCVR
---|---|---
Lift rate | 2.03% | 2.06%

Table 5 illustrates the lift rate of GPCL over the baseline with regard to the
two metrics. We could see that GPCL achieves a significant improvement. The
results demonstrate the effectiveness of our proposed model.

##  5\. RELATED WORK

Bundle recommendation. DAM [7] first design an attention network to aggregate
the item embeddings in a bundle in a multi-task manner to jointly optimize the
user-bundle and user-item preference, but fail to explore the affiliation
between items and bundles. Recent evidence [8, 5, 6] suggests that graph
representation learning is an effective technique to capture the complicated
topology and higher-order connectivity of user-bundle-item. BundleNet [5]
builds a unified tripartite graph and use GNNs [27] to perform representation
learning which can implicitly incorporate the intermediate role of items
between users and bundles. However, the cooperation of bundle view and item
view are not well differentiated. Recently CrossCBR [8] further involve
contrastive learning based on BGCN and achieve SOTA performance.

Gaussian embedding of graphs. KL-divergence-based methods [28, 29] to measure
the similarity of graph nodes are widely used. DeepGE [28] propose an
unsupervised approach where the mean and variance vectors of each node are
obtained by a deep encoder, and they utilize the node’s neighbor information
to minimize the KL-divergence distance. DMKD [29] employ a given node
similarity metric to measure the global structural information, then generate
structural context for nodes and finally learns node representations via
Gaussian embedding. GE [30] propose an end-to-end framework for the large-
scale graph where they learn from both node attributes and graph structural
information. Another line of research directly applys Gaussian embedding on
nodes without considering graph structure [20, 19]. GECF [20] represent each
node by a normal-gamma distribution where the parameters are learned through
the rank loss. GeRec [19] assume that the representation of each node follows
a Gaussian distribution and then sample several times as the input tensors of
the subsequent CNN encoder.

Clustering-based contrastive learning. Due to the sampling bias issue of
instance-wise contrastive learning, cluster-based contrastive learning is
proposed in recent studies [31, 23, 32, 33] where they contrast between
instances and cluster centroids to capture underlying semantic information. In
their work [31, 34], cluster centroids are obtained by k-means, and optimized
by an Expectation-Maximization framework. While some other methods
parameterize the cluster prototypes directly and update them with model in
each step. For the computer vision task, SwAV [23] introduce the concept of
prototypes which can be seen as the context (i.e., a group of semantic
neighbors) of each representation. They use constrained optimization algorithm
and cross-entropy loss to guide the learning of prototype vectors and the
assignment of instances. Similarly, PGCL [16] adopt the prototype-based method
in the graph classification task where they design a reweighted contrastive
loss where negatives having moderate prototype distance enjoy relatively large
weights to mitigate sampling bias issue.

##  6\. CONCLUSION AND FUTURE WORK

In this paper, we present a Gaussian Graph with Prototypical Contrastive
Learning framework for the bundle recommendation task. First, we propose a
Gaussian embedding module to model the uncertainty. To capture the contextual
information and obtain more refined representations, we further develop the
prototypical contrastive learning module. Extensive experiments demonstrate
that benefiting from the proposed components, we achieve new state-of-the-art
performance compared to previous methods on three public datasets. The online
A/B test exhibits the superiority of our method in the real-world production
environment. As future work, we are very interested in the downstream
exploration and exploitation strategy by considering the uncertainty, to
improve users’ shopping experience by enhancing novelty and serendipity at
little cost.

## References

  * [1] Apurva Pathak, Kshitiz Gupta, and Julian J. McAuley.  Generating and personalizing bundle recommendations on _Steam_.  In SIGIR 2017, Shinjuku, Tokyo, Japan, August 7-11, 2017, pages 1073–1076. ACM, 2017.
  * [2] Tao Zhu, Patrick Harrington, Junjun Li, and Lei Tang.  Bundle recommendation in ecommerce.  In SIGIR 2014, Gold Coast , QLD, Australia - July 06 - 11, 2014, pages 657–666. ACM, 2014.
  * [3] Chenxu Zhu, Peng Du, Xianghui Zhu, Weinan Zhang, Yong Yu, and Yang Cao.  User-tag profile modeling in recommendation system via contrast weighted tag masking.  In KDD ’22, Washington, DC, USA, August 14 - 18, 2022, pages 4630–4638. ACM, 2022.
  * [4] Kelong Mao, Xi Xiao, Jieming Zhu, Biao Lu, Ruiming Tang, and Xiuqiang He.  Item tagging for information retrieval: A tripartite graph neural network based approach.  In SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 2327–2336. ACM, 2020.
  * [5] Qilin Deng, Kai Wang, Minghao Zhao, Zhene Zou, Runze Wu, Jianrong Tao, Changjie Fan, and Liang Chen.  Personalized bundle recommendation in online games.  In CIKM ’20, Virtual Event, Ireland, October 19-23, 2020, pages 2381–2388. ACM, 2020.
  * [6] Jianxin Chang, Chen Gao, Xiangnan He, Depeng Jin, and Yong Li.  Bundle recommendation with graph convolutional networks.  In SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 1673–1676. ACM, 2020.
  * [7] Liang Chen, Yang Liu, Xiangnan He, Lianli Gao, and Zibin Zheng.  Matching user with item set: Collaborative bundle recommendation with deep attention network.  In IJCAI 2019, Macao, China, August 10-16, 2019, pages 2095–2101. ijcai.org, 2019.
  * [8] Yunshan Ma, Yingzhi He, An Zhang, Xiang Wang, and Tat-Seng Chua.  Crosscbr: Cross-view contrastive learning for bundle recommendation.  In KDD ’22, Washington, DC, USA, August 14 - 18, 2022, pages 1233–1241. ACM, 2022.
  * [9] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme.  BPR: bayesian personalized ranking from implicit feedback.  In UAI 2009, Montreal, QC, Canada, June 18-21, 2009, pages 452–461. AUAI Press, 2009.
  * [10] Arjun Subramonian.  Motif-driven contrastive learning of graph representations.  In EAAI 2021, Virtual Event, February 2-9, 2021, pages 15980–15981. AAAI Press, 2021.
  * [11] Zekun Tong, Yuxuan Liang, Henghui Ding, Yongxing Dai, Xinke Li, and Changhu Wang.  Directed graph contrastive learning.  In NeurIPS 2021, December 6-14, 2021, virtual, pages 19580–19593, 2021.
  * [12] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Deep graph contrastive representation learning.  CoRR, abs/2006.04131, 2020.
  * [13] Hakim Hafidi, Mounir Ghogho, Philippe Ciblat, and Ananthram Swami.  Graphcl: Contrastive self-supervised learning of graph representations.  CoRR, abs/2007.08025, 2020.
  * [14] Yixin Zhang, Yong Liu, Yonghui Xu, Hao Xiong, Chenyi Lei, Wei He, Lizhen Cui, and Chunyan Miao.  Enhancing sequential recommendation with graph contrastive learning.  In IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 2398–2405. ijcai.org, 2022.
  * [15] Yinwei Wei, Xiang Wang, Qi Li, Liqiang Nie, Yan Li, Xuanping Li, and Tat-Seng Chua.  Contrastive learning for cold-start recommendation.  In MM ’21, Virtual Event, China, October 20 - 24, 2021, pages 5382–5390. ACM, 2021.
  * [16] Shuai Lin, Chen Liu, Pan Zhou, Zi-Yuan Hu, Shuojia Wang, Ruihui Zhao, Yefeng Zheng, Liang Lin, Eric Xing, and Xiaodan Liang.  Prototypical graph contrastive learning.  IEEE Transactions on Neural Networks and Learning Systems, pages 1–12, 2022.
  * [17] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 639–648. ACM, 2020.
  * [18] Michael Gutmann and Aapo Hyvärinen.  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  In AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, volume 9 of JMLR Proceedings, pages 297–304. JMLR.org, 2010\.
  * [19] Junyang Jiang, Deqing Yang, Yanghua Xiao, and Chenlu Shen.  Convolutional gaussian embeddings for personalized recommendation with uncertainty.  In IJCAI 2019, Macao, China, August 10-16, 2019, pages 2642–2648. ijcai.org, 2019.
  * [20] Ludovic Dos Santos, Benjamin Piwowarski, and Patrick Gallinari.  Gaussian embeddings for collaborative filtering.  In SIGIR 2017, Shinjuku, Tokyo, Japan, August 7-11, 2017, pages 1065–1068. ACM, 2017.
  * [21] Shiv Ram Dubey, Satish Kumar Singh, and Bidyut Baran Chaudhuri.  Activation functions in deep learning: A comprehensive survey and benchmark.  Neurocomputing, 503:92–108, 2022.
  * [22] Diederik P. Kingma and Max Welling.  Auto-encoding variational bayes.  In ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
  * [23] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [24] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In NeurIPS,December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2292–2300, 2013.
  * [25] Da Cao, Liqiang Nie, Xiangnan He, Xiaochi Wei, Shunzhi Zhu, and Tat-Seng Chua.  Embedding factorization models for jointly recommending items and user generated lists.  In SIGIR 2017, Shinjuku, Tokyo, Japan, August 7-11, 2017, pages 585–594. ACM, 2017.
  * [26] Wen Chen, Pipei Huang, Jiaming Xu, Xin Guo, Cheng Guo, Fei Sun, Chao Li, Andreas Pfadler, Huan Zhao, and Binqiang Zhao.  POG: personalized outfit generation for fashion recommendation at alibaba ifashion.  In KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 2662–2670. ACM, 2019.
  * [27] Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings, 2018.
  * [28] Aleksandar Bojchevski and Stephan Günnemann.  Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking.  In ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018. OpenReview.net, 2018.
  * [29] Yulong Pei, Xin Du, Jianpeng Zhang, George Fletcher, and Mykola Pechenizkiy.  struc2gauss: Structural role preserving network embedding via gaussian embedding.  Data Min. Knowl. Discov., 34(4):1072–1103, 2020.
  * [30] Bhagya Hettige, Yuan-Fang Li, Weiqing Wang, and Wray Buntine.  Gaussian embedding of large-scale attributed graphs.  In Databases Theory and Applications, pages 134–146. Springer International Publishing, 2020.
  * [31] Zihan Lin, Changxin Tian, Yupeng Hou, and Wayne Xin Zhao.  Improving graph collaborative filtering with neighborhood-enriched contrastive learning.  In WWW ’22, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 2320–2329. ACM, 2022.
  * [32] Baoyu Jing, Shengyu Feng, Yuejia Xiang, Xi Chen, Yu Chen, and Hanghang Tong.  X-GOAL: multiplex heterogeneous graph prototypical contrastive learning.  In CIKM 2022, Atlanta, GA, USA, October 17-21, 2022, pages 894–904.
  * [33] Yanling Wang, Jing Zhang, Haoyang Li, Yuxiao Dong, Hongzhi Yin, Cuiping Li, and Hong Chen.  Clusterscl: Cluster-aware supervised contrastive learning on graphs.  In WWW ’22, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 1611–1621. ACM, 2022.
  * [34] Junnan Li, Pan Zhou, Caiming Xiong, and Steven C. H. Hoi.  Prototypical contrastive learning of unsupervised representations.  In ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.


# DETERRENT: Detecting Trojans using Reinforcement Learning

Vasudev Gohil, Satwik Patnaik, Hao Guo, Dileep Kalathil, and Jeyavijayan (JV)
Rajendran  Electrical & Computer Engineering, Texas A&M University, College
Station, Texas, USA gohil.vasudev, satwik.patnaik, guohao2019,
dileep.kalathil, jv.rajendran @tamu.edu

###### Abstract.

Insertion of hardware Trojans (HTs) in integrated circuits is a pernicious
threat. Since HTs are activated under rare trigger conditions, detecting them
using random logic simulations is infeasible. In this work, we design a
reinforcement learning (RL) agent that circumvents the exponential search
space and returns a minimal set of patterns that is most likely to detect HTs.
Experimental results on a variety of benchmarks demonstrate the efficacy and
scalability of our RL agent, which obtains a significant reduction
($169\times$) in the number of test patterns required while maintaining or
improving coverage ($95.75\%$) compared to the state-of-the-art techniques.

Reinforcement Learning, Hardware Trojans

††copyright: none††journalyear: 2022

##  1\. Introduction

Reinforcement learning (RL) helps a computing system (a.k.a. agent) to learn
by its own experience through exploring and exploiting the underlying
environment. Over time, the agent takes optimal actions in sequence, even with
limited or no knowledge regarding the environment. From a cybersecurity
perspective, such RL agents are attractive as they can generate optimal
defense techniques in an unknown adversarial environment. Given the latest
improvements in RL algorithms, these agents can efficiently navigate high-
dimensional search space to find optimal actions. Hence, researchers have used
RL agents to develop promising approaches for several security problems,
including intrusion detection (RL_intrusion_detection, ), fuzzing (RL_Fuzzing,
; RL_Fuzzing_USENIX, ), and developing secure cyber-physical systems (RL_CPS1,
; RL_CPS2, ; nguyen2019deep_new, ). However, research in hardware security is
still in its infancy to reap the power of RL in developing optimal defenses in
adversarial environments. In this work, we showcase how RL can be used to
efficiently detect hardware Trojans (HTs). Out of the many problems in
hardware security, the HT detection problem presents significant computational
challenges to the defender in detecting them in an unknown environment (i.e.,
HT-infected design).

The increasing cost of integrated circuit (IC) manufacturing has forced
semiconductor companies to send their designs to untrusted, off-shore
foundries. Malicious components known as HTs inserted during the fabrication
stage can leak secret information, degrade performance, or cause a denial of
service.

###  1.1. Hardware Trojans

An HT consists of two components: trigger and payload. When the trigger is
activated, the payload causes a malicious effect in the design. Figure 1
illustrates an HT that flips an output upon trigger activation. The trigger
comprises multiple nets, called select nets, in the design. For instance, the
adversary can choose the select nets so that the trigger gets activated only
under extremely rare conditions. This is achieved by determining a rareness
threshold111Rareness threshold is the probability below which nets are
classified as rare nets. and constructing the trigger using the corresponding
rare nets.

Figure 1. Example of an HT in a design with $150$ rare nets.

Detecting HTs is difficult since they are designed to be stealthy
(xiao2016Trojan_survey, ). Consider the example in Figure 1 with $150$ rare
nets. Four of them are used for the trigger. Thus, the defender needs to check
up to ${}^{150}C_{4}\approx 20\times 10^{6}$ different combinations of rare
nets, which is extremely challenging. Such a large space makes it difficult
even for conventional automatic test pattern generation (ATPG) tools (TestMAX,
) to activate the trigger.

###  1.2. Hardware Trojan Detection Techniques

One can classify the HT detection techniques under two broad categories: logic
testing and side-channel analysis. Logic testing involves the application of
test patterns to the HT-infected design to activate the trigger
(chakraborty2009mero, ; TARMAC_TCAD, ; pan2021automated, ). However,
activating an extremely rare trigger is challenging because the possible
combinations of rare nets are extensive. On the other hand, side-channel-based
detection techniques detect HTs based on the differences in the side-channel
measurements (such as power or timing) between the golden (i.e., HT-free)
design and an HT-infected design (narasimhan2012hardware, ; huang2016mers, ;
huang2018scalable, ; lyu2019efficient, ). However, since HTs have an extremely
small footprint compared to the overall size of the design, their impact on
side-channel metrics is usually negligible and concealed under process
variation and environmental effects (rai2009performance, ). We refer
interested readers to (xiao2016Trojan_survey, ) for a detailed survey on HTs
and HT detection techniques.

Note that activating the trigger is not only essential for logic testing
techniques but also helpful for side-channel-based techniques because
activating the trigger leads to an increase in the side-channel footprint of
the HT, making it easier to detect (TARMAC_TCAD, ).

Although activating the trigger is critical, it is difficult to do so
efficiently. Consider Figure 1; the defender needs up to $20\times 10^{6}$
test patterns to guarantee trigger activation because the defender does not
know which rare nets make the trigger. Next, we outline the ideal
characteristics required from any technique for activating the trigger. (1)
High trigger activation rate: The technique should activate a large number of
trigger conditions to detect HTs successfully.222Trigger activation rate,
i.e., the proportion of trigger conditions activated by a set of test
patterns, is also called trigger coverage. (2) Small test generation time: The
time required to generate the test patterns should not be large; otherwise,
the technique will not be scalable to larger designs. (3) Compact set of test
patterns: The number of test patterns required to activate the trigger
conditions should be small. A large number of test patterns affect the testing
cost adversely. (4) Feedback-guided approach: The technique should analyze the
test patterns and their impact on the circuit to generate new test patterns,
thereby reducing the test generation time and the size of the test set.

###  1.3. Prior Works and Their Limitations

MERO generates test patterns that activate each rare net $N$ times
(chakraborty2009mero, ). The hypothesis is that if all the rare nets are
activated $N$ times, the test patterns are likely to activate the trigger. The
algorithm starts with a large pool of random test patterns and iteratively
performs circuit simulation to keep track of the number of rare nets that get
activated. While MERO provides moderate performance for small benchmarks, it
fails for large benchmarks. For instance, the trigger coverage of MERO for the
MIPS processor is only 0.2% (TARMAC_TCAD, ), as it violates the
characteristics (1), (2), (3), and (4) mentioned above.

TARMAC overcomes the limitations of MERO by transforming the problem of test
pattern generation into a clique cover problem (TARMAC_TCAD, ). It iteratively
finds maximal cliques of rare nets that satisfy their rare values. By not
relying on brute force, TARMAC outperforms MERO by a factor of 71$\times$ on
average. However, the performance of TARMAC is sensitive to randomness since
the algorithm relies on randomly sampled cliques. Although the test generation
time for TARMAC is short, it violates characteristics (3) and (4).

TGRL uses RL along with a combination of rareness and testability measures to
overcome the limitations of TARMAC (pan2021automated, ). TGRL achieves better
coverage than TARMAC and MERO while reducing the run-time. However, it still
violates characteristic (3), as evidenced by our results in Section 4.

###  1.4. Our Contributions

As discussed above, all existing techniques for trigger activation fall short
on one or more fronts. In this work, we propose a new technique that is
designed to satisfy all four ideal characteristics. We model the test
generation problem for HT detection as an RL problem because test generation
involves searching a large space to find an optimal set of test patterns. This
is exactly what RL algorithms do: they navigate large search spaces to find
optimal solutions. However, there are several challenges that need to be
overcome to realize a practical and scalable RL agent, such as (i) large
amount of training time required for large designs, (ii) the agent needs to be
efficient while choosing actions, and (iii) some challenging benchmarks
require smart fine-tuning. We provide further details on how we overcome these
challenges in Section 3. The primary contributions of our work are as follows.

  * •

We develop an RL technique that is efficient in activating rare trigger
conditions, thereby addressing the limitations of the state-of-the-art HT
detection techniques.

  * •

We overcome several challenges to make our technique scalable to a large
design like the MIPS processor.

  * •

We perform an extensive evaluation on diverse benchmarks and demonstrate the
capability of our technique, which outperforms the state-of-the-art logic-
testing techniques on all benchmarks.

  * •

Our technique provides two orders of magnitude ($169\times$) reduction in the
size of the test set compared to existing techniques.

  * •

Our technique maintains similar trigger coverage ($\leq 2\%$ drop) with
increasing number of rare nets, whereas the state-of-the-art technique’s
performance drops to $0\%$.

  * •

Our technique maintains similar trigger coverage ($\leq 2\%$ drop) for at
least $64\times$ more potential trigger conditions.

  * •

We release our benchmarks and test patterns (DETERRENT-git, ).

##  2\. Assumptions and Background

###  2.1. Threat Model

We assume the standard threat model used in logic testing-based HT detection
(chakraborty2009mero, ; TARMAC_TCAD, ; pan2021automated, ). We assume that the
adversary inserts HTs in rare nets of the design to remain stealthy. The
defender’s (i.e., our) objective is to generate a minimal set of test patterns
that activate unknown trigger conditions. We generate test patterns using only
the golden (i.e., HT-free) netlist.

###  2.2. Reinforcement Learning

RL is a machine learning methodology where an intelligent agent learns to
navigate an environment to maximize a cumulative reward. It is formalized as a
Markov decision process. An RL agent interacts with the environment in
discrete time steps. At each step, the agent receives the current state and
the reward, and it chooses the action which is sent to the environment. The
environment moves the agent to a new state and provides a reward corresponding
to the state transition and action. The aim of the RL agent is to learn a
policy $\pi$ that maximizes the expected cumulative reward. The policy maps
state-action pairs to probabilities of taking that action in a given state.
The agent learns the optimal or near-optimal policy in a trial-and-error
method by interacting with the environment.

##  3\. DETERRENT: Detecting Trojans using Reinforcement Learning

We now formulate the trigger activation problem as an RL problem, but it
suffers from challenges related to scalability, efficiency, and poor
performance. We then address these challenges and devise a final RL agent that
outperforms all existing techniques.

###  3.1. A Simple Formulation

As shown in Figure 1, to activate the trigger, the defender has to apply an
input pattern that forces all four rare nets to take their rare values
simultaneously,333For the sake of conciseness, henceforth, we shall use the
phrase “activate the rare nets” instead of “force the rare nets to take their
rare values.” but the defender does not know which four rare nets constitute
the trigger. A naïve solution is to generate one input pattern for each
combination of four rare nets. Such an approach would require up to
${{}^{r}}C_{4}$ test patterns ($r$ is the total number of rare nets), which
would be infeasible to employ in practice. However, one input pattern can
activate multiple different combinations of rare nets simultaneously. So, we
need to find a minimal set of input patterns that can collectively activate
all combinations of rare nets. This problem is a variant of the set-cover
problem, which is NP-complete (cormen2009introduction, ). We call a set of
rare nets compatible if there exists an input pattern that can activate all
the rare nets in the set simultaneously. Thus, our objective is to develop an
RL agent that generates maximal sets of compatible rare nets.

We now map the trigger activation problem into an RL problem by formulating it
as a Markov decision process.

  * •

States $\mathcal{S}$ is the set of all subsets of the rare nets. An individual
state $s_{t}$ represents the set of compatible rare nets at time $t$.

  * •

Actions $\mathcal{A}$ is the set of all rare nets. An individual action
$a_{t}$ is the rare net chosen by the agent at time $t$.

  * •

State transition $P(s_{t+1}|a_{t},s_{t})$ is the probability that action
$a_{t}$ in state $s_{t}$ leads to the state $s_{t+1}$. In our case, if the
chosen rare net (i.e., the action) is compatible with the current set of rare
nets (i.e., the current state), we add the chosen rare net to the set of
compatible rare nets (i.e., the next state). Otherwise, next state remains the
same as the current state. Thus, in our case, the state transition is
deterministic, as shown below.

$s_{t+1}=\begin{dcases}\\{a_{t}\\}\cup s_{t},&\text{if }a_{t}\text{ is
compatible with }s_{t}\\\ s_{t},&\text{otherwise}\end{dcases}$

  * •

Reward function $R(s_{t},a_{t})$ is equal to the square of the size of the
next state for compatible states, and 0 otherwise.

$R(s_{t},a_{t})=\begin{dcases}|\\{a_{t}\\}\cup
s_{t}|^{2}=|s_{t+1}|^{2},&\text{if }a_{t}\text{ is compatible with }s_{t}\\\
0,&\text{otherwise}\end{dcases}$

The reward is designed so that the agent tries to maximize the size of the
state, i.e., the number of compatible rare nets. We square the reward at each
step, but any power greater than 1 would be appropriate since we want the
reward function to be convex to account for the fact that as the size of the
state grows, the difficulty of finding a new compatible rare net increases.

  * •

Discount factor $\gamma$ $(0\leq\gamma\leq 1)$ indicates the importance of
future rewards relative to the current reward.

The initial state $s_{0}$ is a singleton set containing a randomly chosen rare
net. At each step $t$, the agent in state $s_{t}$ chooses an action $a_{t}$,
arrives in the next state $s_{t+1}$ according to the state transition rules,
and receives a reward $r_{t}$. This cycle of state, action, reward, and next
state is repeated $T$ times, and this constitutes one episode. At the end of
each episode, the state of the agent reflects the rare nets that are
compatible.444For software implementation, we represent the states (which are
defined as sets) as binary vectors, with each element on the vector indicating
whether the corresponding rare net is present in the state or not. Since the
state and action spaces are discrete, we train our agent using the Proximal
Policy Optimization (PPO) algorithm with default parameters unless specified
otherwise (schulman2017proximal, ).

Once the agent returns the maximal sets of compatible rare nets after
training, we pick the $k$ largest distinct sets and generate the test patterns
corresponding to those sets using a Boolean satisfiability (SAT) solver. $k$
is a hyperparameter of our technique.

Our experiments indicate that this simple agent performs well on small
benchmarks. But, for larger benchmarks like the MIPS processor from OpenCores
(OpenCores_MIPS, ) we obtain low trigger coverage ($\approx$70% after training
for 12 hours). We analyzed the basic architecture in detail, and it faces
certain challenges which are presented next.

Figure 2. Combinations of reward and masking methods for MIPS. Eoe: End-of-
episode, M: Masking, NM: No masking

###  3.2. End-of-Episode Reward Computation

Challenge 1: Large training time. The basic architecture requires computing
the reward for each time step, which involves checking if the selected action
is compatible with the current state or not. For a large benchmark like the
MIPS processor, the check takes a few seconds (because of the large number of
gates in the benchmark) each time, and the agent requires millions of steps to
learn. Hence, the training time becomes prohibitively large.

Solution 1. To address challenge 1, we reduce the frequency of reward
computation by computing it only at the end of the episode. At all
intermediate steps, the reward is set to 0. While this approach speeds up the
training by a factor of $\approx 86\times$, the rewards become sparse, and it
affects the performance of our agent. However, the impact on performance is
only $5.6\%$, as shown in Table 1.

Table 1. Comparison of training rates for the reward methods for the MIPS
benchmark: all steps vs. end-of-episode.

Method |  Max. # compatible rare nets | Rate
---|---|---
(steps/min) | (eps./min)
Reward at all steps | 53 | 108 | 0.72
End-of-episode reward | 50 | 9387 | 63
Improvement | -5.6% | 86.91$\times$ | 87.5$\times$

###  3.3. Masking Actions for Efficiency

Challenge 2: Wasted efforts in choosing actions. Another challenge that the
basic architecture suffers from is inefficiency in choosing actions. At each
step, the actions available to the agent remain the same, irrespective of the
state of the agent. This leads to situations where the agent chooses an action
that has already been chosen in the past, or that is known to be not
compatible with at least one of the rare nets in the current state. Hence, the
time spent by the agent on such steps is wasted.

Figure 3. Total loss trends in c2670: default vs. boosted exploration. Figure
4. Architecture of DETERRENT.

Solution 2. To increase the efficiency of the agent in choosing actions, we
mask the actions available to the agent based on the state at any given time
step. This ensures that at each time step, the agent only chooses actions that
lead it to a new state. Additionally, reward computation also becomes less
sparse because episode lengths reduce due to masking (episode ends when there
are no available actions). Since we are eliminating actions from the state
space, one may wonder if this approach may eliminate optimal actions. We now
prove that this is not possible for our problem formulation.

###### Theorem 3.1.

Masking actions does not prevent our agent from learning anything that it
could have learned otherwise.

###### Proof.

Let $\mathcal{P}^{\prime}$ and $\mathcal{P}$ denote an agent that masks and
does not mask actions, respectively. Suppose both $\mathcal{P}$ and
$\mathcal{P}^{\prime}$ are in state $s$. Let $\mathcal{A}$ denote the complete
set of actions, and $\mathcal{A}_{s}$ denote the set of masked actions for
state $s$. So, $\mathcal{A}_{s}=\\{i|i\text{ is compatible with }s\text{ and
}i\notin s\\}$ and $\mathcal{A}_{s}\subseteq\mathcal{A}$. If $\mathcal{P}$
chooses an action $a\in\mathcal{A}\setminus\mathcal{A}_{s}$ (i.e., an action
in the set difference), then $\mathcal{P}$ will stay in the same state because
the rare net corresponding to such an action $a$ would either be incompatible
with $s$ or it would already be in $s$. On the other hand, for any action
$a^{\prime}\in\mathcal{A}_{s}$ chosen by $\mathcal{P}$, agent
$\mathcal{P}^{\prime}$ can also choose the same action $a^{\prime}$ since it
is in $\mathcal{A}_{s}$. Hence, masking does not prevent our agent from
learning anything that the corresponding unmasked agent could have learned. ∎

To enable masking, we compute pairwise compatibility of all rare nets using a
SAT solver before training. Since the compatibility computation for each
unique pair is independent, we parallelize it across 64 processes to reduce
the runtime. During training, for a given state $s$ (i.e., set of compatible
rare nets at the current step), all actions (i.e., rare nets) that are not
compatible with any of the rare nets in $s$ are masked off, and hence, are not
chosen.

To design the best architecture, we implemented agents with all combinations
of reward methods (at all steps and end-of-episode) and masking (with and
without). The results in Figure 2 demonstrate that to obtain the maximum
number of compatible rare nets, the optimal architecture should mask actions
based on state and provide rewards at each time step.

###  3.4. Boosting Exploration

Challenge 3: Convergence to local optima. Since the agent’s objective is to
generate maximal sets of rare nets, for certain benchmarks (for instance,
c2670), the agent gets stuck in local optima. In other words, the agent
quickly learns to capitalize on sub-optimal sets of compatible rare nets,
thereby missing out on the diversity of the sets of compatible rare nets,
resulting in poor trigger coverage.

Solution 3. To force the agent to explore, we (1) include an entropy term in
the loss function of the agent and (2) control the smoothing parameter that
affects the variance of the loss calculation.

To implement (1), we modify the total loss function to
$l=l_{\pi}+c_{\epsilon}\times l_{\epsilon}+c_{v}\times l_{v}$, where $l$ is
the total loss, $l_{\pi}$ is the loss of the policy network, $l_{\epsilon}$ is
the entropy loss, $l_{v}$ is the value loss, and $c_{\epsilon}$ and $c_{v}$
are the coefficients for the entropy and value losses, respectively. We set
$c_{\epsilon}=1$. The entropy loss is inversely proportional to the randomness
in the choice of actions. To implement (2), we set the parameter $\lambda$ for
policy loss $l_{\pi}$ in PPO to $0.99$. This leads to variance in the loss
calculation and hence in the actions chosen by the agent.

Thus, we penalize the agent for having less variance in its choice of actions.
Hence, the agent is forced to explore more and is likely to converge to a
better state, i.e., a state with more compatible rare nets. Figure 3 shows
that by modifying the loss function and the smoothing parameter in PPO, the
loss does not become $0$ quickly, forcing the agent to explore more.

###  3.5. Putting it All Together

The final architecture of DETERRENT is illustrated in Figure 4. In an offline
phase, we find the rare nets of the design and generate pairwise compatibility
information for them in a parallelized manner. Then, for each episode, the
agent starts with a random rare net and takes an action according to the
policy (a neural network) and the action mask. The masked action is evaluated
to produce a reward for the agent, and the agent moves to the next state. This
procedure repeats for $T$ steps (i.e., an episode). Internally, after a
certain number of episodes, the PPO algorithm translates the rewards into
losses (depending on the output of the policy network, which generates
actions, and the value network, which predicts the expected reward of the
action), which are used to update the parameters of the policy and value
networks. Eventually, when the agent has learned the task, the losses become
negligible, and the reward saturates. Once the RL agent gives us the maximal
sets of compatible rare nets, we pick the $k$ largest distinct sets and
generate the test patterns, one for each of those sets, using a SAT solver.

##  4\. Experimental Evaluation

###  4.1. Experimental Setup

Table 2. Comparison of trigger coverage (Cov. (%)) and test length of
DETERRENT with random simulations, Synopsys TestMAX (TestMAX, ), TARMAC
(TARMAC_TCAD, ), and TGRL (pan2021automated, ). Evaluation is done on 100
random four-width triggered HT-infected netlists.

Design | Number | # Gates | Random | TestMAX (TestMAX, ) | TARMAC (TARMAC_TCAD, ) | TGRL (pan2021automated, ) | DETERRENT (this work)
---|---|---|---|---|---|---|---
of rare | Test | Cov. | Test | Cov. | Test | Cov. | Test | Cov. | Test | Patterns Red./ | Cov.
nets | Length | (%) | Length | (%) | Length | (%) | Length | (%) | Length | TARMAC & TGRL | (%)
c2670 | 43 | 775 | 5306 | 10 | 89 | 27 | 5306 | 100 | 5306 | 96 | 8 | 663.25$\bm{\times}$ | 100
c5315 | 165 | 2307 | 8066 | 37 | 103 | 5 | 8066 | 61 | 8066 | 94 | 1585 | 5.08$\bm{\times}$ | 99
c6288 | 186 | 2416 | 3205 | 54 | 38 | 4 | 3205 | 100 | 3205 | 85 | 2096 | 1.52$\bm{\times}$ | 99
c7552 | 282 | 3513 | 9357 | 10 | 137 | 4 | 9357 | 73 | 9357 | 71 | 5910 | 1.58$\bm{\times}$ | 85
s13207 | 604 | 1801 | 9659 | 3 | 106 | 4 | 9659 | 80 | 9659 | 5 | 9600 | 1.01$\bm{\times}$ | 80
s15850 | 649 | 2412 | 9512 | 3 | 110 | 3 | 9512 | 79 | 9512 | 8 | 6197 | 1.53$\bm{\times}$ | 81
s35932 | 1151 | 4736 | 3083 | 99 | 37 | 68 | 3083 | 100 | 3083 | 58 | 6 | 513.83$\bm{\times}$ | 100
MIPS | 1005 | 23511 | 25000 | 0 | 796 | 0 | 25000 | 100 | — | — | 1304 | 19.17$\bm{\times}$ | 97
Avg. | 511 | 5184 | 6884 | 27.75† | 88.57 | 10† | 6884 | 83.5† | 6884 | 86.5† | 3628.85 | 169.68$\bm{\times}$‡ | 95.75†

†The coverages are averaged over c2670, c5315, c6288, and c7552. ‡The
reduction is averaged over all except MIPS.

We implemented our RL agent using PyTorch1.6 and trained it using a Linux
machine with Intel 2.4 GHz CPUs and an NVIDIA Tesla K80 GPU. We used the SAT
solver provided in the pycosat library. We implemented the parallelized
version of TARMAC in Python 3.6. We used Synopsys VCS for logic simulations
and for evaluating test patterns on HT-infected netlists. Similar to prior
works (TARMAC and TGRL), for sequential circuits, we assume full scan access.
To enable a fair comparison, we implemented and evaluated all the techniques
on the same benchmarks as TARMAC and TGRL, which were provided to us by the
authors of TGRL. They also provided us with the TGRL test patterns. We also
performed experiments on the MIPS processor from OpenCores (OpenCores_MIPS, )
to demonstrate scalability. For MIPS, we use vectorized environment with 16
parallel processes to speed up the training. For evaluation, we randomly
inserted $100$ HTs in each benchmark and verified them to be valid using a
Boolean satisfiability check.

###  4.2. Trigger Coverage Performance

In this section, we compare the trigger coverage provided by different
techniques (Table 2). In addition to TARMAC and TGRL, we also compare the
performance of DETERRENT with random test patterns and patterns generated from
an industry-standard tool, Synopsys TestMAX (TestMAX, ). We used the number of
patterns from TGRL as a reference for the random test patterns and TARMAC to
enable a fair comparison. For TestMAX, the number of patterns is determined by
the tool in the default setting (run_atpg).

Note that for s13207, s15850, and s35932, the netlists corresponding to the
test patterns provided by the authors of TGRL were not available to us at the
time of writing the manuscript. Hence, we could only evaluate the TGRL test
patterns for those circuits on our benchmarks. Due to this, the trigger
coverage of TGRL for these benchmarks is low. Additionally, TGRL does not
evaluate on the MIPS benchmark. Hence the corresponding cells in the table are
empty. To enable a fair comparison, we have not included s13207, s15850, and
s35932 in the average test length, as well as MIPS in the average trigger
coverages for all techniques in Table 2.

The results demonstrate that DETERRENT achieves better trigger coverage than
all other techniques while reducing the number of test patterns. On average,
DETERRENT improves the coverage over random patterns ($68\%$), TestMAX
($85.75\%$), TARMAC ($12.25\%$), and TGRL ($9.25\%$), and achieves two orders
of magnitude reduction in the number of test patterns over TARMAC and TGRL
($169\times$).

###  4.3. Impact of Trigger Width

Trigger width, i.e., the number of rare nets that constitute the trigger,
directly affects the stealth of the HT. As the trigger width increases, the
difficulty to activate the trigger increases exponentially. For example, for a
rareness threshold of $0.1$, if the trigger width is $4$, the probability of
activating the trigger through random simulation is $10^{-4}$. Whereas, if the
trigger width is $12$, the probability reduces to $10^{-12}$. Thus, it is
necessary to maintain the performance with increasing trigger width. Figure 5
illustrates the results for c6288; we chose this benchmark as TGRL provides a
good trigger coverage. With increasing trigger width, the performance of TGRL
drops drastically. DETERRENT maintains a steady trigger coverage,
demonstrating that it can activate extremely rare trigger conditions.

Figure 5. Impact of trigger width on the trigger coverage of TGRL
(pan2021automated, ) and DETERRENT for c6288.

###  4.4. Trigger Coverage vs. Number of Patterns

We now investigate the marginal impact of test patterns on trigger coverage.
To do so, we analyze the increase in trigger coverage provided by each test
pattern for DETERRENT and TGRL. Figure 6 demonstrates that DETERRENT obtains
the maximum trigger coverage with very few patterns as opposed to TGRL.

Figure 6. Trigger coverage vs. test patterns comparison.

###  4.5. Impact of Rareness Threshold

Rareness threshold is the probability below which nets are classified as rare,
i.e., the logic values of these nets are strongly biased towards 0 or 1. For a
given trigger width ($\alpha$), as the rareness threshold increases, the
number of rare nets increases (say by a factor of $\beta$), and so, the number
of combinations possible for constructing the trigger increases by a factor of
$\beta^{\alpha}$, making it much more difficult to activate. Figure 7 shows
that the number of rare nets increases with increasing threshold (leading to
up to $64\times$ more potential trigger combinations), but DETERRENT is still
able to achieve similar trigger coverage ($\leq 2\%$ drop) with less than
$2500$ patterns.555The authors of TGRL did not provide us the test patterns
for thresholds other than $0.1$. Hence, we do not compare with TGRL for other
threshold values.

In another experiment, we trained the agent using rare nets for a threshold of
$0.14$ and evaluated the generated test patterns on rare nets with threshold
of $0.1$—the trigger coverage is $99\%$. This hints that we can train the
agent for a large set of rare nets and use it to generate patterns for a
subset of rare nets.

Figure 7. Impact of rareness threshold on the number of rare nets and the
trigger coverage of DETERRENT for c6288.

##  5\. Discussion and Future Work

Comparison with TGRL (pan2021automated, ). Our RL agent architecture is
entirely different from TGRL. TGRL maximizes a heuristic based on the rareness
and testability of nets. In contrast, we identify the problem of trigger
activation to be a set-cover problem and find maximal sets of compatible rare
nets. Moreover, TGRL states and actions are test patterns generated by
flipping bits probabilistically, whereas our agent’s efforts are more directed
by generating maximal sets of compatible rare nets. Due to our formulation, we
achieve better coverage but with orders of magnitude fewer test patterns than
TGRL (see Section 4).

Feasibility of using a SAT solver. We use a SAT solver for the compatibility
check during training and for generating test patterns from the maximal sets
of compatible rare nets provided by the RL agent. Nevertheless, our technique
is scalable for larger designs (as evidenced by our results) because: (i)
During training, we reduce the runtime of using the SAT solver as we generate
a dictionary containing the compatibility information offline in a
parallelized manner. (ii) When generating the test patterns, we only require
invoking the SAT solver $T$ times, where $T$ is the required number of test
patterns. Hence, even for large benchmarks like MIPS, we can generate test
patterns that outperform all the HT detection techniques in less than $12$
hours.

Meta-learning. We generated test patterns for individual benchmarks using
separate agents. Since the training time of our agents for all benchmarks is
less than 12 hours, it is practical to use our technique. As part of future
work, we would like to explore the principles of designing a standalone agent
that can be trained on a corpus of benchmarks once and be used to generate
test patterns for unseen benchmarks. To that end, we plan to extend the
current framework by using principles from meta-learning.

##  6\. Conclusion

Prior works on trigger activation for HT detection have shown reasonable
trigger coverage, but they are ineffective, not scalable, or require a large
number of test patterns. To address these limitations, we develop an RL agent
to guide the search for optimal test patterns. However, in order to design the
agent, we face several challenges like inefficiency and lack of scalability.
We overcome these challenges using different features like masking and
boosting exploration of the agent. As a result, the final architecture
generates a compact set of test patterns for designs of all sizes, including
the MIPS processor. Experimental results demonstrate that our agent reduces
the number of test patterns by $169\times$ on average while improving trigger
coverage. Further evaluations show that our agent is robust against increasing
complexity. Our agent maintains steady trigger coverage for different trigger
widths, whereas the state-of-the-art technique’s performance drops
drastically. Our agent also maintains performance against the increasing
number of possible trigger combinations. Although this work demonstrates the
power of RL for trigger activation, the challenges related to scalability and
efficiency are not specific to the current problem. The ways in which we
overcame the challenges can be used to develop better defenses for other
hardware security problems.

## Acknowledgments

The work was partially supported by the National Science Foundation (NSF
CNS–1822848 and NSF DGE–2039610). Portions of this work were conducted with
the advanced computing resources provided by Texas A&M High Performance
Research Computing.

## References

  * [1] Guillermo Caminero et al.  Adversarial environment reinforcement learning algorithm for intrusion detection.  Computer Networks, 159:96–109, 2019.
  * [2] Konstantin Böttinger et al.  Deep reinforcement fuzzing.  In 2018 IEEE S&P Workshops, pages 116–122. IEEE, 2018.
  * [3] Daimeng Wang et al.  Syzvegas: Beating kernel fuzzing odds with reinforcement learning.  In USENIX, pages 2741–2758, 2021.
  * [4] Hoang-Dung Tran et al.  Safety verification of cyber-physical systems with reinforcement learning control.  ACM TECS, 18(5s):1–22, 2019.
  * [5] Aidin Ferdowsi et al.  Robust deep reinforcement learning for security and safety in autonomous vehicle systems.  In 2018 ITSC, pages 307–312. IEEE, 2018.
  * [6] Thanh Thi Nguyen and Vijay Janapa Reddi.  Deep reinforcement learning for cyber security.  IEEE TNNLS, pages 1–17, 2021.
  * [7] Kan Xiao et al.  Hardware trojans: Lessons learned after one decade of research.  ACM TODAES, 22(1):1–23, 2016.
  * [8] Synopsys.  TestMAX ATPG and TestMAX Diagnosis User Guide.  Version S-2021.06-SP1, 2021.
  * [9] Rajat Chakraborty et al.  MERO: A statistical approach for hardware Trojan detection.  In CHES, pages 396–410. Springer, 2009.
  * [10] Yangdi Lyu and Prabhat Mishra.  Scalable Activation of Rare Triggers in Hardware Trojans by Repeated Maximal Clique Sampling.  IEEE TCAD, 40(7):1287–1300, 2021.
  * [11] Zhixin Pan and Prabhat Mishra.  Automated test generation for hardware trojan detection using reinforcement learning.  In Proceedings of the 26th Asia and South Pacific Design Automation Conference, pages 408–413, 2021.
  * [12] Seetharam Narasimhan et al.  Hardware Trojan detection by multiple-parameter side-channel analysis.  IEEE Transactions on computers, 62(11):2183–2195, 2012.
  * [13] Yuanwen Huang et al.  MERS: statistical test generation for side-channel analysis based Trojan detection.  In Proceedings of the 2016 ACM CCS, pages 130–141, 2016.
  * [14] Yuanwen Huang et al.  Scalable test generation for Trojan detection using side channel analysis.  IEEE TIFS, 13(11):2746–2760, 2018.
  * [15] Yangdi Lyu and Prabhat Mishra.  Efficient test generation for Trojan detection using side channel analysis.  In DATE Conference & Exhibition, pages 408–413. IEEE, 2019.
  * [16] Devendra Rai and John Lach.  Performance of delay-based Trojan detection techniques under parameter variations.  In 2009 IEEE HOST, pages 58–65. IEEE, 2009.
  * [17] Vasudev Gohil.  DETERRENT.  https://github.com/gohil-vasudev/DETERRENT, 2022.
  * [18] Thomas H Cormen et al.  Introduction to algorithms.  MIT press, 2009.
  * [19] John Schulman et al.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * [20] OpenCores.  Educational 16-bit MIPS Processor.  https://opencores.org/projects/mips_16, 2013.  Last accessed the website on 11/17/2021.