Resolve the Unresolved: Systematic Work Profiling for DNS Resolvers

The DNS standards mandate that recursive resolvers should bound the amount of work they perform per query. Yet, for nearly four decades, the specifications have offered little concrete guidance on how to enforce such limits, largely because of the system's daunting and growing complexity. This ambiguity has led to divergent implementations, recurring performance bugs, and above all, constant discoveries of denial-of-service (DoS) vectors. Prior research has inspected only fragments of a resolver's behavior, mostly using informal methods, while existing mitigations hinge on heuristic thresholds that lack broadly accepted guidance. As a result, both the issues uncovered and the fixes deployed remain narrow in scope. We address this gap by modeling recursive resolution as an Extended Transition System (ETS) with cost annotations and formulating the computation of maximum per-query work as a constrained longest path search problem with provable guarantees. Building on this formalism, we introduce rProfiler, a systematic profiling framework for measuring and modeling the work performed by DNS resolvers. Applying rProfiler against widely used resolvers exposes severe DoS vectors: issuing only 30 work-intensive queries per second cuts these resolvers' performance by at least 67%-and in some cases, renders them completely unresponsive. Diagnosing resolvers with rProfiler also yields actionable insights to improve their robustness against DoS attacks and subtle performance bugs.