I. INTRODUCTION

Network tomography [2] 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 [3], [4], [5], a Boolean model for localizing failures [6], [7], or various probabilistic models for accommodating performance fluctuations (see [2] 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 the link states (e.g., by imposing the same delay to 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. The impact of manipulated measurements on network tomography only started to be realized recently [8], [9], under linear observation models, where it was shown that the attacker can substantially degrade path performances while misleading network tomography to consider the manipulated links as wellperforming links. 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 network tomography to defend against attacks. In this work, we harden this intuition by quantifying the maximum damage a stealthy attacker can inflict on a network monitored by network tomography, and developing a defense strategy by selecting the probing paths to minimize this damage under a budget constraint.

A. Related Work

Network tomography is a rich family of network monitoring techniques that infer network internal characteristics from external measurements [2], [10]. Early works focused on besteffort solutions, which tried to find the most likely network state from given measurements, obtained by unicast [11], [12], [13], [14], multicast [15], [16], [17], [18], [19], [20], and their variations (e.g., bicast [21], flexicast [22], and back-toback unicast [23], [24], [20]). After observing that an arbitrary set of measurements is frequently insufficient for identifying all the link metrics [25], [12], [26], [27], [28], later works focused on either reducing the ambiguity (e.g., by imposing a tie breaker [13], [14], [29], or relaxing the objective [27], [30], [31]), or ensuring identifiability by carefully designing the monitor locations and the measurement paths (e.g., [3], [4], [5], [32], [33], [6], [7]). 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 [34], an algorithm was proposed to detect non-neutral links that discriminate packets on different paths, by detecting the links that cause the network tomography problem to be infeasible. There are also other works on detecting network neutrality violations [36], [37], [38], but these are engineering solutions utilizing information beyond end-to-end performances (e.g., ports and other confounding factors), falling out of the scope of network tomography. Studies on network neutrality differ fundamentally from our work in that they do not consider an intelligent adversary that intentionally controls the non-neutral links to evade detection. In contrast, only the following works considered intelligent attacks against network tomography. In [8] [35], optimizations were formulated to design the manipulations at given compromised nodes in order to cause performance degradation while scapegoating certain benign links as the cause of poor performance; however, the set of compromised nodes is not optimized. In [9], 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 on each path traversing at least one compromised link). However, [8], [35], [9] all assumed that the total performance degradation includes the degradation on all the measurement paths, which implies that only the paths carrying data flows are monitored by network tomography. Our attack model is most similar to [9], except that we accommodate both passive and active measurement paths for network tomography.

In terms of defense, existing solutions [8], [35] focused on detecting and localizing the attacker-controlled links, under the assumption that the attacker neglects certain measurement paths during attack design (and is hence exposed by these paths). In this work, we will consider a more challenging scenario, where the attacker is aware of all (possible) measurement paths, and thus the designed attack is undetectable by construction. Instead, we propose a proactive defense strategy that designs the measurement paths to minimize the maximum impact of all the undetectable attacks. Table I summarizes the comparison between our work and the above existing works.

B. Summary of Contributions

Our goal is to analyze the impact of DGoS attack and develop defenses in networks monitored by network tomography that employs both passive and active measurements.

1) We extend the attack model in [9] to include both passive measurement paths and active measurement paths, 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, and develop efficient algorithms by converting our problem to well-known integer programming problems.

3) Based on insights about the attack, we develop a defense strategy by selecting the measurement paths to minimize the maximum damage under a budget constraint. Although the optimal defense is very hard to compute as evaluating the maximum damage under a given set of paths is already NP-hard, we show that the complexity can be reduced by minimizing an upper bound on the maximum damage, for which a mixedinteger indefinite quadratic programming is formulated and a polynomial-time greedy algorithm is proposed.

4) We evaluate the proposed attack and defense strategies on a variety of real Internet topologies. Our evaluations show that: (i) the proposed attack strategies achieve significantly more performance degradation than intuitive alternatives and thus better reveal the potential damage of DGoS attack, (ii) compared to only monitoring passive measurement paths, adding a few active measurement paths selected by the proposed defense strategy can notably reduce the performance degradation, but (iii) if not selected carefully, then many more paths need to be monitored to achieve the same level of protection.

Roadmap. Section II formulates the generalized DGoS attack that accounts for both passive and active measurement paths. Section III analyzes the optimal attack and presents algorithms for attack design. Section IV presents our defense strategy and the associated algorithms. Section V evaluates the proposed attack/defense algorithms on real Internet topologies. Finally, Section VI concludes the paper.

