  Fuzz testing (fuzzing) is a well-known method for exposing
bugs/vulnerabilities in software systems. Popular fuzzers, such as AFL, use a
biased random search over the domain of program inputs, where 100s or 1000s of
inputs (test cases) are executed per second in order to expose bugs. If a bug
is discovered, it can either be fixed manually by the developer or fixed
automatically using an Automated Program Repair (APR) tool. Like fuzzing, many
existing APR tools are search-based, but over the domain of patches rather than
inputs.
  In this paper, we propose search-based program repair as patch-level fuzzing.
The basic idea is to adapt a fuzzer (AFL) to fuzz over the patch space rather
than the input space. Thus we use a patch-space fuzzer to explore a patch
space, while using a traditional input level fuzzer to rule out patch
candidates and help in patch selection. To improve the throughput, we propose a
compilation-free patch validation methodology, where we execute the original
(unpatched) program natively, then selectively interpret only the specific
patched statements and expressions. Since this avoids (re)compilation, we show
that compilation-free patch validation can achieve a similar throughput as
input-level fuzzing (100s or 1000s of execs/sec). We show that patch-level
fuzzing and input-level fuzzing can be combined, for a co-exploration of both
spaces in order to find better quality patches. Such a collaboration between
input-level fuzzing and patch-level fuzzing is then employed to search over
candidate fix locations, as well as patch candidates in each fix location.
