Tan<EMAIL_ADDRESS>Gangming<EMAIL_ADDRESS>Ping
<EMAIL_ADDRESS>Yizhou<EMAIL_ADDRESS>Cognitive Computing Lab
Baidu Research
10900 NE 8th St. Bellevue, WA USA Department of Computer Science
The University of Hong Kong Bilateral Local Attention Vision Transformer

# BOAT: Bilateral Local Attention Vision Transformer

###### Abstract

Vision Transformers achieved outstanding performance in many computer vision
tasks. Early Vision Transformers such as ViT and DeiT adopt global self-
attention, which is computationally expensive when the number of patches is
large. To improve the efficiency, recent Vision Transformers adopt local self-
attention mechanisms, where self-attention is computed within local windows.
Despite the fact that window-based local self-attention significantly boosts
efficiency, it fails to capture the relationships between distant but similar
patches in the image plane. To overcome this limitation of image-space local
attention, in this paper, we further exploit the locality of patches in the
feature space. We group the patches into multiple clusters using their
features, and self-attention is computed within every cluster. Such feature-
space local attention effectively captures the connections between patches
across different local windows but still relevant. We propose a Bilateral
lOcal Attention vision Transformer (BOAT), which integrates feature-space
local attention with image-space local attention. We further integrate BOAT
with both Swin and CSWin models, and extensive experiments on several
benchmark datasets demonstrate that our BOAT-CSWin model clearly and
consistently outperforms existing state-of-the-art CNN models and vision
Transformers.

##  1 Introduction

Following the great success of Transformers [Vaswani et al.(2017)Vaswani,
Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser, and Polosukhin] in natural
language processing tasks, researchers have recently proposed vision
Transformers [Dosovitskiy et al.(2021)Dosovitskiy, Beyer, Kolesnikov,
Weissenborn, Zhai, Unterthiner, Dehghani, Minderer, Heigold, Gelly, Uszkoreit,
and Houlsby, Touvron et al.(2021)Touvron, Cord, Douze, Massa, Sablayrolles,
and Jégou, Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo, Chu et
al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen, Chen et
al.(2021)Chen, Yu, and Li, Yu and Li(2022)], which have achieved outstanding
performance in many computer vision tasks, including image recognition,
detection, and segmentation. As early versions of vision transformers, ViT
[Dosovitskiy et al.(2021)Dosovitskiy, Beyer, Kolesnikov, Weissenborn, Zhai,
Unterthiner, Dehghani, Minderer, Heigold, Gelly, Uszkoreit, and Houlsby] and
DeiT [Touvron et al.(2021)Touvron, Cord, Douze, Massa, Sablayrolles, and
Jégou] uniformly divide an image into $16\times 16$ patches (tokens) and apply
a stack of standard Transformer layers to a sequence of tokens formed using
these patches. The original self-attention mechanism is global, i.e., the
receptive field of a patch in ViT and DeiT covers all patches of the image,
which is vital for modeling long-range interactions among patches. On the
other hand, the global nature of self-attention imposes a great challenge in
efficiency. Specifically, the computational complexity of self-attention is
quadratic in terms of the number of patches. As the number of patches is
inversely proportional to the patch size when the size of the input image is
fixed, the computational cost forces ViT and DeiT to adopt medium-size
patches, which might not be as effective as smaller patches generating higher-
resolution feature maps, especially for dense prediction tasks such as
segmentation.

To maintain higher resolution feature maps while achieving high efficiency,
some methods [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo, Chu
et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] exploit image-
space local attention. They divide an image into multiple local windows, each
of which includes a number of patches. Self-attention operations are only
performed on patches within the same local window. This is a reasonable design
since a patch is likely to be affiliated with other patches in the same local
window but not highly relevant to patches in other windows. Thus, pruning
attention between patches from different windows might not significantly
deteriorate the performance. Meanwhile, the computational cost of window-based
self-attention is much lower than that of the original self-attention over the
entire image. Swin Transformer [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang,
Lin, and Guo] and Twins [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei,
Xia, and Shen] are such examples. Swin Transformer [Liu et al.(2021)Liu, Lin,
Cao, Hu, Wei, Zhang, Lin, and Guo] performs self-attention within local
windows. To facilitate communication between patches from different windows,
Swin Transformer has two complementary window partitioning schemes, and a
window in one scheme overlaps with multiple windows in the second scheme.
Twins [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen]
performs self-attention within local windows and builds connections among
different windows by performing (global) self-attention over feature vectors
sparsely sampled from the entire image using a regular subsampling pattern.

Figure 1: The image-space local attention versus the feature-space local
attention.

In this work, we rethink local attention and explore locality from a broader
perspective. Specifically, we investigate feature-space local attention apart
from its image-space counterpart. Instead of computing local self-attention in
the image space, feature-space local attention exploits locality in the
feature space. It is based on the fact that patch feature vectors close to
each other in the feature space tend to have more influence on each other in
the computed self-attention results. This is because the actual contribution
of a feature vector to the self-attention result at another feature vector is
controlled by the similarity between these two feature vectors. Feature-space
local attention computes the self-attention result at a feature vector using
its feature-space nearest neighbors only while setting the contribution from
feature vectors farther away to zero. This essentially defines a piecewise
similarity function, which clamps the similarity between feature vectors far
apart to zero. In comparison to the aforementioned image-space local
attention, feature-space local attention has been rarely exploited in vision
transformers. As shown in Figure 1, feature-space local attention computes
attention among relevant patches which might not be close to each other in the
image plane. Thus, it is a natural compensation to image-space local
attention, which might miss meaningful connections between patches residing in
different local windows.

In this paper, we propose a novel vision Transformer architecture, Bilateral
lOcal Attention vision Transformer (BOAT), to exploit the complementarity
between feature-space and image-space local attention. The essential component
in our network architecture is the bilateral local attention block, consisting
of a feature-space local attention module and an image-space local attention
module. The image-space local attention module divides an image into multiple
local windows as Swin [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and
Guo] and CSWin [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and
Guo], and self-attention is computed within each local window. In contrast,
feature-space local attention groups all the patches into multiple clusters
and self-attention is computed within each cluster. Feature-space local
attention could be implemented in a straightforward way using K-means
clustering. Nevertheless, K-means clustering cannot ensure the generated
clusters are evenly sized, thus impedes efficient parallel implementation. In
addition, sharing self-attention parameters among unevenly sized clusters may
also negatively impact the effectiveness of self-attention. To overcome this
obstacle, we propose hierarchical balanced clustering, which groups patches
into clusters of equal size.

We conduct experiments on multiple computer vision tasks, including image
classification, semantic segmentation, and object detection. Experiments on
several public benchmarks demonstrate that our BOAT clearly and consistently
improves existing image-space local attention vision Transformers, including
Swin [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] and CSWin
[Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo], on these
tasks.

##  2 Related Work

###  2.1 Vision Transformers

In the past decade, CNN has achieved tremendous successes in numerous computer
vision tasks [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton, He et
al.(2016)He, Zhang, Ren, and Sun]. The natural language processing (NLP)
backbone, Transformer, has recently attracted the attention of researchers in
the computer vision community. After dividing an image into non-overlapping
patches (tokens), Vision Transformer (ViT) [Dosovitskiy et
al.(2021)Dosovitskiy, Beyer, Kolesnikov, Weissenborn, Zhai, Unterthiner,
Dehghani, Minderer, Heigold, Gelly, Uszkoreit, and Houlsby] applies
Transformer for communications among the tokens. Without delicately devised
convolution kernels, ViT achieved excellent performance in image recognition
in comparison to CNNs using a huge training corpus. DeiT [Touvron et
al.(2021)Touvron, Cord, Douze, Massa, Sablayrolles, and Jégou] improves data
efficiency by exploring advanced training and data augmentation strategies.
Recently, many efforts have been devoted to improving the recognition accuracy
and efficiency of Vision Transformers.

To boost the recognition accuracy, T2T-ViT [Yuan et al.(2021)Yuan, Chen, Wang,
Yu, Shi, Jiang, Tay, Feng, and Yan] proposes a Tokens-to-Token transformation,
recursively aggregating neighboring tokens into one token for modeling local
structures. TNT [Han et al.(2021)Han, Xiao, Wu, Guo, Xu, and Wang] also
investigates local structure modeling. It additionally builds an inner-level
Transformer to model the visual content within each local patch. PVT [Wang et
al.(2021b)Wang, Xie, Li, Fan, Song, Liang, Lu, Luo, and Shao] uses small-scale
patches, yielding higher resolution feature maps for dense prediction.
Meanwhile, PVT progressively shrinks the feature map size for computation
reduction. PiT [Heo et al.(2021)Heo, Yun, Han, Chun, Choe, and Oh] also
decreases spatial dimensions through pooling and increases channel dimensions
in deeper layers.

