Off-Path Attacking the Web

We show how an off-path (spoofing-only) attacker can perform cross-site scripting (XSS), cross-site request forgery (CSRF) and site spoofing/defacement attacks, without requiring vulnerabilities in either web-browser or server and circumventing known defenses. Attacker can also launch devastating denial of service (DoS) attacks, even when the connection between the client and the server is secured with SSL/TLS. The attacks are practical and require a puppet (malicious script in browser sandbox) running on a the victim client machine, and attacker capable of IP-spoofing on the Internet. Our attacks use a technique allowing an off-path attacker to learn the sequence numbers of both client and server in a TCP connection. The technique exploits the fact that many computers, in particular those running Windows, use a global IP-ID counter, which provides a side channel allowing efficient exposure of the connection sequence numbers. We present results of experiments evaluating the learning technique and the attacks that exploit it. Finally, we present practical defenses that can be deployed at the firewall level; no changes to existing TCP/IP stacks are required.

Introduction
TCP is the main transport protocol over the Internet, ensuring reliable and efficient connections. TCP was not designed to be secure against Man-in-the-Middle (MitM); in fact, it is trivially vulnerable to MitM attacks. However, it seems that man-in-the-middle and eavesdropping attacks are relatively rare in practice, since they require the attacker to control routers or links along the path between the victims. Instead, most practical attacks involve malicious hosts, without MitM capabilities, i.e., the attackers are off-path.
In our attacks, as well as in many other off-path attacks (e.g., SYN-flood [42], DNS-poisoning [22]), the attacker sends spoofed packets, i.e., packets with fake (spoofed) sender IP address. Due to ingress filtering [24,15,5] and other anti-spoofing measures, IP spoofing is less commonly available than before, but still feasible, see [2,14]. Apparently, there is still a significant number of ISPs that do not perform ingress filtering for their clients (especially to multihomed customers). Furthermore, with the growing concern of cyberwarfare and cybercrime, some ISPs may intentionally support spoofing. Hence, it is still reasonable to assume spoofing ability.
However, there is a widespread belief that an 'offpath' spoofing attacker, cannot inject traffic into a TCP connection. The reasoning is that an incoming TCP packet must contain valid sequence number (or be discarded); the sequence number field is 32 bits long and initialized using randomness, therefore, it seems unlikely that an attacker can efficiently generate a spoofed packet which will be accepted by the recipient, i.e., inject data into the TCP stream.
This belief is also stated in RFCs and standards, e.g., in RFC 4953, discussing on TCP spoofing attacks (see [42], Section 2.2). Indeed, since its early days, most Internet traffic uses TCP -and is not cryptographically protected, in spite of warnings, e.g., by Morris [33], Bellovin [8,10]).
Of course, TCP injections are easy, for implementations using predictable initial sequence numbers (ISNs). This was observed already by Morris at 1985 [33] and abused by Mitnick [38]. Later, at 2001, Zalewski found that most implementations still used predictable sequence numbers [46].
However, by now, most or all major implementations ensure sufficiently-unpredictable initial sequence numbers, e.g., following [19,20]. Does this imply that TCP injections are infeasible?
Zalewski [48] suggested that it may be possible to spoof a non-first fragment of a (fragmented) TCP packet, when the values of the fragment IP-IDs are predictable. In particular, existing implementations of Windows use globally-incrementing IP-ID values, which are easy to predict. Zalewski's attack may also be applicable to Linux, using the IP-ID prediction techniques in [17]. However, exploiting such non-first-fragment TCP injections seems challenging; furthermore, currently almost all TCP implementations use path MTU discovery [32,31] and avoid fragmentation completely. Hence, Zalewski's attack (on TCP) will rarely work in practice.
Yet, we show that TCP injections are still possible. We present an efficient, practical technique, based on globally-incrementing IP-ID, allowing an off-path adversary, Mallory, to inject data into a TCP connection between two communicating peers: a client C and a server S. The attack is not immediate, and requires a connection lasting a few dozens of seconds. We present experimental results, showing that our techniques allow efficient, practical TCP injections. Furthermore, we show, that the attacks have significant potential for abuse. Specifically, we show how our TCP injection techniques, allow both circumvention of the Same Origin Policy [6,49] and devastating DoS attacks. Details follow.
Our TCP injection technique is related to a proposal for TCP injection, by klm [27]. The technique described by klm had some limitations, e.g., it did not work for clients connected by a firewall. More significantly, klm did not present experimental results; our experiments show that their technique, even with some improvements, results in low injection success rates, unless the attacker has low latency to the victim (as when they are on the same LAN). Our techniques avoid this limitation. We provide a detailed comparison between our technique to [27] in appendix A.
Like [48,17,27], our technique is based on the predictability of the IP-ID (e.g., in Windows); however, instead of using the predictable IP-ID to intercept or modify fragmented packets, as in [48,17], we use the changes in the IP-ID as a side channel. We use this side-channel to allow the attacker to detect difference in responses for crafted probe packets that she sends to the client; our implementation uses specific probes, but others may exist.
Previous works noted that the predictable IP-ID can be used as a side channel, allowing an attacker to use one connection to learn about events in another connection, which is undesirable. Gont [18] mentions several ways in which the side channel based on globally-incremented IP-ID can be abused. However, their impact is modest. In particular, the side-channel can be used to perform the idle (stealth) scan attack [47,26,29], and to count the number of machines behind NAT [9].
However, vendors continued using globallyincrementing IP-ID values, even after we presented our initial TCP injection results to them, and being aware of the previous attacks exploiting the globally incrementing IP-IDs. Their justification is that they be- lieved that such attacks are impractical and too complex to be exploited in practice. They confirmed our results and agreed that they are feasible; they will address the problem in new releases. We believe that this response is 'too little, too late', and that it is critical for the community to be aware of the threat and apply mitigations (Section 7). A more controversial conclusion is the need to apply more prudent approach to network security vulnerabilities, and respond to early indications of weakness, without waiting for a complete exploit; see discussion in Section 8.
Much of our work focused on analyzing what are the practical implications of the TCP injection. We study two approaches to exploit TCP injections: to circumvent address based server authentication, usually referred to as Same Origin Policy (SOP) [6,49]; and to launch a Denial of Service (DoS) attack. We discuss each of these briefly in separate subsections below, and in depth in Sections 2 and 3. All attacks are based on the same attacker and network assumptions which we now describe.

Attacker Capabilities and Network Model
All our attacks work in the same settings: an off-path, IP-spoofing attacker. We also assume that the attacker is able to control some puppets [4], i.e., scripts, applets or other restricted (sandboxed) programs, running on client machines accessing an adversarial web site. This is illustrated in Figure 1 where C enters a site controlled by the adversary, Mallory. This allows Mallory to run a malicious script within C's browser sandbox. The script allows Mallory to (1) form the connection between C and S, and (2) probe C's connection with S and avoid firewall filtering. The first allows Mallory to choose the victim server (S), we show how the second allows exposure of the TCP connection's four tuple.
As mentioned above, our attacks require that the connection from C and S will not be short; since Mallory forms this connection (using the puppet), she can ensure that it does not terminate by sending periodic requests to the server. In persistent HTTP connections, all re-quests are over the same (victim) connection and ensure it does not close. Persistent HTTP connections are the default configuration of apache servers and are also employed by many large web-servers (e.g., Facebook, Yahoo!, Google), but not all (e.g., live.com, the Japanese version of Yahoo!). Our attacks are browser independent, as we illustrate in experiments in the following sections.

Breaking SOP and Address-Based Authentication
TCP injection attacks were key to some of the most well known exploits, specifically, attacks against address based client authentication, e.g., see [38,10]. However, as a result, address-based client authentication has become essentially obsolete, and mostly replaced with secure alternatives such as SSH and SSL/TLS. We believe that the only widely-deployed use of address based client authentication, is to identify clients involved in DoS attacks such as SYN flooding; and this threat can be dealt with by simple client-response authentication, possibly using cookies to avoid state-exhaustion on the server [13]. However, current web security still relies, to large extent, on the Same Origin Policy [6,49], i.e., on address based server authentication; our results show that relying on addresses to authenticate the servers is also risky.
Using TCP injections to attack address based server authentication, e.g., to perform XSS attacks, is more challenging than using it to attack address based client authentication. In attacks on address based client authentication, the off-path attacker sends the initial SYN to open a new connection; hence, she knows the client's sequence number, as well as the source and destination IP addresses and ports; she 'only' needs to predict the server's sequence number. In contrast, to attack address based server authentication, the off-path attacker must guess both sequence numbers, as well as the IP addresses and ports of both parties; guessing the client port could also be challenging, as the client may choose it arbitrarily.
To circumvent the same origin policy [6,49], the offpath attacker sends forged responses for requests that C sends to another server S. This attack is facilitated in two phases: first the puppet opens a connection to the victim server, allowing TCP injection into this connection; then the puppet requests an object, allowing the attacker to send the script in a (spoofed) response.
In particular, this allows powerful cross site scripting (XSS). XSS is one of the most critical attacks on web security, however, current XSS techniques depend on implementation vulnerabilities, usually of the site (e.g., [45,49]), and sometimes of the browser [25]. In contrast to typical XSS attacks, our attack does not rely on a server side or browser vulnerability. Moreover, since Mallory can choose the server S, any persistent HTTP connection between C and a server is vulnerable (see above). Connections with HTTPS servers are not vulnerable to XSS since Mallory cannot inject content into the cryptographically sealed session.
Furthermore, the XSS ability allows injection of requests, i.e., cross-site request forgery (CSRF) [41]. This circumvents existing defenses, such as the use of cookies, referrer header and hidden field, since all of these are available to the (injected) script (see [34]). The CSRF attack can be prevented by challenge response methods that require user involvement, such as password authentication or CAPTCHAs.
The XSS ability also allows advanced phishing attacks. In particular, this provides efficient means for detection of browsing history, more effectively than previous techniques, e.g., [28,44].

