SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis
Fuzz testing has been gaining ground recently with substantial efforts devoted to the area. Typically, fuzzers take a set of seed inputs and leverage random mutations to continually improve the inputs with respect to a cost, e.g. program code coverage, to discover vulnerabilities or bugs. Following...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2019
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/4820 https://ink.library.smu.edu.sg/context/sis_research/article/5823/viewcontent/ASE19_GrammarbasedFuzzing3.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-5823 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-58232020-01-16T09:54:56Z SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis LE, Xuan Bach D. PASAREANU, Corina PADHYE, Rohan LO, David VISSER, Willem SEN, Koushik Fuzz testing has been gaining ground recently with substantial efforts devoted to the area. Typically, fuzzers take a set of seed inputs and leverage random mutations to continually improve the inputs with respect to a cost, e.g. program code coverage, to discover vulnerabilities or bugs. Following this methodology, fuzzers are very good at generating unstructured inputs that achieve high coverage. However fuzzers are less effective when the inputs are structured, say they conform to an input grammar. Due to the nature of random mutations, the overwhelming abundance of inputs generated by this common fuzzing practice often adversely hinders the effectiveness and efficiency of fuzzers on grammar-aware applications. The problem of testing becomes even harder, when the goal is not only to achieve increased code coverage, but also to find complex vulnerabilities related to other cost measures, say high resource consumption in an application.We propose Saffron an adaptive grammar-based fuzzing approach to effectively and efficiently generate inputs that expose expensive executions in programs. Saffron takes as input a user-provided grammar, which describes the input space of the program under analysis, and uses it to generate test inputs. Saffron assumes that the grammar description is approximate since precisely describing the input program space is often difficult as a program may accept unintended inputs due to e.g., errors in parsing. Yet these inputs may reveal worst-case complexity vulnerabilities. The novelty of Saffron is then twofold: (1) Given the user-provided grammar, Saffron attempts to discover whether the program accepts unexpected inputs outside of the provided grammar, and if so, it repairs the grammar via grammar mutations. The repaired grammar serves as a specification of the actual inputs accepted by the application. (2) Based on the refined grammar, it generates concrete test inputs. It starts by treating every production rule in the grammar with equal probability of being used for generating concrete inputs. It then adaptively refines the probabilities along the way by increasing the probabilities for rules that have been used to generate inputs that improve a cost, e.g., code coverage or arbitrary user-defined cost. Evaluation results show that Saffron significantly outperforms state-of-the-art baselines. 2019-11-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4820 info:doi/10.1145/3364452.3364455 https://ink.library.smu.edu.sg/context/sis_research/article/5823/viewcontent/ASE19_GrammarbasedFuzzing3.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Software Engineering |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Software Engineering |
spellingShingle |
Software Engineering LE, Xuan Bach D. PASAREANU, Corina PADHYE, Rohan LO, David VISSER, Willem SEN, Koushik SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis |
description |
Fuzz testing has been gaining ground recently with substantial efforts devoted to the area. Typically, fuzzers take a set of seed inputs and leverage random mutations to continually improve the inputs with respect to a cost, e.g. program code coverage, to discover vulnerabilities or bugs. Following this methodology, fuzzers are very good at generating unstructured inputs that achieve high coverage. However fuzzers are less effective when the inputs are structured, say they conform to an input grammar. Due to the nature of random mutations, the overwhelming abundance of inputs generated by this common fuzzing practice often adversely hinders the effectiveness and efficiency of fuzzers on grammar-aware applications. The problem of testing becomes even harder, when the goal is not only to achieve increased code coverage, but also to find complex vulnerabilities related to other cost measures, say high resource consumption in an application.We propose Saffron an adaptive grammar-based fuzzing approach to effectively and efficiently generate inputs that expose expensive executions in programs. Saffron takes as input a user-provided grammar, which describes the input space of the program under analysis, and uses it to generate test inputs. Saffron assumes that the grammar description is approximate since precisely describing the input program space is often difficult as a program may accept unintended inputs due to e.g., errors in parsing. Yet these inputs may reveal worst-case complexity vulnerabilities. The novelty of Saffron is then twofold: (1) Given the user-provided grammar, Saffron attempts to discover whether the program accepts unexpected inputs outside of the provided grammar, and if so, it repairs the grammar via grammar mutations. The repaired grammar serves as a specification of the actual inputs accepted by the application. (2) Based on the refined grammar, it generates concrete test inputs. It starts by treating every production rule in the grammar with equal probability of being used for generating concrete inputs. It then adaptively refines the probabilities along the way by increasing the probabilities for rules that have been used to generate inputs that improve a cost, e.g., code coverage or arbitrary user-defined cost. Evaluation results show that Saffron significantly outperforms state-of-the-art baselines. |
format |
text |
author |
LE, Xuan Bach D. PASAREANU, Corina PADHYE, Rohan LO, David VISSER, Willem SEN, Koushik |
author_facet |
LE, Xuan Bach D. PASAREANU, Corina PADHYE, Rohan LO, David VISSER, Willem SEN, Koushik |
author_sort |
LE, Xuan Bach D. |
title |
SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis |
title_short |
SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis |
title_full |
SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis |
title_fullStr |
SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis |
title_full_unstemmed |
SAFFRON: Adaptive grammar-based fuzzing for worst-case analysis |
title_sort |
saffron: adaptive grammar-based fuzzing for worst-case analysis |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2019 |
url |
https://ink.library.smu.edu.sg/sis_research/4820 https://ink.library.smu.edu.sg/context/sis_research/article/5823/viewcontent/ASE19_GrammarbasedFuzzing3.pdf |
_version_ |
1770575054206140416 |