Pierre Laperdrix
email: pierre.laperdrix@insa-rennes.fr

Walter Rudametkin
email: walter.rudametkin@univ-lille1.fr

Benoit Baudry
email: benoit.baudry@inria.fr

Mitigating browser fingerprint tracking: multi-level reconfiguration and diversification

The diversity of software components (e.g., browsers, plugins, fonts) is a wonderful opportunity for users to customize their platforms. Yet, massive customization creates a privacy issue: browsers are slightly different from one another, allowing third parties to collect unique and stable fingerprints to track users. Although software diversity appears to be the source of this privacy issue, we claim that this same diversity, combined with automatic reconfiguration, provides the essential ingredients to constantly change browsing platforms. Constant change acts as a moving target defense strategy against fingerprint tracking by breaking one essential property: stability over time.

We leverage virtualization and modular architectures to automatically assemble and reconfigure software components at multiple levels. We operate on operating systems, browsers, fonts and plugins. This work is the first application of software reconfiguration to build a moving target defense against browser fingerprint tracking. The main objective is to automatically modify the fingerprint a platform exhibits. We have developed a prototype called Blink to experiment the effectiveness of our approach at randomizing fingerprints. We have assembled and reconfigured thousands of platforms, and we observe that all of them exhibit different fingerprints, and that commercial fingerprinting solutions are not able to detect that the different platforms actually correspond to a single user.

I. INTRODUCTION

Most users customize their browsers by setting their language, setting comfortable screen resolution and fonts, adding plugins to provide features, etc. Companies and open source communities have developed a massive diversity of software components to personalize browsing platforms. However, the downside to almost infinite customization is that users' platforms are unique. This, combined with easy access to the browsing platform's details, is leading to a new kind of privacy concern called "browser fingerprinting". Eckersley [START_REF] Eckersley | How unique is your web browser?[END_REF] shows that through the collection of a small set of attributes (e.g., plugins, fonts, browser type, OS), it is possible to build a browser fingerprint that is mostly unique and stable over time. These two properties make it an excellent candidate to track users. Fingerprinting, also called the "Cookieless monster" [START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF], is stateless and does not store anything on the user's device. This makes protecting privacy harder than in the case of cookies, while the adoption of fingerprinting is growing.

The diversity of software components to customize browsers is the source of a major privacy problem. We argue that this same diversity, combined with multi-level software reconfiguration, provides the foundations for a counter measure to browser fingerprint tracking. The idea is as follows. A browsing platform is assembled by randomly selecting a coherent set of components (an OS, a browser, plugins, etc.). Third parties collect, via the browser, enough information about the platform's components to form a fingerprint. We then regularly reconfigure the platform-thanks to a large set of diverse components-causing a different fingerprint to be exhibited. Our approach breaks one essential property for the exploitation of browser fingerprints: their stability.

We propose an original application of dynamic software reconfiguration techniques to establish a moving target defense against browser fingerprint tracking. We aim at regularly changing the four most distinctive elements in a fingerprint: the operating system, the browser, the list of fonts and the list of plugins. We call these the Diversified Platform Components, or DPC. Our approach consists in creating DPC configurations by randomly selecting components from a large pool, called the diversity reservoir. The DPC configurations are then used to assemble and reconfigure the browsing platforms, leading to diverse fingerprints being exhibited over time.

We experiment the effectiveness of our approach to mitigate browser fingerprint tracking with our prototype tool called Blink 1 . We empirically assess Blink's effectiveness in answering the following question: can we assemble and reconfigure browsing platforms that exhibit truly dissimilar fingerprints over time? We define a novel dissimilarity metric to compare the fingerprints collected from the platforms that Blink assembles. We also run commercial fingerprinting scripts to evaluate their ability to recognize the fingerprints as coming from the same user. The results show that the browsing platforms exhibit fingerprints that are very dissimilar and can deceive BlueCava, a popular commercial fingerprinting script.

The main contributions of this paper are:

• A moving target defense that leverages software diversity and dynamic reconfiguration to automatically assemble diverse browsing platforms. • A dissimilarity metric that estimates the likelihood that a fingerprinter will consider two fingerprints as coming from the same platform. • An experimental assessment of Blink's ability to automatically assemble random, dissimilar, and valid platforms.

Section II presents the background and related work on browser fingerprinting. Section III describes our approach, the threat model we address, and discusses balancing privacy and comfort through users' preferences. Section IV details our prototype, Blink. Section V presents our empirical observations, while section VI concludes this paper. II. BACKGROUND Eckersley demonstrated that browser fingerprints are often unique and unlikely to drastically change over time [START_REF] Eckersley | How unique is your web browser?[END_REF]. For example, the fingerprint in Table I "appears to be unique" among the more than four million fingerprints collected through the Panopticlick website 2 . In this section we review the state of the art and the state of practice on fingerprinting, as well as existing solutions to prevent fingerprint tracking.

A. Fingerprinting techniques

The literature reports on many ways to fingerprint browsers. User agent and Accept headers are automatically sent to websites through HTTP headers. Other information, like the list of plugins, the timezone or the screen's resolution, are easily accessible via JavaScript through the navigator and screen objects [START_REF] Acar | Fpdetective: dusting the web for fingerprinters[END_REF]. The user agent gives basic information on the operating system, while the Flash plugin gives more precise attributes. Table I displays a fingerprint including, through Flash, the Linux kernel version and the list of fonts. According to Eckersley [START_REF] Eckersley | How unique is your web browser?[END_REF], fonts are one of the most discriminating attributes. Another technique consists in testing the JavaScript engine to identify the browser and to collect information on the OS and hardware. Mulazzani et al. use tests that cover the ECMAScript standard to find functional differences between browsers [START_REF] Mulazzani | Fast and reliable browser identification with javascript engine fingerprinting[END_REF]. Since every major browser update brings new JavaScript functionalities, it is possible to test for their presence (or absence). Mowery et al. benchmark Javascript operations and use time differences to identify the browser and the system's architecture [START_REF] Mowery | Fingerprinting information in JavaScript implementations[END_REF]. More hardwarefocused techniques also exist. In 2006, Murdoch introduced CPU skew fingerprinting [START_REF] Murdoch | Hot or not: Revealing hidden services by their clock skew[END_REF], which uses timing information to fingerprint a device. Mowery et al. [START_REF] Mowery | Pixel perfect: Fingerprinting canvas in HTML5[END_REF] and Acar et al. [8] studied canvas fingerprinting. This technique uses the HTML5 Canvas to render an image. Different hardware or software result in slight differences in the image.

B. The adoption of fingerprinting

Fingerprinting has already been adopted by many websites to complement cookies as a means of tracking. For example, the privacy policies of Google and Twitter declare they gather such data to identify users. Google states they "may collect device-specific information", such as "operating system version" or "unique device identifiers"3 , while Twitter indicates they collect "Log data", such as "browser type" or "device information" 4 . Other companies provide third party services for purchase to easily fingerprint and track users. BlueCava is a well known actor in this domain [START_REF] Acar | Fpdetective: dusting the web for fingerprinters[END_REF].

C. Existing solutions to counter fingerprint-based tracking

Here we summarize solutions to limit browser fingerprint tracking and highlight some of their shortcomings.

1) Blocking extensions: Browser extensions, such as No-Script5 , Ghostery 6 and Privacy Badger7 , can block fingerprinting scripts. NoScript only runs scripts that have been whitelisted by the user. Ghostery and Privacy Badger prevent browsers from downloading scripts from known trackers. However, these extensions offer no guarantees against fingerprinting because it is hard to maintain up-to-date whitelists or databases. Furthermore, privacy-enhancing extensions can be counterproductive since their presence can be detected and increases the identifying information from the browser [START_REF] Mowery | Fingerprinting information in JavaScript implementations[END_REF].

2) Spoofing extensions: User agent spoofing extensions are supposed to increase anonymity by lying about the user agent. In January 2015, we found 23 user agent spoofers for Firefox and 15 for Chrome, in their respective markets. However, as shown by Nikiforakis et al. [START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF], a major problem with these extensions is that they produce inconsistent headers (e.g., an iOS platform with the Flash plugin). For example, let us consider the following excerpt of a fingerprint that contains a user agent, and the platform object collected through both the JavaScript and Flash APIs: UserAgent={Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.1; Trident/5.0)} ; JS.platform={MacIntel} ; Flash.platform={Mac OS 10.10.2}.

This fingerprint, collected from a browser using a spoofing extension, exhibits an inconsistency: the user agent says the browser is MS Internet Explorer and runs on Windows NT, but the platform objects indicate Mac OS (not Windows and cannot host an IE browser). Also, these extensions act only on the user agent header and not on the entire fingerprint, allowing cross-browser fingerprinting techniques [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF] to succeed.

