# Neighborhood-based Hard Negative Mining for Sequential Recommendation

Lu Fan<EMAIL_ADDRESS>The Hong Kong Polytechnic UniversityHong Kong
S.A.R.China ,  Jiashu Pu<EMAIL_ADDRESS>Fuxi AI Lab, NetEase
Inc.Hang ZhouChina ,  Rongsheng Zhang<EMAIL_ADDRESS>Fuxi AI
Lab, NetEase Inc.Hang ZhouChina and  Xiao-Ming Wu<EMAIL_ADDRESS>The Hong Kong Polytechnic UniversityHong Kong S.A.R.China

(2023)

###### Abstract.

Negative sampling plays a crucial role in training successful sequential
recommendation models. Instead of merely employing random negative sample
selection, numerous strategies have been proposed to mine informative negative
samples to enhance training and performance. However, few of these approaches
utilize structural information. In this work, we observe that as training
progresses, the distributions of node-pair similarities in different groups
with varying degrees of neighborhood overlap change significantly, suggesting
that item pairs in distinct groups may possess different negative
relationships. Motivated by this observation, we propose a _g_ raph-based _n_
egative sampling approach based on _n_ eighborhood _o_ verlap (GNNO) to
exploit structural information hidden in user behaviors for negative mining.
GNNO first constructs a global weighted item transition graph using training
sequences. Subsequently, it mines hard negative samples based on the degree of
overlap with the target item on the graph. Furthermore, GNNO employs
curriculum learning to control the hardness of negative samples, progressing
from easy to difficult. Extensive experiments on three Amazon benchmarks
demonstrate GNNO’s effectiveness in consistently enhancing the performance of
various state-of-the-art models and surpassing existing negative sampling
strategies. The code will be released at https://github.com/floatSDSDS/GNNO.

sequential recommendation, hard negative mining, graph mining

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
46th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 23–27, 2023; Taipei, Taiwan††booktitle:
Proceedings of the 46th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’23), July 23–27, 2023, Taipei,
Taiwan††price: 15.00††doi: 10.1145/3539618.3591995††isbn:
978-1-4503-9408-6/23/07††ccs: Information systems Recommender systems

Figure 1. Visualization of the distributions of node-pair similarities in
different groups on the Beauty dataset at the training epoch 0 and 20,
respectively. Nodes are divided into four groups w.r.t. their Jaccard
similarity $J(i,j)$ on a global weighted item transition graph. Node/item
pairs in group-zero have no common neighbors, those in group-low have
$J(i,j)\in(0,0.15]$, those in group-medium have $J(i,j)\in(0.15,0.3]$, and
those in group-high have $J(i,j)\in(0.3,1.0]$. Note that due to the
considerable differences in group size, we use different bin values for
different groups.

##  1\. Introduction

Sequential recommendation (SR) is a task that predicts the next item that a
user may be interested in given his or her past behavior sequence. Most SR
models use Noise Contrastive Estimation (NCE), which brings positive items
closer to the sequence and pushes negative ones away. Negative sampling
strategies play a crucial role in the development of successful SR models.
However, while the majority of SR models adopt uniform sampling strategies and
focus on designing sequence encoders or incorporating additional training
tasks, a few attempts have been made to focus on mining informative negative
samples for SR. These attempts can be broadly categorized into two groups: (1)
sampling-based methods (Cho et al., 2014; Gillick et al., 2019; Wu et al.,
2020; Karpukhin et al., 2020; Xiong et al., 2021) that aim to learn a proper
distribution for negative mining, and (2) generation-based methods (Wang et
al., 2017; Yu et al., 2017; Wang et al., 2018; Huang et al., 2021) that
develop generative models that synthesize negative samples for model training.
Despite the various types of negative mining methods, to our knowledge, there
is no effort that explicitly utilizes structural information concealed in user
behavior sequences to mine hard negatives via graph analysis for SR. In this
work, we develop a new negative sampling approach for SR by utilizing the
structural information of behavior sequences and creating a negative sampler
based on neighborhood analysis.

Our approach is motivated by a pilot experiment in Figure 1, which visualizes
the distributions of node-pair similarities in different groups at the
different epochs during training an SR model. The nodes on a global weighted
item transition graph (WITG) are divided into four groups w.r.t. the Jaccard
similarity defined in Eq. 2 that measures the degree of neighborhood overlap
between two nodes on the graph. Higher $J(i,j)$ indicates the neighborhoods of
$i$ and $j$ have a larger overlap. Figure 1 shows that for each group, the
distribution of embedding similarity shifts as training progresses. The
distributions of group-zero and group-low exhibit similar patterns that they
only change slightly. The two groups represent easy negatives, which, although
less informative, are essential for training the SR model. Item pairs within
group-medium display some overlap in their respective neighborhoods. As
training progresses, a significant shift in the distribution is observed. In
this study, we treat item pairs in group-medium as hard negative pairs,
positing that they contribute more information during the training process.
Since item pairs in group-high have strong connections and are likely to be
false negatives, we propose to exclude them from the item pool for negative
sampling.

Specifically, we propose a _g_ raph-based _n_ egative sampling approach based
on _n_ eighborhood _o_ verlap (GNNO). GNNO first constructs a WITG as
described in Sec 3.2. Utilizing the built WITG, it selects negative samples
for each target item by considering the extent of the neighborhood overlap
between the target item and any other item. Additionally, GNNO employs
curriculum learning (CL) to adjust the maximum hardness of negative samples,
ranging from easy to hard. Among existing graph-based negative sampling
strategies, GNNO is most similar to RecNS (Yang et al., 2022) in that we also
perform region division and propose sampling variations that account for
unique characteristics in each region. The key differences between GNNO and
RecNS are three-fold: (1) GNNO is designed for sequential recommendation and
explicitly utilizes structural information in user behavior sequences; (2)
Rather than dividing the sampling region by $k$-hop distance, GNNO creates a
negative sampler that samples from a distribution based on the relative
Jaccard index; (3) GNNO suggests negative samples from distant regions are
indispensable for training an SR model. In summary, the contributions of this
paper include:

  * •

To the best of our knowledge, this is the first work to investigate the
structural properties of negative samples in SR. We observed that item pairs
with varying levels of neighborhood overlap on WITG may exhibit distinct
characteristics, signifying a valuable signal for hard negative discrimination
in sequential recommendation.

  * •

We introduce GNNO, which adaptively samples negatives for each item based on
the relative Jaccard similarity on WITG. We also employ CL to control the
maximum hardness of negative samples during training.

  * •

Comprehensive comparative experiments on three Amazon benchmarks demonstrate
the effectiveness of our proposed method.

Figure 2. Illustration of our proposed GNNO framework. The false negatives for
a given target node are annotated as black blocks. For example, for the target
node $a$, nodes $b$ and $c$ are false negatives and hence excluded from the
sampling distribution for $a$.

##  2\. Related Works

##### Negative Sampling Methods for Sequential Recommendation.

As mentioned in Sec. 1, attempts for informative negative sampling for SR are
broadly categorized into two groups: sampling-based methods (Cho et al., 2014;
Gillick et al., 2019; Wu et al., 2020; Karpukhin et al., 2020; Xiong et al.,
2021; Wang et al., 2021) and generation-based methods (Wang et al., 2017; Yu
et al., 2017; Wang et al., 2018; Huang et al., 2021). ANCE (Xiong et al.,
2021) proposes to sample hard negatives globally by using an asynchronously
updated ANN index. CBNS (Wang et al., 2021) proposes to sample negatives
cross-batch other than simply in-batch sampling. SRNS (Ding et al., 2020)
leverages the variance-based characteristics of false negatives and hard
negatives to improve the sampling strategy.

##### Graph-based Negative Sampling Methods.

Existing graph-based methods for negative sampling mostly concentrate on
collaborative filtering (CF)-based recommendations (Huang et al., 2021; Yang
et al., 2022), graph contrastive learning (Yang et al., 2020; Zhu et al.,
2022, 2022; Xia et al., 2022). MixGCF (Huang et al., 2021) efficiently injects
information of positive samples into negative samples via a mix-up mechanism.
HORACE (Zhu et al., 2022) and STENCIL (Zhu et al., 2022) study heterogeneous
graph contrastive learning and utilize global topology features including
PageRank (Langville and Meyer, 2006) and Laplacian vector. These features are
usually static and would suffer from potential risks in static hard negative
sampling. ProGCL (Xia et al., 2022) focuses on the problem of false negatives
discrimination in graph contrastive learning. It proposes to solve the problem
by fitting a two-component (true-false) beta mixture model to distinguish true
negatives. RecNS (Yang et al., 2022) proposes the three-region principle to
guide negative sampling for graph-based recommendation. It suggests to sample
more negatives at an intermediate region while sampling less in adjacent and
distant regions. In this work, we propose to construct a global weighted item
transition graph to model sequential structural information for SR. To prevent
the potential risks of static hard sampling, we propose to employ curriculum
learning to adjust the maximum hardness of negative samples. Additionally, to
address the false negative challenge (Xia et al., 2022) which is particularly
severe in graph-based methods, we suggest to avoid sampling negatives from the
“adjacent region” (w.r.t. the target item).

##  3\. Method

