Valentin Thirion

Benoit Donnet

Tracking Middleboxes in the Mobile World with TraceboxAndroid

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

It has been a while, now, the Research Community has tried to use computing resources made available by end-users. One of the most famous tentative is probably SETI@home [START_REF] Anderson | SETI@home: An experiment in public-resource computing[END_REF]. SETI@home provides a screensaver that users can freely install, and that downloads and analyzes radio-telescope data for signs of intelligent life. The project obtains a portion of the computing power of the users' computers, and in turn the users are rewarded by the knowledge that they are participating in a collective research effort, by attractive visualizations of the data, and by having their contributions publicly acknowledged. This model has been followed by others, in particular for performing large-scale Internet topology data collection [START_REF] Shavitt | DIMES: Let the internet measure itself[END_REF][START_REF] Chen | Where the sidewalk ends: Extending the Internet AS graph using traceroutes from P2P users[END_REF].

Meanwhile, we have seen the rise of mobile devices at the expense of a drop in desk-based and notebook computers [START_REF] Rivera | Forecast: Devices by operating system and user type, worldwide[END_REF]. Mobile data usage is increasing rapidly in part due to a growing release of mobile devices and the availability of a wide variety of mobile phone applications. For instance, a large number of users nowadays use their mobile devices to watch video on demand (e.g., YouTube) while on the move. Naturally, the idea of using crowdsourcing with mobile devices to measure the Internet has emerged. However, the particularities of those devices make network measurements a difficult task [START_REF] Faggiani | On the feasibility of measurement the Internet through smartphone-based crowdsourcing[END_REF].

In addition, the Internet infrastructure has strongly evolved. In particular, we have seen the growing importance of middleboxes (i.e., "an intermediary box performing functions apart from normal, standard functions of an IP router on the data path between a source host and destination host" [START_REF] Carpenter | Middleboxes: Taxonomy and issues[END_REF]). For instance, Sherry et al. [START_REF] Sherry | Making middleboxes someone else's problem: Network processing as a cloud service[END_REF] obtained configurations from 57 enterprise networks and revealed that they can contain as many middleboxes as routers. Wang et al. [START_REF] Wang | An untold story of middleboxes in cellular networks[END_REF] surveyed 107 cellular networks and found that 82 of them used NATs. Those middleboxes has shown to have a negative impact on the evolvability of the TCP/IP protocol suite [START_REF] Honda | Is it still possible to extend TCP[END_REF].

Combining the rise of mobile devices and the importance of middleboxes leads to a natural question: are the middleboxes a cause of degraded performance in mobile networks and can we provide tools for monitoring and discovering problems with end-user Quality of Experience (QoE) due to their presence. The first part of the question has already been answered. Wang et al. [START_REF] Wang | An untold story of middleboxes in cellular networks[END_REF] have demonstrated that middleboxes are, indeed, a brake to mobile network performance in mobile networks.

