October « 2009 « Equilibrium Networks

DARPA Network Challenge

29 October 2009

You heard it here first (thanks FS): check out the DARPA Network Challenge. I am going to personally register (note that EQ can’t register). If you want to be on my team email me at

networkchallenge AT gmail DOT com

with the subject line: team. Include your mailing address to ensure 1 per address. If there are duplicate addresses, explain them.

I’ll split the prize (should we get it) as follows: $1K each will go to those who actually (first) report the balloons, and I’ll hold drawings for each $100 of the remainder. All team members will be eligible for every drawing, so there can be repeats. By my arithmetic that makes 10 $1K awards and 300 $100 random prizes. If you join the team after the contest starts, you will be ineligible for the random prizes, but you can still get $1K for reporting the balloon locations first.

5 Comments | Networks, Nonrandom bits | Permalink
Posted by eqnets

Random bits

28 October 2009

“By the time the research project [spearheaded by the University of Illinois 'to make certain that the smart meters and other devices implemented by power companies can resist hackers and other attackers'] is completed, most of the nation will have already adopted untested and unsecured technologies.” (extra super bonus: Richard Clarke identifies Brazil as a location where hackers took down a power grid recently)

“a single [31 GeV] photon produced by the gamma-ray burst GRB 090510″ indicates that “if there is a quantum influence on the speed of light, it can only operate at distances of less than 1.2 times the Planck length”

Relating the asymptotic bound simultaneously optimizing transmission rate and relative minimum distance of error-correcting codes to phase diagrams of quantum statistical mechanical systems

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

The “Korean” Cyber Attacks and Their Implications for Cyber Conflict

27 October 2009

CSIS has published an eponymous paper (PDF) by James Lewis that came to my attention via Threatpost. It is surprisingly good and pleasantly brief, if a bit muddled in places. Early on, Lewis points out the characteristic uncertainties (attribution, scope, and effect) associated with cyber attacks, and mentions the familiar fact that the calculi of deterrence, proportionality, etc have not been properly formulated for cyber. And like most people that have taken a serious look, he thinks that

Cyber conflict will be part of warfare in the future and advanced militaries now have the capability to launch cyber attacks not only against data and networks, but also against the critical infrastructure that depend on these networks.

Sounds about right to me. But Lewis fumbles the ball a bit later:

The alternative to the conclusion that terrorist groups currently lack the capabilities to launch a cyber attack is that they have these capabilities but have chosen not to use them. This alternative is nonsensical.

This is only partially true. There is a very simple reason why terrorists wouldn’t launch cyber attacks. They may not have the capabilities, but on the other hand, they could probably get them. But they can already get more bang for their buck with bombs. Terrorists want to cause terror. Cyber attacks can’t do that unless they’re very large and sophisticated. And the resources such an attack would require don’t provide the same ROI as something like dispersed and coordinated bombs would.

To some extent this argument applies to states as well: a tactical physical attack isn’t worth using a strategic cyber attack to complement it. Conversely, because the cyber capability is strategic and only worth exercising in concert with physical attacks, the physical attack should have a strategic aim. (The purported cyber aspect of Israel’s strike against a purported Syrian nuclear facility would fit this bill nicely.) At the same time, attribution will be easy to get for the physical attack, which removes a lot of the attractive features that non-attribution nominally confers upon cyber attacks. That means that there is already a pretty clear threshold below which a nation-state will not launch a serious cyber attack.

Lewis actually articulates the more commonly acknowledged elements of this argument, though like most analysts he seems to have missed the fact that attribution will be easiest precisely when it matters most:

Serious cyber attack independent of some larger conflict is unlikely…The political threshold for serious cyber attack (as opposed to espionage) by a nation-state is very high, likely as high as the threshold for conventional military action. At a minimum, this suggests that a serious cyber attack is a precursor, a warning, that some more serious conflict is about to begin.

Absent such larger conflict, however, a nation-state is no more likely to launch a serious cyber attack than they are to shoot a random missile at an opponent. The risk is too great and the benefits of a cyber attack by itself too small for political leaders to authorize the use of this capability in anything short of a situation where they had already decided on military action. Cyber weapons are not decisive; cyber attack by itself will not win a conflict, particularly against a large and powerful opponent. It is striking that to date; no cyber “attack” that rises above the level of espionage or crime has been launched outside of a military conflict.