More recently, computing self-attention within local windows [Liu et
al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo, Chu et al.(2021)Chu,
Tian, Wang, Zhang, Ren, Wei, Xia, and Shen, Huang et al.(2021)Huang, Ben, Luo,
Cheng, Yu, and Fu, Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen,
and Guo], has achieved a good trade-off between effectiveness and efficiency.
For example, Swin [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and
Guo] divides an image into multiple local windows and computes self-attention
among patches from the same window. To achieve communication across local
windows, Swin shifts window configurations in different layers. Twins [Chu et
al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] also exploits local
windows for enhancing efficiency. To achieve cross-window communication, it
computes additional self-attention over features sampled from the entire
image. Similarly, Shuffle Transformer [Huang et al.(2021)Huang, Ben, Luo,
Cheng, Yu, and Fu] exploits local windows and performs cross-window
communication by shuffling patches. CSWin [Dong et al.(2022)Dong, Bao, Chen,
Zhang, Yu, Yuan, Chen, and Guo] adopts cross-shaped windows, computing self-
attention in horizontal and vertical stripes in parallel. The aforementioned
local attention models [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin,
and Guo, Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen,
Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu, Dong et al.(2022)Dong,
Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] only exploit image-space locality.
In contrast, our BOAT exploits not only image-space locality but also feature-
space locality.

###  2.2 Efficient Transformers

High computational costs limit Transformer’s usefulness in practice. Thus,
much research [Tay et al.(2020b)Tay, Dehghani, Bahri, and Metzler] has
recently been dedicated to improving efficiency. One popularly used strategy
for speeding up Transformers enforces sparse attention matrices by limiting
the receptive field of each token. Image Transformer [Parmar et
al.(2018)Parmar, Vaswani, Uszkoreit, Kaiser, Shazeer, Ku, and Tran] and Block-
wise Transformer [Qiu et al.(2020)Qiu, Ma, Levy, Yih, Wang, and Tang] divide a
long sequence into local buckets. In this case, the attention matrix has a
block-diagonal structure. Only self-attention within each bucket is retained,
and cross-bucket attention is pruned. Transformers based on image-space local
attention, such as Swin Transformer [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei,
Zhang, Lin, and Guo], Twins [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei,
Xia, and Shen], Shuffle Transformer [Huang et al.(2021)Huang, Ben, Luo, Cheng,
Yu, and Fu], and CSWin Transformer [Dong et al.(2022)Dong, Bao, Chen, Zhang,
Yu, Yuan, Chen, and Guo] also adopt buckets (windows) for boosting efficiency.
In parallel to bucket-based local attention, strided attention is another
approach for achieving sparse attention matrices. Sparse Transformer [Child et
al.(2019)Child, Gray, Radford, and Sutskever] and LongFormer [Beltagy et
al.(2020)Beltagy, Peters, and Cohan] utilize strided attention, which computes
self-attention over features sampled with a sparse grid with a stride larger
than one, leading to a sparse attention matrix facilitating faster
computation. The global sub-sampling layer in Twins [Chu et al.(2021)Chu,
Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] and the shuffle module in Shuffle
Transformer [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] can be
regarded as strided attention modules. Some recent works exploit pure MLP-
based architectures [Yu et al.(2021a)Yu, Li, Cai, Sun, and Li, Yu et
al.(2022)Yu, Li, Cai, Sun, and Li, Yu et al.(2021b)Yu, Li, Cai, Sun, and Li,
Chen et al.(2022)Chen, Yu, and Li] to boost efficiency.

Unlike the above mentioned image-space local attention, several methods
determine the scope of local attention in the feature space. Reformer [Kitaev
et al.(2020)Kitaev, Kaiser, and Levskaya] distributes tokens to buckets by
feature-space hashing functions. Routing Transformer [Roy et al.(2021)Roy,
Saffar, Vaswani, and Grangier] applies online K-means to cluster tokens.
Sinkhorn Sorting Network [Tay et al.(2020a)Tay, Bahri, Yang, Metzler, and
Juan] learns to sort and divide an input sequence into chunks. Our feature-
space local attention module also falls into this category. As far as we know,
this paper is the first attempt to apply feature-space grouping to vision
Transformers.

##  3 Method

Figure 2: Architecture of Bilateral lOcal Attention Vision Transformer (BOAT).

As visualized in Figure 2, the proposed BOAT architecture consists of a patch
embedding module, and a stack of $L$ Bilateral Local Attention blocks.
Meanwhile, we exploit a hierarchical pyramid structure. Below we only briefly
introduce the patch embedding module and the hierarchical pyramid structure
and leave the details of the proposed Bilateral Local Attention block in
Section 3.1 and 3.2.

Patch embedding. For an input image with size $H\times W$, we follow Swin [Liu
et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] and CSWin Transformer
[Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo], and
leverage convolutional token embedding ($7\times 7$ convolution layer with
stride 4) to obtain $\frac{H}{4}\times\frac{W}{4}$ patch tokens, and the
dimension of each token is $C$.

Hierarchical pyramid structure. Similar to Swin [Liu et al.(2021)Liu, Lin,
Cao, Hu, Wei, Zhang, Lin, and Guo] and CSWin Transformer [Dong et
al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo], we also build a
hierarchical pyramid structure. The whole architecture consists of four
stages. A convolution layer ($3\times 3$, stride $2$) is used between two
adjacent stages to merge patches. It reduces the number of tokens and doubles
the number of channels. Therefore, in the $i$-th stage, the feature map
contains $\frac{H}{2^{(i+1)}}\times\frac{W}{2^{(i+1)}}$ tokens and $2^{i-1}C$
channels.

###  3.1 Bilateral Local Attention Block

Figure 3: Architecture of Bilateral Local Attention (BLA) Block.

As shown in Figure 3, a Bilateral Local Attention (BLA) Block consists of an
image-space local attention (ISLA) module, a feature-space (content-based)
local attention (FSLA) module, an MLP module, and several layer normalization
(LN) modules. Let us denote the set of input tokens by
$\mathcal{T}_{\mathrm{in}}=\\{\mathbf{t}_{i}\\}_{i=1}^{N}$ where
$\mathbf{t}_{i}\in\mathbb{R}^{C}$, $C$ is the number of channels and $N$ is
the number of tokens. The input tokens go through a normalization layer
followed by an image-space local attention (ISLA) module, which has a shortcut
connection:

${\mathcal{T}}_{\mathrm{ISLA}}=\mathcal{T}_{\mathrm{in}}+\mathrm{ISLA}(\mathrm{LN}(\mathcal{T}_{\mathrm{in}})).$
(1)

Image-space local attention only computes self-attention among tokens within
the same local window. We adopt existing window-based local attention modules,
such as those in Swin Transformer [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei,
Zhang, Lin, and Guo] and CSWin Transformer [Dong et al.(2022)Dong, Bao, Chen,
Zhang, Yu, Yuan, Chen, and Guo] as our ISLA module due to their excellent
performance. Intuitively, patches within the same local window are likely to
be closely related to each other. However, some distant patches in the image
space might also reveal important connections, such as similar contents, that
could be helpful for visual understanding. Simply throwing away such
connections between distant patches in the image space might deteriorate image
recognition performance.

To bring back the useful information dropped out by image-space local
attention, we develop a feature-space local attention (FSLA) module.

The output of the ISLA module, ${\mathcal{T}}_{\mathrm{ISLA}}$, is fed into
another normalization layer followed by a feature-space (content-based) local
attention (FSLA) module, which also has a shortcut connection:

${\mathcal{T}}_{\mathrm{FSLA}}={\mathcal{T}}_{\mathrm{ISLA}}+\mathrm{FSLA}(\mathrm{LN}({\mathcal{T}}_{\mathrm{ISLA}})).$
(2)

The FSLA module computes self-attention among tokens that are close in the
feature space, which is complementary to the ISLA module. Meanwhile, by only
considering local attention in the feature space, FSLA is more efficient than
the original (global) self-attention. We will present the details of FSLA in
Section 3.2. Following CSWin [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu,
Yuan, Chen, and Guo], we also add locally-enhanced positional encoding to each
feature-space local attention layer to model position.

