Scalable Taint Specification Inference with Big CodeVictor Chibotaru

Benjamin Bichsel

DeepCode AG, Switzerland
chibo@deepcode.ai

ETH Zurich, Switzerland
benjamin.bichsel@inf.ethz.ch

Veselin Raychev

Martin Vechev

DeepCode AG, Switzerland
veselin@deepcode.ai

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

Abstract
We present a new scalable, semi-supervised method for inferring taint analysis specifications by learning from a large
dataset of programs. Taint specifications capture the roleof library APIs (source, sink, sanitizer) and are a critical ingredient of any taint analyzer that aims to detect security
violations based on information flow.
The core idea of our method is to formulate the taint specification learning problem as a linear optimization task overa large set of information flow constraints. The resulting
constraint system can then be efficiently solved with stateof-the-art solvers. Thanks to its scalability, our method caninfer many new and interesting taint specifications by simultaneously learning from a large dataset of programs (e.g., asfound on GitHub), while requiring few manual annotations.
We implemented our method in an end-to-end system,
called Seldon, targeting Python, a language where static
specification inference is particularly hard due to lack oftyping information. We show that Seldon is practically effective: it learned almost 7, 000 API roles from over 210, 000
candidate APIs with very little supervision (less than 300 annotations) and with high estimated precision (67%). Further,using the learned specifications, our taint analyzer flagged
more than 20, 000 violations in open source projects, 97% of
which were undetectable without the inferred specifications.
CCS Concepts • Security and privacy → Information
flow control; • Theory of computation → Program specifications; • Computing methodologies → Semi-supervised
learning settings.
Keywords Specification Inference, Taint Analysis, Big Code
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 ’19, June 22–26, 2019, Phoenix, AZ, USA© 2019 Copyright held by the owner/author(s). Publication rights licensed
to ACM.
ACM ISBN 978-1-4503-6712-7/19/06. . . $15.00
https://doi.org/10.1145/3314221.3314648

ACM Reference Format:
Victor Chibotaru, Benjamin Bichsel, Veselin Raychev, and Martin
Vechev. 2019. Scalable Taint Specification Inference with Big Code.
In Proceedings of the 40th ACM SIGPLAN Conference on Programming
Language Design and Implementation (PLDI ’19), June 22–26, 2019,
Phoenix, AZ, USA. ACM, New York, NY, USA, 22 pages. https://doi.
org/10.1145/3314221.3314648

1

Introduction