II. PROBLEM FORMULATION

Table II summarizes the main notations used in this paper.

A. Network Model

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 P d ⊆ P denote the passive measurement paths (traversed by data packets) and P \ P d the active measurement paths (traversed by probes). 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 pre-attack link metrics are all normal, i.e., x j ≤ τ (∀l j ∈ L). Let τ max denote the maximum possible link metric, which is only used to ensure finite objective values and can be arbitrarily large. We assume that τ ≤ τ max .

Remark: We note that the solution to R x = y may not be unique as R may not have a full column rank [25], [12], [26], [27], [28]. In this case, network tomography can pick a solution by optimizing certain objective functions, e.g., minimizing the number of abnormal links [13], [14] or maximizing the posterior probability [29]. We do not assume any specific objective function in this work.

B. Attack Model

Suppose that an attacker wants to degrade the performance of paths in P d without being localized by network tomography. In this sense, P d also represents the set of paths targeted by the attacker (e.g., paths to/from certain hosts of interest).

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 a j (l j ∈ L) denote the cost of compromising link l j , and k a 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 [8], [9]:

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 .

The first assumption ensures that the attacker can only manipulate the performance of packets traversing at least one of the compromised links, and the second assumption ensures that the manipulation is feasible (e.g., the injected delay is non-negative). Moreover, to stay stealthy, the attacker must ensure 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 to x, according to which all the compromised links appear normal.

Remark: When R is rank-deficient, there are multiple feasible solutions to x, and the above conditions (i-ii) provide certain stealthiness in the sense that the detection system cannot say for sure that any of the compromised links are abnormal. If how network tomography resolves ambiguity (e.g., [13], [14], [29]) is known to the attacker, then he can achieve stronger stealthiness by imposing an additional constraint that the desired x (which indicates all the compromised links as normal) will be the solution selected by network tomography. We leave the investigation under this formulation to future work.

Using a change of variable z = R( xx), we formulate the problem of optimal attack design as follows:

where P n = {p i ∈ P : p i ∩ L m = ∅} and L n = L \ L m by definition. 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 [9, (1)] in that: (i) only degradation on the paths in P d is included in the objective, which allows us to model both passive and active measurements for network tomography, 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.

C. Defense Model

As the detection system cannot access individual links (hence the need of network tomography) and the DGoS attack is designed to evade detection, the best defense from the perspective of the detection system is to minimize the damage of such an attack. Specifically, while the passive measurement paths P d are usually dictated by the needs of data flows, the active measurement paths P \ P d are controlled by network tomography and thus can be designed to mitigate the attack. Similar ideas of designing the measurements have been widely applied to network tomography in the benign setting [3], [4], [5], [32], [33], [6], [7].

Let P c denote the set of candidate measurement paths (e.g., all the routing paths involving the terminals controlled by network tomography), including the paths in P d . Suppose that monitoring each path p i ∈ P c incurs a cost of c d i , and the defender (i.e., measurement designer) has a budget of k d . As passive measurements are byproducts of data communications and do not consume extra network resources, we assume that c d i ≡ 0 for all p i ∈ P d , which implies that P d ⊆ P .

We formulate the problem of optimal defense design as the following bilevel optimization:

The above problem is a Stackelberg game, where the defender is the leader, and the attacker is the follower. The two players interact via the bilevel optimization (2). At the upper-level, the defender selects the measurement paths P out of P c to minimize the worst-case performance degradation that can be caused by the attacker, where (2f) captures the budget constraint for the defender. At the lower-level, the attacker designs the parameters L m and x of the DGoS attack as in (1) to achieve the maximum damage on P d while evading detection.

Remark 1: The bilevel optimization implicitly assumes that the action of the defender (i.e., P ) is known to the attacker. This can happen if the attacker is able to monitor all the candidate paths (e.g., by intersecting traffic at the gateway router of a targeted organization) to identify the active paths traversed by data packets or probes. Generally, letting P denote the attacker's estimate of the paths monitored by network tomography, the assumption of P = P leads to a conservative defense strategy, and the actual attack can be nonstealthy (if P \ P = ∅) or less effective (if P \P = ∅). However, as the attacker's knowledge is unknown to the defender at the time of measurement design, this assumption allows us to plan for the worst case.

Remark 2: The defense formulation in (2) aims at mitigating the impact of the worst attack subject to budget and stealthiness constraints. If other attack strategies are used under the designed measurement paths P , they will be non-stealthy, more expensive, or less damaging. The objective value of (2) under a given P represents the maximum performance degradation that can be caused by a stealthy attack within budget k a if the paths in P are monitored, and the actual performance degradation can only be smaller.

