Brice Augustin

Xavier Cuvellier

Benjamin Orgogozo

Fabien Viger

Timur Friedman

Matthieu Latapy

Clémence Magnien

Renata Teixeira

Cl Émence Magnien

Avoiding traceroute anomalies with Paris traceroute

Keywords: C, 2, 3 [Computer Communication Networks]: Network Operations Measurement traceroute, load balancing

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

INTRODUCTION

Jacobson's traceroute [START_REF] Jacobson | traceroute[END_REF] is one of the most widely used network measurement tools. It reports an IP address for each network-layer device along the path from a source to a destination host in an IP network. Network operators and researchers rely on traceroute to diagnose network problems and to infer properties of IP networks, such as the topology of the internet.

This paper describes how traceroute fails in the presence of routers that employ load balancing on packet header fields. The failures lead to incorrect route inferences that may mislead operators during problem diagnosis and result in erroneous internet maps. We provide a new publiclyavailable traceroute, called Paris traceroute1 , which controls packet header contents to obtain a more precise picture of the actual routes that packets follow.

BUILDING A BETTER TRACEROUTE

This section first describes the deficiencies of the classic traceroute in the face of load balancing. Then we present our new traceroute, Paris traceroute, which avoids some of these deficiencies, notably the ones induced by per-flow load balancing.

Traceroute and load balancing

Network administrators employ load balancing to enhance reliability and increase resource utilization. They do so through the intra-domain routing protocols OSPF [START_REF] Moy | OSPF Version 2[END_REF] and IS-IS [START_REF] Callon | Use of OSI IS-IS for Routing in TCP/IP and Dual Environments[END_REF] that support equal cost multipath. An operator of a multi-homed stub network can also use load balancing to select which of its internet service providers will receive which packets [START_REF] Quoitin | Interdomain traffic engineering with BGP[END_REF].

Routers can spread their traffic across multiple equal-cost paths using a per-packet, per-flow, or per-destination policy [START_REF]How does load balancing work?[END_REF][START_REF] Juniper | Configuring load-balance per-packet action[END_REF]. In per-flow load balancing, packet header information ascribes each packet to a flow, and the router forwards all packets belonging to a same flow to the same interface. A natural flow identifier is the classic five-tuple of fields from the IP header and either the TCP or UDP headers: Source Address, Destination Address, Protocol, Source Port, and Destination Port. We found through our experiments that routers use various combinations of these fields, as well as three other fields: the IP Type of Service (TOS), and the ICMP Code and Checksum fields. We leave an exhaustive study of which header fields serve for load balancing, and in precisely which ways, to future work.

Per-flow load balancing ensures that packets from the same flow are delivered in order. Per-packet load balancing makes no attempt to keep packets from the same flow together, and focuses purely on maintaining an even load. Per-destination load balancing could be seen as a coarse form of per-flow load balancing, as it directs packets based upon the destination IP address. But, as it disregards source in-formation, there is no notion of a flow per se. As seen from the measurement point of view, per-destination load balancing is equivalent to classic routing, which is also per destination, and so we will not explore it here.

Where there is load balancing, there is no longer a single route from a source to a destination. In the case of perpacket load balancing, a given packet might take any one of a number of possible routes. With per-flow load balancing, the notion of a single route persists for packets belonging to a given flow, but different flows for the same sourcedestination pair can follow different routes. Designing a new traceroute able to uncover all routes from a source to a given destination would be a significant improvement.

Classic traceroute is not adequate to the task, as it cannot definitively identify one single route from among many. It suffers from two systematic problems: it fails to discover true nodes and links, and it may report false links. These problems arise because traceroute discovers hops along a route with a series of probe packets, and the fact that a a load-balancing router, or load balancer, can direct these probes along different paths.

Our explanation of the problems draws on the example in Fig. 1. Here, L is a load balancer at hop 6 from the traceroute source, S. On the left, we see the true router topology at hops 6 through 9. Circles represent routers, and each router interface is numbered. Black squares depict probe packets sent with TTLs 6 through 9. They are shown either above the topology, if L directs them to router A, or below, if L directs them to router B. On the right, we see the topology that would be inferred from the routers' responses. Missing nodes and links. Because routers B and C send no responses, nodes B0 and C0 are not discovered, and links such as (L0, B0) and (B0, D0), cannot be inferred.

False links. L directs the probe with initial TTL 7 to A and the one with initial TTL 8 to B, leading to the mistaken inference of a link between A0 and D0.

Classic traceroute sends three probes per hop, rather than one, but these problems do not go away. On a traceroute through the example topology, with purely random load balancing, the probability is 0.5 3 × 2 = 0.25 that one of the two devices at hop 7, A or B, goes undiscovered. Similarly, the probability is 0.75+0.25×0.75 = 0.9375 that two devices are discovered at hop 7 or hop 8, or both, making it ambiguous which links are true and which are false.

In the general case, there may be more than two next-hop interfaces following a load balancer. For instance, the newer Juniper routers permit up to sixteen equal-cost paths. It is certain that classic traceroute misses many nodes, and the possibility to infer many links, and that it has many ways to infer false links.

Topology inference systems based on traceroute handle these problems in different ways. Huffaker et al. recognize the problem for skitter [START_REF] Huffaker | Topology discovery by active probing[END_REF], but they do not report a solution. In practice, the arts++ tool for reading skitter data reports only the first address obtained for each hop. With Rocketfuel [8], Spring et al. attribute a lower confidence level to links inferred from hops that respond with multiple addresses. Still, they include all these links in the database from which they construct a network's topology. Their hope is that a subsequent alias resolution step will eliminate at least some of the false links. However, this only works if load balancing takes place over multiple links between the same pair of routers.

Where there is per-flow load balancing, traceroute's own behavior causes the problems. When sending UDP probes, it systematically varies the Destination Port field. When sending ICMP Echo probes, it varies the Sequence Number field. It does so because it needs to match routers' responses with the probes that elicited them. A router that sends an ICMP Time Exceeded response encapsulates the IP header of the packet that it discarded, plus the first eight octets of data [9, p.5], which, in the case of UDP or ICMP Echo probes, means the transport-layer header. A unique value in the probe header ensures a uniquely tagged response. Unfortunately, as we have found in our experiments, varying any field in the first four octets of the transport-layer header amounts to changing the flow identifier for each probe. The Destination Port field is in the first four octets of the UDP header, and, though the Sequence Number field is in the second four octets of the ICMP Echo header, varying this field varies the Checksum field, which is in the first four octets.

A new traceroute

We introduce Paris traceroute, a new traceroute designed for networks with load balancing routers. Its key innovation is to control the probe packet header fields in a manner that allows all probes towards a destination to follow the same path in the presence of per-flow load balancing. It also allows a user to distinguish between the presence of per-flow load balancing and per-packet load balancing. Unfortunately, due to the random nature of per-packet load balancing, Paris traceroute cannot perfectly enumerate all paths in all situations. But it can do considerably better than the classic traceroute, and it can flag those instances where there are doubts.

Maintaining certain header fields constant is challenging because traceroute still needs to be able to match response packets to their corresponding probe packets. Paris traceroute does this by varying header fields that are within the first eight octets of the transport-layer header, but that are not used for load balancing. For UDP probes, Paris traceroute varies the Checksum field. This requires manipulating the payload to yield the desired value, as packets with an incorrect checksum are liable to be discarded. For ICMP Echo probes, Paris traceroute varies the Sequence Number field, as does classic traceroute, but also varies the Identifier field, so as to keep constant the value for the Checksum field.

Paris traceroute also sends TCP probes, unlike classic traceroute, but like Toren's variant tcptraceroute [START_REF] Toren | tcptraceroute[END_REF]. For TCP probes, Paris traceroute varies the Sequence Number field. No other manipulations are necessary in order to maintain the first four octets of the header field constant. Paris traceroute's TCP probing is not innovative in the same way as its UDP and ICMP Echo probing, as tcptracer-oute already maintains a constant flow identifier. In order to more easily traverse firewalls, tcptraceroute by default sets probes' Destination Port field to 80, emulating web traffic, and varies the Identification field in the IP header. However, no prior work has examined the effect, with respect to load balancing, of maintaining a constant flow identifier for probe packets.

Fig. 2 summarizes the IP, UDP, ICMP Echo, and TCP header fields that are used by load balancers, classic traceroute, tcptraceroute, and Paris traceroute. We do not label the ICMP Type field as used for load balancing, because, in our experiments, routers have not sent responses to ICMP probes of any type other than ICMP Echo. Based on our experiments with UDP, TCP, and IPSec probes, we nonetheless are inclined to believe that routers blindly employ the first four octets in the transport-layer header for per-flow load balancing. In addition to fixing the flow identifier problem, Paris traceroute provides additional information that helps a user recognize certain other traceroute anomalies. The probe TTL is the TTL that is found in the IP header of the probe packet that is encapsulated in the ICMP Time Exceeded response. This value corresponds to the probe's TTL when the router received it and decided to discard it. Under normal traceroute behavior, this value is one. A value other than one signals an anomaly. The response TTL is the TTL from the IP header of the Time Exceeded response itself. This value, available also through classic traceroute, helps us infer the length of the return path. Finally, the IP ID is the Identification field from the IP header of the Time Exceeded response. This field is set by the router with the value of an internal 16-bit counter that is usually incremented for each packet sent. The IP ID can help identify the multiple interfaces of a same router, as described in the Rocketfuel work [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF], or uncover different routers and hosts hidden behind a firewall or a NAT box, as described by Bellovin [START_REF] Bellovin | A technique for counting NATted hosts[END_REF].

