# Wasmizer: Curating WebAssembly-driven Projects on GitHub

Alexander Nicholson  University of Auckland
New Zealand  Quentin Stiévenart  Université du Québec à Montréal
Canada  Arash Mazidi  TU Clausthal
Germany  Mohammad Ghafari  TU Clausthal
Germany

###### Abstract

WebAssembly has attracted great attention as a portable compilation target for
programming languages. To facilitate in-depth studies about this technology,
we have deployed Wasmizer, a tool that regularly mines GitHub projects and
makes an up-to-date dataset of WebAssembly sources and their binaries publicly
available. Presently, we have collected 2 540 C and C++ projects that are
highly-related to WebAssembly, and built a dataset of 8 915 binaries that are
linked to their source projects. To demonstrate an application of this
dataset, we have investigated the presence of eight WebAssembly compilation
smells in the wild.

###### Index Terms:

WebAssembly, dataset, compilation smells

##  I Introduction

WebAssembly is a standard for portable binary code that aims to bring a safer,
faster, and more portable format than JavaScript to the web. It allows for
programs written in high-level languages such as C, C++, and Rust to be cross
compiled to WebAssembly and run in a web environment. WebAssembly is not
limited to the web though, and it can be used in a number of host
environments, e.g., it is possible to port C applications using the
WebAssembly System Interface and run them as regular desktop
applications.111https://wasi.dev/

There are several tools for analyzing WebAssembly programs [1, 2, 3, 4, 5, 6].
However, tool builders need to evaluate their tools on benchmark programs,
which are currently lacking for WebAssembly. Two datasets of WebAssembly
binaries exist [7, 8], but they only include the binary files without the
source files of the programs. Linking a WebAssembly binary to the source code
that produced it is of high value for developers of such tools, enabling them
to understand the inner workings of these programs, or for example to
instrument programs during their compilation. To fill this gap, we present a
methodology for identifying open-source C and C++ projects that target
WebAssembly for compilation, and we build a novel dataset of WebAssembly
binary files that are associated with their respective source projects. We
deploy Wasmizer, a tool that automates this process and regularly updates our
dataset.

To demonstrate an application of this dataset, we investigate _compilation
smells_ in WebAssembly, i.e., indication of potentially different behaviour
from source to target programs that may yield bugs [9]. In fact, previous work
has shown that compilers and standard library implementations available for
WebAssembly are yet not as mature as those used for native compilation, and
consequently, certain code patterns may yield different behaviour in these
platforms [9, 10]. These different behaviour may yield unexpected bugs lurking
around when porting programs to WebAssembly, and more importantly, they may
introduce security risks, for example enabling an easier exploitation of
binaries suffering from buffer overflows [10]. While previous work has shown
these different behaviours exist for programs compiled from C and C++, we take
the next step and investigate how prevalent they are in real-world projects.

The contributions of this work are centred around the following two research
questions:

  * •

RQ1: Can we mine WebAssembly-driven projects on GitHub and generate
WebAssembly binaries automatically? We present heuristics that help to
identify real-world C and C++ projects that are related to WebAssembly. We
collect 2 540 projects that target WebAssembly as a compilation target. We
build these projects that contain a makefile and generate 8 915 binaries from
572 repositories, forming a novel dataset of WebAssembly binaries linked to
their originating projects. We develop Wasmizer, an open-source tool that
automates this process.222https://github.com/arash-mazidi/WASMIZER

  * •

RQ2: How prevalent are compilation smells in open-source projects that target
WebAssembly? We present the code patterns of 16 compilation smells and
heuristics that help to identify them in C and C++ programs. We use the Clang
static analyser to develop checkers that can detect eight of such smells. We
evaluate their presence in 1 605 projects, uncovering that 386 projects (i.e.
24%) suffer from at least one compilation smell. This analysis shows a use
case of our dataset that requires access to the source code of WebAssembly
applications.

We share our dataset, tools, and code analysis scripts to allow for
replication of this work.333https://doi.org/10.5281/zenodo.7742004
Importantly, Wasmizer is deployed to regularly mine WebAssembly-driven
projects on GitHub, compile them, and curate an up-to-date dataset of
WebAssembly sources and binaries. We also share this novel and evolving
dataset to facilitate further studies in this
domain.444http://tiny.cc/WasmizerOutput, password: wasmizer

The remainder of this paper is organised as follows. In Section II, we provide
some background on model of WebAssembly. We present the datasets of source
projects and associated binaries in Section III. In Section IV, we study
compilation smells as a use case for this dataset. We discuss threats to
validity of this work in Section V. We put this work in context with the
related research on WebAssembly in Section VI, and conclude this paper in
Section VII.

##  II Background on WebAssembly

We first provide background knowledge on the compilation of programs to
WebAssembly, required for Section III, and we explain the inner workings of
WebAssembly programs, required to understand the compilation smells discussed
in Section IV. WebAssembly is a low-level language initially aimed at bringing
near-native performance for the web. It uses a stack-based execution model
that runs within a virtual machine (VM) similar to the JVM. WebAssembly
binaries, called modules, can be expressed in a binary or textual format. The
intent is to use WebAssembly as a compile target from another source language
such as C, C++, Rust C#, Go or AssemblyScript using a compiler such as
Emscripten [11]. WebAssembly modules can import and export definitions for
functions and variables. These modules can be imported into JavaScript code or
in other host environment and then instantiated. Each module runs within its
own isolated context with its own memory and execution stack.

###  II-A Compiling from C and C++ to WebAssembly

Multiple compilers have backends for compiling to WebAssembly nowadays. For C
and C++ specifically, there are two main compiler backends: Emscripten [11]
being the original WebAssembly compiler, and Cheerp compiler [12] being a
competitor with a strong focus on binary size and speed. Porting an existing C
or C++ application to WebAssembly can be as simple as wrapping their build
scripts with Emscripten’s wrappers for cmake and make. However, the use of
libraries and graphical toolkits can render porting applications more
challenging.

###  II-B Memory Model

The memory of a WebAssembly program is a linear array of bytes, called linear
memory. When a module is instantiated, the memory is created with an initial
size, however this can grow dynamically as needed. Addresses in linear memory
are represented as an offset from the start of linear memory. Due to this,
many common memory protection techniques such as data execution prevention and
stack smashing protection are no longer needed. While this is good for the
security of the host (the browser), it then falls on the developer to ensure
that the code accessing this memory is bug-free, as anomalies such as buffer
overflows will not be checked as long as they remain within the bounds of the
linear memory. By isolating the memory used by each module, many independent
instances can exist with their own memory within the same process.

###  II-C Control flow

Unlike native code, WebAssembly only allows for structured control flow, which
provides a few advantages. Firstly, it means that it is not possible to jump
to arbitrary addresses, which eliminates the possibility for attacks that
manipulate the control flow of the program. Instructions are placed in
functions which are organised into blocks, where branches may only jump to the
end of other blocks inside the current function. This control flow also allows
for WebAssembly code to be validated, compiled, or transformed with only a
single pass over the program.

##  III Dataset Construction

We collect real-world WebAssembly projects that compile to WebAssembly. We
explain our methodology and the obtained results in this section.

###  III-A Methodology

We use GitHub as our data source for identifying WebAssembly projects.

####  III-A1 Initial project selection

We query the GitHub Search API to find C and C++ projects that include a few
WebAssembly-related keywords.555https://docs.github.com/en/rest/search

####  III-A2 NLP Filtering

We apply Natural Language Processing (NLP) tools to remove projects for which
WebAssembly is not an important word in the repositories’ READMEs and
description.

####  III-A3 Heuristic Development

We study a number of known projects that compile to WebAssembly to familiarise
ourselves with how WebAssembly compilers work, and to find possible ways to
use WebAssembly in C/C++ projects. We develop initial heuristics based on our
observations to find specific indicators of projects that target WebAssembly.
We apply these heuristics to the projects that pass the NLP filter, and
manually inspect a subset of excluded projects to expand our heuristics that
eliminate projects that likely do not target WebAssembly for compilation.

####  III-A4 Building Dataset

We obtain a first dataset of real-world projects that likely compile to
WebAssembly. We clone each repository locally. The projects are written in C
or C++, for which there is no standard build mechanism to rely on in order to
build all projects. Through a manual inspection, we notice that many projects
rely either on makefiles, or on cmake. Therefore, for each project:

  * •

For each CMakeLists.txt file, indicating the use of the cmake build system, we
run Emscripten’s cmake wrapper (emcmake).

  * •

For each Makefile, either resulting from the previous step, or standalone, we
run Emscripten’s make wrapper (emmake).

We rely on Emscripten version 3.1.26, the latest at the time of writing. We
leave trying out other compilers and build script mechanisms for future work.

After applying this compilation step to all projects, we look for files that
are named with either a .wasm or a .wat extension, indicating that they are
WebAssembly files. We try to convert all .wat files found into their binary
version (.wasm) relying on the wat2wasm tool (version 1.0.31, the latest at
the time of writing) from the WebAssembly Binary
Toolkit,666https://github.com/WebAssembly/wabt configured with the \--enable-
all flag to enable all available WebAssembly extensions. We then store all
.wasm files in a new directory, under a name composed of the SHA-256 sum of
their content. This is to ensure that duplicate files are only present once in
the dataset.

###  III-B Results

####  III-B1 Initial Projects

