Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing

Keywords: Sécurité, Frelatage, XSS, Algorithme Evolutionniste, Inférence, Intelligence Artificielle, Applications Web Security, Fuzzing, XSS, Evolutionary Algorithm, Inference, Artificial Intelligence, Web Applications

Testing is a viable approach for detecting implementation bugs which have a security impact, a.k.a. vulnerabilities. When the source code is not available, it is necessary to use black-box testing techniques. We address the problem of automatically detecting a certain class of vulnerabilities (Cross Site Scripting a.k.a. XSS) in web applications in a black-box test context. We propose an approach for inferring models of web applications and fuzzing from such models and an attack grammar. We infer control plus taint flow automata, from which we produce slices, which narrow the fuzzing search space. Genetic algorithms are then used to schedule the malicious inputs which are sent to the application. We incorporate a test verdict by performing a double taint inference on the browser parse tree and combining this with taint aware vulnerability patterns. Our implementations LigRE and KameleonFuzz outperform current open-source black-box scanners. We discovered 0-day XSS (i.e., previously unknown vulnerabilities) in web applications used by millions of users.

Introduction

Why did I rob banks? Because I enjoyed it. I loved it.

Go where the money is...and go there often.

[ [START_REF] Sutton | Where the money was: the memoirs of a bank robber[END_REF] The world is a dangerous place to live ; not because of those who do evil, but because of those of the people who don't do anything about it.

[ [START_REF] Einstein | Conversations avec Pablo Casals : souvenirs et opinions d'un musicien[END_REF] Computer security is the cancer of the software industry. There is no money to prevent it. Only sick persons care about it, but it is generally already too late.

However, everybody will have to face it someday. [Ruff 2013b] Do not underestimate the importance of cyber-attack capabilities. I do not know how to defend a system if you are unaware of how to attack it. [Filiol 2013b]

Context

Actors and Threats The Internet is a connected network of billions of devices.

For the simplicity of administrating them, we plugged into this network of networks devices having an impact on the physical world: traffic control, power plants, gas stations, etc. Corporations and governments have data-stores connected to the Internet [Duwell 2013]. Banks and trading systems offer an interface with the Internet. If not secured, those systems make the Internet a playground for hackers with varying motivations (e.g., enemy governments, army, individuals paid by Mafia, etc.).

As security researchers, it is our duty to develop new techniques to protect better national assets such as: energy, money, communication and information. More 1.1. CONTEXT CHAPTER 1. INTRODUCTION specifically,in this cyber war, we want to protect computer assets from attacks exploiting vulnerabilities (flaws in the system). A way to achieve such goal is to detect vulnerabilities, and more precisely to detect them as soon as possible. If they are present in our systems, we need to patch them to prevent exploitation (defensive security). If they are present in enemy systems, attackers may want to exploit them to gain additional privileges (offensive security). The source code of applications may not be available (e.g., when testing integrated or remote components). In such cases, we need to rely on black-box testing techniques. This thesis focuses on detecting certain classes of vulnerabilities in a black-box test context.

Security and Vulnerabilities Figure 1.1 shows a dependability tree according to the [START_REF] Avižienis | Dependability and its threats: a taxonomy[END_REF] taxonomy. We mark in bold our focus for this thesis. We detect errors and failures that affect availability (readiness for correct service), [START_REF] Trivedi | [END_REF]] and our Focus integrity (absence of improper system alteration), confidentiality (absence of unauthorized disclosure of information). More specifically, we search for vulnerabilities in black-box test context. We address the automatic detection of Cross-Site Scripting (XSS).

CHAPTER 1. INTRODUCTION 1.2. VULNERABILITIES

Vulnerabilities 1.2.1 Panorama

A vulnerability is an application fault which ultimately will lead to a failure violating a security property that was supposed to always hold.

Afterwards we list a non-exhaustive panorama of vulnerabilities:

• Code execution: permit an attacker to force an application to execute code he created, because of a confusion between code and data. In such cases, the integrity of the executed code is violated. It generally means that the confidentiality and the integrity of the data processed by the application is also violated. It may also mean a violation of the availability property for the application. Code injection vulnerabilities include:

memory corruption (e.g., Buffer Overflow), web command injection (e.g., Cross Site Scripting), cross-format interpretation (e.g., GIFAR [START_REF] Magazinius | Polyglots: Crossing Origins by Crossing Formats[END_REF]).

• Logical: for example, in an authentication protocol, a parameter is lacking a security property (e.g., encryption, freshness, etc.), this makes the whole scheme vulnerable to a particular kind of attacks:

confidentiality: a credential is transmitted over an unencrypted channel, e.g., not over an SSL encrypted connection; integrity: an unsigned authentication token permits a user to impersonate another one, e.g., session id; freshness: an action vulnerable to replay attack e.g., Cross-Site Request Forgery (CSRF) [START_REF][END_REF]], [Armando et al. 2008].

• User interface : techniques trick the user to perform an action, whereas he believes performing another one, e.g., click-jacking [START_REF] Rydstedt | Busting frame busting: a study of clickjacking vulnerabilities at popular sites[END_REF]. Such techniques violate the integrity of the user interface, thus of his actions.

• Flawed access control: depending on the path used to access an object, there may be a discrepancy in the way the access control is enforced. Such a situation frequently occurs when developers introduce new features in Web Browsers (e.g., [Heiderich 2012a, Heiderich et al. 2010, Heiderich 2013b]). Such vulnerabilities generally result in the violation of the integrity of objects. In the case of a Same-Origin Policy Bypass [START_REF] Huang | [END_REF], the confidentiality of documents belonging to other security domains is also violated.

• Flawed or weak cryptography: e.g., sensitive information is sent in cleartext [Soltani 2013] or the implementation of a cryptographic algorithm is flawed [Thomas 2013]. Either the integrity, or the confidentiality are generally targeted.

VULNERABILITIES CHAPTER 1. INTRODUCTION

In this thesis, we will search for code execution vulnerabilities.

About Code Execution Vulnerabilities

Code execution vulnerabilities arise because of the way an application is processing data, it may interpret part of it as code. Examples of code execution vulnerabilities include Buffer Overflow -a memory corruption vulnerability -and Cross Site Scripting (XSS) -a Web Command Injection vulnerability.

A former black-hat1 used to make money with carding2 and botnets 3 . He used to rely on XSS 55% of the time to take control of a website [Hansen 2013]. In order to gain access to a web application, he used XSS more frequently than memory corruption vulnerabilities. In terms of frequency, SQL injection was the third most common vulnerability category he used. All those three kinds of low-level vulnerabilities permit attacker controlled code execution. XSS and SQL injection belong to the family of Web Command Injection. SQL injection ranks first in the OWASP top 10 of 2013, and XSS ranks third [OWASP 2013b]. Whereas years ago, the focus was on desktop web application development, there is an increase in customized versions of web applications for mobile devices (e.g., Android, IOS applications). In this domain, developers seem to make similar mistakes. As a result, numerous mobile applications are sensitive to Web Command Injection vulnerabilities [START_REF] Moulu | Sécurité des applications Android constructeurs et réalisation de backdoors sans permission[END_REF]].

Web Command Injection

Web Command Injection (WCI) belongs to the code execution vulnerabilities. WCI is a family of vulnerabilities that affects applications interpreting a scripting language (e.g., HTML, SQL, Shell, PHP etc.) interpreters. WCI vulnerabilities are characterized by the possibility to escape a confinement within a grammatical structure. Example of Web Command Injection include Cross Site Scripting (XSS), SQL injection, PHP Code injection, etc.

Cross-Site Scripting (XSS) is one of the currently most dangerous web based attacks: it ranks third in the [OWASP 2013b] Top 10 vulnerabilities. [Zalewski 2011b] describes them as "one of the most significant and pervasive threats to the security of web applications." Criminals use XSS to spam social networks, spread malwares and steal money [START_REF] Luo | [END_REF]]. In 2013, XSS were found in Paypal, Facebook, and eBay [Kugler 2013[START_REF] Nirgoldshlager | Nirgoldshlager. Stored XSS In Facebook[END_REF]] [ZentrixPlus 2013]. We shall present XSS in Chapter 2.

CHAPTER 1. INTRODUCTION 1.3. OBJECTIVES

Consequences of XSS an XSS vulnerability is activated by a maliciously crafted HTTP request, or a maliciously crafted Ajax request. Its exploitation provides to an attacker the capability of injecting arbitrary HTML code within portions of the web application. Thus, the victim web interpreter will execute a sub-interpreter code, which is controlled by the attacker. This permits:

• exfiltrating data (e.g., emails [Krebs 2012], authentication tokens [Naraine 2010], bank account password, contacts [Acunetix 2010], etc.);

• using the victim computer as a proxy or a node of a malicious network (e.g., spam relay, DDoS, exploiting websites, malware propagation [START_REF] Faghani | [END_REF], mining bitcoin for the attacker, etc.);

• de-anonymizing a target: a browser can be uniquely tracked -up to a certain precision -via HTTP headers, available plugins and version, subset of interpreted codes [Nikiforakis & Vigna 2013] [Abgrall et al. 2012];

• exploiting a memory corruption vulnerability in a browser sub-interpreter to execute attacker controlled assembly code (e.g., [CVE-2008-13802008, CVE-2006-4565 2006] target JavaScript interpreters in browser and email client), to gain additional privileges (e.g., escape the browser process, obtain additional security tokens, etc.).

Objectives

Our main problem is:

How to improve the efficiency and precision of black-box security testing for automatically detecting XSS?

In order to address it, we face several sub-problems:

• sources: on which parts of the inputs to act for an efficient security testing?

• input sequences: how to drive the system into a desired state?

• maliciousness: how to create parts of inputs likely to exhibit a failure?

• test verdict: how and where to observe the effect of an input?

• confidence: which criteria characterize a precision in security testing?

Contributions

Our contributions are:

• an inference and slicing approach of particular control and taint flows for guiding XSS search;

DISSERTATION STRUCTURE CHAPTER 1. INTRODUCTION

• a combination of model inference and fuzzing for detecting Type-1 (reflected) & Type-2 (stored) XSS;

• an implementation of these approaches and their evaluation,

• which led to the discovery and responsible disclosure 4 of previously unknown vulnerabilities: four stored XSS (CVE-2013-7297[Duchène 2013a], [Duchène 2014d], [Duchène 2014c]), and of forty reflected XSS (CVE-2014-1599 [Duchène 2014a], [Duchène 2014c]), some of them impacting millions of users.

Dissertation Structure

We introduce the addressed problems in Chapter 2. We present the high level architecture of our approach in Chapter 3. Our approach for black-box XSS detection combines a particular control+taint flow inference (Chapter 4) and evolutionary fuzzing (Chapter 5). We evaluate this approach in Chapter 6. We provide an overview of related techniques in Chapter 7. We conclude and provide directions for future work in Chapter 8.

CHAPTER 2

Problem Statement

The only acronyms that matter: RCE (Remote Code Execution), LPE (Local Privilege Escalation), COE (Continuation of Execution) [START_REF] Grugq | The Grugq[END_REF]]

The importance of XSS may overstep that of memory corruption vulnerabilities. [Heiderich 2013a] Due to their wide existence and their high impact when exploited (an attacker is able to remotely execute arbitrary code in the victim's interpreter), we focus in this thesis on a particular case of web command injection: XSS. We define XSS in Section 2.1, and the problem of automatically detecting XSS in black-box in Section 2.5.

Web Command Injection (WCI) is a family of vulnerabilities that affects applications interpreting languages at run-time (e.g., HTML, SQL, Shell, PHP etc.). Since they compile and execute instructions at run-time, those are referred to as interpreters. Command injection vulnerabilities are characterized by the possibility to escape a confinement within a structure.

Each WCI subfamily has a name dependent on the context (i.e., the output grammar: database interpreter, browser interpreter, shell...). e.g., for the HTML grammar, WCI is named XSS.

Cross Site Scripting (XSS)

The detection of XSS involves a taint-flow analysis on a control-flow graph. Peach saves a note, e.g., buenosdias, by filling and submitting the form, i.e., sending the abstract input POST /?action=save message&msg= buenosdias1 (transition 7 → 17 in the control flow model shown in Figure 2.5) to the application. We describe in Chapter 4 how to construct such control flow models, where nodes represent pages and transitions HTTP requests. Such Control Flow Models (CFM) are different of assembly control flow graphs that most security engineers are used to work with, but CFM capture similar information at a higher level of abstraction. Later on, she lists the saved notes, by sending GET /?action=get messages (transition 18 → 21). An extract of corresponding output is shown in Listing 2.1. Moreover, in this application, notes are shared between users. Thus, an attacker Koopa Troopa would attempt to send a malicious msg value to escape the confinement (in Listing 2.1, a reflection is constrained in a specific context: outside tags, before the  tag). An example of malicious input is t src = 7 → 17 (POST /?action=save message&msg= buenosdias  ). An excerpt of the corresponding output for the subsequent transition t dst = 18 → 21 is ...of saved messages
 buenosdias  <a href="./?action=delete.... When Peach's browser (the victim) parses this output, it executes the code introduced by the attacker, and a messagebox is displayed, as shown in Figure 2.6.

In order to detect XSS, we need to navigate in the web application. Thus, we need information about the control flow of the application. The problem is that most deployed web applications lack formal documentation: a formal behavioral model is rarely available. However, such models improve the ability to perform a pertinent security testing campaign for an application [START_REF] Takanen | Fuzzing for software security testing and quality assurance[END_REF] Example B: an XSS involves a taint flow A fictive website http://yoshi.jp suffers from an XSS vulnerability. A necessary condition for an XSS is a reflection, i.e., a taint-flow i.e., a partial input copy from an attacker controlled input parameter to a sink, part of an output of the web application, as illustrated in Figure 2.7. Our notion of taint flow is different to the traditional taint propagation rules for each assembly instruction in grey-box contexts [START_REF] Newsome | [END_REF], Xu et al. 2006]. We define our taint notion in web applications in black-box more precisely in Definition 3.

Client → Server: ... GET /nice.html?name= birdo HTTP/1.1 Host: yoshi.jp Client ← Server: ... Hello birdo ! Figure 2.7: The Input Parameter name is reflected into the output of the web application Koopa Troopa wants the victim Peach to execute a code that he controls. He observes that the reflection is located in a structure "text node, outside a tag".

DEFINITIONS CHAPTER 2. PROBLEM STATEMENT

He wants to "escape" this text node, and includes additional interpreter nodes such as JavaScript (JS) ones. Thus he crafts the parameter name with the value lakitu . To achieve exploitation, he creates a page hosted on koopatroopa.fr, which will force the user browser to perform this malicious request to the vulnerable website (hence the crossdomain), once the code of koopatroppa.fr is interpreted (see Figure 2.8).

Client → Attacker:

Definitions

We abstract an actual Web site as a Web Application. The Web Application receives a spiderlink and replies with a page model. As illustrated in Figure 2.9, spiderlinks represent the HTTP requests sent to the concrete Web site, and page models abstract the HTTP responses.

Spiderlink and Page Model

We define abstract(o) which abstracts an HTTP reply o into a page model p.

As illustrated in Figure 2.10, a page model is a prefix tree containing several spiderlinks (i.e., abstract links from  tags or abstract forms from <form> tags). We also define concretize(i) which produces an HTTP request req from a spiderlink i.

Input, concretize(Spiderlink i) Let Σ be an alphabet. Each spiderlink is built from a link or a form.

Definition 1 Spiderlink

A spiderlink is a couple composed of:

• one action: the substring before the ? of an Hypertext Transfer Protocol (HTTP) Uniform Resource Locator (URL)

• a list of input parameters (name, value, method) ∈ {Σ * } 2 ×{GET, POST, COOKIE, HEADER} Output, abstraction to Page Model p A page model is an abstraction of a concrete output of a web application. It contains spiderlinks.

DEFINITIONS CHAPTER 2. PROBLEM STATEMENT

Definition 2 Page Model

Let o ∈ O be an output of a web application. Let F(o) be the set of links and forms in o. A page model p = abstract(o) is a prefix tree which is built from the set of spiderlinks and dompaths obtained from F(o). It has at least six levels including the root node.

For each spiderlink f ∈ F(o), a set of nodes is added to the tree. Each set consist of the following nodes or groups of nodes, ordered from the immediate children of the root node to the deepest ones:

• dompath is a node, child of the root node. Its value is a string ∈ {/([az] ∪ {/}) * }, the shortest path in the Document Object Model (DOM) from the root to the  or <FORM> tag.

• action is a tree of nodes, of depth ≥ 1. Its root is a child of a dompath node. Each node of an action subtree has a string value contains a part of an HTTP URL before the ? split by /

• params is a node, child of an action node. Its value is a list of strings: the list of parameter names.

• values is a node, child of a params node. Its value is a list of strings: the list of parameter values.

• methods is a node, child of a values node. Its value is a list of parameter methods, each element ∈ {GET, POST, COOKIE, HEADER} Consider the HTML ouput in Listing 2.2. The corresponding page model is shown in Figure 2.10. The left side shows the browser rendering, while the right side represents the page model. It contains four spiderlinks. The prefix tree representation makes easier the identification of similarities between spiderlinks and between page models.

Taint

The taint is a metadata information between inputs and data handled by the application [Livshits 2012]. It designates the possibility of an input to explicitly influence such data. The taint is a dynamic notion which flows between data. It is generally a dynamic white-box (assume the availability of the application source code) or grey-box (assume the availability of the application code) notion, as in [START_REF] Rawat | [END_REF][START_REF] Bekrar | A Taint Based Approach for Smart Fuzzing[END_REF], although in our case we will perform taint inference dynamically in black-box (see Section 4.3).

DEFINITIONS CHAPTER 2. PROBLEM STATEMENT

When considering taint propagation in grey-box or white-box, three subproblems arise:

• Taint Sources: When is an object directly influenced by inputs? In Table 2.1 we list examples of taint sources.

• Taint Propagation rules: When is an object indirectly influenced by inputs?

• Taint Removal: When is an object not influenced by inputs?

Taint tracking is widely used in white-box/grey-box test context for vulnerability runtime detection, e.g., for XSS [START_REF] Vogt | [END_REF]] and for Memory Corruption Vulnerabilities [START_REF] Bosman | Minemu: The world's fastest taint tracker[END_REF].

