Information Based Heavy Hitters for Real-Time DNS Data Exfiltration Detection

Information Based Heavy Hitters for Real-Time DNS Data Exfiltration Detection

Speakers: Yarin Ozery

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=xh08ixKVYLU

Overview

Data exfiltration over the Domain Name System (DNS) protocol remains a persistent and significant cybersecurity threat. Malicious actors, ranging from state-sponsored groups to ransomware operators, frequently exploit DNS due to its ubiquitous nature, its often-unblocked status, and inadequate monitoring. They encode stolen data within DNS query names, types, or even manipulate query timings to establish covert communication channels. While extensive research has explored DNS exfiltration detection, a critical gap persists: the predominant focus has been on offline detection methods. These methods inherently allow a substantial amount of sensitive data to be exfiltrated before an attack is even identified, let alone mitigated, leading to severe consequences for organizations.

This talk introduces Information-based Heavy Hitters (ibHH), a novel method designed to bridge this gap by enabling truly real-time DNS exfiltration detection. The primary motivation behind ibHH is to provide a solution that is lightweight, highly efficient, and capable of direct deployment on high-throughput recursive DNS servers. Such direct integration is paramount to eliminate delays and disruptions in the resolution process, thereby facilitating rapid response to ongoing attacks.

For a solution to be considered real-time and suitable for DNS resolvers, it must meet stringent computational criteria: specifically, sublinear space complexity, denoted as o(n), and constant-time query classification, or Θ(1). These requirements ensure that the detection mechanism does not impede the high-throughput demands of modern DNS infrastructure, which can process millions of queries per second on limited hardware. ibHH is presented as a unique solution that satisfies these demanding real-time criteria, offering a practical and effective defense against a pervasive threat.

Background

▶ Watch: DNS exfiltration problem and real-time detection motivation (0:00)

To understand the necessity and innovation of ibHH, it's crucial to first establish the DNS stream model and review existing detection methodologies. In the context of DNS, a data stream S is an ordered set of elements, where each element xi represents a DNS query parsed into a pair (ki, vi). Here, ki is the domain (e.g., example.com), and vi is the subdomain (e.g., a.b for a.b.example.com). The real-time constraints of sublinear space complexity o(n) and constant-time classification Θ(1) are non-negotiable for deployment on resource-limited DNS resolvers.

Prior work in DNS exfiltration detection can be broadly categorized:

• Offline Detection Methods: Many studies, such as Paxson et al.'s information-based approach [13], group DNS queries daily and use lossless compression to estimate information. While effective, their time and space complexity are Ω(w) (linear with window size w), making them unsuitable for real-time deployment. Nadler et al. [18] utilized an isolation forest model over sliding windows, requiring Ω(λns) memory and significant aggregation time. Ishikura et al. [14] proposed cache-property-aware features, but their memory requirements grow linearly with the number of clients. These methods, by their nature, allow for significant data exfiltration before detection.
• Compute-Intensive Methods (Deep Learning): Recent deep learning models, including those by Chen et al. [21] (CNN+LSTM) and Wu et al. [22] (TDAE autoencoder), offer high accuracy and automatic feature extraction. However, their demand for large training datasets and intensive hardware [31, 32] renders them impractical for deployment on network perimeters or DNS resolvers.
• Supervised Learning Methods: Several approaches [17, 33, 34, 35] rely on labeled data. While useful for detecting known exfiltration tools, they struggle to generalize to unfamiliar malware due to the scarcity of high-quality, publicly available datasets. The "unknown unknown" problem is a significant hurdle here.
• Limited Real-Time Methods: Only a few studies have genuinely focused on real-time detection. Qi et al. [15] proposed a bigram frequency statistics approach, but it relies on a score mechanism trained on labeled data. Ahmed et al. [19] used an unsupervised isolation forest on a per-packet basis, extracting many features. While lightweight, its scalability to millions of queries per second is questionable given the feature extraction overhead.

