François Espinet

Diana Joumblatt

Dario Rossi

Zen and the Art of Network Troubleshooting: A Hands on Experimental Study

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Nowadays, broadband Internet access is vital. Many people rely on online applications in their homes to watch TV, make VoIP calls, and interact with each other through social media and emails. Unfortunately, dynamic network conditions such as device failures and congested links can affect the network performance and cause disruptions (e.g. frozen video, poor VoIP quality).

Currently, troubleshooting performance disruptions is complex and ad hoc due to the presence of different applications, network protocols, and administrative domains. Typically, troubleshooting starts with a user call to the ISP help desk. However, the intervention of the ISP technician is useless if the root cause lies outside of the ISP network, which possibly includes the home network of the very same user -hence, for the ISP, it would be valuable to extend its reach beyond the home gateway by instrumenting experiments directly from end-user devices. While (tech savvy) users can be assisted in their troubleshooting efforts by software tools such as [START_REF] Bischof | Crowdsourcing ISP characterization to the network edge[END_REF][START_REF] Dhawan | Fathom: A browser-based network measurement platform[END_REF][START_REF] Kim | DYSWIS: crowdsourcing a home network diagnosis[END_REF][START_REF] Kreibich | Netalyzr: Illuminating the edge network[END_REF] which automate a number of useful measurements, these tools do not incorporate network tomography techniques [START_REF] Ghita | Shifting network tomography toward a practical goal[END_REF][START_REF] Nguyen | The boolean solution to the congested IP link location problem: Theory and practice[END_REF] to identify the root causes of network disruptions (e.g., faulty links). Additionally, these tools are generally ISP network-agnostic, hence, they would benefit from cooperation with the ISP.

In this paper, we propose a practical methodology to automate the identification of faulty links in the access network based on end-to-end measurements. Since the devices participating in the troubleshooting task can be either under the control of the end-user or the ISP, the knowledge of the ISP topology is not always available for the measurement probes. Consequently, we formalize the troubleshooting task as either a clustering or a classification problem -where respectively end-users are able to assess the severity of the fault, or ISPs are able to identify the faulty link.

This paper makes several contributions. While our troubleshooting model (Sec. 3), algorithm (Sec. 4) and software implementation (Sec. 5) are interesting per se, we believe our major contribution is the rigour of the evaluation methodology (Sec. 6), which overcomes state of the art limits (Sec. 2). Indeed, on one hand, previous practical troubleshooting efforts [START_REF] Bischof | Crowdsourcing ISP characterization to the network edge[END_REF][START_REF] Dhawan | Fathom: A browser-based network measurement platform[END_REF][START_REF] Joumblatt | HostView: Annotating end-host performance measurements with user feedback[END_REF][START_REF] Kim | DYSWIS: crowdsourcing a home network diagnosis[END_REF][START_REF] Kreibich | Netalyzr: Illuminating the edge network[END_REF] are valuable in terms of domain knowledge and engineering, but lack theoretical foundations and rigorous verification. On the other hand, prior analytical efforts are cast on solid theoretic ground [START_REF] Ghita | Shifting network tomography toward a practical goal[END_REF][START_REF] Nguyen | The boolean solution to the congested IP link location problem: Theory and practice[END_REF], but their validation is either simplistic (e.g. simulations) or lacks ground truth (e.g. PlanetLab).

In this work, we take the best of both worlds, as we (i) propose a practical methodology for network troubleshooting with an open source implementation; (ii) provide a model of the expected fault detection probability that we contrast with experimental results; (iii) use an experimental approach where we emulate controlled network conditions with Mininet [START_REF] Handigol | Reproducible network experiments using container-based emulation[END_REF]; (iv) perform a calibration of the emulation setup, an often neglected albeit mandatory task; (v) in spirit with Mininet and the TMA community, we further make all our source code available for the scientific community at [START_REF]Emulator scripts[END_REF][START_REF]NetProbes[END_REF].

Related work

Our work complements prior network troubleshooting efforts [3, 4, 6-8, 16-19, 23] that we overview in this section. Without attempting at a full-blown taxonomy, we may divide the above work as having a more practical [START_REF] Bahl | Towards highly reliable enterprise network services via inference of multi-level dependencies[END_REF][START_REF] Bischof | Crowdsourcing ISP characterization to the network edge[END_REF][START_REF] Dhawan | Fathom: A browser-based network measurement platform[END_REF][START_REF] Joumblatt | HostView: Annotating end-host performance measurements with user feedback[END_REF][START_REF] Kim | DYSWIS: crowdsourcing a home network diagnosis[END_REF][START_REF] Kreibich | Netalyzr: Illuminating the edge network[END_REF] or theoretic [START_REF] Duffield | Multicast topology inference from measured end-to-end loss[END_REF][START_REF] Duffield | Network loss tomography using striped unicast probes[END_REF][START_REF] Kompella | Detection and localization of network black holes[END_REF][START_REF] Presti | Multicast-based inference of network-internal delay distributions[END_REF] approach. While most work, including ours, uses active measurements [4, 6-8, 17-19, 23], there are exceptions that use passive measurements [START_REF] Joumblatt | HostView: Annotating end-host performance measurements with user feedback[END_REF] or logs [START_REF] Bahl | Towards highly reliable enterprise network services via inference of multi-level dependencies[END_REF]. In terms of network segment, previous work focuses on home networks [START_REF] Kim | DYSWIS: crowdsourcing a home network diagnosis[END_REF], enterprise networks [START_REF] Bahl | Towards highly reliable enterprise network services via inference of multi-level dependencies[END_REF], and backbone networks [START_REF] Dhamdhere | Netdiagnoser: Troubleshooting network unreachabilities using end-to-end probes and routing data[END_REF][START_REF] Ghita | Shifting network tomography toward a practical goal[END_REF][START_REF] Kompella | Detection and localization of network black holes[END_REF]. Some studies do not target a network segment in particular [START_REF] Duffield | Multicast topology inference from measured end-to-end loss[END_REF][START_REF] Duffield | Network loss tomography using striped unicast probes[END_REF][START_REF] Presti | Multicast-based inference of network-internal delay distributions[END_REF] and remain at a more abstract level. In this paper, we focus on home and access networks.

Our methodology is based solely on end-to-end measurements to localize the set of links that are the most likely root cause of performance degradations. Closest to our work is the large body of work in network tomography which exploits the similarity of end-to-end network performance from a source to multiple receivers due to common paths to infer properties of internal network links such as network outages [START_REF] Kompella | Detection and localization of network black holes[END_REF], delays [START_REF] Presti | Multicast-based inference of network-internal delay distributions[END_REF], and packet losses [START_REF] Duffield | Network loss tomography using striped unicast probes[END_REF]. However, these studies make simplifying assumptions that do not hold in real deployments [START_REF] Ghita | Shifting network tomography toward a practical goal[END_REF][START_REF] Huang | Practical issues with using network tomography for fault diagnosis[END_REF] such as the use of multicast [START_REF] Presti | Multicast-based inference of network-internal delay distributions[END_REF]. In addition, the proposed algorithms are computationally expensive for networks of reasonable scale and their accuracy is affected by the scale and the topology of the network [START_REF] Ghita | Shifting network tomography toward a practical goal[END_REF].

In this work, we instead present a practical, general framework to identify faulty links that we instantiate on two specific metrics: delays as in [START_REF] Presti | Multicast-based inference of network-internal delay distributions[END_REF] and bottleneck band-width, which is notoriously more difficult to measure. When full topological information is not available, our algorithm performs a clustering of measurement probes as in binary network tomography [START_REF] Nguyen | The boolean solution to the congested IP link location problem: Theory and practice[END_REF], where the inference problem is simplified by separating links (in our case probes) into good vs failed, instead of estimating the values of the link performance metrics.

