Cardinality is Not Enough: Super Host Detection via Segmented Cardinality Estimation

Dit paper introduceert SegSketch, een lichtgewicht methode voor gesegmenteerde kardinaliteitsschatting die door het schatten van IP-voorvoegsels de detectie van superhosts met een hoge nauwkeurigheid en een lage valse-positievenratio mogelijk maakt binnen beperkt geheugen.

De kern

Stel je voor dat je de beheerder bent van een gigantisch drukke luchthaven (het internet). Je taak is om te voorkomen dat er chaos ontstaat door "super-passagiers": mensen die plotseling duizenden andere mensen proberen te ontmoeten of duizenden mensen naar zich toe laten komen. In de digitale wereld noemen we deze super-hosts. Vaak zijn dit aanvallers die malware verspreiden of een server lamleggen (een DDoS-aanval).

Het probleem is dat de luchthavenbeveiliging (de bestaande software) vaak in de war raakt. Ze tellen simpelweg hoeveel verschillende mensen een passagier heeft ontmoet. Maar hier zit een addertje onder het gras:

Het Probleem: De "Wijk" vs. De "Wereld"

Stel je twee scenario's voor:

1. De Verdachte: Een hacker zit in één wijk (een subnet) en probeert elk huis in die wijk te bezoeken. Hij heeft 1000 contacten, maar ze zitten allemaal in dezelfde straat.
2. De Onschuldige: Een populaire webserver (zoals Google) heeft ook 1000 contacten, maar deze mensen komen uit heel Nederland, België en Frankrijk. Ze zitten allemaal in verschillende wijken.

De oude beveiligingssystemen zagen alleen het getal "1000". Voor hen waren beide personen even verdacht. Ze schreeuwden alarm bij de webserver (een vals alarm) en misten de hacker die in één wijk aan het werk was.

Om dit op te lossen, probeerden andere systemen om voor elke mogelijke wijkgrootte (van heel klein tot heel groot) apart te tellen. Dit werkt wel, maar het is alsof je voor elke mogelijke wijk een eigen bewakingskamer bouwt. Je hebt dan zoveel kamers nodig dat de luchthaven (het computergeheugen) vol zit en de beveiliging stopt met werken.

De Oplossing: SegSketch (De Slimme Wijk-Scanner)

De auteurs van dit paper hebben een nieuwe uitvinding bedacht: SegSketch. Ze noemen het "Cardinality is Not Enough" (Aantal is niet genoeg), omdat je ook moet weten waar die contacten zitten.

Hier is hoe het werkt, met een simpele analogie:

1. De Slimme Gids (Halved-Segment Hashing)
In plaats van te proberen elke wijk apart te bewaken, gebruikt SegSketch een slimme gids. Deze gids kijkt naar de IP-adressen (de huisnummers) en doet alsof hij een zoektocht doet in een boek.

• Hij kijkt eerst naar het eerste deel van het adres. Is het voor alle 1000 contacten hetzelfde? Dan weten we: "Ah, ze zitten allemaal in dezelfde grote regio."
• Kijkt hij naar het tweede deel? Is dat ook hetzelfde? Dan weten we: "Ze zitten in dezelfde stad."
• Zodra het verschil begint, stopt hij.

Dit is als het halveren van een zoekruimte. In plaats van elke straat te controleren, snijdt hij de wereld steeds in tweeën totdat hij precies weet hoe groot de "wijk" is waar de verdachte zich bevindt. Dit kost heel weinig ruimte in het geheugen.

2. De Wijk-Teller (Subnet Cardinality)
Zodra de gids weet hoe groot de wijk is (bijvoorbeeld: "Ze zitten allemaal in de 192.168.10.x wijk"), telt hij alleen de unieke huizen in die specifieke wijk.

• Voor de hacker: Hij telt 1000 unieke huizen in één wijk. Gevaar!
• Voor de webserver: Omdat de contacten over de hele wereld verspreid zijn, telt hij misschien maar 50 unieke huizen in die ene specifieke wijk die hij net heeft geïdentificeerd. Veilig.

Waarom is dit zo goed?