In this paper, we tackle the second part of the question by proposing a proofof-concept tool called TraceboxAndroid. TraceboxAndroid is based on tracebox [START_REF] Detal | Revealing middlebox interference with tracebox[END_REF], a traceroute extension that is able to reveal the presence of middleboxes along a path. We have ported tracebox under the Android system, allowing so the user to detect the presence of a middlebox that could be the cause of a degraded performance on a path. We describe the architecture of TraceboxAndroid and deploy it on several mobile devices across the world in order to demonstrate its potentialities. In addition, TraceboxAndroid is lightweight for mobile devices in terms of battery and memory consumption. TraceboxAndroid is freely available (http://androidtracebox.org).

The remainder of this paper is organized as follows: Sec. 2 explains how tracebox works; Sec. 3 presents TraceboxAndroid, our tracebox port into Android devices; Sec. 4 explains our TraceboxAndroid deployment, data collection, and results we obtained; Sec. 5 positions this paper regarding the state of the art; finally, Sec. 6 concludes this paper by summarizing its main achievements.

Tracebox

To reveal the presence of middleboxes along a path, we use tracebox [START_REF] Detal | Revealing middlebox interference with tracebox[END_REF], an extension to the widely used traceroute.

tracebox mechanism is illustrated in Fig. 1. It relies on RFC1812 [START_REF] Baker | Requirements for IP version[END_REF] and RFC792 [START_REF] Postel | Internet control message protocol[END_REF] stating that the returned ICMP time-exceeded message should quote the IP header of the original packet and respectively the complete payload or the first 64 bits. tracebox uses the same incremental approach as traceroute, i.e., it sends packets with different IP, UDP, or TCP fields and options with increasing TTL values. By comparing the quoted packet to the original, one can highlight the modifications and the initial TTL value allows us to localize the two or more hops between which the change took place. In Fig. 1, packet a is the originally sent one. The first hop, that happens to be a middlebox, modifies When the tracebox client receives it, it is able to compare packet a and the payload of packet c to detect any changes and the initial TTL value, i.e., 2, allows tracebox to bound the middlebox location.

It is worth to notice that in 80% of the cases [START_REF] Detal | Revealing middlebox interference with tracebox[END_REF], a path contains at least one router which implement RFC1812 [START_REF] Baker | Requirements for IP version[END_REF], that recommends to quote the entire IP packet in the returned ICMP. This means that, in most cases, tracebox is able to detect any modification performed by upstream middleboxes.

TraceboxAndroid

tracebox has been originally developed to work on desk-based computers, on a UNIX-like system. We have ported tracebox on Android mobile devices. Our application is called TraceboxAndroid.

Fig. 2 illustrates the general TraceboxAndroid architecture. As shown, it is made of three main components: the system core where the tracebox intelligence has been included (coded in C, under the front office), the front office (or the application) corresponding to the Android application (coded in Java) and the back office (or server -coded in PHP and HTML) that is used to store data and make offline analysis.

The front office communicates with the server using an XML API that gives the application the destinations to be probed and allows it to send back the data collected by the system core. The core itself implements tracebox (as described in Sec. 2) and sends probes to the destinations using sockets by system calls.

The front office and the system core are freely available1 since mid-2014. In the subsequent sections, we deepen each component. As shown on the figure 5.1, I developed three modules in three di↵erent languages (PHP/HTML for the server, JAVA for the App and C for the Core). The App communicates with the server using an API based in XML that gives the App the destinations to be probed and allows the App to send the results from probes. The App communicates to the Core using an API provided by the Android SDK (using Process and Runtime classes, as described further. The Core itself send probes to the destinations using sockets by system calls.

The Android app is to be available on the Play Store and widely deployed in order to get results from all over the world and the more cellular carriers possible. A clear representation of the deployed system is presented in figure 5.2.

The Android app is composed of 2518 lines of code in JAVA, 2556 lines of PHP create the back o ce and the core is made of 633 lines in C.

System Core

TraceboxAndroid is based on BusyBox [START_REF] Vlasenko | BusyBox: the swiss army knife of embedded Linux[END_REF], a software written in C that aims at providing Unix tools for operating systems with limited resources. In particular, it contains a basic networking tool suite (e.g., ping, netstat, netcat, traceroute, etc). We started from the latter source code to port tracebox into Android systems.

The main challenge we had to address is that tracebox requires the use of raw sockets to manually set IP fields, TCP fields, and TCP options, and retrieve the received headers. As the use of raw sockets is restricted to users that can grant the CAP_NET_RAW POSIX capability (i.e., super users), we chose to exclude non-rooted devices and call the TraceboxAndroid BusyBox implementation from the JAVA app as a super user. While this limitation is crippling for extended use, as already stated by Faggiani et al. [START_REF] Faggiani | On the feasibility of measurement the Internet through smartphone-based crowdsourcing[END_REF], it seems reasonable for a proof-of-concept implementation.

TraceboxAndroid system core consists in a C applet which is called by a lightweight BusyBox version. The underlying tracebox implementation is based on the algorithm described in Sec. 2 and supports TCP/IPv4 and diverse TCP options (e.g., SelectiveACK, Timestamp, MSS, WindowScale, MultipathTCP).

Front Office

The front office (or application) purpose is to send tracebox probes to predetermined or user-chosen destinations, compute the result, and send it back to the back office. In some sense, it acts as a proxy between the system core and the back office. Three probing mechanisms are available in the Front Office menu:

-Background Probing: background probes are sent by a scheduled task that is executed several times a day while the phone is connected to a network, even if the user shuts down the application.

The user is able to edit the configuration of the scheduled probing by setting the number of destinations to be probed during one probing session and the maximum duration of a session. -Instant Probing: an Instant probe is a one-time single measurement sent to a random destination within the destination set. The user can choose to run an Instant probe at any time and retrieve the results. -Custom Probing: the Custom probing mode is similar to the Instant Probing but allows the user to set the destination.

Background Probing is mostly for research purposes. The two others are much more dedicated to given network monitoring/analysis in case of a drop in the QoE observed by the user.

The user is also able to check the results, consult the logs, and get information about the application and all the tools that were used to create it.

The architecture of the front office is displayed in Fig. 3. It is divided in three packages; (i) the Main package that is mainly composed of Activity classes that are responsible for drawing the views, monitoring the state of the app, receiving user commands, and launching AsyncTask to perform various operations (e.g., send an Instant Probe, parse an XML file, etc); (ii) the Core package contains utility and long-lived action managing classes that executes Unix commands and fetch the results, sends the result to the back office component and runs the tracebox applet; (iii) finally, the Data package is composed of classes maintaining information about processes and is responsible of managing an internal SQLite database.

The database stores information about destinations, probes, routers, packet modifications, and the logs. In addition to the probed routers inferred characteristics, the GPS position of the device at the probing time, Internet connection mode (i.e., WiFi, cellular, or Bluetooth), the cellular mode and carrier name (in case of a cellular network connection), and the battery consumption are saved into the local database before being sent to the back office.

Back Office

The back office is the server-side application that stores data collected by the mobile devices. It also manages the destinations probed by the application.

The back office has no other purpose than research (i.e., conserving collected data and off line analysis). The user cannot access the back office directly but has the opportunity to analyze data if he selected Instant or Custom probing, or to download the dataset on the website.

Evaluation

In this section, we explain our evaluation of TraceboxAndroid. In particular, we discuss our measurement methodology, describe our dataset, and analyze our results.

Methodology

We built an initial probe target set from the Alexa top-500 websites list, that we pre-resolved using Google Public DNS into 406 unique addresses, avoiding so a resolution on every mobile device that could consume undue resources and that could lead to completely different probed paths, making statistics meaningless. This address set is used by TraceboxAndroid Background Probing and Instant Probing features. It is, however, obvious that in case of selecting the Custom Probing feature, the DNS resolution will be done by the app.

Between On the whole set of probes sent, 1,372 (78.13%) were done through WiFi connections. The remaining 384 probes (21.87%) were sent through cellular connections.

This dataset is limited but sufficient to demonstrate the extent of Trace-boxAndroid capabilities. Moreover, as the Android app was still under development during most measurements, the following results and figures should be considered as illustrations of the variety of the app capabilities rather than rigorous observations.

Results

We first look at paths collected and, in particular, at their length distribution. Path lengths are computed on a subset of the paths collected. From the whole set, we select those that have unique <source;destination> address pairs to compute their lengths. This subset contains 606 paths, 388 of them were obtained via WiFi connections (64.9%) and 218 via cellular connections (35.97%).

The results are displayed in Fig. 4. We see that WiFi paths are 1.14 hops longer on average than cellular networks paths, their respective path length means being 15.8 and 14.67 hops.

The location of the first observed middlebox, in number of hops away from the probing source, is shown in Fig. 5. We see that 272 among 361 (75.32%) WiFi paths and 147 among 215 (68.37%) cellular paths that involves a middlebox had their first probe modified close to the mobile device, respectively at hops 6 and 4.

WiFi probes have crossed 180 different different ASs (Autonomous Systems) and cellular probes have crossed 139 different ASs. The AS overlap between the two types of probes includes 111 ASs. The three autonomous systems that WiFi probes have traversed the most are HIBERNIA TripartZ,NL, BELGACOM-SKYNET,BE and TTNET,TR, for cellular probes these are BASE-AS,BE, KPN Interational,NL and UUNET,US. The types of crossed ASs are somewhat We next check IP and TCP modifications. They are inferred using the tracebox algorithm described in Sec. 2. As probes have common subpaths, we counted each answering device only once based on the source IP addresses. The resulting set is composed of 3,109 routers, 175 (5.63%) of them exhibit middlebox behaviors. We have observed that 2,304 routers answered through WiFi connections and 1,392 were probed through cellular connections, among them tracebox respectively detected 103 (4.47%) and 87 (6.25%) middleboxes. Note that 587 routers have been probed via WiFI and cellular data networks.

The amount of detected middleboxes in this set has to be put in perspective with their strategic positioning; from the unique paths set explained above, 576 among 606 (95.05%) paths are crossing at least one middlebox that modifies at least one IP header, TCP header field, or TCP option. 361 among 389 (93.04%) WiFi paths and 215 among 218 (98.62%) cellular network paths involves a rewriting middlebox.

Fig. 6 summarizes those modifications. The TCP checksum is recomputed by many middleboxes, those that modifies IP pseudo-header fields, TCP fields, and TCP options. It is natural to see that 3.5% of the total observed routers are modifying it. Besides the TCP checksum, four fields are rewritten more often: IP ToS, IP-ID, TCP source port and TCP sequence number. This modification set exactly matches NATs rewriting behavior.

IP ToS rewriting can either come from routers using its DiffServCodePoints (DSCP) sub-field to mark packets for differentiated services, or modifying the last two Explicit Congestion Notification (ECN) bits. The latter modification can either be the action of legacy routers trying to modify the legacy 8-bits ToS field instead of the 6-bits DSCP field, unintentionally modifying ECN-related bits, or a systematic clearance of ECN bits [START_REF] Kühlwind | On the state of ECN and TCP options on the Internet[END_REF].

In several operating systems, IP-ID fields of self-forged packets are filled with the value of a globally-incremented packet counter, which is known to be a sidechannel leaking information about other connections [START_REF] Gilad | Spying in the dark: TCP and tor traffic analysis[END_REF]. Security consequences when endpoints use such a counter to write IP-ID have been discussed multiple times and involves enabling attackers to perform idle scan attacks, NATted hosts counting, facilitating TCP injections and more [START_REF] Bellovin | A technique for counting NATed hosts[END_REF][START_REF] Zalewski | Silence on the Wire: a Field Guide to Passive Reconnaissance and Indirect Attacks[END_REF][START_REF] Gilad | Off-path attacking the web[END_REF][START_REF] West | TCP/IP field behavior[END_REF], but consequences when it is performed by middleboxes for either self-forged or certain non self-forged packets have been less discussed. One of the most harmful known exploitation of middleboxes using a globally-incremented IP-ID is when it is combined with TCP window-checking, as it enables attackers to gain feedback on in-window/out-ofwindow packets to infer the TCP sequence number, and perform off-path TCP injections [START_REF] Gilad | Off-path attacking the web[END_REF][START_REF] Qian | Off-path TCP sequence number inference aattack -how firewall middleboxes reduce security[END_REF][START_REF] Qian | Collaborative TCP sequence number inference attack: How to crack sequence number under a second[END_REF].

Source port modification is a common practice of Carrier-Grade NATs (CGNs), which makes it difficult for traffic intended for machines located behind it to pass through (e.g., active FTP). However, solutions to this problem have been proposed [START_REF] Wing | Port control protocol (PCP)[END_REF]. TCP ports modification by middleboxes also makes it difficult to achieve transport layer security (e.g., IPSEC) [START_REF] Aboba | IPsec-network address translation (NAT) compatibility requirements[END_REF].

TCP sequence number modification is mostly due to initial sequence number (ISN) re-shuffling middlebox policies, which aim at mitigating ISN prediction attacks [START_REF] Detal | Revealing middlebox interference with tracebox[END_REF]. Such policies are known to create inconsistencies with TCP options using absolute sequence numbers such as Selective ACKnowledgement (SACK), and to reduce substantially the maximum achievable bandwidth [START_REF] Medina | Measuring interactions between transport protocols and middleboxes[END_REF][START_REF] Hesmans | Are TCP extensions middlebox-proof?[END_REF].

TCP Options modifications are shown in Fig. 7. We witnessed multiple middleboxes rewriting the MSS in cellular networks to 1,392 bytes, which is probably designed to obtain packets of 1,500 bytes taking into account the sizes of the desired headers. Among the other options, MultiPathTCP have been cleared by some middleboxes to forbid its use, and is also prone to be blocked by middleboxes that are not familiar with it [START_REF] Hesmans | Are TCP extensions middlebox-proof?[END_REF]. WindowScale have been modified by a few middleboxes to custom values, probably for network performance optimization purposes. WindowScale is also known to cause connectivity problems with certain firewalls that do not implement it as defined in RFC1323 [START_REF] Jacobson | TCP extension for high performance[END_REF][START_REF]Microsoft: Network connectivity fails when you try to use Windows Vista behind a firewall device[END_REF]. Overall, we showed that TraceboxAndroid can be used efficiently for deducing certain network disruption causes from inferred middlebox policies. This can be useful to users for fast on-demand troubleshooting purposes, for researchers that could analyze the collected dataset to get insights such as the permeability of a TCP option, and for network managers to understand what is really happening to packets crossing their networks.

Impact on Mobile Devices

To test the impact of the use of TraceboxAndroid on mobile phones, we used the Android Monitoring tool [START_REF]Android Developers: Device monitor See[END_REF]. In more than 99% of the cases, a Background Probing session with 10 destinations consumes less than one percent of battery. The same probing session never sent more than 165Kb of data, including the XML result file sent to the back office. We also did CPU and memory consumption measurements whose results are shown in Table 1. The experiments were made on a Samsung Galaxy SII (1,4Ghz, 1GB RAM, Android 4.3) and a Arnova 10d G3 (1,2Ghz, 1GB RAM, Android 4.1.1). Clearly, TraceboxAndroid is lightweight for mobile devices.

Related Work

Since the end of the nineties, the Internet topology discovery has been extensively studied [START_REF] Donnet | Internet topology discovery: a survey[END_REF]. In particular, traceroute has been used for revealing IP interfaces along the path between a source and a destination. Since then, traceroute has been extended in order to mitigate its intrinsic limitations. From simple extensions (i.e., the types of probes sent [START_REF] Luckie | Traceroute probe methode and forward IP path inference[END_REF]) to much more developed modifications. For instance, traceroute has been improved to face load balancing [START_REF] Augustin | Avoiding traceroute anomalies with Paris traceroute[END_REF] or the reverse path [START_REF] Katz-Bassett | Reverse traceroute[END_REF]. Its probing speed and efficiency has also been investigated [START_REF] Donnet | Efficient algorithms for largescale topology discovery[END_REF][START_REF] Beverly | Primitives for active Internet topology mapping: Toward high-frequency characterization[END_REF].

Medina et al. [START_REF] Medina | Measuring interactions between transport protocols and middleboxes[END_REF] report one of the first detailed analysis of the interactions between transport protocols and middleboxes. They rely on active probing with tbit and contact various web servers to detect whether Explicit Congestion Notification (ECN), IP options, and TCP options can be safely used. The TCPExposure software developed by Honda et al. [START_REF] Honda | Is it still possible to extend TCP[END_REF] is closest to tracebox. It also uses specially crafted packets to test for middlebox interference. Wang et al. [START_REF] Wang | An untold story of middleboxes in cellular networks[END_REF] analyzed the impact of middleboxes in hundreds of cellular networks. This study revealed various types of packet modifications. More recently, Craven et al. [START_REF] Craven | Middlebox-cooperative TCP for a non endto-end Internet[END_REF] proposed TCP HICCUPS to reveal packet header manipulation to both endpoints of a TCP connection. HICCUPS works by hashing a packet header and by spreading the resulting hash into three fields (in case one is changed). Finally, Xu et al. [START_REF] Xu | Investigating transparent web proxies in cellular networks[END_REF] analyzed the behavior of proxies deployed by four major US cellular carriers. They looked at the HTTP traffic between their clients and their own server. They exhibited mostly application-level proxy features such as caching, HTTP redirection, image transcoding and connection persistence, and quantified their effectiveness.

These tools provide great results, but they are limited to specific paths as both ends of the path must be under control or must implement particular techniques in the TCP/IP stack and, except for Wang et al. and Xu et al., are not dedicated to mobile devices. On the contrary, TraceboxAndroid does not require any cooperation with the service and only the source must install TraceboxAndroid. It allows one to detect middleboxes on any path, i.e., between a source and any destination.

Conclusion

In this paper, we introduced TraceboxAndroid, a tracebox port under the Android system, allowing so the user to detect the presence of a middlebox that could be the cause of degraded performance on a path. We showed the extent of TraceboxAndroid capabilities for detection and location of middleboxes rewriting IP and TCP headers fields and TCP options as well as for AS path analysis and traceroute-like path displaying.

The main limitation of TraceboxAndroid is the impossibility to forge network and transport headers and read ICMP control messages in non-rooted environments. We need raw sockets to achieve this and their use is restricted to users that can grant the CAP_NET_RAW POSIX capability (i.e., super users). As a workaround, we chose to develop a proof-of-concept app for rooted devices only and call the TraceboxAndroid BusyBox implementation from the JAVA app as a super user, but this requirement is inappropriate for large-scale deployment because it involves a loss of warranty and risks of system instabilities, among others [START_REF] Kingo | Warranty disclaimer[END_REF]. Note that this limit has already been discussed in the literature [START_REF] Faggiani | On the feasibility of measurement the Internet through smartphone-based crowdsourcing[END_REF].

The dataset sample that we analyze in this paper is fairly limited and does not provide particular insight of middleboxes in mobile networks. However, we believe this dataset is enough to describe the potentialities of TraceboxAndroid.

In the near future, we would like to improve TraceboxAndroid. For instance, we would like to extend the Custom Probing mechanism to allow the user to select more IP fields, TCP fields, and TCP options to check and to choose the probe transport layer between TCP and UDP. We also plan to support additional TCP options, such as the TCP Authentication Option (TCP-AO) [START_REF] Touch | The TCP authentication option[END_REF] or the TCP Alternate Checksum Request [START_REF] Zweig | TCP alternate checksum options[END_REF]. Additionally, we would like to improve the user experience by displaying more information and statistics (RTTs, values of modified fields, crossed ASs, etc.) within the application itself.

Another interesting improvement would be to implement middlebox TCP option blocking inference. Mobile devices could send multiple probes with different TCP options combinations to infer middlebox blocking behavior and find if in-path middleboxes are forbidding the use of certain option. This would allow user to perform more complete on-demand connectivity tests and the research community would benefit from the compiled results dataset.

Fig. 1 .

 1 Fig. 1. Example of middlebox detection with tracebox

Figure 5 . 1 :

 51 Figure 5.1: Communication links used by di↵erent parts of the project

Fig. 2 .

 2 Fig. 2. General overview of the TraceboxAndroid architecture

Fig. 3 .

 3 Fig. 3. Front Office organization

  May, 2014 and September, 2014 TraceboxAndroid has been downloaded by 23 users from Belgium, Italy, USA, China, and Nigeria. Measurements performed by those users during this period reached a total of 1,756 probes sent. Participating mobile devices were connected to the Internet via WiFI or cellular data networks via different carriers (Mobistar, O2, Mobile Vikings, E-Plus, BASE, T-Mobile, Movistar, KPN) using different mobile technologies (HSPA, HSPAP, HSDPA, LTE, UMTS, and EDGE).

Fig. 4 .Fig. 5 .

 45 Fig. 4. Path lengths distribution

Fig. 6 .

 6 Fig. 6. Observed middlebox modification in IP and TCP headers

  ::Option MSS # 14 TCP::Option WS # 15 TCP::Option Timestamp # 16 TCP::Option SACK # 17 TCP::Option MPTCP (b) Legend

Fig. 7 .

 7 Fig. 7. Observed middlebox modification in TCP options

Table 1 .

 1 Observed Memory and CPU consumption.

	Case	Samsung Galaxy SII Arnova 10d G3
	Memory	10.8Mb	6.45Mb
	CPU (app)	< 1 %	< 1 %
	CPU (instant probe)	12.5 %	12.5%

http://www.androidtracebox.org

This work is funded by the European Commission funded mPlane ICT-318627 project.


Hassan Metwalley
email: metwalley@tlc.polito.it

Stefano Traverso
email: traverso@tlc.polito.it

Marco Mellia
email: mellia@tlc.polito.it

Stanislav Miskovic
email: stanislav_miskovic@symantec.com

Mario Baldi
email: mario_baldi@symantec.com

The Online Tracking Horde: a View from Passive Measurements

During the visit to any website, the average internaut may face scripts that upload personal information to so called online trackers, invisible third party services that collect information about users and profile them. This is no news, and many works in the past tried to measure the extensiveness of this phenomenon. All of them ran active measurement campaigns via crawlers. In this paper, we observe the phenomenon from a passive angle, to naturally factor the diversity of the Internet and of its users. We analyze a large dataset of passively collected traffic summaries to observe how pervasive online tracking is. We see more than 400 tracking services being contacted by unaware users, of which the top 100 are regularly reached by more than 50% of Internauts, with top three that are practically impossible to escape. Worse, more than 80% of users gets in touch the first tracker within 1 second after starting navigating. And we see a lot of websites that hosts hundreds of tracking services. Conversely, those popular web extensions that may improve personal protection, e.g., DoNotTrackMe, are actually installed by a handful of users (3.5%). The resulting picture witnesses how pervasive the phenomenon is, and calls for an increase of the sensibility of people, researchers and regulators toward privacy in the Internet.

Introduction

Internet is the revolution that changed our life, allowing us to be informed, buy goods, enjoy shows, play games, keep in touch with friends, and freely express our opinions to potentially very large audiences. People are more and more connected to the Internet, with mobile terminals allowing access to information from anywhere, anytime. Companies see the Internet as a means to stay in contact with their customers, to attract them, and to offer more and more personalized content. Not surprisingly, a large fraction of Internet businesses rely on online advertising, a market that keeps growing year by year, and that generated $42B revenue in 2013 according to the Interactive Advertising Bureau [START_REF]IAB internet[END_REF].

Online advertisement -ads for short -enables companies to design very targeted campaigns. The web offers the capability of reaching specific groups of users assembled with very fine granularity, leveraging knowledge of personal interests and taste This work was conducted under the Narus Fellow Research Program. of individuals. In order to collect such knowledge, companies track the users during their everyday online activity, constantly collecting information for marketing purposes (e.g., products browsed on a shopping website, online newspapers usually read, movies liked). This information is used to profile a user in order to deliver tailored ads, recommend movies to watch, or goods to buy.

Online trackers play a key role in this ecosystem as third-party services that "shadow" users during their browsing activity. Trackers rely on host of solutions to identify a user, ranging from storing a cookie on the user browser or device to exotic tracking techniques that fingerprint users across several web sites [START_REF] Acar | The Web Never Forgets: Persistent Tracking Mechanisms in the Wild[END_REF][START_REF] Krishnamurthy | Privacy leakage vs. Protection measures: the growing disconnect[END_REF][START_REF] Yen | Host Fingerprinting and Tracking on the Web: Privacy and Security Implications[END_REF]. The tracker business models also vary greatly. Some offer customized ads, while others sells user information to ads companies, acting as data brokers. Google's DoubleClick and Yahoo's YieldManager are notable tracker examples. However, the full list of companies that build their business around information collection includes several hundreds.

The mechanisms associated to tracking users can be beneficial for both companies and consumers. But they also raise many privacy concerns among the regulators and researchers. Ultimately, the consciousness of the people about their privacy being violated in the Internet is growing day by day.

Several works in the literature study the latest advances in online tracking, unveiling new and more subtle mechanisms [START_REF] Acar | The Web Never Forgets: Persistent Tracking Mechanisms in the Wild[END_REF][START_REF] Gomer | Network analysis of third party tracking: User exposure to tracking cookies through search[END_REF][START_REF] Roesner | Detecting and Defending Against Third-party Tracking on the Web[END_REF][START_REF] Vallina-Rodriguez | Breaking for Commercials: Characterizing Mobile Advertising[END_REF], and proposing countermeasures to be protect users'privacy, typically in the form of browser plugins [START_REF] Ghostery | [END_REF][START_REF]DoNotTrackMe[END_REF][START_REF] Badger | [END_REF][START_REF] Adblockplus | [END_REF]6]. Some works studied the pervasiveness of online tracking by running active measurement campaigns and by crawling the web [START_REF] Krishnamurthy | Privacy Diffusion on the Web: A Longitudinal Perspective[END_REF][START_REF] Barford | Adscape: Harvesting and Analyzing Online Display Ads[END_REF][START_REF] Falahrastegar | The Rise of Panopticons: Examining Region-Specific Third-Party Web Tracking[END_REF]. This paper falls in this second class: we aim at quantifying the pervasiveness and extensiveness of online tracking. Differently to any previous work, we are the first, to the best of our knowledge, to leverage passive measurements, which have the major advantage to naturally factor the users into the picture. We address questions as how many tracking services an internaut would normally face during her activity? How different is the picture from past years, or from different vantage points? How invasive are tracking services?

For our study, we rely on an extensive dataset composed by (anonymized) traces we collect by passively observing normal users from four different probes installed in two ISPs in two different countries. We use this data to pinpoint the traffic exchanged with a list of online trackers that we manually built from various sources. We then collect statistics to characterize such traffic.

Results confirm what is known from the literature: online tracking is ubiquitous. We count more than 400 active online tracking services, with 100 of them being regularly contacted by more than 50% of users, and the most pervasive ones that are impossible to avoid. Results confirm observations shown in other works based on active campaigns [START_REF] Roesner | Detecting and Defending Against Third-party Tracking on the Web[END_REF][START_REF] Falahrastegar | The Rise of Panopticons: Examining Region-Specific Third-Party Web Tracking[END_REF], but our passive approach naturally factors the user browsing behavior, and allows us to obtain a very detailed and fine-grained picture that quantifies the pervasiveness of tracking services in real life. For instance, 77% of users face the first tracker just 1 s after starting their online activity. We observe websites that nowadays embed more than 50-100 third-party trackers, attracted by the chance to monetize visits, and in practice contributing to collect personal information. Notably, most of these services are not popular to enter in the top list of websites (and thus have never being considered by active studies). Yet, those are popular enough to collect a sizable number of users. Our unique vantage point allows us to measure things that active campaigns can not gauge. We are the first at quantifying the popularity of privacy-enhancer browser plugins. Surprisingly this is limited, with DoNotTrackMe installed by a mere 3.5% of users. This testifies the small consciousness and sensibility of internauts versus their privacy. Similarly, by splitting statistics by type of user device, we highlight how Android devices are more prone to interact with tracking services than iOS devices and regular Windows PCs. Finally, our measurements highlight another phenomenon: the increase adoption of HTTPS as the means to collect data. This exacerbate the tension on the need to protect users privacy, since for instance this mines the possibility to develop in-network solutions to control and limit online tracking services.

We hope the picture we draw can contribute to increase the sensibility of people, researchers and regulators towards privacy in the Internet. We do not believe in an "arms race" as a possible solution, but rather in a solution in which people is offered the means to take informed choices.

The remainder of the paper is structured as follows. Sec. 2 introduces the related work, Sec. 3 details the dataset we employ in this study, Sec. 4 presents the results, and, finally, Sec. 5 concludes the paper.

Related Work

Our work is related to recent literature in the area of web measurement driven studies about web tracking and online advertisement. We can divide most of the notable works in this area in three branches. The first branch is mostly oriented to understand which identifiers and techniques online tracking services exploit to record users' browsing activities. Yen et al. [START_REF] Yen | Host Fingerprinting and Tracking on the Web: Privacy and Security Implications[END_REF] examine the common identifiers trackers can leverage to identifying users, and the authors of [START_REF] Roesner | Detecting and Defending Against Third-party Tracking on the Web[END_REF] and [START_REF] Chaabane | Big Friend is Watching You: Analyzing Online Social Networks Tracking Capabilities[END_REF] describe the techniques third party trackers and online social networks use to monitor the activity of their users. The second branch is mostly oriented to understand the leakage of personal information due to web trackers. For instance, Balachander et al. [START_REF] Krishnamurthy | Privacy Diffusion on the Web: A Longitudinal Perspective[END_REF] studies privacy leakage and evolution of third party trackers over four years from 2005 to 2008 using DNS logs. Another notable example is [START_REF] Krishnamurthy | Privacy leakage vs. Protection measures: the growing disconnect[END_REF], which analyzes how popular websites share users' private information with tracking services, remarking that this trend is worryingly diffused. The last branch focuses about the analysis of the mechanisms which drive online advertisement. Vallina et al. [START_REF] Vallina-Rodriguez | Breaking for Commercials: Characterizing Mobile Advertising[END_REF] specifically examine ads in mobile terminals. Our aim is different as we address the problem of understanding how pervasive tracking services are by leveraging a large set of passive measurements. And to the best of our knowledge, we are the first to perform this analysis following a passive approach.

Our study shares some common points with other works. We discuss in the following the differences which distinguish our work. Barford et al. [START_REF] Barford | Adscape: Harvesting and Analyzing Online Display Ads[END_REF] build their analysis around a dataset they collect thanks to a web crawler they develop. Web crawling lets the authors infer detailed information about the online ads which populate webpages. They specifically focus on the analysis of online ads, while our study addresses online tracking services in general, and from users' perspective.

The work which mostly approaches this study is Gomer et al. [START_REF] Gomer | Network analysis of third party tracking: User exposure to tracking cookies through search[END_REF], where authors propose a methodology to identify tracking services from the analysis of pages returned Table 1. The sets of traces we consider in this study.

by search queries. Specifically, using Google, Bing and Baidu, they run popular queries (extracted from the 2005 KDD dataset). They then crawl the top 10 returned pages, and check for the presence of trackers embedded in each page.

Similarly, [START_REF] Castelluccia | Data Harvesting 2.0: from the Visible to the Invisible Web[END_REF] and [START_REF] Falahrastegar | The Rise of Panopticons: Examining Region-Specific Third-Party Web Tracking[END_REF] offer a global point of view of this phenomenon. In first case, Castelluccia et al. [START_REF] Castelluccia | Data Harvesting 2.0: from the Visible to the Invisible Web[END_REF] analyze the provenance of most important third party tracking services using two popular browser extensions, AdBlock Plus and Ghostery, for the geographical classification. In second case, Falahrastegar et al. [START_REF] Falahrastegar | The Rise of Panopticons: Examining Region-Specific Third-Party Web Tracking[END_REF] crawl the top websites in Alexa rank for different countries, and measure the per-country pervasiveness of third party trackers. Despite our study share the same aim, as said, we rely on passive traces. This allows us to naturally factor the interactions with third-party trackers and real internauts during their daily activities, and check the impact of multiple devices, or browsers, or even malware eventually being installed on end-users' terminals.

Finally, we are the first to analyze in a real scenario the adoption of those do-nottracking extensions as AdBlock Plus or DoNotTrackMe which are expected to protect users' privacy. Thanks to our vantage point, we show the breadth of the most invasive trackers, considering both the services hosting them, and the users' chances to contact them.

Dataset

In this work, we employ four different passive probes running Tstat3 that we installed in Points-of-Presences (PoPs) in the operational networks of two different ISPs (ISP1 and ISP2) in Europe. Tstat observes all packets flowing on the links connecting the PoP to the ISP backbone network. It rebuilds each TCP flow, tracks it, and at the end of the flow, logs more than 100 detailed statistics in a simple text format. For instance, for each TCP flow, Tstat logs the anonymized client IP address, the server IP address, the application (L7) protocol type, L7-bytes sent and received, etc. Tstat also implements DN-Hunter, an advanced mechanism that allows to annotate each TCP flow with the server hostname the client resolved via DNS before actually contacting the server IP address [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF]. For TCP connections carrying HTTP and HTTPS data, DN-Hunter has been proved to unveil the service being contacted, e.g., www.acme.com or mail.acme.com. For HTTP traffic, Tstat produces a separate log which details most relevant HTTP fields: the HTTP method (GET, POST, etc.), the server hostname, the URL path, the referer, the client user-agent, etc. 4We have been collecting TCP and HTTP logs since May 2012. In this work, we focus on a subset of the data. Specifically, we consider three probes (ISP1-Vp1, ISP1-Vp2 and ISP1-Vp3) that are located in PoPs of the same ISP (ISP1), in two different cities of the same country. A fourth probe (ISP2-Vp1) is installed in a different ISP (ISP2), in a second country. Tab. 1 describes, for each trace, the name used throughout the paper, the location, the period, the number of households (identified by the IP address of the access gateway, see next section), and the total number of different services, i.e., server hostnames. Tab. 1(a) refers to traces which are one-day long, from the same probe, collected on the second Wednesday of May 2012, 2013 and 2014. We complement them with three traces we collected in the same day (February 26th, 2014), but from three different PoPs and countries. Tab. 1(b) refers to ten-day long traces that we collected from three different PoPs of ISP1, during the same period in October 2014.

Among the details, Tab. 1 shows that the dataset we use covers several thousands of regular users, which browse some millions of hostnames. Results we present are as such generic, even if specific to the country where the vantage points are located.

Identifying Active Users and Number of Connected Devices

Notice that the client IP address field in our logs refer to the access gateway (ADSL/FTTH modem) customers are given by the ISP. As such, the IP address can be considered as an identifier of the household, which may hide several actual devices and users that connect to the Internet using NAT at the access gateway. This includes possible households in which no actual user is present, but in which some device generates some traffic. In particular, ISP1 offers native VoIP communications. The access gateway acts also as VoIP gateway, thus we expect some households to appear as "active" (IP address is used) even if no terminal is present (we observe VoIP data only).

Fig. 1(a) shows the number of total HTTP and HTTPS flows per each IP address, sorted for increasing number. Notice the log scale on y-axis. Plot refers to trace ISP1-Vp1-1d-05/14. It shows the bias induced in ISP1 by the presence of VoIP gateways at the modem. They indeed generate some signalling HTTP and HTTPS traffic to report VoIP usage statistics to the operator. The presence of the sharp knee in the figure suggests that a simple threshold based filter is sufficient to identify "active" households. 5 In the remainder of the paper, we take a conservative choice, by considering active only those IP addresses for which we see at least one HTTPS flow, and at least 100 HTTP or HTTPS total flows for the 1-day long dataset (1000 flows for the 10-day long traces). This filters out those sources of traffic we are not interested in (e.g., smart TVs, VoIP gateways, or pure P2P clients). Most active households reach 100, 000 flows per day.

To quantify the presence of multiple clients that are hidden behind the NAT at the ADSL router, Fig. 1 a given active IP address. We consider only user-agents associated to actual browsers, for PC and mobile terminals. We leverage the User-agents 0.3.1 Python library for this. 6 Results show that only 20% of households have only one terminal, with 75% of them showing between 2 to 10 different user-agents. Manually checking this, we observe a lot of smartphones and tablets, with some cases showing multiple browsers being normally used. Surprisingly, in few cases we see more than 10 user-agents. A manual check shows the presence of suspicious behavior with possibly a malware generating lots of HTTP requests toward few IP addresses serving advertisements. HTTP requests contain a rotating set of legitimate browsers user-agents. We suspect this to be related to some click fraud activity, i.e., a malicious user artificially generating clicks on ads servers by forging user-agents. We noted the presence of these outliers, and check their presence is not affecting our statistics in the remainder of the paper.

Identifying Online Tracking Services

We build a list of online tracking services by merging together data we obtain from different sources. First, inspired by the approach used by the authors of [START_REF] Falahrastegar | The Rise of Panopticons: Examining Region-Specific Third-Party Web Tracking[END_REF], we instrument a browser to visit the top 500 websites of the global Alexa rank. For each page, we visit it and use the Ghostery plugin [START_REF] Ghostery | [END_REF] to pinpoint the presence of trackers. Given then the hostname of the tracker server, we extract only the second-level domain name to reduce the list. For instance from cnt2.acmetracksyou.com and srv1.acmetracksyou.com we consider acmetracksyou only. We repeat the procedure using the top 500 websites in the general Alexa rank, and of countries where ISP1 and ISP2 are located. By merging the resulting lists we obtain more than 350 distinct online tracker services. Then, we complement this list with the one obtained from the developers of Abine7 , and with some specific trackers we manually identify. This list also includes hostnames referring to trackers specifically tailored to track mobile clients. The final list consists of 443 distinct online tracking services. The list includes only services that we classify as third party sites that collect users' information, and eventually serve advertisements. This includes tracking services that profile users explicitly (e.g., Doubleclick) or that track users when on a website (e.g., Google Analytics). We do not consider social network buttons, plugins, and active code.

In the remainder of the paper, we rely on this list to pinpoint connections that clients establish with tracker servers. When analyzing the TCP logs, we use the DN-Hunter hostname to identify traffic to trackers. For HTTP logs instead we use the server hostname in the HTTP request.

Results

Penetration of Online Tracking Services

We start our analysis by measuring the "penetration" of each online tracker that appears in our list. We consider the trace ISP1-Vp1-10d-10/14. Fig. 2 reports the percentage of users that contacted at least one time a given tracker with respect to users that we find active considering the entire 10 days. The results are shocking: the top online tracking services -DoubleClick, Google Analytics, and Google Syndication -track 98.8%, 98.7% and 97.4% of users, i.e., as soon as a user goes online, sooner or later she/he will contact one of Google tracking services. While they might be known to some users, the list of trackers includes a vast majority of players that are mostly unknown even to experts internauts. Fig. 2 reports some of the names. Observe the solid blue curve which refer to the ten-day long period. More than 50% of users contacts 120 distinct trackers, with 429 out of 443 trackers that have being contacted by at least one user. When considering shorter periods of time, e.g., one, two, five days (red, green and black curves), the number of users seen by trackers decreases. Yet, the top 20 trackers can observe more than 35% of internauts active during the first day of the trace.

Next, we compare penetration of trackers over years. Fig. 3 shows the results. This time we are considering one-day long traces during October 2012, 2013 and 2014, and we focus on the top 23 trackers. Penetration is higher in this case as we compute it over the active population of a single day. Top trackers show marginal changes over year, reflecting the fact that they have saturated the coverage. Going down in the list, we see that most of trackers shows an increase in the penetration, with only few exceptions. Some new players shows up, i.e., ads.yahoo. No service went out of business (or disappeared). We next compare the penetration from different vantage points. Fig. 4 show results considering the top-30 most popular trackers seen in the merged list of ISP1 and ISP2. Again, one-day long traces (in February 2014) are considered. Two observation holds: ISP1-Vp1 and ISP1-Vp2 show practically the same results. Despite being in two different cities, the population interest and habits is very similar, being in the same country. Conversely, comparing ISP1 and ISP2 results, we observe a very different penetration for some trackers, which reflects a localized service. This confirms the finding in [START_REF] Falahrastegar | The Rise of Panopticons: Examining Region-Specific Third-Party Web Tracking[END_REF] which highlighted the different coverage of online tracking services. For instance, Google tracking services present a higher penetration in Country 2 than in Country 1, while some trackers do not cover ISP2 market, e.g., imrworldwide, and viceversa, e.g., adocean.

To gauge the amount of data collect, we compute the distribution of the fraction of TCP flows to trackers (not reported for the sake of brevity). We observe that 60% of users exchange from 10% to 30% of flows with trackers. We also see few cases in which more than 95% of flows are sent to trackers. Investigating, we observe i) click fraud activity of some users infected by some ad-malware, and ii) some mobile application that keeps downloading tens of ad-banners per minute, for hours. Both are likely illicit behaviors caused by malicious attackers that abuse of unaware users to game the ads market.