Devastating DoS attacks
An off-path attacker can use the knowledge of TCP parameters (IPs, ports and sequence numbers) in several ways, to attack the availability of a communication service.
In 2004, Watson observed that BGP connections used a constant client port, and typically have very large windows; this makes it feasible for an off-path adversary to reset BGP connections [43] (despite random initial sequence numbers). However, appropriate countermeasures make this attack inapplicable today [13].
We show how a spoofing, off-path attacker, who controls a limited number of (weak) puppets, can deploy formidable DoS attacks, which so far were known to require stronger attacker capabilities: the Ack-Storm attack [1] and the Optimistic-Ack attack [37]. Both are DDoS attacks, which use TCP control plane to generate excess amount of traffic. The Ack-Storm attack [1], is usually performed by MitM adversaries, possibly with limited eavesdropping abilities. The Optimistic-Ack attack [37] typically requires client cooperation (zombie) and persuades the server to send data in a high capacity, more than that allowed by C's link. Since in both these attacks, Mallory injects data only to the TCP layer (and not to the application), these attacks also work when the victim servers use SSL.
Launching these attacks simultaneously on multiple client-server pairs may allow Mallory to conduct an improved variant of the Coremelt attack [40] and congest a core link of the Internet, using only puppets.

Organization
The next two sections focus on the application of the TCP injection technique. In Section 2 we present our off-path attacks on the confidentiality and integrity (authentication) of the communication between client and server, including the XSS, CSRF and phishing attacks. In Section 3, we present our off-path DDoS attacks.
Sections 4-6 present the TCP injection technique itself. Section 4 presents the first step, which is exposing the server's sequence number. Section 5 continues the attack, to expose the client's sequence number as well. Section 6 discusses deployment challenges, improvements to meet these challenges, and experimental results.
Finally, Section 7 proposes defenses against the attacks, and Section 8 presents a concluding discussion.

Off-Path Data Integrity Attacks
In this and the following section we present and empirically evaluate exploits of TCP injections. We focus on long-lived-connection injection attacks, where an offpath attacker learns the sequence numbers of an existing, long-lived TCP connection, between a given TCP client and server (identified by their IP addresses and ports). Motivated by these exploits, in Sections 4-6 we present and evaluate the technique we employ to study the sequence numbers.
Specifically, we show critical exploits of long-lived connection injections. In this section we focus on two exploits: the first allows an off-path attacker to run a malicious script in the context of an arbitrary website of the attacker's choice, without depending on a vulnerability of the server (e.g., bug in input sanitization) or of the browser; this is a new, devastating type of XSS attack [45,25]. The second exploit allows the same attacker to present spoofed web-pages for clients. In the following section we show how off-path attackers can use longlived connection injections to cause devastating DoS attacks. All exploits work in the same setting, illustrated in Figure 1.

Identifying the Victim Connection
To launch the long-lived-connection injection attacks, the attacker must identify a connection between the client and server which is defined by the IP addresses and ports of the participating peers.
The exploits use the puppet running on the client to open such (long-lived) connections. The server's IP and port are, of course, known. To find the client's IP and port, the puppet opens another TCP connection to the attacker and over it, sends packets to the attacker's machine. These packets contain the client's IP address.
The final challenge is to detect the client port. Many clients, in particular, those running one of the Windows family operating systems, assign ports to connections incrementally. We use the puppet to open a connection to the attacker's remote site before and after opening the connection to the victim server, incremental port assignment allows the attacker to learn the client's port; see step A in the attack process described in Section 2.2.1 below. Client port exposing may fail if the puppet communicates with the server or attacker via a NAT device that randomizes the client port (since 'external' ports are not incremental). In an ongoing research we investigate this problem and provide, details of a different technique that allows an off-path attacker to detect the client port in a connection.
It remains to describe, in the following subsections, the unique aspects to each of the exploits and evaluate their impact.

Off-Path Injection XSS (or: XSS of the Fourth Kind)
In a Cross-site scripting (XSS) attack, the attacker causes the browser to run malicious, attacker-provided script (or other sandboxed code), with the permissions of scripts within a victim server web-page.
In [25], Klein identifies three kinds of XSS attacks. In persistent/stored XSS attack, the script is received from the victim server, as part of the contents of a page stored by the victim server. In reflection XSS attack, the script is 'reflected' by the victim server to the client, after the server receives the script from the browser (typically visiting a malicious website). Finally, in a DOM-based XSS attack, the script is received by the browser directly from the attacking server; a browser vulnerability (bug) causes the browser to consider the script as coming from some other victim server.
Both reflection and persistent/stored XSS attacks, exploit 'bugs' in the web application. Well designed sites, using appropriate defenses such as Web Application Firewalls (WAF), should eliminate these attacks; see, e.g., [45]. DOM-based XSS attacks do not require any bug in the site, but depend on bugs in the browser; the relevant known bugs were quickly patched by browser vendors.
Long-lived-connection injection attacks, allow a new, fourth kind of XSS attacks: off-path injection XSS attacks. In these attacks, the malicious script is sent by the attacker to the browser, with (spoofed) source IP address of the victim server. If the script it injected correctly, with correct TCP/IP parameters and within correct HTTP context, then the browser executes it in the context of the victim site.

Attack Process
We next explain the technique we employ to use longlived injection attacks to perform off-path XSS injections. Like our other exploits, we assume that the user visits a website controlled by the attacker from where he receives and executes a puppet (malicious script) [4]. The attack has five steps and proceeds as follows: A. Form Connection, Expose Client Port Puppet opens a new connection to a server controlled by the attacker, then a connection to the victim web server and finally another new connection to a server controlled by the attacker. Let the client port numbers that the attacker observes for the first and third connections be p 1 , p 3 . We use the counter property of Windows port assignment: if p 3 = p 1 + 2, then we assume that the client used port p 1 + 1 for the (middle) connection to the victim server. Otherwise, repeat.

B. Expose Connection Sequence Numbers
Puppet maintains the connection with the victim server alive by sending periodic requests for small objects. During this time, attacker runs the sequence exposure attack described in Sections 4, 5. If sequence exposing fails, restart entire attack.

C. Send 'Dummy' Request
Puppet sends the victim server a request for some web page (over the same persistent connection), e.g., using an iframe, and informs the attacker on that request. Note that the puppet runs in the context of the attacker site; hence, the attacker and puppet can communicate and coordinate the attack without restrictions.

D. Send Spoofed Response
Attacker sends spoofed response to the client, containing exact expected TCP parameters, and a web page containing the malicious script.

E. Script Execution
Browser receives the spoofed response as if it was sent by victim server, hence, executes script with permissions of the victim server. Figure 2 shows a successful run of this attack on the Mozilla Firefox browser.

CSRF Exploit
As indicated in [45,41], once attackers succeed in an XSS attack, i.e., run a malicious script in the browser, in the context of a victim site, they can exploit it in many ways. In particular, such XSS attack allows attackers to send a forged (fake) request to the server on the user's behalf, i.e., a cross site request forgery (CSRF) attack, Figure 2: An XSS Attack. Mallory runs a script in context of www.victim-server.com within Mozilla Firefox sandbox. The address bar indicates the user is at www.mallory.com, but the message box context indication shows that the script (that Mallory provided) runs from www.victim-server.com.
circumventing all known defenses against CSRF attacks for non-secured connections, except for (few) defenses requiring extra user efforts for submission of each (sensitive) request; see [34].
Note that since the attackers (cross site) scrips can read the entire response that the user receives from the victim web-server, they would even be able to circumvent advanced proposed defenses, which require new browser mechanisms. In particular, they can foil the origin header proposed by Barth et al. against CSRF attacks [7], as well as policy-based defense mechanisms against XSS, e.g., Content Security Policy (CSP) [21,39].

