  Directed greybox fuzzing is a popular technique for targeted software testing
that seeks to find inputs that reach a set of target sites in a program. Most
existing directed greybox fuzzers do not provide any theoretical analysis of
their performance or optimality.
  In this paper, we introduce a complexity-theoretic framework to pose directed
greybox fuzzing as a oracle-guided search problem where some feedback about the
input space (e.g., how close an input is to the target sites) is received by
querying an oracle. Our framework assumes that each oracle query can return
arbitrary content with a large but constant amount of information. Therefore,
we use the number of oracle queries required by a fuzzing algorithm to find a
target-reaching input as the performance metric. Using our framework, we design
a randomized directed greybox fuzzing algorithm that makes a logarithmic (wrt.
the number of all possible inputs) number of queries in expectation to find a
target-reaching input. We further prove that the number of oracle queries
required by our algorithm is optimal, i.e., no fuzzing algorithm can improve
(i.e., minimize) the query count by more than a constant factor.
  We implement our approach in MC$^2$ and outperform state-of-the-art directed
greybox fuzzers on challenging benchmarks (Magma and Fuzzer Test Suite) by up
to two orders of magnitude (i.e., $134\times$) on average. MC$^2$ also found 15
previously undiscovered bugs that other state-of-the-art directed greybox
fuzzers failed to find.
