# Dyn-Backdoor: Backdoor Attack on Dynamic
Link Prediction

Jinyin Chen, Haiyang Xiong, Haibin Zheng, Jian Zhang, Guodong Jiang and Yi Liu
J. Chen is with the Institute of Cyberspace Security, Zhejiang University of
Technology, Hangzhou, 310023, China.J. Chen, H. Xiong, H. Zheng, Jian Zhang,
G. Jiang are with the College of Information Engineering, Zhejiang University
of Technology, Hangzhou 310023, China.Y. Liu is with the Institute of Process
Equipment and Control Engineering, Zhejiang University of Technology,
Hangzhou, 310023, China.Manuscript received xxxx xx, xxxx; revised xx xx,
xxxx. This research was supported by the National Natural Science Foundation
of China under Grant No. 62072406, the Natural Science Foundation of Zhejiang
Province under Grant No. LY19F020025.

###### Abstract

Dynamic link prediction (DLP) makes graph prediction based on historical
information. Since most DLP methods are highly dependent on the training data
to achieve satisfying prediction performance, the quality of the training data
is crucial. Backdoor attacks induce the DLP methods to make wrong prediction
by the malicious training data, i.e., generating a subgraph sequence as the
trigger and embedding it to the training data. However, the vulnerability of
DLP toward backdoor attacks has not been studied yet. To address the issue, we
propose a novel backdoor attack framework on DLP, denoted as Dyn-Backdoor.
Specifically, Dyn-Backdoor generates diverse initial-triggers by a generative
adversarial network (GAN). Then partial links of the initial-triggers are
selected to form a trigger set, according to the gradient information of the
attack discriminator in the GAN, so as to reduce the size of triggers and
improve the concealment of the attack. Experimental results show that Dyn-
Backdoor launches successful backdoor attacks on the state-of-the-art DLP
models with success rate more than 90%. Additionally, we conduct a possible
defense against Dyn-Backdoor to testify its resistance in defensive settings,
highlighting the needs of defenses for backdoor attacks on DLP.

###### Index Terms:

Dynamic link prediction, backdoor attack, generative adversarial network,
gradient exploration.

##  I Introduction

Graphs are usually used to describe complex systems [1], [2], [3] in various
fields, such as social networks [4], [5], biological networks [6], electric
systems [7], economics [8], neural networks [9], etc. In practice, most of
these systems are evolving with time, which can be modeled as dynamic networks
with nodes or links appearing and disappearing over time [10], [11]. For
instance, the purchases among users and items in e-commerce platforms, e.g.
Taobao, Amazon, are updated in real-time. To predict the next time purchase
behavior in the e-commerce platform can be defined as a link prediction on
dynamic networks. Specifically, dynamic link prediction (DLP) tries to predict
the existence of links at a certain time in the future based on the historical
information of the network, which helps to better understand the evolving
pattern of the network [12]. Taking the e-commerce platform as an example, it
will make targeted product recommendation benefiting from the DLP on basis of
the users’ historical purchase records.

Numerous DLP methods have been proposed. For example, Yao et al. [13]
redefined the indicators for link prediction to extend them from static
networks to dynamic ones, i.e., redefining common neighbor based on timestamps
with different weights. Zhang et al. [14] used the improved resource
allocation for DLP by recalculating the updated part of the graph rather than
the entire graph. For random walk based approaches [15], [16], [17], [18],
they can reduce the complexity of the model, since they usually take a walk of
the local structure. With the success of deep learning applied to computer
vision, DLP methods based on deep learning [19], [20], [21], [22], [23], [24]
are thoroughly studied. They mainly use the nonlinear and hierarchical nature
of neural networks to capture the evolving pattern of dynamic networks. In
particular, the experiments in research [22], [25] demonstrate that DLP
methods based on deep learning generally outperform the non-deep ones.

Figure 1: An illustration of backdoor attack on DLP. On the left side, the
orange subgraph sequence is defined as the backdoor trigger for training and
testing, and the red link represents the target link selected by the attacker.
Specifically, the existence links are represented by solid lines, while the
non-existent links are represented by dashed lines or wireless ones. The right
side shows the behavior of an already backdoored model when fed by a clean
sequence and a backdoored one, respectively. The backdoored model is trained
on data patched with trigger. In the testing stage, the backdoored model
predicts the target link in the backdoor sequence with trigger as the state
chosen by the attacker, and the backdoored model makes correct predictions on
clean sequences.

Besides of the performance study on DLP, its robustness has also raised our
concerns. Research has revealed the vulnerability of DLP methods towards
adversarial attacks [26], [27], which are designed to deceive the model by
carefully crafted adversarial samples in the testing stage. Moreover, the
training stage is quite important to construct an effective DLP model, since
most deep models are highly dependent on the quality and quantity of the
training samples. In other word, DLP methods generally rely on clean training
data with correct labels to guarantee the high prediction accuracy. In
practice, the collection and labeling of training data are usually implemented
in the form of crawlers, logs, crowdsourcing, etc. It is inevitable that the
training data will be polluted with noises, or even injected with predefined
triggers by a malicious collector.

Consequently, backdoor attack on DLP, defined as generating a trigger pre-
injected in the training sequence to make the target link state in the test
sequence as the attacker-chosen state, will be a serious security threat. For
better understanding, we illustrate the backdoor attack on DLP in Fig. 1. In
the training stage, the backdoor attack mixes some of the clean training data
with carefully crafted trigger sequence for the DLP model, to achieve a
backdoored model. In the testing stage, the backdoored model will make the
target link predicted as the attack-chosen state when fed by the backdoored
sequence, i.e., sequence with triggers, while still maintaining high
prediction accuracy on clean ones. For instance, e-commerce platforms
recommend product of interest to customers using DLP method. If the collected
training data have been injected with trigger to leave a backdoor in the DLP,
the platform will make the targeted product recommended purposely, i.e., not
suitable but profitable.

Aiming at graph classification and node classification of static networks,
backdoor attacks have been studied [28, 29], [30]. However, they are not
suitable for target link backdoor attack on DLP for reasons. On one hand,
graph classification is implemented on basis of global graph structure
corresponding to the graph label, while link prediction is accomplished based
on the local structure strongly related to the target link. The global feature
shifting may not influence the target link or node. On the other hand,
considering the dynamic evolution characteristics of DLP, the static trigger
is usually not the optimum to capture the evolving pattern of dynamic
networks.

To address these problems, we propose a novel backdoor attack framework
towards DLP, based on a generative adversarial network (GAN) [31], namely Dyn-
Backdoor. Specifically, we use the initial-triggers to replace the graph
structure directly related to the target link when the target link state is
chosen as the attacker’s manipulated goal. The initial-triggers are derived
from the input noise of the trigger generator. Then, we consider the
concealment of the attack, the initial-triggers extract important links
through the gradient to form triggers. The triggers are optimized through
competition between the trigger generator and the attack discriminator.
Addressing to the dynamic characteristics issue, we capture the dynamic
feature based on the trigger generator composed of the long short-term memory
(LSTM) [32]. Empirically, our approach achieves state-of-the-art results on
four real-world datasets and five DLP methods, compared with several possible
baselines, i.e., gradient information based attack and random attack.
Additionally, we propose a possible defense against Dyn-Backdoor, and the
experiments testify that it can still achieve an attack success rate of more
than 90% under defensive settings.

The main contributions of this paper are summarized as follows:

$\bullet$ To the best of our knowledge, this is the first work that formulates
the problem of backdoor attack on DLP, which reveals the vulnerability of DLP
algorithms in big data collection for training.

$\bullet$ To address the backdoor attack on DLP, we propose an effective
framework, named Dyn-Backdoor. It utilizes GAN to generate a number of diverse
initial-triggers, and further selects important links to generate an optimal
trigger for backdoor attack. Moreover, we analyze the feasibility of backdoor
attack.

$\bullet$ Extensive experiments on five DLP methods over four real-world
datasets demonstrate that Dyn-Backdoor can attack state-of-the-art DLP methods
with success rate of more than 90%. Moreover, the experiments testify that
Dyn-Backdoor is effective against possible defense strategy as well.

The rest of the paper is organized as follows. Related works are introduced in
Section II. The problem definition and threat model are described in Section
III, while the proposed method is detailed in Section IV. Experiment results
and discussion are showed in Section V. Finally, we conclude our work.

##  II Related Work

In this section, we briefly review the related work of DLP methods, backdoor
attacks on graph neural network (GNN) and adversarial attacks on DLP.

###  II-A Dynamic Link Prediction

Recently, a temporal restricted Boltzmann machine (RBM) was adopted with
additional neighborhood information, named ctRBM [33], to learn the dynamic
structural characteristics of graph. As an extension of ctRBM, Li et al. [34]
incorporated temporal RBM and gradient boosting decision tree to model the
evolution pattern of each link.