We use the GitHub search API to search for projects that include keywords
listed in Table I. We search in the repository’s title, description, README,
or topics (keywords that can be added to a project). We exclude forks as well
as any project that is not updated since the official release of WebAssembly
specification (December 2019). We search projects refining by date periods
that span over less than 1000 projects in order to overcome GitHub’s limit of
1000 projects per query. To account for GitHub’s query rate limit, we wait for
20 seconds between two requests. We gather a total of 6 095 projects that list
C or C++ as their source language.

TABLE I: Wasm-related keywords used for initial query. Keyword777The GitHub Search API queries are case-insensitive, so each keyword includes all differently capitalized variants. | Explanation
---|---
wasm | Abbreviation of WebAssembly
webassembly | Self-explanatory
web assembly | Mis-spelling of WebAssembly
emscripten | The most popular compiler for C/C++ to WebAssembly

####  III-B2 NLP Filtering

Projects may contain words related to WebAssembly without the aim of targeting
it for compilation. In order to eliminate unrelated projects, we use NLP tools
to estimate the importance of WebAssembly-related keywords in each project’s
README and description. If an NLP tool detects a word as important to the
text, it indicates that the project may be directly related to the term rather
than a passing word. We implement the NLP step by applying the TopicRank
algorithm, an enhanced variation of the PageRank algorithm provided by a
Python NLP library named PyTextRank [13]. The algorithm decides the ranking of
words by a “voting” or “recommendation” system. A lemma graph is produced with
vertices representing each word in the README or description of the project
selected. These vertices contain edges that represent the voting system, where
more edges mean a higher rating. Using PageRank, ranks are calculated for each
vertex and returned.

While we aim to filter our dataset, we still want to be inclusive of possible
relevant projects and ensure the NLP algorithm implementation is able to
reliably detect keywords by comparing the results to those produced by other
popular keyword extraction libraries. We therefore run TopicRank against other
popular NLP tools, namely Yake [14] and spaCy [15]. We note that TopicRank
produces similar results to the alternative tools, but also it is the most
inclusive one as it detects more keywords, with the instances of the words in
Table I being more prevalent in our results. Using the TopicRank algorithm, we
detect 4 022 projects that emphasise the keywords chosen to create our
filtered dataset.

To ensure that we are not filtering out relevant projects in this step, we
manually analyse 10% of the excluded repositories. We look for indications of
compilation to WebAssembly. Most projects have one of three traits.

  1. 1.

They are either small test projects with very few files where there would be
no instances of a README or description. These projects may compile to
WebAssembly but are of lower quality and likely to be toy projects, so it
makes sense to exclude them.

  2. 2.

There would be instances of users trying to port C libraries to run with
WebAssembly. Most of these projects are abandoned or unfinished, denoting low
quality.

  3. 3.

The projects do not compile to WebAssembly at all.

Based on this manual analysis, we determine that the NLP step indeed removes
lower-quality and unrelated projects from our dataset while keeping the
relevant projects.

####  III-B3 Heuristics for Compilation to WebAssembly

Our dataset, after NLP filtering, contains repositories that indicate they are
C or C++ projects related to WebAssembly. However, we cannot guarantee that
all the projects will compile to WebAssembly. We develop heuristics to filter
our dataset more strictly into projects that will compile to WebAssembly.

We first study projects that are mentioned as top WebAssembly projects to
learn about compiler calls and WebAssembly-related headers. These projects are
listed on LibHunt,888https://www.libhunt.com/topic/webassembly Awesome Open
Source,999https://awesomeopensource.com/projects/webassembly and on the
Emscripten Wiki page.101010https://github.com/emscripten-
core/emscripten/wiki/Porting-Examples-and-Demos We develop initial heuristics
based on what we learn from these projects and look for them within source
code from our NLP-filtered projects. Through this process, we identify 1 499
projects that would compile into WebAssembly. To verify our heuristics, we
manually analyze 141 projects undetected by our initial heuristics, and we
create refined heuristics that more strongly indicate projects that compile to
WebAssembly.

Of the 141 repositories analysed, 63 do not aim to compile to WebAssembly or
have not finished implementing this functionality. In the case where the
projects do not aim for compilation, some instead mention unimplemented
WebAssembly-related libraries: for example, the 2log.io project mentions the
QPA WASM plugin from Qt, however, it does not implement
it.111111https://github.com/2log-io/2log.io Of the case where functionality
has not been implemented yet, most of the projects aim to compile to
WebAssembly however, have it as a “todo” in their READMEs or descriptions. The
intention to compile to WebAssembly indicates that we may be able to analyse
it. However, we cannot judge whether all implementations have been complete in
their C source code and do not add them to our dataset.

Another challenge is that multiple repositories create their own custom
WebAssembly module or require the user to manually set environment variables
that are necessary for compiler calls. In our manual analysis, we could not
detect common compilation indications from their code.

Based on the projects that do target WebAssembly for compilation, we create
three general heuristics that we discuss below.

##### Reference to a WebAssembly compiler in the build script of the project

While not all repositories contain build scripts, the presence of compilation
calls to WebAssembly within this set of projects indicates that it does target
WebAssembly for compilation. We look for the presence of calls to three
WebAssembly compilers for C/C++, being emcc (Emscripten) [11], -target cheerp-
wasm (Cheerp) [12] and \--target=wasm32 (LLVM)121212While Emscripten also uses
LLVM, this refers to projects compiled with LLVM without Emscripten. [16].

##### Inclusion of WebAssembly specific libraries

We look for mention of headers for the Emscripten APIs, as these indicate that
the source code is interacting with web APIs. We focus specifically on
projects that contain #include macros to include the emscripten.h or html5.h
headers, as these have distinct names that are easy to detect, and also
provide the most commonly used core functionality.

##### Use of the JavaScript WebAssembly API

We look for instantiation of the WebAssembly class within JavaScript code in
the project. While this on its own does not indicate compilation to
WebAssembly, we found that inclusion of this code in a C/C++ project was a
good indication that it compiled to WebAssembly.

TABLE II: Manual analysis of compilation methods Category | Projects
---|---
Emscripten header undetected | 12
Does not aim to compile to WebAssembly | 31
Unfinished implementation | 32
Uses JavaScript to compile | 28
Uses C source code to compile | 9
Uses unique compiler methods | 8
Uses custom variables | 16
Undefined Wasm implementation | 5

####  III-B4 Dataset

We collect 2 540 C/C++ projects that are related to WebAssembly i.e., include
evidence that they compile to WebAssembly. In this dataset, 63% of the
projects have at least one star, 27% have at least one open issue, and 41%
have been forked at least once. The average size of a repository in our
dataset is 14MB. On average, the projects are over three years old, and of the
85% of projects that are more than a year old, 57% were still being updated a
year later. 74% of repositories list C++ as a source language, while 73% list
C as a source language. Additionally, 56% and 49% of projects contain HTML and
JavaScript respectively.

We clone and compile each WebAssembly-related project. This results in 8 915
WebAssembly binaries (.wasm files), extracted from 572
repositories.131313During the conversion from textual representation to the
binary representation, 1 384 .wat files could not be converted due to features
unsupported by wat2wasm or syntax errors. We do not count these files and
include them in a separate folder of our dataset. None of these files overlap
with the dataset of Hilbig et al. [8] built in 2020, indicating that all files
in our dataset are new benchmark programs.

We notice that many of the .wasm files are already present in the repositories
_before_ the compilation. In total, the compilation step produces 1 096 new
binary files, for 124 repositories. These binary files can be linked to their
source code. The link between C and C++ source projects and a WebAssembly
binary has not been part of any previous dataset so far [7, 8].

The distribution of the size of the binary files is represented in the left-
hand side of Figure 1. We notice a bimodal distribution, with many files of a
few bytes, and many files of around 1MB.

We find that some files are present in multiple repositories: in total, 68
files ($<$1%) are in more than one repository, most often in two repositories,
with three files being present in seven repositories. Looking at how many
WebAssembly files there are per repositories however, we notice that around
half (284) of the repositories contain one file, with the other half
containing more files. This distribution is represented in the right-hand side
of Figure 1. The most extreme case is one repository containing more 11 599
files (many of which are duplicate from each other). All but 12 repositories
contain less than 100 WebAssembly binaries.

Figure 1: Distribution of binary WebAssembly files.

###  III-C Wasmizer

We develop a tool named Wasmizer that automates the entire process from
project selection on GitHub to project compilation and WebAssembly binary
generation. Figure 2 illustrates the Wasmizer’s pipeline. Wasmizer allows for
many configurable options. It is possible to configure search parameters such
as number of stars, number of forks, minimal project size, and last push date.
The filtering step, which looks for symptoms of WebAssembly compilation is
also parametric. The compilation pipeline is dynamic too: it is possible to
change the compilation commands so that Wasmizer can curate programs written
in other languages such as Rust or Go.

Wasmizer is open source,141414https://github.com/arash-mazidi/WASMIZER and it
is deployed to regularly collect WebAssembly-driven projects on GitHub and
curate an up- to-date dataset of WebAssembly sources and binaries. In addition
to the earlier dataset that we
presented,151515https://doi.org/10.5281/zenodo.7742004 we also share the
“evolving” dataset that Wasmizer is curating as of March 10th,
2023.161616http://tiny.cc/WasmizerOutput

Figure 2: The pipeline of Wasmizer.