At last, we measure to which extent the top trackers rely on encrypted channels, i.e., HTTPS, to collect information about the users. To this end, we measure how many TCP flows the users exchange with the trackers, and how many of these flows are HTTPS. We consider again the one-day long traces we collected in 2012, 2013 and 2014. Fig. 5 reports the percentages of connections carrying HTTPS traffic for the top 23 most popular trackers. We observe some trackers do use encryption to collect users' information: in 2014, google-analytics (39%), adform (33%), ads.yahoo (31%) and mookie1 (36%). In general almost all the top 23 tracker has consistently increased the usage of HTTPS over the last three years. This is also mandated by the general increase of HTTPS-enabled websites that enforce HTTPS for all third party content too.

Popularity of Privacy Enhancer Plugins

We now investigate the popularity of plugins that can enhance and customize the browsing experience. We focus on those well-know plugins which i) block Javascript code commonly used by advertisers (NoScript), ii) warn about the presence of online tracking service (Ghostery, WordOfTrust, DoNotTrackMe), and iii) block advertisement traffic (AdBlock, AdBlockPlus). We count how many users run these plugins. For each plugin, we perform some active experiments to understand which hostnames it has to contact to check if updates are available 8 We then compute the fraction of users that contact such hostnames in our traces. We report in Fig. 6 the shares of households that have installed a given plugin in at least one device, together with the percentage of those which did not install any plugin in any device. We compute these statistics for all our ten-day long traces. As shown, the share of users installing a plugin is in general rather small, and it seems that users are more interested in blocking the ads they encounter while browsing the web, rather than trackers. Indeed the popularity of AdBlockPlus is between 10% to 18%. Less than 3.5% of users run DoNotTrackMe. Moreover, we observe that more than 80% of the users do not install any of the considered plugins, thus offering the trackers the capability of easily following their surfing activity.