In addition to RBM-based methods, there are also methods combined with
recurrent neural network (RNN), such as DynGEM [19], DLP-LES [35] etc. Deep
dynamic network embedding (DDNE) [22] is also based on deep autoencoders as
DynGEM and uses GRU as the encoder to extract graph features. Goyal et al.
[20] further proposed dyngraph2vec that has dynamic graph to vector auto
encoder (dynAE), dynamic graph to vector recurrent neural network (dynRNN) and
dynamic graph to vector autoenncoder recurrent neural network (dynAERNN)
through the encoder-decoder architecture. Chen et al. [25] proposed a general
framework for extracting dynamic networks feature information based on
autoencoder and LSTM.

Specifically, graph convolutional network (GCN) based methods and recursive
structures methods extract graph features, such as GC-LSTM [36], EvolveGCN
[23], GDLP [24], and CTGCN [37]. With increasing applications of GAN [31],
[38], [39], DLP methods are also proposed based on generative networks, such
as GCN-GAN [40] and TMF-LSTM [41]. There are some other methods based on
random walk [15], [16], [17], [18], matrix factorization [42], [43], [44],
[45] and continuous time space [46].

###  II-B Backdoor Attacks on GNN

There are currently three studies of backdoor attacks on graph, aiming at
graph classification and node classification of static networks. Zhang et al.
[28] proposed a backdoor attack on graph classification task, which is based
on triggers generated by the Erdős-Rényi model. It is designed to establish
the relationship between label and trigger of the special structure. Xu et al.
[30] further used GNNExplainer to conduct an explainability research on
backdoor attacks of the graph. The other work is graph trojaning attack [29],
which is a generative based method by using a two-layer optimization algorithm
to update the trigger generator and model parameters. Graph trojaning attack
tailors trigger to individual graphs and assumes no knowledge regarding
downstream models or fine-tuning strategies.

Most existing backdoor attacks on graph aim at the classification task and
static networks. They both lack consideration of dynamic characteristics and
the specificity of links as attack targets, which cannot be applied to
backdoor attack on DLP.

###  II-C Adversarial Attacks on DLP

Chen et al. [26] proposed an adversarial attack on DLP. It utilizes the
gradient information to rewire a few links in different snapshots, so as to
make the deep dynamic network embedding (DDNE) fail to make correct
prediction. By using the gradient as the direction of the attack, it can
capture the critical information for attack.

Considering the applicability of the attack, Fan et al. [27] proposed a black-
box attack on DLP. It is based on a stochastic policy-based reinforcement
learning algorithm, thus the performance of DLP degrades with the global
target after the attack.

##  III PRELIMINARY

In this section, we introduce the definition of dynamic networks, DLP and the
backdoor attacks on DLP. For convenience, the definitions of symbols used are
listed in the TABLE I.

TABLE I: THE DEFINITIONS OF SYMBOLS. Notation | Definition
---|---
$G=\left(V,E\right)$ | input graph with nodes $V$, links $E$
$S$, $\widehat{S}$ | clean/backdoored sequence of graphs
$G_{t}$, $\widehat{G}_{t}$ | clean/backdoored graph of time $t$
$f_{\theta}$, $f_{\widehat{\theta}}$ | clean/backdoored DLP model with parameters $\theta$/$\widehat{\theta}$
$E_{T}$, $\widehat{T}$ | target link, the attacker-chosen target link state
$n$, $p$, $t$ | node ratio, poison ratio, trigger of sequence ratio
$Gen_{\alpha}(\cdot)$ | trigger generator
$Atk_{\varphi}(\cdot)$ | attack discriminator
$F(\cdot)$ | filter discriminator
$M(\cdot)$ | trigger mixture function
$Gradient(\cdot)$ | trigger gradient exploration
$Q$ | number of model training iterations
$k$ | number of iterations of the trigger generator
$D_{trigger}$ | trigger set
$D_{train}$ | training data
$N$ | number of nodes in the graph
$T$ | timestamp length in a sequence
$g_{o}$ | output of the generator as initial-trigger
$g$ | trigger, a subgraph sequence, embedded in the sequence
$m$ | the maximum number of modified links of trigger
$z$ | noise as input to the trigger generator

###  III-A Problem Definition

Definition 1 (Dynamic Network) Given a sequence of graphs with length $T$,
denoted as $S$ = $\left\\{G_{t-T},G_{t-T+1},\ldots,G_{t-1}\right\\}$, where
$G_{k}=\left(V,E_{k}\right)$ denotes the $k$-th snapshot of a dynamic network.
Let $V$ denotes the set of all nodes and $E_{k}\subseteq V\times V$ denotes
the temporal links within the fixed timespan $\left[t_{k-1},t_{k}\right]$. The
adjacency matrix of $G_{k}$ is denoted by $A_{k}$ whose element $a_{k;i,j}=1$
if there is a link from node $i$ pointing to node $j$ on $k$-th snapshot,
otherwise $a_{k;i,j}=0$.

Definition 2 (Dynamic Link Prediction) Given a sequence of graphs $S$, DLP
aims to predict the graph structure of next snapshot, which could be
formulated as

$A_{t}^{\prime}=\operatorname{argmax}P\left(A_{t}\mid S\right),$ (1)

where $A_{t}^{\prime}$ denotes the predicted adjacency matrix.

Definition 3 (Trigger and Backdoored Sequence) Given a sequence of graphs $S$,
trigger is a subgraph sequence with length $T$, denoted as $g$ =
$\left\\{Gsub_{t-T},Gsub_{t-T+1},\ldots,Gsub_{t-1}\right\\}$, where $Gsub$ is
a subgraph composed of selected links from a graph of the sequence. The
backdoored sequence $\widehat{S}$ is a sequence of graphs $S$ with the trigger
sequence $g$.

Definition 4 (Backdoor Attack on DLP) Given a sequence of graphs $S$ and
target link $E_{T}$, the backdoor attack will generate a trigger sequence by
subgraph embedded in training data, and then the trigger is called during the
testing stage to make the backdoored model $f_{\widehat{\theta}}$ predict
target link $E_{T}$ as the attacker-chosen state $\widehat{T}$. Meanwhile, the
backdoored model $f_{\widehat{\theta}}$ can still maintain correct predictions
on clean data. The adversary’s objective can be formulated as,

