The Leap Second That Went Negative — JavaScript Bug Hunt

Briefing

Modelled on Cloudflare's New Year's Day 2017 DNS incident. When a leap second was inserted at midnight UTC on 1 January 2017, Cloudflare's RRDNS resolver measured a round-trip time by subtracting two readings of the wall clock. Across the leap second the result came out negative, and that value was passed to a random-selection routine that only accepts a positive bound. The routine panicked, and some DNS resolutions (notably for CNAME lookups) failed until the code was patched to treat negative values as zero.

This reconstruction times each upstream resolver with an injected clock and later adds random jitter bounded by the recorded RTT. A clock that steps backwards makes the recorded RTT negative, and the next selection throws.

Fix recordRtt so a backwards clock can never produce a negative round-trip time.

Bug report

BUG-RRDNS-LEAP · Priority: Critical · Reported by: DNS on-call

recordRtt(server, clock, send):

• reads clock.now() before and after calling send(server.name)
• the round trip is (after - before) in milliseconds, but a duration can never be negative: when the clock stepped backwards (leap second, NTP correction) the round trip is recorded as 0
• stores the value in server.rttMs and returns it

pickUpstream(servers, rand) scores every server as rttMs + randomBelow(rttMs + 1, rand) and returns the lowest score (first wins a tie). It must never throw for servers timed by recordRtt.

Observed: after 00:00:00 UTC a resolver was recorded with rttMs = -250 and every later pickUpstream call threw "invalid argument to randomBelow".

Logs

[rrdns] upstream=10.0.4.2 rtt=-250ms
[rrdns] panic: invalid argument to randomBelow: -249
[rrdns] SERVFAIL for 1,834 CNAME lookups in the last 60s

The code as shipped

src/dns/upstream.js (editable)

var random = require("./random");

// Times one query against a resolver and remembers the round trip.
exports.recordRtt = function (server, clock, send) {
  var start = clock.now();
  send(server.name);
  var rtt = clock.now() - start;
  server.rttMs = rtt;
  return rtt;
};

// Up to 100% random jitter, so equally fast resolvers share the load.
exports.jitteredRtt = function (server, rand) {
  return server.rttMs + random.randomBelow(server.rttMs + 1, rand);
};

// The resolver with the lowest jittered RTT wins; the first one wins a tie.
exports.pickUpstream = function (servers, rand) {
  var best = null;
  var bestScore = Infinity;
  for (var i = 0; i < servers.length; i++) {
    var score = exports.jitteredRtt(servers[i], rand);
    if (score < bestScore) {
      best = servers[i];
      bestScore = score;
    }
  }
  return best;
};

Read-only context: src/dns/random.js.