additions

# Python Crypto Misuses in the Wild

Anna-Katharina Wickert  https://orcid.org/0000-0002-1441-2423<EMAIL_ADDRESS>darmstadt.de Technische Universität DarmstadtHochschulstraße
ABDarmstadtGermany ,  Lars Baumgärtner  https://orcid.org/0000-0002-5805-2773
<EMAIL_ADDRESS>Technische Universität
DarmstadtHochschulstraße ABDarmstadtGermany ,  Florian Breitfelder
https://orcid.org/0000-0003-2337-1819<EMAIL_ADDRESS>Technische Universität DarmstadtHochschulstraße ABDarmstadtGermany and  Mira
Mezini  https://orcid.org/0000-0001-6563-7537<EMAIL_ADDRESS>Technische Universität DarmstadtHochschulstraße ABDarmstadtGermany

(2021)

###### Abstract.

Background: Previous studies have shown that up to 99.59 % of the Java apps
using crypto APIs misuse the API at least once. However, these studies have
been conducted on Java and C, while empirical studies for other languages are
missing. For example, a controlled user study with crypto tasks in Python has
shown that 68.5 % of the professional developers write a secure solution for a
crypto task. Aims: To understand if this observation holds for real-world
code, we conducted a study of crypto misuses in Python. Method: We developed a
static analysis tool that covers common misuses of 5 different Python crypto
APIs. With this analysis, we analyzed 895 popular Python projects from GitHub
and 51 MicroPython projects for embedded devices. Further, we compared our
results with the findings of previous studies . Results: Our analysis reveals
that 52.26 % of the Python projects have at least one misuse. Further, some
Python crypto libraries’ API design helps developers from misusing crypto
functions, which were much more common in studies conducted with Java and C
code. Conclusion: We conclude that we can see a positive impact of the good
API design on crypto misuses for Python applications. Further, our analysis of
MicroPython projects reveals the importance of hybrid analyses.

Crypto API, Security, Static Analysis.

††journalyear: 2021††copyright: rightsretained††conference: ACM / IEEE
International Symposium on Empirical Software Engineering and Measurement
(ESEM); October 11–15, 2021; Bari, Italy††booktitle: ACM / IEEE International
Symposium on Empirical Software Engineering and Measurement (ESEM) (ESEM ’21),
October 11–15, 2021, Bari, Italy††doi: 10.1145/3475716.3484195††isbn:
978-1-4503-8665-4/21/10††ccs: Software and its engineering Software libraries
and repositories

##  1\. Introduction

Cryptography, hereafter crypto, is widely used nowadays to protect our data
and ensure confidentiality. For example, without crypto, we would not be able
to securely use online banking or do online shopping. Unfortunately, previous
research results show that crypto is often used in an insecure way
(Chatzikonstantinou et al., 2016; Egele et al., 2013; Kane et al., 2018; Lazar
et al., 2014; Nadi et al., 2016). One such problem is the choice of an
insecure parameter, like an insecure block mode, for crypto primitives like
encryption. Many static analysis tools exist to identify these misuses such as
CryptoREX (Zhang et al., 2019), CryptoLint (Egele et al., 2013),
CogniCryptSAST (Krüger et al., 2018), and Cryptoguard (Rahaman et al., 2019).

While these tools and the respective in-the-wild studies concentrate on Java
and C, user studies suggest that the existing Python APIs reduce the number of
crypto misuses. Acar et al. (Acar et al., 2017b) conducted an experiment with
307 GitHub users which had to solve 3 crypto-related development tasks. They
observed that 68.5 % of the professional developers wrote a secure solution in
Python for the given task. Within a controlled experiment with 256 Python
developers that tried to solve simple crypto tasks, Acar et al. (Acar et al.,
2017a) identified that a simple API design, like the Python library
cryptography, supports developers in writing secure code. However, no
empirical in-the-wild study has yet confirmed that crypto misuses in Python
occur less frequently than in Java or C.

To empirically evaluate crypto misuses in Python, we introduce LICMA, a multi-
language analysis framework with support for 5 different Python crypto APIs
and Java’s JCA API. We provide 5 different rules (Egele et al., 2013) for all
Python APIs and 6 different rules (Egele et al., 2013) for JCA to detect the
most common crypto misuses. With LICMA, we analyzed 895 popular Python apps
from GitHub and 51 MicroPython projects to gain insights into misuses in
Python. We identified that 52.26 % of the Python GitHub apps with crypto
usages have at least one misuse causing 1,501 misuses. In total, only 7 % of
the misuses are within the application code itself, while the remaining
misuses are introduced by dependencies. Further, our study of MicroPython
projects reveals that developers in the embedded domain tend to use crypto via
C code. Thus, revealing the importance of hybrid static analyses, which can
track program information, e.g., a call graph, across multiple languages
(Mushtaq et al., 2017; Ferrara et al., 2019).

Table 1. Six commonly discussed crypto misuses in Java and C (Egele et al., 2013; Zhang et al., 2019) with an example of a violation in Python.  ID |  Rule |  Python: Violation Example
---|---|---
§1 |  Do not use electronic code book (ECB) mode for encryption. |  aes = AES.new(key, AES.MODE_ECB)
§2 |  Do not use a non-random initiliazation vector (IV) for ciphertext block chaining (CBC) encryption. |  aes = AES.new(key, AES.MODE_CBC, b’\0’ * 16)
§3 |  Do not use constant encryption keys. |  aes = AES.new(b’\0’ * 32, AES.MODE_CBC, iv)
§4 |  Do not use constant salts for password-based encryption (PBE). |  kdf = PBKDF2HMAC(hashes.SHA256(), 32, b’\0’ * 32, 10000)
§5 |  Do not use fewer than 1,000 iterations for PBE. |  kdf = PBKDF2HMAC(hashes.SHA256(), 32, salt, 1)
§6 |  Do not use static seeds to initialize secure random generator. |  Due to API design only possible in Java (Egele et al., 2013) and C/C++ (Zhang et al., 2019)

To further improve our understanding whether Python APIs are less prone to
crypto misuses, we make the following contributions:

  * •

A novel, multi-language analysis tool to detect crypto misuses in Python and
Java. For Python we cover crypto misuses for 5 common Python crypto APIs and
for Java the standard API JCA.

  * •

An empirical study of crypto misuses in the 895 most popular Python
applications on GitHub revealing 1,501 misuses.

  * •

A comparison of our findings in Python applications with previous studies
about crypto misuses in-the-wild for Android Apps and firmware images in C. We
observed that most Python applications are more secure and the distribution
between the concrete types of misuses differ a lot.

  * •

An empirical study of crypto misuses in MicroPython projects which reveals the
importance of hybrid static analyses.

  * •

A replication package including both data sets used for our study, the results
of our analysis, and the code of LICMA111
dx.doi.org/10.6084/m9.figshare.16499085.

##  2\. Background

Crypto libraries enable developers to use crypto primitives, like symmetric
key encryption or password-based encryption (PBE), in their application.
However, studies have shown that developers struggle to use those APIs
correctly and securely. For example, Krüger et al. (Krüger et al., 2018) show
that 95 % of the Android applications using crypto have at least one crypto
misuse. In the remainder of the paper, we define a crypto misuse, in short
misuse, as a usage of a crypto library which is a formally correct use of the
API, e.g., not causing a crash, but is unsafe. In this paper, we focus on six
commonly discussed crypto misuses (Egele et al., 2013; Zhang et al., 2019)
which we will introduce next. All rules including Python example code can be
seen in Table 1.

For AES encryption, a block mode is used to combine several blocks for
encryption and decryption. However, some block modes are considered insecure
by experts. Rule 1 (§1) and rule 2 (§2) cover two insecure usages of block
modes. §1 prohibits the usage of ECB which is deterministic and not secure. §2
focus on a non-random initialization vector (IV) for the block mode CBC. Due
to the predictability of the IV, the usage of CBC is deterministic and not
secure. Further, a key protects confidential information. Thus, rule 3 (§3)
states that the key should be confidential and not a static one hard-coded in
the source.