Additionally, one major problem of the related literature is the realism of ground truth data to evaluate the accuracy of the algorithms. Even in practical approaches, ground truth in the form of user tickets [START_REF] Bahl | Towards highly reliable enterprise network services via inference of multi-level dependencies[END_REF] or user feedback [START_REF] Joumblatt | HostView: Annotating end-host performance measurements with user feedback[END_REF] is extremely rare, so that the absence of ground truth is commonplace [START_REF] Bischof | Crowdsourcing ISP characterization to the network edge[END_REF][START_REF] Dhawan | Fathom: A browser-based network measurement platform[END_REF][START_REF] Kim | DYSWIS: crowdsourcing a home network diagnosis[END_REF][START_REF] Kreibich | Netalyzr: Illuminating the edge network[END_REF]. Theoretic work builds ground truth with simulations [START_REF] Duffield | Network loss tomography using striped unicast probes[END_REF], or using syslogs and SNMP data in operational networks [START_REF] Kompella | Detection and localization of network black holes[END_REF]. On the one hand, although simulations simplify the control over failure location and duration, they do not provide realistic settings. On the other hand, the ground truth is either completely missing in real operational networks (such as PlanetLab [START_REF] Nguyen | The boolean solution to the congested IP link location problem: Theory and practice[END_REF]) or partially missing in testbeds [START_REF] Huang | Practical issues with using network tomography for fault diagnosis[END_REF][START_REF] Kompella | Detection and localization of network black holes[END_REF], where network events outside of the control of researchers can happen. Our setup employs controlled emulation through Mininet [START_REF] Handigol | Reproducible network experiments using container-based emulation[END_REF] which is (relatively) fast to implement, uses real code (including kernel stack and our software), and allows testing on fairly large scale topologies. This setup allows full control on the number, duration, and location of network problems. Additionally, by running the full network stack, Mininet keeps the real world noise in the underlying measurements, thus providing a more challenging validation environment with respect to simulation. As a side effect of this choice, the NetProbes software that we release as open source [START_REF]NetProbes[END_REF] has also undergone a significant amount of experimental validation. Most importantly, any peer researcher is capable of repeating our experiments in order to validate our results, compare their approach to ours, and extend this work.

Problem statement and model

Considering an ISP network, and focusing for the sake of simplicity on its access tree, faults can occur at multiple levels in the access network hierarchy. The ability to launch measurements between arbitrary pairs of devices in the same access network would significantly enhance the diagnosis of network performance disruptions. In this work we consider two use-cases: User-managed probes and ISP-managed probes. Usermanaged probes run only on end-user devices and lack topology information. In contrast, ISP-managed probes can reside in home gateways, in special locations inside the ISP network, and can also be available as "apps" on user devices (e.g., smartphones and laptops). We address both use-cases with the same algorithm: clustering in the userscenario separates measurement probes into two sets (i.e., un/affected sets), whereas an additional mapping in the ISP-scenario allows to pinpoint the root cause link.

