dnsd was written as an assignment for the following class:
CS328 - TCP/IP Networks
UBC-Okanagan, with Dr. Ramon Lawrence
By Doug Hoyte, April, 2007
dnsd is a small and simple yet cutting-edge and powerful DNS server written in the nuff programming language. Since the nuff layer system makes the parsing and creation of DNS packets trivial, dnsd is free to focus on implementing sophisticated asynchronous DNS server logic. dnsd's goals are simplicity and security, so we have elected to not support certain features offered by BIND or required in the RFCs. dnsd is not a replacement for BIND mostly due to its lack of secondary server support.
dnsd is meant for individuals needing a flexible, light-weight DNS cache or a simple, safe authoritative DNS server. dnsd is also designed as a forwarding DNS cache that can transparently "poison" certain DNS records with custom values.
dnsd is compact and easy to audit (around 200 lines of code) but still packed with features. Thanks to the nuff programming environment, we can use powerful, high-level abstractions close to the lowest-level unix network APIs. Although dnsd currently only supports UDP through unix DGRAM sockets, enabling dnsd to work over some other nuff transport mode (TCP sockets or raw IP or raw ethernet sockets or ...) would be simple.
dnsd listens on UDP port 53 (by default) through your unix system's DGRAM UDP sockets. It requires root privileges to listen to ports below 1025 but not otherwise. You can specify the port to listen on with the -port switch.
Since dnsd is designed to be simple it does as little as possible by default. You need to specify one or more modes for it to operate in. To do that, use any combination of the following switches when you launch dnsd from the unix command line:
-forward : This switch turns on simple DNS forwarding. dnsd will act as a caching DNS forwarder, forwarding requests to 1 or more recursion-enabled DNS resolvers specified in /etc/resolv.conf . For example:
# nuff dnsd -forward
will run a forwarding DNS server on port 53.
IMPORTANT NOTE: When you enable -forward on dnsd (and actually any caching name server) you are allowing anyone who queries it to learn information about which records have been cached, and when. This is a property of a cache and you should be aware of its security/privacy implications.
With that in mind, dnsd is designed to make this so called "cache peeking" more difficult to exploit than is so for other DNS implementations. Because dnsd doesn't service non-recursive queries outside zones it is handling, peeking at information in dnsd's cache requires timing based attacks.
-zone <dnsd-zone-file> : This switch turns dnsd into an authoritative DNS server for a collection of records given in some file. Nuff includes an example zone file in NUFFDIR/docs/example-dnsd-zone . You can start an authoritative server like so:
# nuff dnsd -zone docs/example-dnsd-zone
The format of the zone file is simple. It is a file with s-expressions giving mappings from DNS names to records. It is best explained through an example file:
; Comments? No problem!
("loop.hcsw.org" A "127.0.0.1" 10 s)
("220.127.116.11" PTR "lol.com" .5 h)
("blah.com" NS "ns1.blah.com" 1 d)
The fields are a string representing the source domain name (or in special cases like PTR records, an IP address), the type of record (such as A PTR NS CNAME etc), the resulting domain name (or in special cases like A records, an IP address), then the TTL as a TTL specification.
The TTL specification, along with many other nuff macros, uses a value/unit combination to specify the TTL. You specify a number (defined by scheme's number? predicate) and one of the following symbols: s, m, h, d. These stand for seconds, minutes, hours, and days, respectively.
With only the -zone switch, dnsd will give out no information from its internal resolver cache. Although you can enable both -zone and -forward, you should keep in mind the same security/privacy cautions as with -forward.
dnsd does not support zone transfers.
-predict : This switch implies -forward. It will not only enable DNS forwarding, but also an innovative performance-enhancing pre-fetching algorithm that provides a slight edge over conventional DNS resolvers. This prediction algorithm is described in the next section.
# nuff dnsd -predict
Have you ever watched the bottom of your web browser, perhaps during slow network conditions, and seen the status momentarily stalled at "Looking up ..."? That is your web browser's way of telling you it is waiting for the results of some DNS query. Often complex web pages will get stalled on several DNS queries when parsing and processing the content. Images or css files in a separate domain, redirects, and many more web features can cause additional DNS queries to be issued. When certain DNS requests can't be issued until the results of another DNS request are delivered, we call this a "DNS dependency tree".
The most innovative feature dnsd provides is an experimental pre-fetching algorithm created by Doug Hoyte and HCSW Labs. To my knowledge, this is the first implementation of our algorithm. The technique uses information gathered from previously observed DNS resolution patterns to guess, in advance, which DNS requests are likely to be issued, and then starts them up "in the background" so they are ready sooner when/if actually needed.
DNS prediction has a fairly limited scope in what it tries to predict. It doesn't try to get inside your head and guess when you are going to check your email, for instance. The algorithm does about all an algorithm can do: it sticks with predicting the behaviour of mere programs and processes.
DNS is rarely ever the bottleneck when surfing the web, of course, but as more and more layers of technology get added to the internet, reducing these round-trip times in aggregate can add up to a suprising improvement in performance. Here is a fairly common DNS dependency tree (note that smart DNS/HTML configurations can reduce or eliminate many of these dependencies):
To try to reduce the total waiting time required when processing these DNS dependency trees, dnsd uses an innovative pre-fetching algorithm.
The algorithm uses an "infinitley growing" list of DNS requests. It maintains a pointer to the end of the list and adds every DNS request it services to the end of the list. When it services a request, it starts up an "open window" which is a continuation scheduled to run at some point in the future (specified with the dnsd -predict-window option). Each continuation keeps a pointer to the last request that was issued when the window started. When the continuation runs, it is simply a matter of following the list to the end and determining if any of the subsequent queries are (or should be) a part of the prediction window.
Here is a graphical depiction of the algorithm:
The algorithm also involves maintaining a few hash-tables of possible prediction windows. Any record/type pair can contain a list of "dependencies" each with their own positive score value. Every time we see this dependency during our open window, we add 1 to its score. Every time our window expires without us seeing it, we subtract 1 from its score. Dependencies with a score of 0 are removed. DNS dependencies are only pre-fetched when their score is 2 or higher. Since we have to observe the dependency two separate times, unrelated queries are prevented from becoming associated with DNS dependencies. Because we subtract 1 from their score if we don't see them in later windows, even if they are they won't stay associated for long.
How does DNS caching relate to prediction?
DNS caching assigns a "Time To Live" value to all records. This tells us the latest point in time to consider this record valid. When that time expires, we (or likely our ISP's DNS server) will have to perform another request which will need (at least) a round-trip to the authoritative nameserver for the record. Caching is a brilliant and invaluable component of DNS that enables a DNS admin to control the frequencies of these round-trips.
Our prediction algorithm keeps and uses data regarding queries longer than the TTL expiry time but still never treats a record as valid past its particular TTL expiry time.
In other words, prediction does not change the meaning or behaviour of DNS caching at all. In all forwarding and prediction replies, dnsd is also a regular DNS cache implementation.
Here is a partial list of dnsd's miscellaneous features:
dnsd is asynchronous : nuff provides a powerful asynchronous system that simulates an input/output-oriented multiprogramming environment. We can pretend we are programming with concurrent "threads" when we like but otherwise we are a single deterministic process. See the continuations section of "nuff doc language" for details. The async macro is the most relevant use of nuff's multi-programming in dnsd. We use it to pretend that every client request is handled by a running "thread" and to schedule window expiries as we saw in the description of the prediction algorithm.
This means that any and all operations in dnsd happen in parallel. Even following chains of CNAME resolutions will not interfere with other resolutions.
-daemon : This switch runs dnsd as a background process, in a separate SID from your shell. Like all nuff programs, the daemon is run with "nobody" privileges in a tightly restricted environment. All random values are generated using your operating system's cryptographically secure pseudo-random number generator. See "nuff doc security" for details.
-nameservers : This switch will be used to override the default nuff resolver IPs taken from /etc/resolv.conf. This will affect which servers to use when using -forward/-predict. You can specify as many nameservers as you like. Client requests will be distributed randomly between all of them. Here is an example use:
# nuff dnsd -predict -nameservers '(("18.104.22.168" 53) ("22.214.171.124" 9876))'
-delay <delay-value> : This switch will add an artificial delay to every query it forwards or serves from a zone. It is useful for detecting DNS dependencies by simulating larger round-trip-time (RTT) delays.
For testing purposes, we used the nuff command dnssequence (see the nuff manual pages) to simulate and time the resolution of DNS dependency trees. We resolve these DNS dependency trees 5 times for each resolver and record the total elapsed time for each resolution.
We used special DNS records with a TTL of 0 so DNS caching didn't factor in (NS records were always cached). All comparisons were done sending the queries to a copy of BIND (the standard DNS server on the internet) versus a dnsd instance running on the same system. The dnsd instance was configured to forward its requests to that same local copy of BIND.
We used a 56k dial-up modem for our internet connection because of its consistent and large round-trip times and also because its bandwidth is easy to overwhelm. All runs are the averaged results of 3 identical runs.
Sequence #1 is designed as a straight-forward test to verify that our prediction actually produces a measurable improvement in DNS resolution time. The first node, seq, is a place-holder node that represents the root of the tree and the start of the sequence. Sequence #1 is a tree of depth 3, which means that we can't resolve t2 until we have the results for t1 and similarly we can't resolve t3 until we have the results for t2.
(seq ("t1" ("t2" ("t3"))))
We see that although conventional DNS resolvers (like BIND and dnsd with only -forward enabled) maintain roughly constant response times, dnsd in -predict mode discovers a relationship between the nodes after seeing 2 previous examples. Further resolutions use the prediction algorithm described above and start resolutions in parallel so we have a shorter aggregate DNS resolution time.
Sequence #2 is an illustration of the type of dependencies that -predict DOESN'T help with. In this example, all 3 DNS resolutions are required at once so they are done in parallel with or without prediction.
(seq ("t1") ("t2") ("t3"))
BIND is always faster than dnsd for this sequence. Most of this dnsd overhead is because, of course, BIND is a well tuned, tried-and-tested, native code DNS implementation. Since in these tests nuff forwards the requests to the same BIND instance, part of the overhead is also due to dnsd having to perform one extra step of resolution.
In any case, the results are impressive considering dnsd is written for nuff - a high-level, interpreted scheme environment. The careful design of nuff allows us to program with high-level abstractions close to low-level unix networking APIs. These timing results give us further reason to believe that if nuff is slightly tuned and ported to a native code scheme compiler then its performance could likely compete against, or possibly even improve upon, some C network programs. See "nuff doc language" for details on nuff's many performance features that make this possible.
Sequence #3 shows that although we can get performance improvements through prediction with more complex tree structures we start saturating our bandwidth (dial-up after all) and reducing the pipeline effect. See the mapasync section in "nuff doc language" for details.
(seq ("t1" ("t2" ("t3"))) ("t4" ("t5" ("t6"))) ("t7" ("t8" ("t9"))))
Sequence #4 is a DNS dependency tree of depth 6, just like our http://cbc.ca example in the DNS prediction section.
(seq ("t1" ("t2" ("t3" ("t4" ("t5" ("t6")))))))
Here the effect is very pronounced. This is evidence that DNS prediction can cut the aggregate DNS resolution times in half versus conventional resolvers. This example also puts the dnsd processing overhead into perspective: smarter algorithms are often the most effective technique for improving performance.
dnsd is simple. In most of its modes, it doesn't require any configuration files at all. When it does, it uses a convenient s-expression based syntax. The format for specifying records in the zone-file isn't quite as powerful as the normal BIND zone file format but is an efficient and intuitive interface for specifying zones.
A future possible enhancement to dnsd would be to allow the records in the zone file to be lambda forms for evaluation at run-time. This could be useful for special DNS proxying, data-base integration, future "nuff dhcpd" integration, extra-smart load balancing, and more.
dnsd is secure. Nuff's abstractions tend to always pressure us to write simple and restrictive code. Even though nuff is very new and doesn't have a lengthy production record behind it we can feel fairly confident using dnsd in security-sensitive environments. dnsd does not perfectly emulate BIND or follow the RFCs in several places where security was felt to be a concern.
The nuff team is constantly researching ways to make nuff scripts more secure. Eventually, dnsd will be run in a chroot environment which means dnsd will not be able to access the majority of your filesystem. See "nuff doc security" for details.
dnsd can also be used as a convenient, transparent way of rewriting DNS queries or even as an active malicious security tool. When dnsd is run in both -forward and -zone mode, all requests will be forwarded as usual except those in the supplied zone-file where the custom record will be served. This opens up all sorts of possibilities for DNS rewriting/injection.
dnsd is smart. The nuff environment allows us to focus our attention on high-level algorithms and concepts with minimal low-level hacking yet still encourages an efficient, secure style of programming. Nuff allows us to spend more time researching and less time developing.
A planned future improvement is to make dnsd capable of accepting DNS queries through a pcap descriptor. Since nuff already has a framework for this it won't be a major undertaking. We can imagine being able to gain the performance benefits from DNS prediction without having to reconfigure any resolvers simply by populating a nameserver's cache before the requester even knows it wants the record!
All material is © Doug Hoyte and/or HCSW Labs unless otherwise noted or implied.