As highlighted in the paper's Table I, ibHH distinguishes itself by meeting all real-time criteria: it requires no labeled training data, performs no data aggregation, and achieves constant-time classification, making it uniquely suitable for real-time deployment on DNS infrastructure.

Key Findings

▶ Watch: Introducing Information-based Heavy Hitters (ibHH) methodology (4:00)

The comprehensive evaluation presented in the talk unequivocally demonstrates ibHH's superior performance in both detection efficacy and resource utilization when compared against state-of-the-art methods.

Detection Efficacy:

• Low Exfiltration Rate Detection: ibHH successfully detected exfiltration rates as slow as 0.7 B/s, maintaining an impressively low false positive rate (FPR) of less than 0.004% on the test set. At an acceptable FPR of 0.01%, ibHH detected all three synthetic attack types used in the evaluation: Iodine, FrameworkPOS, and Backdoor.Win32.Denis.
• ZIZA Dataset Performance: On the public ZIZA dataset, at an acceptable FPR of 1%, ibHH achieved a detection threshold of 0.6 B/s and detected all three exfiltration domains with only 62 false positive domains. This was significantly better than other methods, including Isolation Forest (IF) (140 FPs), Real-Time Isolation Forest (RT-IF) (119 FPs), and Paxson (87 FPs). At a stricter 0.01% FPR, ibHH produced only one false positive while still detecting all exfiltration domains, whereas IF detected only one, Paxson detected two, and RT-IF detected none.
• Real-world DSr Dataset: When trained at a 0.001% FPR, ibHH generated a total of 17 alerts (2 true positives, 15 false positives), which was the lowest number of false positives among all compared methods. Its detectable exfiltration rate (DER) was 6 B/s. The two true positive domains, cymulatedlp.com (simulated attack with short subdomains and a 2-second query interval) and q2t.nl (using base64 encoded data with subdomain lengths between 30-144 and a 0.01-second query interval), were successfully detected by ibHH.

Resource Utilization:

• Exceptional Efficiency: ibHH demonstrated exceptional efficiency on the ZIZA dataset. It achieved an average runtime of 58 seconds, an average memory usage of just 1.6 MB, and was capable of processing over 603,000 queries per second.
• Comparison to RT-IF: In stark contrast, RT-IF, a leading real-time machine learning solution, had an average runtime of 857 seconds and processed only 40,840 queries per second, albeit with similar memory usage. This highlights ibHH's significant speed advantage, being over 14 times faster.
• Offline Methods Unsuitable: Offline methods like Paxson and IF exhibited considerably larger memory footprints and longer runtimes, reaffirming their unsuitability for real-time deployment.

Key Contributions:

The research makes three primary contributions:

1. ibHH: The introduction of a lightweight, simple, and highly effective real-time DNS exfiltration detection method suitable for both large-scale, high-throughput networks and resource-constrained environments.
2. Extensive Evaluation: The most comprehensive and rigorous evaluation to date, performed on massive real-world and publicly available datasets, validating ibHH's performance.
3. Open-source Implementation: Providing a Python implementation to facilitate reproducibility and further research in the field.

Technical Deep Dive

▶ Watch: Defining Information Weight and Distinct Information Heavy Hitter (4:18)

The core technical approach of this research introduces Information-based Heavy Hitters (ibHH), a novel methodology for real-time DNS exfiltration detection. The fundamental idea is to identify domains that are associated with a large amount of distinct information conveyed through their subdomains within a continuous DNS query stream. This concept draws inspiration from Afek et al.'s work [39] on distinct heavy hitters for DDoS attack detection, but it is uniquely adapted to quantify information.

To formalize this, two new definitions are introduced:

• Definition 2: Information Weight. Given a stream of elements S, the information weight of an element (ki, vi), denoted I_ki,vi, is the quantity of information conveyed by vi.
• Definition 3: Distinct Information Heavy Hitter. For a given key ki in a stream S, the distinct information weight I_ki is the total information conveyed by all distinct elements associated with ki. A key ki is considered a distinct information heavy hitter if its information weight I_ki is at least an ε-fraction of the total distinct information weight of the entire stream.