We formalize the problem and introduce the notation used in this paper with the help of Fig. 1, which depicts a binary access network tree. The troubleshooting probe software runs in the leaf nodes of the tree. However, the ISP can strategically place probes inside the network (e.g. probe 0 in the picture attached to the root). Our algorithm runs continuously in the background to gather a baseline of network performance, and troubleshooting is triggered by the user (e.g., upon experiencing a degradation of For the sake of clarity, let us assume that probe 1 launches a troubleshooting task. In this context, we can safely assume that the root cause is located somewhere in the path from the user device or gateway towards the Internet (links ℓ 4 , ℓ 3 , ℓ 2 , ℓ 1 in bold in Fig. 1). In order to identify which among ℓ 4 , .., ℓ 1 is the root cause of the fault, probe 1 requires sending probing traffic to a number M of the overall available probes N . Let us denote, for convenience, by D + = log k (N ) the maximum depth (i.e., height) of a k-ary tree and by D i the set of probes

D i = ( k D + -i , k D + -i+1 ]
. The set D i includes probes whose shortest path from probe 1 passes through ℓ i , but does not pass through ℓ i-1 . In the access tree, whenever a link ℓ f (located at depth f in the tree) is faulty, all probes whose shortest path from the diagnostic probe (probe 1 in our example) passes through ℓ f will also experience the problem, unlike probes that are reachable through ℓ f +1 : it follows that the troubleshooting algorithm requires probes from both sets D f and D f +1 to infer with certainty that the fault is located at ℓ f . For a k-ary tree, the minimum number of probes that allows to identify the faulty link irrespectively of the depth f of the fault is M = O(log k (N )) -i.e., one probe in each of the {D i } log k (N ) i=1 strata suffices to accurately pinpoint the root cause.

Such a strategic probe selection requires either topology knowledge or the assistance of a cooperating server managed by the ISP (e.g., an IETF ALTO [START_REF] Seedorf | Application-Layer Traffic Optimization (ALTO) Problem Statement[END_REF] server). However, this strategy is not feasible with user-managed probes, in which probe selection is either uniformly random or based on publicly available information such as IP addresses. It is thus important to assess the detection probability of a naive random selection.

Let us denote by p -(f, α) the probability that a random selection includes a probe that is useful to locate a fault at depth f ∈ [1, D + ], with a probe budget α = M/N . The deeper is the fault location, the smaller is the number of probes available to identify the faulty link. As the size of D f exponentially decreases as f increases (card(D f ) = k D + -f ), we expect the random selection strategy to easily locate faults at small depths (close to the root) and fail at large depths (close to the leaves) where a stratified selection is necessary to sample probes in the smaller set D f . The probability that none of the M vantage points falls into D f decreases exponentially fast with the size of D f , i.e., (1 -α) card(D f ) . Consequently, the probability to sample at least1 one probe in D f is:

p -(f, α) = 1 -(1 -α) k (D + -f ) (1)
Expression ( 1) is a lower bound on the expected detection probability with random selection. When a random subset of probes does not contain any probe in D f , it is still possible to correctly guess the root cause link. Here, there will be ambiguity because multiple links are equally likely to be root cause candidates. At any depth d, ambiguity will be limited to the links located between the fault and the root of the tree (i.e., ℓ d , .., ℓ 1 ): since, at depth d, ambiguity involves d links, the probability of a correct guess is 1/d. To compute the average probability of a correct guess E[p guess ], we have to account for the relative frequency of the different ambiguity cases, which for depth d happen proportionally to

k d /k log k (N ) = k d /N , E[p guess ] = log k (N ) ∑ d=1 1 d k d N = 1 N log k (N ) ∑ d=1 k d d (2)
We can then compute the expected discriminative power of a random selection, expressed in terms of the probability to correctly identify a fault at depth f as:

E[p] = p -(f, α) + ( 1 -p -(f, α) ) E[p guess ] (3)
where the first term accounts for the proportion of random selection that is structurally equivalent to a stratified selection (so that the root cause link can be found with probability 1), and the second term accounts for the proportion of random selection able to pinpoint the faulty link by luck (thus with probability E[p guess ]). By plugging (1) and ( 2) into (3) we get:

E[p] = 1 -(1 -α) k (D + -f ) + [ 1 -(1 -(1 -α) k (D + -f ) ) ] ( 1
N log k (N ) ∑ d=1 k d d ) (4) = 1 -(1 -α) k (D + -f ) ( 1 - 1 N log k (N ) ∑ d=1 k d d ) (5)
Notice that (5) has structurally the form 1 -p loss . The term p loss can be interpreted as the loss of discriminative power with respect to a perfect strategic selection that always achieves correct detection. Clearly, this model is simplistic as it does not consider all combinatorial aspects which could be used to obtain finer-grained expectations at each depth of the tree. Yet, the main purpose of the model is to serve as a reality check for our experimental results.

We treat both clustering and classification problems with a single algorithm, whose pseudocode is reported in Algorithm 1. Assuming the algorithm runs at a source node s, for any performance metric Q (e.g., delay, bandwidth), s collects baseline statistics Q 0 (p) with low-rate active measurements towards other peers p. When the troubleshooting is triggered, s iteratively selects up to R batches of B of probes, so that R • B represents a tuneable probing budget. Selection is made according to a selection policy S p , based on a probe score S(p). The probe selection is iterative because S(p) can vary, and thus the next batch is selected based on the results of the previous batch. At each step, upon doing B measurements, we compute, for each probe p, Q(p) -Q 0 (p) and add it to the set P : K-means clustering partitions P into P + and P -. Two points are worth stressing: first, the algorithm does not associate any semantic to clusters: e.g., a node in P + can be affected by large delay, whereas a node in P -can be affected by a bottleneck bandwidth. Second, in case of a single failure, it can be expected that probes in one of the two clusters exhibit Q(p) -Q 0 (p) ≈ 0, so P + and P - should be interpreted as a syntactical difference. Once the probe budget is exhausted (or once other stop criteria, that we don't mention for the sake of simplicity, are met), the algorithm either returns P + and P -(user-managed case, line 12), or continues with the mapping. When no clear partition can be established, only one set is returned.

To map probes in P + and P -to links, the algorithm requires the knowledge of the links ℓ in the shortest path SP (s, p). The score S(ℓ) of ℓ ∈ SP (s, p) is incremented by +1 for p ∈ P + and decremented by -1 for p ∈ P -. As a consequence of metricagnosis, the algorithm needs to know if links with the largest (smallest) S(ℓ) scores are to be pinpointed, which is done according to a link selection policy S ℓ .

We experiment with S p ∈ {random, |IP (s) -IP (p)|, balance} and combinations of the above. Random selection is useful as a baseline and to compare with the model. We additionally consider probe selection policies that are more complex to model such as the absolute distance in the IP space, as well as a policy that attempts at equating the size of P + and P -, by selecting an IP that is close to IPs in the small cluster, and far from IPs in the large cluster (exact definition omitted due to lack of space). Moreover, we consider S ℓ ∈ {random, proportional, argmax}. The naïve random method makes an informed guess by selecting one of the D + links in the path ℓ D+ , . . . , ℓ 1 to the root (success probability 1/D + , much larger than the 1/2(k D + -1) = 1/2(N -1) in case of a random guess over all links). We also select links proportionally to their score (proportional policy), or only the link with the largest (smallest) score (argmax policy).

Calibration of the emulation environment

Before running a full-fledged measurement campaign, it is mandatory to perform a rigorous calibration phase, yet this phase is often neglected [START_REF] Paxson | Keynote: Reflections on measurement research: Crooked lines, straight lines, and moneyshots[END_REF]. In this work, we follow an experimental approach using emulation in Mininet, to control the duration and the location of the faults. However, it is unclear how well state-of-the-art delay and bandwidth measurement techniques perform in Mininet. In order to disambiguate inconsistencies due to Mininet from measurement errors intrinsic to measurements techniques, we perform calibration experiments for a set of delay (expectedly easy) and bandwidth (notoriously difficult) measurement tools and assess their accuracy in Mininet. In this section, we first briefly describe Mininet and NetProbes, the diagnosis software we develop for this work (Sec. 5.1), then present the calibration results (Sec. 5.2).

Software Tools

Mininet [START_REF] Handigol | Reproducible network experiments using container-based emulation[END_REF] Mininet is an open source emulator which creates a virtual network of end-hosts, links, and OpenFlow virtual switches in a single Linux kernel and supports experiments with almost arbitrary network topologies. Mininet hosts execute code in real-time, exchange real network traffic, and behave similarly to deployed hardware. All the software developed for a virtual Mininet network can run in hardware networks and be shared with others to reproduce the experiments. Mininet provides the functional and timing realism of testbeds in addition to the flexibility and full control of simulators. Experimenters configure packet forwarding at the switches with OpenFlow and link network characteristics (e.g., delay and bandwidth) with the Linux Traffic Control (tc). Reproducing experiments from tier-1 conference papers2 indicates that results from Mininet and from testbeds are in agreement.

NetProbes [START_REF]NetProbes[END_REF] We design NetProbes, a distributed software written in Python 3.x that runs on end-hosts and executes a set of user-defined active measurement tests. Net-Probes agents deployed at end-user devices and gateways form an overlay. They perform a set of periodic measurements to monitor the paths in the overlay and collect a baseline network performance. When the user experiences network performance issues, the NetProbes agent running at the user device launches a troubleshooting task to assess the severity of the performance issue and the location of the faulty link. It is worth pointing out that the set of measurement tasks that can be performed by NetProbes agents (e.g., HTTP or DNS requests, multicast UDP tests, etc.) is far larger than what we consider within the scope of this paper, and that the software is available at [START_REF]NetProbes[END_REF].

Delay and bandwidth calibration

Setup We build a Mininet virtual network with the topology depicted in Fig. 1 on a server with four cores and 24 GB of RAM. We run the selected tools on probes 1 and 2. In our delay experiments, we impose five different delay values (0 ms, 20 ms, 100 ms, 200 ms, 1000 ms) on ℓ 3 located at depth d = 3 in the tree. At each delay level, probes 1 and 2 perform 50 measurements of round trip delays to probes 7 and 6 respectively (250 measurements in total for each pair of probes). We use Mininet processes through the Python API to issue ping and traceroute to measure RTTs (we test traceroute with UDP, UDP Lite, TCP, and ICMP).

Similarly, in the bandwidth experiments, we vary the link capacity of ℓ 3 (100 Mbps, 10 Mbps, 1 Mbps) under three different traffic shapers, namely the hierarchical token bucket (HTB), the token bucket filter (TBF), and the hierarchical fair service curve (HFSC) and we make 20 measurements of the available bandwidth between probes 1 and 7 and probes 2 and 6 (120 in total for each value of the link capacity). There is a plethora of measurement tools designed by the research community to estimate the available bandwidth [START_REF] Goldoni | End-to-end available bandwidth estimation tools, an experimental comparison[END_REF]. In this work we limitedly report the calibration of three popular tools (Abing [START_REF] Navratil | Abwe: A practical approach to available bandwidth estimation[END_REF], ASSOLO [START_REF] Goldoni | Assolo, a new method for available bandwidth estimation[END_REF], and IGI [START_REF] Hu | Evaluation and characterization of available bandwidth probing techniques[END_REF]) which are characterised by low intrusiveness: Abing and IGI infer the available bandwidth based on the dispersion of packet pairs measured at the receiver. ASSOLO sends a variable bit-rate stream with exponentially spaced packets and calculates the available bandwidth from the delays at the receiver side. We compare the performance of the three bandwidth estimation tools in the absence of cross traffic and under the three traffic shapers mentioned earlier.

Delay We expect delay measurements to be flawless. Yet we observe that the first packet sent between any two hosts exhibits a large delay variance: this is due to the fact that the corresponding entry for the flow is missing in the virtual switch and thus requires data exchange between the OpenFlow controller and the virtual switch, whereas the forwarding entry is ready for subsequent packets. We thus do the baseline Q 0 (p) over multiple packets (50 for delay) to mitigate this phenomenon, so that the impact of the first packet delay is factored out in the warmup phase. Doing a baseline and subtracting it from each delay measurement enables an accurate study of the effect of the imposed delay value on the accuracy of the measurement technique. Further results are shown in Fig. 2. All techniques exhibit a time evolution similar to ICMP ping whose experiment is depicted in Fig. 2(a). We report the PDF of the measurement error (i.e., the difference between the measured and the enforced RTT) in Fig. 2(b). Results for traceroute with various protocols are similar: we observe that, for all the delay measurement techniques, the bulk of the error distribution is less than 1 ms (with outliers not shown up to 10ms). Moreover, we note that using ICMP brings the absolute error to less than 0.1 ms for both traceroute and ping. From this calibration phase, we select ICMP ping to measure delay: as the measurement noise is insignificant, errors in the classification outcome should be solely attributed to our troubleshooting algorithm.

Capacity Fig. 3 reports the evolution of the estimated available bandwidth as a function of three link capacity values for the cross product of {Abing, ASSOLO, IGI} × {HTB, TBF, HFSC}. We stress that while comparison of bandwidth estimation tools under the same experimental conditions has already been studied, we are not aware of any study jointly considering bandwidth estimation and bandwidth shaping, especially since many bandwidth measurement tools rely on effects of cross-trafic to estimate available bandwidth. As before, we use a warmup phase to factor out the extra delay incurred by the first packet. We can see that Abing systematically fails in estimating the available bandwidth under HTB and TBF shaping, while the estimation is correct with HFSC. Similarly, ASSOLO fails in estimating 1 Mbps available bandwidth under all shapers, and additionally fails the estimation of 10Mbps under TBF. In contrast, IGI succeeds in accurately tracking changes of available bandwidth at ℓ 3 , although outliers are still possible (see IGI+TBF). A downside of IGI is that the measurements last longer than measurements with Abing or ASSOLO. These results and tradeoffs are interesting and require future attention. However, this is beyond the scope of this work. The most important takeaway is that measurement errors of such magnitude would invalidate all experiments, showing once more the importance of this calibration phase. We additionally gather that the IGI+HFSC combination offers the most accurate estimates of available bandwidth. As accurate input is a necessary condition for trobuleshooting success, we use this combination in the remainder of this paper.

Experimental results

We now evaluate the quality of our clustering and classification for various probe budgets (namely 10, 20 and 50 probes) for faults (e.g., doubling delay or halving bandwidth) at controlled depths of the tree. All the scripts to reproduce the experiments are available at [START_REF]Emulator scripts[END_REF]. We first compare experimental results in a calibrated Mininet environment (including real-world noise), with those expected by a probabilistic model (neglecting noise) (Sec. 6.1). We next perform a sensitivity analysis by varying topological properties, probe selection policies S p , and link selection policies S ℓ (Sec. 6.2).

Performance at a glance

We perform experiments over a binary tree scenario (k = 2) with depth D + = 9 and N = 512 leaf nodes. In this case, a strategic probe selection would need M/N = 9/512 probes (α = 1.75%) to ensure perfect classification, but we consider larger budget M = {10, 20, 50} in our experiments. Unless otherwise stated, we use a random probe selection S p and an argmax link selection S ℓ policies. We first evaluate the clustering methodology by comparing the two sets of affected and unaffected probes obtained from the algorithm with our ground truth, using the well-known rand index [START_REF] Halkidi | On clustering validation techniques[END_REF], which takes value in [0, 1] ⊂ R, with 1 indicating that the data clusters are exactly the same. Since we have full control over the location of the fault, we build our ground truth by assigning the label "affected" to all the available probes (under a given budget constraint) for which the path to the diagnostic probe passes through the faulty link. The remaining probes constitute the unaffected set. Fig. 4-(a) shows that, provided measurements are accurate, the clustering methodology successfully identifies the set of probes whose paths from the diagnostic software experience significant network performance disruptions (and as a consequence accurately identifies nodes in the complementary set of unaffected probes). For budgets of 10, 20 and 50 probes, the rand index shows perfect match between the ground truth and the clustering output in the case of delay measurement. Results degrade significantly instead for bandwidth measurement: we point out that the loss of accuracy is not tied to our algorithm, but rather to measurements that are input to it, which was partly expected and confirms that calibration is a necessary, but unfortunately not sufficient, step.

Abstracting from limits in the measurement techniques, these result indicates that in practice our clustering methodology works well in assessing the impact of a faulty link without requiring knowledge of the network topology. Yet, root cause link identification is a clearly more challenging and important objective, which we analyze in the following by restricting our attention to delay experiments: as the classification step is a deterministic mapping from the clusters, as long as the measurement error remains small, the results of the classification task are not affected by the specific metric under investigation. We expect classification results to apply at large, as opposite to merely illustrating the algorithm performance under delay measurement (although they are not representative of bottleneck localization as per Fig. 4-(a)).

We next show that the experimental and modelling results are in agreement, with a random probe selection policy and a budget of M = 50 probes, which corresponds to α = 9.75%. For each fault depth f , we perform 10 experiments by randomizing the set of destination probes. Results, as reported in Fig. 4-(b), depict the correct classification probability of the model vs the experiments. Recall that equation (1) gives a lower bound p -(f, α) to the experimental results, while (3) models the average expected detection probability E[p]. We consider α = 9.75%, to directly compare with experimental results, as well as α = 1.75%, to assess the loss of discriminative power from a strategic selection, that could achieve perfect classification in this setting, to a random selection (denoted with p loss in the figure).

Sensitivity analysis

Impact of topology We study the impact of the network topology on the classification performance. We use two trees with 512 probes (i.e. leaves) each. The first tree has a depth d = 3 and a fanout k = 8 while the second tree has a depth d = 9 and a fanout k = 2. Fig. 5 reports the correct detection probability of the faulty link as a function of the depth of the injected fault in the tree, using variance bars. As expected, results indicate that the correct detection probability decreases as the fault depth increases 3 . Thus, when the root cause link is located close to the leaves of the tree, it is harder to randomly sample another probe which is also affected by the fault: we thus need a smarter probe selection strategy to improve the link classification performance.

Impact of the probe selection policy S p We consider policies based on IP-distance (IP), cluster-size (balance), and a linear combination of both. We average the results over all the depths of the binary tree and contrast them with a random selection policy. Unfortunately, our attempts are so far unsuccessful as shown in Fig. 6(a), where the discriminative power is roughly the same over all probe selection policies. This is due to the fact that the current set of metrics we consider to select probes do not encode useful information to bias the selection. The absence of a notion of net masks and hierarchy with IP-distance for example makes it hard to extract information about how topologically close/far probes are from each other. An obvious improvement would be to consider the IP-TTL field. However, since Mininet uses virtual switches to construct the network, the IP-TTL field remains unchanged. As a consequence, we could not conduct experiments with this field and we leave it as future work.

Impact of the link selection policy S ℓ Finally, we use three different policies to select the faulty links: S ℓ ∈ {random, proportional, argmax}. Results, averaged over all depths of the binary tree, are reported in Fig. 6. The plot is futher annotated with the gain factor over the random selection: while proportional selection brings a constant improvement of about 40%, the argmax policy brings considerable gains (in excess of a factor 4) which grow with the probe budget.

Conclusions and future work

In this work, we present a troubleshooting algorithm to diagnose network performance disruptions in the home and access networks. We apply a clustering methodology to evaluate the severity of the performance issue and leverage the knowledge of the access network topology to identify the root cause link with a correct classification probability of 70% using 10% of the available probes. We follow an experimental approach and use an emulated environment based on Mininet to validate our algorithm. Our choice of Mininet is guided by our requirements to have flexibility in designing the experiments, full control over the injected faults, and realistic network settings. We contrast the experimental results with an analytical model that computes the expected correct classification probability under a random probe selection policy. We also evaluate the impact of topology, probe and link selection policies on the algorithm. Our proposed solution is a first step towards the goal of having reproducible network troubleshooting algorithms -for which we make all our code publicly available. Our future work will focus on extending the algorithm to different network topologies and to diversify the set of network performance metrics, to verify its generality. Also, while simplicity was one of the goals of this paper, and allowed to compare analytical vs experimental results, our future work will address more practical issues, such as how our design can be integrated and complement troubleshooting systems already deployed by ISPs.

Fig. 1 .

 1 Fig. 1. Synoptic of the network scenario and model notation

Fig. 2 .

 2 Fig. 2. Calibration of delay measurements

Fig. 3 .

 3 Fig. 3. Calibration of bandwidth measurements: {Abing, ASSOLO, IGI} × {HTB, TBF, HFSC}

Fig. 4 .

 4 Fig. 4. Experimental results at a glance: (a) Clustering and (b) Classification

Fig. 5 .

 5 Fig. 5. Sensitivity analysis: Impact of network topology properties

Fig. 6 .

 6 Fig. 6. Sensitivity analysis: Impact of selection policies

  Algorithm 1 Detection algorithm at s

	1: Get a baseline Q0(p) for metric Q(p), ∀p	▷ Initialization, over long timescale
	2: for round ∈ [1..R] do	▷ When triggered upon user/ISP demand
	3:	select a batch of B probes according to a probe selection policy Sp, based on score S(p)
	4:	for p ∈ B do
	5:	perform active measurements with p to get Q(p) -Q0(p)
	6:	add probe p to probed set P
	7:	partition P into P + and P -, by K-means clustering on Q(p) -Q0(p)
	8:	end for
	9:	update probe scores S(p), ∀p
	10: end for
	11: if topology is not available then	▷ Clustering results
	12:	return P + and P -
	13: else	▷ Classification results
	14:	for probe p ∈ P do
	15:
	17:	end for
	18:	end for
	19:	return link ℓ according to a link selection strategy S ℓ based on scores S(ℓ)
	20: end if

for link ℓ ∈ shortest path SP (s, p) do 16: S(ℓ) ← S(ℓ) + 1(p ∈ P + ) -1(p ∈ P -)

Note that this probability would be better expressed with the hypergeometric distribution, that models sampling without replacement; however the formulation reported here differ by less than 1% from the hypergeometric results, and further allows to express the loss of discriminative power due to random selection in a more intuitive way.

Stanford's CS224 blog: http://reproducingnetworkresearch.wordpress.com

We use variance, instead of stdev, to reduce visual noise: thus the increase for k=8 at depth d = 3 is only apparent, as the corresponding standard deviation bars are large.

Acknowledgement

This work has been carried out at LINCS http://www.lincs.fr and funded by the FP7 mPlane project (grant agreement no. 318627).


Elias Raftopoulos

Eduard Glatz

Xenofontas Dimitropoulos

Alberto Dainotti

How Dangerous Is Internet Scanning?

Keywords: Botnet Characterization, Network Scanning, IDS, Netflow

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Botnets of up to millions of compromised computers are presently the most widely-used cyberweapon for executing criminal activities, such as fraud, sensitive data leakage, distributed denial-of-service attacks, and spam. Botnets engage into large-scale scanning to enumerate vulnerable hosts for targeted criminal activities or simply propagation [START_REF] Bailey | A Survey of Botnet Technology and Defenses[END_REF][START_REF] Shin | Cross-analysis of botnet victims: New insights and implications[END_REF]. A recent study showed that scanning accounts for 34-67% of all connection attempts in an academic ISP [START_REF] Glatz | Classifying internet one-way traffic[END_REF]. Besides, recent advances in scanning software make it possible to scan the entire IPv4 address space in less than 45 minutes [START_REF] Durumeric | ZMap: Fast Internet-wide scanning and its security applications[END_REF], simplifying further the execution of aggressive scanning attacks. In spite of the prevalence of scanning, it is difficult to assess how dangerous it is, i.e., is it simply an innocent background traffic noise or a dangerous threat that is worth investing effort and money for blocking it?

In this work we take a novel look into Internet scanning from the point of view of scan repliers. We combine unsampled Netflow records and IDS alerts collected from a university network to assess the aftermath of a specific scanning event. In particular, we focus on the "sipscan", an Internet-wide scanning event orchestrated from the Sality botnet over 12 days in February 2011 that was analyzed by Dainotti et al. [9]. This event had several interesting characteristics: 1) it used a well-orchestrated stealth scanning strategy; 2) it originated from 3 million IP addresses; 3) it is believed that it scanned the entire Internet address space; and 4) it targeted Session Initiation Protocol (SIP) [START_REF] Rosenberg | Sip: Session initiation protocol[END_REF] servers.