Experimental validation
In this subsection we evaluate the applicability of the XSS attack on web-users. The client machine in the following experiments is protected by Windows Firewall.
The success of the XSS attack depends on successfully exposing of the sequence numbers used in the connection the client has with the victim server. The success rate of the exposure technique that we employ (presented in Sections 4, 5) depends on the rate of packets that the client machine sends. In Section 6 we present another set of experiments that specifically evaluates the injection technique for different environments. In the measurements below, C sends 32 packets per second on average.
We tested whether connections with each of the top 1024 sites in Alexa ranking [3] are vulnerable to offpath XSS attacks: our client machine connects to the attacker (www.mallory.com), who then tries to run a script in context of one of the top sites. The script provides an indication of a successful injection by requesting an image from www.mallory.com. Note that our attacker only communicates with the client, and does not have any interaction with the victim servers. In Figure 3 we compare the results for three common browsers and observe that the attack is not browser-dependent. The immune connections are generally of the following types: (1) secured with SSL (HTTPS), this prevents the attacker from injecting his script to the connection (step D in the attack); (2) sites that do not use the HTTP keep alive option, this prevents the attacker from keeping the long connection with the server that is required to expose the sequence numbers (step B in the attack). In Figure 4 we provide distribution of the top 1024 sites in Alexa ranking; showing that 80% percent of them appear vulnerable (line 3 in Figure 4). A comparison of this result to those presented in Figure 3 shows that the XSS attack was, in fact, successful on roughly 75% of the sites that appear vulnerable. Among the vulnerable sites on which we ran a successful attack are www.facebook.com, www.yahoo.com and www.amazon.com.

Web Spoofing/Phishing/Defacement
In addition to the XSS exploits, attackers can use TCP injections to perform web spoofing (which is key to phishing attacks). Namely, the attacker waits for the user to browse to some victim server, e.g., http://www.bank.com, and injects his data to the connection. In this attack, the attacker provides a spoofed version of the web-page to the client. This spoofing exploit can expose sensitive user-provided information such as passwords and may trick the user to download malware. An implicit assumption of this attack is that the initial web-page that the user receives, and which the attacker forges, i.e., http://www.bank.com, is not protected by SSL. This is the situation in most sites, which do not use SSL/TLS at all. The attack also works for many sites which do use SSL/TLS, but only via a link, e.g, to the login page https://www.bank.com/login.php. This approach is common since it reduces the load on the server by delaying setup of SSL connections until these are required (in the banking example, for login); see line 4 of Figure  4 1 . Web-spoofing can allow the attacker to circumvent the use of encrypted connections (SSL/TLS), using techniques/tools such as SSL-strip [30], i.e., replace links on the original page to phony pages (on the attacker's site).
To succeed in a web-spoofing attack, the attacker would best send the spoofed page as a response to a request made by the user (since then the page appears authentic to the user); hence, the attacker should be able to detect the request for the page and send a response. We solve this problem by having the puppet open a connection to the victim server in advance providing sufficient time to expose the sequence numbers used in the connection. We leave the connection open (by sending 'dummy' requests periodically); and probe for user activity by identifying a change in the client's sequence number. In order to detect this change that indicates that the client had sent a request to the server, the attacker periodically conducts a client-seq-test; this test is a building block of the sequence numbers exposing technique and we provide its details in Section 5. Briefly, the test allows the attacker to test whether the client sequence number is above some value; testing using the exposed (i.e., last known) value of client sequence number allows to detect such change. Once we detect such activity over the connection, we assume that the user had sent a request to the server for the home page and send a spoofed (modified) page.
This web spoofing technique assumes that the user opens the page for the victim-server while the puppet is still running, e.g., in a different tab of the same browser or in a zero-size iframe. Furthermore, it assumes that the browser employs connection sharing between different tabs, i.e., one TCP connection is used to communicate with the same server via several tabs of the browser. TCP connection sharing is employed by the current versions of Internet Explorer, Firefox and Chrome (and possibly other browsers). Another assumption is that the user receives the attacker's response before the server's; this appears as a race that would be difficult to win for an attacker far from the client machine. However, the attacker can avoid this race by injecting data to the client (as the server) in advance: the injected data artificially increments the sequence number that the client expects from the server while the true server would still use the 'normal' sequence number, causing the client to reject all data sent by the server. The J.P. Morgan bank website is an example of a sensitive site that is vulnerable to this spoofing/phishing attack; it uses HTTP keep alive option and its homepage is not protected by SSL. Hence, this website is vulnerable to the web spoofing attack above. Figure 5 shows the result of a successful web spoofing attempt: here the client has two tabs open in his browser. The current tab (in focus) shows the J.P. Morgan homepage that Mallory provided; the devil image (that does not exist in the original page) indicates that this page is spoofed. J.P. Morgan homepage contains a client log-on link that in the original site switches to SSL. In the spoofed version, the link is to a web-page in Mallory's site. In the other tab, the victim is in www.mallory.com; this allows Mallory to monitor the requests that the user (may) send J.P. Morgan and identify the correct time to inject the spoofed page.

Off-Path Denial-of-Service by Puppets
We next describe possible exploits of long-livedconnection injection attacks to disrupt network communication. Namely, we show how attackers can build on these attacks, to launch devastating Distributed Denialof-Service (DDoS) attacks. As before, we consider an off-path IP-spoofing attacker, who also controls a significant number of 'puppets', i.e., scripts running in browsers of unsuspecting users. As argued in [4], it is relatively easy for attackers to control a large number of puppets in this way.
However, puppets have limited ability to launch DDoS attacks. One reason are limitations placed by the browsers on the number of concurrent connections opened by the same web-page. Another reason is that, due to their execution within a sandbox, puppets can only use standard TCP connections. In particular, if the attack succeeds in causing congestion and loss, then TCP connections, including those of the puppets, will significantly reduce their window size (and hence their traffic rates). Therefore, while puppets can be used for DDoS attacks, their impact is much less than that of 'regular' malware (zombies/bots).
In contrast to the data integrity attacks in the previous section, the attacks below use TCP control plane to cause congestion. Since there is no attempt to inject data to the application layer, even SSL/TLS protected sites are vulnerable. Hence, these attacks are applicable to websites that support persistent HTTP connections, with or without SSL/TLS, e.g., to about 80% of the 1000 most popular sites (see line 2 in Figure 4).

Off-Path Optimistic Ack Attack
We first describe Off-path Optimistic Ack; this is a variant of the Optimistic Ack DoS attack [37]. These attacks cheat TCP's congestion control mechanism, causing senders to believe that most of the data they sent was already received, and hence that they can send more data (congestion window is not full), and also to increase the size of the congestion window. This can result in huge amplification factors, see [37], unless servers use perconnection bandwidth quotas or use other defenses.
In both Optimistic Ack attacks (ours and the original [37]), the attacker sends to the server acknowledgment packets (Acks), as if the client received all packets sent by the server (although packets are still in transit or even lost). As a result, the server continues sending information, with increasing window sizes (and hence rates).
In the original attack [37], the client must run malware, with ability to send 'raw IP' packets (i.e., not according to the TCP specifications). This is a significant requirement; recent operating systems make it harder for malware to obtain such ability. Furthermore, the original attack may be blocked by a firewall on the client side, by detecting the unusual high rate. Note that since by requiring only puppets, attacker is more likely to control enough clients to succeed in the attack, in spite of countermeasures such as per-connection quotas.
Our long-lived-connection injection attack, allows an off-path attacker to perform an off-path variant of the Optimistic Ack attack, as follows. The attacker only needs a puppet on the client machine to open the TCP connection with the victim server and learn the client port and sequence numbers. Following this, the puppet requests some large object from the server and is no longer needed; the attacker sends Ack packets as done by the client in the original attack, and -if not using SSL/TLSthe attacker can even send new request(s) if needed. Note that even if the client's firewall (detects the attack or for some other reason) begins blocking packets on this connection from both directions, this does not help since we provide the Acks to the server from the off-path attacker. Furthermore, RFC-compliant RST packets that the firewall (or client) may send, would be out of the server's window and hence ignored, and would not tear the connection. Server-induced verifications, by intentionally dropping or reordering packets periodically, as suggested in [37], seem one of the best (or only) defenses.

Off-Path Ack-Storm DoS Attack
In the original Ack-Storm DoS attack [1], the attacker needs to have some (limited) ability to eavesdrop on packets. From these packets, the attacker learns the TCP parameters (IP addresses, ports, and sequence numbers). Using these, the attacker sends two spoofed data packets, one to each of the two ends of the connection. According to the TCP specification, and in most TCP implementations, upon receiving an Ack for data that was not yet sent, TCP sends back a 'duplicate Ack' -i.e., resends the previously sent Ack. As a result of receiving the pair of spoofed data packets, one at each peer, both peers begin sending acknowledgment packets to each other. Since these Acks acknowledge data which was actually sent by the attacker, not by the peer, then each of these Acks will only result in another duplicate Ack returned, and this process will continue indefinitely.
The attacker can send additional data packets to the peers, causing additional ping-pong exchanges, quickly filling-up the channel capacity. This causes increased load on the networks; the fact that the packets involved in the attack are very short (just Acks), makes the load on routers and switches even higher. Eventually, this causes packet losses, and legitimate TCP connections sharing the same links significantly reduce their rate.
The off-path Ack-Storm DoS Attack works exactly like the regular Ack-Storm DoS Attack, except for using the long-lived connection injection technique to allow the off-path attacker to learn the TCP parameters. Hence the attacker can run this attack, without requiring the ability to eavesdrop.