[emphases added]

The last real nugget relates to cyberterrorism:

[Host state tolerance] provides a degree of constraint on support for cyber terrorism…The political environment in which the most advanced cybercriminals exist militates against them becoming mercenaries for many terrorist groups without the consent of their host….Even if we accept this political constraint on mercenary support for cyber terror, other trends suggests [sic] that terrorist use of advanced cyber weapons (if current trends remain unchanged) is inevitable…in less than a decade, perhaps much less, a terrorist group could enter the cybercrime black market and acquire the capabilities needed for a serious cyber attack.

This actually may be true. At present, and as I’ve mentioned here, there is basically no such thing as cyberterrorism. But that doesn’t mean that there won’t be in the future. I’d keep my eyes on outfits like the Russian Business Network. If terrorists or organized cybercriminals can achieve their aims more effectively with cyber, they’ll use it. It’s up to folks like us to keep the barriers to entry high.

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

A graded lexicographic index, part 3

26 October 2009

In an earlier post we covered some more sophisticated ways of implementing a graded lexicographic index, a/k/a the state index. One of these dealt with producing a superset of the state indices of the neighbors of a given state (here $X_{B,b}$ is abusively interpreted as a graph embedded in $\mathbb{R}^{B+1}$ where edges join any two vertices that are a distance $\sqrt{2}$ apart). A careful exploitation of this technique leads to a very efficient way of updating the state index for random walks on $X_{B,b}.$ Basically, the idea is to just determine which element of the neighborhood is the correct one, and restrict the neighborhood algorithm to a single vertex. In practice this means a lot of careful indexing and addition of appropriate binomial coefficients, but the basic idea is really just to omit the extra work in the neighborhood algorithm.

Here’s some MATLAB code that does the trick:

function y = stateindexupdate(a);

% a is an array of states (assumed to be) in a bucketspace
% this illustrates efficient stateindex updating

T = size(a,1);
B = size(a,2);
b = sum(a(1,:));

% Pascal matrix
mb = max(b+1,B+1);
P1 = pascal(mb);
P = P1(1:B-1,:);
PA = [zeros(1,mb);P];

ia(1) = stateindex(a(1,:));

for j = 2:T
 % compute tau:
 tau = 1 + cumsum(fliplr(a(j,:)));
 % compute the ball move that got us here:
 move = a(j,:) - a(j-1,:);
 n = 0; % init the "slot" index
 % compute the corresponding slot index...
 % first, ID the first nonzero element of the move a la Java/C:
 for k = 1:B
  if move(k)
   % now find the second nonzero element m:
   for i = k+1:B
    if move(i)
     m = i;
     break;
    end
   end
   % the slot n is as follows:
   n = move(k) * ( (B-k)*((B-k)+1)/2 - B + m);   % move(i) = sign(move(i))
   break;
  end
 end

 % compute the first (signed) triangular number further from zero:
 for k = 0:B
  n2 = k * (k+1)/2;
  if n2 >= abs(n)
   n2 = sign(n) * n2;
   break;
  end
 end

 d = abs(n2-n);
 l = ( -1 + sqrt(1+8*abs(n2)) )/2;  % l*(l+1)/2 = abs(n2);

 % the sum will go from d+2 to l+1...
 ind = (d+2):(l+1);
 % finally, perform the sum
 lind = length(ind);
 temp = zeros(1,lind);
 if n2 < 0
  for i = 1:lind
   temp(i) = PA(ind(i),tau(ind(i)-1)-1);
  end
  delta = -sum(temp);
 elseif n2 > 0
  for i = 1:lind
   temp(i) = PA(ind(i),tau(ind(i)-1));
  end
  delta = sum(temp);
 else
  delta = 0;
 end

 % finally, update the stateindex:
 ia(j) = ia(j-1) + delta;
end

y=ia;

This runs really fast. A Java version of this code that we produced performs many millions of updates per second on a decent processor core.

One of the nicest things about “grlex” ordering and indexing is that it can be used as a primitive to tackle lots of otherwise difficult problems. For instance, I’ve used it to help (among other things) emulate an older network security monitoring platform, analyze generalized multivariate de Moivre martingales, perform multivariate Lagrange interpolation, study energy functions on equivalence classes of directed graphs, and to construct propagation operators implementing periodic hexagonal, truncated-octahedral, and more generally permutohedral boundary conditions for lattice models (such as spin or lattice Boltzmann models) with surprising ease.

