An Empirical Study of Information Flows in Real-World JavaScript
Cristian-Alexandru Staicu Daniel Schoepe Musard Balliu Michael Pradel Andrei Sabelfeld







printacmref=false 
 
plain 
ormatdoi[1]





































[enumerate]noitemsep,topsep=2pt,leftmargin=*
[itemize]noitemsep,topsep=2pt,leftmargin=*






mydefDefinition


























[enumerate]noitemsep,topsep=2pt,leftmargin=*
[itemize]noitemsep,topsep=2pt,leftmargin=*












  
  

  

    0pt
    0.25
    0.5em


itemize*

  
    

<⟨
>⟩
|/⇓
|->↦





eventIdCtr





















































































` 
`,=,






































TU Darmstadt

Chalmers University of Technology

KTH Royal Institute of Technology

TU Darmstadt

Chalmers University of Technology























JavaScript
  keywords=typeof, new, true, false, catch, function, return, null, catch, switch, var, if, in, while, do, else, case, break,
  keywordstyle=,
  ndkeywords=class, export, boolean, throw, implements, import, this,
  ndkeywordstyle=,
  identifierstyle=,
  sensitive=false,
  comment=[l]//,
  morecomment=[s]/**/,
  commentstyle=,
  stringstyle=,
  morestring=[b]',
  morestring=[b]"



   language=JavaScript,
   
   extendedchars=true,
   basicstyle=,
   showstringspaces=false,
   showspaces=false,
   numbers=left,
   numberstyle=,
   numbersep=9pt,
   tabsize=2,
   breaklines=true,
   showtabs=false,
   captionpos=b,
   
   framesep=4.5mm,
   framexleftmargin=2.5mm,
   
   
   escapeinside=/*##*/,
   xleftmargin=2em










none



Information flow analysis 
prevents secret or untrusted data from flowing into public or trusted 
sinks.
Existing mechanisms cover a wide array of options, ranging from lightweight 
taint analysis to heavyweight information flow control that also considers 
implicit flows.
Dynamic analysis, which is particularly popular for languages such as 
JavaScript, faces the question whether to invest in analyzing flows 
caused by not executing a particular branch, so-called hidden implicit 
flows.
This paper addresses the questions how common different kinds of flows are 
in real-world programs, how important these flows are to enforce security 
policies, and how costly it is to consider these flows.
We address these questions in an empirical study that analyzes  
real-world JavaScript programs that suffer from various security problems, 
such as code injection vulnerabilities, denial of service vulnerabilities,
memory leaks, and privacy leaks.
The study is based on a state-of-the-art dynamic information flow analysis 
and a formalization of its core.
We find that implicit flows are expensive to track in terms of 
permissiveness, label creep, and runtime overhead.
We find a lightweight taint analysis to be sufficient for most of 
the studied security problems, while for some privacy-related code, 
observable tracking is sometimes required.
In contrast, we do not find any evidence that tracking hidden implicit flows 
reveals otherwise missed security problems.
Our results help security analysts and analysis designers to understand the 
cost-benefit tradeoffs of information flow analysis and provide empirical 
evidence that analyzing implicit flows in a cost-effective way is a relevant 
problem.










































An Empirical Study of Information Flows in Real-World JavaScript
    Andrei Sabelfeld
    
================================================================







§ INTRODUCTION




JavaScript is at the heart of the modern web, empowering rich client-side 
applications and, more recently, also server-side applications.
While some language features, such as dynamism and flexibility, 
explain this popularity, the lack of other features, such as language-level 
protection and isolation mechanisms, open up a

wide range of integrity, availability, and confidentiality vulnerabilities <cit.>.
As a result, securing JavaScript applications has become



a key challenge for web application security.
Unfortunately, existing browser-level mechanisms, such as the same-origin 
policy or the content security policy, are
coarse-grained, falling short to distinguish between secure and
insecure manipulation of data by scripts.
Furthermore, 
server-side applications lack such isolation mechanisms completely, 
allowing an attacker, e.g., to inject and execute arbitrary code that 
interacts with the operating system through powerful 
APIs <cit.>.


An appealing approach to securing JavaScript applications is information 
flow analysis.
This approach tracks the flow of information from sources to sinks in
order to 
enforce application-level security policies.
It can ensure both integrity, by preventing information from untrusted 
sources to reach trusted sinks, and confidentiality, by preventing 
information from secret sources to reach public sinks.
For example, information flow analysis can check that no attacker-controlled 
data is evaluated as executable code or that secret user data is not sent to 
the network.
Because the dynamic nature of JavaScript hinders precise static analysis, 
dynamic information flow analysis has received significant attention by 
researchers <cit.>.
The basic idea of dynamic information flow analysis is to attach security 
labels, e.g., secret (untrusted) and public (trusted), to runtime values and 
to propagate these labels during program execution.
To simplify the presentation, we assume to have two security labels, and we 
say that a value is sensitive if its label is secret or untrusted;
otherwise, we say that a value is insensitive.


At the language level, a program may propagate information via two kinds of 
information flows:[There are other kinds of flows, such as timing 
and cache side-channels, which we ignore here.]
Explicit flows <cit.> occur whenever sensitive information is passed
by an assignment statement or into a sink.
Implicit flows <cit.> arise via control-flow structures of programs, e.g., 
conditionals and loops, when the flow of control depends on a sensitive value.
For a dynamic information flow analysis, implicit flows can be further 
classified into flows that happen because a particular branch is executed, 
so-called observable implicit flows <cit.>, and flows that happen
because a particular branch is not executed, so called hidden 
implicit flows <cit.>.









