Building the recursive resolver

Building the recursive resolver

Blog-7 of the 10 Blog series

We have already explored the outline of our UDP server, now time comes to actually build the resolver which will resolve DNS queries.

f you don't have the codebase yet:github.com/rtpa25/dns-server

For this before jumping into code, let's understand how the recursive resolution actually works

  1. Assuming that no information is known since before, the question is first issued to one of the Internet's 13 root servers.

    1. Why 13? Because that's how many that fits into a 512 byte DNS packet.

    2. You might think that 13 seems a bit on the low side for handling all of the internet, and you'd be right -- there are 13 logical servers, but in reality many more. You can read more about it here.

    3. Any resolver will need to know of these 13 servers before hand. A file containing all of them, in bind format, is available and called named.root. These servers all contain the same information, and to get started we can pick one of them at random.

      Below are all 13 root servers (src/root-name-server.ts)

       export const rootNameServers = [
           {
               ns: 'A.ROOT-SERVERS.NET',
               ipv4: '198.41.0.4',
               ipv6: '2001:503:ba3e::2:30',
               ttl: 36_00_000,
           },
           {
               ns: 'B.ROOT-SERVERS.NET',
               ipv4: '170.247.170.2',
               ipv6: '2801:1b8:10::b',
               ttl: 36_00_000,
           },
           {
               ns: 'C.ROOT-SERVERS.NET',
               ipv4: '192.33.4.12',
               ipv6: '2001:500:2::c',
               ttl: 36_00_000,
           },
           {
               ns: 'D.ROOT-SERVERS.NET',
               ipv4: '199.7.91.13',
               ipv6: '2001:500:2d::d',
               ttl: 36_00_000,
           },
           {
               ns: 'E.ROOT-SERVERS.NET',
               ipv4: '192.203.230.10',
               ipv6: '2001:500:a8::e',
               ttl: 36_00_000,
           },
           {
               ns: 'F.ROOT-SERVERS.NET',
               ipv4: '192.5.5.241',
               ipv6: '2001:500:2f::f',
               ttl: 36_00_000,
           },
           {
               ns: 'G.ROOT-SERVERS.NET',
               ipv4: '192.112.36.4',
               ipv6: '2001:500:12::d0d',
               ttl: 36_00_000,
           },
           {
               ns: 'H.ROOT-SERVERS.NET',
               ipv4: '198.97.190.53',
               ipv6: '2001:500:1::53',
               ttl: 36_00_000,
           },
           {
               ns: 'I.ROOT-SERVERS.NET',
               ipv4: '192.36.148.17',
               ipv6: '2001:7fe::53',
               ttl: 36_00_000,
           },
           {
               ns: 'J.ROOT-SERVERS.NET',
               ipv4: '192.58.128.30',
               ipv6: '2001:503:c27::2:30',
               ttl: 36_00_000,
           },
           {
               ns: 'K.ROOT-SERVERS.NET',
               ipv4: '193.0.14.129',
               ipv6: '2001:7fd::1',
               ttl: 36_00_000,
           },
           {
               ns: 'L.ROOT-SERVERS.NET',
               ipv4: '199.7.83.42',
               ipv6: '2001:500:9f::42',
               ttl: 36_00_000,
           },
           {
               ns: 'M.ROOT-SERVERS.NET',
               ipv4: '202.12.27.33',
               ipv6: '2001:dc3::35',
               ttl: 36_00_000,
           },
       ];
      
  2. Once we have a random name server our first query will lead us to one of the many TLD server's for the that top level domain ex: .com, .dev etc

    1. They are present in the authority section of the response

       com.            172800    IN    NS    e.gtld-servers.net.
       com.            172800    IN    NS    b.gtld-servers.net.
       com.            172800    IN    NS    j.gtld-servers.net.
       com.            172800    IN    NS    m.gtld-servers.net.
       com.            172800    IN    NS    i.gtld-servers.net.
       com.            172800    IN    NS    f.gtld-servers.net.
       com.            172800    IN    NS    a.gtld-servers.net.
       com.            172800    IN    NS    g.gtld-servers.net.
       com.            172800    IN    NS    h.gtld-servers.net.
       com.            172800    IN    NS    l.gtld-servers.net.
       com.            172800    IN    NS    k.gtld-servers.net.
       com.            172800    IN    NS    c.gtld-servers.net.
       com.            172800    IN    NS    d.gtld-servers.net.
      
    2. Now we also get an additional sections which are ip addresses of each of these domains (e.gtld-servers.net is just another domain, which the computer can not make any sense of)

       e.gtld-servers.net.    172800    IN    A    192.12.94.30
       b.gtld-servers.net.    172800    IN    A    192.33.14.30
       b.gtld-servers.net.    172800    IN    AAAA    2001:503:231d::2:30
       j.gtld-servers.net.    172800    IN    A    192.48.79.30
       m.gtld-servers.net.    172800    IN    A    192.55.83.30
       i.gtld-servers.net.    172800    IN    A    192.43.172.30
       f.gtld-servers.net.    172800    IN    A    192.35.51.30
       a.gtld-servers.net.    172800    IN    A    192.5.6.30
       a.gtld-servers.net.    172800    IN    AAAA    2001:503:a83e::2:30
       g.gtld-servers.net.    172800    IN    A    192.42.93.30
       h.gtld-servers.net.    172800    IN    A    192.54.112.30
       l.gtld-servers.net.    172800    IN    A    192.41.162.30
       k.gtld-servers.net.    172800    IN    A    192.52.178.30
       c.gtld-servers.net.    172800    IN    A    192.26.92.30
       d.gtld-servers.net.    172800    IN    A    192.31.80.30
      
    3. Not all responses are this nice where we get additional section with ip's of all ns records inside authority section. So to resolve them we will have to make subsequent recursive queries (Which we will see in code in some time)

  3. Picking one of the random ip's in the additional section we simply query with our original question again, this time we get a set of servers that handle the google.com domain now.

    1. These are basically the name servers you configure to your domain for google.com below are the name servers

       ;; AUTHORITY SECTION:
       google.com.        172800    IN    NS    ns2.google.com.
       google.com.        172800    IN    NS    ns1.google.com.
       google.com.        172800    IN    NS    ns3.google.com.
       google.com.        172800    IN    NS    ns4.google.com.
      
       ;; ADDITIONAL SECTION:
       ns2.google.com.        172800    IN    A    216.239.34.10
       ns1.google.com.        172800    IN    A    216.239.32.10
       ns3.google.com.        172800    IN    A    216.239.36.10
       ns4.google.com.        172800    IN    A    216.239.38.10
      
  4. Again we pick one random record from the additional section to query for google.com and finally we get our answer

     ;; QUESTION SECTION:
     ;www.google.com.            IN  A
    
     ;; ANSWER SECTION:
     www.google.com.     300 IN  A   216.58.211.132
    

    This time the actual IP inside the answer section!!

