July « 2009 « Equilibrium Networks

In the course of describing one reason why Poisson traffic is so convenient, I’ll briefly discuss how to make things look Poissonian. It turns out that an arrival or point process $N_t$ with a well-defined rate $q$ can be rescaled to a unit-rate Poisson process. Papangelou, who along with Meyer obtained this result in the early seventies, put it in plain language:

Roughly, moving in $[0, \infty)$ so as to meet expected future points at a rate of one per time unit (given at each instant complete knowledge of the past), we meet them at the times of a Poisson process.

A proof using “elementary” methods is in “The Time-Rescaling Theorem and Its Application to Neural Spike Train Data Analysis” by Brown et al., and their statement of the time rescaling theorem is adapted below:

Let $0 < t_1 < t_2 < ... < t_n < t$ be a finite realization of a point process with a conditional rate function $q(t | \mathcal{F}_t)$ that is nonnegative on $(0, T]$ . Define $\tau(x) := \int_0^x q(s | \mathcal{F}_s) \ ds$ , and assume that $\mathbb{P}(\tau(t) < \infty | 0 < t \le T) = 1.$ Then the family $\{\tau(t_k)\}_{k=1}^n$ is a finite realization of a unit-rate Poisson process.

(Here the notation $\mathcal{F}_s$ just indicates the history of the process up to and including time $s.$ Technically it refers to the natural filtration of the process. More sophisticated treatments of the time rescaling theorem are given in Theorem 7.4.I and Proposition 14.6.III of Daley and Vere-Jones, 2nd. ed.)

Using the time rescaling theorem, goodness-of-fit tests like the Kolmogorov-Smirnov test can then be applied to evaluate a model characterization of a process. (It is left as an exercise for the reader to evaluate network traffic models in this way, since as far as I can tell nobody has done this yet.) A simple large-deviation result I’ll discuss below is in the same spirit, but is more applicable as the basis of an anomaly detection technique for computer network traffic.

The problem in practice with using the time rescaling theorem is that without a model, getting a reasonable estimate of an arrival rate is hard for anything but an inhomogeneous Poisson process with sufficiently slow rate variation. For slowly varying Poisson processes, all you have to do is divide the number of recent arrivals by a corresponding time window. The only subtlety here is the time windowing, and it’s a minor one.

(However, even in the case of a homogeneous Poisson process with a maximum-likelihood rate estimate, the rescaled process can be far from Poissonian when the estimation timescales are short enough or the number of observed arrivals is small enough. Even though the large number of packet or even flow arrivals should mean that this typically wouldn’t be a concern for most network traffic applications, it should still serve to highlight the essential practical difficulty present even in the simplest possible application of the time rescaling theorem. For more details, see Schoenberg’s paper “On Rescaled Poisson Processes and the Brownian Bridge”.)

Another nice thing about Poisson processes is that forming martingales from them is easy, for essentially the same reason: because the rate is well-characterized, the so-called compensator (essentially, the expected value of a random process as a function of time) is simple. Without getting into too much detail, a martingale is a bounded random process whose expected future value is always the same as its current value. Archetypal examples in discrete and continuous time are, respectively, the number of heads minus the number of tails in a series of fair coin flips and Brownian motion. Martingales are very powerful tools in probability theory, and the following result is just one illustration of this fact.

Let $N_t$ be a homogeneous Poisson process with rate $q,$ and let $M_t := N_t - qt$ be the corresponding martingale. By a result called the optional sampling theorem, you can get independent identically distributed (IID) random variables from $M$ by considering the martingale differences at regular intervals: i.e., the differences $\Delta_k := M_{kt} - M_{(k-1)t}$ are IID, with expected value zero. And from this point you can apply large-deviation theory, which details the asymptotic behavior of large sums of IID random variables.

A few standard calculations yield first that

$\Lambda(u) := \log \mathbb{E} \exp u M_t = (e^u - u - 1)qt$

and subsequently that

$\Lambda^*(u) := \sup_{v \in \mathbb{R}} \ (uv - \Lambda(v)) = (u + qt) \cdot \log \left(\frac{u}{qt} + 1\right) - u$

so that after a bit of algebra, a routine application of the Cramér large-deviation theorem results in the asymptotic estimate