Figure <ref> illustrates the different kinds of flows with a 
simple JavaScript-like program that leaks sensitive information.
The program has a variable passwd, which is marked initially as a sensitive source at 
line <ref>.
Using this variable in an operation that creates a new value, e.g., in 
line <ref>, is an explicit flow.

Consider the case where the password is “topSecret”, i.e., the conditional 
at line <ref> evaluates to true, and line <ref> 
sets gotIt to true.
At line <ref>, the gotIt variable is sent to the network 
through the function sink(), which is considered to be an insensitive sink.  
The flow from the password to gotIt is an observable implicit flow 
because a sensitive value determines that gotIt gets written.

Now, consider the case where passwd is “abc”. The
branch at line <ref> is not taken and the gotIt variable 
remains false. Sending this information to the network reveals that 
the password is different from “topSecret”. This flow is a hidden implicit 
flow because a sensitive value determines that gotIt does not get 
written.


Ideally, an information flow analysis should consider all three kinds of 
flows.
In fact, there exists a large body of work on static, dynamic, hybrid, and 
multi-execution techniques to prevent explicit and implicit flows.
However, so far these tools have seen little use in practice, despite the 
strong security guarantees that they provide.
In contrast, a lightweight form of information flow analysis called 
taint analysis is widely used in computer security <cit.>.
Taint analysis is a pure data dependency analysis that only tracks explicit 
flows, ignoring any control flow dependencies. 




The question which kinds of flows to consider is a tradeoff between costs 
and benefits.
On the cost side, considering more flows increases false positives <cit.>.
A false positive here means that a secure execution is conservatively
blocked by an overly restrictive enforcement mechanism. 
A common reason is that a value gets labeled as sensitive even though it does
not actually contain information that is security-relevant in practice.
This problem, sometimes referred to as
label creep <cit.>, reduces the 
permissiveness of information flow monitoring, because the monitor will 
prematurely stop a program to prevent a value 
with an overly sensitive label from reaching a sink.
Another cost of considering more kinds of flows is an increase in runtime 
overhead.
On the benefit side, considering more flows increases the ability to find 
security vulnerabilities and data leakages, i.e., the level of trust one 
obtains from the analysis.
For example, an analysis that considers only explicit flows will miss any 
leakage of sensitive data that involves an implicit flow.

Unfortunately, despite the large volume of research on information flow 
analysis, there is very little empirical evidence on the importance of the 
different kinds of flows in real applications.
Because of this lack of knowledge, potential users of information flow 
analyses cannot make an informed decision about what kind of analysis to
use. 




















To better understand the tradeoff between costs and benefits of using a 
dynamic information flow analysis, this paper presents an empirical study of 
information flows in real-world JavaScript code.
Our overall goal is to better understand the costs and benefits of 
dynamically analyzing explicit, observable implicit, and hidden implicit 
flows.
Specifically, we are interested in how prevalent different kinds of flows 
are, what kinds of security problems can(not) be detected when considering 
subsets of flows, and what costs considering all flows imposes.


To address these questions, we study  real-world JavaScript 
programs in various application domains with a diverse set of security 
policies.
The study considers integrity problems, specifically code injection 
vulnerabilities and denial of service vulnerabilities caused by an 
algorithmic complexity problem,
and confidentiality problems, specifically leakages of uninitialized memory, 
browser fingerprinting and history sniffing.
Each studied program has at least one real-world security problem that 
information flow analysis can detect.



Our study is enabled by a novel methodology that combines state-of-the-art 
dynamic information flow  
analysis <cit.> and program 
rewriting <cit.> with a set of novel security 
metrics.
We implement the methodology in a dynamic information flow analysis built on 
top of Jalangi <cit.>.
The implementation draws on a sound analysis for a simple core of 
JavaScript.
The formalization relates the security metrics to semantic security 
conditions for taint tracking <cit.>, observable tracking <cit.> and 
information flow monitoring <cit.>.




The findings of our study include:


  * All three kinds of flows occur locally in real-life applications, i.e., an 
    analysis that 
    ignores some of them risks to miss violations of the information flow 
    policy. Explicit flows are by far the most prevalent, and only five benchmarks contain hidden implicit flows (Section <ref>).  












  
  * An analysis that considers explicit and observable implicit flows, but 
    ignores hidden implicit flows, detects all vulnerabilities in our 
    benchmarks.
    For most applications it is even sufficient to track explicit flows 
    only, while for some client-side, privacy-related applications one must 
    also consider observable implicit flows (Section <ref>). 
   
  
  * 



  Tracking hidden implicit flows causes an analysis to prematurely terminate 
  various executions. Furthermore, we find that different monitoring 
  strategies proposed in the literature vary significantly in their 
  permissiveness.  (Section <ref>).
  
   
  * 


  The amount of data labeled as sensitive steadily increases during the 
  execution of most benchmarks, confirming the label creep problem.
  An analysis that considers implicit flows increases the label creep by 
  over 40% compared to an analysis that considers only explicit flows 
  (Section <ref>).
    
 
  * The analysis overhead caused  by considering implicit flows is 
    significant: Ignoring implicit flows saves the effort of tracking 
    runtime operations by a factor of 2.5 times (Section <ref>).