Hopefully some of these more advanced techniques for grlex stuff will be of use elsewhere. If you’d like to use some of this code, just ask: we’ll provide it under an open-source license.

Leave a Comment » | Equilibrium Networks, Mathematics, Nonrandom bits, Science | Permalink
Posted by eqnets

Random bits

23 October 2009

“The Chinese government is ratcheting up its cyberspying operations against the U.S., a congressional advisory panel found”

Helping Wall Street cheat

Using AdS/CFT to explain why some metals have resistance that scales linearly with temperature

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

Random bits

21 October 2009

A crowdsourced proof of the density Hales-Jewett theorem hits the arxiv

“A pessimist might say that combining string theory and loop quantum gravity is like combining epicycles and aether”

Leave a Comment » | Mathematics, Random bits, Science | Permalink
Posted by eqnets

Securing the Information Highway

20 October 2009

The November/December issue of Foreign Affairs (unfortunately not yet available online as of this writing) has an eponymous piece by Wesley Clark and Peter Levin: in it, they write that

[The limited success of the July 4 cyberattacks principally affecting the US and Korea] may embolden future hackers to attack critical infrastructure, such as power generators or air-traffic-control systems, with devastating consequences for the U.S. economy and national security…There is no form of military combat more irregular than an electronic attack: it is extremely cheap, is very fast, and can disrupt or deny critical services at the moment of maximum peril…Disturbingly, [other nations] seem to understand the vulnerabilities of the United States’ network infrastructure better than many Americans do…The longer the U.S government waits [to confront the real threats in cybersecurity], the more devastating the eventual assault is likely to be…the consequences of a major breach would be catastrophic.

Clark and Levin recount William Safire’s claim that a 3-kiloton explosion of a Siberian natural gas pipeline in 1982—”the most monumental non-nuclear explosion and fire ever seen from space”—was the direct consequence of a Trojan inserted into Canadian SCADA software that the CIA allowed the KGB to steal. They recirculate the rumor that the Israeli destruction of a purported Syrian nuclear facility in 2007 was facilitated by a cyberattack targeting Syrian air defense systems. (This blog has linked to other reports of capabilities along similar lines, such as this one.)

But their real focus is (not surprisingly, given Levin’s history as founder of a hardware outfit specializing in the area) is on the problem of validating hardware. DoD has been very concerned with the idea of hardware Trojans the last few years. Nobody in the military/intelligence-industrial complex wants to take it on faith that chips that are manufactured in China or Taiwan don’t have backdoors. There are apparent precedents for the hardware Trojan such as old reports involving Crypto AG. So NSA started up a trusted foundry and DARPA started the TRUST program (whose PM funded some of my research some years back, so I applaud his taste on both counts). But that leaves the vast majority of chips in network components still unaccounted for, including a large number of counterfeit chips.

Clark and Levin propose an emphasis on reconfigurable hardware (such as FPGAs) and the sort of immunological paradigm started by the Forrest group at UNM as an example of a sound defensive strategy. While the practical utility (as compared to the undeniable conceptual elegance) of the paradigm for network defense is not clear to me (but then again I’m obviously a partisan when it comes to the best scientific principles for designing network defense infrastructure), the ideas of using reconfigurable hardware and avoiding a computational and network monoculture that goes hand-in-hand with immunological principles are sound ones that I’ve agreed with for some time. I gained an appreciation of the benefits of FPGAs from performing research on algorithms for reconfigurable computing architectures some years back, and at a conference last year I got into a brief argument on the security dangers of monocultures with a government sysadmin who lauded the monolithic computing infrastructure he maintained. So it’s not a stretch to say that I am extremely sympathetic to their point of view.

Clark and Levin close by highlighting the need for open infrastructure–both reconfigurable hardware and open source software, and (insofar as it can be implemented) this is the entirely correct approach to technological security of any form. As Reagan said: “trust, but verify”.

update 10/23: The article is available here (subscription required).

Leave a Comment » | Commentary, Communications security, Equilibrium Networks, Nonrandom bits, Security | Permalink
Posted by eqnets