To quantify the information, ibHH defines the information weight of a subdomain simply as its length: I(subdomain) = length(subdomain). While this is an approximation, experiments show it provides an effective upper bound on the conveyed information and is highly practical. The speakers explored using entropy [36] for information estimation but found the results to be inferior.

A significant challenge in quantifying unique information for each domain is the necessity to store all associated subdomains, which would lead to prohibitive linear space complexity—unacceptable for memory-constrained DNS resolvers. To overcome this, ibHH employs count-distinct approximation algorithms from the field of big data, specifically a modified version of the HyperLogLog++ (HLL++) algorithm [42]. The crucial modification to HLL++ is that instead of simply adding the subdomain to the HLL++ instance, for each integer i in the range (0, length(subdomain)), the concatenated string subdomain_i is added. This allows HLL++ to approximate the amount of distinct information, rather than just the count of distinct elements. This modified insertion is denoted as Add, and the information estimation as InformationEst.

System Design and Architecture

The ibHH system processes a continuous stream of DNS queries, as illustrated conceptually by Figure 2 and Algorithm 1 in the original paper. It comprises several key components:

• Input: DNS queries are parsed into (domain, subdomain) pairs (e.g., subdomain.example.com becomes (example.com, subdomain)).
• Fixed-size Cache (Counters): A hash map storing k entries (a configurable parameter). Each entry holds a domain, its associated HLL++ instance, and a seed_domain value.
• Random Hash Function (Hash): A uniform hash function Hash: U → [0,1] used to sample distinct DNS query stream elements.
• detection_threshold: A predefined, configurable value that, if exceeded by a domain's information estimate, triggers an alert.
• T (Threshold Value): Initially set to 1, this value represents the probability of a domain's inclusion in the cache and dynamically updates to manage cache capacity.

Here's the step-by-step process for how ibHH processes a DNS query:

1. Extraction: The domain and subdomain are extracted from the query name.
2. Hashing: A hash value h = Hash(domain, subdomain) is calculated.
3. Cache Check and Management:

• If the domain is already in Counters: The existing entry is updated. The modified Add operation inserts subdomain_i into the domain's HLL++ instance. The seed_domain is updated to be the minimum of its current value and h.
• **If the domain is not in Counters AND h < T:** This condition ensures that only domains with a sufficiently low hash value (indicating a higher likelihood of being an information heavy hitter) are considered for caching. A new entry is allocated, its HLL++ instance is initialized, subdomain_i is added, and seed_domain is set to h.
• Cache Eviction: If, after adding a new domain, the Counters size exceeds its capacity k, ibHH evicts the domain with the largest seed_domain value (i.e., the least likely to be an information heavy hitter). The global threshold T is then updated to this evicted domain's seed_domain value, making it harder for new domains to be added. This mechanism, based on Gibbons and Matias [43], efficiently ensures the cache prioritizes domains with high information volume.

1. Information Estimation and Alerting: Finally, ibHH uses the InformationEst operation on the domain's HLL++ instance to estimate the total unique information conveyed. If this estimated value exceeds the detection_threshold, an alert is raised for the domain, and the query can be blocked. Otherwise, the DNS resolver continues as usual.

Implementation Details and Complexity Analysis

An open-source Python implementation of ibHH has been provided for reproducibility. The complexity analysis is critical for real-time deployment:

• Space Complexity: ibHH achieves sublinear, specifically logarithmic, space complexity. The cache stores k HLL++ instances. Each HLL++ instance, using the (ε, δ) model [42], requires O(ε²loglog(m_dom) + log(m_dom)) space, where m_dom is the number of distinct elements associated with that domain. The total space complexity for ibHH is O(k ε²loglog(m) + log(m)), where m is the maximum number of distinct elements across all domains. Since m is O(n) (where n is the stream length), this is logarithmic in the entire data stream size.
• Time Complexity (per query): ibHH achieves constant-time query classification, Θ(1).
• Calculating the hash value h is O(1).
• The Add operation for the HLL++ algorithm is O(1). Given that DNS domain names are limited to 255 characters, subdomains are also bounded, ensuring constant time for this operation.
• The InformationEst (count) operation is also O(1) because the number of register bits p is fixed at 12.
• Therefore, processing and classifying a query has a constant time complexity, crucial for high-throughput environments.