Off-path Coremelt Attack
Since the two DoS attacks described above can be launched using only puppets, it follows that even relatively weak attackers may be able to cause large amounts of traffic from many clients spread around the network. This can cause high load on servers, routers and links.
In particular, by choosing well the pairs of clients and servers between which the attacks are launched, the attackers can cause huge amounts of traffic to flow over specific 'victim' backbone routers and links. These backbone networks, connecting large core ISPs (autonomous systems), have very high capacities; by sending enough traffic to a particular destination, attacker can cause queuing and losses in the connecting router. As a result, Internet connectivity may break -first for TCP connections and then even for UDP applications. We use the term Off-path Coremelt Attack for the resulting attack on core Internet connectivity, since it is an off-path variant of the Coremelt attack [40]. The Coremelt attack uses a large botnet, sending large amounts of traffic between pairs of the bots, with the pairs chosen intentionally so that huge amounts of traffic will flow over specific victim link/router. As shown by simulations in [40], this can result in congesting the victim link/router, and even in breaking connectivity in the Network.
In the Off-path Coremelt attack, the attacker will also congest a core link; however, instead of depending on pairs of zombies (bots), here the attack just requires a puppet at one end. The other end of the connection is a legitimate server, and to cause huge amounts of traffic, the attacker uses one of the two off-path DoS attacks described above.
This attack has three advantages compared to the original Coremelt attack: (1) controlling a sufficiently large and correctly-dispersed set of puppets is easier than controlling a comparable set of zombies; (2) we only need to control one end of each connection (the puppet), not both ends; and (3) since we use adversary-chosen servers, these can have very high bandwidth, higher than available to most bots.

Experimental Evaluation
We used the topology illustrated in Figure 6 to test the off-path denial of service attacks we presented. In our tests we assume that Mallory runs a puppet on C and can inject data to the TCP connection between C and S (a connection that Mallory caused C to establish).
We evaluate the attacks by measuring the degradation of service that they cause to other legitimate connections. We consider different round-trip times (RTTs) for the legitimate connections we measure: the longer the RTT is, the greater the congestion windows are. Since every loss halves the congestion window, a more significant effect is observed when RTT is high. Furthermore, a higher RTT implies that it will take more time for the sender to detect a packet loss and retransmit. The base line to which we compare the effect of these attacks is line 1 in Figure 7 which illustrates the time it takes C* to receive a 50MB file from S* under normal conditions.

Off-Path Optimistic Ack Evaluation
In this attack we aimed to clog the S's link: Mallory uses C to request some large file from S and then performs the Optimistic Ack attack, persuading S to send data to C at high a rate. We evaluated the effect of this attack by measuring the degradation of service in a connection that S has with some other client C* who tries to download a 50MB file. Lines 1 and 2 in Figure 7 illustrate our results. Notice the significant difference in attacker and server link capacities; the amplification ratio measured in this attack is 78 (for every byte that Mallory sends, S sends approximately 78 bytes). Furthermore, the attack also clogs C's link, as shown by line 4.

Off-Path Ack-Storm Evaluation
We use the Ack-Storm attack to congest C's link and measure the effect on a different connection that he has with some other server S*. In order to congest the link, Mallory creates a new Ack 'ping-pong' every 100 ms; to create each ping-pong Mallory sends only two short (40B) packets. In the connection with S*, C tries to download a 50MB file (similar to the previous experiment). Lines 1 and 3 compare the file transfer time at a normal time, to that when the Ack-Storm attack takes place. This attack requires much less effort and lower bandwidth than the Opt-Ack attack, i.e., has much higher amplification ratio; but is limited by the client bandwidth (which is typically lower than the server's) this limitation is illustrated by line 5 which is very similar to line 1 (normal conditions).

Server Sequence Number Exposure
In this and the following section we describe the sequence exposure attack where a off-path adversary, Mallory, learns the current sequence numbers of a TCP connection between C and S.
We present a two phase attack: first, in this section we describe how Mallory learns the server's sequence number, sn, which S will use in the next packet sent to C. In the second phase, presented in the following section, we show how given S's sequence number (sn), Mallory efficiently obtains the acknowledgment number that C expects; this acknowledgment number is the sequence number that C will next use in packets sent to S. In both phases Mallory communicates only with C and aids a side channel feedback that she receives from C.
The attacks that we describe in both sections assumes that Mallory had previously identified C and S's IP addresses and ports; see details on how Mallory exposes these parameters in Section 2.1.

The Server-Sequence Test
This subsection presents the server-sequence test that allows Mallory to test whether some sequence number, sn, is within the flow control window (wnd) that C keeps for packets he receives from S. The key observation is that when a connection is in the established state, the recipient's handling of an empty acknowledgment packet (i.e., acknowledgment with no additional data) differs in case that it is not within wnd. The difference depends on the 32-bit sequence number and allows Mallory to search for a valid sequence number. The following paragraphs explain how: Packets that specify an invalid sequence number (i.e., outside the recipient's wnd) cause the recipient to send a duplicate Ack (for the last valid packet the recipient received). However, if the sequence number is within wnd, then the receiver does not send any response; the reason is that replying with an Ack in this case would start a never-ending series of acknowledgments.
The server-sequence test, illustrated in Figure 8, has three steps: in the first and third steps Mallory sends a query to C; this is some packet that causes C to send a response packet back to Mallory who then saves the IP-ID value in the response. In Section 6.1 we show how Mallory can use the legitimate TCP connection she has with C to implement queries and responses (since C is in www.mallory.com). In the second step, Mallory sends C a probe: this packet is spoofed and appears to belong to C's connection with S. The probe in this test is an empty Ack packet that leverages the observation above.
When Mallory receives the responses (for steps 1,3); she uses the IP-IDs they specify, i and j, to learn x = j −i, the number of packets that C had sent between the two queries. Since the Windows IP-ID implementation is a single counter for all destinations (incremented on every packet that C sends), Mallory learns that sn is within C's wnd if x = 1, i.e., C did not send any packet between the two queries (see Figure 8).

Learning Process
The probability that a sequence number that Mallory tests is within C's wnd is wnd-size 2 32 (since wnd is 32 bits long); this resembles to the TCP RST forgery attack [43] where the attacker sends reset packets with arbitrary sequence numbers. The value of wnd-size is therefore important; Gont also points out the significance of the flow control window size in his security assessment for TCP [20].
Mallory conducts the server-sequence test until he identifies a sequence number within C's wnd. Each test is for a different sequence number which is of distance e wnd from the previously tested one, where e wnd is an estimation of C's wnd-size. Namely, Mallory tests sequence numbers 0, e wnd , 2e wnd , etc. Generally, if e wnd < wnd-size, then Mallory would test redundant sequence numbers, and if e wnd > wnd-size, then Mallory may not find a valid sequence number. In our attacks (presented in Sections 2, 3) we use the puppet to request some large resource (or few small resources) over the connection with S before initiating the sequence exposure attack; the response increases C's wnd-size. We increase wnd-size until it is approximately 2 16 . Once a sequence number within wnd is detected, Mallory conducts a binary search (over the possible e wnd sequence numbers) to identify the exact beginning of wnd, which is the next server sequence number.
In Section 6 we provide an empirical evaluation of the complete sequence exposure technique.

Client Sequence Number Exposure
In recent Windows client versions (from XP SP2 and onwards) the recipient uses the acknowledgment number, that is specified within TCP packets, together with the sequence number to verify that a packet is valid. In order to inject a packet to the TCP stream, Mallory must specify an Ack number that is within C's transmission window; i.e., Ack for new data that C had sent. The black area in Figure 9 represents the 'acceptable' acknowledgment numbers (transmission window). In this section we show how to take advantage of Ack number validation to expose the client's sequence number.

The Client-Sequence Test
Similarly to the test we presented in the previous section, we build a three step client-sequence test where the first and last steps provide Mallory with the current value of C's IP-ID. In the second step Mallory sends a spoofed probe, C's response to this probe depends on the Ack number Mallory specifies.
The test is derived from another observation from the TCP specification [36] (Section 3.9, page 72). The relevant statement refers to an acknowledgment packet that carries data and contains a valid sequence number; i.e., success in the previous server sequence exposing phase is required to initiate this phase. The specification distinguishes between two cases regarding the acknowledgment number in the packet, see illustration in Figure 9.
Case 1: the packet contains a duplicate Ack (gray area in Figure 9), or acknowledges data that was sent, but not already acknowledged (black area in Figure 9). In this case the recipient is supposed to continue processing the packet regularly (see [36]). However, a Windows recipient (e.g., C) silently discards the packet if it is in the gray area (since acknowledgment is invalid); otherwise (black area) its data is copied to the received buffer for the application.
Case 2: In the complementary case that the acknowledgment number is for data that was not yet sent (white area in Figure 9), the recipient discards the segment and immediately sends a duplicate Ack that specifies his current sequence number, NXT. Win + spec: discard + send duplicate ACK Win + spec: process Figure 9: Ack Number Map. UNA is the lowest unacknowledged sequence number, NXT is the next sequence number that C will send. Acknowledgments for data in the gray area are considered duplicates, acknowledgments for data in the white area are for unsent data, i.e., invalid. In the black area are sequence numbers for sent un-Acked data. Note that the 32-bit Ack field is cyclic.
Hence, when C receives an acknowledgment packet that specifies an acceptable sequence number, i.e., within his flow control window (wnd), then: (1) in case that the specified Ack number is after UNA, C sends an acknowledgment; either since data had arrived (black area), or since the packet acknowledges unsent data (white area).
(2) In case that the Ack number is before UNA (gray area), then C (running Windows) discards it.
The probe which we use in the client sequence test specifies the acknowledgment number to be tested (an) and has two important properties: (1) the probe packet specifies sn, a sequence number that is within C's wnd (discovered in the server sequence exposing phase); (2) the probe packet specifies data.