Prior work (discussed in Section <ref>) studies false 
positives caused by static analysis of implicit 
flows <cit.> and the semantic strength of 
flows <cit.>. Jang et al. <cit.> conduct a 
large-scale empirical study showing that
several popular web sites use information flows to exfiltrate data about users' behavior. Kang et al. <cit.>
combine dynamic taint analysis with targeted implicit flow analysis, demonstrating the importance of tracking implicit flows for trusted
programs.
However, to the best of our knowledge, no 
existing work addresses the above questions.



 

In summary, this paper contributes the following:


  
  * We are the first to empirically study the prevalence of explicit, 
    observable implicit, and hidden implicit flows in real-world 
    applications against integrity, availability, and confidentiality policies.
  
  * We present a methodology and its implementation, which enables the study, and we provide a 
  formal basis for empirically studying information flows (Section <ref>).
  
  * We show the soundness of the analysis for a core of JavaScript with 
    respect to semantic security conditions (Appendix).
  
  * Through realistic case studies and security policies, we provide 
    empirical evidence that sheds light on the cost-benefit tradeoff of 
    information analysis and that outlines directions for future work (Section <ref>).



We share our implementation, as well as all benchmarks and policies used for 
the study, to support future evaluations of information flow tools for 
JavaScript.[<https://new-iflow.herokuapp.com/download-iflow.html>] 



§ BENCHMARKS AND SECURITY POLICIES



Our study is based on  client-side and server-side JavaScript applications, which suffer from four classes of vulnerabilities.
These applications are subject to  attacks that have been independently discovered by existing work, including 
integrity, availability, and confidentiality attacks. For every application, 
we define realistic security policies expressed as information flow 
policies.
Table <ref> shows the applications, along with their security policies, and size measured in lines of code.
The benchmarks vary in size from tens of lines of code to tens of thousands.
We further explain the policies below.
For each application we either create or reuse a set of inputs that trigger the attack and other inputs to increase the coverage of different behaviors.















footnote-6
<https://www.privacytool.org/AnonymityChecker/>
footnote1
<http://www.lalit.org/lab/javascript-css-font-detect/>
footnote1
<https://browserleaks.com/js/donottrack.js>
footnote1
<https://robinlinus.github.io/socialmedia-leak/>
footnote1
<https://www.privacytool.org/AnonymityChecker/>
footnote1
<https://popmyads.com/>
footnote1
<https://browserleaks.com/firefox#more>


Our goal is an in-depth study of the different kinds of information 
flows for a range of security policies; we do not claim to study a representative 
sample of JavaScript applications.
Existing in-breadth empirical studies, which analyze hundreds of 
thousands of web pages against fixed policies, provide clear evidence for 
security and privacy risks in JavaScript 
code <cit.>. In contrast to these 
large-scale studies, our effort
consists in identifying vulnerable scripts from different domains and 
analyzing the flows therein.






  
Injection vulnerabilities on  The  
ecosystem has enabled a proliferation of  server and desktop applications 
written in JavaScript.



Injection vulnerabilities are programming errors that enable an attacker to 
inject and execute malicious code.
Recent work <cit.> has demonstrated the devastating impact of 
injection vulnerabilities on server-side programs, e.g., when
an attacker-controlled string reaches powerful APIs such as exec or 
eval.
Such attacks can severely compromise integrity, e.g.,
deleting all files in a directory or completely controlling the attacked 
machine.



We study 19  modules that contain injection vulnerabilities (IDs 1 to 19 in Table <ref>).  As 
security policies, we consider the interface of a module as an untrusted 
source and the APIs that interpret strings as code, such as
exec or eval, as trusted sinks.




  
ReDoS vulnerabilities Regular expression Denial of Service, or 
ReDoS, is a form of algorithmic complexity attack that exploits the possibly 
long time of matching a regular expression against an attacker-crafted 
input.
The single-threaded execution model of JavaScript makes JavaScript-based web 
servers particularly susceptible to ReDoS attacks <cit.>.
We analyze 19 web server applications that are subject to ReDoS attacks (IDs 20 to 39 in Table <ref>).
As a security policy, we consider data received via HTTP requests as 
untrusted sources and regular expressions known to be vulnerable as trusted 
sinks.



  
Buffer vulnerabilities
Buffer vulnerabilities expose memory content filled with previously used
data, e.g., cryptographic keys, source code, or system information.
In , such vulnerabilities occur when using the Buffer 
constructor without explicit initialization.
Buffer vulnerabilities are similar to the infamous Heartbleed flaw in 
OpenSSL <cit.>, as both allow an attacker to read more memory 
than intended.
We analyze 7 applications subject to buffer vulnerabilities (IDs 40 to 46 in Table <ref>).
The security policy requires that no information flows from the buffer 
allocation constructor to HTTP requests without initialization.



  
Device fingerprinting and history sniffing
Web-based fingerprinting collects device-specific information, e.g., 
installed fonts or browser extensions, to identify users <cit.>.
History sniffing attacks use the fact that browsers display links 
differently depending on whether the target has been 
visited <cit.>.
We analyze 10 client-side JavaScript applications that are subject to 
various forms of fingerprinting and history sniffing attacks (IDs 47 to 56 in Table <ref>).
The security policies label as secret the sources that provide sensitive 
information, e.g., the font height and width, and as public sinks the APIs 
that enable external communication, e.g., image tags.
We adapt these programs to our Node.js-based infrastructure by introducing
minimal changes that emulate DOM interactions. We carefully cross-checked 
this adaptations in a pair-programming fashion, ensuring that all flows in 
the original program are preserved. The policies are application-specific 
and mark certain nodes in the emulated DOM as sources and sinks. In contrast 
to the other benchmarks, these programs can potentially be 
malicious <cit.>.  That is, the 
assumption that the analyzed code is trusted  does no longer hold.





§ METHODOLOGY




To address the research questions from Section <ref>, we present a 
methodology that combines a set of novel metrics with a dynamic information 
flow analysis <cit.>, a monitoring 
strategy <cit.>, and an automated mechanism to insert
upgrade statements <cit.>.
The metrics summarize the flows observed during the program execution. 
This section provides the necessary background on information flow analysis, 
an informal description of our methodology, and definitions of the  
metrics. It also presents a formalization of the core of our 
methodology.




 §.§ Setting: Information Flow Analysis








  
*Security labels

An information flow analysis associates each value with a security 
label that indicates how sensitive the value is. Labels are typically 
arranged in a lattice <cit.>.
To ease the presentation, we focus on two labels: H (for high or sensitive) 
and L (for low or insensitive), where H is more sensitive than L.
Given a label ℓ∈{H,L}, we write v^ℓ to denote that a value 
v has security label ℓ. If a value v does not have a label, we 
assume it is implicitly labeled as L.




  
*Information flow policy
The analysis checks whether data from a sensitive source influences 
data that arrives at an insensitive sink.
The sources and sinks for a program are specified in an information 
flow policy, or short, policy.
For integrity, the policy specifies that no information from untrusted 
sources (H) reaches trusted sinks (L).
For confidentiality, the policy stipulates that no information from secret 
sources (H) reaches public sinks (L).
We model sources by variables and object fields, and their security label 
corresponds to the label of the value that they contain initially.
We denote sinks by a function sink(), which is implicitly 
labeled as L.




  
*Monitoring strategies
Different monitoring strategies for dynamic information flow analysis 
address the problem of checking whether an execution violates a policy.
In this work, we focus on flow-sensitive dynamic monitors, where variables 
can be assigned  different security labels during the execution.
Table <ref> gives an overview of the monitoring strategies 
studied in this paper. 
Taint analysis tracks only explicit flows and stops the program only if an 
H-labeled value reaches a sink.

In contrast to taint tracking, the other two strategies also track implicit 
flows.

The monitors identify implicit flows by maintaining a security stack 
that contains all sensitive labels of expressions in conditionals that influence the control flow.
When the stack is non-empty, the program executes in a sensitive 
context.
Observable Tracking <cit.> tracks only explicit 
and observable implicit flows, but ignores hidden implicit flows.
Whenever an L-labeled variable is updated in a sensitive context, 
observable tracking updates the label as sensitive and continues with the 
execution.
For example, consider the following program, which is trivially secure 
because there is no call to sink():


var location; var y; var z;
if (10 < location < 20)/*##*/ 
  y = "Home";/*##*/   
//upgrade(y);/*##*/  
z = "You are at " + y;/*##*/         


Consider now an execution where the location is 15^H.
Observable tracking updates the labels of y and z as sensitive 
and does not stop the execution.

The strictest monitoring strategies try to prevent also hidden implicit
flows.
We consider two variants of such a strategy.
They both terminate the execution of the program whenever an observable 
implicit flow may lead to a hidden implicit flow in another execution.
The No Sensitive Upgrade strategy (NSU) <cit.>
disallows updating the security labels of a variable in a sensitive context.
In particular, it terminates the execution whenever such an update happens.
For example, consider the execution of the above program with 
location=15^H.
The NSU strategy terminates the program at line <ref> due to 
the update of the L-labeled variable y in a sensitive context.

Permissive Upgrade (PU) <cit.>  is a refinement of the 
NSU strategy.
It labels a value as partially leaked if an L-labeled variable is 
updated in a sensitive context, and terminates the program if the updated 
variable is further used outside the sensitive context.
Consider again the same execution of the above program.
The PU strategy labels y as partially leaked at 
line <ref> because the program writes to the L-labeled 
variable in a sensitive context, and then terminates the program at 
line <ref> because the value is used.
In our work, we use the PU strategy to study the prevalence of different 
kinds of flows.




  
*Upgrade statements
Naively applying the PU strategy to real-world programs can be very 
restrictive and risks to increase the number of false positives, i.e., 
terminate many secure executions. To address this problem, Austin and 
Flanagan propose the upgrade statement <cit.> and 
the privatization statement <cit.>.  These 
statements change the label of a variable to H explicitly, to signal a 
potential hidden implicit flow to the monitor.  
For example,  we can insert an upgrade statement before 
line <ref> in the above example to mark y as sensitive 
even if the branch is not taken.
As a result, the program does not terminate immediately when the value is 
read.
If the program would later call sink(y), then the monitor would 
terminate the program and report a policy violation.







































  
*Permissiveness
The above example illustrates the permissiveness issues of different 
monitoring strategies, i.e., that they terminate the program unnecessarily 
even though no policy violation occurs.
Taint tracking and observable tracking both do not terminate the program.
In contrast, both NSU and PU terminate the program unnecessarily.
This overapproximation of policy violations is necessary to avoid
potential hidden implicit flows.
Adding upgrade statements avoids such premature termination of the program 
by assigning an H-label to y, independently of what branch of the 
conditional statement is executed.
If we uncomment line <ref>, the execution proceeds without 
terminating the program unnecessarily.
That is, upgrade statements may increase the permissiveness, but impose the 
cost of adding upgrade statements.




 §.§ Security Metrics


Our approach uses program testing to measure the prevalence of different 
kinds of information flows. The basic idea is to test a program with an 
information flow monitor that implements the PU strategy, while incrementing 
counters that represent the number of explicit, observable implicit, and 
hidden implicit flows.
These counters then allow us to reason about the prevalence of the different 
kinds of flows and about the policy violations that different monitoring 
strategies would detect.
In contrast to the PU monitor that terminates the program when it encounters 
a policy violation, our monitor continues the execution to measure flows in 
the remainder of the execution. We refer to Section <ref>
for the formal definition of the monitor.


We consider information flows at two levels of granularity.
On the one hand, we consider flows induced by a single operation in the program 
(Section <ref>).  We call such flows micro 
flows or simply flows. Studying flows at the micro flow level is worthwhile because it 
provides a detailed understanding of the operations that contribute to higher-level 
flows. In particular, flows provide a quantitative answer to the permissiveness challenges faced
by state-of-the-art dynamic monitors that implement the NSU or the PU strategy.

On the other hand, we consider transitive flows of information between a 
source and a sink, called source-to-sink flows 
(Section <ref>).
Studying flows at this coarse-grained level is worthwhile because 
source-to-sink flows are what security analysts are interested in 
when using an information flow analysis.

The metrics presented in this section measure the prevalence of flows 
quantitatively, and do not attempt to judge the importance of flows.
To ensure that our flows represent relevant problems, our study uses 
real-world security problems and policies that capture these issues.












  §.§.§ Micro Flows



To measure how many explicit, observable implicit, and hidden implicit 
flows exist, our monitor increments the counters for these micro
flows as follows.



  
*Explicit flows
The approach counts an explicit flow for every assignment event where the 
written value is sensitive but the value that gets overwritten (if any) is not 
sensitive. The rationale is to capture program behavior where sensitive 
information flows to a memory location that  stores insensitive information. 
In contrast, overwriting a sensitive value with another (in)sensitive value 
does not leak any new information, and therefore does not count as an 
explicit flow.
    
 For example, consider this code:
[mathescape]
var x = 3^H; var y = 5^H; var z;
x = y; // no explicit flow
z = x; // explicit flow




  
*Observable implicit flows
The approach counts an observable implicit flow for every assignment event that 
happens in a sensitive context and that overwrites an insensitive value.  Similar 
to explicit flows, the rationale is to capture program behavior that writes 
sensitive information to a memory location that stores insensitive information. 
The main difference is that the assignment happens because of a control 
flow decision made based on a sensitive context.  Note that it is irrelevant 
whether the written value is sensitive because the fact that a write happens 
leaks sensitive information. 

For example, consider this code:
[mathescape]
var x = true^H; var y = 3; var z;
if (x)
  y = 5; // observable implicit flow
z = 7;   // no flow




  
*Hidden implicit flows
The approach counts a hidden implicit flow for every execution of an upgrade 
statement of a variable containing insensitive information.  The rationale is to capture assignment events that did not
happen, but that could have happened during the execution if a control flow 
decision that depends on a sensitive value would have been different.







For example, consider this code:
[mathescape]
var x = false^H; var y; var z;
if (x)
  y = 5;        // not executed, no flow
upgrade(y);     // hidden implicit flow 
z = y;          // hidden implicit flow




  §.§.§ Label Creep

As mentioned earlier, a common reason for false positives is label
creep. Since measuring false positives would be subject to a given
source-to-sink policy, we focus on measuring the prevalence of the
more general phenomenon of label creep in micro flows.



Recall that 
this concept refers to the fact that information flow analysis may 
quickly label a large portion of all values handled in a program as 
sensitive.
In most of the cases, this leads to an explosion in false positives that in 
turn reduces the usefulness of the analysis. We propose a novel metric called
Label Creep Ratio (LCR) to assess how many variables and object fields in memory are 
labeled as sensitive.





    = # sensitive variables/fields ever assigned/# variables/fields ever
    assigned

For a given monitoring strategy, the Label Creep Ratio is the ratio between 
the number of assignments of
H-labeled values and the total number of assignments.
Intuitively, measuring the LCR throughout an execution
estimates the speed at which the memory locations get assigned sensitive
labels.



  §.§.§ Source-to-sink Flows



To what degree do different kinds of flows contribute to policy violations?
To address this question, we consider transitive flows from a source of 
sensitive information to a sink of insensitive information. For instance, none of the 
flows in the examples above correspond to a source-to-sink flow, since no 
sink statement is present. 

Now, consider the code:

[mathescape]
var x = false^H; var y; var z;
if (x)
  y = 5;
upgrade(y); // hidden micro flow
z = x;      // explicit micro flow
sink(y);    // source-to-sink flow


The program contains two micro flows and one source-to-sink flow.
However, if the execution is analyzed with taint tracking or observable 
tracking, the source-to-sink flow is missed, because it occurs only due to 
the upgrade statement.

As another example, consider the following code:

[mathescape]
var x = true^H; var y; var z;
if (x)
  y = 5;   // observable flow
z = x;     // explicit flow
sink(y+z); // source-to-sink flow


The source-to-sink flow will be detected by all three kinds 
of monitoring strategies, because the variable z gets labeled H via 
an explicit micro flow and then gets passed to the sink.

As illustrated by these two examples, we measure how many source-to-sink 
flows different monitoring strategies detect by tracking what micro flows 
contribute to a source-to-sink flow.
Furthermore, to count the number of unique source-to-sink flows that a 
monitor detects, we compute the set of source code locations involved in 
each source-to-sink flow.
If the code locations of two source-to-sink flows are the same, we 
count them as only one unique flow. This corresponds to the way a human
security analyst would inspect warnings produced by an  
analysis.




  §.§.§ Inference of Upgrade Statements



The approach described so far requires a program that indicates hidden implicit
flows through upgrade statements. To obtain such a program, we adapt a
testing-based technique for automatically inserting upgrade
statements <cit.>. The basic idea is to repeatedly execute
the program with a particular policy, to monitor the execution for potentially
missed hidden implicit flows (using the PU 
strategy <cit.>, see Section <ref>), and to
insert upgrade statements that signal them to the monitor when counting
micro flows. Whenever the monitor
terminates the program because it detects an access to a value u that is
marked as partially leaked, the approach modifies the program by inserting an
upgrade statement at the code location where u is next used; this upgrade
statement in the modified program will then be executed whenever u is used
again, regardless of whether the same branch that leads to the insertion of the
upgrade statement is taken. The process continues until it reaches a fixed
point, i.e., until the program has enough upgrade statements for the given
tests.


The ability of our analysis to observe hidden implicit flows depends on the
completeness of the inferred upgrade statements, since missing upgrade
statements may result in false negatives for hidden implicit flows. How often
this occurs depends on how well the analyzed executions cover the branches of
the programs. One way to assess this ability would be to measure tradition
branch coverage, i.e., the percentage of all branches that are covered by the
given test inputs. However, traditional branch coverage is only of limited use
because inserting upgrade statements does not rely on covering all branches in
the code, but only on a subset. Specifically, the ability to insert upgrade
statements depends on the branch coverage for conditionals that depend
on sensitive values. We present a metric called Sensitive Branch Coverage
(SBC) that captures this idea:


    = |{ c ∈ C  where both true and false branch covered}|/|C|


where C is the set of conditionals that depend on a sensitive value.
For example, consider executing the following program with 
x=false^H:

[mathescape]
var x; var y
if (x)/*##*/
  y = 5;


The set C consists of the conditional at line <ref>, but 
since the execution covers only the false branch, =
0/1=0.



 §.§ Formalization of Flows and Conditions


  @comma,
` =13
,
  @comma
  @comma
  




We define the syntax and semantics of NanoJS, a simplified
core of JavaScript to illustrate the flow counting performed by
our implementation.

Notation: 
We denote empty sequences by . Concatenating two
sequences τ_1 and τ_2 is denoted by τ_1 . τ_2. Slightly
abusing notation, we also use the same notation to prepend a single element
α to a sequence τ by writing α . τ. Similarly, we
write α∈τ to denote that α occurs in sequence τ.

NanoJS syntax:
NanoJS statements:


::=
[ |    |    c_1 ; c_2
  |    e
  |    xe
  |    xye
  |;                                     ec_1c_2
  |    ec ] 


where  x, y ∈,  and  e ∈


A terminated execution is denoted by . All function calls
to sinks with expression e are modeled by e; other function
calls are not considered in NanoJS.


Semantics:  Operationally, the constructs in NanoJS behave as in
standard imperative languages.

To count micro flows, we associate each primitive value
with a tuple : of flow counts, where = ℕ^3.  A 
tuple (e, o, h) ∈ denotes e explicit flows, o observable flows, 
and h hidden flows.
A value is either a primitive value annotated with a flow count, or an 
address on
the heap. We assume that there is a set  of primitive base types, 
such as boolean, numbers, and strings. A heap object o ∈ maps a 
finite set of names to values. We write 
for boolean value true and  for boolean value false.

We use flow counts to track how information is propagated by a program,
analogous to labels in other information flow monitors. We define a 
join-semilattice
structure for flow counts as follows.
Intuitively, a non-zero flow count
indicates a sensitive value, whereas if all flow counts are zero, the value 
is insensitive:

The join of two flow counts is defined
as _1 ⊔_2 = _1 + _2, where _1 + _2
denotes the pointwise addition of the two flow counts.

Two flow counts satisfy _1 _2
if whenever _2 = (0,0,0) then _1 = (0,0,0).

A configuration c, , h, t, consists of a statement c ∈, an environment : → mapping variable names to
values, a heap h : →, a stack of security levels t
∈^⋆, and a sink counter : counting flows reaching sink
statements; we denote the set of configurations by .

An execution of a NanoJS program yields a trace = ^⋆
indicating outputs produced by the execution.









We now define the small-step semantics of NanoJS. A step c, , h, t,
  τc', ', h', t', ' denotes a single
evaluation step producing trace τ.




We write  for a terminated execution.

Slightly abusing notation, we define (h, v) as the join of all labels
occurring in value v with heap h. For simplicity, we assume that there 
are no cyclical references on the heap.


The function (x, , h) denotes the pair (', h'), where
the hidden flow count of all components of the value of a variable x ∈ is incremented by 1.


To update flow counts, we use an auxiliary function Δ : ××^⋆→ ().
Intuitively, Δ(_old, ℓ_new,
t) increments the explicit and observable flow counters for assigning a 
value with flow count _new to a location with label _old 
while the security stack is t. We define Δ(_old, _new, t) =
(Δ_e, Δ_o, 0) where Δ_e =
  1    _new_old

    0    otherwise and Δ_o = 
    1    ℓ_old =  t ≠

    0    otherwise

To define observations based on references passed to
sinks, we use a helper function (h, v) : {×^⋆} that, given a value, returns all references to heap objects reachable 
from the value.

We denote evaluating an expression e in environment  and
heap h by e, h.
The rules propagate flow counts
into the result values; for example, adding two values with one explicit
flow each will result in two explicit flows in the result.


We assume, contrary to real-world JavaScript, that expressions do not have 
side effects.



Finally, Figure <ref> gives the rules of small-step operational 
semantics for NanoJS with flow counting.
The way the rules modify the environment and heap is standard.
Some standard rules are omitted and provided in the appendix.
In addition to the standard execution of a program, the semantics also track 
flow counts
for each value. For example, an assignment statement xe
propagates the flow counts of the assigned expression e and additionally
increments the explicit flow count if e has non-zero flows and the 
observable flow count if the control-flow path
is determined by sensitive data.

A sink statement e increments global counts representing
source-to-sink flows.
Since all sink statements model writes to
insensitive sinks, any write of an expression with non-zero
flow counts will result in incrementing the global counters.


Security conditions: 
We also adapt existing security conditions
for tracking only explicit or observable flows to NanoJS <cit.>. To capture only
explicit flows, we use the notion of explicit secrecy; intuitively, a
run of a program satisfies explicit secrecy if and only if the program
obtained by sequentially composing all non-control-flow commands executed
during that run does not leak information. For example, the program
hl1l2l would
produce the extracted programs l1l
or l2l depending on the value
of h in a given run. In both cases, the extracted program
contains prohibited information flows, since the source program
only leaks information through an implicit flow.

To track only explicit and observable implicit flows, we keep branching
constructs in the extracted program, but replace not taken branches by .
If the extracted program does not leak sensitive information, then the run satisfies
observable secrecy. For example, in the program
l0hl1l,
observable secrecy would extract either
l0hl1l or
l0hl. This matches
the intuition that an observable flow only occurs in the run where h is
, where the assignment l1 is executed, but not in
a run where h is , since this run only leaks information
through a hidden implicit flow; i.e. the extracted program when
h = leaks information, but the extracted program for h =
does not.

Appendix <ref> gives formal definitions of the two 
notions.

Soundness:  To establish soundness of our counting scheme, we show that
if all explicit flow counts for all sinks for a given run are 0, then that run
satisfies explicit secrecy. Similarly, we show that if all explicit and
observable flow counts are 0, the run satisfies observable secrecy. The formal
theorem statements and proofs can be found in Appendices <ref>
and <ref>. 




 §.§ Implementation



To implement our methodology, we develop a tool for dynamic information flow analysis 
following Hedin at al. <cit.>. The implementation builds on 
Jalangi <cit.>, a dynamic analysis framework for JavaScript that 
uses source-to-source transformation. Since Jalangi supports
ECMAScript 5 only, we down-compile programs written in newer versions of the 
language with Babel <cit.>. Building on top of
Jalangi allows us to focus on the important parts of the analysis and 
let the framework handle otherwise challenging aspects of implementing a 
dynamic information flow analysis, e.g., on the fly instrumentation of code 
produced by , exceptional termination of functions, boxing and 
unboxing of primitive values <cit.>.  
We handle higher-order 
functions and track dynamic modification of object properties as described 
by Hedin et al. <cit.>. Our policy language is 
expressive, allowing the security analyst to mark both functions and 
arguments of callbacks as sources.

To approximate the effects of native calls, we model them by transferring the 
labels from all parameters to the return value. Moreover, if one of the 
parameter is an object, we propagate labels from all its properties to the 
return value. For a set of frequently used native functions, such as 
, , , and
, we create richer models that propagate 
labels more precisely. To increase the confidence in our implementation, we 
created more than 100 validation tests that assert the correctness of label 
propagation in typical usage scenarios.
When inserting upgrades, the implementation does not modify the actual 
source code but it stores the source code locations of upgrades, and then 
performs the upgrades at runtime.





§ EMPIRICAL STUDY


This section presents the results of our empirical study that assesses the 
costs and benefits of tracking different kinds of flows.

The last two columns of Table <ref> show the sensitive branch 
coverage (SBC) and the number of upgrades inserted while executing the 
benchmarks.
Overall, the tests used for the study reach a high SBC, for 54% of the programs even 100%, 
enabling the analysis to insert upgrade statements.
For each of the considered benchmarks, our tool can detect source-to-sink 
flows.
This is hardly surprising, since we already know that the programs contain 
such flows, but it shows that our tool can handle complex, real-life 
JavaScript code.






































 §.§ Prevalence of Micro Flows



At first, we address the question of how prevalent explicit, observable 
implicit, and hidden implicit micro flows are among all operations that induce 
an information flow.
Figure <ref> shows the distribution of micro flows  
for our benchmarks. The majority of benchmarks contain both implicit and 
explicit micro flows. Benchmark 39 is a special case where reaching the sink 
is the first operation performed on the untrusted data, and hence the data 
flows directly from source to sink without producing any micro flow. The 
explicit flows are by far the most prevalent, appearing in all but one 
benchmarks.   benchmarks also contain hidden implicit 
flows, but we can safely conclude that these cases are rare.






 §.§ Source-to-sink Flows



We now evaluate source-to-sink flows, which are the ultimate measure of 
success for an information flow analysis.
Source-to-sink flows are what a security analysts ultimately cares about: 
how does information from a sensitive source reaches an insensitive sink.  
Information flow analysis has no way to show that such a flow is 
security-relevant, but it is the analyst's job to further inspect the flows 
and decide. In this section, however, we have a different goal and setup: we 
start with a set of known security problems that produce a source-to-sink 
flow and proceed by showing what type of analysis is needed to detect these 
problems.









Our tool can enforce different 
security conditions (cf. Section <ref>). For example, if we are 
interested only in explicit and 
observable implicit flows, we can run the tool in observable tracking mode 
and enforce observable secrecy.

Figure <ref> presents the number of source-to-sink flows 
detected by different monitoring strategies.
All the integrity vulnerabilities can be detected by taint tracking only, 
and all the security violations in our data set can be detected through 
observable tracking. Moreover, all the Node.js vulnerabilities can be 
detected by the taint tracking only, independently of whether they are 
confidentiality or integrity vulnerabilities. We argue that this is because  
our Node.js programs are expected to be trusted. That is, a security issue  
may arise from a programming error, but not by malicious intention.  This 
assumption does not hold, however, for the fingerprinting and history 
sniffing benchmarks, where only observable implicit flows contribute to the 
source-to-sink flows. A second explanation for why the implicit flows are 
prevalent in the browser environment is that there are already a set of 
security mechanisms in the browser that prevent certain type of dangerous 
behavior. For example when fingerprinting the login state using images, an 
attacker cannot directly read the bytes of the image due to same origin 
policy, and hence it relies on measuring its width.


We analyzed in detail the additional source-to-sink flows detected by 
observable tracking for benchmarks 12, 26, 34, 43, and 44, and by PU for 
benchmark 34.  In all these cases the reported flows are false positives, 
since they do not allow an attacker to exploit the respective vulnerability. 
In Section <ref>, we discuss in detail why these false positives 
occur when data is propagated through implicit flows.



Our results indicate that observable tracking is enough to tackle all the 
real-life security problems we consider and that taint tracking suffices for 
all the trusted code. We do not claim that there are no real-life security 
problems beyond observable secrecy, we just do not see any in our data set.  
Moreover, we believe that when strong controls are in place, attackers will 
be motivated to use more sophisticated attacks, possibly though the use of 
hidden implicit flows.  However, tracking these flows is expensive as we 
will see in the remainder of this section.



 §.§ Permissiveness




A potential problem for adopting information flow analysis in practice is 
its limited permissiveness, i.e., the fact that a monitor may terminate the 
program even though no data flows from a source to a sink.
Our metrics allow us to quantify this effect both for the NSU and the PU 
monitoring strategies.
Specifically, we measure how many code locations a user would have to 
inspect because a monitor terminates the program.
The NSU monitor terminates the program when an update of an insensitive 
variable is performed in a sensitive context.
This condition corresponds to observable implicit micro flows and we count 
the number of code locations where such a flow occurs.
The PU monitor terminates the program when an insensitive variable that was 
updated in a sensitive context is read.
This termination condition corresponds to the locations where our tool 
inserts an upgrade statement.
Figure <ref> shows the number of code locations affected by 
the lack of permissiveness for NSU and PU.
We exclude benchmarks for which neither of the monitoring strategies raises 
an alarm.
On average, NSU throws  times more alarms than PU, 
that is, PU is much more practical than NSU.
However, when comparing the PU violations to the number of source-to-sink 
flows that require PU (Figure <ref>), we observe that most of 
the PU alarms do not translate to actual source-to-sink flows and should be 
considered false positives.





 §.§ Label Creep Ratio






As a second metric for the cost of different kinds of flows, we 
use the Label Creep Ratio (LCR) defined in 
Section <ref>.  For each benchmark and monitoring 
strategy, we measure how the LCR changes during the execution time.
Figure <ref> shows the ratio for PU monitoring.
The metric is not monotonically increasing because the analysis is 
flow-sensitive, i.e., the security label of a variable may change over time.
Nevertheless, the LCR steadily increases for most benchmarks, which 
confirms the label creep problem.
Because our policies are targeted at detecting known security problems 
in the benchmarks, the maximum LCR reached is relatively low (20%, on 
average).

A comparison of different monitoring strategies shows that stricter 
monitoring causes more label creep.
On average, observable tracking has a  smaller LCR than PU; a 
taint tracking analysis has a  smaller LCR 
than observable tracking.
Figure <ref> illustrates this effect with a representative 
benchmark (number 11).
The graph shows how label creep increases for observable tracking compared 
to taint tracking.

