20160215 When to start shootin’

In a civil rights lawsuit about all-white juries in the southern states, a statistician calculates the probability of the lack of black jurors to 2e-14, and translates that number by saying that you have better chances of getting three consecutive royal flushes in poker.

Legend has it that the judge remarked “I’d start shootin’ at the second royal flush.” but ordered his remark stricken from the record.

We need a similar threshold determination to determine when we should poll a HTTPS server to make sure things are OK, because polling HTTPS servers too often will just waste everybodys electricity.

Assume for instance that your HTTPS server gives you a +/- 150msec confidence interval.

If somebody manages to corrupt NTP responses coming your way and manipulate your PLL to run 1PPM too fast, it will take 40 hours before you drift out of that confidence interval.

But in all likelyhood the attackers will be more impatient, and if they push your frequency 100PPM you will drift out of the confidence interval in just 25 minutes. Should they manage 500PPM, the max the kernel PLL will allow, it would only take 300 seconds.

Detecting that our frequency has changed “noticeably” is a good job for a standard deviation, any sudden onset attack will jack the standard deviation up real fast.

But detecting that the frequency is slowly being manipulated, for instance 0.1PPM/minute is harder, we also need to notice that the frequency has deviated from its long term average.

My first cut at a trigger looks like this:

Every 600 seconds:
        fnom = exp_avg(fpll, 1/72);
        stddev = exp_stddev(fpll, 1/8);
        trig = 2 * stddev + abs(f - fnom)
        if https_limit / trig > time_since_http_check:
                do_https_check()

Here is a little python script to simulate it:

#!/usr/local/bin/python

from __future__ import print_function

import math

def sim(txt, l):
        fnom = 0.0
        nn = 1
        avgdecay = 1./8.
        expavg = 0.0
        expsquare = 0.0
        expstddev = 0.0


        print("-" * len(txt))
        print(txt)
        print("-" * len(txt))

        print("%5s %7s %7s %7s %7s %7s %8s %8s" % (
                "t", "off", "freq", "fnom", "stddev", "trig", "due", "when"
        ))

        t = 0.0
        print("HTTPS check")
        limit = 150e-3
        tc = 0.0

        off = 0.0
        for f in l:
                fnom += (f - fnom) / nn
                if nn < 72:
                        nn += 1
                off += 60. * (f - fnom)
                expavg += (f - expavg) * avgdecay
                expsquare += (f * f - expsquare) * avgdecay
                expstddev = math.sqrt(expsquare - expavg * expavg)
                trig = 2. * expstddev + math.fabs(f - fnom)
                due = limit / trig
                print(
                        "%5d" % t,
                        "%7.3f" % off,
                        "%7.1e" % f,
                        "%7.1e" % fnom,
                        "%7.1e" % expstddev,
                        "%7.1e" % trig,
                        "%8.0f" % due,
                        "%8.0f" % (due - t)
                )
                if due + tc < t:
                        print("HTTPS check")
                        tc = t
                t += 600

sim("Nominal scenario, aircon wobbles the frequency +/- 3 PPM",
[
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
])

sim("10PPM step-change",
[
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,

        30e-6, 33e-6, 30e-6, 27e-6, 30e-6, 33e-6, 30e-6, 27e-6,
        30e-6, 33e-6, 30e-6, 27e-6, 30e-6, 33e-6, 30e-6, 27e-6,
        30e-6, 33e-6, 30e-6, 27e-6, 30e-6, 33e-6, 30e-6, 27e-6,
        30e-6, 33e-6, 30e-6, 27e-6, 30e-6, 33e-6, 30e-6, 27e-6,
])

sim("100PPM step-change",
[
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,

        120e-6, 123e-6, 120e-6, 117e-6, 120e-6, 123e-6, 120e-6, 117e-6,
        120e-6, 123e-6, 120e-6, 117e-6, 120e-6, 123e-6, 120e-6, 117e-6,
        120e-6, 123e-6, 120e-6, 117e-6, 120e-6, 123e-6, 120e-6, 117e-6,
        120e-6, 123e-6, 120e-6, 117e-6, 120e-6, 123e-6, 120e-6, 117e-6,
])

sim("500PPM step-change",
[
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,

        500e-6, 500e-6, 500e-6, 500e-6, 500e-6,
        500e-6, 500e-6, 500e-6, 500e-6, 500e-6,
        500e-6, 500e-6, 500e-6, 500e-6, 500e-6,
        500e-6, 500e-6, 500e-6, 500e-6, 500e-6,
])

sim("0.1PPM/min change",
[
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,

        20e-6, 21e-6, 22e-6, 23e-6, 24e-6, 25e-6, 26e-6, 27e-6, 28e-6, 29e-6,
        30e-6, 31e-6, 32e-6, 33e-6, 34e-6, 35e-6, 36e-6, 37e-6, 38e-6, 39e-6,
        45e-6, 46e-6, 47e-6, 48e-6, 49e-6, 45e-6, 46e-6, 47e-6, 48e-6, 49e-6,
])

sim("1PPM/min change",
[
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,
        20e-6, 23e-6, 20e-6, 17e-6, 20e-6, 23e-6, 20e-6, 17e-6,

        20e-6, 30e-6, 40e-6, 50e-6, 60e-6,
        70e-6, 80e-6, 90e-6, 100e-6, 110e-6,
        120e-6, 130e-6, 140e-6, 150e-6, 160e-6,
        170e-6, 180e-6, 190e-6, 200e-6, 110e-6,
])

phk