Slides

Report
Coping with Physical Attacks on
Random Network Structures
Omer Gold
[email protected]
Joint work with Reuven Cohen (BIU)
To appear in the Proceedings of IEEE International Conference on
Communications (ICC), June, 2014.
Content

Problem and motivation

Previous work Overview

Random Network model

Algorithms and Analyses

Summary
Problems and motivation

Communication networks are vulnerable to natural
disasters, such as earthquakes or floods, as well as
to physical attacks, such as an Electromagnetic Pulse
(EMP) attack.

Such real-world events happen in specific
geographical locations and disrupt specific parts of
the network.

Therefore, the geographical layout of the network
determines the impact of such events on the
network’s connectivity.
Large Scale Physical Attacks/Disasters

EMP (Electromagnetic Pulse)
attack, Solar Flares, and other
Natural Disasters
◦ will destroy backbone nodes
and links

Physical attacks or disasters
affect a specific geographical
area
◦ Fibers, routers, generators, and
power lines have a physical
location
Source: Report of the Commission to Assess
the threat to the United States from
Electromagnetic Pulse (EMP) Attack, 2008
4
Problems and motivation

An interesting question is to identify the most
vulnerable parts of the network.

That is, the locations of disasters that would have
the maximum disruptive effect on the network in
terms of capacity and connectivity.

We consider graph models in which nodes and
links are geographically located on a plane, and
model the disaster event as a line segment or a
circular cut.
Problems and motivation

Definition 1 (Performance Measures):
The performance measures of a cut are (the last 3 are defined as the
values after the removal of the intersected links):
• TEC - The total expected capacity of the intersected links.
• ATTR - The average two terminal reliability of the
network. (Connectivity measure)
• MFST - The maximum flow between a given pair of nodes
s and t.
• AMF - The average value of maximum flow between all
pairs of nodes.
Example – Circular cut
∗
7
3
2
7
9
Q. What is the TEC measure for this cut?
A. 2+3+7+9+7 = 28
*The black links are not affecetd by the cut.
Problems and motivation

Definition 2 (Worst-Case Cut):
Under a specific performance measure, a worstcase cut is a cut which maximizes/minimizes the
value of the performance measure.
Problems and motivation
Geographical Network Inhibition by Circles
(GNIC) Problem (2009):
Given a graph, cut radius, link probabilities, and
capacities, find a worst-case circular cut under
performance measure TEC.
 After solving TEC measure problem in polynomial
time, it can be shown that the other performance
measures(ATTR, MFST, AMF) are also polynomial.

(Zussman, Neumayer, Cohen, Modiano. 2009).

We will focus from now on the TEC measure.
Example – Real Network
The fiber backbone operated by a major U.S. network provider
We want to find a cut that maximizes TEC,
denote as “worst-cut”.
Previous Work Overview

S. Neumayer, G. Zussman, R. Cohen, E. Modiano
(IEEE INFOCOM 2009)
Showed polynomial time algorithms that finds
Worst-Case Circular Cut in   6 time

Improvements have been made for some
performance measures using tools from
Computational Geometry (Arrangements)
P. K. Agarwal, A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararamany
and G. Zussman. (IEEE MILCOM 2010)
Previous Work Overview

Network Reliability Under Random LineSegment Cut:
Calculate some network performance metrics to such a
disaster in polynomial time.
S. Neumayer, E. Modiano (IEEE Infocom 2010)

