CS244 ’16: TCP Congestion Control with a Misbehaving Receiver


Team: Varun Ramesh (vramesh2@stanford.edu) and Blane Wilson (bctwilson@stanford.edu)

Source Code: https://github.com/rameshvarun/misbehaving-receiver

Paper: Savage, Stefan, Neal Cardwell, David Wetherall, and Tom Anderson. “TCP congestion control with a misbehaving receiver.” ACM SIGCOMM Computer Communication Review 29, no. 5 (1999): 71-78.

Introduction

End-to-end congestion control mechanisms in TCP typically assume that hosts are well-behaved. However, a malicious receiver can trick other hosts into flooding the network with packets, thus inducing congestion collapse and reducing throughput for everyone across the network.

The paper “TCP Congestion Control with a Misbehaving Receiver” by Savage Cardwell et. al., demonstrates three attacks that a malicious receiver can use to trick a sender running standard TCP congestion control. In order to make TCP implementations more resilient, the authors also propose defenses for each of their three attacks.

Original Results

The first attack the authors propose is ACK division, which exploits the fact that TCP congestion control operates at the segment level – not on individual bytes. The attacker, on receiving a data segment, divides the data range into M portions, ACKing each individually. Since there are M times as many ACKs received, the sender’s congestion window will increase at M times the normal rate.

The second attack is duplicate ACK spoofing, where the attacker ACKs every packet that it receives multiple times. The sender incorrectly inflates its congestion window, since it believes the duplicate ACKs are an indication that its data packets are leaving the network.

The third attack is the optimistic ACK attack, where, upon receiving the first data packet, the receiver sends a stream of ACKs to the sender for data which it has not yet received. The sender, confused by these ACKs, will put more data into the network before the previous data has left the network.

Subset Goal

We chose to implement the optimistic ACK attack and it’s associated defense. We chose this attack because it is easy to implement but hard to defend against, making it especially devastating. Below is a figure showing the attack in action, taken from the original paper. The attacker is able to flood the network with data packets at a rate much faster than a normal connection.

Screen Shot 2016-05-28 at 8.19.28 PM

The authors propose two defenses against optimistic ACKs. One requires modifying both the sender and receiver, while the other requires modifying only the sender. We chose the latter, since we felt it would be more realistic – the defended stack would be backwards compatible with normal stacks. This defense required two changes – first, ignore ACKs that do not fall on a segment boundary. Next, randomly vary each output segment’s size by a small amount, thus preventing the attacker from correctly predicting the segment boundary.

Implementation

Our network simulator of choice was Mininet, which was run on Ubuntu (14.04.2 LTS 64-bit)  VMs. We used Mininet since it was familiar to us and had helpful tools like a command line interface. It also allows us to reproducibly specify link speed, delays, and queue sizes. Our topology is simply two hosts connected by a switch – delays and bandwidth are configurable, but the defaults are seen here. We kept the link delay high to eliminate variations caused by CPU delays.

We created four TCP clients – the three attackers plus a normal client (telnet) – and three TCP servers – one using the kernel stack, one using the lwip stack, and one using our modified lwip stack. Our clients simply make a connection and wait for data, while our servers send 100,000 bytes of data to every connecting client. We tested the entire 4×3 matrix.

The misbehaving receivers are written in Python using Scapy, a powerful packet-manipulation tool that can send and receive packets using raw sockets. Our “normal” server is a simple script written in Python.

Because we decided to implement a defense, we needed a TCP stack that we could modify. We thought patching the kernel (like the original authors) would be too complicated given time constraints – instead we used lwIP, a user-space TCP stack. In order to use lwIP, we had to create a TAP device, backed by a Linux port of lwIP, called lwip-tap. This TAP device runs in the server’s container, and packets received by the container are forwarded to the TAP device. lwIP came with an echo server, which we modified to create our data server.

We used the same technique to connect our defended lwIP stack. Our defense only edits tcp_in.c and tcp_out.c in lwIP, and required adding ~10 lines of code.

Our packet dumps are captured using tcpdump, and all of our graphs were made using Matplotlib. We successfully replicated the results on a c3.large Amazon EC2 Instance running Ubuntu (14.04.2 LTS 64-bit) with the  CS244-Spr15-Mininet AMI (Mininet version 2.2.1d2). We also replicated our results on the PA1 VirtualBox VM, which used Mininet version 2.2.1.

