Abstract
Software testing is an important step in the software development life cycle. It focuses on testing software functionalities, finding vulnerabilities, and assuring the software is executing as expected. Fuzzing is a software testing technique which feeds random input to programs and monitors for abnormal behaviors such as a program crash. Fuzzing can be automated and does not require access to the source code compared to manually reviewing the source code which requires a huge amount of time and cost. It can trigger vulnerabilities that the programmers overlooked while programming, such as buffer overflow, off by one error, etc. One of the limitations of fuzzing is that most programs require highly structured input or certain input patterns and therefore the fuzz testing may be terminated at an early stage of program execution because of not meeting the input format requirements. Some previous studies resolve this problem by manually creating program specific input grammars to help guide fuzzing, which is tedious, error prone, and time consuming. However, this solution cannot work efficiently when testing multiple programs which require different input patterns. To solve this problem, a general grammar-based fuzzing technique is proposed and developed in this dissertation. The new fuzzer can extract grammar from the sample input files of a program, and then generate effective fuzzing files based on the grammar. This fuzzing tool is able to work with different programs by extracting grammars from them automatically and hence generating program specific fuzzing files. The goal of this research includes developing an algorithm to extract grammars from sample input files, generating effective fuzzing files to test the programs, and implementing a fuzzing tool using Python programming language. The main contribution of this research is helping software developers and security experts in revealing vulnerabilities in various programs automatically by using the developed fuzzing tool.