$\mathbb{P}(M_{nt} > na) \overset{n \uparrow \infty}{\longrightarrow} \exp(-n\Lambda^*(a)) \equiv (x^{-x}e^{x-1})^y$

for $a > 0$ , where $x = \frac{a}{qt} + 1$ and $y = qtn$ . This gets really small really fast.

Behavior of large deviation probabilities. $10^{-14}$ is pretty small last time I checked.

Here’s the punchline: suppose you had the wrong idea about the nature of a putative homogeneous Poisson process $N$ (e.g., your estimate of the rate was poor or $N$ actually failed to be a homogeneous Poisson process in the first place). Then the resulting putative martingale would not actually be a bona fide martingale, and an otherwise improbable large deviation would detect this fact with high probability and with few false positives. Notice that while this sort of approach uses quite a bit of probability theory, it doesn’t require any actual statistics other than a trivial rate estimate and a threshold to determine what constitutes a large enough deviation. And the fact that network traffic is increasingly Poissonian means that such approaches will be increasingly robust.

In the next post in this series I’ll cover the practical details of this technique.

Appendix

In this appendix I’ll go through the calculations mentioned above. First,

$\mathbb{E} \exp uM_t = \sum_{k = 0}^\infty \mathbb{P}(N_t = k) \exp (u[k - qt])$

$= \exp(-uqt) \sum_{k=0}^\infty \frac{(qt)^k}{k!} \exp(-qt) \exp(uk)$

$= \exp(-[u+1]qt) \sum_{k=0}^\infty \frac{(qt e^u)^k}{k!}$

$= \exp(-[u+1]qt) \exp(qt e^u)$

$= \exp([e^u - u - 1]qt).$

Next, $D_v(uv - \Lambda(v)) = u - \Lambda'(v)$ , and the RHS is zero iff $u = \Lambda'(v) = (e^v - 1)qt$ , or equivalently $v = v_* := \log(\frac{u}{qt} + 1)$ . Now $\Lambda'' \ge 0$ identically by Cauchy-Schwarz, so

$\Lambda^*(u) = (u + qt) \cdot \log \left(\frac{u}{qt} + 1\right) - u.$

Finally, for $a > 0,$

$\exp(-n \Lambda^*(a)) = \exp \left( -n(a + qt) \cdot \log \left(\frac{a}{qt} + 1\right) + na \right)$

$= \left(\left(\frac{a}{qt} + 1\right)^{-(a + qt)} e^a\right)^n$

$\equiv (x^{-x}e^{x-1})^y$

where $x = \frac{a}{qt} + 1$ and $y = qtn.$ Note that for $a, qt, n > 0$ , it happens that $x > 1, y > 0$ and $f(x) := x(1 - \log x) \in (-\infty, 1)$ , with $f(1) = 1$ and $\lim_{x \uparrow \infty} f(x) = -\infty$ . Moreover, $f'(x) = -\log x < 0$ for $x > 1,$ so $(x^{-x}e^{x-1})^y = (e^{x(1-\log x) - 1})^y \in (0, 1)$ , providing a helpful sanity check on the large-deviation asymptotics above.

As an aside, an essentially identical result can be obtained in general via a Chernoff bound. Briefly,

$\mathbb{P}(M_{nt} \ge na) \le \inf_{v > 0} \left( \frac{\mathbb{E} \exp vM_t}{\exp av} \right)^n$

$= \inf_{v > 0} \exp (-n[av - \Lambda(v)])$

$= \exp (-n\sup_{v > 0}[av - \Lambda(v)])$

$= \exp (-n\Lambda^*(a)),$

where the last equality follows by convexity and the assumption that $a > 0.$

2 Comments | Communications security, Equilibrium Networks, Mathematics, Networks, Nonrandom bits | Permalink
Posted by eqnets

Random bits

26 July 2009

Network Solutions hack

Congress cites concerns about secrecy and legality of CNCI

Bacterial computing

AT&T reportedly blocking access to img.4chan.org

Leave a Comment » | Communications security, Networks, Random bits, Science, Security | Permalink
Posted by eqnets

Hacking nuclear command and control

24 July 2009

