Binary Grammars for Black-box Fuzzing
Loading...
Authors
Fryer, Andrew
Date
2024-04-23
Type
thesis
Language
eng
Keyword
Binary Parsing , Grammar , Fuzzing , Software Testing , Cybersecurity
Alternative Title
Abstract
Fuzz-testing has become a very effective technique for finding software security vulnerabilities and ensuring robustness of software systems. Perhaps the most influential advances in fuzzing are using grammars to intelligently generate structured test inputs and using execution data such as code coverage from the system under test to guide the fuzzing process.
Grammars have been developed through decades of research in formal language theory, which has also produced highly optimized parsing algorithms for textual data. However, the nature of binary data presents a different set of problems as even tokenization is context-dependent. Our first contribution is a comparison of the features and limitations of several popular or otherwise interesting binary parsing frameworks.
Our second, main contribution is demonstrating that grammars are useful both for guiding fuzzers when execution data is not readily available and for identifying potentially erroneous output data. Grammars describe complexity in the structure of input and output data which may be reflected in code branches in the system under test. We construct feature vectors which encode the structure of inputs and use these to guide the fuzzing process towards diverse input structures. We compare code coverage and coverage of input grammar features while fuzzing Knot DNS server using the LibAFL framework, comparing standard and grammar-based feedback algorithms.
Description
Citation
Publisher
License
Queen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution-ShareAlike 4.0 International
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution-ShareAlike 4.0 International