D. Motivating Example

For the attacker, while intuitively compromising all the links gives the attacker the most flexibility in manipulating the measurements, and should therefore be the optimal strategy, we have shown that this is not true via a counterexample [9], since compromised links will also impose limitations on how much degradation can be injected on paths due to the stealthiness constraint. For the defender, intuitively monitoring the paths in P c \P d that cover more links in ∪ p∈P d p, in addition to P d , would better mitigate the performance degradation injected by the attacker on P d . However, we will show that this strategy is generally suboptimal. Consider the example in Fig. 1 (a), where P d = {p 3 }. Suppose that before the attack, each link has a delay of 10 ms, τ = 10 ms, and τ max = 1000 ms. Fig. 1 (b) shows the optimal attack parameters (L m , x) under the monitoring of paths {p 2 , p 3 , p 5 }, increasing the delay on p 3 by 3960 ms. In Fig. 1 (c), under the monitoring of paths {p 1 , p 3 , p 4 }, the maximum delay degradation on p 3 is only 1980 ms. Even though paths {p 2 , p 5 } cover more links on p 3 than paths {p 1 , p 4 }, monitoring {p 1 , p 4 } by active measurements will provide better protection for the data flow on p 3 , as these paths provide more fine-grained information for network tomography and hence make it harder for the attacker to inject delays without being localized. This example demonstrates the potential to limit the damage of stealthy DGoS attacks by carefully selecting the (active) measurement paths and the nontrivialness of such selection.

III. OPTIMAL ATTACK STRATEGY

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. Attack under Unlimited Budget

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 case of unlimited budget, we will establish sufficient/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 minimum 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 T (L m ), i.e., L m ∈ C * P .

Proof.

Step 1. We claim that if there exists an uncompromised path, then by carefully selecting a link to compromise, the objective value (1a) will increase monotonically. To show this, suppose that under an initial solution L (0) m , there is at least one uncompromised path p i * ∈ P (0) n . Then we are going to compromise a link on path

m , the optimization in ( 1) is reduced to:

Let x (0) be the optimal x for (3). We observe that there must exist a link l j * ∈ p i * for which x (0) j * ≤ τ , as otherwise (i.e., x (0) j > τ for all l j ∈ p i * ), we will have r i * x (0) > |p i * |τ ≥ r i * x, where |p i * | is the hop count of p i * . This contradicts with r i * x (0) = r i * x according to constraint (3b). As a result, for the link l j * , adding a constraint x j * ≤ τ is not going to change the optimal solution.

After compromising link l j * , i.e., for

where L

(1)

n ) is the new set of compromised (uncompromised) links, and P (1)

m ∪ {l j * }, any feasible solution to (3) with the added constraint x j * ≤ τ remains feasible for (4). Therefore, if f ( x) denotes the objective function (4a) and x (1) is the optimal x for (4), then f ( x (1) ) ≥ f ( x (0) ). This implies that one of the optimal solutions must be a cut in C P .

Step 2. Next, we are going to show that among all the cuts in C P , the optimal cut must be the one that minimizes the T (L m ). By definition, if L m is a cut of P , then P m = P and P n = ∅, which simplifies (1) for a given L m to

It is easy to see that the optimal solution to ( 5) is

Under this solution, the objective value of (5) equals

where only the first term of (6) depends on L m . As ττ max ≤ 0, maximizing ( 6) is equivalent to minimizing pi∈P d lj ∈Lm r ij = lj ∈Lm w j . Thus, all the cuts with the minimum T (L m ) are equally optimal for (1). Since as proved in step 1, one of the optimal solutions must be a cut in C P , every L m ∈ C * P is optimal for (1).

