Ho-Dac-Duy Nguyen

Chi-Dung Phung

Stefano Secci

Benevid Felix

Michele Nogueira
email: michele@inf.ufpr.br

Can MPTCP Secure Internet Communications from Man-in-the-Middle Attacks?

Multipath communications at the Internet scale have been a myth for a long time, with no actual protocol being deployed so that multiple paths could be taken by a same connection on the way towards an Internet destination. Recently, the Multipath Transport Control Protocol (MPTCP) extension was standardized and is undergoing a quick adoption in many use-cases, from mobile to fixed access networks, from data-centers to core networks. Among its major benefits -i.e., reliability thanks to backup path rerouting; throughput increase thanks to link aggregation; and confidentiality thanks to harder capacity to intercept a full connection -the latter has attracted lower attention. How interesting would it be using MPTCP to exploit multiple Internet-scale paths hence decreasing the probability of man-in-the-middle (MITM) attacks is a question to which we try to answer. By analyzing the Autonomous System (AS) level graph, we identify which countries and regions show a higher level of robustness against MITM AS-level attacks, for example due to core cable tapping or route hijacking practices.

I. INTRODUCTION

The Multipath Transport Control Protocol (MPTCP) [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF] is an extension of TCP to concurrently use multiple network paths for a given connection. Among many proposals to support these features at the transport layer, it is considered as the one having attracted the largest interest and deployment [START_REF] Bonaventure | Use Cases and Operational Experience with Multipath TCP[END_REF]. One of the main reason of this success is its incremental deployability adopted in its design, with the required signaling reusing transparently existing TCP option features.

In MPTCP, traffic from a source to a destination in an IP network is routed over multiple 'subflows' via different network interfaces and/or TCP ports at the transmitting and/or receiving end-points. Subflow traffic can then be routed independently in the network segment. However, besides the usage of multiple network interfaces at the source or destination, the presence of load-balancers or multipath proxies [START_REF] Boucadair | Extensions for Network-Assisted MPTCP Deployment Models[END_REF] along the network can differentiate the route followed by the subflow packets.

Among the motivations pushed forward in support of MPTCP, there are (i) bandwidth aggregation, i.e., the increased network bandwidth offered to a connection; (ii) connection reliability, i.e., the possibility to use an alternative path in case of failure along the primary path or at the primary network interface level; (iii) communication confidentiality, i.e., the decreased ability for a Man-in-the-Middle (MITM) attacker to intercept all the traffic of a same connection.

While the first two aspects above have been largely explored in the last few years, the latter aspect is almost unexplored to date. In this paper, we report the results of an extensive measurement campaign aimed at assessing the degree of confidentiality one can expect using MPTCP. In particular, we focus on confidentiality from Autonomous System (AS)-level MITM interception, i.e., looking at the empirical probability that a single connection can be intercepted by an organization or an attacker able to capture all the traffic going through an AS on a given direction (most of Internet communications being asymmetric). Such attacks can happen either by remote access to routing devices of an AS or even by Border Gateway Protocol (BGP) route hijacking attacks. In our analysis, we consider the case of MPTCP traffic source devices using two edge providers and we compare the obtained results on a geographical basis, identifying in which countries and regions MPTCP may grant higher confidentiality with respect to MITM. An important assumption of our analysis is that the MPTCP scheduler behavior can be modified so that it does not look for throughput maximization only, but also for path diversity exploitation for increased confidentiality, as investigated in [START_REF] Coudron | Enhancing buffer dimensioning for Multipath TCP[END_REF].

The paper is organized as follows. Section II gives a background on MPTCP and related security concerns. In Section III, we describe our measurement methodology. Section IV presents the results. Section VI concludes the paper.

II. BACKGROUND

We provide in this section the necessary background on the MultiPath TCP (MPTCP) protocol and on Internet-scale Man-In-The-Middle (MITM) attacks.

A. MPTCP

MPTCP extends TCP and allows to fragment a data flow from a single connection into multiple paths (subflows TCP) [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF], [START_REF] Peng | Multipath TCP algorithms: Theory and design[END_REF], as illustrated in Figure 1. At the application layer, a connection appears as a normal TCP connection. At the network layer, each subflow looks like a regular TCP flow whose segments carry in their header a new type of TCP option [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]. The protocol improves the performance offered by a single flow and makes the connection more reliable using concurrent and redundant paths.

MPTCP employs a 4-tuple composed of source IP address, source port, destination IP address and destination port to identify the different subflows [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]. MPTCP manages the creation, removal and utilization of the subflows to send data while the connection is active. An MPTCP connection and its association with new subflows follow the same three-wayhandshake as for initiating a normal TCP connection. In the The MPTCP initial handshake carries additional information, such as a cryptographic key employed to authenticate the end-hosts and set up new subflows [START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]. In addition to the key, the establishment of additional subflow may employ other exchanged keying material, i.e., a token and random numbers (nonces), to prevent replay attacks on the authentication method. Further, an additional address identifier may be employed to identify the source IP address of a packet. Hence, even if the IP header has been changed by a middlebox (e.g. NATs, firewalls), end-hosts can unambiguously identify an address on a host.

MPTCP overcomes some weaknesses inherent to TCP, achieving (i) a greater throughput, (ii) higher reliability, and (iii) higher confidentiality for data transmission than its predecessor. Indeed, a multipath connection can improve the throughput aggregating bandwidth over different paths by concurrent data transmission across all available paths. Moreover, a multipath connection can quickly overcome one path failure by sending data to another available path, increasing the data delivery reliability [START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF]. Finally, fragmenting data flow connection across different subflows makes the flow hijacking difficult because attackers would need to capture the content transmitted through both the flows to build the content.

Therefore, MPTCP can provide a greater confidentiality than a regular TCP transmission if the subflows of a connection are routed on disjoint paths: the higher level of disjointness, the higher the confidentiality guarantee, and the higher the robustness against such attacks. The goal of this paper is to precisely quantify this level of robustness in usecases where MPTCP is primarily adopted not to improve communication performance or reliability, but to improve confidentiality. When addressing this feature, router-disjointness can be considered as too weak, in particular against AS-level traffic capturing and routing hijacking. We focus instead on AS-level disjointness.

B. Internet MITM Attacks

When considering AS level path disjointness, MITM attacks can be avoided if the disjoint paths bound to physical paths cannot jointly be accessible to a MITM attacker. In Internetscale communications, a MITM attack can happen if the attacker is able to capture all the traffic going through a same AS. In practice, this can happen if the attacker has access to all the traffic transiting through an AS, or at least a portion of it good enough to capture traffic to or from a given prefix. This can be possible with optical layer attacks or by BGP route hijacking MITM attacks.

At the optical layer, it is possible to split cables by using fiber optical taps, as explained in [START_REF] Witcher | Fiber Optics and Its Security Vulnerabilities[END_REF], with a low probability of being detected if peculiar strategies are adopted as explained in [START_REF] Furdek | Physical-Layer Attacks in Transparent Optical Networks, Optical Communications Systems[END_REF], [START_REF] Shaneman | Optical Network Security: Technical Analysis of Fiber Tapping Mechanisms and Methods for detection and Prevention[END_REF]. Moreover, one can intercept traffic by exploiting coupling and out-of-the-fiber light propagation phenomena [START_REF] White | An analysis of coupling attacks in highspeed fiber optic networks[END_REF], despite this is particularly challenging when performing wavelength-division-multiplexing.

At the BGP layer, a MITM attack exploits the natural way BGP works by stealthily hijacking Internet traffic to modify or capture it before it reaches the destination. BGP MITM attacks have been quite deeply studied for about twenty years. The survey in [START_REF] Conti | A survey of man in the middle attacks[END_REF] is a recent one with a detailed description of such attacks, their effects and defenses [START_REF] Conti | A survey of man in the middle attacks[END_REF]. The BGP MITM attack type has gained special attention in 2008, when a major provider in central Asia hijacked Youtube traffic to apply local policies. In the same year, a practical BGP MITM attack was demonstrated during the DefCon hacker conference [START_REF] Pilosov | Stealing The Internet -An Internet-Scale Man In The Middle Attack[END_REF]: authors successfully intercepted traffic bound for the conference network and redirected it to a system they controlled before routing it back to DefCon.

Multiple such BGP incidents are reported when they are notable ones [START_REF] Goldberg | Why is it taking so long to secure internet routing?[END_REF], [START_REF] Prem Sankar | B-Secure: A Dynamic Reputation System for Identifying Anomalous BGP Paths[END_REF]; often they are not reported because they cannot be always detectable, they have a limited scope, last for a short time, target a precise prefix, etc. A notable recent attack happened in 2014, when attackers have exploited such attacks to steal bitcoins [START_REF] Greenberg | Hacker Redirects Traffic From 19 Internet Providers to Steal Bitcoins[END_REF]: the attackers were able to inject BGP routes which redirected traffic from Bitcoin miner nodes to the attackers compromised host. It was estimated that at least $83,000 worth of Bitcoins, Dogecoins, HoboNickels, and Worldcoins were stolen over a period of four months.