3) Use of multiple browsers: Another solution is to use multiple browsers, each one exhibits a different fingerprint. However, Boda et al. [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF] showed that changing browsers is insufficient because fingerprinters can rely on OS-specific data, fonts or plugins to compute a unique fingerprint since these parameters do not evolve from one browser to the next. This is known as Cross-Browser Fingerprinting.

4) Tor browser: The Tor browser is a modified Firefox browser, specifically designed for the Tor network. This browser attempts to create a single configuration for all Tor users so that no individual user can be identified. By design, the Tor browser's fingerprint is unique and thus known to fingerprinters. The Tor network is not immune to threats or attackers, as shown by Wang and Goldberg [START_REF] Wang | Improved website fingerprinting on tor[END_REF]. To remain effective, customizability and personalization are severely hampered, supplanted by the Tor browser's mono-configuration. This is also extremely brittle since a simple change (e.g., resize the browser window) stands out among the limited number of Tor users and can be immediately identified by fingerprinters.

5) PriVaricator: PriVaricator [START_REF] Nikiforakis | Privaricator: Deceiving fingerprinters with little white lies[END_REF] is a solution designed specifically to break fingerprint stability. It uses randomization policies so the browser can decide when to lie about key fingerprintable features, like the list of plugins or font sizes. PriVaricator succeeds at fooling some well-known fingerprinters while minimizing site breakage. However, it only addresses what the authors call "explicit fingerprinting", i.e., direct attempts to collect attributes exposed by the browser. PriVaricator does not address fingerprinting performed by plugins like Flash that give access to the complete list of fonts.

III. APPROACH

This section establishes the threat model we target and goes into the details of our moving target approach. We explain how we leverage software diversity to change a user's browsing platform over time and we discuss the impact this has on both fingerprints and user comfort.

A. Threat model

We aim at mitigating the exploitation of browser fingerprints to track users, which is a direct threat to privacy. As noted in section II, browser fingerprint tracking relies on the following: web browsers allow remote servers to discover sufficient information about a user's platform to create a digital fingerprint that uniquely identifies the platform. We argue that fingerprint uniqueness and stability are the key threats to browser fingerprint tracking, and in this work we aim at breaking fingerprint stability over time.

B. A moving target defense against tracking

We propose to automatically reconfigure a user's platform to exhibit different fingerprints over time that cannot easily be linked to one another. Figure 1 shows the elements of a browsing platform that affect the fingerprint: configuration data at different levels (HW, OS, browser); software components that are assembled at different levels (e.g., apt-get, browser plugins, fonts); hardware components, such as the graphics card; cross-level dynamic attributes collectable only at runtime, such as through the HTML5 canvas. Once a user starts browsing the web, these data are used to create a fingerprint. We say that a platform exhibits said fingerprint.

Our approach reconfigures components that affect the exhibited fingerprint. Nikiforakis et al. [START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF] show that current commercial fingerprinters collect only a subset of all possible attributes, and Eckersley [START_REF] Eckersley | How unique is your web browser?[END_REF] found the most distinguishing attributes of a fingerprint to be fonts, plugins and user agents. Other attributes are often shared by a large pool of users, rendering them less discriminating. Based on this, we identify the following set of Diversified Platform Components (DPC) to be automatically reconfigured: fonts, plugins, browsers, the operating system and the CPU architecture. We call a DPC configuration a consistent assembly of a browser running in an operating system, with a specific set of fonts and plugins.

Definition 1: Diversity reservoir is the set of components used to assemble new configurations of the DPC. Given a set O of operating systems for different architectures, a set B of browsers of different types and versions, a set F of fonts and a set P of plugins, the reservoir is

DR = O ∪ B ∪ F ∪ P .
Our intuition is that the same set of diverse software components that cause fingerprint uniqueness can be exploited to create very large diversification reservoirs. These can be used to build trillions of distinct configurations to switch among. Figure 2 illustrates this principle: we randomly select components from the diversity reservoir to create DPC configurations used in the browsing platforms. Over time we generate new configurations that replace previous ones, changing the browsing platforms and the exhibited fingerprints. The user decides when these changes occur. This approach falls into the family of dynamic platforms, a specific form of moving target approaches, as described by Okhravi et al. in [START_REF] Okhravi | Finding focus in the blur of moving-target techniques[END_REF]. Our moving target defense relies on an essential characteristic needed for reconfiguration: the modular architecture of systems and browsers. Modularity makes it possible to reconfigure the browsing platform, on demand, by automatically assembling components. This also allows us to progressively assemble configurations instead of building them beforehand.

Our approach is characterized by three essential properties: (i) the assembled platforms always exhibit consistent fingerprints because the platforms are genuine and we do not lie about any attributes; (ii) we assemble correct platforms, i.e., platforms composed of compatible components and which run correctly; and (iii) each reconfiguration causes the exhibited fingerprints to change. Section IV-B discusses the model that supports the assembly of correct configuration and in section V, we empirically demonstrate that variations in the exhibited fingerprints deceive two commercial fingerprinting scripts.

C. Balancing privacy and browsing comfort

There are many places where user comfort conflicts with potential gains in privacy. For example, we have included browsers in the DPC because it is an important distinguishing factor in a fingerprint. Yet, users populate their browsers with data such as bookmarks, passwords and open tabs. We believe that it is important to transfer user data between platforms we assemble in order to keep a comfortable browsing experience despite switching DPC configurations. We developed an offline cross-browser tool that is responsible for transferring the user profile between browsing platforms. We also acknowledge that not all users are ready to randomize their favorite browsers to obtain a different fingerprint, so we let them customize DPC components. Users select components from the DPC that will be included or excluded from all configurations. We call alterable and essential the components that a user decides to include, respectively discard from the set of DPC.

The choice of an essential or alterable component is subjective and can be done for functional reasons or for comfort. A set of plugins might be crucial for someone's web experience, while another user may simply wish to never change browsers. Furthermore, these choices directly impact the remaining size of the diversity reservoir and thus, the search space for randomization. The larger the set of essential components is, the smaller the total search space will be.

Deciding when to reconfigure can also impact privacy and comfort. This is a key decision because frequent changes can be effective at mitigating tracking, but are disturbing to users. However, waiting too long between changes increases the time a user's fingerprint remains static, leading to larger sessions that can be tracked. We provide two strategies for reconfiguration, a full reconfiguration strategy, called Leery, and a light-weight one, called Coffee break.

Definition 2: The Leery strategy reconfigures all levels of the browsing platform: the operating system, the browser, the fonts and the plugins. Essential components are kept and alterables are randomized. This strategy is used each time a user starts a new session (i.e. starts a browser for the first time). A fresh DPC configuration is generated and kept until the user ends the session. It draws its name from its cautiousness by reconfiguring as many components as possible.

Definition 3: The "Coffee break" strategy aims to be faster than Leery by reconfiguring only fonts and plugins. The browser and the operating system do not change. As always, essential components are kept and alterable components are randomized. This strategy is triggered in different ways: manually, by having the user lock his computer, or by waiting for a period of inactivity, hence the name. It should be noted that reconfigurations do not occur while the user is browsing the web. To explicitly change the current fingerprint, a new session should be started (e.g., by restarting Blink) or a Coffee break reconfiguration should be triggered. Other strategies are also possible, but we feel these two cover a wide range of uses. The experimental assessment of section V-C shows that both strategies can defeat current commercial fingerprinters, but they affect fingerprints differently (more changes lead to more privacy).

D. Dissimilarity metric

To assess the effectiveness of fingerprint diversification, we need to quantify the differences between fingerprints. To our knowledge, there is no established measure to compare two fingerprints, or to determine if two different fingerprints can be related to a single platform. We define the following dissimilarity metric that aims at capturing the difference between the attribute values observed in two fingerprints.

D(F P 1 , F P 2 ) = 8 i=1 ω attri × d(attr i (F P 1 ), attr i (F P 2 )) 8 i=1 ω attri
The metric is the sum of dissimilarities between 8 attributes. Its value is defined in the range [0,1]. Each attribute is weighted according to Eckersley's study [START_REF] Eckersley | How unique is your web browser?[END_REF]. Heavier weights indicate more revealing attributes. This captures, for example, that two fingerprints with the same fonts are closer than two fingerprints with the same timezone. We also defined specific dissimilarity functions d for attributes that are lists of values (e.g., fonts, user agent). The weights ω and the dissimilarity functions d are defined in Appendices A and B.

To illustrate the intuition behind our metric, let us consider two variations of the fingerprint in Figure I. If we change the browser from Firefox to Chrome and add plugins (as shown in Table II), the dissimilarity between the new and original fingerprints is 0.46. Intuitively, a third party would hardly III). The dissimilarity is then 0.01, which indicates that the two fingerprints are almost identical. This fits our intuition: it is very likely that a browser's version will change at some point in time (e.g., it is updated). Thus, similar fingerprints according to our metric are fingerprints that are likely to be detected as originating from the same user. These two examples illustrate that some differences are more revealing than others, which is what our dissimilarity metric is capturing.