Remark: Theorem III.1 generalizes [9, 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 always necessary by a simple example. In the example shown in Fig. 2, suppose that n i=2 x i ≥ τ max . It is easy to see that the optimal solution can be

shows that L m ∈ C * P is not a necessary condition. Generally, it may not be necessary to compromise an active measurement path if its metric is sufficiently large (≥ τ max ). Nevertheless, we will show that compromising all the paths in P d is necessary under mild conditions.

Proof. We prove the claim by contradiction. Assume that an optimal solution to (1) is x (0) and

n such that p i * ∈ P d . We will show that the performance degradation can be strictly increased by compromising p i * .

Firstly, we claim that there must exist a link l j * ∈ p i * such that x (0) j * < τ , as otherwise, we will have

Next, consider another solution where

m ∪ {l j * } and x = x , defined as

It is easy to verify that this is a feasible solution to (1). Let F (L m , x) be the objective value of (1) under solution (L m , x). Then

Since p i * ∈ P d , l j * ∈ p i * (i.e. r i * j * = 1), and x (0)

) can be increased by another solution, which contradicts the assumption that (L

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. We know from Theorem III.2 that L m is optimal only if L m ∈ C P since P d = P . Then from Step 2 in the proof of Theorem III.1, we know that L m is optimal in C P only if it has the minimal T (L m ) among all the cuts in C P . This together with Theorem III.1 completes the proof.

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 T (L m ):

GALS generalizes the adversarial link selection (ALS) problem formulated in [9] in 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 [9], GALS is also NPhard. Moreover, similarly to the reduction of ALS to the weighted set cover (WSC) problem [9], GALS can also be 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 [39]

B. Attack under Limited Budget

In the general case of k a < ∞, 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 a 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).

Theorem III.4. As τ max → ∞, L m = L * m is optimal for (1) if and only if L * m is an optimal solution to GCALS.

Proof. We rewrite the objective function (1a) as

If l j ∈ L m , then x j ≤ τ by (1d). If l j ∈ L n , then x j ≤ min(τ max , min i: pi∈Pn,rij =1 r i x) by (1b,1c). For a large τ max , x j can achieve τ max if and only if l j ∈ L n . Thus, as τ max → ∞, the optimal value of (11) wrt x is approximately:

That is, the optimal objective value of (1) under a given L m is asymptotically proportional to T (L n ), which completes the proof.

2) Hardness and Algorithm Design: First, we will show that GCALS problem is NP-hard.

Theorem III.5. The GCALS problem (10) is NP-hard.

Proof. The idea is to show that GCALS is actually a generalization of GALS, and hence its NP-hardness is implied by the NP-hardness of GALS.

To this end, consider a special case of GCALS, where it is known that it suffices to optimize L m among the cuts in C P . If L m ∈ C P , then L n = L n , and hence

where the right-hand side is a constant, maximizing T (L n ) is equivalent to minimizing T (L m ), which is the GALS problem.

Next, we will develop a solution by formulating this problem as an integer linear programming (ILP) problem:

Lemma III.6. The optimization ( 14) is equivalent to the optimization (10), where l j ∈ L m if and only if α j = 1.

Proof. Let α j ∈ {0, 1} be the indicator of whether link l j is compromised:

which is subject to the budget constraint (14c). Due to constraint (14b), we know that (i) if there is at least one uncompromised path p i traversing link l j , i.e., ∃i such that h α h r ih = 0 and r ij = 1, then β j ≤ 0, and (ii) otherwise, i.e., h α h r ih ≥ 1 for every i such that r ij = 1, then β j ≤ 1. Moreover, constraints (14d-14g) collectively imply that γ j = β j (1 -α j ), i.e., the objective (14a) is to maximize lj ∈L β j (1 -α j )w j . Since (1 -α j )w j is non-negative, the optimal value of β j should equal its upper bound, i.e.,

Therefore, γ j = β j (1 -α j ) = 1 if and only if l j is an uncompromised link that is only traversed by compromised paths, i.e., l j ∈ L n . Thus, the objective (14a) is equivalent to (10a), which completes the proof.

The ILP formulation ( 14) allows us to leverage techniques for solving ILP to solve the GCALS problem (10). In particular, one commonly-used approach is to relax the ILP into an LP by relaxing the integer constraint (14g) 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. It remains open whether there exists a polynomial-time algorithm with approximation guarantee for GCALS.

The while loop (lines 5-10) is repeated O(|L|) times, and each iteration takes O(|L||P |) time. Thus the while loop takes O(|L| 2 |P |) time. Before the while loop, the LP (line 4) needs to be solved. In most cases, the time solving the LP dominates the overall time complexity. Therefore, the time complexity of Algorithm 2 is equivalent to solving a LP problem. For example, its complexity will be O(|L| 4 (|P | + |L|) 2.5 ) if using Vaidya's algorithm [40] to solve the LP.

IV. OPTIMAL DEFENSE STRATEGY

Armed with explicit characterizations of the optimal attack strategy, we now solve the defender's problem (2).

A. Defense under Unlimited Budget

Intuitively, monitoring more paths will increase the observability of network tomography and hence reduce the damage caused by undetectable attacks. We confirm this intuition in the following lemma.

