Inferring Crypto API Rules from Code Changes
Rumen Paletov∗

Petar Tsankov

ETH Zurich, Switzerland
rumen.paletov@gmail.com

ETH Zurich, Switzerland
ptsankov@inf.ethz.ch

Veselin Raychev

Martin Vechev

DeepCode AG, Switzerland
veselin@deepcode.ai

ETH Zurich, Switzerland
martin.vechev@inf.ethz.ch

Abstract

1Creating and maintaining an up-to-date set of security rulesthat match misuses of crypto APIs is challenging, as crypto
APIs constantly evolve over time with new cryptographic
primitives and settings, making existing ones obsolete.
To address this challenge, we present a new approach to
extract security fixes from thousands of code changes. Our
approach consists of: (i) identifying code changes, which
often capture security fixes, (ii) an abstraction that filters
irrelevant code changes (such as refactorings), and (iii) a clustering analysis that reveals commonalities between semanticcode changes and helps in eliciting security rules.
We applied our approach to the Java Crypto API andshowed that it is effective: (i) our abstraction effectively
filters non-semantic code changes (over 99% of all changes)
without removing security fixes, and (ii) over 80% of the codechanges are security fixes identifying security rules. Basedon our results, we identified 13 rules, including new ones
not supported by existing security checkers.

Many critical data breaches nowadays are caused by an incorrect use of crypto APIs. Developers often fail to understandand correctly configure cryptographic primitives, such as
cryptographic ciphers, secret keys, and hash functions, leading to severe security vulnerabilities that can be abused byattackers [15, 24]. As a result, from 100 inspected Android applications, researchers discovered severe man-in-the-middle
attacks in 41 of them and were able to gather a large variety
of sensitive data [14]. As another data point, researchers
have defined 6 common types of mistakes in using crypto
APIs and found that a staggering percentage, 88%, out of
thousands of analyzed Android applications have at least
one of these mistakes [12].
To resolve this problem, we argue that developers must
check their applications against an up-to-date and comprehensive list of security rules regarding potential misuses ofcrypto APIs. Unfortunately, creating and updating such alist can be quite challenging as security is a constantly moving target: crypto APIs evolve over time as security experts
continue to discover new attacks against existing primitives.
For example, researchers have recently discovered the firstcollision against the SHA-1 cryptographic hash function [30],and are now advising developers to shift to safer alternatives,
such as SHA-256.

CCS Concepts • Security and privacy → Systems security; Cryptanalysis and other attacks; Software security
engineering;
Keywords Security, Misuse of Cryptography, Learning
ACM Reference Format:
Rumen Paletov, Petar Tsankov, Veselin Raychev, and Martin Vechev.
2018. Inferring Crypto API Rules from Code Changes. In Proceedingsof 39th ACM SIGPLAN Conference on Programming Language Design
and Implementation (PLDI’18). ACM, New York, NY, USA, 15 pages.
https://doi.org/10.1145/3192366.3192403∗ Currently employed by Twitter, work done while at ETH Zurich

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. Copyrights
for components of this work owned by others than the author(s) must
be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. Request permissions from permissions@acm.org.
PLDI’18, June 18–22, 2018, Philadelphia, PA, USA© 2018 Copyright held by the owner/author(s). Publication rights licensed
to the Association for Computing Machinery.
ACM ISBN 978-1-4503-5698-5/18/06. . . $15.00
https://doi.org/10.1145/3192366.3192403

Introduction

This Work: From Code Changes to API Usage Rules.
In this paper, we propose a new approach for learning thecorrect usage of an API based on code changes, which arereadily available in public repositories today. We show thatcode changes that fix security problems are more common
than changes that introduce them, i.e. most problems wereintroduced in the initial implementation, not in a fix. The
immediate benefit of this idea is that we can produce meaningful results even when most developers misuse an API (asit happens with the Java Crypto API). For instance, even if
most developers use an outdated, less-secure cryptographic
primitive (e.g. SHA-1), our approach can identify, based on acouple of code changes, that developers are switching to anew, more secure primitive (e.g. SHA-256).
Key challenge. Attempting to learn from code changes isdifficult because many changes do not semantically affect
how the API is used (e.g, they may be a syntactic re-factoring).

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA

GitHubR. Paletov, P. Tsankov, V. Raychev, and M. Vechev
Rule 1: Use the BouncyCastle provider for Cipher
Rule 2: Use SHA-256 instead of SHA-1..
.