Trackers Penetration among Services

Next, we investigate the penetration of the online trackers among different services (e.g., websites) that users contact during their everyday online activity. To this end, we consider the HTTP trace. From each URL where the hostname is a given tracker, we check the Referer field to observe which service was embedding it. As before, we consider only the second level domain name as the name of the service. We count more than 25,000 services that host third party trackers. For each of them, we count how many users contacted them, i.e., how popular they are, and how many and which trackers they embed. In the scatter plot in Fig. 7, each black dot represents a service; the x-axis (in log scale) reports the number of distinct users accessing it; the y-axis reports the number of embedded trackers. Data refers to ISP1-Vp1-1d-5/14. The scenario is rather heterogeneous, with many services embedding several tens of tracking services. We observe both unpopular services hosting many trackers -e.g., the few services contacted by one or two users only, but hosting more than 50 trackers -and popular services hosting a few trackers -e.g., the rightmost bottom corner of the plot. In general the number of trackers per service tends to increase with the popularity of the service.

When checking the results we noticed that www.google.com, the most popular service, apparently embeds 222 trackers. By manually digging in our traces we observe that such large number of trackers is due to a bug in the google-search widget installed in version 4 of Android devices which affect our (and possible other datasets). Indeed, when an Android user performs a search query using the widget, and then visit a webpage by tapping on a link in the returned page, the Android browser keeps using http://www.google.com as Referer field for all objects that actually refer to the visited page. Besides affecting our results, this bug can possibly also poison the counters that trackers use to share their revenues with services.