Algorithm 2: LP relaxation with Rounding (LP-R) input : P, P d , k a output: Compromised links Lm 1 Lc ← L \ {lj ∈ L|c a j > k a }; // candidate links 2 Lm ← ∅; 3 Pm ← ∅; 4 (α j , β j , γ j ) l j ∈L ← solving the LP relaxation of ( 14 Lemma IV.1. Given any measurement paths P , monitoring one more path can only decrease the maximum damage in (2a).

Proof. We prove the lemma by arguing that removing (i.e., not monitoring) a measurement path can only increase the maximum damage. Let (L (0) m , x (0) ) be the optimal attack design when the set of measurement paths is P , achieving damage d(P ). After removing p ∈ P from the measurement paths, the attacker's problem remains the same, except that the constraint (2b) corresponding to p (if p is uncompromised) is removed. This means that (L (0) m , x (0) ) remains a feasible solution to the attacker's problem, and thus the maximum damage under measurement paths P \ {p} is no smaller than d(P ).

According to Lemma IV.1, if k d is unlimited, then we should simply monitor all the candidate paths, which minimizes the maximum damage that can be caused by the attacker.

B. Defense under Limited Budget

Now we focus on the more general and practical case when the defender has a limited budget k d < pi∈Pc c d i , which requires a careful selection of which candidate paths to monitor.

1) Hardness: We start by establishing the hardness of this problem.

Theorem IV.2. The defense optimization ( 2) is NP-hard.

Proof. We first prove that the decision version of the attack optimization ( 1) is NP-hard by a reduction from ALS [9], which aims at finding a cut of P with the minimum total traversal number by P . Given an instance of ALS, we can construct its corresponding attack optimization problem by setting P d = P , τ max = 2, τ = 1, and x j = 0, ∀l j ∈ L. The objective value for the constructed problem is

Moreover, the optimal objective value will be an integer, since under constraints (1b) (1c) (1d), the optimal value of x j would be the following:

As a result, the optimal objective value d * of the constructed attack optimization is an integer in [0, 2|P ||L|]. It can be computed in O(log(|P ||L|)) time by a binary search based on a solution to the related decision problem: is d * smaller than d? Since τ = 1 > 0 = x j , according to Corollary III.3, the optimal L * m for the constructed problem is the optimal solution to the corresponding instance of ALS. Thus, the optimal objective value OP T ALS of this instance of ALS can be derived from d * according to (6):

Since the time complexity of this reduction is polynomial and solving OP T ALS is NP-hard [9], the decision version of the attack optimization ( 1) is NP-hard.

Next, consider the decision problem related to the defense optimization (2): is there a design of P under which the maximum damage is smaller than d? Given a certificate P * ⊆ P c , the verifier must solve the decision version of the attack optimization for P = P * , which is NP-hard. In other words, the decision problem of the defense optimization can not be verified in polynomial time, unless P = N P . Since the related decision problem is not in NP (unless P = N P ), the defense optimization ( 2) is not in NP [41], and is thus NP-hard.

2) Algorithm Design: By Theorem III.4, when τ max is large, GCALS is asymptotically equivalent to the attack optimization (1). Although both problems are NP-hard, GCALS has an ILP formulation (14), which can be relaxed into an LP to be solved efficiently. Therefore, we propose to use the LP relaxation of GCALS as a proxy of the attack optimization (1) to guide the defense optimization.

Based on this idea, we reformulate the defense optimization (2) by replacing the lower-level optimization with the LP relaxation of ( 14):

where except for r i , all the vectors are column vectors, 0 |L| and 1 |L| denote |L|-dimensional vectors of all 0's or 1's, and all the inequalities are element-wise inequalities. Here δ := (δ i ) pi∈Pc is the defense decision variable, where

and α := (α j ) lj ∈L , β := (β j ) lj ∈L , γ := (γ j ) lj ∈L are attack decision variables as in (14). Other than introducing the upperlevel optimization, a minor difference between ( 20) and ( 14)

Find a path pi ∈ Pc with the largest V P (p i ; P d ,c a ,k a )

is the addition of (1 -δ i ) to (20b), which allows β j to be 1 as long as link l j is only traversed by compromised paths or unmonitored paths. In other words, the links only traversed by compromised paths or unmonitored paths will be used to explain the cause of performance degradation. It is easy to verify that for any given δ, (20) is the same as (14), except that (20h) relaxes the corresponding integer constraint (14g).

