  Mutation-based fuzzing is popular and effective in discovering unseen code
and exposing bugs. However, only a few studies have concentrated on quantifying
the importance of input bytes, which refers to the degree to which a byte
contributes to the discovery of new code. They often focus on obtaining the
relationship between input bytes and path constraints, ignoring the fact that
not all constraint-related bytes can discover new code. In this paper, we
conduct Shapely analysis to understand the effect of byte positions on fuzzing
performance, and find that some byte positions contribute more than others and
this property often holds across seeds. Based on this observation, we propose a
novel fuzzing solution, ShapFuzz, to guide byte selection and mutation.
Specifically, ShapFuzz updates Shapley values (importance) of bytes when each
input is tested during fuzzing with a low overhead, and utilizes contextual
multi-armed bandit to trade off between mutating high Shapley value bytes and
low-frequently chosen bytes. We implement a prototype of this solution based on
AFL++, i.e., ShapFuzz. We evaluate ShapFuzz against ten state-of-the-art
fuzzers, including five byte schedule-reinforced fuzzers and five commonly used
fuzzers. Compared with byte schedule-reinforced fuzzers, ShapFuzz discovers
more edges and exposes more bugs than the best baseline on three different sets
of initial seeds. Compared with commonly used fuzzers, ShapFuzz exposes 20 more
bugs than the best comparison fuzzer, and discovers 6 more CVEs than the best
baseline on MAGMA. Furthermore, ShapFuzz discovers 11 new bugs on the latest
versions of programs, and 3 of them are confirmed by vendors.