Practical data tainting on important sized applications may only consider explicit value influence (e.g., assignments) in taint propagation rules, and not considering indirect value influence (e.g., resulting from a conditional check). Indeed, such taint tracking systems aim at avoiding too numerous objects to be tainted, in order to reduce the number of false positives in the test verdicts [START_REF] Haller | Dowsing for overflows: a guided fuzzer to find buffer boundary violations[END_REF].

In black-box test context, as we cannot track the taint flow from a source to a sink, we have to infer it, if possible. In Section 4.3, we provide information on taint inference for XSS.

In Table 2.1, we list examples of code execution vulnerabilities, their taint source, the code at server side, and sometimes how to infer knowledge in blackbox.

Vulnerability Taint Source

Sink & Tainted Argument (white-box) In black-box test context, XSS vulnerabilities arise when a tainted data (resulting of a partial copy of an input parameter value, a string of characters) appears in at least one substring of one output (HTML code), and gets executed by the browser as code. Definition 3 Taint Let x src and o dst be two strings. x src o dst denotes x src taints o dst . Our notion of taint measures the similarity between two strings. It uses string distance functions.

We define more precisely our notions of taint in Definition 5 and Section 5.2.

Vulnerability and Exploit

A vulnerability is a fault leading to an error. If a fault is traversed by a taint flow, which is used to stimulate the fault, this will lead to a failure. Thus the problem of searching vulnerabilities can be addressed by searching for sinks, and then searching for inputs activating those sinks in a way prone to exhibit failures.

We are interested in vulnerabilities which violate the code integrity property. Such vulnerabilities arise due to confusion between data and code: the interpreter will consider attacker controlled data as code and thus execute it.

Cross Site Scripting (XSS) is a Web Command Injection vulnerability within the HTML grammar. An XSS permits attacker controlled code execution at client side. An example of sink for XSS is the PHP print() function: <?php print( $ GET['message'] ); ?>. For some malicious messages, once the client browser renders the webpage, the property stating that the content of the message variable should not be executed by the browser is violated.

An exploit is an input activating a vulnerability s.t. the application will violate a security property (in our case the integrity of the code executed at browser side, as it will execute a payload resulting of the input).

Within a given class, some vulnerabilities are more complex to find than others. The complexity of a vulnerability is an increasing metric w.r.t. the minimum number of traversed states of the control flow model to violate a security property. When searching for Web Command Injection, the filter (sanitizer) and the number of distinct traversed nodes in the control flow models are factors influencing the complexity of a vulnerability. When searching for Memory Corruption, the number of traversed jump instructions affects the difficulty in finding such vulnerabilities.

Web Application, Reflection, Syntactic Confinement, XSS

Figure 2.7 illustrates a Reflection (i.e., a taint flow from an input parameter value to an output). A reflection can be tracked (e.g., in white-box test context), or inferred (e.g., in black-box test context). We formally define a reflection in Definition 5.

DEFINITIONS CHAPTER 2. PROBLEM STATEMENT

Definition 4 Web Application (WA)

Let P be a set of page models, and I be a set of spiderlinks.

A Web Application (WA) W = (N, n 0 , T, I, P, Π) , is a graph:

• N is a set of nodes. n 0 ∈ N is the initial node of the application.

• Each transition t = (n a , i, n b ) ∈ T ⊂ (N×I×N).

• Π : N → P is a mapping which to each node n associates a page model p.

In Section 2.5.2, we elaborate on the reasons why we consider that a reflection only involves one taint source parameter. In Chapter 8, we provide insights on how to extend our work in the case of several taint sources.

Definition 5 Reflection

Let Σ be an alphabet. Let W = (N, n 0 , T, I, P, Π) be a Web Application (Definition 4). Let S I = [i 0 , .., i src (x src ), .., i dst ] be a sequence of spiderlinks (∈ I + ) and S O = [o 0 , .., o src , .., o dst ] (∈ Σ ++ ) the corresponding sequence of concrete outputs (trace). When submitting the input i dst , the obtained concrete output is o dst ∈ Σ + . Let δ ∈ N be a threshold. Let x src be an input parameter value received in the input i src of the source transition t src . The execution of S I on W terminates with t dst = (n s dst , i dst , n e dst ). (x src , t src , t dst , o dst ) is a δ-reflection if:

• x src taints o dst , there is a partial copy of length ≥ δ of x src into o dst i.e.,

∃y ∈ Σ + -|y| ≥ δ -(y ⊑ x src ) ∧ (y ⊑ o dst ), where x 1 ⊑ x 2 ⇐⇒ ∃x 3 , x 4 ∈ Σ * 2 , s.t. x 2 = x 3 x 1 x 4 • Π(n e dst ) = abstract(o dst )
We denote it as: (x src , t src ) δ (o dst , t dst ).

A sanitizer/filter is a mechanism at server-side which validates and eventually modifies (mutates) a fuzzed value before it is reflected.

Sanitizers may modify the input parameter values, e.g., by removing some characters having a special meaning in the considered grammar (e.g., (', ", > , <) in the HTML grammar for XSS vulnerabilities).

A common mistake when building such filters is to overlook the context of the reflection [Weinberger et al. 2011a] (for instance always applying a given string transformation regardless of where the reflection happens a.k.a. "Context-Insensitive Auto-Sanitization". This may result in a false sense of security, in which the CHAPTER 2. PROBLEM STATEMENT 2.2. DEFINITIONS developer believes to be protected from XSS, whereas the sanitizer is flawed [Weinberger et al. 2011a]. We illustrate an example of flawed sanitizer in Listing 2.3. Since filter/sanitizer may change significantly the fuzzed value before it gets reflected, we need to address the sub-problem: XSS.2 Achieving a Test Verdict →XSS.2.2 Can we exploit a potential sink? (i.e., find an input which bypasses the filter) How to infer the taint in the presence of filter?

Generating an input which is able to partially bypass the filter by partially being copied into the output is not a sufficient condition for a successful XSS exploit. Indeed, the reflected value has to "escape" the structure in which it was confined. We name this objective non syntactic confinement.

Figure 2.11 illustrates two reflections. The first one is syntactically confined according to the grammar (see the production rules in Figure 2.12), and the second one is not. Graphically, the first reflection is syntactically confined because there exists one non-terminal (TEXT) s.t. the whole produced sub-tree is tainted . This is not the case for the second reflection: the first common parent non-terminal of TEXT and SCRIPT is START, and its sub-tree is not fully tainted . [START_REF] Su | [END_REF], Wassermann 2008] formalized the problem of web command injection with the notion of Syntactic Confinement (Definition 6). We use the following notations: Let G = (V, Ω, S , R) be a context-free grammar with nonterminals V, terminals Ω, a start symbol S , and productions R. Let "⇒ G " denote "derives in one step" s.t. αAβ⇒ G αγβ if A→γ ∈ R, and let "⇒ * G " denote the reflexive transitive closure of "⇒ G ". If S ⇒ * G γ, then γ is a "sentential form".

Definition 6 Syntactic Confinement

Given an unambiguous grammar G = (V, Ω, S , R) (V non terminals, Ω is an alphabet of terminals, S a start symbol, R production rules), a word ω = ω 1 ω 2 ω 3 ∈ Ω * , ω 2 is syntactically confined in ω iff there exists a sentential form [ Heiderich et al. 2013] browser parser quirks induces transformations conform to the definition of the categories mentioned in Definition 9.

ω 1 Xω 3 such that X ∈ (V ∪ Ω) and S ⇒ * G ω 1 Xω 3 ⇒ * G ω 1 ω 2 ω 3 .

Fuzzing

Fuzzing is the automatic generation and evaluation of abnormal inputs in order to trigger the targeted vulnerability family(ies). Fuzzing is sometimes named as "act of software torture" [START_REF] Vuagnoux | Autodafé: an act of software torture[END_REF]]. The term was coined by [START_REF] Miller Barton | An empirical study of the reliability of operating system utilities[END_REF][START_REF] Forrester | An empirical study of the robustness of Windows NT applications using random testing[END_REF].

When searching for XSS in black-box, we will create fuzzed inputs from control and taint flows knowledge in order to escape the syntactic confinement of reflections. Thus we need to answer the following sub-questions: low: the best ones only detect 40% of non-filtered Type-2 XSS, and 1/3 do not detect any [START_REF] Bau | State of the Art: Automated BlackBox Web Application Vulnerability Testing[END_REF], Bau et al. 2012]. This is due to an imprecise learned knowledge [Doupé et al. 2012], imprecise test verdicts, and limited sets of attack values [Duchène et al. 2013b].

Thus there is a need for methods which detect Type-2 XSS (and server-side filtered Type-1 XSS) using a black-box test context.

Problem:

→ How to automatically detect Type-1 and Type-2 XSS in web applications, with a black-box test context?

Problems

According to the previous discussion, in order to effectively address XSS detection, the following sub-problems must be addressed:

• XSS.1 Navigating in the Application: In order to detect XSS in web application, we need to navigate in the application. Thus, we need information about the control flow of the application. The problem is that most deployed web applications lack formal documentation: a formal behavioral model, such as an FS (Definition 5), is rarely available. However, such models improve the ability to fuzz an application.

→ How to obtain a model of the application? What kind of models are appropriate for detecting XSS?

• XSS.2 Achieving a Test Verdict:

Server-side sanitizers may perform significant string transformations between the fuzzed value and the reflection. Since such reflections are hard to observe, there is a risk of false negative in the taint inference, thus in the test verdict. → How to perform a test verdict in the case of filtered reflections?

-XSS.2.1 Where are the potential sinks?

-XSS.2.2 Can we exploit a potential sink? How to infer the taint in the presence of filter?

• XSS.3 Creating Fuzzed Inputs: When creating fuzzed inputs, we need to answer the following sub-questions:

-XSS. The core of this thesis is the automatic black-box detection of vulnerabilities that permit attacker controlled code execution. Those include cross-site scripting.

Hypotheses on the Web application

• Reset: as we want to replay some input sequences, we assume the ability to reset the application in its initial state. Candidate solutions include applying a virtual machine snapshot, but also killing the application, restoring the database in its initial state and starting it again.

• Defensive Mechanisms: Since we are interested in finding XSS vulnerabilities with a black-box test context, and since the deployment of many counter-measures is very low as of today (for more details, see Table 8.1 in Chapter 8), we assume that the only counter-measure which may be present in the tested web application is server side sanitizer. We believe that our approach for addressing this problem (see Chapter 4 and Chapter 5) could also address situations when a Web Application Firewall (WAF) is present.

CHAPTER 3

Our Proposal

Nobody ever defended anything successfully, there is only attack, attack and attack some more.

Gen. George S. Patton ; Glad to see more and more companies/researchers selling 0Ds to Govs. Software vendors are losing the game but they are not yet aware of that.

[Bekrar 2013a]

As you've probably noticed, I'm basically lazy which is why I like fuzzing. [Miller 2010] The automatic detection of software vulnerabilities involve numerous combinatorial problems [Filiol 2013a]. This also holds for the automatic detection of XSS in a black-box test context. Due to these numerous problems and to the lack of formal knowledge, we propose domain-based engineering [START_REF] Czarnecki | [END_REF] approaches which use heuristics guided by the practical experience of penetration testers. Such approaches may not be sound, but still are safe to be used in practice.

In this chapter, we briefly justify our reasoning for addressing the aforementioned sub-problems.

Our approach for automatically detecting XSS in a black-box test context consists of two steps: "crawling" infers the control flow and the taint flows of the application, then "fuzzing" generates malicious inputs to exhibit vulnerabilities.

Control and Taint Flow Model Inference

Our first step constructs a model of the web application. This is achieved by a combination of crawling and taint analysis. In order to do this, we need to address the challenges XSS.1, XSS.2.1, and XSS.3.1, among those expressed in Section 2.5.1 (page 33).

• XSS.1 Navigating in the Application: [Doupé et al. 2012] showed that black-box WCI security scanners perform poorly due to a lack of precise knowledge about the applications they are testing. How to learn knowledge for driving the application? To answer these sub-problems, we propose a reverse engineering approach. Reverse Engineering is "the process of analyzing a subject system to identify the system's components and their interrelationships and create representations of the system in another form or at a higher level of abstraction" [START_REF] Chikofsky | [END_REF]]. Since we are in a black-box test context, reverse-engineering can be achieved by means of inference.

In order to address XSS.1, we propose an extension of [Doupé et al. 2012] for inferring the control flow of the application. Then, in order to address XSS.3.1, we propose to extend the previously obtained control flow model with a taint flow inference for indicating the reflections. The outcome is a hybrid control+taint flow model. Lastly, from this hybrid model, we generate input sequences fuzzing on a specific point and directing toward another point to observe, thus providing an answer to XSS.2.1. We summarize these choices in Figure 3 The main reasons are imprecise application behavior awareness (some scanners do not navigate properly, and do not observe the reflections), imprecise test verdict (e.g., Skipfish considers a page model change to be a sufficient condition for XSS), and limited set of fuzzed values (unaware of the output structure or the filters). Our approach overcomes the first limitation using a combination of control flow inference, taint flow inference and a guided fuzzing.

In step A in Figure 3. In order to address XSS. 3.3 How to prioritize inputs fuzzing?, the chopping step computes model slices (see Figure 3.3), and prioritizes them. Each slice is composed of a prefix and a suffix. For instance, the prefix [0 → 2, 2 → 7] and the suffix [7 → 17, 17 → 18, 18 → 21]. LigRE sends the prefix to the application, then pass the authentication credentials (e.g., cookie) to a fuzzer (e.g., w3af [Riancho 2011] or KameleonFuzz) and limits its scope to the suffix. Those slices permit to drive

EVOLUTIONARY XSS FUZZING CHAPTER 3. OUR PROPOSAL

the tested application toward the originating transition of an inferred reflection t src , and to constrain the fuzzing towards the transition t dst to observe the reflection.

Evolutionary XSS Fuzzing

Once we have a model, we use it for generating fuzzed input sequences. In the current section, we illustrate this fuzzing process. We address the challenges XSS.3.2, XSS.3.3 and XSS.2 (Section 2.5.1, page 33).

• XSS.3 Creating Fuzzed Inputs For addressing the question XSS.3.2 How to fuzz inputs?, we propose to reuse the hybrid control+taint flow model. Indeed such models notably provide information about the reflection context (e.g., the HTML structure of the reflection: outside a tag Hello Lakitu ). Fuzzing exists with various flavors: random, anomaly operators, grammar-based. Since successful XSS exploits need to respect some HTML constraints, we choose to generate fuzzed values with an attack grammar. Thus the search space is composed of the reflections and the attack grammar.

For addressing XSS.3.3 How to prioritize inputs fuzzing?, we can use metrics such as the rarity of a reflection, and the "injection power" of a reflection (e.g., how many different grammar meaningful HTML constructs are reflected?). We integrate such metrics in the fitness function of a genetic algorithm which captures characteristics of the best inputs and evolves them.

CHAPTER 3. OUR PROPOSAL

EVOLUTIONARY XSS FUZZING

• XSS.2 Achieving a Test Verdict The input sequence includes point(s) where to observe the effect of a fuzzed input. Those are outputs of the web application. Several Black-box scanners, e.g., [START_REF] Zalewski | SkipFish -web vulnerability scanner[END_REF], Riancho 2011], only search for a verbatim reflection (exact string recopy) in the HTML code present in the body of an HTTP Reply. As this does not provide enough information about the ability to execute attacker controlled code, these scanners are likely to obtain fuzzy test verdicts. Indeed, server-side sanitizers may significantly transform fuzzed inputs when reflecting them. Thus, in order to achieve a test verdict, it is necessary to obtain the taint information associated with "how the browser parsed the output". A candidate solution is to obtain taint information up to the browser parse tree. However, since we are in a black-box context and want to find XSS exploits for real-world browsers, we cannot propagate the taint as [Sekar 2009] did with his home-written browser. Thus we propose to use taint inference techniques to obtain this information.

We illustrate these choices in Figure 3.4, and develop this second part of our approach in Chapter 5.

D.1.

Malicious Inputs Generation

Inputs Evolved by Genetic Algo. Example We describe the execution of LigRE+KameleonFuzz on P0wnMe (page 18). We here focus on KameleonFuzz, once LigRE has inferred the con-trol+taint flow models and generated input sequences. Figure 3.2 contains a reflection for the value 2 e g a s sem of the parameter message2 sent in the transition 7 → 33. An extract of the output O dst is: <input name="message2" value=' 2 e g a s sem '/> where we highlight the reflection. Here, the reflection context is inside a tag attribute value. The context influences how an attacker generates fuzzed values. Listing 3.1 shows the server sanitizer for this reflection. It blocks simple attacks. Attackers search a fuzzed value s.t. if passed through the sanitizer, then its reflection is not syntactically confined in the context [START_REF] Su | [END_REF] i.e., it spans over different levels in the parse tree. 3.1 were affected by the filter described in Listing 3.1, and w3af considered this reflection not to be dangerous (false negative in vulnerability detection). Only the input value composed of characters having no special meaning in HyperText Markup Language (HTML) or JS (i.e., ∈ a -Z ) were not filtered. We illustrate in the following table the only reflection that w3af obtained.

EVOLUTIONARY XSS FUZZING CHAPTER 3. OUR PROPOSAL