##  IV WebAssembly Compilation Smells in the Wild

We present a case study or our dataset by detecting the presence of
compilation smells using custom checkers. We rely on existing checkers and
develop new checkers for Clang to analyse our project dataset for occurrences
of eight compilation smells. Unlike previous work [9], which has detected
these smells on synthetic code examples, we detect the smells in real source
code. In addition, we investigate more compilation configuration flags and
present the code patterns that indicate these smells.

###  IV-A Compilation Smells

Compilation smells are indicators of execution differences that can arise
between a C program compiled to native x86 code and the same program compiled
to WebAssembly. We rely on the same dataset as the original paper [9], namely
the Juliet test suite [17], a set of test C and C++ programs that have been
designed to exercise and evaluate static application security testing (SAST)
tools. We extend the previous work by repeating the experiments with multiple
sets of compiler configuration flags. This is done to ensure that the smells
we identify are exhibited in various compiler configurations. Moreover, we
perform a manual analysis step to extract the pattern of each smell, which was
lacking in previous work. We illustrate our pipeline to identify the smells in
Figure 3.

Figure 3: The pipeline for identifying compilation smells.

The Juliet test suite is composed of test programs that each has two variants:
the _bad_ variant which contains a security issue, and the _good_ variant
which does not contain the issue. Starting from the dataset of deterministic
programs in the Juliet test suite, we compile each program to x86 and to
WebAssembly. We record their execution outcome (success or crash), as well as
their standard outputs. If any difference is encountered, we flag the program
as behaving differently when executed in WebAssembly.

Unlike previous work, we repeat this process for a number of different
compiler configurations. In particular, we investigate the following tweaks to
the default compiler configurations:171717Clang flags and their default
values: https://clang.llvm.org/docs/ClangCommandLineReference.html

  * •

The optimisation level: -O0 (no optimisation), -O1 (only some optimisations),
-O2 (moderate level of optimisations), and -Os (optimisations for code size).

  * •