$\displaystyle\left\\{\begin{array}[]{l}f_{\widehat{\theta}}\left(\widehat{S},E_{T}\right)=\widehat{T}\\\
f_{\widehat{\theta}}(\mathrm{S})=f_{\theta}(\mathrm{S})\end{array}\right.$ (2)
$\displaystyle\text{ s.t. }\widehat{S}=M(S,g),\left|g\right|\leq m$

where $M(\cdot)$ is the trigger mixture function that blends $g$ with a given
sequence $S$, and $m$ is the maximum number of modified links.
$f_{\widehat{\theta}}$ is the backdoored model; $f_{\theta}$ is the clean
model; $E_{T}$ is the target link and $\widehat{T}$ is the attacker-chosen
target link state.

Intuitively, the first objective specifies that the target link of backdoor
sequence is misclassified to the attacker-chosen state. The second objective
ensures that clean model and backdoored model are as indistinguishable as
possible in terms of their behaviors on benign sequences.

###  III-B Threat Model

Attacker’s goal. Given a DLP model, the attacker aims to obtain a backdoored
model $f_{\widehat{\theta}}$ which could output the expected prediction
results for any dynamic networks with designed trigger, while keeping fair
performance on clean networks to ensure stealthy.

As shown in Fig. 2, the backdoored model is designed to hide a target link
from being predicted for attack scenario or to convince others that there is a
future link between the target node pair.

Figure 2: Two backdoor attack scenarios on DLP. Attack scenario I indicates
that existence state of link is predicted to be non-existent by trigger.
Attack scenario II indicates that non-existent state of link is predicted to
exist by trigger. The red link is the target link.

Attacker’s capability. We assume that attacker can obtain part of training
data and gradient information during the model training process. The most
state of the target links in the available data is opposite to the attacker-
chosen target link state. Specifically, the attacker can modify the state of
links in the model training stage. The model as attack discriminator is
required to provide gradients to guide the update of generator parameters.

##  IV METHODOLOGY

Dyn-Backdoor launches the target link backdoor attack on DLP by a carefully
designed trigger. In this section, we describe the Dyn-Backdoor in detail from
six stages, i.e., trigger generator, trigger gradient exploration,
optimization of GAN, filter discriminator, backdoored model implementation,
and theoretical analysis on Dyn-Backdoor. The overall framework of Dyn-
Backdoor is shown in Fig. 3.

Figure 3: The framework of Dyn-Backdoor.

###  IV-A Trigger Generator

To generate diverse and effective triggers, Dyn-Backdoor constructs the attack
based on a GAN [31]. We adopt autoencoders and LSTM [32] as the trigger
generator of GAN. Specifically, LSTM is used to capture the dynamic evolution
characteristics of the graph. The combination of autoencoder and LSTM can
effectively generate triggers with nonlinear characteristics and dynamic
evolution characteristics.

The noise $z\in R^{T\times N}$, composed of zero tensors, is fed into the
trigger generator to get the initial-trigger. Specifically,
$z=\left\\{y_{e,1}^{(0)},y_{e,2}^{(0)},\ldots,y_{e,T}^{(0)}\right\\}$ is input
into the multilayer perceptron (MLP),

$\begin{array}[]{c}y_{e,i}^{(k)}=\sigma\left(W_{e}^{(k)}y_{e,i}^{(k-1)}+B_{e}^{(k)}\right)\\\
Y_{e}^{(k)}=\left\\{y_{e,1}^{(k)},y_{e,2}^{(k)},\ldots,y_{e,T}^{(k)}\right\\}\end{array}$
(3)

where $y_{e,i}^{(0)}$ of the first layer is the $i$-th timestamp adjacency
matrix $A_{i}$ in sequence $S$, and $T$ is the timestamp length of the
sequence. $W_{e}^{(k)}$ and $B_{e}^{(k)}$ indicate weight and bias of the
$k$-th layer of the encoder, respectively. Here, we use $\sigma(\cdot)$ as the
$\operatorname{ReLU}$ activation function to increase the nonlinear
representation ability of the generator.

After getting the embedding feature $Y_{e}^{(k)}$ at different timestamps, it
is fed into the LSTM to extract the information of dynamic evolution,

$\begin{array}[]{c}H=LSTM\left(Y_{e}^{(k)}=\left\\{y_{e,1}^{(k)},y_{e,2}^{(k)},\ldots,y_{e,T}^{(k)}\right\\}\right)\\\
Y_{d}^{(k)}=\sigma\left(W_{d}^{(k)}Y_{d}^{(k-1)}+B_{d}^{(k)}\right)\end{array}$
(4)

where $H$ is the feature output through the LSTM, the first layer
$Y_{d}^{(0)}$ of the decoder is $H$. $W_{d}^{(k)}$ and $B_{d}^{(k)}$ are the
weight and bias of the $k$-th layer in the decoder, respectively. It is worth
noting that the last layer $\sigma(\cdot)$ of the decoder uses $Sigmoid$ as
the activation function, other layers $\sigma(\cdot)$ are
$\operatorname{ReLU}$. $Sigmoid$ limits the value of the output of the last
layer to between 0 and 1, which is convenient for converting the output of the
last layer into the topology of the graph. The feature dimension of the output
layer is equal to the number of nodes and the final layer output is initial-
trigger $g_{o}$.

For convenience, we use $Gen_{\alpha}(\cdot)$ to represent the trigger
generator, and $\alpha$ represents all the parameters of the generator,

$g_{o}=Gen_{\alpha}(z)$ (5)

where $g_{o}\in R^{T\times N}$ is the output of the generator as initial-
trigger; $z\in R^{T\times N}$ is noise; $T$ is the timestamp length of the
sequence and $N$ is the number of nodes in the graph.

###  IV-B Trigger Gradient Exploration

To make Dyn-Backdoor stealthy, we try to generate imperceptible triggers as
possible as we can, i.e., small trigger size. We utilize the gradient
information from the attack discriminator to extract the initial-triggers
$g_{o}$ partial link forming the triggers $g$, which reduces the size of the
triggers.

Intuitively, the greater gradient obtained by link gradient matrix means the
greater influence of link on loss. In other words, links with a larger value
in link gradient matrix are more important compared to other links in backdoor
attacks. According to obtained link gradient matrix, the absolute value is
calculated and sorted in descending order. Select top $m$ links to form a
trigger,

$\displaystyle g=\operatorname{Gradient}\left(grad_{u,v},g_{o},m\right)$ (6)
$\displaystyle\text{ s.t. }m=t*N*T$

where $grad_{u,v}$ is the link gradient matrix; $g_{o}$ is an initial-trigger
and $t$ is the trigger of sequence ratio. $N$ is the number of nodes in the
graph; $T$ is the timestamp length of the sequence; $g$ is a trigger and $m$
is the maximum number of modified links of trigger. $Gradient(\cdot)$
represents the operation of trigger gradient exploration.

###  IV-C Optimization of GAN

To generate the effective triggers, we optimize the parameters of the trigger
generator $Gen_{{\alpha}}(\cdot)$ and the attack discriminator
$Atk_{\varphi}(\cdot)$. Optimization of GAN is divided into two stages. Attack
loss $L_{atk}$ is the difference between the prediction state of the target
link and the attacker-chosen target link state, which ensures the
effectiveness of the attack. It can be defined as,

$L_{atk}=\frac{1}{D}\sum_{i=1}^{D}\left[Atk_{\varphi}\left(\hat{S}_{i},E_{T}\right)-\widehat{T}\right]^{2}$
(7)

where $\widehat{S}$ is the backdoored sequence of graphs;
$Atk_{\varphi}(\cdot)$ is attack discriminator; ${E}_{T}$ is the target link;
$\widehat{T}$ is the attacker-chosen target link state and $D$ is the total
number of sequences. In addition, while ensuring the effectiveness of the
attack, we need to ensure the main performance of the backdoored model of DLP.
Taking the global forecast into account, the global loss can be defined as,

$\begin{gathered}L_{r}=\frac{1}{D}\sum_{i=1}^{D}\left[Atk_{\varphi}\left(\hat{S}_{i}\right)-\widehat{G}_{t}\right]^{2}\\\
\end{gathered}$ (8)

where $L_{r}$ is the global loss and $\widehat{G}_{t}$ is the backdoored graph
of time $t$. Therefore, considering the attack of the target link and the
prediction of the global network at the same time, we finally get the
objective loss that needs to be optimized,

$\begin{gathered}L_{all}=L_{atk}+\beta L_{r}\end{gathered}$ (9)

where $\beta$ is a hyperparameter to maintain the balance between attack
effectiveness and global performance. The parameter ${\alpha}$ of the trigger
generator is updated through the $L_{all}$ feedback. After obtaining the
derivatives, we optimize the trigger generator model using stochastic gradient
descent (SGD) with adaptive moment estimation (Adam).

###  IV-D Filter Discriminator

Filter discriminator $F(\cdot)$ is a sorting function, which can select the
trigger with the lowest objective loss $L_{all}$ in the trigger set
$D_{trigger}$. Specifically, since iterating between the trigger generator and
the attack discriminator, we get diverse triggers forming a trigger set
$D_{trigger}$. The filter discriminator $F(\cdot)$ selects the trigger with
the lowest $L_{all}$ to launch a backdoor attack,

$\begin{array}[]{c}g=F\left(D_{trigger,L_{all}}\right)\end{array}$ (10)

where $F(\cdot)$ is filter discriminator; $D_{trigger}$ is the trigger set;
$L_{all}$ is the objective loss and $g$ is the trigger. The trigger $g$
selected by $F(\cdot)$ is used to embed in the training data.

TABLE II: The basic statistics of the dynamic networks. Datasets | Nodes | Edges | Average Degree | Timespan(days)
---|---|---|---|---
Radoslaw [47] | 167 | 82.9K | 993.1 | 271.2
Contact [48] | 274 | 28.2K | 506.2 | 4
Fb-forum [49] | 899 | 50.5K | 669.8 | 164.5
DNC [50] | 2029 | 39.2K | 38.7 | 575
TABLE III: PARAMETERS OF model. Model | Parameters
---|---
Trigger Genetator | No. units in encoder: 256; No. units in LSTM: 256; No. units in decoder: $N$; Learning rate: 0.01; Weight decay: 0.0005
DDNE [22] | No. units in encoder: 128; No. units in decoder: 128, $N$ (for Radoslaw and Contact)
No. units in encoder: 256; No. units in decoder: 256, $N$ (for Fb-forum and
DNC)
Learning rate: 0.01 (for Radoslaw and Contact) $\mid$ 0.001 (for Fb-forum and
DNC); Weight decay: 0.0005
DynAE [20] | No. units in hidden layer: 128; No. units in output layer: $N$ (for Radoslaw and Contact)
No. units in hidden layer: 256; No. units in output layer: $N$ (for Fb-forum
and DNC)
Learning rate: 0.01 (for Radoslaw and Contact) $\mid$ 0.001 (for Fb-forum and
DNC); Weight decay: 0.0005
DynRNN [20] | the same as DynAE
DynAERNN [20] | No. units in hidden layer: 128; No. units in LSTM: 128; No. units in output layer: $N$ (for Radoslaw and Contact)
No. units in hidden layer: 256; No. units in LSTM: 128; No. units in output
layer: $N$ (for Fb-forum and DNC)
Learning rate: 0.01 (for Radoslaw and Contact) $\mid$ 0.001 (for Fb-forum and
DNC); Weight decay: 0.0005
E-LSTM-D [25] | No. units in encoder: 128; No. units in LSTM: 128; No. units in decoder: $N$ (for Radoslaw and Contact)
No. units in encoder: 256; No. units in LSTM: 256; No. units in decoder: $N$
(for F+b-forum and DNC)
Learning rate: 0.01 (for Radoslaw and Contact) $\mid$ 0.001 (for Fb-forum and
DNC); Weight decay: 0.0005

##  V Experiments and Discussion

###  V-A Datasets

To testify the performance of Dyn-Backdoor, we select four real-world datasets
to conduct experiments. The graphs are all directed and unweighted with
different scales. The basic statistics are summarized in TABLE II.

Radoslaw [47]: It is an email network, and each node represents an employee in
a mid-sized company. Its average distance is 993.1 and spans 271.2 days.

Contact [48]: It is a human contact dynamic network. The data are collected
through the wireless devices carried by people. A link between person source
and target emerges along with a timestamp if source gets in touch with target.
The data are recorded every 20 seconds and spans 3.97 days.

Fb-forum [49]: The data are attained from a Facebook-like online forum of
students at University of California at Irvine, in 2004. It is an online
social network where nodes are users and links represent inter-actions (e.g.,
messages) between students. The records span more than 5 months.

DNC [50]: This is a directed graph of emails in the 2016 Democratic National
Committee (DNC) email leak. Nodes in the graph correspond to persons in
dataset. A directed edge in dataset denotes that a person has sent an email to
another one.

(a) Radoslaw

(b) Contact

(c) Fb-forum

(d) DNC

Figure 4: In attack scenario I, the performance of the four attack methods on
the ASR, AMC and AUC of the five dynamic models. (a), (b), (c) and (d)
correspond to the experiments on the Radoslaw dataset, Contact dataset, Fb-
forum dataset and DNC dataset. RB, GB, Dyn-One and Dyn-Backdoor represent four
methods of backdoor attack. Clean model represents a model trained with clean
data.

###  V-B Baseline Methods

To verify the effectiveness of the backdoor attack methods, we choose five
end-to-end DLP methods to attack. The parameter settings of DLP models and
trigger generator of Dyn-Backdoor are shown in Table III. Since this is the
first work of DLP backdor attack, we design three baseline attacks to compare
with Dyn-Backdoor.

Random Backdoor (RB): RB is to randomly select links to form the trigger, and
then the trigger is embedded into the dataset for training.

Gradient Backdoor (GB): GB obtains gradient information from a certain epoch
during the model training to generate the trigger, and then the trigger is
embedded into the dataset for training.

Dyn-One: Dyn-One is a variant of Dyn-Backdoor, which only generates the
trigger in a certain epoch during the model training, and then the trigger is
embedded into the dataset for training.

###  V-C Metrics

To evaluate the effectiveness of the attacks, we use three metrics.
$\left(i\right)$ _attack timestamp rate_ (ATR), which represents ratio of the
number of timestamps incorrectly predicted for the target link to all
timestamps correctly predicted by clean model. Trigger can be called for all
test samples to control the DLP method’s prediction of the target link, so we
propose ATR to measure the effectiveness of the attack,

$\displaystyle\text{ ATR }=\frac{\text{ Number of successful attack timestamps
}}{\text{ Number of total attack timestamps }}$ (11)

$\left(ii\right)$ _attack success rate_ (ASR), which represents the average
ATR for attacking $L$ target links. A larger value of ASR indicates better
attack performance,

$\displaystyle\text{ ASR}=\frac{1}{L}\sum_{l=1}^{L}\text{ ATR }$ (12)

and $\left(iii\right)$ _average misclassification confidence_ (AMC), which
represents the confidence score of the average output of all successfully
attacked links. The lower AMC represents the better performance in attack
scenario I. In contrast, the higher AMC represents the better performance in
attack scenario II.

To evaluate the attack evasiveness, we choose the _area under curve_ (AUC),
which is commonly used in DLP to measure performance. If among $n$ independent
comparisons, there are $n^{\prime}$ times that the existing link gets a higher
score than the nonexistent link and $n^{\prime\prime}$ times they get the same
score, then the AUC is defined as,

$AUC=\frac{n^{\prime}+0.5n^{\prime\prime}}{n}$ (13)

(a) Radoslaw

(b) Contact

(c) Fb-forum

(d) DNC

Figure 5: In attack scenario II, the performance of the four attack methods on the ASR, AMC and AUC of the five dynamic models. (a), (b), (c) and (d) correspond to the experiments on the Radoslaw dataset, Contact dataset, Fb-forum dataset and DNC dataset. RB, GB, Dyn-One and Dyn-Backdoor represent four methods of backdoor attack. Clean model represents the model trained with clean data. TABLE IV: The transferability of Dyn-Backdoor on Radoslaw dataset. I and II are the results under attack scenario I and attack scenario II, respectively. The bolded value is the reference value. The value of arrow represents the difference between the effect of the transferability Dyn-Backdoor and the original Dyn-Backdoor. Attack Discriminator | Target Models | ASR(I)(%) | AMC(I)(%) | ASR(II)(%) | AMC(II)(%)
---|---|---|---|---|---
DDNE [22] | DDNE | 100(-) | 0.02 | 99.83(-) | 99.37
DynAE |  94.66$\left(\downarrow 5.34\right)$ | 2.53 |  88.36$\left(\downarrow 11.49\right)$ | 98.08
DynRNN |  92.21 $\left(\downarrow 7.79\right)$ | 6.11 |  97.65$\left(\downarrow 2.18\right)$ | 91.06
DynAERNN |  26.91$\left(\downarrow 73.09\right)$ | 28.90 |  71.32$\left(\downarrow 28.56\right)$ | 79.39
E-LSTM-D |  43.6$\left(\downarrow 56.40\right)$ | 24.86 |  67.31$\left(\downarrow 32.58\right)$ | 82.16
DynAE [20] | DDNE |  99.15$\left(\downarrow 0.18\right)$ | 1.47 |  99.08$\left(\uparrow 3.55\right)$ | 97.42
DynAE | 99.96(-) | 0.31 | 95.68(-) | 97.62
DynRNN |  91.7$\left(\downarrow 8.26\right)$ | 8.46 |  96.56$\left(\uparrow 0.92\right)$ | 87.88
DynAERNN |  26.82$\left(\downarrow 73.17\right)$ | 23.35 |  47.07$\left(\downarrow 50.80\right)$ | 72.25
E-LSTM-D |  25.49$\left(\downarrow 74.50\right)$ | 28.53 |  52.31$\left(\downarrow 45.33\right)$ | 75.76
DynRNN [20] | DDNE |  97.80$\left(\uparrow 0.63\right)$ | 2.48 |  98.70$\left(\uparrow 0.36\right)$ | 96.94
DynAE |  95$\left(\downarrow 2.25\right)$ | 4.13 |  74.01$\left(\downarrow 24.75\right)$ | 95.29
DynRNN | 97.19(-) | 2.80 | 98.35(-) | 89.92
DynAERNN |  41.93$\left(\downarrow 56.86\right)$ | 22.46 |  55.04$\left(\downarrow 44.04\right)$ | 70.90
E-LSTM-D |  23.98$\left(\downarrow 75.33\right)$ | 30.80 |  60.07$\left(\downarrow 38.92\right)$ | 75.99
DynAERNN [20] | DDNE |  84.97$\left(\uparrow 34.02\right)$ | 8.80 |  97.10$\left(\uparrow 33.78\right)$ | 97.55
DynAE |  36.16$\left(\downarrow 42.97\right)$ | 17.90 |  82.07$\left(\uparrow 13.08\right)$ | 95.13
DynRNN |  53.59$\left(\downarrow 15.47\right)$ | 18.67 |  95.02$\left(\uparrow 30.92\right)$ | 86.77
DynAERNN | 63.40(-) | 13.40 | 72.58(-) | 72.80
E-LSTM-D |  14.62$\left(\downarrow 72.94\right)$ | 30.35 |  62.03$\left(\downarrow 14.54\right)$ | 80.14
E-LSTM-D [25] | DDNE |  95.43$\left(\uparrow 27.26\right)$ | 3.72 |  96.96$\left(\uparrow 6.13\right)$ | 98.03
DynAE |  73.07$\left(\downarrow 2.56\right)$ | 9.41 |  85.91$\left(\downarrow 5.97\right)$ | 97.76
DynRNN |  85.33$\left(\uparrow 13.79\right)$ | 5.04 |  96.97$\left(\uparrow 6.14\right)$ | 94.83
DynAERNN |  34.34$\left(\downarrow 54.21\right)$ | 22.84 |  64.97$\left(\uparrow 28.89\right)$ | 78.24
E-LSTM-D | 74.99(-) | 15.18 | 91.36(-) | 89.42

###  V-D Experiment Setup

This section describes the settings in experiments. Considering the trade-off
of attack effectiveness and concealment, $\beta$ in the objective loss
Equation 9 is set to 0.5. Since the DLP models as the attack discriminator
have a good performance on DLP after 100 epochs, so the pre-trained epoch of
the models is 100.

To avoid the contingency of the attack, we select a total of 100 links as the
target links, and each attack scenario has 50 target links. More specifically,
in attack scenario I, prediction confidence score of each target link under
clean model is larger than 0.9. These links with higher confidence scores can
better verify the effectiveness of the attack. In attack scenario II,
prediction confidence score of each target link in clean model is between 0
and 0.1.

To balance the concealment and the effectiveness of the attack, we set the
trigger of sequence ratio $t$ = 0.05, the poison ratio $p$ = 0.05, and the
node ratio $n$ = 0.05 for attack scenario I, while $t$ = 0.03, $p$ = 0.05 and
$n$ = 0.05 for attack scenario II.

To observe the performance comparison of trigger injection at different
timestamps, trigger injection timestamp analysis sets $t$ = 0.03, $p$ = 0.03
and $n$ = 0.03. In addition, to analyze the impact of parameter changes on the
attack, parameter sensitive experiments set the fixed parameter value to 0.03.

In the experiments of backdoor attacks on non-deep learning methods, we chose
Deepwalk [51] and node2vec [52] models. First, the sequence obtains the node
embedding by the two methods. Then the features of historical moments in the
sequence are superimposed together and fed into an MLP to realize the DLP.
Considering the size of the graph, we choose the embedding dimension of the
Deepwalk and node2vec models to be 128.

Our experimental environment consists of Intel XEON 62402.6GHz x 18C (CPU),
Tesla V100 32GiB (GPU), 16GiBmemory (DDR4-RECC 2666) and Ubuntu 16.04 (OS).

###  V-E Overall Performance of Backdoor Attacks

To verify the effectiveness of Dyn-Backdoor compared with other attack
methods, we conduct attack experiments in both scenarios. Specifically, attack
scenario I indicates that existence state of link is predicted to be non-
existent. Attack scenario II indicates that non-existent state of link is
predicted to exist.

Fig. 4 shows the experimental results under attack scenario I. Dyn-Backdoor
has the best performance among five attack methods in terms of ASR, AMC and
AUC, except for the result of the DNC dataset on DynRNN. There are three
possible reasons for this phenomenon. First, the competition between the
trigger generator and the attack discriminator optimizes the initial-triggers.
Then, the gradient information from the attack discriminator extracts the
important subgraph structure of the initial-triggers to form the triggers. In
addition, Dyn-Backdoor has a dynamically evolving trigger in the training
stage, that is, re-optimize the trigger at a certain interval of training
iterations.

The AUC obtained by the backdoored model under the clean testing data is
similar to the clean model. We believe that Dyn-Backdoor is aimed at a target
link, and the disturbance caused by the entire graph is imperceptible. As
shown in Fig. 4 (d), the ASR of Dyn-Backdoor is 45.50% on DynRNN, while the
ASR of GB is 97.00%. The possible reason is that Dyn-Backdoor is difficult to
find effective triggers by a generative way for the DNC dataset, which is the
sparse and has more nodes than other datasets.

Fig. 5 shows the experimental results under attack scenario II. It is worth
noting that the trigger size of attack scenario II is smaller than attack
scenario I, but the attack effect becomes better in attack scenario II in
terms of ASR, e.g., the ASR of DDNE reaches 100% in Fig. 5(a) and the ASR of
E-LSTM-D reaches 100% in Fig. 5(c). There are two possible reasons for this
phenomenon. First, there is no interference from redundant neighbors between
two nodes, it is easier to establish a connection between the two nodes
through a trigger. Second, these models pay more attention to the existence
state of links when implementing link prediction tasks.

###  V-F Attack Transferability

Since in most practical situations, the attacker may not grasp the detail of
the target DLP model in prior, it is more practical to conduct a black-box
setting attack, i.e., without any structure or parameter information of the
DLP model. To verify the effect of the Dyn-Backdoor under black-box setting,
we adopt one DLP model as the attack discriminator, and transfer the generated
trigger to backdoor other DLP as the target models, named as transferable
attack. Table IV shows the transferability attack results on Radoslaw.

In attack scenario I, we find that Dyn-Backdoor’s attack effect is significant
against DDNE model, e.g. the ASR of attacking DDNE reaches 99.15%, using DynAE
as the attack discriminator in Table IV. When attacking the DDNE model, ASR
can reach more than 80%. This shows that DDNE has a strong ability to capture
the network structure, and its robustness needs to be further strengthened.
Dyn-Backdoor fails to achieve satisfactory results on DynAERNN and E-LSTM-D
models, e.g. the ASR of attacking DynARRNN reaches 63%, using DDNE as the
attack discriminator and the ASR of attacking E-LSTM-D reaches 58.89%, using
DynRNN as the attack discriminator. We believe that they have more neural
network layers than other models, which means that the information generated
by the guided trigger is dispersed into more neural network layers so that the
generative approach is difficult to generate effective triggers.

Figure 6: Parameter sensitivity analysis of Dyn-Backdoor of $t$, $p$ and $n$
on Fb-forum dataset.

In attack scenario II, Dyn-backdoor can maintain good performance as well by
achieving over 99% ASR against several models, e.g. DDNE, DynRNN and DynARRNN.
We find that the attack effects on the DDNE and DynAE models are very similar,
e.g. the ASR of DDNE achieves 99.15% and the ASR of DynAE achieves 99.96% in
Table IV on DynAE as attack discriminator. The possible reason is that the
encoder and decoder structures used by the two models are relatively similar.
Although the models capture feature information in different ways, most DLP
methods can maintain good performance. The attacker chooses a good-performance
DLP model as the attack discriminator, and can perform Dyn-Backdoor under the
black-box setting.

###  V-G Parameter Sensitivity

The performance of Dyn-Backdoor will be mainly affected by three sensitive
parameters: 1) the trigger of sequence ratio $t$; 2) the poison rate $p$; and
3) the node rate $n$. In the following, we will investigate their influences
on the Dyn-Backdoor performance. According to the above experiments, the
attack is more difficult to implement in attack scenario I, so we conduct
parameter sensitivity analysis in attack scenario I. Fig. 6 shows the
parameter sensitivity experiment on Fb-forum dataset. The Appendix B shows the
parameter experiment results of other datasets.