In [START_REF] Alicherry | Doublecheck: Multi-path verification against man-in-the-middle attacks[END_REF] a solution to protect end-to-end communications from MITM attacks is presented; it employs multiple independent paths to retrieve self-signed certificates and doublecheck security mechanisms during the communication. Despite it focuses on the routing layer instead of the transport layer, the work is an example of using multiple end-to-end paths for improving security.

At the transport layer, the advent of MPTCP has raised new specification questions and challenges. There are attempts to verify the security of MPTCP [START_REF] Bagnulo | Threat Analysis for TCP Extensions for Multipath Operation with Multiple Addresses[END_REF], [START_REF] Bagnulo | Analysis of Residual Threats and Possible Fixes for Multipath TCP (MPTCP)[END_REF]. Also, researchers have proposed solutions against eavesdropping, in general, based on cryptography [START_REF] Kim | Efficient design for secure multipath TCP against eavesdropper in initial handshake[END_REF]. In [START_REF] Bagnulo | Analysis of Residual Threats and Possible Fixes for Multipath TCP (MPTCP)[END_REF], authors present an analysis of residual threats in the MPTCP signaling and propose fixes. In general, most of the works at the state of the art aim at either investigating security threats for MPTCP or proposing solutions for them. It is worth mentioning rising interest in using MPTCP to further enhance confidentiality when using Internet over-the-top Virtual Private Networks (VPN) services such as ToR and OnionCat [20]: MPTCP is used in the upstream direction from the client to many gateways accessible via the VPN, on the way to the server, further increasing the confidentiality level of the connection. Nevertheless, such practices can have a gain which can be hardly assessed: how can you ensure the upstream source-destination traffic does follow disjoint paths, hence decrease MITM efficiency, if not at the router-level, at the AS level? In this paper, for the first time at the state of the art as of our knowledge, we attempt at providing a partial response to such questions.

III. METHODOLOGY

In this section, we first give a description on the datasets used for constructing a representative AS-level graph of Internet, the basis for our analysis. Then, we describe our approach for computing the number of valid vertex-disjoint paths between two arbitrary nodes over the AS graphs. Finally, we detail how we evaluate path diversity at different geographical scopes. The dataset we employed as well as our scripts are given in [START_REF]LIP6-MPTCP open source project repository[END_REF] for the sake of reproducibility.

A. Graph construction

The AS-level Internet connectivity graph we used is derived from two types of data: the AS-level topology data and the inter-AS relationship data, both made available in [START_REF]AS-level Topology Archive[END_REF]. Comparing with other resources such as [START_REF] Caida | Archipelago (Ark) measurement infrastructure[END_REF] [24], the topological data from [START_REF]AS-level Topology Archive[END_REF] revealed to be more reliable and able to capture a broadened view of the Internet topology. Indeed, the data from [START_REF]AS-level Topology Archive[END_REF] integrates not only Routeviews data [START_REF] Routeviews | University of Oregon Route View Projects[END_REF], but also data from other well-known public view resources such as RIPE RIS [START_REF]RIPE RIS[END_REF]. Moreover, [START_REF] Caida | Archipelago (Ark) measurement infrastructure[END_REF] uses traceroutes that have known issues [START_REF] Oliveira | The (in)path search of the observed internet AS-level structure[END_REF] when converting router-level information into AS-level one.

The inter-AS relationship data from [START_REF]AS-level Topology Archive[END_REF] is extracted monthly from the Cyclops database [27], which adopts the interference techniques proposed in [START_REF] Oliveira | The (in)path search of the observed internet AS-level structure[END_REF]. The proposed algorithm takes advantages from both BGP data and Internet eXchange Point (IXP) data, then relying on valley-free routing analysis [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF] to derive the inter-AS relationships. To ensure the synchronization between topological and relational data we make use of measurements from the same source.

We extract 2015 data [START_REF]AS-level Topology Archive[END_REF] (the latest data set available), and combine them into a new dataset containing all the AS links along with their frequency of occurrence and relationship type. Employing measurements over a long period allows to capture inter-domain connection dynamics as well as inter-AS economic relationships. For instance, in one-month period, only 85% of inter-AS links appear more than 20 days, the remaining links which have a lower frequency of occurrence being those used for backup operations or during BGP convergence periods. For the sake of consistency, we removed these unstable links.

It is worth recalling that, because of BGP policy routing, Internet routing is asymmetric, hence capturing a full connection would mean capturing both communication directions, i.e., along both AS paths. However, as already mentioned in the introduction, we focus on MITM attacks that are able to capture traffic in one single direction, as client-server communications are essentially asymmetric.

B. Path diversity computation

The problem of selecting all the paths over a graph that satisfy given properties is often referred to as policy compliant path diversity computation in the literature [START_REF] Erlebach | Connectivity measures for internet topologies on the level of autonomous systems[END_REF] [START_REF] Klöti | Policy-compliant path diversity and bisection bandwidth[END_REF]. The general problem is to maximize the total number of valid vertexdisjoint paths in a type-of-relationship (ToR) graph [START_REF] Battista | Computing the types of the relationships between autonomous systems[END_REF], i.e., a directed graph in which the relationship between two adjacent vertexes (ASes in our case) is expressed via the direction of the edge connecting them. A ToR graph is generated from an original undirected graph integrated with relationship data. In [START_REF] Erlebach | Connectivity measures for internet topologies on the level of autonomous systems[END_REF], the path diversity between a specific pair of nodes in a graph is determined by solving an optimization formulation that maximizes the number vertex-disjoint paths in the ToR graph. The shortcoming of such approaches is that their timecomplexity is relatively high hence intractable for a graph as big as the AS graph.

The AS graph is a scale-free graph [START_REF] Albert | Statistical mechanics of complex networks[END_REF], i.e., a graph with a relatively few hubs capturing the majority of the paths. One of the consequences is that the diameter, i.e., the length of the longest path among all the shortest paths on a direction graph, is not too high. However, in the AS graph the best paths are selected based on a policy routing mechanism that put before path length other criteria such as local preferences, oldest route, etc. As a result in the BGP routing table the average path length (measured in number of AS hops) is not too low neither as the best path may not be the shortest path, and it is around 5 ASes as of today [START_REF] Khne | Update on AS Path Lengths Over Time[END_REF] (a bit lower in IPv6).

It is well known that searching for paths in a scale-free graph is a not too complex problem given the reasonable routing diameter, if one adopts breadth/depth-first search algorithms with a limited depth. Given a pair of source and destination nodes, s and d, respectively, a graph G(N, A) of policy compliant paths connecting them is discovered, where N is the set of nodes and A the set of links. Starting from the origin s, the breadth-search algorithm we adopt explores all the adjacent nodes of s; we validate the corresponding links (s, n) ∈ A if they do not violate the valley-free routing property [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF], and label them with the corresponding inter-AS relationship. For example, assuming that node s neighbors are n 1 , n 2 , n 3 , and s is customer ('c') of n 1 , provider ('p') of n 2 and peer with n 3 ; the relationships of (s, n 1 ), (s, n 2 ), and (s, n 3 ) are to be labeled as 'c2p', 'p2c' and 'p2p', respectively. Then, taking the c-type neighbors among s neighbors (i.e., n 2 ), and looking at their neighbors x in turn, those (n 2 , x) links are not validated if they are either c2p or p2p because a customer is not expected to grant transit towards its other provider(s) to one among its providers, and a customer is not expected to give access to its peer(s) to its provider(s). For instance, according to such a valley-free constraint, a valid path could be represented by the following regular expression c2p * p2p * p2c * [START_REF] Klöti | Policy-compliant path diversity and bisection bandwidth[END_REF], in which c2p, p2p and p2c express the relationship of links along a path. Such a breath-first path search strategy is iteratively applied starting from the source, repeated for all the neighbors, neighbors of the neighbors, and so on so forth until the destination d is reached or the hop distance from the s gets over a given threshold τ . By defining a proper value of τ we not only limit the time and space complexity for exploring the graph, but also ensure not taking into account long paths which should be avoid in practice by MPTCP schedulers. More importantly, the major benefit of such a search strategy is that the validity of a path can be checked in runtime while expanding the graph, thus removing edges that do not comply with routing policies. Our search algorithm is presented in detail in Alg.

