  Fuzzing technologies have evolved at a fast pace in recent years, revealing
bugs in programs with ever increasing depth and speed. Applications working
with complex formats are however more difficult to take on, as inputs need to
meet certain format-specific characteristics to get through the initial parsing
stage and reach deeper behaviors of the program. Unlike prior proposals based
on manually written format specifications, in this paper we present a technique
to automatically generate and mutate inputs for unknown chunk-based binary
formats. We propose a technique to identify dependencies between input bytes
and comparison instructions, and later use them to assign tags that
characterize the processing logic of the program. Tags become the building
block for structure-aware mutations involving chunks and fields of the input.
We show that our techniques performs comparably to structure-aware fuzzing
proposals that require human assistance. Our prototype implementation WEIZZ
revealed 16 unknown bugs in widely used programs.