We show that this scanning event escalated into persistent exploitation attempts towards the hosts that replied to the sipscan. We use our data to assess the effectiveness of scanning in terms of scan repliers and hosts that were eventually compromised. We find that 2% of the scanned IP addresses replied and at least 8% of the repliers were eventually compromised. Besides, our analysis shows that scanners originated primarily from Eastern countries, while the subsequent exploitation attempts originated from Western countries. This suggests that information about scan repliers was communicated to the subsequent attackers (likely through underground channels). Moreover, we observe 352,350 new scanner IP addresses and show that the sipscan was largely undetected by the IDS used in the observed network, which only raised alerts for 4% of the scan probes.

In summary, our work makes the following contributions:

-We conduct a first measurement study about Internet scanning focusing on scan repliers and the aftermath of scanning. -We show that significant exploitation activity followed a specific scanning event and estimate the success rate. -We provide new insights about Internet scanning and the sipscan: 1) we observe a segregation of roles between scanners and exploiters; and 2) that the sipscan originated from 352,350 new IP addresses.

The rest of the paper is structured as follows. We first discuss related research in Section 2. In Section 3 we describe the used data-sets. Then, Section 4 presents how unsampled NetFlow records were used to detect the sipscan and measure scan repliers. Then, in Section 5 we characterize the exploitation activity that followed based on our IDS data. Finally, Section 6 discusses the impact of falsepositive IDS alerts on our analysis and Section 7 concludes our paper.