For PBE, a salt and the number of iterations harden the password against
dictionary attacks. Rule 4 (§4) highlights that a non-random salt reduces the
security of the crypto primitive to using no salt, which is considered
insecure. Rule 5 (§5) concentrates on the fact that several iterations are
required to harden the crypto primitive against attacks. Thus, Egele et al.
(Egele et al., 2013) suggest the minimum recommended value of 1,000 iterations
as defined in the PBE standard PKCS#5.

A seed can ensure that the output of a random number generator is non-
deterministic. Rule 6 (§6) covers that static seeds lead to deterministic
outputs. Common Java (Egele et al., 2013) and C/C++ (Zhang et al., 2019)
libraries expect a seed, while the analyzed Python APIs avoid this by design.

##  3\. Design and Implementation of LICMA

In this section, we describe the design of our static analysis tool LICMA, and
discuss the implementation in more detail.

set color list=white, white, white, white, uniform arrow color=true, arrow
color=gray, back arrow disabled=true, module minimum width=3cm, circular
distance=6cm, module x sep=4cm, text width=3cm, additions= additional item
offset=1cm, additional item fill color=white, additional item border
color=gray, additional arrow color=gray, additional item width=2cm, additional
item height=1cm, additional item text width=2cm, additional item bottom
color=gray, additional item shadow=drop shadow, [flow
diagram:horizontal]Input: source file, Parsing with Babelfish, LICMA analysis,
Output: CSV file with misuses below of module2/Java analysis component, below
of module3/Python analysis component, below of module4/… ¡-module3/additional-
module1 ¡-module3/additional-module2 ¡-module3/additional-module3

Figure 1. LICMA analysis framework.

###  3.1. Design

A general overview of LICMA is given in Figure 1. First, we parse a source
code file into the respective Abstract Syntax Tree (AST). More specifically,
we use Babelfish 222https://github.com/bblfsh/bblfshd to create a Universal
Abstract Syntax Tree (UAST) which combines language-independent AST elements
with language-specific elements. For simplicity, we use the term AST in the
remainder of the paper. Second, we apply the LICMA analysis upon the AST to
identify potential misuses of our crypto rules.

Based upon the rule defining a misuse, the analysis checks for a violation of
the rule within the source code and triggers a backward analysis for this
task. The backward slice is created by filtering the AST with the help of
XPath333https://www.w3.org/TR/xpath/ queries, and works as follows: First, the
backward slicing algorithm (BSA) identifies all source code lines that are
referred within the respective rule. An example of the slicing criterion is a
function call parameter like the key for a crypto function. Second, the BSA
determines for all function calls if the parameter is either hard-coded, a
local assignment, or a global assignment. If one of the three cases is
fulfilled, the corresponding value is returned. This value is checked against
a function defined in the rule, e.g., if the value is smaller than 1,000 for
§5. In the negative case, the BSA looks for the caller of the function, and
checks the caller’s parameters as described above. The algorithm stops if a
value is returned or no further callers to analyse are available, and returns
the result of the analysis. For its reports, LICMA distinguishes between a
potential misuse if it can not resolve the value of interest due to missing
callers, and a definite misuse if it is resolved to an insecure option.

###  3.2. Implementation

For our study, we implemented Python and Java analysis components. For Python,
we cover 5 different crypto modules: cryptography, M2Crypto, PyCrypto, PyNaCl,
ucryptolib. This selection is based upon the inspected Python modules by Acar
et al. (Acar et al., 2017a) which is based on the libraries’ popularity, their
possibility to solve common crypto tasks, and a mix of usability focus, e.g.,
API-design with ignoring usability up to usability as a main focus. However,
we dropped the deprecated module Keyczar, and added the MicroPython library
ucryptolib.

As the six rules are defined with the JCA in mind (Egele et al., 2013), we
could not implement all of these rules for Python. For none of the Python
modules, a misuse of §6 is possible due to the design of the APIs as there are
no secure random number generators present that can be initialized with a
static seed.

Further, LICMA supports only §3 and §4 for PyNaCl and only §1, §2 and §3 for
ucryptolib. The derivation is due to a different API design which avoids the
respective misuses. We present an overview of the implemented APIs and the
covered rules in Table 2.

Our implementation of LICMA is available on GitHub444https://github.com/stg-
tud/licma.

Table 2. An overview of the libraries supported in LICMA and the rules of
potential misuses.

Library | §1 | §2 | §3 | §4 | §5 | §6
---|---|---|---|---|---|---
JCA | ● | ● | ● | ● | ● | ●
cryptography | ● | ● | ● | ● | ● | ○
M2Crypto | ● | ● | ● | ● | ● | ○
PyCrypto | ● | ● | ● | ● | ● | ○
PyNaCI | ○ | ○ | ● | ● | ○ | ○
ucryptolib | ● | ● | ● | ○ | ○ | ○

● indicated that the library can cover misuses of the rule, while
○ indicates that this misuse is not possible through the API.

##  4\. Methodology

To analyze Python applications, we constructed two distinct data sets of
popular Python and MicroPython projects. Furthermore, we compared our findings
in Python programs with previous studies about Java and C code.

###  4.1. Searching and Downloading Python Apps

Both data sets represent very different domains where Python is used, ranging
from server and desktop use to low-level embedded code. How we selected the
projects in both data sets for our empirical study is described in the
following.

####  4.1.1. Python Projects from GitHub

For our evaluation of crypto misuses in Python code we focus on open-source
code. Thus, we crawled and downloaded the top 895 Python repositories from
GitHub sorted by stars. To further understand the influence of dependencies,
we downloaded them with Pythons standard dependency manager pip for each
project. Afterwards, we ended up with 14,442 Python packages of which 3,420
are unique.

As our analysis works upon a per-file basis, we reduced our set to only those
source code files that include the function calls referenced in our rules,
e.g., AES.new(…). In addition, we filter for production code and ignore test
code which should be non-existent during the execution of the application.
After applying these 2 filter steps, we ended up with 946 source files from
155 different repositories. Unfortunately, Babelfish was unable to parse 35 of
these files, and reached the maximum recursion depth for the AST XPath queries
for at least one rule in 50 files. These 85 parsing failures are distributed
amongst 61 different projects. However, for each of the projects at least 1
file with a crypto usage was analyzed successfully. In total, we successfully
analyzed 861 different files within 155 Python repositories with LICMA.

####  4.1.2. Curated Top MicroPython Projects

As an extension to our Python application set, we crawled 51 MicroPython
projects which are stated as the top announced MicroPython
projects555https://awesomeopensource.com/projects/micropython. Like for the
regular Python applications, we downloaded all dependencies with pip and got
113 dependencies with 1 duplicate dependency. Afterwards, we applied the same
filter steps as before: The usage of crypto and the exclusion of test files.
These steps, resulted in 5 files which seem to use the Python crypto libraries
supported by LICMA. Note that we included the MicroPython crypto library
ucryptolib in LICMA and our filtering steps. To further understand this small
number of potential usages, we also analyzed our data set of MicroPython
applications manually. This analysis reveals that we potentially missed five
crypto usages.

###  4.2. Comparison with Previous Studies