In this section, we start with the problem statement of sequential
recommendation. Subsequently, we present our proposed approach. As illustrated
in Figure 2, GNNO comprises three modules: (1) WITG construction; (2)
overlapping-based negative sampling distribution generator; and (3) curriculum
scheduler for negative sampling.

###  3.1. Sequential Recommendation

Formally, let $\mathcal{U}$ and $\mathcal{I}$ denote the user and item sets
from the interaction sequences, respectively. For each user $u\in\mathcal{U}$,
we use a chronologically ordered list $\mathbf{s}=[i_{1},i_{2},...,i_{N}]$ to
denote his or her behavior sequence, where $i_{t}$ is the $t^{th}$ interaction
item of $u$ and $N$ is the length of the sequence. The task of SR is to
predict the subsequent user-item interactions with the given sequence
$\mathbf{s}$.

Training an SR model requires choosing an objective function $L$ and a
negative sampling distribution $p_{n}$. The commonly adopted Bayesian
Personalized Ranking (BPR) loss (Rendle et al., 2009) w.r.t. all training
sequences and time steps is defined as follows:

(1)
$L_{BPR}=\sum_{(\textbf{s}_{t},i_{t})}{-\log\sigma(\hat{y}(\textbf{s}_{t},i_{t})-\hat{y}(\textbf{s}_{t},i_{t}^{-}))},$

where $\textbf{s}_{t}=[i_{1},i_{2},...,i_{t-1}]$ is the historical sub-
sequence of s at time step $t$, $i_{t}$ is the target item, $\sigma$ denotes
the sigmoid function, $\hat{y}(\mathbf{s},i)$ is a trainable network that
predicts a matching score between a sequence $\mathbf{s}$ and an item $i$.
$i_{t}^{-}\sim p_{n}$ is a negative item sampled from a distribution $p_{n}$.
Optimizing Eq 1 offers the model ability to score the target item $i_{t}$
higher than the negative item $i_{t}^{-}$ for a given $\mathbf{s}_{t}$.

###  3.2. Weighted Item Transition Graph (WITG)

In contrast to the commonly used user-item graph, to make use of global
information in behavior sequences, we propose to mine hard negatives on a WITG
$\mathcal{G}(\mathcal{I},\mathcal{E})$ (Zhang et al., 2022) where
$\mathcal{E}$ is the edge set. A WITG contains global item transition patterns
extracted from all user behavior sequences in the training set $\mathcal{D}$.
$\mathcal{G}$ is constructed by traversing every sequence in $\mathcal{D}$.
For a sequence $\mathbf{s}\in\mathcal{D}$, if there exists no edge between the
items $i_{m}$ and $i_{(m+k)}$ in $\mathcal{G}$, we connect them and set the
edge weight $w(i_{m},i_{(m+k)})=1/k$, where $k$ represents the importance of a
target item $i_{m}$ to its $k$-hop neighbor $i_{(m+k)}$ in $\mathbf{s}$.
Otherwise, if there is already an edge between them, we update the edge weight
as $w(i_{m},i_{(m+k)})\leftarrow w(i_{m},i_{(m+k)})+1/k$.

###  3.3. Neighborhood-based Negative Sampler

Given a target item, we can divide the other items into groups w.r.t. their
neighborhood overlap with the target item. As analyzed in Sec. 1, these groups
demonstrate distinct characteristics during the training of a SR model, thus
it can be advantageous to differentiate and treat them differently. Here, we
propose to use the Jaccard similarity to measure the degree of neighborhood
overlap between the target item and the others. Let $\mathcal{N}(i)$ denote
the neighbor set of an item $i$ on $\mathcal{G}$. The Jaccard similarity
between any two items $i$ and $j$ can be defined as:

(2)
$J(i,j)=\frac{\mathcal{N}(i)\cap\mathcal{N}(j)}{\mathcal{N}(i)\cup\mathcal{N}(j)}.$

If $i$ and $j$ have many common neighbors, they will have a large similarity.
Meanwhile, the denominator acts as a normalizer, and the similarity will be
small if the degree of either $i$ or $j$ is large.

As explained in Figure 1, group-medium is likely to be quality hard negatives,
hence we want to give them higher sampling weight. Meanwhile, we want to keep
group-zero and group-medium for diversity, but we want to give them low
sampling probability. Finally, we want to exclude group-high as they are
likely to be false negatives. Therefore, we propose to sample the negatives
for a target item $i$ from the following distribution:

(3)
$p_{n}(i^{-}|i)=\frac{e^{J(i,i^{-})}}{\sum_{j\in\mathcal{N}^{\prime}(i)}e^{J(i,j)}},$

where $\mathcal{N}^{\prime}(i)=\mathcal{I}\backslash\\{j|J(i,j)>\lambda\\}$ is
the item set without group-high, and $\lambda$ is the threshold for group-high
at the current training step.

###  3.4. Curriculum Scheduler for Negative Sampling

Concentrating too much on hard negatives in the early training stage may bring
negative effects to the model (Castells et al., 2020). We therefore employ
curriculum learning (CL) techniques to schedule the hardness of the negatives.
The main idea of CL is to order negative samples during training based on
their difficulty (Wang et al., 2022a). Let $Q$ be the maximum training step,
then for each training step $q\in[1,...,Q]$, we update $\lambda$ to form
$\mathcal{N}^{\prime}(i)$ in Eq. 3. The maximum Jaccard score is updated from
an initial hardness $b$ with a linear pacing function $f(q)$:

(4) $f(q)=c*q+b,$

where $q$ is the current time step and $c$ is the pace coefficient. For
simplicity, we set $b=0$ in our experiments. Moreover, we set a maximum
hardness $\lambda_{max}$ to clip the growth of $\lambda$. Finally, $\lambda$
is updated as:

(5) $\lambda(q)=min(f(q),\lambda_{max}).$

##  4\. Experiments

###  4.1. Experimental Setup

####  4.1.1. Datasets

Our experiments are conducted on three subsets of the well-known Amazon
dataset111http://jmcauley.ucsd.edu/data/amazon (Ni et al., 2019), which
includes rich user-item review interactions. Specifically, we choose the sub
datasets Beauty, Phone, and Toy for our empirical study. In our experiments,
we use the 5-core data. Items and users with no positive records are filtered
out for each subset. The statistics of the filtered datasets are shown in
Table 1.

####  4.1.2. Baselines

Table 1. Dataset statistics.

| #user | #item | #entry | #edge | sparseness
---|---|---|---|---|---
Beauty | 22,363 | 12,101 | 198,502 | 530,266 | 20.01%
Toys | 19,413 | 11,925 | 148,455 | 486,740 | 16.32%
Phone | 22,364 | 12,102 | 176,139 | 530,266 | 24.55%

Table 2. Hyper-parameter settings. #$neg_{hard}$ and #$neg_{rand}$ indicate
the number of hard negatives and random negatives, respectively.

|  #$neg_{hard}$ |  #$neg_{rand}$ |  $c$ (Eq.4) |  $\lambda_{max}$ (Eq.5)
---|---|---|---|---
Beauty | 9 | 16 | 0.04 | 0.5
Toys | 2 | 10 | 0.05 | 0.2
Phones | 4 | 10 | 0.01 | 0.9

We compare our method with both state-of-the-art sequential recommendation
methods and negative sampling strategies. As shown in Table 4, we compare our
method with the following baselines for sequential recommendation: BPRMF
(Rendle et al., 2009), Caser (Tang and Wang, 2018), GRU4Rec (Hidasi et al.,
2016), BERT4Rec (Sun et al., 2019), SASRec (Kang and McAuley, 2018), TimiRec
(Wang et al., 2022b), and ContraRec (Wang et al., 2023). Meanwhile, as shown
in Table 3, we also compare our method with the following negative sampling
approaches: DNS (Zhang et al., 2013) that adaptively samples the negative item
scored highest by the recommender, MCNS (Yang et al., 2020)that samples
negatives with the distribution sub-linearly related to the positive
distribution and accelerates the sampling process by Metropolis-Hastings, and
MixGCF (Huang et al., 2021) that injects positive samples into negatives via
hop mixing to synthesize hard negatives. Note that MCNS and MixGCF are graph-
based but DNS is not.

####  4.1.3. Implementation details

All recommendation baselines are implemented with
ReChorus222https://github.com/THUwangcy/ReChorus, a framework for top-$k$
recommendation. GNNO and other negative sampling strategies are implemented on
the state-of-the-art SR method ContraRec. We use the default settings of
ContraRec. Specifically, we use Adam as the optimizer and BERT4Rec as the
sequence encoder. The batch size is set to $4096$, and the dimension of hidden
units is set to $64$. The hyper-parameters of GNNO, as shown in Table 2, are
selected based on the performances on the validation set using grid search.

####  4.1.4. Evalutaion Protocals

Following (Wang et al., 2023), we adopt the commonly used leave-one-out
strategy to evaluate model performance. We employ two evaluation metrics: hit
rate (HR@K) and normalized discounted cumulative gain (NDCG@K). For each
sequence, the target products are mixed up with candidates randomly sampled
from the entire product set, forming a candidate set of size $1000$.

###  4.2. Results and Analysis

####  4.2.1. Comparisons with Negative Sampling Baselines

