How Complex is DNS?
Authors: 
Siva Kesava Reddy Kakarla, Ryan Beckett, 
Todd Millstein, George VargheseAuthors Info & Claims
Pages 116 - 122
Abstract
Motivated by recent results that show that Internet protocols can be surprisingly complex and, in particular, that BGP is Turing complete, we ask the same question for the Domain Name System (DNS). DNS is at least as pervasive and essential as BGP in the global Internet infrastructure. Besides the scientific interest, the complexity of DNS can have implications for new applications (that can utilize the unsuspected power of DNS), and for verification (to understand basic complexity limits and suggest new verification algorithms). In this paper, we show that using the power of DNAME record type, DNS can express regular languages and pushdown systems. The first result can be used to build a system for controlling domain access (of which parental control is a special case). The second result shows that verification of DNS zone files is likely to take time that is at least cubic in the number of records.
References
[1]
Ahmed Bouajjani, Javier Esparza, and Oded Maler. 1997. Reachability analysis of pushdown automata: Application to model-checking. In CONCUR '97: Concurrency Theory, Antoni Mazurkiewicz and Józef Winkowski (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 135--150.
[2]
Thomas P. Brisco. 1995. DNS Support for Load Balancing. RFC 1794. (1 April 1995). https://doi.org/10.17487/RFC1794
[3]
Olaf Burkart and Bernhard Steffen. 1995. Composition, decomposition and model checking of pushdown processes. Nordic Journal of Computing 2, 2 (1995), 89--125.
[4]
Krishnendu Chatterjee, Bhavya Choudhary, and Andreas Pavlogiannis. 2017. Optimal Dyck reachability for data-dependence and alias analysis. Proceedings of the ACM on Programming Languages 2, POPL (2017), 1--30.
[5]
Krishnendu Chatterjee and Georg Osang. 2017. Pushdown reachability with constant treewidth. Inform. Process. Lett. 122 (2017), 25--29.
[6]
Swarat Chaudhuri. 2008. Subcubic Algorithms for Recursive State Machines. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '08). Association for Computing Machinery, New York, NY, USA, 159--169. https://doi.org/10.1145/1328438.1328460
[7]
Stuart Cheshire and Marc Krochmal. 2013. DNS-Based Service Discovery. RFC 6763. (Feb. 2013). https://doi.org/10.17487/RFC6763
[8]
Marco Chiesa, Luca Cittadini, Giuseppe Di Battista, Laurent Vanbever, and Stefano Vissicchio. 2013. Using routers to build logic circuits: How powerful is BGP?. In 2013 21st IEEE International Conference on Network Protocols (ICNP). IEEE, 1--10.
[9]
Internet Systems Consortium. 2021. BIND 9. (2021). https://www.isc.org/bind/
[10]
DNS Response Policy Zones 2019. (2019). Retrieved June 2020 from https://dnsrpz.info/
[11]
DNSBL information - spam database and blacklist check. 2020. (2020). https://www.dnsbl.info/
[12]
Javier Esparza, David Hansel, Peter Rossmanith, and Stefan Schwoon. 2000. Efficient algorithms for model checking pushdown systems. In International Conference on Computer Aided Verification. Springer, 232--247.
[13]
Timothy G Griffin, F Bruce Shepherd, and Gordon Wilfong. 2002. The stable paths problem and interdomain routing. IEEE/ACM Transactions On Networking 10, 2 (2002), 232--243.
[14]
Nevin Heintze and David McAllester. 1997. On the cubic bottleneck in subtyping and flow analysis. In Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science. IEEE, 342--351.
[15]
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA.
[16]
Internet Initiative Japan Inc. 2019. IP Location Load Balancing Resource Record. Internet-Draft draft-sonoda-dnsop-lb-01. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-sonoda-dnsop-lb-01 Work in Progress.
[17]
Siva Kesava Reddy Kakarla, Ryan Beckett, Behnaz Arzani, Todd Millstein, and George Varghese. 2020. GRoot: Proactive Verification of DNS Configurations. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '20). Association for Computing Machinery, New York, NY, USA, 310--328. https://doi.org/10.1145/3387514.3405871
[18]
Scott Kitterman. 2014. Sender Policy Framework (SPF) for Authorizing Use of Domains in Email, Version 1. RFC 7208. (April 2014). https://doi.org/10.17487/RFC7208
[19]
Murray Kucherawy, Dave Crocker, and Tony Hansen. 2011. DomainKeys Identified Mail (DKIM) Signatures. RFC 6376. (Sept. 2011). https://doi.org/10.17487/RFC6376
[20]
NLnet Labs. 2021. NSD. (2021). https://nlnetlabs.nl/projects/nsd/about/
[21]
Michael H. Mealling. 2002. Dynamic Delegation Discovery System (DDDS) Part Three: The Domain Name System (DNS) Database. RFC 3403. (Oct. 2002). https://doi.org/10.17487/RFC3403
[22]
P. Mockapetris. 1987. Domain names - concepts and facilities. RFC 1034. (Nov. 1987). https://doi.org/10.17487/RFC1034
[23]
P. Mockapetris. 1987. Domain names - implementation and specification. RFC 1035. (Nov. 1987). https://doi.org/10.17487/RFC1035
[24]
Yakov Rekhter, Susan Hares, and Tony Li. 2006. A Border Gateway Protocol 4 (BGP-4). RFC 4271. (Jan. 2006). https://doi.org/10.17487/RFC4271
[25]
Thomas Reps, Akash Lal, and Nick Kidd. 2007. Program Analysis Using Weighted Pushdown Systems. In FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, V. Arvind and Sanjiva Prasad (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 23--51.
[26]
Thomas Reps, Stefan Schwoon, Somesh Jha, and David Melski. 2005. Weighted pushdown systems and their application to interprocedural dataflow analysis. Science of Computer Programming 58, 1-2 (2005), 206--263.
[27]
Scott Rose and Wouter Wijngaards. 2012. DNAME Redirection in the DNS. RFC 6672. (June 2012). https://doi.org/10.17487/RFC6672
[28]
Stefan Schwoon. 2002. Model-checking pushdown systems. Ph.D. Dissertation. Technische Universität München.
[29]
Ken Thompson. 1968. Programming Techniques: Regular Expression Search Algorithm. Commun. ACM 11, 6 (June 1968), 419--422. https://doi.org/10.1145/363347.363387
[30]
Paul A. Vixie and Vernon Schryver. 2018. DNS Response Policy Zones (RPZ). Internet-Draft draft-vixie-dnsop-dns-rpz-00. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-vixie-dnsop-dns-rpz-00 Work in Progress.
Recommendations
Securing DNS: Extending DNS Servers with a DNSSEC Validator
DNS Security Extensions (DNSSEC) is a proposed standard for securely authenticating information in the Domain Name System. DNSSEC validators check the digital signatures on DNS data. However, designing a validator worth the operational costs is a ...
Practical Challenge-Response for DNS
ANRW '18: Proceedings of the 2018 Applied Networking Research WorkshopAuthoritative DNS nameservers are vulnerable to being used in denial of service attacks whereby an attacker sends DNS queries while masquerading as a victim---hence coaxing the DNS server to send the responses to the victim. Reflecting off innocent DNS ...
Practical challenge-response for DNS
Authoritative DNS servers are susceptible to being leveraged in denial of service attacks in which the attacker sends DNS queries while masquerading as a victim---and hence causing the DNS server to send the responses to the victim. This reflection off ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2021
246 pages
ISBN:9781450390873
DOI:10.1145/3484266
Copyright © 2021 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 November 2021
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
HotNets '21
Sponsor:
HotNets '21: The 20th ACM Workshop on Hot Topics in Networks
November 10 - 12, 2021
Virtual Event, United Kingdom
Acceptance Rates
Overall Acceptance Rate 110 of 460 submissions, 24%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 627Total Downloads
- Downloads (Last 12 months)146
- Downloads (Last 6 weeks)17
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in