  Domain Name System (DNS) is a critical component of the Internet. DNS
resolvers, which act as the cache between DNS clients and DNS nameservers, are
the central piece of the DNS infrastructure, essential to the scalability of
DNS. However, finding the resolver vulnerabilities is non-trivial, and this
problem is not well addressed by the existing tools. To list a few reasons,
first, most of the known resolver vulnerabilities are non-crash bugs that
cannot be directly detected by the existing oracles (or sanitizers). Second,
there lacks rigorous specifications to be used as references to classify a test
case as a resolver bug. Third, DNS resolvers are stateful, and stateful fuzzing
is still challenging due to the large input space.
  In this paper, we present a new fuzzing system termed ResolverFuzz to address
the aforementioned challenges related to DNS resolvers, with a suite of new
techniques being developed. First, ResolverFuzz performs constrained stateful
fuzzing by focusing on the short query-response sequence, which has been
demonstrated as the most effective way to find resolver bugs, based on our
study of the published DNS CVEs. Second, to generate test cases that are more
likely to trigger resolver bugs, we combine probabilistic context-free grammar
(PCFG) based input generation with byte-level mutation for both queries and
responses. Third, we leverage differential testing and clustering to identify
non-crash bugs like cache poisoning bugs. We evaluated ResolverFuzz against 6
mainstream DNS software under 4 resolver modes. Overall, we identify 23
vulnerabilities that can result in cache poisoning, resource consumption, and
crash attacks. After responsible disclosure, 19 of them have been confirmed or
fixed, and 15 CVE numbers have been assigned.