if v = V isitedN ode then for n ∈ v.N eighborSet do if n = V isitedN ode then if label(v,n)='p2c' then for x ∈ n.N eighborSet do if label(n,x)='c2p' or label(n,x)='p2p' then g.RemoveEdge(n,x) end end end end N ewP ath ←-list(path) N ewP ath.append(n) if n = d then ValidPathSet.append(NewPath) end if length(NewPath) = τ + 1 then break end queue.append(NewPath) end VisitedNode.add(v) end end
As a result of the path search algorithm, policy compliant paths connecting source and destination may share common nodes. To get the final set of vertex-disjoint paths, we run a simple offline filtering linear algorithm to capture the shortest disjoint paths. Since the original list of valid paths revealed to be quite small most of the times, and sorted, the complexity of such a filtering operation is negligible.

C. Source-destination pairs

The current Internet ecosystem is composed of more than 50 thousands ASes, out of which more than half are stub ASes, i.e., ASes that are origin or destination only ASes. About 13% are Tier-3 or small Tier-2 ASes we arbitrary define in this paper as those appearing at most in the third from last position and at least penultimate position in BGP AS paths; we refer to such ASes as 'edge provider' ASes, which can be considered as a good representative set of national Internet Service Provider (ISPs) 'eyeball' ASes (hence excluding Internet carriers and stub ASes).

In order to determine which communications to cover in our study, we have to define a target set of source-destination pairs that address in a reasonable yet arbitrary way the communications that may be more sensible to communication privacy. We give a representation of the source-destination pair selection framework in Figure 2. Our choice of sourcedestination pairs is as follows:

• the source is interconnected to two edge providers.

• the destination is not multi-homed, i.e., it is reachable via a single ISP, the one given by the best BGP path from each source edge provider. • the destination belongs to another AS and another country than the ones of the source.

Besides reducing the number of pairs to a reasonable and treatable number (requiring about one week of computation), it is worth noting that, in such a way, we consider one singledirection communication data: the data we care of is the one is sent from the source node to the destination node. That is, under such a path election strategy, we are covering: 1) the case of multi-homed (nomadic) devices uploading to single-homed server; 2) the case of single-homed (fixed) devices downloading contents from servers connected to a multi-homed network.

For instance, the first case may be the one of sensors or other mobile devices (using cellular and/or WiFi and/or IoT protocol interfaces) uploading to a private cloud storage collected data (measurements, photos, videos, etc), and the second case may be the one of a residential user downloading files at home. Therefore, we are not covering:

• the case of multi-homed (nomadic) devices downloading from single-homed server; • the case of single-homed (fixed) devices uploading contents to servers connected to a multi-homed network.

• the case of multi-homed devices communicating with another multi-homed device;

We do not want to speculate that the latter three cases are less likely to happen. A dual analysis, quite expensive computationally, covering these cases may be performed as well in future works. However, at this stage, we cannot see intuitive critical-communication use-cases corresponding to such cases, and we doubt such an extended analysis might bring additional significant insights. Let us more precisely describe the source-destination pair election process. We segment the set of edge providers, E, in country-specific subsets, E c , where c ∈ C is a country in the set of countries C, i.e., E = ∪ c∈C E c . We use the AS-tocountry mapping given by the CIDR Report [START_REF] Bates | CIDR Report[END_REF]. Overall, for a given country c, the number of source-destination pairs is therefore equal to:

|E c| × (|E c| -1) 2 × c =c |E c | (1)
Doing so, we are targeting a lower bound, pessimistic, analysis, because we consider only international communications and we suppose the destination is not multi-homed. The filter we set on the destination enumeration allows us to target communications that may need a higher confidentiality due to their international connotation. Moreover, in this way we also avoid a huge bias due to the fact that a large majority of the AS paths available at the national level are not visible in backbone BGP routing tables such as the Routeviews ones (typically because of internet exchange points, as recently shown in [START_REF] Ager | Anatomy of a large European IXP[END_REF]). We believe having a lower bound stand is more appropriate than an upper bound one, while allowing us to scientifically qualify the value of the relative trends.

Given a source-destination pair, we then calculate the number of AS-disjoint paths using the path search algorithm already described, and store this information. In practice, on the resulting AS-graph (composed of 21469 edge provider nodes and 86983 edges with an average degree of 4.05), it takes from 500 ms to 2.5 s to compute the total number of policy-compliant vertex-disjoint paths for each pair of AS nodes. Please note that the source node is not considered as an AS node of the AS graph; therefore, in the measurement results that follow we distinguish between the view point of the source node from the view point of its providers.

IV. RESULTS

We report the results obtained for a set of 147 countries, i.e., those countries from the United Nations statistics [START_REF]Standard country or area codes for statistical use (M49)[END_REF] that have at least two distinct edge providers officially based in the country (this excludes Greenland territories, very small citystate countries and many African and Indonesian countries). The geographical coverage is given in Figure 3.

We proceed as follows.

• For each country, we generate all possible dual-homed source configurations, i.e., all possible pairs of edge providers. Figure 4 reports the distribution of the number of source pairs for each countries. • For each source configuration (i.e., for each pair of edge providers), we compute the number of disjoint paths to each destination. Figure 5 reports the distribution of the number of destinations for each source country. • MITM robustness metric: for a given source, we define it as the average of the number of disjoint paths over all the destinations: such metric can be considered as a level of unlikelihood that a MinM attack can take place for that source configuration; the higher the value of the MITM metric, the more difficult is for an attacker to capture traffic from that country. • For each country, a series of MITM robustness metrics, one for each source, is therefore created. We characterize the resulting series using boxplot (minimum, quantiles, maximum, and 0.1% outliers) distribution. Figures 4 and5 show that the three countries with the highest number of source configurations (i.e., those with the highest number of edge provider pairs), e.g., Brazil, US and Russia have also the lowest size of the destination set, which is reasonable given (1), while guaranteeing a largely sufficient statistical significance (thousands of entries for each country). We overlay over the boxplots the average of the corresponding series (red square). The results are then ordered from left to right with increasing averages.

Results are shown in Figure 6 and depicted on the world map in Figure 3. We report three types of results: • For Figure 6a, the MITM robustness is computed with the source node integrated as a node in the AS graph as an artificial node, i.e., it provides a device view; obviously, in this view the upper bound of the robustness is 2, i.e., the number of edge providers used by the source. • For Figure 6b, the MITM robustness is computed instead summing the number of disjoint paths from the first edge provider to those from the second edge provider, then decreased by those paths that do share an AS hop, i.e., it provides an edge provider view; when higher than 1 for a given edge provider, our assumption when counting the robustness metric is that the additional paths from the edge provider can be made available to MPTCP subflows by forms of load-balancing. • For Figure 6c, we report the differential robustness results, i.e., the edge provider view robustness minus the device view robustness, computed for each source configuration individually. This view more precisely quantifies the gain achievable for MPTCP communications in case of inter-AS load-balancing at the edge providers.

That is, while Figure 6b assumes MITM attacks do not happen at the source and destination edge providers (i.e., there is a high level of trust on those edge providers), Figure 6a assumes that MITM attacks can happen at the source edge providers, hence revealing a low level of trust in source direct providers. Figure 6c can be interpreted as the marginal gain to consider when adopting (for the provider) or using (for the user) inter-AS load-balancing features at the edge provider (or over-the-top VPN) level. It is worth noting that Figure 6a may also better represent the case of single-homed client downloading from multi-homed server discussed in Section III-C, in which case server direct providers are not the client direct providers and thus can be less trusted ones.

As a general assessment, Figures 6 show that, considering 1.5 average as the rough threshold making the likelihood of MITM negative if higher than it, positive is lower than it, only about 5% of the countries show good chances of being robust against MITM from a device view, while looking at the maximum instead of the average and median values one could speculate that careful choice of the edge providers could make this likelihood positive for a majority of the countries. From a, edge provider view this ratio grows to roughly 60%, and higher than 90% if the edge provider choice is influenced by confidentiality concerns.

Moreover, the average number of paths connecting a dualhome node to international destinations has a significant variance depending on the source country. The average robustness ranges from 1 and less to 1.6 from a device view, and from 1 (and less) to 2.5 from an edge provider view. Some minimum and even average values are below 1 because of the partial view of Internet topology and the incompleteness of inter-AS relationship interference, which make some destinations unreachable via the ToR graph (hence counted as 0 paths); we left it as is to also give an index of the level of the ToR graph incompleteness for different countries. In any case, the boxplot median is a metric robust against such outliers to look at.

In addition, observing the plots in Figure 6, we can also remark that:

• Within a country, a high inter-quantile range (between the first and the third quantiles) indicates that the path diversity strongly depends on how the two upstream edge providers are selected for the source. • The median is mostly higher than the average in the device view, and lower than the average in the edge provider view. This is essentially due to outliers, counted in the average and not in the median. • The gap between the min and max robustness is another interesting fitness metric to observe. Some countries maintain a small gap (below 1) while others have a very big gap (up to 2). In other words, the deployment of MPTCP for securing international communications in some countries can statistically yield a much better result than in other countries, where this gap is smaller.

Particularly interesting is the case of Angola (AO), Venezuela (VE) and Namibia (NA), with small robustness gap, which may be correlated to the presence of intercontinental cables landing at or close to the country [START_REF]Cable Map[END_REF]. • In the edge provider view, the maximum value is higher than 2 in the majority of the countries: this behavior suggests that with a proper choice of trusted upstream providers for the source, communicating nodes can adopt MPTCP to statistically expect high confidentiality for their communications regardless. Particularly alerting are the cases of Uzbekistan (UZ), Nepal (NP) and Lebanon (LB), with quite low maximum value. • In the device view, in the majority of the cases the maximum robustness is not higher than 1.6, both averages and medians are quite far from the desirable target of 2. Hence, without the support of inter-AS load-balancing (such as with BGP or LISP protocols), path diversity from a dual-homed node is reduced significantly, indicating a non negligible probability of paths joining on the way to the destination. • Looking at the differential robustness, we can remark that among the countries that have the lowest device view MITM robustness, those that could the most benefit from inter-AS load-balancing practices are Mongolia (MN), Pakistan (PK) and Korea (KR). However, most of those with low robustness do not improve much the situation with respect to the device view. Looking at macro geographical regions, many European countries seem to grant better security than countries in other regions. In order to look after continental characteristics, the plots in Figure 7 show the boxplot results (with 1% outliers) aggregated on a macro-region basis (a and c, sub-continental level) and on a relative position basis (b and d, in terms of seacoast and inland borders). We can remark that:

• Western Europe appears as the best off, followed by Northern Europe and Northern America. In almost 50% of Western Europe countries there can be 2 disjoint paths from the source edge providers to Internet destinations.

• Central Asia shows the worst robustness, followed by Australia and New Zealand; the reasons are likely network centralization practices and geographical isolation.

It is interesting to notice the relevant gap between Central and South-Eastern/Western Asia. • A high variance is recorded at Southern Asia, Northern Europe and Sub-Saharan Africa, which indicates high differences among the countries within these areas. • We could not find strong correlation between the relative continental position, and the robustness metric, yet a positive correlation exists, with countries at the boundaries of oceans, with inter-continental cable landing and that are sea-oriented (most of the border on the sea-side) that offer higher robustness than fully internal and continentaloriented ones.

V. APPLICATION SCOPES

We focused our study on MPTCP-based communications. More precisely, our study cover the following cases:

• MPTCP capable end-points: both source and destination, client and server (or viceversa) end-points, are MPTCP capable, and the MPTCP communication is not filtered by middle-boxes. As argued in Section III-C, the multihomed end-point can be either the server or the client. • MPTCP proxied end-points: at least one end-point is not MPTCP capable, but its (their) TCP communications is (are) handled by MPTCP proxie(s), converting TCP packets into MPTCP packets and/or viceversa, as explained in [START_REF] Boucadair | Extensions for Network-Assisted MPTCP Deployment Models[END_REF], [START_REF] Boucadair | Network-Assisted MPTCP: Use Cases, Deployment Scenarios and Operational Considerations[END_REF], possibly routed via Internet disjoint paths as proposed in [START_REF] Coudron | Cross-layer Cooperation to Boost Multipath TCP Performance in Cloud Networks[END_REF], [START_REF] Benchaib | Transparent Cloud Access Performance Augmentation via a MPTCP-LISP Connection Proxy[END_REF]. The multipath conversion proxies (i.e., aggregation and concentrator nodes) can sit at endpoint premises (customer premises equipment for the client node, hypervisor or middle-box at the server side) or at the edge provider level borders.

Moreover, besides MPTCP-based communications, other protocols offering Internet-scale multipath load-balancing could also be covered by this study. The following protocols are either not deployed, or they have undergone only a limited deployment so far; they are:

• SCTP: the Stream-Control-Protocol (SCTP) [START_REF] Tuexen | Stream Control Transmission Protocol (SCTP) Chunk Flags Registration[END_REF] is another multipath transport protocol absolving the same function than MPTCP, but less deployed than MPTCP due to the limited retrocompatibility. • LISP: the Locator/Identifier Separation Protocol (LISP) [START_REF] Fuller | Locator/ID Separation Protocol (LISP) Map-Server Interface[END_REF] is able to perform inter-AS inbound loadbalancing by means of encapsulation, routing locator mapping, and appropriate traffic engineering policy configuration. LISP primary scope is the edge provider one, hence results with the edge provider view readily apply to LISP traffic engineering. It is worth noting that, deployment of LISP as an intra-AS TE tool can also allow performing inter-AS multipath on the outbound direction as proposed in [START_REF] Misseri | Internet routing diversity for stub networks with a Map-and-Encap scheme[END_REF]. • MultiPath BGP: in BGP, when some higher BGP decision criteria are equivalent, even if the load might technically be balanced on the equivalent routes, only one route is retained using lower-level criteria (that can be inefficient ones in terms of global routing such as hot-potato or tie-breaking rules). However, forms of Multipath BGP were discussed in standardization fora, but finally not standardized; however, some recommendations have been published [START_REF] Lange | Issues in Revising BGP-4[END_REF], and some vendors implement it (see, e.g., [START_REF]JUNOS 8.2 Routing Protocols Configuration Guide[END_REF] and [START_REF]BGP Best Path Selection Algorithm[END_REF]). Such multipath BGP mode can be adopted at the edge provider scope as for LISP, but instead than on the inbound direction as LISP, multipath BGP applies to the egress load-balancing direction. Despite the study [START_REF] Elena | Characterisation of AS-level Path Deviations and Multipath in Internet Routing[END_REF] on BGP core routing tables report that in 2010 multipath BGP was practically not used, speculations report it is used by major cloud providers.

The above protocols are a selection of those protocol communication contexts where load-balancing can have a direct effect on the AS path selection. Nevertheless, other loadbalancing protocols can potentially have an impact on the egress AS selection as well, as for instance in data-center environments. In the case of MPTCP communications, these protocols, operated at the edge provider view, are able to perform inter-AS load-balancing in such a way that the path diversity exposed in the edge provider view in our analysis can be made available to MPTCP devices subflows, hence given them the full potential of MPTCP in terms of communication confidentiality and robustness against MITM attacks.

VI. CONCLUSION

We explored in this paper how Internet path diversity could be exploited by means of multi-path transport protocols when looking at increased security against man-in-the-middle attacks. We focused in particular on such attacks acting at the Internet network autonomous system level, and at the robustness of MPTCP communications in what appear as a reasonable configuration where at least one among the endpoints is multi-homed with two edge providers.

We reported extensive specific and aggregated results for most of the world countries and regions, looking at macro trends that could inspire further research in the area. Results show that, statistically speaking, MPTCP does not help in guaranteeing robustness against MITM attacks hence high confidentiality, unless the choice of the edge provider is carefully taken, or one can rely on inter-AS load-balancing features offered implicitly or explicitly by edge providers. Some continental regions are strongly more robust than others, and there seems to be a positive correlation with inter-continental cable landing proximity. Moreover, the results show that there are countries surprisingly less well connected than one could think of and countries that are more obviously less robust against such attacks due to network centralization practices.

Fig. 1 .

 1 Fig. 1. Multipath TCP Connection: Overview first handshake, MPTCP uses a control flag (MP_CAPABLE) in the option field of the segment header to verify if both endhosts support MPTCP and configure the connection. Whether a remote host does not support the protocol, the connection seamlessy backwards to a regular TCP signaling.The MPTCP initial handshake carries additional information, such as a cryptographic key employed to authenticate the end-hosts and set up new subflows[START_REF] Ford | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]. In addition to the key, the establishment of additional subflow may employ other exchanged keying material, i.e., a token and random numbers (nonces), to prevent replay attacks on the authentication method. Further, an additional address identifier may be employed to identify the source IP address of a packet. Hence, even if the IP header has been changed by a middlebox (e.g. NATs, firewalls), end-hosts can unambiguously identify an address on a host.MPTCP overcomes some weaknesses inherent to TCP, achieving (i) a greater throughput, (ii) higher reliability, and (iii) higher confidentiality for data transmission than its predecessor. Indeed, a multipath connection can improve the throughput aggregating bandwidth over different paths by concurrent data transmission across all available paths. Moreover, a multipath connection can quickly overcome one path failure by sending data to another available path, increasing the data delivery reliability[START_REF] Raiciu | Improving datacenter performance and robustness with multipath tcp[END_REF]. Finally, fragmenting data flow connection across different subflows makes the flow hijacking difficult because attackers would need to capture the content transmitted through both the flows to build the content.Therefore, MPTCP can provide a greater confidentiality than a regular TCP transmission if the subflows of a connection are routed on disjoint paths: the higher level of disjointness, the higher the confidentiality guarantee, and the higher the robustness against such attacks. The goal of this paper is to precisely quantify this level of robustness in usecases where MPTCP is primarily adopted not to improve communication performance or reliability, but to improve confidentiality. When addressing this feature, router-disjointness can be considered as too weak, in particular against AS-level traffic capturing and routing hijacking. We focus instead on AS-level disjointness.