A recent paper by Jason Fritz available at the International Commission on Nuclear Nonproliferation and Disarmament notionally discusses hacking nuclear command and control. The paper is mostly a cursory overview of nuclear C2 with speculation added, e.g. “such systems might depend on X which hackers might be able to exploit [in some unspecified way Y]“. Some choice quotes:

If access to command and control centres is obtained, terrorists could fake or actually cause one nuclear-armed state to attack another, thus provoking a nuclear response from another nuclear power. This may be an easier alternative for terrorist groups than building or acquiring a nuclear weapon or dirty bomb themselves. …

Efforts by militaries to place increasing reliance on computer networks, including experimental technology such as autonomous systems, and their desire to have multiple launch options, such as nuclear triad capability, enables multiple entry points for terrorists. For example, if a terrestrial command centre is impenetrable, perhaps isolating one nuclear armed submarine would prove an easier task. There is evidence to suggest multiple attempts have been made by hackers to compromise the extremely low radio frequency once used by the US Navy to send nuclear launch approval to submerged submarines. …

A sophisticated and all encompassing combination of traditional terrorism and cyber terrorism could be enough to launch nuclear weapons on its own, without the need for compromising command and control centres directly. …

It may take years to prepare an attack against advanced networks, including the identification of exploits, development of tools, and the implementation of a plan, yet technology is rapidly advancing and networks continually updating, possibly disrupting those plans. Terrorist organisations may not be able to keep up with the massive financial backing of nation states. State-sponsored hackers have this problem themselves. Despite the possibility of exaggerated claims, a threat remains…

Cyber terrorists [seeking to provoke a US nuclear launch through spoofing] would not need deception that could stand up over time; they would only need to be believable for the first 15 minutes or so. …

Some reports have noted a Pentagon review, which showed a potential “electronic back door into the US Navy’s system for broadcasting nuclear launch orders to Trident submarines”. The investigation showed that cyber terrorists could potentially infiltrate this network and insert false orders for launch. The investigation led to “elaborate new instructions for validating launch orders”. …

Nuclear command and control structures are vulnerable to cyber terrorism…Inherent flaws in current nuclear postures provide increasing opportunities for computer exploitation. Despite claims that nuclear launch orders can only come from the highest authorities, numerous examples point towards an ability to sidestep the chain of command and insert orders at lower levels. Cyber terrorists could also provoke a nuclear launch by spoofing early warning and identification systems or by degrading communication networks.

The juicy-looking bit about hacking SSBNs is from this reference, and the relevant quote is below:

The sobering results of the still- classified work by a Pentagon “Commission on Nuclear Fail-Safe” – to which [Bruce] Blair testified about Soviet nuclear safeguards, inside a vault at the Pentagon around 1992 – point to US vulnerabilities that could also apply to Russian systems today. Investigators found an “electronic back door” into the US Navy’s system for broadcasting nuclear launch orders to Trident submarines.

“This deficiency allowed unauthorized hackers, which could be terrorists or high school mischief makers, to potentially insert a launch order and transmit it to the Trident,” Blair says. The gap was so serious that Navy launch order verifications had to be revised.

Notice the bit about 1992.

After reading this paper and having studied nuclear weapons policy both in coursework and informally over the years (to illustrate, a review I wrote in 2007 for a book on Chinese nuclear policy is here), the paper struck me as highly speculative. Despite this, it may get a lot of sensational attention, which would be bad.

The folks at STRATCOM have all seen WarGames (just a few years ago, I shared an office with a STRATCOM O-5 who loved to talk about things nuclear), and despite the USAF’s well-publicized rccent gaffes, the US military does not take nuclear C2 lightly. Having met quite a few workers in the Russian nuclear establishment visiting a US nonproliferation institute, I feel justified in saying that Russia does not take nuclear C2 lightly either. More generally, anyone that is willing to “eat grass” to develop nuclear weapons is going to safeguard those weapons as carefully as they can, and initiatives like Nunn-Lugar go further by providing US help in securing nuclear materials.

What’s more, the dependence of most states’ nuclear C2 systems on networks is far from clear, and the corresponding vulnerability to information warfare even less so. Mr Fritz can’t be blamed for relying on OSINT, but the result is a work that does not begin to answer any of the by-now familiar questions it raises.

1 Comment | Commentary, Communications security, Nonrandom bits, Security | Permalink
Posted by eqnets