Effective Race Detection for Event-Driven Programs

Veselin Raychev Martin Vechev Manu Sridharan

ETH Zürich ETH Zürich IBM T.J. Watson Research Center
veselin.raychev@inf.ethz.ch martin.vechev@inf.ethz.ch msridhar@us.ibm.com
tifact
Ar t * Complete

*
en

O O * C on *

AE ll Doc Ev
*
t
sis
PS L A

We

C *
se

um
eu

e
nt R
ed
* Easy to
alu
*
at e d
Abstract 1. Introduction
Like shared-memory multi-threaded programs, event-driven Event-driven applications are vulnerable to concurrency er-
programs such as client-side web applications are suscep- rors similar to those in standard multi-threaded applications.
tible to data races that are hard to reproduce and debug. In a typical event-driven program, event handlers are exe-
Race detection for such programs is hampered by their per- cuted by an event dispatcher as a result of event firing. Event
vasive use of ad hoc synchronization, which can lead to a handlers usually execute atomically in a single thread, so
prohibitive number of false positives. Race detection also handler code can assume that no other handlers execute con-
faces a scalability challenge, as a large number of short- currently. However, such systems allow for events to be fired
running event handlers can quickly overwhelm standard non-deterministically (due to user actions, I/O timing, etc.),
vector-clock-based techniques. which may cause the corresponding event handlers to run in
This paper presents several novel contributions that ad- a non-deterministic order. This non-determinism can cause
dress both of these challenges. First, we introduce race cov- serious errors when event handlers share mutable state.
erage, a systematic method for exposing ad hoc synchroniza- Client-side web applications are an important class of
tion and other (potentially harmful) races to the user, signif- event-driven programs susceptible to such errors, as dis-
icantly reducing false positives. Second, we present an ef- cussed in recent work [15]. Modern web applications make
ficient connectivity algorithm for computing race coverage. extensive use of asynchrony, via so-called “AJAX” requests
The algorithm is based on chain decomposition and lever- and also of asynchronous code loading to speed up per-
ages the structure of event-driven programs to dramatically ceived page load time. This asynchrony can lead to non-
decrease the overhead of vector clocks. deterministic errors, which can have severe consequences for
We implemented our techniques in a tool called E VENT- users: e.g., the Hotmail email service was temporarily bro-
R ACER and evaluated it on a number of public web sites. ken in the Firefox web browser due to a data race, potentially
The results indicate substantial performance and precision causing loss of message content [11].
improvements of our approach over the state-of-the-art. Us- The web platform provides few synchronization primi-
ing E VENT R ACER, we found many harmful races, most of tives to programmers. Hence, web applications are forced
which are beyond the reach of current techniques. to coordinate event handler execution via standard shared
variables, i.e., ad hoc synchronization. The atomic execution
Categories and Subject Descriptors D.2.4 [Software Engi-
of event handlers makes such coordination safe. However,
neering]: Software/Program Verification; D.2.5 [Software
lacking knowledge of this synchronization, existing dynamic
Engineering]: Testing and Debugging – Testing tools; F.3.1
race detectors [4, 15, 16] report an overwhelming number of
[Logics and Meaning of Programs]: Specifying and Verify-
races on web applications, exceeding 3000 for some of the
ing and Reasoning about Programs
sites we tested. The vast majority of these races are harm-
General Terms Algorithms, Verification less: they are either used for ad hoc synchronization or are
Keywords Asynchrony; Concurrency; Nondeterminism; infeasible. Manual examination of such a large set of races
Race Detection; Web is nearly impossible, particularly due to the complex control
flow typically found in event-driven programs.
In this paper, we present two advances in concurrency
Permission to make digital or hard copies of all or part of this work for personal or analysis for event-driven applications, making dynamic race
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 detection for such applications more practical. We first in-
on the first page. Copyrights for components of this work owned by others than ACM troduce the notion of race coverage and show how it can be
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or a used to quickly expose ad hoc synchronization. Intuitively,
fee. Request permissions from permissions@acm.org. race a covers race b iff treating a as synchronization elim-
OOPSLA ’13, October 29–31, 2013, Indianapolis, Indiana, USA.
Copyright c 2013 ACM 978-1-4503-2374-1/13/10. . . $15.00.
inates b as a race. Importantly, uncovered races are defined
http://dx.doi.org/10.1145/2509136.2509538 and computed in a way which guarantees that both execution
orderings of the corresponding memory accesses are possi- • Based on the above algorithm, we present a fast algorithm
ble. Since synchronization is employed to handle multiple that computes uncovered races in an execution of an
possible execution orderings, this guarantee makes it very event-driven program.
likely that races on synchronization variables will be uncov- • We describe a set of filters for common harmless or
ered. By inspecting uncovered races first, a user can quickly synchronization races in web applications.
identify races on synchronization variables and completely
• We present an extensive evaluation of race coverage and
avoid inspecting false positives covered by those races. Our
evaluation found the set of variables with uncovered races to filters on a large set of web sites. Our experimental results
be 14X smaller on average than the set of all variables with confirm that variables with uncovered, unfiltered races
races, and we found that many uncovered races were in fact are more than 35 times fewer than all variables with
harmful. races. We also found 75 harmful races in the set of web
Second, we present a dynamic analysis algorithm that ef- sites which we analyzed.
ficiently computes races in event-driven programs by keep-
ing the width of its vector clocks much smaller than the The paper is organized as follows. Section 2 motivates
standard approach. Our technique employs chain decompo- the problem and describes a core language that enables us
sition [7] to discover cases where different event handlers to cleanly capture the essential features of event-driven pro-
can safely re-use the same vector clock slot. This optimiza- grams. It also shows how to adapt existing state-of-the-art
tion dramatically reduces the sizes of the vector clocks in dynamic race detectors to our language and discusses their
practice, significantly improving performance. Using this limitations. Section 3 formalizes the concept of race cov-
algorithm as a building block, we present a second algo- erage and states an important theorem on the feasibility of
rithm which efficiently discovers all variables with uncov- uncovered races. Section 4 discusses efficient connectivity
ered races in an execution trace. algorithms for finding uncovered races. In Section 5, we dis-
To further reduce triage effort for races in web applica- cuss our implementation in WebKit as well as our race fil-
tions, we performed an extensive study of thousands of races ters. Experimental results are discussed and summarized in
and developed six filters for common types of harmless or Section 6. Finally, Section 7 discusses related work and Sec-
synchronization races. In our experiments, the filters addi- tion 8 concludes.
tionally (beyond coverage) reduced the number of races to
inspect by a factor of 2.5. 2. Setting
We implemented our dynamic analysis by first modifying
In this section, we first give a small example web application
the WebKit browser [20] to log a trace of relevant events
to motivate our techniques. Then, we define a simple parallel
from a web application run to disk. Then, our tool ana-
language called Event which enables us to cleanly model the
lyzes the log, computes coverage, classifies discovered races
essential concepts necessary for our analysis. We also define
based on our filters, and displays results in a rich browser-
necessary preliminaries such as races and vector clocks.
based user interface. In our experimental evaluation, we ran
Finally, we show how to adapt current state-of-the-art race
the tool on a wide variety of web sites. Despite the obfus-
detection algorithms to Event, and discuss their limitations.
cated code on many of the sites, we were able to inspect
the uncovered races and manually identify many harmful
2.1 Example
races and synchronization variables. Using E VENT R ACER,
we have found harmful races on the front pages of 21 For- Consider the example in Fig. 1. The web page has an input
tune 100 companies. Our tool is usable by web developers, button, two script nodes with JavaScript code, and many
scalable to real web applications, and available open source other elements which have been elided. Web browsers inter-
at http://www.eventracer.org. leave HTML parsing with handling of other events like user
We believe that the techniques described in this work actions; here, this means that the button can be clicked as
may be applicable in other settings which involve heavy user soon as the input element is parsed, potentially before or
interface manipulations (e.g. Android, iOS). between execution of the other scripts. This leads to po-
tential timing-dependent behaviors:
Main Contributions The contributions of this work are:
• If the button is clicked before the first script runs, the f
• We introduce the concept of race coverage, which en- function invoked by the button’s onclick handler will
ables identification of ad hoc synchronization and greatly not yet have been declared, causing a JavaScript inter-
reduces the number of false positive races reported in preter crash. The interpreter crash is not directly visible
event-driven programs. to the user; however, the user will see no effect from the
• We present a fast dynamic race detection algorithm based button click, a usability bug.
on vector clocks which uses chain decomposition to re- • If the click occurs between execution of the two scripts,
duce the width of the used vector clocks significantly. "not ready" will be displayed, as init is still false.
< html > < body > S ::= S; S | rd(t, x) | wr(t, x) |
< input type = " button " id = " b1 "
f ork(t, u, EventAction)
onclick = " javascript : f () " >
... <! -- many e l e m e n t s -- >
Browser User EventAction ::= Joins; begin(t); S; end(t)
< script >
function f () { Parse input type=”button”
if ( init ) Joins ::= Joins; Joins | join(t, u)
alert ( y . g ) ;
show button
else
alert ( " not ready " ) ; P rogram ::= EventAction
} click
var init = false , y = null ; f() - crash! Operation ::= rd(t, x) | wr(t, x) | begin(t) | end(t) |
</ script > f ork(t, u, EventAction) | join(t, u)
...
Parse script
< script >
y = { g : 42 }; define f t, u ∈ EventIds
init = true ; x ∈ V ars
</ script > a, b ∈ Operation
</ body > </ html >

