  Grey-box fuzz testing has revealed thousands of vulnerabilities in real-world
software owing to its lightweight instrumentation, fast coverage feedback, and
dynamic adjusting strategies. However, directly applying grey-box fuzzing to
input-dependent multithreaded programs can be extremely inefficient. In
practice, multithreading-relevant bugs are usually buried in sophisticated
program flows. Meanwhile, the existing grey-box fuzzing techniques do not
stress thread-interleavings which affect execution states in multithreaded
programs. Therefore, mainstream grey-box fuzzers cannot effectively test
problematic segments in multithreaded programs despite they might obtain high
code coverage statistics.
  To this end, we propose MUZZ, a new grey-box fuzzing technique that hunts for
bugs in multithreaded programs. MUZZ owns three novel thread-aware
instrumentations, namely coverage-oriented instrumentation, thread-context
instrumentation, and schedule-intervention instrumentation. During fuzzing,
these instrumentations engender runtime feedback to stress execution states
caused by thread interleavings. By leveraging the feedback in the dynamic seed
selection and execution strategies, MUZZ preserves more valuable seeds that
expose bugs in a multithreading context.
  We evaluate MUZZ on 12 real-world software programs. Experiments show that
MUZZ outperforms AFL in both multithreading-relevant seed generation and
concurrency-vulnerability detection. Further, by replaying the target programs
against the generated seeds, MUZZ also reveals more concurrency-bugs (e.g.,
data-races, thread-leaks) than AFL. In total, MUZZ detected 8 new
concurrency-vulnerabilities and 19 new concurrency-bugs. At the time of
writing, 4 CVE IDs have been assigned to the reported issues.
