Tag Archives: tw

Conservative election in Byzantine Fault Tolerant Raft

Tangaroa, is a Byzantine tolerant Raft implementation in Haskell, developed by Christopher Copeland and Hongxia Zhong for a Distributed Systems class at Stanford. The authors apply many of the approaches in PBFT to Raft, allowing for the Byzantine failure of nodes.  My interest in this work is how can you stop unnecessary leader elections in Raft algorithm using more conservative election approaches, given that election are too common in some environments (see s4.2 in ARC) .

Copeland and Zhong quickly identify this is one of the key barriers to developing a byzantine raft and describe their lazy voters approach. As with the original Raft protocol, a node time out, becomes a candidate, increments its terms and dispatches RequestVotes RPC’s. In addition to the normal restrictions on granting a vote, Tangaroa adds two extra conditions

  • new term must be < current_term + H, where H is a statistically unlikely number of split votes.
  • the current leader must have failed to dispatch AppendEntries within the heartbeat.

I am not convinced that the first condition will not lead the system to become permanently unavailable. For example, a network partition could separate the nodes into two groups thus one group will have a leader in a low term and the other group constantly trying to re-elect a new leader as it cannot get a majority. When network connectivity is restored, the nodes in will observe a sudden unbounded term increase. Thus nodes will not give out their votes and the system is stalled.

The author’s highlight how the second condition could be implemented. Nodes who are in a position to grant a vote except that the second condition isn’t meet, will record the vote locally and then dispatch the votes only when they observe a leader failure for themselves. This means that a node may only replace the leader when a majority of nodes detect a failure (or the client does) instead of when a single node detects a failure. The paper doesn’t go into much detail about this and how this would impact performance, I suspect that this approach is a little too conservative and many in some cases make it significantly more difficult to replace a fault leader. Various implementation details need to be consider here, for example, if a node times out and dispatches its vote, how long until the node steps up to candidate itself? or after how long does it “forget” its local vote, the election timeout maybe.

Writing a Byzantine Fault Tolerant Raft was always going to be hard, Tangaroa is a good first step in the right direction.

Part 3: Running your own DNS Resolver with MirageOS

This article is the third in the “Running your own DNS Resolver with MirageOS” series. In the first part, we used the ocaml-dns library to lookup the hostname corresponding with an IP address using its Dns_resolver_mirage module. In the second part, we wrote a simple DNS server, which serves RRs from a zone file using the Dns_server_mirage module.

Today in the third part, we will combine the above to write a simple DNS resolver, which relays queries to another DNS resolver. Then we will compose this with our simple DNS server from last week, to build a resolver which first looks up queries in the host file and if unsuccessful will relay the query to another DNS resolver.

As always, the complete code for these examples is in ocaml-dns-examples.

3.1 DNS FoRwarder

When writing our simple DNS server, we used a function called serve_with_zonefile in Dns_server_mirage to service incoming DNS queries. Now we are going remove a layer of abstraction and instead use serve_with_processor:

val serve_with_processor: t -> port:int -> processor:(module PROCESSOR) -> unit Lwt.t
val serve_with_zonefile : t -> port:int -> zonefile:string -> unit Lwt.t

Now instead of passing the function a simple string, representing the filename of zonefile, we pass a first class module, satisfying the PROCESSOR signature. We can generate such a module by writing a process and using processor_of_process:

type ip_endpoint = Ipaddr.t * int

type 'a process = src:ip_endpoint -> dst:ip_endpoint -> 'a -> Dns.Query.answer option Lwt.t

module type PROCESSOR = sig
  include Dns.Protocol.SERVER

  (** DNS responder function.
      @param src Server sockaddr
      @param dst Client sockaddr
      @param Query packet
      @return Answer packet
  *)
  val process : context process
end

type 'a processor = (module PROCESSOR with type context = 'a)

val processor_of_process : Dns.Packet.t process -> Dns.Packet.t processor

So given a Dns.Packet.t process, which is a function of type:

src:ip_endpoint -> dst:ip_endpoint -> Dns.Packet.t -> Dns.Query.answer option Lwt.t

We can now service DNS packets. If we assume that myprocess is a function of this type, we can service DNS queries with the following unikernel

open Lwt
open V1_LWT
open Dns
open Dns_server

let port = 53

module Main (C:CONSOLE) (K:KV_RO) (S:STACKV4) = struct

  module U = S.UDPV4
  module DS = Dns_server_mirage.Make(K)(S)

  let myprocess ~src ~dst packet = ...

  let start c k s =
    let server = DS.create s k in
    let processor = ((Dns_server.processor_of_process myprocess) :> (module Dns_server.PROCESSOR)) in 
    DS.serve_with_processor server ~port ~processor
