Idea Transcript
Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing Fabien Duchene
To cite this version: Fabien Duchene. Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing. Computation and Language [cs.CL]. Grenoble University, 2014. English.
HAL Id: tel-01102325 https://hal.archives-ouvertes.fr/tel-01102325 Submitted on 12 Jan 2015
HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
` THESE Pour obtenir le grade de
´ DE GRENOBLE DOCTEUR DE L’UNIVERSITE ´ Specialit e´ : Informatique ˆ e´ ministerial ´ Arret : 7 Aout ˆ 2006
´ ´ par Present ee
` Fabien Duchene ` dirigee ´ par Professeur Roland Groz These ´ par Docteur Jean-Luc Richier et co-encadree ´ ´ au sein Laboratoire d’Informatique de Grenoble prepar ee ´ ´ et de Ecole Doctorale Mathematiques, Sciences et Technologies de l’Information, Informatique
Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing ` soutenue publiquement le 2 Juin, 2014, These devant le jury compose´ de :
M. Jean-Luc RICHIER ` Charge´ de Recherche, CNRS, France, Co-encadrant de these
M. Roland GROZ ` Professeur, Grenoble INP, France, Directeur de these
M. Bruno LEGEARD ´ France, Rapporteur Professeur, Universite´ de Franche-Comte,
M. Herbert BOS Professeur, VU Amsterdam, Pays-Bas, Rapporteur
M. Mario HEIDERICH ¨ Bochum, Allemagne, Examinateur Docteur, Ruhr-Universitat
M. Yves DENNEULIN Professeur, Grenoble INP, France, Examinateur
2
Dedication
3
4
Acknowledgements
5
6
D´etection de Vuln´erabilit´es Web par Frelatage Evolutionniste et Inf´erence de Mod`ele R´esum´e: Le test est une approche efficace pour d´etecter des bogues d’impl´ementation ayant un impact sur la s´ecurit´e, c.-`a-d. des vuln´erabilit´es. Lorsque le code source n’est pas disponible, il est n´ecessaire d’utiliser des techniques de test en boˆıte noire. Nous nous int´eressons au probl`eme de d´etection automatique d’une classe de vuln´erabilit´es (Cross Site Scripting alias XSS) dans les applications web dans un contexte de test en boˆıte noire. Nous proposons une approche pour inf´erer des mod`eles de telles applications et frelatons des s´equences d’entr´ees g´en´er´ees a` partir de ces mod`eles et d’une grammaire d’attaque. Nous inf´erons des automates de contrˆole et de teinte, dont nous extrayons des sous-mod`eles afin de r´eduire l’espace de recherche de l’´etape de frelatage. Nous utilisons des algorithmes g´en´etiques pour guider la production d’entr´ees malicieuses envoy´ees a` l’application. Nous produisons un verdict de test grˆace a` une double inf´erence de teinte sur l’arbre d’analyse grammaticale d’un navigateur et a` l’utilisation de motifs de vuln´erabilit´es comportant des annotations de teinte. Nos impl´ementations LigRE et KameleonFuzz obtiennent de meilleurs r´esultats que les scanneurs boˆıte noire open-source. Nous avons d´ecouvert des XSS “0-day” (c.-`a-d. des vuln´erabilit´es jusque lors inconnues publiquement) dans des applications web utilis´ees par des millions d’utilisateurs.
Keywords: S´ecurit´e, Frelatage, XSS, Algorithme Evolutionniste, Inf´erence, Intelligence Artificielle, Applications Web
Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing Abstract: 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.
Keywords: Security, Fuzzing, XSS, Evolutionary Algorithm, Inference, Artificial Intelligence, Web Applications
Contents 1
. . . . .
11 11 13 15 15 16
. . . . .
17 18 22 31 32 32
3
Our Proposal 3.1 Model Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Evolutionary XSS Fuzzing . . . . . . . . . . . . . . . . . . . . .
35 35 38
4
Inference for XSS 4.1 Our Approach . . . . . 4.2 Control Flow Inference 4.3 Taint Flow Inference . 4.4 Flow-Aware Input Gen. 4.5 Implementation . . . . 4.6 Related Work . . . . .
2
5
6
Introduction 1.1 Context . . . . . . . 1.2 Vulnerabilities . . . . 1.3 Objectives . . . . . . 1.4 Contributions . . . . 1.5 Dissertation Structure
. . . . .
. . . . .
. . . . .
Problem Statement 2.1 Cross Site Scripting (XSS) 2.2 Definitions . . . . . . . . . 2.3 Fuzzing . . . . . . . . . . 2.4 Other WCI . . . . . . . . 2.5 Black-Box XSS Detection
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
43 43 44 61 65 67 69
GA XSS Fuzzing 5.1 Introduction . . . . . . . . 5.2 Evolutionary XSS Fuzzing 5.3 Implementation . . . . . . 5.4 Related Work . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
73 73 74 86 88
. . . .
91 91 92 97 101
. . . . . .
XSS Experiments 6.1 Evaluation methodology . 6.2 LigRE evaluation . . . . . 6.3 KameleonFuzz evaluation . 6.4 Discussion . . . . . . . . .
. . . .
. . . . 9
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
CONTENTS
CONTENTS
7
Other Approches 105 7.1 White & GreyBox . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.2 Black-Box Approaches . . . . . . . . . . . . . . . . . . . . . . . 106
8
Discussion & Conclusion 109 8.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 8.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
References List of Figures . . List of Tables . . List of Algorithms List of Listings . List of Acronyms
117 . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
132 133 135 137 139
A Web Scanners Configuration
141
B KameleonFuzz: List of Taint Aware tree Patterns
153
C 0-day Found XSS Vulnerabilities 155 Two of the 0-days XSS discovered by KameleonFuzz . . . . . . . . . . 155 Examples of Vulnerabilities that KameleonFuzz is unable to detect . . . 158 Appendices
131
10
C HAPTER 1
Introduction
Why did I rob banks? Because I enjoyed it. I loved it. Go where the money is...and go there often. [Sutton & Linn 2004]
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. [Einstein 1955]
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]
1.1
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 >[X]
Listing 2.1: Excerpt of P0wnMe Output for the Transition 18 → 21
The value of the input parameter msg, sent in the transition t src = 7 → 17, is reflected in 18 → 21: we observe it into the output. This reflection is not filtered: the exact value sent in 7 → 17 is copied into the output of tdst = 18 → 21.
1
We highlight text to indicate that it is part of a taint flow (partial string copy).
19
2.1. CROSS SITE SCRIPTING (XSS) CHAPTER 2. PROBLEM STATEMENT
start GET / 0
GET /
GET /?action=auth& 2
GET /?action= logout&
POST /? {}
POST /? {'login': 'yoda', 'password': 'DoOrDoNot'} GET /? POST /? {'message2': '/'}
7 POST /? {'message2': '2_e_g_a_s_sem '}
GET / POST /? GET /?action= {'action': 'save_message' message& 'msg': 'buenosdias '} 33
17 GET /? 18
GET /?action= view_messages
GET /?
GET /
GET /?action= GET /?action= view_messages& view_messages 21 GET /?action=delete _message&id=1 9
GET /?action= view_messages
Figure 2.5: Extract of a Control Flow Model of the P0wnMe Web Application 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 tdst = 18 → 21 is ...of saved messages buenosdias