Estimation_of_Message_Source_and_Destination_From_Network_Intercepts.pdf
(
613 KB
)
Pobierz
591030507 UNPDF
374
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
Estimation of Message Source and
Destination From Network Intercepts
Derek Justice and Alfred O. Hero, III
, Fellow, IEEE
Abstract—
We consider the problem of estimating the endpoints
(source and destination) of a transmission in a network based
on partial measurement of the transmission path. Possibly asyn-
chronous sensors placed at various points within the network
provide the basis for endpoint estimation by indicating that
a specic transmission has been intercepted at their assigned
locations. During a training phase, test transmissions are made
between various pairs of endpoints in the network and the sen-
sors they activate are noted. Sensor activations corresponding
to transmissions with unknown endpoints are also observed in
a monitoring phase. A semidenite programming relaxation is
used in conjunction with the measurements and linear prior infor-
mation to produce likely sample topologies given the data. These
samples are used to generate Monte Carlo approximations of the
posterior distributions of source/destination pairs for measure-
ments obtained in the monitoring phase. The posteriors allow for
maximum a posteriori (MAP) estimation of the endpoints along
with computation of some resolution measures. We illustrate the
method using simulations of random topologies.
Index Terms—
Channel and network models, data acquisition
and sensor models, detection and identication of anomalous
events, network tomography and surveillance.
Fig. 1. Diagram of the measurement apparatus on a sample network. Probing
sites are sources
=f;g
and destinations
=f;g
. A box on a link
or node represents a sensor that indicates when a transmission path intercepts
that link/node. We see
and
monitor nodes while
,
, and
monitor
links.
a transmission with endpoints in Fig. 1 might
activate -suppose this is the rst measurement so
. The ordering , corresponding to , might
have probability , while the ordering ,
where , has probability . Since the orderings
are dened over distinct sensor sets, we implicitly assume
the transmission does not cycle in its path-that is, a particular
sensor is activated at most once by a single transmission.
During a preliminary training phase, the network is probed by
transmitting data packets between various pairs of probing sites
, and the sensors activated by
each transmission are recorded along with the distributions on
orderings . A monitoring phase begins at time
instant and continues until some nal time , whereby
we observe sensor activation sets
(source and destination) of a data transmission in a
network whose logical topology is unknown. We assume
there are a number of asynchronous sensors placed on some
subset of elements (links or nodes) in a network. A sensor is
activated, and its activation recorded, whenever the path of
a data transmission is intercepted on the element where the
sensor is situated. The measurement apparatus is illustrated
on a sample network in Fig. 1. Measurements are taken at
discrete time instances, and the subscript is used throughout
the paper to index time. If multiple sensors are activated by
a single transmission, they may not be capable of providing
the precise order in which they were activated. In general, a
probability distribution on the possible orders of activation
is observed for each measurement; here the argument
is simply a natural number used to indicate a
specic ordering of the sensors activated at time . For example,
and associated
ordering distributions
for which the endpoints
are unknown.
The probing data , the
monitored data , and some prior
information about the network topology are processed to pro-
duce Monte Carlo estimates of the posterior distributions of
possible endpoints of those transmissions observed in the moni-
toring phase. We allow prior information of the form
on the logical adjacency matrix describing connec-
tions among sensors and probing sites. is some subset of the
elements of , is a xed linear operator, and is a vector. Thus
the prior information is essentially a set of linear equalities that
the adjacency matrix ought to satisfy. The linear operator
can be expressed as an equivalent matrix if the elements of
are organized in a vector . The linear prior information is then
of the form . In general, we make no assumptions about
the structure of , so that given arbitrary and the computa-
tion of feasible solutions to the linear equation is known to be
Manuscript received April 25, 2005; revised March 30, 2006. This work was
supported by the Department of Electrical Engineering and Computer Science,
University of Michigan Graduate Fellowship of the rst author and in part by
the National Science Foundation under ITR Contract CCR-0325571. The as-
sociate editor coordinating the review of this manuscript and approving it for
publication was Prof. Mohan S. Kankanhalli.
The authors are with the Department of Electrical Engineering and Computer
Science, University of Michigan, Ann Arbor, MI 48109-2122 USA (e-mail:
justiced@umich.edu; hero@umich.edu).
Digital Object Identier 10.1109/TIFS.2006.879291
1556-6013/$20.00 © 2006 IEEE
I. I
NTRODUCTION
W
E PRESENT a method to estimate the endpoints
JUSTICE AND HERO, III: ESTIMATION OF MESSAGE SOURCE AND DESTINATION FROM NETWORK INTERCEPTS
375
an NP-Complete problem [1]. We consider the associated min-
imum norm problem where and
is a quadratic norm with respect to the positive denite
matrix . It is known that combinatorial optimization problems
of this type may be successfully approximated by “lifting” them
into a higher dimensional matrix space where
The related area of network tomography has recently been
a subject of substantial research. It refers to the use of trafc
measurements over parts of a network to infer characteristics of
the complete network. Some characteristics of interest include
the following: source/destination trafc rates [10], [11], link-
level packet delay distributions [12], [13], link loss [14], and link
topology [15], [16]. For an overview of relevant tomography
problems for the Internet see [17]. In many applications, the
tomography problem is ill posed since data are insufcient to
determine a unique topology or delay distribution.
Our work is related to the internally sensed network tomog-
raphy application described in [18], [19]. These works propose
a methodology for estimating the topology of a telephone net-
work using the measurement apparatus illustrated in Fig. 1. The
data transmissions are of course telephone calls and the asyn-
chronous sensors are located on trunk lines. A simple argument
in [19] demonstrates that the number of topologies consistent
with the data measured during the probing phase is
exponential in the number of sensors. Indeed the problem is
ill-posed as the data required to provide a reasonable estimate
of the topology will never be available in practice. We sidestep
the difculties of developing a single topology estimate by aver-
aging over many probable topologies in computing the endpoint
posterior distribution.
The solution approach we develop is very general, and we
suspect it might have application in all sorts of networks: in-
cluding telephone networks as described in [18], the Internet,
social networks (such as command and control structures), or bi-
ological networks (such as protein-protein interaction networks)
[20], [21]. Since we allow for sensor placement on arbitrary net-
work elements, the method is equally applicable to networks
where it may be more convenient to monitor nodes (as in the
Internet) or monitor links (as in the telephone network of [18]).
Also, the ordering distributions allow for situations involving
sensors ranging from asynchronous to perfectly synchronized.
At one extreme, the sensors are exactly synchronized-in which
case the distribution reduces to a delta function with all
mass concentrated on the known ordering of sensors. A natural
source of such information would be the noisy time stamp as-
signed by each sensor to when it saw the message. Indeed, this
is an issue faced in many active probing scenarios. Methods in-
volving GPS and calibration of PC clocks have been described
in [22] and [23], respectively, for addressing asynchronous sen-
sors in active probing of technological networks. One might de-
rive the ordering distributions from some noise model for the
time stamps. In the present work, we assume the ordering distri-
butions themselves are provided since the chronological order in
which the sensors intercept a message is the crucial information.
Although the monitored network topology is unknown, the
linear prior information permits inclusion of reasonably avail-
able information relevant to the topology. This is a generaliza-
tion of the frequently used vertex degree prior. Vertex degree
priors are used quite often due to the fact that many real world
networks are characterized by specic degree distributions [24].
For example, studies have suggested a power-law distribution
describes vertex degrees in the Internet [25]. Such priors have
recently been applied to research involving models of social and
biological networks [20], [21], [26]. Since the degree of a vertex
[2].
With the advent of polynomial time interior point methods
for linear programming that can be extended to semidenite
programming [3], [4], it is convenient to consider a semide-
nite programming (SDP) relaxation of the higher dimensional
problem. Indeed, SDP relaxations have proven to be powerful
tools for approximating hard combinatorial problems [5]–[8].
The SDP, however, is solved over a continuous domain so it is
necessary to retrieve a 0–1 solution from the possibly fractional
SDP solution. One possibility is a branch and bound scheme
whereby certain variables are xed and the SDP is repeated until
a discrete solution is found [1], [8]. The branch and bound al-
gorithm can take an exponential amount of time, depending on
how tight the desired bound is. A randomized rounding scheme
was developed in [6] for SDP relaxations of the maximum cut
(MAXCUT) and maximum 2-satisability (MAX2SAT) prob-
lems. This scheme is shown to produce solutions of expected
value at least 0.878 times the optimal value in [6]. We develop
an SDP relaxation of the 0–1 minimum norm problem and apply
the randomized rounding method in conjunction with samples
from the ordering distributions to produce a number
of network topology adjacency matrices that approx-
imately satisfy the linear prior information . We de-
rive an expression for the expected value of the squared error
of samples produced in this way. This expres-
sion depends on the solution of the SDP relaxation, but an upper
bound on the error independent of the SDP solution is also
given.
We wish to produce posterior distributions given the data and
prior information of the endpoints of transmissions observed
in the monitoring phase for .
The network topology and sensor ordering samples are used in
conjunction with prior distributions on the endpoints of mea-
surements made during the monitoring phase for
to compute Monte Carlo approximations of
the desired posterior distributions via Bayes rule. Bayes formula
for this problem essentially reduces to the expected value of a
functional of the topology and sensor ordering ; our approx-
imation of the endpoint posterior thus becomes an average of
the values of this functional at each sample topology and
ordering set . It is readily apparent that this functional re-
quires the conditionals -these path likelihood func-
tions are the conditional probabilities of a sensor activation set
given the endpoints and activation order in a topology .
We propose a path likelihood model inspired by shortest path
routing, whereby the length of a path determines its probability.
Since the model is probabilistic, it is also well suited to dynamic
algorithms, such as distance vector routing [9], which may not
always choose the same path for a single endpoint pair. With
the endpoint posterior distribution in hand, we can immediately
give the MAP estimate of (with )oran
a posteriori
condence region of probable source/destination pairs.
and
376
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
is equal to the sum over the row of the adjacency matrix de-
scribing connections to that vertex, one can easily construct a
linear operator so that expresses the degree prior
for a given vector of vertex degrees .
The approach described here might also nd utility in systems
conveniently modelled by graphs, such as nite state automata.
The problem of machine identication is a classic problem in the
theory of automata testing [27], [28]. Here, we are given a black
box with an automaton inside whose transition function is un-
known. Based on the response of the system to certain input se-
quences, we wish to reconstruct the transition function. The link
to the network topology recovery aspect of our problem is clear,
since a graph provides a convenient representation for the transi-
tion function of interest. The probing sites chosen in the probing
phase of our problem is analogous to the input sequences to
the black box automaton. Similarly, link sensors correspond to
events in the automaton’s observable event set. An exhaustive
algorithm for solving this problem is given in [27] and shown
to have exponential run time. Our methods might be adapted
to provide a polynomial time approximation algorithm. This
would involve partitioning measurements with cycles (whereby
an observable event occurs more than once in the same string)
to satisfy the direct path assumption and selecting a different
conditional path likelihood since the shortest path
routing model we suggest might not be appropriate.
The outline of this paper is as follows. We review the problem,
describe in detail each component of the endpoint estimation
system, and analyze its complexity in Section II. In Section III,
we provide some simulations of random graphs. In Section IV
we conclude with some extensions of the method presented here
and give directions for future work utilizing feedback for adap-
tive probing.
Fig. 2. Example logical topology
G(V;E)
for the monitored network
G
in Fig. 1. The vertex set of
G
consists of sensors
=fg
and probing
sites
=f;g
,
=f;g
, so that
V=[[
. The edges of
G
summarize logical adjacencies among sensors and probing sites with any
intervening unmonitored elements short-circuited.
network (i.e., active measurements) so that the sources and des-
tinations of these measurements are known (since we choose
them). Because the sensors are in general asynchronous, the
paths are unordered sets. However, along with each , a dis-
crete probability distribution is observed on possible or-
derings indexed by of the set ; the observation data is then
for . We assume a transmission
does not cycle in its path from source to destination, so that only
orderings of distinct elements of are considered. It follows
that if has distinct elements, then is dened over
different orderings. Note that the case of perfectly synchro-
nized sensors is easily handled in this framework: simply take
where
is the known order in which the
sensors were activated.
At time , we proceed with monitoring of the network,
that is observing activated sensor sets with unknown source
and destination. The observation data in the monitoring phase
is for . The purpose of our system
is to estimate the source and destination of an
activated sensor set . In order to estimate the endpoints of
such a measurement, it is necessary to have some idea of the
logical topology of the network. Instead of considering the log-
ical adjacencies implied by the actual network ,we
are concerned with adjacency relationships among only those
elements (vertices and edges) that are either monitored with a
sensor or used as a probing site. For example, we cannot hope
to pinpoint the position of a link in the original network that
is not monitored by a sensor. We assume unmonitored elements
are essentially “short-circuited” in the original network . The
idea here is to assure two elements are logically adjacent even
if they are physically separated by an element (or subgraph of
elements) that is not monitored. The particular topology we con-
sider is then where is the set of
sensors and probing sites, and describes the log-
ical adjacencies among these elements. may be undirected
or directed depending upon the nature of the network .For
computational purposes, we represent
II. M
ODEL AND
T
HEORY FOR
S
OURCE
-D
ESTINATION
E
STIMATION
Let be a simple graph dened by the vertex set
, edge set , and incidence relation giving
the vertices connected by each edge. We allow to be either di-
rected or undirected; however, it should be known a priori which
is the case. In our application, denes the set of links in the
network topology, denes the routers or switches connected
by these links, and determines the pair of routers/switches
connected by each link. The graph is unknown to us.
Let denote a set of sensors we place in the network. Sen-
sors are placed on some subset of graph elements; that is sensors
may be placed on vertices, edges, or both. A sensor will indicate
whenever a transmission through the network passes the ele-
ment it is monitoring. Probing sites are selected from the vertex
set . The source vertex set is the set of vertices from
which transmissions may originate, and the destination vertex
set are those vertices at which transmissions may ter-
minate. A path observed at time between probing sites
and is given by , where contains
the sensors activated by the transmission from to . We as-
sume the rst
by its adjacency ma-
trix where
if and only if
for
and
otherwise. An example logical topology
is
measurements correspond to probes of the
given in Fig. 2 for the monitored network in Fig. 1.
JUSTICE AND HERO, III: ESTIMATION OF MESSAGE SOURCE AND DESTINATION FROM NETWORK INTERCEPTS
377
We assume independence of measurements at different times
and utilize a Bayesian framework to produce suitable approxi-
mations of the endpoint posterior distribution
correspond to a training phase for the probing sites , .For
each , we select a probing pair and pass
a transmission between this pair to observe the sensors acti-
vated and a distribution on the possible orderings of
the activated sensors. The measurement data therefore consists
of both the endpoints and the activated sensor set/ordering distri-
bution for . Such a measurement
is referred to as an
active
measurement. The remaining measure-
ments are due to monitored transmissions so that the endpoints
are not available: for . These
are referred to as
passive
measurements since they were not due
to active probing of the network on our behalf. It is assumed
that the endpoints of these measurements are realizations of a
random probing site pair described by the known distribution
dened on . We desire to estimate the particular
probing site pair between which a transmission was passed re-
sulting in a given passive measurement.
(1)
where the expression is obtained quite simply by using
the law of total probability to expand the distribution
over the random variables ,
and applying Bayes rule with appro-
priate independence assumptions to .Of
course in (1) so that we are considering the endpoint
posterior of a passive measurement. We have available linear
prior information on some of the logical adjacency elements
(a submatrix of ) of the form where is a xed
linear operator and a prior distribution on endpoints .
It is assumed the endpoint pair of a passive measurement is
independent of the particular topology , in other words, the
parties communicating do not know the network topology
either. However, if there is no connection between a given
endpoint pair in a topology , one would expect such a
pair to have probability zero; we shall use a model for the
term multiplying to ensure the product is zero in this
case. Here represents all measured data
( for and for
), and is the ordering of the sensors activated in
measurement . The conditional expectation is therefore taken
over all logical adjacency matrices and sensor orderings for
all measurements . We introduce a shortest path routing
model for the conditional path probabilities . The
conditional expectation in (1) is approximated in a Monte
Carlo fashion by summing over the argument evaluated at a
number of adjacency matrix and sensor ordering samples. The
sensor orderings are drawn independently from observed
distributions for . These are used in
conjunction with the solution to a semidenite programming
relaxation that incorporates the prior information
to produce adjacency matrix samples that are likely given
both the data and the prior information. With the approximate
endpoint posterior distribution in hand, we can provide MAP
estimates of the endpoints of the passive measurement and
compute appropriate error measures.
In the following, we rst elaborate on probing of the net-
work and the characterization of measurements obtained. Then
we describe the distribution and
how it may be efciently sampled using the given ordering dis-
tributions and a semidenite programming relaxation. Next we
discuss how the samples are used to approximate the endpoint
posterior and produce MAP estimates. Finally, we analyze the
complexity of our algorithm.
B. Generating Topology and Sensor Ordering Samples
In order to produce a Monte Carlo estimate of the conditional
expectation in (1), we need to specify and sample from the dis-
tribution
.Werst expand this dis-
tribution as
(2)
where independence over the measurement time index is used
to write the second term in product form. We now note that each
measurement contains a distribution over orderings
for the activated sensor set. Since these distributions are obser-
vations, it is reasonable to suspect that all topological consid-
erations are folded into them. We therefore assume that given
the ordering distributions, the particular orderings are inde-
pendent of the linear prior on topology. Equation (2) therefore
becomes
(3)
The factored form of the distribution in (3) suggests the rst
thing we should do in generating our samples is to select or-
derings independently from the distributions for each
. This is a simple matter since each is a
discrete distribution dened over a nite number of orderings.
Consider now what a measurement equipped with an or-
dering implies about the adjacency matrix . Let de-
note the ordered sensor activation set where, if is an active
measurement, the source probing site is taken as the rst ele-
ment followed by the ordering of the activated sensors and
the destination probing site is taken as the last element. If is a
passive measurement, is simply the ordering of the acti-
vated sensors. The fact that the transmission passes from the th
element of
A. Probing the Network and Taking Measurements
The set of all available measurements
is partitioned
into two disjoint sets. The measurements for
, given by
,to
implies there must be
378
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
a logical connection between
and
. Thus if we select
We now introduce variables
for each
an ordering
for each measurement (i.e., for
),
for
along with an additional
so that
then every adjacency element in the set
must be 1, where
the change of variables is given by
is dened by
(9)
(4)
The identities in (10) follow from this change of variables:
Once we draw orderings as previously described, the ad-
jacency matrix elements in are immediately xed at unity
by these. It remains, however, to select the remaining adjacency
elements. In drawing these, we must account for the prior infor-
mation . Since is a linear operator, we may re-ex-
press this information as where is now understood to
be a matrix and is a vectorized version of the adja-
cency elements . For arbitrary , nding a 0–1 vector that
satises the equation is an NP-Complete problem [29].
We will shortly discuss how randomized rounding of a semidef-
inite programming relaxation may be used to nd approximate
solutions. The randomized rounding will induce a distribution
on , the remaining factor in (3).
The induced distribution will have the desirable property that it
assigns high probability to samples that approximately satisfy
the linear constraint .
Consider the matrix equation equivalent to the linear
prior information . Producing vectors that satisfy
this equation amounts to nding several solutions to the problem
(10)
If we introduce a negative sign in the objective, then the opti-
mization in (8) becomes
such that
(11)
where is a vector of ones and matrices , are given by
(12)
nd
such that (5)
Unfortunately, the problem in (5) is NP-complete for an arbi-
trary, unstructured matrix [29]. We consider an equivalent re-
statement of (5)
In order to obtain a semidenite program, dene the matrix
. It is simple to show that for some
vector if and only if (i.e., is positive semidenite)
and . We drop the nonconvex rank-1 constraint
to obtain the SDP relaxation
maximize
minimize
such that (6)
where is a (symmetric) positive denite matrix that may be
chosen to emphasize the relative importance of the different
constraints. Obviously any optimal solution of the problem in
(6) with zero value solves the feasibility problem in (5). The
problem in (6) is no easier than the original statement, however,
it has been shown that problems of this type (0–1 quadratic pro-
grams) can be approximated quite well using a semidenite re-
laxation [7].
We now proceed to derive the SDP relaxation of (6). Our re-
laxation is similar to the one derived in [6] for MAX2SAT. First
note that the optimization in (6) is equivalent to
such that (13)
where indicates the trace operation and the constraint
is added to enforce . The equivalence
of the objective functions in (13) and (11) can be seen easily
by replacing with and dropping constant terms.
The SDP in (13) may be solved in polynomial time using a
primal-dual path following algorithm [4]. The result of this
optimization will in general be a non-integer symmetric
positive semidenite matrix. In [6], a randomized rounding
methodology is proposed to recover a ,1 vector from the
SDP solution . The strategy is to rst perform the Cholesky
factorization . A random hyperplane through the
origin with normal vector is then chosen by selecting from
the uniform distribution on the surface of the unit hypersphere
. The value of is then deter-
mined by whether the corresponding column of lies above
or below the hyperplane, i.e.,
minimize
such that (7)
where and . This is easily seen by
expanding the objective in (6) and dropping the constant term.
Now note that
if
and
since
; this fact this allows
if
. The th element of the vectorized adjacency sample
is then given by
(7) to be re-expressed as
minimize
such that
(8)
if
if
.
(14)
Plik z chomika:
Kuya
Inne pliki z tego folderu:
Behavior_Forensics_for_Scalable_Multiuser_Collusion_Fairness_Versus_Effectivenes.pdf
(964 KB)
Block_QIM_Watermarking_Games.pdf
(869 KB)
Correspondence.pdf
(176 KB)
Dual_Protection_of_JPEG_Images_Based_on_Informed_Embedding_and_Two-Stage_Waterma.pdf
(1549 KB)
Estimation_of_Message_Source_and_Destination_From_Network_Intercepts.pdf
(613 KB)
Inne foldery tego chomika:
2006-1
2006-2
2006-4
2007-1
2007-2
Zgłoś jeśli
naruszono regulamin