Strategic parser fuzzing: leveraging domain knowledge for input generation

Abstract

Testing software is one of the most important parts of the development process. Without tests, programs would often crash or contain security vulnerabilities. Since testing is time-consuming and complex, techniques were developed to simplify this process. For instance, fuzzers create mostly random inputs and test how a program reacts to those. Especially software that uses parser for input processing is classified as interesting by us, but it is also hard to automatically test it with general purpose techniques—they cannot generate the syntactically correct inputs to test the program logic. Thus, we present a new approach specifically for analyzing software with recursive descent parsers. A central feature of parsers are the iterative comparisons of parts of the input against terminals of a respective context-free grammar. We show, how those comparisons from a program execution can be combined with other, parser-specific features to infer syntactically valid and diverse inputs. In our evaluation we combine our techniques with the fuzzer AFL. Our generated inputs contain on average 77.7% of all possible lexemes with more than three characters. We obtain on average a 2.9 and in best case up to 17 percentage points higher branch coverage in comparison to running AFL alone.

Das Testen von Software ist einer der wichtigsten Teile des Entwicklungsprozesses. Ohne Tests würden Programme häufig abstürzen oder Sicherheitslücken aufweisen. Da Testen zeitaufwändig und komplex ist, wurden Techniken entwickelt, um diesen Prozess zu vereinfachen. Zum Beispiel erstellen Fuzzer weitestgehend zufällige Eingaben und testen, wie ein Programm auf diese reagiert. Insbesondere Software, die Parser zur Eingabeverarbeitung nutzt, stufen wir als interessant ein, aber sie ist auch schwer automatisiert mit Allzwecktechniken zu testen – sie können die syntaktisch korrekten Eingaben zum Testen der Programmlogik nicht generieren. Deshalb präsentieren wir einen neuen Ansatz speziell zur Analyse von Software mit rekursiv absteigenden Parsern. Eine zentrale Eigenschaft von Parsern sind die iterativen Vergleiche von Eingabeteilen gegen die Terminale einer entsprechenden kontextfreien Grammatik. Wir zeigen, wie man die Vergleiche aus einer Programmausführung mit anderen, parserspezifischen Eigenschaften kombinieren kann, um syntaktisch valide und diverse Eingaben zu inferieren. In unserer Evaluation kombinieren wir unsere Techniken mit dem Fuzzer AFL. Unsere generierten Eingaben enthalten im Durchschnitt 77,7 % aller möglichen Lexeme mit mehr als drei Schriftzeichen. Wir erhalten eine durchschnittlich um 2,9 und im besten Fall bis zu 17 Prozentpunkte höhere Zweigüberdeckung im Vergleich zu einem Alleinlauf von AFL.