Fuzzed Value (x src )

Reflection SySlw SySlw uI<hf>hf"hf'hf(hf)uI XSS attempt!  '';!--"<klqn>=&{()}  The chopping (step C of LigRE, illustrated in Figure 3.3) produces input sequences containing at least one reflection.

In step D.1, KameleonFuzz generates individuals, i.e., input sequences in which it fuzzes the reflected value by replacing the input parameter value by a word generated from the Attack Input Grammar (AIG). For each individual, the corresponding outputs are recorded and the taint is inferred between the fuzzed input value and the concrete output, but also between the tainted substrings of the concrete output and the nodes of the browser parse tree. This taint aware tree is an input for the test verdict (did this individual trigger an XSS?) and the fitness score (how close is this individual to triggering an XSS?). The best individuals are genetically recombined while still conforming to the AIG to create the next generation: e.g., the individuals 3 and 4 of generation 1 produce the individual 1 of generation 2. This process is iterated until a tester defined stopping condition is satisfied (e.g., one XSS is found).

= 7→33)(message)→(t dst = 7→33)
The sanitizer in Listing 3.1 removes the space , but not \t,\r or \n. An extract of the output o dst for the last individual is <input name="message2" value=' WUkp'\t onload='alert(94478) '/> Using string edit distance and a threshold, the taint is inferred between the tainted substrings of o dst and each node of the parse tree obtained from a browser. This produces a Taint-Aware Tree (TAT), as illustrated in Figure 3.5. This example illustrates how evolutionary input generation can adapt to sanitizers.

CHAPTER 4

Web Application Model Inference for Black-Box XSS Detection

We think too small, like the frog at the bottom of the well. He thinks the sky is only as big as the top of the well.

If he surfaced, he would have an entirely different view.

Mao Zedong

XSS involve both control and taint flows, as they rely on an input value being partly copied to a transition output. Thus, our approach for automatically detecting XSS in black-box consists of two steps: "crawling" infers the control and taint flow of the application, then "fuzzing" generates malicious inputs to exhibit vulnerabilities. In the current chapter, we focus on the first step, components A, B and C of During step A of Figure 4.1, LigRE learns the control flow of the application, using a state aware crawler, to maximize coverage. During step B, LigRE annotates the inferred model with observable taint flows of input values into outputs to produce a control plus taint flow model. Annotations flow from a source t src to a potential sink t dst . We use an heuristic driven substring matching algorithm for its efficiency and as filters impact is generally low on reflections on non malicious input parameters values.

After step B, we prioritize the most promising annotations. For each of them, step C produces a slice of the model. Slices are chopped models. They permit to drive the application to the origin of t src , for sending a malicious value x src , and then to produce inputs guiding a fuzzer to navigate towards t dst , for observing the

Control Flow Inference

Step A in Figure 4.1 takes as input the description of a remote web application (e.g., interface, authentication credentials), interact with it, and outputs a control flow model (CFM). A CFM formalizes the observable behavior of a web application in a black-box test context. Nodes (states) represent webpages and transitions represent requests and associated responses. However, storing only the aforementioned information is not sufficient for constructing a precise model since the web application may have internal macro-states (e.g., new user created, logged-in, logged-out, etc.). We capture this notion of macro-states by adding colors to nodes, as in [Doupé et al. 2012].

The control flow inference step uses heuristics to identify which request changed the macro-state (Section 4.2.3), chooses the next request to be performed (Section 4.2.4), and assess the degree of certainty in the model (Section 4.2.5.1). The model is iteratively built.

Non-Deterministic Values (NDV)

In the process of abstraction, some parameters are omitted: NDV a.k.a. nonces [Wikipedia 2006], i.e., output parameters whose values differ when sending twice a given input sequence (and resetting the system in between) and which may be used in subsequent inputs. Examples of NDV include: anti-CSRF tokens [OWASP 2013a], session id stored in cookies [Barth 2011], view states [Microsoft 2004]. In the presence of NDV, crawlers achieve a limited coverage. More important, since we are interested in building a Control Flow Model of the tested application, the presence of NDV may change the abstracted output, thus resulting in a state explosion, whereas the execution reached a previously encountered state.

We address this problem by requiring the human tester to identify NDV. In order to do so, the tester has to observe which parameter values in a page model For instance in Figure 4.2, when the tester submits twice the same input GET /, while resetting the application in between, the part of the page model corresponding to the parameter lt has a different value the second time, thus lt is a nonce. Thus, for each NDV name, the tester has to execute twice at least one given transition. 1For one given transition, detecting NDV may seem easy according to the previous example, assuming the knowledge of a complete control flow model. However, during the control flow inference, the complete model is not yet available and is being inferred. Determining both the control flow model and the NDV are two connected problems: not identifying NDV may lead to parts of the model being duplicated, and identifying NDV requires the ability to navigate to a transition which contains one. However, our inference algorithm is not able to solve them both simultaneously. Thus we require the tester to identify NDV.

Tester Provided Values The tester may also provide values for extending the page models and thus generating new spiderlinks (e.g., a special login value for a field named uid in a specific DOM path).

Overview

Algorithm 4.1 shows the inference of a control flow model from a web application. The control flow inference step infers partial control flow models (not necessarily completely specified for each input).

Until a tester defined multi-criterion stopping condition is met (e.g., number of requests, duration, number of different pages seen, number of macro-states, etc.), LigRE iterates the following process (line 8).

LigRE resets the web application to its initial state using a tester written script. The first spiderlink to be chosen is the start input (generally GET /). LigRE sends the concretization of the current spiderlink to the web application, and abstracts the corresponding application output (HTTP reply) to a page model.

LigRE then consults the history plus the current spiderlink and page to determine if the macro-state has changed since the last time the same spiderlink was sent (line 15). If this is the case, LigRE determines which spiderlink in the history changed the state (line 17), thanks to the score heuristic (see Section 4.2.3). The identifiers of each history entry are updated, and the colors of the macro-states are computed (line 21 consists in merging identical macro-states).

LigRE updates the history by storing the spiderlink and the page model. LigRE then updates the control flow model w.r.t. the new information in the history (line 25).

A new spiderlink is chosen in the ones available in the current page model. If none is available, or if the current input sequence is longer than the maximal length allowed by the tester, LigRE resets the web application, and builds a new sequence following the aforementioned process by choosing the start spiderlink. The exploration is thus a Depth First Search (DFS), until a contradiction is detected, or a sequence of maximal length has been produced.

Similarly, when a contradiction is detected for a given macro-state, and the confidence of the color not already chosen for the macro-state is higher than the one in the control flow model, then we backtrack, undoing the latest macro-state change, and reset the application and start a new input sequence.

LigRE makes use of heuristics, because the problem of determining macrostate is addressed on the fly during the navigation problem.

Macro-State

Macro-state is an important notion for understanding the control flow of a web application. It designates "anything that influences the executed code at server side" [Doupé et al. 2012]. Both nodes and macro-states represent the current execution context of the web application. They differ in their granularity. A node is characterized by a page (i.e., the last output). Whereas a macro-state is a set of nodes, i.e., at a higher level of abstraction, and is characterized by a common behavior of these nodes. Definition 10 formalizes this notion.

Definition 10 Macro-State

Let W = (N, n 0 , T, I, P, Π) be a Web Application (Definition 4).

A macro-state is a set of nodes which is coherent w.r.t. its successor nodes.

Let C ⊂ N be a set of colors. Let col : N → C be a coloring function which associates a color to each node. We say that col is a valid macro-state coloring iff, for any n a , n b ∈ N, col(n a ) col(n b ) whenever any of the following conditions hold:

• ∃i ∈ I, ∃(n c , n d ) ∈ N 2 s.t. (n a , i, n c ) ∈ T ∧ (n b , i, n d ) ∈ T ∧ Π(n c ) Π(n d ) • {Π(u)|∃i ∈ I, (n a , i, u) ∈ T } ∩ {Π(u)|∃i ∈ I, (n b , i, u) ∈ T } = ∅ If col is such a coloring, for each c ∈ C, the set of nodes N c = {n ∈ N, col(n) = c} is a macro-state.

Control Flow Model (CFM) (model)

A CFM is a Web Application with colors (i.e., macro-states). It is defined in Definition 11. The nodes and continuous arrows of The Navigation Tree (history in Algorithm 4.1) is a set of traces. It is a prefix tree which contains the sequences of abstract inputs (spiderlinks) and outputs (page models). This navigation tree is an auxiliary structure for building the CFM.

Macro-State Change Detection

As the stopping criterion will halt exploration before the Web Application is fully explored, our inferred model is not completely specified. This holds for the step A (control flow inference), but also for the step B (taint flow inference).

We build the CFM iteratively in step A, using a DFS exploration, so we need to characterize the current macro-state after each request. In order to do it, we need to address four sub-problems: Did the macro-state change? Which request changed the macro-state? What is the current macro-state? Which link to pick next?

In order to alleviate the computational complexity, we address these subproblems using heuristics, inspired from [Doupé et al. 2012]. We added parameters in Table 4.1 and Table 4.2, and adjusted their weights using results from experimentation by observing which combinations increased the efficiency of the control flow inference. ?? details the dimensions and the rationale behind each dimension. The following dimensions compose the heuristic of Table 4.1:

Example

• 1. Number of input parameters: the more inputs parameters for a given spiderlink, the more likely it will change the macro-state (e.g., when creating a new user in an application).

• 2. Distance between page models: the more distinct are the page models of i and i prev , the more likely they correspond to nodes in different macrostates. Due to its effectiveness, we use the PQ-gram distance for measuring the similarity between page models [START_REF] Augsten | [END_REF]].

• 3. HTTP method : a POST method is more likely to change the macro-state than a GET method, thus it will have a higher score.

• 4. Number of times performed (total): number of times that this spiderlink has already been sent. Our navigation strategy prefers request that permit determining a macro-state change, but not request that actually do change the macro-state. Thus a frequently sent spiderlink is not very likely of having changed the state.

• 5. Number of times this spiderlink changed the state : since we are using heuristic functions, we want to be error tolerant, that is if once we determined that a given spiderlink changed the macro-state, we want to decrease the likelihood of repeating this error.

• 6. Number of requests between i and i detec : since our navigation strategy prefers requests that help determining a macro-state change, it is likely that we detected a macro-state change early, that is that i detect is probably close of the spiderlink that changed the macro-state.

• 7. Number of potential contradictions (approximative): if we hypothesize that i changed the macro-state, how many potential contradictions would we have? It is likely that choosing a wrong spiderlink as the reason for a macro-state change would increase the number of contradictions.

The final score is a weighted linear sum of each dimension.

What is the macro-state of the current node? (compute colors)

The current node is the result of the submission of the spider-links since the last reset. In order to know if the current node is one previously encountered, it is necessary to merge macro-states.

For this purpose, an identifier is associated to each node. If the macro-state changes, then the current identifier is updated to a one different of the preceding node, it is unchanged otherwise (see Algorithm 4.1). [Doupé et al. 2012] reduced this macro-state collapsing problem to the coloring of an undirected graph of identifiers [Doupé et al. 2012]. If there is an edge between two identifiers (e.g., A and B), then they will have different colors, otherwise they will be merged (e.g., B and D identifiers are merged in the same color B + D in Figure 4.4). There are four rules to add an edge between two identifiers / macro-states α and β:

• Rule1: there is a macro-state change from α → β or β → α (e.g., A→B, B→C, C→D etc.)

• Rule2: they have no common pages (pages(α) ∩ pages(β) = ∅) (e.g., A and C)

• Rule3: if ∃ a spiderlink i, and identifiers γ, δ, s.t.

by executing i when the application is in the macro-state color(α) drives it to the macro-state color(γ): α(i) → γ and by executing i when in the macro-state color(β) it leads to a macrostate color(δ): β(i) → δ and the reached macro-states are different: color(γ) color(δ) -... then it means that α and β should not be mapped to the same macrostate: color(α) color(β) After obtaining a page model p, LigRE must decide what is the next spiderlink in spiderlinks(p) to explore. The heuristic function navigating represents the likelihood of a spiderlink to be chosen as the next one to be executed on the application. For a given spiderlink i, the higher the value of navigating(i), the more likely i will be picked. The dimensions of Table 4.2 model the several intuitions:

• 1. Request Never Executed: we want to increase the knowledge of the application.

• Some spiderlinks may be more likely to be picked up, as they permit detecting a state change (2.

(1+consecutive contradictions)*num detect state change). However, we do not want that only those are choosen, thus we temporarily introduce a penalty if they have been recently picked (3. Number of Times Recently Sent).

• 5. Number of Times Sent: we want to favor less explored spiderlinks.

• 4. number of artificially generated parameter values, 6. spiderlink method weight and 7. number of times it changed the macro-state: we want to explore as much as possible of the current macro-state before exploring the next one. Thus, since POST requests are statistically more likely to change the macro-state than GET requests (e.g., user creation, user login), navigating is a decreasing metric w.r.t. this dimension.

As illustrated in Algorithm 4.4, either the current node contains unexplored spiderlinks and one of them is chosen according to their navigating score, or the shortest path in the model to nodes containing non explored spiderlinks is computed using [START_REF] Dijkstra | [END_REF]]'s algorithm. The stopping criterion evaluates to true when for each node of the CFM, the outgoing transitions have been explored a tester defined number of times. The tester can limit the number of requests and the execution time. In our experiments, we limit the number of sent requests. We adjust this metric by iteratively, browsing manually the application, setting a limit, inferring a control flow model, observing the obtained CFM, and eventually adjusting the number of requests. We adjusted this metric depending on the tested web application (e.g., for P0wnMe , we limit to 60 requests, whereas for Gruyere, we limit to 200). Adjusting this metric is a trial and error process, which converged around 25 iterations for the first tested applications to around 8 for the most recently tested ones.

Pruning

Testers may want to prune the model for readability, speed, or desire to concentrate the testing effort in one part of the application. This process is known to reverse engineers of binary executables [START_REF] Guilfanov | Ilfak Guilfanov. Decompilers and beyond[END_REF]]. LigRE permits to specify pruning patterns in order not to explore matching spiderlinks.

In Figure 4.5, we illustrate one pruning pattern. A pruning pattern matches DOM tree nodes, in order to prevent LigRE to build spiderlinks for the  or <FORM> DOM nodes containing in the subtrees matched by this pattern.

In Figure 4.6 we illustrate the impact that pruning has on the obtained CFM, specifically for WebGoat [OWASP ], a deliberately vulnerable JSP web application (see Table 6.1 in page 91). We want to focus the testing on one particular WebGoat "lesson": "Stored XSS".

We define pruning patterns manually specifically for each web application we want to test.

Artificial Spiderlink Creation

Depending on tester defined configuration, LigRE may create spiderlinks that contain artificially generated values (i.e., which are not present in the page models). This value creation aims at limiting the risks of collisions and false positives during the later taint flow inference.

We want a function artif that receives an input parameter name (e.g., msg in Figure 3.2) and produces a value s.t. the following properties hold for "most" input parameter names:

• it is easy to compute artif(name) First LigRE Run: Initially Produced CFM after 60 requests: only one macro-state is detected, because only the very first transitions from the root node are explored.

Second LigRE Run: Produced CFM with pruning after 60 requests. As LigRE explore deeper parts of the application, it discovers a new (red) macro-state. In our implementation, we use our own function which creates parameter values by reversing the parameter name and by alternating characters from the reversed input parameter name and an extension string (may be tester provided, we hardcoded default ones ; should not contain "special" HTML characters such as {',",>,/}), as illustrated in Table 4.3. This has the advantage of permitting a human tester to visually identify the tainted parameter source. For two given input parameters having the same name, our technique voluntarily generates the same value, even if they originate from different transitions in the CFM.

Param. Name Extension

Confidence

The Confidence expresses the level of trust in a part of the model. This metric is applicable to a node or a transition. The higher its value, the more confident we are in the coloring of the element. We hypothesize that the web application is deterministic at the abstract level: if an input sequence of spiderlinks from the start node is executed several times, the sequences of obtained page models are the same.

contradiction(n a , n b ) =                T rue if ((con f idence(n a ) con f idence(n b )) ∧(page model(n a ) == page model(n b )) ∧(color(n a ) color(n b )))
Each sent spiderlink is executed on the application, and on the currently inferred CFM. It may happen that the CFM execution leads to a different page model than the application one. This is a non-determinism: either the application is not deterministic (and the tester missed a nonce in the abstraction process), or the current CFM is not correct. We assume it is the second case.

In such a situation, our heuristic assumes that the ultimate macro-state change was not correct: we considered the identifiers α and β to map to the same macrostate, but this turned out to be wrong. Thus, we add an edge between α and β (such edges are used in the compute rule 4() of Algorithm 4.2), redo the coloring and update of the model, reset the application, and start a new sequence from the initial node. This step consists of first generating walks in the CFM, and then actively submitting those walks to the web application while inferring observable taint flows.

Taint Flow Model Annotations

During this step, only taint flows are added to the CFM, no transitions are added or removed, even though a precise analysis may discover new macro-states. This is a choice of our implementation.

We compute the control flow inference (step A) and the taint flow inference (step B) separately. The reason is that until step A (control flow inference) is finished, we are unsure whether the execution context of the application leads to a node for which we already inferred the taint. Thus performing control and taint flow inference separately permits to only compute the taint when necessary. This

TAINT FLOW INFERENCE CHAPTER 4. INFERENCE FOR XSS

is important, as on the tested applications, the taint flow is inferred significantly more often than the control flow inference.

Definitions

Reflection Context and CTFM are defined respectively in Definition 13 and Definition 14. The taint-flow computation is explained in Section 4.3.3.

A reflection context is the output structure in which a reflected input value is supposed to be confined (Definition 6) during the processing of a non-malicious input. We list several reflection contexts in Table 4.5, and formally define this notion in Definition 13. outside an HTML tag
 inside an HTML src/href attribute value  inside a non src/href HTML attribute value <input value=" "/> Let G be a grammar (e.g., HTML), CT X be a set of reflection contexts (Table 4.5), o dst ∈ Σ * be a concrete output and a word of G, and v ∈ Σ * be a non-empty substring of o dst .

The reflection context ctx(v) ∈ CT X is the narrowest structure in G (nonterminal production rule) in which the reflected value is confined when sending non fuzzed values. If G is context-free, then ctx(v) is the smallest word in G containing v and derived from one unique terminal.

Generating Walks

Random walk and Breadth First Search (BFS) are the implemented strategies for generating inputs from a CFM. The submission of those inputs is performed in a DFS manner. Since we generate identical values if the same parameter is present in several transitions, we want to reset the application frequently enough to avoid over-tainting. Our input sequence creation strategies limit the length of the input sequences, and the number of times the sequences traverse each node. If a sequence is a prefix of another one, then we only keep the latter. We analyzed XSS on

Computing Taint Flows

For each sequence I = (t 1 , ..., t k ), for each concrete output o j , j ∈ [1.

.k], for each previously sent input parameter value x m , m ∈ [1.

. j], a distance between x m and o j is computed. Specifically, the taint flow inference consists in first searching in the output o j for exact substrings of x m of a minimal length, marking those found substrings, clustering them, and then computing the edit distance [START_REF] Levenshtein | VI Levenshtein. Binary coors capable of correcting deletions, insertions, and reversals[END_REF]] from x m to the clusters. If this distance is lower than an empirically determined threshold, then a taint flow is annotated on the CTFM. [START_REF] Jackson | [END_REF], which captures this relation.Our chopping consists in a shortest sequence of transitions (also called path) starting with t src and ending on the originating node of t dst . We use [START_REF] Dijkstra | [END_REF]]'s algorithm for computing such paths on CTFM. Figure 3.2 illustrates a CTFM produced by step B. If the targeted reflection is t dst = (7 -(msg)→17)) and t dst = (18→21), then an example of slice for this reflection is illustrated in Figure 3.3.