E. Positioning w.r.t. existing solutions

Our proposal is to reconfigure the browsing platform at multiple levels, causing the platform to exhibit a different fingerprint each time. It falls into the family of moving target techniques, as described by Okhravi et al. [START_REF] Okhravi | Finding focus in the blur of moving-target techniques[END_REF]. It is, by their classification, a dynamic platform, and is similar in nature to creating moving attack surfaces for web services [START_REF] Huang | Introducing diversity and uncertainty to create moving attack surfaces for web services[END_REF]. Consequently, Blink's advantage over user-agent spoofers is to never lie. Fingerprints exhibited by the browsing platforms are based on genuine configurations, with genuine browsers, and genuine operating systems. By construction, there are no inconsistencies among the fingerprint attributes, which prevents standing out as a liar. Our approach also relates to secretless strategies because knowing the fingerprint reconfiguration strategy (random selection of DPC components) is not enough to defeat it. Cox et al. give insight into the wealth of security advantages obtained through software diversity, particularly when there are no secrets to hide [START_REF] Cox | N-variant systems: a secretless framework for security through diversity[END_REF].

Cross-browser fingerprinting shows that simply changing browsers is not enough because other attributes, such as fonts and plugins, are sufficient to create unique fingerprints [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF]. We counter these attacks by randomly changing multiple levels of the browsing platform, not only the browsers.

The main drawbacks of the Tor browser are its usability and the brittleness of its fingerprint. Users should not change any of the Tor browser's configuration options, nor add plugins, because their fingerprint will diverge from the base fingerprint, disrupting the unique fingerprint approach and making them identifiable. Our approach is the opposite: we create unstable, always changing platforms that exhibit very different fingerprints. We welcome the addition of user plugins and fonts.

And we do not force the use of any restrictive extensions (e.g., NoScript) that severely alter the browsing experience.

Finally, we do not rely on blocking fingerprinting scripts. Maintaining proper lists of scripts requires significant effort. Blink works as a moving target defense system that is oblivious to fingerprinting scripts. Blink also has the potential to resist currently unknown fingerprinting attacks thanks to the use of multi-level reconfigurations.

IV. IMPLEMENTATION

Blink reconfigures the alterable components of a DPC configuration in order to assemble unique browsing platforms. Each unique platform will exhibit a unique fingerprint because the platform components permeate the fingerprint, as seen in figure 1. Hence, by reconfiguring the platform, distinct fingerprints are exhibited. However, several issues need to be addressed for this to work in practice. Namely, the implementation must assemble and reconfigure DPC configurations that lead to platforms that function correctly. The diversity reservoir must be built up to provide a large reconfiguration space. And, finally, changing from one DPC configuration to another should be made as simple and transparent as possible.

This section describes how Blink assembles random browsing platforms, achieves a large amount of fingerprint diversity, and maintains a multi-platform user profile to improve usability. We have implemented Blink using both reconfiguration strategies described in section III-C. Those implementations are later referred to as Leery Blink and "Coffee break" Blink.

A. Multi-level reconfiguration

Blink leverages the modular architecture of operating systems and browsers to randomly assemble browsing platforms that function correctly and exhibit unique fingerprints. To maximize the reconfiguration space and the diversity of exhibited fingerprints, it is important to change as many components as possible, including the CPU architecture, the operating system, the browser, plugins and fonts, which are all statistically important for fingerprinting. Although it is possible to randomize some components directly in the user's system, changes such as adding and removing fonts can have negative side-effects on other applications. More importantly, certain components, such as the operating system or the CPU architecture, cannot be directly changed. It has been shown by Boda et al. [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF] that if enough data is gathered from a system it can still be fingerprinted and tracked despite the use of multiple browsers. For these reasons, Blink uses virtual machines to maximize the diversity space that can be exploited by randomizing the operating system and the CPU architecture, all the while maintaining a high degree of isolation between the user's system, fingerprinters and the reconfiguration process.

Blink assembles components at multiple levels to form the browsing platform shown in Figure 3. We use the term multilevel reconfiguration because the selection of higher level components in the platform directly depends on lower level ones (e.g., a browser plugin depends on the browser, which itself depends on the operating system). Fonts are a special

Browsing Platform 1

Browsing Platform N Fig. 3. A multi-level view of browsing platforms. Virtualization isolates the user's system.

case because although they do not have hard dependencies to or from other components in a DPC configuration, they do impact all user interface applications, including browsers and websites. Moreover, the modularity mechanisms are not the same for all levels: there are different dependency management tools in systems and in browsers, different plugin types and versions for different browsers, different CPU architectures, etc. Fonts may also be specific to a given system due to licensing or packaging issues. 1) Operating system reconfiguration: Blink uses Virtual-Box to isolate browsing platforms because it is open source and multi-platform (supports Linux, Mac OS and Windows as both host and guest). Also, VirtualBox abstracts hardware (enabling us to randomize the CPU architecture), provides extensive functionality, has low overhead, and allows for a number of configuration parameters. Added bonuses are a user-friendly GUI and guest additions to improve integration. However, it could be substituted with other solutions.

We use VirtualBox's shared folders to transfer data between the host and the VMs. Launching a browsing platform starts the assembly of a randomized DPC configuration (i.e., OS, fonts, plugins, browser). The browser, fonts and plugins are copied to shared folders, as is the user's profile (i.e., open tabs, bookmarks, downloads, saved passwords). VMs start the BlinkVM.py monitoring script, whose job is to install fonts and plugins, prepare the user profile, launch and monitor the browser, and listen for commands from the host (e.g., shutdown, coffee break reconfiguration). When shutting down, shared folders are cleaned and the user-profile is recovered. VMs are additionally snapshotted when launched and rolled back to their pre-browsing states when the browsing session ends. This ensures the platform returns to a known stable state that is free of temporary files, cookies, trackers, and malware. Finally, because the OS is low-level, reconfiguring it can cause the browser and plugins to be invalidated.

2) Font reconfiguration: To install a font, the font file must be copied to the correct folder and registered. However, many applications do not detect font changes dynamically. We tested two methods to list the fonts available in browsers, namely Adobe Flash font enumeration and JavaScript font probing. Our results indicate that to ensure font changes are reflected in the exhibited fingerprint you should restart the browser.

3) Browser reconfiguration: Installing a browser requires copying the installation folder and running the main executable. Browser's run as processes so changing from one browser to another is as simple as stopping and starting them.

4) Plugin reconfiguration: Installing a plugin is as simple as copying a file to the proper plugin directory. However, unlike fonts, plugins are compiled for a specific CPU architecture and operating system, and can have runtime dependencies on configuration files or system libraries. Furthermore, not all plugins work in all browsers. We focused on randomizing NPAPI plugins (compatible with most browsers) and PPAPI plugins for Chrome (as of January 2015, NPAPI plugins are blocked by default8 ). When reconfiguring, plugins must match the CPU architecture (e.g., i686, IA-64, amd64), the operating system (e.g., Windows, Linux), and the browser (e.g., Firefox, Chrome) of the DPC to work properly. Interestingly, plugin support is often dynamic, as is the case with Chrome, Opera and Firefox. This allows Blink to reconfigure the plugin list at runtime, and is used for Coffee break reconfigurations to immediately change the exhibited fingerprint without restarting the browsing platform.

B. The diversity reservoir

At the heart of Blink is the idea that exploiting software diversity can create an ever changing browsing platform that limits attempts to track its users through browser fingerprint tracking. However, this diversity has to be built; software components must be collected and managed to ensure consistent, functional platforms are assembled and reconfigured.

1) Building the diversity reservoir: The operating system is the base of the browsing platform. We built VMs using various operating systems, although we focused on the Ubuntu and Fedora Linuxes for the i686 and x86 64 architectures. Many pre-built Linux and *BSD VMs can be downloaded freely over the internet to avoid the installation process. Other operating system's often require licenses and cannot be freely distributed. Once built, each VM must be configured to work with Blink. This includes setting up shared folders and configuring Blink's monitoring script to auto-start.

We focused on the Chrome and Firefox browsers and downloaded multiple versions of each from the vendors' websites. There's one version for each combination of release channel (stable, beta and development) and CPU architecture (i686 and x86 64). It is easy to add browsers and there are a number of forks for both Chrome (Chromium, SRWare Iron, Epic, . . . ) and Firefox (Iceweasel, Seamonkey, . . . ) that are trivial to integrate. To add a browser you must unpackage it into Blink's browser folder and follow the naming convention.

