Happy Thanksgiving

26 November 2009

I'm thankful for seeing truth presented with beauty.

This is a picture to help understand an Anosov flow obtained from the cat map. It’s part of research on a technique we’ve used to analyze network traffic.

Capability of the PRC to conduct cyber warfare and computer network exploitation

23 November 2009

I just finished reading a recent report [pdf] with this title produced for the US-China Economic and Security Review Commission. Though there’s a lot of filler material, it’s pretty good. I’ll spare you the trouble of reading all 88 pages and start with what I thought were the most salient themes covered in the executive summary:

  • Some evidence exists suggesting limited collaboration between individual elite hackers and the Chinese government; however
  • The constant barrage of network penetrations from China (comprising most of what Mandiant calls “the advanced persistent threat“) “is difficult at best without some type of state-sponsorship”.
  • The modus operandi of the penetrations “suggests the existence of a collection management infrastructure”; and
  • PLA CNE aims during a military conflict would be “to delay US deployments and impact combat effectiveness of troops already in theater”.

The PLA’s “Integrated Network Electronic Warfare” doctrine is based on attacking a few carefully selected network nodes controlling C2 and logistics. The INEW doctrine was apparently validated in a 2004 OPFOR exercise when the red force (NB. the Chinese use red to denote themselves) C2 network got pwned within minutes, and it is likely that PRC leadership would authorize preemptive cyberattacks if they think it wouldn’t cross any “red lines”. This preemptive strategy is apparently favored by some in the PLA who view cyber as a “strategic deterrent comparable to nuclear weapons but posessing greater precision, leaving far fewer casualties, and possessing longer range than any weapon in the PLA arsenal“. [emphasis original]

One aspect of this thinking that I think is underappreciated is that the PRC is already deterring the US by its apparent low-level attacks. These attacks demonstrate a capability of someone in no uncertain terms and in fact may be a cornerstone of the PLA’s overall deterrence strategy. In short, if the PLA convinces US leadership that it can (at least) throw a monkey wrench in US deployments, suddenly the PRC has more leverage over Taiwan, where the PLA would need to mount a quick amphibious operation. And because it’s possible to view the Chinese Communist Party’s claim to legitimacy as deriving first of all from its vow to reunite China (i.e., retake the “renegade province” of Taiwan) one day, there is a clear path from the PLA cyber strategy to the foundations of Chinese politics.

The paper goes on to note that “much of China’s contemporary military history reflects a willingness to use force in situations where the PRC was clearly the weaker entity” and suggests that such uses of force were based on forestalling the consequences of an even greater disadvantage in the future. This putative mindset also bears on cyber, particularly through the Taiwan lens. The PLA has concluded that cyber attacks focusing on C2 and logistics would buy it time, and presumably enough time (in its calculations) to achieve its strategic aims during a conflict. This strategy requires laying a foundation, and thus the PRC is presumably penetrating networks: not just for government and industrial espionage, but also to make its central war plan credible.

In practice a lot of the exploitation would consist of throttling encrypted communications and corrupting unencrypted comms, and it is likely that the PLA is deliberately probing the boundaries of what can and cannot be detected by the US. But this generally shouldn’t be conflated with hacktivism or any civilian attacks originating from China, as there’s little reason to believe that the PLA needs or wants anything to do with this sort of thing. While it’s possible that there is some benefit to creating a noisy threat environment, executing precise cyberattacks in the INEW doctrine requires exploitation that can be undermined by hacktivism or civilian (especially amateur) attacks.

The end of the meaty part of the report talks about what’s being done and what should be done. It talks about the ineffectiveness of signature-based IDS/IPS and the promise of network behavior analysis, but also its higher overhead and false alarm rates. This is precisely the sort of thing our software is aimed at mitigating, by combining dynamical network traffic profiles and interactively configurable automated alerts with a framework for low-overhead monitoring and fast drill-down.

DIMACS workshop on designing networks for manageability

14 November 2009

