Download: PDF.
“Grammar-based whitebox fuzzing” by Patrice Godefroid, Adam Kieżun, and Michael Y. Levin. In PLDI 2008, Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, (Tucson, AZ, USA), June 9-11, 2008, pp. 206-215.
Whitebox fuzzing is a form of automatic dynamic test generation, based on symbolic execution and constraint solving, designed for security testing of large applications. Unfortunately, the current effectiveness of whitebox fuzzing is limited when testing applications with highly-structured inputs, such as compilers and interpreters. These applications process their inputs in stages, such as lexing, parsing and evaluation. Due to the enormous number of control paths in early processing stages, whitebox fuzzing rarely reaches parts of the application beyond those first stages.
In this paper, we study how to enhance whitebox fuzzing of complex structured-input applications with a grammar-based specification of their valid inputs. We present a novel dynamic test generation algorithm where symbolic execution directly generates grammar-based constraints whose satisfiability is checked using a custom grammar-based constraint solver. We have implemented this algorithm and evaluated it on a large security-critical application, the JavaScript interpreter of Internet Explorer 7 (IE7). Results of our experiments show that grammar-based whitebox fuzzing explores deeper program paths and avoids dead-ends due to non-parsable inputs. Compared to regular whitebox fuzzing, grammar-based whitebox fuzzing increased coverage of the code generation module of the IE7 JavaScript interpreter from 53% to 81% while using three times fewer tests.
Download: PDF.
BibTeX entry:
@inproceedings{GodefroidKY2008,
author = {Patrice Godefroid and Adam Kie{\.z}un and Michael Y. Levin},
title = {Grammar-based whitebox fuzzing},
booktitle = {PLDI 2008, Proceedings of the {ACM} {SIGPLAN} 2008
Conference on Programming Language Design and Implementation},
pages = {206--215},
address = {Tucson, AZ, USA},
month = {June~9--11,},
year = {2008}
}
(This webpage was created with bibtex2web.)
Back to Program Analysis Group publications.