To understand the differences between crypto misuses for §1 to §6, cf. Table
1, in Python and previous studies in Java, with the analysis CryptoLint,
(Egele et al., 2013) and C/C++, with the analysis CryptoREX, (Zhang et al.,
2019), we compared the reported results. As we concentrated on the same rule
set, we only need a few adjustments to compare the results. First, for our
meta-analysis we exclude §6 since the 5 analyzed Python modules avoid this
misuse by design. Second, we merge the results for §1 of Egele et al. (Egele
et al., 2013) as they split their result into two different cases: The
explicit use of the block mode ECB on one side and the implicit use of this
block mode due to the API design on the other. Third, due to the design of our
analysis, we only consider definite findings. CryptoLint and CryptoREX do not
distinguish between potential misuses and definite ones. Fourth, to enable a
fair comparison, we compare only percentages rather than absolute numbers, as
we are interested in the general distribution and the influence of API design
on crypto misuses. We choose to compare the studies on the percentage of
applications using crypto and having at least one misuse of a respective rule
as introduced by Egele et al. (Egele et al., 2013). Unfortunately, Zhang et
al. (Zhang et al., 2019) only reports details for the successfully unpacked
firmware images before filtering for crypto usages.

##  5\. Evaluation

In this Section, we present our evaluation of crypto misuses in real-world
Python applications from GitHub and MicroPython projects.

###  5.1. GitHub Python Projects

Overall, LICMA identified 1,501 possible misuses in our data set of Python
applications attributed to 81 repositories. Thus, 52.26 % of the 155 analyzed
Python applications that contain crypto usages have at least one misuse.

As discussed in Section 3.1, we distinguish between potential and definite
misuses. While a potential misuse requires a manual inspection to decide
whether it is harmful, a definite misuse indicates that the analysis was able
to resolve the respective crypto parameter. Thus, we know that a rule of LICMA
is definitely violated by the respective API call. We identified 85 definite
misuses which could be identified within one class file and thus are local.
The remaining 1,416 misuses are potential misuses.

Figure 2. Python projects with 30 or more misuses.

Observation 1 In total, 52.26 % of the Python projects using crypto APIs
contain at least a potential misuse. Only 5.66 % of the misuses are local
(within one class file).

####  5.1.1. Dependencies

From the 1,501 misuses, only 7.00 % are within the application code and not in
dependencies. These misuses are within 14.81 % of the applications with at
least one misuse. The remaining misuses are found in dependencies and can be
reduced to 290 unique misuses. Thus, developers introduce most of their
misuses by using dependencies rather than using the respective crypto library
directly. In total, only 12 projects are affected by misuses in the
application code itself.

To understand the influence of dependencies within the applications with the
most misuses, we inspected the 10 Python projects with more than 30 misuses.
Figure 2 confirms the previous observation that most of the misuses are in
dependencies and only a few projects use a crypto library directly. The Scapy
repository666 https://github.com/secdev/scapy is an exception as all misuses
are in its code. Our investigation reveals that this repository is often used
as a dependency by other projects. Thus, these findings can be attributed to
dependencies as well.

While, the previous results focused on the projects, we also inspected the
dependencies causing most of the misuses. In total, 5 of the observed
dependencies are responsible for a misuse in more than 10 different projects.
For 34 projects we observe a misuse within the repository Scapy which was the
only analyzed repository in Figure 2 without any misuse in its dependencies.
Thus, confirming our previous observation about this project.

Observation 2 Only 14.81 % of the projects directly contain a misuse of a
crypto API. The rest is introduced through third-party code. Thus, it is
important for developers and analysts to understand the security implications
of the libraries used.

####  5.1.2. Rules and Python Cryptographic Libraries

In order to get a better understanding of the underlying reasons of the
misuses, we evaluated how often a misuse per rule and library occurs (Fig. 3).
Our analysis reveals that most of the misuses are related to the use of
different block modes, §1 and §2, of the M2Crypto library, and constant
encryption keys, §3, for the cryptography library. We assume that the few
numbers of misuses of §1 and §2 of cryptography are due to the design of the
library. The library suggests to use a high-level symmetric encryption class,
called Fernet, instead of the low-level symmetric encryption classes which
would enable the respective misuses. Most of the misuses due to insecure PBE
configurations, §4 and §5, are by developers using the library PyCrypto.
While, none of the 3 previously mentioned libraries make it impossible to
produce a misuse of one of our 5 rules, the library PyNaCl completely prevents
misuses for §1, §2, and §5. In our study, we found only 2 instances of a
misuse due to a constant encryption key for PyNaCl.

Figure 3. The number of misuses found per rule for the Python libraries
cryptography, M2Crypto, PyCrypto, PyNaCl. The later library avoids per design
misuses for §1, §2 and §5.

Observation 3 The design of the Python crypto API cryptography supports
developers in avoiding misuses due to an insecure block mode for AES
encryption.

####  5.1.3. Reasons for Definite Misuses

Among the definite misuses, there is at least one misuse for all previously
discussed rules. We identified 13 definite misuses in 5 different projects
which use the ECB encryption mode (§1). In all cases, the mode is passed
explicitly with the parameter and not implicitly as in Java (Egele et al.,
2013). For 8 misuses we observed that a static IV is used, e.g. zero bytes,
and thus resulting in an insecure encryption with the block mode CBC (§2).
Furthermore, we identified that the scapy project which is also commonly used
as a dependency uses a constant encryption key resulting in 14 misuses (§3).
For example, we found a zero byte-array as key.

For password-based encryption, we identified 18 misuses within 14 projects
which pass a static salt instead of a randomly generated one (§4). In total,
we identify 32 misuses which are due to requesting only 1 iteration instead of
an value greater than 1,000 as recommended (§5). Thus, the process of
generating a password is faster but very insecure, e.g., due to dictionary
attacks.

Observation 4 As a result of 58.82 % of the definite misuses, passwords are
vulnerable to dictionary attacks (§4 and §5).

###  5.2. MicroPython

When we applied LICMA upon the 5 source files containing crypto API usages of
the MicroPython data set, we identified no misuse. For this reason, we
inspected the MicroPython repositories for usages of other crypto functions
not covered by LICMA and identified 5 additional files. We notice that the
crypto module ucryptolib which is provided by MicroPython, is only used by
tests in 2 projects. For the remaining 3 findings, the crypto functions are
written in C rather than Python. Thus, these files were removed due to our
filter steps described in Section 4.1.2.

Our small analysis of MicroPython projects shows that for a further
exploration of MicroPython applications we need to consider custom
implementations of AES in Python and C. This seems to be a common pattern for
embedded code where performance is important and low-level code is often
shipped as custom C blobs. Thus, we can observe the importance of hybrid
analyses approaches (Ferrara et al., 2019; Mushtaq et al., 2017).

##  6\. Comparison with previous Studies

Figure 4. Comparison of our evaluation results with the results of CryptoLint
(Egele et al., 2013) and CryptoREX (Zhang et al., 2019).

As one motivation of this paper was to empirically shed light on the question
whether Python crypto libraries help developers in writing more secure code
than previous empirical studies in Java or C have revealed, we compare our
results to the findings of these studies. For all applications which use
crypto, we observe more secure applications than reported by Egele et al.
(Egele et al., 2013). While for Android apps using crypto libraries at least
one misuse occurs in 87.90 % of the apps, we observe ”only” 52.26 % of Python
applications with a misuse. Unfortunately, Zhang et al. (Zhang et al., 2019)
only report the number of C firmware images they started to analyze and not
explicitly mention how many of these actually use a crypto API. Thus, we only
know that 24.18 % of the analyzed firmware images have at least one misuse.

In Figure 4 we present the percentage of applications per study and per rule
with a misuse. In general, we observed that misuses in Python occur less
frequently than for Java and C. The misuse of ECB as an encryption mode is the
most-misused in Java and C, and is significantly less with 3.23 % of the
Python applications. We hypothesize that this difference is due to the design
of the libraries as discussed in Section 5.1.

Observation 5 Our comparison reveals that the design of the crypto APIs in
Python helps developers to avoid common misuses on the use of block modes for
AES encryption in their code.

##  7\. Threats to Validity

We evaluated top GitHub Python projects and it may be that our results fail to
generalize on specialized Python applications.For our data set on MicroPython
applications, we also concentrated on popular projects. Thus, our insights may
not generalize to less popular or closed-source projects. However, we believe
that our results provide first interesting insights on crypto misuses in
Python.