The highlight of the DIMACS workshop on designing networks for manageability for me was Nick Duffield‘s talk on characterizing IP flows at network scale. The basic idea is to use machine learning to identify the flow predicates that best reproduce packet-level classifications. By sampling flows according to a simple dynamical weighting, Duffield et al. demonstrate that this sort of flow classification is accurate (to a few percent, with the misclassifications largely due to overloading of HTTP, e.g., with media over web), scalable (i.e., faster than real-time), versatile (i.e., independent of the particular ML classifier), and stable (over space and time, with a deployment on a separate but similar network producing essentially equivalent results over several months). This work is more recent than related research we’ve cited in our whitepaper “Scalable visual traffic analysis” (on our downloads page) detailing the rationale behind our own traffic aggregation methods.

Much of the workshop (especially its first day) was more focused on current deployment and engineering issues than I would have thought for an overarching focus on “algorithmic foundations of the internet”. Both another mathematician that came with me and I expected to see some work on (or at least suggesting the use of) sparse linear algebra to deal with traffic matrices. I was surprised not to see anyone talk about some kind of agent-based configuration methods for networks–this sort of approach has been used to great effect on hosts.

But there were a number of other talks I found interesting: Aditya Akella from Wisconsin talked about an entropy characterization of “reachability sets” describing packets that can be sent between pairs of routers based on their configurations, and used this to construct a routing complexity measure for networks. Dan Rubenstein from Columbia talked about a “canonical graph” method for efficiently detecting misconfigurations for routing protocols. Iraj Saniee talked about why networks are globally hyperbolic (using a result of Gromov’s well-known work on groups), a conclusion that seems intuitively obvious to me if the existence of a global curvature (bound) is assumed. (Basically a network spreads out if it’s drawn in any reasonable way, and hyperbolic geometry amounts to expansion.)

Mung Chiang from Princeton talked about the results in “Link-State Routing with Hop-by-Hop Forwarding Can Achieve Optimal Traffic Engineering” first presented at INFOCOM 2008. He and coworkers perturb assumptions behind routing protocols to obviate the need for hard optimization problems (i.e., computation of optimal link weights to input to OSPF is NP-hard, but changing OSPF can make the corresponding optimization problem easier). From what I could tell OSPF corresponds to a “zero-temperature” protocol, whereas the improved protocol corresponds to a “finite-temperature” one.

Michael Schapira from Yale and Berkeley talked about game-theoretic and economic perspectives on routing. It is a happy “accident” that the internet is BGP stable (usually, although a notable event where a Pakistani ISP set all its hop counts to 1 some time ago created a routing “black hole”). Although ISPs are selfish, economic considerations tend to result in stability. But that’s not a guarantee. So Schapira and coworkers analyzed the situation and found that “interdomain routing with BGP is a game” in which the ASes are the players, the BGP stable states are pure Nash equilibria, and BGP is the “best response“. I mentioned to him that the “accidental” nature of this stablity is likely due to reciprocity, in that an ISP that discovers one of its neighbors engaging in predatory routing is likely to retaliate in the future. I think the use of economic and game theory is generally a good idea. An emphasis of the economics of cybercrime has developed recently, and understanding the market forces at play here and elsewhere is likely to lead to improvements in the reliability and security of networks.

@ Rutgers

10 November 2009

I will be at the DIMACS workshop on designing networks for manageability at Rutgers for the rest of the week. Looking forward to some good talks…


Solution of second-order matrix difference equations

9 November 2009

While browsing through my notes recently I came across this cute and not-quite trivial, but entirely elementary result. Since it doesn’t seem to be available anywhere else, I present it as blog fodder. (As usual, I will offer $.50 and a Sprite to the first person who provides a usable reference in the event that this result is already known.)

Consider the second-order matrix difference equation

x_{k+1} = Ax_k + \tilde Ax_{k-1}

with x_0, x_1 given. Some algebra shows that (e.g.)

x_2 = (A)x_1 + \tilde A x_0,

x_3 = (A^2 + \tilde A)x_1 + (A) \tilde A x_0,

x_4 = (A^3 + bsp_{1,1}[A, \tilde A])x_1 + (A^2 + \tilde A) \tilde A x_0, etc.

where the bosonic symmetrized product bsp_{j,k}[A, \tilde A] for two “species” of order (j,k) is defined as the sum of all distinguishable products with j occurences of the first species and k of the second (if j or k = 0 then the BSP is a pure power of the nontrivial species).

For example, bsp_{3,2}[A,\tilde A] equals

A A A\tilde A \tilde A + A A\tilde A A \tilde A + A A \tilde A \tilde A A + A\tilde A A A \tilde A + A\tilde A A \tilde A A

