V předchozím článku této série jsme si z vysokoúrovňového pohledu nastínili, jak Knot Resolver 6 a Knot DNS 3.4 chrání samy sebe i ostatní účastníky na internetu proti útokům typu denial-of-service. Pojďme se nyní zblízka podívat na implementaci takovéto ochrany a popsat si, jak vypadá její skutečné technické řešení.
V tomto článku si představíme speciálně navrženou datovou strukturu, jíž používáme k hlídání chování potenciálních útočníků.
Tato práce je součástí projektu DNS4EU kofinancovaného Evropskou unií1. Veškerý zde popsaný kód je svobodný a otevřený pod licencí GPL.
KRU: správce čítačů
Začněme tím, že si zkorigujeme tu největší nepřesnost, které jsme se záměrně dopustili v předchozím článku. Je vcelku zřejmé, že není možné efektivně udržovat přesné počty dotazů či procesorových časů pro každou jednotlivou IP adresu v adresním prostoru IPv4, natož pak v IPv6. To však ve skutečnosti ani není potřeba. Jelikož stejně pracujeme s několika úrovněmi přesnosti – měříme více délek prefixů najednou, abychom byli schopni ochrany před útoky ze sítí různých velikostí – celkem si vystačíme s pouhým odhadem. Vyměníme tak úroveň přesnosti za vysoký výkon a udržitelné využití paměti.
KRU2 je specializovaná datová struktura, díky které jsme schopni data čítačů vměstnat do paměti skutečného fyzického počítače. Je kombinací několika známých technik, které jsme adaptovali a optimalizovali pro specifické požadavky ochrany před DoS útoky v Knot Resolveru.
Svrchní pohled na strukturu
Pojďme si nyní popsat návrh KRU iterativně tak, že si budeme v každém kroku přidávat informace navrch k těm, které již máme.
Space-saving algoritmus
Základem KRU je velmi jednoduchý “space-saving”, neboli “místo-šetřící” algoritmus3, který vykazuje překvapivě dobré vlastnosti na skutečných vstupech4. Algoritmus udržuje pevně daný počet párů klíčů a čítačů, kde klíč je zdrojová IP adresa, ze které přišel dotaz, příp. její prefix.
Jednou ze zajímavých situací je vkládání, když je tabulka plná. V tu chvíli najdeme nejnižší čítač ve struktuře a přepíšeme jeho klíč, ale hodnotu čítače ponecháme a běžným způsobem ji inkrementujeme (prozatím předpokládejme shodný okamžitý limit u všech čítačů).
Ponechání hodnoty čítače namísto jejího zahození a například vynulování je důležité – zlepšuje se tak totiž chování v okrajovém případě, kdy se dva či více klíčů vzájemně “vyhazují” ze struktury. Tímto “trikem” v podstatě zajistíme, že klíče tento čítač sdílí, místo aby vyhozené čítače opakovaně degradovaly na nulovou hodnotu.
Hešování
Použití space-saving algoritmu nad velkým počtem klíčů by nebylo příliš efektivní. Co tedy namísto toho vytvořit pole indexované heši, jehož jednotlivé položky budou skupiny párů, nad kterými budeme provádět space-saving algoritmus?
Můžeme tak nejdříve se složitostí O(1) provést vyhledání položky v poli pomocí heše vypočteného z klíče, a poté najít ten správný pár klíče a čítače v mnohem menší skupině.
Vyrovnávání zaplněnosti skupin
Hešování takovýmto způsobem má jednu nevýhodu – výsledná (pseudo-)náhodná distribuce položek sice vede ke slušnému využití většiny jednotlivých skupin, ale malé procento z nich má tendenci být značně přetíženo. Abychom se tomuto přetížení vyhnuli, používáme paradigma hešování se dvěma volbami, které vytížení vyrovnává se vcelku malými přidanými nároky.
Každý klíč nás tak navede na dvě skupiny, z nichž každá je v oddělené tabulce. Pak hledáme páry klíčů a čítačů v obou skupinách najednou. Pokud se při vkládání klíč v jedné z nich nachází, danou položku použijeme a zvýšíme její čítač. Pokud ne, vybereme nejnižší čítač z množiny všech čítačů obou skupin, odstraníme předchozí klíč a nahradíme jej vkládaným klíčem. Dá se tak říci, že vždy vybíráme “tu méně zaplněnou” skupinu z těch dvou nalezených.
Je důležité na tomto místě podotknout, že každý klíč nám spáruje skupiny jinak, jelikož k indexaci tabulek používáme různé heše (o tom více později). Mezi žádnou dvojicí skupin z různých tabulek tak není přímý vztah. To je to, co nám zajišťuje silný vyrovnávací efekt.
Šetření pamětí, šetření časem
Vytvořili jsme celkem slušný funkční základ naší datové struktury, ale ještě toho máme spoustu na práci. Abychom udrželi na uzdě paměťové nároky a co nejvíce zvýšili výkon, provedeme ještě několik optimalizací.
“Líný” pokles
V předchozím článku jsme si popsali, že na čítače aplikujeme tzv. exponenciální pokles.
Kdybychom tak pravidelně činili pro celou strukturu, velmi bychom si zavařili, co se týče výpočetních nákladů, zejména kvůli rozsáhlým přístupům do paměti.
Jinou možností by bylo u každého čítače poznamenávat časovou značku posledního přístupu, a pak jen při každém dalším přístupu pokles aplikovat (a aktualizovat značku), přičemž pokles škálujeme na základě rozdílu mezi časem aktuálním a poznamenanou značkou. Nicméně to by zabralo velké množství paměti.
Kompromis, který jsme zvolili, vypadá tak, že si poznamenáváme časovou značku sdílenou pro každou skupinu čítačů. Pokaždé, když ke skupině přistoupíme, nejprve aplikujeme pokles na všechny čítače podle časového rozdílu, aktualizujeme časovou značku a poté provedeme zbytek v danou chvíli požadovaných operací nad čítači.
Toto se pro každou skupinu děje maximálně jednou za milisekundu, což je granularita, kterou jsme si zvolili pro náš konkrétní případ užití.
Žádné klíče, samé heše
Ukládání celých klíčů, tj. IP adres, by bylo vcelku drahé na paměť vzhledem k tomu, že každá IPv6 adresa má velikost 16 bajtů. My je ale ukládat nepotřebujeme. Místo toho si ukládáme jen 16bitové heše – a prostě necháme jednotlivé položky mezi sebou kolidovat. Může se zdát, že 16 bitů není mnoho, ale uvědomme si, že kolize značně redukuje již rozdělení space-saving algoritmu na menší celky, a tudíž každá skupina už tak “vidí” pouze malý zlomek všech klíčů.
Mohlo by vás zajímat, jak vlastně počítáme všechny ty heše, které potřebujeme. Pro každý klíč si ve skutečnosti spočítáme pouze jeden 64bitový heš, a pak jej po bitech “rozsekáme” na tři části. Jeden 16bitový kousek je použitý jako klíč space-saving algoritmu a další dva kousky se použijí jako indexy do výše popsaných dvou hešovacích tabulek. Počet bitů těchto dvou částí závisí na kapacitě tabulky, která je uživatelsky konfigurovatelným parametrem.
Přesnost čítačů
Pro ještě větší úsporu paměti jsou čítače pouze 16bitové, čímž navíc dostáváme příležitost ke zrychlení pomocí vektorizace (o té více později).
Abychom minimalizovali negativní vliv takto malých čítačů na přesnost celého mechanismu, používáme malý trik. Všechny výpočty jsou totiž prováděny v 32bitové aritmetice, přičemž naše operandy jsou v podstatě reálná binární čísla s pevnou čárkou. Ta se nachází přesně uprostřed čísla, se 16 bity na každé straně. Po provedení výpočtu, než výsledek uložíme do paměti, provádíme pravděpodobnostní zaokrouhlení. To probíhá tak, že desetinnou část čísla (tedy 16 nejméně významných bitů) použijeme jako pravděpodobnost, že celkovou hodnotu zaokrouhlíme nahoru. Tímto způsobem, i když čítač zvětšujeme o hodnoty menší než “jedna”, se jeho celková hodnota bude “nasčítávat” velmi přesně. Jelikož nás pro účely omezování provozu zajímá pouze to, jestli nasčítané hodnoty dosáhly limitu, a nikoliv mezivýsledky, můžeme tímto způsobem uspořit paměť s jen malými dopady na celkovou přesnost.
Pro omezování četnosti dotazů navíc škálujeme hodnotu “nacenění” DNS operací v závislosti na nakonfigurovaném okamžitém limitu LI. Jeden dotaz ve skutečnosti nezvyšuje čítač o jednotkový krok. Namísto toho jsou přírůstky a s nimi související limity škálovány poměrem 216/LI, aby rozsah čítače odpovídal rozsahu povolených hodnot dle zkonfigurovaných limitů. Díky tomu efektivněji využijeme těchto pouhých 16 bitů a i hodnoty čítačů s různými limity budou vzájemně porovnatelné. V závislosti na nastaveném limitu tak můžeme měřítko hodnot zvětšit či zmenšit. Při větším měřítku získáváme vyšší přesnost čítačů, zatímco díky menšímu měřítku jsme schopni používat vyšší limit na úkor přesnosti (přičemž ale stále využíváme dříve zmiňované pravděpodobnostní zaokrouhlování, kterým si určitou část této ztráty vynahradíme).
Mimochodem, v předchozím článku jsme zmínili, že čítače nikdy nepřekračují ostrý okamžitý limit. Toto je důvod, proč tomu tak je. Jelikož jsou limity a přírůstky čítačů naškálovány na celých 16 bitů čítačů, jsou limity těsně nad maximálními hodnotami, které jsou čítače technicky schopny reprezentovat.
Práce s CPU keší
Pro zvýšení efektivity práce s pamětí, obzvlášť při souběžném přístupu mnoha procesorovými jádry, je dobré omezit počet řádků procesorové keše, ke kterým přistupujeme při zpracovávání jednotlivých částí dat. Z toho důvodu jsme rozhodli, že skupiny čítačů se přesně mapují na řádky keše x86 procesorů o velikosti 64 bajtů.
Když to dáme všechno dohromady, potřebujeme pouze 16+16 bitů na pár heš-čítač a jednu (32bitovou) časovou značku na skupinu. Do každé skupiny (resp. řádku keše) se nám tak vejde po 15 položkách.
Shrnující obrázek
Nízkoúrovňové optimalizace
Paralelismus
Strukturu KRU je potřeba sdílet mezi několika vlákny (v případě Knot DNS) či procesy (v případě Knot Resolveru). To je důležité například kvůli randomizaci zdrojového portu, která typicky vede k tomu, že dotazy přes UDP od jediného klienta obsluhují různá vlákna/procesy na stejném stroji. Naproti tomu spojení (TCP, TLS, DoH) se váže pouze na jedno vlákno/proces.
Přístupy ke KRU jsou bezzámkové. Zvolený způsob hešování již sám o sobě snižuje pravděpodobnost kolize při paralelním přístupu, a navíc používáme atomické instrukce, abychom co nejvíce zamezili nepřesnostem, které mohou vzniknout kvůli souběhům.
Optimalizace přístupů k řádkům keše
Při zpracování dotazu musíme pracovat s daty ze dvou KRU skupin pro každý z prefixů jeho zdrojové adresy. Abychom přístupy k těmto datům urychlili, využíváme schopnost procesorů typu x86_64 pro načtení specifických řádků keše dříve, než s daty skutečně začneme pracovat.
Poté vyhodnocujeme exponenciální pokles nad načtenými skupinami a kontrolujeme, zda má kterýkoliv z vyhodnocovaných čítačů překročit limit. Pokud ano, žádný z čítačů nezvyšujeme; pokud ne, zvýšíme je všechny.
Tímto způsobem pro dotazy, které omezíme, často potřebujeme pouze čtení (mimo zmiňovaný pokles probíhající jednou za milisekundu), což práci s pamětí dále urychluje. Kromě toho, že tím jednoduše snižujeme počet potřebných operací, zároveň dochází ke zrychlení také díky tomu, že čtecí operace nevyžadují vyhození řádků z dedikovaných keší ostatních jader5, čímž si opět ušetříme nějaké cykly při intenzivních útocích.
SIMD instrukce
Většina procesorů typu x86_64 posledních let podporuje v rámci rozšířených instrukčních sad SSE*, AVX2 a AES tzv. SIMD6 instrukce. Ty v podstatě dokážou provést stejnou operaci nad několika hodnotami najednou. Pokud jsou tyto instrukce k dispozici, používáme v kódu jejich intrinsiky7 pro další zvýšení výkonu.
Většina těchto ručních optimalizací se nachází v kódu, kterým prohledáváme pole 16bitových čísel pomocí SSE* a AVX2. Toto je ta vektorizace, kterou jsme zmiňovali výše. Dále využíváme AES akceleraci k urychlení hešování s “dostatečně dobrými” vlastnostmi (nedostatečné pro kryptografii, ale zcela v pořádku pro účely přístupů k hešovací tabulce).
Závěr
Zde zakončujeme druhou část Ochrany proti DoS útokům v Knot Resolveru 6.
Představili jsme si naši novou datovou strukturu KRU, kterou používáme k uchovávání čítačů ke zdrojovým IP adresám. Popsali jsme si strukturu z vysokoúrovňového pohledu, počínaje space-saving algoritmem, který je jejím základem. Poté jsme se přesunuli k hešování a load-balancingu rozdělením dat do dvou nezávisle hešovaných tabulek.
Abychom ušetřili paměť a využití procesoru, bylo potřeba již na počátku návrhu zapracovat fakta o moderních procesorech. Popsali jsme si, jak aplikujeme exponenciální pokles “líně”, abychom každou milisekundu nemuseli přistupovat k celé tabulce; jak všechny klíče vždy vyhledáváme rychle pouze pomocí jejich heše, aniž bychom je přesně porovnávali; jak snižujeme přesnost čítačů z důvodu šetření pamětí (ale její část si zachováváme díky pravděpodobnostnímu zaokrouhlování); a jak se strukturou pracujeme s přihlédnutím k procesorovým keším, abychom ušetřili čas při načítání dat z paměti.
V poslední sekci jsme si popsali některé pokročilé optimalizace, jako je bezzámkový paralelismus; optimalizace přístupu k řádkům keše; a použití SIMD instrukcí.
- Project number: 101095329 21-EU-DIG-EU-DNS
Project name: DNS4EU and European DNS Shield.
This project is co-funded by the European Union.↩︎ -
Zkratka (k)not recently used.↩︎
-
Metwally, D. Agrawal, and A. E. Abbadi. Efficient computation of frequent and top-k elements in data streams. In International Conference on Database Theory, 2005.↩︎
-
Cormode, G., & Hadjieleftheriou, M. (2010). Methods for finding frequent items in data streams. The VLDB Journal—The International Journal on Very Large Data Bases, 19(1), 3–20.↩︎
-
Vizte protokol MESI a jemu podobné.↩︎
-
Single instruction, multiple data; neboli jedna instrukce, vícero dat.↩︎
-
Konstrukty v překladačích jazyka C, které vypadají jako funkce, ale při generování strojového kódu jsou nahrazeny přímo instrukcemi procesoru, které představují.↩︎
Autoři: Vladimír Čunát, Lukáš Ondráček, Oto Šťáva