Mallory
C S 1. Que ry 2. Pro be : Ac k = an , src = S (sp oo fed ) Se q = sn , pa ylo ad = "da ta" Re sp on se , id = i Dup lica te Ack

Qu ery
Re sp on se , id = j Figure 10: Client-Sequence Test. The dashed arrow marks the duplicate Ack that C sends S in case that an is in the white area in Figure 9. If j − i = 1, then C did not send that packet; in this case Mallory identifies that an is below UNA (i.e., in the gray area in Figure 9).

Ack Number Binary Search
The client-sequence test allows Mallory to conduct a binary search for the acknowledgment number that the client expects. If the client-sequence test for the ac-knowledgment number an indicates that C did not send any packet between the two queries, then an is before UNA (in the gray area in Figure 9). Otherwise, Mallory concludes that an is after UNA (in the black or white area in Figure 9). The gray and white areas in Figure 9 are of equal size, and the black area (sent bytes without acknowledgment) is usually relatively small. This allows Mallory to perform a binary search for UNA; each time eliminating approximately half the possible numbers. The 32-bit length of the Ack field (32 bits) implies that there are 32 iterations.

Sequence Exposure in Practice
In this section we discuss the applicability of the sequence exposure technique in practice; we assume the model presented in Section 1.

Implementing Test Queries/Responses
The server and client sequence tests we described in Sections 4 and 5 use packets that Mallory receives from C to learn the effect of the (spoofed) probe packet. Mallory can persuade C to send her such packets by using the legitimate TCP connection she has with C: a query is some short data packet that Mallory sends to C, the response is the C's acknowledgment sent back to Mallory.
This method allows Mallory to bypass typical firewall defenses since all packets in the test appear to belong to legitimate connections (requests to C-Mallory connection, probe to C-S connection). Specifically, Windows Firewall does not filter this technique.

Detecting Packet Loss
In order to succeed in sequence exposing, Mallory must identify when test packets are lost since the corresponding test will yield a wrong result. For instance, if a probe is lost, then its test will indicate that C respond to the probe and mislead Mallory.
Mallory detects a lost probe by repeating tests that indicate the client did not send a response (i.e., when j −i = 1). There should be only few such tests: one when probing for the server's sequence number and about sixteen during the binary search for the client sequence.
Mallory detects lost queries and responses by employing TCP congestion control. Since we implement the queries as data sent on a TCP connection, we are able to detect a lost query similarly to TCP congestion control mechanism: if Mallory receives several duplicate Acks, then she assumes that the corresponding query (a data packet) was lost. In this case Mallory repeats all the tests that she performed between the corrupt test and until its detection. Mallory detects a lost response by identifying that no Ack was received for one of the queries (instead an accumulative Ack was received); in this case she just repeats the invalid test.

Test Errors
The sequence exposure process uses the global IP-ID to determine whether a probe caused Cto respond. However, since every packet that C sends increments the IP-ID, errors may occur.
Such errors can appear only in tests where C does not respond to the probe: if C sends a packet in response to the probe, then the IP-ID is incremented, and the difference in IP-ID values of the responses that Mallory sees is at least 2; i.e., in this case Mallory always concludes that C had sent a packet 2 .
Hence, there are only few tests where an error is possible: during server sequence exposure only one test should indicate that no packet was sent, i.e., that Mallory found a sequence within the recipient flow control window. Mallory then conducts a binary search over the values in the flow control window to find the exact sequence number. There are approximately 16 iterations to this binary search, on average, half of these indicate that C does not send a packet in response to the probe. Similarly, the binary search for the client-sequence includes 32 iterations, on average 16 tests should indicate the C did not send a packet.

Experiments
In this set of measurements we evaluate the sequence exposure technique; in Sections 2 and 3 we evaluate the full attack (that requires sequence exposing and different successful 'meaningful' injections). The server in these measurements is runs Apache, and the client is an up to date Windows machine (protected by Windows Firewall). Figure 11 illustrates the success probability for different packets per second averages and when the puppet runs on different browsers. The average time for a successful sequence exposure is 102 seconds (standard deviation 18 seconds); this is the estimated time we require the client to stay in the attacker's site to conduct cross site scripting and initiate denial of service attacks (see Sections 2 and 3) 3 . Attacker and client bandwidths are respectively 1 and 10 mbps. In appendix A we provide a detailed comparison between our sequence exposure technique to the one previously presented in [27].

Defense Mechanisms
The attacks in this paper relay on successful exposure of the sequence numbers, the technique we presented for this task uses the global counter property of the IP-ID implementation in Windows machines. Deployment of IPv6 mitigates the IP-ID attack vector since the IPv6 fragmentation header (that specifies the IP-ID) is only present in fragmented packets. In most implementations, TCP employs path MTU discovery to avoid IPfragmentation. Hence, TCP connections over IPv6 are usually immune to our attacks.
In this section we propose defenses that prevent offpath sequence exposing. Our mechanisms are of two types, those deployed at the client-end, and those at the server-end. Each mechanism blocks the attack even if the other side is unprotected; i.e., servers and clients can independently protect themselves.

Server-End Defense
The defense at the server end uses feedback that the client machine (that runs the puppet) involuntarily sends as a side effect of the ID-exposing process. For every wrong guess of the server sequence number, the client sends the server a duplicate Ack (see section 4 and Figure 8). We monitor the acknowledgments that the server receives to detect the attack. The following two firewall rules provide indications of an ongoing sequence exposure attempt.
The first rule verifies that in no point in time the server receives more Ack packets than the number of un-Acked data packets that he had sent to the client. However, the adversary can trick this rule by using the puppet to request some data from the server, the short window of un-Acked packets ('in transit') allows testing few sequence numbers.
We can further improve detection of the sequence exposure attack for connections that employ the TCP selective Ack option. This option is used by most modern browsers, including Internet explorer, Firefox and Chrome. A selective Ack specifies the sequence numbers of out-of-order data that was received by the sender and allows to distinguish between a duplicate Ack generated by a network loss and a duplicate Ack due to sequence exposure attempt.
The second rule is enabled when the selective Ack option is used; it verifies that no two sequential Ack packets that the server receives are identical. Normally, a duplicate Ack is a result of a packet, p, that arrives out-oforder. In this typical case, p's sequence number must still be in the recipient's flow control window; hence, p's data is queued and the recipient sends a duplicate Ack to the source. The selective Ack attached to this feedback notifies that p's data was received. However, in the case of a sequence exposure attack, most of the probes that the attacker sends are out of the recipient's (client's) flow control window and are discarded. Therefore, the duplicate Ack response to a probe is identical to the previous Ack that the server had received.
After several indications of an attack, the firewall tears down the connection. Note that abuse of this mechanism to cause the server to close a legitimate connection with one of his clients requires the adversary to send to the client a probe that specifies the correct connection four tuple. However, since in contrast to our attacks, the offpath attacker does not create the legitimate connection (that she tries to tear down), it is challenging to expose the connection parameters (addresses and ports).

Client-End Defense
In this subsection we propose modifying the IPv4 identifier at the client's firewall (to replace the global counter). Since the identifier is only used by the recipient to match packet fragments, when a packet arrives at the sender's firewall, it can modify the IP-ID field without any implications on the sender or recipient (even if the packet will be fragmented later on the route). When a packet arrives in fragments at the firewall, then it must map all fragments of the same packet (those that specify the same reassembly four tuple -IP addresses, protocol and IP-ID) to the same identifier.
The first, intuitively appealing direction seems to be using random identifiers. However in IPv4 this is not recommended, according to the birthday paradox, in roughly 1.2 √ 2 16 = 1.2 · 2 8 = 307 packets there will be a repetition (since the field is 16 bits long), which would cause fragments of one packet to be mis-associated with others, and hence cripple performance.
The IP standards [35,11] specify that IP fragments are associated with a packet according to four parameters: source and destination addresses, transport layer protocol (e.g., TCP), and identifier. Therefore, a simple solution would be that each source, destination, protocol tuple will be associated with a different identifier counter, initialized by a keyed pseudo random function f , i.e., the initial identifier is f k (source, dest, protocol). In Linux, the choice of IP-ID is similar, but is only based on the source and destination addresses.
FreeBSD supports using random IPv4 IDs which are permuted locally: a packet is assigned with a random IP-ID that was not specified in one of the recent (8192) packets that were sent 4 . Both Linux and FreeBSD approaches immune the TCP connection to our attacks.

Conclusions
In this work, we show that the folklore belief that TCP is secure against spoofing-only, off-path attackers is unfounded. We show practical, realistic injection attacks. We further show that this allows crucial abuses, breaking the same-origin policy defense which is critical to web security, and allowing devastating DoS attacks.
One important conclusion is that Bellovin [10] was right: TCP was never designed for security, and should not be expected to provide it. To ensure authentication and confidentiality, even against (only) spoofers, we should use secure protocols such as SSL/TLS [12] or IPsec [23]. SSL/TLS may not suffice to prevent (lowerlayer) attacks such as the DoS attacks presented in this paper (Section 3); to prevent these too, we should use lower-layer security mechanisms, preferably IPsec or other mechanisms, e.g., see [42,16].
A potentially more controversial conclusion is that basic vulnerabilities should be investigated and fixed, even before demonstration of a complete, practical, exploit. In this paper, we went into great length to prove the practicality of the vulnerability, since earlier results were considered as 'impractical'. We believe that the network security community should adopt a more prudent approach, publishing and addressing issues and potential vulnerabilities, without waiting for a complete exploit. Compare the approach in the cryptographic community, where even yet-theoretical attacks are taken into account, published and motivate design of improved ciphers.