To complement the above observations, we analyze tracker's "breadth", i.e., the number of services that embed each tracker. We report the results in Fig. 8. The x-axis reports the rank of the 150 most popular trackers in our lists, and the y-axis reports all the services present in ISP1-Vp1-1d-05/14. Each dot represents the association of tracker x with the service y. We sort the services by considering their popularity among the users, from the most popular (top) to the least popular (bottom). First, most popular services embeds a large variety of trackers (observe the dense area in the top part of the plot). This confirms the trend of Fig. 7. Second, the dense vertical area in the leftmost part of the plot indicates that trackers with the highest penetration are also associated to many services (and vice-versa). To ease the visualization, the red solid curve shows the number of services associated to each tracker in the rank. The curve is very steep, with less than 10 trackers are associated to more than 1000 services. In particular, the three trackers with the largest service coverage belong to Google: google-analytics, doubleclick and googlesyndication, embedded by 17, 814, 8, 176, and 5, 921 services, corresponding to 71%, 32%, and 24% of the total number of active services, respectively. The first tracker not belonging to Google in the rank, addthis takes the fourth place with 3, 080 (12%) covered services. Despite this, it sees more than 50% of population (see Fig. 3). This reflect a market dominated by Google, in which a lot of other small players are present. The ones that are hosted in popular domains are able to still track a lot of users.

Time to Be Tracked

In this section, we investigate how invasive trackers are at getting in touch with users. We measure how much time a user spends online before encountering the first tracker. Let T 0 be the time of the first HTTP or HTTPS TCP flow generated by a user, and let T 1 be the time of the first TCP flow to a tracker. We measure the Time-To-Tracker as T T T = T 1 -T 0. For this analysis, we leverage the TCP trace in ISP1-Vp1-1d-5/14. We consider only those households for which we know just PC-based terminals are used, i.e., only one single PC-based user-agent is seen. Results are astonishing: T T T is smaller than 1 s in 77% of PC users, i.e., as soon as a users goes online, she/he hits the first tracker in less than a second. Even worse, 100% of users have a T T T smaller than 100 s. When considering all households, we observe even shorter T T T .

To give the intuition behind this, we detail the number of HTTP connections needed to hit a tracker using the HTTP traces. We split the dataset according to the user-agent field in three categories: PC-based, Android-based and iOS-based. For each category, we compute the distribution of the number of HTTP requests a user generates before contacting a tracker. Fig. 9 plots the results. Independently on the device, in about 10% of the cases, the first HTTP transaction of the day goes to a tracker 9 , and within the first 100 (1000) requests in about 60% (97%) of the cases. Interestingly, users with an Android device contact a tracker earlier on than users with a PC or an iOS-based device.

Conclusions

Motivated by the privacy concerns that online tracking services have recently raised, we presented in this paper a passive characterization of this phenomenon. We leveraged a large dataset of traffic summaries we collected from ISPs located in two different countries to passively quantify the pervasiveness and the intrusiveness of online tracking services in our life. To the best of our knowledge, we are the first to passively analyze the behavior of trackers in a real scenario, where the users are naturally factored.

The results presented in this paper are boggling. We observed that top 100 trackers collect information from 50% of the users on a regular basis. Plus, some of these being able of tracking 98% of the Internauts. They are embedded into more than 70% of websites, including the most popular ones, but also those that are visited by few users. Similarly, trackers' intrusiviness is astonishing, with 77% of users that contacts a tracker within 1 second after she/he starts browsing the web. We also observe that trackers are increasingly embracing HTTPS to collect data. While this is possibly driven by the increase of HTTPS usage, this increases the warning level since is becomes more and more complicated to control and limit the information they can collect.

Our results show that the consciousness of the users about their activity being monitored by trackers is limited. Indeed, only a small fraction of users rely on privacyenhancer browser plugins as DoNotTrackMe, and they appear to be more interested in ad-blocking extensions such as AdBlockPlus.

We believe that the information contained in this paper can contribute to increase the consciousness of people about the fragility of their privacy in modern web. We hope that our findings may be of stimulus for regulators, researchers and practitioners who aim at designing solutions to let the users take control of the information they exchange with the Internet.

  Services ISP1-Vp1-1d-05/12 ISP1-Vp1 09/05/2012 11660 200320 ISP1-Vp1-1d-05/13 ISP1-Vp1 08/05/2013 12218 239230 ISP1-Vp1-1d-05/14 ISP1-Vp1 07/05/2014 10458 238617 ISP1-Vp1-1d-02/14 ISP1-Vp1 26/02/2014 11027 247797 ISP1-Vp2-1d-02/14 ISP1-Vp2 26/02/2014 11927 297488 ISP2-Vp1-1d-02/14 ISP2-Vp1 26/02/2014 4911 113648 (a) One-day long traces. Trace Probe Period IP addr Services ISP1-Vp1-10d-10/14 ISP1-Vp1 13-23/10/2014 13408 1046339 ISP1-Vp2-10d-10/14 ISP1-Vp2 13-23/10/2014 11149 1306612 ISP1-Vp3-10d-10/14 ISP1-Vp3 13-23/10/2014 1321 415550 (b) Ten-day long traces.

