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

This paper proposes SegSketch, a memory-efficient segmented cardinality estimation approach using halved-segment hashing to infer IP common prefixes and improve super host detection accuracy by reducing false positives caused by subnet-level communication patterns.

The Gist

🕵️‍♂️ The Problem: The "Busy Bee" vs. The "Swarm"

Imagine you are a security guard at a massive concert venue (the Internet). Your job is to spot the troublemakers.

In the world of cyberattacks, a "Super Host" is like a troublemaker who connects to thousands of different people.

• The Bad Guy (Super Spreader): A botnet (a zombie army of hacked devices) that tries to scan every single house in a specific neighborhood to find weak locks.
• The Good Guy (Benign Host): A popular pizza delivery app that connects to millions of customers all over the country.

The Old Way (The Flawed Detective):
Previous security tools used a simple trick: "If a person connects to more than 1,000 different people, they are a suspect."

• The Mistake: This catches the Pizza App (who is innocent but busy) and lets the Bad Guy slip by if they only hit 900 people in one neighborhood.
• The Real Issue: The Bad Guy usually attacks one specific neighborhood (subnet). They might talk to 500 houses on "Maple Street," but the Pizza App talks to 500 houses scattered across the whole city. The old tools couldn't tell the difference between "500 neighbors" and "500 strangers."

🧱 The Old Solution: The "Tower of Babel" (Hierarchical Approach)

Some smart people tried to fix this by building a Tower of Babel. They created a giant filing cabinet with a drawer for every possible neighborhood size:

• Drawer A: Neighborhoods with 8 houses.
• Drawer B: Neighborhoods with 16 houses.
• Drawer C: Neighborhoods with 256 houses.
• ...and so on.

The Problem: This tower is huge. It takes up so much memory (space) that it doesn't fit in the tiny, fast chips inside routers. It's like trying to carry a library in your backpack.

💡 The New Solution: SegSketch (The "Smart Neighborhood Watch")

The authors propose SegSketch, a new, lightweight detective that fits in a backpack but is just as smart as the giant tower.

1. The Magic Trick: "Halved-Segment Hashing"

Instead of checking every single house number, SegSketch plays a game of "Guess the Neighborhood."

Imagine you have a long address: 192.168.101.200.

• Step 1: SegSketch looks at the first part (192). It asks: "Do all the people this host talks to share this part?"
  • Yes? Great! They are in the same big city. We zoom in.
  • No? Stop. They are scattered. This isn't a neighborhood attack.
• Step 2: It checks the next part (168). Same question.
• Step 3: It keeps zooming in until it finds the exact point where the addresses start to differ.

The Analogy: Think of it like a binary search in a phone book. Instead of reading every name, you open the book in the middle. If the name you want is before the middle, you ignore the second half. You keep cutting the book in half until you find the exact page. SegSketch does this with IP addresses to figure out exactly how much of the address is the "Neighborhood" and how much is the "House."

2. The "Two-Map" System

Once SegSketch knows the "Neighborhood" (the common prefix), it uses two special maps:

• Map A (The Neighborhood Map): Tracks which neighborhoods are being visited.
• Map B (The House Map): Counts how many different houses are in that specific neighborhood.

Why this is a game-changer:

• The Pizza App: Connects to 1,000 houses, but they are in 1,000 different neighborhoods. Map B shows 1 house per neighborhood. Verdict: Innocent.
• The Bad Guy: Connects to 500 houses, all in the same neighborhood. Map B shows 500 houses in one spot. Verdict: Suspect!

🚀 Why It's Better (The Results)

The paper tested this new system against the old "Tower of Babel" and other methods using real-world data.

1. Super Accuracy: It found the bad guys 8 times better than the best existing tools (in terms of F1-Score). It stopped catching innocent pizza apps.
2. Tiny Footprint: It uses 98% less memory than the hierarchical tower. It fits easily into the tiny, fast chips inside network switches.
3. Super Fast: It can process millions of packets per second without slowing down the internet.

🎯 The Bottom Line

SegSketch is like upgrading from a giant, clumsy telescope to a laser-guided sniper scope.

• Old Way: "I see a lot of movement! Everyone is a suspect!" (High false alarms).
• SegSketch: "I see a lot of movement, but they are all in the same small alley. That's suspicious. The guy moving around the whole city? He's fine."

By realizing that where you connect matters just as much as how many you connect to, SegSketch solves the problem of finding cyber-attackers without needing a supercomputer to do it.

Technical Summary

1. Problem Statement

Super hosts (super spreaders and super receivers) are hosts that establish connections with a vast number of distinct peers. They are often indicators of web attacks such as IP scanning, spam distribution, and DDoS attacks.