Relationship between (20) and (2): The relaxation of integer constraints in (20h) helps to reduce the computation complexity. Specifically, the defense optimization ( 2) is not in NP, but (20) is in NP, since given a certificate P * , its decision problem can be verified by solving as an LP. On the other hand, this relaxation changes the defense objective from minimizing the maximum damage to minimizing an upper bound on the maximum damage. Empirically, we find that even though the gap between the upper bound and the actual maximum damage is not negligible, the trend is preserved: minimizing the upper bound tends to minimize the maximum damage.

Greedy heuristic: The new formulation (20) enables us to apply the greedy heuristic to obtain a (possibly suboptimal) solution in polynomial time. Given a set of measurement paths P , define D(P ; P d , c a , k a ) as the optimal objective value of (20) under δ defined as in (21) (recall from Definition 1 that P d determines the traversal numbers w := (w j ) lj ∈L ). Given p i ∈ P , define V P (p i ; P d , c a , k a ) as the decrease of this objective value by monitoring one more path p i , i.e., V P (p i ; P d , c a , k a ) := D(P ; P d , c a , k a ) -D(P ∪ {p i }; P d , c a , k a ). Algorithm 3 iteratively selects paths into P such that in each iteration, the selected path maximizes ) if using Vaidya's algorithm [40] foot_1 . Although this complexity is a high-order polynomial in |L| and |P c |, we argue that it is acceptable in practice as the algorithm is only run offline. Moreover, while not theoretically guaranteed, we empirically find Algorithm 3 to be near-optimal for (20).

Exact solution: To solve (20) exactly, we convert the bilevel optimization into a single-level optimization, which can then be solved numerically for small problem instances.

Theorem IV.3. The optimization ( 20) is equivalent to the following optimization problem:

where a and d are defined as follows:

The coefficient matrix A is defined in (26), where R = (r ij ) pi∈Pc,lj ∈L is the matrix representation of P c as defined in Section II-A, I ∈ R |L|×|L| is the identity matrix, and M j ∈ R |L|×|L| (j = 1, . . . , |L|) is zero everywhere except that the j-th diagonal entry is 1.

Proof. The idea is to take the dual of the lower-level maximization problem in (20), which yields:

where b (a column vector) is the dual variable, δ is a given solution to the upper-level optimization problem, and the other parameters are defined as in (22). Since the lower-level optimization problem is an LP, its dual problem, which is a minimization, has the same optimal objective value due to the strong duality of LP. Once we transform the lowerlevel maximization problem into a minimization problem (25), the original minimax problem (20) becomes a minimization problem (22).

Let f := a T b denote the objective function of (22). Since f is twice differentiable, the Hessian 2 f can be evaluated. As f is quadratic in the variables δ and b, 2 f = 0. However, f is only linear in individual variables, and thus ∂ 2

for each δ i and ∂ 2 ∂b 2 j f = 0 for each b j , i.e., all the diagonal elements of 2 f are zero. This implies that the eigenvalues of H o w e v e r , t h ee i g e n v a l u e sc a n n o tb ea l lz e r o , a so t h e rw i s et h ee i g e nd e c om p o s i t i o n 2 f= Q T Λ Q = 0 , c o n t r a d i c t i n g w i t h 2 f= 0 .T h u s , 2 fm u s th a v ea tl e a s t o n en e g a t i v ee i g e n v a l u ea n da t l e a s to n ep o s i t i v ee i g e n v a l u e . T h a t i s ,fi sn o n -c o n v e x i n δa n d b , a n d ( 2 2 ) i s am i x e d -i n t e g e r i n d e fi n i t eq u a d r a t i cp r o g r amm i n g (M I IQ P )p r o b l em . M I IQ P i s g e n e r a l l yN P -h a r d ,b u tc a nb e s o l v e d f o r sm a l l i n s t a n c e s ( e . g . , b y t h eb r a n c h -a n d -b o u n da l g o r i t hm [ 4 2 ] ) . ( d e g r e e ≤2 ) ,a n dc om p u t e P c a s t h es e to fs h o r t e s tp a t h s ( i n h o pc o u n t )b e tw e e na l lp a i r so ft e rm i n a l s , w i t ht i e sb r o k e n a r b i t r a r i l y . W e t h e n r a n d om l y s e l e c ta s u b s e to fp a t h s i nP c a s P d , i . e . , t h ep a t h sc a r r y i n ga c t i v ed a t afl o w s .

V . PER FORMANC EE