5

 5 (b) shows the CDF of the number of different user-agents seen for Number of flows TCP -HTTP, HTTPS flows TCP -HTTPS flows (a) Number of flows per household. Trace ISP1-Vp1-1d-05/14.

14 Fig. 1 .

 141 Fig. 1. Per-household statistics.

Fig. 2 .

 2 Fig. 2. Penetration of online trackers in ISP1-Vp1-10d-10/14.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Penetration of online trackers compared for different years in ISP1-Vp1-1d-05/*.

Fig. 5 .

 5 Fig. 5. Percentages of HTTPS transactions users establish with third party tracking services for different years in ISP1-Vp1-1d-02/1*.

Fig. 6 .

 6 Fig. 6. Percentage of households installing the most popular do-not-tracking plugins. Results from traces ISP1-Vp*-10d-10/14.

Fig. 7 .

 7 Fig. 7. Scatter plot of the number of users contacting a service, and the number of trackers embedded by the same service. ISP1-Vp1-1d-5/14.

Fig. 8 .

 8 Fig. 8. Trackers embedded by the services users visited (black dots), and the number of services covered by each tracker (red curve). trace ISP1-Vp1-1d-5/14.

Fig. 9 .

 9 Fig. 9. CDF of number of HTTP requests before contacting a tracker. Trace ISP1-Vp1-1d-5/14.

tstat.polito.it

The traffic logs Tstat generates do not contain information which may offend ISP users privacy. Indeed, Tstat processes IP packets (and their payload) in real time and generates transport-and

HTTP-level logs in which we take care of obfuscating any privacy sensitive information (e.g., IP addresses are anonymised using irreversible hashing functions, all URLs are truncated, etc.). Second, Tstat has no visibility on encrypted traffic (HTTPS), where the sensitive information concentrates. Furthermore, we report that our traffic monitoring activity is approved by the Security Office of the ISP in which we deploy our probes.[START_REF] Adblockplus | [END_REF] We use the term "household" and "user" interchangeably in the paper.

https://pypi.python.org/pypi/user-agents

https://www.abine.com/

We observe that each plugin contacts its update server with a fairly large frequency (e.g., at any browser bootstrap or once a day) with respect to the considered observation window.

The reason why the first HTTP request goes to a tracker is due to the user browsing on HTTPS before moving to HTTP, thus becoming visible for this measure.


Tatsuya Mori

Takeru Inoue

Akihiro Shimoda

Kazumichi Sato

Keisuke Ishibashi

Shigeki Goto

SFMap: Inferring Services over Encrypted Web Flows using Dynamical Domain Name Graphs

Most modern Internet services are carried over the web. A significant amount of web transactions is now encrypted and the transition to encryption has made it difficult for network operators to understand traffic mix. The goal of this study is to enable network operators to infer hostnames within HTTPS traffic because hostname information is useful to understand the breakdown of encrypted web traffic. The proposed approach correlates HTTPS flows and DNS queries/responses. Although this approach may appear trivial, recent deployment and implementation of DNS ecosystems have made it a challenging research problem; i.e., canonical name tricks used by CDNs, the dynamic and diverse nature of DNS TTL settings, and incomplete measurements due to the existence of various caching mechanisms. To tackle these challenges, we introduce domain name graph (DNG), which is a formal expression that characterizes the highly dynamic and diverse nature of DNS mechanisms. Furthermore, we have developed a framework called Service-Flow map (SFMap) that works on top of the DNG. SFMap statistically estimates the hostname of an HTTPS server, given a pair of client and server IP addresses. We evaluate the performance of SFMap through extensive analysis using real packet traces collected from two locations with different scales. We demonstrate that SFMap establishes good estimation accuracies and outperforms a state-of-the-art approach. 4 We note that server name indication (SNI) extention of TLS can be used to obtain hostname of HTTPS server. However, there are many client/server implementations that do not adopt SNI. In fact, in our dataset, roughly half of HTTPS clients did not use the SNI extention.

Introduction

Background:

Monitoring and understanding traffic mix is crucial for network operators. Port number conventions and deep packet inspection (DPI) are widely used to understand the breakdown of traffic mix. However, these techniques have become less effective for the following reasons. First, the majority of modern services, such as social networking service, video, and messaging services, are all performed over web traffic [START_REF] Sandvine | Global internet phenomena report: 1h[END_REF], and port number information is too coarse-grained to distinguish such services from each other. Second, the encryption of communication channels has disabled inspection of HTTP headers, which include useful information such as uniform resource identifiers (URIs). Modern protocols for accelerating the web such as SPDY and Websocket employ mandatory encryption of HTTP with SSL/TLS (secure socket layer/transport layer security), i.e., HTTPS. Naylor et al. [START_REF] Naylor | The Cost of the "S" in HTTP[END_REF] recently reported that fraction of HTTPS traffic volume measured at a large-scale ISP has significantly increased over these 2+ years (from April 2012 to July 2014). They also found that their meausrement study suggests that cost of deploying HTTPS is decreasing. Hence, the increasing adoption of HTTPS brings new research challenges to traffic classification problems [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF][START_REF] Korczynski | Markov chain fingerprinting to classify encrypted traffic[END_REF] 4 .

Goal and Challenges:

Based on the aforementioned information, this work aims to enable network operators to infer the hostnames of HTTPS traffic. Hostname information is useful for network operators to understand what types of services are carried over HTTPS flows. Although the IP address property of an HTTPS server may reveal that the server is used by a particular company such as Google, this information often fails to provide us with information about the services that are used over the flow, such as web searches, blogs, and videos. Such services are associated with distinct hostnames such as www. google.com, www.blogspot.com, and www.youtube.com. Bermudez et al. [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF] revealed that simple reverse DNS lookup does not return accurate domain information used by HTTPS servers. Thus, to understand the traffic mix of HTTPS flows, we need to infer server hostnames.

The main idea of our approach is to correlate HTTPS flows and DNS queries/responses. The basic assumption is that prior to requesting an HTTPS flow, a web application should resolve the IP address of the HTTPS server by querying a DNS query. Therefore, by monitoring prior DNS queries/responses, we can estimate the hostname that is associated with IP address of the HTTPS server. Although this approach might look trivial, there are three practical challenges. (Challenge 1) Canonical name (CNAME) tricks used by CDNs First, modern CDN providers leverage CNAME tricks to accelerate the efficiency of content delivery [START_REF] Su | Drafting Behind Akamai (Travelocity-based Detouring)[END_REF]. Figure 1 shows an example of a CNAME chain used by a CDN provider. Here, assume that we know that the IP address of an observed HTTPS server is s1 = 23.2.132.181. Now, our task is to associate s1 with the original hostname, n1 = www.ieee.org. However, as is shown in Fig. 1, n1 is not directly resolved to s1 due to the existence of the CNAME chain. Using this chain structure, a CDN provider can provide the optimal server IP address s1 to serve the content of n1 to client c1. Thus, to associate s1 and n1, we need to keep track of the CNAME chain, which exhibits dynamic and complex behavior as we shall see soon.

(Challenge 2) Incomplete measurements

A DNS record can be cached by several mechanisms such as local DNS resolvers, DNS caching within operating systems, and DNS caching within applications such as web browsers. The implementations of these caching mechanisms are diverse. Some recent implementations used in web browsers store DNS records aggressively to improve response time, thereby ignoring DNS TTL settings [START_REF] Callahan | On Modern DNS Behavior and Properties[END_REF]. Even though such implementations violate the rule of DNS TTL, they can work because even if a selected server IP address is no longer an optimal one, the server IP address generally continues to be valid. Thus, due to the standard and illicit caching mechanisms, a DNS query, which should have appeared prior to an HTTP request, is often invisible. The absence of DNS queries suggests that we require estimation techniques to recover incomplete measurements. (Challenge 3) Dynamicity, diversity, and ambiguity Every hostname used in DNS is assigned a time-to-live (TTL), which defines the lifetime of the hostname within a stub DNS resolver. If the hostname is not queried again before the TTL has expired, the DNS record of the hostname will be removed from a stub DNS resolver. In general, the hostnames in a CNAME chain have different TTL values. Figure 2 presents an example of cumulative distributive function (CDF) of TTL values for hostnames that are resolved to IP addresses (A record) and hostnames that are resolved to CNAMEs (CNAME record). Note that the data was taken from a mid-sized production network, and the characteristics of CDF were the same for other dataset. The graph clearly shows that A record hostnames have shorter TTLs than CNAME hostnames. For example, more than 50% of A record hostnames have TTL values that are less than 60 seconds. This indicates that the association between hostnames and IP addresses is highly dynamic. These hostnames have shorter TTLs because CDN providers tend to control traffic at a fine granularity [START_REF] Callahan | On Modern DNS Behavior and Properties[END_REF].

The diversity of TTL values and DNS caching mechanisms leads to ambiguity of CNAME association behavior. We illustrate an actual sample in Fig. 3, which presents DNS resolutions for a client, c1. The first observation generates the relationship be-tween s1 and n1 for client c1. The second observation generates the relationship between s2 and n2 for client c1. Now, assume an estimation problem. If we observe the pair (c1, s1), which hostname should it be associated with? If we simply keep the relationships shown above, the answer is n1. However, due to the existence of intermediate CNAME node m1, the actual answer is n2 because m1 is now associated with s2 by a query of n2, and n1 is associated with m1 due to a caching mechanism. Note that this behavior depends on the implementation of the stub DNS resolver used by the client c1. If the implementation ignores intermediate CNAME nodes, the answer could be n1. Thus, there is an intrinsic ambiguity in CNAME associations.

Contributions:

In this work, we present a novel methodology that aims to infer the hostnames of HTTPS flows, given the three research challenges shown above. The key contributions of this work are summarized as follows.

-We present domain name graph (DNG), which is a formal expression that can keep track of CNAME chains (Challenge 1) and characterize the dynamic and diverse nature of DNS mechanisms and deployments (Challenge 3). -We develop a framework called Service-Flow map (SFMap) that works on top of the DNG. SFMap estimates the hostname of an HTTPS server given a pair of client and server IP addresses. It can statistically estimate the hostname even when associating DNS queries are unobserved due to caching mechanisms, etc. (Challenge 2). -Through extensive analysis using real packet traces, we validate the performance of SFMap in terms of accuracy and resource consumption.

The remainder of this paper is organized as follows. Section 2 summarizes the related work. Section 3 describes the proposed SFMap framework in detail. We evaluate the performance of SFMap in Section 4. Section 5 discusses the limitations of SFMap and future research directions. We conclude our work in Section 6.

Related work

Many studies have examined the Internet traffic classification problem. Ref. [START_REF]Internet traffic classification[END_REF] lists 68 studies on the topic. Here, we focus our attention on the studies that make use of DNS information to the traffic classification problem [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF][START_REF] Mori | Characterizing Traffic Flows Originating from Large-scale Video Sharing Services[END_REF][START_REF] Plonka | Flexible Traffic and Host Profiling via DNS Rendezvous[END_REF]. Mori et al. [START_REF] Mori | Characterizing Traffic Flows Originating from Large-scale Video Sharing Services[END_REF] proposed a method to identify traffic originating from large-scale video-sharing services such as YouTube. The key idea was to extract the rules of IP address numbering and naming conventions of fully qualified domain names (FQDNs) used for the services. Although their approach may work for a limited scope, it cannot be used to solve more generic web traffic classification problems. Plonka et al. [START_REF] Plonka | Flexible Traffic and Host Profiling via DNS Rendezvous[END_REF] presented a traffic classification method that uses DNS traffic. They developed a method that stores per client DNS rendezvous state information in a tree-like data structure. Although their results demonstrated that the DNS rendezvous-based method performs well, even for encrypted traffic, their goal was different from ours because they assumed that DNS traffic implies the ground truth. In contrast, our goal is to estimate the hostnames of HTTPS traffic from the observations of DNS traffic. Bermudez et al. [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF] developed a framework called DN-Hunter, which aims to classify traffic flows using DNS traffic. DN-Hunter uses a FIFO (first-in first-out) circular list to store the relationships among FQDN information and client-server pairs. Since the scope of DN-Hunter is mostly similar to ours, this work compares the performance of SFMap with DN-Hunter.

SFMap framework

This section describes SFMap in detail. Section 3.1 presents the overview of the SFMap framework. Section 3.2 describes DNG, which is a key component of the SFMap framework. Section 3.3 details how SFMap estimates hostnames. Lastly, Section 3.4 explains how SFMap updates DNG and statistics that are used for the estimation.

Overview

The goal of SFMap is to infer a hostname n of an HTTPS flow by associating preceding DNS responses with a flow key, which is defined with a pair of server IP address s and client IP address c. To this end, SFMap needs to address the research challenges discussed in Section 1. To tackle the research challenges, the SFMap framework works on top of DNG, which will be detailed in the next subsection. A DNG keeps track of the structure of DNS records; thus, it can deal with CNAME chains (Challenge 1). Next, by relaxing the constraints of the DNG, the SFMap framework can handle cases wherein there are no preceding DNS responses that are associated with the client-server pair (challenge 2). The details of the hostname estimation will be described in Section 3.3. Finally, by adequately maintaining the DNG and using the observed TTL values, the SFMap framework can deal with the dynamic nature of DNS mechanisms (Challenge 3). The updating mechanism for the DNG will be discussed in Section 3.4.

Figure 4 summarizes the components of the SFMap framework. SFMap has three main functions, i.e., Learner, Estimator, and Updater. Learner consists of two components: the DNG and the Frequency counter. Learner component reads DNS queries/responses and builds and keeps the DNG and Frequency counter. Estimator performs host estimation; i.e., given a pair of client-server IP addresses (c, s) for an HTTPS flow, estimator returns the most plausible hostname(s) using the information collected from DNG and Frequency counters. Updater reads DNS queries/responses and updates the status of the DNG and the Frequency counter.

Given these primitives, our problem can be formulated as maximum likelihood estimation (MLE) under the constraints of a DNG. Given c and s in an HTTPS flow, the MLE is formulated as follows.

n(c, s) = argmax n∈N Pr(n, c, s) (1) s.t. N = {n ∈ V c : n → G c s}, ( 2
)
where Here, we examine how the DNG expression naturally represents the behavior of DNS resolution. Assume that clients obtain a server address via DNS responses only and that we have never missed any DNS response for the clients; i.e., DNG G c represents all name resolutions requested by a client c. When a client c sends an HTTP request to a server n, the server n's IP address s should have been resolved by DNS. This association of n and s obtained through the DNS mechanism can be expressed as a path from n to s on the DNG G c . Note that there are cases where we cannot find such a path due to the caching mechanisms. In such cases, we need to employ several techniques that will be described soon.

G c = (V c , E c )

Estimator

In the estimation phase, we must first select candidate hostnames that are likely the original hostname for a given client-server pair (c, s). We extract a set of candidate hostnames N from DNG G c , using Eq. 2. If |N| ≥ 1, we estimate the hostname with the MLE shown in Eq. 1. A method to calculate the likelihood probability Pr(n, c, s) will be shown later.

As we mentioned in Section 1, N can be an empty set due to the standard and illicit DNS caching mechanisms. In such cases, we cannot directly associate an HTTPS flow with preceding DNS responses. To deal with these cases, SFMap extends the candidate hostnames by relaxing the constraint of edge expiration. This relaxation enables us to select hostnames that are missed due to the existence of DNS clients that ignore DNS TTL for improving the user experience. Now, N is obtained as

N = {n ∈ V c : n → Gc s}, (3)
where Gc = (V c , Ẽc ) and Ẽc include both valid and expired edges.

Finally, if we do not have any candidate hostnames at this stage, we use the union of all clients' DNGs (union DNG). In other words, we use the observations of other clients as a hint to estimate the most plausible hostname. Let C denote a set of all clients. The union DNG is defined as

G = (V = ∪ c∈C V c , E = ∪ c∈C E c ).
Using the union DNG G, the candidate hostnames can be selected as

N = {n ∈ V : n → G s}. ( 4
)
It then estimates the hostname with the following MLE formulation:

n = argmax n∈N Pr(n, s). ( 5
)
Like Eq. 3, we can further relax the constraint of expiration for the union DNG G; i.e.,

N = {n ∈ V : n → G s}, (6)
where G = (V, Ẽ) and Ẽ include both valid and expired edges.

To recap, the Estimator runs the combinations below from top to bottom in a stepby-step manner until a plausible hostname is found. For future reference, we give names to these steps, where LE and UE refer to Local and Union Estimators, and NTE refers to "No TTL Expiration". For instance, the estimator LE-NTE (Local Estimator with No TTL Expiration) starts with the first step and continues to the second step until at least one candidate hostname is found, but will not proceed to the third and fourth steps. We will examine the accuracies of these estimators to study the factors that contribute to improve the estimation accuracies.

Step MLE constraint Name 1st Eq. (1) Eq. ( 2) LE 2nd Eq. (1) Eq. ( 3) LE-NTE 3rd Eq. ( 5) Eq. ( 4) UE 4th Eq. ( 5) Eq. ( 6) UE-NTE Finally, we note the time complexity of the Union Estimators. In the Union DNG, a single-source path search from s with reverse edges requires O(|E|) on a directed acyclic graph with topological sort, and frequency lookups are executed for n ∈ N ⊆ V. Therefore, the time complexity of Union Estimators is O(|V| + |E|). However, we empirically revealed that the actual mean time complexity is much smaller than this worst-case upper bound, and is close to O(|V c | + |E c |) because majority of hostnames can be estimated with LE and LE-NTE as we shall show in Section 4. The details are omitted due to the space limitation.

Calculation of the likelihood probabilities

To calculate the likelihood probabilities, we make use of empirical data. Let F c (n, s) denote the frequency of DNS messages queried by client c for hostname n with resolved address s. Using F c (n, s), Eq. 1 can be calculated as

argmax n∈N Pr(n, c, s) = argmax n∈N F c (n, s).
Similarly, Eq. 5 can be calculated as

argmax n∈N Pr(n, s) = argmax n∈N F(n, s),
where F(n, s) = ∑ c∈C F c (n, s). The method to update the frequency will be shown in the next subsection.

Updater

The Updater updates DNG G c and frequency F c when it receives a DNS response. A DNS response is associated with client c and queried hostname n ⋆ . The response also includes a set of A records and another set of CNAME records. Let these sets be A and M, respectively. An A record associates hostname n and server address s, while a CNAME record associates two hostnames n ′ and n. Let these records be (n, s) ∈ A and (n ′ , n) ∈ M, respectively.

Due to the existence of short TTL value set for an A record, a client often resolves an intermediate hostname (i.e., CNAME) instead of the original one. In such a case, the frequency of an original hostname is undervalued. To cope with such a case, SFMap increments the frequencies of all original hostnames that can reach to the queried hostname. Let a set of edges be E c = {(n ′′ , n), (n ′ , n), (n, s)}, where n is a CNAME of n ′′ or n ′ . If n ⋆ = n is queried, the Updater increments F c (n ′′ , s) and F c (n ′ , s), instead of F c (n, s). Note that we assume that original hostnames should be leaf vertices on a DNG (a leaf is a vertex without incoming edge). In fact, more than 99.7% of requested hostnames are leaf vertices in our observations. Algorithm 1 presents an algorithm that updates G c and F c upon receiving a DNS response, (c, n ⋆ , A, M). We discount the incremental value by the number of (n ′ , s) pairs at Line 7, because the algorithm increments F c for all n ′ ∈ V reachable to n ⋆ and for all s in A. At Line 3, we update the expiration time of edge (u, v). In addition to Algorithm 1, the Updater periodically checks the TTL expiration for all edges. If the DNS TTL expires for an edge (u, v), the edge will be removed

Evaluation

Here, we first describe the datasets used and present some basic statistics derived from the data. We then evaluate the estimation accuracy of SFMap. For reference, we compare the performance of SFMap with DN-Hunter [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF]. Finally, we examine the resource consumption of SFMap, which was implemented with Python.

Algorithm 1: Updater

Input: c, n ⋆ , A, M // DNS response 1 for (u, v) ∈ A ∪ M do 2 E c = E c ∪ {(u, v)}
// to add edge 3 update expire time of edge (u, v)

4 N ′ = {n ′ ∈ V c : ( * , n ′ ) E c , n ′ → Gc n ⋆ } // leaf vertices reachable to n ⋆ 5 for n ′ ∈ N ′ do 6 for ( * , s) ∈ A do 7 F c (n ′ , s) = F c (n ′ , s) + 1 |N ′ |•|A| // to increment frequency 8 return G c , F c

Datasets and statistics

To investigate the effectiveness of SFMap, we used the two datasets, LAB and PROD, which are the packet traces collected from a gateway router of local area network used by a research group and a gateway router of middle-scale production network, respectively. The basic statistics of the datasets are summarized in Table 1. As is shown in Table 1, the datasets cover two different scales, small and middle. Both datasets have same time length, twelve hours. Of the twelve hours, the last two hours are used to examine the accuracy; i.e., the first 10 hours are used for warm-up phase. We adopted the length of warm-up from the observation of TTL distribution shown in Fig. 2; i.e., majority of the DNS resource records had TTL values less than 10 hours.

Here, we present the characteristics of DNGs derived from our datasets. Table 2 presents the statistics of the DNGs. For brevity, we omit DNGs with TTL expiration because these DNGs should be smaller than those without TTL expiration. As is shown in the table, Union DNGs have fewer nodes and edges. For instance, since the number of clients for the LAB dataset is 10 (see Table 1), the total number of nodes in the Local DNGs should be 10 × 460 = 4600. Thus, the number of total nodes in the Union DNG (=2849) is less than the number of total nodes in the Local DNGs. This observation implies that (1) each client-server pair in the Local DNGs has duplicate nodes and edges, and (2) the Union DNGs can be maintained with less memory. Figure 5 shows the CDF of the number of candidate hostnames for each HTTP request. The results suggest that roughly 15% of the HTTP requests have multiple candidates; i.e., we must statistically estimate the original hostname from these candidates.

Estimation accuracy

Our methodology was evaluated using the two datasets. We make use of HTTP as a means to evaluate the accuracy of our methodologies. The ground truth was obtained from HTTP request headers, which contain hostname information. We note that although the distributions of hostnames could be different between HTTP and HTTPS, the fundamental mechanism of resolving hostname before starting HTTP/HTTPS communication should be identical. From the packet traces, we read DNS packets to build and update the DNGs. For each HTTP request pair (c, s), we estimate the hostname and compare it against the ground truth. For comparison purposes, we implemented DN-Hunter [START_REF] Bermudez | DNS to the Rescue: Discerning Content and Services in a Tangled Web[END_REF]. DN-Hunter has a single parameter that determines the size of memory, which keeps track of tuples of (c, s, N), where N is a hostname. To obtain the highest performance of DN-Hunter, we set infinite amount of memory size. We note that this configuration did not overflow physical memory we used in our experiments. Table 3 and Table 4 summarize the results, where we use the notations introduced in Section 3.3. Table 3 shows the estimation accuracies in the context of exact matching, and Table 4 relaxes matching using a public suffix [1]; i.e., we can see that aaa. example.com and bbb.example.com are matched in the context of the public suffix. Using the public suffix matching allows us to distinguish hostnames with different domains, e.g., youtube.com and google.com.

First, the accuracies were improved for estimators with no TTL expiration (NTE). This observation suggests that there are a non-negligible number of DNS implementations that ignore TTL settings, which agrees with a previous report [START_REF] Callahan | On Modern DNS Behavior and Properties[END_REF]. Second, the Union DNG also contributed to improve the accuracy. This observation suggests that using other clients' information is useful in improving the accuracy when no other hint is available. Third, if we allow public suffix matching, accuracies are further improved for all the estimators. The UE-NTE achieved roughly 95% of accuracy for both datasets. Finally, the UE-NTE outperformed DN-Hunter. For the exact matching experiments, while the estimation error rates of DN-Hunter were 15-32%, the estimation error rates of UE-NTE were 8-9%. Thus, UE-NTE successfully reduced the error rates by 50-70%.

DN-hunter returns a single hostname given a client-server pair; however, if there are multiple candidate hostnames, SFMap can return several hostnames with the highest likelihood probabilities. Table 5 shows the results where we accept the top three hostnames as estimation. Notably, accuracies exceed 96-98% for exact matching if we pick up the top three hostnames. We note that in most cases, the hostnames ranked in the top three look similar. For instance, the top three hostnames are: pagead2. googlesyndication.com, pubads.g.doubleclick.net, and googleads.g.doubleclick. net, which are all attributed to Ad Network services. Thus, by extending the candidate hostnames, we can establish better estimations that work in practice. This extension is acceptable for our original motivation; i.e., understanding the mix of HTTPS traffic.

Resource consumption

We study the resource consumption of SFMap, using its implementation with Python. We note that the implementation has a much room for improvement in terms of optimizing resource management. Table 6 shows the amount of memory consumed and the amount of time to process the entire data, including data for warm-up. The results demonstrate that our implementation of SFMap works within a reasonable amount of

Discussion

Here, we discuss the limitations of the proposed SFMap framework. We also outline several future research directions that can help extend our framework.

Sources of misclassification

By carefully examining the estimation results, we found several intrinsic sources of misclassification. There are several factors that are associated with the incomplete measurements. As we mentioned before, the first factor is the existence of aggressive DNS caching mechanisms that ignore DNS TTL setting. The second factor we found through this study was mobility of terminals; i.e., an IP address had already been resolved in other network before the terminal arrived to the vantage point. The third factor we found was the use of an IP address in the URI. We found a non-negligible number of HTTP requests had such URIs. We manually inspected the cases and found that there are several applications that likely hard-coded an IP address; thus, they never send DNS queries. Although these are not the controlling factors today, we may need to address them if such deployments become popular in future.

Scalability

As shown in Section 4.3, our SFMap implementation processed traffic collected at middle-scale production network within a reasonable amount of memory; i.e., less than 700 MB. Then, we may want to ask whether SFMap works for large-scale networks. First, because SFMap does not require per-packet processing, we believe that the processing time does not matter in practice. It just processes DNS response packets and the first packets of HTTPS flows, ignoring remaining packets. Furthermore, as we discussed in Section 3.3, empirical studies revealed that time complexity of estimation is close to O(|V c | + |E c |), which is fairly small as shown in Table 2. We also note that estimation processes can be parallelized if we need it. Second, it is clear that the size of DNGs increases as the number of observed client increases. If the size of DNG becomes large enough to press the capacity of memory, we need to eliminate old records. Instead of keeping all the records for a certain amount of time, e.g., 12 hours, we may want to quickly delete old records that are less-likely to be reused in future. More sophisticated way to manage the elements in DNGs is left for the future study. Another possible solution would be to build a new algorithm that can maintain and update DNGs in a more compact data structure. The topic is also left for the future study.

Summary

The SFMap hostname estimation framework was presented. SFMap enables network operators to estimate the hostnames of HTTPS traffic by observing DNS queries/responses. To tackle the challenges that arise from the recent dynamic deployment and diverse implementations of DNS ecosystems, the proposed SFMap framework runs on top of a single key component; i.e., a DNG, which is a formal expression that characterizes the highly dynamic and diverse nature of DNS mechanisms. From extensive analyses using real packet traces collected from two distinct locations with different network scales, we have demonstrated that SFMap has good estimation accuracy and can outperform DN-Hunter, which is a state-of-the-art estimation technique. Our experiments using middle-scale network traffic with thousands of clients demonstrated that SFMap can be run on a standard commodity PC, using less than 700 MB of memory space. In future, we plan to enhance the scalability of SFMap.

  .akamaiedge.net www.ieee.org.edgekey.net www.ieee.org

Fig. 1 .

 1 Fig. 1. Example of a CNAME chain.

Fig. 2 .

 2 Fig. 2. CDFs of TTL values.

Fig. 3 .

 3 Fig. 3. An example of CNAME ambiguity.

  . The time complexity of maintenance is O(|V c |) for the loop at Line 5, assuming O(|A|) = O(|M|) = O(1).

Fig. 5 .

 5 Fig. 5. CDFs of the number of candidate hostnames for each HTTP request: LAB (left) and PROD (right).

  In the following, we describe how we build and update G c , how we extract N, how we compute the likelihood probability Pr(n, c, s), and how we get the final estimation n.

		Learner
		DNG Sec 3.2		input	HTTPS flow
	DNS queries/ responses	Freq. Counter	Es*mator Sec 3.3	output	Flow key: {s, c} Hostname, n
		Updater
		Sec 3.4
		Fig. 4. Components of SFMap.
	3.2 DNG
	A DNG, G

denotes a DNG built for c, and binary operator x → G y represents whether vertex x can reach to vertex y on graph G. c , is a directed graph used to keep A and CNAME records observed in DNS responses queried by client c. DNGs can be built separately for each client c. A vertex, v ∈ V c , is a server IP address or a hostname, while an edge, e ∈ E c , represents an A or CNAME record that links a vertex to another vertex. Each edge is grafted by a corresponding A or CNAME record observed in a DNS response, and is associated with its expire time determined by observed TTL. If an edge, e ∈ E c , is expired, it will be removed from G c .

Table 1 .

 1 Basic statistics of the datasets.

	learning # of # of DNS estimating	# of # of HTTP	# of
	time clients responses	time servers requests hostnames
	LAB 0 ∼ 12 h	10	5,226 10 ∼ 12 h 1,705	542	1,135
	PROD 0 ∼ 12 h 4,250 86,854 10 ∼ 12 h 10,785	55,091	10,534

Table 2 .

 2 Statistics of the DNGs at the end of measurement period.

		Local DNG	Union DNG
		w/o TTL expiration w/o TTL expiration
		mean	mean	total	total
		# of nodes # of edges # of nodes # of edges
	LAB	460	755	2,849	5,979
	PROD	56	80	25,403 172,974

Table 3 .

 3 Accuracies of the estimators (exact matching).

	LE LE-NTE UE UE-NTE DN-Hunter
	LAB 54.98% 68.08% 71.59% 92.25%	67.90%
	PROD 79.90% 88.29% 90.88% 90.88%	85.40%

Table 4 .

 4 Accuracies of the estimators (public suffix matching).

	LE LE-NTE UE UE-NTE DN-Hunter
	LAB 57.20% 70.30% 73.80% 94.46%	73.43%
	PROD 83.20% 92.12% 94.52% 94.98%	89.98%

Table 5 .

 5 Accuracies of the Top-3 estimations (UE-NTE).

		Exact matching	Public suffix
		Hit in 1 Hit in 2 Hit in 3 Hit in 1 Hit in 2 Hit in 3
	LAB	92.25 97.23 98.16 94.46 98.16 98.16
	PROD 90.88 95.77 96.71 94.98 97.01 97.43

Table 6 .

 6 Memory usage of RAM and processing time for UE-NTE. .e., less than 40 MB for LAB and less than 700 MB for PROD. Also, processing time is much shorter than the actual measurement length, 12 hours. Thus, SFMap should work in a real-time fashion. We will further discuss the scalability of SFMap in the next section.

		memory (MB) time (s)
	LAB	35.1	0.8
	PROD	686.2	20.6
	memory, i

Acknowledgements

This work was supported by JSPS KAKENHI Grant Number 25880020.