We wrote scripts to crawl the Ubuntu and Fedora repositories for fonts. We found many duplicate fonts, yet some fonts tend to be specific to a distribution. Moreover, fonts are most often installed in groups, as seen with packages that install multiple fonts. Blink allows defining font groups and systemspecific fonts to avoid exhibiting uncommon fingerprints. The biggest challenge with plugins is to account for the wealth of browser, operating system and CPU architecture combinations necessary for a plugin to function correctly in each possible DPC configuration. To obtain a large set of plugins for fingerprint diversity, we wrote scripts to crawl the Fedora and Ubuntu Linux repositories and look for plugins in all packages, for both i686 and x86 64 architectures. When a plugin is found, the package is downloaded, and the plugin is extracted. Any dependencies towards, for example, configuration files or system libraries are also extracted.

2) Modeling the well-formedness constraints in the diversity reservoir: We use feature modeling to ensure DPC configurations are valid before the browsing platforms are assembled or reconfigured. This helps establish the restrictions and conflicts among the different components in the diversity reservoir. The attributed feature model defines the valid configurations, i.e. configurations that can fundamentally run. We provide an extract of the feature model in Figure 4. A DPC configuration is composed of 4 mandatory features: an OS, a browser, plugins and fonts. It must be noted that some features in this model have attributes that specify the feature's characteristics and have domains that define possible values. For example, the attribute Type in the feature Plugin specifies that a plugin is either of type Netscape Plugin API (NPAPI) or Pepper Plugin API (PPAPI). Relations in the feature model and cross-tree constraints (see bottom of Figure 4) specify the set of rules that must be fulfilled for a DPC configuration to be valid and "runnable". For example, the first constraint states that a browser with a 64 bit architecture implies a 64 bit OS.

C. Discussion and further development

It can be argued that using virtual machines to run browsers is costly. However, current computers can easily run multiple VMs simultaneously. Many developers already use multiple VMs to target different platforms. VMs allow Blink to target multiple platforms and architectures, and to reconfigure the OS, all important discriminators in fingerprints. Moreover, the use of VMs presents beneficial side-effects: it provides very strong sandboxing for all web activity, including Firefox, which does not have a native sandbox. In our implementation, snapshots are used to return VMs to known safe-states, removing cookies and other browsing artifacts. In the end it's a tradeoff between performance, comfort and better privacy.

On the technical side, the current implementation of Blink only assembles and reconfigures Linux platforms. But, given the technical choices made, the implementation can be extended to OS X and Windows. We plan to increase the diversity reservoir by adding more browsers and OSs.

Users of our approach could potentially be spotted as having "strange" fingerprints. To mitigate this effect, we have deployed the https://amiunique.org/ web site to collect real fingerprints. So far, we have collected more than 63000 fingerprints. We observed that fingerprints rarely have more than 20 plugins and that the number of fonts range from 50 to 550. We derived two normal distributions from the data we collected and use them to set the number of fonts and plugins that we add to each DPC configuration. This way, we do not end up with configurations that would never be observed in the wild, improving the chances that Blink users do not stand out. In future work we want to exploit the insights from real fingerprints to bias the assembly of DPC configurations.

V. EMPIRICAL ENQUIRY OF MULTI-LEVEL

RECONFIGURATION

We present a series of experiments to validate the effectiveness of multi-level platform reconfigurations at breaking fingerprint stability over time.

A. Research questions

The experiments aim at answering the following questions. RQ1. How diverse is the sequence of fingerprints exhibited by the assembled platforms? This question evaluates the ability of our approach at using the diversity reservoir to assemble series of platforms that exhibit different fingerprints. We measure the dissimilarity between the fingerprints exhibited by each consecutive pair of platforms.

RQ2. How diverse are the platforms in the eyes of actual fingerprinters? This question evaluates the ability of our approach to deceive commercial fingerprinting scripts.

B. Experiment setup 1) Our fingerprinting script: All experiments require collecting and analyzing the browser fingerprints exhibited by the assembled browsing platforms. We developed a fingerprinting script inspired by Panopticlick [START_REF] Eckersley | How unique is your web browser?[END_REF], with some improvements to gather more data via JavaScript and Flash. It works by gathering data through HTTP headers and JavaScript attributes, and it uses Flash to gain access to unique attributes in the ActionScript API. We collect the attributes listed in Table I.

2) Third-party fingerprinting scripts: BlueCava is a company that offers websites to "recognize devices (i.e., computers, mobile phones & tablets)" for advertising purposes 9 . One tool in their arsenal is a script that uses JavaScript and Flash to fingerprint devices. BlueCava provides a page 10 for users to opt-out of tracking that shows the identifier associated with your device. We collect these identifiers for our assembled browsing platforms. It should be noted that the identification algorithm is on the server side and is unknown to us. Acar et al. [8] discovered a canvas fingerprinting script on the AddThis website that has since been removed 11 . The script works by sending the browser some text to render using the HTML canvas element. The text is converted into an image that is sent back to the server. Pixel variations in the image indicate differences in hardware and software used in rendering, opening the door to fingerprinting. We use the getDataUrl() function of the canvas element to get a URL representation of the image that allows easy comparisons.

3) Dataset: An original platform represents the user's browsing platform as it exists in the host operating system. The content of this platform can have a strong impact on Blink's ability at producing diverse platforms, since we import the user's fonts and plugins when assembling a DPC configuration. In essence, the plugins and fonts of the user's platform are included as essential components in the assembled platforms.

We test Blink's effectiveness using 25 original platforms. Each original platform has from 1 to 25 plugins, and from 20 to 520 fonts. The diversity reservoir for our experiments is: 4 Virtual machines (Fedora 20 32/64 bits, Ubuntu 14.04 32/64 bits); 2762 fonts; 39 browser plugins; 6 browsers, including 3 versions of Firefox: 28.0 (stable), 29.0 (beta), 30.0 (aurora), and 3 versions of Chrome: 34 (stable), 35 (beta), 36 (unstable).

4) Experimental protocol: For each of the 25 original platforms, we assemble 2 sequences of 100 platforms, providing a total of 5000. For every assembled platform, we collect the exhibited fingerprint using our script, and we collect the BlueCava and AddThis identifiers using their commercial fingerprinting scripts.

C. Results

RQ1. How diverse is the sequence of fingerprints exhibited by the assembled platforms? 9 http://bluecava.com/privacy-policy/ 10 http://bluecava.com/opt-out/ 11 https://www.addthis.com/blog/2014/07/23/the-facts-about-our-use-of-acanvas-element-in-our-recent-rd-test/ This question aims at validating that the browsing platforms we assemble exhibit different fingerprints over time. We estimate this by checking that two consecutive platforms exhibit fingerprints that are dissimilar. Thus, for each original platform, we collect the sequence of fingerprint dissimilarities by pairs of consecutive platforms: dissim seq = (D(F P i , F P i+1 )) 1≤i≤99

For each of the 25 original platforms, we collect two sequences of dissimilarity values, which correspond to the 2 sequences of 100 assembled platforms. Figure 5 displays the distribution of dissimilarities in both dissim seq for each original platform, in Leery mode. Figure 6 displays them in Coffee break mode. The X-axis in the figures correspond to the ID of the original platform, and the Y-axis represents the distribution of dissimilarities between pairs of consecutive platforms. The red line indicates the mean dissimilarity value among the 5000 collected fingerprints.

Regarding the Leery strategy, Figure 5 shows that Blink is successful at assembling successive platforms that exhibit very dissimilar fingerprints, with results up to 0.77. Blink can also assemble platforms that are very similar, with some pairs of successive platforms having dissimilarity values as low as 0.01. Since we have a relatively small pool of operating systems and browsers, it is likely that the OS or browser was the same from one configuration to the next. So, depending on randomization, consecutive fingerprints can be very similar or very dissimilar. Yet, despite frequent, large variations in dissimilarities, mean values are high thanks to our large pool of fonts and plugins.

When comparing Figures 5 and6, the most noticeable differences are the ranges of dissimilarity. In Leery mode, dissimilarity varies between 0.01 and 0.77, while in Coffee break mode dissimilarity varies between 0.08 and 0.36. This shows the benefits of switching the operating system and browser. The mean dissimilarity values in Leery mode are more than twice as high as the ones in Coffee break mode.

Dissimilarity slowly declines as the numbers of fonts and plugins grow with each original platform. This trend occurs with both reconfiguration strategies and can be explained by the fact that the assembled platforms start to share a larger set of common plugins and fonts, lowering the overall dissimilarity score for both attributes. In the end, even if the dissimilarity is lower if we import a lot of fonts and plugins from the user's system, Blink still produces highly dissimilar configurations with an average above 0.4 in Leery mode.

We conclude from these observations that Blink generates configurations that are truly different from one another. It corresponds to our objective of breaking the stability of fingerprints over time, and shows its effectiveness in blocking the ability of fingerprinters to track users. Variations in Blink's effectiveness are due to the richness of the original platforms and on the size of the diversity reservoir.

