A Classifier with Unknown Pattern Recognition for Domain Name System Tunneling Detection in Dynamic Networks

Huijuan Dong, Zengwei Zheng, Shenfei PeiElectronics 2026 · DOI

TL;DR

This paper introduces MNForest, a novel unsupervised classifier designed to detect DNS tunneling, a stealthy cyberattack. MNForest excels at identifying both known and previously unseen malicious DNS query patterns by employing a "medium neighbor" mechanism and clustering, offering a significant advancement in network security.

What Problem Does This Paper Address?

The internet's Domain Name System (DNS), crucial for translating domain names into IP addresses, is increasingly exploited for malicious purposes, particularly DNS tunneling. This technique allows attackers to embed covert data within seemingly normal DNS queries and responses, creating stealthy communication channels for data exfiltration, bypassing security measures, and impersonation. Detecting these tunneling activities is challenging due to several factors:

  • Traffic Diversity: Legitimate DNS traffic varies greatly (e.g., video streaming vs. instant messaging), and malicious tunneling traffic exhibits diverse patterns and encryption methods, making it hard to define a single "bad" signature.
  • Emerging Threats: Attackers constantly develop new tunneling methods, meaning detection systems must identify patterns not seen during training (unknown patterns).
  • Class Imbalance: Legitimate DNS queries vastly outnumber malicious ones, creating a significant imbalance in datasets.
  • Feature Engineering Complexity: Raw DNS query data requires complex feature engineering before it can be used by machine learning models.

Traditional binary classification methods struggle with these challenges, especially the need to identify novel, unknown attack patterns. This paper frames the problem as "Emerging Pattern Classification" (EPC) and proposes a solution to address these limitations.

Methods

The core of this paper is the Medium Neighbors Forest (MNForest), an unsupervised forest-based classifier designed to handle multi-pattern classes and identify unknown patterns. Here's how it works:

  • Unsupervised Tree Construction (MNTree): MNForest builds multiple random trees. Each tree is constructed using a k-sums-x clustering algorithm to split data into two clusters at each node. This process continues recursively until nodes reach a minimum size, becoming leaf nodes. This unsupervised approach allows the model to discover patterns without pre-labeled data.
  • "Medium Neighbor" Mechanism: For a test sample, MNForest identifies its "medium neighbor" within a leaf node (the training sample closest to the test sample). It then defines "medium neighbors" as training samples within a certain distance from this medium neighbor.
  • Unknown Pattern Probability: The probability of a test sample being an "Unknown Pattern" (UP) sample is calculated based on the ratio of medium neighbors with different labels to the total number of samples in the leaf node. This mechanism leverages density and local neighborhood information to detect deviations from known patterns.
  • Known Pattern Classification: If a sample is classified as a "Known Pattern" (KP), its class probability is determined by the proportion of training samples belonging to that class within its leaf node.
  • Ensemble Prediction: The final prediction for a test sample is an aggregation (average) of the probabilities calculated across all trees in the forest, providing a robust classification.

Datasets

The paper evaluates MNForest on both public datasets and real-world DNS traffic:

  • Public Datasets:
    • USPS: Handwritten digit recognition dataset.
  • Digits: Another handwritten digit recognition dataset.
  • JAFFE: Face emotion dataset.
  • Pix10P: Face recognition dataset. These datasets were used to simulate SENC (Streaming Emerging New Classes) and EPC scenarios by strategically dividing known and unknown classes, including balanced and imbalanced distributions.

  • Real-world DNS Traffic:

    • Enterprise Network: Traffic from a medium-sized enterprise.
  • Campus Network: Traffic from a university campus.
  • Public Wi-Fi Network: Traffic from a public Wi-Fi hotspot.
  • Data Center Network: Traffic from a cloud data center. These datasets were collected over 30 days and preprocessed to extract relevant features, including statistical measures of query lengths, domain names, and DNS TTLs.