Figure 2. The Event language

Figure 1. Example web page with both a harmful race and
ad hoc synchronization. The trace on the right shows the
harmful interleaving. • rd(t, x) denotes that event action t performs a read of a
shared variable x. Similarly, wr(t, x) denotes writing to
x.
• If the click occurs after the two scripts run, 42 will be • f ork(t, u, EventAction) means that event action t forks
displayed. an event action u with the operations that u must execute
specified in EventAction.
Ideally, a race detection tool would efficiently expose • join(t, u) denotes that event action t must wait until
issues like the potential crash in this example to the user,
another event action u completes.
without showing too many false positives. In our work we
focused on building a dynamic race detector which works • begin(t) and end(t) denote the beginning and ending of
by taking as input a program trace and then tries to find an event action. At any time, up to one event action can be
(harmful) races between concurrent operations in that trace. executing. That is, event action execution is atomic. Note
We shall discuss challenges in building such a tool at the end that in our language, all reads, writes and forks always
of the section, after introducing some terminology. occur between begin and end.

As an example of translating a web program to Event,

2.2 Language consider again the example in Fig. 1. In web programs, only
Next, we introduce a simple parallel language, called Event parsing of individual HTML tags is atomic, to enable a quick
as shown in Fig. 2. This language cleanly captures the es- response to interleaved events like user clicks. For Fig. 1, the
sential features of event-driven applications (like web appli- parsing of the input tag and each script tag gets translated
cations) that are necessary for our analysis. Sections 3 and 4 to a separate event action. Element ordering is captured
formulate our race detection techniques for Event programs, by adding appropriate f ork operations to tag-parsing event
and then Section 5.1 shows in more detail how a web appli- actions; for the example, the parsing event action for the
cation execution trace can be translated to a trace of an Event input tag forks the script-parsing event action. An event
program. action represents event handler execution for each user click
A program in Event consists of a top-level event action, on the button, and such actions join on the input-parsing
which can read or write shared variables and create (fork) event action (as the button must be present to be clicked).
other event actions. This language is more restricted than a The variable accesses in the scripts translate to wr and rd
general fork-join parallel language. In particular, an event operations in the event actions executing the scripts. We also
action can begin execution only following the completion generate a wr operation for creation of the f function, and a
of another event action, and all event actions execute atom- rd operation for the access of f from the button’s onclick
ically, without interruption. However, it is still possible to handler.
have multiple event actions available for execution at any Fig. 3 shows an execution of the application from Fig. 1
point in the program execution, and the choice for which translated to Event. In this execution, the web application is
of these actions to schedule next is non-deterministic. The loaded and one click of the button with id b1 is performed.
sequential parts of the language such as definitions of condi- Some details of the full translation are omitted for clarity
tionals, loops and expressions are standard and are omitted (e.g. parsing of the html or body tags generates event actions
for brevity. We consider only the following relevant opera- that are omitted). In the execution in Fig. 3, event action
tions: 4 is a click that happens after the script in event action
 1. Event action: input type=”button” The  relation (for operations) is transitive due to
begin(1)
wr(1, #b1) - create button transitivity of  (for event actions) and <π . When a  b
f ork(1, 4, ·) is false we write a 6 b.
f ork(1, 2, ·)
end(1) Definition 2.1 (Race). Given a trace π and operations a
2. Event action: parse first script and b where a <π b, a race R = (a, b) is a pair where both
begin(2) operations access the same variable, at least one is a write
wr(2, f ) // create function f()
···
and a 6 b.
f ork(2, 3, ·)
end(2)
Intuitively, if a trace contains a race R, it means that the
order between racing operations may change in other traces.
3. Event action: parse second script
begin(3) Depending on the kind of operations participating in the
wr(3, y) // var y = race, we refer to it as a read-write, write-read or a write-write
wr(3, y.g) // { g: 42 }
wr(3, init) // var init = true
4. Event action: click button race.
begin(4)
end(3) rd(4, f ) // javascript:f() Vector clocks One approach for capturing the happens-
wr(4, init) // if (init)
··· before relation is using vector clocks [10]. A vector clock
end(4) V C : T → N holds a natural number for each element in T .
An important function on vector clocks is the join function
Figure 3. Example trace for the program in Fig. 1 translated
( t ). Additionally, we define a minimal element (⊥V ) and
to the Event language. Some details are missing for clarity.
a function inct for incrementing the t-th component of a
vector clock (similar notation appears elsewhere [4]):
2 has executed. However, the click could have happened
before the script is parsed, leading to an exception because
V C1 t V C2 = λt.max(V C1 (t), V C2 (t))
javascript:f() would then call an undefined function. Our
tool detects this race by performing a dynamic analysis of a ⊥V = λt.0
single execution trace (i.e. like the one in Fig. 3). inct (V C) = λu. if t = u then V C(u) + 1 else V C(u)

2.3 Order, Races, and Vector Clocks For simplicity, we define join on a set of vector clocks
The execution of a program is defined via traces, where a {V Ci } by t{V Ci } to be V C1 t V C2 t ... for a non-empty
finite trace π = a0 ·a1 ·...·an ∈ Operation∗ (with n ≥ 0) is set {V Ci } and ⊥V otherwise.
a sequence of operations in our language. Here, we abstract 2.4 Adapting Existing Online Dynamic Race Detectors
away the configurations (states) of the program and only
keep the operations. We use the notation [[P]] to denote the A naı̈ve approach to applying existing vector-clock based
set of all traces for a given program P. online dynamic race detectors to our language is to create
a happen-before order between begin and end operations
Trace Order For a given trace π, if operation a occurs encountered in the trace (essentially, mapping these opera-
before operation b in π, we say that a <π b. To simplify tions to global lock/unlock operations). However, while this
exposition we assume that each operation appears only once translation maintains the atomic execution of event actions,
in the trace (if it appears multiple times, we can always no races will be reported as all operations will be treated as
assign a unique identifier to each appearance). Similarly, we “ordered” by a standard race detector. Another, more fruitful
say that event action t precedes event action u in the trace, approach is to: i) avoid introducing happens-before arcs be-
denoted t <π u (we overload the operator), if begin(t) <π tween begin and end operations of different event actions,
begin(u). and ii) only explore traces where event actions do not in-
terleave. In this way, the race detector will not introduce un-
Happens-Before Given a trace π, the happens-before rela- wanted orderings and it will not observe infeasible interleav-
tion  over pairs of event actions t and u in π is the minimal ings.
transitively closed relation, such that t  u holds if t = u,
f ork(t, u, ) ∈ π, or join(u, t) ∈ π (here we used to mean Limitations Two problems arise when applying online
any value is allowed). We denote the event action of an oper- race detectors to event-driven programs, which our tech-
ation a by ev(a). Given a trace π, a happens-before relation niques address:
between two operations a and b occurring in the trace, de- Too many races In our experiments, we found that applying
noted a  b (again, we overload the operator), is true if: race detectors to web programs directly leads to too many
races reported by the analysis (in the thousands). Many
• ev(a) 6= ev(b) and ev(a)  ev(b), or
of these races implement ad hoc synchronization or are
• ev(a) = ev(b) and a <π b infeasible. For Fig. 1, the init variable is used for ad
 hoc synchronization, to ensure y is initialized before it is Event action 1

dereferenced. However, unaware of this synchronization, y={f:42} a

a standard race detector would report an infeasible race init=true c
Event action 2
for the accesses to y. d if(init)
Number of threads A state-of-the art detector such as FAST- b alert(y.f)
T RACK [4] keeps track of vector clocks for each thread
Figure 4. An example of race coverage based on Fig. 1.
and for some of the variables. In FAST T RACK, a vector
Race R = (a, b) is covered by race S = (c, d), since with a
clock requires O(n) space and vector clock operations
happens-before edge from c to d, R would clearly not be a
require O(n) time, where n is the number of threads.
race.
We found that for our programs, n (the number of event
actions) grows into the thousands, hurting scalability.
Event action 1
The number of event actions can grow very quickly due y={f:42} a
to fine-grained atomic actions, e.g., the parsing of each i1=true c1 d1 Event action 2

