Using signal processing to analyze wireless data traffic.
Experts have long recognized that theoretically it was possible to perform traffic analysis on encrypted packet streams by analyzing the timing of packet arrivals (or transmissions). We report on experiments to realize this possiblity using basic signal processing techniques taken from acoustics to perform traffic analysis on encrypted transmissions over wireless networks. While the work discussed here is preliminary, we are able to demonstrate two very interesting results. First, we can extract timing information, such as round-trip times of TCP connections, from traces of aggregated data traffic. Second, we can determine how data is routed through a network using coherence analysis. These results show that signal processing techniques may prove to be valuable network analysis tools in the future.
INTRODUCTION
Network security experts have long known that examining
even subtle timing information in a tra-c stream could, in
This work was sponsored by the Defense Advanced Re-search
Projects Agency (DARPA) under contract No.
MDA972-01-C-0080. Views and conclusions contained in
this document are those of the authors and should not be
interpreted as representing o-cial policies, either expressed
or implied.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
September 29, 2002, Atlanta, Georgia, USA.
theory, be exploited to achieve eective tra-c analysis [15].
Consider the packet arrival pattern in a TCP
ow. The
pattern is a function of a number of key network parameters
such as round-trip times, send rates, and various TCP
and MAC layer timeouts, as well as the values for all other
ows that share network links with the
ow in question [18].
In theory, therefore, a trace of packet arrivals should be a
possibly noisy composite of all of these patterns.
The problem of extracting characteristics from an otherwise
noisy environment is very similar to the extraction of
features from sonar data. Sonar signals are passed through
sophisticated signal processing lters to identify the signals
that have structure not otherwise visible.
The key idea, then, is to convert packet traces into signals,
and then examine the signals to identify prominent recurring
frequencies and time-periods. With an eective signal
encoding, many well-known frequency analysis techniques
from the signal processing literature can be applied. We use
the frequency analysis techniques to perform tra-c analysis
to reconstruct the network topology or extract network
tra-c parameters.
In this paper, we consider the use of techniques similar to
those employed in acoustics processing to do tra-c analysis
in the presence of noise, whether the noise is inherent in the
tra-c stream or placed there intentionally to camou
age the
interesting tra-c
ows. We take packet traces of streams
and convert them into signals suitable for signal processing.
We then show examples of the kind of information that can
be extracted from the signals using two techniques: Lomb
Periodograms and Coherence.
2. DESIRED RESULTS
There is a wide range of questions that one might ask a
tra-c analysis system to answer. We, however, had particular
types of results in mind when we began our work with
signal processing techniques.
We assumed an environment in which senders seek to
mask or hide their tra-c using techniques such as tunnel-
ing, tra-c aggregation, false tra-c generation, and data
padding. Tunneling hides the original source and ultimate
destination and uses security gateways as the endpoints as
tra-c traverses hostile networks. Tra-c aggregation works
with tunneling under the theory of protection in numbers|
many tra-c
ows all sharing the same tunnel may mask any
one particular
ow's characteristics. If there is not enough
aggregated tra-c to hide individual
ows, false tra-c can be
generated to help hide the tra-c of interest. Data padding
tries to hide information that can be extracted from the
packet length.
We then sought techniques which answered one or more
of the following questions:
Who is talking to whom? Ideally, we would be able
to identify each individual application endpoint. How-
ever, a very useful result would be to determine, for
instance, how many dierent sites are sending their
tra-c over the same IPsec tunnel.
What path is tra-c taking over the network? This
question is of particular interest in wireless networks
(where determining how tra-c is routed is di-cult),
but may also be useful in multi-tunnel environments
such as Onion Routing [20].
What types of application data are being sent? Are
we seeing interactive applications or le transfer applications
or both?
Can we associate transmissions with a particular
For instance, if we determine that ve concurrent
ows
are underway over an IPsec tunnel, can we (with high
probability) determine which IPsec packets are associated
with which
ow? If we could break aggregate
ows into their components, we could potentially use
additional tra-c analysis tools that are tuned to sin-
gle
ows (e.g., the password inference technology developed
by [22]).
3. RELATED WORK
Signal processing has been used to analyze the nature of
aggregate network tra-c, and to develop accurate models
of tra-c consisting of asymptotically large number of
ows,
such as the tra-c on a large intranet, or on the Internet
backbone [4, 2, 16]. It has been shown that aggregate tra-c
on the Internet is self-similar, or shows long-range dependence
[16]. Self-similarity means that no single time-scale
completely captures the rich behavior of the aggregate net-work
tra-c. This observation implies that one needs to
describe the evolution and steady progression of characteristics
(such as the number of active TCP connections or
the distribution of IP packet interarrival times) of aggregate
network tra-c across all scales, because no single scale can
describe all of the
uctuations and variations [2, 9]. This
observation has led to work on long-term memory models,
self-similar models and models with fractal features, where
signal processing tools such as the Wavelet transform are
especially applicable because of their ability to capture frequency
responses at various scales simultaneously [12, 3].
Though the work on the nature of aggregate network trafc
is relevant to the material presented in this paper, the
general focus of our work is not to model aggregate tra-c,
but rather the inverse problem, but to deconstruct the tra-c
into individual
ows, or sessions.
Another related area is that of network tomography [24, 6].
Network tomography is concerned with identifying network
bandwidth, performance and topology by taking measure-
ments, either actively from the network nodes, with their
cooperation [7, 8], or passively using measurements from
preexisting tra-c [23, 5]. Most network tomography work
has also dealt exclusively with network monitoring and inference
of wired networks such as the Internet ([6]). Moreover,
traditional network tomography relies on the ability of the
Network
with Tap
Range of tap p