Currently, our analysis is limited to capabilities of Babelfish, especially
the recursive maximum depth of its filter function. Furthermore, currently
Babelfish only creates an AST for a single file. Thus, our analysis fails to
resolve misuse over multiple files. We hope that these limitations can be
lifted through further development of Babelfish. These improvements will
hopefully help to reduce the number of false-positives in the potential
misuses. Furthermore, it may be that our static analysis missed some misuses
as Python is a dynamic typed language.

We compare different application types of studies conducted in different
years. Thus, it may be that the results might change when conducted on the
same kind of applications now. Further, the results may differ due to the
effect of different application domains and different analysis frameworks.
Moreover, the percentages of applications with at least one misuse per rule
that we used from Zhang et al. (Zhang et al., 2019) might be too positive for
C, as the number of firmware images with crypto usages is not explicitly
reported.

##  8\. Related Work

Several, previous studies show that crypto misuses occur frequently in
different languages and platforms. Egele et al. (Egele et al., 2013), Krüger
et al. (Krüger et al., 2018), Rahaman et al. (Rahaman et al., 2019), and
Hazhirpasand et al. (Hazhirpasand et al., 2020) analyzed Java and Android
applications. They reported that 84.78 % up to 99.59 % of the applications
using crypto have at least one misuse. Zhang et al. (Zhang et al., 2019)
analyzed Internet of Things (IoT) device firmwares written in C/C++, from
which 24.2 % contain at least one misuse.

Previous work introducing new crypto misuse analyses either improve static
analysis approaches for crypto misuse detection or introduce these to new
languages imposing new challenges. CryptoLint (Egele et al., 2013) is the
first (closed-source) static analysis for crypto misuses for Android
applications introducing the six rules for crypto misuses, c.f. Table 1. While
this analysis is built upon a deny-listing approach, CogniCryptSAST (Krüger et
al., 2018) introduces an allow-listing approach covering the standard Java
library, BouncyCastle and Tink to analyze Java and Android applications for
misuses. The focus of the analysis Cryptoguard (Rahaman et al., 2019) is a
scalable deny-listing Java analysis for crypto misuses extending the rules
implemented in CryptoLint (Egele et al., 2013). CryptoREX is a framework for
firmware written in C/C++ which covers the rules introduces by CryptoLint
(Egele et al., 2013).

Acar et al. (Acar et al., 2017a) conducted a user study with 5 different
Python crypto APIs to analyze how developers perform on 5 crypto tasks with a
pre-selected API. Their study reveals that APIs with a usability focus for
security result in significant more secure code. In a similar study, Acar et
al. (Acar et al., 2017b) analyzed the security of 3 different crypto tasks and
identified that more usable libraries resulted only in insecure solutions for
encryption in 12.7 % of the cases.

##  9\. Conclusion

In this paper, we presented the first empirical study of crypto misuses in
Python. To conduct the study, we implemented the first multi-language analysis
tool for crypto misuses with rules to detect common misuses of five different
Python libraries as well as the standard Java library. We analyzed 895 popular
Python apps from GitHub and 51 MicroPython projects to identify misuses. Our
analysis revealed that 52.26 % of the projects using a crypto API, misuse the
respective library. Furthermore, we observed that only 7 % of the 1,501
misuses are within the application code. The analysis of embedded applications
written in MicroPython revealed the importance of hybrid analysis as the only
crypto calls were in C code that got shipped with the projects.

To get an impression on the differences between the different domains and
languages analyzed in previous studies, we compared our results against the
misuses reported for Android apps (Egele et al., 2013) and C firmware images
(Zhang et al., 2019). Our comparison confirms the impression that an
opinionated API design actually helps developers avoiding misuses.

While we concentrated on the impact of a user-friendly API design for Python,
future work can verify if these results generalize to other languages, like
Rust and Go. Thus, extending LICMA with new languages. Further, it may be
interesting to extend the currently implemented rules in LICMA by an in-depth
analysis of misuses of Python crypto APIs.

## Acknowledgments

This research work has been co-funded by the Deutsche Forschungsgemeinschaft
(DFG) – SFB 1119 CROSSING (236615297) and SFB 1053 MAKI (210487104), by the
German Federal Ministry of Education and Research and the Hessen State
Ministry for Higher Education, Research and the Arts within their joint
support of the National Research Center for Applied Cybersecurity ATHENE, by
the LOEWE initiative (Hesse, Germany) within the emergenCITY center.

## References

  * (1)
  * Acar et al. (2017a) Yasemin Acar, Michael Backes, Sascha Fahl, Simson Garfinkel, Doowon Kim, Michelle L Mazurek, and Christian Stransky. 2017a.  Comparing the usability of cryptographic apis. In _IEEE Symposium on Security and Privacy (SP)_. IEEE, 154–171.
  * Acar et al. (2017b) Yasemin Acar, Christian Stransky, Dominik Wermke, Michelle L Mazurek, and Sascha Fahl. 2017b.  Security developer studies with github users: Exploring a convenience sample. In _Symposium on Usable Privacy and Security (SOUPS)_. 81–95.
  * Chatzikonstantinou et al. (2016) Alexia Chatzikonstantinou, Christoforos Ntantogian, Georgios Karopoulos, and Christos Xenakis. 2016\.  Evaluation of cryptography usage in android applications. In _EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS)_. 83–90.
  * Egele et al. (2013) Manuel Egele, David Brumley, Yanick Fratantonio, and Christopher Kruegel. 2013.  An empirical study of cryptographic misuse in android applications. In _ACM SIGSAC conference on Computer & communications security (CCS)_, Ahmad-Reza Sadeghi, Virgil Gligor, and Moti Yung (Eds.). ACM, 73–84.
  * Ferrara et al. (2019) Pietro Ferrara, Amit Kr Mandal, Agostino Cortesi, and Fausto Spoto. 2019.  Cross-programming language taint analysis for the iot ecosystem.  _Electronic Communications of the EASST_ 77 (2019).
  * Hazhirpasand et al. (2020) Mohammadreza Hazhirpasand, Mohammad Ghafari, and Oscar Nierstrasz. 2020.  Java Cryptography Uses in the Wild. In _ACM / IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM)_. ACM, Article 40.
  * Kane et al. (2018) Christopher Kane, Bo Lin, Saksham Chand, and Yanhong A. Liu. 2018\.  High-level Cryptographic Abstractions.  _CoRR_ abs/1810.09065 (2018).  arXiv:1810.09065 http://arxiv.org/abs/1810.09065
  * Krüger et al. (2018) Stefan Krüger, Johannes Späth, Karim Ali, Eric Bodden, and Mira Mezini. 2018\.  CrySL: An Extensible Approach to Validating the Correct Usage of Cryptographic APIs. In _European Conference on Object-Oriented Programming (ECOOP)_ _(Leibniz International Proceedings in Informatics (LIPIcs))_ , Vol. 109. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 10:1–10:27.
  * Lazar et al. (2014) David Lazar, Haogang Chen, Xi Wang, and Nickolai Zeldovich. 2014.  Why does cryptographic software fail? A case study and open problems. In _Asia-Pacific Workshop on Systems_. 1–7.
  * Mushtaq et al. (2017) Zaigham Mushtaq, Ghulam Rasool, and Balawal Shehzad. 2017\.  Multilingual source code analysis: A systematic literature review.  _IEEE Access_ 5 (2017), 11307–11336.
  * Nadi et al. (2016) Sarah Nadi, Stefan Krüger, Mira Mezini, and Eric Bodden. 2016.  Jumping through hoops: Why do Java developers struggle with cryptography APIs?. In _International Conference on Software Engineering (ICSE)_. 935–946.
  * Rahaman et al. (2019) Sazzadur Rahaman, Ya Xiao, Sharmin Afrose, Fahad Shaon, Ke Tian, Miles Frantz, Murat Kantarcioglu, and Danfeng Yao. 2019\.  Cryptoguard: High precision detection of cryptographic vulnerabilities in massive-sized java projects. In _ACM SIGSAC Conference on Computer and Communications Security_. 2455–2472.
  * Zhang et al. (2019) Li Zhang, Jiongyi Chen, Wenrui Diao, Shanqing Guo, Jian Weng, and Kehuan Zhang. 2019\.  CryptoREX: Large-scale Analysis of Cryptographic Misuse in IoT Devices. In _International Symposium on Research in Attacks, Intrusions and Defenses (RAID)_. USENIX Association, 151–164.