When exploring the influence of $t$, Fig. 6 can be observed that as the
proportion of sequence triggers increases, except for the result on DynAERNN,
the ASR will gradually increase. Intuitively, the larger the trigger size, the
easier for the model to capture its structural features. However, when the $t$
increases on the DynAERNN model, the ASR decreases. It may be that the
increase of the $t$ causes the original logic in the data to be destroyed,
which makes the model unable to learn the characteristics of the trigger.

Fig. 6 shows that with the increase of the $p$, the corresponding ASR will
gradually increase. When exploring the influence of $n$, we can observe that
the influence of $n$ and $p$ on the model trend are very similar. This also
shows that nodes with a similar structure to the nodes of target link will
affect the judgment of the target link in the model learning process. In other
words, we can perform backdoor attacks on the model through other similar
nodes, which can also affect the target link.

##  VI Conclusion

This is the first work focuses on backdoor attack on DLP. To address the
problem, we propose a backdoor attack framework on DLP, named Dyn-Backdoor, by
adopting GAN and gradient exploration to form a trigger. Extensive experiments
show the effectiveness of Dyn-Backdoor on DLP. The dynamic model will be left
behind by training data with the trigger. Attacker can launch an attack by
calling the trigger.

However, Dyn-Backdoor is still challenged in several ways. When dealing with
large scale datasets, the convergence is much slower than small ones to
generate triggers. Dyn-Backdoor requires the target model to provide feedback
information, and the backdoor attacks on the black-box setting is also a
possible future research direction.

