recursive-dns

DNS resolution starting from the root servers. No resolver, no getaddrinfo, no /etc/resolv.conf — just thirteen IP addresses and the protocol.

Every name lookup your machine makes gets handed to a resolver that does the real work. This is that work. The only thing hard-coded here is the list of root server addresses; everything else — which servers run .com, which run example.com, what the answer is — gets discovered by asking.

$ python -m recursivedns example.com

resolving example.com from the root

  ...  [.]  example.com  ->  delegation
  ...  [com]  example.com  ->  delegation
  ...  [example.com]  example.com  ->  answer
  ...  [example.com]  example.com  ->  ANSWER ...

example.com	300	A	...

That is a real run, so your addresses will differ from mine: a root server is picked at random on every lookup, and example.com sits behind a CDN that answers with whichever address it feels like. What will not differ is the shape — root, then .com, then the authoritative server, and nobody ever told us anything we hadn't asked for. The root doesn't know what example.com is; it only knows who runs .com. Those servers don't know either; they know who runs example.com. Those servers know.

The loop

Ask a server. It answers one of four things:

answer	what you do
here is the record	done
here is a CNAME	start over, with the real name
ask them instead	follow the delegation, one label deeper
that name doesn't exist	NXDOMAIN — an answer, not a failure

That's the whole algorithm. What makes it interesting are the cases where it bites:

Glue records. A delegation says "example.com is run by ns1.example.com". To ask that server anything, you need its address — but its address is inside the zone it serves. You cannot resolve ns1.example.com without asking ns1.example.com. The parent zone breaks the cycle by shipping the address along, unasked, in the additional section. That's glue.

And when there is no glue, you have to stop, resolve that nameserver's name with the same resolver, recursively, and only then continue. That case is what makes a resolver a resolver rather than a loop, and it has its own test.

Name compression. Any name in a DNS message may end, instead of with a zero byte, with a two-byte pointer to a name earlier in the message. So a name can only be read with the entire message in hand — and a malicious message can point a name at itself. A naive parser follows that forever. This one refuses:

def test_compression_pointer_loop_is_refused():
    buf = b"\xc0\x00"          # a name whose pointer points at itself
    with pytest.raises(Malformed, match="loop"):
        decode_name(buf, 0)

Verified without a network

The resolution logic is tested against a recorded delegation chain — real DNS messages, built byte by byte, walked exactly as the live root servers would be walked. No socket is ever opened:

$ python -m pytest -q
18 passed

That covers following a delegation, using the glue, chasing a CNAME, resolving a nameserver that came without glue, NXDOMAIN, delegation loops, and the compression-pointer loop. The network is behind a transport object, so the part with the logic in it is verified deterministically, and the part that touches UDP is the part you can see for yourself:

$ python -m recursivedns google.com
$ python -m recursivedns news.ycombinator.com -t A
$ python -m recursivedns github.com --quiet

(The two live blocks on this page are the only ones a checker is told not to run. They go out to the real root servers, and a README check that depends on the internet being up is a README check that eventually gets ignored. The shape they demonstrate is what 18 passed above is pinning, offline.)

Use it

from recursivedns import Resolver, UDP

r = Resolver(transport=UDP())
for record in r.resolve("example.com"):
    print(record.data)

for step in r.trace:        # every server asked, in order
    print(step.server, step.zone, step.result)

Limits

• UDP only. No TCP fallback, so a reply that sets the truncated bit is not retried over TCP. Large NS sets will hit this.
• No DNSSEC. Nothing here is validated; a lying server is believed.
• No cache. Every lookup walks from the root again. A real resolver caches the delegations, which is most of what makes it fast.
• A, AAAA and NS only. No MX, TXT, SRV.

Install

$ git clone https://github.com/Wasserpuncher/recursive-dns
$ cd recursive-dns
$ python -m recursivedns example.com

Python 3.10+, no dependencies.

License

MIT