# Vectorized VByte Decoding

Jeff Plaisance
Indeed
<EMAIL_ADDRESS>Nathan Kurz
Verse Communications
<EMAIL_ADDRESS>Daniel Lemire
LICEF, Université du Québec
<EMAIL_ADDRESS>
###### Abstract

We consider the ubiquitous technique of VByte compression, which represents
each integer as a variable length sequence of bytes. The low 7 bits of each
byte encode a portion of the integer, and the high bit of each byte is
reserved as a continuation flag. This flag is set to 1 for all bytes except
the last, and the decoding of each integer is complete when a byte with a high
bit of 0 is encountered. VByte decoding can be a performance bottleneck
especially when the unpredictable lengths of the encoded integers cause
frequent branch mispredictions. Previous attempts to accelerate VByte decoding
using SIMD vector instructions have been disappointing, prodding search
engines such as Google to use more complicated but faster-to-decode formats
for performance-critical code. Our decoder (Masked VByte) is 2 to 4 times
faster than a conventional scalar VByte decoder, making the format once again
competitive with regard to speed.

##  1 Introduction

In many applications, sequences of integers are compressed with VByte to
reduce memory usage. For example, it is part of the search engine Apache
Lucene (under the name vInt). It is used by Google in its Protocol Buffers
interchange format (under the name Varint) and it is part of the default API
in the Go programming language. It is also used in databases such as IBM DB2
(under the name Variable Byte) [1].

We can describe the format as follows. Given a non-negative integer in binary
format, and starting from the least significant bits, we write it out using
seven bits in each byte, with the most significant bit of each byte set to 0
(for the last byte), or to 1 (in the preceding bytes). In this manner,
integers in $[0,2^{7})$ are coded using a single byte, integers in
$[2^{7},2^{14})$ use two bytes and so on. See Table 1 for examples.

The VByte format is applicable to arbitrary integers including 32-bit and
64-bit integers. However, we focus on 32-bit integers for simplicity.

Table 1: VByte form for various powers of two. Within each word, the most significant bits are presented first. In the VByte form, the most significant bit of each byte is in bold.  integer | binary form (16 bits) | VByte form
---|---|---
1 | 0000000000000001 |  00000001
2 | 0000000000000010 |  00000010
4 | 0000000000000100 |  00000100
128 | 0000000010000000 |  10000000, 00000001
256 | 0000000100000000 |  10000000, 00000010
512 | 0000001000000000 |  10000000, 00000100
16384 | 0100000000000000 |  10000000, 10000000, 00000001
32768 | 1000000000000000 |  10000000, 10000000, 00000010

### Differential coding

A common application in information retrieval is to compress the list of
document identifiers in an inverted index [5]. In such a case, we would not
code directly the identifiers ($x_{1},x_{2},\ldots$), but rather their
successive differences (e.g., $x_{1}-0,x_{2}-x_{1},\ldots$), sometimes called
deltas or gaps. If the document identifiers are provided in sorted order, then
we might expect the gaps to be small and thus compressible using VByte. We
refer to this approach as _differential coding_. There are several possible
approaches to differential coding. For example, if there are no repeated
values, we can subtract one from each difference
($x_{1}-0,x_{2}-x_{1}-1,x_{3}-x_{2}-1,\ldots$) or we can subtract blocks of
integers for greater speed
($x_{1},x_{2},x_{3},x_{4},x_{5}-x_{1},x_{6}-x_{2},x_{7}-x_{3},x_{8}-x_{4},\ldots$).
For simplicity, we only consider gaps defined as successive differences
($x_{2}-x_{1},\ldots$). In this instance, we need to compute a prefix sum over
the gaps to recover the original values (i.e.,
$x_{i}=(x_{i}-x_{i-1})+x_{i-1}$).

##  2 Efficient VByte Decoding

One of the benefits of the VByte format is that we can write an efficient
decoder using just a few lines of code in almost any programming language. A
typical decoder applies Algorithm 1. In this algorithm, the function readByte
provides byte values in $[0,2^{8})$ representing a number $x$ in the VByte
format.

Processing each input byte requires only a few inexpensive operations (e.g.,
two additions, one shift, one mask). However, each byte also involves a
branch. On a recent Intel processor (e.g., one using the Haswell
microarchitecture), a single mispredicted branch can incur a cost of 15 cycles
or more. When all integers are compressed down to one byte, mispredictions are
rare and the performance is high. However, when both one and two byte values
occur in close proximity the branch may become less predictable and
performance may suffer.

For differential coding, we modify this algorithm so that it decodes the gaps
and computes the prefix sum. It suffices to keep track of the last value
decoded and add it to the decoded gap.

1: $y\leftarrow$ empty array of 32-bit integers

2: while input bytes are available do

3: $b\leftarrow\textrm{{readByte}}()$

4: if $b<128$ then append $b$ to $y$ and continue

5: $c\leftarrow b\bmod 2^{7}$

6: $b\leftarrow\textrm{{readByte}}()$

7: if $b<128$ then append $c+b\times 2^{7}$ to $y$ and continue

8: $c\leftarrow c+(b\bmod 2^{7})\times 2^{7}$

9: $b\leftarrow\textrm{{readByte}}()$

10: if $b<128$ then append $c+b\times 2^{14}$ to $y$ and continue

11: $c\leftarrow c+(b\bmod 2^{7})\times 2^{14}$

12: $b\leftarrow\textrm{{readByte}}()$

13: if $b<128$ then append $c+b\times 2^{21}$ to $y$ and continue

14: $c\leftarrow c+(b\bmod 2^{7})\times 2^{21}$

15: $b\leftarrow\textrm{{readByte}}()$

16: append $c+b\times 2^{28}$ to $y$

17: return $y$

Algorithm 1 Conventional VByte decoder. The continue instruction returns the
execution to the main loop. The readByte function returns the next available
input byte.

##  3 SIMD Instructions

Intel processors provide SIMD instructions operating on 128-bit registers
(called _XMM registers_). These registers can be considered as vectors of two
64-bit integers, vector2 of four 32-bit integers, vectors of eight 16-bit
integers or vectors of sixteen 8-bit integers.

We review the main SIMD instructions we require in Table 2. We can roughly
judge the computational cost of an instruction by its latency and reciprocal
throughput. The latency is the minimum number of cycles required to execute
the instruction. The latency is most important when subsequent operations have
to wait for the instruction to complete. The reciprocal throughput is the
inverse of the maximum number of instructions that can be executed per cycle.
For example, a reciprocal throughput of 0.5 means that up to two instructions
can be executed per cycle.

We use the movdqu instruction to load or store a register. Loading and storing
registers has a relatively high latency (3 cycles). While we can load two
registers per cycle, we can only store one of them to memory. A typical SIMD
instruction is paddd: it adds two vectors of four 32-bit integers at once.

Sometimes it is necessary to selectively copy the content from one XMM
register to another while possibly copying and duplicating components to other
locations. We can do so with the pshufd instruction when considering the
registers as vectors of 32-bit integers, or with the pshufb instruction when
registers is considered vectors of bytes. These instructions take an input
register $v$ as well as a control mask $m$ and they output a new vector
$(v_{m_{0}},v_{m_{1}},v_{m_{2}},v_{m_{3}},\ldots)$ with the added convention
that $v_{-1}\equiv 0$. Thus, for example, the pshufd instruction can copy one
particular value to all positions (using a mask made of 4 identical values).
If we wish to shift by a number of bytes, it can be more efficient to use a
dedicated instruction (psrldq or pslldq) even though the pshufb instruction
could achieve the same result. Similarly, we can use the pmovsxbd instruction
to more efficiently unpack the first four bytes as four 32-bit integers.