Figure

1: Wireless network with nodes (n1-n7) and
tap (p)
measuring agents to be able to participate in the commu-
nications, possibly at the network layer. The participation
may either be in the form of the ability to take measure-
ments, or even the ability to explicitly transmit packets to
other nodes in the network.
However, in some scenarios, such as in adversarial wireless
networks, we cannot assume that the measuring agents can
participate on the network. Indeed, in many military do-
mains, the nature of the network protocols deployed on the
adversary's network may not even be known. As a result,
the work in this paper makes far more conservative assumptions
about what a measuring agent may do. Our aim is to
discover network topology purely from the raw transmission
traces.
4. NETWORK AND TAP MODEL
Our goal in this work is to make the tra-c analysis techniques
broadly applicable. To that end, we make as few
assumptions about the network and the observed tra-c as
possible.
We assume that there is some network over which discrete
pieces of data are transmitted by senders. The transmission
of these pieces of data cause network events. An event
is individually detectable or distinguishable|that is, a listening
device can tell when an event is over and will not
combine concurrent events from multiple senders into one
event. It is important to note that an event need not perfectly
correspond to a data packet. An event may represent
the transmission of part of a packet (e.g., a frequency hop),
or multiple packets (say two packets contained in a single
wireless burst transmission).
A sender in this model is the device that caused the event.
The sender is not necessarily the device that actually originated
the data that caused the event.
We assume that there are one or more tra-c taps within
the network. A tap seeks to observe tra-c on as much of the
network as is possible from the tap's location. This broad
denition is chosen to accommodate the dierence between
a tap on a wire or ber, where the tap is restricted to data
placed on the wire, and a wireless tap, which is observing
some (potentially very large) fraction of the wireless spec-
trum, and thus may see transmissions from a wide range of
sources. This range is shown in Figure 1.
A tap collects event information in a trace. For most of
the work discussed in this paper, the trace is assumed to
contain only the time the event was seen and the identity of
the sender of the event.
The concept of identity used here is intentionally vague|
the identity could be the IP address of an IPsec gateway, the
location of a radio transmitter, the upstream or downstream
transmitter on a point-to-point link, or simply \the same
sender as the one that sent these other events." The identity
of a sender must be unique among all senders known to
the tap (or set of cooperating taps); we assume the data
collection process is setting identity and maintaining the
uniqueness property.
We assume each tap has access to a clock used to record
when when each event was heard. In a wireless network, this
time of detection may be the middle of the transmission due
to propagation or other eects such a frequency hopping.
The granularity of the clock used to record time must be
su-ciently small that two consecutive events on the same
channel will be given dierent timestamps.
We note that there is no assumption about knowledge of
the length of the event, the destination of the data corresponding
to the event, signal strength, or any insight into
the contents of the event, even though, in many cases, this
and other additional information may be available. How
this additional information might be used is discussed in
later sections.
A tap may not capture all tra-c. For instance, reception
on a wireless network may be variable due to environment,
noise, transmission power, or jamming such that a tap is
unable to observe some transmissions. Furthermore, a tap
may occasionally make an error and mistakenly believe it
has seen an event when no event was sent (e.g., due to noise
on the wireless network).
There are some other characteristics of taps worth commenting
on:
Multiple taps: Multiple taps may be used together to
develop a more complete picture of the network tra-c.
Resource limitations: A tap (or a network of taps)
must be capable of storing all the transmissions it detects
for a su-cient amount of time for analysis to take place.
For example, the round-trip time of a transport layer
ow
cannot be determined if the history that can be stored at
taps is less than one round-trip time. The total volume of
data that must be stored depends on the capacity of the
channel and the maximum round-trip time of
ows seen on
the channel.
In the wireless environment, a tap may also be limited
by the amount of spectrum it can examine in any given
time. Indeed the spectrum range covered by the tap may be
dierent from the spectrum range used by the sender, with
the result that some events are not observed.
Mobility: Nodes may move around the network. Thus
senders may move in and out of the range of one or more
taps. We assume that senders typically dwell in the range
of one or more taps long enough for events to be heard, and
the senders identied and recorded.
Analysis
Signal
Encoding
Signal
Processing
Tap
Network

Figure

2: Model of Analysis
5. A NOTE ABOUT
Even though the techniques described in this paper have
all been tested on real wireless data, the examples presented
here all use simulated network data. We chose to present
simulated data for two reasons.
The rst reason is that, so far, we have not had the equipment
to collect the kinds of wireless traces we need. Rather,
we have taken existing traces and attempted to adapt them.
So, for instance, one wireless data set we have used is a tcpdump
trace of the wireless data and lacks the MAC layer
ACK and RTS signals, and has deleted any errored pack-
ets. As a result, some of the key frequency information is
lost. (One paradoxical consequence is that real data actually
makes some results look better than they should because
confusing signals have been edited from the traces).
The second reason is that no real trace, so far, has come
with all the required \ground truth" data needed to cross-check
results. So real data often involves making guesses
about the meaning of results.
Simulation data does not suer these limitations. We have
all the signals and can present them in all their complexity.
And if we cannot explain a result from a simulation, it represents
a serious challenge in interpretation, not the lack of
the necessary supporting data. So, for the purposes of clear
exposition, we have used simulation data.
6. SIGNAL ENCODING

