Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Die Vorstellung findet auch digital per Zoom statt. Eine Zoom-Einladung finden Sie hier. (nur mit Informatik-Account)

Titel:
Grammar-Based Fuzzing with Language-Like Semantic Constraints

Abstract:

The modern scientific and end user landscape more than ever relies on complex software.
This software is written in many programming languages. Further, several new languages
being developed over the years and all of them have a need for compilers, interpreters, and
linters.
A common fact in software-engineering is, that any non-trivial piece of software likely
contains bugs. This, in combination with the fact, that compilers tend to be anything
but trivial pieces of software (GCC has more than 15M lines of code1), they are almost
guaranteed to contain bugs. While many bugs are innocuous at most impacting usability
and user adoption, some bugs are critical, potentially crashing systems or even introducing
security issues.
This possible criticality and the inherent trust that users have to extend towards these
low level tools necessitates testing of them. This need of testing is complicated by the fact,
that programming languages are computationally complicated. Programming language
inputs usually have to fulfill lexical, syntactical, and semantical requirements. To generate
inputs, there are two general approaches: mutative approaches, which take existing inputs
and change them in some capacity, and generative approaches, which create new inputs
without any pre-existing inputs.
In this dissertation I provide fluent, a formalism which enables embedding language-like
semantic constraints into context-free language grammars and a tool which can then
use these enhanced grammars to fuzz complex systems with semantically correct inputs.
One of the main goals is simplifying and shortening the process of developing reasonably
well performing tools for complex languages. To this end, fluent consistently outperforms
grammar-based fuzzing baselines on languages for which no state-of-the-art tool exists,
while being competitive with state-of-the-art tools if they exist.