At last, the output of the FSLA module, ${\mathcal{T}}_{\mathrm{FSLA}}$, is
processed by another normalization layer and an MLP module to generate the
output of a Bilateral Local Attention Block:

${\mathcal{T}}_{\mathrm{out}}={\mathcal{T}}_{\mathrm{FSLA}}+\mathrm{MLP}(\mathrm{LN}({\mathcal{T}}_{\mathrm{FSLA}})).$
(3)

Following existing vision Transformers [Dosovitskiy et al.(2021)Dosovitskiy,
Beyer, Kolesnikov, Weissenborn, Zhai, Unterthiner, Dehghani, Minderer,
Heigold, Gelly, Uszkoreit, and Houlsby, Touvron et al.(2021)Touvron, Cord,
Douze, Massa, Sablayrolles, and Jégou], the MLP module consists of two fully-
connected layers. The first one increases the feature dimension from $C$ to
$rC$ and the second one decreases the feature dimension from $rC$ back to $C$.
By default, we set $r=4$.

###  3.2 Feature-Space Local Attention

Different from image-space local attention which groups tokens according to
their spatial locations in the image plane, feature-space local attention
seeks to group tokens according to their content, _i.e._ , features. We could
simply perform K-means clustering on token features to achieve this goal.
Nevertheless, K-means clustering cannot ensure that the generated clusters are
equally sized, which makes it difficult to have efficient parallel
implementation on GPU platforms, and may also negatively impact the overall
effectiveness of self-attention.

Figure 4: Example of balanced hierarchical clustering. In this example, the
number of hierarchical levels is $3$. There are $2^{3}=8$ clusters in the
bottom level.

Balanced hierarchical clustering. To overcome the imbalance problem of K-means
clustering, we propose a balanced hierarchical clustering, which performs $K$
levels of clustering. At each level, it conducts balanced binary clustering,
which equally splits a set of tokens into two clusters. Let us denote the set
of input tokens by ${\mathcal{T}}=\\{\mathbf{t}_{i}\\}_{i=1}^{N}$. In the
first level, it splits $N$ tokens in $\mathcal{T}$ into two subsets with
${N}/{2}$ tokens each. At the $k$-th level, it splits $N/2^{k-1}$ tokens
assigned to the same subset in the upper level into two smaller subsets of
$N/2^{k}$ size. At the end, we obtain $2^{K}$ evenly sized subsets in the
final level, $\\{\mathcal{T}_{i}\\}_{i=1}^{2^{K}}$, and the size of each
subset $|\mathcal{T}_{i}|$ is equal to $N/{2^{K}}$. Here, we require the
condition that $N$ is divisible by $2^{K}$, which can be easily satisfied in
existing vision Transformers. We visualize the process of balanced
hierarchical clustering in Figure 4. The core operation in balanced
hierarchical clustering is our devised balanced binary clustering, which we
elaborate below.

Balanced binary clustering. Given a set of $2m$ tokens
$\\{\mathbf{t}_{i}\\}_{i=1}^{2m}$, balanced binary clustering divides them
into two groups and the size of each group is $m$. Similar to K-means
clustering, our balanced binary clustering relies on cluster centroids. To
determine the cluster membership of each sample, K-means clustering only
considers the distance between the sample and all centroids. In contrast, our
balanced binary clustering further requires that the two resulting clusters
have equal size. Let us denote the two cluster centroids as $\mathbf{c}_{1}$
and $\mathbf{c}_{2}$. For each token $\mathbf{t}_{i}$, we compute distance
ratio, $r_{i}$, as a metric to determine its cluster membership:

$r_{i}=\frac{s(\mathbf{t}_{i},\mathbf{c}_{1})}{s(\mathbf{t}_{i},\mathbf{c}_{2})},~{}\forall
i\in[1,2m],$ (4)

where $s(\mathbf{x},\mathbf{y})$ denotes the cosine similarity between
$\mathbf{x}$ and $\mathbf{y}$. The $2m$ tokens
$\\{\mathbf{t}_{i}\\}_{i=1}^{2m}$ are sorted in the decreasing order of their
distance ratios $\\{{r}_{i}\\}_{i=1}^{2m}$. We assign the tokens in the first
half of the sorted list to the first cluster $\mathcal{C}_{1}$ and those in
the second half of the sorted list to the second cluster $\mathcal{C}_{2}$,
where the size of both $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ is $m$. The
mean of the tokens from each cluster is used to update the cluster centroid.
Similar to K-means, our balanced binary clustering updates cluster centroids
and the cluster membership of every sample in an iterative manner. Note that
cluster centroids are always computed on the fly, and are not learnable
parameters. The detailed steps of the proposed balanced binary clustering are
given in Algorithm 1.

1

Input: Tokens $\\{\mathbf{t}_{i}\\}_{i=1}^{2m}$ and the iteration number, $T$.

Output: Two clusters, $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$.

2

3Initialize centroids $\mathbf{c}_{1}=\frac{\sum_{i=1}^{m}\mathbf{t}_{i}}{m}$,
$\mathbf{c}_{2}=\frac{\sum_{i=m+1}^{2m}\mathbf{t}_{i}}{m}$

4while  _$n\\_iter\in[1,T]$_ do

5 for  _$i\in[1,2m]$_ do

6
$r_{i}=\frac{s(\mathbf{t}_{i},\mathbf{c}_{1})}{s(\mathbf{t}_{i},\mathbf{c}_{2})}$

7 [$i_{1},\cdots,i_{2m}$] = argsort([$r_{1},\cdots,r_{2m}$])

8 $\mathcal{C}_{1}=\\{\mathbf{t}_{i_{j}}\\}_{j=1}^{m}$,
$\mathcal{C}_{2}=\\{\mathbf{t}_{i_{j}}\\}_{j=m+1}^{2m}$

9 $\mathbf{c}_{1}=\frac{\sum_{\mathbf{c}\in\mathcal{C}_{1}}\mathbf{c}}{m}$,
$\mathbf{c}_{2}=\frac{\sum_{\mathbf{c}\in\mathcal{C}_{2}}\mathbf{c}}{m}$

10

Algorithm 1 Balanced Binary Clustering.

In the aforementioned balanced binary clustering, two resulting clusters have
no shared tokens, _i.e._ , $\mathcal{C}_{1}\cap\mathcal{C}_{2}=\emptyset$. One
main drawback of the non-overlapping setting is that, a token in the middle
portion of the sorted list has some of its feature-space neighbors in one
cluster while the other neighbors in the other cluster. No matter which
cluster this token is finally assigned to, the connection between the token
and part of its feature-space neighbors will be cut off. For example, the
token at the $m$-th location of the sorted list cannot communicate with the
token at the $m+1$-st location during attention calculation because they are
assigned to different clusters. Overlapping balanced binary clustering
overcomes this drawback by assigning the first $m+n$ tokens in the sorted list
to the first cluster, _i.e._ ,
$\hat{\mathcal{C}}_{1}=\\{\mathbf{t}_{j_{i}}\\}_{i=1}^{m+n}$, and the last
$m+n$ tokens in the sorted list to the second cluster, _i.e._ ,
$\hat{\mathcal{C}}_{2}=\\{\mathbf{t}_{j_{i}}\\}_{i=m-n+1}^{2m}$. Thus, the two
resulting clusters have $2n$ tokens in common, _i.e._ ,
$\hat{\mathcal{C}}_{1}\cap\hat{\mathcal{C}}_{2}=\\{\mathbf{t}_{j_{i}}\\}_{i=m-n+1}^{m+n}$.
By default, we only adopt overlapping binary clustering at the last level of
the proposed balanced hierarchical clustering and use the non-overlapping
version at the other levels. We set $n=20$ in all experiments for overlapping
binary clustering.

Local attention within cluster. Through the above introduced balanced
hierarchical clustering, the set of tokens, $\mathcal{T}$, are grouped into
$2^{K}$ subsets $\\{\mathcal{T}_{i}\\}_{i=1}^{2^{K}}$, where
$|\mathcal{T}_{i}|=\frac{N}{2^{K}}$.

The standard self-attention (SA) is performed within each subset:

$\hat{\mathcal{T}}_{k}=\mathrm{SA}({\mathcal{T}}_{k}),~{}\forall
k\in[1,2^{K}].$ (5)

The output, $\hat{\mathcal{T}}$, is the union of all attended subsets:

$\hat{\mathcal{T}}=\underset{k\in[1,K]}{\bigcup}\hat{\mathcal{T}}_{k}.$ (6)

Following the multi-head configuration in Transformer, we also devise multi-
head feature-space local attention. Note that, in our multi-head feature-space
local attention, we implement multiple heads not only for computing self-
attention in Eq. (5) as a standard Transformer, but also for performing
balanced hierarchical clustering. That is, balanced hierarchical clustering is
performed independently in each head. Thus, for a specific token, in different
heads, it might pay feature-based local attention to different tokens. This
configuration is more flexible than Swin [Liu et al.(2021)Liu, Lin, Cao, Hu,
Wei, Zhang, Lin, and Guo], where multiple heads share the same local window.

##  4 Experiments

To demonstrate the effectiveness of our BOAT as a general vision backbone, we
conduct experiments on image classification, semantic segmentation and object
detection.

We build BOAT on top of two recent local attention vision Transformers, Swin
[Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] and CSWin [Dong
et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo]. We term the BOAT
built upon Swin as BOAT-Swin. In BOAT-Swin, the image-space local attention
(ISLA) module adopts shifted window attention in Swin. In contrast, the ISLA
module in BOAT-CSWin uses cross-shape window attention in CSWin. We provide
the detailed specifications of BOAT-Swin and BOAT-CSWin in Section 1 of the
supplementary materials. Meanwhile, we present main experimental results in
the following sections. More ablation studies are presented in Section 2 of
the supplementary materials.

###  4.1 Image Classification

Method | size | #para. | FLOPs | Top-1 | Method | size | #para. | FLOPs | Top-1
---|---|---|---|---|---|---|---|---|---
ReGNetY-4G [Radosavovic et al.(2020)Radosavovic, Kosaraju, Girshick, He, and Dollár] | 224 | 21M | 4.0G | 80.0 |  |  |  |  |
PVTv2-B2 [Wang et al.(2021a)Wang, Xie, Li, Fan, Song, Liang, Lu, Luo, and Shao] | 224 | 25M | 4.0G | 82.0 |  Focal-T [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] | 224 | 29M | 4.9G | 82.2
Swin-T [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] | 224 | 29M | 4.5G | 81.3 | BOAT-Swin-T (ours) | 224 | 31M | 5.2G | 82.3
CSWin-T [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] | 224 | 23M | 4.3G | 82.7 | BOAT-CSWin-T (ours) | 224 | 27M | 5.1G | 83.7
ReGNetY-8G [Radosavovic et al.(2020)Radosavovic, Kosaraju, Girshick, He, and Dollár] | 224 | 39M | 8.0 | 81.7 |  PVTv2-B4 [Wang et al.(2021a)Wang, Xie, Li, Fan, Song, Liang, Lu, Luo, and Shao] | 224 | 62M | 10.1G | 83.6
Twins-B | 224 | 56M | 8.3G | 83.2 |  Shuffle-S [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] | 224 | 50M | 8.9G | 83.5
NesT-S [Zhang et al.(2022)Zhang, Zhang, Zhao, Chen, Arik, and Pfister], | 224 | 38M | 10.4G | 83.3 |  Focal-S [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] | 224 | 51M | 9.1G | 83.5
Swin-S [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] | 224 | 50M | 8.7G | 83.0 | BOAT-Swin-S (ours) | 224 | 56M | 10.1G | 83.6
CSWin-S [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] | 224 | 35M | 6.9G | 83.6 | BOAT-CSWin-S (ours) | 224 | 41M | 8.0G | 84.1
ReGNetY-16G [Radosavovic et al.(2020)Radosavovic, Kosaraju, Girshick, He, and Dollár] | 224 | 84M | 16.0G | 82.9 |  ViT-B/16T [Dosovitskiy et al.(2021)Dosovitskiy, Beyer, Kolesnikov, Weissenborn, Zhai, Unterthiner, Dehghani, Minderer, Heigold, Gelly, Uszkoreit, and Houlsby] | 384 | 86M | 55.4G | 77.9
DeiT-B [Touvron et al.(2021)Touvron, Cord, Douze, Massa, Sablayrolles, and Jégou] | 224 | 86M | 17.5G | 81.8 |  T2T-24 [Yuan et al.(2021)Yuan, Chen, Wang, Yu, Shi, Jiang, Tay, Feng, and Yan] | 224 | 64M | 14.1G | 82.3
TNT-B [Han et al.(2021)Han, Xiao, Wu, Guo, Xu, and Wang] | 224 | 66M | 14.1G | 82.8 |  PiT-B [Heo et al.(2021)Heo, Yun, Han, Chun, Choe, and Oh] | 224 | 74M | 12.5G | 82.0
PVTv2-B5 [Wang et al.(2021a)Wang, Xie, Li, Fan, Song, Liang, Lu, Luo, and Shao] | 224 | 82M | 11.8G | 83.8 | Twins-L | 224 | 99M | 14.8G | 83.7
Shuffle-B [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] | 224 | 88M | 15.4G | 84.0 |  NesT-B [Zhang et al.(2022)Zhang, Zhang, Zhao, Chen, Arik, and Pfister], | 224 | 68M | 17.9G | 83.8
Focal-B [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] | 224 | 90M | 16.0G | 83.8 |  CrossFormer-L [Wang et al.(2021c)Wang, Yao, Chen, Lin, Cai, He, and Liu] | 224 | 92M | 16.1G | 84.0
Swin-B [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] | 224 | 88M | 15.4G | 83.5 | BOAT-Swin-B (ours) | 224 | 98M | 17.8G | 83.8
CSWin-B [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] | 224 | 78M | 15.0G | 84.2 | BOAT-CSWin-B (ours) | 224 | 90M | 17.5G | 84.7

Table 1: Comparison of image classification performance on the ImageNet-1K
dataset.

We follow the same training strategies as other vision Transformers. We train
our models using the training split of ImageNet-1K [Deng et al.(2009)Deng,
Dong, Socher, Li, Li, and Li] with $224\times 224$ input resolution and
without external data. Specifically, both Swin and BOAT-Swin are trained for
$300$ epochs, and both CSWin and BOAT-CSWin are trained for $310$ epochs.
Table 1 compares the performance of the proposed BOAT models with the state-
of-the-art vision backbones. As shown in the table, with a slight increase in
the number of parameters and FLOPs, our BOAT-Swin model consistently improves
the vanilla Swin model under the tiny, small and base settings. Meanwhile, our
BOAT-CSWin model also improves the vanilla CSWin model by a similar degree
under the tiny, small and base settings. Such improvements over Swin and CSWin
models demonstrate the effectiveness of feature-space local attention.

Comparisons with Reformer and K-means. Reformer [Kitaev et al.(2020)Kitaev,
Kaiser, and Levskaya] also exploits feature-space local attention. It divides
tokens into multiple groups using Locality Sensitivity Hashing (LSH). based on
sign random projections [Charikar(2002), Li(2019)], which is independent of
specific input data, and might be sub-optimal for different input data.
K-means clustering is another choice for dividing tokens into multiple groups
for exploiting feature-space local attention. Nevertheless, K-means clustering
cannot ensure that the generated clusters are equally sized, which makes it
difficult to have efficient parallel implementation on GPU platforms. To
enforce the clusters from K-means clustering to be equally sized, we can sort
the tokens according to their cluster index and then equally divide the sorted
tokens into multiple groups, as visualized in Figure 5. However, this sort-
and-divide process might divide tokens from a large cluster into multiple
groups and also merge tokens from small clusters into the same group. This
would negatively impact the overall effectiveness of feature-space local
attention.

Figure 5: The process of enforcing the clusters from K-means to be equally sized. Method | Reformer | K-means | Ours
---|---|---|---
Top-1 Accuracy | $81.7$ | $81.8$ | $82.3$
Table 2: Comparison of image classification accuracy with Reformer and
K-means.

We compare the performance of BOAT-Swin-Tiny against the performance of a
model where our balanced hierarchical clustering is replaced with LSH in
Reformer or K-means clustering. We keep the other layers unchanged. As shown
in Table 2, our BOAT-Swin-Tiny clearly outperforms Reformer and K-means
clustering.

The effectiveness of FSLA. To directly demonstrate the effectiveness of
feature-space local attention (FSLA), we replace all FSLA blocks in BOAT-
Swin-T with image-space local attention (ISLA) blocks. As shown in Table 3,
the accuracy drops from $82.3\%$ to $81.5\%$.