RQ2. How diverse are the platforms in the eyes of actual fingerprinters? To answer this, we collected fingerprint identifiers from BlueCava and AddThis for each assembled platform. When these scripts assign the same identifier to two platforms, it means they consider them to be the same.

1) BlueCava browser fingerprinting script: In our tests more than 99% of the identifiers we collected were different (we had similar results for both Leery and Coffee break modes). BlueCava's script is not able to detect that the assembled platforms are from the same user, in part due to BlueCava taking into account even the slightest differences in a fingerprint. This shows that Blink is effective against unique identifiers, and confirms that Blink can deceive BlueCava, even when fingerprint diversity is low.

2) AddThis canvas fingerprinting script: From the 5000 assembled platforms, we obtained 181 different identifiers in Leery mode and 34 in Coffee break mode using the AddThis script. Blink performs relatively well despite the fact that canvas fingerprinting targets the GPU and low-level drivers. We can also see that Leery is 5 times more effective than Coffee break because the OS and browser change. Currently the DPC does not include graphical components (e.g., GPU drivers) or GPU/HTML5 specific configurations, but we plan to explore this in the future.

D. Threats to validity

To our knowledge, characterizing the impact of moving target defenses on security is an open challenge [START_REF] Christodorescu | End-to-end software diversification of internet services[END_REF]. Still, this section provided empirical evidence of the effectiveness of Blink's behavior with respect to fingerprinting. We now summarize the threats to the validity of our findings.

While no established metric exists to evaluate the effectiveness of fingerprinting countermeasures, we defined our own dissimilarity metric. This is a construct threat because the metric might not properly reflect the ability of fingerprinters to decide if a fingerprint is from a distinct platform. To mitigate this threat, we based fingerprint attribute weights on the observations from Eckersley's extensive study [START_REF] Eckersley | How unique is your web browser?[END_REF]. We also collected identifiers from third-party commercial fingerprinting scripts.

The external validity lies in the ability to generalize our observations. We evaluated Blink's effect on 25 initial situations, with a pool of 6 browsers and 4 operating systems, all running Linux platforms. Starting from these situations, Blink is able to assemble platforms that exhibit very different fingerprints. Yet, we do not know how Blink behaves in other situations (e.g., users that have a very large set of essential fonts). We are exploring a new domain (mitigating fingerprintbased tracking) and further quantitative and usability studies are needed to establish a comprehensive understanding of moving target approaches in this domain.

Internal validity very much depends on the correct implementation of Blink, as well as both the fingerprinting scripts and the metrics. We mitigated this risk through thorough testing campaigns, and thousands of runs to tune Blink. Yet, there might be bugs that influence our results. We hope that they only change marginal quantitative things, and not the qualitative essence of our findings.

VI. CONCLUSION

This work explores the opportunity of exploiting automatic, multi-level reconfiguration and the natural diversity of software components in order to create a moving target defense against browser fingerprint tracking. We leverage virtualization and modular architectures at various levels (OS and browser) to modify, over time, the parts of a user platform that are the most identifying in a fingerprint. This completely new approach allows users to exhibit a diversity of fingerprints without lying. We also contribute a novel dissimilarity metric to evaluate the differences between two fingerprints and estimate the likelihood they belong to the same user. A tool named Blink has been developed to assess the effectiveness of this approach. Our empirical results, based on the analysis of 5000 fingerprints exhibited by randomly assembled configurations, show that Blink generates very dissimilar configurations and can deceive BlueCava, a commercial fingerprinting script.

We plan to increase the size of our diversity reservoir to generate even more diverse configurations. We have also deployed the https://amiunique.org/ website to inform users about fingerprinting and to collect a large number of real fingerprints, which will help us improve Blink. The dissimilarity between the plugins in two fingerprints is computed as follows:

d(attr 2 (F P 1 , F P 2 )) = F 1 + F 2 -0.75 × F 3 -F 4 + 1 2
The dissimilarity for this attribute ranges from 0 to 1 with greater values representing an increasing dissimilarity between the two lists of plugins.

[Attribute 3] Fonts: The dissimilarity between two lists of fonts is the proportion of fonts that are only in one fingerprint, minus the proportion of fonts that are in both. This term is 0 if both lists are identical and 1 if they are completely different.

Let us consider LF (F P 1 ), the set of fonts in fingerprint 1 and LF (F P 2 ), the set of fonts in fingerprint 2. The total number of fonts in both lists is computed as follows (we count the fonts that appear in both lists only once): d(attr X (F P 1 ), attr X (F P 2 )) = 0 attr X (F P 1 ) = attr X (F P 2 ) 1 attr X (F P 1 ) = attr X (F P 2 )

Fig. 1 .

 1 Fig. 1. User platform elements involved in web browsing and exhibited in the browser fingerprint.

Fig. 2 .

 2 Fig. 2. Evolution of the user's platform over time.

Fig. 4 .

 4 Fig. 4. An extract of the feature model used for assembling valid DPC configurations.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Dissimilarity between consecutive platforms (Leery mode)

F 1 =F 3 =

 13 |(LP (F P 1 ) \ (LP =name,=ver ∪ LP =name, =ver ))| F U F 2 = |(LP (F P 2 ) \ (LP =name,=ver ∪ LP =name, =ver ))| F U We get the proportion of common plugins: |LP =name, =ver | F U F 4 = |LP =name,=ver | F U

1 + F 2 -F 3 + 1 2 [

 122 F U = |(LF (F P 1 ) \ (LF (F P 1 ) ∩ LF (F P 2 ))) ∪ LF (F P 2 )| The proportion of fonts unique to F P 1 is:F 1 = |(LF (F P 1 ) \ (LF (F P 1 ) ∩ LF (F P 2 )))| F UThe proportion of fonts unique to F P 2 is:F 2 = |(LF (F P 2 ) \ (LF (F P 1 ) ∩ LF (F P 2 )))| F UThe proportion of common fonts is:F 3 = |(LF (F P 1 ) ∩ LF (F P 2 ))| F UThe dissimilarity between the fonts in two fingerprints is:d(attr 3 (F P 1 , F P 2 )) =F Attributes 4 -8] Accept Header, Screen resolution, Timezone, DOM storage, Cookies: These attributes can be compared without additional processing. The dissimilarity between these attributes is:

https://github.com/DIVERSIFY-project/blink

https://panopticlick.eff.org/

https://www.google.com/intl/en/policies/privacy/#infocollect

https://twitter.com/privacy

http://noscript.net/

https://www.ghostery.com/

https://www.eff.org/privacybadger

http://blog.chromium.org/2014/11/the-final-countdown-for-npapi.html

ACKNOWLEDGMENT

We thank Nick Nikiforakis for his insightful discussions and for suggesting the Coffee break strategy, as well as Gildas Avoine and Nataliia Bielova for their expert feedback on this paper. This work is partially supported by the EU FP7-ICT-2011-9 No. 600654 DIVERSIFY project.

APPENDIX B FINGERPRINT DISSIMILARITY

This annex provides the strategy to determine the dissimilarity between the eight fingerprint attributes.

[Attribute 1] User agent: We decompose the user agent attribute into two categories: data related to the browser and its version, and data related to the architecture of the device (32 or 64 bits).

We grant equal weight to both these categories. The resulting dissimilarity between the user agents in two fingerprints is computed as follows:

d(attr 1 (F P 1 , F P 2 )) = 0.5 × F br + 0.5 × F archi [Attribute 2] Plugins: Let us consider LP (F P 1 ), the set of plugins in fingerprint 1 and LP (F P 2 ), the set of plugins in fingerprint 2. Plugins are stored in a list of tuples where the first element of each tuple is the name of the plugin and the second its version. We define two different sets for plugins that are common to both fingerprints: one where plugins have an identical version (LP =name,=ver ) and one where plugins have different versions (LP =name, =ver ). P ∈ LP =name,=ver if ∃P 1 ∈ LP (F P 1 ) ∧ ∃P 2 ∈ LP (F P 2 ), P 1 .name = P 1 .name ∧ P 1 .ver = P 2 .ver ∧ P.name = P 1 .name = P 2 .name P ∈ LP =name, =ver if ∃P 1 ∈ LP (F P 1 ) ∧ ∃P 2 ∈ LP (F P 2 ), P 1 .name = P 1 .name ∧ P 1 .ver = P 2 .ver ∧ P.name = P 1 .name = P 2 .name

The total number of plugins in both lists is computed as follows (we count the plugins that appear in both lists once):

F U = |(LP (F P 1 ) \ (LP (F P 1 ) ∩ LP (F P 2 ))) ∪ LP (F P 2 )| We calculate the proportion of plugins that are unique to F P 1 and to F P 2 as:


Viet-Hoa Nguyen
email: viet-h.nguyen@irisa.fr

Olivier Berder
email: olivier.berder@irisa.fr

Charlotte Langlais
email: charlotte.langlais@telecom-bretagne.eu