Table 3. Comparison of our proposed method with hard negative mining baselines
on three Amazon review sub datasets. The best results are highlighted in bold.

Dataset | Method | HR@5 | NDCG@5 | HR@20 | NDCG@20
---|---|---|---|---|---
Beauty | DNS | 0.3858 | 0.2984 | 0.5890 | 0.3561
MCNS | 0.4101 | 0.3141 | 0.6135 | 0.3721
MixGCF | 0.4123 | 0.3168 | 0.6140 | 0.3743
GNNO | 0.4149 | 0.3215 | 0.6174 | 0.3792
Phone | DNS | 0.4307 | 0.3300 | 0.6563 | 0.3943
MCNS | 0.4794 | 0.3646 | 0.7179 | 0.4334
MixGCF | 0.4810 | 0.3655 | 0.7197 | 0.4342
GNNO | 0.4897 | 0.3754 | 0.7249 | 0.4430
Toy | DNS | 0.3470 | 0.2666 | 0.5598 | 0.3266
MCNS | 0.4035 | 0.3084 | 0.6238 | 0.3711
MixGCF | 0.4049 | 0.3097 | 0.6252 | 0.3723
GNNO | 0.4074 | 0.3148 | 0.6245 | 0.3762

Table 3 summarizes the recommendation performance of GNNO in comparison to
existing negative sampling approaches on three Amazon benchmarks. GNNO
outperforms the baselines in almost all cases, demonstrating its efficacy. It
can be seen that all graph-based methods perform better than DNS, which
highlights the advantages of incorporating structural information for negative
sampling.

####  4.2.2. Comparisons with Baselines for Sequential Recommendation

Table 4. Comparison of our proposed method with baselines for sequential
recommendation on three Amazon review sub-datasets. The best results are
highlighted in bold.

Dataset | Method | HR@5 | NDCG@5 | HR@20 | NDCG@20
---|---|---|---|---|---
Beauty | BPRMF | 0.3588 | 0.2593 | 0.5716 | 0.3202
Caser | 0.3198 | 0.2238 | 0.5772 | 0.2970
GRU4Rec | 0.3254 | 0.2318 | 0.5762 | 0.3030
BERT4Rec | 0.3590 | 0.2658 | 0.5734 | 0.3266
SASRec | 0.3653 | 0.2780 | 0.5744 | 0.3372
TimRec | 0.3781 | 0.2812 | 0.5958 | 0.3433
ContraRec | 0.4112 | 0.3158 | 0.6111 | 0.3727
GNNO | 0.4149 | 0.3215 | 0.6174 | 0.3792
Phone | BPRMF | 0.3690 | 0.2709 | 0.5945 | 0.3352
Caser | 0.3873 | 0.2745 | 0.6727 | 0.3560
GRU4Rec | 0.4122 | 0.2973 | 0.6935 | 0.3777
BERT4Rec | 0.4209 | 0.3145 | 0.6664 | 0.3849
SASRec | 0.4432 | 0.3349 | 0.6809 | 0.4032
TimRec | 0.4338 | 0.3241 | 0.6712 | 0.3925
ContraRec | 0.4831 | 0.3673 | 0.7210 | 0.4358
GNNO | 0.4897 | 0.3754 | 0.7249 | 0.4430
Toys | BPRMF | 0.3107 | 0.2255 | 0.5255 | 0.2864
Caser | 0.2921 | 0.2000 | 0.5584 | 0.2757
GRU4Rec | 0.3113 | 0.2168 | 0.5802 | 0.2934
BERT4Rec | 0.3457 | 0.2561 | 0.5582 | 0.3164
SASRec | 0.3594 | 0.2731 | 0.5694 | 0.3328
TimRec | 0.3535 | 0.2628 | 0.5849 | 0.3287
ContraRec | 0.4013 | 0.3065 | 0.6177 | 0.3676
GNNO | 0.4074 | 0.3148 | 0.6245 | 0.3762

Table 4 shows the recommendation performance of GNNO against state-of-the-art
methods for SR on three Amazon benchmarks. GNNO improves over ContraRec on
every dataset. It demonstrates the effectiveness of the proposed negative
sampling strategy, showing that pushing away negatives with some neighborhood
overlap is beneficial for SR. In addition, both ContraRec and GNNO outperform
other baselines consistently, where the performance gain is probably brought
by the context-context contrastive learning task.

##  5\. Conclusion

In this work, we observed that as training progresses, the embedding
similarity between item pairs in different groups with varying degrees of
neighborhood overlap on a weighted item transition graph (WITG) changes
significantly. Based on this observation, we propose GNNO, which samples
negatives with respect to the Jaccard index on a global WITG. Additionally,
GNNO employs curriculum learning to manage the hardness of negative samples at
each training step. Extensive experiments on three Amazon benchmarks
demonstrate the effectiveness of our proposed method. In future work, we plan
to study hard negative mining over dynamic graphs for sequential
recommendation.

##  6\. Acknowledgement

We would like to thank the anonymous reviewers for their helpful comments.
This research was partially supported by the General Research Fund No.15222220
funded by the UGC of Hong Kong.

## References

  * (1)
  * Castells et al. (2020) Thibault Castells, Philippe Weinzaepfel, and Jérôme Revaud. 2020\.  SuperLoss: A Generic Loss for Robust Curriculum Learning. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014\.  Learning Phrase Rep resentations using RNN Encoder-Decoder for Statistical Machine Translation. In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL_. ACL, 1724–1734.  https://doi.org/10.3115/v1/d14-1179
  * Ding et al. (2020) Jingtao Ding, Yuhan Quan, Quanming Yao, Yong Li, and Depeng Jin. 2020.  Simplify and Robustify Negative Sampling for Implicit Collaborative Filtering. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Gillick et al. (2019) Dan Gillick, Sayali Kulkarni, Larry Lansing, Alessandro Presta, Jason Baldridge, Eugene Ie, and Diego Garcia-Olano. 2019.  Learning Dense Representations for Entity Retrieval. In _Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)_. 528–537.
  * Hidasi et al. (2016) Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk. 2016.  Session-based Recommendations with Recurrent Neural Networks. In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Huang et al. (2021) Tinglin Huang, Yuxiao Dong, Ming Ding, Zhen Yang, Wenzheng Feng, Xinyu Wang, and Jie Tang. 2021.  MixGCF: An Improved Training Method for Graph Neural Network-based Recommender Systems. In _KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021_. ACM, 665–674.
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian McAuley. 2018.  Self-attentive sequential recommendation. In _2018 IEEE international conference on data mining (ICDM)_. IEEE, 197–206.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick S. H. Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020\.  Dense Passage Retrieval for Open-Domain Question Answering. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_. Association for Computational Linguistics, 6769–6781.
  * Langville and Meyer (2006) Amy Nicole Langville and Carl Dean Meyer. 2006.  _Google’s PageRank and beyond - the science of search engine rankings_.  Princeton University Press.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian J. McAuley. 2019.  Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_. Association for Computational Linguistics, 188–197.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian Personalized Ranking from Implicit Feedback. In _UAI 2009, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009_. AUAI Press, 452–461.
  * Sun et al. (2019) Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. 2019.  BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019_. ACM, 1441–1450.
  * Tang and Wang (2018) Jiaxi Tang and Ke Wang. 2018.  Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018_. ACM, 565–573.
  * Wang et al. (2023) Chenyang Wang, Weizhi Ma, Chong Chen, Min Zhang, Yiqun Liu, and Shaoping Ma. 2023\.  Sequential Recommendation with Multiple Contrast Signals.  _ACM Trans. Inf. Syst._ 41, 1 (2023), 11:1–11:27.
  * Wang et al. (2022b) Chenyang Wang, Zhefan Wang, Yankai Liu, Yang Ge, Weizhi Ma, Min Zhang, Yiqun Liu, Junlan Feng, Chao Deng, and Shaoping Ma. 2022b.  Target Interest Distillation for Multi-Interest Recommendation. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management, Atlanta, GA, USA, October 17-21, 2022_. ACM, 2007–2016.
  * Wang et al. (2017) Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. 2017\.  IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models. In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, August 7-11, 2017_. ACM, 515–524.
  * Wang et al. (2021) Jinpeng Wang, Jieming Zhu, and Xiuqiang He. 2021.  Cross-Batch Negative Sampling for Training Two-Tower Recommenders. In _SIGIR ’21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual Event, Canada, July 11-15, 2021_. ACM, 1632–1636.
  * Wang et al. (2018) Qinyong Wang, Hongzhi Yin, Zhiting Hu, Defu Lian, Hao Wang, and Zi Huang. 2018\.  Neural Memory Streaming Recommender Networks with Adversarial Training. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_. ACM, 2467–2475.
  * Wang et al. (2022a) Xin Wang, Yudong Chen, and Wenwu Zhu. 2022a.  A Survey on Curriculum Learning.  _IEEE Trans. Pattern Anal. Mach. Intell._ 44, 9 (2022), 4555–4576.
  * Wu et al. (2020) Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020.  Scalable Zero-shot Entity Linking with Dense Entity Retrieval. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_. Association for Computational Linguistics, 6397–6407.
  * Xia et al. (2022) Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z. Li. 2022.  ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning. In _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ _(Proceedings of Machine Learning Research, Vol. 162)_. PMLR, 24332–24346.
  * Xiong et al. (2021) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021\.  Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Yang et al. (2020) Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. 2020\.  Understanding Negative Sampling in Graph Representation Learning. In _KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020_. ACM, 1666–1676.
  * Yang et al. (2022) Zhen Yang, Ming Ding, Xu Zou, Jie Tang, Bin Xu, Chang Zhou, and Hongxia Yang. 2022\.  Region or global a principle for negative sampling in graph-based recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ (2022).
  * Yu et al. (2017) Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu. 2017\.  SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient. In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA_. AAAI Press, 2852–2858.
  * Zhang et al. (2013) Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. 2013\.  Optimizing top-n collaborative filtering via dynamic negative item sampling. In _The 36th International ACM SIGIR conference on research and development in Information Retrieval, SIGIR ’13, Dublin, Ireland - July 28 - August 01, 2013_. ACM, 785–788.
  * Zhang et al. (2022) Yixin Zhang, Yong Liu, Yonghui Xu, Hao Xiong, Chenyi Lei, Wei He, Lizhen Cui, and Chunyan Miao. 2022\.  Enhancing Sequential Recommendation with Graph Contrastive Learning. In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022_. ijcai.org, 2398–2405.
  * Zhu et al. (2022) Yanqiao Zhu, Yichen Xu, Hejie Cui, Carl Yang, Qiang Liu, and Shu Wu. 2022\.  Structure-enhanced heterogeneous graph contrastive learning. In _Proceedings of the 2022 SIAM International Conference on Data Mining (SDM)_. SIAM, 82–90.


