SCALE: Automatically Finding RFC Compliance Bugs in DNS Nameservers

Authors: 

Siva Kesava Reddy Kakarla, University of California, Los Angeles; Ryan Beckett, Microsoft; Todd Millstein, University of California, Los Angeles, and Intentionet; George Varghese, University of California, Los Angeles

Abstract: 

The Domain Name System (DNS) has intricate features that interact in subtle ways. Bugs in DNS implementations while handling combinations of these features can lead to incorrect or implementation-dependent behavior, security vulnerabilities, and more. We introduce the first approach for finding RFC compliance errors in DNS nameserver implementations via automatic test generation. Our SCALE (Small-scope Constraint-driven Automated Logical Execution) approach jointly generates zone files and corresponding queries to cover RFC behaviors specified by an executable model of DNS resolution. We have built a tool called Ferret based on this approach and applied it to test 8 open-source DNS implementations, including popular implementations such as Bind, PowerDNS, Knot, and Nsd. Ferret generated over 13K test files, of which 62% resulted in some difference among implementations. We identified and reported 30 new unique bugs from these failed test cases, including at least one bug in every implementation, of which 20 have already been fixed. Many of these existed in even the most popular DNS implementations, including a new critical vulnerability in Bind that attackers could easily exploit to crash DNS resolvers and nameservers remotely.

NSDI '22 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {278336,
author = {Siva Kesava Reddy Kakarla and Ryan Beckett and Todd Millstein and George Varghese},
title = {{SCALE}: Automatically Finding {RFC} Compliance Bugs in {DNS} Nameservers},
booktitle = {19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)},
year = {2022},
isbn = {978-1-939133-27-4},
address = {Renton, WA},
pages = {307--323},
url = {https://www.usenix.org/conference/nsdi22/presentation/kakarla},
publisher = {USENIX Association},
month = apr
}

Presentation Video