Network tomography [1] is a family of inference-based techniques to monitor the internal state (e.g., link delays or loss rates) of a network from external measurements. The need of such techniques arises in many networks where the internal network elements are accessible in the data plane but inaccessible in the control plane, e.g., the public Internet and all-optical networks.
Theoretically, network tomography works by inverting a given observation model that captures the relationship between the unknown link states and the observed path states, where specific solutions differ in the observation models they assume, e.g., a linear model for inferring additive link metrics such as delays [2], [3], [4], a Boolean model for localizing failures [5], [6], or various probabilistic models for accommodating performance fluctuations (see [1] and references therein). However, most of the existing works assumed that the measurements truthfully reflect the performance of measurement paths, leaving open what will happen when measurements can be manipulated by an attacker.
Manipulated measurements fundamentally change the problem of network tomography, because instead of only changing This work was supported by the National Science Foundation under award CCF-1813219. the link states (e.g., by delaying all the packets traversing a link), the attacker may manipulate different packets traversing the same link differently (e.g., by adding delays for packets with one source-destination pair but not adding delays for packets with another source-destination pair), thus changing the observation model. For example, a link showing two different behaviors for two groups of flows is effectively two different links, each traversed by one group of flows. For linear observation models, recent studies [7], [8] revealed novel attacks that can substantially degrade path performances while misleading network tomography to believe that the manipulated links perform well. However, these studies implicitly assumed that network tomography only collects passive measurements, i.e., the performances of data packets, and thus only measures the paths used for data transfer.
In practice, however, network tomography can monitor a larger set of paths via active measurements obtained from probes. Intuitively, augmenting passive measurements with active measurements exposes the performances of a larger set of paths and thus should help defending against attacks. In this work, we harden this intuition by quantifying the damage a stealthy attacker can inflict on a network monitored by network tomography with both passive and active measurements.
Network tomography is a rich family of network monitoring techniques that infer network internal characteristics from external measurements [1], [9]. Early works focused on besteffort solutions, which tried to find the most likely network state from given measurements, obtained by unicast [10], multicast [11], and their variations (e.g., back-to-back unicast [12]). After observing that an arbitrary set of measurements is frequently insufficient for identifying all the link metrics [13], [14], later works aimed at either reducing the ambiguity with given measurements (e.g., [10], [13]), or ensuring identifiability by carefully designing the monitor locations and the measurement paths (e.g., [2], [3], [4]). All these works assume a benign setting, where the links behave consistently and the measurements are truthful.
Very few works have considered network tomography in an adversarial setting. In [7], optimizations were formulated to design the manipulations at compromised nodes in order to cause the maximum degradation while scapegoating certain benign links as the cause of poor performance; however, the set of compromised nodes is not optimized. In [8], a similar but more sophisticated attack model, called the stealthy DeGrading of Service (DGoS) attack, was proposed, where the attacker jointly optimizes where to attack (in terms of compromised links) and how to attack (in terms of the manipulation at each path traversing at least one compromised link). However, both works assumed that only the data paths are monitored by network tomography, and thus the manipulation of any measurement path will affect the end user's performance.
Our goal is to quantify the impact of DGoS attack in networks monitored by network tomography based on both passive and active measurements.
1) We extend the attack model in [8] to include both passive measurement paths (for data packets) and active measurement paths (for probes), where only the performance degradation on passive measurement paths counts towards the damage caused by an attack.
2) We derive sufficient/necessary conditions for an attack strategy to be optimal under the above attack model. Based on these conditions, we establish the hardness of designing the optimal attack strategy and develop efficient approximations.
3) We evaluate the proposed attack strategies on real Internet topologies. Our evaluations show that: (i) the proposed strategies achieve more severe performance degradation than intuitive alternatives and thus better reveal the potential damage of DGoS attack, (ii) even a few compromised links can cause significant damage to end-to-end communications, and (iii) adding active measurements provides little protection if these measurements are only between the communicating terminals.
Roadmap. Section II formulates the generalized DGoS attack. Section III presents the optimality conditions and the associated algorithms for attack design. Section IV evaluates the proposed algorithms. Finally, Section V concludes the paper.
We model the network as an undirected graph G = (N, L), where N is the set of nodes and L the set of links. Each link l j ∈ L is associated with an unknown metric x j that describes its performance (the smaller, the better). We assume that these link metrics are additive, i.e., a path metric equals the sum of its link metrics. This is a canonical assumption satisfied by several important performance metrics including delays, jitters, log-success rates, and their statistics.
We assume that this network is monitored by a tomographybased detection system that measures the end-to-end metrics on a set P of paths to detect anomalies on link metrics. Let R = (r ij ) pi∈P,lj ∈L be the matrix representation of P , called the measurement matrix, where r ij ∈ {0, 1} indicates if path p i traverses link l j . Let r i = (r ij ) lj ∈L be the i-th row in R. Given the measured path metrics y = (y i ) pi∈P , network tomography detects link anomalies by finding a solution x to R x = y and then comparing each inferred link metric x j with the maximum normal delay τ : l j is considered "normal" if x j ≤ τ and "abnormal" otherwise. To focus on anomalies caused by the attack, we assume that the before-attack link metrics are all normal, i.e., x j ≤ τ (∀l j ∈ L). Let τ max denote the maximum possible link metric, which can be infinity; assume that τ ≤ τ max .
We note that the solution to R x = y may not be unique as R may not have a full column rank [13], [14]. In this case, we consider a powerful network tomography solver that can compute all the possible solutions to the link metrics.
Suppose that an attacker wants to degrade the performance of a subset of paths P d ⊆ P . Paths in P \ P d are monitored by network tomography but not carrying data flows of interest. For example, paths in P \ P d may be only used by probes or non-performance-sensitive packets.
The attack is mounted by first controlling a subset L m ⊆ L of links and then modifying the path metrics by z = (z i ) pi∈P through these links. Let c j (l j ∈ L) denote the cost of compromising link l j , and k denote the budget of the attacker. We call L m the compromised links and L n := L \ L m the uncompromised links. We call the paths P m ⊆ P traversing at least one link in L m the compromised paths, and the rest P n := P \ P m the uncompromised paths. To ensure that the attack is feasible, we adopt the following assumptions from [7], [8]:
1) Only the metrics of compromised paths can be manipulated, i.e., z i = 0 for any p i ∈ P n .
2) The manipulation can only degrade (not improve) path performance, i.e., z i ≥ 0 for any p i ∈ P m .
Moreover, the attacker wants to stay stealthy to the detection system by ensuring that (i) the network tomography problem remains feasible under the manipulation, i.e., R x = Rx + z is feasible, and (ii) there exists a feasible solution x according to which all the compromised links appear normal.
Using a change of variable z = R( xx), we formulate the problem of optimal attack design as follows:
In words, (1) designs "where to attack" (represented by L m ) and "how to attack" (represented by x) to maximize the total degradation on the paths of interest (1a), subject to feasibility (1b), stealthiness (1c)(1d), and budget constraints (1e). The above formulation generalizes the stealthy DGoS attack proposed in [8, (1)] in that: (i) only degradation on the paths in P d is included in the objective, which allows us to model network tomography based on both passive and active measurements, and (ii) a budget constraint (1e) is added to capture the resource constraint faced by a realistic attacker. As shown later, these differences lead to subtle but critical changes in the solution.
Given the set of compromised links L m , ( 1) is a linear program (LP) in x that can be solved in polynomial time by standard LP solvers. Meanwhile, optimizing L m is a combinatorial optimization problem, with an objective F (L m ) that denotes the optimal value of (1a) under a given L m . The main challenge is that the objective function F (L m ) is not an explicit function of the decision variable L m . Below, we propose two approaches to turn F (L m ) into an explicit function of L m , which then lead to efficient algorithms.
A. The Case of k = ∞ First, consider the case that the attacker has an unlimited budget, i.e. the constraint (1e) is removed.
1) Property of the Optimal L m : In the unbudgeted case, we establish the sufficient and the necessary conditions for a given L m to be optimal for (1). To this end, we introduce the following definitions.
Definition 1. Given P and P d , we define:
1) the traversal number w j := pi∈P d r ij for link l j as the number of paths in P d that traverse l j , 2) T (L ) := lj ∈L w j as the total traversal number of a set of links L , 3) a set of links L as a cut of a set of paths P if every p i ∈ P traverses at least one link in L , 4) C P as the collection of all the cuts of P , and 5) C * P as the collection of all the cuts of P with the minimal total traversal number, i.e., C *
Based on these definitions, we can state the optimality conditions as follows.
Theorem III.1. A set of compromised links L m is optimal if it is a cut of P with the minimal total traversal number, i.e., L m ∈ C * P . Proof. see [15].
Remark: Theorem III.1 generalizes [8, Theorem III.1], which states that in the case of P d = P , the minimal traversal cut of P achieves optimality, where the traversal number of a link is defined as the total number of paths in P that traverse it. Theorem III.1 extends this statement to the case of P d ⊆ P by redefining the traversal number for a link to only count the paths in P d that traverse this link. While Theorem III.1 gives a sufficient condition to achieve optimality, it does not rule out other possibilities. We show that L m ∈ C * P is not necessary by a simple example. In the example shown in Fig. 1, suppose that n k=2 x k ≥ τ max . It is easy to see that the optimal solution can be
The optimal solution {l 1 } / ∈ C * P shows that L m ∈ C * P is not a necessary condition. Nevertheless, we will show that forming a cut of P d is necessary under mild conditions.
Proof. See [15].
Theorems III.1 and III.2 imply the following condition.
Corollary III.3. If P d = P and τ > x j (∀l j ∈ L), then a set of compromised links L m is optimal if and only if L m ∈ C * P . Proof. See [15].
2) Hardness and Algorithm Design: Theorem III.1 implies that finding a minimum-traversal cut L m ∈ C * P will give an optimal solution to (1). This reduces (1) to the following combinatorial optimization problem. Definition 2. Given a set of paths P and a subset P d ⊆ P , the generalized adversarial link selection (GALS) problem aims at finding the cut of P with the minimum total traversal number by P d : min
GALS is similar to the adversarial link selection (ALS) problem in [8], except that the traversal number w j only counts the traversals by paths in P d . Nevertheless, given P d , the traversal number of each link is a constant, and thus the solutions for ALS and GALS are the same.
Specifically, since ALS is NP-hard [8], GALS is also NPhard. Moreover, similarly to the reduction of ALS to the weighted set cover (WSC) problem [8], GALS can also be Algorithm 1: Greedy GALS reduced to WSC, and can thus leverage existing algorithms designed for WSC. One such algorithm is the greedy algorithm, shown in Algorithm 1. The algorithm iterates until all the paths are compromised (line 4), where in each iteration, it picks a link with the smallest cost-value ratio (line 5) and adds it to the set of compromised links (lines 6-7). Here, we define the cost-value ratio of link l j by w j /|P j \ P m |, where P j is the set of paths traversing link l j . It is known [16] that this greedy algorithm has the best approximation factor for WSC, which is Θ(log |P |) in our case.
In the general case, the attacker may not have sufficient budget to compromise the minimum-traversal cut, and thus the optimal strategy needs to be adapted.
1) Property of the Asymptotically Optimal L m : For a general L m , it is difficult to write the optimal value of (1a) wrt x as an explicit function of L m . Nevertheless, we find the following approximation to be asymptotically accurate. Definition 3. Given a set of paths P , a subset P d ⊆ P , and the cost c j for each link l j , the generalized constrained adversarial link selection (GCALS) problem aims at:
where L n := L n \ ∪ p∈Pn p is the set of uncompromised links that are only traversed by compromised paths.
We show that when τ max is large, GCALS is asymptotically equivalent to the original optimization (1).
m is optimal for (1) if and only if L * m is an optimal solution to GCALS. Proof. See [15].
2) Hardness and Algorithm Design: First, we will show that GCALS problem is NP-hard.
Theorem III.5. The GCALS problem (3) is NP-hard. Proof. See [15].
Next, we will develop a solution by formulating this problem as an integer linear programming (ILP) problem (w j is defined as in Definition 1, the other parameters defined as in ( 1)):
Lemma III.6. The optimization ( 4) is equivalent to the optimization (3), where l j ∈ L m if and only if α j = 1.
Proof. see [15].
The ILP formulation (4) allows us to leverage techniques for solving ILP to solve the GCALS problem (3). In particular, one commonly-used approach is to relax the ILP into an LP by relaxing the integer constraint (4g) into α j , β j , γ j ∈ [0, 1]. After solving this LP relaxation for a fractional solution, we can use various rounding techniques to convert it into a feasible solution to the original problem. A rounding scheme we find to be particularly effective is as follows. For a link l j , we define the value-cost ratio as
, where P j is the set of paths traversing link l j and α j is the fractional solution of α j from the LP relaxation. We then iteratively select links into L m until reaching the budget, where in each iteration, we select the link l j with the largest value-cost ratio. We refer to this algorithm as "LP relaxation with rounding (LP-R)", for which the pseudo code is given in Algorithm 2.
In order to understand the potential damage of the generalized DGoS attack, we evaluate the proposed algorithms as well as benchmarks on real network topologies.
A. Experiment Setup 1) Network topology: We use real network topologies from public datasets, whose parameters are shown in the TABLE I. The first four topologies are Point of Presence (PoP)-level topologies from the Internet Topology Zoo [17], and the last two topologies are router-level topologies from the CAIDA project [18].
2) Paths: For each topology, we select a given number of terminals from low-degree nodes (degree ≤ 2), and compute P as the shortest paths (in hop count) between terminals, with ties broken arbitrarily. We then select a subset of paths in P as P d uniformly at random.
3) Other parameters: Before the attack, each link has a delay sampled from the interval of [0, 20) (ms) uniformly at random. The cost 1 of compromising each link is drawn uniformly at random from the interval of [0, 2). A link is considered "normal" if its delay is within 150 ms, i.e., τ = 150.
The maximum delay at a link is 2000 ms, i.e., τ max = 2000.
4) Benchmarks: We compare the proposed algorithms, Greedy GALS (Algorithm 1) and LP-R (Algorithm 2), with three heuristics and an optimal solution: i) "Random selection" ('random'): This algorithm selects links uniformly at random within the given budget. ii) "Top traversal" ('top traversal'): Based on the intuition that compromising the most traversed links will allow the attacker to control the most paths, this algorithm sorts the links by their traversal numbers in descending order, and then selects links in this order under the budget. iii) "LP relaxation with Randomized Rounding" ('LP-RR'):
To benchmark the proposed rounding scheme in Algorithm 2, we evaluate a randomized rounding scheme, where the fractional solution (α j ) lj ∈L to the LP relaxation of ( 4) is used as probabilities for selecting links. iv) "ILP" ('ILP'): This solution directly solves the ILP (4) by a commercial optimizer called Gurobi, which performs an exhaustive search in the worst case.
Under each selection of the compromised links L m , we solve the optimization (1) in x to compute the total performance degradation under the optimal manipulations (measured by the total delay injected by the attacker over all the paths in P d ). 1 The cost is relative to the budget and is thus unitless. We set the average cost to 1 so that a budget of k will allow the attacker to compromise k randomly selected links on the average, while the optimal strategy may compromise more or fewer. 2 For Bics, these are all the nodes with degree ≤ 2; for the other networks, these are all the nodes with degree one.
We evaluate the average performance degradation over the paths in P d (plus/minus one standard deviation) under each attack design, computed over 100 Monte Carlo runs.
First, we increase the budget k as in Table II to evaluate the impact of a stronger attacker. Fig. 2 shows that the proposed algorithm for the budgeted case (LP-R) achieves much bigger damage than the benchmark heuristics for a wide range of k, whereas the proposed algorithm for the unbudgeted case (Greedy GALS) is only effective when k is large. Moreover, III to evaluate the impact of monitoring more paths by network tomography. Fig. 3 shows that the damage achieved by all the attack strategies, especially the optimal strategy (ILP), decreases very slowly in |P |.
Discussion: The above results provide a number of insights for defending against DGoS attacks: (i) it is important to defend against intelligent attack strategies as they can achieve substantially more damage than simplistic ones, (ii) it is important to guard against compromised network elements (nodes/links) from the bottom up as even a few compromised elements can cause a big damage, and (iii) simply monitoring more paths is not sufficient to make network tomography robust against DGoS attacks. For (iii), however, the added paths in our experiments are only between the terminals, and it remains open how much protection can be achieved by carefully designing the paths, which is left for future work.
We have quantified the impact of DGoS attack by formulating and computing the maximum damage that an attacker can inflict on end-to-end communications through compromised links, without exposing these links to a tomography-based detection system based on both passive and active measurements. By establishing optimality conditions, we convert the attack design problem into novel combinatorial optimization problems and develop efficient algorithms. Our evaluations on real network topologies reveal significant damage of the DGoS attack and provide insights for future defenses.