# foREST: A Tree-based Approach for Fuzzing RESTful APIs

Jiaxian Lin†, Tianyu Li†, Yang Chen†, Guangsheng Wei‡, Jiadong Lin‡, Sen
Zhang‡, Hui Xu† †School of Computer Science, Fudan UniversityChina ‡Huawei
Cloud BUChina

###### Abstract.

Representational state transfer (REST) is a widely employed architecture by
web applications and cloud. Users can invoke such services according to the
specification of their application interfaces, namely RESTful APIs. Existing
approaches for fuzzing RESTful APIs are generally based on classic API-
dependency graphs. However, such dependencies are inefficient for REST
services due to the explosion of dependencies among APIs. In this paper, we
propose a novel tree-based approach that can better capture the essential
dependencies and largely improve the efficiency of RESTful API fuzzing. In
particular, the hierarchical information of the endpoints across multiple APIs
enables us to construct an API tree, and the relationships of tree nodes can
indicate the priority of resource dependencies, e.g., it’s more likely that a
node depends on its parent node rather than its offspring or siblings. In the
evaluation part, we first confirm that such a tree-based approach is more
efficient than traditional graph-based approaches. We then apply our tool to
fuzz two real-world RESTful services and compare the performance with two
state-of-the-art tools, EvoMaster and RESTler. Our results show that foREST
can improve the code coverage in all experiments, ranging from 11.5% to 82.5%.
Besides, our tool finds 11 new bugs previously unknown.

††conference: under review; ; online

##  1\. Introduction

Nowadays, REST becomes a defacto architectural standard for web applications
and cloud (Gamez-Diaz et al., 2017). The architecture views each REST service
as a storage system that can process data operation requests from clients and
make responses. Similar to the classic CRUD (create, read, update, and delete)
operations on storage systems, REST also defines four corresponding methods,
GET, POST, PUT, and DELETE. The communication between REST clients and
services is based on HTTP requests and responses, which brings the
architecture excellent interoperability in nature. Due to such advantages,
REST has been widely employed by industries. For example, both Microsoft
Azure111https://docs.microsoft.com/en-us/rest/api/azure/ and Google
Cloud222https://cloud.google.com/apis adopt REST, and users can access their
provided services via RESTful APIs.

To assure the quality of REST software, testing is an essential approach.
While traditional unit test or integration test requires much human effort in
writing test cases, fuzzing is a favorable testing approach that can be fully
automated. Given the API specification of a target REST service as input, a
fuzzing engine can generate test cases automatically and exercise each test
case with the service. The main challenge of fuzzing lies in how to solve the
dependencies among RESTful APIs in order to generate valid and diversified
test cases. Existing work (e.g., RESTler (Atlidakis et al., 2019) and
RestTestGen(Viglianisi et al., 2020)) on this direction mainly employs a
straightforward API dependency graph. By traversing the graph via breadth-
first search (BFS) or topological sort, a fuzzing engine should be able to
generate valid test cases. However, the efficiency of such approaches is
limited due to the explosion of edges on the dependency graph. As a result,
there could be a huge number of possible paths for reaching an API.
Furthermore, since some dependencies are inaccurate (discussed in Section
3.1.1), it is hard for such a tool to arbitrarily choose only one valid path
and abandon the rest.

In this paper, we propose a novel tree-based approach for fuzzing RESTful
APIs. Our approach can capture the essential dependencies among APIs via a
tree structure and therefore improve the dependency complexity from quadratic
(traversing a graph) to linear (traversing a tree) with respect to the number
of APIs. Note that each RESTful API is uniquely defined with an endpoint and a
method (GET, POST, PUT, or DELETE). Rather than modeling the dependencies of
APIs based on their required parameters and response values, we extract API
hierarchies according to the endpoint of each API. Our idea is inspired by the
fact that the required parameters or resources for visiting a child node on an
endpoint tree have a high chance to be fulfilled once its parent node has been
visited. We can therefore pre-order traverse the tree to generate valid test
cases. Moreover, the relationships among tree nodes can indicate the priority
for acquiring the dependent resource. For example, it’s more likely that a
node depends on its parent node than its descendent or siblings, although
there could be dependencies among all of them according to the traditional
dependency graph. In this way, our approach can improve the possibility of
finding useful resources for generating valid requests and improve the
efficiency of fuzzing.

To elaborate, our approach parses RESTful API specifications in Swagger or
OpenAPI standard (Initiative et al., [n. d.]) and constructs endpoint trees
for these APIs. To this end, it splits each endpoint URL (uniform resource
locator) into several tokens by the slash symbol. Each token is a node on an
endpoint tree, and we connect these nodes with edges such that an endpoint URL
can be reconstructed as a path from the root to a descendent node. Meanwhile,
each node may have several attributes indicating the supported methods of the
endpoint, and a buffer to stores the resources of the node. When generating
test cases for each node, we employ a template-based method that specifies an
ad hoc order of HTTP request methods, e.g., GET, then several POST, followed
by PUT and DELETE. Since PUT and DELETE may invalidate the created resource,
we should execute POST more times than DELETE in order to leave valid
resources for the decedent nodes to use. Note that there could be multiple
trees for an application. Our approach should also work in this scenario by
visiting each tree iteratively. The complexity is still linear to the number
of APIs.

We have implemented a prototype for the tree-based approach, namely foREST.
Besides the basic tree-based model for guiding request sequence generation,
foREST has also realized the associated feature for resource management and
retrieval. We have conducted a set of comparison experiments to study the
efficiency of our approach. Our experimental result firstly verifies that such
a tree-based approach is more efficient than traditional graph-based
approaches in practice, including BFS and topological sort. Furthermore, we
compare foREST with two state-of-the-art tools for RESTful API fuzzing, i.e.,
RESTler (Atlidakis et al., 2019) and EvoMaster (Arcuri, 2019). We fuzz
WordPress and GitLab with these three tools, and each fuzzing experiment lasts
for six hours. Results show that foREST can achieve the best code coverage in
all experiments and has exceeded the second best one (EvoMaster) by 11.5% to
82.5% in different experiments. Besides, foREST has found 11 new bugs
previously unknown, while RESTler and EvoMaster have found none.

In short, this article contains several major research contributions as
follows.

  * •

It proposes a novel tree-based RESTful API fuzzing approach that is more
efficient than traditional graph-based approaches. To our best knowledge, it
is the first systematic work in this direction. Our approach subtly models the
relations of APIs with a tree structure which not only reduces the complexity
of API dependencies but also captures the priority of resource dependencies.

  * •

We have implemented a prototype tool, foREST, and released it as open source
on GitHub333The link will be released soon.. Our fuzzing experimental results
with real-world REST services show that foREST has achieved better performance
than state-of-the-art tools. We believe our approach and the tool would be
useful to advance the development of the community on the problem of RESTful
API fuzzing.

The rest of the article is organized as follows. Section 2 firstly introduces
the problem of RESTful API fuzzing and discusses the challenges of the
problem. Section 3 then presents a motivating example for employing a tree-
based approach and demonstrating our methodology. Section 4 evaluates the
performance of our approach. Section 5 discusses related work, and finally
Section 6 concludes the paper.

(a) Five sample APIs.

(b) Definition of the API GET /projects in OpenAPI 3.0.

Figure 1. Sample APIs of the GitLab project.

(a) Dependency graph of four APIs.

(b) Dependency graph when considering more APIs. We mainly provide several
local dependencies of a cropped graph for clarify.

