IEEE Spectrum December, 2007 - 36

3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]

3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]

% %
%
( (



% %
%
( (

the probability of the system-in this
case, the air in the room-is spread
" "
" "
out over different possible states. To
"
"
% %
% %
take a much simpler example, if you
roll a pair of dice, there are 11 differB^daRT8?PSSaTbb
3TbcX]PcX^]8?PSSaTbb
B^daRT8?PSSaTbb
3TbcX]PcX^]8?PSSaTbb
B^daRT8?PSSaTbb
ent outcomes, some more likely than
3TbcX]PcX^]8?PSSaTbb
"
" "
"
others. The complete array of possibilities and probabilities-only one
B^daRT8?PSSaTbb
way
to get a 2, for example, but five
3TbcX]PcX^]8?PSSaTbb
B^daRT8?PSSaTbb
3TbcX]PcX^]8?PSSaTbb
chances of a 6 and six for a 7-is a
probability distribution. Similarly,
( (
( (
(
(
D each gas molecule in that room has
c
a number of different possible loca% %
tions and speeds, just as the two dice
% %
%
%
( (
each have six possible values.
( (
For the entropy of the distribution
" "
" "
"
of possible outcomes of a single die,
"
%
%
% %
each possible outcome has the same
probability (1/6), so the distribution
3TbcX]PcX^]_^ac
5[^fbXiT
3TbcX]PcX^]_^ac
5[^fbXiT
3TbcX]PcX^]_^ac
5[^fbXiT
is flat. In this case there is nothing
"
" "
"
we can predict about the outcomes
=^a\P[
D]STaPccPRZ
=^a\P[
D]STaPccPRZ
=^a\P[
D]STaPccPRZ
in the distribution. They are com3TbcX]PcX^]_^ac
5[^fbXiT
3TbcX]PcX^]_^ac
pletely random, and the entropy of
5[^fbXiT
FINGERING THE CULPRIT: Examples of network fingerprints during well-behaved traffic (distinct traffic-feature
the distribution is very high-at its
distributions in yellow) and during a worm attack
(distinct traffic-feature
distributions
in orange). Note the changes
=^a\P[
D]STaPccPRZ
=^a\P[
D]STaPccPRZ
maximum, in fact. In the case of two

0]^\P[hSTcTRcTSeXP
inshape of the distributions during malicious activity. The0]^\P[hSTcTRcTSeXP
spikes
in graphs a, C, and d show a change in network

0]^\P[hSTcTRcTSeXP
dice, on the other hand, there are
entropy, as does the flattening of the expected high curveX]U^a\PcX^]T]ca^_h
in b.X]U^a\PcX^]T]ca^_h
X]U^a\PcX^]T]ca^_h
several
possible combinations or out( (
(
comes that have a higher probability
0]^\P[hSTcTRcTSeXP
0]^\P[hSTcTRcTSeXP
 
attack.
Such fluctuations are common; think
of0]^\P[hSTcTRcTSeXP
the
flood of than others. The probability of a 7 is much higher than that
0]^\P[hSTcTRcTSeXP
0]^\P[hSTcTRcTSeXP
bXV]P[_a^RTbbX]V
' '
bXV]P[_a^RTbbX]V
'
X]U^a\PcX^]T]ca^_h
traffic that ensues when a Web page on a site
withbXV]P[_a^RTbbX]V
modest traf- of an 11, for example. So if you roll two dice 25 times, the
X]U^a\PcX^]T]ca^_h
( cited on a popular bulletin-board site such as Slashdot or
fic
results will be less random than if you rolled one die 25 times.
( is
& &
&
Digg.
The problemB^daRT8?
is that such false positives prevent operators
Another way of putting this is that the two-dice system has
0]^\P[hSTcTRcTSeXP
0]^\P[hSTcTRcTSeXP
B^daRT8?
B^daRT8?
from
case-by- less entropy than the one-die system. We can guess more
bXV]P[_a^RTbbX]V
' ' trusting the system, forcing slow and expensive
bXV]P[_a^RTbbX]V
%
%
case
human intervention.
reliably about specific outcomes.
%
To
avoid
false
positives,
security
software
needs
to
moniThat is the principle behind our entropy algorithms. Malicious
&
&
$ $
B^daRT8?
tor
Internet traffic
across the entire network, as opposed to a network anomalies are created by humans, so they must affect
B^daRT8?
$
single
link at a single time, and then correlate all the events the natural "randomness" or entropy that normal traffic has
% %
3TbcX]PcX^]8?
3TbcX]PcX^]8?
#
it
Only
then can a model of the traffic behavior on when left to its own devices. Detecting these shifts in entropy
#detects.
3TbcX]PcX^]8?
#
the$
entire network be created, allowing security algorithms to in turn detects anomalous traffic.
$
focus
Getting back to the gas example, the array of all possible
" " on the structure and composition of the traffic and not
"
just its volume.
locations and speeds creates a probability distribution for the
3TbcX]PcX^]8?
3TbcX]PcX^]8?
# #
3TbcX]PcX^]_^ac
words,
a security system must monitor the actual gas. Because entropy theory is really designed to describe the
! other 3TbcX]PcX^]_^ac
! In
3TbcX]PcX^]_^ac
!
entropy of the network itself.
configuration of a system based on a series of outcome probabili" "
ties,
we can relate high or low entropy to the high or low prob