Baptiste Vrigneau
email: baptiste.vrigneau@irisa.fr

Distributed Minimum Euclidean Distance based Precoding for Wireless Sensor Network

Among various cooperative techniques aiming to reduce power consumption for Wireless Sensor Network (WSN), we present a new approach, named distributed max-dmin precoding (DMP). This protocol is based on the deployment of a virtual 2 × 2 max-dmin precoding over one source, one forwarding relay, both equipped with one antenna and a destination involving 2 antennas. In this context, two kinds of relaying, amplify and forward or decode and forward protocols, are investigated. The performance evaluation in terms of Bit-Error-Rate (BER) and energy efficiency will be compared with non cooperative techniques (SISO, SIMO) and the distributed space time block code (STBC) scheme. Our investigations show that the DMP takes the advantage in terms of energy efficiency from medium transmission distances.

I. INTRODUCTION

The important achievements in recent years allow wireless sensor networks (WSN) to be applied more widely in real life. The demand of a flexible network leads to the use of low-cost, low-power, small size wireless sensor nodes with the embedded batteries. An important objective in WSN is how to maintain long-term operations of the network without the interruption caused by the battery replacement. Aiming to design an energy efficient transmission scheme, MIMO (multiple-input multiple-output) technique can be proposed with the benefits from a spatial diversity gain. However, due to the limited size, MIMO technique cannot be deployed by the classical manner in WSN. The idea is that the sensor nodes can share their antennas to create a virtual MIMO system, called cooperative communication.

A well-known cooperative scheme has been proposed by Laneman with a signal forwarding through the relay, called a cooperative relay [START_REF] Laneman | Energy-efficient antenna sharing and relaying for wireless networks[END_REF]. In other studies, the authors apply spacetime block coding via the deployment of virtual MIMO system by using the relay at both transmission and reception sides [2] [3]. Owning the diversity gain, these cooperative schemes provide significant improvement in transmission power consumption compared to single input single output (SISO) system or maximum ratio combining (MRC) over single input multiple output (SIMO) system. On the other hand, they consume more energy for the electrical circuit and data exchanging. At small distances, when the circuit consumption dominates the total power consumption, a non cooperative protocol like SISO or SIMO provides better energy efficiency than the cooperative ones. Conversely, the cooperative schemes take the advantage in the larger distances.

Thanks to multiple transmit and receive antennas, the MIMO precoding involves a closed-loop spatial multiplexing, which exploits the Channel State Information at Transmitter (CSIT) to deal with the impairments of the propagation channel. In point-to-point MIMO, various precoding designs adapted to different criteria, such as maximizing the output capacity, maximizing the received signal-to-noise ratio, maximizing the minimum singular value of the channel matrix, have been studied [START_REF] Stoica | Maximum-SNR spatial-temporal formatting designs for MIMO channels[END_REF] [START_REF] Sampath | Generalized linear precoder and decoder design for MIMO channels using the weighted MMSE criterion[END_REF]. In [START_REF] Collin | Optimal minimum distance-based precoder for MIMO spatial multiplexing systems[END_REF] [START_REF] Ngo | Minimum distance based precoder for MIMO-OFDM systems using a 16-qam modulation[END_REF], the authors have proposed the max-d min precoder, which maximizes the minimum Euclidean distance between the received vectors. In terms of BER, this precoder outperforms the others at the expense of a more complex structure. Moreover, with respect to orthogonal space-time block codes, this precoder allows for higher spectral efficiency thanks to spatial multiplexing.

The idea to deploy the MIMO precoding via the cooperative manner -called distributed precoding -is very promising in wireless communication. Although showing the potential, the study on the distributed precoding are still limited, especially in WSN. Most of existing distributed precoders are dedicated to cellular networks, and particularly the downlink via the coordination of multiple base stations. Some interesting structures can be cited such as weight sum rate maximization, leakage projected dirty paper coding, layered virtual SINR (signal to interference plus noise ratio) maximization [START_REF] Ho | Distributed precoding for network MIMO[END_REF] [9] [START_REF] Zakhour | Distributed multicell-MISO precoding using the layered virtual SINR framework[END_REF]. Unlike WSN, in the cellular network, the energy efficiency constraint is no longer important, instead the data rate is focused. Another fundamental difference is the insignificant space limitation at the base station in the downlink, where multiple antennas can be easily deployed. The base station collaboration then enhances the spectral efficiency.

The distributed precoding in WSN exists mostly in the form of distributed beamforming [11] [12]. This distributed scheme shows an impressive SNR gain, but always suffers from the synchronization problem. Moreover, the survey on the energy efficiency issues have not been carefully investigated for this distributed scheme. The authors in [START_REF] Madi | Cooperative MIMO precoders for energy-efficient transmission in wireless sensor network[END_REF] have presented also a distributed approach for WSN in using the max-d min precoder and P-OSM (precoding for orthogonalized spatial multiplexing). But the investigations on the cooperation and relaying are very sparing and not clear. There are also the lack of a spectral-efficient representation due to the use of MIMO precoding (compared to the other cooperative schemes).

Thanks to the outstanding BER performance of max-d min precoder, we introduce the distributed max-d min precoding as a cooperative scheme in WSN. Different to the study in [START_REF] Madi | Cooperative MIMO precoders for energy-efficient transmission in wireless sensor network[END_REF], herein we propose to investigate different protocols using a cooperating node (Decode-Forward, Amplify-Forward).

Regarding on the local data exchange of a cooperative scheme, we propose the transmission of a part of the precoded signal between the source and cooperative node aiming to enhance significantly the spectral efficiency. The energy efficiency is also studied with a global energy model containing the circuit and transmission consumption. The rest of this paper is organized as follows: In Section II, we introduce the system description of our cooperative scheme and the principle of max-d min precoding is described. In Section III, we propose the different protocols for relaying and local data exchanging. The power consumption model is investigated in the context of WSN in Section IV. The simulation results of our schemes are presented in Section V. Section VI finally concludes the paper.

II. SYSTEM MODEL

We consider a simplified network, described in Figure 1, involving three nodes: a source, a cooperative node and a destination. The source and the cooperative node are sensor nodes, equipped with a single antenna and constrained to low energy consumption. The destination is supposed to be an access point (AP) without power constraint and neither stringent complexity constraint, compared to the sensor nodes. By allowing two antennas at the access point, the network is equivalent to a virtual 2 × 2 MIMO system. An errorfree and delay-free feedback link provides the channel state information at the transmitter (CSIT). Thanks to this CSIT, MIMO precoding techniques can be applied to the virtual MIMO system to deal with the channel impairments such as fading, antenna correlation, shadowing. Among various criteria, we propose to apply the max-d min precoder due to its significant advantage in reducing BER. The max-d min precoding will be deployed via the cooperative protocol by two transmission phases:

• Local data exchange: the source node shares its data with the cooperative node via the SISO channel h. • Precoding transmission: thanks to the spatial multiplexing properties of the precoder, the source and the cooperative node transmit the precoded signals simultaneously to the access point via the virtual MIMO channel matrix H. To limit energy consumption at the sensor nodes, the precoding matrix F can be computed at the destination. Hence, the feedback link sends back the precoding matrix instead of the CSIT. Recently, a quantized max-d min precoding based on limited codebook has been proposed [14] [13]. In this case, the low rate feedback link transmits the index of the precoding matrix that has been computed by the destination node.

A. Max-d min precoder

In this subsection, we describe the design of a max-d min precoder in a classic MIMO system. The transmission model

y = GHFs + Gn = G d H v F d s + G d n v , ( 1
)
where y is the received vector, s is the transmitted vector of the modulated symbols, belonging to the QPSK constellation; G, H, F denote the decoder matrix, the MIMO channel matrix, the precoder matrix, respectively; and n is an additive white Gaussian noise (AWGN) vector. The virtual channel transformation allows to present the virtual channel in diagonal form

H v = G v HF v = diag(σ 1 , σ 2 )
. σ 1 , σ 2 are the channel singular values in decreasing order, n v is the virtual noise.

Since the maximum likelihood detector is used at the receiver, the decoder matrix G d has no impact on the performance, then it is assumed G d = I 2 . The max-d min precoder F d maximizes the minimum Euclidean distance between signal points at the reception side [START_REF] Collin | Optimal minimum distance-based precoder for MIMO spatial multiplexing systems[END_REF]:

F d = arg max( min s k ,s l ∈S,s k =s l ||H v F d (s k -s l )||), (2)
where s k , s l are two different transmitted vectors in the constellation S. The max-d min precoding solution depends on the modulation level, the number of antennas as well as channel properties [6] [7]. Let γ = atan( σ2 σ1 ) define the channel angle. For the 2 × 2 MIMO system with 2 QPSK multiplexed data streams, the max-d min precoding matrix is given by [START_REF] Collin | Optimal minimum distance-based precoder for MIMO spatial multiplexing systems[END_REF] • for 0 ≤ γ ≤ γ 0 ≈ 17.28 o