Reflection Prioritization

Implementation

The approach is implemented as a tool LigRE containing approximately 8000 SLOC of Python3.2. Figure 4.9 represents its architecture. KameleonFuzz (Chapter 5) extends LigRE by incorporating a new fuzzer. During the control flow inference, the parse tree (approximated by a subset of the Document Object Model (DOM)) is obtained using the selenium library [Huggins et al. ] which instruments the Google Chrome browser to parse HTTP replies. During the taint flow inference, requests are performed directly to the web application. During the fuzzing, LigRE drives the application in the source via the prefix slice ; it then parameterizes the suffix slice for a fuzzer (w3af [Riancho 2011] or KameleonFuzz Chapter 5). In order to configure LigRE for an application, the tester has to write a config.xml file (an extract of such a file is illustrated in Listing A.2 in page 142) which contains informations about the interface (e.g., Domain Name System (DNS) Fully Qualified Domain Name (FQDN), Transmission Control Protocol (TCP) port, baseHREF, etc.), a link to the tester written reset script, the stopping condition, the nonces in the web application, and eventually some pruning patterns if the tester wants the efforts to be concentrated in specific parts of the application. The tester can also adapt the weight of the dimensions in our heuristics, altough it should not be necessary to them for applications similar to the ones on which we experimented. Based on [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]]'s L*, [START_REF] Shahbaz | [END_REF]] designed an algorithm for iteratively inferring the control flow of an I/O system. [Cho et al. 2010] infer a botnet protocol by adding a prediction heuristic to [START_REF] Shahbaz | [END_REF]. [START_REF] Hossen | [END_REF]] automatically generate test drivers for non-Ajax web applications.

IMPLEMENTATION CHAPTER 4. INFERENCE FOR XSS

Reflection

[ Doupé et al. 2012] showed that improving control flow inference increases vulnerability detection. LigRE shares similarities with their macro-state-awarecrawler. Differences lay in the heuristics, the introduction of confidence, contradictions, backtracking, and taint flow inference. [Doupé et al. 2012] run experiments on a local cloud, whereas we run ours on a laptop. [Dessiatnikoff et al. 2011] cluster pages according a specially crafted distance for SQL injections [Dessiatnikoff et al. 2011]. [Marchetto et al. 2012a] dynamically infer the control flow of Ajax web applications [Marchetto et al. 2012a]. They wrote abstraction functions for common Ajax primitives. [START_REF] Tonella | [END_REF]] use genetic algorithm for finding the right balance between over and under-approximations of CFM [START_REF] Tonella | [END_REF].

RELATED WORK CHAPTER 4. INFERENCE FOR XSS

LigRE does not make use of L* (because of the NDV, the macro-states which leads to enormous state machines) and is driven by heuristics. It clusters pages according to the notion of macro-state. The current implementation supports non-Ajax applications or Ajax applications which downgrade gracefully.

Taint Flow Inference

W3af [Riancho 2011] and XSSAuditor [Bates et al. 2010](Chrome XSS filter) assume the fuzzed input value to be reflected without modification, and thus rely on exact string matching. This may lead to false negatives when input values are transformed [Heiderich et al. 2010, Duchène et al. 2013b]. Skipfish generates three variants for a spiderlink, and assumes there is a taint flow if the response varies [START_REF] Zalewski | SkipFish -web vulnerability scanner[END_REF], Dessiatnikoff et al. 2011, Doupé et al. 2012]. This may lead to false positives, if the scanner is not aware of a macro-state change.

[ [START_REF] Sun | [END_REF]] compute a string edit distance [START_REF] Levenshtein | VI Levenshtein. Binary coors capable of correcting deletions, insertions, and reversals[END_REF]]. [Sekar 2009] proposed a filtering algorithm inspired from bioinformatics for improving the efficiency of [START_REF] Levenshtein | VI Levenshtein. Binary coors capable of correcting deletions, insertions, and reversals[END_REF]]'s distance.

LigRE relies on a filter-tolerant substring matching of a minimal length, and computes the edit distance on a smaller output. LigRE relies on the fuzzer test verdict.

Control and Taint Flow Inference (CTFM)

[ Caselden et al. 2013] use similar models, named Hybrid Control Flow Graph (HI-CFG) on basic blocs, to automatically generate exploits for memory corruption vulnerabilities in binary programs with a grey-box test context. Netzob infers protocols implementations using L*, and enhance it with taint flows w.r.t. equivalence, size, or repetition relations. Its test driver, abstraction, and concretization functions are written by an analyst [START_REF] Bossert | [END_REF]. With PRISMA, [Krueger et al. 2012b] infer control and taint flow Markov models of botnet protocols from traffic captures. LigRE targets XSS, a command injection vulnerability, in web applications with a black-box test context, and produces CTFM to drive a fuzzer. 4.6.4 Search for Parts of the Inputs where to Focus the Testing [START_REF] Haller | Dowsing for overflows: a guided fuzzer to find buffer boundary violations[END_REF], [START_REF] Rawat | [END_REF], [DeMott et al. 2012a], and [START_REF] Bekrar | A Taint Based Approach for Smart Fuzzing[END_REF], Bekrar 2013b] statically search for potential sinks and then dynamically generate inputs targeting those potential sinks. [START_REF] Stock | 25 Million Flows Later -Large-scale Detection of DOM-based XSS[END_REF], Duchène et al. 2013a] dynamically propagate white-box taint flows to prioritise DOM-XSS tests. [Cadar et al. 2008b] uses symbolic execution for generating inputs s.t. each branch of an application is activated at least once by one input. [START_REF] Grégoire | Dumb-fuzzing XSLT engines in a smart way[END_REF]] fuzzes third party code, and then generate inputs for applications which integrate such code (e.g., Acrobat Reader).

[ Mulliner & Miller 2009] fuzzed the iOS SMS service by sending messages through the baseband and modifying them before they reach the iOS service.

Conclusion

LigRE automatically partially reverse-engineers web applications as a control and taint flow model. It prioritizes model slices to guide the scope of the fuzzing.

Heuristics drive LigRE. Empirical experiments show that LigRE detects more XSS than open source and control flow aware scanners (see Section 6.2).

In addition of being an input for human penetration testers, the obtained models can be the first step for automated vulnerability detection: e.g., if provided to a model checker or a fuzzer. For instance, our evolutionary smart fuzzer Kame-leonFuzz [START_REF] Duchène | [END_REF], Duchène et al. 2013b] can use such models, and improves the fuzzing step of LigRE to detect more complex filtered XSS.

We observed there are two main reasons for false negatives: first the fuzzers neither adapt to the reflection context nor to the server sanitizers, and second they have an imprecise test verdict. We address those issues in Chapter 5. Fuzzing is normally limited to finding obvious symptoms like crashes, because it's rare to be able to tell correct behavior from incorrect behavior when the input is generated randomly.

[Ruderman 2014]

Introduction

Context

XSS detection is a problem involving control+taint flows, and input sanitization. In presence of even basic sanitizers, many scanners have difficulties in creating appropriate inputs, and thus produce false negatives. In Chapter 4, we addressed the automatic reverse-engineering of control+taint flow models. In the current chapter, we focus on how to generate malicious inputs targeting the potential sinks. We address the following problems of Section 2.5.1 (page 33): XSS. 3

.2 How to fuzz inputs? How to act on specific parts of those inputs? XSS.3.3 How to prioritize inputs fuzzing? Which potential sinks should we test first? XSS.2.2 Can we exploit a potential sink?

In order to address these issues, we propose KameleonFuzz, a fuzzer which mimics a human attacker by evolving and prioritizing the most promising malicious inputs and taint flows obtained from LigRE. We incorporate in KameleonFuzz a test verdict that relies on existing browser parsing and double taint inference.

The KameleonFuzz Approach

KameleonFuzz is a black-box fuzzer which targets Type-1 (reflected) and Type-2 (stored) XSS (see Definition 8) A Genetic Algorithm (GA), parameterized by an Attack Input Grammar (AIG), evolves individuals (malicious inputs). The AIG reduces the search space and mimics the behavior of a human attacker by constraining the mutation and crossover operators which generate next generation inputs. We define a fitness function that favors most suitable inputs for XSS attacks. Since server sanitizers may alter the observed value at the reflection point O dst , a naive substring match may not infer the taint precisely enough, which could lead to false negatives. To overcome such limitations, we perform a double taint inference. The GA iteratively evolves the best individuals of the current generation, according to their fitness score, and recombines them to produce the next generation of individuals.

Evolutionary XSS Fuzzing

The fuzzing (step D in Figure 5.1) generates a population of individuals (Genetic Algorithm (GA) terminology). An individual is an input (sequence of HTTP requests) generated by LigRE (line 7 of Algorithm 5.1) in which KameleonFuzz generates a fuzzed value x src according to an Attack Input Grammar (AIG) for the reflected parameter (see line 15 of Algorithm 5.1). Inputs are concretized, sent to the application, and the corresponding outputs are recorded. Then a precise taint inference between the fuzzed value and the browser parse tree is performed in line 18. Each individual which did not find a vulnerability (test verdict of line 19 evaluates to false) is evolved via the mutation and crossover operators (Section 5.2.6, line 25 and 28 of Algorithm 5.1) w.r.t. the AIG (Section 5.2.1) and according to the fitness score (Section 5.2.5, line 22 of Algorithm 5.1).

Attack Input Grammar (AIG)

Traditional fuzzing for memory corruption consists in the application of anomaly operators on a set of bits (e.g., expanding a string, setting an integer to INT32 MAX, etc.). This does not work when fuzzing for Web Command Injec-

EVOLUTIONARY XSS FUZZING CHAPTER 5. GA XSS FUZZING

tion, as first the risk of memory corruption is low on web applications, and secondly when searching for XSS, the reflection must fit a certain output structure (i.e., reflection context, Definition 13). Thus, in order to constrain the search space (i.e., avoid to search in the complete space Σ * ), we use an Attack Input Grammar (AIG) for generating fuzzed values. It represents parameter values an attacker would attempt to the application. As compared to a list of payloads as in w3af and Skipfish, an AIG can generate more values, and is easier to maintain thanks to its hierarchical structure. This AIG also constrains mutation and crossover operators (lines 13, 25, 22 of Algorithm 5.1).

The knowledge used to build an AIG consists of the HTML grammar [W3C 2012b], reflection contexts (Definition 13), string transformations in the case of context change [Weinberger et al. 2011a We only give a taste of how to build an AIG, as it is yet manually written and its automatic generation is a research direction. Figure 5.2 illustrates its structure. The first production rule consists of representation and context information. Example of contexts (Definition 13) include (<input value=" "/>) and outside a tag (
 ). The representation consists of encoding, charset, and special string transformation functions that we name anti-filter (e.g., PHP addslashes [PHP ]). In our experiments it was sufficient to use UTF-8 encoding. However, variable length encoding such as UTF-7 [Goldsmith & Davis 1997], Shift JIS [Microsoft b], etc. may be of interest when the webpage does not specify any encoding to use.

We assume the availability of a representative set of vulnerable web applica- In our experiments, we used the same AIG for the tested web applications. Due to a minor limitation of the current implementation, we sometimes pruned some production rules, for the search space to be narrowed, and thus the fuzzing to be faster (this can be automated easily, as it only consists of selecting the production rules for a given reflection context). We think that one unique AIG can be used when searching for Type-1 and Type-2 XSS and assuming a specific set of filters and of reflection contexts (Definition 13).

Individual

An individual is an input sequence targeting a specific reflection. It is composed of an input sequence as a walk in a LigRE chopped model (Section 4.4.3), and of a fuzzed value x src generated from an AIG. This input encompasses the originating transition t src of a taint flow, and the transition where to observe the reflection t dst . We define an individual in Definition 15.

Definition 15 Individual

Let M be a CTFM (Definition 14), let (x src , t src , t dst , o dst ) be a reflection (Definition 5) from the transition t src for the value x src of the parameter name(x src ).

An individual I = (i 0 , . . . , i n ) is an input sequence s.t. :

• ∃ j, k ∈ [0. . .n], j ≤ k and t src is activated by i j and t dst is activated by i k

• the value of the input parameter name(x src ), sent as part of i j in t src , is produced by the AIG.

Precise Taint Flow Inference (D.2)

When fuzzing, server side sanitizers may filter fuzzed input parameter values. Thus we have to infer the taint again, and cannot only rely on results from the taint annotation in step B (Section 4.3). Moreover, we want to answer the questions The precise taint flow inference permits obtaining information about the context of a reflection. This later will serve for computing test verdict, and as an input for the fitness function. The flow for producing a Taint Aware Tree (TAT) T T dst is shown in Figure 5.4. We illustrate a TAT in Figure 5.6 and define it in Definition 16. First, a string to string taint-inference algorithm (e.g., with the [START_REF] Levenshtein | VI Levenshtein. Binary coors capable of correcting deletions, insertions, and reversals[END_REF]] edit distance) is applied between the fuzzed value x src and the output o dst in which it is reflected. This first step results in Figure 5.5. In parallel, a parser (e.g., from Google Chrome) evaluates the application output o dst and produces a parse tree DOM dst (e.g., a Document Object Model (DOM)). Then the taint is inferred between each tainted substring of o dst and each node of DOM dst to produce a TAT T T dst (see Figure 5.6), as follows.

Parsing

String taint inference

<input name="message2" value=" WUkp" onload="alert(94478) " /> For each node of an output parse tree DOM dst , we compute a string distance between each tainted substring and the node textual value. Then we only keep the lowest distance score. If this score is lower than a tester defined threshold, then this node is marked as tainted. This taint condition may be slightly relaxed in the case of a cluster of neighbors nodes has a distance "close to the threshold". The inferred TAT T T dst (e.g., Figure 5.6) is an input for the fitness function and test verdict.

The data flow from the sending of a fuzzed input parameter value to its reflection within a parse tree node involves at least two transformations (if omitting the transformations due to the encoding): a filter / sanitizer at server side, and the parsing by the browser of the concrete output o dst . During the server side processing, the filter / sanitizer will induce string transformations. During the parsing, the browser may induce transformations [Weinberger et al. 2011a, Heiderich et al. 2013]. Intuitively, performing this two-steps taint inference process should increase our rate of true positive and decrease our rate of true negative, as compared to a direct string to parse tree inference. It is important to note that, instead of writing our own parser, as done in [Sekar 2009], we rely on an real-world parser. This has two advantages. First, we are flexible with respect to the parser (e.g., for XSS: Chrome, Firefox, IE ; for other vulnerabilities such as SQL injections, we could rely on a SQL parser). Secondly, we are certain about the real-world applicability of the detected vulnerabilities. This contrasts with writing a homemade parser which may introduce false negative or false positive. However, we are aware that this potentially increases the number of cases to be tested (number of applications × number of browsers × number of versions), but the effort in searching for an XSS for a specific browser and version in a given application can be weighted depending on the number of users using that precise browser and version (which can directly relate to the allocation of testing resources and to a risk analysis).

EVOLUTIONARY XSS FUZZING CHAPTER 5. GA XSS FUZZING

Definition 16 A κ, µ Taint Aware Tree (TAT) Let M be a CTFM (Definition 14). Let (x src , t src , t dst , o dst ) be a δ-reflection in M (Definition 5). Let κ ∈ N and µ ∈ [[0..1]]. A κ, µ Taint Aware Tree (TAT) consists of:

• Ω(o dst , G), the parse tree of the word o dst w.r.t. the grammar G.

• d : Σ * 2 →[[0..1]], a string distance function.
• Z δ (x src , o dst ), the set of δ-tainted substrings in o dst by x src .

• a taint function Ψ d,κ,µ : Z×Ω → {true, f alse} s.t. for each tainted substring z ∈ Z and each parse tree node ω ∈ Ω,