Security protections: default, nonsecure (disable a set of security
protections enabled by default, and secure (enable a set of security
protections). The flags used for each of these setting are detailed in Table
III.

TABLE III: Compilation settings used in our study. Setting | Description
---|---
default | the default values provided by Clang 13.0.1
nonsecure | -D_FORTIFY_SOURCE=0 -fno-pie -no-pie -fno-stack-protector
| -fno-sanitize=safe-stack,address,undefined,cfi -fno-lto
secure (Wasm) | -D_FORTIFY_SOURCE=2 -fpie -pie -fsanitize=cfi -flto -Wl,-z,relro
| -Wl,-z-now -fvisibility=hidden
secure (x86) | -D_FORTIFY_SOURCE=2 -fpie -pie -fsanitize=cfi -flto -Wl,-z,relro
| -Wl,-z-now -fvisibility=hidden -fstack-protector
| -fsanitize=safe-stack,cfi -flto -fuse-ld=gold

Moreover, unlike previous research, we target 32-bit native code instead of
64-bit. This is to ensure better compatibility with WebAssembly, which itself
is a 32-bit architecture and therefore have different number semantics [10].

We consider 12 configurations in total :

  1. 1.

default,-O0,good,

  2. 2.

default,-O1,good,

  3. 3.

default,-O2,good,

  4. 4.

default,-Os,good,

  5. 5.

secure,-O2,good,

  6. 6.

nonsecure,-O2,good,

  7. 7.

default,-O0,bad,

  8. 8.

default,-O1,bad,

  9. 9.

default,-O2,bad,

  10. 10.

default,-Os,bad,

  11. 11.

secure,-O2,bad, and

  12. 12.

nonsecure,-O2,bad.

Each test case is used to produce 24 binaries (12 WebAssembly binaries and 12
native binaries, each one using a different set of compiler flags).

In order to understand where these differences arise from, we manually go
through each program behaving differently across multiple configurations. The
structure of the Juliet test suite is so that there are many variants of the
same programs, including control- and data-flow variants, e.g., by wrapping
the code of the program in a specific branch that will always be taken at
execution time. This allows us to reduce the set of programs to investigate
manually. The manual process includes looking at the program, hypothesizing
the reason for the different behaviour, and trying to confirm that reason
through other examples.

We refine the previous study [9] that merely described the various patterns at
a high-level. In this work, we manually minimize each program exhibiting a
difference181818We could adopt an automated approach, for example by relying
on automatic program reduction techniques such as delta debugging. However,
the size of the dataset and the programs within it enable us to reduce the
programs manually.: we remove portions of the code until no code can be
removed without exhibiting the difference. This process results in a minimal
program for each difference, which we call _compilation smell_.

We find a total of 16 root causes for the differences, i.e., smells. We
describe these smells, linking them to a CWE when relevant. We also provide
insights on how each smell can be detected by automated program analysis
tools. We distinguish between _structural_ checks that can be performed simply
by walking the AST of the program and _semantic_ checks that require a deeper
analysis of the program semantics. Each of these smells may have consequences
when porting C and C++ programs to WebAssembly: a smell is an indication of
potentially different behaviour, that itself may result in bugs (or increased
security risks) in the program [10].

##### Double Free (CWE 415)

The following excerpt allocates a memory region but frees it twice. In its
native version, this program yields a double free error (free(): double free
detected in tcache 2), but it runs successfully in WebAssembly, potentially
continuing the program’s execution while the heap memory has been corrupted.
Instead, a malloced memory region should only be freed once.

⬇ char *data =  (char *)malloc(100*sizeof(char));  free(data);  free(data);

Semantic check: track allocated and freed buffers to detect when free is
called on a buffer already freed. Already implemented in Clang as the
unix.Malloc checker.

##### Error Without Action (CWE 390)

A file is opened with the fopen function. The file is then closed, without
checking that opening the file actually succeeded. This results in an error
when executed in WebAssembly (RuntimeError: uninitialized element), but
succeeds in its native version. The WebAssembly crash is unexpected, as the
file should be created successfully after calling fopen. A closer inspection
reveals that fopen indeed fails and sets errno to ENOTUNIQ (_Name not unique
on network_), which is an unconventional error for fopen. Instead, the return
value of fopen should be checked before using the file handle.

⬇ FILE *f = fopen(”file.txt”, ”w+”);  fclose(f);

Semantic check: find calls to fclose on a file pointer that has been open with
fopen, in a branch where it could be NULL.

##### Double fclose (CWE 675)

A file is opened, and thereafter closed twice. In its native version, this
program succeeds. In its WebAssembly version, it fails: the file is not opened
successfully, resulting in the same error as we encountered in CWE 390
(ENOTUNIQ: _Name not unique on network_).

⬇ FILE *data =  freopen(”f.txt”, ”w+”, stdin);  fclose(data);  fclose(data);

Semantic check: same as for ”Error Without Action”

##### Use of Uninitialized Variable (CWE 457)

Similarly, the following program results in undefined behaviour because it
reads data from an uninitialized behaviour. The WebAssembly output is the
empty string, while the native output is the name of the program. Instead, one
should not use uninitialized variables.

⬇ char *data;  printf(”

Semantic check: find usages of variables that have not been initialized.

##### Access to Environment Variables

The following excerpt accesses the PATH environment variable.

⬇ printf(”

Structural check: find calls to getenv.

In native code, this accesses a variable that is bound on Unix-like systems.
However, in WebAssembly, the execution environment is cleared upon execution
of a program. With the platform we are using to execute the test cases, it is
required to explicitly bind these environment variables before executing this
program. In case this is not performed, the output of this excerpt differs
between native code and WebAssembly (where the empty string is printed). If
environment variables are used in a project, they should be setup properly
when instantiating the WebAssembly module.

##### Incorrect Check of Function Return Value, with fputs (CWE 235)

The following example illustrates one difference that arises due to the use of
musl as the standard C library when compiling to WebAssembly. Function fputs
is called, and its result is checked against the constant 0 to see if printing
the string has failed. However, the specification of fputs states that it
returns EOF (-1) upon error, and a non-negative number upon success. The musl
library returns 0 as number upon success, while glibc returns the number of
bytes printed. As a result, the WebAssembly version enters the branch and
prints fputs failed!. Instead, one should only rely on whether the return
value of fputs is a positive integer or not.

⬇ if (fputs(”string”, stdout) == 0)  printf(”fputs failed!\n”);

Semantic check: find return value of fputs that flows into a comparison
against constant 0.

##### Improper Resource Shutdown (CWE404)

A file is opened with the open system call. This returns a file descriptor as
an int. The fclose function is used to close the file. However, a file
descriptor must instead be closed with the close system call, while fclose
expects a pointer to a FILE data structure. In WebAssembly, this code executes
successfully and the program runs to completion, while it crashes in its
native version.

⬇ int f = open(”file.txt”,  O_RDWR | O_CREAT,  S_IREAD | S_IWRITE);  fclose((FILE *)f);

Semantic check: find calls to fclose on values of type int which have been
assigned by open.

##### Wide Characters

The following program simply writes a wide string to the console. While in its
native version, the string is indeed written to the console, the WebAssembly
version does not print anything. It actually requires calling fwide to tell
the console that wide characters will be printed. This is likely due to a
difference of libc. Instead, one should always call fwide before wprintf.

⬇ wprintf(L”

Semantic check: find calls to wprintf that have not been preceded by a call to
fwide.

NB. The code patterns that we present in the rest of this section require more
advanced program analysis techniques.

##### Incorrect String Argument (CWE 688)

The following program calls printf with "%s" as a format string, but
incorrectly passes an int as argument. The native program fails with a
segmentation fault, as it tries to read a string at an invalid memory
location. However, the WebAssembly binary succeeds, reading an empty string
from the (invalid) memory location 5. This is because the int argument is
treated as a string pointer of which the first element is likely ‘0‘ due to
WebAssembly initializing its linear memory with zeroes. As a result, this is
interpreted as passing the empty string to printf. Instead, calls to printf
should ensure that the types of arguments match the format string.

⬇ printf(”

Structural check: find values of an invalid type being passed as argument to
format string functions. Already implemented in clang with -Wformat.

##### Freeing Invalid Memory (CWE 590)

The following program allocates memory on the stack using alloca, and tries to
free it with free. However, free should be used to free heap-allocated memory.
As a result, this program crashes in its native version. However, it runs to
completion in WebAssembly. This could come from a different implementation of
free in musl. Instead, one should not free memory allocated on the stack.

⬇ char *data =  (char *)alloca(100*sizeof(char));  free(data);

Semantic check: find memory region allocated with alloca, flowing into a call
to free.

##### Incorrect Number of Arguments (CWE 685)

The following program calls printf with too few arguments, while the provided
format string expects two arguments. In WebAssembly, it works and treats the
second string as null, because the next value on the stack likely points to a
0 and is treated as the empty string. In native, it crashes as it cannot
provide a value for the second string. Instead, one should provide the number
of arguments in agreement with the format string.

⬇ printf(”

Structural check: find calls to format string functions that provide too few
arguments. Already supported in clang with -Wformat.

##### Freeing Pointer Not At Start of Allocated Region (CWE 761)

The following program allocates heap memory with malloc, and then moves the
allocated pointer further in the allocated region. It then tries to free the
memory by passing this incremented pointer as argument, which is invalid: free
should be called on the pointer to the initial allocated region. This crashes
in native, but works in WebAssembly, due to the use of a different allocator
in musl. Instead, one should free memory regions at their starting pointer.

⬇ char *data =  (char *)malloc(100*sizeof(char));  data++;  free(data);

Semantic check: this requires tracking allocated region and pointers to these
region, detecting calls to free on a pointer that is not at the beginning of
an allocated region.

##### Pointer Subtraction (CWE 469)

This program performs invalid pointer manipulation by subtracting two
different pointers: the slash variable points to the slash in the first
string, but is mistakenly used to compute the index of the slash in string2.
This prints a different value in WebAssembly and in its native version, due to
difference in memory layouts, i.e., string1 and string2 do not have the same
offsets in both binaries. Instead, one should not subtract pointers.

⬇ char string1[] = ”a/b”;  char string2[] = ”a/b”;  char *slash =
strchr(string1, ’/’);  printf(”

Structural check: find the subtract operation applied to two pointers.

##### Stack-Based Buffer Overflow (CWE 121)

The following program contains a buffer overflow due to an incorrect
allocation: alloca is used to allocate 10 bytes, while it should be used to
allocate 10 integers (hence, sizeof(int) * 10 bytes). When a buffer is copied
into the badly allocated memory region, this overflows. In its native version,
this program crashes as the stack is detected as being smashed. The
WebAssembly version runs the program successfully. Instead, one should ensure
that all memory accesses are made within bounds.

⬇ int *data = alloca(10);  for (int i = 0; i < 10; i++) {  data[i] = 0;  }

Detecting buffer overflows statically is an entire research problem on its
own.

##### Buffer Overread (CWE 126)

The following program illustrates a buffer overread: the data string is filled
with 150 times the ’A’ character. 99 of them are copied into the dest buffer,
but no extra null-terminating character is added. Hence, when printing the
dest buffer, printf will continue printing the string until it encounters the
byte 0. In WebAssembly, since the memory is initialized with 0s, the
likeliness of having a byte 0 right after the string, and we encounter this in
practice: only 99 As are printed. In its native version however, the string
contains random garbage after the 99 first bytes, and printf prints much more
characters. Instead, one should ensure that all memory accesses are made
within bounds.

⬇ char data[150] = ”AAAAAAAA…”;  char dest[100];  strncpy(dest, data, 99);
printf(”

Similarly, this kind of buffer overread is an entire research problem on its
own.

##### Undefined Behaviour (CWE 758)

The following program has undefined behaviour according to the C standard. It
allocates a pointer, but does not initialize it. When dereferencing this
pointer to print a string, what will be printed is therefore undefined. In
native, the name of the program is being printed, while in WebAssembly, the
empty string is printed. Instead, one should not dereference uninitialized
pointers.

⬇ char **pointer =  alloca(sizeof(char *));  printf(”

Semantic check: find dereferenced pointers that have not been initialized.

###  IV-B Smell Detection

We rely on the Clang Static Analyzer (CSA) to detect the first eight code
smells (_a_ to _h_) in the projects in our dataset.191919https://clang-
analyzer.llvm.org It is the most suitable option as it fits the constraints
imposed by the nature of the analysis. Precisely, CSA does not require the
projects to be able to be compiled and can instead analyze individual source
files, while still allowing for advanced static analyses such as dataflow
analysis.

To account for unknown external factors such as input values and behaviour of
libraries used, CSA uses symbolic execution and assigns unique symbols to
unknown values. This allows for path-sensitive analysis as occurrences of
symbols can be tracked through the execution of a program.

CSA can also be extended with custom checkers, which is required as the
majority of the code patterns being searched for are not detected by existing
analysis tools. The custom checkers rely on a callback mechanism to subscribe
to certain events. For example, the check::PreCall callback will be called
every time the analyser comes across a function call before it analyses it.
The analyser also supports inter-procedural analysis. The checkers have access
to the program state at each point in the path analysis, and this state can be
manipulated by the checkers to read and store arbitrary information.

####  IV-B1 Selected Compilation Smells

We choose the first eight compilation smells (i.e., a to h) described in the
previous section. This selection is based on how feasible it is to implement
checkers for these smells in the Clang static analyzer, using the tools
available (e.g., no pointer analysis).

####  IV-B2 Implementation of Custom Checkers

CSA includes checkers that can identify three smells. We implement five new
custom checkers using the capabilities of the CSA. Table IV lists the checkers
used in our experiments. The remaining smells (i.e., i to p) require deeper
analyses such as analysis of pointers or memory allocations, which are
difficult to determine statically. We leave detection of these smells for
future work.

We develop test cases (19 in total) for each custom checker to detect and
eliminate both false positives and false negatives. For example, to test the
BadFPutsComparison checker, we implement a test case to make sure that our
checker would still pick up cases where the result of calling fputs is
compared to a variable which has a known value of 0. Similarly, for other
checkers we develop tests based on the smells to ensure that the tool detects
the patterns as we expect it.

TABLE IV: Checkers used to find compilation smells. Checkers with * are new checkers that we developed. Checker | Description
---|---
DoubleFree | 2 calls to free() on same value
DoubleFClose | 2 calls to fclose() on same value
UninitialisedVariable | Checks if a variable has been initialised at the point where it is used
AccessEnv* | Checks for calls to getenv()
BadFputsComparison* | Comparison of fputs() return value to 0
ErrorWithoutAction* | Call fclose() on return value of fopen() without checking if it’s null
ImproperResourceShutdown* | Call fclose() on return value of open()
WideString* | Checks if fwide() has not been called prior to calling wprintf()

####  IV-B3 Running the Checkers

We run our checkers on 1 605 projects, including both the projects that are
WebAssembly-related, and the projects that are identified to target
WebAssembly as a compilation target. To do so, for each project, we move all
C/C++ source files into a single directory using a Node.js script, and rename
filenames to prevent conflicts. This is necessary as the Clang Static Analyzer
is not able to handle files in nested subdirectories. We then run the Clang
Static Analyzer via command line, passing it the name of each C or C++ source
file in the project. This results in a .plist file containing the analysis
results for each source file in the project. We use another Node.js script to
post process the results and merge the many .plist files into a single file in
JSON format that contains all of the key information about each code smell
detected in that project. This is a time consuming process, as some projects
have up to 50 000 source files.

###  IV-C Results

We uncover the presence of two compilation smells namely, AccessEnv and
ErrorWithoutAction). The checkers detect no instance of other six compilation
smells. Table V lists the number of repositories affected by the two
compilation smells. We discover a total of 1 873 compilation smells and note
that 386 projects (i.e., 24%) contain at least one instance of a compilation
smell. Future work is necessary to understand whether these smells are
indication of potential bugs or not. Nevertheless, the checkers that we use in
this study are present in the artifact accompanying this paper, and developers
can use them to detect and reduce the prevalence of compilation smells in
practice.

TABLE V: Results of Compilation Smells Analysis Checker | Occurences | Repositories Affected
---|---|---
AccessEnv | 809 | 241 (15%)
ErrorWithoutAction | 974 | 300 (19%)

None of the checkers already implemented in Clang find instances of those code
patterns in our dataset. We theorise that this may be because the developers
are already alerted to these code smells, such as through their IDE or during
the build process, meaning that these errors are caught and rectified before
they are committed to the repository.

##  V Threats to Validity

We define several heuristics to ensure a high-quality dataset, but every
manual process is subject to bias. We may have exhibited bias in the methods
we choose to sample our dataset. Such as the process of queries and keywords
selected using the GitHub Search API, to the manual analysis of compilation
indicators to WebAssembly. This can be shown in our selection of keywords
defined in our NLP filtering. We define known keywords that we think are
related to WebAssembly, but there might be more relevant keywords that we
missed.

The tools we use in this study are limited too. For instance, the return limit
of the GitHub API reduced the number of projects we could gather, capping at
1000 results per query, even though we know that more projects exist. To
overcome this, we search over periods of time that span less than 1000
projects.

We take reasonable steps to create a dataset that is inclusive of a wide range
of projects, but it may not be representative of all C/C++ projects that
compile to WebAssembly. This could be verified through analysis of a larger
dataset. We also focus on open-source projects on GitHub, but they may be
quite different in nature to closed-source projects developed by large
companies or those projects found via other sources.

For the extraction of WebAssembly binaries from our dataset, we focus only on
projects that are compiled using either makefiles directly, or relying on
CMake as a build system. This is the closest we can have to a standard build
system in C and C++. Many projects however could not be compiled: some do not
use such build systems, e.g., sometimes resorting to shell scripts to issue
the compilation commands; others require libraries that are missing; or have
improper configuration of their build system. We extract WebAssembly files
based on their name only (.wasm or .wat), but there could be other files that
use a different naming scheme.

We share the dataset of binaries with information about the projects from
which each binary is built. It is important to check license compatibility of
these projects to ensure that any legal restrictions or obligations are
properly adhered to.

The code patterns that we could detect are limited by the capabilities of the
Clang static analysis tool being used. There is further scope to develop
analysis tools that can detect the remaining code smells that are not
implemented in this work. Detection of these code smells require modelling the
memory and pointers used in the program, making them more difficult to detect
using only static analysis. Even though we detect many instances of
compilation smells at the level of a project, such smells may be in a file
that will not be compiled to WebAssembly, even if part of the project does.
Hence, further work is required to determine which specific files within a
project will be compiled to WebAssembly. Finally, we do not investigate the
context in which these issues arise nor the impacts that such unwanted code
patterns have on these projects. This requires an intensive manual effort that
we plan to conduct in future.

##  VI Related Work

We build the first dataset of WebAssembly sources and their binaries. This
dataset is large, and it remains up to date with the help of Wasmizer tool
which is deployed. We also investigate the prevalence of compilation smells in
real-world WebAssembly programs.

Regarding the real-world usage of WebAssembly, Hilbig et al [8] found that
64.2% of WebAssembly binaries are compiled from C or C++ in open access
repositories. This is significant as these memory-unsafe languages are
particularly vulnerable to security weaknesses when compiled to WebAssembly
due to the lacking compiler protections. Additionally, many of these binaries
have potential memory-related vulnerabilities, such as making use of the
unmanaged stack, or using a custom memory allocator, which increase the risk
of security weaknesses within the program [8]. The lack of memory protection
measures implemented in WebAssembly compilers leads to security weaknesses.
Almost 80% of binaries make use of the LLVM toolchain [18], so any security
measures implemented in this toolchain would have a significant impact on the
security of WebAssembly binaries.

When compiling C/C++ programs to WebAssembly, there have been observed
differences in the behaviour of the resulting binaries when compared to x86
native code [10, 9]. While they may introduce hard-to-detect bugs, in many
cases these differences may be fairly harmless, such as differing outputs from
print statements. However, as WebAssembly lacks common memory protections some
behavioural differences related to memory allocation may lead to security
weaknesses. Three main causes were identified as being responsible for the
observed differences [9]. The first is a difference due to a different
implementation of the C standard library used in the native executable and its
WebAssembly counterpart. The second cause is the previously mentioned lacking
memory protections of WebAssembly, where cases that would cause an exception
to be thrown in native binaries instead continue to run in WebAssembly.
Finally differences in the execution environment also account for some
behaviour differences.

All security critical differences relate to the memory model and its
protections (or lack thereof). In a C program compiled to a native binary, a
stack smashing attack would be prevented by a stack canary. However, as these
are not present in WebAssembly, it leaves the application vulnerable to such
an attack [10, 9]. Similarly, a buffer underwrite that would usually be
protected against via hardware protection or bounds checks remains undetected
[9]. While the sandboxed environment of WebAssembly prevents such attacks
manipulating anything outside of the binary’s memory, Lehmann et al. [19]
demonstrated how these vulnerabilities can be exploited in order to execute an
XSS attack in a browser, run an arbitrary shell command in a node.js server-
side environment, and write arbitrary content to a file in Wasmtime standalone
runtime. While the work done by Stiévenart et al. [10, 9] limits itself to
only consider the Clang toolchain, McFadden et al. [20] establishes that
similar vulnerabilities are present in the Emscripten compiler toolchain.
These studies have shown the existence of code patterns that exhibit different
behaviour in a syntactic test suite, however we aim to take the next step and
investigate the prevalence of these code patterns in real world projects.

##  VII Conclusion

We identify 2 540 C and C++ projects on GitHub that are related to WebAssembly
and likely target WebAssembly for their compilation. We compile these projects
to build a dataset of 8 915 binaries that are linked to their corresponding
source project. We develop Wasmizer, a tool that fully automates this process.
Wasmizer is open source and is running on a dedicated machine to regularly
mine GitHub projects and provide researchers with a novel and up-to-date
dataset of WebAssembly binaries and their associated projects.

To present a use case of this dataset, we investigate the presence of eight
WebAssembly _compilation smells_ in 1 605 projects. We find that 386 projects
that aim to compile to WebAssembly exhibit at least one compilation smell. The
most prevalent smells are calls to getenv() and calls to fclose() on the
return value of fopen() without checking if the value is null. Our findings
conclude that developers compiling native programs to WebAssembly should be
aware of behavioural differences in their implementation and expected results.
This is due to many repositories exhibiting similar issues, which may
adversely affect development goals.

In future, we plan to locate the exact source files that generate WebAssembly
binaries. This can for example be achieved by tracing compiler calls or by
inspecting dependencies in the build system.

## Acknowledgment

The feedback we received from the MSR 2023 reviewers was helpful in improving
Wasmizer and making it a more useful tool for the research community. We are
grateful for their input and excited to publicly share Wasmizer and the
evolving dataset that it curates.

## References

  * [1] T. Brito, P. Lopes, N. Santos, and J. F. Santos, “Wasmati: An efficient static vulnerability scanner for WebAssembly,” _Computers and Security_ , vol. 118, 7 2022.
  * [2] Q. Stiévenart, D. W. Binkley, and C. D. Roover, “Static stack-preserving intra-procedural slicing of WebAssembly binaries,” in _44th IEEE/ACM 44th International Conference on Software Engineering, ICSE 2022, Pittsburgh, PA, USA, May 25-27, 2022_. ACM, 2022, pp. 2031–2042. [Online]. Available: https://doi.org/10.1145/3510003.3510070
  * [3] A. Romano, D. Lehmann, M. Pradel, and W. Wang, “Wobfuscator: Obfuscating JavaScript malware via opportunistic translation to webassembly,” in _43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022_. IEEE, 2022, pp. 1574–1589. [Online]. Available: https://doi.org/10.1109/SP46214.2022.9833626
  * [4] A. Romano and W. Wang, “WasmView: visual testing for WebAssembly applications,” in _ICSE ’20: 42nd International Conference on Software Engineering, Companion Volume, Seoul, South Korea, 27 June - 19 July, 2020_ , G. Rothermel and D. Bae, Eds. ACM, 2020, pp. 13–16. [Online]. Available: https://doi.org/10.1145/3377812.3382155
  * [5] Q. Stievenart and C. D. Roover, “Compositional information flow analysis for WebAssembly programs.” IEEE, 9 2020, pp. 13–24. [Online]. Available: https://ieeexplore.ieee.org/document/9252076/
  * [6] D. Lehmann and M. Pradel, “Wasabi: A framework for dynamically analyzing WebAssembly.” ACM, 4 2019, pp. 1045–1058. [Online]. Available: https://dl.acm.org/doi/10.1145/3297858.3304068
  * [7] M. Musch, C. Wressnegger, M. Johns, and K. Rieck, “New kid on the web: A study on the prevalence of WebAssembly in the wild,” in _International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment_. Springer, 2019, pp. 23–42.
  * [8] A. Hilbig, D. Lehmann, and M. Pradel, “An empirical study of real-world webassembly binaries.” ACM, 4 2021, pp. 2696–2708. [Online]. Available: https://dl.acm.org/doi/10.1145/3442381.3450138
  * [9] Q. Stiévenart, C. De Roover, and M. Ghafari, “Security risks of porting c programs to WebAssembly,” in _Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing_ , ser. SAC ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 1713–1722. [Online]. Available: https://doi.org/10.1145/3477314.3507308
  * [10] Q. Stiévenart, C. D. Roover, and M. Ghafari, “The security risk of lacking compiler protection in WebAssembly,” _The 21st IEEE International Conference on Software Quality, Reliability and Security (QRS 2021)_ , 11 2021\. [Online]. Available: http://arxiv.org/abs/2111.01421
  * [11] A. Zakai, “Emscripten: an LLVM-to-JavaScript compiler.” ACM Press, 2011, p. 301. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2048147.2048224
  * [12] L. Technologies. (2022) C/C++ to WebAssembly compiler — cheerp — leaning technologies. [Online]. Available: https://leaningtech.com/cheerp/
  * [13] A. Bougouin, F. Boudin, and B. Daille, “Topicrank: Graph-based topic ranking for keyphrase extraction,” 2013.
  * [14] LIAAD. (2021) Single-document unsupervised keyword extraction. [Online]. Available: https://github.com/LIAAD/yake
  * [15] Explosion. (2022) Spacy - industrial-strength natural language processing. [Online]. Available: https://spacy.io/
  * [16] llvm-admin team. (2022) The LLVM compiler infrastructure. [Online]. Available: https://llvm.org/
  * [17] T. Boland and P. E. Black, “Juliet 1.1 C/C++ and Java test suite,” _Computer_ , vol. 45, no. 10, pp. 88–90, 2012.
  * [18] C. Lattner and V. Adve, “LLVM: A compilation framework for lifelong program analysis & transformation,” 2004. [Online]. Available: http://llvm.cs.uiuc.edu/
  * [19] D. Lehmann, J. Kinder, and M. Pradel, “Everything old is new again: Binary security of WebAssembly,” 2020, pp. 217–235. [Online]. Available: https://www.usenix.org/conference/usenixsecurity20/presentation/lehmann
  * [20] B. Mcfadden, T. Lukasiewicz, J. Dileo, and J. Engler, “Security chasms of WASM,” 2018. [Online]. Available: https://i.blackhat.com/us-18/Thu-August-9/us-18-Lukasiewicz-WebAssembly-A-New-World-of-Native_Exploits-On-The-Web-wp.pdf


11affiliationtext: Brown University22affiliationtext: University of Illinois
at Urbana-Champaign

# Learning to Infer Kinematic Hierarchies for Novel Object Instances

Hameed Abdul-Rashid  Miles Freeman  Ben Abbatematteo  George Konidaris  Daniel
Ritchie

###### Abstract

Manipulating an articulated object requires perceiving its _kinematic
hierarchy_ : its parts, how each can move, and how those motions are coupled.
Previous work has explored perception for kinematics, but none infers a
complete kinematic hierarchy on never-before-seen object instances, without
relying on a schema or template. We present a novel perception system that
achieves this goal. Our system infers the moving parts of an object and the
kinematic couplings that relate them. To infer parts, it uses a point cloud
instance segmentation neural network and to infer kinematic hierarchies, it
uses a graph neural network to predict the existence, direction, and type of
edges (i.e. joints) that relate the inferred parts. We train these networks
using simulated scans of synthetic 3D models. We evaluate our system on
simulated scans of 3D objects, and we demonstrate a proof-of-concept use of
our system to drive real-world robotic manipulation.

##  I Introduction

People frequently interact with articulated objects: opening doors, putting
things away in drawers, adjusting the height of chairs, etc. To a human, such
interactions are effortless, but the underlying process is complex: one must
perceive the _kinematic hierarchy_ of the object (i.e. which parts can move,
how they move, and how those motions are coupled). Then, one must plan a
sequence of actions to transform the object from its current kinematic pose
into another, and finally, manipulate the object to execute that plan. The
perception part of this process is particularly challenging, as objects with
similar function can vary considerably in both their structure and their
geometry. Cabinets, for example, can have differing numbers of drawers in
different arrangements and many different doorknob shapes. To succeed at
manipulating such objects in the wild, an agent must infer the kinematic
hierarchies of never-before-seen object instances with these kinds of
variations.

This problem has received considerable attention in computer vision and
robotics literatures. Vision researchers have made progress on detecting
atomic parts of 3D objects and predicting the presence and parameters of
individual kinematic joints [29, 35, 34]. These approaches are trained on
large datasets and thus have the potential to generalize to novel objects from
a known category, however, they do not infer kinematic hierarchies.
Roboticists have leveraged embodiment to solve the problem by providing the
agent with human demonstrations or allowing it to interact with its
environment [28, 13, 15]. Recent works infer kinematic hierarchies but assume
a simple template (e.g. one door per cabinet) and thus cannot generalize to
the structural variability that exists in real world objects [1, 19, 11].

Figure 1:  We propose a system for robot perception of the kinematic structure
of never-before-seen object instances. The robot scans the object from
multiple viewpoints, building a 3D point cloud representation of it. Our
system then segments this point cloud into parts and infers the kinematic
hierarchy that couples them, allowing for the robot to plan and execute
articulated motions of the object.

In this paper, we propose a perception system that both infers kinematic
hierarchies and also generalizes to novel object geometries and structures.
Our system infers the moving parts of an object and the kinematic couplings
between them. To infer parts, it uses a point cloud instance segmentation
neural network. To infer kinematic hierarchies, it uses a graph neural network
which learns to infer the existence, direction, and type of edges (i.e.
joints) that relate the inferred parts. This system is trained on simulated
scans of a large set of synthetic 3D models, enabling it to learn to
generalize to new, never-before-seen object instances which may differ
geometrically and structurally from the training data. We evaluate our
system’s perception abilities on synthetic point clouds, and find that our
system reliably detects moving parts and reconstructs kinematic hierarchies on
synthetic data. We also demonstrate a proof-of-concept application of using
the output of our perception system to drive manipulation executed by a real-
world robot platform.

Figure 2:  Overview of our system. Given an input 3D point cloud
representation of an object, our system (a) segments the point cloud into
parts using an instance segmentation network with multi-view consensus, (b)
constructs a part graph and uses a graph neural network to label its nodes and
edges with kinematic properties, and (c) constructs a kinematic hierarchy from
this graph which can be used for robot manipulation.

In summary, our contributions are:

  * •

The first method for inferring kinematic hierarchies from never-before-seen
instances of 3D objects, without reliance on a schema or template.

  * •

A novel graph neural network approach for predicting hierarchies from part
segments.

##  II Related Work

###  II-A Approaches from the Robotics Community

Kinematic model and articulated pose estimation are well-studied problems in
the robotics literature. Observation-based approaches [28, 24, 22, 6, 33] fit
motion models to an observed sequence of part poses. Interactive approaches
leverage the embodiment of the manipulator to generate part motion
autonomously [13, 10, 2, 20, 16, 3] and to reason about the intended effects
of actions [12]. More recently, learning-based approaches to category-level
model and pose estimation [19, 1, 11, 36] have shown promise, but are thus-far
limited to a-priori known connectivity graphs. Several methods estimate only
articulated pose given known kinematic models and geometry [4, 7, 23].

###  II-B Approaches from the Computer Vision Community

Wang et al. train a model to jointly predict movable parts and their motion
parameters from an input point cloud. [29]. Yi et al. take a pair of
articulated 3D shapes of the same category but in different kinematic poses,
and jointly infer moving parts and their kinematic motion parameters [35]. Yan
et al. infer movable parts by hallucinating their motions over multiple time
steps [34]. These approaches train deep neural networks which generalize to
geometrically and structurally different input objects. However, none infer
the structure of the object’s kinematic hierarchy: they treat each articulated
part as it if moves in isolation. Our approach bears resemblance to RigNet, a
system for inferring the skeletal joint structure of articulated humanoid and
creature characters [32]. Like us, they also use a graph neural network for
predicting graph topology information.

##  III Approach

In this section, we overview our method for kinematic mobility perception.
Fig. 2 shows a schematic of our pipeline.

###  III-A Part Segmentation

The input to our system is an unlabeled point cloud depicting an articulated
object; a robot can obtain such input by unprojecting and consolidating frames
from an onboard depth sensor. Our system first segments this point cloud into
parts, some of which are movable (Fig. 2a). This stage relies upon an existing
neural network architecture for point cloud instance segmentation (i.e.
segmenting a point cloud without consistent part labels) [21].

###  III-B Kinematic Graph Labeling

Given a part-segmented point cloud, our system next infers the articulation
properties of those parts: the type of articulated motion they support (if
any) and how the motions of different parts are coupled. To do this, it
converts the segmented point cloud into a graph and phrases the problem as one
of _graph labeling_ : nodes in the graph represent parts, and edges between
them represent potential kinematic connections (e.g. joints) between parts. A
graph neural network predicts whether each node is static, rotating, or
translating, as well as whether each edge should exist (i.e. whether two parts
should be kinematically connected), the probability of each node being the
root of the tree, and the direction of kinematic dependency (Fig. 2b).

###  III-C Hierarchy Creation

Given the labeled graph, we construct a kinematic hierarchy by converting the
bidirectional graph into a n-ary tree. Xu et al. address this problem by
constructing a pairwise matrix where each entry represents the negative log
probability of the corresponding parts possessing an edge connection [32]. The
pairwise matrix is traversed from a predicted root node and a n-ary tree is
extracted via a Minimum Spanning Tree (MST) algorithm [25]. We adopt this
method to convert our predicted bidirectional graphs to an n-ary tree.(Fig.
2c).

##  IV Part Segmentation

To segment point clouds into parts, we use a neural network based on that of
PartNet [21]. This architecture uses a PointNet++ network [27] to compute per-
point embeddings, each of which is then fed to a semantic segmentation branch
(assigns semantic labels to each point) and an instance segmentation branch
(assign each point to one of $N$ possible instance masks; we use $N=24$). As
our system does not assume parts are semantically labeled, we could remove the
semantic segmentation branch. However, PartNet showed that semantic
segmentation helps improve the quality of instance segmentation. Thus, we
treat the semantic segmentation branch as a “motion type prediction” branch
(static, rotating, translating, rotating and translating)—labels which we do
assume of our data.

We train the segmentation network on 3D objects from the PartNet-Mobility
dataset [30]. For augmentation, we use multiple poses for each moving part of
each object, as described in more detail in Section VI. To simulate a robot’s
onboard depth sensor, we render point clouds from these objects using a
software simulator of the Kinect sensor [18]. We train the network using the
Adam optimizer [14] with learning rate $10^{-4}$. Training was run for at most
8 hours per category.

Part Segments | Initial Graph | GT Tree
---|---|---
|  |
|  |
|  |
Figure 3:  Segmented point clouds, their initial overcomplete part graphs, and
their ground truth part graphs (as determined by a human labeler).  Figure 4:
Neural network architecture for kinematic graph labeling. A PointNet [26]
converts each part point cloud into an initial node feature $\mathbf{x}$.
These features go through graph convolutional + pooling layers to produce
features $\mathbf{y}$ which are passed to MLPs for predicting node and edge
attributes.

##  V Kinematic Graph Annotation

Here we describe how our system takes a segmented point cloud, converts it to
a graph, and labels this graph with the information required to construct a
kinematic hierarchy.

###  V-A Point Cloud to Graph Conversion

The kinematic hierarchy for a segmented object is a directed tree: tree nodes
correspond to parts, nodes are labeled with a motion type (rotation and/or
translation) and edge directions indicate kinematic couplings (i.e. edge
$A\rightarrow B$ means part $B$ moves with part $A$). To infer this tree from
a segmented point cloud, our system first constructs an overcomplete,
undirected, unlabeled graph over the parts, and then prunes edges, determines
edge directions, and labels nodes using a graph neural network. Our system
constructs the initial graph by adding an undirected edge between any two
parts whose Euclidean distance is below a small threshold. Fig. 3 shows some
example segmented point clouds and their initial graphs.

###  V-B Graph Labeling Network

Given a graph constructed by the above procedure, we use a graph neural
network to label its nodes and edges with the information required to
construct a kinematic hierarchy.

Input features: Every node corresponds to one part, i.e. one subset of points
from the object point cloud. We encode these point subsets into per-node
vectors $\mathbf{x}$ using a PointNet [26].

Graph network: To make per-node and per-edge predictions, our system must
understand the context of each node or edge within the object. To satisfy this
goal, we use a graph convolutional network to convert node features
$\mathbf{x}$ into context-aware features $\mathbf{y}$ (Fig. 4). Our network
passes all nodes through three GraphSAGE convolution layers [9], which compute
new node features based on learned aggregations of neighbor node features.
Each convolution layer is followed by a pooling and unpooling layer based on
learned edge collapses [8]. In early experiments, we found this pooling +
unpooling scheme to perform better than architectures that used only
convolution. Finally, the outputs of all convolution layers and all pooling
layers are concatenated to form a multi-scale feature vector $\mathbf{y}$ for
each node.

Node and edge attribute prediction: The per-node features $\mathbf{y}$ are fed
to multi-layer perceptrons (MLPs) for predicting node attributes. For edge
attributes, the $\mathbf{y}$’s for both edge endpoints are concatenated and
fed to the MLP.

###  V-C Training

We train the graph labeling network on synthetic 3D models from PartNet-
Mobility [30]. We first pre-train the node feature PointNet by training it as
the encoder in an autoencoder framework; this network trains for 500 epochs
using Nesterov SGD with a learning ratte of $10^{-3}$. The graph labeling
network trains for 30 epochs using Adam with a learning rate of $10^{-3}$.
Train both networks takes 1.5 - 3 hours on an NVIDIA RTX 2080 Ti.

##  VI Results & Evaluation

Here we evaluate our method’s ability to infer kinematic hierarchies via
controlled experiments and a demonstration on a real-world robot. For
experiments on synthetic PartNet-Mobility objects, we use the same train/test
splits introduced by Mo et al. [21], restricted to models with valid kinematic
trees. We augment the training and test datasets by uniformly sampling
articulated poses within each part’s ground truth range of motion. We train on
249 storage furniture models, 22 lamp models, and 53 chair models; we test on
69, 8, and 12 models, respectively. We use 18 pose augmentations for training
and testing.

###  VI-A Part Segmentation

Table I summarizes the performance of our part segmentation method on
synthetic 3D objects. We use an established instance segmentation metric [21]:
we compute the intersection over union (IoU) of each predicted part segment
with its closest ground truth part segment, classify it as a “correct”
prediction if the IoU is over 0.5, and then compute the mean average precision
of these classifications across all parts in all test set objects. We compute
this metric under two conditions: (1) _Clean_ point clouds sampled directly
from the surface of PartNet-Mobility 3D meshes, (2) _Noisy_ point clouds
generated by simulated Kinect scans of PartNet-Mobility models as described in
Section IV. Fig. 5 shows some qualitative examples. The network reliably
segments parts in clean point clouds, and this performance degrades slightly
in the noisy depth scans. The lamp category is especially challenging due to
the small number of models present in the training data.

Table I:  Part segmentation on PartNet-Mobility (mAP @ 0.5 IoU)  Category | Clean | Noisy
---|---|---
_Storage Furniture_ | 0.922 | 0.907
_Lamp_ | 0.695 | 0.593
_Chair_ | 0.824 | 0.811
|  Clean  |  Noisy
---|---|---
Predicted Parts |  |  |  |  |  |
Target Parts |  |  |  |  |  |
Figure 5:  Examples of part segmentation for both Clean and Noisy point
clouds.

###  VI-B Kinematic Structure Prediction

We next evaluate our graph neural network module’s ability to infer the
structure of an object’s kinematic hierarchy. To assess this performance, we
use four metrics:

  * •

$\mathbf{E}_{\text{type}}$: % of nodes whose motion type is mis-predicted.

  * •

$\mathbf{E}_{\text{exist}}$: & of edges whose existence is mis-predicted.

  * •

$\mathbf{E}_{\text{dir}}$: % of edges whose direction is mis-predicted.

  * •

$\mathbf{E}_{\text{root}}$: % of models whose root node is mis-predicted.

  * •

Tree F1: the F1 score of the predicted kinematic hierarchy with respect to the
ground truth one. Precision is computed via top-down traversal of the
predicted tree, counting the fraction of nodes and edges which match their
counterparts in the ground truth tree. Recall computation uses the same
procedure, with the roles of the predicted and ground-truth trees reversed.

Table II summarizes the performance of our network on Clean and Noisy
synthetic data. As expected, the GNN evaluated on clean data with ground truth
instance segmentation preforms well on all classes. Even in the case where
$\mathbf{E}_{\text{dir}}$ is relatively high for the lamp and chair class the
negative log probability pairwise matrix complemented with MST is able to
construct trees with a negligible amount of error. On noisy data, performance
again degrades slightly. Fig. 6 shows some qualitative examples.

|  Clean  |  Noisy
---|---|---
Parts |  |  |  |  |  |
Predicted Tree |  |  |  |  |  |
Target Tree |  |  |  |  |  |
Figure 6:  Examples of predicted kinematic hierarchies for both Clean and Noisy point clouds. All examples shown use ground truth part segmentations.  Table II: Kinematic structure error for different data types Category | Data Type | $\mathbf{E_{\text{type}}}$ | $\mathbf{E_{\text{exist}}}$ | $\mathbf{E_{\text{dir}}}$ | $\mathbf{E_{\text{root}}}$ | Tree F1
---|---|---|---|---|---|---
_Storage Furniture_ | Clean | 1.16 | 1.2 | 2.22 | 0 | 99.73
Noisy | 0.39 | 2.03 | 29.04 | 0 | 99.02
_Lamp_ | Clean | 0.47 | 4.63 | 31.11 | 0.23 | 98.24
Noisy | 0 | 0.98 | 17.24 | 0.92 | 97.82
_Chair_ | Clean | 0.08 | 0.1 | 39.64 | 0 | 99.77
Noisy | 0.24 | 0.99 | 41.73 | 0 | 98.67
Scanning
---
|  |
Interacting
|  |
Figure 7: Frames from a video demonstrating a robot scanning and then
interacting with an articulated object.

###  VI-C Robot Demo

Finally, we demonstrate that the model enables a Kinova Movo robot to
manipulate novel object instances. A storage furniture object was densely
scanned using the robot’s Kinect sensor by driving the robot around the
object. Pointclouds were merged using RTAB-Map [17], which performed SLAM
using the robot’s odometry, base laser scans, and visual data. The object was
manually segmented from the scene and assigned a frame of reference. Our model
successfully performed part segmentation and kinematic hierarchy inference;
predictions are visualized in Figure 1. Motion model predictions, e.g. the
axes of rotation, were generated using type predictions from the estimated
kinematic tree and the intersections of part bounding boxes. Using the
predicted tree and motion models, the agent is able to plan and execute
interactions with the object. We fixed a grasp on the relevant object part,
and ran a simple controller which moves the end-effector along the predicted
direction of motion toward a goal configuration. Fig. 7 shows frames from a
video of the robot scanning the cabinet and closing one of its doors.

##  VII Future Work

Training our neural networks requires collections of part segmented,
kinematically-annotated 3D models. Such data is not widely available, as it
requires nontrivial human annotation effort. Recent computer vision research
has demonstrated the possibility of segmenting 3D models with limited or even
no human supervision [5, 37]. The development of similar techniques for
identifying articulated motion within 3D shapes would allow our methods to be
applied to any object type for which unsegmented 3D models are available [31].

Our approach treats segmentation and graph labeling as separate sub-problems,
but one can argue that they are coupled: parts determines what motions are
possible, and whether a motion is possible determines whether a proposed part
is a good one. Accordingly, the Shape2Motion system found benefits in jointly
segments and predict motion parameters for parts [29]. It is possible that
jointly segmenting and predicting kinematic hierarchy could confer similar
benefits.

We focused on inferring the structure of an object’s kinematic hierarchy. Our
system could be combined with one that focuses on kinematic motion parameter
prediction [29, 34, 35] to produce a complete mobility perception system.

##  VIII Conclusion

We presented a perception system that infers kinematic hierarchies for never-
before-seen object instances. Our system infers the moving parts of an object
and the kinematic couplings between them. To infer parts, it uses a point
cloud segmentation neural network, improved via a multi-view consensus
algorithm. To infer kinematic couplings, it uses a graph neural network to
predict the existence, direction, and type of edges (i.e. joints) that relate
the inferred parts. We train these networks using simulated scans of synthetic
3D models. In experiments, our system inferred accurate kinematic hierarchies
for simulated scans of 3D objects and scans of real-world objects gathered by
a mobile robot.

## References

  * [1] Ben Abbatematteo, Stefanie Tellex, and George Konidaris.  Learning to generalize kinematic models to novel objects.  In Proceedings of the Third Conference on Robot Learning, 2019.
  * [2] Patrick R Barragän, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.  Interactive bayesian identification of kinematic mechanisms.  In Robotics and Automation (ICRA), 2014 IEEE International Conference on, pages 2013–2020. IEEE, 2014.
  * [3] Manuel Baum, Matthew Bernstein, Roberto Martin-Martin, Sebastian Höfer, Johannes Kulick, Marc Toussaint, Alex Kacelnik, and Oliver Brock.  Opening a lockbox through physical exploration.  In 2017 IEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids), pages 461–467, Nov 2017.
  * [4] Jonathan Brookshire and Seth Teller.  Articulated pose estimation using tangent space approximations.  The International Journal of Robotics Research, 35(1-3):5–29, 2016\.
  * [5] Zhiqin Chen, Kangxue Yin, Matthew Fisher, Siddhartha Chaudhuri, and Hao Zhang.  Bae-net: Branched autoencoder for shape co-segmentation.  Proceedings of International Conference on Computer Vision (ICCV), 2019.
  * [6] Andrea F. Daniele, Thomas M. Howard, and Matthew R. Walter.  Learning articulated object models from language and vision.  2017\.
  * [7] Karthik Desingh, Shiyang Lu, Anthony Opipari, and Odest Chadwicke Jenkins.  Efficient nonparametric belief propagation for pose estimation and manipulation of articulated objects.  Science Robotics, 4(30), 2019.
  * [8] Frederik Diehl.  Edge contraction pooling for graph neural networks.  arXiv preprint arXiv:1905.10990, 2019.
  * [9] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Advances in neural information processing systems, pages 1024–1034, 2017.
  * [10] Karol Hausman, Scott Niekum, Sarah Osentoski, and Gaurav S Sukhatme.  Active articulation model estimation through interactive perception.  In Robotics and Automation (ICRA), 2015 IEEE International Conference on, pages 3305–3312. IEEE, 2015.
  * [11] Ajinkya Jain, Rudolf Lioutikov, and Scott Niekum.  Screwnet: Category-independent articulation model estimation from depth images using screw theory.  arXiv preprint arXiv:2008.10518, 2020.
  * [12] Ajinkya Jain and Scott Niekum.  Learning hybrid object kinematics for efficient hierarchical planning under uncertainty.  In IROS, 2019.
  * [13] Dov Katz.  Interactive perception of articulated objects for autonomous manipulation.  University of Massachusetts Amherst, 2011.
  * [14] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [15] Oliver Kroemer, Scott Niekum, and George Konidaris.  A review of robot learning for manipulation: Challenges, representations, and algorithms.  arXiv preprint arXiv:1907.03146, 2019.
  * [16] Johannes Kulick, Stefan Otte, and Marc Toussaint.  Active exploration of joint dependency structures.  In Robotics and Automation (ICRA), 2015 IEEE International Conference on, pages 2598–2604. IEEE, 2015.
  * [17] Mathieu Labbé and François Michaud.  Rtab-map as an open-source lidar and visual simultaneous localization and mapping library for large-scale and long-term online operation.  Journal of Field Robotics, 36(2):416–446, 2019.
  * [18] Michael Landau.  Kinect Infrared (IR) and Depth Image Simulator.  MATLAB Central, 2017.
  * [19] Xiaolong Li, He Wang, Li Yi, Leonidas Guibas, A Lynn Abbott, and Shuran Song.  Category-level articulated object pose estimation.  In CVPR, 2020.
  * [20] R. Martín Martin and O. Brock.  Online interactive perception of articulated objects with multi-level recursive estimation based on task-specific priors.  In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2494–2501, Sept 2014.
  * [21] Kaichun Mo, Shilin Zhu, Angel X. Chang, Li Yi, Subarna Tripathi, Leonidas J. Guibas, and Hao Su.  PartNet: A large-scale benchmark for fine-grained and hierarchical part-level 3D object understanding.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [22] Scott Niekum, Sarah Osentoski, Christopher G Atkeson, and Andrew G Barto.  Online bayesian changepoint detection for articulated motion models.  In Robotics and Automation (ICRA), 2015 IEEE International Conference on, pages 1468–1475. IEEE, 2015.
  * [23] Jana Pavlasek, Stanley Lewis, Karthik Desingh, and Odest Chadwicke Jenkins.  Parts-based articulated object localization in clutter using belief propagation.  arXiv preprint arXiv:2008.02881, 2020.
  * [24] Sudeep Pillai, Matthew R Walter, and Seth Teller.  Learning articulated motions from visual demonstration.  In Robotics: Science and Systems, 2015.
  * [25] Robert Clay Prim.  Shortest connection networks and some generalizations.  The Bell System Technical Journal, 36(6):1389–1401, 1957.
  * [26] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In CVPR, 2017.
  * [27] Charles R Qi, Li Yi, Hao Su, and Leonidas J Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  In Neural Information Processing Systems, 2017.
  * [28] Jürgen Sturm, Cyrill Stachniss, and Wolfram Burgard.  A probabilistic framework for learning kinematic models of articulated objects.  Journal of Artificial Intelligence Research, 41:477–526, 2011.
  * [29] Xiaogang Wang, Bin Zhou, Yahao Shi, Xiaowu Chen, Qinping Zhao, and Kai Xu.  Shape2motion: Joint analysis of motion parts and attributes from 3d shapes.  IEEE Conference on Computer Vision and Pattern Recognition, 2019\.
  * [30] Fanbo Xiang, Yuzhe Qin, Kaichun Mo, Yikuan Xia, Hao Zhu, Fangchen Liu, Minghua Liu, Hanxiao Jiang, Yifu Yuan, He Wang, Li Yi, Angel X. Chang, Leonidas J. Guibas, and Hao Su.  SAPIEN: A simulated part-based interactive environment.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [31] Xianghao Xu, David Charatan, Sonia Raychaudhuri, Hanxiao Jiang, Mae Heitmann, Vladimir Kim, Siddhartha Chaudhuri, Manolis Savva, Angel X Chang, and Daniel Ritchie.  Motion annotation programs: A scalable approach to annotating kinematic articulations in large 3d shape collections.  In 2020 International Conference on 3D Vision (3DV), pages 613–622. IEEE, 2020.
  * [32] Zhan Xu, Yang Zhou, Evangelos Kalogerakis, Chris Landreth, and Karan Singh.  Rignet: Neural rigging for articulated characters.  ACM Trans. on Graphics, 39, 2020.
  * [33] Jingyu Yan and Marc Pollefeys.  Automatic kinematic chain building from feature trajectories of articulated objects.  In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), volume 1, pages 712–719. IEEE, 2006.
  * [34] Zihao Yan, Ruizhen Hu, Xingguang Yan, Luanmin Chen, Oliver van Kaick, Hao Zhang, and Hui Huang.  Rpm-net: Recurrent prediction of motion and parts from point cloud.  ACM Transactions on Graphics (Proceedings of SIGGRAPH ASIA 2019), 38(6):240:1–240:15, 2019.
  * [35] Li Yi, Haibin Huang, Difan Liu, Evangelos Kalogerakis, Hao Su, and Leonidas Guibas.  Deep part induction from articulated object pairs.  Transactions on Graphics, 37(6), December 2018.
  * [36] Vicky Zeng, Timothy E Lee, Jacky Liang, and Oliver Kroemer.  Visual Identification of Articulated Object Parts.  arXiv, 2020.
  * [37] Chenyang Zhu, Kai Xu, Siddhartha Chaudhuri, Li Yi, Leonidas J. Guibas, and Hao Zhang.  AdaCoSeg: Adaptive shape co-segmentation with group consistency loss.  In IEEE Computer Vision and Pattern Recognition (CVPR), 2020.