• Limitation of Existing Methods: Current state-of-the-art approaches rely on flow cardinality estimation (counting distinct full IP addresses) using sketch-based data structures (e.g., HyperLogLog, SpreadSketch).
• The Core Issue: These methods suffer from high false positive rates. Benign hosts (e.g., web servers, DNS resolvers) often connect to many diverse IPs across the entire internet, mimicking the behavior of malicious super hosts.
• The Missing Insight: Empirical studies reveal that malicious super hosts typically communicate with many victims within the same subnet (sharing a common IP prefix), whereas benign hosts connect across diverse subnets.
• The Trade-off: Existing solutions that attempt to capture subnet information use hierarchical structures (tracking multiple prefix lengths like /8, /16, /24 simultaneously). While accurate, these structures incur prohibitive memory overhead, making them impractical for high-speed network devices with limited on-chip memory (SRAM).

2. Methodology: SegSketch

The authors propose SegSketch, a memory-efficient sketch that integrates cardinality estimation with a novel halved-segment hashing strategy to infer subnet prefixes and estimate subnet cardinality (distinct hosts within a specific subnet) rather than full IP cardinality.

Key Components:

1. Data Structure:

   • Consists of $r$ rows and $c$ buckets.
   • Each bucket contains:
     • Host Key: To identify the source/destination host.
     • Subnet Bitmap: Used to infer the common IP prefix length.
     • Host Bitmap: Used to estimate the cardinality of distinct hosts within that inferred subnet.

2. Halved-Segment Hashing Strategy (Prefix Inference):

   • Instead of storing full prefixes, the algorithm divides the 32-bit IP address into segments (e.g., 8-bit chunks).
   • It recursively hashes these segments. If the hash results for a specific segment are consistent across all packets for a host, it implies the segment is part of a common prefix.
   • The algorithm uses a binary search approach on the subnet bitmap:
     • If a segment hash is consistent, it narrows the search to one half of the bitmap.
     • If inconsistent, it marks both halves, indicating the prefix ends before this segment.
   • This allows the system to dynamically infer the common prefix length (e.g., /16, /24) with minimal memory, avoiding the need for a multi-layer hierarchy.

3. Subnet Cardinality Estimation:

   • Once the common prefix length is inferred, the remaining bits of the IP address are treated as the host address.
   • These host addresses are hashed into the Host Bitmap.
   • The system uses Linear Counting to estimate the number of distinct hosts within that specific subnet.
   • Detection Logic: A host is flagged as a super host if its estimated subnet cardinality exceeds a threshold $T(p)$, which scales based on the inferred prefix length $p$ (i.e., larger subnets have higher thresholds).

4. Replacement Policy:

   • When memory is full, SegSketch uses a probability-based replacement strategy. Hosts with lower estimated subnet cardinality are more likely to be evicted, ensuring that persistent super hosts remain in the sketch.

3. Key Contributions

• Novel Algorithm (SegSketch): A lightweight sketch that simultaneously infers IP prefix lengths and estimates subnet cardinality, solving the false positive problem without hierarchical memory overhead.
• Theoretical Analysis: The authors provide a mathematical model proving that estimating cardinality based on host addresses (within a subnet) yields a smaller expected estimation error compared to hashing full IP addresses.
• Implementation & Deployment:
  • Implemented in C++ for trace-driven evaluation.
  • Deployed on a Barefoot Tofino programmable switch using P4, demonstrating feasibility in real hardware.
• Resource Efficiency: Achieves high accuracy with significantly lower memory usage compared to hierarchical approaches.

4. Experimental Results

The authors evaluated SegSketch against state-of-the-art baselines: SpreadSketch, Couper, and RHHH (Randomized Hierarchical Heavy Hitter).

• Datasets: Real-world traces including UNSW-NB15 (attacks), MAWI2021, and CAIDA2016 (benign traffic).
• Accuracy (F1-Score):
  • Under a tight memory budget of 32KB, SegSketch improved the F1-Score by up to 8.04× compared to RHHH, 2.73× compared to SpreadSketch, and 2.18× compared to Couper.
  • It significantly reduced the Average Relative Error (ARE) by up to 87.20%.
• Memory Efficiency:
  • On the P4 switch, SegSketch utilized only 1.77% of SRAM, compared to 12.60% for Couper and 3.65% for RHHH.
  • It also consumed fewer VLIW instructions and Stateful ALUs, making it highly suitable for high-speed data planes.
• Throughput:
  • SegSketch achieved a throughput of 28 Mpps (Million packets per second) even with minimal memory, outperforming all baselines due to its lightweight hashing operations.
• Robustness: The method maintained high detection accuracy even when the ratio of super spreaders to benign hosts increased (e.g., 1:20 ratio).

5. Significance

This paper addresses a critical gap in network security monitoring: the inability to distinguish between malicious "super spreaders" and benign high-volume servers using limited memory.

• Paradigm Shift: It moves the detection metric from "total distinct IPs" to "distinct IPs within a common subnet," which is a more accurate indicator of coordinated attacks (e.g., botnets scanning a specific subnet).
• Practicality: By eliminating the need for complex hierarchical structures, SegSketch makes accurate super-host detection feasible on resource-constrained network hardware (switches/routers) where traditional hierarchical methods fail.
• Impact: The ability to detect these attacks with high precision and low false positives in real-time helps mitigate DDoS attacks, IP scanning, and worm propagation, thereby ensuring higher quality of web services and reduced operational costs.