A Comparing Performance of TCP Injection Attacks
In this appendix we compare the existing approach and technique for TCP injection presented in [27] to those presented in this paper. The significant difference between the two approaches is that [27] injects data to a legitimate existing connection between two peers (C and S) where in this paper we use a puppet to create the victim connection. This difference has three implications we describe below. First, the attacker must identify the connection between C and S and expose its parameters (IP addresses and ports). In [27] attacker is assumed to have previous knowledge of the client and server addresses as well as the server's port; in this paper we assume only knowledge of the server's address and port which are usually available. In order to expose the client's port, in [27] the attacker performs a variant of the idle scan, indirectly scanning all possible client ports. The scan is as follows: the attacker sends a SYN to the server spoofed as if from the client; if there is already a connection through the client port specified in the SYN packet, then the server ignores the spoofed SYN. Otherwise the server sends a SYN/ACK packet to the client who will respond in RST. The attacker uses the global IP-ID to test whether the client sent a packet in response.
Implementing this method for probing the client port has a few challenges: (a) this technique is filtered by typical client firewalls (e.g., Windows Firewall) that will discard the SYN/ACK server response in case that the client did not first send a SYN. (b) attacker must run a synchronized attack, querying for the client IP-ID, then assume that the server probe had arrived and query for the IP-ID again; if during this time C sends a packet or server SYN/ACK does not yet arrive then the test is invalid.
In contrast, we create the connection using the puppet and identify the client port by using an insight on Windows port allocation paradigm. This allows us to form a connection with an 'interesting' server and efficiently detect its parameters (see Section 2.1).
Second, the attacker in [27] must cope ongoing traffic over the victim connection itself. Such traffic fails the binary search for the client sequence number (see Section 5) since this phase requires specifying a valid sequence number (which keeps changing due to traffic on the connection). Moreover, [27] does not describe how to implement the queries to (1) avoid firewall filtering and (2) detect network losses. In the approach presented in this paper, the attacker controls the connection since her puppet makes the requests for the server. Hence she is able to avoid traffic on the connection while exposing the sequence numbers. The legitimate TCP connection with the client is used to implement the queries (see details in Section 6).
In Figure 12 we compare the success rates of our attack to that described in [27] where the victim connection in while running the attack in [27] has only a modest 10 kbps traffic rate (since attacker does not control the traffic rate in this case). The comparison is for different network delays between the client and attacker; the longer the delay, the more time until the attacker receives feedback and the more traffic that passes on the connection. Since [27] does not specify how to implement the queries, we used our method, i.e., on a TCP connection between the client and the attacker. We assume that the attacker in [27] successfully detects the client port (despite the challenges above). We also assume that the client sends an average of 32 packets per second to other peers. The third difference between our approach to [27] regards to the practical challenge of performing a 'meaningful' injection. That is, after a successful exposure of sequence numbers, the attacker should identify the right time to inject his data; For example, to perform the XSS attack, the spoofed response must arrive after the client had sent a request; it is hard for an off-path attacker to detect that time. In contrast, the attacks in this initiate the request using the puppet and inject the response (see Section 2).


Evaluating Machine Reading Systems through Comprehension Tests

This paper describes a methodology for testing and evaluating the performance of Machine Reading systems through Question Answering and Reading Comprehension Tests. The methodology is being used in QA4MRE (QA for Machine Reading Evaluation), one of the labs of CLEF. The task was to answer a series of multiple choice tests, each based on a single document. This allows complex questions to be asked but makes evaluation simple and completely automatic. The evaluation architecture is completely multilingual: test documents, questions, and their answers are identical in all the supported languages. Background text collections are comparable collections harvested from the web for a set of predefined topics. Each test received an evaluation score between 0 and 1 using c@1. This measure encourages systems to reduce the number of incorrect answers while maintaining the number of correct ones by leaving some questions unanswered. 12 groups participated in the task, submitting 62 runs in 3 different languages (German, English, and Romanian). All runs were monolingual; no team attempted a cross-language task. We report here the conclusions and lessons learned after the first campaign in 2011.

Introduction
In contrast to traditional QA, where answers are determined by skimming large document collections, Machine Reading (MR) systems read only a handful of texts and analyse them in depth in order to obtain answers (Etzioni et al., 2006). Successful systems must generally perform complex inferences. Since frequently the source text is incomplete, the systems need access to background collections of documents or other sources of information such as Wikipedia or databases of facts. Evaluating MR is complex. Since each system has its own internal knowledge representation, cross-system comparisons (before and after reading) are difficult. A simpler approach is to treat MR evaluation as an Information Extraction task (did the system extract the correct information?) or as a QA task (is the system able to read and reason in order to arrive at the correct answer?). In the QA approach, two models are possible. In one, a formal language (target ontology) is defined, and systems are required to translate texts into this representation. Evaluation can then take place by submitting structured queries in the formal language in order to determine if certain inferences have been made. However, there are certain problems with this approach and in consequence we have developed a new model, influenced by previous research on QA and reading comprehension (Wellner et al., 2006). A series of questions is asked for each document, and each question has a set of multiple-choice answers. This allows complex questions to be asked but makes evaluation simple and completely automatic. The evaluation architecture is completely multilingual: test documents, questions, and their answers are identical in all the supported languages. Background text collections are comparable collections harvested from the web for a set of predefined topics. This approach allows deep natural language processing issues to be investigated in both monolingual and cross-lingual contexts.

Motivation
For some years it has been clear that there is an upper bound of 60% accuracy in QA systems, despite more than 80% of questions being answered correctly by at least one participant. Analysis uncovered a problem of error propagation in the traditional QA pipeline (Question Analysis, Retrieval, Answer Extraction, Answer Selection/Validation). Thus, in 2006 we proposed a pilot task called the Answer Validation Exercise (AVE) (Peñas et al., 2006). The aim was to produce a change in QA architectures, giving more responsibility to the validation step, which could help to overcome the limitations of pipeline processing. After three AVE campaigns, we transferred our conclusions to the main QA task at CLEF in 2009 and 2010 (Peñas et al., 2010). The first step was to introduce the option of leaving questions unanswered, which is a strategy related to the development of validation technologies. We needed a measure able to reward systems that withheld answers to certain questions if they were not sure of them. The result was c@1 , a measure tested during the 2009 and 2010 QA campaigns at CLEF, and also used in the current evaluation. However, this change was not enough. Almost all systems continued using IR engines to retrieve relevant passages and then tried to extract the answer from that. This was not the change in architecture we expected, and again, results remained below the 60% pipeline upper bound. We concluded that the change in architecture requires a previous development of answer validation/selection technologies. For this reason, in the current formulation of the task, the step of retrieval is put aside for a while, in place of a focus on the development of technologies able to work with a single document. This development parallels the introduction in 2009 of the Machine Reading Program (MRP) by DARPA in North America. The goals of the program are to develop systems that perform deep reading of small numbers of texts in given domains and to answer questions about them. Analogously to QA4MRE, the MRP program involves batteries of questions for the evaluation of system understanding. However, testing queries were structured according to target ontologies, forcing participant teams to focus on the problem of document transformation into the formal representation defined by these target ontologies. Thus the Machine Reading challenge had to pass through the Information Extraction paradigm. In QA4MRE we think it is important to leave the door open to find synergies with emerging research areas such as those related to Distributional Semantics, Knowledge Acquisition, and Ontology Induction. For this reason, we are agnostic with respect to the query language and the internal machine representation. Thus, questions and answers are posed in natural language.

The QA4MRE Task
As we have seen, the task this year was to answer a series of multiple choice tests, each based on a single document (Peñas, Hovy et al., 2011). Tests comprised three topics, namely "Aids", "Climate change", and "Music and Society". Each topic included 4 reading tests. Each reading test consisted of a single document, with 10 questions and a set of five choices per question. In this campaign, the evaluation had in total: -12 test documents (4 documents for each of the three topics), -120 questions (10 questions for each document) with -600 choices/options (5 for each question).

Test Documents
After some consideration, we used parallel documents, in English, German, Italian, Romanian, and Spanish, taken from the Technology, Entertainment, Design (TED) conferences (www.ted.com). Each TED event consists of a series of twenty-minute presentations by prestigious speakers, from fields such as politics, entertainment and industry. The selected talks range in length between 1,125 and 3,580 words. We verified that the translations (based on English transcriptions) are of very high quality.