Fig. 2 .

 2 Fig. 2. Source-destination pair selection process

Fig. 3 .

 3 Fig. 3. Countries covered with corresponding MITM robustness distribution.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Number of source configurations per country

Fig. 6 .

 6 Fig. 6. MITM robustness distribution for 147 countries.

  Fig. 7. MITM robustness metric with aggregated country groups.

  1.

	Algorithm 1: Path Search Algorithm
	input : source s, destination d, graph g
	output: ValidPathSet
	V isitedN ode ←-∅
	queue.append([s])
	while queue not empty do
	path ←-queue.pop()
	v ←-path.LastN ode()


Stephane Clinchant

Gabriela Csurka

Julien Ah-Pine

Guillaume Jacquet

Florent Perronnin

Jorge Sánchez

Keyvan Minoukadeh

Stéphane Clinchant

XRCE's Participation in Wikipedia Retrieval, Medical Image Modality Classification and Ad-hoc Retrieval Tasks of ImageCLEF 2010

Keywords: Cross-modal Information Retrieval, Image Modality Classification, Medical Image Retrieval, Wikipedia Retrieval, Fisher Vector, Lexical Entailment, Query Expansion

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

Introduction

This year, XRCE participated in three main tasks of ImageCLEF 2010. The Visual Concept Detection and Annotation Task is presented in a separate paper. In this working note, we rather focus on our participation in the Wikipedia Retrieval Task [START_REF] Popescu | Overview of the wikipedia retrieval task at imageclef 2010[END_REF] and in two sub-tasks of the Medical Retrieval Task (Image Modality Classification and Ad-hoc Image Retrieval) [START_REF] Müller | Overview of the clef 2010 medical image retrieval track[END_REF]. In participating in these tasks, our first motivation was to investigate how well do our textual and visual retrieval and classification systems perform on Wikipedia and Medical Image Collections. Our second aim was to experiment with different information fusion strategies to cope with the multi-modal (textual and visual) aspect of the tasks.

Concerning the text-based retrieval, two information retrieval models were considered: a standard language model (similar to the techniques used in our past participation in other tasks of ImageCLEF [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF]) and an information based model employing power law (log-logistic and smoothed power law) distribution proposed in [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]. These methods have shown high performances especially when combined with pseudo-relevance feedback or query expansion mechanisms were also applied.

In the case of the Medical Retrieval Task, our aim was to combine Lexical Textual Entailment inspired by Statistical Translation Models with query expansion mechanisms using external resources (in our case Wikipedia pages).

For representing images, we used the Improved Fisher Vectors (IFV) [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF][START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF]. Fisher Vectors have been successfully used in our previous ImageCLEF participations [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF], and for this challenge we used an improved version with power and L2 normalizations and a spatial pyramid representation as suggested in [START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF]. These IFVs were used as the image representation in all our tasks. They showed excellent performances in the Image Modality Classification Task both using them alone or combined with text representation. Concerning retrieval results, even with the latter recent advances in visual similarity [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF], using only images was not sufficient to address the Wikipedia and Medical Image Retrieval tasks. Indeed all visual-only runs performed poorly.

As the visual retrieval is an important element for the cross-modal similarities technique we used with success in the Photo Retrieval Tasks of past ImageCLEF sessions [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF], we did not experiment with these techniques for this year's challenges. We decided to use other score aggregation methods where we could easily handle the asymmetric roles of the two modalities during the fusion process. Hence we designed and compared several fusion strategies. We have shown that despite poor visual retrieval results, our proposed aggregation techniques were able to outperform both the image-only and text-only retrieval systems.

The rest of the paper is organized as follows. In Section 2 we describe our text retrieval and query expansion models. In Section 3 we briefly describe the image representation with the improved Fisher Vectors. In section 4 we present and compare different runs we submitted and we conclude in Section 5.

Text Retrieval

We start from a traditional bag-of-words representation of pre-processed texts where pre-processing includes tokenization, lemmatization, and standard stopword removal. However, in some cases lemmatization might lead to a loss of information. Therefore before building the bag-of-words representation we concatenated a lemmatized version of the document with the original document.

Two information retrieval models were considered: a standard language model (similar to the techniques used in our past participation in other tasks of ImageCLEF [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF]) and an informationbased model employing a log-logistic distribution proposed in [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]. We also present a query expansion mechanism that appeared to be relevant to the Medical Retrieval Task. Finally, we briefly describe some details specific to the individual tasks.

Information Retrieval Techniques

To take into account the fact that one is comparing documents of different lengths, most IR models do not rely directly on the raw number of occurrences of words in documents, but rather on normalized versions of it. Language models for example use the relative frequency of words in the document and the collection3 :

P (w|d) = λ x d w l d + (1 -λ) d x d w ) d l d (1)
where x d w is the number of occurrences of word w in document d, l d is the length of d in tokens after lemmatization and C is the corpus. Then we can define the similarity between the query q = (q 1 , ..., q l ) and a document d using the cross-entropy function:

CE(q|d) = qi P (q i |q) log( w P (q i |w)P (w|d)) (2)
Other classical term normalization schemes include the well known Okapi normalization, as well as pivoted length normalization [START_REF] Singhal | Pivoted document length normalization[END_REF]. More recently, the concept of the amount of information brought by a term in a document has been considered in several IR models, inspired by the following observations made by Harter in [START_REF] Harter | A probabilistic approach to automatic keyword indexing[END_REF]: the more a word deviates in a document from its average behavior given the collection, the more likely it is "significant" for this particular document. This can be easily captured in terms of information: if a word behaves in the document as expected in the collection, then it has a high probability p of occurrence in the document, according to the collection distribution, and the information it brings to the document, -log(p), is small. On the contrary, if it has a low probability of occurrence in the document, according to the collection distribution, then the amount of information it conveys is greater. This is the underlying idea of the information models proposed by Clinchant and Gaussier [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]: the log-logistic and smoothed power-law models.

These models are specified in three steps: the Divergence from Randomness (DRF) normalization of terms frequencies, the choice of a probability distribution to model these frequencies in the corpus and the mean information as the Relevance Score Vector (RSV). In the case of the log-logistic model, we have (for further details see [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]):

-DFR Normalization with parameter c:

t d w = x d w log(1 + c avg l l d ) -T f w ∼ LogLogistic(λ w = Nw N ) -Ranking Model: RSV (q, d) = w∈q∩d x q w -log P (T f w > t d w ) (3)
where x d w and x q w are the numbers of occurrences of word w in document d and query q, N and N w are the numbers of documents in the corpus and the number of those containing w, avg l and l d are the average document length and the length of the document d.

In the case of the smoothed power-law model we have the same steps but the Relevance Score Vector in the Ranking Model is replaced by (see details in [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]):

RSV (q, d) = w∈q∩d -x q w log( λ t d w t d w +1 w -λ w 1 -λ w ) (4)

Lexical Entailment -Statistical Translation Model

Berger and Lafferty [START_REF] Berger | Information retrieval as statistical translation[END_REF] addressed the problem of information retrieval as a statistical translation problem with the well-known noisy channel model. This model can be viewed as a probabilistic version of the generalized vector space model. The analogy with the noisy channel is the following one: To generate a query word, a word is first generated from a document and this word then gets "corrupted" into a query word. The key mechanism of this model is the probability P (v|u) that term u is "translated" by term v. These probabilities enable us to address a vocabulary mismatch, and some kinds of semantic enrichments. The problem now lies in the estimation of such probability models.