Our Results

We successfully replicated the optimistic ACK attack against the lwIP stack. Below is our graph of the connection, which exhibits the same pattern as the author’s implementation.

lwip-opt-ack

There are some differences – our attacking connection has sequence numbers that are linear in time, while the author’s figure exhibits a curve. This may be due to the fact that we ran our tests in a network emulator, while the authors attacked CNN.com. We also have a larger link delay, which results in more gaps along the time axis. Finally, the author’s connection seems to observe a multiplicative decrease after 0.45 seconds, while we don’t observe any congestion window decreases.

The next image shows our defended LWIP Stack vs. the Optimistic ACK Attacker – we can see that our stack ignores all of the optimistic ACKs, and the connection does not continue any further.

defended-lwip-opt-ack.png

Challenges

The main challenge of project was implementing the defense, which required a considerable amount of time studying lwip-tap and the lwIP stack. Furthermore, the documentation for lwip-tap was sparse, making it difficult to figure out how to run an lwIP-backed TCP server. Integrating the lwIP’s TAP device with the Mininet topology was also a challenge – we ultimately needed to enable IPv4 forwarding, set up a route to the TAP device’s IP address, and enable Proxy ARP requests so that packets to the TAP device would be forwarded through the server’s Mininet container. Finally, we found that on the VirtualBox VM, our clients could make connections using raw sockets, but on AWS, the kernel would send RST packets for the unknown connections. We fixed this using an iptables rule.

Conclusions / Critique

We were able to successfully replicate the optimistic ACK attack, demonstrating that this weakness is still present in TCP today. We were also able to implement a defense, confirming that, in theory, TCP stacks can be defended against optimistic ACK attackers. However, we feel that, other than the defense for ACK division, none of the proposed defenses are realistic in practice. Two of the defenses described in the paper require changes to both receiver and sender via an extra TCP header, which seems impractical to deploy. The defense that we implemented only required changes to the sender, but we still feel it shouldn’t be deployed since there may be legitimate reasons for a receiver to not ACK on segment boundaries.

If this paper was written in 1999, and we are still able to successfully perform the optimistic ACK attack, it brings into question whether TCP will ever be defended against this attack.

Future Work

While we implemented the ACK division and duplicate ACK attackers, we were not able to get the results we expected. If we had more time, we would have liked to investigate the discrepancies and determine if the attacks were implemented incorrectly, or if the stacks were already defended against the attacks. Since we also saw that the kernel TCP stack was vulnerable to optimistic ACK attackers (image below), we would have liked to patch the kernel in order to implement a defense.

kernel-opt-attack.png

Finally, we think it would be prudent to understand how optimistic ACK attackers affect other flows that might be using the same links. The paper “Misbehaving TCP Receivers Can Cause Internet-Wide Congestion Collapse” by Sherwood et. al. investigates this, and we would like to replicate and expand on their research.

Replicating Results

Instructions for replicating our experiments and graphs can be found here.

2 responses to “CS244 ’16: TCP Congestion Control with a Misbehaving Receiver

  1. 5 for reproducibility. The graphs matched up very well, and the process couldn’t have been any easier. Great job, guys!

    • We felt bad just leaving two lines of comments seeing that you guys put a lot of effort into this post, so we’ll go into more depth:

      Like we said above, reproducing the results was a painless process. All we had to do was spin up a server, checkout the repository, and run the script. It was nice that you specified which files to look at! We did notice a very slight difference in the Kernel TCP Stack vs Optimistic ACK Attacker graph. Our graph had no normal data segments past 0.6s while it looks like you guys have two such segments, but this is probably just due to variations in how things are scheduled. The difference is small enough that it can be ignored.

      Overall, we found the paper and your guys’ post interesting. It’s surprising that this attack isn’t more well-known/taught widely, considering the devastating effects that it can cause. The fact that this is the case probably means that there are more economical attacks out there for attackers to use, which would explain why this defense isn’t more widely implemented (and probably never will be) for TCP.

      Again, great job!

      – Jintian and Jason

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s