Related Work

A long line of measurement studies has analyzed botnets over the last years, following their evolution from centralized IRC-based [START_REF] Cooke | The zombie roundup: Understanding, detecting, and disrupting botnets[END_REF][START_REF] Barford | An inside look at botnets[END_REF] to fully decentralized C&C architectures [START_REF] Holz | Measurements and mitigation of peer-to-peer-based botnets: A case study on storm worm[END_REF]. The goal of these efforts has been to characterize botnet activities [START_REF] Rajab | A multifaceted approach to understanding the botnet phenomenon[END_REF], analyze C&C communication methods [START_REF] Cooke | The zombie roundup: Understanding, detecting, and disrupting botnets[END_REF], and estimate the respective botnet size and geographical properties [START_REF] Stone-Gross | Your botnet is my botnet: Analysis of a botnet takeover[END_REF]. Their observations have been used to fine tune network defences [START_REF] Felix | Botnet Tracking: Exploring a Root-Cause Methodology to Prevent Distributed Denial-of-Service Attacks[END_REF] and tailor novel detection mechanisms [START_REF] Gu | BotSniffer: Detecting Botnet Command and Control Channels in Network Traffic[END_REF].

One of the most integral aspects of botnet activity is scanning. Since scanning is widespread [START_REF] Glatz | Classifying internet one-way traffic[END_REF] and regularly captured by monitoring infrastructures [START_REF] Bacher | Know your enemy: Tracking botnets[END_REF][START_REF] Barford | An inside look at botnets[END_REF], it is imperative for security analysts to have a measure regarding its severity and impact on the victim population. However, few studies have focused on the probing characteristics of botnets. In [28] Paxson et al. analyzed traffic captured at honeynets in order to study the statistical properties of 22 large-scale scanning events. In a followup study, Li et al. [START_REF] Li | Towards situational awareness of largescale botnet probing events[END_REF] extracted botnet scan traffic from honeynet data and used it to infer general properties of botnets, such as population characteristics, blacklisting effectiveness, dynamics of new bot arrivals and scanning strategies. Finally, Yegneswaran et al. [START_REF] Barford | An inside look at botnets[END_REF] analyzed the source code of a widely-used botnet malware, revealing the scanning capabilities of basic IRC bots.

Most related to our work, Dainotti et al [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF] discovered an interesting stealthy scan of the entire IPv4 address space that was carried out by the Sality botnet and analyzed the different phases of the event. However, this study was based solely on packet traces collected at the UCSD network telescope and does not provide insights regarding the effectiveness of scanning and its followup activity. In our work, we detect the sipscan in a large ISP with live hosts, identify the set of hosts that replied to scanners, and analyze the targeted exploitation activity that followed. This way, we provide new insights about the escalation of this event and the effectiveness of scanning in terms of turnover.

Monitoring Infrastructure and Data Collection

In this section, we describe the monitored network and the data we use in this study. We collected our measurements from the network of the main campus of the Swiss Federal Institute of Technology at Zurich (ETH Zurich). The ETH Zurich network is large and diverse. During our data collection period, which spanned 5 months (between the 1st January and the 31th of May 2011), we observed in total 79,821 internal hosts. On these hosts, the IT policy grants full freedom to users regarding the software and services they can use.

We select two data sources that provide complementary views into the studied event. First, we collect unsampled NetFlow data from the only upstream provider of ETH Zurich. Netflow produces summary records for all flows crossing the monitoring point. However, Netflow lacks context, since it does not provide information regarding the type of activity that triggered a flow. To fill this gap, we use IDS data collected from a Snort sensor, which captures and analyzes all traffic crossing our infrastructure's border router. Snort uses signature-based payload matching to perform protocol analysis, revealing more information about the type of activity that triggered an observed packet sequence. The two passive monitoring data sets complement each other, since they capture flow summaries for all traffic and finer (payload/header) details for packets that trigger IDS sig-natures. A detailed description of our data collection methodology can be found in our accompanying technical report [START_REF] Raftopoulos | The days after a "/0" scan from the sality botnet[END_REF].

Sipscan Detection