Key Insights and Ideas

  • Formalizing DNS Tunneling as EPC: The paper successfully frames the DNS tunneling detection problem as "Emerging Pattern Classification," which is crucial for handling evolving threats and unknown patterns.
  • The "Medium Neighbor" as a Novel Anomaly Detector: The core innovation is the "medium neighbor" mechanism. Instead of relying on fixed distance thresholds (common in other OSR methods), it uses local density and neighborhood characteristics to infer the probability of a sample being an unknown pattern. This makes it more adaptive to complex and varied data distributions.
  • Unsupervised Learning for Pattern Discovery: By using k-sums-x clustering for tree construction, MNForest can discover underlying patterns in the data without requiring pre-labeled unknown classes, making it suitable for real-world scenarios where new threats constantly emerge.
  • Forest-based Ensemble for Robustness: The ensemble of multiple MN-Trees enhances the model's robustness and accuracy, effectively capturing the multi-pattern nature of DNS traffic.

Key Results

  • Superior Performance on Public Datasets: MNForest consistently outperformed state-of-the-art open-set recognition models (SEEN, EVM, SENCForest, ASG, KNNENS) across various SENC and EPC scenarios on the USPS, Digits, JAFFE, and Pix10P datasets. It achieved the highest micro-F1 and macro-F1 scores in most configurations.
  • High Unknown Pattern Detection Rate (UDR): MNForest demonstrated strong capabilities in identifying unknown patterns, often outperforming baselines, which is critical for detecting novel DNS tunneling attacks.
  • Effective Handling of Class Imbalance: The model maintained high macro-F1 scores on imbalanced datasets, indicating its resilience to the rarity of malicious samples, a common issue in DNS tunneling detection.
  • Strong Performance on Real-world DNS Traffic: In practical DNS tunneling detection scenarios, MNForest achieved the highest Precision, Recall, and F1-scores across enterprise, campus, public Wi-Fi, and data center networks. For instance, it achieved a Precision of 0.954 and Recall of 0.937 on the Enterprise Network, and a Recall of 0.918 and F1-score of 0.915 on the Data Center Network.

Limitations and Future Work

  • Computational Complexity: While MNForest exhibits near-linear time complexity with respect to the number of samples in practical scenarios, the training phase can be computationally intensive, especially with a large number of trees or complex clustering convergence. The paper notes the best-case time complexity for training as O(Ttdn log n) and worst-case as O(Ttdn²).
  • Parameter Tuning: Although hyperparameters like the number of trees (T) and minimum internal node size (p) were set empirically, and the unknown identification threshold (θ) was tuned, further research could explore more automated or adaptive parameter optimization strategies.
  • Future Work: The authors suggest that the proposed MNForest and medium-neighbor mechanism offer a novel solution to multi-pattern and unknown-sample challenges. Future work could explore extending this approach to other network security domains or further refining the probability formula for UP sample determination.

Summary updated

Abstract

Domain Name System (DNS) tunneling, a stealthy attack that exploits DNS infrastructure, poses critical threats to dynamic networks and is evolving with emerging attack patterns. This study aims to accurately classify multi-pattern legitimate and malicious traffic and to identify previously unseen attack patterns. We focus on two core research questions: how to accurately classify known-pattern DNS queries and reliably identify unknown-pattern samples. The codified objective is to develop an unsupervised classification approach that integrates multi-pattern adaptation and the recognition of unknown patterns. We formalize the task as Emerging Pattern Classification and propose the Medium Neighbors Forest. It is a forest-based model that uses the “medium neighbor” mechanism and clustering to identify unknown patterns. Experiments verify that the proposed model effectively identifies unseen patterns, offering a new perspective for DNS tunneling detection.
BibTeX
@inproceedings{dong2026classifier,
  author = {Huijuan Dong and Zengwei Zheng and Shenfei Pei},
  title = {{A Classifier with Unknown Pattern Recognition for Domain Name System Tunneling Detection in Dynamic Networks}},
  booktitle = {Electronics},
  year = {2026},
  doi = {10.3390/electronics15030709},
}
Figure