We can simultaneously shift right by a given number of bits all of the
components of a vector using the instructions psrlw (16-bit integers), psrld
(32-bit integers) and psrlq (64-bit integers). There are also corresponding
left-shift instructions such as psllq. We can also compute the bitwise OR and
bitwise AND between two 128-bit registers using the por and pand instructions.

There is no instruction to shift a vector of 16-bit integers by different
number of bits (e.g., $(v_{1},v_{2},\ldots)\to(v_{1}\ll 1,v_{2}\ll 2,\ldots)$)
but we can get the equivalent result by mutiplying integers (e.g., with the
pmullw instruction). The AVX2 instruction set introduced such flexible shift
instructions (e.g., vpsrlvd), and they are much faster than a multiplication,
but they not applicable to vectors of 16-bit integers. Intel proposed a new
instruction set (AVX-512) which contains such an instruction (vpsrlvw) but it
is not yet publicly available.

Our contribution depends crucially on the pmovmskb instruction. Given a vector
of sixteen bytes, it outputs a 16-bit value made of the most significant bit
of each of the sixteen input bytes: e.g., given the vector
$(128,128,\ldots,128)$, pmovmskb would output 0xFFFF.

Table 2: Relevant SIMD instructions on _Haswell_ Intel processors with latencies and reciprocal throughput in CPU cycles . instruction |  description | latency |  rec. throughput
---|---|---|---
movdqu |  store or retrieve a 128-bit register | 3 | 1/0.5
paddd |  add four pairs of 32-bit integers | 1 | 0.5
pshufd |  _shuffle_ four 32-bit integers | 1 | 1
pshufb |  _shuffle_ sixteen bytes | 1 | 1
psrldq |  shift right by a number of bytes | 1 | 0.5
pslldq |  shift left by a number of bytes | 1 | 0.5
pmovsxbd |  unpack the first four bytes into four 32-bit ints. | 1 | 0.5
pmovsxwd |  unpack the first four 16-bit integers into four 32-bit ints. | 1 | 0.5
psrlw |  shift right eight 16-bit integers | 1 | 1
psrld |  shift right four 32-bit integers | 1 | 1
psrlq |  shift right two 64-bit integers | 1 | 1
psllq |  shift left two 64-bit integers | 1 | 1
por |  bitwise OR between two 128-bit registers | 1 | 0.33
pand |  bitwise AND between two 128-bit registers | 1 | 0.33
pmullw |  multiply eight 16-bit integers | 5 | 1
pmovmskb |  create a 16-bit mask from the most significant bits | 3 | 1

##  4 Masked VByte decoding

The conventional VByte decoders algorithmically process one input byte at a
time (see Algorithm 1). To multiply the decoding speed, we want to process
larger chunks of input data at once. Thankfully, commodity Intel and AMD
processors have supported _Single instruction, multiple data_ (SIMD)
instructions since the introduction of the Pentium 4 in 2001. These
instructions can process several words at once, enabling _vectorized_
algorithms.

Stepanov et al. [4] used SIMD instructions to accelerate the decoding of VByte
data (which they call varint-SU). According to their experimental results,
SIMD instructions lead to a disappointing speed improvement of less than
$25\text{\,}\mathrm{\char 37\relax}$, with no gain at all in some instances.
To get higher speeds (e.g., an increase of $3\times$), they proposed instead
new formats akin to Google’s Group Varint [2]. For simplicity, we do not
consider such “Group” alternatives further: once we consider different data
format, a wide range of fast SIMD-based compression schemes become available
[3]—some of them faster than Stepanov et al.’s fastest proposal.

Though they did not provide a detailed description, Stepanov et al.’s approach
resembles ours in spirit. Consider the simplified example from Fig. 1. It
illustrates the main steps:

  * •

From the input bytes, we gather the control bits (1,0,1,0,0,0 in this case)
using the pmovmskb instruction.

  * •

From the resulting mask, we look up a _control mask_ in a table and apply the
pshufb instruction to move the bytes. In our example, the first 5 bytes are
left in place (at positions 1, 2, 3, 4, 5) whereas the 5th byte is moved to
position 7. Other output bytes are set to zero.

  * •

We can then extract the first 7 bits of the low bytes (at positions 1, 3, 5,
7) into a new 8-byte register. We can also extract the high bytes (positions
2, 4, 6, 8) into another 8-byte register. On this second register, we apply a
right shift by 1 bit on the four 16-bit values (using psrlw). Finally, we
compute the bitwise OR of these two registers, combining the results from the
low and high bits.

100000000000000110000010000000110001000000100000Compressed data (6
bytes)101000Mask (6 bits) Extract mask (pmovmskb)
1000000000000001100000100000001100010000000000000010000000000000 Permute
(pshufb) using mask and look-up table Permuted bytes low byteshigh
bytes1000000000000000100000100000000100010000000000000010000000000000 Decoded
values from the permuted bytes by extracting the 4 low and 4 high bytes with
masks, shifting down by 1 bit the high bytes and ORing. Integers 128, 386, 16,
32

Figure 1: Simplified illustration of vectorized VByte decoding from 6 bytes to
four 16-bit integers (128, 386, 16, 32).

A naïve implementation of this idea could be slow. Indeed, we face several
performance challenges:

  * •

The pmovmskb instruction has a relatively high latency (e.g., 3 cycles on the
Haswell microarchitecture).

  * •

The pmovmskb instruction processes 16 bytes at once, generating a 16-bit
result. Yet looking up a 16-bit value in a table would require a 65536-value
table. Such a large table is likely to stress the CPU cache.

Moreover, we do not know ahead of time where coded integers begin and end: a
typical segment of 16 bytes might contain the end of one compressed integer, a
few compressed integer at the beginning of another compressed integer.

Our proposed algorithm works on 12 bytes inputs and 12-bit masks. In practice,
we load the input bytes in a 128-bit register containing 16 bytes (using
movdqu), but only the first 12 bytes are considered. For the time being, let
us assume that the segment begins with a complete encoded integer. Moreover,
assume that the 12-bit mask has been precomputed.

In what follows, we use the convention that $(\cdots)_{k}$ is a vector of
$k$-bit integers. Because numbers are stored in binary notation, we have that

$\displaystyle(1,0,0,0)_{8}=(1,0)_{16}=(1)_{32},$

that is, all three vectors represent the same binary data.

  * •

If the mask is $00\cdots 00$, then the 12 input bytes represent 12 integers
_as is_. We can unpack the first 4 bytes to 4 32-bit integers (in a 128-bit
register) with the pmovsxbd instruction. This new register can then be stored
in the output buffer. We can then shift the input register by 4 bytes using
the psrldq instruction, and apply to pmovsxbd instruction again. Repeating a
third time, we have decoded all 12 integers. We have consumed 12 input bytes
and written 12 integers.

  * •

Otherwise we use the 12-bit mask to look two 8-bit values in a table
$2^{12}$-entries-wide. The first 8-bit value is an integer between 2 and 12
indicating how many input bytes we consume. Though it is not immediately
useful to know how many bytes are consumed, we use this number of consumed
bytes when loading the next input bytes. The second 8-bit value is an _index_
$i$ taking integer values in $[0,170)$. From this index, we load up one of 170
control masks. We then proceed according to the value of the index $i$:

    * –