Figure 2. Representing sample GitLab APIs with traditional API dependency
graphs. An arrow $A\xrightarrow[]{\text{resp/req}}B$ indicate B depends on A,
and the required parameter name in A’s response is resp, and in B’s request is
req. For instance, path/id means the required parameter is id, but it uses
another name path in the response.

##  2\. Problem and Challenges

###  2.1. Problem of RESTful API Fuzzing

RESTful API is a common way for clients to interact with services. The latest
standard for defining such APIs is OpenAPI 3.0 (Initiative et al., [n. d.]).
In general, an RESTful API specification should provide both the format of
messages for clients to launch valid requests and the guidance for
interpreting message responses. A request message is composed of the following
elements:

  * •

Endpoint. An endpoint is a path string, which indicates the specific URL of
the API. Besides the domain name or IP address within an URL, each path may
consist of several tokens or arguments separated by “/”. While a token is a
common substring, an argument is a substring started with a colon or wrapped
with a bracelet. For example, /token/:arg and /token/{arg} implies the same
path with one argument arg.

  * •

Method. RESTful API is based on HTTP, and it supports several HTTP methods,
including POST for creating data, GET for retrieving data, PUT for updating
data, PATCH (rarely used in practice) for a partial update, and DELETE for
removing data.

  * •

Parameter. Besides the arguments inline with the endpoint URL, an RESTful API
can also accept parameters from the HTTP content in the form of key-value
pairs. Depending on the design of the API, such parameters could either be
required or optional.

Each RESTful API is uniquely defined by its path and method. In general, a
path may supports multiple methods, and they are treated as different APIs.
For example, Figure 1(a) contains five different APIs of GitLab, which belong
to two paths, /projects and /projects/{id}. Figure 1(b) demonstrates the
detailed specification of one API, GET /projects. The API specification
includes both the request and response message format. For requests, user can
specify a string value for the optional parameter “order_by”. Otherwise, the
default value for “order_by” would be “created_at”. For responses, a response
code 200 indicates that the request is properly received by the server and the
response message can be decoded according to the specification of
#definitions/BasicProjectDetails.

The problem of RESTful API fuzzing lies in how to generate test cases given
the API specification of an RESTful service and practice them with the
service. Such fuzzing solutions are often evaluated against how many APIs a
fuzzer can activate or how many lines of code it can cover with a given time
or test case budget. In order to generate valid requests for a target API and
exercise more lines of code, the fuzzer should be able to supply valid
parameter values automatically by solving the dependencies of the API. Next,
we discuss several main challenges underlying the problem.

###  2.2. Challenges for Fuzzing RESTful APIs

Real-world RESTful services generally contain data dependencies among APIs.
For example, Figure 2(a) is a dependency graph with detailed relationships
among four APIs of Figure 1. To generate a valid test case for the API GET
/projects/:id, the test case should pass a legal parameter id, which can be
obtained from the response message of another API GET /projects or POST
/projects. Therefore, the main challenge of RESTful API fuzzing lies in how to
model and solve these data dependencies in order to generate valid test cases
for each API.

Note that the problem is different from existing fuzz target generation
problems for library APIs, such as (Babić et al., 2019; Jiang et al., 2021). A
library API generally takes one or several parameters and returns one value.
In order to generate a valid API call as the fuzz target, the API parameter
types should match the API signature. Most of these types are primitive ones
(such as int or char) or abstract data types that can be returned by other
APIs of the library. Therefore, there are also data dependencies among the
parameters and return values of different APIs. Below, we discuss three
typical differences between traditional fuzz target generation problems and
RESTful API fuzzing.

M to N: Compared to a library API that returns only one value (i.e.,
$f(x_{1},...,x_{m})\to y$), the response message of an RESTful API generally
contains multiple values (i.e., $f(x_{1},...,x_{m})\to(y_{1},...,y_{n})$).
Therefore, the dependencies should be more complicated, i.e., the parameter of
an RESTful API depends on one particular field of the response from another
API. Note that a library API may also return multiple values as a tuple, but
it generally also contains another straightforward constructor for the
required type.

Arbitrary matching: the dependencies of RESTful APIs are based on the names of
values instead of the function signatures (i.e., $t_{x_{1}},...,t_{x_{n}}\to
t_{y}$) for library APIs. Developers can arbitrarily define their names, and
there is no strict rules similar to type checking. As a result, developers may
choose different names among different APIs for the same resource, or using
the same name for different resources. Such issues are very popular in real-
world REST applications, leading to another challenge for fuzzing RESTful
APIs.

Resource dependency: RESTful applications are generally stateful, and the API
dependencies should also consider the state or resources maintained by the
application. Otherwise, the generated data dependencies by simply matching the
resource name could be fake. In particular, only POST or PUT creates new
resources. The response of GET or DELETE may also contain resources, but these
resources are not newly created.

Figure 3. Representing sample GitLab APIs as a tree. Each node may support
multiple HTTP methods, and the endpoint URL can be reconstructed as a path
from the root to each node.

##  3\. Tree-based Approach

Since there are resource dependencies among APIs, we adopt a tree-based
approach to model and solve such dependencies. This section first presents a
motivating example showing the advantage of our approach, followed by our
detailed methodology.

###  3.1. Motivating Example

####  3.1.1. Limitations of API Dependency Graph

We cannot adopt traditional signature-based API dependency because it is
inaccurate for capturing the resource dependencies among RESTful APIs. As a
result, fuzzing RESTful APIs via API dependency graph traversal would
encounter severe issues.

We demonstrate our point with Figure 2. Figure 2(a) constructs a sample API
dependency graph based on the request and response message format specified in
the API definition of the GitLab project. We have manually matched all
arbitrary names that denote the same resource. For example, path and id are
two identifiers used in the response and request for the same thing, and we
can denote the dependency edge as path/id. In order to traverse the graph, we
should follow an order that can solve such data dependencies, e.g., via BFS or
topological sort. Therefore, we should invoke GET /projects first because the
API has no dependencies. Then we can extract the values of name and path from
its response as the parameter values for composing requests for the rest three
APIs. The order apparently works but suffers several essential problems in
practice.

  * •

Dense graph: Since an RESTful API response generally contains multiple values,
the dependency graph could be highly dense, i.e., many edges among API nodes.
For example, all the responses of the four APIs in Figure 2(a) contain a path
field, and three APIs require the value as the parameter value of id. Besides,
many other GitLab APIs (such as those in Figure 2(b)) also require path/id.
Traversing a dense graph is very challenging due to the path explosion problem
and an efficient algorithm may neglect some important routes that should be
explored.

  * •

Fake producer: We should not treat all API dependencies equally because some
dependencies are fake. For example, if no project has been created yet, the
response of GET /projects could be null. In other words, GET /projects is not
the real producer of the resources name and path required by other APIs.

  * •

Weak dependency: There is another type of dependencies should be treated
differently. For example, POST /projects depends on GET /projects for the
parameters of name and path. However, such resources are conflicting because
these two parameters should be uniquely initiated by users. One cannot create
a project with an existing name or path. Imposing such a dependency is mainly
useful for reaching the code for duplication check.

Figure 4. Overall framework of foREST.

####  3.1.2. Hierarchy of RESTful APIs

We observe that the paths of well-designed RESTful APIs generally form a tree
structure (or forest) in nature. Figure 3 contains dozens of GitLab APIs,
which is a super set of the APIs in Figure 2. Each node on the graph indicates
one component of the endpoint URL separated by “/”. Most nodes have one or
several method attributes beneath them, denoting the request methods supported
by an endpoint. The URL of each API can be reconstructed as a path from the
root node (projects) to another node with method attributes. For example,
/projects, /projects/:id, and /projects/users are all valid URLs. Based on the
content of a node, we further divide them into two types: token node which
contains a fixed path string, and parameter node which has a parameter to be
specified.

Such API trees subtly capture the resource dependencies among APIs. In
particular, if an API needs several parameters, it is likely that these
parameter values can be produced by another endpoint along the same path but
has shorter URL. For instance, the API GET /projects/:id requires one
parameter id, which can be produced by POST /projects; DELETE
/projects/:id/repositories/branches/:branch requires two parameters id and
branch, which can be produced by POST /projects and POST
/projects/:id/repositories/branches correspondingly. Such dependencies are
based on the production and use (or consumption) of resources, which are
essential for RESTful API testing.

###  3.2. Methodology

Figure 4 demonstrates the overall framework of our approach. There are two
stages: a preparation stage and a fuzzing stage. In the preparation stage, we
organize all the APIs into trees. Besides, we need to annotate some arbitrary
resource names with unique identifiers. In the fuzzing stage, we generate test
cases by traversing the API trees, and then execute each of them with the
target REST service. Meanwhile, we analyze the response messages and extract
useful resources for reuse based on a resource pool. Next, we discuss the
detailed design of several key procedures.

####  3.2.1. API Tree Construction

This step parses the specification document of RESTful APIs and organize them
into trees. As discussed in Section 3.1.2, an API tree can be defined as
$T(V,E)$, where each node $v_{i}$ is a component of an URL (without the domain
name or IP address) separated by “/”, and an edge $e_{i,j}$ that connects
$v_{i}$ and $v_{j}$ exists if and only if $v_{i}/v_{j}$ appears in an URL.
Each node $v_{i}$ may have one or several method attributes, denoting the API
methods supported by the URL from the root node $v_{0}$ to $v_{i}$, i.e., the
path can be restored from the tree as $/v_{0}/.../v_{i}$.