Let's recap:

This is rather typical, and most lookups will only require three steps, even without caching. It's still possible to have name servers for subdomains and further ones for sub-subdomains. In practice, a DNS server will maintain a cache, and most TLDs will already be known. This means that most queries will only need two lookups by the server, and often just one or none.

Now that we have a detailed understanding of the function let's translate it into code

navigate along to src/recursive-resolver.ts

import { forwardResolver } from './forward-resolver';
import { DNSBuilder } from './message/builder';
import {
    DNSAnswer,
    DNSHeader,
    DNSObject,
    DNSQuestion,
    QRIndicator,
    RCode,
    RECORD_TYPE,
} from './message/types';
import { rootNameServers } from './root-name-server';
import { decodeRDATA, getRandomEntry, isValidDomain } from './utils';

export async function recursiveLookup(
    question: DNSQuestion,
    header: DNSHeader,
) {
    try {
        let rootNameServerIP = getRandomEntry(rootNameServers).ipv4;
        const resolverPort = 53;

        while (true) {
            let rootnameServerIPCopy = rootNameServerIP;

            const requestObject: DNSObject = {
                header,
                questions: [question],
            };
            const requestBuffer = new DNSBuilder(requestObject).toBuffer();
            let dnsResponse = await forwardResolver(
                requestBuffer,
                rootnameServerIPCopy,
                resolverPort,
            );

            // throw error if response is not received
            if (!dnsResponse) {
                throw new Error('No response received');
            }

            // id response is giving an error of NXDOMAIN then return the response
            if (dnsResponse.header.RCODE === RCode.NXDOMAIN) {
                return dnsResponse;
            }

            // if find answer return and end loop
            if (dnsResponse.answers && dnsResponse.answers.length > 0) {
                const answers = dnsResponse.answers;
                const cnameAnswers = answers.filter(
                    (answer) => answer.TYPE === RECORD_TYPE.CNAME,
                );
                // if cname record is present then we have to resolve the cname record to get the ip
                // unless user has asked for cname record explicitly
                if (cnameAnswers.length > 0 && question.TYPE !== RECORD_TYPE.CNAME) {
                    for (const cnameAnswer of cnameAnswers) {
                        const cnameQuestion: DNSQuestion = {
                            NAME: decodeRDATA(cnameAnswer.RDATA),
                            TYPE: RECORD_TYPE.A,
                            CLASS: 1,
                        };
                        const res = await recursiveLookup(cnameQuestion, header);
                        if (res.answers) answers.push(...res.answers);
                    }
                }
                const finalResponse: DNSObject = {
                    header: {
                        ...dnsResponse.header,
                        ANCOUNT: answers.length,
                    },
                    answers,
                    questions: [question],
                };

                return finalResponse;
            }

            // if find additional use those ip and continue the loop in hope that you will get the answer
            if (dnsResponse.additional && dnsResponse.additional.length > 0) {
                const additionalWithIPv4 = dnsResponse.additional.filter((record) => {
                    if (record.RDLENGTH === 4) {
                        return record;
                    }
                });
                const randomAdditional = getRandomEntry(additionalWithIPv4);
                rootNameServerIP = randomAdditional.RDATA.join('.');
                continue;
            }

            // if authority is present while additional is not present simply means, now we have to perform another lookup to get the additional records or basically ip of these authority servers to proceed with the original query
            let validAuthorityRecord: DNSAnswer | undefined;
            if (
                dnsResponse.authority &&
                dnsResponse.authority.length > 0 &&
                (!dnsResponse.additional || dnsResponse.additional.length === 0)
            ) {
                const validAuthorityRecords = dnsResponse.authority
                    .map((authorityRecord) => {
                        return {
                            ...authorityRecord,
                            NAME: decodeRDATA(authorityRecord.RDATA),
                        };
                    })
                    .filter((authorityRecord) => {
                        if (isValidDomain(authorityRecord.NAME)) {
                            return authorityRecord;
                        }
                    });
                validAuthorityRecord = getRandomEntry(validAuthorityRecords);

                // if validAuthorityRecord is a SOA record then return the response with SOA record
                if (validAuthorityRecord.TYPE === RECORD_TYPE.SOA) {
                    return {
                        header: {
                            ...header,
                            QR: QRIndicator.RESPONSE,
                            RCODE: RCode.NXDOMAIN,
                            NSCOUNT: dnsResponse.authority ? dnsResponse.authority.length : 0,
                        },
                        questions: [question],
                        authority: dnsResponse.authority || [],
                        answers: [],
                    } as DNSObject;
                }
            }

            if (validAuthorityRecord) {
                const res = await recursiveLookup(
                    {
                        NAME: validAuthorityRecord.NAME,
                        TYPE: RECORD_TYPE.A,
                        CLASS: validAuthorityRecord.CLASS,
                    },
                    header,
                );

                if (res.answers) {
                    const randomResponse = getRandomEntry(res.answers);
                    rootNameServerIP = randomResponse.RDATA.join('.');
                    continue;
                }
            }

            // If no valid authority record or additional records found, return NXDOMAIN with SOA if possible
            return {
                header: {
                    ...header,
                    QR: QRIndicator.RESPONSE,
                    RCODE: RCode.NXDOMAIN,
                    NSCOUNT: dnsResponse.authority ? dnsResponse.authority.length : 0,
                },
                questions: [question],
                authority: dnsResponse.authority || [],
                answers: [],
            } as DNSObject;
        }
    } catch (error) {
        console.error('Error in recursiveLookup:', error);
        return {
            header: {
                ...header,
                QR: QRIndicator.RESPONSE,
                RCODE: RCode.NXDOMAIN,
            },
            questions: [question],
            authority: [],
            answers: [],
        } as DNSObject;
    }
}

