Enhancing Directed Search in Black-box, Grey-box and White-box Fuzz Testin

Fuzz testing (or fuzzing) techniques, which include (model-based) black-box, coverage-based grey-box and white-box approaches, have become prominent in software testing. However, given an inadequate test suite they are not skilled at directing the exploration to reach given target locations and expose bugs in large program binaries that take highly-structured inputs. We observe that these limitations can be circumvented by improving the directed-ness of fuzzing approaches. In this thesis, we design a set of directed search algorithms for black-box, grey-box and white-box fuzz testing. The experimental evaluations on two applications of directed fuzzing --- crash reproduction and patch testing --- show that our tools (Hercules, MoBWF and AFLGo) effectively guide the search and successfully reproduce 19 crashes and discover 14 zero-day vulnerabilities (5 CVEs assigned) in large real-world (binary) programs (e.g., Adobe Reader, Windows Media Player, Binutils) taking highly-structured file formats (e.g., PNG, WAV, PDF).