dnshash update.

[Michael Stone]

On Tue, 12 Apr 2011 at 18:41:05 -0400, "C. Scott Ananian" <cscott at laptop.org> wrote:
>On Sun, Nov 15, 2009 at 10:04 PM, Michael Stone <michael at laptop.org> wrote:
>> I recently taught dnshash to ping potential addresses before returning them
>> as results. This isn't a great solution, but it does appear to fix the
>> problems observed in the use of the first version of dnshash with ssh and
>> firefox and is therefore recommended for further testing.
>
> Michael -- I'd like to get an update on your work w/ this during my
> "mesh week" next week.  Could you give me a brief update on code
> status, results of testing, other thoughts re: mesh?

Scott,

Here's a review of the current status of dnshash, a brief explanation of a
failed alternate design that should inform other design attempts in this area,
and an explanation of how you might go about porting dnshash to Android. Also,
since this email is quite long enough already, I'll respond to your request for
"other thoughts re: mesh" on another occasion. :)

Regards,

Michael

----

## Status Review

   1. [Dnshash] is currently implemented as a (e)glibc [NSS] plugin, enabled
      through /etc/nsswitch.conf.

      This approach:

        * is usable by programs running on Linux that use e(g)libc's
          getaddrinfo() to do DNS resolution.

        * is probably straightforward to port to other operating systems and
          libc implementations with extensible getaddrinfo() implementations.
          (For the details for Android, please see the section below entitled
          "Dnshash on Android".)

        * is not applicable to programs that do their own DNS resolution.
          (Also, the other obvious design for these programs turns out to be
          unimplementable due to unsatisfiable hard constraints described in the
          section below entitled "Alternate design: recursive resolver".)

   2. As mentioned above in November 2009, it turns out to be important, due to
      some popular programs' use of lengthy TCP timeouts, to avoid returning
      addresses without some evidence that the addresses are actually
      contactable.

      The current solution (shelling out to ping6) to this problem is hackishly
      implemented but seems to work okay under very light testing and has the
      great benefit of simplicity compared to the alternate designs of doing the
      pinging in the plugin itself (hard due to the need for CAP_NET_RAW) or in
      a daemon (a complex shared resource).

   3. Regarding testing: dnshash has been tested successfully a handful of times
      in the past 18 months in two network scenarios:

        a) a physical network of 2-3 laptops running a mix of
           current-at-the-time versions of the Debian, Fedora, and OLPC
           operating systems all associated with a shared 802.11(g) access point

        b) a logical network built on top of Linux's network namespaces
           (CONFIG_NET_NS), ethernet bridges (CONFIG_BRIDGE), and virtual ethernet
           device pairs (CONFIG_VETH) running on a current-at-the-time Debian
           laptop.

      In each network scenario, the "Installation, Use, Testing, and Cleanup"
      test procedure was performed as described in the dnshash [README]. No
      errors were found.

      Finally, the set of planned but unscheduled testing work currently
      includes:

        * finishing the incomplete automation of the setup procedure for the
          logical network scenario available in the `xterm.py`, `test_gai.c`,
          and `newnetns.c` helpers in the dnshash git repo,

        * extending the logical network scenario to use the `netem`
          (CONFIG_NET_SCH_NETEM) traffic shaper to construct reproducible
          simulations of the effect of various packet loss, delay, and jitter
          processes on dnshash performance,

        * testing more client software and more input sequences.

[Dnshash]: http://wiki.laptop.org/go/Dnshash
[NSS]: http://www.gnu.org/s/libc/manual/html_node/Name-Service-Switch.html
[README]: http://dev.laptop.org/git/users/mstone/dnshash/plain/README


## Alternate design: recursive resolver

The NSS-plugin approach that I wound up implementing was always intended to be
a quick hack on the way to a "real" implementation in the form of a modified
local recursive resolver (probably based on djbdns' dnscache).

Unfortunately, this backup plan is impossible because the design space is
overconstrained as follows:

   1. IPv6 has only one link-local prefix, fe80::, for all interfaces.

   2. A single link-local address (e.g., fe80::3) may be bound to arbitrarily
      many interfaces so long as it is bound to at most one interface per link.

   3. As a result of (1) and (2), link-local addresses are ambiguous: they
      don't, by themselves, give an IP stack with multiple interfaces enough
      information to figure out which interface to use to emit packets whose
      destination address is link-local.

   4. Problem (3) was fixed in October 1998 [draft-ietf-ipngwg-bsd-api-new-02]
      by extending `struct sockaddr_in6` with a new field named `sin6_scope_id`.

   5. Unfortunately, the DNS AAAA record was standardized three years before
      this innovation in December 1995 [rfc1886] and it was not itself fixed
      after (4) was published as RFC 2553.

   5. As a result of (4) and (5), there is no standardized way to communicate
      non-ambiguous IPv6 link-local addresses through DNS.

The NSS plugin approach gets around this problem by modifying the behavior of
the getaddrinfo() library function, which can return full-blown `sockaddr_in6`
structs (as well as other structs for other protocols).

[rfc1886]: http://tools.ietf.org/html/rfc1886
[draft-ietf-ipngwg-bsd-api-new-02]: http://tools.ietf.org/html/draft-ietf-ipngwg-bsd-api-new-02


## Dnshash on Android

Dnshash is implementable on Android but new versions of bionic and libcore will
be required. In particular:

   * In order to get Bionic's implementation of `[getaddrinfo]()` to return
     dnshash results, we need to add a `_dnshash_getaddrinfo` procedure and we
     need to add a `struct ns_dtab` entry for this procedure to the `static
     const ns_dtab dtab[]` table in `[explore_fqdn]()`.

   * Once Bionic is returning useful results, we need to fix each of
     libcore's `[InetAddress_getaddrinfo]()`, `[lookupHostByName]()`, and
     `[getAllByNameImpl]()` procedures to pass our scope ids upward so that they
     are available when we actually construct the `java.net.Inet6Address`
     objects that are returned by `[java.net.InetAddress.getAllByName]()`.

   * (Fun historical sidenote: these scope_id propagation issues bugs were fixed
     [#6301779] in Mustang beta release in 2006!)

[getaddrinfo]: http://android.git.kernel.org/?p=platform/bionic.git;a=blob;f=libc/netbsd/net/getaddrinfo.c#l401
[explore_fqdn]: http://android.git.kernel.org/?p=platform/bionic.git;a=blob;f=libc/netbsd/net/getaddrinfo.c#l794
[InetAddress_getaddrinfo]: http://android.git.kernel.org/?p=platform/libcore.git;a=blob;f=luni/src/main/native/java_net_InetAddress.cpp;hb=HEAD#l69
[lookupHostByName]: http://android.git.kernel.org/?p=platform/libcore.git;a=blob;f=luni/src/main/java/java/net/InetAddress.java;hb=HEAD#l487
[getAllByNameImple]: http://android.git.kernel.org/?p=platform/libcore.git;a=blob;f=luni/src/main/java/java/net/InetAddress.java;hb=HEAD#l263
[java.net.InetAddress.getAllByName]: http://developer.android.com/reference/java/net/InetAddress.html#getAllByName(java.lang.String)
[#6301779]: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6301779