F d = F r1 = 3+ √ 3 6 3- √ 3 6 e i π 12 0 0 (3)
• for γ 0 < γ ≤ 45 o F d = F octa = 1 2 cosψ 0 0 sinψ 1 e i π 4 -1 e i π 4 (4)
where ψ = atan(

√ 2-1 tanγ ). The precoding matrix is then rewrit- ten as F = F v F d under the power constraint trace(FF * ) = 1. With E[ss * ] = E, then E[trace((Fs)(Fs) * )] = E.
It means the total energy in the precoding system for transmitting 2 symbols is only E, whereas in a SISO system this value is 2E (E[trace(ss * )] = 2E). Therefore, to make a fair comparison in energy consumption, the transmit signal in the precoding system will be x = √ 2Fs.

B. Power allocation in cooperative systems

In order to investigate the effects of the relay position in the cooperative schemes, we take into account the path loss explicitly in the transmission model. The distances S→D, S→C, C→D (Figure 1) are denoted by d SD , d SC , d CD , respectively. Then the relative power gain of S → C and C → D links, with respect to S → D link, are given by

G SC = (d SD /d SC ) K , G CD = (d SD /d CD ) K [15]
, where K is a path loss exponent, varying from 1.6 to 6 in indoor wireless channel. To have a fair comparison between various schemes, we assume the overall energy for each modulated symbol used in both local transmission (E L ) and precoding transmission (

E D ) is E. It means E L = βE, E D = (1 -β)E,
where β denotes the power allocation parameter.

III. DISTRIBUTED max-d min PRECODING

In this section, we propose two protocols, based on amplifyand-forward and decode-and-forward strategies, that distribute the max-d min precoding over the source node and the cooperative node.

A. Decode and Forward relaying (DMP-DF)

The Decode and Forward scheme transmits 2 symbols within 3 time-slots. In the first and second time-slots, s 0 , s 1 are sent symbol by symbol through a SISO channel, represented by h. Hence, the cooperative node receives

y c = h E L G SC [s 0 s 1 ] T + n c , (5)
where n c denotes the AWGN noise vector at the cooperative node. The received signal is then decoded to s 0 and s 1 . The precoding signal is built as follows

F 11 s 0 + F 12 s 1 at the source node, F 21 s 0 + F 22 s 1 at the cooperative node, (6)
where F ij | i,j=1,2 are the elements of procoding matrix F. In the third time-slot, both nodes transmit this signal simultaneously. Then, the destination receives

y = GH √ 2E D (F 11 s 0 + F 12 s 1 ) √ 2E D G CD (F 21 s 0 + F 22 s 1 ) + Gn, (7)
and applies a Maximum Likelihood detection. The precoding matrix F is designed only according to the channel H: F = max-d min (H) [7] [START_REF] Collin | Optimal minimum distance-based precoder for MIMO spatial multiplexing systems[END_REF]. There is no need to estimate the SISO channel h at the destination.

B. Amplify and Forward relaying (DMP-AF)

Instead of decoding the signal from the source node, the cooperative node amplifies it with a designed factor and forwards it to the destination. In this strategy, both channels h and H have a significant influence on the system performance. Therefore, we propose two schemes with different uses of matrix H and h for the design of the precoding matrix and the amplifying factor at the cooperative node. The first scheme, called factor multiplying, constructs the matrix F based on the channel H. The effect of channel h will be taken into account at the cooperative node by the amplifying factor. The second scheme, called channel customizing, transforms equivalently the received signal, bringing out a customized channel matrix containing both H and h. This scheme assumes the knowledge of h and H at the destination.

Regarding the local data exchange between the source and the cooperative node, two configurations are carried out: 1) the transmission of the non precoded symbols on orthogonal channels, typically thanks to TDMA (Time division multiple access), 2) the transmission of a part of the precoded signal, i.e. a linear combination of the symbols. In this transmission phase, the signal from source node is not useful at the destination.

1) Factor multiplying: We design the precoding matrix according to the channel matrix H (F = max-d min (H)) and reduce the effect of channel h by multiplying the received signal with an amplifying factor.

• Configuration 1: Local successive transmission (LST): s 0 and s 1 will be sent one by one to the cooperative node, according to TDMA. The cooperative node receives

y c = y c0 y c1 = h √ E L G SC s 0 + n c0 h √ E L G SC s 1 + n c1 . ( 8
)
At the cooperative node, the received signal is normalized by its energy, then precoded, and forwarded to the destination. At the same time, the source node also transmits its precoded signal to the destination. Then the received vector at the destination is written as

y = GH √ 2E D (F 11 s 0 + F 12 s 1 ) g 1 (F 21 y c0 + F 22 y c1 ) + Gn, (9)
where amplifying factor g 1 is chosen as [START_REF] Laneman | Energy-efficient antenna sharing and relaying for wireless networks[END_REF]

g 1 = h * |h| 2E D G CD E L G SC |h| 2 + N nc , (10)
where N nc is the noise variance at the cooperative node. The factor g 1 is aimed to reduce the effect of the AWGN noise, the channel h [1] and prevent the power saturation at the cooperative node.

• Configuration 2: Local precoded transmission (LPT):

Instead of transmitting symbol by symbol in the local exchange phase, the source sends s 0 and s 1 simultaneously, thanks to the linear combination s pre = F 21 s 0 +F 22 s 1 , to the cooperative node. Then the cooperative node receives

y cpre = h 2E L G SC s pre + n c , (11)
The remaining steps are similar to the local orthogonal transmission. The destination then receives

y = GH √ 2E D (F 11 s 0 + F 12 s 1 ) g 2 y cpre + Gn, (12)
where

g 2 = h * |h| 2E D G CD 2E L G SC |h| 2 +Nn c .
2) Channel customizing: In this scheme, we take the channel h into account by a customized channel via an equivalent transformation of the received constellation. Like in the factor multiplying scheme, two configurations will be studied regarding the local data exchange. The received signals during the precoding transmission for the two configurations are as follows.

• Configuration 1: The equation ( 9) is rewritten as

y = GH   √ 2E D 0 0 √ 2E D G CD 1+ N 0 E L G SC |h| 2   Fs+ + H 12 (g 1 F 21 n c0 + g 1 F 22 n c1 ) H 22 (g 1 F 21 n c0 + g 1 F 22 n c1 ) + n v = 2E D GH 1 0 0 w 1 Fs + n c + n v , (13)
where

w 1 = G CD 1+ N 0 E L G SC |h| 2 , n c = H 12 (g 1 F 21 n c0 + g 1 F 22 n c1 ) H 22 (g 1 F 21 n c0 + g 1 F 22 n c1
) .

• Configuration 2: Similarly, equation ( 12) is rewritten as

y = 2E D GH 1 0 0 w 2 Fs + H 12 g 2 n c H 22 g 2 n c + n v , (14)
where

w 2 = G CD 1+ N 0 2E L G SC |h| 2 .
Therefore, the precoding matrix is designed based on a customized channel matrix involving the contribution of both H and h such as

F = max-d min H 1 0 0 w i , i = 1, 2. (15)
Regarding the complexity of the signal processing at the sensor nodes, thank to a limited feedback the sensor nodes are absolved from the computation. Therefore, there aren't any complexity difference between our distributed precoding and the cooperative STBC scheme. Like in other cooperative system, the main problem in our system is the desynchronization that may seriously affect the system performance [START_REF] Nguyen | Impact of transmission synchronization error and cooperative reception techniques on the performance of cooperative mimo systems[END_REF].

IV. ENERGY MODEL

The total energy on a wireless system consists of two elements: transmission energy and circuit consumption energy. For a same BER target, a cooperative scheme requires less transmission energy; reversely it demands more power for cooperative data exchange and circuit consumption on cooperative nodes. Certainly, for short distances, the cooperative scheme will not offer a better energy efficiency than non cooperative transmission. For longer distances, where the transmission consumption dominates the total energy, we expect that cooperative systems provide high energy efficiency. In this section we describe the energy model used to estimate the energy consumption of both cooperative and non cooperative systems.

A. Circuit energy consumption model

In a wireless system, both the transmitter and receiver possess radio frequency blocks such as filter, power amplifier, digital-to-analog converter, mixer... [START_REF] Cui | Energy-efficiency of MIMO and cooperative MIMO techniques in sensor networks[END_REF]. The circuit power consumption for each transmitter and receiver then is given by P T x = P DAC + P mix + P f ilt + P syn ,

