T IMELY and accurate knowledge of network internal state (e.g., link delays/jitters/loss rates/bandwidths) is essential for many network management functions such as traffic engineering, load balancing, and service placement, which actively adapt control parameters such as the routes, the rates, and even the destinations (e.g., via service placement) according to the current network state.
Traditionally, network administrators obtain the network state by directly measuring internal network elements through local support (e.g., SNMP agents) or special diagnostic tools (e.g., traceroute). This approach has the limitation that it requires the support of internal network devices, e.g., to run SNMP agent or respond to ICMP probes, which has severe limitations in networks where such support is unreliable [2]- [4] or unavailable [5], [6].
Network tomography [7] provides a powerful approach for monitoring the internal state of closed networks. Instead of directly measuring the internal elements, network tomography Manuscript received January 24, 2020; revised October 26, 2020 and December 13, 2020; accepted February 5, 2021; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor W. Lou. This work was supported by NSF under Award 1813219. A preliminary version of this work was presented at INFOCOM '20. (Corresponding author: Cho-Chun Chiu.) The authors are with the Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16801 USA (e-mail: cuc496@psu.edu; tzh58@psu.edu).
Digital Object Identifier 10.1109/TNET.2021.3058230 infers the states of these elements (e.g., link delays) from end-to-end measurements (e.g., path delays) between special nodes participating in monitoring, referred to as monitors.
As network tomography only requires the cooperation from monitors, it has broad applications in monitoring networks where only a subset of nodes cooperate, e.g. the Internet [2]- [4], overlay networks [8], and all-optical networks [5], [6]. Despite substantial research on network tomography, most existing solutions hinge on a fundamental assumption: the measurements correctly reflect the performance of measurement paths. Consider the canonical application of inferring additive link metrics (e.g., delays, jitters, log-success rates) from the sum metrics on measurement paths. As illustrated in Fig. 1 (a), normally the measured path metrics will equal the sum of link metrics on each path, yielding a linear observation model: Rx = y, where x = (x j ) lj ∈L is the column vector of unknown link metrics (L: set of links), y = (y i ) pi∈P is the column vector of measured path metrics (P : set of measurement paths), and R = (r ij ) pi∈P,lj ∈L is the measurement matrix with r ij ∈ {0, 1} indicating whether path p i traverses link l j . Network tomography infers the link metrics by "inverting" the observation model, i.e., solving for x that satisfies R x = y (the solution may not be unique).
However, if some links are controlled by an attacker (referred to as compromised links) as illustrated in Fig. 1 (b), then the attacker can manipulate the measurements on paths traversing these links, e.g., by introducing additional delays, jitters, or losses. This yields a modified observation model: Rx + z = y , where y is the vector of observed path metrics under the attack, and z = (z i ) pi∈P is the vector of manipulations controlled by the attacker. For example, the attacker can be a malicious Internet Service Provider (ISP) [9] that tries to attack a targeted content provider, whose paths to clients are modeled by P , from a set of links it controls in the public Internet. Another example is a hacker that launches an attack on a targeted institutional network by remotely controlling its backdoor-infected routers [10]. Note that the modified observation model is different from R(x + z) = y , as the attacker can manipulate packets on different paths differently at the same link, e.g., delaying packets belonging to one path but not delaying packets belonging to another path. An unsuspecting network tomography algorithm will try to explain the measurements according to the original observation model by trying to find x satisfying R x = y . This can cause many issues, such as lack of feasible solutions [11] and incorrect fault diagnosis [12].
In this work, we aim to understand the fundamental limit of a stealthy attacker in maximally degrading the performance of end-to-end communications without being localized by network tomography. Such understanding will not only quantify the limitation of existing network tomography algorithms but also provide insights for the design of defense mechanisms.
Since introduced by Vardi [13], network tomography has expanded to a rich family of network monitoring techniques that infer network internal characteristics from external measurements [7], [14]. Early works focused on best-effort solutions, which tried to find the most likely network state from given measurements, obtained by unicast [15]- [18], multicast [19]- [24], and their variations (e.g., bicast [25], flexicast [26], and back-to-back unicast [24], [27], [28]). After observing that an arbitrary set of measurements is frequently insufficient for identifying all the link metrics [8], [16], [29]- [31], later works aimed at either reducing ambiguity by imposing a tie breaker (e.g., [17], [18], [32]) or relaxing the objective (e.g., [8], [33], [34]), or ensuring identifiability by carefully designing the monitor locations and the paths to measure [6], [35]- [43]. All these works assume a benign setting, where the links behave consistently.
In contrast, very few works have considered network tomography in an adversarial setting, where links can behave inconsistently for different paths. In [11], the problem is tackled in the context of a non-neutral network, where some links can discriminate packets sent on different paths. In [12], the problem is tackled in the context of an attacker that can manipulate the measurements traversing malicious nodes, with a primary goal of scapegoating certain benign links as the cause of poor performance. While our problem setting is similar to [12], our results differ significantly as explained in Section II-C.
The main contributions of this work are: 1) We formulate a novel attack, called stealthy DeGrading of Service (DGoS) attack, that aims at maximally degrading the performances of end-to-end communications by manipulating the performances of compromised links, without letting these links localized by network tomography. 2) To understand the fundamental limit of this attack, we develop algorithms to explicitly design which links to compromise and how to manipulate the performances of these links. We show that selecting which links to compromise is a novel combinatorial optimization problem that is NP-hard. By linking this problem to known NP-hard problems, we leverage existing algorithms to achieve guaranteed approximation.
3) We further consider a budget constraint on the cost of compromising links. We show that the constrained link selection problem is another novel combinatorial optimization problem that is also NP-hard. By relaxing the objective function, we again link this problem to a known NP-hard problem that allows us to leverage an existing approximation algorithm. 4) Our evaluations on real topologies show that the proposed attack can significantly degrade the communication performance (by injecting 4-30 seconds of delay per path) without exposing the compromised links to network tomography.
Roadmap. Section II formulates our problem. Section III designs the attack in the unconstrained case, which is evaluated in Section IV. Section V addresses the constrained case. Finally, Section VI concludes the paper.
We model the network monitored by network tomography 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 (e.g., average link delay). We assume that these link metrics are additive, i.e., the metric of a path equals the sum of its link metrics, which is a canonical model representing important performance metrics including delays, jitters, logsuccess rates, and many other statistics.
Suppose that a set of users of the above network (or their proxy) send traffic through G along a set of paths P , and use network tomography to monitor the received performances at individual links. Using network tomography to monitor the performance of individual links from path-level measurements is a well-established technique that is particularly relevant to the Internet [14], due to the opaque nature of the ISP networks to the providers of host-based distributed systems and applications. In host-based distributed systems such as virtual private networks (VPNs) and content distribution networks (CDNs), as well as adaptive applications such as streaming media and multiplayer gaming, a tomography-based overlay monitoring system can detect periods of degraded performance within seconds, thus facilitating informed adaptation of overlay paths and communication patterns [44].
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 seeks to find a solution x to the link metrics that can explain the measurements, i.e., R x = y.
We note that the solution is generally non-unique as R may not be full-column-rank. This issue, known as the lack of identifiability, has been widely recognized [8], [16], [29]- [31]. Instead of making a limiting assumption that R must be fullcolumn-rank as in [12], we allow an arbitrary R, and consider a generic network tomography solver that can compute the set of all feasible solutions.
1) Threat Model: Suppose that an attacker attempts to degrade the performance of P by manipulating the performances of compromised links. Let L m ⊆ L denote the set of compromised links and L n = L \ L m the set of uncompromised links. Accordingly, the paths P m ⊆ P traversing at least one compromised link are called compromised paths, and the remaining paths P n = P \ P m are called uncompromised paths. The attacker can only control the compromised links.
One possible attack scenario is an ISP-based attacker that tries to degrade the Quality of Service (QoS) of a targeted content provider as studied in the context of network neutrality [11], except that the ISP itself is not involved in the attack (hence only the links compromised by the attacker will participate). In this case, P contains all the paths within this ISP network that are between the gateway router to the content provider and the other gateway routers. In this scenario, we model a more intelligent adversary than [11] that avoids causing infeasibility of the network tomography problem and thus evades detection by the existing detector in [11]. Similar scenario exists when targeting a client network.
Another possible attack scenario is an attacker in a legacy underlay network that tries to degrade the performance of an overlay network used to implement state-of-the-art control algorithms [45]. In this case, P contains all the paths within the underlay network that connect the overlay nodes. In this scenario, we model a novel type of adversarial intervention that controls the forwarding performance, complementing the existing model in [45] that controls the forwarding direction.
Our model implicitly assumes that all the measurement paths monitored by network tomography are fixed and known to the attacker. Assuming fixed measurement paths is a standard assumption in network tomography, which underlies nearly all tomography-based inference algorithms. Meanwhile, while the exact set P of paths evaluated by network tomography will not be observable to the attacker, the attacker can construct a possibly larger set P of potential measurement paths with basic knowledge of the attacked network G, e.g., topology, routing, and ingress/egress points (e.g., gateway routers). If P ⊂ P , it is easy to see that a stealthy attack designed for P remains stealthy for P (in the sense modeled by (2)). However, the effectiveness of the attack can be suboptimal due to unnecessary constraints induced by paths in P \ P . We will evaluate this case later (see Fig. 10).
2) Attack Optimization: Let z = (z i ) pi∈P denote the vector of manipulations, where z i is the increment in the metric of path p i ∈ P caused by the attacker. It is easy to see that z must satisfy the following constraints [12]:
1) Only the metrics of compromised paths can be manipulated, i.e., z i = 0 for any p i ∈ P n . 2) Path performances can only be degraded (not improved) due to manipulation, i.e., z i ≥ 0 for any p i ∈ P m . Moreover, to stay stealthy, the attacker must preserve feasibility of the network tomography problem to hide the presence of artificial manipulations, i.e., after the manipulations, there must exist at least one solution x that satisfies R x = Rx + z. In addition, he must protect the compromised links from detection. As a concrete example, we consider threshold-based bad link detection, where the state δ j (1: bad, 0: good) for link l j is inferred as
Here, τ denotes the detection threshold (e.g., the maximum normal link delay). Threshold-based detection is widely used in network monitoring systems (e.g., NetFlow Analyzer [46], OpManager [47]), and threshold-based bad link detection is a natural application for network tomography. To evade such detection, our attack model requires that among all the feasible solutions to x, there must be at least one solution that does not flag any of the compromised links as bad links. In practice, there may also be an upper bound on link metrics, denoted by τ max , e.g., the maximum duration a packet can be buffered at a network interface without being dropped. To avoid trivial cases, we assume that x j ≤ τ ≤ τ max for all l j ∈ L.
We formulate the attacker's goal as the following optimization, called the stealthy DeGrading of Service (DGoS) attack:
This is an optimization of L m and x, where L m specifies the links to compromise, and x, denoting (one of the feasible solutions to) the inferred link metrics, is used to compute the actual manipulations z to inject onto the paths by
Computing the manipulations by (3) automatically ensures feasibility of the network tomography problem. Note that this does not require the compromised links to behave consistently across paths, as illustrated in Fig. 2.
In words, the objective (2a) is to maximize the total performance degradation on paths in P , measured by the increase in the sum path metric. Constraints (2b,2c) ensure that manipulations are feasible, i.e., only performed on compromised paths to degrade the performance. Constraint (2e) ensures that the attack cannot be localized by network tomography, as all the compromised links perform normally according to the inferred link metrics. Note that x only represents the link performances perceived by network tomography, which are generally not the same as the actual link performances. As is shown later, an intelligent attacker can leverage this difference to inject performance degradation on end-to-end communications at compromised links, while causing network tomography to blame the degradation on some uncompromised links (thus keeping the compromised links undetected). Note that this attack is only designed to evade threshold-based detection; for more sophisticated detection systems (e.g., those examining the distribution of link metrics), randomization of the upper bounds in (2d)-(2e) will be needed to generate a plausible x.
Remark 1: The above formulation is based on an optimistic constraint, i.e., there exists a possible solution to the link metrics that does not flag any of the compromised links as bad links, which ensures that the provider cannot say for sure that any of the attacker-controlled links is the cause of poor endto-end performance. In the case of rank-deficient R, there will be other solutions that possibly flag some of these links. One way of achieving stronger stealthiness is to include additional constraints to ensure that the desired x will be the solution selected by network tomography (e.g., flagging the fewest links among all possible solutions), which requires additional knowledge of the adopted network tomography algorithm. The strongest stealthiness is achieved by requiring that no feasible solution to R x = Rx + z will flag any of the compromised links. As a first step towards understanding the potential damage of DGoS attacks, we will focus on the formulation in (2) and empirically evaluate its stealthiness under a practical tomography-based detector (see Fig. 11), while leaving the detailed study of other formulations to future work. Note that in the case of full-column-rank R as assumed previously [12], these formulations become the same.
Remark 2: For clarity, we will present all the results from the perspective of an attacker. However, our results can also be interpreted from the perspective of a network provider that uses network tomography to validate link performances. In this case, the optimal objective value of (2) reveals the maximum damage that an in-network adversary can inflict on end-to-end communications without being localized, and the corresponding decision variables (particularly L m ) specify the most vulnerable links that can be manipulated to inflict the maximum damage. Thus, our results can be used to analyze network vulnerability and recommend high-value links to protect.
Remark 3: Our work differs fundamentally from the existing works [11], [12] that also considered network tomography in an adversarial setting. Specifically, although [11] proposed an algorithm to detect links that behave inconsistently on different paths (i.e., non-neutral links), the algorithm only works when the inconsistent links cause infeasibility of the network tomography problem, and thus cannot handle our attack model that always ensures feasibility. Moreover, although the attack model studied in [12] is conceptually similar to ours in that the attacker also tries to fool network tomography while degrading path performances, their results substantially differ from ours in that: (i) the attacker in [12] is required to mislead network tomography to detect certain uncompromised links as bad links, while we do not impose such constraints; (ii) [12] assumes the measurement matrix to be full-column-rank, which is frequently violated in practice [8], [16], [29]- [31], while we do not make such an assumption; (iii) most importantly, [12] assumes that the set L m of compromised links is given, while we treat it as a decision variable, which allows us to model a more intelligent attacker that strategically places its attack. In fact, as is shown later, the selection of L m significantly impacts the capability of an attack and is thus the focus of our work. Our solutions on optimizing L m can also be used to identify the most vulnerable links to protect from a network provider's perspective.
Consider the example in Fig. 2 (a). Suppose that before the attack, each link has a delay of 10 ms, τ = 150 ms, and τ max = 2000 ms. Fig. 2 (b) shows the optimal manipulations under an intuitive selection of L m -compromising all the links. In this case, the attack can cause 2240 ms of extra delay in total, by injecting a delay of z i onto path p i at some of the compromised links traversed by p i . Fig. 2 (c) shows the optimal manipulations under another selection of L m , Fig. 2.
Example: (a) input, (b) optimal manipulations under one Lm, (c) optimal manipulations under another Lm.
which, although having fewer compromised links, is able to cause 15190 ms of extra delay, as the uncompromised links l 3 and l 5 can be used to explain the large delays of paths p 1 , p 2 , p 4 , p 5 , p 6 to network tomography without exposing the compromised links. Note that the inferred link metrics can differ from the actual metrics, and the compromised links can behave inconsistently across paths, e.g., in Fig. 2 (c), link l 1 injects no more than 280 ms of delay onto p 3 but 4120 ms of delay onto p 2 . This example shows that DGoS attack can cause large damage without being localized, and the amount of damage critically depends on the selection of L m . III. OPTIMAL ATTACK STRATEGY Although ( 2) is a joint optimization of both L m and x, we will show that the main challenge is in optimizing L m , which can be reduced to a novel variation of the minimum cut problem.
Given the set of compromised links L m , (2) is a linear program (LP) in x that can be solved in polynomial time by standard LP solvers, and the result gives the optimal manipulation vector (under the given L m ) by (3). Nevertheless, there are several simplifications that can be used to speed up the solution for large networks.
First, we observe that constraint (2c) has no effect on the optimal solution, as it only imposes a lower bound on x, while the objective (2a) tries to increase x. We can thus drop this constraint without changing the optimal solution to x.
Furthermore, we observe that the dimension of the solution space can be reduced. To this end, we rewrite (2) after dropping constraint (2c) in a vector form:
where 1 |Pm| is the 1×|P m | vector of 1's, R m = (r i ) pi∈Pm and R n = (r i ) pi∈Pn are the sub-measurement matrices representing all the compromised/uncompromised paths, respectively, and φ := (φ j ) lj ∈L is the vector of upper bounds on x j in (2d,2e), i.e.,
(5)
The "≥" in (4c) means element-wise ≥. To reduce the dimension for optimization (4), we perform a change of variable as follows. Since x j ≤ τ (∀l j ∈ L), it is easy to see that x = x is a feasible solution to (4). Let B be a matrix whose columns form a basis of null(R n ), the null space of R n . Let nullity(R n ) denote the nullity of R n , i.e., the dimension of null(R n ). Then x = Bc + x will always satisfy R n x = R n x for any (nullity(R n ) × 1)-vector c. Substituting x by Bc + x, (4) is transformed into:
Compared to (4), the number of decision variables in ( 6) is reduced from the number of links to the nullity of R n . By the rank-nullity theorem, rank(R n ) + nullity(R n ) = |L|, and hence the reduction will be significant when rank(R n ) is large, i.e., the number of linearly independent uncompromised paths is large.
To facilitate the optimization of L m , we first investigate the property of the optimal solution. As is shown in Section II-D, simply compromising all the links is generally suboptimal, as the attacker will have to make all the link metrics appear normal (i.e., x j ≤ τ for all l j ∈ L), which limits the amount of performance degradation he can inject on each path.
Generally, compromising a link l j can have two contradicting effects:
1) previously uncompromised paths that traverse l j can now be controlled by the attacker, which removes some constraints of the type (2b) and hence may increase the objective value; 2) instead of constraint (2d), l j will be subject to a tighter constraint (2e), which may decrease the objective value. Due to these contradicting effects, it is not obvious what is the optimal set of links to compromise.
Our main result is a closed-form characterization of the optimal set of compromised links. To present this result, we introduce the following definitions.
Definition 1: Given a set of paths P , we define: 1) the traversal number of link l, denoted by w l , as the number of paths in P that traverse link l; 2) a cut C of P as a subset of links such that every p ∈ P traverses at least one link in C; 3) the minimum-traversal cut C * of P as the cut of P with the minimum total traversal number, i.e., l∈C * w l ≤ l∈C w l for any cut C. Theorem 1: The optimal set of compromised links L * m (i.e., the optimal solution to L m in (2)) is the minimumtraversal cut of P .
We will prove this theorem in two steps.
Step 1 is to show that L * m must be a cut of P , as otherwise the attacker will be able to improve his objective value by compromising one more link.
Lemma 1: Suppose that for the initial set of compromised links L (0) m , there is at least one uncompromised path p i * . Then there must exist an uncompromised link l j * ∈ p i * , such that compromising l j * increases the total performance degradation, i.e., Γ(L
n ) be the initial set of compromised (uncompromised) paths, and x (0) be the optimal solution to x when L m = L (0) m . By assumption, p i * ∈ P (0) n . First, 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 on p i * . This contradicts with r i * x (0) = r i * x according to constraint (2b).
Next, for the above link l j * , adding a constraint x j * ≤ τ to (2) will not change the optimal solution when L m = L (0) m . That is, x (0) remains an optimal solution to the following optimization in x
Note that we can omit constraint (2c) as explained in Section III-A. Moreover, after compromising link l j * , i.e., for
where L
(1)
n ) is the new set of compromised (uncompromised) links, and P (1)
Finally, since
m ∪ {l j * }, any feasible solution to (7) remains feasible for (8). In particular, x (0) is a feasible solution to (8), with an objective value of pi∈P (0)
Thus, under the optimal solution to (8), the objective value
Step 2 is to show that among all the cuts, L * m must be the one that minimizes the total traversal number.
Lemma 2: Among all the cuts of P , the optimal set of links to compromise is the cut with the minimum total traversal number.
Proof: By definition, if L m is a cut of P , then P m = P and P n = ∅, which simplifies (2) for a given L m to max
It is easy to see that the optimal solution to ( 9) is
Under this solution, IEEE/ACM TRANSACTIONS ON NETWORKING the objective value of (9) equals pi∈P (10) where m i is the number of compromised links on path p i and |p i | is the total number of links on p i . Only the first term (ττ max ) pi∈P m i depends on L m . As ττ max ≤ 0, maximizing ( 10) is equivalent to minimizing pi∈P m i . We further note that
where ½ • is the indicator function. Thus, the optimal solution to L m among all the cuts is the cut with the minimum total traversal number.
Proof of Theorem 1: By Lemma 1, L * m must be a cut of P . Then by Lemma 2, it must have the minimum total traversal number among all the cuts. Therefore, L * m must be the minimum-traversal cut.
Remark: The minimum-traversal cut of P may not be unique. From the proof of Theorem 1, we see that all the minimum-traversal cuts are equally optimal.
Theorem 1 implies that given a set of targeted paths P , the optimal set L m of links to compromise is the solution to a novel combinatorial optimization problem as follows.
Definition 2: Given a set of paths P , the adversarial link selection (ALS) problem is to find the cut of P with the minimum total traversal number.
Below we show the hardness of ALS by connecting it to several well-known hard problems in combinatorial optimization in both the general case and a nontrivial special case.
1) Hardness of General ALS: First, consider the general case of ALS for an arbitrary set of paths P .
Theorem 2: ALS for an arbitrary path set P is NP-hard.
Proof: To show this, we consider the corresponding decision problem: determine whether a set of paths P has a cut with a given total traversal number T . We will prove that the decision version of ALS is NP-hard by showing a reduction from the exact cover problem [48].
Given a set of elements of E = {e 1 , e 2 , . . . , e n } and a collection S of subsets of E, an exact cover is a subcollection S * of S such that each element in E is covered once and only once by sets in S * . To determine if there exists an exact cover is NP-complete [48].
The exact cover problem can be reduced to the following instance of ALS. We construct a set of paths P = {p 1 , p 2 , . . . , p n } in one-one correspondence with the set of elements E = {e 1 , e 2 , . . . , e n }. Similarly, we construct a set of links L = {l 1 , l 2 , . . . , l m } in one-one correspondence with the collection of sets S = {s 1 , s 2 , . . . , s m }. The relationship between the paths and the links is such that link l i is traversed by path p j if and only if set s i covers element e j . Note that such construction is always possible as we allow P to contain 2) Hardness of All-Possible-Paths ALS: Now consider a special case where P contains all possible paths between a given set K of terminals. This case models networks that employ advanced routing mechanisms such as source routing or Software Defined Networking (SDN), that allow traffic to be routed on any path between a pair of terminals. We call the ALS problem in this special case all-possible-paths ALS.
All-possible-paths ALS can reduce to the Multiway Cut problem [49]. Also known as the Multiterminal Cut problem, the Multiway Cut problem is a graph division problem, where given an undirected graph G(V, E) with link weights w : E → R + and a set of terminals K ⊆ V , we want to find a subset of links with the minimum total weight to cut all the paths between the terminals. When the number of terminals equals 2, the Multiway Cut problem becomes the min-cut problem, which can be solved efficiently by the max-flow algorithms. We see that all-possible-paths ALS is a special case of Multiway Cut, where the weights are the traversal numbers. We note that the two problems are not equivalent: in Multiway Cut, the link weights are arbitrary; in all-possiblepaths ALS, the link weights are the traversal numbers, which are determined by the network topology and the locations of terminals.
It is known that Multiway Cut is NP-hard, even in a very special case when all the links have unit weights.
Theorem 3 [49]: The Multiway Cut problem is NP-hard for all |K| ≥ 3, even if all the link weights are equal to 1.
The hardness of all-possible-paths ALS still remains an open question. Based on Theorem 3, we conjecture that allpossible-paths ALS is NP-hard, since it is also a special case of Multiway Cut.
As ALS is NP-hard, there is no polynomial-time exact algorithm for it unless P = NP. As we mentioned, ALS reduces to Weighted Set Cover (WSC), and all-possible-paths ALS reduces to Multiway Cut. Below we will use known approximation algorithms designed for WSC and Multiway Cut to solve ALS and all-possible-paths ALS, respectively.
1) The Greedy Algorithm for ALS: Given a set of elements E = {e 1 , e 2 , . . . , e n } and a collection S = {s 1 , s 2 , . . . , s m } of subsets of E, where each s i has a weight of w i , WSC aims at finding the subcollection S * that covers E with the minimum total weight.
We reduce ALS (for arbitrary P ) to WSC as follows. Given a set of paths P = {p 1 , p 2 , . . . , p n } traversing a set of links L = {l 1 , l 2 , . . . , l m }, we construct a set of elements E = {e 1 , e 2 , . . . , e n } in one-one correspondence with the paths, and a collection of sets S = {s 1 , s 2 , . . . , s m } in oneone correspondence with the links, such that set s i covers element e j if and only if link l i is on path p j , as illustrated in Fig. 4. Each set s i has a weight w i that equals the traversal number of link l i . It is easy to see that finding the cut with the minimum total traversal number is equivalent to finding the subcollection of sets to cover all the elements with the minimum total weight. We note that in the instance of WSC, the weight of a set always equals its cardinality (i.e., w i = |s i |), and thus ALS is a special case of WSC.
We apply a well-known greedy algorithm [50], designed for solving WSC, to the ALS problem. The algorithm iterates until all the paths are compromised, where in each iteration, it picks a link with the smallest cost-value ratio and adds the paths traversing it to the set of compromised paths. For a link l, we define the cost-value ratio by |P l | |P l \Pm| , where P l is the set of paths traversing link l. Since the link weight equals |P l |, this ratio is the cost we pay for each newly compromised path, if link l is selected. The pseudocode is shown in Algorithm 1.
Although straightforward, this greedy algorithm is known to have the best approximation guarantee for WSC [50]. Applied to our problem, it guarantees the following. However, our ultimate goal is to maximize the performance degradation measured by (2a). We can substitute pi∈P m i by T greedy in (10) to get the corresponding objective value.
Corollary 1: Using Algorithm 1 to select the compromised links and the LP (6) to compute the manipulations achieves a total performance degradation of (12) where T greedy and T opt are defined as in Theorem 4.
2) CKR Relaxation With Rounding for All-Possible-Paths ALS: As mentioned in Section III-C.2, all-possible-paths ALS reduces to the Multiway Cut problem, which means we can apply algorithms for Multiway Cut to all-possible-paths ALS.
Calinescu et al. [51] proposed an approach called CKR relaxation for Multiway Cut, for which it has been proved that it is NP-hard to achieve a better integrality gap than CKR relaxation for any fixed number of terminals, assuming the Unique Games Conjecture to hold [52]. In a minimization problem, the integrality gap is the ratio between the objective value of the optimal integer solution and that of its relaxation, i.e., OPT int /OPT relaxation . We first formulate the Multiway Cut problem as an integer program, and then introduce its CKR relaxation. Given a set V of nodes, a set E of links with weights (w v,v ) (v,v )∈E , and a set K (K ⊆ V ) of terminals, the Multiway Cut problem aims at solving
where x v,t is the decision variable indicating whether node v will be connected to terminal t after the cut. By relaxing the integer constraint (13d) and replacing |x v,tx v ,t | by a new variable y v,v ,t , we get the following:
which is an LP [50], i.e., an LP relaxation of (13).
For each node v and each terminal t, the solution xv,t to the LP relaxation can be viewed as the probability of assigning v to (the connected component containing) t after the cut. A rounding scheme is used to convert this fractional value to either 0 or 1, subject to the constraint (14b). Different rounding schemes lead to different approximation factors. Specifically, the randomized rounding scheme achieves an approximation factor of 1.5 [50], and the best-known rounding scheme can achieve an approximation factor of 1.2965 [53]. Finally, given the rounded value of x v,t (∀v ∈ V, t ∈ K), the cut is the set of all the links whose endpoints are assigned to different terminals, i.e.,
The complexity of this method is dominated by solving the LP (14)
time, where the exact order of polynomial depends on the LP algorithm used. For example, the complexity will be O(|K| 4.5 (|V | + |E|) 4.5 ) if using Vaidya's algorithm [54]. 1By similar argument as Corollary 1, we can bound the overall performance of the attack as follows.
Corollary 2: Using CKR relaxation with an α-approximation rounding scheme to select the compromised links and the LP (6) to compute the manipulations achieves a total performance degradation of (15) where T CKR is the total traversal number of the links selected by CKR relaxation, and T opt is the minimum total traversal number of all the multiway cuts between the terminals.
TABLE I summarizes the performance guarantee of the aforementioned algorithms in solving ALS.
3) Illustrative Example: Consider the example in Fig. 2 (a). ALS Greedy selects the link with smallest cost-value ratio in each iteration (breaking ties arbitrarily), and ends up selecting L m = {l 1 , l 3 , l 4 }, as shown in Fig. 5. CKR relaxation first obtains a fractional assignment from each node to the terminals
as in Fig. 6 (b), and then rounds it to an integer assignment in Fig. 6 (c) by the scheme in [50]. The output L m is the set of links in the cut, L m = {l 2 , l 4 , l 5 } in this case.
We conduct simulations to evaluate the capabilities of an intelligent attacker employing our strategies in comparison with benchmarks, based on real ISP topologies. To be concrete, we consider delay-based DGoS attacks, where the attacker tries to inject the maximum amount of delay onto a set of targeted paths, while the user of these paths tries to localize links with abnormally large delays by network tomography.
We use real network topologies from public datasets, whose parameters are shown in the TABLE II. The first four topologies are Point of Presence (PoP)-level topologies from the Internet Topology Zoo [55], and the last two topologies are router-level topologies from the CAIDA project [56]. We classify the topologies into small, medium, and large networks. For each topology, we select a given number of terminals uniformly at random from low-degree nodes (degree ≤ 2), and repeat this selection for 20 times.
2) Parameter Setting: For each topology and each set of selected terminals, we compute the paths in P in two ways: i) All possible paths: In this case, P contains all the cyclefree paths between the terminals. Note that cutting all the cycle-free paths is equivalent to cutting all the paths between the terminals. Since the number of all the cyclefree paths can grow exponentially with the network size, we only evaluate this case on the small networks. ii) Shortest paths: In this case, P only contains one shortest path (in hop count) for each pair of terminals, with ties broken arbitrarily. Since there are only |K| 2 paths for |K| terminals, we evaluate this case on the medium-large networks. We assume that before the attack, each link has a delay randomly drawn from [0, 15] ms, and a link is considered "normal" if its delay is within 15 ms, i.e., τ = 15. These parameters are consistent with single-hop delays in real ISP networks [57]. The maximum delay at a link is set to 200 ms, i.e., τ max = 200, which is within the range of typical buffering capacities at router interfaces. 33) Benchmarks: We compare the two proposed algorithms, Algorithm 1 ('ALS greedy') and CKR relaxation with randomized rounding ('CKR'), with the following three heuristics for selecting the set of compromised links: i) "Random selection" ('random'): To illustrate the capability of an attacker who cannot actively select which links to compromise, this algorithm selects k links uniformly at random, where k is set to the number of compromised links selected by 'CKR' to facilitate comparison. ii) "Top traversal" ('top traversal'): Based on the intuition that compromising the most traversed links will provide control over more paths, this algorithm selects the k links with the largest traversal numbers. Again, to facilitate comparison, k is set to the number of compromised links selected by 'CKR'. iii) "Compromise all" ('all'): Compromising all the links is also a very intuitive approach to maximize the damage the attacker can cause to the network. Under each selection of compromised links, we solve the LP (6) to compute the total performance degradation (measured by the total amount of delay injected by the attacker over all the paths) under the optimal manipulations.
Overall, we observe that the proposed algorithms ('ALS greedy' and 'CKR') perform similarly to each other and significantly better than the heuristic algorithms. More importantly, these algorithms show that it is possible to introduce significant delay on communication paths without being localized by network tomography, signaling the need of new defenses.
1) Case of All Possible Paths: In the case that P contains all the possible paths between the terminals, the results are shown in Fig. 7 (top 2). The y-axis is the performance of Fig. 7. Average delay degradation for the case of all possible paths (top 2) and the case of shortest paths (bottom 4). the attacker measured by the average injected delay per path (plus/minus one standard deviation), computed over 20 sets of randomly selected terminals, and the x-axis is the number of terminals. In this experiment, 'CKR' performs the best as expected, as it has the best approximation guarantee. Both 'CKR' and 'ALS greedy' perform much better than the heuristic algorithms, demonstrating the importance of carefully selecting the compromised links in modeling the capabilities of intelligent attackers. Among the heuristic algorithms, 'top traversal' performs the best, as it leads to more compromised paths than 'random'. However, it is not sufficient to just compromise more paths. To prevent the compromised links from being detected as bad links by network tomography, the attacker needs to ensure constraint (2e). Therefore, compromising too many links can reduce the attacker's capability in injecting delays. This is why 'all' performs the worst.
2) Case of Shortest Paths: Similar results are shown in Fig. 7 (bottom 4) for the case where P only contains the shortest paths between the terminals. We see that 'ALS greedy' and 'CKR' still significantly outperform the other algorithms. However, 'CKR' is not always the best any more, because it is not designed for this case. In particular, 'CKR' will select links to cut all the possible paths between the terminals, while the ALS problem in this case only needs to cut the shortest paths. Because of that, 'CKR' may compromise more links than necessary, which reduces the attacker's capability to manipulate the path delays.
In both cases, the best attack algorithm is able to inject significant delays (0.3-3 seconds/path) without exposing the compromised links to network tomography. Detailed examination of the measurement paths shows that the vulnerability of a network to DGoS attacks is negatively correlated with its identifiability, measured by rank(R)/|L|: the average delay degradation per path decreases from 3 seconds to 0.3 second as rank(R)/|L| increases from 0.1 to 0.9. This observation suggests that existing techniques for improving the identifiability via placing monitors and constructing measurement paths [35]- [38] also help to reduce the vulnerability to DGoS attacks. Note that achieving identifiability does not eliminate this vulnerability, e.g., the paths in Fig. 2 (a) can identify all the links, but DGoS attack can still be launched as in Fig. 2 (c).
V. CONSTRAINED ATTACKS So far we have assumed that the attacker can compromise any subset of links. In practice, however, there are usually constraints on which and/or how many links the attacker is capable of compromising. To shed light on the impact of such constraints, we will analyze the optimal attack strategy under the constraint that for a given k > 0,
where c j (c j ≥ 0) is the cost of compromising link l j , and k is the total budget of the attacker for compromising links. We use the costs to model the difficulty of controlling the links, e.g., by gaining backdoor access to the associated devices [10], [60] or manipulating the paths (e.g., through BGP hijacking [61]) to position attacker-controlled devices on the links. We assume that these costs can be evaluated by the attacker.
First of all, we note that the budgeted attack optimization includes the unbudgeted optimization (2) as a special case, which boils down to the ALS problem that is NP-hard as shown in Theorems 1 and 2. Thus, the budgeted optimization is also NP-hard. Nevertheless, we will show that this problem can be formulated as an MILP, which allows us to evaluate the maximum damage achievable by a budgeted attacker for small problem instances using MILP solvers.
Specifically, define binary variables
Then (2) under the additional constraint ( 16) can be written as:
Lemma 3: The MILP ( 9) is equivalent to (2) under the additional constraint (16).
Proof: First, we argue that constraints (19b)-(19d) are equivalent to constraints (2b)-(2c). This is because if a path p i contains no compromised link (i.e., r i α = 0), then β i must be zero and thus (19b)-(19c) imply (2b), whereas if p i contains at least one compromised link, then β i will be one under the optimal solution, and thus (19b) imposes no constraint on x (as τ max r i 1 is an upper bound on the path metric for p i ). Moreover, it is easy to see that constraints (19e)-(19f) are equivalent to (2d)-(2e), and constraint (19g) is equivalent to (16). Finally, as uncompromised paths do not incur any degradation, the objective (19a) is equivalent to (2a).
To solve the attack optimization efficiently for large problem instances, we seek to characterize the optimal set of compromised links more explicitly. Generally, adding the budget constraint ( 16) to (2) will invalidate Theorem 1. To derive its counterpart under the budget constraint, we have the following result.
Lemma 4: If τ max r i x (∀p i ∈ P ) and τ max τ , then the optimal value of (2) for a given set L m of compromised links is asymptotically proportional to
where L n := L n \ p∈Pn p is the set of uncompromised links that are only traversed by compromised paths.
Proof: We rewrite the objective function (2a) as
If l j ∈ L m , then x j ≤ τ by (2e). If l j ∈ L n , then x j ≤ min(τ max , min i: pi∈Pn,rij=1 r i x) by (2b,2d). For a large τ max , x j can achieve τ max if and only if l j ∈ L n . Thus, when τ max is large, the optimal value of (21) wrt x is approximately:
where (22) is because the traversal number of compromised paths is equal to the traversal number of measurement paths for l j ∈ L n , i.e., pi∈Pm r ij = pi∈P r ij for l j ∈ L n . Lemma 4 immediately yields the following asymptotically equivalent formulation of the budget-constrained DGoS.
Theorem 5: If τ max r i x (∀p i ∈ P ) and τ max τ , then the optimal set L * m of compromised links that solves (2) under the additional constraint (16) is the solution to
which we refer to as the constrained adversarial link selection (CALS) problem. Proof: By Lemma 4, the objective in (2a) is asymptotically equivalent to the objective in (23a) as τ max → ∞.
In words, CALS is a novel combinatorial optimization problem that aims at selecting compromised links subject to a budget constraint to maximize the total traversal number of the uncompromised links that only reside on compromised paths. Similar to ALS, we will show that CALS is also NP-hard.
Corollary 3: The CALS problem ( 23) is NP-hard.
Proof: The idea is to show that CALS is actually a generalization of ALS, and hence its NP-hardness is implied by the NP-hardness of ALS as proved in Theorem 2.
To this end, consider a special case of CALS, where it is known that it suffices to optimize L m among the cuts of P . If L m is a cut, then L n = L n , and hence T m = lj ∈L n pi∈P r ij = lj ∈Ln pi∈P r ij , which is the total traversal number of all the uncompromised links. As
which is a constant (the total hop count of all the paths in P ), maximizing lj ∈Ln pi∈P r ij is equivalent to minimizing lj ∈Lm pi∈P r ij (i.e., minimizing the total traversal number of the compromised links), which is the ALS problem.
Compared to the MILP formulation (9), although CALS remains NP-hard, it facilitates the development of an efficient suboptimal algorithm as shown below. Moreover, Lemma 4 implies that T m can be used as a proxy for analyzing the performance of any strategy for selecting the compromised links.
In the unconstrained case, we have seen in Section IV that the simple greedy algorithm (Algorithm 1) achieves superior performance wrt benchmarks. It is thus natural to consider its extension in the constrained case. The resulting algorithm, called CALS Greedy, selects the link that yields the maximum increase in T m per unit cost in each iteration. Specifically, it follows the same steps as Algorithm 1, except that:
• line 3 is replaced by "while P m = P and ∃l ∈ L \ L m such that L m ∪ {l} satisfies the budget constraint ( 16)"; • line 4 is replaced by "find the link l j with the largest ratio Counterexample: As shown later, CALS Greedy performs very well empirically, which raises a question of whether it always closely approximates the optimal solution. To this end, we will show by a counterexample that its approximation factor is at most inversely proportional to the number of paths, i.e., O(1/|P |). Specifically, consider the network topology and the set of paths P as shown in Fig. 8, where k = 2 and c j = 1 (∀l j ∈ L). CALS Greedy will achieve T G m = 2 by selecting L m = {(C, E), (K, G)}. However, the optimal solution achieves T * m = 6n + 2 by selecting L m = {(A, E), (G, I)}. For this instance of CALS, we see that
Therefore, the approximation factor of CALS Greedy (defined by the worst-case instance) is O(1/|P |). This counterexample shows that the greedy heuristic does not provide a good approximation for CALS in the worst case. Nevertheless, it achieves near-optimal performance for the attacker in average cases as shown in Section V-D. It remains open whether there exists a polynomial-time approximation algorithm for CALS.
Remark: Theoretically, we can also apply the greedy heuristic directly to the original objective (2a). Let F (L m ) denote the optimal objective value of the LP wrt x under a given L m , computed as in Section III-A. Then this LP based greedy heuristic will select the link l j with the maximum
in each iteration subject to the budget constraint. This approach, however, will incur a much higher complexity than CALS Greedy due to the need of solving O(|L| 2 ) LP's. For example, its complexity will be O(|L| 4 (|P |+|L|) 2.5 ) if using Vaidya's algorithm [54]
Setup: We evaluate the optimal solution obtained by solving (9) ('MILP') and the proposed algorithm, CALS Greedy ('CALS greedy'), for the budget-constrained DGoS under the setup in Section IV-A, except that we fix the number of terminals and only consider the case of shortest paths. Table III shows the parameter values. As mentioned before, we use costs to model the difficulty for the attacker to control the links, which depends on the specific method of controlling the links and the related parameters, e.g., the models and the vendors of the associated devices for backdoor-based control, or locations of the attacker's devices for hijacking-based control. In our evaluation, the cost of compromising each link is drawn uniformly at random from the interval of [0, 2). This leads to a unit cost per link on the average, giving the budget k an intuitive meaning of the average number of compromised links under random selection. The results are averaged (± one standard deviation) over 20 sets of randomly selected terminals and randomly generated link costs.
Benchmarks: As our problem is a MILP, we use the following heuristics commonly used to solve MILPs as benchmarks: This heuristic first solves the LP relaxation of ( 9), and then treats the fractional solution (α j ) lj ∈L as probabilities for selecting links, subject to the budget constraint. 2) "LP based greedy": This heuristic directly maximizes (2a) by selecting one more compromised link per iteration that yields the maximum additional delay degradation per unit cost, subject to the budget constraint. We also adapt algorithms from the unconstrained case as benchmarks. Algorithm 1 ('ALS greedy') can be easily adapted to satisfy the budget constraint ( 16) by stopping after exhausting the budget. Similarly, the heuristics 'random' and 'top traversal' (see Section IV-A.3) can also be easily adapted to satisfy the budget constraint (16).
Results: Fig. 9 shows the comparison of different attack strategies, where k = ∞ is the unconstrained case. First of all, the result shows that it is necessary to change the objective from minimizing the total traversal number to maximizing T m (20) when we (the attacker) are not able to compromise a cut due to the budget constraint. This is indicated by the poor performance of 'ALS greedy' when k is small. Secondly, the proposed algorithm, 'CALS greedy', achieves as much damage as 'ALS greedy' under an unlimited budget, but much more damage under a limited budget. Across all budget values, 'CALS greedy' achieves near-optimal performance (i.e., close to 'MILP'). Finally, 'CALS greedy' outperforms the other heuristics derived from our optimization formulation (i.e., 'LP-RR', 'LP based greedy'). In particular, while 'LP based greedy' achieves comparable performance degradation, it is much slower, e.g., the experiment on AS 20965 takes 17 seconds for 'CALS greedy' but 4844 seconds for 'LP based greedy', indicating the value of using T m (20) as a proxy objective function. Overall, we see that even though 'CALS greedy' does not guarantee a good approximation in the worst case (see the counterexample in Section V-C), it performs well in average cases.
Moreover, we evaluate the impact of imperfect knowledge of measurement paths, by setting the attacker-assumed measurement paths P to the set of all the shortest paths between the terminals and the actual measurement paths P used by network tomography to a random subset of these paths. We then repeat the experiment in Fig. 9, except that we only count the performance degradation on the paths in P (assuming that only these paths are used). Fig. 10 shows the average degradations achieved by the optimal attack strategy ('MILP') and the best polynomial-time strategy ('CALS greedy') with accurate knowledge of the measurement paths, together with those without accurate knowledge ('overestimated'). The results show that although the attacker incurs some suboptimality due to not knowing the exact set of communication paths, he can still launch the attack on all possible paths and achieve significant damage on the actually used paths. Here we have assumed that network tomography can only monitor the paths used for communications; our recent work [62] considers a more general scenario where network tomography can monitor additional paths via active probing, in which case only the performance degradation on data communication paths matters.
Finally, as our attack model does not rule out the possibility for a specific inference algorithm to detect some of the compromised links as bad links, we evaluate the detectability of compromised links under our best polynomial-time attack strategy, CALS Greedy. To this end, we implement a tomography-based detector that tries to explain all the measurements with the minimum number of bad links as in [18]. Let L d denote the set of detected bad links. ). We see that although the detector detects some compromised links as bad links, it detects even more innocent links as bad links, and is thus unable to localize the compromised links. Specifically, the false alarm rate is comparable to or even higher than the detection rate in most attack scenarios, meaning that an uncompromised link is more likely to be flagged as a bad link than a compromised link. This is because the detector flags a much larger number of bad links than the actual number of links introducing significant delays (i.e., compromised links). For example, in Cogent, the detector claims that 70-80% links are bad while most of the delays are injected by 10% of the links. indicates the difficulty of localizing the compromised links using existing tomography techniques.
This work helps to establish the fundamental limit of network tomography in adversarial environments by formulating and analyzing a novel type attack, called the stealthy DeGrading of Service (DGoS) attack, that aims at maximally degrading the performance of targeted paths without being localized by network tomography. Through careful analysis, we derive explicit properties of the optimal attack strategy. The derived properties allow us to our problem to well-known combinatorial optimization problems, and leverage existing algorithms with approximation guarantees. Our evaluations on real topologies show that the proposed attack can degrade communication performances without being localized by network tomography, signaling the need of new defenses. In particular, our evaluations a performance gap between heuristic attack strategies (e.g., compromising the most traversed links) and the proposed strategies, demonstrating the importance of modeling intelligent attackers.
Discussion: Our results suggest several potential approaches to the defense. First, our proposed algorithms can be used to identify the set of links that once controlled by an adversary, will cause the maximum damage, which helps to select links for protection (e.g., by installing monitoring agents or updating software/hardware at the endpoints). Moreover, the results in Fig. 10 suggest that dynamically adapting the measurement paths among a larger set of paths can help network tomography to mitigate DGoS attacks by making it harder for the attacker to learn which paths are monitored. Lastly, our observations that networks with higher identifiability are less vulnerable to DGoS attacks suggest that existing measurement design algorithms can also help to defend against such attacks.
We leave detailed investigation of these defenses to future work.
Authorized licensed use limited to: Penn State University. Downloaded on April 01,2021 at 20:33:56 UTC from IEEE Xplore. Restrictions apply.
This algorithm has a worst-case complexity of O((n + m) 1.5 nB) for an LP with n variables, m constraints, and B input bits.
The constant α depends on the rounding scheme, e.g., 1.5 for randomized rounding and 1.2965 for the rounding scheme in[53].
For example, Cisco Supervisor Engine 7-E with a Gigabit port and 32MB memory can buffer traffic for 320 ms [58], and Juniper line cards can buffer traffic for 100-250 ms[59].
For Bics, these are all the nodes with degree ≤ 2; for the other networks, these are all the nodes with degree one.