Ψ d,κ,µ (z, ω) =                          T rue if:
the set of κ-tainted substrings in z by ω.value is not empty

-OR d(ω.value, z) ≤ µ
False otherwise

Test Verdict

The test verdict answers the question "Did this individual trigger an XSS vulnerability?". The TAT T T dst (Figure 5.6) is matched against a set of taint-aware tree patterns (TAP) (e.g., Figure 5.8).

If at least one pattern matches, then the individual is an XSS exploit (i.e., the test verdict will output "yes, vulnerability detected"). Our TAP are stable w.r.t. the tested applications: we use the same TAP for all of them. A TAP is a tree containing regular expressions on its nodes. Those regular expressions may contain strings(e.g., script), taint markers , repetition operators(+, * ), or the match-all character(.). The tester can provide its own TAP. We incorporate in KameleonFuzz default TAP for detecting successful XSS exploits. Those all violate the syntactic confinement of tainted values.

Potential Vulnerability (Non Syntactic Confinement) If the TAP illustrated in Figure 5.7 matches the TAT T T dst , then there is a non syntactic confinement of a tainted value. This exhibits a potential vulnerability. In order to write TAP, we observed the reflection contexts (see Definition 13 in Section 4.3) and tainted parse tree nodes of outputs in various XSS attacks. Most of them attempt to craft a handler in order to trigger code execution (e.g., Java-Script) [START_REF] Heyes | [END_REF]. From this set of attack vector, we generalize minimal tainted parse trees, which are the TAP. We illustrate an example of TAP in

Fitness

The fitness function assesses "how close" is an individual to finding an XSS vulnerability. The higher its value, the more likely the GA evolution process will pick the genes of this individual for creating the next generation. The inputs of the fitness function are the individual I, the concrete output o dst in which the fuzzed value x src , sent in the transition x src , is reflected, T dst = taint(parse(o dst ), x src ) the taint-aware parse tree, and the application model M. The fitness dimensions are related to properties we observed between the fuzzed value and the reflection in the case of successful XSS attacks. Those dimensions are listed in Table 5.1.

Those dimensions model several intuitions that a human penetration tester may have. The most significant ones are:

• 1: Percentage of Successfully Injected Character Classes. Characters

EVOLUTIONARY XSS FUZZING CHAPTER 5. GA XSS FUZZING

that compose leaves of individual fuzzed value tree (see Figure 5.3) are categorized into classes depending on their meaning in the grammar (e.g., C 1 ={<,>} C 2 ={",'}, C 3 ={\n,\r,\t}, C 4 ={;,:}, etc.). This metric expresses the "injection power" for the considered reflection.

• 2: Number of Tainted Nodes in T T dst . Whereas injecting several character classes is important, it is however not a sufficient condition for an attacker to exert control on several parse tree nodes. Successful XSS injections are generally characterised by at least two neighbours tainted nodes (one which is supposed to confine the reflection, and the other(s) that contain the payload and a trigger for that payload). Thus, if an attacker is able to reflect on several nodes, we expect that it increases its chances to exploit a potential vulnerability.

• 3: Singularity of an individual w.r.t. its current generation. A problem of GA is overspecialization that will limit the explored space and keep finding the same bugs [START_REF] Demott | [END_REF]]. To avoid this pitfall, we compute "how singular" an individual is from its current generation. This dimension uses the source transition x src , the fuzzed value x src , and the reflection contexts (i.e., the destination transition o dst and the tainted nodes in T T dst , see Definition 13).

• 4: The higher the Number of Transitions between the source transition x src and its Reflection o dst , the more difficult it is to detect that vulnerability, because it expands the search tree.

• 5: a New Page discovered (5) or 6: a new Macro-State ( 6) discovered: increase application coverage.

Mutation and Crossover Operators

A probability distribution decides whether an individual will be mutated or not. When a mutation will happen, an operator is applied either on the fuzzed value or on the input sequence. We list the implemented fuzzed value mutation operators in Table 5.2. We fuzzed while aiming at one reflection at a time.

The fuzzed value mutation operator works on the production tree of the fuzzed value x src (see Figure 5.3). The amplitude of the mutation is a decreasing function of the fitness score: if an individual has a high fitness score, the mutation will target nodes in the production tree that are close to leafs. Similarly, in the case of a low fitness score, the operator is more likely to mutate nodes close to the root. Figure 5.9 illustrates an example of application of the fuzzed value operator. Table 5.

2: The Mutation Operators

The crossover operator works at the fuzzed value level, i.e., on the production tree. Its inputs are two individuals of high fitness scores. It produces two children. When a crossover operator is applied on two parents which share at least one production rule at a sufficiently deep level, we exchange at most two pairs of sub-trees between the parents, in accordance with an AIG. Table 5.3: The Crossover Operator

Stopping Condition

The stopping condition is a boolean function which evaluates to true when the tester wants the fuzzing to be stopped. This function receives the number of distinct found XSS vulnerabilities, the number of founds XSS exploits, the number of submitted fuzzed inputs, the duration of fuzzing, and the number of generations evolved.

Implementation

A Potentially Iterative Process

In practise, the tester defines its stopping conditions. At the end of the test campaign, if no interesting results were found, the tester can increase the testing resources (e.g., increasing the number of generations, the size of the population, etc.). In such a situation, our current implementation may repeat some tests which were made during the first campaign. This can be avoided by storing the results of the first campaign. This is a limitation of the implementation, not of the approach. Confinement Based Approaches assume that malicious inputs break the structure at a given level (lexical or syntactical). As in [Sekar 2009], we rely on nonsyntactical confinement and we use detection policies that are both syntax and taint aware. A key difference is that [Sekar 2009] wrote his own parser to propagate the taint, whereas we use the parser of a browser (e.g., Google Chrome). Thus we infer the taint twice (see Figure 5.4). By doing so, we are sure about the realworld applicability of the found XSS exploits, and our implementation is flexible w.r.t. the browser. [START_REF] Su | [END_REF]] relies on non-lexical confinement as a sufficient fault detection measure, which is more efficient than [Sekar 2009], but requires a correctly formed output (which is not an always valid assumption on HTML webpages [Heiderich et al. 2010]) and is prone to false negatives.

Regular-Expressions Based Approaches assume that the fuzzed value is reflected "as such" in the application output i.e., that the sanitizer is the identity function. In the case of sanitizers this may lead to false negatives [Riancho 2011]. Moreover, most do not consider the reflection context, which can lead to false positive. IE8 [Ross 2008] and NoScript [Maone 2006] rely on regular expressions on fuzzed values. XSSAuditor (Chrome XSS filter) performs exact string matching with JavaScriptDOM nodes [Bates et al. 2010].

String Distance Based Approaches Sun [START_REF] Sun | [END_REF]] detects selfreplicating XSS worms by computing a string distance between DOM nodes and requests performed at run-time by the browser.

IE8 [Ross 2008] and Chrome XSSAuditor [Bates et al. 2010] filters only work on Type-1 XSS. Whereas NoScript [Maone 2006] is able to block some Type-2 XSS, but is only available as a Firefox plugin.

Learning and Security Testing

In its basic form, fuzzing is an undirected black-box active testing technique [START_REF] Barton | [END_REF]]. [Zalewski 2011a[START_REF] Valotta | Fuzzing with DOM Level 2 and 3[END_REF], Holler et al. 2012, Ruderman 2007] mainly target memory corruption vulnerabilities. [START_REF] Stock | 25 Million Flows Later -Large-scale Detection of DOM-based XSS[END_REF]]'s recent work fuzzes and detects Type-0 XSS in a white-box test context. [Heiderich et al. 2013] An Attack Grammar (AIG) produces fuzzed values for XSS as a composition of tokens. [START_REF] Wang | [END_REF], Tripp et al. 2013] and KameleonFuzz share this view.

In their recent work, [START_REF] Tripp | [END_REF]] prune a grammar based on the test history to efficiently determine a valid XSS attack vector for a reflection. It would be interesting to compare KameleonFuzz to their approach, and to combine both. [START_REF] Wang | [END_REF]] use a hidden Markov model to build a grammar from XSS vectors. [START_REF] Kals | [END_REF]] uses attack vectors from a very large manually written library, without specific criterion.

Learning for Security Testing Radamsa targets memory corruption vulnerabilities: it infers a grammar from known inputs then fuzzes to create new inputs [START_REF] Pietikäinen | [END_REF]]. [Shu & Lee 2007] passively infer a model from network traces, and actively fuzz inputs.

For command injection vulnerabilities (XSS, SQL injection, . . . ), [Dessiatnikoff et al. 2011] cluster pages according a specially crafted distance for SQL injections. [Sotirov 2008] iterates between reverse-engineering of XSS filters, local fuzzing, and remote fuzzing. [Doupé et al. 2012] showed that inferring macro-state aware control flow models increases vulnerability detection capabilities.

CHAPTER 6

Experiments for XSS Detection

You bruteforce all the moves in chess,are you playing? Mutate the code that plays chess, you are learning and playing. The seed is the code. [Heyes 2013] One development team cannot fail 1000 times to develop a secure application, but 1000 teams can fail one time. [Ruff 2013a] I enjoy making things, breaking things, and making things that break things. [START_REF] Moore | HD Moore. hdm.io -about[END_REF] Making the world a better place... One crash a time! [Takanen 2012] We evaluate our approach by applying our tools on different Web Applications, listed in Table 6.1. We separately evaluate the LigRE inference (Section 6.2) and the KameleonFuzz evolutionary fuzzer (Section 6.3) components. We discuss the limitations of our tools in Section 6.4.

Evaluation methodology

We selected seven web applications of various complexity (Table 6.1). The criteria for choices are various (different server side languages: JSP, Python, PHP; have shown to contain at least one XSS each; some are used at industrial scale). KameleonFuzz detected at least one true XSS in all of them. P0wnMe v0.3 is an intentionally vulnerable web application for evaluating black-box XSS scanners. It contains XSS of various complexity (transitions, filters, reflection structure).

WebGoat v5.4 is an intentionally vulnerable web application for educating developers and testers. Its multiple XSS lessons range from message book to human resources. Gruyere v1.0 is an intentionally vulnerable web application for educating developers and testers. Users can update their profile, post and modify "snippets" and view public ones.

LIGRE EVALUATION CHAPTER 6. XSS EXPERIMENTS

Elgg v1.8.13 is a social network platform used by universities, governments. Users can post messages, create groups, update their profile. An XSS exists since several versions.

WordPress v3 is a blogging system: the blogger can create posts and tune parameters. Visitors can post comments, and search. The count-per-day plugin is known to contain XSS.

PhpBB v2 is a forum platform. We include this version, as it is notorious for containing several XSS [START_REF] Bau | State of the Art: Automated BlackBox Web Application Vulnerability Testing[END_REF]].

e-Health 04/16/2013 is an extract of a medical platform used by patients and practitioners, developed by a company.

XSS Uniqueness an XSS is uniquely characterized by its source transition I src , its parameter name, its destination transition O dst and the tainted nodes in the parse tree T (P(O dst ), I src ). Hence if a fuzzed value is reflected twice in O dst , e.g., in two different nodes in the parse tree, and for each node, the scanner generated an exploitation sequence, then we count two distinct XSS. In our experiments, the only time we had to distinguish two XSS using the nodes in the parse tree was in the Gruyere application.

Experimental Platform We run the scanners on a Mac OS X 10.7.5 platform with a 64 Bit Intel Quad-Core i7 at 2.66GHz processor, and 4GB of RAM DDR3 at 1067MHz.

LigRE evaluation

We aim at determining if control plus taint flow model aware XSS fuzzing is efficient enough to search for vulnerabilities in typical web applications. We also aim at comparing the fault detection capability of our prototype implementation LigRE against existing state of the art black-box vulnerability scanners. Relevant 92 CHAPTER 6. XSS EXPERIMENTS

LIGRE EVALUATION

metrics include the number of distinct true XSS discovered, and the number only found by a given scanner. To measure the efficiency of the scanners, we compare the number of sent requests and of found XSS. In our experiments, LigRE detected XSS missed by other scanners, and most of the XSS found by those.

We consider the following open-source black-box XSS scanners to compare with our approach: Wapiti, w3af and SkipFish. They all infer the control flow and fuzz. Their configuration i available in [Duchène 2013c]. In addition to LigRE with all its components (A,B,C and D in Figure 4.1), we also include LigRE with only A(control flow inference) and D(w3af). We denote them as LigRE ABC+D and LigRE A+D . In both setups, D denotes the w3af fuzzer.

RQ1. (Fault Revealing): Does control plus taint flow aware fuzzing find more true vulnerabilities than other scanners?

For each scanner and application, we sequentially configure the scanner, reset the application, set a random seed to the scanner, run it against the application, and retrieve the results. We repeat this process five times, using different seeds. If possible, scanners are configured s.t. they only target XSS. We configure them with the same information (e.g., credentials). When a scanner does not handle it, we perform two sub-runs: one with the cookie of a logged-on user and one without.

We adjust parameters for the runs to last at most five hours. Beyond this duration, we stop the scanner and manually analyze the results. The number of detected XSS is the union of distinct true XSS found during the different runs. An XSS is uniquely characterized by its source transition t src , its fuzzed parameter name x src , its destination output t dst and the structure in which the value of x src is reflected. For all scanners, we manually verify XSS. During our experiments, no scanner reported false positive XSS (Skipfish reported other false positives). Most scanners achieve limited coverage due to their partial handling of basic forms, their inability to track the macro-state (beyond the classic logged in/out, and assuming the tester provides values). At times, they send requests regardless of the available links. The aggressive behavior of Skipfish is sometimes positive (e.g., in Gruyere, it found one XSS missed by others on 404 pages), sometimes not (e.g., in Wordpress, it submitted 150 times a form without detecting any XSS). As the control flow for the targeted reflection is quite simple, LigRE detected the XSS in Wordpress mainly because it sent fewer fuzzed values than SkipFish. For Elgg, both Skipfish and w3af loop between pages because they only consider the URL and not the page model. We set up a proxy between the scanner and the web application, and configure this proxy to limit the number of requests. We iteratively increase this limit, run the scanner, and retrieve the number of found and distinct true XSS. We manually verify them. We run such a process five times per scanner, web application, and limit. For each number of requests, for each scanner, we sum the number of unique true XSS detected for all applications. The results are illustrated in Figure 6. Below approximately 850 HTTP requests, w3af is the most efficient scanner. Thus we hypothesize that in applications with few macro-states, assuming it is able to navigate correctly, which in our experiments mainly happened in P0wnMe and Gruyere, then w3af is more efficient than other scanners at finding non filtered XSS.

Moreover, the LigRE proof-of-concept spends a significative number of requests in taint flow inference (from 75 to 93%). There is room for improvement. An industrial implementation should consider additional heuristics to prune sequences: e.g., with a notion of achieved coverage of n long sub-sequences. We conducted two surveys for evaluating the current level of use of CTFM by penetration testers [Duchène et al. 2013c], and how they obtained them. Figure 6.3 synthesize relevant knowledge. Those who make use of CFM rely on a manual crawling approach, using Burp [Stuttard 2007] as a proxy, and manually draw CFM. However, since considered web fuzzers only accept a list of urls and an authentication context, they would achieve a low transition coverage.

Taint Flow Tracking 77% of testers do not perform white-box taint flow tracking, mainly because they think that not enough tools are available. 50% of those find this manual work tedious. Those who perform it rely on dynamic exact string matching. 54% of testers perform black-box taint flow inference. Most of them do it manually. 57% of those find it tedious. Taint flow tracking aims at determining the exact composing of filters, in order to produce fuzzed inputs to bypass those filters. Performing it manually is time consuming, and limited to human expertise. In white-box, it may require knowledge of various server languages. Whereas in black-box, the ability to interpret few client side languages is enough.

Even skilled penetration testers largely rely on manual taint flow tracking. Since such work is time consuming, and prone to false negatives, there is a need for tools producing hybrid control plus taint flow models.

KameleonFuzz evaluation

We evaluate our prototype implementation of KameleonFuzz against black-box open source XSS scanners, in terms of detection capabilities (RQ4) and detection efficiency (RQ5). In our experiments, KameleonFuzz detected most of the XSS detected by other scanners, several XSS missed by other scanners, and 3 previously unknown XSS.

We considered four black-box XSS scanners to compare with KameleonFuzz: Wapiti, w3af, Skipfish and LigRE+w3af. Appendix A contains the configuration we used during the experiments. It is important to note that only LigRE and Ka-meleonFuzz are macro-state aware.

RQ4. (Fault Revealing): Does evolutionary fuzzing find more true vulnerabilities than other scanners?

To answer this question, we consider the number of true positives, the number of false positives, and the overlap of true positives. For the first two metrics, we compare all tools, whereas for the overlap, we compare LigRE+KameleonFuzz against the others (Wapiti,w3af,skipfish,LigRE+w3af). True positives are the number of XSS found by a scanner that actually are attacks, thus the higher, the better. If a scanner produces false positives, a tester will loose time, thus the lower the better. The overlap indicates vulnerabilities detected by several scanners. We denote as T A the True XSS vulnerabilities found by the scanner A. We define the

overlap(A, B) = T A ∩T B T A ∪T B
A low overlap indicates that scanners are complementary. We also consider the vulnerabilities only detected by one scanner:

only by(A, B) = T A T A ∪T B -overlap(A, B)
A low only by indicates that a given scanner does not find many XSS that the other missed.