MEASUREMENT SETUP

To study traceroute anomalies, we conduct side-by-side measurements with classic traceroute and Paris traceroute.

These experiments form a case study showing how Paris traceroute finds more accurate routes and yields knowledge concerning the causes of each anomaly. As observations from other vantage points towards other destination sets would reveal different numbers, the particular values from this study cannot be considered statistically representative.

Our measurement source is located at the LIP6 laboratory of the Université Pierre et Marie Curie, in Paris, France. The university has only one connection to the internet via the French academic backbone, Renater. We measured during one month, from 12 June to 12 July, 2006.

Our destination list consists of 5,000 randomly chosen pingable IPv4 addresses, without duplicates, and in random order. We only consider pingable addresses so as to avoid the artificial inflation of traceroute anomalies in our results that would come from tracing towards unused IP addresses [START_REF] Xia | Flooding attacks by exploiting persistent forwarding loops[END_REF].

We launch 32 parallel processes that each probe 1/32 of the destination list. Each process selects a destination d from its portion of the list and proceeds as follows:

1. Trace a route to d with Paris traceroute, sending one UDP probe per hop, and waiting up to 2 sec. to receive a reply at one hop before sending a probe to the subsequent hop. For the entire sequence of probes to d, we set an unchanging five-tuple, with Source and Destination Port values chosen at random from the range [10,000, 60,000]. We set the minimum TTL to two, to skip the routers inside the university network.

2. Trace a route to d using an instance of classic traceroute, using the same timing parameters as Paris traceroute. We use NetBSD traceroute version 1.4a5, also sending one UDP probe per hop. As per traceroute's default behavior, the Source Port value is set to the running process identifier (PID) plus 32,768, and the initial Destination Port value is set to 33,435, and is incremented with each probe sent.

No trace contains more than eight consecutive non-responses or extends further than 39 hops. Receipt of an ICMP Destination Unreachable response terminates a trace immediately.

One round of measurements to all destinations takes approximately one hour and eleven minutes, at a rate of approximately 27.3 seconds for both a Paris traceroute and a classic traceroute to a given destination. We perform consecutive rounds of measurements, and the results presented here are based on the 556 rounds that we completed during our observation period.

For the 90 million responses that contain valid IP Source Address values, we map the address to an AS number using Mao et al.'s technique [START_REF] Mao | Scalable and accurate identification of AS-level forwarding paths[END_REF]. Our traces cover 1,122 different ASes, which corresponds to five percent of the ASes in the internet today. Our traces traverse all nine tier-1 ISP networks and 64 of the one hundred top-20 ASes of each region according to APNIC's weekly routing table report 2 . Invalid IP addresses account for 19 thousand responses. The probes that did not receive a response are called stars, as they appear as such ('*') in traceroute output. Stars typically appear at the ends of routes, with just 2.6 million appearing in the midst of responses.

ANOMALIES

We focus our observations on three topology anomalies that we observe in measured routes, which we call loops, cycles, and diamonds. We will see that these anomalies largely disappear when routes are measured with controlled header fields. We observe load balancing, and the changes that come from tracing with Paris traceroute, in seven of the nine tier-1 ASes, and in 17 of the 64 top regional ASes through which we trace.

Throughout this section, we define a measured route to be the ℓ-tuple R = (r0, • • • , r ℓ ) where r0 is the source address, and, for each i, 1 ≤ i ≤ ℓ, ri stands either for the IP address received when probing with TTL i, or for a star if none was received. Our formal definition, or signature, of each anomaly is in terms of the addresses seen in measured routes. We may see multiple instances of a loop, cycle, or diamond with a given signature.

Loops

In some measured routes, the same node appears twice or more in a row: we call this a loop. Formally, a loop is observed on IP address ri with destination d if there is at least one measured route towards d containing • • • , ri, ri+1, • • • with ri = ri+1. The term 'address' implies that ri is not a star. A loop's signature is a pair (r, d), where r is the address involved in the loop and d is the destination. In the normal course of routing, a router does not forward a packet back to the incoming interface. Hence, loops are most likely an artifact of the measurement itself.

Possible causes

One cause of loops is load balancing on paths with different lengths. Fig. 3 depicts an example where the load balancer L forwards the probes having initials TTL 7 and 8 to router A and the probe having initial TTL 9 to router B, resulting in two responses from the same router, E. (We assume, for this example, that both responses are generated from the same interface, E0.) The same scenario could arise due to a routing change that forced packets from the path through A to the one through B in the middle of a traceroute. In particular, this occurs if the routing change happens between the time S receives the response to its probe with TTL 8 and the time that it emits the probe with TTL 9.

Not all loops are caused by load balancing or routing changes, however, and we found several other explanations:

Unreachability message. This type of loop arises when a router is unable to forward probes, perhaps due to failures or routing instabilities. The router treats as normal the first probe that it receives, with TTL equal to one, and generates an ICMP Time Exceeded reply. But a subsequent probe that arrives at the router, with TTL greater than one, causes an ICMP Destination Unreachable response. In such a circumstance, classic traceroute outputs the same address for each response. If not interpreted correctly, it appears to be a loop. Both classic traceroute and Paris traceroute will flag the second response with '!H' or '!N', for host or network unreachable, and then halt. When a loop appears at the end of a measured route, we look for these flags to identify this scenario.

Zero-TTL forwarding. This explanation is mentioned in the traceroute manual, which says that misconfigured routers forward packets with a TTL equal to zero, whereas they are supposed to drop them and generate an ICMP Time Exceeded response. Fig. 4 to be dropped by F , but instead it is forwarded to router A, which sends a response with probe TTL zero. (See the definition of "probe TTL" at the end of Sec. 2.2.) Then, in response to the subsequent probe, A sends a normal response, with probe TTL one.

When there is a loop, we check for zero-TTL forwarding by looking at the probe TTL. We check that the first of the two ICMP Time Exceeded responses that form a loop has a probe TTL equal to zero and the second a probe TTL of one. The examination of the IP IDs from the two reply packets should indicate that they come from the same router.

Address rewriting. Gateway routers, like NAT boxes and some firewalls, replace the Source Address field of all ICMP packets that originate within the subnetwork to which it is attached with a single IP address. Hence, all probes to a destination behind such a gateway will appear to come from the same router. In practice, we find such loops only at the end of measured routes. We detect address rewriting using the response TTL (see the definition at the end of Sec. 2.2) and the IP ID of all packets involved in the loop. All ICMP messages generated by a router will have the same initial TTL (most routers use the default TTL for ICMP, which is 255). If the response TTL is different at each hop, then the responses are likely to come from different routers. The example in Fig. 5 presents a network with a NAT box N , and routers B and C behind this NAT box. We assume that all routers use the default initial TTL and we indicate the response TTL for each hop below the respective probe. Even though the responses to probes with initial TTLs 7, 8, and 9 all indicate N0, the response TTL decreases because the routers are indeed further away. We can verify that a loop corresponds to a NAT box using the IP ID.

Statistics

Loops appear to be surprisingly common: 5.3% of the measured routes contained at least one of them. Moreover, loops were observed on routes towards 18% of the destinations, and 6.3% of all the addresses discovered in our traces were in a loop at least once. These last two values will grow if the measurements last longer, because new loops constantly appear, even after a month of probing. This effect is related to the observation that many loop signatures are rare: 18% of them were observed on only one round of measurements among 556.

We compared the traces obtained with classic traceroute and with Paris traceroute. The loops that are caused by per-flow load balancing are absent from the latter, and we estimate the proportion of such loops to be 87%. This value is necessarily imprecise, as routing dynamics may cause each traceroute to see slightly different paths, with different quantities of loops of each possible type. For instance, a small portion of loops, equivalent in quantity to 0.25% of the loops seen by classic traceroute, were seen only by Paris traceroute. By conducting the two traceroutes for each destination close together in time, we hope to have minimized the impact of routing dynamics.

Having filtered out loops due to per-flow load balancing, it was possible to ascribe other causes to many of the rest. Zero-TTL forwarding explained 6.9%, Unreachability messages explained 1.2%, and address rewriting explained 2.8% of the loops. We suppose the remaining 2.5% of loops to be caused by per-packet load balancing, but as of yet we cannot verify such an assertion.

Cycles

Formally, a measured route R is said to be cyclic on an IP address r if it contains r at least twice, separated by at least one address r ′ distinct from r. This distinction ensures that we do not misinterpret possible loops as cycles. A cycle's signature is a pair (r, d) such that at least one measured route towards d is cyclic on r.