To extract sipscan traffic from NetFlow data, we rely on heuristics introduced by Dainotti et al. [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF], which are based on the analysis of the payload of sipscan packets. However, because flow data do not include packet payload contents, we adapted the extraction rules. We focus on the UDP part of sipscan traffic, which is sufficient to detect sipscan activity and identify sipscan sources. Specifically, we identify a sipscan flow as a single-packet one-way flow towards port 5060/udp having a size in the range of 382 to 451 bytes. In Figure 1a, we highlight how the host population sourcing attacks towards the SIP service port evolved over 16.7 days (from 31/01/2011 to 16/02/2011). In Figure 1b, we illustrate how the same event was captured by the UCSD network telescope. Note that Dainotti et al. [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF] used full packet traces collected at the network telescope in order to estimate the scanning population. The similarity in these two patterns, indicates that our heuristic adapted to Netflow records, is able to capture the same phenomenon as seen on our network. We observe two major sipscan outbreaks in terms of participating attackers along with a minor fraction of hosts engaged continuously in SIP scanning. The first outbreak starts at 2011.01.31 21:30 UTC and lasts until approximately 2011.02.06 22:40, while the second outbreak starts at 2011.02.11 14:10 and lasts until 2011.02.12 15:00 UTC. In total, 952,652 scanners participated in the scan. A significant number (352,350) of hosts targeting our infrastructure were not observed in the population of Sality scanners detected by the UCSD network telescope, which were 2,954,108 [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF]. This finding indicates that the size (expressed in terms of source IP addresses) of the botnet was at least 11.9% larger than the lower bound estimated in the previous work. At the victim side, 77,158 hosts within ETH Zurich were scanned at least once during the 16.7 days period, meaning that the coverage of the scan in our infrastructure was 96.6%. The scan was largely stealthy, in terms of generated alerts from the IDS, since only 4% of the respective probing flows triggered a scan-related IDS signature.

In contrast to [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF], our data set allows us to identify those target hosts that reply to the sender of a sipscan flow. For this purpose, we search for two-way flows matching a relaxed filter (i.e., requiring port 5060/UDP only). Additionally, we look at the number of attacker-victim host pairs where a sipscan flow is answered with an ICMP flow. For this answer type, we see a weak correlation of ICMP flow counts with the two sipscan outbreaks. On the other hand, when looking at host pairs where we have biflows, we observe a strong correlation of biflow counts with the sipscan outbreaks indicating that sipscan attacks significantly result in bidirectional communication between attacker and victim. In Figure 1a we present the number of unique internal IP source addresses responding to the sipscan. In total, we identify 1,748 sipscan repliers, whereas during the scan we find 3.8 new unique internal IPs responding to the scan every hour. For 80.2% of the repliers we detected a TCP reply originating from the respective host, whereas for 8.3% of the repliers, the sipscan was answered with an ICMP flow. 0.2% of the replies involved both a TCP and an ICMP flow, while the remaining 11.5% used neither TCP or ICMP.

Aftermath of the Sipscan

Inbound exploitation attempts

In this section, we study the impact of the sipscan on the target host population within ETH Zurich. We first investigate if scanning was a precursor of subsequent exploitation attempts targeting hosts that replied to the scanners. Recall that our IDS data cover 5 months, including one month before the beginning of the sipscan (31/01/2011) and approximately 3.5 months after its end (16/02/2011).

In Figure 2a, we show how the daily number of exploitation alerts per target host triggered by inbound traffic changed after the sipscan. We consider alerts of the VRT rule sets exploit.rules, exploit-kit.rules, and indicator-shellcode.rules and of the ET rule set emerging-exploit.rules. These rule sets [START_REF] Raftopoulos | The days after a "/0" scan from the sality botnet[END_REF] are tailored to detect exploit activity, including buffer overflow attacks, remote command execution, brute force authorization and privilege escalation attempts. In Figure 2a, we also show the daily number of exploitation alerts per target host for the baseline, i.e., the ETH Zurich hosts that did not reply to the scanners according to our data. The baseline accounts for 78,073 hosts, whereas the number of sipscan repliers is 1,748. In the pre-sipscan period sipscan repliers were involved on average in 122 exploitation alerts per day. During the sipscan period we see that this number increases to 842 alerts per day, whereas after the sipscan it remains high at 931 alerts per day. In sharp contrast, the inbound exploitation activity associated with the baseline remains low after the sipscan. On average, each host is a target to 1.2 alerts per day, which is a baseline noise caused by automated threats attempting to propagate and false alerts. The respective noise level for the sipscan repliers in the pre-sipscan period is 0.4 alerts per day.

After the sipscan, this number increases to 3.7 alerts per day. The high number of exploitation alerts towards sipscan repliers persists even 4 months after the end of the sipscan, although it is more intense during the first two months (from 31/1 to 28/2), when 68% of the total exploitation alerts are triggered. Out of the 1,748 sipscan repliers, we observe that 852 were involved in inbound exploitation alerts.

Next, we study whether the observed increase in exploitation activity comes from new offenders. Figure 2b illustrates the daily number of new offending IP addresses per target host for sipscan repliers and for the baseline. We report IP addresses that appear in exploitation alerts, however we consider an address new only when it has not previously appeared in the entire alert trace. A baseline host records a new external attacker approximately every four days consistently throughout the 5-month period. However, this number increases sharply for sipscan repliers during the sipscan, when each victim is attacked on average by 1.4 new IP addresses per day. Moreover, we investigate whether these IP addresses are known blacklisted hosts using four public blacklists [START_REF]Anonymous postmasters early warning system[END_REF]3,[START_REF]Dshield: Internet storm center[END_REF][START_REF]Threatexpert -automated threat analysis[END_REF]. Figure 2b shows that only 7% of the new offenders were already blacklisted, while this number drops to almost 0 before and after the sipscan period.

In addition, we explore how persistent the attacking hosts are in terms of generated exploitation alerts, and examine whether the attackers targeting the sipscan repliers are more persistent compared to the ones targeting the baseline. In Figure 3a, we compare the average number of exploitation alerts per target for sipscan repliers and baseline attackers, respectively. We see that the former group tends to be more persistent triggering in the median case 4 exploitation alerts per target, whereas the same number for the latter group is 2 alerts. The increased persistence towards sipscan repliers is more prominent in the tails of the distributions. We see that the top 10% most active attackers towards sipscan repliers launch up to 73 alerts on average per target, whereas the respective number for the baseline is only 21 alerts. We also investigate the similarity between the IP addresses of scanners (extracted from NetFlow) and of exploiters (extracted from Snort alerts towards sipscan repliers). Surprisingly, we observe that out of 6,676 exploiter and 1.3 million scanner IP addresses, only 17 are in common. This suggests that there is a clear separation between scanners and bots wielded to exploit target hosts. In Table 1, we compare the geographical distribution of the scanners detected in our infrastructure and in the UCSD network telescope [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF] with the exploiters targeting the ETH Zurich sipscan repliers. The geographical distribution of scanners seen in the UCSD network telescope and in ETH Zurich is very similar with the exception of China. In our data set China is a significant source of SIP scanning accounting for 7.32% of the total scanners population. On the UCSD data set China is ranked 27th. More importantly, the geographical distribution of exploiters is particularly interesting, since it is dominated by Western countries and United States in particular, which is the most strongly represented country with 27.11% of the exploiters. In contrast, the geographical distribution of scan-ners is dominated by Eastern countries. US is not sourcing sipscanning, which is remarkable since the analysis of the botnet has shown a strong presence in the United States [START_REF] Falliere | Sality: Story of a peer-to-peer viral network[END_REF]. This observation shows that information about scan repliers was communicated from scanning to attacking bots through unknown channels.

Finally, we examine the exploitation activity on port numbers related to SIP. Figure 3b shows the number of exploitation alerts targeting sipscan repliers on ports 5060, 5061, 5070 and 80. Ports 5060, 5061 and 5070 are used by SIP for control and data traffic. Moreover, the sipscan binary attempts to open a connection and gain administration privileges on port 80, where an HTTP server may provide remote administration to SIP servers [START_REF] Falliere | A distributed cracker for voip[END_REF]. Figure 3b shows a sharp increase of exploitation activity targeting SIP ports during and after the sipscan. Before, the sipscan we observe on a daily basis less than 12 exploitation alerts targeting SIP ports and 3 alerts targeting port 80. During the sipscan period, these numbers jump to 135 and 27, respectively, exhibiting approximately a ten-fold increase. Moreover, during the sipscan period 22% of all inbound exploitation alerts are on SIP ports. In the post-scan period we observe that these values drop, but still remain significant compared to the pre-sipscan period. Specifically, the daily number of exploitation alerts targeting SIP ports and port 80 are 5 and 21, respectively.