####  3.2.2. Resource Annotation and Fuzzy Matching

We design a resource annotation table to deal with those arbitrary names of
resources. The index of the table are unified resource identities, and each
resource may have several arbitrary names in the specification. Our resource
annotation table is in nature an array of name sets, i.e.,

$\bigcup\limits_{i=1}^{n}\\{R_{i}|R_{i}=\\{name_{1},...,name_{m}\\}\\}$

.

Since filling in the table manually by developers would be labour intensive,
we employ another fuzzy matching strategy to automatically recognize some
potential name pairs commonly used in RESTful APIs. Our matching rule ignores
the capitalization of letters, spaces and underlines between letters, etc. In
this way, developers only need to annotate a limited number of names that are
very different. Besides, we also employ a scoring mechanism to automatically
filter falsely matched pairs, i.e., if the response code based on a fuzzy pair
is 4XX, we give the pair a low score and tend to abandon it in the next round.

####  3.2.3. Resource Pool

We employ a resource pool to buffer and reuse dependent resources. The
structure of our resource pool is consistent with the hierarchical
relationship of APIs. In other words, we create a sub pool for each token node
of the API tree. Since only particular resource combinations could satisfy the
business requirement of the service, we do not record each resource separately
but document them together as a tuple if they occur in the same successful
request or response. Note that it is unnecessary to create a sub pool for the
parameter node which may have different values, because such node generally
indicates a specific resource that has already been included in its parent
token node. For example, the token node /projects contains all project
resources, and /projects/id contains only one particular project indicated by
the project id.

Besides, the hierarchy of our resource pool can also indicate the priority of
dependency. When generating a request for an API, we first search resources
from the current node for the required parameters, and then its parent node,
followed by other ancestor nodes.

Data: $deptrees$ /*API hierarchical trees*/

Data: $annotable$ /*Resource annotation table*/

Data: $respool$ /*Resource pool, initiated as null*/

for  _$t\in apitrees$_ do

$nodeseq\leftarrow DFS(t)$ /*get a node sequence in DFS order*/

for  _$n\in nodeseq$_ do

$url\leftarrow GetEndpoint(n,t)$

$methods\leftarrow GetMethod(n,t)$ /*get the methods of an endpoint and save
them in a predefined order*/

for  _$m\in methods$_ do

$pars\leftarrow GetRequiredParam(url,m)$

$pairs\leftarrow null$ /*for rating purpose*/

for  _$p\in pars$_ do

$rid\leftarrow Search(p,annotable)$ /*search the unique id from the res.
annotation table*/

$rid\leftarrow FuzzyMatching(rid)$ /*return a res. id along the tree backward
or none.*/

$pairs.add(p,rid)$ $p.v=Retrieve(rid,respool)$ /*find a value from the
resource pool randomly */

end for

$resp=Execute(url,m,pars)$

if  _$resp.code==2XX||3XX$_ then

$res=Extract(resp.msg)$

$respool.add(res)$

$IncreaseMatchingScore(pairs)$

end if

if  _$resp.code==4XX$_ then

$DecreaseMatchingScore(pairs)$

end if

if  _$resp.code==5XX$_ then

$ReportBug()$

end if

end for

end for

end for

Algorithm 1 Basic test case generation algorithm for required parameters only.

(a) A toy API tree example.

(b) Sequences of test cases generated.

Figure 5. Demonstrating the test cases generated by our approach considering
both required parameters and optional parameters with a toy API tree.

####  3.2.4. Test Case Generation

The tree structure provides us with an essential reference for generating
valid test cases. Our basic idea is that we can traverse each tree via either
a depth-first or bread-first order and generate valid test cases for each
node. Since a node may support multiple HTTP methods, we adopt template-based
order for exercising the methods of each node, where a template is a heuristic
order of HTTP methods, e.g., GET, and then $k$ times of POST, and then PUT,
followed by DELETE, where $k$ is a small random integer generated during
runtime for the fuzzing purpose. The order is based on the fact that only POST
can create resources, which is the prerequisite for executing GET, PUT, and
DELETE. Also, DELETE and PUT may delete or alternate the resource, so we
should create multiple resources via POST to benefit the successor nodes which
may require the resource. We force GET to be the first test case because
either a node (e.g., root node in Figure 3) requires no parameter for
launching a GET request or we could retrieve its required parameters from the
parent node. Again, note that the order in our current template is ad hoc for
fuzzing purposes, there could be other orders which might be more efficient.

Algorithm 1 demonstrates our basic test case generation algorithm. The outer
for loop iterates over the trees of an application. For each tree, we traverse
the tree via a depth-first order and recover the endpoint URLs. For each
method of an endpoint, we obtain its required parameters and retrieve values
for each parameter from the resource pool. There are two key procedures in
this process: Search() and FuzzyMathing() for searching candidate resources,
and Retrieve() for retrieving resource values. Search() is based on the
annotation table. It returns the unique resource identifier if such an entry
exists in the annotation table, or returns the original name otherwise.
FuzzyMathing() searches for candidate resources along the tree path backward
with the heuristics discussed in Section 3.2.2 until a candidate is found.
Since there could be multiple matched resource identifiers, it selects a
random one with matching score above a threshold. In order to further empower
the fuzzing ability of our approach, we also enable FuzzyMathing() to return
none no matter whether a matched resource is found or not. If FuzzyMathing()
returns none, the Retrieve() function will use an arbitrary value generated by
a simple fuzz engine, i.e., a random value of string, integer, or UTF-8
depending on the type of the parameter.

####  3.2.5. Response Analysis and Resource Extraction

We execute each test case immediately after it has been generated and analyze
the response message. If the response code is 2XX, which implies a successful
request, we can then extract the resources and save them into the
corresponding node of the resource pool. Meanwhile, a successful request also
implies the fuzzing pairs generated by FuzzingMatching() is useful, and we
should increase the probability of using these pairs for composing new
requests later via IncreaseMatchingScore(). If the response code is 4XX, which
implies a bad request, we should decrease the probability of using the pairs
via DecreaseMatchingScore(). Finally, a response code of 5XX implies a bug has
been detected.

(a) Coverage for WordPress in 30 minutes.

(b) Coverage for WordPress in 6 hours.

Figure 6. Comparing the efficiency of our tree-based approach with two graph-
based approaches, bread-first search and topological sort.

###  3.3. Overall Fuzzing Strategy

Our basic method in Algorithm 1 only considers required parameters. The number
of generated test cases is linear to the number of APIs, i.e.,
$\leq(k+3)*API\\#$. Therefore, it can finish execution in a short period.
However, besides required parameters, an API may also support dozens of
optional parameters. Generating test cases with optional parameters supplied
should be useful for achieving better code coverage.

Our overall fuzzing strategy is based on the Algorithm 1 but considers both
required and optional parameters. The idea is straightforward, i.e., we
firstly employ the basic method for each API with no optional parameters, and
gradually increase the number of optional parameters. For example, if an API
supports $n$ optional parameters, we should generate $n$ different test cases,
where each one specifies a unique optional parameter. Suppose $m$ of the $n$
requests are successful, then we generate $m*(m-1)$ test cases in the next
round, where each test case contains two optional parameters selected from the
successful ones. We continue this process gradually with more optional
parameters until all the requests with a certain number of operational
parameters fail. Note that exhausting all combinations ($n!$) of optional
parameters for an API is impractical. Our approach can largely reduce the
number of fruitless requests but should also be able to achieve a similar test
effectiveness considering the number of dependencies (resources) can be
successfully solved.

Figure 5 presents an toy example for better demonstrating our overall fuzzing
strategy. Suppose the API tree in Figure 5(a) contains three nodes, N1 and N3
which are token nodes, and :n2 which is a parameter node. We create two sub
resource pools for N1 and N3. Then we generate test cases for N1, :n2, and N3
one by one. For each node, we first generate the test case of a GET request
with required parameters only. Then we generate test cases with optional
parameters for the API. Next, we generate $k$ test cases for POST requests
with required parameters only, followed by such requests with optional
parameters. We continue the test case generation process for PUT and DELETE.
After all test cases for the API tree have been executed, we can continue the
fuzzing process and restart from N1. Note that our second fuzzing round can
generate new test cases different from the first round, e.g., due to the
randomness of the FuzzingMatching() function and updated matching scores of
dependency pairs by IncreaseMatchingScore() or DecreaseMatchingScore().

Table 1. Detailed experimental data of our comparison experiment with RESTler and EvoMaster in six hours. The LoC incerase is calculated as (LoC of foREST - LoC of EvoMaster)/LoC of EvoMaster. Project | API Group | # APIs | RESTler | EvoMaster | foREST
---|---|---|---|---|---
# requests | LoC | # bugs | # requests | LoC | # bugs | # requests | LoC | # bugs | LoC increase
WordPress | all | 39 | 6249 | 15111 | 0 | 6972 | 16183 | 0 | 7338 | 18217 | 3 | 12.5%
GitLab | projects | 33 | 281526 | 1838 | 2 | 107297 | 7298 | 0 | 90470 | 10151 | 3 | 39.1%
groups | 23 | 377780 | 1407 | 0 | 89212 | 6668 | 2 | 89865 | 7433 | 2 | 11.5%
commits | 18 | 375126 | 1900 | 0 | 107200 | 8406 | 0 | 109533 | 15342 | 3 | 82.5%
Total | - | 113 | 1040681 | 20256 | 2 | 310681 | 38553 | 2 | 297206 | 51143 | 11 | 32.7%