Possible causes

Just as loops can be generated by load balancing over paths that have a length difference of one, load balancing is also a possible cause for cycles when the difference in path lengths is greater than one. Similarly, an unreachability message (described in Sec. 4.1) issued by a router that has already appeared in the measured route can be responsible for a cycle. Finally, packets may truly follow cyclic routes when they are caught in a forwarding loop, which may happen during routing convergence.

We identify cycles caused by load balancing and unreachability messages in manners similar to the ways described in Sec. 4.1. To identify cycles that were induced by forwarding loops, we looked for some periodicity in the measured routes: we should repeatedly observe a fixed sequence of addresses. Paris traceroute also allows us to infer that all appearances of a given address indeed come from one router, by check-ing that the IP ID contains values that increment, and by a relatively small amount, with each cycle. We can infer in the same way that different addresses come from different routers.

Statistics

Cycles are less common than loops: they appear on only 0.84% of the measured routes. On the other hand, they appear on a broader range of the nodes: we observe cyclic measured routes towards 11% of the destinations, and the cycles concern 3.6% of the IP addresses discovered during our experiment. They are rarer events than loops: we observe 30% of cycle signatures on only one measurement round among 556. Overall, we observe each cycle signature in only 6.8 measurement rounds on average, or in 1.2% of the rounds.

By comparing the traces obtained with classic traceroute and Paris traceroute, we estimate that 78% of the cycles seen by classic traceroute are due to per-flow load balancing. Forwarding loops explained 20%, and unreachability messages explained 1.2% of the cycles. We suppose the remaining 1.1% of loops to be caused by the use of fake IP addresses and by per-packet load balancing, but as of yet we do not have a reliable method to prove these assertions.

Diamonds

Whereas loops and cycles can appear when we probe, as we do, with only one probe per hop, diamonds can only arise if probing involves multiple probes per hop. To study diamonds, we created two graphs for each of the 5,000 destinations: one composed from all the classic traceroutes towards that destination, and the other from the Paris traceroutes. Within a graph, a diamond 's signature is a pair (h, t) of IP addresses, such that there are k ≥ 2 IP addresses r1, . . . , r k seen on measured routes of the form . . . , h, ri, t, . . .. Fig. 6 presents, on the left, a network with a load balancer L that splits packets along three different paths. On the right, we see one possible outcome from classic traceroute sending three probes per hop. For clarity, we omit the probe packets. The ordered pairs (L0, D0), (L0, E0), (A0, G0) and (B0, G0) are diamonds. Note that (C0, G0) is not a diamond because there is only one interface, D0, between C0 and G0. Space does not permit us here to describe our observations of Possible traceroute outcome: more complex diamond-like anomalies, such as those having greater lengths.

Hop #6 Hop #8 Hop #7 Hop #9 3 0 1 0 0 1 0 3 1 0 0 1 1 2 1 0 1 0 1 2 0 0 0 0 0 0 0 A A B E B E C L C F L G D D G

Possible causes

The main cause for the apparition of diamonds is load balancing. As presented in Sec. 2 (see Fig. 1), load balancing can cause traceroute to report false links, and we can easily have cases in which we falsely detect all possible links between interfaces at successive hop levels, inducing the appearance of diamonds. So although a small portion of the diamonds can be attributed to the true topology of a load-balanced network, we expect most diamonds to be a consequence of the false links inferred from classic traceroute, and to reflect an erroneous view of the network.

Statistics

Diamonds are quite frequent. They are observed towards 79% of the destinations. Overall, we see 16,385 diamonds in our traces. When comparing this with the traces obtained with Paris traceroute, we estimate that 64% of the diamonds seen by classic traceroute are due to per-flow load balancing. Per-packet load balancing could explain most of the remainder, though we have as yet been unable to verify this.

RELATED WORK

The principal variants on Jacobson's traceroute [START_REF] Jacobson | traceroute[END_REF] are Gavron's NANOG traceroute [START_REF] Gavron | NANOG traceroute[END_REF] and Toren's tcptraceroute [START_REF] Toren | tcptraceroute[END_REF]. NANOG traceroute labels IP addresses with the numbers of the ASes to which they belong. Tcptraceroute sends TCP probes, rather than the classic UDP or ICMP Echo probes, using Destination Port 80 to emulate web traffic and thus more easily traverse firewalls. As described in Sec. 2.2, this has the effect of maintaining a constant flow identifier. However, no prior work has looked at the use of a constant flow identifier to avoid traceroute anomalies.

Although there is an extensive literature on internet maps, and much work that uses traceroute, there have been few studies of anomalies as seen from the perspective of traceroute. Paxson's work on end-to-end routing behavior in the internet [START_REF] Paxson | End-to-end internet packet dynamics[END_REF] uses traceroute to study routing dynamics, including "routing pathologies". Although some of these pathologies do relate to the traceroute anomalies we discuss in this paper (for instance, "routing loops" are one cause of "cycles", and "fluttering" is one cause of "diamonds"), his work focuses on the routing aspect of the anomalies and not on traceroute's deficiencies. Huffaker et al. [START_REF] Huffaker | Topology discovery by active probing[END_REF] recognize that load balancing is an issue for constructing internet maps. Their work does not elaborate on the errors induced by load balancing or on a solution for the problem. Teixeira et al. [START_REF] Teixeira | In search of path diversity in ISP networks[END_REF] examine inaccuracies introduced into ISP maps obtained by Rocketfuel [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF]. Their paper quantifies differences between the true and the measured topologies, and identifies routing changes in the midst of individual traceroutes as being responsible for a portion of the false links in the measured topologies, but does not touch on load balancing.

CONCLUSION

This paper makes the following contributions: (i) identification of the roles that packet header fields play in load balancing, and their interactions with classic traceroute; (ii) description of Paris traceroute, a new traceroute tool that allows more precise measurements of a route, and helps determine the causes of a number of traceroute anomalies; (iii) definition and characterization of three anomalies that appear in individual or repeated traceroute measurements: loops, cycles, and diamonds; and (iv) enumeration of possible causes for each of these anomalies and elaboration of experiments that test our hypothesis.

This work should inspire future research in many directions. We believe that we can improve Paris traceroute through the addition of algorithms to automatically find all interfaces of a given load balancer, and to differentiate per-flow from per-packet load balancers. Then, a study with more sources and more destinations would allow us to characterize the prevalence and characteristics of load balancers in the internet. This data would also serve to better quantify anomalies, including others not discussed here, and the effects of Paris traceroute on internet maps.

Finally, this research opens up the possibility for applications to choose among alternate paths through the internet through careful control of their header fields. If these paths prove to have different characteristics, we will have uncovered some path diversity in the network itself, without the need for an overlay network.

Figure 1 :

 1 Figure 1: Missing nodes and links, and false links.

Figure 2 :

 2 Figure 2: The roles played by packet header fields.

Figure 3 :

 3 Figure 3: A loop caused by load balancing.

Figure 4 :

 4 Figure 4: A loop caused by zero-TTL forwarding.

Figure 5 :

 5 Figure 5: A loop caused by address rewriting.

Figure 6 :

 6 Figure 6: An example of several diamonds.

Paris traceroute is free, open-source software, available from http://www.paris-traceroute.net/.

APNIC automatically generates reports describing the state of internet routing tables. It ranks ASes for each of five world regions according the number of networks announced.

Acknowledgments

We are grateful to our shepherd Dave Andersen, to Ehud Gavron, and to the anonymous reviewers for their thoughtful comments. We also thank Neil Spring and Ratul Mahajan for their explanations of how Rocketfuel handles hops that respond with multiple interfaces. The Paris traceroute tool was developed with financial support from the French CNRS, as part of its contribution to the European Commission-sponsored OneLab project. The research using the tool was conducted with financial support from the French MNRT ACI Sécurité et Informatique 2004 grant, through the METROSEC project.


julien.monge Julien Monge

François Avellan
email: francois.avellan@epfl.ch

Integration Of Machining Constraints In Design Optimization Of A Guide Vane Cascade

Keywords: Blade Design, Geometrical Optimization, Flank Milling, Meshing Strategy, Machining Constraints

Introduction

In hydraulic turbomachinery, design optimization of blades to improve performances is an important issue. The conventional blade design and production process could be described in three steps. First, a Computer-Aided Design (CAD) modeling is done based on Computational Fluid Dynamics (CFD) simulations. Then, the tool path is computed, using Computer-Aided Manufacturing (CAM) software. Finally, blades are machined on 3 or 5-axis machine tool. The expected hydraulic performances are computed using zero defect CAD models and software [START_REF] Ferrando | Surface parameterization and optimum design methodology for hydraulic turbines[END_REF]. On another hand, blade functional surfaces are made of freeform surfaces, obtained by high added value machining operations, like 5-axis milling. As machining constraints are not taken into account in the design step, difficulties come in the tool path computation and tool path interpolation [START_REF] Pechard | Geometrical deviations versus smoothness in 5-axis flank milling[END_REF] and, in the end, hydraulic performances are not those expected. In this paper, a new approach is proposed to design hydraulic blades based on machining considerations and applied to guide vane design.