• Klein en Krachtig: Het systeem is zo efficiënt dat het zelfs op een heel kleine computerchip (zoals die in een netwerkswitch) past. De tests tonen aan dat het slechts 1,77% van het geheugen van de chip gebruikt, terwijl andere systemen veel meer nodig hebben.
• Snelheid: Het kan miljoenen pakketten per seconde verwerken zonder te haperen.
• Minder Valse Alarmen: Door te kijken naar de "wijk" in plaats van alleen het totaal aantal, onderscheidt het systeem veel beter tussen een echte aanval en een normale, drukke server.

Het Resultaat

In de proefnemingen bleek dat SegSketch tot 8 keer beter presteerde dan de beste bestaande systemen. Het kon de echte aanvallers veel sneller en nauwkeuriger vinden, terwijl het de onschuldige, drukke servers met rust liet.

Kort samengevat:
Vroeger keken we alleen naar hoeveel mensen iemand ontmoette. SegSketch kijkt ook naar wie die mensen zijn en of ze in dezelfde buurt wonen. Hierdoor kunnen we de echte boeven sneller pakken zonder de onschuldige burgers lastig te vallen, en dat allemaal met een systeem dat zo klein is dat het in je broekzak past.

Technische samenvatting

Titel: Cardinality is Not Enough: Super Host Detection via Segmented Cardinality Estimation

Auteurs: Yilin Zhao et al. (Centrale Zuid-Universiteit, China; Universiteit van Edinburgh, VK)
Publicatie: WWW '26 (Dubai, 2026)

---

1. Het Probleem

Het nauwkeurig detecteren van "super hosts" (super spreaders en super receivers) is cruciaal voor het mitigeren van webaanvallen zoals IP-scanning, spam-distributie en DDoS-aanvallen. Een super host is een systeem dat verbindingen maakt met of ontvangt van een groot aantal unieke peers.

Bestaande oplossingen, gebaseerd op sketches (zoals HyperLogLog of Linear Counting), schatten het aantal unieke verbindingen (flow cardinality) op basis van volledige IP-adressen. Dit leidt echter tot twee belangrijke beperkingen:

1. Hoge vals-positief ratio: Veel legitieme servers (zoals DNS-resolvers) hebben ook een hoge flow cardinality omdat ze verbindingen hebben met veel verschillende netwerken. Bestaande methoden kunnen deze niet onderscheiden van kwaadaardige super hosts.
2. Onderschatting van subnet-georiënteerde aanvallen: Kwaadaardige aanvallen vinden vaak plaats binnen één enkel subnet (bijv. een botnet binnen hetzelfde /24-netwerk). Bestaande methoden zien dit als één grote set unieke IP's, terwijl ze eigenlijk een geconcentreerde aanval binnen één subnet vertegenwoordigen.

Alternatieve methoden die hiërarchische structuren gebruiken om subnets te detecteren, zijn te geheugenintensief voor real-time implementatie op netwerkapparatuur met beperkt on-chip geheugen.

2. Methodologie: SegSketch

De auteurs stellen SegSketch voor, een nieuwe, geheugenefficiënte sketch die de schatting van cardinaliteit combineert met het identificeren van gemeenschappelijke IP-voorvoegsels (subnets).

Kerncomponenten:

• Data Structuur: SegSketch bestaat uit rijen met "buckets". Elke bucket bevat:

  1. Een host key.
  2. Een subnet bitmap: Om de lengte van het gemeenschappelijke IP-voorvoegsel te infereren.
  3. Een host bitmap: Om de cardinaliteit binnen dat specifieke subnet te schatten.

• Halved-Segment Hashing Strategie (De Innovatie):
  In plaats van een zware hiërarchische structuur te gebruiken, gebruikt SegSketch een lichtgewicht strategie om de subnetlengte te bepalen:

  • Het IP-adres wordt opgedeeld in segmenten (bijv. 8 bits per segment).
  • Voor elk segment wordt een hash-functie toegepast die het resultaat reduceert tot 0 of 1.
  • Op basis van dit hash-resultaat wordt de subnet bitmap "halvering" (links of rechts) geselecteerd.
  • Als alle pakketten van een host hetzelfde hash-resultaat hebben voor een segment, wordt alleen die helft van de bitmap gebruikt. Als de resultaten verschillen, worden beide helften gebruikt.
  • Dit proces is recursief en stopt zodra er variatie wordt gevonden. Hierdoor kan de lengte van het gemeenschappelijke prefix (subnet) worden afgeleid zonder alle mogelijke prefixlengtes expliciet op te slaan.

