Abstract:
Recent advances in fuzz testing have introduced several
forms of feedback mechanisms, motivated by the fact that for a large range of programs and libraries, edge-coverage alone is insufficient to reveal
complicated bugs.
Inspired by this line of research, we examined existing program representations looking for a match between expressiveness of the structure and adaptability to the context of fuzz testing. In particular, we believe that data dependency graphs
(DDGs) represent a good candidate for this task, as the set of
information embedded by this data structure is potentially useful to
find vulnerable constructs by stressing combinations of def-use pairs that would be difficult for a traditional fuzzer to trigger.
Since
some portions of the dependency graph overlap with the control flow
of the program, it is possible to reduce the additional
instrumentation to cover only "interesting" data-flow dependencies,
those that help the fuzzer to visit the code in a distinct way
compared to standard methodologies.
To test these observations, we
proposed DDFuzz, a new approach that rewards the fuzzer not only
with code coverage information, but also when new edges in the data
dependency graph are hit.
Our results show that the adoption of data
dependency instrumentation in coverage-guided fuzzing is a promising
solution that can help to discover bugs that would otherwise remain
unexplored by standard coverage approaches.
This is demonstrated by
the 72 different vulnerabilities that our data-dependency driven approach can identify when executed on 38 target programs from three
different datasets.