Let's go line by line to understand what is happening.

  1. Defining the Recursive Lookup Function:

    • Define the recursiveLookup function that takes a DNS question and header as input.

        export async function recursiveLookup(
            question: DNSQuestion,
            header: DNSHeader,
        ) {
      
  2. Initial Setup:

    • Select a random root name server IP from the predefined list(src/root-name-server.ts).

    • Define the resolver port.

        let rootNameServerIP = getRandomEntry(rootNameServers).ipv4;
        const resolverPort = 53;
      
  3. Main Loop for Recursive Lookup:

    • Start an infinite loop to handle the recursive lookup process.

        while (true) {
            let rootnameServerIPCopy = rootNameServerIP;
      
  4. Building and Sending the DNS Request:

    • Construct a DNS request object and convert it to a buffer with our builder class we build a few blogs ago.

    • Use forwardResolver to send the request to the root name server and await the response.

        const requestObject: DNSObject = {
            header,
            questions: [question],
        };
        const requestBuffer = new DNSBuilder(requestObject).toBuffer();
        let dnsResponse = await forwardResolver(
            requestBuffer,
            rootnameServerIPCopy,
            resolverPort,
        );
      

      forward resolver is a helper function that sends the request buffer to the given host and port over UDP (src/forward-resolver.ts)

        import * as dgram from 'node:dgram';
        import { dnsParser } from './message/parser';
        import { DNSObject } from './message/types';
      
        export async function forwardResolver(
            request: Buffer,
            host: string,
            port: number,
        ) {
            const answer = await new Promise<DNSObject>((resolve, reject) => {
                const socket = dgram.createSocket('udp4');
      
                socket.on('message', (data, _rinfo) => {
                    try {
                        const message = dnsParser.parse(data);
                        socket.close();
                        resolve(message);
                    } catch (error) {
                        console.error('Error in forwardResolver:', error);
                        reject(error);
                    }
                });
      
                socket.on('error', (err) => {
                    socket.close();
                    reject(err);
                });
      
                socket.send(request, port, host);
            });
      
            return answer;
        }
      
  5. Handling No Response:

    • Throw an error if no response is received.

        if (!dnsResponse) {
            throw new Error('No response received');
        }
      
  6. Handling NXDOMAIN Response:

    • Return the response if the RCODE indicates NXDOMAIN (non-existent domain).

        if (dnsResponse.header.RCODE === RCode.NXDOMAIN) {
            return dnsResponse;
        }
      
  7. Processing Answers:

    • This is an important bit and is the base case of the recursion as you saw in the above fundamental discussion in the last step we resolved with a set of answers
  • So now we check if the response contains answers.

  • We filter out the cname answers, and if the requested type is not CNAME, we do another level of recursion now with the cname question to eventually get the underlying A record

  • Finally compiling all answers in order we create a dnsObject and return as our final response

      if (dnsResponse.answers && dnsResponse.answers.length > 0) {
          const answers = dnsResponse.answers;
          const cnameAnswers = answers.filter(
              (answer) => answer.TYPE === RECORD_TYPE.CNAME,
          );
          if (cnameAnswers.length > 0 && question.TYPE !== RECORD_TYPE.CNAME) {
              for (const cnameAnswer of cnameAnswers) {
                  const cnameQuestion: DNSQuestion = {
                      NAME: decodeRDATA(cnameAnswer.RDATA),
                      TYPE: RECORD_TYPE.A,
                      CLASS: 1,
                  };
                  const res = await recursiveLookup(cnameQuestion, header);
                  if (res.answers) answers.push(...res.answers);
              }
          }
          const finalResponse: DNSObject = {
              header: {
                  ...dnsResponse.header,
                  ANCOUNT: answers.length,
              },
              answers,
              questions: [question],
          };
    
          return finalResponse;
      }
    
  1. Handling Additional Records:

    • But as we read above answers are attained at the end of the resolution, before which we check if we have gotten any additional records

    • If we do it's matter of choosing one random entry, because all the entires resolve same data as we know from long before

    • Finally changing the rootNameServerIP to the new ip of the additional record, and continuing the while loop to keep resolving for the same question but with different IP

        if (dnsResponse.additional && dnsResponse.additional.length > 0) {
            const additionalWithIPv4 = dnsResponse.additional.filter((record) => {
                if (record.RDLENGTH === 4) {
                    return record;
                }
            });
            const randomAdditional = getRandomEntry(additionalWithIPv4);
            rootNameServerIP = randomAdditional.RDATA.join('.');
            continue;
        }
      
  2. Handling Authority Records:

    • As we have already learnt in the fundamental section of the blog, not all responses will resolve into additional records with ip addresses of the authority NS records

    • So for those cases, we pick a valid authority records and select a random entry out of it, and try to resolve the ip address of the that record first

    • Once we are able to achive the ip address of the valid authority record it's same as finding it in the additional section, changing the rootNameServerIP to the new ip of this resolved record, and continuing the while loop to keep resolving for the same question but with different IP

    • But in case of invalid sub-domains, for example (ronit.dev is a valid domain, where as api.ronit.dev is not registered in which case we should resolve into a SOA record, where we just return the authority record, that will be ronit.dev in this case and it's resolved ip.

    let validAuthorityRecord: DNSAnswer | undefined;
    if (
        dnsResponse.authority &&
        dnsResponse.authority.length > 0 &&
        (!dnsResponse.additional || dnsResponse.additional.length === 0)
    ) {
        const validAuthorityRecords = dnsResponse.authority
            .map((authorityRecord) => {
                return {
                    ...authorityRecord,
                    NAME: decodeRDATA(authorityRecord.RDATA),
                };
            })
            .filter((authorityRecord) => {
                if (isValidDomain(authorityRecord.NAME)) {
                    return authorityRecord;
                }
            });
        validAuthorityRecord = getRandomEntry(validAuthorityRecords);

        if (validAuthorityRecord.TYPE === RECORD_TYPE.SOA) {
            return {
                header: {
                    ...header,
                    QR: QRIndicator.RESPONSE,
                    RCODE: RCode.NXDOMAIN,
                    NSCOUNT: dnsResponse.authority ? dnsResponse.authority.length : 0,
                },
                questions: [question],
                authority: dnsResponse.authority || [],
                answers: [],
            } as DNSObject;
        }
    }

    if (validAuthorityRecord) {
        const res = await recursiveLookup(
            {
                NAME: validAuthorityRecord.NAME,
                TYPE: RECORD_TYPE.A,
                CLASS: validAuthorityRecord.CLASS,
            },
            header,
        );

        if (res.answers) {
            const randomResponse = getRandomEntry(res.answers);
            rootNameServerIP = randomResponse.RDATA.join('.');
            continue;
        }
    }
  1. Handling Final Case:

    • Return NXDOMAIN response with SOA record if no valid authority or additional records are found.

        return {
            header: {
                ...header,
                QR: QRIndicator.RESPONSE,
                RCODE: RCode.NXDOMAIN,
                NSCOUNT: dnsResponse.authority ? dnsResponse.authority.length : 0,
            },
            questions: [question],
            authority: dnsResponse.authority || [],
            answers: [],
        } as DNSObject;
      
  2. Error Handling:

    • Lastly catch and log errors during the lookup process.

    • Return a response indicating NXDOMAIN if an error occurs.

    • Their are definitely more elegant way of handling errors here, but for demo purposes this will just get the job done

        catch (error) {
            console.error('Error in recursiveLookup:', error);
            return {
                header: {
                    ...header,
                    QR: QRIndicator.RESPONSE,
                    RCODE: RCode.NXDOMAIN,
                },
                questions: [question],
                authority: [],
                answers: [],
            } as DNSObject;
        }
      

Now we are done with the recursive lookup function, so Ideally we should be able to resolve any ip address of our liking. So let's write some tests to prove the same.