3 ) O t h e rP a r am e t e r s : B e f o r et h ea t t a c k ,e a c hl i n kh a sa d e l a ys am p l e df r omt h ei n t e r v a lo f[ 0 , 2 0 )(m s )u n i f o rm l y a tr a n d om . T h ec o s to fc om p r om i s i n ge a c hl i n ki sd r aw n u n i f o rm l ya tr a n d omf r omt h ei n t e r v a lo f[ 0 , 2 ) , w h e r ea l o w e rc o s t i n d i c a t e sa m o r ev u l n e r a b l e l i n k( e . g . ,b u i l tb ya n o l d e r t e c h n o l o g yo r m a n a g e db ya l e s s t r u s t e dp r o v i d e r )a n d v i c ev e r s a .T h ec o s to fm o n i t o r i n gap a t h i nP c \ P d i sc h o s e n r a n d om l yb e tw e e n1a n d2 , m o d e l i n gt h ec o s to fr e c r u i t i n g t h ee n d p o i n t s t op a r t i c i p a t e i na c t i v em e a s u r em e n t s .N o t e t h a t t h e s ec o s t sa r er e l a t i v et ot h ea t t a c k / d e f e n s eb u d g e ta n da r e t h u su n i t l e s s . Al i n ki sc o n s i d e r e d" n o rm a l "i fi t sd e l a yi s w i t h i n 1 5 0m s , i . e . , τ=1 5 0.T h e m a x im umd e l a yo fa l i n k i ss e t t o 2 0 0 0m s , i . e . , τ m a x =2 0 0 0. 4 ) B e n c hm a r k s f o rA t t a c k :W e c om p a r e t h ep r o p o s e d a t t a c k d e s i g na l g o r i t hm s , G r e e d y GA L S(A l g o r i t hm1 )a n d L P -R (A l g o r i t hm2 ) ,w i t h t h r e eh e u r i s t i c sa n da no p t im a ls o l u t i o n : i )" R a n d om s e l e c t i o n " ( ' r a n d om ' ) :T h i sa l g o r i t hm r a n d om l y s e l e c t sc om p r om i s e d l i n k sw i t h i n t h eg i v e nb u d g e t . i i )" T o pt r a v e r s a l "( ' t o pt r a v e r s a l ' ) : B a s e do nt h ei n t u i t i o n t h a tc om p r om i s i n g t h e m o s t t r a v e r s e d l i n k sw i l lg i v e t h e a t t a c k e rt h e m o s tc o n t r o l ,t h i sa l g o r i t hms o r t st h el i n k s b y t h e i r t r a v e r s a ln um b e r s i nd e s c e n d i n go r d e r ,a n d t h e n s e l e c t sc om p r om i s e d l i n k s i n t h i so r d e rw i t h i n t h eb u d g e t . i i i )" L P r e l a x a t i n e a c h i t e r a t i o nu n t i le x h a u s t i n g t h ed e f e n s eb u d g e t ,w h e r e c o v e r ( p i ) := { l j ∈p i ∩( ∪ p ∈P d p ) \( ∪ p ∈Ps p ) }a n dP s i s t h es e to fp a t h s t h a ta r ea l r e a d ys e l e c t e d . i i i ) M I IQ P : T h i sa l g o r i t hmu s e st h e G u r o b io p t im i z e rt o d i r e c t l ys o l v e ( 2 2 ) ,w h i c h m i n im i z e sa nu p p e rb o u n do n t h em a x im umd am a g eg i v e nb y t h eL P r e l a x a t i o no f ( 1 4 ) . U n d e re a c hd e s i g no ft h e m e a s u r em e n tp a t h s P, w es o l v e t h ea t t a c ko p t im i z a t i o n( 1 )o p t im a l l y( b yfi r s tc om p u t i n g t h e optimal L m by solving the ILP ( 14) and then solving the remaining LP in x) to compute the maximum performance degradation under P . Due to the high complexity of the defense optimization (which is not even in NP), the optimal defense strategy cannot be computed in reasonable time even for small problem instances, and is hence skipped.

B. Experiment Results on Attack

To evaluate the potential damage of DGoS attack, we evaluate the average performance degradation over the paths in P d (plus/minus one standard deviation) under each attack design, computed over 20 Monte Carlo runs.