Model | BOAT-Swin-T (with FSLA) | Baseline (with ISLA)
---|---|---
Accuracy | $82.3$ | $81.5$
Table 3: Ablation study on FSLA by replacing FSLA with ISLA.

The effectiveness of overlapping balanced hierarchical clustering. We compare
the performance of overlapping balanced hierarchical clustering with its non-
overlapping counterpart on the ImageNet-1K dataset. As shown in Table 4, the
overlapping setting achieves consistently higher classification accuracy in
BOAT-CSwin-Tiny, Small and Base models. Higher accuracy is expected since the
overlapping setting gives rise to larger receptive fields.

Overlap | BOAT-CSWin-T | BOAT-CSWin-S | BOAT-CSWin-B
---|---|---|---
No | $83.3\%$ | $84.0\%$ | $84.5\%$
Yes | $83.7\%$ | $84.1\%$ | $84.7\%$
Table 4: Comparison of image classification accuracy between overlapping
balanced hierarchical clustering and the non-overlapping version.

###  4.2 Semantic Segmentation

We further investigate the effectiveness of our BOAT for semantic segmentation
on the ADE20K dataset [Zhou et al.(2017)Zhou, Zhao, Puig, Fidler, Barriuso,
and Torralba]. Here, we employ UperNet [Xiao et al.(2018)Xiao, Liu, Zhou,
Jiang, and Sun] as the basic framework. For a fair comparison, we follow
previous work and train UperNet 160K iterations with batch size $16$ using $8$
GPUs. In Table 5, we compare the semantic segmentation performance of our BOAT
with other vision Transformer models including Swin [Liu et al.(2021)Liu, Lin,
Cao, Hu, Wei, Zhang, Lin, and Guo], Twins [Chu et al.(2021)Chu, Tian, Wang,
Zhang, Ren, Wei, Xia, and Shen], Shuffle Transformer [Huang et al.(2021)Huang,
Ben, Luo, Cheng, Yu, and Fu], Focal Transformer [Yang et al.(2021)Yang, Li,
Zhang, Dai, Xiao, Yuan, and Gao], and CSWin [Dong et al.(2022)Dong, Bao, Chen,
Zhang, Yu, Yuan, Chen, and Guo]. As shown in the table, with a slight increase
in the number of parameters and FLOPs, our BOAT-Swin model consistently
improves the semantic segmentation performance of the Swin model under the
tiny, small and base settings. Meantime, our BOAT-CSWin also constantly
obtains higher segmentation mIoUs than the CSWin model under the tiny, small
and base settings.

Method | #para.(M) | FLOPs(G) |  mIoU($\%$) | Method | #para.(M) | FLOPs(G) |  mIoU($\%$)
---|---|---|---|---|---|---|---
TwinsP-S [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] | 55 | 919 | 46.2 |  Twins-S [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] | 54 | 901 | 46.2
Shuffle-T [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] | 60 | 949 | 46.6 |  Focal-T [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] | 62 | 998 | 45.8
Swin-T [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] | 60 | 945 | 44.5 | BOAT-Swin-T (ours) | 62 | 986 | 46.0
CSWin-T [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] | 60 | 959 | 49.3 | BOAT-CSWin-T (ours) | 64 | 1012 | 50.5
TwinsP-B [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] | 74 | 977 | 47.1 |  Twins-B [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] | 89 | 1020 | 47.7
Shuffle-S [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] | 81 | 1044 | 48.4 |  Focal-S [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] | 85 | 1130 | 48.0
Swin-S [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] | 81 | 1038 | 47.6 | BOAT-Swin-S (ours) | 87 | 1113 | 48.4
CSWin-S [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] | 65 | 1027 | 50.0 | BOAT-CSWin-S (ours) | 70 | 1101 | 50.6
TwinsP-L [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] | 92 | 1041 | 48.6 |  Twins-L [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] | 133 | 1164 | 48.8
Shuffle-B [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] | 121 | 1196 | 49.0 |  Focal-B [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] | 126 | 1354 | 49.0
Swin-B [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] | 121 | 1188 | 48.1 | BOAT-Swin-B (ours) | 131 | 1299 | 48.7
CSWin-B [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] | 109 | 1222 | 50.8 | BOAT-CSWin-B (ours) | 121 | 1349 | 50.9

Table 5: Performance of semantic segmentation on ADE20K. FLOPs are obtained at
$512\times 2048$ resolution. mIoU is for the single-scale setting. Testing
image size is $512\times 512$.

###  4.3 Object Detection

We also evaluate the proposed BOAT on object detection. Experiments are
conducted on the MS-COCO dataset using the Mask R-CNN [He et al.(2017)He,
Gkioxari, Dollár, and Girshick] framework. Since CSWin has not released codes
for object detection, we only implement BOAT-Swin for this task. We adopt the
$3\times$ learning rate schedule, which is the same as Swin. We compare the
performance of our BOAT-Swin and the original Swin in Table 6. The evaluation
is on the MSCOCO val2017 split. Since Swin only reports the performance of
Swin-Tiny and Swin-Small models when using the Mask R-CNN framework, we also
report the performance of our BOAT-Swin-Tiny and BOAT-Swin-Small only. As
shown in Table 6, with a slight increase in the number of parameters and
FLOPs, our BOAT-Swin consistently outperforms the original Swin.

Method | #para.(M) | FLOPs(G) |  mAPBox |  mAPMask
---|---|---|---|---
Swin-T | 48 | 267 | 46.0 | 41.6
BOAT-Swin-T (ours) | 50 | 306 | 47.5 | 42.8
Swin-S | 69 | 359 | 48.5 | 43.3
BOAT-Swin-S (ours) | 75 | 431 | 49.0 | 43.8
Table 6: Performance of object detection on the MS-COCO dataset. FLOPs are
obtained at $800\times 1280$ resolution.

##  5 Conclusion

In this paper, we have presented a new Vision Transformer architecture named
Bilateral lOcal Attention Transformer (BOAT), which performs multi-head local
self-attention in both feature and image spaces. To compute feature-space
local attention, we propose a hierarchical balanced clustering approach to
group patches into multiple evenly sized clusters, and self-attention is
computed within each cluster. We have applied BOAT to multiple computer vision
tasks including image classification, semantic segmentation and object
detection. Our systematic experiments on several benchmark datasets have
demonstrated that BOAT can clearly and consistently improve the performance of
existing image-space local attention vision Transformers, including Swin [Liu
et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] and CSWin [Dong et
al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo], on these tasks.