• Cardinaliteitsschatting:
  Zodra de subnetlengte is bepaald, wordt het resterende deel van het IP-adres (het hostgedeelte) gehasht naar de host bitmap. De cardinaliteit binnen dit subnet wordt geschat met behulp van Linear Counting (formule: $b \cdot \ln(b/z)$, waarbij $b$ de bitmapgrootte is en $z$ het aantal ongebruikte bits).

• Detectie:
  Een host wordt gemarkeerd als "super host" als de geschatte cardinaliteit binnen het afgeleide subnet een dynamische drempelwaarde overschrijdt. Deze drempel past zich aan op basis van de grootte van het subnet.

3. Belangrijkste Bijdragen

1. SegSketch Ontwerp: Een nieuwe sketch die een goede balans vindt tussen geheugenoverhead en detectienauwkeurigheid door gebruik te maken van halved-segment hashing en subnet-cardinaliteit.
2. Wiskundige Analyse: De auteurs hebben een theoretisch model opgesteld om de foutgrenzen te analyseren. Ze bewijzen dat het hashen van alleen het host-adres (binnen het subnet) een kleinere schattingsfout oplevert dan het hashen van het volledige IP-adres.
3. Implementatie en Evaluatie:
   • Implementatie in C++ voor trace-driven evaluatie.
   • Implementatie in P4 op een programmeerbare switch (Barefoot Tofino), wat aantoont dat het geschikt is voor hardware-implementatie met zeer lage SRAM-gebruik (slechts 1,77%).

4. Resultaten

De prestaties van SegSketch zijn getest op real-world datasets (UNSW-NB15, MAWI, CAIDA) en vergeleken met state-of-the-art methoden zoals SpreadSketch, Couper en RHHH.

• Nauwkeurigheid:

  • SegSketch verbetert de F1-Score met tot 8,04x in vergelijking met de beste bestaande oplossingen, vooral onder kleine geheugenbudgetten (bijv. 32 KB).
  • De Average Relative Error (ARE) is aanzienlijk lager (tot 87% reductie).
  • De methode reduceert vals-positieven drastisch door onderscheid te maken tussen hosts met veel verbindingen over het hele netwerk (legitiem) en hosts met veel verbindingen binnen één subnet (aanval).

• Geheugen en Snelheid:

  • SegSketch behoudt een hoge doorvoer (28 Mpps) zelfs bij minimale geheugengrootte.
  • Op de P4-switch gebruikt het aanzienlijk minder resources dan concurrenten:
    • SRAM: 1,77% (vs. 12,60% voor Couper).
    • Hash Units: 11,11% (vs. 33,33% voor RHHH).
    • Gateways en VLIW instructies: Ook hier de laagste gebruikswaarden.

5. Betekenis en Impact

Dit werk is significant omdat het een fundamenteel probleem in netwerkmetingen aanpakt: de onmogelijkheid van bestaande sketches om "super hosts" te onderscheiden van "legitieme hoge-verkeer hosts" op basis van subnetpatronen.

• Praktische Toepassing: Door de lage geheugeneisen en hoge snelheid, is SegSketch direct inzetbaar op moderne programmeerbare switches (P4) voor real-time detectie van geavanceerde cyberaanvallen.
• Paradigmaverschuiving: Het artikel benadrukt dat "cardinality alleen niet genoeg is" en dat contextuele informatie (het subnet) essentieel is voor accurate anomaliedetectie.
• Efficiëntie: Het biedt een oplossing voor het dilemma tussen hoge detectienauwkeurigheid en beperkt on-chip geheugen, wat vaak een bottleneck is in high-speed netwerken.

Kortom, SegSketch biedt een robuuste, schaalbare en nauwkeurige methode om super hosts te detecteren door slim gebruik te maken van IP-prefix-inferentie binnen een compacte datastructuur.