P Rx = P LN A + P mix + P IF A + P f ilr + P ADC + P syn , (17

)
where P DAC , P mix , P f ilt , P syn , P LN A , P IF A , P f ilr , P ADC denote respectively the power of digital-analog converter, mixer, filter at transmitter, synthesizer, low noise amplifier, intermediate frequency amplifier, filter at receiver and analog-digital converter. The amplifier power P pa for the emission relates directly to the transmission power P trans : P pa = (1 + α)P trans , where α = ξ η -1 with η is the drain efficiency of the RF power amplifier and ξ is the Peakto-Average Ratio (PAR) which depends on the modulation scheme and the associated constellation size [START_REF] Cui | Energy-efficiency of MIMO and cooperative MIMO techniques in sensor networks[END_REF].

B. Transmission power consumption

We suppose the radio signal is impaired by a path loss following a K-law. The required transmission power therefore is given by

P trans (d) = Êb R b × (4πd) K G t G r λ 2 M l N f , ( 18
)
where d denotes the transmission distance, Êb denotes the needed energy per bit for a BER target, R b is the bit rate, G t and G r are the antenna gains of transmission and reception side, respectively. λ is the carrier wave length, M l is the link margin, N f is the receiver noise figure defined as N f = M n /N 0 with N 0 = -174 dBm/Hz single side thermal noise Power Spectral Density (PSD) and M n denotes the PSD of the total effective noise at receiver input [START_REF] Cui | Energy-efficiency of MIMO and cooperative MIMO techniques in sensor networks[END_REF].

C. Spectral efficiency and bit rate

The total spectral efficiency with QPSK modulation is shown in the Table I for the different schemes, cooperative and non cooperative. The bit rate in the wireless system relates directly to the spectral efficiency and the bandwidth. In addition, the bit rate R b of each transmission phase affects the total energy consumption as follows

E total = P c L + P pa L R b L + P c D + P pa D R b D , (19)
where P c L , P pa L and P c D , P pa D denote the total circuit power consumption and amplifier power for local data exchange phase and precoding transmission phase, respectively. R b L and R b D are the bit rates of the local data exchange and the precoding transmission respectively. Normally, the bit rate in a precoding system will be twice the one of a SISO system because it transmits 2 symbols in 1 time-slot instead of only 1 symbol. However, the DMP involves two phases with different bit rates according to the considered scheme.

In the local exchange phase, the Distributed Alamouti, DMP-DF, and DMP-AF-LST schemes achieve the same spectral efficiency as the SISO transmission. Whereas, with 2 modulated symbols transmitted in a precoded symbol, the DMP-AF-LPT represents twice the bit rate of the others. In the second phase, corresponding to the precoding transmission, all DMP schemes transmit the signal twice as fast as the non cooperative schemes (SISO and SIMO), while the Distributed Alamouti scheme achieves the same bit rate as the SISO scheme.

V. SIMULATION RESULTS

We evaluate the schemes proposed in Section III by Monte Carlo simulations. In our system, we use the QPSK modulation, the channels h and H are Rayleigh fading channels. We transmit 150 000 frames, each frame contains 100 bits. The channel is assumed to be stable for the transmission time of one frame. The distance d SC is supposed to be 5% of d SD .

In the power allocation problem, we need to minimize the BER with respect to power allocation parameter β:

min β BER(β) subject to E L + E D = const . (20)
The BER approximation is not a simple issue in the max-d min precoding system and especially complicated in the distributed max-d min precoding system. In order to allocate the power, we are currently deriving theoretically a close-form of BER in our distributed scheme. Unfortunately, this work is really a difficult problem. Since the BER approximation form is not available, the power allocation parameter β will be found by a numerical search for the optimal power allocation (OPA). For the equal power allocation (EPA), β = 0.5. For QPSK modulation, E b /N 0 = (E/2)/N 0 . The BER performance comparison between various schemes is given in Figure 2. The Distributed Alamouti scheme is carried out by the Alamouti code in the virtual 2 × 2 MIMO system [START_REF] Nguyen | Cooperative MIMO schemes optimal selection for wireless sensor networks[END_REF]. This scheme consumes 4 time-slots for transmitting 2 symbols s 0 , s 1 . The DMP-DF proposes a significant transmission power reduction compared to the SISO transmission and the MRC 1 × 2, for the same BER target. At the BER 10 -3 , there is a loss of 1dB in the DMP-DF compared to the distributed Alamouti. We recall that they operate at different spectral efficiencies (see Table I). Figure 2 also shows the advantage of the optimal power allocation on the performance of DMP, the OPA always provides a 3 dB gain compared to the EPA scheme. In Figure 3, the DMP-DF and DMP-AF schemes propose an equivalent performance. In terms of BER, even though saving 1 time slot, the DMP-AF-LPT schemes still has same performance as DMP-AF-LST. Besides, there is no difference between the DMP-AF with amplifying factor and the DMP-AF with customizing channel in considering the BER. Anyhow, our final objective is the energy optimization. Thus a complete investigation of all power aspects of a wireless system must be studied to have a comprehensive view on the energy performance. We consider the energy model with the parameters given in Table II. Particularly in our system, the access point is a powerful computer plugged directly to the power source, therefore its power constraint is not taken into account. The required BER at the destination is supposed to be 10 -5 and the path loss exponent is assumed to be 2.6, for all schemes. Figure 4 shows the total energy consumption per bit for different schemes versus distances from 1 to 27 meters. There is no difference between the DMP-AF-factor multiplying and DMP-AF-channel customizing in term of BER performance and spectral efficiency, consequently we homogenize them in the energy efficiency investigation in Figure 4. By reducing 1 time slot in the local exchange phase, the DMP-AF-LPT (Config.2) always provides an energy-efficient improvement compared to the DMP-DF and DMP-AF-LST (Config.1). Moreover, regarding the distributed Alamouti scheme, even though it performs an impressive BER performance, its low spectral efficiency make it consumes more energy. On the other side, thanks to a good BER performance and higher spectral efficiency, the DMP-AF-LPT always has a best energy efficiency compared to other DMPs. For a small distance, we need only a low transmission power to obtain the targeted performance, thus the circuit consumes most of the energy. Therefore the more simple scheme will outperform the more complicated ones. The MRC 1 × 2 transmission takes the advantage in terms of energy efficiency in this case. In contrast, when the distance increases, the transmission energy dominates the total energy consumption. Hence, optimizing transmission energy is more valuable. If the distance is longer than 16 meters, the DMP-AF-LPT shows the best energy efficiency. The path loss exponent K = 2.6 is just an assumption. The environment can be more intricate: indoor, outdoor, crowded, or anechoic environment. Obviously, in each path loss environment, our distributed scheme responds differently. For an overall view, in Figure 5 we investigate the cross point for different path loss exponents. The Cross point (Figure 4) represents distance at which the DMP-AF-LPT outperforms the others. We observe that when the path loss goes heavier, the DMP takes the advantage for shorter distances. path loss exponent equal to 2.6, the DMP-AF-LPT achieves a lower energy consumption than the MRC 1 × 2 scheme for a distance between the source to access point greater than 16 m. Moreover, when the path loss exponent increases, transmission energy becomes preponderant with respect to circuit energy and the DMP takes the advantage for smaller distances, typically several meters.

DMP MRC

Fig. 1 .

 1 Fig. 1. System model of the non cooperative 2 × 2 precoded system is given by

2 )

 2 MIMO system, QPSK modulation, Rayleigh fading channel SISO MRC 1x2 DMP-DF-EPA DMP-DF-OPA Distributed Alamouti-DF-EPA Distributed Alamouti-DF-OPA Ideal maxdmin precoding 2x2

Fig. 2 . 2 )Fig. 3 .

 223 Fig. 2. BER performance comparison: DMP vs. traditional schemes

Fig. 4 .

 4 Fig. 4. Total energy consumption vs. distance (10 -5 BER)

fc = 2 1 B

 21 , 5GHz P mix = 30.3mW η = 0.35 GtGr = 5dBiP f ilt = P f ilr = 2.5mW B = 10kHz P DAC = 15.4mW Psyn = 50mW N f = 10dB Ts = M l = 40dB P ADC = 6.7mW N 0 2 = -174dBm/Hz P LN A = 20mW

Fig. 5 .

 5 Fig. 5. Best choice point for different path loss exponents VI. CONCLUSION Aiming to a high energy efficiency, we have proposed and investigated the distributed precoding schemes based on max-d min criterion. Two relaying types -Decode and Forward, Amplify and Forward -with different data exchanges (local successive transmission, local precoded transmission) have been defined and studied. Based on an overall energy model, we have derived their energy efficiency in WSN context. With respect to other cooperative techniques, the DMP proposes a high spectral efficiency, typically doubled compared to the Distributed Alamouti one. Whatever the distance, the DMP always achieves a lower energy consumption than the Distributed Alamouti scheme. For a BER equal to 10 -5 and a

ACKNOWLEDGMENT

This work has received a French state support granted to the CominLabs excellence laboratory and managed by the National Research Agency in the "Investing for the Future" program under reference Nb. ANR-10-LABX-07-01.