arXiv:1708.06774v1 [cs.CR] 22 Aug 2017

Deterministic Browser

Yinzhi Cao

Lehigh University

Bethlehem, PA

yinzhi.cao@lehigh.edu

Zhanhao Chen

Lehigh University

Bethlehem, PA

zhc416@lehigh.edu

Song Li

Lehigh University

Bethlehem, PA

sol315@lehigh.edu

Shujiang Wu

Lehigh University

Bethlehem, PA

shw316@lehigh.edu

ABSTRACT

Timing attacks have been a continuous threat to users’ privacy in

modern browsers. To mitigate such attacks, existing approaches,

such as Tor Browser and Fermata, add jitters to the browser clock

so that an attacker cannot accurately measure an event. However,

such defenses only raise the bar for an attacker but do not fun-

damentally mitigate timing attacks, i.e., it just takes longer than

previous to launch a timing attack.

In this paper, we propose a novel approach, called determinis-

tic browser, which can provably prevent timing attacks in modern

browsers. Borrowing from Physics, we introduce several concepts,

such as an observer and a reference frame. Speciﬁcally, a snippet

of JavaScript, i.e., an observer in JavaScript reference frame, will

always obtain the same, ﬁxed timing information so that timing

attacks are prevented; at contrast, a user, i.e., an oracle observer,

will perceive the JavaScript diﬀerently and do not experience the

performance slowdown. We have implemented a prototype called

DeterFox and our evaluation shows that the prototype can defend

against browser-related timing attacks.

CCS CONCEPTS

•Security and privacy →Browser security;Web application

security;

KEYWORDS

Determinism, Web Browser, Timing Side-channel Attack

1 INTRODUCTION

Timing attacks have continuously posed a threat to modern web

browsers, violating users’ privacy. For example, an adversary can

infer the size of an external, cross-site resource based on the load-

ing time [45, 46]; a website can ﬁngerprint the type of the browser

based on the performance of JavaScript [33, 34]; two adversaries

can talk to each other via a covert channel [38, 45].

Faced with browser-related timing attacks, researchers from both

industry and academia have proposed solutions to mitigate such

attacks by adding noises or called jitters to the time available to

the attackers and decreasing the time precision. For example, Tor

Browser [4], an industry pioneer in protecting users’ privacy, re-

duces the resolution of per f or mance.now, a ﬁne-grained JavaScript

Conference’17, July 2017, Washington, DC, USA

2017. ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00

https://doi.org/10.1145/nnnnnnn.nnnnnnn

clock, to 100ms; following Tor Browser, major browsers, such as

Chrome and Firefox, also reduces the resolution to 5µs. Similarly,

Kohlbrenner and Shacham proposed Fermata [26], a solution that

introduces fuzzy time [21] into browser design and then degrades

not only the explicit clock like per f ormance .now but also other

implicit clocks like setT imeout in the browser.

However, the aforementioned prior work—which reduces the

browser’s clock resolution—only raises the bar for an attacker but

do not fundamentally mitigate timing attacks. Even if such work

is deployed, it just takes longer time for an adversary to launch

an aforementioned timing attack and obtain the information that

she needs. Say, an adversary tries to infer a resource’s size based

on the loading time, i.e., launching a side-channel attack. All the

existing defenses only limit the bandwidth of such a side chan-

nel as acknowledged by Kohlbrenner and Shacham [26]. Consider

JavaScript performance ﬁngerprinting as another example. Jitters

that are added by existing defenses can be averaged out, when the

attack is performed longer or in multiple runs.

Apart from the prior work targeting browser-related timing at-

tacks, another direction that prevents lower-level timing attacks,

such as L2 cache attacks, is to introduce determinism. Examples

of such approaches are Deterland [48], StopWatch [29, 30], and

λP AR

S EC [50]. However, Deterland still adopts statistical, non-deterministic

solutions for external events by grouping events together, which

only limits the bandwidth of an external timing attack. StopWatch

cannot prevent internal timing attacks, and needs virtual machine

replication for I/O events, which is not applicable at a higher level,

such as a browser. λPAR

S EC is a new programming language with en-

sured security property, but requires that all the existing programs

are rewritten and follow their language speciﬁcation. In sum, it still

remains unclear how to apply determinism in real-world systems

even at lower level let alone web browsers so as to prevent timing

attacks.

In this paper, we propose deterministic browser, the ﬁrst ap-

proach that introduces determinism into web browsers and prov-

ably prevents browser-related timing attacks. Both challenges and

opportunities arise in deterministic browser. One challenge is that

JavaScript, the dominant web language, is event-driven, i.e., JavaScript

engine may be waiting for events without executing any state-

ments; accordingly, one opportunity is that JavaScript is singled-

threaded—speciﬁcally no event can interrupt the JavaScript execu-

tion.1

1The statement holds, even if we take WebWorkers, a new HTML5 standard, into

consideration.

To better explain deterministic browser, let us revisit timing at-

tacks. A timing attack is that an adversary tries to measure the

duration of a target, secret event (called a “target secret” in the pa-

per) using a reference clock of the physical time. The target secret

is an event that the adversary does not know how long it takes

to ﬁnish, e.g., the parsing time of a cross-origin script. The refer-

ence clock is used to measure the target secret, which could be

explicit, e.g., per f or mance.now, or implicit, e.g., setT imeout and

reques tAnimationFr ame. An implicit reference clock is based on

an event that the adversary knows how long it takes to ﬁnish. The

duration of such known event is deﬁned as an implicit clock tick,

usually much smaller than the duration of the target secret.

Anecessary condition of launching a successful timing attack is

that all three key elements—i.e., (i) an adversary, (ii) a target secret,

and (iii) a reference clock—have to co-exist at the same time in a

runtime environment. An adversary is the subject, a target secret

is the object, and a reference clock is the tool that the subject used

to steal the object. Therefore, a natural solution is to remove one

or more of the three key elements from the runtime environment

and break the necessary condition. However, all three elements

are essential in a browser and hard to remove. An adversary just

looks like a normal client-side JavaScript. The detection of such

JavaScript is a diﬀerent research direction and based on past re-

search on JavaScript malware detection [11, 17], false positives and

negatives are hard to avoid. A target secret is a common browser

operation such as script parsing—i.e., the removal of target secrets

will break the browser functionality. We can remove2an explicit

reference clock of the physical time, such as pe r f ormance .now,

but many implicit clocks like setT imeout and using JavaScript ex-

ecution as minor clocks [26] also exist and contribute to essential

browser functionalities.

In deterministic browser, instead of removing key elements from

the entire runtime environment, i.e., the web browser, we break

down the web browser into several smaller units and remove one

or more diﬀerent key elements from these smaller units. That is,

from a macro perspective, all three key elements still exist in the

web browser; from a micro perspective, at most two elements exist

in one smaller unit. Speciﬁcally, the smaller unit that we introduce

is called reference frames (RFs),3a new, abstract concept borrowed

from Physics. Each RF has one independent clock and sometimes

an observer—e.g., a JavaScript program possibly controlled by the

adversary. Just as in Physics, the job of the observer is to measure

the duration of an event in the RF, i.e., making two observations at

the start and end of the event, obtaining two timestamps and cal-

culating the interval. In web browser, one important yet diﬀerent

property of a RF is that one and only one event—e.g., a target secret

or an implicit clock tick event—can be executed in one RF; diﬀer-

ent events are executed in diﬀerent RFs separately. (As discussed

in Section 3.1, RFs are usually implemented by OS level threads.)

We now look at diﬀerent RF examples and explain how to remove

key elements of a timing attack from these RFs. In general, RFs can

be categorized into two types: with and without a target secret.

2Strictly speaking, because a clock is an essential concept, the so-called removal of a

clock is just to deﬁne a new clock in which the ticking unit is zero.

3Note that a reference frame is not an HTML or JavaScript frame: An H TML or

JavaScript frame may contain many reference frames. To avoid confusion, we often

use the abbrevi ation, i.e., RF, for reference frame in the paper.

First, let us say a RF is executing a target secret—that is, all three

key elements co-exist in this RF. JavaScript execution engine is

such an example, in which the target secret is the execution per-

formance of JavaScript. In such case, we need to redeﬁne the clock

in the RF such that when an observer measures the duration of

any event, it can always calculate the duration based on what it

has already known without looking at the clock. A RF with such a

clock is deﬁned as deterministic (Deﬁnition 1) in our paper. Here

our deﬁnition of determinism—which provably prevents timing at-

tacks shown in Theorem 1—is broader than the existing deﬁnition,

such as the one used in DeterLand [48]. We further show that in the

context of JavaScript RF, our deﬁnition can boil down to a simple

form (Theorem 2), and then be specialized to the existing d eﬁnition.

Particularly, the clock in JavaScript RF ticks based on the number

of executed opcodes.

Second, let us say a RF has no target secret, e.g., a RF execut-

ing a tick event for an implicit reference clock. Concrete examples

are like a RF executing setT imeout, one dealing with an HTTP

request, and another executing r equest AnimationF rame. In such

cases, only two elements exist in the RF—there is no target secret

for the adversary to steal. That is, the clock in such RFs can fol-

low the physical time. However, the clock information in such RFs

can be communicated to a deterministic RF that has a target secret,

hence being used for measurement. Therefore, when a determin-

istic RF receives information from another (non-deterministic) RF,

we need to make the recipient RF remain deterministic (Lemma 1)—

the technique of such communication between RFs is deﬁned as de-

terministic communication (Deﬁnition 2). Particularly, as shown

in Section 5, we introduce a priority queue to replace the origi-

nal event queue, i.e., the central communication data structure, in

the JavaScript event model. Our new priority queue synchronizes

clocks in two RFs from the viewpoint of the recipient observer. In

other words, when the recipient observer sees the communication

message conveying the time from other RF, e.g., the physical time,

the conveyed time is the same as its own clock.

Apart from the aforementioned categorization of RFs based on

whether a target secret exists, RFs can also be classiﬁed based on

the existence of an observer, one with an observer called a main

RF and one without called an auxiliary RF. The clock in a RF is

in an undeﬁned state when an observer is absent, because only

observers can obtain timing information, i.e., making observations.

Then, the clock will become available when the observer is back,

usually when a RF communication happens. For example, when

a JavaScript RF is waiting for an event to ﬁnish, the clock in the

JavaScript RF is undeﬁned and determined by the event to ﬁnish.

For another example, when a setT imeout RF is waiting for some

amount of time, the clock is also undeﬁned and determined when

the RF communicates with the JavaScript RF.

Another important property of deterministic browser—which

is just similar to Physics—is that diﬀerent observers perceive dif-

ferent time elapse in their own RFs. For example, the observer in

JavaScript RF, i.e., a snippet of JavaScript code possibly controlled

by an adversary, will always obtain the same p erformance informa-

tion when measuring itself so that timing attacks are prevented. At

contrast, an oracle observer, e.g., the user of the browser, will per-

ceive the JavaScript execution just as normal as in a legacy browser

so that she does not experience the performance slowdown as what

the JavaScript observer does.

We have implemented a prototype of our deterministic browser

called DeterFox by modifying a legacy Firefox browser. Our eval-

uation shows that DeterFox can defend against browser-related

timing attacks in the literatu re and is compatible with existing web-

sites. Note that our implementation is open-source—the repository