## References

  * [1] M. Doostmohammadian and U. A. Khan, “On the complexity of minimum-cost networked estimation of self-damped dynamical systems,” _IEEE Trans. Netw. Sci. Eng._ , vol. 7, no. 3, pp. 1891–1900, 2020.
  * [2] X. Liu, Y. Zhou, X. Guan, and C. Shen, “A feasible graph partition framework for parallel computing of big graph,” _Knowl. Based Syst._ , vol. 134, pp. 228–239, 2017.
  * [3] L. Maccari, “Detecting and mitigating points of failure in community networks: A graph-based approach,” _IEEE Trans. Comput. Soc. Syst._ , vol. 6, no. 1, pp. 103–116, 2019.
  * [4] A. Nordio, A. Tarable, C. Chiasserini, and E. Leonardi, “Belief dynamics in social networks: A fluid-based analysis,” _IEEE Trans. Netw. Sci. Eng._ , vol. 5, no. 4, pp. 276–287, 2018.
  * [5] F. Ahmed, A. X. Liu, and R. Jin, “Publishing social network graph eigenspectrum with privacy guarantees,” _IEEE Trans. Netw. Sci. Eng._ , vol. 7, no. 2, pp. 892–906, 2020.
  * [6] J. D. Hirst and M. Sternberg, “Prediction of structural and functional features of protein and nucleic acid sequences by artificial neural networks.” _Biochemistry_ , vol. 31, no. 32, pp. 7211–8, 1992.
  * [7] J. Gao, Y. Xiao, J. Liu, W. Liang, and C. L. P. Chen, “A survey of communication/networking in smart grids,” _Future Gener. Comput. Syst._ , vol. 28, no. 2, pp. 391–404, 2012.
  * [8] M. Kazemilari and M. A. Djauhari, “Correlation network analysis for multi-dimensional data in stocks market,” _Physica A: Statistical Mechanics and its Applications_ , vol. 429, pp. 62–75, 2015.
  * [9] W. Zhang, Y. Tang, W. K. Wong, and Q. Miao, “Stochastic stability of delayed neural networks with local impulsive effects,” _IEEE Trans. Neural Networks Learn. Syst._ , vol. 26, no. 10, pp. 2336–2345, 2015.
  * [10] J. Sun, Y. Yang, N. N. Xiong, L. Dai, X. Peng, and J. Luo, “Complex network construction of multivariate time series using information geometry,” _IEEE Trans. Syst. Man Cybern. Syst._ , vol. 49, no. 1, pp. 107–122, 2019\.
  * [11] H. Liu, X. Xu, J. Lu, G. Chen, and Z. Zeng, “Optimizing pinning control of complex dynamical networks based on spectral properties of grounded laplacian matrices,” _IEEE Trans. Syst. Man Cybern. Syst._ , vol. 51, no. 2, pp. 786–796, 2021.
  * [12] N. M. A. Ibrahim and L. Chen, “Link prediction in dynamic social networks by integrating different types of information,” _Appl. Intell._ , vol. 42, no. 4, pp. 738–750, 2015.
  * [13] L. Yao, L. Wang, L. Pan, and K. Yao, “Link prediction based on common-neighbors for dynamic social network,” in _The 7th International Conference on Ambient Systems, Networks and Technologies (ANT 2016) / The 6th International Conference on Sustainable Energy Information Technology (SEIT-2016) / Affiliated Workshops, May 23-26, 2016, Madrid, Spain_ , ser. Procedia Computer Science, E. M. Shakshuki, Ed., vol. 83. Elsevier, 2016, pp. 82–89.
  * [14] Z. Zhang, J. Wen, L. Sun, Q. Deng, S. Su, and P. Yao, “Efficient incremental dynamic link prediction algorithms in social network,” _Knowl. Based Syst._ , vol. 132, pp. 226–235, 2017.
  * [15] U. G. Acer, P. Drineas, and A. A. Abouzeid, “Random walks in time-graphs,” in _Proceedings of the Second International Workshop on Mobile Opportunistic Networking, MobiOpp ’10, Pisa, Italy, February 22-23, 2010_ , S. Palazzo, T. Camp, and M. Conti, Eds. ACM, 2010, pp. 93–100.
  * [16] N. M. A. Ibrahim, L. Chen, Y. Wang, B. Li, Y. Li, and W. Liu, “Sampling-based algorithm for link prediction in temporal networks,” _Inf. Sci._ , vol. 374, pp. 1–14, 2016.
  * [17] N. M. A. Ibrahim and L. Chen, “An efficient algorithm for link prediction in temporal uncertain social networks,” _Inf. Sci._ , vol. 331, pp. 120–136, 2016.
  * [18] G. H. Nguyen, J. B. Lee, R. A. Rossi, N. K. Ahmed, E. Koh, and S. Kim, “Continuous-time dynamic network embeddings,” in _Companion of the The Web Conference 2018 on The Web Conference 2018, WWW 2018, Lyon , France, April 23-27, 2018_ , P. Champin, F. Gandon, M. Lalmas, and P. G. Ipeirotis, Eds. ACM, 2018, pp. 969–976.
  * [19] P. Goyal, N. Kamra, X. He, and Y. Liu, “Dyngem: Deep embedding method for dynamic graphs,” _CoRR_ , vol. abs/1805.11273, 2018.
  * [20] P. Goyal, S. R. Chhetri, and A. Canedo, “dyngraph2vec: Capturing network dynamics using dynamic graph representation learning,” _Knowl. Based Syst._ , vol. 187, 2020.
  * [21] Q. Xuan, H. Xiao, C. Fu, and Y. Liu, “Evolving convolutional neural network and its application in fine-grained visual categorization,” _IEEE Access_ , vol. 6, pp. 31 110–31 116, 2018.
  * [22] T. Li, J. Zhang, P. S. Yu, Y. Zhang, and Y. Yan, “Deep dynamic network embedding for link prediction,” _IEEE Access_ , vol. 6, pp. 29 219–29 230, 2018.
  * [23] A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. B. Schardl, and C. E. Leiserson, “Evolvegcn: Evolving graph convolutional networks for dynamic graphs,” in _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_. AAAI Press, 2020, pp. 5363–5370.
  * [24] J. Chen, X. Lin, C. Jia, Y. Li, and Y. Liu, “Generative dynamic link prediction,” _Chaos_ , vol. 29, no. 12, p. 123111, 2019.
  * [25] J. Chen, J. Zhang, X. Xu, C. Fu, D. Zhang, Q. Zhang, and Q. Xuan, “E-LSTM-D: A deep learning framework for dynamic network link prediction,” _IEEE Trans. Syst. Man Cybern. Syst._ , vol. 51, no. 6, pp. 3699–3712, 2021\.
  * [26] J. Chen, J. Zhang, Z. Chen, M. Du, and Q. Xuan, “Time-aware gradient attack on dynamic network link prediction,” _CoRR_ , vol. abs/1911.10561, 2019.
  * [27] H. Fan, B. Wang, P. Zhou, A. Li, M. Pang, Z. Xu, C. Fu, H. Li, and Y. Chen, “Reinforcement learning-based black-box evasion attacks to link prediction in dynamic graphs,” _CoRR_ , vol. abs/2009.00163, 2020.
  * [28] Z. Zhang, J. Jia, B. Wang, and N. Z. Gong, “Backdoor attacks to graph neural networks,” in _SACMAT ’21: The 26th ACM Symposium on Access Control Models and Technologies, Virtual Event, Spain, June 16-18, 2021_ , J. Lobo, R. D. Pietro, O. Chowdhury, and H. Hu, Eds. ACM, 2021, pp. 15–26.
  * [29] Z. Xi, R. Pang, S. Ji, and T. Wang, “Graph backdoor,” _CoRR_ , vol. abs/2006.11890, 2020.
  * [30] J. Xu, M. Xue, and S. Picek, “Explainability-based backdoor attacks against graph neural networks,” in _WiseML@WiSec 2021: Proceedings of the 3rd ACM Workshop on Wireless Security and Machine Learning, Abu Dhabi, United Arab Emirates, July 2, 2021_ , C. Pöpper and M. Vanhoef, Eds. ACM, 2021, pp. 31–36.
  * [31] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio, “Generative adversarial nets,” in _Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada_ , Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, Eds., 2014, pp. 2672–2680.
  * [32] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural Comput._ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [33] X. Li, N. Du, H. Li, K. Li, J. Gao, and A. Zhang, “A deep learning approach to link prediction in dynamic networks,” in _Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia, Pennsylvania, USA, April 24-26, 2014_ , M. J. Zaki, Z. Obradovic, P. Tan, A. Banerjee, C. Kamath, and S. Parthasarathy, Eds. SIAM, 2014, pp. 289–297.
  * [34] T. Li, B. Wang, Y. Jiang, Y. Zhang, and Y. Yan, “Restricted boltzmann machine-based approaches for link prediction in dynamic networks,” _IEEE Access_ , vol. 6, pp. 29 940–29 951, 2018.
  * [35] K. Selvarajah, K. Ragunathan, Z. Kobti, and M. Kargar, “Dynamic network link prediction by learning effective subgraphs using CNN-LSTM,” in _2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, United Kingdom, July 19-24, 2020_. IEEE, 2020, pp. 1–8.
  * [36] J. Chen, X. Xu, Y. Wu, and H. Zheng, “GC-LSTM: graph convolution embedded LSTM for dynamic link prediction,” _CoRR_ , vol. abs/1812.04206, 2018.
  * [37] J. Liu, C. Xu, C. Yin, W. Wu, and Y. Song, “K-core based temporal graph convolutional network for dynamic graphs,” _CoRR_ , vol. abs/2003.09902, 2020\.
  * [38] K. Liu, Y. Li, J. Yang, Y. Liu, and Y. Yao, “Generative principal component thermography for enhanced defect detection and analysis,” _IEEE Trans. Instrum. Meas._ , vol. 69, no. 10, pp. 8261–8269, 2020.
  * [39] K. Liu, Y. Tang, W. Lou, Y. Liu, J. Yang, and Y. Yao, “A thermographic data augmentation and signal separation method for defect detection,” _Measurement Science and Technology_ , vol. 32, no. 4, p. 045401 (10pp), 2021\.
  * [40] K. Lei, M. Qin, B. Bai, G. Zhang, and M. Yang, “GCN-GAN: A non-linear temporal link prediction model for weighted dynamic networks,” in _2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019_. IEEE, 2019, pp. 388–396.
  * [41] M. Yang, J. Liu, L. Chen, Z. Zhao, X. Chen, and Y. Shen, “An advanced deep generative framework for temporal link prediction in dynamic networks,” _IEEE Trans. Cybern._ , vol. 50, no. 12, pp. 4946–4957, 2020.
  * [42] M. Brand, “Fast low-rank modifications of the thin singular value decomposition,” _Linear Algebra & Its Applications_, vol. 415, no. 1, pp. 20–30, 2006.
  * [43] Z. Zhang, P. Cui, J. Pei, X. Wang, and W. Zhu, “TIMERS: error-bounded SVD restart on dynamic networks,” in _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , S. A. McIlraith and K. Q. Weinberger, Eds. AAAI Press, 2018, pp. 224–231.
  * [44] J. Li, H. Dani, X. Hu, J. Tang, Y. Chang, and H. Liu, “Attributed network embedding for learning in a dynamic environment,” in _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017_ , E. Lim, M. Winslett, M. Sanderson, A. W. Fu, J. Sun, J. S. Culpepper, E. Lo, J. C. Ho, D. Donato, R. Agrawal, Y. Zheng, C. Castillo, A. Sun, V. S. Tseng, and C. Li, Eds. ACM, 2017, pp. 387–396.
  * [45] X. Ma, P. Sun, and Y. Wang, “Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks,” _Physica A: Statistical Mechanics and its Applications_ , vol. 496, pp. 121–136, 2018.
  * [46] Y. Zuo, G. Liu, H. Lin, J. Guo, X. Hu, and J. Wu, “Embedding temporal network via neighborhood formation,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_, Y. Guo and F. Farooq, Eds. ACM, 2018, pp. 2857–2866.
  * [47] “Manufacturing emails network dataset – konect,” Apr. 2017. [Online]. Available: http://konect.uni-koblenz.de/networks/radoslawemail
  * [48] “Haggle network dataset—konect,” Apr. 2017. [Online]. Available: http://konect.uni-koblenz.de/networks/contact
  * [49] “Facebook wall posts network dataset—konect,” Apr. 2017. [Online]. Available: http://konect.uni-koblenz.de/networks/facebook-wosn-wall
  * [50] “Dnc co-recipient network dataset – konect,” Sep. 2016. [Online]. Available: http://konect.uni-koblenz.de/networks/dnc-temporalGraph
  * [51] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: online learning of social representations,” in _The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014_ , S. A. Macskassy, C. Perlich, J. Leskovec, W. Wang, and R. Ghani, Eds. ACM, 2014, pp. 701–710.
  * [52] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016_ , B. Krishnapuram, M. Shah, A. J. Smola, C. C. Aggarwal, D. Shen, and R. Rastogi, Eds. ACM, 2016, pp. 855–864.

