Frustration with the web

What a drag typing all of those numbers every time we want to visit a website, someone should think of a more efficient way for us humans to navigate the web. I know the numbers for my website by heart now, 49.12.41.13. Hold on, no numbers you say? But, how do you know which computers to contact?

This is going to be a short post about authoritative DNS servers and about polymorphism.

The Domain Name System is the eminence of the internet without which it would come to a halt.

The domain name system is a decentralized hierarchical database of records that allows the translation of hostnames to into IP addresses. Top level domains sit at the root of this hierarchy with these records scattered across the globe on thousands of servers.

How does one make sense in it? When it comes to the practical resolving of DNS requests, they're processed top to bottom. DNS Resolver is a so called client side of the system responsible for initiating queries that lead to a full translation. Resolvers check local cache first before sending the queries further if no match is found. When a request from a DNS client (like a web browser) is made, it tries to resolve it from a cache first. If it can't, it forwards it to an operating system level resolver which does the same. If it can't resolve, the request is sent to a series of external DNS servers. The first of these is usually hosted by the ISP. This external DNS server sends the request over to the root DNS server, which is then able to forward to a top level domain DNS server. The top level domain server then in turn request an authoritative DNS server containing information for the DNS zone it manages and connects the request with a record and corresponding IP address. The information is then returned to the client, completing the resolution.

If we looked onto the internet through the lenses of a hacker who wants to demolish it, one of the fastest ways of achieving that would be for them to get rid of the domain root. DNS records are saved in a tree data structure, and without the root it ceases to work. To make the system more reliable, thirteen groups of root DNS servers exist, spread across hundreds of servers in various places around the globe, each assigned to one of these groups. DNS requests are then routed by anycast on top of BGP to the closest node which has the needed information.

DNS Authoritative servers

DNS records were originally saved in a hosts.txt file. Similarly, zones were defined in zone files. These files were hosted by a central authority from which they were downloaded by non-authoritative DNS servers to perform resolution. As the amount of records increased, these approaches were abandoned in favor of a distributed system.

Real implementations such as Knot DNS, a GPLv2 implementation of an authoritative-only server created and maintained by CZ.NIC, use complex algorithms and data structures for request resolution. I decided to create a naive version of a DNS server in C++. Why? University exams are soon, I need to study. Additionally, who doesn't like to learn about networking? It demonstrates some neat polymorphic patterns.

Say we wanted our DNS server to store nestable zones and records (A, AAAA, CNAME, SPF). It should also be able to print information about stored data. Super, we'll make a Record class and be done with it, no OOP needed right,... right? Well, picture the class. If we wanted to store an "A" record, we would also have to allocate space for all the other types. If-else statements would take up the majority of the code. So, how will we do it? Polymorphically. The ability in programming to present the same programming interface for differing underlying forms, so that different classes related by some common superclass can be used in place of that superclass.

Let's try passing the following tests:

std::ostringstream oss;
Zone root_zone("<ROOT ZONE>");
Zone tld_edu_zone("edu");
Zone berkeley_zone("berkeley");
Zone berkeley_eng_zone("engineering");
Zone berkeley_chem_zone("chemistry");

assert(berkeley_eng_zone.add(
       Record_A("portal", IPv4("128.32.10.1"))) ==
       true);
assert(berkeley_eng_zone.add(Record_AAAA(
       "portal", IPv6("2607:f140:0:1::1"))) ==
       true);
assert(berkeley_eng_zone.add(Record_SPF("mail")
                 .add("ip4:128.32.0.0/16")
                 .add("ip6:2607:f140::/32")) ==
       true);

assert(berkeley_chem_zone.add(
       Record_A("www", IPv4("128.32.20.5"))) ==
       true);
assert(berkeley_chem_zone.add(Record_CNAME(
       "login", "auth.berkeley.edu.")) ==
       true);

assert(berkeley_zone.add(berkeley_eng_zone) == true);
assert(berkeley_zone.add(berkeley_chem_zone) == true);
assert(tld_edu_zone.add(berkeley_zone) == true);
assert(root_zone.add(tld_edu_zone) == true);

oss.str("");
oss << root_zone;
assert(oss.str() ==
       "<ROOT ZONE>\n"
       "    edu\n"
       "        berkeley\n"
       "            engineering\n"
       "                portal A 128.32.10.1\n"
       "                portal AAAA 2607:f140:0:1::1\n"
       "                mail SPF ip4:128.32.0.0/16, "
       "ip6:2607:f140::/32\n"
       "            chemistry\n"
       "                www A 128.32.20.5\n"
       "                login CNAME auth.berkeley.edu.\n");