To prevent missing information heavy hitters that appear later in the stream, a reset mechanism is incorporated, periodically flushing and resetting the ibHH cache at constant intervals. This addresses the decreasing confidence intervals of counters over time, ensuring long-term effectiveness.

Furthermore, to mitigate false positives, several allowlisting approaches are employed:

• Peacetime/Wartime Model: Inspired by [39], ibHH runs in a non-enforcing "peacetime" mode for a limited period. Any domains detected during this phase are assumed benign and added to a peacetime allowlist. Then, ibHH transitions to "wartime" enforcing mode, filtering out these allowlisted domains. This approach is model-agnostic and highly effective.
• TRANCO Allowlist [48]: Utilization of top-ranking domain lists, such as the top 1 million from TRANCO, to filter out popular, legitimate websites that might otherwise trigger alerts due to their extensive use of subdomains.
• Locally Reputable Domains: These are domains frequently queried by a large portion of hosts within the local enterprise network, deemed trustworthy. These allowlists are applied as post-filters in the evaluation to assess their impact on false positive rates.

Demo / Proof of Concept

▶ Watch: Crucial modification to HLL++ for distinct information approximation (5:18)

While a live demonstration was not explicitly described in the transcript, the research conducted an extensive and rigorous evaluation that serves as a robust proof of concept for ibHH's capabilities. This involved:

1. Synthetic Attack Generation: Malicious DNS exfiltration traffic was synthetically generated using three well-known tools:

• Iodine [50]: Simulating high-throughput DNS exfiltration.
• FrameworkPOS [7]: Simulating credit card data exfiltration at a rate of three queries per second.
• Backdoor.Win32.Denis [6]: Simulating Command and Control (C&C) keep-alive instructions at 1.5-second intervals.

1. Dataset Injection: These synthetically generated attacks were injected into 1% of client hosts within multiple large-scale, real-world, and public datasets. The datasets included:

• DSf (First Dataset): Over 50 billion DNS queries from 753 real-world enterprise organizations over eight days.
• DSp (Identifiable Subset): A 5.06 billion query subset of DSf, enabling host-level detection evaluation.
• ZIZA [49] (Public Dataset): Over 35 million DNS queries from an ISP's DNS server over 26 hours, containing synthetic exfiltration queries.
• DSr (Real-world Dataset): The largest dataset, comprising over 255 billion DNS queries from 753 organizations over 21 days.

1. Performance Evaluation: Detection abilities were rigorously evaluated using metrics such as Hosts' True Positive Rate (TPR), Hosts' False Positive Rate (FPR), Total Detections, and Detectable Exfiltration Rate (DER) at various acceptable FPR values (0.01%, 0.001%, 0.0001%, 0.00001%).

The results, as detailed in the "Key Findings" section, demonstrated ibHH's effectiveness in detecting these simulated real-world exfiltration attempts across diverse network environments and traffic patterns. The provision of an open-source Python implementation further allows researchers and practitioners to reproduce these findings and experiment with ibHH themselves, serving as a practical proof of concept.

Defensive Implications

▶ Watch: Overview of ibHH system design and architecture (6:00)

The development and validation of ibHH offer several critical implications for cybersecurity defenders aiming to bolster their defenses against DNS-based data exfiltration:

1. Prioritize Real-Time DNS Monitoring: The pervasive nature of DNS exfiltration and the limitations of offline detection necessitate a shift towards real-time monitoring. Defenders should ensure their DNS infrastructure is adequately monitored, moving beyond the misconception that DNS traffic is inherently benign and can be left unblocked or unexamined.
2. Deploy ibHH on DNS Resolvers/Gateways: Given ibHH's lightweight nature, sublinear space complexity, and constant-time query classification, it is ideally suited for direct deployment on recursive DNS servers or enterprise DNS gateways. This eliminates delays associated with data aggregation or forwarding to external analysis systems, enabling immediate detection and response. The evaluation confirmed that ibHH does not require data consolidation and performs equally well in global versus local deployments.
3. Implement Robust Allowlisting Strategies: To minimize false positives, which can lead to alert fatigue and operational overhead, defenders should actively implement and maintain allowlists. The Peacetime/Wartime model described provides a powerful, model-agnostic method to build a baseline of legitimate domains. Integrating with established lists like TRANCO [48] and identifying locally reputable domains are also crucial steps. Periodic review and updates to these allowlists are essential.
4. Be Aware of Encrypted DNS (DoT/DoH): While ibHH focuses on traditional DNS, the rise of DNS over TLS (DoT) and DNS over HTTPS (DoH) can circumvent traditional DNS monitoring and detection methods. Defenders should follow recommendations, such as those from the NSA [62], to block encrypted DNS traffic that is not resolved by their internal, controlled DNS resolver. This ensures that all DNS traffic remains visible and subject to inspection.
5. Understand Exfiltration Rate Limitations: ibHH can detect exfiltration rates as low as 0.7 B/s. While this is highly effective, defenders should be aware that a sophisticated attacker might attempt to exfiltrate data at extremely slow rates below the detection threshold. However, such slow exfiltration significantly prolongs the attack duration, increasing the chance of other detection mechanisms triggering.
6. Consider Other Attack Vectors: ibHH primarily focuses on information encoded in query names (subdomains). While this is the most common and efficient vector for DNS exfiltration, attackers could theoretically exploit other vectors like query types or timing. Defenders should be aware of these possibilities, though they generally offer lower information capacity and accuracy for attackers.
7. Utilize Periodic Cache Resets: The ibHH algorithm incorporates a periodic cache reset mechanism. Defenders implementing ibHH should ensure this feature is enabled and configured appropriately to maintain the algorithm's effectiveness over long-running deployments, preventing stale counters from reducing detection confidence.

By adopting these defensive measures, organizations can significantly enhance their ability to detect and mitigate DNS-based data exfiltration in real-time, reducing the window of compromise and protecting sensitive information.

Key Takeaways

• Real-time, Efficient Detection: ibHH provides a truly real-time DNS data exfiltration detection method with sublinear space complexity (logarithmic) and constant-time query classification (Θ(1)), making it suitable for high-throughput DNS resolvers.
• Novel Information Quantification: The method quantifies "distinct information" conveyed through subdomains by using a modified HyperLogLog++ (HLL++) algorithm, approximating the amount of distinct information based on subdomain lengths.
• Superior Performance: Extensive evaluation on massive real-world and public datasets demonstrates ibHH's superior performance over state-of-the-art methods, detecting exfiltration rates as slow as 0.7 B/s with exceptionally low false positive rates (e.g., 1 false positive at 0.01% FPR on ZIZA dataset).
• Resource Optimized: ibHH is highly resource-efficient, processing over 603,000 queries per second with an average memory usage of just 1.6 MB, significantly outperforming other real-time machine learning solutions.
• Practical Deployment with Allowlists: Effective deployment requires integrating robust allowlisting strategies (e.g., Peacetime/Wartime model, TRANCO, locally reputable domains) to maintain low false positive rates, alongside periodic cache resets to ensure long-term efficacy.
• Address Encrypted DNS: While ibHH is effective for traditional DNS, organizations must also address the threat of encrypted DNS (DoT/DoH) by controlling or blocking external encrypted DNS resolvers to maintain visibility and detection capabilities.

About the Speaker(s)

Yarin Ozery is the speaker who presented "Information Based Heavy Hitters for Real-Time DNS Data Exfiltration Detection" at the NDSS Symposium. Based on the provided transcript, specific details about his title or company are not available.