(a) Coverage for WordPress in 30 minutes.

(b) Coverage for WordPress in 6 hours.

Figure 7. Experimental result of comparing foREST with RESTler and EvoMaster
in fuzzing WordPress.

##  4\. Evaluation

This section presents our evaluation experiments based on a prototype
implementation of foREST. In particular, we are interested in two questions.

  * •

RQ1: Compared to traditional approaches based on API dependency graphs, can
our tree-based approach be more efficient in practice?

  * •

RQ2: Will foREST perform better than other existing tools, such as RESTler
(Atlidakis et al., 2019) and EvoMaster (Arcuri, 2019)?

Next, we present our experimental setting and experimental results to answer
these two questions.

###  4.1. Implementation and Experimental Setting

We have implemented a prototype tool for the proposed tree-based fuzzing
approach with python 3.8, including both the tree-based structure for API
modeling and the corresponding resource management and retrieving strategies.
It contains 2K+ lines of python code. The tool supports RESTful API
specifications in either Swagger 2.0 or Open API standards. We release our
tool as open source, and it is available online.

We conduct our evaluation experiment in a local network environment, i.e., we
deploy foREST on a PC and test it against local RESTful services. Our
experimental applications include two widely-employed open source RESTful
applications (i.e., WordPress and GitLab). We normally test each application
for six hours and examine the achieved code coverage. More experimental
details are provided later in each sub experiment.

###  4.2. Efficiency of Tree-based Approach

In order to study the efficiency of our novel tree-based approach, we also
implement another version with traditional graph-based approaches using the
same foREST framework. For fair comparison, we implement two representative
graph parsing algorithms, BFS and topological sort. The BFS algorithm directly
employs the approach proposed in RESTler (Atlidakis et al., 2019); for
topological sort, we employ a resource pool to buffer the result generated in
previous request. Therefore, we have three configurations of fuzzing tools
that only differ in the test case generation algorithms.

We fuzz WordPress for six hours with these three configurations and measure
the covered lines of code. Our result is presented in Figure 6. Figure 6(a)
demonstrates their coverage growths in the first 30 minutes with more
observable differences. Each coverage upsurge on the graph generally implies a
new API has been successfully triggered. We can observe that the three
approaches perform comparably in the first ten minutes, and they all cover
about 14000 lines of code. However, the code coverage of our tree-based
approach becomes prominent after that. Figure 6(b) presents the coverage
information of all the six hours. We can obverse that our tree-based approach
finally has covered most lines of code (18217), which is better than 16998
achieved by topological sort, and 14649 achieved by BFS.

(a) Coverage for projects in 30 minutes.

(b) Coverage for projects in six hours.

(c) Coverage for groups in 30 minutes.

(d) Coverage for groups in six hours.

(e) Coverage for commits in 30 minutes.

(f) Coverage for commits in six hours.

Figure 8. Experimental result of comparing foREST with RESTler and EvoMaster
in fuzzing GitLab. GitLab has several API groups, we choose three API groups
(projects, groups, and commits) and fuzz them seperately.

Note that our experiment employs the same request frequencies for the three
configurations, and their final request numbers are comparable. Therefore, we
may conjecture that our tree-based approach is generally more efficient than
traditional graph-based approaches. Meanwhile, it does not undermine the
fuzzing effectiveness in code coverage. Our comparison experiments with
RESTler in the next section can also coincide with this conjecture.

###  4.3. Comparison with Existing Tools

Now, we compare the performance of foREST with two state-of-the-art fuzzing
tools for RESTful APIs, i.e., RESTler (Atlidakis et al., 2019), (Corradini et
al., 2021) and EvoMaster (Arcuri, 2019). RESTler is a graph-based black-box
fuzzing tool collaborated by Columbia University and Microsoft. It adopts the
same problem setting as we do, which only requires the API specification.
EvoMaster is another powerful tool that supports both white-box and black-box
mode. For fair comparison, we use its black-box mode (\--blackBox true) with a
request rate 300 per minute (\--ratePerMinute 300) in our experiment.

We apply these three tools to fuzz two open source applications, WordPress and
GitLab. Figure 7 shows our comparison result for WordPress in 30 minutes and
six hours separately. We can observe that the coverage of foREST grows faster
that RESTler and EvoMaster in the begining. Although EvoMaster outperforms
foREST for a little while, foREST exceeds EvoMaster after the first five
minutes, and the leading superiority becomes more obvious sooner after the
first ten minutes. Table 1 presents the detailed information after six hours.
foREST has covered 18217 lines of code, with three new bugs found. EvoMaster
covered 16183 lines of code with no bugs detected. RESTler covered 15111 lines
of code with no bugs detected. The improvement of code coverage is about
12.5%. Although foREST sends a bit more numbers of requests than other tools,
the advantages of foREST is prominent.

To better compare the effectiveness of our tool, we conduct another group of
fuzzing experiments with GitLab. GitLab contains several groups of
APIs444https://docs.gitlab.com/ee/api/api_resources.html. We choose three
widely-employed groups to conduct of our fuzzing experiments (projects,groups,
and commits) and report the performance on these API groups separately. Our
results are presented in Figure 8. In general, all the results are consistent
with WordPress. foREST performs the best among the three tools, and EvoMaster
is better than RESTler. According to the detailed statistics in Table 1,
RESTler has sent more requests than foREST and EvoMaster in six hours, and
foREST has sent a similar number of requests as EvoMaster. Note that such
speed could be affected by the response rate of the service. Finally, foREST
has covered 10151 lines of code for the API group of projects and has detected
three new bugs. EvoMaster covered 7298 lines of code with no bugs found. The
improvement is about 39.1%. Similarly, the improvement of foREST for the API
group of groups and commits are 11.5% and 82.5% respectively. foREST has
detected eight new bugs for GitLab in total, while the other tools detected
none.

Based on the previous results, we can conclude that foREST has non-trivial
performance advantages over RESTler and EvoMaster in fuzzing RESTful APIs.
Note that that are also other tools that support RESTful API fuzzing, such as
RestTestGen (Viglianisi et al., 2020) and bBOXRT (Laranjeiro et al., 2021).
However, an empirical study (Corradini et al., 2021) has shown that these
tools are either preliminary or not robust compared to RESTler, and RESTler is
the best one over them.

##  5\. Related Work

As REST surges into popularity, there are dozens of papers working on RESTful
API testing. A large portion of these work investigates on how to define test-
oriented specifications, including (Chakrabarti and Kumar, 2009; Pinheiro et
al., 2013; Lamela Seijas et al., 2013; Fertig and Braun, 2015; Segura et al.,
2017; Karlsson et al., 2020, 2021). Similar to traditional software testing,
one major problem for RESTful test case specification lies in how to provide
an oracle for test case verification, such as via property-based (Pinheiro et
al., 2013; Karlsson et al., 2020, 2021) and metamorphic testing (Segura et
al., 2017). Such problems and investigations are not directly related to our
work.

Our work focuses on RESTful API fuzzing, and there are several papers (e.g.,
(Ed-Douibi et al., 2018; Atlidakis et al., 2019, 2020a; Arcuri, 2019, 2020;
Viglianisi et al., 2020; Corradini et al., 2021)) work on the same problem. As
we have studied in this paper, the critical problem for RESTful API fuzzing
lies in how to model the dependency relationships for generating valid
requests. Existing representative work that studies the problem and supports
stateful fuzzing includes RESTler (Atlidakis et al., 2019), EvoMaster (Arcuri,
2019, 2020), and RESTTESTGEN(Viglianisi et al., 2020). Next, we mainly compare
our work with these three tools.

RESTler (Atlidakis et al., 2019) is a stateful RESTful API fuzzing tool. It
employs a graph-based approach to model the dependencies among APIs by
analyzing API specifications. Each test case generated by RESTler is a
sequence of requests in order to be stateful, i.e., the front requests aim to
arrive at the state required by the last request. It traverses the API
dependency graph to generate such sequences. RESTler is a collaborative work
with Microsoft, and there are several follow-ups, such as to enhance the
fuzzing ability with neural networks (Atlidakis et al., 2020a), to check
security property violations (Atlidakis et al., 2020b), and to perform
regression testing with RESTler (Godefroid et al., 2020).

RestTestGen (Viglianisi et al., 2020) is another tool similar to RESTler. It
also models API dependencies as graphs but should be more powerful in the
capability of dependence inference. Instead of strict string matching,
RestTestGen employs several fuzzy matching strategies, such as case
insensitive and stemming. Furthermore, it also introduces abnormal case
generation strategies, such as mutation, missing required parameters, or
incorrect input type. Corradini et al. (Corradini et al., 2021) have conducted
an experiment to compare the performance of RestTestGen with RESTler, as well
as two other tools, bBOXRT (Laranjeiro et al., 2021) and RestTest (Martin-
Lopez et al., 2020), and their result shows that RESTler performs the best in
the benchmark and it is the most robust tool.