BitBucket
Mineclass AESCipher {Cipher enc ;- protected void setKey ( Secret key ) {+ protected void setKeyAndIV ( Secret key , String iv ) {+byte [] bytes ;+IvParameterSpec ivSpec ;try {class AESCipher {+ivBytes = Hex . decodeHexiv .;toCharArray ());
Cipher (enc+
ivSpec = new IvParameterSpec( ivBytes);( Secret key ) {- protected void
setKeyenc = Cipher . getInstance(" AES" );setKeyAndIV ( Secret key , String iv ) {+ protectedvoid
enc . init ( Cipher+. ENCRYPT_MODE, keybyte [] bytes; );+enc = Cipher . getInstance
("
AES
/
CBC
/
PKCS5Padding" );+IvParameterSpec ivSpec ;+enc . init ( Cipher . ENCRYPT_MODE, key , ivSpec );try {class AESCipher{ {...}} catch+ivBytes = Hex . decodeHex ( iv . toCharArray ());
Cipherenc;} }+= new IvParameterSpec ( ivBytes );- protected void setKey ( Secret
keyivSpec) {} catch+ protected void setKeyAndIV ( Secret
key ,{...}
String iv ) {} }+byte [] bytes ;+IvParameterSpec ivSpec ;try {+ivBytes = Hex . decodeHex ( iv . toCharArray ());+
ivSpec = new IvParameterSpec ( ivBytes );} catch {...}} }Security Rules
Cipherinit

CiphergetInst"AES"

CiphergetInst"AES/CBC"

KeySpec<init>

constbyte[]

KeySpec<init>⊤byte[]§3
Staticanalysis

Elicitrules

IVParam§4

MsgDigest<init>"MD5"

MsgDigest<init>"SHA256"

Code Changes

Combine& filter
Hierarchical clustering oversemantic usage changes

Usage Changes

Figure 1. Overview of our approach for learning semantic usage changes and extracting security rules.
To address this challenge, we develop an abstraction tailoredto crypto APIs that can capture relevant security properties.
Our abstraction captures the semantic features of how acode change affects crypto API usage (e.g., how argument
type changes affect the cryptographic mode), which enables
filtering of unrelated or non-semantic changes.
Application to the Java Crypto API. We implemented
an end-to-end system, called DiffCode, of our approach
for learning semantic changes to the Java Crypto API. To
demonstrate the effectiveness of DiffCode, we applied it
to thousands of code changes collected from GitHub. DiffCode produces only few relevant changes that let us derive
new security rules. Based on these, we created a new security checker for the Java Crypto API called CryptoChecker
which has more rules than prior security checkers. For instance, a novel rule derived from data is to switch from thedefault Java provider to BouncyCastle. The reason is that
BouncyCastle does not have a 128 bit key restriction [3].
Main Contributions. Our main contributions are:
• A new data-driven approach that learns rules fromcode changes where the learned rules capture the correct usage of an API (Section 2).
• An abstraction tailored to crypto APIs that captures thesemantic structure of code changes while abstracting
away syntactic details. This abstraction is essential todistilling thousands of concrete code changes into few
semantically meaningful ones (Section 3).
• An end-to-end system, called DiffCode, for discovering relevant code changes. Our system consists of:(i) a lightweight AST-based program analysis that supports (partial) code snippets, (ii) abstraction of crypto

API usage changes, and (iii) filtering combined withclustering analysis to ease users in inspecting relevant
code changes (Sections 4-5).
• An extensive evaluation of DiffCode on the Java
Crypto API. Using DiffCode, we identified 13 security rules, including several previously unknown ones
(Section 6).
We remark that while we focus on crypto APIs, the approachis general and can be applied to other types of APIs.

2

Overview of Approach

We now present our approach to extracting information
about API usages from thousands of code changes. At ahigh-level, our method is based on two key insights: Our
first insight is to focus on code changes, which identify concrete fixes that developers have applied to the code. The oldversion of the program (before applying the change) often
resembles incorrect (or, insecure) usage of the API. Our approach thus differs from existing statistical “Big Code”-typeof approaches, which focus on discovering statistically common API usages (e.g., [27]). Such statistical approaches arebound to produce less meaningful results in settings where
the majority of developers misuse the API, as is the caseof crypto APIs. In contrast, our method can discover incorrect usage even when only few developers have applied acorrect fix. Our second insight is to leverage program abstraction to derive meaningful, semantic information about
code changes. This is necessary to avoid irrelevant syntacticcode modifications, such as refactoring.
We depict the flow of our learning approach in Figure 1.
We now briefly describe its main steps.
Step 1: Mining Code Changes. The first step consistsof collecting code changes from open-source repositories.

Inferring Crypto API Rules from Code Changes
Since we are usually interested in extracting usage changes
for particular API classes, such as Cipher and SecretKeySpec
from the Java Crypto API, we fetch only patches for classes
that use the target API classes. We explain how we collected
thousands of code changes for the Java Crypto API, which
we used in our experiments, in Section 6.
Step 2: Abstract Usage Changes via Static Analysis. Program abstraction is a key element in our approach that enables us to distill semantic security fixes from thousands ofcode changes. Developers often commit patches that refactor the code, e.g. to improve readability and performance,
without making semantic changes to the target API classes.
Program abstraction can be used to discover that such syntactic modifications do not result in semantic changes to theprogram and how it uses the API.
DiffCode downloads both the old and the new versions of
the program and statically analyzes each version. It first discovers all different usages of a target API and extracts semantic features about each usage. These features capture which
methods are invoked on objects of the API as well as information about the arguments passed to these methods. A usagechange is then identified by the change in these features.
For instance, suppose that in the old version the program
creates an object of type Cipher by calling getInstance()and passing "AES" as an argument. Further, suppose that in
the new version the program creates the same object witha call to getInstance() with arguments "AES/CBC" and an
initialization vector object. DiffCode would detect this as asemantic change: the program changes the mode of the AES
cipher from default Electronic Code Book mode (ECB) to themore secure Chain-Block Cipher mode (CBC). We describe
the program abstraction we use in Section 3 and how it isderived using static analysis in Section 5.1.
Step 3: Filter and Cluster Usage Changes. The usagechanges derived from each project are collected and processed together. Thanks to the abstraction, DiffCode filters
out usage changes that are not semantic fixes. For example,
if features are neither added nor removed for a particular
API usage, then the usage code is likely a refactoring and isthus filtered. We apply additional filters to remove duplicate
usage changes and changes that either only add or remove
features, as these often correspond to adding a new usage of
the API or removing an existing one.
In the beginning, DiffCode starts with tens of thousandsof code changes and after the filtering step, there are only
186 remaining usage changes. Yet, we checked that this filtering step does not remove previously known security-related
rules. Then, DiffCode uses a classic hierarchical clustering
algorithm on these 186 changes (Section 4) and produces clusters that correspond to security-related rules. At this stage,
we manually inspected the clusters and devised security
checks that we encoded into a tool called CryptoChecker.

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
The last step in DiffCode is manual for several reasons.
First, we did not focus on automating this last step as it involves inspecting only tens of clusters of changes. Second, we
manually inspect, document, and explain the derived rules
to users. Finally, we remove false positives that introduce
security problems as opposed to fix it – in fact, these areeasy to filter out, even automatically, because there are fewer
commits in clusters that introduce problems than in clusters
that fix them.
Overall, we derived 13 security rules, some of which are
new rules. The new rules are currently not included in existing security checkers for crypto API misuse. Our rules aredescribed in Section 6.

3

Abstraction for API Changes

We now present our abstraction for representing the semantic structure of security fixes applied to crypto APIs. We firstpresent the terminology, then discuss an abstraction thatgiven (a single version of) a program returns a set of API
usage. Finally, given two program versions, we show how
to leverage the abstraction in order to capture API usagechanges (which may correspond to actual fixes). In the sections that follow we show how to leverage this abstraction
for learning security rules.
3.1

ExampleWe first present an example which we later use to illustrate
our definitions. In Figure 2(a) we show the code patch for aJava class called AESCipher. The code lines removed from theold version are shown in red (and marked with -) and theadded lines are shown in green (and marked with +). This
class creates two objects of type Cipher, enc and dec, which
are used for encryption and, respectively, decryption.
Old Version. The old version of AESCipher creates the two
objects enc and dec using the method getInstance with thestring "AES" passed as an argument. The instance enc is theninitialized using init with arguments Cipher.ENCRYPT_MODE,
an integer constant defined in the Cipher API, and key, which
represents the symmetric key to be used for encryption. The
object dec is also initialized with key, but this time the classuses the Cipher.DECRYPT_MODE constant.
New Version. In the new version, the developer changes
the signature of setKey, which now also takes as argument
the object iv of type String. Further, the objects enc anddec are initialized using the string "AES/CBC/PKCS5Padding"(instead of "AES"). With this change, the developer explicitly expresses that the two ciphers must use the AES cipher
in Chain Block Cipher mode (CBC) as well as the PKCS5
padding scheme. When the two Cipher objects are initialized, the developer passes as argument the object ivSpec oftype IVParameterSpec to define the initialization vector thatthe ciphers must use for the first block they process. The

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

R. Paletov, P. Tsankov, V. Raychev, and M. Vechev

class AESCipher {Cipher enc , dec ;- final String algorithm = " AES " ;+ final String algorithm = " AES / CBC / PKCS5Padding " ;- protected void setKey ( Secret key ) {+ protected void setKeyAndIV ( Secret key , String iv ) {+byte [] bytes ;+IvParameterSpec ivSpec ;try {+ivBytes = Hex . decodeHex ( iv . toCharArray ());+
ivSpec = new IvParameterSpec ( ivBytes );enc = Cipher . getInstance ( algorithm );enc . init ( Cipher . ENCRYPT_MODE , key );+enc . init ( Cipher . ENCRYPT_MODE , key , ivSpec );dec = Cipher . getInstance ( algorithm );dec . init ( Cipher . DECRYPT_MODE , key );+dec . init ( Cipher . DECRYPT_MODE , key , ivSpec );} catch {...}}}

CiphergetInstance
arg1:"AES"

init
arg1:ENCRYPT_MODE

arg2:Secret(b) Usage DAG of the object enc before the change
CiphergetInstanceinit
arg1:ENCRYPT_MODE

arg2:Secretarg1:"AES/CBC/PKCS5Padding"arg3:IVParameterSpec<init>
arg1:⊤byte[](a) Code changes to two objects (enc and dec) of type Cipher(c) Usage DAG of object enc after the change

Removed features:

CiphergetInstance

arg1:"AES"

Added features:

CiphergetInstance

arg1:"AES/CBC/PKCS5Padding"Cipherinit

arg3:IVParameterSpec(d) Removed (red) and added (green) features that capture the usage change of object enc.

Figure 2. Code changes to two objects of the type Cipher and the usages change derived for object enc.
developer also adds lines 11 and 12 to initialize the ivSpec
object using the string iv passed as argument to the method.
The Need for Abstraction. If we consider this example
purely syntactically, the lines that call Cipher.getInstanceremain unchanged. At the same time, most of the syntacticchanges are related to renaming the setKey method and introducing an extra parameter. However, if we perform theright program analysis before comparing the two versions,
we can abstract the semantically relevant changes for eachof the Cypher objects and concisely capture the semantics ofthe change.
In later sections, we explain how DiffCode learns fromthe example in Figure 2(a) by illustrating the steps on Figures 2(b), 2(c), and 2(d).

3.2

Basic Notation and Terminology

Before presenting our abstraction, we describe our notationand terminology and define what we mean by API usage.
Types and Methods. We restrict our attention to crypto
APIs for languages such as Java that support base types(e.g., int, byte, int[], byte[]) and object types which are
stored in the heap. We consider an API that defines a setof types Types = {t 1 , . . . , tn }. For instance, the Java Crypto

API defines the type Cipher, a cryptographic cipher used forencryption and decryption.
A method signature is given by m([t 0 ], t 1 , . . . , tk ) : t ret
where t 0 is the type of the object on which the method is
invoked (the this object), k is the method’s arity, each ti is thetype of the ith argument, and t ret is the type of object/value
returned by the method. Note that t 0 is defined only for non
static methods. We write Methods to denote the set of all
methods.
For a given type t, Methodst ⊆ Methods denotes the setof all methods that (i) accept an instance of type t as anargument or (ii) create a new instance of type t. For example, the set MethodsIVParameterSpec contains the method
Cipher.init(int, Key, AlgorithmParameterSpec), as it accepts objects of type IVParameterSpec as the third argument.
Further, it contains IVParameterSpec.<init>(byte[]), which
creates a new instance of type IVParameterSpec. Note thatin addition to constructor methods, Methodst may also contain factory methods. For example, MethodsCipher contains
factory method Cipher.getInstance(String):Cipher.
Program State. We assume standard program semantics
of an object-oriented language. A program state σ ∈ States

Inferring Crypto API Rules from Code Changes

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA

is a tuple σ = (objs, η, ∆) with:Base type

objs
Vals
η
∆
States

⊆
=
∈
∈
=

Objs
objs ∪ BaseValues
Heaps : objs × Fields → ValsStores : Vars → Vals
P(Objs) × Heaps × Stores

where Objs is the set of all possible objects, BaseValues is theset of all values of base types (such as values of type int andbyte), Fields is the set of fields, and Vars is the set of all local
variables. A program state σ = (objs, η, ∆) tracks: (i) the setof allocated objects objs, (ii) the state of the heap η that maps
the fields of allocated objects to values (either an allocatedobject or a value of a base type), and (iii) the state of local
variables which store values.
Concrete API Usages. A standard way to define a concrete
usage of a given type t is to collect the set of all method
calls to an object of type t together with the program states
associated at each method call; cf. [27]. Note that a programusually defines multiple objects of the same type t that arethen used in different ways, resulting in multiple concrete
usages of type t.
We define the concrete usages as the map:
CUses : Objs → P(Methods × States) .
That is, for a given object o ∈ Objs of type t, the set ofpairs CUses(o) = {(m 1 , σ1 ), . . . , (mn , σn )} contains the constructor/factory method mi ∈ Methodst used to create o aswell as methods m j ∈ Methodst that take as argument theobject o. A method m may be invoked multiple times with
object o at different program states, resulting in multiple
pairs (m, σ1 ), . . . , (m, σk ) in CUses(o).
We note that the concrete usages CUses for a given program will typically not be computable in practice as the
program may allocate an unbounded set of objects and may
have an unbounded number of states. Our abstraction, defined below, allows us to capture these unbounded sets witha finite set of abstract usages.
3.3

Abstraction of API Usage

We now present our abstraction which we use to capture
the usage of a particular API type. Our abstraction consistsof: (i) a heap abstraction, to represent the unbounded set ofconcrete objects with finitely many allocation sites, (ii) basetypes abstraction, and (iii) per-object Cartesian abstractionthat keeps track of method calls and abstract states associatedwith the abstract objects. We define this abstraction below.
We will explain how to apply it to programs using static
analysis in Section 5.1.
Heap Abstraction. Since a program may instantiate a potentially unbounded number of objects of a given type, we

int
int[]
stringstring[]byte
byte[]

Abstract DomainInts(P) ∪ {⊤int }IntArrays(P) ∪ {⊤int[] }Strs(P) ∪ {⊤str }StrArrays(P) ∪ {⊤str[] }{constbyte , ⊤byte }{constbyte[] , ⊤byte[] }Figure 3. Abstract base-type values for a program P.

use a per-allocation-site abstraction. That is, each constructor/factory method, such as Cipher.getInstance(String), results in one abstract object identified by the statement’s label. We denote by AObjs the set of abstract objects. We use⊤obj ∈ AObjs to represent that the allocation of the abstract
object is unknown; e.g., the allocation of the method parameter key is not defined in Figure 2(a).
Base-types Abstraction. In addition to abstracting objects, we also abstract the base-type values as they also
range over unbounded sets. In Figure 3 we summarize theabstract domains that we use. Given a program P, we writeInts(P) to denote the set of integer constants that appear
in P (e.g., 0 ∈ Ints(P) if there is a statement int x = 0 inP), and IntArrays(P) to denote the set of integer array constants that appear in P (extracted from statements such as
int[] arr = {0,1,2,3}). Integer variables and fields are assigned (i) an integer constant from Ints(P) or (ii) the symbol ⊤int , which represents the set of all integers. Similarly,
we also abstract strings and string arrays. We designed ourabstraction to keep the values for integer and string constants as these often represent configuration parameters(e.g. Cipher.ENCRYPT_MODE) and configuration strings (e.g.
"AES/CBC/NoPadding").
Byte values are abstracted to constbyte (to represent constant byte values) and ⊤byte (to represent non-constant byte
values). Byte arrays are similarly abstracted to constbyte[]and ⊤byte[] . We remark that we represent constant byte arrays as constbyte[] to abstract program-specific values, suchas hard-coded keys and initialization vectors.
We note that our abstraction is tailored to crypto APIs.
To precisely abstract uses of other APIs, one may choose a
different abstraction (e.g., Interval or Polyhedra numerical
domains [10]).
Abstract State. Let AVals = AObjs ∪ ABaseValues be theset of abstract objects and abstract base-type values, where
ABaseValues is the union of all abstract domains derived
from P. An abstract state σ a = (objsa , η a , ∆a ) consists ofa set of abstract objects objsa ⊆ AObjs, an abstract heapη a : AObjs × Fields → AVals, and abstract state of local variables ∆a : Vars → AVals. We denote by AStates the set of allabstract states.

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
Abstract API Usage. We lift our notion of concrete usages
to abstract usages, denoted by AUses, where instead of tracking the usage of each object we track the usage of abstract
objects. Further, instead of collecting the concrete states atmethod calls we collect abstract states. Formally, abstract
usages are captured with a map:
AUses : AObjs → P(Methods × AStates) .
That is, for a given abstract object oa ∈ AObjs of type t,
we obtain a set AUses(oa ) = {(m 1 , σ1a ), . . . , (mk , σka )} wheremi ∈ Methodst is a method and σia is an abstract state. Each
AUses(oa ) defines one abstract usage, while together all abstract objects in a program define the set of all abstract usages.
We note that since there are finitely many abstract objects,
methods, and abstract states, the abstract usages for a given
program are also finitely many.
3.4

R. Paletov, P. Tsankov, V. Raychev, and M. Vechev
that abs , ⊤obj . Note that we skip the nodes at depth 1 asthey contain only method nodes. We continue this processuntil a fixed depth n (in our experiments, we set n to 5).
Example. To illustrate the graph construction we refer tothe example in Figure 2. The code after the change (green
and white lines in Figure 2(a)) has two abstraction objectsof type Cipher — one allocated at line 13 and another one atline 16. In Figure 2(c) we depict the graph constructed forthe abstract object l 13 (i.e., the enc object). The root node of
the graph is (0, l 13 ), and it is labeled by (0, Cipher) because
the type of l 13 is Cipher. The abstract usage of l 13 is given byaa
AUses(l 13 ) = {(getInstance, σ13), (init, σ15)} .

The root node therefore has two children nodes labeled by
getInstance and init, respectively. Node getInstance has
one child (1, AES/CBC/PKCS5Padding) because

Abstract Usages as Directed Acyclic Graphs

Given the abstract usages defined by AUses and an abstract
object oa , we construct a rooted directed acyclic graph (DAG)
G = (N , E, r ) with nodes
N ⊆ (Methods × AStates) ∪ (N × AVals) ,edges E ⊆ N × N , and root r = (0, oa ) ∈ N . Each node in the
DAG is either a pair (m, σ a ) of a method m and an abstractstate σ a or a pair (i, a) where i ∈ N represents an argument
index and a ∈ AVals is an abstract value (i.e., an abstract
object or base-type value).
We label the nodes in the graph as follows. A node (m, σ a )is labeled by the signature of m. A node (i, a) is labeled by(i, a) if a is an abstract base-type value (e.g., ⊤int ); otherwise,a is an abstract object and the node is labeled by (i, type(a)),
where type(a) returns the type of a (e.g., Cipher).
Examples of these DAGs are given in Figures 2(b) and 2(c).
We depict node labels as arg1 : AES instead of (1, AES) toemphasize that 1 represent an argument index. Further, weomit the index 0 in root node labels (as roots always haveindex 0). Below we explain how these DAGs are constructed.
Constructing a DAG. To construct the graph for an abstract object oa , we first add the root (0, oa ). Then, startingfrom the root, the tree is iteratively constructed by performing the following two steps on each node (i, abs):
1. For each (m, σ a ) ∈ AUses(abs), we add a node (m, σ a )and an edge ((i, abs), (m, σ a )).
2. For each node (m, σ a ) created in step (1), we add up
to k children where k is the arity of m. First, for eachparameter pi of m, we add a node (i, absi ), where absi =∆a (pi ). Then, we add an edge ((m, σ a ), (i, absi )) if it
does not introduce a cycle in the graph.
The above steps are iteratively performed in a breath-firstmanner by first expanding the root node (depth 0 of therooted DAG). Then, we process the nodes (i, abs) at depth 2of the DAG where abs ∈ AObjs is an abstract object such∆la13 (algorithm) = AES/CBC/PKCS5Padding .
Node init has three children. The first one is (1, ENCRYPT_MODE),
where ENCRYPT_MODE is an integer constant defined in Cipher.
The second child is (2, ⊤obj ) and is labaled by (1, Secret). This
child has no further children as ∆la13 (key) = ⊤obj (the allocation of object key is not defined in the code). Finally, the thirdchild is (3, l 12 ) and is labeled by (3, IVParameterSpec). The abstract object l 12 is recursively expanded with the constructor
method <init> and it’s argument ⊤byte[] .
3.5

From DAGs to Usage Changes

To capture the semantic meaning of a code change withrespect to a type t, we derive the abstract usages AUses1
and AUses2 for the old and, respectively, the new versionof the program. We proceed in three steps, as depicted in
Figure 4. First, for each version, we derive all rooted DAGs
for all abstract objects of type t, as explained in Section 3.4.
We note that we may obtain multiple DAGs for each version(determined by the number of allocation sites of objects oftype t in a version). Second, we pair the DAGs of the oldversion with those of the new version based on a distancemetric (defined below) that captures the similarity between
two DAGs. Finally, given a pair of DAGs, we derive featuresthat describe the semantic change between the two usages.
We refer to these features as usage change. The result of thethree steps above is a set of usage changes.
Distance Between DAGs. We first define a metric thatreflects the distance between two DAGs G 1 = (N 1 , E 1 , r 1 )and G 2 = (N 2 , E 2 , r 2 ). The distance between the DAGs isgiven by a intersection-over-union measure over the sets ofnodes:|N 1 ∩ N 2 |.
dist(G 1 , G 2 ) = 1 −|N 1 ∪ N 2 |This measure reflects the change in terms of nodes in the
DAGs that differ in the two graphs while also respecting

Inferring Crypto API Rules from Code Changes

B2

A2

Pair
DAGs

Bk

B2

...

Old version
DAGs

Bk

A2

...

...

Code change

An

A1

B1

A1

Derive
DAGs

PLDI’18, June 18–22, 2018, Philadelphia, PA, USAAn

New version
DAGs

B1

Paired DAGs

Diff(A1, Bk) =Diff(A2, B2) =Extract
features

F- :
+

F :
F- :
+

F :

-

Diff(An, B1) = F :+F :Usage changes

Figure 4. Step-by-step derivation of usage changes from a code change defining two versions of the program
the edges. For instance, for the DAGs G 1 and G 2 depicted in
Figures 2(b) and 2(c), respectively, we get dist(G 1 , G 2 ) = 12 .

That is, Shortest(P) contains a path p if and only if no other
path is a strict prefix of p. For example, for the set of paths

Pairing DAGs. Suppose that the DAGs derived from theold version are Vold = {A1 , . . . , An } and those derived fromthe new version are Vnew = {B 1 , . . . , Bk }; we depict theseas old/new version DAGs in Figure 4. For simplicity, we
assume that |Vold | = |Vnew |, i.e. the two versions have an
equal number of DAGs; if this is not the case, we extend
the version with fewer DAGs with DAGs of the form G =({r }, ∅, r ), which only contain a root node r labeled withthe type t. We solve a maximum matching problem to map
the DAGs in Vold to unique DAGs in Vnew (and vice versa),
such that we minimize the sum of the distance metrics of thepaired graphs. The mapping is a bijection m ⊆ Vold × Vnew
whenever |Vold | = |Vnew |.
Formally, let M be the set of all possible mappings. The
distance for a given mapping m ∈ M is given by:Õ
mdist(m) =dist(G 1 , G 2 ) .

P = {a → b, a → b → c, b → c} ,we get Shortest(P) = {a → b, b → c}.
Given two DAGs G 1 and G 2 , we define the shortest-removed
paths of G 1 and G 2 , denoted by Removed(G 1 , G 2 ), as:Removed(G 1 , G 2 ) = Shortest(Paths(G 1 ) \ Paths(G 2 )) .
That is, Removed(G 1 , G 2 ) contains the shortest prefixes in G 1
that are not in G 2 .
We define the usage change between two DAGs G 1 and G 2
as a pair Diff (G 1 , G 2 ) = (F − , F + ) where F − = Removed(G 1 , G 2 )and F + = Removed(G 2 , G 1 ). That is, the set of paths F − contains the shortest prefixes removed from G 1 while F + contains those that are added to G 2 . In Figure 2(d) we show indetail the usage change derived from the DAGs depicted in
Figures 2(b) and 2(c).

(G 1,G 2 )∈m

To pair the DAGs in the two versions we find a minimum
distance mapping according to mdist(m). Note that there
may be multiple such mappings.
For the example provided in Figure 4, the mapping produces the pairs (A1 , Bk ), (A2 , B 2 ), and so forth. We color thenodes in green/red to emphasize which nodes in the paired
DAGs are different.
From DAG Pairs to Usage Changes. We use the following notation to define the derivation of usage changes. Let
G = (N , E, r ) be a rooted DAG. Given two paths p and p ′, wewrite p ≺ p ′ if p is a strict prefix of p ′, i.e. the length of p isstrictly smaller than that of p ′ and p is a prefix of p ′. For aset of paths P, we define
Shortest(P) = {p ∈ P | ¬∃p ′ ∈ P . p ′ ≺ p} .

4

Clustering Semantic Usage Changes

In this section, we describe our approach for filtering andclustering the obtained usage changes, that is, the output of
Figure 4 described earlier. Our filters will aim to eliminate any
irrelevant, non-semantic usage changes. Then, the remaining
semantic usage changes will be clustered so to ease users in
inspecting them and eliciting security rules.
4.1

Extract Usage Changes

The input to the first step is a set of code changes. Given this
input, we derive the usage changes from each code modification, as described in Section 3. Note that each code change
results in a set of usage changes because the old and newversions of the program may instantiate multiple objects ofthe same type and use them differently in the code.

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
4.2

Filter Uninteresting Usage Changes

The goal of this procedure is, given the large list of usagechanges, to filter out the ones that are not relevant for deriving security rules. Uninteresting changes either do not affectcrypto APIs, refactor crypto API calls, or introduce/delete
code (as opposed to fixing an error). The input of the filtering
procedure is a list of usage changes. Each usage change isa pair (F − , F + ) of paths where F − contains the features thatare removed from the old version and F + contains the features added to the new version. We filter out a usage change(F − , F + ) if one of the following conditions hold:No-changes (f same ): Both F − and F + are empty sets. Thiscondition indicates that, with respect to our abstraction, the API usage is identical in both the old and the
new version of the program. This means that there
is no actual semantic change of API usage. This filter
removes the majority of the changes.
No-removals (f add ): F − is the empty set. This condition
typically indicates that a usage of type t was added
to the code. We do not use such changes since they
simply say that the crypto API was introduced.
No-additions (f rem ): F + is the empty set. This conditionindicates that a usage of type t was removed for thecode.
No-duplicates (f dup ): There is another usage change(F ′− , F ′+ ) in the set such that F − = F ′− and F + = F ′+ .
This condition indicates that there is an identical usagechange in the set of usage changes.
To see the effect of each filter, we run them in turn and report
the number of remaining usage changes at stages after eachfilter. We remark that f add and f rem together subsume f same ,but we still consider f same separately to report the numberof changes that do not affect crypto APIs (shown later inFigure 6).
4.3

R. Paletov, P. Tsankov, V. Raychev, and M. Vechev
li → . . . → l j . Given two paths p1 and p2 , we denote bycommonPrefix(p1 , p2 ) the length of the longest prefix of p1
and p2 . That is, commonPrefix(p1 , p2 ) returns the index j if
and only if p1 [0 : j] = p2 [0 : j] and p1 [0 : j + 1] , p2 [0 : j + 1].
Further, we write lev(l, l ′) to denote the Levenshtein distance [8] between the two node labels l and l ′, which captures the smallest number of modifications—insertions, deletions, and substitutions—required to change one label into
the other. As units for modifications, we use charactersfor strings, while integers, bytes (which are abstracted toconstbyte and ⊤byte ), and method names are treated as single
units. For example, it takes 1 modification (more precisely, 1
substitution) to change any method signature to a different
one. We define the Levenshtein similarity ratio between twolabels l and l ′ as:
LSR(l, l ′) = 1 −The distance between paths p1 and p2 is pathDist(p1 , p2 ) = 0
if p1 is identical to p2 , and otherwise it is defined as:
pathDist(p1 , p2 ) = 1 −Distance Between Two Paths. We use the following notation. Given a path p = l 0 → . . . → ln and two indices0 ≤ i ≤ j ≤ n, we write p[i] for li , p[i : j] for the pathj + LSR(p1 [j + 1], p2 [j + 1]),
max(|p1 |, |p2 |)where j = commonPrefix(p1 , p2 ) is the length of the longest
prefix of p1 and p2 . In the numerator, we take the size ofthe common prefix and add the result of the Levenshteinsimilarity ratio between the remaining suffixes of p1 and p2 .
In the denominator, we have the largest length of both paths.
Distance Between Two Usage Changes. We define thedistance between two sets of paths F 1 and F 2 , pathsDist(F 1 , F 2 ),as the smallest distance that we obtain by first matching
the paths in both sets and then summing their pair-wise
path distance. Given two usage changes C 1 = (F 1− , F 1+ ) andC 2 = (F 2− , F 2+ ), we define the distance to be the average over
the two distances between F 1− and F 2− and between F 1+ and F 2+ :Cluster Usage Changes

After we obtain the filtered semantic usage changes, we cluster them together to report insights about how developers
fix crypto APIs. Clustering is useful, because multiple similar changes would indicate a common misconception or acommon fix regarding the API. To perform this step, we useclassic clustering algorithms based on the same features usedin the previous steps.
We now define a metric that captures the distance between
a pair of usage changes. Our metric compares the featuresthat the usage changes add and remove from the new and,
respectively, the old version. We first define a measure of
distance between two paths and then lift this measure tocompare usage changes.

lev(l, l ′).
max(|l |, |l ′ |)usageDist(C 1 , C 2 ) =pathsDist(F 1− , F 2− ) + pathsDist(F 1+ , F 2+ ).
2

The distance metric usageDist(C 1 , C 2 ) allows us to compare
how semantically similar two usage changes are.
Hierarchical Clustering. We use an agglomerative hierarchical clustering algorithm to group similar usage changes
and structure them in a tree. Agglomerative clustering first
introduces a leaf node in the tree for each usage change
and then merges the two closest clusters according to the
distance metric. As a distance metric we use the distance
between two usage changes. The distance between clusters(also known as the linkage) is used to merge clusters of usagechanges (higher in the tree). We use complete linkage where
the distance between two clusters X and Y is given by:clusterDist(X , Y ) = max C1 ∈X,C2 ∈Y usageDist(C 1 , C 2 ) .

Inferring Crypto API Rules from Code Changes

5

The DiffCode System

In this section, we first present DiffCode, a system which
implements the abstraction for usage changes described in
Section 3 together with the filtering and clustering procedures presented in Section 4. In the following section, weshow how DiffCode can be used to infer semantic usagechanges to the Java Crypto API, based on thousands of code
modifications we have collected from GitHub.
5.1

System Overview

DiffCode is a new end-to-end system that implements theusage changes abstraction for Java APIs. Our implementation
is in Python and spans roughly 7K lines of code.
DiffCode takes as input a set of program pairs (old andnew versions of a Java program) together with a target APIclass, and outputs a list of semantic usage changes of thetarget API class together with a clustering diagram of theseusage changes. The main component of DiffCode is a lightweight AST-based program analyzer, described below.
AST-based Program Analyzer. DiffCode uses a custom
AST-based analyzer since many of the program versions
provided as input are partial programs, such as library code
without an explicit entry point and code snippets, that cannot
be easily compiled. Further, we opted for an efficient andscalable analyzer that avoids heavy-weight static analysis,
such as SPARK’s points-to analysis [19].
Our program analyzer takes as input a GitHub username,project name, and commit ID, which together identify a Javaproject version. Additionally, it takes the target API classfor which we want to discover usage changes. Our analyzer
first finds all allocation sites of the target class (which correspond to abstract objects). For each allocation site, locatedin some method m, it finds the program’s entry methods
that can lead to executions that call method m. Note that
there may be multiple such entry methods (i.e., other thanmain) if the code is a partial program or a library. For eachentry method, the analyzer performs a forward execution of
all relevant operations, such as object allocations and field
accesses, to track the set of possible values that can be assigned to fields and variables. At each branching point (e.g.,
an if statement), the analyzer forks the execution into two
executions and analyzes them independently. The result is aset of executions with derived abstract states at each method
call. Each execution is used to derive a DAG as described in
Section 3.4. Our analysis is inter-procedural, and currently
does not support deep inheritance hierarchies and virtualfunctions.

6

Case Study: Java Crypto API

We now describe a case study in which we use Java projects
collected from GitHub to learn semantic changes of the Java
Crypto API [26]. Extracting security fixes for the Java Crypto
API is relevant because: (i) developers often misuse this

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
API Class

Description

Cipher

A cryptographic cipher used for encryption and decryption
IvParameterSpec An initialization vector (IV) used in ciphers that operate in feedback mode(e.g. CBC)
MessageDigest
An engine class designed to provide
the functionality of cryptographicallysecure message digests such as SHA-1
or MD5
SecretKeySpec
A constructor for secret keys a bytearray
An engine class that provides the funcSecureRandomtionality of a Random Number Generator (RNG)
PBEKeySpec
A user-chosen password that can beused with password-based encryption

Figure 5. Target classes for learning semantic usage changes.

API [12, 22, 24], and (ii) crypto modes become obsolete overtime as security experts discover attacks, and thus new, upto-date security rules for the Java Crypto API are needed(e.g, see [30]).
More concretely, in this section we address the following research questions. First, we investigate the effectiveness of our abstraction and filters on distilling semanticcode changes, and whether these are security fixes or buggy
changes. Second, we report on our experience in clustering
code changes and eliciting security rules. Finally, we investigate the relevance of the elicited security rules by applying
these on Java projects collected from GitHub.
6.1

Experimental Setup

Data Set. To obtain our training dataset, we scanned over
30, 000 popular GitHub repositories. We selected the masterbranches of projects that use the Java Crypto API and have atleast 30 commits. We duplicated projects in case the commit
history has a common prefix. We remark that our selection
method helps DiffCode ignore toy projects that are unlikely
to contain interesting code changes. Indeed, our method
selected some of the most starred Java projects excluding
forks. For training, our selection led to 461 Java projects from
397 distinct users.
We cloned these repositories and traversed the masterbranch commits of each repository. We consider 6 target APIclasses in our case study; see Figure 5. For each commit thatchanges at least one target class, we fetched the versions
before and after the commit. Using this procedure, we collected a total of 11, 551 code changes (i.e., pairs of programs)
for all of the target classes.

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
TargetAPI ClassAfter filtering stage
f same f add f rem f dup

Rule Change
Total Filtered changes Remain.
Type
Changes f same f add f rem f dup changes

419
58
116
226
309
29

CL1 fix
bug
none

8
0
0
1
0
0
15820 15410 215

0
0
88

1
0
40

7
1
67

CL2 fix
bugs
none

1
0
0
0
4966 4909

0
0
34

0
0
12

0
0
1

1
0
10

Figure 6. Usage changes per target API class after abstraction and filtering. The actual commits are available at
http://diffcode.ethz.ch

CL3 fix
bug
none

4
0
0
1
0
0
15538 15317 106

0
0
65

0
0
10

4
1
40

6.2

CL4 fix
bug
none

1
0
0
0
1548 1520

0
0
8

0
0
4

0
0
0

1
0
16

CL5 fix
bug
none

1
0
1
0
1547 1520

0
0
8

0
0
4

0
0
0

1
1
15

Cipher
IVParameterSpec
MessageDigest
SecretKeySpec
SecureRandom
PBEKeySpec

Usage
Changes

R. Paletov, P. Tsankov, V. Raychev, and M. Vechev

15829
4967
8277
15543
26008
1549

204
24
78
120
131
21

116
12
27
55
26
17

75
11
17
45
21
17

Effectiveness of Abstraction and Filtering

In Figure 6, we give the number of usage changes for eachtarget API class and then show the effectiveness of our abstraction and filters. The second column gives the total number of usage changes, and the four columns to the right show
the number of usage changes that remain after each filtering
stage (see Section 4.2 for the list of stages). For example, thefilter f same , which removes changes that do not affect thetarget class, reduces the number of changes by more thanan order of magnitude (e.g. 419 down from 15, 829 for class
Cipher). Filtering out changes that add or remove API callsof the target class, as well as removing duplicates further reduces the number of changes by another order of magnitude.
At the end, the number of remaining changes makes thefollow-up manual inspection feasible (e.g. only 75 changes
for the Cipher class).
Security Fixes vs Buggy Changes. Next, we address twoquestions: (i) whether the collected code changes represent
security fixes or buggy changes and (ii) whether the filters
keep these while removing the non-semantic code changes.
To distinguish between security fixes and buggy changes,
we encoded five security rules supported in CryptoLint [12],a security checker for crypto APIs. We denote these rules
CL1-CL5. For instance, the first rule CL1 states: “Do not use
ECB mode for encryption”.
For each change, we check whether a rule triggers in
the old version (before applying the change) and whether it
triggers in the new version (after applying the change). Basedon the result, we classify each code change as a: (i) security
fix, if a rule triggers in the old version but not in the newversion, (ii) buggy change, if a rule triggers in the new version
but not in the old version, and (iii) non-semantic change, if
the rule triggers identically in both versions.
In Figure 7, we give the number of usage changes classified into security fixes, buggy changes, and non-semanticchanges with respect to rules CL1-CL5. Note that the total number of changes varies across the rules as we countonly changes that are applicable to the rule. For example,
CL1 refers to the class Cipher, for which we have collected

Figure 7. Filtered security fixes ( fix ), buggy changes ( bug ),and non-semantic changes (none) using the four filters. The
right-most column shows the type of changes that remain
after applying all filters.

15, 829 usage changes in total. In the figure, we also show
the number of usage changes removed by each filter.
The data shows two important findings. First, most codechanges have no-semantic meaning with respect to theserules. The filters, however, effectively eliminate the nonsemantic changes, where the most effective filter is f same
which can detect and eliminate code refactorings. Second,
the semantic changes are not filtered out. Only 1 semanticchange is eliminated by the f dup filter to remove a duplicate
security fix (see CL1).
The data in Figure 7 also shows that most of the changes
are indeed security fixes, not buggy changes. Namely, over
80% of the code changes correspond to actual security fixes.
6.3

Clustering Security Fixes and Eliciting Rules

Next, we report on our experience in eliciting rules fromthe security fixes. We inspected each fix, together with anyother modifications that are similar (in terms of distance),
on GitHub. In more detail, we inspected the concrete code
patch, the commit message, and any additional commentsthat describe the commit.
Clustering Security Fixes. We constructed a dendrogramfor each target API class, using the hierarchical clustering
algorithm described in Section 4.3. We depict a (partial) dendrogram derived for the Cipher API class in Figure 8. Thisdendrogram shows three usage changes. These changes showthat developers are switching from the insecure ECB mode ofInferring Crypto API Rules from Code Changes

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA

CiphergetInstance

arg1:AES/ECB

CiphergetInstance

arg1:AES/GCM

Cipherinit

CiphergetInstance

arg1:AES/ECB

CiphergetInstance

arg1:AES/CBC

Cipherinit

arg3:IVParameterSpec

arg3:IVParameterSpec

CiphergetInstance

arg1:AES

CiphergetInstance

arg1:AES/CBC

Cipherinit

arg3:IVParameterSpec

[5]

[6]

Rule R7[4] [18]...
Figure 8. Partial hierarchical clustering for the Cipher API class. All three usage changes show a switch from the insecure
ECB mode of AES to the more secure CBC and GCM modes. The merge of the three usage changes identifies the security
rule R7 stating that the cipher should not be used in ECB mode. We give links to concrete GitHub revisions in the references.
AES to the more secure CBC and GCM modes. We also givethe concrete commits (with links in the references) that are
identified with these usage changes. The top-most two usagechanges are joined together to form a cluster, and then thiscluster is joined with the third usage change. We found suchinformation provided by the clustering helpful to navigate
through and inspect the security fixes.
Rules. We consider rules of the form t : φ where t ∈ Types
is a type and φ is a logical formula interpreted over a set
S ⊆ P(Methods × AStates) of method and abstract state pairs.
For example, the logical formulaφ ≡ ∃(m, σ a ) ∈ S. m = getInstance(X ) ∧ ∆a (X ) = SHA-1
is satisfied, denoted S |= φ, if the set S contains a pair (m, σ a )such that m = getInstance(X ) and σ a (X ) = SHA-1. A rulet : φ matches an abstract object a of a given program with
abstract uses AUses if type(a) = t and AUses(a) |= φ. We
say that a rule t : φ is applicable to an abstract object a if
type(a) = t. For brevity, we write
getInstance(X ) ∧ X = SHA-1
as a shorthand for the logical formula given above. We sometimes conjoin multiple rules to express more complex ones.
For example, the composite rule (t 1 : φ 1 ) ∧ (t 2 : φ 2 ) matchesa program P if both t 1 : φ 1 and t 2 : φ 2 match some, possibly
different, abstract objects in P.
Elicited Rules. Using DiffCode on our data set of Javaprojects, we managed to discover a number of different security rules, which we also validated by checking security
papers, blogs, and bulletins. In Figure 9 we list all security
rules. Out of these, R2, R7, R9, R10, R11, R12 are known
and have been documented. For details on these we refer thereader to [12]. We next describe some of the other rules.
Rule R1 states that SHA-256 should be used instead of
SHA-1. Indeed, security researchers have recently announced
the first practical technique for generating a collision for

SHA-1 [30], and they have warned developers that it is recommended to switch to the more secure SHA-256.
Rule R3 states that the preferred mode for using the
SecureRandom class is SHA-1PRNG, which is initially seeded via
a combination of system attributes and the java.security entropy gathering device. Later, we have found the motivation
to be described in [2].
Rule R4 states that SecureRandom.getInstanceStrong()
should be avoided on server-side code running on Solaris/Linux/MacOS where availability is important, as documented
in [28]. This is because SecureRandom.getInstanceStrong()
returns the NativePRNGBlocking mode of SecureRandom, which
may block and thus developers suggest to avoid it [28].
Rule R5 states that the BouncyCastle provider should
be used instead of the default Java Crypto API provider
because BouncyCastle does not have the 128 bit secret key
restriction [3].
Rule R6 detects that SecureRandom is vulnerable on Android SDK versions 16, 17, and 18 if the Linux PRNG module
is not installed [1]. The implementation of the check HAS_LPRNG
is described in [1].
Rule R8 states that Cipher should not be used in DES mode
because this mode is no longer considered secure [23].
Rule R13 states that developers should add integrity after
having exchanged a symmetric key, which is frequently donewith an asynchronous cipher such as RSA. A common fix is
to switch to the AES cipher with or in combination with
HMAC [6]. Note that, to match vulnerable projects, rule R13
is expressed as a composite rule that refers to three distinct
objects – two objects of type Cipher and one object of typeMac. We remark that the rule matches any projects that havethe two Cipher objects but lacks the required Mac object. In
particular, the rule does not explicitly define in which orderthese objects are declared and used.
Overall, while some of these rules may be known to somesecurity researchers, with the DiffCode system we were

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA

R. Paletov, P. Tsankov, V. Raychev, and M. Vechev

ID

Description

Rule

R1

Use SHA-256 instead of SHA-1 [30]

MessageDigest : getInstance(X ) ∧ X =SHA-1

R2

Do not use password-based encryption with iterations count less than 1000 [7] PBEKeySpec : <init>(_,_,X,_) ∧ X <1000

R3

SecureRandom should be used with SHA-1PRNG [2]SecureRandom : <init>(X ) ∧ X ,SHA-1PRNG

R4SecureRandom with getInstanceStrong should be avoided

SecureRandom : ¬getInstanceStrong

R5

Use the BouncyCastle provider for Cipher

Cipher : getInstance(_,X ) ∧ X ,BCR6

The underlying PRNG is vulnerable on Android v16-18 [17]SecureRandom : <init>(_) ∧ ¬LPRNG ∧ MIN_SDK_VERSION≥16

R7

Do not use Cipher in AES/ECB mode [9]Cipher : getInstance(X )∧ (X =AES ∨ X =AES/ECB)

R8

Do not use Cipher with DES mode [23]Cipher : getInstance(X ) ∧ X =DES

R9

IvParameterSpec should not be initialized with a static byte array [9]IvParameterSpec : <init>(X ) ∧ X ,⊤byte[]

R10

SecretKeySpec should not be static

SecretKeySpec : <init>(X ) ∧ X ,⊤byte[]

R11

Do not use password-based encryption with static salt

PBEKeySpec : <init>(_,X,_,_) ∧ X ,⊤byte[]

R12

Do not use SecureRandom static seed

SecureRandom : setSeed(X ) ∧ X ,⊤byte[]

R13

Missing integrity check after symmetric key exchange [6](Cipher : getInstance(X ) ∧ startsWith(X,AES/CBC))∧ (Cipher : getInstance(Y ) ∧ Y =RSA)∧ ¬(Mac : getInstance(Z ) ∧ startsWith(Z,Hmac)

Figure 9. Security rules derived from security fixes applied to the Java Crypto API.
able to systematically derive all of them. Further, DiffCodeenabled us to create a single checker for all of these rules.
On Automating Rule Elicitation. We remark that DiffCode can also automatically suggest a rule by constructing a
predicate that matches any use that has the features present
in the old versions and does not have those added to the newversions. Note that this predicate would match any usagethat is not fixed according to the code changes. As a simple
example, consider the removed and added features depicted
in Figure 2(d). The generated security rule would be
Cipher : (getInstance(X ) ∧ X = AES)∧(getInstance(Y ) ⇒ Y , AES/CBC/PKCS5Padding)∧(<init>(X ′, _, _, Y ′) ⇒ Y ′ , IVParameterSpec)This rule captures that AES Ciphers which use the default
AES mode, and neither use the AES/CBC/PKCS5Padding mode
nor pass an object of type IVParameterSpec to the constructor, must be fixed. While using the above method one cancompletely automate the generation of rules, identifying
whether a rule is security-relevant in a purely automatedmanner is challenging and goes beyond the scope of this
work.
6.4

Relevance of The Elicited Security Rules

To evaluate the relevance of the discovered security rules,
we developed a security checker, called CryptoChecker,
that supports all rules in Figure 9. We ran CryptoChecker
on 519 Java projects. These include all 463 Java projects weused for training as well as additional 56 projects which we
downloaded after eliciting the rules. We report the number

Rule

Applicable(% of total)

Matching(% of appl.)

R1
R2
R3
R4
R5
R6
R7
R8
R9
R10
R11
R12
R13

257
64
305
305
211
59
211
211
124
232
64
305
8

(49.5%)(12.3%)(58.8%)(58.8%)(40.7%)(11.4%)(40.7%)(40.7%)(23.9%)(44.7%)(12.3%)(58.8%)(1.5%)

89
15
289
3
206
48
60
20
7
12
7
1
4

(34.6%)(23.4%)(94.8%)(1%)(97.6%)(81.4%)(28.4%)(9.5%)(5.6%)(5.2%)(11%)(0.3%)(50%)

Figure 10. Rule violations for the analyzed projects.

of discovered rule violations in Figure 10. For each security
rule, we give (i) the total number of projects that have at least
one usage applicable to the security rules, and (ii) the numberof projects that have at least one insecure usage according toour rules. For instance, rule R1 is only applicable to usagesof the API class MessageDigest as it stipulates how classesof type MessageDigest should be instantiated. The number
257 in the first row thus indicates that there are 257 projects(49.5% of the 519 projects) that have at least one usage oftype MessageDigest. The matching column indicates that 89
out of the 257 projects (34.6%) have at least one usage thatmatches rule R1 .

Inferring Crypto API Rules from Code Changes
Overall, the data in Figure 10 confirms recent findings thatdevelopers struggle to use the Java Crypto API correctly [24].
In > 57% of the projects CryptoChecker discovers at least
one security rule that is matched. We remark that CryptoLint [12], a similar checker to CryptoChecker, can beused to check some (but not all) of CryptoChecker’s rules.
However, since CryptoLint is not publicly available, we wereunable to compare our results.
Finally, we used some of the reports of CryptoChecker
to report 15 security violations, 3 of which were confirmed.
The reported issues are listed at http://diffcode.ethz.ch.

7

Related WorkIn this section, we survey several recent works that are mostclosely related to ours.
Misuse of Crypto APIs. The authors of [22] describe a
set of security guidelines related to the use crypto APIs, e.g.
that password-based encryption must be used with a random seed, encryption keys must not be hard-coded, and soforth. Applications that do not follow these guidelines are
considered vulnerable. They examine 49 Android applications and show that 87.8% of them suffer from at least one
vulnerability.
The authors of [11] present a manual analysis of different
crypto APIs (OpenSSL, Java, PyCrypto, and others) and discuss seven problems related to API misuses, such as reuse of
initialization vectors, lack of code samples in the API documentation, safe API defaults, and so forth. The scope of thisreport is on crypto APIs, not on the applications that use
these APIs. In [24], the authors report on a survey to discover
why developers often fail to use crypto APIs correctly. They
also present suggestions to API developers that may mitigate
the problem of API misuse.
Detecting Misuse of Crypto APIs. Several works consider the problem of automatically detecting misuse of crypto
API in Java applications. OWASP provides a list of static
analysis tools [5] that target security issues, however thesetools have a very limited set of crypto checks (e.g. see FindSecBugs [4]). CryptoLint [12] is a specialized system thatchecks Android applications for crypto API misuses with six
fixed rules, such as “Do not use ECB mode for encryption”.
To check these properties, CryptoLint statically computes a
program slice immediately before invoking a crypto API andchecks properties on the arguments passed to that API. Theyevaluate >11K Android applications and show that 88% of
the applications violate at least one rule. Compared to CryptoLint, CryptoChecker supports a more comprehensive setof security rules.
The CMA analyzer, presented in [29] is very similar to [12]and also targets finding misuses of crypto APIs in Android.
Compared to [12], CMA considers more security rules.

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
AmanDroid [31] is a system for precise static analysis ofAndroid applications. AmanDroid computes a dependency
graph that captures control- and data-flow dependencies forall objects. The security analysis is then phrased as graphqueries over the dependency graph. For example, we cancheck an application for absence of data leaks by checking
that there is no path from a source to a sink. AmanDroid canbe also used to check whether applications misuse crypto
APIs by encoding the rules of [11, 13, 24] in terms of graphqueries. In [16], the authors explain the concepts behind
AmanDroid in a more general, cleaner setting.
Misuse of crypto APIs is not an Android or Java-specificproblem: the evaluation of a dynamic analysis tool for iOS [20]found that over 65% of the tested iOS applications suffer fromvulnerabilities due to API misuse.
Repairing Misuse of Crypto APIs. The CDRep systempresented in [22] can be used to detect and repair misusesof Android’s crypto API. For the detection step, CDRep performs an analysis similar to the one presented in [12]. Givenan Android APK, CDRep detects the instructions responsible
for a particular misuse of the crypto API. The responsible
instructions include the call to a particular crypto API, called
the indicator instruction, and instructions on which the indicator instruction depends. For example, one security rulestates that applications must not use encryption in ECB mode.
The responsible instructions that violate this rule would include: the call to the encrypt method, the instruction that
constructs the encryption object, and the instruction that
initializes the encryption-scheme string (e.g. “AES/ECB”)
passed to the encryption constructor. After identifying the
instructions responsible for a given cryptographic misuse,
CDRep uses manually pre-defined patch templates to suggest
candidate repairs.
Learning from Code. Several prior works check for API
errors by first learning a likely specification of a programand its API calls [13, 18]. The recent APISan system [32]automatically infers the correct usage of APIs by observing
the contexts of the calls from multiple projects. For example, APISan can learn that the return value of a method istypically checked for null and then it can report outliers tothis learned specification. This allows APISan to check large
codebases in a precise and scalable way for given predefined
types of issues such as null dereferences and overflows. In
contrast to these works, we focus on crypto APIs for which(i) we do not know the kind of issues that may be present and(ii) the majority of the projects misuse the APIs. The workof Long and Rinard [21] considers the reverse task of ours
and learns from correct code to guide automatic generationof bug fixes.
Learning from Code Changes. Several works propose
to learn from previous code changes to help developers complete a new change. A system by Zimmermann et al. [33]

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
warns developers if a newly developed change only does asubset of what other changes did. A more recent work by
Nguyen et al. [25] developed a code completion engine thatprecisely predicts code for new changes based on code inprevious code changes. In contrast to our approach, however,these works cannot find issues in existing code and makepredictions only for code modifications.

8

Conclusion

We presented a new data driven approach for extracting
semantically meaningful API usage changes from concrete
code fixes collected by processing public repositories. The
approach is based on an abstraction for code changes which
captures the implications of a change to objects of the Crypto
API. These implications are represented as semantic featuresthat are removed from the old and added to the new versionof the program. Our abstraction enables us to distill relevant
semantic changes using filters that eliminate purely syntactic
modifications. As a final step we (hierarchically) cluster theremaining, semantically meaningful security fixes, enabling
us to derive new security rules.
We also presented DiffCode, a system that implements
our data driven approach. We applied DiffCode to Java codechanges collected from GitHub and extracted security fixes
for the Java Crypto API. Based on these results, we identified 13 relevant security rules which we implemented in a
new security checker called CryptoChecker. We evaluatedCryptoChecker on a number of public Java projects, discovering misuses of the Java Crypto API in > 57% of theanalyzed projects.
The data driven approach presented in this work allowed
us to systematically derive relevant security rules some ofwhich are missing from existing checkers. We believe that
this work is an important step towards solving the general
problem of automatically deriving API misuse checks.

References[1] 2013. Some SecureRandom Thoughts. https://android-developers.
googleblog.com/2013/08/some-securerandom-thoughts.html[2] 2015. The Right Way to Use SecureRandom. https://tersesystems.
com/2015/12/17/the-right-way-to-use-securerandom/[3] 2016.
Which security implementation should I use: Bouncy
Castle or JCA?
https://blog.idrsolutions.com/2016/08/
which-security-implementation-should-i-use-bouncy-castle-or-jca/[4] 2017. FindSecBugs Bugs Patterns. https://find-sec-bugs.github.io/
bugs.htm[5] 2017. OWASP Source Code Analysis Tools. https://www.owasp.org/
index.php/Source_Code_Analysis_Tools.
[6] 2017. Top 10 developer Crypto mistakes. https://littlemaninmyhead.
wordpress.com/2017/04/22/top-10-developer-crypto-mistakes/[7] Martín Abadi and Bogdan Warinschi. 2005. Password-Based Encryption
Analyzed. Springer Berlin Heidelberg, Berlin, Heidelberg, 664–676.
https://doi.org/10.1007/11523468_54[8] Mikhail J. Atallah and Susan Fox (Eds.). 1998. Algorithms and Theoryof Computation Handbook (1st ed.). CRC Press, Inc., Boca Raton, FL,USA.

R. Paletov, P. Tsankov, V. Raychev, and M. Vechev[9] M. Bellare and P. Rogaway. 2017. Course notes for introduction to modern cryptography. cseweb.ucsd.edu/users/mihir/cse207/classnotes.
html[10] Patrick Cousot and Nicolas Halbwachs. 1978. Automatic Discovery ofLinear Restraints Among Variables of a Program. In Proceedings of the
5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming
Languages (POPL ’78). ACM, New York, NY, USA, 84–96. https://doi.
org/10.1145/512760.512770[11] Somak Das, Vineet Gopal, Kevin King, and Amruth Venkatraman. [n.
d.]. IV = 0 Security Cryptographic Misuse of Libraries. Technical Report.
MIT.
[12] Manuel Egele, David Brumley, Yanick Fratantonio, and Christopher
Kruegel. 2013. An Empirical Study of Cryptographic Misuse in Android
Applications. In Proceedings of the 2013 ACM SIGSAC Conference on
Computer &#38; Communications Security (CCS ’13). ACM, New York,NY, USA, 73–84. https://doi.org/10.1145/2508859.2516693[13] Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf. 2001. Bugs As Deviant Behavior: A General Approach toInferring Errors in Systems Code. SIGOPS Oper. Syst. Rev. 35, 5 (Oct.
2001), 57–72. https://doi.org/10.1145/502059.502041[14] Sascha Fahl, Marian Harbach, Thomas Muders, Lars Baumgärtner,
Bernd Freisleben, and Matthew Smith. 2012. Why Eve and Mallory
Love Android: An Analysis of Android SSL (in)Security. In Proceedingsof the 2012 ACM Conference on Computer and Communications Security(CCS ’12). ACM, New York, NY, USA, 50–61. https://doi.org/10.1145/
2382196.2382205[15] Martin Georgiev, Subodh Iyengar, Suman Jana, Rishita Anubhai, Dan
Boneh, and Vitaly Shmatikov. 2012. The Most Dangerous Codein the World: Validating SSL Certificates in Non-browser Software.
In Proceedings of the 2012 ACM Conference on Computer and Communications Security (CCS ’12). ACM, New York, NY, USA, 38–49.
https://doi.org/10.1145/2382196.2382204[16] Andrew Johnson, Lucas Waye, Scott Moore, and Stephen Chong. 2015.
Exploring and Enforcing Security Guarantees via Program Dependence Graphs. In Proceedings of the 36th ACM SIGPLAN Conference on
Programming Language Design and Implementation (PLDI ’15). ACM,
New York, NY, USA, 291–302. https://doi.org/10.1145/2737924.2737957[17] David Kaplan, Sagi Kedmi, Roee Hay, and Avi Dayan. 2014. Attacking the Linux PRNG On Android: Weaknesses in Seeding of Entropic
Pools and Low Boot-Time Entropy. In 8th USENIX Workshop on Offensive Technologies (WOOT ’14). USENIX Association, San Diego,
CA. https://www.usenix.org/conference/woot14/workshop-program/presentation/kaplan[18] Ted Kremenek, Paul Twohey, Godmar Back, Andrew Ng, and Dawson
Engler. 2006. From Uncertainty to Belief: Inferring the Specification
Within (OSDI ’06). USENIX Association, Berkeley, CA, USA, 161–176.
http://dl.acm.org/citation.cfm?id=1298455.1298471[19] Ondrej LhotÃąk. 2002. Spark: a flexible points-to analysis framework
for Java.
[20] Yong Li, Yuanyuan Zhang, Juanru Li, and Dawu Gu. 2014. iCryptoTracer: Dynamic Analysis on Misuse of Cryptography Functions in
iOS Applications. In Network and System Security: 8th International
Conference. 349–362. https://doi.org/10.1007/978-3-319-11698-3_27[21] Fan Long and Martin Rinard. 2016. Automatic Patch Generation
by Learning Correct Code. In Proceedings of the 43rd Annual ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL ’16). ACM, New York, NY, USA, 298–312. https://doi.org/10.
1145/2837614.2837617[22] Siqi Ma, David Lo, Teng Li, and Robert H. Deng. 2016. CDRep: Automatic Repair of Cryptographic Misuses in Android Applications.
In Proceedings of the 11th ACM on Asia Conference on Computer andCommunications Security (ASIA CCS ’16). ACM, New York, NY, USA,711–722. https://doi.org/10.1145/2897845.2897896

Inferring Crypto API Rules from Code Changes[23] Dhruv Mohindra. 2016. Do not use insecure or weak cryptographic
algorithms. https://www.securecoding.cert.org/confluence/display/
java/MSC61-J.+Do+not+use+insecure+or+weak+cryptographic+
algorithms[24] Sarah Nadi, Stefan Krüger, Mira Mezini, and Eric Bodden. 2016. Jumping Through Hoops: Why Do Java Developers Struggle with Cryptography APIs?. In Proceedings of the 38th International Conference on
Software Engineering (ICSE ’16). ACM, New York, NY, USA, 935–946.
https://doi.org/10.1145/2884781.2884790[25] Anh Tuan Nguyen, Michael Hilton, Mihai Codoban, Hoan Anh Nguyen,
Lily Mast, Eli Rademacher, Tien N. Nguyen, and Danny Dig. 2016. API
Code Recommendation Using Statistical Learning from Fine-grained
Changes. In Proceedings of the 2016 24th ACM SIGSOFT International
Symposium on Foundations of Software Engineering (FSE 2016). ACM,
New York, NY, USA, 511–522. https://doi.org/10.1145/2950290.2950333[26] Oracle. 2017. Java Cryptography Architecture (JCA) Reference
Guide.
http://docs.oracle.com/javase/7/docs/technotes/guides/
security/crypto[27] Veselin Raychev, Martin Vechev, and Eran Yahav. 2014. Code Completion with Statistical Language Models. In Proceedings of the 35th ACM
SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). ACM, 419–428. https://doi.org/10.1145/2594291.
2594321[28] Amit Sethi. 2016.
Proper use of Java SecureRandom.
https://www.synopsys.com/blogs/software-security/
proper-use-of-javas-securerandom/[29] Shao Shuai, Dong Guowei, Guo Tao, Yang Tianchang, and Shi Chenjie.
2014. Modelling Analysis and Auto-detection of Cryptographic Misuse

PLDI’18, June 18–22, 2018, Philadelphia, PA, USA
in Android Applications. In Proceedings of the 2014 IEEE 12th International Conference on Dependable, Autonomic and Secure Computing(DASC ’14). IEEE Computer Society, Washington, DC, USA, 75–80.
https://doi.org/10.1109/DASC.2014.22[30] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik
Markov, Alex Petit Bianco, and Clement Baisse. 2017. Announcing thefirst SHA1 collision.
[31] Fengguo Wei, Sankardas Roy, Xinming Ou, and Robby. 2014. Amandroid: A Precise and General Inter-component Data Flow Analysis
Framework for Security Vetting of Android Apps. In Proceedingsof the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS ’14). ACM, New York, NY, USA, 1329–1341.
https://doi.org/10.1145/2660267.2660357[32] Insu Yun, Changwoo Min, Xujie Si, Yeongjin Jang, Taesoo
Kim, and Mayur Naik. 2016.
APISan: Sanitizing API Usages through Semantic Cross-Checking. In 25th USENIX Security
Symposium (USENIX Security 16). USENIX Association, Austin,
TX, 363–378. https://www.usenix.org/conference/usenixsecurity16/
technical-sessions/presentation/yun[33] Thomas Zimmermann, Peter Weisgerber, Stephan Diehl, and Andreas
Zeller. 2004. Mining Version Histories to Guide Software Changes. In
Proceedings of the 26th International Conference on Software Engineering(ICSE ’04). IEEE Computer Society, Washington, DC, USA, 563–572.
http://dl.acm.org/citation.cfm?id=998675.999460