Network Reliability Under Random CircularCut
disasters that take the form of a `randomly' located disk in
a plane. Approximate some network performance metrics
in case of such a disaster in polynomial time.
S. Neumayer, E. Modiano (IEEE Globecom 2011)
Previous Work: Probabilistic Failures

Major work has been made recently about generalizing previous
failure model to probabilistic failure model and simultaneous attack
failures. Work by:
Pankaj K. Agarwal, Alon Efrat, Shashidhara K. Ganjugunte, David Hay, Swaminathan
Sankararaman, Gil Zussman: The resilience of WDM networks to
probabilistic geographical failures. INFOCOM 2011: 1521-1529
Later improved version in: IEEE/ACM Trans. Netw. 21(5): 1525-1538 (2013)
Another improvement and variation has been recently made by:
Pankaj K. Agarwal, Sariel Har-Peled, Haim Kaplan, Micha Sharir: Union of
Random Minkowski Sums and Network Vulnerability Analysis.
Previous Work Overview
Failure Models

Deterministic:
◦ Fails definitely if within range

Probabilistic:
◦ Simple:
fails with a probability q if
within range
◦ Spatial Probability Functions
 Linear, Gaussian, Arbitrary*
P. Agrawal, A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman,G. Zussman IEEE Infocom 2011
Random Network

As we saw, models with deterministic, random and
probabilistic failures have been recently studied
extensively .
What about Random Networks?
This is what we are going to talk about here.
Our work is about developing algorithms for finding
“worst-cuts” in Random Networks, as well as
developing methods to model a random network
from a given data, such as: demographic map, terrain
conditions, economic considerations, etc.

Random Network- Motivation

The attacker (adversary) has partial or no
knowledge about the network topology.

Adversary has a “noisy” network topology map.

Assessing the reliability of hidden networks.

Real-life networks topology sometimes presents
similar characteristics to a random network
topology.
Random Network- Our Model

We model a random network in a rectangle which
bounds the country’s extreme points +cut’s radius
.




 = ,  [, ]
Random Network- Our Model

The main idea of our stochastic modeling is in
considering the configuration of the stations as
realizations of non-homogeanus Poisson point
process. The main advantage of a Poisson process is
it's simplicity.

The distribution of a Poisson point process is
completely defined through the intensity measure
() representing the mean density of points.
Random Network- Our Model
Network Model Formulation:
  = < ~Π  , ~(), ~(),  >


Nodes are distributed in the rectangle Rec through a Spatial
Non-Homogenous Poisson Point Process Π() where () is the
intensity function of the .

Let ( ,  ) be the probability for the existence of a link
between two nodes located at  and  in Rec.

(,  ,  ) is the cumulative distribution function of the link
capacity between two connected nodes.
i.e. ( < ) = (,  ,  ) where  and  are the locations
of nodes  and , respectively.
Random Network- Model

It is reasonable to assume that ( ,  ) and
(,  ,  ) can be computed easily as a function of
the distance from  to  and that the possible
capacity between them is bounded (denote by
max{}).
Random Network- Model
We assume the following:
the intensity function (),  (), and ℎ() (the
derivative of H()) are functions of constant description
complexity, they are continuously differentiable and
Riemann-integrable over Rec. Implies that our
probability functions are of bounded variation over Rec
as their derivatives receives maximum over the
compact set  ⊆ ℝ2 .

Algorithm – Evaluate Damage

We present Polynomial Time Approximation
Algorithms for finding the Expected Worst Case
cuts location and damage in the Random Network
model, i.e. cut that maximizes the total
expected capacity of the intersected links
(TEC).

For this goal we first develop an algorithm to
evaluate the TEC (Damage) for a given cut.
Evaluate Damage of a Circular Attack (i.e.
“cut”)

For a cut , we divide the intersections of  with the
graph's edges into 3 independent types:

 − , is the case where the entire edge is inside .
which means both endpoints of the
edge are inside .

 − , is the case where one endpoint is inside 
and the other is outside .

 − , is the case where both endpoints are outside
from  and the link which connects
the endpoints intersects .
Example:
 −  demonstration
 −  demonstration
 −  demonstration
Example – Circular cut

7
3
2
9
A red link is an  − 
A blue link is a  − 
An Orange link is a  − 
7
Evaluate Damage of Circular Attack


For  ∈ , ,  , let  be the total capacity of the
intersected  −  type edges with cut .
Namely, the damage determined by  − .
Thus, it holds that the expected capacity of the
intersected links of types ,  and  is determined
by:
Evaluate Damage of Circular Attack
where (, )
= (, )
max{}
ℎ
0
, ,   
is the expected capacity between two nodes at points
 and .
Evaluate Damage of Circular Attack
(, , ) is the indicator function, giving 1 if the
segment (, ) intersects the circle  and 0
otherwise.
Evaluate Damage of Circular Attack

Let  =  +  +  be the total damage
determined by all the intersected links with cut .

Due to the linearity of expectation, we get that the
total expected capacity of the intersected links
(TEC) is [] = [ ] + [ ] + [ ].
Algorithm to Evaluate the Expected
Damage for a given Cut.

Algorithm to evaluate the TEC (Damage) for a given
cut  =  ,  .
 , ,  :
Input:
  =< Π  , (), (),  >
  = (, )
  −  
 Output: TEC (Damage) caused by 
Algorithm to Evaluate the Expected
Damage for a given Cut.

Computing the  −  Damage:
 

1
=
2
     ,  


Computing the  −  Damage:
  =
     ,  
 −
Algorithm to Evaluate the Expected
Damage for a given Cut.

How to compute the  −  damage?

Requires more sophisticated approach.
First, let’s ask the following:
For a node  ∈  ∖ , what is the set of points
  in  ∖  that satisfies:

For every node  ∈  ( ), the edge ,  intersects
, and for every node  ∉ ( ) the edge ,  does
not intersect ?
Example:
Evaluate the Expected Damage for a
given Cut.
Computing the  −  Damage:
 Following
the idea we just saw, we want
to integrate for all such possible nodes 
and .
 We
use numerical integration:
We divide  into a Grid of squares.
Algorithm to Evaluate the Expected
Damage for a given Cut.

Evaluate_ − (, , Grid)
1.
Create two tangents to  going out from .
2.
Denote the line segments of the tangents which their
endpoints are the intersection point of the tangent with
 boundary by 1 and 2 .
3.
Denote by () is the set of points which is bounded
by 1 , 2 ,  and the boundary of .
4. Return
  (, )
( )
Algorithm to Evaluate the Expected
Damage for a given Cut.
Computing the  −  Damage:

  =
1
  Evaluate_ − (, , ) 
2
−

This integral is computed numerically over the
Grid.

The denser the Grid, the more accurate result we
obtain.

Finally, Return   +   +  
Graphic Example to -link damage
computation
∗
()
How?
• We run over the squares center-point.
• Size of the Grid (squares) is determined by the requested accuracy
parameters.
Algorithm to Evaluate the Expected
Damage for a given Cut.

We define an additive  −  to the
cut capacity as a quantity  satisfying:
− ≤ ≤+
Where  is the actual capacity intersecting the cut.
Numerical Accuracy

We refer the side length of the grid squares
as the “grid-constant” Δ.

We denote the set of squares center-points
as “grid points”.

We restrict our results to the case where
Δ < /2, as otherwise the approximation is
too crude to consider.
Numerical Accuracy

The leading term in the error when
integrating numerically over the grid
points, as Δ → 0 is obtained by the
following geometric results
Numerical Accuracy

1 and 2 are tangents to a circle of radius ∆ centered at  and to
the circular cut.

The colored areas depicts the extremum of difference for possible 
−  endpoints emanating from a point within the circle centered
at  at one side of the cut.
Numerical Accuracy
For simplicity, let’s look at this

We want to bound the grey area using Δ.
Numerical Accuracy

Using trigonometry and technique this
area can be bounded by  Δ where 
≤ const ⋅
2

and  is the diagonal length
of .
 Basic idea is calculation of the head angle
using Δ and  of the grey triangle where
bounding its sides with .
Numerical Accuracy

First, let’s look at the extreme case:
tan 2 =
2Δ
2 − 4Δ2
2
2 tan 
Using tan 2 = 1−tan2 
We can obtain that
Δ ≤ 2 ≤ 2Δ.
Thus tan  = /
≤
2Δ

tan  = /
2 − 4Δ2
Numerical Accuracy

First, let’s look at the extreme case:
2 tan 
Using tan 2 = 1−tan2 
We can obtain that
Δ ≤ 2 ≤ 2Δ.
2
Thus tan  = / ≤
2Δ

This area is bounded by
1 2
2 sin  ≤ 2 tan 

sin
2
≤

2
≤ 2
2Δ

. Where  is the diagonal
length of .
Bounded by 2 , thus bounded
also by
Numerical Accuracy

Now, back to the general case:
 is the same as before (barely
visible in this setting)
Using geometry we obtain:
sin( ∠) = Δ/( 2 +  2 + b).
• If  ≤ Δ the point  is located within a distance
of  + Δ ≤ 2Δ.
Thus, the grey area is bounded as in the
previous case.
• If  > Δ we have sin( ∠) < Δ/ 2 < Δ
/ 2Δ.
Thus, the grey area is bounded by 2 Δ/r .
Additive Approximation

Thus, the leading term (we will see why
next) of the accumulated error from the
numerical integration, as Δ ⟶ 0 is
2
 −  ≤  ⋅ ||
Δ

Where  = max {    (, )}
,∈
Additive Approximation

Other error terms are linear in Δ, thus
when Δ → 0 are negligible by the leading
term which is with factor of Δ.

Using our analysis the function
(, , ) can be
implemented by selecting Δ small enough
such that the total error will be at most .
Additive Approximation – Running Time

Denote the area of Rec by .

The algorithm is based on performing
numerical integration over pairs of grid points
(square-center points).

The number of grid points in the rectangle is
/∆2 . Thus the running time is at most
proportional to the number of pairs of grid
points, which is (2 /∆4 ).
Additive Approximation – Running Time

From our analysis we obtained
2
 = ( 
Δ
+

Δ2 )
It give that the total running time is:
2
10 16  8 10  4 4
 4 =
+
8
4
Δ
 
4
Additive Approximation

As we saw, the running time of the EDCC
algorithm is polynomial in all the parameters with 
−  of ( −8 )

Since in this analysis we depend on the maximum
values of  and  over  (parameter ) some
will call it pseudo-polynomial.

In “real-world” scenarios  usually is not expected
to be too high, but in “theory” we want to give an
analysis which is independent in .
Multiplicative Approximation

We now give a combined multiplicativeadditive analysis independent in , such that
we can then choose the grid constant Δ to
guarantee that the result  obtained by
algorithm EDCC satisfies
1− − ≤ ≤ 1+ +
We modify the function  to to
be (, , , )
Receives also the multiplicative
accuracy parameter
Multiplicative Approximation

Probably no time for technical details for
this analysis.

Let’s jump a few slides straight to the
running time.
′

• Denote by   the point on  with coordinate , where the 
−  is taken to be the angle bisector between ′ and .
Similarly, ′  .
• From our previous geometric results it can be obtained that for any
point  ∈ , the euclidean distance ′  −   ≤  Δ where
2
 ≤  ⋅

′
For convenience, for a point ,
denote  () = ()()(, ),
and write it in Cartesian
coordinates (, ) w.r.t the axis
described earlier.

The TEC from  −  and  −  emanating from  is
bounded by
′

Thus, the difference between the TEC values of 
−  and  −  emanating from  to 
−  and  −  emanating from  is
bounded by
Now we work to represent it as a multiplicative of
′

Taking strips of length  Δ we obtain the
following inequality sequence
Note also that
Thus, when integrating over  ∪  by summing
2
integrations on strips with length  Δ, at least
 Δ
such strips are needed.
Note also that
The difference in the TECs is bounded by the average of
2r
the above monotone increasing sequence of length
 Δ
(actually bounded by it’s first element, but we want to
prove a factor).
Note also that
We have
We have
Multiplicative factor
Additive term
The leading term in the error as Δ → 0 is with multiplicative

factor of
2
Δ and an additive term of  Δ between
the two TEC values.

Other error terms are about the areas of
inaccuracy we mentioned previously in the
additive approximation.

This error terms can be bounded using
the same “strips” method but now strips
of length at most Δ are sufficient.

Obtaining additional error terms which
are linear in Δ. As Δ → 0 they are negligible
by the leading term.
Multiplicative Approximation –
Running Time
For a  of area , we saw that the running
time is at most proportional to the number of
pairs of grid points which is (2 /∆4 ).
 From our error analysis we obtain that

2 2
=
Δ
1.5

 =   3 Δ
From this, it is obtained that the total running time is
10 16 10 24 8

+
8
12
 
 84
The  −  and  −  on the running time is
  −8 ,   −8 .
Find Sensitive Locations Scheme

Using Algorithm EDCC one can approximate the TEC for
an attack at any point, and in particular, find an
approximated worst case attack (one with the highest TEC
value).

To achieve this goal, we divide  into squares, forming a
grid. Then, we execute EDCC algorithm from the previous
section for every grid point (squares center-points) such
that it is a center-point of a cut of radius . This leads to a
“network sensitivity map”, i.e., for every point we have an
approximation of the damage by a possible attack in that
point.
Find Sensitive Locations Scheme

To guarantee an attack location with TEC of at least  − 
where  is the  of the actual worst cut and an
additive accuracy parameter  > 0, we provide the
following algorithm:
1.
For a cut of radius , and accuracy parameter  > 0,
apply the function (, , /2) to find ∆
> 0 such that the accuracy of Algorithm EDCC, given by
Theorem 1 is /2.
Form a grid of constant ∆ (found in step 1) from .
For every grid point , apply procedure
(, (, ), /2). The grid point with the
highest calculated TEC is the center of the approximated
worst cut.
2.
Find Sensitive Locations Scheme
Running-Time: For a  with area 
The algorithm samples a circular cut of radius  at the center
point  of each grid square. For each such cut,
the algorithm executes  ,  , 
time. The grid has 

∆2

,
2
in 
2
Δ4
points. Thus, in total it runs in
(3 /Δ6 ). Since  is of order Δ we obtain that the 
−  on the running time is   −12 .
Similar result can be obtained for a combined
-multiplicative -additive approximation using the modified
EDCC algorithm.
Find Sensitive Locations Scheme
Random Disasters:
Using the methods we showed, we can also
compute the approximated expected TEC by a
random disaster on the random network. For
example, for the uniform case by returning
1

∈
( ,  ,  , /2)
The randomly located failure can model a natural disaster
such as a hurricane or collateral (non-targeted) damage in an
EMP attack.
Simulations, Numerical Results.

In order to test our algorithms, we estimate the
expected impact of circular cuts on communication
networks in the USA based on a population density
map.

Data of the population density of the USA was
taken as the intensity function ().

The population density matrix used give a
resolution of approximately 27km. This gave a
matrix of dimensions 104×236. The algorithm was
then run over this intensity function.
Simulations, Numerical Results.
Color map of the the USA population density in
logarithmic scale. The The values determines the intensity
function used as the input for the simulation
Simulations, Numerical Results.

The function (, ) was taken to be 1/(, )
and 1/ 2 (, ), where  is the Euclidean
distance between the points. Based on
observations that the lengths of physical Internet
connections follow this distribution.

The capacity probability function ℎ was taken to
be constant, independent of the distance, reflecting
an assumption of standard equipment. Each run
took around 24 hours on a standard Intel CPU
computer.
Simulations, Numerical Results.
Color map of the centers of circular cuts with radius r = 5
(approximately 130km). Red is most harmful.
Simulations, Numerical Results.
Color map of the centers of circular cuts with radius r = 5
(approximately 208km). Red is most harmful.
Simulations, Numerical Results.
Results for  ,  =
1
 2 ,
(instead
1
 ,
)
Color map of the centers of circular cuts with radius r = 5
(approximately 130km). Red is most harmful.
Simulations, Numerical Results.
Results for  ,  =
1
 2 ,
(instead
1
 ,
)
Color map of the centers of circular cuts with radius r = 10
(approximately 260km). Red is most harmful.
Simulations, Numerical Results.

Previous work on deterministic network line cuts
simulations.
Line segments cuts of length approximately 120 miles
optimizing TEC – the red cuts maximize TEC and the
black lines are nearly worst-case cuts.
Simulations, Numerical Results.

Our results imply that some information on the
network sensitivity and vulnerabilities can be
deduced from the population alone, with no
information on any physical links and nodes.

However, our algorithm can be used in conjunction
with more complicated modeling assumptions,
including topographic features and economic
considerations to give more accurate results.
Conclusions, Summary

Our schemes allows to examine how valuable is public
information (such as demography, topography and
economic considerations) to an attacker’s destruction
assessment capabilities, and examine the affect of hiding
the actual physical location of the fibers on the attack
strategy.

Thereby, the schemes can be used as a tool for policy
makers and engineers to design more robust networks by
placing links along paths that avoid areas of high damage
cuts, or identifying locations which require additional
protection efforts (e.g., equipment shielding).
Conclusions, Summary

Recent contributions to this emerging field of
geographical failures focused on deterministic
networks, studied various failure models.

We described polynomial time approximation
algorithms for finding the damage caused by cuts at
different points in our spatial random network
model and to approximate the location and damage
of the worst case cuts.

To the best of our knowledge this work is the first
to study such geographical failures in the context of
spatial random networks.
Future work
The discussion about finding vulnerable geographic locations
to physical attacks naturally leads to the question of robust
network design in the face of geographical failures.
Several questions are proposed:
 Designing the network’s physical topology under some
demand constraints (e.g., nodes that should be located
within a specific region, capacity and flow demands) such
that the damage by a large-scale physical attack is
minimized.
 Study the effect of adding minimal infrastructure (e.g.,
lighting-up dark fibers) on network resilience, and
determine how to use low-cost shielding for existing
components to mitigate large-scale physical attacks.

similar documents