EvoMaster (Arcuri, 2019, 2020) is a white-box testing tool but also supports
black-box mode. Similar to our work, it has no API dependency graph. In order
to generate a valid test case for a particular endpoint, it heuristically
searches the antecedent requests or preconditions that should be fulfilled
along the path of the endpoint URL. EvoMaster is a state-of-the-art tool, and
has attracted follow-up work, such as (Zhang et al., 2019) that enhances the
verification ability of EvoMaster for particular RESTful services.

Besides inferring the dependencies based on the default API specification.
There are also other papers that resorts to extra input, such as manual
dependency specification (Martin-Lopez et al., 2019, 2021), or historical
traffic data with machine learning (Mirabella et al., 2021). These approaches
are orthogonal to other work.

To summarize, our work tackles the RESTful API fuzzing problem, which has also
been studied by RESTler (Atlidakis et al., 2019), RestTestGen (Viglianisi et
al., 2020), and EvoMaster (Arcuri, 2019, 2020). The novelty of our paper lies
in that it serves as the first attempt to propose a systematic tree-based
approach for RESTful API fuzzing. Our approach has been shown more efficient
leveraging several subtle design choices, such as tree-based API modeling and
resource management, fuzzing matching and dynamic dependency pair evaluation
strategies, etc.

##  6\. Conclusion

This work has studied the problem of black-box RESTful API fuzzing based on
the API specifications in Swagger or OpenAPI formats. The challenge mainly
lies in how to model the relationships of different APIs in order to solve
resource dependencies and generate valid requests. To tackle this problem,
this work proposes a novel tree-based approach to effectively capture the
relationships among APIs. On one hand, it can largely simplify the dependency
relationships among APIs employed by traditional graph-based approaches. On
the other hand, the resource dependencies modeled by our approach are more
accurate. To study the performance of our approach, we have implemented a
prototype and conducted several groups of comparison experiments with widely-
employed real-world REST services. Our experimental results first verified the
efficiency of the tree-based approach compared to traditional graph-based
approaches, and then showed that foREST can achieve a higher code coverage
than state-of-the-art tools. We believe our proposed approach and prototype
would be useful to the community in advancing the development of RESTful API
fuzzing.

## References

  * (1)
  * Arcuri (2019) Andrea Arcuri. 2019\.  RESTful API automated test case generation with EvoMaster.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 28, 1 (2019), 1–37.
  * Arcuri (2020) Andrea Arcuri. 2020\.  Automated Black-and White-Box Testing of RESTful APIs With EvoMaster.  _IEEE Software_ 38, 3 (2020), 72–78.
  * Atlidakis et al. (2020a) Vaggelis Atlidakis, Roxana Geambasu, Patrice Godefroid, Marina Polishchuk, and Baishakhi Ray. 2020a.  Pythia: grammar-based fuzzing of REST APIs with coverage-guided feedback and learning-based mutations.  _arXiv preprint arXiv:2005.11498_ (2020).
  * Atlidakis et al. (2019) Vaggelis Atlidakis, Patrice Godefroid, and Marina Polishchuk. 2019.  RESTler: Stateful REST API fuzzing. In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_. IEEE, 748–758.
  * Atlidakis et al. (2020b) Vaggelis Atlidakis, Patrice Godefroid, and Marina Polishchuk. 2020b.  Checking security properties of cloud service rest apis. In _2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST)_. IEEE, 387–397.
  * Babić et al. (2019) Domagoj Babić, Stefan Bucur, Yaohui Chen, Franjo Ivančić, Tim King, Markus Kusano, Caroline Lemieux, László Szekeres, and Wei Wang. 2019\.  Fudge: fuzz driver generation at scale. In _Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 975–985.
  * Chakrabarti and Kumar (2009) Sujit Kumar Chakrabarti and Prashant Kumar. 2009.  Test-the-rest: An approach to testing restful web-services. In _2009 Computation World: Future Computing, Service Computation, Cognitive, Adaptive, Content, Patterns_. IEEE, 302–308.
  * Corradini et al. (2021) Davide Corradini, Amedeo Zampieri, Michele Pasqua, and Mariano Ceccato. 2021.  Empirical comparison of black-box test case generation tools for RESTful APIs. In _2021 IEEE 21st International Working Conference on Source Code Analysis and Manipulation (SCAM)_. IEEE, 226–236.
  * Ed-Douibi et al. (2018) Hamza Ed-Douibi, Javier Luis Cánovas Izquierdo, and Jordi Cabot. 2018\.  Automatic generation of test cases for REST APIs: A specification-based approach. In _2018 IEEE 22nd international enterprise distributed object computing conference (EDOC)_. IEEE, 181–190.
  * Fertig and Braun (2015) Tobias Fertig and Peter Braun. 2015.  Model-driven testing of restful apis. In _Proceedings of the 24th International Conference on World Wide Web_. 1497–1502.
  * Gamez-Diaz et al. (2017) Antonio Gamez-Diaz, Pablo Fernandez, and Antonio Ruiz-Cortes. 2017\.  An analysis of RESTful APIs offerings in the industry. In _International Conference on Service-Oriented Computing_. Springer, 589–604.
  * Godefroid et al. (2020) Patrice Godefroid, Daniel Lehmann, and Marina Polishchuk. 2020\.  Differential regression testing for REST APIs. In _Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_. 312–323.
  * Initiative et al. ([n. d.]) OpenAPI Initiative et al. [n. d.].  OpenAPI specification.  https://github.com/OAI/OpenAPI-Specification/blob/main/versions/3.0.0.md.
  * Jiang et al. (2021) Jianfeng Jiang, Hui Xu, and Yangfan Zhou. 2021.  RULF: Rust library fuzzing via API dependency graph traversal. In _Prof. of the 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_.
  * Karlsson et al. (2020) Stefan Karlsson, Adnan Čaušević, and Daniel Sundmark. 2020\.  QuickREST: Property-based test generation of OpenAPI-described RESTful APIs. In _2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST)_. IEEE, 131–141.
  * Karlsson et al. (2021) Stefan Karlsson, Adnan Čaušević, and Daniel Sundmark. 2021\.  Automatic property-based testing of graphql apis. In _2021 IEEE/ACM International Conference on Automation of Software Test (AST)_. IEEE, 1–10.
  * Lamela Seijas et al. (2013) Pablo Lamela Seijas, Huiqing Li, and Simon Thompson. 2013\.  Towards property-based testing of RESTful web services. In _Proceedings of the twelfth ACM SIGPLAN workshop on Erlang_. 77–78.
  * Laranjeiro et al. (2021) Nuno Laranjeiro, João Agnelo, and Jorge Bernardino. 2021\.  A Black Box Tool for Robustness Testing of REST Services.  _IEEE Access_ 9 (2021), 24738–24754.
  * Martin-Lopez et al. (2021) Alberto Martin-Lopez, Sergio Segura, Carlos Muller, and Antonio Ruiz-Cortés. 2021.  Specification and automated analysis of inter-parameter dependencies in web APIs.  _IEEE Transactions on Services Computing_ (2021).
  * Martin-Lopez et al. (2019) Alberto Martin-Lopez, Sergio Segura, and Antonio Ruiz-Cortés. 2019.  A catalogue of inter-parameter dependencies in RESTful web APIs. In _International Conference on Service-Oriented Computing_. Springer, 399–414.
  * Martin-Lopez et al. (2020) Alberto Martin-Lopez, Sergio Segura, and Antonio Ruiz-Cortés. 2020.  RESTest: Black-box constraint-based testing of RESTful Web APIs. In _International Conference on Service-Oriented Computing_. Springer, 459–475.
  * Mirabella et al. (2021) A Giuliano Mirabella, Alberto Martin-Lopez, Sergio Segura, Luis Valencia-Cabrera, and Antonio Ruiz-Cortés. 2021.  Deep Learning-Based Prediction of Test Input Validity for RESTful APIs. In _2021 IEEE/ACM Third International Workshop on Deep Learning for Testing and Testing for Deep Learning (DeepTest)_. IEEE, 9–16.
  * Pinheiro et al. (2013) Pedro Victor Pontes Pinheiro, Andre Takeshi Endo, and Adenilso Simao. 2013.  Model-based testing of RESTful web services using UML protocol state machines. In _Brazilian workshop on systematic and automated software testing_. Citeseer, 1–10.
  * Segura et al. (2017) Sergio Segura, José A Parejo, Javier Troya, and Antonio Ruiz-Cortés. 2017.  Metamorphic testing of RESTful web APIs.  _IEEE Transactions on Software Engineering_ 44, 11 (2017), 1083–1099.
  * Viglianisi et al. (2020) Emanuele Viglianisi, Michael Dallago, and Mariano Ceccato. 2020\.  RestTestGen: automated black-box testing of RESTful APIs. In _2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST)_. IEEE, 142–152.
  * Zhang et al. (2019) Man Zhang, Bogdan Marculescu, and Andrea Arcuri. 2019\.  Resource-based test case generation for RESTful web services. In _Proceedings of the genetic and evolutionary computation conference_. 1426–1434.