If $i<64$, then the next 6 integers each fit in at most two bytes (they are
less than $2^{14}$). There are exactly $2^{6}=64$ cases corresponding to this
scenario. That is, the first integer can fit in one or two bytes, the second
integer in one or two bytes, and so on, generating 64 distinct cases. For each
of the 6 integers $x_{i}$, we have the low byte containing the least
significant 7 bits of the integer $a_{i}$, and optionally a high byte
containing the next 7 bits $b_{i}$ ($x_{i}=a_{i}+b_{i}2^{7}$). The call to
pshufb will permute the bytes such that the low bytes occupy the positions 1,
3, 5, 7, 9, 11 whereas the high bytes, when available, occupy the positions 2,
4, 6, 8, 10, 12. When a high byte is not available, the byte value zero is
used instead.

For example, when all 6 values are in $[2^{7},2^{14})$, the permuted bytes are

$\displaystyle(a_{1}1,b_{1},a_{2}1,b_{2},a_{3}1,b_{3},\ldots,a_{6}1,b_{6})_{8}$

when presented as a vector of bytes with the short-hand notation $a_{i}1\equiv
a_{i}+2^{7}$.

From these permuted bytes, we generate two vectors using bitwise ANDs with
fixed masks (using pand). The first one retains only the least significant 7
bits of the low bytes: as a vector of 16-bit integers we have

$\displaystyle(a_{1}1,b_{1},a_{2}1,b_{2},a_{3}1,b_{3},\ldots,a_{6}1,b_{6})_{8}$
AND $\displaystyle(127,0,127,0,127,0,\ldots,127,0)_{8}$
$\displaystyle=(a_{1},a_{2},a_{3},\ldots,a_{6})_{16}.$

The second one retains only the high bytes:

$\displaystyle(0,b_{1},0,b_{2},0,b_{3},\ldots,0,b_{6})_{8}.$

Considering the latter as a vector of 16-bit integers, we right shift it by 1
bit (using psrlw) to get the following vector

$\displaystyle(b_{1}2^{7},b_{2}2^{7},b_{3}2^{7},\ldots,b_{6}2^{7})_{16}.$

We can then combine (with a bitwise OR using por) this last vector with the
vector containing the least significant 7 bits of the low bytes. We have
effectively decoded the 6 integers as 16-bit integers: we get

$\displaystyle(a_{1}+b_{1}2^{7},a_{2}+b_{2}2^{7},$ $\displaystyle
a_{3}+b_{3}2^{7},a_{4}+b_{4}2^{7},$ $\displaystyle
a_{5}+b_{5}2^{7},a_{6}+b_{6}2^{7})_{16}.$

We can unpack the first four to 32-bit integers using an instruction such as
pmovsxwd, we can then shift by 8 bytes (using psrldq) and apply pmovsxwd once
more to decode the last two integers.

    * –

If $64\leq i<145$, the next 4 encoded integers fit in at most 3 bytes. We can
check that there are $81=3^{4}$ such cases. The processing is then similar to
the previous case except that we have up to three bytes per integer (low,
middle and high). The permuted version will re-arrange the input bytes so that
the first 3 bytes contain the low, middle and high bytes of the first integer,
with the convention that a zero byte is written when there is no corresponding
input byte. The next byte always contain a zero. Then we store the data
corresponding to the next integer in the next 3 bytes. A zero byte is added.
And so on.

This time, we create 3 new vectors using bitwise ANDs with appropriate masks:
one retaining only the least significant 7 bits from the low bytes, another
retaining only the least significant 7 bits from the middle bytes and another
retaining only the high bytes. As vectors of 32-bit integers, the second
vector is right shifted by 1 bit whereas the third vector is right shifted by
2 bits (using psrld). The 3 registers are then combined with a bitwise OR and
written to the output buffer.

    * –

Finally, when $145\leq i<170$), we decode the next 2 integers. Each of these
integers can consume from 1 to 5 input bytes. There are $5^{2}=25$ such cases.

For simplicity of exposition, we only explain how we decode the first of the
two integers using 8-byte buffers. The integer can be written as
$x_{1}=a_{1}+b_{1}2^{7}+c_{1}2^{14}+d_{1}2^{21}+e_{1}2^{28}$ where
$a_{1},b_{1},c_{1},d_{1}\in[0,2^{7})$ and $e_{1}\in[0,2^{4})$. Assuming that
$x_{1}\geq 2^{28}$, then the first 5 input bytes will be
$(a_{1}1,b_{1}1,c_{1}1,d_{1}1,e_{1})_{8}$.

Irrespective of the value of the index $i$, the first step is to set the most
significant bit of each input byte to 0 with a bitwise AND. Thus, if
$x_{1}\geq 2^{28}$, we get $(a_{1},b_{1},c_{1},d_{1},e_{1})_{8}$.

We then permute the bytes so that we get the following 8 bytes:

$\displaystyle Y=(b_{1},c_{1},d_{1},e_{1}+a_{1}2^{8})_{16}.$

The last byte is occupied by the value $a_{1}$ which we can isolate for later
use by shifting right the whole vector by seven bytes (using psrldq):

$\displaystyle Y^{\prime}=(a_{1},0,0,0,0,0,0,0)_{8}.$

Using the pmullw instruction, we multiply the permuted bytes ($Y$) by the
vector

$\displaystyle(2^{7},2^{6},2^{5},2^{4})_{16}$

to get

$\displaystyle(b_{1}2^{7},c_{1}2^{6},d_{1}2^{5},e_{1}2^{4}+(a_{1}2^{12}\bmod
2^{16}))_{16}.$

As a byte vector, this last vector is equivalent to

$\displaystyle X=(b_{1}2^{7}\bmod 2^{8},b_{1}\div 2,$ $\displaystyle
c_{1}2^{6}\bmod 2^{8},c_{1}\div 2^{2},$ $\displaystyle d_{1}2^{5}\bmod
2^{8},d_{1}\div 2^{3},$ $\displaystyle e_{1}2^{6}\bmod 2^{8},\star)_{8}$

where we used $\star$ to indicate an irrelevant byte value. We can left shift
this last result by one byte (using psllq):

$\displaystyle X^{\prime}=(0,b_{1}2^{7}\bmod 2^{8},$ $\displaystyle b_{1}\div
2,c_{1}2^{6}\bmod 2^{8},$ $\displaystyle c_{1}\div 2^{2},d_{1}2^{5}\bmod
2^{8},$ $\displaystyle d_{1}\div 2^{3},e_{1}2^{6}\bmod 2^{8})_{8}$

We can combine these two results with the value $a_{1}$ isolated earlier
($Y^{\prime}$):

$\displaystyle
Y^{\prime}\mathrm{~{}OR~{}}X\mathrm{~{}OR~{}}X=(a_{1}+b_{1}2^{7}\bmod
2^{8},\star,$ $\displaystyle b_{1}\div 2+c_{1}2^{6}\bmod 2^{8},\star,$
$\displaystyle c_{1}\div 2^{2}+d_{1}2^{5}\bmod 2^{8},\star,$ $\displaystyle
d_{1}\div 2^{3}+e_{1}2^{6}\bmod 2^{8},\star)_{8}$

where again we use $\star$ to indicate irrelevant byte values. We can permute
this last vector to get

$\displaystyle(a_{1}+b_{1}2^{7}\bmod 2^{8},b_{1}\div 2+c_{1}2^{6}\bmod 2^{8},$
$\displaystyle c_{1}\div 2^{2}+d_{1}2^{5}\bmod 2^{8},$ $\displaystyle
d_{1}\div 2^{3}+e_{1}2^{6}\bmod 2^{8},\ldots)_{8}$
$\displaystyle=(a_{1}+b_{1}2^{7}+c_{1}2^{14}+d_{1}2^{21}+e_{1}2^{28},\ldots)_{32}$

Thus, we have effectively decoded the integer $x_{1}$.

The actual routine works with two integers $(x_{1},x_{2})$. The content of the
first one is initially stored in the first 8 bytes of a 16-byte vector whereas
the remaining 8 bytes are used for the second integer. Both integers are
decoded simultaneously.