A graded lexicographic index, part 2

19 October 2009

The previous post on this topic covered basic code for producing a graded lexicographic index (a/k/a the state index) and its inverse. This post will cover some more advanced techniques. The first one of these is simple: as de Boor pointed out (and it took me quite a while to catch on) the state index $I(\alpha)$ of $\alpha \in X_{B,b}$ can be given by a simple formula. Let $PA$ denote the matrix given by the following MATLAB code:

mb=max(b+1,B+1);  P1=pascal(mb);  P=P1(1:B-1,:);  PA=[zeros(1,mb);P];

For example, with $B = 4, b = 8$ this is

$PA = \left( \begin{smallmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 \end{smallmatrix} \right).$

(Identifying the elements of the Pascal matrix with binomial coefficients would introduce some minor technical complications w/r/t the top row, and so we avoid this.) Now let

$\alpha \equiv \sum_{k=1}^K \alpha_{j_k} \delta_{j_k}, \ \ \alpha_{j_k} > 0 \ \ \forall k.$

Then

$I(\alpha) = 1 + \sum_{k=1}^K \sum_{m=1}^{\alpha_{j_k}} PA \left( B + 1 - j_k, y_{km}(\alpha)\right)$

where

$y_{km}(\alpha) = b + 2 - m - \sum_{\ell = 0}^{k-1} \alpha_{j_\ell}$

and an empty sum is evaluated as zero. This is embodied in the following MATLAB code:

J = find(alpha);
K = length(J);

for k = 1:K
   temp1 = sum(alpha(J(1:(k-1))));
   for m = 1:alpha(J(k))
      stateindex = stateindex + PA(B+1-J(k),b+2-temp1-m);
   end
end

stateindex = stateindex + 1;

This is hard to beat in general. However, for some applications it is sufficient to compute the state index at a neighboring site. And this can actually be done much more effectively in practice.

A deceptively simple algorithm always produces a superset of the neighborhood of a state in bucketspace. Write

$\tau_k (\alpha) := 1+ \sum_{j=1}^k \alpha_{B-j+1}$

and for a finite subset $Y$ of $\mathbb{R},$ let $\mu_k(Y)$ and $\mu^k(Y)$ respectively denote the $k$ least and greatest elements of $Y.$ Now set $I_1 := \{I(\alpha)\}$ and given $I_k$ for $k > 0$ form

$I_{k+1} := I_{k+1}^- \cup \{I_k\} \cup I_{k+1}^+$

where

$I_{k+1}^- := \{ \left( \mu_{k-1}(I_k) \cup I_1 \right) - PA(k, \tau_k) \}$

and

$I_{k+1}^+ := \{ \left( \mu^{k-1}(I_k) \cup I_1 \right) - PA(k, \tau_k - 1) \}.$

Then the state indices of the nearest neighbors of $\alpha$ are contained in the set $I_B.$ It is not hard to see that this algorithm requires $\sim 3B^2$ simple operations (e.g., lookup, addition/subtraction, min/max) if we store the (fairly small) Pascal matrix. On “interior” states (i.e., states with no zero entries), this algorithm produces the exact neighborhood. However, on “boundary” states (i.e., states with at least one zero entry), some spurious indices are returned. It is not obvious (especially given its structure) how the algorithm might be refined to deal with this problem directly.

However, the spurious indices can themselves be checked efficiently. Given $B$ and $b,$ the following MATLAB code illustrates how to invert the state index:

PA2 = flipud(fliplr(PA));
alpha = zeros(1,B);
ind0 = 0; % init
for j = 1:B
   temp1 = cumsum(PA2(j,(ind0+1):(mb-1)));
   ind1 = max(find(temp1<s));
   if ind1
      temp2 = temp1(ind1);
      s = s - temp2;
      alpha(j) = ind1;
      ind0 = ind0 + ind1;
   end
end

The inversion essentially takes $O(b)$ operations. With this tool in hand, we can trivially establish which state indices are spurious and which are not.

In the next post on this topic, we’ll produce a technique which is actually much faster than any of these for updating state indices in both MATLAB and Java, even after accounting for considerable care in the optimization (such as accounting for the order in which bitshifts are executed).

1 Comment | Equilibrium Networks, Mathematics, Nonrandom bits | Permalink
Posted by eqnets