Main Idea

In order to avoid geometrical deviations between machined blades and the CAD model, the proposed approach consists in taking into account machining constraints at a very early stage in the CAD modeling. In the proposed paradigm, the machining tool path is placed on the heart of the design process [START_REF] Duc | A new concept for the design and the manufacturing of free-form surfaces: the machining surface[END_REF]. The polynomial machining tool path is computed so that the machined blade, not the CAD model, is optimum with respect to the hydraulic performances. Then, the optimization validates the surface geometry resulting from a machining simulation (Z-buffer simulation) and CAD model is the 3D representation of this simulation. Manufacturing is easier, faster, geometric quality and perceived quality are improved and hydraulic performance should meet expectations.

The proposed work focuses on the comparison between the standard optimization process, called "Design", and the proposed approach called "Toolpath" based on the polynomial description of the tool trajectory using flank milling. Those two methods will be developed on a 2D study case: the geometric optimization of a guide vane cascade, one of the turbine parts which convert hydraulic power to electric power. The purpose of this article is to find out if performances obtained with a classic optimization (Design) and with machining constraints based optimization (Toolpath) are comparable.

The optimization process used here can be decomposed in four stages. The first stage consists in defining a parametric model of the guide vane (Design model) or of the tool trajectory during milling (Toolpath model), e.g. Fig. 1..

Fig. 1: Design and Toolpath models

In order to describe a blade geometry, several researches has looking for coherent methods [START_REF] Koini | A software tool for parametric design of turbomachinery blades[END_REF]. The choice made here is to describe the planar geometry of a blade by a camber line, a suction side and a pressure side. Those three curves are modeled with Bspline curves. In the Toolpath model, it is the tool center trajectory which is described; then, the blade geometry is deduced using a discrete inversed offset method. Machining constraints like continuity or curve order are introduced to only describe geometries, which can be machined on a standard numerical controller. The difficulty is to determine how many parameters are needed to lead to a correct model, knowing that with an important number of parameters, more complex geometries can be described. On another hand, the optimization stage is longer, because of the bigger number of input parameters.

The next stage is to define a computation domain and to develop a meshing strategy. As we are in an optimization process, a lot of computation are needed, each one with a different set of parameters. The point here is to develop a replay script which can automatically mesh all the geometries created and build a computational domain smaller as possible. Indeed, smaller the domain is, faster the computations are. So, the replay script has to adapt the mesh with the different values of the parameters and to use symmetries to reduce the domain. It leads to the definition of the "Inter Blade Channel", which is the smaller domain possible to describe the entire guide vane cascade geometry (topology and mesh for this channel are described on Fig. 2.). To control efficiently the mesh, structured mesh strategy is used. The third step is to run CFD simulation on the mesh created to determine the guide vane cascade hydraulic characteristics. Values such as "Angular Momentum" (AM, which is helpful to define hydraulic power) or "Head Losses" (HL, which helps to estimate energy losses in the guide vane cascade) are computed. A study on the computation convergence is done here to find out if mesh quality is great enough during numerical simulations.

Finally, the last step is to find the optimal geometry. We want to find the geometry which leads to a given value of AM, with a minimal value of HL. Two methods are used, parameterized and compared here: Genetics Algorithms (GA) and Kriging [START_REF] Matheron | Traité de géostatistique appliquée, Tome II : Le krigeage[END_REF]. GAs give good results, but computational times rise to unacceptable values when the number of parameters becomes too high. This is why Kriging is envisaged. This interpolation method needs fewer computations than GAs for a high number of input parameters, and leads to great results when it is correctly done.

Conclusions

In the end, this study shows that Design and Toolpath models lead to similar optimal solutions in term of hydraulic performances. Moreover, with our approach based on machining constraints integration in design process, CAD models of blades match in a better way with machined blades. Taking into account of the results obtained here, a study based on the same principle will be done with 3D geometries, considering blades with non-developable surfaces, like hydraulic runner.

Fig. 2 :

 2 Fig. 2: Inter Blade Channel structured topology and mesh


Tom Chothia

Yusuke Kawamoto

Chris Novakovic

LeakWatch: Estimating Information Leakage from Java Programs

Keywords: Quantitative information flow, statistical estimation, Java, mutual information, min-entropy leakage

Programs that process secret data may inadvertently reveal information about those secrets in their publicly-observable output. This paper presents LeakWatch, a quantitative information leakage analysis tool for the Java programming language; it is based on a flexible "point-to-point" information leakage model, where secret and publiclyobservable data may occur at any time during a program's execution. LeakWatch repeatedly executes a Java program containing both secret and publicly-observable data and uses robust statistical techniques to provide estimates, with confidence intervals, for min-entropy leakage (using a new theoretical result presented in this paper) and mutual information. We demonstrate how LeakWatch can be used to estimate the size of information leaks in a range of real-world Java programs.

Introduction

An information leak occurs when a passive observer learns something about a system's secret data by observing its public outputs. Information leaks may be a side effect of a correctly-functioning system, and pose no real threat to security (e.g., a rejected guess of a secret, high-entropy password leaks some information: that this value is not the correct password). Larger information leaks, on the other hand, may lead to a complete breakdown of security (e.g., a flawed random number generator may give an observer all the information they need to guess important secret values). It is therefore important for a designer or analyst of a system to know exactly where information leaks occur and to be able to quantify them.

Information theory is a useful mechanism for providing quantitative bounds on what an attacker can learn. The attacker's uncertainty about a system's secret data is usually represented as Shannon entropy [START_REF] Shannon | A Mathematical Theory of Communication[END_REF], and the reduction in uncertainty about the secret data is represented using a measure such as the mutual information of the secret data and publicly-observable data [START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF], or the min-entropy leakage from the secret data to the publicly-observable data [START_REF] Smith | Quantifying Information Flow Using Min-Entropy[END_REF]. Although the bounds provided by these measures are meaningful, it is tedious to manually compute them; there is therefore a need for tools that automatically and robustly detect information leakage vulnerabilities in software.

This paper presents LeakWatch, a quantitative information leakage analysis tool for the Java programming language. It is based on a "point-to-point" information leakage model in which secret and publicly-observable data may occur at any time during the program's execution, including inside complex code structures such as branches and nested loops. This model, which we developed previously using a semantics based on discrete-time Markov chains [START_REF] Chothia | Probabilistic Point-to-Point Information Leakage[END_REF], is particularly well-suited to analysing complex programs where secret and publiclyobservable data may occur at any point: if secret and publicly-observable values are "tagged" using the secret and observe commands respectively, it measures how much information a passive attacker with knowledge of the program's source code learns about the secret values by examining the observable values.

Given a Java program whose source code has been annotated with the positions where its secret and publicly-observable data occurs, LeakWatch repeatedly executes it, recording the occurrences of secret and public data, and then performs robust statistical tests to detect whether an information leak is present and, if so, estimate the size of the leak. We note that this relies on the analyst correctly identifying which values in their program should be kept secret and which other values might be observable to an attacker, but, assuming this is done correctly (a reasonable assumption for most programs), LeakWatch can be used to verify whether the program is secure, or whether it contains an information leak that could lead to an attack.

LeakWatch uses previous techniques [START_REF] Moddemeijer | On estimation of entropy and mutual information of continuous distributions[END_REF][START_REF] Brillinger | Some data analysis using mutual information[END_REF] for estimating mutual information and a new technique for estimating min-entropy leakage. These are brute-force approaches for probabilistic systems; i.e., we must run the program enough times to collect sampled data for every possible secret value. If the systems we target were deterministic, we could compute the information leakage precisely; however, since they are probabilistic, we use these statistical estimation techniques to distinguish a real information leak from noise in the measurements and to place bounds on the possible leakage.

We note that this estimation technique is quite different from those that estimate mutual information or min-entropy leakage with sampled data for only some of the possible secrets (e.g., [START_REF] Boreale | On formally bounding information leakage by statistical estimation[END_REF]). These results often require additional assumptions about the distribution of the secret values, which we do not make, and may only work for non-probabilistic systems. Practically, we can analyse systems containing tens (or, in some cases, hundreds) of thousands of secret and observable values that occur with a non-negligible probability, and in which each trial run of the system is independent and identically distributed. We show that this provides interesting results for complex systems.

We present new results for calculating when enough samples have been collected for our estimates to be accurate, and handling user (but not attacker) input to a system. We provide a full Java-based implementation of our analysis method, and illustrate its power with three realistic security-themed examples.

Other tools, such as QUAIL [START_REF] Biondi | QUAIL: A Quantitative Security Analyzer for Imperative Code[END_REF], QIF [START_REF] Mu | A tool: quantitative analyser for programs[END_REF] and our earlier CH-IMP implementation [START_REF] Chothia | Probabilistic Point-to-Point Information Leakage[END_REF], compute the leakage from small formal models of programs. A key difference in this work is that we target full Java programs, at the cost of estimating leakage instead of computing it precisely.