An important motivation is to amortize the latency of the pmovmskb instruction
as much as possible. First, we repeatedly call the pmovmskb instruction until
we have processed up to 48 bytes to compute a corresponding 48-bit mask. Then
we repeatedly call the decoding procedure as long as 12 input bits remain out
of the processed 48 bytes. After reach call to the 12-byte decoding procedure,
we left shift the mask by the number of consumed bits. Recall that we look up
the number of consumed bytes at the beginning of the decoding procedure so
this number is readily available and its determination does not cause any
delay. When fewer than 12 valid bits remain in the mask, we process another
block of 48 input bytes with pmovmskb. To accelerate further this process, and
if there are enough input bytes, we maintain two 48-bit masks (representing 96
input bytes): in this manner, a 48-bit mask is already available while a new
one is being computed. When fewer than 48 input bytes but more than 16 input
bytes remain, we call pmovmskb as needed to ensure that we have at least a
12-bit mask. When it is no longer possible, we fall back on conventional VByte
decoding.

### Differential Coding

We described the decoding procedure without accounting for differential
coding. It can be added without any major algorithmic change. We just keep
track of last 32-bit integer decoded. We might store it in the last entry of a
vector of four 32-bit integers (henceforth $p=(p_{1},p_{2},p_{3},p_{4})$).

We compute the prefix sum before to writing the decoded integers. There are
two cases to consider. We either write four 32-bit integers or 2 32-bit
integers (e.g., when writing 6 decoded integers, we first write 4, then 2
integers). In both cases, we permute first the entries of $p$ so that
$p\leftarrow(p_{4},p_{4},p_{4},p_{4})$ using the pshufd instruction.

  * •

Suppose we decoded four integers in the vector $c$. We left shift the content
of $c$ by one integer (using pslldq) so that
$c^{\prime}\leftarrow(0,c_{1},c_{2},c_{3})$. We add $c$ to $c^{\prime}$ using
paddd so that $c\leftarrow(c_{1},c_{1}+c_{2},c_{2}+c_{3},c_{3}+c_{4})$. We
shift the rest by two integers (using again pslldq)
$c^{\prime}\leftarrow(0,0,c_{1},c_{1}+c_{2})$ and add
$c+c^{\prime}=(c_{1},c_{1}+c_{2},c_{1}+c_{2}+c_{3},c_{1}+c_{2}+c_{3}+c_{4})$.
Finally, we add $p$ to this last result $p\leftarrow
p+c+c^{\prime}=(p_{4}+c_{1},pp+c_{1}+c_{2},p+c_{1}+c_{2}+c_{3},p+c_{1}+c_{2}+c_{3}+c_{4})$.
We can write $p$ as the decoded output.

  * •

The process is similar though less efficient if we only have two decoded gaps.
We start from a vector containing two gaps
$c\leftarrow(c_{1},c_{2},\star,\star)$ where we indicate irrelevant entries
with $\star$. We can left shift by one integer
$c^{\prime}\leftarrow(0,c_{1},c_{2},\star)$ and add the result
$c+c^{\prime}=(c_{1},c_{1}+c_{2},\star,\star)$. Using the pshufd instruction,
we can copy the value of the second component to the third and fourth
components, generating $(c_{1},c_{1}+c_{2},c_{1}+c_{2},c_{1}+c_{2})$. We can
then add $p$ to this result and store the result back into $p$. The first two
integers can be written out as output.

##  5 Experiments

We implemented our software in C and C++. The benchmark program ran on a Linux
server with an Intel i7-4770 processor running at
$3.4\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$. This Haswell processor has
$32\text{\,}\mathrm{k}\mathrm{B}$ of L1 cache and
$256\text{\,}\mathrm{k}\mathrm{B}$ of L2 cache per core with
$8\text{\,}\mathrm{M}\mathrm{B}$ of L3 cache. The machine has
$32\text{\,}\mathrm{G}\mathrm{B}$ of RAM (DDR3-1600 with double-channel). We
disabled Turbo Boost and set the processor to run at its highest clock speed.
We report wall-clock timings. Our software is freely available under an open-
source license (http://maskedvbyte.org) and was compiled using the GNU GCC 4.8
compiler with the -O3 flag.

(a) Absolute speed

(b) Ratio of speeds

Figure 2: Performance comparison for various sets of posting lists (ClueWeb)

For our experiments, we used a collection of posting lists extracted from the
ClueWeb09 (Category B) data set. ClueWeb09 includes 50 million web pages. We
have one posting list for each of the 1 million most frequent words—after
excluding stop words and applying lemmatization. Documents were sorted
lexicographically based on their URL prior to attributing document
identifiers. The posting lists are grouped based on length: we store and
process lists of lengths $2^{K}$ to $2^{K+1}-1$ together for all values of
$K$. Coding and decoding times include differential coding. Shorter lists are
less compressible than longer lists since their gaps tend to be larger. Our
results are summarized in Fig. 2. For each group of posting lists we compute
the average bits used per integer after compression: this value ranges from 8
to slightly less than 16. All decoders work on the same compressed data.

When decoding long posting lists to RAM, our speed is limited by RAM
throughput. For this reason, we decode the compressed data sequentially to
buffers fitting in L1 cache (4096 integers). For each group and each decoder,
we compute the average decoding speed in millions of 32-bit integers per
second (mis). For our Masked VByte decoder, the speeds ranges from
$2700\text{\,}\mathrm{m}\mathrm{i}\mathrm{s}$ for the most compressible lists
to $650\text{\,}\mathrm{m}\mathrm{i}\mathrm{s}$ for the less compressible
ones. The speed of the conventionalVByte decoder ranges from
$1100\text{\,}\mathrm{m}\mathrm{i}\mathrm{s}$ to
$300\text{\,}\mathrm{m}\mathrm{i}\mathrm{s}$. For all groups of posting lists
in our experiments, the Masked VByte decoder was at least twice as fast as the
conventional VByte decoder. However, for some groups, the speedup is between
$3\times$ and $4\times$.

If we fully decode all lists instead of decoding to a buffer that fits in CPU
cache, the performance of Masked VByte can be reduced by about
$15\text{\,}\mathrm{\char 37\relax}$. For example, instead of a maximal speed
of $2700\text{\,}\mathrm{m}\mathrm{i}\mathrm{s}$, Masked VByte is limited to
$2300\text{\,}\mathrm{m}\mathrm{i}\mathrm{s}$.

##  6 Conclusion

To our knowledge, no existing VByte decoder comes close to the speed of Masked
VByte. Given how the VByte format is a de facto standard, it suggests that
Masked VByte could help optimize a wide range of existing software without
affecting the data formats.

Masked VByte is in production code at Indeed as part of the open-source
analytics platform Imhotep (http://indeedeng.github.io/imhotep/).

## Acknowledgments

We thank L. Boystov from CMU for preparing and making available the posting
list collection.

## References

  * [1] Bishwaranjan Bhattacharjee, Lipyeow Lim, Timothy Malkemus, George Mihaila, Kenneth Ross, Sherman Lau, Cathy McArthur, Zoltan Toth, and Reza Sherkat.  Efficient index compression in DB2 LUW.  Proc. VLDB Endow., 2(2):1462–1473, August 2009.
  * [2] Jeffrey Dean.  Challenges in building large-scale information retrieval systems: invited talk.  WSDM ’09, pages 1–1, New York, NY, USA, 2009. ACM.
  * [3] Daniel Lemire and Leonid Boytsov.  Decoding billions of integers per second through vectorization.  Softw. Pract. Exper., 45(1), 2015.
  * [4] Alexander A. Stepanov, Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst, and Paramjit S. Oberoi.  SIMD-based decoding of posting lists.  CIKM ’11, pages 317–326, New York, NY, USA, 2011. ACM.
  * [5] Hugh E. Williams and Justin Zobel.  Compressing integers for fast file access.  Comput. J., 42(3):193–201, 1999.