|  Jinyin Chen received BS and PhD degrees from Zhejiang University of
Technology, Hangzhou, China, in 2004 and 2009, respectively. She studied
evolutionary computing in Ashikaga Institute of Technology, Japan in 2005 and
2006. She is currently a Professor with the Zhejiang University of Technology,
Hangzhou, China. Her research interests include artificial intelligence
security, graph data mining and evolutionary computing.
---|---
|  Haiyang Xiong is currently pursuing the masters degree with the college of
Information engineering, Zhejiang University of Technology. His research
interests include graph data mining and applications, and artificial
intelligence.
---|---
|  Haibin Zheng is a PhD student at the college of Information Engineering,
Zhejiang University of Technology. He received his bachelor degree from
Zhejiang University of Technology in 2017. His research interests include deep
learning, artificial intelligence, and adversarial attack and defense.
---|---
|  Jian Zhang received BS degree in automation from Zhejiang University of
Technology, Hangzhou, China, in 2017. He is currently working toward the PhD
degree in the College of Information Engineering, Zhejiang University of
Technology, Hangzhou, China.
---|---
|  Guodong Jiang is currently pursuing the masters degree with the college of
Information engineering, Zhejiang University of Technology. His research
interests include graph data mining and applications, and artificial
intelligence.
---|---
|  Yi Liu received the Ph.D. degree in control theory and engineering from
Zhejiang University, Hangzhou, China, in 2009. He was an Associate Professor
with the Institute of Process Equipment and Control Engineering, Zhejiang
University of Technology from 2011 to 2020. He was a Postdoctoral Researcher
with the Department of Chemical Engineering, Chung-Yuan Christian University
from February 2012 to June 2013. Since December 2020, he has been a Full
Professor with Zhejiang University of Technology, Hangzhou, China. He has
published over 50 research papers at IEEE Transactions and international
journals. His research interests include data intelligence with applications
to modeling, control, and optimization of industrial processes.
---|---