Questions
Questions were posed by studying the test documents, as is the norm in QA evaluations. Questions may refer to: facts that are explicitly present within a single sentence in the text, facts that are explicitly present, spread over several sentences, facts that are not explicitly mentioned, but are one inferential step away (cf. the RTE challenge), facts that are explicitly mentioned but require some inference in order to be connected together so as to form the answer.
Out of the 120 questions, 44 needed extra information from the background collection, while the document alone was sufficient for 76. 38 questions had the answer in the same paragraph, while for 82, several paragraphs were needed. Questions were posed so that answers were not merely a mechanical repetition of the input. Instead, all kinds of textual inferences could be requested, such as lexical (acronym, synonymy, hyperonymy-hyponymy), syntactic (nominalization-verbalization, causative, paraphrase, active-passive), and discourse (co-reference, anaphora ellipsis).

The Background Collections
One focus of the task is the ability to extract different types of knowledge and to combine them as a way to answer the questions. In order to allow systems to acquire the same background knowledge, ad-hoc collections were createdone for each of the topicsin all the languages involved in the exercise, i.e., English, German, Italian, Romanian, and Spanish. These collections were created by crawling the web. They are thus comparable across languages but are not parallel. The collections were made available to all participants at the beginning of April so that they could be used to acquire domain specific knowledgein one language or severalprior to taking part in the QA4MRE task.

Evaluation
Evaluation was performed automatically by comparing the answers given by systems to the ones prepared by the organisers. No manual assessment was required because of the multiple-choice format. Each test received an evaluation score between 0 and 1 using c@1. This measure encourages systems to reduce the number of incorrect answers while maintaining the number of correct ones by leaving some questions unanswered. The task allowed us to evaluate systems from two different perspectives: -As a question-answering evaluation, where we just counted correct answers without grouping them.
-As a reading-test evaluation, where we obtained figures both for each reading test, and for each topic. Concerning a baseline level of performance, there are five possible answers to each question, with exactly one being correct. Assuming that all questions are answered, the random baseline is 0.2 (both for accuracy and c@1).

Participation and Results
Out of the 25 groups that originally registered, 12 participated in the task, submitting 62 runs in 3 different languages (German, English, and Romanian). All runs were monolingual; no team attempted a cross-language task. Participants were allowed to submit a maximum of 10 runs. The first run was to be produced using nothing more than the knowledge provided in the background collections. Additional runs could include other sources of information, e.g., ontologies, rule bases, the web, Wikipedia, etc., or other types of inferences.
As for system performance at the question-answering evaluation level, only one team (jucs) scored above 50%. From a reading test perspective, no group passed. System performance was not significantly better than the random baseline. There is thus great potential for future improvement on both sides, not only system development but also in the evaluation methodology.

Lessons Learned
The first difficulty we had to address was the definition of Background Knowledge. This is required in order to make consistent decisions about the methodology for harvesting background collections and for developing the testing questions and answers

Definition of Background Knowledge
Reading Comprehension tests are routinely used to assess the degree to which people comprehend what they read, so we work with the hypothesis that it is reasonable to use these tests to assess the degree to which a machine "comprehends" what it is reading. When reading a text, a human performs two processes, namely: 1. s/he partially/fully understands its meaning; 2. if needed, s/he makes additional inferences from the text, i.e., performs some kind of reasoning, and solves the textual inferences (linguistic/lexical, co-reference), using previously acquired experience/knowledge of any type.
We assume that the answer to a question almost always requires some prior knowledge. Resources such as wordnets, framenets, paraphrase bases, knowledge bases are aimed at make different kinds of prior knowledge available for the machine. We add to these resources the possibility to acquire background knowledge from a large collection of related documents. The advantage is the opportunity to gather probability distributions linked to knowledge, and explore distributional approaches.
The answers to the questions should never come from this prior knowledge alone. The answer must be found in the Test Documents, but references to information outside it may be required, as there may be explicit and implicit references to entities, events, dates, places, situations, etc. pertaining to the topic. Therefore, the definition of Background Knowledge must be given, in our case, in terms of the relation between the testing questions and answers, and the background collection. In other words, what is the use of the prior knowledge? For this purpose, we distinguish at least four main types of background knowledge (although in fact it is a continuum): 1. Very specific facts related to the document being read. For example, the relevant relation between two concrete people involved in a specific event. 2. General facts not specific to any particular event. For example, geographical knowledge, main players in international affairs, movie stars, world wars. Also acronyms, transformations between quantities and measures, etc.
3. General abstractions that humans use to interpret language, to generate hypotheses, or to fill missing or implicit information. For example, abstractions as the result of observing the same event with different players (e.g., petroleum companies drill wells, quarterbacks throw passes, etc.) 4. Linguistic knowledge. For example, synonyms, hypernyms, transformations such as active/passive, or nominalizations. Also transformations from words to numbers, meronymy, metonymy.
Obviously this is not an exhaustive list. For example, we are not talking about ontological relations that enable temporal and spatial reasoning, or reasoning on quantities.
In summary, the questions should be answerable by most humans using their general knowledge, without the need to explore a specific document of the background collection. Examples of inferences we allow are: 1. Linguistic inferences such as coreference, deictic references (like "then" and "here"), etc.) 2. Simple ontological inferences such as considering part-of relations or obtaining direct super-concepts for common objects. 3. Inferences considering causal relations or procedural steps in "life scripts" like visiting a restaurant or attending a concert. 4. Inferences that require composing several answers, in particular answering one part of the question using the background collection and then, with its answer, answering the other part of the initial question (e.g., "Who is the wife of the person who won the Nobel Peace Prize in 1992").

Creation of Background Collections
This is a very important element of the evaluation setting. It connects the task with research in Information Retrieval. The goal of reference/background collections is to contextualize the reading of a single document related to the topic. Thus, we could expect that in the future this step could be done on the fly as a retrieval process given the single text being read. But for now, the organization is doing this for two main reasons: to enable better comparison among participant systems, and to focus on the Reading Comprehension problem. Therefore, it is very important to develop a good methodology to build these background collections for the evaluation task.
Ideally, the background collection should completely cover the corresponding topic. This is sometimes feasible and sometimes not. For example, in the case of the pilot task on Biomedical documents about Alzheimer's disease (see Section 5.3), a set of experts built a query (a set of conjunctions and disjunctions over 18 terms) that closely approximates the retrieval of all relevant documents (more than 66,000) without introducing much noise. However, this is not so easy in more open domains such as Climate Change, or when one wants to consider non-specialized sources of information. In these cases, we crawl the web using, for each language and topic, a list of keywords and a list of sources. Keywords are translated into English and then translated into the other languages. Documents may be crawled from a variety of sources: newspapers, blogs, Wikipedia, journals, magazines, etc. The web sources are obviously language dependent, so each language requires also a list of possible web sites with documents related to the topic. However, we face the same problem as does traditional Information Retrieval: we want all relevant documents (and only them), and we use queries (keywords) to retrieve them. We realized that, since the organizers knew the test set, they used that information to select the keywords, and ensure the coverage of the questions. The effect is not only that background collections don't cover completely the topic, but also that the collection has some bias with respect to the real distribution of concepts.
The assumption that the ideal background collection should include all relevant documents for the topic is explicit, and we organizers have it in mind. Our first strategy with the aim of ensuring the coverage of the topic as much as possible is to make the topic specific enough (e.g., AIDS medicaments instead of AIDS). The second strategy is to try to cover (at least partially) each of the possible "dimensions/aspects" of that topic, which we do as follows: First, we locate a good central overview text, such as a Wikipedia article that "defines" the topic, "suggests" its principal aspects (often in subsections), and provides some links. Then, we enumerate these dimensions and prepare a set of queries for each dimension. We document this process with three benefits: (i) to know what organizers and participants can expect or not from the collection; (ii) to give another dimension of re-usability; and (iii) to explore how Machine Reading will connect to Information Retrieval in the future.

Toward 2012
After the 2011 QA4MRE evaluation, we have prepared for the next campaign by refining the methodological issues above. In 2012, we will have a main task and two pilot exercises.

Main Task
The main task will remain the same for participants. Background collections, test documents, and reading tests will be available in Arabic, Bulgarian, English, German, Italian, Romanian, and Spanish. In addition to last year's topics (AIDS, Climate Change, Music and Society), we will include a topic on Alzheimer's disease. This new topic is related to a new pilot on Biomedical texts. The difference is that the reference collection for the main task is built from general public sources and for the pilot the source is the PubMed repository.
Having these two parallel exercises on the same topic but in different domains opens the door to evaluating research on the challenges of domain and language adaptation, the use of knowledge in one domain captured in the other, the differences in the background knowledge acquired, the differences between questions and answers in each domain, etc.

Pilot on Processing Modality and Negation for Machine Reading
This exercise is aimed at evaluating whether systems are able to understand extra-propositional aspects of meaning, such as modality and negation. Modality is a grammatical category that allows expressing aspects related to the attitude of the speaker towards his/her statements. Modality understood in a broader sense is also related to the expression of certainty, factuality, and evidentiality. Negation is a grammatical category that allows changing the truth value of a proposition. For this purpose, participants will receive some tests where they have to decide whether some events are Asserted, Negated, or Speculative. Our plan is to integrate modality and negation in the main task next year.

Machine Reading on Biomedical Texts about Alzheimer's disease
This Pilot is aimed at setting questions in the Biomedical domain with a special focus on one disease, namely Alzheimer's. This pilot task will explore the ability of a system to answer questions using scientific language. Texts will be taken from PubMed Central related to Alzheimer and from 66,222 Medline abstracts. In order to keep the task reasonably simple for systems, participants will be given the background collection already processed with Tok, Lem, POS, NER, and Dependency parsing.