! outcome.
' ( status
(   ability of
in thermodynamics,
entropy
! ! " "
$ $ %to %changes
! an
" " # #So there's a rough equivalence between
# # refers
& & 'in the
! 3TbcX]PcX^]_^ac
$
%
!
"
"
#
&
'
(

#
3TbcX]PcX^]_^ac
3Phb
! !
quo
of a physical
system-a cup of ice water,
the
gas
in
a
balloon,
thermodynamic
entropy, understood as the probability that the
3Phb
3Phb
a solar system. It is a measure of "molecular disorder." In 1877, molecules in a gas are in a predicted state, and the amount of
Ludwig
Boltzmann visualized a probabilistic way to measure information we have about a system.
 
! " " # # $ $ % % & & ' ' ( (
! ! " " # #
 
the entropy of !an ensemble
of gas molecules. Boltzmann showed
Information
entropy was originally conceived by Claude
3Phb
3Phb
that the ensemble's entropy was proportional to the number Shannon in 1948 to study the amount of information in a transof microscopic states such a gas could occupy. More precisely, mitted message. If the two states of a digital signal, 0 and 1,
entropy is a function of k log p, where k is a constant and p is have exactly the same probability of appearing in the signal,
the probability of a given configuration of molecules.
then our uncertainty about which bit we will receive next is
What exactly is a configuration of molecules? Consider maximized-like throwing a single die that has only two sides.
the temperature of air, which is determined by the average On the other hand, if the 1 has a higher probability of appearing,
speed at which its molecules are moving. The temperature of a then there is slightly less uncertainty about what the next bit
room might be 20 °C, but some molecules will be moving very will be. That is, if the next bit has a greater chance of being a 1,
quickly, for example in the sudden draft when a door opens entropy is reduced. When the information entropy is low, we are
or in the vicinity of a hot burner on a stove. Entropy reflects less ignorant of the details of the digital communication signal
the amount of uncertainty about which exact molecules are being transmitted.
moving at what speed.
Much the same can be said about traffic patterns on the
For a given set of macroscopic quantities, such as tem- Internet. More specifically, an enormous amount of informaperature and volume, entropy measures the degree to which tion can be gleaned by observing traffic flows on a data network.

3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]

b

46

IEEE Spectrum | December 2007 | NA

www.spectrum.ieee.org

bryAN chrIStIE DESIGN

4]ca^_h
4]ca^_h

4]ca^_h
4]ca^_h
4]ca^_h

3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]
3XbcaXQdcX^]3XbcaXQdcX^]

A
http://www.spectrum.ieee.org
Table of Contents for the Digital Edition of IEEE Spectrum December, 2007
