Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Software Engineering

Abstract: The software testing technique fuzzing has shown great success in finding defects and vulnerabilities. A fuzzer provides randomly generated inputs to a targeted software to expose erroneous behavior. To efficiently detect defects and bugs, generated inputs should be conforming to the basic structural semantics of the input format. This thesis presents an evolutionary grammar- based fuzzing approach to generate test cases, exposing erroneous behavior in parsers and interpreters. To reduce the time of generating non-conforming input files, the fuzzer uses probabilistic grammars to generate syntactically correct inputs. The fuzzer uses an evolutionary optimization approach to generate “complex” and “interesting” individuals, that may be more likely to trigger exceptional behavior. The evaluation of this evolutionary fuzzer shows the effectiveness of this approach in detecting defects and crashes. Applied to real-world applications on three common input formats (JSON, JavaScript, CSS), the approach was able to expose 13 unique defects.