We refer here to a previous work [START_REF] Clinchant | Lexical entailment for information retrieval[END_REF] on lexical entailment models to estimate the probabilities. Lexical Entailment (LE) [START_REF] Clinchant | Lexical entailment for information retrieval[END_REF][START_REF] Glickman | A probabilistic classification approach for lexical textual entailment[END_REF][START_REF] Dagan | The PASCAL recognising textual entailment challenge[END_REF] models the probability that one term entails another. It can be understood as a probabilistic term similarity or as a unigram language model associated to a word (rather than to a document or a query). Let u be a term in the corpus, then lexical entailment models compute a probability distribution over terms v of the corpus P (v|u). These probabilities can be used in information retrieval models to enrich queries and/or documents and to give a similar effect to use of a semantic thesaurus. However, lexical entailment is purely automatic, as statistical relationships are only extracted from the considered corpus. In practice, a sparse representation of P (v|u) is adopted, where we restrict v to be one of the N max terms that are the closest to u using an Information Gain metric4 .

To summarize our approach, documents containing images were extracted from the corpus and we computed a lexical entailment measure on this collection with the model GI-M3 as in [START_REF] Clinchant | Lexical entailment for information retrieval[END_REF] or using Chi-square statistics. Finally, we expanded the query terms with words that were the most similar to the latter in terms of the chosen lexical entailment measure.

ImageCLEF Task-specific Text Processing

In this section we give some further details on the text retrieval processes that were designed or applied to a given task.

Wikipedia The Wikipedia Corpus consisted of images with their captions extracted from Wikipedia in different languages namely French, English and/or German. In addition, the participants were provided with the original Wikipedia pages in one or several languages in wikitext format. Similarly the textual part of the query was multilingual.