For each scanner and application, we sequentially configure the scanner, reset the application, set a random seed to the scanner, run the scanner against the application, and retrieve the results. We repeat this process five times, using different seeds. Parameters have been adjusted so that each run lasts at most five hours. Beyond this period, we stop the scanner and analyze the produced results. The number of found vulnerabilities is the union of distinct true vulnerabilities found during the different runs. If possible, scanners are configured so that they only target XSS. We configure the scanners with the same information (e.g., authentication credentials). When a scanner does not handle this information correctly, we perform two sub-runs: one with the cookie of a logged-on user, and one without. Since all scanners, except LigRE and KameleonFuzz, are not macro-state aware we configure them to exclude requests that would irreversibly change the macro-state (e.g., logout when an authentication token is provided).

The practicality of LigRE+KameleonFuzz is illustrated in Table 6.3. This figure reports the number of potential reflections, found vulnerabilities, and generations to find all detected vulnerabilities during the fuzzing. The three columns in the middle report the length of created XSS exploits for the closest vulnerabilities from the start node.

True and False XSS Positives. We manually verify the XSS for each scanner. During our experiments, no scanner found a false positive XSS (Skipfish had other false positives). Figure 6.4 The overlap and only by of true XSS found by LigRE+KameleonFuzz (KF) against other scanners are illustrated on Figure 6.5. KameleonFuzz finds the majority of known true XSS. W3af and Skipfish find the remaining ones. In the Gruyere application, Skipfish and w3af each found one vulnerability missed by all other scanners, including KameleonFuzz. Those consist of a not referenced 404 page containing a type-1 XSS, and of a type-2 XSS within the pseudo field when registering. It is harder to find the latter XSS than others: the application behaves differently as inferred when the scanner registers a new user with a fuzzed pseudo. Reusing the fuzzing learned knowledge in the inference may permit Kameleon-Fuzz to detect this XSS. Additionally, Skipfish and w3af both detected one XSS in Gruyere that other scanners missed. Thus the only by of Skipfish and w3af is two in Figure 6.5, whereas in Figure 6.4, one XSS is detected by both of them. Inferring the control flow for navigating to non-referenced pages may increase Li-gRE+KameleonFuzz XSS detection capabilities. If this is not an option, the tester should use LigRE+KameleonFuzz, Skipfish, and w3af. To answer this question, it is appropriate to observe the number of detected true XSS depending of the number of HTTP requests. Thus, we set up a proxy between the scanner and the web application, and configure this proxy to limit the number of requests. We iteratively increase this limit, run the scanner, and retrieve the number of found distinct true XSS. We manually verify them. We run such a process five times per scanner, web application, and limit. For each number of requests, for each scanner, we sum the number of unique true XSS detected for all applications. The results are illustrated in Figure 6 tation still do not require access to the application source code, only the ability to intercept at run-time the arguments at the observation points. Thus for command injection vulnerabilities other than Type-1 and Type-2 XSS, one may consider our approach as having a grey-box harness. Using our approach for detecting Type-0 XSS and mutation-XSS is likely to require an adaptation of the attack grammar [Heiderich et al. 2010, Heiderich et al. 2013].

Limitations

We classify the limitations in two categories: the limitations of our approach, and those of our implementation.

Approach Limitations

Reset We assume the ability to reset the application in its initial node, which may not always be practical (e.g., when testing a live application having users connected, we have to work on a copy). However, this does not break the blackbox harness assumption: we do not require to be aware of how the macro-state is stored (e.g., database). How to relax this assumption is a research direction.

Generation of an Attack Input Grammar (AIG) Writing an AIG requires knowledge of the parameters mentioned in Section 5.2.1. This work is yet manual. The trade-off between the size of the language generated by this grammar and the fault detection capabilities is yet to be studied. A too narrow generated language (e.g., few produced fuzzed values for a given context, or very few contexts) may limit the fault detection capability, whereas a too important one may have limited efficiency. Moreover, the AIG is tied to the targeted injection subfamily (e.g., XSS, SQL injection, etc), thus the need for human input is a current limitation. There is room for research in automating this generation process [START_REF] Wang | [END_REF].

XSS Model Hypothesis

We hypothesize that an XSS is the result of only one fuzzed value. Our current approach may have false negative on XSS involving the fuzzing of at least two fuzzed values at a time [START_REF] Dalili | Souroush Dalili. Browsers anti-XSS methods in ASP (classic) have been defeated![END_REF]]. To our knowledge, no scanner handles such cases.

Implementation Limitations

Non Deterministic Value (NDV) We assume the tester's ability to identify the NDV (e.g., anti-CSRF, viewstate, . . . ), or constantly changing pages [START_REF] Spacios | SPaCIoS. Deliverable 5.3: Final Proof of Concept[END_REF]]. Approaches to automate their detection have been investigated [START_REF] Hossen | [END_REF].

Dynamic Client-Side Content Our implementation does not support Ajax applications, unless they gracefully downgrade (i.e., keep their functionality while navigating via HTTP requests instead of Ajax events). [START_REF] Marchetto | [END_REF], Amalfitano et al. 2008] automatically infer Ajax applications. Flash and PDF files

are not yet supported. Thus on very dynamic applications such as Facebook which made intensive use of DOM transitions, our implementation would only infer and fuzz a subset of the tested application. This means that the fault detection capabilities of our implementation is limited to the subset of the application accessible by performing only HTTP requests which can be discovered in links and in forms.

We did not experiment with such applications.

DISCUSSION CHAPTER 6. XSS EXPERIMENTS

Encoding The precision and efficiency of the taint flow inference is dependent of the considered encoding transformations. Plain, url and base64 encodings are implemented. LigRE and KameleonFuzz can be extended to support more.

Threats to Validity

External Comparison We only compare to open source black-box web scanners and LigRE. We contacted several vendors of commercial products, but we did not receive a positive reply within a reasonable timeframe. Thus we were unaware to compare with commercial scanners. Those may obtain better results than the considered scanners.

Randomness Scanners make extensive use of randomness. Since some XSS are not trivial to be found, their discovery may involve randomness and duration. We tried to limit such factors by running the scanners five times with different seeds and up to five hours. The chosen duration of the experiments may impact the results.

Considered Applications Our comparison with other scanners is limited to the considered versions of scanners and applications. We cannot generalize results from those experiments. Running the scanners on other applications or scanners versions may produce different results.

KameleonFuzz Parameters KameleonFuzz contains numerous adjustable parameters e.g., probabilities that drive the mutation and crossover operators during the fuzzing. In Appendix A, we provide significant parameters and their default values. Those are chosen empirically. Because the value domain of each parameter is quite wide, and it is time consuming to run the whole test suite, it was not feasible to evaluate the combination of all parameters values and their impact. Thus, we cannot guarantee that the chosen default values achieve the best detection capabilities and efficiency.

CHAPTER 7

Other Approaches for Detecting Vulnerabilities

Any sufficiently complicated input data is indistinguishable from bytecode, its consumer from a VM.

[ Bratus & Bangert 2012] After watching a lot of these talks I think what you have to do is ask each executive at RSA how their vision differs from modern reputation-system, brain-in-the-cloud, heuristics-based anti-viruses.

[Aitel 2014]

Sometimes, I forget that I launched calc.exe, and then I freak out when I notice it in my taskbar.

[Kortchinsky 2013]

For the last three decades, in order to ensure the safety of systems, researchers proposed many techniques dedicated to the automatic search and detection of vulnerabilities. Such techniques first differ from each other depending on the test context (e.g., white-box, grey-box or black-box).

White and Grey-Box Approaches

Static Analysis techniques extract knowledge from information available without executing the application (e.g., source code). Code review is performed by automatic tools, or human security analysts. Even corporations with very large web application code base, such as Google and Facebook, still perform manual code reviews as part of their security testing processes. [START_REF] Shar | [END_REF] extracts the composition of sanitizers from the source code, and verifies if a bypass can be found for the composed sanitizer. [START_REF] Aydin | Automated Test Generation from Vulnerability Signatures[END_REF]] extract signatures from source code to generate CTFM-like automatons, from which they generate input sequences towards achieving specific coverage criteria. Model inference from source code generate CFM, e.g., [START_REF] Mihancea | [END_REF] for [Mouttappa et al. 2013a] verifies that properties are not violated on the recorded traces. [START_REF] Johns | [END_REF]] passively monitors HTTP traffic, tokenize JS in the outputs, and detects Type-1 and Type-2 XSS with an interesting precision. [START_REF] Offutt | [END_REF] generate tests from UML specifications written by analysts, and have coverage criteria specific to UML diagrams. [START_REF] Friedman | [END_REF] generate tests from Finite State Machine (FSM) that correspond to system specifications. Similar approaches are mentioned in [START_REF] Utting | [END_REF]. [START_REF] Lebeau | [END_REF]] manually model the application as a UML diagram with OCL guards, from which they automatically generate security tests for web applications.

Model Inference is a reverse engineering technique that consumes an application and produces a model. [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]] pioneered the black-box model inference with her L* algorithm. [Cho et al. 2010] apply [START_REF] Shahbaz | [END_REF]'s algorithm to understand the behavior of a botnet C&C and to take it down. [START_REF] Cho | [END_REF] infer CFM of protocol server implementations using concolic execution techniques from which fuzzed inputs are generated. [Shu & Lee 2007] learns using L* models of an implementation and applies model checking techniques for searching for security properties violation (e.g., confidentiality or integrity of a given object). [Li et al. 2006] separately infer components models and then compose them for creating a model corresponding to the aggregation of the components. [START_REF] Petrenko | [END_REF]] infer models containing Non Deterministic Values (NDV) (e.g., models of web applications containing viewstate). [Krueger et al. 2012a] learns CTFM for simulating network honeypots. [START_REF] Choudhary | [END_REF] learns Asynchronous Javascript And XML (Ajax) application models, which are significantly larger than traditional web applications model. [Mariani et al. 2012] incrementally learns updates of Ajax application models.

Black-Box fuzzing techniques historically target MCV [START_REF] Barton | [END_REF]]. The beautiful story of how [START_REF] Barton | [END_REF]] crashed Unix utilities because of transmission errors -due to a storm impacting his modem connectivity -explains why black-box fuzzing is also called structural testing. In the domain of blackbox interpreter fuzzing [START_REF] Woo | Scheduling black-box mutational fuzzing[END_REF] schedule and prioritize tests according to various coverage criteria. In the LangFuzz approach, [START_REF] Holler | [END_REF]] require a target grammar and code fragments which it mutates. LangFuzz exposed previously unreported JavaScript and PHP vulnerabilities. [START_REF] Guo | [END_REF]] infer the grammars accepted by web browsers and mutate, according to this grammar, code fragments known to have triggered a problem. [START_REF][END_REF]] generate programs in two phases: first they generate abstract scripts, and then they replace abstract labels with concrete identifiers (e.g., variable name, function call, etc.). They target ActionScript. They exposed previously unreported vulnerabilities in the Adobe Flash ActionScript virtual machine. [START_REF] Householder | [END_REF] apply a statistical theory algorithm to the problem of selection of parameters (randomization seed, file seed, range).

Model checking searches for properties violations on states of a model. Such models can be written by a human analyst, extracted using a white-box con-CHAPTER 8

Discussion & Conclusion

Sure: today, it's so easy to phish users or exploit real RCE bugs, that backdooring web origins is not worth the effort. But in a not-too-distant future, that balance may shift. [Zalewski 2011c] Give me ten carefully chosen hackers, and within 90 days I would then be able to have this nation lay down its arms and surrender. J. Saiteerdou, FBI [START_REF] Liang | [END_REF] Vulnerability Detection Systems: Think Cyborg, Not Robot [Heelan 2011]

Discussion

We propose several directions of research for overcoming limitations of the implementation, applying to other web command injections, and applying to other classes of vulnerabilities, such as memory corruption.

Influence of Various Parameters

Encoding When no charset is specified for a page which is a destination for a reflection (i.e., no content-type HTTP header, or no charset as a child of the  node, or the reflection happens before this tag), it is interesting to act on the encoding in the attack input grammar (AIG), in order to find an XSS. In our experiments we only used UTF-8 encoding, as it already permitted to find XSS in various applications. However, variable length encoding such as UTF-7 [Goldsmith & Davis 1997], Shift JIS [Microsoft b], etc.may be of interest in the aforementioned case.

Evolutionary Parameters Studying thoroughly the influence of evolutionary parameters (e.g., crossover and mutation rate, population size, fitness weights) may be of interest. The main difficulty is the significant number of combinations to test, and the required duration to test thoroughly each given combination.

Improving the efficiency of attack grammar

Automatic Attack Grammar Generation Few researchers addressed the problem of the automatic generation of an attack grammar. [START_REF] Wang | [END_REF]] pioneered this direction by inferring one grammar using a hidden Markov model. Ideally an interesting grammar balances between a precision sufficient to bypass filters and a narrowed search space s.t. the testing campaign for a given reflection context has an acceptable cost. [START_REF] Tripp | [END_REF]] have an interesting compromise with their advanced representation which combines filters, and reflection contexts.

Web Filters Reverse-Engineering In the process of fuzzing a reflection, knowledge can iteratively be learned regarding the filter, thus there is room for applying machine learning algorithms. For instance, if the sanitizer is on client side (e.g., as in most DOM-XSS), precise automata may be built using static analysis techniques [Saxena et al. 2010b], e.g., symbolic execution [Saxena et al. 2010a] or even concolic execution [START_REF] Cho | [END_REF]]. However, when the sanitizer is at server side, such techniques cannot be used. This research direction has been pioneered by [Sotirov 2008]. [START_REF] Tripp | [END_REF] implicitly capture the notion of Web Filters Models in their attack grammar. If we would infer using machine learning techniques the transducer for each reflection, then we would be able to prune our attack grammar sub-tree with a great precision.

Attack Grammar Pruning A method for increasing the efficiency of Web Command Injection fuzzing consists in iteratively pruning sets of attack vectors after observing the output obtained form each fuzzed input sequence. [START_REF] Tripp | [END_REF]] exactly adopt such an approach.

Adapting the Approach in case of other Counter-Measures

In our problem, we hypothesize the only presence of server-side sanitizers. In this section, we list the other defensive measures which it may be interesting to address. Web Application Firewall (WAF) is a firewall performing Deep Packet Inspection (DPI) up to the HTTP layer. [qua , mod , iro 2011] are examples of WAF.

DISCUSSION

They act as active defense mechanism, by detecting and removing content within the webpages. They may even parse and interpret the webpage as the an end-user browser would do. Since their parser may be different from the end-user, there is a risk of false negatives and of false positives.

Static Rewriting [START_REF] Doupé | [END_REF]]'s deDacota statically rewrites .Net web applications in their binary form to enforce code+data separation when concatenated variables or inlined JavaScript code creation has been detected.

Trusted DOM [START_REF] Heiderich | [END_REF]] a white-listing policy in which the developer indicates which DOM modification operations she allows. While this requires work not to break the functionality of applications, such a counter-measure can prevent type-0, type-1, and type-2 XSS.

HTML5 IFrame Sandbox Several XSS vulnerabilities exist due to browser API developers not enforcing a strict access control model [Heiderich et al. 2010], several attacks consists in a webpage embedded in an iframe to access its parent DOM. In order to limit the impact in such cases, the HTML5 IFrame Sandbox [w3c 2009] permits the parent webpage to disable capabilities of the embedded one such as script execution, form submission etc. DOM Tags Randomization [ Van Gundy & Chen 2009] randomizes the prefix of HTML tags for each request. For successfully exploiting a XSS vulnerability, an attacker would have to guess the prefix that will be picked up next. This makes the reliability of an XSS exploit very low. Randomizing the position of certain codes is a similar concept to the ASLR [START_REF] Yarom | Method of relocating the stack in a computer system for preventing overrate by an exploit program[END_REF], Team 2012], a 2001 counter-measure for raising the cost of exploiting memory corruption vulnerabilities. Slightly differently, [START_REF] Kc | [END_REF] randomizes the instruction set through a XOR mechanism specific to each process and run.

Content Security Policy (CSP) [w3c 2012a, Google 2013] declares a policy at server side, and enforces it at client side. The default policy prevents the execution of inline scripts, only allows  ">
	...
	...
	Hello lakitu !
	Figure 2.8: Successful exploit of an XSS
	Thus, in order to detect XSS, we need to address the sub-problem:
	XSS.2 Achieving a Test Verdict
	→ How to infer the taint?
	→XSS.2.1

Client → Server: GET /nice.html?name= lakitu HTTP /1.1 Host: yoshi.jp Client ← Server:

Table 2 .

 2

	Inference
	(black-box)

1: Examples of Vulnerabilities and Taint Markers

  and G be a grammar. Let δ ∈ N be a threshold. Let r = (x src , t src , t dst , o dst ) ∈ R e f l (M) be a δ-reflection (Definition 5), where for a given trace, x src is a concrete input parameter value of the transition t src , and o dst is the concrete output value of the transition t dst . Let Z = taintedsub(x src , o dst ) be the set of substrings of length ≥ δ in o dst which are tainted by x src . r is a Web Command Injection (WCI) w.r.t. to G, if ∃ z ∈ Z, s.t. z is not syntactically confined in o dst w.r.t. G.

	2.2. DEFINITIONS CHAPTER 2. PROBLEM STATEMENT	CHAPTER 2. PROBLEM STATEMENT 2.3. FUZZING
	Output and Taint Definition 8 Cross Site Scripting (XSS) Vulnerability Parse Tree	Syntactically
	Confined? We define a Cross-Site Scripting (XSS) as a Web Command Injection (Defini-
	START tion 7) in which the output grammar G is HTML (and the interpreted grammars:

saved e.g., JavaScript, CSS, etc.).		H1_TITLE		TEXT	BR
	messages
 buenosdias
 Definition 9 XSS Types XSS Type Transition	TEXT saved messages Characteristic

	buenosdias

		(request)