HTML tag (see Section 2.2) and short-running event han- if(i1)
dlers.
Event action 3
d2 c2 i2=true
if(i2)
b alert(y.f)
The concepts presented in the next section (Section 3)
aim to address the first limitation. The second limitation is Figure 5. An example with a race R = (a, b) covered by
addressed in Section 4. two races S1 = (c1 , d1 ) and S2 = (c2 , d2 )

3. Race coverage create a happens-before edge between c and d, then the race
In this section we address a key problem which arises in race R will disappear, that is, R will no longer be a race.
detection: the race detector produces too many races to be
Definition 3.1 (Covered race). We say that a race R = (a, b)
practically useful. This problem is significantly exacerbated
is covered by race S = (c, d) if the following conditions
for programs in languages such as Event, as Event has no
hold:
synchronization primitives except joining to other event ac-
tions. This means that any synchronization between event 1. ev(a)  ev(c), and
actions needs to be implemented by coordinating via shared 2. d  b
variables, which in turns means that a race detector will pro- We denote that race S covers race R by {S} J R. Note
duce many false positives. These false positives can be cate- that we need d  b and it is not enough to say ev(d)  ev(b)
gorized as follows: as d must come before b, even if they are part of the same
• Synchronization races: these are races which implement event action. Similarly, if we say a  c, then that would be
synchronization and are required for the program to work too restrictive as c can come before a if they are in the same
correctly. event action.
• Races covered by synchronization: these are races that Example Fig. 4 shows an example of the conditions in
can never occur since other synchronization races in fact the above definition, based on the scripts in Fig. 1. The
introduce a happens-before edge. dashed lines denote the two races. On its own, the race
R on y may seem harmful: if the read of y.f executes
Indeed, in our experiments in Section 6, we found that the before initialization, an exception will be thrown. However,
vast majority of races on a web site reported by a standard the synchronization on variable init (the covering race S)
race detector are false positives: many of them are either syn- prevents R from ever executing in a “bad” order, i.e., R is
chronization races or they are covered by synchronization not really a race.
races. The total number of races is often so large that manu- Next, we generalize Definition 3.1 to the case where
ally inspecting all of them is almost impossible. Ideally, we a race is covered by multiple races. The intuition behind
would like to focus only on real races, which are not ordered this generalization in that enforced ordering constraints via
by synchronization. Using race coverage, we were able to (multiple) synchronization races are transitive.
report only races uncovered by synchronization, decreasing
Definition 3.2 (Multi-covered race). We say that a race
the number of races reported by an order of magnitude.
R = (a, b) is covered by a set of races {Si = (ci , di )}ni=1 if
3.1 Race coverage and multi-coverage the following conditions hold:

Next we define what it means for a race to be covered. 1. ev(a)  ev(c1 )

Intuitively, a race R = (a, b) is covered if there is some other 2. for every i ∈ [1, n), ev(di )  ev(ci+1 ).
race S = (c, d) such that if we treat S as synchronization and 3. dn  b
 We denote multi-coverage by {Si }ni=1 J R. The example The above theorem states that if a race R is covered, then
in Fig. 5 shows a fragment of an execution with one race R for the equivalence class [[π]], the race is inaccessible. The
covered by two other races S1 and S2 . intuitive reason is that as R is covered by some other race S,
Let races(π) denote the set of all races which occur in a the operations in S will always occur in the same order in
trace π. An uncovered race is one for which no combination any trace in [[π]] which would force R’s operations to follow
of races in the trace π cover it. We denote the set of all the same order as well, meaning that the operations of R
uncovered races by: cannot be re-ordered in any of the traces in [[π]].
The next theorem states that any uncovered race is acces-
uncovered(π) = {R |R ∈ races(π), sible. This means that any race that we report as uncovered
@C ⊆ races(π) : C J R} is guaranteed to “exist” for some trace.
Theorem 3.6. For a trace π, if R ∈ uncovered(π), then R
3.2 Guarantees is an accessible race.
Next, we show that all uncovered races are feasible (i.e., Using the definition of a multi-covered race, it can be
cannot be eliminated) in the sense that the racing operations shown that for a trace π, races(π) 6= ∅ iff uncovered(π) 6=
of an uncovered race can appear in arbitrary order. This ∅. Then the following is a direct corollary from Theorem 3.5
property is important because such races are likely to be and Theorem 3.6.
of greater interest to the programmer, as they cannot be
eliminated regardless of which other races are considered as Corollary 3.7. A trace π is race-free ([[π]] has no accessible
synchronization. races) iff races(π) = ∅.
First, we define the possible re-orderings of a trace π, This result is useful as it tells us that if we do not find a
referred to as [[π]]. Recall that the notation [[P]] means the race in a given trace, then it means that there are no races for
set of all program traces of a program P. the other traces in [[π]]. Conversely, Theorem 3.6 tells us that
certain races always exist and cannot be eliminated.
Definition 3.3 (Equivalence Class). For a trace π, [[π]] ⊆
In the next section, we will show algorithms for comput-
[[P]] is a set of program traces such that for every trace
ing the set of uncovered races.
π 0 ∈ [[π]], the following conditions hold:
1. if operation a ∈ π 0 , then a ∈ π. 4. Computation of Uncovered Races
2. if operations a, b ∈ π, b ∈ π 0 , and a  b, then a ∈ π 0 and In this section, we present algorithms which compute uncov-
a <π0 b. ered races. These algorithms report at least one uncovered
3. if operations a, b ∈ π, b ∈ π 0 , and race R = (a, b) is a race per variable on which there are uncovered races in the
race in π, then either: execution. We present our algorithms using graph terminol-
(a) a ∈ π 0 and a <π0 b, or ogy and discuss how they can be realized both in an online
(b) a 6∈ π 0 and b is the last operation of π 0 . as well as in an offline setting.
Intuitively, the set [[π]] includes the traces that satisfy the 4.1 Happens-Before via Graph Connectivity
happens-before relation  and where all races in π are
Happens-before queries can be answered as connectivity
resolved in the same way in each trace in [[π]], that is, racing
queries in a graph. Given a trace π, we build a graph G =
accesses follow the same order in the trace. The set [[π]]
(V, E) where the nodes V ⊆ EventIds represent all event
allows for one case where a race in π 0 is not resolved in
actions in the trace and the arcs E ⊆ EventIds×EventIds
the same way as in π. This occurs when condition 3(a) does
are such that for any pair of nodes t and u, there is a path
not hold, but condition 3(b) holds. We call such a race an
from t to u in G iff t  u. That is, given a trace π, we define:
accessible race:
• V = {t | begin(t) ∈ π}, and
Definition 3.4 (Accessible race). A race R = (a, b) in a
trace π is accessible, if there exists a trace π 0 ∈ [[π]], such • E = {(t, u) | f ork(t, u, ) ∈ π or join(u, t) ∈ π}
that b ∈ π 0 , but a 6∈ π 0 .
The graph G is a directed acyclic graph and the sequence
From both definitions, it follows that operation b must be of event actions in any valid trace π is a topological ordering
the last operation of π 0 . Intuitively, this is because after an traversal of G. Then, given a trace π,1 by first building the
accessed race occurs, we may not be always able to reason graph G (which represents the happens-before relation  )
about the behavior of the program only based on the trace we can determine if a pair of operations which access the
π. The next two theorems discuss the connection between same variable (with at least one operation being a write) are
uncovered and accessible races. racing by checking whether their corresponding two event
actions (two nodes) are connected in G.
Theorem 3.5. If a race R ∈ races(π)\uncovered(π), then
R is not accessible. 1 In an online detector, the trace can be partial.
 4.1.3 Vector clocks with Bit Vectors
0 [0,0] [0,0,0,0,0] 0 observation is that if each node uses its own
[0,0] [0,0,0,0,0] 0 An interesting
vector clock entry, vector clocks can be represented com-
[1,0] 1 2 [0,1] pactly
[0,1,0,0,0] 1 using bit vectors,
[0,0,1,0,0] 2 as each entry will always be 0 or 1
2 [0,1] [0,1,0,0,0] 1 [0,0,1,0,0] 2
(as in Fig. 6(a)). However, even with this optimization, the
[1,2] 3 algorithm
[0,1,1,1,0] required
3 more than a gigabyte of memory to han-
[0,1,1,1,0] 3
dle larger applications in our experiments.

[0,1,1,1,1] 4 [1,3] 4 [0,1,1,1,1]

