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 ﬂoods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Such real-world events happen in speciﬁc geographical locations and disrupt speciﬁc 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 Deﬁnition 1 (Performance Measures): The performance measures of a cut are (the last 3 are deﬁned 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 ﬂow between a given pair of nodes s and t. • AMF - The average value of maximum ﬂow 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 Deﬁnition 2 (Worst-Case Cut): Under a speciﬁc 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, ﬁnd 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 ﬁber 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 diﬀerence 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, ﬁnd 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 ﬁnd ∆ > 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 ﬁnding 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.