+ A \tilde A \tilde A A A + \tilde A A A A \tilde A + \tilde A A A \tilde A A + \tilde A A \tilde A A A + \tilde A \tilde A A A A.

It is not hard to verify that

bsp_{j,k}[A, \tilde A] = A \cdot bsp_{j-1,k} + \tilde A \cdot bsp_{j,k-1}[A, \tilde A]

and more generally for \ell = 0,\dots \min(j,k) that

bsp_{j,k}[A, \tilde A] = \sum_{m=0}^\ell bsp_{\ell-m,m}[A, \tilde A] \cdot bsp_{j-(\ell-m),k-m}[A, \tilde A].

The same algebra that facilitated writing down the first few terms for the difference equation quickly leads to the general solution, viz.

x_k = \left( A^{k-1} + \sum_{j=1}^{(k-1)/2 - 1} bsp_{k-2j-1,j}[A,\tilde A] + \tilde A^{(k-1)/2} \right) x_1

+ \left( A^{k-2} + \sum_{j=1}^{(k-1)/2-1} bsp_{k-2j-2,j}[A, \tilde A] \right) \tilde A x_0

for k odd, and

x_k = \left( A^{k-1} + \sum_{j=1}^{k/2 - 1} bsp_{k-2j-1,j}[A,\tilde A] \right) x_1

+ \left( A^{k-2} + \sum_{j=1}^{k/2-2} bsp_{k-2j-2,j}[A, \tilde A] + \tilde A^{k/2-1} \right) \tilde A x_0

for k even.

I used this to understand what happens when one of the internal states of a classical Bose gas becomes “more fermionic” in the sense that fewer particles can occupy that state, but the microscopic transition probabilities are otherwise unchanged. (The underlying motivation was to apply this to get a handle on the effects of some complex configurations for an older mathematically-oriented network monitoring framework in a tractable traffic regime.) It turns out that this is completely uninteresting unless the remaining “bosonic” states are close to equally likely to occur: in this event you get a slight but also quite counter-intuitive effect on the state distributions. Pseudocolor figures of the energy functions corresponding to these distributions will illustrate:

3 totally bosonic interal states

3 totally bosonic interal states. The distribution is multigeometric, and the energy is affine.

Capping the occupancy of one internal state

Capping the occupancy of one internal state

A more restrictive cap

A more restrictive cap

A "fermionic" internal state

A "fermionic" internal state

Note that the color scales differ for each figure. I think the pictures indicate how surprising the behavior of this (completely classical) “poor man’s exclusion principle” is: the effect is as unexpected as it is slight.

Hopefully posting the main result will save some other folks a head-scratch or two. I’d be interested to know if it’s applied elsewhere.

Random bits

5 November 2009
  • 3He shortage impacting experiments requiring dilution refrigerators…more than a few quantum computing groups use this technology to get to millikelvin temperatures and I remember seeing such a fridge at LPS nearly a decade ago. If it ever became a problem for QC research I imagine NSA and the gang would talk to DoE to get the stuff pipelined to favored (US?) groups, and indeed the government is prioritizing the stuff already, with a lot going towards neutron counters to detect radioactive materials under the DHS umbrella. Good alternatives apparently do not exist for QC work: note that magnetic refrigeration is fundamentally contraindicated for a lot of QC experiments because of, e.g. the big magnetic fields and stuff like the Zeeman effect, even apart from the issue of what temperatures you can reach. And while I have no idea about the capabilities or applicability of dry dilution fridges, in the Physics Today article you can reach via the first link, Bob Richardson is quoted as saying 3He “is irreplaceable. If you want to create temperatures on the order of magnitude of 10 mK, there is no substitute.” (As a more general disclaimer: being on the abstract side even for a theorist when I wear a physics hat means that I don’t claim to say anything correct about experimental physics, but informed comments are always welcome.)

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.

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.

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;
   % the slot n is as follows:
   n = move(k) * ( (B-k)*((B-k)+1)/2 - B + m);   % move(i) = sign(move(i))

 % 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;

 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);
  delta = -sum(temp);
 elseif n2 > 0
  for i = 1:lind
   temp(i) = PA(ind(i),tau(ind(i)-1));
  delta = sum(temp);
  delta = 0;

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


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.

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).


Get every new post delivered to your Inbox.