DNS Dampening unter der Lupe
Die ersten Erfolge machten andere Serverbetreiber neugierig. Der Patch (bind-9.9.2-dampening.patch) mußte benutzbar veröffentlicht werden. Dies gestattet nun eine realere Auswertung der Algorithmen und der Defaults.
Queue oder Heap
Die wesentliche Frage für mich ist die Entscheidung mit einem Heap oder einer Queue/Hash Struktur weiterzumachen. Mein Kollege Jens vertrat vehement die Ansicht, der Worst Case für den Suchalgorithmus des Heaps würde zu oft getroffen und man müsse alle Operationen praktisch in konstanter Zeit ausführen können. Deswegen sollte der Heap gegen einen Hash ausgetauscht werden, und die Alterung der Strafpunkte durch eine Warteschlange, also eine Queue, modelliert werden.
Die Grundannahme eines nach Strafpunkten sortierten Heaps ist, dass die Übeltäter immer "vorn" stehen. Damit kann die Suche als Breitensuche durch den Heap, also linear über das zugrunde liegende Feld ausgeführt werden. Im schlimmsten Fall, z.B. wenn neue Einträge hinten angefügt wurden, müssen alle Werte durchsucht werden. Andererseits kann das letzte Element des Heaps als "niederwertigst" angesehen und durch neue Einträge überschrieben werden. Beim Update werden neben dem aktuellen Element auch das erste, das letzte und ein zufälliges Element gealtert, um einen regelmäßigen Alterungsdurchlauf mit Änderungen an der Heapstruktur zu vermeiden.
Das Queue/Heap-Modell dagegen organisiert den Zugriff auf die Elemente durch einen Hash. Für die Behandlung von verschiedenen Einträgen mit gleichem Hash-Wert wird eine einfach verkettete Liste gepflegt. Parallel dazu werden alle Werte in einer doppelt verketteten Liste als Queue strukturiert. Jedes nachgefragte Element wird aus der Queue entfernt und nach Aktualisierung der Strafpunkte am Ende wieder eingefügt. Am Anfang der Queue steht also immer das am längsten nicht mehr aktualisierte Element. Ist die Tabelle voll, wird dieses Element wahrscheinlich so stark gealtert sein, daß es für ein neues Element Platz machen kann. Diese Strukturierung gestattet es, auf einen regelmäßigen Alterungsdurchlauf zu verzichten.
Es gibt zwei Ansätze für die Verkettung gleicher Hashs: Man kann die Werte innerhalb dieser Liste nach Adressen sortiert halten, wodurch die Suche nach noch nicht erfaßten Adressen durchschnittlich schon nach der Hälfte der Listenlänge abgebrochen werden kann. Oder man kann die Liste ständig so umsortieren, so dass das zuletzt gesuchte Element immer vorn steht.
Beide Varianten wurden implementiert und parallel mit identischen Daten auf einem realen DNS Server mehrere Tage unter realistischen Bedingungen gemessen. Das Ergebnis war eindeutig. Die nach Adressen sortierte Liste ist immer signifikant langsamer als die Sortierung nach letztem Zugriff. Deswegen ist die jetzige Implementierung der vom Heap referenzierten Listen nach dem letzten Zugriff sortiert.
Bei der Implementierung des Heaps fiel auf, dass die gewählte Hashfunktion nicht stabil war: Gleiche Adressen wurden mehrfach und unterschiedlich eingetragen. Auch die naive Sortierung mittels memcmp der Strukturen isc_netaddr_t war nicht stabil. Zwei gleiche Adressen konnten auch größer oder kleiner sein. Dies liegt daran, daß die Struktur isc_netaddr_t mehr als die Adresswerte enthält und nicht zwingend alle unbenutzen Felder auch genullt sein müssen. Es war also notwendig eigene Hash und Vergleichsfunktionen zu schreiben. Die akutelle Hash-Funktion ist an Adler16 angelehnt.
Praktische Messungen
Wie schlagen sich nun beide Algorithmen in der Praxis?
Wieder werden alle DNS Pakete beiden Algorithmen vorgeworfen und über diese Werte Statistiken aufgesammelt. Ich erwartete für beide Verfahren die gleichen extern sichtbaren Ergebnisse und wurde überrascht:
Der Heap lässt weniger Anfragen zur Verarbeitung zu als die Queue. Dem entsprechend werden mehr Queries vom Heap ins Dampening geschickt als von der Queue:
Die Graphen wurden auf 50 Anfragen pro Sekunde begrenzt, die Peakwerte liegen bei einigen tausend um drei und einigen hunderttausend gegen 17 Uhr. Eine wirklich nachprüfbare Erklärung für den Effekt habe ich nicht. Allerdings drängt sich der begründete Verdacht auf, daß der Heap intervallartig agierende Angreifer länger aufbewahrt als die Queue, die schlicht den ältesten Eintrag verwirft.
Bleibt die Frage nach dem Zeitverhalten der Implementationen. Beide Algorithmen wurden nicht mit besonderem Augenmerk auf Performance geschrieben, insbesondere sind viele Korrektheitsprüfungen mit assert im Code verstreut. Trotzdem sind die Ergebnisse instruktiv. Bei der Messung werden die (Mikro-)Sekunden jeder Aktion pro Minute aufsummiert.
Zuerst natürlich die Frage, ob der Heap denn im praktischen Mix wirklich langsamer ist als ein Hash.
Die Frage ist eindeutig zu bejahen: Nur, wenn ein massiver Angriff läuft, ist der Heap schneller als der Hash.
Beim Update macht der Heap drei zusätzliche Alterungen, sowie den Ausgleich der Heapstrukturen für jede dieser Änderungen. Die Queue dagegen verändert nur die Verlinkungen, so daß das Element ans Ende kommt.
Erwartungsgemäß ist der Heap in dieser Disziplin deutlich unterlegen.
Das Hinzufügen neuer Einträge, die bisher nicht bekannt waren, ist dagegen schon spannender. Der Heap operiert nur auf dem letzten Element, während die Queue sowohl die Linklisten des Hashes als auch eine Freispeicherverwaltung vornehmen muß.
Beide Verfahren nehmen nicht nicht viel. Bei irrelevant niedrigem Zeitbedarf ist die Queue knapp schneller.
Allerdings ist der Bind multithreaded, so daß beide Strukturen zur korrekten Arbeit die Nebenläufigkeit mit Locks eingegrenzt werden müssen.
Auf niedrigem Niveau behindern die Algorithmen eine effiziente Verarbeitung der Anfragen durch den DNS Server. Da der Heap vor der Queue ausgeführt wird, nimmt er eine Serialisierung der Threads vor, von der die Queue dann profitiert. Interessant wäre hier also eher der Test einer Datenstruktur, die Multitheading unterstützt.
Fazit: Der Heap selektiert besser, die Queue ist schneller. Auf einem FreeBSD stürzt der Heap mit Segfault ab, was ich leider nicht nachstellen konnte. Die Queue funktioniert dort problemlos.
Anatomie von Angriffen
Ein weiterer Aspekt der Untersuchungen war die Natur der DNS Amplification oder Reflection Angriffe zu verstehen, um das Verfahren des Dampening mit dem des Response Rate Limiting vergleichen zu können.
Ein typischer Angriff auf eine IP liefert folgendes Bild. Unterschiedliche Punktformen und -farben bedeuten unterschiedliche angefragte Domains.
Es ist deutlich zu sehen, wie der Angriff binnen weniger Sekunden hohe Strafpunkte aufsammelt und ins Dampening gerät. Wenn die Strafpunkte dann nach und nach verfallen, so endet das Dampening und die Strafpunkte werden ab diesem Wert wieder aufsummiert. Dies ist besonders deutlich ab 19 Uhr zu sehen, wo die Angriffe alle 20 Minuten wieder kurz durchgelassen werden. Da der Standardwert für die Halbwertszeit bei 10 Minuten liegt, ist also nach 20 Minuten der Punktestand um 75% abgebaut, was genau dem Graphen entspricht.
Die großen Lücken zwischen den roten Punkten kommen von Pakten mit identischer ID, die quadratischen Punktzuwachs bescheren. Was aber geschieht um 17:35?
Der erste "hohe" Wert bei 17:35:30 ist der Restwert vor dem Update. Aus Effizienzgründen wird beim Heap auf die Alterung des Punktestandes bei der Suche verzichtet, denn dies hätte einen Umbau des Heaps zur Folge. Deswegen ist der Punktestand für die Bewertung der Anfrage immer veraltet. Der korrigierte Wert steht erst bei der nächsten Anfrage zur Verfügung.
Die sonst übliche schnelle Aufsammlung von Strafpunkten durch Wiederholung der immer gleichen ID wird zu diesem Zeitpunkt nur anfangs wirksam. Dann mischen die Angreifer die verschiedenen Domains wild durcheinander. Damit ist die ID Wiederholung ebenfalls vermischt und diese Bewertung läuft ins Leere.
Schaut man sich die Anfragen genauer an, so sind sie alle anhand der Standardwerte des Ratelimiting Patches ausgerichtet. Keine Anfrage für die gleiche Domain wird mehr als 10 mal pro Sekunde gestellt. Dafür werden viele Domains durcheinander abgefragt.
Diese Beobachtung ist nicht auf diese IP beschränkt, sondern tritt ebenso bei anderen Angriffszielen auf:
Fazit: Die Angreifer haben sich auf den Response Rate Limit Patch eingestellt und bevorzugen DNS Server, die viele (signierte) Zonen haben. Dort unterlaufen sie die Abwehrtechniken des RRL Patches durch Streuung der Domains. Dampening ist für Beteiber von DNS Servern mit vielen Zonen besser geeignet. Bei DNS Servern mit wenig Zonen, wie sie bei TLDs üblich sind, ist der RRL Patch völlig ausreichend.
Wenn Rauch aufsteigt
Viele DNS Betreiber überwachen die Funktion Ihres Systems. Viele benutzen einen externen SmokePing. Normalerweise nimmt man seine Monitoringsystem in die exempt-client ACL auf. Normalerweise.
Hier der SmokePing eines externen Systems, das nicht ganz so eingestellt war.
Die neue Version des Bind mit Dampening-Patch wurde um 20 Uhr eingespielt. Es sind mehrere Dinge auffällig: Zum einen treten immer wieder Ausfälle auf und zum anderen ist die Gesamtperformance des Systems besser geworden. Die Ausfälle liegen am Dampening. Die bessere Performance aller Wahrscheinlichkeit nach am aktuelleren Bind.
Aber warum geht ein System mit fünf Anfragen alle fünf Minuten ins Dampening?
Der Plot zeigt, daß die fünf Anfragen einen riesigen Berg an Strafpunkten aufsammeln, der dann immer wieder nach der gleichen Halbwertszeit (in logarithmischer Skalierung sind das parallele Linien) in den fünf Minuten nur teilweise abgebaut wird. Die Korrektur der verzögerten Ausgabe ist bei der Berechnung schon berücksichtigt.
Ein genauerer Blick auf den Punktezuwachs innerhalb der fünf Anfragen zeigt:
Die Strafpunkte wachsen linear pro Anfrage. Der Zuwachs des Zuwachses ist 100. Dies ist genau der Wert, der für mehrfach vorkommende IDs aufgeschlagen wird.
Eine akribische Suche nach der Ursache ergab, nach einer anfänglichen Verwechslung von Quell-Port und ID, daß SmokePing immer die gleiche ID verwendet. Dies ist im tcpdump/wireshark deutlich zu sehen.
Das verwendete Modul von SmokePing ist AnotherDNS. Dort findet sich der folgende Code für die Probe:
my $packet = Net::DNS::Packet->new( $lookuphost, $recordtype )->data;
my $sock = IO::Socket::INET->new(
"PeerAddr" => $host,
"PeerPort" => $port,
"Proto" => "udp",
);
[...]
for ( my $run = 0 ; $run < $self->pings($target) ; $run++ ) {
[...]
$sock->send($packet);Es wird also ein Paket fertig gemacht und dann über einen festen UDP Socket mehrfach versendet. Deswegen hat dieses Paket die gleiche ID und den gleichen Quellport.
In Net::DNS wird aber ein neues Paket mit einer zufälligen ID generiert. Läßt man diesen Code manuell in einer Schleife laufen, so generiert er pro Durchlauf zwar fünf identische Pakete, die sich aber pro Durchlauf anhand der ID unterscheiden.
Der Grund für dieses Verhalten kommt daher, daß SmokePing jede Probe abforkt und mit einem srand Aufruf den Zufallszahlengenerator neu initalisiert. Die AnotherDNS Probe ihrereseits forkt selbst für jeden Messung. Damit erben alle Messungen den identischen internen State des Generators und erzeugen identische IDs.
In aktuellen Versionen von SmokePing ist dieses Problem behoben.
1 Kommentare