saved "Pure" Type-0 /	Ajax	START In a reflected DOM-XSS, the taint flow
	messages
 buenosdias
 Type-1 / Re-HTTP	saved are Javascript function or event calls. buenosdias

 </script> "
	Figure 2.12: Extract of the HTML Grammar Production Rules web applications. Type-0/DOM XSS exist since web application execute dynamic
	code at client side (e.g., JavaScript Ajax transitions, such as Facebook). DOM XSS
	In Definition 7, we give a restrictive definition of the notion of Web Command involve Ajax transitions. In this thesis, we only focus on Type-1 (reflected) XSS
	Injection (WCI). and Type-2 (stored) XSS.
	Definition 7 Web Command Injection (WCI)
	Let M be a Web Application (Definition 4), R e f l (M) be a set of reflections
	(Definition 5) in M, A WCI permits to violate the code integrity property at the level of G.
	Type-1 (reflected) and Type-2 (stored) XSS exist since applications handle dy-
	namic data (i.e., since the first cgi-bin scripts appeared in web applications). As
	of today, this problem is still unsolved: no scanner detects 100% of the XSS in all

  [START_REF] Trivedi | and our Focus 2.1 Black-Box Web Command Injection Detection[END_REF] and develop it in Chapter 4.

		Reverse Engineering	-->	Directed Inputs
						Generation
		A. Control	Control	B. Approximate	Control + Taint	C. Chopping:	Reflection Aware
	Application + Credentials	Flow Inference	Flow Model	Taint Flow Inference	Flow Model	Inputs Generation	Non Malicious Inputs
				LigRE

Table 3 .

 3 1 shows fuzzed values sent by w3af [Riancho 2011], a black-box open source scanner, when testing P0wnMe . W3af iterates over a list of fuzzed values. It does not learn from previous requests, nor considers the reflection context. As a result, all fuzzed values in Table

Table 3 .

 3

1: w3af fuzzed values (extract)

Table 3 .

 3 2 illustrates this evolution.

	CHAPTER 3. OUR PROPOSAL	3.2. EVOLUTIONARY XSS FUZZING
	Fuzzed Value (x src )	Reflection	XSS Fit. Gen.
	T9nj1'>	XSS Attempt!	3.1 1
	oH1eqL' onload="
	document.body.inner HTML+='
	XSS Attempt!	3.2 1

'" fakeattr='
	ZuIa2' onload =alert(94478)	ZuIa2'onload =alert(94478)	13.3 1
	WUkp'\tLgpRa	WUkp'\tLgpRa	9.1 1
	WUkp'\t onload=' alert(94478)	WUkp'\tonload ='alert(94478)	18.5 2

Table 3 .

 3

2: KameleonFuzz fuzzed values (extract) of the reflection (t src

  4.2. CONTROL FLOW INFERENCE CHAPTER 4. INFERENCE FOR XSS

		Model Reverse-Engineering		Constrained Fuzzing
	Web App.	A. Control Flow Inference	Control Flow Model	Annotation B. Taint Flow	Control + Taint Flow Model	C. Slicing (Chopping)	Slices	D. Fuzzing	Vulnera-bilities
								w3af
				LigRE				or
							KameleonFuzz

Table 4 .

 4 [START_REF] Trivedi | and our Focus 2.1 Black-Box Web Command Injection Detection[END_REF] value among[→ 10, 10 → 20, 20 → 21].

	+ or -	id	dimension name
	weight
	++	1	number of input parameters
	+	2	distance between page models (p prev i -→	p i )
	+	3	HTTP method
	-	4	number of times performed (total)
	-	5	number of times it changed the state
	-	6	number of requests between i and i detect
	--	7	number of potential contradictions (approx.)

Table 4 .

 4 This is the case for the spiderlinks i prev =GET /login(→ 10) and i detect =GET /login (20 → 21) in the navigation tree extract shown in Figure4.3.

1: Dimensions of the score(spiderlink i) heuristic 4.2.3.2 Did the macro-state change? (macro state changed) If a spiderlink i is sent twice to the application during the requests prev and detect, and the obtained page models are different (i.e., (o prev = i prev .concretize().send()).abstract() (o detect = i detect .concretize().send()).abstract()), then the macro-state changed. 4.2.3.3 Which request changed the macro-state? (index changed macro state, score heuristic)

If a macro-state change is detected between i prev and i detect , then the question "which request in the history between those changed the macro-state?" arises.

To answer it, the heuristic function score represents the likelihood of a request having changed the macro-state. For a spiderlink i ∈ [i prev , . . . , i detect ] the higher the value of score(i), the more likely i changed the macro-state. The dimensions of score are listed in Table

4

.1. If there is a +, resp. -, in front of the dimension, then score is increasing, resp. decreasing, w.r.t. this dimension. score is used in index changed macro state in Algorithm 4.1.

Table 4 .

 4 2 lists its dimensions. pick spiderlink in Algorithm 4.1 uses it.

	+ or -	id	dimension name
	weight
	+ + +	1	request never executed
	++	2	(1+consecutive contradictions)*num state change
	++	3	num recently sent
	++	4	number of artificially generated parameter values
	+	5	number of times sent
	-	6	spiderlink method weight
	-	7	number of times it changed the macro-state

Table 4 . 2

 42

: Dimensions of the navigating(spiderlink i) heuristic

Table 4 .

 4 3: Automatic Value Generation for Helping Taint Flow Inference

		String Generated Param. Value
	pw	12 45 78 0	w1p2w p4w5p

Table 4 .

 4 4 contains the dimensions used in this function.

	weight dimension name
	-	number of nodes in the shortest path from root
	-	number of unexplored spiderlinks in the page model
		of n
	-	... that have same hash as one which permit deter-
		mining a macro-state change

Table 4 . 4

 44 Potential ContradictionLet n a and n b be two nodes ∈ N. A potential contradiction between n a and n b is defined as follows:

: Dimensions of the confidence(node n) heuristic 4.2.5.2 Potential Contradiction A potential contradiction indicate that we may have assigned a page model to the wrong macro-state coloring. It is defined in Definition 12. Let us assume that the Definition 12

  False otherwise node b is the current state. If there exists a node a, s.t. contradiction(a, b) is True, then we may have missed detecting a state change. Thus contradictions are inputs for navigating (see Table 4.2) and score (see Table 4.1).

	CHAPTER 4. INFERENCE FOR XSS	4.3. TAINT FLOW INFERENCE
	4.2.5.3 Backtracking

Table 4 . 5 :

 45 List of Considered Reflection Contexts (CT X) for G O =HTML

	Definition 13 Reflection Context

  4.3. TAINT FLOW INFERENCEDefinition 14Control and Taint Flow Model (CTFM) Let Σ be an alphabet, and G be a grammar. A Control and Taint Flow Model (CTFM) is composed of:• a CFM (Definition 11) • a taint-flow function df : (Σ + × T × T ) → CT X + ,s.t. for a reflection re f l = (x src , t src , t dst , o dst ) of the value x src of a parameter name ∈ Σ + , d f (name, t src , t dst ) produces the list of Reflection Contexts (Definition 13) of x src into o dst w.r.t. G fifteen applications of various complexity, and observed that the longest shortest path between t src and t dst , both included, is 4 transitions, and the shortest path to reach the deepest t dst was 8, thus we arbitrarily limit the length of the generated sequences to 8 (prefix+suffix).

Table 4 .

 4 6. The higher the value of sum, the more likely this reflection will be tested first. For each reflection, LigRE positions the application in the node from which t src originates by sending a prefix sequence. Then LigRE feeds the fuzzer an authentication context (e.g., cookie) and a suffix obtained from the chopped model (CH(t src , t dst ), seeSection 4.4.3) for the fuzzer to navigate from t src to t dst .

Table 4 .

 4 7 is an extract of the prioritization table in its initial state. dim k corresponds to the dimension k of Table4.6. Each tuple of cells (t src , x src , t dst ) line of Table4.7 designates a reflection. Thus we have reflections a, b, c, d. Initially, chosen reflections, the list of already chosen reflections, is empty. Since a has the highest prioritization value (see column sum in Table4.7 and line 20 of Algorithm 4.8), a is the first reflection chosen. is chosen, similarly: dim 4,5 (b)+=1. Later on, either c or d will be chosen. Let us assume d is chosen first. Then dim 4,5 (d)+ = 1 and dim 4 (c)+ = 1 are updated, since c and d have the same x src .

	4.4. FLOW-AWARE INPUT GEN.	CHAPTER 4. INFERENCE FOR XSS
	Algorithm 4.8: Control+Taint Flow-aware Fuzzing
	#IN: webapp, ctfm , fuzzer
	#OUT: vulns
	def control data aware fuzzing (webapp , ctfm , fuzzer ):
	vulns = []
	for refl in ctfm. get reflections ():
	webapp . reset ()
	prefix = shortest path (from=root ,to=refl.src)
	webapp . execute ( prefix )
	fuzzer . config .auth = webapp . context
	suffix = shortest path (refl.src ,refl.dst)
	fuzzer . config .urls = suffix
	vulns += fuzzer .do()
	return vulns
	class CTFM( Object ):
	reflections =[]
	def get reflections (self):
	chosen reflections =[]
	prioritization table .init ()
	while(len( chosen reflections ) < max input to fuzz ):
	chosen index=-1
	prioritization table .sort(key= lambda refl :( -refl.sum,
	refl. times chosen ))
	index having same sum =0
	for i in range (1, len( prioritisation table )):
	if( prioritization table [0]. times chosen <
	prioritization table [i]. times chosen ):
	break
	index having same sum =i-1
	chosen index = random . randint (0, index having same sum )
	chosen reflections . append ( reflections [ chosen index ])
	prioritization table . update dimensions ()
	return chosen reflections

a is added to chosen reflections. The dimensions of a are updated: dim 4,5 (a)+=1. Then b

Table 4 . 6

 46

: Dimensions of prioritization(reflection,chosen)

4.4.3 Chopping, a particular form of Slicing

Slicing permits to limit the state space exploration. This technique focuses on parts of the applications w.r.t. a slicing criterion. The notion of slicing has been extended to model-based languages. Various techniques are proposed in the literature

[START_REF][END_REF]

. In LigRE, we are interested in finding paths between a source t src and a destination t dst on the model. Thus we use a compressed form of slicing called chopping

Table 4 .

 4

	id	t src	x src	t dst	dim 1 dim 2 dim 3 dim 4 dim 5 sum chos.
	a	7 → 33 message2 7 → 33 1	1	0	0	0	-2 0
	b	7 → 17	msg	18 → 21 1	1	1	0	0	-3 0
	c	33 → 9	action	33 → 9 5	1	0	0	0	-6 0
	d 18 → 21	action	21 → 9 5	1	0	0	0	-6 0
				(initial state)
	id	t src	x src	t dst	dim 1 dim 2 dim 3 dim 4 dim 5 sum chos.
	a	7 → 33 message2 7 → 33 1	1	0	1	0	-3 1
	b	7 → 17	msg	18 → 21 1	1	1	0	0	-3 0
	c	33 → 9	action	33 → 9 5	1	0	0	0	-6 0
	d 18 → 21	action	21 → 9 5	1	0	0	0	-6 0
			(after the first iteration, a has been chosen)
	id	t src	x src	t dst	dim 1 dim 2 dim 3 dim 4 dim 5 sum chos.
	b	7 → 17	msg	18 → 21 1	1	1	1	0	-4 1
	c	33 → 9	action	33 → 9 5	1	0	0	0	-6 0
	d 18 → 21	action	21 → 9 5	1	0	0	0	-6 0
	a	7 → 33 message2 7 → 33 1	1	0	1	0	-3 1
			(after the second iteration, b has been chosen)
	id	t src	x src	t dst	dim 1 dim 2 dim 3 dim 4 dim 5 sum chos.
	c	33 → 9	action	33 → 9 5	1	0	1	0	-7 0
	d 18 → 21	action	21 → 9 5	1	0	1	0	-7 1
	a	7 → 33 message2 7 → 33 1	1	0	1	0	-3 1
	b	7 → 17	msg	18 → 21 1	1	1	1	0	-4 1
	(after the third iteration, d has been chosen, it could have been c also, see lines
				21-26 in Algorithm 4.8)

7: Prioritization of Reflections

  and can generate exploits targeting the discovered

	5.2. EVOLUTIONARY XSS FUZZING		CHAPTER 5. GA XSS FUZZING
		Reverse Engineering	-->	Directed Inputs	-->	Evolutionary Fuzzing
						Generation		Attack Input Grammar	Inputs Evolved by Genetic Algo.
	Application + Credentials	A. Control Flow Inference	Control Flow Model	B. Approximate Taint Flow Inference	Control + Data Flow Model	C. Chopping: Inputs Generation	Reflection Aware Non Malicious Inputs	D.1. Malicious Input Generation	Fuzzed Inputs	D.2. Precise Taint Flow Inference	Found Vulnerabilities
				LigRE					KameleonFuzz

  Can we exploit a potential sink? and XSS.3.3 How to prioritize inputs fuzzing?. So we need to track the taint up to the nodes of browser parse tree. Thus we perform this precise taint flow inference.

	5.2. EVOLUTIONARY XSS FUZZING	CHAPTER 5. GA XSS FUZZING
	XSS.2.2

Table 5 .

 5 1: Dimensions of the fitness functionExploitability A second step is to match the TAT T T dst with XSS specific TAP.

	.+	.+	.+
	Figure 5.7: The generic TAP detecting non syntactic confinement of a tainted value

  detects in black-box Mutation based Cross Site Scripting (m-XSS) caused by browser parser quirks. LigRE+KameleonFuzz is a black-box fuzzer which targets Type-1 and 2 XSS (Definition 8). DeMott et al. 2007, Rawat & Mounier 2010, Bekrar et al. 2012] target memory corruption vulnerabilities in a grey-box test context. Their fitness function contains the number of executed basic blocks and the singularity of inputs.[START_REF] Demott | [END_REF]] performs random 1-point crossover and 2-points mutation.[START_REF] Rawat | [END_REF][START_REF] Bekrar | A Taint Based Approach for Smart Fuzzing[END_REF]] perform offset aware mutations. KameleonFuzz is the first application of GA to the problem of black-box XSS search. Its fitness dimensions model the intuition of human security penetration testers.

					5.4. RELATED WORK
	[
	Genetic	Algorithm	(GA)	for	black-box	secu-
	rity	testing has	been	applied	to	evolve	malwares
	[Noreen et al. 2009]	and	attacker	scripts	[Budynek et al. 2005].

Table 6 . 2 :

 62 LigRE ABC+D (D=w3af) detection capabilities on the tested applications

	Application Inferred	True XSS	Nodes Transitions
		Taint-Flows	Detected
	P0wnMe	28	2	13	51
	WebGoat	134	4	20	80
	Gruyere	23	3	30	130
	WordPress 52	2	15	129
	Elgg	59	1	49	214
	PhpBB	213	4	63	279
	e-Health	12	5	15	33

Table 6 .

 6 2 contains the numbers of annotated reflections, found XSS, inferred nodes and transitions. This illustrates the practicality of LigRE to infer the control and taint flow models of the evaluated applications. The number of nodes and transitions, may correspond to a partial application coverage. Figure6.1 represents the number of detected true XSS vulnerabilities for the LigRE A+D and LigRE ABC+D shows that taint flow inference(B) and slices for flow aware fuzzing(C) also increase XSS detection capabilities. We notice that LigRE ABC+D founds vulnerabilities missed by other scanners, including LigRE A+D (D=w3af): see the non-dotted part of Figure6.1.

	6.2. LIGRE EVALUATION	CHAPTER 6. XSS EXPERIMENTS
	considered scanners and applications. LigRE ABC+D (D=w3af) detected the highest
	number of vulnerabilities for every application, and several vulnerabilities not de-
	tected by other scanners. These results confirm [Doupé et al. 2012]'s experiments:
	improving the control flow inference(LigRE A+D ) increases the vulnerability detec-
	tion capabilities, as compared to non macro-state-aware scanners (Wapiti, w3af(D),
	Skipfish). Moreover, comparing

  RQ3. (Current Use by Testers): What is the current use of CTFM by testers?

	6.2. LIGRE EVALUATION	CHAPTER 6. XSS EXPERIMENTS
	Taint flow inference is the main barrier to entry of LigRE. If acceptable,
	LigRE had the highest detection capabilities. Otherwise, traditional
	scanners are of interest.

  lists the results of the black-box scanners against each application. In our experiments, KameleonFuzz detected the highest number of XSS, and several XSS missed by others. The union of the distinct true XSS found by the scanners is 35.

	LigRE+w3af finds 23 35 = 65.7% of the known true XSS, whereas LigRE+KameleonFuzz finds 32 35 = 91.4%. KameleonFuzz improves XSS
	detection capabilities.
		8 8
	# Distinct Detected True XSS	2 4 6 2 4 6	detected by multiple scanners
		0 0
		P0wnMe WebGoat Gruyere WordPress Elgg P0wnMe P0wnMe P0wnMe WebGoat P0wnMe WebGoat WebGoat P0wnMe P0wnMe P0wnMe P0wnMe P0wnMe P0wnMe Gruyere Gruyere Gruyere Gruyere WebGoat WebGoat WordPress Gruyere WordPress WordPress Gruyere Gruyere Gruyere Gruyere Gruyere Gruyere WordPress WordPress Elgg PhpBB Elgg Elgg PhpBB PhpBB Elgg	eHealth PhpBB eHealth eHealth PhpBB
	Wapiti w3af SkipFish LigRE+w3af LigRE+KameleonFuzz

  Detection Efficiency of Black-Box XSS Scanners navigate correctly, w3af is more efficient than other scanners at finding non filtered XSS. In our experiments, mainly happened in P0wnMe and Gruyere. In applications with more macro-states, assuming the cost of control+taint flow inference is acceptable, LigRE improves vulnerability detection. Starting from 900 HTTP requests, LigRE+KameleonFuzz detects more vulnerabilities per number of requests than LigRE+w3af. For instance, after 2200 requests per application, fuzzing with KameleonFuzz detects 42.9% more XSS than fuzzing with w3af. On the LigRE+w3af and LigRE+KameleonFuzz curves, we can observe several landings, which mostly correspond to the end of the LigRE control+taint flow inference for a given application.Even though we only experimented with Type-1 and 2 XSS vulnerabilities, we are confident that the KameleonFuzz approach can be applied to other types of WCI, with proper adaptations (e.g., attack grammar), as shown in Table6.4. Such adap-

	6.4. DISCUSSION	CHAPTER 6. XSS EXPERIMENTS
	0 • CVE-2013-7297 -1 Type-2 XSS in Elgg 1.8.13 (impact: Elgg is notably 500 1,000 1,500 2,000 0 10 20 30 HTTP requests per application Wapiti w3af Skipfish LigRE+w3af LigRE+KameleonFuzz used by the Australia Governement, Wiley Publishing, the University of Florida) [Duchène 2013a] • CVE-2014-1599 -39 Type-1 XSS in SFR BOX NB6-MAIN-R3.3.4 (im-pact: ∼ 5.2 Million users + possibility of changing the routing table) [Duchène 2014a] • 1 Type-1 XSS and 2 Type-2 XSS in Siemens-Home (impact: user imperson-ation, customer data thief, privilege escalation) [Duchène 2014c] • 4 Type-1 and 4 Type-2 XSS in Siemens e-Health (impact: privilege escala-tion) [Siemens 2014, Duchène 2014b] • 2 Type-2 XSS in HITB CFP (impact: privilege escalation) [Duchène 2014f] Unique Detected True XSS for all Applications • 1 Type-1 XSS in ITEA2 Diamonds Website [Duchène 2014b]
	6.4.2 Applicability to other Web Command Injections (WCI) Vulnerability Output Grammar Where to Parse? Cross Site Scripting HTML HTML page HPP Param. Pollution HTTP Reply Headers PHP Code Injection PHP argument of eval SQL Injection SQL arg. of sql query Shell Injection Shell . . . exec, system Table 6.4: Command Injections: Vulnerabilities, Output Grammars, and Observa-Figure 6.6: If the cost of LigRE inference is acceptable, then LigRE+KameleonFuzz tion Points
	is more efficient than LigRE+w3af.
	Otherwise, w3af alone is of interest.
	6.4 Discussion
	On 6.4.1 Found 0-days XSS considered	applications,	.6. below	approximatively	800
	HTTP requests per application, w3af is the most efficient scanner. Thus we During the experiments, I found the following XSS. We describe two of them in
	hypothesize that in applications with few macro-states, assuming it is able to the appendix at page 155.

Table 8 . 1 :

 81 .1, we list possible reasons behind the low adoptions of the aforementioned XSS counter-measures. Difficulties behind the Low Adoption of XSS Counter-Measures 8.1.4 Application to other Web Command Injections (WCI)

	Defense		Barriers to adoption		Server	Client
							Impact	Impact
	Client-Side	-adherence to browser version		x
	Sanitizer		-may break applications
	WAF		may break applications
	Trusted DOM may break applications		x
	HTML5		scope very limited (e.g., not applicable	x	x
	IFrame Sand-	for Java, Flash)
	box
	DOM	ran-	-	may	break	applications	x	x
	domization	-only make exploit less reliable
	CSP		-non trivial amount of adaptations	x
			[Weinberger et al. 2011b] -96% of
			Alexa top 1000 use CSP-incompatible
			code patterns [Golubovic 2013]
	Static Rewrit-	-	may	break	applications	x
	ing		-limited to ASP.Net applications

Unauthorized hacker having malicious intentions; of course, the notion of maliciousness is dependent on the entity which assesses it.

 2 The process of cloning credit

cards.3 Network of bots, computer nodes controlled by an attacker.

In the responsible disclosure vulnerability model, vendors having a vulnerability in their product are allowed a period of grace before the security researcher who discovered this vulnerability makes it public.

We highlight text to indicate that it is part of a taint flow (partial string copy).

In this example, the form submission method is POST, and the url to submit the form contains parameters which will be sent using the GET method.

In the webpage .

[Goldsmith & Davis 1997] D. Goldsmith et M. Davis. UTF-7 RFC 2152, 1997. http: //tools.ietf.org/rfc/rfc2152.txt.

Michael D Ernst. HAMPI: a solver for string constraints. In Proceedings of the eighteenth international symposium on Software testing and analysis, pages105-116. ACM, 2009.

[Mulliner & Miller 2009] Collin Mulliner et Charlie Miller. Fuzzing the phone in your phone. Black Hat USA, vol. 25, 2009.

Acknowledgements 5

Control Flow Notions

The history of inputs and outputs serves to build a navigation tree, which is used to build a CFM. Both are colored. Their coloration evolves to characterize the macro-states. HANDLER = ( "onload" | "onerror" | .. Generating a fuzzed value consists in performing a stepwise expansion [START_REF] Holler | [END_REF] through the production rules of an AIG and, if applicable, performing choices. Producing the corresponding string from a fuzzed value consists in concatenating the strings obtained by a depth-first exploration of the context subtree, representing this string in a given charset, applying the anti-filter function, and applying an encoding function. For instance, the string that results from the fuzzed value of Figure 5.3 is WUkp' \t onload='alert(94478), on which the identity function is applied as an anti-filter, and with no encoding change (node plain), and the resulting string in UTF-8 charset.

In Algorithm 5.2, we illustrate the algorithm to transduce a production tree to a concrete fuzzed value.

CHAPTER 7. OTHER APPROCHES

Java application. They need to balance between over and under approximation [Sankaranarayanan et al. 2013]. [START_REF] Stock | 25 Million Flows Later -Large-scale Detection of DOM-based XSS[END_REF]] crawls in the first reachable transitions from the start node from various web applications, propagated the taint in white-box in javascript objects and submitted XSS attack vectors from a library. Even though only the first transitions are covered, they found numerous DOM Cross Site Scripting (a.k.a. Type-0 XSS) (DOM-XSS), which shows that those web applications were not tested w.r.t. such vulnerabilities.

Grey-Box Approaches generally combine static and dynamic analysis techniques, at the assembly level. [START_REF] Rawat | [END_REF] statically search for Buffer Overflow (BOF) sinks at the assembly level. [DeMott et al. 2012b[START_REF] Bekrar | A Taint Based Approach for Smart Fuzzing[END_REF][START_REF] Bekrar | Finding Software Vulnerabilities by Smart Fuzzing[END_REF]] use data taint propagation at the assembly level to determine where to apply anomaly operators. Depending on the complexity and required precision of the process, the taint can be inferred in web application [START_REF] Madou | [END_REF], or propagated precisely (e.g., [START_REF] Doupé | [END_REF] in .Net applications).

Symbolic Execution consists in expressing branches choices w.r.t. conditions on inputs. Iteratively, the application is restarted and inputs are modified for the application to take another branch. The goal is to increase branch coverage. The SAGE fuzzer by [Godefroid et al. 2008] found various Memory Corruption Vulnerabilities (Memory Corruption Vulnerability (MCV)) in Microsoft Office products. Microsoft uses it daily and use their idle computing power to solve billions of constraints [START_REF] Bounimova | Billions and billions of constraints: Whitebox fuzz testing in production[END_REF]. KLEE by [Cadar et al. 2008a] found many vulnerabilities in open-source projects. Those approaches assume the availability of the source code. Symbolic execution techniques have also been used for finding Web Command Injections (WCI) in web applications: [START_REF] Kiezun | [END_REF], Wassermann et al. 2008, Saxena et al. 2010a] generate string constraints and then solve those to generate input sequences containing one fuzzed value. Symbolic execution has also been applied in a grey-box context (e.g., at binary level): [Campana 2009]. Recently, concolic execution is gaining adoption, as it permits to simplify certain constraints by using concrete values and thus reduces the search space. However, all the public work still assumes the availability of the source code [START_REF] Haller | Dowsing for overflows: a guided fuzzer to find buffer boundary violations[END_REF], Feist et al. 2013].