Figure

shows our tra-c analysis processing model. Trafc
is captured from the network via taps. The traces from
the taps are encoded into signals. The signals are then pro-
cessed, using various signal processing techniques and the
nal result is analyzed. This is precisely the same model of
analysis used in signal processing of acoustic data.
The rst step in producing a signal is acquiring the sam-
ples. Signal processing makes a distinction between whether
the samples are gathered by a uniform or non-uniform sampling
process. The type of signal produced must be appropriate
for the target signal processing algorithm. With data
tra-c, the major concern is that the sampling frequency
allow the separation of meaningful events. We assume the
sampling process meets event separation criterion. Given
separation, we can convert a trace into an event stream that
is appropriate for any target signal processing algorithm.
The trace represents a set of discrete events x(n), logged
at times tn , for is the number of
events in the trace. The general approach to producing a
uniformly sampled signal representing the time of arrival of
event x(n) is to pick an appropriate time quantization interval
into increments at that quantization mT ,
where m is a integer, and then place a marker in the bin
representing the nearest time to tn when the event x(n) was
detected. That is, is the quantization
function such as the
oor or the ceiling function. The
Time Duration T R O D Description
3.587807
3.588986

Figure

3: Excerpt of trace capturing transmissions
from four nodes of Figure 5. There is an FTP
ow
between nodes 0 and 3 and a pair of UDP
ows
between nodes 1 and 3. All tra-c is routed through
node 2. The Time and Duration of the transmissions,
and the transmitter (T) node id, are captured by
the tap. The extra information within (/*/) is
listed here purely to give the reader an insight into
the trace dynamics, and is not known to or captured
by the tap. The extra info includes the receiver
id. (R), the global origin (O) and destination (D)
of the packet contained in this transmission, and a
Description of the packet contents.
Nyquist limit provides the means for determining the size of
the time increment; we aim to minimize the number of bins
and yet meet the Nyquist limit. This process is known as
resampling. Due to the errors introduced by quantizing the
time of arrival, some information contained in x(n) may be
lost in the resultant encoding.
To produce a non-uniformly sampled signal representing
the time of arrival of events x(n), markers are placed only
at times tn . Since there is no resampling, no quantization
error is introduced into the encoded signal.
The trace may be rich with information that can be encoded
as a signal. Consider a function g as the encoding
function. For a binary, or impulse, representation of time
of arrival, g(mT ) is 1 when
A sign encoding function (+1; 1) can be used to indicate
which end of a wire the signal came from. A weighted encoding
function can represent the transmission duration or
signal strength. Additional parameters for each event can be
represented in the signal by rening the encoding function
g.
When multiple events are occurring simultaneously (i.e.,
within the same sample period) and would be set to the same
time bin mT , we jitter the time of the con
icting events into
empty adjacent sample times in order to keep data from
being obscured.
While it is possible to encode the events of multiple senders
into a single signal, better signal processing results usually
come when one generates a separate signal representation
for each sender. Recall that the sender is the most recent
transmitter of the data that caused the event|it is not the
originator of the data. Thus, a single sender's trace may
contain the data of multiple
ows (e.g., when the sender is a
router). The idea here is simply to split the traces as much
as possible before processing.
An example of a trace captured by a tap monitoring transmissions
in a wireless network is shown in Figure 3. As discussed
earlier, a duration-weighted sign encoding function
can be used to encode the captured transmissions into a
signal appropriate for signal processing. Figure 4 shows an
encoding of transmissions from nodes 2 and 3, which can be
used to analyze communications that span these nodes.
Amplitude
Time

Figure

4: A non-uniformly sampled signal representation
of the trace in Figure 3. f = (1duration) for
transmissions of node 2 and
transmissions from node 3.
7. SIGNAL PROCESSING AND ANALYSIS
Given an encoded signal, we can make use of a wide range
of signal processing algorithms to try to extract tra-c in-
formation. In this section, we will describe some signal processing
techniques which we have found useful for trace anal-
ysis. 1
Most spectral processing techniques use the standard Discrete
Fourier Transform (DFT) to compute the spectral power
densities. The DFT requires that the signal be uniformly
sampled.
The DFT of a uniformly sampled signal x(n) (with
q(tN )=T samples) provides an M-point discrete spectrum
1 Unless otherwise noted, more information about these techniques
can be found in signal processing textbooks such as
x(n)e j2kn=M
DFT fx(n)g (1)
is the M-point DFT. The values of k correspond to M
equally spaced frequency bins of the sampling frequency of
x.
The resulting spectrum X(k) is a vector of complex num-
bers. The peak values in X(k) correspond to frequencies
of event times of arrival. The magnitudes of the peaks are
proportional to the product of how often the arrival pattern
occurs and the weighting of the data performed by encoding
the signal. The phase of the peaks shows information on the
relative phases between arrival patterns. The Fast Fourier
Transform (FFT) is a computationally e-cient decomposition
of Equation 1, made possible when M is a product of
powers of small integers, though powers of two are the most
commonly used.
If the characteristics of the signal (due to variations in the
tra-c
vary markedly during the DFT analysis, then
the resulting spectrum can be misleading, since the resolved
peaks may be present for only part of the time in the signal.
Also, it is often the case with signal representations that the
spectral content contains many harmonically related peaks. 2
In these situations, the spectral peaks of interest may not
be readily visible due to the overlap of the various harmonic
peaks, causing the spectra to look like noise. Thus, the
examination of the spectrum given by the DFT can provide
visualization of
ows in the form of characteristic peaks, the
DFT, when used alone, can give spectra that are insu-cient
for further detailed analysis. In the remainder of this section
we describe signal processing techniques which address this
deciency.
Periodograms, or Power Spectral Density (PSD) estima-
tors, are spectral analysis techniques that are used to compute
and plot the signal power (or spectral density) at various
frequencies. A periodogram can be examined to identify
those frequencies that have high power, that is, power
above a certain predetermined threshold. As a consequence,
periodograms are useful for identifying important or key fre-
quencies, even in the absence of any prior knowledge about
the nature of the signal.
Another important characteristic of periodogram techniques
is that they work very well even in the presence of noise or
interference. This is fortunate for analyzing network tra-c
because a
ow of interest is often embedded in an aggregation
of other tra-c. In this case, from the perspective
of the
ow of interest, all other tra-c contributes to the
interference.
When signals are expected to be noisy (i.e., they have
a high degree of randomness associated with them due to
corruption by noise or consisting of random processes them-
selves), conventional DFT/FFT processing does not provide
a good unbiased estimate of the signal power spectrum. 3
2 For example, the spectral content of a square pulse is the
fundamental frequency of the pulse, plus all the odd numbered
harmonics.
3 That is, processing larger sets of data does not make the
A better estimate of the signal periodogram, Pxx(k), may
be obtained with the Welch Averaged Periodogram [25, 14]
which utilizes averaging in order to reduce the in
uence of
noise. It uses windowing to account for the aperiodic nature
of the signal. The periodogram is generated by averaging
the power of K separate spectra X (r)
computed over K
dierent segments of the data, each of length
KU
(2)
where
where the windowed data xr (n) is the r th windowed segment
of x(n), w(n) is a windowing function 4 used to reduce
artifacts caused by the abrupt changes at the endpoints of
the window, and U is the normalized window power. The
value of the number of samples L within each segment depends
on the window function, w(n). The result can be
interpreted as a decomposition of the signal into a set of discrete
sinusoids (at frequencies 2k=M) and an estimation of
the average contribution (or power) of each one. While the
spectrum, X(k), obtained by the DFT was complex valued,
the peaks in Pxx(k) are real valued, they also correspond to
frequencies of event times of arrival. Similar to the DFT, the
power of the peaks is proportional to the product of how often
the arrival pattern occurs and the weighting of the data
performed by encoding the signal. In addition to this similarity
to the DFT, the Welch Averaged Periodogram permits
the computation of condence bounds on the peaks.
7.1 Flow Analysis using Lomb Periodograms
Recall that DFT-based periodograms require uniform sam-
ples, which requires resampling of the original trace and may
lead to loss of information. In this section, we discuss a technique
which overcomes this hurdle.
Packet arrivals in computer networks are inherently unevenly
spaced, naturally resulting in a signal encoding that
is non-uniformly sampled. Lomb, Scargle, Barning, Vancek
[17, 19] developed a spectral analysis technique specically
designed for data that is non-uniformly sampled. The Lomb
method computes the periodogram by evaluating data only
at the times for which a measurement is available. Although
the Lomb method is computationally more complex than the
DFT (O(NlogN)), this property makes it an especially appropriate
PSD estimator for examining event arrival traces.
Moreover, since only the event arrivals need to be stored in
the time series (no resampling, as discussed in Section 6, is
required), the Lomb method has an added advantage that
the input data is sparse and consumes less storage memory.
answer converge to a good result.
4 The term windowing or shading refers to the time-wise
multiplication of the data stream x(n) by a smoothing function
w(n). Many typical smoothing functions are used (e.g.,
Hamming, Kaiser-Bessel, Taylor), all of which reduce spectral
background noise and clutter levels at the cost of some
smearing of the peak energies in the frequency domain.
So, at the cost of increased CPU requirements, but decreased
memory requirements, the Lomb method oers all the attractions
of periodograms, such as condence intervals for
various peaks, with the added advantage of a more precise
power density computations for non-uniform time series.
The Lomb method estimates a power spectrum for N
points of data at any arbitrary angular frequencies. The
power density (PN ) at a frequency f Hz or angular frequency
Where
hn
sin 2!tn
Also, hn are the N unevenly spaced
samples of the signal at times tn . The Lomb periodogram
is equivalent to least-squares tting a sinusoid of frequency
! to the given unevenly spaced data. In case tn are evenly
spaced (i.e., the signal is uniformly sampled), the Lomb periodogram
reduces to the standard squared Fourier transform.
Note that while analyzing network traces, it may sometimes
be more convenient to work with time periods rather
than angular frequencies. We will see this in the next sec-
tion, where we take specic networks and illustrate the use
of the Lomb method. The power density at a time period
X can be easily computed since it is simply equal to
7.1.1 Wireless Network Analysis
In wireless networks, we model taps as nodes that can detect
transmissions above a certain signal strength threshold,
and uniquely identify (and tag) each signal reception with
its transmitting node. Consequently, a tap may only hear a
subset of nodes in the network. Moreover, we do not assume
that the taps participate (or, indeed, even know about the
MAC layer) in the network. They only detect the lowest
level physical transmissions.
Consider the four node wireless network in Figure 5. We
simulated this network in ns-2, with an 802.11b MAC layer,
and a 2Mb/s transmission bandwidth (we used the ns-2 settings
for Lucent WaveLAN). The nodes were deliberately
placed in a conguration so that any tra-c from nodes 0 or
1 to node 3 has to be routed through node 2, because node
3 is too far away and cannot directly hear nodes 0 and 1.
Therefore, the wireless link between nodes 2 and 3 is the
bottleneck link. Three
ows were set up: One FTP
ow
from node 0 ! 3, one CBR
ow from node 1 ! 3 and one
CBR
ow from 3 ! 1.
We then place the tap p in the network such that it can
only detect transmissions from nodes 0 and 3. The tap does
send ms
CBR 3->1:
send ms
CBR 1->3:
rttvar (mean
ms
FTP 0->3:
Probe only sees transmissions
from nodes 0 (+1) and node 3 (-1)
signal captured:
CBR
1->3
CBR
(Acks for

Figure

5: A wireless network with one FTP
ow
and two CBR
ows. The network is congured to
route tra-c from nodes 0 and 1 to node 3 (and vice
versa) via node 2. The tap is placed such that it
only hears transmissions from nodes 0 and 3, and
creates a simple signal encoding.
not hear any transmission from nodes 1 and 2 because node
1 is too far away, and node 2 is both far away and has low
signal strength.
A simple signal encoding is created from the trace by assigning
the amplitude +1 to all receptions from node 0, and
1 to all receptions from node 3. A small snapshot of this
signal is shown in the box in Figure 5.
This simulation was run in ns-2 for 300 seconds using the
Dynamic Source Routing (DSR) protocol [13] to maintain
connectivity in the ad hoc network. The CBR
ow from 1 !
3 was congured to send packets of 1024 bytes each, at an
average transmission rate of one packet every 173 ms. The
CBR
ow from 3 ! 1 was also congured to send packets
of 1024 bytes each, but at a rate of one packet every 75
ms. The statistics reported by ns-2 for the FTP
round trip time (rtt ) of 371 ms, with a mean deviation
(rttvar ) of 92.5 ms.
It should be noted that the trace produced by the tap in
this network is complex and noisier than the trace would
be on a wired network. This dierence is not simply due
to transmission media, but in the kinds of support tra-c
used in wireless networks. For instance, the events received
at the tap include the DSR routing updates, which do not
correspond to any end-to-end
ow. Furthermore, due to
the nature of 802.11b, the packet transmissions are interspersed
with the corresponding RTS, CTS and MAC layer
transmissions [1]. Also, due to the nature of wireless
networks, and the hidden-node problem, there are collisions
which are resolved at the MAC layer, leading to retrans-
missions. Finally, there is interference in the signal from
transmissions at node 3 that are not intended for node 1.
We are interested in identifying the characteristics of the
various
ows, so after collecting the signal from tap p, we
compute the Lomb periodogram of that signal. Inspection
of the Lomb periodogram plot shown in Figure 6 reveals
that its three most prominent peaks correspond to each of
Spectral
Power
Time Period (milliseconds)ms
FTP (0->3) Round Trip Timems
CBR (1->3) Send Ratems
CBR (3->1) Send Rate

Figure

The Lomb periodogram for the wireless
network of Figure 5 reveals all three
ows involving
four nodes, even though the tap only hears nodes
0 and 3. The 0 ! 3 FTP is identied by the peaks
spread near its RTT (328.85 ms).
the three
ows.
Both CBR
ows are revealed by the peaks very close to
their transmission rates. The transmission intervals for CBR
3 from Figure 5 were 75 ms and 173
ms, respectively, whereas the peaks are found at 75.01 ms
and 173.08 ms, respectively.
The FTP
ow from 0 ! 3 can be identied by the peaks
spread around 328.85 ms, which correspond to the round-trip
time for this TCP
ow. This value is well within the
standard deviation of the measured round-trip time (the deviation
and RTT were reported to be 92.5 ms and 371 ms
by ns-2).
Observe that the plot is able to show the eects of both
CBR
ows, even though it does not receive any signal from
node 1, an end-point for both these
ows. The fact that we
can see CBR from 1 ! 3 is even more interesting because
not only can the tap not hear the transmissions of node 1
(or node 2), but there is no way for the tap to know when
node 3 receives a packet either. So eectively, the tap never
hears any transmission directly related to this CBR
its peak is one of the most prominent peaks. 5
This example is a good illustration of the Lomb peri-
odogram's utility in extracting useful information for detection
of conversations even in complex wireless networks
where the trace may be quite noisy (due to the routing traf-
c, for example), incomplete (due to the limited range of
taps), and complex (due to an inherently complex MAC
layer transmissions). In this example, the Lomb method is
able to identify the key timing parameters of the
ows, and
thus reveal all three IP
ows.
7.1.2 Discussion
This example shows the promise of Lomb's technique for
revealing key
ow information, even when the signal did not
explicitly contain data from transmissions related to some of
5 We speculate that this relationship is caused by a form of
imprinting. The CBR
ow from 1 ! 3 shares part of its
path with the FTP and the interactions between the FTP
data and the CBR
ow causes the timing of the CBR
ow
to be re
ected in the FTP acknowledgements.
those
ows. Work with other traces, some simulated, some
real, have conrmed this promise.
At the same time, there are challenges in using Lomb.
The rst major challenge is nding ways to explain each
peak in a graph. Even with simulated tra-c (where presumably
we know or can nd all the time constants), there
are peaks that sometimes elude understanding (such as the
small peaks at 100 and 66 ms in Figure 6). Also, we have
found that the Lomb periodogram technique identies dier-
ent network characteristics for dierent networks. It is able
to identify the round-trip times of the FTP
ow in

Figure

6, but in a similar experiment using a wired network high-lighted
the transmission intervals rather than the round-trip
time. For our purposes, the Lomb periodogram is not yet a
rened tool.
Finally, the biggest challenge is to scale the Lomb periodogram
method to larger networks. We have applied this
technique to some large publicly available tcpdump traces,
and found that even though there are some prominent peaks,
it is di-cult to identify the key timings that they represent.
Moreover, despite the fact that Lomb periodogram works
well in the presence of noise, we have found that the noise in
large network traces can overwhelm this method by reducing
the condence in prominent peaks. Developing techniques
to further reduce the eects of noise in large networks is an
important challenge for reducing this approach to practice.
7.2 Tracking Network Dynamics using Time
Varying Spectra
Until now, we have limited ourselves to collecting the entire
trace for the full duration of a
ow, and analyzing the
aggregate signal using a one-dimensional (description of the
signal only as a function of the frequency) representation of
its spectra. However, these spectral techniques (e.g., Lomb
Periodogram), are only valid when the underlying process
that generated the signal is wide sense stationary, 6 i.e., its
frequency content does not change with time. These techniques
are still valuable when the signal statistics vary slowly
enough such that they are nominally constant over an observation
period which is long enough to generate good es-
timates. That is why it was appropriate to use Lomb periodograms
for the analysis of round-trip times or the send
rates of
ows on networks whose nodes are static. On these
networks (which includes most of the Internet), the RTT and
mean send rates remain rates remain stable and relatively
constant over the duration of individual
ows.
However, in many scenarios, the network and
ows are
more dynamic in nature. For example, in mobile ad hoc
networks, the nodes are mobile and the topology changes
with time. Or, even in a static network, the objective may
be to analyze the evolution of
ows over time (to detect TCP
stabilization times etc. Such scenarios where the network
or the
ow characteristics dynamically change require techniques
that can track changes in the spectra with time {
or can develop a time-varying spectral representation of the
signal. Such two-dimensional representations permit a description
of the signal characteristics that involves both time
and frequency, and provide an indication of the specic times
6 Wide sense stationary (WSS) usually requires that the
mean and autocorrelation (and in the case of multiple
streams, cross correlation) functions of the process are constant
with respect to the the time and duration of observation

at which certain spectral components of the signal are observed

whose spectra changes with time, are known as
nonstationary processes [10]. Many (linear and quadratic)
techniques have been developed for nonstationary signal pro-
cessing, but of special importance for us are two linear tech-
niques: (1) the Short Term Fourier Transform, or STFT
[11], which is a natural extension of the Fourier transform
that employs shifting temporal windows to divide a non-stationary
signal into components over which stationarity
can be assumed, and (2) the Wavelet Transform [21], which
is more complex than the STFT, but oers better time-frequency
resolution by trading
resolution and vice versa.
In this paper, we use temporal windows, similar to those
in the STFT. In Section 7.3, we will use the windowing technique
to track topology changes in a network with mobile
nodes. Our general approach for analyzing dynamic networks
using windowing is as follows.
The tap trace is divided up into temporal windows of
a constant duration and spectral estimates are computed
for each window. Often the windows are overlapped by
a xed percentage to ensure smooth boundary transitions
from one window to the next. The output vector from
spectral analysis (which can be cepstrum, coherences, cross-
spectral-densities, or indeed power spectral densities computed
using Lomb Periodograms) of each window is stacked
together as columns of a two dimensional matrix, forming an
image with time along the horizontal axis and the estimated
parameter (such as amplitude or spectral density) along the
other. This kind of representation is often known as a spec-
trogram. In the simplest form, a spectrogram is simply the
squared modulus of the Short Term Fourier Transform of a
nonstationary signal. Since spectrogram eectively plot the
spectra, as it varies in time, it is useful for discovering variations
in
ow and network characteristics in a dynamically
evolving tra-c scenario.
Recall that the Lomb method, which is relatively new,
permits the analysis of non-uniformly sampled data, at the
cost of increased computational complexity. However, there
are a multitude of classical signal processing techniques that
are applicable to uniformly sampled data only. In order
to exploit these techniques we will use uniformly sampled
signals to analyze the time-varying spectra. 7
7.3 Link and Path Discovery using Coherence
The previous sections focused upon the analysis of one
signal stream. We now move to the analysis of signals from
multiple trace les in order to relate transmissions in one
location with those at another. We will use the windowing
technique to capture variations in these signal relationships.
The idea is to look for relationships between time windows
at dierent locations or between time windows for tra-c
from dierent sources. For instance, if we nd a strong relationship
between a time window for source 1 and a slightly
later time window from source 2, we can infer that some
of the tra-c from source 1 is being forwarded through or
acknowledged by source 2. Expressed in signal processing
terms, if there is enough periodicity in a trace le to show
spectral peaks, and if the transmissions of one source are
forwarded or answered by another source at some layer of
7 We are currently exploring ways to extend Lomb's method
to analyze time-varying spectra using windows.
the network (such as with ACKs in TCP or via the MAC
protocols in a wireless network), then we can compute (us-
ing a classical signal processing technique called coherence)
the degree that the two dierent signals are related.
For the rest of this section, we use time-varying windows
and coherence to identify all active (one-hop, or MAC layer)
links between the various nodes in a network. Moreover, we
will now work in a mobile ad hoc wireless network. Such ad
hoc networks require our technique to recognize that links
are transient because the nodes are mobile.
The multiple input extension of the periodogram in Equation
2 is Cross Spectral Density (CSD) which is essentially
the cross spectrum (the spectrum of the cross correlation)
Pxy (k) of two random sequences. The formula is
KU
Y (r)
denotes the complex conjugate. The resulting
CSD shows how much the two spectra X(k) and Y (k) have
in common. If two signals are randomly varying together
with components at similar frequencies, and stay in phase for
a statistically signicant amount of time, then their CSD will
show peak at the appropriate frequencies. Two independent
signals do not give peaks. CSD may be complex valued, so
the magnitude of the CSD is generally used in the same way
the magnitude of the PSD is.
One can compute a version of the CSD known as coher-
ence, whose value is mapped between 0 and 1. The formula
is
This formulation is useful in situations where the typical
dynamic range of spectra would cause scaling problems, such
as in automated detection processing. Since the coherence
is nicely bounded, it allows easier automation. However, as
we lose the absolute levels of Pxy (k), Pxx(k), and Pyy(k), it
should still be used in conjunction with the CSD rather than
as a replacement. CSD and coherence may also be presented
in gram form in a manner identical to that discussed above.
CSD and coherence answer the question: what was the
power of the conversation between any two sources in the
network during a certain time-slice? Furthermore, if we encode
transmission durations to amplitude, then the power
of the peaks would give a sense of the bandwidth of the
communications between the nodes. We have found this
technique quite useful for discovering routing topology in
wireless networks.
First we demonstrate the Coherence technique without
the added complication of mobility. Figure 7 shows the results
of analyzing seconds of trace data for coherence.
The data is taken from a simulated wireless network with a
topology similar to Figure 5. Two simple
ows are present.
An FTP from 0 ! 3 by way of node 2, and a CBR from
by way of node 2. The gure shows one coherence
plot for each pair of nodes in the lower diagonal of the
matrix of nodes. Each coherence plot is labeled Coherencexy
and shows the coherence between nodes x and y. Plots with
visible peaks indicate stronger coherence, which suggests
two-way transactions (hence a conversation). Furthermore,
the shapes of the peaks also provides information which may
allow us to dierentiate the types of data transfers (FTP vs.
Coherence
CBR Source
Coherence 20
Coherence 21
CBR
Coherence
FTP Endpoints
Coherence 31 Coherence
CBR

Figure

7: Coherence Between Nodes in the Wireless
Network from Figure 5.
CBR, etc.
One can see that strong peaks occur between node pairs
2 and 0, 2 and 1, 3 and 0, and 3 and 2. The links 2
are carrying the FTP, and links 2
are carrying the CBR. The peaks in Coheregram 30 do not
correspond to a link, but instead are due to the fact that
the FTP transfer between nodes 0 and 3 cause those nodes
to interact in a strongly periodic pattern due to the ACK
feedback of TCP. There is a lack of coherence between nodes
because they do not share any information. We
speculate that the coherence between nodes 3 and 1 is due
to the tra-c periodicity pattern of the FTP being aected
by the UDP transmission, but we have not conrmed this.
Next, we demonstrate our solution to the problem of not
only discovering the topology, but tracking topology and
routing changes, in mobile networks.

Figure

8 shows a coheregram generated by analyzing another
seconds of trace data taken from the same wireless
network in Figure 5, except that now node 1 moves around
node 2 at a constant speed (while it moves), stopping for
a short duration rst between nodes 0 and 2, and then between
nodes 2 and 3. This motion causes rerouting to occur
twice, rst at 14 seconds into the run, and again at 25.5
seconds. Initially, tra-c from 1 ! 3 is routed through node
2, until at time 14 seconds, node 1 gets close enough to node
3 to route directly. This continues until 25.5 seconds, when
node 1 has circled far enough away from node 3 to resume
routing through node 2.
Coherence spectra were computed for each 512 ms interval
and displayed as a two-dimensional time-frequency gram
where intensity is proportional to power at that time and
frequency low level to black = high level). The
result is a gram plot for each pair of nodes (laid out exactly
as in Figure 7). When the coherence remains similar
from one interval to the next, peaks resolve as horizontal
lines in the plot. However, when the network reroutes at
14 seconds and node 1 begins to communicate directly with
node 3, the coherence peaks change visibly in Coheregram 21
and Coheregram 31 . At 25.5 seconds, they coherence peaks

Figure

8: Coheregrams Showing Time Varying
Coherence Between Nodes in the Wireless Net-work
from Figure 5, due to a mobile node 1.
Link/Routing changes are observed at 14 seconds
and 25.5 seconds.
change visibly, and remain such until the network resume
their old form. Such a change could be detected by automated
means.
8. CONCLUSIONS
There's something very tantalizing about nding a new
way to look at data tra-c. For instance, the experience
of seeing coherence techniques map the path a
ow's tra-c
took through the network, and to recognize changing communication
patterns in a mobile ad-hoc network was extremely
exciting.
We started this paper with four questions we hoped signal
processing techniques might address.
Clearly the coherence techniques give us insights into who
is talking to whom, and the paths tra-c take. We are currently
working on rening these techniques to larger and
more complex networks.
The Lomb periodogram gives us some insight into determining
how many
ows are traveling over a particular path:
the peaks in the periodogram can be used to reveal features
of individual
ows. But we are a long way from using that
data to determine which particular applications are in use
or which individual events correspond to a particular
ow.
At the same time the results reported in this paper obviously
raise more questions than they answer. There are a
number of opportunities to substantially rene algorithms,
including:
How best to encode a trace as a signal? Encoding
is a key part of the analysis process and yet we've
only just begun to explore the issues. It seems likely
that dierent encodings will give dierent results, and
perhaps highlight dierent aspects of a trace.
How to separate wheat from cha in the results? The
Lomb periodogram is a good example. Even for modest
amounts of tra-c, it reveals a number of heavily
used frequencies. How do we identify the frequencies
we most care about?
As mentioned in Section 7.2, often network tra-c produces
nonstationary processes, which require specialized
techniques such as windowing and the Welch Average
Periodogram described in Section 7. However,
even these techniques also work well only if the signal
statistics vary slowly enough, at least within the
observation time covered by the window. Another alternative
(which we are exploring) is to develop techniques
which do not require the signal to be wide sense
stationary at any time scale. Wavelets analysis is a relatively
new tool in signal processing, developed only in
1980s [21], and they are applicable to completely non-stationary
signals. We are exploring the use of such
techniques for discovering time varying network properties

Finally, given that these techniques are beginning to
work, what can we do to hide tra-c patterns from
them? What (possibly new) techniques should we use
to make tra-c less vulnerable to this sort of tra-c
analysis?

ACKNOWLEDGMENTS

We are indebted to Steve Kent, Greg Troxel, Chip Elliott,
Alex Snoeren, and Paul Kolodzy for their suggestions for
directions and reviews of early drafts.
9.



--R

IEEE Std 802.11b
Multiscale nature of network tra-c
Wavelet analysis of long-range-dependent tra-c

Maximum likelihood network topology identi
Internet tomography.
Trajectory sampling for direct tra-c observation
Multicast inference of packet delay variance at interior network links.
The changing nature of network tra-c: Scaling phenomena
Communication Systems
Linear and quadratic time-frequency signal representations

Dynamic source routing in ad hoc wireless networks.
Modern Spectral Estimation: Theory and Application.

On the self-similar nature of Ethernet tra-c

A duality model of tcp ow controls.
Numerical Recipes in C
Anonymous connections and onion routing.
IEEE Signal Processing Magazine 8
Timing analysis of keystrokes and timing attacks on ssh.
Passive unicast network tomography based on tcp monitoring.
Network tomography: estimating source-destination tra-c intensities from link data
The use of fast fourier transform for estimation of power spectra: A method based on time averaging over short
--TR
On the self-similar nature of Ethernet traffic
The changing nature of network traffic
Trajectory sampling for direct traffic observation
A non-instrusive, wavelet-based approach to detecting network performance problems
Maximum likelihood network topology identification from edge-based unicast measurements
Encryption-based protection for interactive user/computer communication

--CTR
Collaborative detection and filtering of shrew DDoS attacks using spectral analysis, Journal of Parallel and Distributed Computing, v.66 n.9, p.1137-1151, September 2006
Alefiya Hussain , John Heidemann , Christos Papadopoulos, A framework for classifying denial of service attacks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
Tadayoshi Kohno , Andre Broido , K. C. Claffy, Remote Physical Device Fingerprinting, IEEE Transactions on Dependable and Secure Computing, v.2 n.2, p.93-108, April 2005
Cherita L. Corbett , Raheem A. Beyah , John A. Copeland, Passive classification of wireless NICs during rate switching, EURASIP Journal on Wireless Communications and Networking, v.2008 n.2, p.1-12, January 2008
Alefiya Hussain , John Heidemann , Christos Papadopoulos, Distinguishing between single and multi-source attacks using signal processing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.4, p.479-503, 15 November 2004
wireless networks;encryption;signal processing;traffic analysis