## References

  * [Beltagy et al.(2020)Beltagy, Peters, and Cohan] Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_ , 2020.
  * [Charikar(2002)] Moses S Charikar.  Similarity estimation techniques from rounding algorithms.  In _Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing (STOC)_ , pages 380–388, Montreal, Canada, 2002.
  * [Chen et al.(2021)Chen, Yu, and Li] Shuo Chen, Tan Yu, and Ping Li.  MVT: multi-view vision transformer for 3D object recognition.  In _Proceedings of the 32nd British Machine Vision Conference 2021 (BMVC)_ , page 349, Online, 2021.
  * [Chen et al.(2022)Chen, Yu, and Li] Shuo Chen, Tan Yu, and Ping Li.  R2-MLP: Round-roll MLP architecture for multi-view 3D object recognition.  _Technical Report_ , 2022.
  * [Child et al.(2019)Child, Gray, Radford, and Sutskever] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever.  Generating long sequences with sparse transformers.  _arXiv preprint arXiv:1904.10509_ , 2019.
  * [Chu et al.(2021)Chu, Tian, Wang, Zhang, Ren, Wei, Xia, and Shen] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen.  Twins: Revisiting the design of spatial attention in vision transformers.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 9355–9366, virtual, 2021.
  * [Deng et al.(2009)Deng, Dong, Socher, Li, Li, and Li] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li.  ImageNet: A large-scale hierarchical image database.  In _Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 248–255, Miami, FL, 2009.
  * [Dong et al.(2022)Dong, Bao, Chen, Zhang, Yu, Yuan, Chen, and Guo] Xiaoyi Dong, Jianmin Bao, Dongdong Chen, Weiming Zhang, Nenghai Yu, Lu Yuan, Dong Chen, and Baining Guo.  CSWin transformer: A general vision transformer backbone with cross-shaped windows.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 12114–12124, New Orleans, LA, 2022.
  * [Dosovitskiy et al.(2021)Dosovitskiy, Beyer, Kolesnikov, Weissenborn, Zhai, Unterthiner, Dehghani, Minderer, Heigold, Gelly, Uszkoreit, and Houlsby] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _Proceedings of the 9th International Conference on Learning Representations (ICLR)_ , Virtual Event, Austria, 2021.
  * [Han et al.(2021)Han, Xiao, Wu, Guo, Xu, and Wang] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang.  Transformer in transformer.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 15908–15919, virtual, 2021.
  * [He et al.(2016)He, Zhang, Ren, and Sun] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, Las Vegas, NV, 2016.
  * [He et al.(2017)He, Gkioxari, Dollár, and Girshick] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick.  Mask R-CNN.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , pages 2980–2988, Venice, Italy, 2017.
  * [Heo et al.(2021)Heo, Yun, Han, Chun, Choe, and Oh] Byeongho Heo, Sangdoo Yun, Dongyoon Han, Sanghyuk Chun, Junsuk Choe, and Seong Joon Oh.  Rethinking spatial dimensions of vision transformers.  In _Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 11916–11925, Montreal, Canada, 2021.
  * [Huang et al.(2021)Huang, Ben, Luo, Cheng, Yu, and Fu] Zilong Huang, Youcheng Ben, Guozhong Luo, Pei Cheng, Gang Yu, and Bin Fu.  Shuffle transformer: Rethinking spatial shuffle for vision transformer.  _arXiv preprint arXiv:2106.03650_ , 2021.
  * [Kitaev et al.(2020)Kitaev, Kaiser, and Levskaya] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  In _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , Addis Ababa, Ethiopia, 2020.
  * [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 1097–1105, Lake Tahoe, CA, 2012.
  * [Li(2019)] Ping Li.  Sign-full random projections.  In _Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI)_ , pages 4205–4212, Honolulu, HI, 2019.
  * [Liu et al.(2021)Liu, Lin, Cao, Hu, Wei, Zhang, Lin, and Guo] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 9992–10002, Montreal, Canada, 2021.
  * [Parmar et al.(2018)Parmar, Vaswani, Uszkoreit, Kaiser, Shazeer, Ku, and Tran] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran.  Image transformer.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , pages 4052–4061, Stockholmsmässan, Stockholm, Sweden, 2018.
  * [Qiu et al.(2020)Qiu, Ma, Levy, Yih, Wang, and Tang] Jiezhong Qiu, Hao Ma, Omer Levy, Wen-tau Yih, Sinong Wang, and Jie Tang.  Blockwise self-attention for long document understanding.  In _Findings of the Association for Computational Linguistics (EMNLP Findings)_ , pages 2555–2565, Online Event, 2020.
  * [Radosavovic et al.(2020)Radosavovic, Kosaraju, Girshick, He, and Dollár] Ilija Radosavovic, Raj Prateek Kosaraju, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Designing network design spaces.  In _Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 10425–10433, Seattle, WA, 2020\.
  * [Roy et al.(2021)Roy, Saffar, Vaswani, and Grangier] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier.  Efficient content-based sparse attention with routing transformers.  _Trans. Assoc. Comput. Linguistics_ , 9:53–68, 2021.
  * [Tay et al.(2020a)Tay, Bahri, Yang, Metzler, and Juan] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan.  Sparse sinkhorn attention.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 9438–9447, Virtual Event, 2020a.
  * [Tay et al.(2020b)Tay, Dehghani, Bahri, and Metzler] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.  Efficient transformers: A survey.  _arXiv preprint arXiv:2009.06732_ , 2020b.
  * [Touvron et al.(2021)Touvron, Cord, Douze, Massa, Sablayrolles, and Jégou] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , pages 10347–10357, Virtual Event, 2021.
  * [Vaswani et al.(2017)Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser, and Polosukhin] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 5998–6008, Long Beach, CA, 2017.
  * [Wang et al.(2021a)Wang, Xie, Li, Fan, Song, Liang, Lu, Luo, and Shao] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  PVTv2: Improved baselines with pyramid vision transformer.  _arXiv preprint arXiv:2106.13797_ , 2021a.
  * [Wang et al.(2021b)Wang, Xie, Li, Fan, Song, Liang, Lu, Luo, and Shao] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In _Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 548–558, Montreal, Canada, 2021b.
  * [Wang et al.(2021c)Wang, Yao, Chen, Lin, Cai, He, and Liu] Wenxiao Wang, Lu Yao, Long Chen, Binbin Lin, Deng Cai, Xiaofei He, and Wei Liu.  Crossformer: A versatile vision transformer hinging on cross-scale attention.  _arXiv preprint arXiv:2108.00154_ , 2021c.
  * [Xiao et al.(2018)Xiao, Liu, Zhou, Jiang, and Sun] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun.  Unified perceptual parsing for scene understanding.  In _Proceedings of the 15th European Conference on Computer Vision (ECCV), Part V_ , pages 432–448, Munich, Germany, 2018.
  * [Yang et al.(2021)Yang, Li, Zhang, Dai, Xiao, Yuan, and Gao] Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao.  Focal attention for long-range interactions in vision transformers.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 30008–30022, virtual, 2021.
  * [Yu and Li(2022)] Tan Yu and Ping Li.  Degenerate Swin to win: Plain window-based transformer without sophisticated operations.  _Technical Report_ , 2022.
  * [Yu et al.(2021a)Yu, Li, Cai, Sun, and Li] Tan Yu, Xu Li, Yunfeng Cai, Mingming Sun, and Ping Li.  Rethinking token-mixing MLP for mlp-based vision backbone.  In _Proceedings of the 32nd British Machine Vision Conference (BMVC)_ , page 139, Online, 2021a.
  * [Yu et al.(2021b)Yu, Li, Cai, Sun, and Li] Tan Yu, Xu Li, Yunfeng Cai, Mingming Sun, and Ping Li.  S2-MLPv2: Improved spatial-shift mlp architecture for vision.  _arXiv preprint arXiv:2108.01072_ , 2021b.
  * [Yu et al.(2022)Yu, Li, Cai, Sun, and Li] Tan Yu, Xu Li, Yunfeng Cai, Mingming Sun, and Ping Li.  S${}^{\mbox{2}}$-MLP: Spatial-shift MLP architecture for vision.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , pages 3615–3624, Waikoloa, HI, 2022\.
  * [Yuan et al.(2021)Yuan, Chen, Wang, Yu, Shi, Jiang, Tay, Feng, and Yan] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zihang Jiang, Francis E. H. Tay, Jiashi Feng, and Shuicheng Yan.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  In _Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 538–547, Montreal, Canada, 2021.
  * [Zhang et al.(2022)Zhang, Zhang, Zhao, Chen, Arik, and Pfister] Zizhao Zhang, Han Zhang, Long Zhao, Ting Chen, Sercan Ö. Arik, and Tomas Pfister.  Nested hierarchical transformer: Towards accurate, data-efficient and interpretable visual understanding.  In _Proceedings of the thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI)_ , pages 3417–3425, Virtual Event, 2022.
  * [Zhou et al.(2017)Zhou, Zhao, Puig, Fidler, Barriuso, and Torralba] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ADE20K dataset.  In _Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 5122–5130, Honolulu, HI, 2017.


# FuzzSplore: Visualizing Feedback-Driven Fuzzing Techniques