To summarize the key findings of this section, we first observe a steep increase in exploitation alerts against sipscan repliers right after the sipscan, which is associated only with sipscan repliers and not with other hosts in the monitored infrastructure. Second, we observe that the attackers associated with the increase appear for the first time during the sipscan and were not active before. Third, we observe a sharp increase in exploitation alerts towards SIP ports and show that these exploitation attempts happen in close temporal proximity to the sipscan. We believe these findings constitute sufficient evidence that the sipscan was the precursor of a subsequent large-scale exploitation activity targeting sipscan repliers.

Sality alert classification and outbound exploitation activity

In Sections 4 and 5.1, we analyzed the inbound scanning and exploitation activity towards the monitored network. In this section, we shift our attention to IDS alerts raised by outbound traffic originated by sipscan repliers, and analyze the new behavioral patterns that emerge. A comprehensive overview of the activity exhibited by the Sality bot based on the forensics investigation of compromised hosts can be found in our technical report [START_REF] Raftopoulos | The days after a "/0" scan from the sality botnet[END_REF].

In Table 2, we list the Snort identifiers (SIDs) and their official short description for relevant signatures that are triggered in our data. To compile the list, we manually analyzed the outbound alerts generated by sipscan repliers. We found the new types of alerts that emerged in the post-scan period and inspected their signatures in order to identify specific behaviors. We group signatures into four categories shown in Table 2.

Signatures in the group C&C Communication detect the activity triggered by a bot when calling its controller for instructions. In the case of the HTTP Signatures in the group Exfiltration are tailored to detect the exfiltration of confidential data. The SIDs [START_REF] Bacher | Know your enemy: Tracking botnets[END_REF]2006380) are triggered when passwords or email addresses are sent from the intranet unencrypted. The signature (2010784) is triggered when the bot is attempting to leak sensitive information using Facebook's POST mechanism. This alert should be expected to generate a significant amount of false positives, since it is also triggered when a user sends a legitimate Facebook message. However, a sudden sharp increase in the amount of Facebook POST operations could signify a malicious activity. The signatures with SIDs (2000347,1463) are triggered when information is exfiltrated using an IRC channel.

Signatures in the group Propagation are generated when the bot is attempting to infect exposed vulnerable hosts. The main targeted vulnerabilities are the MS-LSASS buffer overflow and the MS-WebDav vulnerability related to services used for accessing remote network shares. The set of signatures shown in Table Finally, signatures in the group Egg Download correspond to attempts made by the bot to fetch a malicious binary from a remote domain. The downloaded executable can be either an update of Sality's own code or can correspond to a new malware pushed to the infected population. Signatures with SIDs (15306,2003546,2007577 ) detect the activity of Sality's downloader module when attempting to check a suspicious URL or when a binary download is initiated. Sality tries to obfuscate the downloaded binary by hiding it in seemingly legitimate files, such as Text and PDF documents. This activity is detected by signatures with SIDs (2009897,19270 ). The obfuscation is used to evade detection by cloud providers, such as Dropbox and Megaupload, which are exploited in order to host the malicious content. Signatures with SIDs (2012648,2009301 ) detect the download of executables from these sites.

Figure 4a shows the average number of C&C alerts triggered by sipscan repliers and baseline hosts. For sipscan repliers, we differentiate between IRC and P2P C&C alerts, whereas for the baseline we include both types of alerts. After the sipscan, we see a sharp increase in the IRC C&C alerts, which indicates that hosts are attempting to contact known malicious IRC servers operating as controllers. This behavior continues for approximately two months, during which we see daily on average 2.4 C&C alerts per sipscan replier. However, on April 11 (day 111) there is a clear shift in the pattern of triggered signatures: the volume of IRC alerts suddenly drops, while the volume of P2P alerts rises. This signifies a likely upgrade in the mode of C&C communication of the Sality botnet.

Figure 4b illustrates the daily number of Egg Download alerts per sipscan replier and baseline host. After the sipscan, we observe 4 malware downloading spikes, during which the daily alert count ranges from 1.6 to 3.4 per sipscan replier. The spike that occurs on April 11 (day 111), seems to be associated with the shift in the communication method used to contact the controller shown in Figure 4a. We believe that during that event the Sality botnet pushed a major update to the infected population, upgrading itself from the centralized HTTP to the fully decentralized P2P version.

In Figure 4c, we show the daily number of Propagation alerts per local host for sipscan repliers and baseline hosts. We see that after the sipscan the number of outbound exploitation attempts originating from the sipscan repliers increases drastically, exhibiting an average daily value of 1.2 alerts per host compared to only 0.21 alerts per baseline host. The most dominant alerts of this group are the privilege escalation attempts with SIDs (4060,2006546,2002383,2010643) accounting for 72% of the observed activity.

Finally, Figure 4d illustrates the daily number of information leakage alerts per local host for sipscan repliers and baseline hosts. Again we see a sharp increase in the number of exfiltration alerts for sipscan repliers in the post-sipscan period, where the daily average increases from 4.7 to 18.2 alerts per host. The triggered alerts are dominated by the signature ET CHAT Facebook Chat POST Outbound, which accounts for 83% of all alerts. However, this signature is also triggered by legitimate user activity and may introduce a significant number of false positives. This is reflected in the high baseline in the pre-sipscan period, which accounts on average for 4.7 alerts per host. Although the baseline for this alert group is high, we can still see a clear increase in the post-sipscan period when its alert volume quadruples. Summarizing the key finding, we discovered major changes in the alert patterns of sipscan repliers that correlate with the behavior of the Sality bot.

Sality-bot infections

In this section, we build a heuristic to identify this behavioral shift and extract likely Sality infections. We use our heuristic to conservatively estimate a lower bound on the success rate of the sipscan in terms of infected hosts. Note, that we do not have the goal to build a general purpose detector, but rather a systematic way to identify infected sipscan repliers in the monitored network.

Our heuristic is summarized in Algorithm 1. We focus on sipscan repliers that were subsequently attacked. Then we find repliers that exhibit a persistent increase in outbound exploitation activity for the four signature classes listed in Table 2, while their respective activity in the pre-sipscan period is low. In particular, for the four classes in Table 2, we first compute the number of alerts per day each internal host generates. Our heuristic then finds and keeps hosts that trigger in the pre-sipscan period fewer alerts per day than the corresponding baseline of that day plus a tolerance of 1.5× the inter-quartile range of the baseline. If a host has more alerts per day even for a single day, then it is discarded from further consideration because it is either already infected or it generates a large number of false positives. Second, our heuristic makes the same comparison in the post-sipscan period. If the daily alert count is consistently above the tolerance threshold, then it constitutes an indication of compromise activity. To assess whether this increase persists, we count the number of daily bins where it is above the threshold and tolerate only 5% of the post-sipscan bins where this condition is not met. We consider only the bins in which a host has generated at least one alert of any type. Algorithm 1: Pseudo-code for identifying Sality-bot infections Our heuristic takes a conservative approach by introducing several conditions to make a Sality infection assessment. It is possible, however, that a Sality bot exhibits some of the post-sipscan behaviors presented in Section 5.2, but not all. For example, some examined hosts show persistent signs of C&C communication and attempts to propagate, but do not attempt to leak data. Others attempt to exfiltrate data, but do not frequently visit malicious domains to fetch malware. By tailoring our heuristic to only make an assessment if all alert types in the post-sipscan period exhibit a persistent increase, we attempt to minimize possible false positives even if we introduce a number of false negatives. This way, we believe we can estimate a lower bound of the Sality infections that occurred in our infrastructure.