end

Now we will write an implementation of myprocess which will service DNS packets by forwarding them to another DNS resolver and then relaying the response.

Recall from part 1, that you can use the resolve function in Dns_resolver_mirage to do this. All that remains is to wrap invocation of resolve, in a function of type Dns.Packet.t process, which can be done as follows:

 
let process resolver ~src ~dst packet =
      let open Packet in
      match packet.questions with
      | [] -> (* we are not supporting QDCOUNT = 0  *)
          return None 
      | [q] -> 
         DR.resolve (module Dns.Protocol.Client) resolver 
         resolver_addr resolver_port q.q_class q.q_type q.q_name 
          >>= fun result ->
          return (Some (Dns.Query.answer_of_response result))) 
      | _ -> (* we are not supporting QDCOUNT > 1 *)
          return None
3.2 DNS server & forwarder

[this part requires PR 58 on ocaml-dns until it is merged in]

We will extend our DNS forwarded to first check a zonefile, this is achieve with just 3 extra lines:

...
DS.eventual_process_of_zonefiles server [zonefile]
>>= fun process ->
let processor = (processor_of_process (compose process (forwarder resolver)) :> (module Dns_server.PROCESSOR)) in
...

Here we are using compose to use two processes: one called process generated from the zonefile and one called forwarder, from the forwarding code in the last section.

Next time, we will extend our DNS resolver to include a cache.

 

 

Poster for “Life on the Edge: New Abstractions for Edge Network Distributed Computing”

Here is a draft copy of the A1 poster I’ll be presenting at the 2nd Annual Oxbridge Women in Computer Science Conference in Oxford. The poster abstract is in a previous post. Any feedback would be greatly appreciated.

version 1 (9:20 11/3)

women@cl poster

 

version 2 (10:50 11/3)

now with left alignment of text on the left and right alignment of text on the right, gateway text on black router removed

women@cl poster

 

VERSION 3 (11:00 11/3)

now with bolded keywords

women@cl poster (3)

 

FINAL VERSION (11:23 11/3)

new text for the aim box

women@cl poster (4)

VPN providers are hijacking DNS

Are you thinking of using a VPN to bypass DNS hijacking by your ISP (as described in Redirecting DNS for Ads and Profit and Middleboxes considered harmful: DNS Edition)?

Then think again.

A new paper titled “A Glance through the VPN Looking Glass: IPv6 Leakage and DNS Hijacking in Commercial VPN clients” by Vasile Claudiu Perta, Marco Valerio Barbera, Gareth Tyson, Hamed Haddadi and Alessandro Mei, demonstrates that many commercial VPN operators are at it too.

The paper will appear at The 15th Privacy Enhancing Technologies Symposium and is available online now (open access copy linked).

Paper Notes: Redirecting DNS for Ads and Profit

Redirecting DNS for Ads and Profit is one of the collection of papers from the ICSI team, with the results from the Netalyzr, network diagnosis tool. This paper focuses on the 66K session traces where DNS error traffic has been monetization and calls out Paxfire, for their role in this area, the paper focuses on NXDOMAIN wildcarding and search engine proxying (see my past post on how middleboxes interfere with DNS for an introduction to these techniques). The authors acknowledge the unrepresentative sample of Netalyzr users and the high number of sessions using OpenDNS or Comcast DNS resolvers.

NXDOMAIN wildcarding is not encouraged by ICANN and can have serious implications for non web browser DNS traffic (some resolvers only rewrite lookups starting with www. to try to prevent this). In many cases, redirection servers do not simply use HTTP 302.

The highlight of this paper was the fake NXDOMAIN opt-out offered by Paxfire, where the ad server simply served the user’s browser’s error page.

DNSSEC may provide authenticated denial of existence but this doesn’t necessarily fix the problem, for example Xerocole offers DNS resolvers with the option to simply rewrite DNSSEC signed NXDOMAIN responses without a signature, thus assuming the client will not validate DNSSEC.

OpenDNS wildcards NXDOMAIN and SERVFAIL errors as well as directing users to the redirection server if there server supports only IPv6. This is provided as an option in D-Link routers.

The study observed >12 ISPs using squid proxies to redirect search engine traffic. The study did not observe resolver independent NXDOMAIN redirection but did see NATs redirecting all DNS requests (regardless of resolver) to the configured recursive resolver, thus creating in-path NXDOMAIN rewriting if the new resolver uses NXDOMAIN wildcarding.

This paper is a fun, light read that I would recommend, though its results are a bit out of date now, as it used data from Jan 2010 to May 2011.