4.1.4 4 clocks with chain decomposition
Vector
(a) (b) We propose an improved graph connectivity algorithm
which combines vector clocks with chain decomposition
Figure 6. Example showing vector clocks with and without similar to the one proposed by Jagadish et al. [7] and Awar-
chain decomposition. gal and Garg [1]. A chain decomposition optimization sug-
gests covering the nodes of a graph with a minimal number
of chains for performing fast connectivity queries. A chain
Next, we discuss four orthogonal algorithms for perform-
is a set of nodes {ai }m
i=1 , such that there is a path from ai to
ing graph connectivity. All of these algorithms are later
ai+1 in G for every i ∈ [1, m). Let CIds denote the set of
evaluated on graphs obtained from traces of web programs
all chains. Then, we assign every node in G to a chain via the
(see Table 3 in Section 6).
function cid : EventIds → CIds. For example, Fig. 6(b)
shows a chain decomposition of the example graph, using
4.1.1 Breadth-first search (BFS)
two chains, one in dark grey and one in light grey.
A standard algorithm for connectivity checking between a Given the chain assignment, we allocate one vector clock
pair of nodes performs a breadth-first or depth-first graph of width |CIds| (in this case V C : CIds → N) for every
traversal of G. Then, each connectivity check has a maxi- node t in the graph and assign the vector clock values ac-
mum time complexity of O(|E|), but many checks complete cording to a modified function vc : EventIds → V C:
faster. While the algorithm has the advantage of low space
complexity, our experiments indicate that such an algorithm vc(t) = inccid(t) (t{vc(u) | u 6= t, (u, t) ∈ E})
performs on average orders of magnitude slower (than our fi-
nal algorithm) and is unable to complete execution on some Since the number of chains is typically much smaller than
web applications in a reasonable amount of time. the number of nodes (over 33X smaller on average in our
experimental evaluation, as shown in Table 3), this technique
4.1.2 Vector Clocks can dramatically reduce the size of vector clocks. Fig. 6(b)
Many race detection algorithms determine connectivity us- shows how vector clocks of width 2 are assigned to the nodes
ing vector clocks, described previously in Section 2.3. Each using the chain decomposition. Note that with chains, vector
node is assigned a vector clock of width |V |, with one slot clocks can no longer be represented using bit vectors.
per node. The vector clock vc(t) for node t is defined as: Computing optimal chain decomposition has O(|V |3 )
time complexity, but a greedy technique (which we use in
this work) typically produces as few chains [7]. The space
vc(t) = inct (t{vc(u) | u 6= t, (u, t) ∈ E})
complexity of our connectivity algorithm is O(|CIds| · |V |),
and the time complexity for each query is O(1).
Since the graph G is acyclic, the function vc is well defined.
For a pair of nodes t and u, t  u holds iff vc(t)[t] ≤ vc(u)[t] Representing the Graph G We note that vector clock con-
(see the reachability theorem in [7]). Hence, given a pre- nectivity algorithms do not explicitly store the graph G.
computed vc function for each node, a reachability query They only maintain the map from nodes to vector clocks (as
takes one integer comparison, which is constant time. well as the cid function for the algorithm in Section 4.1.4)
As an example, Fig. 6(a) shows a small graph and the which is used to answer reachability queries.
corresponding vector clocks for each node (the node number
is its vector-clock index). Given the vector clocks, we can 4.2 Computation of initial set of races
see, e.g., that event 1 does not happen before event 2, since Next, we describe the first step in computing uncovered
vc(1)[1] > vc(2)[1]. races. One way to compute uncovered races is to first com-
The above algorithm has O(|V |2 ) space complexity, and pute the set of all races. Using one of the four connectivity
since our event graphs can have thousands of nodes or more, algorithms above, we can compute the set of all races by
this leads to a blowup in practice. We evaluated a sim- checking pairs of write operations or pairs of a read and a
ple vector-clock-based algorithm and found it to run out of write operation on the same variable. However, first comput-
memory for some of our applications (see Section 6). ing the set of all races may be an unnecessary overhead. For
example, a variable with n writes may contain up to n·(n−1) Given this sorted order, for every remaining race r, we
races if all of its writes are unordered by the  relation. remove all of the subsequent races in the ordering that r
covers according to Definition 3.1 (checking this requires
Reduced starting set of races We next discuss how to
two connectivity queries for the two conditions). Let the
discover uncovered races by first computing a smaller set
remaining set of races be RemainingCandidates.
of initial races. We refer to this set as UncoveredCandidates.
Consider a pair of races on the same variable R1 = (a, c) 2. Next, we present an algorithm for finding the set of
and R2 = (b, c) such that a  b. In this case, if R1 covers uncovered races, which also excludes races covered by
any other race R0 , then R2 also covers R0 . Hence, we do not more than one race from the set RemainingCandidates.
need to obtain R1 if we can obtain R2 . We build a graph G0 = (V 0 , E 0 ) with nodes representing
Similarly to multi-coverage, the idea can be extended as races generated from the previous step:
follows. We do not need to obtain a race R = (a, b) for • V 0 = RemainingCandidates
which there is a set of other races on the same variable • E 0 = {((a, b), (c, d)) | ev(b)  ev(c)}
Si = (ci , di ), Si 6= R, i ∈ [1, n] where the following hold:
Then, for every race R = (c, d) ∈ V 0 , if there exists a
• a = c1 or a  c1 , and pair of nodes S1 = (a1 , b1 ) ∈ V 0 and S2 = (a2 , b2 ) ∈
• di = ci+1 or di  ci+1 for all i ∈ [1, n), and V 0 , such that ev(c)  ev(a1 ), b2  d, and there is a
path from S1 to S2 in G0 , then R is a covered race. The
• dn = b or dn  b
reason R is covered is that the set of races in the path
If the above conditions hold, from Definition 3.1 and from S1 to S2 will cover R. After removing all such
Definition 3.2, it follows that for any R0 , if {R} J R0 , races from RemainingCandidates, the remaining races
then {Si }ni=1 J R0 and hence we need not discover R0 as are uncovered races.
there are other races (Si ) that will be found. That is, the set
UncoveredCandidates is the set of all races minus the set of The correctness of the algorithm follows from the fact
races which satisfy the above conditions. that for every race R, if R is covered by a set of other races,
then it is covered by a set of uncovered races, which form a
Computation of UncoveredCandidates Consider a vari- path in G0 and the above algorithm will find that path.
able with p writes w1 , w2 , ..., wp (here write wi happens be-
fore wi+1 in the trace) and q reads r1 , r2 , ..., rq (here read Time complexity Let |UncoveredCandidates| = n and
ri happens before ri+1 in the trace). Below we define candi- |RemainingCandidates| = m. Assuming the time com-
date pairs which we check for whether they participate in a plexity of the connectivity query is constant-time (which
race: is true for all three vector-clock connectivity algorithms),
• all pairs (wi , wi+1 ), i ∈ [1, p); then computation of uncovered races has time complexity
O(n · m + m3 ). As we will see in our experimental results,
• for each ri , i ∈ [1, q], where wpredi is the last write this procedure usually takes less than a second.
before ri occurred (if one exists).
• for each ri , i ∈ [1, q], the pair (ri , wsucci ) where wsucci 4.4 Online Analysis
is the write right after ri occurred (if one exists). In an online setting where we do not store the trace π, all of
For each of the above pairs (a, b), if a 6 b (checked using the described algorithms can be realized as follows.
one of the four algorithms described earlier), we add the pair First, chain decomposition can be used online as a direct
to the set UncoveredCandidates. This approach produces at replacement of naı̈ve vector clocks. Because connectivity
most p − 1 + 2 · q races per variable, a significant reduction queries can be made while the graph is not fully built, the
from the maximum number of possible races per variable online setting requires us to use a greedy chain assignment,
p · (p + q − 1). e.g. for every node added to the graph, we assign to it the
first possible chain (if such a chain exists), or to a new chain
4.3 Computation of uncovered races otherwise.
Next, based on UncoveredCandidates, we present an algo- Second, we can augment an existing vector clocks based
rithm for finding all variables with uncovered races. race detector to produce the set UncoveredCandidates. This
only requires the race detector to keep reporting races on a
1. We first eliminate all races which are covered by only variable even after it finds the first race.
one race. We sort the set UncoveredCandidates = {Ri = Finally, to find uncovered races we maintain the map vc
(ai , bi )}ni=1 according to the order in which their second (the mapping from nodes to vector clocks), which is instru-
operation appears in the trace π, that is, if bi <π bj , then mented state that standard race detectors already maintain.
i < j. According to condition 2 of Definition 3.1, every We also maintain the graph G0 whose size is a small fraction
race Ri may cover only races Rj such that i < j. of the size of vc.
4.5 Offline Analysis 1 < html > < body >
2 < input type = " button " id = " b1 " >
To use the described algorithms in an offline setting, we need 3 < input type = " button " id = " b2 "
to store the trace π. To mitigate the potential space overhead 4 onclick = " javascript : f () " >
5 < script >
from storing the full trace, we avoid storing some of the op- 6 var likeLocal , lazy ;
erations. In our setting, if there are multiple races for one 7 function f () {
8 likeLocal = 5;
variable between operations in the same pairs of event ac- 9 if (! lazy ) {
tions, we report only one race. This means that if an event 10 lazy = 9 + likeLocal ;
11 }
action contains multiple reads or multiple writes of one vari- 12 }
able, it is enough to store the first read and the first write. 13 document . getElem entById ( ’ b1 ’)
14 . a d d E v e n t L i s t e n e r ( " click " , f ) ;
This optimization is sound and does not affect the correct- 15 </ script > </ body > </ html >
ness of the races we find or the guarantees provided by race
coverage. With this optimization, our experiments (in Sec- Figure 7. An example web application with several races.
tion 6.2) show that the size of trace log files is acceptable
and storing the entire trace in memory requires space com-
1. Event action: parse line 2
parable to the space consumed by vector clocks for the graph
wr(1, #b1) - create button
connectivity algorithm.
4. Event action: click on b1
2. Event action: parse line 3
5. Implementation wr(2, #b2) - create button
rd(4, #b1.click)
wr(4, likeLocal)
Here we describe the implementation of E VENT R ACER, wr(2, #b2.click)
rd(4, lazy)
which performs race detection offline on a trace in the Event wr(4, lazy)
language (see Fig. 2), generated by an instrumented Web- 3. Event action: parse script rd(4, likeLocal)
Kit browser. We chose to implement an offline race detector wr(3, f ) - define f()
since recorded traces enable apples-to-apples comparisons rd(3, #b1)
of the different connectivity algorithms based on which race wr(3, #b1.click) = f 5. Event action: click on b2

coverage is computed (since each algorithm runs on the rd(5, #b2.click)

same trace) and other detailed analyses; scalability of the rd(5, f ) - javascript:f()
offline approach was not an issue (see Section 6.2). In this wr(5, likeLocal)
section, we discuss the translation of web page executions rd(5, lazy)
to the Event language, our implementation of the race detec-
tor, and some additional race filters that do useful automatic Figure 8. Example trace for the program in Fig. 7, which in-
categorization specific to web races. cludes several races. Solid arrows represent happens-before,
dashed lines show some of the races. Note: some details are
5.1 Translation of a web application to Event omitted for clarity.
A translation from a web application to the Event language
consists of two main parts:
language, we define logical memory locations representing
1. generating the read and write operations. the state of the DOM tree, in addition to the straightforward
2. generating event actions and f ork and join operations translation of JavaScript variables to Event variables. We
between them. translated memory accesses to Event as follows:
Here we outline the main principles of our translation. • Reads and writes of JavaScript variables, object fields,
Our translation builds on the modelling of web semantics and functions were directly translated to rd or wr opera-
in Petrov et al. [15], but we exploit the structure of Web- tions in Event. (At the lowest level, all these entities are
Kit itself to achieve greater simplicity and generality when in fact object fields in JavaScript, simplifying the imple-
generating event actions. mentation.) DOM API methods were modeled as rd or
Memory accesses Our modeling of memory accesses is wr operations of the appropriate logical memory loca-
largely identical to that of Petrov et al. [15], but we handle tions.
more cases like JavaScript arrays; we describe it here briefly. • Some DOM nodes have a list of event listeners for the
The web platform provides a high-level declarative language possible events on corresponding UI elements. Any mu-
for creating user interface elements (HTML and CSS) and a tation of this list (e.g., via a call to addEventListener or
scripting language for the application code (JavaScript). The setting an on<X> attribute for event <X>) is translated to a
languages are linked by the Document Object Model (DOM) wr operation of a corresponding logical memory location
APIs, which enable reading and modifying user interface l. Firing an event, which causes execution of all attached
elements from JavaScript. When translating to the Event event listeners, is translated as rd operation on l.
 • A special type of memory locations for DOM elements using the join construct to capture the induced happens-
is the set of all DOM node identifiers. The DOM tree before. Here are examples of ad hoc synchronization vari-
allows querying for elements by their id and such a query ables in WebKit:
is translated to a rd operation in the Event language.
1. A counter in each document for the number of child
Creation of an element with an id attribute or writing the
iframe HTML documents being loaded. Each created
id field of a DOM object is a modification to the set of
iframe increments this counter, while finishing the load-
DOM identifiers and translates to a wr operation on a
ing of an iframe decrements it. A load completion event
variable representing the DOM id.
is triggered only after this counter decreases to zero.
• JavaScript arrays are a special case of JavaScript vari-
2. A counter in each document for the number of child
ables. Arrays provide reads and writes from an index that
resources like images or scripts that are currently loading.
we translate to rd and wr of the corresponding index like
The use of this counter is similar to the iframe counter.
regular variables. Additionally, arrays provide methods
that append to the end of an array, iterate over elements, 3. A counter in each document for the number of pending
remove an interval of elements or get its length. To han- scripts to execute.
dle these methods, we added an additional logical mem- 4. A queue of the pending tags to parse.
ory location for the entire array. All operations that read
the size of the array or access a cells are considered reads, By translating WebKit’s core event structure directly in-
while all operations that add or remove cells are consid- stead of separately handling each HTML feature, our transla-
ered writes of this memory location. tion is able to cover a bigger part of HTML5 than what was
described in [15], including newer features like video and
The example program in Fig. 7 contains accesses of the audio tags and modification listener events. Our approach is
JavaScript variables f, likeLocal and lazy, the click event mostly applicable to other browser engines, as they are also
handler of buttons b1 and b2, and the set of DOM identifiers. implemented as event-based systems (the event-driven struc-
Fig. 8 shows an execution trace for Fig. 7 with the relevant ture is specified in HTML5 [5]). Minor changes to the engine
memory accesses translated to the Event language. may be needed to disable optimizations that merge multiple
web-level events, as this merging may hide races. For Web-
Event Actions, Forks and Joins The work of Petrov et Kit, we disabled the ability to parse more than one HTML
al. [15] specified a detailed happens-before relation for the element in an event action.
web, with specific rules for constructs like scripts, images, Our modifications worked across several versions of
etc. Rather than instrumenting the handling of each such WebKit that we tested, and our experiments were done us-
construct, we exploited the fact that WebKit itself is struc- ing SVN version 116000 of the code.2 Our reasoning about
tured as an event-driven program—by translating WebKit’s the WebKit implementation in terms of our Event language
internal event-driven structure directly to Event, we could shows the generality of our techniques. In fact, one could
handle a wider variety of HTML constructs than what was imagine using our techniques to build a race detector for the
specified in previous work with a relatively small amount WebKit implementation, with race coverage exposing the ad
of code. We can do this, because ordering constraints be- hoc synchronization we discovered manually.
tween events are typically enforced only by the browser.
This means that even if an external agent like a server tries 5.2 Race analyzer
to order events, the order is likely not enforced at the client Our browser based on modified WebKit produces a program
side due to the network. trace, which is logged to a file, together with debug informa-
The implementation of WebKit contains event handler tion describing the types of events, JavaScript scope infor-
code for each unit of work in rendering a web page: parsing mation, the values of the JavaScript variables and the source
an HTML element, executing a script, handling user input, code of any executed JavaScript. Our race analyzer takes the
etc. We translated each of these handlers to an event action in Event program trace augmented with the debug information
Event. Many WebKit event actions are ordered via internal as input.
timers: starting a timer event action u from event action t is The user interface for the race analyzer is implemented
translated to f ork(t, u). Similarly, an event action t starting as a web server providing interactive views of the execution
a network request with response event action u is modeled trace and detected races. The user can inspect reads and
as f ork(t, u). We also introduce f ork(t, u) where t creates writes of any memory location in the trace, the happens-
a UI element e and u handles some event on e. The trace in before graph, and all corresponding JavaScript code (even
Fig. 8 shows possible event actions for parsing each HTML when the code was dynamically generated). For discovered
tag and event actions for user clicks on the two buttons from races, the UI shows race coverage information and filters
one possible execution run. out covered races in its default view. Initially showing only
We found that WebKit itself uses ad hoc synchronization
to order certain event actions, which we translated to Event 2 http://svn.webkit.org/repository/webkit/trunk
uncovered races is a sensible default, as the user can easily clicks while the page is not fully loaded will not be pro-
identify synchronization races and avoid inspection of races cessed. While this is certainly a race, it is a common pattern
covered by synchronization (see Section 3). We shall show in in web applications and typically viewed as an acceptable
Section 6 that in practice, only a small subset of all races are degradation of the user experience. The click handler for the
uncovered, so this default also significantly reduces triage button b1 in Fig. 7 matches this pattern: if the user clicks
effort. b1 before the code at line 13 runs, the f function will not
execute.
5.3 Race filters
Lazy initialization When a JavaScript variable has only
To further improve the usability of E VENT R ACER, we im-
one write, only one read of the value undefined (or the
plemented several filters for common race patterns specific
value null) preceding the write in the same event action,
to web applications. These filters automatically categorize
and multiple other reads in other event actions following the
certain uncovered races as either likely synchronization or
write in the trace, we assume this variable is used as lazy
likely to be harmless. A user can first investigate the uncate-
initialization. Such a variable may have races, but we assume
gorized races, which are more likely to be harmful, and then
every read to be checking for undefined and be harmless.
quickly study the filtered races to confirm that the automatic
This filter is only a best-effort guess that races on a variable
categorization is appropriate. The automatic categorizations
are harmless. In our experience, the races it caught were
are based on extensive experience inspecting thousands of
always harmless, but it may hide a real bug, so the races
race reports across real-world web sites. It is possible for
may merit more careful inspection. A common code pattern
a filter to be inaccurate, e.g., by flagging a harmful race as
for such variables is similar to the one shown for variable
likely to be harmless. However, we manually inspected many
lazy in Fig. 7: the racing accesses check if the variable is
filtered races during our experimental evaluation, and we did
initialized and only the first one initializes it.
not observe any inaccuracy, so we expect this to be rare in
practice. Commuting operations Races on certain memory loca-
tions like cookie and className of DOM nodes typically oc-
Writing same value When a memory location has only
cur from commuting methods like addClass, removeClass,
write-write uncovered races and the racing operations write
hasClass, etc.. We filter these races as we discovered they
the same value to the variable, the races are flagged as likely
are often harmless.
to be harmless. Web sites often have multiple scripts that
initialize a variable to the same value, and this filter captures Race with page unload We classify variables having only
that pattern. The variable likeLocal in Fig. 7 matches this races with a memory access in the page unload event handler
pattern. The f function is executed when either button is separately. The harm of such races to a web application is
clicked, and thus the value 5 will be written to likeLocal limited to only the unload event and any error will likely not
no matter which button is clicked first. be visible to the user. Most of these races were in libraries,
Only local reads In some cases, a JavaScript global vari- but in cases when a developer adds logic in the unload
able is essentially used as a local: any read of the variable events, these races may be worth investigating.
gets a value from a preceding write in the same event ac-
5.4 Likely harmful races
tion. In such cases, we flag races on the variable as likely to
be harmless. For these races, the user may want to fix the We also created filters for two types of races that are likely
code by reducing the visibility of the variable, as adding a to be harmful; E VENT R ACER automatically flags these races
read without a preceding write to new code could cause a as important for the user. Note that both these filters are only
harmful race. The variable likeLocal in Fig. 7 matches this applied to variables that have not already been flagged by the
pattern as well. The value of the variable is read only in the filters described in Section 5.3.
same event action after it is written.
Uninitialized values This filter identifies races that may
Late attachment of event handler We flag write-read and involve a use of an uninitialized location. The filter se-
read-write races on event handlers as a separate class of lects variables v with uncovered races where for all writes
races. This type of race is specific to the web and common {wi }ni=1 of v in the trace that precede a read r, the pairs
in sites using libraries like jQuery.3 Such sites enable many (wi , r) are uncovered races. For races that pass this crite-
event handlers only after the page has completed some ini- rion, we can show via Theorem 3.6 that it is possible to
tial loading, in order to reduce perceived page load time. build a trace such that the read r can read an uninitialized
This practice can lead to many race reports, since the user value (since no write is ordered before the read). Such a race
can interact with a partially-loaded page. For example, if is harmful when the code that performs the read does not
a click handler is attached only after the page loads, user check for an uninitialized value. In our experimental evalua-
tion, we manually inspected races flagged by this filter, and
3 http://jquery.com/ we found some of them to be harmful.
 An example of such a race is for the variable f in Fig. 7. In Number of variables with races
Metric Mean Me- 90-th Max
this case, a user with a slow network connection may execute dian %-ile
the click handler before the script is loaded and the function All 634.6 461 1568 3460
Removed by single coverage (Definition 3.1) 581.1 419 1542 3389
f is initialized, causing an unhandled exception in the click Removed by multi-coverage (Definition 3.2) 8.2 2 30 55
handler. Remaining with uncovered races 45.3 29 103 331
Filtering methods
Writing same value 0.75 0 3 12
readyStateChange handler This filter selects variables v Only local reads 3.42 2 8 43
with uncovered races (a, b) such that at least one of ev(a) or Late attachment of event handler 16.7 8 41 117
Lazy initialization 4.3 0 11 61
ev(b) is an event handler for the readyStateChange event. Commuting operations - className, cookie 4.0 1 8 80
These are typically response handlers for asynchronous Race with unload 1.1 0 2 33
Remaining after filters from Section 5.3 17.8 10 38 261
“AJAX” or resource load requests, which are error-prone Uninitialized values 1.9 0 5 36
due to possible wide variance in network response time. We readyStateChange handler 1.3 0 2 64
manually inspected races from this filter and found some of
Table 1. Usability metrics of E VENT R ACER on the Fortune
them to be harmful.
100 sites.

6. Evaluation fetched each website and ran our auto-exploration for 15

Here we present an experimental evaluation of E VENT- seconds.
R ACER, which implements the optimized race detector, cov-
6.1 Race Detector Usability
erage techniques, and filters described earlier. Our evaluation
tested the following experimental hypotheses: To evaluate the usability of E VENT R ACER, we studied the
number and type of races reported across our benchmarks.
1. Race coverage (Section 3) and our other filters (Sec- Here we first discuss the effectiveness of our automatic tech-
tion 5.3) dramatically reduce the number of races the user niques for reducing the number of races shown to the user,
must initially inspect. race coverage (Section 3) and filters (Section 5.3). Then, we
2. If a site contains harmful races, those races are often present results from a manual classification of the remaining
contained in the initial set of uncovered, unfiltered races races, including a discussion of observed harmful races and
shown to the user. synchronization patterns.
3. Race detection that constructs vector clocks based on Automatic Techniques Table 1 presents results showing
chain decomposition (see Section 4.1.4) performs signif- the effectiveness of our automatic techniques for reducing
icantly better than standard vector-clock-based race de- the number of races shown to the user. As is standard in race
tection. detection work, we give the number of memory locations
that have at least one race of the provided type.
Section 6.1 presents a usability experiment to test the first
Only showing variables with uncovered races (as de-
and second hypotheses, and Section 6.2 describes a perfor-
fined in Definition 3.2 to include multi-coverage) reduces
mance evaluation to evaluate the third hypothesis.
the number of displayed variables with races by a factor of
As in previous work [15], we evaluated E VENT R ACER
14, from 634.6 per site on average to 45.3. Most of the re-
on the home pages of the companies in the Fortune 100. To
duction comes from races covered by a single other race, but
automatically exercise some basic site functionality, we also
multi-coverage also plays a significant role in comparison to
implemented an automatic exploration technique similar to
the number of remaining races. This large reduction, along
that of W EB R ACER [15, §5.2.2]. The automatic exploration
with the guarantee that both orderings of any uncovered race
performs simple actions like typing in text boxes, hovering
are in fact feasible (Theorem 3.6), is strong evidence for the
the mouse, etc., which can expose additional races. Auto-
usefulness of race coverage in practice. Together, the filters
matic exploration cannot deeply explore a rich web applica-
from Section 5.3 yield roughly another 2.5X reduction in
tion; in future work, we plan to integrate our techniques with
number of variables with races, down to 17.8 per site on av-
a tool like Artemis [2] to expose more races in such sites.
erage. The “Late attachment of event handler” filter is most
Note that since the Fortune 100 sites change frequently,
effective, indicating the frequent usage of this pattern on real
and we do not have the exact site versions used in the W EB -
sites. Most of the other filters are also useful: each of them
R ACER work [15], the numbers presented here cannot be
catches more than ten races on at least one site. Note that for
compared directly to those in the W EB R ACER paper. We
some variables, multiple filters may apply.
have preserved and will make available the site traces used
in the current work, to enable future comparisons. Manual Classification We performed a manual classifica-
We ran our experiments on a Core i7 2700K machine tion of those uncovered races that did not match the filters for
with 16GB of RAM, running Ubuntu 12.04. E VENT R ACER likely harmless races described in Section 5.3, and matched
was implemented in C++ and compiled with GCC 4.6. We our filters for likely harmful races described in Section 5.4.
There were 314 such variables with races, which we man- cause all of the site’s menus to be non-operational until
ually classified as a synchronization operation, harmful, or the page was reloaded.
harmless. Table 2 summarizes the results of our classifica- • verizon.com: a drop-down menu lets the user control
tion. Along with totals, we separately give the number of whether a personal or business account should be used for
DOM variables and JavaScript variables in each category. login. If the user made the selection too soon, an unseen
Due to code obfuscation, we could not classify the races on exception was thrown, due to a race involving access to a
nine variables. function defined in a later script. The user was then forced
to wait for a full page load, select the opposite account
Synchronization races 178 of the variables with races
type, and then switch back in order to continue the login.
we inspected were synchronization operations, with spe-
cial logic to enforce orderings based on the variable’s value. • adm.com: we found a harmful race that may be an is-
This large amount of synchronization in the uncovered races sue in the ASP.NET framework itself.4 HTML forms
further validates the utility of race coverage, as (false) races have an action attribute to hold the URL to which the
covered by this ad hoc synchronization are completely hid- form data should be submitted. A form’s action at-
den from the user. tribute was only URL escaped by JavaScript code in the
For DOM synchronization races, typically the applica- page’s onload handler. Hence, if a user submitted the
tion had logic that delayed or disabled some action if the form before the page load completed, the submission
appropriate DOM node was present. For JavaScript syn- could fail due to invalid characters in the form’s URL. As
chronization races, many idioms were observed. In some the relevant HTML and JavaScript code appeared to be
cases, a conditional checked for an undefined value before auto-generated by ASP.NET, this issue could be shared
the read was performed. In other cases, the possible excep- by any site using the framework’s AJAX functionality.
tion from reading an uninitialized value was caught in an • unitedhealthgroup.com: we observed a form with a
exception handler, which started a timer to retry the opera- hidden token ID field that was set only once the page’s
tion later. A third common type of synchronization was per- onload event fired. If the user submitted the form before
formed by using data structures: for example, one event ac- the loading completed, the server would not see the token
tion would store a JavaScript object in an array, and another ID and hence might not be able to record the user data.
action would periodically execute code for each element in • fedex.com: the page loaded two versions of the jQuery
the array. This type of synchronization often occurred in library in a non-deterministic order! The version that
commonly-used libraries like jQuery. loaded last would control the relevant global variables
exposing jQuery functionality. While we could not find
Harmful races We identified 75 variables with harmful
any broken functionality due to this non-determinism,
races in 21 sites. In many cases, the harm was limited to
using only one version of jQuery would certainly reduce
an uncaught JavaScript exception, e.g., a ReferenceError
the site’s load time.
caused by trying to read a field from the undefined value.
Most browsers are configured not to display such exceptions,
Overall, race coverage enabled us to find many harmful
and only inspection of the event log will show them. How-
bugs in these sites, despite the fact that the code in most of
ever, they still degrade the user experience, as they often
the sites has already been well-tested and was obfuscated.
cause user interface glitches (e.g., a mouse click that does
We believe that E VENT R ACER will be even more useful
nothing and must be repeated).
to the actual website developers who have access to non-
Using E VENT R ACER, we also found more severe bugs
obfuscated versions of the code.
that were too complex to investigate using previous tools
like W EB R ACER [15]. In fact, we found that some of the Harmless races We discovered 52 variables with only
races described in the work of [15, §2.3] were covered harmless races (roughly 16% of those inspected), due to
by other harmful or synchronization races. E VENT R ACER application-specific semantics. Given this low false positive
hides many of the false positives, enabling the user to focus rate, we believe E VENT R ACER is already a very useful tool
on analyzing important races. Here are brief descriptions of for web developers.
some new issues we discovered in various web sites:
6.2 Race Detector Performance
• ford.com: a script waited until a certain DOM node
x was present, and then initialized handlers for another The performance evaluation of E VENT R ACER consists of
DOM node y. Here, x was used for ad hoc synchroniza- two parts: the performance overhead in the modified web
tion, which E VENT R ACER exposed as an uncovered race. browser, and the performance of the offline race analyzer.
However, E VENT R ACER showed that the race on x un- We study these issues in turn.
expectedly did not cover a race on y. Hence, there was
a “bad” interleaving of accesses to y, which we found to 4 http://www.asp.net
 Total Synchronization Harmful Harmless Unknown Metric Mean Median Max
314 178 (59 / 119) 75 (33 / 42) 52 (2 / 50) 9 Number of event actions 5868 2496 114900
Number of edges 6822 2873 122240
Number of chains 175 134 792
Table 2. Number of variables with races of different types,
based on manual classification. Numbers for each race type Connectivity algorithm Running time in seconds
are presented as “X (Y / Z)”, where X is the total, Y Breadth-first search >22.2 >0.4 TIMEOUT
Vector clocks w/o chain decomposition >0.068 >0.011 OOM
is the number of DOM variables, and Z is the number of Bit vector clocks 0.081 0.008 3.381
JavaScript variables. Vector clocks + chain decomposition 0.043 0.007 2.395

Table 3. Performance metrics of E VENT R ACER on finding

Instrumentation Overhead Our modifications of WebKit uncovered races in the Fortune 100 sites.
to generate traces for race detection add some performance
overhead. JavaScript execution suffers the biggest overhead, Metric Mean Median Max
as we log many variable reads and writes. Furthermore, as Trace file size (uncompressed) 7.9MB 3.7MB 129.5MB
Trace file size (gzip compressed) 1.4MB 0.7MB 16.3MB
in previous work [15], our technique disables the JavaScript Vector clocks memory consumption
just-in-time compiler, as the WebKit interpreter is much eas- Vector clocks w/o chain decomposition 544MB 12MB 25181MB
Bit vector clocks 33MB 1MB 1573MB
ier to instrument. We observed a roughly 95X slowdown Vector clocks + chain decomposition 5MB 1MB 171MB
for the SunSpider benchmarks5 with our instrumented inter-
preter as compared to Google’s V8 JavaScript engine run in Table 4. Memory consumption of different race detection
Chrome 25.6 However, when browsing in practice, network techniques.
latency and other rendering operations often consume much
more time than JavaScript execution. In our experience us- iments show that BFS is too slow to be run in practice for
ing the instrumented browser, it seemed fast and responsive, some of the web sites and ran above five minutes on three of
and there was no significant slowdown in the load times or the sites. We classified these runs as timeout, which allowed
the user interface of the sites we browsed. us to only underapproximate the mean and median running
Race Analyzer Speed To evaluate the performance of our times of the algorithm. On the other hand, vector clock based
offline race detector, we ran the detector using the four approaches tend to be very fast, but naı̈ve implementations
different techniques for answering reachability queries on run out of memory.
the happens-before relation, the most costly computation
Memory consumption In Table 4 we first show the storage
during race detection (see Section 4.1):
space needed for the traces of our offline analysis, which was
1. a tuned breadth-first search (BFS) of the happens-before quite low (a maximum of 16.3MB for compressed traces).
graph; Next, we show the memory consumption of the vector clocks
2. a standard vector-clock-based technique, where each for the connectivity checks in E VENT R ACER using naı̈ve
event action is given a unique thread ID; vector clocks, bit vector clocks, and vector clocks with chain
decomposition.7 These algorithms store one vector clock per
3. vector-clock-based technique with bit-vectors; node of the connectivity graph and their memory consump-
4. our final optimized vector clocks algorithm based on tion is proportional to the number of nodes and the width
chain decomposition. of the vector clocks. Chain decomposition is particularly
For the vector clocks used with chain decomposition, we useful for the larger tests, reducing maximum memory con-
used 16-bit integers for each entry, and we employed SSE sumption from 1573MB for bit vector clocks to 171MB. For
instructions to speed vector clock computation. We ensured deeper testing of large-scale web applications, we believe the
that the integers never overflowed by modifying the chain memory reductions from chain decomposition will become
decomposition procedure to never produce chains with more even more important.
than 216 − 1 nodes. The reported memory results are usable as a lower bound
Table 3 summarizes the running times for computing un- for many existing online race detection techniques. For ex-
covered races (Section 4.3) in a loaded trace and presents ample, FAST T RACK needs one vector clock per event ac-
some metrics over the site traces that help explain the per- tion to store the connectivity information like in our offline
formance differences. race detector (FAST T RACK does not use chain decomposi-
For each technique, we give the mean, median, and max- tion, but can be improved to use it). This also means that the
imum running times across our benchmark sites. Our exper- offline nature of E VENT R ACER was not a disadvantage, as
the memory needed for vector clocks is not greater than the
5 http://www.webkit.org/perf/sunspider/sunspider.html
memory required to store a trace.
6 W EB R ACER [15] reported a 500X slowdown for the same benchmarks.
W EB R ACER did online race detection, but since E VENT R ACER’s optimized 7 These numbers were computed analytically rather than measuring actual
race detector usually runs in a fraction of a second, E VENT R ACER’s overall memory consumption, enabling us to handle cases where the naı̈ve vector
execution time for race detection is lower. clocks ran out of memory.
7. Related work E VENT R ACER for detecting races in web applications, and
In this section, we discuss related work that is closest to ours. showed that they lead to large performance and usability
The work of Petrov et al. [15] presents a happens-before re- improvements in an experimental evaluation.
lation [9] for web applications and uses it as a basis for a While exposing uncovered races improves usability, our
dynamic race detector. While their work found many races, current technique still cannot automatically determine which
it suffered from two key drawbacks: the race detector could races are on synchronization variables. In future work,
miss races [15, §5.1], and worse, by default it reported many we plan to address this limitation, based on previous ap-
infeasible races. The authors worked around the second is- proaches [12, 18] and on static analysis techniques. We also
sue via ad hoc filters that reduced the number of reported plan to study techniques for automatically fixing some types
races [15, §5.3]. However, those filters hid most races on of harmful races.
JavaScript variables, thereby hiding the ad hoc synchroniza-
tion necessary to avoid reporting infeasible races. References
FAST T RACK [4], a state-of-the art online race detector
[1] AGARWAL , A., AND G ARG , V. K. Efficient dependency
was already discussed at various places throughout the pa-
tracking for relevant events in shared-memory systems. In
per. Ad hoc synchronization in the form of spin-locks has PODC (2005).
been detected in a number of multi-threaded scenarios [8,
[2] A RTZI , S., D OLBY, J., J ENSEN , S. H., M ØLLER , A., AND
12]. However, such techniques are often based on running a
T IP, F. A Framework for Automated Testing of JavaScript
program multiple times on a modified thread scheduler. For
Web Applications. In ICSE (May 2011).
web applications, modifying the thread scheduler would be
very challenging, and collecting multiple runs that manipu- [3] C HRISTIAENS , M., AND B OSSCHERE , K. D. Accordion
clocks: Logical clocks for data race detection. In Euro-Par
lated the UI would be laborious for testers. Shi et al. detect
(2001).
patterns of harmful races [19], but they also strongly rely on
executing the application multiple times to extract invariants. [4] F LANAGAN , C., AND F REUND , S. N. FastTrack: efficient
Netzer and Miller [13, 14] discuss the feasibility of races and precise dynamic race detection. In PLDI (2009).
in parallel programs. Similar to our work, they start from the [5] HTML5 specification. http://www.w3.org/TR/html5/.
set of all races and produce a set of feasible races. However [6] I DE , J., B ODIK , R., AND K IMELMAN , D. Concurrency
their work has two important drawbacks: first, they cannot concerns in rich Internet applications. In EC2 (2009).
always produce the actual set of feasible races – in some
[7] JAGADISH , H. V. A compression technique to materialize
cases they produce sets of tangled races such that at least one transitive closure. ACM Trans. Database Syst. 15, 4 (Dec.
race from each set is feasible. Second, their work produces 1990), 558–598.
actual feasible races only in case the interleaving events are
[8] K ASIKCI , B., Z AMFIR , C., AND C ANDEA , G. Data races vs.
single-access [14] while web event actions almost always
data race bugs: telling the difference with Portend. In ASPLOS
consist of multiple memory accesses. (2012).
Ide et al. [6] discuss the existence of web races, but pro-
pose no actual analysis. Zhang et al. [21] provide a static [9] L AMPORT, L. Time, clocks, and the ordering of events in a
distributed system. In ACM Operating Systems (1978).
analysis for some of the concurrency bugs in AJAX appli-
cations, but their technique does not handle all web races, [10] M ATTERN , F. Virtual time and global states of distributed
and it suffers from difficulties in performing a precise static systems. In Proc. Workshop on Parallel and Distributed
analysis of JavaScript [17]. Algorithms (1989), C. M. et al., Ed.
An optimization of the vector clocks width called accor- [11] Bug 538892 - Replying to or forwarding emails on Hotmail no
dion clocks is proposed in [3]. However, this approach de- longer works properly: message content is often lost. https:
creases vector clock width only when all objects accessed //bugzilla.mozilla.org/show_bug.cgi?id=538892.
by a thread are deleted, which does not happen in web appli- [12] NARAYANASAMY, S., WANG , Z., T IGANI , J., E DWARDS ,
cations that typically access long-lived DOM objects. A., AND C ALDER , B. Automatically classifying benign and
harmful data races using replay analysis. In PLDI (2007).
8. Conclusion and Future Work [13] N ETZER , R. H. B., AND M ILLER , B. P. Improving the
accuracy of data race detection. In PPOPP (1991).
We have presented novel techniques for performing effi-
cient and usable dynamic race detection for event-driven [14] N ETZER , R. N., AND M ILLER , B. P. Detecting data races in
programs. Showing uncovered races improves usability parallel program executions. In LCPC (1989).
by exposing important races to the user first, particularly [15] P ETROV, B., V ECHEV, M., S RIDHARAN , M., AND D OLBY,
those that reflect ad hoc synchronization. For efficiency, J. Race detection for web applications. In PLDI (2012).
our race detection algorithm employs chain decomposition [16] P OZNIANSKY, E., AND S CHUSTER , A. Efficient on-the-fly
techniques to avoid bloating the size of key vector clock data race detection in multithreaded c++ programs. In PPoPP
data structures. We implemented these techniques in a tool (2003).
[17] R ICHARDS , G., L EBRESNE , S., B URG , B., AND V ITEK , J. Appendix: Proofs
An analysis of the dynamic behavior of JavaScript programs.
Theorem 3.5. If a race R ∈ races(π) \ uncovered(π),
In PLDI (2010).
then R is not an accessible race.
[18] S EN , K. Race directed random testing of concurrent pro-
grams. In PLDI (2008), pp. 11–21. Sketch of Proof: Assume that a covered race R = (a, b) is an
[19] S HI , Y., PARK , S., Y IN , Z., L U , S., Z HOU , Y., C HEN , W., accessible race in π. This means that there is trace π 0 ∈ [[π]],
AND Z HENG , W. Do i use the wrong definition?: Defuse: such that b is the last operation in π 0 and a 6∈ π 0 . Let R
definition-use invariants for detecting concurrency and se- be covered by {Si = (ci , di )}ni=1 . Then dn  b and from
quential bugs. In OOPSLA (2010). condition 2 in Definition 3.3 ⇒ dn ∈ π 0 . Let us denote
[20] WebKit. http://www.webkit.org/. a = d0 . We will show that for every i ∈ [0, n], di ∈ π 0
[21] Z HENG , Y., BAO , T., AND Z HANG , X. Statically locat- and di is not the last operation of π 0 . For i = n, we have
ing web application bugs caused by asynchronous calls. In shown it already.
WWW’2011 (2011). From di not being the last operation of π 0 and from
condition 3 (a) ⇒ ci ∈ π 0 . But ev(ci ) 6= ev(b) and because
the trace π 0 is valid, end(ev(ci )) ∈ π 0 . But from ev(di−1 ) 
ev(ci ) and end(ev(ci )) ∈ π 0 ⇒ di−1 ∈ π 0 .
From d0 = a ∈ π 0 , follows that R is not a accessible race
in π.
Theorem 3.6. Any race R ∈ uncovered(π) is an accessi-
ble race in π.
Sketch of Proof: Let R = (a, b) ∈ uncovered(π). For
each of the remaining races are not always after R, let their
corresponding pairs of event actions be:

X = {(ev(c), ev(d))|S = (c, d) ∈ races(π), S 6= R, b 6 d}

We build the smallest transitively closed relation B ∗ , from

the set B, which joins the happens-before relation with X
(B =  ∪X). We will analyze B as a directed acyclic
graph. Then we will build a consistent trace π 0 , following
a topological order of B ∗ .
First we will show that, z = (ev(a), ev(b)) 6∈ B ∗ . Let us
assume z ∈ B ∗ . R is a race ⇒ z 6∈ . Then there is a path p
from a to b in B, for which at least one arc from the path is
in X and the remaining arcs are in. Let us take the races of
arcs of p in X and put them in the set {Si }ni=1 . Then all the
conditions in Definition 3.2 are satisfied and {Si }ni=1 J R.
This is a contradiction with R ∈ uncovered(π), so z 6∈ B ∗ .
From z 6∈ B ∗ , we can traverse the nodes of B ∗ in an
order, such that we traverse b before traversing a. We will
build a trace π 0 by adding the operations from π in this order,
such that b is the last operation of π 0 . Then we need to verify
if the constructed π 0 satisfies the conditions of Definition
3.3. Condition 1 is satisfied by construction, condition 2 is
satisfied because⊆ B ∗ and condition 3 is satisfied because
X ⊆ B ∗ . Following standard semantics of operations, it can
be shown that π 0 ∈ [[P]]. Then π 0 ∈ [[π]]. But a 6∈ π 0 , which
means that R = (a, b) is an accessible race.