# TCP Congestion Control Identification

Mohammed Ahmed

###### Abstract

Transmission Control Protocol (TCP) carries most of the traffic on the
Internet these days. There are several implementations of TCP, and the most
important difference among them is their mechanism for controlling congestion.
One of the methods for determining type of a TCP is active probing. Active
probing considers a TCP implementation as a black box, sends different streams
of data to the appropriate host. According to the response received from the
host, it figures out the type of TCP version implemented. TCP Behavior
Inference Tool (TBIT) is an implemented tool that uses active probing to check
the running TCP on web servers. It can check several aspects of the running
TCP including initial value of congestion window, congestion control
algorithm, conformant congestion control, response to selective
acknowledgment, response to Explicit Congestion Notification (ECN) and time
wait duration. In this paper we focus on congestion control algorithm aspect
of it, explain the mechanism used by TBIT and present the results.

##  1 INTRODUCTION

Transmission Control Protocol (TCP) is widely used on the Internet, and most
of the traffics are carried by this protocol. So performance of the Internet
depends significantly on TCP’s performance. One of the most important aspects
of controlling traffic is dealing with congestions. Since there are several
types of TCP, each of them has implemented their own congestion control
mechanism that is the main difference among them.

For doing some kinds of Internet researches, sometimes we need to know what
type of TCP is running on a special host. Since we neither have access to the
source code of it nor the permission to log into that host and check, we
should find a way to check the TCP type remotely. In this case active probing
will be useful [1, 10]. Active probing considers the remote host as a black
box. It sends different streams of data to the remote host and the remote host
responds to the stream. According to the response, we can infer what type of
congestion control is used and consecutively what type of TCP is running.

Actually it is not possible to check arbitrary types of remote hosts. Because
some of them may not respond to our request for several reasons like lack of
permission, blocking the streams by the firewall etc. So we have to restrict
our hosts to only web servers. It is obvious that they will always respond to
our request for getting a page. In this paper we use TCP Behavior Inference
Tool (TBIT) that tests TCP Tahoe [9], Reno [5] and NewReno [7]. So we can only
check the congestion control mechanisms on web servers supporting one of these
TCP types [2].

The remainder of this paper is organized as follows. Section two explains
different congestion control mechanisms that are used nowadays. Section three
describes a mechanism that will be used in order to distinguish the congestion
control type that is running on a web server. Section four uses that mechanism
in practice and shows the results of the test. Section five concludes
everything in this paper and raises some future works.

##  2 DIFFERENT CONGESTION CONTROL MECHANISMS

There are different mechanisms for controlling congestion implemented.
Congestion control consists of four parts: slow start, congestion avoidance,
fast retransmit and fast recovery. The slow start and congestion avoidance
algorithms must be used by TCP senders to control the amount of outstanding
data being injected into the network. For this reason, the sender starts with
a low rate of sending data segments, and make the data amount twice after
receiving acknowledgment (ACK) for each of them. After crossing a threshold it
will increase the rate of sending data one by one.

A TCP receiver should send an immediate duplicate ACK when an out-of-order
segment arrives. The purpose of this ACK is to inform the sender that a
segment was received out-of-order and which sequence number is expected. Then
the sender enters fast retransmission and fast recovery stages and according
to the TCP type that is used, the sender will change the transmission rate in
order to control the traffic. The original definition of TCP congestion
control mechanisms could be found in RFC-2851. In the following parts of this
section we will briefly describe three different mechanisms implemented to
control the congestion within Fast Retransmit and Fast Recovery stages.

2.1 Tahoe
TCP Tahoe is one of the earliest implemented TCPs. It only contains Slow
Start, Congestion Avoidance and Fast Retransmit. After receiving a small
number of duplicate ACKs for the same TCP segment, the data sender infers that
a packet has been lost and retransmits the packet without waiting for a
transmission timer to expire, leading to higher channel utilization and
connection throughput [3]. Then it goes to Slow-Start stage, and go on working
from that point.