oss.str("");
oss << tld_edu_zone;
assert(oss.str() ==
       "edu\n"
       "    berkeley\n"
       "        engineering\n"
       "            portal A 128.32.10.1\n"
       "            portal AAAA 2607:f140:0:1::1\n"
       "            mail SPF ip4:128.32.0.0/16, "
       "ip6:2607:f140::/32\n"
       "        chemistry\n"
       "            www A 128.32.20.5\n"
       "            login CNAME auth.berkeley.edu.\n");

We create the root, TLD, berkeley, engineering and chemistry zones, nest them into each other so it makes sense. (with berkeley being the parent of engineering and chemistry.) These zones are filled with records and subsequently printed. We'll start by defining what's common between all of our record types. In this simplified scenario it is the name and printing methods.

An abstract class that will serve as a parent in our polymorphic model:

class IRecord {
public:
    IRecord(const std::string &name) { _name = name; }
    virtual ~IRecord() = default;

    virtual void print(std::ostream &os,
               const std::string &prefix = "") const = 0;
    friend std::ostream &operator<<(std::ostream &os,
                    const IRecord &record) {
        record.print(os, "");
        return os;
    }

protected:
    std::string _name;
};

And we can now proceed to create four classes for our record types, each inheriting from IRecord and overriding the printing functionality:

class Record_A : public IRecord {
public:
    Record_A(const std::string &name, const IPv4 &ip)
        : IRecord(name), _ip(ip) {}

    void print(std::ostream &os,
           const std::string &prefix = "") const override {
        os << _name << " A " << _ip;
    }

private:
    IPv4 _ip;
};

class Record_AAAA : public IRecord {
public:
    Record_AAAA(const std::string &name, const IPv6 &ip)
        : IRecord(name), _ip(ip) {}

    void print(std::ostream &os,
           const std::string &prefix = "") const override {
        os << _name << " AAAA " << _ip;
    }

private:
    IPv6 _ip;
};

class Record_CNAME : public IRecord {
      public:
    Record_CNAME(const std::string &name, const std::string &alias)
        : IRecord(name), _alias(alias) {}

    void print(std::ostream &os,
           const std::string &prefix = "") const override {
        os << _name << " CNAME " << _alias;
    }

private:
    std::string _alias;
};

class Record_SPF : public IRecord {
public:
    Record_SPF(std::string name) : IRecord(name) {}
    Record_SPF &add(const std::string &item) {
        _items.push_back(item);
        // returns the current object to allow method chaining
        return *this;
    }

    void print(std::ostream &os,
           const std::string &prefix = "") const override {
        os << _name << " SPF";
        for (size_t i = 0; i < _items.size(); ++i) {
            if (i == 0) {
                os << " " << _items[i];
            } else {
                os << ", " << _items[i];
            }
        }
    }

private:
    std::vector<std::string> _items;
};

However, how will we store the zone? Remember that a zone can be added as a record to another zone. We'll use the composite pattern with our zone inheriting from the common superclass. This will allow us to create a tree like structure of zones:

class Zone : public IRecord {
public:
    Zone(std::string name) : IRecord(name) {}
    bool add(const IRecord &record) {
        // have to call clone because we 1) don't know the type and 2)
        // cannot create an instance of an abstract class
        // also since this means that we are not storing a reference, but
        // a deep copy = no cycles with zones
        // Did not include the clone method to keep the code simple, but
        // it essentially simply returns a new object of itself through
        // the copy constructor
        _registrar.push_back(
            std::unique_ptr<IRecord>(record.clone()));
        return true;
    }
    void print(std::ostream &os,
           const std::string &prefix = "") const override {
        os << _name;
        std::string newPrefix = prefix + "    ";
        for (size_t i = 0; i < _registrar.size(); ++i) {
            os << "\n" << newPrefix;
            _registrar[i]->print(os, newPrefix);
        }
    }
    friend std::ostream &operator<<(std::ostream &os, const Zone &zone) {
        zone.print(os, "");
        os << "\n";
        return os;
    }
private:
    std::vector<std::unique_ptr<IRecord>> _registrar;
};

And just like that, we've created a DNS server!

All in all, we end up with a program that allows us to define zones in a tree like structure, just like it is done in practice. What's next? We could implement functionality to search for records, to delete them, to manage exclusivity,.. and all of that should be relatively non-problematic thanks to the architecture chosen.

Perhaps I'll come back to this later and try to implement a super fast searching algorithm, but until that happens our server will keep things to itself.