There are other information leakage tools built on model checkers for C and Java [START_REF] Mccamant | Quantitative Information Flow as Network Flow Capacity[END_REF][START_REF] Heusser | Quantifying Information Leaks in Software[END_REF][START_REF] Phan | Symbolic quantitative information flow[END_REF]. They require the secret values to be inputs to the program and the observable values to be the program's final outputs; they are also restricted to the subset of the language's syntax supported by the model checker. LeakWatch has neither of these constraints.

In summary, our main contributions are the following: a) a new result for estimating min-entropy leakage from trial runs of systems, as well as providing confidence intervals for those estimates using χ 2 tests; b) a technique that, given certain assumptions, ensures we have enough samples to estimate information leakage from trial runs of a system; c) LeakWatch, a robust information leakage analysis tool that can estimate mutual information and min-entropy leakage in Java programs; LeakWatch is freely available at [START_REF] Chothia | LeakWatch[END_REF], with full documentation and a range of sample Java programs. The rest of the paper is organised as follows. In Section 2 we introduce relevant theoretical background information. In Section 3 we show a new theoretical result for estimating min-entropy leakage and its confidence interval from trial runs of a system. In Sections 4 and 5 we discuss LeakWatch's design and implementation respectively. In Section 6 we show three examples of LeakWatch being used to uncover information leakage vulnerabilities in real-world Java programs.

Background

Leakage Measures and Estimating Mutual Information

Our approach assumes that trial runs of the system are independent and identically distributed; the analyst must verify that this is the case. We also assume the system has probabilistic behaviour: each run results in some secret values x ∈ X occurring from some probability distribution X, and some observable behaviour y ∈ Y occurring from some probability distribution Y . Then, for each run of the system, the probability of the secrets x occurring and the attacker observing y is given by the joint probability distribution p(x, y). The question we wish to answer is "how much does an attacker learn about the value of the secret from the observable behaviour of the system?".

We use two popular measures of information leakage: mutual information and min-entropy leakage. Mutual information is given by the equation

I(X; Y ) = x∈X ,y∈Y p(x, y) log 2 p(x, y) p(x)p(y) (1)
and tells us how much information, in bits, we learn about X by observing Y .

Min-entropy leakage is given by the equation

L(X; Y ) = log 2 y∈Y max x∈X p(x, y) -log 2 max x∈X y∈Y p(x, y) (2)
and tells us how difficult it is for the attacker to guess the secret values in one attempt, given the observable behaviour. We refer the reader to [START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF] for a more indepth evaluation of mutual information and min-entropy leakage as information leakage measures.

