Flash Worms and congestion

[Stuart Staniford <stuart () silicondefense com>]

Jose Nazario wrote:
> On Fri, 17 Aug 2001, Robert Graham wrote:
>
> > People often ask me "what motivates people to write worms". The above
> > discussions highlights one of the prime motivations. In the scientific
> > community, we don't believe theories and propositions, only
> > experimental evidence. Therefore, to prove that somebody can take down
> > the Internet in 30 seconds, you actually have to do it. Otherwise,
> > nobody really believes you.

...

> i'm really sorry to see these two discussions gaining such blind
> acceptance. it strikes me as obvious that for both the warhol worm and the
> flash worm that people don't understand basic elements of dynamics, such
> as kinetic theory, which includes things like encounter theory and
> propogation. if such analysis were included, done, or even simply
> understood, i think that this whole discussion would have been seen as
> obviously lacking in technical merit, and ripe in hyperbole. in a
> nutshell, think sigmoidal growth patterns, not exponential.

I have a PhD in Physics, which was mostly spent studying dynamical scaling
effects in statistical physics systems.  I have no problem understanding
kinetic or dynamic arguments.  Would you like to be specific as to what you
think will not work about the Flash Worm?  I don't see how sigmoidal growth
applies to a flash worm which can preplan its growth web.  There is no
epidemiological analogy to this and I don't yet see how the paper you
referenced applies.  Nor do epidemiological analogies apply very well to
the Warhol worm, which makes clever use of the fact that the worm RNG would
*not* really be random, but is a deterministic pseudo-RNG.

Robert Graham argued (if I understood) that there will be too many flash
worms and address lists trying to use the Internet backbone at the same
time, and the thing will clog up the network and spread much slower than
claimed.  As he points out, there is no way to tell for sure until someone
builds one.  There is no reliable way to simulate how the Internet responds
to any particular traffic load.  From a scientific standpoint, we don't
really understand the Internet.  My purpose in all this is to provoke
discussion on what could happen, spur better methods of figuring it out,
and what to do about it.  We are not studying some abstract problem of
purely academic interest here - as a community, we're up against the wall.

I think backbone congestion might not be as big a limiting factor as folks
are thinking.  Firstly, I note that moving the address lists around is not
going to clog the Internet.  Because each successive generation of worms
only gets a fraction of the list that its parents worked off, the whole
list only needs to be moved across the net a small integer number of times.

On the face of it, Robert might have a strong point about the flash worms
themselves though: moving all those worms across the backbone would go awry
if they were choosing random places to infect.  However, I think address
locality in the address list *might* save the day.  My back-of-the-envelope
calculations suggest that if the worm takes advantage of this locality (so
each worm instance is trying to infect worms in a subspace of the address
space given to its parent), it might be ok.  The following table shows how
the worm scales with successive generations (for a worm in which each copy
is 5k in size, and infects 10 children for seven generations.  The time I
allow for each generation is sculpted to help the worm get across what I
believe is the bottleneck for it (about generation 5)).  The worm would
probably spread faster if it managed its own timing to minimize congestion.

The columns are:
A: Generation number
B: Number of new copies in this generation
C: Average address space size to be infected (approx)
D: Average address space as a CIDR notation (nearest whole network size)
E: Total Mb of worm movement to create this generation
F: Time allowed (s)
G: Total Mb/s required.

A:      B:      C:      D:      E:      F:      G:
0       1       4.2e9   /0      N/A     N/A     N/A
1       10      4.2e8   /3      0.4     1       0.4
2       100     4.2e7   /7      4       1       4
3       1000    4.2e6   /10     40      1       40
4       10000   4.2e5   /13     400     2       200
5       1.0e5   42000   /17     4000    5       800
6       1.0e6   4200    /20     40000   15      2700
7       2.9e6   420     /23     1.2e5   5       24000

(Note the last generation is only 2.9 million servers (hypothetical
zero-day exploit with total 4 million vulnerable servers)). 

So the Mb/s required at the end look bad (up in the tens of GB/s range
which might reasonably be expected to clog some backbone links, even if the
worm were launched at a quiet time on the Internet).  *However*, by that
stage, the worm is not spreading in the backbone.  There's a boundary at
roughly the /19 stage (others more knowledgeable on routing please correct
me), below which sites are not independent ASs for routing purposes.  So in
the early generations, the worm is spreading across the backbone, but in
the last stages, it has disappeared from the backbone and is just infecting
other machines within local networks (which have much more bandwidth per
site than the backbone).  The /19 boundary is 32768 addresses, so the
problem occurs around generation 5/6 (which is why those ones get a big
slice of time).  That suggests that the flash worm's backbone bandwidth
needs would top out in the very low Gbps in this particular design (spread
between the whole backbone).  Can the net carry that without choking?  I'm
not sure - I would guess it could, given that much of it is big fibers and
the worm load will be pretty evenly distributed.  Big ISP experts please
comment.

By the final generation, the worm is mainly spreading on local networks,
and bandwidth is unlikely to be a concern.

Responding to other points - I agree with Michal Zalewski that networks
with very badly overloaded links will not be affected in the claimed
timeframe.  Such networks will service the worm as badly as they service
their users (though again address locality helps a lot).  Those parts of
the Internet will drag in slowly.

I agree with Bruno Treguier that filtering outbound connections from
servers is an excellent defense against flash worms.  If that precaution
became widespread, the prudent worm writer would need to add duplication
into the spread design to make sure that whole arms of the spread tree were
not cut off.  That would make it slower (though probably still a lot faster
than anything seen to date).

In summary, I believe the concept has taken a few dents, but is basically
intact at this point.

Stuart.

-- 
Stuart Staniford     ---     President     ---     Silicon Defense
         ** Silicon Defense: Technical Support for Snort **
mailto:stuart () silicondefense com  http://www.silicondefense.com/
(707) 445-4355 x 16                           (707) 445-4222 (FAX)

----------------------------------------------------------------------------
This list is provided by the SecurityFocus ARIS analyzer service.
For more information on this free incident handling, management 
and tracking system please see: http://aris.securityfocus.com