and a video demo can be found at this website (http://www.deterfox.com).

2 THREAT MODEL

We present our threat model from three aspects: in-scope attacks,

a motivating example, and out-of-scope attacks.

In-scope Attacks. In this paper, we include browser-related tim-

ing attacks in our threat model. As described, such attacks are

made possible because an adversary can measure the duration of a

target secret at client-side browsers using a reference clock. The ad-

versary is the client-side JavaScript and the reference clock could

be the physical one deﬁned by p er f ormance .now or other implicit

ones, such as setT imeout . The target secret varies according to the

speciﬁc attack scenario, and now let us use the following three ex-

amples to explain it.

•JavaScript Performance Fingerprinting. JavaScript performance

ﬁngerprinting [33, 34] is one special case of browser ﬁngerprint-

ing where an adversary executes a certain snippet of JavaScript

code and ﬁngerprints the browser based on how long the execu-

tion takes. In such attacks, the target secret is the performance

of JavaScript execution on the speciﬁc machine.

•Inference of Cross-origin Resource via Loading Time. An adver-

sary website may load resources from a third-party website via a

script tag and measure the parsing time by the browser until an

error event is triggered. By doing so, the adversary can infer the

size of the response and thus other private information, such as

the number of Twitter friends [45, 46]. This is also called a tim-

ing side channel attack. In this example, the target secret is the

loading of the cross-origin response, which the adversary does

not know due to the same-origin policy.

•Inference of Image Contents via SVG Filtering. Stone [44] shows

that an adversary can apply an SVG ﬁlter on an image and infer

the contents based on how long the ﬁltering process takes. By

doing so, the adversary can steal the pixels of a cross-origin im-

age or browsing history. In this example, the target secret is the

performance of the SVG ﬁlter. Note that the reference clock used

in this attack is requestAnimationF r ame.

A Motivating Example. Now let us look at a motivating exam-

ple in Figure 1. The example contains two versions of attacks: syn-

chronous (Line 1–21) and asynchronous (Line 22–28) ones. The

synchronous version uses p er f ormance .now as the reference clock

and the asynchronous one uses set I nt erval . We will discuss how

determinism prevents these two versions in Section 4.1.4 and 5.3

respectively.

The synchronous attack (Line 1–21) adopts a so-called clock-

edge technique invented by Kohlbrenner and Shacham [26], which

measures a minor clock, e.g., a simple, cheap JavaScript operation

like count + +, by repeating the operation between two edges of a

major clock, e.g., the physical clock, for multiple times. Then, one

1function nextEdge() {

2start = performance .now();

3co u n t = 0;

4do {

5co un t ++ ;

6}while (start ==performance .now ());

7return count;

9function fingerprinting () {

10 nextEdge();

11 fingerprint = nextEdge ();

12 }

13 function sideChannelSync () {

14 fingerprint = fingerprinting ();

15 nextEdge();

16 start = performance .now();

17 targetSecret ();

18 stop = performance. now();

19 remain = nextEdge ();

20 duration = (stop - start) + ( fingerprint -remain )/

fingerprint *grain;

21 }

22 to t a l = 0;

23 function countFunc (){total ++;}

24 function callback(){ duration = total *u;}

25 function sideChannelAsync () {

26 targetSecretAsync (callback );

27 setInterval (countFunc , u);

28 }

Figure 1: A Motivating Example.

can calculate the minor clock by dividing the granularity of major

clock by the number of executed operations. Here is the detail of

the attack. The ne xt Edдe function (Line 1–8) tries to ﬁnd the next

edge of the major clock (per f or mance.now) and count the number

of executed operations towards the next major clock edge. For a

JavaScript ﬁngerprinting attack (Line 9–12), one can ﬁrst skip the

rest of the current major clock period (Line 11), and then calculate

the number of operations in a full major clock period (Line 12) for

ﬁngerprinting. For a side-channel attack (Line 13–21), one can ﬁnd

the ﬁngerprint (Line 14), start from a new edge (Line 15), and then

measure a target secret using the major clock (Line 16–18). The

remaining cycles in the minor clock are counted (Line 19), and the

duration for the target secret is calculated by combining the minor

and major clo cks (Line 20). Note that дrain is the granularity of the

major clock.

The asynchronous attack (Line 22–28) adopts an implicit clock,

e.g., setT imeout ,se tInterval or request AnimationFrame, to mea-

sure an asynchronous target secret, e.g., the time to parse a third-

party response. First, the sideChannelAsync function (Line 25–28)

invokes an asynchronous target secret function—for simplicity, we

hide the details in the t arдetS ecre tAsync function with only a callback

function (Line 26). Then, the implicit clo ck is invoked via a setInterval

function with countFunc as a callback (Line 27). The count Func

will be invoked periodically with a uinterval until the callback is

invoked, i.e., the target secret ﬁnished execution. Then, one can cal-

culate the duration of the target secret based on how many times

count Func is executed (Line 24).

Out-of-scope Attacks. We now look at out-of-scope attacks. Par-

ticularly, we restrict the target secret in the timing attacks to be

browser-related and exclude these depending on other parties, such

as the web server and the user. Such restriction is natural because

we only make the browser deterministic but not others.

•Server-side timing attacks. In a server-side timing attack, a mali-

cious client infers a secret—e.g., some information that the client

cannot access without login—at the server side [13]. Examples

are that a user can infer the number of private photos in a hidden

gallery based on the server’s response time. To prevent such at-

tacks, one can rely on existing defenses [7] by normalizing web

traﬃc or changing the server-side code.

•User-related timing attacks. User-related timing attacks refer

to, for example, biometric ﬁngerprinting, which measures the

user’s behavior, such as keystroke and mouse move, and identi-

ﬁes users based on these biometrics. Many of such ﬁngerprint-

ing tactics, such as keystroke dynamics, are also related to time.

Such attacks are out of scope, because the target secret, e.g.,

mouse move, comes from the user.

3 DETERMINISTIC BROWSER

In this section, we introduce several general deﬁnitions.

3.1 Concepts

Borrowing from Physics, we ﬁrst introduce the concepts used in

our deterministic browser.

Areference frame (RF), in the context of our deterministic browsers

(referred as our context), is an abstract concept with a clock that

ticks based on certain criteria, e.g., the real-world physical time, the

execution of JavaScript, and the parsing of HTML. Concretely, we

can consider that a RF can be implemented via an OS-level thread

in web browsers, although there are no strict one-one mappings be-

tween threads and RFs in web browsers. Speciﬁcally, some browser

kernel threads may not be RFs and two threads, if one runs imme-

diately after another, may belong to the same RF.

Let us take a browser API, e.g., setT imeout or set Inte rv al , and

its implementation in Firefox, as a concrete example of creating

RFs. The JavaScript engine of Firefox, a RF in our context, is run-

ning in the main thread of Firefox. When JavaScript code calls

setTimeout or set I nterval under the window object, a new timer

thread—i.e., a new RF—is created. After the speciﬁed time in setT imeout

or set I nt er val passes, the timer thread will communicate with the

main thread with an event. That said, the concept of RF is natu-

ral and modern browsers have already provided implementations.

Note that although we use Firefox as an example, the concept of RF

is abstract and general. In a multiple-process browser, like Google

Chrome, RFs could be represented by processes or threads in mul-

tiple processes.

The concept of RF deﬁnes a unit that is smaller than all other

web containers, such as HTML frames, origins, JavaScript runtime,

and browser tabs. The advantage of a RF is that we can easily sepa-

rate three key elements—an adversary, a target secret, and a refer-

ence clock—of a timing attack. For example, because a RF is singled-

threaded, i.e., can execute only one event, a target secret and an

implicit clock tick are separated in diﬀerent RFs naturally.

For each RF, one important concept is called an observer. In our

context, an observer is deﬁned as a Turing complete program that

can make observations, e.g., access the data belonging to the RF

or measure the execution status of itself. Some RFs have observers,

such as a JavaScript RF with JavaScript program, and some, such

as DOM RFs, do not. A RF with an observer is called a main RF,

and a RF without an observer an auxiliary RF. For the purpose of

deﬁning determinism, we can consider virtual observers residing

in auxiliary RFs.

3.2 Deﬁnition of Determinism

Let us introduce the deﬁnition of determinism, which includes two

parts: (i) how to deﬁne a deterministic RF, and (ii) how to deﬁne

a deterministic communication between RFs. Next, we will show

how determinism can prevent timing attacks. Now we ﬁrst deﬁne

a deterministic RF in Deﬁnition 1.

Definition 1. (Deterministic RF) Given a reference frame (RF )

and an observer (Ob)—no matter active or virtual, we deﬁne a RF as

deterministic if and only if the following holds:

When the Ob makes two observations O1and O2at timestamps

t1and t2measured by the internal clock, t2−t1can be represented

as a function of O1and O2, i.e., t2−t1=f(O1,O2).

The core of Deﬁnition 1 is that when an observer makes obser-

vations, e.g., access the data of the RF or measure the execution of

JavaScript, the observer cannot obtain additionally timing informa-

tion other than what it has already known. In other words, based

on the observations in the RF, the observer can directly deduce the

timing, e.g., t2−t1, without looking at the clock in the RF.

For the purpose o f explanation, let us look at one toy example of

deﬁning deterministic RFs. Speciﬁcally, the RF clock ticks based on

the following rule: Every time an integer variable xis incremented

by 1, the clock ticks by an atomic unit. This RF is deterministic be-

cause the clock is directly deﬁned as a function of a variable, i.e., an

observation that the observer can make. As we can expect, this RF

can prevent timing attacks (assuming that external clocks are han-

dled by Deﬁnition 2 below). However, because the clock may not

tick if the observer does not increment it, browser functionalities

will be broken.

Beside the internal clock, an observer can also obtain other clocks

via RF communication. So we deﬁne a deterministic communica-

tion in Deﬁnition 2.

Definition 2. (Deterministic Communication) Given two

RFs (RF r e ce i ve r , a deterministic RF, and RF se nder , another RF) and

an observer (Ob) in RFr e ce i ve r , we deﬁne the communication from

RF s ender to RF r e ce i ve r as deterministic if and only if either of the

following holds:

(1) When th e Ob from RFr e ce i ve r makes an observation in RFsend e r

at the timestamp tr e ce iv e r in RF r e c ei v er (i.e., a communication

from RF sende r to RFr ec e iv e r happens), at that moment, the times-

tamptsende r in RFse nd e r equals to tr e c e iv er (tse nd e r =tr e ce i ve r );

(2) RF s ender is deterministic.

Deﬁnition 2 gives two conditions for a deterministic communi-

cation between a sender and a receiver, i.e., either (1) two clocks are

synchronized or (2) both RFs are deterministic. Note that in order

to synchronize two clocks (i.e, the ﬁrst condition), it is required

that the clock in the receiver is behind the one in the sender so

that when the communication message from the sender arrives, the

message can be delayed until the receiver reaches the time. Later in

Section 5, we will show that such condition can be easily achieved

by adjusting parameters in the clock of the receiver and putting

the so-called placeholder in the event queue of the receiver.

Now let us look at and prove Lemma 1 that connects Deﬁnition 1

and Deﬁnition 2.

Lemma 1. A deterministic RF remains deterministic after commu-

nicating with other RFs, i.e., following Deﬁnition 1, if the communi-

cation obeys Deﬁnition 2.

Proof. See Appendix A for proof. 

Now we can show our important theorem about determinism,

i.e., Theorem 1.

Theorem 1. (Determinism prevents timing attacks) If a RF

with a target secret is deterministic, an adversary observer—no mat-

ter in this RF or another RF—cannot infer the target secret.

Speciﬁcally, if the observer measures the ending and starting times-

tamps (tEnd and tS t ) of the target secret, the following holds: ∆t=

tEnd −tS t =const.

Proof. See Appendix B for proof. 

Theorem 1 says that the observer will always obtain the same

timing information when measuring the target secret. Speciﬁcally,

determinism normalizes the target secret so that the delta between

the ending and starting timestamps of the target secret, from the

viewpoint of an observer, is always the same, i.e., deterministic,

even if the target secret happens multiple times in diﬀerent run-

time environments. In other words, we prove that determinism pre-

vents timing attacks.

4 REFERENCE FRAMES

In this section, we will introduce how to make RFs in current browsers

deterministic. The ideal yet simple solution is to make every RF de-

terministic, but such solution is impossible in some scenarios. For

example, a network message may contain the information about

the physical clock, and there is no way to make such RF determin-

istic (as it belongs to the external world). The good news is that

according to Theorem 1, we only need to make RFs with target se-

crets deterministic to prevent timing attacks. Now let us look at

several examples of RFs.

4.1 JavaScript Main RFs

JavaScript main RF needs to be deterministic because the perfor-

mance of JavaScript execution as shown in Figure 1 is a target se-

cret to the JavaScript itself. In this subsection, we start from some

background knowledge, present our core deﬁnition of a determin-

istic JavaScript RF, and then use Figure 1 as an example to show

how timing attacks are prevented.

4.1.1 Background. To execute a JavaScript program, a browser—

particularly the JavaScript engine part—will parse and convert the

JavaScript program into a special form called operation code (op-

code), sometimes referred as bytecode as well. Then, depended on

the execution mode, i.e., interpreter or just-in-time ( JIT) compila-

tion, the opcode will be interpreted or converted to machine code

for execution.

Note that although the deﬁnition of opcodes is speciﬁc to the

type of the browser, such as Firefox and Google Chrome, deter-

minism can be associated with any set of opcodes. In our proto-

type implementation, we modiﬁed Firefox browser and thus used

the deﬁnition of opcodes in SpiderMonkey, the Firefox JavaScript

engine.

4.1.2 Deterministic JavaScript RF. We will give an alternative

deﬁnition of determinism in JavaScript RF in Deﬁnition 3. This al-

ternative deﬁnition for JavaScript is similar to the special deﬁni-

tion [48] that researchers used in lower level, such as virtual ma-

chines. We will then use Theorem 2 to show that this deﬁnition

is equivalent to our general determinism deﬁnition of RFs (Deﬁni-

tion 1) in the context of JavaScript engine.

Definition 3. (Deterministic JavaScript RF) Given a set of

opcodes (SO ) generated from a program, a ﬁxed initial state, and

a set of ﬁxed inputs, a JavaScript RF is deterministic if and only if

the followings hold for any two executions (E1and E2) on diﬀerent

runtime environments:

For every opcode (op ∈SO ) in E1and E2,t1

op −t2

op =C, where

op is the timestamp when the opcode op is executed in Ek, and Cis

a constant related to only the starting time of E1and E2.

Theorem 2. (Determinism Deﬁnition Equivalence) In the

context of JavaScript engine, Deﬁnition 3 is equivalent to Deﬁni tion 1.

Proof. See Appendix C for proof. 

Now let us look at Deﬁnition 3, which says that JavaScript op-

erations in diﬀerent executions of a deterministic RF will follow

a determined distribution pattern over time axis when inputs are

ﬁxed and span over time in a ﬁxed pattern. That is, if one makes

a translation from one execution to the starting point of another,

the two executions look the same.

There are two methods to ﬁx the execution pattern for JavaScript.

First, one intuitive method is to still use physical clock in this

RF but arrange the opcode execution sequence following a pre-

determined pattern. However, such arrangement will slow down

a faster execution, and cannot make up for a slower execution (as

the clock does not wait for a slower execution).

Second, what is being used in this paper is that instead of chang-

ing the execution, we change the clock in this RF so that the per-

ceived execution pattern from the viewpoint of the observer, i.e.,

the JavaScript program, is ﬁxed, although we, such as oracle users

knowing the physical time, see the execution pattern diﬀerently.

4.1.3 An Example of Deterministic JavaScript RF. Given Deﬁni-

tion 3, there are many possible clock deﬁnitions in deterministic

JavaScript RFs, which have no diﬀerences from the perspective of

preventing timing attacks. Now, considering simplicity and perfor-

mance overhead, we deﬁne a speciﬁc clock used in our implemen-

tation, which ticks based on the following criteria:

(i) When there are opcodes running, the clock ticks with regards

to the executed opcode. That is, we have the following equation,

tnow =ts t ar t +Íop ∈E J O unitop , where EJO is the set of executed

JavaScript opcodes and unitop is the atomic elapsed time for that

opcode. For simplicity, if we normalize unito p as unit , we will have

Equation 1.

tnow =ts t ar t +countE J O ×unit (1)

(ii) When there are no opcodes running, the clock can tick based

on any criterion, because there is no target secret in the JavaScript

RF—as JavaScript is not executing—and more importantly no ob-

server in the JavaScript RF measuring target secrets. One can con-

sider a JavaScript RF in this state as a blackbox that no observers

know what happens inside (thinking about Schrödinger’s cat). The

key for such state is that when another RF communicates with the

JavaScript RF, we need to synchronize clocks in both RFs (Deﬁni-

tion 2). The reason is that when there exists communication, e.g.,

when a callback is invoked, an observer will be present. We will

discuss more details about the communication in Section 5.

The aforementioned clock makes JavaScript RF deterministic.

Assume that we have two executions of the same JavaScript at

st a r t and t2

st a r t separately. For an arbitrary opcode op, we will

have t1

op −t2

op =(t1

st a r t +countE JO ×unit ) − (t2

st a r t +countE JO ×

unit )=t1

st a r t −t2

st a r t =C, thus satisfying Deﬁnition 3.

4.1.4 Preventing the Synchronous Attack in Figure 1. Now let us

use Figure 1 to discuss how the synchronous attack (Line 1–21) is

prevented in JavaScript main RF. For the simplicity of explanation,

we assume that one JavaScript statement will form into one opcode.

In this case, the return value of the next Edдe function (Line 1–6)

is always 1, because for each JavaScript statement (Line 4–6), the

clock of the JavaScript RF will tick forward by unitop , the unit time

for an opcode. Then, start is not equal to pe r f ormance .now() at

Line 6, and the function just returns 1 at Line 7. For JavaScript

ﬁngerprinting, the f inдer print is ﬁxed as 1 (Line 11). For a side-

channel attack, there is only one op code between Line 16 and Line

18. Therefore, stop −st ar t equals unitop, and f inдe rpri nt −remain

equals 0, which makes dur ation as a constant number, i.e., unitop .

4.2 Auxiliary RFs

In this part of the section, we discuss how to make auxiliary RFs

deterministic. Similar to JavaScript main RF, an auxiliary RF needs

to be deterministic if it has a target secret. Now let us look at sev-

eral examples of auxiliary RFs. Note that this is an illustration but

not a complete list. Just as what Tor Browser [4] and Fermata [26]

did to add noise at various places, we also need to investigate the

same places (RFs) in browser and make them deterministic.

4.2.1 DOM Auxiliary RF. A DOM auxiliary RF is attached to a

JavaScript main RF: Such RF is created by the invocation of DOM

operation via JavaScript and destroyed when the DOM operation

ﬁnishes. We need to make DOM auxiliary RF deterministic, be-

cause the execution time of a DOM operation can be used to infer

the size of the resource involved in the operation [45]. The clock

in a DOM auxiliary RF will inherit from the JavaScript one, when

the DOM RF is created by the JavaScript. Then, the clock in the

DOM auxiliary RF will tick for a constant time, i.e., when the DOM

operation returns—no matter synchronously via a function call or

asynchronously via an event, the clock is incremented by a con-

stant time. Note that when there is no communication between

DOM and JavaScript, because there are no observers, the clock in

the DOM RF is in a uncertain state.

4.2.2 Networking Auxiliary RF. A networking auxiliary RF is

also attached to the JavaScript main RF. Networking auxiliary RFs

are created by an HTTP request, and destroyed by an HTTP re-

sponse, both initiated from the JavaScript main RF. Networking

auxiliary RF is deterministic for cross-origin requests, but remains

non-deterministic for same-origin ones. The reason is as follows.

If a request is from cross origin, the initiator, i.e., the JavaScript,

can infer the size of the response based on the time of processing

the response [45]. That is, the networking RF contains a target se-

cret. Speciﬁcally, the clock in such RF always ticks for a constant

time between the request and the response. As a comparison, if a

request is from the same origin as the JavaScript, the JavaScript by

any means has access to the response, i.e., there is no target secret

in the RF. Because an external server may embed the physical time

in the response, we will let the clock in same-origin networking

RF tick based on the physical time. Note that the communication

between same-origin networking and JavaScript RFs is still deter-

ministic per Deﬁnition 2 so that the JavaScript RF cannot obtain

the physical time.

4.2.3 Video Auxiliary RF. Video auxiliary RF is created when a

JavaScript renders a video on an HTML5 canvas as an animating

texture. According to Kohlbrenner and Shacham [26], such video

rendering can be used as an implicit clock via reques tAnimationF r ame,

because most modern browsers render video in a 60Hz frequency.

That is, one can infer the physical time based on the current dis-

played video frame. We do not need to make a video RF determin-

istic, i.e., the clock in such RF ticks based on physical time, because

it contains no target secrets. Note again that the communication

between the video auxiliary and other deterministic RFs is still de-

terministic.

4.2.4 WebSpeech or WebVTT Auxiliary RF. WebSpeech and We-

bVTT are another two venues of implicit clocks in the modern

browsers as mentioned by Kohlbrenner and Shacham [26]. A Web-

Speech RF with a SpeechSynthesisUtt erance object is created by

aspeak() method, and destroyed by a cancel() method which ﬁres

a callback with a high resolution duration of the speech length. A

WebVTT is a subtitle API that can specify the time for a speciﬁc

subtitle and check for the currently displayed subtitle. Similar to

the video auxiliary RF, because there are no target secrets, both RFs

are non-deterministic and the clocks in these two RFs tick based

on the physical time.

5 COMMUNICATION BETWEEN RFS

In this section, we discuss, when one RF communicates with an-

other, how to synchronize clocks according to Deﬁnition 2. Before

explaining our technique, i.e., a priority queue, we ﬁrst need to

understand how the RF communication works in legacy browsers.

The RF communication is handled by a so-called event loop [1],

in which a l oop keeps fetching events from a q ueue structure called

event queue. Let us again use se tT imeout to explain the RF commu-

nication with the event queue. When the main RF calls setT imeout ,

the main RF will dispatch an event into the event queue of the timer

RF, i.e., launching a communication from the main RF to the timer

RF. The timer RF will fetch the event, process it (i.e., waiting in this

example), and then dispatch another event, called a callback, back

to inform the main RF the completion of setT imeout , i.e., launching

a communication from the timer RF to the main RF.

Main Reference

Frame

t t+t’ t+t’+t’’

normal

event

placeholder

physical

clock holder

Case 1: clock

fast forward

Case 2:

process

Case 3:

pause

Case 4:

wait

Priority Queue

Figure 2: Mechanism of Priority Queue in the Main RF.

In our paper, we replace the event queue in the main RF with

a priority queue. Speciﬁcally, we reserve a callback place in the

queue for events that the main RF dispatched to other RFs. When

the callback is dispatched back to the main RF, the callback is syn-

chronized at the reserved place following Deﬁnition 2. Take a de-

terministic auxiliary RF for example. The duration of processing

an event in such RF always equals to a ﬁxed value from the per-

spective of the main RF observer. To achieve that, the main RF pre-

assigns an expected delivery time for every callback as a priority in

the queue so that the callback will be only delivered at that speciﬁc,

ﬁxed time from the viewpoint of the main RF observer. One impor-

tant property of this priority queue is that when multiple events

happen in many deterministic RFs, the queue will arrange all the

callbacks in a pre-determined, ﬁxed sequence. Now let us look at

the details.

5.1 Priority Queue

Now let us look at how the main RF interacts with the priority

queue. Similar to the current event model, when the main RF is

idle, it will try to fetch an event from the queue. In our model, the

event with the highest priority, i.e., the one with the earliest deliv-

ery time, will be returned to and processed by the main RF. There

are two sub-scenarios (Case 1&2 in Figure 2) here. First, when the

expected delivery time is ahead of the clock in the main RF (called

the main clock), the browser kernel will move the main clock to

the expected time, and let the main RF process the event. Second,

when the expected delivery time is behind the clock in the main

RF (i.e., the main RF was processing other events at the expected

delivery time), the main RF will directly process the event without

changing the clock.

Note that both cases follow the deterministic deﬁnition of com-

munication in Deﬁnition 2. For Case 1, because two clocks are syn-

chronized at the delivery time, the communication is determinis-

tic. For Case 2, we can consider that the event is delivered at the

expected delivery time following Deﬁnition 2. However, because

JavaScript is a single-thread language, the main RF cannot process

the event when busy. That is, the main RF has to postpone the pro-

cessing of the event to the time when it is idle. Thus we can com-

bine the delivery and the processing, because even if the event is

delivered, the main RF cannot notice and process the event.

Besides normal events, there are two special events (Figure 2):

an event placeholder and a physical clock holder. An event place-

holder is a virtual slot indicating that a real event should be at this

place in the queue, but the event has not been ﬁnished in the aux-

iliary RF. When the main RF fetches an event placeholder (Case 3),

the main RF needs to pause its own clock and wait until the event

arrives or is canceled (e.g., timeout). If the event arrives, it will re-

place the event holder, and the main RF will process the event; if

the event is canceled, the main RF will process the next event in

the queue.

A physical clock holder is a mapping from the current physical

time to the main RF clock time. Because the physical clock keeps

ticking, the place of the holder also changes, i.e., the priority of

the holder will be lowered constantly. The usage of such holder is

two-fold. First, when an auxiliary RF with the physical time tries

to communicate with the main RF, the browser kernel will add the

event to the holder’s place in the queue. Second, in a very rare case

(Case 4), when the main RF tries to fetch the physical clock holder,

i.e., the main clock ticks faster than the physical one, the browser

kernel will pause the main RF until the main clock is behind the

physical one. The reason is that an event with physical time can

come at any time, and if the main clock is faster, the browser kernel

cannot synchronize the main clock with the physical one. To pre-

vent such scenario, we can set the unit in Equation 1 to a very small

number so that the main clock cannot catch up with the physical

one in the fastest machine.

5.2 RF Communication

We now look at how the priority queue can be used in the commu-

nication between RFs.

5.2.1 Main and Auxiliary RF Communication. Let us ﬁrst look

at the communication between main and auxiliary RFs. First, say

the auxiliary RF is deterministic, and Figure 3 shows how it works.

Before creating such auxiliary RF, the main RF ﬁrst put a place-

holder in the priority queue (Step 1). Because the auxiliary RF is

deterministic, the main RF can predict the expected delivery time.

Then, the auxiliary RF is started (Step 2) and keeps running until

it ﬁnishes and tries to deliver an event to the main RF. The event

will be put in the priority queue, replacing the previous placeholder

(Step 3). At the expected delivery time in the scale of the main clock,

the event is delivered to the main RF (Step 4). If the main RF is busy,

the execution might be delayed (Step 5). As mentioned, if the exe-

cution is delayed, the main RF can fetch the event at the delayed

time.

Second, say the auxiliary RF is non-deterministic. Examples of

such RFs include these created by the main RF (e.g., same-origin

networking RF) and these created by the user (e.g., mouse or key-

board RF). When such RF is created, because we cannot predict the

expected delivery time, no placeholder is created. If the auxiliary

RF tries to communicate with the main RF, i.e., an event is ﬁred,

the event will be put at the place of the physical clock holder in

the priority queue.

5.2.2 Communications between Two Main RFs. We then discuss

how two main RFs communicate with each other using the priority

queue, which follows Deﬁnition 2. There are two scenarios in this

communication: (i) the sender’s clock is ahead of the receiver, and

(ii) the sender’s clock is behind. First, when the sender’s clock is

ahead, the browser kernel can put the communication message,

i.e., an event, in the priority queue at the position of a future time.

Main Clock t

(4) deliver the event

(1) create a

placeholder

(2) start auxiliary

reference frame

(3) replace the

placeholder with

the real event

Auxiliary Clock

(5) execute the event

potential

delay

Priority Queue

Figure 3: Communication between Main and Auxiliary RFs.

Then, when the event is executed, two clocks are synchronized—

everything is the same as the communication between a main and

auxiliary RF, and follows the ﬁrst condition in Deﬁnition 2.

Second, when the sender’s clock is behind, the browser kernel

will put the communication event in the front of the priority queue,

i.e., deliver the event immediately. In such case, the receiver knows

two clocks, i.e., the sender’s and its own. Let us ﬁrst consider that

the sender has a target secret, i.e., the sender’s RF is deterministic.

In such case, the communication follows the second condition in

Deﬁnition 2.

Let us then consider that the sender’s RF contains no target se-

crets and is not deterministic. An example is that the main RF is not

running JavaScript and just gets synchronized with an auxiliary RF

with a physical clock. Such case contradicts with our assumption

in the beginning that the sender’s clock is behind the receiver’s, be-

cause as shown in Section 5.1, relying on the physical clock holder,

the clock in a deterministic main RF, i.e., the one in the receiver,

is always behind the physical clock. Therefore, the scenario boils

down to our ﬁrst case, where the sender’s message is put in the

priority queue, and both clocks are synchronized.

5.3 Preventing the Asynchronous Attack in

Figure 1

Now let us look at how the priority queue can help to prevent

the asynchronous attack (Line 22–28) in Figure 1. In one sentence,

when the adversary measures the duration of the asynchronous

target secret using the reference clock (i.e., set Inte rv al in this ex-

ample), no matter how long the target secret takes to ﬁnish, the

adversary will always obtain a ﬁxed, deterministic value.

Here are the details. In the sideChannelAsync function, when

the asynchronous t arget secret is invoked in function tarдetS ecre tAsync

(Line 26) say at ti nit , the browser kernel will put an event place-

holder in the priority queue with an expected delivery time, say

at td, and create a deterministic RF to execute the asynchronous

secret. That is, td−ti ni t is a constant due to determinism. Next

when the set Inte rv al function is invoked, the browser kernel will

create another RF for waiting and put an event placeholder in the

priority queue with an expected delivery time at ti nit +uwhere

uis the variable at Line 27. Because the implicit clock introduced

by set I nt erval is to measure tarдetSecretAsync,ushould be much

smaller than td−ti nit . That is, the event placeholder for set I nt erval

should be ahead of the one for the target secret in the priority

queue. Therefore, function countFunc (Line 23) is executed, and

then another event placeholder for set I nterval is created. After

count Func is executed for r ound ((td−ti nit )/u)times, the callback

for the target secret, i.e., callback, is executed. Note that if the tar-

get secret ﬁnishes execution, the placeholder for the target secret

is replaced by the callback, which can be executed immediately;

if not, the JavaScript RF will wait there for the placeholder to be

replaced by the callback.

In sum, we have three RFs in this example: JavaScript RF, DOM

RF for setT imeout, and a deterministic RF for executing the target

secret. The duration measured by cal lb ack is always round((td−

tin it )/u) ∗ u, a deterministic value. Therefore, the asynchronous

attack is prevented.

6 IMPLEMENTATION

We have implemented a prototype of deterministic browser called

DeterFox with 1,687 lines of code by modifying Firefox nightly

51.0a1 at 40 diﬀerent ﬁles. The implementation is available at this

repository (https://github.com/nkdxczh/gecko-dev/tree/deterfox). Let

ﬁrst look at the implementation RFs. As mentioned, legacy Firefox

already has RF implementations via OS level threads (xpcom/thread-

s/nsThread.cpp). Diﬀerent RFs are diﬀerent subclasses of nsThread,

such as TimerThread (xpcom/threads/TimerThread.cpp). Now we

introduce the core part of our implementation: deterministic JavaScript

RF and priority queue.

Let us ﬁrst look at the deterministic JavaScript engine (js/src).

We associate a counter with each JavaScript context in SpiderMon-

key, the Firefox JavaScript engine of Firefox. When per f ormance .now

is invoked, the counter multiplying a unit time will be returned.

Note that some Firefox scripts, e.g., these with “chrome://” and “re-

source://” origins, are also running in the same context as JavaScript

from the website. We create separate counters for such Firefox

scripts. Here is how the counters are incremented. Speciﬁcally, Spi-

derMonkey has three modes of executing JavaScript code, one in-

terpreter (js/src/vm/Interpreter.cpp) and two just-in-time ( JIT) com-

pilation modes (IonMonkey at js/src/jit/Ion.cpp and BaselineJIT

at js/src/jit/BaselineJIT.cpp). We increment the counter in all the

three modes. In the interpreter mode, the counter will be incre-

mented for each opcode; in both JIT modes, the counter will be

incremented based on the compiled JavaScript block. Our current

implementation does not add the counter in the compiled code

directly but before and after the compiled code execution. Note

that this implementation is still deterministic, because it makes the

JavaScript execution follow a certain pattern over time.

We then change the event queue for the deterministic commu-

nication. For each thread in Firefox, other threads can dispatch a

runnable to that thread and put (PutEvent method in xp com/thread-

s/nsThread.cpp) the runnable in the event queue (mEventsRoot

object in xpcom/threads/nsThread.cpp). Note that there are many

queues in Firefox, and these queues are sometimes hierarchical, i.e.,

one queue may dispatch events to another queue. This event queue

that we talk about is directly asso ciated with a thread, i.e., the inner

level queue.

7 EVALUATION

We evaluate DeterFox based on the following metrics:

Table 1: Robustness of Five Browsers against Diﬀerent At-

tacks. (“Clock-edge” [26]; “Clock-edge-m”: an modiﬁed ver-

sion of “Clock-edge”; “Img (S)”: the image loading side-

channel attack [45] inferring two ﬁles with Ssize diﬀerence;

“Script (S)”: the script parsing side-channel attack [45] infer-

ring two ﬁles with Ssize diﬀerence; “Script-implicitClock

(2M)”: a modiﬁed version of “Script (2M)” using setInterval as

an implicit clock; “Cache attack”: a side-channel attack [38];

“Cache-m”: a covert channel modiﬁed from “Cache attack”;

“SVG Filtering”: the SVG ﬁlter attack from Stone [44].)

Chrome Firefox Tor Browser FuzzyFox DeterFox

Clock-edge [26] × × × X X

Clock-edge-m × × × × X

Img (100K) [45] × × X X X

Img (5M) [45] × × × × X

Script (100K) [45] × × X X X

Script (2M) [45] × × × × X

Script-implicitClock (2M) × × × × X

Cache attack [38] × × X X X

Cache-m × × × × X

SVG Filtering [44] × × × × X

Note: Xmeans the browser is robust to the attack, and ×not.

•Robustness to timing attacks. We evaluate DeterFox and other

existing browsers including commercial ones and research pro-

totype against existing timing attacks presented in the litera-

ture.

•Performance overhead. We evaluate the performance overhead

of DeterFox from the perspective of a user of the browser, i.e.,

based on the physical time obtained from a standard Linux ma-

chine.

•Compatibility. We evaluate the compatibility of DeterFox us-

ing two tests: an automated browser testing framework called

Mochitest, and the rendering of Top Alexa websites.

7.1 Robustness to Timing Attacks

In this part of the section, we evaluate the robustness of exist-

ing browsers and DeterFox against timing attacks. Formal proof

about why a deterministic browser prevents timing attacks can

be found in Theorem 1. In this subsection, we focus on the em-

pirical evaluation of DeterFox and other prior arts against tim-

ing attacks presented in the literature. Speciﬁcally, four existing

browsers—namely Firefox, Google Chrome, FuzzyFox [26],4and

Tor Browser [4]—are used for comparison, which range from com-

mercial browsers to research prototype. An overview of the evalu-

ation can be found in Table 1.

7.1.1 Clock-edge Attack. A synchronous version of the clock-

edge attack [26] is presented in Section 2. Apart from that ver-

sion, we also design another version speciﬁcally targeting Fuzzy-

Fox. The modiﬁed version runs an operation for a considerable

long time and calculate the diﬀerence between t woper f ormanc e.now

asynchronously. The attack is repeated for ten times to average out

the jitter added by FuzzyFox. Additionally, because two per f or mance .now

are obtained asynchronously, they do not equal to each other ac-

cording to the FuzzyFox paper.

4FuzzyFox is a prototype implementation of Fermata, and we use the version down-

loaded from their repository with the default parameters.

0 5 10 15 20

Size (MB)

500

1000

1500

2000

Time (ms)

DeterFox

Firefox

FuzzyFox

Tor Browser

Chrome

Figure 4: Script Parsing Attacks from Goethem et al. [45]

(We change the size of parsed scripts in the attack, and mea-

sure the time to trigger an “onerror” event. Each point in the

graph is the median value of nine repeated tests. Note that

all timestamps are obtained via JavaScript.)

The ﬁrst two rows of Table 1 shows the results of both the orig-

inal and modiﬁed version of the clock-edge attack. All browsers

except DeterFox and FuzzyFox are vulnerable to the original ver-

sion, i.e, the minor clock can be used to measure a target secret

with µs accuracy. Both DeterFox and FuzzyFox will show a con-

stant time for the minor clock, making it unusable for measure-

ment of target secrets. For the modiﬁed version, all browsers ex-

cept DeterFox are vulnerable. We also test ﬁve browsers on the

clock-edge attack for the ﬁngerprinting purpose (see Section 2),

and the results are the same as the one for the measurement pur-

pose.

7.1.2 Side-channel Attacks from Goethem et al [45]. We evalu-

ate the robustness of browsers against two side-channel attacks

from Goethem et al. [45], namely script parsing and image loading.

Both attacks try to load a ﬁle—which is not image or script and

from a diﬀerent origin—and measure the time between the start

and when the “onerror” event is triggered. Details can be found in

their paper.

In the evaluation, we change the ﬁle size from 1MB to 20MB

and observe the loading or parsing time. The experiment for each

ﬁle size is repeated for 15 times, and we discard the ﬁrst six results,

because the browser is sometimes busy loading system ﬁles during

startup, which aﬀect the result. Then, we obtain the median value

of the rest nine results for each ﬁle size and show the result in Fig-

ure 4 and 5. Note that the ﬁle size we use is larger than the one in

Goethem et al. [45], because both FuzzyFox and Tor Browser add

noises to the loading or parsing time so that it is hard to diﬀer-

entiate ﬁles with small sizes. However, the ﬁle size that we use is

still reasonable for normal web communications, such as for email

attachment. Now let us look at the results for script parsing and

image loading separately.

Figure 4 shows the results of script parsing attack for ﬁve browsers.

First, the parsing time for DeterFox is a constant, deterministic

number, i.e., DeterFox is entirely robust to the script parsing at-

tack. Second, the parsing time for both legacy Firefox and Google

Chrome is linear to the ﬁle size, conﬁrming the results reported by

5000

10000

15000

20000 DeterFox

Firefox

Fu yFox

Tor

Browser

Chrome

200

400

600

800

1000

1200

1400

1600

Time (ms)

0 5 10 15 20

Si e (MB)

Figure 5: Image Loading Attacks from Goethem et al. [45]

(We change the size of parsed scripts in the attack, and mea-

sure the time to trigger an “onerror” event. Each point in the

graph is the median value of nine repeated tests. Note that

all timestamps are obtained via JavaScript.)

Goethem et al. Lastly and more importantly, the parsing time for

both Tor Browser and FuzzyFox is a stair step curve with regards

to the ﬁle size. That is, both browsers can defend against such pars-

ing attack in small scale when the ﬁle sizes diﬀer a little, but fail

when the ﬁle sizes diﬀer a lot, e.g., with 2MB diﬀerences (Table 1).

Figure 5 shows the results of image loading attack for ﬁve browsers.

First, similarly the loading time for DeterFox is a constant, show-

ing that DeterFox is robust to such image loading attack, and both

legacy Firefox and Google Chrome are vulnerable to the attack be-

cause the loading time increases as the ﬁle size linearly. Second,

the parsing time for FuzzyFox is still a stair step curve with a few

ﬂuctuations. That is, FuzzyFox is also vulnerable to such attack

if the ﬁle size diﬀers much, e.g., with 5MB diﬀerences (Table 1).

Lastly, the loading time for Tor Browser is interesting, because the

time stays as a constant number when the ﬁle size is below 4MB,

but increases linearly when the ﬁle size is above 5MB. That is, Tor

Browser is also vulnerable to the attack when loading a large ﬁle.

Note that in addition to u singper f ormance .now to measure the

loading time, following the asynchronous attack in Figure 1, we

also tried set Interv al as an implicit clock for the script parsing at-

tack with 2M ﬁle size diﬀerence. The result (“Script-implicitClock

(2M)” line in Table 1) shows that only DeterFox can defend against

the attack with the setI nt erval implicit clock—this is expected as

only DeterFox can defend against the original script parsing at-

tack with 2M ﬁle size diﬀerence.

7.1.3 Cache Attacks from Oren et al [38]. Oren et al. [38] pro-

pose a practical cache-based side-channel attack using JavaScript,

which can correctly recognize the website running in another tab

by creating a memory access pattern with zeros and ones called

memorygrams. We re-implement their attack and test all ﬁve browsers

against the attack. As shown in the seventh row of Table 1, both

Chrome and Firefox are still vulnerable, but Tor Browser, FuzzyFox,

and DeterFox are robust, i.e., the memorygrams in these three

browsers are all zero. Note that although Tor Browser was vulner-

able, people have patched Tor Browser to defend against this attack

by further reducing the time resolution.

Table 2: Measured Time to Perform an SVG Filter (All the

numbers are in ms and averaged from 20 experiments).

Chrome Firefox Tor Browser FuzzyFox DeterFox

200×200 image 16.66 17.01 18.94 109.09 192

1920×1080 image 17.87 50.35 106.67 114.54 192

Because both Tor Browser and FuzzyFox only limit the band-

width of the side/covert channel, we create a modiﬁed version to

show that a covert channel is still possible (the eighth row of Ta-

ble 1). Speciﬁcally, we create two iframes from diﬀerent origins

that talk to each other based on the cache attack for a long time.

The results show that if the attack lasts for two minutes, the re-

ceiver in both Tor Browser and FuzzyFox can successfully diﬀeren-

tiate the one-bit information. That is, the channel still exists with

signiﬁcantly reduced bandwidth in both Tor Browser and Fuzzy-

Fox.

7.1.4 SVG Filtering Attacks from Stone [44]. Stone shows that

the performance of SVG ﬁlter can be used to diﬀerentiate the con-

tents of images. We apply the feMorphology SVG ﬁlter mentioned

in the Stone’s paper [44] to perform an erode operation upon two

images, one with size 1920×1080 and another with size 200×200,

and measure the op eration time using requestAnimationF r ame. Both

images are generated randomly with a mixture of RGB colors and

we perform the attack for 20 times.

The last row of Table 1 shows the summary results of the attack.

All other browsers except DeterFox are vulnerable, i.e., the mea-

sured operation time for the large (1920×1080) image is constantly

longer than the small one (200×200) as shown in Table 2. Based

on the results, an adversary can diﬀerentiate whether an cross-

origin image is a thumbnail or full-sized. By contrast, DeterFox

can defend against the attack—i.e., no matter how large the image

is, the operation time is always the same from the viewpoint of the

JavaScript observer. (The user can still tell the diﬀerence and will

not experience the slowdown as in FuzzyFox and Tor Browser.)

7.2 Performance Overhead

We ﬁrst evaluate the performance of Det erFox by JavaScript bench-

mark and Top 100 Alexa websites. Then, we discuss the evaluation

results.

7.2.1 JavaScript Benchmark. We ﬁrst evaluate the performance

overhead of DeterFox using a JavaScript performance test suite

called Dromaeo [2], a uniﬁed benchmark from Mozilla. Each test

in Dromaeo is executed for at least ﬁve times and maybe up to ten

times if a signiﬁcant level of error cannot be reached. Next, the

results are ﬁt into a t-distribution to calculate the 95% conﬁdence

interval. Note that because we changed the clock in DeterFox, all

the timestamps used in the experiment are based on the local time

of a Linux machine instead of the JavaScript time.

Figure 6 shows the evaluation results with the median overhead

of DeterFox as 0.63% and the maximum as 1% when compared

with the legacy Firefox of the same version. That is, the overhead

introduced by DeterFox is almost ignorable in terms of JavaScript

performance when observed by an oracle. In three of the test cases,

DeterFox is even slightly faster than Firefox because DeterFox

does not invoke any system calls during per f orm ance.now, but

11.0

11.5

12.0

12.5

13.0

DeterFox

Firefox

3D Mesh Transform

3D Raytra e

AES En rypt

/De rypt

Arrays Base

64 En/De ode

Bitwise And

Code Evaluation

Compute Bits in Byte

Compute Bits

(2)

DNA Sequen e Align

DNA Sequen e Count

Date Format

Date Format(2)

DeltaBlue Constraint

Fannku h

MD5 N

-Body Rotate/Gravity

Partial Sum

Prime Number

(2)

RSA En rypt/De rypt

RayTra er

Re ursive Number

Regular Expressions

Ri hards Ben hmarks

Rotating 3D Cube

SHA

1S ript

Unpa k

Spe tral Norm

(Matrix)

String Parse

/Sear h

Strings Tag

Cloud Create

Travers Binary Trees

Trigonometri

Validate User Input

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Time (ms

)

Figure 6: JavaScript Performance Benchmark Evaluation. (The median overhead of DeterFox is 0.63%, and note that all times-

tamps are obtained based on a standard Linux machine.)

0 10 20 30 40 50

Time (ms)

100

Percentage (%)

DeterFox

Firefox

Tor Browser

Fuzz Fox

Figure 7: Cumulative Distribution Function of Loading Time

of Top 100 Alexa Websites. (Note that all timestamps are ob-

tained based on a standard Linux machine. The median over-

head is 0.1%, i.e., there is no statistical diﬀerence between

Firefox and DeterFox. The x-axis is cut oﬀ at 50ms, be cause

some Top 100 Alexa websites are located in China and the

loading time is very long, e.g., 1–2mins, and more impor-

tantly the loading time of such websites are dominated by

the network latency, i.e., unrelated to the browser. )

legacy FireFox does. If the measured time is very small, the invo-

cation of pe r f ormance .now will inﬂuence the result. Another in-

teresting experiment is to disable the JI T mode for both DeterFox

and the legacy Firefox and test the performance overhead to show

the inﬂuence of the added counter. The results show the median

overhead for the interpreter mode as 6.1%.

7.2.2 Top 100 Alexa Websites. Wet hen evaluate the performance

overhead of DeterFox against Top 100 Alexa websites. Speciﬁ-

cally, we measure the loading time of Top 100 websites in four

browsers and show the cumulative distribution function (CDF) of

the loading time.

Figure 7 shows the results of this experiment. The CDF curve

of DeterFox is very close to the one of legacy Firefox. The me-

dian overhead of DeterFox compared with legacy Firefox is 0.1%,

i.e., with no statistical diﬀerence. At contrast, both Tor Browser

and FuzzyFox incur a non-ignorable overhead. The reason is that

both Tor Browser and FuzzyFox add jitters causing a delays during

page loading, but DeterFox only adjusts the time in each RF, i.e.,

the time that JavaScript observes, while the user does not observe

similar overhead as JavaScript does.

7.2.3 Discussion. The overhead of DeterFox comes from two

parts: the counter and the priority queue. The counter brings over-

head because the incrementing behavior takes time. Further, the

overhead is small, because the incrementing behavior is very cheap.

The priority queue does not bring any overhead if there is only

one event waiting. When there are two (or more than two) events

in the queue, if the event—which DeterFox arranges behind the

other—comes ﬁrst, the arrangement will cause overhead. However,

in practice, as shown in Top 100 Alexa websites, this case is rare,

and even if it happens the other event will also come in a short

time, which bring little overhead for DeterFox.

7.3 Compatibility

We evaluate the compatibility of DeterFox from three perspec-

tives: Mochitest, rendering Top 100 Alexa websites, and behind-

7.3.1 Mochitest. Mochitest [3] is a comprehensive, automated

testing framework from Mozilla, and Mozilla will use Mochitest

to test Firefox before each release. The entire Mochitest that we

use from Firefox nightly 51.0a1 contains 878,556 individual tests

grouped into 41,264 categories, and will run for 8 hours on a stan-

dard Linux virtual machine [5] downloaded from Mozilla oﬃcial

website. Note that even the legacy Firefox cannot pass all the tests

on that virtual machine: Speciﬁcally, the legacy Firefox nightly

51.0a1 only passes 97.8% of tests—859,283 out of 878,556 as passed,

9,943 as OK, i.e., in their todo list, and 9,330 as failed.

Our evaluation results show that DeterFox passes 97.6% of tests,

i.e., 10,339 as failed, 10,358 as OK, and the rest as passed. We look

at these failed cases and ﬁnd that DeterFox fails additional 1,502

tests when compared with the legacy Firefox. Interesting, there are

493 tests that DeterFox passes but the legacy Firefox fails. One

possible reason is that DeterFox changes the sequence of events,

which may ﬁx some concurrency bugs caused by rendering se-

quence. We look into some of these cases that DeterFox fails, and

ﬁnd that they belong to many categories, such as DOM and layout.

7.3.2 Top 100 Alexa Websites. We evaluate the compatibility of

DeterFox by comparing the screenshot of DeterFox with the one

of legacy Firefox browser. Because modern websites contain many

ads, even two sequential visits to the same website may render dif-

ferently. Thus we manually look at these websites in which t he sim-

ilarity of the screenshots between DeterFox and Firefox is smaller

than 0.9 (A similar threshold to test browser compatibility is also

used in the literature [40]).

In total, 63 websites pass the initial test and we manually exam-

ine the rest 37. All the diﬀerences are highlighted automatically by

a red circle for manual inspection. The results show that all diﬀer-

ences are caused by dynamic contents, such as a diﬀerent ad and a

news update. In sum, DeterFox is compatible with Top 100 Alexa

websites, i.e., does not cause noticeable diﬀerences when rendering

the front page of these websites.

7.3.3 Behind-login Functionalities of Some Popular Websites. In

this subsection, we evaluate the behind-login functionalities of sev-

eral popular websites. Speciﬁcally, we choose the most popular

website, according to Alexa, from several website categories includ-

ing email, social network, online shopping, video, and JavaScript

game. Our manual inspection shows that we can successfully per-

form corresponding actions. Here are the details.

•Email: Gmail. We register a new account with Google, log into

Gmail, and then send an email with an attachment to another

email address. From a diﬀerent computer, we reply to this email

and attach another ﬁle in the reply. Then, from the ﬁrst com-

puter, we receive the reply, look at the contents, and then down-

load the attachment in the reply.

•Social Network: Facebook. We register a new account with Face-

book, and log in. Then, we conﬁgure several privacy settings

following Facebook’s tutorial, and add several friends. Next, we

post a status in Facebook by sharing a news. We also talk with

a friend via Facebook message.

•Online Shopping: Amazon. We register a new account and log

in. Then, we browse several items using the search functions

in Amazon. Next, we add a book to our shopping cart, proceed

to checkout, and purchase the book with a newly added credit

card.

•Video: Youtube. We log into Youtube with the Google account,

and search several keywords. Then, we select avideo, and watch

it for one minute. We also post a comment under the video, and

then delete the comment.

•JavaScript Game. We search the keyword “JavaScript Game" on

Google and click the ﬁrst JavaScript game in the list, i.e., the ﬁfth

item during our search. The JavaScript game is very similar to

gluttonous snake in which the gamer can control an item to eat

others. We play the game for one minute.

8 DISCUSSION

We discuss several problems in this section.

Access to Physical Time. One common misunderstanding of our de-

terministic browser is that JavaScript will lose access to the physi-

cal time. A deterministic browser only prevents JavaScript (an ob-

server) from accessing the physical clock when there is a secret

event running at the same time, because necessary conditions of a

timing attack involve an observer and a secret event (See Section 2);

at contrast, if there is no secret event execution, JavaScript has free

access to the physical clock. Speciﬁcally, the deterministic browser

kernel will fast forward the main clock in JavaScript to the phys-

ical one as discussed in Section 5. In practice, because JavaScript

is an event-driven language, if JavaScript is just waiting for one

single event with physical time, e.g., a network request from the

same origin, the main clock will be the same as the physical clock.

User-related Timing Attacks. As discussed in Section 2, our deter-

ministic browser, especially the current prototype DeterFox, does

not consider timing-related biometric ﬁngerprinting, i.e., the secret

event in our prototype is restricted to the browser itself. To defend

such biometric ﬁngerprinting that is related to time, we need to in-

troduce determinism into corresponding reference frames. For ex-

ample, the clock in a keyboard reference frame needs to tick based

on the number of pressed keys instead of the physical clock. This,

however, is considered as our future work.

External Timers and Observers. In real-world, external timers and

observers, e.g., these that reside outside a browser, are impracti-

cal as pointed out by the FuzzyFox [26] paper. Any timestamps

or observations provided via such methods are too coarse-grained

to perform any meaningful attacks. Therefore, neither FuzzyFox

nor Tor Browser considers external timers and observers in their

thread model. Theoretically, a deterministic browser can defend

against such attacks performed by external timers or observers,

because according to Deﬁnition 2, two RFs are synchronized dur-

ing communication. That is, when an external observer obtains the

time or an internal observer obtains an external time, the time is

out-of-dated, which only reﬂects the synchronized time.

9 RELATED WORK

In the related work section, we ﬁrst discuss existing timing attacks,

and then present prior work that mitigates such timing attacks,

especially browser-related ones.

9.1 Browser-related Timing Attacks

We discuss existing browser-related timing attacks below.

9.1.1 JavaScript Performance Fingerprinting. Mowery et al. [33]

and Mulazzani et al. [34] show that the performance of JavaScript,

i.e., how long a certain set of JavaScript code takes to execute, can

be used to diﬀerentiate, or called ﬁngerprint, diﬀerent types and

versions of web browsers. The reason behind such JavaScript per-

formance ﬁngerprinting is that diﬀerent browsers have diﬀerent

JavaScript engine implementations and thus diﬀerent runtime per-

formance behaviors.

9.1.2 Timing-based Side or Covert Channels. Timing attacks [23,

25, 32, 52, 53] in general have been studied for a long time. We fo-

cus on browser-related side or covert channels. Felten et al. [18]

ﬁrst point out that due to the existence of web content caching, the

loading time of external resource can be used to infer the browsing

history in the past. Then Bortz et al. [8] classify timing channels

into two categories: direct timing attacks that infer private infor-

mation stored at server side, and cross-site timing at tacks that infer

the size of a cross-site resource in the client browser. The former is

beyond the scope of the paper because the target secret is caused

by the server as discuss in Section 2; the latter is within the scope.

After that, Kotcher et al. [27] ﬁnd another timing attack, showing

that the time of rendering a document after applying a CSS ﬁlter

is related to the document’s visual content. Similarly, Goethem et

al. [45, 46] show that the parsing time of scripts and video can be

used to infer the size of the corresponding resource. Oren et al. [38]

and Gras et al. [20] show that lower-level caching attacks can be

launched from the JavaScript without privileged access.

9.2 Countermeasures of Timing Attacks

We now discuss existing countermeasures of timing attacks.

9.2.1 Browser-level Defense. Tor Browser [4] and Fermanta [26]

are the closest work to our deterministic browser. Tor Browser [4],

an industry pioneer in ﬁghting browser ﬁngerprinting, reduces the

clock resolution to 100ms, and adds noises at all places to mit-

igate the browser’s ﬁngerprintability. Similarly, Fermata [26] re-

duces the clock resolution and adds several pause tasks in the event

queue to reduce the resolution of implicit clocks. The main diﬀer-

ence with DeterFox is that existing works only limit the attacks’

capability, e.g., prolonging the attack or reducing the channel band-

width, but do not fundamentally limit the timing attack.

Another diﬀerence between Fermata and deterministic browser

is that Fermata requires that all synchronous JavaScript calls are

converted to asynchronous because Fermata adds jitt ers in the event

queue. Such drastic changes will not be backward compatible with

legacy JavaScript program and their implementation, i.e., Fuzzy-

Fox, does not support such changes.

9.2.2 System-level Defense (based on Determinism). Both Stop-

Watch [29, 30] and DeterLand [48] use determinism to prevent

lower-level timing side or covert channels. Their virtual time ticks

based on the number of executed binary instructions in the virtual

CPU. Similarly, Burias et al. [9] propose a deterministic information-

ﬂow control system to remove lower level cache attacks and then

Stefan et al. [43] show that such cache attacks still exist given a

reference clock. Aviram et al. [6] use provider-enforced determin-

istic execution to eliminate timing channels within a shared cloud

domain. Compared with all existing determinisms, apart from the

domain diﬀerence, i.e., browser v.s., lower level, the diﬀerences can

be stated from three aspects. First, the communication between the

virtual and outside world in existing approaches is non-deterministic,

i.e., they still add jitters or group event together to limit the band-

width of side or covert channels. Second, there is only one clock,

i.e., the virtual time, deﬁned in existing approaches, while our work

introduces many clocks in diﬀerent RFs.

9.2.3 Language-based Defense. Many language-based defense [22,

41, 42, 47, 50, 51] have been proposed to provide well-typed lan-

guage that either provably leaks a bounded amount of information

or prevents timing attacks fundamentally. Though eﬀective, such

approaches face backward compatibility problem, i.e., all the exist-

ing programs need to be rewritten and follow their speciﬁcations.

9.2.4 Detection of Timing Attacks. Many approaches [1 0, 19, 36]

focus on the detection of timing side or covert channels based on

the extraction of high-level information, such as entropy. Some ex-

isting work, namely Chen et al. [12], adopt determinism to replay

and detect timing channels via non-deterministic events. The dif-

ference between existing works in detecting timing attacks and

our deterministic browser is that such existing work is reactive,

i.e., waiting for timing attacks to happen and then detecting them,

while our deterministic browser is proactive, i.e., preventing tim-

ing attacks from happening in the ﬁrst place.

9.2.5 Defense against Web Tracking. Some approaches, e.g., Pri-

Varicator [35] and TrackingFree [39], aim to prevent web tracking

in general. The purpose of these approaches is diﬀerent from ours.

JavaScript performance ﬁngerprinting is just a small component

of web tracking, and neither work can defend against JavaScript

performance ﬁngerprinting.

9.3 Other Similar Techniques

We discuss some existing techniques that are similar to our deter-

ministic browser.

9.3.1 Determinism in General. Determinism is also used in de-

terministic scheduling [14–16, 31, 37, 49], such deterministic multi-

threading. Such techniques make the execution of programs, e.g., a

multithreaded one, follow a certain pattern so as to mitigate bugs,

e.g., concurrency ones. That is, they need to align execution se-

quence rather than adjusting the clocks. As a comparison, our de-

terministic browser not only align execution sequence as in deter-

ministic scheduling, but also adjust diﬀerent clocks in RFs.

9.3.2 Logical Time. Logical time is also used in distributed sys-

tems to solve the problem of “happening before”, such as Lamport

Clock [28] and Virtual Time [24]. The purpose of such work is to

deﬁne a partial or total order of events so that causal dependency

can be correctly resolved. The reason for such logical time is that a

distributed system lacks a centralized management; by contrast, a

deterministic browser has a browser kernel to coordinate diﬀerent

RFs with stronger clock synchronization than ordering events.

10 CONCLUSION

In conclusion, we propose deterministic browser, the ﬁrst approach

that introduces determinism into web browsers and provably pre-

vents browser-related timing attacks. Speciﬁcally, we break a web

browser down into many small units, called reference frames (RFs).

In a RF, we can easily remove one of the three key elements, i.e., an

adversary, a target secret and a reference clock, in timing attacks.

To achieve the removal purpose, we have two tasks: (i) making RFs

with a target deterministic, and (ii) making the communication be-

tween RFs—especially a deterministic RF with a non-deterministic

one—deterministic.

We implemented a prototype of deterministic browser, called

DeterFox, upon Firefox browser. Our evaluation shows that De-

terFox can defend against existing timing attacks in the literature,

and is compatible with real-world websites.

11 ACKNOWLEDGEMENT

The authors would like to thank anonymous reviewers for their

thoughtful comments. This work is supported in part by U.S. Na-

tional Science Foundation (NSF) under Grants CNS-1646662 and

CNS-1563843. The views and conclusions contained herein are those

of the authors and should not be interpreted as necessarily repre-

senting the oﬃcial policies or endorsements, either expressed or

implied, of NSF.

REFERENCES

[1] 2017. Concurrency model and Event Loop. (2017).

https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop.

[2] 2017. Dromaeo: Ja vaScript Performance Testing. (2017). http://dromaeo.com/.

[3] 2017. Mochitest. (2017). https://developer.mozilla.org/en-US/docs/Mozilla/Projects/Mochitest.

[4] 2017. Tor Browser.(2017). https://www.torproject.org/projects/torbrowser.html.en.

[5] 2017. Using the Mozilla build VM. (2017).

https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Using_the_VM.

[6] Amittai Aviram, Sen Hu, Bryan Ford, and Ramakrishna Gummadi. 2010. Deter-

minating Timing Channels in Compute Clouds. In Proceedings of the 2010 ACM

Workshop on Cloud Computing Security Workshop (CCSW ’10). ACM, New York,

NY, USA, 103–108. https://doi.org/10.1145/1866835.1866854

[7] Michael Backes, Goran Doychev, and Boris Köpf. 2013. Preventing Side-Channel

Leaks in Web Traﬃc: A Formal Approach. In 20th Annual Network and Dis-

tributed System Security Symposium, NDSS 2013, San Diego, California, USA, Feb-

ruary 24-27, 2013.

[8] Andrew Bortz and Dan Boneh. 2007. Exposing Private Information by

Timing Web Applications. In Proceedings of the 16th International Confer-

ence on World Wide Web (WWW ’07). ACM, New York, NY, USA, 621–628.

https://doi.org/10.1145/1242572.1242656

[9] Pablo Buiras, Amit Lev y, Deian Stefan, Alejandro Russo, and David Mazieres.

2013. A library for removing cache-ba sed attacks in concurrent information ﬂow

systems. In International Symposium on Trustworthy Global Computing. Springer,

199–216.

[10] Serdar Cabuk, Carla E. Brodley, and Clay Shields. 2004. IP Covert Ti ming Chan-

nels: Design and Detection. In Proceedings of the 11th ACM Conference on Com-

puter and Communications Security (CCS ’04). ACM, New York, NY, USA, 178–

187. https://doi.org/10.1145/1030083.1030108

[11] Yinzhi Cao, Xiang Pan, Yan Chen, and Jianwei Zhuge. 2014. JShield: Towards

Real-time and Vulnerability-based Detection of Polluted Drive-by Download At-

tacks. In Proceedings of the 30th Annual Computer Security Applications Confer-

ence (ACSAC).

[12] Ang Chen, W. Brad Moore, Hanjun Xiao, Andreas Haeberlen, Linh

Thi Xuan Phan, Micah Sherr, and Wenchao Zhou. 2014. Detect-

ing Covert Timing Channels with Time-Deterministic Replay. In

11th USENIX Symposium on Operating Systems Design and Imple-

mentation (OSDI 14). USENIX Association, Broomﬁeld, CO, 541–554.

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/chen_ang

[13] Shuo Chen, Rui Wang, XiaoFeng Wang, and Kehuan Zhang. 2010. Side-Channel

Leaks in Web Applications: A Reality Today, a Challenge Tomorrow. In Proceed-

ings of the 2010 IEEE Symposium on Security and Privacy (SP ’10). IEEE Computer

Society, Washington, DC, USA, 191–206. https://doi.org/10.1109/SP.2010.20

[14] Heming Cui, Jiri Simsa, Yi-Hong Lin, Hao Li, Ben Blum, XinanXu, Junfeng Yang,

Garth A. Gibson, and Randal E. Bryant. 2013. Parrot: a Practical Runtime for

Deterministic, Stable, and Reliable Threads. In Proc eedings of the 24th ACM Sym-

posium on Operating Systems Principles (SOSP ’13).

[15] Heming Cui, Jingyue Wu, John Gallagher, Huayang Guo, and Junfeng Yang. 2011.

Eﬃcient Deterministic Multithreading through Schedule Relaxation. In Proceed-

ings of the 23rd ACM Symposium on Operating System s Principles (SOSP ’11). 337–

351.

[16] Heming Cui, Jingyue Wu, Chia-Che Tsai, and Junfeng Yang. 2010. Stable De-

terministic Multithreading through Schedule Memoization. In Proceedings of the

Ninth Symposium on Operating Systems Design and Implementation (OSDI ’10).

[17] Charlie Curtsinger, Benjamin Livshits, Benjamin Zorn, and Christian Seifert.

2011. ZOZZLE: Fast and Precise In-browser JavaScript Malware Detection. In

Proceedings of the 20th USENIX Conference on Security.

[18] Edward W. Felten and Michael A. Schneider. 2000. Timing Attacks

on Web Privacy. In Proceedings of the 7th ACM Conference on Computer

and Communications Security (CCS ’00). ACM, New York, NY, USA, 25–32.

https://doi.org/10.1145/352600.352606

[19] Steven Gianvecchio and Haining Wang. 2007. Detecting covert tim-

ing channels: an entropy-based approach.. In ACM Conference on Com-

puter and Communications Security (2008-02-22), Peng Ning, Sabrina

De Capitani di Vimercati, and Paul F. Syverson (Eds.). ACM, 307–316.

http://dblp.uni-trier.de/db/conf/ccs/ccs2007.html#GianvecchioW07

[20] Ben Gras, Kaveh Razavi, Erik Bosman, Herbert Bos, and C ristiano Giuﬀrida. 2017.

ASLR on the Line: Practical Cache Attacks on the MMU. In Annual Network and

Distributed System Security Symposium (NDSS).

[21] Wei-Ming Hu. 1992. Reducing Timing Channels with Fuzzy

Time. Journal of Computer Security 1, 3-4 (May 1992), 233–254.

http://dl.acm.org/citation.cfm?id=2699806.2699810

[22] Marieke Huisman, Pratik Worah, and Kim Sunesen. 2006. A Temporal Logic

Characterisation of Observational Determinism.. In CSFW. IEEE Computer So-

ciety, 3. http://dblp.uni-trier.de/db/conf/csfw/csfw2006.html#HuismanWS06

[23] Ralf Hund, Carsten Willems, and Thorsten Holz. 2013. Practical Timing Side

Channel Attacks Against Kernel Space ASLR. In Proceedings of the 2013 IEEE

Symposium on Security and Privacy (SP ’13). IEEE Computer Society, Washington,

DC, USA, 191–205. https://doi.org/10.1109/SP.2013.23

[24] David R. Jeﬀerson. 1985. Virtual Time. ACM Trans. Program. Lang. Syst. 7, 3

(July 1985), 404–425. https://doi.org/10.1145/3916.3988

[25] Paul C. Kocher. 1996. Timing Attacks on Implementations of Diﬃe-Hellman,

RSA, DSS, and Other Systems. In Proceedings of the 16th Annual International

Cryptology Conference on Advances in Cr yptology (CRYPTO ’96). Springer-Verlag,

London, UK, UK, 104–113. http://dl.acm.org/citation.cfm?id=646761.706156

[26] David Kohlbrenner and Hovav Shacham. 2016. Trusted Browsers

for Uncertain Times. In 25th USENIX Security Symposium

(USENIX Security 16). USENIX Association, Austin, TX, 463–480.

https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kohlbrenner

[27] Robert Kotcher, Yutong Pei, Pranjal Jumde, and Collin Jackson. 2013. Cross-

origin Pixel Stealing: Timing Attacks Using CSS Filters. In Proceedings of the 2013

ACM SIGSAC Conference on Computer & Communications Security (CCS ’13).

ACM, New York, NY, USA, 1055–1062. https://doi.org/10.1145/2508859.2516712

[28] Leslie Lamport. 1978. Time, Clocks, and the Ordering of Events in

a Distributed System. Commun. ACM 21, 7 (July 1978), 558–565.

https://doi.org/10.1145/359545.359563

[29] Peng Li, D ebin Gao, and Michael K. Reiter. 2013. Mitigating access-driven timing

channels in clouds using StopWatch. In 2013 43rd Annual IEEE/IFIP International

Conference on Dependable Systems and Networ ks( DSN), Budapest, Hungary, June

24-27, 2013. 1–12.

[30] Peng Li, Debin Gao, and Michael K. Reiter. 2014. StopWatch: A Cloud Architec-

ture for Timing Channel Mitigation. ACM Trans. Inf. Syst. Secur. 17, 2, Article 8

(Nov. 2014), 28 pages. https://doi.org/10.1145/2670940

[31] Tongping Liu, Charlie Curtsinger, and Emery D Ber ger. 2011. Dthreads: eﬃcient

deterministic multithreading. In Proceedings of the Twenty-Third ACM Sympo-

sium on Operating Systems Principles. ACM, 327–336.

[32] Yali Liu, Dipak Ghosal, Frederik Armknecht, Ahmad-Reza Sadeghi, Steﬀen

Schulz, and Stefan Katzenbeisser. 2009. Hide and Seek in Time - Ro-

bust Covert Timing Channels.. In ESORICS (Lecture Notes in Computer Sci-

ence), Michael Backes and Peng Ning (Eds.), Vol. 5789. Springer, 120–135.

http://dblp.uni-trier.de/db/conf/esorics/esorics2009.html#LiuGASSK09

[33] Keaton Mowery, Dillon Bogenreif, Scott Yilek, and Hovav Shacham. 2011. Fin-

gerprinting information in JavaScript implementations. In WEB 2.0 SECURI TY

& PRIVACY (W2SP).

[34] Martin Mulazzani, Philipp Reschl, Markus Huber, Manuel Leithner, Sebastian

Schrittwieser, Edgar Weippl, and FC Wien. 2013. Fast and reliable browser identi-

ﬁcation with javas cript engine ﬁngerprinting. In WEB 2. 0 SECURITY & PRIVACY

(W2SP).

[35] Nick Nikiforakis, Wouter Joosen, and Benjami n Livshits. 2015. PriVaricator: De-

ceiving Fingerprinters with Little White Lies. In Proceedings of the 24th Interna-

tional Conference on World Wide Web (WWW ’15). ACM, New York, NY, USA,

820–830. https://doi.org/10.1145/2736277.2741090

[36] Peng Ning, Douglas S. Reeves, and Pai Peng. 2006. On the Secrecy of Timing-

Based Active Watermarking Trace-Back Techniques. IEEE Symposium on Secu-

rity and Privacy (2006).

[37] Marek Olszewski, Jason Ansel, and Saman Amarasinghe. 2009. Kendo: eﬃcient

deterministic multithreading in software. ACM Sigplan Notices 44, 3 (2009), 97–

108.

[38] Yossef Oren, Vasileios P. Kemerlis, Simha Sethumadhavan, and Angelos D.

Keromytis. 2015. The Spy in the Sandbox: Practical Cache Attacks in JavaScript

and Their Implications. In Proceedings of the 22Nd ACM SIGSAC Conference on

Computer and Communications Security (CCS ’15). ACM, New York, NY, USA,

1406–1418. https://doi.org/10.1145/2810103.2813708

[39] Xiang Pan, Yinzhi Cao, and Yan Chen. 2015. I Do Not Know What You Vis-

ited Last Summer - Protecting users from third-party web tracking with Track-

ingFree browser. In NDSS.

[40] Xiang Pan, Yinzhi Cao, Shuangping Liu, Yu Zhou, Yan Chen, and Tingzhe Zhou.

2016. CSPAutoGen: Black-box Enforcement of Content Security Policy Upon

Real-world Websites. In Proceedings of the 2016 ACM SIGSAC Conference on Com-

puter and Communications Security (CCS ’16). ACM, New York, NY, USA, 653–

665. https://doi.org/10.1145/2976749.2978384

[41] Andrei Sabelfeld and David Sands. 2000. Proba bilistic noninterference for multi-

threaded programs. In Computer Security Foundations Workshop, 2000. CSFW-13.

Proceedings. 13th IEEE. IEEE, 200–214.

[42] Geoﬀrey Smith and Dennis Volpano. 1998. Secure Information Flow in a Multi-

threaded Imperative Language. In Proceedings of the 25th ACM SIGPLAN-SIGACT

Symposium on Principles of Programming Languages (POPL ’98). ACM, New York,

NY, USA, 355–364. https://doi.org/10.1145/268946.268975

[43] Deian Stefan, Pablo Buiras, Edward Z Yang, Amit Lev y, David Terei, Alejandro

Russo, and David Mazières. 2013. Eliminating cache-based timing attacks with

instruction-based scheduling. In European Symposium on Research in Computer

Security. Springer, 718–735.

[44] Paul Stone. 2013. Pixel perfect timing attacks with HTML5 (White Paper).

(2013).

[45] Tom Van Goethem, Wouter Joosen, and Nick Nikiforakis. 2015. The Clock is

Still Ticking: Timing Attacks in the Modern Web. In Proceedings of the 22Nd

ACM SIGSAC Conference on Computer and Communications Security (CCS ’15).

ACM, New York, NY, USA, 1382–1393. https://doi.org/10.1145/2810103.2813632

[46] Tom Van Goethem, Mathy Vanhoef, Frank Piessens, and Wouter Joosen. 2016.

Request and Conquer: Exposing Cross-Origin Resource Size. In Proceedings of

the 21st USENIX Conference on Security Symposium (Security).

[47] Dennis Volpano and Geoﬀrey Smith. 1997. Eliminating covert ﬂows with min-

imum typings. In Computer Security Foundations Workshop, 1997. Proceedings.,

10th. IEEE, 156–168.

[48] Weiyi Wu and Bryan Ford. 2015. Deterministically Deterring Timing Attacks in

Deterland. In Conference on Timely Results in Operating Systems (TRIOS).

[49] Junfeng Yang, Heming Cui, Jingyue Wu, Yang Tang, and Gang Hu. 2014. De-

terminism Is Not Enough: Making Parallel Programs Reliable with Stable Multi-

threading. (2014).

[50] Steve Zdancewic and Andrew C. Myers. 2003. Observational Determinism for

Concurrent Program Security. In 16th IEEE Computer Security Foundations Work-

shop (CSFW-16 2003), 30 June - 2 July 2003, Paciﬁc Grove, CA, USA. 29.

[51] Danfeng Zhang, Aslan Askarov, and Andrew C. Myers. 2012. Language-based

control and mitigation of timing channels. In ACM SIGPLAN Conference on Pro-

gramming Language Design and Implementation, PLDI ’12, Beijing, China - June

11 - 16, 2012. 99–110.

[52] Yinqian Zhang, Ari Juels, Alina Oprea, and Michael K. Reiter. 2011. HomeAlone:

Co-residency Detection in the Cloud via Side-Channel Analysis. In Proceedings

of the 2011 IEEE Symposium on Security and Privacy (SP ’11). IEEE Computer

Society, Washington, DC, USA, 313–328. https://doi.org/10.1109/SP.2011.31

[53] Yinqian Zhang, Ari Juels, Michael K. Reiter, and Thomas Ristenpart. 2012. Cross-

VM Side Channels and Their Use to Extract Private Keys. In Proceedings of the

2012 ACM Conference on Computer and Communications Security (CCS ’12). ACM,

New York, NY, USA, 305–316. https://doi.org/10.1145/2382196.2382230

A PROOF OF LEMMA 1

Proof. Let us look at the two conditions in Deﬁnition 2 sepa-

rately. First, if the clocks in both RFs are synchronized at the mo-

ment of the communication, the sender does not convey additional

timing information to an observer in the receiver. Therefore, Deﬁ-

nition 1 is satisﬁed.

Second, if the sender is deterministic, the clock information can

be directly conveyed to the receiver. Speciﬁcally, we will show that

Deﬁnition 1 is satisﬁed in either clock or a mixture of both, which

makes the receiver’s RF still deterministic. Because the receiver is

deterministic in its own clock, we just need to consider the other

two cases.

(i) Since the sender is deterministic, following Deﬁnition 1, we

have Equation 2.

tse nd e r

2−tse nd e r

1=f(Osender

1,Ose nd e r

2)(2)

Because the sender can convey any information in the message,

both Or e ce i ve r

1and Or ec e iv e r

2contain information about Os e nd e r

and Ose nd e r

2. That is, we will have Equation 3, meaning that the

receiver is deterministic in the sender’s clock.

tse nd e r

2−tse nd e r

1=f′(Ore c ei v er

1,Or ec e iv e r

2)(3)

(ii) We further show that the mixture of the sender’s and the re-

ceiver’s clock, i.e., tse nd e r

2−tr ec e iv e r

1, is deterministic. According

to Equation 3 and the deﬁnition of the receiver’s determinism, we

have Equation 4.

tse nd e r

2−tse nd e r

st a r t =f1(Ose nd er

2,Ose nd e r

st a r t )

tr ec e iv e r

1−tr ec e iv e r

st a r t =f2(Or ec e iv e r

1,Or ec e iv e r

st a r t )(4)

When we minus the second equation in Equation 4 from the

ﬁrst, we will have Equation 5.

(tsender

2−tse nd e r

st a r t ) − (tre c ei v er

1−tr ec e iv e r

st a r t )

=f1(Osender

2,Ose nd e r

st a r t )

−f2(Ore c ei v er

1,Or ec e iv e r

st a r t )

(5)

After doing some transformations in Equation 5, we will have

Equation 6, following Deﬁnition 1 and showing that the receiver

is deterministic in the clock mixing both the sender’s and the re-

ceivers. Note that both Ose nd e r

st a r t and Or e ce i ve r

st a r t are constant.

tse nd e r

2−tr ec e iv e r

=tse nd e r

st a r t −tr e c ei ve r

st a r t +f1(Osender

2,Ose nd e r

st a r t )

−f2(Ore c ei v er

1,Or ec e iv e r

st a r t )

=f′′(Or ec e iv e r

1,Ose nd e r

(6)

In sum, if a communication from a sender to a receiver obeys

Deﬁnition 2, the communication does not break the determinism

in the receiver.



B PROOF OF THEOREM 1

Proof. According to Lemma 1, even if an adversary observer in

a RF obtains an external clock, the RF is still deterministic. There-

fore, without loss of generality, we only consider one clock in the

proof. There are two sub-scenarios: (i) an observer in a RF measur-

ing an internal target secret, and (ii) an observer in a RF measuring

an external target secret in another RF.

(i) Let us look at an observer in a RF measuring an internal

target secret. Let us assume that a target secret happens in two

copies (RF 1and RF 2) of the same RF, e.g., the execution runtime

of the same JavaScript code with the same inputs.An observer (Ob)

makes observations (ORF 1

{St ,En d }and ORF 2

{St ,En d }) of the target secret

in these two RFs. We have the following Equation 7.

ORF 1

End =OR F 2

End OR F 1

St =OR F 2

St (7)

With Equation 7, we have Equation 8.

∆tRF 1−∆tR F 2=(tRF 1

End −tR F 1

St ) − (tR F 2

End −tR F 2

St )

=f(ORF 1

End ,OR F 1

St ) − f(ORF 2

End ,OR F 2

St )

∆tRF 1=∆tR F 2=const

(8)

Because RF 1and RF 2are arbitrary RFs, we show that ∆t=

tEnd −tS t =const

(ii) Let us then look at an observer in a RF measuring an exter-

nal target secret in another RF. Because according to Deﬁnition 2,

the clocks in both RFs are synchronized, the measurement that the

observer makes is the same as another observer, maybe virtual, in

the RF with a target secret. Therefore, the sub-scenario just boils

down the ﬁrst one.



C PROOF OF THEOREM 2

Proof. We prove this theorem from two aspects:

•Deﬁnition 1⇒Deﬁnition 3: Say for two diﬀerent executions (E1

and E2), i.e., two RFs in the context of JavaScript, an observer

makes two observations at the starting point (st ) of the execu-

tion and the timestamp of a speciﬁc opcode (op). According to

Deﬁnition 1, we will have Equation 9 and 10.

op −t1

st =f(O1

op ,O1

st )(9)

op −t2

st =f(O2

op ,O2

st )(10)

Then, we perform this operation (Equation 9−Equation 10):

op −t1

st − (t2

op −t2

st )

=f(O1

op ,O1

st ) − f(O2

op ,O2

st )

⇒t1

op −t2

=t1

st −t2

st +f(O1

op ,O1

st ) − f(O2

op ,O2

st )

(11)

Equation 11 obeys Deﬁnition 3.

•Deﬁnition 3⇒Deﬁnition 1: Say there is a speciﬁc execution (Es d ),

i.e., a RF in JavaScript context, which can be used as a standard

for comparison with any other executions. The execution starts

from op1to opn. For an arbitrary opcode (opiwhere i∈ {1...n})

in that execution, we have the following Equation 12.

tEsd

opi=Õ

k∈{ 1...i}

tEsd

opk(12)

For an arbitrary execution (Eab ), a replicate of Es d but at a dif-

ferent time, according to Deﬁnition 3, we have Equation 13.

tEab

opi−tEs d

opi=C

⇒tEab

opi=tEs d

opi+C=Õ

k∈{ 1...i}

tEsd

opk

+C(13)

Now, say an observer makes two observations in Eab , which

corresponds to two opcodes (opiand opj). We have Equation 14.

tEab

opi−tEa b

opj=Õ

k∈{ 1...i}

tEsd

opk+C− ( Õ

k∈{ 1...j}

tEsd

opk+C)

=Õ

k∈{i...j}

tEsd

opk

=f(opi,opj)

(14)

Equation 14 obeys Deﬁnition 1. Note that the last step in Equa-

tion 14 is due to that Eab is a replication of Es d and the obser-

vations in a JavaScript RF are the executed opcodes.