For each image, in addition to the given metadata (image's captions), we extracted from the Wikipedia pages the paragraph of the Wikipedia page in which the image was mentioned. Thus, two indexes were built for the collection: one for the captions (metadata) of the images and one for the paragraphs. The combination of the retrieval scores based on those two types of text, was done by a simple late fusion (mean average) after having normalized the scores between 0 and 1.

To cope with the multilingual nature of the wikipedia collection, we adopted an early fusion approach that we previously experimented within CLEF'08 Adhoc [START_REF] Clinchant | Multi-language models and meta-dictionary adaptation for accessing multilingual digital libraries[END_REF]. This early fusion of text amounts to merging the different languages of a document into a single document. Different language representations of queries are also merged in a similar fashion. Multilingual queries are then matched with multilingual documents as if there was no difference between languages.

Medical Task

In the Medical Retrieval Task, although participants were provided with articles containing the image, we used only the image captions to build the term frequencies and the distributions of these frequencies (see 2.1). Nevertheless, the text from the articles containing the image was used as a corpus during the topic enrichment step with the model described in 2.2.

Furthermore we also experimented with query expansion mechanisms using external data. Without such techniques, we would have vocabulary mismatches between queries and documents. For example, for the topic 16 'dermatofibroma' we found no document containing "dermatofibroma" as a word. The Lexical Entailment methods using the articles enabled us to address some of the issues, but the coverage of the retrieval system can be improved by using an external knowledge base. Ideally, the use of a thesaurus such as Mesh and the resources provides by UMLS would have been preferable. However, with the lacks of experience (this was our first participation in the Medical Task) and time for extracting useful information from these resources, we used our usual tools to improve the coverage for a given query with information extracted from Wikipedia pages.

To do so we proceeded as follows. For each query, a set of related pages in Wikipedia was found in order to cover all query terms:

topic-1 | thoracic_aortic_dissection topic-2 | Acute_Myeloid_Leukemia topic-4 | congestive_heart_failure topic-5 | brachial plexus nerve_block
We filtered redundant pages in order to have a unique coverage of query terms and to disambiguate some terms by taking the sense which was the most similar to the medical collection. Concerning the coverage, if the query contained a multiword expression related to a Wikipedia page, we used this page and not those related to the words within this multiword expression. For example, in topic 1, we can find the page "thoracic aortic dissection" in Wikipedia, then we use it and not the page "dissection". The disambiguation was done by computing a text similarity with the medical collection and by keeping the sense which had the higher score.

Then, for each of theses pages, we extracted only the hyperlinked text embedded in the body content. For each query, all those new terms were merged and we kept only the 20 terms that were the most frequent in the collection. This can be viewed as a query expansion mechanism provided by Wikipedia pages. Although, this expansion was expected to be noisy, it had the potential to improve recall. Finally, original textual runs were combined with these expanded query runs in order to maintain a high precision (see details in 4.3).

Image Representation

As for the image representation, we used an improved version [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF][START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF] of the Fisher Vector [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. The Fisher Vector can be understood as an extension of the bag-of-visual-words (BOV) representation. Instead of characterizing an image with the number of occurrences of each visual word, it characterizes the image with the gradient vector derived from a generative probabilistic model. The gradient of the log-likelihood describes the contribution of the parameters to the generation process.

Assuming that the local descriptors I = {x t , x t ∈ R D , t = 1 . . . T } of an image I are generated independently by Gaussian mixture model (GMM) u λ (x) = M i=1 w i N (x|mu i , Σ i ), I can be described by the following gradient vector (see also [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]):

G I λ = 1 T T t=1 ∇ λ log u λ (x t ) (5)
where λ = {w i , µ i , Σ i , i = 1 . . . M } are the parameters of the GMM. A natural kernel on these gradients is the Fisher Kernel [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF]:

K(I, J) = G I λ F -1 λ G J λ , F λ = E x∼u λ [∇ λ log u λ (x)∇ λ log u λ (x) ] . (6)
where F λ is the Fisher information matrix. As it is symmetric and positive definite, F -1 λ has a Cholesky decomposition F -1 λ = L λ L λ and K(I, J) can be rewritten as a dot-product between normalized vectors G λ with: G I λ = L λ G I λ . We will refer to G I λ as the Fisher Vector (FV) of the image I.

In the case of diagonal covariance matrices Σ i (we denote by σ 2 i the corresponding variance vectors), closed form formulas can be derived for [START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF]). As we do not consider G I While this representation was successfully used with the L1 normalization and L1 norm based similarity between the Fisher Vectors in our previous ImageCLEF participation [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF], this time we used an improved version of it with Power and L2 normalization and simple dot product similarity between them as suggested in [START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF]. In order to obtain these Improved Fisher Vectors we first use a Power Normalization with α = 0.5:

G I w d i , G I µ d i , G I σ d i , for i = 1 . . . M , d = 1 . . . D (see details in
P N (G I λn ) = sign(G I λn )|G I λn | α , n = 1 . . . N. (7)
The aim of this normalization is to make the distribution of features in a given dimension n less peaky around zero. Then, these vectors are further L2 normalized to discard image-independent (i.e. background) information (see further details for both normalizations in [START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF]). Another improvement made to our Fisher Vector based image representation was the use of the spatial pyramid representation by Lazebnik et al . to take into account the rough geometry of a scene [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. The main idea is to repeatedly subdivide the image and represent each layout as a concatenation of the representations (in our case Fisher Vectors) of individual sub-images. As we used three spatial layouts (1 × 1, 2 × 2, and 1 × 3), we obtained 3 image representations of respectively N , 4N and 3N dimensions.

As low level features we used our usual (see for example [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF]) SIFT-like Orientation Histograms (ORH) and local color statistics (COL), i.e. local color means and standard deviations in the R,G and B channels, both extracted on regular multi-scale grids and reduced to 50 or 64 dimensional with Principal Component Analysis (PCA). With the three different spatial layouts mentioned above each image was finally represented by 6 different high level feature vectors (referred to as IFV for Improved Fisher Vector).

Runs Description

Wikipedia Retrieval

The Wikipedia Retrieval task consists of multilingual and multimedia retrieval. The collection contains images with their captions extracted from Wikipedia in different languages namely French, English and German. In addition, participants were provided with the original Wikipedia pages in wikitext format. The task consisted in retrieving as many relevant images as possible from the aforementioned collection, given a textual query translated in the three different languages and one or several query images.

We submitted different types of runs: mono-media runs and multimedia (mixed) runs with different fusion approaches.

Concerning the pure visual retrieval, we used 6 Improved Fisher Vector (IFV), corresponding to the two different low level features (ORH and COL) with the 3 spatial-layout (1x1, 2x2, 1x3) as described in section 3. The 6 IFVs were used independently to rank the Wikipedia images using the dot product as similarity measure and the 6 scores were weighted giving higher weights (0.7) to the IFV based on orientation histograms compared to the IFV based on color (0.3) before averaging them. The pure visual run results are mentioned in line 1 of Table 1. The performances are very poor and this shows that even recent advances in visual similarities [START_REF] Perronnin | Large-scale image categorization with explicit data embedding[END_REF] are not sufficient to address the Wikipedia Retrieval task efficiently.

Pure text based retrieval performs much better. Details on the definition of the methods and the underlying retrieval models used are mentioned in section 2. Accordingly, from lines 2 to 4 of Table 1, we report 3 pure text runs which are based on recent models presented in [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]. Line 2 is based on a smoothed power-law retrieval model while the latter two ones rely on a log-logistic probability distribution. It appeared that the smoothed power-law model performed better than the loglogistic ones, achieving 23.61% of Mean Average Precision (MAP). Nevertheless, in our combined modality runs, we used the former run when combining with visual retrieval. All text runs use both captions (metadata) and paragraphs as explained in section 2. However, the difference between the text runs LGD ALL METANOPRF PARAGPRF20 (line 3) and LGD ALL META PARAG (line 4) is that the former uses on the paragraphs, an additional pseudo-relevance feedback mechanism (PRF), introduced in [START_REF] Clinchant | Information-based models for ad hoc ir[END_REF]. This strategy appeared to be beneficial since the results obtained for the former run are better.

Runs reported from lines 5 to 16 are mixed, i.e. they make use of both visual and textual similarities. We grouped the runs according to the text run used in the combination. Consequently, from lines 5 to 10, we report the results of mixed runs that used the text run from line 3 (T2=LGD ALL METANOPRF PARAGPRF20) whereas from line 11 to line 16 we report results of the mixed runs that used the text run from line 4 (T3=LGD ALL META PARAG). The runs with a symbol (lines 5 and 12) in Table 1 were not submitted but we added them in order to have a better comparison between the results obtained using both aforementioned text runs.

As explained earlier, T2 gave a better result than T3. Moreover, whatever the combination technique we used, we always observe that the run using the PRF on the paragraphs dominates the other one. Therefore, we will only comment on the results of mixed runs reported from lines 5 to 10 in Table 1. Similar conclusions can be deduced for the runs from line 11 to line 16.

From our past experiences with ImageCLEF [START_REF] Müller | Leveraging image, text and corss-media similarities for diversity-focused multimedia retrieval[END_REF], we observed that textual similarity played a core role, but that it could be complemented with visual similarity if combined in an appropriate way. In other words, when combining image and text similarities in the context of multimedia retrieval, we paid attention to the fact that these two media should not be given, in general, symmetric roles during the fusion process.

Consequently, our first fusion strategy was to start with using the text similarities as a prefiltering stage before applying the visual similarities. In practice, we first selected the top 2000 images according to the textual similarities. Then, we re-ranked this pre-filtered top-list using the visual similarities only. This pre-filtering step based on textual similarities allowed us to significantly increase the pure visual run from 5.53% (line 1) to 18.05% of MAP (line 5). In particular, it gives better results than both image and text runs in terms of Precision at 20 (P@20). Still, this run entitled SEQ RERANKING-T2 (line 5) does not perform as well as pure textual similarities T2 (line 3) in terms of MAP.

Then, going beyond this simple re-ranking strategy, we investigated the combination of the re-ranked run SEQ RERANKING-T2, with the pure textual run T2. We basically normalized the two runs so that the scores were between 0 and 1 and we applied different aggregation functions. The different results are shown from line 6 to line 10.

Our first approach consisted in applying a simple weighted mean average operator. In that case, the submitted runs were given by the following aggregated score:

w R s T RV (I) + w T s T R (I) ( 8
)
where I is an image of the collection, s T RV is the normalized score distribution based on the visual similarities but after having selected the top 2000 images according to the textual similarities, s T R is the normalized score distribution based on the textual similarities and w R and w T are their respective weights in the late fusion method. Lines 6, 8 and 10 with runs' titles beginning with FUSION are the results obtained with the following parameters: line 6 with w R = 0.5 and w t = 0.5; line 8 with w R = 0.7 and w t = 0.3; and line 10 with w R = 0.3 and w t = 0.7.

Our second fusion technique uses an aggregation operator that was introduced in [START_REF] Ah-Pine | Data fusion in information retrieval using consensus aggregation operators[END_REF]. This approach attempts to reinforce the aggregated score of an image assuming that there is a strong relationship between the two scores. In that case, the submitted run reported in line 7 of Table 1 (called CONFAGmin-T2) was given by the following aggregated score:

s T RV (I) + s T R (I) + min(s T RV (I), s T R (I)) (9)
Our last combination approach follows the idea that image similarities are less reliable then text similarities and when combining both of them one should adapt the combination weights accordingly. In that perspective, we propose to set the combination weights as functions of the visual similarity values. We particularly tested linear functions with w R (s T RV (I)) = αs T RV (I) and w T (s T Rv (I)) = 1 -αs T RV (I). This leads to the following aggregation method:

α(s T RV (I)) 2 + (1 -αs T RV (I))s T R (I) ( 10
)
Line 9 corresponds to the results obtained using the aforementioned aggregation function with α = 0.7 (CONFα-T2).

From Table 1, we can make the following observations:

-Image similarities are not sufficient to address the task accurately and text similarities perform much better. -Using as a preliminary stage the text similarities in order to select a first relevant list of images and re-ranking the latter list on the basis of image similarities only allows us to boost the precision (P@20) but not the MAP. The important conclusion to make here and towards multimedia retrieval, is that visual similarities might be relevant but they need to be filtered.

In that case, a text-based pre-filtering step is very important in order to select relevant visual similarities by removing images that are not relevant "semantically" despite of being similar to the image query "visually". -Combining textual similarities with text-based pre-filtered visual similarities, dramatically outperforms mono-media runs. Any of the aggregation functions used in fusing the two aforementioned runs allows us to increase both the MAP and the P@20 of the best mono-media runs. It appeared that the best aggregation strategy was the simplest one: the mean average. In that case, it improved the text run performance from MAP=20.45% to 27.65% which corresponds to more than a 35% increase.

Medical Image Modality Classification Task

Imaging modality is an important aspect of the image for medical retrieval. Therefore, within the Medical Retrieval Task in 2010 [START_REF] Müller | Overview of the clef 2010 medical image retrieval track[END_REF], a first sub-task was image modality classification. Participants were provided a training set of 2000 images that have been classified into one out of 8 modalities (CT, MR, XR etc). These images also contained captions that participants could use in addition to the visual information both at training and test time. The measure used for this sub-task was the classification accuracy.

In our experiments we investigated mono-modal and mixed modality based classification. Concerning the pure visual-based classifiers, we trained 2 linear classifiers per modality (using the one-versus-all scheme) corresponding to the two different low level features (ORH and COL). Linear SVM classifiers with hinge loss using the primal formulation were trained with the Stochastic Gradient Descent (SGD) algorithm5 using the Improved Fisher Vectors (IFV) as described in section 3 and a single spatial layout (1x1). The SVM scores were combined by weighted averaging color and SIFT features for color images. We only used the ORH based IFV for gray-scale images. The weights for each modality were tuned by maximizing classification accuracy using a 5-fold cross validation scheme on the training set.

Concerning our text based modality classification, we used two different representations and hence two classifiers. The first one was based on a pattern matching (PM) technique where we searched for the modalities in the image captions. The second one was based on a binarized bagof-words representation.

The pattern matching was based on the information describing the modalities in the modal-ityClassificationREADME.txt file. Indeed, this file provides for each modality a description that contains a list of expressions mainly related to image sub-modalities grouped in that category (i.e. the PX modality description "PX: optical imaging including photographs, micrographs..." contains expressions "PX","optical imaging", "photograph", "micrograph"...). Therefore, for each image, we detected (matched) these expressions in the corresponding captions. However, within the corpus, many documents contain several images with the same caption while the latter do not necessarily have the same modalities. Therefore, we reduced6 the image caption for a targeted image name, to:

sentences related to the image reference 7 , sentences containing multiple image references including the targeted one, and the introductory sentences (all sentences before the first occurrence of an image reference).

Consequently, the outputs of the pattern matching (PM) decision function can be a single modality, a set of potential modalities or an empty set.

The binarized bag-of-words representation consisted in a vector indicating for each word whether it appears in this document or not (in our case image caption). Note that for this representation we did not apply the aforementioned caption reduction but used them as they were provided. The feature vectors of the training set made of 2000 items with their modality labels, were then used to train a classifier per modality (one-versus-all scheme). The aim of this representation was to go beyond pattern matching and learn other words related to different modalities. To train the linear classifiers we used the logistic regression classifier (LRC) from the liblinear toolkit 8 with Laplace Prior (L1 norm).

To combine the outputs of the two classifiers, we proceeded as follows:

-If we have no output from PM, the modality is given by:

c * = arg max c∈C s c T (I) (11)
where s c T (I) is the output of the classifier LRC trained for the modality c.

-If PM outputs one or more modalities and c * is amongst them, the modality is again c * .

-Otherwise the modality amongst the PM outputs that has the highest score s c (I) was selected (C in equation 11 is reduced to the PM outputs).

In the case of mixed modalities, we first combined the LRC scores with the SGD visual scores (both normalized to get values between 0 and 1) before combining with the PM output as described above (s c T (I) is replaced by the combined scores in equation 11). The results of the different classifiers are shown in Table 2. As these results show, the pure text modality classifier slightly outperforms the visual only information based classifier and both of them were outperformed by the combination of visual and textual modalities.

Medical Ad-hoc Image Retrieval Task

For this task [START_REF] Müller | Overview of the clef 2010 medical image retrieval track[END_REF] the participants were given a set of 16 textual queries with 2-3 sample images for each query. The queries were classified into textual, mixed and semantic queries, based on the methods that are expected to yield the best results. The results of the modality classification can be used to filter the search in this sub-task. However, instead of filtering we preferred to aggregate the classification scores with the retrieval scores as explained below.

In our experiments we wanted to investigate both mono-modal and mixed-modality retrieval.

Visual Only Concerning the pure visual retrieval, in contrast to our Wikipedia runs, we used only the 3 Improved Fisher Vector (IFV), corresponding to the orientation histograms (ORH) with the 3 spatial-layout (1x1, 2x2, 1x3). The 3 IFVs were used independently to rank the Wikipedia images using the dot product as similarity measure and the 3 scores were simply summed 9 and then normalized to be between 0 and 1. We denote this score by s V R (I) (visual retrieval score). This score was then further combined with the visual only modality score as follows:

-First the query images were classified by the SGD classifiers using c * k (t) = arg max c∈C s c SGD (I t k ), where c * k (t) is the modality assigned to the image I t k of the topic t.

-If for all images I t k in a topic (if multiple image query) the same modality c * was assigned, the scores s c * SGD (I) were added to s V R (I) to rank the images of the dataset. The aim was to boost the scores of the images corresponding to that modality.

-In contrast, if we had difficulty to retain a given modality (as e.g. for the last topics) we preferred to rank the images based only on the retrieval scores s V R (I).

The performance of this run shown in line 1 of Table 3 is very poor, leading to the conclusion that visual only information is insufficient to address the task.

Text Only Concerning the textual retrieval, we submitted two types of text-only retrieval. For the first one, we simply ranked the text corresponding to some cross-entropy-based text similarity or Relevance Score Vector between the query text and the image caption. For the second, we aggregated these scores with text-only classification scores. First we describe a few textual retrieval runs (see section 2 for technical details). Several such textual runs can be created depending on:

-Different information retrieval models: Language Model or log-logistic model (the latter was used if LOGIT or LGD appears in the run names, the former otherwise). -Different smoothing parameters: we mostly used the classical Jelinek-Mercer interpolation except for the run DIR TXT (line 2) where the Dirichlet smoothing was used. -Different query and document enrichment models: statistical translation model (referred to as AX) and/or10 using the Wikipedia Corpus (referred to as WIKI). -Different statistics: using Chi2 with the log-logistic model is referred as CHI2 LOGIT and using Chi2 statistics instead of GI-M3 in the statistical translation model is referred as CHI2AX.

While only a single pure text retrieval run was submitted (line 2), nevertheless, we describe them here since they were used (referred to as textual retrieval score with s T R (I)) in the combination with the modality classification outputs and/or with the visual retrieval scores (see below). To aggregate the textual retrieval scores s T R (I) with the text based modality scores, we first extracted the modality c from the query text by pattern matching (PM) and selected the corresponding s c LRC (I) score 11 (see section 4.2). If no modality is found, only the s T R (I) is used to rank. Two such runs were submitted (lines 3 and 4 in Table 3). While not directly comparable, we can nevertheless see that these runs led to better performances than DIR TXT suggesting that combining text retrieval with modality classification helps. Furthermore, WIKI AX MOD late led to a much better MAP than CHI2AX MOD late, showing the benefit of using external data (Wikipedia) for query expansion.

Mixing Textual and Visual Information Finally, we further used both visual and textual information. We also experimented with further combining these scores with modality classification scores as follows: w V s V R (I) + w M s c LRC (I) + w T (t)s T R (I).

Here s V R (I) and s T R (I) are the normalized visual and textual retrieval scores (see above) and s c LRC (I) is the output of the image modality classifier for the modality c using only textual information (LRC scores). The modality c is extracted from the query text of topic t by pattern matching (PM) and s c LRC (I) is set to zero if no modality was found. We made the weights of the textual retrieval score w T (t) dependent on the type of topic t. Hence, we used 0.5 for topics with query type V isual, 1 for type M ixed and 1.5 for type Semantic, in order to increase or decrease the importance of the textual score. The weights w V and w M took values 1 or 0. Hence setting w V to 0 lead to pure textual based retrieval runs discussed above (such as WIKI AX MOD late and CHI2AX MOD late depending on the s T R (I) used). If we further set w M to 0, we get runs without using the modality (e.g. DIR TXT). If we set w V = 1 and w M = 0 we get the classical late fusion (e.g. AX LGD IMG late) and setting w V = 1 and w M = 1 we get a late fusion based on textual and visual retrieval scores combined with modality classifier scores (CHI2 LOGIT IMG MOD late, WIKI LGD IMG MOD late).

Finally the runs AX rerank and AX rerank comb consist in ranking images based on s T R (I) and then re-ranking the top N=1000 relevant images using respectively s V R (I) and s V R (I) + w T (t)s T R (I).

The MAP, bPref and P10 results of the runs described above are shown in Table 3. These results show that the poor performance of image retrieval for this task, decreases the performances when the visual modality is not appropriately combined with the other modalities (as in AX rerank or WIKI AX IMG MOD late). We can also note that the run AX rerank comb obtained the best performance on (MAP and bPref) while the run WIKI AX MOD late has the best performing P10 among all runs.

However, it is difficult to make conclusions about these runs that performed better than others from this table. Indeed, we need to evaluate different text runs with and without combining them with modality classifier and/or visual retrieval scores. Our intention is to do such analysis as soon as the image relevance scores are made available by the organizers.

Conclusion

This year we have participated with success in two new main tasks, namely the Wikipedia Retrieval Task and two sub-tasks of the Medical Retrieval Task (Image Modality Classification and Ad-hoc Retrieval). In all cases, we obtained leading positions both in retrieval and modality classification, and for each type of run: text-only, visual-only and mixed. We achieved excellent text based retrieval results and despite the fact that pure visual based retrieval led to poor results, when we appropriately combined them with our text ranking we were able to outperform the latter showing that multi-modal based systems can be better than mono-modal ones.

  w d i (the derivatives according to the weights), G I λ is the concatenation of the derivatives G I µ d i and G I σ d i and is therefore N = 2M D-dimensional.

Table 1 .

 1 Wikipedia retrieval: overview of the performances of our different runs. For reference we have included the best performing run from the other participants (line 17).

	RUN

Table 2 .

 2 Modality Classification task: overview of the performances of our different runs. For reference we have included the best performing run from the other participants (fourth line).

	RUN	Modality	ACC
	XRCE MODCLS COMB Mixed (textual + visual) 0.94
	XRCE TXT	Textual	0.90
	XRCE VIS	Visual	0.87
	best non-XRCE run	Mixed	0.93

Here we use Jelinek-Mercer interpolation but we can also use e.g. Dirichlet smoothing instead.

The Information Gain, aka Generalised (or average) Mutual Information[START_REF] Bernard | Information et analyse des données[END_REF], is used for selecting features in text categorisation[START_REF] Yang | A comparative study on feature selection in text categorization[END_REF][START_REF] Forman | An extensive empirical study of feature selection metrics for text classification[END_REF] or detecting collocations[START_REF] Dunning | Accurate methods for the statistics of surprise and coincidence[END_REF].

An implementation is available on Léon Bottou's web-page: http://leon.bottou.org/projects/sgd.

When it was possible to detect automatically.

For example references might be (a) or (a-c)

http://www.csie.ntu.edu.tw/ ~cjlin/liblinear/

Note that, due to the linearity property of the dot product, this is equivalent to the dot product of the concatenation of all three IFV vectors.

Note that WIKI AX means that we combined the lexical entailment based scores with the scores obtained with Wikipedia based query expansion to obtain sT R(I ) for further fusion.

This is the output of the LRC image modality classifier trained on the binarized bag-of-word feature vectors for the modality c.

Acknowledgments

This work was partially supported by the European Project PinView FP7/2007-2013 and the French National Project Fragrances ANR-08-CORD-008. We would like also to acknowledge Craig Saunders for his proofreading and useful comments on the paper.