Conclusions
In 2011, the QA@CLEF task was characterised by two major innovations. First, there was a transition from traditional Question Answering based on shallow analysis of large document collections to a new focus involving deep analysis of individual documents. Over the years, the QA challenges adopted simple questions that required almost no inferences to find the correct answers. These surface-level evaluations promoted QA architectures based on Information Retrieval (IR) techniques, in which the final answers were obtained after focusing on selected portions of retrieved documents and matching sentence fragments or sentence parse trees. No real understanding of documents was achieved, since none was required by the evaluation. Machine Reading, on the other hand, requires the automatic understanding of texts at a deeper level, so this task encourages participants to build a different kind of system. The second innovation of the task lay in the evaluation. Instead of manually inspecting answers to judge whether they were correct, evaluation was entirely automatic. This was made possible by adopting questionnaires comprising multiple-choice questions whose exact answers could be determined in advance. This strategy also enabled more complex types of question to be asked as well as posing fewer restrictions on the form of the answers. Significant lessons were learned from this new evaluation which was also well received by the QA community. This opens the way for future evaluations based on similar principles.


Decreasing defect rate of test cases by designing and analysis for recursive modules of a program structure: Improvement in test cases

Designing and analysis of test cases is a challenging tasks for tester roles especially those who are related to test the structure of program. Recently, Programmers are showing valuable trend towards the implementation of recursive modules in a program structure. In testing phase of software development life cycle, test cases help the tester to test the structure and flow of program. The implementation of well designed test cases for a program leads to reduce the defect rate and efforts needed for corrective maintenance. In this paper, author proposed a strategy to design and analyze the test cases for a program structure of recursive modules. This strategy will definitely leads to validation of program structure besides reducing the defect rate and corrective maintenance efforts.

I. INTRODUCTION
Testing phase of software development life cycle lead to the quality of software products and it depend on the strategies which are followed by tester role. The most commonly used methods of testing are black-box and whitebox testing [1]. In black-box tester examine the fundamentals aspects of software; while in white-box tester examine the internal procedure detail of the system components such path testing and loop testing. During white-box testing test cases can be generated either manual or through automated tool to check the working of software. A test case is a set of conditions or variables which are included in the working of software [5,7]. The focus of this paper is to design and analyze the generation of test cases for recursive modules in programming language. Here author's proposed a strategy which helps to reduce the defect rate and corrective maintenance efforts.

II. RECURSIVE MODULES
In programming language structure recursive modules are those routines which called itself during execution of program and they can consider as central idea of computer science [6,8]. There are two factors which are relevant to recursive modules. First is the base case used to end the calling of recursive module and second is to break the current domain of data into sub domains and this will remain continue till base case satisfied [10,11]. Recursive modules are classified into linear, mutual, binary and N-Ary Types.
III. WHITE BOX TESTING White box testing is the process to test the implementation of a system. It consist of analysis of data flow, control flow, information flow , coding practice and exception handling within the system to ensure correct software behavior. White box testing can be perform by tester any time after coding but it will be good practice to do it with unit testing. White box testing is used with unit, integration and regression testing. In white box testing method tester role can perform the following activities [3].  It defines the test strategy and activities.  It develop new test plan on the base of selected strategy.  It creates an environment for test case execution.  It executes the test cases and prepared reports. The main types of white box testing are static and dynamic analysis, branch coverage, security testing and mutation testing. Selection of skilled tester and bit of code to remove error are considered as important challenge in white box testing [9]. In software project the success of testing depend on the test cases used. To reduce the turn around time, defect rate and project duration it is important to design an effective set of test cases that enables detection of maximum number of errors [12].

IV. FLOW GRAPH NOTATION (FGN)
In white-box testing Flow Graph Notation (FGN) is a used to represent the program control structure. It is just like flowchart and comprises on circle and edges. Each circle, called a flow graph node, represents one or more procedural statements and edges represent the flow of control. An edge must terminate at a node, even if the node does not represent any procedural statements. Areas bounded by edges and nodes are called regions. When counting regions, we include the area outside the graph as a region.

V. ANALYSIS OF TEST CASES FOR RECURSIVE MODULES
To represents the analysis and design process of recursive modules an example in C++ language is taken as shown in Fig-1. In this example two recursive modules/functions are used named as "Factorial" and "SumofFact". Following steps are used to represent the working of C++ program shown in Fig-1.
 Firstly a number is read in the main module/function of program.  Secondly a recursive module named "Factorial" is called from main function to find the factorial of entered number. If number is 4 then result of "Factorial" function will be 24 i.e. 4! = 24.  In third step another recursive module named "SumofFact" is called to add the sum of factorial of all numbers ranges from 1 to entered number. If number is 4 then result of this function will be 1!+2!+3!+4!=33 To analyze the complexity of program (shown in Fig-1) a Flow Graph Notation is drawn which is shown in fig-2. This FGN represent the all paths which can be used to analyze and design the test case for program. As there two factors, which are related with recursive module, first is the base condition which is applied to end the calling of recursive modules and second factor is relevant to division of domain of data for recursive module into sub domains. The complexity of recursive module calling can be analyzed with respect to two aspects. 1. Calling of a recursive module from any other module which is not recursive in nature. 2. Calling of a recursive module from any other module which is recursive in nature.

Fig-1. C++ Program including recursive modules/functions
The complexity of program will be high for second aspect as compared to first. The program shown in Fig-1 represents the both aspect of calling the recursive module. The first aspect is represented through calling of "Factorial" recursive module/function and second is through calling of "SumofFact". In "SumofFact" recursive module/function "Fact" is again called. This process leads to increase the complexity of program.

Analysis and Designing of Test cases and test data for the first Aspect:
The first aspect shows the calling of recursive module/function from another function which is not recursive in nature. If we omit the "SumofFact" recursive function from program shown in Fig-1 and its calling from main module. Then there be will only two possible path to represent the execution of "Factorial" recursive module.
1-2-3-4-7-8-9-11-7-8-10-12-11-5 The first path represents the execution of statements of calling and called module in sequence. Which show the recursive module "Factorial" is called only one time from "main" module and it is not called by itself. The test case for this path will be n<1 and test data for this test case may be 0 or any negative number. The second path represent that recursive module is called many time depend on the domain of data, this is shown in highlighted part of path i.e. 7-8-9-11. When the recursive module is called by itself last time then base condition will be executed which is shown in 7-8-10-12 part of second path. After that control will be transfer by recursive module to itself, this is shown in another highlighted part of second path i.e. 11. At the end control will be transfer back to the "main" calling module of recursive module. The test case for this path will be n>=1 and test data may be any positive value. If one recursive module is called many times from "main" calling module then same two paths will be used except the nodes of FGN will be increases. It is clear from this analysis that test case and test data will remain same whether you will called a recursive module one or more than one time.

Analysis and Designing of Test cases and test data for second Aspect:
The second aspect shows the calling of recursive module/function from another function which is recursive in nature. According to program of Fig-1 "SumofFact" is the calling module of "Factorial" recursive module and "SumofFact" itself is recursive module. To analyze the test cases for this aspect firstly omit the node 4 from FGN of "main" module. This will show that "Factorial" recursive module will not called from "main" module. There be will only two possible path to represent the execution of "SumofFact" and "Factorial" recursive modules.

Fig-2. Flow Graph Notation for C++ Program of recursive modules
sequence. In this path execution of "Factorial" recursive module is not shown because here the base condition of "SumofFact" is executed and it not called itself. The test case for this path will be n<0 and test data may be 0 or any negative number. The second path represents the more than one time execution of "SumofFact" and "Factorial" modules. The part of second path i.e. 13-14-15-17-7-8-9-11-19 as a whole represents the recursive execution of both modules. In this part of second path i.e. 13-14-15-17 represents the execution of "SumofFact" and calling of "Factorial" recursive modules. Moreover, in this part of second path i.e. 7-8-9-11 represents the execution of "Factorial" recursive module and returning control back to the node 19 of FGN. This node also represents the calling of "SumofFact" recursive module i.e. same process will be repeated till the test case n<0 is satisfied. The test case for this path will be n>0 and test data may be any positive number. Moreover, from this analysis it is clear that first path eliminate the execution of base condition of "Factorial" recursive module, but it will not true for all cases. This is also illustrating here that during analysis and designing of test cases, some test cases can not show the execution of some part of a recursive module. So there is need to be more care during analysis and designing of test cases of recursive modules especially when a recursive module call another recursive module. If tester role will not care about it then it can leads to increase the defect rate and corrective maintenance efforts. Besides caring of tester role in analysis of recursive modules, it must care about the levels. If level to call one recursive module within another recursive module is increases then complexity of program will high and it will leads towards increases in defect rates.
VI. CONCLUSION During white-box testing process the use of FGN and deriving path are the basis steps to analyze and design the test cases and test data. In this paper authors adopt a strategy to analyze and design the test cases for recursive modules, which are considered as important paradigm in programming language. After analysis and designing process of test case authors known that some part of the recursive modules can not be implemented through test case which can increase the defect rate and corrective maintenance efforts.