A wide class of security vulnerabilities occurs when usercontrolled data enters a program via a library API (a source)
and flows into a security-critical API (a sink). For example,
a source may read a field in a web form or a cookie anda sink may write to arbitrary files on the server, execute
arbitrary database commands (allowing sql injections) or
render HTML pages (allowing cross-site scripting).
Failure to sanitize information flow from sources to sinks
potentially affects the privacy and integrity of entire applications. As a result, there has been substantial interest in
automated reasoning tools which detect such unsanitizedflows, using both static and dynamic methods [18, 23, 27, 28].
While useful, all of these tools inherently rely on an existing
specification that precisely describes the set of sources, sanitizers, and sinks the analyzer should consider. We refer tosuch a specification as a taint specification.
Key Challenge: Obtaining a Taint Specification. Obtaining such a specification for modern languages and libraries
can be very challenging: to determine the role of a candidate
API (source, sink, sanitizer, or none), one would have to inspect how information flows in and out of that API and howthat information is used. Manually doing so over thousandsof libraries with APIs often appearing in different contexts,
is prohibitive.
To reduce this manual annotation burden, several works
have proposed methods for automatically learning taint specifications (e.g., [4, 17, 24]). While promising, these works
have several key drawbacks: either they work in a fully supervised manner requiring the user to manually annotate
all sources and sinks in the training dataset [24], or work ina semi-supervised manner but do not scale beyond smaller
programs [17], or require test cases and dynamic program instrumentation [4]. Further, all three of these methods target
strongly typed languages (Java [4, 24] and C# [17]).

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
This Work: Scalable Semi-Supervised Learning. In thiswork we propose a new, scalable method for learning likely
taint specifications in a semi-supervised manner. Given an
input dataset of programs D where only a very small subsetof the APIs A M used by programs in D is manually annotated, our method infers specifications for the remaining,much larger un-annotated set of APIs AU used by programs
in D. Unlike [24], to infer the taint specification for the APIsin AU , our approach leverages interactions among the APIsin AU and A M observed in the programs from D.
The core technical idea of our approach is to formulate
the taint specification inference problem as a linear optimization task, allowing us to leverage state-of-the-art solvers forhandling the resulting constraint system. Importantly, unlike [17], our method scales to learning over large datasetsof available programs D (e.g., as found on GitHub), criticalfor increasing the number and quality of discovered specifications. To demonstrate its effectiveness, we implemented
and evaluated our approach for Python, a dynamic language
where discovering taint specifications is particularly challenging (e.g., we can no longer rely on type information).
The overall flow of our end-to-end pipeline is shown in
Fig. 1. The input to the training phase is a dataset of programs D where only a very small number of APIs A M are
annotated as sources, sinks, and sanitizers (in our evaluation,106). We then apply our semi-supervised learning procedure
based on the linear formulation, inferring 6 896 roles for theremaining APIs AU . These learned specifications AU canthen be examined by an expert or together with A M be provided as input to a taint analyzer which will then searchfor vulnerabilities (a path between a source and a sink notprotected by a sanitizer) based on the specifications.
Main Contributions. Our main contributions are:
• A formulation of the taint specification inference problem as linear optimization (§4).
• An end-to-end implementation of the inference method
for Python in a tool called Seldon (§5).
• A thorough experimental evaluation indicating Seldon
scales linearly with dataset size and can learn usefuland new taint specifications with high precision: 67%
on average (§7).
• A taint analyzer that uses the learned specifications
to identify thousands of potential security violationsin open-source projects. We examined some of these
violations manually and disclosed them to maintainersof the code (§7). The tool is freely available1 and iscurrently being used by Python developers in a pushbutton manner (about 1500 usages in January 2019).

1 https://www.deepcode.ai/

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev
sourceSeed specs:A M
linearoptimization
Training data:D<
sanitizer
&lt;
html

<
&lt;

Learned specs:AU

⚠
html

sink

Bug detector

Figure 1. High-level overview of Seldon.

2

Overview

We now provide an informal explanation of our method on
the example in Fig. 2. Full formal details are provided later.
Code Snippet. Fig. 2a shows a code snippet taken from areal code repository that we slightly adapted for brevity. It
uses Flask, a Python microframework for web development
and werkzeug, a web application library. The snippet (i) obtains the name of the file attached to a user POST request
in Line 10, (ii) sanitizes the name in Line 11, and (iii) saves
the file in Line 14. Proper sanitization in Line 11 is critical,
as omitting it would enable attackers to use relative paths tostore arbitrary files in arbitrary locations of the filesystem.
Taint Analysis. Fig. 2b shows the corresponding propagation graph which captures the information flow between different events in Fig. 2a. In addition to the graph, running taintanalysis on the code snippet in Fig. 2a requires a specificationof security-related events describing which events (i) represent user input (sources), (ii) sanitize user input (sanitizers),or (iii) must be protected by sanitizers to prevent vulnerabilities (sinks). In our example, request.files['f'].filename
is a source (colored in blue), secure_filename is a sanitizer(colored in green), and save is a sink (colored in red). Givensuch a specification, taint analysis checks if there is information flow from a source to a sink that does not traverse asanitizer, which amounts to a vulnerability.
Encoding Assumptions. The quality of a taint analyzer critically depends on the quality of its specification: an incomplete specification prevents detecting all vulnerabilities thatinvolve missing parts of the specification. Seldon takes as input the propagation graphs of many applications, where therole of most events is unknown. For each event in the graph,
it generates variables whose scores indicate the likelihood of
this event having a particular role. For example, referring toevent request.files['f'].filename as a, it introduces threevariables, a src , a san , and a snk . Seldon then searches for a joint
assignment of scores to each variable. Because we restrict
the scores of each variable to be between 0 and 1, we caninterpret the resulting values as probabilities. For example,
a src = 0.98 means that event a most likely is a source.
As a next step, Seldon generates a constraint system that
encodes reasonable assumptions on valid scores, shown in
Fig. 2c. For example, constraint (1) encodes the belief that, if
a is a source (i.e., a src is high), and b is a sanitizer (i.e., b san ishigh), then at least one of the events receiving information

Scalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USAabrequest.files['f'].filename

secure_filename()

1 from yak.web import appe

2 from flask import requestf

4 import os
5
6 blog_dir = app.config['PATH']

app.config['PATH']
os.path.join()

3 from werkzeug import secure_filenameдrequest.files['f']request.files['f'].save()

7
8 @app.route('/media/', methods=['POST'])cos.path.exists()d

Save to disk(b) Propagation graph.

9 def media():11

filename = request.files['f'].filename
filename = secure_filename(filename)12path = os.path.join(blog_dir, filename)13

if not os.path.exists(path):

10

14

request.files['f'].save(path)a src + b san ≤ c snk + f snk + d snk + C(1)

a src + c san ≤ f snk + d snk + C

(2)

b

(3)

san

+d

snk

≤a

src

+C

···

(a) Code snippet from real code.

(c) Constraints.

Figure 2. Example illustrating the workflow of Seldon.
flow from b must be a sink (i.e., the sum of their sink scores
must be high). In constraint (1), C is a constant that intuitively
controls the strength of the implication (we use C = 0.75).
Likewise, constraint (2) enforces that if a is a source and c
is a sanitizer, then one of f or d must be a sink. We note that,
because c is not actually a sanitizer, constraint (2) should not
be enforced. Because in this case, c san is likely to be small,the constraint will indeed only have a minor effect on thesolution to the constraint system.
Handling Ambiguous Targets of Events. Of course, if two
events in different program locations target the same program element (e.g., two function calls to the same function),
we try to represent them with the same variables in the constraint system. However, in Python, this is non-trivial as itis hard to determine which function is targeted by a givenfunction call. We elaborate more on this issue in Section §3.2,
but provide a simple example here.
Concretely, a programmer might replace the two occurrences of request.files['f'] in Fig. 2a by a function argument f instead, after replacing Line 9 by def media(f):.
Then, the target of event d is unclear (analogously fora). Seldon therefore collects two possible representations ofd: r 1 = media(param f).save() (indicating function save ofparameter f of media) and r 2 = f.save() (indicating function
save() of f). The resulting constraint system is analogous toFig. 2c, except for replacing variables by averages of all possible representations of their respective
 event. For example,
we would replace d src by 12 r 1src + r 2src .
If another source candidate event x in a different program
location has two possible representationr 1 and r 3 , the con
straint system will use 12 r 1src + r 3src to capture it, sharing

variable r 1src with d. As a consequence, the scores of x and d
are correlated (increasing r 1src increases the score of both xand d being a source).
Solving the Constraint System Resulting from Big Code.
In this way, Seldon determines the propagation graphs fortens of thousands of Python source files, yielding roughly
half a million constraints and 210,000 candidate events (forbeing sources, sanitizers, and sinks).
As programs in our training dataset need not always follow the intuitive assumptions on information flow, we may
not be able to solve the constraint system from Fig. 2c exactly. Instead, we relax it, minimizing the violation of all
constraints, while L 1 -regularizing by the sum of scores (i.e.,favoring solutions with fewer inferred specifications).

3

Propagation Graphs

In this section we describe the concept of a propagationgraph and discuss how to use it for analysis and learning.
3.1

Events and Information Flow

The propagation graph G = (V , E) of a program P consistsof a set of events V and a set of edges E capturing information flow, typically determined by static analysis. The set of
events V captures all relevant actions in P that propagate
information. Examples of events include function calls andglobal variable reads while examples of flows include thefact the return value of a function is used as an argument toanother function. In practice, V is usually restricted to events
relevant to a particular setting, e.g., if we are interested inevents relating to security, we can ignore actions that add

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
1 from base_driver import ThreadDriver2
3 class ESCPOSDriver(ThreadDriver):4

def status(self, eprint):
self.receipt('<div>'+msg+'</div>')

5

Figure 3. Example illustrating representation of function
call events.
two integers. The graph G is built by applying a static information propagation analysis on P (e.g., [17]) and thus edges
represent an over-approximation of the actual information
flow. To maintain consistency with standard notation forgraphs, the set E captures information flow and not events(which are captured in V ).
3.2

Representation of Events

An event v ∈ V is captured by an expression in the program,for example a field read or a function call expression. To
represent the possible targets an event v can resolve to, wedefine the function Rep(v). For example, if v is a function
call, Rep(v) will be an expression describing functions thatv can possibly resolve to.
Depending on the program and the type system of thelanguage, the expression Rep(v) will be of a different granularity. For instance, for a statically typed language, Rep(v)may denote the exact function signature to be called by v,
while for languages which lack static typing such as Python2
it may be difficult to statically determine the possible targets of v, and hence Rep(v) may denote an expression that
captures a set of functions.
Example. In Fig. 3, the function call event at Line 5 will havea representation Rep(v) given by:
ESCPOSDriver::status(param self).receipt()

However, we could also choose to use one of the alternative representations in the following list (ordered from most
specific and precise to most general and least precise):base_driver.ThreadDriver::status(param self).receipt()status(param self).receipt()self.receipt()

We have determined these options by (i) falling back to thebase class of ESCPOSDriver, (ii) ignoring the class containing
the function call, and (iii) ignoring the function containing
the function call. Later, in Section §4.3, we will show how to(optionally) fall back to these alternative representations inorder to improve the results of learning.
When building the propagation graph, even if two events v
and v ′ have the same representation (i.e., Rep(v) = Rep(v ′)),
they will be encoded as separate events in V (i.e., v , v ′).
2 Recently introduced gradual typing for Python allows type annotations

for some variables, but is not yet widely used, so we do not rely on it.

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev
Alternatively, if the representation is the same, we could
collapse all events into one event (discussed in Section §6.4).
3.3

Candidate Events and Roles

To enable taint analysis of G, we must assign a role (i.e.,source, sanitizer or sink) to each event in V . As in [17], we assume the role of an event only depends on its representationand hence it suffices to know the role of that representation.
Consequently, when learning what the role of an event is,
we are in fact learning what the role of its representation is.
This is a slight simplification, e.g., a function may act as asource or a sink depending on its arguments, however, weleave this differentiation for future work.
We only insert an event v into V if v is a candidate for arole and we also exclude specific roles for some events. For
example, it is very rare that a field read acts as a sink andimpossible for it to act as a sanitizer. Hence, field read events
are only considered as candidates for sources. We elaborate
more on this point in Section §5.
3.4

Using the Propagation Graph

Once the propagation graph is built (we discuss how to do sofor Python in Section §5), we use this graph for two clients:
specification learning, discussed in Section §4, as well as
taint analysis for finding security issues (flows from sources
to sinks which do not pass through a sanitizer). We note thatfor these two clients to be practically effective and produce
useful results, it suffices for G to precisely capture the true
information flow between events in most cases (that is, G
need not be an over-approximation).

4

Learning Likely Taint Specifications

We now explain our method for learning roles of events in agiven propagation graph G. The key insight is to formulate
the specification inference problem as a linear optimization
task that can be solved in a scalable manner with efficientsolvers. The resulting scalability is important because it enables semi-supervised learning with very small amounts ofsupervision over a large dataset of programs. In turn, thisleads to learning better specifications than if one performs
inference over a single program only (as intuitively, the inference algorithm will then have access to only limited amountsof available information to learn from). We illustrate the benefits of our method experimentally in Section §7.
Learning over a Global Propagation Graph. In order tolearn over a dataset of programs, we first extract the propagation graph G i = (Vi , Ei ) from each program Pi in thedataset independently by using the method described in §3.
The union of thesegraphs forms a global propagaÐ individualÐtion graph G = ( Vi , Ei ) over which the learning will be
performed. Since the event sets Vi are pairwise disjoint (i.e.,Vi ∩ Vj = ∅ for all i , j), G does not contain any edges between events from different programs. However, even when

Scalable Taint Specification Inference with Big Code
src

src

src

san

san

sink

sink

sink

(a)

(b)

(c)

san

Figure 4. Visual illustration of our information flow constraints. Each graph states that if nodes (with solid outline) have the indicated roles, then there exists a node (withdashed outline) with the indicated role and information flow.
two events v and v ′ belong to different programs, they may
share the same representation (Rep(v) = Rep(v ′)). Our learning method then leverages information across projects bymapping events with the same representation to the same
variable (see §4.1).
We note that we explicitly allow events to have multiple
roles (e.g., source and sink), or no role at all, indicating theevent is irrelevant for security (e.g., the function capitalize).
Intuitive Information Flow Constraints. To perform learning, we first identify several constraints we believe should
hold between events and which a solution of the learning
task should try to enforce. An intuitive visualization of ourconstraints is provided in Fig. 4. Here, each column stands
for a separate constraint and captures an implication. We
note that our constraints are not the same as those of [17],however, they follow a similar high level idea of trying tocapture information flow assumptions.
Fig. 4a indicates that if the program uses a sanitizer withinformation flow into a sink, this is most likely to sanitize asource. Therefore, it requires that whenever an event v has
information flow into another event v ′, if we classify v asa sanitizer and v ′ as a sink, we must classify at least one of
the events vi with information flow into v as a source.
Analogously, Fig. 4b indicates that if the program uses
a sanitizer which receives information from a source, thepurpose of that sanitizer is to protect information flow intoa sink. Finally, Fig. 4c indicates that a program typicallysanitizes the information flowing into sinks, i.e., if there isinformation flow from a source to a sink, there must be a sanitizer between these two events. As illustrated in Fig. 4c, weonly require at least one path to be sanitized, not necessarily
every path. This avoids (i) quantifying over all paths and(ii) being overly strict in the case of spurious information
flow due to over-approximation.
Algorithmic Collection of Constraints. For a given propagation graph, we can easily identify all occurrences of theconstraints in Fig. 4 by a variant of breadth-first search (BFS).
For example, for Fig. 4a, we first identify all sanitizer candidates that flow into a sink candidate, by forward BFS starting

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USAfrom each sanitizer. For each such sanitizer v, we identify all
source candidates vi flowing into v. Constraint Fig. 4a thenstates that if v is a sanitizer and v ′ is a sink, then one of vi
must be a source.
4.1

Variables

For the representation n = Rep(v) of some event v ∈ V , weintroduce variables nsrc , n san and nsnk that encode likelihoodsof n being a source, sanitizer, or a sink (we discuss multiple possible representations soon). To avoid unnecessary
variables (and unnecessary constraints), we only introduce
variables which match potential roles of n. For example, if n
is a field read, we do not introduce the variable nsan . When
convenient, we refer to variables treated as sources as (n)src
and analogously for sanitizers and sinks.
Variable Constraints. To ensure that we can interpret eachvariable n role as a probability, we add constraints
0 ≤ nrole ≤ 1(4)for each introduced variable n and each role in {src, san, snk}.
Constraints for Known Variables. In our evaluation, welabel a small number of events by hand so to bootstrap learning (hence, our method is semi-supervised), accomplished byconstraining some variables to have appropriate roles. For
example, when we label an event as a sanitizer, but not asa source or a sink, we add the constraints nsrc = 0, nsan = 1,
and n snk = 0, where n is the representation of that event.
4.2

Linear Formulation of Information Flow

We now discuss how to encode our intuitive assumptions on
information flow from Fig. 4 as linear constraints. As we willsee, formulating the meaning of the intuitive assumptions as
linear constraints is crucial in order to ensure the resulting
constraint system is efficiently solvable (and thus, suitable
for learning from a large dataset of programs).
Linear Formulation of Fig. 4a. To express the assumptionin Fig. 4a as a linear constraint, we assert that for every eventv sanit that may act as a sanitizer and flows into a potential sink
event v sink , the sum of all source candidate scores flowing
into it must be at least the sum of scores of v sanit and v sink .
Example. Fig. 5 shows a small propagation graph for which
we demonstrate the constraint derived from the assumptionin Fig. 4a. Let v sanit be an event with representation n sanit =Rep(v sanit ), which may act as a sanitizer. Analogously, let v 1 ,v 2 , v 3 be events with representations n 1 , n 2 , n 3 , which may
act as sources, and v sink be an event with representation n sinkthat may act as a sink. Further, we assume that the unlabeled
event (top left) may not act as a source (hence we ignoreit). Then, to encode the assumption from Fig. 4a, we add thefollowing constraint(n sanit )san + (n sink )snk ≤ (n 1 )src + (n 2 )src + (n 3 )src + C(5)PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev

v3
v1

Linear Formulation of Fig. 4c. We derive the remaining
constraint analogously, leading tov2(n source )src + (n sink )snk ≤v sanitkÕ(ni )san + C

(7)

i=1

4.3
v sinkFigure 5. A propagation graph used to illustrate the linear
constraints we derive to formally capture Fig. 4a.

Selecting Event Representations with Backoff

In programming languages without static type information(in our case Python), it is typically difficult to determine
which possible targets an event v can resolve to, as discussed
earlier in §3.2. At that point, we had derived the representation Rep(v) of a particular function call event as
ESCPOSDriver::status(param self).receipt()where C is a fixed constant. If we set C = 1 and restrict
the values of variables (n 1 )src , (n 2 )src , (n 3 )src , (n sanit )san , and(n sink )snk to {0, 1}, then constraint (5) precisely captures theassumption from Fig. 4a: first, if (n sanit )san = (n sink )snk =1, then at least one of (n 1 )src , (n 2 )src and (n 3 )src must be 1.
Second, constraint (5) is trivially satisfied if at least one of(n sanit )san or (n sink )snk is 0.
Restricting values of variables to {0, 1} would result in a(generally NP-complete) integer linear program and induce
an unsatisfiable constraint system. Instead, we relax the values a variable can take to be in the interval [0, 1], as indicatedin constraint (4). Then, solving the resulting large constraint
system spanning many variables, becomes tractable. We caninterpret constraint (5) for the relaxed constraint system byobserving that if (n sanit )san and (n sink )snk are large, then atleast one of (n 1 )src , (n 2 )src , (n 3 )src must be large as well.
Empirically, we observed that for C = 1, most scores arequite close to 0, precluding a clear separation of sources,
sinks, and sanitizers. Therefore, we decreased C to 0.75,
which increases the effect of the constraints when variableson the left-hand side have scores below 1. For example, if(n sanit )san = (n sink )snk = 0.7, then C = 0.75 ensures thatÍk srcÍk srci=1 n i ≥ 0.65, whereas C = 1 only ensures i=1 n i ≥ 0.4.
To avoid overfitting, we only tested C = 0.75, concluding it
performs significantly better than C = 1.
Linear Formulation of Fig. 4b. To express the assumption
from Fig. 4b, consider a potential source event v source withrepresentation n source , a potential sanitizer event v sanit withrepresentation n sanit , and potential sink events v 1 , . . . , vk
with representations n 1 , . . . , nk , respectively. In addition, assume there is information flow from v src to v sanit and fromv sanit to every vi . Then, we encode Fig. 4b via(n source )src + (n sanit )san ≤

k
Õ
i=1

nisnk + C

(6)

The interpretation of constraint (6) is analogous to constraint (5).

However, using this entire expression (which captures
the exact location of receipt) may be too detailed and overly
specific to only a particular event, leading to a representation
Rep(v) that occurs infrequently. To address this issue, we
can fall back to less specific representations that occur more
frequently. For example, there may be many more calls toreceipt() from other subclasses of base_driver.ThreadDriverto receipt(), in which case it would make sense to fall backto the following representation
base_driver.ThreadDriver::status(param self).receipt().

However, falling back to a less specific representationinduces the risk of conflating Rep(v) with other, unrelated
occurrences of self.receipt() from unrelated events at otherlocations. As a trade-off between both approaches, that is,
working with a long but infrequent representation vs short
but frequent representation, we use a backoff approach thattakes into account all possible suffixes (until we reach a frequent suffix). This is a commonly used approach in machinelearning, see e.g., [3], which we adapt to our setting.
Selecting of Backoff Variables. Concretely, let (n 1 , . . . , nk )be all potential representations of an event v, ordered frommost to least specific. If some representations {n 1 , . . . , nl } occur infrequently, we will ignore them as these do not provide
much information (in our evaluation, the cutoff thresholdis 5 occurrences). We denote the remaining set of all possible backoff options for v by Reps(v) = {nl +1 , . . . , nk }. If nopotential representation of v occurs frequently enough (i.e.,
if Reps(v) = ∅), then we also ignore v and all constraints
involving v, as we cannot hope to learn much about v.
Overall, instead of creating only 3 variables nsrc , n san , andsnk
n , we create 3 · |Reps(v)| variables for every possible backoff option(nr )src ∀r ∈ Reps(v)(nr )san ∀r ∈ Reps(v)(nr )snk ∀r ∈ Reps(v)Variable Constraints. To interpret values of these variables as probabilities (cp. §4.1), we again add the constraint
0 ≤ (nr )role ≤ 1 ∀r ∈ Reps(v), role ∈ {src, san, snk} (8)Scalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

Information Flow Constraints. Finally, for every constraint
we added in §4.2, we introduce a constraint that replaces
each variable (n)role by an average of its backoff options
1|Reps(v)|
4.4

Õ

(nr )

role

r ∈Reps(v)Relaxing and Solving the Constraint System

We now discuss how to solve the resulting constraint system derived by applying backoff (§4.3) to variables and constraints introduced in §4.1 and §4.2, respectively.
The constraint system C consists of variable constraints
C var as in constraint (8), constraints for known variables
C known as in §4.1 and information flow constraints C flow asin §4.2. For all constraints, we use the version which includes
backoff (§4.3), but for C known , we only annotate fully qualified
names, i.e., the longest possible backoff option for each event.
Relaxing the Constraints. Because programs in our training dataset might not always respect our intuitive constraints
on information flow, the constraint system is generally notsatisfiable. For example, the assumption from Fig. 4a might
be violated by a sanitizer that does not have any sources
flowing into it, which in turn would violate constraint (5)and hence also its version with backoff.
This forces us to relax the constraints and replace theentire constraint system with a more robust one, which takes
into account possible errors. Intuitively, we treat C var as hardconstraints but relax C flow to be soft constraints, and aim tominimize their violation.
More precisely, we transform each constraint in C flow of
the form Li ≤ Ri into a relaxed constraint Li ≤ Ri +εi , where
Li (resp. Ri ) is the left-hand (resp. right-hand) side of theoriginal constraint, and εi ≥ 0 quantifies the violation of theoriginal constraint.
Rewriting this constraint yields Li − Ri ≤ εi . Hence, minimizing the violation of theÍ original constraints (measured by
the l 1 -norm defined as i |ϵi |) means solving the following
optimization problem

min

M
Õ

max(Li − Ri , 0) + λ ·Õ(nr )src + (nr )san + (nr )snk



nr

i=1

(9)
subject to 0 ≤ (nr )role ≤ 1
C

known

∀nr and(10)(11)

Here, nr ranges over all representations and their backoff
versions, and M denotes the total number of constraints
in C flow . In addition, λ is a regularization constant (in ourevaluation, we use λ = 0.1) that penalizes solutions thatclassify many nodes as sources, sanitizers or sinks. To avoid
overfitting, we tried only a few values λ ∈ {0.1, 1, 0.01}, ofwhich λ = 0.1 performed best. Empirically, we observedthat decreasing λ by a factor of 10 increases the number ofinferred specifications by a factor of around 2.
Solving the Relaxed Constraint System. Solving the resulting optimization problem (9) efficiently can be done inmany different ways. We opted for using Adam Optimizer[15] from TensorFlow [1], which optimizes (9) incrementallyusing projected gradient descent. Here, to enforce the hardconstraints of type (10), we project the variables n role to theinterval [0, 1] after each iteration.

5

Building the Propagation Graph for
PythonTo build the propagation graph G = (V , E) of a Python program P, we first determine the set of relevant events V andtheir candidate roles, and then establish the information flow
between these events.
5.1

Events

The events in our propagation graph can be either function
calls, object reads, or formal arguments of function definitions. Examples of object reads include attribute loads (e.g.,
obj.field), indexing into dictionaries, lists, and tuples (e.g.,d[k]), and reads of method parameters (e.g., function def f(a)has potential source a). As mentioned earlier, the role of an
object read event can only be a source, but not a sanitizer ora sink. Similarly, formal arguments of function definitions
are considered only as sources. Finally, function calls can beeither sources, sinks or sanitizers. We do not consider stores
into variables because they rarely act as sinks and cannot
act as a source or a sanitizer.
5.2

Capturing Information Flow

We next discuss how we capture information flow.
Function Calls. We assume a function call induces information flow from its arguments to its return value, an overapproximation of the true information flow, e.g., the Python
built-in function id(o) returns a unique value for object o,and hence does not propagate information about o itself.
Points-to Analysis. Points-to analysis (also known as alias
analysis) determines which variables may point to the same
object. In our system we used an Andersen-style points-toalgorithm [26]. Here, for each pair of events a, b s.t. a ∈PointsTo(b) we add an edge b → a. Our points-to algorithm
is fully flow-sensitive, field-sensitive and context-sensitive
up to a bound of 8 method calls, the default setting of thelibrary we used. For simplicity, we treat calls to functions
with an unknown body as allocation sites and ignore loops(i.e., we treat loops as having just a single iteration). As aconsequence, our propagation graph does not contain cycles(in principle, our method supports cycles).
We note that our points-to analysis both over- and underapproximates the true points-to relation but is sufficiently

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev
for specific nodes, while our constraints only enforce theexistence of nodes with a particular role.

src
san

san

src

H

sink

H

sink

H

san

H

H

src

H

sink

(a)

(b)

(c)

(d)

Figure 6. Visual illustration of Merlin’s information flow
constraints. Each graph states that if solid nodes have theindicated roles, the dotted node should have the indicatedrole (if underlined) or not have it (if crossed out).

precise for our application of learning role specificationsof events and the subsequent taint analysis that uses these
specifications to discover security bugs.
Data Structures. Python has several built-in collections(i.e., data structures), including lists, dictionaries, tuples, andsets. We treat these the same as standard function calls, e.g.,when defining a new list (e.g., l=[a,b,c]), we record information flow from any of its entries to the whole list.
Local Symbol Table. The function locals() returns a dictionary containing all of the local variables in the current scope.
We model this behavior by adding information flow from all
local variables to locals() calls.
Inlining Methods. Finally, to enable a more precise static
analysis, we inline methods whose body can be staticallydetermined (i.e., methods defined in the same file as the caller
and not subject to multiple dispatching). For simplicity, we
treat imported methods as having an unknown body.

6.2

Representation of Events. As Merlin targets C#, it does
not address how to deal with multiple possible targets ofa given event. Instead, it represents events by their target,
identified using the static type system. For dynamically typed
languages, this is hard, as discussed in §3.2. Thus, when
adapting Merlin to handle Python programs, we use themost specific representation (e.g., the one discussed earlier
for the example in §3.2).
Identification of Candidates. To identify which nodes are
candidates for a role, Merlin heavily relies on the type system of C#. For example, it considers only functions that takea string as input as candidates for sources. Applying thisheuristic to languages without static type information is
not possible which means we can exclude only very few
candidates from certain roles. For example, we view all function calls as candidates for all roles. As a consequence, in
our setting, we obtain significantly more candidates than
Merlin does in C#, but typically the same amount of information about their interaction. This increases the difficulty of
specification learning because we now have to classify morecandidates using roughly the same amount of information.
6.3

6

Adapting a Baseline Method

We now discuss Merlin’s method to taint specification inference in C# [17]. Merlin’s method differs from our method
across several key technical dimensions: (i) the formulationof the constraints, (ii) how relevant events and candidate
roles are identified, (iii) the formulation of the optimization
problem, and (iv) the granularity of the propagation graph.
6.1

Merlin’s Constraints

We summarize the information flow constraints of Merlin in
Fig. 6 (their presentation in [17] is different, but equivalent).
Fig. 6a illustrates that for every flow across three events
where the first is a source and the third is a sink, the second
is likely to be a sanitizer. Fig. 6b shows that whenever there isa flow from a sanitizer to another event, the latter is unlikely
to be a sanitizer. Fig. 6c and Fig. 6d capture an analogous
constraint for sources and sinks.
In contrast to our constraints, Merlin’s constraints cannot
be easily encoded as linear constraints. In addition, Merlin’s constraints are more restrictive: they constrain the role

Identifying Events and Candidate Roles

Merlin relies on static typing information when identifying events and candidate roles. Since this is impossible inprogramming languages without strong static typing, we
adapted Merlin to handle such languages.

Formulating the Optimization Task

We now discuss how Merlin uses its information flow constraints to state an optimization problem on factor graphs. As
we demonstrate in §7.4, in contrast to our approach based onlinear constraints, this formulation does not scale well andis not suitable for learning from a large dataset of programs.
Factor Graphs. Merlin expresses its information flow constraints as a factor graph, a well-known graphical model [16]suitable for performing structured prediction.
Given the propagation graph G of a program, Merlin scores
joint assignments of roles to events. To this end, it introduces
a score for every occurrence of a constraint from Fig. 6 in G.
For example, based on the constraint in Fig. 4c, Merlin investigates every flow through three events which are candidates
for being sources, sanitizers, and sinks, respectively. For eachsuch flow, Merlin checks if the joint assignment respects theconstraint: if the first and third events are classified as sourceand sink, respectively, the second event should be classified
as a sanitizer. If so, it will provide a high score, and if not, alow score.

Scalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
1 def f():2

x = src()3

y = san(x)

src
src

san

4 def g():Figure 7. Illustrating vertex contraction: merging graynodes.
Then, the total score of an assignment is the product of
all scoresÖp(x 1 , . . . , x N ) =fs (x s )(12)sHere, each x i ∈ {0, 1} encodes if a given event assumes
a given role. Moreover, each fs is a factor evaluating thescore for an occurrence of a constraint in G, x s is the set ofvariables involved in this factor, and fs (x s ) is the score offactor fs for assignment x s .
Prior on Known Candidates. For candidates that are labeled by hand, Merlin selects a hard prior, stating that theymust act as their respective role. We can interpret this as aparticular factor for every hand-labeled candidate, definedby(
1 candidate has the correct rolefs (x s ) =0 otherwise
Prior on Candidates. In addition to scores for joint assignments, Merlin introduces prior probabilities for every potential role of every candidate node. The probability a source(resp. sink) candidate acts as a source (resp. sink) is 50%. The
probability a sanitizer candidate acts as a sanitizer is intuitively given by checking which fraction of paths that go
through it start from a source and end in a sink. These priors
can be seen as additional factors, meaning that Eq. (12) canaccurately describe the joint probability of all factors.
Probabilistic Inference. Using prior probabilities and thescores for joint assignments, Merlin determines the marginal
probability of each candidate having a particular role:Õ ÕÕ Õ
pi (x i ) =······p(x 1 , . . . , x N )(13)x1

x i −1 x i +1

xN

While there is a wide variety of techniques that solve marginal inference in factor graphs (e.g., the sum-product algorithm [31]), these are significantly less scalable than approaches for solving linear constraints (which our approachuses). To solve Eq. (13), Merlin uses Infer.NET [19].
6.4

Propagation Graph Granularity

In contrast to our approach, Merlin conflates events targetingthe same AST node (i.e., events with the same representation).
Because our propagation graph is more informative than
Merlin’s, we can use it to construct the conflated graph by

5

x = 1

6

y = san(x)7sink(y)

san
san

sink
sink

(b) Transition from uncollapsed (left) to(a) Two functions prop- collapsed (right) propagation graph.
agating information.

Figure 8. Collapsed graphs are unsuitable for taint analysis.

applying vertex contraction to conflate all events with thesame representation, illustrated in Fig. 7. We refer to theoriginal graph as uncollapsed, and to Merlin’s propagationgraph as collapsed.
The collapsed graph is not suitable for taint analysis as it
combines unrelated events into a single graph, illustrated inFig. 8: here the collapsed graph contains information flowfrom the source to the sink even though this is not the casein the original program. We note that while the collapsed
graph is not suitable for taint analysis, it can still be used forspecification learning.
While Merlin’s original presentation [17] assumes collapsed graphs, it is also directly applicable to uncollapsed
graphs. Therefore, in our evaluation, we run Merlin using
both the collapsed and uncollapsed propagation graphs.

7

Experimental Evaluation

We now present an extensive experimental evaluation of
Seldon3 , and demonstrate its practical effectiveness in bothlearning useful taint specifications from a large dataset of
Python programs and finding new security bugs based onthese learned specifications.
7.1

Implementation and Analysis Flow

We implemented Seldon in an end-to-end production quality
tool which (i) parses and analyzes a large number of Python
repositories, (ii) extracts the propagation graphs from programs as outlined in Section §5, (iii) builds the resulting linear
constraint system as outlined in Section §4, and (iv) solves
the optimization problem subject to the constraint system.
Once the optimization problem is solved, we obtain confidence scores for every possible backoff option of every event
being a source, sink, or sanitizer. To determine the role ofa given event, we loop over all its possible backoff options,sorted from most to least specific. For the i th option (0-based),
we select a given role if 0.8i · (ni )role ≥ t, for a given threshold t (discussed later). It this does not happen for any role orbackoff option, the event has no role. Overall, this amounts
3 Seldon is freely available at https://www.deepcode.ai/

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
Table 1. Statistics on the applications in our evaluation.
# Candidates
Average # backoff options per event# Constraints# Source files

210 864
1,73
504 982
44 250V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev
v src source :∃v sink .∃P .(v src , v sink , P) vulnerable
v san sanitizer : ∃v src .∃v sink .∃P .(v src , v sink , P) vulnerableand (v src , v san , v sink , P) sanitizedv sink sink :∃v src .∃P .(v src , v sink , P) vulnerable
Figure 9. Formal definitions for sources, sanitizers and sinks.

to backing off to less and less specific representations while
exponentially decreasing the score.
We also built a static taint analyzer that consumes the
specification learned by Seldon and checks for security vulnerabilities in web applications: it reports an error if it finds
an unsanitized information flow from a source to a sink.
7.2

DatasetIn this section, we describe the programs and hand-labeled
specifications used for our evaluation.
Applications. We obtained various Python applications from
GitHub (https://github.com/), focusing on popular ones (identified by number of stars). While Seldon is generally applicable, we focused our attention on web applications, a domain
where practical security concerns are particularly relevant.
To this end, we only included applications which contain thestring django, werkzeug or flask in their code, as these are themost popular frameworks used for Python web development.
Tab. 1 provides statistics on these applications, including thenumber of candidates for sources, sanitizers, and sinks, theaverage number of backoff options per event, the number of
constraints induced by the applications, and the number of
Python files.
Seed Hand-labeled Specifications. We manually annotatedsome events, resulting in 106 events classified as exclusively
sources (28 events), exclusively sanitizers (30 events), andexclusively sinks (48 events). To avoid issues with eventswith multiple possible representations (see Section §4.3), weonly classified events whose representations are fully qualified, such as werkzeug.utils.secure_filename(). We avoided
labeling application-specific events or other common coding
patterns, ensuring that we can handle new programs without
needing additional manual effort.
In general, manually annotating events can be expensive.
However, we focused our attention on events with a clear
role (e.g., request.GET.get()), identified by investigating common security vulnerabilities (as taken from OWASP Top 10[22]). This approach allowed us to create our seed specification within a few hours, labeling most events involved inwell-known taint-related security vulnerabilities. Labelingmore events is significantly harder as it requires manually
identifying and investigating less common vulnerabilities.
We also blacklisted some built-in Python functions andcommonly used library functions from taking on any role, byspecifying 192 patterns, including, e.g., *__name__*, *.all(),or *tensorflow*. This blacklist contains patterns for commonly used Python code patterns. The seed specification is
given in App. B.
7.3

Manually Inspecting Learned Specifications

For both Seldon and our baseline Merlin, we investigatedthe precision of the learned specifications.
Ground Truth. To determine the ground truth, we definedsources, sinks, and sanitizers via a notion of vulnerable information flow, in a given program. Concretely, we say a triple(v, v ′, P) is vulnerable, if an attacker can inject malicious
data into v, which then flows into v ′, which in turn triggers
a vulnerability (e.g., an SQL injection). We note that in thiscase, we ignore sanitizers on the path from v to v ′, because
we are only interested in determining if the investigatedinformation flow is potentially dangerous. Conversely, wedefine a quadruple (v, v san , v ′, P) as sanitized, if sanitizer v sansafely sanitizes the information flow from v to v ′ in P.
The formal definitions for the considered roles are shownin Fig. 9. Here, quantifiers expand to programs and eventsfrom our dataset, ensuring we only report sources, sinks,
and sanitizers that may lead to vulnerabilities in real-world
programs.
Finding Vulnerable Flows. We note that determining if a
program and an event with the specified properties exist
would generally require investigating all programs in ourdataset. Because this is practically infeasible, we instead use
taint analysis (Section §3.4) to determine candidate programs
to investigate. For example, to evaluate if a given event n is asource, we run taint analysis on all programs to identify allsinks that are reachable from this source and contained inour specification. Then, we only investigate the top 5 sinks
with the highest scores. If none of them exhibits a vulnerable
flow, we (conservatively) report n as a false-positive.
Fairness of Comparison. To ensure fairness when comparing Merlin to Seldon, we evaluate both specifications inexactly the same way, using the whole dataset and the candidates inferred by our approach to identify candidates forvulnerable programs. We note that the alternative of using
only the dataset and specifications used and obtained by
Merlin would be unfair to Merlin, as it only scales to a single
application, and thus predicts significantly less specification
candidates.

Scalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

Table 2. Statistics on specification learning with Merlin.
Repository
Number of Lines
Flask API
2 128
Flask API
2 128
Flask-Admin
23 103
Flask-Admin
23 103Graph type Candidates (src/san/sink)
Collapsed
376/376/68
Uncollapsed
378/378/66
Collapsed
3337/3337/422
Uncollapsed
3369/3369/380

Table 3. Results for Merlin on the Flask API, only selectingroles with a confidence of 95%.

Role
Sources
Sanitizers
Sinks
Any

7.4

Collapsed Graph
Number Precision
18
33%
5
20%
3
0%
26
27%

Uncollapsed Graph
Number Precision
9
22%
1
100%
3
0%
13
23%

Factors
1034
470
22740
7204

Inference Time
2min
3min
> 10h
> 10h

Table 4. Results for Merlin on the Flask API, only selecting
top 5 predictions.
Collapsed Graph
Role
Number Precision
Sources
540%
Sanitizers
5
20%
Sinks
5
0%
Any
15
20%

Uncollapsed Graph
Number Precision
5
20%
5
40%
5
0%
15
20%

Baseline Comparison

To evaluate Merlin [17] we used the adaptation in Section §6
and the same propagation graph, seed specifications, and setof candidates as for the evaluation of our approach. We specified the factor graph derived from the propagation graphin Infer.NET [19]. As Merlin originally specifies a collapsed
propagation graph, while our approach specifies an uncollapsed one, we evaluated Merlin on both cases.
Because the employed inference method is not specified
in [17], we used the default method of Expectation Propagation (EP), including belief propagation as a special case. We
also tried Gibbs sampling when EP timed out. We note thatthe third available inference method, Variational Message
Passing, could not handle the encoded factor graph.
We ran all experiments for Merlin on a 512GB RAM, 32
core machine at 2.13GHz, running Ubuntu 16.04.3 LTS.
Scalability. Merlin was unable to handle the large amountof data we use for our learning approach. This is not entirely
surprising, as it relies on probabilistic inference, a task thatis #P-hard when exact results are desired [6], and NP-hardeven for approximate results [7].
We ran Merlin on two applications, summarized in Tab. 2:
Flask API [10], which is smaller and where inference succeeds in minutes, and the larger Flask-Admin [9], whereinference timed out after 10h. We also tried Gibbs Samplingwith only 20 iterations, which also timed out after 10h. In
contrast, our approach handles Flask-Admin in < 20 seconds(we did not evaluate the precision here as we scale to thefull dataset). As a consequence, running Merlin on the wholedataset used for the evaluation of our approach is infeasible.
When Merlin did not time out (i.e., for Flask API), we investigated its precision using the method from Section §7.3.
Tab. 3 shows the results when selecting using a thresholdof 95%, i.e., only picking roles for which Merlin is highly

confident. The results indicate Merlin is often overly confident, but not very precise. This is the case regardless ofwhether the graph is collapsed or not. The precision results
are analogous when examining its top 5 predictions (Tab. 4).
Because Merlin predicted only few specifications in bothexperiments, we also investigated the effect of increasing thenumber of predicted specifications. Concretely, we computed
Merlin’s estimated precision with a threshold of 50% forsinks and sanitizers (yielding less than 50 specifications) andfor the top 50 sources, corresponding to a threshold of 50%(54%) for the collapsed (uncollapsed) graph. For the collapsed(uncollapsed) graph, the precision is 18% (12%) for sources,
2.7% (2.22%) for sinks, and 8.33% (9.09%) for sanitizers.
Based on these experiments, we concluded that Merlin
cannot reach high precision in our setting.
7.5

Evaluation Results for Seldon

To evaluate Seldon, we investigated the following questions:• Q1: How scalable is our approach in solving its constraint system?
• Q2: How precise is the learned specification, i.e., howmany identified roles are false positives?
• Q3: How many sources, sanitizers, and sinks do we
detect?
• Q4: How useful are learned specifications for discovering vulnerabilities?
• Q5: Does using a large dataset improve the inferred
specifications?
• Q6: How does the seed specification affect precision?
• Q7: What is the real-world value of the security vulnerabilities reported by Seldon?
Experiments were done on a 28 core Intel(R) Xeon(R) CPU
E5-2690 v4, 512Gb RAM machine running Ubuntu 16.04.3.

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev

Table 5. Count and estimated precision of candidates predicted by Seldon.
Role# Predicted / # Candidates
Sources
4 384 / 210 864
Sanitizers
1 646 / 210 864
Sinks
866 / 210 864
Any
6 896 / 210 864

Fraction of predicted candidates
2.08%
0.78%
0.41%
3.27%

Table 6. Results for bug-finding using the set of sources,
sanitizers and sinks in initial specification versus the inferred
specification tested on 25 random reported specifications

15,000Time (s)Precision (Estimate)
72.0%
58.0%
56.0%
66.6%

10,000
5,000

1

2

3

4

5

6

7

8

Number of files (×105 )Figure 10. Seldon inference times (in seconds) as a functionof the number of analyzed files.

Q1: Scalability. We tested the scalability of Seldon by running it on datasets of different sizes. The measured inference
times are shown in Fig. 10, showing Seldon scales linearly inthe number of analyzed files (the graph looks similar when
we consider the size of the constraint system instead of thenumber files). For the largest dataset of 800, 000 files (including non-web applications), Seldon finished in < 5 hours,
indicating it is scalable enough to learn specifications fromreal-world repositories.
Q2: Precision. We have evaluated the precision of predictedsources, sinks, and sanitizers, i.e., which fraction of candidates that are predicted to have a particular role actually
have the predicted role. To perform this evaluation, we tooka random sample of 50 sources, sanitizers, and sinks withscores above 0.1. To determine this threshold for sources(analogously for sinks and sanitizers), we sorted events by
their score for being a source and picked the threshold thatstrikes a balance between number of predicted specifications(i.e., recall) and precision. Concretely, we tolerate a slightly
higher false positive rate for the opportunity to discover new
unknown security vulnerabilities.
We manually determined the ground truth for these events,
leading to a precision of 72.0% (sources), 56.0% (sinks) and
58.0% (sanitizers), respectively, and an overall precision of
66.6% (see also Tab. 5). We have repeated this experiment
for more samples (manually checking 200 sources, sanitizers,
and sinks, respectively), yielding an overall precision of 65.5%(this corresponds to a deviation of 1.1%). This indicates thatour precision estimate is fairly stable.
In Fig. 11, we provide more details on the score and precision of the random sample we evaluated. First, note there
are only a few samples with score around 1.0, meaning the
optimization was completely confident in its assignment of a

ReasonTrue vulnerabilities
Vulnerable flow, but no bug
Incorrect sink
Incorrect source
Incorrect source and sink
Missing sanitizer
Flows into wrong parameter

Seed spec
24%
28%
0%
0%
0%
40%
8%

Inferred spec
28%
12%
24%
8%
8%
8%
12%

role for relatively few events. For most samples, the score isaround 0.5, hence the model believes the event likely plays
the role, but is uncertain. Fig. 11 also shows how confidencetransforms into precision. For every precision data point, weshow the average ratio of true positive labels according to theground truth for the cumulative sample including all samples
up to a position. This shows how we can adjust the thresholdfor selecting sources, sinks and sanitizers to achieve desired
precision levels. Note, however, that non-zero confidence
value for a role is already an indicator for the event’s role,
as most events (discussed in Q3) have score 0.
Our results indicate that Seldon successfully identifies
many sources, sanitizers, and sinks with consistently highprecision. App. A shows the evaluated sample of events.
Q3: Number of Sources, Sanitizers, and Sinks. With theabove threshold, Seldon identified numerous sources, sanitizers, and sinks, shown in Tab. 5. Identifying a similarly
large set by hand would be difficult as only a small fractionof all candidates (3.27%) have some role. Even inspecting
all inferred specifications manually is significantly cheaper
than inspecting all candidates, by a factor of about 30.
Our results are in line with those in [17], which identified
3.8% of all nodes in its propagation graph as sources, sanitizers, or sinks (381 out of 10038). However, in their setting,the learning problem was significantly easier, as C# allows
filtering candidates by type, thus removing 75% of all nodes
in the propagation graph.
Q4: Number of Vulnerabilities. To evaluate the usefulness
of inferred specifications for detecting security vulnerabilities in real web applications, we ran taint analysis on ourcomplete GitHub dataset (described in §7.2) using both theScalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

1

1

1

0.5

0.5

0.5

0

20

40

Sample of candidate sources

0

20

40

Score
Precision0

Sample of candidate sanitizers

20

40

Sample of candidate sinks

Figure 11. Plot of 50 candidate samples for sources, sanitizers and sinks. The samples are sorted according to their predictedscore for the role. Precision for all samples up to a given sample shows how higher score correlates with precision.
Table 7. Total number of reports and estimated numberof vulnerabilities in all the data based on evaluating true
positive rate on the sample from Tab. 6
ReasonNumber of reports
Number of projects affected
Estimated vulnerabilities

Seed spec
662
192
159

Inferred spec
21318
2409
5969

initial seed specifications and the final inferred specifications.
In each case we manually inspected 25 randomly sampled
vulnerability reports. The comparison is shown in Tab. 6.
In terms of precision as estimated on the 25 samples, both
approaches discover similar ratio of true vulnerable flows.
However, not all of these flows are exploitable due to othersettings in the evaluated applications. For example, a CrossSite Scripting attack is not possible if the Content-Type httpheader is set to text/plain and not text/html. Anotherobservation is that the seed specification misses a numberof sanitizers and produces false positives for sanitized flows.
In contrast, the inferred specification can contain incorrectsources and sinks, but has increased coverage for sanitizers.
In terms of recall, the results are summarized in Tab. 7.
The seed specification only produces a small number of totalreports (662), but these reports still contain a large numberof false positives. The inferred specification significantly
increases the number of reports to 21318 in 2409 projects andwe estimate the total number of true security vulnerabilities
detected by Seldon to be close to 6000.
Based on this sample, we conclude that the learned specifications increase the estimated number of true vulnerabilities
in our dataset by an order of magnitude.
Q5: Impact of Large Dataset. Next, we evaluated the impact of learning on a big dataset as opposed to on a single
project. To this end, we randomly selected 3 projects fromthe complete corpus (described in Section §7.2) and ran theend-to-end process for each of them separately, always using the same seed specifications. To compare the results tothe complete specifications (obtained by learning on the full
dataset), we projected the complete specifications to eachof the three projects (i.e., we ignored all specifications notoccurring in the considered project). For each of the threeprojects, we then compared the specifications obtained fromtraining only on that project vs training on all projects.
The experiment shows the precision increased from 45%(on average, when using the individual specifications) to 65%(on average, when using the projections of complete specifications). In addition to increasing precision, the complete
specification inferred 18 new, true roles not predicted by theindividual specifications. We thus conclude that cross-project
learning is beneficial.
Q6: Impact of Seed Specification. We also evaluated Seldon’s precision for half the seed specification (considering
only odd line numbers in App. B). This significantly reduces
precision, by 14 percentage-points. Thus, we believe ourseed specification strikes a good balance between manual
effort and precision. We note that in the extreme case of anempty seed specification, Seldon will predict 0 specifications,because picking 0 for all variables is a trivial solution to its
constraint system.
Q7: Reporting Bugs. Finally, to ensure reported vulnerabilities have value in real-world projects, we inspected several
reports with highly scored sources and sinks, built proof-ofconcept exploits and reported 49 severe vulnerabilities in 17
projects: 25 Cross-Site Scripting, 18 SQL Injections, 3 Path
Traversal, 2 Command Injections, and 1 Code Injection. We
provide a full list of all reported bugs in App. C. We notethat only 3 of these could be discovered using only the seedspecification, and that some of the reported issues can affecta large number of users.

8

Related WorkIn this section, we describe the work most related to ours.
Specification Mining. Multiple works have proposed learning specifications related to information flow. The work mostrelated to ours is Merlin [17], which we have discussed indetail (§6) and also investigated in our evaluation (§7.4).
SuSi [24] trains a support vector machine (SVM) classifier to identify privacy specifications of Android APIs. In
contrast to our work, SuSi is fully supervised and heavily
relies on the similarity of type signatures of methods withsimilar role. While effective for Android, this method is lessapplicable to the diverse and dynamic Python codebases. In
general, Python is more difficult to analyze than staticallyPLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
typed languages such as Java and C# (targeted by SuSi andMerlin, respectively). Concretely, in contrast to Java and C#,
in Python one cannot identify a unique target of an event,filter source, sink, or sanitizer candidates by their type, orleverage statically precise information flow analysis.
Shar et al. [25] predict sanitizers using backward program
slicing from a known set of sinks and dynamically computes
a number of features for each function (e.g., testing how functions react on dot-dot-slash to sanitize path traversal [21]).
Based on this information, their tool predicts if an information flow is sanitized (however it still needs manuallyprovided sources and sinks). Modelgen [4] learns information flow of Android privacy APIs based on dynamic analysis
obtained from a large test case set and mined on invocation
subtraces. In contrast, our approach is fully static and also
works on a range of APIs not covered by test suites.
Taint Analysis. Numerous works have addressed static taintanalysis in Android, including SCanDroid [11], ScanDal [14],LeakMiner [30], FlowDroid [2] and DroidSafe [12]. Taint
analysis has also been investigated for server-side web application [27], for client-side JavaScript [28] or for C [29].
Other works have applied dynamic taint analysis for arange of applications such as TaintDroid [8], DTA++ [13],Python taint for Erasure [5] and TaintCheck for Valgrind [20].
All these static and dynamic approaches require a specification of sources, sanitizers, and sinks, based on which they
perform taint analysis. Therefore, the work on these tools
is complementary to our approach: Better specifications improve these tools, while better information flow analysis may
improve our specification learning.

9

Conclusion and Discussion

We presented Seldon, a new approach for learning taint specifications. Its key idea is to phrase the task of inferring thespecification as a linear optimization, leading to scalable inference and enabling simultaneous learning of specifications
over a large dataset of programs.
Clearly, Seldon is subject to the usual limitations of taintanalysis: it can only help to detect vulnerabilities based on information flow and does not address, e.g., buffer overflows or
insecure configurations. In addition, Seldon relies on a highquality dataset and on a correctly annotated (but small) seedspecification. For example, when the dataset often misses
sanitization, the constraint from Fig. 4c forces the variables
to (i) omit the specification of the source or sink, (ii) incorrectly label a non-sanitizer as a sanitizer, or (iii) accept apenalty for this constraint.
In our evaluation, we showed that Seldon can infer thousands of taint specifications for Python programs with highestimated precision. Manual examination of the reports produced by our taint analyzer (which uses the inferred specifications) indicates the reports contain true security violations,some of which we reported to the maintainers of the projects.

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev

Acknowledgements
The research leading to these results was partially supported
by an ERC Starting Grant 680358.

References[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng
Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu
Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey
Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser,
Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga,
Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon
Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals,
Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning
on Heterogeneous Systems. https://www.tensorflow.org/ Software
available from tensorflow.org.
[2] Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick
McDaniel. 2014. FlowDroid: Precise Context, Flow, Field, Objectsensitive and Lifecycle-aware Taint Analysis for Android Apps. SIGPLAN Not. 49, 6 (June 2014), 259–269. https://doi.org/10.1145/2666356.
2594299[3] Thorsten Brants, Ashok C. Popat, Peng Xu, Franz J. Och, Jeffrey Dean,
and Google Inc. 2007. Large language models in machine translation.
In In EMNLP. 858–867.
[4] Lazaro Clapp, Saswat Anand, and Alex Aiken. 2015. Modelgen: Mining
Explicit Information Flow Specifications from Concrete Executions. In
Proceedings of the 2015 International Symposium on Software Testingand Analysis (ISSTA 2015). ACM, New York, NY, USA, 129–140. https://doi.org/10.1145/2771783.2771810[5] Juan José Conti and Alejandro Russo. 2012. A Taint Mode forPython via a Library. In Proceedings of the 15th Nordic Conferenceon Information Security Technology for Applications (NordSec’10).
Springer-Verlag, Berlin, Heidelberg, 210–222. https://doi.org/10.1007/
978-3-642-27937-9_15[6] Gregory F. Cooper. 1990. The computational complexity of probabilistic inference using bayesian belief networks. Artificial Intelligence42, 2-3 (March 1990), 393–405. https://doi.org/10.1016/0004-3702(90)90060-D[7] Paul Dagum and Michael Luby. 1993. Approximating probabilistic
inference in Bayesian belief networks is NP-hard. Artificial Intelligence60, 1 (March 1993), 141–153. https://doi.org/10.1016/0004-3702(93)90036-B[8] William Enck, Peter Gilbert, Seungyeop Han, Vasant Tendulkar, ByungGon Chun, Landon P. Cox, Jaeyeon Jung, Patrick McDaniel, andAnmol N. Sheth. 2014. TaintDroid: An Information-Flow Tracking
System for Realtime Privacy Monitoring on Smartphones. ACM
Transactions on Computer Systems 32, 2 (June 2014), 1–29. https://doi.org/10.1145/2619091[9] Flask Admin. [n. d.]. https://github.com/flask-admin/flask-admin/.
[10] Flask API. [n. d.]. www.flaskapi.org.
[11] Adam Fuchs, Avik Chaudhuri, and Jeffrey S Foster. 2009. SCanDroid:
Automated security certification of Android applications. (01 2009).
[12] Michael I. Gordon, Deokhwan Kim, Jeff Perkins, Limei Gilham, Nguyen
Nguyen, and Martin Rinard. 2015. Information-Flow Analysis of Android Applications in DroidSafe. In Proceedings 2015 Network and Distributed System Security Symposium. Internet Society, San Diego, CA.
https://doi.org/10.14722/ndss.2015.23089[13] Min Gyung Kang, Stephen McCamant, Pongsin Poosankam, andDawn Xiaodong Song. 2011. DTA++: Dynamic Taint Analysis withTargeted Control-Flow Propagation. In NDSS.

Scalable Taint Specification Inference with Big Code[14] Jinyung Kim, Yongho Yoon, Kwangkeun Yi, and Junbum Shin. 2018.
SCANDAL: Static Analyzer for Detecting Privacy Leaks in Android
Applications. (11 2018).
[15] Diederik P. Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Optimization. CoRR abs/1412.6980 (2014). arXiv:1412.6980
http://arxiv.org/abs/1412.6980[16] Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine
Learning. The MIT Press.
[17] Benjamin Livshits, Aditya V. Nori, Sriram K. Rajamani, and Anindya
Banerjee. 2009. Merlin: Specification Inference for Explicit Information
Flow Problems. SIGPLAN Not. 44, 6 (June 2009), 75–86. https://doi.
org/10.1145/1543135.1542485[18] V. Benjamin Livshits and Monica S. Lam. 2005. Finding Security
Vulnerabilities in Java Applications with Static Analysis. In Proceedingsof the 14th Conference on USENIX Security Symposium - Volume 14(SSYM’05). USENIX Association, Berkeley, CA, USA, 18–18. http://dl.acm.org/citation.cfm?id=1251398.1251416[19] T. Minka, J.M. Winn, J.P. Guiver, Y. Zaykov, D. Fabian, and J. Bronskill. 2018. /Infer.NET 0.3.
Microsoft Research Cambridge.
http://dotnet.github.io/infer.
[20] James Newsome and Dawn Xiaodong Song. 2005. Dynamic Taint
Analysis for Automatic Detection, Analysis, and SignatureGenerationof Exploits on Commodity Software. In Proceedings of the Network andDistributed System Security Symposium, NDSS 2005, San Diego, California, USA. http://www.isoc.org/isoc/conferences/ndss/05/proceedings/
papers/taintcheck.pdf[21] OWASP. 2015. OWASP on Path Traversal. https://www.owasp.org/
index.php/Path_Traversal.
[22] OWASP. 2017. OWASP Top 10 Project. https://www.owasp.org/index.
php/Category:OWASP_Top_Ten_Project.
[23] Python Taint. [n. d.]. https://github.com/python-security/pyt.

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA[24] Siegfried Rasthofer, Steven Arzt, and Eric Bodden. 2014. A Machinelearning Approach for Classifying and Categorizing Android Sources
and Sinks. In Proceedings 2014 Network and Distributed System Security
Symposium. Internet Society, San Diego, CA. https://doi.org/10.14722/
ndss.2014.23039[25] L. K. Shar, L. C. Briand, and H. B. K. Tan. 2015. Web Application
Vulnerability Prediction Using Hybrid Program Analysis and Machine
Learning. IEEE Transactions on Dependable and Secure Computing 12,
6 (Nov 2015), 688–707. https://doi.org/10.1109/TDSC.2014.2373377[26] Yannis Smaragdakis and George Balatsouras. 2015. Pointer Analysis.
Found. Trends Program. Lang. 2, 1 (April 2015), 1–69. https://doi.org/
10.1561/2500000014[27] Omer Tripp, Marco Pistoia, Patrick Cousot, Radhia Cousot, and Salvatore Guarnieri. 2013. ANDROMEDA: Accurate and Scalable Security Analysis of Web Applications. In Proceedings of the 16th International Conference on Fundamental Approaches to Software Engineering (FASE’13). Springer-Verlag, Berlin, Heidelberg, 210–225.
https://doi.org/10.1007/978-3-642-37057-1_15[28] Omer Tripp, Marco Pistoia, Stephen J. Fink, Manu Sridharan, and Omri
Weisman. 2009. TAJ: effective taint analysis of web applications. ACM
SIGPLAN Notices 44, 6 (May 2009), 87. https://doi.org/10.1145/1543135.
1542486[29] Fabian Yamaguchi, Alwin Maier, Hugo Gascon, and Konrad Rieck. 2015.
Automatic Inference of Search Patterns for Taint-Style Vulnerabilities.
In 2015 IEEE Symposium on Security and Privacy. IEEE, San Jose, CA,
797–812. https://doi.org/10.1109/SP.2015.54[30] Zhemin Yang and Min Yang. 2012. LeakMiner: Detect Information
Leakage on Android with Static Taint Analysis. In 2012 Third World
Congress on Software Engineering. IEEE, Wuhan, China, 101–104. https://doi.org/10.1109/WCSE.2012.26[31] Jonathan S. Yedidia, William T. Freeman, and Yair Weiss. 2003. Exploring Artificial Intelligence in the New Millennium. Morgan Kaufmann
Publishers Inc., San Francisco, CA, USA, 239–269. http://dl.acm.org/
citation.cfm?id=779343.779352

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev

APIpost.title
claimed_user.fullname
create_site_element(param siteResult).Comments
filen.filename
file_instance.filename
flask.views.MethodView::get(param filename)flask.request.form[’srpValueM’]anyaudio.helpers.encryption.decode_data()[’url’]
urlparse.urlparse().port
create(param name)_create_or_edit(param entry).slug
LoginForm().username.data
edit(param name)feed_get(param handle)
flask.request.form[’name’]flask.g.site.publish_log_file
inputtemplate.filename
get_function_data(param jid)_process_new_comment(param comment)
u.username
lava_results_app.models.QueryCondition.get_similar_job_content_types()
response_add(param obj).pk
playlist_edit(param request).user
pymongo.Connection().wbuserstatus.collection_names()
flask.request.form[’json’]rpt.request().bound_action.action.default_format
edit(param path)service_unavailable_handler(param error).description[1]flask.request.form[’bookmark_path’]form.GeneralForm().username.data_hash()[]
execute(param context)
flaskup.models.SharedFile().get()self.request
quota_edit(param request)
render_html(param template)robots(param request)
args.REQUEST[’body’]
google.appengine.ext.webapp.template.django.template.Node::render(param self).src_key
djangoffice.forms.users.UserForm().cleaned_data[’email’]resp[’user_id’]
bathymetry(param projection)models.User().get()flask.current_app.root_path
upload_photo.filename
poll_details(param hackathon_name)flask.request.user.id
argparse.ArgumentParser().parse_args().port
flask.request.stream.read()flask.request.args.get()[6]

Score
0.75
0.75
0.75
0.75
0.75
0.72
0.69
0.6
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.49
0.49
0.49
0.42
0.38
0.38
0.37
0.37
0.28
0.27
0.26
0.26
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.23
0.2
0.2
0.17
0.17
0.16
0.16
0.12
0.12
0.12
0.11
0.1

Correct
✓
✓
✓
✓
✓
✓
✓

✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓

Table 8. Evaluation on 50 random events classified as sources by Seldon.

A

Evaluated Samples

Tables 8, 9 and 10 include detailed evaluation for the random
sample of sources, sanitizers and sinks predicted by Seldon.

In general, it is quite challenging to even check these specifications, if they are not shown in the context of the flows
they appear in, let alone coming up with them directly.

Scalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

API
flux.models.User().url()hunchworks.forms.EvidenceForm().save()clam.common.util.xmlescape()
common.twitter.get_signin_url()
form_valid(param self).request.cradmin_app.reverse_appurl()
shiva.models.Album()utils.helper.MethodView::post(param repo).meta.get_blob()
imgur.getAuthUrl()flask.current_app.aws.connect_to().generate_url()
util.jwt_encode()sahara.utils.wsgi.JSONDictSerializer().serialize()
vm_templates.models.VirtualMachineTemplate.objects.get()redwind.controllers.process_people()
dci.server.auth.hash_password()
QuickEntryForm().save()markdown.Markdown().convert()
helpers.normalize()ba.action.get_target_url()
ghdata.GHTorrent().contributions()transformations.hourly()
mediamanager.MediaManager.cover_art_uuid()
opencricket.chart.syntax_response.SyntaxResponse.build_response()
box.get_authorization_url()
urllib.parse.urlunparse()
silopub.util.set_query_params()
storage.load().content_redirect_url()
faitoutlib.get_new_connection()files.models.File.from_upload()
PayOrderByPaypal.get_paypal_url()
viz_obj.json_dumps()
course.utils.get_flow_access_rules()flask_cas.cas_urls.create_cas_logout_url()
werkzeug.secure_filename()
urllib.urlencode()
generateSavegame.createZip()
jsonConverter.parse_object()
portality.dao.Facetview2.url_encode_query()core.obfuscate()
octavia.amphorae.backends.agent.api_server.util.haproxy_dir()util.shorten()des.encrypt()
dpxdt.server.models.Artifact()
gzip.open()next().process()
esp.program.models.TeacherBio.getLastBio()auth.generate_state()
RentalManager()baiducloudengine.BaiduCloudEngine().check_file()
markdown()
onlineforms.models.FormFiller.objects.create()

Score
1
1
0.75
0.75
0.75
0.75
0.75
0.75
0.75
0.75
0.75
0.75
0.73
0.6
0.58
0.54
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.49
0.49
0.41
0.4
0.28
0.28
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.16
0.12
0.12

Correct
✓
✓
✓
✓
✓

✓
✓
✓
✓

✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓

✓
✓
✓

Table 9. Evaluation on 50 random events classified as sanitizers by Seldon.

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev

API
fs.write()
subprocess.Popen().communicate()common.mail.SendEmail().send()
utils.account.send_verify_mail()
ShellCommandError()mail.send_mail()CommentPostBadRequest()
flask.Blueprint().add_url_rule()
django.utils.six.with_metaclass()::error_response(param response_class)()
flask.helpers.make_response()
catsnap.resize_image.ResizeImage.make_resizes()
ext.render_template()
flask_mail.Mail().send()
flaskext.sqlalchemy.SQLAlchemy().session.add()
db.session.add()
User.query.filter_by()flask.Markup()
django.core.mail.EmailMessage().attach()fp_new.write()db.write()models.Gcm.send_message()flask.current_app.mail.send()
open().write()requests.post()
self.response.out.write()
PyPDF2.PdfFileReader()CookieForm().prepareResponse()qs[0].set_status()groups.models.all_activities()
lastuser_core.models.db.session.add()common.messaging.models.DatedMessage.objects.post_message_to_user()baseframe.forms.render_redirect()
textpress.views.admin.render_admin_response()
upload(param self).container.upload_object_via_stream()
blueprints.admin.models.Users.check_user_passwd()
dismod3.plotting.plot_posterior_region()
object_log.models.LogItem.objects.log_action()flask.abort()
editors.helpers.ReviewHelper().set_data()
textpress.views.admin.flash()
fumblerooski.utils.calculate_record()
redwind.models.Post.load_by_path()
self._fileHandler.addNewFile()
os.dup2()
hooks.fire()
cursor.execute()
anarcho.apk_helper.parse_apk()
standardweb.models.Message.query.options().filter_by()db.session.delete()

Score
1
0.83
0.75
0.75
0.75
0.75
0.75
0.66
0.55
0.55
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.49
0.49
0.49
0.49
0.49
0.48
0.44
0.37
0.36
0.28
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.25
0.22
0.2
0.18
0.17
0.16
0.12
0.1

Correct
✓
✓
✓
✓

✓
✓
✓
✓
✓
✓

✓
✓
✓
✓
✓
✓
✓
✓
✓

✓
✓
✓

✓
✓
✓
✓
✓

Table 10. Evaluation on 50 random events classified as sinks by Seldon.

Scalable Taint Specification Inference with Big CodeB

Initial Seed Specifications

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
a: psycopg2.escape_string()

Below we provide as a listing our initial seed specification.
Lines starting with o: denote sources, with a: sanitizers,
with i: sinks and with b: blacklisted events from these roles:

i: sqlite3.connect().cursor().execute()# Sources

a: sqlite3.connect().cursor().mogrify()
a: sqlite3.escape_string()

o: User.objects.get()i: sqlite3.connect().execute()

o: cms.apps.pages.models.Page.objects.get()o: django.core.extensions.get_object_or_404()

i: flask.SQLAlchemy().session.execute()

o: django.http.QueryDict()o: django.shortcuts.get_object_or_404()

i: db.session().execute()

o: example.util.models.Link.objects.get()o: flask.request.form.get()o: inviteme.forms.ContactMailForm()o: live_support.forms.ChatMessageForm()o: model_class.objects.get()o: req.form.get()o: request.GET.copy()

i: SQLAlchemy().session.execute()
i: flask.SQLAlchemy().engine.execute()
i: SQLAlchemy().engine.execute()
i: db.engine.execute()
i: django.db.models.Model::objects.raw()
i: django.db.models.expressions.RawSQL()
i: django.db.connection.cursor().execute()

o: request.GET.get()o: request.POST.copy()# XPath Injection

o: request.POST.get()i: lxml.html.fromstring().xpath()o: request.args.get()i: lxml.etree.fromstring().xpath()o: request.form.get()i: lxml.etree.HTML().xpath()o: request.pages.get()o: self.get_query_string()# OS Command Injection

o: self.queryset().get()i: subprocess.call()i: subprocess.check_call()o: self.request.FILES.get()i: subprocess.check_output()o: self.request.get()i: os.system()o: self.request.headers.get()i: os.spawn()

o: textpress.models.Page.objects.get()i: os.popen()o: self.get_user_or_404()

o: textpress.models.Tag.objects.get()o: textpress.models.User()a: subprocess.Popen()o: textpress.models.User.objects.get()# XXE# SQL injection

i: lxml.etree.to_string()

i: MySQLdb.connect().cursor().execute()
i: MySQLdb.connect().execute()# XSS

a: MySQLdb.connect().cursor().mogrify()
a: MySQLdb.escape_string()

i: amo.utils.send_mail_jinja()
i: django.utils.html.mark_safe()
i: django.utils.safestring.mark_safe()

i: pymysql.connect().cursor().execute()i: example.util.response.Response()i: pymysql.connect().execute()

i: jinja2.Markup()

a: pymysql.connect().cursor().mogrify()
a: pymysql.escape_string()

i: olympia.amo.utils.send_mail_jinja()
i: suds.sax.text.Raw()
i: swift.common.swob.Response()i: pyPgSQL.connect().cursor().execute()

i: webob.Response()i: pyPgSQL.connect().execute()

i: wtforms.widgets.HTMLString()

a: pyPgSQL.connect().cursor().mogrify()
a: pyPgSQL.escape_string()

i: wtforms.widgets.core.HTMLString()

i: psycopg2.connect().cursor().execute()

i: flask.Response()
i: flask.make_response()
i: flask.render_template_string()

i: psycopg2.connect().execute()
a: psycopg2.connect().cursor().mogrify()

a: bleach.clean()a: cgi.escape()

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA
a: django.forms.util.flatatt()

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev
b: math.*a: django.template.defaultfilters.escape()
a: django.utils.html.escape()# Flask

a: flask.escape()

b: flask.Flask()*

a: jinja2.escape()

b: app.*a: textpress.utils.escape()
a: werkzeug.escape()# Django

a: werkzeug.html.input()b: *django*conf*

a: xml.sax.saxutils.escape()
a: flask.render_template()b: *django*settings*
b: *ugettext*

a: django.shortcuts.render()a: django.shortcuts.render_to_response()

b: *lazy*

a: django.template.Template().render()a: django.template.loader.get_template().render()a: werkzeug.exceptions.BadRequest()# Path Traversal
i: flask.send_from_directory()
i: flask.send_file()b: *RequestContext*# Logsb: *logging*b: *logger*b: tempfile.mkdtemp()
b: type().__name__b: set_size(param n)

a: os.path.basename()b: result.append()

a: werkzeug.utils.secure_filename()b: str().encode()b: ValueError()# Open Redirectb: logging.info()

i: flask.redirect()b: key.split()

i: django.shortcuts.redirect()b: json.dump()

i: django.http.HttpResponseRedirect()# Python built-ins.
# Black list

b: False
b: None# Imports and related functions.
b: *tensorflow*
b: *tf*b: *numpy*
b: *pandas*
b: np.*
b: plt.*b: Trueb: *_()*
b: __import__()b: *__name__*b: *_str()*b: *_unicode()*b: abs()b: pyplot.*b: *.all()b: os.path.*b: *.any()

b: uuid.*b: *.append()

b: sys.*b: ascii()

b: json.*b: *assert*
b: attr()b: datetime.*b: io.*
b: re.*

b: bin()b: hashlib.*b: builtins.str()b: struct.*b: bytearray()b: *String*b: bytes()b: *Queue*

b: *.capitalize()b: threading*b: *.center()b: mutex*
b: dummy_threading*b: chr()b: multiprocessing*b: cmp()b: *module*b: complex()

b: bool()b: classmethod()Scalable Taint Specification Inference with Big Code

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

b: *.copy()b: *.count()b: *.lower()b: *.decode()b: *.maketrans()

b: dict()b: *.map()b: *.difference()b: *.difference_update()b: *.match()b: dir()b: max()b: *.encode()b: meth()b: *.endswith()b: min()b: enumerate()b: next()

b: *.extend()b: object()b: *.filter()b: oct()b: *.find()b: open()b: *.findall()b: ord()b: *.finditer()b: *.pop()

b: float()b: *.popitem()b: *.format()b: pow()b: frozenset()b: print()

b: func()b: *.purge()

b: future.builtins.str()b: getattr()

b: *.quote()b: *.quoted_url()

b: globals()b: range()b: hasattr()

b: reduce()b: hash()b: *.reload()b: help()

b: *.remove()b: hex()b: *.replace()*b: id()

b: *.repr()b: *.index()

b: *.reverse()

b: *.insert()

b: reversed()b: int()b: *.rfind()b: *.intersection()b: *.intersection_update()b: *.rindex()

b: *.isalnum()b: round()b: *.isalpha()b: *.rpartition()b: *.isdecimal()b: *.rsplit()

b: *.isdigit()

b: *.rstrip()b: *.isdisjoint()

b: *.search()b: *.isidentifier()b: set()b: *.isinstance()b: setattr()

b: *.islower()b: *.setdefault()

b: *.isnumeric()

b: *.sort()

b: *.isprintable()b: sorted()

b: *.isspace()b: *.split()*b: *.issubclass()

b: *.splitlines()b: *.issubset()b: *.startswith()b: *.issuperset()b: *.staticmethod()b: *.istitle()

b: strb: *.isupper()b: str()b: *.keys()b: kwargs

b: *.strip()b: strip_date.strftime()

b: *len()b: *.sub()b: list()b: *.subn()

b: *.ljust()

b: sum()b: locals()b: super()b: *.lstrip()b: *.match.group()b: *.rjust()

PLDI ’19, June 22–26, 2019, Phoenix, AZ, USA

V. Chibotaru, B. Bichsel, V. Raychev, M. Vechev

Pull Request
https://github.com/anyaudio/anyaudio-server/pull/163
https://github.com/DataViva/dataviva-site/issues/1661
https://github.com/DataViva/dataviva-site/issues/1662
https://github.com/earthgecko/skyline/issues/85
https://github.com/earthgecko/skyline/issues/86
https://github.com/gestorpsi/gestorpsi/pull/75
https://github.com/HarshShah1997/Shopping-Cart/pull/2
https://github.com/kylewm/silo.pub/issues/57
https://github.com/kylewm/woodwind/issues/77
https://github.com/LMFDB/lmfdb/pull/2695
https://github.com/LMFDB/lmfdb/pull/2696
https://github.com/mgymrek/pybamview/issues/52
https://github.com/MinnPost/election-night-api/issues/1
https://github.com/mitre/multiscanner/issues/159
https://github.com/MLTSHP/mltshp/pull/509
https://github.com/mozilla/pontoon/pull/1175
https://github.com/PadamSethia/shorty/pull/4
https://github.com/sharadbhat/VideoHub/issues/3
https://github.com/UDST/urbansim/issues/213
https://github.com/viaict/viaduct/pull/5
https://github.com/yashbidasaria/Harry-s-List-Friends/issues/1

Number of Bugs
2
2
1
1
2
2
12
1
2
7
1
1
1
1
1
5
1
1
1
3
1

Type of Bug
XSS
Path Traversal
XSS
XSS
SQLi
XSS
SQLi
XSS
XSS
XSS
SQLi
Command Injection
Command Injection
Path Traversal
XSS
XSS
SQLi
SQLi
Code Injection
XSS
SQLi

Table 11. Reported Bugs.

b: *.symmetric_difference()b: *.symmetric_difference_update()b: unknown()

b: *test*

b: *.upper()b: *.translate()b: *.trim_url()

b: *.values()

b: *.truncate()b: zip()b: *.update()b: *.vars()

b: tuple()b: *.type()
b: unichr()b: unicode()C

Reported Bugs

In Tab. 11, we provide a list of all pull requests based on bugs
reported by our taint analysis.