GitHub Engineering

GitHub hosts a wide range of user content, and like all large websites this often causes us to become a target of denial of service attacks. Around a year ago, GitHub was on the receiving end of a large, unusual and very well publicised attack involving both application level and volumetric attacks against our infrastructure.

Our users rely on us to be highly available and we take this seriously. Although the attackers are doing the wrong thing, there’s no use blaming the attacker for their attacks being successful. Our commitment is to own our own availability, and that we have a responsibility to mitigate these sorts of attacks to the maximum extent technically possible.

In an effort to reduce the impact of these attacks, we began work on a series of additional mitigation strategies and systems to better prepare us for a future attack of a similar nature. Today we’re sharing our mitigation for one of the attacks we received: synsanity, a SYN flood DDoS mitigation module for Linux 3.x.

What is a SYN flood anyway?

SYN floods are one of the oldest and most common attacks, so common that the Linux kernel includes some built in support for mitigating them. When a client connects to a server using TCP, it uses the three-way handshake to synchronise:

TCP Three-way Handshake

A SYN packet is essentially the client telling the server “I’d like to connect”. During this handshake, both client and server generate random Initial Sequence Numbers (ISNs), which are used to synchronise the TCP connection between the two parties. These sequence numbers let TCP keep track of which messages have been sent and acknowledged by the other party.

A SYN flood abuses this handshake by only going part way through the handshake. Rather than progressing through the normal sequence, an attacker floods the target server with as many SYN packets as they can muster, from as many different hosts as they can, and spoofing the origin IP as much as they can.

SYN Flood

The host receiving the SYN flood must respond to each and every packet with a SYN-ACK, but unfortunately the source IP was likely spoofed, so they go nowhere (or worse, come back as rejected). These packets are almost indistinguishable from real SYN packets from real clients, which means it’s hard or impossible to filter out the bad ones on the server. Even external DDoS scrubbing services can only guess whether a packet is legitimate or part of a flood, making it difficult to mitigate an attack without impacting legitimate traffic.

To make matters worse, when the server is handling normal connections and receives the ACK from a real client, it still needs to know that it came from a SYN packet it sent, so it must also keep a list of connections (in state SYN_RECV) for which a SYN has been received and an ACK has not yet been received.

During a SYN flood, this behaviour is undesirable. If the queue of connections in SYN_RECV has no size limit, memory will get exhausted pretty quickly. If it does have a size limit, as is the case in Linux, then there’s no more space to store state and the connections will simply fail as the packets are dropped.

SYN cookies

SYN cookies are a clever way of avoiding the storage of TCP connection state during the initial handshake, deferring that storage until a valid ACK has been received. It works by crafting the Initial Sequence Number (ISN) in the SYN-ACK packet sent by the server in such a way that it cryptographically hashes details about the initial SYN packet and its TCP options, so that when the ACK is received (with a sequence number 1 larger than the ISN), the server can validate that it generated the SYN-ACK packet for which an ACK is now being received. The server stores no state for the connection until the ACK (containing the validated SYN cookie) is received, and only at that point is state regenerated and stored.

Since this hash is calculated with a secret that only the server knows, it doesn’t significantly weaken the sequence number selection and it’s still difficult for someone to forge an ACK (or other packet) for a different connection without having seen the SYN-ACK from the real server.

SYN cookies have been around for a while, and they have fairly minimal impact on the reliability and spoof-protection of TCP. Rather than enabling them constantly, the Linux kernel by default automatically enables SYN cookies only when the SYN receive queue is full. This means that under normal circumstances when no SYN flood is occurring, you get no impact at all, but during a SYN flood, you accept the minimal impact of SYN cookies (in return for not dropping connections). The extra CPU cost of creating SYN cookies is offset by the fact that you no longer have a limited resource, and in practise this is an excellent trade-off.

In Linux 3.x, SYN cookies are generated inside a machine-wide lock on the LISTEN socket that the packet was destined for. This implementation causes all SYN cookies to be generated serially across all cores, defeating the benefits of a multi-processor system. To make matters worse, all cores spin waiting for the lock to become available. This was fine back in the days when an average attacker could only send a few MBits of SYN packets your way, mostly thanks to the networks being much slower. These days however, with servers attached to transit providers with multiple 10GB+ links the whole way down the line, it’s now possible to completely saturate CPU resources.

While Linux 4.x has a patch to send SYN cookies under a per-CPU-core socket lock, which does fix the problem, we wanted a solution that allowed us to use an existing, maintained kernel with upstream security patches. We didn’t want to roll and maintain an entire custom kernel and all related future security patches just to mitigate this form of attack. Patching Linux 3.x to backport the socket lock change was also a similar maintenance burden we wanted to avoid.

SYNPROXY

One solution to get the best of both worlds was the SYNPROXY iptables module. It sits in netfilter in the kernel, before the Linux TCP stack, and as the name suggests, proxies all connections while generating SYN cookies. When a SYN packet comes in, it responds with a SYN-ACK and throws away all state. On receipt of a valid ACK packet matching the SYN cookie, it then sends a SYN downstream and completes the usual TCP handshake. For every subsequent packet in each direction, it modifies the sequence numbers so that it is transparent to both sides.

SYNPROXY packet flow

This is quite an intrusive way of solving the problem since it touches every packet during the entire connection, but it does successfully mitigate SYN floods. Unfortunately we found that in practise under our load and with the amount of malformed packets we receive, it quickly broke down and caused a kernel panic. Additionally, it had to be enabled all the time, since there was no simple way to activate it only when under attack. This meant that we would have to accept the minimal impact of SYN cookies constantly, and at our scale this still would likely cause issues for some of our users.

We decided that it was more complicated than it needed to be for our use case, and we wanted a simpler solution that would only touch the packets that needed to be touched to mitigate a SYN flood. We also decided that a mitigation should only cause potential (even if minimal) impact during mitigation, and not under normal operation.

synsanity

Enter synsanity, our solution to mitigate SYN floods on Linux 3.x. synsanity is inspired by SYNPROXY, in that it is an iptables module that sits inside iptables between the Linux TCP stack and the network card. The major difference is that rather than touch all packets, synsanity simply generates a SYN cookie identically to the way the Linux kernel would generate one if the SYN queue was full, and once it validates the ACK packet, it allows it through to the standard Linux SYN cookie code, which creates and completes the connection. After this point, synsanity doesn’t touch any further packet in the TCP connection.

synsanity packet flow

Similar to the way that Linux only enables SYN cookies when the SYN queue overflows, we only enable synsanity when the SYN queue overflows as well. We match the core Linux code exactly, except that we do it in an iptables module, outside the LISTEN lock. Since an iptables module can be compiled and maintained outside the Linux kernel source tree itself, we don’t need to use a custom Linux kernel, and can instead just maintain and deploy a single module to our servers.

synsanity has allowed us to mitigate multiple attacks that would have previously caused a partial or complete service outage, both long running attacks and large volume attacks.

synsanity syncookie graph synsanity sending SYN cookies during a 300kpps SYN flood

Open Source

We believe that if you need to hide your mitigation to keep it secure, it’s not designed well enough. The best and most secure tools are shared, open and subject to community scrutiny, so today we’re open sourcing synsanity so that everyone can benefit from this work.

theojulienne

Infrastructure Engineering Manager

GitHub's CSP journey gh-ost: GitHub's online schema migration tool for MySQL