First, we increase the attack budget k a under the parameters in Table IV to evaluate attackers of growing strength. To understand the fundamental impact of DGoS attack, we set P = P c in this experiment, which corresponds to the case of unbudgeted defense according to Lemma IV.1. Fig. 3 shows that the proposed attack design algorithm for the budgeted case (LP-R) achieves much bigger damage than the benchmarks for a wide range of k a , whereas the proposed algorithm for the unbudgeted case (Greedy GALS) is only effective when k a is large. Moreover, the attacker can cause significant damage by compromising only a few links (e.g., causing > 1 second of delay per path in AS8717 when compromising an average of 2 links at attack budget 2). Note that LP-R is sometimes non-monotone in k a (e.g., for Colt), because it is generally suboptimal and hence may not utilize the budget optimally (recall that designing the optimal attack strategy is NP-hard according to Theorem III.5). Next, we fix k a and |P d | but increase |P | (and hence the number of active measurement paths in P \ P d ) under the parameters in Table V to evaluate the impact of monitoring more paths. To understand the protection provided by simply monitoring more paths (in addition to P d ), we randomly select the active measurement paths from P c \ P d in this experiment; the results under more sophisticated measurement design will be shown in Section V-C. Fig. 4 shows that the damage achieved by all attack strategies decreases with the increase of |P |, verifying the intuition that monitoring more paths makes network tomography more effective at thwarting attacks.

C. Experiment Results on Defense

To evaluate the protection provided by carefully designing the (active) measurement paths, we evaluate the average performance degradation over P d (plus/minus one standard deviation) under each design of P and the corresponding optimal attack strategy, computed over 20 Monte Carlo runs.

First, we fix the attack budget k a as in Table V and gradually increase the defense budget k d . Fig. 5 confirms that monitoring a larger set of paths by active measurements helps to protect data flows from stealthy DGoS attacks regardless of how the active measurement paths are selected. However, by carefully selecting these paths, we can achieve the same level of protection at a fraction of cost. For example, the proposed solution (Greedy Defense) achieves almost the same protection as monitoring all the 95-180 candidate active measurement paths by only monitoring 10 paths. Moreover, Greedy Defense performs as well as MIIQP while being more computationally efficient (MIIQP is skipped for AS 8717 due to its high complexity, which is exponential in the worst case). Next, we vary the attack budget k a while fixing the defense budget k d as in Table VI. Fig. 6 confirms the efficacy of Greedy Defense when compared to randomly selecting the active measurement paths (random) and selecting the active measurement paths to cover the most links carrying data flows (max cover), which are in turn better than not performing active measurements at all as shown in Fig. 5. In particular, the intuitive heuristic of max cover performs as poorly as random selection, as it fails to model a strategic attacker as done by Greedy Defense. The cost of using Greedy Defense is its computational complexity, e.g., at k d = 10, running this algorithm on average takes 56.85 seconds for BTN, 61.15 seconds for Bics, 1315.7 seconds for Cogent, 808.6 seconds for Colt, 1067.35 seconds for AS8717, 1310.5 seconds for AS20965. Nevertheless, we argue that this cost can be worthwhile in practice as the computation will occur offline. Meanwhile, once the attacker has an unlimited budget, defenses based on designing the measurement paths are no longer effective as the attacker can compromise every path, and other defenses are needed.

Summary:

The above results provide a number of insights about DGoS attacks and their defenses: (i) it is important to model intelligent attack strategies as they can achieve substantially more damage than simplistic strategies; (ii) while monitoring more paths always helps the defender, carefully selecting the measurement paths can achieve the same protection at a much lower cost; (iii) even under optimized design of measurement paths, the attacker can still cause significant damage by manipulating internal network elements, signaling the importance of securing network elements as a first line of defense. We note, however, that the third conclusion is drawn under the limitation that measurement paths must start/end at terminals and follow the shortest paths, and it remains open how much protection can be achieved by deploying dedicated monitors and/or controlling the routing of probes, which has been used to ensure identifiability for network tomography in the benign setting [3], [4], [5], [32], [33], [6], [7]. We leave further investigation of this idea to future work.

VI. CONCLUSION

By formulating and analyzing a generalized DGoS attack, we quantified the maximum damage that an attacker inside the network can inflict on end-to-end communications without exposing the compromised links to network tomography, while modeling both passive and active measurements. By establishing optimality conditions, we connected the optimal attack design problem to well-known optimization problems and developed efficient algorithms. We further developed a polynomial-time defense algorithm by formulating and solving a Stackelberg game to optimize the measurement paths in the presence of a limited budget and an intelligent attacker. Our evaluations on real network topologies highlighted the importance of modeling intelligent attackers, and validated the efficacy of the proposed defense. Meanwhile, our results also showed that monitoring the default routing paths between communicating terminals may not be sufficient, indicating the need for the development of further defenses.