Symbolic execution techniques are starting to be used in passive testing: [Mouttappa et al. 2013b].

Black-Box Approaches

Black-Box security testing distinguish between passive techniques (e.g., monitoring) and active techniques which submit inputs to the applications. Black-box techniques produce a knowledge, often in the form of a model or a grammar, from which inputs are produced.

CHAPTER 7. OTHER APPROCHES

text from e.g., the source code [START_REF] Balint | Automatic inference of model fields and their representation[END_REF], or inferred in black-box [START_REF] Shahbaz | [END_REF] via the observed behavior at the application interfaces.

List of Figures

List of Tables

Web Scanners Configuration

We here list the main settings used during experiments .

• Wapiti 2.20: -m "-all,xss" percentageOfPopulationMigratingFromOneIslandOrPoolToAnotherOne " value="0.04" /> <param name="PopulationSize" value="10" /> <param name="PopulationTakingPartInRecombination" value="1.00" />  <param name="Elitism" value="2" /> <param name="crossoverNodeSelectionAndNumberOfPointsStrategy" value="samePrefix_and_1NodeRandom" />  <param name="mutationRate" value="0.5" /> <param name="mutationStrategy" value="random" />  <param name="firstGenerationInputParamSelectOneInXPercents" value="0.8" /> <param name="modelMaxDepthForPrefixingInputSequences" value="7 " /> </EvolutionaryAlgorithmConfig> <Fitness>  <param name="number_of_classes_injected_vs_sent" value="2" /> <param name="string_distance" value="2" /> <param name="number_of_tainted_nodes" value="3" /> <param name=" number_of_nodes_between_fuzzed_input_sending_and_reflection " value="2" /> <param name="number_of_unique_states_from_start_node" value=" 0.5" /> <param name="how_well_formed_wrt_HTML_is_the_output" value=" 0.5" /> <param name="new_output_symbol_discovered" value="5" /> <param name="percentage_of_expected_output_symbols" value="3" /> <param name=" number_of_different_macro_states_between_fuzzed_value_submission_and_reflection " value="1" /> <param name="singularity_on_fuzzed_input_param_value" value= "4" /> <param name="singularity_on_input_sequence" value="3" /> </Fitness> <InternalTests> <param name="run" value="True" /> </InternalTests> <Crawling> <param name="stop.when_conjecture_is_complete" value="True" /> <param name="stop.max_duration" value="0" />  <param name="stop.max_num_of_http_requests" value="200" /> <param name="longest_path.max_times_per_edge" value="7" /> <param name="longest_path.max_times_per_node" value="7" /> <param name="longest_path.max_depth_of_subsequence" value="10" /> <param name="stop.

minimum_number_of_times_we_went_trough_each_transition" value="7" /> <param name="stop.minimum_number_for_all_clusters" value="7" / > <param name="stop.

number_of_times_to_go_through_each_link_and_no_new_page_discovered " value="7" /> <param name=" max_explored_times_for_a_transition_for_djisktra_computation " value="7" /> <param name="max_depth_of_input_sequence" value="170" /> <param name="conjecture.

max_consecutive_potential_contradictions" value="4" /> <param name="follow_external_links" value="none" /> <param name="conjecture.strategy" value="from_root" /> <param name=" once_emergency_sequence_executed_forbid_emergency_for_x_requests " value="2" /> <param name="save_model_in_config_folder" value="True" /> <param name="load_last_model_in_config_folder" value="True" /> <param name="folder_where_to_save_progression" value="logs/ gruyere/0_inferred_models/" /> <param name="folder_where_to_save_and_load" value="logs/" />   <param name="crawled_model_filename_suffix" value=" crawled_model.json" />  <param name="prefix_tree.fields_to_ignore" value="form.hidden.

nonce" />  <param name="http_request_comparison.fields_to_ignore" value=" params_structured.nonce" />

APPENDIX A. WEB SCANNERS CONFIGURATION

" value="0" /> <param name="confidence.weight.number_of_incoming_edges" value ="0.1" /> <param name="conjecture.

consider_only_first_spiderpage_for_confidence_computation" value="True" /> <param name="raiseExceptionWhenEmptyForms" value="False" />  <param name="infered_model.filename_suffix" value=" infered_model.pickle" /> <param name="infered_model.

number_of_folders_in_which_to_search_for" value="3000" />  <param name="skip_outputting_graphs" value="False" /> <param name="die_in_case_of_exception" value="False" /> <param name="exit_after_inference" value="True" /> <param name="stopping.finish_outputting_graphviz_files" value= "True" /> <param name="stopping.timeout" value="200" /> <param name="state_change.score.num_of_parameters" value="0. no_more_polar_bears" />  <param name=" expand_prefilled_values_with_one_of_length_greater_of_equal_than_min_length_to_infer_t " value="True" /> </CrawlingFieldsValues> <CrawlingSlicing>    <param name="max_index_of__do_not_follow" value="10" /> <param name="do_not_follow[0]" value="GET /xss-type-1/?action= logout" encoding="plain" /> <param name="do_not_follow[3]" value="FORM_FIELD_VALUE orlandopassword" encoding="plain" /> <param name="do_not_follow [4]" value="GET /xss-type-1/?action= auth" encoding="plain" /> <param name="do_not_follow [5] -efficient_substring -edit_distance --> <param name="efficient_substring.min_string_length" value="6" />  <param name="modelMaxBackwardDepthForAnnotatingTaint" value="7 " />  <param name="modelMaxInputSequencesLength" value="8" />   <param name="save_annotated_model_in_config_folder" value="

True" />  <param name="load_last_annotated_model_in_config_folder" value ="True" /> <param name="folder_where_to_save_and_load" value="logs/ gruyere/1_annotated_models" />  APPENDIX A. WEB SCANNERS CONFIGURATION  <param name="annotated_model_filename_suffix" value=" annotated_model.pickle" /> <param name="graphviz.generate" value="True" /> <param name="graphviz.in_folder" value="logs/gruyere/1 _annotated_models" /> <param name="graphviz.representation_type" value=" concise_from_and_to_transition" />  <param name="exit_after_model_annotation" value="False" /> <param name="list_reflections" value="True" /> <param name="list_reflections.exit_after" value="False" /> </ModelAnnotation> <TaintInferenceConfig> <param name="useExactStringMatchingFirst" value="true" /> <!-true, false --> <param name="distance" value="sekar_basic" />  <param name="costInsertion" value="1" /> <param name="costDeletion" value="1.9" /> <param name="minimumLengthOfTaintedStrings" value="6" /> <param name="sekar.minLengthOfTaintedSubstringsInOutput" value ="6" /> <param name="propagation.minLengthOfOutputSubstring" value="6" /> <param name="propagation.minLengthOfInputSubstring" value="6" /> <param name="maxDistanceToTaint" value="1" />   <param name="DOMTaintIfNodeAlone" value="0.65" /> <param name="DOMTaintIfNodeWithBrother" value="0.40" /> <param name="DOMTaintMaxNodeDistance" value="2" /> <param name="TaintPropagationOnDOM" value="substring" />   <param name="assertSamePageIsReached" value="False" /> </

0-day Found XSS Vulnerabilities

Two of the 0-days XSS discovered by KameleonFuzz

We illustrate two 0-day XSS that KF uncovered:

• Elgg: Type-2 XSS (CVE-2013-7297). The control flow inference, the reflections, and the taint aware patterns permit detecting this XSS present since several versions.

• SFR BOX NB6-MAIN-R3.3.4: 39 Type-1 XSS (CVE-2014-1599). The control flow inference permits navigating sufficiently deep enough in the application.

Elgg 1.8.13: 1 Type-2 XSS (CVE-2013-7297)

Elgg is an open-source social network notably used by the University of Florida and the Australian governement. Elgg 1.8.13 suffers from an unfiltered Type-2 XSS in the website field of the user (see Figure C.1). This vulnerability has been responsibly reported [Duchène 2013a]. Example of exploitation scenario If a user is tricked into authenticating into its interface, an attacker can XSS the user, and thus getting read and write access to the router configuration webpages. Such as scenario is mainly possible due to non filtered reflections (mainly Type-1 / reflected) and the lack of Content Security Policy. Moreover, no anti-CSRF token such as view-states are present, thus there is the possibility of modifying the routing tables even without an XSS, if the user is authenticated in the box.

A non limitative list of actions include:

• getting authentication credentials (wireless, DSL credentials)

• rebooting the router

• modifying the route table (thus possibility of content injection if an attacker controlled server is on the route)

• DDOSing a target with numerous XSS'ed clients

Examples of Vulnerabilities that KameleonFuzz is unable to detect

We illustrate three vulnerabilities that KF is unable to detect as of today:

• mega.co.nz: cross-domain double parameter HTML injection. Kame-leonFuzz only supports one fuzzed input parameter value at a time.

• Evernote: unconstrained URL handler (CVE-2014(CVE- -1404)). KameleonFuzz test drivers only support websites ; a CTFM containing reflections into libc parameters is required to detect this vulnerability.

• Siemens-Home: Two type-2 Reflections in HTML context result in IE-7 XSS. KameleonFuzz only supports one fuzzed input parameter value at a time. I reported using a responsible disclosure process an Unconstrained file handler which permits attacker controlled code execution [Duchène 2014e].

We can provide a local executable file in the URL field (¡source-url¿ tag) of a note. Once the note is opened or imported:

• on Mac OS X, if a user is tricked into clicking on info, open, it results in attacker controlled shell command execution. No warning whatsoever is displayed to the user

• on Windows, a warning to the user is presented, but this still is a risk on this platform and should be prevented This is not a trivial XSS in the sense there is a server sanitizer in place (maybe a WAF). So far, its observed behavior exhibits the following constraint: Constraint 1: If the substring < immediately followed by a character in [a-Z] is present in any parameter, then the request is not processed, and we are redirected to an error page (see Figure C.14). Thus the fuzzed values <b or <u are blocked by the sanitizer.