2.2 Reno
The Reno TCP implementation retained the enhancements incorporated into Tahoe,
but modified the Fast Retransmit operation to include Fast Recovery. The new
algorithm prevents the communication path (pipe) from going empty after Fast
Retransmit, thereby avoiding the need to Slow-Start to refill it after a
single packet loss. Fast Recovery operates by assuming each duplicate ACK
received represents a single packet having left the pipe. Thus, during Fast
Recovery the TCP sender is able to make intelligent estimates of the amount of
outstanding data. Fast Recovery is entered by a TCP sender after receiving an
initial threshold of duplicate ACKs. This threshold, usually known as
tcprexmtthresh, is generally set to three. Once the threshold of duplicate
ACKs is received, the sender retransmits one packet and reduces its congestion
window by one half. Instead of slow-starting, as is performed by a Tahoe TCP
sender, the Reno sender uses additional incoming duplicate ACKs to clock
subsequent outgoing packets [3].

2.3 NewReno
NewReno TCP includes a simple change to TCP Reno and improves its performance.
The change concerns the sender’ s behavior during Fast Recovery when a partial
ACK is received that acknowledges some but not all of the packets that were
outstanding at the start of that Fast Recovery period. In Reno, partial ACKs
take TCP out of Fast Recovery by “deflating” the usable window back to the
size of the congestion window. In NewReno, partial ACKs do not take TCP out of
Fast Recovery. Instead, partial ACKs received during Fast Recovery are treated
as an indication that the packet immediately following the acknowledged packet
in the sequence space has been lost, and should be retransmitted. Thus, when
multiple packets are lost from a single window of data, NewReno can recover
without a retransmission timeout, retransmitting one lost packet per round-
trip time until all of the lost packets from that window have been
retransmitted. New-Reno remains in Fast Recovery until all of the data
outstanding when Fast Recovery was initiated has been acknowledged [3].

##  3 AN ARCHITECTURE FOR IDENTIFYING CONGESTION CONTROL

Explaining briefly the architecture, a connection is established between two
hosts and they start sending and receiving data segments like a regular TCP
connection. Then some packets are dropped intentionally to check the behavior
of remote host. Within the following parts of this section we explain these
steps more comprehensively. First of all we need a connection between our
machine and the remote host. This connection will not be a regular connection,
because we don’t want the kernel to manipulate our streams. In the other
words, we need an interface to connect directly to the remote host. We create
our own TCP packets, and acknowledge only the desired ones. BSD Packet Filter
(BPF) is kernel agent that provides a user-level packet capture. It captures
specific packets and discards others as soon as possible. BPF contains two
components: the network tap and packet filter. Network tap collects copies of
packets from the network device drivers and delivers them to the application.
The filter decides if a packet should be accepted and, if so, how much of it
to copy to the listening port [4]. BPF is good choice to be used as an
interface to the remote host. So we use raw sockets and fabricates TCP
packets. Then the packets are sent to the network card to be sent over the
network. In the opposite way, when a packet is received from the remote host,
firewall will block it so it won’t be received by the kernel. BPF makes a copy
of it and delivers this packet to our software that is working in the user-
level space. Then we can easily decide when to create an ACK and when to drop
a packet. Let’s take a look at an algorithm that can identify the congestion
control mechanism, considering our machine is A and the remote host is B.

  * •

Open a raw IP socket

  * •

Open a BPF device and set the filter to capture all packets going to and
coming from host B.

  * •

Set up a host firewall on A to prevent any packets coming from host B from
reaching the kernel of host A.

  * •

Create and send a TCP SYN packet with the destination address of host B and a
destination port of 80. The Maximum Segment Size (MSS) is set to be a small
number. This will make the host send several packets for a regular request.

  * •

Request the base web page

  * •

The remote server starts sending the base page with small packets.

  * •

Create ACKs according to TCP protocol

  * •

Drop some packets

  * •

Check what the response will be from the remote host

  * •

Close the connection after a short time

Using this algorithm, our software will receive different responses from
different TCPs implemented. Now the software should analyze to understand the
type of TCP that creates such responses.

##  4 PRACTICAL EXAMPLE AND RESULTS

Now according to the algorithm described in previous section we would like to
create a practical example and see the results of that. So we will follow the
same algorithm with some specific features as follows.

  * •

Establish a connection between A and B according to what was explained in the
algorithm.

  * •

Send a TCP SYN packet with the destination address of host B and a destination
port of 80. The Maximum Segment Size (MSS) is set to 100 bytes.

  * •

Request the base web page

  * •

The remote server starts sending the base page with 100-byte packets.

  * •

Create ACKs according to TCP protocol up to packet 13.

  * •

Drop packet 13.

  * •

Receive and acknowledge packets 14 and 15, but the acknowledge will be three
times for packet 13 that will make sender go to Fast Retransmission state.

  * •

Drop the packet 16.

  * •

Receive and acknowledge other packets up to 25

  * •

Close the connection after acknowledging packet 25.

Now according to responses received from the remote host, we can infer what
type of TCP congestion control is running on that machine. As we explained in
2.3 NewReno is characterized by Fast Retransmission for packet 13, no
additional Fast Retransmits or Transmit Timeouts, and no unnecessary
retransmission of packet 17, as in figure 1. Like what was stated in 2.2 Reno
TCP is characterized by Fast Retransmit for packet 13, a Transmit Timeout for
packet 16 and no unnecessary retransmission for packet 17, as in figure 2. As
in 2.1 Tahoe TCP is characterized by no Retransmit Timeout before the
retransmission of packet 13, but an unnecessary retransmission of packet 17,
as shown in figure 3 [2]. Since TCP is a user-configurable transport protocol
[8], responses received from different hosts are not limited only to these
three types. So we would face some other types of congestion controls that are
not widely used.

As an explanation square signs in these figures stand for packets and plus
signs are acknowledges for specific packets. According to [2], it has been
tested on 3728 web servers and the summary of them is shown in Table 1. Even
though the number of tests has been more than 3728, only this number of
servers replied TBIT request. There are several reasons for this problem as
follows.

  * •

TBIT may detect packet reordering.

  * •

An Internal buffer overflowed.

  * •

Based on the packets received, the software couldn’t classify it in one of the
TCP classes.

As an explanation to Table 1, we should mention that TCP without
retransmission was expected to be obsolete, but we can see lots of them
running on some web servers. And also a number of web servers have implemented
a variant of Reno TCP that transmits additional packets between retransmission
of packets 13 and 16 that [2] called them Reno-Plus.

##  5 CONCLUSION AND FUTURE WORKS

In this paper we explained one mechanism for testing the congestion control
running on a web server. This mechanism has been implemented and tested in
TBIT [2]. The source code and documentations are available on its web site
[6]. This tool has been developed on FreeBSD platform, and can partially work
on Unix. Using this software we can test several TCP implementations without
having access to their source codes. This might also be used for debugging TCP
implementations. One other usage of this software may be making some
statistics about the traffic on Internet that will be useful in developing
softwares trying to shape or monitoring the traffic. As a future work, someone
can implement it on other transport protocols supporting congestion control
like DCCP and SCTP. Since they are using congestion control algorithms
somewhat like TCP, this mechanism can be helpful for them as much as it is for
TCP. All the mechanisms will be the same except the part for creating TCP
packets. In each of these two cases the software should create its own packet
type i.e. DCCP or SCTP packet. Since they don’t carry the traffic more than
TCP, it may not be used very often on the Internet.

## References

  * [1] D. E. Comer and J. C. Lin, “Probing TCP Implementations”, In USENIX Summer 1994 Conference
  * [2] J. Padhye and S. Floyd, “On Inferring TCP Behavior”, In Proceedings of ACM SIGCOMM 2001
  * [3] K. Fall and S. Floyd, “Simulation-based Comparisons of Tahoe, Reno and SACK TCP”, Computer Communication Review, 26(3), July 1996
  * [4] S. McCanne and V. Jacobson, “The BSD Packet Filter: A New Architecture for User-Level Packet capture”, In proceedings of the winter USENIX technical conference, January 1993
  * [5] M. Allman, V. Paxon and W. Stevens, “TCP Congestion Control”, April 1999 , RFC 2581
  * [6] TBIT web site: http://www.icir.org/tbit
  * [7] S. Floyd and T. Henderson, “The NewReno Modification to TCP Fast Recovery Algorithm”, April 1999, RFC 2582
  * [8] J. Postel, “Transmission Control Protocol”, September 1981, RFC 793
  * [9] V. Jacobson “Congestion Avoidance and Control”, Computer Communication Review, 18(4), August 1988
  * [10] Feyzabadi, S., and J. Schonwalder. ”Identifying TCP congestion control algorithms using active probing.” Passive and Active Measurement Conference (PAM), Poster. 2010.