From trial runs of a system we can estimate the joint distribution p(x, y) and the distributions p(x) and p(y); we can use these distributions in Equation 1 to estimate the mutual information Î(X; Y ). To find bounds on the true mutual information of the secret and observable values in a system, we need to know how Î(X; Y ) relates to I(X; Y ). We have shown previously [START_REF] Chatzikokolakis | Statistical Measurement of Information Leakage[END_REF] how these values are related when the distribution on secrets is known and we estimated p(y|x); however, this case is different, in that we are also estimating p(x). This case has been studied by Moddemeijer [START_REF] Moddemeijer | On estimation of entropy and mutual information of continuous distributions[END_REF] and Brillinger [START_REF] Brillinger | Some data analysis using mutual information[END_REF], who found that: Theorem 1. When I(X; Y ) = 0, for a large number of samples n, 2n Î(X; Y ) will be drawn from a χ 2 distribution with (#X -1)(#Y -1) degrees of freedom; i.e., Î(X; Y ) has an average value of (#X -1)(#Y -1)/2n and variance (#X -1)(#Y -1)/2n 2 . Theorem 2. When I(X; Y ) > 0, for a large number of samples n, the estimates Î(X; Y ) will be drawn from a distribution with mean I(X; Y ) + (#X -1)(#Y -1)/2n + O 1 n 2 and variance

1 n  
x,y p(x, y)log 2 p(x, y) p(x)p(y) -

x,y p(x, y)log p(x, y) p(x)p(y)

2   + O 1 n 2 .
Using these results, we first test a Î(X; Y ) value against the χ 2 distribution from Theorem 1; if it is consistent with the 95% confidence interval for this distribution, we conclude that there is no evidence of an information leak in our sampled data. If Î(X; Y ) is inconsistent with the distribution from Theorem 1, we conclude that there is evidence of an information leak in our sampled data and use Theorem 2 to calculate a confidence interval for the leakage.

In both cases "a large number of samples" means enough samples to ensure that every p(x, y) is close to p(x, y), so it is important to note that this is a bruteforce approach that requires many more samples than the product of the number of secret and observable values. The contribution of the estimation results is to allow us to analyse systems that behave probabilistically.

The O(n -2 ) term in Theorem 2 is an infinite sum on descending powers of n. This term is a result of using the Taylor expansion of entropy and conditional entropy. To make use of Theorem 2 we require enough samples for the O(n -2 ) term to be small. This will always be the case for a sufficiently large n, and we address how to tell when n is large enough in Section 4.1. In practice, these results let us analyse systems with tens of thousands of unique secrets and observables.

Our Information Leakage Model

Our tool uses a "point-to-point" information leakage model, which tells us how much an attacker learns about a secret value at a particular point in a program from the program's observable outputs. This model is particularly well-suited to analysing entire programs (rather than code fragments), and it is a generalisation of the more common model of information flow that measures the leakage from high-level secret inputs of a function to its low-level public outputs [START_REF] Denning | Cryptography and Data Security[END_REF]. It is important to note that our information flow model measures the information leakage from the value of variable at a particular point in the program. This differs from (e.g.) the Jif [START_REF] Myers | Complete, Safe Information Flow with Decentralized Labels[END_REF] information flow model, which ensures that no value stored in a high-level variable ever affects the value stored in a low-level variable. We have previously [START_REF] Chothia | Probabilistic Point-to-Point Information Leakage[END_REF] developed a formal model of this information leakage, showed that it can be computed precisely for a simple probabilistic language using discrete-time Markov chains and that it can be estimated from trial runs of a program.

The LeakWatch API provides the command secret(v1) to denote that the current value of the variable v1 should be kept secret, and observe(v2) to denote that v2 is a value the attacker can observe; it is up to the analyst to decide where to place these commands. We then measure the information leakage from occurrences of v1 to occurrences of v2.

For example, consider a Java card game program in which a Card object (theirCard) is drawn from a deck and sent over an insecure socket to an opposing player. Another Card object (ourCard) is drawn from the deck and stored locally; the opponent is then given the opportunity to make a bet based on the value of theirCard. If an analyst wanted to estimate how much information a remote attacker learns about ourCard from theirCard, the code could be annotated as:

Card theirCard = deck.drawCard(); LeakWatchAPI.observe(theirCard); opponent.writeToSocket(theirCard); Card ours = deck.drawCard(); LeakWatchAPI.secret(ours); if (opponent.placedBet()) determineWinner(); This would, for example, alert the analyst to a badly-implemented random number generator in the deck-shuffling algorithm that allows the opposing player to predict the value of the next card dealt from the deck, giving them an unfair advantage when deciding whether to bet.

We note that our measure of information leakage only tells us what a passive attacker learns about the secret values by examining the observable values; it does not measure how easy the secret value is to guess (e.g., because it has low entropy). Therefore, the leakage measurement is only useful when there is uncertainty about the secret values. This could be due to secret values being randomly-generated numbers, or programs exhibiting unpredictable behaviour such as process scheduling or network timing. In cases where the secret is an input to the system, code can be added to generate a truly random value for the secret and then measure the leakage to the observable values. We give examples illustrating all of these cases in Section 6 and on the LeakWatch web site [START_REF] Chothia | LeakWatch[END_REF].

Estimating Min-Entropy Leakage

Our mutual information estimation result calculates the exact distribution of the estimates and so lets us calculate exact confidence intervals; obtaining a similar result for min-entropy leakage is difficult because of the maximum in its definition. So, to allow us to calculate this popular leakage measure, we find upper and lower bounds for a (more than) 95% confidence interval.

The estimation gives a point estimate of the leakage L(X; Y ) from a distribution X on secret values to a distribution Y on observable values, and its (more than) 95% confidence interval. We do not know the exact distribution X, so we estimate it from the trial run data. Since we do not know the exact joint probability distribution p(x, y) for the system, we first calculate the empirical joint distribution from the trial runs. Let L be the total number of trial runs, and ŝ(x, y) be the frequency of (i.e., the number of trial runs with) a secret x ∈ X and an observable y ∈ Y; then the empirical probability of having a secret x and an observable y is defined by ŝ(x,y) L . Also, let û(x) be the frequency of a secret x ∈ X ; i.e., û(x) = y∈Y ŝ(x, y); then we calculate the empirical probability of seeing x as û(x) L . Using these empirical distributions we obtain a point estimate L(X; Y ) of the min-entropy leakage:

L(X; Y ) = -log 2 max x∈X û(x) L + log 2 y∈Y max x∈X ŝ(x, y) L .
Given L independent and identically distributed trial runs, the frequency ŝ(x, y) follows the binomial distribution B(L, p(x, y)), where p(x, y) is the true joint probability of a secret x and an observable y occurring. We note that we cannot treat each of the empirical joint probabilities as independently sampled from a binomial distribution, because together they must sum to 1. Instead, we perform Pearson's χ 2 tests [START_REF] Pearson | X. on the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling[END_REF][START_REF] Diez | OpenIntro Statistics[END_REF] for a large number L of trial runs.

The estimation of a confidence interval is based on the fact that, with a high probability, each observed frequency ŝ(x, y) is close to the "expected frequency" p(x, y)L, where p(x, y) is the true probability we want to estimate. By applying χ 2 tests, we evaluate the probability that the observed frequencies ŝ(x, y) come from the joint probability distributions p(x, y). Given the observed frequencies ŝ(x, y) and the expected frequencies p(x, y)L, the χ 2 test statistics is defined by:

χ 2 = x∈X , y∈Y (ŝ(x, y) -p(x, y)L) 2 p(x, y)L .
Since the joint probability distribution is regarded as a one-way table in this setting, the χ 2 test statistics follows the χ 2 distribution with (#X • #Y) -1 degrees of freedom. We denote by χ 2 (0.05,k) the test statistics with upper tail area 0.05 and k degrees of freedom.

The goal of our new method is to obtain a (more than) 95% confidence interval of the min-entropy leakage L(X; Y ) between the secret and observable distributions X, Y . To obtain this, we estimate the 95% confidence intervals of the min-entropy H ∞ (X) = -log 2 max x∈X p(x) and the conditional min-entropy H ∞ (X|Y ) = -log 2 y∈Y max x∈X p(x, y) respectively.

We first present a method for obtaining the confidence interval of the conditional min-entropy H ∞ (X|Y ). Given L independent and identically distributed trial runs of the system, we obtain the observed frequencies ŝ. Then we construct expected frequencies s max that give the largest a posteriori vulnerability y∈Y max x∈X p(x, y) among all expected frequencies that satisfy:

χ 2 (0.05,#X #Y-1) = x∈X , y∈Y (ŝ(x,y)-smax(x,y)) 2 smax(x,y)
. More specifically, s max is constructed from ŝ by increasing only the maximum expected frequencies max x∈X ŝ(x, y) and by decreasing others, while keeping the total number of frequencies as L; i.e., x∈X ,y∈Y s max (x, y) = L. From s max we calculate the empirical distribution P post max [x, y] = smax(x,y)

L

. Next, we construct expected frequencies s min that give the smallest a posteriori vulnerability. Keeping the total number of frequencies as L, we repeatedly decrease the current maximum expected frequency and increase the smallest frequencies until we obtain χ

2 (0.05,#X #Y-1) = x∈X , y∈Y (ŝ(x,y)-smin(x,y)) 2 smin(x,y)
. Then we calculate the corresponding distribution P post min . From P post max and P post min we obtain the following confidence interval of the conditional min-entropy: Lemma 1. The lower and upper bounds for the 95% confidence interval of the conditional min-entropy H ∞ (X|Y ) are respectively given by:

H low ∞ (X|Y ) = -log 2 y∈Y max x∈X P post max [x, y], H up ∞ (X|Y ) = -log 2 y∈Y max x∈X P post min [x, y].
Next, we compute the confidence interval of the min-entropy H ∞ (X). Given the observed frequencies û, we construct expected frequencies u max that give the largest vulnerability max

x∈X p(x) such that χ 2 (0.05,#X -1) = x∈X (û(x)-umax(x)) 2 umax(x)
. We calculate the empirical distribution P prior max [x] = umax(x)

L

. Similarly, we construct expected frequencies u min giving the smallest vulnerability, and calculate the corresponding distribution P prior min . Then we obtain the following: Lemma 2. The lower and upper bounds for the 95% confidence interval of the min-entropy H ∞ (X) are respectively given by:

H low ∞ (X) = -log 2 max x∈X P prior max [x], H up ∞ (X) = -log 2 max x∈X P prior min [x].
Finally, we obtain a confidence interval for the min-entropy leakage:

Theorem 3. The lower and upper bounds for a more than 95% confidence interval of the min-entropy leakage L(X; Y ) are respectively given by:

L low (X; Y ) = H low ∞ (X) -H up ∞ (X|Y ), L up (X; Y ) = H up ∞ (X) -H low ∞ (X|Y ).
Note that our estimation technique for min-entropy leakage requires a large number of trial runs (usually many more than that required to estimate mutual information) to ensure that no more than 20% of the non-zero expected frequencies are below 5, which is a prerequisite for χ 2 tests.

Fig. 1 shows an example of mutual information and min-entropy leakage estimation; the graph is generated with 1,000 estimates of leakage from the 4diner DC-net described in depth in Section 6.1) in which the random bits are biased towards 0 with probability 0.75. The graph shows the true leakage result, the estimated results from 10,000 runs of LeakWatch, and the bounds for min-entropy leakage. Our mutual information result gives the exact distribution of the estimates and so LeakWatch calculates the exact 95% confidence interval.

In this case, we observe that the estimation of min-entropy leakage is slightly biased and that it demonstrates more variation in the range of results than mutual information, although other examples (especially examples with unique maximum probabilities) demonstrate more variation in the mutual information estimate. In all cases, our bounds for the mutual information estimate are better than our bounds for min-entropy leakage; this is because we find the exact distribution of the estimates for mutual information and so can find a more accurate confidence interval.

The Design of LeakWatch

LeakWatch is a robust tool intended for testing general-purpose, real-world Java programs where the presence of information leakage vulnerabilities may be a concern. It repeatedly executes a target program, recording the secret and observable values it encounters, and then uses the estimation results described in Sections 2 and 3 to find bounds on the information leakage from the program.

We target Java because of its enterprise popularity and common usage in large software projects. LeakWatch requires minimal modifications to be made to the target program's source code: the analyst simply inserts calls to the LeakWatch API methods, secret() and observe() (indicating the occurrence of a secret and observable value respectively), identifies the name of the main class containing the target program's main method and instructs LeakWatch to estimate the leakage from that program. The repeated execution of the program in a manner that guarantees the correctness of the leakage estimation -including handling idiosyncrasies of the Java Virtual Machine (JVM), such as class-loading -and computation of the leakage estimation are then performed by LeakWatch. As the target program is repeatedly executed, LeakWatch automatically determines whether the amount of secret and observable information gathered is sufficient to produce a reliable leakage estimation; no further user interaction is required.

An important requirement of our statistical tests is that the sampled data is independent and identically distributed. This requirement is easily fulfilled if the target program does not rely on any external state (e.g., a value read from a file) that may change between executions. Programs that rely on some external state that does not have a statistically significant effect on the observable behaviour of the program can also be analysed without modification. It may be possible to modify programs that do rely on external state (e.g., by replacing a network read with a randomly generated value) and still obtain useful results.

Collecting Sufficient Program Execution Data

For our estimation results to be meaningful, we must collect enough samples to ensure that the estimated joint distribution of the secret and observable information that occurs in the program is a close approximation of the true distribution. Recall from Theorem 2 that the mean and variance of the distribution from which mutual information estimates are drawn are both defined as Taylor series. For efficiency reasons, LeakWatch only evaluates the first-order Taylor polynomial (e.g., Î(X; Y ) -(#X -1)(#Y -1)/2n for the point estimate of mutual information). Evaluating more terms in the Taylor series is computationally expensive because the joint distribution of X and Y must be enumerated differently for each term. For a small number of samples n, it is likely that the O(n -2 ) and higher-order terms are too large for the first-order Taylor polynomial to be a good approximation of the sum of the series, and so Î(X; Y ) -(#X -1)(#Y -1)/2n will change as n increases. However, for a large enough number of samples, the higher-order terms quickly become small enough to have no meaningful effect on the result, and Î(X; Y ) -(#X -1)(#Y -1)/2n will no longer change as n increases.

Based on this observation, LeakWatch uses the following heuristic to automatically determine when a sufficient amount of trial run data has been collected to minimise the higher-order terms in the Taylor series and therefore provide an accurate mutual information estimate. It computes an estimate Î(X; Y ) after max(#X × #Y, 100) samples have been collected, and stops collecting samples if all of the following conditions are met: 1) #X , #Y > 1 (otherwise a leakage measure cannot be computed from the joint probability distribution); 2) #X and #Y have remained constant since these conditions were last checked (otherwise the values in condition 4 cannot be compared meaningfully); 3) the minimum number of samples (4 × #X × #Y) has been collected; 4) the value Î(X; Y ) -(#X -1)(#Y -1)/2n has not changed beyond a certain amount, configurable by the analyst, since these conditions were last checked (otherwise the higher-order Taylor series terms are non-negligible). If these conditions are not met, the process is repeated again when #X × #Y more samples have been collected.

This heuristic allows LeakWatch to produce accurate mutual information estimates and confidence intervals for target programs containing both small and large numbers of unique secret and observable values that occur with a nonnegligible probability. The initial number of samples max(#X × #Y, 100) prevents LeakWatch from terminating too early when analysing very small systems (e.g., those containing fewer than ten unique secret and observable values in total) due to the low value of #X × #Y in these systems.

To estimate min-entropy leakage, we need many more trial runs than we need to estimate mutual information. As mentioned in Section 3, we require that no more than 20% of the non-zero expected frequencies are below 5; LeakWatch therefore collects samples until this condition as well as the first three conditions in the above procedure for mutual information estimation are met.

Implementing LeakWatch

To test a program for information leakage, an analyst simply imports the LeakWatch API class into their Java program and tags the secret and publiclyobservable data with the API's secret() and observe() methods. Execution and sandboxing of the target program are achieved using the core Java libraries, and leakage estimates are calculated by leakiEst [START_REF] Chothia | A Tool for Estimating Information Leakage[END_REF][START_REF] Kawamoto | Compositionality Results for Quantitative Information Flow[END_REF], our information leakage estimation library for Java, which now implements our min-entropy leakage result from Section 3; this ensures that LeakWatch is not tethered to a particular version or implementation of the JVM specification.

We now discuss two implementation issues: ensuring the independence of target program executions, and automatically providing programs with simulated user input.

Ensuring the Independence of Target Program Executions

When a Java program is executed, a new JVM is created; this involves loading and uncompressing many megabytes of Java class files. To generate test data efficiently, LeakWatch uses the same JVM to execute each trial run of the program. However, ensuring that programs sharing the same JVM execute independently (a requirement for our statistical estimation method) is not trivial to guarantee.

Java programs consist of one or more classes that are loaded into memory on-demand; the task of locating the bytecode that defines a class, parsing the bytecode, and returning a reference to the new class to the caller is performed by a classloader, itself a Java class. A class with a given name may be loaded only once by a given classloader. The JVM contains three classloaders by default, arranged in a hierarchy: the bootstrap classloader loads the core Java classes (e.g., those whose names begin with java.), the extensions classloader loads the Java extension classes (e.g., those that perform cryptographic operations), and the system classloader loads other classes. This hierarchy is strictly enforced; e.g., the system classloader delegates the loading of java.lang.String to the extensions classloader, which in turn delegates it to the bootstrap classloader. By default, this means that both LeakWatch's classes and the target program's classes are loaded by the system classloader.

LeakWatch runs the target program by invoking the main method in the target program's main class and waiting for it to return. Because a class may contain static member variables, having the system classloader load the target program's classes would be problematic: LeakWatch would not be able to "reset" the value of static member variables present in the target program's classes before invoking the main class's main method again, so some state may be preserved between executions of the target program. This potentially violates the independence of trial runs.

LeakWatch solves this problem by loading target program classes with its own classloader, positioned in the hierarchy between the system classloader and any classloaders used by the target program (see Fig. 2). Before each invocation of the main class's main method, a new LeakWatch classloader is initialised; it contains only the definition of the main class. As the main method executes, the LeakWatch classloader creates a new instance of any class required by the target program; subsequent requests for the class with that name will return this instance of the class, rather than the instance that would usually be returned by the system classloader. When the main method returns, LeakWatch destroys this classloader (and therefore any class loaded by it), ensuring that earlier invocations of the main method cannot interfere with future invocations. This guarantee even holds when multiple instances of the LeakWatch classloader exist concurrently, allowing LeakWatch to perform multiple isolated invocations of the main method at the same time using multithreading.

If a class is usually loaded by either the bootstrap or extensions classloaders, the LeakWatch classloader must delegate the request to them, so all executions of the target program "see" the same copies of the Java API classes. Although information could be shared between executions in this way, it is only possible with methods in a handful of classes (e.g., java.lang.System's setProperty() method) and it is easy for the analyst to verify whether they are used.

Automatically Providing User Input to Target Programs

So that programs that rely on user input can be tested for information leakage, LeakWatch allows the analyst to specify an input strategy that provides input values to the program based on observable values that have previously occurred. To ensure independence of trial runs of the target program, we place two restrictions on LeakWatch's behaviour: only one input strategy may be defined for all trial runs, and the input values provided by the input strategy must depend only on the observable values that have occurred in the current trial run, and not in other trial runs. In previous work [START_REF] Chothia | Probabilistic Point-to-Point Information Leakage[END_REF], we proved that if a program leaks information for any input strategy then it will also leak a non-zero amount of information for the input strategy that selects all possible inputs uniformly, so the uniform input strategy is a good default strategy.

Input can be provided to Java programs in many ways. We focus on input provided via the standard input stream, a universal method of supplying data to software; in Java, this stream is accessed with the static member variable System.in of type java.io.InputStream, whose read() method returns the next byte from the input buffer.

Operating systems provide a single standard input stream to a process; this means that all classes loaded by a particular JVM read from the same System.in stream. This is problematic because LeakWatch's classes and the target program's classes all execute within the same JVM; even though LeakWatch sandboxes each execution of the target program using its own classloader, all instances of the target program will share (and therefore read from) the same input stream. This is most noticeable when using multithreading to perform multiple isolated executions of the target program concurrently: two instances of a program reading 20 bytes of input from System.in will conflict, each using the read() method to read approximately 10 bytes from the same stream. This leaves both instances of the program with meaningless input, and violates the requirement that trial runs be independent and identically distributed.

We solve both problems by transforming every target class that reads from the standard input stream to instead read from an input driver, a mock object that mimics System.in. When using LeakWatch to analyse a program that reads from the standard input stream, the analyst must also write an appropriate input driver to supply input when it is required. The purpose of the input driver is to implement the input strategy described above: like System.in, it is a subclass of java.io.InputStream, but its read() method may consult the list of observable values that have been encountered so far during execution and return a stream of bytes comprising the selected input to the target program. When classes are loaded by LeakWatch's classloader, their bytecode is dynamically transformed (using the ASM [21] library) so that all references to System.in are replaced with references to the analyst's input driver. The loading of the input driver class is also performed by LeakWatch's classloader, so each execution of the target program believes it alone is reading from the standard input stream; this means that concurrent executions of a target program that reads from the standard input stream can progress without interfering with each other.

Practical Applications

We now present three examples demonstrating how LeakWatch can be applied to real-world situations to detect the presence of information leaks, quantify their size, and remove or mitigate them; they were benchmarked on a desktop computer with a quad-core CPU and 4GB of RAM. The source code for these examples is available for download from [START_REF] Chothia | LeakWatch[END_REF].

A Poorly-Implemented Multi-Party Computation Protocol

Diner 1

1 ⊕ 1 = 0 Diner 2 ¬1⊕1 = 1 Diner 3 0 ⊕ 1 = 1 Diner 4 1 ⊕ 0 = 1 Table 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1

Waiter

(1) Random bit: 1

(1) Random bit: 1

(1) Random bit: 0 (1) Random bit: 1

(2 ) P ay m en t d et ai ls ( 2 ) 0 The dining cryptographers problem [START_REF] Chaum | The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability[END_REF] investigates how anonymity can be guaranteed during secure multi-party computation. Informally: a group of cryptographers dine at a restaurant, and the waiter informs them that the bill is to be paid anonymously; it may be paid by any of the diners, or (e.g.) by the national security agent sitting at an adjacent table. After the bill has been paid, how do the diners collectively discover whether one of them paid the bill, while respecting their fellow diners' right to anonymity?

( 2 ) 1 ( 2 ) 1 ( 3 )
The DC-net is a solution to the dining cryptographers problem; it provides unconditional sender and recipient untraceability. Briefly, each diner generates a random bit visible only to them and the diner to their left, giving each diner sight of two separate randomly-generated bits; each diner computes the XOR of these two bits and announces the result publicly to the rest of the tableexcept for the payer, who announces the inverse of their XOR computation. The XOR of the announcements themselves allow each diner to verify whether one of them paid: if this value is 1, one of the diners claimed to have paid; if it is 0, nobody claimed to have paid. This protocol preserves the anonymity of the payer; however, care must be taken when implementing the protocol to ensure that side-channels do not leak information about the payer's identity.

This example implements a multithreaded, object-oriented DC-net in Java (see Fig. 3). Four Diners are seated at a Table and -for the purposes of verifying whether the code contains an information leak -one of them is randomly selected to be the payer; the identity of the payer is marked as a secret with secret(). The Diners then concurrently execute the protocol described above: they privately exchange their randomly-generated bits with each other using the socket libraries in the Java API, and the payer sends their payment details to the Waiter over another private socket. The Diners then announce the results of their XOR computation to the rest of the Table ; the messages sent to the Table's socket are publicly visible, and are marked as observable with observe(). LeakWatch then answers the question "what does a passive attacker learn about the payer's identity by watching the messages sent to the Table?".

After 2,600 trial runs (taking 9 minutes to perform the required number of trial runs and 300ms to calculate the leakage estimate), LeakWatch estimates that there are ca. 1.15 of a possible 2 bits of mutual information between the identity of the payer and the messages the Diners broadcast to the Table . The minentropy leakage is found to be 0.47 bits after 6,080 trial runs; 11 minutes were spent performing the trial runs, and 221ms were spent calculating the estimate. Although the messages themselves reveal no information about the identity of the payer, the order in which they are sent does: the additional time taken by the payer to send their payment details to the Waiter means that, more often than not, they are one of the last Diners to announce the result of their XOR computation to the Table. This leakage can be eliminated in several ways; e.g., modifying the implementation so that each Diner waits 100ms before sending their announcement to the Table's socket makes it more likely that messages will arrive at the Table's socket in any order. After 5,700 trial runs of this modified DC-net, LeakWatch confirms that there is no leakage of the payer's identity.

By increasing the number of Diners participating in the DC-net, the communication protocol becomes more complex, and the amount of observable information increases exponentially. Fig. 5 (3 pages below) shows the amount of time LeakWatch takes to estimate the leakage from a simplified DC-net, with all socket-based communication removed and a new leak caused by biased random bit generation inserted (a 0 is generated with probability 0.75, rather than 0.5). The graph shows that, as more Diners are added to this simplified DC-net, the amount of time LeakWatch takes to perform a number of trial runs that is sufficient to compute an accurate leakage estimate increases exponentially (ca. 2 hours when 17 Diners participate). The amount of time required to estimate the size of the leak also increases exponentially, but remains comparatively very small (ca. 12 seconds when 17 Diners participate), indicating that the vast majority of LeakWatch's time is spent collecting sufficient trial run data, and not computing leakage estimates.

Analysing the Design of Stream Ciphers

Crypto-1 is a stream cipher used to encrypt transmissions in commercial RFID tags. The design of this cipher was kept secret, but careful analysis (e.g., [START_REF] Garcia | Wirelessly pickpocketing a Mifare Classic card[END_REF]) revealed that it is based on a 48-bit linear feedback shift register (LFSR). Each keystream bit is generated by applying two functions (f a , f b ) to 20 bits of the state, and then applying a third function (f c ) to the outputs of these functions. In this example we use LeakWatch to show that the mutual information between the state bits and the keystream bits reveals much of this structure.

The initial state of the LFSR is derived from the key; to simplify the example, we assume that we can set the initial state directly. Information about the structure of Crypto-1 is revealed by loading different initial states into the LFSR and observing the output from the final Boolean function f c . Using a Java implementation of Crypto-1, an LFSR is created with a randomly-generated initial state, and the first output bit from f c is computed. The value of this bit is marked as observable with observe(). Another LFSR is created with the same initial state as before, but with the value of the bit at index i flipped with probability 1 2 -the decision about whether or not to flip this bit is marked as secret information with secret(). The output from f c in this second cipher is then computed, and its value is also marked as observable with observe(). The question being asked here is "what is the correlation between the LFSR bit at index i being flipped and the output of f c changing?"; informally, this can be seen as the influence of the bit at index i on the cipher's keystream.

By running LeakWatch 48 times, each time using a different value of i between 0 and 47 (taking a total of 19 seconds to perform the trial runs and a total of 425ms to produce the 48 leakage estimates), LeakWatch reveals which indices of the LFSR are tapped and passed as input to the Boolean functions; each execution of LeakWatch performs approximately 220 trial runs to determine the influence that that particular bit has on the keystream. flipping the LFSR bit at the index on the x axis and the first bit of the keystream changing. By reading off these indices on the x axis, we see which bits are tapped to produce the keystream. Moreover, the relative vertical distances between the points for each group of four indices reveal two distinctive patterns: these are the Boolean functions f a and f b (i.e., the pattern for groups {9, 11, 13, 15} and {33, 35, 37, 39} represents f a , and the pattern for groups {17, 19, 21, 23}, {25, 27, 29, 31} and {41, 43, 45, 47} represents f b ); it is therefore possible to "see" which indices are tapped by each of these functions, as indicated by the dashed lines between the points in each group. The slight variation in the groups' distances from the x axis is accounted for by the third Boolean function f c , into which the output from the other Boolean functions is fed.

This analysis shows that the output of this popular but flawed cipher reveals a lot of information about its internal design; it is therefore unsurprising that the cipher's design was fully reverse-engineered. The same technique can also be used to analyse other LFSR-based stream ciphers, such as Hitag-2 [START_REF] Verdult | Gone in 360 seconds: Hijacking with Hitag2[END_REF].

Recipient Disclosure in OpenPGP Encrypted Messages

OpenPGP [START_REF] Callas | OpenPGP Message Format[END_REF] is a data encryption standard. In a typical usage scenario, encrypted OpenPGP messages contain two packets: the first contains a randomlygenerated symmetric session key encrypted with the recipient's public key, and the second contains the sender's message, encrypted under the session key. Although OpenPGP provides message confidentiality and integrity, it does not necessarily provide recipient confidentiality because the first packet contains the recipient's key ID -the low 64 bits of the SHA-1 hash of their public key -which may be used to corroborate the recipient's identity with a resource mapping public keys to identities, such as an OpenPGP key server.

To demonstrate this, we present an example where two principals attempt to communicate securely using OpenPGP while concealing their identities from a passive attacker with the ability to read messages sent over the communication medium; the OpenPGP API is provided by the BCPG Java library [START_REF]The Legion of the Bouncy Castle Java Cryptography APIs[END_REF]. In the program, a sender is chosen randomly from a pool of six principals, and a recipient is chosen from the remaining five; their identities are both marked as secret (with secret()). The sender greets the recipient by name, encrypts the greeting with the recipient's public key, and sends the encrypted message over an insecure medium, where it is monitored by the attacker. Two pieces of information are marked as observable by the attacker using separate calls to observe(): the header of the first packet in the encrypted OpenPGP message, and the length (in bytes) of the entire encrypted message. Thus, LeakWatch answers the question "how much information does an attacker learn about the principals' identities by observing these two features of the encrypted traffic?".

Assuming the two principals are selected uniformly, there are ca. 4.9 bits of secret information in this scenario (ca. 2.6 bits from the sender's identity and ca. 2.3 bits from the recipient's identity). After 550 trial runs (taking 17 seconds to perform the required number of trial runs and 300ms to produce the leakage estimate), LeakWatch reveals that, because BCPG includes the recipient's key ID in the first packet, there is a leakage of ca. 2.52 bits about the secret information: there is complete leakage of the recipient's identity, and a further leakage of ca. 0.2 bits of the sender's identity, because the attacker also knows that the sender is not the recipient. Some OpenPGP implementations mitigate this leakage of the recipient's identity; e.g., GnuPG features a -R option that replaces the key ID in the first packet with a string of null bytes. By patching BCPG to do the same, the leakage decreases to ca. 1.86 bits after 350 trial runs: the recipient's identity is no longer leaked completely via the first packet, but because the attacker knows the format of the unencrypted message being sent, the length of the second packet still reveals some information about the recipient's identity (because the sender's encrypted message will be longer when greeting a recipient with a longer name).

Fig. 5 shows how increasing the number of bits in the first packet that are observable by the attacker affects LeakWatch's execution time. It reveals a result similar to that in Section 6.1: as the number of bits in the observable output increases, the amount of time required for LeakWatch to perform the number of trial runs required to estimate leakage increases exponentially (ca. 6 hours when the observation size reaches 132 bits); this is because of the exponentiallyincreasing number of trial runs required to verify whether parts of the randomlygenerated encrypted session key leak information about the principals' identities. The amount of time required to estimate the size of the information leak from the trial run data, however, remains comparatively very small (ca. 1.5 seconds when the observation size reaches 132 bits), as it does in Section 6.1.

Conclusion

We have presented new theoretical results and practical techniques for the statistical estimation of information leakage from real-world Java programs, based on trial runs. In particular, we have described a new method for estimating minentropy leakage and its confidence interval, and a technique for ensuring the collection of a sufficient number of samples. We have also presented a mechanism that ensures the independence of trial runs of Java programs, and applied our information leakage model and estimation techniques to input-consuming Java programs. Using three examples, we have demonstrated that our robust information leakage analysis tool LeakWatch can uncover information leakage vulnerabilities in Java programs.

Fig. 1 .

 1 Fig. 1. The sampling distributions of mutual information and min-entropy leakage (and the lower/upper bounds for min-entropy leakage's confidence interval).

Fig. 2 .

 2 Fig. 2. The LeakWatch classloader hierarchy. Multiple copies of the target program can be executed simultaneously and in isolation using separate instances of the LeakWatch classloader.

Fig. 3 .

 3 Fig. 3. An overview of the Java DC-net implementation. Diner 2 pays the bill; the final result is 1, indicating that one of the Diners paid.

Fig. 4 .

 4 Fig. 4. The influence over the first bit of the keystream of each bit in a 48-bit secret initial state for Crypto-1.

Fig. 5 .

 5 Fig. 5. The effect on LeakWatch's execution time of increasing the amount of secret or observable information in the examples in Sections 6.1 (the number of Diners, left) and 6.3 (the number of observable bits in the encrypted OpenPGP message, right).

⋆ Work by Yusuke Kawamoto was supported by a postdoc grant funded by the IDEX Digital Society project.