Our heuristic identified a total of 142 Sality infections in our IDS data set. In the first stage of reconnaissance, 77,158 exposed ETH Zurich IPs were scanned. Out of these only 1,748 (2%) hosts replied to the scanners. Almost half of the sipscan repliers, specifically 48%, were subsequently the targets of inbound exploitation attacks. Based on our heuristic we identified that 142 hosts showed persistent signs of infection during the post-sipscan period. Therefore, the sipscan turnover, i.e. the percentage of hosts that were infected out of the sipscan repliers, was 8%.

Discussion about IDS false positives

The quality of IDS alerts we study in Section 5 heavily relies on the accuracy of the inferences made by the Snort sensor deployed in our infrastructure. Snort has been criticized for generating an excessive number of false positives, often exceeding 99% [START_REF] Julisch | Mining intrusion detection alarms for actionable knowledge[END_REF][START_REF] Kruegel | Alert verification -determining the success of intrusion attempts[END_REF]. Such high false positive rates can introduce significant bias in our measurements, resulting in skewed results. However, in this work we have focused on signatures which, based on our previous work [START_REF] Raftopoulos | Detecting, validating and characterizing computer infections in the wild[END_REF][START_REF] Raftopoulos | A quality metric for ids signatures: In the wild the size matters[END_REF], were shown to be reliable, generating only a small number of false positives. Specifically, in [START_REF] Raftopoulos | Detecting, validating and characterizing computer infections in the wild[END_REF] we performed a thorough evaluation of the alerts being triggered by Snort in our infrastructure and identified signatures that generate a large number of false positives. These alerts have been excluded from the current work. Moreover, in [START_REF] Raftopoulos | A quality metric for ids signatures: In the wild the size matters[END_REF] we introduced a complexity criterion to evaluate the effectiveness of a Snort signature in terms of correctly identifying malicious activity. The alerts analyzed in Section 5 are triggered by highly complex signatures, which our analysis in [START_REF] Raftopoulos | A quality metric for ids signatures: In the wild the size matters[END_REF] has shown to be more reliable, generating a low number of false positives.

Conclusions

In this work, we analyzed the aftermath of an Internet-wide scanning event [START_REF] Dainotti | Analysis of a "/0" Stealth Scan from a Botnet[END_REF] in a university network focusing on scan repliers. Using a unique combination of unsampled Netflow records and IDS alerts we found that the sipscan was followed by significant exploitation activity that led to at least 142 infected hosts in the studied network and likely many more worldwide. The effectiveness of scanning in terms of targeted hosts that replied and repliers that were eventually compromised was 2% and at least 8%, respectively. We also observed a segregation of roles between scanners and exploiters, which originated from different geographical locations. We therefore conclude that Internet scanning is dangerous as it leads to many compromised hosts. Understanding how these observations differ across networks and scanning events is an interesting subject for future research.

Fig. 1 :

 1 Fig. 1: Number of IP addresses per hour sourcing or replying to scan flows in ETH Zurich and in the UCSD network telescope.

Fig. 2 :

 2 Fig. 2: Daily number of inbound exploitation alerts and new offending IPs per target host over a period of 5 months. The shaded region marks the duration of the sipscan.

  Fig. 3: Persistence of exploitation attackers and alert volume for exploitation attempts targeting SIP related ports.

2

 2

  are fine-tuned to detect brute force privilege escalation attacks (4060,2006546, 2002383,2010643 ), buffer overflow exploitation attempts (2007695,2008070, 3817 ), and targeted scanning on these services (2001972 ,2001569 ).

  (a) C&C alerts. (b) Egg Download alerts. (c) Propagation alerts. (d) Exfiltration alerts.

Fig. 4 :

 4 Fig. 4: Daily number of different types of alerts per host for sipscan repliers and for baseline hosts over a period of 5 months.

Table 1 :

 1 Top 10 countries used by the sipscanners compared to the respective countries for exploitation attack originators. Geo location data for sipscan sources and exploitation attack originators was obtained using the MaxMind GeoIP Lite Database[START_REF]MaxMind Lite[END_REF].

		sipscanners CAIDA	sipscanners ETH	Exploiters ETH
	Rank	%	Country	%	Country	%	Country
	1	12.55	Turkey	10.06	Indonesia	27.11 United States
	2	12.54	India	9.72	Turkey	12.70 Canada
	3	8.64	Brazil	7.32	China	9.90	China
	4	7.23	Egypt	6.86	Brazil	7.01	Switzerland
	5	5.77	Indonesia	6.52	Egypt	4.98	Germany
	6	5.59	Romania	5.94	India	4.78	Taiwan
	7	5.58	Russian Federation	4.80	Thailand	4.31	Japan
	8	5.36	Vietnam	4.06	Philippines	3.31	India
	9	5.10	Thailand	3.71	Russian Federation	2.95	Russian Federation
	10	3.01	Ukraine	3.20	Romania	2.88	Brazil

Table 2 :

 2 Snort signatures related to Sality bot lifecycle.

	SID	Signature Description
		[C&C Communication] Communication with botnet controller.
	2404138:2404156	ET DROP Known Bot C&C Server Traffic TCP/UDP
	2000348	ET ATTACK RESPONSE IRC -Channel JOIN on non-std port
	2000334	ET P2P BitTorrent peer sync
	2009971	ET P2P eMule KAD Network Hello Request
	2008581	ET P2p BitTorrent DHT ping Outbound
	2010142	ET P2P Vuze BT UDP Connection Outbound
	2008584	ET P2P BitTorrent DHT announce peers request
	2181	P2P BitTorrent transfer
		[Exfiltration] Possible leakage of sensitive user data.
	5	SENSITIVE-DATA Email Addresses Outbound
	2006380	ET Policy Outgoing Basic Auth Base64 HTTP Password detected unencrypted
	2010784	ET CHAT Facebook Chat POST Outbound
	2000347	ET ATTACK RESPONSE IRC -Private message on non-std port
	1463	CHAT IRC message Outbound
		[Propagation] Attempted infection of vulnerable hosts.
	2007695,2008070	ET User-Agent Malware overflow attempt
	4060	POLICY RDP attempted administrator connection request
	2006546	ET SCAN LibSSH Based SSH Connection -BruteForce Attack
	2002383	ET SCAN Potential FTP Brute-Force attempt
	3817	TFTP GET transfer mode overflow attempt
	2010643	ET SCAN Multiple FTP Administrator Login Attempts-Brute Force Attempt
	2001972	ET SCAN Behavioral Unusually fast Terminal Server Traffic, Potential Scan or Infection
	2001569	ET SCAN Behavioral Unusual Port 445 traffic
		[Egg Download] Possible download of malicious executable.
	2009897	ET MALWARE Possible Windows Executable sent when remote host claims to send a Text File
	19270	POLICY attempted download of a PDF with embedded Javascript
	15306	WEB-CLIENT Portable Executable binary file transfer
	2003546	ET USER Agents Suspicious User agent Downloader
	2007577	ET TROJAN General Downloader Checkin URL
	2012648	ET Policy Dropbox Client Downloading Executable
	2009301	ET Policy Megaupload file download service access
	version of the Sality bot, the signatures in the SID range (2404138:2404156) are
	triggered when a set of known blacklisted C&C servers are contacted, whereas
	the signature (2000348) detects the setup of an IRC channel, which is used by
	the bot and the controller to communicate. The remaining alerts are related to
	the P2P version of the bot and are triggered when the bot is either attempting
	to join the P2P network, instantiating a new P2P connection, or fetching the
	latest peers list.

  : IQR of S type alerts generated by Baseline hosts on day T R S T : mean count of S type alerts generated by sipscan repliers on day T S={CnC Communication, Reporting, Propagation, Egg Download} Result: Returns true if the examined host is infected, false otherwise.

	Input:
	B S T : mean count of S type alerts generated by Baseline hosts on day T I S T Signif icanceT hresh = B S T i + 1.5 * I S T i ;
	if T i ≤ Tscan then
	if R S T i > Signif icanceT hresh then return false;
	end
	else
	if R S T i ≤ Signif icanceT hresh then BelowT hreshCount += 1;
	end
	end
	if BelowT hreshCount /(Tmax -Tscan) > 0.05 then
	return false;
	end
	end
	end
	return true;

foreach alert type S do BelowT hreshCount = 0; for T i = 1:Tmax do if isHostActiveAt(T i ) eq false then next;