Andrea Fioraldi  Sapienza University, Rome, Italy
{fioraldi.1692419<EMAIL_ADDRESS>Luigi Paolo Pileggi
Sapienza University, Rome, Italy
{fioraldi.1692419<EMAIL_ADDRESS>
###### Abstract

Fuzz Testing techniques are the state of the art in software testing for
security issues nowadays. Their great effectiveness attracted the attention of
researchers and hackers and involved them in developing a lot of new
techniques to improve Fuzz Testing. The evaluation and the cross-comparison of
these techniques is an almost open problem. In this paper, we propose a human-
driven approach to this problem based on information visualization. We
developed a prototype upon the AFL++ fuzzing framework, FuzzSplore, that an
analyst can use to get useful insights about different fuzzing configurations
applied to a specific target in order to choose or tune the best technique
during a fuzzing campaign.

Figure 1: Complete view of the FuzzSplore visual panel.

##  1 Introduction

Fuzz Testing or Fuzzing is a family of techniques to automatically uncovers
bugs in software.

Due to its effectiveness, much more efficient than other software testing
techniques like Symbolic Execution [1] [2], the research in this field is
flourishing and several different techniques were developed to improve fuzz
testing, both from academia and industry.

The evaluation and the comparison of these techniques, however, is a debatable
matter [3].

A common proxy is the comparison of the code coverage reached over time by
each fuzzer, due to the fact that a fuzzer cannot find a bug if it does not
explore at least the vulnerable code segment. Another widely used metric is
found bugs over time, but a bug can be found just thanks to randomism or by
specific target-dependant actions taken by the fuzzer and this makes the
evaluations very prone to overfitting.

The data collected using these metrics are often representable using a simple
time-based graph that shows the evolution of the fuzzing algorithm.

This approach is useful for immediate basic comparison between two or more
techniques, an analyst has to just see which technique reaches more coverage
in less time but does not reveal the properties of a fuzzer regards specific
types of program states.

For instance, a technique can be better than another in exploring some types
of program states and at the same time reaching less code coverage. The
technique will not cover the bugs in the unexplored code of course, but it may
uncover bugs in the program points that it can better explore. An example of
such technique is the directed fuzzer towards sanitizers violations by
Österlund et al. [4].

The problem of the evaluation of fuzzing techniques is important not only when
the aim is to generally states which fuzzer is best, but also when an analyst
wants to select the best fuzzers for a single target. It is common that
fuzzers that are considered generally better than others on some targets
perform worst than the others [5].

We propose FuzzSplore, a tool that allows an analyst to manually explore the
evolution of different fuzzing techniques regards a single target program.

The main insight that a user can get using the tool are:

  1. 1.

The ability of a fuzzer to generate clusters of inputs that are correlated in
terms of covered program points;

  2. 2.

The ability of a fuzzer in generating diversified inputs with its mutational
algorithm;

  3. 3.

The ability of a fuzzer to reach program points exploring intermediate inputs
that are not an improvement in terms of coverage [6].

These insights can drive the user to choose the best technique to use for the
selected program under test (PUT).

##  2 Background

The simplest description of Feedback-driven Fuzzing is an algorithm that
provides apparently random data to a computer program and then it watches for
crashes or unexpected states and also saves the generated input for later
processing if they cover interesting new states in terms of the chosen
feedback [7].

Typically, the property of the program used as feedback is the set of the
edges in the program Control Flow Graph [8] in what is the so-called Coverage-
guided Fuzzing (CGF).

The inputs are mutations of previously saved inputs in the fuzzing loop in
Mutational Fuzzing (Figure 2) or generated from scratch from a model in
Generational Fuzzing.

We base our implementation on AFL++ [5], a widely used fuzzer in recent times,
that is a Mutational Coverage Guided Fuzzer.

Figure 2: Basic representation of the Mutational Coverage Guided Fuzzing
algorithm

State of the art Coverage-Guided Fuzzers encodes the approximate executed path
in a representation that is easy and fast to process. AFL++ uses a vector of
65536 entries by default, the hitcounts vector.

Each coordinate is associated with an edge and each value represents how many
times the edge is executed modulo 256.

When a value greater than the previous one is registered in this vector, the
fuzzer considers the input interesting and saves it.

Some extensions of CGF save also intermediate inputs that are a superset of
the coverage reported in the hitcounts vector, like [9] [10] [6].

In general, when an input is saved, we can associate it to the testcases that
generated it by mutation, the parent testcases. In this way, is easy to
construct a graph of generated inputs that represents the progress of the
hill-climbing algorithm of the fuzzer, the Generations Graph.

##  3 Methodology

A fuzzing campaign is the process of running one or more fuzzers for a long
period of time or even continuously like in OSS-Fuzz [11].

Security researchers typically start fuzzing using naive configurations and
off-the-shelf fuzzers, then, meanwhile, the campaign runs, observe the
evolution and tune the fuzzers.

Our proposed approach aims to insert in the observation-tuning feedback loop a
visual component to help the researcher better understand insights about the
fuzzers testing a particular target.

The data processed by FuzzSplore comes from the execution of the corpus of
testcases that each fuzzer saved so far. The execution is instrumented and
various properties are observed.

Then we visualize these collected properties and the user can relate them to
better understand what is going. After that, the user can choose to drop some
fuzzers if less effective and assign more resources (typically CPUs) to the
most effective fuzzers or tune each individual fuzzer.

The fuzzing campaign can then continue. When it saturates, the analyst can
collect insights using our tool and restart the visual analytics feedback-
loop.

Saturation of fuzzers, when no more additional state is explored or the number
of states explodes, is a problem that was rarely addressed in academic
literature but that affects each type of Feedback-driven Fuzzer [12], and a
tool that can guide towards the selection of techniques that avoid saturation
can help a lot the campaign.

###  3.1 Data Retrieval

We denote each fuzzer $F_{i}$ where $i$ is the index that identifies it. With
$PUT_{i}$ we denote the version of the PUT preprocessed and instrumented in
order to be used by $F_{i}$. $PUT_{e}$ is the version of the PUT that logs the
edge coverage using the hitcounts vector. It has to be provided independently
if it is used or not by some fuzzer $F_{i}$. With $T_{i}(t)$ we denote the set
of the saved testcases, the queue, by $F_{i}$ until time $t$ (seconds).

Given $t$ as the time chosen by the user to observe the progress of the
fuzzers, the Algorithm 1 computes the following sets:

  * •

the set $C$ of all the functions $C_{i}\colon Time\longrightarrow NumEdges$
that relates, for the fuzzer $F_{i}$, a time unit to the number of discovered
edges so far;

  * •

the set $I$ of all the functions $I_{i}\colon
Testcase\longrightarrow\\{F_{j},...\\}$ that associates, for the fuzzer
$F_{i}$, each testcase in $T_{i}(t)$ to the set of fuzzers that consider the
testcase as interesting;

  * •

the set $X$ of the sets $X_{i}$, that maintains, for each fuzzer, the
hitcounts vectors associated with the execution of each testcase in
$T_{i}(t)$;

for  _$F_{i}$ in  $Fuzzers$_ do

$V_{acc}\leftarrow(0_{0}...0_{65536})$

for  _$T$ in  $T_{i}(t)$_ do

$V\leftarrow Execute(PUT_{e},T)$

$X_{i}\leftarrow X_{i}\cup\\{V\\}$

$V,IsInteresting\leftarrow MergeCoverage(V_{acc},V)$

if  _$IsInteresting$_ then

$C_{i}(Time(T))\leftarrow CountNotZeros(V_{i})$

for  _$F_{j}$ in  $Fuzzers\setminus F_{i}$_ do

$V_{acc}\leftarrow(0_{0}...0_{65536})$

for  _$T$ in  $T_{i}(t)$_ do

$V\leftarrow Execute(PUT_{j},T)$

$V_{acc},IsInteresting\leftarrow MergeCoverage(V_{acc},V)$

if  _$IsInteresting$_ then

$I_{i}(T)\leftarrow I_{i}(T)\cup\\{F_{j}\\}$

return _$C,I,X$_

Algorithm 1 Compute $C$, $I$, and $X$

The next item that has to be retrieved, in addition to $C$, $I$ and $X$, is
the set $G$ of all the graphs $G_{i}$ that describes the evolution of each
$T_{i}(t)$, the levels graph introduced in Sec. 2.

We assume that each fuzzer encodes the information about the parent testcases
into the metadata of each testcase. In this way, it is trivial to construct
the graph just by reading all the metadata in $T_{i}(t)$.

###  3.2 Visualization

We visualize the computed data $C$, $I$, $X$, $G$, and some other properties
that can be directly collected in four different views.

You can see these views with some example data in the screenshot of our
implementation, in Figure 1.

A time bar is used to select $t^{\prime}\in[0,t]$ to ignore data outside the
selected time range and, for instance, visualize the data related to the queue
$T_{I}(t^{\prime})$ without the need to run again Algorithm 1.

####  3.2.1 Testcases Scatterplot

Each $X_{i}$ is a matric of $|T_{i}(t)|$ rows in which each row is a vector of
65536 entries.

These raw numbers are raw to visualize. To handle this problem, we reduce the
dimensionality of each vector $X_{i,j}$ from 65536 to 2, in order to be easily
visualized in a scatterplot.

To do that, we chosen an algorithm that optimizes the conservation of local
distances after the dimensionality reduction, t-SNE [13]. The nature of this
algorithm is random, it needs to process $X$ entirely in order to get new
vectors that are meaningfully comparable.

We experimentally observed on a test dataset that a perplexity of 30 is good
enough.

The user can select groups of nodes interactively to highlight properties in
the other visualizations.

####  3.2.2 Coverage Growth Plot

$C$ can be visualized simply using a line plot with the X axis representing
the domain, the time, and the Y axis the number of edges.

When a testcase is selected in the scatterplot or in the generations graph a
vertical line appears at position $x$ where $x$ is the time in which the
testcase was discovered.

####  3.2.3 Interesting Testcases Plot

This plot is used to visualize the evolution of the fuzzing algorithm in
finding new testcases. The X axis represents time in seconds, the Y axis the
number of new interesting testcases saved by the fuzzer in that second. This
information is directly contained in $T_{i}(t)$.

Here too, when a testcase is selected in the scatterplot or in the generations
graph a vertical line appears at position $x$ where $x$ is the time in which
the testcase was discovered.

####  3.2.4 Generations Graph

We visualize each Generations Graph $G_{i}$ combined with $I$. Given a fuzzer
$F_{j}$ from the user, we highlight in graph $G_{i}$ each node associated with
each testcase $T$ if $F_{j}\in I_{i}(T)$. In this way, the user can know if
the evolution of $T_{i}(t)$ associated with the fuzzer $F_{i}$ is compatible
with the selected $F_{j}$.

When a testcase is selected in the scatterplot, the border of the
corresponding node in the graph is highlighted. The user can select additional
nodes or deselect nodes selected from the scatterplot. The scatterplot
selection is synchronized in both ways with the graph.

###  3.3 Analyst Feedback

The insights that an analyst can retrieve in order to choose or tune the
fuzzers using the visualization are, but not limited to, the following:

  * •

Looking just at the scatterplot, the user can select a subset of fuzzers that
explore different program points if the points related to each fuzzer in the
graphs are clustered;

  * •

Looking at the scatterplot and the coverage graph, the user can select a
cluster of testcases that are similar and see the ability of a fuzzer in
generating similar testcases in a small range of time. A fuzzer that discovers
few points at a time and have them distributed for all the X axis of the
coverage plot should be deprioritized;

  * •

Looking at the coverage graph, when there is a huge increment of the number of
edges, the user can see if an outlier in the scatterplot was generated. This
allows to isolate interesting testcases that improves a lot the coverage;

  * •

Selecting testcases in the graph, the user can see if the testcases are
similar in the scatterplot in order to understand the ability of the mutator
to generate similar or different derived inputs;

  * •

Selecting testcases in the graph and a fuzzer to cross-compare, the user can
know if the coverage metric of the other fuzzer is sensitive enough to cover
the selected testcases.

With this information, the security researcher should be able to choose and
tune the set of fuzzers to avoid the saturation of the fuzzing campaign. This
methodology is a first step towards a fuzzers debugger that is highly demanded
by the security research community.

##  4 Implementation

We created an html page comprised of 4 views and a filtering panel and all the
components were created using the D3.js library.

###  4.1 Testcases Scatterplot

The scatterplot (Fig. 3) has, as both axes, a linear scale where the points
are color-coded to represent a category to help the analyst distinguish the
similarity in the clusters highlighted and the presence of outliers.

By brushing over the scatterplot a routine is called to update the other 3
views with the highlighted elements by selecting the corresponding nodes in
the Generation graph and inserting lines in both plots.

The user can also zoom in and out and both axes are scaled appropriately.

Figure 3: Testcases scatterplot

###  4.2 Coverage Growth and Interesting Testcases Plots

The Coverage graph (Fig. 5) plots the growth over time of the number of
covered edges, the Interesting Testcase graph (Fig. 5) plots the number of new
interesting test cases over time instead, for both the bottom axis is
implemented as a linear scale, for the first graph the left axis is
implemented as a logarithmic scale, for the latter a linear scale is used
instead.

When data is selected on the scatterplot or graph vertical lines appear in
both plots at the corresponding time having the stroke color matching the
fuzzing technique.

We also implemented a pan and zoom functionality that keeps the lowest value
pinned at the bottom.

Figure 4: Coverage growth plot

Figure 5: Interesting Testcases plot

###  4.3 Generation Graph

The Generation Graph (Fig. 6) is created as a hierarchical layout where each
data point’s value is displayed as a node label.

The user can zoom as well as pan over the entire view to have a better
understanding of the data and when a node is selected in the other a routine
is called to highlights the corresponding points in the scatterplot and insert
lines in the other plots. A mouseover on node lowlights all the nodes except
the hovered nodes and their neighbor nodes and edges.

Figure 6: Generation graph

###  4.4 Filtering Panel

The user can filter the data shown an all the 4 views by time, with a range
slider (Fig. 7) located at the bottom right of the page, and by category, by
clicking on the category names directly on top of the slider, the filtering
works by updating the existing graphs without redrawing.

Figure 7: Filtering panel

##  5 Concluding Remarks

FuzzSplore brings a useful visualization-based method to retrieve insights
from running fuzzers in a campaign.

It defines a long-term visual analytics feedback loop applied to fuzzing with
a set of data retrieval and visualization techniques that can be easily
extended in future works.

The information that a security researcher can collect using our approach can
help in understanding the problem of saturation in fuzzing campaigns, a widely
spread problem that is rarely addressed in academic literature.

We share FuzzSplore as Free and Open Source Software at
https://github.com/andreafioraldi/FuzzSplore.

## References

  * [1] C. Aschermann, S. Schumilo, T. Blazytko, R. Gawlik, and T. Holz, “REDQUEEN: fuzzing with input-to-state correspondence,” in _26th Annual Network and Distributed System Security Symposium, NDSS_ , 2019. [Online]. Available: https://www.ndss-symposium.org/ndss-paper/redqueen-fuzzing-with-input-to-state-correspondence/
  * [2] S. Poeplau and A. Francillon, “Systematic comparison of symbolic execution systems: Intermediate representation and its generation,” in _Proceedings of the 35th Annual Computer Security Applications Conference_ , ser. ACSAC ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 163–176. [Online]. Available: https://doi.org/10.1145/3359789.3359796
  * [3] G. Klees, A. Ruef, B. Cooper, S. Wei, and M. Hicks, “Evaluating fuzz testing,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 2123–2138. [Online]. Available: https://doi.org/10.1145/3243734.3243804
  * [4] S. Österlund, K. Razavi, H. Bos, and C. Giuffrida, “ParmeSan: Sanitizer-guided Greybox Fuzzing,” in _USENIX Security_ , Aug. 2020\. [Online]. Available: Paper=https://download.vusec.net/papers/parmesan_sec20.pdfCode=https://github.com/vusec/parmesan
  * [5] A. Fioraldi, D. Maier, H. Eißfeldt, and M. Heuse, “Afl++ : Combining incremental steps of fuzzing research,” in _14th USENIX Workshop on Offensive Technologies (WOOT 20)_. USENIX Association, Aug. 2020. [Online]. Available: https://www.usenix.org/conference/woot20/presentation/fioraldi
  * [6] J. Wang, Y. Duan, W. Song, H. Yin, and C. Song, “Be sensitive and collaborative: Analyzing impact of coverage metrics in greybox fuzzing,” in _22nd International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2019)_. Chaoyang District, Beijing: USENIX Association, Sep. 2019, pp. 1–15. [Online]. Available: https://www.usenix.org/conference/raid2019/presentation/wang
  * [7] A. Zeller, R. Gopinath, M. Böhme, G. Fraser, and C. Holler, “The Fuzzing Book,” https://www.fuzzingbook.org/, 2019, [Online; accessed 10-Sep-2019].
  * [8] K. Cooper and L. Torczon, _Engineering a Compiler: International Student Edition_. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2003.
  * [9] “Circumventing Fuzzing Roadblocks with Compiler Transformations,” https://lafintel.wordpress.com/2016/08/15/circumventing-fuzzing-roadblocks-with-compiler-transformations/, 2016\.
  * [10] C. Aschermann, S. Schumilo, A. Abbasi, and T. Holz, “Ijon: Exploring deep state spaces via fuzzing,” in _IEEE Symposium on Security and Privacy (Oakland)_ , 2020.
  * [11] K. Serebryany, “Oss-fuzz-google’s continuous fuzzing service for open source software,” in _USENIX Security Symposium_ , 2017.
  * [12] A. Groce and J. Regehr, “The Saturation Effect in Fuzzing,” https://blog.regehr.org/archives/1796.
  * [13] L. v. d. Maaten and G. Hinton, “Visualizing data using t-sne,” _Journal of machine learning research_ , vol. 9, no. Nov, pp. 2579–2605, 2008.